前言

一提到線程安全的并發(fā)計(jì)數(shù)器，AtomicLong 必然是第一個(gè)被聯(lián)想到的工具。Atomic* 一系列的原子類以及它們背后的 CAS 無(wú)鎖算法，常常是高性能，高并發(fā)的代名詞。本文將會(huì)闡釋，在并發(fā)場(chǎng)景下，使用 AtomicLong 來(lái)充當(dāng)并發(fā)計(jì)數(shù)器將會(huì)是一個(gè)糟糕的設(shè)計(jì)，實(shí)際上存在不少 AtomicLong 之外的計(jì)數(shù)器方案。近期我研究了一些 Jdk1.8 以及 JCTools 的優(yōu)化方案，并將它們的對(duì)比與實(shí)現(xiàn)細(xì)節(jié)整理于此。

閱讀本文前

本文相關(guān)的基準(zhǔn)測(cè)試代碼均可在博主的 github 中找到，測(cè)試方式全部采用 JMH，這篇文章可以幫助你入門 JMH。

AtomicLong 的前世今生

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

在 Jdk1.7 中，AtomicLong 的關(guān)鍵代碼如下：

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 讀當(dāng)前 long 值
2. 自增
3. 自旋判斷新值與當(dāng)前值
4. 自旋成功，返回；否則返回 1

我們特別留意到 Jdk1.7 中 unsafe 使用的方法是 compareAndSwapLong，它與 x86 CPU 上的 LOCK CMPXCHG 指令對(duì)應(yīng)，并且在應(yīng)用層使用 while(true) 完成自旋，這個(gè)細(xì)節(jié)在 Jdk1.8 中發(fā)生了變化。

在 Jdk1.8 中，AtomicLong 的關(guān)鍵代碼如下：

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

Jdk1.7 的 CAS 操作已經(jīng)不復(fù)存在了，轉(zhuǎn)而使用了 getAndAddLong 方法，它與 x86 CPU 上的 LOCK XADD 指令對(duì)應(yīng)，以原子方式返回當(dāng)前值并遞增（fetch and add）。

當(dāng)問(wèn)及 Atomic* 高效的原因，回答 CAS 是不夠全面且不夠嚴(yán)謹(jǐn)?shù)模琂dk1.7 的 unsafe.compareAndSwapLong 以及 Jdk1.8 的 unsafe.getAndAddLong 才是關(guān)鍵，且 Jdk1.8 中不存在 CAS。

Jdk1.8 AtomicLong 相比 Jdk1.7 AtomicLong 的表現(xiàn)是要優(yōu)秀的，這點(diǎn)我們將在后續(xù)的測(cè)評(píng)中見(jiàn)證。

AtomicLong 真的高效嗎？

無(wú)論在 Jdk1.7 還是 Jdk1.8 中，Atomic* 的開(kāi)銷都是很大的，主要體現(xiàn)在：

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

拋開(kāi)上述導(dǎo)致 AtomicLong 慢的原因，AtomicLong 仍然具備優(yōu)勢(shì)：

1. 上述的第 4 點(diǎn)換一個(gè)角度也是 AtomicLong 的有點(diǎn)，相比下面要介紹的其他計(jì)數(shù)器方案，AtomicLong 能夠保證每次操作都精確的返回真實(shí)的遞增值。你可以借助 AtomicLong 來(lái)做并發(fā)場(chǎng)景下的遞增序列號(hào)方案，注意，本文主要討論的是計(jì)數(shù)器方案，而不是序列號(hào)方案。
2. 實(shí)現(xiàn)簡(jiǎn)單，回到那句話：“簡(jiǎn)單的架構(gòu)通常性能不高，高性能的架構(gòu)通常復(fù)雜度很高”，AtomicLong 屬于性能相對(duì)較高，但實(shí)現(xiàn)極其簡(jiǎn)單的那種方案，因?yàn)榇蟛糠值膹?fù)雜性，由 JMM 和 JNI 方法屏蔽了。相比下面要介紹的其他計(jì)數(shù)器實(shí)現(xiàn)，AtomicLong 真的太“簡(jiǎn)易”了。

看一組 AtomicLong 在不同并發(fā)量下的性能表現(xiàn)：

橫向?qū)Ρ龋瑢懙男阅芟啾茸x的性能要差很多，在 20 個(gè)線程下寫性能比讀性能差距了 4~5 倍。

縱向?qū)Ρ?，主要關(guān)注并發(fā)寫，線程競(jìng)爭(zhēng)激烈的情況下，單次自增耗時(shí)從 22 ns 增長(zhǎng)為了 488 ns，有明顯的性能下降。

實(shí)際場(chǎng)景中，我們需要統(tǒng)計(jì)系統(tǒng)的 qps、接口調(diào)用次數(shù)，都需要使用到計(jì)數(shù)的功能，寫才是關(guān)鍵，并不是每時(shí)每刻都需要關(guān)注自增后的返回值，而 AtomicLong 恰恰在核心的寫性能上有所欠缺。由此引出其他計(jì)數(shù)器方案。

