プログラム実行における公理の破壊

新たな間違いを犯す

私はソフトウェアエンジニアとして約 15 年間働いています。私はキャリアを通じて多くのことを学び、その学んだことを多くの分散システムの設計と実装 (時には段階的に廃止したり、そのまま残したり) に応用しました。その過程で私は数多くの間違いを犯し、今でも間違いを犯し続けています。しかし、私の主な焦点は信頼性だったので、エラーの頻度を最小限に抑える方法を見つけるために自分の経験とコミュニティを振り返ってきました。私のモットーは、次のとおりです。新しい間違い (それほど明白ではありませんが、より高度な間違い) を絶対に犯してみなければなりません。間違いを犯すのは問題ありません。それを繰り返して学習するのです。それは悲しく、落胆させます。

おそらくそれが、私が常に数学に魅了されてきた理由です。それはエレガントで簡潔であるだけでなく、その論理的厳密さが間違いを防ぐためです。現在の状況、どのような仮説や定理を信頼できるかについて考える必要があります。これらのルールに従うことが効果的であり、正しい結果が得られます。確かに、コンピューターサイエンスは数学の一分野です。しかし、私たちが普段実践しているのはソフトウェアエンジニアリングであり、非常に独特なものです。私たちは、時間の制約とビジネス ニーズを考慮しながら、コンピューター サイエンスの成果と発見を実践に適用します。このブログは、コンピュータ プログラムの設計と実装に半数学的推論を適用する試みです。多くのプログラミング エラーを回避するためのフレームワークを提供する、さまざまな実行体制のモデルを提案します。

ささやかな始まりから

私たちがプログラミングを学び、最初の暫定的な (または大胆な) ステップを実行するとき、通常は単純なものから始めます。

• ループのプログラミング、基本的な算術演算の実行、および端末での結果の出力
• おそらく MathCAD や Mathematica などの特殊な環境で数学の問題を解く

私たちは筋肉の記憶を獲得し、言語の構文を学び、そして最も重要なことに、私たちは思考と推論の方法を変えます。私たちはコードを読み、コードがどのように実行されるかを推測することを学びます。私たちが言語標準を読むことから始めて、その「メモリ モデル」セクションを注意深く読むことはほとんどありません。それは、言語標準を十分に理解して活用するための準備がまだ整っていないからです。私たちは試行錯誤を繰り返します。最初のプログラムでは論理的および算術的なバグが発生します。これらの間違いは、私たちの仮定を確認することを教えてくれます。このループの不変式は正しいですか、この方法で配列要素のインデックスと長さを比較できますか (これはどこに -1 を置きますか)。しかし、何らかのエラーが見つからない場合、多くの場合、暗黙のうちに何らかのエラーが内部化されます。不変条件システムは私たちに強制し、提供します。

つまり、これは次のとおりです。

コード行は常に同じ順序で (シリアル化されて) 評価されます。

この公準により、次の命題が真であると仮定することができます (証明するつもりはありません)。

• 評価順序は実行間で変わりません
• 関数呼び出しは常に戻ります

数学的公理を使用すると、強固な基盤に基づいてより大きな構造を導出し、構築することができます。数学では、4+1 の公準をもつユークリッド幾何学があります。最後はこう言っています。

平行線は平行のままで、交差したり分岐したりしません。

何千年もの間、数学者はそれを証明し、最初の 4 つからそれを導き出そうとしました。それは不可能であることがわかりました。この「平行線」公準を代替案に置き換えて、さまざまな種類の幾何学形状 (つまり、双曲線や楕円形) を得ることができます。これにより、新たな可能性が開かれ、適用可能で有用であることがわかります。結局のところ、私たちの惑星の表面は平らではなく、GPS ソフトウェアや飛行機のルートなどでそれを考慮する必要があります。

変化の必要性

しかしその前に、立ち止まってエンジニアリングに関する最も重要な質問をしてみましょう。なぜわざわざそうするのでしょうか?プログラムがその役割を果たし、サポート、維持、進化するのが簡単であれば、そもそも、なぜこの予測可能な逐次実行という居心地の良い不変条件を放棄する必要があるのでしょうか?

答えは 2 つあります。 1つ目はパフォーマンスです。プログラムを 2 倍の速度で実行できる場合、またはハードウェアの半分を必要とする場合、これはエンジニアリングの成果です。同じ量の計算リソースを使用する場合、2 倍 (または 3、4、5、10 倍) のデータを処理できます。これにより、同じプログラムのまったく新しいアプリケーションが開かれる可能性があります。サーバーではなく、ポケットの携帯電話上で実行される場合があります。場合によっては、賢いアルゴリズムを適用したり、よりパフォーマンスの高い言語で書き直すことによって速度を向上させることができます。はい、これらが最初に検討すべきオプションです。しかし、それらには限界があります。ほとんどの場合、アーキテクチャは実装よりも優れています。ムーアの法則は最近あまりうまくいっておらず、単一の CPU のパフォーマンスはゆっくりと成長しており、RAM のパフォーマンス (主にレイテンシー) が遅れています。したがって、当然のことながら、エンジニアは他の選択肢を探し始めました。

