System and method for data protection with multidimensional parity

CROSS REFERENCE TO RELATED PATENT APPLICATIONS

0001The present invention is a continuation of U.S. Ser. No. 09/782,613, now U.S. Pat. No. 6,826,711, filed on Feb. 13, 2001 which claims the benefit of U.S. Provisional Patent Application Ser. No. 60/183,762 for: “System and Method for Decentralized Data Storage” filed Feb. 18, 2000, and U.S. Provisional Patent Application Ser. No. 60/245,920 filed Nov. 6, 2000 entitled “System and Method for Decentralized Data Storage” the disclosures of which are herein specifically incorporated by this reference.

BACKGROUND OF THE INVENTION

00021. Field of the Invention

0003The present invention relates, in general, to network data storage, and, more particularly, to software, systems and methods for high availability, high reliability data storage using parity data protection having an arbitrary dimensionality.

00042. Relevant Background

0005Economic, political, and social power are increasingly managed by data. Transactions and wealth are represented by data. Political power is analyzed and modified based on data. Human interactions and relationships are defined by data exchanges. Hence, the efficient distribution, storage, and management of data is expected to play an increasingly vital role in human society.

0006The quantity of data that must be managed, in the form of computer programs, databases, files, and the like, increases exponentially. As computer processing power increases, operating system and application software becomes larger. Moreover, the desire to access larger data sets such as those comprising multimedia files and large databases further increases the quantity of data that is managed. This increasingly large data load must be transported between computing devices and stored in an accessible fashion. The exponential growth rate of data is expected to outpace improvements in communication bandwidth and storage capacity, making the need to handle data management tasks using conventional methods even more urgent.

0007High reliability and high availability are increasingly important characteristics of data storage systems as data users become increasingly intolerant of lost, damaged, and unavailable data. Data storage mechanisms ranging from volatile random access memory (RAM), non-volatile RAM, to magnetic hard disk and tape storage, as well as others, are subject to component failure. Moreover, the communication systems that link users to the storage mechanisms are subject to failure, making the data stored behind the systems temporarily or permanently unavailable. Varying levels of reliability and availability are achieved by techniques generally referred to as “parity”.

0008Parity storage, as used herein, refers to a variety of techniques that are utilized to store redundant information, error correcting code (ECC), and/or actual parity information (collectively referred to as “parity information”) in addition to primary data (i.e., the data set to be protected). The parity information is used to access or reconstruct primary data when the storage devices in which the primary data is held fail or become unavailable.

0009Parity may be implemented within single storage devices, such as a hard disk, to allow recovery of data in the event a portion of the device fails. For example, when a sector of a hard disk fails, parity enables the information stored in the failed sector to be recreated and stored at a non-failed sector. Some RAM implementations use ECC to correct memory contents as they are written and read from memory.

0010Redundant array of independent disks (RAID) technology has developed in recent years as a means for improving storage reliability and availability. The concept, as initially conceived, contemplated the clustering of small inexpensive hard disks into an array such that the array would appear to the system as a single large disk. Simple arrays, however, actually reduced the reliability of the system to that of the weakest member. In response, a variety of methods (i.e., RAID technology) for storing data throughout the array in manners that provided of redundancy and/or parity were developed to provide varying levels of data protection.

0011Conventional RAID (redundant array of independent disks) systems provide a way to store the same data in different places (thus, redundantly) on multiple storage devices such as hard disk drives. By placing data on multiple disks, input/output (I/O) operations can overlap in a balanced way, distributing the load across disks in the array and thereby improving performance. Since using multiple disks in this manner increases the mean time between failure (MTBF) for the system as a whole with respect to data availability, storing data redundantly also increases fault-tolerance. A RAID system relies on a hardware or software controller to hide the complexities of the actual data management so that RAID systems appear to an operating system to be a single logical volume. However, RAID systems are difficult to scale because of physical limitations on the cabling and controllers. Also, RAID systems are highly dependent on the controllers so that when a controller fails, the data stored behind the controller becomes unavailable. Moreover, RAID systems require specialized, rather than commodity hardware, and so tend to be expensive solutions.

0012RAID solutions are also relatively expensive to maintain, as well as difficult and time consuming to properly configure. RAID systems are designed to enable recreation of data on a failed disk or controller but the failed disk must be replaced to restore high availability and high reliability functionality. Until replacement occurs, the system is vulnerable to additional device failures. Condition of the system hardware must be continually monitored and maintenance performed as needed to maintain functionality. Hence, RAID systems must be physically situated so that they are accessible to trained technicians who can perform required maintenance. Not only are the man-hours required to configure and maintain a RAID system expensive, but since most data losses are due to human error, the requirement for continual human monitoring and intervention decreases the overall reliability of such a system. This limitation also makes it difficult to set up a RAID system at a remote location or in a foreign country where suitable technicians would have to be found and/or transported to the locale in which the RAID equipment is installed to perform maintenance functions.

0013RAID systems (levels 0–5) cannot be expanded in minimal increments (e.g. adding a single storage element) while the system is in operation. The addition of a storage element requires that the entire system be brought down, parity recalculated, and then data restored. Hence, expanding the capacity addressed by RAID systems may result in data unavailability for indefinite amounts of time.

0014Moreover, RAID systems cannot scope levels of parity protection differently for arbitrarily small subsets of data within the overall data set protected. A RAID controller is configured to provide one type of parity protection at a time on a fixed, known set of storage devices. However, different types of data have very different and highly varied protection requirements. Mission critical data may need an extremely high level of protection, whereas data such as program files and seldom used documents may need little or no protection at all. Currently, users must either implement multiple systems to provide varying levels of protection to different types of data, or compromise their data protection needs by either paying too much to protect non-critical data, or by providing less than desired protection for critical data.

