字节跳动自研强一致在线 KV

2023-08-29 11:13:06 26

本文选自“字节跳动基础架构实践”系列文章。

“字节跳动基础架构实践”系列文章是由字节跳动基础架构部门各技术团队及专家倾力打造的技术干货内容，和大家分享团队在基础架构发展和演进过程中的实践经验与教训，与各位技术同学一起交流成长。

自从 Google 发布 Spanner 论文后，国内外相继推出相关数据库产品或服务来解决数据库的可扩展问题。字节跳动在面对海量数据存储需求时，也采用了相关技术方案。本次分享将介绍我们在构建此类系统中碰到的问题，解决方案以及技术演进。

前情回顾

字节跳动自研强一致在线 KV &表格存储实践 - 上篇

关键技术

下面我们继续展开对于关键技术中的分布式事务、分区自动分裂和合并、负载均衡这几个技术点的讨论。

分布式事务

前面在介绍接口部分时，提到了 ByteKV 原子性的 WriteBatch 和满足分布式一致性快照读的 MultiGet。WriteBatch 意味着 Batch 内的所有修改要么都成功，要么都失败，不会出现部分成功部分失败的情况。MultiGet 意味着不会读取到其他已提交事务的部分数据。

ByteKV 大致采用了以下几种技术来实现分布式事务：

集群提供一个全局递增的逻辑时钟，每个读写请求都通过该模块分配一个时间戳，从而给所有请求都分配一个全局的顺序。一个 Key 的每次更新都在系统中产生一个新的版本，保证新的写入不会影响到旧的读的快照。在写请求的流程中引入两阶段提交，保证写入可以有序、原子性的提交。

全局授时服务

毫无疑问，给所有的事件定序，能让分布式系统中的很多问题都得以简化。我们也总是见到各种系统在各种各样的物理时钟、逻辑时钟、混合逻辑时钟中取舍。ByteKV 从性能、稳定性和实现难度的角度综合考虑，在 KVMaster 服务中实现了一个提供全局递增时间戳分配的接口，供集群所有的读写模块使用，该接口保证吐出的时间戳是全局唯一且递增的。

之所以采用这样的架构，是因为我们觉得：

时钟分配的逻辑非常简单，即便是由一个单机模块来提供，也能得到稳定的延时和足够的吞吐。我们可以使用 Raft 协议来实现时钟分配模块的高可用，单机的失败绝不会成为系统的单点。

在具体实现上，为了保证时钟的稳定、高效和易用，我们也做了一些工程上的努力和优化：

同一个客户端拿时钟的逻辑是有 Batch 的，这样可以有效减少 RPC 的次数。时钟的分配要用独立的 TCP Socket，避免受到其他的 RPC 请求的干扰。时钟的分配用原子操作，完全规避锁的使用。时钟要尽量接近真实的物理时间，非常有利于一些问题的调试。

多版本

几乎所有的现代数据库系统都会采用多版本机制来作为事务并发控制机制的一部分，ByteKV 也不例外。多版本的好处是读写互不阻塞。对一行的每次写入都会产生一个新的版本，而读取通常是读一个已经存在的版本。逻辑上的数据组织如下：

相同的 Key 的多个版本会连续存储在一起，方便具体版本的定位，同时版本降序排列以减少查询的开销。

为了保证编码后的数据能够按我们期望的方式排序，对 RocksDB Key 我们采用了内存可比较编码[2]，这里之所以没有自定义 RocksDB 的 compare 函数，是因为：

Key 比较大小是在引擎读写中非常高频的，而默认的 memcmp 对性能非常友好。减少对 RocksDB 的特殊依赖，提高架构的灵活性。

为了避免同一个 Key 的多个版本持续堆积而导致空间无限膨胀，ByteKV 有一个后台任务定期会对旧版本、已标记删除的数据进行清理。在上篇中，存储引擎章节做了一些介绍。

两阶段提交

