ACM SIGOPS名人堂（第十二期）

SIGOPS名人堂奖（Hall of Fame Award，HoF）是SIGOPS组织于2005年设立的奖项，用于评选一批发表10年以上对操作系统领域产生巨大影响力的文章，是系统领域至高无上的荣誉。该奖项每年评选一次，在每年系统领域顶级会议SOSP和OSDI上颁发（两会议隔年交替举办），起初两届奖项（SOSP 2005和OSDI 2006）由当年的SOSP和OSDI的程序委员会成员（Program Committees，PC）投票选出，后为减轻PC们沉重的工作负担，从2007年起成立名人堂奖项委员会，委员会成员由最近4届SOSP和最近4届OSDI的大会主席组成，以此保障奖项的公允性和含金量。

前面我们介绍了十一期，分别是：

在本期名人堂中，我们将介绍2015年最后3篇获选文章和2016年的1篇获选文章：

1. ReVirt: Enabling Intrusion Analysis through Virtual-Machine Logging and Replay

2. The Google File System

3. MapReduce : Simplified Data Processing on Large Clusters

4. Bigtable : A Distributed Storage System for Structured Data

ReVirt: Enabling Intrusion Analysis through Virtual-Machine Logging and Replay

第一篇文章发表于2002年的OSDI上。文章提出了一个基于虚拟机日志（logging）和重放（replay）的入侵分析系统ReVirt。在这篇文章之前，基于事件日志的入侵分析已经有了一定发展历史。但此前的日志记录方法存在着两个缺陷。首先，日志功能依赖于可能被攻击的操作系统，一旦操作系统本身被入侵者控制，生成的日志也可能被入侵者篡改或者删除。其次，此前的日志记录的信息（如用户登陆/退出、进程开始/结束等）并不完备，缺少重放程序的许多重要信息，特别是执行中的非确定性事件如外部中断、用户输入等。

ReVirt运行在该架构中的VMM中（来自原论文）

ReVirt为了解决这两个问题，将需要被分析的整个客户操作系统（guest OS）放在一个虚拟机中，然后在更下层的虚拟机监视器（virtual machine monitoring，通常运行于不同的域）中记录日志。这样，即便入侵者控制了整个客户操作系统，也无法影响到运行在其他域的VMM日志记录。同时，ReVirt详细分析了虚拟机执行中可能的各类非确定性事件，并完整地记录这些事件发生时的上下文。基于ReVirt的日志，虚拟机中的任意程序均可被高效、确定性地重放。

ReVirt所设计的日志-重放机制，最初目的只是用于入侵分析。然而，它也可以被用于系统调试、故障恢复、程序监控以及其他的虚拟机服务。ReVirt对于许多商业产品有着直接的影响，同时它也开启了一个新的研究方向，一直到今天该方向相关的研究仍在持续发展。

ReVirt项目负责人Peter Chen教授

ReVirt是由密歇根大学Peter Chen教授领导的课题组所设计开发。Peter Chen教授是密歇根大学Arthur F. Thurnau具名教授，他的研究方向包括虚拟化系统安全、操作系统与分布式系统的推测执行、可靠性内存与分布式应用中间件等。ReVirt属于Peter Chen教授主导的CoVirt的项目（后因为与一个公司重名而改名）在虚拟化系统安全领域的成果之一。除此以外，该项目的研究还包括：减少在虚拟机中部署导致的性能开销（USENIX ATC 2003）、从程序回放中找到可疑的入侵行为（SOSP 2003与NDSS 2005）、基于虚拟机回放功能的反向调试（USENIX ATC 2005）、利用虚拟机自我检查（introspection）发现软件安全漏洞（SOSP 2005）、以及从攻击者角度利用虚拟机作为工具获取系统权限（IEEE S&P 2006）。

The Google File System

本期的后三篇文章均来自于Google，分别介绍了Google的三大核心技术：Google File System (GFS)、MapReduce和Bigtable。这三篇文章均是大规模数据处理领域的经典文献。其中发表于SOSP 2003年的The Google File System介绍了Google的无结构化的分布式文件系统GFS。这篇文章也获得了当年的SOSP最佳论文奖。

GFS的架构包括一个主服务器（Master）、大量用于实际数据存储的Chunk服务器与GFS客户端。从Google的自身需求出发，GFS的设计基于若干假设，这些假设既对系统设计提出了挑战，也为系统的架构优化提供了机会。首先，GFS是由大量廉价的商业PC搭建的，这些廉价PC的可能经常发生故障。其次，GFS存储的文件基本都是超过100MB甚至几个GB的大文件，虽然GFS也支持小文件，但对小文件的优化并不是必需的。再次，对GFS上数据的访问有着明显的特征，其中顺序读大块数据与追加写大块数据占据了主导，同时系统必须支持对同一文件来自多个客户端的并发追加写操作。最后，GFS对高带宽的需求超过了低延迟的需求。

