You are viewing a plain text version of this content. The canonical link for it is here.
Posted to common-dev@hadoop.apache.org by Ketan Dixit <ke...@gmail.com> on 2010/03/01 17:48:36 UTC
Namespace partitioning using Locality Sensitive Hashing
Hi,
I am a graduate student in Computer Science department at SUNY Stony Brook.
I am thinking of doing a project on Hadoop for my course "Cloud Computing"
conducted by Prof. Radu Sion.
While going through the links of the "Yahoo open source projects for
students" page I found the idea
"Research on new hashing schemes for filesystem namespace partitioning"
interesting. It looks to me the idea is
to assign subtree of the whole namespace to one namenode and another subtree
to another namenode.
How LSH is better than normal hashing? Because still, a client or a fixed
namenode has to take decision of which namenode to contact in whatever
hashing ? It looks to me that requests to files under same subtree are
directed to the same namenode then the performance will be faster as the
requests to the same namenode are clustered around the a part of namespace
subtree
(For example a part of on which client is doing some operation.) Is this
assumption correct? Can I have more insight in this regard.
Thanks,
Ketan
Re: Namespace partitioning using Locality Sensitive Hashing
Posted by springring <sp...@126.com>.
I have a question.
Now that hadoop have "maper" and "reducer" , how about the solution like Map<Tree(nodepair set), root(node) > and Reduce<root(node), Tree(nodepair set)>
or that directly Reduce<root(node), nodepair> here nodepair can be look as a branch...
----- Original Message -----
From: "Konstantin Shvachko" <sh...@yahoo-inc.com>
To: <co...@hadoop.apache.org>
Sent: Tuesday, March 02, 2010 10:21 AM
Subject: Re: Namespace partitioning using Locality Sensitive Hashing
> Symlinks is a brand new feature in HDFS.
> You can read about it in
> https://issues.apache.org/jira/browse/HDFS-245
> Documentation is here:
> https://issues.apache.org/jira/secure/attachment/12434745/design-doc-v4.txt
>
> Symbolic links in HDFS can point to a directory in a different file system,
> particularly on a different HDSF cluster. They are like mount points in this case.
> So you can create a symlink on cluster C1 pointing to the root of cluster C2.
> This makes C2 a sub-namespace of C1.
>
> --Konstantin
>
> On 3/1/2010 5:42 PM, Ketan Dixit wrote:
>> Hello,
>> Thank you Konstantin and Allen for your reply. The information
>> provided really helped to improve my understanding.
>> However I still have few questions.
>> How Symlinks/ soft links are used to solve the probem of partitioning.
>> (Where do the symlinks point to? All the mapping is
>> stored in memory but symlinks point to file objects? This is little
>> confusing to me)
>> Can you please provide insight into this?
>>
>> Thanks,
>> Ketan
>>
>> On Mon, Mar 1, 2010 at 3:26 PM, Konstantin Shvachko<sh...@yahoo-inc.com> wrote:
>>>
>>> Hi Ketan,
>>>
>>> AFAIU, hashing is used to map files and directories into different name-nodes.
>>> Suppose you use a simple hash function on a file path h(path), and that files
>>> with the same hash value (or within a hash range) are mapped to the same name-node.
>>> Then files with the same parent will be randomly mapped into different
>>> name-nodes: Pr(h(/dir/file1) = h(/dir/file2)) - is small.
>>>
>>> The ides with LSH is to add some locality factor in the hash function in order
>>> to increase probability of placing files from the same directory (or a subtree)
>>> into the same name-node.
>>>
>>> Example 1.
>>> Suppose that you apply MD5 only to the path to the parent rather
>>> then to the entire file path: h(/root/dir/file) = MD5(/root/dir)
>>> Then all files of the same directory will have the same hash value and therefore
>>> will be mapped into the same name-node.
>>>
>>> Example 2.
>>> If a path consists of path components pi, where i = 1,..,n
>>> Lets define the following hash function:
>>> h(/p1/.../pn) = 0, if n< 7
>>> h(/p1/.../pn) = MD5(/p1/.../p7), if n>= 7
>>> With this hash function each subtree rooted at level 7 of the namepsace hierarchy
>>> will be entirely mapped to the same name-node.
>>>
>>> There could be more elaborate examples.
>>>
>>> Symlinks do provide a way to partition the namespace, as Allen points out,
>>> although this is a static partitioning. Static partitions as opposed to dynamic
>>> ones do not guarantee that the partitions will be "equal" in size, where "size"
>>> may have different meanings (like number of files, or space occupied by the
>>> files, or number of blocks).
>>> A good hash function need to conform to some equal partitioning requirement.
>>> Function from Example 2 would be considered bad in this sense, while Example 1
>>> defines a good function.
>>>
>>> This is my take on the problem. Hope it makes sense,
>>> --Konstantin
>>>
>>>
>>> On 3/1/2010 8:48 AM, Ketan Dixit wrote:
>>>>
>>>> Hi,
>>>> I am a graduate student in Computer Science department at SUNY Stony Brook.
>>>> I am thinking of doing a project on Hadoop for my course "Cloud Computing"
>>>> conducted by Prof. Radu Sion.
>>>> While going through the links of the "Yahoo open source projects for
>>>> students" page I found the idea
>>>> "Research on new hashing schemes for filesystem namespace partitioning"
>>>> interesting. It looks to me the idea is
>>>> to assign subtree of the whole namespace to one namenode and another subtree
>>>> to another namenode.
>>>> How LSH is better than normal hashing? Because still, a client or a fixed
>>>> namenode has to take decision of which namenode to contact in whatever
>>>> hashing ? It looks to me that requests to files under same subtree are
>>>> directed to the same namenode then the performance will be faster as the
>>>> requests to the same namenode are clustered around the a part of namespace
>>>> subtree
>>>> (For example a part of on which client is doing some operation.) Is this
>>>> assumption correct? Can I have more insight in this regard.
>>>>
>>>>
>>>>
>>>> Thanks,
>>>> Ketan
>>>>
>>>
>>
>
Re: Namespace partitioning using Locality Sensitive Hashing
Posted by Konstantin Shvachko <sh...@yahoo-inc.com>.
Symlinks is a brand new feature in HDFS.
You can read about it in
https://issues.apache.org/jira/browse/HDFS-245
Documentation is here:
https://issues.apache.org/jira/secure/attachment/12434745/design-doc-v4.txt
Symbolic links in HDFS can point to a directory in a different file system,
particularly on a different HDSF cluster. They are like mount points in this case.
So you can create a symlink on cluster C1 pointing to the root of cluster C2.
This makes C2 a sub-namespace of C1.
--Konstantin
On 3/1/2010 5:42 PM, Ketan Dixit wrote:
> Hello,
> Thank you Konstantin and Allen for your reply. The information
> provided really helped to improve my understanding.
> However I still have few questions.
> How Symlinks/ soft links are used to solve the probem of partitioning.
> (Where do the symlinks point to? All the mapping is
> stored in memory but symlinks point to file objects? This is little
> confusing to me)
> Can you please provide insight into this?
>
> Thanks,
> Ketan
>
> On Mon, Mar 1, 2010 at 3:26 PM, Konstantin Shvachko<sh...@yahoo-inc.com> wrote:
>>
>> Hi Ketan,
>>
>> AFAIU, hashing is used to map files and directories into different name-nodes.
>> Suppose you use a simple hash function on a file path h(path), and that files
>> with the same hash value (or within a hash range) are mapped to the same name-node.
>> Then files with the same parent will be randomly mapped into different
>> name-nodes: Pr(h(/dir/file1) = h(/dir/file2)) - is small.
>>
>> The ides with LSH is to add some locality factor in the hash function in order
>> to increase probability of placing files from the same directory (or a subtree)
>> into the same name-node.
>>
>> Example 1.
>> Suppose that you apply MD5 only to the path to the parent rather
>> then to the entire file path: h(/root/dir/file) = MD5(/root/dir)
>> Then all files of the same directory will have the same hash value and therefore
>> will be mapped into the same name-node.
>>
>> Example 2.
>> If a path consists of path components pi, where i = 1,..,n
>> Lets define the following hash function:
>> h(/p1/.../pn) = 0, if n< 7
>> h(/p1/.../pn) = MD5(/p1/.../p7), if n>= 7
>> With this hash function each subtree rooted at level 7 of the namepsace hierarchy
>> will be entirely mapped to the same name-node.
>>
>> There could be more elaborate examples.
>>
>> Symlinks do provide a way to partition the namespace, as Allen points out,
>> although this is a static partitioning. Static partitions as opposed to dynamic
>> ones do not guarantee that the partitions will be "equal" in size, where "size"
>> may have different meanings (like number of files, or space occupied by the
>> files, or number of blocks).
>> A good hash function need to conform to some equal partitioning requirement.
>> Function from Example 2 would be considered bad in this sense, while Example 1
>> defines a good function.
>>
>> This is my take on the problem. Hope it makes sense,
>> --Konstantin
>>
>>
>> On 3/1/2010 8:48 AM, Ketan Dixit wrote:
>>>
>>> Hi,
>>> I am a graduate student in Computer Science department at SUNY Stony Brook.
>>> I am thinking of doing a project on Hadoop for my course "Cloud Computing"
>>> conducted by Prof. Radu Sion.
>>> While going through the links of the "Yahoo open source projects for
>>> students" page I found the idea
>>> "Research on new hashing schemes for filesystem namespace partitioning"
>>> interesting. It looks to me the idea is
>>> to assign subtree of the whole namespace to one namenode and another subtree
>>> to another namenode.
>>> How LSH is better than normal hashing? Because still, a client or a fixed
>>> namenode has to take decision of which namenode to contact in whatever
>>> hashing ? It looks to me that requests to files under same subtree are
>>> directed to the same namenode then the performance will be faster as the
>>> requests to the same namenode are clustered around the a part of namespace
>>> subtree
>>> (For example a part of on which client is doing some operation.) Is this
>>> assumption correct? Can I have more insight in this regard.
>>>
>>>
>>>
>>> Thanks,
>>> Ketan
>>>
>>
>
Re: Namespace partitioning using Locality Sensitive Hashing
Posted by Eli Collins <el...@cloudera.com>.
Hey Brian,
Great points. Agree that federating a set of file systems via symlinks
doesn't solve the general problem of scaling a namespace.
Imagine GFS' "Name Spaces" was mostly useful for systems that grew w/o
much need for rebalancing, eg log storage.
Thanks,
Eli
On Mon, Mar 1, 2010 at 6:31 PM, Brian Bockelman <bb...@cse.unl.edu> wrote:
>
> Hey Eli,
>
> From past experience, static, manual namespace partitioning can really get you in trouble - you have to manually keep things balanced.
>
> The following things can go wrong:
>
> 1) One of your pesky users grows unexpectedly by a factor of 10.
> 2) Your entire system grew so much that there's not enough excess capacity to split and balance the cluster into new pieces - the extra bandwidth required would drive down production performance too much (or you need downtime to do it and can't afford the downtime).
> 3) Your production system began as a proof of concept, and your file name system makes it hard to split in a sane manner because you never planned on splitting the proof of concept in the first place!
>
> Any one of these can be solved with enough effort, but it can require a huge amount of effort if you don't realize things soon enough! In fact, I seem to remember a ACM Queue article with the original Google authors who cited explosive application growth as one reason that manual balancing quickly fell out of favor.
>
> I wouldn't deny that symlinks are an incredible tool to fight namespace growth - but it's not a 100% solution.
>
> That said, I'm looking forward to symlinks to solve a few local problems!
>
> Brian
>
> On Mar 1, 2010, at 8:15 PM, Eli Collins wrote:
>
>> On Mon, Mar 1, 2010 at 5:42 PM, Ketan Dixit <ke...@gmail.com> wrote:
>>> Hello,
>>> Thank you Konstantin and Allen for your reply. The information
>>> provided really helped to improve my understanding.
>>> However I still have few questions.
>>> How Symlinks/ soft links are used to solve the probem of partitioning.
>>> (Where do the symlinks point to? All the mapping is
>>> stored in memory but symlinks point to file objects? This is little
>>> confusing to me)
>>> Can you please provide insight into this?
>>
>> The idea is to use symlinks to present a single namespace to clients
>> that is backed by multiple file systems (hdfs or other supported
>> hadoop file systems). Eg a "root" HDFS file system could contain links
>> to other file systems, eg /dir1 could point to S3, /dir2 could point
>> to a local file system, /dir3 could point to another HDFS file system,
>> etc. Clients always contact the "root" HDFS file system but are
>> transparently redirected to other file systems by symlinks. This way a
>> single namespace is partitioned across multiple file systems, but the
>> client only needs to know about the root file system. This
>> partitioning is static (you have to establish the symlinks), though
>> you can grow on the fly by adding file systems and links that point to
>> them.
>>
>> Thanks,
>> Eli
>
>
Re: Namespace partitioning using Locality Sensitive Hashing
Posted by Brian Bockelman <bb...@cse.unl.edu>.
Hey Eli,
From past experience, static, manual namespace partitioning can really get you in trouble - you have to manually keep things balanced.
The following things can go wrong:
1) One of your pesky users grows unexpectedly by a factor of 10.
2) Your entire system grew so much that there's not enough excess capacity to split and balance the cluster into new pieces - the extra bandwidth required would drive down production performance too much (or you need downtime to do it and can't afford the downtime).
3) Your production system began as a proof of concept, and your file name system makes it hard to split in a sane manner because you never planned on splitting the proof of concept in the first place!
Any one of these can be solved with enough effort, but it can require a huge amount of effort if you don't realize things soon enough! In fact, I seem to remember a ACM Queue article with the original Google authors who cited explosive application growth as one reason that manual balancing quickly fell out of favor.
I wouldn't deny that symlinks are an incredible tool to fight namespace growth - but it's not a 100% solution.
That said, I'm looking forward to symlinks to solve a few local problems!
Brian
On Mar 1, 2010, at 8:15 PM, Eli Collins wrote:
> On Mon, Mar 1, 2010 at 5:42 PM, Ketan Dixit <ke...@gmail.com> wrote:
>> Hello,
>> Thank you Konstantin and Allen for your reply. The information
>> provided really helped to improve my understanding.
>> However I still have few questions.
>> How Symlinks/ soft links are used to solve the probem of partitioning.
>> (Where do the symlinks point to? All the mapping is
>> stored in memory but symlinks point to file objects? This is little
>> confusing to me)
>> Can you please provide insight into this?
>
> The idea is to use symlinks to present a single namespace to clients
> that is backed by multiple file systems (hdfs or other supported
> hadoop file systems). Eg a "root" HDFS file system could contain links
> to other file systems, eg /dir1 could point to S3, /dir2 could point
> to a local file system, /dir3 could point to another HDFS file system,
> etc. Clients always contact the "root" HDFS file system but are
> transparently redirected to other file systems by symlinks. This way a
> single namespace is partitioned across multiple file systems, but the
> client only needs to know about the root file system. This
> partitioning is static (you have to establish the symlinks), though
> you can grow on the fly by adding file systems and links that point to
> them.
>
> Thanks,
> Eli
Re: Namespace partitioning using Locality Sensitive Hashing
Posted by Ketan Dixit <ke...@gmail.com>.
Folks,
I am still wondering why would an LSH (Locality Sensitive Hashing)
based partitioning scheme provide better scalability than a normal
cryptographic hash scheme. Is there a chance that LSH will offer
better performance than a normal one?
Best,
Ketan
On Mon, Mar 1, 2010 at 9:15 PM, Eli Collins <el...@cloudera.com> wrote:
> On Mon, Mar 1, 2010 at 5:42 PM, Ketan Dixit <ke...@gmail.com> wrote:
>> Hello,
>> Thank you Konstantin and Allen for your reply. The information
>> provided really helped to improve my understanding.
>> However I still have few questions.
>> How Symlinks/ soft links are used to solve the probem of partitioning.
>> (Where do the symlinks point to? All the mapping is
>> stored in memory but symlinks point to file objects? This is little
>> confusing to me)
>> Can you please provide insight into this?
>
> The idea is to use symlinks to present a single namespace to clients
> that is backed by multiple file systems (hdfs or other supported
> hadoop file systems). Eg a "root" HDFS file system could contain links
> to other file systems, eg /dir1 could point to S3, /dir2 could point
> to a local file system, /dir3 could point to another HDFS file system,
> etc. Clients always contact the "root" HDFS file system but are
> transparently redirected to other file systems by symlinks. This way a
> single namespace is partitioned across multiple file systems, but the
> client only needs to know about the root file system. This
> partitioning is static (you have to establish the symlinks), though
> you can grow on the fly by adding file systems and links that point to
> them.
>
> Thanks,
> Eli
>
Re: Namespace partitioning using Locality Sensitive Hashing
Posted by Eli Collins <el...@cloudera.com>.
On Mon, Mar 1, 2010 at 5:42 PM, Ketan Dixit <ke...@gmail.com> wrote:
> Hello,
> Thank you Konstantin and Allen for your reply. The information
> provided really helped to improve my understanding.
> However I still have few questions.
> How Symlinks/ soft links are used to solve the probem of partitioning.
> (Where do the symlinks point to? All the mapping is
> stored in memory but symlinks point to file objects? This is little
> confusing to me)
> Can you please provide insight into this?
The idea is to use symlinks to present a single namespace to clients
that is backed by multiple file systems (hdfs or other supported
hadoop file systems). Eg a "root" HDFS file system could contain links
to other file systems, eg /dir1 could point to S3, /dir2 could point
to a local file system, /dir3 could point to another HDFS file system,
etc. Clients always contact the "root" HDFS file system but are
transparently redirected to other file systems by symlinks. This way a
single namespace is partitioned across multiple file systems, but the
client only needs to know about the root file system. This
partitioning is static (you have to establish the symlinks), though
you can grow on the fly by adding file systems and links that point to
them.
Thanks,
Eli
Re: Namespace partitioning using Locality Sensitive Hashing
Posted by Ketan Dixit <ke...@gmail.com>.
Hello,
Thank you Konstantin and Allen for your reply. The information
provided really helped to improve my understanding.
However I still have few questions.
How Symlinks/ soft links are used to solve the probem of partitioning.
(Where do the symlinks point to? All the mapping is
stored in memory but symlinks point to file objects? This is little
confusing to me)
Can you please provide insight into this?
Thanks,
Ketan
On Mon, Mar 1, 2010 at 3:26 PM, Konstantin Shvachko <sh...@yahoo-inc.com> wrote:
>
> Hi Ketan,
>
> AFAIU, hashing is used to map files and directories into different name-nodes.
> Suppose you use a simple hash function on a file path h(path), and that files
> with the same hash value (or within a hash range) are mapped to the same name-node.
> Then files with the same parent will be randomly mapped into different
> name-nodes: Pr(h(/dir/file1) = h(/dir/file2)) - is small.
>
> The ides with LSH is to add some locality factor in the hash function in order
> to increase probability of placing files from the same directory (or a subtree)
> into the same name-node.
>
> Example 1.
> Suppose that you apply MD5 only to the path to the parent rather
> then to the entire file path: h(/root/dir/file) = MD5(/root/dir)
> Then all files of the same directory will have the same hash value and therefore
> will be mapped into the same name-node.
>
> Example 2.
> If a path consists of path components pi, where i = 1,..,n
> Lets define the following hash function:
> h(/p1/.../pn) = 0, if n < 7
> h(/p1/.../pn) = MD5(/p1/.../p7), if n >= 7
> With this hash function each subtree rooted at level 7 of the namepsace hierarchy
> will be entirely mapped to the same name-node.
>
> There could be more elaborate examples.
>
> Symlinks do provide a way to partition the namespace, as Allen points out,
> although this is a static partitioning. Static partitions as opposed to dynamic
> ones do not guarantee that the partitions will be "equal" in size, where "size"
> may have different meanings (like number of files, or space occupied by the
> files, or number of blocks).
> A good hash function need to conform to some equal partitioning requirement.
> Function from Example 2 would be considered bad in this sense, while Example 1
> defines a good function.
>
> This is my take on the problem. Hope it makes sense,
> --Konstantin
>
>
> On 3/1/2010 8:48 AM, Ketan Dixit wrote:
>>
>> Hi,
>> I am a graduate student in Computer Science department at SUNY Stony Brook.
>> I am thinking of doing a project on Hadoop for my course "Cloud Computing"
>> conducted by Prof. Radu Sion.
>> While going through the links of the "Yahoo open source projects for
>> students" page I found the idea
>> "Research on new hashing schemes for filesystem namespace partitioning"
>> interesting. It looks to me the idea is
>> to assign subtree of the whole namespace to one namenode and another subtree
>> to another namenode.
>> How LSH is better than normal hashing? Because still, a client or a fixed
>> namenode has to take decision of which namenode to contact in whatever
>> hashing ? It looks to me that requests to files under same subtree are
>> directed to the same namenode then the performance will be faster as the
>> requests to the same namenode are clustered around the a part of namespace
>> subtree
>> (For example a part of on which client is doing some operation.) Is this
>> assumption correct? Can I have more insight in this regard.
>>
>>
>>
>> Thanks,
>> Ketan
>>
>
Re: Namespace partitioning using Locality Sensitive Hashing
Posted by Konstantin Shvachko <sh...@yahoo-inc.com>.
Hi Ketan,
AFAIU, hashing is used to map files and directories into different name-nodes.
Suppose you use a simple hash function on a file path h(path), and that files
with the same hash value (or within a hash range) are mapped to the same name-node.
Then files with the same parent will be randomly mapped into different
name-nodes: Pr(h(/dir/file1) = h(/dir/file2)) - is small.
The ides with LSH is to add some locality factor in the hash function in order
to increase probability of placing files from the same directory (or a subtree)
into the same name-node.
Example 1.
Suppose that you apply MD5 only to the path to the parent rather
then to the entire file path: h(/root/dir/file) = MD5(/root/dir)
Then all files of the same directory will have the same hash value and therefore
will be mapped into the same name-node.
Example 2.
If a path consists of path components pi, where i = 1,..,n
Lets define the following hash function:
h(/p1/.../pn) = 0, if n < 7
h(/p1/.../pn) = MD5(/p1/.../p7), if n >= 7
With this hash function each subtree rooted at level 7 of the namepsace hierarchy
will be entirely mapped to the same name-node.
There could be more elaborate examples.
Symlinks do provide a way to partition the namespace, as Allen points out,
although this is a static partitioning. Static partitions as opposed to dynamic
ones do not guarantee that the partitions will be "equal" in size, where "size"
may have different meanings (like number of files, or space occupied by the
files, or number of blocks).
A good hash function need to conform to some equal partitioning requirement.
Function from Example 2 would be considered bad in this sense, while Example 1
defines a good function.
This is my take on the problem. Hope it makes sense,
--Konstantin
On 3/1/2010 8:48 AM, Ketan Dixit wrote:
> Hi,
> I am a graduate student in Computer Science department at SUNY Stony Brook.
> I am thinking of doing a project on Hadoop for my course "Cloud Computing"
> conducted by Prof. Radu Sion.
> While going through the links of the "Yahoo open source projects for
> students" page I found the idea
> "Research on new hashing schemes for filesystem namespace partitioning"
> interesting. It looks to me the idea is
> to assign subtree of the whole namespace to one namenode and another subtree
> to another namenode.
> How LSH is better than normal hashing? Because still, a client or a fixed
> namenode has to take decision of which namenode to contact in whatever
> hashing ? It looks to me that requests to files under same subtree are
> directed to the same namenode then the performance will be faster as the
> requests to the same namenode are clustered around the a part of namespace
> subtree
> (For example a part of on which client is doing some operation.) Is this
> assumption correct? Can I have more insight in this regard.
>
>
>
> Thanks,
> Ketan
>
Re: Namespace partitioning using Locality Sensitive Hashing
Posted by Allen Wittenauer <aw...@linkedin.com>.
On 3/1/10 8:48 AM, "Ketan Dixit" <ke...@gmail.com> wrote:
> How LSH is better than normal hashing? Because still, a client or a fixed
> namenode has to take decision of which namenode to contact in whatever
> hashing ? It looks to me that requests to files under same subtree are
> directed to the same namenode then the performance will be faster as the
> requests to the same namenode are clustered around the a part of namespace
> subtree
> (For example a part of on which client is doing some operation.) Is this
> assumption correct? Can I have more insight in this regard.
IIRC, the thought process was this was a scalability feature, not being done
for performance. There is a general reluctance by the HDFS dev's to only
store hot file metadata structures in memory. So in order to prevent the
JVM's heap size from spiral out of control, using separate name spaces
allows you to divide and conquer.
With symlinks , this feature is essentially a solved problem. The 'who is
the decision maker' issue is now the client's to resolve. As an added
bonus, because it is URI based, the client may get pushed off to a
completely different service. [This is definitely a feature--just think,
you can store really hot files on the local file system, completely
bypassing the overhead that HDFS incurs.]