ACM SIGOPS名人堂 ( 第十三期 )

本期是“SIGOPS 名人堂”介绍的最后一期，我们将介绍前不久在上海评选出的2017年的两篇名人堂文章：

1. The Chubby lock service for loosely-coupled distributed systems.
2. Dynamo: Amazon’s Highly Available Key-value Store.

The Chubby lock service for loosely-coupled distributed systems

Mike Burrows

第一篇文章是发表在2006年的OSDI上的，作者是来自Google的Mike Burrows。论文中提出了一个分布式锁服务Chubby。Chubby本质上是一个分布式文件系统，不同的服务调用者可以通过创建、访问、关闭文件的方式获得拿锁、放锁的功能，从而解决分布式系统中的一致性问题。以在集群中选举master为例，所有的机器可以同时在Chubby中创建同一个文件。Chubby保证只有一个请求会被接受，而这一机器就能够成功创建文件，并将自己的IP地址写在文件中。而其它机器之后即可通过读取该文件，获得选举后的master机器的IP。

Chubby 系统架构图

Chubby的基本实现如上图所示，用户进程通过RPC进行服务调用。而Chubby内部则是由多个（文中实现采用5个）称为Chubby cell的机器组成的一个分布式文件系统。其中1个Chubby cell是master，而剩余的均为备份机器。只有master cell会处理用户请求，写操作会同步更新到所有的备份机器上。而Chubby内部对于master的选举则通过一致性协议（例如之前几期所介绍的Paxos协议）实现。

与前一期介绍的Google三驾马车（GFS，MapReduce，Bigtable）相比，Chubby对外并不是太知名，但实际上Chubby被Google内部广泛使用。例如GFS中对于master的选举，就是通过调用Chubby的服务实现的。而MapReduce与Bigtable的实现也都基于Chubby提供的服务。可以说Chubby为这三驾马车铺平了道路。

Dynamo: Amazon’s Highly Available Key-value Store

之前介绍了多篇来自Google的文章，而2017年入选的第二篇文章是来自亚马逊的Dynamo，发表于2007年的SOSP。Dynamo是亚马逊设计实现的一个高可靠的键-值存储系统，其目标在于满足亚马逊内部大量的数据管理需求（例如购物车、session，产品介绍等）。Dynamo通过牺牲ACID（A，原子性；C，一致性；I，隔离行；D，持久性）中的一致性（C），提升整个系统的可用性。

Dynamo使用的一致性哈希算法

Dynamo使用一致性hash算法将数据分在不同的机器上。上图显示的是一个哈希环，每个机器作为环上的一个节点。数据在插入时，它的键会被计算为一个哈希值，之后键-值对会被放入哈希环中顺时针方向最近的三个节点上。为了保证一致性，Dynamo采用了Quorum的一致性协议。写操作访问的机器数量与读操作访问的机器数量之和必需大于目标键-值对的备份数量。同时Dynamo采用了向量时钟、Hinted Handoff等技术来保证整个系统的ACID特性。

与之前介绍的几篇来自Google的工作类似，Dynamo无疑也是系统领域工业界学术成果的代表作之一。而这几年来大量来自工业界的论文入选“SIGOPS 名人堂”也显示了在系统领域，大型互联网企业对于学术研究的重要性与影响力。

小结：

本期介绍了2017年入选的两篇名人堂文章，均是来自国际顶尖互联网公司的工作。继2015年名人堂的GFS以来，已经有连续5项来自大型企业的工作入选名人堂。再看前不久在上海胜利召开的SOSP大会，今年接收的 39 篇论文中，更是有 19 篇论文来自工业界或是学术界与工业界的合作。这些充分显示了顶级IT公司对于系统领域学术研究的重要性。

到本期为止，我们长达13期的“SIGOPS 名人堂”介绍就正式完结了。在名人堂中，我们看到了系统领域各个研究方向的“奠基”之作；了解了一位位图灵奖获得者的杰出贡献；学习到了诸多顶级IT企业在系统领域的学术成果。相信这些久经考验的优秀学术成果能为各位读者带来收获，也祝大家在新的一年里做出更多有影响力的优秀工作！

作者：华志超。上海交通大学并行与分布式系统研究所 博士三年级，研究方向为虚拟化、系统安全。