Patent Description:
A KV store or a KV database, is a data storage paradigm designed for storing, retrieving, and managing associative arrays, and a data structure more commonly known as a hash table. Hash tables contain a collection of objects, or records, which in turn have many different fields within them, each containing data. These records may be stored and retrieved using a key that uniquely identifies the record, and may be used to find the data within the database. KV stores often use less memory than a relational database.

<CIT> discloses: A system comprises a host processor and a storage system. The storage system comprises one or more storage devices, and each storage device comprises a non-volatile memory and a compute offload controller. The non-volatile memory stores data, and the compute offload controller performs compute tasks on the data based on compute offload commands from the host processor.

<CIT> discloses: Systems for distributed computing systems. A topological configuration of computing nodes is selected to manage availability of metadata data in a computing system. A method commences by accessing a plurality of node topology attributes and using those attributes to map between nodes and availability domains. Resource usage measurements such as computing node load are collected. A plurality of candidate replication configurations are generated, and each candidate replication configuration is scored with respect to several quantitative objectives. Additionally, the candidate replication configurations are given respective resource usage balance scores. One or more candidate replication configurations are selected based on resource usage balance scores and/or a separation skew value. Determination of a selected configuration is dominated by resource usage when there is a tie between best-scoring configurations or when none of the configurations meet a scoring threshold. Recalculation of configurations are triggered by an administrative command or by a topology change.

<CIT> discloses: A data storage device includes a nonvolatile memory device including a key storage area and a value storage area; and a first control circuit configured to control storing a value in the value storage area, and storing a key corresponding to the value with address information of a value in the key storage area according to a KV command.

The present disclosure is made to address at least some of the disadvantages described above and to provide at least the advantages described below.

An aspect of the present disclosure is to provide a system and method that allows packing of multiple keys inserted with no temporal locality, such that they may be grouped into a bunch of memory pages (e.g. NAND pages) with spatial locality. This provides a reduction in the number of NAND pages required to store all keys, and read amplification factor (RAF)/ write amplification factor (WAF) reduction due to dense key packing. Further, NAND pages may limit garbage collection (GC) to when all keys in a page are invalidated.

Accordingly, the present disclosure may significantly reduce GC overheads by a factor of packing density and reduce lengths of hash-map collision chains, which improves tail latency and lessens the number of NAND page reads that significantly decrease lookup latencies.

According to one embodiment, a KV store may be provided, which includes a key logger; and a processor configured to receive a first command for storing a first KV in the KV store, write a first value of the first KV to a first memory page, generate an extent map for identifying the first memory page including the value, write the extent map to a second memory page, append an entry for storing the first KV to the key logger, and update a device hashmap of the KV store to include a first key of the first KV, upon a threshold being met within the key logger.

Hereinafter, embodiments of the present disclosure are described in detail with reference to the accompanying drawings. It should be noted that the same elements will be designated by the same reference numerals although they are shown in different drawings. In the following description, specific details such as detailed configurations and components are merely provided to assist with the overall understanding of the embodiments of the present disclosure. Therefore, it should be apparent to those skilled in the art that various changes and modifications of the embodiments described herein may be made without departing from the scope of the present disclosure. In addition, descriptions of well-known functions and constructions are omitted for clarity and conciseness. The terms described below are terms defined in consideration of the functions in the present disclosure, and may be different according to users, intentions of the users, or customs. Therefore, the definitions of the terms should be determined based on the contents throughout this specification.

The present disclosure may have various modifications and various embodiments, among which embodiments are described below in detail with reference to the accompanying drawings. However, it should be understood that the present disclosure is not limited to the embodiments, but includes all modifications, equivalents, and alternatives within the scope of the present disclosure.

An electronic device according to one embodiment may be one of various types of electronic devices. The electronic devices may include, for example, a portable communication device (e.g., a smart phone), a computer, a portable multimedia device, a portable medical device, a camera, a wearable device, or a home appliance. According to one embodiment of the disclosure, an electronic device is not limited to those described above.

