Computer Science

Computer Science ›› 2019, Vol. 46 ›› Issue (12): 213-219.doi: 10.11896/jsjkx.181102097

• Software & Database Technology • Previous Articles     Next Articles

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

LIAO Bin1, ZHANG Tao2,3, LI Min1, YU Jiong2, GUO Bing-lei2, LIU Yan4   

  1. (College of Statistics and Data Science,Xinjiang University of Finance and Economics,Urumqi 830012,China)1;
    (School of Information Science and Engineering,Xinjiang University,Urumqi 830046,China)2;
    (Department of Medical Engineering and Technology,Xinjiang Medical University,Urumqi 830011,China)3;
    (School of Software,Tsinghua University,Beijing 100084,China)4
  • Received:2018-11-14 Online:2019-12-15 Published:2019-12-17

PDF (PC)

593

Abstract: 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.

Key words: Consistency check, Consistency principle, DAG diagram, Distributed database, Key-Value database

CLC Number: 

  • TP391
[1]LI J Z,WANG H Z,GAO H.State-of-the-Art of Research on Big Data Usability[J].Journal of Software,2016,27(7):1605-1625.
[2]GILBERT S,LYNCH N.Perspectives on the CAP Theorem [J].Computer,2011,45(2):30-36.
[3]LAMPORT L.Fast Paxos[J].Distributed Computing,2006,19(2):79-103.
[4]BENZ S,SOUSA L P D,PEDONE F.Stretching multi-ring Pa- xos[C]//ACM Symposium on Applied Computing.New York:ACM,2016:492-499.
[5]OKI B M,LISKOV B H.Viewstamped Replication:A New Primary Copy Method to Support Highly-Available Distributed Systems[C]//ACM Symposium on Principles of Distributed Computing.New York:ACM,1988:8-17.
[6]EL-SANOSI I,EZHILCHELVAN P.Improving ZooKeeper Atomic Broadcast Performance by Coin Tossing[C]//European Workshop on Performance Engineering.Springer,2017:249-265.
[7]SONG M,LUO G,HAIHONG E.A Service Discovery System based on Zookeeper with Priority Load Balance Strategy[C]//IEEE International Conference on Network Infrastructure and Digital Content.Piscataway,NJ:IEEE,2017:117-119.
[8]JUNQUEIRA F P,REED B C.The life and times of a zookeeper[C]//ACM Symposium on Principles of Distributed Computing.New York:ACM,2009:1-4.
[9]BECKER M Y,SEWELL P.Cassandra:flexible trust management,applied to electronic health records[C]//ComputerSecu-rity Foundations Workshop.Piscataway:IEEE,2004:139-154.
[10]MALIK P,MALIK P.Cassandra:a decentralized structured storage system[C]//ACM SIGOPS Operating Systems Review.New York:ACM,2010:35-40.
[11]WANG B Q,YU Q,LIU X,et al.Efficient and dynamic data management system for cassandra database[J].ComputerScien-ce,2016,43(7):197-202.
[12]VORA M N.Hadoop-HBase for Large-Scale Data[C]//International Conference on Computer Science and Network Technology.Piscataway,NJ:IEEE,2012:601-605.
[13]FENG S C,CAO B,CHAO D W,et al.Hash Synopsis Forest Index Schema Based on Hbase[J].Journal of Chinese Computer Systems,2018,39(1):100-104.
[14]BOYD S,GHOSH A,PRABHAKAR B,et al.Randomized gossip algorithms[J].IEEE Transactions on Information Theory,2006,52(6):2508-2530.
[15]HAAS Z,HALPERN J Y,LI L.Gossip-based ad hoc routing [J].IEEE/ACM Transactions on Networking,2006,14(3):479-491.
[16]BOHANNON P,FAN W,GEERTS F,et al.Conditional Functional Dependencies for Data Cleaning[C]//IEEE,International Conference on Data Engineering.Piscataway,NJ:IEEE,2007:746-755.
[17]FAN W,GEERTS F,JIA X.Improving data quality:consistency and accuracy[J].Pakistan Journal of Biological Sciences,2007,7(6):315-326.
[18]ZHANG A Z,MEN X Y,WANG H Z,et al.Hadoop-Based Inconsistence Detection and Reparation Algorithm for Big Data.Journal of Frontiers of Computer Science and Technology,2015,9(9):1044-1055.
[19]ANDERSON E,LI X,SHAH M A,et al.What consistency does your key-value store actually provide?[C]//Proc of Workshop on Hot Topics in System Dependability.New York:ACM,2010:1-16.
[20]COLOMBO D,MAATHUIS M H.Learning high-dimensional directed acyclic graphs with latent and selection variables[J].Annals of Statistics,2012,40(2012):294-321.
[21]WANG Y,CAO S,GUO H,et al.Communication aware multiple directed acyclic graph scheduling considering cost and fairness[J].Journal of Computer Applications,2015,37(3):316-321.
[22]BING S,ZHEN Z,BING W,et al.Scene Segmentation with DAG-Recurrent Neural Networks[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2018,40(6):1480-1493.
[1] LING Fei, CHEN Shi-ping. Shared Digital Credits Management Mechanism of Enterprise Alliance Based on Blockchain [J]. Computer Science, 2021, 48(11A): 533-539.
[2] LIANG Ru-bing and LIU Qiong. Method of Semantic Cache Consistency Checking in Mobile Computing Environments Based on Agent Technology [J]. Computer Science, 2014, 41(3): 132-136.
[3] . Validation Environment of Software Architecture Based on OCL [J]. Computer Science, 2012, 39(Z11): 409-414.
[4] . Cloud Data Storage Security and Privacy Protection Policies under IoT Environment [J]. Computer Science, 2012, 39(5): 62-65.
[5] ZHAO Xiao-fei,HUANG Zhi-qiu. Inconsistency Checking and Resolving of CWM Metadata Based on Description Logics [J]. Computer Science, 2010, 37(11): 166-171.
[6] . [J]. Computer Science, 2008, 35(1): 193-195.
[7] Wang ZhiHe;Yang YanJiao;Zhang Jiang. [J]. Computer Science, 2005, 32(8): 73-74.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.