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

今回はMisskeyのチャート生成機能のバックエンド実装（チャートエンジン）について解説します。

チャートとは

Misskeyのチャート機能は、サーバー上で発生した様々な種類のイベントの推移をグラフやヒートマップ等でグラフィカルに表示できる機能です。

チャート表示できる情報には、例えば次のものがあります。

• アクティブユーザー数の推移
• 投稿数の推移
• 連合しているサーバー数の推移

このようなサーバー全体の情報だけではなく、他にも「ユーザーごと」や「連合しているサーバーごと」の情報も集計できます。例えば以下の情報を表示できます。

• あるユーザーのフォロワー数の推移
• あるユーザーのプロフィールページのPV数の推移
• あるサーバーのリクエスト数の推移

さらに、取得するチャートの分解能を「1時間毎」「⁠1日毎」から選択できます。

なお、チャートの描画にはChart.jsを使っていますが、今回はバックエンド側実装について取り上げます。

設計

まずチャートを生成するためのデータを集計する方法はどういうものがあるかを考えてみます。

データベースから集計する方法

チャートを得るには、データベースにある実際のデータを集計するのが処理的には最も簡単で愚直な方法です。一般的に各レコードには挿入日時カラムがありますので、それを元に範囲を指定して集計すればチャートが得られます。

実際、Misskeyでも一部そのような処理を行っている個所もあります。

しかしこの方法では、得られる情報がチャート生成を行う時点のものに限られます。例えばデータベースから物理的に削除されたデータを推移として結果に反映させることができませんし、レコード量が多いとパフォーマンスが低下するため実用的ではありません。

また、そもそもデータベースのレコードとして記録しないようなデータ（アクセスログ等）のチャートは生成できません。

ログを記録する方法

次に考えられるのは、イベント発生時にその変動（ログ）を記録する方法です。「⁠⚪︎年⚪︎日⚪︎時⚪︎分⚪︎秒にユーザーが1人増えた」「⁠⚪︎年⚪︎日⚪︎時⚪︎分⚪︎秒に投稿が1つ削除された」のようなログをレコードとして保存するイメージです。

この方法であれば、「⁠削除」も推移として記録できるようになりますし、レコードとして保存しないデータの記録も可能になります。

しかしイベント発生ごとにログを行っていくと、1億回投稿が行われたら1億個のログが挿入されることになるため、やはりレコード量が膨大になり、パフォーマンス上の問題が生じてしまいます（ちなみにmisskey.ioの投稿レコード数は記事執筆時点で約3億あります⁠）⁠。

ログを記録する方法［発展］

そこでMisskeyでは、イベントごとにログを挿入していくのではなく、「1時間単位」「⁠1日単位」といったように期間を分けて、その期間ごとにログを挿入していくという方法を実装しました。例えば、「⁠⚪︎年⚪︎日⚪︎時は投稿が500個増え、累計で30万個になった」とか、「⁠⚪︎年⚪︎日はユーザーが6人増え、累計で1200人になった」という感じです。

ある程度期間を決めて、その期間ごとの変動を記録していくことで、チャートの分解能を犠牲にする代わりにデータ量が抑えられます。

さらに、パフォーマンス向上のため「その時点での累計投稿数」などの情報はログ挿入時にその都度集計するのではなく、前のログのデータを利用して算出するようにします。

この方法であれば、例え1時間のうちに1000回投稿されてもレコードは1つしか挿入されないので、データ量は格段に少なくなりますし、既に集計された値がそのまま入っているため長い期間のチャートを取得する場合も一瞬で処理できます。

Misskeyではこの方法を使いながら推移を記録していきます。

チャートエンジンの実装

こういった仕組みでチャートの記録と集計を行うMisskeyのバックエンド実装がチャートエンジンです。

実際の実装が記述されいてるpackages/backend/src/core/chartにあるcore.tsを見ていきます。

• packages/backend/src/core/chart/core.ts

また、チャートの種類ごとにChartクラスを継承したクラスが用意される実装になっており、各チャートクラスは以下にあります。

• packages/backend/src/core/chart/charts

テーブルの生成

チャートのログはデータベースに保存されるので、最初にテーブルを定義する必要があります。しかし、チャートの種類が多く、さらに各チャートテーブルの中でも必要になるカラム数が多く複雑になります。

そこでチャートエンジンはチャート定義を元にして自動でテーブル定義を生成できるようになっています。

これらのテーブルは以下のような定義から自動生成されています。

import Chart from '../../core.js';

export const name = 'notes';

