大家好，我是坤哥！

上周我在極客時間某個課程看到某個講師在討論 ConcurrentHashMap(以下簡稱 CHM)是強一致性還是弱一致性時，提到這么一段話。

這個解釋網(wǎng)上也是流傳甚廣，那么到底對不對呢，在回答這個問題之前，我們得想清楚兩個問題。

• 什么是強一致性，什么是弱一致性。
• 上文提到 get 沒有加鎖，所以沒法即時獲取 put 的數(shù)據(jù)，也就意味著如果加鎖就可以立即獲取到 put 的值了?那么除了加鎖之外，還有其他辦法可以立即獲取到 put 的值嗎？

強一致性與弱一致性

強一致性

首先我們先來看第一個問題，什么是強一致性。

一致性(Consistency)是指多副本(Replications)問題中的數(shù)據(jù)一致性。可以分為強一致性、弱一致性。

強一致性也被可以被稱做原子一致性(Atomic Consistency)或線性一致性(Linearizable Consistency)，必須符合以下兩個要求。

任何一次讀都能立即讀到某個數(shù)據(jù)的最近一次寫的數(shù)據(jù)。

系統(tǒng)中的所有進程，看到的操作順序，都和全局時鐘下的順序一致。

簡單地說就是假定對同一個數(shù)據(jù)集合，分別有兩個線程 A、B 進行操作，假定 A 首先進行了修改操作，那么從時序上在 A 這個操作之后發(fā)生的所有 B 的操作都應(yīng)該能立即(或者說實時)看到 A 修改操作的結(jié)果。

弱一致性

與強一致性相對的就是弱一致性，即數(shù)據(jù)更新之后，如果立即訪問的話可能訪問不到或者只能訪問部分的數(shù)據(jù)。如果 A 線程更新數(shù)據(jù)后 B 線程經(jīng)過一段時間后都能訪問到此數(shù)據(jù)，則稱這種情況為最終一致性，最終一致性也是弱一致性，只不過是弱一致性的一種特例而已。

那么在 Java 中產(chǎn)生弱一致性的原因有哪些呢，或者說有哪些方式可以保證強一致呢，這就得先了解兩個概念，可見性和有序性。

一致性的根因：可見性與有序性

可見性

首先我們需要了解一下 Java 中的內(nèi)存模型。

上圖是 JVM 中的 Java 內(nèi)存模型，可以看到，它主要由兩部分組成，一部分是線程獨有的程序計數(shù)器，虛擬機棧，本地方法棧，這部分的數(shù)據(jù)由于是線程獨有的，所以不存在一致性問題(我們說的一致性問題往往指多線程間的數(shù)據(jù)一致性)，一部分是線程共享的堆和方法區(qū)，我們重點看一下堆內(nèi)存。

我們知道，線程執(zhí)行是要占用 CPU 的，CPU 是從寄存器里取數(shù)據(jù)的，寄存器里沒有數(shù)據(jù)的話，就要從內(nèi)存中取，而眾所周知這兩者的速度差異極大，可謂是一個天上一個地上，所以為了緩解這種矛盾，CPU 內(nèi)置了三級緩存，每次線程執(zhí)行需要數(shù)據(jù)時，就會把堆內(nèi)存的數(shù)據(jù)以 cacheline(一般是 64 Byte) 的形式先加載到 CPU 的三級緩存中來，這樣之后取數(shù)據(jù)就可以直接從緩存中取從而極大地提升了 CPU 的執(zhí)行效率(如下圖示)。

但是這樣的話由于線程加載執(zhí)行完數(shù)據(jù)后數(shù)據(jù)往往會緩存在 CPU 的寄存器中而不會馬上刷新到內(nèi)存中，從而導(dǎo)致其他線程執(zhí)行如果需要堆內(nèi)存中共享數(shù)據(jù)的話取到的就不會是最新數(shù)據(jù)了，從而導(dǎo)致數(shù)據(jù)的不一致。

