キャッシュコヒーレンス

我々のサーバには HTTP リクエストを捌く 32 コアがある。各コアは私的な L1（約 32 KB）と私的な L2（約 1 MB）を持ち、共有されるのは L3 と DRAM だけだ。

ロードは 1 バイトではなく、そのバイトが載る 64 バイトのラインごと引き上げる。アドレスをドラッグして、名指ししたバイトがついてきた 63 バイトごと届くのを見てほしい：

注目してほしい。どのバイトを名指ししても答えは変わらない。8 バイト目でも63 バイト目でも、届くのは同じ 64 バイトだ。以下のどの規則も単位はバイトではなくラインであり、変数を 1 つも共有しない 2 スレッドに 05 節が請求できるのもそのためである。

再生を押して、DRAM にある唯一のコピーが 4 つに増えるのを見てほしい。各コアが順に x を読み、自分だけのラインを 1 本ずつ埋めていく：

注意してほしい。まだ 1 回も書いていないし、何も壊れていない。それでもマシンは同じ変数の版を 4 つ抱えている —— うち 3 つは他のコアから覗けない私的キャッシュの中だ。コヒーレンスとはこの 4 つを一致させ続ける規則のことで、このページの残りはその規則の代価の話である。

規則を外すと故障はすぐに現れる。コア 1 が自分のコピーを持ったまま、コア 0 に読みと書きを 1 回ずつ実行させる。次にプロトコルを入れて、無効化が届く様子を見てほしい：

見てのとおり、プロトコルがなければコア 1 は 5 を読む —— 1 回分の書き込みに遅れており、そのことを教えてくれるものはどこにもない。MESI があれば、コア 0 の書き込みがまずラインをコア 1 から取り上げるので、コア 1 の次の読みはミスして 6 を取り直す。契約はこれだけだ：もう成り立たない値を返す読みは、ソフトウェアが防ぐべきものではない。

コヒーレンスはアドレスごとに述べられ、言うことは 2 つだけだ。x への書き込みはいずれ全コアに見えること、そしてx への書き込み順序は全コアで同一であること。コア 0 の 4 回の書き込みをコア 1 の 4 回にドラッグで通し、その唯一の順序が並び替わるのを見てほしい：

境界をどこで離しても、下段の行はつねに 1 本きりで、どのコアも同じその行を読む。コヒーレンスが禁じているのは、コア 1 が a3 を b1 より先に見て、コア 2 が b1 を先に見ることだ。順序は選べない。保証されるのはひとつの順序であることだけである。

この保証が覆うのは 1 アドレスだけで、2 アドレスについては何も言っていない。スライダーを上げてflag のストアにdata のストアを追い越させ ——2 ステップ早くにしてみて —— 消費側が何を印字するか読んでほしい：

個々のアドレスは完璧なのに、消費側が 0 を印字する。data は 42、flag は true、どちらも古い値は読まれていない。このページはこの区別の上に立つ。コヒーレンスはアドレス単位で自動、コンシステンシは異なるアドレスへの書き込みが見える順序の話であり、volatile や std::atomic のメモリ順序、mfence が設定しているのはそちらだ。03 節で買う。

どの私的キャッシュのどのラインも 2 ビットの状態を持つ。プロトコルとは、自コアが、そして他のコアが読み・書き・追い出しをしたときに、その 2 ビットがどう動くかの規則だ。

スライダーで 4 つの状態を歩き、それぞれが次に何を許すかを読んでほしい。M と E が黙って書ける 2 つ、I は何も持たない状態だ：

M と Eが共有し、S が持たない性質に注目してほしい。他のコアが 1 つもコピーを持たないときに限って、コアは誰にも告げずに書ける。これが不変条件であり、表明として書き下す価値がある ——任意の瞬間において、あるラインを書き込み可能な形で保持するコアは高々 1 つであり、そのとき他のコアはコピーを 1 つも持たない。単一書き手か、多数読み手か、その両方はない。

