关于分布式:数据系统派生数据系统批处理系统

Web 和越来越多基于 HTTP/REST 的 API 使得申请 / 响应的交互模式变得如此广泛，以至于很容易将其视为天经地义。然而咱们该当记住，这并不是构建零碎的惟一路径，其余办法也有其长处。上面咱们来辨别三种不同类型的零碎：

在线服务（或称在线零碎）

服务期待客户申请或指令的达到。当收到申请或指令时，服务试图尽可能快地解决它，并发回一个响应。响应工夫通常是服务性能的次要掂量指标，而可用性同样十分重要。

批处理零碎（或称离线零碎）

批处理零碎接管大量的输出数据，运行一个作业来解决数据，并产生输入数据。作业往往须要执行一段时间，所以用户通常不会期待作业实现。相同，批量作业通常会定期运行（例如，每天一次）。批处理作业的次要性能衡量标准通常是吞吐量（解决肯定大小的输出数据集所需的工夫）。

流解决零碎（或称近实时零碎）

流解决介于在线与离线 / 批处理之间（所以有时称为近实时或近线解决）。与批处理零碎相似，流解决零碎解决输出并产生输入（而不是响应申请）。然而，流式作业在事件产生后不久即可对事件进行解决，而批处理作业则应用固定的一组输出数据进行操作。这种差别使得流解决零碎比批处理零碎具备更低的提早。流解决是在批处理的根底上进行的。

批处理是构建牢靠、可扩大与可保护利用的重要组成部分。例如，2004 年发表的驰名批处理算法 MapReduce“使得 Google 具备如此大规模的可扩展性能力”。该算法随后在各种开源数据系统中被陆续实现，包含 Hadoop、CouchDB 和 MongoDB。

咱们从一个简略的例子开始。假如有一个 Nginx 服务器，每次响应申请时都会在日志文件中追加一行记录，应用的是默认的拜访日志格局。

假如想找出网站中前五个最受欢迎的网页，能够在 UNIX shell 中执行下列操作：

cat /var/log/nginx/access.log |   ①
awk '{print $7}'   |   ②
sort                        |   ③
uniq -c                  |   ④
sort -r -n              |   ⑤
head -n 5                 ⑥

① 读取日志文件。
② 将每一行按空格宰割成不同的字段，每行只输入第七个字段，即申请的 URL 地址。
③ 按字母顺序排列 URL 地址列表。如果某个 URL 被申请过 n 次，那么排序后，后果中将蕴含间断 n 次的反复 URL。
④ uniq 命令通过查看两条相邻的行是否雷同来过滤掉其输出中的反复行。- c 选项为输入一个计数器：对于每个不同的 URL，它会报告输出中呈现该 URL 的次数。
⑤ 第二种排序按每行起始处的数字（-n）排序，也就是 URL 的申请次数。而后以反向（-r）程序输入后果，即后果中最大的数字首先返回。
⑥ 最初，head 只输入输出中的前五行（-n 5），并抛弃其余数据。

该命令序列的输入如下所示：

4189   /favicon.ico
3631   /2013/05/24/improving-security-of-ssh-private-keys.html
2124   /2012/12/05/schema-evolution-in-avro-protocol-buffers-thrift.html
1369   /
915     /css/typography.css

该命令行的功能强大，将在几秒钟内解决千兆字节的日志文件，你能够轻松批改剖析指令以满足本人的需要。例如，如果要省略 CSS 文件，将 awk 参数更改为 '$7 !~ /\.css$/ {print $7}' 即可。如果想得到申请次数最多的客户端 IP 地址而不是页面，那么就将 awk 参数更改为'{print $1}'。

排序与内存中聚合

你也能够写一个简略的程序来做同样的事件，例如 Ruby。Ruby 脚本须要一个 URL 的内存哈希表，其中每个 URL 地址都会映射到被拜访的次数。UNIX 流水线例子中则没有这样的哈希表，而是依赖于对 URL 列表进行排序，在这个 URL 列表中屡次呈现的雷同 URL 仅仅是简略反复。

哪种办法更好呢？这取决于有多少个不同的网址。对于大多数中小型网站，兴许能够在内存中存储所有不同的 URL，并且能够为每个 URL 提供一个计数器。在此示例中，作业的工作集仅取决于不同 URL 的数量：如果单个 URL 有一百万条日志条目，则哈希表中所需的空间表依然只是一个 URL 加上计数器的大小。如果这个工作集足够小，那么内存哈希表工作失常。