舉個例子，以執(zhí)行以下代碼為例。

//線程1執(zhí)行的代碼
int i = 0;
i = 10;

//線程2執(zhí)行的代碼
j = i;

在線程 1 執(zhí)行完后 i 的值為 10，然后 2 開始執(zhí)行，此時 j 的值很可能還是 0，因為線程 1 執(zhí)行時，會先把 i = 0 的值從內(nèi)存中加載到 CPU 緩存中，然后給 i 賦值 10，此時的 10 是更新在 CPU 緩存中的，而未刷新到內(nèi)存中，當(dāng)線程 2 開始執(zhí)行時，首先會將 i 的值從內(nèi)存中(其值為 0)加載到 CPU 中來，故其值依然為 0，而不是 10，這就是典型的由于 CPU 緩存而導(dǎo)致的數(shù)據(jù)不一致現(xiàn)象。

那么怎么解決可見性導(dǎo)致的數(shù)據(jù)不一致呢，其實只要讓 CPU 修改共享變量時立即寫回到內(nèi)存中，同時通過總線協(xié)議(比如 MESI)通過其他 CPU 所讀取的此數(shù)據(jù)所在 cacheline 無效以重新從內(nèi)存中讀取此值即可。

有序性

除了可見性造成的數(shù)據(jù)不一致外，指令重排序也會造成數(shù)據(jù)不一致。

public class Reordering {

    private static boolean flag;
    private static int num;

    public static void main(String[] args) {
        Thread t1 = new Thread(new Runnable() {
            @Override
            public void run() {
                while (!flag) {
                    Thread.yield();
                }

                System.out.println(num);
            }
        }, "t1");
        t1.start();
        num = 5;                ① 
        flag = true;        ② 
    }
}

以上代碼執(zhí)行步驟可能很多人認(rèn)為是按正常的 ①，②，③ 執(zhí)行的，但實際上很可能編譯器會將其調(diào)換一下位置，實際的執(zhí)行順序可能是 ①③②，或 ②①③，也就是說 ①③ 是緊鄰的，為什么會這樣呢，因為執(zhí)行 1 后，CPU 會把 x = 1 從內(nèi)存加載到寄存器中，如果此時直接調(diào)用 ③ 執(zhí)行，那么 CPU 就可以直接讀取 x 在寄存器中的值 1 進行計算，反之，如果先執(zhí)行了語句 ②，那么有可能 x 在寄存器中的值被覆蓋掉從而導(dǎo)致執(zhí)行 ③ 后又要重新從內(nèi)存中加載 x 的值，有人可能會說這樣的指令重排序貌似也沒有多大問題呀，那么考慮如下代碼：

public class Reordering {

    private static boolean flag;
    private static int num;

    public static void main(String[] args) {
        Thread t1 = new Thread(new Runnable() {
            @Override
            public void run() {
                while (!flag) {
                    Thread.yield();
                }

                System.out.println(num);
            }
        }, "t1");
        t1.start();
        num = 5;                ① 
        flag = true;        ② 
    }
}

以上代碼最終輸出的值正常情況下是 5，但如果上述 ① ，② 兩行指令發(fā)生重排序，那么結(jié)果是有可能為 0 的，從而導(dǎo)致我們觀察到的數(shù)據(jù)不一致的現(xiàn)象發(fā)生，所以顯然解決方案是避免指令重排序的發(fā)生，也就是保證指令按我們看到的代碼的順序有序執(zhí)行，也就是我們常說的有序性，一般是通過在指令之間添加內(nèi)存屏障來避免指令的重排序。

那么如何保證可見性與有序性呢？

相信大家都非常熟悉了，使用 volatile 可以保證可見性與有序性，只要在聲明屬性變量時添加上 volatile 就可以讓此變量實現(xiàn)強一致性，也就是說上述的 Reordering 類的 flag 只要聲明為 volatile，那么打印結(jié)果就永遠(yuǎn)是 5!

