これについて
Misskeyのチャートエンジンの動作を解説します。(自分自身のための備忘録の意味もあります)
私について
Misskeyの作者です。
チャートとは
Misskeyの様々なデータの変動の推移を記録・表示する機能です。
記録する対象の例:
- 投稿の増減
- ユーザー数の増減
- ドライブの使用量の増減
- 連合しているインスタンスの増減
など
チャートエンジン
チャートエンジンはチャート機能のうち、情報の記録と出力を担当します。表示はクライアントなどがその情報をもとにグラフで表示したりします。チャートエンジンがデータを出力したら、あとは煮るなり焼くなりという感じで、表示には関与しません。
情報の記録
最初に思いつく方法
チャートエンジン無しで、データベースにある実際のデータを集計してチャートを生成するのが一番簡単に思われます。
しかしこの方法では、データベースから物理的に削除されたデータをチャートに反映させることができません。しかもデータ量が多いとパフォーマンスが低下し、実用的ではありません。
次に考えた方法
そこで、情報が変動するたびにその変動を記録(ログ)する方法を考えました。
しかし情報が変動するたびにログを行っていくと、ログの量が膨大になってしまいます。例えば一千万回投稿が行われたら、それに伴って一千万個のログが挿入されることになってしまいます。この方法だと記録の解像度(注1)は無限ですが、データ量は非常に大きくなり、パフォーマンスも悪化するため現実的ではありません。
注1: 記録をどこまで拡大できるか、ということを便宜的にそう呼ぶようにしました。
最終的に考えた方法
そこでMisskeyのチャートエンジンでは、変動ごとにログを挿入していくのではなく、「1時間単位」「1日単位」といったふうにスパンを分けて、そのスパンごとにログを挿入していくという方法を考えました。
例えば、「この時間では投稿が500個増え、トータルで30万個になった」とか、「この日はユーザーが6人増え、トータルで1200人になった」という感じです。
ある程度期間を決めて、その期間ごとの変動を記録していくことで、解像度を犠牲にする代わりにデータ量を抑えられる、ということです。
また、パフォーマンス向上のため、「その時点でのトータル投稿数」などの情報はログ挿入時にその都度集計するのではなく、前のログのデータを利用して算出するようにします。
この方法なら、例え1時間のうちに1000回投稿されてもログは1つしか挿入されないので、データ量は格段に少なくなります。
チャートエンジンはこの方法を使いながら変動を記録していきます。
イメージ:
・2019年3月12日9時0分2秒に新しい投稿がされた
・2019年3月12日9時0分5秒に新しい投稿がされた
・2019年3月12日9時0分6秒に新しい投稿がされた
↓まとめる
・2019年3月12日9時は投稿が3つ増えた
注意点
注意点として、スパンごとにログを挿入するといっても、ログ挿入/更新のタイミングは変動が起こる毎だということです。つまり、「どこかでタイマーみたいなものが動作していて、そのタイマーが1時間または1日経つごとに変動したデータを調べて記録」、ということではないです。
あくまでもデータが変動したときに、その時間または日に合わせて、記録するログを特定して更新(または新規に挿入)するということです。
こういう設計にしたのは、どこかでタイマーを動作させるとズレが生じるかもしれないのと、やはりそのようにすると集計時にデータの量によってはパフォーマンスが悪化するためです。それに並列環境との相性も悪いです。
情報の出力
変動を記録するだけではなく、その記録を出力することもしなければなりません。
「1時間単位で、今から遡って48時間分のデータ」「1日単位で、今から遡って30日分のデータ」というふうにリクエストが来るので、それに従ってデータベースにあるログを集めてまとめて出力する必要があります。
問題点
今説明してきた方法では問題点がいくつかあります。
問題点1
ひとつめは、先述した「あくまでもデータが変動したときにログを挿入/更新する」という方法に起因する問題で、「ログに抜けがある場合がある」という問題です。
詳しい説明
例えば、「1時と3時には投稿があったけど、2時の間には投稿がひとつもされなかった」というケースを考えると、データベースには1時と3時のログはありますが2時のログはありません。
ここで、データ出力の際にただ単にデータベースにあるログを集めてくるだけでは、こういった抜けが発生してしまいます。
したがってチャートエンジン側でこの間を補完(隙間埋め、パディングなどと呼んでます)する処理も必要になります。
「ログが無いってことは、投稿がされていないことは明らかなんだから、その時間は投稿が0だったことにするだけで良いんじゃない？」と思われるかもしれません。たしかに「その時間内で投稿された数」は0ですが、同時に記録している「その時間時点でのトータルの投稿数」といった情報は本来0ではありません。ですから、一律に「ログが無ければその時点の情報は全て0」という処理で済ますことはできません。
問題点2
ふたつめは、先述した「トータル投稿数などの情報は前のログのデータを利用して算出する」という方法に起因する問題で、「実際のデータとズレが生じる場合がある」という問題です。
詳しい説明
Misskeyの利用するリレーショナルデータベースでは、データの依存関係を定義し、「あるデータが削除されたら関係するデータも削除する」という処理を行います。これは例えば、ユーザーのアカウントが削除されたら、そのユーザーが行ったすべての投稿やアップロードしたファイルも自動的に削除される、といったことです。
こういったデータベースによる自動的な削除は、Misskey側で動いているチャートエンジンには感知することができません。したがって、Misskeyによる「自発的」なデータの削除は正しく記録することはできても、データベースによる「自動的」な削除は正しく記録できないことになり、実際のデータとのズレが生じます。前述した仕組み的に、そのズレは一時的なものではなく恒久的で、自然に修正されることもなく、むしろどんどん拡大していきます。
この問題を解決するために、定期的に情報を正しい値に「同期」する処理が必要になってきます。
実装
動作の概念は説明したので、ここからは具体的な実装をかいつまんで説明します。
チャート基底クラス
まずチャートの基本機能を提供するチャート基底クラスChartがあり、投稿チャート、ドライブチャートなどの各チャートがこのクラスを継承します。
派生クラス
例えば投稿チャートはNotesChartといったふうにChartクラスを継承したクラスで表されます。
それぞれの派生チャートクラスは、どういうデータをログとして保存するかのスキーマのようなものを持っていて、基底クラスがそれを利用して実際のログ挿入/更新などを行います。
また、先述の「ログ挿入時は過去のログを利用する」という仕組みのための、「過去のログデータを引き継いだ新たなログデータを生成する」機能や、後述する「ズレ」問題対策のために、正確なデータをデータベースから取得する機能も基底クラスに提供します。
ログの更新と挿入
情報の変動が発生した時はログを更新または挿入しなければなりません。
getCurrentLogメソッドで、更新すべきログをデータベースから取得します。ログがなければ新たに挿入します。
まず現在のスパンに合致するログがすでに存在するか確認します。あればそのログを返して終了します。なければ先述のように新たにログを生成する必要があるので処理を続けます。
新たにログを挿入するためには、そのMisskeyインスタンス初めてのログ挿入時を除き、「前のログデータを利用する」という仕組みのため直近のログを取得する必要があります。
そのために、まず最も最近のログがあれば取得します。「1時間前」とか「1日前」ではなく「最も最近の」とするのは、例えば昨日何もチャートを更新するような出来事がなかった場合にはそもそもログが存在しないためです。
その過去のログがあった場合は、派生クラスで実装されているgetNewLogメソッドにそのログを渡して現時点でのログにデータを引き継げるようにします。
例えば「投稿数のトータル」といった情報は新規ログごとに0になっては困るため、このメソッドで引き継ぐようにします。
そして、データを引き継いだログを新たに挿入しそれを返します。
過去のログがなかった場合(インスタンスで初めての情報変動時)は、空のログを生成して挿入し、それを返します。
そのようにしてgetCurrentLogメソッドから更新すべきログを取得できたら、ログの情報を更新して処理は終了です。
隙間埋め
先述した「ログ抜け」問題への対応処理です。
まず、例えば「3時、4時、5時」のログを要求されたとき、「3時、4時、5時」のどれもログが存在しなかった場合の対応を行います。
その場合、その期間より前の時点から情報の変動がないことは明らかですので、「その期間より前の期間内の、最も新しいログ」をデータベースから取得してきて(2時があればそれを取得し、なければ1時を取得し、なければ… というふうに)、そのログデータを引き継いだデータを各々の時間で生成し、それで隙間埋めします。
次に、例えば「3時、4時、5時」のログを要求されたとき、「4時、5時」だけログがあった場合(つまり最も古い部分のログだけ無い場合)の対応を行います。
この場合も、先ほどと同様に最も新しいログを持ってきてそれを引き継いだデータを生成し末尾に追加します。
最後に、例えば「3時、4時、5時」のログを要求されたとき、「3時、5時」だけログがあった場合(つまり途中で抜けがある場合)の対応を行います。
この場合、抜けがある場所ごとに、その時点での過去の最も新しいログ(この例で言うならば3時)を参照し、それを引き継いだデータで隙間埋めします。
「3時、4時」だけログがあった場合(つまり先頭が抜けている場合)は、最後の方法で対応可能です。
これで、「抜け」問題は解決です。
同期
Chartの各々の派生クラスは「同期」のためのfetchActualメソッドを持っています。このメソッドは、以前のログデータを利用することなしに、現時点での正確な値を取得するメソッドです。同期の際は、このメソッドから返されたデータを使ってログを更新し、ズレを修正します。
この「同期」処理は、現時点では管理者による手動操作をトリガーとして実行されます。
おわり🤯
いかがでしたか？
この一連のチャートシステムは、Misskeyに限らず他のシステムでも利用可能なので、ぜひ参考にしていただければと思います。
また、「もっと良い方法あるぞ」という提案も歓迎です。
リンク集
- チャート基底クラス: https://github.com/syuilo/misskey/blob/develop/src/services/chart/core.ts
- テスト: https://github.com/syuilo/misskey/blob/develop/test/chart.ts