Thursday, May 20, 2021

System design: Distributed database consistency model | Causal consistency | Happen before | 用happens before关系的有向无环图定义了Causal consistency

 

深入浅析一致性模型之Causal Consistency

2019.05.25 19:16 3302浏览

本文是《如何学习分布式系统》中,关于一致性模型的相关介绍。

Causal consistency的定义

Causal consistency叫做因果一致性,被认为是比Sequential Consistency更弱的一致性,因为在Causal consistency中,只对有因果关系的事件有顺序要求。

Causal consistency的概念最早在《Causal memory: Definitions, implementation, and programming》一文中被提出。随后在《Consistency, Availability, and Convergence》一文中,作者用happens before关系的有向无环图定义了Causal consistency,并且提出了real time causal consistency一致性模型。这篇文章得出了以下两个重要的结论,有兴趣的同学可以读一下原文:

  1. No consistency stronger than real time causal (RTC) consistency, a strengthening of causal consistency, can be provided in an always-available, one-way convergent system.
  2. RTC can be provided in an always-available, one-way convergent system.

Causal consistency要求如果两个事件有因果关系,那么在所有节点上必须观测到这个因果关系。

Causal consistency的例子

比如下图中,我们认为P2写入的3是基于它读出来的1计算出来的,它读出来的1又是由P1的写入产生的,因此认为P1写入1和P2写入3具有因果关系。P4没有观测到这个因果关系,所以这个系统不具备Causal Consistency。

Causal Consistency例子1

而下图中,认为P2写入3和P1写入1不具有因果关系,则P4和P3可以以任意顺序观测到它们。这个系统仍然可以说具有Causal consistency,但是不具备Sequential Consistency。
Causal Consistency例子2

Causal consistency的应用

Causal consistency一般应用在跨地域同步数据中心系统中,例如Facebook、微信这样的应用程序,全球各地的用户,往往会访问其距离最近的数据中心,数据中心之间再进行双向的数据同步。为了减小数据同步的延迟,往往并行的同步数据。
图片描述
没有因果一致性时会发生如下情形:

  1. 夏侯铁柱在朋友圈发表状态“我戒指丢了”
  2. 夏侯铁柱在同一条状态下评论“我找到啦”
  3. 诸葛建国在同一条状态下评论“太棒了”
  4. 远在美国的键盘侠看到“我戒指丢了”“太棒了”,开始喷诸葛建国
  5. 远在美国的键盘侠看到“我戒指丢了”“我找到啦”“太棒了”,意识到喷错人了

或者:

  1. 夏侯铁柱从好友中删除了诸葛建国
  2. 夏侯铁柱发表了朋友圈“清理了一波没用的好友”
  3. 远在美国的诸葛建国看到了该朋友圈
  4. 诸葛建国想去点个赞。。。

所以很多系统采用因果一致性系统来避免这种问题,我们将会在后续的文章中介绍。

例如微信的朋友圈就采用了因果一致性,但是它的资料有点过于简略,有兴趣的可以参考https://www.useit.com.cn/thread-10587-1-1.html

No comments:

Post a Comment