DDIA：Unix 中蕴含的批处理哲学

在本书的前两部分，我们讨论了请求（requests）和查询（queries），与之相对的是响应（responses）和结果（results）。这种请求应答风格的数据处理是很多现代系统的基本设定：你向系统询问一些事情，或者你发送一个指令，系统稍后（大概率上）会给你一个回复。数据库、缓存、搜索引擎、 web 服务器和其他很多系统，都以类似的方式工作。

在这些在线（online）系统中，不论是 web 浏览器请求一个页面，还是服务调用一个远程 API，我们通常假设这些请求是由真人用户触发，且会等待回复。他们不应该等太久，因此我们花很多精力在优化这些系统的响应延迟（response time）上（参见衡量负载）。

web 服务和日趋增长的基于 HTTP/REST 的 API，让请求/应答风格的交互如此普遍，以至于我们理所当然的认为系统就应该长这样。但须知，这并非构建系统的唯一方式，其他方法也各有其应用场景。我们来对下面三种类型系统进行考察：

• 服务（在线系统，online systems） 服务（service）类型的系统会等待客户端发来的请求或指令。当收到一个请求时，服务会试图尽快的处理它，然后将返回应答。响应时间通常是衡量一个服务性能的最主要指标，且可用性通常很重要（如果客户端不能够触达服务，则用户可能会收到一条报错消息）。之前章节我们主要在讨论此类系统。
• 批处理系统（离线系统，offline systems） 一个批处理系统通常会接受大量数据作为输入，然后在这批数据上跑任务（job），进而产生一些数据作为输出。任务通常会运行一段时间（从数分钟到数天不等），因此一般来说没有用户会死等任务结束。相反，批处理任务通常会周期性的执行（例如，每天一次）。吞吐量（throughput，处理单位数据量所耗费的时间）通常是衡量批处理任务最主要指标。我们本章会主要围绕该类型系统进行讨论。
• 流式系统（近实时系统，near-real-time systems） 流式处理介于在线处理和离线处理（批处理）之间（因此也被称为近实时，near-real-time，或者准在线处理，nearline processing）。和批处理系统一样，流式处理系统接受输入，产生一些输出（而不是对请求做出响应，因此更像批处理而非服务）。然而，一个流式任务通常会在事件产生不久后就对其进行处理，与之相对，一个批处理任务通常会攒够一定尺寸的输入数据才会进行处理。这种区别让流式处理系统比同样功能的批处理系统具有更低的延迟。由于流式处理基于批处理，因此我们下一章再讨论它。

我们在本章将会看到，批处理是我们寻求构建可靠的、可扩展的、可维护的应用的重要组成部分。例如，MapReduce ，一个发表于 2004 年的批处理算法，（可能有些夸大）使得“谷歌具有超乎寻常可扩展能力”。该算法随后被多个开源数据系统所实现，包括 Hadoop，CounchDB 和 MongoDB。

相比多年前为数据仓库开发的并行处理系统，MapReduce 是一个相当底层的编程模型，但是它在基于廉价硬件上实现大规模的数据处理上迈出了一大步。尽管现在 MapReduce 的重要性在下降，但它仍然值得深入研究一番，因为通过这个框架，我们可以体会到批处理的为何有用、如何有用。

实际上，批处理是一种非常古老的计算形式。在可编程的数字计算机发明之前，打孔卡制表机——比如用于 1890 年美国人口普查的 Hollerith 制表机（IBM 前身生产的）——实现了一种对大量输入的半机械化批处理。MapReduce 与二十世纪四五十年代 IBM 生产的卡片分类机有着惊人的相似。就像我们常说的，历史总是在自我重复。

在本章，我们将会介绍 MapReduce 和其他几种批处理算法和框架，并探讨下他们如何用于现代数据系统中。作为引入，我们首先来看下使用标准 Unix 工具进行数据处理。尽管你可能对 Unix 工具链非常熟悉，但对 Unix 的哲学做下简单回顾仍然很有必要，因为我们可以将其经验运用到大规模、异构的分布式数据系统中。