好了，現(xiàn)在問題來了，CHM 到底是不是強一致性呢，首先我們以 Java 8 為例來看下它的設(shè)計結(jié)構(gòu)(和之前的版本相差不大，主要加上了紅黑樹提升了查詢效率)。

來看下這個 table 數(shù)組和節(jié)點的聲明方式(以下定義 8 和 之前的版本中都是一樣的)：

public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
    implements ConcurrentMap<K,V>, Serializable {
        transient volatile Node<K,V>[] table;
      ...
}

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V val;
    volatile Node<K,V> next;
      ...
}

可以看到 CHM 的 table 數(shù)組，Node 中的 值 val，下一個節(jié)點 next 都聲明為了 volatile，于是有學(xué)員就提出了一個疑問？

講師的回答也提到 CHM 為弱一致性的重要原因：即如果 table 中的某個槽位為空，此時某個線程執(zhí)行了 key，value 的賦值操作，那么此槽位會新增一個 Node 節(jié)點，在 JDK 8 以前，CHM 是通過以下方式給槽位賦 Node 的。

V put(K key, int hash, V value, boolean onlyIfAbsent) {
  lock();
  ...
    tab[index] = new HashEntry<K,V>(...);
  ...
    unlock();
}

然后是通過以下方式來根據(jù) key 來讀取 value 的。

V get(Object key, int hash) {
    if (count != 0) { // read-volatile
        HashEntry<K,V> e = getFirst(hash);
        while (e != null) {
            if (e.hash == hash && key.equals(e.key)) {
                V v = e.value;
                if (v != null)
                    return v;
                return readValueUnderLock(e); // recheck
            }
            e = e.next;
        }
    }
    return null;
}

可以看到 put 時是直接給數(shù)組中的元素賦值的，而由于 get 沒有加鎖，所以無法保證線程 A put 的新元素對執(zhí)行 get 的線程可見。

put 是有加鎖的，所以其實如果 get 也加鎖的話，那么毫無疑問 get 是可以立即拿到 put 的值的。為什么加鎖也可以呢，其實這是 JLS(Java Language Specification Java 語言規(guī)范) 規(guī)定的幾種情況，簡單地說就是支持 happens before 語義的可以保證數(shù)據(jù)的強一致性，在官網(wǎng)(https://docs.oracle.com/javase/specs/jls/se8/html/jls-17.html)中列出了幾種支持 Happens before 的情況，其中指出使用 volatile，synchronize，lock 是可以確保 happens before 語義的，也就是說使用這三者可以保證數(shù)據(jù)的強一致性，可能有人就問了，到底什么是 happens before 呢，其實本質(zhì)是一種能確保線程及時刷新數(shù)據(jù)到內(nèi)存，另一線程能實時從內(nèi)存讀取最新數(shù)據(jù)以保證數(shù)據(jù)在線程之間保持一致性的一種機制，我們以 lock 為例來簡單解釋下：

public class LockDemo {
  private int x = 0;

  private void test() {
    lock();
    x++;
    unlock();
  }
}

如果線程 1 執(zhí)行 test，由于拿到了鎖，所以首先會把數(shù)據(jù)(此例中為 x = 0)從內(nèi)存中加載到 CPU 中執(zhí)行，執(zhí)行 x++ 后，x 在 CPU 中的值變?yōu)?1，然后解鎖，解鎖時會把 x = 1 的值立即刷新到內(nèi)存中，這樣下一個線程再執(zhí)行 test 方法時再次獲取相同的鎖時又從內(nèi)存中獲取 x 的最新值(即 1)，這就是我們通常說的對一個鎖的解鎖, happens-before 于隨后對這個鎖的加鎖，可以看到，通過這種方式可以保證數(shù)據(jù)的一致性。

