System and method for data protection with multidimensional parity

• US 6,826,711 B2
• Filed: 02/13/2001
• Issued: 11/30/2004
• Est. Priority Date: 02/18/2000
• Status: Expired due to Term

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Avamar Technologies, Inc. (Dell Technologies Inc.)
• Inventors: Moulton, Gregory Hagan, Hamilton, Felix
• Primary Examiner(s): BADERMAN, SCOTT T
• Application Number:
  US09/782,613
• Publication Number:
  US 20020048284A1
• Time in Patent Office: 1,386 Days
• Field of Search: 714/6, 711/114
• US Class Current: 714/6.12
• 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/1028 Distributed, i.e. distributed RAID systems with parity

Abstract

A high availability, high reliability storage system that leverages rapid advances in commodity computing devices and the robust nature of internetwork technology such as the Internet. A system of parity distribution in accordance with the present invention allows for greater fault tolerance and levels of storage efficiency than possible with conventional RAID (levels 0-5) paradigms. Data can be recovered or made available even in the case of loss of N, N+1, or more devices or storage elements over which stripes of the data set have been distributed or partitioned. The present invention provides a parity distribution that can be used to distribute data stored in a single storage device or across multiple connected or otherwise networked devices.

Claims

1. A data storage management system comprising:

a plurality of storage devices, each storage device comprising a plurality of storage areas;

a storage management control mechanism configured to receive a storage request associated with a data set;

a communication system between the plurality of storage devices and the storage management mechanism;

means for determining at least one digital representation of the data set;

a write mechanism in the storage management control mechanism capable of writing the digital representation in at least one storage area;

a read mechanism in the storage management control mechanism capable of reading the data set from the storage devices using the digital representation from the at least one storage area;

wherein the storage management control mechanism includes mechanisms to govern the read mechanism to perform the act of reading the data set from at least three of a plurality of digital representations for the data set; and

wherein the storage management control mechanism determines which data to report in response to a read request based on the consensus of the three digital representations.

2. The data storage management system of claim 1 wherein the at least one digital representation includes an unaltered data set.

3. The data storage management system of claim 1 wherein the at least one digital representation includes a parity image of the data set.

4. The data storage management system of claim 1 wherein the at least one digital representation includes at least one exclusive-or result of the data set with at least one other data set.

5. The data storage management system of claim 1 wherein the at least one digital representation includes at least one binary complement result of data set.

6. The data storage management system of claim 1 wherein the at least one digital representation includes the one'"'"'s complement binary addition result of the data set with at least one other data set.

7. The data storage management system of claim 1 wherein the at least one digital representation includes the one'"'"'s complement binary subtraction result of the data set with at least one other data set.

8. The data storage management system of claim 1 wherein the at least one digital representation includes the two'"'"'s complement binary addition result of the data set with at least one other data set.

9. The data storage management system of claim 1 wherein the at least one digital representation includes the two'"'"'s complement binary subtraction result of the data set with at least one other data set.

10. A data storage management system of claim 1 wherein the storage management control mechanism includes mechanisms that govern the read mechanism to perform the act of reading the data set from one of a plurality of digital representations for the given data set.

11. The data storage management system of claim 1 wherein the storage management control mechanism governs the read mechanism to perform the act of reading the data set from one of the plurality of storage devices containing a written digital representation of the given data set.

12. A data storage management system of claim 1 wherein the storage management control mechanism governs the read mechanism to select at least one the storage devices based upon reducing the time required to complete the operation.

13. A data storage management system of claim 1 wherein the storage management control mechanism governs the read mechanism to perform the read operation from at least one of the plurality of storage device devices such that inaccessible ones of the storage devices are avoided.

14. A data storage management system of claim 1 wherein at least some of the digital representations corresponding to the data set differ from each other.

15. A data storage management system comprising:

a plurality of storage devices, each storage device comprising a plurality of storage areas;

a storage management control mechanism configured to receive a storage request associated with a data set;

a communication system between the plurality of storage devices and the storage management mechanism;

means for determining at least one digital representation of the data set; and

a write mechanism in the storage management control mechanism capable of writing the digital representation in at least one storage area;

wherein the number of the storage areas used for writing a first data set differs from the number of the storage areas used for writing a second data set.

16. A data storage management system for storing a plurality of data sets, the system comprising:

a plurality of storage devices, each storage device comprising a plurality of storage areas;

a storage management control mechanism configured to receive a storage request associated with a data set;

a communication system coupling the plurality of storage devices and the storage management mechanism; and

a plurality of parity groups defined within at least one storage area, the parity group comprising a logical combination of the plurality of data sets;

wherein levels of parity protection of the plurality of parity groups varies for arbitrarily small subsets of data within the overall data set protected by the plurality of parity groups.

17. The data storage mechanism of claim 16 wherein the parity group is dynamically configured by altering the membership of the group of the plurality of data sets.

18. The data storage mechanism of claim 16 wherein each of plurality of data sets is stored in a storage area that is separate from the storage area in which the parity group is defined.

19. The data storage mechanism of claim 16 wherein the storage management control mechanism dynamically modifies the parity group definition while the plurality of data sets remain available.

20. The data storage mechanism of claim 18 wherein the parity group is used to reconstruct primary data and to serve data requests in lieu of or in addition to serving the data requests directly from the primary data.

21. A method of providing parity protection for a data set comprising the acts of:

selecting a primary data element for entry;

determining a desired degree of fault tolerance for the data element;

selecting a number of non-intersecting parity groups to be associated with the primary data element;

selecting a primary location for the primary data element;

writing the data element to the primary location;

updating the parity groups associated with the data element; and

confirming the write operation and associated parity updates.

22. The method of claim 21 further comprising:

reading the data element directly from its primary location in response to a read request.

23. The method of claim 21 further comprising:

reading an image of the data element reconstructed from one of its associated parity groups.

24. The method of claim 21 further comprising:

automatically maintaining, migrating, and reconstructing primary data and associated parity groups in response to detected network, server, disk, and human error while the data element remains available for reading from at least one source.

25. A method of implementing data parity protection for a plurality of data sets comprising the acts of:

providing a plurality of storage devices, each storage device comprising a plurality of storage areas;

associating a parity group with each data set, each parity group comprising at least one of the plurality of data sets, wherein the act of associating a parity group with each data set comprises selecting a number of parity groups for each data set independently of the number of parity groups for each other data set; and

dynamically altering the composition of the plurality of storage devices.

26. The method of claim 25 further comprising dynamically altering the parity group.

27. The method of claim 25 wherein the act of dynamically altering the composition of the plurality of storage devices comprises adding a storage device.

28. The method of claim 25 wherein the act of dynamically altering the composition of the plurality of storage devices comprises removing a storage device.

29. The method of claim 26 wherein the act of dynamically altering the parity group comprises adding an additional data set to the parity group without affecting availability of other data sets in the parity group.

30. The method of claim 26 wherein the act of dynamically altering the parity group comprises removing a data set from the parity group without affecting availability of other data sets in the parity group.

31. The method of claim 25 further comprising accessing data from a selected data set by reading from at least one parity group associated with the data set without reconstructing the data set.

32. A method of providing parity protection for a data set comprising the acts of:

determining a desired degree of fault tolerance for data element;

selecting a number of non-intersecting parity groups to be associated with the data element;

selecting a location for the data element; and

writing the data element to the selected location.