《编程机制探析》第十一章 Copy on Write

《编程机制探析》第十一章 Copy on Write

Hash Table（哈希表，也叫散列表）是计算机编程中极为重要、极为常用的数据结构，其用法如下：我们可以用一个名字（name，或者叫做键值key）作为索引，把对应的内容存入到哈希表中；以后，我们可以提供对应的名字或者键值，从散列表把对应的内容取出来。用代码来表示就是这样：
hashTable.put(“myName”, myThing) // 以“myName”为键值，存入myThing。
fetched = hashTable.get(“myName”) //以“myName”为键值，取出之前存入的myThing。
散列表数据结构的特点是用空间换时间。散列表存入内容的时候，会用哈希（Hash）算法为每一个名字或者键值生成一个一定范围内的数字，这个数字对应散列表内部一个数组里的位置。这样，无论是存还是取，都可以快速地对应到数组里相应的位置，而不需要从头到尾地遍历数组。当然，这样做的速度确实是快了，但是，空间利用效率却不是那么高。数组里面很多地方很可能都是空的，只有对应上哈希算法结果的那些位置才有数据。这也是为什么哈希表也叫做散列表的原因——散列表可以更形象化地描述哈希表内部的数据分布状况。
不过，这些都是散列表的内部实现算法了。我们不关心这个。我们只在乎散列表的外在表现。我们只需要知道散列表的特性和用法就够了。
在Java语言中，有一个叫做Map（映射表）的接口，对应散列表的方法定义。HashMap类是Map接口的一个实现类，也是程序员经常使用的一个类。
Map的用法直观而简单，无需赘言。我们这里需要考虑的是，Map对象的线程同步问题。
当一个Map对象被多个线程同时访问的时候，就有可能产生访问冲突，甚至有可能破坏Map对象的内部结构。因此，这种情况下，我们必须用同步锁来解决线程访问冲突的问题。
当所有的线程都只是读取Map的时候，不会引起任何问题。但是，当有线程开始往Map对象里面写入数据的时候，就会引起问题了。因此，这是一个读写锁的控制问题。
上一章，我给出了读写锁的示意代码，并介绍了一个后来被JDK1.5引入的java.util.concurrent工具包，其中包括Lock, ReadWriteLock,  CurrentHashMap, CurrentReaderHashMap等类。
我设想了一下，CurrentHashMap应该是采用ReadWriteLock实现读写同步。代码看起来应该像这个样子。
class CocurrentHashMap
{
Private Map map = null;
final ReadWriteLock rwLock = new …. ;
final Lock readLock = rwLock.readLock();
final Lock writeLock = rwLock.writeLock();

// decorate the map as concurrent
public CocurrentHashMap(Map m){
   map = m;
}

// all write method, like put, putAll, remove, clear
public void putAll(Map m){
   writeLock.lock();
   try{
      map.putAll(m);
   }finally{
      writeLock.unlock();
   }
}

// all read method. like get, containsKey, containsValue, entrySet()
public Object get(Object key){
   readLock.lock();
   try{
      return map.get(key);
   }finally{
      readLock.unlock();
   }
};
}
上述代码中用到了Proxy Pattern，包装并代理了内部Map对象的所有方法。我感觉，真正的CurrentHashMap 的代码应该就是这种结构。但我看了CurrentHashMap 的源代码，发现不是这样。其中的实现比较复杂，把Table分成段进行分别管理。那个内部类 Segment extends ReentrantLock。 里面的 readValueUnderLock 方法里面用了lock()和unlock()这对方法来加锁和解锁。
/**
  * Read value field of an entry under lock. Called if value
  * field ever appears to be null. This is possible only if a
  * compiler happens to reorder a HashEntry initialization with
  * its table assignment, which is legal under memory model
  * but is not known to ever occur.
  */
  V readValueUnderLock(HashEntry<K,V> e) {
     lock();
     try {
         return e.value;
     } finally {
         unlock();
     }
}
上述的代码用到了try {} catch() {} finally {} 的结构。这是Java语言中进行异常（Exception）处理的通用格式。异常处理也是现代语言中的常见的特性。关于这块知识，我本人没有什么特殊的心得，也不觉得有多么重要。因此，还是请读者自行弥补这方面的知识。
另外需要特别说明的一点事，上述的代码引自于JDK1.5的代码，其中用到了泛型语法。JDK1.5之后，开始支持Generic Programming（泛型编程）。我们看到的代码中的<K, V>就属于泛型代码，其中的K和V代表类型的名字。在真正编程中，K和V这两个类型名需要对应到具体的类型上。这就相当于把K和V这两个类型参数化了。因此，泛型有时候也叫做参数化类型（Parameterized Type）。
我对于泛型这种技术没有太多的感觉，谈不上有什么恶感，也谈不上有什么好感。关于泛型，我不打算专门抽出一个独立章节来讲解，既然在这里遇到了，就顺便讲讲吧。
我们首先需要弄清楚的一个问题是，泛型的目的是什么？简单而言，就是为了Type Dispatch（类型分派）。比如，一个通用的算法，可以应用到int、float等多种数据类型上。但是，我们又苦于没有办法把这些数据类型综合成一个通用的数据类型。我们只好为每一个数据类型，写一套基本类似的算法。为了消除这种重复，语言设计者们想出了一个办法，就是把算法中那些可变的类型作为参数，抽离出来。这就形成了“参数化类型”（Parameterized Type），即泛型（Generic）。
为此，C++设计者开发出了模板技术（Template），能够让程序员只写一份带有参数类型的算法代码。然后，编译器帮助程序员进行Type Dispatch，为每一种类型生成一套针对该类型的算法代码。
C++ STL就是一个完美应用Template技术的例子。但是，C++ Template实在是太强大了。不仅可以参数化类型，还可以参数化代码中的其他部分。C++ Template设计人员没有抵抗住这种诱惑，开始滥用C++ Template，为各种重用场景生成代码，结果导致C++ Template完全误入歧途。嗯。我是这么认为的。因为，后来出现的各种极为强大、极为诡异的C++ Template用法，我是完全看不懂了。
C++的Template技术，本质上都是一种预编译技术。这种技术只和编译器相关，和运行时一点关系都没有。编译器在编译期就根据类型参数生成一堆堆的源代码，然后编译成一堆堆的目标代码。这种技术实际上造成了代码膨胀。不仅是源代码膨胀，目标代码也跟着膨胀。
Java的泛型技术借鉴了C++ Template技术。不过，控制得还不错，只借鉴到了“参数化类型”的程度，还没有疯狂到参数化其他的部分。
Java的泛型技术有个名字，叫做“类型擦除法”（Type Erasure），其含义也是说，其泛型定义只在编译期起作用，编译之后，泛型（参数化的类型）会被擦除掉。
C#的泛型的实现技术与Java有所不同，表现出来的特性也有所不同。有哪些不同呢？这个问题，我们放到后面合适的时候再讲。因为这个问题涉及到一些运行期类型获取的知识，而现在我们还没有讲到这方面的知识。
好了，关于泛型的知识，就告一段落。我们回到之前的主题，继续对JDK1.5引入的java.util.concurrent工具包的源代码进行研究。
我又了解了一下开发包中的CurrentReaderHashMap类。它的描述是这样的，“A version of Hashtable that supports mostly-concurrent reading, but exclusive writing.”
但是，我阅读其源代码的时候，看到其中的read ( get, contains, size …) 方法里面用到了synchronized关键字，仍然需要用到Java虚拟机提供的同步锁。既然read方法里面用到了同步锁，又如何保证可以同时读呢？这点我想不明白，也没有深究。
多年来的编程经验已经让我明白，看别人的代码是非常费劲的，还不如自己想，自己写，反而更清楚明白。这也是为什么人们说“修改代码比重写代码更难”的原因吧。
我不再想那么多，而是开始自己构想一个读的时候不需要同步、写的时候才需要同步的Map实现。在这个构想中，普通的读写锁模型不足以满足我的需求。因为，在使用读写锁的情况下，每个线程每次读Map的时候，都需要检查一下读写锁，这也是一种开销。我希望能够把这种开销完全消除。
这种需求是完全符合现实的。因为，我们在工作的过程中，经常遇到如下的需求：
用一个Map存放常用的Object，这个Map的并发读取的频率很高，而写入的频率很低，一般只在初始化、或重新装装载的时候写入。读写冲突虽然很少发生，不过一旦发生，Map的内部结构就可能乱掉，所以，我们不得不为Map加上同步锁。
这时候，一种叫做Copy on Write的设计思路进入了我的视野。Copy On Write是这样一种机制。当我们读取共享数据的时候，直接读取，不需要同步。当我们修改数据的时候，我们就把当前数据Copy一份副本，然后在这个副本上进行修改，完成之后，再用修改后的副本，替换掉原来的数据。这种方法就叫做Copy On Write。
Oracle关系数据库的数据修改就采用Copy On Write的模式。Copy On Write模式对并发读取的支持很好，但是在并发修改的时候，会有版本冲突的问题。可能有多个线程同时修改同一份数据，那么就同时存在多个修改副本，这多个修改副本可能会相互覆盖，导致修改丢失。因此，Oracle数据库引入了版本检查机制。即增加一个版本号字段，来检测是否存在并发修改。相似的版本控制机制存在于CVS、SVN等版本控制工具中。
在我们的Copy On Write Map中，我们只需要让新数据覆盖旧数据就可以了，因此不需要考虑版本控制的问题。这就大大简化了我们的实现。
基本思路就是让读和写操作分别在不同的Map上进行，每次写完之后，再把两个Map同步。代码如下：
/*
* Copy On Write Map
*
* Write is expensive.
* Read is fast as pure HashMap.
*
* Note: extra info is removed for free use
*/
import java.lang.Compiler;
import java.util.Collection;
import java.util.Map;
import java.util.Set;
import java.util.HashMap;
import java.util.Collections;
public class ReadWriteMap implements Map {
protected volatile Map mapToRead = getNewMap();
// you can override it as new TreeMap();
protected Map getNewMap(){
return new HashMap();
}
// copy mapToWrite to mapToRead
protected Map copy(){
Map newMap = getNewMap();
newMap.putAll(mapToRead);
return newMap;
}

// read methods
public int size() {
return mapToRead.size();
}
public boolean isEmpty() {
return mapToRead.isEmpty();
}

public boolean containsKey(Object key) {
return mapToRead.containsKey(key);
}

public boolean containsValue(Object value) {
return mapToRead.containsValue(value);
}

public Collection values() {
return mapToRead.values();
}

public Set entrySet() {
return mapToRead.entrySet();
}

public Set keySet() {
return mapToRead.keySet();
}

public Object get(Object key) {
return mapToRead.get(key);
}

// write methods
public synchronized void clear() {
mapToRead = getNewMap();
}

public synchronized Object remove(Object key) {
Map map = copy();
Object o = map.remove(key);
mapToRead = map;
return o;
}

public synchronized Object put(Object key, Object value) {
Map map = copy();
Object o = map.put(key, value);
mapToRead = map;
return o;
}

public synchronized void putAll(Map t) {
Map map = copy();
map.putAll(t);
mapToRead = map;
}
}
这个Map读取的时候，和普通的HashMap一样快。写的时候，先把内部Map复制一份，然后在这个备份上进行修改，改完之后，再让内部Map等于这个修改后的Map。这个方法是同步保护的，避免了同时写操作。可见，写的时候，开销相当大，应该尽量使用 putAll() 方法。
到此为止，线程同步的主要模型都讲完了。但是，关于线程的话题却还远没有结束。
一开始的时候，人们觉得进程（Process）的开销太大，因此，创建了线程（Thread）的概念模型。随着技术的进步，程序并发运行的需求越来越多，越来越高。人们开始觉得，线程（Thread）的开销也太大了。这时候，人们开始追求更轻量级的运行单元。各种概念模型纷纷呈现。比如，出现了一种叫做纤程（Fiber）的概念。Thread是线的意思，Fiber干脆就是纤维的意思，比线还要细。
当然，还有一些语言，不在名词上玩花头，而是默默地做实际工作。比如，一种叫做ErLang的函数式编程语言中，就实现了对进程、线程模型的完全重塑。在ErLang中，并没有Thread的概念，而是直接叫做Process。不过，这里的Process不再是对应操作系统的进程，而是，ErLang虚拟机自己管理的轻量级的运行单元。
在ErLang中，Process之间基本不需要同步。这是因为函数式编程语言的特性，在大多数正统的函数式编程语言中，变量近乎于常量，一生只能赋一次值，之后就不能再改变。用Java语言的术语来说就是，所有变量都是final的，不允许变量的值发生任何变化。既然变量不会变化，那还同步个啥子呢？有了这样的语法上的制约，ErLang就天生占了便宜，
那么，对于那些没有提供轻量级线程模型的语言（比如Java）来说，程序员又可以做那些努力来降低线程的开销呢？一种常见的做法就是线程池（Thread Pool），其工作原理如下：
首先，系统会启动一定数量的线程。这些线程就构成了一个线程池。
当有任务要做的时候，系统就从线程池里面选一个空闲的线程。然后把这个线程标记为“正在运行”。然后把任务传给这个线程执行。线程执行任务完成之后，就把自己标记为“空闲”。
这个过程并不难以理解。难以理解的是，一般来说，线程执行完成之后，运行栈等系统资源就会释放，线程对象就被回收了。一个已经完成的线程，又如何能回到线程池的空闲线程队列中呢？
秘诀就在于，线程池里面的线程永远不会执行完成。线程池里面的线程，都是一个无穷循环。具体代码如下：
Thread pooledThread {
   … theTask …. // theTask成员变量，表示要执行的任务

   … run() {
      while( true ) { // 永不停止的循环
         signal.wait(); // 等待系统的通知

         theTask.run(); // 执行任务
      }
   }
}
系统只需要调用 signal.notify() 就可以启动一个空闲线程。
在这段代码中，用到了一个JDK的Thread类。除此之外，JDK中还有一个Runnable接口，也是一个与线程开发相关的类型定义。关于Thread类和Runnable接口的具体定义和用法，请读者自行查阅。
关于线程的内容就到这里。有了线程的知识打底之后，我们下一章讲解一个非常重要的设计模式——Iterator Pattern。