BoltDB

BoltDB是一个简单的键值数据库实现，主要特性包括：单文件，基于COW的B+树键值存储，基于mmap的页面管理，可以看作是LMDB的简化版。原来的BoltDB已经archive了，现在有etcd维护的BoltDB而fork，叫BboltDB变化不大

下面简单了解下BoltDB的设计和实现

内存管理

BoltDB中的页面是定长的（如4K），但每但key和value是变长的。在BoltDB中，页面又有多个类型：Meta、Freelist、Node。其中meta类型的页面有固定位置的两个用于相互备份，而freelist页面则记录了数据库文件中空闲的页面的id，最后node页面即B+树的节点，也是存放键值对的地方

这里只关注node页面的管理，BoltDB中，同一个node存在两种形式，一种是在数据文件中固化的二进制数据page，另一种是内存中的数据结构node。在树的查找过程中会将page加载到内存中转化为node，并且这些数据都是只读的，当设计到新增和删除时，直接在node上操作，当事务提交时，将这些修改了的node重新会根据其大小申请内存，并转化为page格式，最后写入到文件中的其他位置

因此，node而页面管理非常简单：1. 在加载时，将mmap内存转化为node缓存起来，2. 在提交时，缓存的node写入到新分配的内存

文件管理

虽然BoltDB只有一个文件，但由于B+树的合并会产生删除的page，分裂会新增page，对于删除来说，BoltDB会记录删除的page id到freelist页面中，后的新增如果能在freelist中找到连续的页面，那么就从freelist中分配，结果就是覆盖掉已删除的页面，实现垃圾回收利用；否则就需要扩大数据文件的

文件的扩大，是在事务提交时发生的，在提交过程中会收集脏数据写到page（即将node序列化为内存中的page）中，当freelist无法满足时，就会从全局最大的page id开始为这些数据分配id，而这些id乘上页面大小，就是写入的偏移

数据文件在BoltDB中的读写分别使用mmap和write + sync完成，其中mmap以只读方式映射

并发控制

从前面的描述可以发现，在BoltDB中所有的修改都不是原地的，而是先在内存副本中完成修改，最后将修改持久化到文件中，这种对B+树的修改到节点拷贝的技术称为Shadow Paging，常用于COW文件系统的实现上，在数据库领域用得很少，其中一个很重要的原因就是对性能的影响。但这种技术也有一些优点，从修改的root节点出发可以看到和原来的B+树不同的数据，从原来的root出发又可以访问到从未修改过的数据，这是天然的快照实现

因此，在BoltDB中，读事务不阻塞写事务，写事务也不阻塞读事务，这满足MVCC的特点，虽然只有两个版本（BoltDB中的写事务是串行执行的）

持久性和原子性

BoltDB没有日志机制来保证持久性，而是使用了两个meta页面相互备份，只有在写事务时才会出发meta页面的切换，当遭遇到崩溃时，会检查meta页面的完整性，从一个完整的meta恢复，由于同时只能执行一个写事务，因此两个meta是足够的

当BoltDB在刷入数据页面是遭遇崩溃，那么由于所有的修改都在内存中，因此不会出现数据不完整的情况，要么全都丢失掉

处理大的键值

BoltDB限制了key的大小（32K），对于插入的kv，只要内存能放下，都能插入成功，但在写入文件时是按照设定大小的页面来组织数据的，因此，如果数据超过了一个页面的大小，那么会在page结构的overflow字段记录额外占用的页面数量，连续的分配需要的页面数量，依次写入键值对到这些页面即可

在从文件page还原为node的过程中也是利用overflow字段，做反向操作即可

性能

从实现上来看，BoltDB的性能谈不上好，主要的瓶颈有：

没有自己的内存管理机制，依赖于操作系统的mmap，详见Are You Sure You Want to Use MMAP in Your Database Management System?
COW导致大量的内存复制
同一个事务内修改越多，性能下降越明显，因为B+树的平衡操作只在事务提交时触发。当然这个问题可以从用户侧做约束
一把大锁实现的写事务串行执行，对于巨大fanout的B+树来说，这个锁的粒度太粗了