キャッシュ一貫性基礎

我々のサーバには受信 HTTP リクエストを処理する 32 コアがある。各コアは私的な L1(~32 KB)と L2(~1 MB)を持ち、L3 と DRAM だけが共有される。 2 つのコアが同時に接続プールの参照カウンタを触るとき、互いの古い値を見ないようにするのは何か —— そしてその「させない」が、なぜ 2 コア間で行える最も高い行為なのか? 5 セクションで答えを組み立てる:契約(coherence vs consistency、多くのエンジニアが混同する 1 点);MESI と対話的なステート走査;代価 —— バウンス、アトミック演算、メモリモデル;偽共有 とスループットクリフ demo;最後に クイックリファレンス、頻出 6 問とその回答骨子。

契約 —— coherence vs consistency

1 コアは簡単。2 コアになった瞬間、ソフトウェアは 2 つの異なる保証に分かれた問題に直面し、ほぼ全員がそれらを混同する。両者を切り分けることが、本 primer の中でまず先に固めておく価値のある 1 点。

1 コアの「メモリ」は単純:アドレス X に書き、X を読めば、書いた値が返る。マルチコアではこの約束を守るのが格段に難しくなる —— ハードウェアは 2 つの階層化された保証で答えるが、シニアを含むほぼ全エンジニアが両者を混同する。両者を分けることが、本 primer の中で最も深く理解する価値がある部分 —— そしてプロダクションで並行性バグが出たとき、真っ先に手に取る概念。

セットアップ。現代のサーバ CPU は 32 コア持ち得る。各コアは私的な L1(~32 KB)と L2(~1 MB)を持ち、L3(32–64 MB)と DRAM だけ共有。コア A がアドレス X を読むと、X を含むキャッシュラインが A の L1 にロードされる。数サイクル後コア B も X を読むと、B の L1 にもロードされる —— いま、同じ論理メモリ位置の物理コピーが 2 つ存在する。両者が X を書いたら、いずれの次の読みは何を返すべきか?

ハードウェアは 2 つの異なる保証で答える:

Coherence は単一アドレスの性質。口語的に: 「単一のメモリ位置は、全コアから見て、書き込みの単一 FIFO に見える」。形式的に:(1)X への全書き込みは最終的に全コアに見える; (2)全コアが X への書き込みを同じ順序で観測する。 Coherence は次節の MESI が強制するもの。これがなければx = 1; print(x) が同一コア上ですら誤動作し得る。
Consistency は跨アドレスの性質。異なる位置への書き込みがどの順序で観測されるかを支配する。典型はプロデューサ / コンシューマ:

// プロデューサ(コア A):    // コンシューマ(コア B):
data = 42;                    while (!flag) {}
flag = true;                  print(data);

Coherence はコア B が最終的に flag = true を見ることを保証する。 Coherence は B が data = 42 を flag = true の前、後、または交互で観測するかは何も言わない。それが consistency の問題 —— 弱メモリモデルハードウェア(ARM、POWER、RISC-V)では、明示的なフェンスなしにコア B が合法に 0 を print できる。

なぜ混同されるか。両者ともキャッシュ階層の性質で、両者ともハードウェアが強制する。違いは「何を保証するか」:coherence はほぼ無償で全面的 —— コード上で明示的に推論することはない。 Consistency こそが Java の volatile、C++ の std::atomic memory_order、 Rust の Ordering::Acquire/Release、アセンブリの mfence / dmb ish が実際に設定するもの。

要点。「キャッシュ一貫性(coherence)は単一アドレスの古い値を読まない保証。メモリ一貫性(consistency)は —— ハードウェアに気にしていると伝えない限り —— 異なるアドレス間の値の相対的な順序に依存できない、という保証。」次節で見るプロトコル(MESI)が coherence の機構; 言語標準のメモリ順序は consistency のつまみ。

