本連載は分散型マイクロブログ用ソフトウェアMisskeyの開発に関する紹介と、関連するWeb技術について解説を行っています。

Misskeyでは、新機能の追加や改修・バグ修正はもちろんですが、運営者がより少ないコストでサーバーを維持できるよう、Misskeyのスケーラビリティ改善も継続して行っています。

今回はそういった最近のMisskeyのパフォーマンス改善の取り組みについて紹介します。

Fan-out Timeline

Misskey v2023.10.0[1]では、以前より検討を重ねていた、タイムラインのアーキテクチャをPull型からPush型に変更する改修を行いました。

従来のPull型の場合、ユーザーが投稿を行うとデータベースの投稿テーブルに投稿レコードが挿入され、タイムラインを取得する際はデータベースに都度クエリを発行するという一般的かつシンプルな処理になります。

この場合、投稿作成時（write）のパフォーマンスは、基本的に単にレコードを一つ挿入するだけですから大した負荷はかかりません。

しかし、タイムライン読み取り時（read）のパフォーマンスにおいては、投稿テーブルが肥大化（数億レコード規模）してくるとインデックスがメモリに載りきらないことも珍しくなく、相対的に負荷が高くなってきます。

特に、フォローしているユーザーが少なく、タイムラインを埋めるための投稿がなかなかデータベースに見つからないようなシチュエーションだと負荷が顕著に高まります。

そこで、投稿テーブルのスキャンの必要性をなくしてパフォーマンスを向上させようというのがPush型タイムラインの発想です。

Push型タイムラインはFan-out Timelineとも呼ばれ、ユーザーが投稿を行うと、投稿テーブルにレコードも挿入するのですが同時にフォロワー全員のタイムラインにも投稿を追加するというアーキテクチャです。X（旧Twitter）でもこの方式が採用されています。

「フォロワーのタイムライン」はRedis上にリストとして持っておき、タイムライン取得の際はデータベースではなくこのRedisにある自分のタイムラインリストを取得しにいきます。

投稿されるたびに休眠ユーザー、およびリモートユーザー除くすべてのフォロワーのタイムラインに対して投稿の追加処理が発生するため、投稿時の負荷は高まりますが、MisskeyのようなSNSにおける負荷は：
「⁠投稿が作成される数 <<< タイムラインが読み込まれる数」
であり、圧倒的にWriteよりReadのほうが実行される数が多いです。

そのため、Writeのパフォーマンスが悪化してもReadのパフォーマンスが改善するのであれば大きな価値があります。

このPush型タイムラインの実装は、Redisにタイムラインがキャッシュされていなかった場合のデータベースへのフォールバック処理、タイムラインが肥大化しないようにするトリム処理、write時の負荷低減のため休眠ユーザーの判定を行い、当該ユーザーには配信をスキップする処理など、考慮すべきことが多いです。比較的難しい作業でしたが無事リリースすることができ、実際に「フォローしているユーザーが少ない」シチュエーションでも大幅にパフォーマンスが向上しています。

この場を借りて、ベータテストに参加してくださったサーバー管理者の皆様、利用者の皆様に改めて感謝申し上げます。

MFMパース処理の削減

Misskeyでは投稿本文はMFM（Markup Language for Misskey）であると解釈され、様々な構文を使用することが可能です。

しかしそのために必要なMFMのパース（構文解析）処理は比較的高価で、タイムラインの取得などで同時に大量に実行されるとパフォーマンスへの影響が無視できないものになってきました。

そこでv2023.11.0では、一度解析した結果を使いまわせるところは使いまわして無駄なパースを避けたり、nyaize（投稿内容の「な」が「にゃ」に変換されるジョーク機能）をサーバーサイドではなくクライアントサイドで行うようにするなどの改修を行いパフォーマンスを向上させました。

nyaizeに関してはもともとユーザーを困らせることが目的のひとつとして実装されたものです。今回処理をサーバーサイドからクライアントサイドに移すことでnyaize処理を迂回することが可能になり「ユーザーを困らせることができなくなるのではないか」との懸念の声も挙がりましたが、苦渋の決断でパフォーマンスを優先することとしました。

ハイライトシステム刷新

Misskeyにはハイライトという機能があります。簡単に言うと最近の人気の投稿（バズった投稿）を一覧で見ることのできる機能です。

今までの実装方法は、まず投稿レコードごとにスコアというカラムを持っておき、リアクションやリノートが行われた際に当該投稿のスコアを1加算するなどして、「⁠どれだけ人気か」という投稿ごとの値を保存します。

そしてハイライト取得の際は、取得する期間を絞った上で、その範囲内の投稿に対してスコアで降順にソートを行い、上位にある投稿を切り出してハイライトとして提供するという愚直な実装でした。

この方法の問題点は、投稿の数が多いとそれに比例してソートの負荷が高くなることです。

また、似たような機能にハッシュタグトレンドという直近で人気のハッシュタグを一覧できる機能もあり、こちらも投稿数が多い場合負荷が高いことが以前から問題になっていました。

そこで、それら人気のものを集計するシステムを統合し、データベースを酷使する実装ではなく、Redisを活用することでパフォーマンスを大幅に向上させる改修をv2023.10.0で行いました。

具体的には、RedisのSorted Setと呼ばれるデータ構造を利用し、投稿IDとそのスコアの組をメモリ上に保持しておきます（Misskey実装内ではランキングと呼びます⁠）⁠。

このランキングを用いるとスコアによるソートが非常に高速に行えるため、データベースに負担がかからずパフォーマンスが向上します。

さらに、スコアを変動させるべきイベントが発生した際、従来は律儀にどんな場合でも加算もしくは減算処理を行っていましたが、これをサンプリングするようにし、一定の確率でスコアの変動処理が行われるように変更しました。これによりスコアの操作回数を減らせるため、負荷の低減になります。