再生を押し、3 コアが引き起こしうるすべての遷移を 1 本のラインで辿ってほしい。各ステップがインターコネクトに載せるメッセージは、下の線の上に描かれている：

注目してほしい。9 つの状態のうち 7 つはバスメッセージによって到達している。ただ 1 つ無料だった書き込みはステップ 3 で、そのときラインはすでに排他だった —— E が「他に誰も持っていない」ことをすでに証明していたので、M への昇格に許可はいらない。 E が存在する理由はまさにこれで、私的ラインへの 2 回目のアクセスを無料にするためだ。

共有ラインへの書き込みは無料ではなく、値段は「先に壊さねばならないコピーの数」に等しい。共有者の数を上げて —— 8 つを試して —— 消えていくコピーを数えてほしい：

共有者が 8 つなら、1 回の書き込みは7 回の無効化と 7 回の確認応答を、ストアが適用される前に支払う。だから読み中心で毎秒 1 回書かれる変数は問題なく、同じ変数が毎秒 100 万回書かれるとスケーラビリティの壁になる。代価は書き込みごとで、しかも観客の数とともに増える。

そのメッセージの届け方が、ラップトップとサーバを分ける。コア数を 32 まで引き、スヌープのブロードキャストとディレクトリを比べてほしい：

見てのとおり、ディレクトリの線は水平のまま、ブロードキャストの線が登っていく。スヌープは全コアに尋ね全コアが答える —— ラインを持っているかに関わらず 2(n−1) 通だ。ディレクトリは誰が実際に共有しているかを知っており、 2 + 2s しか払わない。共有者が 2 つなら 5 コア以上でディレクトリが厳密に安く、 32 コアのソケットがブロードキャストしない理由はそこにある。

4 つの状態では「共有かつダーティ」を表せない。だからコア 0 が書いたラインに 2 人目の読み手が付いた瞬間、 MESI はそれを書き戻すしかない。プロトコルを切り替えてその書き戻しを 1 歩ずつ進め、その次に読みに来るコアに誰が答えるかを見てほしい：

素の MESI の DRAM に注目してほしい。ダーティなラインはメモリへ戻され、 2 つのキャッシュはクリーンで持つ。クリーンなラインには指定の転送者がいないので、コア 1 の読みも DRAM が供給する。 Intel の MESIF は共有者から 1 つを応答者に選ぶ（F、forward）ので、2 回目は外に出ない。 AMD の MOESI では Owner がダーティなまま答え、書き戻し自体が起きない。

コアと L1 のあいだにはストアバッファがある —— Skylake で 56 エントリ、Ice Lake で 72。ストアはそこへ退役してコアは先へ進み、獲得と適用はあとだ。ストアフォワーディングで、書き手だけは最新値を読める。

バッファに残っているストアを増やし ——56 全部まで押し上げて —— 2 つの読み値が離れていくのを見てほしい：

注意してほしい。このコアは 100 を読み、他のすべてのコアはまだ 44 を読む。ここに非コヒーレントなものは何もない。キャッシュ階層から見れば、それらのストアはまだ起きていないのだ。順序どおり、いまから約 15.6 ns 後に起きる —— だが全員が合意している値は、書き手が見ている値に遅れる。

この遅れは外から観測できる。2 コアがそれぞれストアしてからロードする。「1 度に 1 ストア」から本物のバッファへ切り替え、最後までスクラブしてほしい：

なぜなら、ストアが 1 つずつ落ちるなら、どちらかのロードより先に必ず片方が落ちるので、r1 = r2 = 0 は到達不能 —— 結果は 3 通りだ。各コアにバッファを与えると、2 つのストアが飛行中のまま 2 つのロードが実行できてしまう：4 通り。これが x86 の TSO が許す唯一の並べ替えであり、mfence が存在する理由のすべてでもある。

