Content Entry

字节跳动自研强一致在线KV与表格存储实践

文章作者:字节跳动基础架构团队

内容来源:字节跳动技术团队

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

01 背景

互联网产品中存在很多种类的数据,不同种类的数据对于存储系统的一致性,可用性,扩展性的要求是不同的。比如,金融、账号相关的数据对一致性要求比较高,社交类数据例如点赞对可用性要求比较高。还有一些大规模元数据存储场景,例如对象存储的索引层数据,对一致性,扩展性和可用性要求都比较高,这就需要底层存储系统在能够保证数据强一致的同时,也具有良好的扩展性。在数据模型上,有些数据比如关系,KV 模型足够用;有些数据比如钱包、账号可能又需要更丰富的数据模型,比如表格。

分布式存储系统对数据分区一般有两种方式:Hash 分区和 Range 分区。Hash 分区对每条数据算一个哈希值,映射到一个逻辑分区上,然后通过另外一层映射将逻辑分区映射到具体的机器上,很多数据库中间件、缓存中间件都是这样做的。这种方式的优点是数据写入一般不会出现热点,缺点是原本连续的数据经过 Hash 后散落在不同的分区上变成了无序的,那么,如果需要扫描一个范围的数据,需要把所有的分区都扫描一遍。

相比而言,Range 分区对数据进行范围分区,连续的数据是存储在一起的,可以按需对相邻的分区进行合并,或者中间切一刀将一个分区一分为二。业界典型的系统像 HBase。这种分区方式的缺点是一、对于追加写处理不友好,因为请求都会打到最后一个分片,使得最后一个分片成为瓶颈。优点是更容易处理热点问题,当一个分区过热的时候,可以切分开,迁移到其他的空闲机器上。

从实际业务使用的角度来说,提供数据强一致性能够大大减小业务的负担。另外 Range 分区能够支持更丰富的访问模式,使用起来更加灵活。基于这些考虑,我们使用 C++ 自研了一套基于 Range 分区的强一致 KV 存储系统 ByteKV,并在其上封装一层表格接口以提供更为丰富的数据模型。

02 架构介绍

1. 系统组件

整个系统主要分为 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。

空间管理层负责管理系统的存储空间,数据既可以存储在物理机的本地磁盘,也可以接入其他的共享存储进行统一管理。

03 对外接口

1. KV 接口

ByteKV 对外提供两层抽象,首先是 namespace,其次是 table,一个 namespace 可以有多个 table。具体到一个 table,支持单条记录的 Put、Delete 和 Get 语义。其中 Put 支持 CAS 语义,仅在满足某种条件时才写入这条记录,如仅在当前 key 不存在的情况下才写入这条记录,或者仅在当前记录为某个版本的情况下才写入这条记录等,同时还支持 TTL 语义。Delete 也类似。

除了这些基本的接口外,还提供多条记录的原子性写入接口 WriteBatch, 分布式一致性快照读 MultiGet, 非事务性写入 MultiWrite 以及扫描一段区间的数据 Scan 等高级接口。WriteBatch 可以提供原子性保证,即所有写入要么全部成功要么全部失败,而 MultiWrite 不提供原子性保证,能写成功多少写成功多少。MultiGet 提供的是分布式一致性快照读的语义:MultiGet 不会读到其他已提交事务的部分修改。Scan 也实现了一致性快照读的语义,并且支持了前缀扫描,逆序扫描等功能。

2. 表格接口

表格接口在 KV 的基础上提供了更加丰富的单表操作语义。用户可以使用基本的 Insert,Update,Delete,Select SQL 语句来读写数据,可以在 Query 中使用过滤(Where/Having)排序(OrderBy),分组(GroupBy),聚合(Count/Max/Min/Avg)等子句。同时在 SDK 端我们也提供了 ORM 库,方便用户的业务逻辑实现。

04 关键技术

以下我们将详细介绍 Raft、存储引擎、分布式事务、分区自动分裂和合并、负载均衡这几个技术点。(其中 Raft、存储引擎 会在本篇详述,其他几个技术点会在下篇详述)

1. 自研 ByteRaft

作为一款分布式系统,容灾能力是不可或缺的。冗余副本是最有效的容灾方式,但是它涉及到多个副本间的一致性问题。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 还为一些其他企业场景提供了技术支持。

① Learner