教科書がぼかす 1 点。完全な coherence があっても、グローバルで瞬間的な「本当の」アドレス値は存在しない —— あるのは各コアがキャッシュしている値、バス上を流れている値、最終的に DRAM に落ち着く値だけ。プロトコルの仕事は観測可能な値の列が、ある単一のグローバル FIFO 順に整合的であることを保証すること。任意のピコ秒の物理状態は、この抽象が示唆するよりずっと乱雑であり、ソフトウェアは意図的にそれを見ることを禁じられている。

MESI —— 4 つの状態、1 つのプロトコル

あらゆるキャッシュ内のあらゆるキャッシュラインは 2 ビットのタグを纏う。プロトコル全体は、コアが読み、書き、互いを snoop するときに 4 タグ間をどう遷移するかの規則。

Coherence は MESI が実装する。プロトコル名は各キャッシュラインが取り得る 4 状態 ——Modified、Exclusive、Shared、Invalid —— の頭字。状態表全体は暗記できるほど小さい —— そして暗記する価値がある。プロダクションデバッグで出てくる coherence 関連の問いは、すべてここのどこかに住んでいるから。

状態   他に副本?      DRAM と一致?     このコアが…
─────────────────────────────────────────────────────────
  M    なし            不一致(DRAM 古) 自由に読み書き
  E    なし            一致             自由に読み書き
                                         (書くと M に静かに)
  S    あり(他コア)   一致             自由に読み;
                                         書きは先にブロードキャスト
  I    空または古い    —                次のアクセスは必ずミス

遷移は 2 種類のイベントで起こる。ローカルプロセッサイベント: PrRd(このコアが読む)、PrWr(このコアが書く);バス / snoop イベント(他コアから):BusRd(他者が読み中)、BusRdX(他者が独占を要求)、 BusUpgr(共有者が S→M に昇格したい)、BusWb(DRAM へライトバック)。各キャッシュは自分の仕事をしながらも常にバスを snoop しており、プロトコルの正しさはそれに依存する。

網羅的な状態遷移表はここに収まらないが、重要な規則は直感的:

初回アクセス(PrRd、ラインが I):BusRd を発行。誰も持っていなければ E で到着。他に少なくとも 1 つ持っていれば、両者とも S に。
Exclusive ラインへの書き(PrWr、ラインが E):静かに M へ。バストラフィックなし —— まだ誰も気にしていない。
Shared ラインへの書き(PrWr、ラインが S):BusUpgr(または BusRdX)を発行し、他の共有者を強制的に S→I へ。書き手は M。一般的な操作の中で最も高い。
外部コアが Modified ラインを読む(snoop BusRd、ラインが M):ダーティデータをライトバックし(DRAM 追従)、ラインを要求元に直接供給。両者 S。
外部コアが本コアにキャッシュされたラインを書く(snoop BusRdX / BusUpgr):I に降りる。

1 / 8

2 つの私的 L1 を一致させ続けるプロトコルを 1 ステップずつ歩く。最後の 2 遷移に注目: 既に M の状態での「静かな書き込み」はバストラフィックゼロだが、次に別コアが読んだ瞬間ライトバックが強制される。このパターンの繰り返しが真の共有(true sharing) のコスト —— 次節のテーマ。

Snoop バス vs ディレクトリ方式

上記は snoopy プロトコル:各キャッシュがあらゆるメモリトランザクションを聞き、反応するかを自ら決める。少コア数では機能する —— バスはどのみち全 coherence メッセージを運ぶ。 16 コアを超えるあたりから、「全キャッシュへブロードキャスト」が支配的コストになる。

多コア系(Intel Xeon、AMD EPYC、Apple M シリーズ、ARM Neoverse)は代わりにディレクトリベースのプロトコルを使う: 中央または分散したディレクトリが、各キャッシュラインを現在共有しているコアの集合を追跡。書き込みは共有者だけに送られ、ブロードキャストされない。論理的には同じ 4 状態、ネットワーク振る舞いは大きく違う。

MESIF(Intel)と MOESI(AMD)—— 実 CPU が走らせるもの

