rocksdb基于Log-Structured Merge (LSM) Trees，分析rocksdb存储引擎的读写空间放大比例，即主要对LSM Trees结构进行分析，相关基础概念以论文A Comparison of Fractal Trees to Log-Structured Merge (LSM) Trees中的定义为准。
先来看基础概念：
1> Read amplification is the number of I/O’s required to satisfy a particular query.
读放大：一次指定查询所需的IO操作数目。
2> Write amplification is the amount of data written to storage compared to the amount of data that the application wrote.
写放大：实际写入磁盘的数据大小比上用户期望程序写入的数据量。
3> Space amplification is the space required by a data structure can be inflated by fragmentation or requirements for temporary copies of the data.
空间放大：存储采用的数据结构因分裂或临时数据拷贝造成的磁盘空间占用放大。
LSM Trees有leveled和size-tiered两种形式：
1. Leveled LSM Trees
从第Level 0到Level h（h>1）所在层数据大小按k倍逐层增长，例如k=10，总计7层时，对应level 6有不超过10TB大小的数据。
假定数据集总大小为N，增长因子为k，假设最小层单个文件大小为B。
rocksdb采用的就是leveled compaction（其实也结合了类似size-tiered进行优化）。
读放大：
每一层均需执行二分查找，最底层（最大层）数据大小为O(N)，二分查找IO次数为O(log(N/B))；倒数第二层则数据大小为O(N/k)，需要O(log(N/(kB))) = O(log(N/B) – logk)次IO；倒数第三层则数据大小为O(N/K2)，需要O(log(N/(k2B))) = O(log(N/B) – 2logk)次IO ……，则总共的IO次数为：
R = log(N/B) + (log(N/B) – logk) + (log(N/B) – 2logk) + … + 1 = logk(N/B)*log(N/B) – k(k+1)/2*logk
因此读放大为O(logk(N/B)*log(N/B) ) = O(log2(N/B)/logk)。
写放大：
可计算对应的levels（树的高度）为logk(N/B)。数据被merge到下一层一次，而指定层对应数据被上一层merge回本层平均合并k/2次（最少会不被merge，最多k次，平均即为k/2），因此写放大为 k/2 * logk(N/B)，即O(klogk(N/B))。
空间放大：
空间放大取决于还有多少旧数据待垃圾回收。
若每层仅有一个文件，相邻层合并生成新的较大层文件，同一条记录会存在两份，因此空间放大是2。
若每层有多个文件，10倍增长因子，最坏情况下，以最底层达到10TB数据来算，从上一层到最顶层约占1TB多，根据定义，因此空间放大为10/(10-1)=1.11…。
若考虑到merge时暂未删除的旧数据，则空间放大可以认为约1.2。
2. Size-tiered LSM Trees
按大小分层组织，每层单个文件大小固定，层间单个文件大小为k倍关系，被越往底层单个数据文件越大越陈旧。
假定数据集总大小为N，扇出因子是k，则compaction时，k个文件为一组合并到下一层，以此类推。
该种结构的典型应用是Cassandra。
读放大：
为保持与leveled LSM Trees的评价分析方式一致，需要读的文件个数相当于O(klogk(N/B))，每层内文件相当于再执行二分查找，则总计需要O(klog2(N/B)/logk)。
写放大：
数据会被写到每一层仅一次，因此写放大为层高，即logk(N/B)。
空间放大：
合并时生成新的较大文件，以k=4计算，则空间放大为(4-1)/1 = 3。
若考虑到merge时暂未删除的旧数据，则空间放大可以认为是2。
refer:
1. A Comparison of Fractal Trees to Log-Structured Merge (LSM) Trees
2. Optimizing Space Amplification in RocksDB
3. https://planet.mysql.com/entry/?id=5993077