数据同步是存储系统不可或缺的能力。ByteKV 提供了一款事务粒度的数据订阅方案。这种方案保证数据订阅按事务的提交顺序产生,但不可避免的导致扩展性受限。在字节内部,部分场景的数据同步并不需要这么强的日志顺序保证,为此 ByteRaft 提供了 Learner 支持,我们在 Learner 的基础上设计了一款松散的按 Key 有序复制的同步组件。

同时,由于 Learner 不参与日志提交的特性,允许一个新的成员作为 Learner 加入 Raft Group,等到日志差距不大时再提升为正常的跟随者。这个过程可以使得 KVMaster 的调度过程更为平滑,不会降低集群可用性。

② Witness

在字节内部,ByteKV 的主要部署场景为三中心五副本,这样能够保证在单机房故障时集群仍然能够提供服务,但是这种方式对机器数量要求比较大,另外有些业务场景只能提供两机房部署。因此需要一种不降低集群可用性的方案来降低成本。Witness 作为一个只投票不保存数据的成员,它对机器的资源需求较小,因此 ByteRaft 提供了 Witness 功能。

有了 Witness,就可以将传统的五副本部署场景中的一个副本替换为 Witness,在没有降低可用性的同时,节省出了部分机器资源。另外一些只有两机房的场景中,也可以通过租用少量的第三方云服务,部署上 Witness 来提供和三中心五副本对等的容灾能力。更极端的例子场景,比如业务有主备机房的场景下,可以通过增加 Witness 改变多数派在主备机房的分布情况,如果主备机房隔离,少数派的机房可以移除 Witness 降低 quorum 数目从而恢复服务。

2. 存储引擎

① RocksDB

和目前大多数存储系统一样,我们也采用 RocksDB 作为单机存储引擎。RocksDB 作为一个通用的存储引擎,提供了不错的性能和稳定性。RocksDB 除了提供基础的读写接口以外,还提供了丰富的选项和功能,以满足各种各样的业务场景。然而在实际生产实践中,要把 RocksDB 用好也不是一件简单的事情,所以这里我们给大家分享一些经验。

Table Properties:

Table Properties 是我们用得比较多的一个功能。RocksDB 本身提供一些内置的 SST 统计信息,并且支持用户自定义的 Table Properties Collector,用于在 Flush/Compaction 过程中收集统计信息。具体来说,我们利用 Table Properties 解决了以下几个问题:

  • 我们的系统是采用 Range 切分数据的,当一个 Range 的数据大小超过某个阈值,这个 Range 会被分裂。这里就涉及到分裂点如何选取的问题。一个简单的办法是把这个 Range 的数据扫一遍,根据数据大小找到一个中点作为分裂点,但是这样 IO 开销会比较大。所以我们通过 Table Properties Collector 对数据进行采样,每隔一定的数据条数或者大小记录一个采样点,那么分裂的时候只需要根据这些采样点来估算出一个分裂点即可。
  • 多版本数据进行启发式垃圾回收的过程,也是通过 Table Properties 的采样来实现的。在存储引擎中,一条用户数据可能对应有一条或多条不同版本的数据。我们在 Table Properties Collector 中采集了版本数据的条数和用户数据的条数。在垃圾回收的过程中,如果一个 Range 包含的版本数据的条数和用户数据的条数差不多,我们可以认为大部分用户数据只有一个版本,那么就可以选择跳过这个 Range 的垃圾回收。另外,垃圾回收除了要考虑多版本以外,还需要考虑 TTL 的问题,那么在不扫描数据的情况下如何知道一个 Range 是否包含已经过期的 TTL 数据呢?同样是在 Table Properties Collector 中,我们计算出每条数据的过期时间,然后以百分比的形式记录不同过期时间的数据条数。那么,在垃圾回收的过程中,给定一个时间戳,我们就能够估算出某一个 Range 里面包含了多少已经过期的数据了。
  • 虽然 RocksDB 提供了一些参数能够让我们根据不同的业务场景对 compaction 的策略进行调整,比如 compaction 的优先级等,但是实际上业务类型多种多样,很难通过一套单一的配置能够满足所有的场景。这时候其实我们也可以根据统计信息来对 compaction 进行一定的“干预”。比方说有的数据区间经常有频繁的删除操作,会留下大量的 tombstone。如果这些 tombstone 不能被快速的 compaction 清除掉,会对读性能造成很大,并且相应的空间也不能释放。针对这个问题,我们会在上层根据统计信息(比如垃圾数据比例)及时发现并主动触发 compaction 来及时处理。

