風(fēng)人園

在7月份的那期 Java理論與實(shí)踐（“Concurrent collections classes”）中，我們簡(jiǎn)單地回顧了可伸縮性的瓶頸，并討論了怎么用共享數(shù)據(jù)結(jié)構(gòu)的方法獲得更高的并發(fā)性和吞吐量。有時(shí)候?qū)W習(xí)的最好方法是分析專家的成果，所以這個(gè)月我們將分析 Doug Lea 的util.concurrent 包中的 ConcurrentHashMap 的實(shí)現(xiàn)。JSR 133 將指定 ConcurrentHashMap 的一個(gè)版本，該版本針對(duì) Java 內(nèi)存模型（JMM）作了優(yōu)化，它將包含在 JDK 1.5 的 java.util.concurrent 包中。util.concurrent 中的版本在老的和新的內(nèi)存模型中都已通過線程安全審核。

針對(duì)吞吐量進(jìn)行優(yōu)化
ConcurrentHashMap 使用了幾個(gè)技巧來獲得高程度的并發(fā)以及避免鎖定，包括為不同的 hash bucket（桶）使用多個(gè)寫鎖和使用 JMM 的不確定性來最小化鎖被保持的時(shí)間——或者根本避免獲取鎖。對(duì)于大多數(shù)一般用法來說它是經(jīng)過優(yōu)化的，這些用法往往會(huì)檢索一個(gè)很可能在 map 中已經(jīng)存在的值。事實(shí)上，多數(shù)成功的 get() 操作根本不需要任何鎖定就能運(yùn)行。（警告：不要自己試圖這樣做！想比 JMM 聰明不像看上去的那么容易。util.concurrent 類是由并發(fā)專家編寫的，并且在 JMM 安全性方面經(jīng)過了嚴(yán)格的同行評(píng)審。 ）

多個(gè)寫鎖
我們可以回想一下，Hashtable（或者替代方案 Collections.synchronizedMap）的可伸縮性的主要障礙是它使用了一個(gè) map 范圍（map-wide）的鎖，為了保證插入、刪除或者檢索操作的完整性必須保持這樣一個(gè)鎖，而且有時(shí)候甚至還要為了保證迭代遍歷操作的完整性保持這樣一個(gè)鎖。這樣一來，只要鎖被保持，就從根本上阻止了其他線程訪問 Map，即使處理器有空閑也不能訪問，這樣大大地限制了并發(fā)性。

ConcurrentHashMap 摒棄了單一的 map 范圍的鎖，取而代之的是由 32 個(gè)鎖組成的集合，其中每個(gè)鎖負(fù)責(zé)保護(hù) hash bucket 的一個(gè)子集。鎖主要由變化性操作（put() 和 remove()）使用。具有 32 個(gè)獨(dú)立的鎖意味著最多可以有 32 個(gè)線程可以同時(shí)修改 map。這并不一定是說在并發(fā)地對(duì) map 進(jìn)行寫操作的線程數(shù)少于 32 時(shí)，另外的寫操作不會(huì)被阻塞——32 對(duì)于寫線程來說是理論上的并發(fā)限制數(shù)目，但是實(shí)際上可能達(dá)不到這個(gè)值。但是，32 依然比 1 要好得多，而且對(duì)于運(yùn)行于目前這一代的計(jì)算機(jī)系統(tǒng)上的大多數(shù)應(yīng)用程序來說已經(jīng)足夠了。 

map 范圍的操作
有 32 個(gè)獨(dú)立的鎖，其中每個(gè)鎖保護(hù) hash bucket 的一個(gè)子集，這樣需要獨(dú)占訪問 map 的操作就必須獲得所有32個(gè)鎖。一些 map 范圍的操作，比如說 size() 和 isEmpty()，也許能夠不用一次鎖整個(gè) map（通過適當(dāng)?shù)叵薅ㄟ@些操作的語義），但是有些操作，比如 map 重排（擴(kuò)大 hash bucket 的數(shù)量，隨著 map 的增長(zhǎng)重新分布元素），則必須保證獨(dú)占訪問。Java 語言不提供用于獲取可變大小的鎖集合的簡(jiǎn)便方法。必須這么做的情況很少見，一旦碰到這種情況，可以用遞歸方法來實(shí)現(xiàn)。

