RDMA-enabled key-value store

Abstract

According to one or more embodiments, lookup, insertion, and deletion operations are allowed to continue during actions required for collision remediation. When relocation operations are used to resolve a collision, information encoded in header portions of the hash table entries that store the key-value pairs indicates when the associated key-value pairs are undergoing relocation. This information facilitates continued access to the RKVS during the relocation process by allowing other processes that access the RKVS to handle relocations without failure. Furthermore, when hash table expansion is needed in order to resolve a collision, a second, larger, hash table is allocated, and lookup operations continue on both the old hash table and the new hash table. One or more embodiments further prevent insertion, lookup, and deletion failures in the RKVS using flags, encoded in header information in hash table entries, that reflect the state of the respective key-value pairs in the store.

What is claimed is: 
     
       1. A computer-executed method comprising:
 a first process performing a first sub-operation of a particular key-value pair operation by:
 sending a remote direct memory access (RDMA) request to obtain header information from a particular entry, for a particular key-value pair, in a hash table in volatile memory of a computing device, 
 wherein the header information comprises a set of flags that comprises one or more of:
 an allocd flag that indicates whether the particular entry is occupied, 
 an influx flag that indicates whether an incomplete write operation, to the particular entry, is in process, 
 a time flag that indicates whether data in the particular entry is undergoing migration, and 
 a fence flag that indicates whether a second process, other than the first process, has priority for inserting the particular key-value pair into the hash table, 
 
 determining that one or more flags, of the set of flags, are set; and 
 
 based on the first sub-operation of the particular key-value pair operation determining that the one or more flags of the particular key-value pair are set, the first process aborting a second sub-operation of the particular key-value pair operation; 
 wherein the method is performed by one or more computing devices. 
 
     
     
       2. The method of  claim 1 , wherein:
 the particular key-value pair includes a particular value; 
 the particular key-value pair operation is a lookup operation to retrieve the particular value from the particular entry of the hash table; 
 the one or more flags comprise the time flag; and 
 the method further comprises, after aborting the second sub-operation of the particular key-value pair operation and after a pre-determined amount of time subsequent to said determining that the one or more flags are set, the first process performing a second lookup operation to retrieve the particular value. 
 
     
     
       3. The method of  claim 2 , wherein the first process performs the second lookup operation to retrieve the particular value from the hash table. 
     
     
       4. The method of  claim 2 , wherein:
 the hash table (a) is a first hash table, and (b) implements a key-value store; 
 the method further comprises determining that the key-value store is being migrated from the first hash table to a second hash table; 
 the first process performs the second lookup operation to retrieve the particular value over both the first hash table and the second hash table based, at least in part, on said determining that the key-value store is being migrated from the first hash table to the second hash table. 
 
     
     
       5. The method of  claim 1 , wherein:
 the particular key-value pair operation is an insertion operation to insert the particular key-value pair into the particular entry of the hash table; 
 the one or more flags comprises the fence flag; 
 the method further comprises, after aborting the second sub-operation of the particular key-value pair operation, sending a second RDMA request to unset one or more flag bits in the header information of the particular entry. 
 
     
     
       6. The method of  claim 1 , wherein:
 the particular key-value pair includes a particular value; 
 the particular key-value pair operation is a lookup operation to retrieve the particular value from the particular entry of the hash table; 
 the one or more flags comprises the influx flag; 
 the method further comprises, after aborting the second sub-operation of the particular key-value pair operation and after a pre-determined amount of time subsequent to said determining that the one or more flags are set, the first process performing a second lookup operation to retrieve the particular value. 
 
     
     
       7. The method of  claim 1 , wherein:
 the RDMA request is a compare and swap (CAS)-type RDMA request; 
 the CAS-type RDMA request compares the header information, from the particular entry, to target header information in which one or more unset flag bits correspond to the one or more flags; 
 said determining that the one or more flags, of the set of flags, are set comprises: the CAS-type RDMA request returning information indicating that the header information, from the particular entry, does not match the target header information. 
 
     
     
       8. A computer-executed method for migrating at least a portion of a key-value store from a first hash table in volatile memory to a second hash table in the volatile memory comprising:
 sending one or more messages to one or more clients that are configured to access the key-value store at the first hash table using RDMA requests, wherein the one or more messages comprise information identifying the second hash table; 
 relocating a plurality of key-value pairs, in the key-value store, from the first hash table to the second hash table; 
 while relocating the plurality of key-value pairs from the first hash table to the second hash table, maintaining both the first hash table and the second hash table; 
 while both the first hash table and the second hash table are being maintained, servicing:
 one or more first RDMA requests, from the one or more clients, for the first hash table, and 
 one or more second RDMA requests, from the one or more clients, for the second hash table; and 
 
 after relocating the plurality of key-value pairs from the first hash table to the second hash table, deallocating the first hash table; 
 wherein the method is performed by one or more computing devices. 
 
     
     
       9. The method of  claim 8 , wherein relocating the plurality of key-value pairs from the first hash table to the second hash table comprises relocating a particular key-value pair, of the plurality of key-value pairs, from a first entry of the first hash table to a second entry of the second hash table by:
 setting a time flag in header information for the first entry of the first hash table; and 
 after said setting the time flag, writing information for the particular key-value pair to the second entry of the second hash table. 
 
     
     
       10. The method of  claim 8 , further comprising, during said relocating the plurality of key-value pairs, a particular client, of the one or more clients, the method further comprises performing a lookup operation for a particular key-value pair, of the plurality of key-value pairs, from the key-value store, at least in part, by sending a first RDMA request, of the one or more first RDMA requests, to the first hash table and sending a second RDMA request, of the one or more second RDMA requests, to the second hash table. 
     
     
       11. The method of  claim 8 , further comprising, during said relocating the plurality of key-value pairs, a particular client, of the one or more clients, performing an insertion operation to insert a particular key-value pair, of the plurality of key-value pairs, into the key-value store, at least in part, by sending a third RDMA request to write information for the particular key-value pair to the second hash table. 
     
     
       12. One or more non-transitory computer-readable media storing one or more sequences of instructions that, when executed by one or more processors, cause:
 a first process performing a first sub-operation of a particular key-value pair operation by:
 sending a remote direct memory access (RDMA) request to obtain header information from a particular entry, for a particular key-value pair, in a hash table in volatile memory of a computing device, 
 wherein the header information comprises a set of flags that comprises one or more of:
 an allocd flag that indicates whether the particular entry is occupied, 
 an influx flag that indicates whether an incomplete write operation, to the particular entry, is in process, 
 a time flag that indicates whether data in the particular entry is undergoing migration, and 
 a fence flag that indicates whether a second process, other than the first process, has priority for inserting the particular key-value pair into the hash table, 
 
 determining that one or more flags, of the set of flags, are set; and 
 
 based on the first sub-operation of the particular key-value pair operation determining that the one or more flags of the particular key-value pair are set, the first process aborting a second sub-operation of the particular key-value pair operation. 
 
     
     
       13. The one or more non-transitory computer-readable media of  claim 12 , wherein:
 the particular key-value pair includes a particular value; 
 the particular key-value pair operation is a lookup operation to retrieve the particular value from the particular entry of the hash table; 
 the one or more flags comprise the time flag; and 
 the one or more sequences of instructions further comprise instructions that, when executed by the one or more processors, cause, after aborting the second sub-operation of the particular key-value pair operation and after a pre-determined amount of time subsequent to said determining that the one or more flags are set, the first process performing a second lookup operation to retrieve the particular value. 
 
     
     
       14. The one or more non-transitory computer-readable media of  claim 13 , wherein the first process performs the second lookup operation to retrieve the particular value from the hash table. 
     
     
       15. The one or more non-transitory computer-readable media of  claim 13 , wherein:
 the hash table (a) is a first hash table, and (b) implements a key-value store; 
 the one or more sequences of instructions further comprise instructions that, when executed by the one or more processors, cause determining that the key-value store is being migrated from the first hash table to a second hash table; 
 the first process performs the second lookup operation to retrieve the particular value over both the first hash table and the second hash table based, at least in part, on said determining that the key-value store is being migrated from the first hash table to the second hash table. 
 
     
     
       16. The one or more non-transitory computer-readable media of  claim 12 , wherein:
 the particular key-value pair operation is an insertion operation to insert the particular key-value pair into the particular entry of the hash table; 
 the one or more flags comprises the fence flag; 
 the one or more sequences of instructions further comprise instructions that, when executed by the one or more processors, cause, after aborting the second sub-operation of the particular key-value pair operation, sending a second RDMA request to unset one or more flag bits in the header information of the particular entry. 
 
     
     
       17. The one or more non-transitory computer-readable media of  claim 12 , wherein:
 the particular key-value pair includes a particular value; 
 the particular key-value pair operation is a lookup operation to retrieve the particular value from the particular entry of the hash table; 
 the one or more flags comprises the influx flag; 
 the one or more sequences of instructions further comprise instructions that, when executed by the one or more processors, cause, after aborting the second sub-operation of the particular key-value pair operation and after a pre-determined amount of time subsequent to said determining that the one or more flags are set, the first process performing a second lookup operation to retrieve the particular value. 
 
     
     
       18. The one or more non-transitory computer-readable media of  claim 12 , wherein:
 the RDMA request is a compare and swap (CAS)-type RDMA request; 
 the CAS-type RDMA request compares the header information, from the particular entry, to target header information in which one or more unset flag bits correspond to the one or more flags; 
 said determining that the one or more flags, of the set of flags, are set comprises: the CAS-type RDMA request returning information indicating that the header information, from the particular entry, does not match the target header information. 
 
     
     
       19. One or more non-transitory computer-readable media storing instructions that, when executed by one or more processors, cause:
 sending one or more messages to one or more clients that are configured to access a key-value store at a first hash table in volatile memory using RDMA requests, wherein the one or more messages comprise information identifying a second hash table in the volatile memory; 
 relocating a plurality of key-value pairs, in the key-value store, from the first hash table to the second hash table; 
 while relocating the plurality of key-value pairs from the first hash table to the second hash table, maintaining both the first hash table and the second hash table; 
 while both the first hash table and the second hash table are being maintained, servicing:
 one or more first RDMA requests, from the one or more clients, for the first hash table, and 
 one or more second RDMA requests, from the one or more clients, for the second hash table; and 
 
 after relocating the plurality of key-value pairs from the first hash table to the second hash table, deallocating the first hash table. 
 
     
     
       20. The one or more non-transitory computer-readable media of  claim 19 , wherein relocating the plurality of key-value pairs from the first hash table to the second hash table comprises relocating a particular key-value pair, of the plurality of key-value pairs, from a first entry of the first hash table to a second entry of the second hash table by:
 setting a time flag in header information for the first entry of the first hash table; and 
 after said setting the time flag, writing information for the particular key-value pair to the second entry of the second hash table. 
 
     
     
       21. The one or more non-transitory computer-readable media of  claim 19 , wherein, the instructions include a set of instructions that, when executed by the one or more processors, causes, during said relocating the plurality of key-value pairs, a particular client, of the one or more clients, performing a lookup operation for a particular key-value pair, of the plurality of key-value pairs, from the key-value store, at least in part, by sending a first RDMA request, of the one or more first RDMA requests, to the first hash table and sending a second RDMA request, of the one or more second RDMA requests, to the second hash table. 
     
     
       22. The one or more non-transitory computer-readable media of  claim 19 , wherein, the instructions include a set of instructions that, when executed by the one or more processors, causes, during said relocating the plurality of key-value pairs, a particular client, of the one or more clients, performing an insertion operation to insert a particular key-value pair, of the plurality of key-value pairs, into the key-value store, at least in part, by sending third RDMA request to write information for the particular key-value pair to the second hash table.