1.前言
排名
第一次参加这种类型的比赛，在第一赛季拿到16名尝到甜头的同时，第二赛季策略和想法的偏差，最终拿到28名。我这里说一下为什么标题是java&c++，因为个人java玩的多，但是打一些算法比赛用的c，而队友就是纯搞c的，所以基本上我们属于java和c++都踩过坑了。
由于此次比赛也是遇到了好多坑，不像大佬们，成绩出来就占据前头，所以我们的初赛和复赛框架还是大有不同的，因此在架构方面我特地细分开来详细描述。
2.赛题介绍
比赛总体分成了初赛和复赛两个阶段，整体要求实现一个简化、高效的 kv 存储引擎初赛要求支持 Write、Read 接口。
public abstract void write(byte[] key, byte[] value);
public abstract byte[] read(byte[] key);
复赛在初赛题目基础上，还需要额外实现一个 Range 接口。
public abstract void range(byte[] lower, byte[] upper, AbstractVisitor visitor);
程序评测逻辑 分为2个阶段：
1）Recover 正确性评测：
此阶段评测程序会并发写入特定数据（key 8B、value 4KB）同时进行任意次 kill -9 来模拟进程意外退出（参赛引擎需要保证进程意外退出时数据持久化不丢失），接着重新打开 DB，调用 Read、Range 接口来进行正确性校验
2）性能评测
随机写入：64 个线程并发随机写入，每个线程使用 Write 各写 100 万次随机数据（key 8B、value 4KB）
随机读取：64 个线程并发随机读取，每个线程各使用 Read 读取 100 万次随机数据
顺序读取：64 个线程并发顺序读取，每个线程各使用 Range 有序（增序）遍历全量数据 2 次 注： 2.2 阶段会对所有读取的 kv 校验是否匹配，如不通过则终止，评测失败； 2.3 阶段除了对迭代出来每条的 kv校 验是否匹配外，还会额外校验是否严格字典序递增，如不通过则终止，评测失败。
语言限定：C++ & JAVA，一起排名
总的来说大致一个系统框架如下图：
系统框架图
而我们就是要做的在此架构上的数据层中，根据相应的业务场景来设计我们存储框架，使其达到最优的效果。
3.初赛篇
3.1 Recover 正确性评测
我将主办方描述的语句中，我自己文字加粗的部分摘下来：
key 8B、value 4KB
进行任意次 kill -9
参赛引擎需要保证进程意外退出时数据持久化不丢失
我们可以清楚的知道，kv在主办发的要求下，与IO操作下字节完美对齐，而任意次kill和数据持久化则是主办方要求你不能在写的阶段做一些数据的缓存，来对比赛进行一些所谓的hack。
3.2 性能评测之随机写入
我们是根据计算每个key的hash，再进行分桶来使得数据达到均匀分布的效果,代码如下：
int temp_partition = (key.hashCode() & Integer.MAX_VALUE) % FILE_MAX;
逻辑图如下：
逻辑图
上述是对value的一种划分和写入，而另外一部分就是key的设计，关于key，我们特地设计了一种数组型分桶式哈希表，其目的在于：（1）分桶能使得数据更加均匀（2）在多线程情况下使得数据插入变得线程安全。
hash设计图
A区域每个节点是一个int字节，大约4M的小索引，当一个key过来时，hash映射到A的某一块上，同时原子量从0开始自增，该块上的地址值等于B上某一个地址，同时B上此时的地址指向下一个地址，链表形式。
B区域是存放key相关信息的一些数据，每个index包括下一个地址int型 4字节，本身key值 8字节，以及文件偏移量4字节，总共6500w个，大约1.2G左右。
为了使得在多线程情况下，使得数据安全地插入，这里采用的是CAS无锁操作
a->next =head->next;
（head->next）.compare_exchange_strong(a->next,a );
解释一下用法，令head->next 为 A，a->next为B，a为C
当A==B时，C=A；
当A！=B时，B=A；
其中head->next是某个key映射到A区域的头结点指针head的下一个指针，而a->next是当前key的值下一个指针，a是自己本身地址。分析一下如何达到线程安全的效果：
首先来了一个key，假如hash地址为A的区域某一个，这里记做A,同时此时的原子量B的地址是B1，A之前指向一个地址B
a)如果A的地址指向和B1的地址指向相同,说明上述两个语句没有被其他线程所打扰，那么A->next=a,连接成功
b)如果A的地址指向和B1的地址指向不相同，说明存在线程安全问题，那么a->next = head->next,再一次比较的时候，如果head->next在之前线程又给他改变了，那么继续a->next = head->next，直到出现（a）的情况，连接成功。
3.3 性能评测之随机读
前面的所有设计都是为了随机读而准备，所以随机读就按哈希读就行，当然里针对这种4kB的读写，为了达到最优的读数据时间，我们采取的是DIO的方式，这里涉及到linux内核的知识了，稍微提一下，linux中分为两个状态，用户态和内核态，一般的文件读取是进行了两次拷贝，即从磁盘到内核，再到用户态，然后返回给上层应用层，DIO是直接跳过中间的两次拷贝。
4.复赛篇
4.1 性能评测之随机写入
由于复赛多了一个range，还需要做两遍range增序迭代遍历，所以就算随机读IO完全打满，是根本达不到最优状态，因为复赛开始我就试过了，64线程+二级缓存最多660s左右，如果额外开成128个的话，顶多600s左右。
所以根据数据随机分布的特点，我们采取了前9位hash的方式来对value进行均匀划分，测试打印出来确实数据十分地均匀。
int temp_patition = ((key[0] & 0xff) << 1) | ((key[1] & 0xff) >> 7);
总体逻辑框架如下：
总体逻辑框架
随机读阶段基本上与初赛无差，这里就不在叙述了。
4.2 性能评测之range阶段
range阶段的设计应该是非常有意思的，在初赛的时候64个线程6400w随机读需要106s左右，而range阶段是需要1个线程就遍历6400W*2的数据，所以如果单纯的read读肯定超时，这也就提醒了我们，必须要做缓存了，逻辑图如下：
线程逻辑图
大致的思路就是额外开32个线程来对每个块文件读取数据，当读取完毕时，唤醒visit线程，此时同时visit再唤醒read线程，来读取数据，然后达到io和cpu同步的效果，最终最优的结果是202s左右，但是与前面的大佬还是差那么几秒，原来是这个互相唤醒的结果，因为在最后我们发现，其实就是IO存在瓶颈，visit速度其实很快，而这个互相唤醒等价于这两个类型的线程在一定程度上优先级相同，换句话说cpu给他两的时间片是相同的，最优的做法就是让read线程不断read，visit如果阻塞了，就直接让他让出当前时间片就行了。
0.总结
这里先说下java和c的一些差距，初赛的时候，同一套方案，我是280.290s左右，队友用c直接比我少了30.40s，在range阶段，读一份文件256M，单线程0.165s左右，队友可以达到0.1s左右，所以性能上还是有差距的。
因为也比较忙，所以花了几个小时的时间把一些最终的框架和思路给写了出来，等有时间再把一些优化的点补一补，总的来说，成绩还是不错的，也超过了一些之前打了中间件的大佬，不过还是有差距的，一些细节方面确实没别人做的好，也没有考虑到，不然最终成绩还是可以稳进前15，还是那句话，加油吧！
网友评论