西 坪

本文翻译自Google的[The Chubby lock service for loosely-coupled distributed systems]。翻译此文旨在传播更多信息。翻译水平有限，时间少且文章太长了，质量一般。完整版本请阅读原文。如果转载请完整转载，并包含本申明。

• 摘要
• 1 简介
• 2 设计
•   2.1 基础依据(Rationale)
•   2.2 系统结构
•   2.3 文件，目录和句柄
•   2.4 锁和序号
•   2.5 事件
•   2.7 缓存
•   2.8 会话 和 KeepAlives
•   2.9 故障切换
•   2.12 镜像 (mirroring)
• 3 扩展机制
• 4 实际应用，意外和设计错误
•   4.1 实际应用和表现
•   4.4 故障切换的问题
•   4.5 攻击性的客户端
•   4.6 Lessons learned
• 5 与相关工作的比较 (Comparison with related work)
• 6 总结
• 7 致谢
• 参考文献

=========================================================================

用于松耦合分布式系统的锁服务Chubby

摘要

我们描述了我们在Chubby锁服务方面的经历。Chubby的目标是为松散耦合的分布式系统，提供粗粒度的锁定、可靠的存储（尽管容量不大）。Chubby提供了一个很像带有意向锁的分布式文件系统的接口（interface)，不过它的设计重点是可用性和可靠性，而不是高性能。许多Chubby服务实例已经使用了超过一年，其中的几个实例每个都同时处理着数万台客户端。本文描述了最初的设计和预期使用，将之与实际的使用相比较，并解释了设计是怎样修改以适应这些差别的。

1. 简介

本文介绍了一种锁服务： Chubby。它被计划用在由适度规模的大量小型计算机通过高速网络互联构成的的松散耦合的分布式系统中。例如，一个Chubby实例（也叫Chubby单元(Cell))可能服务于通过1Gbit/s网络互联的一万台4核计算机。大部分Chubby单元限于一个数据中心或者机房，不过我们运行着至少一个各个副本(replica)之间相隔数千公里的Chubby单元。

锁服务的目的是允许它的客户应用们(clients)同步它们的活动，并对它们所处环境的基本信息取得一致。主要的目标包括在适度大规模的客户应用群时的可靠性、可用性，以及易于理解的语义；吞吐量和存储容量被认为是次要的。Chubby的客户端接口很像这样一个简单的文件系统：能执行整文件的读和写，另外还有意向锁和和多种诸如文件改动等事件的通知。

我们预期Chubby帮助开发者处理他们的系统中的粗粒度同步，特别是处理从一组各方面相当的服务器中选举领导者。例如Google文件系统（Google File System）^[7]使用一个Chubby锁来选择GFS Master 服务器，Bigtable^[3]以数种方式使用Chbbuy：选择领导者；使得Master可以发现它控制的服务器；使得客户应用(client)可以找到Master。此外，GFS和Bigtable都用Chubby作为众所周知的、可访问的存储小部分元数据(meta-data)的位置；实际上它们用Chubby作为它们的分布式数据结构的根。一些服务使用锁在多个服务器间（在粗粒度级别上）拆分工作。

在Chubby发布之前，Google的大部分分布式系统使用必需的、未提前规划的(ad hoc)方法做主从选举(primary election)（在工作可能被重复但无害时），或者需要人工干预（在正确性至关重要时）。对于前一种情况，Chubby可以节省一些计算能力。对于后一种情况，它使得系统在失败时不再需要人工干预，显著改进了可用性。

熟悉分布式计算的读者会意识到在多个相同体(peer)间primay选举是分布式协同(distributed consensus)问题的一个特例，同时意识到我们需要一种异步（asynchronous）通信的解决方案。异步（asynchronous）这个术语描述了绝大多数真实网络（real networks）如以太网或因特网的行为：它们容许数据包丢失、延时和重排序。（专家们一般应该了解（真实网络的）协议集建立在对环境做了很强假设的模型之上。） 异步一致性由Paxos协议^{[12, 13]}解决了。同样的协议被Oki和Liskov（见于他们有关Viewstamped replication的论文^{[19, $4]}）使用，其他人使用了等价的协议^{[14, $6]}。实际上，迄今为止我们遇到的所有可用的异步协同协议的核心都有Paxos。Paxos不需要计时假设来维持安全性，但必须引入时钟来确保活跃度(liveness)。这克服了Fisher等人的不可能性结果(impossibility result of Fisher et al.)^{[5, $1]}。