至此我們明白了：在 Java 8 以前，CHM 的 get，put 確實是弱一致性的，可能有人會問為什么不對 get 加鎖呢，加上了鎖不就可以確保數(shù)據(jù)的一致性了嗎，可以是可以，但別忘了 CHM 是為高并發(fā)設(shè)計而生的，加了鎖不就導(dǎo)致并發(fā)性大幅度下降了么，那 CHM 存在的意義是啥?

所以 put，get 就無法做到強一致性了嗎?

我們在上文中已經(jīng)知道，使用 volatile，synchronize，lock 是可以確保 happens before 語義的，同時經(jīng)過分析我們知道使用 synchronize，lock 加鎖的設(shè)計是不滿足我們設(shè)計 CHM 的初衷的，那么只剩下 volatile 了，遺憾的是由于 Java 數(shù)組在元素層面的元數(shù)據(jù)設(shè)計上的缺失，是無法表達(dá)元素是 final、volatile 等語義的，所以 volatile 可以修飾變量，卻無法修飾數(shù)組中的元素，還有其他辦法嗎?來看看 Java 8 是怎么處理的(這里只列出了寫和讀方法中的關(guān)鍵代碼)。

private static final sun.misc.Unsafe U;

// 寫
final V putVal(K key, V value, boolean onlyIfAbsent) {
      ...
    for (Node<K,V>[] tab = table;;) {
      if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
        if (casTabAt(tab, i, null,
                     new Node<K,V>(hash, key, value, null)))
          break;
      }
    }
      ...
}

static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                        Node<K,V> c, Node<K,V> v) {
  return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}


// 讀
public V get(Object key) {

  if ((tab = table) != null && (n = tab.length) > 0 &&
      (e = tabAt(tab, (n - 1) & h)) != null) {
    ...
  }
  return null;
}

@SuppressWarnings("unchecked")
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
  return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}

可以看到在 Java 8 中，CHM 使用了 unsafe 類來實現(xiàn)讀寫操作。

• 對于寫首先使用 compareAndSwapObject(即我們熟悉的 CAS)來更新內(nèi)存中數(shù)組中的元素。
• 對于讀則使用了 getObjectVolatile 來讀取內(nèi)存中數(shù)組中的元素(在底層其實是用了 C++ 的 volatile 來實現(xiàn) java 中的 volatile 效果，有興趣可以看看)。

由于讀寫都是直接對內(nèi)存操作的，所以通過這樣的方式可以保證 put，get 的強一致性，至此真相大白!Java 8 以后 put，get 是可以保證強一致性的!CHM 是通過 compareAndSwapObject 來取代對數(shù)組元素直接賦值的操作，通過 getObjectVolatile 來補上無法表達(dá)數(shù)組元素是 volatile 的坑來實現(xiàn)的。

注意并不是說 CHM 所有的操作都是強一致性的，比如 Java 8 中計算容量的方法 size() 就是弱一致性(Java 7 中此方法反而是強一致性)，所以我們說強/弱一致性一定要確定好前提(比如指定 Java 8 下 CHM 的 put，get 這種場景)。

總結(jié)其實 Java 8 對 CHM 進行了一番比較徹底的重構(gòu)，讓它的性能大幅度得到了提升，比如棄用 segment 這種設(shè)計，改用對每個槽位做分段鎖，使用紅黑樹來降低查詢時的復(fù)雜度，擴容時多個線程可以一起參與擴容等等，可以說 Java 8 的 CHM 的設(shè)計非常精妙，集 CAS，synchroinize，泛型等 Java 基礎(chǔ)語法之大成，又有巧妙的算法設(shè)計，讀后確實讓人大開眼界，有機會我會再和大家分享一下其中的設(shè)計精髓，另外我們對某些知識點一定要多加思考，最好能自己去翻翻源碼驗證一下真?zhèn)危嘈拍銜W(wǎng)上的一些謬誤會更容易看穿。