純粋な MESI には弱点がある:あるコアが、複数キャッシュで S のラインを読みたいとき、どの共有者が応えるか? タイブレーカなしでは全員が応える(無駄)か、要求が DRAM まで落ちる(遅)。現実の 2 つの拡張がそれぞれ異なる方法で解く:

MESIF(Intel Nehalem 以降、2008 頃)。Forward 状態を追加 —— 任意時点で、共有者のうち高々 1 つが受信した BusRd の応答者に指名される。S→S 遷移は変わらないが、応えるのは 1 キャッシュのみ。厳密には MESI セマンティクスの上の最適化。
MOESI(AMD K8 以降、2003 頃;ARMv8 でも多くの構成で採用)。Owned 状態を追加:あるコアがダーティラインを保持しつつ、 DRAM へライトバックせずに他コアと共有できる。修正データのキャッシュ間転送 —— より高速だが invariant がより厳しい。1 コアが激しく書き、多コアが読む場面で特に有効。

要点。「MESI は皆が学ぶ 4 状態 coherence プロトコル。実ハードは拡張を使う —— Intel は F(Forward)状態を加え、共有ラインの読みに対し 1 キャッシュのみが応えるようにする;AMD は O(Owned)状態を加え、1 コアがダーティラインを保持したまま他コアがそれを直接読めるようにする。同じ 4 状態直感、異なる速いパス。」

代価 —— バウンス、アトミック、メモリモデル

Coherence の正しさはハードウェアが保証する。それはまた、2 コアが互いに行える最も高い行為でもある。数字を知ること —— と、それを回避するパターンを知ること —— が、32 コアまでスケールするコードと 4 コアで頭打ちのコードの差。

バウンスの代価

あるラインの「書込権(M)」を 1 コアから別コアへ移すどの遷移も、snoop、 Invalidate ブロードキャスト(またはディレクトリ参照)、データ本体のキャッシュ間転送を含む。現代の x86 では同一ソケット内で 1 バウンスあたり実測 ~30–100 ns、ソケット間では 150–300 ns。これは「競合キャッシュラインへ何回/秒書けるか」の硬い上限を決める:

バウンス時間   競合ライン上の有効書込 ops/sec
─────────────────────────────────────────────────────────
  ~30 ns         ~33 M ops/sec   (同ソケット、最良)
  ~100 ns        ~10 M ops/sec   (同ソケット、典型)
  ~300 ns        ~ 3 M ops/sec   (ソケット跨ぎ NUMA)

対比:競合のない L1 書きは ~1 ns。競合のあるアトミックカウンタは、競合のないものより 2 桁遅い。これが「アトミック ops/sec スケーリングカーブ」—— 単一共有カウンタの ops/sec を書き手スレッド数の関数として描いたとき —— が、書き手数個を超えると平坦化、もしくは減少に転じる理由。

CAS、LOCK CMPXCHG、LDREX/STREX

アトミック操作は coherence の最重要ユーザ。C++ の compare_exchange_strong(Java の CAS、Rust の AtomicI64::compare_exchange)を考える。 x86 では LOCK CMPXCHG にコンパイルされる:LOCK 接頭辞はキャッシュに coherence プロトコル経由でラインを M に取得させ、 compare-and-swap をアトミックに実行(他コアは中間状態を観測できない)、解放する。非競合で ~10–25 サイクル(1 桁 ns);競合下はバウンスコストが支配し、通常 100 ns 以上。

ARM のやり方は異なる。LDREX(load-exclusive)がキャッシュラインを「監視中」にマーク;STREX(store-exclusive)は書き込みを試み、その間にラインが触られていなければアトミックに成功、触られていれば失敗。 CAS ループは STREX が成功するまで再試行する。機能は等価だが、競合下のコスト変動はさらに大きい —— 失敗した再試行はすべて無駄な仕事だから。

メモリ順序 —— coherence と別物、代価は連動

Coherence は単一アドレスの保証を与える(Section 01)。メモリ順序 ——std::memory_order_*、Java volatile、Rust Ordering::*で設定するもの —— は跨アドレスの可視性。一貫性のコストは底層 coherence プロトコルと密接だが、両者は別のつまみ。

