2.4 分布式系统的进阶

分布式系统是一个古老而宽泛的话题，而近几年因为“大数据”概念的兴起，使分布式系统又焕发出了新的青春与活力。此外，分布式系统也是一门理论模型与工程技法并重的学科内容。相比于机器学习这样的研究方向，学习分布式系统的读者往往会感觉“入门容易，深入难”。的确，学习分布式系统几乎不需要太多数学知识，会造成“入门容易”的错觉。然而一旦深入下去，往往需要学习者去体会系统研究的“简洁”与“美”，系统工作更偏向于“艺术”而不是“科学”，这一点是系统研究工作最难的地方之一，但同时也是最精华的地方。总之要把握一个原则：好的系统研究工作，尤其是分布式系统研究，一定是尽可能地用最简单、最直观的方法去解决实际的问题，简单就意味着实用。例如上文提到过的著名的MapReduce。

总的来说，分布式系统的任务就是把多台机器有机地组合、连接起来，让其协同完成一件任务，可以是计算任务，也可以是存储任务。如果一定要给现代分布式系统研究做一个分类的话，大概可以分成三大类别：分布式存储系统；分布式计算系统；分布式资源管理系统。

毫无疑问，十多年来，Google 在这三个方向上都是开创者，甚至很多业内人士都认为这十年是外界追随谷歌技术的十年。之前讲过分布式系统的研究是一门由实际问题驱动的研究，而Google则是最先需要面对这些实际问题的公司。下面分别介绍近年来工业界及学术界在这三个方面取得的进展。

2.4.1 分布式存储系统

分布式存储是一个很老的话题，同时也是分布式系统里最难、最复杂、涉及面最广的问题。分布式存储系统大致可分为 5 个子方向：结构化存储、非结构化存储、半结构化存储、In-memory 存储及NewSQL。

除了这5个子方向之外，分布式存储系统还有一系列的理论、算法、技术作为支撑，例如 Paxos、CAP理论、一致性散列、时钟技术、2PC、3PC等，部分内容前面已经提到。

1.结构化存储

结构化存储的历史非常古老，典型的场景就是事务处理系统或者关系型数据库（RDBMS）。传统的结构化存储都是从单机做起的，例如大家耳熟能详的 MySQL。MySQL 的成长史就是互联网的成长史。除了MySQL之外，PostgreSQL也是近年来势头非常强劲的一个RDBMS。传统的结构化存储系统强调以下内容。

结构化的数据（例如关系表）；

强一致性（例如银行系统，电商系统等场景）；

随机访问（索引、增删查改、SQL）。

然而，正是由于这些性质和限制，结构化存储系统的可扩展性通常都不是很好，这在一定程度上限制了结构化存储在大数据环境下的表现。随着摩尔定律面临瓶颈，传统的单机关系型数据库系统面临着巨大的挑战。

2.非结构化存储

与结构化存储不同的是，非结构化存储强调的是高可扩展性，典型的系统就是分布式文件系统。分布式文件系统也是一个很老的研究话题，例如20世纪70年代的Xerox Alto，80年代的NFS、AFS， 90年代的xFS等。然而，这些早期的分布式文件系统只是起到了网络磁盘的作用，其最大的问题就是不支持容错和错误恢复。而Google在2003年SOSP会议上推出的GFS（Google File System）则走出了里程碑的一步，其开源实现对应为HDFS。

Google设计GFS最初的目的是为了存储海量的日志文件以及网页等文本信息，并且对其进行批量处理（例如配合MapReduce为文档建立倒排索引、计算网页PageRank等）。与结构化存储系统相比，虽然分布式文件系统的可扩展性、吞吐率都非常好，但是几乎无法支持随机访问操作，通常只能对文件进行追加操作。而这样的限制使非结构化存储系统很难面对那些低延时、实时性较强的应用。

3.半结构化存储

半结构化存储的提出是为了解决非结构化存储系统随机访问性能差的问题。我们通常会听到一些流行的名词，例如 NoSQL、Key-Value Store，包括对象存储等。这些都属于半结构化存储研究的领域，其中以 NoSQL 的发展势头最为强劲。NoSQL 系统既有分布式文件系统所具有的可扩展性，又有结构化存储系统的随机访问能力（例如随机操作），系统在设计时通常选择简单键值（K-V）进行存储，抛弃了传统RDBMS里复杂SQL查询及ACID事务。这样做可以换取系统最大限度的可扩展性和灵活性。在NoSQL里比较有名的系统包括：Google的Bigtable、Amazon的Dynamo以及开源界大名鼎鼎的HBase、Cassandra等。通常这些NoSQL系统底层都是基于比较成熟的存储引擎，例如Bigtable就是基于LevelDB，底层数据结构采用 LSM-Tree。

