Snapshot deletion in a distributed storage system

• US 10,430,292 B2
• Filed: 12/19/2017
• Issued: 10/01/2019
• Est. Priority Date: 12/19/2017
• Status: Active Grant

• Current Assignee: Robin Systems, Inc. (Rakuten Group, Inc.)
• Original Assignee: Robin Systems, Inc. (Rakuten Group, Inc.)
• Inventors: Mukku, Jagadish K., Venkatesan, Dhanashankar, Patel, Ripulkumar Hemantbhai
• Primary Examiner(s): Rossiter, Sean D
• Application Number:
  US15/847,693
• Publication Number:
  US 20190188090A1
• Time in Patent Office: 651 Days
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

A new snapshot of a storage volume is created by instructing computing nodes to suppress write requests. Once pending write requests from the computing nodes are completed, storage nodes create a new snapshot for the storage volume by allocating a new segment to the new snapshot and finalizes and performs garbage collection with respect to segments allocated to the previous snapshot. The snapshots may be represented by a storage manager in a hierarchy. Deleted snapshots may be flagged as such in the hierarchy and deletion may be implemented only in memory on a storage node, which is then restored from the hierarchy in the event of a crash. A snapshot is removed from the hierarchy when all segments previously are freed by garbage collection. A hybrid storage node may perform both computing and storage services. Data may be written with tags indicating encoding protocols used to encode the data.

Claims

1. A method comprising:

storing, by a storage manager computer, a hierarchy of snapshots S(i), i=1 to N, N being a number of snapshots, for a storage volume;

receiving, by the storage manager computer, an instruction to delete a snapshot S(j) in the snapshot;

updating, by the storage manager computer, the hierarchy to indicate that snapshot S(j) is deleted while retaining reference to S(j) in the hierarchy; and

transmitting, to a storage node, an instruction to delete the snapshot S(j);

(a) in response to the instruction to delete the snapshot S(j), mapping segments of a storage device assigned to snapshot S(j) to snapshot S(j+1) in a segment map stored in a memory of the storage node without updating a copy of the segment map stored in the storage device;

(b) detecting, by the storage node, restarting of the storage node;

in response to (b);

loading, by the storage node, the segment map from the storage device into the memory of the storage node;

requesting, by the storage node, the hierarchy from the storage manager computer;

determining (c) that the snapshot S(j) is indicated as deleted in the hierarchy; and

in response to determining (c), again performing (a).

2. The method of claim 1, further comprising:

performing, by the storage node, garbage collection with respect to snapshot S(j+1);

determining, by the storage node that (b) all segments of the storage device assigned to snapshot S(j) in the copy of the segment map stored in the storage device have been freed as a result of performing the garbage collection;

in response to determining (b), transmitting, by the storage node, a notification to the storage manager computer; and

in response to the notification, deleting, by the storage manager, the reference to snapshot S(j) in the hierarchy.

3. A method comprising:

storing, by a storage manager computer, a hierarchy of snapshots S(i), i=1 to N, N being a number of snapshots, for a storage volume;

receiving, by the storage manager computer, an instruction to delete a snapshot S(j) in the snapshot;

updating, by the storage manager computer, the hierarchy to indicate that snapshot S(j) is deleted while retaining reference to S(j) in the hierarchy; and

transmitting, to a storage node, an instruction to delete the snapshot S(j);

(a) in response to the instruction to delete the snapshot S(j), mapping segments of a storage device assigned to snapshot S(j) to snapshot S(j+1) in a segment map stored in a memory of the storage node without updating a copy of the segment map stored in the storage device;

performing, by the storage node, garbage collection with respect to snapshot S(j+1);

determining, by the storage node that (b) all segments of the storage device assigned to snapshot S(j) in the copy of the segment map stored in the storage device have been freed as a result of performing the garbage collection;

in response to determining (b), transmitting, by the storage node, a notification to the storage manager computer; and

in response to the notification, deleting, by the storage manager, the reference to snapshot S(j) in the hierarchy

prior to receiving the instruction to delete the snapshot S(j);

receiving, by the storage node, a first write instruction referencing snapshot S(j), the snapshot S(j) being a current snapshot;

writing, by the storage node, first data from the first write instruction to a first segment mapped to the snapshot S(j) in a segment map;

