# Why Order Matters: Turing Equivalence in Automated Systems Administration ## Abstract(和訳) well-architected な企業インフラのホストは自己管理(self-administered)されており、自身の保守・アップグレードを自ら実行する。定義上、自己管理ホストは自己修正コードを実行する。それらは単純な状態機械の規則に従って振る舞うのではなく、複雑なフィードバックループと進化的な再帰性を内包しうる。 この振る舞いが持つ含意は、企業・ミッションクリティカルなコンピューティングの信頼性・セキュリティ・所有コストに直接関わる。振り返れば、この懸念は手動管理されるマシンにも同様に当てはまる——管理者は対象ディスクのコンテキストで実行されるツールを使って同じディスクの内容を変更するからである。手動・自動いずれの管理手法の自己修正的振る舞いも、従来型に管理されたインフラで高可用性とセキュリティを維持することがなぜ困難かつ高コストなのかを説明する一助になる。 インフラアーキテクチャのツール設計という営みは、この自己言及的な混沌に秩序をもたらすために存在する。従来型のシステム管理は、規律・文化の醸成と、企業ニーズにより適合した実践の採用によって大きく改善しうる。低コストな保守戦略を作ることは依然として職人芸(art)にとどまっている。この職人芸を比較的経験の浅い管理者の手に渡すには何ができるか。我々は、その答えの一部が、計算の理論的性質に一部基づく、保守ツールのための実証済みの戦略の採用にあると考える。 本論文では、この振る舞いを理解するための理論的基盤を構築するため、自己管理ホストをチューリング機械になぞらえる。決定的順序付け(deterministic ordering)技法を用いて自己管理ホストを信頼性高く管理する仕組みを提供するいくつかのツールについて論じる。 我々の知見によれば、いかなる言語で書かれたツールであっても、各ホスト上の変更の決定的かつ再現可能な順序を維持しない限り、企業インフラを予測可能に管理することはできないようである。あらゆるツールの実行環境は常に対象オペレーティングシステムのコンテキストで実行されるため、変更はツール自体の振る舞いに影響を与えうる循環依存を生む。これらの変更の振る舞いは事前に予測することが難しい場合があるため、変更されたホストを検証するにはテストが必要になる。テストで変更が検証された後は、この同じ循環依存性ゆえに、テストされたのと同じ順序で本番環境に反映しなければならない。 複数ホストを管理する最も低コストな手法もまた、決定的順序付けであるように見える。他のあらゆる既知の管理手法は、より多くのテストか、管理対象ホストごとのより高いリスクのいずれかを伴うようである。 ## 論文情報 - 著者: Steve Traugott(TerraLuna, LLC)、Lance Brown(National Institute of Environmental Health Sciences) - 会議: USENIX LISA 2002(16th Systems Administration Conference)、Philadelphia, PA、2002-11-03〜08、pp. 99-120 - URL(HTML版): https://www.usenix.org/legacy/publications/library/proceedings/lisa02/tech/full_papers/traugott/traugott_html/index.html - PDF実URL: https://www.usenix.org/legacy/publications/library/proceedings/lisa02/tech/full_papers/traugott/traugott.pdf - 前作: [[@1998__LISA__Bootstrapping an Infrastructure]](Traugott & Huddleston, LISA XII, 1998)の後継論文で、同論文が導入したisconf(makeベースの状態エンジン)の理論的基礎付けを試みる。 ## 概要 本論文は理論(computability theory)寄りの立場論文(position paper)であり、実証実験は行わない。中心的な主張は次の3層からなる。 1. **計算機システム管理手法の3分類**(発散・収束・合同)を提示し、企業インフラの多くが実際には発散状態にあると指摘する。 2. Lance Brown が発案した比喩——**UNIXマシンをチューリング機械になぞらえる思考実験**——を、A.1〜A.60 の番号付き言明(assertion)として展開し、自己管理ホスト(ASAT: Automatic Systems Administration Tool が動くホスト)が実質的にネットワーク接続されたユニバーサルチューリング機械であることを示す。 3. この理論的等価性から、**決定的順序付け(deterministic ordering)による変更管理が最小コストの管理手法である**という実践的帰結を導く。 論文自体が「本論文は生きた文書であり、改訂と議論はInfrastructures.Orgで見られる」と明記し、査読論文というより実務者コミュニティ向けの理論的マニフェストの性格が強い。 ## 問題設定 自己管理ホスト(self-administered host)——自動構成・管理ツールを自身の実行環境のコンテキストで定期的または起動時に実行するホスト——は、自己修正コード(self-modifying code)を実行する。これは以下の3つの実務的困難を生む。 - **循環依存(circular dependency)問題**: 管理ツールがツール自身や基盤(underlying host)を変更するコードを実行するとき、順序が重要になる。ツール設計者は利用者がこの複雑な循環依存の挙動を理解しているとは仮定できない。 - **テストインフラの必要性**: 変更を本番に展開する前にその振る舞いを検証するテスト環境が必要だが、テスト環境で得た結果を本番へ再現するには、テスト環境と全く同じ順序で変更を適用する保証手段が必要になる。 - **決定的順序付けのコスト優位性**: 決定的な変更順序を生成するツールは、より柔軟な順序付けを許すツールよりも低コストで運用できるはずだという仮説。 論文はこれを「Order Matters(順序が重要である)」という予測(A Prediction)として定式化する——**2つのホストの振る舞いを完全に同一に保つ最も低コストな方法は、常に同じ変更を同じ順序で両ホストに適用することである**。この予測はディザスタリカバリ、クローニング、単一ホストの再構築(セキュリティ侵害後)にも適用されると主張する。 ## 提案手法 ### 管理手法の3分類 - **発散(Divergence、Figure 1)**: 稼働中ホストの構成が、望ましい/想定されたベースラインから徐々にドリフトしていく状態。今日のほとんどの企業インフラはこの状態にあると論文は主張する。原因は場当たり的な手動変更、同一ホスト上で独立に動く複数の自動エージェント、`rdist`/`rsync`/`ssh` によるpush型変更配布など。 - **収束(Convergence、Figure 2)**: 稼働中ホストの構成が理想的なベースラインへ向かって動いている状態。[[Mark Burgess]] のComputer Immunology原理([[cfengine]])に代表される、ディスクの一部(ファイルのチェックサム等)をサンプリングし逸脱を検知して修正するアプローチ。全ディスク内容を管理対象にはしないため、管理対象外ファイルが常に残り、それが将来の変更に影響するかは決定不能(undecidable)である。収束のみで発散インフラが合同に到達した例を著者らは知らないと述べる。 - **合同(Congruence、Figure 3)**: 稼働中ホストを、完全記述的なベースライン(初期状態+それを変更した手順の順序付き記録)に完全準拠させ続ける実践。ディスク状態(振る舞いではなく)で定義される、なぜなら「ディスク状態は完全に記述できるが、振る舞いは記述できない」(§A.59)ため。合同なインフラでは、最も古く複雑なホストでも数年分の管理作業を1時間で無人再生できる。isconf(著者ら自身のツール)が唯一の具体的な合同ツールだと述べ、cfengineも慎重に使えば合同管理に転用可能だとする。 いずれの図も、ラスター画像ではなくハッチングパターン(縦縞・横縞の矩形)を時間軸に沿って並べたベクトル描画で、実際のディスク状態(Actual)と目標状態(Target)のずれの推移を模式的に示す。 著者らの試算では、300ホスト・月次成長率2%の既存発散インフラを合同へ移行するROIは8か月未満(投資回収は5か月、11か月目に損益分岐)であるとする(Figure 4)。 ### チューリング等価性の思考実験(A.1〜A.60) Lance Brownの着想を起点に、著者らは以下の論証チェーンを構築する。 1. チューリング機械(A.1〜A.9、Figure 5): 無限テープを読み書きし完了状態で停止する機械。プログラムは quintuple(現在状態・読み取り文字・書き込み文字・移動方向・遷移先状態)の集合。ハルティング問題(A.7)ゆえ、任意のチューリング機械の停止性は一般には決定不能。 2. ユニバーサルチューリング機械(UTM)とチューリング仮想機械(TVM)(A.4〜A.6、Figure 6): UTMは任意のTMをエミュレートでき、TVMのプログラムとデータはUTMのテープ上に読み書き可能なビット列として存在するため、TVMは自身を記述する機械語命令を書き換えられる(自己修正コード)。Figure 6 は UTM のテープ上に TVM のプログラムと TVM のデータが並んで書き込まれる構造を示す。 3. ネットワーク接続されたUTM(A.14〜A.24): TVMがネットワーク経由で新しい命令セットB・Cを逐次フェッチし、既存の命令セットAを部分的に上書きしながらAB、ABC…と進化する様子を示す(命令セットAをBが部分的に上書きしAB機械が生じる Figure 7、さらにAB機械がCを読み込みABC機械が生じる Figure 9)。**命令ロード順序が異なれば異なる機械が生成される**(AB ≠ BA、Figure 8)。 4. ロールバックの限界(A.27〜A.32): AB機械からB命令を単純に除去してもAには戻らない(Bの一部がAを上書き済みのため)。安全なロールバックは事実上「最初から作り直す」ことに限られ、著者らは**プログラム制御下でのテープ変更は単調(monotonic)でなければならない**と結論する。 5. 現実のUNIXホストへの写像(A.33〜A.60): アプリケーションプログラムは(比較的)固定プログラムのチューリング機械に相当するのに対し、ASAT(自動システム管理ツール)はroot権限で自身のマスターコピーを含むディスク全体を書き換えられる点でTVM/UTMに相当する。この対応から、以下が導かれる。 - 順序A,B,Cとある順序A,C,Bで変更を行ったホスト群は、将来の全ての変更についても両バージョンをテストし続けねばならない(A.47、「二重のホストクラスの発生」)。 - N変更の順列の全数テストはN!に比例して爆発する(A.55、8変更で4.6年、実際のISconfクックブックの121ステップでは天文学的な年数)。 - 変更の直交性(orthogonality、互いに独立で無関係)を事前に証明することはできず(A.54)、直交性を予測するコスト Cpredict は、テストコスト Ctest やエラーコスト Cerror よりも高い(Cpredict > Cerror、Cpredict > Ctest)。 - 結論として、コスト順は Crandom > Cpredict > Cpartial > Ctest(Figure 10)であり、単一の決定的順序を検証・展開する Ctest が最小コストの選択肢である。 ## 新規性 - 従来のシステム管理論(Burgessのcfengine系列を含む)が主に**収束(convergence)**——理想状態への漸近的な補正——を軸に据えていたのに対し、本論文は収束と対立する第三の道として**合同(congruence)**——決定的順序付けされた変更履歴による完全記述——を明示的に定式化し、命名した最初の論文である([[収束型システム管理]] concept で既知の Burgess vs Traugott 論争の一次資料)。 - システム管理ツール設計に**計算可能性理論(チューリング機械・ユニバーサルチューリング機械・ハルティング問題)を直接援用**し、循環依存や自己修正コードの予測不能性を形式的な語彙で論じた点が独自である。著者ら自身「我々は理論家ではない」「数学的に証明したわけではない」と明言し、思考実験(thought experiment)として位置づけている。 - N!の組合せ爆発(A.55)を根拠に、決定的順序付けが「テストコストの観点から証明可能に最小コストである」と主張する点は、cfengineの収束理論(Burgess 2000、理想状態近傍での補正コストが線形)とは異なるコスト論証の軸を提供する。 ## 実験設定・実験結果 理論・思考実験中心の立場論文であり、統制された実験は行われない。準実証的な要素として以下がある。 - **ROI試算(Figure 4)**: 300ホスト・月次成長率2%の発散インフラを合同へ移行する際の累積コストを計算グラフとして提示し、8か月未満での投資回収、11か月目の損益分岐点を示す。著者らは「計算によるものだが、実際に転換した企業環境と一致する」と述べるのみで、定量的な検証データや統計的手法は開示していない。infrastructures.orgにパラメータを変えられるCGIジェネレータがあるとする。 - **実務経験からの帰納**: isconfを用いて数千ホストを長年運用してきた経験(「最初のインフラの一部は数年後も稼働し続けている」)を根拠として繰り返し引用するが、対照群を伴う比較実験ではない。 - **N!の組合せ計算(A.55)**: ISconf version 2iのHACMPクラスタ構築makefileが121ステップの逐次操作を持つという実例を挙げ、121!/24/365 ≈ 9.24×10^196年という数値で全順序テストの非現実性を定量的に示す。これは数学的な計算例であり、実験結果ではない。 ## 考察 - 著者らは§A系列の議論について「証明ではなく仮説として提示した」「他者による反証・支持の試みを歓迎する」と明言し、理論的厳密性より実務的直観の形式化に主眼を置く。 - 結論部(Conclusion and Critique)で、"Turing Equivalence"節の構成自体が複雑になりすぎたことを自己批判し、前方参照を避けるための番号付き言明という構成が可読性を犠牲にしたと認めている。著者らはこの複雑さを、A.1〜A.60の言明どうしの参照関係を線で結んだ相関図(Figure 11: Thread structure of Turing Equivalence assertions)として自ら可視化し、絡み合った参照の連鎖の多さを図示することで、論証を単一の線形な順序へ再構成すれば読みやすくなるはずだが前方参照が避けられなくなる、というトレードオフを認めている。 - テープサイズに関する未解決の問い(ネットワークがインターネットである場合、ホストはテープサイズも含めて真にUTMと等価かもしれない)を提起し、これは自己選択的にパッケージをダウンロード・インストールする現代のパッケージ管理ツールの傾向と関連しうると示唆する。 - Gödel数、Gödelの不完全性定理、Chomsky階層、対角化、ハルティング問題、NP完全性、順序集合論、閉ループ制御理論をさらなる理論的研究の出発点として挙げる。 ## 強み・弱点 **強み** - 発散・収束・合同という3分類は、その後の構成管理・IaC(Infrastructure as Code)の議論で繰り返し参照される基本的な語彙を提供した(cfengineの「収束」との対比軸として、後年のイミュータブルインフラストラクチャ論——[[@2021__OReillyJapan__SREの探求 - Chapter 24 イミュータブルなインフラストラクチャとSRE]]——にも通じる先駆的な整理)。 - N!組合せ爆発という単純だが説得力のある定量的論証で、「変更順序の任意性を許すこと」のテストコストを直感的に示している。 - 著者ら自身が数千ホスト規模の実運用でisconfを長期間使ってきた実務家であり、抽象論に終始せず具体的なmakefileの例(Listing 1・2)を通じて合同管理の実装イメージを与える。 **弱点** - チューリング等価性の議論は数学的な証明を伴わず、著者ら自身も「証明ではなく思考実験」と認めている。したがって「自己管理ホストはUTMと等価である」という中心的主張は、比喩としての説得力はあるが形式的な証明の対象にはなっていない。 - 実証データはROI試算1件のみで、検証方法・入力パラメータの妥当性は開示されていない。 - 図(Figure 1〜11)はいずれもASCII的なハッチングパターンや矢印を用いた説明用ダイアグラムであり、PDFには埋め込みラスター画像として存在しない(ベクトル描画)。本ページでは図をテキスト説明として扱い、画像埋め込みは行っていない。 - cfengineとisconfの比較は、著者らが後者の開発者であるという立場上のバイアスを免れない(cfengineは「慎重に使えば合同管理にも使える」と好意的に評価されるが、isconfのみが「唯一の合同ツール」と位置づけられる)。 ## 関連 - [[@1998__LISA__Bootstrapping an Infrastructure]] — 本論文の前身。isconfの原型(Hostkeeper)とEVM(Enterprise Virtual Machine)構想の初出。 - [[@2000__LISA__Theoretical System Administration]] / [[@2004__Wiley__Principles of Network and System Administration - Chapter 6 Models of network and system administration]] — Mark Burgessによる収束理論の定式化と、§6.7でのTraugottのcongruence論への直接応答。本論文はそのTraugott側の一次資料にあたる。 - [[収束型システム管理]] — 発散・収束・合同の3分類と、収束 対 合同(congruence)の論争の集約先concept。 - [[べき等性]] — cfengineの言語設計によるべき等な収束操作と対比される、決定的順序付けという別の再現性確保方針。 ## 出典 - Steve Traugott and Lance Brown, "Why Order Matters: Turing Equivalence in Automated Systems Administration," Proceedings of LISA '02: Sixteenth Systems Administration Conference, USENIX Association, Berkeley, CA, pp. 99-120, 2002.