赛题3：高性能应用目录差异分析服务项目说明文档

队伍信息

队伍名称：鸿蒙ix

指导教师：李少峰

队伍成员：董金辉、赵景齐、卢晓琴

赛道：系统创新赛道

赛题：赛题3：高性能应用目录差异分析服务

赛题完成情况及算法思想

1.全量备份（模拟全量备份）

提供数据目录A1，并对数据目录进行全量备份，注意保留相关的备份数据分析信息。

完成情况

程序能够对指定目录进行全量备份，同时为每个文件生成哈希码，作为备份数据分析信息。完成题目要求的功能。

算法思想

• 为尽可能提高性能，充分利用rk3568开发板CPU的四个核心，通过C++多线程技术，使用4个内核级线程并发执行。
• 4个线程对数据目录进行层序遍历以完成拷贝。具体而言，初始时将备份目录的路径加入队列中，每个线程从共享队列中取出一个路径，通过字符串操作生成相对于数据目录的相对路径，以及该文件或目录在备份目录中的路径。若路径为子目录，首先在备份目录中递归创建目录结构，接着遍历子目录中的文件，将文件路径加入队列中；若路径为文件，则拷贝文件至备份目录，拷贝内容的同时，还拷贝文件的创建时间、修改时间、权限等元数据，最后生成该文件的哈希码并写入备份目录的文本文件中。
• 通过BLAKE2b算法生成哈希码并写入文件，能够提高比对文件内容的速度，提高后续差分备份中差异分析的性能。

  运行效果

  数据目录A下有文件夹1…5，每个文件夹的总大小为1GB。 文件夹1下有一个1GB的文件 文件夹2下有两个文件夹(称作2阶文件夹)，每个文件夹下有两个256MB的文件 文件夹3下有3个文件夹(称作2阶文件夹)，每个2阶文件夹下有3个文件夹(称作3阶文件夹)，每个3阶文件夹下有3个38MB的文件 以此类推，文件夹5下有5个文件夹(称作2阶文件夹)，每个2阶文件夹下有5个3阶文件夹….一直到5阶文件夹，文件夹下有5个文件

全量备份5GB大小的A目录总共用时约228秒，在系统服务目录data/Backup_Service下生成文件夹A_2017_08_05_15_16_59，其中子目录data存放备份的文件及目录，A.hash存放每个文件的哈希码，如下图所示。

2.差分备份1（模拟普通差分备份）

提供数据目录A1和A2，需要分析数据目录A2和A1的差异，并进行差分备份，输出A2和A1间的差异数据全集。建议将大文件进行适当粒度的分块（4KB起步）。

完成情况

程序能够分析并输出两个目录的所有差异，包括文件的删除、新增与修改，以及空目录的新增和删除，能够将差异文件及其所在目录结构进行拷贝备份。

算法思想

准备工作

• 读取上次全量备份生成的分析信息文件，将全量备份的目录中每个文件的哈希码存入哈希表中

  核心算法：差异分析

• 为尽可能提高性能，使用两个内核级线程并发执行目录差异分析
• 线程1递归遍历目录A1的所有子目录及文件，以找出发生删除和修改的文件或空目录。具体而言，对于文件或空目录，通过字符串操作生成该文件或空目录相对于数据目录A1的相对路径，以及该文件或空目录在数据目录A2中的路径(若存在)，接着访问文件或空目录在A2中的路径，若该文件或空目录不存在，则说明发生了删除，记录差异类型为“删除”及文件路径；否则比较两个文件的修改时间，若修改时间不同，则比较两个文件的哈希码，不同则说明文件内容发生了修改，记录差异类型为“修改”及修改后的文件路径；对于非空的子目录，则递归执行该差异分析函数。最后将差异记录在哈希表中。
• 线程2递归遍历目录A2的所有子目录及文件，以找出新增的文件或空目录。具体而言，对于文件或空目录，通过字符串操作生成该文件或空目录相对于数据目录A2的相对路径，以及该文件或空目录在数据目录A1中的路径(若存在)，接着访问文件或空目录在A2中的路径，若该文件或空目录不存在，则说明是新增的文件或空目录，记录差异类型为“新增”及新文件的路径；对于非空的子目录，则递归执行该差异分析函数。
• 最后输出差异信息并备份差异文件。具体而言，首先在系统服务目录data/Backup_Service下生成备份目录a、目录a下的文本文件b和目录c。接着遍历差异哈希表中的每个键值对，读取文件路径及变化类型，并追加到文件b中，接着先拷贝文件所在目录结构，再拷贝文件，完成差异文件的备份。

  运行效果

  数据目录A结构请参考1.全量备份（模拟全量备份）运行效果 现将目录A进行拷贝，生成目录B，并做如下操作：