JMM概述
在進(jìn)入 put()、get() 和 remove() 的實(shí)現(xiàn)之前，讓我們先簡(jiǎn)單地看一下 JMM。JMM 掌管著一個(gè)線程對(duì)內(nèi)存的動(dòng)作 （讀和寫）影響其他線程對(duì)內(nèi)存的動(dòng)作的方式。由于使用處理器寄存器和預(yù)處理 cache 來提高內(nèi)存訪問速度帶來的性能提升，Java 語言規(guī)范（JLS）允許一些內(nèi)存操作并不對(duì)于所有其他線程立即可見。有兩種語言機(jī)制可用于保證跨線程內(nèi)存操作的一致性——synchronized 和 volatile。

按照 JLS 的說法，“在沒有顯式同步的情況下，一個(gè)實(shí)現(xiàn)可以自由地更新主存，更新時(shí)所采取的順序可能是出人意料的。”其意思是說，如果沒有同步的話，在一個(gè)給定線程中某種順序的寫操作對(duì)于另外一個(gè)不同的線程來說可能呈現(xiàn)出不同的順序， 并且對(duì)內(nèi)存變量的更新從一個(gè)線程傳播到另外一個(gè)線程的時(shí)間是不可預(yù)測(cè)的。

雖然使用同步最常見的原因是保證對(duì)代碼關(guān)鍵部分的原子訪問，但實(shí)際上同步提供三個(gè)獨(dú)立的功能——原子性、可見性和順序性。原子性非常簡(jiǎn)單——同步實(shí)施一個(gè)可重入的（reentrant）互斥，防止多于一個(gè)的線程同時(shí)執(zhí)行由一個(gè)給定的監(jiān)視器保護(hù)的代碼塊。不幸的是，多數(shù)文章都只關(guān)注原子性方面，而忽略了其他方面。但是同步在 JMM 中也扮演著很重要的角色，會(huì)引起 JVM 在獲得和釋放監(jiān)視器的時(shí)候執(zhí)行內(nèi)存壁壘（memory barrier）。

一個(gè)線程在獲得一個(gè)監(jiān)視器之后，它執(zhí)行一個(gè)讀屏障（read barrier）——使得緩存在線程局部?jī)?nèi)存（比如說處理器緩存或者處理器寄存器）中的所有變量都失效，這樣就會(huì)導(dǎo)致處理器重新從主存中讀取同步代碼塊使用的變量。與此類似，在釋放監(jiān)視器時(shí)，線程會(huì)執(zhí)行一個(gè)寫屏障（write barrier）——將所有修改過的變量寫回主存。互斥獨(dú)占和內(nèi)存壁壘結(jié)合使用意味著只要您在程序設(shè)計(jì)的時(shí)候遵循正確的同步法則（也就是說，每當(dāng)寫一個(gè)后面可能被其他線程訪問的變量，或者讀取一個(gè)可能最后被另一個(gè)線程修改的變量時(shí)，都要使用同步），每個(gè)線程都會(huì)得到它所使用的共享變量的正確的值。

如果在訪問共享變量的時(shí)候沒有同步的話，就會(huì)發(fā)生一些奇怪的事情。一些變化可能會(huì)通過線程立即反映出來，而其他的則需要一些時(shí)間（這由關(guān)聯(lián)緩存的本質(zhì)所致）。結(jié)果，如果沒有同步您就不能保證內(nèi)存內(nèi)容必定一致（相關(guān)的變量相互間可能會(huì)不一致），或者不能得到當(dāng)前的內(nèi)存內(nèi)容（一些值可能是過時(shí)的）。避免這種危險(xiǎn)情況的常用方法（也是推薦使用的方法）當(dāng)然是正確地使用同步。然而在有些情況下，比如說在像 ConcurrentHashMap 之類的一些使用非常廣泛的庫類中，在開發(fā)過程當(dāng)中還需要一些額外的專業(yè)技能和努力（可能比一般的開發(fā)要多出很多倍）來獲得較高的性能。

