SYSTEM AND METHOD OF IMPLEMENTING A TABLE STORAGE SUPPORT SCHEME

• US 20150177988A1
• Filed: 11/18/2014
• Published: 06/25/2015
• Est. Priority Date: 12/20/2013
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Sandisk Technologies Incorporated (Western Digital Corporation)
• Inventors: ROZENTAL, ROMAN
• Granted Patent: US 10,359,937 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 first memory storing a table, wherein the table includes a plurality of pages, wherein each page of the plurality of pages is the same size, and wherein the first memory is a non-volatile memory; and

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

reserve a portion of a logical memory address space associated with the first memory, wherein the portion of the logical memory space is used to maintain multiple versions of each page of the table, and

store, in the first memory, an updated version of a page of the table based on a table update request, wherein the updated version of the page is stored in the first memory at a location identified by an address within the portion of the logical memory address space.

2. The data storage device of claim 1, wherein the controller is further configured to update a first version of the table to generate a second version of the table based on updating at least one page of the table without generating a copy of non-updated pages of the table, wherein the second version of the table includes the updated 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, wherein the table update request is received from a host device, and wherein the table update request received from the host device 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 distinct from the first memory, and wherein the controller is further configured to update a data structure stored in the second memory to identify the updated version of the page.

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

6. The data storage device of claim 1, wherein the table update request includes an offset value, and wherein the controller is configured to translate the offset value into a page number.

7. The data storage device of claim 1, wherein the controller is configured to open a first transaction and to open a second transaction.

8. The data storage device of claim 7, wherein the second transaction is a nested transaction, and wherein the second transaction occurs during the first transaction.

9. The data storage device of claim 1, wherein the first memory stores a committed data structure that corresponds to a 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 page in the first memory in response to the table update request and to read the page from the first location of the first memory.

11. The data storage device of claim 1, wherein the controller is further configured to modify the page to generate the updated version of the page and to write the updated version of the page to a second location of the first memory.

12. The data storage device of claim 1, wherein the portion of the logical memory address space includes a first sub-portion and a second sub-portion.

13. The data storage device of claim 1, wherein the controller is further configured to store data in a second memory of the data storage device, wherein the data identifies the updated version of the page.

14. The data storage device of claim 13, wherein the data is stored in a data structure stored in the second memory, wherein the data structure includes an entry for each page of the table, and wherein, for each page of the table, the entry points to a corresponding sub-portion of the portion of the logical memory address space.

15. The data storage device of claim 14, wherein the controller is further configured to generate the data structure as a copy of another data structure, and wherein the data structure is associated with a different version of the table than the other data structure.

16. The data storage device of claim 14, wherein the controller is further configured to receive a commit indicator or an abort indicator from a host device, wherein, in response to receiving the commit indicator, the controller is configured to store the data structure into the first memory, and wherein, in response to receiving the abort indicator, the controller is configured to discard the data structure.

17. The data storage device of claim 13, wherein the controller is further configured to open a transaction that includes the table update request and to close the transaction, wherein closing the transaction is associated with committing or aborting an update to the table based on the table update request.

18. The data storage device of claim 1, wherein the first 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 wherein the first memory includes circuitry associated with operation of the memory cells.

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

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

receiving a table update request associated with the table stored in the first memory;

identifying, based on the table update request, a first sub-portion of a reserved portion of a logical memory address space of the first memory, wherein the reserved portion of the logical memory space is used to maintain multiple versions of each page of the table, wherein the first sub-portion identifies a first address of the first memory, and wherein a first version of a particular page of the table to be modified based on the table update request is stored in the first memory at the first address;

modifying the first version of the particular page to generate a second version of the particular page based on the table update request; and

determining, based on the first sub-portion, a second sub-portion of the reserved portion, wherein the second sub-portion identifies a second address of the first memory to store the second version of the particular page.

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

21. The method of claim 20, further comprising:

accessing, based on the particular page, a particular entry of a data structure stored in a second memory of the data storage device, wherein the data structure includes an entry for each page of the table, and wherein, for each page of the table, the entry points to a corresponding sub-portion of the reserved portion;

determining a particular sub-portion of the reserved portion that is pointed to by the particular entry, wherein the particular sub-portion includes the first sub-portion; and

updating the particular entry to point to the second sub-portion based on the table update request.

22. The method of claim 19, wherein the reserved portion of the logical memory address space includes multiple sub-portions, wherein a number of addresses in each sub-portion is the same as a number of pages in the table, and wherein the multiple sub-portions include the first sub-portion and the second sub-portion.

23. The method of claim 22, wherein each sub-portion of the multiple sub-portions is associated with a corresponding logical block address range.

24. The method of claim 19, wherein the first sub-portion and the second sub-portion are associated with a sequential order.

25. The method of claim 24, further comprising identifying the second sub-portion as a next sub-portion of the first sub-portion based on the sequential order.

26. The method of claim 19, wherein the first 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 wherein the data storage device includes circuitry associated with operation of the memory cells.

27. A method comprising:

in a host device coupled to a data storage device having a first version of a table including a plurality of pages, performing;

sending an open transaction command to the data storage device to cause the data storage device to open a transaction;

sending a table update request to the data storage device during the transaction, wherein the table update request instructs the data storage device to modify a first version of a particular page of the table to generate a second version of the particular page and to update a particular entry of a data structure in the data storage device that corresponds to the particular page, the update for identifying the second version of the particular page; and

sending a close transaction command to the data storage device.

28. The method of claim 27, wherein the table update request is associated with a read-modify-write operation.

29. The method of claim 27, wherein the transaction is a nested transaction.

30. The method of claim 27, wherein the close transaction command includes a commit indicator or an abort indicator, wherein, when the close transaction command includes the abort indicator, the data storage device discards the data structure, and wherein, when the transaction command includes the commit indicator, the data storage device identifies the data structure as a committed data structure.