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.1整体架构设计

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

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

3.2存储设计

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

3.3索引设计

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

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

3.4RPC协议设计

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

4 具体功能实现

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

4.1日志式存储引擎实现

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

4.2单机KV存储引擎实现

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

4.3RPC实现

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

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

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

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

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

5 细节优化

5.1无锁环形缓冲

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

上图为cache line对齐的meta结构。

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

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

5.2 SpinLock & SpinRWLock

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

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

5.3 多存储单元

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

5.4 预读

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

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

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

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

            下图所示为预读预测代码，通过分析跨块时的访问模式，智能地进行正向和反向预读。

    5.5内存管理 & 对齐 & 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请求栈上内存构建，减少系统调用，利用CPU cache

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

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 总结

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

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

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

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

作者：0xCC