x86 は TSO(Total Store Order)。ロードは他のロードと並べ替えられない; ストアは他のストアと並べ替えられない;ロードは時として古いストアより前に並べ替え可能だが、異なるアドレス間に限る(ストアバッファのトリック)。実務上、x86 では大半の C++ atomic 操作が通常の MOV にコンパイルされ、明示的フェンス不要。memory_order_seq_cst のストアだけがMFENCE(~20–30 サイクル)を追加で持つ。

ARM は弱順序。明示的バリアなしには、異なるアドレスへのロード / ストアは他コアから任意の順序で観測され得る。acquire ロードは LDAR、 release ストアは STLR、完全な seq_cst フェンスは DMB ISH(通常 20–80 サイクル)。これが「Intel では動くが ARM で壊れる」が最頻のクロスアーキ並行バグである理由。

競合下で勝つパターン

「1 つのアトミックカウンタ、N スレッド」の競合の直し方は、カウンタを共有しないこと。各スレッドに自分のカウンタを与え(自分のキャッシュラインに、Section 04 参照)、アトミックなしで局所増分し、定期的に各スレッドの local 値をグローバル合計に reduce する。 Linux の per-CPU カウンタはこの方式;Go の sync/atomic 統計配管はこの方式; Java の LongAdder もこの方式(JDK は競合の激しい AtomicLong の代替として明示的に推奨している)。

スループットが「何スレッドでも合計 ~10 M ops/sec」から「スレッドあたり ~300 M ops/sec、コア数に線形」へ変わる。代価は reduce 間で合計値がわずかに古いこと —— ほぼ常に許容できる。合計の読み出し頻度自体が元来低いから。

要点。「アトミック操作が遅いのは、命令自体が遅いからではない。競合下で coherence プロトコル経由でコア間直列化されるから遅い。競合のあるホットライン上のアトミックは 1 操作 ~100 ns;競合のないものは ~1–5 ns。だから問うべきは『これはアトミックか』ではなく、常に『これは競合しているか』だ。」

偽共有 —— 見えないバグ

2 スレッドが別々の変数を書く。同じキャッシュライン。~30 倍の減速 —— ソースコードからは見えず、単スレッドプロファイリングでも検出されず、プロダクションで「マルチスレッドコードが 4 コアでスケールしなくなった」物語の背後にいる、最頻の静かなキラー。

Coherence は キャッシュライン粒度 で動作する、バイト粒度ではない。現代の一般的な CPU(x86、ARM64、Apple Silicon、POWER、RISC-V)では、キャッシュラインは 64 バイト。だから 2 スレッドがそれぞれ自分のカウンタを保持しても —— ソース上は完全に独立、共有変数なし、ロックなし、アトミックなし —— にもかかわらず 2 つのカウンタ変数がたまたま同じ 64 バイトラインに乗ると、どちらのスレッドの書き込みも他方のキャッシュコピーを無効化する。ラインは延々とピンポンする。

これを 偽共有(false sharing) と呼ぶ —— 論理的な共有が一切存在しないから。スレッドたちは自分は独立だと思っている;物理ラインしか見ない coherence は両者を競合と扱う。競合のコストすべて、実際の共有はゼロ。

1 / 6

同じ仕事量、同じコード、同じハードウェア —— 変わるのは 2 つのスレッドローカルカウンタ間のバイト距離だけ。padding = 56(T1 が 64 バイト境界を跨ぐ値)での崖が、一貫性のスラッシングが止まる瞬間。 ops/sec の絶対値は説明用;~30 倍の比は実測再現可能。

64 バイト境界はコード上でどう見えるか

同僚に次の構造体を見せ、何が悪いか聞いてみる:

// よくある無声キラー配置
struct Counters {
    std::atomic<long> a;   // バイト  0..7  —— スレッド 0 が書く
    std::atomic<long> b;   // バイト  8..15 —— スレッド 1 が書く
};
Counters c;                // 1 構造体、2 フィールドが隣接

