一种基于增量存储的多副本文件版本控制方法

引 言

在云存储 [1,2] 中，数据所有者对 CSP 端文件的每一次动态更新操作都是DO 与CSP 之间的多次交互，而在云存储平台中每次发生版本更新更迭，系统都会将历史版本保存下来以响应用户的版本恢复请求。在多副本的情况下，传统的全量存储方式对云存储平台存储空间消耗巨大，尤其对改动频繁的大容量文件会消耗更大的存储空间，因此文件的全量存储方式对于多副本文件是不可取的[3,4]。

为了解决上述问题，缓解云存储平台的存储空间，本文采用增量存储方式来存储多副本文件版本的信息[5,6]。增量存储的基本思想是仅存储最新版本与基本版本之间的差异信息（以下称之为增量），由基本版本和增量构成版本信息。目前有正增量和逆增量两种存储模型[7,8]。

1 增量存储模型

(1) 正增量存储模型

在正增量存储模型中，Vi+1=Vi+Δi│条件，i ≥ 0，当 i= 0 时为原始版本。Δi │条件是在 Vi 基础上通过操作条件修改得到差异信息，即只存储原始版本的完整数据，而后继版本只保存其与前一版本的增量[9]，如图 1 所示。

(2) 逆增量存储模型

在逆增量存储模型中，只存储最新版本的完整数据，其余历史版本则只存储与后继版本之间的增量信息，即 Vi 存储Vi+1 和 Vi 之间的增量 Δi │条件，最后一个版本存储其完整内容。

2 文件版本控制

数据所有者将文件划分为多个文件块，并为文件块产生多个副本和数据标签，且每个副本可唯一标识。文件块的多个副本由同态概率加密方法生成，文件块的数据标签由BLS 签名生成，将文件块副本和文件块的数据标签发送到云端。这些文件块的加密副本表示未加密文件块的基本版本，对未加密文件块当前版本的每一次修改都将产生新的版本，新版本的文件块不直接存储在云端，只存储增量，增量为未加密文件块的新版本与基本版本之间的差异。当需要文件块的特定版本时， 数据所有者请求云端将增量块与文件块的基本版本合并，从而得到文件块所需版本。

文件版本表由五部分组成，分别为块号（BN）、增量块号（DBN）、文件版本（FV）、块版本（BV）、块操作（BO）。

(1) BN表示文件块的索引，描述了文件块在数据文件中的物理位置。

(2) DBN是增量块的索引，如果增量不存在，则该值存储 为 - 。

(3) FV表示整个文件的版本。

(4) BV表示文件块的版本。

(5) BO指出了对文件块执行操作的类型。

FV 的最大值表示文件的最新版本，并且对于特定的BN， 其BV 的最大值表示该文件块的最新版本。如果在文件版本表中没有找到文件块号的条目，则意味着没有对文件块的基本版本进行更新操作，且文件的基本版本和最新版本的文件块相同。当对块号为b、文件版本为 v 和文件块版本为 y 的文件块进行修改时，数据所有者可以选择将整个文件的版本更改为 v + 1 或保持原版本不变。对于这两种情况，数据所有者在文件版本表中创建一个新条目。在第一种情况下，表条目将是 <b，-，v+1，0，Modify>，并且对于第二种情况，表条目将是 <b，-，v， y+1，Modify>，见表 1 所列。

数据所有者使用文件版本表来跟踪记录文件块的版本更新情况，用来验证 CSP 存储的所有文件及其版本的完整性和一致性。当数据所有者对文件块执行更新操作时，将会生成新版本的文件块，数据更新操作包括文件块插入、删除或修改， 当且仅当数据更新操作是 修改 时才会生成增量块，一旦更新操作完成，数据所有者就会更新文件版本表，文件版本表仅在数据所有者端维护，有助于数据所有者隐藏 CSP 执行更新操作的详细信息。

3 算法设计

3.1 文件版本动态更新

本文的文件版本动态更新操作由更新 请求算法PrepareUpdate（） 和更新执行算法 ExecUpdate（） 来执行， 对应的请求操作包括数据块修改、数据块插入和数据块删除。文件版本修改操作如图 2 所示。

3.1.1 更新请求算法

更新请求算法：PrepareUpdate（）→ Update。本算法在数据所有者端运行，对远程 CSP 存储的外包文件副本执行更新操作，算法的输出是更新请求。数据所有者将更新请求以<Idf，BlockOp，j，bi '，φ' > 的形式发送到云端，其中Idf 是文件标识符，BlockOp 对应块操作，j，bi ' 和φ' 分别表示文件块的索引、更新的文件块和更新的标签，BlockOp 可以是数据插入、修改或删除操作。

(1) 数据插入 ：对文件 F的任一版本 v的插入操作意味着在文件中插入新的文件块。数据所有者决定新文件块所属的文件版本，可以是当前文件版本v或者是下一个文件版本v+1。如果新文件块添加到文件版本 v+1，则 v+1就是文件的新版本，在文件版本表中创建一个新记录为<BN，-， v或v+1，0，Insert>。由于没有增量块且插入了新的文件块， 所以 DBN值为 - ，BV值为 0。

