LevelDB 学习备忘

LevelDB 设计出发点

​ LevelDB 是一个轻量级，写优先，批量读，硬盘存储的K-V嵌入式数据库，这是其许多设计和优化的出发点。为了保证读性能中查找操作的可用性，一段数据必须要被有序地放入到数据库中，并且最优的算法复杂度是固定的——O(nlogn)，这意味着数据被放入预定位置延迟是具有最小值的，即写操作必定会具有固定的延迟。LevelDB 的设计就是如果合理地利用结构来优化这个延迟，来获得最小的写入延迟，核心技巧就是将数据写入数据库的操作分解，并且尽可能地将操作放入后台线程中运行，以此来获得最小的用户输入延迟，从而获得优异的批量写入性能，并且同时保证一定的读性能。

​ LevelDB 的典型应用之一是作为临时存储——在本地临时存储用户的工作数据，当工作确认提交后再整体发送给其他数据库。

LevelDB 的写入延迟优化

​ 不同于其他的单机数据库形式，LevelDB 的设计更多地用于嵌入式数据库，因此必须要保证数据库的系统资源占用较小。LevelDB 的写入延迟优化的核心思想是进行数据写入操作的分解，牺牲一定的总操作时间，来换取每一步操作的低延迟，从而实现较低的用户操作延迟以及较低的系统资源占用。

​ 总体来看，LevelDB 中数据的写入流程可以被分解为：

• WAL 日志：目的为获得低用户写入延迟
• 批写入缓冲：目的为获得较少的线程同步次数
• 内存缓冲表：目的为优化用户修改近期数据的需要
• SSTFile 以及合并：目的为减少系统占用，优化读性能

WAL 日志

​ 虽然将数据有序地写入数据库中的延迟最小是 O(nlogn)，但是只是将数据持久化到硬盘中的延迟只有 O(1)。利用 WAL 操作，用户调用 Put()操作时，操作被追加到 WAL 文件中即可对用户操作返回成功。实际设计中，LevelDB 将操作记录到内存缓冲区后，再写入到 WAL 文件中，后台线程会根据内存缓冲区完成后续的数据写入操作。由于 WAL 文件流时追加形式，并且是持续打开的，不需要寻址，因此该速度非常快。

批写入缓冲

​ 在 LevelDB 中，具有一个缓冲区用于存储用户的写入操作。只有当该缓冲区满时，或者经过一段时间后，后端线程才会将该缓冲区中的数据真正写入到内存中的跳跃表中。这一设计主要的优点如下：

• 优化跳跃表写入时间：跳跃表写入操作需要进行查找，查找操作是插入延时的主要原因。利用批写入缓冲，可以将用户的 N 个操作根据键值进行排序，在进行跳跃表写入时，最坏情况下只需要从头遍历一次跳跃表，大大节约了查找的时间。
• 符合用户操作习惯：用户在执行插入操作时，可能会在短期内多次更新同一个值，这样可以将多次插入操作合并为一次。
• 优化线程同步：跳跃表是需要由多个后台线程共享的（插入线程，持久化线程，读取线程），执行写入操作时是需要进行加锁的。执行批写入时，写入时间更短，获取锁的时间更短，同时唤醒其他线程的时机也更少，对线程同步是有益的。

​ 批量写入也有一定的弊端，主要是数据库宕机时会增加恢复时间，但总体来说对数据库性能的影响很小。

MMAP (跳跃表)

​ mmap 主要是实现了缓冲区的功能，将多次写入硬盘的操作合并为一次写入。由于操作系统的调度机制，频繁进行 IO 的线程优先级是比较低的，线程频繁进行 IO 操作会浪费很多时间在调度上。同时，使用内存缓冲区时，可以将整个表进行数据压缩操作，节约硬盘的存储空间。

