Optimization of storage device accesses in RAID systems

• US 7,917,831 B2
• Filed: 06/14/2007
• Issued: 03/29/2011
• Est. Priority Date: 06/14/2007
• Status: Expired due to Fees

• Current Assignee: SRI International, Inc.
• Original Assignee: Freescale Semiconductor, Inc. (NXP Semiconductors NV)
• Inventors: Millman, Steven D., Torla, Michael J.
• Primary Examiner(s): RIZK, SAMIR WADIE
• Application Number:
  US11/763,107
• Publication Number:
  US 20080313397A1
• Time in Patent Office: 1,384 Days
• Field of Search: 714/763, 711111-114
• US Class Current: 714/763
• 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/1064 Parity-single bit-RAID3, i.e. RAID 3 implementations

Abstract

A result value, such as a parity value, for a set of corresponding data elements from a plurality of storage devices is determined using a commutative operation. When accessing the set of corresponding data elements from a plurality of storage devices, a dual access can be performed for the storage device accessed last for the set of corresponding data elements so as to also obtain a data element from the last-accessed storage device for the next parity calculation. As a result, the number of storage device accesses can be reduced compared to conventional systems whereby a single access is performed for each storage device to obtain a single data element from the storage device.

Claims

1. In a data storage system comprising N storage devices, a method comprising:

performing a single access to each storage device of a first sequence of storage devices to obtain a data element from each storage device of the first sequence, the first sequence advancing from a first storage device to an N−

1th storage device, and the data elements from the storage devices of the first sequence forming a first subset of N−

1 data elements;

performing a first dual access to an Nth storage device of the N storage devices to obtain a first data element and a second data element, the first subset of N−

1 data elements and the first data element forming a first set of N data elements;

performing a first commutative operation using each data element of the first set of N data elements to generate a first result data; and

storing the first result data.

2. The method of claim 1, further comprising:

performing a single access to each storage device of a second sequence of storage devices to obtain a data element from each storage device of the second sequence, the second sequence advancing from the N−

1th storage device to a second storage device, and the data elements from the storage devices of the second sequence forming a second subset of N−

2 data elements;

performing a second dual access to the first storage device to obtain a third data element and a fourth data element, the second data element, the third data element, and the second subset of N−

2 data elements forming a second set of N data elements;

performing a second commutative operation using each data element of the second set of N data elements to generate a second result data; and

storing the second result data.

3. The method of claim 2, further comprising:

correcting an erroneous data element of the first set of N data elements using the first result data.

4. The method of claim 2, wherein:

the first commutative operation comprises an XOR operation; and

the second commutative operation comprises an XOR operation.

5. The method of claim 1, further comprising:

performing a single access to each storage device of a second sequence of storage devices to obtain a data element from each storage device of the second sequence, the second sequence advancing from the N−

1th storage device to the first storage device, and the data elements from the storage devices of the second sequence forming a second subset of N−

1 data elements;

performing a second commutative operation using each data element of the second set of N data elements to generate a second result data; and

storing the second result data.

6. The method of claim 5, further comprising:

correcting an erroneous data element of the first set of N data elements using the first result data.

7. The method of claim 5, wherein:

the first commutative operation comprises an XOR operation; and

the second commutative operation comprises an XOR operation.

8. The method of claim 1, wherein storing the first result data comprises storing the first result data at a register.

9. The method of claim 1, wherein storing the first result data comprises storing the first result data as a parity data at a storage location of one of the plurality of storage devices, the parity data corresponding to the first data element and the second data element.

10. The method of claim 1, further comprising:

correcting an erroneous data element of the first set of N data elements using the first result data.

11. The method of claim 1, wherein the first commutative operation comprises an XOR operation.

12. A method comprising:

performing a first access operation to a first storage device of a plurality of storage devices to obtain a first data element from the first storage device;

storing the first data element at a first-in first-out (FIFO) buffer;

performing a second access operation to a second storage device of the plurality of storage devices to obtain a second data element and third data element from the second storage device, the second access operation performed subsequent to the first access operation;

storing the second data element at the FIFO buffer subsequent the first data element;

