冠军 0xCC 作品解析

1、概述

华为云 TaurusDB 是华为云自主研发的最新一代云原生分布式数据库，采用计算与存储分离、日志即数据的架构设计，实现数据库性能方面的大幅提升，具备极致可靠、极致性价比、多维拓展、完全可信等诸多特性。

赛题以此为背景，目标是设计一个计算存储分离的 KV 存储引擎。首先回顾下赛题，本次大赛的目的是设计一个 KV 存储引擎，复赛加入了计算存储分离的要求，引入了网络通信。同时，赛题要求程序能保证数据在应用层崩溃情况下的安全性，追求更高的性能。

因此，大赛主要考察点有 5 个：

• 读写吞吐量最大化

• 支持异常退出的缓冲设计

• 高效紧凑的索引结构

• 合理的缓存预读机制

• 高速稳定的 RPC 设计

• 主要考察点集中在文件 IO 和网络 IO 上，需要选手对操作系统底层有较多的了解。

2、测试

为了达到最优的性能目标，首先进行的是性能测试，这里对测评环境下的 SSD，网络进行了详细的测试，结合运行环境的限制，最终确定磁盘采用 direct 方式调用，以 2M 单位写，16M 或 32M 读。

由于网络环境在测评阶段发生过变动，限速环境下丢包率高，使用 16 连接 4K 大小调用，pipeline 的方式请求大块数据，即柱状图最右侧 1212M/s，用多连接打满带宽，后期去除限速后，采用单 tcp 连接 128K 调用，即最高的 1939M/s。

3、具体设计

整体架构设计

确定了硬件的吞吐量，就可以对程序进行整体的设计了。计算节点和存储节点都根据其功能分为 3 层，计算节点前部分的 KV 接口层负责适配调用接口及记录必要的参数，因为计算节点无状态，没有持久化功能，KV 抽象层通过对 RPC client 的包装，抽象出 KV 的存储层，实现接口和代码复用。存储节点除了 RPC 服务层，KV 管理层负责管理到存储层的读写缓冲，文件系统层则负责将抽象的存储调用映射到多个磁盘文件。

可以看出，计算节点和存储节点都有使用读缓冲提升性能，读取时计算节点负责建立索引和预读，而存储节点抽象为一个块存储，写入时存储节点则抽象为一个 RPC 服务端，计算节点远程调用。

存储设计

存储引擎，首要设计存储的结构，这里采用 KV 分离的日志式存储的方式，KV 在顺序上一一对应，可以通过读 key 文件快速建立索引，同时考虑到文件管理迁移的情况，文件以 1G 进行分片。

索引设计

索引是加速读取必不可少的，为了将 6400w 索引到内存中并能提供高性能插入和检索，采用了 hash+array+linked list 结构，同时能应对数据倾斜的情况，通过细粒度锁提升并发度，hash 和 array 的长度也是可调的以适应不同场景。

索引以 key 和 offset 作为一个单元，将 key 文件全部读入内存，插入新 KV 时直接 hash 到对应 slot，append 到后面，当需要查找时，对索引进行排序，key 为第一优先级，offset 为第二优先级，通过二分查找 upper_bound 方式，找到最大的 offset 值，即最新 value 对应 offset，具备处理重复 key 的能力。

RPC 协议设计

而针对网络传输，设计了二进制的 RPC 协议，整体协议由计算端发起，无状态。设计考虑到应对各种网络环境和传输方式，请求和响应具备 batch 能力，最大化利用带宽。同时包头尽量 4bytes 对齐，提升 payload 的拷贝效率。

4、具体功能实现

结构和协议设计完成后，下面就需要实现具体功能了。

日志式存储引擎实现

首先是基于日志的存储部分，该部分抽象为 writer，reader 和 file operator 三部分，writer 负责写入，通过 mmap 使用 page cache 作为缓冲、meta 和 keys 的存储，同时使用精心设计的 lock free ringbuffer 提升高并发写入性能，flusher 和 loader 负责异步刷盘，重叠 CPU/IO 时间，达到最大吞吐量。读缓存使用最简单的 hash，在顺序读时高效实现最优缓存策略。reader 会读写缓冲，保证任何情况下写即可见。

单机 KV 存储引擎实现

基于之前的日志式存储引擎，加上索引模块，记录 key 和对应存储偏移，即可完成单机版的 KV 存储引擎。系统初始化时，restorer 负责多线程读取 keys，并以(key,offset)进行排序，即前文介绍的索引初始化及查找算法。索引基于 linked list+array 的结构，固定大小分配自内存池，无碎片，统一生命周期管理。同时基于底层存储引擎特性，保证 KV 写入即可见的基本要求。

RPC 实现

对于 client 有两套调用流程，分别用于适配延迟敏感的写入操作和追求极致吞吐量的读取操作。首先，每个 KV agent 初始化一个 client，client 预先建立多条 tcp 连接。对于时延敏感的写入，采用单路阻塞 IO 模型，确认持久化后返回；对于追求吞吐量的读取，采用 pipeline 请求+多路复用 IO 模型，pipeline 并行度可根据网络状况进行调整。

