IPv6网络中基于喷泉码的分布式存储系统研究

文 /郝树华 安红心 袁磊

随着互联网和物联网的飞速发展，越来越多的信息需要存储到计算机网络中。例如一个视频码率为8Mbit/s的摄像头一天将产生超过86G的信息，一个智慧城市中的交通和安防摄像头的数目至少几十万个并且还在增长，它们每天产生的信息都需要存储在互联网中。又如在教育行业新兴的慕课、腾讯课堂以及各种教育资源也需要占用大量的存储空间。信息量的爆炸式增长带来了如何高效、低成本、可靠存储信息的难题。一些重要信息的毁坏或丢失将带来非常严重的后果，提高存储信息的可靠性和降低存储成本是一个极其重要的研究方向。大数据时代下，可靠保存和有效管理信息变得尤为重要。大型数据中心的规模有几千到几万台存储服务器，如百度最大的数据中心服务器设计装机规模超过16万台，将承担80%的流量，众多的服务器设备的升级、维修等耗费巨大，并且不能完全保证用户存储的信息不丢失。例如谷歌、亚马逊等存储服务系统都曾出现过问题。一种有效降低成本的办法是将众多普通存储设备组合起来构成一个分布式存储系统。为了保证信息的高可靠性，常用的方法是副本方式。副本就是对原始文件进行完全复制，这种做法占用存储空间大，副本存储占用空间是原始文件大小的整数倍，如微软、亚马逊等公司都采用过三副本方式存放新创建的数据[1]。之后研究人员将具有防止数据丢失特性的纠删码(Erasure Correcting Codes)引入存储领域，纠删编码技术相对于副本存储技术具有更高的存储效率[2]。常用的纠删码有里德所罗门编码(RS码, Reed Solomon Codes)、局部重构编码(LRC码,Local Reconstruction Codes)。将纠删码应用于存储集群的实例如谷歌在其GFS文件系统增加了RS码支持，它采用了最基本的RS (6,3)编码，最多可允许包括数据块和校验块在内的任意3个块错误；Facebook早期在HDFS RAID中采用的编码方式为RS(10,4)，进阶版“HDFS”采用了LRC(10,6,5)[1]。喷泉码(Fountain Codes)是一类码率不受限的纠删码[3,4]，与普通纠删码(如RS码、LRC码)相比，喷泉码更适合于分布式存储系统，因为它的编译码复杂度低得多，并且它能任意调整冗余比例[5]。分布式存储系统引入喷泉码之后，经过编码可以产生任意大小的编码文件而不必是原始文件的整数倍，并且编码后的文件将建立各个文件块之间的联系，即受到破坏的文件块可以由其他已恢复文件进行译码恢复，从而提高了存储信息的可靠性。

兰州大学

国内现阶段网络资源存储基本都是基于IPv4设计与实现的。IPv6是用来替代现行版本IPv4的下一代IP协议。IPv4使用的是32位地址，而IPv6使用128位地址，这表示有340万亿个地址可以使用。并且IPv6使用更小的路由表，提高了路由器转发数据包的速度，减少网络传输时延；IPv6可以对网络层的数据进行加密并对IP报文进行校验，极大地增强了网络的安全性。2017年，中共中央办公厅、国务院办公厅印发了《推进互联网协议第六版(IPv6)规模部署行动计划》，该行动计划旨在加快推进基于互联网协议第六版(IPv6)的下一代互联网规模部署，促进互联网演进升级和健康创新发展[6]。

兰州大学作为CERNET、CNGI-CERNET2在甘肃省的中心节点，在1999年初开始进行关于IPv6的实验性研究，是国内最早建成的功能齐全的IPv6试验床，并通过CNGI-CERNET2主干网建设和驻地网建设，在学校全网范围开通了IPv6/IPv4双协议栈接入[6]。目前兰州大学校园网IPv6全覆盖，为IPv6协议下的实验奠定了物理基础。本文设计实现了IPv6网络中基于喷泉码的分布式存储原理系统，该系统采用C++语言在Qt开发框架下完成[7]，实现了文件的喷泉编码、分布式存储、译码恢复等功能，实测结果表明IPv6网络中基于喷泉码的分布式存储系统具有高效可靠的性能。本文所提方案为兰州大学校内资源快速、稳定、可靠存储提供了一种新的设计思路。

喷泉码介绍

喷泉码最早起源于通信领域，是针对删除信道下大规模数据广播和分发的需求提出的解决方案[4]。该方案通过对传输信息进行编码传输，以解决传输过程中信息丢失的问题。由于喷泉码具有无码率、编码后节点地位相同等特点，将其引入分布式存储领域代替普通纠删码，可以提高存储可靠性和降低编译码复杂度[5]。

