基于有序哈希链的文件数据同步方法

曾畅，蒋文保，郭阳楠

（北京信息科技大学信息管理学院，北京 100085）

0 概述

随着信息时代的到来，分布式系统得到了广泛的应用，包括个人使用多台主机保存文件与数据，企业利用总部、分部服务器来运行业务数据等。个人由于工作场景、工作需求的不同使用多台主机工作，导致文件数据分散且难以同步更新。企业要求各分部服务器与总部服务器保持实时更新以及通过远程服务器备份来应对异常情况。大型企业及单位需要同步或备份的文件数据量较大且更新频繁，采用传统完全拷贝式同步或备份难以满足其要求。这些需求促使文件数据同步方法的发展［1-2］。目前，国内所进行的同类工作多为远程同步系统或文件备份架构的研究，针对文件数据同步算法的优化研究较少［3］。

基于差异的文件同步算法改进了传统文件同步中将文件库所有文件重新传输一遍的缺点［4］，在一定程度上提高了同步的效率。其中Rsync 同步算法是被广泛使用的远程同步算法［5-6］，其核心方法是计算服务器端和客户端文件库的差异，以及通过差异计算对不同部分进行同步更新，保证两端文件的一致性。目前，国内外对于文件数据同步的研究主要是基于Rsync 算法［7］。ZHANG 等［8］提出一种新的增量同步方法SimpleSync，根据服务器端不主动修改云存储服务中备份文件的特点，去掉了Rsync 中的冗余步骤，仅通过一次通信就可以实现客户端和服务器端之间的同步。该方法在计算差异部分时仍存在使用大量哈希算法的问题。IRMAK 等［9］提出一种基于冗余码的新方法，通过对单轮协议的文件进行同步，以显著地改进Rsync 算法。尽管这些方法都在实践中对Rsync 进行改进以提升同步效率，但是都未从根本上减少同步过程中时间和资源的消耗。

现有的大多数同步算法需要逐个对文件浏览对比并进行差异计算，增加了性能消耗，以及缺少一致性承诺，无法快速判断文件库是否产生新变动和同步完全。在对文件进行查找比对和同步后，现有算法未对操作状态和更新结果进行备份［10］，在恢复文件库原有版本面临诸多困难。

本文提出一种基于操作系统的文件同步方法hcsync。通过对文件库进行差异监视，利用哈希链记录全部文件操作状态。由于有序哈希链的节点包含文件/目录的变化信息，并记录了相关操作的状态，因此通过哈希链的比较能快速找到变化的文件/目录，同时跳过没有变化的文件/目录，从而提高了同步效率［11-12］。链尾哈希值能满足快速验证文件库的变动情况和一致性。通过服务器端链尾哈希值判断文件库是否产生新的更新，利用客户端链尾哈希值判断链尾和服务器端的文件库是否保持一致性。由于哈希链会记录文件库的相关操作状态，因此使用者可以通过溯源哈希链查询认证或撤销某次操作。

1 相关工作

1.1 Inotify 特性

Inotify 是一个Linux 内核特性，为用户提供监控文件系统的接口，并记录某些事件，例如读、写、删除等操作，以及跟踪事件的源头、目标等细节［13］。Inotify 在虚拟文件系统（Virtual File System，VFS）层中工作。VFS 又称虚拟文件系统开关，采用标准的UNIX 系统调用读写位于不同物理介质上的不同文件系统。

本文方法根据Inotify 构建哈希链，监控文件库中的文件数据变化来获取新建、修改、移动、删除等事件的相关属性。对于不同系统的服务器，在哈希链构造时所监控的系统接口存在不同情况，如Linux系统下使用Inotify 接口，windows 系统下使用WinApi 接口等，需要根据不同的系统做适当的调整。

1.2 哈希链

哈希链的思想最初由美国数学家LAMPORT［14］提出，用于一种安全通信的用户密码认证方法。利用哈希运算对密码进行多次迭代，所得的密文序列具有较优的抗干扰性、防篡改性，且根据最后一次加密密文即可验证整条密文序列。

