ACM SIGOPS名人堂（第六期）

本文转自 CNSys

在本期 SOSP 名人堂中，作者将向大家介绍 2010 年当选的三篇文章，它们分别是:

1. Using Encryption for Authentication in Large Networks of Computers.
2. Crash Recovery in a Distributed Data Storage System.
3. The Recovery Manager of the System R Database Manager.

"Using Encryption for Authentication in Large Network of computers"

Roger Needham(左)Michael Schroeder(右)

文章的第一作者 Roger Needham 教授(1935~2003)，曾任英国剑桥大学计算机系主任、常务副校长。1997 年 Roger Needham 离开剑桥大学,指导创建微软在英国的研究实验室。Roger Needham 突出的学术贡献集中在信息安全领域，提出了一系列影响深远的理论技术:BAN 逻辑、Needham-Schroeder 安全协议、协助设计 TEA 及 XTEA 加密算法、使用单项哈希函数的密码保护技术等。

文章的第二作者 Michael Schroeder，美国的计算机科学家。他的研究领域主要包括计算机安全、分布式系统和操作系统等。自 1976 年开始，Schroeder 先后在 MIT EECS 系、施乐 Palo Alto 研究中心(Xerox PARC)和 DEC 系统研究中心工作。Schroeder 最广为人知的工作应当就是这篇和 Roger Needham 合作的文章了。在计算机领域之外，他对美国风景画大师吉尔伯特·马格的画作也颇有研究。

这篇文章是二人在施乐 Palo Alto 研究中心期间合作完成的工作，讨论了大规模计算机网络中通信的加密认证，提出了后来以两位作者的姓氏命名的 Needham-Schroeder 安全协议，开辟了安全协议的崭新领域，为后续Kerberos、IPSec、SSL 和其他众多现代安全协议奠定了重要基础。在计算机通信的语境下，认证是指在不安全的网络环境下验证通信对端的身份。文章提出加密认证协议的三个重要功能:(1)交互式通信的认证(2)单项通信的认证(3)信息来源和完整性由第三方机构认证的签名通信。基于对称加密和非对称加密两种不同的加密技术，文章分别给出了上述三种功能的基本协议实现，并讨论了在大型计算机网络中认证服务器的分布式组织方式。

"Crash Recovery in a Distributed Data Storage System”

Bulter Lampson

这是 Bulter Lampson 在名人堂奖项中第二次获奖的工作，也是他第二次出现在我们sigops 名人堂介绍的系列文章中。Lampson 是美国的计算机科学家，致力于开发和实现个人计算机，因在计算机科学领域的卓著贡献，Lampson 获得荣誉无数:1992 年获图灵奖,1994 年被评选为 ACM 会士，2001 年获得冯·诺依曼奖章等等。文章的第二作者 Howard E. Sturgis 是 Lampson 指导的毕业于 1973年的博士，后来和 Lampson 继续共事。

这篇文章是同样诞生于施乐 Palo Alto 研究中心，主要探讨了分布式数据存储系统中恢复系统的设计，主要的贡献在于从存储、计算和网络三个方面全面建立了系统故障的模型。他提出了原子事务的算法，其主要思想是通过两阶段地执行事务来达到原子性。正如Lampson 最喜欢说的“计算机科学中的任何问题都可以通过增加一个中间层来解决”，文章首先在不可靠的物理系统基础上增加一个中间层，以消除底层物理系统中部分计算和存储故障，并隐藏通信;在此基础上，再增加一个中间层构造 Compound atomic actions 和 Stable sets 两个系统原语;最终在顶层实现原子事务的编程接又。

"The Recovery Manager of the System R Database”

从左至右:Jim Gray，Paul McJones，Mike Blasgen，Bruce Lindsay

从左至右:Raymond Lorie，Franco Putzolu，and Irving Traiger

Jim Gary(1944~2007)，美国科学院、工程院两院院士，ACM 和 IEEE 两会会士，关系型数据库领域的泰斗，因在数据库和事务处理研究和实现方面的开创性贡献而获得 1998 年图灵奖。1969 年博士毕业后，他在 IBM 研究院工作了十年，期间参与和主持了 IMS、System R、SQL/DS、DB2 等项目的开发，这些系统除了 System R 仅作为研究原型、没有成为产品外，其余都成为 IBM 在数据库市场上有影响力的产品。1995 年 Jim Gray 成为微软研究员，领导研发了MS SQL Server 7.0，成为微软历史上一个里程碑式的版本，而且也成为当今关系数据库市场上的佼佼者。Jim Gray 最著名的学术成就包括:数据库多粒度锁、对数据库的任何更新分两阶段提交、分配存储的五分钟规则、ACID 测试等;其研究成果反映在专著《Transaction Processing: Conceptsand Techniques》。让人遗憾的是，Jim Gary 在 2007 年 1 月独自驾船出海后失踪。

Jim Gray 喜好写作和旅行，每次旅行都要写旅行报告。开发 System R 时，同事Franco 一年写了两万行代码，但 Jim Gray 经常花时间旅行，一年才写了一万行代码，于是老大经常会去敲他的门说“快点写代码!!”。根据 Jim Gray 的回忆，整个开发过程中他写了五万到七万行代码，主要是涉及并发控制，系统恢复，系统启动，安全性管理等方面。

这篇上榜文章详细介绍了实验数据库管理系统 System R 的恢复子系统的设计与实现。整个恢复子系统基于影子和日志两大机制，实现事务的基本操作、savepoint 功能和 checkpoint 功能。在此基础上，文章给出了典型故障场景下数据的恢复流程，并对恢复子系统功能从实现代价、执行代价、IO 代价、成功比例等多个维度进行了评价。

小结

纵观第六届获奖的三篇文章，均为系统领域中基础但影响深远的工作，文章提出的理论方法经久不衰，至今仍表现出强大的生命力。Needham-Schroeder 安全协议为之后广泛使用的 Kerberos 协议奠定理论基础。后面的两篇文章都关注在数据存储系统中的数据恢复和事务管理问题上。第二篇提出了存储系统故障模型和通过两阶段提交实现原子事务的算法;第三篇实现了基于日志的 DOUNDO-REDO 策略。如今回顾这两篇文章的工作，对现今数据库系统发展都做出了基础性贡献。

作者

张宇翔，中国科学技术大学计算机科学与技术学院，大四本科生，研究兴趣: 程序分析、异构并行。

参考文献

[1]https://www.sigops.org/award-hof.html
[2]https://en.wikipedia.org/ wiki/Roger_Needham

[3]http://dl.acm.org/citation.cfm?id=359659
[4]https://en.wikipedia.org/wiki/Butler_Lampson

[5]https://www.microsoft.com/en-us/research/publication/crash-recovery-in-a-distributed-data-storage-system/

[6]https://en.wikipedia.org/wiki/Jim_Gray_(computer_scientist)
[7]http://amturing.acm.org/award_winners/gray_3649936.cfm
[8]http://dl.acm.org/citation.cfm?id=356847
[9]http://duanple.blog.163.com/blog/static/70971767201311810939564/