Claims:1. A processor implemented method, comprising:
receiving in a Field-Programmable Gate Array (FPGA) system, an input from a user, wherein the input comprises at least a command and an incoming key (202);
calculating, using a checksum technique, ‘n’ bit hash value for the incoming key and writing the calculated ‘n’ bit hash value and the input into an internal queue (204); and
performing a key operation based on the command by reading the calculated ‘n’ bit hash value and the input, wherein the key operation comprises one of a search key operation, an insert key operation, or a delete key operation (206),
wherein the search key operation comprises:
comparing in parallel, the incoming key with one or more keys stored in a hash bucket identified based on the calculated ‘n’ bit hash value to obtain a matched key (206a), wherein the identified hash bucket is searched in at least one of an on-chip memory, and an off-chip memory of the FPGA system (206a); and
retrieving and providing corresponding associated data based on a data pointer stored which points to a first data segment stored in a linked list format that is mapped to the matched key (206b), wherein the data pointer is stored in a corresponding data pointer bucket,
wherein the insert key operation comprises:
determining a validity of a hash bucket pointer pointed by the calculated ‘n’ bit hash value (206c); and
based on the determined validity, performing one of (206d):
(i) dynamically allocating, for the incoming key and associated data, a new hash bucket and a data pointer bucket that has capacity of storing one or more keys; or
(ii) inserting the incoming key and associated data in an allocated key hash bucket and a data pointer bucket respectively and incrementing a key count, wherein the allocated key hash bucket is searched in parallel and selected for allocation from one or more hash buckets groups based on an availability status, and
wherein the delete key operation comprises:
comparing in parallel, the incoming key with one or more keys stored in a specific hash bucket identified based on the calculated ‘n’ bit hash value to obtain a matched key (206e);
deleting the matched key from the specific hash bucket and de-allocating one or more data segments allocated for the matched key (206f); and
refraining from forming a memory hole by shifting remaining keys from the one or more keys stored in the specific hash bucket to a corresponding new position in at least one direction, after (i) the matched key being deleted and (ii) the one or more data segments being de-allocated (206g).

2. The processor implemented method of claim 1, wherein the step of performing the insert key operation is preceded by determining whether the incoming key to be inserted in the allocated hash bucket results in the key count exceeding a hash bucket capacity.

3. The processor implemented method of claim 2, wherein when the key count exceeds the hash bucket capacity, the method further comprises:
allocating another new hash bucket from an unallocated hash bucket pool and transferring (i) the incoming key and (ii) remaining previously inserted keys from the allocated hash bucket into the another new hash bucket, wherein the another new hash bucket is identified and allocated by obtaining a hash bucket of higher capacity than capacity of the allocated hash bucket, wherein if the hash bucket of higher capacity is unavailable, a hash bucket having lower capacity is obtained and allocated from the unallocated hash bucket pool, wherein the hash bucket having lower capacity is linked to the allocated hash bucket to form a linked list of hash buckets until an exhaustion of hash buckets from the on-chip memory of the FPGA system, and wherein upon exhaustion of the hash buckets from the on-chip memory of the FPGA system, a hash bucket is obtained from an unallocated hash bucket pool comprised in the off-chip memory of the FPGA system; and
returning the corresponding allocated hash bucket to the unallocated hash bucket pool.

4. The processor implemented method of claim 1, further comprising: upon deleting the matched key from the specific hash bucket specific:
dynamically determining, a replacement requirement of the specific hash bucket based on at least one of number of remaining keys ; and
transferring, based on the replacement requirement, at least one of the number of remaining keys and associated data pointers to a hash bucket and a data pointer bucket respectively.

5. The processor implemented method of claim 1, wherein the one or more data segments are de-allocated by identifying (i) a data pointer at an index from a corresponding data pointer bucket of the specific hash bucket specific to the matched key and (ii) one or more corresponding data segments specific to the identified data pointer, and wherein the index indicates the matched key of the specific hash bucket.

6. The processor implemented method of claim 1, wherein the hash bucket is allocated from one or more hash bucket groups that are configurable based on design of a FPGA system, each of the one or more hash bucket groups comprising one of more key hash buckets, and wherein capacity of the one or more key hash buckets is configurable based on design of a FPGA system, and number of each of the one of more key hash buckets to be comprised in each of the one or more hash bucket groups is configurable by the user.

7. The processor implemented method of claim 1, wherein the associated data is a fixed length data or a variable length data.

8. A Field Programmable Gate Array system (100), comprising:
a memory (102) comprising at least one of an on-chip memory and an off-chip memory;
input/output interfaces (106); and
a hardware processor (104) coupled to the memory (102) via the one or more communication interfaces (106), wherein the hardware processor (104) are configured to:
receive, an input from a user, wherein the comprises at least a command and an incoming key;
calculate, using a checksum technique, ‘n’ bit hash value for the incoming key and writing the calculated ‘n’ bit hash value and the input into an internal queue; and
perform a key operation based on the command by reading the calculated ‘n’ bit hash value and the input, wherein the key operation comprises one of a search key operation, an insert key operation, or a delete key operation,
wherein the search key operation comprises:
comparing in parallel, the incoming key with one or more keys stored in a hash bucket identified based on the calculated ‘n’ bit hash value to obtain a matched key, wherein the identified hash bucket is searched in at least one of the on-chip memory, and the off-chip memory of the FPGA system; and
retrieving and providing corresponding associated data based on a data pointer which points to a first data segment stored in a linked list format that is mapped to the matched key, wherein the data pointer is stored in a corresponding data pointer bucket,
wherein the insert key operation comprises:
determining a validity of a hash bucket pointer pointed by the calculated ‘n’ bit hash value; and
based on the determined validity, performing one of:
(i) dynamically allocating, for the incoming key and associated data, a new hash bucket and a data pointer bucket that has capacity of storing one or more keys; or
(ii) inserting the incoming key and associated data in an allocated key hash bucket and a data pointer bucket respectively and incrementing a key count, wherein the allocated key hash bucket is searched in parallel and selected for allocation from one or more hash buckets groups based on an availability status, and
wherein the delete key operation comprises:
comparing in parallel, the incoming key with one or more keys stored in a specific hash bucket pointed by the calculated ‘n’ bit hash value to obtain a matched key;
deleting the matched key from the specific hash bucket and de-allocating one or more data segments allocated for the matched key; and
refraining from forming a memory hole by shifting remaining keys from the one or more keys stored in the specific hash bucket to a corresponding new position in at least one direction, after (i) the matched key being deleted and (ii) the one or more data segments being de-allocated.

9. The FPGA system of claim 8, wherein the hardware processor is further configured to determine, prior to performing the insert key operation, whether the incoming key to be inserted in the allocated hash bucket results in the key count exceeding a hash bucket capacity.

10. The FPGA system of claim 9, wherein when the key count exceeds the hash bucket capacity, the hardware processor is further configured to:
allocate another new hash bucket from an unallocated hash bucket pool and transferring (i) the incoming key and (ii) remaining previously inserted keys from the allocated hash bucket into the another new hash bucket, wherein the another new hash bucket is identified and allocated by obtaining a hash bucket of higher capacity than capacity of the allocated hash bucket, wherein if the hash bucket of higher capacity is unavailable, a hash bucket having lower capacity is obtained and allocated from the unallocated hash bucket pool, wherein the hash bucket having lower capacity is linked to the allocated hash bucket to form a linked list of hash buckets until an exhaustion of hash buckets from the on-chip memory of the FPGA system, and wherein upon exhaustion of the hash buckets from the on-chip memory of the FPGA system, a hash bucket is obtained from an unallocated hash bucket pool comprised in the off-chip memory of the FPGA system; and
return the allocated hash bucket to the unallocated hash bucket pool.

11. The FPGA system of claim 8, wherein upon deleting the matched key from the specific hash bucket, the hardware processor is further configured to:
dynamically determine, a replacement requirement of the specific hash bucket based on at least one of number of remaining keys; and
transfer, based on the replacement requirement, remaining keys and associated data pointers to a hash bucket and a data pointer bucket respectively

12. The FPGA system of claim 8, wherein the one or more data segments are de-allocated by identifying (i) a data pointer at an index from a corresponding data pointer bucket group of the specific hash bucket specific to the matched key and (ii) one or more corresponding data segments specific to the identified data pointer, and wherein the index indicates the matched key of the specific hash bucket.

13. The FPGA system of claim 8, wherein the hash bucket is allocated from one or more hash bucket groups that are configurable based on design of a FPGA system, each of the one or more hash bucket groups comprising one of more key hash buckets, and wherein capacity of the one or more key hash buckets is configurable based on design of a FPGA system and number of each of the one of more key hash buckets to be comprised in each of the one or more hash bucket groups is configurable by the user.

14. The FPGA system of claim 8, wherein the associated data is a fixed length data or a variable length data.
, Description:FORM 2

THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENT RULES, 2003

COMPLETE SPECIFICATION
(See Section 10 and Rule 13)

Title of invention:

SYSTEMS AND METHODS FOR PERFORMING KEY-VALUE STORE OPERATIONS IN FPGA

