随着云存储的不断发展，越来越多的企业和用户选择将数据和应用从本地转移到远程云服务器^[1]，这逐渐成为了未来信息存储的主流趋势，如Google每月有超过400 PB的数据存储到分布式文件系统（Google file system, GFS）中^[2]，Facebook每天有超过500 TB的数据存储到Amazon的云端^[3]。而在实际应用中，数据损坏的情况不可避免^[4]，在2015年8月20日，Google位于比利时布鲁塞尔的数据中心遭雷击，造成电力系统供电中断，导致数据中心磁盘损坏和云存储系统断线，部分数据永久丢失^[5]。因此，在云存储系统中数据出现损坏情况时需要准确快速地进行损坏数据的探测，进而有针对性地进行数据恢复工作^[6]。除此之外，原始文件更新也是现实的需求，在云存储系统中不仅要实现动态更新功能，还要确保远程云服务器能够实时对原始文件进行更新^[7]。

在现有方案中，云存储的损坏数据探测过程和动态更新的计算开销和通信开销往往与云存储服务器中数据块数量呈线性增长关系，这也会给第三方服务器和云存储服务器带来非常大的计算开销和通信开销，而且还会限制方案的可拓展性，无法满足用户数据存储快速增长的需求。文献Cao^[8]、李力^[9]等提出了基于逐一验证标签的云存储方案，该方案的每个存储服务器都有一个聚合标签，通过一一验证聚合标签确定损坏数据块所在的服务器，再在该服务器里逐一探测损坏数据。但是，该方案的计算和通信开销会随着服务器数量和每个服务器内数据块数量呈线性增长，且不支持数据的动态更新。Erway等^[10–11]提出了基于认证跳跃表的云存储方案，该方案的数据块对应跳跃表的底层节点，通过验证根节点与验证路径上的节点探测损坏数据块，支持数据动态更新。但是，在探测损坏数据过程中，验证路径较长，且每次验证过程中需要大量的辅助信息支持，使得计算开销与通信开销增大。Zheng^[12]和Ren^[13]等提出了基于值域2～3树的云存储方案，该方案采用了数据结构比认证跳跃表简单的值域2～3树，通过验证聚合标签探测出损坏数据块，且支持数据动态更新，但是，值域2～3树的结构仍较为复杂，两个叶子节点数量相同的树可能结构不一样，导致树的生成时间较长，而且每个云存储服务器都有一个值域2～3树，在探测损坏数据时，需要一一验证每个树的聚合标签，消耗时间较多，效率不高。

针对上述问题，在已有工作的基础上，基于LT编码设计了两级分布式二叉树的云存储方案以进行损坏数据探测与动态更新。在分布式云存储中，由于存储节点之间的带宽和通信负载可能会成为瓶颈，需要采用恢复时具有较少通信开销的编码，特别是当一个节点发生故障，且需要进行数据探测时，LT码能高效地执行数据探测与更新操作，而且整个过程中的通信开销和计算开销都比较小。该方案通过对探测数据建立两级分布式二叉树结构，确保了探测过程中的数据冗余量最小化和验证结构可扩展性，从同态技术出发，将探测数据作为叶子节点，利用BLS（Boneh–Lynn–Shacham）签名的聚合特性，将所有探测数据的验证标签进行聚合得到根节点的聚合标签值，验证根节点的聚合标签值是否正确，若正确则证明探测数据无损坏，反之则证明探测数据存在损坏情况，再通过两级分布式二叉树探测出损坏数据块。除此之外，利用LT码的编码性质，实现了数据动态更新，数据用户通过从云存储服务器得到的部分两级分布式二叉树来计算更新后根节点的聚合标签值，再与云存储服务器更新后得到的根节点聚合标签值进行比较，若相同则证明云存储服务器执行了数据更新操作，反之则证明未执行数据更新操作。实验分析与结果表明，相比于现有方案，该方案在存储开销相当的情况下，有效地减少了计算和通信开销，显著提高了损坏数据探测的效率。

1 问题描述 1.1 系统模型

在云数据存储服务中，包含3类实体：数据用户、云存储服务器、第三方服务器，如图1所示。

