Granted Patent B2

US 10,956,071 · App. 16/246,425 · Granted Mar 23, 2021

Inventor: Sanjay Subbarao (Irvine, CA)

Assignee: Western Digital Technologies, Inc.

G06F3/064G06F3/061G06F3/0679G06F16/122

Abstract

Claims (68)

1. A method for operating a Data Storage Device (DSD) including at least one non-volatile storage media for storing data, the method comprising:

receiving a command to modify a data object or file stored in the at least one non-volatile storage media, wherein the command is byte-addressable for overwriting only a portion of the data object or file, deleting only a portion of the data object or file, or inserting new data into the data object or file stored in the at least one non-volatile storage media;

writing in a storage location of the at least one non-volatile storage media the modified portion of the data object or file and an indication of a page container entry that points to a previous storage location for previously written data for the data object or file that was most recently written in the at least one non-volatile storage media before writing the modified portion;

updating a mapping for the data object or file to point to the storage location in the at least one non-volatile storage media storing the modified portion of the data object or file and the indication of the page container entry;

generating a non-unique hash value for a data object or file to be accessed from the at least one non-volatile storage media using a unique key for the data object or file to be accessed; and

using the generated non-unique hash value to identify the mapping for the data object or file to be accessed by at least:

reading a metadata container that is identified by the generated non-unique hash value; and

identifying a handle in the metadata container that is associated with the unique key for the data object or file and points to the mapping for the data object or file.

2. The method of claim 1 , further comprising creating at least one container data structure that points to storage locations in the at least one non-volatile storage media that store data for data objects or files, wherein the mapping and the page container for the data object or file are stored in the at least one container data structure.

3. The method of claim 2 , wherein the data for the data objects or files stored in the storage locations pointed to by the at least one container data structure have varying sizes with a minimum size that is less than a page size of the at least one non-volatile storage media.

4. The method of claim 1 , further comprising executing an Application Programming Interface (API) including an insert command for inserting byte-addressable data into data objects or files previously stored in the at least one non-volatile storage media.

5. The method of claim 1 , further comprising:

determining the previous storage location from the mapping for the data object or file before updating the mapping; and

creating the page container entry that points to the previous storage location.

6. The method of claim 1 , further comprising:

receiving a read command from a host to read the data object or file from the at least one non-volatile storage media;

using the mapping to determine the storage location in the at least one non-volatile storage media storing the modified portion of the data object or file and the indication of the page container entry;

reading the modified portion of the data object or file and the indication of the page container entry that points to the previous storage location in the at least one non-volatile storage media for the previously written data that was most recently written for the data object or file before writing the modified portion;

accessing the page container entry to determine the previous storage location;

reading from the previous storage location the previously written data that was most recently written for the data object or file before writing the modified portion;

assembling a current version of the data object or file using the modified portion of the data object or file and the previously written data for the data object or file; and

returning the current version of the data object or file to the host to complete the read command.

7. The method of claim 1 , wherein in assembling a current version of the data object or file, the method further comprises determining whether the modified portion of the data object or file replaces at least a portion of the previously written data for the data object or file.

8. The method of claim 1 , further comprising:

performing a maintenance operation to rewrite portions of the data obj ect or file from different storage locations in the at least one non-volatile storage media to a contiguous storage location;

updating the mapping for the data object or file to point to the contiguous storage location; and

deleting the page container entry that points to the previous storage location.

9. The method of claim 1 , wherein a link between the unique key and the mapping for the data object or file to be accessed remains fixed from an initial storage of the data object or file in the at least one non-volatile storage media to when the data object or file is identified for deletion.

10. The method of claim 1 , further comprising using a dense hash function to generate the same non-unique hash value for a plurality of unique keys, and wherein a total number of metadata containers is limited to a fraction of a total number of data objects or files stored in the at least one non-volatile storage media so that each of the metadata containers is associated with multiple unique keys for different data objects or files.

11. A Data Storage Device (DSD), comprising:

at least one non-volatile storage media configured to store data; and

control circuitry configured to:

maintain at least one container data structure that points to storage locations in the at least one non-volatile storage media that store data for data objects or files, wherein data container entries in the at least one container data structure point to storage locations for data having varying sizes with a minimum size that is less than a page size of the at least one non-volatile storage media;

receive a command to modify a data object or file stored in the at least one non-volatile storage media, wherein the command is byte-addressable for overwriting only a portion of the data object or file, deleting only a portion of the data object or file, or inserting new data into the data object or file stored in the at least one non-volatile storage media;

write the modified portion of the data object or file and an indication of a page container entry at a storage location in the non-volatile storage media, wherein the page container entry is stored in the at least one container data structure and points to a previous storage location in the at least one non-volatile storage media for previously written data for the data object or file that was most recently written before writing the modified portion; and

