和 CopyOnWriteArrayList 提供线程安全性和已改进的可伸缩性

eJava理论与实践:并发集合类ConcurrentHashMap和CopyOnWriteArrayList提供线程安全性和已改进的可伸缩性级别:初级BrianGoetz([e-mail]),首席顾问,QuiotixCorp2003年9月28日DougLea的util.concurrent包除了包含许多其他有用的并发构造块之外，还包含了一些主要集合类型List和Map的高性能的、线程安全的实现。在本月的Java理论与实践中，BrianGoetz向您展示了用ConcurrentHashMap替换Hashtable或synchronizedMap，将有多少并发程序获益。您可以在本文的论坛中与作者以及其他读者共享您的想法（您也可以点击文章顶部或者底部的讨论进入论坛）。在Java类库中出现的第一个关联的集合类是Hashtable，它是JDK1.0的一部分。Hashtable提供了一种易于使用的、线程安全的、关联的map功能，这当然也是方便的。然而，线程安全性是凭代价换来的――Hashtable的所有方法都是同步的。此时，无竞争的同步会导致可观的性能代价。Hashtable的后继者HashMap是作为JDK1.2中的集合框架的一部分出现的，它通过提供一个不同步的基类和一个同步的包装器Collections.synchronizedMap，解决了线程安全性问题。通过将基本的功能从线程安全性中分离开来，Collections.synchronizedMap允许需要同步的用户可以拥有同步，而不需要同步的用户则不必为同步付出代价。Hashtable和synchronizedMap所采取的获得同步的简单方法（同步Hashtable中或者同步的Map包装器对象中的每个方法）有两个主要的不足。首先，这种方法对于可伸缩性是一种障碍，因为一次只能有一个线程可以访问hash表。同时，这样仍不足以提供真正的线程安全性，许多公用的混合操作仍然需要额外的同步。虽然诸如get()和put()之类的简单操作可以在不需要额外同步的情况下安全地完成，但还是有一些公用的操作序列，例如迭代或者put-if-absent（空则放入），需要外部的同步，以避免数据争用。有条件的线程安全性同步的集合包装器synchronizedMap和synchronizedList，有时也被称作有条件地线程安全――所有单个的操作都是线程安全的，但是多个操作组成的操作序列却可能导致数据争用，因为在操作序列中控制流取决于前面操作的结果。清单1中第一片段展示了公用的put-if-absent语句块――如果一个条目不在Map中，那么添加这个条目。不幸的是，在containsKey()方法返回到put()方法被调用这段时间内，可能会有另一个线程也插入一个带有相同键的值。如果您想确保只有一次插入，您需要用一个对Mapm进行同步的同步块将这一对语句包装起来。清单1中其他的例子与迭代有关。在第一个例子中，List.size()的结果在循环的执行期间可能会变得无效，因为另一个线程可以从这个列表中删除条目。如果时机不得当，在刚好进入循环的最后一次迭代之后有一个条目被另一个线程删除了，则List.get()将返回null，而doSomething()则很可能会抛出一个NullPointerException异常。那么，采取什么措施才能避免这种情况呢？如果当您正在迭代一个List时另一个线程也可能正在访问这个List，那么在进行迭代时您必须使用一个synchronized块将这个List包装起来，在List1上同步，从而锁住整个List。这样做虽然解决了数据争用问题，但是在并发性方面付出了更多的代价，因为在迭代期间锁住整个List会阻塞其他线程，使它们在很长一段时间内不能访问这个列表。集合框架引入了迭代器，用于遍历一个列表或者其他集合，从而优化了对一个集合中的元素进行迭代的过程。然而，在java.util集合类中实现的迭代器极易崩溃，也就是说，如果在一个线程正在通过一个Iterator遍历集合时，另一个线程也来修改这个集合，那么接下来的Iterator.hasNext()或Iterator.next()调用将抛出ConcurrentModificationException异常。就拿刚才这个例子来讲，如果想要防止出现ConcurrentModificationException异常，那么当您正在进行迭代时，您必须使用一个在Listl上同步的synchronized块将该List包装起来，从而锁住整个List。（或者，您也可以调用List.toArray()，在不同步的情况下对数组进行迭代，但是如果列表比较大的话这样做代价很高）。清单1.同步的map中的公用竞争条件Mapm=Collections.synchronizedMap(newHashMap());Listl=Collections.synchronizedList(newArrayList());//put-if-absentidiom--containsaracecondition//mayrequireexternalsynchronizationif(!map.containsKey(key))map.put(key,value);//ad-hociteration--containsraceconditions//mayrequireexternalsynchronizationfor(inti=0;ilist.size();i++){doSomething(list.get(i));}//normaliteration--canthrowConcurrentModificationException//mayrequireexternalsynchronizationfor(Iteratori=list.iterator();i.hasNext();){doSomething(i.next());}信任的错觉synchronizedList和synchronizedMap提供的有条件的线程安全性也带来了一个隐患――开发者会假设，因为这些集合都是同步的，所以它们都是线程安全的，这样一来他们对于正确地同步混合操作这件事就会疏忽。其结果是尽管表面上这些程序在负载较轻的时候能够正常工作，但是一旦负载较重，它们就会开始抛出NullPointerException或ConcurrentModificationException。可伸缩性问题可伸缩性指的是一个应用程序在工作负载和可用处理资源增加时其吞吐量的表现情况。一个可伸缩的程序能够通过使用更多的处理器、内存或者I/O带宽来相应地处理更大的工作负载。锁住某个共享的资源以获得独占式的访问这种做法会形成可伸缩性瓶颈――它使其他线程不能访问那个资源，即使有空闲的处理器可以调用那些线程也无济于事。为了取得可伸缩性，我们必须消除或者减少我们对独占式资源锁的依赖。同步的集合包装器以及早期的Hashtable和Vector类带来的更大的问题是，它们在单个的锁上进行同步。这意味着一次只有一个线程可以访问集合，如果有一个线程正在读一个Map，那么所有其他想要读或者写这个Map的线程就必须等待。最常见的Map操作，get()和put()，可能比表面上要进行更多的处理――当遍历一个hash表的bucket以期找到某一特定的key时，get()必须对大量的候选bucket调用Object.equals()。如果key类所使用的hashCode()函数不能将value均匀地分布在整个hash表范围内，或者存在大量的hash冲突，那么某些bucket链就会比其他的链长很多，而遍历一个长的hash链以及对该hash链上一定百分比的元素调用equals()是一件很慢的事情。在上述条件下，调用get()和put()的代价高的问题不仅仅是指访问过程的缓慢，而且，当有线程正在遍历那个hash链时，所有其他线程都被锁在外面，不能访问这个Map。（哈希表根据一个叫做hash的数字关键字（key）将对象存储在bucket中。hashvalue是从对象中的值计算得来的一个数字。每个不同的hashvalue都会创建一个新的bucket。要查找一个对象，您只需要计算这个对象的hashvalue并搜索相应的bucket就行了。通过快速地找到相应的bucket，就可以减少您需要搜索的对象数量了。译者注）get()执行起来可能会占用大量的时间，而在某些情况下，前面已经作了讨论的有条件的线程安全性问题会让这个问题变得还要糟糕得多。清单1中演示的争用条件常常使得对单个集合的锁在单个操作执行完毕之后还必须继续保持一段较长的时间。如果您要在整个迭代期间都保持对集合的锁，那么其他的线程就会在锁外停留很长的一段时间，等待解锁。实例：一个简单的cacheMap在服务器应用中最常见的应用之一就是实现一个cache。服务器应用可能需要缓存文件内容、生成的页面、数据库查询的结果、与经过解析的XML文件相关的DOM树，以及许多其他类型的数据。cache的主要用途是重用前一次处理得出的结果以减少服务时间和增加吞吐量。cache工作负载的一个典型的特征就是检索大大多于更新，因此（理想情况下）cache能够提供非常好的get()性能。不过，使用会妨碍性能的cache还不如完全不用cache。如果使用synchronizedMap来实现一个cache，那么您就在您的应用程序中引入了一个潜在的可伸缩性瓶颈。因为一次只有一个线程可以访问Map，这些线程包括那些要从Map中取出一个值的线程以及那些要将一个新的(key,value)对插入到该map中的线程。减小锁粒度提高HashMap的并发性同时还提供线程安全性的一种方法是废除对整个表使用一个锁的方式，而采用对hash表的每个bucket都使用一个锁的方式（或者，更常见的是，使用一个锁池，每个锁负责保护几个bucket）。这意味着多个线程可以同时地访问一个Map的不同部分，而不必争用单个的集合范围的锁。这种方法能够直接提高插入、检索以及移除操作的可伸缩性。不幸的是，这种并发性是以一定的代价换来的――这使得对整个集合进行操作的一些方法（例如size()或isEmpty()）的实现更加困难，因为这些方法要求一次获得许多的锁，并且还存在返回不正确的结果的风险。然而，对于某些情况，例如实现cache，这样做是一个很好的折衷――因为检索和插入操作比较频繁，而size()和isEmpty()操作则少得多。回页首ConcurrentHashMaputil.concurrent包中的ConcurrentHashMap类（也将出现在JDK1.5中的java.util.concurrent包中）是对Map的线程安全的实现，比起synchronizedMap来，它提供了好得多的并发性。多个读操作几乎总可以并发地执行，同时进行的读和写操作通常也能并发地执行，而同时进行的写操作仍然可以不时地并发进行（相关的类也提供了类似的多个读线程的并发性，但是，只允许有一个活动的写线程）。ConcurrentHashMap被设计用来优化检索操作；实际上，成功的get()操作完成之后通常根本不会有锁着的资源。要在不使用锁的情况下取得线程安全性需要一定的技巧性，并且需要对Java内存模型（JavaMemoryModel）的细节有深入的理解。ConcurrentHashMap实现，加上util.concurrent包的其他部分，已经被研究正确性和线程安全性的并发专家所正视。在下个月的文章中，我们将看看ConcurrentHashMap的实现的细节。ConcurrentHashMap通过稍微地松弛它对调用者的承诺而获得了更高的并发性。检索操作将可以返回由最近完成的插入操作所插入的值，也可以返回在步调上是并发的插入操作所添加的值（但是决不会返回一个没有意义的结果）。由ConcurrentHashMap.iterator()返回的Iterators将每次最多返回一个