認(rèn)識(shí) LongAdder

Doug Lea 在 JDK1.8 中找到了一個(gè)上述問(wèn)題的解決方案，他實(shí)現(xiàn)了一個(gè) LongAdder 類。

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

LongAdder 的 API 如下

LongAdder

你應(yīng)當(dāng)發(fā)現(xiàn)，LongAdder 和 AtomicLong 明顯的區(qū)別在于，increment 是一個(gè) void 方法。直接來(lái)看看 LongAdder 的性能表現(xiàn)如何。(LA = LongAdder, AL = AtomicLong, 單位 ns/op)：

我們從中可以發(fā)現(xiàn)一些有意思的現(xiàn)象，網(wǎng)上不少很多文章沒(méi)有從讀寫上對(duì)比二者，直接宣稱 LongAdder 性能優(yōu)于 AtomicLong，其實(shí)不太嚴(yán)謹(jǐn)。在單線程下，并發(fā)問(wèn)題沒(méi)有暴露，兩者沒(méi)有體現(xiàn)出差距；隨著并發(fā)量加大，LongAdder 的 increment 操作更加優(yōu)秀，而 AtomicLong 的 get 操作則更加優(yōu)秀。鑒于在計(jì)數(shù)器場(chǎng)景下的特點(diǎn)—寫多讀少，所以寫性能更高的 LongAdder 更加適合。

LongAdder 寫速度快的背后

網(wǎng)上分析 LongAdder 源碼的文章并不少，我不打算詳細(xì)分析源碼，而是挑選了一些必要的細(xì)節(jié)以及多數(shù)文章沒(méi)有提及但我認(rèn)為值得分析的內(nèi)容。

1、Cell 設(shè)計(jì)減少并發(fā)修改時(shí)的沖突

LongAdder

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

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

LongAdder 通過(guò)一系列算法，將計(jì)數(shù)結(jié)果分散在了多個(gè) Cell 中，Cell 會(huì)隨著并發(fā)量升高時(shí)發(fā)生擴(kuò)容，最壞情況下 Cell == CPU core 的數(shù)量。Cell 也是 LongAdder 高效的關(guān)鍵，它將計(jì)數(shù)的總值分散在了各個(gè) Cell 中，例如 5 = 3 + 2，下一刻，某個(gè)線程完成了 3 + (2 + 1) = 6 的操作，而不是在 5 的基礎(chǔ)上完成直接相加操作。通過(guò) LongAdder 的 sum() 方法可以直觀的感受到這一點(diǎn)（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、并發(fā)場(chǎng)景下高效獲取隨機(jī)數(shù)

LongAdder 內(nèi)部算法需要獲取隨機(jī)數(shù)，而 Random 類在并發(fā)場(chǎng)景下也是可以優(yōu)化的。

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

使用 ThreadLocalRandom 替代 Random，同樣出現(xiàn)在了 LongAdder 的代碼中。

3、longAccumulate

longAccumulate 方法是 LongAdder 的核心方法，內(nèi)部存在大量的分支判斷。首先和 Jdk1.7 的 AtomicLong 一樣，它使用的是 UNSAFE.compareAndSwapLong 來(lái)完成自旋，不同之處在于，其在初次 cas 方式失敗的情況下(說(shuō)明多個(gè)線程同時(shí)想更新這個(gè)值)，嘗試將這個(gè)值分隔成多個(gè) Cell，讓這些競(jìng)爭(zhēng)的線程只負(fù)責(zé)更新自己所屬的 Cell，這樣將競(jìng)爭(zhēng)壓力分散開(kāi)。

LongAdder 的前世今生

其實(shí)在 Jdk1.7 時(shí)代，LongAdder 還未誕生時(shí)，就有一些人想著自己去實(shí)現(xiàn)一個(gè)高性能的計(jì)數(shù)器了，比如一款 Java 性能監(jiān)控框架 dropwizard/metrics 就做了這樣事，在早期版本中，其優(yōu)化手段并沒(méi)有 Jdk1.8 的 LongAdder 豐富，而在 metrics 的最新版本中，其已經(jīng)使用 Jdk1.8 的 LongAdder 替換掉了自己的輪子。在最后的測(cè)評(píng)中，我們將 metrics 版本的 LongAdder 也作為一個(gè)參考對(duì)象。

JCTools 中的 ConcurrentAutoTable

并非只有 LongAdder 考慮到了并發(fā)場(chǎng)景下計(jì)數(shù)器的優(yōu)化，大名鼎鼎的并發(fā)容器框架 JCTool 中也提供了和今天主題相關(guān)的實(shí)現(xiàn)，雖然其名稱和 Counter 看似沒(méi)有關(guān)系，但通過(guò)其 Java 文檔和 API ，可以發(fā)現(xiàn)其設(shè)計(jì)意圖考慮到了計(jì)數(shù)器的場(chǎng)景。

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

