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）というトークンを返し、それを明示的に解放します.

主な特徴:

• 3 つのモード: write lock（排他的書き込み）、read lock（共有読み取り）、optimistic read（ロックしない楽観的読み取り）。
• 再入不可（no 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 は再入をサポートしません。スレッドがすでにロックを保持している状態で再度取得しようとすると—デッドロックになります。

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）を有効にでき、スレッドはキュー順に処理されます。これはスターベーション（飢餓）を防ぎます。
• StampedLock にはフェアネスがありません。他のスレッドが常にロックを「横取り」する状況では待ち時間が長くなることがあり、まれにスターベーションが起こり得ます。

5. カウンタ: LongAdder/LongAccumulator vs AtomicLong

競合が高い場合の AtomicLong の問題

AtomicLong は、スレッドセーフなインクリメントを提供するアトミック変数です。しかし多数のスレッドが同時に incrementAndGet() を呼ぶと、単一の変数を巡って争うことになり、性能低下を招きます。

LongAdder: ストライプ（striped）なカウンタ

LongAdder は別の方法で問題を解決します。カウンタを複数の「ストライプ」（stripe）に分割し、それぞれがスレッド群を担当します。各スレッドはどれか一つのストライプを増加させ、最終値は全ストライプの合計です。

利点:

• 高い競合時でもスレッド同士の干渉がほとんどない。
• 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 の手法は、共有資源を複数の独立した部分（stripe）に分割し、それぞれを別々のロックや変数で保護します。スレッドをストライプに均等に分散させることで競合を減らし、性能を高めます。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 vs AtomicLong の計測

テスト: 8 スレッド × 100 万インクリメント

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 を使う際の典型的なミス

ミス1: unlockRead/unlockWrite の呼び出し忘れ。 スタンプを解放しないと、他のスレッドは永遠に待たされます。常に try/finally を使いましょう！

ミス2: 再入を試みる。 StampedLock は再入をサポートしません。同一スレッドから二重にロックを取得しないでください。

ミス3: validate の誤用。 tryOptimisticRead の後に validate を確認しないと、一貫性のないデータを得る可能性があります。

ミス4: 高い競合時に AtomicLong を使う。 AtomicLong は 1～2 スレッドでは有効ですが、8 以上になると「ボトルネック」になります。LongAdder を使いましょう。

ミス5: ストライプロックを忘れる。 独自の striped-lock を実装するなら、スレッドがストライプに均等に分散されることを確認してください。そうしないと、一部のストライプが過負荷になり、他は遊んでしまいます。

ミス6: StampedLock にフェアネスを期待する。 StampedLock はスレッドの処理順序を保証しません。まれにスターベーションが起こり得ます。