サンプリングをしたとしても、人気になるような投稿であれば「スコア変動イベント」は非常に多く発生しますので、非サンプリング時と比較しても統計的に誤差の範囲にとどまります。

また、ランキングはそのままだと無限に肥大化してしまいますし、過去の投稿が延々とランキングに載り続けてしまいますので、定期的にリセットする必要が生じます。

しかし、単にリセットするとリセット直後にハイライトを取得した場合、十分なデータが蓄積されていませんので結果が不正確なものになってしまいます。

そこで、ランキングは「今期」「⁠前期」「⁠それ以前」のように何種類か持っておき、徐々に古いものから削除していくようにしました。リセット直後はまだ残っている前期のデータと“⁠攪拌⁠”することで結果の精度を担保する仕組みにしています。

ハイライトシステムが軽量になったことで、ユーザーごとのハイライト機能などの新機能の実装も行うことができました。

ハッシュタグトレンド（チャート）

ハッシュタグトレンド機能もRedisを活用した実装に統合されたことは説明しましたが、ハッシュタグトレンドについては実はもう一つ負荷の高い処理があります。

それはハッシュタグの使用状況をグラフ（チャート）で表示できる機能です。このチャートを取得する処理が非常にデータベース負荷の高いものとなっていました。

そこでチャート表示機能に関しても、Redisを活用することで大幅にパフォーマンスを向上させる改修をv2023.10.0で行いました。

具体的には、Redisに標準実装されているHyperLogLogと呼ばれる確率的データ構造（アルゴリズム）を活用し、データベースをスキャンしなくてもある時間の地点でどれだけそのハッシュタグが使われたかという情報を高速に取得できるようにしました。

HyperLogLogに関しては数学的な話になりますのでここでは詳しく解説しませんが、簡単に言うと一定のメモリ使用量で集合内の要素数をカウントできるものになります。

ハッシュタグは、トレンドの精度を高めるため同じユーザーが何回そのハッシュタグを使ったとしても「使われた数」は1としてカウントしたいため、単に使われた数を数値として持っておくのでは不十分です。つまり、「⁠使ったユーザー一覧」を持っておく（そして、既にその一覧に含まれているなら新たに追加はしない）必要があります。

しかし、愚直にハッシュタグごとに「使ったユーザー一覧」を保持しておくと、ユーザー数の多さに比例してメモリ使用量も増えてしまいます。

そこでHyperLogLogが活躍します。HyperLogLogではメモリ使用量を増やすことなく、一覧内にユーザーを追加していくことが可能です。魔法のように聞こえますが、実際には「確率的」アルゴリズムなので、精度は犠牲になっており、正確な結果を得られないというトレードオフになります。

Misskeyの場合、「⁠ある時点でどれだけ使われたか」という数はチャートの生成においては厳密さが求められず、多少誤差があっても何ら問題は発生しないのでこの欠点は無視できます。

このように、「⁠正確な結果が得られるとは限らない」確率的アルゴリズムを利用することで、ある程度の精度を犠牲にする代わりにパフォーマンスを大幅に向上させられる場合があります。

HyperLogLog の他にはBloom Filterといったアルゴリズムがあり、Misskeyでも活用できる場所がないか検討しています。

リアクションキャッシュ

リアクション機能はMisskeyの大きな特徴のひとつですが、Xのような「いいね」だけのシステムに比べるとどうしても負荷は高くなります。

タイムラインを取得する際は、取得したすべての投稿に対して「自分がその投稿にリアクションしたことがあるか（そしてしたことがあるならばどのリアクションか⁠）⁠」という情報も取得する必要が生じます。

リアクションは下手すると投稿よりも多い数がデータベースにレコードとして作成されますので、投稿ひとつひとつに対して自分のリアクションを取得するのはパフォーマンスに影響してきます。

そこで、統計的にMisskeyにある投稿のうちほとんどはリアクションが全くないか、あっても10個以下にとどまる（つまり、「⁠バズった」投稿は全体から見ればわずかである）ことに着目し、デフォルトで最大16個「誰がどのリアクションをしたか」という情報を直接投稿レコード内にキャッシュとして埋め込むようにする実装をv2023.10.2で行いました。

こうすることで、投稿を取得した際にその投稿へのリアクション数が16以下であれば、データベースに追加で問い合わせずとも自分がその投稿にリアクションしているか、そしてしているならば何のリアクションかという情報を得ることができます。

筆者のタイムラインでは、体感的に90%以上のケースで取得した投稿のリアクション数がそれ以下なので、ほとんどのケースでデータベースへのクエリ発行の必要性がなくなりパフォーマンスを向上させることに成功しました。

まとめ

今回は最近のMisskeyのパフォーマンス改善の取り組みを紹介しました。

Redisを上手く活用することで、従来のデータベースでは負荷の高い処理も高速に行うことが可能です。Redisでは操作ごとにどれくらいの計算量なのかという情報がドキュメントに記載されていますので、そこに注目して利用すると良いでしょう。

コンピュータに例えると、データーベースはCPUでRedisはGPUだと思っています。データベースはCPUのように、オールマイティに様々な処理を行えますが、速度は遅くなります。一方RedisはGPUのように、できる処理が限られますがその分高速です。

また、確率的なアルゴリズムやサンプリング処理を行うことで、精度を犠牲にする代わりにパフォーマンスを向上できるケースもあることを紹介しました。高い精度が必要ないユースケースではそれらの手法を取り入れることを検討してみてください。

ここで紹介した以外にも、細かなパフォーマンス改善は常に行っています。

今後もMisskeyのパフォーマンス改善について特筆すべきものがあれば紹介していきたいと思います。