基于Raptor 码的可靠云存储服务∗

马玲玲 张功萱

（南京理工大学计算机科学与工程学院 南京 210094）

1 引言

随着云计算技术的普及，其上衍生出来的新兴网络存储技术——云存储也越来越受到人们的关注和欢迎。个人及企业越来越多地倾向于将信息从本地移动到云存储中，使用者可以不受地域，时间，设备的限制，方便地从云上获取或存储数据［15］。但同时云存储也带来了很多安全隐患：首先为了实现成本效益，云存储服务提供商一般将所有的用户数据集中存储，通过应用软件来协调配合但缺乏高安全系数的数据隔离和API 控制措施，攻击者能够通过公共访问接口窃取存储信息；第二，分布在不同地区和环境中的物理存储设备很可能会发生宕机，硬件损坏，软件故障等问题，这样就会导致该存储设备中的数据不能访问，严重地会导致数据永久丢失［1］。因此基于以上两点，云存储服务提供商需要对存储的每一个数据块都添加良好的保密措施以防止信息泄露，同时为了应对某个服务器出现不能使用的状况，需要有良好的容错能力。

1998 年，John Byers 和Luby 等首次提出了“数字喷泉”的概念，主要是为了传统“抹除信道”上的大规模数据分发而设计的。在实用的数字喷泉码LT 码和Raptor 码提出后，它的学术理论日渐完善并且被应用到越来越多的领域，比如无线网、移动网的流媒体点播或广播，广域网上的高速大文件传输以及深空通信等方面。但是由于它的可译码性不是绝对的百分之百等的问题，数字喷泉码很少被应用到分布式存储中的数据编码，少量的研究该方向的文献也只是讨论了数字喷泉码在编译码效率和节省空间等方面的优势。

因此本论文将研究如何把Raptor 码应用到分布式存储中：利用Raptor码的优势提出分布式文件存储架构，解决云存储中容易出现的信息泄露和容错能力差的问题；针对译码中可能出现的“最后一块”问题提出反馈机制，提高译码效率并使得译码概率无限接近于1。

2 相关算法和技术

2.1 Raptor码编码

喷泉码也称为无率码，顾名思义就是码率不需要事先确定。喷泉码将原始文件划分为一定数量的数据包，再通过数据包编码出任意数量的有效编码包。当发送端传送该数据时，只要接收端收到稍大于原始数据包数量的编码包子集，就能够还原原始数据［11］。这在有损连接的场景中是非常高效的传输数据的方式。因为在传输过程中，接收端不需要知道丢包率是多少，也不需要反馈接收到的数据包的情况。在“数字喷泉”概念提出之后，Luby 实现了第一种实用的数字喷泉码——LT码。针对LT码的不足，Shokrollahi又在LT码基础上提出了Raptor 码，其在编译码效率以及译码成功率上有了很大的改进，几乎达到理想的编译码性能。

Raptor 编码过程由预编码和LT 编码组成，假设目前原文件M 需要经过Raptor 码进行编码。编码过程［6］如下：

1）预编码：把原文件M 均分为k-n 个分组，将k-n 个输入单元通过某种传统的纠删码（如：LDPC码）转换为k个中间编码校验单元。

2）LT编码过程

输入：k 个数据包x1，x2… xk，度分布函数ρ(d)

输出：s个编码包y1，y2… ys

定义：编码包的度d为一个编码包包含的原始数据包的数量

（1）通过弱化的鲁棒孤波分布确定度分布ρ(d)

（2）根据度分布ρ(d)得到数值d，1 ≤d ≤k

（3）在k 个数据包中随机均匀地选出d 个数据包

（4）将选出的d 个数据包进行异或运算，输出一个编码包

（5）重复（2）～（4）步骤产生s 个编码包，s 值根据信道质量而定

2.2 Raptor码译码

Raptor 译码主要用两种方法，第一为编码的逆过程，利用LT 解码技术恢复出一定比例的中间编码校验单元，再使用对应纠删码的译码方法恢复出原始数据块。第二为定义内码和外码中符号间的关系来直接恢复原始数据，例如高斯消元法求解的联立方程。本论文所提的模型会针对LT解码时的效率做出优化，因此只讨论第一种译码方法。

1）LT喷泉码的解码过程（置信传播译码）

（1）根据接收到的一定数量的编码包重建数据包和编码包的双向图。

（2）找到一个度为1 的编码包，若存在，则通过复制运算便可求得与之相连的数据包。若不存在，则译码停止或继续接收编码包直到找到。

