- Discordはメッセージ保存量が数十億件から数兆件へと増加する中で、2022年初頭には177ノードのCassandraクラスターの運用負荷と予測しづらいレイテンシをもはや支えきれなくなっていた
channel_idと時間バケット中心のCassandra設計は、大規模サーバーに集中する読み取りトラフィックでホットパーティションを生み、quorum読み取り・書き込みのためレイテンシがより広範なユーザー影響へ波及した- APIとデータベースの間にRustベースのデータサービスを置き、同じ行への同時リクエストを統合し、チャネルIDベースの一貫性ハッシュルーティングでデータベース負荷を下げた
- ScyllaDBへの移行は新しいクラスター構成とRustマイグレーターで進められ、Sparkベースでは3か月と見積もられていた作業を9日程度まで短縮し、最大毎秒320万件のメッセージを移行した
- 2022年5月の移行後、ノード数は177台のCassandraから72台のScyllaDBへ減少し、過去メッセージ参照のp99は40〜125msから15msへ、メッセージ挿入のp99は5〜70msから5msへ改善した
Cassandraで増大した運用負荷
- Discordは2017年に数十億件のメッセージを保存する方法を公開し、MongoDBからCassandraへ移行した過程を共有していた
- 当時の目標は、スケーラブルで障害に強く、比較的保守の少ないデータベースだったが、保存量の増加とともにCassandraクラスター自体が大きな運用負荷になった
- メッセージ保存用の
cassandra-messagesクラスターは、2017年の12ノードから2022年初頭には177ノードまで増え、数兆件のメッセージを保存していた
- 運用チームはデータベース問題で頻繁に呼び出され、レイテンシは予測しづらく、コストの大きすぎる保守作業を減らす必要があった
メッセージスキーマとホットパーティション
- 単純化したメッセージスキーマには
channel_id、bucket、message_id、author_id、contentが含まれ、主キーは((channel_id, bucket), message_id)だった
- DiscordのIDはSnowflakeベースのため時系列順に並べられ、メッセージはチャネルと静的な時間ウィンドウであるbucketでパーティション化されていた
- Cassandraでは、特定のチャネルとbucketの全メッセージがまとめて保存され、レプリケーション係数に応じて複数ノードへ複製される
- 小規模なフレンドグループのサーバーと数十万人規模のサーバーではメッセージ量に桁違いの差があり、この差がパーティション単位の負荷差につながっていた
- 書き込みはコミットログとメモリ構造であるmemtableにappendされた後ディスクへflushされるが、読み取りはmemtableと複数のSSTableを参照しうるため、コストがより高かった
- 大規模サーバーで同時読み取りが集中すると特定パーティションがホットパーティションとなり、そのノードのレイテンシが増加し、他のクエリにも影響した
- 読み取りと書き込みにquorum consistency levelを使っていたため、ホットパーティションを担当するノードのレイテンシ増加はより広いユーザー影響へと波及した
Cassandra保守のボトルネック
- Cassandraのcompactionも、繰り返し発生する障害対応の原因になっていた
- SSTableをディスク上でcompactすると読み取り性能が向上するが、compactionが滞ると読み取りコストが増大する
- ノードがcompactionを実行している間、レイテンシが連鎖的に増加することがあった
- Discordは「gossip dance」と呼ぶ作業を頻繁に行っていた
- ノードをトラフィックから外してcompactionを進める
- 再投入してCassandraのhinted handoffによるhintを追いつかせる
- compaction backlogがなくなるまでこの過程を繰り返す
- JVMガベージコレクタとheap設定のチューニングにも多くの時間を要し、GC pauseは大きなレイテンシスパイクを生んでいた
ScyllaDBへ移行した理由
- Discordはメッセージ以外にも複数のCassandraクラスターを運用しており、各クラスターで似た問題が発生していた
- 以前の記事で関心を示していたScyllaDBは、Cassandra互換のデータベースでC++で書かれており、より高い性能、高速なrepair、shard-per-coreアーキテクチャに基づくワークロード分離、ガベージコレクションのない構造を提供していた
- ScyllaDBにも問題がまったくないわけではなかったが、JavaではなくC++で書かれていてガベージコレクタがない点は、Cassandraの運用課題と直接的な対比をなしていた
- 実験とテストで改善を確認した後、DiscordはすべてのデータベースをScyllaDBへ移行することを決め、2020年までに
cassandra-messagesを除くすべてのデータベースを移行した
- メッセージクラスターは数兆件のメッセージと約200ノードを抱える巨大クラスターだったため、最後まで残った
- ScyllaDBの逆方向クエリ性能は初期テストで要件を満たしていなかった
- 逆方向クエリとは、テーブルのソート順と逆向きにスキャンするケースで、例としてメッセージを昇順でスキャンする処理がある
- ScyllaDBチームが性能改善を優先実装したことで、最後のデータベース移行を妨げていた要因が取り除かれた
Rustベースのデータサービス
- Discordはデータベースを置き換えるだけでは、すべての問題が自動的に解決するわけではないと考え、データベース上位層もあわせて変更した
- APIモノリスとデータベースクラスターの間にデータサービスを置き、データベースへ向かう同時リクエストを制御した
- データサービスはRustで書かれている
- Discordは以前からいくつかのプロジェクトでRustを使っていた
- Rustは安全性を犠牲にせずC/C++並みの速度を提供する
- Tokio ecosystemは非同期I/Oシステム構築の基盤として使われ、CassandraとScyllaDBのドライバ対応もあった
- データサービスはデータベースクエリごとにおおむね1つのgRPCエンドポイントを持ち、意図的にビジネスロジックは含めない
- 中核はリクエスト統合にある
- 複数のユーザーが同時に同じrowを要求しても、データベース参照は1回だけ行われる
- 最初のリクエストがサービス内でworker taskを作成し、後続リクエストはそのtaskの存在を確認して購読する
- worker taskがデータベースを参照し、結果のrowをすべての購読者へ返す
ルーティングで統合効果を高める
- データサービスの前段には一貫性ハッシュベースのルーティングを適用した
- 各データサービスリクエストにはrouting keyが与えられ、メッセージではrouting keyはチャネルIDになる
- 同じチャネルのすべてのリクエストが同じサービスインスタンスへ送られるため、リクエスト統合がよりよく機能する
- たとえば大規模サーバーで
@everyone通知が発生すると、多くのユーザーがアプリを開いて同じメッセージを読み、データベーストラフィックが急増しうる
- 以前の構成ではこうした状況がホットパーティションにつながり、運用チームの呼び出しが必要になることもあったが、データサービスはデータベースへ向かうトラフィックスパイクを大幅に減らした
- この改善でCassandraクラスターのホットパーティションやレイテンシが完全になくなったわけではないが、新しいScyllaDBクラスターの準備と移行を進める時間を確保できた
数兆件メッセージの移行
- 移行要件は明確だった
- 数兆件のメッセージを移行しなければならない
- ダウンタイムは許されない
- Cassandraはいまも頻繁な障害対応の原因となっており、素早く終える必要がある
- Discordはまず、super-disk storage topologyを使う新しいScyllaDBクラスターを構成した
- Local SSDで速度を確保する
- RAIDでデータをpersistent diskへミラーリングする
- ローカルディスクの速度とpersistent diskの耐久性を両立する構成だった
- 当初の計画は、cutover timeを境に新しいデータはScyllaDBを使い、過去データは裏で移行する方式だった
- 新しいデータについてはCassandraとScyllaDBへの二重書き込みを開始し、同時にScyllaDBのSpark migratorを準備した
- Spark migratorには多くのチューニングが必要で、設定後の完了見積もりは3か月だった
- その後Discordは既存の高速なデータベースライブラリを拡張し、Rustでデータマイグレーターを書き直した
- データベースからtoken rangeを読む
- SQLiteでローカルcheckpointを記録する
- データをScyllaDBへバルク転送する
- 新しいRustマイグレーターの完了見積もりは9日まで短縮され、この速度により複雑な時間ベース手法ではなく、全体移行を一括で実施できた
切り替えと検証
- マイグレーションは最大毎秒320万件のメッセージの速度で進行した
- 進捗が99.9999%で止まったが、これは最後のいくつかのtoken rangeにCassandraでcompactされていない巨大なtombstone範囲があったためだった
- 該当するtoken rangeをcompactすると、数秒後にマイグレーションは完了した
- Discordは読み取りリクエストのごく一部を両データベースへ送り、結果を比較する方法で自動データ検証を行い、結果に問題はなかった
- ScyllaDBクラスターは本番トラフィック全体でも十分に耐え、Cassandraはますます頻繁なレイテンシ問題を抱えていた
- チームはその場でScyllaDBをprimary databaseへ切り替えた
移行後の性能と規模
- メッセージデータベースの切り替えは2022年5月に行われた
- その後の運用は静かで安定しており、週末を通して障害対応に追われたり、稼働維持のためにクラスターのノードを調整し続けたりする状況はなくなった
- ノード数は177台のCassandraノードから72台のScyllaDBノードへ減少した
- ScyllaDBノードあたりのディスク容量は9TBで、Cassandraノード平均の4TBより大きかった
- tail latencyも大幅に改善した
- 過去メッセージ参照 p99: Cassandra 40〜125ms → ScyllaDB 15ms
- メッセージ挿入 p99: Cassandra 5〜70ms → ScyllaDB 5ms
- 性能改善により、Discordはメッセージデータベースへの信頼をもとに新しい製品ユースケースを開拓できた
World Cupトラフィックで確認された負荷処理
- 2022年末のWorld Cup期間中、世界中のユーザーが試合を見ながら、Discordのメッセージ送信グラフにもゴールの瞬間が現れた
- World Cup Finalのメッセージ送信グラフには、試合イベントに対応する複数のspikeが現れた
- MessiのPKとArgentinaの1-0リード
- Argentinaの追加点
- ハーフタイム中に続いた15分のplateau
- MbappeがFranceのために得点し、90秒後に再び得点して同点にしたspike
- 正規時間終了と延長戦突入
- 延長前半のハーフタイム中のチャット
- Messiの追加点
- Mbappeの同点ゴール
- 延長終了とPK戦突入
- Franceの失敗とArgentinaの優勝
- メッセージ送信量が大幅に増えた状況でも、RustベースのデータサービスとScyllaDBがトラフィックを処理した
- 最終的なシステムは数兆件のメッセージを処理できる構成として整理された
1件のコメント
Hacker News のコメント
この記事は ガベージコレクションを大きく責めているように見えるが、以前の記事 [0] を見ると、Cassandra の使い方や Cassandra による大量削除の処理、あるいはその両方の限界に近いように見える
ユーザーが API で数百万件のメッセージを削除してチャンネルにメッセージを 1 件だけ残し、Cassandra は削除を tombstone として扱うため、ユーザーがそのチャンネルを開くと、実際のメッセージは 1 件だけなのに数百万件の tombstone をスキャンしなければならなかった。その過程で JVM が回収できる速度よりも速くガベージが発生した、という説明
また GC チューニングの話も出てくるが、[1] を見るとそれほど多くチューニングしていたわけでもなく、Cassandra、そしておそらく JVM も古いバージョンを使っていたようだ。ちょうど CMS から移行したばかりだった点も大きい
0) https://discord.com/blog/how-discord-stores-billions-of-messages
もともと解決策の使い方を間違えていたとしても、間違えにくい解決策のほうが良いと思う
2022 年に Java 11 なら 4 年前のランタイム、Java 8 なら 8 年前のランタイムを使っていたことになるので、かなり多くの性能を取り逃していた可能性が高い
Needs (2023)
このサービス層は、大きく派手な分散 Varnish Cache のように見えた。キャッシュに言及せず “coalesce” という言葉を選んでいるのを見ると、実際のキャッシュはあまりしていないようだが、Varnish の “grace mode” と stampede を防ぐ用途、つまり自分が初めて「リクエスト合流（request coalescing）」を聞いた文脈を思い出した https://varnish-cache.org/docs/6.1/users-guide/vcl-grace.htm...
また 一貫性ハッシュが何度も出てくるのも嬉しい。似たような状況で有用性が証明されている、優れたダクトテープのような技術だ。何がどこにあるべきか分かれば、誰もがどこへ探しに来るかも分かる
proxy_cache_use_stale updating;ScyllaDB の共同創業者がいくつか補足している。Discord は Cassandra で repair を完了できなかったが Scylla ではそうではなく、Scylla は LSM ツリーや compaction など Cassandra と共通点が多い一方、独自の CPU/IO スケジューラーによってクエリに compaction より高い優先度を与えられる
アイドル帯域幅が十分にある半ミリ秒に compaction を先送りでき、関連する記事も多いという。Scylla には 1.5 年前に導入された
tombstone_gc=repairという、より安全なモードがあり、最近リリースされた Raft と tablets ベースの新アーキテクチャがユーザーにとって次の大きな変化だというこうした問題は、40年以上前から存在する分散チャットプロトコルであるIRCを使っていれば、そもそも起きなかったはず
公開仕様と複数の実装があるという利点もある。壁で囲まれた庭でもない。IRCが現代では古すぎると思うなら、MatrixやXMPPを見ればいい。Discordがどうやって支配的になったのか理解しがたく、むしろ悲劇に近い
IRCは複数デバイスで会話を追うには、事実上バウンサーを必要とする。メッセージを暗号化せず、任意でクライアントとサーバー間の接続だけを暗号化する。エンドツーエンド暗号化がなければ、サーバーや運用者に対するプライバシーはなく、そのサーバーは狙われやすい単一障害点になる
Matrixプロトコルはまだ変化の途中で、実装は仕様に追いついていない。Elementを使わなければ、機能とセキュリティで遅れを取る。XMPPもIRCと同様、エンドツーエンド暗号化のような基本機能を任意の拡張に依存しており、クライアントがそれを完全かつ正しくサポートしていない場合がある
soatokの分析を読むことを勧める: https://soatok.blog/2024/08/04/against-xmppomemo/ https://soatok.blog/2024/08/14/security-issues-in-matrixs-ol...
2013年のSnowden事件は11年前のこと。今やエンドツーエンド暗号化は基本機能であり、コモディティのように扱われるべきで、HTTPSを求めたときと同じくらい粘り強く要求すべきだ。もちろんDiscordはエンドツーエンド暗号化を実装していない
最近、私が所属する非常に技術寄りのグループがTelegramからMatrixへ移ったが、ユーザー体験は良くない。アプリにはバグがあり見た目もいまいちで、新しい「Element」アプリではSSOがサポートされておらず、アカウントを使えなかった。私のように自分で掘り下げる人間には許容できる小さな不便だが、友人たちに使うよう説得することはできそうにない
exeをダウンロードしてインストールし、アカウントを作ればすぐに動く。誰でもできる。有用で優れたソフトウェアは多いが、その大半は一般大衆には簡単ではなく、一部、あるいは多くはGUIすらない。人々はあまりに多くの手順に耐えるより、自分のアイデンティティを売り、場合によってはお金まで払う方を選ぶ
この記事から私が得た結論は、著者の意図とは少し違うかもしれない
「最後の1つ？ 私たちの友人 cassandra-messages。[…] 最初から大きなクラスターだった。数兆件のメッセージとほぼ200ノードがあったので、どんな移行も複雑な作業にならざるを得なかった。」
Discordの規模を考えると、メッセージストアに200未満のノードというのは驚くほど小さく見える。もっと高速なスケーラビリティを目指し、可動部品の多い複雑なアーキテクチャを予想していた。実際の複雑さは記事に出ているものより高いだろうが、自分がより少ない仕事をする200台超の物理ノードを部分的に担当していた経験を思い出すと、現代のクラウドアーキテクチャがどれほど過剰設計されているのか気になってくる
もっと小さなCassandraノード群で数十億件のレコードを保存したことがある立場から言うと、Cassandraはオンコールでは本当に苦痛な存在で、何度か大きな障害の原因にもなった
[0] https://news.ycombinator.com/item?id=34950843
記事はとてもよく書かれている。解決策の一部がまったく別の何かを導入するのではなく、Cassandraの代替品のように使えるScyllaDBへ切り替えるものだったのはありがたい
Discordは、過去のメッセージを削除することを事実上不可能にしている。プライバシーの悪夢であり、EUがなぜ介入していないのか疑問
核心的な問いは、Matrixをメールに近いものと見るべきか、それともFacebookに近いものと見るべきかに集約される。メールなら、送信者が自分のメッセージを私のメールスプールから削除できるということに人々は仰天するだろうし、Facebookなら、削除権を行使した後でも投稿がどこかに見えているということに人々は仰天するだろう
これを解決するには判断が必要であり、GDPRの精神が実際に何を達成しようとしているのかをまず考慮する形で取り組んだ、という説明だ
https://matrix.org/blog/2018/05/08/gdpr-compliance-in-matrix...
GDPRの観点での問題は、Discordがそれを削除しにくくしていることだ。アカウントデータ削除の意図を検知すると「匿名化」の方向へ誘導し、表向きにはユーザー名がメッセージから切り離されるが、それでも特定の人物として追跡できる。サーバー側でもこのように処理されているなら、ユーザーの個人識別情報削除要求を執行するには、膨大なメッセージを調べるか、過去メッセージを大量削除しなければならない状況になる
EU議会は、新法案を提案できるのが委員会だけで、選挙で選ばれた議会はおおむね採決するだけという点で本物の議会ではなく、委員会を支配しているのは大衆ではなく米国務省だと思う。NewsguardやMuskではない米国ビッグテック、Discordも同じ政治・金融的な既得権ネットワークに属しており、国務省出身者が多い
大衆の怒りがなければ、EUレベルの機関は掌握される可能性が高く、世論も、違法なDiscordデータでLLMを訓練し選挙広告を狙い撃ちするサイバーパンク的な既得権層が支配していると思う。結局、恒久的な既得権から抜け出せないOrwell的な状態が来るかもしれない点を心配すべきだと思う
ただし、この大半は広い意味で正しい確率を50%以上程度としか見ていないので、かなり割り引いて聞くべきだ
Cassandraは本質的に、ほとんど追記のみの分散フォールトトレラントなハッシュテーブルに近い。高い書き込みスループットでまさにそれが必要なら良い選択だ
人々がなぜこれをデータベースのように使うのか理解できない。すぐに限界にぶつかり、データベースのように使おうとする苦痛は規模が大きくなるほどさらにひどくなる
これではチャットサーバーのメッセージストアとしては筋が通らないと思う。分散システムのログ収集先、つまり多くのクライアントがデータを流し込むが、ほとんどの場合ログを監査する必要もなく、特定項目の読み取り回数が1未満であるようなケースには適していそうだ。Discordのメッセージは明らかにそうではない
自分の経験では、Cassandraを使い始めたプロジェクトが1年ほど経った後も使い続けているのを見たことがない。限界にぶつかるまでに1年ほどかかり、結局Postgresのようなデータベースに置き換えることになる
なぜ単にシャーディングできないのか分からない。Discordの各「サーバー」は互いに分離されているのではないか？ 相互にメッセージを送れないなら、数兆件のメッセージを数千個のシャードに分け、各シャードが数十億件ずつ処理するようにすればよいのではないかと思う
「ScyllaDBチームは改善作業を優先し、性能の良い逆方向クエリを実装して、移行計画における最後のデータベース上の障害を取り除いた」とある
ScyllaDBを使う前に、これをやってもらうためにいくら支払ったのか気になる