# 目录差异分析 **Repository Path**: gxj777/find_dir_diff ## Basic Information - **Project Name**: 目录差异分析 - **Description**: nullnullnull - **Primary Language**: Unknown - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2024-07-03 - **Last Updated**: 2025-10-13 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README 差分备份 基于全备份： 差分备份总是基于上次全备份进行。它保存自上次全备份以来发生变化的所有数据。 恢复速度快： 恢复数据时，只需要最新的全备份和最新的差分备份。 eg: 星期一晚上：执行全备份，备份文件包含所有数据。 星期二白天：执行差分备份，备份文件包含自星期一晚上以来的所有更改。 星期三白天：执行差分备份，备份文件包含自星期一晚上以来的所有更改（包括星期二和星期三的更改）。 src文件夹为核心代码， threadpool.cpp为线程池的代码，其中每个工作线程的线程函数是从任务队列(每个任务对比的一对目录或者是对比的一对同名文件)取一个任务执行。 对比目录： 读取左右两边两个目录的目录项然后做匹配操作，其中左右两边都有相同的目录则作为新的任务加入到任务队列中，由新的工作线程进行对比操作； 左边有而右边没有的文件和目录则是被删除的，记录到差异文件diff.txt中； 左边没有而右边有的文件和目录则是新增加的，记录到差异文件中和delta中。 左右两边都有的文件也作为新的任务加入到任务队列中，交给其他工作线程进行对比。 对比文件： 分块计算每一块的hash值，然后对比差异 注意：写差异文件和差异数据是同时进行的，保证顺序的一致性。写一行modify信息则同时需要把修改后的数据写入delta中，在写delta时先写差异数据的大小，然后再紧跟差异的数据。 新增文件的信息也是如此。删除文件的不对应有写delta的操作。 backup.cpp是实现A目录全备份的代码 blockhash.cpp是实现两个同名文件找出差异部分的代码，思路是按照指定大小将文件切块，计算每一块的hash值，然后根据hash值是否相同判断是否被修改。记录修改的区间信息，然后将差异信息写到diff.txt和delta中 mergediff.cpp是思想合并差异信息的代码，包括合并一个文件的两次修改(A1中的某个文件在A2中修改了，然后在A3中又被修改了)；合并删除和新增的文件信息 parseDifffile.cpp是解析diff.txt的代码，将文件中记录的差异信息读取到内存中，为了合并两个diff.txt中信息。 sava_diff.cpp是保存差异信息到文件的代码。 test下面为测试代码 test_dircmp.cpp为线程池版本的测试 dir.cpp为单线程两个hash表匹配的测试 编译命令: g++ test_dircmp.cpp ../src/threadpool.cpp ../src/mergediff.cpp ../src/parseDifffile.cpp ../src/backup.cpp ../src/block_hash.cpp -o dir_test1 -std=c++17 -lssl -lcrypto -g g++ dir.cpp ../src/compare_directories.cpp ../src/block_hash.cpp -o dir_test2 -std=c++17 -lssl -lcrypto -g 运行 ./create_structure.sh 生成测试目录A1 (17G) 拷贝A1: cp -r A1 A2 然后在A2中做点修改 测试结果： ❯ time ./dir_test1 A1 A2 compare diretories finished ./dir_test1 A1 A2 1.90s user 1.52s system 99% cpu 3.421 total ❯ time ./dir_test1 A1 A2 compare diretories finished ./dir_test1 A1 A2 1.78s user 1.58s system 99% cpu 3.359 total ❯ time ./dir_test1 A1 A2 compare diretories finished ./dir_test1 A1 A2 1.89s user 1.45s system 99% cpu 3.353 total ❯ time ./dir_test1 A1 A2 compare diretories finished ./dir_test1 A1 A2 1.81s user 1.53s system 99% cpu 3.343 total ❯ time ./dir_test2 A1 A2 ./dir_test2 A1 A2 1.98s user 2.09s system 99% cpu 4.072 total ❯ time ./dir_test2 A1 A2 ./dir_test2 A1 A2 2.18s user 2.63s system 99% cpu 4.817 total ❯ time ./dir_test2 A1 A2 ./dir_test2 A1 A2 2.22s user 2.63s system 99% cpu 4.850 total ❯ time ./dir_test2 A1 A2 ./dir_test2 A1 A2 2.06s user 2.73s system 99% cpu 4.791 total 最终选用多线程的版本。 三种情况：全备份，模拟差异备份，提供数据目录A1、A2和A3, 根据A1->A2的修改, A2->A3的修改得到A1->A3的修改。 ./dir_test1 -f dirPath backupPath 模拟全量备份dirPath至backupPath ./dir_test1 -d dirPath1 dirPath2 模拟普通差分备份, 备份数据目录为dirPath1_backup, 目录下保存有一个文本文件b(diff.txt)和一个目录c。 文本文件保存了该备份的文件或目录的状态信息。 目录c下保存了具体文件的变化。修改的文件按照修改块的size直接追加到一起(这句话不太理解？是否变化的每个文件都存一个变化)。 ./dir_test1 -m dirPath1 dirPath2 dirPath3 提供数据目录A1、A2和A3, 需要分析数据目录A2和A1的差异, 输出备份数据1。 然后分析A3和A2的差异, 并在备份数据1的基础上叠加差异, 输出备份数据2。不允许直接获取A3和A1的差异。 读取差异文件和delta文件，从文件到内存中修改集合 diff和delta是一一对应的 两个文件结合->得到修改集合 delete 不用管delta文件的处理 add 则需要去读取delta当前位置的8B，读写指针再+size modify 读diff可以得到修改的区间，，读取delta当前位置的8B的size，然后当前delta的位置则是修改后数据的offset， 读写指针再+size 对于这个modify， 1-100 改为 1-98, diff记录(1 100),然后从delta文件当前位置读8B得到修改后内容的大小, 从而替换 diff.txt的格式： (delete) && (A1/subdir5) (add) && (A2/subdir4/addfile1.txt) || (0 0) (modified) && (A1/subdir1/modify.txt) || ((256 384) || (384 512)) (delete) && (A1/subdir3/subdir3-2/subdir3-2-1/size3_file1) (modified) && (A1/subdir4/subdir4-4/subdir4-4-2/subdir4-4-2-4/testmod.txt) || ((0 128)) delta文件的格式，size(8字节)后紧跟size长度的数据 size1|data1|size2|data2|size3|data3 diff文件结合delta文件得到修改集合 diff中一行是delete，不用delta文件处理, 记录删除信息 diff中一行是add， 则需要去读取delta当前位置的8B(读写指针会移动8B到data1的位置)， 然后记录当前读写指针的offset表示新增数据在delta中偏移量，读写指针再+size指向下一个 得到add信息：startpos，增加数据在delta的offset，新增数据的size diff中一行是modify，读diff可以得到修改的区间， 每个区间都读取delta当前位置的8B的size，然后当前delta的位置则是修改后数据的offset， 读写指针再+size 得到modify信息：startpos，被修改数据的size，修改后数据的在delta的offset，修改数据的size 存储删除信息的数据结构，用set方便查找 std::unordered_set& del, 存储新增信息 std::unordered_set, TupleHash, TupleEqual>& added, 存储修改信息 std::unordered_map>>& modified 调用loadDiff得到修改的集合1，修改的集合2 for (auto [file, modify1_vector] : modified1) { if (file in modified2) { MergeDiff(modify1_vector， modify2_vector，) // 合并两次修改 } } ## LCS方法优化 采用lcs求两个文件的公共序列，找到两个文件的相同的部分，从而求出不同的部分。对于lcs_diff.cpp threadpool_opt即使用该优化的线程池 相比与分块hash的方法，这样可以更细粒度的找到差异的部分，减小delta中存储的差异部分的大小，但lcs也有开销。 测试代码为dir_testcmpopt 编译： g++ test_dircmpopt.cpp ../src/threadpool_opt.cpp ../src/mergediff.cpp ../src/parseDifffile.cpp ../src/backup.cpp ../src/save_diff.cpp ../src/lcs_diff.cpp -o dir_test_opt -std=c++17 -lssl -lcrypto -g 分块hash的测试为dir_testcmp g++ test_dircmp.cpp ../src/threadpool.cpp ../src/mergediff.cpp ../src/parseDifffile.cpp ../src/backup.cpp ../src/save_diff.cpp ../src/block_hash.cpp -o dir_test -std=c++17 -lssl -lcrypto -g 测试发现,LCS(时间复杂度为O(N^2))带来的开销还是很大的。时间换空间 ❯ ./dir_test -d A1 A2 compare diretories finished Program execution time: 5.28852 seconds. ❯ ./dir_test_opt -d A1 A2 Program execution time: 19.2359 seconds. ❯ ./dir_test -d A2 A3 compare diretories finished Program execution time: 5.13879 seconds. ❯ ./dir_test_opt -d A2 A3 Program execution time: 18.659 seconds. ❯ ./dir_test -m A1 A2 A3 compare diretories finished compare diretories finished Program execution time: 9.35646 seconds. ❯ ./dir_test -m A1 A2 A3 compare diretories finished compare diretories finished Program execution time: 9.35646 seconds. ❯ ./dir_test_opt -m A1 A2 A3 Program execution time: 38.3917 seconds. ## oh环境, (链接: https://pan.baidu.com/s/1R5Lz_GmjXE6Xtviqsp1WEg 提取码: 4x74 是编译好的包含该功能的镜像，可直接烧录) 标准系统，3568开发板 设备开发文档：https://docs.openharmony.cn/pages/v4.1/zh-cn/device-dev/device-dev-guide.md 快速入门中，根据情况选择基于IDE或者命令行开发这两种方式的一种 step1：准备开发环境，Ubuntu虚拟机就行，硬盘差不多需要150g step2：安装库和工具集，根据文档弄。或者用他提供的编译环境docker镜像(建议)：https://docs.openharmony.cn/pages/v4.1/zh-cn/device-dev/get-code/gettools-acquire.md 中的搭建Docker环境（标准系统） step3：获取源码，推荐从镜像站点获取 https://docs.openharmony.cn/pages/v4.1/zh-cn/device-dev/get-code/sourcecode-acquire.md文档中的方式3，选择全新代码(标准、轻量和小型系统),  复制下载链接然后wget，下载完成后对比下校验码是否一致。 step4：安装编译工具，只用安装hb就行，用docker就不用。 step5：编译，参考文档： https://docs.openharmony.cn/pages/v4.1/zh-cn/device-dev/quick-start/quickstart-pkg-3568-build.md docker参考https://docs.openharmony.cn/pages/v4.1/zh-cn/device-dev/quick-start/quickstart-pkg-3568-build.md 系统编译成功后，根据hello world的例子，将本项目代码移植到oh中。可参考当前的sample目录。 subsystem_config是openharmony中在build/subsystem_config.json中添加新建的子系统的配置 config.json是openharmony中在vendor/hihope/rk3568/config.json 然后执行编译(前提是系统编译成功)，编译该模块 hb build -T dirdiff --fast-rebuild 编译成功后，在路径 out/rk3568/packages/phone/images 目录里下载镜像然后烧录 参考：https://gitee.com/hihope_iot/docs/blob/master/HiHope_DAYU200/docs/%E7%83%A7%E5%BD%95%E6%8C%87%E5%AF%BC%E6%96%87%E6%A1%A3.md