ByteKV 使用两阶段提交来实现分布式事务，其大致思想是整个过程分为两个阶段：第一个阶段叫做 Prepare 阶段，这个阶段里协调者负责给参与者发送 Prepare 请求，参与者响应请求并分配资源、进行预提交（预提交数据我们叫做 Write Intent）；第一个阶段中的所有参与者都执行成功后，协调者开始第二个阶段即 Commit 阶段，这个阶段协调者提交事务，并给所有参与者发送提交命令，参与者响应请求后把 Write Intent 转换为真实数据。在 ByteKV 里，协调者由 KVClient 担任，参与者是所有 PartitionServer。接下来我们从原子性和隔离性角度来看看 ByteKV 分布式事务实现的一些细节。

首先是如何保证事务原子性对外可见？这个问题本质上是需要有持久化的事务状态，并且事务状态可以被原子地修改。业界有很多种解法，ByteKV 采用的方法是把事务的状态当作普通数据，单独保存在一个内部表中。我们称这张表为事务状态表，和其他业务数据一样，它也分布式地存储在多台机器上。事务状态表包括如下信息：

事务状态：包括事务已开始，已提交，已回滚等状态。事务状态本身就是一个 KV，很容易做到原子性。事务版本号：事务提交时，从全局递增时钟拿到的时间戳，这个版本号会被编码进事务修改的所有 Key 中。事务 TTL：事务的超时时间，主要为了解决事务夯死，一直占住资源的情况。其他事务访问到该事务修改的资源时，如果发现该事务已超时，可以强行杀死该事务。

在事务状态表的辅助下，第二阶段中协调者只需要简单地修改事务状态就能完成事务提交、回滚操作。一旦事务状态修改完成，即可响应客户端成功， Write Intent 的提交和清理操作则是异步地进行。

第二个问题是如何保证事务间的隔离和冲突处理？ByteKV 会对执行中的事务按照先到先得的原则进行排序，后到的事务读取到 Write Intent 后进行等待，直到之前的事务结束并清理掉 Write Intent 。Write Intent 对于读请求不可见，如果 Write Intent 指向的事务 Prepare 时间大于读事务时间，那么 Write Intent 会被忽略；否则读请求需要等待之前的事务完成或回滚，才能知道这条数据是否可读。等待事务提交可能会影响读请求的延迟，一种简单的优化方式是读请求将还未提交的事务的提交时间戳推移到读事务的时间戳之后。前面说了这么多 Write Intent，那么 Write Intent 到底是如何编码的使得处于事务运行中还没有提交的数据无法被其他事务读到？这里也比较简单，只需要把 Write Intent 的版本号设置为无穷大即可。

除了上述问题外，分布式事务需要解决容错的问题。这里只讨论协调者故障的场景，协调者故障后事务可能处于已经提交状态，也可能处于未提交状态；部分 PartitionServer 中的 Write Intent 可能已经提交或清理，也可能还保留在那里。如果事务已经提交，随后的读写事务碰到遗留的 Write Intent 时，会根据事务状态表中的状态来辅助之前的事务提交或清理 Write Intent；如果事务还未提交，后续事务会在之前的事务超时（事务 TTL）后修改事务状态为已回滚，并异步地清理 Write Intent。由于 Write Intent 本身也包含着事务的相关信息，如果我们把参与者列表也记录在 Write Intent 中，就可以把事务提交的标志从原子的修改完事务状态修改为所有 Write Intent 都完成持久化，从而降低一次提交延迟；而后续的操作碰到 Write Intent 后可以根据参与者列表还原出事务状态。

分区自动分裂和合并

前面提到 ByteKV 采用 Range 分区的方式提供扩展性，这种分区方式带来的一个问题是：随着业务发展，原有的分区结构不再适用于新的业务模式。比如业务写入热点变化，热点从一个分区漂移到另一个分区。为了解决这个问题，ByteKV 实现了自动分裂的功能：通过对用户写入进行采样，当数据量超过一定阈值后，从中间将 Range 切分为两个新的 Range。分裂功能配合上调度，提供了自动扩展的能力。

分裂过程

