Data Storage System Scale-Out with Local Address Remapping

A method of managing a data storage system having a first plurality of data storage devices, the method comprising:

• at a controller system having one or more processors and a communications interface for communicatively coupling the controller system to data storage devices in the data storage system, in response to adding a set of one or more storage devices to the first plurality of data storage devices, thereby forming a second plurality of data storage devices:
• for a global logical address space divided into a first plurality of segments, each segment further divided into a first plurality of sub-segments, wherein, in accordance with a first data layout, each sub-segment of each segment in the first plurality of segments for which data is stored, or is to be stored, in the first plurality of data storage devices is mapped to a respective storage device in the first plurality of data storage devices and to a respective sub-segment offset in a local logical address space in the respective storage device:
• determining for one or more segments in the first plurality of segments, a subset of that segment's sub-segments, the subset comprising sub-segments that are to be copied;
• copying each respective sub-segment in the determined subset from a source storage device to which the respective segment is mapped by the first data layout to a destination storage device to which the respective sub-segment is mapped by a second data layout, wherein the destination storage device is in the set of one or more added storage devices;
• in the source storage device, to which the respective segment is mapped by the first data layout, adding a local logical address range for the respective sub-segment to a free list for the source storage device;
• and
• in the source storage device, performing a logical address compaction operation by remapping one or more local logical address ranges, corresponding to one or more sub-segments in the global logical address space mapped to the source storage device by the second data layout, to logical address ranges in the free list for the source storage device, without moving data corresponding to the remapped one or more logical address ranges.

A memory controller, comprising:

• a storage interface for coupling the memory controller to a first plurality of data storage devices;
• a communications interface for communicatively coupling the memory controller to storage devices in the first plurality of data storage devices;
• and
• a processing module for processing addition of a storage device by performing a sequence of operations, including:
• for a global logical address space divided into a first plurality of segments, each segment further divided into a first plurality of sub-segments, each sub-segment further divided into a number of blocks, determining a first data layout that maps each sub-segment of each segment in the first plurality of segments for which data is stored, or is to be stored, in the first plurality of storage devices to a respective storage device in the first plurality of storage devices and to a respective sub-segment offset in a local logical address space in the respective storage device;
• in response to adding one or more storage devices to the first plurality of storage devices, thereby forming a second plurality of storage devices:
• determining a second data layout that maps each sub-segment of each segment in a second plurality of segments for which data is stored, or is to be stored, in the second plurality of storage devices to a respective storage device in the second plurality of storage devices and to a respective sub-segment offset in a local logical address space in the respective storage device, wherein the second plurality of segments includes the first plurality of segments and additional segments;
• for one or more respective segments in the first plurality of segments:
• for one or more respective sub-segments in the respective segment for which the second data layout maps the respective segment to a different storage device than the storage device to which the respective segment is mapped by the first data layout:
• copying the respective sub-segment from a source storage device to which the respective segment is mapped by the first data layout to a destination storage device to which the respective sub-segment is mapped by the second data layout;
• and
• in the source storage device to which the respective segment is mapped by the first data layout, adding the local logical address range for the respective sub-segment to a free list for the source storage device;
• and
• in a source storage device, for which at least one respective sub-segment has been copied to a respective destination storage device, performing a logical address compaction operation by remapping one or more local logical address ranges to logical address ranges in the free list for the source storage device, without moving data corresponding to the remapped one or more logical address ranges.

A computer readable storage medium storing one or more programs configured for execution by a memory controller configured to be coupled to a plurality of data storage devices in a data storage system, the one or more programs comprising instructions that when executed by one or more processors of the memory controller, cause the memory controller to:

• for a global logical address space divided into a first plurality of segments, each segment further divided into a first plurality of sub-segments, each sub-segment further divided into a number of blocks, determining a first data layout that maps each sub-segment of each segment in the first plurality of segments for which data is stored, or is to be stored, in a first plurality of storage devices to a respective storage device in the first plurality of storage devices and to a respective sub-segment offset in a local logical address space in the respective storage device;
• in response to adding one or more storage devices to the first plurality of storage devices, thereby forming a second plurality of storage devices:
• determining a second data layout that maps each sub-segment of each segment in a second plurality of segments for which data is stored, or is to be stored, in the second plurality of storage devices to a respective storage device in the second plurality of storage devices and to a respective sub-segment offset in a local logical address space in the respective storage device, wherein the second plurality of segments includes the first plurality of segments and additional segments;
• for one or more respective segments in the first plurality of segments:
• for one or more respective sub-segments in the respective segment for which the second data layout maps the respective segment to a different storage device than the storage device to which the respective segment is mapped by the first data layout:
• copying the respective sub-segment from a source storage device to which the respective segment is mapped by the first data layout to a destination storage device to which the respective sub-segment is mapped by the second data layout;
• and
• in the source storage device to which the respective segment is mapped by the first data layout, adding the local logical address range for the respective sub-segment to a free list for the source storage device;
• and
• in a source storage device, for which at least one respective sub-segment has been copied to a respective destination storage device, performing a logical address compaction operation by remapping one or more local logical address ranges to logical address ranges in the free list for the source storage device, without moving data corresponding to the remapped one or more logical address ranges.