Research On Design Techniques For Conflict-free Replicated Data Types

The development of Internet applications has resulted in an enormous number of users and massive data of various types.To improve the scalability and fault tolerance,and reduce the delay of service,the underlying data storage of online applications chooses data replication technology.However,replicating distributed data brings the data consistency problem.Because of the intrinsic tradeoff indicated in the CAP theorem and the high availability requirements,modern online applications often choose eventual consistency.Conflict-free Replicated Data Type(CRDT)is a simple and theoretically sound approach to providing eventual consistency.However,existing CRDT designs are often tricky and hard to extend to other data types.To address this challenge,the Remove-Win design Framework(RWF)employs a competent remove-win strategy to resolve conflicts among concurrent updates,and specifies a systematic design framework for conflict-free replicated data types(RWF-DTs).RWF is proposed recently,and how to explore the potential of RWF and design new CRDT based on RWF has become a challenging problem.A generic algorithm skeleton for RWF-DT design is provided by RWF,whose core is the RWF-Set.In order to design the key principle of conflict resolution,the focus of RWF-Set is mainly the conflict resolution among basic insert/delete operations.Thus,oversimplified operations limit the application scenarios of RWF-Set.Moreover,exemplar implementations based on RWF are in great need,and more CRDT designs following RWF are in great need to show the generic design for RWF-DTs.To address challenges above,binary operations(Union,Intersection and Complement)of RWF-Set are proposed and implemented,and RWF-Tree is designed and implemented.Specifically,the main contributions of this work are:First,this work proposes binary operations design of RWF-Set,which is based on add and remove operations of RWF-Set.By converting binary operations to add and remove operations,we design the algorithm of binary operations and prove the correctness.Then,according to the examples of conflict resolution,we present the semantic characteristics of RWF-Set binary operations.Second,this work proposes the design of RWF-Tree.We define the system model of RWF-Tree,based on the system of Tree data type and the cases of conflict.Then we design the algorithm of RWF-Tree operations,which is able to resolve concurrent conflict automatically.In the end,we show the conflict resolution strategy by concurrent conflict resolution examples of RWF-Tree.Finally,this work implements RWF-Set and RWF-Tree,and measures their performance.Based on Redis,a popular NoSQL database,RWF provides an implementation platform of RWF-DTs.We implement RWF-Set and RWF-Tree over the platform,which reduces the development effort.We design a local sandbox experiment to measure the performance of RWF-Set and RWF-Tree.We measure the performance of RWF-Set,and compare the result with other existing conflict-free replicated Set data types.The comparison shows that the data consistency of RWF-Set is comparable to other conflict-free replicated Set data types,while the meta-data overhead is low.Meanwhile,we measure the performance of RWF-Tree by comprehensively tuning experiment parameters.The experiment rusults show that the performance of RWF-Tree in terms of data consistency and meta-data overhead is competent.