Storage scheme for a distributed storage system

• US 10,579,276 B2
• Filed: 09/13/2017
• Issued: 03/03/2020
• Est. Priority Date: 09/13/2017
• Status: Active Grant

• Current Assignee: Rakuten Symphony Incorporated (Rakuten Group, Inc.)
• Original Assignee: Robin Systems, Inc. (Rakuten Group, Inc.)
• Inventors: Venkatesan, Dhanashankar, Seetala, Partha Sarathi
• Primary Examiner(s): Faal, Baboucarr
• Application Number:
  US15/703,803
• Publication Number:
  US 20190079679A1
• Time in Patent Office: 902 Days
• Field of Search: None
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/0665 at area level, e.g. provisioning of virtual or logical volumes
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

A storage scheme allocates portions of a logical volume to storage nodes in excess of the capacity of the storage nodes. Slices of the storage nodes and segments of slices are allocated in response to write requests such that actual allocation on the storage nodes is only in response to usage. Segments are identified with virtual segment identifiers that are retained when segments are moved to a different storage node. Logical volumes may therefore be moved seamlessly to different storage nodes to ensure sufficient storage capacity. Data is written to new locations in segments having space and a block map tracks the last segment to which data for a given address is written. Garbage collection is performed to free segments that contain invalid data, i.e. data for addresses that have been subsequently written to.

Claims

1. A method comprising:

assigning, by a storage manager computer system, at least a portion of a storage volume to a first storage node computer system;

receiving, by the first storage node computer system, write requests for the at least the portion of the storage volume;

allocating, by the first storage node computer system, a first segment of a plurality of segments on a first storage device of the first storage node computer system only in response to the write requests; and

writing, by the first storage node computer system, data from the write requests to the one or more segments, reassigning, by the storage manager computer system, the at least the portion of the storage volume to a second storage node computer system;

transferring, by the first storage node computer system, data from the first segment to the second storage node computer system;

allocating, by the second storage node computer system, a second segment of a second storage device of the second storage node computer system to the at least the portion of the storage volume; and

writing, by the second storage node computer system, the data from the first segment to the second segment;

wherein allocating the first segment of the first storage device further comprises mapping, by the first storage node computing device, the first segment to a virtual segment identifier; and

2 wherein allocating the second segment further comprises mapping, by the second storage node computing device, the second segment to the same virtual segment identifier.

2. The method of claim 1, further comprising:

assigning, by the storage manager computer system, the at least the portion of the storage volume to the first storage node computer system such that a sum of a size of the at least the portion of the storage volume and any other portions of at least one of the storage volume and one or more other storage volumes assigned to the first storage node computer system exceeds a storage capacity of the first storage node computer system.

3. The method of claim 1, further comprising:

determining, by the first storage node computer system, that the first storage node is full up to a threshold capacity; and

in response to determining that the first storage node is full up to the threshold capacity, invoking, by the first storage node computer system, the reassigning of the at least the portion of the storage volume to the second storage node computer system.

4. The method of claim 1, further comprising:

defining a segment map having a plurality of segment entries, each segment entry corresponding to a segment of a plurality of segments available for storage on the first storage device; and

processing a first write request of the write requests by;

determining that an entry in the segment map references the at least the portion of the storage volume and corresponds to a first segment having sufficient space for the data of the first write request; and

in response to determining that the entry in the segment map references the at least the portion of the storage volume and corresponds to the segment having sufficient space for the data of the first write request, writing the data of the first write request to the first segment.

5. The method of claim 4, further comprising processing, by the first storage node computer system, a second write request of the write requests by:

determining (a) that no entry in the segment map both of references the at least the portion of the storage volume and corresponds to a segment having sufficient space for the data of the second write request; and

in response to determining (a)—

selecting an unassigned segment from the plurality of segments;

adding a reference to the at least the portion of the storage volume to a segment entry of the segment map corresponding to the unassigned segment; and

writing the data of the second write request to the assigned segment.

6. The method of claim 5, further comprising

defining, by the storage manager computer system, a volume map for the storage volume, the volume map including a plurality of volume entries each mapping an offset within the storage volume to one of a plurality of storage nodes, the plurality of storage nodes including the first storage node computer system;

wherein assigning the at least a portion of a storage volume to the first storage node computer system comprises creating a volume entry including an offset corresponding to the at least the portion of the storage volume and a reference to the first storage node computer system.

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

writing, by the first storage node computer system, the data from the first write request at a first open position from a first end of the first segment; and

writing, by the first storage node computer system, a metadata entry to the first segment at an open position in an un-filled metadata index closest to a second end of the first segment opposite the first end, the metadata entry including a write address and size included in the first write request.

8. The method of claim 7, further comprising:

assigning a virtual segment identifier to the first segment according to a monotonically increasing virtual segment counter and recording the virtual segment identifier;

recording the virtual segment identifier in the entry for the first segment in the segment map.

9. The method of claim 8, further comprising:

receiving, by the first storage node computer system, a read request, the read request referencing the at least the portion of the storage volume and including a read address;

searching, by the first storage node computer system, metadata entries of one or more segments mapped to the at least the portion of the storage volume in the segment map;

identifying, by the first storage node computer system, a read segment of the plurality of segments that has a highest virtual segment identifier assigned thereto and that includes the read address in a metadata entry thereof; and