​ 跳跃表是一个综合来看比较优异的数据结构。对比跳跃表、哈希表、红黑树三种典型的数据结构，哈希表并不是一种顺序容器，在迭代操作的时候可能会遇到问题（迭代器失效），红黑树的插入操作因为涉及到旋转，时间常数会比较高，插入性能略差。而跳跃表可以提供顺序迭代访问，并且插入数据时比较简单，很容易实现无锁结构，易于并发访问，因此 LevelDB、Redis 等一些内存数据库经常会使用跳跃表进行缓存操作。

​ MMAP 的惰性删除机制：在引入惰性删除机制前，对跳跃表的操作需要分为四类：读、写、删除、修改。其中，写、删除操作因为涉及链表的重构，是需要写并发控制才能够运行的；而另外两种操作，并不涉及到链表内部节点的修改，只需要将值设置为原子量就可以进行并发访问了。在引入惰性删除机制后，通过修改节点的标志量来标记删除，当 MMAP 持久化时再删除节点，这样就将删除操作变更为了修改操作，能够大大提升对内存表的并发访问量。

SSTFile

​ 为了保证读性能的可用性，必须将键值对放入预期的位置。如果数据库简单地将所有数据在硬盘中有序排列，那么每次将 MMAP 中的数据插入到硬盘的操作时间复杂度就是 O(nlogn)，但是这样会导致一次插入操作的系统占用过高。LevelDB 设计了一套分层存储机制来代替传统的存储机制。

​ SSTFile 是数据在硬盘中的组织形式，不同的 SSTFile 分为不同的层级（ 0 - n ），文件内部的键值对是有序排列的，Level 0 之外的文件在层级之间也是有序排列的。每次 MMAP 中的数据需要持久化时，会生成一个 Level 0 的 SSTFile，如果一个 Level 对应的文件数量过多会触发合并操作。这样设计，高层级的数据是有序的旧数据，低层级因为单个文件数据量很小，因此无序存储也不会过多地影响系统的读性能。每次进行读取操作时，从低层次往高层次进行查找，直到找到数据。

​ 很显然，这种设计会造成写扩大：同样的数据被写入硬盘多次才保证了全局一致性；但是这种写扩大是被分摊到多个不同的时间节点的，虽然总的写入时间加大了，但是却能够确保每个时间点的系统占用很小。因为 SSTFile 的合并是被动的，数据库只会惰性地检查每个层级是否满足合并条件，并且确保一次只存在一个合并操作；此外，如果一次合并操作花费过多的时间，那么数据库还会中断本次操作并选择延迟执行，以防止MMAP 不能及时持久化到硬盘中。

修改和删除数据

​ 由于数据库采用层级的查找机制，当用户需要进行旧数据的修改时（MMAP 中数据并不存在）；LevelDB 其实并不会对文件中的数据进行查找，而是直接将新的数据写入到 MMAP 中，并不需要删除掉旧数据。因此，在 LevelDB 中，修改操作其实已经退化为了写入操作。同样地，删除操作也只会在 MMAP 中查找数据，若未查询到数据，则会在 MMAP 中插入一条删除记录。

​ 这种优化是因为 LevelDB 面向的应用场景中，用户更加倾向于频繁修改最近的数据，而旧数据的修改可能只会零散的发生，因此额外的硬盘占用量是很小的。

LevelDB 的读取优化

​ LevelDB 是一个批处理的数据库系统，这种应用场景下，读取操作是具有显著特征的。

• 用户可能会多次修改最近的数据，如不小心输入错误的数据。
• 对于旧的数据，用户可能会批量读取并进行操作。

​ 由于 LevelDB 本身存在两个缓冲区，因此已经满足了修改最近数据的需求，基本上只有对旧数据的读取需要进行大规模优化。

文件索引与布隆过滤器