构建Chubby是一种满足上文提到的各种需求的工程上的工作，不是学术研究。我们声明没有提出新的算法和技术。本文的目的在于描述我们做了什么以及为什么这么做，而不是提出这些。在接下来的章节中，我们描述Chubby的设计和实现，以及在实际过程中它是怎么改变的。我们描述了预料之外的Chubby的使用方式，以及被证明是错误的特性。我们忽略了在其他文献中已经包括的细节，例如一致性协议或者RPC系统。
Read more…

Redis相比于她的一些竞争对手如Memcached, Tokyo Tyrant等，有一个实在是太吸引人的特性，就是事务。尽管它的事务支持不那么完美，但还是很难得。打算介绍一点使用心得，本想先写个简单介绍，不过觉得官方的文档写得相当不错，我索性做个翻译好了。

声明：本文翻译自Redis官方的MULTI/EXEC命令文档。翻译本文旨在传播更多信息，原著版权为Redis所有。转载请包含此声明。

WATCH key1 key2 ... keyN (Redis >= 2.1.0)
UNWATCH
MULTI
COMMAND_1 ...
COMMAND_2 ...
COMMAND_N ...
EXEC or DISCARD

MULTI, EXEC, DISCARD 和 WATCH 命令是Redis事务的基石。一个Redis事务允许一组Redis命令单步执行，并提供下面两个重要保证：

1. 一个事务中的所有命令串行执行。在事务的执行过程中不会为另一个客户端发起的请求提供服务。这保证了事务中的命令以原子操作的方式被执行。
2. 要么全部命令要么没有任何命令被处理。Exec命令触发事务中的所有命令的执行，所以如果一个在事务上下文中的客户端在调用MULTI（译注:貌似应该是EXEC，原文为MULTI）之前丢失了到服务器的链接，没有任何操作会被执行，而如果EXEC命令被调用了，所有的操作都会执行。一个例外是当AOF开启的时候：每个属于某个Redis事务的命令只要操作完成了的话就会记录在AOF中，所以如果Redis服务器崩溃或者被系统管理员以一种粗暴的方式杀死，可能只有部分操作被登记在AOF中。

从Redis 2.1.0开始，以类似于CAS（比较并设置）操作的乐观地锁定一组key的形式，在上面两种保证之外提供更进一步的保证也是可行的。这将在后文中详细阐述。

用法

通过MULTI命令进入一个事务。MULTI总是返回OK。然后用户可以发起多个命令。Redis将这些命令排队，而不是执行它们。一旦EXEC被调用，所有的命令都被执行。

调用DISCARD则将清空队列并退出事务。

下面是一个使用Ruby客户端的例子：

?> r.multi
=> "OK"
>> r.incr "foo"
=> "QUEUED"
>> r.incr "bar"
=> "QUEUED"
>> r.incr "bar"
=> "QUEUED"
>> r.exec
=> [1, 1, 2]

正如从上面的会话能看出来的那样，MULTI返回一个回复”数组”，每个元素都是事务中的某一个命令的回复，以命令排队时的顺序排列。

当一个Redis连接处于MULTI请求的上下文中时，所有的命令将用一个简单的字符串“QUEUED”回复，如果它们的语法和参数个数都正确的话。某些命令甚至被允许可在执行期间失败。

在协议层面上这更易于理解；在下面的例子中一个命令将在执行时失败，尽管它的语法是正确的：

Trying 127.0.0.1...
Connected to localhost.
Escape character is '^]'.
MULTI
+OK
SET a 3 
abc
+QUEUED
LPOP a
+QUEUED
EXEC
*2
+OK
-ERR Operation against a key holding the wrong kind of value

MULTI 返回一个两个元素的组合回复(bulk reply)，其中一个是 +OK码，另一个是 -ERR回复。这中情况下将由客户端库来选择一种合理的方式将错误提供给用户。

重要提示：即使在一个命令将会抛出错误时，队列中的所有其他的命令仍将被处理。在发现错误时，Redis不会停止命令的处理。

这是另一个例子，仍旧使用telnet的写协议，展示了语法错误会被尽可能快地报告：

MULTI
+OK
INCR a b c
-ERR wrong number of arguments for 'incr' command

这次由于语法错误，有问题的INCR命令根本不会被排队。

DISCARD

DISCARD用于放弃一个事务。没有命令将被执行，客户端的状态重新变回正常，在事务之外。这是个使用Ruby客户端的例子：

?> r.set("foo",1)
=> true
>> r.multi
=> "OK"
>> r.incr("foo")
=> "QUEUED"
>> r.discard
=> "OK"
>> r.get("foo")
=> "1"

基于WATCH的比较并设置(CAS)事务

