System and method of implementing a table storage support scheme

• US 10,359,937 B2
• Filed: 11/18/2014
• Issued: 07/23/2019
• Est. Priority Date: 12/20/2013
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Inventors: Rozental, Roman
• Primary Examiner(s): Rossiter, Sean D
• Assistant Examiner(s): Wu, Stephanie
• Application Number:
  US14/546,995
• Publication Number:
  US 20150177988A1
• Time in Patent Office: 1,708 Days
• Field of Search: None
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 16/128 Details of file system snapshots on the file-level, e.g. snapshot creation, administration, deletion use of snapshots for error detection or correction G06F11/14, G06F11/16
• CPC Class Codes: G06F 16/2308 Concurrency control transaction processing G06F9/466
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 21/1088 by using transactions with atomicity, consistency, or isolation and durability [ACID] properties
• CPC Class Codes: G06F 3/0607 by facilitating the process of upgrading existing storage systems, e.g. for improving compatibility between host and storage device
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G06F 9/466 Transaction processing

Abstract

A data storage device may be configured to update a table used by a host device, such as a table stored at the data storage device. For, example, the data storage device may generate and store an updated version of a portion of the table. A storage location of the updated version of the portion may be tracked using a data structure that corresponds to a second version of the table. The second version of the table may be discarded or made accessible to the host device responsive to an indicator detected by the data storage device.

Claims

1. A data storage device comprising:

a memory configured to store;

a table that includes a plurality of pages; and

a first data structure including address information for a first page of the table, wherein the address information indicates the first page corresponds to a first set of logical addresses, wherein the first data structure includes address information for less than all of the plurality of pages; and

a controller operatively coupled to the memory, wherein the controller is configured to;

reserve multiple sets of logical addresses associated with the table to enable storage of multiple versions of the first page of the table, the multiple sets including the first set of logical addresses, a second set of logical addresses, and a third set of logical addresses;

responsive to initiation of a transaction, generate a second data structure by copying the first data structure;

update the second data structure to include updated address information corresponding to the first page of the table, wherein the updated address information indicates that the first page corresponds to the second set of logical addresses; and

receive a commit indicator or an abort indicator, wherein the commit indicator makes a first version of the table obsolete and a second version of the table available to the host, wherein the second version of the table is an update of the first version of the table, wherein the abort indicator makes the second version of the table obsolete and the first version of the available to the host, and wherein the commit indicator processes the second version of the table based on whether a transaction is a non-nested transaction or a nested transaction.

2. The data storage device of claim 1, wherein the controller is further configured to update the first version of the table to generate the second version of the table based on an update to at least one page of the table, the second version of the table generated without generation of a copy of non-updated pages of the table, and wherein the second version of the table includes the update to the at least one page of the table and the non-updated pages.

3. The data storage device of claim 1, wherein:

the table comprises a byte table,

a table update request that corresponds to the transaction is received from a host device, and

the table update request identifies a byte value of the byte table.

4. The data storage device of claim 1, further comprising a second memory included in the controller, wherein the second memory is configured to store the second data structure and is distinct from the memory.

5. The data storage device of claim 1, wherein the first page of the plurality of pages is associated with a corresponding page number.

6. The data storage device of claim 1, wherein:

a table update request received during the transaction includes an offset value, and

the controller is further configured to translate the offset value into a first page number and to modify the first page based on the table update request.

7. The data storage device of claim 1, wherein the controller is further configured to:

open the transaction; and

open a second transaction.

8. The data storage device of claim 7, wherein:

the second transaction comprises a nested transaction, and

the second transaction occurs during the transaction.

9. The data storage device of claim 1, wherein the memory stores a committed data structure that corresponds to the first version of the table.

10. The data storage device of claim 1, wherein the controller is further configured to:

determine a first location of the first page in the memory in response to a table update request; and

read the first page from the first location in the memory.

11. The data storage device of claim 1, wherein the controller is further configured to:

modify the first page to generate an updated version of the first page; and

write the updated version of the first page to a second location of the memory.

12. The data storage device of claim 1, wherein the controller is further configured to receive the commit indicator or the abort indicator from a host device.

13. The data storage device of claim 1, wherein the controller is further configured to:

open the transaction that includes a table update request; and

close the transaction.

14. The data storage device of claim 1, wherein the memory includes:

a three-dimensional (3D) memory configuration that is monolithically formed in one or more physical levels of arrays of memory cells having an active area disposed above a silicon substrate; and

circuitry associated with operation of the memory cells.