近年来，哈希链技术的研究和应用在不断地拓展和丰富。HUANG 等［15］提出一种基于哈希链的灾后恢复数据可用性监控方法，解决分布式系统中数据备份及数据恢复问题。MOTOHASHI 等［16］提出一种基于区块链与客户端哈希链相结合的mHealth系统，确保医疗机构数据管理的安全性、可扩展性和可靠性。YE 等［17］提出一种基于哈希链的可信DNP3-BAE 广播认证加密协议，解决了广播模式下消息安全认证机制缺失的问题。ZHAO 等［18］提出一种基于哈希链的跨境身份认证和隐私保护方案，通过哈希链的安全特性来管理网络中的数据信息。

1.3 Rsync 算法

Rsync 是UNIX/Linux 下文件同步算法［19］。该算法对文件数据进行对比检验，在服务器端和客户端传输两个文件库的不同部分，而不是完全拷贝式传输，实现了增量变化同步，提升效率。Rsync 可快速对比在服务器端和客户端磁盘中相同目录下的文件，查出两端的区别，并对客户端上不同的部分进行同步更新。

Rsync 算法由检查模式和同步模式两部分组成，检查模式决定哪些文件需要同步，同步模式决定传输变化文件数据。其中检查模式分为“quick check”策略和常规策略。“quick check”策略如下：

1）同步端创建文件列表，文件列表中包含文件的一些属性信息，主要包括文件大小len、修改时间mtime 等。

2）“quick check”策略快速检查两端文件列表中相同文件的文件大小len、修改时间mtime 是否一致。如果不一致，则表明该文件为待传输文件，对其执行常规策略同步操作；如果一致，“quick check”策略认定该文件相同，不需要传输。

常规策略过程如下：1）客户端将文件f 数据分成没有重叠的m 字节数据块，如果最后一块不足m 字节，则填充为m 字节；2）每个数据块分别计算强弱校验码，强校验码是通过可靠的哈希函数获得，并传输给服务器端；3）服务器端遍历搜索文件f1，产生强弱校验码并与客户端发送的强弱校验码进行对比，首先匹配弱校验和，如果相同说明是同一个数据块，如果强校验和也相等，则说明两个数据块相同，继续比较下一个数据块，如果不相等跳转到下一个字节，对数据块进行匹配，记录不匹配数据块索引与偏移量内容，直到得出所有偏移量内容，则停止比较［20］；4）在客户端获取服务器端的不匹配数据块索引和偏移量内容时，通过这些数据重组临时文件，使其内容与文件f1 相同，当临时文件重组完成后，修改该临时文件的属性信息（权限、mtime 等），然后将该临时文件替换客户端文件f，客户端文件f 与服务器端文件f1保持同步。

1.4 基于哈希树的同步方法

基于哈希树的同步方法是根据文件库的目录结构构建有序哈希树，并利用此哈希树来获取文件库的变化并快速同步［21］。文献［22］提出的基于有序哈希树同步方法中，哈希树各节点由四元组＜p，Hash，firstChild，nextSibling＞表示。其中：p表示路径；Hash表示该节点存储的哈希值，在该方法中Hash 值为路径与时间戳拼接进行运算的哈希值；firstChild 为该节点的第一个子节点；nextSibling 为该节点的后继兄弟节点。因为哈希树的构建过程是遍历目录树，依次计算子节点的哈希值，之后回溯到父节点，按顺序拼接子节点哈希值，并将拼接结果的哈希值作为父节点的哈希值。一旦文件库资料发生变化，其对应有序哈希树的根节点哈希值必定发生变化，如果根节点哈希值未发生变化，则文件库未产生新变化。这就是有序哈希树能快速检测和定位文件库变化的原理。

2 总体设计

2.1 符号定义

基于有序哈希链的文件数据同步方法所使用的符号、函数以及对应参数如表1 所示。

表1 本文方法的重要符号说明Table 1 Important symbol description of the proposed method

2.2 整体架构

基于有序哈希链的同步模型可以用一个三元组表示：

Monitor 表示对文件操作或事务日志的监听算法，以获取文件库的文件数据操作状态，最终输出一个文件库变化内容序列。操作状态的分类以文件系统接口和事务日志提供的类型为基准。