export const schema = {
	'local.total': { accumulate: true },
	'local.inc': {},
	'local.dec': {},
	'local.diffs.normal': {},
	'local.diffs.reply': {},
	'local.diffs.renote': {},
	'local.diffs.withFile': {},
	'remote.total': { accumulate: true },
	'remote.inc': {},
	'remote.dec': {},
	'remote.diffs.normal': {},
	'remote.diffs.reply': {},
	'remote.diffs.renote': {},
	'remote.diffs.withFile': {},
} as const;

export const entity = Chart.schemaToEntity(name, schema);

チャート定義からテーブル定義を生成するコードはcore.tsの208-256行目に記述されています。

インデックスやユニーク制約も自動で定義され、最終的に以下のようなマイグレーションコードが生成されます。

• packages/backend/migration/1000000000000-Init.js#L159-L188

ログの更新と挿入

情報の変動が発生した時はログレコードを更新または挿入しなければなりません。

claimCurrentLogメソッドで、更新すべきログをデータベースから取得します。ログがなければ新たに挿入します。

まず現在の期間に合致するログがすでに存在するか確認し、あればそのログを返して終了します。なければ新たにログを生成する必要があるので処理を続けます。

新たにログを挿入するためには、そのMisskeyサーバー初めてのログ挿入時を除き、「⁠前のログデータを利用する」という仕組みのため直近のログを取得する必要があります。

そのために、まずもっとも最近のログがあれば取得します。「⁠1時間前」とか「1日前」ではなく「もっとも最近の」とするのは、例えば昨日何もチャートを更新するような出来事がなかった場合にはそもそもログが存在しないためです。

その過去のログがあった場合は、派生クラスで実装されているgetNewLogメソッドにそのログを渡して現時点でのログにデータを引き継げるようにします。例えば「累計投稿数」といった情報は新規ログごとに0になっては困るため、このメソッドで引き継ぐようにし、データを引き継いだログを新たに挿入しそれを返します。

過去のログがなかった場合（サーバーで初めてのログ記録時）は、空のログを生成して挿入し、それを返します。

そのようにしてclaimCurrentLogメソッドから更新すべきログを取得できたら、ログの情報を更新して処理は終了です。

同期

先述した「トータル投稿数などの情報は前のログのデータを利用して算出する」という設計では、実際のデータとズレが生じる場合があります。

というのも、リレーショナルデータベースではデータの依存関係を定義し、「⁠あるデータが削除されたら関係するデータも削除する」という処理を行うことができます。このことから、例えばユーザーのアカウントが削除されたら、そのユーザーが行ったすべての投稿やフォロー関係も自動的に削除されるように定義できてしまいます。

つまり、こういったデータベースによる自動的な削除は、Misskey側で動いているチャートエンジンには感知できません。

他にも、外部ツールを利用してMisskeyのデータベースを操作した場合なども、Misskey側から行ったことではないので同じくチャートエンジンから感知できません。

したがって、Misskeyによる「自発的」なデータの操作しか記録できませんので、実際のデータとのズレが生じることがあります。前述した仕組みを考えると、そのズレは一時的なものではなく恒久的で、自然に修正されることもなく、むしろどんどん拡大していきます。この問題を解決するために、定期的に情報を正しい値に「同期」する処理が必要になってきます。

同期処理の実装

同期処理はチャートの種類ごとに実装されていて、この処理を以前の記事でも解説したジョブキューを用いて定期実行されるようにしています。

例えばユーザー数のチャートでは以下のような実装になっています。

protected async tickMajor(): Promise<Partial<KVs<typeof schema>>> {
	const [localCount, remoteCount] = await Promise.all([
		this.usersRepository.countBy({ host: IsNull() }),
		this.usersRepository.countBy({ host: Not(IsNull()) }),
	]);

	return {
		'local.total': localCount,
		'remote.total': remoteCount,
	};
}

このメソッドが定期的に実行されることで、ズレが発生しても修正されるようになっています。

なお、このメソッドは親クラスであるChartクラスで以下のようにabstractメソッドとして定義されているため、子クラスはこの同期処理を実装することが義務付けられています。

	/**
	 * 1日に一回程度実行されれば良いような計算処理を入れる(主にCASCADE削除などアプリケーション側で感知できない変動によるズレの修正用)
	 */
	protected abstract tickMajor(group: string | null): Promise<Partial<KVs<T>>>;

	/**
	 * 少なくとも最小スパン内に1回は実行されて欲しい計算処理を入れる
	 */
	protected abstract tickMinor(group: string | null): Promise<Partial<KVs<T>>>;

ユニークカウント