returning, by the first storage node computer system, data referenced by a last-written metadata entry referencing the read address in the read segment.

10. The method of claim 1, further comprising:

transmitting, by the storage manager computer system to the first storage node computer system, an instruction to delete the at least the portion of the storage volume;

receiving, by the first storage node computer system, the instruction and, in response to the instruction, marking as free all segments assigned to the at least the portion of the storage volume in a first segment map stored in a transitory memory device;

detecting, by the first storage node computer system, restarting of the first storage node computer system prior to updating a second segment map stored in a persistent storage device to match the first segment map, the persistent storage device including at least one of the first storage device and a different storage device;

in response to detecting restarting—

transmitting, by the first storage node computer system, a request to the storage manager computer system for a listing of assignments to the first storage node computer system; and

marking as free in the second segment map, by the first storage node computer system, all segments not mapped to any portion of a storage volume referenced in the listing of assignments.

11. A system comprising:

a storage manager computer system comprising one or more manager processing devices and one or more manager memory devices, the one or more manager memory devices storing manager executable code effective to cause the one or more manager processing devices to assign at least a portion of a storage volume to a first storage node computer system;

a first storage node computer system comprising one or more first processing devices and one or more first memory devices, the one or more first memory devices storing first executable code effective to cause the one or more first processing devices to;

receive write requests for the at least the portion of the storage volume;

allocate a first segment of a plurality of segments on a first storage device of the first storage node computer system only in response to the write requests; and

write data from the write requests to the one or more segments;

wherein the manager executable code is further effective to cause the one or more manager processing devices to transmit an instruction to the first storage node computer system, to reassign the at least the portion of the storage volume to a second storage node computer system;

wherein the first executable code is further effective to cause the one or more first processing devices to, in response to the instruction, transfer data from the first segment to the second storage node computer system;

wherein the second storage node computer system comprises one or more second processing devices and one or more second memory devices, the one or more second memory devices storing second executable code effective to cause the one or more second processing devices to;

allocate a second segment of a second storage device of the second storage node computer system to the at least the portion of the storage volume; and

write the data from the first segment to the second segment;

wherein the first executable code is further effective to cause the one or more first processing devices to allocate the first segment of the first storage device by mapping the first segment to a virtual segment identifier; and

wherein the second executable code is further effective to cause the one or more second processing devices to allocate the second segment of the second storage device by mapping the second segment to the same virtual segment identifier.

12. The system of claim 11, wherein the manager executable code is further effective to cause the one or more manager processing devices to:

assign the at least the portion of the storage volume to the first storage node computer system such that a sum of a size of the at least the portion of the storage volume and any other portions of at least one of the storage volume and one or more other storage volumes assigned to the first storage node computer system exceeds a storage capacity of the first storage node computer system.

13. The system of claim 11, wherein the first executable code is further effective to cause the one or more first processing devices to:

determine that the first storage node is full up to a threshold capacity; and

in response to determining that the first storage node is full up to the threshold capacity, invoke reassigning of the at least the portion of the storage volume to the second storage node computer system.

14. The system of claim 11, wherein the first executable code is further effective to cause the one or more first processing devices to:

define a segment map having a plurality of segment entries, each segment entry corresponding to a segment of a plurality of segments available for storage on the first storage device; and

process each write request of the write requests by;

if an entry in the segment map references the at least the portion of the storage volume and corresponds to a first segment having sufficient space for the data of the each write request, writing the data of the first write request to the first segment;

if no entry in the segment map both of references the at least the portion of the storage volume and corresponds to a segment of the plurality of segments having sufficient space for the data of the each write request, then—

selecting an unassigned segment from the plurality of segments;

adding a reference to the at least the portion of the storage volume to a segment entry of the segment map corresponding to the unassigned segment; and

writing the data of the each write request to the assigned segment.

15. The system of claim 14, wherein the manager executable code is further effective to cause the one or more manager processing devices to:

define a volume map for the storage volume, the volume map including a plurality of volume entries each mapping an offset within the storage volume to one of a plurality of storage nodes, the plurality of storage nodes including the first storage node computer system;

assign the at least a portion of a storage volume to the first storage node computer system by creating a volume entry including an offset corresponding to the at least the portion of the storage volume and a reference to the first storage node computer system.

16. The system of claim 14, wherein the first executable code is further effective to cause the one or more first processing devices to writing the data from the each write request to the first segment by:

writing the data from the each write request at a first open position from a first end of the first segment; and

writing a metadata entry to the first segment at an open position in an un-filled metadata index closest to a second end of the first segment opposite the first end, the metadata entry including a write address and size included in the each write request.

17. The system of claim 16, wherein the first executable code is further effective to cause the one or more first processing devices to writing the data from the each write request to the first segment by:

assigning a virtual segment identifier to the first segment according to a monotonically increasing virtual segment counter and recording the virtual segment identifier;

recording the virtual segment identifier in the entry for the first segment in the segment map.

18. The system of claim 17, wherein the first executable code is further effective to cause the one or more first processing devices to:

receive a read request, the read request referencing the at least the portion of the storage volume and including a read address;

search metadata entries of one or more segments mapped to the at least the portion of the storage volume in the segment map;

identify a read segment of the plurality of segments that has a highest virtual segment identifier assigned thereto and that includes the read address in a metadata entry thereof; and

return data referenced by a last-written metadata entry referencing the read address in the read segment.