1）数据用户。数据用户先将文件 $F$ 进行分块；然后，基于LT码进行编码，并对其进行签名；进而，将编码数据包和验证标签分发到 $n$ 个云存储服务器。如果数据用户需要保护数据内容的机密性，可以在文件编码前先进行加密。编码数据包分发后，数据用户可以随时进行数据的动态更新。

2）云存储服务器。云存储服务器主要负责编码数据包的存储和管理。在损坏数据探测过程中，云存储服务器构建两级分布式二叉树，并将相应的聚合符号和聚合标签发送到第三方服务器，以此判断损坏数据块。在数据动态更新过程中，云存储服务器将待更新的数据块和相应的编码数据包发给数据用户，待数据用户更新数据后，云存储服务器更新相应的编码数据包。

3）第三方服务器。为了减轻数据用户实时在线与有限计算资源的负担，数据用户可以与第三方服务器进行协商，将损坏数据探测任务委托给第三方服务器进行。当数据出现损坏情况时，第三方服务器探测出损坏的数据块，通知云存储服务器进行损坏数据块的修复，同时，将结果报告给数据用户。

1.2 预备知识

介绍在文件处理的过程中用到的LT编码以及签名的相关知识。

1）LT码编解码原理

LT码^[14]的一个特点是在编码过程中，可以生成无限数量的编码数据包，而每个编码数据包都是根据LT码的RS度分布，通过对一定数量的原始数据包进行XOR运算来产生。在解码时，LT码以 $1 - \delta $ 的概率可以从任意 $m + O\left( {\sqrt m {{\ln }^2}\!\left( {m/\delta } \right)} \right)$ 个编码数据包中恢复出 $m$ 个原始数据包，其复杂度为 $O\left( {m\ln\! \left( {m/\delta } \right)} \right)$ 。与编码分组相关联的原始数据分组数被称为该编码的度，用 $d$ 表示，在LT码中，度分布是由理想弧波分布和鲁棒弧波分布决定的。假设理想弧波分布为 $\rho \left( i \right)$ ，那么 $\displaystyle \sum\limits_{i = 1}^m {\rho \left( i \right)} \!\!=\!\! 1$ ，且 $\rho \left( i \right) \!=\! P\left\{ {d = i} \right\}\!\!=\!\! \left\{ {\begin{aligned}&{1/m,}\quad\!\!\! {i = 1;}\\&{1/i\left( {i - 1} \right),}\quad\!\!\! {i=2,3, \cdots, m}{\text{。}}\end{aligned}} \right.$ 假设鲁棒弧波分布为 $\mu \left( i \right)$ ，那么， $\mu \left( i \right) = \left( {\rho \left( i \right) + \tau \left( i \right)} \right)/\beta $ ，其中， $\beta = $ $\displaystyle \sum\limits_{i = 1}^m {\rho \left( i \right) + \tau \left( i \right)} $ ，令 $R = c \cdot \ln \!\left( {m/\delta } \right)\sqrt m $ ，则

$\tau \left( i \right) = \left\{ {\begin{aligned}&{R/im,}\quad {i= 1,2, \cdots ,m/R - 1;}\\&{R\ln\!\left( {R/\delta } \right)/m,}\quad {i=m/R;}\\&{0,}\quad {i=m/R + 1,2, \cdots ,m}{\text{。}}\end{aligned}} \right.$

2）计算Diffie-Hellman问题（computation Diffie-Hellman, CDH）

给定任意的整数 $a,b \in {\textit{Z}}_q^*$ ，以及 $\left\langle {g,{g^a},{g^b}} \right\rangle $ ，计算 ${g^{ab}}$ 。

3）双线性映射

设 ${G_1}{\text{、}}\!\!\!{G_2}$ 是两个阶为大素数 $p$ 的乘法循环群，定义双线性映射为 $\hat e:{G_1} \times {G_1} \to {G_2}$ ，并满足以下性质：

①可计算性。对于任意的 $P,Q \in {G_1}$ ，存在有效算法易于计算 $\hat e\left( {P,Q} \right)$ 。

②双线性。对于任意的 $P,Q \in {G_1}$ ， $a,b \in {\textit{Z}}_p^*$ ，满足 $\hat e\left( {{P^a},{Q^b}} \right) = \hat e{\left( {P,Q} \right)^{ab}}$ 。

③非退化性。存在 $P,Q \in {G_1}$ ，使得 $\hat e\left( {P,Q} \right) \ne 1$ 。

2 方　案

详细介绍作者提出的基于LT码的损坏数据探测技术与动态更新技术，其中， $n$ 台存储服务器 $\left\{{S_1},{S_2}, \cdots , \right.$ $\left.{S_n}\right\}$ 用于为数据用户提供数据存储服务，本文的数据签名技术参考了BLS签名技术^[15]。

2.1 参数设置

设 $e:G \times G \to {G_T}$ 为双线性映射，其中， $g$ 为 $G$ 的一个生成元，BLS哈希函数为 $H:{\{ 0,1\} ^*} \to G$ ，数据用户先产生一个随机数 $\eta \leftarrow {{\textit{Z}}_P}$ 作为密钥 $sk$ ，再计算公钥 $pk \leftarrow {g^\eta }$ 。

2.2 基本思路

基于LT码的损坏数据探测技术的主要步骤包括：

1）密钥生成算法 $\left( {pk,sk} \right)$ 。由数据用户执行，输入为安全参数 $\kappa $ ，输出为公钥 $pk$ 与私钥 $sk$ 。

2）标签生成算法 $TagGen\left( {sk,F} \right) \to \sigma $ 。由数据用户执行，通过对文件 $F$ 分块后计算生成验证标签集合 $\sigma $ ，用于判断数据的验证标签是否损坏。

3）探测生成算法 $DetGen\left( {F,\sigma } \right) \to P$ 。由云存储服务器执行，基于两级分布式二叉树结构，对编码数据块与验证标签进行聚合，生成探测示证 $P$ ，其中， $P$ 包含聚合符号与聚合标签。

4）示证验证算法 $\left( {{\rm{True,False}}} \right)$ 。由第三方服务器执行，对从云存储服务器处收到的示证 $P$ 进行验证。验证通过输出True，表示当前的编码数据块完整；验证失败输出False，表示当前的编码数据块存在损坏情况。

基于LT码的动态更新技术的主要步骤包括：

1）密钥生成算法 $KeyGen\left( {{1^\kappa }} \right) \to \left( {pk,sk} \right)$ 。由数据用户执行，输入为安全参数 $\kappa $ ，输出为公钥 $pk$ 和私钥 $sk$ 。

2）标签生成算法 $TagGen\left( {sk,F} \right) \to \sigma $ 。由数据用户执行，通过对文件 $F$ 分块后计算生成验证标签集合 $\sigma $ 。

3）数据更新请求算法 $U\!\!pdateReque\!st\to R$ 。由数据用户执行，输出一个更新请求 $R$ ，该请求包含更新的编码数据块与对应的验证标签。

4）数据更新算法 $U\!\!pdate\left( {R,T} \right) \to \sigma {\left( {root} \right)^\prime }$ 。由云存储服务器执行，输入为更新请求 $R$ 与两级分布式二叉树 $T$ ，输出为更新后的两级分布式二叉树的根节点的聚合标签 $\sigma {\left( {root} \right)^\prime }$ 。

5）更新验证算法 $\left( {{\rm{True,False}}} \right)$ 。由数据用户执行，对从云存储服务器收到的更新两级分布式二叉树根节点的聚合标签 $\sigma {\left( {root} \right)^\prime }$ 进行验证。验证通过输出True，表示数据已成功更新；验证失败输出False，表示数据并未在云存储服务器上更新。

2.3 数据预处理

将文件 $F$ 分割成 $m$ 个原始数据包 ${F_1},{F_2}, \cdots ,{F_m}$ ，大小均为 $\left| F \right|/m$ bit。根据LT码的RS度分布， $m$ 个原始数据包通过XOR运算产生 $n\alpha $ 个编码数据包，其中， $\alpha $ 为单个服务器存储的编码数据包的数量，值为 $m \cdot (1 + \varepsilon )/k$ 。根据LT码的性质，平均需要 $O(m \cdot {\rm ln}(m/\delta ))$ 次操作才能从任意 $m \cdot (1 + \varepsilon )$ 个编码数据包中以 $1 - \delta $ 的概率恢复出 $m$ 个数据包。但是在实际运用中，不允许出现恢复失败，故数据用户在将编码数据包发送给服务器之前要提前运行解码算法，具体过程是：先将 $n\alpha $ 个编码数据包分为 $n$ 个组，每组有 $\alpha $ 个编码数据包，即 ${\{ {\{ {C_{li}}\} _{1 \le i \le \alpha }}\} _{1 \le l \le n}}$ ；然后，对这 $n$ 组数据包中的任意 $k$ 组执行置信传播解码算法^[16]，如果出现解码失败的情况，则数据用户需要重新生成编码数据包，直至任意 $k$ 组执行置信传播解码算法成功；一旦成功，则该配置可用于以后所有 $n$ 、 $k$ 值相同的存储服务。

每个编码数据包 ${\{ {\{ {C_{li}}\} _{1 \le i \le \alpha }}\} _{1 \le l \le n}}$ 带有两种辅助数据，分别为编码向量、验证标签值。编码向量 ${{\varDelta }_{li}}$ 是一个 $m$ 位的向量，每一位表示是否通过相应的原始数据包进行XOR运算得到 ${{\varDelta }_{li}}$ 。在损坏数据探测之前，需要对每一个编码数据包进行签名，得到相应的验证标签值，其具体工程是：先执行密钥生成算法 $KeyGen\left( {{1^\kappa }} \right) \to \left( {pk,sk} \right)$ ，得到公钥 $u$ 和私钥 $\eta $ ；然后，将每个编码数据包 ${C_{li}}$ 分成 $t$ 个片段 $\{ {C_{li1}},{C_{li2}}, \cdots ,{C_{lit}}\} $ ，并对每个片段 ${C_{lij}}$ 都执行标签生成算法 $TagGen\left( {sk,F} \right) \to $ $ \sigma$ ，生成一个验证标签值 ${\sigma _{lij}}(1 \le j \le t)$ ，计算式如下：

${\sigma _{lij}} \leftarrow {(H(l\parallel i\parallel j) \cdot {u^{{C_{lij}}}})^\eta } \in G$

(1)

这些数据将以 ${\rm{\{ }}l,{{\rm{\{ }}i,{C_{li}},{{\varDelta }_{li}},{\{ {\sigma _{lij}}\} _{1 \le j \le t}}{\rm{\} }}_{1 \le i \le \alpha }}{\rm{\} }}$ 的形式发送到第 $l$ 个服务器中。

2.4 损坏数据探测

为了对服务器上存储的数据进行损坏探测，首先随机选择 $\alpha + t$ 个数字， ${a_1},{a_2}, \cdots ,{a_\alpha },{b_1},{b_2}, \cdots ,{b_t} \leftarrow {{\textit{Z}}_p}$ ，其中， ${a_i}$ 与每个服务器上第 $i$ 个编码数据包一一对应， ${b_j}$ 与每个编码数据包的第 $j$ 个片段一一对应；然后，对每个服务器建立独立的探测子树，探测子树的叶子节点为编码数据块与其相对应的验证标签，通过聚合计算得到探测子树的根节点，同时，每个探测子树的根节点作为探测主树的叶子节点，通过聚合计算得到探测主树的根节点，从而构建出一个两级分布式二叉树，再执行探测生成算法 $DetGen\left( {F,\sigma } \right) \to P$ ，得到聚合符号和聚合标签。其具体过程是：在第 $l$ 个探测子树中，将每个编码数据包片段 ${C_{lij}}$ 及其验证标签值 ${\sigma _{lij}}$ 作为叶子节点，父节点由其两个子节点计算得到；假设两个子节点的编码数据包片段为 ${C_{l11}}$ 与 ${C_{l12}}$ ，验证标签值为 ${\sigma _{l11}}$ 与 ${\sigma _{l12}}$ ，则父节点的聚合符号为 ${a_1}{b_1}{C_{l11}} + {a_2}{b_2}{C_{l12}}$ ，聚合标签为 ${\sigma _{l11}}^{{a_1}{b_1}} \cdot {\sigma _{l12}}^{{a_2}{b_2}}$ ；由此得到第 $l$ 个探测子树的根节点，其聚合符号为 ${\mu _l}$ ，聚合标签为 ${\varsigma _l}$ ，具体计算式如下：

${\mu _l} = \sum\limits_{i = 1}^\alpha {\sum\limits_{j = 1}^t {{a_i}{b_j}{C_{lij}}} } ,\;\;{\varsigma _l} = \prod\limits_{i = 1}^\alpha {\prod\limits_{j = 1}^t {{\sigma _{lij}^{{a_i}{b_j}}}} } $

(2)

同理，在探测主树中，每个探测子树的根节点作为叶子节点，计算得到探测主树的根节点，具体计算式如下：

$\mu = \sum\limits_{l = 1}^n {{\mu _l}} ,\;\;\varsigma = \prod\limits_{l = 1}^n {{\varsigma _l}} $

(3)

在探测主树中，执行示证验证算法 $VerifyProof\left( P \right) $ $\to \left( {{\rm{True,False}}} \right)$ ，对其根节点上的聚合符号 $\mu $ 和聚合标签 $\varsigma $ 进行验证，如式（4）所示，式（4）的证明如式（5）所示。

$e(\varsigma ,g)\mathop {\rm{ = }}\limits^? e \,\left( {\prod\limits_{l = 1}^n {\prod\limits_{i = 1}^\alpha {\prod\limits_{j = 1}^t {H{{(l\parallel i\parallel j)}^{{a_i}{b_j}}}} } } \cdot {u^\mu },v} \right)$

(4)

$\begin{aligned}e(\varsigma ,g) & = e\left(\prod\limits_{l = 1}^n {{\varsigma _l}} ,g\right) = \\&e\left(\prod\limits_{l = 1}^n {\prod\limits_{i = 1}^\alpha {\prod\limits_{j = 1}^t {{\sigma _{lij}^{{a_i}{b_j}}} } }} ,g\right) = \\&e{\left(\!\prod\limits_{l = 1}^n {\prod\limits_{i = 1}^\alpha {\prod\limits_{j = 1}^t {{{(H(l\parallel i\parallel j))}^{{a_i}{b_j}}}} } } \cdot \prod\limits_{l = 1}^n {\prod\limits_{i = 1}^\alpha {\prod\limits_{j = 1}^t {{u^{{a_i}{b_j}{C_{lij}}}}} } } ,g\!\right)^\eta } \!=\\&e\left(\prod\limits_{l = 1}^n {\prod\limits_{i = 1}^\alpha {\prod\limits_{j = 1}^t {{{(H(l\parallel i\parallel j))}^{{a_i}{b_j}}}} } } \cdot {u^{{\sum\limits_{l = 1}^n} {{\sum\limits_{i = 1}^\alpha} {{\sum\limits_{j = 1}^t} {{a_i}{b_j}{C_{lij}}} } } }},v \right) = \\&e\left(\prod\limits_{l = 1}^n {\prod\limits_{i = 1}^\alpha {\prod\limits_{j = 1}^t {{{(H(l\parallel i\parallel j))}^{{a_i}{b_j}}}} } } \cdot {u^\mu },v\right) \end{aligned} $

(5)

如果式（4）等式左右两边相等，则证明当前所有服务器上的数据块不存在损坏情况；否则，证明服务器中存在损坏数据块，此时，对根节点的左右子树分别通过式（4）计算，以此类推，直至找到某个叶子节点不满足式（4）的验证，即某个服务器中存在损坏数据块，假设第 $l$ 个服务器存在损坏数据块，则对第 $l$ 个探测子树的根节点进行验证，具体计算式如下：

$e({\varsigma _l},g)\mathop {\rm{ = }}\limits^? e\left( {\prod\limits_{i = 1}^\alpha {\prod\limits_{j = 1}^t {H{{(l\parallel i\parallel j)}^{{a_i}{b_j}}}} } \cdot {u^{{\mu _l}}},v} \right)$

(6)

同理，直至找到某个数据块不满足式（6）的验证，则证明该数据块已损坏，最后启动数据修复程序。

2.5 动态更新

当数据用户需要更新数据时，向服务器发送更新请求，服务器根据编码数据块中的编码向量将相应的编码数据块传回给数据用户进行处理。假设更新前的数据块为 ${F_k}$ ，则将所有编码向量中第 $k$ 位为1的相应编码数据块以及 ${F_k}$ 传回给数据用户，数据用户更新后，数据块为 ${F'_k}$ ；根据LT码的编码性质，即 $A \oplus A' \oplus A = A'$ ，将传回的编码数据块 ${C_{li}}$ 先后对 ${F_k}$ 和 ${F'_k}$ 进行XOR运算，得到更新后的编码数据块 ${C'_{li}}$ ，即 ${C'_{li}} = {C_{li}} \oplus {F'_k} \oplus {F_k}$ ；再对其进行签名运算，得到 ${\left\{ {{{\sigma '}\!\!\!_{{lij}}}} \right\}_{1 \le j \le t}}$ ，执行数据更新请求算法 $U\!\!pdateReque\!st \to R$ ，从而实现编码数据块的更新。

