Browse Prior Art Database

Method and Means of Reducing OS Installation Time on a 3-drive RAID 5 Array

IP.com Disclosure Number: IPCOM000015943D
Original Publication Date: 2002-May-08
Included in the Prior Art Database: 2003-Jun-21
Document File: 2 page(s) / 47K

Publishing Venue

IBM

Abstract

BACKGROUND

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 56% of the total text.

Page 1 of 2

Method and Means of Reducing OS Installation Time on a 3-drive RAID 5 Array

BACKGROUND

In a RAID 5 array, one stripe unit per stripe is allocated to hold the parity for the stripe where the parity is equal to the XOR'd value of all the other stripe units in the stripe. A sample 5-drive RAID 5 array may look as follows:

Drive 1 Drive 2 Drive 3 Drive 4 Drive 5 Stripe 1 D1 D2 D3 D4 P1 Stripe 2 D5 D6 D7 P2 D8 Stripe 3 D9 D10 P3 D11 D12


.

.

.

Stripe N D4N-3 D4N-2 PN D4N-1 D4N

where Dx stands for data and Px stands for parity (e.g. P1 = D1 xor D2 xor D3 xor D4). When writing data to a RAID 5 array, both the data and corresponding parity must be updated. There are two possible algorithms to compute the new parity. Each is demonstrated below with the assumption that we're writing a new D1 from the above example.

Full Xor Algorithm: Pnew = D1new xor D2 xor D3 xor D4

Read-Modify-Write (RMW) Algorithm: Pnew = Pold xor D1old xor D1new

The RMW works based on the assumption that Pold = D1old xor D2 xor D3 xor D4. Therefore, Pnew = (D1old xor D2 xor D3 xor D4) xor D1old xor D1new. Any data xor'd with itself equals 0. Any data xor'd with 0 equals itself. Since, the xor operation is fully commutative and associative, Pnew = (D1old xor D1old) xor D2 xor D3 xor D4 xor D1new -> Pnew = 0 xor D2 xor D3 xor D4 xor D1new -> Pnew = D1new xor D2 xor D3 xor D4.

Synchronization is the process by which the RAID firmware ensures that the RMW algorithm assumption (Pold = D1old xor D2 xor D3 xor D4) is true. For each stripe in an array, it reads each stripe unit in a stripe and generates parity using the full xor algorithm.

No data can be written to a stripe using the RMW algorithm until the stripe has been synchronized. The full xor algorithm, however, is self-synchronizing and so faces no such restriction. The RMW algorithm cannot be fully replaced in RAID firmware with the full xor algorithm however due to performance. In many instances, the RMW algorithm requires fewer I/Os to do the same operation and is thus preferred. For example, in the 5-drive D1 write case above, the full xor algorithm requires 5 I/Os (read D2, read D3, read D4, write D1new, write Pnew). The RMW algorithm for the same case requires only 4 I/Os (read Pold, read D1old, write D1new, write Pnew). The performance discrepancy increases in favor of the RMW algorithm with single stripe unit writes in larger arrays. There are also cases where the full xor algorithm outperforms the RMW algorithm. In the 5-drive case, if we were writing D1new, D2new, D3new, and D4new, the RMW algorithm would require 10 I/Os (read D1old, read D2old, read D3old, read D4old, read Pold, write D1new, write D2new, write D3new, write D4new, write Pnew). The full xor algorithm would require...