receiving, by the storage node, a new snapshot instruction;

in response to the new snapshot instruction, mapping, by the storage node, a second segment to a snapshot S(j+1);

receiving, by the storage node, subsequent to the new snapshot instruction, a second write instruction; and

writing, by the storage node, second data from the second write instruction to the second segment.

4. The method of claim 3, further comprising:

receiving, by the storage node, a read instruction referencing the snapshot S(j+1);

searching, by the storage node, for reference to a first address in the read instruction in any of (a) the second segment and (b) any other segments mapped to the snapshot S(j+1) in the segment map;

determining, by the storage node, that the first address is not referenced in either of (a) or (b);

in response to determining that the first address is not referenced in either of (a) or (b), searching, by the storage node, for reference to the first address in any of (c) the first segment and (d) any other segments mapped to the snapshot S(j) in the segment map;

determining, by the storage node, that there is a reference to the first address in one of (c) and (d); and

in response to determining that there is a reference to the first address in one of (c) and (d), returning, by the storage node, data corresponding to the first address that was written latest to either of (c) or (d).

5. The method of claim 4, wherein writing the first data from the first write instruction to the first segment comprises:

writing, by the storage node, the first data to a first free location closest to a first end of the first segment; and

writing, by the storage node, a metadata entry to a second free location in an index written at a second end of the current segment opposite the first end, the metadata entry including an address included in the first write instruction;

wherein searching for reference to the first address in any of (c) and (d) comprises searching, by the storage node, the index of the first segment and any indexes of (d).

6. The method of claim 5, wherein performing garbage collection with respect to the snapshot S(j+1) comprises, for each address referenced in the index of segments in the segment map mapped to the first segment, identifying, by the storage node, valid data corresponding to a latest writing to the each address in a last segment assigned to the snapshot S(j+1) that has the each address in the index thereof.

7. The method of claim 6, wherein performing garbage collection with respect to the snapshot S(j+1) comprises, for each segment mapped to the snapshot S(j+1) in the segment map:

comparing, by the storage node, an amount of valid data in the each segment to a threshold;

determining, by the storage node, that the amount of valid data does not exceed the threshold;

in response to determining that the amount of valid data does not exceed the threshold, (a) writing, by the storage node, the valid data to a different segment mapped to the snapshot S(j+1) and having space for the valid data and (b) freeing the each segment to be over written.

8. The method of claim 7,

executing one or more user applications on an application computing device remote from the storage node and storage manager computer;

receiving, by the application computing device, the first and second write instructions;

transmitting, by the application computing device, the first and second write instructions to the storage node.

9. A storage system comprising:

a plurality of storage nodes; and

a storage manager computer programmed to;

store a hierarchy of snapshots S(i), i=1 to N, N being a number of snapshots, for a storage volume;

receive an instruction to delete a snapshot S(j) in the snapshot;

update the hierarchy to indicate that snapshot S(j) is deleted while retaining reference to S(j) in the hierarchy; and

transmit an instruction to delete the snapshot S(j) to one or more storage nodes of the plurality of storage nodes;

wherein each storage node of the one or more storage nodes of the plurality of storage nodes are programmed to;

(a) in response to the instruction to delete the snapshot S(j), map segments of a storage device assigned to snapshot S(j) to snapshot S(j+1) in a segment map stored in a memory of the each storage node without updating a copy of the segment map stored in the storage device; and

wherein each storage node of the one or more storage nodes of the plurality of storage nodes are further programmed to;

(b) detect restarting of the each storage node;

in response to (b);

load the segment map stored in the storage device into the memory;

request the hierarchy from the storage manager computer;

determine (c) that the snapshot S(j) is indicated as deleted in the hierarchy; and

in response to determining (c), again perform (a).

10. The system of claim 9, wherein each storage node of the one or more storage nodes of the plurality of storage nodes are further programmed to:

perform garbage collection with respect to snapshot S(j+1);

determine that (b) all segments of the storage device assigned to snapshot S(j) in the copy of the segment map stored in the storage device have been freed as a result of performing garbage collection; and

in response to determining (b), transmit a notification to the storage manager computer that snapshot S(j) is no longer in use; and

wherein the storage manager is further programmed to;

