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

Patent metadata

Field	Value
Publication number	US-12079120-B2
Application number	US-202318092982-A
Country	US
Kind code	B2
Filing date	Jan 4, 2023
Priority date	Dec 24, 2019
Publication date	Sep 3, 2024
Grant date	Sep 3, 2024

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 nonvolatile memory;
a volatile memory configured to store a plurality of keys including a first key and a second key and a plurality of values including a first value and a second value; and
a controller coupled to the nonvolatile memory and the volatile memory, configured to receive a first command including a first key-value pair that includes the first key and the first value corresponding to the first key, and to receive a second command including a second key-value pair that includes the second key and the second value corresponding to the second key,
wherein the controller is configured to separate the first key and the first value and to store the first key and the first value in the volatile memory, and to separate the second key and the second value and to store the second key and the second value in the volatile memory,
the controller is configured to write the first value in the nonvolatile memory based on the first command, and to write the second value in the nonvolatile memory based on the second command, and
the controller is configured to delete one or more invalid keys among the plurality of keys.

2. The storage device of claim 1 , wherein the controller generates a first key stream using only valid keys among the plurality of keys.

3. The storage device of claim 2 , wherein the controller stores the first key stream in a first region of the nonvolatile memory.

4. The storage device of claim 3 , wherein the controller reads a plurality of key streams including the first key stream stored in the nonvolatile memory, deletes invalid keys among the plurality of key streams, and generates a third key stream using only valid keys among the plurality of key streams.

5. The storage device of claim 1 , wherein the controller performs a garbage collection operation for invalid values corresponding to the one or more invalid keys.

6. The storage device of claim 5 , wherein the controller generates a first value stream using only valid values among the plurality of values.

7. The storage device of claim 6 , wherein the controller stores the first value stream in a second region of the nonvolatile memory.

8. The storage device of claim 1 , wherein the storage device is a universal flash storage (UFS) memory device.

9. A storage device comprising:
a nonvolatile memory;
a volatile memory configured to store a plurality of keys including a first key and a second key and a plurality of values including a first value and a second value; and
a controller coupled to the nonvolatile memory and the volatile memory, configured to receive a plurality of commands including a first command that includes a first key-value pair and a second command that includes a second key-value pair,
wherein the first key-value pair includes the first key and the first value corresponding to the first key,
the second key-value pair includes the second key and the second value corresponding to the second key,
the controller is configured to separate the first key and the first value, to separate the second key and the second value, and to store the first key, the second key, the first value and the second value in the volatile memory,
the controller is configured to write the first value in the nonvolatile memory based on the first command, and write the second value in the nonvolatile memory based on the second command,
the controller is configured to delete one or more invalid keys among the plurality of keys, and
the controller is configured to generate a first key stream using only valid keys among the plurality of keys.

10. The storage device of claim 9 , wherein the controller stores the first key stream in a first region of the nonvolatile memory.

11. The storage device of claim 10 , wherein the controller reads a plurality of key streams including the first key stream stored in the nonvolatile memory, deletes invalid keys among the plurality of key streams, and generates a third key stream using only valid keys among the plurality of key streams.

12. The storage device of claim 9 , wherein the controller performs a garbage collection operation for invalid values corresponding to the one or more invalid keys.

13. The storage device of claim 9 , wherein the controller generates a first value stream using only valid values among the plurality of values.

14. The storage device of claim 13 , wherein the controller stores the first value stream in a second region of the nonvolatile memory.

15. The storage device of claim 9 , wherein the storage device is an embedded universal flash storage (UFS) memory device.

16. A storage device comprising:
a nonvolatile memory;
a volatile memory configured to store a plurality of keys including a first key and a second key and a plurality of values including a first value and a second value; and
a controller coupled to the nonvolatile memory and the volatile memory, configured to receive a plurality of commands including a first command that includes the first key and the first value corresponding to the first key and a second command that includes the second key and the second value corresponding to the second key,
wherein the controller is configured to separate the first key and the first value, to separate the second key and the second value, and to store the first key, the second key, the first value and the second value in the volatile memory,
the controller is configured to write the first value in the nonvolatile memory based on the first command, and write the second value in the nonvolatile memory based on the second command,
the controller is configured to delete one or more invalid keys among the plurality of keys, and
the controller is configured to perform a garbage collection operation for invalid values corresponding to the one or more invalid keys.

17. The storage device of claim 16 , wherein the controller generates a first key stream using only valid keys among the plurality of keys.

18. The storage device of claim 17 , wherein the controller stores the first key stream in a first region of the nonvolatile memory,
the controller generates a first value stream using only valid values among the plurality of values, and
the controller stores the first value stream in a second region of the nonvolatile memory.

19. The storage device of claim 16 , wherein the volatile memory stores a physical address of the nonvolatile memory in which a key stream is stored.

20. The storage device of claim 16 , wherein the storage device is an embedded universal flash storage (UFS) memory device.

Assignees

• Samsung Electronics Co Ltd

Inventors

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

Classifications

• G06F21/107

  License processing; Key processing · CPC title

• G06F13/1668 Primary

  Details of memory controller · CPC title

• G06F21/79

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

• G06F12/0253

  Garbage collection, i.e. reclamation of unreferenced memory · CPC title

• G06F12/1466

  Key-lock mechanism · CPC title