Compare and swap functionality for key-value and object stores

Patent metadata

Field	Value
Publication number	US-10929203-B2
Application number	US-201916248989-A
Country	US
Kind code	B2
Filing date	Jan 16, 2019
Priority date	Jan 16, 2019
Publication date	Feb 23, 2021
Grant date	Feb 23, 2021

Abstract

Embodiments for providing compare and swap (CAS) functionality to key value storage to allow multi-threaded applications to share storage devices and synchronize multiple concurrent threads or processes. A key-value application programming interface (API) is modified to include a CAS API in addition to the standard Put and Get APIs. The CAS function uses a key, expected old value, and new value to compare and swap an existing key value only if its current value equals the expected old value. Hash values of the key value and expected old value may be used by the CAS function to improve performance and reduce bandwidth.

First claim

What is claimed is:

1. A computer-implemented method of accessing a key-value storage using a compare and swap (CAS) process, comprising:
providing a key-value metadata element comprising key, a corresponding value, and associated metadata;
providing a PUT function to put data into the key and value;
providing a GET function to get a value stored for the key;
providing a CAS application program interface (API) to access a plurality of compare and swap (CAS) functions on the key for an expected old value and a new value, and return either a success or miscompare result, wherein the plurality of CAS functions comprise a first CAS function that compares the key with the expected old value, a second CAS function that compares the key with a hash of the expected old value, and a third CAS function wherein the CAS API accepts the hash of the expected old value as the key value pair for the compare;
selecting a CAS function from the plurality of CAS functions based on hash function, hash sizes, and value size thresholds; and
performing the selected CAS function on the key value element using the CAS API by a multi-threaded application comprising multiple processes that require synchronization to access data in the key-value storage.

2. The method of claim 1 wherein the selected CAS function:
performs the compare; and
modifies, if they are the same, the contents of the memory location to the new value, by replacing an existing value of the memory location for the key with the new value and returning a success parameter; and
returns, if they are different, a miscompare parameter signifying a failed comparison.

3. The method of claim 2 further comprising:
using a write-lock on the key to obtain atomicity of the multiple processes; and
using a concurrent set command or another compare and swap function for the same key to wait until the write-lock for the key is released.

4. The method of claim 2 wherein the second CAS function compares a hash of the value of the key with a hash of the expected old value, wherein the hash of the value of the key is saved in one of: the key-value pair in another key or in the metadata of the key-value metadata element.

5. The method of claim 4 wherein the hash is generated by a hash function comprising one of: a fingerprint hash and a cryptographic hash.

6. The method of claim 4 wherein the third CAS function is selected to save bandwidth for keys with large values.

7. The method of claim 1 wherein the selected CAS function uses parameters for a selected hash function, hash size, and value size threshold, and wherein the parameters are set by a user based on requirements of the multi-threaded application.

8. A system comprising:
a server computer;
a key value storage device coupled to the server computer and storing a plurality of key-value databases;
one or more multi-threaded application components coupled to the key value storage device, wherein a PUT function puts data into the key and value, and a GET function gets a value stored for the key; and
a Compare and Swap (CAS) processing component associated with the key-value storage device to allow multi-threading application components to share the storage resources of the key value storage device, wherein the CAS processing component
provides a CAS application program interface (API) to access a plurality of compare and swap (CAS) operations on the key for an expected old value and a new value, and return either a success or miscompare result, wherein the plurality of CAS operations comprise a first CAS operation that compares the key with the expected old value, a second CAS operation that compares the key with a hash of the expected old value, and a third CAS operation wherein the CAS API accepts the hash of the expected old value as the key value pair for the compare,
selects a CAS operation from the plurality of CAS operations based on hash function, hash sizes, and value size thresholds, and
performs the selected CAS operation on the key value element using the CAS API by a multi-threaded application comprising multiple processes that require synchronization to access data in the key-value storage.

9. The system of claim 8 wherein the multi-threaded application components execute at least one multi-threaded application comprising a plurality of program processes executed concurrently and that need synchronization to ensure proper operation.

10. The system of claim 9 wherein the multi-threaded application requires test-and-set routines and incrementors to maintain the synchronicity.

11. The system of claim 9 further comprising:
a key-value metadata element comprising the key, a corresponding value, and associated metadata; and
an application program interface (API) layer providing a PUT API, GET API, and the CAS API to perform the selected CAS operation on the key for an expected old value and a new value, and return either a success or miscompare result.

12. The system of claim 11 wherein the first CAS operation:
compares an existing value of the key with the expected old value; and
modifies, if they are the same, the contents of the memory location to the new value, by replacing an existing value of the memory location for the key with the new value and returning a success parameter; and
returns, if they are different, a miscompare parameter signifying a failed comparison.

13. The system of claim 12 wherein, for the second CAS operation, the hash of the value of the key is saved in one of: the key-value pair in another key or in the metadata of the key-value metadata element, and wherein the hash is generated by a hash function comprising one of: a fingerprint hash and a cryptographic hash.

14. The system of claim 13 wherein the third CAS operation is selected to save bandwidth for keys with large values.

15. The system of claim 8 wherein the storage device comprises an object storage that manages data as objects, and wherein each object includes the data, an amount of metadata, and a globally unique identifier.

16. A computer-implemented method of accessing a key-value storage using a compare and swap (CAS) process, comprising:
reading a key memory location of the key-value storage;
remembering a previous value of the key memory location;
computing, based on the previous value, a new value;
selecting the selected CAS operation from a plurality of CAS operations based on hash function, hash sizes, and value size thresholds, wherein a first CAS operation compares the key with an expected old value, a second CAS operation that compares the key with a hash of the expected old value, and a third CAS operation wherein a CAS API accessing the plurality of CAS operations accepts the hash of the expected old value as the key value pair for the compare,
attempting to swap in the new value using a selected CAS function, where a comparison step of the selected CAS function checks for the key memory location still being equal to the previous value; and
repeating, if the selected CAS function indicates that the attempting step has failed, the reading and computing steps by re-reading the key memory location, re-computing a subsequent new value, and performing the selected CAS function for the subsequent new value.

17. The method of claim 16 further comprising:
compares an existing value of the key with an expected old value;
modifying, if they are the same, the contents of the memory location to the new value, by replacing an existing value of the memory location for the key with the new value and returning a success parameter; and
returning, if they are d

Assignees

• Emc Ip Holding Co Llc

Inventors

• Wolfson Kfir
• Shemer Udi
• Natanzon Assaf

Classifications

• G06F2205/00

  Indexing scheme relating to group G06F5/00; Methods or arrangements for data conversion without changing the order or content of the data handled · CPC title

• G06F2209/52

  Indexing scheme relating to G06F9/52 · CPC title

• G06F9/54 Primary

  Interprogram communication · CPC title

• G06F9/52 Primary

  Program synchronisation; Mutual exclusion, e.g. by means of semaphores · CPC title

• G06F2209/521

  Atomic · CPC title