Distributed Data Storage System with Key-Based Addressing

• US 20160054920A1
• Filed: 08/21/2014
• Published: 02/25/2016
• Est. Priority Date: 08/21/2014
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: Datrium, Inc. (Broadcom, Inc.)
• Inventors: Patterson, R. Hugo III
• Granted Patent: US 9,639,268 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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/104 Metadata, i.e. metadata associated with RAID systems with parity
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/0683 Plurality of storage devices
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

In a Distributed Virtual Array data storage system, a storage pool receives, from at least one writing entity within a host, a request to write a container of data that is identified by a unique key that is independent of physical storage identifiers and that comprises a set of data chunks. The key indicates a plurality of storage devices in which to store the data chunks, which are accordingly stored in those storage devices. Different combinations, each comprising a layout map, of storage devices are represented in a layout table. Information in the container key is used to select which layout map to use for the chunks of each container. An error-correction chunk is preferably also stored along with the chunks of each container so as to enable data container reconstruction in case of storage device failure.

Claims

1. A data storage method comprising:

receiving, from at least one writing entity within a host, a request to write a container of data that is identified by a unique key that is independent of physical storage identifiers and that comprises a set of data chunks;

determining, from the key, a plurality of storage devices in which to store the data chunks; and

storing the chunks in respective, different ones of the plurality of storage devices as determined from the key.

2. The method as in claim 1, further comprising:

generating an error-correction code for the chunks of the data container;

creating at least one error-correcting chunk corresponding to the error-correction code; and

determining, as a function of the key, at least one storage device different from the plurality of storage devices in which the data chunks are stored and storing the at least one error-correcting chunk in respective said different storage device(s).

3. The method as in claim 1, further comprising:

receiving requests to write a plurality of data containers from a plurality of writing entities;

for each data container, associating the respective key with the corresponding writing entity such that the keys associated with any data containers originating with that writing entity are distinct from any key for a data container originating from a different writing entity; and

generating, for at least one subsequent, new data container, a corresponding new key that is different from any other key generated for any previous data container received from the same writing entity.

4. The method as in claim 1, further comprising returning data from a stored data container in response to a read request that provides the key to indicate which data container should be read.

5. The method as in claim 1, further comprising including in the key, for each chunk in the data container, a key portion associated with that chunk.

6. The method as in claim 5 wherein the key for the data container includes indications of the positions of the chunks in the respective data container.

7. The method as in claim 5, further comprising determining the key portion for each chunk in the container from the position of each chunk within the data container and the size of the chunk.

8. The method as in claim 1, further comprising compiling a layout data structure having elements that specify in which storage device each chunk of a given data container is to be stored, as a function of the respective key of each data container.

9. The method as in claim 8, in which:

the layout data structure specifies a plurality of combinations of storage devices into which to store the chunks; and

the function of the respective key of each data container is a many-to-one mapping of the data container keys to respective ones of the combinations, such that chunks from more than one data container may be stored in the same combination of storage devices and at least one of the storage devices may store chunks from data containers mapped to different ones of the combinations.

10. The method as in claim 8, further comprising determining chunk storage location from the corresponding data container key and the layout data structure.

11. The method as in claim 8, further comprising associating with each chunk a metatag indicating according to which layout data structure element it has been stored.

12. The method as in claim 2, further comprising:

detecting inaccessibility of any of the plurality of storage devices; and

for each data container having at least one of its chunks stored in the inaccessible storage device, reconstructing said chunk.

13. The method as in claim 12, further comprising storing the reconstructed chunk in a different one of the storage devices that does not store any other chunk belonging to the same data container.

14. The method as in claim 10, further comprising:

detecting inaccessibility of any of the plurality of the storage devices indicated in the layout data structure;

for each combination of storage devices that includes the inaccessible storage device, determining a new storage device distinct from any other storage device in the combination; and

updating the layout data structure to indicate the newly determined storage device for the respective chunk in the data container mapped to each said combination.

15. The method of claim 12, further comprising:

for each data container having one of its chunks stored on the inaccessible storage device, reconstructing said chunk;

determining from the data container key which updated set of storage devices to use to store the chunks for this data container; and

storing the reconstructed chunk in the respective newly determined storage device.

16. The method as in claim 12, further comprising:

receiving requests to write data containers from writing entities within a plurality of hosts; and

maintaining a copy of the layout data structure in each of the hosts.

17. The method as in claim 1, further comprising storing newly written data in new data containers without changing previously stored data containers.

18. The method as in claim 1, further comprising:

receiving a data container identified by a unique key;

dividing the container into a set of data chunks; and

interpreting the created set of chunks as the set of chunks to be stored.

19. A data storage system comprising:

a plurality of storage devices;

a storage pool receiving, from at least one writing entity within a host, a request to write a container of data that is identified by a unique key that is independent of physical storage identifiers and that comprises a set of data chunks;

said storage pool including a driver configured for determining, from the key, in which of the plurality of storage devices to store the data chunks; and

said storage pool further including chunk stores for storing the chunks in respective, different ones of the plurality of storage devices as determined from the key.

20. The system as in claim 19, in which the pool store is further configured

for generating an error-correction code for the chunks of the data container;

for creating at least one error-correcting chunk corresponding to the error-correction code; and

for determining, as a function of the key, at least one storage device different from the plurality of storage devices in which the data chunks are stored and storing the at least one error-correcting chunk in respective said different storage device(s).

21. The system as in claim 19 in which the pool store is further configured

for receiving requests to write a plurality of data containers from a plurality of writing entities;

for each data container, for associating the respective key with the corresponding writing entity such that the keys associated with any data containers originating with that writing entity are distinct from any key for a data container originating from a different writing entity; and

for generating, for at least one subsequent, new data container, a corresponding new key that is different from any other key generated for any previous data container received from the same writing entity.

22. The system as in claim 19, further comprising a layout manager provided for compiling a layout data structure having elements that specify in which storage device each chunk of a given data container is to be stored, as a function of the respective key of each data container.

23. The system as in claim 22, in which:

the layout data structure specifies a plurality of combinations of the storage devices into which to store the chunks; and

the function of the respective key of each data container is a many-to-one mapping of the data container keys to respective ones of the combinations, such that chunks from more than one data container may be stored in the same combination of storage devices and at least one of the storage devices may store chunks from data containers mapped to different ones of the combinations.

24. The system as in claim 22, in which:

the pool store is further configured for detecting inaccessibility of any of the plurality of the storage devices indicated in the layout data structure; and

for each combination of storage devices that includes the inaccessible storage device, determining a new storage device distinct from any other storage device in the combination; and

the layout manager is configured for updating the layout data structure to indicate the newly determined storage device for the respective chunk in the data container mapped to each said combination.

25. The system as in claim 20, in which the pool store is further configured for detecting inaccessibility of any of the plurality of storage devices;

and for each data container having at least one of its chunks stored in the inaccessible storage device, reconstructing said chunk.