0015Current RAID systems do not provide a practical method by which parity data can be used not only to reconstruct primary data but also to serve data requests in lieu of or in addition to serving those requests directly from the primary data itself. With the exception of mirrored data protection systems, parity information is generally used in the event of a catastrophe to serve requests for lost data only while the primary data is being reconstructed from this parity information. After reconstruction of the primary data, data is once again served from the reconstructed primary only, not the parity information. This increases the effective overhead cost of parity data, as parity information is only passively stored by the storage system rather than actively being used to improve performance during normal operation.

0016NAS (network-attached storage) refers to hard disk storage that is set up with its own network address rather than being attached to an application server. File requests are mapped to the NAS file server rather than being routed through an application server device. NAS may perform I/O operations using RAID internally (i.e., within a NAS node). NAS may also automate mirroring of data to one or more other NAS devices to further improve fault tolerance. This mirroring may be done synchronously or asynchronously, but in both cases network limitations provide range restrictions on geographic separation. Because NAS devices can be added to a network, they may enable some scaling of the aggregate network storage capacity by adding additional NAS nodes. However, NAS devices are constrained in RAID applications to the abilities provided by conventional hardware and software based RAID controllers. NAS systems do not generally enable mirroring and parity across nodes, and so any single point of failure at a typical NAS node makes all of the data stored at that NAS node unavailable. RAID systems are not designed to provide efficient, redundant, and fault tolerant data storage in distributed network data storage environments.

0017In general, current parity protection systems provide one-dimensional parity protection, with some systems providing up to two-dimensional parity protection. One-dimensional parity protection means that one set of parity information is created and maintained for a given primary data set. Hence, the system is vulnerable to simultaneous failure of primary data storage and the associated parity data storage. RAID level <b>6</b> provides two-dimensional parity using two independent, distributed parity groups. However, there remains a need for systems and methods for efficiently providing greater dimensions, and preferably arbitrarily large dimensions of parity protection.

0018Philosophically, the way data is conventionally managed is inconsistent with the hardware devices and infrastructures that have been developed to manipulate and transport data. For example, computers are characteristically general-purpose machines that are readily programmed to perform a virtually unlimited variety of functions. In large part, however, computers are loaded with a fixed, slowly changing set of data that limits their general-purpose nature to make the machines special-purpose. Advances in processing speed, peripheral performance and data storage capacity are most dramatic in commodity computers and computer components. Yet many data storage solutions cannot take advantage of these advances because they are constrained rather than extended by the storage controllers upon which they are based. Similarly, the Internet was developed as a fault tolerant, multi-path interconnection. However, network resources are conventionally implemented in specific network nodes such that failure of the node makes the resource unavailable despite the fault-tolerance of the network to which the node is connected. Continuing needs exist for highly available, highly reliable, and highly scaleable data storage solutions.

SUMMARY OF THE INVENTION

0019Briefly stated, the present invention involves a data storage system implementing an N-dimensional parity paradigm. A system for parity distribution is preferably implemented in a distributed network storage environment, but may also be implemented in a conventional storage array or a single storage device environment. A mechanism for the dynamic addition and subtraction of storage elements as well as the capability to dynamically modify the degree of redundancy protection enjoyed by individual data elements and sets of elements in an arbitrary way is provided.

0020In another aspect, the present invention involves a method for data protection with an arbitrary number of parity dimensions in which a data element is selected for entry and a degree of fault tolerance desired for that data element is determined. A number of non-intersecting parity groups (i.e., where no two members of a single parity group reside on the same physical device) are associated with the primary data element from an arbitrarily large pool of available storage locations which reside on an arbitrary number of physical storage devices. A location for the primary data element to be stored is selected based on user-specified or system-specified metrics. The data element is written to its primary location and the parity elements associated with the previously chosen parity groups are updated. Once the primary write operation and associated parity updates are confirmed, the data entry transaction is finalized. System read operations either read the data element directly from its primary location or read an image of the data element reconstructed from one or more of its associated parity groups. The criteria on which this choice is based are arbitrary, but generally performance related. The process by which primary data elements and the parity elements associated with the logical parity groups to which the primary data belongs are maintained, migrated, and reconstructed due to network, server, disk, and human error is preferably automated and fully dynamic.

BRIEF DESCRIPTION OF THE DRAWINGS

<figref idref="DRAWINGS">FIG. 1</figref> shows a networked computer environment in which the present invention is implemented;

<figref idref="DRAWINGS">FIG. 2</figref> shows a computing environment in which the present invention is implemented at a different level of detail;

<figref idref="DRAWINGS">FIG. 3</figref> illustrates components of a RAIN element in accordance with an embodiment of the present invention;

<figref idref="DRAWINGS">FIG. 4</figref> illustrates entity relationships between various entities in a specific embodiment of the present invention;

<figref idref="DRAWINGS">FIG. 5</figref> illustrates a logical implementation of a first exemplary parity embodiment;

<figref idref="DRAWINGS">FIG. 6</figref> illustrates a logical implementation of a second exemplary parity embodiment;

<figref idref="DRAWINGS">FIG. 7-FIG</figref>. <b>9</b> illustrate multiple parity dimensions;

<figref idref="DRAWINGS">FIG. 10</figref> shows storage data structures in accordance with the present invention;

