Redundant Data Update in S

RedundantData RegenerationRegeneratenewredundantblocksbyallthedatablocksData blocksaredistributed amongnodesSend all the data blocks to redundancy nodeComputethenewredundantblocksinredundancy node·Overhead istoo highDataNodesRedundancyNode

Redundant Data Regeneration Regenerate new redundant blocks by all the data blocks ⚫ Data blocks are distributed among nodes ⚫ Send all the data blocks to redundancy node ⚫ Compute the new redundant blocks in redundancy node ⚫ Overhead is too high Redundancy Node Data Nodes

Redundant Data Regeneration·Datablocksare stored in central archiveserver.Regenerate all the new redundant data in server.Send to redundancy nodes.Servermaybecostly,notdesirable,notfeasibleServerRedundancyNode

Redundant Data Regeneration ⚫ Data blocks are stored in central archive server ⚫ Regenerate all the new redundant data in server ⚫ Send to redundancy nodes ⚫ Server may be costly, not desirable, not feasible Redundancy Node Server

Seguential Redundant Data UpdateldeaOldredundantdata blocks containvaluableinformation onthe data blocksData blocks are different after reorganizationButsomeblocksinparitygroupistheSAMEPossibletoreuseforlinear codedodid2d3roriOldRedundantdatablocksV2V3Co,oCo,1dodidzd3d4roIiNewRedundantdatablocksV20.0C0.1V3VA

Sequential Redundant Data Update Idea ⚫ Old redundant data blocks contain valuable information on the data blocks ⚫ Data blocks are different after reorganization ⚫ But some blocks in parity group is the SAME ⚫ Possible to reuse for linear code v0 v1 v2 v3 c’0,0 c’ v4 0,1 New Redundant data blocks v0 v1 v2 v3 c0,0 c0,1 Old Redundant data blocks d0 d1 d2 d3 d4 r0 r1 d0 d1 d2 d3 r0 r1

Sequential Redundant Data UpdateLinearerasurecorrectioncodeCanbeanalyzed using linearalgebraLinear matrix multiplications in computing redundant dataReed-Solomon ErasureCorrectionCodeRedundant data byVandermondematrixNumberofnodes,NDatafromdataNumberofredundancynode,hnode0.Elementat rowi,columnj=ji-1Redundantdatad11Cioinredundancy%23N-hnode0CV·.:2h-13h-1... (N-h)h-I Ld,N-h-1,Ci.h-1

Sequential Redundant Data Update Linear erasure correction code ⚫ Can be analyzed using linear algebra ⚫ Linear matrix multiplications in computing redundant data Reed-Solomon Erasure Correction Code ⚫ Redundant data by Vandermonde matrix ⚫ Number of nodes, N ⚫ Number of redundancy node, h ⚫ Element at row i, column j = j i-1 Data from data node 0 Redundant data in redundancy node 0 ,0 ,0 ,1 ,1 1 1 1 , 1 , 1 1 1 1 1 1 2 3 1 2 3 ( ) i i i i h h h i h i N h c d c d N h c d N h − − − − − −             −     =                     −    