「每日分享」Java並發計數器探祕

您的關注、點贊、轉發是對我們最大的支持

前言

一提到線程安全的併發計數器，AtomicLong 必然是第一個被聯想到的工具。Atomic* 一系列的原子類以及它們背後的 CAS 無鎖算法，常常是高性能，高併發的代名詞。本文將會闡釋，在併發場景下，使用 AtomicLong 來充當併發計數器將會是一個糟糕的設計，實際上存在不少 AtomicLong 之外的計數器方案。近期我研究了一些 Jdk1.8 以及 JCTools 的優化方案，並將它們的對比與實現細節整理於此。

相關面試題：

單機場景下，有比 AtomicLong 更高效的併發計數器方案嗎？

閱讀本文前

本文相關的基準測試代碼均可在博主的 github 中找到，測試方式全部採用 JMH，這篇文章可以幫助你入門 JMH。

AtomicLong 的前世今生

在 Java 中，Atomic* 是高效的，這得益於 sun.misc.Unsafe 提供的一系列底層 API，使得 Java 這樣的高級語言能夠直接和硬件層面的 CPU 指令打交道。並且在 Jdk1.7 中，這樣的底層指令可以配合 CAS 操作，達到 Lock-Free。

在 Jdk1.7 中，AtomicLong 的關鍵代碼如下：

public final long getAndIncrement() {
 while (true) {
 long current = get();
 long next = current + 1;
 if (compareAndSet(current, next))
 return current;
 }
}
public final boolean compareAndSet(long expect, long update) {
 return unsafe.compareAndSwapLong(this, valueOffset, expect, update);
}

1. get() 方法 volatile 讀當前 long 值
2. 自增
3. 自旋判斷新值與當前值
4. 自旋成功，返回；否則返回 1

我們特別留意到 Jdk1.7 中 unsafe 使用的方法是 compareAndSwapLong，它與 x86 CPU 上的 LOCK CMPXCHG 指令對應，並且在應用層使用 while(true) 完成自旋，這個細節在 Jdk1.8 中發生了變化。

在 Jdk1.8 中，AtomicLong 的關鍵代碼如下：

public final long getAndIncrement() {
 return unsafe.getAndAddLong(this, valueOffset, 1L);
}

Jdk1.7 的 CAS 操作已經不復存在了，轉而使用了 getAndAddLong 方法，它與 x86 CPU 上的 LOCK XADD 指令對應，以原子方式返回當前值並遞增（fetch and add）。

當問及 Atomic* 高效的原因，回答 CAS 是不夠全面且不夠嚴謹的，Jdk1.7 的 unsafe.compareAndSwapLong 以及 Jdk1.8 的 unsafe.getAndAddLong 才是關鍵，且 Jdk1.8 中不存在 CAS。

Jdk1.8 AtomicLong 相比 Jdk1.7 AtomicLong 的表現是要優秀的，這點我們將在後續的測評中見證。

AtomicLong 真的高效嗎？

無論在 Jdk1.7 還是 Jdk1.8 中，Atomic* 的開銷都是很大的，主要體現在：

1. 高併發下，CAS 操作可能會頻繁失敗，真正更新成功的線程佔少數。(Jdk1.7 獨有的問題)
2. 我之前的文章中介紹過“偽共享” (false sharing) 問題，但在 CAS 中，問題則表現的更為直接，這是“真共享”，與”偽共享“存在相同的問題：緩存行失效，緩存一致性開銷變大。
3. 底層指令的開銷不見得很低，無論是 LOCK XADD 還是 LOCK CMPXCHG，想深究的朋友可以參考 instruction_tables ，（這一點可能有點鑽牛角尖，但不失為一個角度去分析高併發下可行的優化）
4. Atomic* 所做的，比我們的訴求可能更大，有時候我們只需要計數器具備線程安全地遞增這樣的特性，但 Atomic* 的相關操作每一次都伴隨著值的返回。他是個帶返回值的方法，而不是 void 方法，而多做了活大概率意味著額外的開銷。

