Systems and methods for providing nonlinear journaling

• US 20080046443A1
• Filed: 08/18/2006
• Published: 02/21/2008
• 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: Husted, Justin M., Passey, Aaron J., Godman, Peter J., Fachan, Neal T.
• Granted Patent: US 7,899,800 B2
• Time in Patent Office: Days
• US Class Current: 707/100
• 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 storage unit comprising:

storing a plurality of groups of data in a journal located in persistent storage;

storing information about the location and status of each of said plurality of groups of data;

providing a data structure linking the stored groups of data and the information about each of said groups of data; 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.

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 each of said plurality of groups of data is associated with a transaction, and wherein said information about the status of each of said plurality of groups of data comprises information about the state of the associated transaction.

6. The method of claim 5, wherein said transaction is global to a distributed system of storage units, and 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.

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

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

9. The method of claim 1, wherein said unlinking is in response to a confirmation that the storage unit has stored a group of data at the corresponding location.

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

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

12. The method of claim 1, further comprising preserving data of any data group as a shadow buffer for a data block in memory that corresponds to said data group, said data block being overwritten with a new data group.

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

a data storage unit;

persistent memory associated with said data storage unit; and

a program module configured to journal in said persistent memory data writes to said data storage unit, said data writes comprising data to be written to said data storage unit and respective locations in said data storage unit to write said data;

wherein said program module is configured to journal said data writes nonlinearly.

14. The system of claim 13, wherein said program module configured to journal data writes nonlinearly comprises being configured to journal data writes into a linked data structure.

15. The system of claim 14, 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.

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

17. The system of claim 14, wherein said linked data structure comprises links, said links comprising addresses in said persistent memory.

18. The method of claim 14, said program module further configured to modify said linked data structure to do at least one of the following:

reduce the amount of space said linked data structure occupies and defragment the space said linked data structure occupies.

19. The system of claim 13, wherein said data are data blocks and said respective locations are data block addresses.

20. The system of claim 19, 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.

21. The system of claim 13, wherein subsets of said data writes correspond to respective separate transactions, and wherein said program module being configured to journal said data writes nonlinearly comprises being configured to record data writes within said subsets in nonlinear locations in persistent memory.

22. The system of claim 13, wherein subsets of said data writes correspond to respective separate transactions, and said program module configured to journal said data writes nonlinearly comprises being configured to record said subsets in nonlinear locations in persistent memory.

23. The system of claim 13, wherein subsets of said data writes correspond to respective separate transactions, and wherein said program module is further configured to journal in said persistent memory information about said respective separate transactions, said information comprising information identifying respective transaction states.

24. The system of claim 23, wherein said information is modified with atomic writes to said persistent memory.

25. The system of claim 23, wherein a transaction subset of said respective separate transactions are global to a distributed system of data storage units comprising said data storage unit, and wherein said information about said respective separate transactions further comprises information identifying respective participants of said global transaction subset.

26. The system of claim 13, 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.

27. The system of claim 13, wherein said program module is further configured to free from said persistent memory space allocated to journal said data following a determination that said data is the least recently written data.

28. The system of claim 13, wherein said program module is further configured to replay said data storage unit using said data and said respective locations.

29. The system of claim 13, wherein said program module is further configured to preserve any of said data as a shadow buffer for a memory buffer, said memory buffer corresponding to said any data and said memory buffer being overwritten with new data.

30. The system of claim 13, wherein said persistent memory is nonvolatile random access memory.

31. The system of claim 13, wherein said data storage unit comprises an array of hard-disk drives, and said locations comprise identifiers for hard-disk drives in said array and disk block addresses for respective said hard-disk drives.

32. The system of claim 13, wherein said persistent memory is located on said data storage unit, and said program module is executed on said data storage unit.

34. The data structure of claim 13, further comprising a journal descriptor comprising an identifier available for a next transaction and a link to one of said plurality of transaction descriptors.

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

512 bytes and 8196 bytes.

36. The data structure of claim 13, wherein said each block descriptor further comprises a link to at least one of said plurality of block descriptors.

37. The data structure of claim 13, wherein said each block descriptor further comprises a link to at least one of said plurality of block descriptors.

38. The data structure of claim 13, wherein said each transaction descriptor further comprises a link to at least one of said plurality of transaction descriptors, an identifier identifying a transaction state, and identifiers identifying participants in a transaction.

39. The data structure of claim 13, wherein said link to at least one of said journal blocks and said link to at least one of said block descriptors are respective addresses in persistent memory associated with the data storage unit.

41. The method of claim 13, wherein said data and said locations are journaled in nonlinear locations in said persistent memory.

33. A journal data structure for recording data writes in conjunction with storage of data writes in a data storage unit, comprising:

a plurality of journal blocks comprising data;

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 associated with said at least one journal block; and

a plurality of transaction descriptors, each transaction descriptor comprising a link to at least one of said block descriptors.

40. A method of journaling data into a linked data structure in conjunction with storage of the data in a data storage unit, comprising:

journaling data in persistent memory;

journaling in persistent memory a location in the data storage unit, said location corresponding to said data; and

linking said data and said location.

42. A method of journaling data into a linked data structure in conjunction with storage of the data in a data storage unit, comprising:

journaling data in persistent memory;

journaling in persistent memory a location in the data storage unit, said location corresponding to said data; and

associating said data and said location;

wherein said data and said location are recorded in nonlinear locations in said persistent memory.