• 删除目录B/5/1/1/1/1及其中的文件
• 在目录B/4/1/1/1下创建目录5，并在目录5下创建5个文件file_1.txt~file5.txt
• 修改B/3/1/1中3个文件file_1.txt~file_3.txt的内容

差分备份B目录用时约2秒，系统正确输出了A与B目录之间的全部差异，并在系统服务目录data/Backup_Service下生成备份目录a_AB_2017_08_05_15_27_26，其中文本文件b.txt保存了差异信息，目录c保存了差异文件及其所在目录结构的备份。运行结果如下图所示。

3.差分备份2（模拟备份过程中，数据目录有修改）

提供数据目录A1、A2和A3，需要分析数据目录A2和A1的差异，输出备份数据1。然后分析A3和A2的差异，并在备份数据1的基础上叠加差异，输出备份数据2。不允许直接获取A3和A1的差异。

完成情况

程序能够分析出A2、A3目录的所有差异，并根据先前全量备份和差分备份生成的备份数据分析信息，叠加分析出A1、A3目录的所有差异，包括文件的删除、新增与修改，以及空目录的新增和删除，并且能够将差异文件及其所在目录结构进行拷贝备份。支持扩展至多于3个时刻的目录的差分备份，具有较好的可扩展性，为鸿蒙系统备份与恢复功能的研发提供了便利。

算法思想

准备工作

• 读取上次全量备份生成的信息文件，将全量备份的目录A1中每个文件的哈希码存入哈希表hash_map中；
• 读取上次差分备份生成的差异信息文本b，将两个目录A1、A2的差异存入另一个哈希表diff1_2中；
• 使用2个线程并发分析目录A2和A3的差异并存入哈希表diff2_3中，算法思想详见2.差分备份1

  核心算法：差异叠加

• 使用两个线程并发执行目录差异叠加；
• 线程1遍历A1、A2的差异哈希表diff1_2中的每个键值对it，读取文件路径及差异类型type1，通过字符串操作生成该路径相对于数据目录A1的相对路径Path1，以及在数据目录A2和A3中的绝对路径Path2、Path3(若存在)；
• 将Path2、Path3作为键，访问A2、A3的差异哈希表diff2_3，若均不存在，则说明该文件在T1->T2时刻发生变化，T2->T3时刻未变化，则直接将该键值对it加入表diff1_3中；
• 否则读取2->3差异类型type2，按照下表进行分析，并叠加至入表diff1_3中

A1->A2的差异	A2->A3的差异	分析A1->A3的差异
删除	删除	不可能，不处理
删除	新增	需要对比两个文件的哈希码，不同则视为1->3发生修改，否则不变，不处理
删除	修改	不可能，不处理
新增	删除	不变，不处理
新增	新增	不可能，不处理
新增	修改	视为1->3新增的文件
修改	删除	视为1->3删除的文件
修改	新增	不可能，不处理
修改	修改	需要对比两个文件的哈希码，不同则视为1->3发生修改，否则不变，不处理

• 线程2遍历A2、A3的差异哈希表diff2_3中的每个键值对it，读取文件路径及差异类型type1，通过字符串操作生成该路径相对于数据目录A2的相对路径Path2，以及在数据目录A1和A3中的绝对路径Path1、Path3(若存在)；
• 将Path1、Path2作为键，访问A1、A2的差异哈希表diff1_2，若均不存在，则说明该文件在T2->T3时刻发生变化，T1->T2时刻未变化，则直接将该键值对it加入表diff1_3中
• 最后根据差异哈希表diff1_3输出差异信息并备份差异文件，算法思想详见2.差分备份1
• 该方法支持扩展至多于3个时刻的目录的差分备份，具有较强的可行性。具体而言，对于应用数据目录A1，首次备份时进行全量备份，接下来每次备份时，分析最新时刻Tn目录与相邻上一时刻T(n-1)目录的差异(差分备份1)，接着叠加T1到T(n-1)时刻目录的差异，生成T1到Tn时刻目录的差异(差分备份2)，如下图所示。

  运行效果

  数据目录A结构请参考1.全量备份（模拟全量备份）运行效果 数据目录B结构请参考2.差分备份1（模拟普通差分备份）运行效果 现将目录B进行拷贝，生成目录C，并做如下操作：
