ACM SIGOPS名人堂（第八期）
我爱计算机 本文转自CNSys
在本期SOSP名人堂中，作者将向大家介绍2012年当选的四篇文章，它们分别是：
- A New Primary Copy Method to Support Highly-Available Distributed Systems
- The Part Time Parliament
- Memory Coherence in Shared Virtual Memory Systems
- The Design and Implementation of a Log-Structured File System
在这四篇文章中第一篇文章发表于1988年的“Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing(PODC)”, 后面三篇分别发表于1998，1989，1992年的”ACM Transactions on Computer Systems（TOCS）“。前面两篇均是研究分布式共识问题里具有里程碑意义的文章，而第三篇则是分布式共享内存的开山之作，第四篇文章研究的技术已经应用在数据中心服务器SSD和分布式文件系统中。
A New Primary Copy Method to Support Highly-Available Distributed Systems
图1 Barbara H. Liskov
第一篇文章是由Barbara H. Liskov教授和她的学生Brian M. Oki共同完成的。Liskov是美国第一个计算机科学女博士，一位计算机世界的杰出女性。在编程语言方面，她不仅发明了CLU和Argus编程语言，而且提出了面向对象五原则中著名的“里氏替换”原则（Liskov substitution principle）。在分布式系统领域，她除了提出Viewstamped Replication（简称VR），1999年她在扩展VR后提出了“Practical Byzantine Fault Tolerance”（简称BFT）问题。正是因为在编程语言和分布式领域的卓越贡献，Barbara H. Liskov教授于2008年获得了图灵奖。
早在上世纪70年代末，Liskov就已经发明了CLU语言，但在设计该语言时并没有考虑程序并行执行的应用场景。当时因特网已经开始被用来收发邮件和传输文件，通过网络连接多台机器进行分布式并行计算的萌芽已经产生。然而，Liskov发现当时并没有支持分布式并行计算的编程语言和系统。所以Liskov开始从研究单机的编程语言转向研究支持多机并行计算的语言。由此，Liskov提出了支持分布式计算的面向对象语言Argus。Argus设计的程序由称为guardians的对象组成，Argus中的每一个计算都作为单独的原子事务进行处理。执行的事务可能包括开始于某些guardians的远程调用，而一个远程调用还可能会触发另外一个guardians上的远程调用。一个事务是否能够成功提交，必须要求所有guardians的所有修改都要完成，否则所有修改都将被撤销。除此之外，还有许多事务并行运行，而Argus需要确保他们之间没有冲突。Liskov在设计Argus时重点关注的一个问题是怎样确保即使存在失败，最后也能顺利提交事务。一种直接的方法是将事务进行的修改记录在磁盘上。然而，这种方法只能确保修改不会丢失，它并不提供可用性。因为存储信息机器的故障将导致信息不可访问。另一种方法是利用分布式集群创建数据的副本：通过足够多的副本可以确保服务的高可用性，那么问题就变成了如何实现一个正确和高效的副本协议。为了解决这个问题，Liskov便提出了Viewstamped Replication（VR）。
Liskov在VR中假设分布式系统中节点失效和故障是常见的事件。为了实现系统的高可用性，通常需要准备数据的多个副本。然而，多个副本会出现数据更新时的不一致性问题。由此，VR在存有相同副本的N个节点中选择一个节点作为主节点，其他副本节点作为备份节点。数据只能通过主节点进行更新，当主节点更新完所有备份节点对应的数据后，才能成功完成数据的最终更新。当副本发生故障时，会自动重新组织副本；如果主节点无法访问，则选择新的主节点。这两种情况称为视图更改，并由视图管理算法完成。在主节点完成副本数据更新的过程中，为了解决网络传输时出现的消息丢失、重复、乱序和延迟等问题，VR的每一次数据更新均需要经过准备、提交两个阶段。而且更新每一个副本的过程均设计为一个副本状态机，以保证所有副本的数据更新均按照指定的相同顺序执行。这些设计使得VR能够解决故障-停止的异步系统多副本数据更新时的一致性问题，在一个具有2N+1个副本的分布式集群中，VR能够容忍最多不超过N个副本同时发生故障。
也许是英雄所见略同，接下来介绍的关于Paxos的文章与VR解决的问题比较相似，而且提出的时间也非常相近（提出时间相差不到一年，只是Paxos因为一些原因发表时间晚了10年）。这应该是一种巧合，因为Liskov曾公开表示她在发表VR时完全不知道Paxos。
The Part Time Parliament
图2. Leslie Lamport
第二篇文章“The Part Time Parliament”非常具有传奇色彩，这篇文章让作者Lamport第二次成功入选名人堂。关于Lamport的相关事迹在第二期的名人堂中已有描述，在这期名人堂中主要围绕这篇文章的诞生和被大家接受的故事展开介绍。
上世纪80年代，SRC(Systems Research Center)构建了一个被称为ECHO的容错文件系统。该系统当时被认为只要有半数以上的进程正常运行，就可以保证在发生任意数量错误（拜占庭将军错误除外）时的数据一致性。Lamport当时认为该系统声称的一致性在错误出现的情况下是不可能实现的，于是Lamport当时试图去证明他的这个想法，最终没有得到想要的结果，但是却发明了Paxos算法。
在写“The Part Time Parliament”这篇文章之前，Lamport已经通过拜占庭将军问题的表达方式(论文The Byzantine General Problem)使得一致性问题成功地被当时的人们接受。受此启发，Lamport 虚构了一个被称为Paxos的古希腊小岛城市；在这个岛上需要根据议会民主制制定法律，但在制定法律时所有的议会成员不一定全部同时出现，同时也没有限制批准决议和消息传递的时间（假设没有拜占庭将军问题），而且议会中的议员不能反对其它议员提出的决议。这种描述中的议员可以对应分布式系统中的各个节点，而制定的法律可以对应于系统的运行状态，议会中的成员是否参与制定过程的不确定性对应于节点或消息传输的不可靠性。一致性要求各个节点最终要进入一个一致的状态，所以要求Paxos小岛在制定法律条文时最终只能产生一个版本。
Lamport费尽心思地想通过描述一个失落的文明，以增加Paxos算法本身的趣味性。为了让这种形象化的描述更生动，Lamport甚至在几次演进中还亲自装扮成印第安纳琼斯style的考古学家，使得读者能够接受并认识到算法的重要性，但结果却适得其反。由于受到Paxos故事的干扰，那些阅读该论文的人包括 Nancy Lynch(“Distributed Algorithms”的作者)并没有意识到Paxos算法的重要性。虽然Lamport在1990就将“The Part Time Parliament”提交给TOCS，但是论文的三个审稿人都认为虽然文章不重要但还有些意思，只是应该删掉其中所有与Paxos相关的故事。Lamport对同行如此缺乏幽默感表示非常生气，他最终选择将论文搁置很多年也没有对其做任何修改和发表。
很多年后，SRC在Lamport的帮助下应用Paxos实现了一个分布式锁服务器，同时1992年的图灵奖得主Butler W.Lampson开始意识到Paxos的重要性，并在学术界为其摇旗呐喊。在这种背景下，历经八年时间的“The Part Time Parliament”没有进行任何修改就直接发表在1998年的TOCS上了。至此可以发现，一篇有深远影响文章的诞生和被发现的过程有时候也是充满曲折和戏剧性的。当然，Paxos的戏剧性与Lamport本人特立独行的个性也有关。
与VR相比，虽然VR比Paxos早发表了10年，但是Paxos由于被工业界广泛应用，尤其在Google的极力推荐下而名声大噪，VR却仍旧默默无闻。究其原因，应该是VR并没有从理论上完全解决分布式共识中的选主问题（主节点故障失效时如何选择主节点），而Paxos理论基础更完善，这保证了选主的唯一性。事实上，VR只是Paxos的第一个阶段，而Paxos可以称得上是第一个真正意义上的完备的三阶段一致性协议。实现Google Chubby系统的人曾说，所有的分布式算法都只是Paxos的一个特例。
Memory Coherence in Shared Virtual Memory Systems
图3. Kai Li 和Paul Hudak
第三篇文章是由普林斯顿大学的李凯教授和他在耶鲁大学时的博士导师Paul Hudak共同完成的。李凯教授的经历颇为传奇，他既是顶尖计算机科学家，同时也是上市公司的创始人。在学术方面，1989年李凯教授提出了分布式共享内存(DSM)技术，开创了新的研究方向，对后来的分布式计算和今天的云计算都有深远的影响。1998年他当选为ACM Fellow。在产业化方面，2001年，李凯教授与合伙人共同创办了Data Domain公司，研制出世界上第一款商用数据去重产品；2009年这家公司被EMC以24亿美元收购，他也被媒体冠以“身价最高的华人教授”。由于在科研与产业化方面的突出贡献，2012年李凯当选美国工程院院士。
李凯教授在1989年发表的“Memory Coherence in Shared Virtual Memory Systems”这篇文章开创了分布式共享内存(DSM)的研究领域，目前被引用已经超过1900多次。他的学生曾经问他当时是如何产生DSM这么好的想法，李凯老师回答说他当时在通过RPC实现一个基于消息的编程模型。在实现的过程中，他需要费劲处理不同机器之间的指针，于是他当时就萌生了一个问题：“为什么不在分布式系统中使用全局地址空间？”。他接下来带着这个问题深入探索，发现这个问题关键的挑战是如何保持多台机器之间的数据一致性。为了应对该挑战，他借鉴了CPU缓存一致性协议的思想，将其成功应用于DSM。实际上，李凯老师的回答分享了他怎么做研究和如何推动研究进展的思路，即在研究之初产生粗略的新想法之后，首先需要抓住和研究其中的关键挑战问题，然后需要专注于该问题直到得到成功解决。
李凯老师在一次访谈中也曾分享过他产业化的成功经验。他创办DataDomain之初的目的是为了节约数据备份的成本。因为当时使用磁带进行备份要比磁盘便宜，但是他们发现如果将数据压缩后存储在磁盘上的话，那么成本将和磁带差不多，于是便具有了市场竞争力。而这其中的关键挑战是需要研究一种有效的数据压缩算法，所以他们发明了一种数据压缩方法。当大规模数据中心比较普遍之后，这种数据压缩方法（也称为数据去重算法）应用在数据中心中将可以大大降低网络传输和数据存储的开销。借用李凯老师的话：“和虚拟机一起，是仅有的两种能几十倍降低功耗的技术”。正是将数据去重技术成功应用于新兴的场景中，使得DataDomain成为资本市场追捧的对象，最终被EMC高价收购。由此可见，好的研究成果是在解决某个应用场景中遇到的问题中产生的，但该成果的应用不一定仅局限于原来的场景，当它应用在新的场景中时甚至还会大放异彩。
The Design and Implementation of a Log-Structured File System
图4 Mendel Rosenblum(左二)和John K. Ousterhout(右一)
第四篇文章的作者Mendel Rosenblum和John K. Ousterhout都是斯坦福大学计算机科学的教授，从他们的经历来看都是学术界和工业界的风云人物。其中，Rosenblum是VMware的联合创始人，他和他的夫人Diane Greene曾分别担任VMware的首席科学家和CEO。2002年Mendel Rosenblum获得ACM SIGOPS Mark Weiser奖。2008年鉴于他对虚拟化技术的突出贡献，被当选为ACM Fellow。文章的第二位作者John K. Ousterhout曾就职于加州大学伯克利分校，他用了14年时间创立了两家公司：Scriptics 和 Electric Cloud。Ousterhout在分布式操作系统和文件系统中的工作也是众所周知的，他是Tcl脚本语言的创建者，并且他还是最新的分布式共识算法Raft的创建者之一。
Mendel Rosenblum和John K. Ousterhout于1992年在加州大学伯克利分校首次提出 “The Design and Implementation of a Log-Structured File System”（LFS）。当时设计LFS是基于一个假设：随着内存的不断增大，文件系统读缓存的命中率将会变得很高，因此磁盘的写I/O将取代读I/O成为系统的性能瓶颈。为了解决磁盘写I/O的性能瓶颈，LFS在修改磁盘数据和元数据时均是追加到文件的末尾，并没有在原地进行更新， 这种设计能将磁盘的随机写转变为顺序写，从而重复利用了磁盘写操作的带宽。具体而言，LFS像磁带驱动器一样将新数据顺序地附加在磁盘中，而不随机访问磁盘中的数据。LFS避免了代价高昂的磁头移动，这样可以使数据写入速度提高10倍，并且还能够更快地从计算机崩溃中恢复。另外，为了更好管理硬盘上的大空间块，LFS把多个log整合为一个segment，利用基于代价的清理策略对大空间块进行压缩和回收。论文在此理论上实现了Sprite LFS的文件系统，它的传输利用率高达70%（大大超越了Unix的5-10%)。
LFS是专门针对写操作进行优化的文件系统，这类文件系统的特点是使用日志结构管理数据。然而，当时设计LFS所基于的假设很长时间并没有成为现实，所以LFS最初找不到应用场景，只停留在研究阶段。除了Sprite LFS文件系统，其后比较典型的是NILFS2（New Implementation of Log Structured File System），因为NILFS2已经被linux 内核2.6.30采用了。 当Google（Google File System）和DataDomain等开始使用LFS构建分布式系统并处理可变大小的块时，LFS开始流行。最近，LFS成为SSD不可或缺的一部分，因为LFS就是SSD如何管理内部闪存芯片的关键技术。
小结
纵观第八届获奖的四篇文章，它们都可以称得上是分布式系统领域革命性的工作。虽然它们是二十多年前研究的技术，但这些技术今天依旧充满了活力，仍被应用在工业界流行的分布式系统中。另一方面也可以发现，好的研究工作都是具有前瞻性的，并非仅仅限于最初的应用场景，随着领域边界不断拓展和研究不断深入，应用视野很可能将更广阔。我们将在下一期为大家继续介绍第九届的获奖文章以及背后的故事。
作者
贝振东，中国科学院深圳先进技术研究院，博士，主要研究方向是分布式系统，大数据分析引擎性能自动优化，云计算和机器学习等
参考文献
[1] https://en.wikipedia.org/wiki/Barbara_Liskov
[2] Liskov B. From Viewstamped Replication to Byzantine Fault Tolerance[J]. Lecture Notes in Computer Science, 2010, 5959:121-149.
[3] https://en.wikipedia.org/wiki/Kai_Li
[4] https://en.wikipedia.org/wiki/Paul_Hudak
[5] https://en.wikipedia.org/wiki/Leslie_Lamport
[6] http://blog.sciencenet.cn/blog-414166-321619.html
[7] http://blog.sciencenet.cn/home.php?mod=space&uid=414166&do=blog&id=706460
[8] https://www.datrium.com/the-beauty-of-a-log-structured-filesystem/
[9] https://en.wikipedia.org/wiki/Mendel_Rosenblum
[10] https://en.wikipedia.org/wiki/John_Ousterhout
