DDIA Note

• pros

  1. 用户读到的数据永远是最新的
  2. 主节点挂了之后，从节点还是有最新的数据的

• cons

  1. 慢
  2. 只要一个从节点有问题，拖累整个系统

• pros

  1. 无阻塞，主节点可以继续处理写请求
  2. 在多数据中心中更适用

• cons

  1. 如果主节点挂了，可能所有数据都丢了

1. 拍一个主节点的快照
2. 把快照复制到从节点
3. 从节点连接到主节点，并请求从快照开始的新的数据
4. 处理完所有的数据变更，可认为从节点赶上了(catch up)，接着就可以正常工作

• 从节点失效：追赶式恢复 从节点重新上线后，从主节点请求从掉线开始的日志，并进行恢复

• 主节点失效：故障转移

  1. 确认主节点确实失效了 节点失效的原因有很多，比如crash，停电，断网等，需要用超时之类的机制确认主节点确实失效了
  2. 选举新的主节点 原主节点确定失效后，需要选举出一个新的主节点，这里就需要解决让所有从节点达成共识的问题(consensus problem)
  3. 重新配置系统让新的主节点生效 客户端需要把写请求发送到新的主节点。初次之外，原主节点可能随时恢复，在它恢复的时候，它自己可能认为它还是主节点，这时候系统需要强制让它下台，可能的话，变成从节点

• 主节点失效恢复过程中产生的问题

  1. 如果是异步复制，新的主节点可能还没有完全更新到旧的主节点的数据。这时候旧的主节点重新加入集群，如何处理这些已经写入进去的数据？常用解决办法是忽略掉旧主节点上未复制出去的数据，但这违背了对客户端持久化的承诺
  2. 忽略已写入的数据是极其危险的，特别是别的系统对数据库的数据有依赖。比如github之前的一个事故，原主节点已经把计数器主键分配给了某些用户，当它出问题的时候，一个未完全同步到数据的从节点被选举成新的主节点，它将这些主键分配给了其他的用户。而原有的主键已经在redis里面被引用，这样导致原有主键用户的私有数据泄露给新持有该主键的用户
  3. 有些情况下，可能同时存在两个节点都认为自己是主节点(俗称脑裂,split brain)，这时候两边都可能在写入数据，导致数据出现问题
  4. 确认主节点失效的超时到底设置多少比较合适？太短会导致开销过大，太长导致总体恢复时间过长

1. 基于语句的复制

   按照sql的语法来，但是会有一些场景不适用

   • 通过now()或者rand()等获取非确定性变量的函数结果是不一致的
   • 有些用了自增或者条件语句，需要串行执行，在并发环境下会有很大限制
   • 只要不是绝对确定性的语句，有些有副作用的语句(如触发器、存储过程或者用户自定义函数)在不同的副本上会产生不同的副作用
2. 基于预写日志(Write-ahead log, WAL)传输 对于LSM存储引擎，日志是主要存储方式，会在后台压缩并进行垃圾回收；如果是用覆盖写入磁盘的B树，会预先写入日志，以方便在出错的时候恢复 这是一种比较底层的方式，兼容性和可移植性都不是很好
3. 逻辑(基于行)日志复制 对存储引擎的增、删、改进行一层抽象，忽略掉实现细节，易解析，对外部系统的支持也更好
4. 基于触发器的复制 很多时候只想复制数据的一部分，或者按照更灵活的需求来做复制，往往会考虑到在感兴趣的数据上加入触发器，然后交给应用层代码来处理 这种方式开销大，容易出错，但是非常灵活

read-after-write consistency: 读自己的写保证用户重新刷新页面的时候，总是能读取到自己刚刚提交的内容

一般有如下实现方案：

• 从主节点读刚刚写入的内容 如果用户可编辑的内容太多，这种方式会严重影响效率(所有的读都从主节点去了)
• 一段时间内从主节点读刚刚写入的内容 一段时间内从主节点读可以缓解全部从主节点读带来的负载压力
• 按照时间戳读取 客户端可以记住写入时候的时间戳(可以是逻辑时间戳、版本号啥的)，如果副本中的版本比时间戳旧，一方面可以去读其他副本，另一方面可以等待直到副本同步到更新的数据
• 主节点路由 如果节点跨越了几个数据中心，可能需要在读取的时候，路由到包含主节点的数据中心

以上方式可以解决单客户端的问题，但是如果用户是多个设备读写同一账户的数据，就要涉及跨设备(cross-device)一致性问题了

• 记住时间戳会变得困难，一个客户端写，其他客户端是不知道写入的时间戳的
• 如果副本跨数据中心，多个设备可能连接上了不同的数据中心，如果是这样，需要路由到相同的数据中心

单调读：确保每次读取数据，都不会比之前读取到的数据旧

前缀一致读：对于一系列按照某种因果顺序发生的写请求，读取这些内容的时候，一定会按照当时的写入顺序读取

通过事务在数据库层面保证一致性，降低应用层的复杂度

单节点事务已经很成熟，但是分布式事务会麻烦很多，具体参考第7章和第9章

在单数据中心用多主节点复制模式没有意义，一般用于如下场景：

• 多数据中心

  在数据中心应用中，单节点和多节点主要优势如下：

  • 性能 单主节点配置中，每次写入都必须经过互联网才能写入到主节点所在的数据中心；而多主节点只需要写入到当前数据中心的主节点，上层应用不用关心数据中心之间的网络同步细节
  • 容忍数据中心失效 单主节点中如果主节点所在的数据中心挂掉了，需要把其他数据中心的一个节点提升为主节点；而多主节点配置中，其他数据中心可以正常服务，失效数据中心在恢复后可以追赶上来
  • 容忍网络问题 广域网的可靠性远不如数据中心内网，而写入操作往往是同步操作，对数据中心之间的网络更为敏感；多主节点之间的复制往往是异步，容错性更好一些

  但是多主节点会有一个严重的问题：如果同一个数据同时被多个数据中心的主节点写入，会造成冲突，这个冲突必须要得到解决

  除此之外，多主节点复制往往是数据库的一个高级功能，一些数据库的功能(自增键、触发器和完整性约束等)在多主节点环境会产生一些副作用

• 客户端的离线操作 当一些客户端需要在离线的情况下继续工作，例如在不同设备上的日历程序，每个设备上程序的数据库可以看做一个数据中心，数据中心之间的同步延迟可能达到数小时甚至数天
• 协同编辑 例如Google Docs这样的，每个浏览器有一个本地的副本，用户修改数据时候，会从本地副本复制到服务器和其他客户端

当两个主节点同时写入同一个数据的时候，就会发生写入冲突

• Synchronous versus asynchronous conflict detection 单主节点是同步写入的，所以不会有这个问题，而多主节点发现冲突的时候，已经太迟了 原则上可以让多主节点复制的写入编程同步模式，但是这样就失去了多主节点复制的最大优势，还不如考虑使用单主节点
• Confict avoidance 解决冲突最直接的办法是避免冲突，如果把对统一用户的写入都放到同一个主节点，就可以避免多主节点写入冲突 这里就需要给每个用户分配一个合适的主节点，用户的所有写入，都交给其主节点来做 不过这里也会有个问题，如果被分配的主节点失效或者用户的物理位置移动，可能就需要给用户重新分配一个主节点，这种情况下，还是会面临写入冲突的问题

• Converging toward a consistent state

  通过算法或者规则让冲突收敛到一致，一般的方式有：

  • 每次写入带上一个唯一的ID，ID最大的写入成功，其他的丢弃；或者带上时间戳，最后写入的成功(last write wins, LWW)。这种方式存在丢失数据的风险
  • 给每一个副本分配一个唯一的ID，来自ID最大的副本的数据，覆盖掉其他的数据，这种方式也可能丢失数据
  • 把冲突的数据按照规则拼接到一起(比如按照字母顺序，写入"B"和写入"C"冲突，可以考虑合并为"B/C")
  • 记录冲突信息，让应用层处理冲突(例如通知用户)

• Custom conflict resolution logic

  处理冲突最好的方式还是依赖用户层，一般有两个时机

  • 在写入的时候处理 只要数据库写入的时候检测到冲突，就通知应用层处理
  • 在读取的时候处理 在写入时候产生冲突，冲突信息被保存下来，用户下次读取的时候，会通知应用层处理

  这里的冲突处理粒度是数据库独立的一行或者一个文档，不是以事务的粒度。所以当一个事务原子地执行几次不同的写入，每次写入都会分别考虑这里的冲突解决

• 什么是冲突 除了这里提到的冲突，第七章和第十二章会讲更多，比如写倾斜问题

一般分为环装、星状(树形)和完全图

前两者容易出现单点问题，后者容易出现特定写入顺序不一致的问题(不同的主节点先后写入同一个内容，其他节点收到的写入顺序可能不一致)

通常可以用一个叫做版本向量(version vectors)的技术来解决这个问题，后面再讲

总的来说多主节点复制的冲突检测技术并不是一个简单的事情，在使用的时候一定要考虑清楚

一般来说，客户端会并行向多个副本发送读请求，根据版本号，可以知道某些节点因为挂掉之类的问题，存储的内容并不是最新的

一般通过两种方式来让数据过期的节点重新获取到最新的数据

• Read repair 客户端一次性会读取多份副本的数据，当发现某些副本落后的时候，由客户端写回过期的副本
• Anti-entropy process 启动一些后台进程，持续监视各个副本之间的异同，并把某些副本确实的数据，从其他副本拷贝过去 这个过程不保证顺序，并且可能会有很大延迟
• Quorums for reading and writing 指定三个变量：n(副本数量)、w(至少成功写入w个节点才算成功写入)、r(每次读取副本的数量) 正常情况下，读写请求会发送给全部n个副本，只有w/r个节点返回成功之后，才认为本次请求成功

选择一个w和r，只要w+r>n，就可以保证写入和读取一定重叠，这样就能保证读取到的数据中，至少一个是最新的

如果选择的w和r更小，可能会遇到读取不到最新值的情况，但是能降低延迟和提高可用性

但是即便w+r>n，也有可能出现读取不到最新值的情况

1. 使用sloppy quorum的情况
2. 如果两个写入同时发生，无法明确发生顺序，这时候唯一安全的方式是合并写入
3. 如果写入的时候发生了读取，无法保证读取到的是新值还是旧值
4. 如果因为某些原因，整体上少于w个节点写入成功，这时候无法回滚已经成功写入的节点
5. 如果一个已经被写入新值的节点挂掉了，在恢复的时候，得到了旧值
6. 即便一切工作正常，第九章还会有Linearizability and quorums问题

所以quorum并不是一个绝对准确的，而是一个灵活可调整最新值的概率

• Monitoring staleness 对于主从复制结构的数据库，主节点到从节点的写入顺序一般是一致的，每个节点都维护了当前所在复制日志的位置，通过对比主节点和从节点的日志位置偏移，可以确定落后程度 而无主节点结构就没有固定的顺序了，这会让监控更加困难。而对于那些只支持read repair(没有 anti-entropy)的数据库，一个节点落后多少是没有限度的

如果因为网络问题之类的原因，不能满足数据仲裁的最低要求这时候就出现了选择：

• 如果成功的节点小于w/r，返回错误比较好？
• 还是说我们允许写入小于w的请求成功，并把把剩下的部分暂存到n个节点之外的其他节点？

后者就是sloppy quorum

一旦网络恢复，这些暂存节点会把原有的数据写回去，这就叫做hinted handoff。这个过程提高了写可用性

• Multi-datacenter operation 无主节点结构可以直接用于多数据中心的环境 配置的时候，写请求会发送到所有数据中心的副本上，但是只会等待本数据中心的回复，这样就不会受到延迟和跨数据中心网络问题的影响

• LWW 我们在说写入时并发的时候，其实是指写入的顺序是未定义的，这时候就需要强制对其排序(例如按照时间戳) LWW是牺牲了数据的持久性的，有些写入请求虽然返回成功，但是依旧会被覆盖掉 LWW唯一安全的用法是，所有的key只允许写入一次
• The “happens-before” relationship and concurrency 定义并发：如果两个操作之间并不知道对方的存在，就认为是并发 如果一个操作确切知道自己发生在另一个操作之后，当前操作就可以安全地覆盖掉之前的操作，否则需要处理并发冲突
• Capturing the happens-before relationship 每个客户端有一个写入链 在写入之前，会从服务端获取最新的数据和版本号，在写入的时候，保证上次获得的版本号之前的冲突数据都是处理了的 写入成功之后，服务端会把最新的版本号，和上次读取到这次写入成功中间的冲突数据一并发回客户端，客户端需要处理掉这些冲突
• Merging concurrently written values 根据需求来，增加的话，可以直接在list后面append；删除的话，需要设置墓碑标志，其他的客户端根据设置墓碑的版本号，选择删除还是保留
• Version vectors 以上讨论的是单副本中的数据，在无主节点结构中，各个副本也可以设置版本矢量，当读取数据的时候，数据库副本会返回版本矢量给客户端

• 原理

  读-提交是最基础的事务隔离级别，只保证两件事情：

  1. 从数据库中读取到的数据，一定是已经提交过的（没有脏读）
  2. 向数据库中写入数据，只会覆盖掉已经提交过的（没有脏写）

  但是无法解决计数器增量竞争的问题

• 实现 通过加锁来防止脏写，通过维护新旧两个版本来防止脏读

• 存在的问题

  1. 无法解决读倾斜(read skew)问题

使用来版本控制，相对读-提交来说的区别在于：读-提交的快照是以查询位粒度的，而快照级别隔离是以事务为粒度的

每条记录快照会带上版本号(事务id)，在读取数据库的时候，几种情况会被忽略：

1. 任何晚于当前事务id的版本
2. 任何已经终止的事务对应的版本
3. 未完成的事务对应的版本

• 索引问题 PostgreSQL等引擎把一个对象的多个版本放到同一个内存页来避免更新索引，而CouchDB等数据库用B树作为主体结构，每一次写入快照，都会创建一个新的root节点

读-提交和快照级隔离都主要是为了解决只读事务在遇到并发写的时候，可以看到什么的问题。之前讨论的脏写，只是写事务冲突的一种特殊情况

更新丢失通常发生的场景是read-modify-write过程，解决这个问题通常有几种方式

• 原子写操作 如果数据库支持原子写(通常是对对象加独占锁或者原子操作强制单线程来实现)，可以把这个过程交给数据库解决。 但是很多时候，我们会在应用层写出read-modify-write的代码，导致无法使用到数据库的原子操作
• 显式加锁 应用层主动加锁，但是很容易漏掉
• 自动检测更新丢失 通过快照级别隔离，很多数据库支持自动检测事务更新丢失

• 原子比较和设置

  在写入的时候带入旧内容，只有旧内容匹配的时候，才进行写入：

  1 2	update wiki_pages set content = 'new content' where id = 1234 and content = 'old content'

  需要注意的是，如果数据库允许where语句从一个旧的快照上读取内容，还是会导致条件为true

• 冲突解决与复制 在多副本数据库中，前面说的原子比较操作和加锁都会失效。一般是保留多个冲突版本，并在应用层去处理冲突。 如果操作可交换(在不同副本上以不同的顺序应用这个操作，能够得到相同的结果)，例如计数器递增、向集合中加入元素，是可以合并更新的 而更为常见的LWW(last write wins)方式却是很容易丢失更新的

写数据的时候，依赖于之前读取的结果，在读和写之间的过程中，读取的结果变了，写入的时候没有发现，会违背规则。这时候如果写入的是同一个对象，则发生 脏写/更新丢失 ；如果是不同对象，则是 写倾斜

幻读：一个事务的写入，改变了另外一个事务查询的结果

• 通过实体化冲突来解决问题 例如订书的例子，可以新建一个表，每一行表示一个预定，包含了时间段和房间号。在事务预定的时候，加锁对应的行，即可避免冲突 但是问题在于，如何实体化冲突，是一个比较困难并且容易出错的问题，而且把并发控制机制泄漏到数据模型中也不够优雅。所以在有备选方案的情况下，不要用这个方案

考虑到内存越来越便宜，OLTP事务通常很短而且读写很少，所以可以考虑：完全移除掉并发，同一时间，只能以串行的方式，执行一个事务

• Encapsulating transactions in stored procedures

  一次性把事务代码直接提交给数据库的操作，叫做存储过程(stored procedure)。如果所有数据都在内存中，完全避免网络和磁盘I/O的开销，这种串行事务的效率也会很高

  存在的问题在于：

  1. 语言不通用
  2. 代码难以维护和调试
  3. 这一层的代码常常是共享代码，其性能非常敏感

• 分区 通常把数据库独立到各个分区，每个分区跑一个实例，可以利用到多核的优势 但如果存在跨分区或者二级索引，会增加大量的协调代码，极大影响性能

• 可实现串行化隔离的约束条件

  1. 事务必须简短高效
  2. 绝大部分数据需要内存处理，磁盘I/O尽量少
  3. 写入吞吐量必须很低才能在单核使用，否则需要分区
  4. 跨分区事务尽量少

近三十年来唯一广泛使用的串行化算法

快照隔离允许读的时候写，或者写的时候读，但是两阶段锁不允许这个操作，这是它们最大的区别

• 实现

  1. 读取一个对象，需要获取共享锁
  2. 写入一个对象，需要获取独占锁

  共享锁之间不冲突，独占锁和任意锁都冲突

这样就容易发生死锁，比如两个事务都要对一个对象有一个读取阶段和写入阶段，如果两个事务同时到达写入阶段，就会相互等待对方放弃读锁

数据库一般都可以通过中止其中一个事务来断掉死锁，并交给应用层处理

• 开销

  1. 锁的获取和释放
  2. 中断了并发
  3. 死锁导致的重试

• Predicate locks(谓词锁)

  到目前为止，2PL能够解决除了幻读以外的所有问题，但是幻读问题依旧，所以这里引入谓词锁

  谓词锁对应一个查询条件，只要满足这个条件的对象，都属于谓词锁的保护

  实现：

  1. A事务要获取满足查询条件的对象，必须以共享锁模式获取这个查询条件的谓词锁，如果存在事务拿到了满足谓词的任意对象的独占锁，A事务必须等待独占锁释放
  2. A事务要修改任何对象，首先要检查这个对象的旧值和新值是否满足任意存在的谓词锁，如果有事务持有这个谓词锁，A必须等到其他事务提交或者放弃

  谓词锁可以保护数据库中还不存在但马上会被写入的数据(幻读)

• 谓词锁优化——索引区间锁(Index-range locks) 谓词锁往往性能不够好，所以一般会把谓词扩大到索引。比如查询一个房间在某个时间段是否预定，房间号和时间区间都可能存在索引，这样就可以把谓词限定在：某个房间的全部时间；某个时间段的全部房间。 如果没有合适的索引，甚至可以锁整张表

相对于2PL，SSI是一种乐观的控制方式，SSI使用一些算法来检测写入冲突并决定中止哪些事务，一般是基于过期的条件做决定，分两种情况：

1. 检测是否读取了一个过期的MVCC对象版本 如果一个事务已经写入了，但是未提交，这时候读取这个值，是可以知道发生冲突了的，但是可以不阻止。 一方面是因为后面的事务读取之后，可能并不写入，也就是不会有写倾斜问题；另一方面，如果第一个事务异常中止了，后面的事务可以安全提交

1. 检测写入是否影响到之前的读取 多个事务同时读了一个值的时候，其中一个事务要进行写入，也是可以知道冲突的(例如前面提到的谓词锁)，这里也不阻止写入 一方面是因为前面读了这个值的事务，不一定会写入，也可能异常终止；另一方面，写入的时候也能发现被改了，这时候终止也来得及

一些依赖于可线性化的用例

• 加锁和Leader节点的选举 一旦新的主节点被选出来，后续节点读取到的主节点，一定要是新的主节点
• 约束和唯一性保证 用户名、邮件名等唯一性保证，有点像加锁；又比如银行交易账单、订票系统
• 跨通道时序依赖 比如两个人用不同设备看比赛结果，他们之间相互交流的结果，需要和各自从设备上看到的结果一致 又比如，系统A往数据库写了东西，然后以其他信道(例如消息队列)通知系统B去处理，系统B在处理的时候，需要保证从数据库能读取到A刚刚写入的内容

• 单主节点系统：部分支持 如果都是从主节点读取或者同步写入到各个副本，原生就是可线性化的 也有些情况不是，比如bugs，或者说设计上就是不可线性化的(使用快照隔离)
• 选举算法：支持 例如ZooKeeper或者etcd，都有实现线性化选举算法
• 多主节点：不支持 设计上就不是可线性化的
• 无主节点：可能不支持 只有合理配置，在一定需求范围内的quorum可能支持 像什么基于时间戳的lww算法完全不可以

对于只有读写操作的quorum，可以支持线性化：

1. 在读操作返回之前，同步执行read repair
2. 在写操作发送写入数据之前，必须读取最新的节点quorum状态

但是这种方式无法支持compare-and-set操作，所以最安全的方式，还是假定无主节点不支持线性化

如果两个数据中心之间的网络中断，用户的线性读写都会受到影响

• CAP理论 CAP理论一方面过于抽象，在实际应用的时候会有很多问题；另一方面，CAP中的P实际上是网络问题导致的，并不存在P与CA之间选择这个问题 如果网络没有问题，C和A是可以共存的；如果网络有问题(P)，才需要再C和A之间做权衡 CAP只讨论了一种一致性模型(线性化)和一种类型的错误(网络问题/活跃节点之间无法通信)，并没有讨论网络延迟、节点不可用等其他情况
• 线性化和网络延迟 对于现在多核cpu，每个核心的缓存的让内存访问可能存在不一致的问题，但这里不能用CAP理论来解释：cpu放弃线性化是因为性能，而不是因为容错 理论上，高效的线性化存储是不存在的，但是弱一点的一致性模型会容易一些

线性化是一种最强的顺序保证，相当于所有的操作都是原子的；但是因果关系(causality)可能存在两个操作之间没有任何联系，也就出现竞态

total ordered(全序)排列的任何两个元素，一定可以对比先后；但是partially order(偏序)并没有这样的保证，两个元素可能无法对比

total order和partially order可以分别映射到Linearizability和Causality

• Linearizability 所有操作有先后顺序
• Causality 没有确定关系的操作就是并发

线性化是因果关系的充分条件，比因果关系有着更强的保证，实际上，要实现因果关系，线性化并不是唯一途径，不过这些途径还在研究中

如果系统有一个唯一的节点，可以对每一个操作进行编号(比如时间戳或者逻辑时钟)，可以自然的生成total order，如果是一个单主节点数据中心，复制日志本身就是全序的

但是如果系统中没有一个中心节点，生成这样的序列号会很麻烦，各个节点之间生成的序号都会有碰撞和交叉的风险

• Lamport timestamps

  这种时间戳就是为了解决多个节点序列号生成不一致的问题，结构为:(counter, node ID)

  对比的时候，先比较counter大小，再比较node ID大小

  1. 每个事件对应一个Lamport时间戳，初始值为0
  2. 如果事件在节点内发生，本地进程中的时间戳加1
  3. 如果事件属于发送事件，本地进程中的时间戳加1并在消息中带上该时间戳
  4. 如果事件属于接收事件，本地进程中的时间戳 = Max(本地时间戳，消息中的时间戳) + 1

  节点内部由2和3保证顺序，节点间由4来保证，如果遇到counter相同，由node ID决定顺序

  lamport逻辑时间戳给系统提供了一个total order的方法

  和版本向量相比，版本向量可以确定两个操作是并发还是因果关系；而lamport timestamps是全序的，没有并发这一说

虽然lamport timestamps提供了一种全序的方案，但是并不能解决问题，例如：

一个操作要创建一个全局唯一的用户名，会出现了几个操作同时创建同一个用户名的情况，这里可以考虑直接利用全序时间戳，时序靠前的成功

但是，要确定谁创建成功，需要搜集所有节点当前跟创建有关的操作，这时候就需要去同步遍历每一个节点。如果在这个过程中，有节点出问题，请求就会被阻塞，导致系统挂住

问题的关键在于，在执行一个操作的时候，你无法知道其他节点有没有执行什么其他操作，也不知道这些操作会被插入到全序序列中的什么位置

总而言之，要解决用户名唯一的问题，光全序操作是不够的，还需要知道这个全序何时结束(当前操作之前的序列不在发生变化？)

这时候就需要全序广播了

全序广播通常被描述为一种节点间消息交换的协议，一般要求两点：

• Reliable delivery 消息不会丢失，如果消息成功发送到了一个节点，那么也一定成功发送到所有节点
• Totally ordered delivery 所有节点上的消息顺序一致

全序广播和lamport之类的时间戳的不同点在于：如果收到了一条消息编号为4，另一条消息编号为6，全序广播可以预估中间有一条消息5；而逻辑时间戳无法知道中间有多少条消息。

全序广播可以类比于只能追加存储的日志

• 基于全序广播实现线性化存储 我们要给用户起一个独一无二的用户名的时候，首先全序广播一条消息，说我要起名了，然后读取消息到我广播的这一条，看这些消息中我是不是第一个
• 基于线性化存储实现全序广播 需要一个线性化存储的整数，并且支持increment-and-get操作，每次发送消息的时候，通过这个操作取得编号，作为全序广播的顺序 实现increment-and-get操作可以是一个单点来做，但是单点可能会失效，这样就面临共识问题了

实现全序广播和实现一个increment-and-get操作的本质，都是共识问题，只要解决其中一个问题，另一个就能得到解决

原子提交：一次事务，要么成功，要么失败，不存在一部分节点成功，一部分失败的情况

2PC是一个多节点事务原子提交的算法(和2PL没啥关系)

2PC包含一个协调节点(coordinator)和一组数据库节点(participants)

1. 协调节点向数据库节点发送数据
2. 协调节点向各节点发送prepare请求
3. 各节点回复prepare请求，作出 promises ，保证无论任何情况发生，都可以完成提交
4. 如果有节点有回复no，coordinator向所有节点发送 放弃 消息
5. 如果所有节点回复yes，coordinator向所有节点发送 提交 消息
6. 第5步无法撤销，coordinator会无限重试直到成功

2PC非常依赖于coordinator，如果coordinator挂了，必须等待其重启

当然participants也可以自己决定该怎么做，但这不是2PC算法的部分了

分布式事务在实践中通常会非常耗，特别是异构分布式系统

• Exactly-once message processing 异构分布式事务允许不同系统集成在一起，例如一个消息队列，其中的消息，有且只有在处理这条消息的数据库事务提交的时候，才算被处理了。 要实现这个过程，就是需要把提交数据库和消息确认放到一个事务中，原子提交，只有两个操作都成功了，才算成功，否者两者都回退 这个过程只有在所有系统中使用相同的原子提交协议，才可能实现。反例就是邮件系统，不支持两阶段提交

X/Open XA(eXtended Architecture)就是一个异构的两阶段提交协议实现标准

• Recovering from coordinator failure 有这样的情况，coordinator在挂掉之后，无法恢复原来的状态，此时部分paricipants还处于in-doubt阶段等着 这时候可能需要系统管理员手动来处理，当然很多XA实现也提供了一些紧急措施(heuristic decisions)，允许参与者自行决定是否放弃本次提交，以跳出in-doubt状态

• Limitations of distributed transactions

  总结起来两点

  1. coordinator容易成为单点问题
  2. XA的兼容性与提供的功能之间需要做权衡

共识算法需要满足如下属性：

1. uniform agreement 所有节点统一意见
2. integrity 不允许反悔或者对同一意见多次决定
3. validity 只能做出合法的决定，不能回复与提议无关的东西
4. termination 所有没挂掉的节点最终要达成共识

第四点要求了出故障的节点是不能超过半数的，否则算法是不工作的。大多数共识算法都保证了前三点，所以即便出现了大规模的停机，以至于不能处理任何需求，但是仍然可以保证数据是对的

大多数共识算法都默认没有拜占庭式错误，即有节点在故意搞事情

全序广播可以说是一种连续的共识，对应起来：

1. 所有节点按照相同顺序传递相同的消息
2. 消息不会重复
3. 消息不会被破坏或者凭空捏造
4. 消息不会丢失

• Single-leader replication and consensus 对单主节点复制机制来说，本质上就是一个全序广播系统(所有的请求由主节点同步给从节点) 只要主节点不挂或者挂掉的时候始终由管理员手动指定，那么就是一个原则上的共识的系统 这种系统往往在实际中工作的很好，但是不满足共识的第四条属性，因为需要人为干预 要满足第四条属性，需要在主节点挂掉的时候选举一个出来 选举要求所有节点达成共识，往往可以通过全序广播系统实现 然后全序广播就是这个系统本身，回到了先有鸡还是先有蛋的问题

• Epoch numbering and quorums 共识算法定义了一个叫任期(epoch number)的时序编号，每一个任期内，只有一个主节点 如果同时出现了两个主节点，任期较小的服从任期较大的 每当主节点被认为是挂掉的时候，各个节点之间可以票选新的主节点，这时候会把任期加一，得到大多数节点投票的节点可以认为是新任期的主节点 在主节点做决定的时候，需要发起提议，得到大部分节点支持(确定没有其他主节点)的时候，才被允许做接下来的事情 这里面的关键点是，参与票选主节点和参与提议的两部分节点中，一定要有重合的部分，这样主节点才能确信自己就是主节点 和2PC不一样的地方在于，2PC需要等待所有节点说yes，而票选只需要大部分节点回复就好了
• 共识的一些问题 票选阶段通常要求同步进行，但是为了性能，很多时候是配置成异步的 共识算法往往需要大部分节点工作就可以继续进行，但是如果这两部分节点的网络出现了中断，剩下一部分节点就会阻塞住 网络不稳定会严重影响共识算法的性能

可以归约为共识问题的几个相同问题：

1. Linearizable compare-and-set registers
2. Atomic transaction commit
3. Total order broadcast
4. Locks and leases
5. Membership/coordination service
6. Uniqueness constraint

单主节点复制通常默认就能够很好的处理这几个问题，但是需要在主节点挂了的时候做出如下几种方式的处理：

1. 等待主节点恢复；但是如果主节点不恢复或者恢复时候出问题，系统就会阻塞住
2. 人为处理主节点挂了的情况
3. 使用共识算法

一般来说，多主节点和无主节点模式可能不需要共识