One embodiment provides a storage device. The storage device includes a storage I/O (input/output) logic and a storage device controller. The storage I/O logic is to couple the storage device to a host device, the storage I/O logic to receive a sort-merge command the host device. The a storage device controller is to identify a level N SSTable (sorted string table) file, a corresponding level N index file, a first level N+1 SSTable file and a corresponding first level N+1 index file, in response to the sort-merge command to be received from the host device. The storage device controller is further to perform a sort-merge of the level N SSTable file and the first level N+1 SSTable file to produce a first level N+1 output SSTable file and a first level N+1 output SSTable index file. The level N SSTable file includes at least one level N key-value (KV) pair. The level N+1 SSTable file includes at least one level N+1 key-value (KV) pair. The sort-merge command includes a level N SSTable file index, a value corresponding to a number of SSTable files included in level N+1 and a level N+1 start SSTable file index. The identifying is based, at least in part, on the level N SSTable file index and the level N+1 start SSTable file index.

FIELD

The present disclosure relates to compaction, in particular to, key-value compaction.

BACKGROUND

For Log-Structured Merge (LSM) tree based key-value data storage systems (e.g., RocksDB, LevelDB), data compaction consumes significant overhead in terms of input/output (I/O) operations and computation cycles. Data compaction typically involves loading two sorted files from a storage device into a host device, performing a merge operation (in the host device) that includes discarding any older duplicates, and saving the merged file to the storage device. Data compaction operations can consume more than 90% of processor, memory, and storage I/O resources.

DETAILED DESCRIPTION

Generally, this disclosure relates to key-value compaction. An apparatus, method and/or system are configured to offload at least some key-value compaction operations from a host device to a storage device. The offloaded key-value compaction operations include sort-merge operations. The storage device is configured to store a plurality of key-value pairs configured as a Log-Structured Merge (LSM) tree. The storage device is configured to perform key-value compaction operations in response to a command from the host device. The command may include information related to key-value data to be sorted—merged. Performing the sort-merge operations by the storage device is configured to eliminate a majority of data transfers between the host device and the storage device, reduce host processor utilization and to exploit a media bandwidth within the storage device. Offloading sort-merge operations to the storage device may improve both power consumption and performance.

The host device and/or storage device is configured to define and/or update a data structure that specifies parameters associated with a sort-merge operation. The storage device may include a key-value compaction architecture, e.g., circuitry, configured to implement the sort-merge operation. The architecture is configured to facilitate parallel sort-merge processing for SSTable (sorted string table) files from different levels of the LSM tree. Thus, a majority of data transfers between the host device and the storage device related to compaction may be eliminated. Host device processor resource utilization may be reduced. A relatively higher internal read/write bandwidth of the storage device may be exploited to further enhance performance.

In an embodiment, a storage device includes a storage device controller and a plurality of nonvolatile media. The storage device controller contains a sort-merge logic and a sort-merge circuitry. The sort-merge logic is configured to identify a level N SSTable (sorted string table) file including at least one level N key-value (KV) pair, a corresponding level N index file, a first level N+1 SSTable file including at least one level N+1 key-value (KV) pair and a corresponding first level N+1 index file, in response to receiving a sort-merge command from a host device. The sort-merge circuitry is configured to perform a sort-merge of the level N SSTable file and the first level N+1 SSTable file to produce a first level N+1 output SSTable file and a first level N+1 output SSTable index file. The sort-merge command may include a level N SSTable file index, a value corresponding to a number of SSTable files included in level N+1 and a level N+1 start SSTable file index. The identifying is based, at least in part, on the level N SSTable file index and the level N+1 start SSTable file index.

FIGS. 1A through 1Cillustrate a structure and elements of a Log-Structured Merge (LSM) tree-based key-value storage system, consistent with several embodiments of the present disclosure.FIG. 1Aillustrates a data layout100of a LSM tree.FIG. 1Billustrates a data structure110of an SSTable file112and a corresponding SSTable index file114.FIG. 1Cillustrates an example130sort-merge operation between an SSTable file included in level N and an SSTable file included in adjacent level N+1.FIGS. 1A through 1Cmay be best understood when considered together.

Turning first toFIG. 1A, the LSM tree based key-value storage system (“tree”)100may be stored in a storage device, as described herein. The LSM tree100is configured to store data in a plurality of levels, L0, L1, L2, L3, . . . , Ln. Starting with Level L0, a respective size (i.e., storage capacity) of each subsequent level may be greater than a respective size of each prior level. In one nonlimiting example, a maximum size of level L0 may be about 4 Mebibytes (MiB, 1 MiB=10242bytes), a maximum size of level L1 may be about 10 MiB and the maximum size of level L2 may be about 100 MiB.

At each level L0, L1, L2, L3, . . . , Ln, user data, i.e., a respective plurality of key-value (“KV”) pairs, is stored in sorted string table (SSTable) files, sorted by the keys. Generally, SSTable files are not fragmented. Each level L0, L1, L2, L3, . . . , Ln, except possibly level L0, is configured to include a plurality of SSTable files. Generally, L0 may be maintained in host memory. Each SSTable file at a selected level is configured to include a non-overlapping range of keys. In some embodiments, a maximum number of SSTable files per level may be same for each level. In these embodiments, a size of each SSTable in a level may increase with level. In one nonlimiting example, the maximum number of SSTable files may be 10. In some embodiments, a respective size of an SSTable file included in a level N may be X times larger than the respective size of level N+1 SSTable files, where X is a configurable system parameter. In one nonlimiting example, X may be 10.

The index file114is configured to point to each key122-1,122-2, . . . ,122-mand each value124-1,124-2, . . . ,124-min the SSTable file112. The index file114includes a plurality of key offset-value offset pairs, e.g., key offset-value offset pair125. For example, key offset-value offset pair125includes a key offset126and a value offset128. Continuing with this example, key offset126is configured to provide an offset to, e.g., point to, key122-1and value offset128is configured to provide an offset to, e.g., point to, value124-1that corresponds to key122-1.

In operation, new KV pairs are written to a write ahead log, and may then be sort-merged to the lowest level (e.g., level L0) when the write ahead log is full. In other words, the new KV pairs are sorted according to respective keys prior to being written to level L0 of the LSM tree100. When there is no available space left in L0, a sort-merge operation is triggered. The SSTable file in L0 may then be sorted-merged to L1, while eliminating KV pairs in L1 that have corresponding more current KV pairs in L0. In other words, the eliminated KV pair and corresponding current KV pair may each have a same key. Storage, e.g., memory, space that was occupied by L0 may then be freed, so that new KV pairs may be stored in level L0. The new KV pairs may be received from, for example, from the host device. When there is no space available in L1, a sort-merge operation from L1 to L2 is performed and so on for each level of the LSM tree100.

FIG. 1Cillustrates an example130sort-merge operation between an SSTable file included in a level N and an SSTable file included in an adjacent level N+1. In this example, SSTable file X132in level N is selected to be sorted merged into level N+1 (and SSTable file Y134). A key range of SSTable file X132overlaps with a key range of SSTable file Y134. The SSTable file X132and SSTable file Y134may be loaded into a memory. A linear sort-merge operation may then be performed, and the sort-merged result may be stored in a new SSTable file Y136.

Thus, user data including a plurality of KV pairs may be configured as a Log-Structured Merge (LSM) tree. SSTable files may be updated and SSTable files in adjacent levels may be sort-merged, as described herein.

FIG. 2illustrates a functional block diagram of a system200that includes a key-value compaction system consistent with several embodiments of the present disclosure. System200includes a host device202and a storage device204. The storage device204may be coupled to and/or included in host device202. The host device202is configured to provide a command206and/or data208to the storage device204.

