《基于网络编码理论的分布式存储》由会员分享，可在线阅读，更多相关《基于网络编码理论的分布式存储（48页珍藏版）》请在金锄头文库上搜索。
1、基于网络编码理论的分布式存储基于网络编码理论的分布式存储自修复编码及进展自修复编码及进展 深圳市云计算机重点实验室 1Institute of Microelectronics报告提纲报告提纲1.网络编码理论简介网络编码理论简介2.分布式存储介绍分布式存储介绍3.存储需求及编码策略存储需求及编码策略4.自修复码的进展自修复码的进展5.未来研究方向未来研究方向Institute of Microelectronics诞生于香港中文大学学的网网络编码理论（NC）简介第第1篇线性网络编码理论的论文由香港中文篇线性网络编码理论的论文由香港中文大学李硕彦，杨伟豪大学李硕彦，杨伟豪: Li-Yeung,
2、“Network multicast flow via linear coding,” Proc. ISORA conference, 8/1998.奠定网络编码理论基础的论文，获得了奠定网络编码理论基础的论文，获得了IEEE 信信息论学会息论学会2005年最佳论文奖年最佳论文奖: 李硕彦等, “Linear Network Coding,” 2/2003， IEEE Trans. On Info. Theory. 信息流不是水流，可以运算压缩后再传送。 故节点的功能应该是 ：“编码”+ 转发。3Institute of MicroelectronicsMIT科学家07年6月在科学美国人杂志以
3、“Breaking Network Logjams”（打破网络僵局）为题详细介绍了诞生于香港中大的NC理论。指出，网络编码是继60年前仙农发表“通信的数学原理”后，网络通信理论的一个全新突破。仙农解决了点对点信道的容量极限问题，而NC解决了如何达到单源对多点及多源对多点的网络通信容量极限的问题。IEEE数据库： NC论文35000篇/ total 320万 Papers4Institute of Microelectronics云存储分布式存储介绍分布式存储介绍5Institute of Microelectronics分布式存储介绍分布式存储介绍/ 6Institute of Microel
4、ectronics分布式存储介绍分布式存储介绍Google 数据中心OregonOklahoma7Institute of Microelectronics分布式存储介绍分布式存储介绍由于自然灾害，电力故障等可能导致节点失效8Institute of Microelectronics分布式存储介绍分布式存储介绍分布式存储(复制)ABAA, BB客户端kshum9Institute of Microelectronics分布式存储介绍分布式存储介绍数据的大小B每个节点存储的数据量为B/kn个存储节点任意k个节点可恢复原始数据MDS（Max. Distance Separable）特性分布式存储(
5、Reed-Solomon codes)节点1节点2节点3节点410Institute of MicroelectronicsA1A2B1B2A1+B12 A2+B2A1, A2,B1, B22 A1+B1A2+B2客户端分布式存储介绍分布式存储介绍分布式存储(Reed-Solomon codes):数据重建11Institute of MicroelectronicsA1A2B1B2A1+B12 A2+B2A1, A2,B1, B22 A1+B1A2+B2为修复B/k=2 的数据使用了K倍(B/k)的带宽B=4带宽A1A2B1, B2A1+B1, 2 A2+B2分布式存储介绍分布式存储介绍分布
6、式存储(Reed-solomon codes)12Institute of Microelectronics存储需求存储需求9. 最小最小I/O；7. 修复带宽；修复带宽；8.修复节点；修复节点；4.编解码复杂度；编解码复杂度；5.重建带宽；重建带宽；可靠性编解码时间修复时间1. MDS特性；特性；2. 存储节点的数量；存储节点的数量；3. 每个节点的可靠性；每个节点的可靠性；6.编码率；编码率；13Institute of Microelectronics编码策略编码策略再生码SIn1Out1In2Out2In3Out3In4Out4Out5In5客户端14Institute of Micr
7、oelectronics最小割SIn1Out1InnOutnDCk-1d编码策略编码策略15Institute of Microelectronics编码策略编码策略n=10，k=516Institute of MicroelectronicsRGC：MDS特性、修复特性、修复带宽最小、最小、但是：但是：修复修复节点数点数 k（修复（修复协议很复很复杂), 编解解码复复杂度度 比比 RS码 大一个数量大一个数量级。RS码：MDS特性、修复特性、修复带宽B、参与修复、参与修复节点数点数k。自修复自修复码SRC(self-repairing codes) ： 基于同基于同态的自修复的自修复码 HS
8、RC (Homomorphic Self-Repairing Codes) 基于射影几何的自修复基于射影几何的自修复码 PSRC (Projective Self-repairing Codes)。编码策略编码策略Institute of MicroelectronicsHSRC-基于同基于同态的自修复的自修复码:优点：参与修复点：参与修复节点数点数为2；修复；修复过程只涉及异或运算；程只涉及异或运算；缺点：缺点： 编解解码复复杂度高，度高， 没有有效的重建没有有效的重建过程；程； 不不满足足MDS特性特性。PSRC-基于射影几何的自修复基于射影几何的自修复码优点：修复点：修复节点点为2； 修
9、复修复过程、程、重建重建过程程均只涉及异或运算均只涉及异或运算；缺点：缺点：编码率不可控且很低，存率不可控且很低，存储空空间效率低效率低。 重建重建带宽不是最小不是最小 ；不；不满足足MDS特性，特性，编码策略编码策略Institute of Microelectronics编码策略：编码策略：RGC & PSRC不实用不实用RGC: 降低复降低复杂度，减少度，减少I/O消耗消耗PSRC: 需提高需提高编码率，最率，最优化修复化修复带宽19Institute of Microelectronics自修复码的进展自修复码的进展最近我们提出通用射影自修复码GPSRC(General Project
10、ive Self-repairing Codes)满足自修复码特性；编码率可控，较高；一般修复过程存在修复带宽和修复节点的折中；重建带宽达到最小；缺点：不满足MDS特性。20Institute of Microelectronics自修复码的进展自修复码的进展射影几何介绍W：GF(q)的m-维向量空间射影几何 PG(m-1，q)：W的所有子空间组成的集合t-空间：W的(t+1)-维子空间t-扩展：t-空间的集合SPG(m-1，q)的存在t-扩展的充要条件：（t+1）整除m21Institute of Microelectronics自修复码的进展自修复码的进展射影几何介绍向量空间W：m-维有限
11、域GF(qm)GF(q) GF(qt+1) GF(qm)GF(qm)*表示GF(qm)的非零元素，是循环乘法群w和v分别为GF(qm)*和GF(qt+1)*的本原元zGF(qt+1)* = z x: x GF(qt+1)*表示GF(qm)*的陪集，z GF(qm)i=0，1，2，N= (qm1)/(qt+11) 1，陪集wiGF(qt+1)为PG(m，q)的t-扩展22Institute of Microelectronics自修复码的进展自修复码的进展通用射影自修复码的参数定义：文件大小为B，用长度为B的GF(2)上的元素表示;t为满足(t+1)整除B的正整数;N为正整数(2B1)/(2t+
12、11)，也是GF(2B)*在GF(2t+1)*中陪集的个数;GPSRC基本特征：每个节点存储 = t+1数据。存储节点的数量n 为B到N之间的一个整数, 即B n N 。失效节点可以通过d个修复节点精确修复，修复节点数量d 为2到t+1的一个整数，2 d t+1。GPSRC(n，k)，n为存储节点个数，每个节点存储B/k数据。23Institute of Microelectronics自修复码的进展自修复码的进展通用射影自修复码的构造方法：Step2：V1=1, v, v2, , vt 为向量空间GF(2t+1)的一组基。 对于i=1, 2, n，节点i的编码向量分别为t-扩展的一组基： V
13、i =wi1, wi1 v, wi1 v2, , wi1 vt。Step1： 设v是GF(2t+1)*的本原元；即1, v, v2, , vt为GF(2t+1)*的一组 基，1, v, v2, , vt 在有限域GF(2)中线性独立。Step3： 对于i=1, 2, n，节点i存储的编码数据为数据文件与编码 向量wi1 vj的乘积，j = 0, 1, 2, t。 （乘积是指数据文件与编码向量对应的二进制数的异或运算）。24Institute of Microelectronics自修复码进展：重建过程自修复码进展：重建过程引理2：编码矩阵的任意一列的连续B个元素均相互独立。证明：假设数据收集者
14、分别下载了节点i, i+1, , i+B-1的第一个编 码数据，编码向量分别为wi, wi+1, , wi+B1。如果存在B个不全为0的系数c1, c2, , cB，使得c1 wi + c2 wi+1+ + cB wi+B1 =0。那么对上式两端同时除以wi，则得到c1+c2w1+cBwB1等于0，这与1, w1, wB1是GF(2B)的一组基相矛盾。由引理2知，编码矩阵的任意一列的连续的B个元素均相互独立，所以可以解码出B个原始数据，即可以恢复出原始数据B。故GPSRC重建数据的方法：下载连续的B个存储节点的第 l列编码数 据, 且1 l t+1 。25Institute of Microe
15、lectronics自修复码的进展自修复码的进展: 修复过程修复过程引理4：在GPSRC(n, k)码中，当一个存储节点失效时，那么最少情况下，只从(a+1) = (t+2）个存储节点中各下载 1 个数据，修复带宽为（t+2），达到最优。(证明见下页）引理3：PSRC(n，k)码，当一个存储节点Nl失效时，可以通过选择任意1个存储节点及其相应的另一个存储节点并下载这2个存储节点来恢复出失效节点Nl存储的数据。26Institute of Microelectronics证明：由引理3知，一个失效的数据可以通过任意的选择1个节点的数据并对应的下载另一个节点的1个数据来恢复。Step1.：假设一个
16、节点丢失数据的编码向量为v1，v2，,va，那么可以任意的选择一个节点的编码向量u1以及其相对应的另一个节点的编码向量u2，使得v1=u1+u2。Step2：之后，选择修复v2的一个编码向量为u2以及其相对应的编码向量u3使得v2=u2+u3。Step3：同样的道理，可以得到v3=u3+u4，, va=ua+ua+1。所以修复编码向量v1，v2，,va共下载了最多(a+1)个存储节点的编码向量(u1，u2，,ua+1)，修复带宽为(a+1)。称该修复过程为最佳带宽修复过程。自修复码的进展：修复过程自修复码的进展：修复过程27Institute of Microelectronics自修复码的进
17、展自修复码的进展两个节点修复模型多个节点修复模型28Institute of Microelectronics自修复码的进展：例子自修复码的进展：例子以B=8位2进制数据o1,o2,o3,o4,o5,o6,o7,o8,为例；取t=3，满足（t+1）整除B，于是有节点数n取值范围为BN。这里取n=B，编码后存在n=8个节点，每个节点存（t+1）=4位。29Institute of Microelectronics自修复码的进展：例子自修复码的进展：例子N2=w，w18，w35，w52，N3=w2，w19，w36，w53，N4=w3，w20，w37，w54，N5=w4，w21，w38，w55，N6
18、=w5，w22，w39，w56，N7=w6，w23，w40，w57，N8=w7，w24，w41，w58由射影几何可知，1 , v, v2, v3 形成了子域GF(24)的基。不妨记节点1的编码向量为1, v, v2, v3，即为N1=1，w17，w34，w51同理，其它7个存储节点存储的向量空间分别为：30Institute of Microelectronics自修复码的进展：例子自修复码的进展：例子节点1的编码向量为1, v, v2, v3，即为N1=1，w17，w34，w51指定前8个元素分别表示为：1=00000001，w=00000010，w2=00000100，w3=0000100
19、0，w4=00010000，w5=00100000，w6=01000000，w7=10000000，31Institute of Microelectronics自修复复码的进展：例子通过前面的介绍，我们知道节点1的存储向量空间为N1=1，w17，w34，w51，故节点1存储数据块依次为：o1，o4+o5+o8，o2 +o3+o4+o7，o2 +o4。根据其他节点的编码向量空间，同理可求出其他节点的数据块存储情况，如下图所示 。32Institute of Microelectronics自修复码的进展自修复码的进展节点数据块存储分布33Institute of Microelectronic
20、s自修复码的进展自修复码的进展通用射影自修复码的重建过程编码矩阵的任意一列的连续B个元素均相互独立。下载连续的B个存储节点的第l 列编码数据在例子GPSRC(8，2)中，任意一列的编码数据都可以重建出原始数据文件34Institute of Microelectronics编码矩阵的任意一列的连续B个元素均相互独立 假设数据收集者分别下载了节点i, i+1, , i+B的第一个编码数据，编码向量分别为wi,wi+1, , wi+B1。如果存在B个不全为0的系数c1, c2, , cB，使得c1 wi + c2 wi+1+ + cB wi+B1 =0。那么对上式两端同时除以wi，则得到c1+c2
21、w1+cBwB1等于0，这与1, w1, wB1是GF(2B)的一组基相矛盾。自修复码的进展自修复码的进展35Institute of MicroelectronicsGPSRC码的重建数据的方法为：下载连续的B个存储节点的第l列编码数据，其中 。由以上引理知，编码矩阵的任意一列的连续的B个元素均相互独立，所以可以解码出B个原始数据，即恢复出原始数据B。自修复码的进展自修复码的进展36Institute of Microelectronics自修复码的进展自修复码的进展通用射影自修复码的修复过程(o1+o3+o5)+(o3+o5)=o1(o5+o7)+(o1+o4+o7+o8)+o1=(o4+
22、o5+o8)(o3+o5)+(o2+o4+o5+o7)=( o2+o3+o4+o7)(o5+o7)+(o2+o4+o5+o7)=( o2+o4)37Institute of Microelectronics自修复码的进展自修复码的进展通用射影自修复码的性能评估自修复能力：修复存储节点的修复节点对的个数，用Cr表示。B=8，(t+1)=2，n=8Node 12345678Cr1111121138Institute of Microelectronics自修复码的进展自修复码的进展通用射影自修复码的性能评估B=8，(t+1)=2，n=10Node 12345678910Cr 1112222211B
23、=8，(t+1)=2，n=12Node 123456789101112Cr 22122343222239Institute of Microelectronics自修复码的进展自修复码的进展通用射影自修复码的性能评估GPSRC修复带宽表示为再生码的修复带宽为当B足够大时，GPSRC的修复带宽优于MSR。实际上，当B=32，(t+1)=4时，GPSRC的修复带宽为6、修复节点为3。而对于MSR码，修复带宽是由(2)式确定的，(2)式是关于d个一个减函数。因此，如果d=15，MSR码可以达到其最小的修复带宽为7.5，大于GPSRC的修复带宽。40Institute of Microelectron
24、ics自修复码的进展自修复码的进展通用射影自修复码的性能评估 B=16，k=441Institute of Microelectronics自修复码的进展自修复码的进展通用射影自修复码的性能评估：由下图，一般情况下GPSRC在修复带宽和修复节点性能中均优于MSR码，而其代价为失去MDS特性。 B=32，k=442Institute of Microelectronics自修复码的进展自修复码的进展自修复码与RS码的开销评估RS：k(n-k)(w-1) (w-1)SRC： nw(w-1)/kw=8，k=243Institute of Microelectronics自修复码的进展自修复码的进展自
25、修复码与柯西优化RS码的开销评估44Institute of Microelectronics总结总结GPSRC满足PSRC的基本特性，选择节点灵活，编码率高；修复过程，修复带宽和修复节点均优于MSR码；重建过程，重建带宽达到最优；构造过程、修复过程和重建过程：异或运算，计算复杂度很低；计算复杂度、修复带宽以及修复节点，优于擦除编码、再生码；GPSRC易于实施、精确修复代价低。一般情况，不满足MDS特性。45Institute of Microelectronics未来研究方向：同时满足下面性质的码未来研究方向：同时满足下面性质的码1.MDS特性2. 最小修复带宽3. 最小重建带宽4. 精确修
26、复5. GF（2）6. 最小I/O46Institute of Microelectronics主要参考文献主要参考文献1 A. G. Dimakis, P. B. Godfrey and Y. Wu and M. J. Wainwright and K. Ramchandran, Network coding for distributed storage system, INFOCOM, May, 2007. 2 OGGIER. F, DATTA. A, “Self-repairing Homomorphic Codes for Distributed Storage Systems”,
27、in IEEE Proc. INFOCOM 2011.3 OGGIER. F, DATTA. A, “Self-Repairing Codes for Distributed Storage A Projective Geometric Construction”, ITW 2011.4 Hanxu Hou, Hui Li, Kenneth Shan, “General Self-repairing Codes for Distributed Storage System”, submitted to IEEE ICC 2013.5 Hanxu Hou, Hui Li, “Practical Self-repairing Codes for Distributed Storage System”, in Proc. IEEE APCloudCC 2012.6 Yuanbo Han, Hui Li, Hanxu Hou, “A Model of Erasure-Coding-Based Distributed ”, in Proc. IEEE APCloudCC 2012.47Institute of Microelectronics谢谢！48