（3）将已经恢复的数据包和与之相连的编码包进行异或操作，同时在双向图中把该数据包与此编码包相连的边删除，对应的编码包度数减1。

（4）重复步骤（2）和（3）直到恢复所有的数据包。

图1 LT解码过程示例

2）使用对应纠删码的译码方法恢复出原始数据块。

2.3 Raptor码度分布

2.3.1 LT码度分布

LT 码的加密过程可以产生无限的编码包，都是通过原始数据包的子集进行异或运算得到的。而编码过程中的度分布直接影响到最终是否能够成功解码以及解码的复杂度，所以度分布的设计是LT 喷泉码的关键。优秀的度分布能够使接收端以尽可能少的编码包冗余，较低的解码复杂度高概率地恢复出原始的数据包。在编解码的过程中，优秀的度分布设计需要平衡两个方面。第一，应使编码包的平均度数尽可能小以此降低解码复杂度，但是又必须选取一定量较大的度以此来确保所有的输入数据包都能够参与到编码过程中。第二，在解码的过程中，度分布设计必须保证每次迭代后都有度为1 的输出编码包以确保解码不会被迫停止导致解码失败，但是太多度为1 的编码包会导致解码过程过快而产生太多的冗余，尤其是将LT 码运用到分布式存储中时，度为1 的个数太多会使LT 喷泉码失去它在安全性，低冗余性方面的优势。

1）理想孤波分布

Luby在提出LT喷泉码的初期提出了理想孤波分布［2］（ISD），表示为ρ(i)，即P{d=i}。

此时编码包的平均度数为ln k ，但是在实际使用中几乎不会用到这种度分布方式，因为随机数产生的值很难实现均匀分布，有一定的概率会使得度分布出现浮动，这就很可能会导致在解码过程中不能出现度为1的编码包从而解码失败。

2）鲁棒孤波分布

Luby 之后提出了鲁棒孤波分布［2］（RSD）去修正理想孤波分布带来的不足。

定义：常数c＞0，允许的最大的解码失败概率δ ∈[0，1]，令R=c ln(k/δ)

度分布：μ(i)=( )ρ(i)+τ(i) β i=1，2，…k

由以上度分布公式可得编码时间复杂度为O(ln(k/δ))，解码时间复杂度为O(k ln(k/δ))。

2.3.2 Raptor对度分布的改进

上述鲁棒孤波分布实现了较好的改进，但为了良好的覆盖率，少量的编码包有很高的度，这会升高编解码复杂度，降低解码成功率。Raptor 码的两步编码方式正是针对此提出的思想。Raptor 码在LT 编码阶段采用了弱化的度分度，即减小度的上限值，这样就会增大连接度小的编码包的概率。在译码的时候，先使用BP 译码解码出绝大部分中间编码校验单元，再通过传统的纠删码恢复出原始文件。因此Raptor码有更低的编解码复杂度，且在相同译码开销下译码成功率更高。

3 基于Raptor 码的分布式存储架构及其可行性分析

3.1 基于Raptor码的分布式存储架构

云存储架构仿照Google 的GFS 分布式文件系统搭建，一个控制节点，若干个存储节点以及若干个用户。1）控制节点存储元数据，包括文件的命名空间，数据块的命名空间，解码所需的双向图，文件到块的映射，块当前的位置等。控制节点与客户之间没有文件内容的交互传输，这能避免控制节点成为整个系统的性能瓶颈；2）客户节点需要安装使用云存储服务所需的客户端应用，由云存储服务供应商提供。上传文件和请求文件时直接与云存储节点传输文件的具体内容；3）云存储节点负责存储用户的数据块，受控制节点的调度，当出现异常状况时会向控制节点汇报。控制节点也会定时监测云存储节点数据块的状况，包括当前数据块的位置，是否存在错误等

图2 基于Raptor码的分布式存储架构

文件上传：客户端使用软件应用进行Raptor编码之后把文件名，块索引以及Raptor编码双向图加密传送给控制节点，控制节点加密存储Raptor码双向图并返回数据块句柄及位置给客户节点，然后客户节点直接查找云存储节点的位置，根据控制节点反馈的信息将数据块传送到对应的云存储节点上。

文件请求：客户端向控制节点发送文件请求，告知请求文件的名称，控制节点查找到对应的解码双向图通过加密的方式传送给客户端，并通过设定的规则查找到符合条件的数据块句柄通知云存储节点将数据块传送给客户端，客户端进行Raptor解码。

双向图以Tanner图的形式存储，例如：

x:中间编码校验单元 y:编码包

