原文名：Efficient Compactions between Storage Tiers with PrismDB
LSM 树针对冷热数据的优化。热放在 3D XPoint NVM 设备，冷放 QLC NAND。
贡献点：
- 多层设计。 DRAM + NVM + flsah.
- Popularity scoring 方式， 文中的 MSC 指标用作 compaction 选择的依据。
总结：相比 Mutant, 用 MSC 作为转冷的指标感觉更好。读采用了 DRAM Btree 和 NVM 加速，写用 NVM slab 做 buffer，flash 上采用 sst 加速。
PrismDB Design·
整体架构 ·
PrismDB 采用 key 分区实现 shard-nothing，保证无锁，避免过多同步开销。 （笔者注：估计是根据 key 分区拆成多个 cf？）但是分区策略交给用户决定，key range 或者 hash range。
所有 metadata（index、bloom filter）都存在当 DRAM 和 NVM 中。NVM 数据是 unsorted 的，Flash 的数据是 sorted。每个分区在 DRAM 中有两个组件：tracker 和 mapper。
tracker 用于评估 key 的流行度，使用 clock 算法。
mapper 决策 value 在不同的 device 的 placement。把 NVM 中最 old 的一部分数据搬移到 flash 中。搬移使用 multi-tiered storage compaction (MSC) 算法。
内存结构 ·
下面介绍各 device 的数据结构：
- in mem: mem 使用 B tree 作为 index，用于索引 nvm 中的数据。每个索引保存 key 和 key 所对应的 nvm 地址（1 字节 slab id + 字节 page offset）。 此外还有 tracker 维护的 clock 算法，每个 tracker entry 是 key 和 1 字节的 clock meta。
文中还描述了这样一句话，暂时不理解是什么意思。 PrismDB does not use a userspace DRAM cache for caching frequently-read objects and instead relies on the OS page cache.
- in nvm: nvm 中采用了 slab 策略保存数据，所有新数据都先插入到 NVM 中。slab 维护了一组 fixed size 的 slot（从 100B，200B 到 1KB）。 此外还维护了 flash 数据的 index，对每个 flash 上的文件，维护了 bloom filter。 index + filter 的大小 range from 100MB 到 GB 级别。
- in flash: 存放 sst。 看 NVM 的大小，如果 NVM 很大，sst 搞一层就行，如果 NVM 比较小，sst 可以搞多层。（笔者注：这和 19 年的一篇韩国人 FAST 文章架构不是差不多一样？只不过本文加了冷热）
写入 object 的生命周期 ·
NVM 容量达到 98%（可调）后，启动 demote 流程，识别 cold 数据，通过 compaction 迁移到 flash，直到容量降到 95%（可调）。 如果 flash 上的 hot object 过多通过 promote 流程迁移到 NVM。
为了避免把 NVM 容量撑爆，加了 rate limiter.
流行度 tracking·
Tracker： 轻量级 tracking objects。使用 clock 剔除算法（近似 LRU，更好 space saving），clock 算法追踪的 key 只有全局 key range 的 10%。
Mapper: Pinning threshold algorithm.。 根据 clock 算法 bits ，按 rank 降序，高于保留阈值的，deremote。高 bit 且低于保留阈值，则保留在 NVM 中，低 bit 也低于阈值的，随机丢。
Multi-Tiered Storage Compaction·
compaction 两个作用：
- 回收垃圾
- 冷热迁移
Compaction cost and benefit 建模：
设计目标： 尽可能将更多的 cold object 转移到 slow storage。并且只从 write 角度考虑，因为 write 少的将保持 stable。
Benifit：
定义每个对应的 coldness： coldness 的定义域为 [0,1)。 $$ coldness (j) = \frac {1}{clock_j + 1} $$ $clock_j$ 是每个 key 的 clock value。对于从未出现过的 key，clock value 为 0. 对于一个 key range， 其 coldness 是整个 key range 的 coldness 纸盒。
Cost
cost 定义成 compaction 导致的 flash 的 IO 次数。
最终推导出的 io cost 为，（推导过程不想写了） $$ cost = F\times \frac {2- o}{ (1 - p)} + 1 $$ 各参数含义:
最终的 MSC（multi-tiered storage compaction) 定义为 benefit /cost
即单位 io 成本上的冷度。 该值越大，代表一个 key range 越冷，应该越先迁移（compaction)
笔者注： 在没发生 compaction 前，怎么提前知道 NVM 中的 range 和 flash 的 range 的 overlap object 个数的？
问题是上述公式如果要精确计算，需要耗费过多 cpu。作者又提出了近似计算。具体做法是将一个 key range 进一步拆分成多个固定大小的 range（称为一个 bucket），对每个 bucket 做近似计算，然后总体的 MSC value 是所有 bucket 的加权和。
key range 选择： 选择哪个 key range 来 compaction？这里采用 power-of-k choices 算法选择，k 设置为 8.
“Power-of-k choices” 算法是一种用于负载均衡的策略，它通过在将任务分配给服务器时选择多个服务器中的最佳服务器来提高效率。 与其随机地将每个任务分配给一个服务器，该算法会随机选择 k 个服务器，然后将任务分配给这 k 个服务器中负载最轻的服务器。
同时为了适应 read heavy workload, 添加了 read trigger compaction（笔者注：记得 leveldb 就有？）
实现 ·
下图展示了 PrismDB 的读写、后台流程。每个 partition 都有两个 worker，前台 worker 处理读写，更新 key 热度，更新 tracker 和 mapper。后台 worker 处理 compaction，将 cold object 搬移到 flash device 中。
支持 4 种接口。 Put, Get, Delete 和 Scan。
Tracker 和 Mapper 更新， Tracker 由 Intel TBB lib 实现的并发 hash map 记录。key 是插入的 object key， value 是 1 字节，其中 2bit 用于 clock 算法记录热度，1bit 用于记录该 key 的位置是在 NVM 上还是 flash 上。 每次插入也可能触发 eviction。 mapper 是一个数组，包含四个 atomic interger，每个 slot 记录对应 clock value 有多个 key。
Compaction Thread: 使用 MSC 指标选择要 compaction 的 range。（笔者注：结合上文所的 power of k chioces. 应该是随机选 8 个 key range, 比较它们的 MSC 指标，选择最小的来 compaction）
Bucket 实现 每个 Bucket 设置为 64K 个 keys，然后把 key range 划分为连续的多个 bucket 空间。（笔者注： 那 bucket 还会分裂、合并吗？文章没有提，然而这个很重要）每个 bucket 包含四个字段： num_nvm_keys (a counter of the number of keys present on NVM), pop_bitmap (a bitmap of key popularity), nvm_bitmap (a bitmap of keys on NVM), and flash_bitmap (a bitmap of keys on flash).
Put 操作增加 num_nvm_keys, compaction 操作减少 num_nvm_keys, Gets 操作将 pop_bitmap 对应位置为 1，eviction 操作将对应位置设置为 0。 nvm_bitmap 和 flash_bitmap 很直观，这两个字段作用是用来计算 overlap 率的。
有了这 4 个字段，就可以粗略计算 MSC 指标了。
评估 ·
略。
