关键要点

• 单机线程和连接问题
• 单机数据库性能
• 单机 log 处理
• 多机网络通信rpc
• 多机调度方法
• 一致性协议
• 备份方式

由于单机性能问题，选择 c++ 更靠近底层的实现一个单机数据库，尽量使用单线程处理。

由于 c++ 的线程库和网络库相较于其他语言还是较为复杂，选择 golang 做分布式一致性的调度，单机只负责 rpc 的对接，也可以直接使用 cgo 交叉编译直接搞定。

单机线程和连接问题

1. 为了方便的实现数据库的事务性和各种锁的性能问题，内存结构的维护采用单线程实现较好。
2. 集群服务器数量不多的情况下考虑维持所有的连接为一个长连接，即每台单机都保持 n 条线路到所有其他服务器，所有连接的复杂度为 \(O(n^2)\)，也便于下掉pod和增加。
3. 由于连接一直保持可以考虑原子性问题，允许发送 payloadsize 不超过限额的一个原子操作（或者说是事务操作），用单线程保证这些操作能够线性的完成。
4. 由于所有连接 fd 和内存结构的维护都基本确定，没有必要引入线程池，可以考虑把内存结构的主线程绑定到一个稳定的 cpucore，或者干脆分离它和其他的线程。

单机数据库性能

数据结构

1. 内存结构
   现在一般来说参考TCmalloc实现或者直接调用自己做一个内存池即可。
2. 字节对齐
   参考 redis/sds 的实现，确实比较细致。
3. hash 实现
   hash 其实一直是个性能难点，c++ 标准库中的 mt19937 有一个高性能的 distribute random，在这里应该是可以发挥奇效。由于个人的竞赛背景其实一直觉得 hash is not good.还是建议能用平衡树就用。
4. 平衡树实现
   平衡树一直是数据库的强需求，排序、区间查找之类的功能实在是太有必要了，其实有很多种方式，splay，treap，btree，b+tree，rbtree 甚至 trie，skiplist。个人建议使用 rbtree，还是太稳定了，如果不是因为 b+tree 的特殊结构应该就是最上位的实现。
5. gc
   一般来说也是建议参考TCmalloc的一套gc思路，三色标记，lazyfree。stw的问题可以配合一致性协议，保证非主的时候才stw就非常完美了，不过整体设计起来仍然比较困难。
6. log
   二进制写入，采用binlog方式还是很有必要的，但是由于 I/O 方面的性能问题一般来说不推荐给一个 sync 的 log 出去，这里log只用于备份数据库，格式的话就每行一句简单的sql即可（由于不是图数据库其实格式都挺好搞定的）。

lru

需要在介质间处理平衡，一般来说就是内存和磁盘之间，做一个lru淘汰机制，部分持久化，主要做备份工作和 I/O。

一般就是 O1 的实现：链表+hashmap。上面的实现也可以复用。

分布式备份同步 maybe 可以考虑外接一个 mq 处理最方便，那就不需要做这部分，不过自建的话还是要细想一下实现方式。

一些细节

1. 分不同大小开多种内存池，比如一个 8 字节的 string 完全就没必要和 \(2^{20}\) 共享同一个内存池，显然造成一些碎片化问题，这其实也是 TCmalloc 一套里面的部分实现方式，具体可以顺带看看 golang 内存结构，也有体现。
2. 系统位数区分，一般来说看 long 的最大值和 longlong 的最大值是不是一样的，一样的说明是 64 位，也可以直接环境变量判一下。
3. 大小端区分，如果涉及到 int128 这种东西的实现（比如我想支持 random 的 int128 或者是 kv 对中有个 int128），这部分可以用两个 int64 去支持，整体想做好其实也非常复杂，参考一下 c++库 absl/numeric