拋開上述導致 AtomicLong 慢的原因，AtomicLong 仍然具備優勢：

1. 上述的第 4 點換一個角度也是 AtomicLong 的優點，相比下面要介紹的其他計數器方案，AtomicLong 能夠保證每次操作都精確的返回真實的遞增值。你可以藉助 AtomicLong 來做併發場景下的遞增序列號方案，注意，本文主要討論的是計數器方案，而不是序列號方案。
2. 實現簡單，回到那句話：“簡單的架構通常性能不高，高性能的架構通常複雜度很高”，AtomicLong 屬於性能相對較高，但實現極其簡單的那種方案，因為大部分的複雜性，由 JMM 和 JNI 方法屏蔽了。相比下面要介紹的其他計數器實現，AtomicLong 真的太“簡易”了。

看一組 AtomicLong 在不同併發量下的性能表現。

橫向對比，寫的性能相比讀的性能要差很多，在 20 個線程下寫性能比讀性能差距了 4~5 倍。

縱向對比，主要關注併發寫，線程競爭激烈的情況下，單次自增耗時從 22 ns 增長為了 488 ns，有明顯的性能下降。

實際場景中，我們需要統計系統的 qps、接口調用次數，都需要使用到計數的功能，寫才是關鍵，並不是每時每刻都需要關注自增後的返回值，而 AtomicLong 恰恰在核心的寫性能上有所欠缺。由此引出其他計數器方案。

認識 LongAdder

Doug Lea 在 JDK1.8 中找到了一個上述問題的解決方案，他實現了一個 LongAdder 類。

@since 1.8
@author Doug Lea
public class LongAdder extends Striped64 implements Serializable {}

LongAdder 的 API 如下

LongAdder

你應當發現，LongAdder 和 AtomicLong 明顯的區別在於，increment 是一個 void 方法。直接來看看 LongAdder 的性能表現如何。(LA = LongAdder, AL = AtomicLong, 單位 ns/op)

我們從中可以發現一些有意思的現象，網上不少很多文章沒有從讀寫上對比二者，直接宣稱 LongAdder 性能優於 AtomicLong，其實不太嚴謹。在單線程下，併發問題沒有暴露，兩者沒有體現出差距；隨著併發量加大，LongAdder 的 increment 操作更加優秀，而 AtomicLong 的 get 操作則更加優秀。鑑於在計數器場景下的特點—寫多讀少，所以寫性能更高的 LongAdder 更加適合。

LongAdder 寫速度快的背後

網上分析 LongAdder 源碼的文章並不少，我不打算詳細分析源碼，而是挑選了一些必要的細節以及多數文章沒有提及但我認為值得分析的內容。

1. Cell 設計減少併發修改時的衝突

LongAdder

在 LongAdder 的父類 Striped64 中存在一個 volatile Cell[] cells; 數組，其長度是 2 的冪次方，每個 Cell 都填充了一個 @Contended 的 Long 字段，為了避免偽共享問題。

@sun.misc.Contended static final class Cell {
 volatile long value;
 Cell(long x) { value = x; }
 // ... ignore
}

LongAdder 通過一系列算法，將計數結果分散在了多個 Cell 中，Cell 會隨著併發量升高時發生擴容，最壞情況下 Cell == CPU core 的數量。Cell 也是 LongAdder 高效的關鍵，它將計數的總值分散在了各個 Cell 中，例如 5 = 3 + 2，下一刻，某個線程完成了 3 + (2 + 1) = 6 的操作，而不是在 5 的基礎上完成直接相加操作。通過 LongAdder 的 sum() 方法可以直觀的感受到這一點（LongAdder 不存在 get 方法）

public long sum() {
 Cell[] as = cells; Cell a;
 long sum = base;
 if (as != null) {
 for (int i = 0; i < as.length; ++i) {
 if ((a = as[i]) != null)
 sum += a.value;
 }
 }
 return sum;
}