<figref idref="DRAWINGS">FIG. 11</figref> through <figref idref="DRAWINGS">FIG. 13</figref> shows data structures resulting from dynamically modifying parity groups in accordance with the present invention; and

<figref idref="DRAWINGS">FIG. 14</figref> shows data reconstruction in accordance with the present invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

0031The present invention is directed to 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.

0032In general, the present invention provides a parity system, herein called “N-dimensional parity”, in which a primary data set can be protected with an arbitrarily large number of parity dimensions whose size is arbitrarily configurable. N-dimensional parity permits several points of failure without loss of data. As a result, failure or unavailability of any particular primary storage device, parity storage device, or set of parity storage devices will not affect the system's ability to reconstruct and serve the primary data set stored in the system. In some embodiments, data requests are served directly from the parity information rather than the primary data even when the primary data is available, thereby reducing the effective overhead of maintaining parity as well as increasing overall system performance.

0033In general, preferred embodiments of the present invention involve a redundant array of independent nodes (RAN) distributed throughout a network topology. Nodes may be located on local area networks (LANs), metropolitan area networks (MAN), wide area networks (WANs), or any other network having spatially distanced nodes. Nodes are preferably internetworked using mechanisms such as the Internet. In specific embodiments, at least some nodes are publicly accessible for data access requests through public networks such as the Internet and nodes communicate with each other by way of private networks and/or virtual private networks, which may themselves be implemented using Internet resources.

0034Significantly, the nodes implement not only storage capacity and read/write operations, but sufficient intelligence to communicate with each other and manage not only their own storage, but storage on other nodes. For example, storage nodes maintain state information describing other storage nodes capabilities, connectivity, capacity, and the like. Also, storage nodes may be enabled to cause storage functions such as read/write functions to be performed on other storage nodes. Traditional storage systems do not allow peer-to-peer type information sharing amongst the storage devices themselves. In contrast, the present invention enables peer-to-peer information exchange and, as a result, implements a significantly more robust system than that provided by conventional systems that is, in addition, highly scaleable. The system is scaleable because, among other reasons, most storage tasks can be implemented in parallel by multiple storage devices. The system is robust because the storage nodes can be globally distributed—making the system immune to events in any one or more geographical, political, or network topological locations.

0035The present invention is implemented in a globally distributed storage system involving storage nodes that are optionally managed by distributed storage allocation management (SAM) processes. The present invention is directed to the architecture and implementation of the parity mechanisms within the storage nodes, and so is not limited to use with the particular SAM processes or RAIN storage devices disclosed in the exemplary embodiments. SAM and RAIN systems are good examples of a storage architecture that can be dynamically expanded to allow for incremental changes in storage capacity as well as the location and performance of storage capacity. However, the exemplary SAM processes and RAIN storage devices are discussed to the extent they illustrate the performance of the storage node architecture of the present invention.

0036The nodes are connected to a network and data is preferably distributed across the nodes in a multi-level, fault-tolerant fashion. In contrast to conventional RAID systems, the present invention enables mirroring and parity operations to be spread across nodes rather than simply across hard drives within a single node. Nodes can be dynamically added to and removed from the system while the data managed by the system remains available. In this manner, the system of the present invention avoids single or multiple failure points in a manner that is orders of magnitude more robust than conventional RAID systems.

0037The present invention is illustrated and described in terms of a distributed computing environment such as an enterprise computing system using public communication channels such as the Internet. However, an important feature of the present invention is that it is readily scaled upwardly and downwardly to meet the needs of a particular application. Accordingly, unless specified to the contrary, the present invention is applicable to significantly larger, more complex network environments as well as small network environments such as conventional LANs. Similarly, essential teachings of the present invention can be implemented in different portions of a single storage device or a portion of a storage device.

0038The present invention is directed to data storage on a network <b>101</b> shown in <figref idref="DRAWINGS">FIG. 1</figref>. <figref idref="DRAWINGS">FIG. 1</figref> shows an exemplary internetwork environment <b>101</b> such as the Internet. The Internet is a global internetwork formed by logical and physical connections between multiple wide area networks (WANs) <b>103</b> and local area networks (LANs) <b>104</b>. An Internet backbone <b>102</b> represents the main lines and routers that carry the bulk of the traffic. The backbone is formed by the largest networks in the system that are operated by major Internet service providers (ISPs) such as GTE, MCI, Sprint, UUNet, and America Online, for example. While single connection lines are used to conveniently illustrate WAN <b>103</b> and LAN <b>104</b> connections to the Internet backbone <b>102</b>, it should be understood that in reality multi-path, routable wired and/or wireless connections exist between multiple WANs <b>103</b> and LANs <b>104</b>. This makes internetwork <b>101</b> robust when faced with single or multiple points of failure.

0039It is important to distinguish network connections from internal data pathways implemented between peripheral devices within a computer. A “network” comprises a system of general purpose, usually switched, physical connections that enable logical connections between processes operating on storage nodes <b>105</b>. The physical connections implemented by a network are typically independent of the logical connections that are established between processes using the network. In this manner, a heterogeneous set of processes ranging from file transfer to mail transfer and the like can use the same physical network. Conversely, the network can be formed from a heterogeneous set of physical network technologies that are transparent to the logically connected processes using the network. Because the logical connection between processes implemented by a network is independent of the physical connection, internetworks are readily scaled to a virtually unlimited number of nodes over long distances.

