Storage scheme for a distributed storage system

• US 10,430,105 B2
• Filed: 09/13/2017
• Issued: 10/01/2019
• 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): Choe, Yong J
• Application Number:
  US15/703,719
• Publication Number:
  US 20190079692A1
• Time in Patent Office: 748 Days
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• 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]

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 storage system comprising:

a storage node comprising a storage device, one or more processing devices, and one or more memory devices operably coupled to the one or more processing devices, the one or more memory devices storing executable code effective to cause the one or more 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 storage device; and

process a plurality of write requests, each write request referencing a storage volume and including write data and a write address;

wherein the executable code is further effective to cause the one or more processing devices to process each write request of the plurality of write requests by—

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

if no entry in the segment map both references the storage volume and corresponds to a segment having sufficient space for the write data of the each write request, (a) selecting an unassigned segment from the plurality of segments, (b) adding a reference to the storage volume referenced by the each write request to a segment entry of the segment map corresponding to the unassigned segment of the plurality of segments, and (c) writing the write data of the each write request to the assigned segment.

2. The storage system of claim 1, wherein the executable code effective to cause the one or more processing devices to define a slice map including a plurality of slice entries, each slice entry having a corresponding slice identifier and representing a portion of the storage device;

the one or more processing devices are further programmed to process the each write request by;

obtaining a logical offset from the each write request; and

if no entry in the slice map corresponds to the offset, writing the logical offset to a slice entry of the plurality of slice entries;

wherein adding the reference to the storage volume referenced by the each write request to the segment entry of the segment map corresponding to the assigned segment of the plurality of segments comprises adding a slice identifier corresponding to the entry of the slice map to which the logical offset was written to the segment entry of the segment map corresponding to the assigned segment.

3. The storage system of claim 1, further comprising a storage manager in data communication with the storage node, the storage manager being a computing device programmed to:

store a volume map, the volume map including a plurality of offset entries each offset entry mapping the offset from each write request to the storage node of the plurality of storage nodes by which each write request was processed.

4. The storage system of claim 1, wherein the executable code is further effective to cause the one or more processing devices to write the write data of the each write request to the assigned segment by:

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

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

5. The storage system of claim 4, wherein the executable code is further effective to cause the one or more processing devices to process the plurality of write requests by:

receiving a block of write requests of the plurality of write requests;

perform a block write to the assigned segment of the write data for all of the write requests in the block of write requests;

buffer the metadata entries corresponding to each write request of the block of write requests;

write the metadata entries to the un-filled metadata index upon detecting that no write requests are pending for the storage device.

6. The storage system of claim 4, wherein the executable code is further effective to cause the one or more processing devices to process each write request of the plurality of write requests by:

creating an entry in a block map for the each write request, the entry including the write address from the each write request and an identifier of the assigned segment.

7. The storage system of claim 6, wherein the executable code is further effective to cause the one or more processing devices to process a plurality of read requests, each read request referencing a storage volume and including a read address, by, for each read request of the plurality of read requests:

identify a read segment mapped to the read address in the block map;

identify a metadata entry referencing the read address in the read segment; and

reading requested data from an offset included in the metadata entry.

8. The storage system of claim 4, wherein adding the reference to the storage volume referenced by the each write request to the segment entry of the segment map corresponding to the assigned segment of the plurality of segments further comprises assigning a virtual segment identifier to the assigned segment according to a monotonically increasing virtual segment counter.

9. The storage system of claim 8, wherein the executable code is further effective to cause the one or more processing devices to process a plurality of read requests, each read request referencing a storage volume and including a read address, by, for each read request of the plurality of read requests:

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

identifying 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 data referenced by a last-written metadata entry referencing the read address in the read segment.

10. The storage system of claim 8, wherein the executable code is further effective to cause the one or more processing devices to:

receive an instruction to receive transfer of transfer data;

in response to the instruction—

write the transfer data to an available segment of the plurality of segments;