WATCH(观察)用于给Redis事务提供CAS(比较并操作）行为。

调用了WATCH命令(WATCHed)的键将被监视以侦测针对键的修改。如果至少有一个监视的键在EXEC调用之前被修改，整个事务将被放弃，EXEC调用将会返回一个空对象(nil object)(一个Null Multi Bulk回复)来通知客户端事务失败了。

例如想象我们需要给一个键的值原子增一（我知道有INCR，让我们假设我们没有它）。

首先我们可能会像这样尝试:

val = GET mykey
val = val + 1
SET mykey $val

这只在一个给定时间内只有一个客户端做这个操作时可靠地工作。如果多个客户端将在大约同一时间内递增这个键，将会出现竞争条件(race condition)。例如客户端A和B将读到旧值，例如10。这个值将被这两个客户端递增到11，并最终设置这个键的值。于是最后的值将是11，而不是12。

多亏了WATCH，我们能够很好地解决这个问题：

WATCH mykey
val = GET mykey
val = val + 1
MULTI
SET mykey $val
EXEC

使用上面的代码，如果存在竞争条件并且另一个客户端在我们调用WATCH和EXEC之间修改了val的结果，事务将会失败。

我们只需要重复这个操作，寄希望于这次没有新的竞争。这种锁定形式叫做乐观锁定，并且在面对许多有多个客户端同时访问数目庞大的键的问题时，是一种十分强大的锁定形式，这种情况下冲突的可能性是很小的：通常操作不需要执行很多次。

WATCH的解释

那WATCH到底是什么呢？它是一个将使得EXEC受到约束的命令：我们要求Redis只在没有别的客户端修改任何一个被监视的键时执行事务。否则，根本就不会开始事务。（注意如果你监视(WATCH)一个瞬时的键，然后Redis在你监视了这个键后，将这个键过期(expire)了，EXEC仍将继续生效。更多信息）

WATCH可以被调用很多次。很简单地，所有的WATCH调用都将从调用时开始监视修改，直到EXEC被调用那一刻。

当EXEC被调用时，不管它是成功还是失败，所有的键都不再被监视。同样当一个客户连接被关闭时，所有的key不再被监视。

也可使用UNWATCH命令（没有参数）来清除被监视的键。有时这是有用的：因为可能我们需要执行一个事务来修改一些键，我们乐观锁定了这些键，但是在读取了这些键的当前内容后我们不想继续修改这些键了。这是我们只需要调用UNWATCH，于是这个连接就能够自由地用于新事务了。

WATCH用于实现ZPOP

一个很好的展示WATCH可被用于创建Redis不直接支持的新原子操作的例子是实现ZPOP，这是一个从有序集合(sorted set)中以原子方式弹出(pop)分数权值(score)较低的元素的命令。下面这是最简单的实现：

WATCH zset
ele = ZRANGE zset 0 0
MULTI
ZREM zset ele
EXEC

如果EXEC失败了(返回一个nil值)，我们只需要重复上面的操作。

返回值

多组合(Multi bulk)回复, 特别地:

一个MULTI/EXEC命令的返回值是一个多组合回复(multi bulk reply)，其中的每个元素是原子事务中的每个命令的返回值。

如果一个MULTI/EXEC事务因为监视命令(WATCH)检测到有键被修改了，返回一个空多组合回复(Null Multi Bulk reply)。

前两天，并行实验室发表了一篇有关volatile关键字的文章^[1]，而该文参考文献中的Sayonara volatile^[2]则更直接地要与volatile再见。两篇文章不谋而合，从c/c++到Java/.net，将这几门语言中的volatile过了一遍。列举出各种乱象，看上去volatile是如此不堪。

确实，volatile的语义不是那么常见。不是锁，但是它又拥有锁的部分特性（可见性，Java 5以后还有顺序保证）。如果不能正确理解，确实是个容易出错的地方。但是如果理解了用对了，仅就Java 5以及以后的版本而言，在目前阶段，volatile对性能上的提升还是有帮助的。

Volatile在Java中的语义以及历史

在维基百科上，对Java中的Volatile给了一个准确的定义^[6]：

• (In all versions of Java) There is a global ordering on the reads and writes to a volatile variable. This implies that every thread accessing a volatile field will read its current value before continuing, instead of (potentially) using a cached value. (However, there is no guarantee about the relative ordering of volatile reads and writes with regular reads and writes, meaning that it’s generally not a useful threading construct.)
• (In Java 5 or later) Volatile reads and writes establish a happens-before relationship, much like acquiring and releasing a mutex.

翻译过来就是：

• (在所有的Java版本中)对volatile变量上的读和写有一个全局排序。这暗示着每个线程访问一个volatile域时在往下运行之前将读到当前的值，而不是(有可能)使用一个缓存值。(然而，在volatie变量的读写与常规的读写之间的排序没有保证，意味着volatile通常不是一个有用的线程化的构造)
• (在Java5及之后版本中) Volatile读和写建立了一种happens-before关系，就像获取和释放一个互斥体。

在Java中，要正确地并发，必须在原子性、可见性和顺序性三个方面做出保证。在Java 5以前的版本中，volatile就已经实现了可见性，但是因为不能保证与普通变量读写之间的顺序，故而经常是没有用的。在Java 5以后的版本中，则额外保证了其与普通变量读写的顺序性。这里不是特别好懂，我们将javamx上的例子^{[3] [4]}改造一下：

public class MyBrokenFactory {
  private static volatile MyFactory instance;
  private int field1, field2 ...
 
  public static MyBrokenFactory getFactory() {
    // This is incorrect: don't do it at home, kids!
    if (instance == null) {
      synchronized (MyBrokenFactory.class) {
        if (instance == null)
          instance = new MyBrokenFactory();
      }
    }
    return instance;
  }
 
  private MyBrokenFactory() {
    field1 = ...
    field2 = ...
  }
}

上面的代码，在Java5以前，这个例子是不能正确工作的，因为volatile不保证对field1,field2的初始化（常规读写）一定在对volatile变量instance的写之前完成。但双检查锁本身并非volatile导致的，反而是Java 1.5的volatile让双检查锁能正确工作了。并行实验室将双检查锁不正确算在volatile的头上，有点冤了。

正是因为volatile在Java 5以前没有得到正确实现，更添加了不少复杂性。在Java 5之前，volatile基本没用处。

Volatile的实现机制分析

在Hotspot JVM中，
a) 在JVM层次，对volatile变量在线程本地工作区中不做缓存，对volatile的读写总是指向堆中的引用。可以视作在一个assign指令后总是跟着一个store指令^[5]。
b) 在机器码执行层次，通过内存屏障指令等迫使CPU不重排序，清除缓存，详细请参考《Memory Barriers and JVM Concurrency》的分析。