遇到的问题和解决办法:

除了上面提到的几个用法以外,这里我们再给大家分享 RocksDB 使用过程中可能遇到的一些坑和解决办法:

  • 你是否遇到过数据越删越多或者已经删除了很多数据但是空间长时间不能释放的问题呢?我们知道 RocksDB 的删除操作其实只是写入了一个 tombstone 标记,而这个标记往往只有被 compact 到最底层才能被丢掉的。所以这里的问题很可能是由于层数过多或者每一层之间的放大系数不合理导致上面的层的 tombstone 不能被推到最底层。这时候大家可以考虑开启 level_compaction_dynamic_level_bytes这个参数来解决。
  • 你是否遇到过 iterator 的抖动导致的长尾问题呢?这个可能是因为 iterator 在释放的时候需要做一些清理工作的原因,尝试开启 avoid_unnecessary_blocking_io 来解决。
  • 你是否遇到过 ingest file 导致的抖动问题?在 ingest file 的过程中,RocksDB 会阻塞写入,所以如果 ingest file 的某些步骤耗时很长就会带来明显的抖动。例如如果 ingest 的 SST 文件跟 memtable 有重叠,则需要先把 memtable flush 下来,而这个过程中都是不能写入的。所以为了避免这个抖动问题,我们会先判断需要 ingest 的文件是否跟 memtable 有重叠,如果有的话会在 ingest 之前先 flush,等 flush 完了再执行 ingest。而这个时候 ingest 之前的 flush 并不会阻塞写,所以也就避免了抖动问题。
  • 你是否遇到过某一层的一个文件跟下一层的一万个文件进行 compaction 的情况呢?RocksDB 在 compaction 生成文件的时候会预先判断这个文件跟下一层有多少重叠,来避免后续会产生过大的 compaction 的问题。然而,这个判断对 range deletion 是不生效的,所以有可能会生成一个范围非常广但是实际数据很少的文件,那么这个文件再跟下一层 compact 的时候就会涉及到非常多的文件,这种 compaction 可能需要持续几个小时,期间所有文件都不能被释放,磁盘很容易就满了。由于我们需要 delete range 的场景很有限,所以目前我们通过 delete files in range + scan + delete 的方式来替换 delete range。虽然这种方式比 delete range 开销更大,但是更加可控。虽然也可以通过 compaction filter 来进一步优化,但是实现比较复杂,我们暂时没有考虑。

由于篇幅有限,上面只是提了几个可能大家都会遇到的问题和解决办法。这些与其说是使用技巧,还不如说是“无奈之举”。很多问题是因为 RocksDB 是这么实现的,所以我们只能这么用,即使给 RocksDB 做优化往往也只能是一些局部调整,毕竟 RocksDB 是一个通用的存储引擎,而不是给我们系统专用的。因此,考虑到以后整个系统的演进的需要,我们设计了一个专用的存储引擎 BlockDB。

② BlockDB

功能需求:

BlockDB 需要解决的一个核心需求是数据分片。我们每个存储节点会存储几千上万个数据分片,目前这些单节点的所有分片都是存储在一个 RocksDB 实例上的。这样的存储方式存在以下缺点:

  • 无法对不同数据分片的资源使用进行隔离,这一点对于多租户的支持尤为重要。
  • 无法针对不同数据分片的访问模式做优化,比如有的分片读多写少,有的分片写多读少,那么我们希望对前者采取对读更加友好的 compaction 策略,而对后者采取对写更加友好的 compaction 策略,但是一个 RocksDB 实例上我们只能选择一种单一的策略。
  • 不同数据分片的操作容易互相影响,一些对数据分片的操作在 RocksDB 中需要加全局锁(比如上面提到的 ingest file),那么数据分片越多锁竞争就会越激烈,容易带来长尾问题。
  • 不同数据分片混合存储会带来一些不必要的写放大,因为我们不同业务的数据分片是按照前缀来区分的,不同数据分片的前缀差别很大,导致写入的数据范围比较离散,compaction 的过程中会有很多范围重叠的数据。

虽然 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 路径提供了良好的基础。

3. 分布式事务

前面在介绍接口部分时,提到了 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 后可以根据参与者列表还原出事务状态。

4. 分区自动分裂和合并

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

分裂过程

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

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

合并过程

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

5. 负载均衡

