Sequence invalidation consolidation in a storage system

Patent metadata

Field	Value
Publication number	US-11449485-B1
Application number	US-201715641011-A
Country	US
Kind code	B1
Filing date	Jul 3, 2017
Priority date	Mar 30, 2017
Publication date	Sep 20, 2022
Grant date	Sep 20, 2022

Abstract

A method for tracking valid and invalid sequence numbers in a storage system, performed by a processor, is provided. The method includes establishing a table as a key value store in memory in the storage system. The table has sequence numbers as keys and represents valid sequence numbers and invalidated sequence numbers of an open-ended sequence relating to storage of data or metadata in the storage system. The method includes adding to the table an entry that records a first plurality of consecutive sequence numbers, as a first range-valued key associated with a first value indicating the first plurality of consecutive sequence numbers is valid. The method includes adding to the table an entry that records a deletion of a second plurality of consecutive sequence numbers, as a second range-valued key associated with a second value indicating the second plurality of consecutive sequence numbers is invalid.

First claim

What is claimed is:

1. A method comprising:
establishing a first table in the storage system, the first table having sequence numbers as keys and representing valid sequence numbers and invalidated sequence numbers of an open-ended sequence relating to storage of data in the storage system;
establishing a plurality of second tables in the storage system, wherein each one of the plurality of second tables is associated with a corresponding authority of the storage system and the first table, each of the plurality of second tables records a range of sequence numbers owned by the corresponding authority;
adding to one of the second tables an entry that records a first plurality of consecutive sequence numbers, as a first range-valued key associated with a first value indicating the first plurality of consecutive sequence numbers is valid; and
adding to the one of the second tables an entry that records a deletion of a second plurality of consecutive sequence numbers, as a second range-valued key associated with a second value indicating the second plurality of consecutive sequence numbers is invalid.

2. The method of claim 1 , further comprising:
adding to the one of the second tables an entry that records a third plurality of consecutive sequence numbers, as a third range-valued key associated with a third value indicating a highest valued sequence number in the third plurality of consecutive sequence numbers is a most recent issued sequence number.

3. The method of claim 1 , further comprising:
adding to the one of the second tables one or more newer entries that combine two or more older entries in the first table; and
deleting the two or more older entries from the first table.

4. The method of claim 1 , further comprising:
adding newer entries to a bottom or end of the one of the second tables; and
searching for a most recent issued sequence number, starting from the bottom or end of the one of the second tables.

5. The method of claim 1 , further comprising:
adding to the one of the second tables an entry that records an additional sequence number, as a single-valued key associated with a value indicating the additional sequence number is valid.

6. The method of claim 1 , further comprising:
adding to the one of the second tables an entry that records a deletion of an additional sequence number, as a single-valued key associated with a value indicating the additional sequence number is invalid.

7. The method of claim 1 , further comprising:
adding to the one of the second tables an entry that records an additional sequence number, as a single-valued key or a portion of a range-valued key associated with a value indicating a create time for a bucket, an object, or an instance of an object, with the bucket, the object or the instance represented by the additional sequence number.

8. The method of claim 1 , further comprising:
adding to the one of the second tables an entry that records an additional sequence number representing an object, as a single-valued key or a portion of a range-valued key associated with a value indicating an object name.

9. The method of claim 1 , wherein the one of the second tables represents sequences of logical addresses or segment identifiers for user data.

10. A tangible, non-transitory, computer-readable media having instructions thereupon which, when executed by a processor, cause the processor to perform a method comprising:
establishing a first table in the storage system, the first table having sequence numbers as keys and representing valid sequence numbers and invalidated sequence numbers of an open-ended sequence relating to storage of data in the storage system;
establishing a plurality of second tables in the storage system, wherein each one of the plurality of second tables is associated with a corresponding authority of the storage system and the first table, each of the plurality of second tables records a range of sequence numbers owned by the corresponding authority;
adding to one of the second tables an entry that records a first plurality of consecutive sequence numbers, as a first range-valued key associated with a first value indicating the first plurality of consecutive sequence numbers is valid; and
adding to the one of the second tables an entry that records a deletion of a second plurality of consecutive sequence numbers, as a second range-valued key associated with a second value indicating the second plurality of consecutive sequence numbers is invalid.

11. The computer-readable media of claim 10 , wherein the method further comprises:
adding to the one of the second tables an entry that records a third plurality of consecutive sequence numbers, as a third range-valued key associated with a third value indicating a highest valued sequence number in the third plurality of consecutive sequence numbers is a most recent issued sequence number.

12. The computer-readable media of claim 10 , wherein the method further comprises:
adding to the first table an entry that coalesces two or more entries in the table; and deleting the two or more entries from the first table that are coalesced by the entry.

13. The computer-readable media of claim 10 , wherein the method further comprises:
adding one or more entries to a bottom of the one of the second tables; and
searching for a most recent issued sequence number, starting from the bottom or end of the one of the second tables.

14. The computer-readable media of claim 10 , wherein:
sequence numbers in the one of the second tables represent buckets, objects or instances of objects; and
values in the one of the second tables, associated with sequence numbers, indicate creation times or names.

15. The computer-readable media of claim 10 , wherein sequence numbers in the one of the second tables represent logical addresses or segment identifiers for user data.

16. A storage system, comprising:
a memory;
one or more processors configurable to establish a first table in the memory, the first table having sequence numbers as keys and representing valid sequence numbers and invalidated sequence numbers of an open-ended sequence relating to storage of data in the storage system, the one or more processors configurable to establish a plurality of second tables in the storage system, wherein each one of the plurality of second tables is associated with a corresponding authority of the storage system and the first table, each of the plurality of second tables records a range of sequence numbers owned by the corresponding authority;
the one or more processors configurable to add to one of the second tables a first range-valued key associated with a first value indicating validity, representing a first plurality of consecutive sequence numbers that is valid; and
the one or more processors configurable to add to the one of the second tables a second range-valued key associated with a second value indicating invalidity, representing a second plurality of consecutive sequence numbers that is invalidated.

17. The storage system of claim 16 , further comprising:
the one or more processors configurable to add to the one of the second tables a third single-valued key associated with a third value indicating validity, representing a third sequence number that is valid; and
the one or more processors configurable to add to the one of the second tables a fourth single-valued key associated with a fourth value indicating invalidity, representing a fourth sequence number that is invalidated.

18. The storage system of claim 16 , further comprising:

Assignees

• Pure Storage Inc

Inventors

• Lee Robert
• Sandvig Cary A

Classifications

• Y02D10/00

  Energy efficient computing, e.g. low power processors, power management or thermal management · CPC title

• G06F3/0665

  at area level, e.g. provisioning of virtual or logical volumes · CPC title

• G06F3/0623

  in relation to content · CPC title

• G06F3/0631

  by allocating resources to storage systems · CPC title

• G06F12/1425 Primary

  the protection being physical, e.g. cell, word, block · CPC title