CockroachDB: The Resilient Geo-Distributed SQL Database

本文介绍了一个叫CockroachDB的数据库系统。

INTRODUCTION

对于现代数据库来说，OLTP的工作负载越来越与地理分布有关。一些应用可能针对不同的地区分布有着不同的数据库需求，比如某些地区的数据需要有更严格的权限控制满足法律法规，有些地区则是处于快速增长的阶段，需要考虑成本、延时、性能等等的情况。

CockroachDB作为一款商业DBMS，满足了全球化公司关于数据库系统的种种需求：

容错和高可用性：在不同的地区为每个分区至少维护三个副本。节点故障，能自动恢复；
地理分布和副本放置：CockroachDB支持水平伸缩，添加节点时自动增加容量并迁移数据。并根据需求选择最优的数据放置方法，同时支持用户自定义选择；
高性能的事务：CockroachDB的事务协议支持跨多个分区的分布式事务，而不需要特定的硬件；

除此之外，CockroachDB还实现了最新的查询优化器和分布式SQL执行引擎来支持更全面的SQL标准。

SYSTEM OVERVIEW

Architecture of CockroachDB

CockroachDB是典型的shared-nothing架构，其所有节点都参与计算和存储。这些节点可由同个数据中心或者多个数据中心组成，client可以连接到任意的节点。在单个节点内部具备以下的分层架构：

SQL

SQL层是最上层，负责与client进行交互，包括了解析器、优化器和SQL执行引擎，其将SQL语句转化成对KV存储的读写请求。SQL层并不清楚数据的具体分区情况。

Transactional KV

SQL层的请求会来到事务KV层，负责确保跨KV对的更新原子性。

Distribution

该层根据key排序呈现了一个key空间的抽象，包括系统元数据和用户数据都可以在该key空间内查找。CockroachDB使用范围分区的方法将数据划分为大小约为64MiB的连续有序块，称之为Range。Range之间的顺序在一组系统Range内的两级索引结构（前面说过用于内部数据结构和元数据的系统数据也会组成Range）中维护。Range会被缓存起来用于快速查找，同时该层也主要负责对上层查询做路由。

Range大小为64MB，并根据需要对Range进行合并和拆分（数据太多就拆分，太少就合并，还有根据一些热点策略做Range划分）。

Replication

默认情况下，每个Range都是三个副本，每个副本存储在不同的节点上。

Storage

最底下的就是存储层，CockroachDB主要依赖了RocksDB。

Fault Tolerance and High Availability

Replication using Raft

CockroachDB使用Raft算法来进行一致性的复制，其中Range的副本会组成一个Raft组，每个副本要么是leader，要么是follower。CockroachDB的复制单元是Command，它表示的是对存储引擎进行的一系列底层修改，当Raft commit日志的时候，每个副本会将Command应用到存储引擎上。

CockroachDB使用Range级别的租约，其中一般是Raft组的leader来充当租约持有者，它是唯一可以提供最新读取信息或者发起提议的副本，所有的写入也是通过租约持有者进行。对于用户Range，节点会每隔4.5秒在系统范围内发送一套特殊记录的心跳；对于系统Range，则是每9秒更新一次租约。

同时为了保证一致性，一次只有一个副本存留，尝试获取租约的副本会通过提交特殊的租约获取日志来达成目的。

Membership changes and automatic load (re)balancing

集群支持节点的添加和删除，节点的变更会导致负载在集群活动节点之间重新分布。

对于短暂的故障，只要大多数副本可用，Raft算法能保证CockroachDB正常运行。如果leader失败，则依赖Raft重新选举leader。对于故障节点重新加入集群，则可以通过以下方式追上更新：发送完整Range数据的快照；发送一组要Apply的Raft缺失日志。二选一。

对于长期故障，CockroachDB则是会根据不受影响的副本，创建一个新的副本，将其放到合适的位置。

Replica placement

CockroachDB支持手动和自动来控制副本的放置。自动放置副本的机制会根据一定的约束条件进行，并且会尽量平衡负载。

Data Placement Policies

CockroachDB的副本和租约holder的放置策略可以由用户根据性能和容错能力决定：

副本按地理位置分区；
租约holder按地理位置分区；
重复索引：通过基于表来复制索引，并将每个索引的lease holder固定到特定地区，CockroachDB就可以通过较快的本地读取功能，同时提高容错性，但可能会带来写放大和跨区写延时的提高；

TRANSACTIONS

CockroachDB的事务可以跨越整个key空间，能在保证ACID的前提下访问到跨越整个集群的数据。CockroachDB是使用MVCC的变形来支持串行化隔离的。

Overview

SQL事务从SQl连接的节点开始，该节点负责扮演事务协调者的角色。