在探测子树与探测主树中，定义从第 $i$ 个叶子节点到根节点所经过的所有节点为一条验证路径^[17]，记为 ${{\pi} _i}$ 。在进行动态更新过程中，服务器将编码数据块 ${C_{li}}$ 的验证路径上所有节点的另一子节点的聚合标签值发送给数据用户，这样数据用户可以重构出部分两级分布式二叉树。如图2所示，验证路径 ${{\pi} _i} = \left\{ {{m_{1,3}},{m_{2,2}},{m_{3,1}},{m_{4,1}}} \right\}$ ，则验证路径上所有节点的另一子节点为 $\left\{ {{m_{1,4}},{m_{2,1}},{m_{3,2}}} \right\}$ 。

得到更新后的编码数据块 ${C'_{li}}$ 后，数据用户可以根据重构出的部分两级分布式二叉树计算得到一个新的根节点的聚合标签值 ${\varsigma '_{{\rm{new}}}}$ ，服务器在执行数据更新算法 $U\!\!pdate\left( {R,T} \right) \to \sigma {\left( {root} \right)^\prime }$ 后，得到探测主树根节点的聚合标签 $\varsigma '$ ，而数据用户执行更新验证算法 $VerifyU\!\!pdate\left( {\sigma {{\left( {root} \right)}^\prime }} \right) \to \left( {{\rm{True,False}}} \right)$ ，通过比较 ${\varsigma '_{{\rm{new}}}}$ 和 $\varsigma '$ 是否相等以验证服务器是否正确执行了编码数据块的更新。

