One Million Checkboxesを6億5千万回のチェックまで拡張した技術

 (eieio.games)
1 ポイント 投稿者 GN⁺ 2024-07-28 | 1件のコメント | WhatsAppで共有
  • 2024年6月26日に公開された One Million Checkboxes は、全員が同じ100万個のチェックボックスをリアルタイムで操作するサイトで、2週間後の終了までに 6億5千万回 を超えるチェックを処理した
  • 状態そのものは 100万ビット、つまり125KBにすぎなかったが、nginx、Flask/gunicorn、Redis pubsubで作られた初期構成は、予想外のトラフィックの前で急速に限界へ達した
  • Hacker News、Reddit、Mastodon、Twitterから数万人が押し寄せると、Redis接続の枯渇、帯域幅の急増、入力検証漏れ、古い更新の適用といった問題が連鎖的に表面化した
  • 対応はサーバーとRedisのスケールアップ、更新のバッチ処理、転送フォーマットの縮小、Linux tc ベースの 250Mbit/s帯域上限、プロセス再起動スクリプトのような、素早く適用できる施策に集中した
  • その後バックエンドをGoへ移行して安定化し、最後はRedis Luaスクリプトでチェックボックスの凍結ロジックを原子的に処理して、2024年7月11日米東部時間4:35 PMにサイトは幕を閉じた

サイトと初期設計

  • One Million Checkboxes(OMCB) は2024年6月26日に公開されたWebサイトで、100万個のグローバルなチェックボックスを提供した
    • 1人のユーザーがチェックボックスをオンまたはオフにすると、すべてのユーザーの画面に即座に反映された
    • 制作には2日かかり、想定ユーザー数は多くても数百人程度だった
  • 実際の反応は予想をはるかに上回った
  • 初日序盤のログは一部残っていない
    • 当初は1日分のログのうち最新100万件だけを保存していたため
    • 2日目から安定化が始まり、その日に5千万件以上がチェックされた
    • サイト終了前の累計チェック数は 6億5千万回 を超えた

Redis中心の元のアーキテクチャ

  • チェックボックスの状態は 100万ビット で表現された
    • チェック済みのボックスは 1、未チェックのボックスは 0
    • 全状態のサイズは125KB
    • クライアントはビットセット(bitset)を保持し、描画時にそれを参照した
  • クライアントはDOM負荷を避けるよう構成されていた
    • 100万個の要素をすべてDOMに入れない
    • react-window を使い、現在画面に見えているチェックボックスと小さなバッファだけを描画した
  • サーバー構成は、シンプルな水平スケールを念頭に置いたものだった
    • nginxが静的コンテンツを配信し、APIリクエストとwebsocket接続をFlaskサーバーへ転送した
    • Flaskサーバーはgunicornで動く2インスタンスだった
    • Redisはチェックボックス状態の保存とメッセージキューの役割を担った
  • Redisの使い方も直接的だった
    • Redisのbit操作primitiveで個々のチェックボックス状態を変更した
    • クライアントがチェックイベントを送ると、FlaskがRedisのbitを反転させ、pubsubにイベントを書き込んだ
    • 2台のFlaskサーバーはpubsubを読み、自分に接続しているクライアントへ変更を通知した
  • 全状態スナップショットは、更新取りこぼしを補正するための仕組みだった
    • タブがバックグラウンドにあり更新を逃したクライアントを同期させるための用途だった
    • 初期実装では30秒ごとに全状態を送る方式だった

スケール方針

  • コストは上限を計算できる必要があった
    • 無制限のオートスケールでコストが爆発する方式は避けた
    • 期待を超える負荷が来たら壊れるままにしておく方を選んだ
  • 人気の持続時間は短いと仮定した
    • 数日や数週間かかる完成度の高い解決策より、数時間で作れる対応を優先した
    • その過程で生じる技術的負債は受け入れた
  • 技術選定はシンプルで直接運用できるものを好んだ
    • 自分でサーバーに入ってコマンドを実行し、デバッグできる構成を選んだ
    • 自前で運用とデバッグが可能な依存関係を主に使った
  • サイトの核心体験は グローバル同期 だった
    • どこへ移動しても即座の変化が見える必要があった
    • ユーザーが見ているチェックボックスだけを送る方式には拡張しなかった