4.In-memory存储

随着业务的并发越来越高，存储系统对低延迟的要求也越来越高。同时由于摩尔定律以及内存的价格不断下降，基于内存的存储系统也开始普及。顾名思义，In-memory存储就是将数据存储在内存中，从而获得读写的高性能。比较有名的系统包括Memcached和Redis。这些基于K-V键值系统的主要目的是为基于磁盘的存储系统做缓存。还有一些偏向于内存计算的系统，例如 Distributed shared memory、RamCloud、Tachyon（Alluxio）项目等。

5.NewSQL

前面介绍结构化存储时提到，单机RDBMS系统在可扩展性上面临着巨大的挑战，然而NoSQL不能很好的支持关系模型。那有没有一种系统能兼备RDBMS的特性（例如，完整的SQL支持、ACID事务支持），又能像NoSQL系统那样具有强大的可扩展能力呢？2012年Google在OSDI会议上发表的Spanner，以及2013年在SIGMOD会议上发表的F1，让业界第一次看到了关系模型和NoSQL在超大规模数据中心上融合的可能性。不过由于这些系统大都过于复杂，没有工业界大公司的支持还是很难做出来的。

前面提到，分布式存储系统有一系列的理论、算法、技术作为支撑。例如Paxos、CAP理论、一致性散列、时钟技术、2PC、3PC等。那么如何学习这些技术呢？掌握这些内容一定要理解其对应的上下文，一定要去思考为什么在当下环境需要某项技术，如果没有这个技术用其他技术替代是否可行，而不是一味陷入大量的细节之中。

2.4.2 分布式计算系统

本节介绍分布式计算系统。首先解决一个很多分布式计算初学者的疑惑：分布式计算和并行计算一样吗？可以这样认为：

传统的并行计算的要求：投入更多机器，数据大小不变，计算速度更快。

分布式计算的要求：投入更多的机器，能处理更大的数据。

换句话说，二者的出发点不同，前者强调高性能，而后者强调可扩展性。举例来说，MapReduce给业界带来的真正思考是什么？其实是普及了Google这样级别的公司对真正意义上的“大数据”的理解。因为在2004年论文发表之前，从事并行计算的人连“容错”的概念都没有。也就是说，分布式计算最为核心的部分就是容错，没有容错，分布式计算根本无从谈起。MapReduce要做成Map ＋Reduce，其实就是为了容错。

而很多分布式计算的初学者对容错的概念也是有误解的：好好的计算怎么就会出错了呢？由于硬件的老化可能会导致某台存储设备没有启动，某台机器的网卡坏了，甚至于计算运行过程中断电了，这些都是有可能的。然而最频繁发生的错误是计算进程被杀掉。因为Google的运行环境是公共集群，任何一个权限更高的进程都可能杀掉计算进程。设想在一个拥有几千台机器的集群中运行，一个进程都不被杀掉的概率几乎为零。

随着机器学习技术的兴起，越来越多的分布式计算系统是为了机器学习这样的人工智能应用设计的。

如同分布式存储系统一样，可以对分布式计算系统做以下分类。

1.传统基于消息的系统

这类系统里比较有代表性的就是MPI（Message Passing Interface）。目前比较流行的两个MPI实现是MPICH2和OpenMPI。MPI这个框架非常灵活，对程序的结构几乎没有太多约束，以至于人们有时把MPI称为一组接口API，而不是系统框架。MPI除了提供消息传递接口之外，其框架还实现了资源管理和分配，以及调度的功能。除此之外，MPI 在高性能计算里也被广泛使用，通常可以和Infiniband 这样的高速网络无缝结合。

2.MapReduce家族系统

这一类系统又称作Dataflow系统，其中以Hadoop MapReduce和Spark为代表。其实在学术界有很多类似的系统，例如 Dryad、Twister 等。这一类系统的特点是将计算抽象成为高层操作，例如像Map、Reduce、Filter这样的函数式算子，将算子组合成有向无环图DAG，然后由后端的调度引擎进行并行化调度。其中，MapReduce系统属于比较简单的DAG，只有Map和Reduce两层节点。MapReduce这样的系统之所以可以扩展到超大规模的集群上运行，就是因为其完备的容错机制。在Hadoop社区还有很多基于MapReduce框架的衍生产品，例如Hive（一种并行数据库OLAP）、Pig（交互式数据操作）等。

