原文

leveldb

如果说Protocol Buffer是谷歌独立数据记录的通用语言 ,那么有序字符串表(SSTable,Sorted String Table)则是用于存储,处理和数据集交换的最流行​​的数据输出格式。正如它的名字本身,SSTable是有效存储大量键-值对的简单抽象,对高吞吐量顺序读/写进行了优化

不幸的是,SSTable名称本身被业界重载,指代的内容远远超出有序表的概念,这可能与简单有效数据结构的定义产生歧义。让我们仔细看看SSTable的内部结构以及LevelDB是怎样使用SSTable的。

SSTable:有序字符串表

假设我们有一大批数据(GB或TB量级)需要处理,处理过程可能分为好几个步骤,每个步骤必须由不同的二进制文件(程序)来处理 - 或者可以假设我们正在执行一系列的map-reduce任务!由于输入数据量很大,读取和写入数据的效率决定了运行时间。因此,不会使用随机读写,而是对数据进行流式读取,一旦处理完成,再通过流式写入将数据刷新到磁盘。通过这种方式,我们可以分摊磁盘I / O成本 。不需要磁盘寻道,直接连续的向前写入。 sstable

有序字符串表(Sorted String Table)是包含一组任意有序键 - 值对的文件,可以很好的处理重复键,不需要额外的空间来填充(padding)键或值,并且键值可以是任意的东西。顺序的读取整个文件,就可以获得一个有序的索引。如果文件非常大,可以在前面追加或创建独立的key:offset索引来加速访问。这就是SSTable,一个非常简单却非常有用的交换大量有序数据片段的方式。

SSTable和Bigtable:快速随机访问?

SSTable刷新到磁盘上后,SSTable就不再可变,因为插入或删除需要大量的I / O来重写文件。也就是说对于静态索引,SSTable是一个很好的解决方案:在索引中读取总是在一个磁盘上寻道,还可以直接将整个文件memmap到内存中。随机读取是简单和快速的。

随机写操作都是非常困难和昂贵的,除非整个表在内存中,在这种情况下只需要简单的指针操作。这就是 谷歌的BigTable着手解决的问题:快速读/写访问SSTable支撑的PB级的数据。我们不禁想问,谷歌是如何做到的呢?

SSTables和日志结构合并树

我们需要SSTables提供的快速读取,同时我们也希望支持快速的随机写入。实际上,我们已经有了达成此目标所需的所有条件:如果SSTable在内存中(让我们把它称为MemTable )随机写入是很快速的,如果表是不可变的,那么磁盘上的SSTable读取也很快速。现在,让我们来介绍以下一组约定:

enter image description here

  1. 磁盘上的SSTable索引总是被加载到内存中
  2. 所有的写操作直接更新MemTable索引
  3. 读操作先在MemTable索引中查找,然后再在SSTable索引中查找
  4. 每隔一段时间,MemTable将刷新到磁盘生成SSTable
  5. 每隔一段时间,磁盘上的SSTable会合并到一起

这组约定做了什么呢?写总是在内存中完成,因此总是很快。MemTable一旦达到一定大小后,它被刷新到磁盘上形成不变的SSTable 。不过,我们需要维护所有的SSTable在内存中的索引,也就是说,对每次读操作,我们可以先在MemTable中查找,然后在SSTable索引中顺序查找需要的数据。这就是我们刚刚改造的 日志结构合并树(LSM树 )(由Patrick O'Neil发明),这也正是BigTable 子表分片背后的机制。

LSM 和 SSTables:更新,删除和维护

这种“LSM”的架构提供了一些有趣的行为: 写入操作总是很快速,并且不用考虑数据集的大小(追加); 随机读取或者通过读取内存或者通过一次快速的磁盘寻道来完成 。然而,该如何处理更新和删除操作呢?

一旦SSTable被写入磁盘,它就不再可变,因此,更新和删除操作不能通过操作SSTable来实现。更新操作通过简单的向MemTable存储一个更新后(相对于旧值)的值,删除操作则是向记录末尾添加一个“墓碑”(tombstone)标记。由于我们会按序检查索引,后续的读操作会获取到更新的或有墓碑标记的记录,而不会获取到旧值!最后,磁盘有数百个SSTables可不是一个好主意,因此我们将 定期运行一个程序合并磁盘上SSTables,在此情况下,更新和删除记录会覆盖并删除旧的数据

SSTables和LevelDB

使用附加MemTable的SSTable,并应用上面的处理约定,你就可以得到对某类负载工作很好的数据库引擎。事实上,谷歌的BigTable,Hadoop的HBase,Cassandra 以及其他一些数据库都在使用这个架构或这个架构的变种。

像许多其他想法一样,SSTable表面上看起来简单,实现细节则麻烦得多。值得庆幸的是, SSTable和谷歌的BigTable基础设施贡献者杰夫·迪恩(Jeff Dean)桑杰格玛沃特(Sanjay Ghemawat)在去年的早些时候发布了LevelDB ,LevelDB基本上是前面描述架构的精确复制:

  • SSTable 在背后处理,MemTable处理写操作
  • 键和值都是任意的字节数组
  • 支持PUT,GET,删除操作
  • 支持向前和向后迭代数据
  • 内置Snappy压缩

LevelDB设计作为WebKit中的索引DB引擎(也就是在浏览器中嵌入),它很容易被嵌入到浏览器中 , 很快速 ,而且最重要的是,LevelDB处理了所有SSTable和MemTable刷新,合并以及其他琐碎细节。

使用LevelDB:Ruby

LevelDB是一个库,而不是一个独立的服务器或服务 - 当然你可以很容易的用LevelDB实现出一个服务程序来。首先,抓住你最喜欢的语言绑定( ruby ),来看看我们能做些什么:

require 'leveldb' # gem install leveldb-ruby

db = LevelDB::DB.new "/tmp/db"
db.put "b", "bar"
db.put "a", "foo"
db.put "c", "baz"

puts db.get "a" # => foo

db.each do |k,v|
   p [k,v] # => ["a", "foo"], ["b", "bar"], ["c", "baz"]
end

db.to_a # => [["a", "foo"], ["b", "bar"], ["c", "baz"]]

仅仅几行代码就可以实现存储键值,检索键值和以及按范围扫描。LevelDB就是这样简单易用,LevelDB为我们维护MemTables,处理SSTables合并以及其他一些琐事。

WebKit中的LevelDB以及其他内容

SSTable是一个非常简单的和有用的数据结构 - 特别适合作为大容量输入/输出格式。然而,有序性和不可更改性使得SSTable快速高效的同时也暴露了其局限性。为了解决这个问题,我们介绍了MemTable的想法,以及用于管理SSTable的一组“日志结构”处理约定。

一如既往,规则总是很简单,而实现细节总会复杂一些,这就是为什么LevelDB是开源数据库引擎堆栈的一个很好的补充。你可能很快就会发现,LevelDB嵌入在您的浏览器,您的手机,以及许多其他地方 。获取LevelDB源码 ,查看LevelDB文档 ,并在需要的时候使用它。