初日: サーバー増設とRedisボトルネック

  • 公開から30分で負荷が急増し、サイトは生きていたが長くは持たない状態だった
    • 最も明確な改善策はサーバー増設だった
    • nginxは別VM上のFlaskインスタンスへ簡単にリバースプロキシでき、状態はすでにRedisにあった
  • 2台目のサーバーは12:30 PMごろ追加されたが、すぐに負荷100%へ達した
    • 当初はサーバーを1〜2台追加すれば十分だと見ていた
    • 実際にはスケールするほどトラフィックも増えた
    • Hacker Newsで1位になり、Twitterでの活動も急増した
  • FlaskサーバーとRedis接続がボトルネックになった
    • Redis接続プールがなく、Redisは接続不足寸前の状態になっていた
    • 更新をバッチにまとめて送る方式へ切り替えた
    • 既存クライアントとの互換性は考慮せず、ユーザーはリロードするだろうと判断した
  • Redis接続プールも追加したが、gunicornとFlaskの組み合わせではきれいには動かなかった
    • それでもRedis接続数の削減には役立ったようだった
    • その後この問題は深掘りせず、Go移行へ進んだ
  • セッション生成のrate limitは削除された
    • rate limitの状態がRedisに保存されており、Redis接続が枯渇していたため
    • 問題は新規セッションの急増ではなく、単一セッションが大量のデータを送ることにあった
    • 短期的には危険だが受け入れ可能な措置だと判断した
  • Redisインスタンスもより大きな構成へ引き上げた
    • Digital Ocean managed Redisを使っていた
    • 1 shared CPU、2GB RAMの小さなインスタンスから、4 dedicated CPU、32GB RAMのインスタンスへ拡大した
    • リサイズには約30分かかった

帯域幅の問題と転送量削減

  • 初期には帯域コストを十分に考慮していなかった
    • Digital Oceanは無料帯域を超えるとGBあたり $0.01 を課金する
    • 以前の作業で1TBの無料帯域があり、OMCBが大きな影響を与えるとは見ていなかった
  • 全状態スナップショットは帯域を急速に消費し得た
    • 100万ビットは1Mbit
    • 30秒ごとに1,000人へ送ると、1分あたり約2GB、1時間あたり120GB規模になる
    • これはincremental updateを考慮しない数値である
  • 帯域確認とコスト上限設定はnginxボックス側で行った
    • ip -s link show dev eth0 で送信バイト数を確認した
    • 単一のnginxリバースプロキシを使っていたため、帯域の発生源を推定しやすかった
  • 転送量削減は2方向で進めた
    • 全状態スナップショットの頻度を下げた
    • incremental updateのフォーマットを小さくした
  • バッチ更新フォーマットは大幅に圧縮された
    • 以前のフォーマットは { "index": 123, "value": true } のようなdictの一覧だった
    • 最終フォーマットはtrueのindex配列とfalseのindex配列の組である [[123, 125], [124]] だった
    • この方式は元の実装より 5倍短かった
  • Linux tc でハードキャップをかけ、コスト暴走を防いだ
    • public interfaceである eth0 のトラフィックを 250Mbit/s に制限した
    • これはおよそ1分あたり2GB、1日で3TB弱に相当する
    • GBあたり $0.01 の前提で、一晩でコストが制御不能に膨らむ事態を避けられた

2日目: 入力検証漏れとRedis replica

  • 翌朝サイトはダウンしており、原因は 入力検証漏れ だった
    • 100万を超えるインデックスのチェックボックスを防いでいなかった
    • 誰かが数億単位のインデックスのチェックボックスを操作した
    • その結果、チェック済みボックス数が100万に達したように見え、サイトが終了したと判断されてしまった
  • Redisデータも不要に膨らんだ
    • 100万番目のbitと1億番目のbitの間に数百万個の 0 が追加された
    • クライアントへ送るデータが100倍になった
  • 復旧は迅速に進んだ
    • nginxを停止した
    • 既存bitsetの先頭100万bitだけを新しいbitsetへコピーした
    • 既存bitsetはデバッグ用に保存した
    • コードが新しいbitsetを参照するよう変更し、入力検証を追加した
  • 初期ページロードも遅くなっていた
    • Redis負荷が高く、connection poolのバグで接続も過剰に作られていた
    • connection pool問題をデバッグする代わりにRedis replicaを追加し、primaryの負荷と接続を分散した
  • replicaのprivate IPは手動で探す必要があった
    • Digital Oceanの案内どおりpublic DNSでは replica- prefixが機能したが、private DNSでは機能しなかった
    • public IPを使うとpublic internet経由と帯域課金のリスクがあると考えた
    • primaryや他サーバーのprivate IP近辺のアドレスへ接続を試し、3回目か4回目の試行でreplicaのprivate IPを見つけた
    • その後そのIPをhardcodeした

