leveldb学习

服务器构架

前端有一级缓存L1

中间有Memory Cache作为二级缓存L2

后端MySQL数据库自带三级缓存L3

Memory Cache产品,最经典的是MemoryCached。

硬盘产品,现在使用SSD硬盘来提到I/O能力。我们使用FusionIO公司的SSD硬盘。

但MemoryCached不能和SSD较好地整合。在和SSD的整合方面,leveldb是最不错的。

我们尝试leveldb和FusionIO产品的整合。

磁盘阵列

RAID: Redundant Array of Independent Disks, 磁盘阵列

分为RAID-0, RAID-1, RADI-1E, RAID-5, RAID-6, RAID-7, RAID-10, RAID-50。

RAID-0: 多个磁盘合并成一个大容量磁盘,不具有冗余。并行I/O。读写速度快。

RAID-1:互相做镜像。冗余最高,安全性最好。读取速度快。写入速度稍慢。

RAID-2: 在RAID-0的基础上加入Hamming码作为错误校验码。至少需要3台磁盘。

RAID-3:数据交错存储。数据分散在各个磁盘。

RAID-4:和RAID-3类似,不过以区块为单位分区。

RAID-5:组合RAID-0和RAID-1,使用奇偶校验信息做冗余。读取速度和RAID-0相近,写入速度较慢(由于奇偶校验信息)。

RAID-6:比RAID-5增加一个独立的奇偶校验信息块,使用不同的算法。可靠性很高,允许两块磁盘失效。写性能很差。

实际应用中RAID-5,RAID-6比较多。

MemoryCached学习

MemoryCached使用LRU(Least Recently Used)算法。

NoSQL相关理论

术语

  1. Five Minutes Rule
  2. CAP理论:
  • C:Consistency 一致性
  • A: Availability 可用性
  • P: Partition(Tolerence of network Partition) 分区容忍性(分布式)
  1. ACID
  • A: Atomic 原子性
  • C: Consistency
  • I:
  • D: D
  1. LSM Tree (Log Structurted Merge Tree, 内存中日志树)

MMAP

分区策略

  1. 一致性Hash环 DHTs
  2. 范围分区,比如Bigtable

BitTable论文学习

映射: :math: (row:string, column:string, timestamp:int64) rightarrow string

时间戳:时间逆序

API:

SSTable文件格式用来存储Bigtable数据。提供持久,有序的键值映射。

每个SSTable包含一系列 块 block,典型的块大小是64KB,可以修改配置文件改变。SSTable的末尾是block的索引。打开SSTable时会把索引载入内存。对索引进行二分查找找到目标块,然后从磁盘中读取该块。也可以把整个SSTable读入内存,这样再查找就不需磁盘I/O操作了。

Chubby

Chubby使用Paxos算法。。。

实现

主服务器, 很多节点tablet服务器, 通信。

tablet server管理一组tablets,一般有上千个tablets。tablet server管理已加载的tablets的读写请求,还负责把太大的tablet拆小。

一个Bigtable集群存储很多tables,每个table由一组tablets组成。每个tablet关联着特定行范围的所有数据。

一开始,每个表只有一个tablet,随着tablet的增大,自动分裂成多个tablets,默认每个tablet的大小上线是100-200MB。

5.1 Tablet定位

Chubby文件 -> 根tablet

根tablet在METADATA表中存储所有的tablets位置信息。METADATA表中存的第一个,当然是根tablet了。根tablet比较特殊,它永不分裂。

LevelDB综述

leveldb主要解决随机写的效率低下问题。

打开数据库初始化时,加载.sst索引数据。在内存中构建一个memtable。同时创建日志文件。以后的写操作都会确保memtable和日志文件的一致性。

写文件用Put函数实现。当进行Put操作时,不是对磁盘而是对memtable进行操作。操作成功的话会将操作追加到操作日志文件中,从而将随机写转化为顺序写。

