Replicated tree data structures are extensively used in collaborative applications and distributed file systems, where clients often perform move operations. Local move operations at different replicas may be safe. However, remote move operations may not be safe. When clients perform arbitrary move operations concurrently on different replicas, it could result in various bugs, making this operation challenging to implement. Previous work has revealed bugs such as data duplication and cycling in replicated trees. In this paper, we present an efficient algorithm to perform move operations on the distributed replicated tree while ensuring eventual consistency. The proposed technique is primarily concerned with resolving conflicts efficiently, requires no interaction between replicas, and works well with network partitions. We use the last write win semantics for conflict resolution based on globally unique timestamps of operations. The proposed solution requires only one compensation operation to avoid cycles being formed when move operations are applied. The proposed approach achieves an effective speedup of 68.19$\times$ over the state-of-the-art approach in a geo-replicated setting on Microsoft Azure standard instances at three different continents.
翻译:复制的树数据结构被广泛用于合作应用程序和分布式文件系统,客户经常在这些系统中进行移动操作。在不同复制品中进行本地迁移操作可能比较安全。然而,远程迁移操作可能并不安全。当客户在不同复制品中同时任意移动操作时,可能会造成各种错误,使这项操作难以执行。先前的工作揭示了数据重复和复制树循环等错误。在本文中,我们提出了一个高效的算法,以便在分布式复制的树上进行操作,同时确保最终的一致性。拟议技术主要涉及有效解决冲突,要求复制品之间没有互动,并且与网络分区运作良好。我们使用最新的写赢语义,以基于全球独特的操作时间标记解决冲突。拟议解决方案只需要一个补偿操作,以避免移动操作时形成周期。在三个不同大陆的Microsoft Azure标准情况下,拟议方法在实时复制的地理设置中,有效加快了68.19美元。