Setup 表示哈希链的构建算法，输入为Monitor 算法中变化内容序列，将变化内容Xi作为哈希链上的新节点，最终输出一个有序哈希链(C1,C2,…,Cn)。该算法将文件库的操作状态以时间顺序，通过哈希函数迭代形成一个能够记录文件库所有操作状态的有序哈希链。

Sync表示根据哈希链执行逻辑同步，根据哈希链上所记录的操作状态o_type=(mov,add,del,mod)，执行服务器端相同的文件数据变化操作，以保证两端文件库的一致性。

hcsync 方法整体架构如图1 所示。该方法不需要对文件库中的文件数据逐一比较，就可以快速获取文件变化并保持更新，避免了传统同步方法中需要全盘检索文件库以获取差异文件而耗费的额外资源与时间。

图1 hcsync 方法整体架构Fig.1 Overall architecture of hcsync method

2.3 构建与同步流程

有序哈希链的构建流程如图2 所示。

图2 有序哈希链的构建流程Fig.2 Construction procedure of ordered Hash chain

服务器端通过系统接口监测文件库，实时获取文件库变化生成的六元组节点，并构成变化内容序列(X1,X2,…,Xn)，再由变化内容序列计算得到哈希序列，最终迭代哈希函数得到哈希链。

客户端通过有序哈希链对服务器端文件库进行同步，同步流程如图3 所示。

图3 客户端同步流程Fig.3 Procedure of client synchronization

客户端首先向服务器端发出同步请求，获取最新哈希链并与本地哈希链做比较，以快速获取最新文件变化。在比较过程中获取新生成的哈希链节点，然后按照顺序执行节点操作。具体同步步骤如下：

1）客户端同步服务器端文件库，如果是首次同步，下载完整文件库与哈希链至本地，否则客户端对比两端哈希链，并进行相应更新操作。

2）当两端哈希链链尾的哈希值不相等时，根据服务器端哈希链新增加的变化节点更新文件库。在执行当前哈希链节点变化操作时，需要对本节点进行哈希值验证，以保证哈希链的不可篡改性和完整性。如果o_type=0 为移动事件，客户端执行相同文件/目录移动操作；o_type=1 为新建事件，客户端同步该新文件至本地；o_type=2 为删除事件，删除客户端文件库的该文件/目录；o_type=3 为修改事件，删除本地文件并同步最新文件。

3）执行完所有新增变化节点，文件库同步更新完毕，此时留存最新哈希链至本地。当服务器端哈希链过长时，同步端可根据需要留存部分哈希链，仅根据链尾哈希值即可判断是否同步完全。

3 单层哈希链

3.1 单层哈希链构建方法

单层哈希链的结构如图4 所示。

图4 单层哈希链结构Fig.4 Structure of single layer Hash chain

该方法根据先后次序将服务器端文件库目录、文件变化看作一个变化序列(X1,X2,…,Xn)。变化序列内容可以用六元组表示：

本文通过哈希函数计算每一个变化内容的哈希值，如图4 中由变化序列计算得到的哈希序列(h1,h2,…,hn)，再通过哈希函数对哈希序列进行迭代，生成哈希链。哈希链节点由八元组表示：

节点哈希值是通过哈希函数对存在变化内容的哈希值与上一节点的哈希值共同处理获得，由多次计算得到的节点Hash 值构成一条哈希链。单层哈希链构建方法的步骤如下：

1）系统监测到文件库存在数据更新，将每一次变化内容按照时间顺序生成变化内容序列。

2）取出变化内容序列头部一个变化内容Xi，为此次内容创建有序哈希链的节点：

3）对变化事件Xi进行哈希运算hi=H(Xi)。

4）获取哈希链末尾节点的哈希值，previous_Hash=Ci-1[Hash]；如果哈希链为空，previous_Hash=null。

5）记Ci[Hash]=H(hi+previous_Hash)，并将其添加至节点：

6）将哈希链节点Ci添加至哈希链尾部，弹出变化内容序列头部Xi。

7）若变化内容序列为空，退出；否则进入步骤2。

