Efficient Synchronization of State-Based CRDTs
Efficient Synchronization of State-Based CRDTs
复制标题
基于状态的 CRDT 的高效同步
DOI：
10.1109/icde.2019.00022
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
J. Leitao
中科院分区：
文献类型：
--
作者：
Vitor Enes;Paulo Sérgio Almeida;Carlos Baquero;J. Leitao
为了确保大规模分布式系统的高可用性，无副本复制数据类型（CRDTs）通过允许在本地副本上进行即时查询和更新操作来放松一致性，而不需要远程同步。基于状态的CRDT通过定期将副本的完整状态发送到其他副本来同步副本，随着CRDT状态的增长，这可能会变得非常昂贵。基于增量的CRDT通过产生用于同步的小增量状态（增量）而不是完整状态来解决这个问题。然而，目前的基于增量的CRDT同步算法会导致冗余浪费的增量传播，表现比预期的差，令人惊讶的是，没有比基于状态的更好。在本文中，我们：1）找出当前基于增量的CRDT同步算法效率低下的两个原因; 2）将连接分解的概念引入到基于状态的CRDT中; 3）利用连接分解获得最优增量; 4）提高同步算法的效率; 5）实验评估改进后的算法。
To ensure high availability in large scale distributed systems, Conflict-free Replicated Data Types (CRDTs) relax consistency by allowing immediate query and update operations at the local replica, with no need for remote synchronization. State-based CRDTs synchronize replicas by periodically sending their full state to other replicas, which can become extremely costly as the CRDT state grows. Delta-based CRDTs address this problem by producing small incremental states (deltas) to be used in synchronization instead of the full state. However, current synchronization algorithms for delta-based CRDTs induce redundant wasteful delta propagation, performing worse than expected, and surprisingly, no better than state-based. In this paper we: 1) identify two sources of inefficiency in current synchronization algorithms for delta-based CRDTs; 2) bring the concept of join decomposition to state-based CRDTs; 3) exploit join decompositions to obtain optimal deltas and 4) improve the efficiency of synchronization algorithms; and finally, 5) experimentally evaluate the improved algorithms.