• 拷贝目录A/5/1/1/1/1及其中的文件至C/5/1/1/1/1，并修改C/5/1/1/1/1/file_1.txt(测试删除又新增且内容不变或变化的情况)
• 删除C/4/1/1/1/5中file_1.txt~file_4.txt 4个文件(测试新增又删除的情况)
• 修改C/4/1/1/1/5/file_5.txt文件的内容(测试新增又修改的情况)
• 删除C/3/1/1/file_1.txt(测试修改又删除的情况)
• 覆盖拷贝A/3/1/1/file_2.txt至C/3/1/1/file_2.txt(测试修改又修改为A目录原内容的情况)
• 修改C/3/1/1/file_3.txt的内容(测试修改又修改的情况)

叠加备份C目录用时约3秒，系统正确叠加并输出了A与C目录之间的全部差异，并生成备份目录a_AC_2017_08_05_15_32_35，其中文本文件b.txt保存了差异信息，目录c保存了差异文件及其所在目录结构的备份。

4.数据恢复

为彰显本备份方案对于数据恢复的可行性，我们直接实现了备份数据的恢复功能，备份与恢复功能相辅相成，更好地完善了系统功能。

完成情况

程序能够对任意方式备份(全量备份、差分备份、叠加备份)的文件及目录进行恢复，且可根据备份时间选择不同版本的数据进行恢复。通过多次差异分析及备份，验证了恢复数据的完整性和恢复程序的正确性。

算法思想

准备工作

• 通过读取系统服务目录下的日志文件log.txt，将备份记录读取并输出给用户；
• 用户通过编号选择要恢复的备份记录，读取备份方式、时间、原数据目录、备份目录、文件哈希值等信息；
• 根据备份方式选择对应的恢复程序

  核心算法

  对于全量备份方式的恢复

1. 若原数据目录路径不存在，则整体拷贝备份目录至原数据目录；
2. 若原数据目录路径存在，则通过目录差异分析(差异分析方法详见2.差分备份：差异分析算法)，分析原数据目录相对于备份目录的差异；
3. 根据差异信息，在原数据目录上对发生变化的文件及目录进行恢复，具体恢复方法如下：

差异类型	处理方法
原数据目录中新增的文件	若文件存在，则删除
原数据目录中新增的子目录	若路径存在，则递归删除
原数据目录中删除的文件	将该文件的备份并拷贝至原文件所在路径
原数据目录中删除的子目录	在原数据目录原位置中创建子目录
原数据目录中内容修改的文件	将该文件的备份并拷贝至原文件所在路径

对于其它备份方式(差分备份、叠加备份等)的恢复

1. 若原数据目录路径不存在，则在原位置创建该目录；
2. 若原数据目录路径存在，则递归删除该目录并重新创建；
3. 多线程拷贝本次备份基于的全量备份目录内容至原数据目录；
4. 通过读取备份目录下的差异信息文件，获得备份目录与全量备份目录的差异；
5. 根据差异信息，在原数据目录上对发生变化的文件及目录进行恢复，具体恢复方法如下：

差异类型	处理方法
新增的文件	将该文件的备份并拷贝至原文件所在路径
新增的子目录	在原数据目录原位置中创建子目录
删除的文件	若文件存在，则删除
删除的子目录	若路径存在，则递归删除
内容修改的文件	将该文件的备份并拷贝至原文件所在路径

运行效果

数据目录A结构请参考1.全量备份（模拟全量备份）运行效果 数据目录B结构请参考2.差分备份1（模拟普通差分备份）运行效果 数据目录C结构请参考3.差分备份2（模拟备份过程中，数据目录有修改）

现对目录A做如下操作：

