System and method for clustering distributed hash table entries
First Claim
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 composite key for the data object, and wherein the composite key comprises a sharable user key and one or more other elements usable to uniquely identify the instance of the data object;
generating keymap information for the instance of the data object that maps the user key to a locator and the locator to the instance of the data object;
applying a hash function to a portion of the composite key that is less than all of the composite key;
determining a computing node on which to store the keymap information dependent on a result of said applying the hash function, wherein the computing node is one of a plurality of computing nodes that each store a portion of a distributed hash table;
storing the keymap information on the determined computing node, wherein the determined computing node also stores keymap information for other data object instances that are related to the instance of the data object.
1 Assignment
0 Petitions
Accused Products
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.
87 Citations
35 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 composite key for the data object, and wherein the composite key comprises a sharable user key and one or more other elements usable to uniquely identify the instance of the data object; generating keymap information for the instance of the data object that maps the user key to a locator and the locator to the instance of the data object; applying a hash function to a portion of the composite key that is less than all of the composite key; determining a computing node on which to store the keymap information dependent on a result of said applying the hash function, wherein the computing node is one of a plurality of computing nodes that each store a portion of a distributed hash table; storing the keymap information on the determined computing node, wherein the determined computing node also stores keymap information for other data object instances that are related to the instance of the data object. - View Dependent Claims (2, 3, 4, 5, 6)
-
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 composite key for the data object, wherein the composite key comprises a sharable user key and one or more other elements usable to uniquely identify the instance of the data object, and wherein the keymap information maps the user key to a locator and the locator to the instance of the data object; applying a hash function to a portion of the composite key that is less than all of the composite key; determining a computing node on which to store the keymap information dependent on a result of said applying the hash function, wherein the computing node is one of a plurality of computing nodes that each store a portion of a distributed hash table; storing the keymap information on the determined computing node, 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. - View Dependent Claims (8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
-
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 composite key for the data object, wherein the composite key comprises a sharable user key and one or more other elements usable to uniquely identify the instance of the data object, and wherein the keymap information maps the user key to a locator and the locator to the instance of the data object; applying a hash function to a portion of the composite key that is less than all of the composite key; determining a computing node on which to store the keymap information dependent on a result of said applying the hash function, wherein the computing node is one of a plurality of computing nodes that each store a portion of a distributed hash table; storing the keymap information on the determined computing node, 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. - View Dependent Claims (20, 21, 22, 23, 24, 25, 26, 27, 28)
-
-
29. A system, comprising:
-
a distributed hash table that is implemented on a plurality of computing nodes and that caches keymap information for a plurality of data objects stored in a persistent data store; one or more processors; and a memory coupled to the one or more processors and storing program instructions that when executed by the one or more processors cause the one or more processors to perform; receiving a request to store keymap information for an instance of a data object stored in the persistent data store, wherein the request comprises a composite key for the data object, and wherein the composite key comprises a sharable user key and one or more other elements usable to uniquely identify the instance of the data object, and wherein the keymap information maps the user key to a locator and the locator to the instance of the data object; applying a hash function to a portion of the composite key that is less than all of the composite key; determining a computing node on which to store the keymap information in the distributed hash table dependent on a result of said applying the hash function, wherein the computing node is one of the plurality of computing nodes, and where each of the plurality of computing nodes stores a portion of the distributed hash table; storing the keymap information on the determined computing node, wherein the determined computing node also stores keymap information for other data object instances that are related to the instance of the data object. - View Dependent Claims (30, 31, 32, 33, 34, 35)
-
Specification