With these workloads, TRIAD yields up to 193% improvement in throughput. It reduces write amplification by a factor of up to 4x, and decreases the amount of I/O by an order of magnitude.
通过某些优化,减少写放大,减少 IO,blablabla,基本所有 paper 都如是。作为读者面对这种说辞我们首先应该想到:
使用的机制是否好实现,侵入性小,或者复杂度和收益的性价比足够高
基于什么样的 workload,是否具有实用价值,是否会对 common case 带来负面影响
The first technique decreases compaction overhead for skewed workloads. We keep KV pairs that are updated frequently (i.e., hot entries) in the memory component, and we only flush the cold entries.
TRIAD(USENIX ATC'17),一个新的 LSM key-value 存储引擎,开发这个引擎的公司叫 Nutanix,用 RocksDB 做核心企业系统 metadata 的管理。TRIAD 的设计以该公司的需求为基础,出身于工业界的产品会有较强的可参考性。
通过某些优化,减少写放大,减少 IO,blablabla,基本所有 paper 都如是。作为读者面对这种说辞我们首先应该想到:
Paper $3.1 Data skew unawareness
第一个优化点是针对冷热数据写差别较大的场景(skewed workload),热数据的频繁更新会导致 memtable 很小而 commit log 却很大,为了避免日志过多而导致数据库重启恢复时间(recovery time)增加, memtable 必须频繁地 flush 从而让 commit log 可以清掉,而这对性能是一种损失。这点在 rocksdb wiki: memtable flush 中有详细介绍,相关配置项为 (
max_total_wal_size
)。当然,memtable 达到一定大小也不可避免会被 flush,相关配置项为 (write_buffer_size
)。Paper $4.1 TRIAD-MEM
大概做法是,原来 rocksdb 只是简单将数据从 memtable 转移到 L0 SST;现在 TRIAD 改成只有冷数据转移至 L0,热数据保留在 memtable 原地不动,同时将这些热数据写一份到 commit log,此前的日志都可以删掉,这样就解决了日志膨胀的问题。
可以看到,后者的优势在于热数据仍然存留在 memtable,未来对它们的更新都会提前在内存中被 merged,日志的 compaction 比 SST 的 compaction 更快也更简单,直接删文件即可,不需要读文件。
举个例子,我们假设一种极端情况,全部数据有 100k 条,每条 64KB,,其中固定 1k 条数据为热数据,其余 99k 条都为冷数据(1:99)。我们让 max_total_wal_size=128MB,write_buffer_size=128MB,2k 的写刚好可以塞满 commit log。
在 2k 次写之后,memtable 有 2k*1%=20 条冷数据,1k 条热数据。20 条冷数据会被写到 L0,memtable 剩下 1k 条。由于此时 commit log 已满,1k 条数据会被写到 commit log,旧日志被删掉。总的写 IO = 2k log writes + 20 L0 writes + 1k log rewrites = 3k writes
而如果是在 rocksdb 下,写 IO = 2k log writes + 1020 L0 writes + 1k compaction writes = 4k writes,显然上述优化减小了写放大。
Paper $4.2 TRIAD-DISK
使用 hyperloglog 来判断是否应该进行 L0 和 L1 的 compaction。每个 L0 SST 文件头存一个 HLL,可以推算如果 L0 和 L1 的 overlap ratio 大于给定 threshold,则进行 L0/L1 compaction。由于没有具体算法,不详述。
有一点是 Cassandra 倒是用了 HLL 来确定 L0 的哪个文件 overlap ratio 最高。简单就是 overlap ratio = UniqueKeys(fi) / SumKeys(fi)。最高的先做 compaction。我在 reddit/rocksdb 三年前的帖子里也发现了相关讨论。
Paper $4.3 TRIAD-LOG
核心思想是把 commit log 当做 SST 来用。因为 commit log 有一份持久化数据,L0 SST 再写一份的话是一种浪费(Paper $3.3 Duplicate writes)。把日志文件直接 rename 成 SST 岂不美哉?
有个困难是,SST 是排好序的,我们可以在内存中维护 key -> latest log offset 的映射,这样对 point read 没有影响,但对 range read 影响很大。
基本上这个思想和 wisckey 很接近,已经被完整讨论过,不做详述。
Conclusion
个人觉得整篇 paper 最好的 idea 是 TRIAD-MEMTABLE,但因为这个 case 不够 attractive,可能工程价值不大。整个项目开源在 https://github.com/epfl-labos/TRIAD ,有兴趣可以看。