第二届华为云数据库挑战赛参赛总结

本文主要是介绍第二届华为云数据库挑战赛参赛总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- - - 1. 赛题分析
    - 2. 程序结构及存储结构设计
    - - 2.1 分区策略
      - 2.2 存储结构&索引结构
    - 3. 读写实现
    - 4. 细节优化
    - 5. Java的不足
    - 6. 总结

继上次参加第五届中间件性能挑战赛之后，又一次参加类似的工程类性能比赛，和上次的TSDB题目类似，本次是实现多版本的KV数据库，由于上次的遗憾出局(复赛第七)，这次抱着破釜成舟一定要拿奖的的心态，最终结果也算比较满意（复赛第五,Java语言最高分）。

1. 赛题分析

本次比赛需实现一个多版本的KV数据库引擎，写入为随机写，查询功能为MinV～NV Delta的累加结果，同时需支持进程奔溃级的故障恢复。本赛题的读写比例为7:1，需寻找合适的数据组织方式来最小化写入和查询IO的总耗时。

赛题介绍

代码地址

2. 程序结构及存储结构设计

2.1 分区策略

评测程序是30/15个线程并发的发送数据，读写同时在进行。由于key可能在多个线程中出现，为了减少一次查询的IO次数，我们在写入时让相同的key放入一个文件。但是如果全局单文件的话同步消耗不可忽视。因此我们决定基于key进行分区。最多30个线程写，理想情况下，同一时间每个线程写不同的文件，因此将分区定为30。文件Id为hash(key)%30。

由于索引结构中包含了key/version，因此查询时不需要文件中的key/version，所以在一个分区下我们将key/version存入一个文件，delta存一个文件，查询时只需读取delta文件。

2.2 存储结构&索引结构

为了让读取尽量能够在一次IO中完成，我们采用了随机写delta数据的方式，尽量将相同的key紧凑的存储，将文件分为多个page，page的大小固定，如果一个key的delta超过了page的阈值，则顺序开辟一个page存放此key的delta，一个page中只会存放一个key的delta。

key和version采用顺序追加写，同时每个key/version后面追加一个delta的偏移坐标。一个分区Bucket的结构如下图所示：
在这里插入图片描述

Key/ Version文件有两个作用

故障恢复时构建内存索引。
当数据总量大至索引无法在内存中存放，可以将key/version文件排序，在内存中构建稀疏索引，采用二分查找来查询所需的key和 version。

由于索引数据可以全放入内存，相比于B+树，Hash索引更具有查询优势。因此采用基本LongObjectHashMap充当索引，即Key -> Versions的映射，Versions保存了key所有的v，以及该key所拥有的pages。

3. 读写实现

写入接口的传入的是一个package，我们对package中相同的key进行压缩合并，同时和可能溢出int，但是不会超过long，因此对合并之后的delta进行压缩。然后逐个遍历不同的key，通过hash(key)取得key的分区Id，根据当前分区的索引判断key是否需要开辟一个page，如果不需要就将delta追加至已存在的page中。否则就开辟新page，并且将新的page位置添加至索引中。key/version/off追加至id.key文件。

key只会在一个文件中，只需找到相应的bucket中的Map索引，遍历Versions中的version即可，因为delta是聚集存储，基本上一次IO即可完成查询。