ByteKV 实现的分裂过程比较简单，当某个 Range 发现自己已经达到分裂条件，便向 KVMaster 申请执行一次分裂并拿到新分区的相关元信息，然后在 Range 内部执行分裂操作。分裂命令和普通的操作一样，作为一条日志，发送给本 Range 的 Raft Leader；当日志提交后，状态机根据日志携带的信息，在原地拉起一个新的 Raft 副本，这些新副本共同服务分裂后的一半分区，原来的副本服务另一半分区。

在另外一些场景，比如大量的 TTL，大量的先写后删，会自动地分裂出大量的分区。当 TTL 过期、数据被 GC 后，这些分裂出来的分区就形成了大量的数据碎片：每个 Raft Group 只服务少量的数据。这些小分区会造成无意义的开销，同时维护它们的元信息也增加了 KVMaster 的负担。针对这种情况，ByteKV 实现了自动合并功能，将一些较小的区间和与之相邻的区间合并。

合并过程

合并的过程比分裂复杂，master 将待合并的两个相邻区间调度到一块，然后发起一次合并操作。如上图所示，这个过程分为两步：首先左区间发起一次操作，拿到一个同步点，然后在右区间发起合并操作；右区间会进行等待，只要当前 Server 中左区间同步点前的数据都同步完成，就能够安全地修改左右区间的元信息，完成合并操作。

负载均衡

负载均衡是所有分布式系统都需要的重要能力之一。无法做到负载均衡的系统不仅不能充分利用集群的计算和存储资源，更会因为个别节点因负载过重产生抖动进而影响服务质量。设计一个好的负载均衡策略会面对两个难点，一是需要均衡的资源维度很多，不仅有最基本的磁盘空间，还有 CPU、IO、网络带宽、内存空间等，二是在字节跳动内部，机器规格非常多样，同一个集群内的不同节点，CPU、磁盘、内存都可能不同。我们在设计负载均衡策略时采取了循序渐进的办法，首先只考虑单一维度同构机型的场景，然后扩展到多个维度异构机型。下面介绍一下策略的演进过程。

单维度调度策略

以磁盘空间单一维度为例，并假设所有节点的磁盘容量完全相同。每个节点的磁盘空间使用量等于这个节点上所有副本的数据量之和。将所有副本一一分配并放置在某一个节点上就形成了一个副本分配方案。一定有一个方案，各节点的数据量的方差值最低，这种状态我们称之为“绝对均衡”。随着数据的持续写入，节点的数据量也会持续发生变化，如果要让集群始终保持“绝对均衡”状态，就需要不断的进行调度，带来大量的数据迁移开销。不仅如此，某个维度的绝对均衡会使得其它维度的绝对均衡无法实现。从成本和可行性的角度，我们定义了一种更弱的均衡状态，称之为“足够均衡”，它放松了均衡的标准，一方面降低了调度的敏感度，少量的数据量变化不会引起频繁调度，另一方面也让多个维度同时达到这种弱均衡状态成为可能。为了直观表达“足够均衡”的定义，我们画这样一个示意图进行说明：

每个节点是一根柱子，柱子的高度是它的数据量，所有节点由高到低依次排列计算出所有节点的平均数据量 Savg，并画一条横线，叫做平均线平均数据量分别加、减一个 alpha 值得到高水位值和低水位值，alpha 可以取 Savg 的 10%或 20%，它决定了均衡的松紧程度，根据水位值画出高水位线和低水位线根据节点数据量与三条线的关系，将它们划分为四个区：高负载区/主动迁出区：节点数据量高于高水位值高均衡区/被动迁出区：节点数据量低于高水位值且高于平均值低均衡区/被动迁入区：节点数据量高于低水位值且低于平均值低负载区/主动迁入区：节点数据量低于低水位值当节点位于高负载区时，需要主动迁出副本，目标节点位于迁入区；当节点位于低负载区时，需要主动迁入副本，来源节点是迁出区当所有节点都位于两个均衡区时，集群达到“足够均衡”状态，下面这个图就是一种“足够均衡”状态

多维度调度策略

以前面的单维度调度为基础，多维度调度的目标是使集群在多个维度上同时或尽量多地达到足够均衡的状态。

