Data processing unit with key value store
A key-value store supporting GET, PUT and DELETE operations, serializes multiple clients using two locks, and that supports asynchronous resizing. The locking scheme includes an operation of holding two locks, one for the key involved in the operation, one for the page currently searched or updated. The store can either be a single volume holding keys and data or can be organized as a directory volume referencing a number of data volumes organized by data-size ranges. The scheme also supports asynchronous resizing of the directory while continuing to perform operations.
1. A method for storage of data, the method comprising:
in response to a request to perform an operation on data associated with a key:
obtaining a lock on the key;
determining, based on a hash of the key, a page associated with the key, wherein:
the page associated with the key is in a set of one or more pages stored in a volume, and
each respective page of the one or more pages stores a respective part of an array of slots;
after obtaining the lock on the key, obtaining a lock on the page associated with the key; and
after obtaining the lock on the page associated with the key:
determining a slot associated with the key, wherein the part of the array of slots stored by the page associated with the key contains the slot associated with the key or contains second keys used to determine the slot associated with the key;
using the slot associated with the key to perform the operation on the data associated with the key, wherein the operation is a get operation, a put operation, or a delete operation; and
releasing the lock on the page associated with the key and the lock on the key.
2. The method of claim 1 , wherein the method further comprises:
updating a parameter to indicate a second size of the array of slots greater than the first size of the array of slots; and
for each respective page of the set of one or more pages:
obtaining a lock on the respective page;
after obtaining the lock on the respective page:
for each respective slot in the part of the array of slots stored in the respective page:
in response to determining that a second key is stored in the respective slot, determining, based on a hash of the second key stored in the respective slot and the second size of the array of slots, a destination page in the set of pages; and
based on the destination page being different from the respective page:
releasing the lock on the respective page; and
after releasing the lock on the respective page, moving data in the respective slot from the respective page to a slot in the part of the array stored in the destination page.
3. The method of claim 2 , wherein moving the data in the respective slot comprises:
obtaining a lock on the second key stored in the respective slot;
determining whether the second key is still stored in the respective slot; and
based on the second key still being stored in the respective slot:
performing the put operation to store the data in the respective slot at the slot in the part of the array stored in the destination page; and
performing the delete operation with respect to the respective slot; and
releasing the lock on the second key stored in the respective slot.
4. The method of claim 1 , wherein:
the operation is the get operation, and
using the slot associated with the key to perform the operation on the data associated with the key comprises:
determining, based on value data stored in the slot associated with the key, the data associated with the key; and
returning the data associated with the key.
5. The method of claim 4 , wherein the page associated with the key is a first page in the set of pages, and determining the slot associated with the key comprises:
checking slots in the first page for a slot that stores the key; and
based on none of the checked slots in the first page storing the key:
obtaining a lock on a second, different page in the set of pages;
checking one or more slots in the second page for a slot that stores the key;
determining that a slot in the second page that stores the key is the slot associated with the key; and
after returning the data associated with the key, releasing the lock on the second page,
wherein the lock on the first page is released in response to determining that none of the checked slots in the first page stores the key.
6. The method of claim 1 , wherein the operation is the put operation and using the slot associated with the key to perform the operation on the data associated with the key comprises:
storing value data in the slot associated with the key, the value data stored in the slot associated with the key being based on the data associated with the key.
7. The method of claim 6 , wherein the page associated with the key is a first page in the set of pages, and determining the slot associated with the key comprises:
checking slots in the first page for an unused slot; and
based on none of the checked slots in the first page being an unused slot:
obtaining a lock on a second, different page in the set of pages;
checking one or more slots in the second page in the set of pages for an unused slot;
determining that the unused slot in the second page is the slot associated with the key; and
after storing the value data in the slot associated with the key, releasing the lock on the second page,
wherein the lock on the first page is released in response to determining that none of the checked slots in the first page stores the key.
8. The method of claim 1 , wherein:
the volume is a directory volume that comprises the page associated with the key,
the operation is the get operation, and
using the slot associated with the key comprises:
reading an address stored in the slot associated with the key;
using the address to determine a storage location in a second volume;
determining, based on value data stored in the storage location, the data associated with the key; and
returning the data associated with the key.
9. The method of claim 1 ,
wherein the volume is a directory volume that comprises the page associated with the key, and
wherein using the slot associated with the key comprises:
in response to determining that the operation is the put operation, determining a size value based on the data associated with the key;
allocating a block in a second volume such that a size of the block is greater than or equal to the determined size value;
storing, in the slot associated with the key, an address of the block and a value indicating the size of the block; and
storing, in the block, value data based on the data associated with the key.
10. The method of claim 9 , wherein:
a third volume comprises a plurality of stacks, each respective stack of the plurality of stacks corresponding to a respective range of sizes, and
allocating the block comprises:
determining, based on the size value, an appropriate stack from among the plurality of stacks;
popping block data off the appropriate stack; and
determining, based on the block data, the address of the block and the size of the block.
11. The method of claim 10 , wherein:
each respective stack of the plurality of stacks has a respective predetermined minimum size value,
allocating the block further comprises based on the block data specifying a size that is greater than a fitted size by at least the minimum size value for the appropriate stack, pushing second space data onto the appropriate stack, the second space data specifying a start of an unused portion of the block and a size of the unused portion of the block, the fitted size being the size value rounded up to a next multiple of the minimum size value for the appropriate stack greater than the size value, and
determining the size of the block comprises determining that the size of the block is the size specified by the block data minus the size of the unused portion of the block.
12. The method of claim 10 , wherein:
the block data is first block data, and
the method further comprises, in response to a request to perform the delete operation on the data associated with the key, pushing second space data onto the appropriate stack, the second space data specifying the address of the block and the size of the block.
13. The method of claim 12 , wherein a cost of the delete operation is 1 atomic write to the appropriate stack and 1 atomic write to a super block of the appropriate stack to update a stack pointer of the appropriate stack.
14. The method of claim 1 , wherein the array of slots has a first size and the method further comprises:
updating a parameter to indicate a second size of the array of slots greater than the first size of the array of slots; and
for each respective page of the set of one or more pages, performing a resize operation for the respective page, wherein performing the resize operation for the respective page comprises, for each respective slot in the part of the array of slots stored in the respective page:
in response to determining that a key is stored in the respective slot, determining, based on a hash of the key stored in the respective slot and the second size of the array of slots, a destination page in the set of pages; and
based on the destination page being different from the respective page, moving data in the respective slot from the respective page to a slot in the part of the array stored in the destination page.
15. The method of claim 14 , wherein moving the data in the respective slot comprises:
obtaining a lock on the key stored in the respective slot;
storing the data in the respective slot at the slot in the part of the array stored in the destination page;
deleting the data in the respective slot; and
releasing the lock on the key stored in the respective slot.
16. The method of claim 14 , further comprising:
prior to performing a resize operation for a last page of the set of pages, performing a get, put, or delete operation on data in the array of slots.
17. A computing system comprising:
a storage device; and
one or more processors configured to:
in response to a request to perform an operation on data associated with a key:
obtain a lock on the key;
determine, based on a hash of the key, a page associated with the key, wherein:
the page associated with the key is in a set of one or more pages stored in a volume stored in the storage device, and
each respective page of the one or more pages stores a respective part of an array of slots;
after obtaining the lock on the key, obtain a lock on the page associated with the key; and
after obtaining the lock on the page associated with the key:
determine a slot associated with the key, wherein the part of the array of slots stored by the page associated with the key contains the slot associated with the key or contains second keys used to determine the slot associated with the key;
use the slot associated with the key to perform the operation on the data associated with the key, wherein the operation is a get operation, a put operation, or a delete operation; and
release the lock on the page associated with the key and the lock on the key.
18. The computing system of claim 17 , wherein the one or more processors are further configured to:
update a parameter to indicate a second size of the array of slots greater than the first size of the array of slots; and
for each respective page of the set of one or more pages:
obtain a lock on the respective page;
after obtaining the lock on the respective page:
for each respective slot in the part of the array of slots stored in the respective page:
in response to determining that a second key is stored in the respective slot, determine, based on a hash of the second key stored in the respective slot and the second size of the array of slots, a destination page in the set of pages; and
based on the destination page being different from the respective page:
release the lock on the respective page; and
after releasing the lock on the respective page, move data in the respective slot from the respective page to a slot in the part of the array stored in the destination page.
19. The computing system of claim 18 , wherein the one or more processors are configured such that, as part of moving the data in the respective slot, the one or more processors:
obtain a lock on the second key stored in the respective slot;
determine whether the second key is still stored in the respective slot; and
based on the second key still being stored in the respective slot:
perform the put operation to store the data in the respective slot at the slot in the part of the array stored in the destination page; and
perform the delete operation with respect to the respective slot; and
release the lock on the second key stored in the respective slot.
20. The computing system of claim 18 ,
the operation is the get operation, and
the one or more processors are configured such that, as part of using the slot associated with the key to perform the operation on the data associated with the key, the one or more processors:
determine, based on value data stored in the slot associated with the key, the data associated with the key; and
return the data associated with the key.
21. The computing system of claim 18 , wherein the operation is the put operation and the one or more processors are configured such that, as part of using the slot associated with the key to perform the operation on the data associated with the key, the one or more processors:
store value data in the slot associated with the key, the value data stored in the slot associated with the key being based on the data associated with the key.
22. The computing system of claim 18 , wherein:
a first volume is a directory volume that comprises the page associated with the key,
the operation is the get operation, and
the one or more processors are configured such that, as part of using the slot associated with the key, the one or more processors:
read an address stored in the slot associated with the key;
use the address to determine a storage location in a second volume;
determine, based on value data stored in the storage location, the data associated with the key; and
return the data associated with the key.
23. The computing system of claim 18 , wherein:
a first volume is a directory volume that comprises the page associated with the key,
the operation is the put operation, and
the one or more processors are configured such that, as part of using the slot associated with the key, the one or more processors:
determine a size value based on the data associated with the key;
allocate a block in a second volume such that a size of the block is greater than or equal to the determined size value;
store, in the slot associated with the key, an address of the block and a value indicating the size of the block; and
store, in the block, value data based on the data associated with the key.
24. The computing system of claim 18 , wherein the array of slots has a first size and the one or more processors are further configured to:
update a parameter to indicate a second size of the array of slots greater than the first size of the array of slots; and
for each respective page of the set of one or more pages, perform a resize operation for the respective page, wherein the one or more processors are configured such that, as part of performing the resize operation for the respective page, the one or more processors, for each respective slot in the part of the array of slots stored in the respective page:
in response to determining that a key is stored in the respective slot, determine, based on a hash of the key stored in the respective slot and the second size of the array of slots, a destination page in the set of pages; and
based on the destination page being different from the respective page, move data in the respective slot from the respective page to a slot in the part of the array stored in the destination page.
25. A computer-readable storage medium comprising instructions for execution by a programmable processor, wherein execution of the instructions by the programmable processor causes the programmable processor to:
in response to a request to perform an operation on data associated with a key:
obtain a lock on the key;
determine, based on a hash of the key, a page associated with the key, wherein:
the page associated with the key is in a set of one or more pages stored in a volume, and
each respective page of the one or more pages stores a respective part of
an array of slots;
after obtaining the lock on the key, obtain a lock on the page associated with the key; and
after obtaining the lock on the page associated with the key:
determine a slot associated with the key, wherein the part of the array of slots stored by the page associated with the key contains the slot associated with the key or contains second keys used to determine the slot associated with the key;
use the slot associated with the key to perform the operation on the data associated with the key, wherein the operation is a get operation, a put operation, or a delete operation; and
release the lock on the page associated with the key and the lock on the key.