プロセス再起動とstale update修正

  • Flaskプロセスはその後もクラッシュし続け、原因はRedis接続不足に見えた
    • 詳細なデバッグの代わりに、実行中のFlaskプロセス数を確認するbashスクリプトを作成した
    • 実行中プロセスが3未満ならsystemd unitを再起動した
    • スクリプトはcrontabに入れた
  • nginx設定も合わせて調整された
    • ダウンしたサーバーは一時的にrotationから外すよう変更した
    • この変更後、サイトは安定化した
  • クライアント状態同期には stale update バグがあった
    • クライアントはincremental updateとfull-state snapshotの両方を受け取っていた
    • 2種類の更新にtimestampがなかったため、新しいsnapshotを受け取った後で古いincremental updateを適用してしまうことがあった
    • その結果、次のfull-state snapshotまで完全に誤った状態を表示することがあった
  • timestampベースの緩和策が追加された
    • full-state snapshotにtimestampを付けた
    • Redis pubsubに書き込む各updateにもtimestampを付けた
    • クライアントへ送るbatchには、含まれるincremental updateのうち最大のtimestampを入れた
    • クライアントは最後のfull-state snapshotより古いbatchを捨てるようになった
  • この解決策は完全ではなかった
    • batch内に新しいupdateが1つでもあれば、大半が古いupdateでも適用され得た
    • それでも以前よりは大幅に改善した

Goへの書き直しと安定化

  • 翌朝にはサイトは生きており、その後はバックエンドの書き直しに集中した
    • Washington Postからメールも届いていた
    • サイトをどう終わらせるかという計画も同時に考えていた
  • 終了計画は、チェック済みボックスがすぐに解除されなければ凍結するという方式だった
    • この変更は活動の急増と追加サーバー作業を引き起こす可能性があった
    • 既存のFlaskベース構成で耐えられるか確信が持てなかった
  • 友人のEliotとともにバックエンドを Go で書き直した
    • 日曜の2 PMから2 AMまで実装を議論し、バックエンド全体を移植した
    • 構造は大きく変えずに移した
    • 最新プロトコルをサポートするGoの socketio ライブラリ探しのような部分が障害になった
  • 性能向上は非常に大きかった
    • あまりにうまくスケールしたため、ボットが過剰なトラフィックを流し込めるようになった
    • より良いrate limitが必要になった
  • 日曜夜にはDDoSもあった
    • サイトをCloudflareの背後に置き、nginx設定を少し変えて対応した

サイト終了ロジック

  • Goへの書き直し後、サイトは安定して動作した
    • その後1週間はインタビューと注目への対応を続けた
    • その後サイト終了作業に入った
  • 終了方式はチェックボックスの凍結だった
    • チェック済みボックスがすばやく解除されなければfrozen状態になった
    • 時間が経つとサイト全体が完全にfrozen状態になった
  • Redisには追加状態が入った
    • 各チェックボックスが最後にチェックされた時刻を保存するhashtableを追加した
    • クライアントへ渡すには大きすぎる状態だが、Redisに保存するには問題なかった
    • time_to_freeze の値も保存した
  • uncheck時点で凍結可否を判定した
    • now - last_checked > time_to_freeze ならuncheckしなかった
    • 代わりに frozen_bitset を更新し、そのチェックボックスがfrozen状態であることを示した
    • frozen_bitset はchecked状態と同じ方式でクライアントへ配信された
    • クライアントはfrozen bitが立ったチェックボックスを無効化した
  • 誰もuncheckしなくても凍結が進むよう別作業を追加した
    • 定期的に、凍結されるべきだがまだ表示されていないbitを見つけてfrozen状態にした
    • Redis Luaスクリプトに関連ロジックを入れ、原子的に実行した
    • race conditionを避けやすかった
  • 終了変更は公開から2週間と1日後に適用された
    • 2024年7月11日米東部時間4:35 PMにbox 491915がチェックされ、サイトは幕を閉じた