ConcurrentHashMap 實(shí)現(xiàn)
如前所述，ConcurrentHashMap 使用的數(shù)據(jù)結(jié)構(gòu)與 Hashtable 或 HashMap 的實(shí)現(xiàn)類似，是 hash bucket 的一個(gè)可變數(shù)組，每個(gè) ConcurrentHashMap 都由一個(gè) Map.Entry 元素鏈構(gòu)成，如清單1所示。與 Hashtable 和 HashMap 不同的是，ConcurrentHashMap 沒有使用單一的集合鎖（collection lock），而是使用了一個(gè)固定的鎖池，這個(gè)鎖池形成了bucket 集合的一個(gè)分區(qū)。

protected static class Entry implements Map.Entry {    protected final Object key;    protected volatile Object value;    protected final int hash;    protected final Entry next;    ...}

不用鎖定遍歷數(shù)據(jù)結(jié)構(gòu)
與 Hashtable 或者典型的鎖池 Map 實(shí)現(xiàn)不同，ConcurrentHashMap.get() 操作不一定需要獲取與相關(guān)bucket 相關(guān)聯(lián)的鎖。如果不使用鎖定，那么實(shí)現(xiàn)必須有能力處理它用到的所有變量的過時(shí)的或者不一致的值，比如說列表頭指針和 Map.Entry 元素的域（包括組成每個(gè) hash bucket 條目的鏈表的鏈接指針）。

大多并發(fā)類使用同步來保證獨(dú)占式訪問一個(gè)數(shù)據(jù)結(jié)構(gòu)（以及保持?jǐn)?shù)據(jù)結(jié)構(gòu)的一致性）。ConcurrentHashMap 沒有采用獨(dú)占性和一致性，它使用的鏈表是經(jīng)過精心設(shè)計(jì)的，所以其實(shí)現(xiàn)可以檢測(cè) 到它的列表是否一致或者已經(jīng)過時(shí)。如果它檢測(cè)到它的列表出現(xiàn)不一致或者過時(shí)，或者干脆就找不到它要找的條目，它就會(huì)對(duì)適當(dāng)?shù)腷ucket 鎖進(jìn)行同步并再次搜索整個(gè)鏈。這樣做在一般的情況下可以優(yōu)化查找，所謂的一般情況是指大多數(shù)檢索操作是成功的并且檢索的次數(shù)多于插入和刪除的次數(shù)。

使用不變性
不一致性的一個(gè)重要來源是可以避免得，其方法是使 Entry 元素接近不變性——除了值字段（它們是易變的）之外，所有字段都是 final 的。這就意味著不能將元素添加到 hash 鏈的中間或末尾，或者從 hash 鏈的中間或末尾刪除元素——而只能從 hash 鏈的開頭添加元素，并且刪除操作包括克隆整個(gè)鏈或鏈的一部分并更新列表的頭指針。所以說只要有對(duì)某個(gè) hash 鏈的一個(gè)引用，即使可能不知道有沒有對(duì)列表頭節(jié)點(diǎn)的引用，您也可以知道列表的其余部分的結(jié)構(gòu)不會(huì)改變。而且，因?yàn)橹底侄问且鬃兊模阅軌蛄⒓纯吹綄?duì)值字段的更新，從而大大簡(jiǎn)化了編寫能夠處理內(nèi)存潛在過時(shí)的 Map 的實(shí)現(xiàn)。

新的 JMM 為 final 型變量提供初始化安全，而老的 JMM 不提供，這意味著另一個(gè)線程看到的可能是 final 字段的默認(rèn)值，而不是對(duì)象的構(gòu)造方法提供的值。實(shí)現(xiàn)必須能夠同時(shí)檢測(cè)到這一點(diǎn)，這是通過保證 Entry 中每個(gè)字段的默認(rèn)值不是有效值來實(shí)現(xiàn)的。這樣構(gòu)造好列表之后，如果任何一個(gè) Entry 字段有其默認(rèn)值（零或空），搜索就會(huì)失敗，提示同步 get() 并再次遍歷鏈。

