Granted Patent B2

US 9,311,006 · App. 12/492,104 · Granted Apr 12, 2016

Abstract

Claims (53)

1. A method of table journaling in a flash storage device comprising a volatile memory and a plurality of non-volatile data blocks, the method comprising the steps of:

creating a first copy, in a first one or more of the plurality of non-volatile data blocks, of an addressing table stored in the volatile memory;

maintaining, for each of the first one or more non-volatile data blocks, a respective indicator in the volatile memory for indicating whether a portion of the addressing table stored in the non-volatile data block has been changed since the portion was last stored in the non-volatile data block;

writing, based on a first schedule, transaction log data to a second one or more of the plurality of non-volatile data blocks, wherein the transaction log data comprises information about data operations performed in at least one of the plurality of non-volatile data blocks different than the second one or more of the plurality of non-volatile data blocks;

in response to the second one or more of the plurality of non-volatile data blocks having been filled with transaction log data, updating one or more portions of the first copy of the addressing table stored in the first one or more of the non-volatile data blocks indicated in the volatile memory as being changed, the updating based on changes made to the addressing table stored in the volatile memory since the one or more portions were last stored in the non-volatile data block; and

writing, to a third one or more of the plurality of non-volatile data blocks based on a second schedule separate from the first schedule, pending operation data from an ordered list indicative of blocks associated with upcoming data operations and not represented in the transaction log data.

2. The method according to claim 1 , wherein the second one or more of the plurality of non-volatile data blocks are pre-allocated for transaction log data.

3. The method according to claim 1 , wherein the transaction log data comprises information about a next one or more of the plurality of data blocks in which data operations are to be performed.

4. The method according to claim 1 , further comprising the steps of:

creating a second copy in a third one or more of the plurality of non-volatile data blocks of the addressing table stored in the volatile memory; and

writing transaction log data to a fourth one or more of the plurality of non-volatile data blocks,

wherein the step of updating the first copy of the addressing table is performed after the fourth one or more of the plurality of non-volatile data blocks have been filled with transaction log data.

5. The method according to claim 4 , further comprising the step of:

erasing the transaction log data in the second one or more of the plurality of non-volatile data blocks after updating the first copy of the addressing table.

6. The method according to claim 1 , further comprising the step of:

maintaining a list indicating which of the first one or more of the plurality of data blocks contains outdated information based upon the changes to the addressing table stored in the volatile memory.

7. The method according to claim 6 , wherein the step of updating the first copy of the addressing table comprises overwriting, with corresponding portions of the addressing table stored in the volatile memory, those data blocks of the first one or more of the plurality of data blocks indicated by the list as containing outdated information.

8. The method according to claim 1 , further comprising the step of:

after a power loss, rebuilding the addressing table stored in the volatile memory by updating the first copy of the addressing table stored in the first one or more of the plurality of non-volatile data blocks with the transaction log data stored in the second one or more of the plurality of non-volatile data blocks.

9. The method according to claim 8 , wherein the transaction log data comprises information about a next one or more of the plurality of data blocks in which data operations were to be performed before the power loss, further comprising the steps of:

scanning the next one or more of the plurality of data blocks to locate transactions not stored in the transaction log data; and

updating the addressing table stored in the volatile memory based on the located transactions.

10. A flash storage device comprising:

a volatile memory;

a plurality of non-volatile data blocks; and

a controller configured to:

create a first copy, in a first one or more of the plurality of non-volatile data blocks, of an addressing table stored in the volatile memory;

maintaining, for each of the first one or more non-volatile data blocks, a respective indicator in the volatile memory for indicating whether a portion of the addressing table stored in the non-volatile data block has been changed since the portion was last stored in the non-volatile data block;

write, based on a first schedule, transaction log data to a second one or more of the plurality of non-volatile data blocks, wherein the transaction log data comprises information about data operations performed in at least two of the plurality of non-volatile data blocks different than the second one or more of the plurality of non-volatile data blocks;

