论文笔记：[EDBT'16] Designing Access Methods: The RUM Conjecture

发表于 更新于 分类于

RUM 猜想指的是在 Read Overhead，Update Overhead 和 Memory (or Storage) Overhead 中，同时优化 2 项时需要以剩余的 1 项劣化作为代价。论文原作者进一步解释了一下，在一定程度以内（还没有达到最优的情况下）优化，不遵循 RUM 猜想，但是达到一定阈值后，就需要付出代价才能进一步进行优化。这里的 Update Overhead 只考虑写放大，不考虑写时寻址的代价。

The RUM Conjecture: Read, Update, Memory – Optimize Two at the Expense of the Third.

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.

论文原作者解释，提出这一猜想不是说大家啥都不用干了，而是说在达到优化阈值后，如果不想付出某一项性能劣化的代价，应当考虑自适应调整之类的方法，根据数据的特征在这三个重要的参数之间进行平衡。

RUM-Aware Access Method Design. Accepting that a perfect access method does not exist, does not mean the research community should stop striving to improve; quite the opposite. The RUM Conjecture opens the path for exciting research challenges towards the goal of creating RUM-aware and RUM-adaptive access methods.

P.S. 这篇论文也由相同的作者在 SIGMOD'16 上发表了几乎相同的内容[2]。

先来看几个极端情况：

  1. \(\min(RO) = 1.0 \implies UO = 2.0 \,\text{and}\, MO \to \infty\)

  2. \(\min(UO) = 1.0 \implies RO \to \infty \,\text{and}\, MO \to \infty\)

  3. \(\min(MO) = 1.0 \implies RO = N \,\text{and}\, UO = 1.0\)

第 1 种情况是我们将读性能优化到极致，类似于哈希表的极端情况，即我们穷举所有可能的 Key Space，为每一个 Key 安排一个固定的空间。这种情况下存储空间的使用量是无界的（或者说实际意义上无界的），因为穷举整个 Key Space 并为每个 Key 预留 Value 大小的空间在大多数情况下是不实际的。

第 2 种情况为写性能优化到极致，简单来说就是一个 Append-Only 的写请求日志。由于我们从来不实际上删除任何内容，所以存储空间是无界的。而写请求需要遍历全部日志，因此也是无界的。

第 3 种情况为将存储空间优化到极致。类似于第 2 种情况但是所有的更新操作都在原地进行。

显然这 3 种只优化一个目标的极端情况都是不实用的。接下来我们考虑同时优化 2 种目标的情况。论文作者提出这样一种假设：在 RUM 中同时优化任意 2 个目标，都需要付出降低剩下的 1 个指标为代价。

The RUM Conjecture. An access method that can set an upper bound for two out of the read, update, and memory overheads, also sets a lower bound for the third overhead.

一些常见的 Access Methods 在 RUM 中的视角如 常见的 Access Methods 在 RUM 中的视角 所示，他们的时间复杂度（大O表示法）如 常见的 Access Methods 的时间复杂度 所示。

常见的 Access Methods 在 RUM 中的视角
Figure 1. 常见的 Access Methods 在 RUM 中的视角
常见的 Access Methods 的时间复杂度
Figure 2. 常见的 Access Methods 的时间复杂度

直觉上考虑一下这个问题。为了读性能优化的数据结构类似于上面第 1 种极端情况的思路，就是在写的时候多做点事情，同时多付出一些冗余的存储空间记录一些辅助查询的信息。为了写性能优化的数据结构类似于上面第 2 种极端情况的思路，在写的时候少做点事情，增加了查询时候的负担。为了给查询减负，又在时间上进行均摊，将本应该在一次写请求中做完的事情拆成上半部和下半部，在非关键路径上执行下半部，将写日志进行重整合并。为了存储空间优化的主要思路是压缩或者牺牲精度，一般都需要同时损失一些读写性能。

参考文献

  • [1] ATHANASSOULIS M, KESTER M, MAAS L, et al. Designing Access Methods: The RUM Conjecture[C]//International Conference on Extending Database Technology (EDBT). Bordeaux, France: 2016.

  • [2] ATHANASSOULIS M, IDREOS S. Design Tradeoffs of Data Access Methods[C]//Proceedings of the 2016 International Conference on Management of Data. New York, NY, USA: Association for Computing Machinery, 2016: 2195–2200.