MISONLN41's Blog

怪文書置き場

なぜDiscordはGoからRustへ移行するのか

DiscordがGoで書かれていたコンポーネントをRustに移行しているらしい。Windowsの低レイヤ層の一部で採用されるなど、近年どんどん注目を集めているRustだが、DiscordはなぜRustを選んだのか。その最大の特徴である「パフォーマンスを妨げる要素であるGCを排した上でメモリセーフな言語」であることにクローズアップした面白い内容だったので、えっちらおっちら和訳してみた。英語が得意というわけでもなく、無理やり翻訳しているところも多いのであしからず。ほとんどGoogle翻訳のままというのは内緒。

追記: 7/31にはてブでいっぱいブックマークされたみたい。気になったブコメへの返信を末尾に追記した。

原文: Why Discord is switching from Go to Rust - Discord Blog


Rustは様々な分野において第一級の言語になりつつあります。Discordでは、Rustはクライアントサイドとサーバーサイドにおいて成功を収めました。例えば、クライアントサイドではGo Live向けの動画エンコードパイプライン、サーバーサイドではElixir NIFsです。最近では、実装をGoからRustに変更することでサービスのパフォーマンスを劇的に改善しました。この記事では、なぜサービスを実装し直すことが理にかなっているのか、それがどのように行われたのか、そしてその結果としてのパフォーマンスの改善について説明します。

Read Statesサービス

Discordは製品中心の会社なので、製品のコンテキスト(利用者の意図や状況、環境などの総体)からスタートします。私たちがGoからRustへ移行したサービスは "Read States" サービスです。Read Statesの目的は、あなたが読んだチャンネルとメッセージを追跡することです。Read Statesは、あなたがDiscordにアクセスするたび、メッセージが送信されるたび、メッセージが読まれるたびにアクセスされます。つまり、Read Statesはホットパス(パフォーマンスがとても重要なパス)にあります。私たちはDiscordを常にきびきびとした状態に保ちたいので、Read Statesを高速にする必要があります。

Goの実装では、Read Statesサービスはプロダクトとしての要件をサポートしていませんでした。それはほとんどの時間において高速でしたが、数分毎にUXに悪影響を及ぼす大きな遅延の急上昇が発生していました。調査ののち、その原因はGoのコア機能であるメモリーモデルとガベージコレクタ (GC) にあると判断しました。

Goがパフォーマンス要件を達成しなかった理由

Goがパフォーマンス要件を達成しなかった理由を明らかにするため、はじめにサービスのデータ構造、スケール、アクセスパターン、アーキテクチャについて説明する必要があります。

Discordにおいて、読み取り状態を保存するために使用するデータ構造は"Read State"と呼ばれています。Discordにはそれぞれのチャンネル、ユーザーごとにRead Statesがあり、合計で数億に及びます。それぞれのRead Stateには不可分的(アトミック)に更新する必要のあるいくつかのカウンターがあり、しばしば0にリセットされます。例えば、カウンターの一つはチャンネル内のメンションの数です。カウンターのアップデートを不可分的かつ素早く行うために、それぞれのRead StatesサーバーにはRead StatesのLeast Recently Used (LRU) キャッシュがあり、そこでは毎秒数十万のキャッシュの更新があります。

データの永続化のために、Cassandra Database Clusterを用いてキャッシュをバックアップします。キャッシュキーを削除する場合、Read Statesをデータベースにコミットします。また、Read Statesがアップデートされているかに関わらず30秒ごとにデータベースへのコミットをスケジュールしています。データベースには一秒あたり数万の書き込みがあります。

下図はGoサービスのピーク時のサンプルフレーム*1です。お気付きのように、遅延とCPU使用率の急上昇が約2分毎に発生しています。

f:id:MISONLN41:20200212021158p:plain

2分毎に遅延とCPU使用率が増える理由

Goでキャッシュキーを削除する際、メモリはすぐには解放されません。

その代わり、ガベージコレクタが頻繁に実行され、参照されていないメモリを見つけて解放しています。つまり、メモリが使用されなくなった直後に解放される代わりにガベージコレクタがメモリが本当に使用されていないかを判断するまで、メモリは少しの間ハングアップします。ガベージコレクションの際、Goは様々な作業を行って空きメモリを判断する必要があり、プログラムの速度が低下する恐れがあります。