我们先想象一下，每个维度都有前面提到的示意图表示它的均衡状态，N 个维度就存在 N 个图。当一个副本发生迁移的时候，会同时改变所有维度的均衡状态，也就是说所有的示意图都会发生改变。如果所有维度都变得更加均衡（均衡区的节点数变多了），或者一部分维度更均衡而另一部分维度不变（均衡区的节点数不变），那么这个迁移是一个好的调度；反正，如果所有维度都变得更加不均衡（均衡区的节点数变少了），或者一部分维度更不均衡而另一部分维度不变，那么这个迁移是一个不好的调度。还有第三种情况，一部分维度更均衡同时也有一部分维度更不均衡了，这是一个中性的调度，往往这种中性的调度是不可避免的，例如集群中只有 A、B 两个节点，A 的流量更高而 B 的数据量更高，由 A 向 B 迁移副本会使流量更均衡而数据量更不均衡，由 B 向 A 迁移副本则相反。

为了判断这种中性的调度能否被允许，我们引入了优先级的概念，为每个维度赋予一个唯一的优先级，牺牲低优维度的均衡度换来高优维度更加均衡是可被接受的，牺牲高优维度的均衡度换来低优维度更加均衡则不可被接受。

仍然考虑前面的例子，因为流量过高会影响读写响应时间进而影响服务质量，我们认为流量的优先级高于数据量优先级，因此由 A 向 B 迁移可被接受。但是也存在一个例外，假设 B 节点的剩余磁盘空间已经接近 0，并且连集群中最小的副本都无法容纳时，即使流量的优先级更好，也不应该允许向 B 迁移任何副本了。为了直观表达这种资源饱和状态，我们在示意图上增加一条硬限线：

配合这个示意图，多维度的负载均衡策略如下：

将多个维度按照优先级排序，从高优维度到低优维度依次执行上文描述的单维度调度策略，仅对流程做少量修改：源节点上最接近Sbest但小于Sbest的副本为候选迁移对象，如果它导致任一下列情况出现，则将它排除，选择下一个副本作为候选对象，直到找到合适的副本为止：迁移之后，目标机器在更高优维度上将处于高水位线以上迁移之后，目标机器在更低优维度上将处于硬限线以上如果对于某一目标节点，源节点上无法选出迁移对象，将排在目标节点前一位的节点作为新的目标节点，重复上述过程如果对于所有目标节点，源节点上仍然无法选出迁移对象，将该源节点从排序列表中剔除，重复上述过程

异构机型调度策略

对于同构机型，一个单位的负载在每个节点上都会使用同样比例的资源，我们可以仅根据负载值进行调度，而不必这些负载使用了多少机器资源，但在异构机型上这是不成立的。举个例子，同样是从磁盘上读取 1MB 的数据，在高性能服务器上可能只占用 1%的 IO 带宽和 1%的 CPU cycle，而在虚拟机上可能会占用 5%的 IO 带宽和 3%的 CPU cycle。在不同性能的节点上，同样的负载将产生不同的资源利用率。

要将前面的调度策略应用到异构机型的场景中，首先要将按负载值进行调度修改为按资源利用率进行调度。对于数据量来说，要改为磁盘空间利用率；对于流量来说，要改为 CPU 利用率、IO 利用率等等。为了简化策略，我们将内存、磁盘 IO、网络 IO 等使用情况全部纳入到 CPU 利用率中。解释一下为什么这么做：

对内存来说，我们的进程内存使用量的上限是通过配置项控制的，在部署时，我们会保证内存使用量一定不会超过物理内存大小，剩余物理内存全部用于操作系统的 buffer/cache，实际上也能够被我们利用。内存大小会通过影响诸如 MemTable、BlockCache 的大小而影响节点性能，而这种影响最终会通过 CPU 和 IO 的使用量反映出来，所以我们考察 CPU 和 IO 的利用率就能把内存的使用情况纳入进来。对于磁盘 IO 来说，IO 利用率最终也会反映在 CPU 利用率上（同步 IO 体现在 wa 上，异步 IO 体现在 sys 上），因此我们考察 CPU 利用率就能把磁盘 IO 的使用情况纳入进来。CPU 中有三级 cache，也有寄存器，在考虑 CPU 利用率时，会把它当作一个整体，不会单独分析 cache 或是寄存器的使用情况。内存和磁盘可以想象成 CPU 的第四、五级 cache，内存越小、磁盘 IO 越慢，CPU 的利用率越高，可以将它们视为一个整体。