(2) 数据修改 ：对最新版本的文件块进行修改。数据所有者识别需要修改的文件块块号，并在文件版本表中搜索块号， 如果没有找到特定块号记录，那么从云中下载来自基本版本的文件块。如果找到了目标记录，那么识别出文件块的最新版本并从云端下载，文件块的最新版本就是解密下载的基本版本的文件块与增量合并得到的文件块版本。对明文进行修改操作以获得更新后的明文，数据所有者将计算更新的明文和基本版本明文之间的差异作为新的增量，然后将增量随机化，并将其发送到云端。随机化的目的在于不向云端暴露增量值。令M={bi}，其中1 ≤ i≤ s 是更新操作之前的文件块集合，M'={bi'}， 1 ≤ i≤ s是更新操作之后的文件块， 增量∆ M值为{bi'-bi}，1 ≤ i ≤ s。使用由PRF 密钥 Keydata 生成的随机数来对增量进行随机化，因此，∆ M={bi '-bi+N-xi}，1 ≤ i ≤ s。最后将 M 值发送到云端。

(3) 数据删除：对文件 v的任一版本的删除操作意味着从文件中删除几个文件块。数据所有者可以从当前版本 v删除文件块，或者从下一版本v+1中删除文件块。且数据所有者在文件版本表中创建一条记录 <BN，-，v或v+1，0， Delete>。删除操作的结果只是在文件版本表中添加一条记录， 而CSP不知道关于删除操作的任何内容。

3.1.2 更新执行算法

更新执行算法：ExecUpdate（F，φ，Update）→（F'，φ'）。本算法在CSP 端运行，输入参数为文件副本 F、标签φ和更新请求（由数据所有者发送）。输出为新的文件副本 F' 以及更新的标签 φ'。在每次块操作之后，数据所有者运行挑战协议以确保云端正确执行了更新操作，更新请求中的操作可以是插入新的文件块或修改文件块，数据所有者不向云端发送任何删除请求，因此不会删除任何数据块。

3.2 文件版本请求与文件版本传递

数据所有者创建文件版本表跟踪数据更新操作，此表中的记录数值取决于对文件块进行动态操作的数量。文件更新作为增量存储在云端，为了获得文件的特定版本，数据所有者将带有两个参数<BN，DBN>的FileVersionRequest 发送到云端。在接收到FileVersionRequest之后，云端执行FileVersionDeliver算法。对于DBN值为–的文件版本请求，CSP直接将块号为BN 的文件块传递给数据所有者，不涉及任何CSP计算开销。对于具有有效DBN值的FileVersionRequest而言，云加密增量块号为DBN的文件块， 执行同态加法运算。

（1）FileVersionRequest ：数据所有者通过检查文件版本表来识别所需版本的文件块，并使用块编号以<BN，DBN> 的形式向CSP 发送请求。此外，需要 DBN 才能访问所需的文件版本，如果文件版本表中没有 DBN 条目，则请求将是

<BN，->。

（2）FileVersionDeliver：对于FileVersionRequest中DBN值为-的所有文件块号，将该文件的基本版本传递给数据所有者，如果具有有效的DBN值，则CSP 利用公钥对增量进行加密，并对基本版本的文件块进行同态加法运算， 最后得到数据所有者请求版本的文件块。令∆M={bi'-bi+N- xi}，1≤i≤s是与数据所有者请求的相应文件版本的文件块相关联的增量，加密的增量 E（∆ M）={（1+（b'-b+N-x）N（r）N}，其中，r ∈ ZN* 是随机数。最后，云端对文件基本版本上所请 求的文件块执行同态加法操作。同态加法之后得到的文件块 表示数据所有者所请求版本的加密文件块，将加密的文件块 发送给数据所有者，数据所有者对文件块进行解密，从而获 得其请求的版本。

4 算法性能分析

4.1 实验环境

本文主要验证文件版本传递算法的 CSP 计算开销，对 1 MB 文件在本地计算机、不同配置的虚拟机环境下进行实 验。本地计算机实验环境为 Intel（R）Core（TM）i7-6700HQ 2.60 GHz 处理器、16 GB RAM ；虚拟机实验环境 1 具有单核 处理器，2 GB 内存，200 GB 硬盘空间；虚拟机实验环境 2 具有双核虚拟处理器，8 GB 内存，500 GB 硬盘空间。

4.2 文件版本传递算法 CSP 计算开销比较

图 3 中 FileVersionRequest 的 数 量 用文件 块 的百分比 表示。例如，1 MB 文件具有 8 192 个大小为 128 B 的文件 块。当数据所有者发送 81 个 FileVersionRequest 时，CSP 加 密 81 个增量块（8 192 个文件块的 1％），并执行 81 次同态加 法运算。因此任何数目的 FileVersionRequest 将导致 CSP 对 这些文件块执行操作，并且 FileVersionRequest 可以用文件 块 的 数目来 表 示。MRFVCM（Multiple Replica File Version Control Method，MRFVCM）在数 据所有者端不涉及执行 FileVersionDeliver 算法的任何计算，数据所有者的唯一成 本是维护文件版本表。图 3 显示了在本地计算机和不同配置 的虚拟机环境上运行 FileVersionDeliver 算法的 CSP 计算时 间的比较。FileVersionDeliver 算法的 CSP 计算时间定义为 CSP 将所请求版本的文件块传递给数据所有者所花费的时间。 FileVersionDeliver 算法在本地计算机上执行得更好，因为它 的配置最高。

5 结 语

本文支持多副本文件版本管理，首先构建了文件版本表， 该表由数据所有者运行维护；其次，详细阐述了用户申请特定 版本到 CSP 执行文件版本传递算法的详细过程 ；最后通过实 验仿真，对比了文件版本传递算法在不同配置运行环境下的 CSP 计算开销，验证了本算法的高效性和可用性。