KV系列1 - LMDB

注: 本文仅为笔记，不怎么通顺和严谨。

KV系列属于一个大规模场景的必备品，而且通常很多公司会选择自研，一方面是各种不同产品均有局限，而大家的需求都有差别。另一方面社区已经有一些比较好的 building blocks，可以方便地进行组装和修改。最常见的情境是，分布式KV的开发 = 选一个底层kv存储 + 一个分布式协议。比如TiDB,ETCD等等。最近看 cloudflare 的 blog, 也是类似的场景。他们选的是 LMDB + 自研的分布式策略(称不上算法，比较简单)，也很好的满足了自己的需求。

全称是 Lightning Memory-Mapped Database, 使用内存映射文件，读写性能比较高。

LMDB的一些特性:

• 支持APPEND模式，提高写操作的性能
• 支持多进程/线程同时访问。这种场景下读性能可以随着实例数增加而线性提升。
• 单独写不block读, 读也不 block 写。
• 不需要 transcation log, 提高了写性能。

实现上来讲，利用内存映射是一大特色。通常的文件读取操作，通过read系统调用，要先把数据从硬盘 copy 到内核，然后再拷贝到用户空间。而 mmap， 不直接进行数据拷贝，而是在缺页中断时进行处理。而且是直接拷贝到用户态，所以会比 read 效率高些。另外，这种内存映射是只读的，也避免了程序错误破坏存储结构。写操作则是通过 write 系统调用完成，由系统来保证数据一致性。其他细节：

• 使用 B+ tree.
• LMDB只允许单个写，性能有所降低，但是不再需要WAL日志，以及其他种种并发控制的冲突及代价。
• LMDB中，数据的基本操作单元是页，COW也是以页为单位。
• 如果写操作比较多，那么数据版本也会很多，旧数据会占用大量空间。LMDB会将旧的页插入到一棵B+tree当中，然后等没有事物再用到它之后就可以重复利用。这样省去了定期清理操作，但是无法保证数据可以恢复到任意时刻了。
• 数据访问可以直接返回内存指针，避免内存拷贝。
• COW保证存储结构一直是合法的。系统崩溃不会导致数据库处于一个不一致的状态。最坏的情况只是丢失了一些未提交的数据。根据一些学界的研究，尚没有发现因为使用 LMDB 导致数据损坏的案例。

LMDB中事物的实现思路如下:

• Atom（A）: LMDB中通过txn数据结构和cursor数据结构的控制，通过将脏页列表放入 dirtylist中，当txn进行提交时再一次性统一刷新到磁盘中或者abort时都不提交保证事务要不全成功、要不全失败。对于长事务，若页面spill到磁盘，因为COW技术，这些页面未与整棵B-Tree的rootpage产生关联，因此后续的事务还是不能访问到这些页面，同样保证了事务的原子性。
• Consistency(C): 有如上的操作,保证其数据就是一致的，不存在因为多线程同时写数据导致数据产生错误的情况。
• Isolation（I）：事务隔离通过锁控制（MUTEX），LMDB支持的锁互斥是进程级别/线程级别，支持的隔离方式为锁表支持，读读之间不锁，写等待读完成之后开始，读等待写完成后开始.
• Duration（D）:LMDB中，没有使用WAL、undo/redo log等技术来保证系统崩溃时数据库的可用性，其保证数据持续可用的技术是COW技术和只有一线程写技术。假如LMDB或者系统崩溃时，只有读操作，那么数据本来就没有发生变化，因此数据将不可能遭到破坏。假如崩溃时，有一个线程在进行写操作，则只需要判断最后的页面号与成功提交到数据库中的页面号是否一致，若不一致则说明写操作没有完成，则最后一个事务写失败，数据在最后一个成功的页面前的是正确的，后续的属于崩溃事务的，不能用，这样就保证了数据只要序列化到磁盘则一定可用，要不其就是还没有遵循ACI原则序列化到磁盘

总结来看，LMDB是一个极为优秀的产品。即使作者声称它主要是为了读场景而不是写场景，但实测的结果都不错。BUG少，稳定性强。

Cloudflare 的实践

Cloudflare 需要一个分布式的 KV Storage 来存储用户配置信息，当用户做了改动之后，能很快地分发到所有的数据中心。最开始用的是Kyoto Tycoon datastore, 在使用过程中发现了不少问题，最终切换到了 LMDB.

需求整理:

用户可以修改他们的配置数据，然后cloudflare会下发这些配置数据到每个区域的每个机器上。它期望的是每个数据中心即使与中控服务断了连接仍然可以独立服务。结构大致如下所示：

由中控节点先下发到各个数据中心的 Management Node, 然后再下发到各个work node 上。每个 work node 都依赖于下发的 config store 来做决断。

最开始，使用的就是 KT(Kyoto Tycoon datastore)。然后发现了的问题如下:

• 读写并发时，读性能下降的很快。排查发现是 flush to disk 的时候 block了。之前的解决办法只能是 disbale fsync, 只在 process shutdown的时候同步数据，代价就是数据损坏的可能性大大加大。数据量太大的情况下，shutdown 也会变得很慢，容易被 systemd kill 了。
• 跟上一条相关，数据一致性的问题。如果无法正常的 shutdown, 那么数据库容易损坏数据，尤其是在关闭 fsync 的情况下。KT 自带了一个修复的功能，但数据量大的情况下效率太低。所以 cloudflare 采取的策略是不修复，直接从健康的 node 上复制数据，代价就是运维成本大大增加了。
• 数据同步的问题。机器从 management node 获取的 transaction log 可能是不全的，因为中间有一些被GC了而无法找回。
• 不支持多进程同事访问一个数据库文件。这导致无法无缝升级。

这些问题无法通过运维手段来改善之后，cloudflare 就计划换 storage engine, 其考虑因为主要有如下几个：

• 支持运行时的 snapshot.LMDB 的架构做 snapshot 比较容易
• 读比写更频繁。
• 支出多进程并发访问
• 数据一致性好

LMDB在这几个方面支持的都比较好。但 LMDB 本身并不是一个分布式存储系统，还是需要 cloudflare 自己再其之上封装一层来达到其目的。首先就是复制协议上的改善，不再是KT那种基于时间戳的，而是基于递增数字:

< 0023 SET “hello” “world”
< 0024 SET “lorem” “ipsum”
< 0025 DEL “42”…

这样更容易确保数据一致性。另外因为写不频繁，可以由单一的数据中心来执行写操作，而且尽量使用 batch.其他方面的改进有:

• transaction log(就是上面的同步协议里的内容) 也存在LMDB中
• 大 value 数据由程序切片和组装
• 支持 kv的 checksum
• snappy 压缩 transcation log.
• 每个节点配置一些 primary server 和 secondary server. 前者用来同步数据。如果前者数据太老或者有问题，那么从后者同步。secondary server的数据一般会保留的更久。
• 升级时在client支持retry.并通过hand off sockets来执行新老程序交接。

Links