0040In contrast, internal data pathways such as a system bus, Peripheral Component Interconnect (PCI) bus, Intelligent Drive Electronics (IDE) bus, Small Computer System Interface (SCSI) bus, Fibre Channel, and the like define physical connections that implement special-purpose connections within a computer system. These connections implement physical connections between physical devices as opposed to logical connections between processes. These physical connections are generally characterized by a limited distance between components, a limited number of devices that can be coupled to the connection, and constrained format of devices that can be connected over the connection.

0041To generalize the above discussion, the term “network” as it is used herein refers to a means enabling a physical and logical connection between devices that 1) enables at least some of the devices to communicate with external sources, and 2) enables the devices to communicate with each other. It is contemplated that some of the internal data pathways described above could be modified to implement the peer-to-peer style communication of the present invention, however, such functionality is not currently available in commodity components. Moreover, such modification, while useful, would fail to realize the full potential of the present invention as storage nodes implemented across, for example, a SCSI bus would inherently lack the level of physical and topological diversity that can be achieved with the present invention.

0042Referring again to <figref idref="DRAWINGS">FIG. 1</figref>, the present invention is implemented by placing storage devices at storage nodes <b>105</b>. The storage devices at any storage node <b>105</b> may comprise a single hard drive, may comprise a managed storage system such as a conventional RAID device having multiple hard drives configured as a single logical volume, or may comprise any reasonable hardware configuration spanned by these possibilities. Significantly, the present invention manages redundancy operations across nodes, as opposed to within nodes, so that the specific configuration of the storage within any given node can be varied significantly without departing from the present invention.

0043Optionally, one or more nodes <b>105</b> implement storage allocation management (SAM) processes that manage data storage across multiple nodes <b>105</b> in a distributed, collaborative fashion. SAM processes may be implemented in a centralized fashion within special-purpose nodes <b>105</b>. Alternatively, SAM processes are implemented within some or all of storage nodes <b>105</b>. The SAM processes communicate with each other and handle access to the actual storage devices within any particular storage node <b>105</b>. The capabilities, distribution, and connections provided by the storage nodes <b>105</b> in accordance with the present invention enable storage processes (e.g., SAM processes) to operate with little or no centralized control for the system as whole.

0044In a particular implementation, SAM processes provide data distribution across storage nodes <b>105</b> and implement recovery in a fault-tolerant fashion across network nodes <b>105</b> in a manner similar to paradigms found in RAID storage subsystems. However, because SAM processes operate across nodes rather than within a single node or within a single computer, they allow for arbitrarily large dimensions of parity—thereby providing a storage system with “n-dimensional” parity. Moreover, it is not simply that the SAM processes operate across network nodes, but also that SAM processes are themselves distributed in a highly parallel and redundant manner, especially when implemented within some or all of storage nodes <b>105</b>. By way of this distribution of functionality as well as data, failure of any node or group of nodes will be much less likely to affect the overall availability of stored data.

0045For example, SAM processes can recover even when a network node <b>105</b>, LAN <b>104</b>, or WAN <b>103</b> becomes unavailable. Moreover, even when a portion of the Internet backbone <b>102</b> becomes unavailable through failure or congestion the SAM processes can recover using data distributed on nodes <b>105</b> and functionality that is distributed on the various SAM nodes <b>106</b> that remain accessible. In this manner, the present invention leverages the robust nature of internetworks to provide unprecedented availability, reliability, and robustness.

0046Dynamically selected sets of storage nodes <b>105</b> are logically associated to form parity groups as suggested by the cross-hatched and solid-filled ones of nodes <b>105</b> in <figref idref="DRAWINGS">FIG. 1</figref>. Parity groups are distributed across different geography, network topology, political boundaries, and the like to provide a kind of data protection not possible with conventional RAID-like storage.

0047<figref idref="DRAWINGS">FIG. 1</figref> may suggest that each member of a parity group is an entire storage node <b>105</b>, which is possible, but not required. Each storage node <b>105</b> comprises a number of storage areas. Each storage area can be roughly equated to the storage capacity required to store a stripe of data or parity associated with a data set. In most implementations it is contemplated that parity group members comprise storage areas, not entire storage nodes <b>105</b>. Data or parity information is stored in the storage area, and any given storage node may hold data/parity from a number of data sets in its various storage areas. Conversely, each member of a parity group may comprise multiple nodes <b>105</b> where the size of a storage area is greater than the capacity of a single node <b>105</b>. A parity group is defined by the selection of storage areas from various storage nodes that are logically combined to generate parity information that is stored in another storage area.

0048Parity groups are formed by sets of storage nodes <b>105</b>, or more specifically, by data structures within selected nodes <b>105</b>. The size of a parity group is determined by the number of stripes (i.e., storage areas) that are associated with a set of parity information. Cross-hatched nodes <b>105</b> suggest a first parity group and solid-filled nodes <b>105</b> suggest a second, independent or non-intersecting parity group. A non-intersecting parity groups refers to groups in which no two members of a single parity group reside on the same physical device. A given data set is stored across an arbitrary number of parity groups of varying size according to a specified parity scheme to achieve the desired level of protection for the data set. In accordance with the present invention, some or all of the members of the parity group are used to store the actual data set (e.g., primary data) and some or all of the members are members of the parity group are used to store parity information. In an alternative embodiment, the parity group members are used to store only parity information, not the primary data set, so that any k parity members are sufficient to reconstruct the primary data set, but that k−1 pieces give NO information about the primary data set.