機能的には正しい。性能的には災害。直し方はアラインメント:

// アライン後 —— 各カウンタが独自ライン
struct Counters {
    alignas(64) std::atomic<long> a;
    alignas(64) std::atomic<long> b;
};
// C++17 以降、より移植性ある書き方:
struct Counters {
    alignas(std::hardware_destructive_interference_size) std::atomic<long> a;
    alignas(std::hardware_destructive_interference_size) std::atomic<long> b;
};

他言語での同じ発想:

Java: @Contended アノテーションを付ける(JDK 8 以降)。非 JDK クラスはデフォルトでオフ —— -XX:-RestrictContended フラグが必要。 JDK 内部の LongAdder、ConcurrentHashMap 等で使用。
Go: 組み込み属性はなし;各ホットフィールドの後に_pad [56]byte を手動追加、または構造体ラッパを使う。 Go ランタイム自身が per-P(per-processor)状態でこの手法を使う。
Rust: ラッパ型に #[repr(align(64))] を付ける、またはフィールドを crossbeam_utils::CachePadded でラップ。
C / カーネルコード: GCC/Clang の __attribute__((aligned(64))); Linux はまさにこのパターン用に ____cacheline_aligned マクロを公開。

実務で偽共有はどこに潜むか

以下のどれも、コンパイラは警告しない。単スレッドマイクロベンチでは検出されない。どれも実本番システムで噛んでいる:

スレッドローカルキューを vector<Queue> に格納。Queue が小さく数個が 64 バイトスロットに収まると、隣接キュー同士が coherence で衝突する。Queue をパディングするか、vector<PaddedQueue> を使う。
同じリングバッファ構造体内のプロデューサポインタとコンシューマポインタ。2 つの最もホットなフィールドで、別スレッドが書き、メモリ上は必然的に隣接。 Disruptor の性能名声の全部は、それぞれを独自キャッシュラインに置くことに依存する —— 並行データ構造のコードレビューで最も指摘されるパターン。
書き手スレッドと読み手スレッドが使うシーケンス番号とフラグフィールド。読み手はフラグをポーリングし続ける;書き手はシーケンス番号を増分し続ける。同じライン → 両方が止まる。
ホットデータ構造に埋め込まれた統計 / カウンタ。読み中心の hashmap のノード内に整数のヒット/ミスカウンタを置くと、カウンタ更新がそのノードを読もうとしていた全スレッドのキャッシュコピーを無効化する。

検出

Linux では perf c2c が専用ツール:対象変数別のキャッシュ間転送を報告する。出力にはアドレス、原因のソース行、最もバウンスしているライン名前が並ぶ。 macOS では Instruments のカウンタビューで同等のことができる。プロファイラなしの場合、典型的な臭いは「マルチスレッドのスループットが 2–4 スレッドを超えるとスケールしなくなり、 CPU は 100% で明確なロックも見えない」。

要点。「偽共有とは、2 スレッドが 2 つの異なる変数を書いていて、たまたまその 2 変数が同じ 64 バイトキャッシュラインに乗っている状態。 Coherence は「実は共有していない」を見抜けないので、ラインはピンポンし続ける。直し方:スレッド毎のホットフィールドを 64 バイト境界にアラインさせ、各自専用ラインを持たせる。 C++17 には hardware_destructive_interference_size、Java には@Contended、Linux には ____cacheline_aligned、その他では手動パディング。」

クイックリファレンス

冷たく説明できる価値のある 6 つの核心問題と、コードレビューで一目で見抜くべき 5 つの赤旗。まず質問を頭に刻み込む;回答骨子はその下に。

キャッシュ一貫性とメモリ一貫性の違いは?

Coherence は単一アドレスの保証:全キャッシュが最終的にあるアドレスへの書き込みを同じ順序で見るので、1 つの場所の古い値を読むことは決してない。 Consistency は跨アドレスの保証:異なるアドレスへの書き込みが他コアにどの順序で可視化されるかを規定する。Coherence はハードウェアが実装(MESI); consistency は volatile / std::atomic のメモリ順序 / フェンスでプログラマが設定する。