​ 文件索引是一个经典的文件读取优化模式。在 LevelDB 中，每个 SSTFile 都会在内存中保留一个索引，索引包含了数据日期，最大键值、最小键值、最近操作时间、最近读取次数等一系列信息。如果 MMAP 中没有查询到用户需要的数据，那么就会触发对 SSTFile 的查找，在每个高层级中键值是有序的，因此可以在层级中对键值对执行二分查找；对于无序的Level 0 数据，因为文件数量很小，执行顺序查找也不会有较高的性能损失。

​ 通过键值范围确定可能的 SSTFile 文件后，LevelDB 还需要通过布隆过滤器来保证该数据存在的可能性；只有成功通过布隆过滤器，数据库才会将文件读取到内存中。同样，文件的内部也是有序的，同样可以执行二分查找，降低查找的时间复杂度。被读取到内存中的文件会缓存一段时间，以此来应对用户多次读取同一段数据的需要。

版本控制 MVCC

​ LevelDB 中写入操作是直接写入到最上层级的，并不会被读操作读到，因此唯一可能出现的冲突是 SSTFile 合并操作与读操作的冲突，使用简单的 MVCC 并发控制就可以避免冲突。

​ 执行读操作时，LevelDB 会将对应文件的引用量加一；当执行迭代器操作时，会将当前全部文件标注引用。当合并操作被触发，原有的文件需要删除时，根据文件的引用量来判断是否真正执行删除操作；若引用不为 0，则进行惰性删除机制，当引用为 0 时再自动触发删除操作。

迭代器遍历操作

​ LevelDB 的读场景存在大量的批量读取，使用迭代器进行数据库的遍历有助于用户简化代码。但由于 LevelDB 中修改和删除操作并不会真正地删除掉旧数据，因此在遍历数据库时必须采取一定措施来防止用户读取过期数据。

​ LevelDB 中只提供全局有序的迭代器操作，并且能够保证数据的有效性。具体做法为：在每个 Level 上都创建一个内部迭代器，当调用迭代器 MoveNext()操作时，使用类似归并的思想进行操作，这样就能够消除过期数据带来的影响。同时，在创建一个迭代器时，会自动创建一个快照，快照只记录需要访问的文件并声明引用，并不会直接复制数据。

防止读扩大

​ LevelDB 的层级读取机制并不能很好地处理一种情景：用户短时间内需要频繁读取一段老数据。该情况下，每次都需要从头开始查找，会消耗过多的查询时间，同时还会造成读取的文件过大，这是需要进行优化的。具体的优化措施为：开辟一片最近读内存缓冲区，将最近读取过的数据存入缓冲区中。缓冲区采用一定的置换策略，并且保证在缓冲区内被多次读取的数据会被持久化到 Level 0 中。

LevelDB 的系统占用优化

​ 当 LevelDB 作为嵌入式数据库使用时，必须要保证较低的内存和 CPU 占用来维持整体软件的性能。类似于写入操作，LevelDB 完成相应功能的总时间也是具有优化上限的，只有采用分割任务的方法，才能保持长时间的低系统占用。

内存池与 Slice

​ LevelDB 内部的内存分配是使用内存池进行分配的，内存池具有效率高、能够避免系统级内存碎片的优点。数据库进程如果只是使用系统调用来简单分配内存，不仅会出现内存频繁申请和销毁的情况，长时间运行还会造成系统级内存碎片，导致系统可用内存下降。

​ 使用内存池会引入较为繁琐的内存管理，因此 LevelDB 引入 Slice 数据结构来简化内存分配。 Slice 是字符串指针和字符串长度的集合，LevelDB 中的所有数据段底层都被存储为 Slice 格式，所有内存申请都是建立在内存池的基础上的，并且会尽量保证持有的内存区域尽可能小。

SSTFile 合并

​ SSTFile 合并操作会评估当前数据库的系统占用情况，并且会保证一次合并操作并不会持续过长时间。如果一次合并操作耗时过长，该合并操作会被中断，并且选择合适的时机再次执行。

本篇文章简述了 MongoDB 与 MySQL 设计中的一些读写优化，更加偏向随笔记录。