3.2 单层哈希链同步方法

算法1单层哈希链同步算法

4 双层哈希链

4.1 双层哈希链构建方法

本文提出一种基于目录-文件双层哈希链，其结构如图5 所示。

图5 双层哈希链结构Fig.5 Structure of double layer Hash chain

该方法将服务器端文件库变化分为目录哈希链和文件哈希链。目录哈希链作为主链记录所有目录的变化，在每个目录下都存在一个文件哈希链记录该目录下文件的变化。当文件库存在文件数据更新时，主链首先记录该文件所属目录变化，再到第二级该目录下的文件哈希链记录文件变化内容。

该方法根据先后次序将服务器端文件库变化视作一个变化序列(X1,X2,…,Xn)，首先根据目录变化生成目录哈希链节点：

再到该目录下文件哈希链生成文件哈希链节点：

双层哈希链的基本构造方法步骤如下：

1）系统监测到文件库存在数据更新，将每一次变化内容按照时间顺序生成变化内容序列。

2）取出变化内容序列头部Xi中的目录部分，为此次内容创建目录哈希链的节点：

爱是春雷，能惊醒迷途的学生；爱如夏雨，能沁入学生的心脾；爱是秋风，能拂去学生心灵的尘垢；爱如冬日，能温暖学生的心灵。

3）对变化内容Xi目录的变化部分进行哈希运算。

4）获取目录哈希链末尾节点的哈希值，previous_Hash=Di-1[Hash]。如果哈希链为 空，previous_Hash=null。

5）记Di[Hash]=H(hi+previous_Hash)，并将其添加至目录哈希链节点Di中。

6）将目录哈希链节点Di添加至目录哈希链尾部。若type=3，进入第二层src_path 目录下的文件哈希链；否则弹出变化内容序列头部Xi并转入步骤9。

7）根据Xi文件变化部分创建src_path 目录下文件哈希链的节点Fi，构建节点的过程与目录哈希链相同。

8）将文件哈希链节点Fi添加至文件哈希链尾部，弹出变化内容序列头部Xi。

9）若变化内容序列为空，则退出；否则转入步骤2。

4.2 双层哈希链同步方法

双层哈希链基于双层结构，将目录和文件变化分级存储。在同步过程中只需要对比两端目录哈希链链尾的哈希值，即可判断是否存在文件库更新。如果是目录变化，对目录执行相关操作；如果是目录下的文件变化，则比较该目录下的文件哈希链并更新文件，执行结束后返回目录哈希链。客户端执行完所有目录哈希链新增的变化节点后，留存最新的双层哈希链并作为本地哈希链，同步完成。双层哈希链同步如算法2 所示。

算法2 双层哈希链同步算法

5 安全性分析

本文验证所提同步方法的安全性，证明如下：

引理假设哈希链构建方法中使用的哈希函数具有密码学安全性。不可篡改性是指在哈希链同步时，哈希链无法被攻击者恶意篡改其内容。

证明每个哈希序列节点Xi包含h_id、src_path、dest_path、p_type、o_type、timestamp。由哈希链构建公式可得：

若哈希链内容被恶意篡改，即Xi转变为X′i，则说明h_id 转变为h_id′，或src_path 转变为src_path′，或dest_path 转变为dest_path′，或p_type 转变为p_type′，或o_type 转变为o_type′，或timestamp 转变为timestamp′，则无法通过哈希值验证，如式（2）所示：

由于节点内容被篡改，因此必然存在Hashi≠Hash′i，则哈希链验证不通过。即使篡改节点Ci的哈希值Hashi为恶意篡改后 的Hash′i，也会导致下一节点无法通过哈希值验证，如式（3）所示：

因此，本文方法可以实现不可篡改性，证毕。

除了不可篡改性，本文方法还具有以下安全特性：1）完整性，将文件库所有更新变化记录在哈希链中，在完成同步后可确保更新内容的完整性以及与服务器端文件库的一致性；2）不可抵赖性，根据哈希链链尾的哈希值即可判断所有节点变化内容都已被执行，哈希链上的所有更新已同步；3）可溯源性，作为一条基于时间顺序记录文件库所有变化的有序哈希链，所有更新内容在哈希链上且可查询，并且通过逆向操作得到想要恢复的文件库版本。

