[笔记] Designing Access Methods: The RUM Conjecture

发表于   |   分类于

The RUM Conjecture

RUM Conjecture非常类似CAP theorem，指对于一个存储系统，出读(Read)、写(Updates)以及空间(Memory)三者之间是一个相互制约的关系，如图



rocksdb的写放大，读放大，空间放大是一个很好的例子，相关的优化方法有：

  • Read-optimized Access Method: Hash, B-Tree, Tries, Prefix B-Tree, Skiplist etc
  • Write-optimized Differential Structures: LSM Tree, Partitioned B-Tree,Materialized Sort-Merge algorithm, Stepped Merge algorithm, Positional Diffferential Tree, LA-Tree, FD-Tree etc.
  • Space-efficient access method: compression tech, lossy index(such as Blomm filters), Count-min sketches,Space indexes(ZoneMaps) etc.

其他因素：

  • 延迟
  • 访问模式
  • 实现复杂性
  • 新硬件
  • 分布式系统一致性、副本等