Sibuna技術ガイド 1.0.0-beta.3 ドキュメント
言語: 日本語
English简体中文한국어日本語EspañolDeutschहिन्दीالعربية
このページの内容

第I部:リクエストのコスト

アルゴリズムを選ぶ前に、それが守るべき資源を特定します。この章では、後のすべての設計判断を測る基準となる小さなモデルを作ります。オリジンの作業、パズルの作業、セッションによる償却、そして信頼できないクライアントがサーバーに保持させ得るメモリです。

許可は経済的な判断

オリジンが、許可したリクエストごとにデータベースを検索し、ページを描画するとします。その作業を\(c_o\)、リクエストあたりのゲートの作業を\(c_g\)、到着率を\(r\)とします。ゲートがなければ、オリジンは毎秒\(r c_o\)単位の作業をこなさなければなりません。割合\(a\)だけを許可するゲートは、この需要を\(r a c_o\)に変え、自身は\(r c_g\)を費やします。ゲートが役に立つのは、節約したオリジンの作業が、ゲート自身のコストと正当な訪問者に課すコストを上回るときだけです。

\[r c_g + r a c_o < r c_o \quad \Leftrightarrow \quad c_g < (1-a) c_o.\]

これは処理能力のモデルであり、測定ではありません。帯域幅、接続の状態、ストレージ、クライアントの待ち時間を省いています。このモデルの価値は、欠けている項がすべて目に見えることです。キャッシュにヒットすれば\(c_o\)は小さくなり、高価なクエリなら大きくなります。要求側とサーバー側のコスト比に普遍的な値はありません。

作業証明が示すもの

クライアントパズルが示すのは、誰かが公開された検証規則を満たす入力を見つけたということです。人間であること、身元、善意は示しません。要求側は計算資源を借りることも、有効期間内の有効なセッションを再利用することも、作業を複数のマシンに分散することもできます。パズルは許可のコストを変えます。許可されたリクエストに何を許すかは、引き続きポリシーと検査が決めます。

アドレスに基づく制限はこれを補います。制限は一つのアドレスを縛りますが、共有アドレスの背後には多くの人がいることがあり、一人の要求者が多くのアドレスを使うこともあります。パズルもアドレスも、身元を判定するオラクルにはなりません。そのためSibunaは、許可、検査、レピュテーションを別々の判断として扱います。

確率変数としてのハッシュ探索

理想的な256ビットのダイジェストでは、先頭に\(b\)個のゼロビットを要求すると、独立な試行ごとの成功確率は\(p = 2^{-b}\)になります。最初の成功までの試行回数を\(K\)とします。このとき

\[P(K=k) = (1-p)^{k-1} p, \quad P(K>k) = (1-p)^k, \quad E[K] = 1/p = 2^b.\]

期待値は裾の和から導かれます。

\[E[K] = \sum_{k=0}^{\infty} P(K>k) = \sum_{k=0}^{\infty} (1-p)^k = 1/p.\]

難易度を1段上げると、期待試行回数は2倍になります。どのパズルも2倍の時間がかかると約束するものではありません。最初の試行で成功するものもあれば、平均よりはるかに長くかかるものもあります。解答を一度だけ測ったクライアントが測ったのは、主にこのランダム性です。

x = 0で1から始まり、x = 4に向かって0へ下がる曲線です。x = 1の印の点は、探索がまだ続いている確率がeのマイナス1乗、約0.368であることを示します。xが約3.0の二つ目の点は、95パーセントの探索が終わっていることを示します。
図 1 ハッシュ探索の生存確率。期待試行回数の\(x\)倍だけ試行した後も探索がまだ続いている確率で、作業量が大きいときの近似\(P(K > x/p) \approx e^{-x}\)を使います。

セッションによる作業の償却

セッションが期限までに\(m\)件のリクエストを許し、パズルのコストが\(c_p\)、検証のコストが\(c_v\)、セッションの確認のコストが\(c_s\)だとします。失敗した試みを無視すると、リクエストあたりの償却したゲートのコストは\(c_v/m + c_s\)、クライアントのパズルのコストは\(c_p/m\)です。セッションの有効期間を延ばすと、人にも自動化されたクライアントにも同じように有利になります。有効期間の選択はポリシーの判断であり、暗号上の最適化ではありません。

有界な状態という第二の予算

作業をリクエストの経路から移しても、作業は消えません。インシデントが到着率\(\lambda\)で届き、ストレージスレッドが平均速度\(\mu\)で永続化し、キューが\(Q\)件のレコードを保持するとします。\(\lambda > \mu\)のとき、流体近似から次が得られます。

\[t_{\mathrm{fill}} \approx \frac{Q}{\lambda - \mu}.\]

大きなキューは時間を稼ぎますが、スループットを生み出しはしません。バッチ処理はトランザクションのコストを償却しますが、保持したレコードには依然としてメモリと、いずれ行う処理が必要です。過負荷のとき、Sibunaは新しいインシデントのレコードを破棄し、その件数を数えます。リクエストの判断はメモリ上の状態から引き続き行います。運用者は、HTTPの成功率だけでなく、失われた証跡も監視しなければなりません。

本書で保ち続ける不変条件

  1. 信頼できないリクエストは、上限のないサーバー状態を作れません。
  2. 有効な許可トークンがあっても、アプリケーションによる拒否は回避されません。
  3. バッファーは、そこから借用したどのスライスよりも長く生存します。
  4. 永続的な再試行によって、インシデントやそのレピュテーションへの効果が重複することはありません。
  5. 公開したポリシーのスナップショットは、最後の読み手が手放すまで変更されません。

本書の残りでは、これらの主張を真にする仕組みと、違反を明らかにするテストを導きます。高速パスが役に立つのは、これらの主張が真であり続ける間だけです。