Triple failure tolerant storage systems using only exclusive-or parity calculations

Abstract—We present a disk array organization that can sur-vive three simultaneous disk failures while only using exclusive-or operations to calculate the parities that generate this failure tolerance. The reliability of storage systems using magnetic disks depends on how prone individual disks are to failure. Unfortunately, disk failure rates are impossible to predict and it is well known that individual batches might be subject to much higher failure rates at some point during their lifetime. It is also known that many disk drive families, but not all, suffer a substantially higher failure rate at the beginning and some at the end of their economic lifespan. Our proposed organization can be built on top of a dense two-failure tolerant layout using only exclusive-or operations and with a ratio of parity to data disks of 2/k. If the disk failure rates are higher than expected, the new organization can be super-imposed on the existing two-failure tolerant organization by introducing (k+ 1)/2 new parity disks and (k+ 1)/2 new reliability stripes to yield a three-failure tolerant layout without moving any data or calculating any other parity but the new one. We derive the organization using a graph visualization and a construction by Lawless of factoring a complete graph into paths. I