3 复杂度分析与实验结果分析

从理论复杂度与实验结果分析两个方面将基于LT编码环境下的两级分布式二叉树的损坏数据探测方案与逐一取回验证损坏数据探测方案^[8]进行分析比较，以及将基于LT编码环境下的动态更新方案与基于RS编码环境下的动态更新方案^[18]进行分析比较。

整个实验系统在Ubuntu 14.04环境下用Python语言编写，设置服务器数量 $n = 12$ ，无损坏数据服务器数量至少为 $k = 9$ ，原始文件分块大小为128 kB，则分块数量 $m = \left| {M/128\,\,{\rm{ kB}}} \right|$ ，各服务器存储的编码块数量 $\alpha = m\left( {1 + \varepsilon } \right)/k$ ， $\delta = 1$ ， $c = 0.1$ ，其中， $\varepsilon \sim O\left( {{{\ln }^2}\!\!\left( {m/\delta } \right)/\sqrt m } \right)$ 为LT码的开销因子。

3.1 复杂度分析

在基于LT编码的环境下，两个不同的损坏数据探测方案的复杂度比较见表1。

从表1可以看到，作者提出的两级分布式二叉树的损坏数据探测方案的复杂度最优为 $O\left( {\sqrt {n\alpha } } \right)$ ，最差为 $O\left( {n\alpha } \right)$ ，最差的复杂度与逐一取回验证方案相当。

