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云数据库。

创作场景

冠军 0xCC 作品解析