Key-value compaction

Patent metadata

Field	Value
Publication number	US-10496371-B2
Application number	US-201715636974-A
Country	US
Kind code	B2
Filing date	Jun 29, 2017
Priority date	Jun 29, 2017
Publication date	Dec 3, 2019
Grant date	Dec 3, 2019

Abstract

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.

First claim

What is claimed is:

1. A storage device comprising:
a storage I/O (input/output) logic to couple the storage device to a host device, the storage I/O logic to receive a sort-merge command the host device; and
a storage device controller 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; and 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, wherein the first level N+1 output SSTable file replaces the N SSTable file or replaces the first level N+1 SSTable file,
the level N SSTable file comprising at least one level N key-value (KV) pair, the level N+1 SSTable file comprising at least one level N+1 key-value (KV) pair, the sort-merge command comprising 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 based, at least in part, on the level N SSTable file index and the level N+1 start SSTable file index.

2. The storage device of claim 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.

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

4. The storage device of claim 1 , wherein performing the sort-merge comprises 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.

5. The storage device of claim 3 , wherein each array element comprises 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.

6. The storage device of claim 1 , wherein the storage device controller comprises a sort-merge circuitry comprising at least one key-value compaction architecture.

7. The storage device of claim 1 , wherein the sort-merge command comprises at least one of a command identifier field and/or a field to indicate a number of SSTable files in level N+1 overlapped by the level N SSTable file.

8. A method comprising:
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; and
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, wherein the first level N+1 output SSTable file replaces the N SSTable file or replaces the first level N+1 SSTable file,
the level N SSTable file comprising at least one level N key-value (KV) pair, the level N+1 SSTable file comprising at least one level N+1 key-value (KV) pair, the sort-merge command comprising 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 based, at least in part, on the level N SSTable file index and the level N+1 start SSTable file index.

9. The method of claim 8 , further comprising 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.

10. The method of claim 8 , further comprising at least one of accessing and/or updating, by the storage device controller, an indirection table, the indirection table comprising an array of SSTable file information array elements, each array element corresponding to a respective SSTable file.

11. The method of claim 8 , wherein performing the sort-merge comprises 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.

12. The method of claim 10 , wherein each array element comprises 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.

13. The method of claim 8 , wherein the storage device controller comprises a sort-merge circuitry comprising at least one key-value compaction architecture.

14. The method of claim 8 , wherein the sort-merge command comprises at least one of a command identifier field and/or a field to indicate a number of SSTable files in level N+1 overlapped by the level N SSTable file.

15. A system comprising a storage device comprising:
a plurality of nonvolatile media;
a storage I/O (input/output) logic to couple the storage device to a host device, the storage I/O logic to receive a sort-merge command the host device; and
a storage device controller 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; and 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, wherein the first level N+1 output SSTable file replaces the N SSTable file or replaces the first level N+1 SSTable file,
the level N SSTable file comprising at least one level N key-value (KV) pair, the level N+1 SSTable file comprising at least one level N+1 key-value (KV) pair, the sort-merge command comprising 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 based, at least in part, on the level N SSTable file index and the level N+1 start SSTable file index.

16. The system of claim 15 , wherein the storage device controller is to identify a second level N+1 SSTable file

Assignees

• Intel Corp

Inventors

• Li Peng
• Khan Jawad B
• Trika Sanjeev

Classifications

• G06F16/901

  Indexing; Data structures therefor; Storage structures (for retrieval from the web G06F16/951) · CPC title

• G06F16/2246

  Trees, e.g. B+trees · CPC title

• G06F7/36 Primary

  Combined merging and sorting · CPC title

• G06F7/24

  Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers {sorting methods in general}(G06F7/36 takes precedence) · CPC title

• G06F2207/224

  External sorting · CPC title