分布式技术原理（七）：分布式计算_生活中用分布式计算解决的问题

目录

分布式计算

什么是分而治之？

分治法的原理

MapReduce 工作原理

MapReduce 实践应用

总结

分布式计算模式之Stream

Stream 工作原理

---

分布式计算

Hadoop 这个框架主要用于解决海量数据的计算问题。那么，它是如何做到海量数据计算的呢？你可能会想，既然是海量数据，规模这么大，那就分成多个进程，每个进程计算一部分，然后汇总一下结果，就可以提升运算速度了。其实，整个计算流程，我们可以很形象地用一个词来解释，就是“同流合污“，在分布式领域中就叫作 MR 模式，即 Map Reduce 模式

什么是分而治之？

分而治之（Divide-and-Conquer），是计算机处理问题的一个很重要的思想，简称为分治法。

顾名思义，分治法就是将一个复杂的、难以直接解决的大问题，分割成一些规模较小的、可以比较简单的或直接求解的子问题，这些子问题之间相互独立且与原问题形式相同，递归地求解这些子问题，然后将子问题的解合并得到原问题的解。

比如，现在要统计全中国的人口数，由于中国的人口规模很大，如果让工作人员依次统计每个省市的人口数，工作量会非常大。在实际统计中，我们通常会按照省分别统计，比如湖南省的工作人员统计湖南省的人口数，湖北省的工作人员统计湖北省的人口数等，然后汇总各个省的人口数，即可得到全国人口数。这，就是一个非常好的分而治之的例子。

当然，这种分治的思想还广泛应用于计算机科学的各个领域中，分布式领域中的很多场景和问题也非常适合采用这种思想解决，并为此设计出了很多计算框架。比如，Hadoop 中的 MapReduce。问题规模比较大或复杂，且问题可以分解为几个规模较小的、简单的同类型问题进行求解；子问题之间相互独立，不包含公共子问题；子问题的解可以合并得到原问题的解。

根据这些特征，我们可以想到，诸如电商统计全国商品数量时，按区域或省市进行统计，然后将统计结果合并得到最终结果等大数据处理场景，均可以采用分治法。

同时，根据这些特征，我们可以推导出，采用分治法解决问题的核心步骤是：分解原问题。将原问题分解为若干个规模较小，相互独立，且与原问题形式相同的子问题。求解子问题。若子问题规模较小且容易被解决则直接求解，否则递归地求解各个子问题。合并解，就是将各个子问题的解合并为原问题的解。接下来，我们就一起看看分布式系统中分治法的原理和应用吧。

分治法的原理

分布式原本就是为处理大规模应用而生的，所以基于分布式系统，如何分而治之地处理海量数据就是分布式领域中的一个核心问题。Google 提出的 MapReduce 分布式计算模型（Hadoop MapReduce 是 Google 的开源实现），作为分治法的典型代表，最开始用于搜索领域，后来被广泛用于解决各种海量数据的计算问题。下面，我将以 MapReduce 为例，带你了解分治法的抽象模型、工作原理和实践应用。

如下图所示，MapReduce 分为 Map 和 Reduce 两个核心阶段，其中 Map 对应“分”，即把复杂的任务分解为若干个“简单的任务”执行；Reduce 对应着“合”，即对 Map 阶段的结果进行汇总。

在第一阶段，也就是 Map 阶段，将大数据计算任务拆分为多个子任务，拆分后的子任务通常具有如下特征：相对于原始任务来说，划分后的子任务与原任务是同质的，比如原任务是统计全国人口数，拆分为统计省的人口数子任务时，都是统计人口数；并且，子任务的数据规模和计算规模会小很多。多个子任务之间没有依赖，可以独立运行、并行计算，比如按照省统计人口数，统计河北省的人口数和统计湖南省的人口数之间没有依赖关系，可以独立、并行的统计。

第二阶段，也就是 Reduce 阶段，第一阶段拆分的子任务计算完成后，汇总所有子任务的计算结果，以得到最终结果。也就是，汇总各个省统计的人口数，得到全国的总人口数。