Goのソースコードを調べていくと、Goは最低2分毎にガベージコレクションを実行することがわかりました。つまり、ヒープの増加とは関係なく、ガベージコレクションが2分以上実行されなかった際にGoはガベージコレクションを強制的に実行しているのです。

私たちはこの遅延の急上昇を改善するため、ガベージコレクションをより頻繁に実行するべきだと考えました。そして、Goサービスにエンドポイントを実装し、ガベージコレクタのGC Percentを直接変更しました。

残念ながら、GC Percentをどのように変更しても何も変わりませんでした。どうしてでしょう?それは、ガベージコレクタ頻繁に実行するのに十分なメモリを割り当てていなかったからでした。

Goのソースコードを調べ続けると、遅延の急上昇が大きい理由がすぐに開放できるメモリが大量にあることではなく、メモリが本当に参照されていないかを判断するためにガベージコレクタがLRUキャッシュ全体をスキャンする必要があるからだとわかりました。したがって、LRUキャッシュを小さくすればガベージコレクタがスキャンするものも減り、ガベージコレクションが早くなると考えました。そこで、Goサービスに別の設定を追加してLRUキャッシュのサイズを変更し、サーバーごとに多数の分割されたLRUキャッシュを持つようにアーキテクチャを変更しました。

これは成功しました。LRUキャッシュを小さくすると、ガベージコレクションは少ない遅延で実行されるようになりました。

残念ながら、LRUキャッシュを小さくしたトレードオフとして、99パーセンタイルの遅延時間を大きくしてしまいました(つまり、遅延の急上昇は抑えられたものの、普段の遅延が大きくなってしまいました)。キャッシュが小さい場合、ユーザーのRead Stateがキャッシュ内にある可能性が低いからです。ユーザーのRead Stateがキャッシュにない場合は、データベースにアクセスする必要があります。

様々なキャッシュのサイズでテストを行った結果、よさげな設定が見つかりました。100%満足というわけではありませんが、十分に満足できるもので、しばらくの間はその設定でサービスを運用していました。

その間、Discordの他の部分においてRustはますます成功を収めており、新しいサービスをRustで構築するために必要なライブラリとフレームワークを作成することをまとめて決定しました。Read Statesサービスは小規模且つ自己完結型であるため、Rustに移植するのにちょうどいい候補でしたが、同時にRustが遅延の急上昇を解決することも期待していました。そこで、Rustがサービス開発に使える言語であることを証明することと、ユーザー体験を向上させることを期待し、Read StatesをRustに移植する作業を始めました。*2

Rustにおけるメモリ管理

Rustは非常に高速かつメモリ効率が良く、ランタイムやガベージコレクタがないため、パフォーマンスが重要なサービスを強化し、組み込みデバイスで動作し、他の言語と簡単に統合できます 。*3

Rustはガベージコレクタがないので、Goのときのような遅延の急上昇は発生しないと考えました。

Rustはメモリに「所有権」という概念を取り入れた、比較的ユニークなメモリ管理のアプローチを採用しています。基本的に、Rustは誰がメモリを読み書きできるのか追跡します。プログラムがいつメモリを使用しているかを認識し、不要になったらすぐにメモリを解放します。Rustはコンパイル時にメモリルールを適用するため、ランタイムのメモリバグを発生させることは事実上不可能です。*4メモリ管理はコンパイラが自動で処理するため、メモリを手動で追跡する必要はありません。

そのため、Rust版のRead Statesでは、ユーザーのRead StateがLRUキャッシュから削除されると直ぐにメモリが解放されます。Read Stateメモリはガベージコレクタが使用されていないメモリを解放するのを待つ必要がありません。Rustはメモリが使用されなくなったら即座にそれを解放します。解放の是非を判断するランタイムプロセスはありません。

RustのAsync

しかし、Rustのエコシステムには問題があります。このサービスをRustで再実装した時点で、安定版のRustは非同期処理に関して不完全でした。ネットワークサービスにおいて非同期プログラミングは必要なものです。非同期処理を有効にした有志のライブラリがありましたが、大量のおまじないコードが必要なうえ、エラーメッセージはとても分かりにくいものでした。

幸いなことに、Rustチームは非同期プログラミングを簡単にすることについて大変に意欲的であり、RustのNightlyチャンネルでは非同期プログラミングが強化されていました。

Discordは、有望そうな新しい技術を採用することを恐れません。例えば、我々はElixir、React、React Native、Scyllaの早期採用者です。技術の一部が有望であり、我々にメリットをもたらすのであれば、先端技術特有の難しさ、不安定性は小さな問題です。これは、50人未満のエンジニアですぐに2億5,000万人以上のユーザーに到達した方法の1つです。

