首先是我们的团队和成员的简介
然后是我们对这次题目重点的理解
接下来，我会介绍一下我们最基础的架构，包括网络、磁盘、缓存等
最后，重点介绍我们每一个性能优化点
团队名叫watermelon，我们三个人都是在读的研究生，分别来自浙江大学和上海交通大学，都是明年毕业。初赛和复赛的成绩都是第四名，历史成绩非常的稳定。
我们总结了几个题目重点：
首先，KV 都是定长的：这样简化了⽂件和内存的操作和管理。
第二点，value远大于key：把 KV 分离存储，解除索引和数据之间的耦合性。
第三点，线程数固定：测评程序固定使用 16 个线程访问数据库。
第四点，只需要保证进程意外退出时的持久性：所以可以利用操作系统的缓存对写入方式进行一些优化。
第五点，分阶段测评：随机写、随机读、顺序读三个阶段互相没有重叠。
第六点，计算节点无状态：我们知道，在这种基于共享存储的计算存储分离架构下，所有持久化数据只能存于存储节点，计算节点只进行逻辑操作。
第七点，数据读取的线程和数据写入线程之间没有绑定关系：就是说，每个线程不是只读取自己写入的数据。 //与初赛不一样，读取线程id不一读的是相同id写入的数据
最后一点，随机读的随机性在每个时刻只局限在一个 10M 热点分区内：并且热点分区按写入的顺序逆序推进。
下面是我们方案的核心架构:
我们计算节点和存储节点的线程采用一对一的tcp连接，因为测评程序是16线程，所以连接数就是16。在存储节点，我们有数据持久化产生的文件，以及读写文件的缓存。在计算节点，我们维护了读数据的缓存，但是没有写数据的缓存，因为要保证计算节点被 kill 的数据持久性。并且我们的索引也是只在计算节点上维护的，在数据库启动阶段从存储节点把索引数据拉到计算节点。
接下来，具体介绍一下我们的文件组织形式:
首先，按写入线程进行数据的分区，就是说，每个写入线程只顺序写自己的分区文件，这样就避免了多线程写同一个文件冲突的问题。
然后，在每个分区内，将 key 和 value 分离存储为两个文件，一个是key log，一个是value log。可以解除索引和数据之间的耦合性。并且我们为了提高写入value 的速度，对 value 进行了缓存，缓存中凑齐若干个value后，再一起进行刷盘。
为了保证缓存不丢失，缓存也使用了mmap的形式，因此对应有一个缓存文件。
我们的索引也是按分区进行构建的，每个分区是一个hash，里面存的是该分区所有数据的索引项，索引项就是一个 key 和 一个value offset
复赛的优化历程，我们从最开始跑通的 2300 分，到最后的 780 分，中间经过了好几次架构和方法的改变。
首先我们的第一个优化是，我们在启动阶段把 key 从存储节点批量的传到计算节点，这样相比每个 key 都请求一次，批量的方法相当于减少了一半的网络请求，使得时间提升了 300 秒。
接下来，由于我们无法搞定网络传输大数据包的问题，因此我们选择先在存储节点实现顺序读和随机读的缓存，这样减少了存储节点的 io 次数，时间提升了 500s
再后来，我们解决了网络传输的问题，所以先在计算计算节点进行了顺序读的缓存，成绩提升到 1100s
这样紧接着，我们按存储节点缓存一样的思路，把随机读缓存也拿到了计算节点，这样做之后我们的成绩就已经突破了 800s
在最后阶段，我们又优化了一些细节问题，最终成绩是 781s
围绕读写文件，缓存策略，和网络传输这三个方面，来讲解我们是如何把这个系统的性能压榨到极致的。
对于 key 这种小数据量的读写模式，采用 mmap 可以利用 page cache 将小数据读写转换为整个内存页的读写，减少了系统调用的时间消耗。value 的大小为固定 4KB，我们知道，写入数据大小要对齐 ssd 的内部 page 时，可以达到最优写入性能。我们经过线上测试，按 1M 大小顺序写入数据可以达到最大吞吐量。所以，为每一个分区分配一个容量为 1M 的写缓冲区，写满 256 个 value 再将缓存数据一起刷盘，刷盘方式采用 direct io。并且，用 mmap 做缓存，可以保证数据持久性。
第二点，我们来看，如何做随机读的缓存，使得缓存命中率最高。现在背景是，随机读在每个时刻只局限在一个 10M 热点分区内，并且热点分区按写入的顺序逆序推进。看图，上面是我们实际存储的文件，按10M分为了若干个block，就是说，我们的缓存只能按 block 对齐进行加载数据。然后，下面是测评的热点分区示意图，我们发现一共 400w 数据，热点分区的边界跟实际数据 10M 边界很可能是不对齐的，并且边界值未知。所以，如果我们只用单个 10M 的缓存，会出现下面这样的问题。假设当前阶段，测评程序要随机访问 hot1 这个热点分区。第一个位置，我们缓存加载了block3，然后，访问第二个位置，发现缓存失效，加载了block2，继续访问第三个位置，缓存又失效了，重现加载回了block3所以，这样就产生了一个缓存来回震荡的问题，极端情况是，我要访问400万数据，一共要加载400万次大块的缓存，肯定超时，还不如不做缓存。
我们的方案是，采用两个 10M 的buffer，一前一后，一起往前推进，这样非常完美了避免了缓存来回震荡的问题。并且这个 buffer 不一定是10M，只要大于10M都可以解决这个问题。
第三点，我们来看，如何使得网络的传输效率最高。我们发现，写入阶段的网络传输时间主要瓶颈是在周转时间上，也就是说，不是网络有多么拥塞导致网络传输变慢，而是说，value发过去再回来，本身就需要这么长的时间。所以我们的优化只能是让存储节点尽可能快的返回ack信号，我们的做法是在数据写入存储节点的mmap之后，就返回ack，而不用等待page cache 刷盘。对于持久性，recover 阶段会把 cachebuffer 里面的数据都重新写进 value 文件里。
对于大块数据进行拆分，然后进行多次发送，可以在发送的同时进行流量控制，使吞吐量保持在一个较高的水平。我们的流量控制方法非常简单粗暴，在发送每两个 4k 数据之间，直接加一个延时，延时的方法是让 CPU 自旋一会。并且，存储节点也做了读缓存，把存储节点的读缓存，批量拆分传到计算节点。
最后，回到一个宏观的位置上来看，通过这次比赛，我们严格按照计算存储分离的思想来设计了我们的系统架构。对基于共享存储的计算存储分离架构有了一些认知和理解。首先，我们看计算节点我们的架构只支持一个 RW 节点，进行数据的写入。但是 RO 节点在理论上是可以无限扩展的。并且，由于底层的共享存储，所以主从复制的延迟可以做到非常低。当 RW 写入一个 kv 数据，对于 RO 节点，它只需要更新已经存在自己 buffer pool 中的数据，而如果发现 RW 写入的数据不在它的 buffer pool 中，那它什么也不做。只有在 RO 节点读取数据时，发现要请求的数据不在自己的buffer pool中，它才去下面的存储节点中拉取这个数据到自己的 buffer pool 中。这样看来，我们在实现高可用功能时候，可以很直接的进行主从切换，RO 节点可以迅速提升为 RW 节点，直接开始对外服务。再看存储节点我们当前只是在单个节点上保证了数据的持久性，而这种 kv 存储可以扩展为分布式架构，采用多副本存储，从而能获得更好的容错性，和更好的读写性能。所以这样一整套架构，可以解决很多实际的痛点，因此，会成为当今云数据库的一个趋势。
