tair 性能挑战赛攻略心得 -Zzzzz

关联比赛:  第二届数据库大赛—Tair性能挑战

​赛题分析

赛题要求实现一个基于 persistent memory（AEP）的持久化键值存储系统，并要求从数据正确性和系统读写性能两个方面来考虑系统设计。

正确性

数据正确性包括数据写入的持久性和原子性两个方面。

持久性

系统需要保证在写操作成功返回后数据不会丢失。这部分较为简单，我们使用 memcpy()向 AEP 写入键值对，只需要在写入地址调用 pmem_persist()即可保证数据的持久化。在每次系统启动时可以扫描 AEP 上持久化的键值对建立数据索引，确保数据不会丢失。

原子性

系统需要保证数据的写入要么成功，要么丢弃，不能读到不正确的数据。由于 AEP 内部仅保证 8B 大小的原子更新，若系统在向 AEP 写入键值对的过程中断电，可能存在仅部分数据被写入的情况，因此系统需要在重启时发现并丢弃这部分未写完的数据。

一种保证原子写入的方式是在每个键值对末尾追加一个 tag 表示写入完成。但是，由于 CPU 对指令的乱序执行，若将 tag 和键值对一起写入 AEP 并持久化，可能出现的一种情况是 tag 先于键值对落盘，因此需要在持久化键值对后再发起一次独立的写操作来写入 tag，这样需要调用两次 pmem_persist()。通过实验我们发现这种方法写入 tag 的性能开销较大，因此弃用了该方案，转用 checksum 在重建数据索引时检测数据的正确性。

性能

性能测试分为纯写和读写混合两个阶段，均由 16 个线程并发发起请求，其中读写混合阶段会存在较多热点访问。

为了有效释放 AEP 的性能，我们主要围绕着以下两点设计系统：

针对热点访问，我们尝试了使用 DRAM 做数据缓存，但是我们发现仅 L3 cache 便能缓存大量热点数据，同时 AEP 的读延迟与 DRAM 相比差距也较小，使用 DRAM 缓存键值对并无明显效果，因此最终仅使用 DRAM 缓存了部分数据索引信息。

最后，写操作中含有较多数据更新，同时 value 大小存在变化。由于赛题存在严格的空间限制，如何高效利用存储空间也需要纳入考虑。

系统设计

整体架构

基于上述分析，我们设计了下图所示的系统架构。系统由 AEP 和 DRAM 两部分组成，分别存储键值数据和管理索引等元数据信息。AEP 在程序中被映射为一大块内存空间，我们以 block 为单位分配这部分空间，并在 DRAM 中以 Free List 结构管理键值对更新后释放的空间。数据索引为 Hash Table 结构，采用数组+链表结合的设计，该 hash table 可以无锁进行并发读访问，同时写操作以粒度较小的 hash 分片(slot)加锁，每个分片还包含 bloom filter 和 hash cache 来加速索引数据的写入和查询。

所有在运行时分配的 DRAM 和 AEP 空间均按写入线程分组，每个写线程独占一组空间，确保没有资源竞争。

下面详细介绍我们对存储和索引部分的设计。

存储设计

如前文所述，为了方便对 AEP 空间的管理，我们将 AEP 空间切分为若干 32 字节的 block，并以 block 作为空间分配的最小单位。从程序的角度看，AEP 空间以 mmap 的方式映射为一大块内存空间，我们将该空间均分成 16 组，每个写入线程独占一组空间，以消除线程同步开销。每组空间的管理分为下图所示两部分：

写入 AEP 的数据记录由键值对本身以及相关元数据组成，元数据包括：

数据写入流程的介绍见后文读写流程部分。

索引设计

系统的索引部分是一个 hash table，其中每个 hash entry 维护 key 和 value 在 AEP 中的地址信息(Meta)，包括：

Hash table 采用数组加链表的设计。每个 Hash bucket 是一个 hash entry 的数组，数组大小可调整，这样能更高效地利用 CPU cache。我们在系统启动时直接分配出 8GB 内存用于存储 Hash table，其中 4GB 根据 bucket 大小存储连续的 2^n 个 bucket，键值对根据 key 的 hash 值低 n 位决定其所在的 bucket。剩余 4GB 作为 spare 空间，当某 bucket 被写满后，从 spare 空间中分配一个新的 bucket，与前面的 bucket 组成链表。这种按需分配空间的链表结构能有效避免 hash 不均匀引起的空间浪费。

