Research On Weak Consistency Measurement For Key-value Stores

The proliferation of Internet applications has resulted in enormous amount of user data of various types.To improve system scalability and avoid single point of failure,modern Internet applications often choose to replicate data.However,replicating dis-tributed data introduces the intrinsic tradeoff between data consistency and availability when network partition occurs,as indicated in the CAP theorem.Modern Internet ap-plications often resort to weak consistency in order to ensure high availability and low latency of data access.NoSQL databases,such as the key-value store,are widely used to provide such weakly consistent data services.The wide use of weakly consistent key-value stores brings the challenge of mea-suring weak consistency.First,the notion of weak consistency encloses a large range of key-value store implementations.These implementations provide different weak con-sistency in various subtle ways,in different scenarios with various workloads.More-over,key-value stores allow users to tune the complex combinations of system parame-ters,which brings forth diverse forms of weak consistency and imposes great difficulty on consistency measurement.Second,the metric of consistency measurement should be independent of specific applications,in order to guarantee the wide applicability of the measurement techniques.Finally,the basic rationale behind the measurement tech-niques should be intuitive and easy to interpret.At the same time,the measurement should also be accurate and systematic,which will greatly facilitate the tradeoff be-tween data consistency and data access latency.To address problems above,this work proposes a new technique,which measures weak consistency based on the inversions in the data access traces.Specifically,the main contribution of this work includes:First,this work defines a new generalized consistency model called i-atomicity,which is based on counting the number of inversions in the data access traces.Then a verification algorithm is proposed to determine whether a given trace is i-atomic.We give the correctness proof of the algorithm,and further demonstrate that in certain types of scenarios,the cost of the verification algorithm is pseudo-polynomial.In the end,we show two practical optimizations which effectively increase the running efficiency of the algorithm.Second,this work measures weak consistency provided by a key-value store in the cloud platform based on i-atomicity.We setup a Cassandra cluster on Aliyun,as well as a local sandbox Cassandra cluster as a supplement.Then we obtain traces of differ-ent weak consistency by comprehensively tuning system and environment parameters.We measure weak consistency of these traces based on i-atomicity,and compare the results with existing measurement techniques k-atomicity and ?-atomicity.The com-parison shows that i-atomicity gets a relatively obvious advantage over existing models in sensibility and comprehensiveness to various data access traces obtained in different configuration of environments and system parameters.Finally,this work measures weak consistency of a key-value store in the mo-bile platform.We design and implement a mobile coordination middleware MDSM,which enables efficient consistency-latency tradeoff for mobile collaboration applica-tions.Then we implement a multi-player mobile gaming application based on MDSM,and measure the execution traces of the application running under different configura-tions.Comparing the measurement results of i-atomicity with those of existing mea-surement techniques,we also find that i-atomicity is better in terms of the sensibility and comprehensiveness of consistency measurement.