4 つ目の結果を取り除くバリアは 1 命令ではない —— 1 命令に、コアが先送りを許されていたすべてが上乗せされる。バリアはすでに入っている —— その下でバッファを詰め直し、それから外してみてほしい：

命令そのものは約 8.3 ns。満杯のバッファの排出でさらに 15.6 ns、合わせて 23.9 ns —— 約 86 サイクルが、ソース上ではたった 1 行だ。毎秒 100 万回まわるループに 1 つ置けば、誰も名指しで頼んでいない順序付けにコアの 2.4% を使ったことになる。

x86 で気にすべき並べ替えは 1 つ、他のアーキテクチャでは 4 つある。アーキテクチャを切り替えて対を順に見てほしい ——プログラムが順序外に観測できる対と、無料でプログラム順に保たれる対だ：

x86-64 が許すのは store→load だけで5 対のうち 4 対は無料だから、そこで「正しい」コードが ARM64 では誤りになる —— ARM64 は IRIW 以外すべて並べ替え可能で、acquire/release は命令に書き込まれている（ldar と stlr）。ロックフリー構造の移植は再コンパイルではなく再導出だ。

あるコアが他のコアの持つラインに書くとき、ラインは旅をする —— 無効化が出ていき、確認応答が返り、データそのものが動く。 1 本のラインでピンポンして測ると、その往復は同一ソケット内で最良約 30 ns、典型で約 70 ns だ。

スライダーで梯子を下り、ソケットをまたぐバウンスがこのコアに留まるものすべてを置き去りにする様子を見てほしい：

注目してほしい。L1 内の素のインクリメントは 0.28 ns —— 3.6 GHz の 1 サイクルで、このページのナノ秒はすべてこのクロックで換算している。自コアがすでに持つラインへの非競合アトミックは 5.6 ns —— 20 サイクルで、競合がまったくないときの std::atomic の値段だから暗記する価値がある。典型的なバウンスは 70 ns、素のインクリメントの 252 倍だ。

この数字は税ではなく天井である。バウンス曲線に沿ってハンドルをドラッグし、競合する 1 本のラインが毎秒どれだけの書き込みを支えられるか読んでほしい：

なぜなら、バウンスが 70 ns なら、1 本のラインが吸収できるのは毎秒1430 万回 —— そしてこの値はコアを増やしても動かない。 32 スレッドが 1 つのカウンタを叩いても 32 倍のスループットにはならず、同じ 1430 万回を 32 分割するだけだ。

下の水平な線がまさにそれである。スレッド数を16 まで上げ、共有カウンタ 1 つとスレッドごとに 1 つが離れていく様子を見てほしい：

注目してほしい。共有側はスケールしなくなるだけでなく、下がる。1 スレッドなら毎秒 1.8 億回 —— ラインがキャッシュを離れないからだ。 2 スレッドは合わせて 1430 万回、16 スレッドでも同じ 1430 万回。スレッドごと版は 29 億回に達し、差は 202 倍になる。

「アトミックにすればいい」ではこれは直らず、アーキテクチャによってはむしろ悪化する。命令を切り替え、競合者の数を上げてほしい：

x86 の lock cmpxchg は read-modify-write のあいだラインを離さないので、試行は必ず 1 回で成功する。ARM の ldxr/stxr は途中でラインを手放すため、奪われると store-exclusive が失敗する。8 スレッドが競えば 1 つが勝ち7 つが再試行し、1 回のインクリメントに 560 ns かかる。アトミックは競合を消さず、払うあいだ結果を正しく保つだけだ。

コヒーレンスは変数ではなくラインに働く。ソースのどの行も同時に触れていない 2 つのカウンタでも、同じ 64 バイトに載れば互いにバウンスする —— しかもプログラムは終始正しい。コードを読んで見つけられる人はいない。

2 つ目のカウンタを割り当ての上でドラッグし、1 つ目のラインから出る瞬間を見てほしい：

