HN 日本語サマリー

← 一覧へ戻る
プログラミング

構造的正確性

Structural Correctness (blog.sao.dev)

14 pointsby stuartaxelowen0 コメント

要約

構造的正確性とは、問題領域を型付きノードとエッジのグラフとしてモデル化し、その構造自体がシステムの定義となることで、検証可能なシステムを構築するアプローチです。型システムやBazelのようなビルドシステムがその例です。この記事では、この概念をデータベースの限界やペトリネットの概念と対比させながら解説し、特にWebスクレイパーの例を用いて、状態と遷移を一元的に定義し検証できるカラーペトリネットの可能性を示しています。

全文翻訳

構造的正確性

型システムは素晴らしいものです。コンパイル時に膨大な数のバグを検出し、アプリケーションの将来的な開発のための文法/語彙に貢献します。型システムと同様に、正確性を検証するための最新のツールは、問題の構造的記述、つまりドメインのグラフ構造モデルを通じて、その恩恵を受けています。

  • 型システムは、プログラムを型、関数、トレイトなどのグラフ、およびそれらの関係として記述します。型はノードであり、returns(返す)、accepts(受け入れる)、implements(実装する)などの関係がエッジとなります。
  • bazelのようなビルドシステムは、ビルドターゲットをノード、依存関係をそれらの間のエッジとしています。明示的な依存関係が指定されていない場合、たとえ他の手段でビルドされたとしても、未指定のパッケージはビルドターゲットに提供されず、完全性(hermiticity)と容易なデプロイ可能性(trivial deployability)を満たします。
  • インターフェース記述言語は、メッセージタイプとサービスをノード、戻り値の型とパラメータの型をエッジ(制限された型システム)としています。
  • データベースは、外部キー(エッジ)を使用して、関連するテーブル行(ノード)間の関係を記述します。しかし、データベースは正確性を実装するためにチェック制約も使用します。これは構造的ではありませんが、加算的に記述できない側面を表現するのに役立つ述語です。

ドメインを、型付けされたノードとエッジのグラフとしてモデル化してください。これらのグラフの最良のものは定義的です。システムを記述する構造そのものがシステムなのです。エッジがなければ、機能もありません。

各ドメインには、ノードタイプとエッジタイプの独自の語彙があります。Bazelは、さまざまなエッジタイプによるその豊かさの良い例です。depsは「このコードをリンクする」、srcsは「これらのファイルをコンパイルする」、dataは「実行時に利用可能にする」を意味します。それぞれがターゲットグラフにおける異なるエッジタイプであり、それぞれが異なる機能を提供します。ノードタイプとエッジタイプのエレガントな選択は、表現力豊かで強力なツールにつながります。これらの正確性ツールの多くは、構造的正確性と述語の両方を利用して、有効な構成を記述します。

これらのグラフ構造システムの最良のものは、構成的/定義的です。それらは「何が有効か」と「出力がどのように計算されるか」の両方を定義します。Bazelでは、ターゲットはdep(依存)していないモジュールをインポートできません。これは2つの貴重な機能を提供します。a) システムが機能するためには検証可能な不変条件を明示的に記述する必要があるため、デフォルトで検証可能なシステムが得られます。b) 明示された属性と関係が、動作と検証の両方に利用されるため、仕様の簡潔さが得られます。Bazelプロジェクトを構築すると、製品の明示的な構造を記述する必要が生じ、開発を続けるにつれてそれを検証する手段が得られます。

「各ドメインには独自のnounds(名詞)とverbs(動詞)がある」という点と、「定義的なグラフ構造システム」という2つの点は、Bazelが製品全体を記述するための優れた基盤である理由です。Bazelを使用すると、ドメインの概念(パッケージ、サービス、データセット)の任意のノードタイプを定義し、型付きエッジを通じてそれらの関係を制約し、その単一の構造記述からビルド/テスト/デプロイパイプライン全体を派生させることができます。サービス、そのメトリクスエンドポイント、およびそれをスクレイピングするPrometheusデプロイメントは、すべて同じグラフ内のノードにすることができます。それらの関係は一度宣言され、システム全体をコンパイル、デプロイ、および検証するために使用されます。