3.2 实验结果分析与对比

如第2.3节所述，数据用户在将编码数据包发送给服务器之前要提前运行解码算法，以保证数据可用性，即对 $n$ 组编码数据包中的任意 $k$ 组执行置信传播解码算法，但是这样的效率偏低，由于编码数据包与编码向量一一对应，因此，将这 $n$ 组的编码向量执行解码步骤，而编码数据包无需执行此步骤，如果出现解码失败的情况，即无法恢复所有数据包，则数据用户需要重新生成编码数据包，直至任意 $k$ 组执行置信传播解码算法成功。

由于 $\varepsilon $ 和 $\alpha $ 呈线性关系，所以 $\varepsilon $ 值越大，执行置信传播解码算法的代价会越高，如图3所示，将 $\varepsilon $ 值设为最小值0.190 4。

两级分布式二叉树的开销包括树的生成时间和节点存储开销，对于一个给定的文件，其对应的两级分布式二叉树的高度与文件大小和数据块数量相关。假设叶子节点数为 $n$ ，则树的高度 $H = \left\lceil {\operatorname{l} {\rm{b }}\,\,n} \right\rceil + 1$ ，节点数 $num = 2n - 1$ 。不同大小文件的两级分布式二叉树的生成时间和存储开销如表2所示。

当出现损坏数据时，需要执行损坏数据探测方案，尽可能快地查找到损坏数据块，如图4所示，随着文件越来越大，两级分布式二叉树损坏数据探测方案的探测时间也越来越大，但是，其增长的幅度比逐一取回验证方案的探测时间的增长幅度小得多，主要原因在于逐一取回验证方案的探测时间开销为 $O\left( {n\alpha } \right)$ ，而两级分布式二叉树损坏数据探测方案的时间开销为 $O\left( {\sqrt {n\alpha } } \right)$ 。

