顺序一致性

July 12, 2021 · 1 min · Gray King

Leslie Lamport 1979 年的论文 How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs 定义：

The customary approach to designing and proving the correctness of multiprocess algorithms for such a computer assumes that the following condition is satisfied: 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. A multiprocessor satisfying this condition will be called sequentially consistent.

为这种计算机设计和证明多处理算法正确性的通常方法假定满足下列条件:任何执行的结果都是相同的，就好像所有处理器的操作都是按某种顺序执行的，每个处理器的操作都是按程序指定的顺序出现的。满足这一条件的多处理器系统将被称为顺序一致的。

顺序一致性允许程序员假设程序按照它们在源码中组织相同的顺序执行，并且单个线程的执行只是以某种顺序交替（interleaving），而不是以其他方式排列。

看一下下面这个 litmus test：

Litmus Test: Message Passing
Can this program see r1 = 1, r2 = 0?
// Thread 1           // Thread 2
x = 1                 r1 = y
y = 1                 r2 = x

如果 litmus test 的执行顺序一致，则有六种可能的交替：

所以这个 litmus test 的答案是 no 。

不幸得时，实践中现在硬件都会偏离顺序一致性来放弃严格的顺序一致性可以让硬件更快的执行程序。

Links to this note

一致性与共识

tags: 分布式共识,一致性一致性保证分布式一致性主要针对延迟和故障等问题来协调副本之间的状态。线性化：最强一致性模型顺序保证：保证时间顺序，特别是因果关系和全局顺序最终一致性：一种非常弱的保证，参见最终一致性效应可线性化分布式语义下对寄存器（单个对象）顺序的读写。应区别与可串行化。可串行化针对不同事务的隔离，用来确保事务执行的结果与串形执行的结果相同可线性化是读写寄存器（单个对象）的最新值的保证。线性化依赖的条件加锁与主节点选举每个启动节点都试图获得锁，其中只有一个可以成功成为主节点。通过加锁来保证主节点选举「线性化」。约束与唯一性保证同一个用户名、电子邮件或系统中文件名需要唯一性的保证，也应该进行「线性化」。跨通道的时间依赖系统中存在其他通信渠道也需要「线性化」。实现线性化系统主从复制（部分支持可线性化）共识算法（可线性化）多主复制（不可线性化）无主复制（可能不可线性化）线性化与Quorum 一致性 Dynamo 风格的复制模型，读写遵从严格的 quorum 是无法支持可线性化的。线性化的代价多主复制和主从复制，网络中断都会导致同步暂停，从而无法保证客户端要求的线性化读写。 CAP 理论可线性化与网络延迟很少有系统真正满足线性化，现代多个 CPU 对同一个内存地址的读写都不能满足（参见硬件内存模型），如果需要强一致则需要内存屏障（栅栏）指令。之所以放弃线性化的原因就是性能，而不是为了容错。由于网络延迟的不确定性，无论是否发生网络故障，线性化对性能的影响都是巨大的。顺序保证顺序与因果关系顺序有助于保持因果关系。因果顺序并非全序：因果关系是小范围集合的偏序，可线性化是一个全序操作。可线性化强于因果一致性捕获因果依赖关系：检测并发写序列号排序非因果序列发生器适用于系统不存在唯一主节点。每个节点都独立产生自己的一组序列号：一个奇数一个偶数，或者切入节点唯一标识符。用足够高的分辨率的墙上时间戳附加到每个操作上。预先分配区间范围，并及时扩容。 Lamport 时间戳可以产生因果关系一致的序列号。Lamport 时间戳是一个值对（计数器，节点 ID）：节点 ID：每个节点都有一个唯一标志符。计数器：每个节点都有一个计数器记录各自处理的请求总数。优点：两个节点可能存在相同的计数器，但是时间戳中的节点 ID 可以确保每个时间戳都是唯一的。保证全序：比较两个 Lamport 时间戳，计数器较大的时间戳越大，计数器相同则节点 ID 大的那个时间戳越大。通过节点排序保证了全局因果关系。Lamport 不同于版本矢量：...

C++ 弱同步原子（acquire/release atomic）

