《网络编码在分布式存储中的应用》由会员分享，可在线阅读，更多相关《网络编码在分布式存储中的应用（25页珍藏版）》请在金锄头文库上搜索。
1、网络编码在分布式存储 中的应用王庆斌 南京邮电大学*基本内容n分布式存储系统简介n采用编码进行分布式存储信息ReplicationErasure codeRegenerating codenRepair 模型Functional RepairExact RepairExact Repair of systematic partsDate分布式存储系统（1）n存储系统的分类 n存储系统从结构上主要分为两种，集中式和分布 式，这里的集中和分布并不简单是地理上的集中 和分散，而主要在于是否具有统一的数据管理机 制。n集中式存储系统采用统一的数据管理，而分布式 存储系统将数据管理的任务分配给各存储节点
2、。Date分布式存储系统（2）n分布式存储优点可靠性可行性网络拥塞Date编码实现分布式存储nRepliaction=Repetition coden每个存储节点将源信息的副本。n可靠性高，但对节点的存储量要求较高。AAA四 个 节 点 存 储A源 文 件四 个 节 点 存 储四 个 节 点 存 储A源 文 件四 个 节 点 存 储Daten纠删码（Erasure code）n基本思想：k个分组的原数据在发送端编码为n个 分组的数据，其中任意k个分组都可以完全重建 原数据。这种编码可以容忍n-k个分组丢失。 Date（4,2）MDS 纠删码任意2个都可以完整重建源信息。比Repliaction
3、在存储有效性上优越。源 信 息ABABB四 个 存 储 节 点A 2BABABA三 个 存 储 节 点（3,2）MDS 纠删码源 信 息四 个 存 储 节 点AB三 个 存 储 节 点n举例说明源 信 息ABB四 个 存 储 节 点A 2BABABA三 个 存 储 节 点源 信 息四 个 存 储 节 点AB三 个 存 储 节 点DatenRegenerating code由Alex Dimakis 于2007年Network Codingfor Distributed Storage Systems 中提出的“We identify a tradeoff between storage and
4、 repair bandwidth and show that codes exist that achieve every point on this optimal tradeoff curve. We call codes that lie on this optimal tradeoff curve regenerating codes. ”与Erasure code类似，原信息分为k个分组，编码 后存储到n个节 点中，任意k个节点可以恢复出原信息。Date简单的Regenerating code 编码过程(1)取自K. V. Rashmi等的Explicit Construction
5、 of Optimal Exact Regenerating Codes for Distributed Storage原文件（9 Petabyte ）分成9片，每片 1 PetabyteDate简单的Regenerating code 编码过程(2)XOR15243点为存储节点，边为存储的信息，每个点存储4 Petabyte。恢复完整信息只需3个存储节点（9/10）。9+1DateRepair过程15243只需要从与失效节 点有公共存储信息 的每个节点节点获 取1Petabyte就可 以恢复该节点失效节点Date基本概念n重建n为系统中节点个数，每个节点存储a个分组，终端节点通 过节点字节恢
6、复原始信息nRegeneration（Repair a node）当某一个节点失效时，自愈系统可以从其他未失效节点下 载一些信息然后恢复该失效节点nRepair bandwidth在恢复失效节点的过程中所需要下载的信息总量DateRepair问题ABCDE?Date不同编码的Repair比较nReplicationRepair带宽为整个源文件的大小从任意一个未失效节点获取n纠删码repair带宽为整个源文件的大小从多个未失效节点获取nRegenerating coderepair带宽比整个源文件要小很多从多个未失效节点获取DateRepair 模型A1+B1A2+B2B1B2A1A2A2+B1
7、A1+A2+B2A1？A2？B2A2+B2A1+A2+B2Failed nodeNew nodeDateRepair 模型nExact repair替代原失效节点的新节点存储的信息与失效节点所存 储的完全相同。nFunctional repair替代原失效节点的新节点存储的信息与失效节点所存 储的不同，但满足纠删码的特性。nExact Repair of systematic parts介于Functional repair与Exact repair之间。DateFunctional repairn由Network Coding for Distributed Storage ystems 知
8、可用信息流图中的多播来表示。S：信源；Xi：输入节点（i=1,2,3,4）；X5替代失效 节点；输出节点；DC：需要重建源文件的节点Date基本结论，定理1：对于任意的 ，点 是可行 的，且线性网络编码可实现，任意 理论 上是不可行的。 定义如下：n：节点的个数，k：重建文件所需的最少的节点数，d：repair时需要提供下载 资源的节点数， ：节点存储的信息量， ：repair带宽 ， ：从每个提 供下载的节点所获得的信息量。DateMSR和MBRnMSR（Minimum-stroage regenerating）(5) 最小的网络带宽在使newcomer所有其他节点通信时实 现的。即d=n-
9、1时(6)MSR 编码的通信量为(n-1)/(n-k)(M/k)，要比节点所存 储的信息量M/k要大 DatenMBR（Minimum-bandwidth regenerating）(7)由上式可知存储信息和总的repair的通信量大小相等。 令d=n-1，可得：(8) ，MBR编码没有repair带宽扩展，和replication 系统一样，下载的总量为一个节点存储的信息量。然 而，在存储时，有个扩展因子为(2n-2)/(2n-k-1)，因而 就冗余可靠性而言不是最优的。DateExact repairnExact-MBR 编码定理2：对d=n-1，公式(8)的割集的下界，可以通过域最 大为
10、n(n-1)/2有限域的deterministic 策略实现。(5,3)-MBR 编码 的编码过 程(不同的颜色)和Repair过程( 蓝色的椭圆 )DatenExact-MSR 编码干扰校对(interference alignment)用于校对维数小于干 扰数的信号子空间中的多个干扰信号。具体而言，解 码器解码出一个受两个不同信号干扰的期望的信号。如下，给出有4个变量的线性等式，一般情况下，任 何变量也无法求出（只是一个子空间）。A1+2A2+B1+B2=y12A1+A2+B1+B2=y2B1+B2=y1有些变量的系数在 较小的子空间内， 可以将他们剔除Date(4,2)-MSR 编码（节
11、点1失效） DateExact repair of the systematic part X为2k长的原始信息，变量ui不随时间变 化，而vi会随着 编码的repair而变化。我们保持时不变特性即2n个的2k长的 变量ui,vi构成一个(2n,2k)-MDS码，ui,vi中的任意2k个变 量的秩都为2k，满秩。这就说明n个节点构成了一个(n,k)- MDS码。 Date参考文献nA Tutorial on Interference AlignmentFarzad TalebinCoding for Distributed Storage WikinBring reliability to t
12、he cloud:regenerating codes for distributed storage.mp4nNetwork coding for Distributed Storage1AlexDimakis.mp4nNetwork coding for Distributed Storage2AlexDimakis.mp4nNetwork Coding for Distributed Storage SystemsnA Survey on Network Codes for Distributed StoragenExplicit Construction of Optimal Exact Regenerating Codes for Distributed StorageDate