見てのとおり、バイト 8 では 2 つのカウンタがline 0 を共有し、この 2 つは毎秒 1430 万回のインクリメントで動く —— バウンス速度そのもので、1 個の変数だった場合とまったく同じだ。バイト 64 では別々のラインに載り、毎秒 3.6 億回になる。この 2 状態のあいだでソースは 1 文字も変わっていない。

2 つ目の状態を買う手段がパディングであり、その量は好みの問題ではない。パディングをゼロから上げて境目を探してほしい ——56 バイトにある：

なぜなら、カウンタが 8 バイト幅なので、 2 つ目を自分だけのラインへ押し出す最小のパディングが 56 になる。48 では何も買えない。これは坂ではなく崖だ。あと少しで別のラインという部分点はない —— 56 バイト離れた 2 つのカウンタは 8 バイト離れたものと同じ性能になる。どちらも line 0 の内側にいて、どちらもバウンスするからだ。

構造体が大きくなっても差は縮まらない。パディングのない構造体にスレッドを足し、共有されたラインがびくともしない様子を見てほしい：

16 スレッドが 1 ラインなら合わせて 1430 万回のまま、 16 スレッドが16 ラインなら 29 億回。パディング版はメモリを 1 KB 余分に使い —— 2 ラインではなく 16 ライン —— 202 倍を買う。この取引に見合う変更は他にない。

うっかりこれを買ってしまう最も多い経路が配列だ。要素サイズを決め、 line 0 の中から始まる要素がいくつあるか数えてほしい：

1 要素 16 バイトなら4 つが line 0 を共有する。各 worker が自分のフィールドだけを増やす vector<Worker> は、共有変数が 1 つもないまま 4 スレッドが 1 ラインに乗り、しかも静かに失敗する —— 答えは正しく、4 つ合わせて毎秒 1430 万回。 4 本の独立したラインなら 7.2 億回で、ハードウェアの 50 分の 1 だ。

「静か」はツールについての主張なので、正確に言っておきたい。レイアウトを切り替え、占有されたコアがまったく動かない一方で、HITM ロードが現れては消えるのを見てほしい：

1 行目が、CPU 時間プロファイルが役に立たない理由である。どちらでもスレッドはコア上で走り、命令を退役させている —— ただラインが別の場所にあるだけだ。名指しできるカウンタはHITM、他のコアが modified で持つラインから供給されたロードだ。Linux の perf c2c はこれを数え、該当のラインとフィールドのオフセットを出す。

その一般形がシャーディングで、Java の LongAdder も Linux の per-CPU カウンタもこれだ。16 スレッドが各自のラインにカウンタを持ち、読まれる数値へ定期的に畳む。効くかは 2 つ —— カウンタは何個か、どれくらいの頻度で畳むか。

カウンタを増やし、混んでいるものが空くのを見てほしい。16 個で、全スレッドが自分だけのラインを得る：

1 個なら 1430 万回。8 個なら 1.14 億回 —— よくはなるが、どのシャードにも書き手が 2 つ残るので、どのシャードもバウンスし続ける。誰も共有しなくなる 16 個に至って初めて曲線は 29 億回へ届く。利得は緩やかには来ない。最後の共有シャードが消えた瞬間にまとめて来る。

畳み込みにも天井があり、それは同じ天井だ。間隔を動かして、リデュースが共有の合計に求める量と1 本のラインが出せる量を比べてほしい —— 1000 回ごとが最初に収まる点だ：

公開される合計は 1 本のラインなので、吸収できるのは毎秒 1430 万回まで。毎回のインクリメントで畳むとそれに 29 億回を要求することになり、シャードは無意味になる。1000 回ごとなら 2.9 百万回で収まる —— 代わりに合計は 16,000 カウント遅れうる。メトリクスなら無料だが、クォータ判定ならバグである。

最後にもう 1 つ、コードを 1 行も触らずに以上をすべて台無しにできるものがある。2 つ目のスレッドをソケット境界の向こうへドラッグしてほしい：

