Systems and methods for providing nonlinear journaling

• US 7,899,800 B2
• Filed: 08/18/2006
• Issued: 03/01/2011
• Est. Priority Date: 08/18/2006
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Isilon Systems Incorporated (Dell Technologies Inc.)
• Inventors: Husted, Justin M., Passey, Aaron J., Godman, Peter J., Fachan, Neal T.
• Primary Examiner(s): Trujillo; James
• Assistant Examiner(s): Singh; Amresh
• Application Number:
  US11/506,597
• Publication Number:
  US 20080046443A1
• Time in Patent Office: 1,656 Days
• Field of Search: 707/202, 707/100, 707/704, 711/154
• US Class Current: 707/704
• 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 nonlinear 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, 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 a first data group associated with a first global transaction is stored prior to a second data group associated with a second global transaction being stored, and the second data group is stored prior to a third data group associated with a third global transaction being stored, wherein the second global transaction is distributed among two or more storage units, such that the second 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 linking the stored groups of data and the information about each of said groups of data, wherein the first data group is linked to the second data group, and the second data group is linked to the third data group; and

providing for the unlinking of any data group and its corresponding stored information, without regards to the order in which the data group was stored in the journal, wherein providing for the unlinking comprises;

determining that the transaction state of the second global transaction indicates that the second global transaction is done, and further determining that all data writes associated with the second global transaction and the first storage unit have been written to the first storage unit;

linking the first data group to the third data group; and

unlinking the second data group.

2. The method of claim 1, wherein said data structure is updated with atomic writes.

3. The 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.

4. The 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.

5. The method of claim, 1 wherein said information about the status of each of said plurality of groups of data further comprises information about the participants of said global transaction.

6. The method of claim 1, wherein said unlinking of any data group corresponds to a determination that a group of data is the least recently written group of data.

15. The method of claim 1, wherein unlinking the second data group comprises removing a link from the first data group to the second data group and removing a link from the second data group to the third data group.

7. A system for journaling data writes into a linked data structure in conjunction with storage of the data writes, comprising:

a first data storage unit, wherein said first data storage unit is part of a system comprising a plurality of data storage units that execute transactions global to the system;

persistent memory associated with said first data storage unit;

a program module configured to journal into a linked data structure in said persistent memory data writes to said first data storage unit, said data writes comprising data to be written to said first data storage unit and respective locations in said first data storage unit to write said data, said data writes associated with a first global transaction, a second global transaction and a third global transaction, wherein a first entry associated with the first global transaction is stored in the linked data structure prior to a second entry associated with the second global transaction being stored, the second entry is stored in the linked data structure prior to a third entry associated with the third global transaction being stored, wherein the first entry comprises a link to the second entry in the linked data structure, and the second entry comprises a link to the third entry in the linked data structure, wherein each entry is associated with status information comprising a transaction state of the associated global transaction, wherein the second global transaction is distributed among two or more data storage units, such that the second global transaction is associated with a request to write data to the first data storage unit and a request to write different data to at least one other data storage unit, wherein said program module is configured to journal said data writes nonlinearly; and

a process module configured to;

determine that the transaction state of the second global transaction indicates that the second global transaction is done, and further determine that the data writes associated with the second global transaction and the first data storage unit have been written to said first data storage unit;

link the first entry to the third entry; and

unlink the second entry.

8. The system of claim 7, wherein said linked 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.

9. The system of claim 7, wherein said linked data structure is modified with atomic writes to said persistent memory.

10. The system of claim 7, wherein said links comprise addresses in said persistent memory.

11. The system of claim 7, wherein said program module being configured to journal said data writes nonlinearly comprises being configured to record said data writes such that said data and said respective locations are recorded in nonlinear locations in persistent memory.

12. The system of claim 7, wherein said program module configured to journal said data writes nonlinearly comprises being configured to record the first entry and the second entry in nonlinear locations in persistent memory.

13. The system of claim 7, wherein said status information further comprises information identifying respective participants of said global transaction.

14. The system of claim 7, wherein said program module is further configured to free from said persistent memory space allocated to journal said data following confirmation that said data storage unit has stored said data at said respective locations.

16. The system of claim 7, wherein unlinking the second entry comprises removing a link from the first entry to the second entry and removing a link from the second entry to the third entry.

17. The system of claim 7, wherein the process module is further configured to determine that the data writes associated with the first transaction have not been written to said data storage unit.