状態についてはどうでしょうか?

良い質問です!データベースは、スキーマで指定されたテーブル、外部キー、およびチェック制約を通じて、何が保存できるかを定義します。しかし、それらの外部では、有効な状態遷移を指定しません。これはしばしばアプリケーション層に任され、HTTPまたはRPCエンドポイントがビジネスロジックを忠実に実装することが期待されます。しかし、これはしばしば問題が発生する場所です。例えば、注文ステータスを変更する2つのエンドポイントがあり、一方がshipped(出荷済み)とマークする前に在庫を確認するのを忘れる、といった具合です。

カラーペトリネット(CPN)は、スキーマで指定されたコレクション(プレース/トークン)を取得し、遷移を通じて厳密な「次の状態」定義を追加します。CPNでは、状態は特定のバインディングが選択され、その遷移が発火して、特定のプレースのトークンを消費、変更、生成することによってのみ変化します。これは状態に対するグラフ構造システムの応用です。プレースと遷移はノードであり、それらを接続するアークはエッジです。Bazelと同様に、CPNシステムの機能を定義する概念は、システムをより完全に検証するための手段としても機能します。

CPNがこれをどのように行うかを示すために、かなり複雑な例、つまりWebスクレイパーを walkthrough してみましょう。私は元のCPN投稿で説明したWebスクレイパーを興味の対象として実装しました。この例では、スクレイパーはプロキシのローテーションセットを使用し、サイトへの過負荷を防ぐためにドメインの「リース」セマンティクスを実装する必要があります。伝統的に、このようなステートフルシステムを構築することは、複数のレイヤーにわたる調整を分散させることを意味します。データベースはリソースの状態(SELECT FOR UPDATEと注意深いロック順序付けを通じて)を処理し、タスクキューはジョブスケジューリングを処理し、アプリケーションコードはレート制限とクールダウンロジックを処理し、さらに別のコンポーネントがドメインの同時実行制限を強制します。それぞれが正確性に関する不完全なビューを持っています。そして、チェック制約、単体テスト、アプリケーションレベルの述語を記述し、試行錯誤を通じてそれらが一致することを確認することで信頼性を向上させます。

プロキシの保全性は、テストするプロパティではなく、ネットのトポロジカルな事実です。

CPNを使用すると、スクレイパーの完全な調整モデルがトークンと遷移として宣言されます。スクレイピングのためにリソースを要求することは、利用可能なリソース、プロキシ、およびドメインの状態にまたがる単一の遷移(select_resource)です。これは、プロキシをリースし、ドメインのアクティブカウントをインクリメントし、セッションをすべて同じ発火で作成します。バインディングシステムは有効な組み合わせのみが参加することを保証するため、正しいロック戦略を取得する必要はありません。プロキシトークンは常に1つのプレース(available_proxiesまたはleased_proxies)にのみ存在し、宣言された遷移のみがそれを移動できるため、プロキシの保全性はテストするプロパティではなく、トポロジカルな事実です。リソースのライフサイクル(available → leased → cooling → available)は、ネット自体の形状であり、実質的にステートマシンです。

また、ネットのクールなアニメーションを見せびらかすことができます(フィードリーダーは下の埋め込みを削除します — フルサイズで表示):

フルサイズ — WebスクレイパーCPN、アニメーション付き

個人的には、この状態と遷移の統合に楽観的です。データベースは一般的に、このデータ+タイプ側と、チェック制約のような述語ツールのみを扱います。既存のシステムが状態関連の不変条件をアプリケーションコード、単体テスト、およびデータベース制約(それぞれ個別の検証を伴う)に分散させているのに対し、CPNはこれらの懸念を統合し、それらを使用してアプリの機能を定義します。

新しいドメインとして、これらのシステムからどのようなバグが発生する可能性があるか、またはどのような種類の操作やパフォーマンスのトレードオフが必要になるかについて、多くの学習が待っています。型システムは、有名にも無料ではありません。しかし、それに伴うさらに大きな機会が見えます。