ACM SIGOPS名人堂（第十一期）
我爱计算机 本文转自CNSys
在本期名人堂中，我们将介绍2015年获选的4篇文章：
- A fast file system for UNIX.
- Disconnected operation in the Coda File System
- Transactional memory: architectural support for lock-free data structures.
- Efficient software-based fault isolation.
前两篇文章均发表在TOCS期刊上，都是关于文件系统的，其中第一篇发表于1984年，介绍了UNIX文件系统FFS，第二篇1992年发表，介绍分布式文件系统Coda。第三和第四篇论文发表于1993年，其中第三篇在ISCA会议上发表的论文是事务内存的开山之作，第四篇介绍基于软件的故障隔离技术的论文，发表在SOSP会议上。这些研究工作在计算机系统和安全领域都产生非常深远的影响。
A fast file system for UNIX.
第一篇文章提出了一种面向UNIX的文件系统 Fast File System，简称FFS。FFS在文件系统领域具有开创性的意义，许多现代的文件系统都采用了与FFS类似的设计思路。例如目前广泛应用于UNIX， Solaris, Free BSD， HP-UX的UFS（Unix File System）文件系统，便是FFS的演化版本。在当时的80年代，计算机的内存小，磁盘也很小，存储的文件也是很小，FFS的设计目标是要提高文件系统存储小文件的性能。
FFS在原有Unix文件系统的基础上，进行一系列改进。第一个改进是提高了块的大小。FFS使用任何大于或等于4096的2的幂作为块的字节大小。相比搜寻和读取多个小块，对磁盘的连续读取能达到更高的带宽。然而，增加块的大小后，同时也增加了磁盘空间的浪费。FFS通过把块分片（fragments）来克服这个问题。分片（fragment）最小可以为512字节，一般是1024字节。FFS通过块位图来管理片，这样块位图不仅需要记录所有块的状态，还要记录所有片的状态。分片策略允许FFS为大文件采用较大的块，而又不会因为小文件浪费太多的空间。
FFS的第二个改进是减少磁盘头的移动。FFS使用柱面组的局域性来组织磁盘上的数据。 FFS把连续的位图块分散到每个柱面组里。本质上，柱面组就是磁盘的一个垂直切片。这个改进能提升性能的原因是，读取多个块的数据只需切换不同的磁头。而磁头的切换是一个电子操作，比其他物理操作（比如移动磁头）要快得多。
不过，现代的磁盘驱动已经把FFS做的大部分事情都做过了，而且做得更好更精确，将数据放在柱面组这一策略，现在由磁盘驱动程序来管理，而不是文件系统了。目前，随着SSD存储介质的兴起以及互联网中越来越多的大文件，FFS文件被后来各类改进的文件系统所替代，但FFS在文件系统领域依据占有相当分量的地位。
Marshall K. McKusick
论文的第一作者Marshall Kirk McKusick 是FreeBSD基金会的董事会成员，FreeBSD的长期维护者。他在加利福尼亚大学伯克利分校就读博士的时候就开始着手开发4.2BSD的文件系统，并曾2次就任USENIX协会的主席。值得一提的是，Marshall Kirk McKusick和他的同性伴侣Eric Allman在经过30多年的共同生活后，于2013年在加州登记结婚。Eric Allman也是一位计算机领域的大神级人物，他与McKusick一起贡献了很多BSD代码。著名的代码风格BSD Style，又名Allman Style，便是以Eric Allman命名。
Eric Allman
Disconnected Operation in the Coda File System
分布式文件系统Coda是CMU终身教授Mahadev Satyanarayanan 和James J. Kistler的研究成果。Satyanarayanan教授是移动和普适计算领域的著名学者，拥有有大量的研究成果，目前他也是边缘计算（Edge Computing）的积极倡导者。
Mahadev Satyanarayanan
Coda的创新特色在于能够让用户与服务器断开连接后，仍然能够操作文件，因此适合在网络连接没有保障的环境中使用。Coda的前身是著名的AFS文件系统，这两个系统都诞生于卡耐基梅隆大学。Coda的中心设计思想是,把客户需要用到的服务器文件事先缓存到本地磁盘中，无论客户与服务器主动断开还是被动断开,都可以在本地模拟服务器的行为,从而使客户能够继续操作。
Coda 系统示意图 (原图例作者：Gaich Muramatsu)
Coda是最早支持断连接操作的分布式文件系统，它对移动计算和普适计算有着重要的意义。在80年代，卡耐基·梅隆大学的校园里使用AFS来连接约1000个客户端。 在这样大的规模下，网络和服务器的故障几乎是每天都会出现的。当大量的移动用户出现后，用户随时可以断开网络连接，Coda这样支持网络暂时失效的分布式文件系统就显得非常有应用价值了。
Transactional Memory: Architectural Support for Lock-Free Data Structures
文章的第一作者Maurice Peter Herlihy 是布朗大学的教授，活跃于多处理器同步领域。Herlihy教授的贡献包括wait-free同步，线性数据同步，组合拓扑结构的分布式计算应用，软硬件事务内存。文章第二作者 J. Eliot B. Moss是多处理器同步和垃圾回收领域的计算机科学家，目前是马萨诸塞大学阿默斯特分校的计算机教授。
Maurice Peter Herlihy
J. Eliot B. Moss
该论文中事务的概念源自于数据库管理系统中数据库事务的概念。在数据库管理系统中，事务必须满足ACID性质，即原子性，一致性，隔离性和持久性。在多核环境下，采用任务并行时需要考虑线程间同步的问题。最原始最常见的方法是使用锁，只有获得了锁的线程在允许访问临界区，但是使用锁会发生一些问题，诸如性能下降明显，死锁等问题。因此后来产生了无锁编程的概念。
Herlihy和Moss提出的事务内存TM（Transactional Memory）是一种基于硬件实现的无锁同步机制。该机制基于SMP结构，通过增加事务Cache，并修改 Cache一致性协议来实现。事务内存不仅避免了传统锁机制带来的一系列问题，增强了线程间的并行度，而且简化了并行程序开发的过程，更利于程序模块的组合。Herlihy和Moss在事务内存上的开创性工作，直接影响了后续业界的基于软件的事务内存（Software Transaction Memory），以及软硬件结合实现的Hybrid TM。
Efficient Software-Based Fault Isolation
Robert-Wahbe
Robert Wahbe等人提出通过纯软件机制(software-based mechanism)实现了一种高效的软件故障隔离方法。在同一地址空间内、不同模块之间的故障隔离，该机制将可信模块的代码和数据限定在地址空间内一个逻辑对立的域中,并在沙箱中运行不可信模块的代码，这一方法有效地提升了软件安全性。目前已经被广泛用于在许多软件里保证系统运行的安全，例如我们每天都在使用的Web浏览器便使用了该方法。
具体来说，故障隔离是指持续监听系统，当错误发生的时候，识别并查看错误的类型和位置。基于软件的故障隔离方法包括两个部分，首先是将不被信任的代码和数据存放在故障域内，这个故障域在逻辑上是应用程序独立的地址空间。其次，修改一个不信任的模块的目标代码并防止它写入或跳转到故障域以外的地址。这两种方法都是可移植的，可以不限于特定的编程语言，因而被广泛使用。 对于频繁通信的模块，基于软件的故障隔离可以大大提高端到端的应用性能。
Robert Wahbe目前是Highspot的创始人，他曾是微软的一名高管，负责微软全世界的产品和业务管理。
小结
本期介绍了2015年获得的四篇文章，都是分布式系统领域具有里程碑意义的研究成果。这些系统和技术对工业界产生了巨大的影响，例如FFS中提出的超级块，inode等设计，至今还在许多现代文件系统中使用；Coda文件系统对分布式存储和云存储中解决数据一致性仍具有很好的指导意义；事务内存有效地提高的多核环境下任务同步的效率，而基于软件的故障隔离技术至今仍是保障系统安全的一个常用方法。我们将在下一期为大家继续介绍第**届的获奖文章以及背后的故事。
作者：任祖杰，吾雨森
参考文献：
[1]Practical File System Design http://www.nobius.org/~dbg/practical-file-system-design.pdf
[2]https://en.wikipedia.org/wiki/Marshall_Kirk_McKusick
[3]https://en.wikipedia.org/wiki/M._Satyanarayanan
[4]http://www.coda.cs.cmu.edu
[5]https://en.wikipedia.org/wiki/Transactional_memory
[6]Software Fault Isolation. https://people.eecs.berkeley.edu/~daw/teaching/cs261-f08/scribenotes/0916-tang.pdf
