Data Reconstruction in Distributed Data Storage System with Key-Based Addressing

• US 20160055054A1
• Filed: 10/22/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, HUANG, Mark L., WANG, Zhe
• Granted Patent: US 9,417,955 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1008 in individual solid state devices G06F11/1004 takes precedence
• 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
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays

Abstract

In a Distributed Virtual Array data storage system, data chunks making up data containers are stored in a key order in storage devices according to layouts specified in a layout data structure. When any of the storage devices becomes inaccessible, the storage devices iteratively return, in storage order, their stored chunks. Chunks belonging to the same container are identified and, if that container had a chunk in the inaccessible storage device, are used to reconstruct the inaccessible chunk. The chunks of the container are then stored according to an updated layout. The keys are independent of physical storage locations.

Claims

1. A method for recovering data from a plurality of storage devices,

said data being grouped as containers written by at least one writing entity within a corresponding one of a plurality of hosts, each container being identified by a unique key that is independent of physical storage identifiers and comprising a set of data chunks stored in different ones of the plurality of storage devices, said method comprising:

detecting inaccessibility of one of the plurality of storage devices in which data chunks are stored;

iteratively requesting and receiving data chunks from the data storage devices in which a given container'"'"'s chunks are stored;

for each container having a data chunk stored in the inaccessible storage device, reconstructing from the received data chunks belonging to the same container the corresponding data chunk that had been stored in the inaccessible storage device; and

storing the reconstructed data chunk in a different one of the storage devices.

2. The method of claim 1, further comprising, in each of the storage devices, storing the respective data chunks in an order determined by the container key corresponding to each respective data chunk.

3. The method of claim 1, in which the step of iteratively requesting and receiving the data chunks comprises iteratively requesting and receiving the data chunks in storage key order.

4. The method of claim 1, further comprising:

storing the chunks of each container in the plurality of storage devices according to one of a plurality of layouts determined as a function of the container'"'"'s key; and

determining which of the received data chunks are stored according to the same layout and whether that layout specified storage of any data chunk of the corresponding container in the inaccessible storage device.

5. The method of claim 4, further comprising:

compiling the layouts into a layout data structure;

updating the layout data structure to reflect the inaccessibility of the storage device and to indicate, per layout, in which of the storage devices data chunks stored in the inaccessible storage are to be reconstructed; and

distributing the updated layout table to the hosts.

6. The method of claim 4, further comprising associating with each chunk metadata indicating according to which layout the chunks of its corresponding container are stored in the storage devices.

7. The method of claim 6, in which the step of determining which of the received data chunks are stored according to the same layout comprises filtering the received data chunks according to their metadata.

8. The method of claim 4, further comprising including, in each key, information indicating according to which layout the corresponding container is stored.

9. The method of claim 1, in which the step of reconstructing the data chunks is carried out within a plurality of the hosts.

10. The method of claim 9, in which the step of determining the chunks stored according to the same layout is carried out within storage nodes that include the storage devices indicated by the respective layouts.

11. The method of claim 9, in which the determination of which host reconstructs a particular container is at least in part a function of the layout of the container.

12. The method of claim 9, in which the determination of which host reconstructs a particular container is at least in part a function of the key used to identify the container.

13. The method of claim 9, further comprising associating metadata with container chunks, such that the determination of which host reconstructs a particular container is a function of the metadata associated with the corresponding container chunks.

14. The method of claim 9, in which multiple hosts concurrently reconstruct disjoint subsets of the containers.

15. The method of claim 1, further comprising reconstructing the data chunks having been stored in the inaccessible storage device independent of any prior knowledge of which chunks belong to the same container.

16. A computer program product comprising code embodied in a non-transitory storage medium, said code being executable on at least one processor for causing the processor(s):

to recover data from a plurality of storage devices, said data being grouped as containers written by at least one writing entity within a corresponding one of a plurality of hosts, each container being identified by a unique key that is independent of physical storage identifiers and comprising a set of data chunks stored in different ones of the plurality of storage devices;

to detect inaccessibility of one of the plurality of storage devices in which data chunks are stored;