• 新建子目录A/6，并在该子目录下随机生成两个文本文件new1.txt、new2.txt；(测试新增文件的识别情况)
• 将子目录A/3移动至子目录A/6中；(测试删除与新增目录及文件的识别情况)
• 修改A/1/file_1.txt的内容；(测试修改文件的识别情况)

现对目录B做如下操作：

• 递归删除目录B(测试恢复情况)

现对目录C做如下操作：

• 递归删除目录C(测试恢复情况)

待三个目录恢复完成后，做如下操作：

• 对当前目录A和目录B进行差分备份，比较本次备份输出的差异信息与恢复前两个目录差分备份的差异信息是否一致；
• 对当前目录A、B和C进行叠加备份，比较本次备份输出的差异信息与恢复前三个目录叠加备份的差异信息是否一致；

恢复全量备份的目录A用时约109秒，恢复差分备份的目录B用时约189秒，恢复叠加备份的目录C用时约191秒。恢复前后备份输出的差异信息完全一致，证明了恢复数据的完整性和正确性。 经测试，恢复前后备份输出的差异信息完全一致，证明了恢复数据的完整性和正确性，如下图所示。

项目结构及部署运行

项目结构

project
├── images      # 系统镜像文件
│   ├── boot_linux.img
│   ├── MiniLoaderAll.bin
│   ├── parameter.txt
│   ├── resource.img
│   ├── system.img
│   ├── uboot.img
│   ├── updater.img
│   ├── userdata.img
│   └── vendor.img
├── readme.md    # 项目说明文件
├── rk3568.json        # 系统配置文件
├── src        # 项目源代码文件
│   ├── add_backup        # 叠加备份
│   │   ├── BUILD.gn
│   │   ├── bundle.json
│   │   ├── include
│   │   │   ├── blake2.h
│   │   │   └── blake2-impl.h
│   │   └── src
│   │       ├── blake2b-ref.c
│   │       └── main.cpp
│   ├── data_generator        # 测试数据生成器
│   │   ├── BUILD.gn
│   │   ├── bundle.json
│   │   ├── include
│   │   └── src
│   │       └── main.cpp
│   ├── diff_backup        # 差分备份
│   │   ├── BUILD.gn
│   │   ├── bundle.json
│   │   ├── include
│   │   │   ├── blake2.h
│   │   │   └── blake2-impl.h
│   │   └── src
│   │       ├── blake2b-ref.c
│   │       └── main.cpp
│   ├── full_backup        # 全量备份
│   │   ├── BUILD.gn
│   │   ├── bundle.json
│   │   ├── include
│   │   │   ├── blake2.h
│   │   │   └── blake2-impl.h
│   │   └── src
│   │       ├── blake2b-ref.c
│   │       └── main.cpp
│   └── restore        # 数据恢复
│       ├── BUILD.gn
│       ├── bundle.json
│       ├── include
│       │   ├── blake2.h
│       │   └── blake2-impl.h
│       └── src
│           ├── blake2b-ref.c
│           └── main.cpp
└── subsystem_config.json        # 系统配置文件

17 directories, 39 files

部署运行

本项目基于OpenHarmony-v3.1-Release源码进行开发，为系统添加了名为mybackup的子系统及full_backup、add_backup、diff_backup、restore等4个部件，实现了系统服务的新增，备份数据均存放在/data/Backup_Service/目录下，其中存放每次备份的备份目录dirname_time及日志文件log.txt，接下来将介绍如何使用该系统服务。

1. 使用烧录软件将系统镜像烧录至rk3568开发板中；
2. 等待开发板出现系统画面，通过hdc shell或串口通信进入终端，通过cd指令把工作目录切换至需要备份的数据目录下，也可通过输入data_generator命令生成随机测试数据文件，数据目录depth建议设置为5；
3. 输入命令full_backup，并输入目录名称，对数据目录进行全量备份；
4. 输入命令diff_backup，接着选择全量备份的记录，最后输入第二目录名称，对两个数据目录进行差分备份；
5. 输入命令add_backup，接着选择全量备份的记录，接着选择差分备份或叠加备份的记录，最后输入第三目录名称，对三个数据目录进行叠加备份；
6. 输入命令restore，接着选择要恢复的备份数据记录，等待系统完成恢复即可；