由于 MongoDB 与 MySQL 的设计年代不同，因此设计思路也有所不同。从整体上看，MongoDB 的优化更加偏向于写入性能，而 MySQL 的优化更加偏向于读取性能。

读取链路的优化

​ 由于 MongoDB 大量数据和索引是常驻内存的，所以读取性能是会比 MySQL 高很多的，通常来说 MongoDB 的写入性能更容易达到瓶颈。MongoDB 的设计中牺牲了一定的读取性能来换取更高的写入性能。而 MySQL 大量数据是常驻在硬盘中的，读性能的可优化之处更多也更加具有性价比，因此做了较多的优化来换取更高的读取性能。

MySQL 读取链路优化

​ MySQL 在读取链路的优化主要有查询缓存、页缓存、自适应哈希索引、CheckPoint、覆盖索引、MRR 优化、ICP 优化

MRR 优化

​ 需要查询时，先根据辅助索引将 WHERE 语句中所有符合条件的主键值放入缓冲区，在缓冲区进行排序后查询。这样可以将随机 IO 转化为顺序 IO。

ICP 优化

​ 当索引取出时，会根据 WHERE 语句条件进行判断，这一优化是适用于联合索引，或者 WHERE 语句中包含主键值的情况。

写入链路的优化

MongoDB 写入链路优化

​ MongoDB 的写入链路主要做了以下几点优化：Check Point、Copy On Write、无锁 B+ 树、Insert List、事务组提交。

Check Point

​ Check Point 技术允许 MongoDB 按照每一秒的频率对整个 B+ 树进行刷盘操作，这使得大量的写入操作在写入日志后不需要立刻进行刷盘，只需要写入到内存当中。结合Copy On Write可以使得 B+ 树在正常刷脏的过程中也不会阻塞写入。

Copy On Write

​ Copy On Write 技术是在上一 Check Point 的基础上在内存中新开辟内存区域进行写入，这样做的好处主要有两点：第一是很好地区分了脏页，在刷脏的过程中减小了遍历的范围，提高了刷脏的效率，第二是能够减少刷脏过程中的阻塞时间，如果一页在刷脏过程中被写入，那么将会立刻开辟出一个新的缓冲区，写入操作将会写入到该缓冲区的跳跃表中，并不会造成写入的阻塞（但并不意味着不会增加写入的时间，事实上，在刷脏时写入将会等待缓冲区的分配，这会稍微延长写入时间）。

Insert List

​ MongoDB 中所有的写入操作并不是在原有的位置上更新。每一个页表中都有多个跳跃表，插入操作会将值插入到统一的缓冲区内，并且在跳跃表中增加指向该值的指针，并且跳跃表是可以做到无锁并发的，可以大大提高写入的性能。但是这同时会造成读取链路变长，在读取时需要首先查找原有的值数组，然后再对跳跃表进行遍历。

无锁 B+ 树

​ 这里主要是针对 B+ 树节点的分裂优化，由于 B+ 树节点的分裂会造成写入的阻塞，在 MongoDB 中只有单个节点短时间内插入过多数据时，才会允许 B+树节点的分裂，其余情况下，只有在 Check Point 或者冷淘汰过程中才会进行节点的分裂。所以 MongoDB 中内存中页面的大小可能与硬盘中的页面大小不相同，在刷入硬盘中时，会将内存中的页面分为几个较小的页面写入到硬盘中。

​ 单个节点插入过多数据时，会将最后一个插入跳跃表放入到新的节点中，这一过程是可以做到不阻塞的（先将剩下的插入操作引导至新的页面中，随后再将旧节点拷贝到新的页面上）。但是这种设计会对热点数据的读取性能造成一定的影响，最新插入的数据需要更多的查询次数，降低了读取性能。

事务组提交