3.2 基于Raptor 码的分布式存储架构可行性分析

1）系统容错性能：当前商用云存储架构为了提高系统的容错性，一般通过引入冗余技术实现的，常用的两种冗余容错技术为：副本和纠删码技术。因此本文将这三种技术的容错性进行对比。

定义冗余度为采用容错技术后所需的存储空间与原始数据所需的存储空间的比值。在云存储中原始数据都会被划分为固定大小的数据块，而这三种容错技术都不会改变单个数据块的大小，因此我们设定k个原始数据块经过容错技术后产生n个数据块，最多允许t个数据块失效。则冗余度为

三种技术产生的数据块需满足以下条件：

副本技术：

纠删码技术：

Raptor码技术：

（e 与译码失败率和n大小相关）

Raptor 的最新版本——RaptorQ Codes 能够在接收到稍大于k 个编码包的情况下编码失败率低于10-6。并且随着接收到的符号个数的增长，编码成功率将无线接近于百分之百。设定t为10。

图3 相同容错性下数据包与编码包关系

由图3 可得，副本技术的冗余度成线性增长，纠删码和Raptor 码的冗余度相比于副本技术低很多。

2）编解码复杂度

Raptor码：

O(k ln(1/ε))（ε 是译码开销）

常见的RS纠删码：

副本技术：0

图4 解码复杂度与数据包关系

从图4 中可以看出因为副本技术不需要编解码，所以在编解码复杂度上占绝对优势，也正是因为这个原因云存储服务商还是以副本技术为主。Raptor 编解码复杂度比RS 纠删码低很多，尤其是当k 逐渐增大时纠删码的编解码速度会快速减慢，Raptor码相比于纠删码的优势会更明显。

3）数据机密性

本文单从以上三种编码技术本身来讨论它们对保证数据机密性的贡献。

副本纠删码Raptor码攻击存储节点使得数据泄露伪造客户请求获得原始数据1 1 1 1 0 0

Raptor 编码过程是根据度分布随机选取原始数据块异或得到编码块，因此会改变原始数据的内容，即便攻击者攻破云存储节点获得存储的数据块，也无法得知具体的内容。尽管纠删码的校验数据块也是通过编码获得，但是原始数据块仍然保留在存储设备中，这就跟副本技术一样，攻击者容易从存储节点找寻弱点来窃取数据。

Raptor 是根据双向图来译码的，所以如果以高安全系数的加密方式存储双向图（如：可信安全芯片TCM［4，7］），即便攻击者伪造客户请求获得所有的编码数据块，也无法恢复原始的数据。但是副本技术和纠删码技术就不能达到这方面的安全性要求。

4 基于反馈的Raptor译码优化

将Raptor码用于分布式存储中存在一个问题，即控制节点接收到用户请求后选取哪些编码包来译码。我们需要保证能够译码，还要尽可能减少译码开销和减少系统调度开销。

图5 Raptor编码分析图（由上到下为数据包，中间编码校验单元，编码包）

因此本文根据译码的流程提出了基于反馈的Raptor 译码优化。设定原始文件均分为k 个数据包，经过预编码产生k+m 个中间编码校验单元，再经过LT 编码产生2k 个编码包。LT 译码过程需要译码出≥k 个中间编码校验单元才能恢复原始数据。

之所以设置2k（副本技术一般存储3k 个数据包）个编码包是因为尽管Raptor 码接收到稍大于K个编码包恢复出原始数据的失败率很低但也不是绝对的百分之百，如果用在分布式云存储上这很低的概率也可能会导致用户数据永久丢失。此外也是为了提供一定的容错能力，由于我们不知道云存储节点的故障率是多少，所以为了研究方便我们设置存储2k 个编码包使得解码成功率无限接近于百分之百同时也保障了足够的容错性能。但是如果在译码时收集所有的编码包并进行译码，不仅会增大系统调度开销，也会使得编码包冗余度增大从而增加译码开销，因此本文设定控制节点只调度最近的k（1+σ）σ ≥0 个编码包，如果LT 译码环节成功译码出大于等于k 个包，就向控制节点反馈成功信息，如果没有达到最低标准，就向控制节点反馈未译码出的中间编码校验单元。以下就详细分析未达到译码要求时的情况。

定义：（中间编码校验单元简称：中间单元）

已译码出的中间单元集合：φ(x)

