LevelDB剖析(1):Basic Idea

感谢@boisterouscloud的给力推荐,特此整理为读后感,以馈诸道友:

LevelDB剖析(1):Basic Idea
LevelDB剖析(2):sstable 和 recordio
LevelDB剖析(3):memtable 和 cache
LevelDB剖析(4):Get, Write 和 Recover
LevelDB剖析(5):Compaction
LevelDB剖析(6):Iterator 和 Snapshot
LevelDB剖析(7):并发模型 和 MVCC

一、LevelDB介绍
LevelDB是Google开源的一套Key-Value持久存储引擎,IO的处理策略上可以看做BigTable的单机版(tablet). 其特点是读写性能很高,尤其是写性能比读性能还高,详细Benchmark可以参考官方数据. 除了支持常见KV存取接口如Get(key)、Set(key,value)、BatchWrite、Iterate等等外,还提供了多版本Snapshot支持. 非关系型DB. Key和Value可以是任意数据且无大小限制,但不适用于海量数据场景. 典型应用有chrome浏览器,比特币钱包等.

LevelDB本身是一个lib形式发布的存储引擎,业界不少企业或个人在基本库上做了不少改进或封装,如RocksDB、SSDB等,思想和应用都影响较广.

二、数据组织和IO
我们先尝试自行设计一个高性能的KV存储方案。

对于读取某个key的value操作,如果只考虑单维度key,可以简单地让数据在磁盘上按key有序排列然后二分查找即可:读数据时先查内存中的索引,再根据索引至多进行一次磁盘IO,同时可以引入缓存. 这里由于key量可能很大而记录可能较小,可以按整块如4K大小来存取和索引:先通过二分查找索引将目标key所在的块读到内存,接着在块中查找key;按块整体处理在IO利用率上较好,如多个连续key的查询只需要一次IO(spacial locality),以及后续再查此块内的其他key可以直接从缓存查(temporal locality).

考虑当记录不存在时能否尽量避免不必要的IO:根据记录和文件的有序性,查索引时如果发现key不属于任何块的[minkey, maxkey]范围,可直接返回不存在. 否则需要去读相关块的内容才能确定该key记录是否存在,若不存在就相当于浪费了一次IO,因此还需要一个高效的过滤策略,例如可以引入BloomFilter机制(空间换时间),至此我们的读过程看起来大致如下:

kv_read

至此针对查询操作目前能用来优化IO的手段包括:索引、块读、BloomFilter,以及缓存. 下文把包含数据块的磁盘文件称做table文件.

再来看写操作. 如果直接在原table文件上修改或插入记录的同时又要保持顺序的话,必然涉及到移动数据或维护索引等信息的更新,IO开销大处理逻辑复杂。那能不改变原来的数据并且找到一种高效写入有序数据的办法呢?很多内存结构如BalancedTree、SkipList等都支持有序数据的高效读写,所以对更新操作我们不妨先写到内存里,称为memtable,查询时先从memtable读最新数据,如果读到就返回否则继续去磁盘查table. 这里有2个明显的问题:1) 内存数据可能丢失,如进程挂了就没了; 2) 内存有限,不能一直增长下去.

对于问题1可以采用redo log的思路,在写入内存时同时append到log里,供异常后恢复mem. 这里单条记录内存和磁盘各写了1次,存在写放大问题,但append操作的性能还不错. 对问题2可以定期把memtable dump到持久层,依然不修改原有的table文件而是落地为全新的table文件,影响就是查文件时需要按从新到旧的顺序从多个table文件做查询,因为新落地的table与其他table文件的key取值范围可能会存在交集. 但是过多的table文件会加重IO影响读取性能,还会产生无效历史数据,因此可以再引入一个定期重整数据(称为Compaction/合并)的流程.

最基本的做法就是,每当新table文件达到一定数量,就把所有table文件合并为一个历史总table,以此方式循环往复,这样就达到了控制文件总数量的目的,同时可以消除掉table间被相互覆盖或删除标记的无用历史记录. Compact过程类似文件归并排序,从可控多个文件顺序地按块读取记录,输出新的历史总table的过程是严格的顺序写,因此逐字节效率是比较高的. Compact还有一个实现优势即完全不影响key的普通读写流程:Set(key)只涉及写log和memtable,Compact过程不对原有table做任何修改,因此也不影响Get(key),Compact完成后只要将DB的相关文件列表等元数据简单更新即可完成数据版本升级,其实是MVCC思想的一个直接应用. 鉴于其相对独立,Compact完全可以用单独的线程来做. 在Compact过程中,memtable可能已经又产生了多个新dump出来的table,这些较新的table将与本轮Compact的结果将组成下一轮的输入:
Compact的输入:所有最新落地的小table和旧历史总table
Compact的输出:新历史总table.