使用Unix工具进行批处理

让我们从一个简单的例子开始。设你有一个 web 服务器，并且当有请求进来时，服务器就会向日志文件中追加一行日志：

216.58.210.78 - - [27/Feb/2015:17:55:11 +0000] "GET /css/typography.css HTTP/1.1"
200 3377 "http://martin.kleppmann.com/" "Mozilla/5.0 (Macintosh; Intel Mac OS X
10_9_5) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/40.0.2214.115
Safari/537.36"

注：上面文本其实是一行，只是为了阅读性，拆成了多行。

这行日志信息量很大。为了便于理解，你可能首先需要了解其格式：

$remote_addr - $remote_user [$time_local] "$request"
$status $body_bytes_sent "$http_referer" "$http_user_agent"

因此，上面一行日志的意思是，在 2015 年的 2 月 27 号，UTC 时间 17:55:11 ，服务器从 IP 为 216.58.210.78 的客户端收到了一条请求，请求路径为 /css/typography.css。该用户没有经过认证，因此用户位置显示了一个连字符（-）。响应状态码是 200（即，该请求成功了），响应大小是 3377 字节。web 浏览器是 Chrome 49，由于该资源在 http://martin.kleppmann.com/ 网站中被引用，因此浏览器加载了该 CSS 文件。

简单的日志分析

有很多现成的工具可以处理这些日志文件，以分析你网站的流量，并产生漂亮的报表。但为了学习，我们只使用基本的 Unix 命令自己造一个分析工具。假设你想获取网站上访问频次最高的五个页面，则可以在 Unix Shell 中输入：

cat /var/log/nginx/access.log | #(1)
      awk '{print $7}' |        #(2)
      sort             |        #(3)
      uniq -c          |        #(4)
      sort -r -n       |        #(5)
      head -n 5                 #(6)

每一行作用如下：

1. 读取给定日志文件
2. 将每一行按空格分成多个字段，然后取出第七个，即我们关心的 URL 字段。在上面的例子中，即：/css/typography.css
3. 按字符序对所有 url 进行排序。如果某个 url 出现了 n 次，则排序后他们会连着出现 n 次。
4. uniq 命令会将输入中相邻的重复行过滤掉。-c 选项告诉命令输出一个计数：对于每个 URL，输出其重复的次数。
5. 第二个 sort 命令会按每行起始数字进行排序（-n），即按请求次数多少进行排序。-r 的意思是按出现次数降序排序，不加该参数默认是升序的。
6. 最后，head 命令会只输出前 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

如果你对 Unix 工具链不熟悉，读懂上面这一串命令可能会有点吃力，但只要理解之后就会发现它们非常强大。这个组合可以在数秒内处理上 G 的日志文件，并且，如果需求发生变动，也可以很方便的重新组合命令。比如，如果你想在输出中跳过 CSS 文件，可以将 awk 的参数改成 '7 !~ /\.css/ {print 7}' 。如果你想统计最常访问的 IP 数而非访问网页，则可以将 awk 的参数变为 '{print 1}'。如此种种。

本书中没有余力去详细讨论所有 Unix 工具使用细节，但他们都很值得一学。你可以在短短几分钟内，通过灵活组合 awk, sed, grep, sort, uniq, 和 xargs 等命令，应对很多数据分析需求，并且性能都相当不错。

链式命令 vs 专用程序

除了链式组合 Unix 命令，你也可以写一个简单的小程序来达到同样的目的。如，使用 Ruby，会有类似如下代码：

counts = Hash.new(0)    # (1)

File.open('/var/log/nginx/access.log') do |file| 
  file.each do |line|
    url = line.split[6] # (2)
    counts[url] += 1    # (3)
  end
end

top5 = counts.map{|url, count| [count, url] }.sort.reverse[0...5] # (4)
top5.each{|count, url| puts "#{count} #{url}" }                   # (5)

标号对应代码功能如下：

