2021/05/25

2021/20: Windows の TCP スタックが改善されている、サーバーレスでマルチプレイヤーゲームを構築するアーキテクチャなど

2021 年 20 週のネットサーフィンふりかえり

Algorithmic improvements boost TCP performance on the Internet

Boosting Dropbox upload speed—and making Windows’ TCP stack resilient to network reordering - Dropbox
https://dropbox.tech/infrastructure/boosting-dropbox-upload-speed

  • Dropbox が Windows におけるファイルアップロード速度を改善したという記事
  • Windows と Linux でアップロード速度に不一致があることを発見し、 Windows Core TCP チームと協力して、問題を切り分けて、回避策を探して、最終的に修正した
  • この問題は Windows TCP stack と、エッジサーバーで使用している NIC 上のファームウェアとのインタラクションに起因していた
  • 結果として Microsoft は TCP RACK-TLP アルゴリズムの Windows 実装と、パケットの reordering に対するレジリエンスを改善した

Algorithmic improvements boost TCP performance on the Internet - Microsoft Tech Community
https://techcommunity.microsoft.com/t5/networking-blog/algorithmic-improvements-boost-tcp-performance-on-the-internet/ba-p/2347061

  • Microsoft が公開した記事
  • TCP のパフォーマンス改善について以下の点を解説している
    • Introduction
      • TCP におけるパフォーマンスを左右する重要な 2つの要素 がある
        1. Congestion Control: 輻輳制御
        2. Loss Recovery: 損失回復
      • 輻輳制御の目的は、良好なパフォーマンスを維持し、輻輳を最小限に抑えるために、ネットワークに安全に注入できるデータ量を決定すること
      • スロースタートは、輻輳制御の初期段階で、パケットロスや ECN などの輻輳信号が発生するまで、 TCP が素早く速度を挙げる
        • ECN: Explicit Congestion Notification
          • 中継ルーターが明示的に congestion の発生を知らせる仕組み
            • Internet Protocol で行われるようだ
            • Type of Service 8bit 最後の 2bit が ECN に使用される
          • 関連 RFC (もっとあるかも)
            • RFC 2481: A Proposal to add Explicit Congestion Notification (ECN) to IP
            • RFC 3168: The Addition of Explicit Congestion Notification (ECN) to IP
            • RFC 4301: Security Architecture for the Internet Protocol
            • RFC 6040: Tunnelling of Explicit Congestion Notification
            • RFC 8311: Relaxing Restrictions on Explicit Congestion Notification (ECN) Experimentation
      • スロースタートに続く steady state の Congestion Avoidance ステージでは、異なる TCP 輻輳制御アルゴリズムが異なるアプローチで、インフライトデータ量を調整する
      • 損失回復は、送信中のパケットロスを検出して回復するプロセス
        • TCP は受信者からの ACK フィードバックをみて、セグメントが失われたことを推測し、失われたと推測されるセグメントを再送する
        • 損失回復に失敗した場合、 TCP は失われたセグメントを再送する最後の手段として、再送タイムアウト (RTO: retransmission timeout) を使用する
        • RTO タイマーが切れると TCP は最初の確認されていないセグメントから、スロースタートに戻る
      • この長い待機時間と、その後の輻輳応答はパフォーマンスに大きな影響を与えるため、 Loss Recovery アルゴリズムを最適化することで、 throughput を向上させ、レイテンシーを軽減する
    • Improving Slow Start: HyStart++
      • 従来のアルゴリズムでは、大量のパケットロスによりスロースタート中に RTO に到達する可能性があった
      • これを軽減するため HyStart と呼ばれるアルゴリズムの使用を検討した
        • HyStart は接続のレイテンシー増加が観測された際に Slow Start からの退出をトリガーする
        • しかし、これは誤検出によって Slow Start から早期終了が発生し、パフォーマンスを制限してしまう場合があることが分かった
        • HyStart がトリガーされた際に、輻輳回避ステージに行くのではなく LSS (Limited Slow Start) という、 Slow Start よりアグレッシブではないが、 Congestion Avoidance よりはアグレッシブなアルゴリズムを使用する
        • HyStart アルゴリズムに関する進行中の作業を TCPM ワーキンググープで採択された IETF ドラフトとして発表した
    • Loss recovery performance: Proportional Rate Reduction
      • HyStart はオーバーシュート問題を防ぎ、パケットロスを少なくして Slow Start の Loss Recovery に入ることができる
      • しかし、 Loss Recovery 自体も、大きなバーストで再送信を行うと、パケットロスが発生する可能性がある
      • PRR: Proportional Rate Reduction は損失回復アルゴリズムによって、 Loss Recovery 中、インフライトのバイト数を正確に調整し、回復終了時には congestion window にできるだけ近づけるようにする
        • RFC 6937: Proportional Rate Reduction for TCP
      • Windows 10 May 2029 Update で、 PRR がデフォルトで有効化されるようになった
    • Re-implementing TCP RACK: Time-based loss recovery
      • PRR と HyStart を実装した後も、 1つの congestion window で多くのパケットが失われた場合、損失回復時に一貫して RTO に到達する傾向があることに気づいた
      • トレースを見てみると TCP がタイムアウトする原因は、失われた再送が原因であることが分かった
      • Windows Server 2016 に同梱されている RACK の実装では、失われた再送を回復することができない
        • 失われた再送を回復できる、完全に RFC に準拠した RACK の実装には、セグメントごとの状態のトレースが必要だが、 Windows Server 2016 ではセグメントごとの状態が保存されていない
        • RFC 8985: The RACK-TLP Loss Detection Algorithm for TCP
      • Windows Server 2016 では、 1つの congestion window 内のデータブロックの送信時間をトレースするために、シンプルな circular-array based data structure を構築した
        • このデータ構造を使っていた RACK の実装には、失われた再送を回復できないなど、多くの制限があった
        • circular-array は所謂リングバッファのことかな
      • Windows 10 May 2020 Update の開発では、 TCP のセグメントごとの状態トラッキングを構築し、 Server 2022 では、失われた再送を回復できる新しい RACK 実装をリリースした
      • NOTE: RACK/TLP RFC の一部であるテールロスからの迅速な回復を支援する TLP: Tail Loss Probe も Windows Server 2016 から実装され、デフォルトで有効になっている
    • Improving resilience to network reordering
      • Microsoft としては Dropbox と Samsung から、ネットワークの並び替えが原因で Windows TCP でのアップロードパフォーマンスが低下しているという報告を受けていた
      • 現在開発中の Windows では RACK の実装を完了し、 RFC に完全に準拠した上で、並び替えの回復力の優先度を上げた
      • Dropbox と Samsung は、この新しい実装により、アップロードパフォーマンスの問題が発生しないことを確認した
  • かなりの大作
  • IP とか TCP とか全然わからん