storing the third data element at the FIFO buffer subsequent to the second data element;

performing a third access operation to the first storage device to obtain a fourth data element and a fifth data element from the storage device, the third access operation performed subsequent to the second access operation;

storing the fourth data element at the FIFO buffer subsequent to the third data element;

storing the fifth data element at the FIFO buffer subsequent to the fourth data element;

obtaining the first data element and the second data element from the FIFO buffer;

performing a first commutative operation using the first data element and second data element to generate a first result data;

storing the first result data;

obtaining the third data element and the fourth data element from the FIFO buffer subsequent to obtaining the first data element and the second data element from the FIFO buffer;

performing a second commutative operation using the third data element and the fourth data element to generate a second result data; and

storing the second result data.

13. The method of claim 12, further comprising:

performing a fourth access operation to the second storage device to obtain a sixth data element from the third storage device;

storing the sixth data element in the FIFO buffer subsequent to the fifth data element;

obtaining the fifth data element and the sixth data element from the FIFO buffer subsequent to obtaining the third data element and the fourth data element from the FIFO buffer;

performing a third commutative operation using the fifth data element and the sixth data element to generate a third result data; and

storing the third result data.

14. The method of claim 12, further comprising:

performing a fourth access operation to a third storage device of the plurality of storage devices to obtain a sixth data element from the third storage device;

storing the sixth data element in the FIFO buffer subsequent to the first data element and prior to the second data element;

performing a fifth access operation to the third storage device to obtain a seventh data element from the third storage device;

storing the seventh data element in the FIFO buffer subsequent to the third data element and prior to the fourth data element;

obtaining the sixth data element from the FIFO buffer subsequent to the first data element and prior to the second data element;

obtaining the seventh data element from the FIFO buffer subsequent to the third data element and prior to the fourth data element;

wherein performing the first commutative operation comprises performing the first commutative operation using the first data element, the second data element, and the sixth data element to generate the first result data; and

wherein performing the second commutative operation comprises performing the second commutative operation using the third data element, the fourth data element, and the seventh data element to generate the second result data.

15. The method of claim 14, further comprising:

performing a sixth access operation to the third storage device to obtain an eighth data element from the third storage device;

storing the eighth data element in the FIFO buffer subsequent to the fifth data element;

performing a seventh access operation to the second storage device to obtain a ninth data element and a tenth data element from the second storage device;

storing the ninth data element in the FIFO buffer subsequent to the eighth data element;

storing the tenth data element in the FIFO buffer subsequent to the ninth data element;

obtaining the eighth data element and the ninth data element from the FIFO buffer subsequent to the fifth data element;

performing a third commutative operation using the fifth data element, the eighth data element, and the ninth data element to generate a third result data; and

storing the third result data.

16. A system comprising:

a controller coupleable to a plurality of storage devices, the controller comprising;

a first-in first-out (FIFO) buffer configured to buffer data elements;

an access interface configured to initiate a first access operation to a first storage device of a plurality of storage devices to obtain a first data element from the first storage device for storage in the FIFO buffer and initiate a second access operation to a second storage device of the plurality of storage devices to obtain a second data element and a third data element from the second storage device for storage in the FIFO buffer subsequent to the first data element; and

a commutative operation component coupled to the FIFO buffer and configured to perform a first commutative operation using the first data element and the second data element obtained from the FIFO buffer to generate a first result data.

17. The system of claim 16, wherein:

the access interface is configured to initiate a third access operation to the first storage device to obtain a fourth data element from the first storage device for storage in the FIFO buffer subsequent to the third data element; and

the commutative operation component is configured to perform a second commutative operation using the third data element and the fourth data element obtained from the FIFO buffer to generate a second result data.

18. The system of claim 16, further comprising:

the plurality of storage devices.

19. The system of claim 18, wherein each of the plurality of storage devices comprises a storage device selected from a group consisting of:

a magnetic disk device;

an optical disk device;

a dynamic random access memory device;

a static random access memory device; and

a flash memory device.

20. The system of claim 16, further comprising:

a correction component to correct an erroneous data element of a storage device of the plurality of storage devices based on the first result data.