The terms used in the present disclosure are not intended to limit the present disclosure but are intended to include various changes, equivalents, or replacements for a corresponding embodiment. With regard to the descriptions of the accompanying drawings, similar reference numerals may be used to refer to similar or related elements. A singular form of a noun corresponding to an item may include one or more of the things, unless the relevant context clearly indicates otherwise. As used herein, terms such as "<NUM>st," "2nd," "first," and "second" may be used to distinguish a corresponding component from another component, but are not intended to limit the components in other aspects (e.g., importance or order). It is intended that if an element (e.g., a first element) is referred to, with or without the term "operatively" or "communicatively", as "coupled with," "coupled to," "connected with," or "connected to" another element (e.g., a second element), it indicates that the element may be coupled with the other element directly (e.g., wired), wirelessly, or via a third element.

As used herein, the term "module" may include a unit implemented in hardware, software, or firmware, and may interchangeably be used with other terms, for example, "logic," "logic block," "part," and "circuitry. " A module may be a single integral component, or a minimum unit or part thereof, adapted to perform one or more functions. For example, according to one embodiment, a module may be implemented in a form of an application-specific integrated circuit (ASIC).

Herein, any of the components or any combination of the components described (i.e., in the device diagrams) can be used to perform one or more of the operations of the flowcharts. The operations depicted in the flowcharts are exemplary operations and may involve various additional steps not explicitly provided in the flowcharts. The order of the operations depicted in the flowcharts is exemplary and not exclusive, as the order may vary depending on the implementation.

An objective of a key value (KV) store may be to complete operations (e.g., Put/Get/Delete operations) in the fastest time possible, and in a typical KV store implementation, keys can be hashed and inserted into a hashmap.

Reducing tail latency of KV operations may be beneficial for several workloads like artificial intelligence/machine learning (AI/ML), data sciences, etc. Further, it may be beneficial that KV technology will adapt to dense media with lower longevity.

High performance computing (HPC) storage may be designed to be compatible with media having <NUM>-<NUM> write cycles. Consequently, reducing a WAF caused by application or device induced GC may also be beneficial. For example, reducing device WAF may also decrease an RAF in KV stores, possibly improving overall storage performance.

A single NAND page can contain one key, which may result in higher device WAF when processing Delete operations and higher RAF when processing Put/Get/Exist operations.

Additionally, worst case tail latency of a KV store may be proportional to a length of a longest collision chain in buckets of the hashmap. Increasing a number of buckets to reduce collision chains results in extra memory space required to host the buckets.

Further, if buckets are themselves stored in NAND, when processing Put of a KV, device WAF increases, since for almost each KV insert, the NAND page hosting the bucket may need to be replaced.

In accordance with this disclosure, systems and methods are provided, which allow for the packing of multiple keys together in a single NAND page, which may reduce worst case collision length in a device hashmap. Keys in the device hashmap may be grouped together to have spatial locality even though the keys themselves have no temporal locality.

<FIG> illustrates a hash implementation in a KV SSD.

As illustrated in <FIG>, keys are hashed and inserted into a hashmap. However, a single NAND page can contain only one key. For example, bucket 2f8 in the hashmap incudes a chain for Key1, Key34, and Key21. Each of Key1, Key34, and Key21 is stored on a separate NAND page. As described above, this may result in higher RAF during Puts/Gets/Exists, and higher device WAF during Deletes. Further, the worst case tail latency may be proportional to the length of longest collision chain in buckets of the hashmap, e.g., bucket <NUM> in <FIG>.

In accordance with an embodiment of the disclosure, multiple keys may be packed together in a single NAND page to reduce the worst case collision length in a hashmap by a packing factor P (average number of keys packed per page).

<FIG> illustrates a hash implementation in a KV SSD, according to an embodiment.

Referring to <FIG>, multiple keys may be packed together in a single NAND page, wherein each key contains an extent pointer.

