in LevelDB 分布式数据库 ~ read.

读放大,写放大,空间放大

读放大,写放大,空间放大

读放大(Read Amplification)

LSM-Tree 的读操作需要从新到旧(从上到下)一层一层查找,直到找到想要的数据。这个过程可能需要不止一次 I/O。

特别是 range query 的情况,影响很明显。

空间放大(Space Amplification)

因为所有的写入都是顺序写(append-only)的,不是 in-place update ,所以过期数据不会马上被清理掉。

通过后台的 compaction 来减少读放大(减少 SST 文件数量)和空间放大(清理过期数据),但也因此带来了写放大(Write Amplification)的问题

写放大

实际写入 HDD/SSD 的IO数据量 是 用户要写入IO数据量大小的好几倍。正常情况下,HDD/SSD 观察到的写入数据多于上层程序写入的数据。

具体写放大,参考 同系列文章LevelDB-Compaction中的问题章节。

HDD 作为主流存储,Compaction 带来的写放大问题没有非常明显。这是因为:

HDD 顺序读写性能远远优于随机读写性能,足以抵消写放大带来的开销。

HDD 的写入量基本不影响其使用寿命。

SSD 作为主流存储,Compaction 带来的写放大问题显得严重:

SSD 顺序读写性能比随机读写性能好一些,但是差距并没有 HDD 那么大。所以,顺序写相比随机写带来的好处,能不能抵消写放大带来的开销,这是个问题。

SSD 的使用寿命和其写入量有关,写放大太严重会大大缩短 SSD 的使用寿命。因为 SSD 不支持覆盖写,必须先擦除(erase)再写入。而每个 SSD block(block 是 SSD 擦除操作的基本单位) 的平均擦除次数是有限的。

所以,在 SSD 上,LSM-Tree 的写放大是一个非常值得关注的问题。

权衡

写放大、读放大、空间放大,三者就像 CAP 定理一样,要做权衡和取舍。