文章作者:字节跳动基础架构团队
内容来源:字节跳动技术团队
导读:自从 Google 发布 Spanner 论文后,国内外相继推出相关数据库产品或服务来解决数据库的可扩展问题。字节跳动在面对海量数据存储需求时,也采用了相关技术方案。本次分享将介绍我们在构建此类系统中碰到的问题,解决方案以及技术演进。
互联网产品中存在很多种类的数据,不同种类的数据对于存储系统的一致性,可用性,扩展性的要求是不同的。比如,金融、账号相关的数据对一致性要求比较高,社交类数据例如点赞对可用性要求比较高。还有一些大规模元数据存储场景,例如对象存储的索引层数据,对一致性,扩展性和可用性要求都比较高,这就需要底层存储系统在能够保证数据强一致的同时,也具有良好的扩展性。在数据模型上,有些数据比如关系,KV 模型足够用;有些数据比如钱包、账号可能又需要更丰富的数据模型,比如表格。
分布式存储系统对数据分区一般有两种方式:Hash 分区和 Range 分区。Hash 分区对每条数据算一个哈希值,映射到一个逻辑分区上,然后通过另外一层映射将逻辑分区映射到具体的机器上,很多数据库中间件、缓存中间件都是这样做的。这种方式的优点是数据写入一般不会出现热点,缺点是原本连续的数据经过 Hash 后散落在不同的分区上变成了无序的,那么,如果需要扫描一个范围的数据,需要把所有的分区都扫描一遍。
相比而言,Range 分区对数据进行范围分区,连续的数据是存储在一起的,可以按需对相邻的分区进行合并,或者中间切一刀将一个分区一分为二。业界典型的系统像 HBase。这种分区方式的缺点是一、对于追加写处理不友好,因为请求都会打到最后一个分片,使得最后一个分片成为瓶颈。优点是更容易处理热点问题,当一个分区过热的时候,可以切分开,迁移到其他的空闲机器上。
从实际业务使用的角度来说,提供数据强一致性能够大大减小业务的负担。另外 Range 分区能够支持更丰富的访问模式,使用起来更加灵活。基于这些考虑,我们使用 C++ 自研了一套基于 Range 分区的强一致 KV 存储系统 ByteKV,并在其上封装一层表格接口以提供更为丰富的数据模型。
整个系统主要分为 5 个组件:SQLProxy, KVProxy, KVClient, KVMaster 和 PartitionServer。其中,SQLProxy 用于接入 SQL 请求,KVProxy 用于接入 KV 请求,他们都通过 KVClient 来访问集群。KVClient 负责和 KVMaster、PartitionServer 交互,KVClient 从 KVMaster 获取全局时间戳和副本位置等信息,然后访问相应的 PartitionServer 进行数据读写。PartitionServer 负责存储用户数据,KVMaster 负责将整个集群的数据在 PartitionServer 之间调度。
集群中数据会按照 range 切分为很多 Partition,每个 Partition 有多个副本,副本之间通过 Raft 来保证一致性。这些副本分布在所有的 PartitionServer 中,每个 PartitionServer 会存储多个 Partition 的副本,KVMaster 负责把所有副本均匀的放置在各个 PartitionServer 中。各个 PartitionServer 会定期汇报自身存储的副本的信息给 KVMaster,从而 KVMaster 有全局的副本位置信息。Proxy 接到 SDK 请求后,会访问 KVMaster 拿到副本位置信息,然后将请求路由到具体的 PartitionServer,同时 Proxy 会缓存一部分副本位置信息以便于后续快速访问。由于副本会在 PartitionServer 之间调度,故 Proxy 缓存的信息可能是过期的,这时当 PartitionServer 给 Proxy 回应副本位置已经变更后,Proxy 会重新向 KVMaster 请求副本位置信息。
2. 分层结构
如上图所示是 ByteKV 的分层结构。
接口层对用户提供 KV SDK 和 SQL SDK,其中 KV SDK 提供简单的 KV 接口,SQL SDK 提供更加丰富的 SQL 接口,满足不同业务的需求。
事务层提供全局一致的快照隔离级别(Snapshot Isolation),通过全局时间戳和两阶段提交保证事务的 ACID 属性。
弹性伸缩层通过 Partition 的自动分裂合并以及 KVMaster 的多种调度策略,提供了很强的水平扩展能力,能够适应业务不同时期的资源需求。
一致性协议层通过自研的 ByteRaft 组件,保证数据的强一致性,并且提供多种部署方案,适应不同的资源分布情况。
存储引擎层采用业界成熟的解决方案 RocksDB,满足前期快速迭代的需求。并且结合系统未来的演进需要,设计了自研的专用存储引擎 BlockDB。
空间管理层负责管理系统的存储空间,数据既可以存储在物理机的本地磁盘,也可以接入其他的共享存储进行统一管理。
ByteKV 对外提供两层抽象,首先是 namespace,其次是 table,一个 namespace 可以有多个 table。具体到一个 table,支持单条记录的 Put、Delete 和 Get 语义。其中 Put 支持 CAS 语义,仅在满足某种条件时才写入这条记录,如仅在当前 key 不存在的情况下才写入这条记录,或者仅在当前记录为某个版本的情况下才写入这条记录等,同时还支持 TTL 语义。Delete 也类似。
除了这些基本的接口外,还提供多条记录的原子性写入接口 WriteBatch, 分布式一致性快照读 MultiGet, 非事务性写入 MultiWrite 以及扫描一段区间的数据 Scan 等高级接口。WriteBatch 可以提供原子性保证,即所有写入要么全部成功要么全部失败,而 MultiWrite 不提供原子性保证,能写成功多少写成功多少。MultiGet 提供的是分布式一致性快照读的语义:MultiGet 不会读到其他已提交事务的部分修改。Scan 也实现了一致性快照读的语义,并且支持了前缀扫描,逆序扫描等功能。
表格接口在 KV 的基础上提供了更加丰富的单表操作语义。用户可以使用基本的 Insert,Update,Delete,Select SQL 语句来读写数据,可以在 Query 中使用过滤(Where/Having)排序(OrderBy),分组(GroupBy),聚合(Count/Max/Min/Avg)等子句。同时在 SDK 端我们也提供了 ORM 库,方便用户的业务逻辑实现。
以下我们将详细介绍 Raft、存储引擎、分布式事务、分区自动分裂和合并、负载均衡这几个技术点。(其中 Raft、存储引擎 会在本篇详述,其他几个技术点会在下篇详述)
作为一款分布式系统,容灾能力是不可或缺的。冗余副本是最有效的容灾方式,但是它涉及到多个副本间的一致性问题。ByteKV 采用 Raft[1]作为底层复制算法来维护多个副本间的一致性。由于 ByteKV 采用 Range 分片,每个分片对应一个 Raft 复制组,一个集群中会存在非常多的 Raft Group。组织、协调好 Raft Group 组之间的资源利用关系,对实现一个高性能的存储系统至关重要;同时在正确实现 Raft 算法基础上,灵活地为上层提供技术支持,能够有效降低设计难度。因此我们在参考了业界优秀实现的基础上,开发了一款 C++ 的 Multi-Raft 算法库 ByteRaft。
日志复制是 Raft 算法的最基本能力,ByteKV 将所有用户写入操作编码成 RedoLog,并通过 Raft Leader 同步给所有副本;每个副本通过回放具有相同序列的 RedoLog,保证了一致性。有时服务 ByteKV 的机器可能因为硬件故障、掉电等原因发生宕机,只要集群中仍然有多数副本存活,Raft 算法就能在短时间内自动发起选举,选出新的 Leader 进行服务。最重要的是,动态成员变更也被 Raft 算法所支持,它为 ByteKV 的副本调度提供了基础支持。ByteKV 的 KVMaster 会对集群中不同机器的资源利用率进行统计汇总,并通过加减副本的方式,实现了数据的迁移和负载均衡;此外,KVMaster 还定期检查机器状态,将长时间宕机的副本,从原有的复制组中摘除。
ByteRaft 在原有 Raft 算法的基础上,做了很多的工程优化。如何有效整合不同 Raft Group 之间的资源利用,是实现有效的 Multi-Raft 算法的关键。ByteRaft 在各种 IO 操作路径上做了请求合并,将小粒度的 IO 请求合并为大块的请求,使其开销与单 Raft Group 无异;同时多个 Raft Group 可以横向扩展,以充分利用 CPU 的计算和 IO 带宽资源。ByteRaft 网络采用 Pipeline 模式,只要网络通畅,就按照最大的能力进行日志复制;同时 ByteRaft 内置了乱序队列,以解决网络、RPC 框架不保证数据包顺序的问题。ByteRaft 会将即将用到的日志都保留在内存中,这个特性能够减少非常多不必要的 IO 开销,同时降低同步延迟。ByteRaft 不单单作为一个共识算法库,还提供了一整套的解决方案,方便各类场景快速接入,因此除了 ByteKV 使用外,还被字节内部的多个存储系统使用。
除了上述功能外,ByteRaft 还为一些其他企业场景提供了技术支持。
数据同步是存储系统不可或缺的能力。ByteKV 提供了一款事务粒度的数据订阅方案。这种方案保证数据订阅按事务的提交顺序产生,但不可避免的导致扩展性受限。在字节内部,部分场景的数据同步并不需要这么强的日志顺序保证,为此 ByteRaft 提供了 Learner 支持,我们在 Learner 的基础上设计了一款松散的按 Key 有序复制的同步组件。
同时,由于 Learner 不参与日志提交的特性,允许一个新的成员作为 Learner 加入 Raft Group,等到日志差距不大时再提升为正常的跟随者。这个过程可以使得 KVMaster 的调度过程更为平滑,不会降低集群可用性。
在字节内部,ByteKV 的主要部署场景为三中心五副本,这样能够保证在单机房故障时集群仍然能够提供服务,但是这种方式对机器数量要求比较大,另外有些业务场景只能提供两机房部署。因此需要一种不降低集群可用性的方案来降低成本。Witness 作为一个只投票不保存数据的成员,它对机器的资源需求较小,因此 ByteRaft 提供了 Witness 功能。
有了 Witness,就可以将传统的五副本部署场景中的一个副本替换为 Witness,在没有降低可用性的同时,节省出了部分机器资源。另外一些只有两机房的场景中,也可以通过租用少量的第三方云服务,部署上 Witness 来提供和三中心五副本对等的容灾能力。更极端的例子场景,比如业务有主备机房的场景下,可以通过增加 Witness 改变多数派在主备机房的分布情况,如果主备机房隔离,少数派的机房可以移除 Witness 降低 quorum 数目从而恢复服务。
和目前大多数存储系统一样,我们也采用 RocksDB 作为单机存储引擎。RocksDB 作为一个通用的存储引擎,提供了不错的性能和稳定性。RocksDB 除了提供基础的读写接口以外,还提供了丰富的选项和功能,以满足各种各样的业务场景。然而在实际生产实践中,要把 RocksDB 用好也不是一件简单的事情,所以这里我们给大家分享一些经验。
Table Properties 是我们用得比较多的一个功能。RocksDB 本身提供一些内置的 SST 统计信息,并且支持用户自定义的 Table Properties Collector,用于在 Flush/Compaction 过程中收集统计信息。具体来说,我们利用 Table Properties 解决了以下几个问题:
除了上面提到的几个用法以外,这里我们再给大家分享 RocksDB 使用过程中可能遇到的一些坑和解决办法:
由于篇幅有限,上面只是提了几个可能大家都会遇到的问题和解决办法。这些与其说是使用技巧,还不如说是“无奈之举”。很多问题是因为 RocksDB 是这么实现的,所以我们只能这么用,即使给 RocksDB 做优化往往也只能是一些局部调整,毕竟 RocksDB 是一个通用的存储引擎,而不是给我们系统专用的。因此,考虑到以后整个系统的演进的需要,我们设计了一个专用的存储引擎 BlockDB。
BlockDB 需要解决的一个核心需求是数据分片。我们每个存储节点会存储几千上万个数据分片,目前这些单节点的所有分片都是存储在一个 RocksDB 实例上的。这样的存储方式存在以下缺点:
虽然 RocksDB 的 Column Family 也能够提供一部分的数据切分能力,但是面对成千上万的数据分片也显得力不从心。而且我们的数据分片还需要支持一些特殊的操作,比如分片之间的分裂合并等。因此,BlockDB 首先会支持数据分片,并且在数据分片之上增加资源控制和自适应 compaction 等功能。
除了数据分片以外,我们还希望减少事务的开销。目前事务数据的存储方式相当于在 RocksDB 的多版本之上再增加了一层多版本。RocksDB 内部通过 sequence 来区分不同版本的数据,然后在 compaction 的时候根据 snapshot sequence 来清除不可见的垃圾数据。我们的事务在 RocksDB 之上通过 timestamp 来区分不同版本的用户数据,然后通过 GC 来回收对用户不可见的垃圾数据。这两者的逻辑是非常相似的,目前的存储方式显然存在一定的冗余。因此,我们会把一部分事务的逻辑下推到 BlockDB 中,一方面可以减少冗余,另一方面也方便在引擎层做进一步的优化。采用多版本并发控制的存储系统有一个共同的痛点,就是频繁的更新操作会导致用户数据的版本数很多,范围查找的时候需要把每一条用户数据的所有版本都扫一遍,对读性能带来很大的影响。实际上,大部分的读请求只会读最新的若干个版本的数据,如果我们在存储层把新旧版本分离开来,就能够大大提升这些读请求的性能。所以我们在 BlockDB 中也针对这个问题做了设计。
除了功能需求以外,BlockDB 还希望进一步发挥高性能 SSD(如 NVMe)随机 IO 的特性,降低成本。RocksDB 的数据是以文件单位进行存储的,所以 compaction 的最小单位也是文件。如果一个文件跟下一层完全没有重叠,compaction 可以直接把这个文件 move 到下一层,不会产生额外的 IO 开销。可以想象,如果一个文件越小,那么这个文件跟下一层重叠的概率也越小,能够直接复用这个文件的概率就越大。但是在实际使用中,我们并不能把文件设置得特别小,因为文件太多对文件系统并不友好。基于这一想法,我们在 BlockDB 中把数据切分成 Block 进行存储,而 Block 的粒度比文件小得多,比如 128KB。这里的 Block 可以类比为 SST 文件里的 Block,只是我们把 SST 文件的 Block 切分开来,使得这些 Block 能够单独被复用。但是以 Block 为单位进行存储对范围扫描可能不太友好,因为同一个范围的数据可能会分散在磁盘的各个地方,扫描的时候需要大量的随机读。不过在实际测试中,只要控制 Block 的粒度不要太小,配合上异步 IO 的优化,随机读依然能够充分发挥磁盘的性能。
另外,为了进一步发挥磁盘性能,减少文件系统的开销,BlockDB 还设计了一个 Block System 用于 Block 的存储。Block System 类似于一个轻量级的文件系统,但是是以 Block 为单位进行数据存储的。Block System 既可以基于现有的文件系统来实现,也可以直接基于裸盘来实现,这一设计为将来接入 SPDK 和进一步优化 IO 路径提供了良好的基础。
前面在介绍接口部分时,提到了 ByteKV 原子性的 WriteBatch 和满足分布式一致性快照读的 MultiGet。WriteBatch 意味着 Batch 内的所有修改要么都成功,要么都失败,不会出现部分成功部分失败的情况。MultiGet 意味着不会读取到其他已提交事务的部分数据。
ByteKV 大致采用了以下几种技术来实现分布式事务:
毫无疑问,给所有的事件定序,能让分布式系统中的很多问题都得以简化。我们也总是见到各种系统在各种各样的物理时钟、逻辑时钟、混合逻辑时钟中取舍。ByteKV 从性能、稳定性和实现难度的角度综合考虑,在 KVMaster 服务中实现了一个提供全局递增时间戳分配的接口,供集群所有的读写模块使用,该接口保证吐出的时间戳是全局唯一且递增的。
之所以采用这样的架构,是因为我们觉得:
在具体实现上,为了保证时钟的稳定、高效和易用,我们也做了一些工程上的努力和优化:
几乎所有的现代数据库系统都会采用多版本机制来作为事务并发控制机制的一部分,ByteKV 也不例外。多版本的好处是读写互不阻塞。对一行的每次写入都会产生一个新的版本,而读取通常是读一个已经存在的版本。逻辑上的数据组织如下:
相同的 Key 的多个版本会连续存储在一起,方便具体版本的定位,同时版本降序排列以减少查询的开销。
为了保证编码后的数据能够按我们期望的方式排序,对 RocksDB Key 我们采用了内存可比较编码[2],这里之所以没有自定义 RocksDB 的 compare 函数,是因为:
为了避免同一个 Key 的多个版本持续堆积而导致空间无限膨胀,ByteKV 有一个后台任务定期会对旧版本、已标记删除的数据进行清理。在上篇中,存储引擎章节做了一些介绍。
ByteKV 使用两阶段提交来实现分布式事务,其大致思想是整个过程分为两个阶段:第一个阶段叫做 Prepare 阶段,这个阶段里协调者负责给参与者发送 Prepare 请求,参与者响应请求并分配资源、进行预提交(预提交数据我们叫做 Write Intent);第一个阶段中的所有参与者都执行成功后,协调者开始第二个阶段即 Commit 阶段,这个阶段协调者提交事务,并给所有参与者发送提交命令,参与者响应请求后把 Write Intent 转换为真实数据。在 ByteKV 里,协调者由 KVClient 担任,参与者是所有 PartitionServer。接下来我们从原子性和隔离性角度来看看 ByteKV 分布式事务实现的一些细节。
首先是如何保证事务原子性对外可见?这个问题本质上是需要有持久化的事务状态,并且事务状态可以被原子地修改。业界有很多种解法,ByteKV 采用的方法是把事务的状态当作普通数据,单独保存在一个内部表中。我们称这张表为事务状态表,和其他业务数据一样,它也分布式地存储在多台机器上。事务状态表包括如下信息:
在事务状态表的辅助下,第二阶段中协调者只需要简单地修改事务状态就能完成事务提交、回滚操作。一旦事务状态修改完成,即可响应客户端成功, 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、磁盘、内存都可能不同。我们在设计负载均衡策略时采取了循序渐进的办法,首先只考虑单一维度同构机型的场景,然后扩展到多个维度异构机型。下面介绍一下策略的演进过程。
以磁盘空间单一维度为例,并假设所有节点的磁盘容量完全相同。每个节点的磁盘空间使用量等于这个节点上所有副本的数据量之和。将所有副本一一分配并放置在某一个节点上就形成了一个副本分配方案。一定有一个方案,各节点的数据量的方差值最低,这种状态我们称之为“绝对均衡”。随着数据的持续写入,节点的数据量也会持续发生变化,如果要让集群始终保持“绝对均衡”状态,就需要不断的进行调度,带来大量的数据迁移开销。不仅如此,某个维度的绝对均衡会使得其它维度的绝对均衡无法实现。从成本和可行性的角度,我们定义了一种更弱的均衡状态,称之为“足够均衡”,它放松了均衡的标准,一方面降低了调度的敏感度,少量的数据量变化不会引起频繁调度,另一方面也让多个维度同时达到这种弱均衡状态成为可能。为了直观表达“足够均衡”的定义,我们画这样一个示意图进行说明:
以前面的单维度调度为基础,多维度调度的目标是使集群在多个维度上同时或尽量多地达到足够均衡的状态。
我们先想象一下,每个维度都有前面提到的示意图表示它的均衡状态,N 个维度就存在 N 个图。当一个副本发生迁移的时候,会同时改变所有维度的均衡状态,也就是说所有的示意图都会发生改变。如果所有维度都变得更加均衡(均衡区的节点数变多了),或者一部分维度更均衡而另一部分维度不变(均衡区的节点数不变),那么这个迁移是一个好的调度;反正,如果所有维度都变得更加不均衡(均衡区的节点数变少了),或者一部分维度更不均衡而另一部分维度不变,那么这个迁移是一个不好的调度。还有第三种情况,一部分维度更均衡同时也有一部分维度更不均衡了,这是一个中性的调度,往往这种中性的调度是不可避免的,例如集群中只有 A、B 两个节点,A 的流量更高而 B 的数据量更高,由 A 向 B 迁移副本会使流量更均衡而数据量更不均衡,由 B 向 A 迁移副本则相反。
为了判断这种中性的调度能否被允许,我们引入了优先级的概念,为每个维度赋予一个唯一的优先级,牺牲低优维度的均衡度换来高优维度更加均衡是可被接受的,牺牲高优维度的均衡度换来低优维度更加均衡则不可被接受。
仍然考虑前面的例子,因为流量过高会影响读写响应时间进而影响服务质量,我们认为流量的优先级高于数据量优先级,因此由 A 向 B 迁移可被接受。但是也存在一个例外,假设 B 节点的剩余磁盘空间已经接近 0,并且连集群中最小的副本都无法容纳时,即使流量的优先级更好,也不应该允许向 B 迁移任何副本了。为了直观表达这种资源饱和状态,我们在示意图上增加一条硬限线:
配合这个示意图,多维度的负载均衡策略如下:
将多个维度按照优先级排序,从高优维度到低优维度依次执行上文描述的单维度调度策略,仅对流程做少量修改:
对于同构机型,一个单位的负载在每个节点上都会使用同样比例的资源,我们可以仅根据负载值进行调度,而不必这些负载使用了多少机器资源,但在异构机型上这是不成立的。举个例子,同样是从磁盘上读取 1MB 的数据,在高性能服务器上可能只占用 1%的 IO 带宽和 1%的 CPU cycle,而在虚拟机上可能会占用 5%的 IO 带宽和 3%的 CPU cycle。在不同性能的节点上,同样的负载将产生不同的资源利用率。
要将前面的调度策略应用到异构机型的场景中,首先要将按负载值进行调度修改为按资源利用率进行调度。对于数据量来说,要改为磁盘空间利用率;对于流量来说,要改为 CPU 利用率、IO 利用率等等。为了简化策略,我们将内存、磁盘 IO、网络 IO 等使用情况全部纳入到 CPU 利用率中。解释一下为什么这么做:
异构调度要解决的第二个问题是,资源利用率和负载值之间的转换关系。举个例子,A、B 两个节点的 CPU 利用率分别是 50%和 30%,节点上每个副本的读写请求也是已知的,如何从 A 节点选择最佳的副本迁移到 B 节点,使 A、B 的 CPU 利用率差距最小,要求我们必须计算出每个副本在 A、B 节点上分别会产生多少 CPU 利用率。为了做到这一点,我们尽可能多的收集了每个副本的读写请求信息,例如:
根据这些信息,将每个读写请求转换成 N 个标准流量。例如,一个 1KB 以内的请求是一个标准流量,一个 1~2KB 的请求是 2 个标准流量;命中 cache 的请求是一个标准流量,未命中 cache 的请求是 2 个标准流量。知道节点上总的标准流量值,就能根据 CPU 利用率算出这个节点上一个标准流量对应的 CPU 利用率,进而能够算出每个副本在每个节点上对应的 CPU 利用率了。
综上,异构机型调度策略只需要在多维度调度策略的基础上做出如下修改:
KVMaster 中,有一个定时任务执行上述的负载均衡策略,叫做“负载均衡调度器”,这里不再赘述;同时,还有另一个定时任务,用来执行另一类调度,叫做“副本放置调度器”,除了副本安全级别(datacenter/rack/server)、节点异常检测等基本策略之外,它还实现了下面几种调度策略:
前面提到,KV 数据模型过于简单,很难满足一些复杂业务场景的需求。比如:
我们需要更加丰富的数据模型来满足这些场景的需求。在 KV 层之上,我们构建了表格层 ByteSQL,由前面提到的 SQLProxy 实现。ByteSQL 支持通过结构化查询语言(SQL)来写入和读取,并基于 ByteKV 的批量写入(WriteBatch)和快照读接口实现了支持读写混合操作的交互式事务。
在表格存储模型中,数据按照数据库(database), 表(table)两个逻辑层级来组织和存放。同一个物理集群中可以创建多个数据库,而每个数据库内也可以创建多个表。表的 Schema 定义中包含以下元素:
表中的每一行都按照索引被编码成多个 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)的读写事务,其基本实现思路如下:
由上述过程可知,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 变更方案一般需要阻塞整表的读写操作,这是线上应用所无法接受的。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 变更过程处理不当,会造成表中数据的不一致。以创建二级索引为例,考虑如下的执行流程:
第 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 实例为不可用状态,不再处理读写请求。
在跨机房部署的场景里,总有部分请求需要跨机房获取事务时间戳,这会增加响应延迟;同时跨机房的网络环境不及机房内部稳定,跨机房网络的稳定性直接影响到集群的稳定性。实际上,部分业务场景并不需要强一致保证。在这些场景中,我们考虑引入混合逻辑时钟 HLC[4]来替代原有的全局授时服务,将 ByteKV 改造成支持因果一致性的系统。同时,我们可以将写入的时间戳作为同步口令返回给客户端,客户端在后续的请求中携带上同步口令,以传递业务上存在因果关系而存储系统无法识别的事件之间的 happen-before 关系,即会话一致性。
此外,还有部分业务对延迟极其敏感,又有多数据中心访问的需求;而 ByteKV 多机房部署场景下无法避免跨机房延迟。如果这部分业务只需要机房之间保持最终一致即可,我们可以进行机房间数据同步,实现类最终一致性的效果。
随着 CloudNative 的进一步发展,以无可匹敌之势深刻影响着现有的开发部署模型。ByteKV 也将进一步探索与 CloudNative 的深入结合。探索基于 Kubernetes 的 auto deployment, auto scaling, auto healing。进一步提高资源的利用率,降低运维的成本,增强服务的易用性。提供一个更方便于 CloudNative 用户使用的 ByteKV。
字节跳动基础架构团队是支撑字节跳动旗下包括抖音、今日头条、西瓜视频、火山小视频在内的多款亿级规模用户产品平稳运行的重要团队,为字节跳动及旗下业务的快速稳定发展提供了保证和推动力。
公司内,基础架构团队主要负责字节跳动私有云建设,管理数以万计服务器规模的集群,负责数万台计算/存储混合部署和在线/离线混合部署,支持若干 EB 海量数据的稳定存储。
文化上,团队积极拥抱开源和创新的软硬件架构。我们长期招聘基础架构方向的同学,具体可参见:job.bytedance.com ( 点击文末阅读原文 ),感兴趣可以联系邮箱:
guoxinyu.0372@bytedance.com