类似于对 AEP 空间的管理，我们将 spare 空间同样均分成 16 份由写线程独占，消除空间分配的线程同步开销。

该 Hash table 可以保证读操作的无锁访问，但是写操作仍是互斥的，因此需要以较小的粒度加锁来减少对锁的争用。然而，如果为每个 bucket 都分配一个独立的锁则内存开销太高。因此，我们将连续的若干 bucket 组成一个分片（slot），并以 slot 为粒度加锁。Slot 包含以下部分：

索引重建

在每次系统重启后，我们用多个线程遍历 AEP 上的键值对来重建索引。由于在 AEP 上记录有每个键值对实际分配的 block 数量，因此很容易找到下一个键值对的起始偏移量。对每个键值对，首先重新计算 checksum，与 AEP 上记录的 checksum 做对比判断其有效性，然后将有效键值对的索引写入 Hash table。

由于我们在写操作中会重复利用被释放的空间，因此在遍历时可能存在较新版本的键值对先于旧版本键值对出现，我们在遇到重复键值对时通过对比数据记录与 hash entry 中的 version 信息来分辨其版本新旧，决定是否覆盖已写入的索引，并将旧版本键值对占据的空间记录到 free list 中。

读写流程

下面介绍数据读写流程。

细节优化

以上是对系统主要部分的介绍，除此以外我们还做了一些细节上的优化，包括内存页预读，缓存预取以及快速内存拷贝。

• 内存页预读。由于 PMEM 是以内存映射的方式访问的，在系统初始化后写操作会产生较多的 page fault，存在一定性能开销。因此，我们在系统初次启动的初始化阶段提前访问整个 PMEM 空间，避免运行时产生 page fault。

for (int i = 0; i < THREAD_NUM; i++) {

ths_init.emplace_back(= {

memset_movnt_sse2_clflushopt(aep_value_log_ + (uint64_t)i * PMEM_SIZE / THREAD_NUM,

0, PMEM_SIZE / THREAD_NUM);

}

• 缓存预取。我们令 hash bucket 大小与 cache line 大小对齐，在搜索 hash table 时使用_mm_prefetch()命令提前将下一块 bucket 预取到 cache 中，以加速查询速度。

mm_prefetch(&hash_cache[slot], _MM_HINT_T0);

...

_mm_prefetch(bucket_base, _MM_HINT_T0);

_mm_prefetch(bucket_base + 64, _MM_HINT_T0);

...

• 快速内存操作。系统中大量数据与元数据的写入和比较都是以 memcpy/memcmp 进行的，为了优化执行速度，我们针对不同大小数据的内存操作做了不同的实现。对于固定大小的小数据如 key(16B)，使用 sse 指令优化，并取得了一定效果；对于较大的数据如 value，我们尝试了使用 avx 指令作优化，但是效果并不明显，因此在最终版本中没有采用。

inline int memcmp_16(const void *a, const void *b) {

register __m128i xmm0, xmm1;

xmm0 = _mm_loadu_si128((__m128i *)(a));

xmm1 = _mm_loadu_si128((__m128i *)(b));

__m128i diff = _mm_xor_si128(xmm0, xmm1);

if (_mm_testz_si128(diff, diff))

return 0; // equal

else

return 1; // non-equal

}

inline void memcpy_16(void *dst, const void *src) {

__m128i m0 = _mm_loadu_si128(((const __m128i *)src) + 0);

_mm_storeu_si128(((__m128i *)dst) + 0, m0);

}

总结

上述系统最终成绩为 38.3 秒，其中写阶段为 29 秒，读写混合阶段为 9.3 秒。我们介绍了所做的各类优化，但是其中一些优化，比如 Bloom filter 的引入并没有带来期望的性能提升，还需进一步思考。此外，我们仅利用了 CPU 的 L3 cahe 来缓存热点数据，至于在 DRAM 中缓存数据，我们仅在实现读无锁前进行了测试，得到了对性能没有提升的结论，在引入无锁操作后或许会更加有效，但是由于时间关系最后没有尝试。

通过本次比赛，我们对 AEP 的性能特征有了更好的了解，如果未来还有类似机会，希望能取得更好的成绩。

查看更多内容，欢迎访问天池技术圈官方地址：tair 性能挑战赛攻略心得-Zzzzz_天池技术圈-阿里云天池

https://tianchi.aliyun.com/forum/post/155144

​