对数据用户而言，存储在服务器上的数据可能不止一个地方损坏，出现多处损坏可能会降低损坏数据探测的效率，进一步，比较在同一文件下不同的损坏数据块数量与探测时间的关系，如图5所示。

当损坏数据块数量为1/300时，两级分布式二叉树损坏数据探测方案的探测时间达到最小值，因为整个探测路径是从探测主树的根节点到探测子树的叶子节点，即整个树的高度。随着损坏数据块的数量越来越多，两级分布式二叉树损坏数据探测方案的探测时间也增大，当所有数据块都损坏时，探测时间达到最大值，因为需要遍历整个探测主树与子树，而逐一取回验证方案的探测时间不随损坏数据块的数量变化而变化。由图5可以看出，在同一文件下，随着损坏数据的不断增加，两个方案的探测时间差不断缩减，甚至到最后两级分布式二叉树探测方案的探测时间比逐一取回验证的损坏数据探测方案的探测时间还要多，其原因在于两级分布式二叉树探测方案每多一次对叶子节点进行计算，就需要对根节点至相应叶子节点的路径上所有节点进行计算。

当数据用户需要更新数据时，需要执行数据动态更新方案，并尽可能快地将数据块进行更新。原始文件大小为300 MB，如图6所示，随着更新数据量不断增加，数据更新所需时间也不断增长，但是从整体上看，作者提出的基于LT编码的数据动态更新方案比基于RS编码的数据动态更新方案^[18]所需时间少一些，主要原因在于LT码是XOR运算，比RS码的矩阵乘法运算简单高效。

4 结　论

云存储是一个以数据存储和管理为核心的云计算系统，是未来存储发展的一种趋势，但随着云存储越来越普及以及数据量越来越大，存储的数据出现损坏情况无可避免，如何能够快速进行损坏数据探测则越来越重要。作者研究了云存储系统中的损坏数据探测和动态更新问题，并且设计了一种基于LT编码的两级分布式二叉树的方案。该方案利用BLS签名的聚合性质对数据块进行计算并生成聚合标签，通过验证聚合标签是否正确来以定位出损坏数据所处的位置，提升了探测损坏数据块的效率；同时，方案基于LT码的编码性质可支持对更新数据块进行异或运算，实现了数据的动态更新，并且能对云服务器是否进行数据更新加以验证。理论分析与实验结果表明，与逐一进行数据探测的方案相比，作者所提方案在存储开销相当的情况下，有效减少了计算和通信开销，显著提高了损坏探测的效率。下一步工作将重点研究如何优化存储数据的数据结构与数据动态更新方案。