Keymap service architecture for a distributed storage system
First Claim
1. A system, comprising:
- a plurality of computing nodes configured to implement;
a plurality of storage nodes configured to store one or more replicas of each of a plurality of data objects, wherein each of said one or more replicas is accessible via a unique respective locator value, each node of the computing nodes comprising a processor and a memory; and
a plurality of keymap instances each configured to store keymap entries corresponding respectively to said data objects, wherein a given one of said keymap entries corresponding to a given one of said plurality of data objects indicates a mapping from a given key value corresponding to said given data object to each said respective locator value of said one or more replicas of said given data object;
wherein for said given data object, each of said plurality of keymap instances is configured to store a replica of said given keymap entry, such that said given keymap entry is replicated across said plurality of keymap instances;
wherein each of said keymap instances is further configured to index its respective stored keymap entries within a respective index data structure;
wherein each of said index data structures includes a respective plurality of index nodes arranged hierarchically and each index node having an associated tag value, wherein for each of said stored keymap entries, there exists a respective, uniquely corresponding one of said index nodes such that at most one keymap entry corresponds to any given one of said index nodes, and wherein at least some of the index data structures are unbalanced;
wherein for each given one of the index nodes, each tag value associated with each ancestor of said given index node is a prefix of the key value that is associated with the given index node; and
wherein a given one of said plurality of keymap instances selects a different one of said plurality of keymap instances at regular or irregular intervals and to at least partially synchronize said respective index data structures of said given keymap instance and said different keymap instance.
2 Assignments
0 Petitions
Accused Products
Abstract
A keymap service architecture for a distributed storage system. A system may implement storage nodes configured to store replicas of data objects, where each of the replicas is accessible via a respective locator value, and keymap instances each configured to store keymap entries corresponding respectively to the data objects. A given keymap entry may indicate a mapping from a given key value corresponding to a given data object to each respective locator value of its replicas. Each of the keymap instances may store a replica of the given keymap entry and may index its respective stored keymap entries within a respective index data structure including hierarchically arranged index nodes corresponding to keymap entries. For a given keymap entry having a given corresponding index node, each tag value associated with each ancestor of the given corresponding index node may be a prefix of the given key value.
-
Citations
49 Claims
-
1. A system, comprising:
-
a plurality of computing nodes configured to implement; a plurality of storage nodes configured to store one or more replicas of each of a plurality of data objects, wherein each of said one or more replicas is accessible via a unique respective locator value, each node of the computing nodes comprising a processor and a memory; and a plurality of keymap instances each configured to store keymap entries corresponding respectively to said data objects, wherein a given one of said keymap entries corresponding to a given one of said plurality of data objects indicates a mapping from a given key value corresponding to said given data object to each said respective locator value of said one or more replicas of said given data object; wherein for said given data object, each of said plurality of keymap instances is configured to store a replica of said given keymap entry, such that said given keymap entry is replicated across said plurality of keymap instances; wherein each of said keymap instances is further configured to index its respective stored keymap entries within a respective index data structure; wherein each of said index data structures includes a respective plurality of index nodes arranged hierarchically and each index node having an associated tag value, wherein for each of said stored keymap entries, there exists a respective, uniquely corresponding one of said index nodes such that at most one keymap entry corresponds to any given one of said index nodes, and wherein at least some of the index data structures are unbalanced; wherein for each given one of the index nodes, each tag value associated with each ancestor of said given index node is a prefix of the key value that is associated with the given index node; and wherein a given one of said plurality of keymap instances selects a different one of said plurality of keymap instances at regular or irregular intervals and to at least partially synchronize said respective index data structures of said given keymap instance and said different keymap instance. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)
-
-
17. A method, comprising:
-
one or more computer systems performing; storing one or more replicas of each of a plurality of data objects, wherein each of said one or more replicas is accessible via a unique respective locator value; storing respective replicas, within each of a plurality of keymap instances, of keymap entries corresponding respectively to said data objects, such that each of said keymap entries is replicated across said plurality of keymap instances, wherein a given one of said keymap entries corresponding to a given one of said plurality of data objects indicates a mapping from a given key value corresponding to said given data object to each said respective locator value of said one or more replicas of said given data object; indexing stored keymap entries of each of said keymap instances within a respective index data structure, wherein at least some of index data structures are unbalanced; and a given one of said plurality of keymap instances selecting a different one of said plurality of keymap instances at regular or irregular intervals and at least partially synchronizing said respective index data structures of said given keymap instance and said different keymap instance; wherein each of said index data structures includes a respective plurality of index nodes arranged hierarchically and each index node having an associated tag value, wherein for each of said stored keymap entries, there exists a respective, uniquely corresponding one of said index nodes such that at most one keymap entry corresponds to any given one of said index nodes; and wherein for each given one of the index nodes, each tag value associated with each ancestor of said given index node is a prefix of the key value that is associated with the given index node. - View Dependent Claims (18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32)
-
-
33. A computer-accessible storage medium storing instructions, wherein the instructions are executable to:
-
store, within a given one of a plurality of keymap instances, keymap entries corresponding respectively to a plurality of data objects, wherein each of said plurality of data objects corresponds to one or more replicas, wherein each of said one or more replicas is accessible via a unique respective locator value, and wherein a given one of said keymap entries corresponding to a given one of said plurality of data objects indicates a mapping from a given key value corresponding to said given data object to each said respective locator value of said one or more replicas of said given data object; replicate said keymap entries across said plurality of keymap instances; index stored keymap entries of said given keymap instance within an unbalanced index data structure; and select a different one of said plurality of keymap instances at regular or irregular intervals and at least partially synchronize said index data structure of said given keymap instance with an index data structure of said different keymap instance; wherein said index data structure includes a plurality of index nodes arranged hierarchically and each index node having an associated tag value, wherein for each of said stored keymap entries, there exists a respective, uniquely corresponding one of said index nodes such that at most one keymap entry corresponds to any given one of said index nodes; and wherein for each given one of the index nodes, each tag value associated with each ancestor of said given index node is a prefix of the key value that is associated with the given index node. - View Dependent Claims (34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48)
-
-
49. A computer-implemented keymap instance, comprising:
-
a plurality of host computers configured to store keymap entries corresponding respectively to a plurality of data objects, wherein each of said plurality of data objects corresponds to one or more replicas, wherein each of said one or more replicas is accessible via a unique respective locator value, wherein a given one of said keymap entries corresponding to a given one of said plurality of data objects indicates a mapping from a given key value corresponding to said given data object to each said respective locator value of said one or more replicas of said given data object, and wherein said host computers are further configured to store a plurality of replicas of said given keymap entry in a distributed fashion among said host computers, each host computer of the host computers comprising a processor and a memory; a computer-implemented keymap coordinator configured to index stored keymap entries of said host computers within an unbalanced index data structure; wherein said keymap coordinator is configured to select a different keymap instance at regular or irregular intervals and to at least partially synchronize said unbalanced index data structure with an index data structure of said different keymap instance; wherein said index data structure includes a plurality of index nodes arranged hierarchically and each index node having an associated tag value, wherein for each of said stored keymap entries, there exists a respective, uniquely corresponding single one of said index nodes such that at most one keymap entry corresponds to any given one of said index nodes; and wherein for each given one of the index nodes, each tag value associated with each ancestor of said given index node is a prefix of the key value that is associated with the given index node.
-
Specification