如果作业的工作集大于可用内存，则排序办法的长处是能够高效地应用磁盘。这与“SSTables 和 LSM-Tree”中探讨的原理雷同：数据块能够在内存中排序并作为段文件写入磁盘，而后多个排序的段能够合并为一个更大的排序文件。归并排序在磁盘上有良好的程序拜访模式。

GNU Coreutils (Linux）中的 sort 实用程序通过主动唤出到磁盘的形式反对解决大于内存的数据集，且排序能够主动并行化以充分利用多核。这意味着之前简略的 UNIX 命令链能够很容易地扩大到大数据集，而不会耗尽内存。从磁盘读取输出文件倒可能会成为瓶颈。

咱们能够非常容易地应用相似例子中命令链来剖析日志文件，这是 UNIX 的要害设计思维之一。通过管道将程序连接起来的想法成为现在的 UNIX 哲学，一系列的在开发人员和 UNIX 用户中逐步变得风行的设计准则。

对于这种哲学有更为残缺的形容：

每个程序做好一件事。如果要做新的工作，则建设一个全新的程序，而不是通过减少新“特色”使旧程序变得更加简单。
期待每个程序的输入成为另一个尚未确定的程序的输出。不要将输入与无关信息混同在一起。防止应用严格的表格状或二进制输出格局。不要应用交互式输出。
尽早尝试设计和构建软件，甚至是操作系统。须要扔掉那些蠢笨的局部时不要犹豫，并立刻进行重建。
优先应用工具来加重编程工作，即便你不得不额定破费工夫去构建工具，并且预期在应用实现后会将其中一些工具扔掉。

这种哲学（自动化、疾速原型设计、增量式迭代、测试敌对、将大型项目合成为可治理的模块等）听起来十分像麻利开发与 DevOps 静止。

像 bash 这样的 UNIX shell 能够让咱们轻松地将这些小程序组合成弱小的数据处理作业。只管这些程序中是由不同人所编写的，但它们能够灵便地联合在一起。那么，UNIX 是如何实现这种可组合性的呢？

对立接口

如果心愿某个程序的输入成为另一个程序的输出，也就意味着这些程序必须应用雷同的数据格式，换句话说，须要兼容的接口。如果你心愿可能将任何程序的输入连贯到任何程序的输出，那意味着所有程序都必须应用雷同的输出 / 输入接口。

在 UNIX 中，这个接口就是文件（更精确地说，是文件描述符），文件只是一个有序的字节序列。这是一个非常简单的接口，因而能够应用雷同的接口示意许多不同的货色：文件系统上的理论文件，到另一个过程（UNIX socket，stdin，stdout）的通信通道，设施驱动程序（比方 /dev/audio 或 /dev/lpo），示意 TCP 连贯的套接字等。

依照常规，许多（但不是全副）UNIX 程序将这个字节序列视为 ASCII 文本。awk，sort，uniq 和 head 都将它们的输出文件视为由 \n（换行符，ASCII OxOA）字符分隔的记录列表，所有这些程序都应用规范雷同的记录分隔符以反对交互操作。对每条记录（即一行输出）的解析则没有明确定义。

逻辑与布线拆散

UNIX 工具的另一个特点是应用规范输出和规范输入。如果运行一个程序而不指定任何参数，那么规范输出来自键盘，规范输入为屏幕。当然，也能够将文件作为输出或将输入重定向到文件。管道容许将一个过程的 stdout 附加到另一个过程的 stdin（具备小的内存缓冲区，而不须要将全副两头数据流写入磁盘）。

程序依然能够在须要时间接读取和写入文件。但如果程序不依赖特定的文件门路，只应用 stdin 和 stdout，则 UNIX 工具能够达到最佳成果。这容许 shell 用户以任何他们想要的形式连贯输出和输入，程序并不知道也不关怀输出来自哪里以及输入到哪里。也能够说这是一种松耦合，前期绑定或管制反转。将输出 / 输入的布线连贯与程序逻辑离开，能够更容易地将小工具组合成更大的零碎。

用户甚至能够编写本人的程序，并将它们与操作系统提供的工具组合在一起。程序只须要从 stdin 读取输出并输入至 stdout，从而参加数据处理流水线。

通明与测试

UNIX 工具如此胜利的局部起因在于，它能够十分轻松地察看事件的停顿：

UNIX 命令的输出文件通常被视为是不可变的。这意味着能够随便运行命令，尝试各种命令行选项，而不会损坏输出文件。
能够在任何时候完结流水线，将输入管道输送到 less，而后查看它是否具备预期的模式。这种查看能力对调试十分有用。
能够将流水线某个阶段的输入写入文件，并将该文件用作下一阶段的输出。这使得用户能够重新启动前面的阶段，而无需从新运行整个流水线。

然而，UNIX 工具的最大局限在于它们只能在一台机器上运行，而这正是像 Hadoop 这样的工具的工作场景。

MapReduce 有点像散布在数千台机器上的 UNIX 工具。和大多数 UNIX 工具一样，运行 MapReduce 作业通常不会批改输出，除了生成输入外没有任何副作用。

UNIX 工具应用 stdin 和 stdout 作为输出和输入，而 MapReduce 作业在分布式文件系统上读写文件。在 Hadoop 的 MapReduce 实现中，该文件系统被称为 HDFS。除 HDFS 外，还有其余各种分布式文件系统，诸如 Amazon S3，Azure Blob 存储和 OpenStack Swift 对象存储服务也有很多相似之处。

与网络连接存储（NAS）和存储区域网络（SAN）架构的共享磁盘办法相比，HDFS 基于无共享准则。共享磁盘存储由集中式存储设备实现，通常应用定制硬件和非凡网络基础设施。而无共享方法则不须要非凡硬件，只须要通过传统数据中心网络连接的计算机。

HDFS 蕴含一个在每台机器上运行的守护过程，并会凋谢一个网络服务以容许其余节点拜访存储在该机器上的文件（假如数据中心的每台节点都附带一些本地磁盘）。名为 NameNode 的地方服务器会跟踪哪个文件块存储在哪台机器上。因而，从概念上讲，HDFS 创立了一个宏大的文件系统，来充分利用每个守护过程机器上的磁盘资源。

思考到机器和磁盘的容错，文件块被复制到多台机器上。复制意味着位于多个机器上的雷同数据的多个正本；或者像 Reed-Solomon 代码这样的纠删码计划，相比于正本技术，纠删码能够以更低的存储开销来复原数据。在分布式文件系统中，文件拜访和复制是在传统的数据中心网络上实现的，而不依赖非凡的硬件。

MapReduce 是一个编程框架，能够应用它编写代码来解决 HDFS 等分布式文件系统中的大型数据集。最简略的了解办法是参考本章后面的“简略日志剖析”中的 Web 日志剖析示例。MapReduce 中的数据处理模式与此十分类似：

读取一组输出文件，并将其分解成记录。在 Web 日志示例中，每个记录都是日志中的一行。
调用 mapper 函数从每个输出记录中提取一个键值对。在后面的例子中，mapper 函数是awk '{print $7}'：它提取 URL（$7）作为关键字。
按关键字将所有的键值对排序。在日志示例中，这由第一个 sort 命令实现。
调用 reducer 函数遍历排序后的键值对。如果同一个键呈现屡次，排序会使它们在列表中相邻，所以很容易组合这些值，而不用在内存中保留过多状态。在后面的例子中，reducer 是由 uniq - c 命令实现的，该命令对具备雷同关键字的相邻记录进行计数。

这四个步骤能够由一个 MapReduce 作业执行。步骤 2（map）和 4（reduce）是用户编写自定义数据处理的代码。步骤 1（将文件分解成记录）由输出格局解析器解决。步骤 3 中的排序步骤 sort 隐含在 MapReduce 中，无需用户编写，mapper 的输入始终会在排序之后再传递给 reducer。

要创立 MapReduce 作业，须要实现两个回调函数，即 mapper 和 reducer，其行为如下：

Mapper

每个输出记录都会调用一次 mapper 程序，其工作是从输出记录中提取关键字和值。对于每个输出，它能够生成任意数量的键值对（包含空记录）。它不会保留从一个输出记录到下一个记录的任何状态，因而每个记录都是独立解决的。

Reducer

MapReduce 框架应用由 mapper 生成的键值对，收集属于同一个关键字的所有值，并应用迭代器调用 reducer 以应用该值的汇合。Reducer 能够生成输入记录（例如雷同 URL 呈现的次数）。

在 Web 日志示例中，第 5 步由第二个 sort 命令按申请数对 URL 进行排序。在 MapReduce 中，如果须要第二个排序阶段，则能够编写另一个 MapReduce 作业并将第一个作业的输入用作第二个作业的输出。这样来看的话，mapper 的作用是将数据放入一个适宜排序的表单中，而 reducer 的作用则是解决排序好的数据。

MapReduce 的分布式执行

下图展现了 Hadoop MapReduce 作业中的数据流。其并行化基于分区实现：作业的输出通常是 HDFS 中的一个目录，且输出目录中的每个文件或文件块都被视为一个独自的分区，能够由一个独自的 map 工作来解决。

一个输出文件的大小通常是几百兆字节。只有有足够的闲暇内存和 CPU 资源，MapReduce 调度器会尝试在输出文件正本的某台机器上运行 mapper 工作。这个原理被称为将计算凑近数据：它防止将输出文件通过网络进行复制，缩小了网络负载，进步了拜访局部性。

大多数状况下，MapReduce 框架首先要复制代码到该节点，而后启动 map 工作并开始读取输出文件，每次将一条记录传递给回调函数 mapper。mapper 的输入由键值对组成。

Reduce 工作中的计算也被宰割成块。Map 工作的数量由输出文件块的数量决定，而 reduce 工作的数量则是由作业的作者来配置的。为了确保具备雷同关键字的所有键值对都在雷同的 reducer 工作中解决，框架应用关键字的哈希值来确定哪个 reduce 工作接管特定的键值对。

键值对必须进行排序。如果数据集太大，可能无奈在单台机器上应用惯例排序算法。事实上，排序是分阶段进行的。首先，每个 map 工作都基于关键字哈希值，依照 reducer 对输入进行分区。每一个分区都被写入 mapper 程序所在本地磁盘上的已排序文件，应用的技术相似“SSTables 和 LSM-Trees”。

当 mapper 实现读取输出文件并写入通过排序的输入文件，MapReduce 调度器就会告诉 reducer 开始从 mapper 中获取输入文件。reducer 与每个 mapper 相连接，并依照其分区从 mapper 中下载排序后的键值对文件。依照 reducer 分区，排序和将数据分区从 mapper 复制到 reducer，这样一个过程被称为 shuffle。

reduce 工作从 mapper 中获取文件并将它们合并在一起，同时保持数据的排序。因而，如果不同的 mapper 应用雷同的关键字生成记录，则这些记录会在合并后的 reducer 输出中位于相邻地位。

reducer 通过关键字和迭代器进行调用，而迭代器逐渐扫描所有具备雷同关键字的记录。reducer 能够应用任意逻辑来解决这些记录，并且生成任意数量的输入记录。这些输入记录被写入分布式文件系统中的文件。

MapReduce 工作流

单个 MapReduce 作业能够解决的问题范畴无限。回顾一下日志剖析的例子，一个 MapReduce 作业能够确定每个 URL 页面的浏览次数，但不是最受欢迎的那些 URL，因为这须要第二轮排序。

因而，将 MapReduce 作业链接到工作流中是十分广泛的，这样，作业的输入将成为下一个作业的输出。Hadoop MapReduce 框架对工作流并没有任何非凡的反对，所以链接形式是通过目录名隐式实现的：第一个作业必须配置为将其输入写入 HDFS 中的指定目录，而第二个作业必须配置为读取雷同的目录名作为输出。从 MapReduce 框架的角度来看，它们依然是两个独立的作业。

因而，链接形式的 MapReduce 作业并不像 UNIX 命令流水线（它间接将一个过程的输入作为输出传递至另一个过程，只须要很小的内存缓冲区），而更像是一系列命令，其中每个命令的输入被写入临时文件，下一个命令从临时文件中读取。

在数据库中，如果执行的查问只波及大量记录，那么数据库通常会应用索引来减速查找。如果查问波及到 join 操作，则可能须要对多个索引进行查找。然而，MapReduce 没有索引的概念，至多不是通常意义上的索引。

在批处理的背景下探讨 join 时，咱们次要是解决数据集内存在关联的所有事件。例如，假如一个作业是同时为所有用户解决数据，而不仅仅是为一个特定的用户查找数据（这能够通过索引更高效地实现）。

示例：剖析用户流动事件

下图给出了批处理作业中典型的 join 示例。图中左侧是事件日志，形容登录用户在网站上的流动右侧是用户数据库。

剖析工作可能须要将用户流动与用户形容信息相关联：例如，如果形容中蕴含用户年龄或出生日期，则零碎能够确定哪些年龄组最受欢迎。然而，流动事件中仅蕴含用户标识，而不蕴含残缺的用户形容信息。而在每个流动事件中嵌入这些形容信息又会太节约。因而，流动事件须要与用户形容数据库进行 join。

join 的最简略实现是一一遍历流动事件，并在（近程服务器上的）用户数据库中查问每个遇到的用户 ID。该计划首先是可行的，但性能会十分差：吞吐量将受到数据库服务器的往返工夫的限度，本地缓存的有效性将很大水平上取决于数据的散布，并且同时运行的大量并行查问很容易使数据库不堪重负。

为了在批处理过程中实现良好的吞吐量，计算必须（尽可能）在一台机器上进行。如果通过网络对每条记录进行随机拜访则申请太慢。而且，思考到近程数据库中的数据可能会发生变化，查问近程数据库意味着会减少批处理作业的不确定性。

因而，更好的办法是获取用户数据库的正本（例如，应用 ETL 过程从数据库备份中提取数据），并将其放入与用户流动事件日志雷同的分布式文件系统。而后，能够将用户数据库放在 HDFS 中的一组文件中，并将用户流动记录放在另一组文件中，应用 MapReduce 将所有相干记录集中到一起，从而无效地解决它们。

排序 - 合并 join

mapper 的目标是从每个输出记录中提取关键字和值，在上图的例子中，这个关键字就是用户 ID：一组 mapper 会扫描流动事件（提取用户 ID 作为关键字，而流动事件作为值），而另一组 mapper 将会遍历用户数据库（提取用户 ID 作为关键字，用户出生日期作为值）。过程如下图所示。

当 MapReduce 框架通过关键字对 mapper 输入进行分区，而后对键值对进行排序时，后果是所有流动事件和用户 ID 雷同的用户记录在 reducer 的输出中彼此相邻。MapReduce 作业能够对记录进行排序，以便 reducer 会首先看到用户数据库中的记录，而后按工夫戳程序查看流动事件，这种技术称为次级排序。

而后 reducer 能够很容易地执行真正的 join 逻辑：为每个用户 ID 调用一次 reducer 函数。因为次级排序，第一个值应该是来自用户数据库的出生日期记录，Reducer 将出生日期存储在局部变量中，而后应用雷同的用户 ID 遍历流动事件，输入相应的已观看网址和观看者年龄。随后的 MapReduce 作业能够计算每个 URL 的查看者年龄散布，并按年龄组进行聚合。

因为 reducer 每次解决一个特定用户 ID 的所有记录，因而只须要将用户记录在内存中保留一次，而不须要通过网络收回任何申请。这个算法被称为排序 - 合并 join，因为 mapper 的输入是按关键字排序的，而后 reducer 将来自 join 两侧的已排序记录列表合并在一起。

分组

除了 join 之外，“将相干数据放在一起”模式的另一个常见用法是通过某个关键字（如 SQL 中的 GROUP BY 子句）对记录进行分组。所有具备雷同关键字的记录造成一个组，而后在每个组内执行某种聚合操作。

应用 MapReduce 实现这种分组操作的最简略办法是设置 mapper，使其生成的键值对应用所需的分组关键字。而后，分区和排序过程将雷同 reducer 中所有具备雷同关键字的记录汇合在一起。因而，在 MapReduce 上实现的分组和 join 看起来十分类似。

分组的另一个常见用处是收集特定用户会话的所有流动事件，以便发现用户的流动序列，称为会话流程。例如，能够应用这种剖析来确定抉择网站新版本的用户是否比抉择旧版本（A/ B 测试）的用户更有可能产生购买行为，或计算某个营销流动是否无效。

如果有多个 Web 服务器解决用户申请，则特定用户的流动事件很可能扩散在各个不同服务器的日志文件中。能够通过应用会话 cookie、用户 ID 或相似的标识符作为分组关键字来实现拜访流程，将特定用户的所有流动事件放在一起，同时将不同用户的事件调配到不同的分区。

解决数据歪斜

如果与单个关键字相干的数据量十分大，那么会毁坏掉“将所有具备雷同关键字的记录放在一起”的模式。例如，在社交网络中，大多数用户会有上百人关注者，但多数名人则可能有数百万的追随者。

在单个 reducer 中收集与名人相干的所有流动可能会导致重大的数据歪斜，某个 reducer 必须解决比其余 reducer 更多的记录。因为 MapReduce 作业只有在其所有 mapper 和 reducer 都实现时能力实现，因而所有后续作业必须期待最慢的 reducer 实现之后能力开始。

如果 join 输出中存在热键，则能够应用算法进行弥补。例如，Pig 中的歪斜 join 办法首先运行一个抽样作业来确定哪些属于热键。在真正开始执行 join 时，mapper 将任何与热键无关的记录发送到随机抉择的若干个 reducer 中的一个（传统 MapReduce 基于关键字哈希来确定性地抉择 reducer）。对于 join 的其余输出，与热键相干的记录须要被复制到所有解决该关键字的 reducer 中。

这种技术将解决热键的工作扩散到多个 reducer 上，能够更好地实现并行处理，代价是不得不将 join 的其余输出复制到多个 reducer。这种技术也十分相似“负载歪斜与热点”所探讨的技术，应用随机化来缓解分区数据库中的热点。

Hive 的歪斜 join 优化采取了另一种办法。它须要在表格元数据中明确指定热键，并将与这些键相干的记录与其余文件离开寄存。在该表上执行 join 时，它将对热键应用 map 端 join。

应用热键对记录进行分组并汇总时，能够分两个阶段进行分组。第一个 MapReduce 阶段将记录随机发送到 reducer，以便每个 reducer 对热键的记录子集执行分组，并为每个键输入更紧凑的聚合值。而后第二个 MapReduce 作业将来自所有第一阶段 reducer 的值合并为每个键的繁多值。

上一节形容的 join 算法在 reducer 中执行理论的 join 逻辑，因而被称为 reduce 端 join。mapper 负责筹备输出数据：从每个输出记录中提取关键字和值，将键值对调配给 reducer 分区，并按关键字排序。

Reduce 端 join 办法的长处是不须要对输出数据做任何假如：无论其属性与构造如何，mapper 都能够将数据处理好以筹备 join。毛病是所有这些排序，复制到 reducer 以及合并 reducer 输出可能会是十分低廉的操作，这取决于可用的内存缓冲区，当数据通过 MapReduce 阶段时，数据可能须要写入磁盘若干次。

另一方面，如果能够对输出数据进行某些假如，则能够通过应用所谓的 map 端 join 来加快速度。这种办法应用了一个缩减版本的 MapReduce 作业，其中没有 reducer，也没有排序。相同，每个 mapper 只需从分布式文件系统中读取输出文件块，而后将输入文件写入文件系统即可。

播送哈希 join

假如对于下面的例子，用户数据库能够齐全放入内存。在这种状况下，当 mapper 程序执行时，它能够首先将用户数据库从分布式文件系统读取到内存的哈希表中。而后，mapper 程序扫描用户流动事件，并简略地查找哈希表中每个事件的用户 ID。

这种是实现 map 端 join 最简略的办法，特地适宜大数据集与小数据集 join，尤其是小数据集可能全副加载到每个 mapper 的内存中。

Map 工作仍然能够有多个：大数据集的每个文件块对应一个 mapper，每个 mapper 还负责将小数据集全副加载到内存中。这种简略而无效的算法被称为播送哈希 join：“播送”一词次要是指大数据集每个分区的 m apper 还读取整个小数据集（即小数据集理论被“播送”给大数据集）﹐“哈希”意味着应用哈希表。

另一种办法并不需要将小数据集加载至内存哈希表中，而是将其保留在本地磁盘上的只读索引中。因为频繁拜访，索引大部分内容其实是驻留在操作系统的页面缓存中，因而这种办法能够提供与内存哈希表简直一样快的随机拜访性能，而实际上并不要求整个数据集读入内存。

分区哈希 join

如果以雷同的形式对 map 端 join 的输出进行了分区，则哈希 join 办法能够独立作用于每个分区。在上例中，能够依据用户 ID 的最初一位十进制数字（因而每一边都有 10 个分区）来调配流动事件和用户数据库中的记录。例如，Mapper 3 首先将所有以 3 结尾的 ID 的用户加载到哈希表中，而后扫描 ID 以 3 结尾的每个用户的所有流动事件。

如果分区操作正确实现，就能够确定所有要 join 的记录都位于雷同编号的分区中，因而每个 mapper 只需从每个输出数据集中读取一个分区就足够了。这样的长处是每个 mapper 都能够将较少的数据加载到其哈希表中。

这种办法只实用于两个 join 的输出具备雷同数量的分区，并且依据雷同的关键字和雷同的哈希函数将记录调配至分区。如果输出是由之前曾经执行过这个分组的 MapReduce 作业生成的，那么这是一个正当的假如。

map 端合并 join

如果输出数据集不仅以雷同的形式进行分区，而且还基于雷同的关键字进行了排序，则能够利用 map 端 join 的另一种变体。这时，输出是否足够小以载入内存并不重要，因为 mapper 能够执行通常由 reducer 执行的合并操作：按关键字升序增量读取两个输出文件，并且匹配具备雷同关键字的记录。

如果 map 端合并 join 是可能的，则意味着先前的 MapReduce 作业会首先将输出数据集引入到这个通过分区和排序的表单中。原则上，join 能够在之前作业的 reduce 阶段进行。然而，在独立的 map 作业中执行合并 join 更为适合，例如，除了特定的 join 操作之外，分区和排序后的数据集还可用于其余目标。

具备 map 端 join 的 MapReduce 工作流

当上游作业应用 MapReduce join 的输入时，map 端或 reduce 端 join 的不同抉择会影响到输入构造。reduce 端 join 的输入按 join 关键字进行分区和排序，而 map 端 join 的输入依照与大数据集雷同的形式进行分区和排序（因为对大数据集的每个文件块都会启动一个 map 工作，无论是应用分区 join 还是播送 join）。

正如所探讨的，map 端 join 也存在对输出数据集的大小、排序和分区方面的假如。在优化 join 策略时，理解分布式文件系统中数据集的物理布局十分重要：仅仅晓得编码格局和数据存储目录的名称是不够的，还必须晓得数据分区数量，以及分区和排序的关键字。

批处理即不是事务处理，也不是剖析。批处理与剖析更为靠近，因为批处理过程通常会扫描大部分的输出数据集。然而，MapReduce 作业的工作流与剖析中 SQL 查问不同。批处理过程的输入通常不是报告，而是其余类型的数据结构。

生成搜寻索引

Google 最后应用 MapReduce 的目标是为其搜索引擎建设索引，这个索引被实现为 5 到 10 个 MapReduce 作业的工作流。只管 Google 起初不再应用 MapReduce，然而如果从构建搜寻索引的角度来看 MapReduce，会更加有助于了解（即便在明天，Hadoop MapReduce 依然是构建 Lucene/Solr 索引的好办法）。

像 Lucene 这样的全文搜寻索引是这样工作的：它是一个文件（术语字典），能够在其中无效地查找特定关键字，并找到蕴含该关键字的所有文档 ID 列表（公布列表）。这是一个非常简单的搜寻索引视图，实际上它还须要各种附加数据，以便按相关性对检索后果进行排序、拼写查看、解析同义词等等，但根本准则相似。

如果须要对一组固定文档进行全文检索，则批处理是构建索引的无效办法：mapper 依据须要对文档集进行分区，每个 reducer 构建其分区索引，并将索引文件写入分布式文件系统。并行处理十分实用于构建这样的文档分区索引。

因为按关键字查问搜寻索引是只读操作，因而这些索引文件一旦创立就是不可变的。如果索引的文档汇合产生更改，则能够抉择定期从新运行整个索引工作流，并在实现后用新的索引文件批量替换之前的索引文件。

如果只有大量文档产生了变动，这种办法在计算上可能比拟低廉，增量建设索引是一种代替办法。如果要增加、删除或更新索引中的文档，Lucene 会生成新的段文件，并在后盾异步合并和压缩段文件。

批处理输入键值

搜寻索引只是批处理工作流输入的一个示例。批处理的另一个常见用处是构建机器学习零碎，如分类器（例如垃圾邮件过滤器，异样检测，图像识别）和举荐零碎（例如你可能意识的人，你可能感兴趣的产品或相干搜寻）。

这些批量作业的输入通常是写入某种数据库：例如，在用户数据库中通过用户 ID 进行查问以获取倡议的好友，或者在产品数据库中通过产品 ID 查问以获取相干产品列表。

查询数据库须要在解决用户申请的 Web 利用中进行，而这些申请通常与批处理作业架构是拆散的。那么批处理过程的输入如何返回至数据库中以供 Web 利用查问？

最显著的抉择可能是间接在 mapper 或 reducer 中应用你最喜爱的数据库客户端软件包（如果其反对批处理的话），而批处理作业则间接写入至数据库服务器，一次写入一条记录。这样的办法可行，但并不是一个好计划：

为每个记录发送一个网络申请比批处理工作的失常吞吐量要慢几个数量级，性能很差。
MapReduce 作业常常并行处理许多工作。如果所有的 mapper 或 reducer 都同时写入同一个输入数据库，并以批处理冀望的速率写入，那么数据库很容易过载，其查问性能会受到影响。
通常状况下，MapReduce 为作业输入提供了一个洁净的“全有或全无”的保障：如果作业胜利，则后果就是只运行一次工作的输入，即便两头产生了某些工作失败但最终重试胜利。如果整个作业失败，则不会产生输入。然而从作业外部写入内部零碎会产生内部可见的副作用，而这种副作用无奈彻底屏蔽。

更好的解决方案是，批处理作业创立一个全新的数据库，并将其作为文件写入分布式文件系统中的作业输入目录。这些数据文件一旦写入就是不可变的，能够批量加载到解决只读查问的服务器中。各种键值存储都反对构建 MapReduce 作业中的数据库文件，包含 Voldemort，Terrapin，ElephantDB 和 HBase 批量加载。

批处理输入的哲学

后面探讨过的 UNIX 设计哲学提倡明确的数据流：一个程序读取输出并写回输入。在这个过程中，输出放弃不变，任何以前的输入都被新输入齐全替换，并且没有其余副作用。这意味着能够得心应手地从新运行一个命令，进行调整或调试，而不会扰乱零碎状态。

MapReduce 作业的输入解决遵循雷同的原理。将输出视为不可变，防止副作用（例如对外部数据库的写入），批处理作业不仅实现了良好的性能，而且更容易保护：

如果在代码中引入了破绽，输入谬误或者损坏，那么能够简略地回滚到先前版本，而后从新运行该作业，将再次生成正确的输入；或者更简略的方法是将旧的输入保留在不同的目录中，而后切换回原来的目录。
与产生谬误即意味着不可挽回的侵害相比，易于回滚的个性更有利于疾速开发新性能。
如果 map 或 reduce 工作失败，MapReduce 框架会主动重新安排作业并在同一个输出上再次运行。如果失败是因为代码破绽造成的，那么它会始终解体，最终导致作业在数次尝试之后失败。然而如果故障是因为临时问题引起的，则能够实现容错。
雷同的文件可用作各种不同作业的输出，其中包含监控作业，它能够收集相干运行指标，并评估其余作业的输入是否满足预期个性（例如，将其与前一次运行的输入进行比拟并测量差别）。
与 UNIX 工具相似，MapReduce 作业将逻辑与连线（配置输出和输入目录）离开，从而能够更好地隔离问题，重用代码。

只管 MapReduce 在 20 世纪末变得十分风行并被大量炒作，但它只是分布式系统的许多可能的编程模型之一。取决于具体的数据量、数据结构以及解决类型，其余工具可能更适宜特定的计算。

MapReduce 是一个有用的学习工具，因为它是分布式文件系统的一个相当清晰和简略的形象。然而，MapReduce 执行模型自身也存在一些问题，这些问题并没有通过减少另一个抽象层次而失去解决，而且在某些类型的解决中体现出蹩脚的性能。

上面咱们会看到一些批处理的代替计划。

如前所述，每个 MapReduce 作业都独立于其余任何作业。作业与其余工作的次要联系点是分布式文件系统上的输出和输入目录。如果心愿一个作业的输入成为第二个作业的输出，则须要将第二个作业的输出目录配置为与第一个作业的输入目录雷同，并且内部工作流调度程序必须仅在第一个作业曾经实现后才开始第二个作业。

如果第一个作业的输入是要在组织外部宽泛散发的数据集，则此设置是正当的。在这种状况下，须要可能通过名称来援用它，并将其用作多个不同作业的输出。将数据公布到分布式文件系统中家喻户晓的地位能够实现松耦合，这样作业就不须要晓得谁在生成输入或者耗费输入。

然而，在很多状况下，咱们晓得一个作业的输入只能用作另一个作业的输出，这个作业由同一个团队保护。在这种状况下，分布式文件系统上的文件只是中间状态：一种将数据从一个作业传递到下一个作业的形式。

相比之下，本章结尾的日志剖析示例应用 UNIX 管道将一个命令的输入与另一个命令的输出连接起来。管道并不齐全实现中间状态，而是只应用一个小的内存缓冲区，逐步将输入流式传输到输出。

与 UNIX 管道相比，MapReduce 齐全实体化中间状态的办法有一些不利之处：

MapReduce 作业只有在后面作业中的所有工作都实现时能力启动，而通过 UNIX 管道连贯的过程同时启动，输入一旦生成就会被应用。
Mapper 在很多状况下是冗余的：它们只是读取刚刚由 reducer 写入的同一个文件，并为下一个分区和排序阶段做筹备。在许多状况下，mapper 代码可能是之前 reducer 的一部分：如果 reducer 的输入被分区和排序的形式与 mapper 输入雷同，那么不同阶段的 reducer 能够间接链接在一起，而不须要与 mapper 阶段交织。
将中间状态存储在分布式文件系统中意味着这些文件被复制到多个节点，对于这样的长期数据来说通常是大材小用了。

关于分布式:数据系统派生数据系统批处理系统

应用 UNIX 工具进行批处理

简略日志剖析

排序与内存中聚合

UNIX 设计哲学

对立接口

逻辑与布线拆散

通明与测试

MapReduce 与分布式文件系统

MapReduce 作业执行