LevelDB 的原理

LevelDB是Google传奇工程师Jeff Dean和Sanjay Ghemawat开源的KV存储引擎。国内各大互联网公司都有基于leveldb 开发的缓存系统,我们今天就简单介绍下这个存储引擎为什么会受大家青睐,

原理:LevelDB的数据是存储在磁盘上的,采用LSM-Tree的结构实现。LSM-Tree将磁盘的随机写转化为顺序写,从而大大提高了写速度。

为了做到这一点LSM-Tree的思路是将索引树结构拆成一大一小两颗树,较小的一个常驻内存,较大的一个持久化到磁盘,他们共同维护一个有序的key空间。写入操作会首先操作内存中的树,随着内存中树的不断变大,会触发与磁盘中树的归并操作,而归并操作本身仅有顺序写。随着数据的不断写入,磁盘中的树会不断膨胀,为了避免每次参与归并操作的数据量过大,以及优化读操作的考虑,LevelDB将磁盘中的数据又拆分成多层,每一层的数据达到一定容量后会触发向下一层的归并操作,每一层的数据量比其上一层成倍增长。这也就是LevelDB的名称来源

---------------------

存储模型内存数据的Memtable,分层数据存储的SST文件,版本控制的Manifest、Current文件,以及写Memtable前的WAL。

WAL: Write-Ahead Logging预写日志系统

数据库中一种高效的日志算法,对于非内存数据库而言,磁盘I/O操作是数据库效率的一大瓶颈。在相同的数据量下,采用WAL日志的数据库系统在事务提交时,磁盘写操作只有传统的回滚日志的一半左右,大大提高了数据库磁盘I/O操作的效率,从而提高了数据库的性能。

---------------------

可以类比HBase的WAL机制,它提供了一种高并发、持久化的日志保存与回放机制。每一个业务数据的写入操作(PUT / DELETE)执行前,都会记账在WAL中。如果出现HBase服务器宕机,则可以从WAL中回放执行之前没有完成的操作。今天暂不讨论WAL机制。下图是leveldb 的原理图:

Memtable:

对应Leveldb中的内存数据,LevelDB的写入操作会直接将数据写入到Memtable后返回。读取操作又会首先尝试从Memtable中进行查询,允许写入和读取。当Memtable写入的数据占用内存到达指定数量,则自动转换为Immutable Memtable,等待Dump到磁盘中,系统会自动生成新的Memtable供写操作写入新数据。

Log文件:

当应用写入一条Key:Value记录的时候,LevelDb会先往log文件里写入,成功后将记录插进Memtable中,这样基本就算完成了写入操作,Log文件在系统中的作用主要是用于系统崩溃恢复而不丢失数据,假如没有Log文件,因为写入的记录刚开始是保存在内存中的,此时如果系统崩溃,内存中的数据还没有来得及Dump到磁盘,所以会丢失数据(Redis就存在这个问题,所以要开启持久化,例如AOF)。

---------------------

Immutable Memtable

当Memtable插入的数据占用内存到了一个界限后,需要将内存的记录导出到外存文件中,LevleDb会生成新的Log文件和Memtable,Memtable会变为Immutable,为之后向SST文件的归并做准备。顾名思义,Immutable Mumtable不再接受用户写入,只能读不能写入或者删除,同时会有新的Log文件和Memtable生成,LevelDb后台调度会将Immutable Memtable的数据导出到磁盘,形成一个新的SSTable文件。

---------------------

SST文件

SSTable就是由内存中的数据不断导出并进行Compaction操作(压缩操作,下文会讲到)后形成的,而且SSTable的所有文件是一种层级结构,第一层为Level 0,第二层为Level 1,依次类推,层级逐渐增高,这也是为何称之为LevelDb的原因。

磁盘数据存储文件。分为Level 0到Level N多层,每一层包含多个SST文件;单个SST文件容量随层次增加成倍增长;文件内数据有序;其中Level 0的SST文件由Immutable直接Dump产生,其他Level的SST文件由其上一层的文件和本层文件归并产生;SST文件在归并过程中顺序写生成,生成后仅可能在之后的归并中被删除,而不会有任何的修改操作。

---------------------

Manifest文件

Manifest文件中记录SST文件在不同Level的分布,单个SST文件的最大最小key,以及其他一些LevelDB需要的元信息。

SSTable中的某个文件属于特定层级,而且其存储的记录是key有序的,那么必然有文件中的最小key和最大key,这是非常重要的信息,LevelDb应该记下这些信息。Manifest就是干这个的

---------------------

Current文件

从上面的介绍可以看出,LevelDB启动时的首要任务就是找到当前的Manifest,而Manifest可能有多个。Current文件简单的记录了当前Manifest的文件名,从而让这个过程变得非常简单。

Current文件的内容只有一个信息,就是记载当前的manifest文件名。因为在LevleDb的运行过程中,随着Compaction的进行,SSTable文件会发生变化,会有新的文件产生,老的文件被废弃,Manifest也会跟着反映这种变化,此时往往会新生成Manifest文件来记载这种变化,而Current则用来指出哪个Manifest文件才是我们关心的那个Manifest文件。

---------------------

接下来看下这个存储引擎有哪些优缺点:

优点:

1、key和value都是任意长度的字节数组;

2、entry(即一条K-V记录)默认是按照key的字典顺序存储的,当然开发者也可以重载这个排序函数;

3、提供的基本操作接口:Put()、Delete()、Get()、Batch();

4、支持批量操作以原子操作进行;

5、可以创建数据全景的snapshot(快照),并允许在快照中查找数据;

6、可以通过前向(或后向)迭代器遍历数据(迭代器会隐含的创建一个snapshot);

7、自动使用Snappy压缩数据;

8、可移植性;

缺点:

1、非关系型数据模型(NoSQL),不支持sql语句,也不支持索引;

2、一次只允许一个进程访问一个特定的数据库;

3、没有内置的C/S架构,但开发者可以使用LevelDB库自己封装一个server;

---------------------

读写过程:

写操作流程:

1、顺序写入磁盘log文件;

2、写入内存memtable(采用skiplist结构实现);

3、写入磁盘SST文件(sorted string table files),这步是数据归档的过程(永久化存储);

读操作流程:

1、在内存中依次查找memtable、immutable memtable;

2、如果配置了cache,查找cache;

3、根据mainfest索引文件,在磁盘中查找SST文件;

综上,想要深入了解原理,还需熟读源码,严格意义上leveldb并不算是个数据库,它只是kv存储系统,别的系统可以用它来做存储引擎。 通过动态链接或者静态链接的方式集成进来如果你写程序,需要存放数据,你可以用leveldb来存。然后编译你的代码的时候将leveldb的静态库或者动态库引进来就行,facebook将leveldb做了很多扩展,然后用作了mysql的一个存储引擎。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181120G12SVP00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

同媒体快讯

扫码关注云+社区

领取腾讯云代金券