自制分布式存储系统入门篇：序章
新的开始
近几年，随着互联网规模的扩大，我们需要处理的数据也变得越来越多；随着机器学习的发展，我们的数据也变得越来越有价值。在这一时代背景下，大规模分布式系统变得越来越重要。遗憾的是，这一领域由于出现的比较晚，相关的学习资料比较少，大家对这一领域的认识和了解都比较有限。我认识的一些名校毕业名企工作的非常优秀的工程师，虽然日常工作中会使用 Hadoop 生态的一些产品，但是对于大规模分布式系统的底层原理的理解也十分有限。
于是我认为，将我有限的知识分享出来，让大家能够对分布式存储系统有一个初步的感性认识，仍然是一件非常有意义的事情，于是便准备开始这样一个系列。
论文笔记：[OSDI'16] Slicer: Auto-Sharding for Datacenter Applications
Slicer [1] 是 Google 内部支持应用按照 Sharding 的方式进行扩展的，与 RPC 框架集成的基础组件。论文中提到其对比其他通用 Sharding 框架论文的独特之处有：
-
控制侧和数据侧分离
-
高效的负载均衡算法，在尽可能减少 key churn 的情况下提供很好的负载均衡效率
-
提供一些在大规模生产环境下的 evaluation
论文笔记：[FTNDB'07] Architecture of a Database System
数据库系统是非常重要且复杂的系统，但是其架构方面的知识却不像其他重要的系统（例如操作系统，编译器等）一样为人所熟知。传统教材通常着重讲述数据库相关的算法和理论知识，很少涉及到系统开发和架构方面。论文[1]使用流行的商业和开源数据库系统作为例子，着重论述（关系型）数据库系统的架构。尽管有些细节方面在这些年中发生了变化，但是大体结构和思路上并没有太多出入。
论文笔记：[OSDI'10] Large-scale Incremental Processing Using Distributed Transactions and Notifications
Percolator[1]在基于Bigtable[2]系统，在不改变Bigtable自身实现的前提下，通过行级事务和多版本控制，实现了Snapshot Isolation级别的跨行事务。此外，论文还描述了一种基于Bigtable实现的可靠的消息通知机制。
比较有特色的是，Percolator在实现上述2个功能时，并没有侵入去改变Bigtable的实现，而是在Bigtable外围通过包装去实现，这在有些情况下是一种非常方便的做法，但是一般会带来性能损失。
论文笔记：[CONCUR'15] A Framework for Transactional Consistency Models with Atomic Visibility
在数据库领域，Transaction是一个非常重要的抽象，其关键在于保证并发请求的正确性。由于Serialisability级别的一致性所需要付出的代价较高，所以通常会使用弱一些的一致性级别来换取性能提升。特别的，在一些特殊场景下，使用弱一致性并不会带来错误。遗憾的是，ANSI SQL对于一致性级别的分类还不够细致，特别的，对于一些常见的弱一致性实现没有形式化规范。这导致人们很难确认特定供应商提供的弱一致性实现在某个特定场景下是否真的不会引入错误。[2]
近年来，不断有一些使用形式化方法分析Transaction一致性的论文，如[3][4]，以及本文希望介绍的[1]。形式化的表述有助于推理和验证，但是仍需要非形式化的解释以进行直观解释，本文将介绍[1]所做的形式化工作，并解释其直觉含义。
论文笔记：[FAST'03] ARC: A Self-Tuning, Low Overhead Replacement Cache
ARC是一种缓存替换算法，在很多种负载环境的表现优于常用的LRU算法，并且实现难度和算法复杂度与LRU近似。
ARC算法具有以下优良特性：
-
在recency和frequency之间持续的进行动态（在线）调整
-
无需事先指定特别的参数（先验知识）
-
具有全局优化策略（意译，不确定翻译的对不对，原文empirically universal，note说明该词出自LZ77的论文）
-
可以（在某种程度上）抵抗线性扫描（scan-resistant）
分布式系统入门介绍
本文特别写给想要学习分布式系统但是还不知道该如何下手的读者，宽泛并点到为止的介绍了我个人对于分布式系统各个方面的一些不成熟的理解，帮助读者认识到分布式系统领域的一个全景图，以便接下来寻找感兴趣的领域进行深入的学习。
学习分布式系统，需要回答以下几个问题：
-
（需求分析）分布式系统主要解决哪些问题？主要应用场景有哪些？
-
（实现方案）构建分布式系统的常见问题有哪些？解决这些问题的主流方案有哪些？
-
（技术难点）实现分布式系统的本质困难是什么？这些困难影响了那些问题？
-
（工业应用）工业上正在构建那些分布式系统？他们的发展情况如何？
大规模集群管理和运维自动化
说到大规模集群管理，就离不开运维自动化。一个人手工也许可以运维几百台机器，但是随着集群规模的增长，我们需要的是一个人运维数万台机器。 这在大规模集群管理中是一个常见的问题。因此，运维自动化是一个很重要的事情，这也是为什么很多公司原因上云，因为上云之后运维的问题就托管给 云平台了。这也是云平台这么贵还能卖的这么好的原因。
运维自动化的问题到底是一个什么问题？我认为，可以拆解为以下子问题：
-
自动发现错误
-
自动修复错误
-
安全（Safety而非Security）
这里的每一个问题都是复杂的，困难的问题，远非表面上看起来那么简单。以下仅作简单的展开，提供一些思路。
论文笔记：[Operating Systems Review 2007] Autopilot: Automatic Data Center Management
Autopilot是微软Bing组研发的集群管理系统，至今已有近20年的历史。Autopilot是一个内部模块高度解耦，完善发达的系统，其设计目标是自动化的管理静态集群。自动化的好处有以下几点：
-
节省人力
-
响应速度和处理时间优于人工处理
-
所有的处理过程都有Audit
-
不易出错
CAP，ACID，我们能做什么
本文从CAP理论和ACID性质为切入点，讨论分布式（存储）系统的设计。
分布式系统，尤其是分布式存储系统，在进行设计考虑时，首先需要想到的就是CAP问题，即在C（Consistency）和A（Availability）之间如何进行取舍的问题。我在思考的过程中发现，尽管对于Consistency有着诸多分类，如Linearizability、Sequential Consistency、Causal Consistency，但是对于Availability却没有一个对应的分类。这有悖于对CAP理论的理解：我们降低了Consistency之后，能得到什么程度的Availability？更进一步的，我们降低了Consistency后，是否真的能够提高Availability？