Parallel update to maintain coherency

• US 10,712,942 B2
• Filed: 11/09/2017
• Issued: 07/14/2020
• Est. Priority Date: 05/27/2015
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Pure Storage, Inc.
• Inventors: Gold, Brian T., Hayes, John, Lee, Robert
• Primary Examiner(s): Yi, David
• Assistant Examiner(s): Otto, Alan
• Application Number:
  US15/808,436
• Publication Number:
  US 20180067652A1
• Time in Patent Office: 978 Days
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/1441 for a range
• CPC Class Codes: G06F 2212/1032 Reliability improvement, data loss prevention, degraded operation etc
• CPC Class Codes: G06F 2212/7209 Validity control, e.g. using flags, time stamps or sequence numbers
• CPC Class Codes: G06F 3/0607 by facilitating the process of upgrading existing storage systems, e.g. for improving compatibility between host and storage device
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0638 Organizing or formatting or addressing of data
• CPC Class Codes: G06F 3/0655 Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices
• CPC Class Codes: G06F 3/0683 Plurality of storage devices
• CPC Class Codes: G06F 3/0685 Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays

Abstract

A method for updates in a storage system is provided. The method includes writing identifiers, associated with data to be stored, to storage units of the storage system and writing trim records indicative of identifiers that are allowed to not exist in the storage system to the storage units. The method includes determining whether stored data corresponding to records of identifiers is valid based on the records of the identifiers and the trim records.

Claims

1. A method, comprising:

writing sequence numbers, that are assigned to data or metadata update operations of a storage system, to memory in the storage system;

writing trim records that indicate sequence numbers allowed to be absent in the storage system, to the memory in the storage system;

determining a missing sequence number in the memory in the storage system;

determining whether the missing sequence number is consistent with read dependencies of the sequence numbers; and

writing a trim record to the memory, based on the missing sequence number and the determining whether the missing sequence number is consistent.

2. The method of claim 1, further comprising:

writing read dependencies of the sequence numbers to the memory in the storage system, wherein the determining the coherency is further based on the read dependencies.

3. The method of claim 1, further comprising:

determining one or more missing sequence numbers in the memory in the storage system.

4. The method of claim 1, further comprising:

determining a latest sequence number to which the storage system can be rolled forward in a recovery, based on the sequence numbers and the trim records.

5. The method of claim 1, further comprising:

determining coherency of data or system state of the storage system, based on the sequence numbers and the trim records.

6. The method of claim 1, further comprising:

performing updates to flash memory of the storage system, based on updates recorded with the sequence numbers in NVRAM (nonvolatile random-access memory) of the storage system; and

writing contents of the NVRAM, including the sequence numbers and the trim records, to the flash memory during a time span supported by backup power, responsive to power loss.

7. The method of claim 1, further comprising:

recovering the sequence numbers and the trim records from flash memory of the storage system, responsive to restoration of power after a power loss, wherein the storage system is comprised of multiple chassis.

8. A tangible, non-transitory, computer-readable media having instructions thereupon which, when executed by a processor, cause the processor to perform a method comprising:

assigning sequence numbers to data or metadata update operations of a storage system;

writing the sequence numbers, and trim records indicating sequence numbers that are allowed to be missing in the storage system, to memory in the storage system;

determining a sequence number that is missing in the memory in the storage system;

determining whether read dependencies of the sequence numbers, and the sequence number that is missing, are consistent; and

writing a trim record to the memory, based on the sequence number that is missing and a positive result of the determining.

9. The computer-readable media of claim 8, wherein the method further comprises:

determining read dependencies of at least a subset of the sequence numbers; and

writing the read dependencies to the memory.

10. The computer-readable media of claim 8, wherein the method further comprises:

determining at least one sequence number that is missing in the memory.

11. The computer-readable media of claim 8, wherein the method further comprises:

determining a sequence number to which to roll forward the storage system in a recovery, based on the sequence numbers and the trim records.

12. The computer-readable media of claim 8, wherein the method further comprises:

determining whether data or system state of the storage system is corrupted, based on the sequence numbers and the trim records.

13. The computer-readable media of claim 8, wherein the method further comprises:

writing contents of NVRAM (nonvolatile random-access memory) of the storage system, including the sequence numbers and the trim records, to flash memory of the storage system, supported by backup power, responsive to power loss; and

recovering the sequence numbers and the trim records from the flash memory, responsive to restoration of power after the power loss.

14. A storage system comprising:

at least one memory; and

one or more processors, configurable to;

record sequence numbers assigned to data or metadata update operations of a storage system, in the at least one memory;

write trim records indicative of sequence numbers allowed to be absent from the memory, to the memory;

determine a sequence number that is missing in the at least one memory;

determine whether the sequence number that is missing, and read dependencies of the sequence numbers, are consistent; and

writing a trim record to the at least one memory, based on determining that the sequence number that is missing, and the read dependencies of the sequence numbers, are consistent.

15. The storage system of claim 14, wherein the one or more processors are further configurable to write read dependencies of the sequence numbers to the at least one memory, wherein the storage system is comprised of multiple chassis.

16. The storage system of claim 14, wherein the one or more processors are further configurable to determine whether one or more sequence numbers is missing in the at least one memory.

17. The storage system of claim 14, wherein the one or more processors are further configurable to:

determine a latest sequence number for a recovery of the storage system, based on the sequence numbers and the trim records; and

roll forward the storage system to a system state in accordance with the determined latest sequence number.

18. The storage system of claim 14, wherein the one or more processors are further configurable to:

determine whether data or system state of the storage system is coherent, based on the sequence numbers and the trim records.

19. The storage system of claim 14, wherein:

the at least one memory comprises NVRAM (nonvolatile random-access memory) supported by backup power, and flash memory; and

the one or more processors are further configurable to;

perform the data or metadata update operations associated with the sequence numbers recorded in the NVRAM; and

write contents of the NVRAM, including the sequence numbers and the trim records, to the flash memory, responsive to power loss.

20. The storage system of claim 14, wherein:

the at least one memory comprises flash memory;

the one or more processors are further configurable to recover the sequence numbers and the trim records from the flash memory, responsive to restoration of power after a power loss.