这与synchronized是有明显不同的，synchronized通常需要原子锁定，在SMP上要通过锁定总线等方式来实现，其代价在大多数平台上通常要比volatile高得多。

Performance

引入Volatile的主要目的，就是为了性能。我分下面几个方面来谈谈volatile在目前的Java平台中的作用。

直接性能比较

简单写了一个测试来比较一下volatile以及它的两种替代品 — 原子类型(atomic)和锁(此处指synchronized)。例子的代码改编自庄周梦蝶的slides《Java NIO trick and trap》中的SystemTimer（部分代码省略，完整源码在Github上）。这个测试只是一个例子，但其实在网络库里都要做定时，原理也大抵如此。

第一个版本如下：

package me.xiping.volitileverify;
public class SystemTimerV1 {
	private final static ScheduledExecutorService executor = Executors.newSingleThreadScheduledExecutor();
	private static final long tickUnit = Long.parseLong(System.getProperty(
			"notify.systimer.tick", "50"));
	private static volatile long time = System.currentTimeMillis();
 
	private static class TimerTicker implements Runnable {
		public void run() {
			time = System.currentTimeMillis();
		}
	}
 
	public static long currentTimeMillis() {
		return time;
	}
 
	static {
		executor.scheduleAtFixedRate(new TimerTicker(), tickUnit, tickUnit,
				TimeUnit.MILLISECONDS);
		Runtime.getRuntime().addShutdownHook(new Thread() {
			@Override
			public void run() {
				executor.shutdown();
			}
		});
	}
}

代码的重点在于volatile修饰的time域。time是一个只有一个线程写，其他线程都是读的域，没有并发修改，这里要解决的就是可见性。这正是volatile最适合的场合。

第二个版本使用synchronize关键字，与版本V1的不同如下：

package me.xiping.volitileverify;
public class SystemTimerV2 {
	....
	private static long time = System.currentTimeMillis();
 
	private static class TimerTicker implements Runnable {
		public void run() {
			synchronized (SystemTimerV2.class) {
				time = System.currentTimeMillis();
			}
		}
	}
 
	public static synchronized long currentTimeMillis() {
		return time;
	}
	....
}

第二个版本使用Java的内部锁来同步，既保证了原子性，也保证了可见性。第三个版本则是使用AtomicLong来实现的，如下：

package me.xiping.volitileverify;
 
public class SystemTimerV3 {
	......
	private static AtomicLong time = new AtomicLong(System.currentTimeMillis());
 