0049One feature of the present invention is that the membership in any parity group can be dynamically determined. Similarly, the number of storage nodes <b>105</b> in a parity group can be dynamically increased or decreased to meet instantaneous needs. Moreover, a data set in a given parity group can be dynamically added to another parity group. The flexibility provided by the present invention enables greater control over and manipulation of data protection than has been possible with conventional data mirroring or RAID-type protections. For example, data can be protected using multiple cost/speed arrangements. Small parity groups are faster to reconstruct and read data from, but expensive. Large parity groups conserve space, but have high communication overhead during reconstruction. The dynamic configuration capabilities provided by the present invention provide a method for efficiently and economically providing multiple levels of data protection so that users can select the level of data protection enjoyed by various data sets.

0050Parity reconstruction can also be used as an alternative source for data even when faults have not occurred. Parity effectively offers a second source for data. N-dimensional parity offers multiple alternative sources for data including mirror copies and parity information. In complex systems it is contemplated that there can be situations in which it is faster to reconstruct data from its associated parity information than to read it from a non-parity (e.g., primary) source. Because the present invention allows data requests for a primary data set to be reconstructed and served from one or more of the parity groups it is associated with even when that primary data is available, performance can even further be enhanced by establishing a large number of small parity groups for data sets under a high transaction load. For example, in a network storage system, the resource holding non-parity versions of requested data may be less desirable to access than the same data reconstructed from parity information. This may be because the resource is currently operating under high load, at a topologically distant location, or has other undesirable characteristics.

0051<figref idref="DRAWINGS">FIG. 2</figref> shows an alternate view of an exemplary network computing environment in which the present invention is implemented. Internetwork <b>101</b> enables the interconnection of a heterogeneous set of computing devices and mechanisms ranging from a supercomputer or data center <b>201</b> to a hand-held or pen-based device <b>206</b>. While such devices have disparate data storage needs, they share an ability to retrieve data via network <b>101</b> and operate on that data using their own resources. Disparate computing devices including mainframe computers (e.g., VAX station <b>202</b> and IBM AS/400 station <b>208</b>) as well as personal computer or workstation class devices such as IBM compatible device <b>203</b>, Macintosh device <b>204</b> and laptop computer <b>205</b> are easily interconnected via internetwork <b>101</b>. The present invention also contemplates wireless device connections to devices such as cell phones, laptop computers, pagers, hand held computers, and the like.

0052Internet-based network <b>213</b> comprises a set of logical connections, some of which are made through internetwork <b>101</b>, between a plurality of internal networks <b>214</b>. Conceptually, Internet-based network <b>213</b> is akin to a WAN <b>103</b> in that it enables logical connections between spatially distant nodes. Internet-based networks <b>213</b> may be implemented using the Internet or other public and private WAN technologies including leased lines, Fibre Channel, frame relay, and the like.

0053Similarly, internal networks <b>214</b> are conceptually akin to LANs <b>104</b> shown in <figref idref="DRAWINGS">FIG. 1</figref> in that they enable logical connections across more limited distances than those allowed by a WAN <b>103</b>. Internal networks <b>214</b> may be implemented using LAN technologies including Ethernet, Fiber Distributed Data Interface (FDDI), Token Ring, Appletalk, Fibre Channel, and the like.

0054Each internal network <b>214</b> connects one or more RAIN elements <b>215</b> to implement RAIN nodes <b>105</b>. RAIN elements <b>215</b> illustrate an exemplary instance of a hardware/software platform that implements a RAIN node <b>105</b>. Conversely, a RAIN node <b>105</b> refers to a more abstract logical entity that illustrates the presence of the RAIN functionality to external network users. Each RAIN element <b>215</b> comprises a processor, memory, and one or more mass storage devices such as hard disks. RAIN elements <b>215</b> also include hard disk controllers that may be conventional EIDE or SCSI controllers, or may be managing controllers such as RAID controllers. RAIN elements <b>215</b> may be physically dispersed or co-located in one or more racks sharing resources such as cooling and power. Each node <b>105</b> is independent of other nodes <b>105</b> in that failure or unavailability of one node <b>105</b> does not affect availability of other nodes <b>105</b>, and data stored on one node <b>105</b> may be reconstructed from data stored on other nodes <b>105</b>.

0055The perspective provided by <figref idref="DRAWINGS">FIG. 2</figref> is highly physical and it should be kept in mind that physical implementation of the present invention may take a variety of forms. The multi-tiered network structure of <figref idref="DRAWINGS">FIG. 2</figref> may be altered to a single tier in which all RAIN nodes <b>105</b> communicate directly with the Internet. Alternatively, three or more network tiers may be present with RAIN nodes <b>105</b> clustered behind any given tier. A significant feature of the present invention is that it is readily adaptable to these heterogeneous implementations.

0056RAIN elements <b>215</b> are shown in greater detail in <figref idref="DRAWINGS">FIG. 3</figref>. In a particular implementation, RAIN elements <b>215</b> comprise computers using commodity components such as Intel-based microprocessors <b>301</b> mounted on a motherboard supporting a PCI bus <b>303</b> and <b>128</b> megabytes of random access memory (RAM) <b>302</b> housed in a conventional AT or ATX case. SCSI or IDE controllers <b>306</b> may be implemented on the motherboard and/or by expansion cards connected to the PCI bus <b>303</b>. Where the controllers <b>306</b> are implemented only on the motherboard, a PCI expansion bus <b>303</b> is optional. In a particular implementation, the motherboard implements two mastering EIDE channels and an PCI expansion card is used to implement two additional mastering EIDE channels so that each RAIN element <b>215</b> includes up to four EIDE hard disks <b>307</b>. In the particular implementation, each hard disk <b>307</b> comprises an 80 gigabyte hard disk for a total storage capacity of 320 gigabyte per RAIN element <b>215</b>. The casing also houses supporting mechanisms such as power supplies and cooling devices (not shown).

