A method of data recovery for a distributed storage system having totally n storage nodes each configured to store data, the system coding data to be stored with minimum storage regenerating code via product matrix construction C(n′,k′,d′),
- where n′=n+δ, k′=k+δ, d′=d+δ, δ denotes number of virtual nodes which are not real storage nodes, but theoretical storage nodes for computation, k indicates that data is equally divided into k segments, each segment contains a data sub-blocks, d is repair degree, C is resulted n′×α coded matrix and each entry thereof is data sub-block after encoded, first δ rows of C are zero, rows δ+1 to δ+k are source data and last m=n′−k′ rows are coded parity data, such that only n=n′−δ data blocks of resulted n′ coded data blocks are needed to be stored,
- the method comprising following steps:
- Step 1:
- selecting assistant nodes from surviving nodes, wherein the surviving nodes are non-failed storage nodes, and the assistant nodes are storage nodes, selected from the surviving nodes, which provide helper data for data recovery, calculating helper data sub-blocks by using the assistant nodes, and sending the helper data sub-blocks to a regenerating node which is a storage node for reconstructing missing data of multiple failed storage nodes;
- letting {Ni|1≤i≤n′} denote a set of both virtual nodes and real nodes, the real nodes being real storage nodes, where N1˜N6 are virtual nodes and Nδ+1˜Nn′ are real nodes, number of the surviving nodes is n′−t, t is number of failed nodes which are the storage nodes missing the data and t≥1, defining X={xi|i=1, . . . ,t, δ<xi≤n′} as a loss list, letting cx1, cx2, . . . , cxi denote missing data blocks, selecting d′−t+1 surviving nodes as assistant nodes, a set of the assistant nodes being denoted by Na={Nai|1≤i≤d′−t+1,1≤ai≤n′,ai∈X}, both the assistant nodes and the failed nodes being referred to as “evolved nodes” represented by Ne={Nj|Nj ∈Na or j∈X},
- the assistant nodes Nj∈Na each first calculating inner products between its stored data block cj and {ϕxi|i=1, . . . , t}, resulting in t helper data sub-blocks:
- {hxi,j=cjϕxit|i=1, . . . ,t}, then sending the helper data sub-blocks as helper data to the regenerating node,
- Step 2:
- the regenerating node calculating a repair matrix RX:
- (1) for each xi, xj∈X, j≠i, calculating a matrix according to following formula:
- Ωi,j=−θxi,fjiϕxi,
- where θxi,fji=ψxi,fji−1+λxiψxi,fji−1, ψxi,fji−1 is a vector consisting of upper α entries of ψxi,fji−1, and ψxi,fji−1 is lower α entries of ψxi,fji−1, here ψxi,fji−1 denotes columns of matrix Ψxi−1 that correspond to the helper data sub-blocks hxi,xj=cxjϕxit, Ψxi−1 is an inverse matrix of Ψxi=[ψjt|Nj∈Ne,j≠xi]t,
- (2) letting Xi=X|xi to be an ordered set of remaining indices of the loss list X without xi, and Gi={gji|j≠i} to be an ordered set of indices of columns in Ψxi−1 that correspond to data blocks {cxj|xj∈Xi}, for each i=1˜t:
- Θi=[θxi,m|1≤m≤d′,m∉Gi]
- where computation of θxi,m is identical to that of θxifji, m=n−k,
- according to aforesaid computing process, there being
- [
- I
- Ω
- 1
- ,
- 2
- ⋯
- Ω
- 1
- ,
- t
- Ω
- 2
- ,
- 1
- I
- ⋯
- Ω
- 2
- ,
- t
- ⋮
- ⋯
- ⋱
- ⋮
- Ω
- t
- ,
- 1
- Ω
- t
- ,
- 2
- ⋯
- I
- ]
- [
- c
- x
- 1
- c
- x
- 2
- ⋮
- c
- x
- t
- ]
- =
- [
- Θ
- 1
-
- h
- →
- x
- 1
- Θ
- 2
-
- h
- →
- x
- 2
- ⋮
- Θ
- t
-
- h
- →
- x
- t
- ]
- where {right arrow over (h)}xi=[hxi,j=cjϕxit|j∈Na]t,
- (3) for each xi, size of vector {right arrow over (h)}xi is d′−t+1, actually first δ entries of {right arrow over (h)}xi being all zero, accordingly first δ columns of each Θi being not useful at all, thereby replacing Θi{right arrow over (h)}xi with Θ′i{right arrow over (h)}′hxi, where Θ′i is Θi without first δ columns and {right arrow over (h)}′xi is {right arrow over (h)}xi without first δ entries:
- letting
- Ξ
- X
- =
- [
- I
- Ω
- 1
- ,
- 2
- ⋯
- Ω
- 1
- ,
- t
- Ω
- 2
- ,
- 1
- I
- ⋯
- Ω
- 2
- ,
- t
- ⋮
- ⋯
- ⋱
- ⋮
- Ω
- t
- ,
- 1
- Ω
- t
- ,
- 2
- ⋯
- I
- ]
- then repair matrix being:
- R
- X
- =
- [
- I
- Ω
- 1
- ,
- 2
- ⋯
- Ω
- 1
- ,
- t
- Ω
- 2
- ,
- 1
- I
- ⋯
- Ω
- 2
- ,
- t
- ⋮
- ⋯
- ⋱
- ⋮
- Ω
- t
- ,
- 1
- Ω
- t
- ,
- 2
- ⋯
- I
- ]
- -
- 1
- [
- Θ
- 1
- ′
- Θ
- 2
- ′
- ⋱
- Θ
- t
- ′
- ]
- and
- Step 3:
- the regenerating node reconstructing missing data blocks for the multiple failed storage nodes:
- obtaining missing data blocks by left multiplying vector [{right arrow over (h)}′x1t, {right arrow over (h)}′x2t, . . . , {right arrow over (h)}′xtt]t composed of the helper data sub-blocks with repair matrix RX;
- and
- performing concurrent recovery of the multiple failed nodes by writing the reconstituted data blocks into new replacements for the failed nodes.