数据库的外部一致性

2020-05-26
数据库 分布式事务

一言以蔽之,外部一致性就是事务在数据库内的执行序列不能违背外部观察到的顺序。

举个例子,客户端先创建一个事务写入一条数据,然后再创建一个事务读取刚才写入的数据,这时候理应能读到,数据库不能给返回个空,然后解释说我把读事务安排在写事务前面了,所以啥也没读到。

传统上数据库的 ACID 里面是没有这个概念的,即使是最高级别的可串行化也没有外部一致性的约束——它只规定了多个事务的运行结果跟一个一个依次运行的结果相同,但没有关于事务次序的规定。也就是说,理论上,对于所有的只读事务,数据库都可以直接返回空,然后解释说所有的只读事务都排在第一条写事务的前面。当然了,没有数据库真的会这么干。正常的数据库都会按照事务请求到达的次序来执行,这不仅符合正常业务的需求,而且在实现层面也容易做。

当数据库进入分布式时代之后,外部一致性这个问题才真正需要被考虑,外部一致性这个概念本身也是 Google Spanner 论文里最早提出来的。原因是在分布式数据通常会保存同一份数据的多份副本来保证高可用和容灾,当多个副本所在的多个节点同时提供服务时,我们需要应付副本同步所带来的复杂性。

比如事务在一个节点写入一条数据,完成后立即另启一个事务在另一个节点读取,能成功读到刚刚写入的数据吗?如果没读到,可以理解成在数据库层面,后一个事务先于前一个事务运行了,这样就违背了外部所观察到的顺序。

再举一个涉及 3 个事务的例子。第一个事务在一个节点写入数据 A,完成后再启动第二个事务在另一个节点写入数据 B,在这个过程中另有第三个并发运行的事务尝试读 A 和 B,如果它读到了 B 却没读到 A,那意味着第二个事务先于第一个事务运行了,也不满足外部一致性。

要注意的是,外部观察到两个事务有先后次序,一定是前一个事务完成后,后一个事务才开始。否则两个事务是并发的,数据库可以以任意顺序执行这两个事务。例如客户端先启动一个事务,在请求发往数据库之后再启动第二个事务,这时这两个事务就是并发的。即使是单机数据库,也不能保证第一个事务的请求会先于第二个事务到达服务器,这两个事务的执行顺序完全有可能调换。

有朋友可能注意到外部一致性跟分布式系统里的线性一致性很类似。没错其实是本质上是一回事,不过线性一致性一般针对单个 key 的场景,外部一致性更侧重于对比传统数据库系统的内部一致性(即事务的时序在数据库系统内部是自洽的)。

TiDB 的外部一致性

TiDB 的方法是非常简单粗暴的,所有事务的 ts (用于标识事务的顺序)都要从中心节点 PD 获取,PD 在分配时保证 ts 严格单调递增。

因为所有事务都要通过同一个 PD 取 ts,假如在外部观察到两个事务有先后次序(如前所说,前一个事务提交完成后,第二个才启动),那么后面事务的 ts 一定会更大。于是,我们用 ts 的大小来规定事务的顺序,一定不会违背系统外部观察到的现象。

实际情况还要更复杂一点,因为事务往往涉及到多个节点,还需要使用 2PC 才能真正保证一致性,这里不展开了。

Spanner 的外部一致性

Spanner 最广为人知的就是它使用了原子钟进行授时。但实际上原子钟只是手段,真正有开创意义的是 TrueTime。利用各种硬件设备(大多数情况下主要起作用的其实是 GPS)和算法,TrueTime API 可以对外返回当前估算时间及误差范围,事务逻辑在考虑到误差之后进行一些补偿,最后就能实现外部一致性了。

原理其实比较简单,打个比方说明下:你跟妹子约会,商量好了 12 点整在电影院门口碰头,结果你等到 12 点还没见到人。这时候你是不会直接离开的,因为你会想可能是两人表的时间没对准,在妹子看来还没到 12 点。然后你一直等到 12:30,发现妹子还没来,你就知道自己是被放鸽子了,毕竟表不准也不太可能差这么多。更进一步,假如你能精确知道误差范围,譬如说误差不超过 10 分钟,那么你等到 12:10 就能知道肯定等不来人了。

Spanner 的事务正是这么做的,核心点就是事务提交的时候,会等待误差范围那么长的时间,然后才给客户端返回。这样一来,客户端接着再启动事务,或者客户端用某种方式通知另一个机房的客户启动事务(即使使用量子通信),新事务的取到的时间一定会比前面那个事务提交的时间要晚。

CockroachDB 的外部一致性

CockroachDB 用的是 HLC(混合逻辑时钟),使用的是结合物理时钟和逻辑时钟的时间戳。这个其实是权衡之后的方案:主打场景是类似 Spanner 那样的全球化部署,但是作为开源方案,也不可能用专有设备来搞一套 TrueTime。如果退而求其次用 NTP 的话,时钟误差无法控制下来会很大程度上影响性能。

HLC 是怎么一回事呢?简单理解下,就是两个事务如果时间间隔大的话,用物理时间能进行定序,如果物理时间上很接近,就依靠逻辑时钟来进行排序。

逻辑时钟的工作方式是,每当两个节点进行通信(比如收发消息包,本质上是产生信息交换时),都进行一次时钟同步。比如 A 给 B 发消息,带上自己的时钟 100,B 收到消息后发现自己的时钟是 80,此时 B 就会把自己本地的时钟设为 101,以此来保证不同节点事件时间戳的大小能体现因果关系。

我们用前面举的例子分析一下。

第一个事务先在节点 A 写,完成后第二个事务去节点 B 读同一份数据,如果 B 是可读的,那一定意味着在这之前 A 和 B 之间发生过信息交换(可以想象一下 paxos 或者 raft),而信息交换会触发逻辑时钟同步,这样第二个事务在 B 所取到的时间戳一定大于第一个事务在 A 取到的时间戳,于是外部一致性就得到保证了。

不过 HLC 也不是绝对安全的。对于前面说的那个 3 事务的例子,CockroachDB 就可能破坏一致性。究其原因,两个写事务写的数据是没有交集的,因此它们对应的两个节点之间没有进行时钟同步,于是有可能后面的事务取到的时间戳更小。这个其实是逻辑时钟最主要的缺陷:逻辑时钟依赖于追踪系统内事件的因果关系,如果因果关系不在系统内部,就无能为力了。


参考资料


欢迎加入技术讨论 QQ 群: 481269635 (硬盘在歌唱)
comments powered by Disqus

消除 TSO 单点

2020-05-27
PD 分布式事务 TiDB

分布式事务的 Commit Point

理解分布式事务原子性(atomic)的关键所在
数据库 分布式系统 TiDB

理解 Google F1: Schema 变更算法

2015-11-18
数据库 TiDB