分布式系统要保证系统的可用性,就需要对数据提供一定的冗余度:一份数据,要存储在多个服务器上,才能认为保存成功,至于这里要保存的冗余数,有 Majority 和 Quorum 之说,可以参考之前的文章:周刊(第 17 期):Read-Write Quorum System及在Raft中的实践[1]。同一份数据保存在多个机器上提供冗余度,也被称为副本(replica)策略,这个做法带来下面的好处:
In computer science, a consistency model specifies a contract between the programmer and a system, wherein the system guarantees that if the programmer follows the rules for operations on memory, memory will be consistent and the results of reading, writing, or updating memory will be predictable.
在上图中,在读进程 的视角看来,两个写进程的事件,需要压平到本进程的时间线上进行排列,可以看到这些事件在压平之后有多种排列的可能性。将多个写进程的事件进行排列,放到单进程的时间线上,这是一个排列组合问题,如果所有的写进程事件加起来一共有 n 个,那么这些事件的所有排列组合就是 。比如事件a、b、c,不同的排列一共有这些:{(a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b,a)}一致性模型就是要回答:在所有的这些可能存在的事件排列组合中,按照要求的一致性严格程度,哪些是可以接受的,哪些不可能出现?后面的讲述将看到:越是宽松的一致性模型,能容纳的事件排列可能性就越多;反之越严格则越少。一致性模型
顺序一致性的定义最初出现在论文《How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Progranm》中,原文中要求顺序一致性模型满足两个要求:
the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program.(任何执行的结果都与所有处理器的操作按某种顺序执行的情况相同,每个单独的处理器的操作按其程序指定的顺序出现在这个序列中。)
它有两个条件:
Requirement Rl: Each processor issues memory requests in the order specified by its program.Requirement R2: Memory requests from all processors issued to an individual memory module are serviced from a single FIFO queue. Issuing a memory request consists of entering the request on this queue.
如果保持了前面两个顺序,那么 执行的时候,必然读不出来 A,而应该是 B 或者 C(即 或者 的执行结果)。
顺序一致性和线性一致性总结
可以看到,如果满足线性一致性,就一定满足顺序一致性,因为后者的条件是前者的真子集。除了满足这些条件以外,这两个一致性还有一个要求:系统中所有进程的顺序是一致的,即如果系统中的进程 A 按照要求使用了某一种排序,即便有其他排序的可能性存在,系统中的其他进程也必须使用这种排序,系统中只能用一种满足要求的排序。这个要求,使得满足顺序和线性一致性的系统,对外看起来“表现得像只有一个副本”一样。但因果一致性则与此不同:只要满足因果一致性的条件,即便不同进程的事件排列不一致也没有关系。
[1]周刊(第17期):Read-Write Quorum System 及在 Raft 中的实践: https://www.codedump.info/post/20220528-weekly-17/[2]happen-before: https://www.codedump.info/post/20220703-weekly-21/#happen-before%E5%85%B3%E7%B3%BB[3]How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Progranm: https://www.microsoft.com/en-us/research/uploads/prod/2016/12/How-to-Make-a-Multiprocessor-Computer-That-Correctly-Executes-Multiprocess-Programs.pdf[4]Linearizability: A Correctness Condition for Concurrent Objects: https://cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf[5]分布式系统一致性的发展历史 (一): https://danielw.cn/history-of-distributed-systems-1[6]条分缕析分布式:浅析强弱一致性 - 铁蕾的个人博客: http://zhangtielei.com/posts/blog-distributed-strong-weak-consistency.html关于 Databend关于 DatabendDatabend 是一款开源、弹性、低成本,基于对象存储也可以做实时分析的新式数仓。期待您的关注,一起探索云原生数仓解决方案,打造新一代开源 Data Cloud。