StampedLock 與低爭用計數器

1. 為什麼 ReadWriteLock 並不總是夠用

寫入競爭高時的問題

ReadWriteLock（最常見的是 ReentrantReadWriteLock）在大多數執行緒只讀資料、寫入者很少時運作良好。此時多個執行緒可以同時讀取，而寫入只在短時間內阻塞存取。

問題出現在當進行寫入的執行緒比預期更多，或它們經常在讀與寫之間切換。若寫入操作耗時較長，執行緒就會更久地等待鎖釋放。結果是對資料的競爭升高，讀寫都變慢，ReadWriteLock 的效率下降。

昂貴的鎖模式切換

當執行緒從讀取模式切換到寫入模式（或反之）時，底層會進行繁瑣的檢查：必須確認沒有其他人正在寫入、所有讀者都已退出，然後才允許寫入。

如果這種切換很頻繁，就會產生延遲。執行緒開始排隊，效能下降——特別是當同時存在大量讀寫操作時。

ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
Lock readLock = lock.readLock();
Lock writeLock = lock.writeLock();

// 讀取
readLock.lock();
try {
    // 讀取資料
} finally {
    readLock.unlock();
}

// 寫入
writeLock.lock();
try {
    // 修改資料
} finally {
    writeLock.unlock();
}

每次執行緒在 readLock 與 writeLock 之間切換時，系統都要做完所有檢查以避免衝突。若這種切換很多——成本就很高。

2. StampedLock：現代化的同步方式

StampedLock 是 Java 8 引入的現代同步機制。它結合了 ReadWriteLock 的理念，但新增了樂觀讀取模式，並且不是直接用鎖，而是用「印章」（stamps）——需要顯式釋放的特殊權杖。

重點特色：

• 三種模式：write lock（獨占寫入）、read lock（共享讀取）、optimistic read（無鎖的樂觀讀取）。
• 不支援重入（reentrancy）：同一執行緒不可再次取得同一把鎖.
• 在讀多寫少時具有高效能。
• 需要顯式管理印章（stamp）。

樂觀讀取: tryOptimisticRead + validate

樂觀讀取是一種完全不加鎖就讀取資料的模式，假設此刻沒有寫入發生。讀取之後必須用方法 validate(stamp) 檢查在讀取期間是否發生過寫入。

import java.util.concurrent.locks.StampedLock;

public class Point {
    private double x, y;
    private final StampedLock lock = new StampedLock();

    public double distanceFromOrigin() {
        long stamp = lock.tryOptimisticRead();
        double currentX = x;
        double currentY = y;
        // 檢查讀取期間是否有寫入發生
        if (!lock.validate(stamp)) {
            // 若有寫入—改用一般的 read lock
            stamp = lock.readLock();
            try {
                currentX = x;
                currentY = y;
            } finally {
                lock.unlockRead(stamp);
            }
        }
        return Math.hypot(currentX, currentY);
    }
}

運作方式：

• tryOptimisticRead() 會回傳印章（long），只要沒有人在寫入，它就「有效」。
• 讀取 x 與 y 的值。
• validate(stamp) 檢查在讀取的起訖之間是否出現寫入。
• 若一切正常—沿用剛剛讀到的值；若發生寫入—改用一般的 readLock 重新讀取。

當寫入極少、讀取很多時最有利。在大多數情況下 validate 會回傳 true，讀取幾乎是免費的。

「多讀少寫」的情境

• 資料很少變動，但被頻繁讀取（例如快取、座標、中繼資料）。
• 希望將讀取延遲降到最低。
• 若期間發生寫入，也能接受「重讀」。

回退到 read lock

若樂觀讀取失敗（validate 回傳 false），執行緒會「回退」到一般的 readLock。這可保證資料正確性，但通常很少發生。

3. StampedLock 的陷阱與注意事項

不支援重入

不同於 ReentrantReadWriteLock，StampedLock 不支援重入。若執行緒已持有鎖並再次嘗試取得——會導致 deadlock。

long stamp1 = lock.writeLock();
long stamp2 = lock.writeLock(); // DEADLOCK! 執行緒在等自己

對中斷的敏感度

StampedLock 對執行緒中斷的反應與傳統鎖並不相同。若執行緒在等待鎖時被中斷，它不一定會立刻「醒來」。對需要快速響應中斷的任務，請使用其他機制。

正確釋放印章

每次呼叫 readLock()、writeLock() 或 tryOptimisticRead() 都會回傳唯一的印章（long）。它必須被傳給對應的 unlock 方法：

• unlockRead(stamp)
• unlockWrite(stamp)

錯誤： 若把印章搞混或忘了呼叫 unlock，就會造成鎖洩漏並讓程式卡死。

4. 與 ReentrantReadWriteLock 的比較

公平模式與對 starvation 的影響

• 在 ReentrantReadWriteLock 中可以啟用「公平」模式（fair），使執行緒依隊列順序被服務。這能避免飢餓（starvation）。
• 在 StampedLock 中沒有公平性：若其他執行緒不斷「搶走」鎖，某些執行緒可能會等待更久。偶爾會發生飢餓。

5. 計數器: LongAdder/LongAccumulator vs AtomicLong

AtomicLong 在高競爭下的問題

AtomicLong 是提供執行緒安全遞增的原子變數。但當大量執行緒同時呼叫 incrementAndGet() 時，大家都在「爭奪」同一個變數，導致效能下滑。