当memtable规模超过预设值时,memtable会分成2部分。一部分对key排序,建立索引后把k/v数据和索引一并持久化存储为.sst文件。同时删除对应的日志文件内容。这叫做minor compaction。

当leveldb意外退出时,系统可以从操作日志中恢复数据,持久化到.sst文件。

读操作用Get函数实现。首先使用bloom过滤器判断是否存在该key,若存在的话,二分查找定位到所需.sst文件,将.sst文件载入内存,和memtable合并(即将操作顺序执行一遍),然后返回最终值,也就是最新值。

当.sst文件个数超过预设值时,会合并成1个.sst文件。这叫做major compaction。

数据格式分析

静态分析

数据库目录下一般有如下几类文件:

  • $version.sst文件(Sorted String Table)
  • $version.log文件(当前操作)
  • CURRENT 存放MANIFEST文件名
  • LOCK
  • LOG 存放最新的系统日志
  • LOG.old 存放日志存档
  • MANIFEST-$version MANIFEST文件

其中$version为6位整数。

$version.log的格式如下:

  • block, 不确定。

  • record,不确定。

  • checksum

    是type和data的循环校验码CRC32C。 uint32类型,4字节,文件头偏移量13字节。

  • length,uint16类型,2字节。只见到值为0的,不知道作用。

  • type,unit8类型,1字节。

表示data的类型,取值如下:

  1. 1 FULL
  2. 2 FIRST
  3. 3 MIDDLE
  4. 4 LAST
  • data 具体的k-v数据。

    在type=1时,结构为:key的长度 key的内容 value的长度 value的内容

时序演示

初始化数据库

假设有如下Python操作:

>>> import leveldb
>>> db = leveldb.LevelDB('./data')

假设当前目录下没有data子目录。leveldb会创建data目录,初始化如下文件:

-rw-r--r-- 1 amoblin amoblin   0 2011-12-09 09:52 000003.log
-rw-r--r-- 1 amoblin amoblin 16 2011-12-09 09:52 CURRENT
-rw-r--r-- 1 amoblin amoblin 0 2011-12-09 09:52 LOCK
-rw-rw-r-- 1 amoblin amoblin 53 2011-12-09 09:52 LOG
-rw-r--r-- 1 amoblin amoblin 64K 2011-12-09 09:52 MANIFEST-000002

000003.log为待写文件,后续Put,Delete等操作会将记录保存至此。

CURRENT内容为MANIFEST文件名,初始时MANIFEST版本为2,即MANIFEST-000002。为什么不是1呢?看接下来的LOG文件。

LOG文件内容如下:

2011/12/09-09:52:33.951468 b770d6c0 Delete type=3 #1

第一列是创建时间,第二列b770d6c0不知何意。Delete代表删除操作。

type=3,说明是MANIFEST文件,#1是版本号。

即删除了MANIFEST-000001文件。所以现存的是MANIFEST-000002文件。

MANIFEST-000002文件待研究。

Put数据

接着上面的交互:

>>> db.Put('cba', 'abcd')

这时操作内容被追加到000005.log文件,使其大小由0变为64KB:

-rw-r--r-- 1 amoblin amoblin 64K 2011-12-09 10:20 000005.log

查看其内容

$ od -A d -t x1 000003.log
0000000 57 c6 a2 f2 16 00 01 01 00 00 00 00 00 00 00 01
0000016 00 00 00 01 03 63 62 61 04 61 62 63 64
0000029

循环校验码从第1行倒数第3个数值00开始,到第2行第1个00为止,共4字节。

接着2字节是length,为0.

接着1字节是type,这里为1,表示接下来的data包含全部内容,并未分片。

接着是data数据,03表示key的长度,63 62 61是key的内容'cba'的ascii码。

然后是value接着2字节是length,为0.

接着1字节是type,这里为1,表示接下来的data包含全部内容,并未分片。

接着是data数据,03表示key的长度,63 62 61是key的内容'cba'的ascii码。

