Transaction log layout for efficient reclamation and recovery

• US 9,952,765 B2
• Filed: 10/06/2015
• Issued: 04/24/2018
• Est. Priority Date: 10/01/2015
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Krishnamachari, Srinath, Pundir, Anshul, Babu, Sriranjani
• Primary Examiner(s): Wilson, Yolanda L
• Application Number:
  US14/876,572
• Publication Number:
  US 20170097873A1
• Time in Patent Office: 931 Days
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 11/1474 in transactions G06F16/20 takes precedence
• CPC Class Codes: G06F 11/3476 Data logging G06F11/14, G06F11/2205 take precedence
• CPC Class Codes: G06F 2201/805 Real-time
• CPC Class Codes: G06F 2201/85 Active fault masking without idle spares active fault masking without idle spare hardware where processing functionality is redundant G06F11/2035
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays

Abstract

A layout of a transaction log enables efficient logging of metadata into entries of the log, as well as efficient reclamation and recovery of the log entries by a volume layer of a storage input/output (I/O) stack executing on one or more nodes of a cluster. The transaction log is illustratively a two stage, append-only logging structure, wherein the first level is non-volatile random access memory (NVRAM) embodied as a NVlog and the second stage is disk, e.g., solid state drive (SSD). During crash recovery, the log entries are examined for consistency and scanned to identify those entries that have completed and those that are active, which require replay. The log entries are walked from oldest to newest (using sequence numbers) searching for the highest sequence number. Partially complete log entries (e.g., log entries in-progress when a crash occurs) may be discarded for failing a checksum (e.g., a CRC error). Old value/new value logs may be used to implement roll-forward or roll-back semantics to replay the log entries and fix any on-disk data structures, first from NVRAM and then from on-disk logs.

Claims

1. A method comprising:

receiving at a storage system an input/output (I/O) request, wherein the storage system includes a persistent memory coupled to a central processor (CPU) and one or more storage devices;

associating a transaction with the I/O request;

allocating a circular log from the persistent memory to a first finite state machine (FSM) for processing the transaction, the first FSM associated with a token identifier (ID);

logging a start entry in the circular log;

in response to processing the transaction, recording one or more entries to the circular log, each recorded entry including a sequence number and a token ID field;

in response to a crash of the storage system, scanning the recorded entries of the circular log to determine whether the first FSM is active at a time of the crash; and

in response to determining that the first FSM is active at the time of the crash, replaying the recorded entries of the circular log having the token ID as a value of the token ID field.

2. The method of claim 1 wherein scanning the recorded entries further comprises:

discarding the recorded entries failing a checksum.

3. The method of claim 2 wherein discarding the recorded entries failing the checksum further comprises:

scanning the circular log to identify a magic number so as to determine a next recorded entry, wherein each recorded entry includes the magic number.

4. The method of claim 1 wherein scanning the recorded entries further comprises:

adding the first FSM and a second FSM to a shadow structure, the second FSM associated with a sentinel value indicating that the second FSM is closed; and

removing each recorded entry having the sentinel value as the value of the token ID field.

5. The method of claim 1 wherein scanning the recorded entries further comprises:

making a first pass through the recorded entries to identify the first FSM as active at the time of the crash; and

making a second pass through the recorded entries to determine a highest sequence number of the recorded entries.

6. The method of claim 5 wherein making the second pass through the recorded entries further comprises:

determining whether a current sequence number of a respective entry of the recorded entries is lower than a previous sequence number of a prior respective entry; and

in response to determining that the current sequence number of the respective entry of the recorded entries is lower than the previous sequence number of the prior respective entry, assigning the previous sequence number as the highest sequence number.

7. The method of claim 1 wherein the persistent memory is one of a non-volatile random access memory and a solid state drive.

8. The method of claim 1 wherein replaying the recorded entries of the circular log further comprises:

applying one of an old value log and a new value log to each replay entry of the circular log.

9. The method of claim 8 wherein applying the old value log further comprises:

restarting the first FSM.

10. The method of claim 8 wherein applying the new value log further comprises:

applying the new value log to a first replay entry of the circular log; and

ensuring that replay of first replay entry is idempotent.

11. A system comprising:

a storage array having one or more storage devices; and

a node having a central processor (CPU) connected to a memory, a persistent memory and the storage array, the CPU configured to execute one or more processes stored in the memory, the one or more processes configured to;

receive at a storage system an input/output (I/O) request;

associate a transaction with the I/O request;

allocate a circular log from the persistent memory to a first finite state machine (FSM) for processing the transaction, the first FSM associated with a token identifier (ID);

log a start entry in the circular log;

in response to processing the transaction, record one or more entries to the circular log, each recorded entry including a sequence number and a token ID field;

in response to a crash of the storage system, scan the recorded entries of the circular log to determine whether the first FSM is active at a time of the crash; and

in response to determining that the first FSM is active at the time of the crash, replay the recorded entries of the circular log having the token ID as a value of the token ID field.

12. The system of the claim 11 wherein the one or more processes configured to scan the recorded entries is further configured to:

discard the recorded entries failing a checksum.

13. The system of claim 12 wherein the one or more processes configured to discard the recorded entries failing the checksum is further configured to:

scan the circular log to identify a magic number so as to determine a next recorded entry, wherein each recorded entry includes the magic number.

14. The system of claim 11 wherein the one or more processes configured to scan the recorded entries is further configured to:

add the first FSM and a second FSM to a shadow structure, the second FSM associated with a sentinel value indicating that the second FSM is closed; and

remove each recorded entry having the sentinel value as the value of the token ID field.

15. The system of claim 11 wherein the one or more processes configured to scan the recorded entries is further configured to:

make a first pass through the recorded entries to identify the first FSM as active at the time of the crash; and

make a second pass through the recorded entries to determine a highest sequence number of the recorded entries.

16. The system of claim 15 wherein the one or more processes configured to make the second pass through the recorded entries is further configured to:

determine whether a current sequence number of a respective entry of the recorded entries is lower than a previous sequence number of a prior respective entry; and

in response to determining that the current sequence number of the respective entry of the recorded entries is lower than the previous sequence number of the prior respective entry, assign the previous sequence number as the highest sequence number.

17. The system of claim 11 wherein the persistent memory is one of a non-volatile random access memory and a solid state drive.

18. The system of claim 11 wherein the one or more processes configured to replay the recorded entries of the circular log is further configured to:

apply one of an old value log and a new value log to each replay entry of the circular log.

19. The system of claim 18 wherein the one or more processes configured to apply the new value log is further configured to:

apply the new value log to a first replay entry of the circular log; and

ensure that replay of first replay entry is idempotent.

20. A non-transitory computer readable medium including program instructions for execution on one or more processors, the program instructions configured to:

implement a storage input/output (I/O) stack that operates with a persistent

memory coupled to the one or more processors and with one or more solid state drives (SSDs);

receive an I/O request;

associate a transaction with the I/O request;

allocate a circular log from the persistent memory to a finite state machine (FSM) for processing the transaction, the FSM associated with a token identifier (ID);

log a start entry in the circular log;

in response to processing the transaction, record one or more entries to the circular log, each recorded entry including a sequence number and a token ID field;

in response to a crash of the storage I/O stack, scan the recorded entries of the circular log to determine whether the FSM is active at a time of the crash; and

in response to determining that the FSM is active at the time of the crash, replay the recorded entries of the circular log having the token ID as a value of the token ID field.