staged event-driven architecture (SEDA) 框架在建模的时候就将负载和资源瓶颈考虑在内,从而可以在高负载的情况下也能工作良好,并且有效防止服务过载。SEDA 架构的基本思想是将业务逻辑切分成一系列通过 queues 连接起来的 stages,组合成一个 data flow 网络去执行。

很久之前就看到过 SEDA 的论文,当时没有太过在意,因为这个 idea 实在是太简单了。最近这几年在多租户系统的隔离性,延迟稳定性方面进行了一些比较深入的工作,又加上最近看到了比较相关的论文和文章之后,突然又产生了一些触动,决定把这篇文章再捞起来写上几句。

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]

新的开始

近几年,随着互联网规模的扩大,我们需要处理的数据也变得越来越多;随着机器学习的发展,我们的数据也变得越来越有价值。在这一时代背景下,大规模分布式系统变得越来越重要。遗憾的是,这一领域由于出现的比较晚,相关的学习资料比较少,大家对这一领域的认识和了解都比较有限。我认识的一些名校毕业名企工作的非常优秀的工程师,虽然日常工作中会使用 Hadoop 生态的一些产品,但是对于大规模分布式系统的底层原理的理解也十分有限。

于是我认为,将我有限的知识分享出来,让大家能够对分布式存储系统有一个初步的感性认识,仍然是一件非常有意义的事情,于是便准备开始这样一个系列。

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

  1. 控制侧和数据侧分离

  2. 高效的负载均衡算法,在尽可能减少 key churn 的情况下提供很好的负载均衡效率

  3. 提供一些在大规模生产环境下的 evaluation

数据库系统是非常重要且复杂的系统,但是其架构方面的知识却不像其他重要的系统(例如操作系统,编译器等)一样为人所熟知。传统教材通常着重讲述数据库相关的算法和理论知识,很少涉及到系统开发和架构方面。论文[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算法具有以下优良特性:

  1. 在recency和frequency之间持续的进行动态(在线)调整

  2. 无需事先指定特别的参数(先验知识)

  3. 具有全局优化策略(意译,不确定翻译的对不对,原文empirically universal,note说明该词出自LZ77的论文)

  4. 可以(在某种程度上)抵抗线性扫描(scan-resistant)

0%