Applicant

Tata Consultancy Services Limited
A company Incorporated in India under the Companies Act, 1956
Having address:
Nirmal Building, 9th floor,
Nariman point, Mumbai 400021,
Maharashtra, India

The following specification particularly describes the invention and the manner in which it is to be performed.

TECHNICAL FIELD
[001] The disclosure herein generally relates to database management systems, and, more particularly, to systems and methods for performing key-value store operations in FPGA.

BACKGROUND
[002] A key–value database, or key–value store, is a data storage paradigm designed for storing, retrieving, and managing associative arrays, a data structure more commonly known today as a dictionary or hash. Key-value stores are probably the simplest form of database management systems. In a typical conventional key-value store system, keys are stored in either in linked list format or in a contiguous manner. However, when a search is performed in the linked list, though memory is optimized this is likely to involve more time for retrieval as the system has to sequentially search each key and compare. Similarly, when the search is performed for keys that are stored in the contiguous manner in a fixed size bucket, the search may be faster but the memory may not be conserved. Further, when specific key operations are performed (say delete operations) by conventional systems and methods for updating data structure for key-value stores, memory holes are formed. Such memory holes formation may add to latency during subsequent key operations. As a result, the systems may be inefficient in terms of processing key operations and thus lead to high latency. It is therefore important to ensure that such key-value store operations are performed accurately and efficiently without a trade-off in processing time, and memory consumption.

SUMMARY
[003] Embodiments of the present disclosure present technological improvements as solutions to one or more of the above-mentioned technical problems recognized by the inventors in conventional systems. For example, in one aspect, there is provided a processor implemented method for performing key-value store operations in a Field-Programmable Gate Array (FPGA) system. The processor implemented method comprises receiving in the Field-Programmable Gate Array (FPGA) system, an input from a user, wherein the input comprises at least a command and an incoming key; calculating, using a checksum technique, ‘n’ bit hash value for the incoming key and writing the calculated ‘n’ bit hash value and the input into an internal queue; and performing a key operation based on the command by reading the calculated ‘n’ bit hash value and the input, wherein the key operation comprises one of a search key operation, an insert key operation or a delete key operation.
[004] In an embodiment, the search key operation comprises: comparing in parallel, the incoming key with one or more keys stored in a hash bucket identified based on the calculated ‘n’ bit hash value to obtain a matched key (206a), wherein the identified hash bucket is searched in at least one of an on-chip memory and an off-chip memory of the FPGA system. Corresponding associated data is retrieved and provided based on a data pointer which points to a first data segment stored in a linked list format that is mapped to the matched key, wherein the data pointer is stored in a corresponding data pointer bucket.
[005] In an embodiment, the insert key operation comprises: determining a validity of a hash bucket pointer pointed by the calculated ‘n’ bit hash value; and based on the determined validity, performing one of: (i) dynamically allocating, for the incoming key and associated data, a new hash bucket that has capacity of storing one or more keys; (ii) inserting the incoming key and associated data in an allocated key hash bucket and a data pointer bucket respectively and incrementing a key count, wherein the allocated key hash bucket is searched in parallel and selected for allocation from one or more hash buckets groups based on an availability status.
[006] In an embodiment, the step of performing the insert key operation is preceded by determining whether the incoming key to be inserted in the allocated hash bucket results in the key count exceeding a hash bucket capacity. When the key count exceeds the hash bucket capacity, the method further comprises: allocating another new hash bucket from an unallocated hash bucket pool and transferring (i) the incoming key and (ii) remaining previously inserted keys from the allocated hash bucket into the another new hash bucket, wherein the another new hash bucket is identified and allocated by obtaining a hash bucket of higher capacity than capacity of the allocated hash bucket, wherein if the hash bucket of higher capacity is unavailable, a hash bucket having lower capacity is obtained and allocated from the unallocated hash bucket pool, wherein the hash bucket having lower capacity is linked to the allocated hash bucket to form a linked list of hash buckets until an exhaustion of hash buckets from the on-chip memory of the FPGA system, and wherein upon exhaustion of the hash buckets from the on-chip memory of the FPGA system, a hash bucket is obtained from an unallocated hash bucket pool comprised in the off-chip memory of the FPGA system; and returning the corresponding allocated hash bucket to the unallocated hash bucket pool.
[007] In an embodiment, the delete key operation comprises: comparing in parallel, the incoming key with one or more keys stored in a specific hash bucket identified based on the calculated ‘n’ bit hash value to obtain a matched key; deleting the matched key from the specific hash bucket and de-allocating one or more data segments allocated for the matched key; and refraining from forming a memory hole by shifting, remaining keys from the one or more keys stored in the specific hash bucket, to a corresponding new position in at least one direction, after (i) the matched key being deleted and (ii) the one or more data segments being de-allocated. In an embodiment, the one or more data segments are de-allocated by identifying (i) a data pointer at an index from a corresponding data pointer bucket of the specific hash bucket specific to the matched key and (ii) one or more corresponding data segments specific to the identified data pointer. In an embodiment, the index indicates the matched key in the specific hash bucket.
[008] In an embodiment, upon deleting the matched key from the specific hash bucket specific, the method comprises dynamically determining, a replacement requirement of the specific hash bucket based on at least one of number of remaining keys stored in the specific hash bucket; and transferring, based on the replacement requirement, at least one of the number of remaining keys, and associated data pointers to a hash bucket and a data pointer bucket respectively.
[009] In an embodiment, the hash bucket is allocated from one or more hash bucket groups that are configurable based on design of a FPGA system, each of the one or more hash bucket groups comprising one or more key hash buckets. In another embodiment, capacity of the one or more key hash buckets is configurable based on design of a FPGA system and number of each of the one or more key hash buckets to be comprised in each of the one or more hash bucket groups is configurable by the user. In an embodiment, the associated data is a fixed length data or a variable length data.
[010] In other aspect, there is provided a Field-Programmable Gate Array (FPGA) system for performing key-value store operations. The system 100 comprises a memory comprising at least one of an on-chip memory and an off-chip memory; input/output interfaces; and a hardware processor coupled to the memory via the I/O interfaces. The hardware processor is configured to: receive, an input from a user, wherein the input comprises at least a command and an incoming key; calculate, using a checksum technique, ‘n’ bit hash value for the incoming key and writing the calculated ‘n’ bit hash value and the input into an internal queue; and perform a operation based on the command by reading the calculated ‘n’ bit hash value and the input, wherein the key operation comprises one of a search key operation, an insert key operation, or a delete key operation.
[011] In an embodiment, the insert key operation comprises: determining a validity of a hash bucket pointer pointed by the calculated ‘n’ bit hash value; and based on the determined validity, performing one of: (i) dynamically allocating, for the incoming key and associated data, a new hash bucket that has capacity of storing one or more keys; (ii) inserting the incoming key and associated data in an allocated key hash bucket and a data pointer bucket respectively and incrementing a key count, wherein the allocated key hash bucket is searched in parallel and selected for allocation from one or more hash buckets groups based on an availability status.
[012] In an embodiment, the step of performing the insert key operation is preceded by determining whether the incoming key to be inserted in the allocated hash bucket results in the key count exceeding a hash bucket capacity. When the key count exceeds the hash bucket capacity, the method further comprises: allocating another new hash bucket from an unallocated hash bucket pool and transferring (i) the incoming key and (ii) remaining previously inserted keys from the allocated hash bucket into the another new hash bucket, wherein the another new hash bucket is identified and allocated by obtaining a hash bucket of higher capacity than capacity of the allocated hash bucket, wherein if the hash bucket of higher capacity is unavailable, a hash bucket having lower capacity is obtained and allocated from the unallocated hash bucket pool, wherein the hash bucket having lower capacity is linked to the allocated hash bucket to form a linked list of hash buckets until an exhaustion of hash buckets from the on-chip memory of the FPGA system, and wherein upon exhaustion of the hash buckets from the on-chip memory of the FPGA system, a hash bucket is obtained from an unallocated hash bucket pool comprised contained in the off-chip memory of the FPGA system; and returning the corresponding allocated hash bucket to the unallocated hash bucket pool.
[013] In an embodiment, the delete key operation comprises: comparing in parallel, the incoming key with one or more keys stored in a specific hash bucket identified based on the calculated ‘n’ bit hash value to obtain a matched key; deleting the matched key from the specific hash bucket and de-allocating one or more data segments allocated for the matched key; and refraining from forming one or more memory holes by shifting, remaining keys from the one or more keys stored in the specific hash bucket, in at least one direction, after (i) the matched key being deleted and (ii) the one or more data segments being de-allocated. In an embodiment, the one or more data segments are de-allocated by identifying (i) a data pointer at an index from a corresponding data pointer bucket of the specific hash bucket specific to the matched key and (ii) one or more corresponding data segments specific to the identified data pointer. In an embodiment, the index indicates the matched key of the specific hash bucket.
[014] In an embodiment, upon deleting the matched key from the specific hash bucket specific, the hardware processor is configured to dynamically determine, a replacement requirement of the specific hash bucket based on at least one of number of remaining keys being stored in the specific hash bucket; and transfer, based on the replacement requirement, at least one of the number of remaining keys and associated data pointers to a hash bucket and a data pointer bucket respectively.
[015] In an embodiment, the hash bucket is allocated from one or more hash bucket groups that are configurable based on design of a FPGA system, each of the one or more hash bucket groups comprising one of more key hash buckets. In another embodiment, capacity of the one or more key hash buckets is configurable based on design of a FPGA system, and number of each of the one or more key hash buckets to be comprised in each of the one or more hash bucket groups is configurable by the user. In an embodiment, the associated data is a fixed length data or a variable length data.
[016] It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory only and are not restrictive of the invention, as claimed.

