System and method for clustering distributed hash table entries

• US 10,235,405 B2
• Filed: 09/29/2014
• Issued: 03/19/2019
• Est. Priority Date: 12/23/2010
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: McHugh, Jason G., Gattu, Praveen Kumar, Ten-Pow, Michael A., Denny-Brown, II, Derek Ernest
• Primary Examiner(s): Ehichioya, Irete F
• Assistant Examiner(s): Johnson, Johnese T
• Application Number:
  US14/500,404
• Publication Number:
  US 20150012539A1
• Time in Patent Office: 1,632 Days
• Field of Search: 707737
• CPC Class Codes: G06F 16/1873 Versioning file systems, temporal file systems, e.g. file system supporting different historic versions of files
• CPC Class Codes: G06F 16/2255 Hash tables

Abstract

A distributed storage system may store data object instances in persistent storage and may store keymap information for those data object instances in a distributed hash table on multiple computing nodes. Each data object instance may include a composite key containing a user key. The keymap information for each data object instance may map the user key to a locator and the locator to the data object instance. A request to store or retrieve keymap information for a data object instance may be routed to a particular computing node based on a consistent hashing scheme in which a hash function is applied to a portion of the composite key of the data object instance. Thus, related entries may be clustered on the same computing nodes. The portion of the key to which the hash function is applied may include a pre-determined number of bits or be identified using a delimiter.

Claims

1. A method, comprising:

performing, by a computer system that stores a plurality of data objects in a distributed storage system;

receiving a request to store an instance of a data object in the distributed storage system, wherein the request comprises a key for the data object;

generating keymap information for the instance of the data object that maps at least part of the key from the request to a locator and the locator to the instance of the data object;

applying a hash function to a portion of the key from the request that is less than all of the key from the request to generate a hash value;

determining a computing node on which to store the keymap information dependent on the hash value generated from said applying the hash function to the portion of the key from the request, wherein the computing node is determined without applying the hash function to all of the key from the request, and wherein the computing node is one of a plurality of computing nodes that each store a portion of a distributed hash table; and

storing the keymap information on the determined computing node.

2. The method of claim 1, further comprising:

receiving a request to retrieve the instance of the data object, wherein the request specifies the key;

applying a hash function to a portion of the specified key that is less than all of the specified key;

determining the computing node on which the keymap information is stored dependent on a result of said applying the hash function to a portion of the specified key; and

returning keymap information for the instance of the data object.

3. The method of claim 2, further comprising retrieving the instance of the data object from the distributed storage system dependent on the returned keymap information.

4. The method of claim 1, wherein the key comprises a shareable user key, and wherein keymap information for all data object instances having the shareable user key is stored on the same computing node.

5. The method of claim 1, wherein the portion of the key to which the hash function is applied is dependent on the position of a delimiter in the key.

6. The method of claim 1, wherein the portion of the key to which the hash function is applied comprises a pre-determined number of bits.

7. A method, comprising:

performing, by a computer system that stores a plurality of data objects in a distributed storage system;

receiving a request to store keymap information for an instance of a data object to be stored in the distributed storage system, wherein the request comprises a key for the data object, wherein the keymap information maps at least part of the key from the request to a locator and the locator to the instance of the data object;

applying a hash function to a portion of the key from the request that is less than all of the key from the request to generate a hash value;

determining a computing node on which to store the keymap information dependent on the hash value generated from said applying the hash function to the portion of the key from the request, wherein determining the computing node includes determining the computing node without applying the hash function to all of the key from the request; and

storing the keymap information on the determined computing node.

8. The method of claim 7, wherein the determined computing node also stores keymap information for other data object instances that are in a same key cluster as the data object, and wherein the key cluster is defined by a set of keys for data object instances to be stored on the same computing node.

9. The method of claim 7, further comprising:

receiving a request to retrieve the instance of the data object, wherein the request specifies the key;

applying a hash function to a portion of the specified key that is less than all of the specified key;

determining the computing node on which the keymap information is stored dependent on a result of said applying the hash function to a portion of the specified key; and

returning keymap information for the instance of the data object.

10. The method of claim 9, further comprising retrieving the instance of the data object from the distributed storage system dependent on the returned keymap information.

11. The method of claim 7, wherein the key comprises a sharable user key, and wherein keymap information for all data object instances having the user key is stored on the same computing node.

12. The method of claim 7, wherein the portion of the key to which the hash function is applied is dependent on the position of a delimiter in the key.

13. The method of claim 7, wherein the portion of the key to which the hash function is applied comprises a pre-determined number of bits.

14. The method of claim 7, wherein the key comprises a sharable user key, and wherein the portion of the key to which the hash function is applied comprises at least a portion of the user key.

15. The method of claim 7, further comprising:

receiving a request for keymap information for a data object, wherein the request includes a particular user key but does not include a version identifier;

determining the latest version of data object instances that are stored in the distributed storage system and that have the particular user key from among a plurality of stored data object instances having the particular user key, wherein determining the latest version comprises examining keymap information for two data object instances having the particular user key; and

returning keymap information for the latest version of data object instances that are stored in the distributed storage system and that have the particular user key.

16. The method of claim 15, wherein the keymap information for the two data object instances having the particular user key is stored on the same computing node.

17. The method of claim 7, wherein the computing node is one of a plurality of computing nodes that each store a portion of a distributed hash table, and wherein the distributed hash table caches keymap information for data objects stored in the distributed storage system, wherein said storing the keymap information on the determined computing node comprises storing the keymap information in the distributed hash table, and wherein the keymap information is indexed in the distributed hash table by a hash value generated as a result of said applying the hash function.

18. The method of claim 7, further comprising storing the keymap information for the instance of the data object in persistent storage.

19. A non-transitory, computer-readable storage medium storing program instructions that when executed on one or more computers cause the one or more computers to perform:

receiving a request to store keymap information for an instance of a data object to be stored in a distributed storage system, wherein the request comprises a key for the data object, wherein the keymap information maps at least part of the key from the request to a locator and the locator to the instance of the data object;

applying a hash function to a portion of the key from the request that is less than all of the key from the request to generate a hash value;

determining a computing node on which to store the keymap information dependent on the hash value generated from said applying the hash function to the portion of the key from the request, wherein determining the computing node includes determining the computing node without applying the hash function to all of the key from the request; and

storing the keymap information on the determined computing node.

20. The storage medium of claim 19, wherein the computing node is one of a plurality of computing nodes that each store a portion of a distributed hash table, wherein the determined computing node also stores keymap information for other data object instances that are in a same key cluster as the data object, and wherein the key cluster is defined by a set of keys for data object instances to be stored on the same computing node.