A method according to an embodiment of the disclosure includes gathering related keys that have no temporal locality and grouping them together to have spatial locality. That is, keys that are indexed within contiguous buckets of the hashmap may be grouped into bucket groups.

Additionally, the format of the KV entries may be modified such that a value may be written to NAND pages and may be tracked by an extent map. The extent map itself may be written to a NAND page, which may also contain part of the value, if space is available in the NAND page after writing the extent map. A key contains one extent pointer to the NAND page that contains the actual extent map, which in turn locates the pages containing the value for the key.

This may significantly reduce device WAF/RAF when processing Get/Put/Delete operations by an entire factor of P. For example, if on an average, <NUM> keys can be packed into a page, the collision chain length reduces by <NUM> times along with a corresponding device WAF/RAF reduction by <NUM> times.

Key packing, as described above, can be achieved with minimal additional resources consumed within the KV Store.

<FIG> illustrates a KV store, according to an embodiment.

Referring to <FIG>, the KV store <NUM> includes a key logger <NUM> (e.g., an Auto Operation Logger (AOL)) that may be used to assist in key packing, a Bloom filter <NUM> to track keys in key logger <NUM>, and a tail pointer table <NUM> to create a back linked-list of keys in the key logger <NUM>. key logger <NUM> may be device wide and may only have append operations to it. Therefore, it may be implemented internally, like a Zoned namespace.

A Bloom filter <NUM> tracks keys in the key logger <NUM> and therefore may be compact.

For example, if the key logger <NUM> contains <NUM> entries, the Bloom filter <NUM> may include as few as <NUM> pages (each <NUM> RAM/SRAM/DRAM).

Given that less than <NUM>% of keys are logged in the key logger <NUM>, compared to total keys in KV stores, most of the Get/Put/Delete operations will not include traversing the tail pointer table <NUM> of entries in the key logger <NUM>.

A tail pointer table <NUM> may be so constructed that if the Bloom filter <NUM> denotes a hit, the number of entries required to be traversed in the key logger <NUM> may be limited to one or two entries only. For example, if key logger <NUM> has <NUM> entries, the tail pointer table <NUM> may have <NUM> entries (each pointer being <NUM> bits only).

Although <FIG> illustrates the components of the KV store <NUM> as separate elements, the disclosure is not limited thereto. For example, at least two of the components may be combined into a single element, such as a processor, integrated circuit (IC), system on chip (SoC), etc., which may perform the corresponding operations.

<FIG> and <FIG> illustrate a deferred key packing operation in a KV store, according to an embodiment. More specifically, <FIG> illustrates an example before processing deferred key packing in KV stores, and <FIG> illustrates an example after processing deferred packing of keys from a key logger. The deferred key packing operation may be based on Store (or Put) and Delete operations on KVs being first written only to the key logger. That is, instead of immediately performing the received Store and Delete operations, the entries may be written in the key logger until a certain threshold is reached and the operation may be performed. For example, the threshold may be a function of the percentage of entries in the key logger and/or a rate at which the key logger is filling up.

Referring to <FIG>, a bucket group includes <NUM> buckets B1 to B8 and points to logical NAND pages <NUM> and <NUM> on which multiple keys are packed with extent pointers (ExtentP). In the example illustrated in <FIG>, each logical NAND page may include a maximum of <NUM> keys, and includes a pointer to the next page containing keys of bucket group.

On logical page <NUM>, Key1 contains an extent pointer to an extent map stored on page <NUM>. The extent map stored on page <NUM> identifies the page on which the value corresponding Key1 is stored. Similarly, Key12 contains an extent pointer to an extent map stored on page <NUM>, Key2 contains an extent pointer to an extent map stored on page <NUM>, KeyA contains an extent pointer to an extent map stored on page <NUM>, and Key5 contains an extent pointer to an extent map stored on page <NUM>. Each of the extent maps identifies the pages on which the values of the corresponding key are stored.