Rust Nightlyの新しいasyncの機能を採用することは、そういった新しい技術を採用することへの意欲の表れの一つです。エンジニアリングチームとして、Rust Nightlyを採用する価値があると判断し、asyncがRustの安定版で完全にサポートされるまでRust Nightlyを使用することを決定しました。同時に我々はRust Nightlyに発生した問題に対処し、そして安定版Rustは非同期処理をサポートしました。*5我々の挑戦は報われました。

実装、負荷テスト、そしてローンチ

コードの書き直しはとても簡単でした。まずはラフな変換から初めて、それからスリム化が理にかなっている部分においてコードのスリム化を行いました。例えば、Rustはジェネリクスへの広いサポートがある素晴らしい型システムがあるため、Goにおいてジェネリクスが不足していたために必要だったコードを削除できます。また、Rustのメモリモデルは複数スレッドに渡ってメモリ安全性を推論できるため、Goで必要だった手動でのcross-goroutineメモリ保護(おそらく複数スレッドをまたいでメモリ安全性を検証するという意味でのcross)が不要になりました。

負荷テストを開始したら、すぐに満足できる結果が出ました。Rust版Read Statesにおける遅延はGoとほぼ同じで、その上Goのような遅延の急上昇はありませんでした!

驚くべきことに、Rust版を実装したときに、私たちは最適化の際にとても基本的な考え方を導入しただけでした。基本的な最適化だけでも、Rust版は手を加えて最適化したGoのそれよりも優れたパフォーマンスを発揮できました。これは、Goで行う必要のある手の込んだ最適化と比較して、Rustがいかに簡単に効率的なプログラムを作成できるのかを示す大きな証拠です。

しかし、我々はただGoのパフォーマンスに並んだだけでは満足しませんでした。プロファイリングとパフォーマンスの最適化を少し行うと、すべてのパフォーマンス測定基準においてGoのパフォーマンスを超えることが出来ました。遅延、CPU使用率、メモリ使用量の全てにおいてです。

Rustのパフォーマンス最適化のためにしたことは、以下の通りです。

  1. メモリ使用量を最適化するために、LRUキャッシュ内のBTreeMapをHashMapに変更した
  2. 内部のMetrics Library(メトリクスが「測定・評価」らしいので、パフォーマンスを測定するライブラリのことだろうか)を最新のRustの並列化を使用したものに変更した
  3. メモリコピーの回数を減少させた

負荷テストを行っていたため、ローンチはとてもシームレスでした。初めに一つのCanary(Chrome Canaryみたいなものだと思う)ノードに展開し、いくつかのエッジケースを見つけて修正しました。その後、すべての環境に向けてロールアウトしました。

結果を下図に示します。

Goが紫のライン、Rustが青色のラインです。

f:id:MISONLN41:20200212220110p:plain

キャッシュ容量を増やす

サービスが数日の間正常に動いた後、LRUキャッシュのサイズを再び増やすことを決定しました。先述の通り、Go版ではLRUキャッシュの容量を増やすとガベージコレクションにかかる時間が長くなります。Rust版ではガベージコレクションをする必要がなくなったため、キャッシュの上限を引き上げてパフォーマンスをさらに向上させることができると考えました。メモリ上限を引き上げ、メモリ使用量を少なくするためデータ構造を最適化し、800万のRead Statesが格納できるまでにキャッシュ容量引き上げました。

結果は以下の通りです。平均時間はマイクロ秒(μs)で、@mentionが最大の時(メンションが最大限の数貯まっている状態?)がミリ秒(ms)です。

f:id:MISONLN41:20200212222126p:plain

進化するエコシステム

最後に、もう一つのRustの素晴らしい点は、どんどん進化していくエコシステムがあることです。最近、tokio(我々が使用しているasyncランタイム)はバージョン0.2がリリースされました。アップグレードすると、それだけでCPUに恩恵がありました。下図の通り、16日以降のCPU使用率が一貫して低くなっています。

f:id:MISONLN41:20200212224919p:plain

おわりに

現時点で、Discordはソフトウェアスタック全体にわたって、様々な場所でRustを使用しています。ゲーム SDK、Go Liveの映像キャプチャとエンコードElixir NIFs、いくつかのバックエンドサービスなどです。