异构调度要解决的第二个问题是，资源利用率和负载值之间的转换关系。举个例子，A、B 两个节点的 CPU 利用率分别是 50%和 30%，节点上每个副本的读写请求也是已知的，如何从 A 节点选择最佳的副本迁移到 B 节点，使 A、B 的 CPU 利用率差距最小，要求我们必须计算出每个副本在 A、B 节点上分别会产生多少 CPU 利用率。为了做到这一点，我们尽可能多的收集了每个副本的读写请求信息，例如：

读写请求的 key、value 大小读的 cache 命中率更新的随机化程度、删除的比例

根据这些信息，将每个读写请求转换成 N 个标准流量。例如，一个 1KB 以内的请求是一个标准流量，一个 1~2KB 的请求是 2 个标准流量；命中 cache 的请求是一个标准流量，未命中 cache 的请求是 2 个标准流量。知道节点上总的标准流量值，就能根据 CPU 利用率算出这个节点上一个标准流量对应的 CPU 利用率，进而能够算出每个副本在每个节点上对应的 CPU 利用率了。

综上，异构机型调度策略只需要在多维度调度策略的基础上做出如下修改：

节点按照资源利用率排序，而不是负载值每个副本的负载值要分别转换成源节点的资源利用率和目标节点的资源利用率，在异构机型上，同一个副本的资源利用率会有较大的不同

其它调度策略

KVMaster 中，有一个定时任务执行上述的负载均衡策略，叫做“负载均衡调度器”，这里不再赘述；同时，还有另一个定时任务，用来执行另一类调度，叫做“副本放置调度器”，除了副本安全级别（datacenter/rack/server）、节点异常检测等基本策略之外，它还实现了下面几种调度策略：

业务隔离策略：不同 namespace/table 可以存放在不同的节点上。每个 namespace/table 可指定一个字符串类型的 tag，每个节点可指定一个或多个 tag，副本所在 namespace/table 的 tag 与某节点 tag 相同时，才可放置在该节点上。调度器会对不满足 tag 要求的副本进行调度。热点检测：当某个数据分片的数据量达到一定阈值时会发生分裂，除此之外，当它的读写流量超过平均值的某个倍数后，也会发生分裂。当分裂发生后，其中一个新产生的分片（左边或右边）的所有副本都会迁移至其他节点，避免节点成为访问热点。碎片检测：当某个数据分片的数据量和读写流量都小于平均值的一定比例时，会与它所相邻的分片进行合并。合并前会将小分片的所有副本迁移至相邻分片所在的节点上。

表格层

前面提到，KV 数据模型过于简单，很难满足一些复杂业务场景的需求。比如：

字段数量和类型比较多需要在不同的字段维度上进行复杂条件的查询字段或查询维度经常随着需求而变化。

我们需要更加丰富的数据模型来满足这些场景的需求。在 KV 层之上，我们构建了表格层 ByteSQL，由前面提到的 SQLProxy 实现。ByteSQL 支持通过结构化查询语言（SQL）来写入和读取，并基于 ByteKV 的批量写入（WriteBatch）和快照读接口实现了支持读写混合操作的交互式事务。

表格模型

在表格存储模型中，数据按照数据库（database）, 表（table）两个逻辑层级来组织和存放。同一个物理集群中可以创建多个数据库，而每个数据库内也可以创建多个表。表的 Schema 定义中包含以下元素：

表的基本属性，包括数据库名称，表名称，数据副本数等。字段定义：包含字段的名字，类型，是否允许空值，默认值等属性。一个表中须至少包含一个字段。索引定义：包含索引名字，索引包含的字段列表，索引类型（Primary Key，Unique Key，Key 等）。一个表中有且仅有一个主键索引（Primary Key），用户也可以加入二级索引（Key 或 Unique Key 类型）来提高 SQL 执行性能。每个索引都可以是单字段索引或多字段联合索引。