0057The specific implementation discussed above is readily modified to meet the needs of a particular application. Because the present invention uses network methods to communicate with the storage nodes, the particular implementation of the storage node is largely hidden from the devices using the storage nodes, making the present invention uniquely receptive to modification of node configuration and highly tolerant of systems comprised by heterogeneous storage node configurations. For example, processor type, speed, instruction set architecture, and the like can be modified and may vary from node to node. The hard disk capacity and configuration within RAIN elements <b>215</b> can be readily increased or decreased to meet the needs of a particular application. Although mass storage is implemented using magnetic hard disks, other types of mass storage devices such as magneto-optical, optical disk, digital optical tape, holographic storage, atomic force probe storage and the like can be used as suitable equivalents as they become increasingly available. Memory configurations including RAM capacity, RAM speed, RAM type (e.g., DRAM, SRAM, SDRAM) can vary from node to node making the present invention incrementally upgradeable to take advantage of new technologies and component pricing. Network interface components may be provided in the form of expansion cards coupled to a mother board or built into a mother board and may operate with a variety of available interface speeds (e.g., 10 BaseT Ethernet, 100 BaseT Ethernet, Gigabit Ethernet, 56K analog modem) and can provide varying levels of buffering, protocol stack processing, and the like.

0058Specifically, it is contemplated that the processing power, memory, network connectivity and other features of the implementation shown in <figref idref="DRAWINGS">FIG. 3</figref> could be integrated within a disk drive controller and actually integrated within the housing of a disk drive itself. In such a configuration, a RAIN element <b>215</b> might be deployed simply by connecting such an integrated device to an available network, and multiple RAIN elements <b>215</b> might be housed in a single physical enclosure.

0059Each RAIN element <b>215</b> may execute an operating system. The particular implementations use a UNIX operating system (OS) or UNIX-variant OS such as Linux. It is contemplated, however, that other operating systems including DOS, Microsoft Windows, Apple Macintosh OS, OS/2, Microsoft Windows NT and the like may be equivalently substituted with predictable changes in performance. Moreover, special purpose lightweight operating systems or micro kernels may also be used, although cost of development of such operating systems may be prohibitive. The operating system chosen implements a platform for executing application software and processes, mechanisms for accessing a network, and mechanisms for accessing mass storage. Optionally, the OS supports a storage allocation system for the mass storage via the hard disk controller(s).

0060Various application software and processes can be implemented on each RAIN element <b>215</b> to provide network connectivity via a network interface <b>304</b> using appropriate network protocols such as User Datagram Protocol (UDP), Transmission Control Protocol (TCP), Internet Protocol (IP), Token Ring, Asynchronous Transfer Mode (ATM), and the like.

0061In the particular embodiments, the data stored in any particular node <b>105</b> can be recovered using data at one or more other nodes <b>105</b> using data recovery and storage management processes. These data recovery and storage management processes preferably execute on a node <b>106</b> and/or on one of the nodes <b>105</b> separate from the particular node <b>105</b> upon which the data is stored. Conceptually, storage management is provided across an arbitrary set of nodes <b>105</b> that may be coupled to separate, independent internal networks <b>215</b> via internetwork <b>213</b>. This increases availability and reliability in that one or more internal networks <b>214</b> can fail or become unavailable due to congestion or other events without affecting the overall availability of data.

0062In an elemental form, each RAIN element <b>215</b> has some superficial similarity to a network attached storage (NAS) device. However, because the RAIN elements <b>215</b> work cooperatively, the functionality of a RAIN system comprising multiple cooperating RAIN elements <b>215</b> is significantly greater than a conventional NAS device. Further, each RAIN element preferably supports data structures that enable parity operations across nodes <b>105</b> (as opposed to within nodes <b>105</b>). These data structures enable operation akin to RAID operation, however, because the RAIN operations are distributed across nodes and the nodes are logically, but not necessarily physically connected, the RAIN operations are significantly more fault tolerant and reliable than conventional RAID systems.

0063<figref idref="DRAWINGS">FIG. 4</figref> shows an exemplary storage system in accordance with the present invention from another perspective. Client <b>503</b> represents any of a number of network appliances that may use the storage system in accordance with the present invention. Client <b>503</b> uses a file system or other means for generating storage requests directed to one of accessible storage nodes <b>215</b>. Not all storage nodes <b>215</b> need to be accessible through Internet <b>101</b>. In one implementation, client <b>503</b> makes a storage request to a domain name using HyperText Transport Protocol (HTTP), Secure HyperText Transport Protocol (HTTPS), File Transfer Protocol (FTP), or the like. In addition to or instead of client <b>503</b> coupling through a public network <b>101</b>, a client <b>503</b> may be connected to the private network <b>501</b> to access the storage device(s). The Internet Domain Name System (DNS) will resolve the storage request to a particular IP address identifying a specific storage node <b>215</b> that implements the SAM processes. Client <b>503</b> then directs the actual storage request using a mutual protocol to the identified IP address.