未译码出的中间单元集合：ϕ(x')

已收集的编码包集合：η(y)

未收集的编码包集合：μ(y')

待发送编码包集合：ℓ(y)

译码流程如下：

调度k（1+σ）个编码包到客户端进行译码；

将译码出的中间单元都加入φ(x)集合中；

未译码出的中间单元都加入ϕ(x')集合中；

while（size（φ(x)）＜k）｛

for（i：ϕ(x')）｛

在Tanner图中定位该中间单元对应的列；

筛选出符合条件的编码包集合Y ，异或产生该类编码包的中间单元集合X 定义为{x|x ∈φ(x)，且x ∉(ϕ(x')-i)，且一定包含当前i}

if（找到符合条件的Y）｛

从Y 中选出最近的一个编码包加入待发送列表ℓ(y)；

｝//if end

｝//for end

将ℓ(y)中的编码包一起调度发送给客户端并继续进行LT译码迭代；

将新译码出的中间单元添加到φ(x)中；

从ϕ(x')删除新译码出的中间单元；

｝//while end

进行纠删码的译码过程；译码结束；

基于反馈的Raptor译码示例：

Tanner图如下：

假定控制节点调度给客户端的k（1+σ）个编码包为y1，y2，y3，y4，y5，LT 译码过程至少要解出5个中间编码校验单元。由图可知能够译码出x1，x2，x3中 间 编 码 校 验 节 点。可 得φ(x)={x1，x2，x3} ，ϕ(x')={x4，x5，x6} ，η(y)={y1，y2，y3，y4，y5} ，μ(y')={y6，y7}

迭代之后的Tanner图为

客户端向控制节点反馈ϕ(x')，控制节点到编码包集合ϕ(x') 中依次选择中间编码校验单元x4，x5，x6，到 μ(y') 中 查 找 符 合 条 件 的 编 码 包，y6和y7都满足除了x4之外的中间编码校验单元都已经被译码得到。控制节点选择最近的编码包（设定为x6）传送给客户端继续迭代过程，能够译码出ϕ(x')={x4，x5，x6}中所有的单元，译码结束。

5 仿真结果及分析

仿真实验1：设定度分布参数c=0.2，δ=0.1，取原始数据包个数分别为k=80，200，400，每个包大小为0.5M。根据本文提出的基于Raptor 码的分布式存储架构进行仿真实验，基于反馈的Raptor码译码开始时客户端只接收k 个原始数据包，将此解码冗余度与用于“抹除信道”传输时的Raptor 冗余度相对比。

图6 两种译码方式下冗余度和译码成功率关系（实线：基于反馈虚线：基于抹除信道）

图中虚线为用于“抹除信道”传输时的Raptor冗余度，实线为用于分布式存储时的Raptor 冗余度。由仿真结果可得采用本文提出的译码方式在接收到1.1k个编码包时，译码成功率就达到95%以上，且k 越大，译码成功率越高。相比于虚线所示的冗余度，该方法有了很大的改进。

仿真实验2：根据本论文提出的基于Raptor 码的云存储架构，测量客户从发送文件请求到接收文件成功所需要的时间。我们从仿真实验1 中可看出，如果不进行反馈，冗余度大概在1.5的时候才能以很高的概率成功译码。因此我们将以下两种情况做对比：1）采用本文提出的基于反馈的Raptor码译码，测量客户发送文件请求到译码成功的时间；2）译码过程不发送反馈，测量客户发送文件请求到客户端接收到1.5k个编码包并译码结束的时间（此种情况下小概率会译码失败，为了测量方便当出现这种情况导致译码停止时，则测量到译码停止的总时间）。原始数据包个数仍为k=80，200，400，每个包大小为0.5M，实验的网速为1M/s。在针对每个数据测量时，我们取10 组同等大小不用内容的文件进行测量再取平均值得到。

图7 两种方式下用户请求文件响应时间

用户请求文件的总时间包括控制节点、客户端节点、存储节点之间沟通的时间，编码包传输的时间，以及译码的时间。理论分析上，基于反馈的译码方式比不反馈节省了一部分编码包传输的时间，多了节点之间沟通的时间。从仿真结果看，编码包传输的时间占总时间的很大一部分，所以基于反馈的译码方式比不反馈的节省了很大的时间开销。

6 结语

本文针对分布式云存储环境中存在的一些问题提出了基于Raptor码的可靠云存储服务，并改进了分布式环境中Raptor 的译码方式。经过分析Raptor 码在编解码效率，容错性以及安全性上相比于传统的分布式存储技术有很大的优越性。并且根据仿真结果得出，改进的基于反馈的Raptor译码在译码开销和整体的用户时间上都有很大的减少。综上，将以上改进的Raptor码应用与分布式云存储上有较高的实践价值。