表中的每一行都按照索引被编码成多个 KV 记录保存在 ByteKV 中，每种索引类型的编码方式各不相同。Primary Key 的行中包含表中的所有字段的值，而二级索引的行中仅仅包含定义该索引和 Primary Key 的字段。具体每种索引的编码方式如下：

Primary Key: pk_field1, pk_field2,... => non_pk_field1, non_pk_field2... Unique Key: key_field1, key_field2,...=> pk_field1, pk_field2... NonUnique Key: key_field1, key_field2,..., pk_field1, pk_field2...=> <null>

其中 pk_field 是定义 Primary Key 的字段，non_pk_field 是表中非 Primary Key 的字段，key_field 是定义某个二级索引的字段。=> 前后的内容分别对应 KV 层的 Key 和 Value 部分。Key 部分的编码依然采用了上述提到的内存可比较编码，从而保证了字段的自然顺序与编码之后的字节顺序相同。而 Value 部分采用了与 protobuf 类似的变长编码方式，尽量减少编码后的数据大小。每个字段的编码中使用 1 byte 来标识该值是否为空值。

全局二级索引

用户经常有使用非主键字段做查询条件的需求，这就需要在这些字段上创建二级索引。在传统的 Sharding 架构中（如 MySQL Shard 集群），选取表中的某个字段做 Sharding Key，将整个表 Hash 到不同的 Shard 中。由于不同 Shard 之间没有高效的分布式事务机制，二级索引需要在每个 Shard 内创建（即局部二级索引）。这种方案的问题在于如果查询条件不包含 Sharding Key，则需要扫描所有 Shard 做结果归并，同时也无法实现全局唯一性约束。

为解决这种问题，ByteSQL 实现了全局二级索引，将主键的数据和二级索引的数据分布在 ByteKV 的不同的分片中，只根据二级索引上的查询条件即可定位到该索引的记录，进一步定位到对应的主键记录。这种方式避免了扫描所有 Shard 做结果归并的开销，也可以通过创建 Unique Key 支持全局唯一性约束，具有很强的水平扩展性。

交互式事务

ByteSQL 基于 ByteKV 的多版本特性和多条记录的原子性写入（WriteBatch），实现了支持快照隔离级别（Snapshot Isolation）的读写事务，其基本实现思路如下：

用户发起 Start Transaction 命令时，ByteSQL 从 ByteKV Master 获取全局唯一的时间戳作为事务的开始时间戳（Start Timestamp），Start Timestamp 既用作事务内的一致性快照读版本，也用作事务提交时的冲突判断。事务内的所有写操作缓存在 ByteSQL 本地的 Write Buffer 中，每个事务都有自己的 Write Buffer 实例。如果是删除操作，也要在 Write Buffer 中写入一个 Tombstone 标记。事务内的所有读操作首先读 Write Buffer，如果 Write Buffer 中存在记录则直接返回（若 Write Buffer 中存在 Tombstone 返回记录不存在）；否则尝试读取 ByteKV 中版本号小于 Start Timestamp 的记录。用户发起 Commit Transaction 命令时，ByteSQL 调用 ByteKV 的 WriteBatch 接口将 Write Buffer 中缓存的记录提交，此时提交是有条件的：对于 Write Buffer 中的每个 Key，都必须保证提交时不能存在比 Start Timestamp 更大的版本存在。如果条件不成立，则必须 Abort 当前事务。这个条件是通过 ByteKV 的 CAS 接口来实现的。

由上述过程可知，ByteSQL 实现了乐观模式的事务冲突检测。这种模式在写入冲突率不高的场景下非常高效。如果冲突率很高，会导致事务被频繁 Abort。

执行流程优化

ByteSQL 提供了更加丰富的 SQL 查询语义，但比起 KV 模型中简单的 Put，Get 和 Delete 等操作却增加了额外的开销。SQL 中的 Insert，Update 和 Delete 操作实际都是一个先读后写的流程。以 Update 为例，先使用 Get 操作从 ByteKV 读取旧值，在旧值上根据 SQL 的 Set 子句更新某些字段生成新值，然后用 Put 操作写入新值到 ByteKV。