Additionally, <FIG> provides an example of a key logger with two chains of entries. Assuming that certain threshold is reached, the entries in the key logger may then be processed, i.e., deferred key packing may be performed.

Referring to <FIG>, among the entries of the chain being processed, there is a Store entry and a Delete entry for Key1/ExtentP <NUM>, which essentially cancel each other out.

There is also Store entry for Key1/ExtentP <NUM>. Accordingly, logical page <NUM> receives a new entry for Key1 that contains an extent pointer to page <NUM>, on which an extent map is stored, which identifies the pages one which the value corresponding to Key1 are stored.

Additionally, the old Key1 (as illustrated in <FIG>) is removed from logical page <NUM>, and page <NUM>, which included the extent map for old Key1, and the pages identified by the extent map for old Key1 are queued for erase.

Similarly, there is a Store entry for Key2/ExtentP <NUM>. Accordingly, logical page <NUM> receives a new entry for Key2 that contains an extent pointer to page <NUM>, on which an extent map is stored, which identifies the pages one which the value corresponding to Key2 are stored.

Additionally, the old Key2 (as illustrated in <FIG>) is removed from logical page <NUM>, and page <NUM>, which included the extent map for old Key2, and the pages identified by the extent map for old Key2 are queued for erase.

There is also a Store entry for Key3/ExtentP <NUM>. Accordingly, logical page <NUM> receives a new entry for Key3 that contains an extent pointer to page <NUM>, on which an extent map is stored, which identifies the pages on which the value corresponding to Key3 are stored.

There is also a Delete entry for Key12, which results in Key12 being removed from logical page <NUM>, and page <NUM>, which included the extent map for Key12, and the pages identified by the extent map for Key12 are queued for erase.

Similarly, there is a Delete entry for Key5, which results in Key5 being removed from logical page <NUM>, and page <NUM>, which included the extent map for Key5, and the pages identified by the extent map for Key5 are queued for erase.

Because two keys were removed from logical page <NUM> (Key12 and Key5) and one new key was added to logical page <NUM> (Key3), only <NUM> keys are left on logical page <NUM>. Therefore, KeyX is moved from logical page <NUM> (as illustrated in <FIG>) to logical page <NUM> (as illustrated in <FIG>) so that logical page <NUM> includes the maximum of <NUM> keys.

<FIG> is a flowchart illustrating a key packing operation of a KV store, according to an embodiment.

Referring to <FIG>, in step <NUM>, a key logger logs key entries for Store and Delete operations.

After a certain threshold is met in the key logger in step <NUM>, e.g., the key logger is filled beyond a set threshold, key entries belonging to a group of adjacent buckets in a device hashmap are collated in step <NUM>.

In step <NUM>, existing keys in the device hashmap are merged with entries from the key logger to form new packed keys for each group of buckets.

In step <NUM>, the packed keys are written to at least one NAND page and the device hashmap is updated to point to pages containing the packed keys.

In step <NUM>, the key logger and its associated Bloom filter are cleared, such that the key logger can log new key entries.

Grouping keys that correspond to a group of buckets may be an operation of O(<NUM>) complexity.

Additionally, when adjacent buckets of a bucket group contain just one or two keys, they can end up sharing a packed key NAND page.

For continuity of Put/Delete/Get operations when a key logger is being processed, a device according to an embodiment can implement two or more independent key loggers.

<FIG> is flowchart illustrating a Put operation of a KV store, according to an embodiment.

Referring to <FIG>, in step <NUM>, upon receiving Put command for storing a KV, the KV store writes only the value of the KV to NAND pages.

In step <NUM>, the KV store creates an extent map page that tracks the location of the various NAND pages that contain the value of the KV.

In step <NUM>, the Bloom filter of the key logger is updated. For example, the Bloom filter may be updated such that a pre-determined number of known hash functions may be used to set bits in the Bloom filter bitmap.