コストと学び

  • サイト運営コストは約 $850 だった
    • donationはこの費用にかなり近い水準だった
    • 大きな損失ではなかったとまとめている
  • Redisとnginxの選択には満足していた
    • Redisとnginxを非常に有用な技術と評価している
    • 自前で運用したことでデバッグと修正がしやすかった
    • ただしmanaged Redisインスタンスを完全には制御できない点はやや不便だった
  • 最初から大規模スケールを長く設計しなかった判断は前向きに評価された
    • インターネットで何が当たるか予測するのは難しいと見ている
    • 最初から数週間スケールを考えていたら公開できなかった可能性がある
    • 多くのユーザーが来たことが、保守の動機と優先順位付けに役立った
  • 制限された匿名的相互作用への需要も確認された
    • 見知らぬ人と限定的な形で相互作用するサイトに人々が関心を示した
    • この種のサイトを今後も作っていく自信が高まった

関連記事

1件のコメント

 
GN⁺ 2024-07-28
Hacker Newsのコメント

  • 分散システムの歴史的知見とともに、学ぶ点の多い記事だった。
    ストレージを除けば、ほぼあらゆる種類の停止や障害点を経験したようで、その解決過程を見られたのがよかった。
    RedisがLuaをサポートしているとは知らなかったが、これを見ると代替の状態ストアとして使ってみたくなる。
    帯域幅はクラウドサービスで最大級の不満の一つだ。課金超過を防ぐハードリミットがないからだ。

    • ストレージも退屈な形では経験した。logrotateの設定がうまくできておらずディスクがほぼいっぱいになり、box-checkログをRedisに送っていたため、Redisが破裂しないよう古いログをディスクへ退避する仕組みを作る必要があった。
      ただ、どちらも大きな問題ではなく、ストレージが意味のある問題にならなかったプロジェクトというのはかなり不思議だった。個人的には新しい経験だった。
      帯域幅は本当に厄介だった。2日ほどずっと緊張しながらNICの送信バイト数を確認し、計算をやり直していたし、ハードキャップがないことが怖かった。Digital Oceanは比較的良心的な価格なのに、それでもそうだった。
      人気のあるサーバーレスサービスは使ったことがないが、そこでは帯域幅コストをかなり強く食らうものだと理解している。
      そしてRedis内のLuaは本当に強力で、多少の性能低下を受け入れられるなら、難しく競合状態の多い問題をかなり回避でき、作業していて楽しかった。

  • 素晴らしい記事だったし、Webサイトも称賛に値する。
    ただ個人的には、この書かれた記事こそが最も誇るべき部分だと思う。

    • ローンチ前にサイトを作るのに使った時間より、記事を書くのにずっと多くの時間を使ったので、それがかなり笑えると思った。

  • 「スケーラビリティをほとんど気にせず、2日でサイトを作ったのは良い選択だった」という部分が核心だと思う。
    特にキャリア初期のエンジニアが学ぶべき点だ。スケーラビリティは問題になるまでは問題ではない。
    問題になった時点では、むしろ良い問題であり、思ったほど直すのが難しいわけでもない。

    • 「だからシステムをシンプルかつ基本的なままに保て」という点まであわせて受け止めた場合にだけ正しい。
      スケールやチーム分割のためではなく、開発者が単にそうしたかったからという理由で、マイクロサービスが「明白な選択」になったシステムをたくさん見てきた。
      そういうシステムをスケールさせるのは本当に苦行だ。

  • 最近の関連記事: One Million Checkboxes - https://news.ycombinator.com/item?id=40800869 - 2024年6月、コメント305件

  • こういうプロジェクトは面白い。
    約6年前にAndroidでPixmapをリリースした。1024x1024のような大きめのグリッドをサポートする、小さな共同ピクセル編集アプリだった。
    各イベントをPNG画像に適用するキューを用意し、クライアントは接続時に初期PNGをロードした後、各ピクセル描画イベントについては小さなオブジェクトを1つ受け取るだけにした。
    こうすると初期ロードでは画像圧縮を活用でき、その後の変更セットは非常に小さくなる。また、すべてのイベントがログに保存されるので、画像を「巻き戻す」こともできる [0]。
    [0] 22mb: https://blog.winricklabs.com/images/pixmap-rewind-demo.gif

    • いいね。複数のWebクライアントにピクセル単位の更新を送る似たようなアイデアを検討したが、自分がやろうとしていた方法では帯域幅とストレージを使いすぎそうだった。
      それで今は、API呼び出しでアドレス指定できるキャンバスをいじっている。
      https://x.com/RussTheMagic/status/1816749136487588311

  • 良い記事だった。最終的に費用がいくらかかったのかが気になる。

    • これは含めるべきだった。
      総費用は約850ドルで、寄付でほぼ相殺された。
      Goへ移行した後にインフラをきちんと落とさないミスをしたし、追加で立てた2つ目のRedisレプリカもなくせたはずだった。費用に集中していれば半分にできたと思う。
      ただ寄付が費用をほぼ賄ってくれていたし、ほかにやることが多すぎたので、そこにはあまり集中しなかった。
      サイトを終了した後もグラフ作成などのためにインフラをしばらく維持したので少し余分にお金がかかり、今はやや赤字だが大きな額ではない。

  • バックエンドを学び始めた立場として、このプロジェクトにもっと単純な代替アーキテクチャがあるのか気になる。
    100万個のビット状態をホストしてクライアントと同期する、もっと簡単な方法があればいいのだが。記事中の一部の解決策は理解しにくかった。
    作者のプロジェクトは素晴らしい。

    • 記事の一部が難しかったなら申し訳ない。
      使った技術をもっと長く説明したかったが、記事がすでに長すぎてこれ以上入れるのは難しいと感じた。
      質問があれば喜んで答える。
      正直、アーキテクチャを大きくさらに単純化する方法はよく分からない。こういう用途に使えるサービスはあるだろうが、それは複雑さを誰か別の人に押し付けるのに近いと思う。
      結局必要なのは、チェックされたボックスを追跡するデータベース、データをデータベースに入れる方法、現在の状態をクライアントに知らせる方法、クライアントがボックスをチェックしたときにサーバーへ知らせて状態を更新する方法、ボックスがチェックまたは解除されたときにクライアントへ知らせる方法、そして常に100万個のDOM要素をレンダリングしない方法だ。
      ここではRedisでチェック状態を保存し、単純さのために100万ビットをそのまま保存し、クライアントには100万ビット全体を送った。データがそれほど大きくなかったのがよかった。
      FlaskとWebSocketでチェックイベントと更新を処理し、個別ボックスの更新と100万ボックス全体の更新の両方を送り、react-windowでレンダリング問題を避けた。
      残りのnginxの静的コンテンツとリバースプロキシは主にスケールを容易にするための仕組みなので、その細部がなくても実装は可能で、サイトも動作する。ただし同じ負荷には耐えられない。
    • 記事に出てくるすべてを単一プロセスに押し込むこともできる。
      データベースの代わりにビット集合をファイルに保存してmmapすればよい。リバースプロキシの代わりに、アプリケーションでHTTPリクエストとWebSocket接続を直接処理することもできる。
    • 正直、この程度ならほぼ最も単純な部類だ。
      キャッシュとpublish/subscribeキューを背後に置いたWebサーバー数台という構成だ。
      大きなホスト1台ですべてをメモリ内で処理することもできただろうが、需要に追いつけなかったり何らかの理由で失敗したりすると完全に詰む。
    • 正直、これよりずっと単純にするのは難しいと思う。
      バックエンドAPIと同じプロセス内に100万個のブール値のグローバルリストを置くような、スケールしない方法くらいを除けば、だが。
    • 同じ状態を持つチェックボックスのブロック全体を(checked, start_x, start_y, end_x, end_y)タプルとして要約するように四分木を使えばいい。ごく当たり前の方法ではないか。

  • 素晴らしい。
    次の記事は、どのチェックボックスが最も少なく、または最も多くチェックされたかについての統計分析になるのか気になる。
    かなり下までスクロールして選んだチェックボックスがほぼ即座に解除されて、少し悲しかった記憶がある。

    • 近いうちに生データを共有する予定だ。
      その前に、このサイトについてもう一つ話しておくべきことがある。

  • ゲームがまだ生きているのか気になる。
    https://onemillioncheckboxes.com/にアクセスすると何もチェックされておらず、JSコンソールにはこれだけが表示される。
    {"total":0,"totalGold":0,"totalRed":0,"totalGreen":0,"totalPurple":0,"totalOrange":0,"recentlyChecked":false}

    • 原文によると「2週間後にサイトを終了する前に6億5000万を超えた」とある。

  • スケーラブルな実装の正反対の例として、1000文字未満の100万チェックボックス実装がある。Deno版だ。
    https://gist.github.com/jeff-hykin/4cdebafd8698298d021f103e2...