0064The storage request is directed using network routing resources to a storage node <b>215</b> assigned to the IP address. This storage node then conducts storage operations (i.e., data read and write transactions) on mass storage devices implemented in the storage node <b>215</b>, or on any other storage node <b>215</b> that can be reached over an explicit or virtual private network <b>501</b>. Some storage nodes <b>215</b> may be clustered as shown in the lower left side of FIG. <b>4</b>., and clustered storage nodes may be accessible through another storage node <b>215</b>.

0065Preferably, all storage nodes are enabled to exchange state information via private network <b>501</b>. Private network <b>501</b> is implemented as a virtual private network over Internet <b>101</b> in the particular examples. In the particular examples, each storage node <b>215</b> can send and receive state information. However, it is contemplated that in some applications some storage nodes <b>215</b> may need only to send their state information while other nodes <b>215</b> act to send and receive storage information. System state information may be exchanged universally such that all storage nodes <b>215</b> contain a consistent set of state information about all other storage nodes <b>215</b>. Alternatively, some or all storage nodes <b>215</b> may only have information about a subset of storage nodes <b>215</b>.

0066Using a parity data protection scheme, data is spread across multiple RAIN nodes <b>105</b> and/or multiple RAIN systems as described above. In event of a failure of one RAIN element <b>215</b>, RAIN node <b>105</b>, or RAIN system, high availability and high reliability functionality can be restored by accessing an alternate RAIN node <b>105</b> or RAIN system. At one level, this reduces the criticality of a failure so that it can be addressed days, weeks, or months after the failure without affecting system performance. At another level, it is contemplated that failures may never need to be addressed. In other words, a failed disk might never be used or repaired. This eliminates the need to deploy technical resources to distant locations. In theory, a RAIN node <b>105</b> can be set up and allowed to run for its entire lifetime without maintenance.

0067RAIN nodes <b>105</b> desirably implement a “heartbeat” process that informs other RAIN nodes or storage management processes of their existence and their state of operation. For example, when a RAIN node <b>105</b> is attached to a network <b>214</b> or <b>215</b>, the heartbeat message indicates that the RAIN node <b>105</b> is available, and notifies of its available storage. The RAIN node <b>105</b> can report disk failures that require parity operations. Loss of the heartbeat might result in reconstruction of an entire node at an alternate node. In a particular implementation, the heartbeat message is unicast to a single management node, or multicast or broadcast to a plurality of management nodes periodically or intermittently. The broadcast may be scheduled at regular or irregular intervals, or may occur on a pseudorandom schedule. The heartbeat may also be derived by the presence of other traffic from or related to a node. The heartbeat message includes information such as the network address of the RAIN node <b>105</b>, storage capacity, state information, maintenance information and the like.

0068Through this exchange of state information and the heartbeat message, nodes <b>105</b> (and/or SAM processes) become aware of other nodes <b>105</b>. This enables nodes <b>105</b> to be seamlessly added and removed from the system. As nodes <b>105</b> are added and removed, the parity operations in accordance with the present invention adapt to use newly added nodes by allocating storage space in the nodes for data/parity stripes. As nodes are removed, the parity operations in accordance with the present invention reconstruct data/parity information stored on the removed node and re-establish data protection with other available nodes <b>105</b>.

0069<figref idref="DRAWINGS">FIG. 5</figref> illustrates a logical implementation of a first exemplary parity embodiment in accordance with the present invention. Specifically, <figref idref="DRAWINGS">FIG. 5</figref> shows a 3×3 uniform parity scheme. In <figref idref="DRAWINGS">FIG. 5</figref>, nine units of data (D<b>1</b>–D<b>9</b>) are held in six unrelated parity groups <b>505</b> and <b>506</b>. The units of data D<b>1</b>–D<b>9</b> and parity are preferably stored in independent nodes <b>105</b>, but may be stored in separate locations of a single node <b>105</b> with predicable affects on availability and reliability. In this example, the loss of any two units of data or parity would allow recover of all original data and parity.

0070<figref idref="DRAWINGS">FIG. 6</figref> illustrates a logical implementation of a second exemplary parity embodiment demonstrating a non-uniform data parity scheme. In <figref idref="DRAWINGS">FIG. 6</figref>, the nine different units of data (D<b>1</b>–D<b>9</b>) are in different parity groups. All of the data as configured below is protected against the loss of a single unit of data or parity. Data units D<b>1</b>–D<b>8</b> are protected against loss of two units of data or parity, while data element D<b>9</b> is protected only against a single unit loss.

0071Conventional parity systems provide a single level of parity protection to all data units stored therein. While convenient to implement, this “one size fits all” approach provides little flexibility to meet customer needs. In contrast, by using the non-uniform parity capability of the present invention, data unit D<b>9</b> can be stored at lower cost while the same system provides higher levels of protection as needed. <figref idref="DRAWINGS">FIG. 5</figref> and <figref idref="DRAWINGS">FIG. 6</figref> show only two dimensional parity and it should be understood that much greater variety in protection levels is available with n-dimensional parity schemes.

0072FIG. <b>7</b>–<figref idref="DRAWINGS">FIG. 9</figref> illustrate multiple parity dimensions in accordance with the present invention. While particular advantages are achieved with higher order parity, it should be understood that the present invention can be configured to provide lower order parity such as one-dimensional (<figref idref="DRAWINGS">FIG. 7</figref>) and two-dimensional (<figref idref="DRAWINGS">FIG. 8</figref>). Significantly, some data sets can be protected using the schemes shown in <figref idref="DRAWINGS">FIG. 7</figref> and <figref idref="DRAWINGS">FIG. 8</figref> while others use higher order parity such as three-dimensional parity (<figref idref="DRAWINGS">FIG. 9</figref>) at the same time, using the same hardware and software resources.