上世纪90年代Luby等人首次提出喷泉码的概念，但并未给出实用的设计方案[4]。其基本思想是将一个原始文件分成一定数目的文件块，每个编码块都是由任意个文件块异或得到，接收端只要接收到足够数量的编码块，即可完成译码恢复原始文件。由于参与编码的文件块是随机选择的，并且数目任意，理论上可以产生无限多的编码块，故具有无码率的特点。这个过程像是喷泉源源不断喷出水滴，故取名为喷泉码[3,4]。随后Luby提出第一个实用喷泉码设计方案：LT(Luby Transform)码[8]，之后喷泉码技术便推向了具体应用[9]，目前，一种系统喷泉码已被3GPP组织的多媒体广播多播业务 (MBMS, Multimedia Broadcast Multicast Service)标准所采用[10]。本文设计的基于喷泉码的分布式存储系统便采用了LT码。

图1 LT码编码示意图

LT码原理

1.LT码编码过程

将信源文件划分为k个输入文件块。译码开销(overhead)定义为N/k-1，其中，N是接收端接收的编码块的数目，编码过程如下，示意图如图1所示。

（1）首先由节点的度分布函数产生一个度值d；

（2）均匀随机地从k个输入文件块中选取d个文件块；

（3）将选取的文件块进行二进制异或运算，得到编码块；

（4）重复上述3个步骤N次，得到N个编码块。

2.度分布

度分布的设计是LT码的关键，为了高效可靠译码，Luby首先提出了理想孤波度分布(ISDD, Ideal Soliton Degree Distribution)，表达式如下：

其中，k为原始文件划分为文件块的数目，p(d)为选择度为d的概率。在ISDD下，编码块节点度平均值约为lnk，这种度分布在实际中工作表现不佳，度为1的节点概率约为1/k，但在实际译码过程中的波动会导致没有度为1的编码块，从而导致译码终止。针对这些不足之处，Luby引入了两个额外的参数c和δ，构成鲁棒孤波度分布(RSDD, Robust Soliton Degree Distribution)。首先，定义

3. LT码译码原理

LT码在删除信道下的译码包括置信传播 (BP，Belief Propagation) 译码算法和极大似然 (ML，Maximum Likelihood) 译码算法。

（1）置信传播译码算法

接收端收到N个编码块后（N稍大于k），即有可能完成译码，恢复原始文件。假定k个输入文件块分别表示为S1，S2，. .. ，Sk，接收的N个编码块分别表示为Y1，Y2，. . . ，YN，译码过程如下：

图2 LT码BP译码过程示例

a.首先找到度为1的编码块Yi，将其赋值给它连接的输入文件块，即St=Yi；

b.找出与输入文件块St连接的编码块进行异或运算，并将所有与St相连的边删除，也就是将G矩阵中相应位置零；

c.再次寻找度为1的编码块，返回步骤a，直到所有输入文件块被恢复。如果没有度为1的编码块，则译码停止。

LT码的译码过程可以用二部图(Bipartite Graph)表示，下文列举了一个简单示例，并称输入文件块为变量节点，编码块为校验节点，不失一般性，假定每个块只包含1比特信息，如图2所示。图2(a)中的校验节点信息为0110。在第一次迭代中首先找到度为1的校验节点：第一个校验节点Y1。将Y1赋值给与其相连的变量节点S1，删除两节点的边，如图2(b)。并找到与S1相连的校验节点，对其进行异或操作，并删除所连接的边，如图2(c)。重复步骤1，找到度为1的校验节点，并将其赋值给与之相连的变量节点，如图2(d)。重复步骤2，将变量节点S2的值与其相连的校验节点异或，删除连接的边。最后，如图2(e)，重复步骤1、2将S3恢复。最终如图2(f)所示，恢复出的变量节点信息为001。

如果在译码过程中找不到度为1的校验节点则译码停止[7,8]，此时如果原始文件仍不能完全恢复，则需要继续接收更多编码块进行译码，直到译码成功为止。实际中，当输入文件块k约为10000时，LT码译码成功所需译码开销大约在5%[4]，因此，BP译码算法适合于大型文件的恢复。

（2）极大似然译码算法

删除信道下，将线性分组码进行极大似然译码的本质是求解线性方程组，求解的过程可以通过高斯消元法 (GE，Gaussian Elimination) 实现。LT 码的GE译码算法性能优于BP译码算法，但是，GE 译码算法复杂度O(k3)远高于 BP 译码算法复杂度O(klogk)。因此，当输入块较少时采用GE译码算法是可行的[10]。即时高斯消元 (OFG，On the Fly Gaussian Elimination) 译码算法是实现 GE 译码的一种有效算法，进一步将复杂度降低为O(k2)[11]。本文设计的分布式存储系统在存储小型文件时采用OFG译码算法恢复原始文件。表1和表2给出了BP和OFG译码算法在不同译码开销下的文件错误率(FER, File Error Rate)即原始文件译码失败概率，其中，原始文件大小k分别为200和1000，度分布采用了参数为c=0.03，ε=0.5的RSDD。