表2 所示为本文同步方法与当前其他同步方法的安全性对比。其中“√”表示该方法具有这种特性，“×”表示不具有这种特性。从表2 可以看出，本文同步方法具有一定的优势。

表2 各同步方法的安全性对比Table2 Security comparison of various synchronization methods

6 效率分析

6.1 实验设计

本文实验采用单层哈希链进行对比，使用的哈希函数为SHA-3，将客户端同步服务器端文件库的过程分为以下三种实验：1）当文件库未发生改变时，hcsync 与Rsync 同步时间效率对比；2）hcsync 与使用“quick check”策略的Rsync 同步时间效率对比；3）hcsync 与使用常规策略的Rsync 同步时间效率对比。当Rsync 使用独特的“quick check”策略时，可以实现快速同步备份数据的目的。实验一在文件库未变动时进行同步效率对比，补充了文件库同步时含有变动和未变动的情况。实验二和实验三分别对比两种策略下Rsync 的同步效率。

客户端首次同步服务器端时需要下载整个文件库，但在后续同步或备份过程中都是更新文件变化，初始同步通常只发生一次，后续的同步是文件库的局部更新。在此基础上，本文设计文件库文件数据发生变化和未发生变化两种情况，涵盖了在日常使用中的绝大多数情况。其中本文实验的文件库变化以文件新增为代表。

本文实验配置为Quad-Core Intel Core i7 2.2 GHz CPU、4 GB RAM、Ubuntu 20.04 LTS操作系统。

本文设计了三种情况下Rsync 方法与hcsync 方法的对比实验，以测量两种方法实际的文件同步效率，并与htsync 方法进行对比。算法参数为两端存储目录/root/test。实验结果中关于Rsync 和基于有序哈希树的同步方法htsync 对比数据来源于文献［22］。

6.2 实验结果

6.2.1 文件库未变动的实验结果

在文件库未变动的情况下，本文实验的文件大小为95 MB、190 MB、285 MB、380 MB、475 MB 和570 MB，未产生相应文件的数据传输。Thcsync、Thtsync分别表示hcsync、htsync 同步时间，TRsync和T′Rsync分别表示与hcsync 和htsync 相同实验环境下的同步时间。基于哈希链与哈希树的同步时间加速比分别如式（4）和式（5）所示：

表3 所示为在不同环境下hcsync 与Rsync 的同步性能对比和htsync 与Rsync 的同步性能对比。在文件库未变动的情况下，hcsync、Rsync、htsync 都需要快速判断客户端与服务器端之间文件库的异同，如果未产生变化时便可结束更新，且hcsync 和htsync 都能较快地完成同步。从表3 可以看出，hcsync 和htsync 的平均加速比分别为94.85% 和3.63%。hcsync 和htsync 相较于Rsync 都不需要对文件库进行逐个文件对比，但htsync 需要对比哈希树与节点哈希值，导致时间延长。hcsync 只需对比链尾哈希值即可判断两端文件库的差别。

表3 在文件库未变动情况下不同方法的同步性能对比Table 3 Synchronization performance comparison among different methods without changing the file library

在文件库未改动的情况下，hcsync 和Rsync 的同步时间对比如图6 所示，hcsync 相较于Rsync 的同步时间大幅减少。

图6 在文件库未变动情况下不同方法的同步时间对比Fig.6 Synchronization time comparison among different methods without changing the file library

6.2.2 “quick check”策略下的实验结果

本文在文件库初始大小为0 和每次新增95 MB的条件下进行实验，当客户端文件库同步结束后，文件库大小分别对应为95 MB、190 MB、285 MB、380 MB、475 MB 和570 MB。Rsync使用“quick check”策略，对比两端文件大小与时间戳后进行同步。hcsync 与使用“quick check”策略Rsync 的同步性能对比如表4 所示。由于htsync 缺少关于“quick check”策略的同步效率，因此该实验不与htsync对比。