MESI を 90 秒で説明。

各コアの私的キャッシュ内の各キャッシュラインは 4 状態のいずれかを持つ:Modified(本コアが唯一の副本を持ち、書き込み済み;DRAM は古い)、Exclusive(本コアが唯一の副本を持ち、DRAM と一致)、Shared(複数コアが読取専用副本を持ち、全 DRAM 一致)、Invalid。ローカルの読み / 書きが本コアの遷移を駆動; snoop されたバスメッセージ(BusRd、BusRdX、BusUpgr、BusWb)が他コア起因の遷移を駆動。実 CPU は追加最適化として F(Intel)や O(AMD)を加えるが、意味的骨格は MESI。

ハードウェアレベルで CAS はどう動く?

x86 では LOCK CMPXCHG。LOCK 接頭辞は coherence プロトコル経由で対象キャッシュラインを M 状態に取得させ、compare-and-swap をアトミックに実行(他コアは中間状態を観測できない)、解放する。 ARM では load-linked / store-conditional のペア —— LDREX がラインを「監視中」にマーク、STREX が書き込み、その間にラインが触られていなければ成功。非競合で数 ns;競合下はバウンスコストが支配。

偽共有とは何か、どう直すか?

2 スレッドが 2 つの異なる変数を書き、その 2 変数が同じ 64 バイトキャッシュラインに乗っている状態。Coherence は「実は共有していない」を識別できないので、ラインがピンポンする。直し方:スレッド毎のホットフィールドを 64 バイトにアライン —— C++ で alignas(64)、 Java で @Contended、Linux で ____cacheline_aligned、 Rust で crossbeam の CachePadded、Go で手動 [56]byte パディング。

なぜ std::atomic<int>::fetch_add はしばしば int++ より遅いか?

通常の int++ はキャッシュにホットなローカル変数では単一 L1 アクセス、~1 ns。atomic::fetch_add は LOCK 接頭辞付き命令(x86)、または LL/SC ループ(ARM)にコンパイルされる;非競合下でもメモリへの完全な順序を強制し、ストアバッファをフラッシュし得る。競合下では coherence プロトコル経由でラインを M に取得するため、1 呼び出しあたり 30–100 ns のバウンス。命令自体が遅いのではない ——それがトリガする coherence の仕事が遅い。

共有 atomic ではなく per-thread カウンタ + reduce を選ぶ場面は?

書き込みが読み出しを大幅に上回り、競合が coherence のボトルネックになるほど高い場面。 Per-thread カウンタは増分時の coherence トラフィックがゼロ —— 各スレッドが自分のキャッシュラインを書く —— 定期的な reduce のみがコストを払う。スループットは「コア数によらず頭打ち」から「コア数に線形スケール」へ。 Java の LongAdder はまさにこの洞察を基にする;Linux per-CPU カウンタも同様。代価は reduce 間で集計が少し古いこと —— metrics / stats 用途ではほぼ常に許容できる。

コードレビューの赤旗

構造体内に隣接した 2 つ以上の std::atomic<T> フィールド。ほぼ確実に同じラインに落ちる。別スレッドが書くなら偽共有確定。
読み中心データ構造のノード内に埋め込まれたホットカウンタやバージョン番号。カウンタ更新ごとに、そのノードを読もうとしていた全スレッドのキャッシュ副本が無効化される。
vector<Worker> や vector<Queue>、ただし Worker / Queue が < 64 B。隣接要素が同じキャッシュラインに同居 —— 連続配置はキャッシュプリフェッチには良いが、 coherence には致命的。
同じリングバッファ構造体内のプロデューサ / コンシューマポインタ、パディングなし。並行データ構造のコードレビューで最も指摘されるパターン。それぞれ専用キャッシュラインが必須。
保護するデータの直隣に置かれた std::atomic<bool> フラグ。フラグの acquire ロードとデータのロードが同じラインに落ちる —— 単書多読ならよいが、書き手が複数になると両者が同じラインを理由なく争う。