MapReduce 工作原理

那么，在 MapReduce 里，各个组件是如何分工完成一个复杂任务的呢？为了解答这个问题，我先带你了解一下 MapReduce 的组件结构。如上图所示，MapReduce 主要包括以下三种组件：

Master，也就是 MRAppMaster，该模块像一个大总管一样，独掌大权，负责分配任务，协调任务的运行，并为 Mapper 分配 map() 函数操作、为 Reducer 分配 reduce() 函数操作。

Mapper worker，负责 Map 函数功能，即负责执行子任务。

Reducer worker，负责 Reduce 函数功能，即负责汇总各个子任务的结果。

基于这三种组件，MapReduce 的工作流程如下所示：

程序从 User Program 开始进入 MapReduce 操作流程。其中图中的“step1，step2，…，step6”表示操作步骤。

step1：User Program 将任务下发到 MRAppMaster 中。然后，MRAppMaster 执行任务拆分步骤，把 User Program 下发的任务划分成 M 个子任务（M 是用户自定义的数值）。假设，MapReduce 函数将任务划分成了 5 个，其中 Map 作业有 3 个，Reduce 作业有 2 个；集群内的 MRAppMaster 以及 Worker 节点都有任务的副本。

step2：MRAppMaster 分别为 Mapper 和 Reducer 分配相应的 Map 和 Reduce 作业。Map 作业的数量就是划分后的子任务数量，也就是 3 个；Reduce 作业是 2 个。

step3：被分配了 Map 作业的 Worker，开始读取子任务的输入数据，并从输入数据中抽取出 <key, value> 键值对，每一个键值对都作为参数传递给 map() 函数。

step4：map() 函数的输出结果存储在环形缓冲区 kvBuffer 中，这些 Map 结果会被定期写入本地磁盘中，被存储在 R 个不同的磁盘区。这里的 R 表示 Reduce 作业的数量，也是由用户定义的。在这个案例中，R=2。此外，每个 Map 结果的存储位置都会上报给 MRAppMaster。

step5：MRAppMaster 通知 Reducer 它负责的作业在哪一个分区，Reducer 远程读取相应的 Map 结果，即中间键值对。当 Reducer 把它负责的所有中间键值对都读过来后，首先根据键值对的 key 值对中间键值对进行排序，将相同 key 值的键值对聚集在一起，从而有利于 Reducer 对 Map 结果进行统计。

step6：Reducer 遍历排序后的中间键值对，将具有相同 key 值的键值对合并，并将统计结果作为输出文件存入负责的分区中。

从上述流程可以看出，整个 MapReduce 的工作流程主要可以概括为 5 个阶段，即：Input（输入）、Splitting（拆分）、Mapping（映射）、Reducing（化简）以及 Final Result（输出）。

所有 MapReduce 操作执行完毕后，MRAppMaster 将 R 个分区的输出文件结果返回给 User Program，用户可以根据实际需要进行操作。比如，通常并不需要合并这 R 个输出文件，而是将其作为输入交给另一个 MapReduce 程序处理。

MapReduce 实践应用

通过上述的流程描述，你大概已经知道 MapReduce 的工作流程了。接下来，我和你分享一个电商统计用户消费记录的例子，再帮你巩固一下 MapReduce 的功能吧。需要注意的是，为了方便理解，我对下面用的数据做了一定的处理，并不完全是真实场景中的数据。每隔一段时间，电商都会统计该时期平台的订单记录，从而分析用户的消费倾向。在不考虑国外消费记录的前提下，全国范围内的订单记录已经是一个很大规模的工程了。

在前面的文章中我也提到过，电商往往会在每个省份、多个城市分布式地部署多个服务器，用于管理某一地区的平台数据。因此，针对全国范围内的消费统计，可以拆分成对多个省份的消费统计，并再一次细化到统计每一个城市的消费记录。为方便描述，假设我们现在要统计苏锡常地区第二季度手机订单数量 Top3 的品牌。我们来看看具体的统计步骤吧。