MapReduce家族的编程风格和MPI截然相反。MapReduce对程序的结构有严格的约束，即计算过程必须能在两个函数中描述：Map和Reduce；输入和输出数据都必须是一个个的记录；任务之间不能通信，整个计算过程中唯一的通信机会是Map阶段和Reduce阶段之间的shuffling阶段，这是在框架控制下的，而不是应用代码控制的。因为有了严格的控制，系统框架在任何时候出错都可以从上一个状态恢复。Spark的RDD则是利用Lineage机制，可以让数据在内存中完成转换。

由于良好的扩展性，许多人将机器学习算法的并行化任务放在了这些平台之上。比较有名的库有基于Hadoop的Mahout，以及基于Spark的MLI。

3.图计算系统

图计算系统是分布式计算的另一个分支，这些系统都是把计算过程抽象成图，然后在不同节点分布式执行，例如PageRank这样的任务，很适合用图计算系统来表示。

大数据图是无法使用单台机器进行处理的，如果对大图数据进行并行处理，对于每一个顶点之间都是连通的图来讲，难以分割成若干完全独立的子图进行独立的并行处理。即使可以分割，也会面临并行机器的协同处理，以及将最后的处理结果进行合并等一系列问题。这需要图数据处理系统选取合适的图分割以及图计算模型来迎接挑战并解决问题。

最早成名的图计算系统当属Google的Pregel，该系统采用BSP模型，计算以节点为中心。随后又有一系列图计算框架推出。除了同步（BSP）图计算系统之外，异步图计算系统里的佼佼者当属GraphLab，该系统提出了 GAS 的编程模型。2015 年这个项目已经改名为 Dato，专门推广基于图的大规模机器学习系统。其他典型的图数据处理系统还包括Neo4j系统和微软的Trinity系统等。

4.基于状态的系统

这一类系统主要包括2010年在OSDI会议上推出的Piccolo，以及后来2012年在NIPS会议上Google 推出的开源机器学习系统 DistBelief，再到后来被机器学习领域广泛应用的参数服务器（Parameter Server）架构。本节重点介绍参数服务器这一架构。

MPI由于不支持容错所以很难扩展至大规模集群之中，而MapReduce系统也无法支持大模型机器学习应用，并且节点同步效率较低。用图抽象来做机器学习任务，很多问题都不能很好地求解，例如深度学习中的多层结构。而参数服务器这种以状态为中心的模型则把机器学习的模型存储参数上升为主要组件，并且采用异步机制提升处理能力。参数服务器的概念最早来自亚历克斯·斯莫拉（Alex Smola）于2010年提出的并行LDA架构。它通过采用分布式的Memcached作为存放参数的存储器，这样就提供了有效的机制作用于不同节点同步模型参数。Google 的杰夫·狄思（Jeff Dean）在2012年进一步提出了第一代Google Brain大规模神经网络的解决方案DistBelief。这后，CMU的邢波（Eric Xing）以及百度的李沐都提出了更通用的DistBelief架构。

5.实时流处理系统

实时流处理系统是为高效实时地处理流式数据而提供服务的，更关注数据处理的实时性，能够更加快速地为决策提供支持。流处理是由复杂事件处理（CEP）发展而来的，流处理模式包括两种：连续查询处理模式、可扩展数据流模式。

连续查询处理模式是一个数据流管理系统（DBMS）的必需功能，一般用户数据SQL查询语句，数据流被按照时间模式切割成数据窗口，DBMS在连续流动的数据窗口中执行用户提交的 SQL，并实时返回结构。比较著名的系统包括：STREAM、StreamBase、Aurora、Telegraph等。

可扩展数据流计算模式与此不同，其设计初衷都是模仿MapReduce计算框架的思路，即在对处理时效性有高要求的计算场景下，如何提供一个完善的计算框架，并暴露给用户少量的编程接口，使得用户能够集中精力处理应用逻辑。至于系统性能、低延迟、数据不丢失以及容错等问题，则由计算框架来负责，这样能够大大增加应用开发的生产力。现在流计算的典型框架包括Yahoo的S4、Twitter的Storm系统、LinkedIn的Samza及Spark Streaming等。

2.4.3 分布式资源管理系统