In step <NUM>, a slot is selected in the tail pointer table based on the hash of the key of the KV. For example, the tail pointer table can contain K/<NUM> entries, where K = total number of entries in the key logger.

In step <NUM>, the KV store notes the contents of the selected slot of the tail pointer table (i.e., the tail entry) and writes a current offset in the key logger to the same slot of the tail pointer table. Basically, the tail pointer table may be a hashmap of entries that are present in the key logger such that each bucket pointer of the hashmap points to the latest entry that mapped to the bucket. The tail pointer table may reduce the number of slots to be traversed in the key logger to find a particular key that may be indicated to be likely present in the key logger by an associated Bloom filter.

In step <NUM>, the KV store creates a four way tuple of the key, the NAND page containing the extent map, the opcode, and the tail entry pointer and appends the tuple to the key logger. Although <FIG> utilizes a four way tuple of the key, the disclosure is not limited thereto, and different sized tuples of the keys may be used.

In step <NUM>, the KV store updates a hashmap of the KVs, after sufficient number of keys are logged into key logger.

<FIG> is a flowchart illustrating a Delete operation of a KV store, according to an embodiment.

Referring to <FIG>, in step <NUM>, upon receiving a Delete command for deleting a KV from the KV store, the KV store checks a Bloom filter tracking key entries in a key logger for the presence of the key to be deleted.

When the Bloom filter for the key logger suggests a hit for the key in step <NUM>, the KV store traverses a hashmap for keys in the key logger in order to check for the presence of a matching keyname in step <NUM>. For example, if the received Delete command is for deleting a KV for Key33, the KV determines whether the key logger already includes an entry for Key33.

When there is a matching keyname in the key logger in step <NUM>, the operation proceeds to step <NUM>.

However, when the Bloom filter for the key logger does not suggest a hit for the key in step <NUM> or when there is not a matching keyname in the key logger in step <NUM>, the KV store determines if the key is present in the device hashmap in step <NUM>.

When the key is not present in the device hashmap in step <NUM>, the operation ends as there is no key available to delete.

However, when the key is present in the device hashmap in step <NUM>, the operation proceeds to step <NUM>.

In step <NUM>, the KV store creates a Delete key entry and appends it to the key logger. For example, a Delete Key Entry tuple contains an indication of the key to be deleted, an address of the NAND page containing an extent map of the key (e.g., as read from the previous entry of the key in key logger), a delete opcode, and a current entry in tail pointer table.

In step <NUM>, the KV store updates the address of the key entry in tail pointer table to reflect the new Delete key entry.

In step <NUM>, the KV store defers the actual deletion of the key from the device hashmap. That is, the KV store waits to execute the delete operation until a certain threshold is reached within the key logger, as described above with reference to <FIG> and <FIG>.

<FIG> is a flowchart illustrating a Get operation of a KV store, according to an embodiment.

Referring to <FIG>, in step <NUM>, upon receiving a Get command for retrieving a stored KV, the KV store checks a Bloom filter tracking key entries in a key logger for the presence of the key to be retrieved.

When the Bloom filter for the key logger suggests a hit for the key in step <NUM>, the KV store traverses a hashmap for keys in the key logger in order to check for the presence of a matching keyname in step <NUM>. For example, if the received Get command is for retrieving a KV for Key77, the KV determines whether the key logger already includes an entry for Key77.

When there is a matching keyname in the key logger in step <NUM>, the KV store determines whether the matching keyname in the key logger includes an opcode for delete in step <NUM>.

When the matching keyname in the key logger includes an opcode for delete in step <NUM>, the Get operation fails in step <NUM>. For example, if the Get command is for retrieving a KV for Key88, but the key logger already includes an command entry to delete the KV for Key88, then the retrieve operation fails.

However, when the matching keyname in the key logger does not include an opcode for delete in step <NUM>, e.g., the matching keyname includes an opcode for store, the operation proceeds to step <NUM>.

