Distributed data storage system with key-based addressing

• US 9,639,268 B2
• Filed: 08/21/2014
• Issued: 05/02/2017
• 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: Patterson, III, R. Hugo
• Primary Examiner(s): Alphonse, Fritz
• Application Number:
  US14/464,733
• Publication Number:
  US 20160054920A1
• Time in Patent Office: 985 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/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, said container comprising a plurality of data sub-sets;

determining, from the key, a plurality of storage devices in which to store the data sub-sets;

storing the data sub-sets in respective, different ones of the plurality of storage devices as determined from the key;

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

creating at least one error-correcting data sub-set 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 sub-sets are stored and storing the at least one error-correcting data sub-set in respective said different storage device(s).

2. 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.

3. 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.

4. The method as in claim 1, further comprising including in the key, for each data sub-set in the data container, a key portion associated with that data sub-set.

5. The method as in claim 4 wherein the key for the data container includes indications of the positions of the data sub-sets in the respective data container.

6. The method as in claim 4, further comprising determining the key portion for each data sub-set in the container from the position of each data sub-set within the data container and the size of the data sub-set.

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

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

the layout data structure specifies a plurality of combinations of storage devices into which to store the data sub-sets; 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 data sub-sets 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 data sub-sets from data containers mapped to different ones of the combinations.

9. The method as in claim 7, further comprising determining the data sub-set storage location from the corresponding data container key and the layout data structure.

10. The method as in claim 9, 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 data sub-set in the data container mapped to each said combination.

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

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

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

for each data container having at least one of its data sub-sets stored in the inaccessible storage device, reconstructing said data sub-set.

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

14. The method of claim 12, further comprising:

for each data container having one of its data sub-sets stored on the inaccessible storage device, reconstructing said data sub-set;

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

storing the reconstructed data sub-set in the respective newly determined storage device.

15. 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.

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

17. 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 sub-sets; and

interpreting the created set of data sub-sets as the set of data sub-sets to be stored.

18. 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 sub-sets;

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

said storage pool further including data sub-set stores for storing the data sub-sets in respective, different ones of the plurality of storage devices as determined from the key;

in which the pool store is further configured

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

for creating at least one error-correcting data sub-set 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 sub-sets are stored and storing the at least one error-correcting data sub-set in respective said different storage device(s).

19. The system as in claim 18 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.

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

21. The system as in claim 20, in which:

the layout data structure specifies a plurality of combinations of the storage devices into which to store the data sub-sets; 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 data sub-sets 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 data sub-sets from data containers mapped to different ones of the combinations.

22. The system as in claim 20, 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 data sub-set in the data container mapped to each said combination.

23. The system as in claim 18, 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 data sub-sets stored in the inaccessible storage device, reconstructing said chunk.