然后04是value的长度,61 62 63 64是value的内容'abcd'的ascii码。

再次打开数据库

如果打开当前数据库:

>>> db = leveldb.LevelDB('./data')

查看文件变化情况:

-rw-r--r-- 1 amoblin amoblin 119 2011-12-09 10:37 000005.sst
-rw-r--r-- 1 amoblin amoblin 0 2011-12-09 10:37 000006.log
-rw-r--r-- 1 amoblin amoblin 16 2011-12-09 10:37 CURRENT
-rw-r--r-- 1 amoblin amoblin 0 2011-12-09 10:37 LOCK
-rw-rw-r-- 1 amoblin amoblin 289 2011-12-09 10:37 LOG
-rw-rw-r-- 1 amoblin amoblin 53 2011-12-09 10:37 LOG.old
-rw-r--r-- 1 amoblin amoblin 64K 2011-12-09 10:37 MANIFEST-000004

CURRENT内容变为MANIFEST-000004。

LOG文件内容如下:

2011/12/09-10:37:43.285941 b770d6c0 Recovering log #3
2011/12/09-10:37:43.286160 b770d6c0 Level-0 table #5: started
2011/12/09-10:37:43.288104 b770d6c0 Level-0 table #5: 119 bytes OK
2011/12/09-10:37:43.291572 b770d6c0 Delete type=3 #2
2011/12/09-10:37:43.291636 b770d6c0 Delete type=0 #3

从系统日志可以看出,leveldb做了3件事:

  • 执行上次的操作

    我们知道,leveldb的Put,Delete操作都是顺序存放在.log文件中的。何时整理呢?就是这时。

    创建了000005.sst表,将上次的k/v数据存入。

  • 更新版本号

    整理完毕后,删除老的版本号MANIFEST-000002,生成新版本号文件MANIFEST-000004。看来没有奇数版本号。

  • 删除旧日志

    删除日志文件000003.log

新文件LOG.old存放上次的LOG文件内容。

查看000005.sst文件

$ od -A d -t x1 000005.sst
0000000 00 0b 04 63 62 61 01 01 00 00 00 00 00 00 61 62
0000016 63 64 00 00 00 00 01 00 00 00 00 e2 3a b7 8c 00
0000032 00 00 00 01 00 00 00 00 c0 f2 a1 b0 00 09 02 64
0000048 01 ff ff ff ff ff ff ff 00 1a 00 00 00 00 01 00
0000064 00 00 00 c9 e4 dd 23 1f 08 2c 16 00 00 00 00 00
0000080 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0000096 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 57
0000112 fb 80 8b 24 75 47 db
0000119

最后48字节是Footer,固定长度。其中从1f开始的40字节是索引。最后8字节是魔数。

索引不足40字节的话补0。上面的索引数据是 1f 08 2c 16。

源码学习

主入口在db.h。

打开数据库Open()

db_impl.cc文件中实现Open函数。

3个参数:options选项,数据库名字(文件夹路径),数据库指针。

DBImpl实例

新建TableCache, VersionSet。

检测数据库路径

首先根据options进行两种操作: 1. 若不存在,创建数据库目录。 #. 若存在,报错。

创建日志文件

日志文件指针为WritalbeFile*类型。根据已有日志版本创建新日志文件,返回文件句柄。

Put操作

首先将操作封装到WriteBatch中,然后将WriteBatch送给Write函数。

Delete操作

类似上述Put操作。

Write函数

将操作追加到日志文件 AddRecord ,更新内存数据。

Get操作

首先在memetable中查找,然后immutable中查找,然后其他。

退出

退出时会修改MANIFEST文件。


附:

python leveldb安装

有两个实现:py-leveldb和cpy-leveldb。

cpy-leveldb安装: 首先配置编译环境:libtool, automake,

$ cd snappy
$ ./autogen.sh
$ ./configure
$ make
$ cd ..
$ make -C leveldb
$ sudo python setup.py build
tagged by
comments powered by Disqus