檢索操作
檢索操作首先為目標(biāo) bucket 查找頭指針（是在不鎖定的情況下完成的，所以說可能是過時(shí)的），然后在不獲取 bucket 鎖的情況下遍歷 bucket 鏈。如果它不能發(fā)現(xiàn)要查找的值，就會(huì)同步并試圖再次查找條目，如清單2所示：

  public Object get(Object key) {    int hash = hash(key);     // throws null pointer exception if key is null    // Try first without locking...    Entry[] tab = table;    int index = hash & (tab.length - 1);    Entry first = tab[index];    Entry e;    for (e = first; e != null; e = e.next) {      if (e.hash == hash && eq(key, e.key)) {        Object value = e.value;        // null values means that the element has been removed        if (value != null)           return value;        else          break;      }    }    // Recheck under synch if key apparently not there or interference    Segment seg = segments[hash & SEGMENT_MASK];    synchronized(seg) {       tab = table;      index = hash & (tab.length - 1);      Entry newFirst = tab[index];      if (e != null || first != newFirst) {        for (e = newFirst; e != null; e = e.next) {          if (e.hash == hash && eq(key, e.key))             return e.value;        }      }      return null;    }  }

刪除操作
因?yàn)橐粋€(gè)線程可能看到 hash 鏈中鏈接指針的過時(shí)的值，簡(jiǎn)單地從鏈中刪除一個(gè)元素不足以保證其他線程在進(jìn)行查找的時(shí)候不繼續(xù)看到被刪除的值。相反，從清單3我們可以看到，刪除操作分兩個(gè)過程——首先找到適當(dāng)?shù)?Entry 對(duì)象并把其值字段設(shè)為 null，然后對(duì)鏈中從頭元素到要?jiǎng)h除的元素的部分進(jìn)行克隆，再連接到要?jiǎng)h除的元素之后的部分。因?yàn)橹底侄问且鬃兊模绻硗庖粋€(gè)線程正在過時(shí)的鏈中查找那個(gè)被刪除的元素，它會(huì)立即看到一個(gè)空值，并知道使用同步重新進(jìn)行檢索。最終，原始 hash 鏈中被刪除的元素將會(huì)被垃圾收集。

  protected Object remove(Object key, Object value) {    /*      Find the entry, then         1. Set value field to null, to force get() to retry        2. Rebuild the list without this entry.           All entries following removed node can stay in list, but           all preceding ones need to be cloned.  Traversals rely           on this strategy to ensure that elements will not be          repeated during iteration.    */    int hash = hash(key);    Segment seg = segments[hash & SEGMENT_MASK];    synchronized(seg) {      Entry[] tab = table;      int index = hash & (tab.length-1);      Entry first = tab[index];      Entry e = first;      for (;;) {        if (e == null)          return null;        if (e.hash == hash && eq(key, e.key))           break;        e = e.next;      }      Object oldValue = e.value;      if (value != null && !value.equals(oldValue))        return null;           e.value = null;      Entry head = e.next;      for (Entry p = first; p != e; p = p.next)         head = new Entry(p.hash, p.key, p.value, head);      tab[index] = head;      seg.count--;      return oldValue;    }  }

圖1為刪除一個(gè)元素之前的 hash 鏈：

圖1. Hash鏈

圖2為刪除元素3之后的鏈：

圖2. 一個(gè)元素的刪除過程

插入和更新操作
put() 的實(shí)現(xiàn)很簡(jiǎn)單。像 remove() 一樣，put() 會(huì)在執(zhí)行期間保持 bucket 鎖，但是由于 put() 并不是都需要獲取鎖，所以這并不一定會(huì)阻塞其他讀線程的執(zhí)行（也不會(huì)阻塞其他寫線程訪問別的 bucket）。它首先會(huì)在適當(dāng)?shù)?hash 鏈中搜索需要的鍵值。如果能夠找到，value字段（易變的）就直接被更新。如果沒有找到，新會(huì)創(chuàng)建一個(gè)用于描述新 map 的新 Entry 對(duì)象，然后插入到 bucket 列表的頭部。

