System, Method, And Service For Providing A Generic RAID Engine And Optimizer

Abstract

A generic RAID engine system accepts an access request, accepts a metadata input comprising a layout description and, optionally, a plurality of resource optimization objectives, accepts a dynamic input comprising a dynamic state of an I/O stack comprising the generic RAID engine and a fault configuration of a plurality of storage devices in the I/O stack, and accepts RAID code input comprising information about the RAID code used by the I/O stack. The metadata input, the dynamic input, and the RAID code input are utilized to transform the access request into individual device reads and individual device writes such that RAID code relationships for the storage devices are maintained at all times. An optional optimizer module selects strategies that meet the resource optimization objectives.

1 . A method of providing a RAID engine in an I/O stack that comprises a data cache and a storage system having a plurality of storage devices, the method comprising:
 accepting an access request directed towards performing I/O operations affecting selected pages of the plurality of storage devices, the access request comprising any of the following I/O operations:
 a read request, 
 a write request, 
 a file read request, 
 a file write request, 
 a block read request, 
 a block write request, 
 a stripe rebuild request, 
 a stripe scrub request, 
 and a stripe migrate request; 
   accepting a metadata input comprising a layout description and, optionally, a plurality of resource optimization objectives: the layout description further comprising a description of a rotation, a stripe size, and an element size of each of the plurality of storage devices: each resource optimization objective further comprising for the access request the objective of minimizing the I/O operations for each of the plurality of storage devices and the objective of minimizing memory bus bandwidth;   accepting a dynamic input comprising
 a dynamic state of the I/O stack containing the RAID engine, 
 a fault configuration of the plurality of storage devices, the fault configuration further comprising a description of all known sector failures and a description of all known storage device failures, and 
 a description of the data cache that includes a description of clean pages in the data cache and a description of dirty pages in the data cache, the clean pages and the dirty pages being in a W-neighborhood of at least one of the selected pages; 
   accepting a RAID code generator matrix input comprising information about a RAID code used by the I/O operations;   transforming the access request into a plurality of individual operations, each individual operation selected from an operations group consisting of an individual device read request, an XOR calculation, an individual device write request, a RAID scrub request, a rebuild request, and a RAID migrate request, each such transformation of the access request being performed through and being dependent upon the metadata input, the dynamic input, and the RAID code generator matrix input while maintaining for each individual operation a plurality of RAID code relationships for the storage devices;
 the transforming of the access request into the individual device read request comprising the steps of:
 determining if at least one fault exists in the plurality of storage devices that prevent a successful read: 
 if the at least one fault exists, then performing further the following steps for each fault:
 computing a pseudo-inverse matrix of the generator matrix for the RAID code, 
 translating the pseudo-inverse for consideration to device reads, and XORs, and 
 generating a read I/O plan for performing individual device reads and XORs: 
 
 the transforming of the access request into the individual device write request comprising the following steps:
 constructing a plurality of affected party vectors, preparing a plurality of failure vectors as required by a degraded layout, 
 computing a plurality of inverse matrices, 
 generating a plurality of sub-plans by combining individual vectors, 
 reblocking the vectors as per the physical layout, and generating a write I/O plan comprising the matrices for performing individual device reads, XORs and writes; 
 
 the transforming of the access request into the RAID scrub request comprises generating a party check matrix based on the generator matrix for the RAID code; and 
 the transforming of the access request into the RAID migration request comprises employing different generator matrices for each of a source target RAID layout and a target RAID layout; 
 
 utilizing the party check matrix to ensure that all elements in the RAID code maintain the necessary RAID relationship at all times; and 
 providing an optimizer for optimizing I/O plans for available hardware resources; 
 wherein the RAID engine automatically optimizes individual read, individual write, and XOR operations necessary to complete the read, write, rebuild, scrub, and migrate operations. 
   
   
   
       2 - 20 . (canceled)