Alternate storage arrangement in a distributed data storage system with key-based addressing

• US 10,514,982 B2
• Filed: 12/12/2014
• Issued: 12/24/2019
• Est. Priority Date: 08/21/2014
• Status: Active Grant

• Current Assignee: VMware, Inc. (Broadcom, Inc.), Vmware LLC (Broadcom, Inc.)
• Original Assignee: Datrium, Inc. (Broadcom, Inc.)
• Inventors: Wang, Zhe, Patterson, R. Hugo, Huang, Mark L.
• Primary Examiner(s): Rizk, Samir W
• Assistant Examiner(s): Ahmed, Enam
• Application Number:
  US14/568,700
• Publication Number:
  US 20160054939A1
• Time in Patent Office: 1,838 Days
• Field of Search: 714766
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 2211/1061 Parity-single bit-RAID4, i.e. RAID 4 implementations

Abstract

In a Distributed Virtual Array data storage system, data chunks making up data containers and identified by keys, which are independent of physical storage locations, are written in storage devices according to layouts specified in a layout data structure. When any of the storage devices becomes inaccessible, the chunks nominally designated to be written in the inaccessible storage devices are instead written to alternate devices. Information indicating writing to an alternate device may be included in or along with such chunks so as to make them easily identifiable during later reconstruction or re-writing to the intended storage device when it again becomes available.

Claims

1. A method for writing data to a plurality of storage devices, comprising:

executing at least one writing entity within a corresponding one of a plurality of hosts,

wherein each host of the plurality of hosts has access to a shared storage pool;

wherein the shared storage pool includes a plurality of chunk stores that manage storage of chunks to, and retrieval of chunks from, the plurality of storage devices;

receiving a request from the at least one writing entity to write particular data to the shared storage pool;

in response to the request, writing the particular data as a stripe across a subset of the plurality of storage devices;

assigning a particular container name to the stripe;

wherein the particular container name is independent of physical storage identifiers and logical block addresses;

wherein writing the particular data as a stripe across the plurality of chunk stores comprises;

generating a plurality of chunks for the stripe, wherein the particular data is contained within the plurality of chunks;

based on the particular container name, indexing into a layout table to retrieve an entry;

determining, from the entry, a target subset of the plurality of chunk stores;

sending each chunk, of the plurality of chunks, to a distinct chunk store from the target subset;

wherein the layout table is configured to ensure that no two chunks of the plurality of chunks are sent to the same chunk store of the plurality of chunk stores;

receiving a request for target data that belongs to the stripe, wherein the request includes the particular container name;

based on the particular container name, indexing into the layout table to locate the entry;

based on the entry, determining the target subset of the plurality of chunk stores; and

retrieving the target data from one or more chunk stores of the target subset.

2. The method of claim 1, wherein:

the entry indicates one or more alternate storage assignments;

the one or more alternate storage assignments indicate one or more chunk stores, that do not belong to the target subset, for storing chunks of stripes that map to the entry in cases where any chunk stores, within the target subset, are unavailable; and

the method further comprises distributing, to each host of the plurality of hosts, the layout table, including an indication of the alternate storage assignments.

3. The method of claim 2, further comprising associating, with each chunk that is written to an alternate chunk store, particular information indicating that it has been written to an alternate storage assignment.

4. The method of claim 3, wherein the particular information is metadata associated with each such chunk.

5. The method of claim 3, wherein the particular information is an indication added into a key associated with each such chunk.

6. The method of claim 2, wherein:

the entry specifies a layout pattern that nominally designates which chunk of the stripe is to be written to each chunk store in the target subset; and

the method further comprises moving a chunk that was written in an alternate chunk store to the chunk store in which it is nominally designated to be written, according to the layout pattern specified by the entry, when the nominally designated chunk store again becomes accessible.

7. The method of claim 1, wherein:

the entry specifies a layout pattern that nominally designates which chunk of the stripe is to be written to each chunk store in the target subset;