弱一致的迭代器
由 ConcurrentHashMap 返回的迭代器的語義又不同于 ava.util 集合中的迭代器；而且它又是弱一致的（weakly consistent）而非 fail-fast 的（所謂 fail-fast 是指，當(dāng)正在使用一個(gè)迭代器的時(shí)候，如何底層的集合被修改，就會(huì)拋出一個(gè)異常）。當(dāng)一個(gè)用戶調(diào)用 keySet().iterator() 去迭代器中檢索一組 hash 鍵的時(shí)候，實(shí)現(xiàn)就簡(jiǎn)單地使用同步來保證每個(gè)鏈的頭指針是當(dāng)前值。next()和 hasNext() 操作以一種明顯的方式定義，即遍歷每個(gè)鏈然后轉(zhuǎn)到下一個(gè)鏈直到所有的鏈都被遍歷。弱一致迭代器可能會(huì)也可能不會(huì)反映迭代器迭代過程中的插入操作，但是一定會(huì)反映迭代器還沒有到達(dá)的鍵的更新或刪除操作，并且對(duì)任何值最多返回一次。ConcurrentHashMap返回的迭代器不會(huì)拋出 ConcurrentModificationException 異常。

動(dòng)態(tài)調(diào)整大小
隨著 map 中元素?cái)?shù)目的增長(zhǎng)，hash 鏈將會(huì)變長(zhǎng)，因此檢索時(shí)間也會(huì)增加。從某種意義上說，增加 bucket 的數(shù)目和重排其中的值是非常重要的。在有些像 Hashtable 之類的類中，這很簡(jiǎn)單，因?yàn)楸３忠粋€(gè)應(yīng)用到整個(gè) map 的獨(dú)占鎖是可能的。在 ConcurrentHashMap 中，每 次一個(gè)條目插入的時(shí)候，如果鏈的長(zhǎng)度超過了某個(gè)閾值，鏈就被標(biāo)記為需要調(diào)整大小。當(dāng)有足夠多的鏈被標(biāo)記為需要調(diào)整大小以后，ConcurrentHashMap 就使用遞歸獲取每個(gè) bucket 上的鎖并重排每個(gè) bucket 中的元素到一個(gè)新的 、更大的 hash 表中。多數(shù)情況下，這是自動(dòng)發(fā)生的，并且對(duì)調(diào)用者透明。

不鎖定？
要說不用鎖定就可以成功地完成 get() 操作似乎有點(diǎn)言過其實(shí)，因?yàn)?code> Entry 的 value 字段是易變的，這是用來檢測(cè)更新和刪除的。在機(jī)器級(jí)，易變的和同步的內(nèi)容通常在最后會(huì)被翻譯成相同的緩存一致原語，所以這里會(huì)有一些 鎖定，雖然只是細(xì)粒度的并且沒有調(diào)度，或者沒有獲取和釋放監(jiān)視器的 JVM 開銷。但是，除語義之外，在很多通用的情況下，檢索的次數(shù)大于插入和刪除的次數(shù)，所以說由 ConcurrentHashMap 取得的并發(fā)性是相當(dāng)高的。

結(jié)束語
ConcurrentHashMap 對(duì)于很多并發(fā)應(yīng)用程序來說是一個(gè)非常有用的類，而且對(duì)于理解 JMM 何以取得較高性能的微妙細(xì)節(jié)是一個(gè)很好的例子。ConcurrentHashMap 是編碼的經(jīng)典，需要深刻理解并發(fā)和 JMM 才能夠?qū)懙贸觥Ｊ褂盟瑥闹袑W(xué)到東西，享受其中的樂趣——但是除非您是Java 并發(fā)方面的專家，否則的話您自己不應(yīng)該這樣試。