SYSTEMS AND METHODS FOR PROVIDING NONLINEAR JOURNALING

• US 20110153569A1
• Filed: 02/25/2011
• Published: 06/23/2011
• Est. Priority Date: 08/18/2006
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Passey, Aaron J., Husted, Justin M., Godman, Peter J., Fachan, Neal T.
• Granted Patent: US 8,380,689 B2
• Time in Patent Office: Days
• US Class Current: 707/648
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 12/0804 with main memory updating G06F12/0806 takes precedence
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 12/123 with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0643 Management of files
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

In one embodiment, systems and methods are provided for nonlinear journaling. In one embodiment, groups of data designated for storage in a data storage unit are journaled into persistent storage. In one embodiment, the journal data is recorded nonlinearly. In one embodiment, a linked data structure records data and data descriptors in persistent storage.

Claims

1. A processor-implemented method of journaling data being written to a first storage unit, wherein said first storage unit is part of a system comprising a plurality of storage units that execute transactions global to the system, the method comprising:

storing a plurality of groups of data in a journal located in persistent storage, the data groups associated with data to be written to the first storage unit, wherein each data group is associated with a different global transaction and each global transaction is distributed among two or more storage units, such that each global transaction is associated with a request to write data to the first storage unit and a request to write different data to at least one other storage unit;

storing information about the location and status of each of said plurality of groups of data, wherein the information about the status of a group of data includes a transaction state of the associated global transaction;

providing a data structure associating the stored groups of data and the information about each of said stored groups of data; and

providing for the removal from the data structure of any data group and its corresponding stored information, wherein a data group can be removed from the data structure regardless of the order in which the data group was stored in the journal.

2. The processor-implemented method of claim 1, wherein associating the stored groups of data and the information about each of said stored groups of data comprises linking the stored groups of data and the information about each of said stored groups of data, wherein the removal of any data group and its corresponding stored information comprises unlinking the data group and its corresponding stored information.

3. The processor-implemented method of claim 2, further comprising linking two or more remaining data groups after unlinking the data group and its corresponding stored information.

4. The processor-implemented method of claim 1, wherein providing for the unlinking of a data group of the stored groups of data comprises:

determining that the transaction state of the associated global transaction indicates that the associated global transaction is done; and

determining that all data writes associated with the associated global transaction and the first storage unit have been written to the first storage unit.

5. The processor-implemented method of claim 1, wherein said data structure is updated with atomic writes.

6. The processor-implemented method of claim 1, wherein said data structure is one of the following:

linked list, two-dimensional linked list, linked list of multiple-dimensional linked lists, binary tree, and b tree.

7. The processor-implemented method of claim 1, wherein said data structure comprises a list of transaction descriptors comprising said information about the status of each of said plurality of groups of data, said transaction descriptors further comprising a pointer to a list of block descriptors comprising said information about the location of each of said plurality of groups of data.

8. The processor-implemented method of claim 1, wherein each group of data is associated with a disk block on a hard-disk drive, and wherein said information about the location of each of said plurality of groups of data comprises information identifying a hard-disk drive and a disk block on said hard-disk drive.

9. The processor-implemented method of claim 1, further comprising modifying said data structure to do at least one of the following, said modifying not causing removal of said groups of data or said information about each of said groups of data:

reduce the amount of space occupied and defragment occupied space.

10. The processor-implemented method of claim 1, further comprising replaying the storage unit with said stored groups of data and said information about each of said groups of data.

11. A journal data structure for recording data to be written to a data storage unit, comprising:

a plurality of journal blocks, wherein each journal block of the plurality of journal blocks comprises data to be written to the data storage unit;

a plurality of block descriptors, each block descriptor comprising a link to at least one of said journal blocks and at least one respective address in the data storage unit to which the at least one journal block is to be written; and

a plurality of transaction descriptors, each transaction descriptor comprising a link to one or more of the plurality of block descriptors, wherein the one or more of the plurality of block descriptors are associated with a given transaction.

12. The data structure of claim 11, wherein each transaction is a global transaction that is distributed among two or more data storage units, such that each global transaction is associated with a request to write data to the data storage unit and a request to write different data to at least one other data storage unit.

13. The data structure of claim 11, wherein said journal blocks are one of the following sizes:

512 bytes and 8196 bytes.

14. The data structure of claim 11, wherein at least one of the plurality of block descriptors further comprises a link to at least one other block descriptor of said plurality of block descriptors.

15. The data structure of claim 11, wherein at least one of the plurality of transaction descriptors further comprises a link to at least one other transaction descriptor of said plurality of transaction descriptors.

16. The data structure of claim 11, wherein each of the plurality of transaction descriptors comprises information identifying a transaction state and one or more data storage units participating in the associated transaction.

17. The data structure of claim 11, wherein said link to at least one of said journal blocks and said link to at least one of said block descriptors each comprise an address in persistent memory associated with the data storage unit.

18. A system for journaling data to be written to a data storage node, comprising:

a processor;

persistent memory configured to store journal data; and

a journal module configured to;

record, in the associated persistent memory, a plurality of journal blocks, wherein each journal block of the plurality of journal blocks comprises data to be written to the data storage node;

record a plurality of block descriptors, each block descriptor comprising a link to at least one of said journal blocks and at least one respective address in the data storage node to which the at least one journal block is to be written; and

record a plurality of transaction descriptors, each transaction descriptor comprising a link to one or more of the plurality of block descriptors, wherein the one or more of the plurality of block descriptors are associated with a given transaction.

19. The system of claim 18, wherein each transaction is a global transaction that is distributed among two or more data storage nodes, such that each global transaction is associated with a request to write data to the data storage node and a request to write different data to at least one other data storage node.

20. The system of claim 18, wherein each of the plurality of transaction descriptors comprises information identifying a transaction state and one or more data storage nodes participating in the associated transaction.