​ 事务组提交是数据库系统中比较常见的优化，但 MongoDB 与MySQL的组提交有所不同。MongoDB 中组提交的缓冲区很小，并且每次组提交后都会进行刷盘，而 MySQL 中时以文件的形式来进行刷盘的。MongoDB 中，一次组提交中线程会将 log 拷贝到缓冲区中，拷贝完成按照 log 的序列号进行提交，不会造成不同组的乱序提交。

MySQL 的写入链路优化

MySQL 写入的优化主要集中在如何将随机 IO 转化为顺序 IO 上，这是因为在设计时 MySQL 的 B+树索引主要是存储在硬盘上的。

插入缓冲区

辅助索引的写入是统一写入到缓冲区后，再进行刷盘操作。这一优化是因为辅助索引通常并不是聚集的，直接写入会造成随机 IO，通常引入这样一个缓冲区，可以结合异步 IO 机制将随机 IO 转换为顺序 IO，提高刷盘时的性能。

Check Point 技术

MySQL 中同样是采取了该技术，当数据需要写入时会将对应的页读取到内存中，然后在内存中进行修改，随后该页并不会被立刻刷入到硬盘中，而是会由 master 线程进行刷盘。MySQL 中的该设计其实主要是考虑到热数据的问题，刚刚写入的数据被再次修改和读取的概率是比较大的，这一举措不仅优化了写入性能，还能够优化读取性能。

事务组提交

bin log 的组提交机制类似于 MongoDB。redo log 则是采用多个文件缓冲和双指针的机制，一个指针指向当前写入的文件缓冲区，另外一个指针指向需要刷盘的缓冲区，实现无锁写入。MySQL 的bin log组提交被 wiredtiger 中的 journal 组提交所借鉴，这确实是一个比较巧妙的设计，但是 MongoDB 中将应用层的日志也当做数据库中的记录，这一设计了避免了bin log 需要和 redo log 分开进行提交的缺陷。

异步 IO

异步 IO 是 MySQL 其他许多优化的基础，异步 IO 允许操作系统将多个 IO 操作合并并且重新排列顺序，使之更加符合硬盘的写入顺序。

刷新邻接页

这一操作在固态硬盘时代好像是一个负优化，一般会关闭。

对比

​ MongoDB 的写入链路是比读取链路要短的，这一点与 MySQL 正好相反。对于单独的事务来看，由于应用层日志是不需要单独提交的，所以 MongoDB 的 WAL 写入理论上是要比 MySQL 快的，（事务在写入 WAL 后就可以返回）。

​ 在大量事务写入的情况下，很容易会造成热点页刷脏的问题。由于 MongoDB 允许内存与硬盘中 B+树大小不相同，并且针对内存中的 B+ 树做了写入优化，大量写入的情况下会优先写入到内存缓冲区中，并且优先在内存中进行分裂。在处理这种瞬时写入压力时，MongoDB 的设计会更加好，这主要是 MongoDB 的设计考虑到了大量的内存缓冲，并且牺牲了一部分读取性能换来的。

​ 最主要的是，MySQL 作为关系型数据库，其事务隔离等级要求较高，这同样会造成较大的性能损耗，例如外键约束、间隙锁等。

​ 但是，MongoDB 在指定主键插入时，由于插入的位置可能并不是页面内最后一个跳跃表，这样就可能会导致创建出多个新页面才能够将插入位置放入到新页面中，或者来不及进行内存节点分裂，导致页面被锁住禁止写入，这样会造成较大的性能毛刺。因为要插入一个非常大的跳跃表，并且还要完成多个页面的持久化。此外，指定主键时，如果数据库体量较大，导致大部分数据不能够常驻内存，MongoDB 可能还需要从硬盘中读取数据来确保主键是唯一的，这样就导致数据量较大时指定主键的插入性能非常低。

​ 所以，MongoDB 并不适合存储那些由用户指定，并且需要保证唯一性的数据，例如用户名称等，而订单编号这种情况可以直接使用 uuid 进行插入。