Organization and management of key-value stores
Organization and management of key-value stores is described. An example method includes providing a stack of tables. Each of the tables includes a set of pages of a pre-determined size for storing a set of key-value entries. The method includes monotonically decreasing a number of pages in the tables according to a position of the table in the stack. The method includes configuring each of the pages in the tables to address a particular range of a key space in such a way that each of the pages in a subsequent table in the stack is configured to address a range addressed by at least two pages in a preceding table in the stack. An action with a key-value entry is carried out by starting with a table in the top of the stack and moving to the next table if the action cannot be carried out.
1. A computer-implemented method for organization and management of a key-value store, the method comprising:
providing a stack of tables, wherein each table includes a set of pages of a pre-determined size, wherein each of the pages is configured to store a set of key-value entries, and each of the key-value entries includes a key and a value;
monotonically decreasing a number of pages in the tables according to a position of the table in the stack; and
configuring each of the pages in the tables to address a particular range of a key space, wherein each of the pages in a subsequent table in the stack is configured to address a key space range addressed by at least two pages in a preceding table in the stack.
2. The method of claim 1 , wherein the key space includes a uniform distribution.
3. The method of claim 1 , wherein the number of pages in the subsequent table in the stack is a fraction of the number of pages in the previous table in the stack.
4. The method of claim 1 , further comprising:
receiving a request for an action with a particular key-value entry; and
performing, from a top of the stack, for a particular table in the stack, the following operations:
determining, based on a key associated with the particular key-value entry, a particular page in the particular table, the particular page addressing a particular range in the key space, the particular range including a key associated with the particular key-value entry;
determining whether the action can be carried out using the particular page;
if the action can be carried out, performing the action on the particular key-value entry using the particular page; and
if the action cannot be carried out, shifting to a table subsequent the particular table in the stack to repeat the operations.
5. The method of claim 4 , wherein:
the action includes an addition of the particular key-value entry; and
the determining that the action can be carried out includes determining that the particular page includes room for the addition.
6. The method of claim 4 , wherein:
the action includes at least one of reading, modifying, and deleting of the particular key-value entry; and
the determining that the action can be carried out includes determining that the particular page holds the particular key-value entry.
7. The method of claim 6 , wherein the determining that the particular page holds the particular key-value entry includes using a per page based Bloom filter for the particular key-value entry.
8. The method of claim 4 , wherein the determining that the particular page is in the particular table includes using a per table based Bloom filter for the particular key-value entry.
9. The method of claim 1 , further comprising:
providing a RAM table for storing recently used key-value entries, the RAM table including cache pages, each of the cache pages being configured to address a cache range of key space, the cache range being addressed by at least two pages from a first table in the stack;
placing the RAM table at a top of the stack;
determining full pages in the RAM table; and
in response to the determination, flushing key-values entries from the full pages to the tables in the stack.
10. The method of claim 9 , wherein the RAM table is located in a random-access memory and each of the tables in the stack is located on at least one of a solid-state disk, flash memory, or hard-disk drive.
11. A system for organization and management of a key-value store, the system comprising:
at least one processor; and
a memory communicatively coupled to the at least one processor, the memory storing instructions, which, when executed by the at least one processor, perform a method comprising:
providing a stack of tables, wherein each of the tables includes a set of pages of a pre-determined size, wherein each of the pages is configured to store a set of key-value entries and each of the key-value entries includes a key and a value;
monotonically decreasing a number of pages in the tables according to a position of the table in the stack; and
configuring each of the pages in the tables to address a particular range of a key space, wherein each of the pages in a subsequent table in the stack is configured to address a key space range addressed by at least two pages in a preceding table in the stack.
12. The system of claim 11 , wherein the key space has a uniform distribution.
13. The system of claim 11 , wherein the number of pages in the subsequent table in the stack is a fraction of the number of pages in the previous table in the stack.
14. The system of claim 11 , wherein the method further comprises:
receiving a request for an action with a particular key-value entry; and
performing, from a top of the stack, for a particular table in the stack, the following operations:
determining, based on a key associated with the particular key-value entry, a particular page in the particular table, the particular page addressing a particular range in the key space, the particular range including a key associated with the particular key-value entry;
determining whether the action can be carried out using the particular page;
if the action can be carried out, performing the action on the particular key-value entry using the particular page; and
if the action cannot be carried out, shifting to a table subsequent the particular table in the stack to repeat the operations.
15. The system of claim 14 , wherein:
the action includes an addition of the particular key-value entry; and
the determining that the action can be carried out includes determining that the particular page includes room for the addition.
16. The system of claim 14 , wherein:
the action includes at least one of reading, modifying, and deleting of the particular key-value entry; and
the determining that the action can be carried out includes determining that the particular page holds the particular key-value entry.
17. The system of claim 16 , wherein the determining that the particular page holds the particular key-value entry includes using a per page based Bloom filter for the particular key-value entry.
18. The system of claim 14 , wherein the determining that the particular page is in the particular table includes using a per table based Bloom filter for the particular key-value entry.
19. The system of claim 11 , wherein the method further comprises:
providing a RAM table for storing recently used key-value entries, the RAM table including cache pages, each of the cache pages being configured to address a cache range of key space, the cache range being addressed by at least two pages from a first table in the stack;
placing the RAM table at a top of the stack;
determining full pages in the RAM table; and
in response to the determination, flushing key-values entries from the full pages to the tables in the stack.
20. A non-transitory computer-readable storage medium having embodied thereon instructions, which, when executed by one or more processors, perform a method comprising:
providing a stack of tables, wherein each of the table includes a set of pages of a pre-determined size, wherein each of the pages is configured to store a set of key-value entries and each of the key-value entries includes a key and a value;
monotonically decreasing a number of pages in the tables according to a position of the table in the stack; and
configuring each of the pages in the tables to address a particular range of a key space, wherein each of the pages in a subsequent table in the stack is configured to address a key space range addressed by at least two pages in a preceding table in the stack.