generating the plurality of chunks further comprises generating a set of data chunks and computing at least one correction chunk; and

the method further comprises, when a chunk written in its nominally designated chunk store becomes inaccessible, reconstructing said chunk from the remaining chunks in the stripe, including the at least one correction chunk.

8. The method of claim 7, further comprising:

including, in each set of data chunks, reconstruction information sufficient to reconstruct a plurality of unavailable data chunks;

determining that a particular set of chunk stores have become inaccessible at the same time;

determining that a particular set of layout patterns within the layout table include one or more chunk stores of the particular set of chunk stores;

for the particular set of layout patterns, reconstructing inaccessible data chunks from stripes that were stored based on the particular set of layout patterns;

wherein reconstructing the inaccessible data chunks of each stripe is performed based on the remaining chunks in each stripe and the reconstruction information;

wherein reconstructing the inaccessible data chunks is performed s in an order such the unavailable data chunks from stripes stored according to layout patterns having relatively more unavailable data chunks are reconstructed before unavailable data chunks for stripes stored according to layout patterns having relatively fewer unavailable data chunks.

9. The method of claim 8, in which the reconstruction information is a plurality of correction chunks.

10. The method of claim 1 wherein:

the plurality of chunks includes a first set of one or more chunks and a second set of one or more chunks;

the first set of one or more chunks include the particular data; and

the method further comprises generating the second set of one or more chunks based on the particular data.

11. The method of claim 1 wherein:

the stripe is one of a plurality of containers in a particular container set;

each stripe in the particular container set has a unique name relative to each other stripe in the particular container set;

the particular container set is one of a plurality of container sets into which the shared storage pool is organized; and

each container set of the plurality of container sets has a unique name relative to each other container set in the shared storage pool.

12. The method of claim 1 wherein indexing into a layout table to retrieve an entry comprises:

deriving a MapID based on the particular container name; and

locating the entry by indexing into the layout table based on the MapID.

13. The method of claim 1 wherein assigning a particular container name to the stripe comprises assigned the stripe a container name that is based on at least (a) an identifier of a container set to which the stripe belongs, and (b) an identifier of the at least one writing entity.

14. The method of claim 1 wherein the entry indicates, for each chunk position within the stripe, which chunk store is designated for storing the chunk, within the stripe, that is located in the chunk position.

15. One or more non-transitory computer-readable media storing instructions for writing data to a plurality of storage devices, wherein the instructions include instructions which, when executed by one or more computing devices, cause:

executing at least one writing entity within a corresponding one of a plurality of hosts, wherein each host of the plurality of hosts has access to a shared storage pool;

wherein the shared storage pool includes a plurality of chunk stores that manage storage of chunks to, and retrieval of chunks from, the plurality of storage devices;

receiving a request from the at least one writing entity to write particular data to the shared storage pool;

in response to the request, writing the particular data as a stripe across a subset of the plurality of storage devices;

assigning a particular container name to the stripe;

wherein the particular container name is independent of physical storage identifiers and logical block addresses;

wherein writing the particular data as a stripe across the plurality of chunk stores comprises;

generating a plurality of chunks for the stripe, wherein the particular data is contained within the plurality of chunks;

based on the particular container name, indexing into a layout table to retrieve an entry;

determining, from the entry, a target subset of the plurality of chunk stores;

sending each chunk, of the plurality of chunks, to a distinct chunk store from the target subset;

wherein the layout table is configured to ensure that no two chunks of the plurality of chunks are sent to the same chunk store of the plurality of chunk stores;

receiving a request for target data that belongs to the stripe, wherein the request includes the particular container name;

based on the particular container name, indexing into the layout table to locate the entry;

based on the entry, determining the target subset of the plurality of chunk stores; and

retrieving the target data from one or more chunk stores of the target subset.

16. The one or more non-transitory computer-readable media of claim 15, wherein:

the entry indicates one or more alternate storage assignments;

the one or more alternate storage assignments indicate one or more chunk stores, that do not belong to the target subset, for storing chunks of stripes that map to the entry in cases where any chunk stores, within the target subset, are unavailable; and

the instructions further comprise instructions for distributing, to each host of the plurality of hosts, the layout table, including an indication of the alternate storage assignments.

17. The one or more non-transitory computer-readable media of claim 16, further comprising instructions for associating, with each chunk that is written to an alternate chunk store, particular information indicating that it has been written to an alternate storage assignment.

18. The one or more non-transitory computer-readable media of claim 17, wherein the particular information is metadata associated with each such chunk.

19. The one or more non-transitory computer-readable media of claim 17, wherein the particular information is an indication added into a key associated with each such chunk.

20. The one or more non-transitory computer-readable media of claim 16, wherein:

the entry specifies a layout pattern that nominally designates which chunk of the stripe is to be written to each chunk store in the target subset; and

the instructions further comprise instructions for moving a chunk that was written in an alternate chunk store to the chunk store in which it is nominally designated to be written, according to the layout pattern specified by the entry, when the nominally designated chunk store again becomes accessible.

21. The one or more non-transitory computer-readable media of claim 15, wherein:

the entry specifies a layout pattern that nominally designates which chunk of the stripe is to be written to each chunk store in the target subset;

generating the plurality of chunks further comprises generating a set of data chunks and computing at least one correction chunk; and

the instructions further cause, when a chunk written in its nominally designated chunk store becomes inaccessible, reconstructing said chunk from the remaining chunks in the stripe, including the at least one correction chunk.

22. The one or more non-transitory computer-readable media of claim 21, further comprising instructions for:

including, in each set of data chunks, reconstruction information sufficient to reconstruct a plurality of unavailable data chunks;

determining that a particular set of chunk stores have become inaccessible at the same time;

determining that a particular set of layout patterns within the layout table include one or more chunk stores of the particular set of chunk stores;

for the particular set of layout patterns, reconstructing inaccessible data chunks from stripes that were stored based on the particular set of layout patterns;

wherein reconstructing the inaccessible data chunks of each stripe is performed based on the remaining chunks in each stripe and the reconstruction information;

wherein reconstructing the inaccessible data chunks is performed s in an order such the unavailable data chunks from stripes stored according to layout patterns having relatively more unavailable data chunks are reconstructed before unavailable data chunks for stripes stored according to layout patterns having relatively fewer unavailable data chunks.

23. The one or more non-transitory computer-readable media of claim 22, wherein the reconstruction information is a plurality of correction chunks.

24. The one or more non-transitory computer-readable media of claim 15 wherein:

the plurality of chunks includes a first set of one or more chunks and a second set of one or more chunks;

the first set of one or more chunks include the particular data; and

the instructions further cause generating the second set of one or more chunks based on the particular data.

25. The one or more non-transitory computer-readable media of claim 15 wherein:

the stripe is one of a plurality of containers in a particular container set;

each stripe in the particular container set has a unique name relative to each other stripe in the particular container set;

the particular container set is one of a plurality of container sets into which the shared storage pool is organized; and

each container set of the plurality of container sets has a unique name relative to each other container set in the shared storage pool.

26. The one or more non-transitory computer-readable media of claim 15 wherein indexing into a layout table to retrieve an entry comprises:

deriving a MapID based on the particular container name; and

locating the entry by indexing into the layout table based on the MapID.

27. The one or more non-transitory computer-readable media of claim 15 wherein assigning a particular container name to the stripe comprises assigned the stripe a container name that is based on at least (a) an identifier of a container set to which the stripe belongs, and (b) an identifier of the at least one writing entity.

28. The one or more non-transitory computer-readable media of claim 15 wherein the entry indicates, for each chunk position within the stripe, which chunk store is designated for storing the chunk, within the stripe, that is located in the chunk position.