2 つのスレッドが別ソケットに載った途端、バウンスは 70 ns から 250 ns になり、天井は 3.6 倍下がる —— それを説明する変更はプログラムのどこにもない。 1 ソケットで見事にスケールしたベンチマークが 2 ソケットで崩れる理由であり、スレッドのピン留めと NUMA を意識した確保がパディングと同じ会話に属する理由でもある。あるスレッドのために丁寧に用意したラインは、そのスレッドが置いた場所に留まっているあいだだけ安い。

このバグはソース上では見えないので、レビューはロジックではなくレイアウトについてのものになる。実務では 4 つの形がほぼすべてを覆い、最初の 2 つが本番に届いてしまう側だ。

4 つを順に見て、どれが 2 スレッドの書き込みを同じラインに入れているか読んでほしい —— テープは終始同じ 128 バイトだ：

隣り合った 2 つのアトミックカウンタも、リングバッファの head と tail も、教科書どおりのフォルスシェアリングだ ——異なるスレッド、同じライン。守る対象のデータの隣に置かれたフラグは安全で、どちらも同じスレッドが書くからである。パディングされた組が対処の姿であり、 4 つのうちメモリを消費するのはこれだけだ。

C++ ではその対処は属性 1 つ、バグは属性 1 つの欠落である：

struct Counters {          // ✗ one line
  std::atomic<uint64_t> a; //   bytes 0..7
  std::atomic<uint64_t> b; //   bytes 8..15
};

struct alignas(64) Padded {  // ✓ one each
  std::atomic<uint64_t> v;
};

コンパイラは型へのその約束を守る。sizeof は 64 になり、ストライドはライン 1 本ぶんになる。手書きの詰め物は何も約束しない。詰め物を 48 バイトのままにして、アロケータが返した先頭アドレスをドラッグしてほしい —— 16 で足りる：

同じ構造体が意見を変える。先頭 0 では 2 つのカウンタは 56 バイト離れてどちらも line 0 に載り、先頭 16 では境界があいだに落ちて別々になる。ソースは 1 文字も動いていない —— 答えはアドレスの下位 6 ビットにあるので、このバグはある実行で現れ次の実行では隠れる。一度捕まえたテストが二度目に捕まえることはない。

約束と呼べるのはライン 1 本ぶんの間隔だけで、そのラインの長さはソースからは見えない。詰め物を 05 節が買った 56 バイトに戻して、下のマシンを取り替えてほしい：

Apple Silicon の粒度は 128 バイトなので、x86-64 でちょうど足りる詰め物が 2 つを同じラインに戻し、同じバイナリがサーバで速くラップトップで遅い。詰め物を 120 バイトまで引けばまた離れる —— これが要点で、この量はソースではなくマシンの属性である。alignas(std::hardware_destructive_interference_size) だけが、推測せずコンパイラに尋ねる書き方だ。支える数字は 5 つ —— ラインは 64 バイト（Apple Silicon は 128、getconf LEVEL1_DCACHE_LINESIZE が教える）、非競合アトミック 20 サイクル、同一ソケットのバウンス約 70 ns、ソケット間約 250 ns、競合する 1 本の上限は毎秒1400 万回前後 —— コアを足しても変わらない。

危険信号

• 構造体内で隣接する 2 つ以上の std::atomic フィールドを、別々のスレッドが書いている。
• 同一のリングバッファ構造体にある生産者インデックスと消費者インデックスのあいだにパディングがない。
• sizeof(T) < 64 の vector<T> で、要素ごとに書き手が別々。
• 読み中心の構造のノードに熱いカウンタやバージョン欄が埋め込まれている —— 更新のたびにそのノードが全読者に対して無効化される。
• 詰め物の量がプラットフォームに問い合わせた値ではなくリテラルで書かれている —— alignas が縛るのは型であって確保ではなく、 C++17 のアライン付き operator new より前は vector<Padded> でさえそれを無視できた。