负载均衡是所有分布式系统都需要的重要能力之一。无法做到负载均衡的系统不仅不能充分利用集群的计算和存储资源,更会因为个别节点因负载过重产生抖动进而影响服务质量。设计一个好的负载均衡策略会面对两个难点,一是需要均衡的资源维度很多,不仅有最基本的磁盘空间,还有 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的副本为候选迁移对象,如果它导致任一下列情况出现,则将它排除,选择下一个副本作为候选对象,直到找到合适的副本为止:
    1. 迁移之后,目标机器在更高优维度上将处于高水位线以上
    2. 迁移之后,目标机器在更低优维度上将处于硬限线以上
  • 如果对于某一目标节点,源节点上无法选出迁移对象,将排在目标节点前一位的节点作为新的目标节点,重复上述过程
  • 如果对于所有目标节点,源节点上仍然无法选出迁移对象,将该源节点从排序列表中剔除,重复上述过程

③ 异构机型调度策略

对于同构机型,一个单位的负载在每个节点上都会使用同样比例的资源,我们可以仅根据负载值进行调度,而不必这些负载使用了多少机器资源,但在异构机型上这是不成立的。举个例子,同样是从磁盘上读取 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 要求的副本进行调度。
  • 热点检测:当某个数据分片的数据量达到一定阈值时会发生分裂,除此之外,当它的读写流量超过平均值的某个倍数后,也会发生分裂。当分裂发生后,其中一个新产生的分片(左边或右边)的所有副本都会迁移至其他节点,避免节点成为访问热点。
  • 碎片检测:当某个数据分片的数据量和读写流量都小于平均值的一定比例时,会与它所相邻的分片进行合并。合并前会将小分片的所有副本迁移至相邻分片所在的节点上。

05 表格层

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

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

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

1. 表格模型

在表格存储模型中,数据按照数据库(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 来标识该值是否为空值。

2. 全局二级索引

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

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

3. 交互式事务

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。

4. 执行流程优化

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;

5. 在线 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 变更过程处理不当,会造成表中数据的不一致。以创建二级索引为例,考虑如下的执行流程:

  1. Schema Change Worker 执行了一个 Create Index 变更任务,包括向 ByteKV 中填充索引记录和写入元数据。
  2. SQLProxy 实例 1 加载了包含新索引的 Schema 元数据。
  3. SQLProxy 实例 2 执行 Insert 请求。由于实例 2 尚未加载索引元数据,Insert 操作不包含新索引记录的写入。
  4. SQLProxy 实例 2 执行 Delete 请求。由于实例 2 尚未加载索引元数据,Delete 操作不包含新索引记录的删除。
  5. 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 实例为不可用状态,不再处理读写请求。

06 未来探讨

1. 更多的一致性级别

在跨机房部署的场景里,总有部分请求需要跨机房获取事务时间戳,这会增加响应延迟;同时跨机房的网络环境不及机房内部稳定,跨机房网络的稳定性直接影响到集群的稳定性。实际上,部分业务场景并不需要强一致保证。在这些场景中,我们考虑引入混合逻辑时钟 HLC[4]来替代原有的全局授时服务,将 ByteKV 改造成支持因果一致性的系统。同时,我们可以将写入的时间戳作为同步口令返回给客户端,客户端在后续的请求中携带上同步口令,以传递业务上存在因果关系而存储系统无法识别的事件之间的 happen-before 关系,即会话一致性。

此外,还有部分业务对延迟极其敏感,又有多数据中心访问的需求;而 ByteKV 多机房部署场景下无法避免跨机房延迟。如果这部分业务只需要机房之间保持最终一致即可,我们可以进行机房间数据同步,实现类最终一致性的效果。

2. 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 google’s 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.

字节跳动基础架构团队:

字节跳动基础架构团队是支撑字节跳动旗下包括抖音、今日头条、西瓜视频、火山小视频在内的多款亿级规模用户产品平稳运行的重要团队,为字节跳动及旗下业务的快速稳定发展提供了保证和推动力。

公司内,基础架构团队主要负责字节跳动私有云建设,管理数以万计服务器规模的集群,负责数万台计算/存储混合部署和在线/离线混合部署,支持若干 EB 海量数据的稳定存储。

文化上,团队积极拥抱开源和创新的软硬件架构。我们长期招聘基础架构方向的同学,具体可参见:job.bytedance.com ( 点击文末阅读原文 ),感兴趣可以联系邮箱:

guoxinyu.0372@bytedance.com

comments loading