Key-to-physical table optimization for key value data storage devices

Patent metadata

Field	Value
Publication number	US-11966630-B2
Application number	US-202217850423-A
Country	US
Kind code	B2
Filing date	Jun 27, 2022
Priority date	Jun 27, 2022
Publication date	Apr 23, 2024
Grant date	Apr 23, 2024

Abstract

A data storage device includes a memory device and a controller coupled to the memory device. The controller is configured to segment a key to physical (K2P) table into two or more segments, wherein each segment of the two or more segments corresponds to a caching priority of key value (KV) pair data, organize the K2P table by storing and relocating one or more K2P table entries into a respective segment of the two or more segments, wherein the storing and relocating comprises moving a K2P table entry based on the caching priority of the KV pair data into the respective segment having the caching priority, and utilize the K2P table to manage KV pair data stored in the memory device, wherein utilizing the K2P table comprises applying a same management operation, such as prefetching, to each K2P table entry of a same segment.

First claim

What is claimed is:

1. A data storage device, comprising:
a memory device; and
a controller coupled to the memory device, wherein the controller is configured to:
segment a key to physical (K2P) table into two or more segments, wherein each segment of the two or more segments corresponds to a caching priority of key value (KV) pair data;
organize the K2P table by storing and relocating one or more K2P table entries into a respective segment of the two or more segments, wherein the storing and relocating comprises moving a K2P table entry based on the caching priority of the KV pair data into the respective segment having the caching priority; and
utilize the K2P table to manage KV pair data stored in the memory device, wherein utilizing the K2P table comprises applying a same management operation to each KV pair data of a same segment.

2. The data storage device of claim 1 , wherein the data storage device is coupled to a host device, and wherein the K2P table is stored in a host memory buffer (HMB).

3. The data storage device of claim 2 , wherein the data storage device is dynamic random access memory-less (DRAM-less).

4. The data storage device of claim 1 , wherein the caching priority is based on a relative performance value of the KV pair data, and wherein each of the two or more segments is associated with a different relative performance value.

5. The data storage device of claim 4 , the relative performance is either:
a first relative performance; or
a second relative performance, wherein the second relative performance has a lower performance requirement than the first relative performance.

6. The data storage device of claim 1 , wherein the caching priority is based on a KV format of the KV pair data, and wherein each of the two or more segments is associated with a different KV format.

7. The data storage device of claim 6 , wherein the KV format corresponds to a size of the KV pair data.

8. The data storage device of claim 1 , wherein the caching priority is based on a grouping corresponding to KV pair data expected to be read together, and wherein each of the two or more segments is associated with a different grouping.

9. The data storage device of claim 8 , wherein the controller is further configured to generate the grouping based on a pattern of keys associated with received read commands.

10. The data storage device of claim 1 , wherein the caching priority is based on a read frequency of the KV pair data.

11. The data storage device of claim 10 , wherein a first segment of the two or more segments is associated with hot KV pair data and a second segment of the two or more segments is associated with cold KV pair data, and wherein the hot KV pair data is read a greater number of times than the cold KV pair data.

12. The data storage device of claim 1 , wherein the same management operation comprises pre-fetching and allocation of resources of the data storage device.

13. A data storage device, comprising:
a memory device; and
a controller coupled to the memory device, wherein the controller is configured to:
receive a read command for key value (KV) pair data stored in the memory device;
access a key to physical (K2P) table for a K2P entry corresponding to the KV pair data;
retrieve the K2P entry; and
prefetch one or more other K2P entries, wherein the K2P entry and the one or more other K2P entries are in a same segment of two or more segments of the K2P table, wherein each segment of the two or more segments of the K2P table corresponds to a caching priority of KV pair data.

14. The data storage device of claim 13 , wherein the controller is configured to use the prefetched one or more other K2P entries on a subsequently received read command, wherein the subsequently received read command is for another KV pair data, and wherein the another KV pair data corresponds to one of the prefetched one or more other K2P entries.

15. The data storage device of claim 13 , wherein a plurality of KV pair data associated with the prefetched one or more other K2P entries has either:
a same KV format as the KV pair data; or
a same size as the KV pair data.

16. The data storage device of claim 13 , wherein the same segment comprises a plurality of K2P entries that are clustered together, wherein the plurality of K2P entries corresponds to KV pair data that are read together.

17. The data storage device of claim 13 , wherein the same segment comprises a plurality of K2P entries that are clustered together, and wherein the plurality of K2P entries correspond to KV pair data that is associated with greater than about 50% of a plurality of received read commands.

18. The data storage device of claim 17 , wherein the plurality of K2P entries are stored in a cache of the data storage device.

19. A data storage device, comprising:
memory means; and
a controller coupled to the memory means, wherein the controller is configured to:
cluster one or more key to physical (K2P) entries in a K2P table based on a key value (KV) format of a KV pair data, a size of the KV pair data, a read frequency of the KV pair data, a read likelihood of an another KV pair data to be read after reading the KV pair data, and a relative performance of the KV pair data; and
prefetch the one or more K2P entries in response to receiving a read command for a K2P entry of the one or more K2P entries.

20. The data storage device of claim 19 , wherein the data storage device is dynamic random access memory-less (DRAM-less), and wherein the K2P table is stored in a host memory buffer (HMB) of a host device coupled to the data storage device.

Assignees

• Western Digital Tech Inc

Inventors

• Zamir Ran
• Bazarsky Alexander
• Avraham David

Classifications

• G06F3/0656 Primary

  Data buffering arrangements · CPC title

• G06F3/0607

  by facilitating the process of upgrading existing storage systems, e.g. for improving compatibility between host and storage device · CPC title

• G06F3/0659

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

• G06F3/0679 Primary

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

• G06F3/061

  Improving I/O performance · CPC title