	private static class TimerTicker implements Runnable {
		public void run() {
			time.set(System.currentTimeMillis());
		}
	}
 
	public static long currentTimeMillis() {
		return time.get();
	}
	.....
}

在我的本上(cpu: 2core; OS: win7/cygwin; java:1.6.0_13)运行100万次，其性能如上面右图一所示(单位:ms)。

运行1000万次性能如图二所示(注意纵坐标的值与图一不一样)。

结论：性能上的优越性是显而易见的。volatile比AtomicLong明细要快，相比于synchronized则有几倍几十倍的提高了。
（欢迎在不同平台下测试并在评论中给一个反馈，反馈时请包括处理器信息（平台，core数），OS和Java版本。源代码在这里。编译和运行需要Ant，具体指南请参考这里。）

[Update, Dec15th： 图片是用Google Chart API 生成的，在源代码中包含着两个自动执行测试并生成图片URL的脚本。脚本需运行在Bash环境下，Windows上需在Cygwin下运行。]

Mina/netty对volatile的利用

写博文时顺便统计了下volatile在一些性能比较重要的程序中的情况，我顺手统计了手边有的mina和netty两个项目的核心代码，数据如下：

其中，mina是2009-3-31日Subversion的trunk，如下：

$svn info
Path: .
URL: http://svn.apache.org/repos/asf/mina/trunk
Repository Root: http://svn.apache.org/repos/asf
Repository UUID: 13f79535-47bb-0310-9956-ffa450edef68
Revision: 761900
Node Kind: directory
Schedule: normal
Last Changed Author: jvermillard
Last Changed Rev: 760493
Last Changed Date: 2009-03-31 23:49:15 +0800 (Tue, 31 Mar 2009)

netty的版本信息是：

$git log
commit 1ffb1aea75c36def56b709bd0892b19df78d9249
Author: Trustin Lee <trustin@gmail.com>
Date:   Fri Nov 12 10:20:03 2010 +0900

从侧面证明了volatile其实是很重要的，在性能很重要的场合，应用还是比较多的。

结论

总而言之，相比与Atomic和synchronized，volatile在性能上还是有显著的优势。

不过，正如文章中开头讨论的那样，volatile的缺点也显而易见，需要开发者对volatile的应用需要对内存模型的理解，否则容易误解而造成错误。在并发程序中，其仅可用于JVM支持的几个基本类型(int,short,long,double,reference, etc.)，而这几个基本类型皆有对应的完整并发特性的包装原子类型(java.util.concurrent.atomic.*)，虽然其性能与volatile有些差距，但大部分情形下也可代替volatile（但用synchronized来代替volatile是很不划算的）。

1. 为什么在多核多线程程序中要慎用volatile关键字？
2. Sayonara volatile
3. Double-checked Locking (DCL) and how to fix it
4. Double-checked Locking (DCL) and how to fix it (ctd)
5. JVM specification#Threads and Locks
6. Volatile variable#Java
7. http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html
8. Memory Barriers and JVM Concurrency

需要从远程数据库上导数据过来，但数据量不小，传输起来估计要花不少时间。看了下手册，Oracle 11g的expdp有下面几个比较符合这种情况的特性：

• Query: 使用Query过滤巨大表中要导出的数据。要注意的是指定query的语法，尤其是在shell下特殊字符的转义问题。
• Compression: 压缩数据。在11g中，有个compression选项，可以选择压缩 {ALL | DATA_ONLY | METADATA_ONLY | NONE}。在Oracle 11g中，不能像exp一样使用pipe给gzip的方式压缩了，要用gzip的话必须手动gzip。
• Parallel: 并行选项，在启用压缩时感觉效率有所提升。

下面是一个例子，使用 BLOCKS 方法的总估计: 2.159 GB，实际压缩后仅仅剩下 28M左右（因某些数据我通过Query限制了，压缩前实际大小可能在300M左右，且数据比较特殊）。 更具普遍性的压缩效果可参考这篇文章（需翻墙）。该文也比较了使用gzip与使用compression参数的压缩效果。

一个实际的例子，导出：

expdp dbaname/dbapwd DUMPFILE=expdumps%u.dmp DIRECTORY=DPUMP_DIR  TABLES='(T1,T2,T3)' 
\QUERY=T1:\"where mod\(ID,10\)=0\",T2:\"where mod\(ID,5\)=0\" PARALLEL=4 COMPRESSION=ALL

导入：

impdp dbaname/dbapwd DIRECTORY=dpump_dir1 DUMPFILE=expdumps%U.dmp

详细信息参考Oracle手册相关内容。