EdgeDup：基于流行度感知的高效通信去中心化边缘数据去重方案

《IEEE Transactions on Parallel and Distributed Systems》：EdgeDup: Popularity-aware Communication-efficient Decentralized Edge Data Deduplication

本文针对边缘存储系统中数据冗余严重、现有去重方法依赖云控导致延迟高和可扩展性差的问题，提出了一种去中心化的边缘数据去重方案EdgeDup。该方案通过构建数据依赖索引，在考虑数据流行度的同时实现跨服务器冗余识别与协同去重，显著降低了数据检索延迟（平均47.78%）并保持较高的去重率，为资源受限的边缘环境提供了高效可靠的存储优化方法。

　　

随着物联网和边缘计算的快速发展，越来越多的应用需要将数据和计算任务部署在靠近用户的边缘服务器上，以降低服务延迟。然而，边缘服务器的存储资源有限，而用户对热门数据（如社交网络上的病毒视频）的重复需求导致大量数据冗余存储在不同边缘服务器上。这种冗余不仅浪费了宝贵的存储空间，还增加了管理复杂度。数据去重技术原本是为云存储系统设计的，能够通过删除重复数据来节省存储空间，但在边缘计算环境中直接应用会遇到新的挑战。

现有的边缘数据去重方法大多依赖云端集中控制，即由云服务器收集所有边缘服务器的存储信息和数据流行度，进行全局优化后下发去重策略。这种方法在实际应用中存在明显缺陷：首先，频繁的边缘-云通信会给回传网络带来沉重负担；其次，由于网络延迟和计算耗时，云服务器生成的去重策略在到达边缘时可能已经过时，无法适应动态变化的边缘环境；再者，集中式方法的系统鲁棒性较差，一旦边缘服务器发生故障或网络拓扑变化，原有策略可能失效甚至导致数据不可用。

更关键的是，现有方法往往忽视数据流行度对用户体验的影响。如图1所示，当六个边缘服务器上的数据流行度分别为{4, 2, 1, 0, 2, 1}时，不考虑流行度的传统EDD方案平均检索延迟为0.70，而考虑流行度的EdgeDup方案可将延迟降至0.40，同时保持相同的去重率（60%）。在真实的边缘计算场景中，系统规模更大、拓扑更复杂，找到合适的流行度感知去重方案并非易事。

为了解决这些问题，华中科技大学的研究团队在《IEEE Transactions on Parallel and Distributed Systems》上发表了题为"EdgeDup: Popularity-aware Communication-efficient Decentralized Edge Data Deduplication"的研究论文，提出了一种全新的去中心化边缘数据去重方案EdgeDup。

EdgeDup的核心技术方法包括三个方面：首先，通过分布式决策机制实现跨边缘服务器的冗余数据识别，避免依赖云控；其次，基于数据流行度进行去重决策，优先保留高流行度数据副本以降低检索延迟；第三，设计了一种创新的数据依赖索引系统（包含供应服务器列表LSS和需求服务器列表LDS），显著减少了去重过程中的通信开销。研究人员在包含95,562个基站的真实世界EUA数据集上进行了实验，通过随机图模型构建了不同规模和网络密度的边缘存储系统测试环境，使用Twitter Trace作为用户请求数据源，对比了EdgeDup与多种现有方法的性能差异。

研究结果显示，EdgeDup在保持接近最优去重率（64.94%）的同时，将数据检索延迟降至12.65毫秒，相比随机去重、MEAN和Ripple等现有方法，延迟分别降低了81.39%、52.96%和41.29%。这一性能优势在各种测试场景下均保持稳定。

系统设计与实现

EdgeDup采用完全去中心化的架构，边缘服务器通过本地交互协作完成去重决策。当某个边缘服务器的存储利用率达到阈值（如80%）时，它会成为决策发起者，收集周边L跳范围内（基于延迟约束L）服务器的数据存储和流行度信息。基于这些信息，决策服务器运行流行度感知的去重算法（算法1），确定哪些数据副本可以安全删除而不影响数据可用性。

数据依赖索引机制

为了解决去中心化去重中的通信开销问题，EdgeDup设计了创新的数据依赖索引系统。每个边缘服务器维护两个核心列表：供应服务器列表(LSS)记录能够提供特定数据的邻居服务器；需求服务器列表(LDS)记录依赖该服务器提供数据的邻居节点。这一机制使得边缘服务器在决定是否删除数据时，只需与LDS中记录的真正需求方进行权限确认，而不需要与所有邻居通信，大幅降低了通信开销。

去重决策执行过程

EdgeDup的去重过程分为决策制定和决策执行两个阶段。在决策执行阶段，边缘服务器通过预删除确认流程（算法2）确保数据删除不会影响系统可用性。只有当所有依赖该数据的需求方确认存在替代数据源时，才会执行删除操作。这种机制有效防止了错误删除和数据不可用的情况。

性能优化效果

实验结果表明，EdgeDup在通信效率方面表现突出。随着系统规模扩大，EdgeDup的通信开销增长远低于对比方法Ripple。当边缘服务器数量从15增加到75时，Ripple的通信开销增长显著，而EdgeDup得益于数据依赖索引，开销增长较为平缓。在网络密度（ρ）从0.07增加到0.21时，Ripple的通信开销增加5.6倍，而EdgeDup仅增加3.56倍。

系统鲁棒性评估

在动态边缘环境下，EdgeDup展现出良好的适应性。当新增边缘服务器或部分服务器发生故障时，只有受影响区域的拓扑关系需要更新，其他区域不受影响。即使存在数据流行度预测偏差，EdgeDup通过结合实际访问统计和自适应反馈机制，仍能保持较低的数据检索延迟。

理论研究证明，EdgeDup的去重决策问题属于单调子模最大化问题，其贪心算法能够达到(1-1/e)的最优近似比，确保了去重效果的理论保证。计算复杂度分析表明，EdgeDup的决策复杂度与数据项数量成线性关系，适用于大规模边缘计算场景。

EdgeDup的研究对边缘计算领域具有重要意义。它首次在去中心化边缘数据去重中同时考虑了数据流行度和通信效率，解决了现有方法在实用性和性能方面的关键局限。通过数据依赖索引机制，EdgeDup在保证数据可用性的前提下，显著降低了去重过程的通信开销，为资源受限的边缘环境提供了可行的存储优化方案。

这项研究的创新点在于将去重决策权下放到边缘服务器，通过本地化协作而非云端集中控制，更好地适应了边缘环境的动态特性。实验结果表明，EdgeDup不仅在实际性能上优于现有方法，还具备良好的可扩展性和鲁棒性，能够适应不同规模的边缘存储系统。

未来工作可以进一步探索EdgeDup在更复杂边缘场景下的应用，如移动边缘计算、车辆边缘网络等动态性更强的环境。同时，如何将机器学习技术更深入地融入数据流行度预测和去重决策过程，也是值得研究的方向。EdgeDup的成功实践为边缘存储系统的优化提供了新思路，推动了边缘计算从理论走向实用化的重要一步。