BRIEF DESCRIPTION OF THE DRAWINGS

[017] The accompanying drawings, which are incorporated in and constitute a part of this disclosure, illustrate exemplary embodiments and, together with the description, serve to explain the disclosed principles:
[018] FIG. 1 illustrates an exemplary block diagram of a system for performing key-value store operations in a Field Programmable Gate Array (FPGA) in accordance with an embodiment of the present disclosure.
[019] FIGS. 2A through 2D illustrate an exemplary flow diagram illustrating a method for performing key-value store operations in the FPGA using the system of FIG. 1 according to an embodiment of the present disclosure.
[020] FIG. 3 is an exemplary block diagram of a key-value Store architecture according to an embodiment of the present disclosure.
[021] FIG. 4 illustrates an exemplary data segment descriptor and data segment memory according to an embodiment of the present disclosure.
[022] FIG. 5A depict a traditional key-value store architecture according to an example embodiment of the present disclosure.
[023] FIG. 5B depict an exemplary key-value store architecture proposed by the system of FIG. 1 according to an example embodiment of the present disclosure.
[024] FIG. 6 depicts format of bucket capacities and bucket groups according an example embodiment of the present disclosure.
[025] FIG. 7 depicts key bucket memory with bucket groups according to an embodiment of the present disclosure.
[026] FIG. 8 depicts bucket descriptor data structure according to an embodiment of the present disclosure.

