20200407 NoSQL笔记（六）

第六章 LevelDb——Google的Key-Value数据库
一、 LevelDb简介

1. LevelDb是Google开发的开源键值单机数据库

1. 具有很高的随机写，顺序读/写性能，但是随机读的性能很一般
2. 适用于写很多，查询少的场景

2. LevelDb特点

1. key和value都是任意长度的字节数组；
2. entry（即一条K-V记录）默认是按照key的字典顺序存储，开发者也可重载这个排序函数；
3. 提供的基本操作接口：Put(Key, Value)、Delete(Key)、Get(Key)、Batch()；
4. 支持批量操作以原子操作进行；
5. 可以创建数据全景的snapshot(快照)，并允许在快照中查找数据；
6. 可以通过前向（或后向）迭代器遍历数据（迭代器会隐含的创建一个snapshot）；
7. 自动使用Snappy压缩数据；
8. 可移植性

3. LevelDb限制

1. 非关系型数据模型（NoSQL）, 不支持SQL语句；
2. 一次只允许一个进程访问一个特定的数据库；
3. 没有内置的C/S架构，但开发者可以使用LevelDB库封装一个server

二、 LevelDb的静态部分

1. MemTable和SSTable

1. MemTable插入的数据占用内存到了一定界限之后，将内存记录压缩导入磁盘中SSTable;
2. MemTable允许写入和读取；
3. Immutable MemTable只允许读取，不允许写入；
4. LevelDB的MemTable类只是一个接口类，真正的操作是通过SkipList实现；
5. SkipList是一种随机化的算法

2. SSTable文件

1. SSTable中的文件按照Key字典序排序，具有层级结构；

2. SSTable中Level 0层级内的.sst文件具有特殊性；
   

3. .sst文件的逻辑布局：划分为数据存储区和数据管理区；
   a) 数据存储区存放键值数据；
   b) 数据管理区提供索引指针等管理数据
   

4. Block：
   a) 每个Block分为三个部分：数据存储区，数据存储类型，数据校验码
   b) Block内容与Block尾部；Block尾部的“重启点”（Restart Point）（相邻的两条记录很可能Key部分存在重叠）
   
   

5. Index：
   a) 数据索引区的每条记录是对某个Data Block建立的索引信息；
   b) 每条索引信息包含三个内容：
    第一个字段记载大于等于数据块i中最大key值，小于数据块i+1中最小Key值;
    第二个字段指出数据块i在.sst文件中的起始位置；
    第三个字段指出数据块i的大小
   

6. Footer：
   a) metaindex_handle指出了metaindex block的起始位置和大小
   b) inex_handle指出了index Block的起始地址和大小；
   

3. Log文件

1. log文件主要用于系统崩溃恢复而不丢失数据；
2. LevelDb对于一个Log文件，会把它切割成以32K为单位的物理Block，每次读取的单位以一个Block作为基本读取单位；一个log文件由三个连续的32KB大小的Block构成
3. 在应用的视野里是看不到Block，应用看到的是一系列的Key: Value对；在LevelDb内部，会将一个Key: Value对看作一条记录；
4. 在每条记录的数据前增加一个记录头，用来记载一些管理信息；记录头包含三个字段：CheckSum（校验码），记录长度，类型；类型可以分为FULL，FIRST，MIDDLE，LAST
   

4. Manifest和Current文件

1. Manifest文件存储SSTable中特定层级的文件名称，属于哪个层级，存储的最小Key和最大Key，Manifest文件存储示意图如下图所示；
2. Current文件记载当前Manifest文件名
   

三、 LevelDb的动态部分

1. 写入与删除记录

1. 写入记录或者是插入操作，分为两个步骤：
   a) 记录以顺序写的方式追加到log文件的末尾；
   b) 记录插入内存中MemTable中，插入规则遵循跳表算法（SkipList）
2. 删除操作插入的是“Key：删除标记”，并不能真正的删除记录
   

2. 读取记录

1. 根据数据的新鲜度读取数据
2. Level L的信息一定比Level L+1数据要新
3. 特殊情况：
   a) 特殊情况1：Level 0中.sst文件中会存在Key重复，重复Key也会按照新鲜度排序；
   b) 特殊情况2：Key和某个Key Range包含这个Key的SSTable文件。
   c) 步骤：
    第一步：先在内存中Cache中查询是否包含这个文件的缓存记录，如果包含，从缓存中读取；
    第二步：如果不包含，则打开SSTable文件，并将这个文件的索引部分加载到内存中并放入 Cache中，这样Cache中就有了这个SSTable的缓存项；
    第三步：文件的索引部分存入内存的Cache中，LevelDB会根据索引定位到Key存储到哪个Block里面；
    第四步：找到相应的Block，返回记录的值。
   

3. 压缩操作
   压缩分为小压缩（minor）和大压缩（major）。

1. 小压缩的目的是当内存中的MemTable大小到了一定值时，将内容保存到磁盘文件中；
2. 大压缩是当某个Level下的SSTable文件数目超过一定设置值之后，LevelDB会从这个Level的SSTable中选择一个文件，将其和更高一层级的level+1的SSTable文件合并
   a) Level 0在文件选择的时候，可能会有多个文件参与大压缩；
   b) Level 选择文件压缩的顺序是字典序，即如果选择文件A压缩，那么下一个文件就是与文件A的键范围紧挨着的文件B压缩，这样每个文件都有机会和高层Level文件进行合并
   

4. 缓存

1. 读取数据两步读取磁盘：
   a) 从磁盘中将SSTable索引部分存入内存；
   b) 从磁盘中将Block内容存入内存
2. 内存中缓存分为表格缓存和数据块缓存。
   a) 表格缓存
    键：SSTatble的文件名称
    值：
    指向磁盘打开的SSTable文件的文件指针；
    指向内存中这个SSTable文件对应的Table结构指针（SSTable的索引内容以及指示数据块缓存用的cache_id）
   
   b) 数据块缓存：
    键：Cache_id，Block在文件中的起始位置block_offset
    值：Block存放的数据记录