When the Bloom filter for the key logger does not suggest a hit for the key in step <NUM> or when there is not a matching keyname in the key logger in step <NUM>, the KV store determines if the key is present in the device hashmap in step <NUM>.

When the key is not present in the device hashmap in step <NUM>, the Get operation fails in step <NUM>, as there is no key available to retrieve.

In step <NUM>, the KV store reads a NAND page containing an extent map of the key and then reads the value of the key from the NAND page or pages identified by the extent map. As described above, because the device hashmap stores may store multiple keys and extent pointers, which point NAND pages containing extent maps for the keys, on a single NAND page, the KV may be able to quickly identify the NAND page containing an extent map of the key and then read the value of the key from the NAND page or pages identified by the extent map.

<FIG> illustrates a block diagram of an electronic device <NUM> in a network environment <NUM>, according to one embodiment.

The electronic device <NUM> may communicate with the electronic device <NUM> via the server <NUM>. The electronic device <NUM> may include a processor <NUM>, a memory <NUM>, an input device <NUM>, a sound output device <NUM>, a display device <NUM>, an audio module <NUM>, a sensor module <NUM>, an interface <NUM>, a haptic module <NUM>, a camera module <NUM>, a power management module <NUM>, a battery <NUM>, a communication module <NUM>, a subscriber identification module (SIM) <NUM>, or an antenna module <NUM>. In one embodiment, at least one (e.g., the display device <NUM> or the camera module <NUM>) of the components may be omitted from the electronic device <NUM>, or one or more other components may be added to the electronic device <NUM>. In one embodiment, some of the components may be implemented as a single integrated circuit (IC). For example, the sensor module <NUM> (e.g., a fingerprint sensor, an iris sensor, or an illuminance sensor) may be embedded in the display device <NUM> (e.g., a display).

The processor <NUM> may execute, for example, software (e.g., a program <NUM>) to control at least one other component (e.g., a hardware or a software component) of the electronic device <NUM> coupled with the processor <NUM>, and may perform various data processing or computations. As at least part of the data processing or computations, the processor <NUM> may load a command or data received from another component (e.g., the sensor module <NUM> or the communication module <NUM>) in volatile memory <NUM>, process the command or the data stored in the volatile memory <NUM>, and store resulting data in non-volatile memory <NUM>. Additionally or alternatively, the auxiliary processor <NUM> may be adapted to consume less power than the main processor <NUM>, or execute a particular function. The auxiliary processor <NUM> may be implemented as being separate from, or a part of, the main processor <NUM>.

The auxiliary processor <NUM> may control at least some of the functions or states related to at least one component (e.g., the display device <NUM>, the sensor module <NUM>, or the communication module <NUM>) among the components of the electronic device <NUM>, instead of the main processor <NUM> while the main processor <NUM> is in an inactive (e.g., sleep) state, or together with the main processor <NUM> while the main processor <NUM> is in an active state (e.g., executing an application). According to one embodiment, the auxiliary processor <NUM> (e.g., an image signal processor or a communication processor) may be implemented as part of another component (e.g., the camera module <NUM> or the communication module <NUM>) functionally related to the auxiliary processor <NUM>.