update a data container entry in the at least one container data structure for the data object or file to point to the storage location in the at least one non-volatile storage media storing the modified portion of the data object or file and the indication of the page container entry.

12. The DSD of claim 1 , wherein the at least one container data structure includes a data container entry for each data object or file stored in the at least one non-volatile storage media that points to a most recently written storage location in the at least one non-volatile storage media storing the most recently written data for the data object or file.

13. The DSD of claim 11 , wherein the minimum size is less than 512 bytes.

14. The DSD of claim 11 , wherein the control circuitry is further configured to execute an Application Programming Interface (API) including an insert command for inserting byte-addressable data into data objects or files previously stored in the at least one non-volatile storage media.

15. The DSD of claim 11 , wherein the control circuitry is further configured to:

determine the previous storage location by reading the data container entry for the data object or file before updating the data container entry; and

create the page container entry that points to the previous storage location.

16. The DSD of claim 11 , wherein the control circuitry is further configured to:

receive a read command from a host to read the data object or file from the at least one non-volatile storage media;

access the data container entry for the data object or file in the at least one container data structure to determine the storage location in the at least one non-volatile storage media storing the modified portion of the data object or file and the indication of the page container entry;

read the modified portion of the data object or file and the indication of the page container entry that points to the previous storage location in the at least one non-volatile storage media for the previously written data that was most recently written for the data object or file before writing the modified portion;

access the page container entry to determine the previous storage location;

read from the previous storage location the previously written data that was most recently written for the data object or file before writing the modified portion;

assemble a current version of the data object or file using the modified portion of the data object or file and the previously written data for the data object or file; and

return the current version of the data object or file to the host to complete the read command.

17. The DSD of claim 11 , wherein in assembling a current version of the data object or file, the control circuitry is further configured to determine whether the modified portion of the data object or file replaces at least a portion of the previously written data for the data object or file.

18. The DSD of claim 11 , wherein the control circuitry is further configured to:

perform a maintenance operation to rewrite portions of the data object or file from different storage locations in the at least one non-volatile storage media to a contiguous storage location;

update the data container entry for the data object or file in the at least one container data structure to point to the contiguous storage location; and

delete the page container entry from the at least one container data structure that points to the previous storage location.

19. The DSD of claim 11 , wherein the control circuitry is further configured to:

generate a non-unique hash value for a data object or file to be accessed from the at least one non-volatile storage media using a unique key for the data object or file; and

use the generated non-unique hash value to identify a data container entry in the at least one container data structure for the data object or file to be accessed.

20. The DSD of claim 19 , wherein in using the generated non-unique hash value to identify the data container entry for the data object or file to be accessed, the control circuitry is further configured to:

read a metadata container identified by the generated non-unique hash value; and

identify a handle in the metadata container that is associated with the unique key for the data object or file to be accessed and points to the data container entry for the data object or file to be accessed.

21. The DSD of claim 20 , wherein a mapping between the unique key and the data container entry for each data object or file remains fixed from an initial storage of the data object or file in the at least one non-volatile storage media to when the data object or file is identified for deletion.

22. The DSD of claim 20 , wherein the control circuitry is further configured to use a dense hash function to generate the same non-unique hash value for a plurality of unique keys, and wherein a total number of metadata containers is limited to a fraction of a total number of data objects or files stored in the at least one non-volatile storage media so that each of the metadata containers is associated with multiple unique keys for different data objects or files.

23. A non-transitory computer readable medium storing computer-executable instructions, wherein when the computer-executable instructions are executed by control circuitry of a Data Storage Device (DSD), the computer-executable instructions cause the control circuitry to:

create at least one container data structure that points to storage locations in at least one non-volatile storage media of the DSD that store data for data objects or files, wherein data container entries in the at least one container data structure point to storage locations for data having varying sizes with a minimum size that is less than a page size of the at least one non-volatile storage media;

receive a command to modify a data object or file stored in the at least one non-volatile storage media, wherein the command is byte-addressable for overwriting only a portion of the data object or file, deleting only a portion of the data object or file, or inserting new data into the data object or file stored in the at least one non-volatile storage media;

write the modified portion of the data object or file and an indication of a page container entry at a storage location in the at least one non-volatile storage media, wherein the page container entry is stored in the at least one container data structure and points to a previous storage location in the at least one non-volatile storage media for previously written data for the data obj ect or file that was most recently written before writing the modified portion; and

update a data container entry in the at least one container data structure for the data object or file to point to the storage location in the at least one non-volatile storage media storing the modified portion of the data object or file and the indication of the page container entry.

Assignments (10)

Continuity (2)

Cited By (1)

US 12,373,440