背景与动机
数据去重作为一种经典的数据缩减技术，在云存储系统中得到了广泛的应用，为提高边缘存储系统的资源利用率提供了一个有效的解决方案。然而，边缘计算环境的独有特性，如边缘服务器的地理分布、覆盖范围和数据的低检索延迟需求，使得传统的云数据去重方法无法直接应用。此外，现有的边缘数据去重策略为了追求最大的数据去重率，往往会删除大量的数据副本。由于边缘服务器的资源异构性，使得去重后的数据分布面临负载不均衡的问题。这种负载不均衡会导致数据被聚集在特定的边缘服务器上，使得数据读写不均从而增加了硬件失效的发生概率，增加了系统维护的硬件和人力成本。与此同时，数据负载不均衡将会大大损害新数据的存储需求，间接增加了数据的存储成本。为此，本文提出了负载均衡感知的边缘数据去重方法，系统地考虑了数据去重率、检索延迟和资源负载均衡等因素。
论文链接：https://doi.org/10.1109/TPDS.2023.3247061论文《Enabling Balanced Data Deduplication in Mobile Edge Computing》发表在《IEEE Transactions on Parallel and Distributed Systems》期刊上。TPDS是计算机高性能计算领域的顶级期刊，同时也是中国计算机学会（CCF）推荐A类国际期刊。
方法
图1 边缘存储系统数据分布
我们对该问题进行形式化定义与抽象，将数据去重率、数据检索延迟和负载均衡指数这三个优化目标进行归一化整合为系统去重收益，构建了一个以最大化系统收益为目标，以边缘服务器覆盖范围和数据检索延迟为约束的整数线性规划模型。首先，我们从经典的NP难问题——背包（BP）问题着手，通过规约理论证明了BEDD问题是一个NP难问题。然后，我们给出了一种最优方法，即采用整数规划求解器CPLEX设计的最优算法BEDD-O；
图2 边缘数据去重方案
针对BEDD-O方法在大规模边缘场景下的计算开销大的问题，我们进一步设计了一种可应用于大规模场景快速求解的BEDD-A近似算法。首先通过拉格朗日松弛将问题模型进行简化，通过迭代更新拉格朗日乘子，找到原问题的下界解。拉格朗日松弛方法的典型应用需要估计原始问题的上界解的值，并使用一个固定步长调整因子来更新拉格朗日乘子。这通常会减慢甚至破坏算法收敛。在BEDD问题中，一些约束导致上界解不能被准确估计。为了解决这些问题，BEDD-A算法采用了一种自适应的步长更新机制，可以以更细粒度的方式迭代地调整上界。随着调整次数的增加，减小算法的更新步长。通过这种调整机制使BEDD-A算法的收敛速度快于传统的Polyak更新方法。最后，设计了一种贪心舍入算法，将BEDD-A算法求得的非整数解转化为整数解，从而实现问题的最终求解。为了确保算法的有效性，我们从理论上证明了BEDD-A算法是可收敛的。
评价和结果
图4. 小规模实验下不同方法的去重收益
图5. 小规模实验下不同方法的时间开销论文在真实数据集上对提出的两种方法分别进行了小规模和大规模实验。小规模的实验结果如图4和图5所示，其可以充分验证BEDD-O的有效性，同时BEDD-O的高计算开销也证明了这是一个NP难问题。大规模实验结果如图6和图7所示。在具有250个边缘节点的场景下求解该问题只需要1.55秒的计算开销，证明了BEDD-A方法的有效性和高效率。综上所述，我们提出的两种负载均衡感知的边缘数据去重方法能够在保证低时间开销的同时，有效降低数据存储量，并且实现数据存储的负载均衡。
图6. 大规模实验下不同方法的去重收益
图7. 大规模实验下不同方法的时间开销
技术贡献
本文在满足移动边缘计算环境中独特约束条件的同时，考虑到数据去重率、数据存储效益和存储负载平衡，提出、制定和解决了负载均衡感知的边缘数据重复数据删除（BEDD）问题，且证明了它是NP难的。本文设计了基于整数规划方法的BEDD-O和改进的拉格朗日松弛迭代方法BEDD-A，分别用于求解小规模和大规模的BEDD问题。理论分析与实验结果表明所提方法较于对比方法具有显著性能提升。该项研究为边缘存储系统资源优化提供了新的思路与解决方案，对于边缘应用的开发部署具有重要意义。
详细内容参见
Ruikun Luo, Hai Jin, Qiang He, Song Wu, and Xiaoyu Xia. “Enabling Balanced Data Deduplication in Mobile Edge Computing.” IEEE Transactions on Parallel and Distributed Systems, vol. 34, no. 5, pp. 1420-1431, 2023.https://ieeexplore.ieee.org/abstract/document/10049532
作者介绍
罗瑞坤，华中科技大学博士后，于2023年在华中科技大学获得博士学位。主要从事边缘计算、数据存储管理等方面的研究工作，相关工作发表在TPDS、TSC、ICSOC等国际期刊和会议。参与与边缘计算相关的重点研发计划和自然科学基金重点项目等科研项目多项，担任TSC、TCOM、T-ASE、TCE、TETC、CCPE和IoTJ等多个国际期刊审稿人。
金海，华中科技大学教授，博导，国家级人才计划入选者，CCF“王选奖”获得者。中国计算机学会副理事长/会士，IEEE Fellow，华中科技大学“大数据技术与系统国家地方联合工程研究中心”主任、“服务计算技术与系统教育部重点实验室”主任。国务院特殊津贴专家。十三五 “云计算与大数据”国家重点研发计划专家组副组长、十四五“先进计算与新兴软件”国家重点研发计划专家组组长。湖北省计算机学会理事长。教育部“长江学者和创新团队发展计划”创新团队学术带头人。主要研究方向为计算机体系结构、并行与分布式处理、虚拟化技术与云计算、大数据、网络安全等。
何强，华中科技大学教授，博导，国家级青年人才计划入选者，获得华中科技大学-澳大利亚斯威本科技大学双博士学位，曾在澳大利亚斯威本科技大学任讲师、高级讲师和副教授，主持和参与国家级科研项目7项，在CCF A类会议和期刊上发表高水平学术论文60余篇，在ACM/IEEE Transactions上发表论文80余篇，5次获国际会议最佳论文奖和最佳学生论文奖，3次获得校级杰出科研奖，培养的博士生3次获得优秀博士生奖，主要研究方向包括边缘计算、云计算和服务计算。
吴松，华中科技大学二级教授，博导，计算机学院副院长，服务计算技术与系统教育部重点实验室副主任，国家科技创新领军人才、教育部新世纪优秀人才、华中卓越学者、中国计算机学会杰出会员。获国家自然科学二等奖1项、国家科技进步二等奖1项、省部级科技一等奖3项。长期从事云计算与虚拟化领域的研究，主持国家自然科学基金重点项目等国家级科研课题十余项，发表重要会议和期刊论文200余篇，获国内外发明专利授权50余项（含美国专利6项），研究成果广泛应用于包括腾讯、华为、阿里、微软、曙光、浪潮等云计算企业。主要研究方向为操作系统、云计算资源调度、系统虚拟化等。
夏啸宇，现任澳大利亚皇家墨尔本理工大学讲师，致力于边缘计算、服务计算及可持续计算的研究。他在澳大利亚墨尔本大学于2015年获得硕士学位，并在澳大利亚迪肯大学于2022年获得博士学位。他在国际知名期刊和会议如IEEE TPDS、TMC、TSC、WWW等发表了多篇高影响力论文。作为多项顶级国际期刊和会议的审稿人，他活跃于IEEE TPDS、TMC、TSC、TNET、TKDE、TDSC、WWW、MM、ICDCS等，并在2023至2025年间担任TPDS审稿委员会成员。