在最后的測(cè)評(píng)中，我們將 JCTools 的 ConcurrentAutoTable 也作為一個(gè)參考對(duì)象。

最終測(cè)評(píng)

Jdk1.7 的 AtomicLong，Jdk1.8 的 AtomicLong，Jdk 1.8 的 LongAdder，Metrics 的 LongAdder，JCTools 的 ConcurrentAutoTable，我對(duì)這五種類型的計(jì)數(shù)器使用 JMH 進(jìn)行基準(zhǔn)測(cè)試。

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

將 5 個(gè)類都適配成 Counter 接口的實(shí)現(xiàn)類，采用 @State(Scope.Group)，@Group 將各組測(cè)試用例進(jìn)行隔離，盡可能地排除了互相之間的干擾，由于計(jì)數(shù)器場(chǎng)景的特性，我安排了 20 個(gè)線程進(jìn)行并發(fā)寫，1 個(gè)線程與之前的寫線程共存，進(jìn)行并發(fā)讀。Mode=avgt 代表測(cè)試的是方法的耗時(shí)，越低代表性能越高。

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

如果我們只關(guān)注 inc 即寫性能，可以發(fā)現(xiàn) jdk1.8 的 LongAdder 表現(xiàn)的最為優(yōu)秀，ConcurrentAutoTable 以及兩個(gè)版本的 LongAdder 在一個(gè)數(shù)量級(jí)之上；1.8 的 AtomicLong 相比 1.7 的 AtomicLong 優(yōu)秀很多，可以得出這樣的結(jié)論，1.7 的 CAS+LOCK CMPXCHG 方案的確不如 1.8 的 LOCK XADD 來(lái)的優(yōu)秀，但如果與特地優(yōu)化過(guò)的其他計(jì)數(shù)器方案來(lái)進(jìn)行比較，便相形見(jiàn)絀了。

如果關(guān)注 get 性能，雖然這意義不大，但可以見(jiàn)得，AtomicLong 的 get 性能在高并發(fā)下表現(xiàn)依舊優(yōu)秀，而 LongAdder 組合求值的特性，導(dǎo)致其性能必然存在一定下降，位列第二梯隊(duì)，而 ConcurrentAutoTable 的并發(fā)讀性能最差。

關(guān)注整體性能，CounterBenchmark.rw 是對(duì)一組場(chǎng)景的整合打分，可以發(fā)現(xiàn)，在我們模擬的高并發(fā)計(jì)數(shù)器場(chǎng)景下，1.8 的 LongAdder 獲得整體最低的延遲 98 ns，相比性能最差的 Jdk1.7 AtomicLong 實(shí)現(xiàn)，高了整整 10 倍有余，并且，隨著并發(fā)度提升，這個(gè)數(shù)值還會(huì)增大。

AtomicLong 可以被廢棄嗎？

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

本文重點(diǎn)討論的角度還是比較局限的：?jiǎn)螜C(jī)場(chǎng)景下并發(fā)計(jì)數(shù)器的高效實(shí)現(xiàn)。AtomicLong 依然在很多場(chǎng)景下有其存在的價(jià)值，例如一個(gè)內(nèi)存中的序列號(hào)生成器，AtomicLong 可以滿足每次遞增之后都精準(zhǔn)的返回其遞增值，而 LongAdder 并不具備這樣的特性。LongAdder 為了性能而喪失了一部分功能，這體現(xiàn)了計(jì)算機(jī)的哲學(xué)，無(wú)處不在的 trade off。

高性能計(jì)數(shù)器總結(jié)

AtomicLong ：并發(fā)場(chǎng)景下讀性能優(yōu)秀，寫性能急劇下降，不適合作為高性能的計(jì)數(shù)器方案。內(nèi)存需求量少。

LongAdder ：并發(fā)場(chǎng)景下寫性能優(yōu)秀，讀性能由于組合求值的原因，不如直接讀值的方案，但由于計(jì)數(shù)器場(chǎng)景寫多讀少的緣故，整體性能在幾個(gè)方案中最優(yōu)，是高性能計(jì)數(shù)器的首選方案。由于 Cells 數(shù)組以及緩存行填充的緣故，占用內(nèi)存較大。

ConcurrentAutoTable ：擁有和 LongAdder 相近的寫入性能，讀性能則更加不如 LongAdder。它的使用需要引入 JCTools 依賴，相比 Jdk 自帶的 LongAdder 并沒(méi)有優(yōu)勢(shì)。但額外說(shuō)明一點(diǎn)，ConcurrentAutoTable 的使用并非局限于計(jì)數(shù)器場(chǎng)景，其仍然存在很大的價(jià)值。

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

總結(jié)

以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，謝謝大家對(duì)腳本之家的支持。