Discordがユーザー当たりの帯域幅を40％も削減した手法を解説

月間アクティブユーザー数が2億人を超える人気チャットアプリ「Discord」の公式ブログにおいて、「どのように使用する帯域幅を削減したのか」について解説した記事が投稿されています。
How Discord Reduced Websocket Traffic by 40%
https://discord.com/blog/how-discord-reduced-websocket-traffic-by-40-percent

Discordのクライアントがサーバーに接続すると、ゲートウェイと名付けられたサービスを通してリアルタイムにさまざまなデータが送受信されます。2017年の後半にzlibを導入してデータを圧縮することで、転送されるデータの量は2分の1から10分の1程度まで減少しました。
その後、Zstandardという2015年に登場した手法が人気を集め、Discordでも使用を検討することになりました。Zstandardはより高い圧縮率と短い処理時間を達成できるだけでなく、辞書がサポートされるため同じ形状のメッセージを多数やりとりするDiscordの使用方法であればより効果的に圧縮できると期待されていました。
Discordの開発チームは理論が現実でも通用することを確かめるため、本番のペイロードを利用してzlibとZstandardの圧縮率の違いを検証しました。下図はZstandardの圧縮率です。

そして下図がzlibの圧縮率。両者ともに最大の圧縮率を達成できた「user_guild_settings_update」という種類のペイロードでzlibが明確に上回ったほか、多数の項目でzlibの方が高い圧縮率を達成できるという結果が出てしまいました。

特に「MESSAGE_CREATE」という種類のペイロードはZstandardの圧縮だとzlibの圧縮よりも3倍以上サイズが大きくなってしまったとのこと。

Zstandardの圧縮率がzlibよりも悪くなる原因を開発チームが調査した結果、zlibではストリーミング圧縮が可能で過去のペイロードから圧縮方法を最適化できていたのに対し、Zstandardではメッセージごとに初期化されていてほとんど履歴を活用できていなかったことが判明しました。
そこでDiscordの開発チームはelixir/erlangのライブラリ「ezstd」をフォークしてストリーミングのサポートを追加。オープンソースの精神にのっとり、アップストリームにもサポートを提供したとのこと。
ストリーミング圧縮を利用したZstandardを使用すると、圧縮率はzlibを大きく上回ることに成功しました。

特に問題だった「MESSAGE_CREATE」のサイズもzlib以下に抑える事に成功。

1バイトあたりの処理時間についても、zlibが約100マイクロ秒かかっていたところをZstandardは約45マイクロ秒まで減少させることができました。

また、辞書を導入することで圧縮率をさらに高める試みも行われました。例えば、サーバー接続が完了した際に送られる「READY」という短いペイロードの場合、辞書を導入すると圧縮率が6.4から6.63へと少し上昇します。「READY」ペイロードは定型文のため辞書の効果を受けやすいはずですが、圧縮率はわずかに上昇するにとどまりました。

その他のペイロードでも確認してみると、辞書は意外と効果がないことが判明。「MESSAGE_CREATE」ペイロードでも辞書を入れたことでデータの量が増加してしまいました。さらなる最適化を重ねれば辞書を使用した方が圧縮率が高まる可能性はあるものの、効果が低いのに実装の複雑性が増してしまうことを嫌い、開発チームは辞書を使用しないことにしたとのこと。

さらに開発チームは日中のユーザーが少ない時間帯に余っているメモリ領域を使用することでさらなる圧縮を試みました。一定以上メモリが余っている場合、Zstandardのメモリ使用量を2倍にアップグレードする仕組みを取り入れたものの、開発チームの想定ほどうまく稼働しませんでした。

開発チームの調査によると、それぞれの接続に対し実際に使用する量よりも多くのメモリが割り当てられており、空きメモリの量が誤って算出されていました。開発チームはメモリ割り当ての最適化に少し取り組んでみたものの、実装の複雑性と期待される効果が釣り合っていないと結論付け、元の割り当て設定に戻したとのこと。
調査中、開発チームはユーザーがしばらく開いていないサーバーの状態を同期するための「passive_update_v1」というペイロードが大きな帯域を占めているのを発見。このペイロードではチャンネルやユーザーなど非アクティブでも同期される情報の1つが更新された際、全てのデータを送信していました。

そこで開発チームは更新の差分のみを送信する「passive_update_v2」を開発。非アクティブサーバーの同期にかかる帯域幅の全体に占める割合が35％から5％まで低下し、全体の帯域も20％削減できました。

Zstandardに加え、「passive_update_v2」を導入したことで、両者を導入する前と比較してDiscordはクライアントごとの帯域幅を平均で約40％削減することができたとのことです。