「TLA+ の検査器」と言うとき、ふつうは TLC というモデル検査器を指します。TLC は、形式仕様記述言語 TLA+ で書いたシステムの設計を読み込むツールです。起こりうるすべての状態を総当たりで探索し、設計上のバグを自動で見つけます。
TLA+ は Leslie Lamport(2013 年のチューリング賞受賞者)が考案した言語で、AWS や Microsoft Azure などで、分散システムや並行処理の設計検証に使われてきました。数学的な手法でソフトウェアの正しさを確かめる形式手法の代表的な道具の 1 つです。
この記事では、TLC が何をしているのか、何を検証できるのか、どこに限界があるのかを、小さな例を使って整理します。
TLA+ と TLC の関係
最初に用語を分けておきます。
| 名前 | 役割 |
|---|---|
| TLA+ | 仕様を書くための言語。システムの状態(変数)と、状態がどう変わりうるか(アクション)を数学的に書く |
| TLC | TLA+ の仕様を読み込み、到達しうる状態を列挙して性質を検査するモデル検査器 |
| TLAPS | TLA+ Proof System。性質を数学的に証明するための対話的な証明系 |
TLC と TLAPS は、どちらも公式の tlaplus プロジェクトで提供されています。TLC は tla2tools.jar に含まれていて、TLA+ Toolbox(Eclipse ベースの IDE)や VS Code の拡張機能から呼び出せます。コマンドラインから直接実行することもできます(後述)。
なぜテストでは並行処理のバグを見つけにくいのか
単体テストや結合テストが確かめられるのは、人間が思いついた実行シナリオだけです。並行処理のバグは、複数の処理のステップが特定の順番で交互に実行されたとき(インターリーブ)にだけ起きることが多くあります。そうした順番をテストで思いつくのは困難です。運良く思いついても、実際にその順番で実行させるのはさらに困難です。
TLC は発想が逆です。順番を人間が選ぶのではなく、ありうる順番をすべて試します。
TLC の仕組み
TLC は次の流れで検査します。
- 初期状態の生成:仕様の
Initを満たす初期状態をすべて作る - 状態空間の探索:遷移ルール(
Nextアクション)を各状態に適用し、到達できる状態をすべて辿る。どのプロセスが次に動くかの組み合わせも、すべて別々の遷移として扱う - 反例トレースの出力:検査する性質が破れる状態を見つけると、初期状態からその状態に至る手順(トレース)を出力して止まる
探索は既定で幅優先です。そのため、安全性の違反について TLC が返す反例は、その違反に至る最短の手順になります(複数のワーカースレッドで探索した場合は、厳密に最短とは限りません)。人間がトレースを読んで原因を理解するうえで、これは大きな利点です。
なお、探索の方式は変えられます。-dfid で反復深化の深さ優先探索、-simulate でランダムな実行を繰り返すシミュレーションモードになります。最初の違反で止めずに探索を続けたいときは -continue を付けます。
小さな例:在庫 1 個を 2 人が同時に買う
「在庫があるか確認してから、在庫を 1 つ減らす」という処理を考えます。確認と減算が別々のステップになっていると、2 人の購入者が同時に「在庫あり」と判断し、両方が減らしてしまう可能性があります。
これを TLA+ で書くと次のようになります。Atomic が FALSE のときは確認(Check)と減算(Buy)が別のステップ、TRUE のときは 1 ステップ(CheckAndBuy)で行います。
---- MODULE Stock ----
EXTENDS Integers
CONSTANTS Buyers, InitStock, Atomic
VARIABLES stock, pc
vars == <<stock, pc>>
Init ==
/\ stock = InitStock
/\ pc = [b \in Buyers |-> "check"]
\* 非アトミック版: 在庫を確認する
Check(b) ==
/\ ~Atomic
/\ pc[b] = "check"
/\ pc' = [pc EXCEPT ![b] = IF stock > 0 THEN "buy" ELSE "done"]
/\ UNCHANGED stock
\* 非アトミック版: 確認した結果を信じて 1 つ減らす
Buy(b) ==
/\ pc[b] = "buy"
/\ stock' = stock - 1
/\ pc' = [pc EXCEPT ![b] = "done"]
\* アトミック版: 確認と減算を 1 ステップで行う
CheckAndBuy(b) ==
/\ Atomic
/\ pc[b] = "check"
/\ stock' = IF stock > 0 THEN stock - 1 ELSE stock
/\ pc' = [pc EXCEPT ![b] = "done"]
Done ==
/\ \A b \in Buyers : pc[b] = "done"
/\ UNCHANGED vars
Next ==
\/ \E b \in Buyers : Check(b) \/ Buy(b) \/ CheckAndBuy(b)
\/ Done
Spec == Init /\ [][Next]_vars /\ WF_vars(Next)
\* 安全性: 在庫はマイナスにならない
NonNegative == stock >= 0
\* 活性: いつかは全員の処理が終わる
AllFinish == <>(\A b \in Buyers : pc[b] = "done")
====
TLA+ では、変数の次の状態をプライム付き(stock')で書きます。各アクションは、割り込まれずに実行される 1 ステップを表します。Done は全員が終わったあとに何も変えないステップで、終了した状態をデッドロックと誤検出させないために置いています。
検査の条件は、別の設定ファイル(Stock.cfg)で与えます。購入者 2 人、在庫 1 個、非アトミック版という最小の構成です。
CONSTANTS
Buyers = {b1, b2}
InitStock = 1
Atomic = FALSE
SPECIFICATION Spec
INVARIANT NonNegative
PROPERTY AllFinish
b1 と b2 は、設定ファイルの中で「モデル値」として扱われる、互いに異なるだけの値です。
TLC を実行する
tla2tools.jar は tlaplus/tlaplus の GitHub Releases から入手できます。Stock.tla と Stock.cfg を置いたディレクトリで、次のように実行します。
java -cp tla2tools.jar tlc2.TLC -config Stock.cfg Stock.tla
TLC が辿る状態
この構成で到達できる状態は、購入者 2 人それぞれの段階(pc)と在庫数の組み合わせで、図の 10 個です。
TLC は、この図を初期状態から幅優先で辿りながら、各状態で NonNegative を確かめます。そして、赤い経路のような手順で不変条件が破れたところで、そのトレースを報告して止まります。
| 手順 | 起きること | stock |
|---|---|---|
| 1 | 初期状態 | 1 |
| 2 | b1 が在庫を確認する(在庫あり) | 1 |
| 3 | b2 が在庫を確認する(在庫あり) | 1 |
| 4 | b1 が 1 つ減らす | 0 |
| 5 | b2 も 1 つ減らす | -1 |
実際の出力では、b1 と b2 のどちらが先に動くかが入れ替わることがあります。それでも、トレースの長さ(初期状態から 4 ステップ)は同じです。
アトミックにすると
Atomic = TRUE にして確認と減算を 1 ステップにすると、この順番は存在しなくなります。CheckAndBuy は在庫が 1 以上のときだけ減らすので、初期在庫が 0 以上である限り、購入者や在庫を増やしても在庫はマイナスになりません。実装でこのアトミック性を確保する手段の 1 つが分散ロックです。
この例は単純なので、人間でも図を描けば気づけます。しかし、ノードが 3 台、メッセージの再送あり、障害からの復旧あり、となると、状態の数は手で追えない規模に急増します。そこを機械的に全部見るのが TLC の役目です。
TLC で検証できる性質:安全性と活性
TLC が検査する性質は、大きく 安全性 と 活性 の 2 種類に分かれます。
安全性(Safety):悪いことが絶対に起きない
- 不変条件(Invariant):どのタイミング、どの実行順でも常に満たすべき条件。設定ファイルの
INVARIANTに指定する- 例:在庫数がマイナスにならない
- 例:2 つのノードが同時にリーダーにならない
- 例:分散 DB のレプリカ間で、コミット済みのデータが食い違わない
- デッドロック:どのアクションも実行できず、システムがそれ以上進めなくなる状態。TLC は既定でデッドロックを検査する。終了状態を正常とみなしたい場合は、上の
Doneのように終了後のステップを書くか、-deadlockオプションで検査を外す
活性(Liveness):良いことがいつか必ず起きる
- 例:リクエストを送ったら、無限ループや飢餓状態に陥らず、いつかは必ずレスポンスが返る
- TLA+ では時相演算子で書く。
<>Pは「いつか P になる」、P ~> Qは「P になったら、いつか Q になる」 - 設定ファイルの
PROPERTYに指定する
活性を検査するときは、公平性の仮定が必要になります。何も仮定しなければ、「システムがずっと何もしない(足踏みし続ける)」実行も許されてしまい、「いつか終わる」は成り立ちません。上の例の WF_vars(Next) は弱公平性の仮定です。「実行可能なステップがずっと実行可能なままなら、いつかは実行される」という意味です。
安全性の違反は「ここで壊れた」という有限の手順で示せます。一方、活性の違反は「この先ずっと良いことが起きない」ことを示す必要があるため、TLC は同じ状態に戻ってくるループを含むトレースを反例として返します。
AWS・Azure での TLA+ 活用事例
2015 年、AWS のエンジニアが論文「How Amazon Web Services Uses Formal Methods」を Communications of the ACM に発表しました。S3 や DynamoDB などのシステムの設計に TLA+ を使った経験が報告されています。DynamoDB の設計では、TLC が見つけたバグを示す最短の反例トレースが 35 ステップに及びました。
このような、長い手順の果てに特定の順番が揃ったときだけ起きる競合状態(race condition)を、コードを書く前の設計段階で見つけられるのが TLC の強みです。
同様に Microsoft も、Azure Cosmos DB が提供する 5 つの一貫性レベルの仕様を TLA+ で書き、Azure/azure-cosmos-tla として公開しています。
TLC のメリットと限界
| 項目 | 内容 |
|---|---|
| 強み | 人間の直感では見落としがちな、長い手順の果てに起きるまれな競合状態を、実装前の設計段階で検出できる。違反は具体的な手順として返るので、原因を追える |
| 限界(状態爆発) | サーバー台数、バッファサイズ、メッセージ数などのパラメータが大きくなると、状態の数が組み合わせ的に増える(状態爆発)。検査ではモデルを有限かつ小さく抽象化する必要がある |
| 限界(モデルと実装の差) | TLC が検査するのは仕様(モデル)であって、実装のコードではない。仕様が正しくても、実装が仕様どおりとは限らない |
状態爆発への対策には、次のようなものがあります。
- 定数を小さく取る:経験的に、並行処理のバグの多くはノード 2〜3 台、メッセージ数件といった小さな構成で再現する
- 対称性で同一視する:交換しても意味が変わらない値(上の例の
b1とb2など)は、仕様側でPermutations(Buyers)(TLCモジュール)を返す演算子を定義し、その名前を設定ファイルのSYMMETRYに書くと、同一視して探索する状態を減らせる。ただし、活性(PROPERTY)の検査と組み合わせると違反を見逃すことがあるので、不変条件だけを検査する構成で使う - 並列化する:
-workersで複数スレッドを使って探索する
「違反なし」の結果を疑う
TLC が違反を報告しなかったとき、それは指定した有限のモデルの範囲では違反がない、という意味です。さらに、モデルの書き方を間違えて、そもそも肝心の状態に到達していない可能性もあります。たとえば上の例で Buy のガード条件を誤って書き、誰も買えないモデルになっていれば、在庫は決してマイナスにならず、検査は「成功」します。
これを防ぐには、破られるべき性質をあえて置き、TLC が違反を報告することを確かめます(例:stock = InitStock を不変条件にして、在庫が実際に減ることを確認する)。検査が空振りしていないかの確認は、末尾で紹介する関連記事でも扱っています。
TLAPS との使い分け
TLC は、有限のモデルを総当たりするモデル検査器です。パラメータを有限に絞った範囲でしか保証できません。
任意の台数、任意の長さの実行について性質が成り立つことを示したい場合は、TLC ではなく、対話的な定理証明系である TLAPS(TLA+ Proof System) を使います。TLAPS では人間が証明の構造を書き、各ステップをバックエンドの自動証明器に検査させます。手間はモデル検査よりはるかに大きいため、まず TLC で設計の穴を潰し、特に重要な性質だけを TLAPS で証明する、という順番が現実的です。
まとめ
- TLC は、TLA+ で書いた設計の、到達しうる全状態を探索するモデル検査器
- 既定の幅優先探索により、安全性の違反は最短の反例トレースとして返る
- 検査できるのは、安全性(不変条件、デッドロック)と活性(いつか必ず起きる)。活性には公平性の仮定が要る
- 長い手順の果てに起きる競合状態を、実装前に見つけられる。AWS では 35 ステップのバグを見つけた例がある
- 限界は状態爆発と、モデルと実装の差。モデルは小さく取り、「違反なし」は空振りでないことを確かめる
- 無限の範囲で保証したいなら TLAPS で証明する
TLA+ と TLC を Claude Code と組み合わせて、実際にキャッシュ設計の競合を見つけた例は、形式手法を Claude Code で回す — Z3 と TLA+ で仕様の穴を見つけ、反例をテストに落とす で紹介しています。