LongAdder：分條（striped）計數器

LongAdder 以不同方式解決：它將計數器切成多個「分條」（stripes），每條服務一組執行緒。執行緒會增加其中一條，而最終值則是所有分條的總和。

優點：

• 在高競爭下，各執行緒幾乎不互相干擾。
• 效能遠高於 AtomicLong。

import java.util.concurrent.atomic.LongAdder;

LongAdder adder = new LongAdder();

Runnable task = () -> {
    for (int i = 0; i < 100_000; i++) {
        adder.increment();
    }
};

Thread[] threads = new Thread[8];
for (int i = 0; i < threads.length; i++) {
    threads[i] = new Thread(task);
    threads[i].start();
}
for (Thread t : threads) t.join();

System.out.println("最終值: " + adder.sum());

LongAccumulator

LongAccumulator 是 LongAdder 的泛化版本，可自訂聚合函式（例如最大值、最小值等）。

import java.util.concurrent.atomic.LongAccumulator;

LongAccumulator max = new LongAccumulator(Long::max, Long.MIN_VALUE);

max.accumulate(10);
max.accumulate(42);
max.accumulate(7);

System.out.println("最大值: " + max.get()); // 42

分條（striped）鎖與降低競爭

striped locks 的技術會將共享資源拆成多個彼此獨立的部分（stripes），每個部分由自己的鎖或變數保護。執行緒會平均分配到各分條，從而降低競爭並提升效能。LongAdder 與 LongAccumulator 正是採用這種做法。

6. 實作：讀多寫少的快取

目標： 我們有一個地圖（Map）與資料以及中繼資料（例如存取計數）。讀取很頻繁，寫入很少。

以 StampedLock 實作：

import java.util.*;
import java.util.concurrent.locks.StampedLock;
import java.util.concurrent.atomic.LongAdder;

public class MetadataCache<K, V> {
    private final Map<K, V> map = new HashMap<>();
    private final StampedLock lock = new StampedLock();
    private final LongAdder hits = new LongAdder();

    public V get(K key) {
        long stamp = lock.tryOptimisticRead();
        V value = map.get(key);
        if (!lock.validate(stamp)) {
            stamp = lock.readLock();
            try {
                value = map.get(key);
            } finally {
                lock.unlockRead(stamp);
            }
        }
        if (value != null) hits.increment();
        return value;
    }

    public void put(K key, V value) {
        long stamp = lock.writeLock();
        try {
            map.put(key, value);
        } finally {
            lock.unlockWrite(stamp);
        }
    }

    public long getHits() {
        return hits.sum();
    }
}

• 讀取使用樂觀模式：若無人寫入——讀取幾乎是免費的。
• 寫入使用 write lock。
• 存取次數的計數使用 LongAdder：即使在高競爭下，遞增也不互相干擾。

7. 在負載下比較 LongAdder 與 AtomicLong

測試: 8 個執行緒，各自進行 1,000,000 次遞增

import java.util.concurrent.atomic.AtomicLong;
import java.util.concurrent.atomic.LongAdder;

public class CounterBenchmark {
    public static void main(String[] args) throws InterruptedException {
        int threads = 8;
        int increments = 1_000_000;

        // AtomicLong
        AtomicLong atomic = new AtomicLong();
        long start = System.nanoTime();
        Thread[] t1 = new Thread[threads];
        for (int i = 0; i < threads; i++) {
            t1[i] = new Thread(() -> {
                for (int j = 0; j < increments; j++) atomic.incrementAndGet();
            });
            t1[i].start();
        }
        for (Thread t : t1) t.join();
        long timeAtomic = System.nanoTime() - start;

        // LongAdder
        LongAdder adder = new LongAdder();
        start = System.nanoTime();
        Thread[] t2 = new Thread[threads];
        for (int i = 0; i < threads; i++) {
            t2[i] = new Thread(() -> {
                for (int j = 0; j < increments; j++) adder.increment();
            });
            t2[i].start();
        }
        for (Thread t : t2) t.join();
        long timeAdder = System.nanoTime() - start;

        System.out.printf("AtomicLong: %d ms, LongAdder: %d ms%n", timeAtomic / 1_000_000, timeAdder / 1_000_000);
    }
}

典型結果:

AtomicLong: 2500 ms, LongAdder: 200 ms

結論: 在高競爭情況下，LongAdder 的速度遠勝 AtomicLong。

8. 使用 StampedLock 與 LongAdder 的常見錯誤

錯誤一：忘記呼叫 unlockRead/unlockWrite。 若不釋放印章，其他執行緒將無限期等待。務必搭配 try/finally！

錯誤二：嘗試重入。 StampedLock 不支援重入。不要在同一執行緒內取得同一把鎖兩次。

錯誤三：錯誤使用 validate。 若在 tryOptimisticRead 之後不檢查 validate，可能得到不一致的資料。

錯誤四：在高競爭下仍使用 AtomicLong。 AtomicLong 適合 1–2 個執行緒，但在 8+ 個執行緒時會成為「瓶頸」。請改用 LongAdder。

錯誤五：忽略分條鎖。 若你自行實作 striped-lock，務必確保執行緒能均勻分配到各分條，否則有些分條會過載，其他分條則閒置。

錯誤六：期待 StampedLock 具備公平性。 StampedLock 不保證執行緒的服務順序。少數情況下可能出現飢餓。