表4 hcsync 与使用“quick check”策略Rsync 的同步性能对比Table 4 Synchronization performance comparison among hcsync and Rsync using‘quick check’policy

图7 所示为hcsync 与使用“quick check”策 略Rsync 的同步时间对比。

图7 hcsync 与使用“quick check”策略Rsync 的同步时间对比Fig.7 Synchronization time comparison of hcsync and Rsync using‘quick check’policy

从图7 可以看出，Rsync 使用“quick check”策略的同步效率大幅增加，仅需要对大小和时间戳有改动的文件执行Rsync 具体同步操作。但是这种模式也有其相应的弊端，如果客户端的文件时间戳和大小与服务器端完全一致，但内容恰巧不一致时，在这种模式下Rsync 是无法发现文件库存在更新。因此，Rsync 的“quick check”策略能够减少同步时对比文件所消耗的资源，提升同步效率，但是却无法完全保证同步的完整性。在两端同步文件时，该策略下记录文件大小与时间戳的文件列表容易被窃取与篡改，存在同步的安全性与稳定性等问题。实验结果表明，相比使用“quick check”策略的Rsync，hcsync同步方法在效率上仍存在一定优势，平均同步加速比为6.5%。因此，基于有序哈希链的同步方法具有较优的完整性、稳定性且较高的效率。

6.2.3 常规策略下的实验结果

该实验场景与6.2.2 节相同，区别在于Rsync 使用常规策略检查模式。hcsync 与使用常规策略Rsync 的同步性能对比如表5 和图8 所示。传统的Rsync 同步算法需要对每个文件数据进行分块、校验码的计算及匹配。

表5 hcsync 与使用常规策略Rsync 的同步性能对比Table 5 Synchronization performance comparison of hcsync and Rsync using general policy

图8 hcsync 与使用常规策略Rsync 的同步时间对比Fig.8 Synchronization time comparison of hcsync and Rsync using general policy

从表5 和图8 可以看出，在常规策略下的Rsync同步过程可以确保数据的一致性，但是速度需减慢。这种情况下，Rsync 会进行大量强弱校验码的计算以及哈希表的匹配。随着文件库中文件数据的增加，耗费的资源与时间也逐渐增加，此时hcsync 平均加速比为69.99%。

基于哈希树的同步方法通过判断根节点哈希值快速获取文件库是否发生变化，利用构建的哈希树结构捕捉变化节点且跳过没有变化的节点，从而加快同步速度。htsync 平均加速比为38.70%。

hcsync 与htsync 同步效率都要高于Rsync，它们都避免了传统Rsync 中需要逐个对比文件数据的弊端，通过树形结构快速捕捉文件变化并进行同步。但哈希链与哈希树的区别在于：一个以时间顺序迭代哈希函数并不断延长链式结构，一个以目录结构创建的需要不断更新的树式结构。但哈希树的缺点是需要不断地维持和更新一个树形结构，即使是一个普通的文件更新，也需从叶子节点溯源到根节点并更新节点与哈希值。当文件库更新时，hcsync只需在哈希链上增加节点，对比两端哈希链节点h_id 即可获取并执行后续变化节点；htsync 则需要遍历比对两端哈希树定位到变化节点，然后从变化节点溯源到根节点并对这些节点进行更新。hcsync 在获取变化节点的效率与更新链式结构的效率上相较于htsync 与Rsync 有较大的提升。因此，hcsync 的同步时间均低于htsync 和Rsync，整体同步效率排序：hcsync＞htsync＞Rsync。

7 结束语

本文设计一种基于有序哈希链的文件数据同步方法hcsync。通过哈希链式结构实时获取并记录文件库数据的变化，以更加安全且稳定地完成端到端的同步传输，在提升同步效率的同时保证了数据的一致性、可追溯性和防篡改性。实验结果表明，在设计的三种实验场景下，hcsync 的同步时间平均加速比分别为94.85%、6.5% 和69.99%，相比htsync 和Rsync，能有效减少同步过程中时间以及资源的消耗，提升了同步效率。下一步将对同步时间和空间上的开销进行探索和改进［25］，实现更高效、更安全的同步技术。