A method of data concurrent recovery for a distributed storage system, the system using minimum storage generating code C(n, k, d) based on interference alignment to encode data needed to be stored,
- the data being equally divided into k segments and then encoded into n data blocks denoted by b1, b2, . . . , bn , each data block containing α sub-blocks, α=d−k+1, d representing repair degree, first k data blocks B=[b1, b2, . . . , bk]T representing systematical blocks, rest m=n−k data blocks vj C=[c1, c2, . . . , cm]T=[bk+1, bk+2, . . . , bn]T representing parity blocks, then C=GB , G representing encoding matrix, each sub encoding matrix being Gij=ūivjT+pjiI, Pji being entry of m×m matrix P, ūi and vj being sub-vectors of first α elements of ui and vj respectively, U=[u1, u2, . . . , um] and V=[v1, v2, . . . , vm] being m×m invertible matrices, wherein the method of data concurrent recovery comprises following steps:
- step 1:
- obtaining helper data sub-blocks from a assistant node:
- letting N={Ni|i=1, . . . , n} denote n storage nodes, t1 number of failed systematical nodes, t2 number of failed parity nodes, t=t1+t2 1 total number of fail nodes, N1, . . . , Nt1 and Nk+1, . . . , Nk+t2 the failed systematical nodes and parity nodes respectively, then selecting assistant nodes from surviving nodes,
- defining actual repaired nodes to constitute a list of nodes to be recovered, the list containing all or part of t1 failed systematical nodes and t2 failed parity nodes, for each missing systematical data block bi, each assistant node Nj encoding its own data block to be hj,i=bjvi, resulting in a vector {right arrow over (h)}i=[ht1+1,i, . . . , hk,i, hk+t2+1,i, . . . , hd+1,i]T form by helper data sub-block,
- for each missing parity block ci, each assistant node Nj encoding its own data block to be gj,i=bjūi, resulting in a vector {right arrow over (g)}i=[gt1+1,i, . . . , gk, i, gk+t2+1,i, . . . , gd+1,i]T form by helper data sub-block, and
- sending helper data sub-block to a regenerating node;
- step 2:
- setting a sub-repair matrix related to missing data blocks:
- a) setting a sub-repair matrix related to missing systematical data blocks:
- setting an α×(tΔ) matrix:
- Φ
- i
- =
- [
- p
- 11
-
- v
- _
- i
- T
- …
- p
- i
- -
- 1
- ,
- 1
-
- v
- _
- i
- T
- u
- _
- 1
- T
- +
- p
- i
-
-
- 1
-
- v
- _
- i
- T
- p
- i
- +
- 1
- ,
- 1
-
- v
- _
- i
- T
- …
- p
- t
- 1
- ,
- 1
-
- v
- _
- i
- T
- p
- 12
-
- v
- _
- i
- T
- …
- p
- i
- -
- 1
- ,
- 2
-
- v
- _
- i
- T
- u
- _
- 2
- T
- +
- p
- i
-
-
- 2
-
- v
- _
- i
- T
- p
- i
- +
- 1
- ,
- 2
-
- v
- _
- i
- T
- …
- p
- t
- 1
- ,
- 2
-
- v
- _
- i
- T
- ⋮
- ⋱
- ⋮
- ⋮
- ⋮
- ⋱
- ⋮
- p
- 1
-
- α
-
- v
- _
- i
- T
- …
- p
- i
- -
- 1
- ,
- α
-
- v
- _
- i
- T
- u
- _
- α
- T
- +
- p
- i
-
-
- α
-
- v
- _
- i
- T
- p
- i
- +
- 1
- ,
- α
-
- v
- _
- i
- T
- …
- p
- t
- 1
- ,
- α
-
- v
- _
- i
- T
-
- -
- v
- _
- i
- T
- 0
- …
- 0
- 0
- -
- v
- _
- i
- T
- …
- 0
- ⋮
- ⋮
- ⋱
- ⋮
- 0
- 0
- …
- 0
- ︸
- ]
- where last t2α columns contain t2 −viT aligned upper-diagonally,
- setting an α×(d−t+1) matrix:
- Γ
- i
- =
- [
- -
- p
- t
- 1
- +
- 1
- ,
- 1
- ...
- -
- p
- k
- ,
- 1
- 0
- ...
- 0
- ⋮
- ⋱
- ⋮
- ⋮
- ⋱
- ⋮
- -
- p
- t
- 1
- +
- 1
- ,
- t
- 2
- +
- 1
- ...
- -
- p
- k
- ,
- t
- 2
- +
- 1
- 1
- ...
- 0
- ⋮
- ⋱
- ⋮
- ⋮
- ⋱
- ⋮
- -
- p
- t
- 1
- +
- 1
- ,
- α
- ...
- -
- p
- k
- ,
- α
- 0
- ...
- 1
- ]
- where right bottom corner thereof is an (α−t2)×(α−t2) identity matrix,
- b) setting a sub-repair matrix related to missing parity blocks:
- setting an α×d matrix Ψi:
- Ψ
- i
- =
- κU
- ′
-
- [
- -
- p
- 11
- …
- -
- p
- k
- ,
- 1
- 1
- …
- 0
- 0
- …
- 0
- ⋮
- ⋱
- ⋮
- ⋮
- ⋱
- ⋮
- ⋮
- ⋱
- ⋮
- -
- p
- 1
- ,
- i
- -
- 1
- …
- -
- p
- k
- ,
- i
- -
- 1
- 0
- …
- 1
- 0
- …
- 0
- κ
- -
- 1
-
- p
- 1
- ,
- i
- …
- κ
- -
- 1
-
- p
- k
- ,
- i
- 0
- …
- 0
- 0
- …
- 0
- -
- p
- 1
- ,
- i
- +
- 1
- …
- -
- p
- k
- ,
- i
- +
- 1
- 0
- …
- 0
- 1
- …
- 0
- ⋮
- ⋮
- ⋮
- ⋱
- ⋮
- ⋮
- ⋱
- ⋮
- -
- p
- 1
-
- α
- …
- -
- p
- k
- ,
- α
- 0
- …
- 0
- 0
- …
- 1
- ]
- +
- [
- 1
- …
- 0
- …
- 0
- ⋮
- ⋱
- ⋮
- ⋱
- ⋮
- 0
- …
- 1
- …
- 0
- 0
- …
- 0
- …
- 0
- ⋮
- ⋱
- ⋮
- ⋱
- ⋮
- 0
- …
- 0
- …
- 0
- ]
- where right side of equal sign thereof is composed of two parts:
- last α−1 columns of the matrix in left bracket containing two identity matrices, upper-left corner of the matrix in right bracket being a k×k identity matrix and other entries thereof being all zero,
- setting a sub-repair matrix corresponding to ci by using Ψi:
- for each j∈ Ji, calculating Ωi,j=−ψijūiT, where ψij denotes jth column of Ψi , Ji={j|j=1, . . . , t1,k+1, . . . ,k+t2−1} denotes column indices of corresponding to missing blocks except ci ,
- then letting Δi=[Ωi,1, . . . , Ωi,t1, Ωi,k+1, . . . , Ωi,k+i−1, I, Ωi,k+i, . . . , Ωi,k+t2−1], and denoting ΨiJ omitting columns of IDs Ji by ΨiJ;
- and
- step 3:
- setting a repair matrix and regenerating missing data blocks:
- combining sub-repair matrix obtained in step 2:
- [
- Φ
- 1
- ⋮
- Φ
- t
- 1
- Δ
- 1
- ⋮
- Δ
- t
- 2
- ]
-
- [
- b
- 1
- T
- ⋮
- b
- t
- 1
- T
- c
- 1
- T
- ⋮
- c
- t
- 2
- T
- ]
- =
- [
- Γ
- 1
- ⋱
- Γ
- t
- 1
- Ψ
- 1
- J
- ⋱
- Ψ
- t
- 2
- J
- ]
-
- [
- h
- ⇀
- 1
- ⋮
- h
- ⇀
- t
- 1
- g
- ⇀
- 1
- ⋮
- g
- ⇀
- t
- 2
- ]
- letting Ξ=[Φ1, . . . , Φt1, Δ1, . . . , Δt2]T,
- Θ
- =
- [
- Γ
- 1
- ⋱
- Γ
- t
- 1
- Ψ
- 1
- J
- ⋱
- Ψ
- t
- 2
- J
- ]
- ,
- then repair matrix being R=Ξ1Θ, and multiplying the repair matrix with the helper data sub-blocks to regenerate missing data blocks.