ACM SIGOPS名人堂（第十四期）
我爱计算机 本文转自 CNSys
本期我们将介绍2015年入选名人堂的四篇文中：
- Managing Update Conflicts in Bayou, a Weakly Connected Replicated Storage System.
- On micro-kernel construction.
- Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications.
- Memory resource management in VMware ESX server
Managing Update Conflicts in Bayou, a Weakly Connected Replicated Storage System
这篇文章发表于1995年SOSP会议上，提出了Bayou系统，即一个分布式的存储系统，主要针对弱连接情况下导致的应用并发访问冲突问题，提出了低开销的一致性维护策略和方法。
Bayou是一个弱一致性的存储系统，在架构设计上，侧重于支持多副本，不要求随时保证多副本之间的一致性，支持特定于应用程序的机制来检测和解决在这样一个系统中出现的更新冲突，确保副本间能够达到最终一致性（eventual consistency）。支持在网络断开情况下的访问操作是Bayou系统的中心目标，在弱连接环境下，Bayou只要求计算机之间（移动终端之间或移动终端与某服务器之间）偶尔成对（pair-wise）互联。
为降低一致性维护的开销，Bayou允许对本地副本进行读写操作，而不必马上与在其他服务器上的其他副本协调来确保一致性。这样应用程序的写入操作可能与其他的用户和应用成簇的写操作相冲突，所以Bayou系统提供了一个per-write冲突解决方案，即提供了一个称为依赖关系检查的冲突检测的新方法，每个写操作包括一个合并过程，如果这个写操作确定造成冲突之后，就会启动对应的合并过程解决冲突。
为了保证最终一致性，Bayou需要确保所有的更新最终传播到所有服务器，即所有的写操作按照同样的顺序（全局序列化顺序）在所有的服务器上执行，所有备份服务器以同样的方式解决冲突。coda和ficus等都是解决弱连接下的一致性问题，但他们的解决方案不同，coda和ficus是系统界别的冲突解决，而 Bayou允许应用级别的冲突解决。
本文的第一作者是Douglas B. Terry，本文是作者在伯克利任教时的工作，2000年，作者离开伯克利，开始在工业界任职，包括微软、三星等，现在亚马逊工作。
在当时的移动网络能力不强的情况下，如何保证移动应用的可用性，Bayou提出了很有价值的解决方法。且与许多今天的应用所面临的问题和解决问题的方案相关。当然，我们也注意到现在的移动互联网（特别是在城市中）保持连接的能力得到了很大的加强，移动终端一般通过移动互联网一直在线连接到data center，可简化面向移动端的系统维持一致性的相对复杂的策略。
On micro-kernel construction
本文发表于1995年SOSP会议上。当时，微内核架构设计被质疑，因为虽然从软件技术的角度来说，它要比集成内核要好，但是在实际使用中，它的性能并不能让人满意。大家普遍认为微内核的操作系统架构设计带来的效率不高和不够灵活是性能差的主要原因。但是本文提出了不同的看法，作者认为低效率和不灵活性不是微内核架构基本设计思想的问题，而是由于当前的微内核功能太多而过载或不适当的实现造成实现。作者在分析中发现当前微内核的IPC设计实现对整个内核的性能影响非常大，为此，作者实现了基于消息传递的IPC原语，并根据此重新设计了内存管理协议，使得微内核的性能有了显著的提升。
另外，作者介绍了L4微内核背后的核心设计思想，特别是最小性原则：一项特性当且仅当安全需要它在特权模式被实现时才应该在微内核里。这个原则是L4的核心设计，使得L4的性能能够超越其他微内核一个数量级。
本文作者是Jochen Liedtke，他L4微内核操作系统的创始人和总设计师，在微内核方面有许多优秀的工作，L4微内核家族是其中的重要代表。在L4之前，作者还设计了微内核Eumel和L3，L4就是在L3的基础上实现的。
起初L4只是一个功能相对单一且高度优化的内核，但由于它出色的性能和很小的体积而被工业界所认可，出现了L4微内核家族，被广泛的商业部署，至今仍有应用和拓展（比如通过形式化验证保证功能正确无bug的SeL4），是一个被工业界和历史检验的优秀的设计。
Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications
本文发表在2001年ACM SIGCOMM会议上，提出了一个能在P2P网络快速定位资源的的算法。P2P网络改变了传统的客户机和服务器模式中集中处理资源的方式，将互联网上的资源有效的组织起来，成为现在的BitTorrent和Skype等应用的基础。chord是结构化P2P领域最著名的算法之一，能够在大规模动态的系统中有效的进行关键字查询，同时可以优雅的处理系统中机器的加入和退出。其思想大量的应用于其后的学术工作和实际生产系统中，论文引用次数上万，使其成为分布式系统领域最为著名的工作之一。
Chord中使用分布式哈希表来组织网络中的节点和文件。分布式哈希表是一个可以在大量节点上提供传统的哈希快速定位能力的技术，每一个文件都表示为一个Key-value对，Key表示文件的索引，value表示文件的内容。通过get(key)和put(key, value) 接口来存取文件。
分布式哈希表的工作原理大概如下：首先，定义一个连续自然数组成的环形的空间，然后，每一个机器在加入网络时都随机生成一个数字，代表这个机器在这个空间中的位置。最后，通过哈希函数将文件的Key映射到分布式哈希表中，并且由顺时针距离该点最近的机器负责该文件。
Chord中使用SHA-1算法作为哈希函数，其环形空间的大小为2^160。同时为了降低线性查找所带来的开销，Chord使用幂次查找。每个节点中维护一个Finger表，表中第i项存放距离自己2^i距离的节点，每个节点找到自己Finger表中距离资源最近的节点，将查询转发给该节点，直到这个节点的后继节点就是该负责该资源的节点。下图为例，当N8节点查找资源54时，自己的Finger表中N42是距离54最近的节点。而后N42将请求转发给N51。N51发现自己的后驱节点N56即是54的负责节点，即将N56返回给N8。
*图片来自[4]
为了适应分布式环境下机器的频繁变化，Chord详细定义了节点的加入和失效操作。节点m加入时先向自己的后继节点请求整个Finger表并以此建立自己的Finger表。同时每个节点维护自己的前驱节点，并周期性的询问自己的后继节点，谁是其前驱节点，以此更新自己的后继节点项。如下图所示，完成这两步之后，m加入Chord环，并且可以正确的响应查询请求。当有多个节点同时加入同一段空间时，该算法也可正确处理。当节点n失效时，需要解决两个问题：其他节点的Finger表可能指向n，及m的前驱节点中的后驱节点项失效。对于第一个问题，当查询是Finger表中指向的节点失效，则当该项不存在，将请求转发给Finder表中上一项。对于第二个问题，每个节点需要维护一个后继节点列表，当m失效时，m的前驱节点将其后驱节点指向列表中第一个存活着的后驱节点。
Chord的工作由Ion Stoica, Robert Morris, David Karger, Frans Kaashoek, 和 Hari Balakrishnan在MIT完成，并发表于2001年。
第一作者Ion Stoica目前在伯克利担任RISELab的leader，除了Chord，他还是Apache Spark的作者之一。
Robert Morris在上一期的名人堂中已经介绍过。Morris最为著名的事迹是其在Cornell读研究生时在MIT释放的第一个蠕虫：Morris蠕虫，并造成多个电脑系统瘫痪，因此被定罪。他现在在MIT担任教授，同时还是Y combinator的创始人之一。
Memory resource management in VMware ESX server
本文发表在2002年OSDI会议上，介绍了多种优雅而高效的虚拟机内存管理技术，对后续基于虚拟机的内存管理技术奠定了很好的基础。
在虚拟机系统中，内存的超配（给多个VM分配的内存总量超过实际物理内存容量）是一种提高资源利用率的常见方法。为此需要根据多个VM的内存访问需求，灵活精确地把当前VM需要的数据/代码放在内存中，而不是放到类似硬盘这样的慢速存储设备上。比如，为了在1G的物理内存上运行两个1G的客户操作系统，页面置换是一个很重要的功能。为此，作者提出Balloon技术，在客户操作系统中插入一个Balloon模块。顾名思义，当内存需求紧张时，hypervisor通知Balloon模块，就像吹气球一样，Ballon向客户操作系统申请相应的物理内存。如果客户操作系统内存空余，则会直接给Ballon模块空余内存，否则则调用客户操作系统的页面置换算法将一部分页面置换出去。Ballon所分配得到的物理内存即是虚拟机系统（VMM or Hypervisor）可以回收的内存。为了决定使用往哪个VM的气球中充气，ESX引入Idle Memory Tax，对内存使用较少的虚拟机降低其权重，更容易被回收内存。
*图片来自[5]
在虚拟机系统中，内存的同质化严重，不必要地消耗了过多的内存。为了能够提高内存的使用效率，ESX建立一个哈希表，将内存的内容映射到哈希表中，判断是否有相同内容的物理页面可以共享，并使用COW技术应对共享页面的修改，极大地减少了内存消耗。
这篇文章的作者Carl Waldspurger从MIT CSAIL实验室毕业后，在DEC实验室（现HP Lab）担任研究员。发表文章的时候在VMware担任Principal Engineer。现在作为一个独立研究员和技术顾问，依然活跃在研究的一线。
作者: 陈渝, 清华大学计算机系副教授，从事操作系统、编程编译方向的研究
参考文献：
[1] Lakshman A, Malik P. Cassandra:a decentralized structured storage system[J]. Acm Sigops Operating Systems Review, 2010, 44(2):35-40.
[2] https://www.linkedin.com/in/doug-terry-08b2b68/
[3] https://en.wikipedia.org/wiki/Jochen_Liedtke
[4] http://www.yeolar.com/note/2010/04/06/p2p-chord/
[5] vSphere Resource Management.
