diff options
Diffstat (limited to 'doc/features/dht.md')
| -rw-r--r-- | doc/features/dht.md | 223 |
1 files changed, 223 insertions, 0 deletions
diff --git a/doc/features/dht.md b/doc/features/dht.md new file mode 100644 index 00000000000..c35dd6d0c27 --- /dev/null +++ b/doc/features/dht.md @@ -0,0 +1,223 @@ +# How GlusterFS Distribution Works + +The defining feature of any scale-out system is its ability to distribute work +or data among many servers. Accordingly, people in the distributed-system +community have developed many powerful techniques to perform such distribution, +but those techniques often remain little known or understood even among other +members of the file system and database communities that benefit. This +confusion is represented even in the name of the GlusterFS component that +performs distribution - DHT, which stands for Distributed Hash Table but is not +actually a DHT as that term is most commonly used or defined. The way +GlusterFS's DHT works is based on a few basic principles: + + * All operations are driven by clients, which are all equal. There are no + special nodes with special knowledge of where files are or should be. + + * Directories exist on all subvolumes (bricks or lower-level aggregations of + bricks); files exist on only one. + + * Files are assigned to subvolumes based on *consistent hashing*, and even + more specifically a form of consistent hashing exemplified by Amazon's + [Dynamo][dynamo]. + +The result of all this is that users are presented with a set of files that is +the union of the files present on all subvolumes. The following sections +describe how this "uniting" process actually works. + +## Layouts + +The conceptual basis of Dynamo-style consistent hashing is of numbers around a +circle, like a clock. First, the circle is divided into segments and those +segments are assigned to bricks. (For the sake of simplicity we'll use +"bricks" hereafter even though they might actually be replicated/striped +subvolumes.) Several factors guide this assignment. + + * Assignments are done separately for each directory. + + * Historically, segments have all been the same size. However, this can lead + to smaller bricks becoming full while plenty of space remains on larger + ones. If the *cluster.weighted-rebalance* option is set, segments sizes + will be proportional to brick sizes. + + * Assignments need not include all bricks in the volume. If the + *cluster.subvols-per-directory* option is set, only that many bricks will + receive assignments for that directory. + +However these assignments are done, they collectively become what we call a +*layout* for a directory. This layout is then stored using extended +attributes, with each brick's copy of that extended attribute on that directory +consisting of four 32-bit fields. + + * A version, which might be DHT\_HASH\_TYPE\_DM to represent an assignment as + described above, or DHT\_HASH\_TYPE\_DM\_USER to represent an assignment made + manually by the user (or external script). + + * A "commit hash" which will be described later. + + * The first number in the assigned range (segment). + + * The last number in the assigned range. + +For example, the extended attributes representing a weighted assignment between +three bricks, one twice as big as the others, might look like this. + + * Brick A (the large one): DHT\_HASH\_TYPE\_DM 1234 0 0x7ffffff + + * Brick B: DHT\_HASH\_TYPE\_DM 1234 0x80000000 0xbfffffff + + * Brick C: DHT\_HASH\_TYPE\_DM 1234 0xc0000000 0xffffffff + +## Placing Files + +To place a file in a directory, we first need a layout for that directory - as +described above. Next, we calculate a hash for the file. To minimize +collisions either between files in the same directory with different names or +between files in different directories with the same name, this hash is +generated using both the (containing) directory's unique GFID and the file's +name. This hash is then matched to one of the layout assignments, to yield +what we call a *hashed location*. For example, consider the layout shown +above. The hash 0xabad1dea is between 0x80000000 and 0xbfffffff, so the +corresponding file's hashed location would be on Brick B. A second file with a +hash of 0xfaceb00c would be assigned to Brick C by the same reasoning. + +## Looking Up Files + +Because layout assignments might change, especially as bricks are added or +removed, finding a file involves more than calculating its hashed location and +looking there. That is in fact the first step, and works most of the time - +i.e. the file is found where we expected it to be - but there are a few more +steps when that's not the case. Historically, the next step has been to look +for the file **everywhere** - i.e. to broadcast our lookup request to all +subvolumes. If the file isn't found that way, it doesn't exist. At this +point, an open that requires the file's presence will fail, or a create/mkdir +that requires its absence will be allowed to continue. + +Regardless of whether a file is found at its hashed location or elsewhere, we +now know its *cached location*. As the name implies, this is stored within DHT +to satisfy future lookups. If it's not the same as the hashed location, we +also take an extra step. This step is the creation of a *linkfile*, which is a +special stub left at the **hashed** location pointing to the **cached** +location. Therefore, if a client naively looks for a file at its hashed +location and finds a linkfile instead, it can use that linkfile to look up the +file where it really is instead of needing to inquire everywhere. + +## Rebalancing + +As bricks are added or removed, or files are renamed, many files can end up +somewhere other than at their hashed locations. When this happens, the volumes +need to be rebalanced. This process consists of two parts. + + 1. Calculate new layouts, according to the current set of bricks (and possibly + their characteristics). We call this the "fix-layout" phase. + + 2. Migrate any "misplaced" files to their correct (hashed) locations, and + clean up any linkfiles which are no longer necessary. We call this the + "migrate-data" phase. + +Usually, these two phases are done together. (In fact, the code for them is +somewhat intermingled.) However, the migrate-data phase can involve a lot of +I/O and be very disruptive, so users can do just the fix-layout phase and defer +migrate-data until a more convenient time. This allows new files to be placed +on new bricks, even though old files might still be in the "wrong" place. + +When calculating a new layout to replace an old one, DHT specifically tries to +maximize overlap of the assigned ranges, thus minimizing data movement. This +difference can be very large. For example, consider the case where our example +layout from earlier is updated to add a new double-sided brick. Here's a very +inefficient way to do that. + + * Brick A (the large one): 0x00000000 to 0x55555555 + + * Brick B: 0x55555556 to 0x7fffffff + + * Brick C: 0x80000000 to 0xaaaaaaaa + + * Brick D (the new one): 0xaaaaaaab to 0xffffffff + +This would cause files in the following ranges to be migrated: + + * 0x55555556 to 0x7fffffff (from A to B) + + * 0x80000000 to 0xaaaaaaaa (from B to C) + + * 0xaaaaaaab to 0xbfffffff (from B to D) + + * 0xc0000000 to 0xffffffff (from C to D) + +As an historical note, this is exactly what we used to do, and in this case it +would have meant moving 7/12 of all files in the volume. Now let's consider a +new layout that's optimized to maximize overlap with the old one. + + * Brick A: 0x00000000 to 0x55555555 + + * Brick D: 0x55555556 to 0xaaaaaaaa <- optimized insertion point + + * Brick B: 0xaaaaaaab to 0xd5555554 + + * Brick C: 0xd5555555 to 0xffffffff + +In this case we only need to move 5/12 of all files. In a volume with millions +or even billions of files, reducing data movement by 1/6 of all files is a +pretty big improvement. In the future, DHT might use "virtual node IDs" or +multiple hash rings to make rebalancing even more efficient. + +## Rename Optimizations + +With the file-lookup mechanisms we already have in place, it's not necessary to +move a file from one brick to another when it's renamed - even across +directories. It will still be found, albeit a little less efficiently. The +first client to look for it after the rename will add a linkfile, which every +other client will follow from then on. Also, every client that has found the +file once will continue to find it based on its cached location, without any +network traffic at all. Because the extra lookup cost is small, and the +movement cost might be very large, DHT renames the file "in place" on its +current brick instead (taking advantage of the fact that directories exist +everywhere). + +This optimization is further extended to handle cases where renames are very +common. For example, rsync and similar tools often use a "write new then +rename" idiom in which a file "xxx" is actually written as ".xxx.1234" and then +moved into place only after its contents have been fully written. To make this +process more efficient, DHT uses a regular expression to separate the permanent +part of a file's name (in this case "xxx") from what is likely to be a +temporary part (the leading "." and trailing ".1234"). That way, after the +file is renamed it will be in its correct hashed location - which it wouldn't +be otherwise if "xxx" and ".xxx.1234" hash differently - and no linkfiles or +broadcast lookups will be necessary. + +In fact, there are two regular expressions available for this purpose - +*cluster.rsync-hash-regex* and *cluster.extra-hash-regex*. As its name +implies, *rsync-hash-regex* defaults to the pattern that regex uses, while +*extra-hash-regex* can be set by the user to support a second tool using the +same temporary-file idiom. + +## Commit Hashes + +A very recent addition to DHT's algorithmic arsenal is intended to reduce the +number of "broadcast" lookups the it issues. If a volume is completely in +balance, then no file could exist anywhere but at its hashed location. +Therefore, if we've already looked there and not found it, then looking +elsewhere would be pointless (and wasteful). The *commit hash* mechanism is +used to detect this case. A commit hash is assigned to a volume, and +separately to each directory, and then updated according to the following +rules. + + * The volume commit hash is changed whenever actions are taken that might + cause layout assignments across all directories to become invalid - i.e. + bricks being added, removed, or replaced. + + * The directory commit hash is changed whenever actions are taken that might + cause files to be "misplaced" - e.g. when they're renamed. + + * The directory commit hash is set to the volume commit hash when the + directory is created, and whenever the directory is fully rebalanced so that + all files are at their hashed locations. + +In other words, whenever either the volume or directory commit hash is changed +that creates a mismatch. In that case we revert to the "pessimistic" +broadcast-lookup method described earlier. However, if the two hashes match +then we can with skip the broadcast lookup and return a result immediately. +This has been observed to cause a 3x performance improvement in workloads that +involve creating many small files across many bricks. + +[dynamo]: http://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf |