分布式事务

分布式
,

ACID

ACID，是指数据库管理系统（DBMS）在写入或更新资料的过程中，为保证事务（transaction）是正确可靠的，所必须具备的四个特性：原子性（atomicity，或称不可分割性）、一致性（consistency）、隔离性（isolation，又称独立性）、持久性（durability）

  • Atomicity（原子性）：一个事务（transaction）中的所有操作，或者全部完成，或者全部不完成，不会结束在中间某个环节。事务在执行过程中发生错误，会被恢复（Rollback）到事务开始前的状态，就像这个事务从来没有执行过一样。即，事务不可分割、不可约简。
  • Consistency（一致性）：在事务开始之前和事务结束以后，数据库的完整性没有被破坏。这表示写入的资料必须完全符合所有的预设约束、触发器、级联回滚等。
  • Isolation（隔离性）：数据库允许多个并发事务同时对其数据进行读写和修改的能力，隔离性可以防止多个事务并发执行时由于交叉执行而导致数据的不一致。事务隔离分为不同级别，包括读未提交（Read uncommitted）、读提交（read committed）、可重复读（repeatable read）和串行化（Serializable）。
  • Durability（持久性）：事务处理结束后，对数据的修改就是永久的，即便系统故障也不会丢失。

CAP

CAP定理（CAP theorem），又被称作布鲁尔定理（Brewer’s theorem），指出对于一个分布式计算系统来说，不可能同时满足以下三点：

  • 一致性（Consistency）: 等同于所有节点访问同一份最新的数据副本(Every read receives the most recent write or an error)
  • 可用性（Availability）: 每次请求都能获取到非错的响应——但是不保证获取的数据为最新数据）(Every request receives a (non-error) response – without the guarantee that it contains the most recent write)
  • 分区容错性（Partition tolerance）: 以实际效果而言，分区相当于对通信的时限要求。系统如果不能在时限内达成数据一致性，就意味着发生了分区的情况，必须就当前操作在C和A之间做出选择。(The system continues to operate despite an arbitrary number of messages being dropped (or delayed) by the network between nodes)

BASE

基本可用（Basically Available）

基本可用是指分布式系统在出现不可预知的故障的时候，允许损失部分可用性，但不等于系统不可用。

  • 响应时间上的损失：正常情况下的搜索引擎0.5秒即返回给用户结果，而基本可用的搜索引擎可以在2秒作用返回结果。
  • 功能上的损失：在一个电商网站上，正常情况下，用户可以顺利完成每一笔订单。但是到了大促期间，为了保护购物系统的稳定性，部分消费者可能会被引导到一个降级页面。

软状态（Soft State）

允许系统中的数据存在中间状态，并认为该状态不影响系统的整体可用性，即允许系统在多个不同节点的数据副本存在数据延时。

最终一致性（Eventually Consistent）

强调系统中所有的数据副本，在经过一段时间的同步后，最终能够达到一个一致的状态。其本质是需要系统保证最终数据能够达到一致，而不需要实时保证系统数据的强一致性。

  1. 因果一致性（Causal consistency）
    即进程A在更新完数据后通知进程B，那么之后进程B对该项数据的范围都是进程A更新后的最新值。

  2. 读己之所写（Read your writes）
    进程A更新一项数据后，它自己总是能访问到自己更新过的最新值。

  3. 会话一致性（Session consistency）
    将数据一致性框定在会话当中，在一个会话当中实现读己之所写的一致性。即执行更新后，客户端在同一个会话中始终能读到该项数据的最新值

  4. 单调读一致性（Monotonic read consistency）
    如果一个进程从系统中读取出一个数据项的某个值后，那么系统对于该进程后续的任何数据访问都不应该返回更旧的值。

  5. 单调写一致性（Monotoic write consistency）
    一个系统需要保证来自同一个进程的写操作被顺序执行。

2PC（阻塞、数据不一致问题、单点问题）

假设

  • 该分布式系统中，存在一个节点作为协调者(Coordinator)，其他节点作为参与者(Cohorts)。且节点之间可以进行网络通信。
  • 所有节点都采用预写式日志，且日志被写入后即被保持在可靠的存储设备上，即使节点损坏不会导致日志数据的消失。
  • 所有节点不会永久性损坏，即使损坏后仍然可以恢复。

算法

第一阶段(提交请求阶段 Commit request (or voting) phase)

  1. 协调者节点向所有参与者节点询问是否可以执行提交操作(query to commit)，并开始等待各参与者节点的响应。
  2. 参与者节点执行询问发起为止的所有事务操作，并将Undo信息和Redo信息写入日志。(The participants execute the transaction up to the point where they will be asked to commit. They each write an entry to their undo log and an entry to their redo log.)
  3. 各参与者节点响应协调者节点发起的询问。如果参与者节点的事务操作实际执行成功，则它返回一个"同意"消息；如果参与者节点的事务操作实际执行失败，则它返回一个"中止"消息。

第二阶段(提交执行阶段 Commit (or completion) phase)

成功

当协调者节点从所有参与者节点获得的相应消息都为"同意"时：

  1. 协调者节点向所有参与者节点发出"正式提交"的请求。
  2. 参与者节点正式完成操作，并释放在整个事务期间内占用的资源。
  3. 参与者节点向协调者节点发送"完成"消息。
  4. 协调者节点收到所有参与者节点反馈的"完成"消息后，完成事务。
失败

如果任一参与者节点在第一阶段返回的响应消息为"终止"，或者 协调者节点在第一阶段的询问超时之前无法获取所有参与者节点的响应消息时：

  1. 协调者节点向所有参与者节点发出"回滚操作"的请求。
  2. 参与者节点利用之前写入的Undo信息执行回滚，并释放在整个事务期间内占用的资源。
  3. 参与者节点向协调者节点发送"回滚完成"消息。
  4. 协调者节点收到所有参与者节点反馈的"回滚完成"消息后，取消事务。

缺点

  1. 同步阻塞

    同步阻塞会极大地限制分布式系统的性能。在二阶段提交的执行过程中，所有参与该事务操作的逻辑都处于阻塞状态，各个参与者在等待其他参与者响应的过程中，将无法进行其他任何操作。

  2. 单点问题

    一旦协调者出现问题，那么整个二阶段提交流程将无法运转，更为严重的是，如果是在阶段二中出现问题，那么其他参与者将会一直处于锁定事务资源的状态中，无法继续完成事务操作。

  3. 数据不一致

    在阶段二，当协调者向所有参与者发送commit请求之后，发生了局部网络异常或协调者在尚未发完commit请求之前自身发生了崩溃，导致最终只有部分参与者接收到了commit请求，于v是这部分参与者执行事务提交，而没收到commit请求的参与者则无法进行事务提交，于是整个分布式系统出现了数据不一致性现象。

  4. 太过保守

    如果参与者在与协调者通信期间出现故障，协调者只能靠超时机制来判断是否需要中断事务，这个策略比较保守，需要更为完善的容错机制，任意一个节点的失败都会导致整个事务的失败。

3PC（解决2PC的阻塞，但还是可能造成数据不一致）

算法

第一阶段（CanCommit）

  1. 协调者向各参与者发送CanCommit的请求，询问是否可以执行事务提交操作，并开始等待各参与者的响应

  2. 参与者收到CanCommit请求后，正常情况下，如果自身认为可以顺利执行事务，那么会反馈Yes响应，并进入预备状态，否则反馈No。

第二阶段（PreCommit）

执行事务预提交

如果协调者接收到各参与者反馈都是Yes，那么执行事务预提交

  1. 发送预提交请求

    协调者向各参与者发送preCommit请求，并进入prepared阶段

  2. 事务预提交

    参与者接收到preCommit请求后，会执行事务操作，并将Undo和Redo信息记录到事务日记中

  3. 各参与者向协调者反馈事务执行的响应

    如果各参与者都成功执行了事务操作，那么反馈给协调者Ack响应，同时等待最终指令，提交commit或者终止abort

中断事务

如果任何一个参与者向协调者反馈了No响应，或者在等待超时后，协调者无法接收到所有参与者的反馈，那么就会中断事务。

  1. 发送中断请求

    协调者向所有参与者发送abort请求

  2. 中断事务

    无论是收到来自协调者的abort请求，还是等待超时，参与者都中断事务