表1 k=200时BP和OFG译码性能比较

表2 k=1000时BP和OFG译码性能比较

由表1和表2可以看出，随着原始文件划分数目k的增加，在相同译码开销下，BP译码算法和OFG译码算法的性能都得到了改善。但是，当原始文件数目划分较少时，如k为200或1000时，在相同译码开销下，OFG译码算法的FER明显低于BP译码算法，其性能至少相差一个数量级。

喷泉码与副本存储性能比较

将原始文件分为k个文件块，副本存储和喷泉码存储都采用三倍冗余方式。假定其中任意一个文件块失效的概率为ε(0＜ε＜1)，对于副本存储而言，若副本存储中任意一个文件块的三份备份全部失效则整个文件无法恢复，表3给出了k为200和1000时，不同删除概率(即文件块失效的概率)下的FER仿真结果：

由表3可以看出当k=200和ε=0.3时，三副本存储方式的FER接近1。对于喷泉码方案而言，当ε=0.3时，可用于译码恢复原始文件的编码块数目为420，即译码开销为2.1。由表1可知当译码开销为0.3时，OFG译码算法的FER为0.008，因此，当译码开销为2.1时，其FER远低于10-3。由以上分析可知，喷泉码存储可靠性远优于副本存储。k为200和1000时的仿真结果表明，随着k的增加，副本存储方案的性能变差，如ε=0.2和k=200时，三副本存储方式的FER为0.788，当k增加到1000时，其FER增加到1。对于喷泉码存储方案则不同，当k越大时，其译码性能越好。

表3 三副本方案下不同删除概率的FER

得到上述结果的原因是喷泉码产生的编码块地位完全等同，即不存在先后顺序的问题，并且编码块的重要程度相同。编码块建立了参与编码的文件块之间的联系，取消了各个文件块的独立性。将这个特性引入存储系统之后，即使存储系统存在一部分编码块的损毁，用户只需要获取足够数量的编码块就能通过译码恢复原始文件块，而不必精确恢复丢失的编码块。在传统分布式存储系统中，当某一文件块的全部副本损毁后，由于文件块不完整则导致整个文件恢复失败。因此引入喷泉码可以提高整个系统的存储可靠性。

时间复杂度分析

副本存储方式是原始文件块的镜像复制，不需要编译码过程。喷泉码编码一个文件块的复杂度为O(logk)，GE 译码算法复杂度O(k3)远高于 BP 译码算法复杂度O(klogk)。即时高斯消元(OFG，On the Fly Gaussian Elimination) 译码算法是实现 GE 译码的一种有效算法，进一步将复杂度降低为O(k2)[11]。为了进一步说明译码时间复杂度，分别对BP和OFG译码时间进行统计，得到译码平均时间见表4，其中，原始文件大小k为 1000，RSDD参数与2.3.2节相同，时间单位为秒(s)。

表4 k=1000时BP和OFG译码时间比较

系统设计

兰州大学校园已实现IPv6全覆盖，本文设计的存储系统依托兰州大学IPv6网络环境，存储节点分别位于本部校区的飞云楼、网络中心和榆中校区图书馆。这样就实现了不同教学楼和不同校区之间的分布式存储，通过异地存储提高数据的安全性。系统部署方案如图3所示。

本实验平台为基于喷泉码的分布式存储系统，该系统由6台PC级存储节点、一台客户端节点和一台服务器节点组成。每个存储节点的配置为：英特尔Core i5-8400 @ 2.80GHz 六核CPU，镁光8GB DDR3内存，希捷ST2000DM006-2DM164 4TB硬盘，主板集成的千兆以太网网卡，Windows 7 64位操作系统。服务器端配置为：英特尔 Core i7-8700k @ 3.70GHz六核CPU，金泰克16GB DDR4内存，希捷ST2000DM006-2DM164 2TB硬盘，主板集成的千兆以太网网卡，Windows 7 64位操作系统。客户端配置为：AMD Ryzen 7 1700 Eight-Core Processor 八核CPU，金泰克16GB DDR4内存，主板集成的千兆以太网网卡，Windows 7 64位操作系统。

图3 系统部署方案

整个系统测试的基本流程可分为以下几个步骤：

1.基于IPv6环境在兰州大学本部飞云楼、网络中心和榆中校区图书馆各放置两台存储PC节点，客户端和服务器位于兰州大学本部校区飞云楼内；