任务拆分（Splitting 阶段）。根据地理位置，分别统计苏州、无锡、常州第二季度手机订单 Top3 品牌，从而将大规模任务划分为 3 个子任务。

通过循环调用 map() 函数，统计每个品牌手机的订单数量。其中，key 为手机品牌，value 为手机购买数量（单位：万台）。如下图 Mapping 阶段所示（为简化描述，图中直接列出了统计结果）。

与前面讲到的计算流程不同的是，Mapping 阶段和 Reducing 阶段中间多了一步 Shuffling 操作。Shuffling 阶段主要是读取 Mapping 阶段的结果，并将不同的结果划分到不同的区。在大多数参考文档中，Mapping 和 Reducing 阶段的任务分别定义为映射以及归约。但是，在映射之后，要对映射后的结果进行排序整合，然后才能执行归约操作，因此往往将这一排序整合的操作单独放出来，称之为 Shuffling 阶段。

Reducing 阶段，归并同一个品牌的购买次数。得到苏锡常地区第二季度 Top3 品牌手机的购买记录。

流程可以看出，Map/Reduce 作业和 map()/reduce() 函数是有区别的：

Map 阶段由一定数量的 Map 作业组成，这些 Map 作业是并发任务，可以同时运行，且操作重复。Map 阶段的功能主要由 map() 函数实现。每个 Map 作业处理一个子任务（比如一个城市的手机消费统计），需要调用多次 map() 函数来处理（因为城市内不同的居民倾向于不同的手机）。

Reduce 阶段执行的是汇总任务结果，遍历 Map 阶段的结果从而返回一个综合结果。与 Reduce 阶段相关的是 reduce() 函数，它的输入是一个键（key）和与之对应的一组数据（values），其功能是将具有相同 key 值的数据进行合并。Reduce 作业处理一个分区的中间键值对，期间要对每个不同的 key 值调用一次 reduce() 函数。在完成 Map 作业后，每个分区中会存在多个临时文件；而执行完 Reduce 操作后，一个分区最终只有一个输出文件。

MapReduce 是一种分而治之的计算模式，在分布式领域中，除了典型的 Hadoop 的 MapReduce(Google MapReduce 的开源实现)，还有 Fork-Join，Fork-Join 是 Java 等语言或库提供的原生多线程并行处理框架，采用线程级的分而治之计算模式。它充分利用多核 CPU 的优势，以递归的方式把一个任务拆分成多个“小任务”，把多个“小任务”放到多个处理器上并行执行，即 Fork 操作。当多个“小任务”执行完成之后，再将这些执行结果合并起来即可得到原始任务的结果，即 Join 操作。

虽然 MapReduce 是进程级的分而治之计算模式，但与 Fork-Join 的核心思想是一致的。因此，Fork-Join 又被称为 Java 版的 MapReduce 框架。但，MapReduce 和 Fork-Join 之间有一个本质的区别：Fork-Join 不能大规模扩展，只适用于在单个 Java 虚拟机上运行，多个小任务虽然运行在不同的处理器上，但可以相互通信，甚至一个线程可以“窃取”其他线程上的子任务。

MapReduce 可以大规模扩展，适用于大型计算机集群。通过 MapReduce 拆分后的任务，可以跨多个计算机去执行，且各个小任务之间不会相互通信。

总结

所谓分而治之，就是将一个复杂的、难以直接解决的大问题，分割成一些规模较小的、可以直接求解的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将子问题的解合并以后就是原问题的解。分布式计算模型 MapReduce 就运用了分而治之的思想，通过 Map 操作将大任务分成多个较小的任务去执行，得到的多个结果再通过 Reduce 操作整合成一个完整的结果。所以，今天我就以 MapReduce 为例，与你讲述了分布式领域中分治法的模型、原理与应用。