1. counts 是一个哈希表，为每个出现过的 URL 保存一个计数器，计数器初始值为 0。
2. 对于每行日志，提取第六个字段作为 URL（ ruby 的数组下标从 0 开始）。
3. 对当前行包含的 URL 的计数器增加 1 。
4. 对哈希表中的 URL 按计数值降序排序，取前五个结果。
5. 打印这五个结果。

该程序虽不如使用 Unix 管道组合的命令行简洁，但可读性也很好，喜欢使用哪种方式是一个偏好问题。然而，两者上除了表面上的语法区别，在执行流程上差别也很大。在你分析海量数据时，这一点变的尤为明显。

排序 vs 内存聚合

Ruby 脚本在内存中保存了 URL 的哈希表，记录每个 URL 到其出现次数的映射。Unix 管道例子中并没有这样一个哈希表。作为替代，它将所有 URL 进行排序，从而让所有相同的 URL 聚集到一块，从而对 URL 出现次数进行统计。

那种方法更好一些呢？这取决于你有多少个不同的 URL。对于大部分中小尺度的网站，你大概率能够把所有 URL 都放到（比如 1 G） 内存中，并为每个 URL 配一个计数器。在该例子中，该任务的工作集（任务需要访问的内存的大小）仅取决于不同 URL 的数量：假设有上百万条日志，但都只针对同一个 URL ，则哈希表所需空间为该 URL 尺寸加上对应计数器尺寸（当然，哈希表本身也是占一些空间的）。如果工作集足够小，则基于内存的哈希表能够很好地工作——即使在笔记本电脑上。

但如果，任务的工作集大于可用内存，则排序方式更有优势，因为能够充分利用磁盘空间。其原理类似我们在SSTables 和 LSM-Trees一节中提到的：可以在内存中分批次对部分进行排序，然后将有序的数据作为文件写入磁盘中，最后将多个有序文件合并为更大的有序文件。归并排序会对数据进行顺序访问，因此在磁盘上性能较好。（为顺序 IO 优化是第三章中反复讨论过的主题，这里也出现了）

GNU 核心工具包中的 sort 命令，会自动的处理超过内存大小的数据集，将一些数据外溢（spill）到磁盘上；此外，该工具还可以充分利用多核 CPU 进行并发地排序。这意味着，我们之前例子中的对日志处理的 Unix 命令行能够轻松应对大数据集，而不会耗尽内存（OOM）。不过，性能瓶颈会转移到从磁盘读取输入文件的 IO 上。

Unix 哲学

我们能够通过简单的组合 Unix 工具来进行复杂的日志文件处理并非巧合：这正是 Unix 的核心设计思想之一，且该思想在今天也仍然非常重要。让我来深入的探究一下其背后哲学，以看看有什么可以借鉴的。

Doug McIlroy，Unix 管道（pipe）的发明人，在 1964 年是这样描述管道的：“我们需要一种像软管一样可以将不同程序连接到一块的方法——当数据准备好以其他方式处理时，只需要接上就行。IO 也应该以这种方式工作”。管道的类比到今天仍然存在，并且成了 Unix 哲学的一部分。Unix 哲学是一组在 Unix 用户和开发者中很流行的设计原则，在 1978 年被表述为：

1. 每一个程序专注干一件小事。在想做一个新任务时，新造一个轮子，而非向已有的程序中增加新的“功能”。
2. 每个程序的输出成为其他程序（即便下一个程序还没有确定）的输入。不要在输出中混入无关信息（比如在数据中混入日志信息），避免使用严格的列式数据（数据要面向行，以行为最小粒度？）或者二进制数据格式。不要使用交互式输入。
3. 尽快的设计和构建软件，即便复杂如操作系统，也最好在几周内完成（译注：这里翻译稍微有些歧义，即到底是尽快迭代还是尽早让用户试用，当然他们最终思想差不多，即构造最小可用模型，试用-迭代）。对于丑陋部分，不要犹豫，立即推倒重构。
4. （Q：unskilled help是指？这一条没太理解）相比不成熟的帮助，更倾向于使用工具完成编程任务，即使可能会进行反复构建相似的工具，并且在用完之后大部分工具就再也不会用到。

