Fault Tolerance of TornadoCodes for Archival StorageHPDC 15 21 June 2006Matthew [email protected] June 20062Key Points Tornado Codes can provide fault tolerant storage Single site applications: better than RAID Distributed applications: better than replication Verify then trust  Tornado codes can work with existing Data Grids Low computational overhead  Behind-the-scenes server-side fault tolerance No reason to alter interfaces, use existing Data Grid tools21 June 20063Outline Background and Motivation Experimental Method and Results Applications to Distributed and Federated Storage Conclusions and Future Work21 June 20064Storage for High Performance ComputingArchival StorageTape silo systemsWorking StorageDisk systemsGrid Front EndGridFTP ServersArchive ManagementCollaborative StorageMassive disk or tape arraysShared using Grid technologyDistributed data stewardingENTERPRISE6 0 0 0ENTERPRISE6 0 0 0TMTMOrigin 320021 June 20065Motivation – Filesystem Features Typical desired features Performance (no waiting) Availability (no downtime) Reliability (no data loss) Inexpensive (no cost) Scalability (no limits) Apply Tornado Codes to distributed archival storageOptimize performance and resource utilization Leverage existing legacy technology Support emerging technologies and solutions (Grid, MAID)Prime directive: Never lose data21 June 20066LDPC Codes and Tornado CodesLow Density Parity Check codes Gallager, 1963 Luby, 1990s Cascaded irregular LDPC graphs are Tornado Codes Average degree of connectivity Distribution of degree Randomly generatedData Nodes Check Nodes Simple XOR operation has low computational overheadABCDEFGH21 June 20067Storage Applications – Safety and Speed Tornado Code advantages Fault tolerance Performance optimizationsRetrieve C or G? If one node is dead, the decision is easy!  If both nodes are available, choose the node with less waitingABGData Nodes Check NodesC21 June 20068Related Work Typhoon (Weatherspoon, 1999) – Performance Higher performance alternative to Reed-Solomon codingfor OceanStore’s archival storage class Simple algorithms for Tornado Code generation RobuSTore (Xia, 2006) – Hide latency LDPC codes and speculative access Hide latency from slow devices This work examines the risk of data loss in distributed filesystems using Tornado Codes21 June 20069Experimental Method Construct and evaluate a Tornado Coding schemepotential graphsdevice failure casessimulated failurebest graphs Initial worst case failure identification Extensive final graph profiling Bound “probabilistically successful” data reconstruction Combine with empirical device failure rates for reliability Final graphs used for filesystem implementation21 June 200610Evaluation Metrics Reconstruction Efficiency Overhead: average data retrieval required to reconstruct Example: 48 data and 48 check nodes Minimum: 48 data nodes Random: average of 62 nodes (1.29)Other authors: between 1.2 and 1.4 Fault Tolerance  First failure: How many nodes/devices can be lost?  Reliability: probability of failure over time Missing blocks may be… available but not retrieved – reconstruction efficiency permanently unavailable – fault tolerance21 June 200611Testing Tornado Codes Fault tolerance analysis of 96-node graphs Small enough to explicitly manage device state Large enough to take advantage of selective retrievals Storing files using Tornado Code graphs Per-file encoding Using a log-based filesystemFilesDataParityStripe}Object Storage21 June 200612First Experiences with Tornado Codes Tornado code graphs fail to reconstruct due to closed set of right nodes (subgraph identification)4851576662842684857172217 [48,57]22 [48,57]Left node [right nodes]Failure with 2 lost nodesFailure with 3 lost nodes6[48,51,57]28 [57,66,68]42 [48,51,66,68] Possible to correct by expanding sets  Example 96-node graph survives all 4-node failures and only 6 / 61,124,064 5-node cases fail21 June 200613Tornado Code Defect Detection ResultsMissing Nodes05 10 15 20 25 30 35 40 45Fraction Reconstruction Failure00.20.40.60.81Prototype Graph (without defect correction)Tornado Graph 3(before adjustment)Tornado Graph 3(after adjustment)5After4Before2PrototypeFirst FailureNever trust a randomly generated Tornado Code graph without testing first!21 June 200614Comparison Single-Site Disk Configurations Compared to familiar RAID systems All configurations have 96 devices RAID 5 RAID 6 Mirrored (RAID 10) Tornado Code graphs Results describe three specific Tornado Code graphs (“Tornado 1”, “Tornado 2”, “Tornado 3”)data paritydatadatadata parity21 June 20061596-Device Tornado Code Fault Tolerance2Mirrored5Tornado 15Tornado 33RAID62RAID5First FailureMissing Nodes05 10 15 20 25 30 35 40 45Fraction Reconstruction Failure00.20.40.60.81RAID5 (*)RAID6 (*)MirroredTornado 1Tornado 3 Tornado codes demonstrate much better fault tolerance than mirroring with the same capacity overhead21 June 200616Calculating Fault Tolerance The probability of any independent drive being lost is given by the binomial distribution:1.000E-192969.504E-189954.753E-08105.408E-0795.476E-0684.873E-0570.0003860.0024550.0131840.0561130.1772920.3695010.381050P( n offline )n offlineDevice AFR: p = 0.01P( n nodes offline )()( )⎟⎟⎠⎞⎜⎜⎝⎛−=−knppkPknk1)lost drives (∑==drives 0)lost drives ()lost drives |fail()fail(nkkPkPP Because the experimental results are independent conditional probabilities, they may be summed: This is a worst case fault tolerance calculation: it ignores all repairs21 June 200617Single Site Fault Tolerance5.857E-104848Tornado 35.947E-104848Tornado 21.345E-094848Tornado 10.004794848Mirrored0.001641680RAID60.04834888RAID50.61895096Striping0.01000Individual DiskP( fail )ParityDataMethod21 June 200618Distributed and Federated Storage Federated Storage Distributed sites maintain subsets or complete copies Replica selection and placement important Data locality (close to researchers) Data permanence (stewarding of historical data)Active Storage SiteDeep Storage Archival SiteActive Storage SiteHigh Throughput Wide-Area Network21 June 200619Multi-graph Federated Storage Federated Storage with Tornado Codes Each site uses a Tornado