這種惰性求值的思想，在 ConcurrentHashMap 中的 size() 中也存在，畢竟他們的作者都是 Doug Lea。

2.併發場景下高效獲取隨機數

LongAdder 內部算法需要獲取隨機數，而 Random 類在併發場景下也是可以優化的。

ThreadLocalRandom random = ThreadLocalRandom.current();
random.nextInt(5);

使用 ThreadLocalRandom 替代 Random，同樣出現在了 LongAdder 的代碼中。

3.longAccumulate

longAccumulate 方法是 LongAdder 的核心方法，內部存在大量的分支判斷。首先和 Jdk1.7 的 AtomicLong 一樣，它使用的是 UNSAFE.compareAndSwapLong 來完成自旋，不同之處在於，其在初次 cas 方式失敗的情況下(說明多個線程同時想更新這個值)，嘗試將這個值分隔成多個 Cell，讓這些競爭的線程只負責更新自己所屬的 Cell，這樣將競爭壓力分散開。

LongAdder 的前世今生

其實在 Jdk1.7 時代，LongAdder 還未誕生時，就有一些人想著自己去實現一個高性能的計數器了，比如一款 Java 性能監控框架 dropwizard/metrics 就做了這樣事，在早期版本中，其優化手段並沒有 Jdk1.8 的 LongAdder 豐富，而在 metrics 的最新版本中，其已經使用 Jdk1.8 的 LongAdder 替換掉了自己的輪子。在最後的測評中，我們將 metrics 版本的 LongAdder 也作為一個參考對象。

JCTools 中的 ConcurrentAutoTable

並非只有 LongAdder 考慮到了併發場景下計數器的優化，大名鼎鼎的併發容器框架 JCTool 中也提供了和今天主題相關的實現，雖然其名稱和 Counter 看似沒有關係，但通過其 Java 文檔和 API ，可以發現其設計意圖考慮到了計數器的場景。

An auto-resizing table of longs, supporting low-contention CAS operations.Updates are done with CAS’s to no particular table element.The intent is to support highly scalable counters, r/w locks, and other structures where the updates are associative, loss-free (no-brainer), and otherwise happen at such a high volume that the cache contention for CAS’ing a single word is unacceptable.

ConcurrentAutoTable

在最後的測評中，我們將 JCTools 的 ConcurrentAutoTable 也作為一個參考對象。

最終測評

Jdk1.7 的 AtomicLong，Jdk1.8 的 AtomicLong，Jdk 1.8 的 LongAdder，Metrics 的 LongAdder，JCTools 的 ConcurrentAutoTable，我對這五種類型的計數器使用 JMH 進行基準測試。

public interface Counter {
 void inc();
 long get();
}

將 5 個類都適配成 Counter 接口的實現類，採用 @State(Scope.Group)，@Group 將各組測試用例進行隔離，儘可能地排除了互相之間的干擾，由於計數器場景的特性，我安排了 20 個線程進行併發寫，1 個線程與之前的寫線程共存，進行併發讀。Mode=avgt 代表測試的是方法的耗時，越低代表性能越高。

Benchmark (counterType) Mode Cnt Score Error Units
CounterBenchmark.rw Atomic7 avgt 3 1049.906 ± 2146.838 ns/op
CounterBenchmark.rw:get Atomic7 avgt 3 143.352 ± 125.388 ns/op
CounterBenchmark.rw:inc Atomic7 avgt 3 1095.234 ± 2247.913 ns/op
CounterBenchmark.rw Atomic8 avgt 3 441.837 ± 364.270 ns/op
CounterBenchmark.rw:get Atomic8 avgt 3 149.817 ± 66.134 ns/op
CounterBenchmark.rw:inc Atomic8 avgt 3 456.438 ± 384.646 ns/op
CounterBenchmark.rw ConcurrentAutoTable avgt 3 144.490 ± 577.390 ns/op
CounterBenchmark.rw:get ConcurrentAutoTable avgt 3 1243.494 ± 14313.764 ns/op
CounterBenchmark.rw:inc ConcurrentAutoTable avgt 3 89.540 ± 166.375 ns/op
CounterBenchmark.rw LongAdderMetrics avgt 3 105.736 ± 114.330 ns/op 

