PidanDB

PidanDB是一个采用C++语言编写的key-value存储，支持并发读写事务与持久化故障恢复。

主要特点

• key和value都是任意的二进制字节串。
• 纯内存存储，所有数据都保存在内存中。
• 支持常见的Put、Get、Delete和Scan等操作。
• 实现write-ahead-log(WAL)，支持故障恢复。
• 高性能B+树做内存索引，充分利用多核优势，具有良好的多核扩展性。
• 支持SQL标准中可序列化(serializable)和已提交读(read committed)两个隔离性级别的并发事务。

主要设计要点

为什么选择B+树

目前索引场景的数据结构主要有B+Tree、Skip List、Masstree、BwTree和ART等，因为需要支持Put、Get、Delete和Scan这四种操作，综合考虑来看，一个优化良好的B+树是非常不错的选择。

如何做到良好的多核扩展性

一开始想实现无锁的索引数据结构（比如无锁B+树），但是考虑到无锁的实现非常复杂，于是放弃。最终参考了这篇论文，实现了一种基于Optimistic Lock Coupling加锁算法的B+树。特点是读操作几乎不需要修改任何内存中的数据，所以并发读的性能非常高。写操作也尽量减少多线程竞争，以此达到充分利用多核优势的特点。 另一方面，在实现MVCC和垃圾回收时，也要尽量避免多线程竞争，不仅是要无锁，甚至要减少原子频繁的原子写操作，因为在多核情况下，cache友好是提升性能的关键。

如何实现并发事务

目前主流数据库实现事务都是采用MVCC，因为MVCC可以真正实现读不阻塞写，写不阻塞读，各种实现方式在协议的选择上各有不同。常见的如时间戳排序、两阶段锁、OCC等。PidanDB在选型时考虑到多核扩展性和主要OLTP的业务场景，选择了多版本两阶段锁（MV2PL）。

性能

在腾讯云16核32G的S5机型上测试，所有测试key和value均为长度为32字节的字节串。测试场景为总共1000万key-value的读写，结果为耗费的时间（单位毫秒）。性能测试采用的隔离级别是已提交读(read committed)，用google-benchmark框架完成。

线程数	1	4	8	16
读	12853ms	3192ms	1825ms	1173ms
写	18035ms	4864ms	2850ms	1877ms

TODO

• B+树索引
• 基于2PL协议的MVCC实现
• 多版本数据与索引的垃圾回收
• WAL
• 支持用户自定义对key的排序函数

pidan是什么意思？

pidan(皮蛋)是我家猫的名字。