Reducing forward mapping table size using hashing

Patent metadata

Field	Value
Publication number	US-10977189-B2
Application number	US-201916562518-A
Country	US
Kind code	B2
Filing date	Sep 6, 2019
Priority date	Sep 6, 2019
Publication date	Apr 13, 2021
Grant date	Apr 13, 2021

Abstract

Technologies are described herein for or reducing the size of the forward mapping table in an SSD or other storage device using hashing. A physical address of a storage location within a storage media is determined for the storage of data associated with a logical block address. The data is written to the storage location and a hash value is computed from a representation of the physical address using a hash function, where the size of the hash value is smaller than the representation of the physical address and the hash value points to a plurality of separate storage locations in the storage media. The hash value is stored in the forward mapping table associated with logical block address as opposed to the representation of the physical address.

First claim

What is claimed is:

1. A method implemented in a controller of a storage device comprising steps of:
determining a physical address of a storage location within a storage media of the storage device to store data associated with a logical block address;
writing the data to the storage location;
computing a hash value from a representation of the physical address using a hash function, the hash value having a smaller size than the representation of the physical address and pointing to a plurality of separate storage locations in the storage media; and
storing the hash value in a mapping table of the controller in a location corresponding to the logical block address associated with the data.

2. The method of claim 1 , wherein the hash function is configured such that the plurality of separate storage locations can be accessed in the storage media concurrently by the controller.

3. The method of claim 1 , wherein the hash function comprises hashing a channel specification portion of the representation of the physical address.

4. The method of claim 1 , wherein the hash function comprises hashing a block number portion of the representation of the physical address.

5. The method of claim 1 , wherein the mapping table is stored in a RAM of the controller.

6. The method of claim 1 , wherein a size of the representation of the physical address does not allow the representation of the physical address to be stored within a word boundary of a CPU of the controller, and wherein the hash value is stored within the word boundary of the CPU.

7. The method of claim 1 , further comprising the steps of:
in response to receiving a read command specifying the logical block address, retrieving the hash value from the mapping table based on the logical block address;
computing physical addresses for each of the plurality of separate storage locations from the hash value using a reverse of the hash function;
reading data from the plurality of separate storage locations based on the computed physical addresses; and
determining the data associated with the logical block address to return for the read command based on header information associated with the data read from the plurality of separate storage locations.

8. The method of claim 7 , further comprising the steps of:
determining that data read from two storage locations of the plurality of separate storage locations are associated with the logical block address;
retrieving a timestamp associated with each of the data from the two storage locations; and
determining the data associated with the logical block address to return for the read command based on a later value of the timestamp associated with each of the data.

9. The method of claim 1 , wherein the storage media comprises NAND flash memory and the storage device comprises a solid-state disk (“SSD”) device.

10. A storage device comprising:
a non-volatile memory comprising a plurality of storage locations;
a forward mapping table for mapping logical block addresses to the plurality of storage locations; and
a controller for storing user data from a host to the non-volatile memory, the controller configured to
determine a physical address of a storage location within the non-volatile memory to store data associated with a logical block address,
write the data to the storage location,
compute a hash value from the physical address of the storage location using a hash function,
store the hash value in the forward mapping table associated with the logical block address,
in response to receiving a read command specifying the logical block address, retrieve the hash value from the forward mapping table based on the logical block address,
compute a plurality of physical addresses from the hash value using a reverse of the hash function,
read data from storage locations within the non-volatile memory corresponding to each of the plurality of physical addresses, and
determine the data associated with the logical block address to return for the read command based on header information associated with the data read from the storage locations.

11. The storage device of claim 10 , wherein the hash function is configured such that the storage locations corresponding to the plurality of physical addresses can be accessed in the non-volatile memory concurrently by the controller.

12. The storage device of claim 10 , wherein the forward mapping table is stored in a RAM of the controller.

13. The storage device of claim 12 , wherein a size of the hash value is smaller than a size of a representation of the physical address.

14. The storage device of claim 12 , wherein a size of a representation of the physical address does not allow the representation of the physical address to be stored within a word boundary of a CPU of the controller, and wherein the hash value is stored within the word boundary of the CPU.

15. The storage device of claim 10 , wherein the hash function comprises hashing a channel specification portion of the physical address.

16. The storage device of claim 10 , wherein the hash function comprises hashing a block number portion of the physical address.

17. A non-transitory computer-readable storage medium containing processor-executable instructions that, when executed by a CPU of a controller of a storage device, cause the CPU to:
determine a physical address of a storage location within a storage media of the storage device to store data associated with a logical block address;
compute a hash value from the physical address of the storage location using a hash function, a size of the hash value being smaller than a size of a representation of the physical address;
store the hash value in a forward mapping table of the controller, the hash value stored in a location within the forward mapping table associated with the logical block address;
in response to receiving a read command specifying the logical block address, retrieve the hash value from the forward mapping table based on the logical block address;
compute a plurality of physical addresses from the hash value using a reverse of the hash function;
read data from storage locations within the storage media corresponding to each of the plurality of physical addresses; and
determine the data mapped to the logical block address to return for the read command based on header information associated with the data read from the storage locations.

18. The non-transitory computer-readable storage medium of claim 17 , wherein the hash function is configured such that the storage locations corresponding to the plurality of physical addresses can be accessed in storage media concurrently by the controller.

19. The non-transitory computer-readable storage medium of claim 17 , wherein the hash function comprises one or more of hashing a channel specification portion of the physical address and hashing a block number portion of the physical address.

20. The non-transitory computer-readable storage medium of claim 17 , wherein the forward mapping table is stored in a RAM of the controller.

Assignees

• Seagate Technology Llc

Inventors

• Conklin Kristofer Carlson
• Goss Ryan James
• Welch Reid Alan

Classifications

• G06F2212/7201

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

• G06F12/0246 Primary

  in block erasable memory, e.g. flash memory · CPC title

• G06F2212/1044

  Space efficiency improvement · CPC title

• G06F2212/657

  Virtual address space management · CPC title

• G06F12/1018 Primary

  involving hashing techniques, e.g. inverted page tables · CPC title