这些手段——尽可能自动化、快速原型验证、小步增量迭代、易于实验测试，将大型工程拆解成一组易于管理的模块——听起来非常像今天的敏捷开发和 DevOps 运动。令人惊讶的是，很多软件工程的核心思想在四十年间并没有太多变化。

Unix 中的 sort 工具是一个程序只干好一个事情的非常典型的案例。相对大多数编程语言的标准库函数（即使在能明显提升性能时，也不能利用磁盘空间、不能利用多核性能），它给出了一个更好的实现。不过，单独使用 sort 威力还不是那么大。只有在与其他 Unix 工具（如 uniq）组合时，sort 才会变的相当强大。

使用 Unix Shell 如 bash 让我们能够轻易的将这些工具组合以应对数据处理任务。即使大部分的工具都是由不同人编写的，也可以很容易的组合到一块。我们不禁会问，Unix 做了什么让其有如此强的组合能力？

统一的接口

如果你希望一个程序的输出可以作为其他程序的输入，就意味着这些程序需要使用同样的数据格式——换句话说，可兼容的接口。如果你想让任意程序的输出能接到任意程序的输入上，则意味着所有这些程序必须使用同样的输入输出接口。

在 Unix 中，这种接口是文件（a file，更准确的说，是文件描述符，file descriptor）。文件本质上是一种有序的字节序列。这种接口是如此简约，以至于很多不同的实体都可以共用该接口：文件系统中真实的文件、与其他程序的通信渠道（Unix socket，标准输入 stdin，标准输出 stdout）、设备驱动（如 /dev/audio 或者 /dev/lp0）、以 socket 表示的 TCP 连接等等。站在今天的视角，这些设定看起来平平无奇、理所当然，但当时能让这么多不同的东西使用统一的接口是一种非常了不起的设计，唯其如此，这些不同的东西才能进行任意可插拔的组合。

另外一个非常成功的接口设计是：URL 和 HTTP，互联网的基石。一个 URL 能够唯一的定位网络中的一个资源，基于此，你可以在网页中任意链接其他网页。使用浏览器的用户因此能在不同的网页间进行无缝的跳转，即使这些网站运行在完全不同的服务器上，且由不同的组织进行运营。这些原则在今天看起来非常显而易见，但也正因为这个符合直觉的关键设计才让今天的互联网如此成功。在此之前的一些系统使用观感就没有这么统一了，比如在公告板系统（bulletin board systems，BBS）时代，每个系统都有其各自的电话号码和波特率配置（这两个名词没太懂，拨号上网？）对其他 BBS 的引用只能使用电话号码+猫（modem ，调制解调器）的配置；用户必须先挂起，拨入其他的 BBS，然后手动的查找信息。我们难以在一个 BBS 中直接引用另一个 BBS 上的内容。

通常来说，大部分（并不是所有）的 Unix 程序将这些字节序列看做是 ASCII 文本。我们之前提到的日志分析例子中就是基于该事实：awk，sort，uniq 和 head 都将其输入文件视为由 \n（换行符，ASCII 码是 0x0A）分割的一系列记录。当初选择 \n 很随意——也许，ASCII 分隔符 0x1E 是一个更好的选项，毕竟，该字符就是为分割而生——但无论如何，只有程序使用相同的记录分隔符，才能方便的进行组合。

相对来说，对于每一个记录（如，一行）的解析是相对模糊、非统一的。Unix 工具通常使用空格或者 tab 作为分隔符将一行分解成多个字段，但有时也会用 CSV（逗号分割）、管道分割等其他编码。即使像 xargs 这样简单的工具，也提供了很多选项，以让用户指定如何对输入进行解析。

使用 ASCII 文本作为统一的接口虽然能应对非常多的场景，但远非完美：在我们的日志分析例子中，使用 {print 7} 来提取每一行中的 URL，可读性就很差。在理想情况下，我们最好能够使用类似 {print request_url} 的方法，之后我们继续会讨论该想法。