在一些场景下，某些字段的值可能是 ByteSQL 内自动生成的（如自动主键，以及具有 DEFAULT/ON UPDATE CURRENT_TIMESTAMP 属性的时间字段）或根据依赖关系计算出来的（如 SET a = a+1），用户需要在 Insert，Update 或 Delete 操作之后立即获取实际变更的数据，需要在写入之后执行一次 Select 操作。总共需要两次 Get 操作和一次 Put 操作。为了优化执行效率，ByteSQL 中实现了 PostgreSQL/Oracle 语法中的 Returning 语义：在同一个 Query 请求中将 Insert/Update 的新值或 Delete 的旧值返回，节省了一次 Get 开销。

UPDATE table1 SET count = count + 1 WHERE id >= 10 RETURNING id, count;

在线 schema 变更

业务需求的不断演进和变化导致 Schema 变更成为无法逃避的工作，传统数据库内置的 Schema 变更方案一般需要阻塞整表的读写操作，这是线上应用所无法接受的。ByteSQL 使用了 Google F1 的在线 Schema 变更方案[3]，变更过程中不会阻塞线上读写请求。

ByteSQL Schema 元数据包含了库和表的定义，这些元数据都保存在 ByteKV 中。SQLProxy 实例是无状态的，每个实例定期从 ByteKV 同步 Schema 到本地，用来解析并执行 Query 请求。同时集群中有一个专门的 Schema Change Worker 实例负责监听并执行用户提交的 Schema 变更任务。Schema Change Worker 一旦监听到用户提交的 Schema 变更请求，就将其放到一个请求队列中并按序执行。本节从数据一致性异常的产生和解决角度，阐述了引入 Schema 中间状态的原因。详细的正确性证明可以参考原论文。

由于不同的 SQLProxy 实例加载 Schema 的时机并不相同，整个集群在同一时刻大概率会有多个版本的 Schema 在使用。如果 Schema 变更过程处理不当，会造成表中数据的不一致。以创建二级索引为例，考虑如下的执行流程：

Schema Change Worker 执行了一个 Create Index 变更任务，包括向 ByteKV 中填充索引记录和写入元数据。SQLProxy 实例 1 加载了包含新索引的 Schema 元数据。SQLProxy 实例 2 执行 Insert 请求。由于实例 2 尚未加载索引元数据，Insert 操作不包含新索引记录的写入。SQLProxy 实例 2 执行 Delete 请求。由于实例 2 尚未加载索引元数据，Delete 操作不包含新索引记录的删除。SQLProxy 实例 2 加载了包含新索引的 Schema 元数据。

第 3 步和第 4 步都会导致二级索引和主键索引数据的不一致的异常：第 3 步导致二级索引记录的缺失（Lost Write），第 4 步导致二级索引记录的遗留（Lost Delete）。这些异常的成因在于不同 SQLProxy 实例加载 Schema 的时间不同，导致有些实例认为索引已经存在，而另外一些实例认为索引不存在。具体而言，第 2 步 Insert 的异常是由于索引已经存在，而写入方认为其不存在；第 3 步的 Delete 异常是由于写入方感知到了索引的存在，而删除方未感知到。实际上，Update 操作可能会同时导致上述两种异常。

为了解决 Lost Write 异常，我们需要保证对于插入的每行数据，写入实例需要先感知到索引存在，然后再写入；而对于 Lost Delete 异常，需要保证同一行数据的删除实例比写入实例先感知到索引的存在（如果写入实例先感知索引，删除实例后感知，删除时有可能会漏删索引而导致 Lost Delete）。

然而，我们无法直接控制不同 SQLProxy 实例作为写入实例和删除实例的感知顺序，转而使用了间接的方式：给 Schema 定义了两种控制读写的中间状态：DeleteOnly 状态和 WriteOnly 状态，Schema Change Worker 先写入 DeleteOnly 状态的 Schema 元数据，待元数据同步到所有实例后，再写入 WriteOnly 状态的 Schema 元数据。那些感知到 DeleteOnly 状态的实例只能删除索引记录，不能写入索引记录；感知到 WriteOnly 状态的实例既可以删除又可以插入索引记录。这样就解决了 Lost Delete 异常。

