Spanner - External consistency

external consistency == linearizable == strict serializable

经典数据库理论提到的隔离性是 Serializable, 允许事务以等价于串行的方式执行，但并没有对先对顺序进行约束，即a, b 事务执行，可以等价于是a,b 也可以是 b,a。

serializable 与 real-time 没有关联，仅仅规定了系统边界之内的处理效果。

strict serializable 严格串行化 在此基础上，增加了一条约束：

b在a提交之后开始执行，则后的等价结果只能是 a,b.

strict serializable 与 real-time 有关联，除了系统边界之内的处理效果外，要求必须与系统之外的真实世界保持因果一致性。

线性一致性（linearizable），严格串行化（strict serializable），外部一致性（external consistency）

都是描述了系统与真实世界保持一种一致性，必须借助于同步或者真实时间才能达到。

同步是引入全局单点，与真实时间一样，用来对行为（读/写）进行确定与真实世界一致的顺序。

若仅需要串行一致性，则系统内部可以不依赖全局单点和读取外部真实时间就能解决，比如使用数据依赖派生出来的时间（逻辑时钟、向量时钟等虚拟设备）。

外部时间没有严格可读取的“register”，也即，从外部世界获取的时钟是存在误差的，导致系统的运算频率（处理单个事务/原子单元）不能提升到误差之内。

Spanner 的 外部一致性原理

spanner 借助了真实时钟，存在误差, e.

TrueTime 由 GPS + atomic-Clock 设施组成，每个idc 一个 GPS + 多个 atomic-Clock。

它们之间进行同步和纠正，然后每个服务器从多个时钟源头进行获取时间，进行调整本地时间和不确定（误差）窗口:e.

用T.abs 表示真实时间

TT.now() 获取一个时间窗口: [oldest, latest],

如果真实时间是 t, 则，t未于这个区间内. 这是时钟设施保证的。

事务时间戳的赋予:

T.commit < TT.now().latest

事务提交结束真实时间T.abs > T.commit, 这一步通过等待确保 TT.now().oldest 返回大于 T.commit.

通过这2条确保：

T.commit > TT.now().latest > T.abs

T.commit < TT.now().latest < T.commit.abs

如果a, b 2个事务，a提交后b开始执行，则:

T.a.commit.abs > T.a.commit

T.a.commit.abs < T.b.start.abs < T.b.commit

于是T.a.commit < T.b.commit

即，a的事务时间戳小于b的事务时间戳。

T.a.commit.abs < T.b.start.abs => T.a.commit < T.b.commit

基于时间戳进行可见性判断，可以获得与外部一致的视图。

来源 https://zhuanlan.zhihu.com/p/139070683