Method and device for log structured merge-tree based key-value data storage

Patent metadata

Field	Value
Publication number	US-12153802-B2
Application number	US-202318177985-A
Country	US
Kind code	B2
Filing date	Mar 3, 2023
Priority date	Dec 12, 2022
Publication date	Nov 26, 2024
Grant date	Nov 26, 2024

Abstract

A log-structured merge-tree (LSM-Tree) based key-value (KV) data storage method includes writing KV data into a NAND flash memory. The KV data includes a key-value pair including a key and a corresponding value. The KV data is stored in a key-value solid state drive (KVSSD), which includes a storage class memory (SCM) and the NAND flash memory. The method further includes storing metadata of the KV data in the SCM. The metadata of the KV data includes the key and index information of the corresponding value of the KV data, and the index information of the corresponding value of the KV data indicates address information of the KV data in the NAND flash memory.

First claim

What is claimed is:

1. A log-structured merge-tree (LSM-Tree) based key-value (KV) data storage method, the method comprising:
writing KV data into a NAND flash memory,
wherein the KV data comprises a key-value pair including a key and a corresponding value, the KV data is stored in a key-value solid state drive (KVSSD), and the KVSSD comprises a storage class memory (SCM) and the NAND flash memory; and
storing metadata of the KV data in the SCM,
wherein the metadata of the KV data comprises the key and index information of the corresponding value of the KV data, and the index information of the corresponding value of the KV data indicates address information of the KV data in the NAND flash memory.

2. The method of data storage according to claim 1 , further comprising:
creating index information of the metadata in a level list stored in a dynamic random access memory (DRAM) included in the KVSSD based on the metadata,
wherein the index information of the metadata indicates address information of the metadata in the SCM.

3. The method of data storage according to claim 2 , further comprising:
reconstructing the level list comprising the index information of the metadata in the DRAM based on the metadata stored in the SCM, after an abnormal power failure and restart of a storage device.

4. The method of data storage according to claim 1 , wherein a portion of the SCM is configured as a cache, and the method further comprises storing KV data satisfying a cache condition in the cache.

5. A system to which a key-value solid state drive (KVSSD) is applied, comprising:
a main processor;
a memory; and
the KVSSD,
wherein the KVSSD is configured to perform the method of data storage according to claim 1 .

6. A key-value (KV) solid state drive (KVSSD), comprising:
a storage class memory (SCM); and
a NAND flash memory,
wherein the KVSSD is configured to store KV data based on a log-structured merge-tree (LSM-Tree), and the KV data comprises a key-value pair including a key and a corresponding value,
wherein the SCM is configured to store metadata of the KV data,
wherein the metadata of the KV data comprises the key and index information of the corresponding value of the KV data, and the index information of the corresponding value of the KV data indicates address information of the KV data in the NAND flash memory,
wherein the NAND flash memory is configured to store the KV data.

7. The KVSSD according to claim 6 , wherein
the KVSSD further comprises a dynamic random access memory (DRAM), and
the DRAM is configured to store a level list comprising index information of the metadata, the index information of the metadata indicating address information of the metadata in the SCM.

8. The KVSSD according to claim 7 , wherein the index information of the metadata in the level list is reconstructed in the DRAM based on the metadata stored in the SCM, after an abnormal power failure and restart of a storage device.

9. The KVSSD according to claim 6 , wherein a portion of a storage area of the SCM is configured as a cache, and storing KV data satisfying a cache condition in the cache.

Assignees

• Samsung Electronics Co Ltd

Inventors

• Zhang Kun
• Qi Bei
• Cao Dan
• Dou Kun
• Zhang Tianyi
• Zhang Zongyuan
• Zhang Ruyi
• Li Yutao

Classifications

• G06F3/0679

  Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP] · CPC title

• G06F3/0659

  Command handling arrangements, e.g. command buffers, queues, command scheduling · CPC title

• G06F16/2246

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

• G06F2212/7203

  Temporary buffering, e.g. using volatile buffer or dedicated buffer blocks · CPC title

• G06F2212/466

  Metadata, control data · CPC title