从支持离线处理的MapReduce，到支持在线处理的Storm，从迭代式计算框架Spark到流式处理框架 S4，各种框架诞生于不同的公司或者实验室，它们各有所长，各自解决了某一类应用问题。而在大部分互联网公司中，这几种框架可能都会采用，例如对于搜索引擎公司，可能的技术方案如下：网页建索引采用MapReduce框架，自然语言处理/数据挖掘采用Spark（网页PageRank计算、聚类分类算法等），对性能要求很高的数据挖掘算法用MPI等。考虑到资源利用率、运维成本、数据共享等因素，公司一般希望将所有这些框架部署到一个公共的集群中，让它们共享集群的资源，并对资源进行统一使用，这样，便诞生了资源统一管理与调度平台，典型的代表是Mesos和YARN。

资源统一管理和调度平台具有以下特点。

1.支持多种计算框架

资源统一管理和调度平台应该提供一个全局的资源管理器。所有接入的框架要先向该全局资源管理器申请资源，申请成功之后，再由框架自身的调度器决定资源交由哪个任务使用，也就是说，整个系统是个双层调度器，第一层是统一管理和调度平台提供的，另外一层是框架自身的调度器。

资源统一管理和调度平台应该提供资源隔离。不同的框架中的不同任务往往需要的资源（内存、CPU、网络I/O等）不同，它们运行在同一个集群中，会相互干扰，为此，应该提供一种资源隔离机制避免任务之间由资源争用导致效率下降。

2.扩展性

现有的分布式计算框架都会将系统扩展性作为一个非常重要的设计目标（例如 Hadoop），好的扩展性意味着系统能够随着业务的扩展线性扩展。资源统一管理和调度平台融入多种计算框架后，不应该破坏这种特性，也就是说，统一管理和调度平台不应该成为制约框架进行水平扩展。

3.容错性

同扩展性类似，容错性也是当前分布式计算框架的一个重要设计目标，统一管理和调度平台在保持原有框架的容错特性基础上，自己本身也应具有良好的容错性。

4.高资源利用率

如果采用静态资源分配，也就是每个计算框架分配一个集群，往往由于作业自身的特点或者作业提交频率等原因，集群利用率很低。当各种框架部署到同一个大的集群中，进行统一管理和调度后，各种作业交错且作业提交频率大幅度升高，为资源利用率的提升增加了机会，如图2.14所示。

5.细粒度的资源分配

细粒度的资源分配是指直接按照任务实际需求分配资源，而不是像MapReduce那样将槽位作为资源分配单位。这种分配机制可大大提高资源利用率，如图2.15所示。

当前比较有名的开源资源统一管理和调度平台有两个，Mesos和YARN。Mesos诞生于加州大学伯克利分校的一个研究项目，现已成为Apache Incubator中的项目，当前有一些公司使用Mesos管理集群资源，例如Twitter。

而YARN是下一代MapReduce，是在第一代MapReduce基础上演变而来的，主要是为了解决原始Hadoop扩展性较差，不支持多计算框架而提出的。它完全不同于Hadoop MapReduce，所有代码全部重写。整个平台由Resource Manager和Node Manager组成。与Hadoop MapReduce相比，其最大特点是将JobTracker拆分成Resource Manager和Application Master，其中Resource Manager是全局的资源管理器，仅负责资源分配，而Application Master对应一个具体的应用（如Hadoop job、Spark job等），主要负责应用的资源申请，启动各个任务和运行状态监控（没有调度功能）。

随着容器技术的流行，面向容器的资源管理与调度系统也成为人们关注的焦点，除了上面提到的 Apache Mesos 之外，Docker 的 Swarm 和 Google 的 Kubernetes 也成为这方面的明星。特别是Kubernetes，大有统一容器界的资源管理的趋势。Kubernetes是Google在2014年提出的开源项目，其开发设计思想深受Google的Borg系统影响。

Google很早就认识到了Docker镜像的潜力，并设法在Google Cloud Platform上实现“容器编排”即服务。Google虽然在容器方面有着深厚的经验，但它现有的内部容器和Borg等分布式计算工具是和基础设施紧密耦合的。因此，Google 没有使用任何现有系统的代码，而是重新设计了 Kubernetes对Docker容器进行编排。Kubernetes的目标和构想如下：

为广大应用开发者提供一个强大的工具来管理 Docker 容器的编排，而不再需要和底层基础架构进行交互；

提供标准的部署接口和元语，以获得一致的应用部署的体验和跨云的API；

建立一个模块化的API核心，允许厂商以Kubernetes技术为核心进行系统集成。

2016年3月，Google向CNCF捐赠了Kubernetes，至今仍然保持着在这个项目的贡献者中首位的位置。发展至今，Kubernetes已经从一个单体的庞大代码库向一个生态型多个代码库演进；除了主体代码库之外，还有约40个其他的插件代码库和超过20个的孵化项目。