Storage device storing data based on key-value and operating method of the same

Patent metadata

Field	Value
Publication number	US-11573890-B2
Application number	US-202017034242-A
Country	US
Kind code	B2
Filing date	Sep 28, 2020
Priority date	Dec 24, 2019
Publication date	Feb 7, 2023
Grant date	Feb 7, 2023

Abstract

A storage device generates and stores a key stream and a value stream by extracting from data a plurality of keys and a plurality of values respectively corresponding to the plurality of keys. The storage device includes a controller and a non-volatile memory. The controller receives from a host information about an invalid key included in the key stream together with a compaction command, and performs a compaction operation on the key stream in response to the compaction command. The non-volatile memory stores the key stream and the value stream. The controller merges the key stream with another key stream based on the information about the invalid key in the compaction operation.

First claim

What is claimed is:

1. A storage device comprising:
a controller configured to generate a key stream and a value stream by extracting a plurality of keys and a plurality of values respectively corresponding to the plurality of keys provided by a host, receive, from the host, information about a specific invalid key included in the key stream together with a compaction command, and perform a compaction operation on the key stream in response to the compaction command; and
a non-volatile memory that stores the key stream and the value stream,
wherein the controller merges the key stream with another key stream to a merged key stream based on the information about the invalid key in the compaction operation.

2. The storage device of claim 1 , wherein the controller is configured to generate the key stream by merging each of the plurality of keys with an index corresponding to a corresponding value among the plurality of values.

3. The storage device of claim 2 , wherein the controller receives, from the host, an index corresponding to the invalid key as the information about the invalid key.

4. The storage device of claim 1 , wherein the controller generates a first key stream by combining at least some of the plurality of keys, generates a second key stream by combining at least some of the plurality of keys, generates a third key stream by merging the first key stream with the second key stream based on the information about the invalid key, and stores the generated third key stream in the non-volatile memory.

5. The storage device of claim 4 , wherein the controller determines invalid keys among a plurality of keys included in the first key stream and the second key stream based on the information about the invalid key, and generates the third key stream by combining valid keys included in the first key stream and the second key stream,
wherein the invalid keys correspond to values that have received a delete command from the host among the plurality of values.

6. The storage device of claim 1 , further comprising:
a volatile memory that stores a key table comprising a physical address for the non-volatile memory and a value table comprising a physical address for the non-volatile memory of the value stream.

7. The storage device of claim 6 , wherein the key table stores a validity bit corresponding to the value stream so that a valid key corresponds to a key corresponding to the plurality of values.

8. The storage device of claim 6 , wherein, when performing the compaction operation, the controller updates the key table by adding an address for the merged key stream to the key table.

9. The storage device of claim 1 , wherein the controller further receives, from the host, data capacity information about values corresponding to a plurality of invalid keys including the invalid key, and performs a garbage collection operation on the values by using the data capacity information.

10. The storage device of claim 1 , wherein the controller receives an address of the non-volatile memory in which the invalid key is stored, as the information about the invalid key.

11. An operating method of a storage device that stores a key stream and a value stream generated by extracting, from data, a plurality of keys and a plurality of values respectively corresponding to the plurality of keys, the operating method comprising:
receiving from a host a compaction command and information about a specific invalid key included in the key stream;
performing a compaction operation based on the compaction command by merging the key stream with another key stream to a merged key stream based on the information about the invalid key; and
storing the merged key stream in a non-volatile memory.

12. The operating method of claim 11 , further comprising: generating indices for the plurality of values respectively corresponding to the plurality of keys; and
generating the key stream by relating the indices with the plurality of keys.

13. The operating method of claim 12 , wherein the information about the invalid key includes index information corresponding to a plurality of invalid keys including the invalid key, and
the performing of the compaction operation comprises merging only valid keys of the key stream with another key stream h excluding the plurality of invalid keys from the key stream based on the index information.

14. The operating method of claim 13 , further comprising:
generating a key table comprising information about a storage location of the key stream in the non-volatile memory and a validity bit corresponding to the key stream; and
updating the validity bit based on the information about the invalid key.

15. The operating method of claim 14 , wherein the performing of the compaction operation comprises generating the merged key stream by extracting valid keys among a plurality of keys included) in the key stream and the another key stream based on the validity bit.

16. A storage system storing a key stream and a value stream generated by extracting, from data, a plurality of keys and a plurality of values respectively corresponding to the plurality of keys, the storage system comprising:
a host configured to transmit a compaction command for the key stream and information about a specific invalid key included in the key stream; and
a storage device configured to receive the compaction command, perform a compaction operation based on the compaction command by merging the key stream with another key stream to a merged key stream based on the information about the invalid key, and store the merged key stream.

17. The storage system of claim 16 , wherein the storage device generates the key stream by combining each of the plurality of keys with an index corresponding to a corresponding value among the plurality of values, and
the information about the invalid key comprises index information corresponding to a plurality of invalid keys including the invalid key.

18. The storage system of claim 17 , wherein the storage device generates a first key stream by combining at least some of the plurality of keys, generates a second key, stream by combining at least some of the plurality of keys that are not in the first key stream generates a third key stream by merging the first key stream with the second key stream based on the index information, and stores the generated third key stream in a non-volatile memory.

19. The storage system of claim 18 , wherein the key table stores a validity bit corresponding to each of the plurality of values to correspond to a key corresponding to the plurality of values.

20. The storage system of claim 16 , wherein the storage device further receives, from the host, data capacity information about values corresponding to a plurality of invalid keys including the invalid key, and performs a garbage collection operation on the values by using the data capacity information.

Assignees

• Samsung Electronics Co Ltd

Inventors

• Lee Hwang
• Kumar Satish
• Kim Chansoo
• Heo Wan

Classifications

• G06F21/79

  in semiconductor storage media, e.g. directly-addressable memories · CPC title

• G06F11/1004

  to protect a block of data words, e.g. CRC or checksum (G06F11/1076 takes precedence; security arrangements for protecting computers or computer systems against unauthorized activity G06F21/00) · CPC title

• G06F3/0613

  in relation to throughput · CPC title

• G06F13/1668 Primary

  Details of memory controller · CPC title

• G06F3/0617

  in relation to availability · CPC title