Methods for detecting out-of-order sequencing during journal recovery and devices thereof

Patent metadata

Field	Value
Publication number	US-9934110-B2
Application number	US-201615145273-A
Country	US
Kind code	B2
Filing date	May 3, 2016
Priority date	May 3, 2016
Publication date	Apr 3, 2018
Grant date	Apr 3, 2018

Abstract

A method, non-transitory computer readable medium and storage server computing device that allocates monotonically increasing sequence numbers to storage operations based on an order of the storage operations corresponding entries in a log. The storage operations are sequenced including by identifying a subset of the storage operations that are parallelizable. A file system data structure is allocated and populated with data associated with one of the storage operations. A determination is made when a rollback is detected based on whether a replay ledger index field of the file system data structure comprises one of the sequence numbers that is greater than another one of the sequence number corresponding to the one of the storage operations. The another one of the sequence numbers is inserted into the replay ledger index field, when the determining indicates that a rollback is not detected.

First claim

What is claimed is:

1. A method, comprising:
allocating, by a computing device, a plurality of sequence numbers to each of a plurality of storage operations based on an order of the storage operations in a log;
sequencing, by the computing device, the storage operations comprising identifying a subset of the storage operations that are parallelizable;
allocating, by the computing device, at least one file system data structure and populating the file system data structure with data associated with one of the storage operations;
determining, by the computing device, when a rollback is detected based on a comparison of one of the sequence numbers in a replay ledger index field of the file system data structure with another one of the sequence numbers, the one of the sequence numbers corresponding to another one of the storage operations and the another one of the sequence numbers corresponding to the one of the storage operations; and
inserting, by the computing device, the another one of the sequence numbers into the replay ledger index field of the file system data structure, when the determining indicates that a rollback is not detected.

2. The method of claim 1 , further comprising inducing, by the computing device, a panic state comprising resequencing the storage operations based on the order of the storage operations in the log and replaying the storage operations in serial, when the determining indicates that a rollback is detected.

3. The method of claim 2 , wherein the one of the storage operations and the another one of the storage operations are included in the subset of the storage operations that are parallelizable.

4. The method of claim 1 , wherein the allocating, populating, determining, and inserting together comprise replaying the one of the storage operations and the method further comprises repeating, by the computing device, the replaying for each other of the storage operations.

5. The method of claim 1 , further comprising translating, by the computing device, each of the storage operations into one of a plurality of native file system messages, wherein the allocating further comprises tagging the native file system messages with the sequence numbers and the another one of the sequence numbers is tagged to one of the native file system messages translated from the one of the storage operations.

6. The method of claim 1 , wherein the file system data structure comprises a buffer, the buffer corresponds to a file block number, and the one of the storage operations and another one of the storage operations both comprise operations to modify file data or metadata at a storage location corresponding to the file block number.

7. A non-transitory machine readable medium having stored thereon instructions for detecting out-of-order sequencing during journal recovery comprising machine executable code which when executed by at least one machine causes the machine to:
allocate a plurality of sequence numbers to each of a plurality of storage operations based on an order of the storage operations in a plurality of corresponding entries in a log;
sequence the storage operations comprising identifying a subset of the storage operations that are parallelizable;
allocate at least one file system data structure and populate the file system data structure with data associated with one of the storage operations;
determine when a rollback is detected based on a comparison of one of the sequence numbers in a replay ledger index field of the file system data structure with another one of the sequence numbers, the one of the sequence numbers corresponding to another one of the storage operations and the another one of the sequence numbers corresponding to the one of the storage operations; and
insert the another one of the sequence numbers into the replay ledger index field of the file system data structure, when the determining indicates that a rollback is not detected.

8. The non-transitory machine readable medium of claim 7 , wherein the machine executable code when executed by the machine further causes the machine to induce a panic state, resequence the storage operations based on the order of the storage operations in the log, replay the storage operations in serial, when the determining indicates that a rollback is detected.

9. The non-transitory machine readable medium of claim 8 , wherein the one of the storage operations and the another one of the storage operations are included in the subset of the storage operations that are parallelizable.

10. The non-transitory machine readable medium of claim 7 , wherein the allocating, populating, determining, and inserting together comprise replaying the one of the storage operations and the machine executable code when executed by the machine further causes the machine to repeat the replaying for each other of the storage operations.

11. The non-transitory machine readable medium of claim 7 , wherein the machine executable code when executed by the machine further causes the machine to:
translate each of the storage operations into one of a plurality of native file system messages; and
tag the native file system messages with the sequence numbers, wherein the another one of the sequence numbers is tagged to one of the native file system messages translated from the one of the storage operations.

12. The non-transitory machine readable medium of claim 7 , wherein the file system data structure comprises a buffer, the buffer corresponds to a file block number, and the one of the storage operations and another one of the storage operations both comprise operations to modify file data or metadata at a storage location corresponding to the file block number.

13. A computing device, comprising:
a memory containing machine readable medium comprising machine executable code having stored thereon instructions for detecting out-of-order sequencing during journal recovery; and
a processor coupled to the memory, the processor configured to execute the machine executable code to cause the processor to:
allocate a plurality of sequence numbers to each of a plurality of storage operations based on an order of the storage operations in a plurality of corresponding entries in a log;
sequence the storage operations comprising identifying a subset of the storage operations that are parallelizable;
allocate at least one file system data structure and populate the file system data structure with data associated with one of the storage operations;
determine when a rollback is detected based on a comparison of one of the sequence numbers in a replay ledger index field of the file system data structure with another one of the sequence numbers, the one of the sequence numbers corresponding to another one of the storage operations and the another one of the sequence numbers corresponding to the one of the storage operations; and
insert the another one of the sequence numbers into the replay ledger index field of the file system data structure, when the determining indicates that a rollback is not detected.

14. The computing device of claim 13 , wherein the processor is further configured to execute the machine executable code to further cause the processor to induce a panic state, resequence the storage operations based on the order of the storage operations in the log, replay the storage operations in serial, when the determining indicates that a rollback is detected.

15. The computing device of claim 14 , wherein the one of the storage operations and the another one of the storage operations are included in the subset of the storage operations that are parallelizable.

Assignees

• Netapp Inc

Inventors

• Brown Joseph

Classifications

• G06F2201/805

  Real-time · CPC title

• G06F3/067

  Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS] · CPC title

• G06F11/1469 Primary

  Backup restoration techniques · CPC title

• G06F2201/80

  Database-specific techniques · CPC title

• G06F3/0619

  in relation to data integrity, e.g. data losses, bit errors · CPC title