Transformational raid for hierarchical storage management system
First Claim
1. A method for converting a first memory structure stored on a plurality of data storage devices to a second memory structure stored on said plurality of data storage devices, the method comprising the steps of:
- (a) identifying a set of blocks of data to be converted, each block of said set being stored on a different respective one of said plurality of data storage devices, said set comprising a plurality of pairs of blocks, both blocks of each respective pair containing identical data;
(b) selecting a first block of said set;
(c) designating the first block as a parity block without altering data contained in said first block;
(d) selecting a respective block from each pair of blocks of said set which does not include said first block; and
(e) designating each respective block selected from each pair of blocks of said set which does not include said first block as available for storage of replacement data.
1 Assignment
0 Petitions
Accused Products
Abstract
A flexible array of storage devices stores a plurality of blocks divided into sets of blocks called stripes, each block of a stripe being stored on a different device. An array controller supports formatting of the stripes independently in accordance with different memory structures. Specifically, the memory structures supported in the preferred embodiment are non-redundant, mirrored, and parity protected. Each block of storage exists in one of five states: (1) EMPTY; (2) DATA; (3) PARITY; (4) COPY; or (5) FREE. Each stripe of storage blocks exists within one of seven states which depend upon the states of the blocks. Certain slate transitions are defined, permitting stripes of one type to be converted to stripes of another type while minimizing the movement of data. Specifically, a stripe in a fully mirrored state is transformed to a parity protected state by designating any one block within the mirrored stripe as a PARITY block, and changing certain status information. No movement of data is necessary in this case. It is also possible to transform a non-redundant or parity protected stripe into a mirrored stripe.
189 Citations
27 Claims
-
1. A method for converting a first memory structure stored on a plurality of data storage devices to a second memory structure stored on said plurality of data storage devices, the method comprising the steps of:
-
(a) identifying a set of blocks of data to be converted, each block of said set being stored on a different respective one of said plurality of data storage devices, said set comprising a plurality of pairs of blocks, both blocks of each respective pair containing identical data; (b) selecting a first block of said set; (c) designating the first block as a parity block without altering data contained in said first block; (d) selecting a respective block from each pair of blocks of said set which does not include said first block; and (e) designating each respective block selected from each pair of blocks of said set which does not include said first block as available for storage of replacement data. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A data storage system, comprising:
-
a plurality of data storage devices; a programmable processor for controlling the operation of said plurality of data storage devices, said programmable processor executing a control program for converting a first memory structure stored on said plurality of storage devices to a second memory structure stored on said plurality of storage devices; wherein said control program maintains status information for said data storage system; and wherein said control program, in response to identification of a set of blocks of data to be converted, each block of said set to be converted being stored on a different respective one of said plurality of data storage devices, said set comprising a plurality of pairs of blocks, both blocks of each respective pair containing identical data, (a) updates said status information to designate a first block of said set of blocks as a parity block, without altering data contained in said first block, and (b) updates said status information to designate a respective block from each pair of blocks of said set which does not include said first block as available for storage of replacement data. - View Dependent Claims (9, 10, 11, 12, 13, 14, 15)
-
-
16. A controller for controlling a data storage system, said data storage system having a plurality of data storage devices for storing data, said controller comprising:
-
a programmable processor for controlling the operation of said plurality of data storage devices, said programmable processor executing a control program for converting a first memory structure stored on said plurality of storage devices to a second memory structure stored on said plurality of storage devices; and a random access memory for containing status information maintained by said control program; wherein said control program, in response to identification of a set of blocks of data to be converted, each block of said set to be converted being stored on a different respective one of said plurality of data storage devices, said set comprising a plurality of pairs of blocks, both blocks of each respective pair containing identical data, (a) updates said status information to designate a first block of said set of blocks as a parity block, without altering data contained in said first block, and (b) updates said status information to designate a respective block from each pair of blocks of said set which does not include said first block as available for storage of replacement data. - View Dependent Claims (17, 18, 19)
-
-
20. A program storage device readable by a digital processing apparatus and tangibly embodying a control program of instructions executable by the digital processing apparatus for controlling a data storage system, said data storage system having a plurality of data storage devices for storing data, said program performing method steps for converting a first memory structure into a second memory structure, the method steps comprising:
-
(a) receiving the identification of a set of blocks of data to be converted from said first memory structure to said second memory structure, each block of said set to be converted being stored on a different respective one of said plurality of data storage devices, said set comprising a plurality of pairs of blocks, both blocks of each respective pair containing identical data; (b) updating status information to designate a first block of said set of blocks as a parity block without altering data contained in said first block; and (c) updating said status information to designate a respective block from each pair of blocks of said set which does not include said first block as available for storage of replacement data. - View Dependent Claims (21, 22)
-
-
23. A method for converting a first memory structure stored on a plurality of data storage devices to a second memory structure stored on said plurality of data storage devices, the method comprising the steps of:
-
(a) identifying a set of blocks of data to be converted, each block of said set being stored on a different respective one of said plurality of data storage devices, said set comprising a plurality of blocks containing data and a block containing parity derived from said plurality of blocks containing data; (b) selecting said block containing parity to contain a copy of data contained in a first of said plurality of blocks containing data, without altering data contained in said first block; (c) selecting a first subset of said set of blocks of data, said first subset having at least one block of data other than said parity block, to contain a copy of data contained in a second subset of said set of blocks of data, said second subset having at least one block of data other than said first of said plurality of blocks containing data, without altering data contained in said second subset; (d) copying data contained in said first of said plurality of blocks to said block containing parity; and (e) copying data contained in each block of said second subset to a respective block of said first subset.
-
-
24. A data storage system, comprising:
-
a plurality of data storage devices; a programmable processor for controlling the operation of said plurality of data storage devices, said programmable processor executing a control program for controlling the operation of said data storage system; wherein data in said plurality of data storage devices is organized into a plurality of sets of blocks, each block of a set being stored on a different respective one of said plurality of data storage devices; wherein said control program supports formatting of said sets of blocks according to a plurality of different memory structures, at least one of said memory structures being a redundant data format, a first set of blocks and a second set of blocks being formattable independently of each other; and a random access memory for storing status information maintained by said control program, said status information including a respective block status for each block and a separate respective set status for said first set of blocks and said second set of blocks, said set status information including identification of the memory structure according to which each respective set of blocks is configured; wherein said control program, in response to identification of a set of blocks of data to be converted from a first memory structure to a second memory structure, at least one of said blocks containing data to be stored in said second memory structure, (a) updates block status information for the blocks of said set of blocks to be converted without altering said data to be stored in said second memory structure, and (b) updates set status information for said set of blocks to identify the set as configured according to the second memory structure. - View Dependent Claims (25, 26, 27)
-
Specification