参加了阿里PolarDB数据引擎比赛，全部使用JAVA实现，相比较使用C++的同学成绩差的比较远，只能寄希望于组内的C++同学继续加油啦。Java在内存控制和底层操作较C++相差较大，但通过多次优化速度提了上来，超过了阿里内部员工Java代码最好成绩，也是一次很有收获的比赛。
本次比赛要求实现put(byte[] key, byte[] value)、read(byte[] key)和range(byte[] lower, byte[] upper, AbstactVisitor visitor)方法，程序测评过程是进行：
随机写；
kill程序；
随机读；
两次range顺序读。
要求如下：
1、支持多线程
2、在程序突然关闭的情况下保证数据不会丢失
3、可能有多个相同的key被put，引擎能根据key进行value更新
4、Java内存要求在2.5G内
5、64个线程并发随机写入和读取，每个线程1000000条数据（key 8B，value 4KB），总共写入64000000条数据，数据总量250G
6、每个线程两次range操作，按key值顺序读取所有写入的数据
7、代码语言：C++ 或 JAVA
写入
拿到题目最开始我们就卡在掉电如何保存的问题上，由于key值只有8B，如果每来一条数据就落盘可能会严重影响性能，同时两条key相同的数据如何能够保证写入后一个数据呢？因为项目中经常使用HBase，对其存储模型比较熟悉，我们借鉴了LSM模型的思想，将最近put的数据放在内存中，同时为了应对掉数据丢失问题，采用WAL(预写日志系统)，在每put一条数据时写入一个日志记录当前事件。具体的写入模型如下图所示：
当数据到来的时候，首先写入Value并记录其文件中的位置seq，方便后续查找。随后将key与seq(int)通过Mmap写入日志文件，方便后续数据恢复，此处使用Mmap虚拟内存映射主要应对小数据量的读写，但其实本身是顺序写入，也可以使用FileChannel写入，有Page Cache缓冲性能相差不大，而且Map本身有一定的时间开销（此处将map操作异步放入线程池进行）。最后写入key,seq到TreeMap，目的主要是对key值进行排序，方便后续查找时索引的建立，同时对于部分key值相同的数据也能在内存中及时更新value的seq，treemap写到一定数据量落盘SST，并记录目前写入的seq，程序被突然掉电时，恢复的时候首先根据记录的最后一个seq，恢复之后的数据即可。这里需要考虑的问题在于write(value)是顺序操作，如果给某个线程的value先分配了seq，另一个线程后分配seq，但抢先将value写入了文件，两者写入位置对换，则查找时就会发生not match错误，需要对put方法加锁。但直接对方法加锁会极大的影响性能，64线程的写入会非常慢，可以将put操作分区，申请多个put实例，使用路由对不同的key转发到不同的put，极大的缓解了加锁的压力，具体如下图所示：
写入耗时124s
读取
读取也是64个线程并发随机读取，需要对所有key建立索引，第一步需要排序。64000000 * (8 + 4) = 768M，如此大的数据量无法同时加载到内存中进行排序，只有每个分区单独排序，所以在路由时按照桶排序的方式指引不同key去不同的分区。这样每个分区间的数据是排序的，每个分区内的数据有很多SST，使用归并排序算法，由于SST是已经排序好的结构，每个分区只要将SST合并成一块大的SST即可，归并排序比较好实现，使用多个三维byte数组和一个队列，所有分区排序完成只需13秒。由于数据量较大，无法建立一级索引，此处使用两级索引，内存中存放第一级索引，查找时找到对应的block，加载到内存，再查找seq。建立的大SST结构如下图所示：
那么每次查找只需要先在blockIndex进行二分查找找到block所在位置（在这里我们可以使用treemap.floorkey()方法），从磁盘读取这块block(4KB IO)，使用二分查找找到对应的key和seq，按照seq读value 4kB。总的查找耗时，两次内存二分 + 两次磁盘4KB IO。
查找所有数据耗时160s。
range
range是64个线程同时发送请求，指定对应的边界（lower, upper）。使用visitor.visit(byte[] key, byte[] value)返回数据，visit调用需要按照key顺序进行。总的查找数据量是64 * 2 * 64000000，如此大的数据量查找实现时间很长，几乎不可能。此处方法是，接收来自线程的range请求并阻塞线程，等待一段时间，收到所有的线程range请求后才开始读取数据，所有数据读取完成后notify线程，由于64个线程range需要的数据相同，完整遍历数据一遍即可满足64个线程的一次range请求。
关键问题在于如何快速按顺序遍历一次数据呢？
我们已经对所有的key值建立索引，进行了排序，只需一个个SST加载并根据seq读取value即可，此处自己写个一个顺序读取key,seq的迭代器，并使用一个数组实现了队列，将key,seq放在队列并根据队列的seq多线程查找value即可，具体遍历过程如下图所示：
耗时220s * 2，线上读取速度1.1G/s，本地读取900M/s(wd black 3d)
第一次优化
在第一周完成了所有的要求后，发现这个模型还有较大的优化空间，虽然所有的读写都是使用Java NIO，但是在随机读取value时只是4KB读，完全不能打满磁盘。考虑linux系统的page cache预读取，随机读取能够命中的概率太低了，这产生了大量的IO冗余。所以第一次我的优化点在于range时如何将小文件的4KB读取修改为大文件的读取。回顾一下，数据在写入时是随机写入，需要一次性加载一个完整的存储value的文件放入内存，才能在range的时候不会重复加载该文件。并且由于内存不足，在最开始分区时我分了32个区，那么每个value文件的大小是64000000 * 4 * 1024B / 32 = 8G，不可能完全加载到内存，因此，我在写入value的时候对文件再次按照桶排序方式分片128个(key值随机分布，比较均衡)，每个文件的大小8G/128=64M，这样就可以完全加载到内存了。非常高兴的一点是，阿里云的linux服务器支持65536个文件句柄，所以同时打开128 * 32 = 4096的文件完全没有问题，将随机读写修改后并测试，没有降低速度。接下来全新的range过程如下图所示：
ByteBuffer开的是堆外内存，每个64M，一共开了6个，value队列是384M，内存队列的长度考虑了GC频率，找到最合适的点。
经过该轮优化后，range总耗时360s，线上速度1.4G，本地测试1.5G
第二次优化
初见成效后进行了第二轮优化，优化点在于随机读取时索引的查询，目前需要两次内存二分查找和一次4KB IO操作，非常耗费时间，如果能够把全部索引放入内存中，就只有两次内存查找，速度能够迅速提升。但是所有索引载入内存需要（8 + 4）* 64000000 = 800M（8byte key，4byte seq），在Java只有2.5G内存的情况下根本不可能申请如此大的空间，就算能够成功申请，由于剩余内存过少引发的频繁GC也会严重影响性能，得不偿失。开源不行，我们只能节流。之前一个分区一个文件，每个分区的seq最大是64000000/32 = 2000000，所以使用4byte(int)空间表示seq，现在文件进行了切片，每个文件被切成128份，每个文件的seq最大只有15000，完全可以使用2byte(short)来表示。这样我们索引占用空间能够减少20%。但依旧有600多M，远远不够。下一步我们对key进行动手，由于使用桶排序，在一个block中的key，前两个字节大部分完全相同，可以舍弃。我们于是在block中优化，如下图所示：
建立索引时取最后4个字节进行hash指向0~340，找到341个位置中该key存储的位置存放，如果地址冲突则后移一位（可以使用其他hash策略减少移地址次数）直到找到正确的key。查找key时先hash到对应位置，再使用第3和第4个字节进行校验，校验不成功则地址往后移位，直到找到为止。在本地测试的时候，能够通过，但在线上出现了冲突情况（两个key在hash后指向同一个地址，并且2byte校验码也相同），2byte用于校验可能不够，于是修改为4byte校验，程序通过。总的索引存储空间只有原来的一半，384M，这完全可以加载到内存中，随机读少了一次4KB IO。时间由原来的160s减少到120s。
优化总结
1、尽管目前的ssd对4K随机读写支持非常好，但是由于linux有page cache存在，随机读速度会受到较大影响，毕竟随机读取不可能命中缓存，或者人品大爆发。需要修改为大文件读写，或者使用C++代码，绕过page cache（Java 可以使用JNI调用C++）。本次比赛有C++代码同学，我全部使用JAVA，如果使用JNI那写JAVA就没什么意思了。
2、尽可能减少对象申请，初始化和分配空间以及回收空间都会大大减缓程序运行速度，使用对象池或ThreadLocal会更好。
3、尽可能使用local变量, full GC比young GC时间长。
4、正确使用jvm_parameter会让你的程序运行速度提升。
5、一个通用的程序去做一件专用的事会有大量冗余，所以尽可能根据场景对数据结构进行优化。