to iteratively request and receive data chunks from the data storage devices in which a given container'"'"'s chunks are stored;

for each container having a data chunk stored in the inaccessible storage device, to reconstruct from the received data chunks belong to the same container the corresponding data chunk that had been stored in the inaccessible storage device; and

to store the reconstructed data chunk in a different one of the storage devices.

17. The computer program product of claim 16, further including code causing the processor(s) to store, in each of the storage devices, the respective data chunks in an order determined by the container key corresponding to each respective data chunk.

18. The computer program product of claim 17, further including code causing the processor(s) iteratively request and receive the data chunks in storage key order.

19. The computer program product of claim 16, further including code causing the processor(s):

to store the chunks of each container in the plurality of storage devices according to one of a plurality of layouts determined as a function of the container'"'"'s key; and

to determine which of the received data chunks are stored according to the same layout and whether that layout specified storage of any data chunk of the corresponding container in the inaccessible storage device.

20. The computer program product of claim 16, said reconstructing of the data chunks being carried out by execution of corresponding code on at least one respective processor within the respective hosts.

21. The computer program product of claim 16, said reconstructing of the data chunks being carried out by execution of corresponding code within a plurality of the hosts.

22. The method of claim 21, in which the step of determining the chunks stored according to the same layout is carried out within storage nodes that include the storage devices indicated by the respective layouts.

23. The method of claim 21, in which the determination of which host reconstructs a particular container is at least in part a function of the layout of the container.

24. The method of claim 21, in which the determination of which host reconstructs a particular container is at least in part a function of the key used to identify the container.

25. The method of claim 21, further comprising associating metadata with container chunks, such that the determination of which host reconstructs a particular container is a function of the metadata associated with the corresponding container chunks.

26. The method of claim 21, in which multiple hosts concurrently reconstruct disjoint subsets of the containers.

27. The computer program product of claim 19, further including code causing the processor(s):

to compile the layouts into a layout data structure;

to updating the layout data structure to reflect the inaccessibility of the storage device and to indicate, per layout, in which of the storage devices data chunks stored in the inaccessible storage are to be reconstructed; and

to distributing the updated layout table to the hosts.

28. The computer program product of claim 16, further including code causing the processor(s) to reconstruct the data chunks having been stored in the inaccessible storage device independent of any prior knowledge of which chunks belong to the same container.

29. The computer program product of claim 19, further including code causing the processor(s) to associate with each chunk metadata indicating according to which layout the chunks of its corresponding container are stored in the storage devices.

30. The computer program product of claim 29, further including code causing the processor(s) to filter the received data chunks according to their metadata.

31. The computer program product of claim 19, further including code causing the processor(s) to include, in each key, information indicating according to which layout the corresponding container is stored.

32. A method for recovering data from a plurality of storage devices,

said data being grouped as containers written by at least one writing entity within a corresponding one of a plurality of hosts, each container being identified by a unique key that is independent of physical storage identifiers and comprising a set of data chunks stored in different ones of the plurality of storage devices, said method comprising:

storing the chunks of each container in the plurality of storage devices according to one of a plurality of layouts determined as a function of the container'"'"'s key;

compiling the layouts into a layout data structure;

in each of the storage devices, storing the respective data chunks in an order determined by the container key corresponding to each respective data chunk, each said key including information indicating according to which layout the corresponding container is stored;

detecting inaccessibility of one of the plurality of storage devices in which data chunks are stored;

iteratively requesting and receiving, in storage key order, data chunks from the data storage devices in which a given container'"'"'s chunks are stored;

for each container having a data chunk stored in the inaccessible storage device, determining which of the received data chunks are stored according to the same layout and whether that layout specified storage of any data chunk of the corresponding container in the inaccessible storage device and, independent of any prior knowledge of which chunks belong to the same container, reconstructing from the received data chunks belonging to the same container the corresponding data chunk that had been stored in the inaccessible storage device; and

storing the reconstructed data chunk in a different one of the storage devices;

updating the layout data structure to reflect the inaccessibility of the storage device and to indicate, per layout, in which of the storage devices data chunks stored in the inaccessible storage are to be reconstructed; and

distributing the updated layout table to the hosts.