HCOONa's blog

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

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

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

Slicer [1] 是 Google 内部支持应用按照 Sharding 的方式进行扩展的，与 RPC 框架集成的基础组件。论文中提到其对比其他通用 Sharding 框架论文的独特之处有：

数据库系统是非常重要且复杂的系统，但是其架构方面的知识却不像其他重要的系统（例如操作系统，编译器等）一样为人所熟知。传统教材通常着重讲述数据库相关的算法和理论知识，很少涉及到系统开发和架构方面。论文[1]使用流行的商业和开源数据库系统作为例子，着重论述（关系型）数据库系统的架构。尽管有些细节方面在这些年中发生了变化，但是大体结构和思路上并没有太多出入。

Percolator[1]在基于Bigtable[2]系统，在不改变Bigtable自身实现的前提下，通过行级事务和多版本控制，实现了Snapshot Isolation级别的跨行事务。此外，论文还描述了一种基于Bigtable实现的可靠的消息通知机制。

比较有特色的是，Percolator在实现上述2个功能时，并没有侵入去改变Bigtable的实现，而是在Bigtable外围通过包装去实现，这在有些情况下是一种非常方便的做法，但是一般会带来性能损失。

在数据库领域，Transaction是一个非常重要的抽象，其关键在于保证并发请求的正确性。由于Serialisability级别的一致性所需要付出的代价较高，所以通常会使用弱一些的一致性级别来换取性能提升。特别的，在一些特殊场景下，使用弱一致性并不会带来错误。遗憾的是，ANSI SQL对于一致性级别的分类还不够细致，特别的，对于一些常见的弱一致性实现没有形式化规范。这导致人们很难确认特定供应商提供的弱一致性实现在某个特定场景下是否真的不会引入错误。[2]

近年来，不断有一些使用形式化方法分析Transaction一致性的论文，如[3][4]，以及本文希望介绍的[1]。形式化的表述有助于推理和验证，但是仍需要非形式化的解释以进行直观解释，本文将介绍[1]所做的形式化工作，并解释其直觉含义。

ARC是一种缓存替换算法，在很多种负载环境的表现优于常用的LRU算法，并且实现难度和算法复杂度与LRU近似。

ARC算法具有以下优良特性：

本文特别写给想要学习分布式系统但是还不知道该如何下手的读者，宽泛并点到为止的介绍了我个人对于分布式系统各个方面的一些不成熟的理解，帮助读者认识到分布式系统领域的一个全景图，以便接下来寻找感兴趣的领域进行深入的学习。

学习分布式系统，需要回答以下几个问题：