Host device202may include, but is not limited to, a mobile telephone including, but not limited to a smart phone (e.g., iPhone®, Android®-based phone, Blackberry®, Symbian®-based phone, Palm®-based phone, etc.); a wearable device (e.g., wearable computer, “smart” watches, smart glasses, smart clothing, etc.) and/or system; an Internet of Things (IoT) networked device including, but not limited to, a sensor system (e.g., environmental, position, motion, etc.) and/or a sensor network (wired and/or wireless); a computing system (e.g., a server, a workstation computer, a desktop computer, a laptop computer, a tablet computer (e.g., iPad®, GalaxyTab® and the like), an ultraportable computer, an ultramobile computer, a netbook computer and/or a subnotebook computer; etc. Host device202includes a host processor circuitry210, a host memory circuitry214and a host communication circuitry216. For example, host processor circuitry210may correspond to a single core or a multi-core general purpose processor, such as those provided by Intel® Corp., etc. Host device202may further include an operating system (OS)218and one or more applications, e.g., application220. Application220may be configured to generate and/or utilize user data that may be stored as an LSM tree, as described herein. Host device202may further include an LSM logic222. LSM logic222may be coupled to and/or included in OS218and/or application220. During operation, host device202may include a write ahead log, e.g., write ahead log223.

Storage device204may include, but is not limited to, a solid-state drive (SSD), a hard disk drive (HDD), a network attached storage (NAS) system, a storage area network (SAN) and/or a redundant array of independent disks (RAID) system, etc. Storage device204includes a storage device controller208and a plurality of nonvolatile (NV) media244-1,244-2, . . . ,244-p. NV media244-1,244-2, . . . ,244-pcorresponds to a plurality of storage media that does not require power to maintain the state of data stored in the storage medium.

In one embodiment, each NV media244-1,244-2, . . . ,244-pmay be a block addressable memory device, such as those based on NAND or NOR technologies. Each NV media244-1,244-2, . . . ,244-pmay also include future generation nonvolatile devices, such as a three dimensional crosspoint memory device, or other byte addressable write-in-place nonvolatile memory devices. In an embodiment, each NV media244-1,244-2, . . . ,244-pmay include, but is not limited to, a NAND flash memory (e.g., a Triple Level Cell (TLC) NAND, multi-threshold level NAND flash memory, or any other type of NAND (e.g., Single Level Cell (SLC), Multi Level Cell (MLC), Quad Level Cell (QLC), etc.)), NOR memory, NOR flash memory, solid state memory (e.g., planar or three Dimensional (3D) NAND flash memory or NOR flash memory), storage devices that use chalcogenide phase change material (e.g., chalcogenide glass), byte addressable nonvolatile memory devices, ferroelectric memory, silicon-oxide-nitride-oxide-silicon (SONOS) memory, polymer memory (e.g., ferroelectric polymer memory), byte addressable random accessible 3D crosspoint memory, ferroelectric transistor random access memory (Fe-TRAM), anti-ferroelectric memory, magnetoresistive random access memory (MRAM), memory that incorporates memristor technology, resistive memory including the metal oxide base, the oxygen vacancy base and the conductive bridge Random Access Memory (CB-RAM), single or multi-level phase change memory (PCM, PRAM), resistive memory, ferroelectric memory (F-RAM, FeRAM), spin-transfer torque memory (STT), spin transfer torque (STT)-MRAM, a spintronic magnetic junction memory based device, a magnetic tunneling junction (MTJ) based device, a DW (Domain Wall) and SOT (Spin Orbit Transfer) based device, a thyristor based memory device, thermal assisted switching memory (TAS), millipede memory, floating junction gate memory (FJG RAM), magnetic tunnel junction (MTJ) memory, electrochemical cells (ECM) memory, binary oxide filament cell memory, interfacial switching memory, battery-backed RAM, ovonic memory, nanowire memory, electrically erasable programmable read-only memory (EEPROM), etc., or a combination of any of the above, or other memory. In some embodiments, NV media244-1,244-2, . . . ,244-pmay refer to the die itself and/or to a packaged memory product. In some embodiments, the byte addressable random accessible 3D crosspoint memory may include a transistor-less stackable cross point architecture in which memory cells sit at the intersection of words lines and bit lines and are individually addressable and in which bit storage is based on a change in bulk resistance.

Storage device controller208includes a device processor circuitry230, a device buffer circuitry232, a storage I/O (input/output) logic238(e.g., a host protocol logic) and a plurality of media controller circuitries234-1,234-2, . . . ,234-p. Storage device controller208may further include a sort-merge logic236. Storage device204and/or storage device controller208may further include a sort-merge circuitry237. Storage device204and/or storage device controller208may include an indirection table240, as described herein. Sort-merge circuitry237may be coupled to and/or included in the storage device controller208. Sort-merge logic236may be coupled to and/or included in sort-merge circuitry237. Device buffer circuitry232may include volatile random-access memory, e.g., dynamic random access memory (DRAM) and/or static random access memory (SRAM), etc. Device buffer circuitry232may be configured to store one or more of a plurality of input buffers250, a plurality of intermediate buffers252and/or an output buffer254, as described herein. Device buffer circuitry232may be further configured to store a command buffer248. Each media controller circuitry234-1,234-2, . . . ,234-pis configured to retrieve stored data from device buffer circuitry232and store the retrieved data to a respective NV media244-1,244-2, . . . ,244-p. Device processor circuitry230may include, but is not limited to, a microcontroller, an application-specific integrated circuit (ASIC), a programmable logic device (PLD), a complex PLD, etc.

Storage I/O logic238is configured to couple the storage device204to the host device202. An interface between the host device202and the storage device204may be termed a “frontend”. An interface between the storage device controller208(e.g., the media controllers) and the NV media circuitry may be termed “backend”. The frontend may comply and/or be compatible with one or more interface protocols including, but not limited to, PCIe (Peripheral Component Interconnect Express), NVMe (Non-Volatile Memory Express), SCSI (Small Computer System Interface), AHCI (Advance Host Controller Interface), SATA (Serial ATA (Advanced Technology Attachment)), PATA (Parallel ATA), etc. The backend may comply and/or be compatible with one or more protocols, e.g., ONFI (Open NAND Flash Interface), JEDEC (Joint Electron Device Engineering Council) standard JESD230C (NAND Flash Interface Interoperability), etc.

In operation, storage device204is configured to receive command(s)206and/or data208from host device202. For example, storage I/O logic238may be configured to receive a sort-merge command from the host device202, as described herein. The command(s)206and/or data208may be provided to storage device204by OS218and/or application220via LSM logic222. The data208includes user data and thus may include one or more KV pairs. In one example, the data208may include a plurality of KV pairs corresponding to the write ahead log223, as described herein. In another example, the data208may include a plurality of KV pairs sorted in an SSTable file, as described herein. Continuing with this example, the data may further include a corresponding index file, as described herein. Device communication interface circuitry238may be configured to receive the data208. The data208may then be stored in device buffer circuitry232prior to being stored in NV media244-1,244-2, . . . , and/or244-p.

In one nonlimiting example, host device202, e.g., application220, may be configured to receive, store and/or retrieve one or more records related to a database of user information, i.e., user data. The user data may be stored in an LSM tree based key-value data storage system that includes a plurality of levels L0, L1, . . . , Ln, e.g., LSM tree100ofFIG. 1A.

Application220, via LSM logic222, may be configured to generate a respective KV pair corresponding to each record. Each new KV pair may then be appended to the write ahead log223. The write ahead log223is configured to provide atomicity and durability in the data storage system. When the write ahead log223is full (e.g., contains a number of KV pairs equal to an SSTable file), a sort operation may be triggered configured to sort the KV pairs by key. The sort operation may be performed by LSM logic222or, for example, sort-merge logic236. Thus, a corresponding SSTable file may be generated. LSM logic222and/or sort-merge logic236may be further configured to generate a corresponding SSTable index file and to add a corresponding entry to an indirection table, e.g., indirection table240, as described herein. The SSTable file may then correspond to level L0 of the LSM tree. A sort-merge operation may then be triggered.

The SSTable file in level L0 may then be sorted-merged into level L1. KV pairs in level L1 that have corresponding (i.e., same key) more current KV pairs in level L0 may be replaced with KV pairs in level L0. Storage space, e.g., NV media, that was occupied by level L0 may then be freed, so that new KV pairs may be stored in level L0. When there is no space available in level L1, a sort-merge operation from level L1 to level L2 may be performed. Similarly, when there is no space available in level L2, a sort-merge operation from level L2 to level L3 may be performed and so on, to level Ln.

The number of SSTable files per level is a system parameter that may be preconfigured. Generally, Level L0 may be configured to include one SSTable file. Levels L1, L2, . . . , Ln may then each include at least one SSTable file. In some embodiments, the number of SSTable files may be the same for each level and a respective size of each SSTable file may increase with level. In some embodiments, the number of SSTable files may increase with level. For example, the size of the SSTable files may be the same across the levels. In another example, the size of the SSTable files may increase with level. In some embodiments, the number of levels (i.e., n+1) may configurable. The number of levels may be related to a storage capacity (i.e., NV media capacity) of the storage device204.

The indirection table, e.g., indirection table240, is configured to include SSTable file information for each SSTable file included in an LSM tree based KV data storage system and stored in, e.g., storage device204and NV media244-1,244-2, . . . , and/or244-p. The indirection table240may be stored in device buffer circuitry232and/or NV media244-1,244-2, . . . , and/or244-p. The indirection table240may be updated by LSM logic222and/or sort-merge logic236when a new SSTable file is generated and/or an SSTable file (and/or corresponding file index) is modified.

Table 1 illustrates one example of the contents of indirection table240. The indirection table240is configured to include SSTable file information that may then be used by storage device204for performing corresponding sort—merge operations, as described herein. The indirection table240is configured to include SSTable file information for each SSTable file and each level of the corresponding LSM tree. The indirection table240is configured to include a number of SSTable File Indexes that corresponds to a number of SSTable files included in the corresponding LSM tree.

Table 1 illustrates one example SSTable file indirection table240.

TABLE 1SSTable File Index (r)SSTable File Information0SSTableFileInfo[0]1SSTableFileInfo[1]. . .. . .RSSTableFileInfo[R]
Table 1 includes a number, R+1, SSTable file indexes and an array SSTableFileInfo that includes the number, R+1, array elements. Each SSTable file index, r, is configured to identify a corresponding SSTableFileInfo array element associated with that SSTable file index, r. Each SSTableFileInfo array element (i.e., SSTableFileInfo[r]) is configured to include information associated with a corresponding SSTable file. The SSTableFileInfo array is configured to include SSTable file information for each SSTable file included in the corresponding LSM tree.

Table 2 illustrates the contents of a respective array element of SSTableFileInfo, i.e., the contents of SSTableFileInfo[r]. Each SSTableFileInfo[r] array element corresponds to a respective SSTable file in the LSM tree stored in the storage device204.

TABLE 2SSTableFileInfoSSTable File IndexSSTable File Start LBASSTable File LBA LengthSSTable Index File Start LBASSTable Index File LBA LengthNumber of KV pairs in this SSTable FileSSTable File Status

SSTable File Index is a unique identifier (ID) for indexing this (i.e., associated) SSTable file. The SSTable File Index of Table 2 corresponds to the SSTable File Index of Table 1. The two SSTable file indexes may be utilized for validation and/or data integration. Each SSTable file index may be calculated as: SSTable file index=Level*(Maximum number of SSTable Files per Level)+Sequence Number. Sequence number corresponds to a location, in a sequence of SSTable files in a level, this SSTable file is positioned. SSTable File Start LBA (Logical Block Address) corresponds to a start LBA of this SSTable file. SSTable File LBA Length corresponds to a size, in logical blocks, of this SSTable file. SSTable Index File Start LBA corresponds to a start LBA of this SSTable index file. SSTable Index File LBA Length corresponds to a size in logical blocks of the SSTable index file. Number of KV pairs in this SSTable File corresponds to the number of KV pairs in this SSTable file. SSTable File Status is configured to indicate whether this SSTable file is currently open or closed. “Open” corresponds to an SSTable file that may be read from or written to as part of an ongoing sort-merge operation. “Closed” corresponds to an SSTable file that is not being read from or written to as part of the sort-merge operation. For example, an SSTable file in level N+1 may be open during sort-merge operations while the SSTable file includes less than a maximum number of KV pairs and may be closed when the SSTable file reaches the maximum number of KV pairs.

Thus, an indirection table, e.g., indirection table240, that includes an array of SSTable file information, may be updated by LSM logic222and/or sort-merge logic236.

In response to a level becoming full, e.g., due to operation of application220and/or LSM logic222, a sort-merge operation may be triggered. A level may be full when a maximum number of SSTable files each includes a maximum number of KV pairs. In an embodiment, LSM logic222may be configured to generate a sort-merge command and to provide the sort-merge command to the storage device204. The sort-merge command may be received by sort-merge logic236. Sort-merge logic236may then be configured to initiate sort-merge operations of sort-merge circuitry237based, at least in part, on the received sort-merge command.

The sort-merge command may be a vendor specific command or a standardized command. For example, the sort-merge command may comply and/or be compatible with one or more storage device interface specifications and/or protocols, e.g., NVMe (Non-Volatile Memory Express), SCSI (Small Computer System Interface), AHCI (Advance Host Controller Interface), SATA (Serial ATA (Advanced Technology Attachment)), PATA (Parallel ATA), etc. The sort-merge command is configured to instruct the storage device204to sort-merge a SSTable file included in level N with one or more SSTable files included in Level N+1. Level N+1 may then include one or more resulting new SSTable files that include one or more KV pairs from the SSTable in Level N.

Table 3 illustrates a command structure for the sort-merge command, consistent with several embodiments of the present disclosure. The sort-merge command, as illustrated in Table 3, includes a plurality of parameters in a corresponding plurality of fields. A first field is configured to include an SSTable File Index in Level N. A second field is configured to include a number of SSTable Files in Level N+1. A third field is configured to include a Start SSTable File Index in Level N+1. A fourth field is configured to include a command identifier (CMD ID) and a fifth field is configured to include a sort-merge command opcode.

TABLE 3SSTable File Index in Level NNumber of SSTable Files in Level N + 1Start SSTable File Index in Level N + 1CMD IDOpcode

The following description of Table 3 may be best understood when considered in combination with Tables 1 and 2. The SSTable File Index in Level N is configured to identify the SSTableFileInfo array element that corresponds to the SSTable file in Level N that is to be sort-merged with one or more SSTable files included in Level N+1. The number of SSTable Files in Level N+1 corresponds to the number of SSTable files in Level N+1 that are to be sort-merged with the identified SSTable file in Level N. The Start SSTable File Index in Level N+1 is configured to identify the first (i.e., start) SSTableFileInfo array element in the SSTableFileInfo array that corresponds to the first SSTable file in Level N+1. It may be appreciated that Number of SSTable Files in Level N+1 and Start SSTable File Index in Level N+1, together, are configured to identify all of the one or more SSTable files in Level N+1 that are to be sort-merged with the identified SSTable file in Level N.

In some situations, a key range of the SSTable file in level N may overlap a plurality of SSTable files in level N+1. A vendor specific sort-merge command may further include a field configured to indicate the number of overlapped SSTable files in level N+1. The overlapped SSTable files may then be loaded to the sort-merge circuitry237in sequential order and sort-merged with the SSTable file in level N. The sort-merged results may then be stored in new SSTable files in level N+1 and the “old” SSTable files in level N+1 may be discarded.

CMD ID is configured to indicate, e.g., select, one or more options associated with the sort-merge operation. For example, a CMD ID may be configured to select ascending or descending order of keys for the sort-merge operation. In another example, a CMD ID may be configured to indicate a value type, e.g., double, integer or string. In another example, a CMD ID may be configured to indicate a size of the value, e.g., 4 bytes, 8 bytes, etc. In another example, the CMD ID may be configured to indicate big endian or little endian control.

In some embodiments, CMD ID may be configured to indicate that the sort-merge operation should be modified to, at least initially, load only the keys and not the corresponding values. A corresponding value may then be loaded only if the corresponding value is used in the sort-merge operation. For example, if two keys (one from the SSTable in Level N and one from an SSTable in Level N+1) are the same, the KV pair associated with Level N+1 may be discarded. In other words, the corresponding KV pair associated with Level N may be newer than the KV pair associated with Level N+1. Thus, loading the value of the Level N+1 KV pair, that will be discarded, may be avoided.

Thus, a sort-merge command may be provided to the storage device204(and, e.g., sort-merge logic236) by the host device202(and, e.g., LSM logic222), in response to a level, e.g., Level N, of an LSM tree becoming full. Storage device204, storage device controller208and/or, e.g., sort-merge logic236and sort-merge circuitry237, may then be configured to perform the sort-merge operations based, at least in part, on the received sort-merge command.

FIG. 3illustrates one example key-value compaction architecture300consistent with several embodiments of the present disclosure. Key-value compaction architecture300is one example of sort-merge circuitry237ofFIG. 2. In some embodiments, sort-merge circuitry237may include one key-value compaction architecture300. In some embodiments, sort-merge circuitry237may include a plurality of key-value compaction architectures300. The plurality of key-value compaction architectures300may perform a plurality of sort-merge operations in parallel (e.g., on different levels of the LSM tree). Performing the plurality of sort-merge operations in parallel is configured to exploit a relatively higher read/write bandwidth of the storage device204compared to the host device202. Thus, an effective operating speed associated with the sort-merge operations may be increased and a corresponding a time duration associated with the sort-merge operations may be decreased.

Example key-value compaction architecture300includes a command buffer320. Example300further includes a plurality of input buffers322,324,326,328,330and332, a plurality of intermediate buffers304,306,308and310and an output buffer316. Example300includes sort-merge logic302, a multiplexer (MUX)314and comparator circuitry312. Command buffer320corresponds to command buffer248ofFIG. 2and is configured to store a sort-merge command received from a host device, e.g., host device202. The input buffers322,324,326,328,330and332are examples of input buffers250ofFIG. 2. The intermediate buffers are examples of intermediate buffers252ofFIG. 2. The output buffer316corresponds to output buffer254ofFIG. 2. Example300further includes an output SSTable file340and an output SSTable index342. The output SSTable file340and output SSTable index342may be stored in NV media244-1,244-2, . . . , and/or244-pofFIG. 2.

A first input buffer322is configured to store an SSTable Index File in Level N. A second input buffer324is configured to store a first SSTable Index File 0 in Level N+1. A third input buffer326is configured to store a second SSTable Index File 1 in Level N+1. In some situations, the third input buffer326may not be used. For example, if only one SSTable file in Level N+1 is involved in the sort-merge operation, the third input buffer326may not be used. The second input buffer324and third input buffer326are configured to operate as ping pong buffers allowing one buffer to be loading while the other buffer is being operated on. Similar to the third input buffer326, in some situations, the sixth input buffer332may not be used (i.e., if only one SSTable file in Level N+1 is involved in the sort-merge operation).

A fourth input buffer328is configured to store an SSTable File in Level N. A fifth input buffer330is configured to store a first SSTable File 0 in Level N+1. A sixth input buffer332is configured to store a second SSTable File 1 in Level N+1. In other words, the fifth input buffer330and sixth input buffer332are configured to operate as ping pong buffers allowing one buffer to be loading while the other buffer is being operated on.

In operation, sort-merge circuitry237, e.g., example key-value compaction architecture300, is configured to receive a sort-merge command from a host device, e.g., host device202. The sort-merge command may be stored in the command buffer320. Sort-merge logic302may then be configured to decode the sort-merge command320. The sort-merge command320includes an SSTable File Index in Level N, a number of SSTable Files in Level N+1, a Start SSTable File Index in Level N+1 and a sort-merge command opcode and may include a command identifier, as described herein. Sort-merge logic302may then retrieve, e.g., read, the corresponding respective SSTableFileInfo array elements that corresponds to each SSTable File Index from indirection table240. For example, the indirection table240may be retrieved from device buffer circuitry232and/or NV media244-1,244-2, . . . , and/or244-p.

The sort-merge logic302is configured to load the SSTable index file in level N to the first input buffer322and the first SSTable index file in level N+1 to the second input buffer (SSTable Index File 0 in Level N+1)324. The SSTable index file in level N and the first SSTable index file in level N+1 may be identified based, at least in part, on the SSTableFileInfo retrieved from indirection table240. The sort-merge logic302is configured to load the SSTable file in level N to the fourth input buffer328and the first SSTable file in level N+1 to the fifth input buffer (SSTable File 0 in Level N+1)330. The SSTable file in level N and the first SSTable file in level N+1 may be identified based, at least in part, on the SSTableFileInfo retrieved from indirection table240. Sort-merge operations may then be initiated.

In some situations, the number of SSTable files in Level N+1 may be greater than one. In some situations (e.g., when the SSTable file in Level N overlaps a plurality of SSTable in Level N+1), the SSTable file in Level N may be sort-merged with a plurality of the SSTable files in Level N+1. The sort-merge logic302may then be configured to load the second (i.e., next) SSTable index file in level N+1 to the third input buffer (SSTable Index File 1 in Level N+1)326. The second SSTable index file in level N+1 may be identified based, at least in part, on the SSTableFileInfo retrieved from indirection table240. The sort-merge logic302is configured to load the second SSTable file in level N+1 to the sixth input buffer (SSTable File 1 in Level N+1)332. The second SSTable file in level N+1 may be identified based, at least in part, on the SSTableFileInfo retrieved from indirection table240.

The index files (e.g., index file114ofFIG. 1A) pointed to by the SSTable file indexes include pointers (i.e., offsets) to each key and corresponding value of each KV pair included in a respective SSTable file. The sort-merge logic302is configured to sequentially load each Level N valid KV pair from the fourth input buffer328to a first intermediate buffer304, i.e., to KV pair buffer A304. As used herein, “valid KV pair” is a most recent copy of the KV pair associated with the corresponding key. For example, a host device may write the same key multiple times via, for example, a PUT(key, value) operation, or delete an existing key via DELETE(key) operation. These operations may then generate stale copies of the KV pairs. The sort-merge logic302is further configured to sequentially load each Level N+1 valid KV pair from the fifth input buffer330(or sixth input buffer332) to a second intermediate buffer306, i.e., to KV pair buffer B306. The sort-merge logic302is further configured to sequentially load each key from a respective KV pair to a corresponding key buffer308,310. In other words, the sort-merge logic302is configured to load a corresponding key from the fourth input buffer (i.e., SSTable file in Level N)328to the third intermediate buffer (i.e., Key buffer A)308and a corresponding key from the fifth (or sixth) input buffer (i.e., SSTable file 0 (or 1) in Level N+1)330(or332) to the fourth intermediate buffer (i.e., Key buffer B)310.

The third and fourth intermediate buffers308,310are coupled to respective inputs to comparator circuitry312. Comparator circuitry312is configured to compare the two keys stored in key buffers A308and B310. An output of comparator circuitry312is coupled to a selector input of MUX314. The first and second intermediate buffers (i.e., KV pair buffer A and KV pair buffer B)304,306are coupled to respective inputs to MUX314. MUX314is configured to couple an output of MUX314to a selected MUX input based on a MUX314selector input, i.e., an output (i.e., comparison result) of comparator circuitry312. If the Level N key (stored in Key buffer A308) is less than the Level N+1 key (stored in Key buffer B310), then the MUX314is configured to select the Level N key-value pair (stored in KV pair buffer A304). If the Level N key (stored in Key buffer A308) is greater than the Level N+1 key (stored in Key buffer B310), then the MUX314is configured to select the Level N+1 key-value pair (stored in KV pair buffer B306). If the Level N key (stored in Key buffer A308) is equal to the Level N+1 key (stored in Key buffer B310), then the MUX314is configured to select the Level N key-value pair (stored in KV pair buffer A304. In other words, keys that are equal may correspond to a newer corresponding value in the KV pair in Level N compared to the corresponding value associated with that key in the KV pair in Level N+1. Sort-merge logic302is configured to store the output of MUX314to KV pair output buffer316.

Sort-merge logic302is configured to update a corresponding SSTable index file in Level N+1 for each new key-value pair written to the SSTable file in level N+1. For example, a new entry may be created in the corresponding SSTable index file in level N+1. The new entry is configured to include a key offset and a value offset, as described herein. Sort-merge logic302may be further configured to update the indirection table240, e.g., corresponding SSTable file LBA length, SSTable index file start LBA, SSTable index file LBA length and/or number of KV pairs in this SSTable file.

If the compared keys were not equal, the first or second intermediate buffer304or306corresponding to the selected KV pair may then be loaded with a corresponding next KV pair and the first or second intermediate buffer304or306corresponding to the not selected KV pair may then retain the not selected KV pair. If the compared keys were equal, the KV pair associated with the unselected KV pair (e.g., in Level N+1) may be discarded and each of the first and second buffers304and306may be loaded with a respective next KV pair. Each key buffer A308and key buffer B310may similarly be loaded with a respective key.

The loading of KV pairs into intermediate buffers304,306, the loading of corresponding keys into key buffers308,310, comparison of keys and selecting the KV pair associated with a same or smaller key operations may be repeated for each KV pair included in SSTable file in Level N328. The sort-merge logic302may then be configured to switch to a next SSTable file in Level N+1. For example, if a current SSTable file in Level N+1 is stored in the fifth input buffer (i.e., SSTable File 0 in Level N+1)330, the next SSTable file in Level N+1 may correspond to the SSTable file stored in the sixth input buffer (i.e., SSTable File 1 in Level N+1) 332. A new next Level N+1 SSTable file may then be loaded to the fifth input buffer330. Conversely, if a current SSTable file in Level N+1 is stored in the sixth input buffer (i.e., SSTable File 1 in Level N+1)332, the next SSTable file in Level N+1 may correspond to the SSTable file stored in the fifth input buffer (i.e., SSTable File 0 in Level N+1)330. A new next Level N+1 SSTable file may then be loaded to the sixth input buffer332. Thus, the fifth and sixth input buffers330,332may correspond to “ping pong” buffers.

Similarly, if a current SSTable index file in Level N+1 is stored in the second input buffer (i.e., SSTable Index File 0 in Level N+1)324, the next SSTable index file in Level N+1 may correspond to the SSTable index file stored in the third input buffer (i.e., SSTable Index File 1 in Level N+1)326. A new next Level N+1 SSTable index file may then be loaded to the second input buffer324. Conversely, if a current SSTable index file in Level N+1 is stored in the third input buffer (i.e., SSTable Index File 1 in Level N+1)326, the next SSTable index file in Level N+1 may correspond to the SSTable index file stored in the second input buffer (i.e., SSTable Index File 0 in Level N+1)324. A new next Level N+1 SSTable index file may then be loaded to the third input buffer326. Thus, the second and third input buffers324,326may similarly correspond to “ping pong” buffers.

The operations may be repeated for each SSTable file in Level N+1. When the KV pair output buffer316includes a target number of sorted merged KV pairs, e.g., corresponding to a maximum size of an SSTable file in Level N+1, the contents of KV pair output buffer316may be written to a new SSTable file in level N+1340. Similarly, the corresponding SSTable index file may be written to a corresponding SSTable index file in Level N+1342. The indirection table240may then be updated to include an array element corresponding to the new SSTable file in Level N+1. The indirection table240may be further updated to delete the array element corresponding to the SSTable file in Level N after all of the SSTable files in Level N+1 have been sort-merged with the SSTable file in Level N.

In some situations, Level N may include a plurality of SSTable files. The example key-value compaction architecture300may be configured to repeat the operations, as described herein, for each SSTable file in Level N.

In some situations, during comparison operations, a first key corresponding to a last KV pair in a first SSTable file in Level N or in Level N+1 may be compared to a second key (in a second SSTable file in Level N+1 or Level N) that is not associated with a last KV pair. In other words, the second SSTable file may include one or more KV pairs following the second key. In these situations, the remaining KV pairs that have not been compared may be written to the KV pair output buffer316. In other words, since there are not keys to compare to, the sort-merge operation may be completed for these SSTable files by storing the remaining KV pairs form the second SSTable file. The use of “first” and “second” in this context is merely to differentiate between the two keys and two SSTable files and do not necessarily indicate order.

In some embodiments, rather than using files, e.g., SSTable index files and/or SSTable files, the KV pairs and corresponding pointers to keys and values may be defined by logical block addresses (LBAs).

In some embodiments, sort-merge logic302may be configured to initially load the SSTable index files to respective input buffers322,324and/or326and only respective keys to intermediate buffers308and310. In other words, initially, sort-merge logic302may not load the values corresponding to the keys. Corresponding values may be read later, if warranted. For example, if the keys being compared are equal, then the value associated with the key from the SSTable file included in Level N+1 may not be loaded since it is discarded.

Turning again toFIG. 2, storage device controller208includes a plurality of media controllers234-1,234-2, . . . ,234-pand storage device204includes a corresponding plurality of NV media244-1,244-2, . . . ,244-p, as described herein. As further described herein, in some embodiments, sort-merge circuitry237may include a plurality of instances of example key-value compaction architecture300. For example, a storage device, e.g., storage device204, may include 4, 8, 16 or more media controller channels, i.e., media controller to corresponding NV media links, e.g., backend. The number of media controller channels may be related to desired performance. In one nonlimiting example, the number of media channels may be eight. Continuing with this example, the eight channels may operate, for example, at a maximum frequency of 400 MHz (Megahertz) in DDR (double data rate) mode and may thus realize up to 800 MB/s BW (i.e., 800 Megabytes per second bandwidth) per channel for a total of 6.4 GB/s (Gigabytes per second). The host device202BW (bandwidth) may be limited by the interface between the host device202and the storage device (i.e., the frontend)204by a number of lanes. A maximum realizable BW may then be approximately 3.2 GB/s after all the overheads are subtracted. Typically, the backend (i.e., the media controller to NV media interface) is operated slower than the frontend (i.e., the host device202to storage device204interface). When the storage device204is performing sort-merge operations as described herein, performance may be enhanced by operating the backend faster than the frontend. Once the sort-merge operations are completed, the backend can be reverted back to slower frequency for power savings.

In another example, at least some storage devices may have a higher read bandwidth relative to a host device, e.g., a storage device may have a read bandwidth that is 2 to 4 times the read bandwidth of the host device. Performing the sort-merge operations on the storage device may reduce the host software stack latency on a file system and device driver, further improving speed. It is contemplated that a performance increase of at least 2× relative to performing sort-merge operations by the host device may be achievable.

Thus, performing the sort-merge operations by the storage device is configured to eliminate a majority of data transfers between the host device and the storage device, reduce host processor utilization and to exploit a media bandwidth within the storage device. Offloading sort-merge operations to the storage device may improve both power consumption and performance.

FIG. 4is a flowchart400of SSTable-related operations according to various embodiments of the present disclosure. In particular, the flowchart400illustrates generating an SSTable file and corresponding index file and triggering compaction (i.e., sort-merge) operations on a storage device. The operations may be performed, for example, by host device202, e.g., LSM logic222, storage device204and/or storage device controller208, e.g., sort-merge logic236, ofFIG. 2.

Operations of this embodiment may begin with generating a new KV pair based, at least in part, on user data at operation402. Operation404may include appending the new KV pair to a write ahead log. Whether the write ahead log is full may be determined at operation406. If the write ahead log is not full, program flow may proceed to operation402.

If the write ahead log is full, the write ahead log may be sorted at operation408. For example, LSM logic222may be configured to sort the write ahead log. An SSTable file and index file corresponding to the sorted write ahead log may be generated at operation410. An indirection table may be updated at operation412. Updating the indirection table is configured to add an array element corresponding to the new SSTable file. Compaction operations may be triggered at operation414. For example, compaction operations may be triggered by providing a sort-merge command to the storage device, as described herein. The sort-merge operations are configured to sort-merge the new SSTable file into an LSM tree. Whether Level N is full may be determined at operation416. If Level N is not full, program flow may proceed to operation402. If Level N is full, a sort-merge command may be provided to a storage device at operation418. Program flow may then continue at operation420.

Thus, an SSTable file and corresponding index file may be generated and compaction operations by a storage device may be triggered.

FIG. 5is a flowchart500of sort-merge operations according to various embodiments of the present disclosure. In particular, the flowchart500illustrates performing a sort-merge operation of a level N SSTable file and a level N+1 SSTable file in response to a sort-merge command from a host device. The operations may be performed, for example, by storage device204and/or storage device controller208, e.g., sort-merge logic236and/or sort-merge circuitry237, ofFIG. 2.

Operations of this embodiment may begin with receiving a sort-merge command from a host device at operation502. A level N SS table file and corresponding level N index file may be identified at operation504. A first level N+1 SS table file and a corresponding first level N+1 index file may be identified at operation506. In some embodiments, a second level N+1 SSTable file and a corresponding second level N+1 index file may be identified at operation508. The SSTable files may be identified based, at least in part, on the received sort-merge command. A sort-merge of the level N SSTable file and the first level N+1 SS table file may be performed to produce a first level N+1 output SSTable file and a first level N+1 SSTable index file at operation510. In some embodiments, a sort-merge of the level N SS table file and the second level N+1 SS table file may be performed to produce a second level N+1 output SSTable file and a second level N+1 SSTable index file at operation512. An indirection table may be updated at operation514. Program flow may then continue at operation516.

Thus, a sort-merge of a level N SSTable file and one or more level N+1 SSTable file(s) may be performed in response to a sort-merge command from a host device.

While the flowcharts ofFIGS. 4 and 5illustrate operations according various embodiments, it is to be understood that not all of the operations depicted inFIGS. 4 and 5are necessary for other embodiments. In addition, it is fully contemplated herein that in other embodiments of the present disclosure, the operations depicted inFIGS. 4 and/or 5and/or other operations described herein may be combined in a manner not specifically shown in any of the drawings, and such embodiments may include less or more operations than are illustrated inFIGS. 4 and 5. Thus, claims directed to features and/or operations that are not exactly shown in one drawing are deemed within the scope and content of the present disclosure.

“Circuitry,” as used in any embodiment herein, may comprise, for example, singly or in any combination, hardwired circuitry, programmable circuitry, state machine circuitry, logic and/or firmware that stores instructions executed by programmable circuitry. The circuitry may be embodied as an integrated circuit, such as an integrated circuit chip. In some embodiments, the circuitry may be formed, at least in part, by the processors210,230executing code and/or instructions sets (e.g., software, firmware, etc.) corresponding to the functionality described herein, thus transforming a general-purpose processor into a specific-purpose processing environment to perform one or more of the operations described herein. In some embodiments, the various components and circuitry of the memory controller circuitry or other systems may be combined in a system-on-a-chip (SoC) architecture.

The foregoing provides example system architectures and methodologies, however, modifications to the present disclosure are possible. The processor may include one or more processor cores and may be configured to execute system software. System software may include, for example, an operating system. Device memory may include I/O memory buffers configured to store one or more data packets that are to be transmitted by, or received by, a network interface.

The operating system (OS)218may be configured to manage system resources and control tasks that are run on, e.g., host device202. For example, the OS may be implemented using Microsoft® Windows®, HP-UX®, Linux®, or UNIX®, although other operating systems may be used. In another example, the OS may be implemented using Android™, iOS, Windows Phone® or BlackBerry®. In some embodiments, the OS may be replaced by a virtual machine monitor (or hypervisor) which may provide a layer of abstraction for underlying hardware to various operating systems (virtual machines) running on one or more processing units. The operating system and/or virtual machine may implement a protocol stack. A protocol stack may execute one or more programs to process packets. An example of a protocol stack is a TCP/IP (Transport Control Protocol/Internet Protocol) protocol stack comprising one or more programs for handling (e.g., processing or generating) packets to transmit and/or receive over a network.

Host memory circuitry212may include one or more of the following types of memory: semiconductor firmware memory, programmable memory, nonvolatile memory, read only memory, electrically programmable memory, random access memory, flash memory, magnetic disk memory, and/or optical disk memory. Either additionally or alternatively system memory may include other and/or later-developed types of computer-readable memory.

Embodiments of the operations described herein may be implemented in a computer-readable storage device having stored thereon instructions that when executed by one or more processors perform the methods. The processor may include, for example, a processing unit and/or programmable circuitry. The storage device may include a machine readable storage device including any type of tangible, non-transitory storage device, for example, any type of disk including floppy disks, optical disks, compact disk read-only memories (CD-ROMs), compact disk rewritables (CD-RWs), and magneto-optical disks, semiconductor devices such as read-only memories (ROMs), random access memories (RAMs) such as dynamic and static RAMs, erasable programmable read-only memories (EPROMs), electrically erasable programmable read-only memories (EEPROMs), flash memories, magnetic or optical cards, or any type of storage devices suitable for storing electronic instructions.

Host storage logic222and device storage logic236may be configured to provide and execute, respectively, command206, as described herein. LSM logic222, sort-merge logic236and/or command206may comply or be compatible with a nonvolatile memory (NVM) specification related to communication with and operation of storage devices. For example, LSM logic222, sort-merge logic236and/or command206may comply with a NVM specification titled: NVM Express®, Revision 1.2, released November 2014, by NVM Express Workgroup, and/or Revision 1.2.1, released June 2016, and/or later and/or related versions of this specification, e.g., Revision 1.3, released May 2017.

In some embodiments, a hardware description language (HDL) may be used to specify circuit and/or logic implementation(s) for the various logic and/or circuitry described herein. For example, in one embodiment the hardware description language may comply or be compatible with a very high speed integrated circuits (VHSIC) hardware description language (VHDL) that may enable semiconductor fabrication of one or more circuits and/or logic described herein. The VHDL may comply or be compatible with IEEE Standard 1076-1987, IEEE Standard 1076.2, IEEE1076.1, IEEE Draft 3.0 of VHDL-2006, IEEE Draft 4.0 of VHDL-2008 and/or other versions of the IEEE VHDL standards and/or other hardware description standards.

In some embodiments, a Verilog hardware description language (HDL) may be used to specify circuit and/or logic implementation(s) for the various logic and/or circuitry described herein. For example, in one embodiment, the HDL may comply or be compatible with IEEE standard 62530-2011: SystemVerilog—Unified Hardware Design, Specification, and Verification Language, dated Jul. 7, 2011; IEEE Std 1800™-2012: IEEE Standard for SystemVerilog-Unified Hardware Design, Specification, and Verification Language, released Feb. 21, 2013; IEEE standard 1364-2005: IEEE Standard for Verilog Hardware Description Language, dated Apr. 18, 2006 and/or other versions of Verilog HDL and/or SystemVerilog standards.

EXAMPLES

Examples of the present disclosure include subject material such as a method, means for performing acts of the method, a device, or of an apparatus or system related to key-value compaction, as discussed below.

According to this example, there is provided a storage device. The storage device includes a storage I/O (input/output) logic and a storage device controller. The storage I/O (input/output) logic is to couple the storage device to a host device, the storage I/O logic to receive a sort-merge command the host device. The a storage device controller is to identify a level N SSTable (sorted string table) file, a corresponding level N index file, a first level N+1 SSTable file and a corresponding first level N+1 index file, in response to the sort-merge command to be received from the host device. The storage device controller is further to perform a sort-merge of the level N SSTable file and the first level N+1 SSTable file to produce a first level N+1 output SSTable file and a first level N+1 output SSTable index file. The level N SSTable file includes at least one level N key-value (KV) pair. The level N+1 SSTable file includes at least one level N+1 key-value (KV) pair. The sort-merge command includes a level N SSTable file index, a value corresponding to a number of SSTable files included in level N+1 and a level N+1 start SSTable file index. The identifying is based, at least in part, on the level N SSTable file index and the level N+1 start SSTable file index.

This example includes the elements of example 1, wherein the storage device controller is to identify a second level N+1 SSTable file and a corresponding second level N+1 index file based, at least in part, on the level N+1 start SSTable file index, and the storage device controller is to perform a sort-merge of the level N SSTable file and the second level N+1 SSTable file to produce a second level N+1 output SSTable file and a second level N+1 output SSTable index file.

This example includes the elements of example 1, wherein the storage device controller is to at least one of access and/or update an indirection table, the indirection table including an array of SSTable file information array elements, each array element corresponding to a respective SSTable file.

This example includes the elements of example 1, wherein performing the sort-merge includes comparing a level N key from the level N key-value pair to a level N+1 key from the level N+1 key-value pair and selecting the level N key-value pair if the level N key is less than or equal to the level N+1 key or selecting the level N+1 key-value pair if the level N key is greater than the level N+1 key.

This example includes the elements of example 3, wherein each array element includes an SSTable file index, an SSTable file start logical block address (LBA), an SSTable file LBA length, an SSTable index file start LBA, an SSTable index file LBA length, a number of key-value (KV) pairs included in the respective SSTable file and an SSTable file status.

This example includes the elements according to any one of examples 1 to 4, wherein the storage device controller comprises a sort-merge circuitry comprising at least one key-value compaction architecture.

This example includes the elements according to any one of examples 1 to 4, wherein the sort-merge command includes a command identifier field.

This example includes the elements of example 7, wherein the sort-merge command further includes a field to indicate a number of SSTable files in level N+1 overlapped by the level N SSTable file.

This example includes the elements according to any one of examples 1 to 4, wherein the storage device controller includes a sort-merge circuitry including a command buffer to store the sort-merge command, a plurality of input buffers to store selected SS table files and selected SS table file indexes, a comparator to compare selected keys, a multiplexer, a plurality of intermediate buffers and an output buffer to store each level N+1 output SSTable file.

According to this example, there is provided a method. The method includes coupling, by a storage I/O (input/output) logic, a storage device to a host device, the storage I/O logic to receive a sort-merge command the host device; identifying, by a storage device controller, a level N SSTable (sorted string table) file, a corresponding level N index file, a first level N+1 SSTable file and a corresponding first level N+1 index file, in response to the sort-merge command to be received from the host device. The method further includes performing, by the storage device controller, a sort-merge of the level N SSTable file and the first level N+1 SSTable file to produce a first level N+1 output SSTable file and a first level N+1 output SSTable index file. The level N SSTable file includes at least one level N key-value (KV) pair. The level N+1 SSTable file includes at least one level N+1 key-value (KV) pair. The sort-merge command includes a level N SSTable file index, a value corresponding to a number of SSTable files included in level N+1 and a level N+1 start SSTable file index. The identifying is based, at least in part, on the level N SSTable file index and the level N+1 start SSTable file index.

This example includes the elements of example 10, further including identifying, by the storage device controller, a second level N+1 SSTable file and a corresponding second level N+1 index file based, at least in part, on the level N+1 start SSTable file index, and performing, by the sort-merge circuitry, a sort-merge of the level N SSTable file and the second level N+1 SSTable file to produce a second level N+1 output SSTable file and a second level N+1 output SSTable index file.

This example includes the elements of example 10, further including at least one of accessing and/or updating, by the storage device controller, an indirection table, the indirection table including an array of SSTable file information array elements, each array element corresponding to a respective SSTable file.

This example includes the elements of example 10, wherein performing the sort-merge includes comparing a level N key from the level N key-value pair to a level N+1 key from the level N+1 key-value pair and selecting the level N key-value pair if the level N key is less than or equal to the level N+1 key or selecting the level N+1 key-value pair if the level N key is greater than the level N+1 key.

This example includes the elements of example 12, wherein each array element includes an SSTable file index, an SSTable file start logical block address (LBA), an SSTable file LBA length, an SSTable index file start LBA, an SSTable index file LBA length, a number of key-value (KV) pairs included in the respective SSTable file and an SSTable file status.

This example includes the elements of example 10, wherein the storage device controller comprises a sort-merge circuitry comprising at least one key-value compaction architecture.

This example includes the elements of example 10, wherein the sort-merge command includes a command identifier field.

This example includes the elements of example 16, wherein the sort-merge command further includes a field to indicate a number of SSTable files in level N+1 overlapped by the level N SSTable file.

According to this example, there is provided system. The system includes a storage device. The storage device includes a plurality of nonvolatile media, a storage I/O (input/output) logic and a storage device controller. The storage device controller is to identify a level N SSTable (sorted string table) file, a corresponding level N index file, a first level N+1 SSTable file and a corresponding first level N+1 index file, in response to the sort-merge command to be received from the host device. The storage device controller is to perform a sort-merge of the level N SSTable file and the first level N+1 SSTable file to produce a first level N+1 output SSTable file and a first level N+1 output SSTable index file. The level N SSTable file includes at least one level N key-value (KV) pair. The level N+1 SSTable file includes at least one level N+1 key-value (KV) pair. The sort-merge command includes a level N SSTable file index, a value corresponding to a number of SSTable files included in level N+1 and a level N+1 start SSTable file index. The identifying is based, at least in part, on the level N SSTable file index and the level N+1 start SSTable file index.

This example includes the elements of example 18, wherein the storage device controller is to identify a second level N+1 SSTable file and a corresponding second level N+1 index file based, at least in part, on the level N+1 start SSTable file index, and the storage device controller is to perform a sort-merge of the level N SSTable file and the second level N+1 SSTable file to produce a second level N+1 output SSTable file and a second level N+1 output SSTable index file.

This example includes the elements of example 18, wherein the storage device controller is to at least one of access and/or update an indirection table, the indirection table including an array of SSTable file information array elements, each array element corresponding to a respective SSTable file.

This example includes the elements of example 18, wherein performing the sort-merge includes comparing a level N key from the level N key-value pair to a level N+1 key from the level N+1 key-value pair and selecting the level N key-value pair if the level N key is less than or equal to the level N+1 key or selecting the level N+1 key-value pair if the level N key is greater than the level N+1 key.

This example includes the elements of example 20, wherein each array element includes an SSTable file index, an SSTable file start logical block address (LBA), an SSTable file LBA length, an SSTable index file start LBA, an SSTable index file LBA length, a number of key-value (KV) pairs included in the respective SSTable file and an SSTable file status.

This example includes the elements according to any one of examples 18 to 21, wherein the storage device controller comprises a sort-merge circuitry comprising at least one key-value compaction architecture.

This example includes the elements according to any one of examples 18 to 21, wherein the sort-merge command includes a command identifier field.

This example includes the elements of example 24, wherein the sort-merge command further includes a field to indicate a number of SSTable files in level N+1 overlapped by the level N SSTable file.

This example includes the elements according to any one of examples 18 to 21, wherein the storage device controller includes a sort-merge circuitry including a command buffer to store the sort-merge command, a plurality of input buffers to store selected SS table files and selected SS table file indexes, a comparator to compare selected keys, a multiplexer, a plurality of intermediate buffers and an output buffer to store each level N+1 output SSTable file.

This example includes the elements according to any one of examples 18 to 21, wherein the storage device is selected from the group including a solid-state drive (SSD), a hard disk drive (HDD), a network attached storage (NAS) system, a storage area network (SAN) and/or a redundant array of independent disks (RAID) system.

This example includes the elements according to any one of examples 18 to 21, wherein each of the plurality of nonvolatile media is selected from the group including a NAND flash memory, a NOR memory, a solid state memory, byte addressable nonvolatile memory devices, ferroelectric memory, silicon-oxide-nitride-oxide-silicon (SONOS) memory, polymer memory, byte addressable random accessible three dimensional crosspoint memory, ferroelectric transistor random access memory, magnetoresistive random access memory, phase change memory, resistive memory, ferroelectric memory, spin-transfer torque memory, thermal assisted switching memory (TAS), millipede memory, floating junction gate memory (FJG RAM), magnetic tunnel junction (MTJ) memory, electrochemical cells (ECM) memory, binary oxide filament cell memory, interfacial switching memory, battery-backed RAM, ovonic memory, nanowire memory and/or electrically erasable programmable read-only memory (EEPROM).

According to this example, there is provided a computer readable storage device. The device has stored thereon instructions that when executed by one or more processors result in the following operations including: coupling a storage device to a host device, a storage I/O logic to receive a sort-merge command the host device; identifying a level N SSTable (sorted string table) file, a corresponding level N index file, a first level N+1 SSTable file and a corresponding first level N+1 index file, in response to the sort-merge command to be received from the host device; and performing a sort-merge of the level N SSTable file and the first level N+1 SSTable file to produce a first level N+1 output SSTable file and a first level N+1 output SSTable index file. The level N SSTable file includes at least one level N key-value (KV) pair. The level N+1 SSTable file includes at least one level N+1 key-value (KV) pair. The sort-merge command includes a level N SSTable file index, a value corresponding to a number of SSTable files included in level N+1 and a level N+1 start SSTable file index. The identifying is based, at least in part, on the level N SSTable file index and the level N+1 start SSTable file index.

This example includes the elements of example 29, wherein the instructions that when executed by one or more processors results in the following additional operations including identifying a second level N+1 SSTable file and a corresponding second level N+1 index file based, at least in part, on the level N+1 start SSTable file index, and performing a sort-merge of the level N SSTable file and the second level N+1 SSTable file to produce a second level N+1 output SSTable file and a second level N+1 output SSTable index file.

This example includes the elements of example 29, wherein the instructions that when executed by one or more processors results in the following additional operations including at least one of accessing and/or updating an indirection table, the indirection table including an array of SSTable file information array elements, each array element corresponding to a respective SSTable file.

This example includes the elements of example 29, wherein performing the sort-merge includes comparing a level N key from the level N key-value pair to a level N+1 key from the level N+1 key-value pair and selecting the level N key-value pair if the level N key is less than or equal to the level N+1 key or selecting the level N+1 key-value pair if the level N key is greater than the level N+1 key.

This example includes the elements of example 31, wherein each array element includes an SSTable file index, an SSTable file start logical block address (LBA), an SSTable file LBA length, an SSTable index file start LBA, an SSTable index file LBA length, a number of key-value (KV) pairs included in the respective SSTable file and an SSTable file status.

This example includes the elements according to any one of examples 29 to 32, wherein the sort-merge command includes a command identifier field.

This example includes the elements of example 34, wherein the sort-merge command further includes a field to indicate a number of SSTable files in level N+1 overlapped by the level N SSTable file.

According to this example, there is provided a storage device. The storage device includes means for coupling, by a storage I/O (input/output) logic, a storage device to a host device, the storage I/O logic to receive a sort-merge command the host device; means for identifying, by a storage device controller, a level N SSTable (sorted string table) file, a corresponding level N index file, a first level N+1 SSTable file and a corresponding first level N+1 index file, in response to the sort-merge command to be received from the host device; and means for performing, by a sort-merge circuitry, a sort-merge of the level N SSTable file and the first level N+1 SSTable file to produce a first level N+1 output SSTable file and a first level N+1 output SSTable index file. The level N SSTable file includes at least one level N key-value (KV) pair. The level N+1 SSTable file includes at least one level N+1 key-value (KV) pair. The sort-merge command includes a level N SSTable file index, a value corresponding to a number of SSTable files included in level N+1 and a level N+1 start SSTable file index. The identifying is based, at least in part, on the level N SSTable file index and the level N+1 start SSTable file index.

This example includes the elements of example 36, further including means for identifying, by the storage device controller, a second level N+1 SSTable file and a corresponding second level N+1 index file based, at least in part, on the level N+1 start SSTable file index, and means for performing, by the sort-merge circuitry, a sort-merge of the level N SSTable file and the second level N+1 SSTable file to produce a second level N+1 output SSTable file and a second level N+1 output SSTable index file.

This example includes the elements of example 36, further including means for at least one of accessing and/or updating, by the storage device controller, an indirection table, the indirection table including an array of SSTable file information array elements, each array element corresponding to a respective SSTable file.

This example includes the elements of example 36, wherein performing the sort-merge includes comparing a level N key from the level N key-value pair to a level N+1 key from the level N+1 key-value pair and selecting the level N key-value pair if the level N key is less than or equal to the level N+1 key or selecting the level N+1 key-value pair if the level N key is greater than the level N+1 key.

This example includes the elements of example 38, wherein each array element includes an SSTable file index, an SSTable file start logical block address (LBA), an SSTable file LBA length, an SSTable index file start LBA, an SSTable index file LBA length, a number of key-value (KV) pairs included in the respective SSTable file and an SSTable file status.

This example includes the elements according to any one of examples 36 to 39, wherein the storage device controller comprises a sort-merge circuitry comprising at least one key-value compaction architecture.

This example includes the elements according to any one of examples 36 to 39, wherein the sort-merge command includes a command identifier field.

This example includes the elements of example 42, wherein the sort-merge command further includes a field to indicate a number of SSTable files in level N+1 overlapped by the level N SSTable file.

According to this example, there is provided a system. The system includes at least one device arranged to perform the method according to any one of examples 10 to 17.

According to this example, there is provided a device. The device includes means to perform the method according to any one of examples 10 to 17.

According to this example, there is provided a computer readable storage device. The device has stored thereon instructions that when executed by one or more processors result in the following operations including: the method according to any one of examples 10 to 17.