Storage scheme for a distributed storage system
First Claim
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—
store a segment map including segment entries, each segment entry referencing a segment of a plurality of segments available for storage on the storage device, a storage volume to which the segment of the plurality of segments is allocated, and a virtual segment identifier;
store data in at least a portion of the plurality of segments such that each segment of the plurality of segments includes a first portion including data payloads from a plurality of write requests and a second portion including metadata entries, each metadata entry indicating a write address within the storage volume for one of the data payloads stored in the first portion;
for each write address included in the metadata entries of the segments of the plurality of segments—
mark as invalid all data payloads in the segments of the plurality of segments that have a corresponding metadata entry including the each write address except for a last-written data payload of a latest segment of the plurality of segments for the each write address, the latest segment for the each write address having a highest valued virtual segment identifier out of all the segments of the plurality of segments including the each write address in the metadata entries thereof.
1 Assignment
0 Petitions
Accused Products
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.
95 Citations
20 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— store a segment map including segment entries, each segment entry referencing a segment of a plurality of segments available for storage on the storage device, a storage volume to which the segment of the plurality of segments is allocated, and a virtual segment identifier; store data in at least a portion of the plurality of segments such that each segment of the plurality of segments includes a first portion including data payloads from a plurality of write requests and a second portion including metadata entries, each metadata entry indicating a write address within the storage volume for one of the data payloads stored in the first portion; for each write address included in the metadata entries of the segments of the plurality of segments— mark as invalid all data payloads in the segments of the plurality of segments that have a corresponding metadata entry including the each write address except for a last-written data payload of a latest segment of the plurality of segments for the each write address, the latest segment for the each write address having a highest valued virtual segment identifier out of all the segments of the plurality of segments including the each write address in the metadata entries thereof. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. A method comprising:
-
providing 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; storing, by the storage node, a segment map including segment entries, each segment entry referencing a segment of a plurality of segments available for storage on the storage device, a storage volume to which the segment of the plurality of segments is allocated, and a virtual segment identifier; storing, by the storage node, data in at least a portion of the plurality of segments such that each segment of the at least the portion of the plurality of segments includes a first portion including data payloads from a plurality of write requests and a second portion including metadata entries, each metadata entry indicating a write address within the storage volume for one of the data payloads stored in the first portion; for each write address included in the metadata entries of the segments of the plurality of segments— marking, by the storage node, as invalid all data payloads in the plurality of segments that have a corresponding metadata entry including the each write address except for a last-written data payload of a latest segment for the each write address, the latest segment for the each write address having a highest valued virtual segment identifier out of all the segments of the plurality of segments including the each write address in the metadata entries thereof. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19, 20)
-
Specification