新しいプロジェクトまたはソフトウェアコンポーネントを開発するとき、我々はRustの使用を検討します。もちろん、Rustを使う意味がある場合にのみ利用します。

パフォーマンスに加えて、Rustを採用することはエンジニアリングチームにとって様々な利点があります。例えば、型の安全性と借用チェッカーにより、製品要件の変更やRustに関する新たな知見が発見された際に、コードのリファクタリングが非常に簡単になります。また、Rustのエコシステムとツールは非常に優れており、その背後にはかなりの勢いがあります。ここまで読み進めたあなたは、おそらくRust(を使う利点)にワクワクしていることでしょう。Rustを専門的に使用し、興味深い問題に取り組みたい場合は、ぜひDiscordで働くことを検討してみてください。

また、面白い事実として、RustチームはDiscordを使用して協調(coordinate。おそらくDiscordを用いて連絡を取り合ったり調整をしたりしているという意)しています。非常に役に立つRustコミュニティのサーバーがあり、我々(Discord開発者)も時々ここで話しています。こちらをクリックしてサーバーに参加できます。


ブコメ・コメントありがとう

こういうの初めてなので、ちょっとびっくりした。自分はプログラミングが出来ないので的確な返しは出来ないと思うけど、気になったものにちょっとずつ言及してみる。

budougumi0617 Go1.12(2019/02リリース)でGCは改善されてるので今はもっとマシです(時間軸的に比較当時も存在していたはずだけれど...😢 https://twitter.com/mattn_jp/status/1226772703413071872

恐らく、Rustへの移行を検討しだした時点でのデータなんじゃないかな。

kwhrtsk GCが無いからといって必ずしもRustの方が安定するわけではない点に注意が必要。例えばデータサイズの小さなKVS/gRPCサーバ実装の例ではRustのレイテンシの方が不安定という結果だった。 https://tech-blog.abeja.asia/entry/2020/04/09/1151

適材適所というのかな、規模や用途によって使い分ける必要は確かにありそう。Dropboxの同期エンジンなんかは、かなり慎重な検討の末にRustへの移行を決めたらしい。

j5ik2o Rustはよい言語なんだけど、この記事では人間側のパフォーマンスやオーバーヘッドがどうなるかが書かれていないってことなんだよな…。

Rustの難しさ、ということだろうか。学習曲線がどうこう、という話はよく聞くけれど、実際のところどうなんだろう?よくわからん。

takaBSD もう前から不思議なんだけど、システムプログラミング言語であるRustとInternet上での使用に最適化されてるGoを比較する人が多いのは何故? RustはCとC++を置き換えるための言語だ!

C/C++を置き換えるための言語、ではないと思いますが。それこそWASMとかもありますし。Goと比較されることが多いのは、確かになんでだろうって感じですね。出てきた時期が近いから?

getcha 面倒くさいから全部 C/C++でいいんじゃないと思っている人です。早いし工夫しようと思えばいろいろできるしCに追いつこうとしなくて良いし。GCは設計上のハンデだから速さ求めちゃ行けないと思う。

絶対に安全なプログラムを書ける、優秀なプログラマーならそれでいいのかなと思う。大半の人間はそこまで賢くないんじゃないかな。プログラミングできないので憶測でしかないけれど。

dowhile “99th” percentileが抜けてるのかな?99パーセンタイルの遅延時間を大きくしてしまった。

den8 "higher 99th latency times" たぶん計測されたレイテンシーを最小 ~ 最大で並べたときの99%部分のレイテンシー時間(いわゆる99 percentile)のことかな?

この記事のコメント欄でも指摘を頂いた。ありがとう。

metatrading dropboxPythonからRustへ移行した意味合いとは異なるね。GoからRustはかなり慎重な意思決定が必要だったように思う。

Malan あわせて読みたい https://navi.dropbox.jp/rewriting-the-heart-of-our-sync-engine

これも前に読んだ。Discordの記事が統計情報とかを中心に書いているのに対して、この記事だと「〇〇がつらい」とか、書き換えの哲学みたいなものが沢山書いてあって面白かった。

*1:グラフはGo 1.9.2のものです。1.8、1.9、1.10も試しましたが改善は見られませんでした。GoからRustへの最初に移植は2019年5月に完了しました。

*2:誤解のないように言うと、我々は全てをRustに移植する必要はないと考えています。

*3:https://www.rust-lang.org/より引用

*4:もちろん、unsafeを使用しない場合に限ります。

*5:https://areweasyncyet.rs/