Spanner - External consistency

2022-06-02 00:00:00 事务 时间 真实 时钟 误差

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

相关文章