基于操作历史图的分布式Key-Value数据库一致性检测算法

Consistency Checking Algorithm for Distributed Key-Value Database Based on Operation History Graph

分布式数据库系统的副本机制在提高系统可靠性及性能的同时,导致了多副本数据管理的一致性问题;数据一致性的实现需要一致性协议模型来进行预防,也需要一致性检测算法对非一致数据进行检测。首先,对读写操作记录之间的时序关系、安全一致性及并行一致性原则等概念进行定义;其次,根据操作记录集合中读写操作之间的并行与时序关系,提取出操作记录集合向操作记录图转化的规则,并在此基础上设计了操作记录向历史记录图的转化算法;然后,以历史记录图为输入,设计了违反一致性查找算法,查找并返回图中所有违反安全与并行一致性读操作的集合;最后,基于Cassandra进行实验并将读写一致性设置为ONE,通过YCSB产生并行读写压力测试,与同类算法的对比实验验证了所提算法在功能与效率两方面的优越性。

The replica mechanism of distributed database system not only improves reliability and performance of the overall system,but also leads to the consistency problem of multi-replica data management mechanism.To keep the consistency of data,a consistency protocol model is needed to avoid data’s inconsistency events.Moreover,consistency checking algorithms are also needed to detect inconsistent data.Firstly,the concepts of temporal relations,security consistency,and concurrent consistency between read and write operations are defined.Secondly,according to the parallel and temporal relationship between read and write operations that recorded in the set of operations,the rules of transforming operation record set to operation record graph are extracted,and then the algorithm of transforming operation records into operation record graph is also designed.Then,taking the set of operation record graph as input,a violation operation search algorithm is designed to find the set of inconsistent read operations which have violated security and parallel consistency.Finally,experiments are conducted based on Cassandra and the read-write consistency is set to ONE.YCSB generates parallel read-write stress tests.The comparative experiments with similar algorithms verify the advantages of the proposed algorithm in both function and efficiency.