15. The data storage device of claim 1, wherein the controller is further configured to, after the second data structure is updated, determine whether to replace the first data structure with the updated second data structure.

16. The data storage device of claim 15, wherein:

the controller is further configured to receive the commit indicator or the abort indicator from a host device, and

a determination of whether to replace the first data structure with the updated second data structure is based on whether the controller received the commit indicator or the abort indicator.

17. The data storage device of claim 1, wherein the controller is further configured to, in response to receipt of the commit indicator, replace the first data structure with the updated second data structure.

18. The data storage device of claim 1, wherein the controller is further configured to, in response to receipt of the abort indicator, maintain the first data structure in the memory as a committed data structure of the table.

19. The data storage device of claim 1, wherein the controller is further configured to, during the transaction and after the second data structure is updated:

open a second transaction; and

generate a third data structure by copying the updated second data structure.

20. The data storage device of claim 19, wherein:

the controller is further configured to, during the second transaction, update the third data structure to include second updated address information corresponding to the first page of the table, and

the second updated address information indicates that the first page corresponds to the third set of logical addresses.

21. A method of managing a table, the method comprising:

in a data storage device including a controller and a memory, wherein the memory stores a table that includes a plurality of pages, performing;

responsive to initiation of a transaction, copying a first data structure to generate a second data structure, the first data structure including address information for a first page of the table, wherein the address information indicates the first page corresponds to a first set of logical addresses of multiple sets of logical addresses, wherein the first data structure includes address information for less than all of the plurality of pages;

updating the second data structure to include updated address information corresponding to the first page of the table, wherein the updated address information indicates that the first page corresponds to a second set of logical addresses of the multiple sets of logical addresses;

generating a third data structure including updated address information that indicates the first page corresponds to a third set of logical addresses of the multiple sets of logical addresses; and

receiving a commit indicator or an abort indicator, wherein the commit indicator makes a first version of the table obsolete and a second version of the table available to the host, wherein the second version of the table is an update of the first version of the table, wherein the abort indicator makes the second version of the table obsolete and the first version of the table available to the host, and wherein the commit indicator processes the second version of the table based on whether a transaction is a non-nested transaction or a nested transaction.

22. The method of claim 21, wherein a table update request that identifies a byte value of the table is received from a host device, and further comprising determining a particular page associated with the table based on the byte value.

23. The method of claim 21, further comprising, after updating the second data structure, determining whether to replace the first data structure with the updated second data structure.

24. The method of claim 21, wherein each set of logical addresses of the multiple sets of logical addresses is associated with a corresponding logical block address range.

25. The method of claim 21, wherein the first set of logical addresses comprises a set of consecutive logical addresses.

26. The method of claim 21, wherein:

the memory includes a three-dimensional (3D) memory configuration that is monolithically formed in one or more physical levels of arrays of memory cells having an active area disposed above a silicon substrate; and

the data storage device includes circuitry associated with operation of the memory cells.

27. A device comprising:

means for storing a table that includes a plurality of pages and for storing a first data structure including address information for a first page of the table, wherein the address information indicates the first page corresponds to a first set of logical addresses of multiple sets of logical addresses, wherein the first data structure includes address information for less than all of the plurality of pages;

means for generating a second data structure as a copy of the first data structure responsive to initiation of a transaction;

means for updating the second data structure to include updated address information corresponding to the first page of the table, wherein the updated address information indicates that the first page corresponds to a second set of logical addresses of the multiple sets of logical addresses;

means for generating a third data structure as a copy of the updated second data structure and for updating the third data structure to include second updated address information that indicates the page corresponds to a third set of logical addresses of the multiple sets of logical addresses; and

means for receiving a commit indicator or an abort indicator, wherein the commit indicator makes a first version of the table obsolete and a second version of the table available to the host, wherein the second version of the table is an update of the first version of the table, wherein the abort indicator makes the second version of the table obsolete and the first version of the table available to the host, and wherein the commit indicator processes the second version of the table based on whether a transaction is a non-nested transaction or a nested transaction.

28. The device of claim 27, further comprising means for reserving the first set of logical addresses, the second set of logical addresses, and the third set of logical addresses for storing multiple versions of one or more pages of the table without reserving physical memory blocks for multiple versions of the first page of the table.

29. The device of claim 27, wherein the table comprises a byte table, and further comprising means for receiving a table update request that identifies a byte value of the byte table.

30. The device of claim 27, further comprising means for determining whether to commit or abort the updated second data structure.