Execution at the transaction coordinator

下面的算法给出了基于协调者角度的事务处理逻辑，在执行事务过程中，协调者接受一些列来自SQL层的KV操作。

从途中可以看出，在下一个操作发出前，需要对当前操作进行应答，为了提高性能，协调者做了两个优化：写流水线和并行提交。因此，协调者需要跟踪还没完全复制成功的操作和维护了事务时间戳（第一行）。

写流水线：如果某个操作未尝试提交，并且该操作与先前任何操作都没有重叠，则可能立即执行该操作（第七行）。这就是为什么写流水线可以对不同key的进行多个操作。如果该操作依赖于先前的操作完成复制，则需要pipeline等待。inflightOps就是对运行中的状态进行追踪。第九行就是协调者将操作发送给租约持有者并等待回应。如果返回的时间戳更待，意味着存在了另一个事务影响了租约持有者的时间戳。协调者此时会调整事务时间戳，并通过一轮RPC去验证新时间戳返回的值是否相同，如果不同则事务失败。（第十到十四行）

本质就是事务内语句流水线并行执行，如果两条语句有操作重叠，则通过事务上下文追踪执行过的key，如果重叠则需要等待其执行成功。

并行提交：一个标准的2PC，往往需要两轮consensus，一轮完成Prepare，一轮将事务设置为Committed。并行提交的做法是使用了staging来表示一个事务操作的所有写入是否已经都复制完成，持久化staging状态和Prepare写数据同时进行（第五行），假设两者都成功，则协调者可以立即确认事务已经提交（第十五行），并且在终止前会异步将事务状态记录为commit。（十六和十七行）

Execution at the leaseholder

如下，当lease holder接收到来自协调者的操作请求时，会按下图执行。第二行险检查租约有效性，第三行会去获取操作依赖的所有key的latch。第四行会校验相关依赖的操作完成。第五和第六行则是在执行写操作时，保证时间戳在任何冲突读取之后，并且根据需要增加时间戳。

接下来则是评估操作需要转换为对存储引擎的哪些操作。如果不是事务则无需要等待复制，lease holder可以直接响应协调者。如果是写操作则会被复制，达成共识后会应用到本地引擎。最后释放锁，响应协调者。

Atomicity Guarantees

CRDB通过观察所有事务的write intents来实现原子提交。write intents就是一个常规的MVCC kv对，所有写入都先写到临时的write intents，其带有的一个元数据指示是intents。该元数据会指向一个事务记录，事务记录就是一个特殊的key，保存了事务当前的状态：pending, staging, committed和aborted。通过write intents，一个Reader会读取其事务记录，如果事务记录已提交，则Reader会将intents视为常规值，并执行清除操作。如果事务是pending的，则会阻塞直至完成。如果是事务是Staging，则可能是commit，也可能是Abort，Reader尝试中止该事务。（如果所有写操作都已经完成复制，实际上就是commit，并对其进行更新）。

Concurrency Control

如前所述，CRDB对每个事务都以commit时间戳来执行写入和读取。这样可以实现串行化的执行，但同时也会因为事物之间的冲突需要调整时间戳。

Write-read conflicts

读请求遇到未commit的intent，如果其时间戳更小，则需要等待事务结束。否则可以忽略，并不需要等待。

Read-write conflicts

以时间戳tb写一个key的时候，如果存在对该key有更大时间戳tb的读请求，则无法直接写入。CRDB强制将写入事务的commit时间戳增加到tb以后。

Write-write conflicts

写请求如果遇到一个时间戳更小的未commit intent，则等到较早的事务完成。相反，遇到较大时间戳的committed key，则会推进该时间戳。写写冲突可能导致冲突，CRDB会采用分布式死锁检测算法来中止循环等待中的一个事务。

Read Refreshes

前面提到的冲突会导致事务的commit timestamp推进。如果可以证明事务在ta读取的数据于(ta, tb]时间间隔内没有更小，可以将事务的read timestamp推进到tb > ta。如果发生了数据变更，则会导致事务重启。

为了确定时间戳是否可以推进，CRDB会在事务的读取集中维护键的集合，并会发出一个Read Refreshes请求来确认key在某个时间间隔内有没有被更新。

Follower Reads

CRDB允许非租约持有者的副本通过查询修饰符“AS OF SYSTEM TIME”来为带有时间戳的只读查询提供服务。为了提供该功能，其要求在给定时间戳T上执行读取操作的非租约持有者副本确认：将来不存在任何写操作使得读操作无效，并且具备读取所需要的所有数据。即要求Follower提供在时间戳T上的读取内容，并且租约持有者不再接受时间戳T'<=T的写操作，Follower还要追上影响到MVCC快找的Raft前缀日志。

