並行性 — 順序を決めなければ結果も決まらない
一言でいうと
複数の実行の流れが同じデータに触れた瞬間、結果が実行順序に依存するようになります。その順序を強制する仕組みがロックで、ロックを誤って使うと、誰も先に進めない状態に陥ります。
なぜ必要なのか
counter = counter + 1という1行は、機械語では最低3段階です。読み、足し、書きます。2つのスレッドがこのコードを同時に実行すると、両方が同じ値を読んで同じ値を書くことが起こり、増加が1回分消えます。これが競合状態(race condition)です。
このバグの厄介な点は再現性です。ほとんどの実行では何も起きないのに、負荷が上がったりコア数が増えたりすると現れます。そのため、テストを通過して本番で爆発します。
どう動くのか
共有リソースに触れるコードの区間をクリティカルセクションといい、正しい解法は3つの条件を満たさなければなりません。
- 相互排除: 一度に1つだけがクリティカルセクションに入ります。
- 進行: 誰も中にいなければ、入ろうとする側のうち1つは必ず入ります。
- 有限待機: 入ろうとする側が無限に後回しにされません。
ソフトウェアだけでも作れますが(ピーターソンのアルゴリズム)、現代のCPUはアトミック命令を提供します。比較して値が同じなら置き換えるCAS(compare-and-swap)が代表的で、ほとんどすべてのロックとロックフリーのデータ構造が、この上に成り立っています。
同期ツールは性格が異なります。
- ミューテックス: 所有者がいます。ロックしたスレッドだけが解除できます。
- セマフォ: カウンターです。所有者の概念がないので、Aが取得してBが返却してもかまいません。リソースの個数を制限するときに向いています。
- 条件変数: 「ある条件が真になるまで待つ」を表現します。必ずミューテックスと組み合わせて使い、起きた後に条件をもう一度検査する必要があります(偽の起床があります)。
待機の方式も分かれます。スピンロックは、解除されるまでCPUを回しながら待ちます。クリティカルセクションがごく短く、コアに余裕があるときにだけ得をし、そうでなければCPUを燃やすだけです。ブロッキングロックはスレッドを眠らせて他の仕事をさせますが、コンテキストスイッチのコストがかかります。
デッドロックは、4つの条件が同時に成立したときにだけ起きます。相互排除、保持して待機、非プリエンプション、循環待機です。4つすべてが必要だということは、1つだけ崩せば防げるという意味でもあります。実務で最もよく使われる方法が、循環待機を崩すこと、つまりすべてのコードがロックを同じ順序で取得するようにするルールです。データベースでデッドロックが多いなら、トランザクションが行に触れる順序がばらばらでないかを、まず見ます。
優先度逆転も知っておく価値があります。優先度の低いスレッドがロックを握ったまま、中間の優先度のスレッドに押されて実行できないと、そのロックを待つ優先度の高いスレッドまで一緒にブロックされます。火星探査機パスファインダーの有名な再起動事故がこの問題で、解法は、ロックを握っているスレッドの優先度を一時的に引き上げる優先度継承です。
現場での姿
アプリケーションで「在庫を確認して、なければ差し引く」のように、読んで判断してから書くパターンは、ロックなしでは常に壊れます。ところがここで、よくある誤解が1つあります。データベースの分離レベルを上げれば解決するという思い込みです。2つのトランザクションが同じ集合を読み、別々の行を更新すると、書き込みの衝突がないので、スナップショット分離はこれを検知できません。この現象をライトスキュー(write skew)といい、直列化可能レベルや明示的なロック、あるいは制約条件でしか防げません。
ロックを減らす方向
ロックは正確ですが高価で、誤って使うとデッドロックを作ります。そのため実務の方向は、ロックをうまく使うことより、ロックが必要ないようにすることです。方法は、おおよそ3つです。
共有しません。各スレッドが自分の分のデータだけを触り、最後にまとめれば、ロックがまったく必要ありません。個数を数える作業なら、スレッドごとに別々に数えて、最後に足す方式です。まとめる段階でだけ1回同期すればよいので、競合がなくなります。
変更しません。値を書き換える代わりに新しい値を作り、参照だけを差し替えれば、読む側はロックなしで安全です。読み取りが圧倒的に多い設定や参照用の表によく合います。その代わり、更新のたびにコピーを作るので、頻繁に変わるデータには向きません。
メッセージで渡します。データを共有する代わりに所有権を1か所に置き、他の流れはリクエストを送って、そこに処理させます。この方式の価値は性能ではなく、そのデータがどこで変わるのかが1か所に集まることです。バグを探す場所が、コード全体ではなく1つの関数になります。
ロックを使うときのルールも、いくつか守れば大半の事故がなくなります。範囲を狭く取ってクリティカルセクションの中で入出力や別のロックを呼ばず、順序を決めて複数のロックを常に同じ順序で取り、ロックを握ったままコールバックを呼ばないようにします。最後のものは特に忘れられがちですが、他人のコードを呼んだ瞬間、その中でどんなロックを取るのかがわからず、順序のルールが崩れます。
最後に、競合状態はテストではなかなか見つかりません。ほとんどの実行で通過するからです。そのため、静的解析器や、実行時に競合を検知してくれるツールをCIに入れるほうがはるかに効果的で、負荷を上げて長く回すテストを別に用意するのも役立ちます。
次のラボですること
スレッド4つに同じ値を増やさせて、更新が消えるところを自分で作ります。同じプログラムを5回実行して、値が毎回違うことを確認したあと、ロックで防ぎ、そもそも共有しない方式でも防いでみます。最後には、ロックを逆の順序で取ってデッドロックを作り、順序を統一するだけでなくします。