次に考慮すべき点は信頼性です。自然は混沌であり、熱力学の第 2 法則は、正確で連続的で反復可能なものに対して常に作用します。ビットが反転し、材料が劣化し、電力が低下し、ワイヤーが切れてプログラムの実行が妨げられます。逐次的かつ反復可能な抽象化を維持するのは困難な仕事になります。私たちのプログラムがソフトウェアやハードウェアの障害を乗り越えて存続できれば、ビジネス上の競争上の優位性を持つサービスを提供できます。これは、私たちが取り組み始めることができるもう 1 つのエンジニアリング課題です。

目標を設定したので、シリアル化されていないアプローチで実験を開始できます。

実行スレッド

この疑似コードの部分を見てみましょう。

```

def fetch_coordinates(poi: str) -> Point:

…

def find_pois(center: Point, distance: int) -> List[str]:

…

def get_my_location() -> Point:

…
def fetch_coordinates(p) - Point:
…

def main():

me = get_my_location()

for point in find_pois(me, 500):
loc = fetch_coordinates(point)
sys.stdout.write(f“Name: {point} is at x={loc.x} y={loc.y}”)

コードを上から下まで読むと、「get_my_location」の後に「find_pois」関数が呼び出されることが合理的に想定できます。そして、次の POI を取得した後、最初の POI の座標を取得して返します。これらの仮定は正しく、メンタル モデルを構築し、プログラムについて推論することができます。

コードを非順次に実行できると想像してみましょう。これを構文的に行う方法はたくさんあります。ステートメントの並べ替えに関する実験 (これは最新のコンパイラや CPU が行うことです) をスキップし、新しい関数実行体制を表現できるように言語を拡張します。同時にあるいは並行して他の機能に関しても。言い換えると、複数の実行スレッドを導入する必要があります。私たちのプログラム関数は特定の環境 (OS によって作成および維持される) で実行されます。現時点では、アドレス指定可能な仮想メモリと、CPU によって実行できるスケジューリング ユニットであるスレッドに興味があります。

スレッドには、POSIX スレッド、グリーン スレッド、コルーチン、ゴルーチンなど、さまざまな種類があります。詳細は大きく異なりますが、要するに実行できるものです。複数の関数を同時に実行できる場合は、それぞれに独自のスケジューリング ユニットが必要です。つまり、マルチスレッドは、実行スレッドが 1 つではなく、複数あることに由来しています。一部の環境 (MPI) や言語では暗黙的にスレッドを作成できますが、通常は、C の `pthread_create`、Python の `threading` モジュール クラス、または Go の単純な `go` ステートメントを使用して明示的にこれを行う必要があります。いくつかの予防措置を講じれば、同じコードをほぼ並行して実行できます。

 def fetch_coordinates(poi, results, idx) -> None: … results[idx] = poi def main(): me = get_my_location() points = find_pois(me, 500) results = [None] * len(points) # Reserve space for each result threads = [] for i, point in enumerate(find_pois(me, 500)): # i - index for result thr = threading.Thread(target=fetch_coordinates, args=(poi, results, i)) thr.start() threads.append(thr) for thr in threads: thr.wait() for point, result in zip(points, results): sys.stdout.write(f“Name: {poi} is at x={loc.x} y={loc.y}”)

私たちはパフォーマンス目標を達成しました。プログラムは複数の CPU で実行でき、コア数の増加に応じて拡張でき、より速く終了します。私たちが次に問わなければならないエンジニアリングの質問は、どれくらいのコストがかかるのかということです。

私たちは、シリアル化された予測可能な実行を意図的に放棄しました。がある全射なし関数 + 時点とデータの間。各時点で、実行中の関数とそのデータの間には常に 1 つのマッピングが存在します。

次の結果は、今回はある関数が別の関数より先に終了する可能性があり、次回は別の方法で終了する可能性があるということです。この新しい実行体制はデータ競合を引き起こします。並行関数がデータを処理する場合、データに適用される操作の順序が未定義であることを意味します。私たちはデータ競合に遭遇し始め、以下を使用してそれに対処する方法を学びます。

• クリティカル セクション: ミューテックス (およびスピンロック)
• ロックフリーのアルゴリズム (最も単純な形式は上記のスニペットにあります)
• 人種検出ツール
• 等

この時点で、少なくとも 2 つのことがわかります。まず、データにアクセスする方法は複数あります。一部のデータは地元(関数スコープ変数など) そして私たちだけがそれを見る(そしてアクセスする)ことができるので、それは常に私たちが残した状態になります。ただし、一部のデータは共有されたり、リモート。これはまだプロセス メモリ内に存在しますが、特別な方法でアクセスするため、同期が失われる可能性があります。場合によっては、データ競合を避けるために、それをローカル メモリにコピーして作業することがあります。そのため == 。クローン（） == は Rust で人気があります。

この推論を続けると、スレッドローカル ストレージなどの他のテクニックが自然に登場します。私たちはプログラミング ツールベルトに新しいガジェットを追加し、ソフトウェアを構築することで達成できることを拡大しました。

ただし、まだ信頼できる不変条件があります。スレッドから共有 (リモート) データにアクセスすると、常にそれを取得します。一部のメモリ チャンクが使用できない状況は発生しません。バッキング物理メモリ領域に障害が発生した場合、OS はプロセスを強制終了してすべての参加者(スレッド) を終了します。ミューテックスをロックした場合、同じことが「私たちの」スレッドにも当てはまります。ロックを失う可能性はなく、実行中の作業を直ちに停止する必要があります。この不変条件 (OS と最新のハードウェアによって強制される) を利用して、すべての参加者は死亡しているか生存しているかのどちらかであると判断できます。すべては運命を共有しています。プロセス (OOM)、OS (カーネル バグ)、またはハードウェアに問題が発生した場合、すべてのスレッドは外部に副作用を残さずに一緒に存在しなくなります。

プロセスの発明

注意すべき重要な点が 1 つあります。スレッドを導入するという最初のステップをどのようにして行ったのでしょうか?私たちは別れ、分岐しました。 1 つのスケジューリング ユニットの代わりに、複数のスケジューリング ユニットを導入しました。この非共有アプローチを適用し続けて、どうなるか見てみましょう。今回はプロセスの仮想メモリをコピーします。これは、プロセスの生成と呼ばれます。プログラムの別のインスタンスを実行したり、他の既存のユーティリティを開始したりできます。これは以下に対する優れたアプローチです。

• 厳密な境界を持つ他のコードを再利用する
• 信頼できないコードを実行し、それを自分のメモリから隔離します

ほぼすべて ==最新のブラウザ==このように動作するため、インターネットからダウンロードされた信頼できない Javascript 実行可能コードを実行し、タブを閉じるときにアプリケーション全体をダウンさせることなく確実に終了させることができます。

これは、運命共同体の不変性を放棄し、仮想メモリの共有を解除してコピーを作成することで発見した、さらに別の実行体制です。コピーは無料ではありません:

• OS はメモリ関連のデータ構造を管理する必要があります (仮想 -> 物理マッピングを維持するため)
• 一部のビットが共有されている可能性があるため、プロセスが追加のメモリを消費します

くつろぐ

なぜここで止まるのですか？他に何をコピーしてプログラムを配布できるかを調べてみましょう。しかし、そもそもなぜ分散するのでしょうか?多くの場合、当面のタスクは 1 台のマシンを使用して解決できます。

分散化する必要がある運命共同体から逃れるためにそのため、下層の層が遭遇する避けられない問題に応じてソフトウェアが停止するようになります。

いくつか例を挙げると、

• OS のアップグレード: 時々、マシンを再起動する必要があります。

• ハードウェア障害: 予想よりも頻繁に発生します

• 外部障害: 停電やネットワークの停止は問題です。

  
  

OS をコピーすると、それを仮想マシンと呼び、顧客のプログラムを物理マシン上で実行し、その上に巨大なクラウド ビジネスを構築できます。 2 台以上のコンピュータを使用し、それぞれでプログラムを実行すると、プログラムはハードウェア障害が発生した場合でも存続し、24 時間年中無休のサービスを提供し、競争上の優位性を得ることができます。大企業ははるか昔にさらに進化し、現在ではインターネット大手が異なるデータセンターや大陸にさえコピーを実行しているため、台風や単純な停電に対してプログラムの回復力が強化されています。

しかし、この独立性には代償が伴います。古い不変条件は強制されず、私たちは独自に行動します。心配しないでください、私たちが初めてではありません。私たちを助けるテクニック、ツール、サービスはたくさんあります。

テイクアウト

私たちは、システムとそのそれぞれの実行体制について推論する能力を獲得したところです。すべての大規模スケールアウト システムの内部では、ほとんどの部分はよく知られたシーケンシャルおよびステートレスであり、多くのコンポーネントはメモリ タイプと階層を備えたマルチスレッドであり、すべて真に分散された部分の組み合わせによってまとめられています。

目標は、現在どこにいるのか、どのような不変条件が保持されているのかを区別し、それに応じて動作 (変更/設計) できるようにすることです。 「未知の未知のもの」を「既知の未知のもの」に変換するという基本的な推論を強調しました。これは重要な進歩ですので、軽く考えないでください。