为了便于检测分片各个 Replica 间的数据差异，我们在 WAL 之上又构建了一层 ReplicaLog（索引），每个 Replica 都对应一个由自己负责的 ReplicaLog，并会在其他 Replica 上创建该 ReplicaLog 的副本，不同 Replica 接收的写请求将写到对应的 ReplicaLog 内，并分配唯一严格递增的 LogID，我们称为 Seqno。
每个 Replica 的后台 Anti-Entropy 任务将定期检查自身与其他 Replica 的 ReplicaLog 的进度，以确定自身是否已经拥有全部数据。流程如下：
- 获取自身 ReplicaLog 进度向量[Seqno1, Seqno2..., SeqnoN]；
- 与其他 Replica 通信，获取其他 Replica 的进度向量；
- 比对自身与其他 Replica 进度向量，是否有 ReplicaLog 落后于其他 Replica，如果是则进入第 4 步，否则进入第 5 步；
- 向其他 Replica 发起数据同步请求，从其他 Replica 拉取缺少的 ReplicaLog 数据，并提交到引擎层
- 若已就某 ReplicaLog 在 SeqnoX 之前已达成一致，回收 SeqnoX 之前的 ReplicaLog 数据。
另外，正常情况下副本间数据能做到秒级达成一致，因此 ReplicaLog 通常只需要构建在内存中，消耗极少的内存，即可达到数据一致的目的。在极端情况下（如网络分区），ReplicaLog 将被 dump 到持久化存储以避免 ReplicaLog 占用过多内存。
与 DynamoDB、Cassandra 等通过扫描引擎层构建 merkle tree 来完成一致性检测相比，Abase 通过额外消耗少量内存的方式，能更高效的完成数据一致性检测和修复。
冲突解决
多点写入带来可用性提升的同时，也带来一个问题，相同数据在不同 Replica 上的写入可能产生冲突，检测并解决冲突是多写系统必须要处理的问题。
为了解决冲突，我们将所有写入数据版本化，为每次写入的数据分配一个唯一可比较的版本号，形成一个不可变的数据版本。
Abase 基于 Hybrid Logical Clock 算法生成全局唯一时间戳，称为 HLC timestamp，并使用 HLC timestamp 作为数据的版本号，使得不同版本与时间相关联，且可比较。
通过业务调研，我们发现在发生数据冲突时，大部分业务希望保留最新写入的数据，部分业务自身也无法判断哪个版本数据更有意义（复杂的上下游关系），反而保留最新版本数据更简洁也更有意义，因此 Abase 决定采用 Last Write Wins 策略来解决写入冲突。
在引擎层面，最初我们采用 RocksDB 直接存储多版本数据，将 key 与版本号一起编码，使得相同 key 的版本连续存储在一起；查询时通过 seek 方式找到最新版本返回；同时通过后台版本合并任务和 compaction filter 将过期版本回收。
在实践中我们发现，上述方式存在几个问题：
- 多版本数据通常能在短时间内（秒级）决定哪个版本最终有效，而直接将所有版本写入 RocksDB，使得即使已经确定了最终有效数据，也无法及时回收无效的版本数据；同时，使用 seek 查询相比 get 消耗更高，性能更低。
- 需要后台任务扫描所有版本数据完成无效数据的回收，消耗额外的 CPU 和 IO 资源。
- 引擎层与多版本耦合，使得引擎层无法方便地做到插件化，根据业务场景做性能优化。
为了解决以上问题，我们把引擎层拆分为数据暂存层与通用引擎层，数据多版本将在暂存层完成冲突解决和合并，只将最终结果写入到底层通用引擎层中。
得益于 Multi-Leader 与 Anti-Entropy 机制，在正常情况下，多版本数据能在很小的时间窗口内决定最终有效数据，因此数据暂存层通常只需要将这个时间窗口内的数据缓存在内存中即可。Abase 基于 SkipList 作为数据暂存层的数据结构（实践中直接使用 RocksDB memtable），周期性地将冲突数据合并后写入底层。
图 7：数据暂存层基本结构示意图
CRDTs
对于幂等类命令如 Set，LWW 能简单有效地解决数据冲突问题，但 Redis String 还需要考虑 Append, Incrby 等非幂等操作的兼容，并且，其它例如 Hash, ZSet 等数据结构则更为复杂。于是，我们引入了 CRDT 支持，实现了 Redis 常见数据结构的 CRDT，包括 String/Hash/Zset/List，并且保持语义完全兼容 Redis。
以 IncrBy 为例，由于 IncrBy 与 Set 会产生冲突，我们发现实际上难以通过 State-based 的 CRDT 来解决问题， 故而我们选用 Operation-based 方案，并结合定期合并 Operation 来满足性能要求。
为了完全兼容 Redis 语义，我们的做法如下：
- 给所有 Operation 分配全球唯一的 HLC timestamp，作为操作的全排序依据；
- 记录写入的 Operation 日志（上文 ReplicaLog）， 每个 key 的最终值等于这些 Operation 日志按照时间戳排序后合并的结果。副本间只要 Operation 日志达成一致，最终状态必然完全一致；
- 为了防止 Operation 日志过多引发的空间和性能问题，我们定期做 Checkpoint，将达成一致的时间戳之前的操作合并成单一结果；
- 为了避免每次查询都需要合并 Operation 日志带来的性能开销，我们结合内存缓存，设计了高效的查询机制，将最终结果缓存在 Cache 中，保证查询过程不需要访问这些 Operation 日志。
图 8：Operation-based CRDT 数据合并示意图
完整 CRDT 的实现算法和工程优化细节我们将在后续 Abase2 介绍文章中详细说明。
全球部署
结合多主模式，系统可以天然支持全球部署，同时，为了避免网状同步造成的带宽浪费，Abase2 在每个地域都可以设置一个 Main Replicator，由它来主导和其它地域间的数据同步。典型的应用场景有多中心数据同步场景以及边缘计算场景。
图 9: 多数据中心部署
图 10: 边缘-中心机房部署
多租户 QoS
为了实现资源池化，避免不同租户间资源独占造成浪费，Abase2 采用大集群多租户的部署模式。同时，为了兼顾不同场景优先级的资源隔离需求，我们在集群内部划分了 3 类资源池，按照不同服务等级进行部署。如图：
图 11：资源池分类示意图
在资源池内的多租户混部要解决两个关键问题：
1、DataNode 的 QoS 保障
DataNode 将请求进行分类量化：
- 用户的请求主要归为 3 类：读、写、Scan，三类请求优先级各不相同；
- 不同数据大小的请求会被分别计算其成本，例如一个读请求的数据量每 4KB 会被归一化成 1 个读取单位。
所有的用户请求都会通过这两个条件计算出 Normalized Request Cost(NRC)。基于 NRC 我们构建了 Quota 限制加 WFQ 双层结构的服务质量控制模块。
图 12：IO 路径上的 QoS 示意图
如上图所示，用户请求在抵达租户服务层之前需要迈过两道关卡：
- Tenant Quota Gate: 如果请求 NRC 已经超过了租户对应的配额，DataNode 将会拒绝该请求，保证 DataNode 不会被打垮；
- 分级 Weight Fair Queue: 根据请求类型分发至各个 WFQ，保证各个租户的请求尽可能地被合理调度。
图 13(1)：正常状态延迟
图 13(2)：突增流量涌入后延迟
如图 13(2)所示，部分租户突增流量涌入后（蓝绿线）并未对其它租户造成较大影响。流量突增的租户请求延迟受到了一定影响，并且出现请求被 Tenant Quota Gate 拦截的现象，而其它租户的请求调度却基本不受影响，延迟基本保持稳定。
2、多租户的负载均衡
负载均衡是所有分布式系统都需要的重要能力之一。资源负载实际上有多个维度， 包括磁盘空间、IO 负载， CPU 负载等。我们希望调度策略能高效满足如下目标：
- 同一个租户的 Replica 尽量分散，确保租户 Quota 可快速扩容；
负载均衡流程的概要主要分为 3 个步骤：
- 根据近期的 QPS 与磁盘空间使用率的最大值，为每个 Core 构建二维负载向量；
- 计算全局最优二维负载向量，即资源池中所有 Core 负载向量在两个维度上的平均值；
- 将高负载 Core 上的 Replica 调度到低负载 Core 上，使高、低负载的 Core 在执行 Replica 调度后，Core 的负载向量与最优负载向量距离变小。
图 14(1): 某集群均衡调度前的负载分布
图 14(2): 某集群均衡调度后的负载分布
上图是线上负载均衡前后各的负载分布散点图，其中：红点是最优负载向量，横纵分别表示 Core 负载向量的第一和第二维度，每个点对应一个 Core。从图可以看出，各个 Core 的负载向量基本以最优负载向量为中心分布。
现状与规划
目前 Abase2 正在逐渐完成对第一代 Abase 系统的数据迁移和升级，使用 Abase2 的原生多租户能力，我们预计可提升 50%的资源使用率。通过对异地多活架构的改造，我们将为 Abase 用户提供更加准确、快速的多地域数据同步功能。同时，我们也在为火山引擎上推出 Abase 标准产品做准备，以满足公有云上用户的大容量、低成本 Redis 场景需求。
未来的 Abase2 会持续向着下面几个方向努力，我们的追求是
技术先进性：在自研多写架构上做更多探索，通过支持 RDMA/io_uring/ZNS SSD/PMEM 等新硬件新技术，让 Abase2 的各项指标更上一个台阶。
易用性：建设标准的云化产品，提供 Serverless 服务，和更自动的冷热沉降，更完善的 Redis 协议兼容，更高鲁棒性的 dump/bulkload 等功能。
极致稳定：在多租户的 QoS 实践和自动化运维等方面不断追求极致。我们的目标是成为像水和电那样，让用户感觉不到存在的基架产品。
结语
随着字节跳动的持续发展，业务数量和场景快速增加，业务对 KV 在线存储系统的可用性与性能的要求也越来越高。在此背景下，团队从初期的拿来主义演进到较为成熟与完善的 Abase 一代架构。秉持着追求极致的字节范儿，团队没有止步于此，我们向着更高可用与更高性能的目标继续演进 Abase2。由于篇幅限制，更多的细节、优化将在后续文章中重点分期讲述。
团队介绍
NoSQL 团队为公司提供稳定可靠的在线存储服务。目前已经覆盖公司几乎所有业务线，支持百亿级请求处理能力。团队依靠公司业务的快速发展浪潮，背靠基础架构的综合技术力量支持，结合最新硬件/技术发展趋势，致力于做用户喜爱的、技术领先的、追求极致的 KV 存储标杆产品。欢迎更多志同道合的同学加入我们：
- 联系邮箱：bytebase@bytedance.com
- 岗位描述：https://job.toutiao.com/s/FUTyXhw