在此上述策略下,Get(key)需要从memtable和若干个table文件读取,读写操作示意如下:

kv_lsmt

注意图中读取table操作中的查索引、block_cache、filter等过程没有列出;memtable本身也可以看做新数据读写cache,延迟WriteBack成为table file.

三、Compaction 和 Level

以上便是LevelDB实现高性能IO的基本思路。但有一个明显的问题即如果每次都将全部数据做Compact,尽管逐字节效率高,但随着数据量的增加,读写总开销最终会变得不可接受,Compact将耗时巨大并拖慢整个系统. 引入单个历史总table虽然提高了Get查询性能,但Compact本身的性能较低,能否平衡一下呢. 针对Compact的数据组织和IO过程优化是LevelDB的精髓所在,也是其名字的由来. 接下来看下LevelDB实际是如何处理Compaction的.

原始方案中之所以要归并所有文件是因为当前所有table文件可能都是有交集的,历史总table的存在意味着其key space几乎与任何新table都有交集, 但首次合并后很容易将历史总table切分成若干不相交的历史子table集合,之后如果还有新table A需要合并,则只需要找出现有历史子table集合中与A有交集的那部分即可,合并后的结果依然与其他历史table没有交集,同样可按照需要将其切分为若干新历史table. 这样就消除了历史总table,并且容易看出由此产生的所有历史table之间总是不相交的. 再看对查询操作产生的影响:在查完memtable和新dump的table后,如果还未找到,我们可以根据目标key确定其所在的历史子table文件,再单独查这个子table即可,因为历史table是不相交的,该key只会存于单个历史table中. 相比原查询过程,区别就是查历史总table变成了查历史子table,查询数据量减少了,而读取文件的数量(IO次数)并没有增加,没有破坏我们做Compact的初衷目的.

可以看到这里的table文件很自然地分为了两类:从memtable dump出的新table和经过Compact输出的历史table,按照数据新旧水平分别归类称为level_0和level_1. 此时Compact操作的含义变为,将level_0中的某个或某些文件合并到level_1中去. (Compaction前后)Invariant:某个table文件要么属于level_0,要么属于level_1;level_0中的table相互间可能存在key范围交集(后文简称为相交),level_1中的所有table间是不相交的. 理由:level_0中的文件是memtable直接落地产生的,这个过程与归并无关,所以key space是任意的(用户决定). 而level_1文件是Compact产生的,由后者的归并输出逻辑保证不相交.

Compaction过程举例:

leveldb_2lvs

如图所示,假设key是整型,下一个要进行Compact的level_0中的table_A的key范围是[10,50],观察到level_0中另一个table_B的范围[14, 65]与其相交,于是也将table_B加到本次Compact的输入中,合并后的输入范围是[10, 65]. 接下来选择level_1中所有与[10, 65]相交的table即table_X和table_Y并加入作为level_1的输入,然后归并这四个有序文件,归并过程中可以顺便清理掉一些被删除或覆盖的无用记录,假设最终产生2个新的level_1文件table_K和table_M,旧的输入table(A、B、X、Y)被删除. 输出多个文件的目的是保持一个可控的文件大小粒度,方便后续其他level_0 table做Compact时按需选取. 可以按固定输出大小如2M为阈值大小做切分.

由于level_1中的文件总是不相交的,查询单个key时在level_1中只需要查其中一个table,而定期Compact保证了level_0中的table数量一般不会太多. 假如一共有n个level_0 table,则查询时最多需要查 1次memtable + n个level_0 table + 1次level_1 table,即总共n+1次磁盘IO.

可见通过分层和控制key space粒度的方式减少了单次Compact操作的IO,但本质问题依然存在:极端情况下某些level_0 table可能与所有的level_1 table都有交集,而level_1文件也会越来越多,基本相当于全部的DB数据了,又回到了老问题. LevelDB的做法是,与level_0文件不能太多的道理类似,为了限制IO,我们必须限制level_1的文件总大小和数量:推广level的概念,一共设置k个level,level越小数据越新,定期把level_n的某个table通过Compact机制合到level_n+1,效果就是level_n减少了1个table,而level_n+1则吸收了来自该table的数据,整体上看新数据会慢慢逐层往下沉淀,而查询时可能需要分别去多个level查询. 通过引入分层和分治查询,将数据归并需要考虑的范围从全局缩小到了相邻的level内,代价是数据冗余度提高以及多level查询的额外开销. 与2层结构同理,除level_0外同一level内的table文件[keymin, keymax]之间是不相交的,查询时只取其一,并且假如在level_n层查到了结果,就不用查level_n+1了. 因此在该模型下Get(key)操作最多需要(level_0文件数+level最大层数)次IO. Set(key)操作依然不受影响(写只涉及log和memtable).