最后，我将今天涉及的核心知识点梳理为了一张思维导图，以方便你理解与记忆。分而治之的思想，是简单且实用的处理复杂问题的方法。所以无论是计算机领域还是其他研究领域亦或日常生活中，我们都可以用分治法去处理很多复杂庞大的问题，将大问题划分成多个小问题，化繁为简、化整为零。

其实，很多算法并不是凭空创造出来的，都是源于生活并服务于生活的。在日常工作学习中，我们对眼前的问题一筹莫展时，就可以将其化繁为简，从最简单的小问题出发，逐渐增加问题的规模，进而解决这个复杂的问题。同样的道理，我们也可以借鉴生活中的例子去解决专业问题。

分布式计算模式之Stream

MapReduce 模式的核心思想是，将大任务拆分成多个小任务，针对这些小任务分别计算后，再合并各小任务的结果以得到大任务的计算结果，任务运行完成后整个任务进程就结束了，属于短任务模式。但任务进程的启动和停止是一件很耗时的事儿，因此 MapReduce 对处理实时性的任务就不太合适了。

实时性任务主要是针对流数据的处理，对处理时延要求很高，通常需要有常驻服务进程，等待数据的随时到来随时处理，以保证低时延。处理流数据任务的计算模式，在分布式领域中叫作 Stream。近年来，由于网络监控、传感监测、AR/VR 等实时性应用的兴起，一类需要处理流数据的业务发展了起来。比如各种直播平台中，我们需要处理直播产生的音视频数据流等。这种如流水般持续涌现，且需要实时处理的数据，我们称之为流数据。

总结来讲，流数据的特征主要包括以下 4 点：

• 数据如流水般持续、快速地到达；

• 海量数据规模，数据量可达到 TB 级甚至 PB 级；

• 对实时性要求高，随着时间流逝，数据的价值会大幅降低；

• 数据顺序无法保证，系统无法控制将要处理的数据元素的顺序。

在分布式领域中，处理流数据的计算模式，就是流计算，也叫作 Stream。这个名字是不是非常形象呢？流计算的职责是实时获取来自不同数据源的海量数据，进行实时分析处理，获得有价值的信息。它是一个对实时性要求非常高的计算形式，如果数据处理不及时，很容易导致过时、没用的结果，这时就需要对造成的后果进行“背锅”。从这个角度来说，Stream 可谓“一门背锅的艺术”。类比于水流的持续不断且变幻莫测，流数据也是以大量、快速、时变的流形式持续在应用中产生，因此流计算一般用于处理数据密集型应用。

比如百度、淘宝等大型网站中，每天都会产生大量的流数据，这些数据包括用户的搜索内容、用户的浏览记录等。实时采集用户数据，并通过流计算进行实时数据分析，可以了解每个时刻数据流的变化情况，甚至可以分析用户的实时浏览轨迹，从而进行个性化内容实时推荐，提高用户体验。

此外，我们常用的爱奇艺、腾讯等音视频平台，对电影、电视剧等数据的处理，也是采用了流计算模式。那么，这种实时的流计算到底是如何运行的呢？接下来，我们就一起看看流计算的工作原理吧。

Stream 工作原理

我在上一篇文章中与你介绍的 MapReduce，是一种批量计算的形式。这种模式下，会先收集数据并将其缓存起来，等到缓存写满时才开始处理数据。因此，批量计算的一个缺点就是，从数据采集到得到计算结果之间经历的时间很长，而流计算强调的是实时性，数据一旦产生就会被立即处理，当一条数据被处理完成后，会序列化存储到缓存中，然后立刻通过网络传输到下一个节点，由下一个节点继续处理，而不是像 MapReduce 那样，等到缓存写满才开始处理、传输。为了保证数据的实时性，在流计算中，不会存储任何数据，就像水流一样滚滚向前。流计算属于持续性、低时延、事件驱动型的计算作业，从这些分析中可以看出，使用流计算进行数据处理，一般包括 3 个步骤，如下图所示。

