最后写入者获胜

tags: 分布式 故障与部分失效 单节点一般是要么工作要么失效，但是分布式系统多节点面临部分失效，大大提高了分布式系统的复杂性。 单节点软件特性： 硬件正常工作时，相同的操作通常总会产生相同的结果，即确定性。 如果发生了某种内部错误，我们宁愿使计算机全部崩溃，而不是返回一个错误的结果。 云计算和超算 超算：垂直扩展的极端，设置检查点，一点节点故障则全部失效从上一个检查点重新开始（离线批处理），类似单机上内核崩溃。 云计算：水平扩展的极端 传统企业位于两个极端的中间 分布式可靠必然面临部分失效，需要依赖软件系统来提供容错机制。我们需要在不可靠的组件上构建可靠的系统。 不可靠网络 分布式无共享系统：成本低廉。 互联网以及大多数 IDC 内部网络都是异步网络：不保证发送一定到达（排队），等待响应时可能出现任何错误。 现实中的网络故障非常普遍 故障检测：HA、主从切换、保活机制（ICMP，SYN） 超时与无限期的延迟 网络拥塞与排队 网络负载过高会出现拥塞。 数据在发送的过程中分别会在发送端和接收端进行排队：等待发送和等待处理。 TCP 的拥塞控制机制。 虚拟化 CPU 核切换虚拟机 同步与异步网络 同步网络：固定电话网络，一路电话分配固定的电路、有带宽保证，规定延迟内保证完成数据包发送，不会丢弃数据包，成本高，利用率低 异步网络：数据中心网络，共享带宽，无法保证延迟和数据包发送，成本低廉，利用率高 不可靠时钟 单调时钟与墙上时钟 时间同步与准确性 计算机中的石英钟不够精确 NTP 服务器不稳定（网络、防火墙或服务本身） 虚拟机中时钟是虚拟化的。 终端设备不可控：休眠、故意设置 依赖同步的时钟 时钟陷阱： 一天可能不总是 86400 秒 回拨 多个节点上的时间完全不相同 需要精确同步的时钟： 自己监控所有节点上的时钟偏差 某个节点时钟漂移超出上限则将其宣告失效 时间戳与时间顺序 最后写入者获胜 时钟的置信区间 通过直接安装 GPS 接收器或原子（铯）时钟，它的误差范围通常可以查询制造商手册。 全局快照的同步时钟 Google Spanner 根据部署了 GPS 接收器或者原子时钟的 TrueTime API 返回的时钟置信区间。确保读事务足够晚发生，避免与先前事务的置信区间产生重叠。 进程暂停 垃圾回收 虚拟化暂停虚拟机 磁盘 I/O 内存交换分区 手动暂停进程（SIGSTOP/SIGCONT） 响应时间保证 RTOS 系统 调整垃圾回收的影响 知识，真相与谎言 真相由多数决定：Quorum 一致性 主节点与锁 Fencing 令牌 拜占庭故障 理论系统模型与现实 计时方面...

读事务遇到并发写会出现脏读（读-提交和可重复读可以解决），写事务并发会带来一些冲突，最值得关注的就是更新丢失问题。 应用程序从数据库读取某些值，然后应用逻辑做出修改，然后写回新值。 原子写操作 UPDATE counters SET value=value+1 WHERE key = 'foo'; 原子操作通常采用方式： 对读取对象加独占加锁，这种技术有时被称为「游标稳定性」。 强制所有原子操作都在单线程上执行。 显式枷锁 BEGIN TRANSACTION; SELECT * FROM figures WHERE name = 'robot' AND game_id = 222 FOR UPDATE; -- 指示数据库对返回的所有结果行要加锁。 缺点：侵入应用逻辑、容易引发死锁（竞争冲突）。 自动检测更新丢失 数据库（Oracle 的串形化和 SQL Server 的快照级别隔离）可以自动检测何时发生了更新丢失，然后终止违规的那个事务。 原子比较和设置 UPDATE wiki_pages SET content = 'new_content' WHERE id = 1234 AND conetnt = 'old_content'; 冲突解决与复制 最后写入者获胜

LWW：最后写入者获胜 Happens-before 关系和并发

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 边界情况

多个主节点看到的执行顺序不一致，病了同时按照各自看到的写入顺序执行，那么数据库最终将处于不一致状态。 数据库必须以一种趋同的方式来解决冲突。 可能的解决方式 给每个写入分配唯一的 ID，如基于时间戳的最后写入者获胜。 为每个主节点分配一个唯一 ID，序列号高的优先于序列号低的主节点，可能导致数据丢失 以某种方式合并值，如按照字母顺序拼接在一起 利用预定义号的格式记录，然后依靠应用层逻辑，事后解决冲突（可能会提示用户）