考虑到多路复用 IO 模型带来的时延问题，server 线程采用简单的阻塞 IO 模型，单线程单 socket。keys 数据传输 zerocopy，提升性能。协议解析使用会话协议缓冲，采用生产消费模型，非常便于扩展协议。

计算存储分离的 KV 存储引擎实现

上图展示的是初始化和写入的流程，首先计算节点 restorer 通过 RPC 拉取已有的 keys 数据，完成索引建立，保证能感知到已写入的 KV。然后写入时，计算节点先通过 RPC 协议包装请求，等待写入完成后，将 key 和 data offset 记录到索引中，最后返回 set。这样保证数据持久化后才返回请求，同时保证计算节点和存储节点实时一致。

由于计算节点的实时性，读取并不需要做额外同步，直接通过索引获取当前 key 的 offset，然后调用计算节点的 reader，这时存储节点抽象为一个块存储，reader 通过 RPC 完成 cache miss 时的读取功能，这里关闭了计算节点的 loader 跨块预读的功能，降低网络带宽占用，降低 get KV 的时延。

5、细节优化

无锁环形缓冲

由于写入是顺序进行的，低写入延迟是提升性能的决定性因素。这里将 meta 存储在 page cache(mmap)中，对抗应用层崩溃，同时提升写入速度。meta 数据按操作线程进行 CPU cache line 对齐，避免写入造成 cacheinvalidate。通过 filled 数组和多个 bound 变量 CAS 操作保证 write 和 flush 操作安全，所以在写缓冲充足时，所有写入操作都是无锁无等待的。本地测试多线程写同一 writer，flush 到内存，可打满内存带宽到 40GBps。

上图为 cacheline 对齐的 meta 结构。

上图为 bound 的逻辑关系示意及具体实现结构。

上图为对 filled 数组和 bound 移动的核心代码。

SpinLock & SpinRWLock

锁操作是在多线程编程中必不可少的，但 mutex 是一个非常重要的操作。这里针对多线程快速同步设计了两套基于原子操作和自旋的锁。实现基于原生 C++11，且占用非常小的空间，RW lock 仅占 2 个 ptr 大小。

RWlock 代码比较多就不贴这，实现参考 java 的 ReentrantReadWriteLock 非公平实现方法。非公平锁吞吐量高，故这里选择非公平方式。

多存储单元

虽然针对多线程传统设计了诸多优化，多存储单元的方式还是一种非常简单直接的避免冲突方式。根据线程 id 路由到不同存储单元上写入，能直接消除线程冲突。但在读的时候，不会总是落在同一单元中，这里通过 prefer 项，利用读写聚集性，减少多单元检索的开销。

预读

预读是重叠 CPU 和 IO 的一种方案。这里，预读是由独立线程 loader 完成的，初赛阶段由于不存在网络延迟，预读能够提升整体吞吐量，提升若干秒的性能。而复赛阶段由于存在网络传输：

∵网络吞吐量 < 磁盘吞吐量 and 网络延迟 >> 磁盘延迟

∴关闭跨块预读的收益 > 预读收益

复赛阶段预读仅包含 values 整块预读，块大小设定为 32MB，由于 reader 的 cache 极大（使用了 2GB），也起到了预读作用。

内存管理 & 对齐 & Misc

这里总结下内存相关优化点，不展开：内存管理

• VM 使用 RAII 思想管理

• 预分配一大块 mmap

• offset 原子加分配内存

• 生命周期统一管理

• 内存分配

• 固定大小 &对齐的内存分配

• array+linked list 方式实现动态数组

• 对齐

• DIO 操作内存和缓存的 VM 都是 4KB 对齐，单独管理+populate&lock

• 代码中设计了 AVX2 的 memcpy(由于 gcc 版本没开)

• Misc

• 索引重载符号使用 std::sort,std::upper_bound

• keys 传输使用 mmap 实现 zero copy

• RPC 请求栈上内存构建，减少系统调用，利用 CPUcache

• 数据分片参数使用类模板，编译阶段优化除法为位运算

6、最优成绩

复赛：

• 最优成绩性能

• 484.889s(写)+133.776s(读)+134.711s(索引+随机读)+0.012s(Misc)=753.388s

• 由于网络存在波动且传输数据较多，很难遇到各阶段都达到最优

• 写阶段最优：484.889s

• 读取并恢复索引：~0.6s

• 读阶段最优：132.263s-(~0.6s(恢复索引))=131.663s

初赛(保留 kill 恢复能力，未达到最大吞吐量)：

• 最优成绩性能

• 130.782s(写)+73.802s(顺序读)+72.827s(随机读)+0.008(Misc)=277.419s

7、总结

• 现实问题受环境影响，不存在永恒的最优方案，需要测试实验作为先导，知己知彼才能百战不殆。

• 良好的抽象有利于最大程度复用已有代码，同时具备良好的可维护性和扩展性。

• 追求极致性能时，在细节上的优化是必不可少的。

最后感谢华为云提供这次比赛机会，通过这次比赛学习到了很多知识，使我受益匪浅。

本文转载自 HW 云数据库。