数据复制
复制是多台机器保存相同数据的副本：如何确保多台机器之间的数据是一致？
- 使数据在地理位置上更靠近用户，从而降低访问延迟
- 当部分组件出现故障，系统依然可以继续工作，从而提高可用性
- 扩展至多台机器以同时提供数据访问服务，从而提高读吞吐量
主从节点复制
主节点处理写请求更新本地数据，主动发送更新数据到从节点或从节点主动向主节点拉去数据 保持主从节点数据一致，从节点只处理读请求。
同步复制/异步复制
主从节点复制方式分为：
- 同步复制：主节点将数据同步写入到从节点才算写请求成功；主节点与所有从节点都使用同步复制会降低写请求性能
- 异步复制：主节点本地数据更新成功后直接返回写请求成功，然后再将数据复制到从节点；主节点与所有从节点都使用异步复制会有数据丢失风险（存在某一刻，数据只保存在主节点）
实践中，主节点与一部分从节点使用同步复制，一部分从节点使用异步复制(Kafka：副本数据n，但可以设置x个节点同步写)。
配置新节点
增加新的副本，问题在于当前节点历史数据为空，如何给新的节点补历史数据？
- 主节点做快照
- 新节点从快照加载数据
- 新节点从当前快照的最后 offset 开始，向主节点同步数据
处理节点失效
任何节点都可能故障，在故障发生时如何保证系统正常运转
- 从节点失效：故障后重启，从同步的最后一个 offset 开始继续向主节点同步
- 主节点失效：主节点切换
- 确认主节点失效，一般为心跳超时
- 选举新的主节点：从节点里选取和主节点数据最接近的从节点成为新的主节点
- 选举出新的主节点这个消息分发到所有节点(Client 后续从节点获取到新的主节点，开始往新的主节点发送数据)
复制日志实现
- 基于语句复制：将 SQL 传输到从节点，SQL 在从节点执行会产生不确定性(时间函数、自增列、其他副作用)
- 基于预写日志复制：直接将磁盘二进制数据传输，若组件本身没有考虑版本兼容性，只能停机升级
- 基于行的逻辑日志复制：直接将更新的当前行数据复制，数据本身不存在不确定性和版本问题，最常用
复制滞后问题
主节点和所有的从节点之间复制不可能全部使用同步复制（写入开销太大），那么从节点往往会出现数据滞后的情况，此时读取从节点的得到不是最新的数据。过一段时间后，也许从节点追上与主节点保持一致，这种模式成为最终一致性(读到不是最新数据)。
- 读自己写：当用户自己写入后，立刻去读，如果是最终一致性，读到的不是最近写入的，这种情况怎么办？
- 有可能被自己修改的内容从主节点读取，否则从节点读取；从而保证读到是最新的
- 记录最近更新的时间，当发起读请求在更新时间附近则从主节点读取，否则去从节点读取；这里多了更新时间和读取时间
- 解决方案思路：判断当前读取的数据最近是否被更改，从而选择是否从主节点读取
- 单调读一致性：比强一致性弱，比最终一致性强
- 案例：从节点 A 数据比从节点 B 新，用户先从A节点读取，然后从B节点读取数据，会发现数据少了
- 解决方案：根据用户 Session Hash ，所有请求都只会到一个从节点，从而保证每次数据读取比之前新
- 前缀一致读：具有因果顺序关系的写入都交给一个分区完成(分区内保证有序)
最终一致性肯定会导致某几个节点数据延迟，当数据延迟对用户体验没有影响是皆大欢喜；当产生影响时，如何消除？其实在应用层也可以做一些保证(读自己写/单调读)，但这会使应用开发变得复杂(开发时需要考虑数据会延迟)。
多主节点复制
配置多个主节点，每个主节点都可以写入，但同时每个主节点也是其他主节点的从节点(技术不是很成熟，除非冲突时用户干预)。
多数据中心
多数据中心可以实现数据中心的高可用，可以根据位置选择不同的数据中心提升用户响应。每个数据中心都有主节点处理读写请求，节点复制采用异步复制。多数据中心有很多好处：性能提升(数据更接近用户)、容忍数据中心失败、容忍网络问题，但有一个潜在的问题：处理写入冲突(当多个数据中心都对同条数据操作)。
离线客户端操作
断网下，离线客户端也要操作，那如何实现呢？离线时的读写操作，都会写本地数据库，下次上线时将数据同步到远端数据库(CouchDB)。这个例子可以看作是多数据中心的极端情况：每个客户端都是数据中心，但简化一点的是客户端之间不需要复制数据。
协作编辑
多个用户同时编辑文档，需要将本地修改复制到服务端和其他用户本地文档(每个用户都是数据中心)。但这里也会有冲突的问题，最简单的处理方式是加锁：只要有用户操作其他用户都不能操作。但这锁粒度太粗会干扰用户操作，需要锁细粒化。
处理写冲突
两个主节点修改同一条记录就会导致写冲突
冲突检查：异步检查文档是否冲突，但此时数据已写入本地，要求解决冲突已晚；同步检查是在写入本地文档时立即同步到所有副本，这就失去多主节点优势变成了主从复制。
避免冲突：与复制滞后的解决方案类似，将同个用户请求都到同个数据中心，这就不会产生冲突。从用户角度，这就变成了主从复制。但有一种情况：当某个数据中心故障时，原先的请求会路由到其他节点，此时还是会有写冲突产生的可能性。
收敛于一致状态：当冲突发生了(主节点1最终结果是A，主节点2最终结果是B)，那么希望在最后所有节点看到的结果是相同的。有几个方案可以实现
- 每个写入分配 UUID(可能有时间戳)，选取最大的 UUID 为最终结果；有可能丢数据
- 为每个副本分配唯一ID，高副本写入优先低副本，丢数据概率很大
- 记录冲突信息，留待用户自己处理(git 冲突)
自定义冲突解决逻辑
冲突最合适有用户解决，
- 写入时，发生冲突回调用户预设的代码(git 在写入时已提示冲突)
- 读取时，所有冲突值保留下来，读取时返回多版本数据留给用户自己处理(CouchDB 处理方式)
拓扑结构
全链路拓扑结构有可能发生数据覆盖的情况：节点1写入A，然后节点2写入B，节点3先同步到了节点2的信息后才同步到节点1的信息，导致节点3上结果是A，显然数据这个结果是错误的。
无主节点复制
客户端(类似主节点功能)直接将请求发往所有副本或者由协调者代表客户端写入(协调者不维护写入顺序)。
节点失效
客户端写三副本，只要两个副本写入成功即认为是成功；当前有一个节点失效后，因为还有两个节点，可以继续写入；但读取时由于某个副本之前未写入数据，此时数据会有差异，如何解决？
确保所有副本的数据最终一致性。
- 读修复：每个数据都有版本号，读取所有副本发现有副本的版本号比其他副本低，则将新版本的数据写回老版本副本
- 反熵过程：系统有后台线程扫描所有副本寻找差异，然后复制，但不保证顺序且滞后明显
Quorum
假设有 n 个副本，写入需要 w 个节点确认，读取至少查询 r 个节点，只要满足 w+r > n 就能保证读取到最新的值(n w r 参数可配)。
满足 w+r > n 就万事大吉了嘛
- 两个写操作同时发生(多数据中心)，无法明确先后顺序，要处理冲突问题
- 同时读写时，写操作只完成一部分，就可能读取不到最新的数据
- 写入副本数少于 w，表示写入失败，但已写入的副本不会回滚，后续读操作会读到新值
- 写入 w 个节点，但某个节点故障，此时不满足 w+r > n
还有一个现象：假设客户端与 n个副本都失连，但与集群内其他节点可以连接，此时允许写入嘛？若允许写入其他的 w 节点(网络正常后数据回传到原先的 n 个副本)，满足了 w+r > n，但此时也不能保证读取到时最新的值。
检测并发写
多个客户端同时对相同键发起写请求，可能导致每个节点收到的内容不一致，导致相同副本不能最终一致，如何处理？
- 为每个写操作增加标识符(时间戳)，每个副本只保存最大的标识符，其他数据被覆盖(last write wins)；机器时间不同步怎么办？
- version 乐观锁，每个写操作 version++，高版本覆盖低版本，若版本相同则合并(这里懵懂)
数据分区
每一条数据只属于特定分区，使用分区可提供扩展性。每个分区可视为完整的小型数据库，独立执行查询。
数据分区与数据复制
- 键-值数据的分区：分区的目标是将数据和查询负载均匀的分布在所有节点，若分布不均匀会产生热点问题(所有请求都在同个节点上)。用键值分配节点，查询时用键路由到节点再查。
- 基于关键字区间分区：利用关键字排序后分段分区(0-9，0-3一个分区，4-6一个分区，7-9一个分区)，分段策略可以调整(HBase)。这可能导致热点问题，以时间为关键字，写入肯定是热点，查询某个时间段也会是热点，最好是关键字加个业务字段打散。
- 基于关键字哈希值分区：哈希可以解决热点问题，但区间特性被打破(相邻关键字数据被分散到不同区间)。用于多个键值组成ROW key，第一个键值打散数据，后面键值按序排列。
哈希可以减轻热点问题，但无法完全避免。以微博热点举例，同一热点会瞬间出现大量写，此时仅对热点哈希无法解决问题，可以加个策略是对热点加随机数打散。
分区与二级索引
键值确定分区后，请求就可以路由到对应的分区。为了加快速度(缺点在于二级索引无法和分区对应)，通常还会加二级索引，但二级索引不是为了查某条数据而是为了某类数据。
- 基于文档分区的二级索引：每个分区单独维护索引条目，写数据时需额外维护到对应索引条目中，读取时也需要从所有分区的索引中扫描。
- 基于词条分区的二级索引：所有分区只有一份全局的索引，但索引字段是分区的(类似关键字分区)；写入时可能需要到其他分区写入索引(涉及跨分区的分布式事务)，读取不需要所有分区只需索引中分区即可。
分区再平衡
数据和请求从一个节点转移到另一个节点的过程称为动态平衡，以下情况下都会涉及
- 查询压力大，CPU 负载高
- 数据规模大
- 节点故障
平衡应尽量减少影响
- 平衡之后，负载、数据、请求应均匀分布
- 平衡过程中，正常提供服务
- 避免不必要的迁移，加快平衡过程
动态分区策略
- 为何不用取模分区：hash(key)%节点数，当节点数变化时这种分区方式导致很多关键字需要从一个节点迁移到另一个节点；迁移成本太高
- 固定分区数据量：创建表时先创建远大于节点数的分区数，增加节点时只需从所有节点拿分区迁移到新节点即可，删除节点类似；这种方式迁移成本很少，但需要先根据数据总量来确定分区数，不然分区数据总是太大或太小，产生不必要的开销
- 动态分区(
HBase)：刚开始初始化分区数，后续根据当前分区数据量进行进行拆分/合并；自动适配数据总量，但对于写入频繁的DB，这个分区操作会比较频繁(HBase 大合并)，虽然迁移的开销较小。 - 按节点比例分区(
Cassandra)：分区数和节点数正比关系(每个节点固定分区数)，数据量增大每个节点数据扩大，增加新的机器来添加新的分区(数据从其他节点的分区迁移来保持节点数据量)。什么时候删分区(减机器)？频次少开销低
请求路由
当数据重分区后，一个新的请求该分发到哪个分区，即重分区后如何得知分区和节点的对应关系？
这其实是服务发现的问题，有几种策略
- 客户端连接任意节点，节点上有数据则处理否则转发到数据对应的节点；节点需要感知分区变化
- 客户端请求路由层，由路由层转发请求到对应节点；路由层需要感知分区变化
- 客户已知分区与节点关系，直接请求到对应节点
以上策略都需要某个角色(客户端/路由/节点)能感知分区变化，否则数据发到错误节点导致失败。共识算法
HBase/Kafka 都依赖 ZK 做分区发现，分区改变后ZK通知保持最新分区状态
Cassandra 不使用ZK，而是通过在节点之间同步分区状态(请求到任意节点)，减少ZK等外部依赖
事务
事务中的所有读写是一个执行整体，整个事务要么成功(提交)，要么失败(中止或回滚)。 事务大大简化应用层的逻辑，那它是如何实现呢。
深入理解事务
事务提供的安全保证是 ACID
ACID含义
原子性：在出错时中止事务(人为中止/由于故障中止)，并将部分完成的写入全部丢弃。一致性：对数据有特定的预期状态(存款不能是负数)，任何数据更改必须满足这些状态约束；应用层借助原子性和隔离性达到一致性，数据库本身不保证一致性。隔离性：并发执行的多个事务相互隔离，它们不能互相交叉(另一个事务只能看到全部结果而不是中间状态)；确保执行结果与串行化一致。持久性：一旦事务提交成功，即使存在硬件故障或数据库崩溃，事务写入的数据也不会消失。
单对象与多对象事务操作
一个事务可能修改多个对象(不同行)；单对象：原子操作(自增/CAS)
处理错误与中止
如果存在违反原子性、隔离性、持久性的风险，则完全放弃整个事务，而不是部分放弃。
弱隔离级别
当两个事务同时修改/读取相同数据，会引发并发问题。这个时候需要隔离，串行化隔离使事务执行结果与串行(一个一个)执行相同。但串行化隔离严重影响性能，一般数据库都采用弱隔离，但这会造成错误需要我们注意。
读提交 -> 可重复读 ->
读-提交
- 读数据库时，只会看到已成功提交的数据(防止脏读)
- 写数据库时，只会覆盖已成功提交的数据(防止脏写)
在这么一个场景下，读-提交无法解决：整型数据 cnt，多个客户端都会进行操作，读取数据并自增；执行结果只会自增一次而不是多次。
- 实现防脏写：行(数据)锁，写操作加锁导致其他操作写操作都不能进行，就不会发生覆盖
- 实现防脏读：一般采用这种方式，待更新对象在数据库会保持新/旧两个版本，事务未提交前读旧值提交后读新值
快照隔离与可重复读
读取操作发生在事务提交前后，那么两次读取的结果必定不一致，这种称为不可重复读。快照隔离可以解决：事务中都从快照读取，保证同个事务中每次读取一致。
多版本并发控制(MVCC)：数据库保留了对象的多个不同提交版本。
每个事务单独一个快照：保证同个事务下的读取一致性。
实现原理：
- 为每个事务赋予单调递增的ID，事务写入数据时，数据会标记写入事务的ID
- 每行数据除了真正的数据，还有管理数据(用户不可见)：created_by 包含写入数据时的事务ID，deleted_by 请求删除的事务ID(如果需要删除)；一条数据要更新时，会存在两条数据：更改完的新数据/被标记要删除的老数据
当一个事务开始时，新快照包含哪些数据呢(数据库管理)
- 事务开始时，创建该对象的事务已经完成提交
- 对象没有被标记为删除；即使标记了，但删除事务还没有完成提交
防止更新丢失
并发写的时候会发生覆盖(不是在原先的写操作上进行，以上面的cnt 自增为例)，解决方案
- 原子操作：自增为例，cnt=cnt+1，是原子操作，不用先读取cnt然后再加1
- 显式加锁：分布式锁
- 自动检测更新丢失：默认允许并发执行，事务管理器检测更新丢失风险，中止当前事务； MySQL InnoDB 不支持检测更新丢失属于没完全支持快照级别隔离，PG、Oracle、SQL Server 支持。
- 乐观锁
写倾斜与幻读
医院排班至少需要1位医生，当前有两位医生，若想离开，流程：
- 查询当前在值医生数
- 若在值数大于1，允许离开；否则不批准
- 更新自己的状态为不在值
当两个医生同时发起流程时，导致流程都批准而没有人值班。这种情况称为写倾斜，为什么会这样的呢？
因为步骤三的结果会改变步骤二的操作(另一个事务产生了幻读)，在本例中要解决可以对步骤一的结果加行锁(for UPDATE)，这样其他事务读取会锁住直到当前事务结束。
幻读：一个事务中的操作会改变另一个事务查询结果；快照级别隔离只能解决只读查询的幻读，无法解决读写事务。
串行化
之前的问题都源于事务是并行化，若串行化则没有以上问题：即使事务可能会并发执行，但最终结果与串行执行结果一致。那如何做到串行化
- 严格按照串行顺序执行
- 两阶段加锁(几乎唯一可行方案)
- 乐观并发控制技术(可串行化的快照隔离)
实际串行执行
单线程执行事务，那单线程如何提高性能呢。数据大部分存内存
以医生值班为例，涉及三个步骤无法一次执行，采用存储过程可以将三个步骤封装成一个操作，一次执行。
- 存储过程：我的理解是可以写数据脚本，将多个步骤串联起来，从而不必频繁与应用交互(判断值班数)
- 分区：单线程最大性能取决于单机CPU，可以将多个事务分区(多实例)执行，但注意不要事务不要夸分区(数据分区)，严重影响性能
两阶段加锁
广泛使用的串行化方法
多个事务可以同时读取同一对象，但只要出现任何写操作则必须加锁以独占访问(数据库实现)。
实现方式：
- 数据库每个对象都有读写锁，锁可以处于共享模式和独占模式
- 要想读先获取共享模式，要想写先获取独占模式(共享升级成独占)
- 共享模式可以多个事务，独占模式是唯一(提交后释放)，其他事务 lock
- 若事务之间由于锁发生死锁，数据库会强制中止某个事务，中止后由应用来重试
由于加锁，锁有开销且会将并行变为串行执行，严重影响性能。
上面的锁是针对单个对象的，但实际场景在操作中往往是涉及多个操作对象的，这需要谓词锁：作用于满足某些搜索条件的所有查询对象(select * from table where A=a)。
谓词锁可以锁住一批对象，但运行时都要去检索这一批对象显然太耗性能了，有没有简单一点的方法。
索引区间锁：简化谓词锁是将保护对象扩大化，以索引为区间。以索引为区间在检索时大大提高性能，但很容易误伤(本来只要锁住a、b对象，但索引是科室)，导致其他对象也被锁住。
可串行化的快照隔离
完整的可串行性保证，性能却比快照隔离损失小。2008年提出，很有可能成为未来数据库的标配。
两阶段加锁是悲观锁，而可串行化的快照隔离是乐观锁：事务并发执行，在提交时才检查冲突，若是则中止由应用重试；事务所有读取操作都是基于数据库一致性快照，增加算法来检测写入之间的串行化冲突。
如何检测冲突，基于过期条件决定在提交时检测
- 读取之前已有未提交的写入
- 读取之后，又有新的写入
分布式系统的挑战
故障与部分失效
在分布式系统中，可能出现系统的一部分正常工作，但其他部分出现难以预测的故障，我们称之为“部分失效”：这部分失效是不确定性的，多个节点网络有时正常，有时失效。
分布式系统工作，必然面临部分失效，需要依靠软件系统来提供容错：在不可靠的组件之上构建可靠系统。
不可靠的网络
通过网络通讯，发送方和接收方有时无法精确交流
- 发送未达到接收方，中间网络故障
- 发送到达接收方，但接收故障无法响应
- 接收方超出负荷，返回 ack 延迟
- 接收方已处理，但ack 未到达发送方
发送方只能通过ack 来确认接收方已处理信息
- 现实中的网络故障：各种情况，网络故障一定会发生
- 检测故障：故障无法避免，那如何检测故障；超时检测
- 超时与无限期的延迟：超时设置短造成波动(误触发)；设置长无法及时发现故障；参数根据现实情况调整
- 网络拥塞与排队：网络或节点超负荷，导致接收和处理信息超时
- TCP 是可靠传输是要检测超时并重发，这会导致延迟；UDP不会重传丢失数据(不会超时检测)，避免延迟
- 同步与异步网络：应用层要考虑超时，增加了复杂性，能不能由硬件来做呢
- 固定电话：每次通话分配专有网络，保证延迟和故障，是端到端的同步
- TCP：网络传输不像电话，流量是固定的，流量波动情况下，经可能快的传递数据，网络带宽是共享的必然有队列容易延迟；异步
- 延迟与资源利用率：资源专属分配(固定电话)可以保证延迟的确定性，但资源利用率低；资源共享成本低，但延迟时间不固定
不可靠的时钟
时钟至关重要，但每台机器都各自维护本地时间，导致分布式系统内的每台机器时钟会稍稍不统一。
单调时钟与墙上时钟
- 墙上时钟：返回1970.1.1 以来的秒数和毫秒数，不含闰秒；与 NTP同步时间，会导致快进/回拨
- 单调时钟：测量时间段；保证总是累加，绝对值没有含义，但两次的差值就是时间间隔，这个数据还是非常准的(微秒级)，System.nanoTime()
时钟同步与准确性
单调时钟不需要同步，它只是个计数器。墙上时钟需要周期性与 NTP 同步时钟，但由于网络/机器故障同步时钟总不会理想导致每个机器时钟不一致；更严重的是每台机器上的石英钟(产生时钟最小间隔)都有偏差(30秒偏差6毫秒)，就算同步 NTP后，过会时钟又不同步了。
依赖同步的时钟
时钟不同步的现象，系统要做好应对措施(某台机器时钟偏移超上限直接下线踢出集群)。
- 时间戳与时间顺序：之前冲突的解决方案是最后写入获胜，但后写入节点上的时钟比先写入节点上的时钟要快，那么最后保留的却是先写入的数据(显然这是错误的)；这里的最后是依靠时钟的判别的，但若是时钟有误差这个判别就不准确了
- 时钟的置信区间：与NTP 的网络延迟以及本地石英钟的偏差，机器上的墙上时钟是有误差的，精确度只能到几十毫秒(微秒级数字不准确)；Google Spanner的TrueTime API 返回的是区间。
- 全局快照的同步时钟：
- 快照隔离指写入发生在快照之后，那么写入对快照不可见；
- 如何快速判断写入是否在快照之后，快照ID带时钟，写入时间对比ID即可；
- 分布式场景下时钟可能不一致，导致明明是写入在快照之后，但写入时间却比快照ID小
- Google Spanner 始终是区间，会等待写入时间区间和快照ID时间区间没交集(此时产生了先后顺序)再操作
进程暂停
所有依靠时钟的策略(心跳超时检测)都会有一个问题，若当前进程暂停过长会导致策略发生错误(暂停20s，恢复后发现心跳超时了)。
什么场景会导致进程暂停
- Java Full GC
- 虚拟环境下，进程迁移(暂停虚拟机把当前进程复制其他机器上后重启虚拟机)
- 操作系统切换上下文，这种情况一般很快，但若有异常也会很耗时
- 操作系统缺页交换内存空间，实际情况很少遇到很耗时
以上情况都会暂停，但进程却毫无感知，去检测时钟才发现已过去相当长一段时间
- 响应时间保证：上述案例都无法保证固定的响应时间，这需要实时操作系统(RTOS)，每个操作响应时间固定且有优先级；车辆碰撞时肯定不希望来个几秒的Full GC
- 调整垃圾回收的影响：垃圾回收影响很大
- 当有节点GC时，此节点下线，集群负载重新调度
- 短期执行快速GC，定期重启机器清所有垃圾，重启前集群负责重新调度
知识，真相与谎言
真相由多少决定
分布式场景，对于某个节点状态是由其他节点多票(quorum)决定(投票决定)
- 某节点能接收信息，但不能发出信息(ack)；那么其他节点会认为该节点失效，虽然该节点能正常接收并处理信息
- Full GC 导致进程停顿后又继续运行，其他节点会感知：有问题的节点突然重新工作了
主节点与锁
选举主机点或者资源时，都需要分布式锁，只要获得分布式锁才能对资源操作。原先获取分布式锁的节点由于GC停顿，导致集群认定该节点失效，此时重新有节点获取分布式锁，若该节点GC后继续操作资源就会发生错误(新节点获取分布式锁也会操作，可能会冲突)。这种情况下加锁并不能完全解决问题。
Fencing 令牌
上面的案例加分布式锁还有问题，这里再加个递增令牌。每次获取分布式锁都会生成更大的令牌值，然后通告其他节点，那么即使旧节点停顿后想继续操作，也会因为令牌检测(比当前已知的令牌值小)不通过而无法执行。Zookeeper 就是使用这种方式防止脑裂(两个leader 节点)，每次选举出新leader 都自增。
拜占庭故障
虽然本书假设所有节点都是可信的，不存在伪造的情况。但还是有必要描述下存在不可信节点时的问题：节点故意发送伪造信息，伪造令牌操作；在这样不信任的环境中需要达成共识的问题成为拜占庭将军问题。
可信节点不存在谎言，但由于一些问题造成错误，此时需要修复/识别
- 网络包数据损坏，需要校验码检测
- 用户所有输入都要校验
- NTP 同步时间，考虑网络传输误差，多台服务器增加健壮性
理论系统模型与现实
接下来的共识算法要解决本章的各种故障，使用系统模型更清楚的描述算法的前提条件。
- 同步模型：网络延迟、进程暂停、时钟误差有最大值不会无限制，但大多数系统并非如此，无限延迟和停顿会发生
- 部分同步模型：大部分情况下是同步模型，但有时候延迟/误差非常大，比较现实的模型
- 异步模型：不会有时机甚至是时钟，某些算法支持但并不常见
节点失效模型
- 崩溃-中止：故障导致崩溃，然后直接中止不响应
- 崩溃-恢复：崩溃后经过一段时间自动恢复，内存里的状态会丢失
- 拜占庭：节点会伪装和欺骗
真是世界是崩溃-恢复和部分同步模型的组合
算法是有场景的(上面的模型)，只要在场景下都满足要求，那么称该算法正确。正确性可以分解为安全性和活性：安全性表示不会有意外，活性暗示最终结果。
模型是对现实世界的抽象，可以用模型对算法评测；但现实世界往往更负责，有些极端情况打破算法正确性时，需要输出提示信息。
一致性与共识
分布式系统中，当网络数据包可能会丢失、顺序紊乱、重复发送/延迟、时钟也有一定的偏差，节点可能发生暂停或者崩溃，应该怎么办？共识算法能很好解决问题，为分布式应用屏蔽以上问题只让应用关心逻辑。
一致性保证
分布式数据库一般只保证最终一致性，同一时刻读写操作如果路由到不同的节点，那么会读不到刚写进去的数据。接下来会探讨更强的一致性模型。
事务隔离主要是为了处理并发执行事务时的各种临界条件，而分布式一致性则主要针对延迟和故障等问题来协调副本之间的状态。
可线性化
使分布式系统看起来只有一个数据副本，且所有的操作都是原子的。关注点在于读写顺序，读都是最新值。
线性化是强保证，那些场景是必须的呢？
- 加锁与主节点选举：线性化存储服务是所有这些协调服务(zk,etcd)的基础
- 约束与唯一性保证：唯一键可以理解为锁，其实与加锁类似，只不过这把锁加了就不会释放，除非删数据
- 跨通道的时间依赖：若所有消息只能从一个通道传输，那么不会有线性问题；发现线性问题，是因为客户端间有交流，如果只有客户端与数据库交流那么不会有线性问题(不知道当前数据对不对，数据库返回值说了算)。
实现线性化系统
线性化的保证是所有副本在数据写入之后那刻开始，数据都是一致的。这要求副本复制是同步的。
线性化的代价
CAP
网络正常，可以保证一致性和可用性
网络不正常，必须选择一致性或者可用性
网络故障不可避免，那么在网络分区的情况下，是选择一致还是可用？
线性化与网络延迟
CAP 理论没考虑网络延迟的情况
现实情况下，不选择一致性往往不是为了可用性，而是基于性能考虑。读写的响应时间至少要与网络中延迟成正比，而现实网络往往高度不确定的网络延迟，那么线性化读写的性能势必非常差。
顺序保证
此小节回顾之前关于顺序的很多案例，可以去思考。
因果一致性
如果系统服从因果关系所规定的顺序，我们称之为因果一致性。
可线性化是全序；因果顺序并非全序，是部分排序(分区有序性)。
因果一致性可以认为是，不会由于网络延迟而显著影响性能，又能对网络故障提供容错的最强一致性模型。
非线性系统如何保证因果一致性呢？跟踪整个数据库请求的因果关系，知道应用程序读取的是哪个版本的数据。
序列号
跟踪所有的因果关系实际上往往不切实际。但可以依赖序列号来表示因果关系(小的先发生)，系统唯一主节点为每个操作生成递增的序列号。
但往往系统中没有这样的唯一节点(分区/多主节点)，又该如何
Lamport 时间戳：每个节点都包含时间戳(计数器, 节点ID)，计数器表示当前节点处理的请求数；- 每个节点以及每个客户端都跟踪迄今为止所见到的最大计数器值，并在每个请求中附带该最大计数器值。当节点收到某个请求(或者回复)时，如果发现请求内嵌的最大计数器值大于节 点自身的计数器值，则立即把自己的计数器修改为该最大值。
- 保证全序性：给定两个时间戳，计数器大的时间戳大；计数器相同，节点ID越大时间戳越大
- 但无法解决这类并发问题：两个客户端同时对两个节点进行相同的操作，理论上只有一个能成功，但用
Lamport实际上两者都会成功(类似写倾斜问题)；问题在于一个节点并不知道另一个节点在做什么，无法构造出最终的请求序列。
全序关系广播
有些地方还是没太明白
全序关系广播/原子广播：处理主节点失效/扩展系统的吞吐量突破单一主节点的限制；指节点之间交换信息的协议。
- 可靠发送：没有消息丢失，如果消息发送到某一节点，则它一定要发送到所有节点
- 严格有序：消息总是以相同的顺序发送给每个节点
Zookeeper 和 etcd 都实现全序关系广播
- 采用全序关系广播实现线性化存储：节点上的每个操作都广播到其他节点，保证其他节点完成；保证读取线性化：读操作时节点确保在这时间点之前所有操作都已完成(强制刷新 zk.sync)
- 采用线性化存储实现全序关系广播：
线性化的原子比较-设置(或自增) 寄存器与全序关系广播 二者都等价于共识问题。
分布式事务与共识
共识问题是分布式计算中最重要也是最基本的问题之一。目标只是让几个节点就某件事情达成一致。
原子提交
原子提交需要共识算法：数据写入到分布式数据库(多节点)，如何保证多个节点一起成功或一起失败。
事务提交不可撤销，不能 事后再改变主意(在提交之后再追溯去中止)。这些规则背 后的深层原因是， 一旦数据提交，就被其他事务可见，继而其他客户端会基于此做出 相应的决策。这个原则构成了读-提交隔离级别的基础。如 果允许事务在提交后还能中止，会违背之后所有读-提交的 事 务，进而被迫产生级联 式的追溯和撤销。
- 两阶段提交：协调者询问所有参与者是否可以提交，若是则协调者对所有参与者发起提交，否则发送放弃请求
分布式事务
分布式事务的某些实现存在严重的性能问题。
- 数据库内部的分布式事务：分布式数据库跨节点的事务
- 异构分布式事务：事务包含两种及以上的组件，写数据库 + 写Zookeeper(提交消息队列offset)；此类充满挑战
XA是异构环境下实施两阶段提交的一个工业标准。两阶段提交最怕的是协调者故障会导致停顿(故障恢复)。此时数据库不会释放锁，数据库事务通常持有待修改行的行级独占锁，用以防止脏写。那么该行数据无法进行后续修改(已加锁)，若协调者不恢复将永久加锁。许多XA的实现都支持某种紧急避险措施称之为启发式决策:这样参与者节点可以在 紧急情况下单方面做出决定，放弃或者继续那些停顿的事务，而不需要等到协调者发出指令(此时违背两阶段提交)。
支持容错的共识
一个或多个节点可以提议某些值，由共识算陆来决定 最终值 。共识算法必须满足以下性质
- 协商一致性：所有的节点都接受相同的协议
- 诚实性：所有的节点不能反悔，即对一项提议不能有两次决定
- 有效性：如果决定值v，那么值v一定是由某个节点提议的
- 可终止性：节点如果不崩溃则最终一定可以达成协议
主从复制与共识：主节点通过广播将数据复制到从节点，这是全序关系广播；但不容错，主节点崩溃时需要选举出新的主节点；但如果把全序关系广播当成是共识算法，<选举新的节点>这个消息是要由主节点来广播的；这就产生一个悖论：需要选举主节点，但选举这条消息却只能是主节点来发送。
如何解决这个悖论呢？选举出一个主节点：首先是投票决定谁是主节点，然后是对主节点的提议进行投票。
网络延迟是共识算法的天敌。
