Back-annotation in storage-device array
View Patent ↗In one embodiment, a method for reading data from a storage-device array including three or more storage devices. The array has a plurality of sector levels, each sector level containing one sector on each storage device in the array at corresponding addresses across the storage devices. Each sector level includes (i) parity data stored on a first storage device and (ii) information stored on the two or more remaining storage devices. The parity data for a current sector level is generated from the information stored at the current sector level on the remaining storage devices. The method includes: (a) generating an instruction for reading (i) the parity data from the first storage device at the current sector level and (ii) the information from the remaining storage devices at the current sector level; (b) receiving an indicator indicating whether one of the remaining storage devices is a degraded storage device; (c) if the indicator does not indicate a degraded storage device, then providing as output the information read from the remaining storage devices at the current sector level; and (d) if the indicator does indicate a degraded storage device, then: (d1) reconstructing information previously stored on the degraded storage device at the current sector level based on (i) the parity data read from the first storage device at the current sector level, and (ii) the information read from each remaining non-degraded storage device at the current sector level; and (d2) providing as output (i) the information read from the one or more non-degraded storage devices at the current sector level and (ii) the reconstructed information.
1. A method for reading data from a storage-device array comprising three or more storage devices, wherein:
the array has a plurality of sector levels, each sector level containing one sector on each storage device in the array at corresponding addresses across the storage devices;
each sector level includes (i) parity data stored on a first storage device and (ii) information stored on the two or more remaining storage devices;
the parity data for a current sector level is generated from the information stored at the current sector level on the remaining storage devices; and
at least first and second profiles concurrently define two or more virtual arrays associated with at least a common subset of one or more of the storage devices, each profile defining (i) a different virtual array associated with a corresponding set of storage devices and (ii) a parameter set of one or more parameters used for accessing the virtual array,
the method comprising:
(a) generating an instruction for reading (i) the parity data from the first storage device at the current sector level and (ii) the information from the remaining storage devices at the current sector level;
(b) receiving an indicator as a parameter from the first profile indicating whether one of the remaining storage devices is a degraded storage device;
(c) if the indicator does not indicate a degraded storage device, then providing as output the information read from the remaining storage devices at the current sector level; and
(d) if the indicator does indicate a degraded storage device, then:
(d1) reconstructing information previously stored on the degraded storage device at the current sector level based on (i) the parity data read from the first storage device at the current sector level, and (ii) the information read from each remaining non-degraded storage device at the current sector level;
(d2) providing as output (i) the information read from the one or more non-degraded storage devices at the current sector level and (ii) the reconstructed information; and
(d3) storing another indicator indicating the degraded storage device as a parameter in the second profile associated with the degraded storage device.
2. The invention of claim 1 , wherein the information stored at the current sector level corresponds to a portion of a data object, and further comprising repeating steps (a) through (d) for one or more other sector levels on which remaining portions of the data object are stored.
3. The invention of claim 2 , wherein the data object is a streaming media object.
4. The invention of claim 1 , wherein the reconstructed information is generated at a resolution of a single sector level.
5. The invention of claim 4 , wherein the reconstructed information is generated by:
storing, in a buffer, one of: (i) the parity data read from the first storage device at the current sector level, and (ii) the information read from the remaining non-degraded storage devices at the current sector level; and
sequentially combining the information in the buffer with the others of: (i) the parity data read from the first storage device at the current sector level, and (ii) the information read from the remaining non-degraded storage devices at the current sector level, to update the information in the buffer, such that the information in the buffer, after (i) the parity data read from the first storage device at the current sector level, and (ii) the information read from the remaining non-degraded storage devices at the current sector level have been processed, is the parity data.
6. The invention of claim 1 , wherein the addresses are logical-block addresses.
7. The invention of claim 1 , wherein the method is implemented at a resolution of a single sector level.
8. The invention of claim 1 , wherein the method is implemented during a normal read operation, without taking any of the storage devices offline.
9. The invention of claim 1 , wherein:
the storage-device array has a plurality of stripes, each stripe having two or more sector levels; and
the method further comprises:
(e) calculating a parity index based on (i) an index value for a current stripe and (ii) the number of storage devices in the array, the parity index identifying a first storage device for parity data for the current stripe; and
(f) at each sector level of the current stripe:
(f1) writing parity data to the first storage device identified by the parity index; and
(f2) writing information to the remaining storage devices.
10. The invention of claim 9 , wherein the storage devices use a buffer having a first portion and a second portion, and the method further comprises:
(g) generating two or more successive pairs of instructions, wherein:
the first instruction of each pair of instructions (i) is based on one or more parameters of the first profile and (ii) is an instruction to read, into the first portion of the buffer, one sector of data from each storage device of a first virtual array; and
the second instruction of each pair of instructions (i) is based on one or more parameters of the second profile and (ii) is an instruction to read, into the second portion of the buffer, one sector of data from each storage device of a second virtual array.
11. The invention of claim 1 , wherein:
the storage-device array has a plurality of stripes, each stripe having two or more sector levels, and the method further comprises:
(e) calculating a parity index based on (i) an index value for a current stripe and (ii) the number of storage devices in the array, the parity index identifying a first storage device for parity data for the current stripe; and
(f) at each sector level of the current stripe:
(f1) reading parity data from the first storage device identified by the parity index; and
(f2) reading information from the remaining storage devices.
12. The invention of claim 11 , wherein the storage devices use a buffer having a first portion and a second portion, and the method further comprises:
(g) generating two or more successive pairs of instructions, wherein:
the first instruction of each pair of instructions (i) is based on one or more parameters of the first profile and (ii) is an instruction to read, into the first portion of the buffer, one sector of data from each storage device of a first virtual array; and
the second instruction of each pair of instructions (i) is based on one or more parameters of the second profile and (ii) is an instruction to read, into the second portion of the buffer, one sector of data from each storage device of a second virtual array.
13. The invention of claim 1 , wherein the storage devices use a buffer having a first portion and a second portion, and the method further comprises:
(e) generating two or more successive pairs of instructions, wherein:
the first instruction of each pair of instructions (i) is based on one or more parameters of a first profile and (ii) is an instruction to read, into the first portion of the buffer, one sector of data from each storage device of a first virtual array; and
the second instruction of each pair of instructions (i) is based on one or more parameters of a second profile and (ii) is an instruction to read, into the second portion of the buffer, one sector of data from each storage device of a second virtual array.
14. Apparatus for reading data from a storage-device array comprising three or more storage devices, wherein:
the array has a plurality of sector levels, each sector level containing one sector on each storage device in the array at corresponding addresses across the storage devices;
each sector level includes (i) parity data stored on a first storage device and (ii) information stored on the two or more remaining storage devices;
the parity data for a current sector level is generated from the information stored at the current sector level on the remaining storage devices; and
at least first and second profiles concurrently define two or more virtual arrays associated with at least a common subset of one or more of the storage devices, each profile defining (i) a different virtual array associated with a corresponding set of storage devices and (ii) a parameter set of one or more parameters used for accessing the virtual array,
the apparatus adapted to:
(a) generate an instruction for reading (i) the parity data from the first storage device at the current sector level and (ii) the information from the remaining storage devices at the current sector level;
(b) receive an indicator as a parameter from the first profile indicating whether one of the remaining storage devices is a degraded storage device;
(c) if the indicator does not indicate a degraded storage device, then provide as output the information read from the remaining storage devices at the current sector level; and
(d) if the indicator does indicate a degraded storage device, then:
(d1) reconstruct information previously stored on the degraded storage device at the current sector level based on (i) the parity data read from the first storage device at the current sector level, and (ii) the information read from each remaining non-degraded storage device at the current sector level;
(d2) provide as output (i) the information read from the one or more non-degraded storage devices at the current sector level and (ii) the reconstructed information; and
(d3) store another indicator indicating the degraded storage device as a parameter in the second profile associated with the degraded storage device.
15. The invention of claim 14 , wherein the apparatus is embodied in an integrated circuit.
16. A computer system comprising:
a computer having a processor and an interface;
a physical storage-device array having a plurality of sector levels, each sector level containing one sector on each storage device in the array at corresponding addresses across the storage devices; wherein:
each sector level includes (i) parity data stored on a first storage device and (ii) information stored on the two or more remaining storage devices;
the parity data for a current sector level is generated from the information stored at the current sector level on the remaining storage devices; and
at least first and second profiles concurrently define two or more virtual arrays associated with at least a common subset of one or more of the storage devices, each profile defining (i) a different virtual array associated with a corresponding set of storage devices and (ii) a parameter set of one or more parameters used for accessing the virtual array; and
a storage system coupled to the computer via the interface and adapted to access the physical storage-device array, the storage system adapted to:
(a) generate an instruction for reading (i) the parity data from the first storage device at the current sector level and (ii) the information from the remaining storage devices at the current sector level;
(b) receive an indicator as a parameter from the first profile indicating whether one of the remaining storage devices is a degraded storage device;
(c) if the indicator does not indicate a degraded storage device, then provide as output the information read from the remaining storage devices at the current sector level; and
(d) if the indicator does indicate a degraded storage device, then:
(d1) reconstruct information previously stored on the degraded storage device at the current sector level based on (i) the parity data read from the first storage device at the current sector level, and (ii) the information read from each remaining non-degraded storage device at the current sector level;
(d2) provide as output (i) the information read from the one or more non-degraded storage devices at the current sector level and (ii) the reconstructed information; and
(d3) storing another indicator indicating the degraded storage device as a parameter in the second profile associated with the degraded storage device.
17. A method for reading data from a storage-device array comprising three or more storage devices, wherein:
the array has a plurality of sector levels, each sector level containing one sector on each storage device in the array at corresponding addresses across the storage devices;
each sector level includes (i) parity data stored on a first storage device and (ii) information stored on the two or more remaining storage devices; and
the parity data for a current sector level is generated from the information stored at the current sector level on the remaining storage devices,
the method comprising:
(a) generating an instruction for reading (i) the parity data from the first storage device at the current sector level and (ii) the information from the remaining storage devices at the current sector level;
(b) receiving an indicator indicating whether one of the remaining storage devices is a degraded storage device;
(c) if the indicator does not indicate a degraded storage device, then providing as output the information read from the remaining storage devices at the current sector level; and
(d) if the indicator does indicate a degraded storage device, then:
(d1) reconstructing information previously stored on the degraded storage device at the current sector level based on (i) the parity data read from the first storage device at the current sector level, and (ii) the information read from each remaining non-degraded storage device at the current sector level; and
(d2) providing as output (i) the information read from the one or more non-degraded storage devices at the current sector level and (ii) the reconstructed information;
wherein the storage devices use a buffer having a first portion and a second portion, and the method further comprises:
(e) accessing first and second profiles, each profile defining (i) a virtual array associated with a selected set of the storage devices and (ii) one or more parameters used for accessing information from the virtual array;
(f) generating two or more successive pairs of instructions, wherein:
the first instruction of each pair of instructions (i) is based on one or more parameters of a first profile and (ii) is an instruction to read, into the first portion of the buffer, one sector of data from each storage device of a first virtual array; and
the second instruction of each pair of instructions (i) is based on one or more parameters of a second profile and (ii) is an instruction to read, into the second portion of the buffer, one sector of data from each storage device of a second virtual array.
18. The invention of claim 17 , wherein:
the storage-device array has a plurality of stripes, each stripe having two or more sector levels; and
the method further comprises:
(g) calculating a parity index based on (i) an index value for a current stripe and (ii) the number of storage devices in the array, the parity index identifying a first storage device for parity data for the current stripe; and
(h) at each sector level of the current stripe:
(h1) writing parity data to the first storage device identified by the parity index; and
(h2) writing information to the remaining storage devices.
19. The invention of claim 17 , wherein:
the storage-device array has a plurality of stripes, each stripe having two or more sector levels; and
the method further comprises:
(g) calculating a parity index based on (i) an index value for a current stripe and (ii) the number of storage devices in the array, the parity index identifying a first storage device for parity data for the current stripe; and
(h) at each sector level of the current stripe:
(h1) reading parity data from the first storage device identified by the parity index; and
(h2) reading information from the remaining storage devices.