add a transfer entry to the segment map for the transfer data, the transfer entry including a virtual segment identifier included with the instruction and a reference to the available segment.

11. A method comprising:

defining, by a storage node comprising one or more processing devices and a storage device, 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 storage device; and

processing a plurality of write requests, each write request referencing a storage volume and including write data and a write address;

determining, by the storage node, that, for a first write request of the plurality of write requests, that (a) an entry in the segment map references the storage volume of the first write request and corresponds to a first segment having sufficient space for the write data of the first write request;

in response to determining (a), writing, by the storage node, the write data of the first write request to the first segment;

determining, by the storage node, that, for a second write request of the plurality of write request, that (b) no entry in the segment map both references the storage volume of the second write request and corresponds to any segment having sufficient space for the write data of the second write request;

in response to determining (b)—

(i) selecting an unassigned segment from the plurality of segments;

(ii) adding a reference to the storage volume of the second write request to a segment entry of the segment map corresponding to the unassigned segment of the plurality of segments; and

(iii) writing the write data of the second write request to the assigned segment.

12. The method of claim 11, further comprising:

defining, by the storage node, a slice map including a plurality of slice entries, each slice entry having a corresponding slice identifier and representing a portion of the storage device;

obtaining, by the storage node, for the second write request, an offset from the second write request;

determining, by the storage that no entry in the slice map corresponds to the offset;

in response to determining that no entry in the slice map corresponds to the offset—

writing the offset to a slice entry of the plurality of slice entries;

wherein adding the reference to the storage volume of the second write request to the segment entry of the segment map corresponding to the assigned segment of the plurality of segments comprises adding a slice identifier corresponding to the slice entry if the plurality of slice entries to which the offset was written to the segment entry of the segment map corresponding to the assigned segment.

13. The method of claim 12, further comprising:

storing, by a storage manager computing device that is remote from the storage node, a volume map, the volume map including a volume entry mapping the offset from the second write request to the storage node.

14. The method system of claim 11, writing the write data of the second write request to the assigned segment by:

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

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

15. The method of claim 14, further comprising:

receiving, by the storage node, a block of write requests of the plurality of write requests, the block of write requests including the second write request;

performing, by the storage node, a block write to the assigned segment of the write data for all of the write requests in the block of write requests;

buffering, by the storage node, metadata entries corresponding to all write request of the block of write requests; and

writing, by the storage node, the metadata entries to the un-filled metadata index upon detecting that no write requests are pending for the storage device.

16. The method system of claim 14, further comprising:

creating, by the storage node, an entry in a block map for the second write request, the entry including the write address from the second write request and an identifier of the assigned segment.

17. The method of claim 16, further comprising:

receiving, by the storage node, a read request the read request including a read address;

identifying, by the storage node, a read segment mapped to the read address in the block map;

identifying, by the storage node, a metadata entry referencing the read address in the read segment; and

reading, by the storage node, requested data from an offset included in the metadata entry.

18. The method of claim 14, wherein adding the reference to the storage volume referenced by the second write request to the segment entry of the segment map corresponding to the assigned segment of the plurality of segments further comprises assigning, by the storage node, a virtual segment identifier to the assigned segment according to a monotonically increasing virtual segment counter.

19. The method of claim 18, further comprising:

receiving, by the storage node, a read request referencing a storage volume and including a read address;

searching, by the storage node, metadata entries of one or more segments mapped to the storage volume in the storage map;

identifying, by the storage node, 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 data referenced by a last-written metadata entry referencing the read address in the read segment.

20. The method system of claim 18, further comprising:

receiving, by the storage node, an instruction to receive transfer of transfer data;

in response to the instruction—

writing, by the storage node, the transfer data to an available segment of the plurality of segments;

adding, by the storage node, a transfer entry to the segment map for the transfer data, the transfer entry including a virtual segment identifier included with the instruction and a reference to the available segment.