Methods of data concurrent recovery for a distributed storage system and storage medium thereof

A distributed storage system with data concurrent recovery function, 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, the system comprising multiple storage nodes each holding a data block, the multiple storage nodes residing on one or more computers each comprising a processor and a storage, the multiple storage nodes comprising systematical nodes that store the systematical blocks, parity nodes that store the parity blocks, and a regenerating node that collects helper data from surviving systematical nodes and surviving parity nodes and regenerates lost data blocks on failed nodes, each surviving node that offers helper data sub-blocks being an assistant node,

• wherein the system is configured to perform a method of data concurrent recovery comprising following steps:
• step 1:
• obtaining helper data sub-blocks from an 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
• 12
• ⁢
• v
• _
• i
• T
• ⋮
• p
• 1
• ⁢
• α
• ⁢
• v
• _
• i
• T
• ⁢
• ⋯
• ⋯
• ⋱
• …
• ⁢
• p
• i
• -
• 1
• ,
• 1
• ⁢
• v
• _
• i
• T
• p
• i
• -
• 1
• ,
• 2
• ⁢
• v
• _
• i
• T
• ⋮
• p
• i
• -
• 1
• ,
• α
• ⁢
• v
• _
• i
• T
• ⁢
• u
• _
• 1
• T
• +
• p
• i
• ⁢
• 1
• ⁢
• v
• _
• i
• T
• u
• _
• 2
• T
• +
• p
• i
• ⁢
• 2
• ⁢
• v
• _
• i
• T
• ⋮
• u
• _
• α
• T
• +
• p
• i
• ⁢
• α
• ⁢
• v
• _
• i
• T
• ⁢
• p
• i
• +
• 1
• ,
• 1
• ⁢
• v
• _
• i
• T
• p
• i
• +
• 1
• ,
• 2
• ⁢
• v
• _
• i
• T
• ⋮
• p
• i
• +
• 1
• ,
• α
• ⁢
• v
• _
• i
• T
• ⁢
• ⋯
• ⋯
• ⋱
• …
• ⁢
• p
• t
• 1
• ,
• 1
• ⁢
• v
• _
• i
• T
• p
• t
• 1
• ,
• 2
• ⁢
• v
• _
• i
• T
• ⋮
• p
• t
• 1
• ,
• ⁢
• α
• ⁢
• v
• _
• i
• T
• ⁢
• -
• v
• _
• i
• T
• 0
• ⋮
• 0
• ⁢
• 0
• -
• v
• _
• i
• T
• ⋮
• 0
• ⁢
• ⋯
• ⋯
• ⋱
• ⋯
• ⁢
• 0
• 0
• ⋮
• 0
• ︸
• totally
• ⁢
• ⁢
• t
• 2
• -
• v
• _
• ⁢
• i
• T
• ]
• 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
• ]
• wherein Ψi is composed of:
• a sum of a matrix in a left bracket and a matrix in a right bracket, wherein 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 Ψi 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.