通过设置每个level的文件数量或大小作为触发Compact的阈值,可以控制每层level的Compact频率,一般来说level越低的数据更新也越快,越往高level数据越旧越不活跃,因此level越低其Compact频率应该越高,具体LevelDB的策略是:对level_0,只要table文件数量超过某个阈值如4个就强制Compact,对level_k,当其数据量达到(10^k)M时就启动Compact,并且level越低优先级越高. level_0的文件数量由于直接影响到Get操作的IO性能,必须进行限制. 而对其他level则使用数据量进行限制,level越高能容纳的数据量越大(约10倍数的关系). 官方的一段说明:These merges have the effect of gradually migrating new updates from the young level to the largest level using only bulk reads and writes (i.e., minimizing expensive seeks). 那level_1及以上要怎么限制Compact输入文件数量或大小呢,LevelDB在产生某个level_n (n>0)的table文件时,除了限制table大小,还会看与level_n+1相交的table文件数据量是否超过了其自身的10倍大小,如果超过了则切换新table输出,主要目的就是防止level_n的某个table在与level_n+1层做合并时产生太多的输入IO.

官方给了个单次Compact实例的IO开销的定量分析:假设memtable涨到1M就落地(即level_0 table大小约为1M),Compact产生新table时文件大小阈值是2M,level_0最多4个文件,则能推出,level_0做Compact时最多有大约4M+10M输入文件(level_1一共10M),总IO约为输入14M+输出14M=28M. level_k(k>0)做Compact时最多有1+12个输入文件(考虑到边界情况,假设level_k+1中最多12个相交文件),每个文件2M,总IO约为26M+26M,再假设磁盘100M/s,则0.5秒内可以完成一次Compaction. 可以看到这些策略可以有效限制单轮Compact的IO开销,但除level_0外其他level的文件数量可能很大,会对文件系统可能造成压力. 最大的level_k理论上最高至少可以达到 (10^k)/2 个文件. 当k=7时,LevelDB理论上能容纳大约10T数据,但实际应用中一般100G以下比较合适.

个人认为多层设计本质上也是一种空间换时间的策略:通过一定的数据冗余换来了Compact操作的IO性能提升(smaller input).

工程实现中有不少问题需要考虑,比如会不会达到一定数据量后多个level同时集中触发Compaction,从而造成系统压力和性能问题,如何分散压力. LevelBD的做法是会在普通Get或遍历操作时做一些探测和统计,如果发现某个level_n的table和level_n+1有数据交集,会考虑在某个适当的时机尝试将其合并,而不用始终等到阈值触发。但如果有太多不必要的Compaction也会影响性能,所以具体时机的把握值得商榷;又比如元数据要如何组织使得版本更新起来尽量简单,如何保证用户正在使用的Snapshot不被清理掉等等.

至此LevelDB的存储模型基本完整了,这里再结合读写过程做一个总体描述:
a) DB数据分为memtable和持久化数据两部分.
b) 持久化数据的基本管理单元是table文件,一个table文件是按key排序的kv记录序列,table只能被整体创建或删除,不能修改.
c) 每个table唯一属于某个level_n;level_0以上table之间数据不相交,level越低数据越新.
d) Compaction: 周期性地将level_n的某个table与level_n+1中有数据交集的table合并为若干新level_n+1 table.
e) 读key:按memtable->level_0->level_1->...level_k的顺序查找,level_0可能需要读多个table.
f) 写key:新数据同时写入log文件和memtable,memtable落地后对应log可以删除.
g) 遍历:遍历读取memtable、level_0、...level_k的有序记录做归并输出.
h) Recover:DB启动时先将log数据恢复到memtable,跳过受损的记录.

四、Immutable Is Good
有一个核心的点值得单独一提,即从上述描述可以看到,table文件是不可修改的(immutable),类似函数式编程中不产生副作用的道理,这种格式在leveldb中简化了很多设计:并发访问友好,不存在写锁;不存在Cache更新和一致性问题;索引和BloomFilter等元数据可随文件一起创建和销毁,即直接存在文件里,不用加载时动态计算,不用维护更新;table仅作为memtable落地和Compaction的结果原子性地产生,MVCC式的处理允许读、写、Compact同时进行.后面会详细说明

这种immutable sorted map(kv pair)格式在BigTable中有一个专门的名字即sstable,在Google使用广泛.

五、LevelDB设计优雅,结构清晰,代细节处理得很好,值得一读.
后几篇将分别选几个点从设计和实现的角度简单记录下阅读体会.

LevelDB剖析(1):Basic Idea》上有2条评论

发表评论

电子邮件地址不会被公开。