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

2020-06-04 00:00:00 索引 数据 事务 节点 维度

本文转载自微信公众号“字节跳动技术团队” 架构实践专栏，原文链接：

字节跳动自研强一致在线 KV &表格存储实践 - 下篇​mp.weixin.qq.com
本文选自“字节跳动基础架构实践”系列文章。

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

自从 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>

相关文章