第三阶段（DoCommit）

执行提交

  1. 发送提交请求

    假设协调者正常工作，接收到了所有参与者的ack响应，那么它将从预提交阶段进入提交状态，并向所有参与者发送doCommit请求

  2. 事务提交

    参与者收到doCommit请求后，正式提交事务，并在完成事务提交后释放占用的资源

  3. 反馈事务提交结果

    参与者完成事务提交后，向协调者发送ACK信息

  4. 完成事务

    协调者接收到所有参与者ack信息，完成事务

中断事务

假设协调者正常工作，并且有任一参与者反馈No，或者在等待超时后无法接收所有参与者的反馈，都会中断事务

  1. 发送中断请求

    协调者向所有参与者节点发送abort请求

  2. 事务回滚

    参与者接收到abort请求后，利用undo日志执行事务回滚，并在完成事务回滚后释放占用的资源

  3. 反馈事务回滚结果

    参与者在完成事务回滚之后，向协调者发送ack信息

  4. 中断事务

    协调者接收到所有参与者反馈的ack信息后，中断事务。

阶段三可能出现的问题：
协调者出现问题、协调者与参与者之间网络出现故障。不论出现哪种情况，最终都会导致参与者无法及时接收到来自协调者的doCommit或是abort请求，针对这种情况，参与者都会在等待超时后，继续进行事务提交（timeout后中断事务）。

优点：降低参与者阻塞范围，并能够在出现单点故障后继续达成一致
缺点：引入preCommit阶段，在这个阶段如果出现网络分区，协调者无法与参与者正常通信，参与者依然会进行事务提交，造成数据不一致。

拜占庭将军问题

拜占庭将军问题（Byzantine Generals Problem），是由莱斯利·兰波特（Leslie Lamport）在其同名论文中提出的分布式对等网络通信容错问题。

一组拜占庭将军分别各率领一支军队共同围困一座城市。为了简化问题，将各支军队的行动策略限定为进攻或撤离两种。因为部分军队进攻部分军队撤离可能会造成灾难性后果，因此各位将军必须通过投票来达成一致策略，即所有军队一起进攻或所有军队一起撤离。因为各位将军分处城市不同方向，他们只能通过信使互相联系。在投票过程中每位将军都将自己投票给进攻还是撤退的信息通过信使分别通知其他所有将军，这样一来每位将军根据自己的投票和其他所有将军送来的信息就可以知道共同的投票结果而决定行动策略。

假设有9位将军投票，其中1名叛徒。8名忠诚的将军中出现了4人投进攻，4人投撤离的情况。这时候叛徒可能故意给4名投进攻的将领送信表示投票进攻，而给4名投撤离的将领送信表示投撤离。这样一来在4名投进攻的将领看来，投票结果是5人投进攻，从而发起进攻；而在4名投撤离的将军看来则是5人投撤离。这样各支军队的一致协同就遭到了破坏。

解决广义拜占庭问题的定义：

  • 一致性：所有将军对结果达成一致。
  • 正确性：少量叛徒不影响忠诚将军采取错误方案。

解决广义拜占庭问题, 必须满足两个条件：

  • 所有忠诚将军必须获取相同的v(1),…v(n)。即，对任意忠诚的将军来说, 他们看到的其余将军的决定必须是一样的, 不允许出现前文那种, 4位将军统计结果是5攻3撤, 另外4位将军是3攻5撤。（节点行为一致）
  • 如果第i个将军是忠诚的，那么他发送的命令和每个忠诚将军收到的v(i)相同。即，所有忠诚将军的决定对于其余所有忠诚将军都是一样的. 比如, v(1)表示1号将军的决定. 那么其余所有忠诚将军的统计表上, v(1)一定是一样的. 如果这点不能保证, 说明间谍已经可以直接颠覆指挥系统了, 系统怎样都是无效的, 哪怕达成了一致。（通信不被篡改）
    条件1亦可以表述为：
    每两个忠诚的将军必须收到相同的值v(i)

Paxos