A-A+

RUM Conjecture

2019年03月17日 分布式 评论 5 条 阅读 1,010 次

《Designing Access Methods: The RUM Conjecture》

这篇论文从读、写、存储空间开销角度总结了access method设计,并提出了一个RUM猜想,认为针对其中两个开销优化,则会导致第三个优化困难。

就RUM猜想本身的可信程度而言,我个人觉得一般,不过这种三角可视化的总结非常有趣,可以一读。

 

What is RUM Conjecture

作者总结了Access Method的一些trade off,审视了RUM三种开销:R是read overhead,U是update overhead,M是memory(or storage) overhead,提出了RUM猜想:

designing access methods that set an upper bound for two of the RUM overheads, leads to a hard lower bound for the third overhead which cannot be further reduced。

就是说,如果你的access method能够确保RUM中的任意两个开销的最坏情况的上限,那么剩下的那个开销的最好的情况就很难优化的很好。

论文提到,某些access method会将索引压缩存放,那么通过引入computation / engineering这种场外信息,RUM猜想的可信程度会有些折扣。不过RUM猜想作为一个对access method的RUM三种开销总结,仍然有些价值。只是我们在遇到新的access method设计问题的时候,不能轻易放弃探索“全面好”的方案,尤其是遇到特定场景下的问题,相反RUM猜想可以视为一个探索的工具。

 

RUM in Practice

 

每个access method设计在RUM空间占一个点或者(允许通过调优)占一个区域。

  • 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), Space indexes(ZoneMaps) etc.

 

 

其他略。

 

5 条留言  访客:0 条  博主:0 条

  1. 秋风走马

    目前这个猜想还没有被证明吧

    • LoopJump

      没有证明。这个描述本身比较粗略,考虑的因素也比较少,比如没有考虑cache等组件。

  2. codemonkey4days

    skiplist只是一种适合实现成无锁的数据结构,由于其结构特征,cache不友好, 远谈不上Read Optimized

    • LoopJump

      ?
      原文上下文的大概意思是,btree/skiplist vs lsmtree的这种对比下,磁盘skiplist相比于lsmtree是读优化的,我感觉可能是说,btree/skiplist相比lsmtree维护了更高的全局有序性。

    • LoopJump

      貌似还有篇专门介绍in-mem index的文章,不过还没仔细读过。

给我留言取消回复