0073In other words, any given set of SAM processes can take a first data set and allocate space within a number of nodes <b>105</b> to provide single dimensional parity for that first data set. The same set of SAM processes can take a second data set and allocate space within the number of nodes <b>105</b>, or a different set of nodes <b>105</b>, to provide three dimensional, four dimensional, or any desired order parity for the second data set. Further, the number of dimensions of parity associated with a given data set can be increased or decreased, as can the size of the parity group itself.

0074<figref idref="DRAWINGS">FIG. 10</figref> shows storage data structures in accordance with the present invention. <figref idref="DRAWINGS">FIG. 10</figref> depicts four storage areas each containing one stripe. Stripes A, B and C in storage areas <b>1001</b>–<b>1103</b>, respectively, are data stripes. Storage area <b>1004</b> holds the parity stripe holding XOR'ed images of A, B and C. The configuration of <figref idref="DRAWINGS">FIG. 10</figref> shows how a single dimension of parity is constructed.

0075The XOR operation does not require all objects to have the same length. For those portions of A, B, or C that do not overlap in the parity stripe, the value is the XOR of those stripes that do. Another way to think about this is to imagine that each stripe A, B and C are padded to the longest length with zeros, so the non-overlapping regions are calculated as XOR(A<b>1</b>,B<b>1</b>,C<b>1</b>); XOR(<b>0</b>,B<b>2</b>,C<b>2</b>)=XOR(B<b>2</b>,C<b>2</b>); and XOR(<b>0</b>,B<b>3</b>,<b>0</b>)=B<b>3</b>.

0076<figref idref="DRAWINGS">FIG. 11</figref> through <figref idref="DRAWINGS">FIG. 13</figref> illustrates the addition of another storage area <b>1101</b> (shown in <figref idref="DRAWINGS">FIG. 11</figref>) to the system described in <figref idref="DRAWINGS">FIG. 10</figref> and a stripe inside it is allocated to hold D. D can be added to the parity stripe in storage area <b>1104</b> by an XOR operation as suggested in the altered parity information in storage area <b>1104</b> shown in <figref idref="DRAWINGS">FIG. 12</figref>. In order perform this operation, each unit of parity information is lengthened as needed to accommodate D's greater length. Note also that the XOR operation to place D into the parity stripe does not require reading A, B and C again because the existing values in P can be used. For example, the first segment of the parity stripe contains XOR(A<b>1</b>,B<b>1</b>,C<b>1</b>), let's call that value P<b>1</b>. So to add in D<b>1</b>, we need only perform XOR(P<b>1</b>,D<b>1</b>) which is the same as XOR(XOR(A<b>1</b>,B<b>1</b>,C<b>1</b>), D<b>1</b>) which is equivalent to XOR(A<b>1</b>,B<b>1</b>,C<b>1</b>,D<b>1</b>). This greatly lessens the administrative overhead in managing parity groups and changing parity group membership.

0077After D joins the parity stripe, the parity stripe is as shown in <figref idref="DRAWINGS">FIG. 12</figref>. Suppose further that this new storage area <b>1101</b> is to be removed from the system. Before that happens the values associated with the D data set must be removed from the parity stripe it just joined. This is accomplished by performing the same operation used in adding it into parity, namely XOR'ing D's values into the existing parity image (as shown in <figref idref="DRAWINGS">FIG. 12</figref>). This is because XOR(D<b>1</b>,XOR(P<b>1</b>,D<b>1</b>) )=P<b>1</b>. After D has been XOR'ed out of the parity stripe, storage area <b>1104</b> (shown in <figref idref="DRAWINGS">FIG. 13</figref>) looks like a longer version of it's former self (shown in <figref idref="DRAWINGS">FIG. 10</figref>), with extra zeros (recall that XOR(D<b>4</b>,D<b>4</b>)=0) at the end from the lengthening operation above. The parity stripe shown in <figref idref="DRAWINGS">FIG. 13</figref> could then be reduced in length to remove the zeros if desired.

0078<figref idref="DRAWINGS">FIG. 14</figref> shows data reconstruction in accordance with the present invention. <figref idref="DRAWINGS">FIG. 14</figref> depicts two separate storage groups <b>1401</b> and <b>1402</b> with a parity stripe in <b>1402</b> that contains data from <b>1401</b>. Parity organized in such a way creates a means to access data at a distant location using the local data and parity. For example, the parity stripe in storage area <b>10</b> contains data stripe C from distant group <b>1401</b> XOR'ed together with data stripes G and J from the local group <b>1402</b>.

0079If the communications channel <b>1403</b> between <b>1401</b> and <b>1402</b> becomes so congested as to make timely access to data untenable, the stripes at <b>1401</b> would normally be effectively inaccessible at <b>1402</b> and the vice versa. Because, however, storage at <b>1402</b> has a parity stripe that contains an image of C XOR'ed together with parity members, namely Q, J and G, then it is possible to derive C from storage group <b>1402</b> alone. This is because XOR(Q,J,G) equals C. Organizing parity stripes using this property can provide alternative paths to data as an expanded form of fault tolerance and a way to enhance system performance.

0080Although the invention has been described and illustrated with a certain degree of particularity, it is understood that the present disclosure has been made only by way of example, and that numerous changes in the combination and arrangement of parts can be resorted to by those skilled in the art without departing from the spirit and scope of the invention, as hereinafter claimed.