LevelDB实现解析

LevelDB是Google开发的一个key-value存储，其已经作为存储引擎被Riak和Kyoto Tycoon所支持( 这里和 这里)，在国内 淘宝的 Tair开源key-value存储也已经将LevelDB作为其持久化存储引擎，并部署在线上使用. 下面PDF就是 淘宝核心系统研发团队的那岩总结的LevelDB内部实现的长文.

Google宣布在BSD许可证下开源其键值存储引擎LevelDB. LevelDB C++库可用于多种不同环境，如被浏览器用于存储最近访问的网页缓存，或者被操作系统使用去储存安装的软件包和依赖包清单，或被应用程序用于存储用户设置. Google称，即将发布的新版Chrome浏览器，就包含了基于LevelDB的IndexedDB HTML5 API实现.

  作者：Jeff Dean, Sanjay Ghemawat. 原文：http://leveldb.googlecode.com/svn/trunk/doc/impl.html. 译者：phylips@bmy 2011-8-17. 出处：http://duanple.blog.163.com/blog/static/7097176720112643946178/ .

本文是一篇转载的翻译文章，翻译对象是LevelDB的官方文档中实现一章，主要描述了LevelDB内部的数据结构，文件结构及相关的存储，压缩恢复等功能的实现过程，看完后你就能知道，LevelDB为什么会叫这个名字了. 作者：Jeff Dean, Sanjay Ghemawat. 原文：leveldb.googlecode.com.

>>> db.Get("2") '222' >>> db.Get("5") '' >>> db.Write(batch) >>> db.Get("5") 'hello world 5' >>> db.Get("2") 'hello world 2' >>> iter = leveldb.Iterator(db) Iterator_init executed.

下面PPT作者是@淘宝解伦，PPT中对LevelDB的特点、设计思想及实现原理都有所涵盖，是一篇不错的LevelDB入门教材. 对LevelDB感兴趣的同学可以看看. LevelDB中的Skip List(跳跃表）. 一个NoSQL与MongoDB的介绍PPT. RethinkDB 与 TokuDB 调研测试报告.

LevelDb日知录之一：LevelDb 101. 说起LevelDb也许您不清楚，但是如果作为IT工程师，不知道下面两位大神级别的工程师，那您的领导估计会Hold不住了：Jeff Dean和Sanjay Ghemawat. 这两位是Google公司重量级的工程师，为数甚少的Google Fellow之二.

为了持久化, 必须写硬盘.. 为了快速写入硬盘, 必须采用追加方式顺序写到 log 文件. 这导致 log 文件中的数据是无序的.. 为了快速从硬盘中读取数据, 基于查找算法和局部性原理考虑, 必须将数据排序组织到 sst 文件中.. 多个 sst 文件而不是单个. 为了快速的插入数据到 sst 文件中, 必须使用多个 sst 文件, 每个 sst 文件只保存一定范围的数据.

    leveldb的实现类似于Bigtable中的一个tablet（Google），只不过底层的文件组织形式稍有不同.     每个Database有一系列本地文件组成，这些文件有不同的类型：.     log文件存储了一序列的最近更新操作，每个更新（update）都会append到当前log文件的尾部，当log文件的尺寸达到预设定的大小时，将会把此log文件转换成一个sorted table（.sst）文件，然后滚动创建一个新的log文件来保存此后的updates操作.