Network key value indexing design
Provided is a method of indexing in a network key value indexing system. The method includes retrieving a first key name from a storage device of the network key value indexing system, the first key name identifying a first prefix, a first bucket, and a first key, the first prefix indicating the first bucket, parsing the first key name into the first prefix, the first bucket, and the first key, determining the first prefix, the first bucket, and the first key based on a first delimiter, and generating a hash table in a memory cache of the network key value indexing system to associate the first prefix with the first key.
1 . A method of indexing, the method comprising:
retrieving, by a key-value-indexing system, a first key name from a storage device of the key-value-indexing system, the first key name comprising:
a first part of the first key name indicating where first data is stored, wherein the first part of the first key name comprises a prefix; and
a first key associated with the first data, such that a hash of the first part of the first key name returns the first key; and
in response to a system crash or power-cycle, generating, by a processing circuit, a data structure in a cache of the key-value-indexing system based on:
the first part of the first key name; and
the first key.
2 . The method of claim 1 , further comprising:
retrieving, by the key-value-indexing system, a second key name from the storage device, the second key name comprising:
the first part of the first key name;
a second part of the second key name indicating where second data is stored; and
a second key; and
associating the second part of the second key name with the second key.
3 . The method of claim 1 , further comprising:
retrieving, by the key-value-indexing system, a third key name from the storage device, the third key name comprising:
the first part of the first key name; and
a third key; and
associating the first part of the first key name with the third key.
4 . The method of claim 1 , wherein:
the first part of the first key name is separated from the first key by a delimiter in the first key name;
the key-value-indexing system comprises a network key-value-indexing system;
the data structure comprises a hash table; and
the cache comprises volatile memory.
5 . The method of claim 1 , further comprising searching, by the key-value-indexing system, for keys and buckets associated with the first part of the first key name in association with a performance of O(N), N being a number of the keys and the buckets associated with the first part of the first key name.
6 . The method of claim 1 , further comprising repeating the retrieving and the generating during a startup of the key-value-indexing system in response to a system crash or a power-cycle.
7 . The method of claim 1 , wherein:
the first key has a non-hierarchical data structure;
the storage device comprises one or more storage device buckets; and
the retrieving the first key name comprises:
applying an iterator to one of the one or more storage device buckets based on an iterator prefix; and
retrieving the first key name iterated by the iterator from the one of the one or more storage device buckets.
8 . A non-transitory computer readable medium implemented on a system for indexing, the non-transitory computer readable medium having computer code that implements a method of indexing, the method comprising:
retrieving, by a processing circuit of a key-value-indexing system, a first key name from a storage device, the first key name comprising:
a first part of the first key name indicating where first data is stored, wherein the first part of the first key name comprises a prefix; and
a first key associated with the first data, such that a hash of the first part of the first key name returns the first key; and
generating, by the processing circuit, a data structure in a cache based on:
the first part of the first key name; and
the first key.
9 . The non-transitory computer readable medium of claim 8 , wherein the computer code further implements the method of indexing by:
retrieving, by the processing circuit, a second key name from the storage device, the second key name comprising:
a second part of the second key name indicating where second data is stored; and
a second key; and
associating the second part of the second key name with the second key.
10 . The non-transitory computer readable medium of claim 8 , wherein the computer code further implements the method of indexing by:
retrieving, by the processing circuit, a third key name from the storage device, the third key name comprising:
the first part of the first key name; and
a third key; and
associating the first part of the first key name with the third key.
11 . The non-transitory computer readable medium of claim 8 , wherein:
the key-value-indexing system comprises a network key-value-indexing system;
the data structure comprises a hash table; and
the cache comprises volatile memory.
12 . The non-transitory computer readable medium of claim 8 , wherein the computer code further implements the method of indexing by searching, by the processing circuit, for keys and buckets associated with the first part of the first key name in association with a performance of O(N), N being a number of the keys and the buckets associated with the first part of the first key name.
13 . The non-transitory computer readable medium of claim 8 , wherein the computer code further implements the method of indexing by repeating the retrieving and the generating in response to a system crash or a power-cycle.
14 . The non-transitory computer readable medium of claim 8 , wherein:
the storage device comprises one or more storage device buckets of locations where data is stored; and
the computer code implements the retrieving the first key name by:
applying an iterator to one of the one or more storage device buckets based on an iterator prefix; and
retrieving the first key name iterated by the iterator from the one of the one or more storage device buckets.
15 . A system for indexing, the system comprising a storage device, a processing circuit, and a cache, wherein the processing circuit is configured to:
retrieve a first key name from the storage device, the first key name comprising:
a first part of the first key name indicating where first data is stored, wherein the first part of the first key name comprises a prefix; and
a first key associated with the first data, such that a hash of the first part of the first key name returns the first key; and
generate a data structure in the cache based on:
the first part of the first key name; and
the first key.
16 . The system of claim 15 , wherein the processing circuit is further configured to:
retrieve a second key name from the storage device, the second key name comprising:
the first part of the first key name;
a second part of the second key name indicating where second data is stored; and
a second key; and
associate the second part of the second key name with the second key.
17 . The system of claim 15 , wherein the processing circuit is further configured to:
retrieve a third key name from the storage device, the third key name comprising:
the first part of the first key name; and
a third key; and
associate the first part of the first key name with the third key.
18 . The system of claim 15 , wherein:
the data structure comprises a hash table; and
the cache comprises volatile memory.
19 . The system of claim 15 , wherein the processing circuit is further configured to search for keys and buckets associated with the first part of the first key name in association with a performance of O(N), N being a number of the keys and the buckets associated with the first part of the first key name.
20 . The system of claim 15 , wherein the processing circuit is further configured to repeat retrieving the first key name and generating the data structure in response to a system crash or a power-cycle.