in response to the second one or more of the plurality of non-volatile data blocks having been filled with transaction log data, update one or more portions of the first copy of the addressing table stored in the first one or more of the non-volatile data blocks indicated in the volatile memory as being changed, the updating based on changes made to the addressing table stored in the volatile memory since the one or more portions were last stored in the non-volatile data block; and

write, to a third one or more of the plurality of non-volatile data blocks based on a second schedule separate from the first schedule, pending operation data from an ordered list indicative of blocks associated with upcoming data operations and not represented in the transaction log data.

11. The flash storage device according to claim 10 , wherein the second one or more of the plurality of non-volatile data blocks are pre-allocated for transaction log data.

12. The flash storage device according to claim 10 , wherein the transaction log data comprises information about a next one or more of the plurality of data blocks in which data operations are to be performed.

13. The flash storage device according to claim 10 , wherein the processor is further configured to:

create a second copy in a third one or more of the plurality of non-volatile data blocks of the addressing table stored in the volatile memory; and

write transaction log data to a fourth one or more of the plurality of non-volatile data blocks,

wherein the controller is configured to perform the step of updating the first copy of the addressing table after the fourth one or more of the plurality of non-volatile data blocks have been filled with transaction log data.

14. The flash storage device according to claim 13 , wherein the controller is further configured to:

erase the transaction log data in the second one or more of the plurality of non-volatile data blocks after updating the first copy of the addressing table.

15. The flash storage device according to claim 10 , wherein the controller is further configured to:

maintain a list indicating which of the first one or more of the plurality of data blocks contains outdated information based upon the changes to the addressing table stored in the volatile memory.

16. The flash storage device according to claim 15 , wherein the controller is configured to update the first copy of the addressing table by overwriting, with corresponding portions of the addressing table stored in the volatile memory, those data blocks of the first one or more of the plurality of data blocks indicated by the list as containing outdated information.

17. The flash storage device according to claim 10 , wherein the controller is further configured to:

after a power loss, rebuild the addressing table stored in the volatile memory by updating the first copy of the addressing table stored in the first one or more of the plurality of non-volatile data blocks with the transaction log data stored in the second one or more of the plurality of non-volatile data blocks.

18. The flash storage device according to claim 17 , wherein the transaction log data comprises information about a next one or more of the plurality of data blocks in which data operations were to be performed before the power loss, and wherein the controller is further configured to:

scan the next one or more of the plurality of data blocks to locate transactions not stored in the transaction log data; and

update the addressing table stored in the volatile memory based on the located transactions.

19. A non-transitory machine-readable medium comprising instructions stored therein for table journaling in a flash storage device having a volatile memory and plurality of non-volatile data blocks, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

creating a first copy, in a first one or more of the plurality of non-volatile data blocks, of an addressing table stored in the volatile memory;

maintaining, for each of the first one or more non-volatile data blocks, a respective indicator in the volatile memory for indicating whether a portion of the addressing table stored in the non-volatile data block has been changed since the portion was last stored in the non-volatile data block;

writing, based on a first schedule, transaction log data to a second one or more of the plurality of non-volatile data blocks, wherein the transaction log data comprises information about data operations performed in at least two of the plurality of non-volatile data blocks different than the second one or more of the plurality of non-volatile data blocks;

in response to the second one or more of the plurality of non-volatile data blocks having been filled with transaction log data, updating one or more portions of the first copy of the addressing table stored in the first one or more of the non-volatile data blocks indicated in the volatile memory as being changed, the updating based on changes made to the addressing table stored in the volatile memory since the one or more portions were last stored in the non-volatile data block; and

writing, to a third one or more of the plurality of non-volatile data blocks and based on a second schedule separate from the first schedule, pending operation data from an ordered list indicative of blocks associated with upcoming data operations and not represented in the transaction log data.

Assignments (12)