Google File System架构（来自原论文）

基于这些实际需求，GFS采用了一些有别于传统文件系统、在当时看来略显激进的系统设计。比如，GFS提供了对每台PC的状态检测、自动化的故障容错与故障恢复机制、让GFS客户端与Chuank服务器之间直接数据传输以获取大带宽、中心化的主服务器节点管理所有的元数据以简化系统设计、针对大文件配置的文件系统参数、只把追加写操作作为性能优化与原子性保证的重点等。由此，GFS可以在上千台机器上可靠地存储海量数据并支持数百个客户端的并发访问。

在GFS文章发表之后，Yahoo!公司基于GFS的设计开发了开源的HDFS分布式文件系统。2010年，Google宣布了自己用于替代GFS的下一代文件系统Colossus，但由于其技术细节并未披露，时至今日，HDFS依然是最为流行的分布式文件系统之一。许多大规模数据分析系统（包括下面要介绍的MapRedue和Bigtable）的底层都是基于GFS或HDFS进行文件存储。而GFS的许多设计思想，也推动着诸多后续分布式文件系统的不断演进，启发了各类针对不用应用场景的分布式文件系统的诞生（如针对随机读或小文件存储）。

The Google File System的三位作者

这篇文章的第一作者Sanjay Ghemawat目前是Google的研究科学家（Research Scientist）。他于MIT获得博士学位并且曾任职与DEC公司。他自1999年起就加入了当时还是初创公司的Google，主要从事分布式系统方面的工作，参与了许多Google的重要数据处理系统如GFS、MapReduce、Bigtable、Spanner、TensorFlow等。同时，他也被认为是硅谷最出色的程序员之一。

文章的第二作者Howard Gobioff同样在1999年加入Google，从事广告系统、爬虫系统与索引系统方面的工作。此前他于CMU获得博士学位。2004年他建立并领导了Google的东京研发中心。不幸的是，他与2008年因淋巴肿瘤去世。在去世之前，Gobioff成立了一个以他的名字命名的基金会用于教育与艺术事业。

文章的第三作者Shun-Tak Leung目前同样任职于Google。他在华盛顿大学获得博士学位并曾任职于DEC公司。在DEC时，他参与开发的性能分析工具DCPI也曾获得过1997年SOSP的最佳论文奖。在Google，继GFS之后，他又参与了后续几个分布式存储的开发包括Bigtable，Colossus和Google Cloud Storage。

MapReduce : Simplified Data Processing on Large Clusters

这篇文章发表于2004年的OSDI。文章提出了Google的大规模数据批处理框架MapReduce。MapReduce框架首先定义了一套极其简单但十分高效的计算模型。该计算模型以Key/Value数据作为输入，只包括两个接口函数Map和Reduce。Map将数据根据Key值进行划分，Reduce将具有相同Key值的所有数据进行聚合。基于该计算模型，MapReduce框架还包括了一个由大量普通商业PC上组成的分布式系统。该系统将分布式计算中最重要的（也是开发者最头疼的）两个因素，即伸缩性与容错性，以极为简单优雅的方式封装在内。因此，MapReduce给开发者提供了一个异常简洁的接口：开发者只需要关注设计Map与Reduce两个函数的算法逻辑，而不必关注底层的分布式细节。

MapReduce是近十多年来计算机系统领域最有影响力的论文之一。Yahoo!公司基于MapReduce论文开发的开源系统Hadoop，被极为广泛地应用于许多大公司的数据处理。众多在MapReduce最初设计目标之外的应用案例，也都以MapReduce为范式进行重设计。当然，MapReduce由于其过于简化的模型，并不是解决所有数据处理问题的万能钥匙。比如，在处理一些复杂的计算任务（如迭代计算）时，MapReduce过于繁琐且并不高效。2008年David DeWitt与Michael Stonebraker（后者是2015年图灵奖得主）也对MapReduce提出了质疑。甚至在2014年，Google也宣布弃用MapReduce并推出了更高效的Cloud Dataflow作为替代方案。但MapReduce的许多设计理念依然堪称是伟大系统的标志，其使用廉价机器构建高效系统的设计，对于后续的分布式数据处理系统有着巨大的启迪意义。

MapReduce的两位作者Jeffery Dean和Sanjay Ghemawat

