System and method for data protection with multidimensional parity

• US 20050022052A1
• Filed: 07/07/2004
• Published: 01/27/2005
• Est. Priority Date: 02/18/2000
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Avamar Technologies, Inc. (Dell Technologies Inc.)
• Inventors: Yueh, Jedidiah, Moulton, Gregory Hagan, Hamilton, Felix
• Granted Patent: US 7,000,143 B2
• Time in Patent Office: Days
• US Class Current: 714/6
• 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 data communication network;

a plurality of storage locations, wherein each storage location is coupled to communicate over the network;

a storage management control mechanism coupled to the network and configured to receive a storage request associated with a data set and determine a degree of fault tolerance for the data set;

means for identifying at least one parity group within the storage locations that provides the determined degree of fault tolerance; and

a write mechanism in the storage management control mechanism capable of writing the data set to at least one of the identified parity groups.

2. The data storage management system of claim 1 wherein the degree of fault tolerance is specified in the storage request.

3. The data storage management system of claim 1 wherein the degree of fault tolerance can be changed at a later time.

4. The data storage management system of claim 1 wherein the system stores multiple data sets and the degree of fault tolerance can be changed at a later time for a specific data set stored in said system and/or for multiple data sets stored in the system.

5. The data storage management system of claim 1 wherein the degree of fault tolerance is determined by intelligence within the storage management control mechanism.

6. The data storage management system of claim 1 wherein each storage location comprises a plurality of storage areas.

7. The data storage management system of claim 1 wherein the degree of fault tolerance is determined based upon characteristics of the data set.

8. The data storage management system of claim 1 wherein the identified parity group comprises a non-intersecting parity group where no two members of a single parity group reside on the same physical device

9. The data storage management system of claim 1 wherein membership in any parity group can be dynamically determined.

10. The data storage management system of claim 1 wherein the number of storage nodes in a parity group can be dynamically increased or decreased to meet instantaneous needs.

11. The data storage management system of claim 1 wherein a data set in a first parity group can be dynamically added to a second parity group.

12. The data storage management system of claim 1 further comprising:

a read mechanism in the storage management control mechanism capable of reading the data set from the at least one parity group.

13. The data storage management system of claim 1 wherein the write mechanism includes components operable to generate a parity image of the data set.

14. The data storage management system of claim 1 wherein the write mechanism includes components operable to generate at least one exclusive-or result of the data set with at least one other numeric sequence.

15. The data storage management system of claim 1 wherein the write mechanism includes components operable to generate at least one binary complement result of data set.

16. The data storage management system of claim 1 wherein the write mechanism includes components operable to generate a one'"'"'s complement binary addition result of the numeric sequence with at least one other numeric sequence.

17. The data storage management system of claim 1 wherein the write mechanism includes components operable to generate a one'"'"'s complement binary subtraction result of the numeric sequence with at least one other data set.

18. The data storage management system of claim 1 wherein the write mechanism includes components operable to generate a two'"'"'s complement binary addition result of the numeric sequence with at least one other data set.

19. The data storage management system of claim 1 wherein the write mechanism includes components operable to generate a two'"'"'s complement binary subtraction result of the numeric sequence with at least one other numeric sequence.

20. The data storage management system of claim 1 wherein the system is used as data storage for a backup, recovery, and archive system.

21. The data storage management system of claim 1 wherein the system is used as primary data storage for a computer or server, or a group of computers or servers.

22. The data storage management system of claim 1 wherein the storage locations, which are coupled to communicate over the network, may be decoupled from time to time and then coupled again to communicate over the network.

23. The data storage management system of claim 10 wherein the storage management control mechanism governs the read mechanism to select at least one parity group from amongst a plurality of parity groups based upon reducing the time required to complete the operation.

24. The data storage management system of claim 1 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.

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

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

a plurality of parity groups wherein each parity group comprises 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 plurality of data sets.

26. The data storage mechanism of claim 25 wherein at least one of the plurality of parity groups is dynamically configurable by altering which of the plurality of data sets are members of the at least one dynamically configurable parity group.

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

28. The data storage mechanism of claim 25 wherein the storage management control mechanism dynamically modifies at least one parity group definition while the plurality of data sets remain available.