因此，租约持有者需要记录所有传入请求的时间戳，并定期在节点级别生成closed timestamp，在该时间戳以前，将不接受进一步的写操作。closed timestamp与当时的Raft日志索引一起在副本之间定期交换，这样Follower副本就可以使用该状态来决定它们是否剧本在特定时间戳下提供一致性读取所需的所有数据。

CLOCK SYNCHRONIZATION

CRDB不依赖特定的硬件来进行时钟同步，通过NTP或者Amazon Time Sync Service在公有云或者私有云的服务器即可。

Hybrid-Logical Clocks

CRDB在集群的每个节点里都维护一个混合逻辑时钟HLC，该时钟提供了物理时间和逻辑时间组合的时间戳。物理时间基于节点的粗同步系统时钟，洛基适中则是基于Lamport时钟。

HLC提供了一些重要的属性：

HLC在每次节点交换时钟时通过其逻辑组建提供了因果追踪。节点在发送消息的时候会附加上HLC时间戳，并使用接收到的信息里的时间戳来更新本地时钟。
HLC在单个节点上的重启内或者重启之间都提供了严格的单调性。
在瞬态时钟的偏斜波动情况下，HLC能提供自我稳定的功能。

Uncertainty Intervals

CRDB不支持严格的可串行化，而是通过追踪每个事务的不确定间隔来满足单key线性化属性，事务协调者的本地HLC会分配一个commit_ts，不确定性间隔为[commit_ts, commit_ts + max_offset]。

当事务遇到在高于commit_ts且在不确定间隔内遇到key时，它会执行不确定性重启，将commit_ts移动到高于不确定值的位置，并保持不确定间隔的上限不变。

Behavior under Clock Skew

这里主要是考虑时钟偏离范围的系统行为。本身在单个Range内，通过Raft日志的读写是能够保持任意时钟偏斜下的一致性。但因为引入了Range的租约，如果存在较大的时钟偏移，多个节点可能会发生脑裂，都认为自己拥有租约。CRDB采用两种保护措施来做保护：

Range租约包含了开始和结束时间戳。租约持有者不能为超出租约间隔的读写提供服务；
每次写入Range的Raft日志时，都会包含建议使用的Range租约序列号。由于Range本身的租约变更也会被写入Range的Raft日志，因此某个时刻内只有一个租约持有者能够对Range进行变更；

SQL

SQL Data Model

每个SQL表或者索引都是存储在若干个Ranges里。所有的用户数据则存储在若干个索引中，其中一个是primary index，primary index在主key上，其他列存储在value里。Secondary Index则是在索引key上，并且还会存储主key以及所以模式所示定的任意数量列。

Query Optimizer

CRDB中的转换规则时通过Optgen的DSL编写的，提供了用于定义、匹配等简洁语法。Optgen编译为Go，然后与其余CRDB代码库无缝衔接。另外，考虑到CRDB的某些规则涉及到地理分布和分区性质，因此优化器会将数据分布考虑到cost model内，会复制辅助索引以使每个地区都有其自己的副本，从而提高性能，减少跨地区的数据通信。

Query Planning and Execution

CRDB的SQL查询执行存在两种模式： gateway-only mode和distributed mode。

由于分布层提供了一个全局key空间的抽象视图，SQL层可以对任何节点上的Ranges执行读写操作。CRDB根据需要的网络带宽来决定采用哪种模型。对于distributed mode，CRDB通过物理计划阶段，将查询优化器的计划转换为物理SQL运算符的有向无环图。物理计划将逻辑扫描操作分为多个TableReader操作符，每个节点都会包含一个扫描需要读取的Range。扫描被分割后，剩余的逻辑运算符会被安排到与TableReader相同的节点上，从而将filters, joins, and aggregations这些推到尽可能接近物理数据的位置。

在数据流内部，CRDB根据输入基数和计划复杂性采用两种不同的执行引擎： Row-at-a-time execution engine和Vectorized execution engine。前者主要是基于Volcano迭代器模型，一次一行。后者则是采用受MonetDB/X100启发的向量化执行引擎，主要面向的是列数据，而不是行，从CRDB的KV层读取时，会将磁盘数据从行格式转换为列格式，才发送会有用户之前再次将列格式转换为行格式。

Schema Changes

CRDB使用一种协议来执行Schema Changes，例如添加列或二级索引，该协议允许在Schema Changes期间保持表能提供在线的读写服务，允许不同的节点在不同时间内异步过渡到新表。具体的实现是将每个Schema Changes分解为一系列增量变更的协议来实现。

CONCLUSION

CockroachDB是一个开源的SQL DMBS，支持全球性分布的OLTP业务，并提供了灵活的SQL使用，保证了更好的伸缩性和高可靠性、高性能。