这篇文章一共有两个作者，其中第二作者Sanjay Ghemawat我们在之前已经介绍过。第一作者Jeffery Dean目前是Google资深Fellow，Google大脑项目负责人，他先后入选了美国工程院与美国艺术与科学学院Fellow、ACM Fellow、AAAS Fellow。Jeffery Dean的研究兴趣十分广泛，包括了分布式系统、信息检索、机器学习在搜索领域的应用等。有趣的是，由于Jeffery Dean参与主导了Google诸多核心项目的开发，Google员工认为Google搜索引擎的速度很大程度上要归功与Jeffery Dean。出于对他的崇拜，Google的员工和前员工们在Quora上整理不少关于Jeffery Dean的幽默笑话（详情请点What are all the Jeff Dean facts）。

Bigtable : A Distributed Storage System for Structured Data

本期的最后一篇文章发表于2006年的OSDI，介绍了Google的Key/Value数据存储架构Bigtable。Bigtable建立在前面介绍过的GFS之上。相比于GFS中的无结构数据，Bigtable对数据建立了结构化的模型，更适合进行数据分析。因此，Google的许多服务都建立在Bigtable而并不是直接在GFS上，包括Google的索引、许多MapReduce应用、Google地图、Youtube、Gmail等。

Bigtable数据模型（来自原论文）

Bigtable本质上是一个三维表格。表格中的每个单元由行主键、列主键与时间戳所定义。有别于传统的关系数据库，Bigtable允许动态地表格的列进行添加删除。与GFS和MapReduce类似，Bigtable也同样在数千台廉价的商业PC上构建，用于支持PB级别的海量数据。为此，Bigtable根据表格行主键将表格进行分割形成若干被成为tablet的存储单元，存储在GFS中。Tablet在GFS中的位置被存储在主服务器（Master）中。Bigtable利用Chubby（一个分布式锁系统）来管理tablet信息，包括保证可用性、存储tablet位置、保存各个Bigtable的列信息与访问权限、动态监测各个服务器的状态等。

在Bigtable之后，Google又陆续推出了若干结构化存储系统，如MegaStore、Spanner、F1等，但Bigtable提出的数据模型对结构化数据存储领域有重要影响，Casandra、LevelDB、Hypertable等系统都提供了对Bigtable或类似数据模型的支持。而基于Bigtable开发的开源系统HBase在业界也有着广泛的应用。

Bigtable的部分作者

Bigtable论文一共有9位作者，均来自于Google，其中包括前面已经介绍了的Jeffery Dean和Sanjay Ghemawat。

小结：

本期介绍的4篇文章，第一篇重点介绍了一种基于虚拟机的入侵分析系统ReVirt。ReVirt开创了系统安全领域的一个新方向，有着极为深远的影响。后三篇文章介绍了Google的三个核心的数据存储与处理技术。基于它们的HDFS、Hadoop、HBase及其后续系统，为日后的“大数据”时代奠定了架构基础，时至今日这些系统依然在业界十分活跃。虽然十多年过去，这些技术的局限性在实际应用中逐渐被发现，但最初设计开发这些技术时所闪耀出的智慧火花，对研发后续技术方案时依然有着重要指导意义。今天的无数新型数据系统，在设计上或多或少都能看到这些技术的身影。

作者：黄群。中科院计算所先进计算机系统研究中心，副研究员，主要研究方向包括分布式系统与网络测量。

参考文档:

http://web.eecs.umich.edu/~pmchen

http://web.eecs.umich.edu/virtual

https://en.wikipedia.org/wiki/Google_File_System

https://www.quora.com/Who-is-Sanjay-Ghemawat

https://research.google.com/pubs/SanjayGhemawat.html

https://en.wikipedia.org/wiki/Howard_Gobioff

https://research.google.com/pubs/shuntak.html

MapReduce: A major step backwards

https://en.wikipedia.org/wiki/Jeff_Dean_(computer_scientist)

https://research.google.com/pubs/jeff.html

https://en.wikipedia.org/wiki/Bigtable

第26届计算机系统原理大会

（Symposium on Operating Systems Principles)

2017年10月28日-10月31日

于上海举办

计算机系统原理大会（SOSP）自1967年以来，每两年举办一次，至今已有50年历史。该会是由ACM组织的、全球最顶级的计算机系统会议之一。在每年的会议上，来自全球各地的学术界、产业界的系统研究者、开发者齐聚一堂，对计算机系统领域的前沿问题进行讨论。今年的第26届计算机系统原理大会于十月份在上海成功召开。点击阅读原文了解更多关于SOSP'17。

SOSP会议信息：

• SOSP会议注册地址：http://www.regonline.com/sosp2017

• 面向计算机领域的女性科研人员交流的Ada论坛：https://www.sigops.org/sosp/sosp17/workshop-ada.html