Storage system and method for fast lookup in a table-caching database

Patent metadata

Field	Value
Publication number	US-10289557-B2
Application number	US-201715688095-A
Country	US
Kind code	B2
Filing date	Aug 28, 2017
Priority date	Aug 28, 2017
Publication date	May 14, 2019
Grant date	May 14, 2019

Abstract

A storage system and method for fast lookup in a table-caching database are provided. In one embodiment, a storage system is provided comprising a volatile memory, a non-volatile memory, and a controller. The controller is configured to store, in the volatile memory, a data structure representing a compressed version of a logical-to-physical address table stored in the non-volatile memory; and search the data structure for a physical address associated with a logical address, wherein the controller is configured to find any physical address in the data structure in a fixed amount of time. Other embodiments are provided.

First claim

What is claimed is:

1. A storage system comprising:
a volatile memory;
a non-volatile memory; and
a controller in communication with the volatile memory and the non-volatile memory, wherein the controller is configured to:
store, in the volatile memory, a data structure representing a compressed version of a logical-to-physical address table stored in the non-volatile memory, wherein each entry in the data structure comprises a start physical address and start and end logical addresses for a sequential run of logical addresses; and
search each entry in the data structure in parallel for a physical address associated with a logical address, wherein:
the searching comprises (i) simultaneously comparing the logical address both to the start logical address and to the end logical address in each entry and (ii) calculating a physical address associated with the logical address, wherein (i) and (ii) are performed in parallel, and
each entry in the data structure is searched in a same amount of time.

2. The storage system of claim 1 , wherein the controller is further configured to calculate the physical address by:
subtracting the start logical address from the logical address;
dividing by a number of entries in the data structure; and
adding the start physical address.

3. The storage system of claim 1 , wherein the non-volatile memory comprises a three-dimensional memory.

4. The storage system of claim 1 , wherein the storage system is embedded in a host.

5. A method for searching a cached, compressed database representing a logical-to-physical address table, the method comprising:
performing the following in a storage system comprising a volatile memory:
caching, in the volatile memory, a compressed database representing a logical-to-physical address table, wherein each entry in the compressed database comprises a start physical address and start and end logical addresses for a sequential run of logical addresses; and
searching each entry in the cached, compressed database in parallel for a logical address, wherein the searching comprises (i) simultaneously comparing the logical address both to the start logical address and to the end logical address in each entry and (ii) calculating a physical address associated with the logical address, wherein (i) and (ii) are performed in parallel, wherein each entry requires a same amount of time to search.

6. The method of claim 5 , wherein the physical address is calculated by:
subtracting the start logical address from the logical address;
dividing by a number of entries in the cached, compressed database; and
adding the start physical address.

7. The method of claim 5 , wherein the storage system further comprises a three-dimensional non-volatile memory.

8. The method of claim 5 , wherein the storage system is removably connectable to a host.

9. A storage system comprising:
a volatile memory;
a non-volatile memory;
means for storing, in the volatile memory, a data structure representing a compressed version of a logical-to-physical address table stored in the non-volatile memory, wherein each entry in the data structure comprises a start physical address and start and end logical addresses for a sequential run of logical addresses; and
means for searching each entry in the data structure in parallel for a physical address associated with a logical address, wherein the searching comprises (i) simultaneously comparing the logical address both to the start logical address and to the end logical address in each entry and (ii) calculating a physical address associated with the logical address, wherein (i) and (ii) are performed in parallel, wherein each entry in the data structure is searched in a same amount of time.

10. The storage system of claim 9 , wherein:
the means for searching comprises a plurality of search circuitry in communication with a decoder and a multiplexor; and
each entry of the data structure is associated with its own search circuitry.

11. The storage system of claim 10 , wherein at least one search circuitry comprises a comparator, an AND gate, a subtractor, a divider, and an adder.

12. The storage system of claim 9 , wherein the non-volatile memory comprises a three-dimensional memory.

13. The storage system of claim 9 , wherein the storage system is embedded in a host.

Assignees

• Western Digital Tech Inc

Inventors

• Duzly Yacov
• Oshinsky Hadas

Classifications

• G06F12/0884 Primary

  Parallel mode, e.g. in parallel with main memory or CPU · CPC title

• G06F3/064

  Management of blocks · CPC title

• G06F16/9017

  using directory or table look-up (use of a directory or look-up table in file systems G06F16/13) · CPC title

• G06F16/172

  Caching, prefetching or hoarding of files · CPC title

• G06F2212/7201

  Logical to physical mapping or translation of blocks or pages · CPC title