第一步，提交流式计算作业。流式计算作业是一种常驻计算服务，比如实时交通监测服务、实时天气预报服务等。对于流式计算作业，首先必须预先定义计算逻辑，并提交到流计算系统中，使得流计算系统知道自己该如何处理数据。系统在整个运行期间，由于收集的是同一类型的数据、执行的是同一种服务，因此流式计算作业的处理逻辑不可更改。如果用户停止当前作业运行后再次提交作业，由于流计算不提供数据存储服务，因此之前已经计算完成的数据无法重新再次计算。

第二步，加载流式数据进行流计算。流式计算作业一旦启动将一直处于等待事件触发的状态，一旦有小批量数据进入流式数据存储，系统会立刻执行计算逻辑并迅速得到结果。从上图中我们可以看出，在流计算系统中，有多个流处理节点，流处理节点会对数据进行预定义的处理操作，并在处理完后按照某种规则转发给后续节点继续处理。此外，流计算系统中还存在管理节点，主要负责管理处理节点以及数据的流动规则。其中，处理节点的个数以及数据转发的规则，都在第一步作业提交时定义。

第三步，持续输出计算结果。流式计算作业在得到小批量数据的计算结果后，可以立刻将结果数据写入在线 / 批量系统，无需等待整体数据的计算结果，以进一步做到实时计算结果的实时展现。到这里，我们小结一下吧。流计算不提供流式数据的存储服务，数据是持续流动的，在计算完成后就会立刻丢弃。流计算适用于需要处理持续到达的流数据、对数据处理有较高实时性要求的场景。为了及时处理流数据，流计算框架必须是低延迟、可扩展、高可靠的。

流计算的应用场景有很多，比如它是网络监控、传感监测、AR/VR、音视频流等实时应用的发展的基础。所以，目前流计算相关的框架和平台也有很多了，主流的划分方式是将其分为如下 3 类：

1.商业级的流计算平台，比如 IBM 的 InfoSphere Streams 和 TIBCO 的 StreamBase。InfoSphere Streams 支持同时分析多种数据类型并实时执行复杂计算。StreamBase 是一个用于实时分析的软件，可以快速构建分析系统，即时做出决策。StreamBase 可以为投资银行、对冲基金、政府机构等提供实时数据分析服务。

2.开源流计算框架，典型代表是 Apache Storm（由 Twitter 开源）和 S4（由 Yahoo 开源）。Storm 是一个分布式的、容错的实时计算系统，可以持续进行实时数据流处理，也可以用于分布式 RPC。S4 是一个通用的、分区容错的、可扩展的、可插拔的分布式流式系统。这些开源的分布式流计算系统由于具备开源代码，因此比较适合开发人员将其搭建在自身业务系统中。

3.各大公司根据自身业务特点而开发的流计算框架，比如 Facebook 的 Puma、百度的 Dstream（旨在处理有向无环的数据流）、淘宝的银河流数据处理平台（一个通用的、低延迟、高吞吐、可复用的流数据实时计算系统）。

除了这些框架外，我们还会经常听到 Spark、Flink 等。Spark 和 Flink 与 Storm 框架的不同之处在于，Spark 和 Flink 除了支持流计算，还支持批量计算，因此我没有直接将它们列入上述的流计算框架中。如果你的业务中需要用到或者需要参考某种计算框架或者平台的话，可以再参考其官方文档或者相关的技术文章。

在流计算中，数据具有时效性，因此在 5G 以及人工智能应用的驱动下，专注于实时处理的流计算越来越得到广泛的关注。流计算的低延时、易扩展等性能非常适用于对时延要求高的终端应用（比如直播中音视频的处理等），从而极大提高用户的服务体验。而批量计算适用于对时延要求低的任务。

在实际运用中，可以根据计算要求，选择不同的计算模式。我将这两种计算模式的特点，总结为了一张表格，以帮助你理解、记忆，以及选择适合自己业务场景的计算模式。