DOM Events

DOM Events
https://domevents.dev/

  • DOM Event を学習するために作られた Web アプリ
  • DOM Event がどのような順序でトリガーされるのかを、可視化して把握できる

Your Ultimate Guide to Understanding DOM Events | egghead.io
https://egghead.io/courses/the-ultimate-guide-for-understanding-dom-events-6c0c0d23

文字エンコーディングの検出方法

文字エンコーディングの検出方法 - インフラエンジニアway - Powered by HEARTBEATS
https://heartbeats.jp/hbblog/2021/05/chardet.html

  • メールパーサーを実装する際に、文字エンコーディングをどのように検出すればよいのかまとめられている
  • 普通はメールに文字エンコーディングが指定されているが、実装次第では文字エンコーディングが指定されていないメールも存在する
    • 文字エンコーディングが指定されていない場合、文字エンコーディングの特徴から検出を行ったり、文字エンコーディング検出器を使うといった、様々な手法がある

サーバーレスでスケールするマルチプレイヤーゲームを構築する

サーバーレスでスケールするマルチプレイヤーゲームを構築する | Amazon Web Services ブログ
https://aws.amazon.com/jp/blogs/news/building-a-serverless-multiplayer-game-that-scales/

  • Web ベースのゲームを構築する際のアーキテクチャについて解説
  • フロントエンド
    • Vue.js で作成した SPA
    • Amplify Console を使うことで、 SPA の構築、デプロイ、ホスティングを手軽にできる
  • バックエンド
    • AWS SAM を使って定義
    • 使用する AWS サービス
      • AWS Lambda
        • マイクロサービスの実現
      • Amazon API Gateway
        • HTTP/Restful, WebSocket のエンドポイント提供
      • AWS IoT
        • MQTT over WebSocket 通信用のエンドポイント提供
      • Amazon DynamoDB
        • データのストア
      • Amaton SNS
        • Pub/Sub によるマイクロサービス間の通信
      • AWS Step Functions
        • 複雑なタスクの調整
      • Amazon Kinesis, Amazon S3, Amazon Athena
        • データ分析
      • Amazon Cognito
        • ログイン機能とユーザーディレクトリの提供
      • NAT Gateway, ElastiCache for Redis
        • サーバーレスではないが、それぞれ必要
        • NAT Gateway: VPC 設定を有効化した Lambda 関数が DynamoDB などのサービスエンドポイントにインターネット経由で接続するため
        • ElastiCache for Redis: ミリ秒未満のレイテンシー要件を持つアプリケーションに適したインメモリデータベースとして使用するため
          • ElastiCache は VPC 内からのアクセスが必要となるため、 Lambda 関数から連携する場合、 Lambda 関数の VPC 設定を有効化する必要があるということだろう
  • ユーザーの認証とバックエンドサービスとの通信
    • Cognito User Pool を使って認証
      • 認証後に払い出される JWT を使って API Gateway に対してリクエストを行う
    • AWS IoT への接続は IAM ポリシーによってアクセス制御
  • ゲームタイプ別のアーキテクチャ
    • シングルプレイヤーでのクイズを提供するアーキテクチャ
      • SPA から API Gateway HTTP API を呼び出してクイズを提供
      • 4つ の Lambda 関数
        1. ActiveGamesList
          • プレイヤーがゲームを遊ぶ際に呼び出される
          • DynamoDB の ActiveGames テーブルをクエリして、アクティブなゲームのリストをユーザーに返す
        2. GamePlay
          • プレイヤーがゲームを選択
          • DynamoDB の GamesDetail テーブルから、ゲームの問題を取得
        3. GameAnswer
          • プレイヤーがクイズに解答
          • GameDetails テーブルを照会してプレイヤーの回答をスコア付けする
          • リーダーボード用のプレイヤースコアと、プレイヤーエクスペリエンスを 2つの SNS トピックに送信する
            1. LeaderboardTopic
            2. PlayerProgressTopic
          • SNS トピックをサブスクライブする Lambda 関数を用意しておき、それぞれ DynamoDB テーブルに詳細を書き込む
        4. LeaderboardGet
          • リーダーボードの表示
          • Leaderboard テーブルから上位 10 名のスコアと、現在のプレイヤーのスコアを取得してレスポンスする
      • このアーキテクチャでは、非同期に処理を行うため、プレイヤーは待たされること無くスコアと解答を受け取れる
        • また、クイズに解答ごとに SNS を経由して、プレイヤーの進行状況を DynamoDB テーブルに保存するため、進行状況に対するセキュリティも強化される
    • マルチプレイヤーでの対戦を提供するアーキテクチャ
      • プレイヤー間の通信が必要
        • 一般的に TCP/UDP ソケットまたは WebSocket を使用する
        • 今回の場合 API Gateway WebSocket API によって実現
      • ゲームホストが対戦を開始
        • WebSocket API 経由で Lambda 関数にメッセージを送信
        • Lambda 関数では DynamoDB テーブルにアイテムを追加し、プレイヤーたちがゲームを見つけて参加できるようにする
        • ゲーム用の問題一式は、この時点で Lambda 関数からホストに対して送信される
        • ゲームホスト情報を別途 DynamoDB テーブルに追加し、どの接続がゲームに関連しているかトレースできるようにしておく
          • プレイヤーが参加するさいも Lambda 関数経由で Connection を DynamoDB で管理する
      • ゲームクライアント
        • すべてのプレイヤーのゲーム状態を管理、ゲームの流れを制御、 Lambda 関数経由でプレイヤーに問題、正答、リーダーボードを送信
        • Lambda 関数は、 DynamoDB を参照して、そのゲームに接続しているクライアントに対してのみ、ゲームメッセージを送信する
        • プレイヤーの解答は Lambda 関数経由でホストに送信される
      • ゲーム終了
        • Lambda 関数経由で最終リーダーボードを含むメッセージを全てのプレイヤーに送信
        • Lambda 関数はリーダーボードを DynamoDB に保存し、 Active なゲームであることを DynamoDB から削除、プレイヤーの進行情報を示すメッセージを SNS に送信
    • マルチプレイヤーでのライブスコアボードを提供するアーキテクチャ
      • AWS IoT で MQTT over WebSocket を使用する
        • これにより、クライアントはトピックをサブスクライブし、受信したメッセージを処理する
      • このアーキテクチャは、状態管理をゲームホストやクライアントで行わず、バックエンドのデータストアで行う
        • そのため、すばやく応答できるデータベースが必要となり ElastiCache for Redis を採用する
        • ゲーム用の問題、プレイヤーの解答、リーダーボードは、すべて Redis を使いクズ中に保存され、更新される
      • ゲームホストは、ゲームを開始し AWS IoT にメッセージを送信、 Lambda 関数をトリガーする
        • Lambda 関数は、ゲームを ActiveGames テーブルに追加し、 DynamoDB から Redis にクイズの詳細をキャッシュする
        • プレイヤーはメッセージを送信してゲームに参加しますが、そのメッセージは Lambda 関数に配信され、 Lambda 関数はユーザーレコードを Redis に追加し、プレイヤーが参加したことをホストに通知する
      • ゲームホストは Lambda 関数を呼び出してプレイヤーに問題を送信
        • Lambda 関数は Redis 内に保存されている、現在の問題番号を更新し、サブスクライブしているプレイヤーに問題を送信する
      • プレイヤー解答は Lambda 関数で処理する
        • 解答を検証し、 Redis に保存、スコアボードを更新、最初の正答のあと、更新されたスコアボード情報と共にすべてのプレイヤーに送信
          • これでリアルタイムに更新されるスコアボードが実現できる
      • ゲーム終了
        • ホストが IoT 経由で Lambda 関数を呼び出し、 Lambda 関数はリーダーボードへの書き込み、プレイヤーの進行状況を SNS Topic に送信、 Redis からゲームを削除、 ActiveGames テーブルからゲームを削除する
  • API Gateway WebSocket API と AWS IoT での MQTT over WebSocket が役割かぶってない？
    • シンプルに実現するなら API Gateway WebSocket API
    • パフォーマンスを重視するなら MQTT over WebSocket + Redis という感じのようだ
  • たしかに API Gateway WebSocket ではコネクション毎に ID を保存しておいて、メッセージ送信も対象とするコネクション ID ごとに行う必要がある
    • これは複数の相手に対して同時にメッセージを配信したいようなユースケースにあまり向いていない
    • MQTT over WebSocket であれば MQTT の Pub/Sub を Web プラットフォーム上で実現できるので、 IoT な感じはしないものの、良い選択肢だと思った

WebAssembly トレーニング

WebAssemblyアクター：クラウドからエッジへ（LFD134x）-LinuxFoundation-トレーニング
https://training.linuxfoundation.org/ja/training/webassembly-actors-from-cloud-to-edge-lfd134x/

  • Linux Foundation が公開した Rust を使って WebAssembly を扱うトレーニングコース

CS50 for Japanese

CS50 for Japanese: コンピュータサイエンスの入門 – 当ウェブサイトは、Creative Commons ライセンスに基づいて管理されています。
https://cs50.jp/

  • ハーバード大学の CS50 というコンピューターサイエンス入門講座の内容を日本語訳したもの

SICP 日本語訳

sicp-pdf/jsicp.pdf at japanese · hiroshi-manabe/sicp-pdf
https://github.com/hiroshi-manabe/sicp-pdf/blob/japanese/jsicp.pdf

  • 結構昔から公開されていたものだが、なんか時間を確保して読みたいなあと思って改めて調べた

See Also