尽管不完美，在数十年后的今天，Unix 统一的接口设计仍然堪称伟大。没有多少软件模块可以像 Unix 工具这样进行任意交互和组合：比如你很难快速构建一个分析软件，以轻松地将你邮件账户中的内容和网上购物的历史整合到电子表格中，并将结果发布到社交网络或者维基百科里。直到今天，让程序像 Unix 工具一样丝滑地协同工作，仍是一个特例，而非常态。

即使两个数据库的数据具有相同的数据模型（Schema），也很难快速的将数据在两个数据库间导来导去。多个系统间缺少有效整合使得数据变得巴尔干化（一种相对贬义的地缘政治学术语，指较大国家分裂成互相敌对的一系列小国的过程）。

逻辑和接线（数据流组织）分离

Unix 工具的另外一个显著特征是其对于标准输入（stdin）和标准输出（stdout）的使用。如果你运行程序时不做任何指定，键盘是默认的标准输入（stdin），屏幕是默认的标准输出（stdout）。当然，你也可以将文件作为程序的输入，或者将输出重定向到其他文件。管道（pipe）能让你将一个程序的标准输出（即编码实现该程序时，程序视角的 stdout）冲定向到另外一个程序的标准输入（仅需要一个比较小的缓冲区足矣，并不需要将所有的中间数据流写入磁盘）。

在需要时，程序当然可以直接读写文件。但若程序不关心具体的文件路径，而仅面向标准输入和标准输出进行编程，可以在 Unix 环境下和其他工具进行更好地协同。这种设定，让 shell 用户可以按任意方式对多个程序的输入输出进行组织（也即接线，wire up）；每个程序既不需要关心输入来自何处，也不需要知道输出去往何方（我们有时也将这种设计称为松耦合，延迟绑定或者控制反转）。将程序逻辑和数据流组织分离，能让我们轻松地组合小工具，形成复杂的大系统。

你也可以自己编写程序，并将其与操作系统中自带的具进行组合。只要你的工具是从标准输入读取数据，并将处理结果写入标准输出，就能作为一环嵌入到 Unix 的数据处理流水线中。比如，在日志分析程序中，你可以写一个将 user-agent 字符串翻译为更具体的浏览器标识符的工具，也可以写一个将 IP 地址翻译国家代码的工具，让后将其插入到流水线中即可。sort 并不关心其上下游的程序是操作系统自带的还是你写的。

不过，只是用 stdin 和 stdout 编程是有很多限制的。比如，如果程序使用多个输入或者产生多个输出怎么办？虽然有办法可以绕过，但是很取巧（tricky）。你不能将一个程序的输出通过管道直接输到网络中（倒也可以通过一些工具，比如 curl 或者 netcat）。如果程序直接打开文件进行读写、或者启动一个子进程、又或者打开一个网络连接，则相当于程序在标准输入输出之外自己进行了 IO 布线。倒确实可以通过配置来做到（比如命令行参数、默认配置文件等），但会大大降低由 shell 进行接线的灵活性。

透明性和实验性

Unix 工具生态如此成功的另外一个原因是，可以很方便让用户查看系统运行的状态：

• Unix 命令的输入文件通常被当做是不可变的。这意味着，你可以使用不同命令行参数，针对同样的输入跑很多次，而不用担心会损坏输入文件。
• 你可以在多个命令组成的处理流水线的任意环节停下来，将该环节的输出打到 less 工具中，以查看输出格式是否满足预期。这种可以对运行环节随意切片查看运行状态的能力对调试非常友好。
• 你可以将一个流水线环节的输出写入到文件中，并将该文件作为流水线下一个环节的输入。这样即使你中断了流水线的执行，之后想重启时就不用重新跑流水线所有环节。

因此，虽然相比关系型数据库中的查询优化，Unix 工具非常粗陋、简单，但却非常好用，尤其是在做简单的实验场景下。

然而，Unix 工具最大的局限在于只能运行在单机上——这也是大数据时代人们引入 Hadoop 的进行数据处理的原因——单机尺度已经无法处理如此巨量的数据。

参考资料

[1]

DDIA 读书分享会: https://ddia.qtmuniao.com/

DDIA 学习会