DETAILED DESCRIPTION OF EMBODIMENTS
[027] Exemplary embodiments are described with reference to the accompanying drawings. In the figures, the left-most digit(s) of a reference number identifies the figure in which the reference number first appears. Wherever convenient, the same reference numbers are used throughout the drawings to refer to the same or like parts. While examples and features of disclosed principles are described herein, modifications, adaptations and other implementations are possible without departing from the spirit and scope of the disclosed embodiments. It is intended that the following detailed description be considered as exemplary only, with the true scope and spirit being indicated by the following claims.
[028] Referring now to the drawings, and more particularly to FIGS. 1 through 8, where similar reference characters denote corresponding features consistently throughout the figures, there are shown preferred embodiments and these embodiments are described in the context of the following exemplary system and/or method.
[029] FIG. 1 illustrates an exemplary block diagram of a system 100 for performing key-value store operations in a Field Programmable Gate Array (FPGA) in accordance with an embodiment of the present disclosure. In an embodiment, the system 100 may also be referred as ‘a Field Programmable Gate Array system’ or ‘a key-value store (KVS) system’, a KVS architecture or a FPGA based KVS system, and interchangeably used hereinafter. In an embodiment, the system 100 includes one or more processors 104, and input/output (I/O) interface(s) 106, and one or more data storage devices or memory 102 operatively coupled to the hardware processor 104. The memory 102 comprises a database 108. The hardware processor 104 can be implemented as state machine, control logic circuitries etc. The system 100 can be implemented in FPGA and used in an Add-On board in a computing system such as Personal Computer, workstation, and the like, etc.
[030] The I/O interface 106 (all I/O interfaces) except configuration interface are functionally similar to queues following First-In-First-Out (FIFO) protocol. The configuration I/O interface follows APB, AXI lite protocol or similar protocol giving access of the KVS control/status registers to a microprocessor system. The memory 102 may include any computer-readable medium known in the art including, for example, volatile memory, such as Static Random Access Memory (SRAM) and Dynamic Random Access Memory (DRAM). The database 108 may store information pertaining to inputs (e.g., one or more commands, keys, operation information) obtained from user(s). Further, stores information pertaining to inputs fed to the system 100 and/or outputs generated by the system (e.g., at each stage), specific to the methodology described herein.
[031] FIGS. 2A through 2D, with reference to FIG. 1, illustrate an exemplary flow diagram illustrating a method for performing key-value store operations in a Field Programmable Gate Array (FPGA) using the system 100 of FIG. 1 according to an embodiment of the present disclosure. In an embodiment, the system 100 comprises one or more data storage devices or the memory 102 operatively coupled to the hardware processor 104 which are implemented as state machines or control logic. The memory of the FPGA system 100 comprises at least one of an on-chip memory and an off-chip memory. The steps of the method of the present disclosure will now be explained with reference to the components of the system 100 as depicted in FIG. 1, and the flow diagram of FIG. 2. In an embodiment of the present disclosure, at step 202, the hardware processor 104 receives an input from a user. In an embodiment, the input comprises a command, an incoming key and optionally data. In an embodiment of the present disclosure, at step 204, the hardware processor 104 calculates, using a checksum technique, ‘n’ bit hash value for the incoming key and writes the calculated ‘n’ bit hash value and the input into an internal queue. In an example embodiment, ‘n’ defines the length of the incoming key. In an embodiment of the present disclosure, at step 206, the hardware processor 104 performs a key operation based on the command by reading the calculated ‘n’ bit hash value and the incoming key. In an embodiment, the key operation comprises one of a search key operation, an insert key operation or a delete key operation. In case when the command is an insert command, the input comprises the insert command, a corresponding key for insertion in a key hash bucket, and associated data to be stored in a data hash bucket.
[032] In an embodiment, the search key operation comprises: comparing in parallel (at step 206a depicted in FIG. 2B), the incoming key with one or more keys stored in a hash bucket that is identified based on the calculated ‘n’ bit hash value to obtain a matched key (206a); and retrieving and providing corresponding associated data based on a data pointer stored in a corresponding data pointer bucket which points to a first data segment stored in a linked list format, that is mapped to the matched key (at step 206b depicted in FIG. 2B). In an embodiment, the data pointed is at the same index in the corresponding data pointer bucket as the matched key in the identified hash bucket. The identified hash bucket is searched in at least one of the on-chip memory, and the off-chip memory comprised in the FPGA system 100. In an embodiment, data pointer buckets store data pointer(s) that point to corresponding data segments stored in the linked list format. In case there is no matched key found, the system 100 provides and returns a message (e.g., an error message) that key is not found. In an embodiment of the present disclosure, expression ‘hash bucket’ refers to ‘key hash bucket’ and may be interchangeably used hereinafter. Below is an illustrative search key operation implemented by the embodiments of the present disclosure provided by way of example:
[033] Consider the scenario where following pair is to be inserted:
<1, A>, <11, B>, <21, C>, <31, D>, <41, E>
[034] Also assume for simplicity that all the keys give the hashed value of 1 after hash calculation.
[035] Assume that the system 100 has to search for key-value 1. The following steps are performed by the proposed method of the present disclosure.
1. Compute a hash value. In this case it is 1
2. Go to location pointer_array[1] and retrieve the entire type 8 bucket.
3. Compare all the keys (say 5 keys are currently stored). The comparison of the incoming key is done in parallel with the 5 keys to obtain a matched key.
4. Data corresponding to key 1 (i.e., A) is read and returned to the user.
[036] Analysis: Only 1 bucket is to be retrieved from memory, which takes 1 clock cycle approximately.
[037] Since there were 5 keys stored, the system 100 performs 5 comparisons in parallel in the FPGA. This will take 1 clock cycle. Therefore the search is completed in 2 clock cycles.
[038] On the contrary, in traditional (or conventional) key-value store approaches, hash table is an array of pointers where each pointer points to a linked list of keys corresponding to every hash value (colliding keys).
[039] Assume that traditional system has to search for key-value 41. In a typical traditional system search is performed as per below example:
1. Compute the hash value, which in this case is 1
2. Go to location pointer_array[1] and go to the first node attached to the pointer array. In this case it is <1, A>.
3. Compare <1, A> to the incoming key 1. Result: It does not match.
4. Traverse the linked list and compare the key 1 with 11, 21, 31 and then finally 41.
5. Read the data corresponding to key 41 (i.e., E) and return it to the user.
[040] As can be seen, 5 nodes are to be retrieved from the memory one-by-one and compared. Assuming that the traditional approach takes 1 clock cycle for each retrieval and 1 clock cycle comparison, the system in total takes 10 clock cycles for completing the search. This results in additional computation, more processing speed and time.
[041] Considering another example, wherein assuming that a key 171 has to be searched. Assume that the system already has <1, A>, <11, B>, <21, C>, <31, D>, <41, E>, <51, F>, <61, G>, <71, H>, <81, I>, <91, J>, <101, K>, <111, L>, <121, M>, <131, N>, <141, O>, <151, P>, <161, Q>, <171, R>, <181, S>, <191, T> as the inserted key-values.
[042] In the present disclosure, a first hash bucket is retrieved and a search on all 16 keys is performed in parallel in this first hash bucket. In case the search does not result in a matching key, then a second hash bucket is retrieved and a parallel search is performed on all keys (says 4 keys are already stored) wherein a matched key is obtained. Therefore, only 2 buckets are to be retrieved from memory (e.g., say on-chip memory). This takes 2 clock cycles. As can be seen from above operation, there will be two comparisons (e.g., 16 and 2 comparisons) to be made which can be done in parallel since its FPGA. This will take 1 clock cycle each. Thus for first bucket, it will be: 1 + 1 and for second bucket it will be: 1 + 1. Total 4 cycles are taken for search operation performed by the embodiments of the present disclosure.
[043] On the contrary, in traditional systems/approaches wherein it is assumed that traditional system has to search for a key 171, linked list is traversed one by one till node having value <171, R> is reached. Here a match is obtained and R as the result of search is returned. Therefore, in traditional systems 18 nodes are to be retrieved from the memory one-by-one and compared. Assuming that it takes 1 clock cycle for each retrieval and 1 clock cycle comparison, traditional system/approach would take 36 clock cycles in total for completing the search. When this traditional approach is compared with the present disclosure, it is evident that processing time and speed is reduced in the present disclosure (18 in traditional versus 4 in the present disclosure) for applications where search occurs very frequently (e.g., say when search is carried out in a trading system). For instance, when users submit trading requests to the trading system’s front end layer, the layer performs range validations and functional validations. Functional validations consist of performing searches based on different parameters such as an Identifier (e.g., say ID) of the user or social security number of the user or some string based search. These integer values or strings are used as keys and search returns different data pertaining to specific user.
[044] In an embodiment of the present disclosure, the hardware processor 104 performs an insert key operation by executing steps 206c and 206d comprising: determining at step 206c as depicted in FIG. 2C, by the hardware processor 104, a validity of a hash bucket pointer pointed by the calculated ‘n’ bit hash value; and based on the determined validity, performing, at step 206d depicted in FIG. 2C, by the hardware processor 104, one of: (i) dynamically allocating, for the incoming key and associated data, a new hash bucket that has capacity of storing one or more keys; or (ii) inserting the incoming key and associated data in an allocated key hash bucket and a data pointer bucket respectively and incrementing a key count, wherein the allocated key hash bucket is searched in parallel and selected for allocation from one or more hash buckets groups based on an availability status. In an example embodiment, if the bucket pointer pointed to by hash value is not valid (which means this is the first key hashed to the bucket), it allocates a news hash bucket with capacity of 1 key or more keys based on availability. If a hash bucket is already allocated, key is stored in an identified hash bucket and key count is incremented by one.
[045] Below is an illustrative insert key operation implemented by the embodiments of the present disclosure provided by way of example:
[046] In the present disclosure, a count has to be stored for the number of keys that are hashed to a particular hash_value. Thus pointer_array has a key_count, a bucket_type and a bucket_pointer as fields. Additionally a data structure referred as bucket is present that stores a set of keys in it. The bucket may have (or store) 1, 4, 8 or 16 keys in it which are categorized as type_1_bucket, type_4_bucket, type_8_bucket and type_16_bucket. Following steps are performed by the embodiments of the present disclosure for insert key operation.
1. For the first key-value pair <1, A>, search for a free type_1_bucket (or an unallocated type_1_bucket). Get the offset and bucket_no of the bucket from free pool.
2. Assuming a type_1_bucket is available, the system 100 populates the type_1_bucket with <1, A> as the values.
3. Go to pointer_array[hash_value] and set the key_count to 1 and bucket_pointer to point to the type_1_bucket populated in step 2 above. Thus the data structure appears as below:
pointer_array[hash_value](bucket_type = 1)(count=1) => [<1, A>]
4. Read the next incoming key-value pair (<11, B>). Compute the hash value for 11 which will be 1 as per assumption made by the present disclosure.
5. Go to pointer_array[hash_value] and check the key count and type. In this case, the count will be 1 and bucket_type will be 1. So when a new key-value has to be inserted, the system 100 finds that it has already exhausted the full capacity of type_1_bucket and thus would require a type_4_bucket.
6. A type_4_bucket is retrieved from one or more hash buckets in free pool in FPGA.
7. Copy <1, A> and <11, B> (which is the incoming key-value pair) to type_4_bucket retrieved in step 6.
8. Release the type_1_bucket to free pool of buckets. Thus the data structure is provided by way of example below:
pointer_array[hash_value](bucket_type = 4)(count=2) => [<1,A>,<11,B>]
9. Similarly, for incoming key-value pairs the data structure will be manipulated and it will evolve as below
pointer_array[hash_value](bucket_type = 4)(count=3) => [<1, A>, <11, B>, <21, C>]
pointer_array[hash_value](bucket_type = 4)(count=4) => [<1, A>, <11, B>, <21, C>, <31, D>]
10. Now when a next key-value pair (<41, E>) is attempted for insertion it is found that that the bucket type=4 is fully filled. Hence a bucket of type 8 is retrieved, wherein all the keys are copied to type 8 bucket and the bucket_type and count in pointer_array are set accordingly. The type 4 bucket is further returned to an unallocated bucket pool. Thus the data structure is provided by way of example below:
pointer_array[hash_value](bucket_type = 8)(count=5) => [<1, A>, <11, B>, <21, C>, <31, D>, <41, E>].
[047] Above steps 5, 6, 7 and 8 are better understood by way of following description:
[048] Prior to performing the insert key operation it is determined whether the incoming key to be inserted in the allocated hash bucket results in the key count exceeding a hash bucket capacity (step 5). When the key count exceeds the hash bucket capacity, another new hash bucket from an unallocated hash bucket pool is identified and allocated (step 6). The incoming key and remaining previously inserted keys from the allocated hash bucket are transferred (or copied) into the another new hash bucket (step 7), wherein the another new hash bucket is identified and allocated by obtaining a hash bucket of higher capacity than capacity of the allocated hash bucket, and if the hash bucket of higher capacity is unavailable, a hash bucket having lower capacity is obtained and allocated from the unallocated hash bucket pool, wherein the hash bucket having lower capacity is linked to the allocated hash bucket to form a linked list of hash buckets until an exhaustion of hash bucket(s) from the on-chip memory of the field-programmable gate array (FPGA) system. In an embodiment of the present disclosure, upon exhaustion of the hash buckets from the on-chip memory of the field-programmable gate array (FPGA) system 100, a hash bucket is obtained from an unallocated hash bucket pool comprised in the off-chip memory (or say off-chip memory’s free hash bucket pool) of the FPGA system 100. At step 8, corresponding allocated hash bucket is returned to the unallocated hash bucket pool (step 8).
[049] On the contrary, in traditional (or conventional) key-value insert operation is performed as below:
1. Create a new node with fields and populate it with <1, A>.
2. Go to the location pointer_array[hash_value] and set it to point to node having <1, A>.
i.e., pointer_array[hash_value] = address of <1,A>.
3. Go for the second key-value pair (<11, B>). Create new node and populate it with <11, B>
4. The hash value of this will be the same (as per the assumption). So now go to pointer_array[hash_value] and insert the node at the end of linked list(this could be in the beginning too)
5. Set the next of the newly inserted node to the earlier inserted node. Thus entire data structure with linked list will be as shown below:
Pointer_array[1] => <1, A> => <11, B>
6. In a similar fashion, after inserting all other incoming key-value pairs the linked list constitutes as shown below:
Pointer_array[1] => <1, A> => <11, B> => <21, C> => <31, D> => <41,E>
[050] Below is another illustrative example of insertion key operation for 18 key-value pairs:
[051] Assume that the following 18 key-value pairs into the key-value store needs to be inserted:
<1, A>, <11, B>, <21, C>, <31, D>, <41, E>, <51, F>, <61, G>, <71, H>, <81, I>, <91, J>, <101, K>, <111, L>, <121, M>, <131, N>, <141, O>, <151, P>, <161, Q>, <171, R>
[052] In the present disclosure, the following steps are performed:
[053] The data structure after insertion of 16 keys using the steps in earlier description is shown as below:
pointer_array[hash_value](bucket_type = 16)(count=16) => [<1, A>, <11, B>, <21, C>, <31, D>, <41, E>, <51, F>, <61, G>, <71, H>, <81, I>, <91, J>, <101, K>, <111, L>, <121, M>,<131, N>, <141, O>, <151, P>]
[054] As discussed above, when an insert key operation is performed and if a current bucket (or current hash bucket) cannot hold new key due to lack of space (or space constraint), the system 100 checks whether there is a free bucket of higher size in Block RAM of the FPGA. In case it is not available, then the system checks for bucket of type 1 or 4 or 8 or 16 for availability. If it is available, then this bucket gets linked to the current bucket (which lacked space to store the new key), to form a linked list of hash buckets in the Block RAM. This is done till all the free hash buckets in the Block RAM (on-chip memory) are exhausted. Once the hash buckets in the Block RAM are exhausted, the system 100 initializes data insertion in the DRAM (or the off-chip memory). In other words, when the key count exceeds the hash bucket capacity, another new hash bucket is allocated from an unallocated hash bucket pool and (i) the incoming key and (ii) remaining previously inserted keys from the allocated hash bucket are transferred into the another new hash bucket, wherein the another new hash bucket is identified and allocated by obtaining a hash bucket of higher capacity than capacity of the allocated hash bucket, and if the hash bucket of higher capacity is unavailable, a hash bucket having lower capacity is obtained and allocated from the unallocated hash bucket pool, wherein the hash bucket having lower capacity is linked to the allocated hash bucket to form a linked list of hash buckets until an exhaustion of hash buckets from the on-chip memory of a field-programmable gate array (FPGA) system, and wherein upon exhaustion of the hash buckets from the on-chip memory of the field-programmable gate array (FPGA) system, a hash bucket is obtained from an unallocated hash bucket pool comprised in the off-chip memory of the FPGA system.
[055] When the next key-value pair is to be inserted, i.e., <161, Q>, then another new bucket of type 1 is to be added. Also, bucket type may have values 16 and 1 in it. Data structure is shown as below:
Pointer_array[hash_value](bucket_type = 16, 1)(count = 17) => [<1, A>, <11, B>, <21, C>, <31, D>, <41, E>, <51, F>, <61, G>, <71, H>, <81, I>, <91, J>, <101, K>, <111, L>, <121, M>, <131, N>, <141, O>, <151, P>]=>[<161, Q>]
[056] When the next key-value pair is inserted, i.e., <171, R>, type 1 bucket requires to be freed and type 4 bucket has to be taken up. Data structure is shown as below:
pointer_array[hash_value](bucket_type = 16, 4)(count = 18) => [<1, A>, <11, B>, <21, C>, <31, D>, <41, E>, <51, F>, <61, G>, <71, H>, <81, I>, <91, J>, <101, K>, <111, L>, <121, M>, <131, N>, <141, O>, <151, P>]=>[<161, Q>, <171, R>]
[057] On the contrary, in the traditional systems/approaches, data structures appears as shown in below example:
pointer_array[1] => <1, A> => <11, B>=> <21, C>=> <31, D>=> <41, E>=> <51, F>=> <61, G>=> <71, H>=> <81, I> = > <91, J> => <101, K> => <111, L> => <121, M> => <131, N> => <141, O> => <151, P> => <161, Q> => <171,R>.
[058] In an embodiment of the present disclosure, the delete key operation performed by the hardware processor 104 comprises: comparing in parallel (at step 206e depicted in FIG. 2C), the incoming key with a one or more keys stored in a specific hash bucket pointed by the calculated ‘n’ bit hash value to obtain a matched key; deleting (at step 206f depicted in FIG. 2C) the matched key from the specific hash bucket and de-allocating one or more data segments allocated for the matched key; and refraining (at step 206g depicted in FIG. 2C) from forming one or more memory holes by shifting, remaining keys from the from the one or more keys stored in the specific hash bucket, in at least one direction, after (i) the matched key is being deleted and (ii) the one or more data segments being de-allocated.
[059] Assume that the key 41 is to be deleted from the key-value store.
[060] Following steps are performed by the embodiments of the present disclosure for insert key operation:
1. Compute the hash value of the incoming key. In this case it is 1
2. Go to the pointer_array[hash_value].
3. Retrieve the bucket corresponding to the hash value.
4. Delete the key 41 from the bucket.
5. Compact the keys by shifting all the valid keys either to the right or to the left in the bucket.
[061] Below example illustrates shifting of keys and data pointers:
[062] Assume that there are 7 keys in a 8-key hash bucket has shown below:

[063] Assume that key 3 is deleted. Then a memory hole is created in the above bucket. The bucket looks as below
[064]
[065] In order to avoid or refrain from forming memory holes in between the keys in the above key hash buck, the system 100 performs shifting operation wherein all the keys from key 4 to key 7 are shifted to the left by one. Thus the key hash bucket upon shifting of keys will look as below:

[066] Thus there are no more memory holes in the above key hash bucket and all the empty slots are at the end of the bucket. This prevents the system 100 to perform additional search as the system 100 is aware that the first 6 slots are occupied with keys and the other 2 slots are empty. Therefore during a subsequent insert key operation, if the above hash bucket is identified for inserting an incoming key (a new key), then the system 100 can perform search operation only in the empty slots and not in the first 6 slots which are already occupied with keys.
[067] Timing analysis of delete: It was analyzed by the present disclosure that search of key to be deleted would take 1 clock and shifting of keys takes 1 clock. Therefore 2 clocks for deletion.
[068] On the contrary, in the traditional systems/approaches assume that the key 41 is to be deleted from the key-value store, following steps are typically performed:
1. Compute the hash value of the incoming key. In this case it is 1.
2. Go to the pointer_array[hash_value].
3. Traverse the linked list corresponding to the pointer array till the desired key is found.
4. Delete that particular node by returning it to the free pool of nodes.
[069] Analysis: key 41 is at the end of the linked list. So traditional system/approach takes 1 clock cycle for fetching the node and one clock for comparing the node. It further takes 1 clock to remove the node from the linked list. Thus traditional system takes 10 + 1 clock cycles to perform delete operation.
[070] It is evident from above analysis that the delete key operation in the present disclosure is efficient in terms of computational time, memory consumption and speed (which takes 2 clock cycles) when compared with delete key operation of the traditional system/approaches (which takes 11 clock cycles). So the delete operation is much faster than traditional where it will take 11 clock cycles.
[071] Below is another illustrative example of delete key operation performed by the systems and methods of the present disclosure:
[072] Assume that key 151 is to be deleted
1. Compute the hash value
2. Go to the pointer array location
3. Retrieve the first bucket
4. Search the key 151 in the first bucket (bucket type 16)
5. Delete the key 151
6. Decrement the count in pointer array
[073] On the contrary, in the traditional systems/approaches assume that the key 151 is to be deleted from the key-value store, following steps are typically performed:
1. Compute the hash value (claim 1)
2. Go to the pointer_array location
3. Traverse the linked list one node at a time till key 151 is found
4. Delete the node
5. The new data structure is shown as below:
pointer_array[1] => <1, A> => <11, B> => <21, C> => <31, D> => <41, E> => <51, F> => <61, G> => <71, H> => <81, I> => <91, J> => <101, K> => <111, L> => <121, M> => <131, N> => <141, O> => <161, Q> => <171, R>
[074] In the present disclosure, it is assumed that the data of a corresponding key is of fixed size i.e., say 1 byte for each data (A, B, C, D, etc.). It is to be understood by person having ordinary skill in the art and person skill in the art that the system 100 and the embodiments of the present disclosure can also be implemented with, and is capable of handling, variable length of data by storing a data pointer at each node instead of the actual data. The data pointer will point to a linked list of data segments. For example, assume variable length of data with following key-value pairs and data segments each of size 1.
<1, AA>, <11, BBB>, <21, CCCC>, <31, DDDD>, <41, EEEEE>
[075] Following data structure is obtained using the proposed method of the present disclosure:
pointer_array[hash_value](bucket_type = 4)(count=4) => [<1, ptr1>, <11, ptr2>, <21, ptr3>, <31, ptr4>]
[076] ptr1, ptr2, ptr3, and ptr4 point to data segments pointer as below with the corresponding data:
ptr1 – (A) -> (A)
ptr2 – (B) -> (B) -> (B)
ptr3 – (C) ->(C) -> (C) -> (C)
ptr4 – (D) -> (D) -> (D) -> (D) -> (D)
[077] The above key-value store operations (e.g., search key operation, insert key operation, and the delete key operations) can be implemented (or executed) in at least one of the on-chip memory (Block RAM) and the off-chip memory (DRAM). Therefore, in such scenarios, where the above key-value store operations are executed in the at least one of the Block RAM and the DRAM, the following scenarios may be applicable:
(i) Keys and associated data can be stored in Block RAM only or DRAM only.
(ii) Keys can be stored in Block RAM only wherein the associated data can be stored in DRAM only
(iii) Keys can be stored in DRAM only wherein the associated data can be stored Block RAM only
(iv) Keys and associated data can be stored in DRAM only
(v) Keys and associated data can be stored partially in Block RAM only, whereas remaining portion of associated data can be stored in DRAM only.
[078] Further, the present disclosure describes 1 key hash bucket, 4 key hash bucket, 8 key hash bucket, 16 key hash bucket. It is to be understood by a person having ordinary skill in the art (or skilled in the art) that the system 100 is capable of being configurable to any number of types of buckets and bucket sizes, and the above examples shall not be construed as limiting the scope of the present disclosure. Alternatively, any hash bucket that gets allocated is obtained from one or more hash bucket groups, wherein the hash bucket groups are configurable based on design of the FPGA system 100. In an embodiment, each of the one or more hash bucket groups may comprise one of more key hash buckets, wherein capacity of these hash buckets is configurable based on design of the FPGA system 100. Further number of each of the one or more key hash buckets to be comprised in each of the one or more hash bucket groups is configurable by the user.
[079] FIG. 3, with reference to FIGS. 1 through 2D, is an exemplary block diagram of a key-value store architecture according to an embodiment of the present disclosure. The system 100 receives stream of keys (e.g., say fixed length keys (256 bit) or variable length keys) and commands (e.g., say 2 bit), and optionally data on a FIFO interface. In an embodiment, the system 100 receives variable length data stream corresponding to each key on a 128 bit wide interface. The data interface consists of 128 bit data (wherein width of data may vary depending on incoming requests and design of the FPGA system 100), end of data (eop- end_of_datapacket) and byte_valid (3:0) signals. Byte valid (3:0) indicates how many bytes are valid in last 128 bit data word of data stream (0000- all 16 bytes valid, 0001- 1 byte valid, 1111-16 bytes valid, etc.). One or more core blocks of the KVS architecture that are critical for implementation of the proposed method of the present disclosure depicted in FIG. 3 are described below:
[080] Hash Value Calculator (also referred as ‘Hash_val_calculator’ as depicted in FIG. 3): 256 bit key and command are read by Hash_val_calculator, which computes 16 bit checksum on 256 bit key. In an embodiment, the system 100 may employ any other hash function (e.g., CRC) and such usage of hash function shall not be construed as limiting the scope of the present disclosure. The Hash_val_calculator uses a pipelined architecture and computes ‘n’ bit checksum (or ‘n’ bit hash value), say for example, 16 bit checksum in 6 clock cycles. It puts the 16 bit checksum, key-value and command code in a small internal FIFO from where the next downstream block which is Operations_decode_exec_sm reads the key-value, 16 bit checksum (hash_val) and 2 bit command code. While the Operations_decode_exec_sm decodes and executes the command, the Hash_val_calculator looks ahead, fetches next key and command and computes the hash value, thus resulting in a highly pipelined architecture.
[081] Operations Decode Execute State Machine (Operations_decode_exec_sm): The function of operations_decode_exec_sm is to interpret the 2 bit command code and execute the corresponding command (00- insert key, 01- search, 10 – delete key). While operations_decode_execute_sm is executing the command, the hash_val_calculator looks ahead, fetches the next key and computes hash value, storing it in the internal FIFO (also referred as ‘internal queue). This parallel operation of hash_val_calculator and fetch_decode_exec_sm increases the throughput of the system 100 (e.g., KVS architecture or KVS system depicted in FIG. 3). The operations_decode_exec_sm decodes and executes different commands, for example: an insert key command, a delete key command, or a search key command.
[082] For new key insertion, keys are stored in hash buckets of different capacities, bucket with capacity of 1 key (256 bit wide), 4 keys (1024 bit wide), 8 keys (2048 bit wide) and 16 keys (4096 bit wide). The buckets are stored in bucket memory – a Block RAM (BRAM) inside FPGA and buckets of different capacities are used for conserving memory. As shown in FIG. 7, Bucket memory buckt_mem consists of bucket groups, buckt_grp and each bucket group can consist of 1 bucket, 2 buckets, 4 buckets or 16 buckets. Bucket group with 1 bucket contains 16 keys (16 keys bucket). For bucket group with 2 buckets, each bucket contains 8 keys (8 key bucket), for bucket group with 4 buckets, each bucket contains 4 keys (4 key bucket) and for bucket group with 16 buckets, each bucket contains one key (1 key bucket). Thus a bucket group always contains 16 keys. As each key is 256 bit wide, width of bucket group is 4096 bits and bucket memory is an array of bucket groups of different capacities. Each bucket is identified by a pointer, which consists of a 16 bit offset into buckt_mem (bkt_offset) and a 4 bit bucket_no. Interpretation of bucket_no depends upon the type of bucket. For 16 key hash bucket, all four bits of bucket_no ie. bucket_no(3:0) identify a key within bucket. For 4 key hash bucket, bucket_no(3:2) identifies particular bucket and bucket_no(1:0) identifies key within the identified bucket. For 8 key bucket, bucket_no[3] identifies one of two buckets while bucket_no(2:0) identifies key within bucket. For 1 key bucket, all for bits bucket_no(3:0) identify a bucket number, since there is only one key in bucket. Corresponding to every bucket, there is a bucket descriptor, which identifies whether bucket is valid (allocated), count of collision keys in bucket, type of bucket (1 key or 4 key or 8 key or 16 key bucket) and pointer to bucket consisting of 16 bit offset value and a 4 bit bucket number. So bucket descriptor memory i.e., buckt_desc_mem is an array of bucket descriptor structures with each structure consisting of 2 bit ptr_type indicating the particular type of bucket, 5 bit key_cnt indicating count of keys in bucket (count = 1 indicates 1 key in a bucket, count = 16 indicates 16 keys in a bucket), a 1 bit valid flag, ptr_vld indicating whether bucket is already assigned and a 20 bit bucket pointer which consists of 16 bit offset into bucket_mem and 4 bit bucket_no which identifies bucket in a bucket group as described above. When key is inserted first time by insert_key command, hash_val is used as address into a bucket_descriptor_memory as shown in FIG. 5B (bucket_number is interpreted based on the ptr_type value- ptr_type 00- one key bucket and 4 bit bucket_number, ptr_type 01- 4 key bucket and 2 bit bucket_number, ptr_type 10- 8 key bucket and 1 bit bucket_number, ptr_type 11 – 16 key bucket). The pointer to the buckets of different capacities (1key bucket, 4 key bucket, 8 key bucket and 16 key bucket) are stored in free bucket pointer pool, which consists of 4 FIFOs containing pointers to 1 key buckets, 4 key buckets, 8 key buckets and 16 key buckets. These pointers are initialized by initialization state machine (init_sm) before the operation of the KVS is enabled. The sum of number of 1 key buckets, 4 key buckets, 8 key buckets and 16 key buckets is fixed based on allocated Block RAM memory and actual number of different types of buckets are configured at run time by the configuration_register_access_logic block. If number of collision keys exceeds 16, one or more hash buckets are allocated from DRAM. In DRAM, there is only one bucket type, which contains 32 keys and all such buckets are linked forming a linked list. So there is no upper limit on number of collision keys if DRAM is used.
[083] Below described is how the insert_key, delete_key and search_key commands are executed by operations_decode_exec_sm block depicted in FIG. 3:
[084] Insert_key: For insert_key command execution, incoming hash value hash_val is used as address into bucket descriptor memory and bucket descriptor is read out. If ptr_vld is 0, it means bucket is not allocated and operations_decode_exec_sm tries to allocate a 1 key bucket to the key by reading from 1 key bucket free pool FIFO. If 1 key bucket is not available, it searches for 4 key bucket from 4 key bucket free pool FIFO. If 4 key bucket is not available, 8 key bucket free pool is read. If 8 key bucket free pool is not empty, 16 key bucket free pool is searched and one of the buckets and is allocated based on availability. Key count is set to one, ptr_vld is set to one and pointer to bucket obtained from free pool is written into bucket descriptor and bucket descriptor is written into bucket descriptor memory using hash value as offset. If ptr_vld is 1, indicating bucket is already occupied, key is written to the same bucket depending upon how many keys are already stored in the same bucket. Else (when ptr_vld is 0), this means there is no bucket allocated. For example, if the ptr_vld is 1, ptr_type is 1 (indicating a 4 key bucket), if bucket already contains 4 keys as indicated by count of keys obtained from bucket descriptor, a new 8 key bucket is allocated based on availability, corresponding bucket descriptor corresponding to 8 key bucket is populated and written into bucket descriptor memory. 4 key bucket which was occupied is returned back to 4 key bucket free pool FIFO, by writing the pointer back to FIFO. If 8 key bucket is not available, the system 100 (or logic in the system 100) tries to allocate 16 key bucket and if 16 key bucket is not available, it allocates 32 key bucket from DRAM. Once the key is allocated and written into a bucket, a pointer for storing data is obtained from data pointer free pool FIFO (which stores the pointers to free data segments used for storing data corresponding to particular key) and this pointer along with key and command code is supplied to downstream data read/write manager block (data_rw_mngr). This data pointer is also written at same position corresponding to key in dtptr_grp_memory using bucket_no(3:0) bits.
[085] Delete_key: For delete operation, bucket descriptor is read using the hash value from the bucket descriptor memory and if bucket contains more than one key, incoming key to be deleted is compared with all keys in bucket and index of the matching key (number between 0-15) is calculated by comparator block implemented in FPGA logic. This comparator compares a maximum of 16 keys in a bucket with incoming key and gives the index of matching key as output. In case of DRAM, the comparator can perform comparison (in parallel) for a maximum of 32 keys in a bucket with incoming key and gives the index of matching key as output. After matching key is found, the data pointer at the same index from corresponding data pointer bucket group is read and sent to data_rw_mngr block. This block deallocates all data segments allocated to particular key and returns them to free pool.
[086] Search_key: During the execution of search_key command, bucket descriptor is read using the hash value as offset, from the bucket descriptor memory and if bucket contains more than one key, incoming key to be searched is compared with all keys in bucket and index of the matching key (number between 0-15) is calculated by comparator block implemented in FPGA logic. This comparator compares keys (say a maximum of 16 keys) in a bucket with incoming key and gives the index of matching key as output. After matching key is found, the data pointer at the same index from corresponding data pointer bucket group is read and sent to data_rw_mngr block. This block reads all the data segments using the data pointer and returns the data to on response interface to user.
[087] Data_rw_mngr: Data_rw_mngr also referred as ‘data read/write manager block’ receives a stream of input structures consisting of key-value, 32 bit data pointer and command code from upstream operations_decode_exec_sm block. The Data_rw_mngr block interprets the command code and carries out operations on the data of the key in based on the command, in following way:
[088] Insert_key: In case of Insert_key command, the data_rw_mngr reads the data from data FIFO and writes the data in data memory starting from the address given by data pointer. As shown in FIG. 4, data memory consists of 128byte data segments and is implemented using Block RAM. Since the data corresponding to a key can be of variable length, it is stored in data segments which are linked using a linked list in data memory. Each data segment has a corresponding descriptor which stores the attributes of data segment. The data segment descriptor contains following information: (i) valid bit which indicates the information in descriptor is valid, (ii) next_desc_ptr: pointer to the next descriptor used for forming linked list, (iii) nxt_ptr_vld: last segment bit indicating this segment is last one in linked list and (iv) byte_cnt: count of number of bytes in last segment. This is shown in FIG. 4. The pointer to the first data segment for a particular key is stored in data pointer group memory dtptr_grp_mem which has structure similar to buckt_mem since there is one data pointer (pointer to first data segment) corresponding to each key. Data segment descriptors are stored in segment_descriptor memory, which is also a Block RAM. Pointer to free data segment descriptors (and corresponding data segments) are stored in data pointer free pool FIFO. For Insert_key command, data_rw_mngr allocates additional descriptors and data segments by reading pointers from data pointer free pool FIFO. It forms the linked list of data segments by populating the corresponding data segment descriptors and also writes the byte_cnt and nxt_ptr_vld information in last descriptor. If data segment pointers are not available in data pointer free pool FIFO, data is stored in DRAM by reading pointers from DRAM data pointer free pool FIFO. In DRAM, data may be stored in fixed length data segments forming a linked list, in an example embodiment. Each data segment in DRAM has corresponding data segment descriptor which has structure similar to data segment descriptors for Block RAM.
[089] Search_key: For executing search_key command, data_rw_mngr reads the linked list of data segments starting from the segment pointed to by data pointer (pointer to first data segment) received from operations_decode_exec_sm. It also reads the corresponding segment descriptors to find out the address of next data segment and last segment information. When nxt_ptr_vld bit in segment descriptor is reset, it uses byte_cnt information to read exact number of bytes. The data read from all data segments along with the key and command information is stored in response data FIFO, cmd_key_response_data_fifo shown in FIG. 3. The response controller state machine resp_out_cntlr reads the data, corresponding command and supplies it on the data output interface.
[090] Delete_key: For executing delete_key command, data_rw_mngr reads the linked list of data segment descriptors using data pointer to first data segment received from operations_decode_exec_sm, resets their valid bits and returns the data pointers of all the data segments in linked list to the data pointer free pool FIFO.
[091] FIG. 4, with reference to FIGS. 1 through 3, illustrates an exemplary data segment descriptor and data segment memory according to an embodiment of the present disclosure. Data corresponding to a key can be of variable length and is stored in linked list of 128 byte data segments. Corresponding to every data segment, there is a data segment descriptor which points to data segments and also contains attribute information. Format of data segment descriptor is depicted in FIG. 4.
[092] Nxt_ptr(32 bit) - This is 32 bit pointer to next data segment, used to form a linked list of data segments.
[093] Nxt_ptr_vld (1 bit) - If nxt_ptr_vld is set, 32 bit data pointer is valid and there is one more data segment present in linked list. If nxt_ptr_vld is reset, data segment pointed to by this descriptor is the last data segment in linked list.
[094] Byte_vld (7 bit) - If nxt_ptr_vld field is reset, indicating that the data segment pointed to by this descriptor is the last segment, this field indicates how many bytes are valid in last data segment.
[095] Since the data segments are corresponding descriptors are present at same offset in memory, data segment descriptors do not contain pointer to the data segment.
[096] Data segments can contain maximum of 128 bytes of data. The last data segment can contain less than 128 bytes of data. This is indicated by byte_vld field in the corresponding data segment descriptor.
[097] FIG. 5A, with reference to FIGS. 1 through 4, depict a traditional key-value store architecture according to an example embodiment of the present disclosure. FIG. 5B, with reference to FIGS. 1 through 5A, depict an exemplary key-value store architecture proposed by the system 100 of FIG. 1 according to an example embodiment of the present disclosure.
[098] Many of the software based KVS engines use hashing process to hash a fixed length key using different techniques such as Cyclic Redundancy Check (CRC), checksum, etc. The hash value is used as index into a hash table, which stores a pointer to linked list of all the colliding keys. This is shown in FIG. 5A. In case of search operation, incoming key is hashed and hash value is used to index hash table which contains pointer to the linked list of all the keys. The keys in linked list are read sequentially and compared with incoming key. When a matching key is found, corresponding data pointer is used to read the data and return data to user. Since the keys are stored in linked list and read sequentially from memory for comparison, the search is slow if there are large number of colliding keys. The KVS architecture implemented by the proposed system 100 of FIG. 1 is depicted in FIG. 5B. The proposed KVS architecture is configured to reduce the latency and optimize memory usage as shown in FIG. 5B. The incoming key is hashed using checksum technique and hash value is used as index into hash table (stored in Block RAM, or BRAM) which stores a key descriptor. The key descriptor contains a valid bit and a pointer to hash bucket which contains either 1, 4, 8 or 16 keys (e.g., keys are stored contiguously in hash bucket). Information pertaining to type of the hash bucket and number of colliding keys is also stored in key descriptor.
[099] For a search operation, incoming key is hashed using checksum technique (or algorithm /hash function), and the hash value is used as index to read the key descriptor stored in Block RAM. All the keys stored in hash bucket are read using pointer in key descriptor, into a parallel comparator (not shown in FIG. 5B) in FPGA. The comparator compares all keys in hash bucket in parallel with incoming key and gives the index of matching key, which is used to obtain data pointer corresponding to that key. This parallel comparison provides (very) low latency and pipelined operations of different blocks results in very high throughput.
[0100] In an embodiment of the present disclosure, to conserve Block RAM, hash buckets of 4 different sizes are used:
1 key bucket - bucket which can contain 1 key maximum
4 key bucket - buckets which can contain 4 keys maximum.
8 key bucket - bucket which can contain 8 keys maximum.
16 key bucket - bucket which can contain 16 keys maximum.
32 key bucket – bucket which can contain 32 keys maximum.
[0101] FIG. 6, with reference to FIGS. 1 through 5B, depicts format of bucket capacities and bucket groups according an example embodiment of the present disclosure.
[0102] Hash buckets: Hash buckets in Block RAM are of size 1, 4, 8 and 16 to conserve memory. Hash bucket in DRAM always contains 32 keys and these buckets are linked in a linked list fashion. DRAM is of very large size as compared to Block RAM and hence large number of keys can be stored in DRAM. Each hash bucket contains a bucket attribute structure (bkt_attr_strct) which contains information about the count of keys in bucket (key_cnt-5 bit), pointer to next hash bucket in linked list (nxt_ptr-20 bit) and a valid bit indicating that pointer information is valid (nptr_vld - 1 bit). Pointer to next bucket (nxt_ptr) itself consists of 16 bit offset and 4 bit bucket number (bucket_no).
[0103] Bucket Group: As depicted in FIG. 6, each bucket group can consist of 1 16_key_bucket, 2 8_key_buckets, 4 4_key_buckets or 16 1 key_buckets. Thus a bucket group always contains 16 keys. As each key is 256 bit wide, width of bucket group is 4096 bits. Bucket memory is an array of bucket groups of different capacities. Each bucket is identified by a bucket_ptr field present in bucket descriptor, which consists of a 16 bit offset (bucket_offset) into bucket memory and a 4 bit bucket number (bucket_no(3:0)).
[0104] Data pointer buckets: Corresponding to every key stored in hash bucket, there is a 32 bit pointer indicating where data corresponding to the key is stored. This data is stored in linked list of data segments, where each data segment can contain maximum of 128 bytes of data. Data pointer points to first data segment in the linked list. Data pointers are stored in data pointer buckets. Since data corresponding to a key can be present in Block RAM or DRAM, there is one bit with every data pointer, indicating if the data pointer points to data in Block RAM (BRAM) or DRAM. Data pointers are stored in buckets of 4 capacities based on bucket type used for storing the key.
[0105] Data Pointer group: A data pointer group is similar to bucket group described above and has similar structure as bucket group. The data pointer group, however contains data pointers bucket which in turn contains data pointers.
[0106] FIG. 7, with reference to FIGS. 1 through 6, depicts key bucket memory with bucket groups according to an embodiment of the present disclosure. As depicted in FIG. 7, a bucket memory is an array of bucket groups of different capacities. Each bucket is identified by a nxt_ptr field present in bucket descriptor, which consists of a 16 bit offset (bucket_offset) into bucket memory and a 4 bit bucket number (bucket_no(3:0)).
[0107] FIG. 8, with reference to FIGS. 1 through 7, depicts bucket descriptor data structure according to an embodiment of the present disclosure. More specifically, FIG. 8 depicts hash function, hash table which contains bucket descriptors and bucket descriptor format. Description of each these components is given below:
[0108] Hash Table (bucket descriptor memory): Incoming 256 bit key is hashed using the 16 bit checksum function (or hash function). The 16 bit hash value (hash_val) is used as index into hash table. Hash table stores the bucket descriptors (bucket_desc).
[0109] Bucket descriptor: Hash table is an array of bucket descriptors and each bucket descriptor contains 6 fields as depicted in FIG. 8. The format of bucket descriptor is described below:
1. Ptr_vld (1 bit) - Indicates contents of bucket descriptor are valid and it holds a valid pointer to hash bucket containing one or more keys.
2. Ptr_type (2 bit) - Indicates the type of hash bucket or capacity of hash bucket if present in Block RAM.
[0110] Since amount of Block RAM in FPGA is limited, this design uses hash buckets of 4 capacities for storing keys as shown below by way of example:

