Concise Server-Wide Causality Management for?Eventually Consistent Data Stores

详细信息    查看全文

• 关键词：Distributed Systems ; Key ; Value Stores ; Eventual Consistency ; Causality ; Logical Clocks ; Anti ; Entropy
• 刊名：Lecture Notes in Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：9038
• 期：1
• 页码：66-79
• 全文大小：289 KB
• 参考文献：1.Almeida, P.S., Baquero, C., Gon?alves, R., Pregui?a, N., Fonte, V.: Scalable and accurate causality tracking for eventually consistent stores. In: Magoutis, K., Pietzuch, P. (eds.) DAIS 2014. LNCS, vol.?8460, pp. 67-1. Springer, Heidelberg (2014)View Article
  2.DeCandia, G., Hastorun, D., Jampani, M., Kakulapati, G., Lakshman, A., Pilchin, A., Vosshall, P., Vogels, W.: Dynamo: amazon’s highly available key-value store. In: ACM SIGOPS Operating Systems Review, vol.?41, pp. 205-20 (2007)
  3.Gilbert, S., Lynch, N.: Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services. ACM SIGACT News?33(2), 51-9 (2002)View Article
  4.Golding, R.A.: Weak-consistency group communication and membership. Ph.D. thesis, University of California Santa Cruz (1992)
  5.Johnson, P.R., Thomas, R.H.: The maintenance of duplicate databases. Internet Request for Comments RFC 677, Information Sciences Institute (1976)
  6.Karger, D., Lehman, E., Leighton, T., Panigrahy, R., Levine, M., Lewin, D.: Consistent hashing and random trees. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pp. 654-63. ACM (1997)
  7.Klophaus, R.: Riak core: building distributed applications without shared state. In: ACM SIGPLAN Commercial Users of Functional Programming. ACM (2010)
  8.Ladin, R., Liskov, B., Shrira, L., Ghemawat, S.: Providing high availability using lazy replication. ACM Trans. Comput. Syst.?10(4), 360-91 (1992)View Article
  9.Lakshman, A., Malik, P.: Cassandra: a decentralized structured storage system. ACM SIGOPS Operating Systems Review?44(2), 35-0 (2010)View Article
  10.Lamport, L.: Time, clocks, and the ordering of events in a distributed system. Communications of the ACM?21(7), 558-65 (1978)View Article MATH
  11.Malkhi, D., Terry, D.: Concise version vectors in winFS. In: Fraigniaud, P. (ed.) DISC 2005. LNCS, vol.?3724, pp. 339-53. Springer, Heidelberg (2005)View Article
  12.Merkle, R.C.: A certified digital signature. In: Brassard, G. (ed.) Advances in Cryptology - CRYPTO 1989. LNCS, vol.?435, pp. 218-38. Springer, Heidelberg (1990), http://dl.acm.org/citation.cfm?id=118209.118230
  13.Parker Jr., D.S., Popek, G., Rudisin, G., Stoughton, A., Walker, B., Walton, E., Chow, J., Edwards, D.: Detection of mutual inconsistency in distributed systems. IEEE Transactions on Software Engineering, 240-47 (1983)
  14.Schwarz, R., Mattern, F.: Detecting causal relationships in distributed computations: In search of the holy grail. Distributed Computing?7(3), 149-74 (1994)View Article MATH
  15.Wuu, G., Bernstein, A.: Efficient solutions to the replicated log and dictionary problems. In: Symp. on Principles of Dist. Comp. (PODC), pp. 233-42 (1984)
  
• 作者单位：Ricardo Gon?alves (15)
  Paulo Sérgio Almeida (15)
  Carlos Baquero (15)
  Victor Fonte (15)
  
  15. HASLab, INESC Tec and Universidade do Minho, Portugal, Braga
  
• 丛书名：Distributed Applications and Interoperable Systems
• ISBN：978-3-319-19129-4
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

Large scale distributed data stores rely on optimistic replication to scale and remain highly available in the face of network partitions. Managing data without coordination results in eventually consistent data stores that allow for concurrent data updates. These systems often use anti-entropy mechanisms (like Merkle Trees) to detect and repair divergent data versions across nodes. However, in practice hash-based data structures are too expensive for large amounts of data and create too many false conflicts. Another aspect of eventual consistency is detecting write conflicts. Logical clocks are often used to track data causality, necessary to detect causally concurrent writes on the same key. However, there is a non-negligible metadata overhead per key, which also keeps growing with time, proportional with the node churn rate. Another challenge is deleting keys while respecting causality: while the values can be deleted, per-key metadata cannot be permanently removed without coordination. We introduce a new causality management framework for eventually consistent data stores, that leverages node logical clocks (Bitmapped Version Vectors) and a new key logical clock (Dotted Causal Container) to provides advantages on multiple fronts: 1) a new efficient and lightweight anti-entropy mechanism; 2) greatly reduced per-key causality metadata size; 3) accurate key deletes without permanent metadata.