BoltDB

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

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

内存管理

BoltDB中的页面是定长的(如4K),但每但key和value是变长的。在BoltDB中,页面又有多个类型:MetaFreelistNode。其中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中的读写分别使用mmapwrite + 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的性能谈不上好,主要的瓶颈有:

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