而对于 Lost Write 异常，我们无法阻止尚未感知 Schema WriteOnly 状态的实例写入数据（因为整个 Schema 变更过程是在线的），而是将填充索引记录的过程（原论文中称之为 Reorg 操作）推迟到了 WriteOnly 阶段之后执行，从而既填充了表中存量数据对应的索引记录，也填充了那些因为 Lost Write 异常而缺失的索引记录。待填充操作完成后，就可以将 Schema 元数据更新为对外可见的 Public 状态了。

我们通过引入两个中间状态解决了 Schema 变更过程中数据不一致的异常。这两个中间状态均是对 ByteSQL 内部而言的，只有最终 Public 状态的索引才能被用户看到。这里还有一个关键问题：如何在没有全局成员信息的环境中确保将 Schema 状态同步到所有 SQLProxy 实例中？解决方案是在 Schema 中维护一个全局固定的 Lease Time，每个 SQLProxy 在 Lease Time 到期前需要重新从 ByteKV 中加载 Schema 来续约。Schema Change Worker 每次更新 Schema 之后，需要等到所有 SQLProxy 加载成功后才能进行下一次更新。这就需要保证两次更新 Schema 的间隔需要大于一定时间。至于多长的间隔时间是安全的，有兴趣的读者可以详细阅读原论文[3]来得到答案。如果某个 SQLProxy 因为某种原因无法在 Lease Time 周期内加载 Schema，则设置当前 ByteSQL 实例为不可用状态，不再处理读写请求。

未来探讨

Cloud Native

随着 CloudNative 的进一步发展，以无可匹敌之势深刻影响着现有的开发部署模型。ByteKV 也将进一步探索与 CloudNative 的深入结合。探索基于 Kubernetes 的 auto deployment, auto scaling, auto healing。进一步提高资源的利用率，降低运维的成本，增强服务的易用性。提供一个更方便于 CloudNative 用户使用的 ByteKV。

参考文献

[1] Ongaro D, Ousterhout J. In search of an understandable consensus algorithm (extended version)[J]. 2013.

[2] https://github.com/facebook/mysql-5.6/wiki/MyRocks-record-format#memcomparable-format

[3] Rae I, Rollins E, Shute J, et al. Online, asynchronous schema change in F1[J]. Proceedings of the VLDB Endowment, 2013, 6(11): 1045-1056.

[4] Kulkarni S, Demirbas M, Madeppa D, et al. Logical physical clocks and consistent snapshots in globally distributed databases[C]//The 18th International Conference on Principles of Distributed Systems. 2014.

[5] Peng D, Dabek F. Large-scale incremental processing using distributed transactions and notifications[J]. 2010.

[6] https://www.cockroachlabs.com/blog/how-cockroachdb-distributes-atomic-transactions/

[7] https://www.cockroachlabs.com/blog/serializable-lockless-distributed-isolation-cockroachdb/

[8] https://www.cockroachlabs.com/blog/living-without-atomic-clocks/

[9] Shute J, Oancea M, Ellner S, et al. F1-the fault-tolerant distributed rdbms supporting googles ad business[J]. 2012.

[10] Corbett J C, Dean J, Epstein M, et al. Spanner: Google’s globally distributed database[J]. ACM Transactions on Computer Systems (TOCS), 2013, 31(3): 1-22.

[11] Ongaro D. Consensus: Bridging theory and practice[D]. Stanford University, 2014.

[12] Roohitavaf M, Ahn J S, Kang W H, et al. Session guarantees with raft and hybrid logical clocks[C]//Proceedings of the 20th International Conference on Distributed Computing and Networking. 2019: 100-109.

[13] Huang G, Cheng X, Wang J, et al. X-Engine: An optimized storage engine for large-scale E-commerce transaction processing[C]//Proceedings of the 2019 International Conference on Management of Data. 2019: 651-665.