A method of data recovery for a distributed storage system having totally n storage nodes, the system codes 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 umber of virtual nodes, k indicates that data is equally divided into k segments, each segment contains α 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;
- wherein the method comprises following steps:
- Step 1:
- selecting assistant nodes from surviving nodes, calculating helper data sub-blocks by using the assistant nodes, and sending the helper data sub-blocks to a regenerating node;
- letting {Ni|1≤i≤n′} denote a set of both virtual nodes and real nodes, where N1˜Nδ are virtual nodes and Nδ+1˜Nn′ are real nodes, number of the surviving nodes is n′−t, t is number of failed nodes 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:
- 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 a 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)}xi′, 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:
- reconstructing missing data blocks:
- 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.