tags: C++11 内存模型,C/C++ C++ 还添加了较弱的原子，可以使用 atomic_store_explicit 和 atomic_load_explicit 以及附加的n内存排序参数来访问这些原子。使用 memory_order_seq_cst 使显式调用等效于C++ 同步原子（atomic）较短的调用。较弱的原子称为 acquire/release 原子，一个 release 如果被后来的 acquire 观察到，那么就创建了一个 happen-before 的关系(从 release 到 acquire)。这个术语意在唤起 mutex:release 就像 unlock mutex ， acquire 就像锁定同一个 mutex 。release 之前执行的写入必须对后续 acquire 之后执行的读取可见，就像解锁 mutex 之前执行的写入必须对后解锁 mutex 之后执行的读取可见一样。 atomic<int> done; // Thread 1 // Thread 2 atomic_store(&done, 1, memory_order_release); while(atomic_load(&done, memory_order_acquire) == 0) { /* loop */ } acquire/release 原子只对单个内存位置的操作进行顺序一致的交替执行，所以属于内存一致性（coherence）而非顺序一致性。来看下面 litmus test： Litmus Test: Store Buffering Can this program see r1 = 0, r2 = 0?...

C++11 内存模型

tags: C/C++,Memory Model,编程语言内存模型受新的 Java 内存模型（2004）许多同样的人开始为 C++ 定义一个类似的内存模型，最终在 C++11 中采用。两个重要方便的差异： C++ 对具有数据竞争的程序不做任何保证 C++ 提供了三种原子性：强同步（顺序一致性），弱同步（内存一致性（coherence））和无同步（“relaxed”，用于隐藏竞争）。第一点尝试消除对 Java 模型的复杂性需求，“relaxed” 的原子性重新引入 Java 关于定义什么是竞争程序的所有复杂性。结果是C++模型比Java更复杂，但对程序员的帮助更小。

内存顺序一致性（sequential consistency）

内存屏障

内存屏障（或栅栏）是非顺序一致性的硬件提供的一种显式指令，用于控制排序提供更强的内存排序，修复同步算法。添加内存屏障，确保每个线程在开始读取之前都会刷新其先前对内存的写入： // Thread 1 // Thread 2 x = 1 y = 1 barrier barrier r1 = y r2 = x x86 总存储有序（x86-TSO) 加上内存屏障之后 r1=0, r2=0 就会变得不可能。

x86 总存储有序（x86-TSO)

x86 总存储有序(x86 Total Store Order, x86-TSO)：所有处理器仍然连接到一个共享内存，但是每个处理器都将对该内存的写入(write)放入到本地写入队列中。处理器继续执行新指令，同时写操作(write)会更新到这个共享内存。一个处理器上的内存读取在查询主内存之前会查询本地写队列，但它看不到其他处理器上的写队列。其效果就是当前处理器比其他处理器会先看到自己的写操作。重要的是：所有处理器都保证写入（存储 store）到共享内存的（总）顺序，所以给这个模型起了个名字：总存储有序（Total Store Order，TSO）。写队列是一个标准的先进先出队列：内存写操作总是以与处理器执行相同顺序的应用于共享内存。基于以上下面 litmus test 的答案依然是 no ，这种情况与顺序一致性模型结果一致： Litmus Test: Message Passing Can this program see r1 = 1, r2 = 0? // Thread 1 // Thread 2 x = 1 r1 = y y = 1 r2 = x On sequentially consistent hardware: no. On x86 (or other TSO): no. 但其他测试则并不一致区分与顺序一致性的常用例子: Litmus Test: Write Queue (also called Store Buffer) Can this program see r1 = 0, r2 = 0?...

内存一致性模型

tags: 一致性，Memory Model 当执行给定程序时，硬件和编译器之间的契约，对编译后后的代码对存储在内存中的数据更改的可见性和一致性。这种契约称为「内存一致性模型（Memeory Consistency Model）」或仅仅是「内存模型（Memory Model）」。最初目标是定义程序员编写汇编代码时硬件提供的保证，后来用来定义高级编程语言（如 C++ 或 Java）对该语言编写代码的程序员提供的保证。例如下面变量都初始为 0 的情况下，线程 1 和 2 都运行在自己专用的处理器上，都运行到完成，这个程序能打印 0 吗？ // Thread 1 // Thread 2 x = 1; while(done == 0) { /* loop */ } done = 1; print(x); Memory coherence vs consistency 内存一致性（coherence）内存顺序一致性（sequential consistency）硬件顺序一致性 x86 总存储有序（x86-TSO) ARM/POWER Relaxed Memory Model 弱有序和无数据竞争（DRF）编程语言内存模型