Keymap service architecture for a distributed storage system

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.

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.

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.