leveldbrocksdb

单机基于 SSTable。适用于与 SSD 一起使用。整体 https://segmentfault.com/a/11…。
mysql 写入千条 /s，读万应该没问题。redis 写入 万条 /s 7M/s(k+v 700bytes，双核)读是写入的 1.4 倍 mem 3gb 2 核。这两个网上搜的，不保证正确，就看个大概吧。
SSD 上 rocksdb 随机和顺序的性能差不多，写要比读性能稍好。随机读写 1.7 万条 /s 14M/s（32 核）。batch_write/read 下 SSD 单线程会耗 8 倍。普通 write 只快 1.2 倍。
没有再一个机器上的对比。rocksdb 在用 SSD 和 batch-write/read 下的读写性能还是可以的。

第一章 levelDb

架构图

读取过程

数据的读取是按照 MemTable、Immutable MemTable 以及不同层级的 SSTable 的顺序进行的，前两者都是在内存中，后面不同层级的 SSTable 都是以 *.ldb 文件的形式持久存储在磁盘上

写入过程

1. 调用 MakeRoomForWrite 方法为即将进行的写入提供足够的空间；
在这个过程中，由于 memtable 中空间的不足可能会冻结当前的 memtable，发生 Minor Compaction 并创建一个新的 MemTable 对象；不可变 imm 去 minor C, 新的 memtable 继续接收写
在某些条件满足时，也可能发生 Major Compaction，对数据库中的 SSTable 进行压缩；
2. 通过 AddRecord 方法向日志中追加一条写操作的记录；
3. 再向日志成功写入记录后，我们使用 InsertInto 直接插入 memtable 中，内存格式为跳表，完成整个写操作的流程；

writebatch 并发控制

全局的 sequence(memcache 中记录)。读写事务都申请 writebatch。
这里即使是并发，也是选择 leader(cas+memory_order)将多个 writebatch 合并一起写入 WAL，再依次写入 memtable 再提交。

ACID

版本控制
内存中
在每次读的时候用 userkey+sequence 生成。这个 sequence 面膜人呢使用当前最新的 sequnce。保证整个读过程都读到当前版本的，在写入时，写入成功后才更新 sequnce 保证最新写入的 sequnce+ 1 的内存不会被旧的读取读到。
Compaction 过程中
被引用的 version 不会删除。被 version 引用的 file 也不会删除
每次获取 current versionn 的内容。更新后才会更改 current 的位置

memtable

频繁插入查询，没有删除。需要无写状态下的遍历（dump 过程）=》跳表
日志文件 4M 后变 sstable.memtable 是日志的副本

sstable

sstable（默认 7 个）【上层 0，下层 7】
filemetadata: refs 文件被不同 version 引用次数,allowed_Seeks 允许查找次数,number 文件序号,file_size，smallest,largest
除了 level0 是内存满直接落盘 key 范围会有重叠，下层都是经过合并的，没重叠，可以直接通过 filemetadata 定位在一个文件后二分查找。level0 会查找多个文件。
上层倒到容量后触发向下一层归并，每一层数据量是比其上一层成倍增长

sstable=>blocks=>entrys

DataBlock Key := UserKey + SequenceNum + Type
Type := kDelete or kValue
Meta Block：比较特殊的 Block，用来存储元信息，目前 LevelDB 使用的仅有对布隆过滤器的存储。写入 Data Block 的数据会同时更新对应 Meta Block 中的过滤器。读取数据时也会首先经过布隆过滤器过滤.
bloom 过滤器：key 散列到 hash% 过滤器容量，1 代表有 0 代表无，判断 key 在容量范围内是否存在。因为 hash 冲突有一定存在但并不存在的错误率
哈希函数的个数 k；=>double-hashing i 从 0 -k, gi(x) = h1(x) + ih2(x) + i^2 mod m,
布隆过滤器位数组的容量 m;
布隆过滤器插入的数据数量 n;
datablock:

有相同的 Prefix 的特点来减少存储数据量, 减少了数据存储，但同时也引入一个风险，如果最开头的 Entry 数据损坏，其后的所有 Entry 都将无法恢复。为了降低这个风险，leveldb 引入了重启点，每隔固定条数 Entry 会强制加入一个重启点，这个位置的 Entry 会完整的记录自己的 Key，并将其 shared 值设置为 0。同时，Block 会将这些重启点的偏移量及个数记录在所有 Entry 后边的 Tailer 中。

合并

Minor C 内存超过限制 单独后台线 入 level0
Major C level0 的 SST 个数超过限制，其他层 SST 文件总大小 /allowed_Seeks 次数。单独后台线程（文件合并后还是大是否会拆分）
当级别 L 的大小超过其限制时，我们在后台线程中压缩它。压缩从级别 L 中拾取文件，从下一级别 L + 1 中选择所有重叠文件。请注意，如果 level- L 文件仅与 level-（L + 1）文件的一部分重叠，则 level-（L + 1）处的整个文件将用作压缩的输入，并在压缩后将被丢弃。除此之外：因为 level- 0 是特殊的（其中的文件可能相互重叠），我们特别处理从 0 级到 1 级的压缩：0 级压缩可能会选择多个 0 级文件，以防其中一些文件相互重叠。
压缩合并拾取文件的内容以生成一系列级别（L + 1）文件。在当前输出文件达到目标文件大小（2MB）后，我们切换到生成新的级别（L + 1）文件。当当前输出文件的键范围增长到足以重叠超过十个级别（L + 2）文件时，我们也会切换到新的输出文件。最后一条规则确保稍后压缩级别（L + 1）文件不会从级别（L + 2）中获取太多数据。
旧文件将被丢弃，新文件将添加到服务状态。
特定级别的压缩在密钥空间中循环。更详细地说，对于每个级别 L，我们记住级别 L 处的最后一次压缩的结束键。级别 L 的下一个压缩将选择在该键之后开始的第一个文件（如果存在则包围到密钥空间的开头）没有这样的文件）。