2.选择125MB大小的MKV格式的视频文件（其代表一个小型文件）和 1.5GB大小的Zip压缩格式文件（其代表一个大型文件）分别进行3倍冗余LT编码；

3.客户端向服务器请求文件存储，服务器选择合适的存储节点并通知客户端向存储节点存放合适大小的编码块文件；

4.客户端向服务器请求下载编码块文件，服务器依据一定的路由选择算法从离客户端由近及远的存储节点进行下载；

5.客户端下载一定数量的编码块后，根据文件大小采用合适的译码算法恢复原始文件，若译码失败则继续下载额外的编码块再次进行译码，直到译码成功为止。

LT码编码模块

存储的LT码编码数据相比于编码块多了4个字节的种子(Seed)信息，伪随机数生成算法利用种子来产生编译码所需要的度和编码块的生成向量。种子信息和编码块存放在不同文件中。其中每个种子信息占4B，每个编码块数据占128KB。由于喷泉编码只进行异或操作，所以编码块与原始文件块大小相同。度分布函数采用RSDD，其参数为c=0.03，ε =0.5。

设计的LT码编码步骤见表5：

表5 LT码编码步骤

LT码译码模块

本文设计的系统涉及到BP译码模块和OFG译码模块，分别描述见表6、7。

本系统的译码过程具体设计为：首次译码时，先下载1.05×k个编码块完成译码，如果无法成功译码，则再每次下载0.05×k个编码块再次译码，直到恢复原始文件为止。

表6 LT码BP译码步骤

表7 LT码OFG译码步骤

关于本系统大小文件的划分：原始文件划分块数k小于5000(即625M)视为小型文件，采用OFG译码算法，否则视其为大型文件，采用BP译码算法。根据4.1节提到的编码块大小为128KB，则125MB大小的mkv文件划分为1000个文件块，视为小型文件，采用OFG译码算法。1.5GB的zip文件大约可分为12288块，可视为大型文件，采用BP译码算法。

系统主要组成单元功能描述

服务器的功能包括：1.利用数据库完成文件信息的组织和记录，本系统采用的数据库模块为Qt支持的SQLite数据库，其生成的db文件可以保存文件信息，如文件名、类型和大小等；2.根据最短路径优先准则选择合适的存储节点并通知客户端；3.负责记录编码块文件的种子信息文件。

当客户端需要存储文件时，首先选择文件并进行LT编码，然后，通过TCP协议将适量的编码块文件传输到服务器选择的存储节点，并将相应的种子信息文件保存到服务器。当客户端需要下载文件时，首先从服务器获知存储节点的IPv6地址，并下载相应种子文件信息，其次，通过TCP协议将适量的编码块文件下载到客户端，最后依据原始文件大小选择相应译码算法并恢复原始文件。

客户端实现

Qt是一个跨平台应用程序和UI开发框架。本系统基于Qt开发的客户端界面主要包括打开文件按钮、喷泉编码按钮、存储按钮、删除按钮、下载按钮、译码按钮和文件信息列表，如图4所示。完成的功能有对文件进行LT编码、存储、下载、译码恢复和删除操作。客户端IPv6地址为2001:da8:c000:2021:3925:cfa4:bdbb:18da。

图4 系统客户端界面

程序启动后客户端首先与服务器交互信息，获得服务器上存储的文件信息列表，并将其显示在客户端文件信息列表中。当客户端需要存储文件时，首先选择文件进行LT编码。其次，点击存储按钮与服务器通信，将种子信息文件保存在服务器，编码块文件则保存在服务器选择的存储节点中。当文件存储完成后，其信息会显示在文件信息列表。当客户端有不需要的文件时可以将其删除，但是，只能删除自身上传的文件。当文件译码成功或被删除时，其信息也将从信息列表删除。当客户端需要下载文件时，首先从文件信息列表选择文件，点击下载按钮，服务器返回存储节点的IPv6地址和相应的种子文件信息，客户端从存储节点下载编码块文件。客户端拥有编码文件后即可进行译码恢复原始文件。当译码失败时，继续请求服务器下载种子信息文件和编码块文件，再次进行译码，直到译码成功为止。每次完成存储、删除和译码操作后，服务器向客户端发送XML文件用以更新文件信息列表。

本文在IPv6网络中设计实现了基于喷泉码的分布式存储系统，该系统在相同存储开销下，相比于副本存储的系统进一步提高了信息存储的可靠性，在相同可靠性下降低了存储空间的使用，提高了空间利用率，但是也相应地增加了编译码的时间开销。进一步的研究方向为：可以对一些访问频度高的热数据采用副本存储的方式，对一些访问频度低的冷数据采用喷泉码存储方式。