IDA(Information Dispersal Algorithm)

• IDA 介绍

IDA是一种数据分片备份容错算法,将一个文件F，假设长度为L,分成n个小片Fi, 1<= i <=n,每片大小为L/m,因而只要任意选择n中的m片,即可重建整个文件F.这种分片重构算法很适合容错,也可以用来保证重要数据的传输，整个的数据容量为n/m*L,由于n/m可以接近于1，所以IDA空间较之分片前数据容量比率不大,比主从双备份节省空间,并且只要n片中任意m即可.

• IDA算法原理介绍

将一个文件F看成一系列的字节集合,B1,B2,B3,B4....BN(N为文件总字节数),那么0<=Bi<=255,取一个素数大于255,p=257,所有的运算都进行的是mod p运算.

对于一个给定的r(你可以视r为丢失数据与幸存数据比率)>0,选择一个m使得n=m+k,满足n/m<=1+r,即k/m<r.然后选择n个向量Ai=(Ai1,Ai2,Ai3...Aim),1<=i<=n,组成一个n*m的矩阵,假设为A,其中任一m个向量子集都是线性独立的,即在{A1,A2...An}中任选m个向量都线性独立.

假设把F文件分成长度为m的一系列的小块,如:

F=(B1,B2,B3,..Bm),(Bm+1, Bm+2...B2m),.....(...BN)(N为文件总字节数)

假定记S1=(B1,B2,B3...Bm),S2=(Bm+1,Bm+2....B2m),Sk=(B(k-1)*m+1,B(k-1)*m+2....Bkm),...

那么编码后的分片表示为Fi=Ci1,Ci2,Ci3...CiN/m(大小为N/m个字节,N为文件总字节数),1<=i<=n,

Cik=Ai*Sk=Ai1*B(k-1)m+1 + .... Aim * Bkm

如果在F1...Fn中任选其中m片，比如F1,..Fm,那么矩阵A也选对应的向量ai,...am,构成一个m*m的矩阵A',那么存在下面等式:

A' * (B1,B2,....Bm) = (C11,C21,..Cm1),

A' * (Bm+1, Bm+2...B2m)=(C12,C22,...Cm2),

A' * (B(k-1)*m+1, B(k-1)*m+2,...Bkm)=(C1k,C2k..Cmk)

......

A' * (.......BN)=(C1N/m,C2N/m,....CmN/m)

即A' * F = (F1,F2...Fm),

F = (F1,F2,...Fm) * Z,Z为A'的反向矩阵即A*Z=1,假设表示为(Zz1,Z2,...Zm),Zi=(Zi1,Zi2...Zim), 1<=i<=n,

则

(B1,B2,....Bm) = Z*(C11,C21,..Cm1)

Bj=Zi1*Cik+...+ Zim*Cmk,1<=k<=N/m,1<=j<=N,i=j mod m,k=[j/m](取整).

如此这可以还原整个数据F.

• 简要概括

就是将一个给定的n*m的矩阵A,乘以一个m*(N/m)的矩阵F(F即为要分片的文件N为整个文件的大小),得到一个n*(N/m)的结果数据,原理就是这个n*(N/m)的结果数据,即n片编码后的数据,只要其中任意m片数据集合F'(即一个m*m矩阵),就可以从矩阵A得到一个对应的m*m的矩阵A',使得A' * F = F',推导出F=Z*F',(Z*A'=1),得到整个文件F.

•  参考来源

Efficient Dispersal of Information for Security,Load Balancing, and Fault Tolerance (MICHAEL O.RABIN)