wal

32K。内存写入完成时，直接将缓冲区 fflush 到磁盘
日志的类型 first full, middle,last 若发现损坏的块直接跳过直到下一个 first 或者 full. 重做时日志部分内容会嵌入到另一个日志文件中

记录
keysize | key | sequnce_number | type |value_size |value
type 为插入或删除。排序按照 key+sequence_number 作为新的 key

其他元信息文件

记录 LogNumber，Sequence，下一个 SST 文件编号等状态信息；
维护 SST 文件索引信息及层次信息，为整个 LevelDB 的读、写、Compaction 提供数据结构支持；
记录 Compaction 相关信息，使得 Compaction 过程能在需要的时候被触发；配置大小
以版本的方式维护元信息，使得 Leveldb 内部或外部用户可以以快照的方式使用文件和数据。
负责元信息数据的持久化，使得整个库可以从进程重启或机器宕机中恢复到正确的状态；
versionset 链表
每个 version 引用的 file（指向 filemetadata 的二维指针（每层包含哪些 file）），如 LogNumber，Sequence，下一个 SST 文件编号的状态信息
versionset 链表
每个 version 引用的 file（指向 filemetadata 的二维指针（每层包含哪些 file）），如 LogNumber，Sequence，下一个 SST 文件编号的状态信息

每个 version 之间的差异 versionedit。每次计算 versionedit, 落盘 Manifest 文件（会存 version0 和每次变更），用 versionedit 构建新的 version。manifest 文件会有多个，current 文件记录当前 manifest 文件，使启动变快
Manifest 文件是 versionset 的物理结构。中记录 SST 文件在不同 Level 的分布，单个 SST 文件的最大最小 key，以及其他一些 LevelDB 需要的元信息。

分布式实现：
google 的 bigtable 是 chubby(分布式锁)+ 单机 lebeldb

第二章 rocksdb

增加功能

range
merge（就是为了 add 这种多个 rocksdb 操作）
工具解析 sst
压缩算法除了 level 的 snappy 还有 zlib,bzip2（同时支持多文件）
支持增量备份和全量备份
支持单进程中启动多个实例
可以有多个 memtable，解决 put 和 compact 的速度差异瓶颈。memcache 中跳表（只有这个支持并发，），hash+skiplist,hash+list 等结构
这里讲了 memtable 并发写入的过程，利用了 InlineSkipList，它是支持多读多写的，节点插入的时候会使用 每层 CAS 判断节点的 next 域是否发生了改变，这个 CAS 操作使用默认的 memory_order_seq_cst。
http://mysql.taobao.org/month…
源码分析
https://youjiali1995.github.i…

合并

通用合并（有时亦称作 tiered）与 leveled 合并（rocksdb 的默认方式）。它们的最主要区别在于频度，后者会更积极的合并小的 sorted run 到大的，而前者更倾向于等到两者大小相当后再合并。遵循的一个规则是“合并结果放到可能最高的 level”。是否触发合并是依据设置的空间比例参数。
size amplification ratio = (size(R1) + size(R2) + … size(Rn-1)) / size(Rn)
低写入放大（合并次数少），高读放个大（扫描文件多），高临时空间占用（合并文件多）

压缩算法

RocksDB 典型的做法是 Level 0- 2 不压缩，最后一层使用 zlib(慢，压缩比很高)，而其它各层采用 snappy

复制

备份 ID，增量。CreateNewBackup，GetBackupInfo，VerifyBackup，恢复：BackupEngineReadOnly::RestoreDBFromBackup()是备份 ID。备份引擎 open 时会扫描所有备份耗时间，常开启或删除文件。
步骤：

禁用文件删除
获取实时文件（包括表文件，当前，选项和清单文件）。将实时文件复制到备份目录。由于表文件是不可变的并且文件名是唯一的，因此我们不会复制备份目录中已存在的表文件。例如，如果 00050.sst 已备份并 GetLiveFiles()返回文件 00050.sst，则不会将该文件复制到备份目录。但是，无论是否需要复制文件，都会计算所有文件的校验和。如果文件已经存在，则将计算的校验和与先前计算的校验和进行比较，以确保备份之间没有发生任何疯狂。如果检测到不匹配，则中止备份并将系统恢复到之前的状态 BackupEngine::CreateNewBackup()叫做。需要注意的一点是，备份中止可能意味着来自备份目录中的文件或当前数据库中相应的实时文件的损坏。选项，清单和当前文件始终复制到专用目录，因为它们不是不可变的。如果 flush_before_backup 设置为 false，我们还需要将日志文件复制到备份目录。我们 GetSortedWalFiles()将所有实时文件调用并复制到备份目录。重新启用文件删除

复制：
然后从中检索文件列表 GetLiveFiles()，复制它们，最后调用 EnableFileDeletion()。
RocksDB 支持一个 API PutLogData，应用程序可以使用该 API 来为每个 Put 添加元数据。此元数据仅存储在事务日志中，不存储在数据文件中。PutLogData 可以通过 GetUpdatesSinceAPI 检索插入的元数据。
日志文件时，它将移动到存档目录。存档目录存在的原因是因为落后的复制流可能需要从过去的日志文件中检索事务
或者调 checkpoint 保存

iter

更多：
SST 大时顶级索引：https://github.com/facebook/r…
两阶段提交：https://github.com/facebook/r…