in response to the notification, delete the reference to snapshot S(j) in the hierarchy.

11. A storage system comprising:

a plurality of storage nodes; and

a storage manager computer programmed to;

store a hierarchy of snapshots S(i), i=1 to N, N being a number of snapshots, for a storage volume;

receive an instruction to delete a snapshot S(j) in the snapshot;

update the hierarchy to indicate that snapshot S(j) is deleted while retaining reference to S(j) in the hierarchy; and

transmit an instruction to delete the snapshot S(j) to one or more storage nodes of the plurality of storage nodes;

wherein each storage node of the one or more storage nodes of the plurality of storage nodes are programmed to;

(a) in response to the instruction to delete the snapshot S(j), map segments of a storage device assigned to snapshot S(j) to snapshot S(j+1) in a segment map stored in a memory of the each storage node without updating a copy of the segment map stored in the storage device;

wherein each storage node of the one or more storage nodes of the plurality of storage nodes are further programmed to;

perform garbage collection with respect to snapshot S(j+1);

determine that (b) all segments of the storage device of the each storage node assigned to snapshot S(j) in the copy of the segment map stored in the storage device have been freed as a result of performing garbage collection; and

in response to determining (b), transmit a notification to the storage manager computer that snapshot S(j) is no longer in use; and

wherein the storage manager is further programmed to, in response to the notification, delete the reference to snapshot S(j) in the hierarchy; and

wherein each storage node of the one or more storage nodes of the plurality of storage nodes are further programmed to;

receive a first write instruction referencing snapshot S(j), the snapshot S(j) being a current snapshot;

write first data from the first write instruction to a first segment mapped to the snapshot S(j) in a segment map;

receive a new snapshot instruction;

in response to the new snapshot instruction, map a second segment to a snapshot S(j+1);

receive, subsequent to the new snapshot instruction, a second write instruction; and

write second data from the second write instruction to the second segment.

12. The system of claim 11, wherein each storage node of the one or more storage nodes of the plurality of storage nodes are further programmed to:

receive a read instruction referencing the snapshot S(j+1);

search for reference to a first address in the read instruction in any of (a) the second segment and (b) any other segments mapped to the snapshot S(j+1) in the segment map;

determine that the first address is not referenced in either of (a) or (b);

in response to determining that the first address is not referenced in either of (a) or (b), search for reference to the first address in any of (c) the first segment and (d) any other segments mapped to the snapshot S(j) in the segment map;

determine that there is a reference to the first address in one of (c) and (d); and

in response to determining that there is a reference to the first address in one of (c) and (d), return data corresponding to the first address that was written latest to either of (c) or (d).

13. The system of claim 12, wherein each storage node of the one or more storage nodes of the plurality of storage nodes are further programmed to:

write the first data from the first write instruction to the first segment by;

writing the first data to a first free location closest to a first end of the first segment; and

writing a metadata entry to a second free location in an index written at a second end of the current segment opposite the first end, the metadata entry including an address included in the first write instruction; and

search for reference to the first address in any of (c) and (d) by searching the index of the first segment and any indexes of (d).

14. The system of claim 13, wherein each storage node of the one or more storage nodes of the plurality of storage nodes are further programmed to perform garbage collection with respect to the snapshot S(j+1) by, for each address referenced in the index of segments in the segment map mapped to the first segment, identifying valid data corresponding to a latest writing to the each address in a last segment assigned to the snapshot S(j+1) that has the each address in the index thereof.

15. The system of claim 14, wherein each storage node of the one or more storage nodes of the plurality of storage nodes are further programmed to perform garbage collection with respect to the snapshot S(j+1) by, for each segment mapped to the snapshot S(j+1) in the segment map:

comparing an amount of valid data in the each segment to a threshold;

determining that the amount of valid data does not exceed the threshold;

in response to determining that the amount of valid data does not exceed the threshold, (a) writing the valid data to a different segment mapped to the snapshot S(j+1) and having space for the valid data and (b) freeing the each segment to be over written.

16. The system of claim 15, further comprising one or more application computing devices each executing one or more user applications and being remote from the storage node and the storage manager computer, each application computing device being programmed to:

receive the first and second write instructions; and

transmit the first and second write instructions to a storage node of the one or more storage nodes.