2025/03/18 21:56 Locks, leases, fencing tokens, FizzBee
ロボ子、新しい形式仕様記述言語FizzBeeって知ってるか？作者はJayaprabhakarさんって人で、StarlarkっていうPythonのサブセットをベースにしてるらしいのじゃ。
初めて聞きました。形式仕様記述言語というと、システムの動作を数学的に記述するものですよね。それがPythonベースというのは面白いですね。
そうそう！で、このFizzBeeがRedlockアルゴリズムの正当性に関する議論で、Kleppmannさんが指摘した問題をモデル化するのに使えるか試した人がいるみたいじゃ。
Redlockですか。分散ロックのアルゴリズムですね。確か、複数のRedisインスタンスを使ってフォールトトレランスを高めるものでしたっけ。
さすがロボ子、よく知ってるのじゃ！そのRedlockのクリティカルセクションをモデル化するのに、FizzBeeではラベルがないから、"in_cs"っていう変数を作ってプロセスがクリティカルセクションにいるかどうかを表現したらしいぞ。
なるほど、変数を定義して状態を表現するんですね。ラベルがないのは少し不便かもしれませんね。
ロックのモデル化では、ロックをセットとして扱って、ロックを取得することをプロセスのIDをセットに追加することとして表現したみたいじゃ。FizzBeeの各ステートメントはデフォルトでアトミックに扱われるらしい。
セットでロックを表現するのは直感的ですね。アトミックな操作がデフォルトというのは、扱いやすそうです。
でも、それだとデッドロックが発生するらしいぞ。FizzBeeのモデルチェッカーは、デッドロックのチェックと、スレッドが任意のステートメントの後にクラッシュする可能性があることをデフォルトで想定するから、すぐに見つかるのじゃ。
デッドロックのチェックがデフォルトで有効なのは便利ですね。フォールトトレラントなロックソリューションを構築するには、プロセスの失敗も考慮する必要がありますね。
そこでリースじゃ！Redlockアルゴリズムは、一定期間後に期限切れになるリースという概念を使うのじゃ。時間をモデル化するために、モデルはすべてのプロセスがアクセスできるグローバルクロックを想定するらしい。
グローバルクロックですか。分散システムで正確な時間を扱うのは難しいですが、モデル化のためには必要ですね。
ロックに有効期限を設定したら、デッドロックの問題はなくなったけど、不変条件は常に真ではなくなったらしいぞ。当然じゃな。
有効期限切れによって、ロックが意図せず解放される可能性があるからですね。
Kleppmannさんは、Redlockがプロセスの実行が一時停止する問題（例えばガベージコレクション）に対して脆弱だって指摘してるのじゃ。だから、期限切れのロックで共有リソースにアクセスするのを防ぐために、フェンシングトークンを使うことを提案したのじゃ。
フェンシングトークンは、リソースへのアクセス順序を保証するためのものですね。でも、2つのプロセスが両方ともロックを保持していると信じている場合は、低いトークンが高いトークンよりも先に共有リソースに到達するシナリオからは保護されないんですね。
そういうことじゃ！FizzBeeを使った感想としては、驚くほど簡単に始めることができたらしいぞ。PlusCalの経験が役に立ったみたいじゃな。Pythonicな構文は、PlusCalやTLA+よりもプログラマーにとって馴染みやすいらしい。
PlusCalをご存知なんですね。TLA+もそうですが、形式手法は学ぶのが難しいイメージがあります。Pythonicな構文なら、もっと気軽に試せそうですね。
TLA+スタイルのモデルで考える方法を学ぶ必要はあるみたいじゃな。スレッドが任意の時点でクラッシュする可能性があるというFizzBeeのデフォルトの動作に少し混乱したけど、これは構成可能で、ロックモデルでデッドロックを示すのに役立ったらしいぞ。
デフォルトの動作に助けられたんですね。アルゴリズムを明示的にモデル化する価値を再認識した、と。
そうじゃな！しかし、FizzBeeでモデル検査をするとは、まるでアリの観察キットでゴジラを飼うようなものじゃな。スケールが違うのじゃ！
はかせ、それ、ちょっと意味が違います！
⚠️この記事は生成AIによるコンテンツを含み、ハルシネーションの可能性があります。