Ptr_type Bucket capacity
00 1 key bucket (256 bit wide)
01 4 key bucket (1024 bit wide)
10 8 key bucket (2048 bit wide)
11 16 key bucket (4096 bit wide)

The above interpretation is valid when hash bucket is present in Block RAM.
3. nxt_ptr (16 bits+ 4 bits) - This is 20 bit pointer to hash bucket pointed to by this descriptor as depicted in FIG. 7. If DRAM_flg is reset, this pointer points to hash bucket in BRAM and consists of 16 bit offset to bucket group (bucket_offset) and 4 bit bucket number (bucket_no(3:0)). A bucket group consists of 1, 4, 8 or 16 hash buckets as explained below and a hash bucket can contain maximum of 16 keys (if present in Block RAM). If DRAM_flg is set, all 20 bits of pointer point to hash bucket in DRAM containing 32 keys. DRAM contains only buckets with 32 keys and ptr_type field is not valid if bucket is contained in DRAM.
4. DRAM_flg (1 bit) - When set, this flag indicates bucket_ptr points to hash bucket present in DRAM. If DRAM_flg is set, ptr_type field has no significance. When reset, flag indicates the bucket_ptr points to hash bucket present in Block RAM (Block RAM) inside FPGA and ptr_type field is interpreted as described above.
5. Key_cnt (5 bit) - Indicates count of colliding keys in the hash bucket pointed to by pointer in this descriptor. This field is valid only if DRAM_flg is reset, i.e. if the bucket is present in Block RAM.
[0111] Embodiments of the present disclosure provide systems and methods for performing key-value store operations by implementing a very low latency key-value search engine IP core in FPGA. Search engine block optimizes use of Block RAM with an efficient memory management scheme. The block supports fixed length (256 byte) keys and variable length associated data. As discussed above, the system 100 supports three commands, namely search key command that when executed matches the incoming key with keys stored in data base and returns data of matching key, insert key command that when executed inserts new key along with the data in database, allocates memory for both key and data, and updates the collision count in case of a collision, and delete key command that when executed deletes the key which matches incoming key, releases the memory allocated to both key and corresponding data.
[0112] In the present disclosure, key, command along with data are received on user interface which uses data_valid/acknowledge protocol for both key and data. 256 bit incoming key is hashed by a using checksum algorithm to generate 16 bit hash value. Hash value is used as index into a memory which stores pointers to hash buckets of different sizes. Hash buckets store the keys in contiguous memory. Search Engine (not shown in FIGS. 1 through 3) uses hash buckets of different sizes to optimize use of the Block RAM inside FPGA. After hashing, the insert key, search key and delete key commands are decoded and executed by command decoder block. For a search operation, data associated with key is retrieved and supplied on result interface. Since the keys in FPGA are compared in parallel, time required for search operation is same irrespective of number of keys in bucket i.e., size of the bucket. In traditional KVS implementation since the keys are stored in linked list, time for search is proportional to number of keys.
[0113] As in the traditional systems and approaches the search is performed sequentially one after another, this results in a lot of latency, and formation of memory holes. Unlike traditional systems and approaches, embodiments of the present disclosure and systems and methods associated thereof performing search operation in parallel thus resulting in an efficient memory management scheme which optimizes use of FPGA internal memory (Block RAM), thereby achieving minimal latency. The present disclosure further implements shifting of keys to refrain from forming memory holes. With this proposed method, the latency is ensured to be minimal such that the keys are stored in a contiguous memory thereby enabling faster, and efficient means of data retrieval for subsequent key-value store operations. The above approach of shifting keys upon delete key operation enables the system 100 to intelligently identify empty slots in specific key and data hash buckets for performing search and insert key-value store operations which may not be possible in conventional systems and methods. In other words, conventional systems and methods perform delete key operations thereby forming memory holes. Therefore when a key operation (e.g., search, and delete operations) are to be performed, the conventional systems and methods search for a matching key in occupied slots, and as well as memory holes that were formed in between other keys during previous operations, thus consuming more time and processing speed/computations to fetch desired output.
[0114] The written description describes the subject matter herein to enable any person skilled in the art to make and use the embodiments. The scope of the subject matter embodiments is defined by the claims and may include other modifications that occur to those skilled in the art. Such other modifications are intended to be within the scope of the claims if they have similar elements that do not differ from the literal language of the claims or if they include equivalent elements with insubstantial differences from the literal language of the claims.
[0115] It is to be understood that the scope of the protection is extended to such a program and in addition to a computer-readable means having a message therein; such computer-readable storage means contain program-code means for implementation of one or more steps of the method, when the program runs on a server or mobile device or any suitable programmable device. The hardware device can be any kind of device which can be programmed including e.g. any kind of computer like a server or a personal computer, or the like, or any combination thereof. The device may also include means which could be e.g. hardware means like e.g. an application-specific integrated circuit (ASIC), a field-programmable gate array (FPGA), or a combination of hardware and software means, e.g. an ASIC and an FPGA, or at least one microprocessor and at least one memory with software modules located therein. Thus, the means can include both hardware means and software means. The method embodiments described herein could be implemented in hardware and software. The device may also include software means. Alternatively, the embodiments may be implemented on different hardware devices, e.g. using a plurality of CPUs.
[0116] The embodiments herein can comprise hardware and software elements. The embodiments that are implemented in software include but are not limited to, firmware, resident software, microcode, etc. The functions performed by various modules described herein may be implemented in other modules or combinations of other modules. For the purpose of this description, a computer-usable or computer readable medium can be any apparatus that can comprise, store, communicate, propagate, or transport the program for use by or in connection with the instruction execution system, apparatus, or device.
[0117] The illustrated steps are set out to explain the exemplary embodiments shown, and it should be anticipated that ongoing technological development will change the manner in which particular functions are performed. These examples are presented herein for purposes of illustration, and not limitation. Further, the boundaries of the functional building blocks have been arbitrarily defined herein for the convenience of the description. Alternative boundaries can be defined so long as the specified functions and relationships thereof are appropriately performed. Alternatives (including equivalents, extensions, variations, deviations, etc., of those described herein) will be apparent to persons skilled in the relevant art(s) based on the teachings contained herein. Such alternatives fall within the scope and spirit of the disclosed embodiments. Also, the words “comprising,” “having,” “containing,” and “including,” and other similar forms are intended to be equivalent in meaning and be open ended in that an item or items following any one of these words is not meant to be an exhaustive listing of such item or items, or meant to be limited to only the listed item or items. It must also be noted that as used herein and in the appended claims, the singular forms “a,” “an,” and “the” include plural references unless the context clearly dictates otherwise.
[0118] Furthermore, one or more computer-readable storage media may be utilized in implementing embodiments consistent with the present disclosure. A computer-readable storage medium refers to any type of physical memory on which information or data readable by a processor may be stored. Thus, a computer-readable storage medium may store logic(s) for execution by processor(s), for causing the processor(s) to perform steps or stages consistent with the embodiments described herein. The term “computer-readable medium” should be understood to include tangible items and exclude carrier waves and transient signals, i.e., be non-transitory. Examples include random access memory (RAM), read-only memory (ROM), volatile memory, nonvolatile memory, hard drives, CD ROMs, DVDs, flash drives, disks, and any other known physical storage media.
[0119] It is intended that the disclosure and examples be considered as exemplary only, with a true scope and spirit of disclosed embodiments being indicated by the following claims.