rocksdb是facebook的项目，目的是开发一套能在服务器压力下，真正发挥高速存储硬件性能的高效数据库系统；使用c 实现；
是嵌入式数据库kv数据库；不提供网络服务，只提供数据持久化的方案。
rocksdb是基于leveldb实现的，原始代码是从leveldb 1.5上fork出来的；
分布式三篇著名的论文，源自于google：
- gfs, 分布式文件存储；
- bigtable，分布式kv存储；
- mapreduce，大数据处理。
leveldb的作者就是bigtable的作者。
主要解决写多读少的问题，牺牲读性能来加速写性能；
mysql innodb b 树，解决了读多写少的问题；
rocksdb是基于lsm-tree(log structure merge-tree)实现的；
利用lsm-tree来提升写性能；
主要思想是利用磁盘顺序io来提升写性能；lsm-tree并不是tree数据结构，仅仅是一种存储结构；lsm-tree是为了写多读少(对读的性能实时性要求相对较低)的场景而提出的ag真人游戏的解决方案；如日志系统、海量数据存储、数据分析等。
以下问题需要考虑：
- 磁盘顺序写，会记录同一个key的多次写操作，存在数据冗余，怎么解决数据冗余的问题？
- 怎么提高读性能？
- 数据肯定是先写到缓存里面的，缓存使用什么样的数据结构？
- 缓存中的数据通过什么样的策略刷到磁盘中？
- 怎么保证缓存和磁盘中数据的一致性？
memtable
memtable是一个内存数据结构，它保存了落盘到sst文件前的数据；写入数据的时候总是先将数据写入到memtable，读取的时候也是先查询memtable；一旦一个memtable被写满，它会变为immutable memtable，即只读的memtable；然后会创建一块新的memtable来提供写入操作；immutable memtable将异步落盘的sst文件中，之后该memtable将会被删除。
memtable默认使用的数据结构是skiplist；
immutable memtable的两个作用？
- 用来落盘
- 提高并发读写性能
memtable中为什么使用skiplist？
缓存中应该使用什么数据结构来存储？
有序结构，并且缓存中没有冗余数据
为什么不使用rbtree？
- 红黑树查找下一个节点的复杂度是o(log2n);skiplist查找一个节点是的时间复杂度是o(1); rocksdb需要实现iterator功能，需要进行遍历，skiplist更加合适；
- 并发读写，skiplist锁粒度比rbtree小；skiplist锁单个节点，rbtree锁整个红黑树。
rbtree与skiplist使用场景比较
- 定时器，查找最小的节点; rbtree时间复杂度o(log2n), skiplist时间复杂度o(1);
- nginx slab使用红黑树，能不能使用skiplist？最好不要用skiplist，因为共享内存一开始要分配固定大小内存，skiplist节点大小不是固定的，节点层级不确定，有冗余数据；
skiplist加锁位置：
- max_height; 需要对它进行并发读写；增删改查，第一步都需要先进行查找，先在最高层进行查找；新增节点，生成的随机高度，有可能大于max_height；
- 对node加锁；
落盘策略
- 定时刷新
- 阈值刷新
wal(write ahead log)
mysql中，redo log 实现wal，写前日志；用来恢复数据，异步刷盘；rocksdb也有wal日志；在出现宕机的时候，wal日志可以用于恢复memtable的数据；当memtable中的数据落盘到sst文件后，才会删除对应的wal日志。
ss table(sorted string table)
每个immutable memtable都会落盘为一个ss table文件；
l0层可能会有重复数据，会有数据冗余，不利于快速查找；文件间无序，文件内部有序；
l1 ~ ln 层会对重复数据进行合并，思想与时间轮算法一致；根据数据的冷热程度进行分层；
l1 ~ ln 每层数据没有重复，跨层可能有重复；文件间是有序的，同一层的每个文件，key的范围不同；
磁盘数据读性能的提升
blockcache
rocksdb在内存中缓存数据，以提高读性能；
rocksdb有两种实现方式，lrucache，clockcache；lrucache读写都需要加锁；clockcache写加锁，读不加锁；nginx定时器使用clockcache，32个操作槽位，提升并发性能；
布隆过滤器
布隆过滤器使用前提：不支持删除，ss table中的数据不存在删除；
特征：能确定一定不存在，不能确定一定存在(有误判率，并且可控)；可控，提供预期存储元素个数和误判率，算出所占存储空间和hash函数个数；
在sst每一层增加一个布隆过滤器，提高查找效率。
怎么合并压缩？
怎么制定合并压缩的策略？
需要综合考虑lsm-tree的三大问题；
lsm-tree三大问题
类似于隔离级别，cap原则；只能减小其中的一个，另外两个会被放大。
读放大
b 树是2-4层，最多4次io，读性能高；lsm-tree最多7层，读性能相比b 树要差；
b 树为什么读性能高，写性能低？
b 树分裂造成写性能比较低；
空间放大
所有的写操作都是顺序写，而不是就地更新，无效数据不会被马上清理掉；
b 树是就地更新，但是由于b 树以页(16k)为单位存储，但是页内有很大的空间浪费，空间放大更严重；
写放大
同一条数据多次写入磁盘；sst不同层级之间可能存在重复数据；
b 树分裂的时候有写放大，其他时候不会。
压缩策略
为了在读放大、空间放大以及写放大之间进行取舍，以适应不同的业务场景；所以需要选择不同的合并算法；
默认策略：leveled compaction & tiered
放大**
同一条数据多次写入磁盘；sst不同层级之间可能存在重复数据；
b 树分裂的时候有写放大，其他时候不会。
压缩策略
为了在读放大、空间放大以及写放大之间进行取舍，以适应不同的业务场景；所以需要选择不同的合并算法；
默认策略：leveled compaction & tiered
内存中多线程，磁盘合并也是多线程的。