例えばあるユーザーのプロフィールに対するPV（ページビュー）数を記録したい場合、同じ人間が同じユーザーのプロフィールを何回開いたとしても、PV数は1としてカウントしたい場合が多いです。

そういったユースケースに対応するために、Misskeyのチャートエンジンには「ユニークカウント」機能があり、同じ値が複数回ログに記録されても値の種類の数をカウントできます。なお、この「種類の数」という概念は、カーディナリティ（cardinality） と呼称されます。

実装としてはcore.tsの462-472行目において、定期的に一時カラム内の値のカーディナリティを計算して正規のカラムに書き込んでいます。この処理は「ベイク」と呼んでいます。

ロック

当然ではありますが、MisskeyはバックエンドのMisskeyプロセスを複数並列に動作させることが可能です。

そのためチャートエンジンも同時に複数のインスタンスが動くことになり、場合によってはそれぞれの処理が競合し意図しない値がデータベースに書き込まれることが発生しえます。

それを防ぐためにcore.tsの372行目において、チャートエンジンは内部的にロックを取得して、同時に1つのインスタンスしかクリティカルな処理を実行しないように制御しています。なお、ロックはRedisを利用しています。

その他

集計グループ

「ユーザーごとの投稿数」といったチャートは、そのチャートが誰のチャートかという情報も追加で保存する必要があります。チャートエンジンではそのようなグループ情報の定義もサポートしています。

インターセクションカラム

集合Aと集合Bに含まれている値をカウントする機能もあります。例えばアクティブユーザーのチャートでは「タイムラインを見た人」と「投稿を行った人」を集計していますが、それに対してさらに「タイムラインを読み、かつ投稿を行った人」を集計するインターセクションカラムも定義されています。

インターセクションカラムの集計処理はcore.tsの474-501行目にあります。

accumulateカラム

前のログの値を引き継ぐカラムを設定できます。累計ユーザー数など、値が蓄積されていくデータに設定します。

引き継ぎ処理は新規ログ取得時である、core.tsの290-296行目で行います。

バッファリング

イベントが発生するたびにデータベースへ書き込みを行うと負荷が高いため、ある程度メモリ上にログを貯めてからまとめて書き込みを行うようにしています。

チャートの取得

チャートの取得は、データベースからログを持ってきてまとめれば良いだけなので難しいことはありませんが、ログの補間処理は必要になります。

ログの補間

「あくまでもデータが変動したときにログを挿入/更新する」という設計では、「⁠ログに抜けがある」場合があります。例えば、「⁠1時と3時には投稿があったが、2時の間には投稿がひとつもされなかった」というケースを考えると、データベースには1時と3時のログはありますが2時のログはありません。

データ出力の際にただ単にデータベースにあるログを集めてくるだけではこういった抜けが発生するため、この間の記録を補間（内挿）する処理も必要になります。コードでいうとcore.tsの639-693行目あたりになります。

ペイロードの圧縮［予定］

取得するチャートの期間が短ければそこまで気にする必要はありませんが、数年分といったチャートを取得する場合はそれなりのデータ量になるので効率的なレスポンスが求められます。そこでAPIのレスポンスペイロードを工夫し、圧縮して送信することを検討しています。

具体的には、現状それぞれの値が100000, 100002, 100005, 99998であるチャートを取得したとき、レスポンスはそのまま[100000, 100002, 100005, 99998]のような配列にシリアライズされています。

これでは無駄があるので、[100000, 2, 3, -7]のように前の値のデルタ値（差分）を入れるような表現方法にすればデータ量が少なく済みます。値が完全にランダムな場合は効果が得にくいですが、一般的なデータは前後の値と近い値であることが多いので、少なくない圧縮効果が望めます。

データの転送効率だけを追求するのであれば、JSONを使わずにバイナリでやり取りする選択肢もあるのですが、実装は複雑になります。

テスト

チャートエンジンのテストはpackages/backend/test/unit/chart.tsにあります。

チャートエンジンは内部的に時刻情報に依存した処理を行うため、テスト内で時間を任意に操作できるように@sinonjs/fake-timersを利用しています。

例えば以下のように書くと、1時間の間隔を空けて2回incrementメソッドが呼ばれた扱いになります。

await testChart.increment();

clock.tick('01:00:00');

await testChart.increment();

まとめ

今回はMisskeyにおけるチャート機能のバックエンド実装について紹介と解説を行いました。

チャートのバックエンド実装はいかに効率よくデータを記録できるかと、いかに高速にデータを取得できるかが課題になります。今後もチャート機能のパフォーマンス向上を考えていますので、また紹介できればと思います。