The communication module <NUM> may include one or more communication processors that are operable independently from the processor <NUM> (e.g., the AP) and supports a direct (e.g., wired) communication or a wireless communication. According to one embodiment, the communication module <NUM> may include a wireless communication module <NUM> (e.g., a cellular communication module, a short-range wireless communication module, or a global navigation satellite system (GNSS) communication module) or a wired communication module <NUM> (e.g., a local area network (LAN) communication module or a power line communication (PLC) module). A corresponding one of these communication modules may communicate with the external electronic device via the first network <NUM> (e.g., a short-range communication network, such as Bluetooth™, wireless-fidelity (Wi-Fi) direct, or a standard of the Infrared Data Association (IrDA)) or the second network <NUM> (e.g., a long-range communication network, such as a cellular network, the Internet, or a computer network (e.g., LAN or wide area network (WAN)). These various types of communication modules may be implemented as a single component (e.g., a single IC), or may be implemented as multiple components (e.g., multiple ICs) that are separate from each other.

According to one embodiment, commands or data may be transmitted or received between the electronic device <NUM> and the external electronic device <NUM> via the server <NUM> coupled with the second network <NUM>.

According to one embodiment, each component (e.g., a module or a program) of the above-described components may include a single entity or multiple entities. One or more of the above-described components may be omitted, or one or more other components may be added. In this case, the integrated component may still perform one or more functions of each of the plurality of components in the same or similar manner as they are performed by a corresponding one of the plurality of components before the integration. Operations performed by the module, the program, or another component may be carried out sequentially, in parallel, repeatedly, or heuristically, or one or more of the operations may be executed in a different order or omitted, or one or more other operations may be added.

<FIG> illustrates a diagram of a storage system <NUM>, according to an embodiment.

The storage system <NUM> includes a host <NUM> and a storage device <NUM>. Although one host and one storage device is depicted, the storage system <NUM> may include multiple hosts and/or multiple storage devices. The storage device <NUM> may be an SSD, a universal flash storage (UFS), etc. The storage device <NUM> includes a controller <NUM> and a storage medium <NUM> connected to the controller <NUM>. The controller <NUM> may be an SSD controller, a UFS controller, etc. The storage medium <NUM> may include a volatile memory, a non-volatile memory, or both, and may include one or more flash memory chips (or other storage media). The controller <NUM> may include one or more processors, one or more error correction circuits, one or more field programmable gate arrays (FPGAs), one or more host interfaces, one or more flash bus interfaces, etc., or a combination thereof. The controller <NUM> may be configured to facilitate transfer of data/commands between the host <NUM> and the storage medium <NUM>. The host <NUM> sends data/commands to the storage device <NUM> to be received by the controller <NUM> and processed in conjunction with the storage medium <NUM>. As described herein, the methods, processes and algorithms may be implemented on a storage device controller, such as controller <NUM>. The sources and destinations described herein may correspond to elements of the host <NUM> (i.e., processors or applications) and the storage medium <NUM>.

In accordance with the above-described embodiments, a system and method are provided, which allow for the packing of multiple keys together in a single NAND page in order to reduce the worst case collision length in a device hashmap by a packing factor P (i.e., the average number of keys packed per page).

Further, related keys that have no temporal locality may be grouped together to have spatial locality. That is, keys that map to adjacent buckets in a device hashmap can be grouped together even though the keys themselves have no temporal locality.

Accordingly, the number of NAND pages required to store all keys may be reduced, and RAF/WAF may be reduced due to dense key packing. Further, NAND pages may reduce GC when all keys in a page are invalidated.

Accordingly, the present disclosure may significantly reduce GC overheads by a factor of packing density and reduce lengths of hash-map collision chains, which may improve tail latency and lessen the number of NAND page reads that can significantly decrease lookup latencies.

Claim 1:
A key value, KV, store (<NUM>), comprising:
a key logger (<NUM>); and
a processor configured to:
receive a first command for storing a first KV in the KV store (<NUM>),
write a first value of the first KV to a first memory page,
generate an extent map for identifying the first memory page including the first value,
write the extent map to a second memory page,
append an entry for storing the first KV to the key logger (<NUM>), and
update a device hashmap of the KV store (<NUM>) to include a first key of the first KV, upon a threshold being met within the key logger (<NUM>),
wherein the first key of the first KV is stored on a third memory page with at least one other key and includes an extent pointer that points to the second memory page including the extent map, and
wherein the processor is further configured to update the device hashmap by:
collating key entries belonging to a group of adjacent buckets in the device hashmap;
merging existing keys in the device hashmap with entries from the key logger (<NUM>), to form packed keys for the group of adjacent buckets;
writing the packed keys to the third memory page; and
updating the device hashmap to point to the third memory page including the packed keys.