CounterBenchmark.rw:get LongAdderMetrics avgt 3 313.087 ± 307.381 ns/op
CounterBenchmark.rw:inc LongAdderMetrics avgt 3 95.369 ± 132.379 ns/op
CounterBenchmark.rw LongAdder8 avgt 3 98.338 ± 80.112 ns/op
CounterBenchmark.rw:get LongAdder8 avgt 3 274.169 ± 113.247 ns/op
CounterBenchmark.rw:inc LongAdder8 avgt 3 89.547 ± 78.720 ns/op

如果我們只關注 inc 即寫性能，可以發現 jdk1.8 的 LongAdder 表現的最為優秀，ConcurrentAutoTable 以及兩個版本的 LongAdder 在一個數量級之上；1.8 的 AtomicLong 相比 1.7 的 AtomicLong 優秀很多，可以得出這樣的結論，1.7 的 CAS+LOCK CMPXCHG 方案的確不如 1.8 的 LOCK XADD 來的優秀，但如果與特地優化過的其他計數器方案來進行比較，便相形見絀了。

如果關注 get 性能，雖然這意義不大，但可以見得，AtomicLong 的 get 性能在高併發下表現依舊優秀，而 LongAdder 組合求值的特性，導致其性能必然存在一定下降，位列第二梯隊，而 ConcurrentAutoTable 的併發讀性能最差。

關注整體性能，CounterBenchmark.rw 是對一組場景的整合打分，可以發現，在我們模擬的高併發計數器場景下，1.8 的 LongAdder 獲得整體最低的延遲 98 ns，相比性能最差的 Jdk1.7 AtomicLong 實現，高了整整 10 倍有餘，並且，隨著併發度提升，這個數值還會增大。

AtomicLong 可以被廢棄嗎？

既然 LongAdder 的性能高出 AtomicLong 這麼多，我們還有理由使用 AtomicLong 嗎？

本文重點討論的角度還是比較侷限的：單機場景下併發計數器的高效實現。AtomicLong 依然在很多場景下有其存在的價值，例如一個內存中的序列號生成器，AtomicLong 可以滿足每次遞增之後都精準的返回其遞增值，而 LongAdder 並不具備這樣的特性。LongAdder 為了性能而喪失了一部分功能，這體現了計算機的哲學，無處不在的 trade off。

高性能計數器總結

• AtomicLong ：併發場景下讀性能優秀，寫性能急劇下降，不適合作為高性能的計數器方案。內存需求量少。
• LongAdder ：併發場景下寫性能優秀，讀性能由於組合求值的原因，不如直接讀值的方案，但由於計數器場景寫多讀少的緣故，整體性能在幾個方案中最優，是高性能計數器的首選方案。由於 Cells 數組以及緩存行填充的緣故，佔用內存較大。
• ConcurrentAutoTable ：擁有和 LongAdder 相近的寫入性能，讀性能則更加不如 LongAdder。它的使用需要引入 JCTools 依賴，相比 Jdk 自帶的 LongAdder 並沒有優勢。但額外說明一點，ConcurrentAutoTable 的使用並非侷限於計數器場景，其仍然存在很大的價值。

在前面提到的性能監控框架 Metrics，以及著名的熔斷框架 Hystrix 中，都存在 LongAdder 的使用場景，有興趣的朋友快去實踐一下 LongAdder 吧。

本文所有的 JMH 測試代碼，均可在我的 github 中獲得：https://github.com/lexburner/JMH-samples.git

閱讀更多 java全棧技術 的文章

關鍵字: Java 計數器 X86