一致性

tags: quorum,一致性，Distributed Systems,Patterns of Distributed Systems,Paxos,Patterns of Distributed Systems: Paxos source: martinfowler.com. “Quorum.” Accessed January 7, 2022. https://martinfowler.com/articles/patterns-of-distributed-systems/quorum.html.

tags: 分布式,一致性 source: https://lamport.azurewebsites.net/pubs/time-clocks.pdf The Big Problem The event order in a distributed system. The defination of a distributed system: the order of its events occurred is unpredictable, sometimes it’s impossiable to say a event occurred before another. How this paper try to solve this problem: use a “happened before” relation to define a partial ordering and distributed algorithm. Background

tags: 分布式,一致性,Clock Synchronization,Multicast source: https://signalsandthreads.com/clock-synchronization/ Electronic Oscillator: Computer itself to Dervie its Notion of Time Computer’s clock are based on a 1 MHz electronic oscillator circuit, that is oscillating at some frequency, and driving an interrupt. So the operating system can use it to derive its notion of time. It helps computer to keep the time correct. But a bad oscillator could be influenced by the heat of CPU, like compiling Linux kernel, etc. A really high-quality oscillator would be really expensive. So most computers come with fairly bad oscillators. ...

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

tags: Memory Model，一致性 FROM 硬件内存模型： threads in the system must agree about a total order for the writes to a single memory location. That is, threads must agree which writes overwrite other writes. This property is called called coherence. 内存一致性的系统都所有线程都必须接受对一个内存地址所有写入的总顺序。换句话说，所有线程必须同意哪些写入可以覆盖另外的一些写入。

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） 编程语言内存模型

tags: 一致性 确定读写成功 确定读写节点在多少节点成功才可以认为写入成功：需要保证读取时至少一个包含新值。 n 个副本的情况下，写入需要 \(w\) 个节点确认，读取必须至少查询 \(r\) 个节点，则只要 \(w + r > n\) ，读取的节点中一定会包含最新值。 \(w\) 仲裁写（法定票数写） \(r\) 仲裁读（法定票说读） 一般 \(n\) 设置为奇数： \(w=r=(n+1)/2\) （向上取整）。 可容忍的失效节点数 仲裁条件 \(w+r>n\) 定义了系统可容忍的失效节点数。 \(w<n\) ，如果一个节点不可用，仍然可以处理写入。 \(r<n\) ，如果一个节点不可用，仍然可以处理读取。 \(n=3\),\(w=2\),\(r=2\)，则可以容忍一个节点不可用 \(n=5\),\(w=3\),\(r=3\), 则可以容忍两个节点不可用 局限性 如果采用了 sloppy quorum，写操作的 w 节点和读取的 r 节点可能完全不同，因此无法保证写请求一定存在重叠的节点。 并发无法明确顺序，需要进行合并并发写入。如最后写入者获胜。 同时读写，写操作在一部分节点上完成，则读取新值还是旧值存在不确定性。 部分节点写入成功，但是最终写入失败无法回滚。 新值的节点失效，但恢复数据来自某个旧值，则总的新值节点数低于 w 边界情况