Fakebook: ゼロから作るSNS その1 データベース設計とクエリ分析

SNSを構築する上で、堅牢かつスケーラブルなデータベースを設計することは最重要だ。この記事では、ユーザ数や投稿記事数がいくら増えてもO(log(N))の対数性能を維持するスキーマとクエリを実例を交えて紹介する。これがおそらくSNS設計の真髄である。DBMSにはPostgreSQLを用いるが、考え方は他のシステムを使っても同じだ。

概要と方針

データベースのスキーマのER図を以下に示す。主なテーブルは三つで、ユーザを管理するusersテーブルと、各ユーザが投稿した記事を管理するpostsテーブルと、通知を管理するnotificationsテーブルである。その他のテーブルは、正規化と性能最適化の過程でその三つのテーブルから分離されたものだ。

DBのスキーマを設計するにあたり、正規化と性能最適化について理解し区別する必要がある。正規化の目的は、データの多重管理を避けて、すなわち真実の出所（single source of truth）を一元化して、不整合が起きにくくすることだ。正規化を進めるとDBの保守性が良くなることが多いが、性能が良くなるとは限らず、むしろ悪化する可能性もある。一方で、性能最適化は、実際に実行するクエリの効率を上げるためにスキーマを変えることで、結果として正規形に違反するスキーマになることもある。多重管理が過ぎると不具合の温床になるし、一元化を追求すると実運用に耐えない性能になるので、両者のバランスを取ることが重要だ。

SNSの文脈では、DBに投げるクエリは2種類に大別して考える。リスト系のクエリと、個別レコード操作のクエリだ。重いのはリスト系の操作で、それがスケーラビリティを決めるので、リスト系クエリをいかに効率化するかを考えてDB設計することになる。今回の例では、ユーザのリスト表示で参照するデータはusersテーブルに集め、ユーザの詳細画面でしか表示しないデータはuser_detailsテーブルに逃がしている。同様に、投稿のリスト表示で参照するデータはpostsテーブルに集め、投稿の詳細画面でしか表示しないデータはpost_detailsテーブルに逃がしている。リスト系クエリで読み込むテーブルを小さくすると、参照局所性が上がり、ストレージ層の入出力のデータ量が減少し、各層のキャッシュが利きやすくなり、結果として性能が上がる。

適切なテーブル分割ができたら、あとはクエリに合わせてインデックスを貼るだけだ。リスト系クエリでの全ての絞り込み操作はインデックスのみを参照するように設計する必要がある。インデックスは参照局所性が高いが、主テーブルは、上述の最適化をもってしても、参照局所性は相対的に低くなる。なので、主テーブルを参照しても良いのは、絞り込みが終わってから、表示するレコードの分だけということにする。この方針に違反したクエリは潜在的にボトルネックになるので、そうならないようにクエリ毎の実行計画を確認しておくことが重要だ。

PostgreSQL vs MySQL

PostgreSQLとMySQLは2025年現在のオープンソースデータベースの二台巨頭と言える位置にいる。今回のプロジェクトでも、どちらを使うか迷った。両者とも、スケーラブルなSNSを実装するのに十分な機能と性能を備えている。標準SQLとストアドプロシージャをサポートし、十分な型があり、適切なインデックスが張れ、トリガ機能があり、レプリケーションができ、バックアップ等のツールがあり、マルチプラットフォームで稼働する。導入実績も申し分ない。両者とも巷で求められる機能や性能を追求した結果、収斂進化が起きて、機能的にも性能的にもどちらが良いと言えない状態になっている。

堅牢性や可用性に関して、どちらが良いとは言えない。PostgreSQLは追記型であることでデータが壊れにくいことは明白だが、InnoDBもUndoログやRedoログでACID性を担保しているので、バグがなければ両者とも十分に堅牢と言える。ハードウェア障害が起きたら両者とも単体では耐えられないが、レプリケーションがあるので、両者とも実運用上での可用性を担保できる。

スケーラビリティに関しても、どちらが良いとは言えない。後述するが、スケーラビリティの限界点を決めるのはインデックスの空間効率であり、PostgreSQLもMySQLも遜色ない空間効率を達成している。インデックスがキャッシュに乗らなくなる規模になると、ハードウェアの性能が律速することになるが、それがDBMSの良し悪しで左右されることはない。

正直なところ、私はMySQLとPostgreSQLのどちらが良いのか判断できない。単に、先に試したのがPostgreSQLだから、PostgreSQLを使い続けているだけだ。スキーマを定義して、インデックスを貼って、ストアドプロシージャやトリガを定義して、クエリを書いて、問題なく動かせた。EXPLAINでクエリ分析をしたところ、所望の実行計画が出てきた。部分インデックスをちゃんと使う実行計画が出てきたのと、WITH句やJOIN LATELALなどを使った複雑なクエリが使えるのが便利と感じた。MySQLでも、書き方は微妙に違っても、ほぼ同様のことができるので、MySQLで駄目ということではない。ただ、クエリを書き直して分析し直すのが面倒なので、乗り換える動機がない。

PostgreSQLの明白な欠点は、追記型アーキテクチャであるせいで、更新処理の空間効率と時間効率が悪いことだ。後述するが、インプレース更新がないので、イイネの数を更新する度にレコード全体を複製する羽目になる。複製処理はDB内部で勝手にやることで、自動VACUUMによって無駄な空間は勝手に解消されるので、普通は利用者側で気にする必要はない特性だ。しかし、更新頻度が極端に高いイイネのようなデータでは、その更新負荷が無視できないことになる。MySQL（InnoDB）はインプレース更新があるので、その問題はない。ただし、イイネの数などのカウンタは、リレーショナルモデルの外側にあるキャッシュ的なデータなので、最適化を進める過程で専用のKVSに追い出すのが定石だ。カウンタを扱う能力の良し悪しでRDBMSを判断するのはフェアじゃないだろう。

MySQL（InnoDB）の主テーブルは、クラスタ化インデックスと呼ばれる構造を持つ。ざっくり言うと、キーが主キーで、その他の値を直列化したものが値であるところのB+木のKVSである。ゆえに、主キーの順序によって主テーブルの参照局所性が決まる。一方で、PostgreSQLの主テーブルは、ヒープと呼ばれるフラット構造である。挿入順にレコードがページの中に並べられる。主キーとレコードのアドレス（ページ番号とページ内オフセット）を持つB木のインデックスを使って主テーブルを参照する。参照局所性は挿入順によって決まる。

主テーブルのデータを物理的に並べるにあたって、作成日時で並べるMySQLと、挿入順で並べるPostgreSQLで、どちらが参照局所性を高められるだろうか。作成日時が新しいほど参照頻度が高まるという単純なモデル化をするなら、MySQLに軍配が上がる。作成日時または更新日時が新しいほど参照頻度が高まるというモデル化をするなら、PostgreSQLに軍配があがる。すなわち、「更新された投稿はしばらく参照頻度が高い状態が続く傾向にある」という経験則を認めるなら、PostgreSQLの方が有利ということになり、それを認めないなら、MySQLの方が有利ということになる。いずれにせよ、SNSは新規投稿がほとんどだということを鑑みると、両者の差は小さい。

どうしても雌雄を決したいのなら、自分のユースケースを具体的に想定した上で、テストデータとアクセスパターンを厳密に定義して、最善の実行計画となるクエリを書いたうえで、実運用環境でベンチマークテストを動かす必要がある。そうでない比較は全て無意味だ。「MySQL PostgreSQL 比較」とかで検索して出てくる記事は9割方がゴミなので、信じてはいけない。

そうは言っても、DBMSの選定をする前にテストデータを作ったりクエリの実行計画を詰めたりするのは現実的じゃない。ゆえに、そもそも雌雄を決するのは諦めるのが現実的だ。自分のユースケースでうまく動くであろう方法がどちらかの製品と組み合わせて実現できそうなら、それを仮採用し、一通りのシナリオが動いたなら、本採用すればよい。私は、今回のユースケースで、PostgreSQLを使って実装と運用ができるとみなしたから採用した。MySQLでも十分に可能であろうとは思うが、プロトタイプを書いてみないと確たることは言えない。どちらが最善かを断言するには、かなりの工数をかけた検証を要するが、それをやるかどうかは要件次第だ。私がDB研究者だったら検証論文を書くかもしれないが、違うので、割愛した。

追記方式の計算量とVACUUM

PostgreSQLは追記型であることで、更新操作の空間効率と時間効率が悪いという見方ができる。それは、半分合っていて、半分間違っている。MySQLのようなインプレース方式の更新では、レコード領域を書き換える前に、元に戻せるように、元のデータをUndoログとして書き出し、またトランザクションを再開できるように更新操作の全体をRedoログに書き出してから、実際の行データの更新を行う。事前にログを書き出すルールをWAL（Write Ahead Logging）とか言う。そして、トランザクションが完了した後に、不要になったログを消す。追記型の更新をインプレースのアナロジーで捉えるなら、更新前のデータがUndoログとして機能しているということになる。追記型方式は、VACUUM処理でUndoログを一括して消す方式だとも言える。更新前にログを書いて、更新後に消す、という構図はインプレース更新でも追記更新でも同じである。行データの更新操作の回数Nに対するログの読み書きの回数は比例するので、時間計算量はO(N)だ。

追記型だと、古いデータ（デッドタプル）が溜まっていくのは間違いない。それがテーブルサイズの20%に達すると、autovacuum機能によって自動的にVACUUM処理が発動する。生きている行データをページの先頭に詰め変えて、デッドタプルが占めていた領域を再利用可能なフリースペースにする。VACUUMの時間計算量はテーブルサイズに依存するので、更新回数Nに対して時間計算量がO(N^2)になるんじゃないかと心配になるかもしれない。しかし、償却計算量という概念を使うと、O(N)のままだと説明できる。テーブルサイズが大きくなるほどに、VACUUMの結果として得られるフリースペースが増えて、次のVACUUMが起こりにくくなっていく。長期的に考えると、VACUUMで読み書きするデータ量は行データの量の定数倍に収束するので、計算量はO(N)と言える。vectorやstringstreamのアルゴリズムを知れば、償却計算量について理解できるだろう。

VACUUMとVACUUM FULLの違いについてだが、VACUUMはページ内のデータの詰め替えだけをして、VACUUM FULLは行データをページ間で移動させる詰め替えをするのが違う。VACUUM FULLの結果としてフリースペースだけになったページは、OSに返却されて、データベースの容量が減るということになる。定期的にVACUUM FULLをしなければいけないと思っている人がたまにいるが、その必要はない。償却計算量の効果を信じて、autovacuumによるVACUUMだけで運用すればよい。VACUUM FULLをしないとストレージ容量が足りなくなりそうな場合、VACUUM FULLの後でも早晩ストレージ容量が足りなくなるので、ストレージを増設するしか解決策はない。

VACUUMは対象テーブルのページ全体を読み込んで、必要に応じて更新するので、軽い処理とは言えない。しかし、ストレージデバイスにとっては、ブロック単位のシーケンシャルアクセスを1回するだけなので、めちゃめちゃ重い処理というわけではない。通常のクエリが起こすランダムアクセスに比べれば、可愛いものだとも言える。インプレース更新を行うMySQLでは、行のサイズが変わることでフラグメンテーションが蓄積されるので、たまにOPTIMIZEをする必要がある。その処理はVACUUMとほぼ同じである。つまり、インプレース更新でも追記更新でも、VACUUMに相当する処理をたまに行うが、その頻度が追記型だと多めになるというだけだ。

さらに言うと、SNSの実運用上では、VACUUMは非常に効率的に動く。なぜなら、古い記事はほとんど更新されないからだ。DBのページが作られた後に、しばらくは新しめの記事が記載され、新しい記事はたまに更新されるのでデッドタプルが出て、VACUUMで再利用されたフリースペースには新しめの記事が記載される。ページが作られてからしばらく経つと、そのページに乗っている記事は全て古い記事になり、デッドタプルは全く発生しなくなる。データ領域が埋まっていてかつデッドタプルがないページにはall-visibleフラグが立つ。VACUUM処理は、Visibility Mapと呼ばれるビットマップをスキャンして、そこに乗っているall-visibleではないページのみを対象に行われる。つまり、ほとんどの古いページはVACUUMで読まれもしない。よって、長期間運用して投稿数が増えても、投稿関連テーブルのVACUUMの負荷は一定に保たれる。ユーザに関しても、古参ユーザはそんなにプロファイルを変えないし、非アクティブなユーザは全く変えないので、同様の時間的な偏りが起こる。よって、ユーザ関連テーブルのVACUUMの負荷は一定に保たれる。

後述する宣言的パーティショニングを使うとテーブルを透過的に水平分割できるが、そうするとVACUUMも分割された小さいテーブルの単位で行われて、負荷が時間分散される。また、テーブルを垂直分割することでも個々のテーブルを小さくでき、VACUUMの負荷を分散する効果が見込める。垂直分割はデッドタプルの蓄積も緩やかにするので、更新処理を効率化する効果が大きい。ただし、垂直分割しすぎると検索時のJOINが増えて効率が下がるので、トレードオフを考える必要がある。

Snowflake ID

個々のテーブルのスキーマを解説する前に、レコードのIDの採番方法について知ることが有益だ。Fakebookでは、Twitterが開発したSnowflake IDの変種を用いる。具体的には、0固定の符号ビットで始まり、その後ろに43ビットで表現したミリ秒のタイムスタンプの後ろにをつけ、その後ろに8ビットで表現したワーカーIDをつけ、その後ろに12ビットのシーケンス番号をつけた、合計64ビットのデータである。これを16進数の文字列で表すと、`198C2E846EE00000` のような16文字になる。

固定桁のタイムスタンプを接頭させることで、数値として比較すると発番の時系列と順序が一致する。10進数や16進数の文字列にした場合でも、固定桁にすれば、辞書順が時系列の順に一致する。この特徴はUUIDv7でも同じだが、Snowflake IDの方が空間効率が良い。Snowflake IDは、数値では8バイトで格納され、文字列（16進数）では16文字とVARLENAメタデータ1バイトの計17バイトで格納される。UUIDは数値では16バイトで格納され、文字列では36文字とVARLENAメタデータ1バイトの計37バイトで格納される。

Snowflake IDでは、単一の発番器が同一ミリ秒に4096回の発番が可能で、256個まで発番器を同時稼働させられるので、実運用上の衝突のリスクはゼロにできる。そして、プライマリキーの順序が時系列と一致すると、created_atのような従属属性を参照しなくてもソートができるため、より効率的なクエリが書けるようになる。

UUIDの利点は、協調型の採番方法でなくてもユニーク性が担保できることと、予測不能な乱数を含むので、秘密情報としても利用できることだ。逆に言えば、協調型の採番方法ができて、IDを公開情報にする場合は、UUIDでなくても良いということになる。UUIDの欠点は、文字列にすると長いことと、それがブラウザのアドレスバーに出てくるとダサいことだ。効率だけではなく、美観のためにSnowflake IDを採用した部分も大きい。

DBの処理効率を上げるには、IDは数値型で扱った方が良い。IDはインデックスにも格納されることが多いが、インデックスが小さくなれば、それだけキャッシュに乗せられるレコード数が多くなる。例えば、平均10バイトのニックネームと数値型8バイトのIDの複合インデックスはレコードあたり最低18バイトの空間が必要だが、IDを文字列の16バイトにすると最低26バイトの空間が必要になる。実際にはメタデータやパディングが入るので18/26=70%ほどの比率にはならないが、IDを数値型にする方が明白に空間効率が良くなる。また、数値の方が比較関数のCPU効率も良くなる。

とはいえ、インデックスのデータ量は主テーブルに比べればとても小さく、また比較関数のCPU負荷がボトルネックになることは稀だ。IDを文字列型で扱うのにも合理性がある。TypeScriptのnumber型の精度は53ビットなので、64ビットの値を数値として扱うにはbigint型にする必要がある。文字列ならば、数値の型の違いでバグるリスクが避けられるし、JSONに入れるのも楽だ。さらに、将来的に任意の採番方法に乗り換えるのも容易だ。

今回は、IDをDB内部では数値型として扱うが、DB操作を隠蔽するサービス層のメソッドの入出力ではIDは常に16進数文字列として表現することにした。それなら、双方の良いとこ取りになる。型を気にしなければいけない部分はサービス層に隠蔽され、その上層のAPI層でJSONなどに入れる際には文字列を扱うので、不整合は起き得ない。採番方向を変えるとしても、サービス層の内部に変更が隠蔽されていれば、APIを変える必要はない。

元来のSnowflake IDは41ビットでタイムスタンプを扱うので、エポックから2^41ミリ秒後（=69.681年後）にオーバーフローする。2010-11-04T01:42:54がエポックであるTwitterでは、2080年6月にオーバーフローする。2080年問題があるということだ。今回使う変種は43ビットのタイムスタンプを使うので、寿命は4倍の278.729年となる。1970-00-00T00:00:00がエポックなので、2248年9月まで使える。なお、最上位1ビットを0に固定している仕様なので、そのビットをタイムスタンプで使うと宣言すれば、寿命が2倍になって、2527年6月まで延命できる。ただし、その際にはDB内部のbigintが負数になるので、予めnumeric型やvarchar型にスキーマ変更する必要がある。

Snowflake IDを主キーとするテーブルのレコードは、そもそもcreated_atに相当する列を持たせないという選択ができる。IDから計算すれば良いからだ。created_atを削ると主テーブルの各レコードが8バイト小さくなり、多少ながら性能が向上することになる。インデックスの空間効率に比べれば主テーブルの空間効率の重要性は低いが、小さいは正義である。それに、Snowflake IDがタイムスタンプとワーカーIDとシーケンスIDの複合キーであると捉えると、その一部分であるタイムスタンプに従属するcreated_atを持っている事態は第2正規形違反とも言える。つまり、IDを変更せずにcreated_atが変更できるというのが不整合の潜在的なリスクになっているわけで、それを解消するのは性能だけじゃなくて保守性も良くする。アプリ側のコードが若干複雑になるという懸念はあるが、Snowflake IDをタイムスタンプに変換する以下のような関数を使うと解決する。あたかもcreated_atという列があるかのようにDBに振る舞わせることができるのだ。

CREATE OR REPLACE FUNCTION id_to_timestamp(id BIGINT)
RETURNS timestamptz
LANGUAGE sql
IMMUTABLE
STRICT
PARALLEL SAFE
AS $$
  SELECT timestamptz 'epoch'
       + (id >> 20) * interval '1 millisecond';
$$;

SELECT
  id, id_to_timestamp(id) AS created_at
FROM users;

なお、上述の方法で作ったcreated_atをORDER BY句で使うべきではない。同一値のレコードが複数存在する場合の順序安定性を考えると、必ず主キーなどの一意の属性との複合条件にすることになるが、だったら主キーだけで順序付けすべきだ。また、複合条件の全てをカバーするインデックスが効かない順序付けは、該当の全レコードを取得した後のソートを意味するが、それはスケールしない。created_atと主キーの複合インデックスを張れば良いことになるが、それは主キーのインデックスの機能と完全に被っている。Snowflake IDは時系列順でありつつも一意であるという点で、created_atの上位互換の存在と言える。

usersテーブル

ユーザを管理するusersテーブルに着目しよう。その実際のスキーマは以下のものだ。

CREATE TABLE users (
  id BIGINT PRIMARY KEY,
  updated_at TIMESTAMPTZ,
  snippet VARCHAR(4096) NOT NULL,
  nickname VARCHAR(50) NOT NULL,
  avatar VARCHAR(100),
  locale VARCHAR(50) NOT NULL,
  timezone VARCHAR(50) NOT NULL,
  ai_model VARCHAR(50) REFERENCES ai_models(label) ON DELETE SET NULL,
  is_admin BOOLEAN NOT NULL,
  block_strangers BOOLEAN NOT NULL
);
CREATE INDEX idx_users_nickname_id ON users(LOWER(nickname) text_pattern_ops, id);
CREATE INDEX idx_users_ai_id ON users (id) WHERE ai_model IS NOT NULL;

プライマリキーであるidはSnowflake IDだ。ユーザ登録時に指定したメアドを使ってログイン操作を行うが、以後のユーザの識別は全てidを用いる。メアドとパスワードはuser_secretsテーブルに分割してある。

nicknameにはUNIQUE制約がないので、同一のニックネームのユーザが複数いることが許される。この点はTwitterのハンドルネームとは明確に異なる。名前の取り合いを避けるためにそうした。ユーザをニックネームで検索する機能があるので、nicknameにはインデックスを貼っている。大文字小文字の違いを無視して検索を効率化したいので、インデックス内の値は小文字に正規化している。また、idとの複合インデックスになっている。検索には必ず順序指定が伴うので、その順序として使われるidとの複合インデックスにすることで検索が効率化する。そうでないと該当の全件をソートすることになってしまう。

ai_modelは、AIエージェントが読んで自分の行動パターンを決めるのに用いる。ai_modelsテーブルを参照していて、モデル毎の設定はそこから取れるようになっている。AIエージェントの一覧を取得するために、ai_modelsが設定されているユーザIDのリストを取得するための部分インデックスが貼ってある。

is_adminは、管理者かどうかのフラグである。ガチなサービスであれば、権限を細かく分けて運用するべきなのだろうけども、管理しきれなくなるリスクもある。AWSやGCPのロールの管理で辟易しているので、それへのアンチテーゼとして、管理者ユーザと一般ユーザの2種類で済ませた。何でもできる管理者と、自分のリソースしか扱えない一般ユーザの区分だけでも、SNSとしての運用はできる。

block_strangersは、自分がフォローしているユーザ以外からのイイネや返信を禁止するフラグだ。見知らぬ人に絡まれすぎるとSNS疲れするので、それを避けるためにこの機能がある。投稿単位でこのフラグを管理することも考えたが、過去の投稿のフラグを変えて回るのは大変だし、機械的にやるにしても処理が重くなるので、アカウント単位にした。

その他の属性は、表示用のものだ。updated_atは、ユーザの更新日時だ。snippetは、ユーザの自己紹介のスニペットで、Markdownを解析した後のJSON文字列が入っている。avatarは、アバター画像（アイコン）の保管場所を示す。通常はS3上のパスが入る。ユーザの作成日時を示すcreated_atは列としては存在しないが、``id_to_timestamp(id) AS created_at`` などとして同等の値を抽出する。

ユーザ一覧画面で表示する属性はusersテーブルに集めている。ログインにだけ必要な属性はuser_secretsに逃し、ユーザ詳細画面でのみ表示する属性はuser_secretsテーブルとuser_detailsテーブルに逃している。

user_secretsテーブルのスキーマは以下のものだ。

CREATE TABLE user_secrets (
  user_id BIGINT PRIMARY KEY REFERENCES users(id) ON DELETE CASCADE,
  email VARCHAR(100) NOT NULL UNIQUE,
  password BYTEA NOT NULL
);

emailはメアドであり、UNIQUE制約があるので、同一アドレスのユーザは一人しか登録できない。UNIQUE制約がついていれば、自動的にインデックスが張られ、emailによる検索が効率化する。ほとんどのメールサービスでは、メアドの大文字と小文字を区別しないので、emailは小文字に正規化して格納する。大文字と小文字を区別するサービスで大文字のメアドを使っている人は、確認メールが届かないので、このシステムを利用できないことになるが、仕方ない。もし大文字小文字の違いを許してしまうと、区別しないサーバでは、同じメアドで大量のアカウントが作れてしまう。RFC5321によるとメアドはユーザ名64文字と@とドメイン名255文字を合わせた320文字までがあり得るが、100文字までに制限している。

passwordにはハッシュ化したパスワードを記録している。ハッシュ値さえあれば、パスワードそのものを保管していなくても、入力されたパスワードに同じハッシュ関数を適用した結果が一致するかどうかでログイン処理は完遂できる。ハッシュ関数はDBの機能に任せずにアプリ側で任意の関数を呼ぶ方が保守性が良い。BYTEA型（バイト配列）のバイナリで格納しているのは、空間効率を上げるためである。バイナリは管理ツールでの視認性が下がるが、パスワードハッシュに視認性があっても仕方がない。

user_detailsテーブルのスキーマは以下のものだ。

CREATE TABLE user_details (
  user_id BIGINT PRIMARY KEY REFERENCES users(id) ON DELETE CASCADE,
  locale VARCHAR(50) NOT NULL,
  timezone VARCHAR(50) NOT NULL,
  introduction VARCHAR(65535) NOT NULL,
  ai_personality VARCHAR(65535)
);

localeはそのユーザの投稿につけられるデフォルトロケール情報で、「ja-JP」「en-US」などの値を持つ。timezoneは通知などに使われるタイムゾーンで、「Asia/Tokyo」「UTC」などの値を持つ。

introductionは自己紹介の全文であり、Markdownの文字列が入っている。ai_personalityはAIの人格を説明するプレーンテキストが入っている。この二つの属性はデータが大きくなりがちなので、それを分離することで、usersの性能が安定する。

postsテーブル

投稿された記事を管理するpostsテーブルに着目しよう。その実際のスキーマは以下のものだ。

CREATE TABLE posts (
  id BIGINT PRIMARY KEY,
  owned_by BIGINT NOT NULL REFERENCES users(id) ON DELETE CASCADE,
  reply_to BIGINT,
  snippet VARCHAR(4096) NOT NULL,
  locale VARCHAR(50),
  allow_likes BOOLEAN NOT NULL,
  allow_replies BOOLEAN NOT NULL,
  published_at TIMESTAMPTZ,
  updated_at TIMESTAMPTZ
);
CREATE INDEX idx_posts_owned_by_id ON posts(owned_by, id);
CREATE INDEX idx_posts_reply_to_id ON posts(reply_to, id);
CREATE INDEX idx_posts_root_id ON posts (id) WHERE reply_to IS NULL;
CREATE INDEX idx_posts_root_owned_by_id ON posts (owned_by, id) WHERE reply_to IS NULL;
CREATE INDEX idx_posts_public_owned_by_published_at ON posts (owned_by, published_at) WHERE published_at IS NOT NULL;

プライマリキーであるidはSnowflake IDだ。usersと同様にリストを返す全てのクエリは `ORDER BY id` をすることになり、その順序が時系列になるのは便利だ。

owned_byは、その投稿を書いたユーザのIDだ。ユーザ毎の投稿の一覧を出すクエリのために、当然それにインデックスを貼る必要がある。その際にもID順でデータを返すので、owned_byとidの複合インデックスにすべきだ。

reply_toは返信先の投稿IDだ。返信ではない投稿はreply_toにNULLを持つ。外部キー制約をつけていないのは、返信先の投稿が消される可能性があるからだ。ON DELETE SET NULLをつければ返信先が消された時にNULLにすることもできるが、返信先が消えたら返信じゃなくなるという扱いもおかしいので、そのまま値を残すことにしている。外部キー制約がないとアプリ側で整合性を保証する必要があるが、それはトランザクション内でちゃんと検査する。なお、投稿毎の返信の一覧を出すクエリのために、reply_toにIDとの複合インデックスを貼る必要がある。また、ログイン後のUIのデフォルト状態では、返信ではない投稿の一覧を出したい。そのクエリを効率化するため、NULL値に限定した、IDとの複合インデックスを作っている。

allow_likesとallow_repliesは、それぞれイイネと返信を受け付けるか否かを示している。ヘルプ記事などは多くのユーザに見られるだろうが、そこにイイネや返信をつけるスパム行為が予期されるため、任意のページのイイネや返信をブロックする機能は必須だ。

その他の属性は、表示用のものだ。localeは、投稿毎のHTMLのlang属性に指定されるなどして、ロケール情報を示す。snippetは、投稿本文のスニペットで、Markdownを解析した後のJSON文字列が入っている。投稿の作成日時を示すcreated_atは存在しないが、postsと同様にid_to_timestamp関数で動的に生成する。published_atは外部公開日時を意味する。これがNULLでなく現在時刻がそれを過ぎているなら、その投稿は外部に公開できる。updated_atは更新日時を意味する。作成時刻を表示したいのは自明だが、更新時刻も重要だ。イイネや返信を集めた後に内容を書き換えると悪戯や意図せぬ誤解の元になるため、少なくとも更新した事実を表示することで警戒を促すべきだ。

投稿一覧画面で表示する属性は全てpostsテーブルにあり、投稿詳細画面でのみ表示する属性はpost_detailsテーブルに逃している。そのスキーマは以下のものだ。

CREATE TABLE post_details (
  post_id BIGINT PRIMARY KEY REFERENCES posts(id) ON DELETE CASCADE,
  content VARCHAR(65535) NOT NULL
);

contentは投稿記事の全文であり、Markdownの文字列が入っている。現状ではそれだけだ。この属性はデータが大きくなりがちなので、それを分離することで、postsの性能が安定する。

MarkdownとJSONの使い分け

ユーザの自己紹介や投稿の記事の本文はMarkdownである。そのスニペットを作るのは、実はかなり複雑な問題を孕んでいる。単に文字列の長さで前方を抽出すると、マーキングの記号の途中で切られる可能性があり、構造が崩れてしまう。また、記号を文字数に数えると、本来の表示する長さで切ることができない。よって、MarkdownをAST（抽象構文木）として表して、それを走査しながら文字数を数える。ノードの途中で打ち切る際には、中身の文字列のみを切って、ノード自体は生き残らせるという処理を行う。HTMLとして表示する際には、ASTをHTMLに変換すればよい。本文全体をHTMLに変換する際にも、全く同じ手順でASTを介して行う。これによって、本文がMarkdownなのに、表示が決して崩れないスニペットを実現できる。

本文をDBに保存する際には、Markdown文字列をそのまま保存する。ASTをJSONとして保存することもできるが、編集する際に再度Markdownに戻すためにはJSONからMarkdownに変換する完全逆写像を実現する必要があり、それを保証するのが大変だ。また、Markdownをそのまま保存した方がデータ量も小さい。

一方で、スニペットをDBに保存する際には、ASTをJSONとして保存する。スニペットをMarkdownに変換することも考えたが、ASTのままの方が無難だ。こちらも完全逆写像の保証が難しいのと、スニペットを編集することはないのが理由だ。ただし、`{"type":"element","tag":"p","text":"Hello World"}` のような文字列をそのまま保存すると効率が悪いので、JSONの体裁のまま圧縮を掛けている。具体的には、`{"T":"p","X":"Hello World"}` のように、構造の圧縮と属性名の辞書変換をかけている。これは可逆圧縮なので、これによって表示が崩れることはない。

ところで、投稿のタイトルなどの構造をDBスキーマとして表現しないのも、設計の工夫のひとつだ。Markdownの中にはタイトル（H1ヘッダ）が本文に含まれる時もあるし、含まれない時もある。おそらく含まれないことの方が多い。構造に制約を持たせないことで、保守性を高めている。また、全文検索との相性も良い。本文を対象とする中間一致の全文検索（`content ILIKE '%xxx%'`）もサポートするが、タイトルと区別しないことで、クエリが単純になる。

なお、現状では、全文検索のために、pg_trgmなどのq-gramインデックスを貼っているわけではないので、全文検索のクエリはボトルネックになっている。インデックスを貼ればマシになるのは明らかなのにそうしていないのは、それによって更新処理が重くなるからだ。さらに、インデックスを貼っても、"the" とかで検索されると、全件取得してからソートするという地獄が待っている。全文検索で絞り込んでからソートする場合、頻出語に弱い。順序キーであるIDと全文検索用インデックスの複合インデックスを作って早期終了する仕組みが求められるが、PostgreSQLの標準的なプラグインには存在しない。ストップワードを足すみたいなad-hoc対応は可能だが、いたちごっこになる。そのあたりを深く考えず、全文検索用のインデックスを張っただけで実運用に入ると、件数が増えたある時に突然システムが停止することになるだろう。

全文検索機能に関しては、バッチ処理でデータを抜き出して作った外部検索エンジンを使うのが無難だ。検索エンジンを別ホストで動かせば、インデックスの更新処理が重くなっても、"the" みたいな爆弾が投げられても、SNSの主たる機能に影響がないというのは実運用上で非常に重要だ。リアルタイム性が必要であれば、最新のデータだけを扱うオンメモリ検索と組み合わせればよい。検索エンジンにデータを流し込む際には、MarkdownからASTを構築すれば、タイトル等を属性として扱うなどの任意の後処理ができる。

ロケールとタイムゾーン

ユーザ登録時に、ブラウザのロケール設定とシステムのタイムゾーン設定は、暗黙的にバックエンド側に送られて、users_detailsテーブルのlocale属性とtimezone属性にそれぞれ記録される。これらの値はユーザプロファイル画面から変更できる。ロケールは主に投稿の言語指定に利用され、タイムゾーンは通知などのスロットの管理に使われる。なぜクライアント環境での設定をサーバ側にコピーして多重管理するかというと、役割が違うからだ。クライアント環境のロケールはUIの表示言語や形式を変更するためにあり、投稿内容の言語とは別かもしれない。クライアント環境のタイムゾーンはユーザが短期滞在している場所かもしれず、ユーザの本拠地とは別かもしれない。

ユーザが記事を書く際に毎回ロケールを指定するのは面倒くさすぎるし、多くのユーザはロケールという概念を知りもしないので、ロケールを一切意識しないで投稿できるようにしている。その場合、投稿のlocaleはNULLになり、表示時にはユーザのロケールが使われる。つまり、巡り巡ってブラウザのロケールが使われる。ただし、投稿時に本文の末尾に「#[locale=en-US]」とか書くと、投稿毎に言語を指定できる。ユーザのロケールと投稿のロケールは従属関係ではなく、独立して設定すべき属性であり、性能の要請による非正規化ではない。投稿のロケールがNULLである場合にはユーザのロケールが使われるというフォールバックが働くだけだ。投稿のロケールは記事の内容から自動判定することも考えたのだが、精度が怪しいし、短い投稿の言語判定は本質的に困難な場合が多いので、現状では凝ったことはしない。

マルチリンガルが普通である地域で運用するには、投稿毎のロケール設定が必須だ。投稿された記事が表示される際には、HTMLのlang属性にロケール情報が乗せられる。この情報は、スクリーンリーダーにとって必須である。言語がきちんと判定できないとまともに読めないからだ。また、記事を外部公開した際には、SEOの観点でも重要になる。

ここで言うロケール情報とは、BCP47（Best Current Practice 47）という規格に則った文字列のことである。「en-US」（米国英語）、「ja-JP」（日本国日本語）、「zh-CN」（大陸中国語）などの文字列である。「en」（英語）、「ja」（日本語）「zh」（中国語）などでも良い。ユーザが米国英語と英国英語を区別したいと思うなら「en-US」「en-GB」を指定すれば良いし、そうでなく英語であることを表せば良いなら「en」指定する。同様に、大陸中国語と台湾中国語を区別したいと思えば「zh-CN」「zh-TW」を指定し、そうでなく中国語であることを表せば良いなら「zh」を指定する。HTMLのlang属性には、特別な理由がない限りは言語コードのみを指定して地域コードを省略するということになっているのだが、特別な理由があるかどうかをサービス側が勝手に判定するのは失礼にあたる。「ja-JP」は冗長だという人も多いだろうが、もしかして「ja-TW」やら「ja-x-osaka」やらを区別したいから敢えてそう指定しているのかもしれない。よって、ユーザが指定したロケールをそのまま出力する。投稿毎のロケール指定をプルダウン選択方式にしないのは、マルチリンガルのみが使う特殊機能だからだ。全ユーザの心理的負荷を上げたくないのと、選択肢では表現できない自由記述を許すためだ。

多言語対応SNSにおけるロケールが3種類あることを整理しておこう。ユーザがブラウザに設定しているロケールと、ユーザがコンテンツを書く際のロケールと、ユーザが閲覧する別の各々のユーザのロケールだ。例えば、日本語を母語としてブラウザの言語設定で日本語を設定しているユーザが、普段は英語の投稿をしているかもしれない。それでいて、ロシア人の友達が多数いて、ロシア語の投稿をよく読むとしよう。そのユーザのブラウザの言語設定は「ja」で、SNSに設定するロケールは「en」で、タイムライン上で表示される各投稿は「ru」だったり「ja」だったり「en」だったりする。ここで重要なのは、サービスに登録する投稿用のロケールである「en」と、ブラウザの言語設定である「ja」が独立であることだ。UIはブラウザの言語設定を見てローカライズすることになるが、現状ではUIパーツはローカライズされないので、サイト自体のlang属性は「en」固定である。しかし、ユーザが投稿する記事のロケールは、サイトのロケールにもブラウザのロケールにも束縛されず、ユーザアカウントに設定したロケールもしくは投稿時に指定したロケールにのみ束縛される。また、他のユーザの各投稿は同様にその著者が投稿時に指定したロケールに束縛される。ロケールはコンテンツの著者が設定するものであり、閲覧者が設定するものではない。

タイムゾーンとTIMESTAMPTZ型の関係には注意すべきだ。TIMESTAMPTZ型の内部表現はUNIXエポックからの経過ミリ秒数を表す符号付き64ビット値であり、TZという接尾辞が付きながら、タイムゾーン情報を保持しない。SELECTされた際にDBサーバのタイムゾーンまたはセッションのタイムゾーンに基づいた日時表現の文字列に自動変換するという仕様が付随しているだけだ。アプリ側でDBのタイムゾーン設定に依存したコードを書くとバグの温床になるので、DBサーバのタイムゾーンはUTCにして、セッションのタイムゾーンは未指定にしておいて、常にUTCで扱うのが良い。クライアント側にはUTCのままでデータを送り、クライアント側ではブラウザの設定に基づいてユーザのタイムゾーンの日時表現に変換して表示する。今回サーバ側でクライアントのタイムゾーンを知る必要があるのは、通知カードを日付単位でまとめるにあたって、ユーザのローカル時間の日付単位でやる必要があるからだ。日本限定で運用するならシステム全体で日本時間固定にしても運用できるが、OSSとして世界に頒布するならそうはいかない。固定タイムジーンだと、一つの国だけで運用するにしても、アメリカやロシアでは破綻する。

余計なお世話ではあるが、日本の典型的なSI案件案件において、日本語および日本標準時間（JST）一択で話が済んでしまうことが多いのは、国際化の観点で不遇だと言えよう。日本を拠点とするサービスだって、ユーザは海外にいるかもしれないし、日本語以外の言語を使うかもしれない。そしてその割合は年々増え続けている。国際化においてロケールとタイムゾーンの対応は根幹になるので、フロントエンドの多言語化よりも先にバックエンドの情報設計を真面目に考えた方が良いだろう。

user_followsテーブルとuser_blocksテーブル

ユーザ同士のフォロー関係を管理するuser_followsテーブルに着目しよう。その実際のスキーマは以下のものだ。

CREATE TABLE user_follows (
  follower_id BIGINT NOT NULL REFERENCES users(id) ON DELETE CASCADE,
  followee_id BIGINT NOT NULL REFERENCES users(id) ON DELETE CASCADE,
  created_at TIMESTAMPTZ NOT NULL,
  PRIMARY KEY (follower_id, followee_id)
);
CREATE INDEX idx_user_follows_follower_created_at ON user_follows (follower_id, created_at);
CREATE INDEX idx_user_follows_followee_created_at ON user_follows (followee_id, created_at);

フォロイー（自分がフォローしているユーザ）の一覧と、フォロワー（自分をフォローしているユーザ）の一覧を見るためには、このテーブルが必要だ。usersテーブルにfollowersやfolloweesという属性を持たせて中に配列を入れるという運用もできなくはないが、第1正規形に違反する構造で運用すると確実に破綻するので、テーブル分割が必要だ。フォロワーとフォロイーのペアが主キーになっているので、一意性はそこで保証される。また、フォロイーとフォロワーの一覧をそれぞれ時系列で取得するクエリを効率化するためのインデックスが、created_atとの複合インデックスとして設けられている。

特定のユーザからのイイネや返信をブロックする機能もある。これもブロッカー（ブロックするユーザ）とブロッキー（ブロックされるユーザ）のペアになっていて、それぞれをキーにして一覧が取得しやすいようにインデックスが張られている。

CREATE TABLE user_blocks (
  blocker_id BIGINT NOT NULL REFERENCES users(id) ON DELETE CASCADE,
  blockee_id BIGINT NOT NULL REFERENCES users(id) ON DELETE CASCADE,
  created_at TIMESTAMPTZ NOT NULL,
  PRIMARY KEY (blocker_id, blockee_id)
);
CREATE INDEX idx_user_blocks_blocker_created_at ON user_blocks (blocker_id, created_at);
CREATE INDEX idx_user_blocks_blockee_created_at ON user_blocks (blockee_id, created_at);

粘着質のユーザをブロックしても、ブロック機能だけでは、アカウントを複数作って攻撃されるのは防げない。これに対する根本的な対策はない。ほとぼりが冷めるまでは、フォロイー以外からのイイネや返信を拒絶するのが望ましいが、そのためにusersテーブルのblock_strangersがある。特定ユーザのブロック機能とユーザ属性としての他人ブロック機能は相補的な関係にある。

ブロックしたユーザも依然として自分の投稿を読むことはできる。この挙動はTwitterと同じであり、ブロック機能に情報隠匿の機能がないことは明言しておかねばならない。Twitterでブロック相手も記事が読める仕様変更を時には物議を醸したが、私はこの仕様は妥当だと思う。アカウントを複数作るか第三者にコピペやスクショを頼むだけで簡単に回避できてしまうような隠匿機能に頼るべきではない。そもそも、特定の相手に見られて困るような内容は、不特定多数に見せるべきではない。

user_followsとuser_blocksでは、ユーザIDがタイムスタンプを内包するSnowflake IDなのに、created_atが分けられている。フォロー関係が成立した日時はユーザの作成日時と独立しているからだ。一覧表示の際には新しく成立した関係から順に表示する。ところで、created_atに限らず、TIMESTAMPTZを順序付けに使うと、同一ミリ秒でのレコードの順序が安定しないが、Snowflake IDを代用すればその問題は解決する。しかし、user_followsやuser_blocksで、同一のユーザIDを持つレコードのcreated_atが重複する可能性は非常に低い。万が一重複したとしても表示順序が前後するかもしれないだけなので、それは許容して、TIMESTAMPTZのままにすると決めた。フォローやブロックが発生する頻度はユーザ作成の頻度よりも高いので、それに律速されてSnowflake IDの発番器を増やすのは避けたいというのもある。後述するpost_likesでTIMESTAMPZを使っているのも同じ理由だ。

post_tagsテーブル

投稿につけられるタグを管理するpost_tagsテーブルに着目しよう。その実際のスキーマは以下のものだ。

CREATE TABLE post_tags (
  post_id BIGINT NOT NULL REFERENCES posts(id) ON DELETE CASCADE,
  name VARCHAR(50) NOT NULL,
  is_root BOOLEAN NOT NULL,
  PRIMARY KEY (post_id, name)
);
CREATE INDEX idx_post_tags_name_post_id ON post_tags(name, post_id);
CREATE INDEX idx_post_tags_root_name_post_id ON post_tags(name, post_id) WHERE is_root;

記事を分類するにあたって、カテゴリとタグのどちらを使うべきかという議論がある。どちらも曖昧な概念ではあるが、その区別は重要だ。一般論として、カテゴリは、記事をフォルダ的に分類するものである。つまり、カテゴリを設ける場合、各記事は1つのカテゴリを必ず持つ。カテゴリがない記事は「その他」とかいったカテゴリをつけ、カテゴリが複数ありそうな記事も、便宜上、代表的なカテゴリを1つ選んでそれに所属させることになる。必然的に、カテゴリの種類を予め決めておいて、記事を執筆する際にどれかのカテゴリを選ぶというUXになる。一方で、タグは、記事を投稿する際に思いつきで決めるものだ。タグが無い記事があっても良いし、タグが複数個ある記事があっても良い。管理者不在で不特定多数が記事を投稿するSNSでは、カテゴリは運用しづらい。よって、タグを採用することになる。Twitterがタグ運用なのも同じ理由だろう。

タグは予め定義するものではなく、投稿の属性の位置づけだが、第1正規形を満たすためと、検索性を持たせるために、テーブルを分離する必要がある。一方で、タグをエンティティとしては扱わないので、タグにIDや作成日時のようなメタデータが付くことはない。よって、post_idとnameのペアを主キーとする。

返信ではないルート投稿であることを示すis_rootフラグがある。postsのreply_toがNULLであるか場合に真になるわけで、主キーの一部であるpost_idに関数従属するので、第2正規型違反だ。アプリ側でpostsを更新する際には必ずpost_tagsのis_rootにも反映させる必要が生じるので気持ち悪い。しかし、これがないと下記のインデックスを作れないので、仕方がない。

タグ名で記事の一覧を取得するクエリを効率化するために、nameとpost_idの複合インデックスを張っている。複合インデックスにするのは、post_idでの順序付けを効率化するためだ。もしもpost_idがインデックスに含まれないと、nameに一致する投稿を全て取得してからソートすることになり、頻出のタグではすぐ破綻してしまうだろう。

さらに、UI上でルート投稿のみに絞り込むモードにした場合もタグ検索の対数計算量を保証するために、ルート投稿に絞ったインデックスも作っている。タグが付く投稿の多くはルート投稿なので、通常のインデックスで絞り込んでも、ほとんどの場合で速い。しかし、返信にだけ使われるタグが大量にあった場合に該当タグの全件走査になり、それがバズると致命傷になり得るので、専用インデックスを作らざるを得ない。

post_likesテーブル

投稿につけられるイイネを管理するpost_likesテーブルに着目しよう。その実際のスキーマは以下のものだ。

CREATE TABLE post_likes (
  post_id BIGINT NOT NULL REFERENCES posts(id) ON DELETE CASCADE,
  liked_by BIGINT NOT NULL REFERENCES users(id) ON DELETE CASCADE,
  created_at TIMESTAMPTZ NOT NULL,
  PRIMARY KEY (post_id, liked_by)
);
CREATE INDEX idx_post_likes_post_id_created_at ON post_likes(post_id, created_at);
CREATE INDEX idx_post_likes_liked_by_created_at ON post_likes(liked_by, created_at);

個々の記事にイイネをつけたユーザの一覧を出すクエリを効率化すべく、post_idとcreated_atの複合インデックスが貼られている。これもソートを省く必要性のために存在する。また、自分がイイネした記事の一覧ができると、ブックマーク的に使えて便利だ。そのクエリを効率化するために、liked_byとcreated_atの複合インデックスも貼られている。created_atがpost_idとは別に保持されているのは、投稿の作成日時とイイネの作成日時は異なるからだ。

カウンタ系テーブル

ユーザ一覧表示には、各ユーザのフォロワー数とフォロイー数と投稿数を表示する。投稿一覧表示には、各投稿のイイネ数と返信数を表示する。それらの値は、user_followsテーブルやpostsテーブルやpost_likesテーブルにSELECT文を発行するサブクエリを書けば取得できる。しかし、クエリを発行するたびに再集計したら、まともな性能が出ないので、ここは非正規化するしかない。それを率直に書くと、以下のようになる。

CREATE TABLE users {
  ...
  count_followers INT NOT NULL,
  count_followees INT NOT NULL,
  count_posts INT NOT NULL
};

CREATE TABLE posts {
  ...
  count_likes INT NOT NULL,
  count_replies INT NOT NULL
};

他テーブルから導出可能な値を二重管理しているので、不整合が心配になる。これらの属性は、他テーブルの集合演算結果への推移的従属をしている。これは、第5正規形までのルールには違反していないとしても、広い意味でのドメインキー正規形には違反している。しかし、PostgreSQLのストアドファンクションでそれらの自動更新をすれば、アプリ側で複雑な処理を書かなくてもトランザクション内で整合性が保たれる。

ここで、PostgreSQL特有の問題が出てくる。追記型であるPostgreSQLは、カウンタの実装に全く向いていないのだ。行の一部の属性を更新する場合にも、行全体のコピーを追記することになる。例えばpostsテーブルのとあるページに一つだけレコードが書いてあったとしよう。IDとスニペットとイイネ数と返信数だけに単純化して表現する。イイネ数3を4に更新すると、行データを丸々コピーした上で、フォロワー数の部分だけ修正したものを、直後に書き込むことになる。

[0x12345|I'm Nancy. Nice to meet you. This is a pen.|3|0]
[0x12345|I'm Nancy. Nice to meet you. This is a pen.|4|0]

投稿本文をpost_detailsに分けているおかげで、posts行データはせいぜい600バイト程度に収まる。それでもイイネの度に600バイトの領域が消費されるのは厳しい。post_detailsを分けていなかったらもっと厳しいことになる。

PostgreSQLでは、更新頻度が高い属性は垂直分割すべきだ。特に、更新頻度が高い属性と、更新頻度が低いがデータが大きい属性は、分けた方が良い。カウンタは更新頻度が高い属性の典型なので、当然分ける。投稿に関しては、post_countsというテーブルを用意して、そこにイイネの数と返信の数を記録する。

CREATE TABLE post_counts (
  post_id BIGINT PRIMARY KEY REFERENCES posts(id) ON DELETE CASCADE,
  like_count INT NOT NULL DEFAULT 0,
  reply_count INT NOT NULL DEFAULT 0
);

投稿用のpost_countsと同じ理屈で、ユーザ用のuser_countsも分離してある。ここまで軽量なテーブルであれば、イイネ数が3,4,5,6とどんどん更新されても、データサイズの増加は緩やかだ。

[0x12345|3|0]
[0x12345|4|0]
[0x12345|5|0]
[0x12345|6|0]

どうせなら、さらに分割してpost_like_countsをpost_reply_countsを作る考えもある。しかし、それは総合的には損が多い。テーブルを分けると参照系クエリでJOINの回数が増えて時間効率が悪くなる。また、テーブル毎に主キーのインデックスを保持する必要があり、空間効率も悪くなる。テーブルの各行に同居のカウンタが1つ増えるのは4バイトの増加で済むが、それが別テーブルの個別のレコードだとすると、主テーブルのフットプリントとインデックスのフットプリントを食うことになる。不要な垂直分割をしてはならない。

行の位置が移動すると全てのインデックスを更新しなければいけないが、HOT（Heap-Only Tuple）の列だけの更新であれば、移動先が同一ページにある限り、ページ内に移動先を記録することでインデックスの更新を抑制する最適化が働く。インデックスに書いてある「ページ内オフセット」は、ページ内のラインポインタ配列の添字であり、その配列要素の値を書き換えるだけならインデックスは書き換えないで済む。HOT最適化の発生を上げるためには、フィルファクタを75%程度にすべきだ。主テーブルのデフォルトのフィルファクタは100%であり、それはINCERTやVACUUMでページの容量一杯まで行データを詰め込むことを意味する。そうすると、既存の行データが更新された場合に、同じページに新しい行データを置ける確率は低くなる。フィルファクタを75%にしておくと、25%の空き領域が更新操作のために予約されている状態になるので、多くの場合で同一ページに更新データを置ける。フィルファクタを低くしすぎると空間効率が悪化し、高くしすぎると時間効率が悪化するので、75%くらいが丁度よいだろう。ついでに、VACUUMの発動条件を0.1に下げて発動しやすくして、ANALYZEの発動条件を0.3に上げて発動しにくくする。

ALTER TABLE post_counts
  SET (fillfactor=75,
       autovacuum_vacuum_scale_factor=0.1, autovacuum_vacuum_threshold=1000,
       autovacuum_analyze_scale_factor=0.3, autovacuum_analyze_threshold=1000);

postsテーブルが肥大化するよりは遥かにマシだと言っても、post_countsもどんどん肥大化する。インプレース更新だったら最新値だけ持てばいいし、そもそもテーブルを分ける必要すら生じなかったのに、なんという非効率だろうか。しかし、冷静に考えると、集計対象であるpost_likesテーブルに比べれば、分離したカウンタテーブルの肥大化はマシなのだ。post_likesテーブルは、投稿IDとユーザIDと発生時刻のタプルがどんどん足されていく構造であり、古いデータを消すことがそもそも不可能だ。user_followsテーブルも同じだ。インプレース更新だとしてもそれらのテーブルは追記していくしかない。post_likesやuser_followsを管理する負荷に比べれば、VACUUMで圧縮されるカウンタ系テーブルの負荷なんておまけみたいなものだ。

PostgreSQLがカウンタの管理に向いていないことは明らかだが、上述の理由でカウンタの負荷は相対的に低いため、意外に問題が顕在化しづらいはずだ。それでも顕在化したなら、カウンタ用のKVSを導入を検討することになる。LMDBやRocksDBが定番だろう。拙作のTkrzwとTkrzw-RPCというのもある。時間効率と空間効率に優れていて、アトミックなインクリメントやCompare-And-Swap機能もある。キャッシュであるRedisを使っても良い。ただし、キャッシュはデータが消えるので、対応するカウンタが存在しない場合にはpost_likesテーブルをスキャンしてイイネを数え直す必要がある。その際の原子性の確保は厄介だ。

実際問題としては、カウンタのためだけにKVSを導入するよりは、post_likesごとKVSにしてしまうというシナリオの方がありそうだ。イイネの有無とか数は、ちょっとずれていても、万が一消えたとしても、サービスの存続を脅かすほどの問題にはならない。よって、堅牢性や一貫性が多少劣るかもしれないが、早くて安くてスケールするKVSに全体を逃がすというのは現実的な判断になる。

宣言的パーティショニング

テーブルを透過的にパーティショニングするための宣言的パーティショニングという機構がある。透過的とは、外部仕様に変更がないということであり、使う側（クエリ）を変更しなくても動作して同じ結果が取得でき、それでいて所望の恩恵が受けられるということを意味する。あるテーブルにパーティショニングを宣言すると、そのテーブルは親テーブルとして機能するようになり、実際の処理をパーティション条件で決めた子テーブルに移譲するようになる。インデックスも分割していない時と同じように働くので、SQL文は全く変えなくて良い。それでいて、テーブルを分割した効果で、VACUUMは子テーブルの単位で実行されるようになる。

カウンタ系のテーブルはVACUUMを頻繁にすべきだが、こまめにやって負荷を時間分散したい。そうすると、CPU負荷やI/O負荷を分散させる効果がある。VACUUMのために読み書きしたページはDBのページキャッシュには乗らないが、OSのページキャッシュには乗るので、その影響を分散させる効果もある。とは言え、今回はイイネの数を抱えるpost_countsにだけ宣言的パーティショニングを施す。フォローや新規投稿や返信の回数よりも、イイネは桁違いに多くなる可能性があるからだ。

CREATE TABLE post_counts (
  post_id BIGINT PRIMARY KEY REFERENCES posts(id) ON DELETE CASCADE,
  like_count INT NOT NULL DEFAULT 0,
  reply_count INT NOT NULL DEFAULT 0
) PARTITION BY HASH (post_id);
ALTER TABLE post_counts ...;

DO $$
DECLARE
  parts int := 8;
  i int;
BEGIN
  FOR i IN 0..parts-1 LOOP
    EXECUTE format(
      'CREATE TABLE IF NOT EXISTS %I PARTITION OF %I
         FOR VALUES WITH (MODULUS %s, REMAINDER %s);',
      'post_counts_p' || i, 'post_counts', parts, i
    );
  END LOOP;
END$$;

パーティションの数は8個にしている。パーティショニングしない場合に比べて、1回のVACUUMの時間の期待値は1/8になり、頻度は8倍になる。デッドタプルの総容量のテーブルサイズに対する比率が最悪値0.1で期待値0.05なのは変わらないが、中心極限定理で分散は減る。パーティションの数は別に16個でも32個でも良いのだが、多くし過ぎると収穫逓減の法則が働き、さらに後述の副作用が悪化する。

VACUUMの負荷が時間分散されるという美点を知ると、全部のテーブルに宣言的パーティショニングをかける誘惑に駆られる。しかし、そうすべきではない。宣言的パーティショニングを使うと、全てのクエリにおいて、読み書きすべきテーブルが倍増する。異なるテーブルのデータは異なるページに置かれるため、操作対象のテーブルが増えればページも増える。SNSのクエリは対象が最新データに参照局所性を持つが、過度のパーティショニングはその効用を落としてしまう。

宣言的パーティショニングが施された子テーブルを参照するクエリが効率的に実行されるかは、絞り込み条件でパーティションプルーニングが利くかどうかにかかっている。つまり、どのパーティションに該当のレコードがあるかどうかをクエリとパーティションルールだけで判定できるかどうかだ。今回の使い方だと、リスト系のクエリにおいては、``LEFT JOIN post_counts pc ON pc.post_id = p.id`` という感じで、JOIN句の中で主キーの完全一致で検索される。更新系でも ``WHERE post_id = ?`` という完全一致で検索される。ハッシュ関数によるパーティショニングは完全一致によるパーティションプルーニングに対応する。さて、その場合、ハッシングの効果で探索範囲が限定され、log2(8)=3回だけB主キーのB木インデックスの比較回数が減ることで、時間効率は上がるだろうか。おそらくそうではない。ハッシュ関数の実行コストで比較関数3回削減の分はチャラになるだろう。B木は多分木なので木の深さはほとんど変わらない。そして、参照するページが多様になると、CPUのL3キャッシュのヒット率が下がる。よって、パーティションプルーニングが効いたとしても、測定不能な程度ではあるが、おそらく遅くなるだろう。

パーティションを主キーで行うなら、主キー以外の絞り込み条件にはパーティションプルーニングが利かない。例えば、usersテーブルのnickname前方一致や、postsテーブルのowned_by完全一致には、パーティションプルーニングが利かない。その場合、全てのパーティションのインデックスを検索した結果をマージするという非効率な処理を行うことになる。これは実運用上は許容できない。ゆえに、参照局所性云々の前に、パーティションプルーニングが利かない条件のクエリを投げているテーブルには宣言的パーティションを施すのは現実的ではない。

event_logsテーブルとnotificationsテーブル

自分がフォローされたり、自分の投稿がイイネされたり、自分の投稿に返信をもらったりした場合、自分が言及されたりした場合、その通知を受け取る機能がある。それらの個々のイベントを全て通知されても鬱陶しいので、通知は日付とリソースの単位でまとめられる。「18 people including Alice, Bob, Nancy have given likes to your post "..." (2025-08-22)」みたいな通知カードになる。ユーザが個々の通知カードをクリックすると、未読状態から既読状態になる。

以上の要件を満たすため、まずはフォローとイイネと返信と言及のイベントを、event_logsテーブルに入れる。そのスキーマは以下のものだ。

CREATE TABLE event_logs (
  partition_id SMALLINT NOT NULL,
  event_id BIGINT NOT NULL,
  payload VARCHAR(65535) NOT NULL,
  PRIMARY KEY (partition_id, event_id)
);
CREATE INDEX event_logs_event_id_hash ON event_logs USING HASH (event_id);

partition_idは、通知先のユーザIDに対する256の剰余で、[0,255] の値を持つ。event_idはイベント発生時刻を元にしたSnowflake IDだ。partition_idとevent_idの複合キーが主キーであり、勝手にインデックスが張られる。よって、特定のpartition_idに属するレコードをevent_idの昇順で取得するクエリが効率化する。

event_idにハッシュインデックスを張っていることは特筆すべきだ。これは普段のクエリでは使わないが、何らかのログ解析の際にイベントIDで効率的に検索するために存在する。なお、event_idにユニーク制約をつけてもインデックスが作られるので検索性は確保できる。しかし、それでBツリーインデックスが作られると、そちらを使って非効率なクエリ実行計画が立てられる不都合が発覚したので、仕方なくハッシュインデックスにしている。PostgreSQLにはMySQLのようなUSE INDEX文がないのが悔やまれる。

payloadにはイベントの内容のJSONが入っている。例を示す。

{"type": "follow", "followeeId": "9901000000000001", "followerId": "0001000000000003"}
{"type": "like", "postId": "9902500000001000", "userId": "0001000000000003"}
{"type": "reply", "postId": "198D9E3364600000", "userId": "0001000000000004", "replyToPostId": "9902500000001000"}
{"type":"mention", "postId":"0002000000000025", "userId":"0001000000000021", "mentionedUserId":"0001000000000302"}

イベントログを読み取るワーカーは複数居て、並列処理を行う。各ワーカーは自分が担当するpartition_idの範囲を知っていて、それに相当するRedisのレコードを監視している。各ワーカーは、イベントログの追加が通知される度に、該当の各パーティションで最大100個のイベントを読み込む。したがって、各パーティションで最後に読んだIDを記録するために、event_log_cursorsテーブルを用意する。

CREATE TABLE event_log_cursors (
  consumer VARCHAR(50) NOT NULL,
  partition_id SMALLINT NOT NULL,
  last_event_id BIGINT NOT NULL DEFAULT 0,
  updated_at TIMESTAMPTZ NOT NULL DEFAULT now(),
  PRIMARY KEY (consumer, partition_id)
);

consumerはワーカーの種類を識別するためにあるが、現状では "notification" しかない。それとpartition_idの複合キーが主キーなので、両者を指定すると効率的にレコードが取得できる。値として重要なのはlast_event_idだけだ。これは最後に処理したevent_idが入っていて、それより大きいIDのイベントログから読み始めれば良いとわかる。updated_atは追跡用の飾りだ。

読み出したイベントは、各ユーザの各リソースの各日を単位としてまとめて通知レコードになる。それを格納するのがnotificationsテーブルだ。

CREATE TABLE notifications (
  user_id BIGINT NOT NULL REFERENCES users(id) ON DELETE CASCADE,
  slot VARCHAR(50) NOT NULL,
  term VARCHAR(50) NOT NULL,
  is_read BOOLEAN NOT NULL DEFAULT FALSE,
  payload VARCHAR(65535) NOT NULL,
  updated_at TIMESTAMPTZ NOT NULL,
  created_at TIMESTAMPTZ NOT NULL DEFAULT now(),
  PRIMARY KEY (user_id, slot, term)
) PARTITION BY HASH (user_id);
CREATE INDEX idx_notifications_user_read_ts ON notifications(user_id, is_read, updated_at);
CREATE INDEX idx_notifications_created_at ON notifications(created_at);

post_countsテーブルと同様に、notificationsも宣言的パーティションで8つに分割している。フィルファクタを75%にしているのもpost_countsと同じだ。event_logsテーブルはレコードがINSERTとDELETEのみだが、notificationsはUPDATEが頻繁に実行されてデッドタプルが溜まりやすい。更新系の負荷が最も高いのはnotificationsテーブルかもしれない。よって、VACUUMの負荷を平準化するために宣言的パーティションを導入する価値がある。ほとんどのクエリはuser_idによるパーティションプルーニングが利くので、宣言的パーティションによる性能劣化はほぼ無い。

ユーザはuser_idで識別する。slotはリソース種別を表し、ユーザ自身が対象であるフォローでは「follow」という決め打ちの値で、投稿が対象であれば「like:{postId}」や「reply:{postId}」の形式の値になる。termはローカル時間の日付だ。スキーマ上は日付じゃなくても適当な期間ラベルをつけられるようになっている。is_readは未読既読の管理フラグで、updated_atとcreated_atは更新時刻と作成時刻だ。user_idとis_readとupdated_atの複合インデックスがあることで、各ユーザの既読通知の一覧と未読通知の一覧を効率的に取得できる。

通知のpayloadはJSONデータであり、その通知レコードに関わるユーザ数や投稿数とともに、最新10件の履歴を入れる。例を示す。recordsの要素にはuserNicknameやpostSnippetなどの属性が足されることがある。

follow => {"records": [{"ts": 1756002248514, "userId": "0001000000000004"}, {"ts": 1756002138545, "userId": "0001000000000003"}], "countUsers": 2}
like => {"records": [{"ts": 1756002187871, "userId": "0001000000000004"}, {"ts": 1756002077724, "userId": "0001000000000003"}], "countUsers": 2}
reply => {"records": [{"ts": 1756002203216, "postId": "198D9E3364600000", "userId": "0001000000000004"}, {"ts": 1756002097802, "postId": "198D9E19A8700000", "userId": "0001000000000003"}, {"ts": 1756002094769, "postId": "198D9E18EAE00000", "userId": "0001000000000003"}], "countPosts": 3, "countUsers": 2}
mention => {"records": [{"ts": 1764465975, "postId": "0002000000000025", "userId": "0001000000000021"}], "countUsers": 1, "countPosts": 1}

event_logsテーブルとnotificationsテーブルは急速に肥大化するので、古いレコードを定期的に削除する必要がある。通知作成のワーカーがその処理を行う。event_logsに関しては、event_idから日付を逆算して発生から31日以上のものを削除する。notificationsに関しては、created_atが31日以前のものを削除する。この削除処理を効率化するためにcreated_atにインデックスを張っている。この処理にはパーティションプルーニングが利かないが、そもそも全パーティションを対象にする操作なので、パーティションを特定する必要がない。削除処理は更新処理が1000回実行されるされる毎に1回だけ実行される。

通知対象の各イベントを発生させる処理で、notificationsテーブルを直接更新すれば、わざわざ非同期処理にしなくても通知機能は実現できる。しかし、通知機能はキューとワーカーを使った非同期処理で実装すべきだ。理由は三つある。一つ目は、保守性のためだ。通知カードを作るための複雑な処理をバックエンドサーバから分離することで、コードの見通しが良くなり、更新作業も楽になる。二つ目は、性能のためだ。通知カードを作るためのクエリが応答の遅延を引き起こすことを避けねばならない。三つ目は、レースコンディションの回避のためだ。既存の通知カードを読み出してからまた書き戻すという処理をするので、もし同時更新されるとデータに不整合が起きる可能性がある。今回のキューはユーザIDでパーティショニングしているので、各ワーカーが自分のパーティションのデータを順番に処理する限り、同一ユーザの通知カードが同時に更新されることはない。それでいて、ワーカーは256個まで並列で動かせるので、並列処理性能も十分だ。

通知のスパム対策について考える。フォローとイイネと返信は、通知対象ユーザが所有するリソースに対する操作を通知するものなので、ブロック機能で対処できる。歓迎されざるユーザを逐一ブロックするか、自分にblock_strangersフラグを立てれば良い。しかし、言及がなされる投稿は、通知対象ユーザが所有するリソースではない。他人の投稿の内容に対して制約を課すことは、システム設計の観点でも、言論の自由という観点でも、許容できない。よって、言及すること自体を禁止することはできない。そもそも、知らない人に言及されたのを通知されると、人気者の通知が膨大になりすぎて使い物にならなくなる。よって、言及の通知は、通知対象ユーザが投稿主をフォローしている場合に限定する。

その他のテーブル

ai_modelsテーブルは、AIエージェントを動かすAIモデル毎に、ラベルとサービス名とモデル名を管理するものだ。AIモデルは頻繁に更新されるため、usersテーブルに直接モデル名を持たせるのではなく、「advanced」「balanced」「basic」などのラベルを介してai_modelsテーブルを参照する。具体的なサービス名やモデル名はai_modelsテーブルに集中化され隠蔽されるので、モデルが更新された際に追従するのが楽になる。それぞれのラベルに対話チャット用のモデルと特徴量ベクトル抽出用のモデルが紐づけられている。それ以外にもAI関連のテーブルがあるが詳細については別の記事に譲る。

削除処理

ユーザや投稿を消す方法として、レコードそれ自体をデータベースから消す物理削除方式と、削除したというフラグを立てる論理削除方式がある。それれぞれ一長一短があり、どちらにすべきかはデータの性質や管理方針によって決めるべきだ。物理削除方式は、消したレコードの分だけデータ容量が削減でき、ユーザが自身の情報管理ができるという点で優れている。しかし、間違って消したデータは元には戻せない。論理削除方式は、フラグを落とすだけでに戻せる。しかし、データ容量は削減できないし、ユーザが削除を所望した情報がDB内に残っているという問題がある。無意味なデータに更新する手はあるが、投稿したという事実は消えないし、返信も残る。

今回は、全てのデータは、物理削除方式を採っている。SNSでわざわざ過去の投稿を消して回る人はほとんどいないので、容量削減の効果はほぼない。不正行為で大量のデータを作られたときには、物理削除で容量を取り戻せることは嬉しいが、それは特別対応すればいい話しなので、通常運用のあるべき姿と混同すべきではない。それでも、ユーザが消すと決めたデータを持ち続けたくないので、後腐れなく消したい。消してしまえば、おそらく厄介事が起きる復旧機能を要望されることもない。

ただし、物理削除は、外部キー制約にまつわる設計判断をきちんとしなければならない。ユーザを消した場合、そのユーザの投稿もON DELETE CASCADEで削除される。フォロー関係やブロック関係も同様だ。投稿につけられたイイネも芋づる式に削除される。そうすると、ある人気ユーザが過去に1000件の投稿をしていて、各々が1000件くらいイイネをもらっているとすると、100万件のレコードが一気に消されることになる。消した行はデットタプルとしてマークが付けられるだけだが、そのマークを書き込む操作を各ページにすることになるので、キャッシュが一気に汚れることになる。関連するインデックスはノード自体を書き換えることになり、その負荷も無視できない。これを緩和するには、非同期処理で少しずつ削除処理を進めるしかない。具体的には、削除すべきユーザIDを専用テーブルに保存して、ワーカが定期的に起動して一定件数の関連リソースを消して、全て終わってからユーザ自体を消すという処理をすべきだ。とはいえ、非同期削除の導入は、よっぽどサービスが成長してからで良いだろう。

postsテーブルのreply_toに外部キー制約を持たせずに、投稿の削除に連動してその返信を更新しないようにしているのは、ユーザ削除処理の負荷を軽減するためでもある。ある人気ユーザがpostsテーブル1000件のページが汚れるのは仕方ないとしても、それひ紐づいた返信が平均100件ずつあたとすると、postsテーブルの10万件の更新されることになる。削除ではなく更新だ。追記型だと更新は複製を作る行為なので、postsテーブルのレコードが一気に10万件複製されるのはだいぶまずい。

ビジネスモデルと運用要件によっては、古いデータを自動的に削除してデータ容量を一定に維持する措置を取るかもしれない。その際には、物理削除でないと意味がない。全てのテーブルにはSnowflake IDまたはタイムスタンプの情報がついているので、一定以上古いデータを消すワーカを実装するのは簡単だ。

VARCHAR vs TEXT

PostgreSQLの主テーブルのシリアライズ方式において、可変長のバイト列は内部的にはVARLENA（variable-length array）と総称される形式になる。126バイト以下のデータは、データサイズを示す1バイトのメタデータをつけて記録され、それを超えるデータはデータサイズを示す4バイトのメタデータをつけて記録される。VARCHAR、TEXT、BYTEA、JSONBなどのデータは全てVARLENAとしてシリアライズされる。

VARCHARとTEXTのどちらを使うべきかという議論があるが、空間効率も処理性能も同じなので、どちらでも良い。VARCHARは文字数の制限があり、TEXTにはそれがない。DBを対象とする全ての入力はデータサイズに制限を設けるべきだが、その制限方法によってVARCHARとTEXTのどちらを使うべきかが決まる。アプリケーション層で文字数の制限をしているなら、VARCHARでも制限するのは二重管理になるのでTEXTが良いという考え方がある。一方で、アプリケーション層では文字数の制限を一切せずに、DB層だけで制限するという考え方もある。

今回は折衷案を取っていて、多くの場所でVARCHARを使っている一方で、アプリケーション層でもデータサイズの制限をしている。基本的にはアプリケーション層で制限をするのだが、万が一忘れてしまった場合でも、致命的なセキュリティホールにならないように、DB層でも緩めの制限をかけるという建付けだ。悪く言えば二重管理なのだが、その管理コストを払ってでも、TEXTよりはVARCHAR(65535)とすることで、事故によるサービス停止のリスクを低減している。

なお、JSONをVARCHARやTEXTとして記録するか、JSONBとして記録するかでは、空間効率に差が出る。VARCHAR等の場合にはJSONの文字列そのものが記録される一方、JSONBの場合はJSONをオブジェクトとして解釈した後にバイナリシリアライザをかけたデータが記録される。JSONBの方がデシリアライズが速いので、そのオブジェクトの中身をクエリの検索条件にしたり、オブジェクトの中身をインデックスに加えたりするような場合は、JSONBに利点がある。しかし、空間効率は文字列としてのJSONの方が良い場合がほとんどなので、検索条件にしないなら、文字列として扱った方が良い。そして、そもそも検索条件にするフィールドを含むなら、そのフィールドの値を列として独立させたほうが良い。

パスワードハッシュ関数

パスワードの平文を持つと、DBデータの漏洩時に即座に大事故になる。Fakebook上の投稿やプロファイルデータは全てが公開情報という建付けなのでそれらの漏洩の被害は少ないが、他のサービスと使い回しているかもしれないパスワードが漏れる事態だけは道義的にまずい。運営者である私が他人のパスワードが見られる立場にある事自体が気持ち悪い。よって、パスワードは必ずハッシュ化することになるが、ハッシュ関数の選択が重要になる。古き良きMD5やSHA系列のような高速ハッシュ関数は、現代ではほぼ無力だ。高速かつ省メモリで計算できる設計なので、GPUによる並列ブルートフォース攻撃に弱く、短かったり頻出パターンだったりする弱いパスワードは数分や数時間で解読されてしまう。他のサービスと使い回している場合には当然弱いことが多いので、高速ハッシュ関数の値が漏洩するのは平文が漏洩するのと同等の被害になる。

よって、最近のサイトでは、Argon2やScryptやBcryptなどの、敢えて時間効率と空間効率を悪くしたハッシュ関数を使うことが定番となっている。実行に数100ミリ秒と数MBの作業領域を要するなら、GPUでの並列処理が難しくなる。ログインの度にサーバ側でそのリソースを食うことになるが、セッションが維持される限りは再ログインは必要ないので、頻度は低い。防御側としては許容範囲だが、攻撃側としては現実的でない負荷となるコストパラメータをハッシュ関数に設定することになる。

今回はパスワードのハッシュ化にscryptを使っている。ハッシュ値20バイトとソルト12バイトを連結した32バイトのバイナリとしてDBに保存している。ハッシュ値20バイトの衝突率は1/(2^160)で、ほぼゼロだ。ソルトの衝突率は1/(2^96)なので、世界の全サービスのDBが漏洩しても同じソルト値を見つける確率はほぼゼロだ。ゆえに、現状においては十分な強度と言えるだろう。

しかし、技術は進歩するので、現状において十分な強度であっても、将来的に大丈夫な保証はない。よって、ハッシュ関数のコストパラメータ等も値に連結したself-containedな値を保存することが推奨されていたりもするが、今回はそうしなかった。全てのレコードで同じ値を持たせるのは冗長なので、それらを設定ファイルに逃がすことで、空間効率を向上させるのを優先した。もしも、やんごとない事情でハッシュ関数を置き換える必要が生じたとしても、古いアルゴリズムの値と新しいアルゴリズムの値は区別できるからだ。古いアルゴリズムでの検証をパスするなら古い値で、新しいアルゴリズムでパスするなら新しい値なので、移行期間中は双方を試して、古い値でログインしたなら新しい値を生成して更新すれば良い。新旧でサイズを変えれば、ハッシュ関数を実行しなくても区別できる。現実的には、移行したユーザにフラグを立てていき、移行期間終了間際にフラグが立っていないユーザに通知を送る必要がある。結局フラグで管理するのだから、ハッシュ値がself-containedである意味はあまりない。

アラインメント

PostgreSQLは、主テーブルの行レイアウトを設定する際に、アラインメントを行う。通常、全ての行データは、8バイト境界を持つ。すなわち、ページ上のオフセットが8で割り切れる位置に記録される。また、レコード内の数値型は、その型に応じてアラインメントされる。例えば8バイトであるBIGINT型やTIMESTAMPTZ型は8バイト境界を持ち、4バイトであるINT型やREAL型は4バイト境界を持ち、2バイトであるSMALLINT型は2バイトのアラインメントを持つ。VARCHARやTEXTなどのVARLENA型は、先頭に長さの数値を持つので、4バイトアラインメントを持つ。そうすることで、メモリに読み込んだ時に数値型のデータのアドレスがアラインメントされるため、そのメモリ領域をCPUがそのまま数値として評価できるようになる。なお、VARLENA型は長さが126文字以下だと長さ情報を1バイトで保持するので、アラインメントがなくなる。

アラインメントを成立させるためには、パディングが用いられる。例えば、レコードの先頭がSMALLINTであり、その直後にINTが宣言されている場合、先頭のSMALLINTの後ろに2バイトのパディングが置かれて、INTの4バイト境界が達成される。よって、``SMALLINT, SMALLINT, INT`` という並びだと全体が8バイトを消費するが、``SMALLINT, INT, SMALLINT`` という並びだと10バイトを消費してしまう。

アラインメント最適化をする以前は、postsテーブルの属性は以下のように並べていた。そのアラインメントを考察してみよう。

id BIGINT : 8バイト境界（パディング不要）
locale VARCHAR : 短いのでアラインメントなし（パディング不要）
snippet VARCHAR : 4バイト境界（最大3バイトのパディング）
owned_by BIGINT : 8バイト境界（最大7バイトのパディング）
reply_to BIGINT : 8バイト境界（パディング不要）
allow_likes BOOLEAN : アラインメントなし（パディング不要）
allow_replies BOOLEAN : アラインメントなし（パディング不要）
published_at TIMESTAMPTZ : 8バイト境界（確実に6バイトのパディング）
updated_at TIMESTAMPTZ : 8バイト境界（パディング不要）

localeが可変長なので、直後のsnippetの前にパディングが置かれる可能性がある。snippetも可変長なので、直後のowned_byの前にパディングが置かれる可能性がある。また、reply_toで8バイト境界になった後にallow_likesとallow_repliesが2バイト消費するので、published_atの前に確実に6バイトのパディングが発生する。可変のパディングでは最大長の半分が平均長になる。よって、合計は、3/2+7/2+6で、平均11バイトのパディングが発生することになる。

パディングを減らすために、以下のように並び替えた。パディングが完全に不要になったので、11バイトの節約ができた。

id BIGINT : 8バイト境界（パディング不要）
owned_by BIGINT : 8バイト境界（パディング不要）
reply_to BIGINT : 8バイト境界（パディング不要）
published_at TIMESTAMPTZ : 8バイト境界（パディング不要）
updated_at TIMESTAMPTZ : 8バイト境界（パディング不要）
snippet VARCHAR : 4バイト境界（パディング不要）
locale VARCHAR : 短いのでアラインメントなし（パディング不要）
allow_likes BOOLEAN : アラインメントなし（パディング不要）
allow_replies BOOLEAN : アラインメントなし（パディング不要）

インプレース更新があるデータベースでは、レコードサイズの増分がパディングに吸収されてインプレース更新ができる確率が上がるという、パディングのわずかなメリットがある。しかし、PostgreSQLはインプレース更新をしないので、パディングのメリットは皆無である。

属性を並び替えるだけで空間効率が上がるが、論理的でない順番で属性を並べると可読性が落ちるという問題が出るかもしれないので、並び替えによるアラインメント最適化を実施するかどうかは慎重に判断すべきだ。今回のpostsテーブルに関しては、レコード数が多く、参照頻度が高く、空間効率の向上が性能上の利点に確実につながる。そして、最適化後の順番も一定の読みやすさを保っている。近い将来に、規約違反の投稿を意味するis_violativeなどのフラグを追加するかもしれないが、それらは末尾に追加することで可読性と空間効率を維持できる。よって、総合的に得だと判断したために、実施した。usersテーブルも同様にアラインメント最適化を施した。それ以外のテーブルにも最適化の余地があるが、費用対効果が低いので実施していない。

なお、published_atとupdated_atのそれぞれを8バイトのTIMESTAMPTZから4バイトのINTに変えると、さらに8バイト節約できる。公開日時や更新日時にミリ秒単位の精度は不要なので、TIMESTAMPTZはオーバースペックとも言える。しかし、INTでUNIX時間を表すと2038年にオーバーフローするので、エポックを未来にずらすとか、値を60で割って分単位の精度に落とすとかの工夫が求められる。8バイトの節約は魅力的だが、保守性への悪影響が大きいので、その最適化も見送った。

シーダ

DBの初期データを登録するには、シーダと呼ばれる機能を実装する必要がある。本番環境で運用開始時に揃えておくべきデータを投入するモードと、開発環境でテスト用データを投入するモードがあるのが普通だろう。シーダの最も単純な実装は、DBに接続してSQL文を実行するものだ。少なくとも、スキーマ定義などのブートストラップ手順はその方法でやるのが率直だ。しかし、その後のデータ登録は、アプリサーバのエンドポイントにリクエストを送る方式にすべきだ。すなわち、管理者アカウントでログインしてから、通常の管理用APIを使って、ユーザ作成や投稿作成を行うのだ。

管理者アカウントはSQLによるブートストラップ手順で作るのが率直だが、その際に問題になるのが、パスワードの指定である。パスワードのハッシュ関数のロジックはアプリサーバ側にしかないので、ハッシュ値をSQL内のリテラルとして書き込むには、アプリ側のユーティリティを使って任意の文字列のハッシュ値を印字するユーティリティが必要になる。パスワードが空文字列やNULLの場合にはダミーのパスワードでログインできるとかいう仕様を設けることも考えられるが、潜在的なセキュリティホールになってしまうので、ユーティリティをちゃんと書いた方が良い。

テスト用のデータを登録する機能も重要だ。システムテストやユーザテストでフロントエンドでページネーションのテストをするには、複数ページで表示されるデータセットを作っておかねばならない。クエリの分析や負荷テストをするには、実運用を見越した大量のデータを登録する必要がある。ユーザや投稿を登録するだけではなく、フォローしたりイイネしたりブロックしたりといった更新操作の多くはシーダで再現可能にしておくべきだ。開発の初期段階でシーダを作っておくと、後工程が楽になる。

整合性の検証と回復

今回のスキーマでは、ドメインキー正規形に違反している属性は限定的だ。usersテーブルのcount_followeesなどのカウンタ属性と、postsテーブルのcount_likesなどのカウンタ属性と、usersテーブルとpostsテーブルのsnippetがそれにあたる。主属性と従属属性の更新はトランザクション内で行われるので不整合が起こることは正常系では無いはずだが、何らかのバグや管理操作のミスを含む異常系では不整合が想定できる。たとえそれらの不整合が起きたとしてもカウンタがずれたりスニペットの表示が崩れたりするだけなので、サービス運営にとって致命傷になるわけではないが、ユーザからクレームが来たら対処できる程度の準備はしておくべきだ。

validate_userやらvalidate_postやらのユーティリティ関数を書いておくと安心だ。ユーザIDや投稿IDを与えると、その整合性検証や回復処理を行うのだ。開発初期にはコマンドラインでそれらを呼び出してテストして、実運用において必要であればエンドポイントを作って管理用ユーティリティから実行できるようにする。

最も単純クエリの分析

ここからは、実際のコードから実行されるクエリの分析をしていく。まず、全ての投稿の中から最新20件を取り出す処理を考える。以下のクエリは実際には使われてないが、説明のための単純化したものを紹介する。デフォルトでは返信以外の投稿を一覧するため、reply_toがNULLであるという条件をつける。

SELECT
  p.id, p.owned_by, p.reply_to,
  p.allow_likes, p.allow_replies, p.updated_at
FROM posts p
WHERE reply_to IS NULL
ORDER BY p.id DESC OFFSET 0 LIMIT 20;

postsテーブルには、reply_toがNULLのレコードだけを対象としたIDの部分インデックスが設けられているため、そのインデックスを引くだけで処理が完了する。全ての投稿数をPと置くと、計算量はO(log(P))で済む。これは、Pが莫大になっても性能に問題が出ないことを意味している。

PostgreSQLでは、クエリごとの実行計画をEXPLAIN文で調べることができる。以下の出力が得られる。インデックスを使って済むと言っている。推定3024件のレコードを持つインデックスを逆向きに操作して、20件がヒットした段階で処理を打ち切ることが示唆されている。つまりめちゃくちゃ効率的に動くということだ。

Limit (cost=0.29..2.61 rows=20 width=34)
 -> Index Scan Backward using idx_posts_root_id on posts p (cost=0.29..3512.64 rows=30210 width=34)

listPosts

実運用上は、各投稿の著者のユーザIDを名前に解決したり、各投稿につけられたタグ情報を結果に含めるために、別のテーブルをJOINすることになる。それを実装しているのが、バックエンドのpostsService.listPostsメソッドだ。reply_toがNULLであるという条件をつけると、実際のクエリは以下のものになる。

SELECT
  p.id, p.snippet, p.owned_by, p.reply_to,
  p.allow_likes, p.allow_replies, p.updated_at,
  u.nickname AS owner_nickname, pu.nickname AS reply_to_owner_nickname,
  ARRAY(SELECT pt2.name FROM post_tags pt2
    WHERE pt2.post_id = p.id ORDER BY pt2.name) AS tags
FROM posts p
JOIN users u ON p.owned_by = u.id
LEFT JOIN posts parent_post ON p.reply_to = parent_post.id
LEFT JOIN users pu ON parent_post.owned_by = pu.id
WHERE p.reply_to IS NULL
ORDER BY p.id DESC OFFSET 0 LIMIT 20;

最も単純な例と同様にインデックスが使われて、結果を返却するはずだ。その過程で、post_tagsテーブルとusersテーブルを結合している。タグに関しては返却の各行に対応して投稿IDが一致するタグをサブクエリで調べて取得して埋め込んでいる。ユーザ名に関しては、owned_byのIDをユーザ名に解決するためと、reply_toの投稿のowned_byのIDをユーザ名に解決するために、2回に分けてJOINしている。

これの計算量を考えよう。全ユーザ数をUと置き、全投稿数をPと置く。タグの数はおそらく投稿数の1%くらいの数になるだろうが、Pに比例するのでPとして扱う。まず、該当の投稿のリストを得るのに、インデックスが利けば、O(log(P))+O(20)の計算量がかかる。20は定数なので消えて、O(log(P))になる。そして、ヒットした20件の各々に対し、タグとユーザ名を解決する。インデックスが利けば、タグ取得はO(20･log(P))で、ユーザ名取得はO(20･log(U))だ。20は定数なので消えて、O(log(P))とO(log(U))になる。UはPよりも十分に少ないと仮定すると、全体の支配項はO(log(P))ということになる。つまり、計算量は最も単純な例の時と同じである。

EXPLAIN文で実行計画を調べると、以下の出力が得られる。投稿でヒットしたレコードの各々に対して処理を行うNested Loopがあり、そこでJOINの処理を行っている。結合先のテーブルからデータを取り出すにあたっては全てインデックスが使われ、一部はキャッシュも使われていて、DB本体のシーケンシャルスキャン（Seq Scan）やインデックスのシーケンシャルスキャン（Filter）がひとつもなく、全てがインデックスの条件付き絞り込み（Index Cond）の理想的な処理になっていることがわかる。

Limit (cost=1.17..106.53 rows=20 width=133)
 -> Nested Loop Left Join (cost=1.17..159137.24 rows=30210 width=133)
    -> Nested Loop Left Join (cost=0.89..14010.38 rows=30210 width=100)
       -> Nested Loop (cost=0.58..13250.15 rows=30210 width=92)
          -> Index Scan Backward using idx_posts_root_id on posts p (cost=0.29..3512.64 rows=30210 width=83)
          -> Memoize (cost=0.30..0.41 rows=1 width=17)
             Cache Key: p.owned_by
             Cache Mode: logical
             -> Index Scan using users_pkey on users u (cost=0.29..0.40 rows=1 width=17)
                Index Cond: (id = p.owned_by)
       -> Memoize (cost=0.30..0.46 rows=1 width=16)
          Cache Key: p.reply_to
          Cache Mode: logical
          -> Index Scan using posts_pkey on posts parent_post (cost=0.29..0.45 rows=1 width=16)
             Index Cond: (id = p.reply_to)
    -> Index Scan using users_pkey on users pu (cost=0.29..0.35 rows=1 width=17)
       Index Cond: (id = parent_post.owned_by)
    SubPlan 1
     -> Index Only Scan using post_tags_pkey on post_tags pt2 (cost=0.42..4.45 rows=2 width=7)
        Index Cond: (post_id = p.id)

listPostsByFollowees

FakebookのSNSとしての典型的なビューは、「自分がフォローしているユーザの投稿の一覧」を見ることである。これがログイン直後のデフォルトのビューでもある。このクエリが効率的に処理できるかどうかがSNSの性能を決めると言って良い。

基本戦略としては、表示件数が20件という定数であることを利用して計算量の削減を図る。全フォロイーの中から直近の投稿が新しい20人を選び、その20人の各々の最新の投稿20件を取り出すことで、最大400件のソートしかしないことが保証できる。実際のクエリは以下のものだ。

WITH
all_followees AS (
  SELECT followee_id
  FROM user_follows
  WHERE follower_id = 0x0001000000000013),
active_followees AS (
  SELECT DISTINCT ON (p2.owned_by) p2.owned_by, p2.id AS last_id
  FROM posts p2
  WHERE p2.owned_by IN (SELECT followee_id FROM all_followees)
  ORDER BY p2.owned_by, p2.id DESC),
top_followees AS (
  SELECT owned_by
  FROM active_followees
  ORDER BY last_id DESC LIMIT 20),
candidates AS (
  SELECT pid.id
  FROM top_followees tf
  JOIN LATERAL (
    SELECT p2.id
    FROM posts p2
    WHERE p2.owned_by = tf.owned_by
    ORDER BY p2.id DESC LIMIT 20) AS pid ON TRUE),
top_posts AS (
  SELECT id
  FROM candidates
  ORDER BY id DESC OFFSET 0 LIMIT 20)
SELECT
  p.id, p.snippet, p.owned_by, p.reply_to,
  p.allow_likes, p.allow_replies, p.updated_at,
  u.nickname AS owner_nickname, pu.nickname AS reply_to_owner_nickname,
  ARRAY(SELECT pt2.name FROM post_tags pt2
    WHERE pt2.post_id = p.id ORDER BY pt2.name) AS tags
FROM top_posts t
JOIN posts p ON p.id = t.id
JOIN users u ON p.owned_by = u.id
LEFT JOIN posts parent_post ON p.reply_to = parent_post.id
LEFT JOIN users pu ON parent_post.owned_by = pu.id
ORDER BY t.id DESC;

クエリが込み入っているので、部分ごとに解説しよう。

フォローしているユーザのIDの一覧をall_followeesというビューとして作る。
all_followeesの各々について最新の投稿IDを紐づけたactive_followeesというビューを作る。
active_followeesの内容を投稿IDでソートして、最も最近に投稿をしたトップ20人のユーザIDの集合であるtop_followeesというビューを作る。
top_followeesの各ユーザIDにJOIN LATERALして、各ユーザの最新投稿IDを20件ずつ取り出したcandidatesというビューを作る。
candidatesの最大400件の投稿IDをソートして、最新20件に絞ったtop_postsというビューを作る。
top_postsの各々のIDに対して、listPostsと同様に、各種属性を肉付けする。

これの計算量を考えよう。全ユーザ数をUと置き、全投稿数をPと置き、フォローしているユーザ数をFと置く。フォローしているユーザの一覧を引くのは、インデックスが利けば、O(log(U))だ。フォローしているユーザの各々の最新投稿を調べるのは、インデックスが利けば、O(F･log(P))だ。F人から最新アクティブユーザ20人を選ぶのはtop-kヒープなので、O(F･log(20)) で、20は定数なので、O(F)だ。最新アクティブユーザ20人の各々の最新投稿20件を取り出すと、400件が取れる。400件から20件を選ぶのもtop-kヒープなので、O(400･log(20))で、400も20も定数なので、O(1)だ。そして20件の各々に肉付けする処理は、全てインデックスが利くなら、O(20･log(P))で、20は定数なので、O(log(P))だ。つまり、UはPよりも少ないと仮定すると、全体の計算量の支配項はO(F･log(P))ということになる。Pは莫大に大きくても大丈夫だし、Fはそこそこ大きくても大丈夫ということになる。

あとは、各処理でちゃんとインデックスが効いているかどうかを確かめれば良い。上述のクエリをEXPLAINにかけてみると、以下の出力が得られる。全てがIndex Condの理想的な実行計画になっていることが確かめられた。

Nested Loop Left Join (cost=77.17..186.79 rows=8 width=141)
 -> Nested Loop Left Join (cost=76.88..148.35 rows=8 width=108)
    -> Nested Loop (cost=76.59..145.31 rows=8 width=100)
       -> Nested Loop (cost=76.31..142.50 rows=8 width=91)
          -> Limit (cost=76.02..76.04 rows=8 width=8)
             -> Sort (cost=76.02..76.04 rows=8 width=8)
                Sort Key: p2_1.id DESC
                -> Nested Loop (cost=28.98..75.90 rows=8 width=8)
                   -> Limit (cost=28.69..28.70 rows=4 width=16)
                      -> Sort (cost=28.69..28.70 rows=4 width=16)
                         Sort Key: p2.id DESC
                         -> Unique (cost=7.56..28.65 rows=4 width=16)
                            -> Incremental Sort (cost=7.56..28.64 rows=4 width=16)
                               Sort Key: p2.owned_by, p2.id DESC
                               Presorted Key: p2.owned_by
                               -> Nested Loop (cost=0.58..28.46 rows=4 width=16)
                                  -> Index Only Scan using user_follows_pkey on user_follows (cost=0.29..8.32 rows=2 width=8)
                                     Index Cond: (follower_id = '281474976710675'::bigint)
                                  -> Index Only Scan using idx_posts_owned_by_id on posts p2 (cost=0.29..10.05 rows=2 width=16)
                                     Index Cond: (owned_by = user_follows.followee_id)
                   -> Limit (cost=0.29..11.77 rows=2 width=8)
                      -> Index Only Scan Backward using idx_posts_owned_by_id on posts p2_1 (cost=0.29..11.77 rows=2 width=8)
                         Index Cond: (owned_by = p2.owned_by)
          -> Index Scan using posts_pkey on posts p (cost=0.29..8.31 rows=1 width=83)
             Index Cond: (id = p2_1.id)
       -> Index Scan using users_pkey on users u (cost=0.29..0.35 rows=1 width=17)
          Index Cond: (id = p.owned_by)
    -> Index Scan using posts_pkey on posts parent_post (cost=0.29..0.38 rows=1 width=16)
       Index Cond: (id = p.reply_to)
 -> Index Scan using users_pkey on users pu (cost=0.29..0.35 rows=1 width=17)
    Index Cond: (id = parent_post.owned_by)
 SubPlan 1
  -> Index Only Scan using post_tags_pkey on post_tags pt2 (cost=0.42..4.45 rows=2 width=7)
     Index Cond: (post_id = p.id)

最新アクティブユーザの各々から表示件数である20件分取得するのは、確実に時系列に最新の投稿を表示するためである。一人のユーザが最新投稿の全てを占める可能性があるからだ。しかし、タイムライン表示で同じユーザの投稿ばかりが占めるというのは嬉しいものではない。そこで、実運用では、ユーザ毎の取得件数をパラメータで指定できるようにして、そのデフォルトは3にする。ソートするのは60件で済むため、より高速化することになる。投稿を取得するコストが軽くなると、最新アクティブユーザを調べるコストの比重が高くなることになる。さらに高速化するには、ユーザ毎の最新投稿時刻をテーブルに分割して持っておくとよい。これも典型的な非正規化だが、O(F･log(P))である支配項がO(F･log(U))になるわけで、確実に効果がある。今回はそこまではやっていないが、タイムラインが重くなったらまず試すべき最適化だ。

ユーザ毎の取得件数を減らすほど、より多くのユーザの最新投稿が表示でき、性能上も利点がある。多数投稿するユーザに関しては、そのユーザの詳細画面から最新投稿一覧を見てもらえば良い。ならば、なぜ1件ではなく3件にするのか。それは、各ユーザの既読の投稿と未読の投稿が1件以上ずつ目に入ると効率が良く、1件足すことでどちらかが0になることを防ぎたいからだ。未読の投稿だけを見ると、そのユーザがもっと未読の投稿をしているかもしれないので、ユーザ詳細画面に遷移して確認したくなる。しかし、ページをめくっているうちにユーザの既読の投稿も目にしている場合、未読の投稿はもうないことがわかる。既読の投稿だけを見るのは、単なる徒労である。投稿のためのアクセスの頻度よりも、閲覧のためのアクセスの頻度の方が高いのが一般的で、多くのユーザが似たような頻度でアクセスすると仮定すると、3件くらいが最もバランスが良さそうだ。とはいえ、最善の設定はユーザ行動分析を経て導くべきだろう。

listPostsLikedByUser

自分がイイネした投稿の一覧を得るには、以下のクエリが使われる。

SELECT
  p.id, p.snippet, p.owned_by, p.reply_to,
  p.allow_likes, p.allow_replies, p.updated_at,
  u.nickname AS owner_nickname, pu.nickname AS reply_to_owner_nickname,
  ARRAY(SELECT pt.name FROM post_tags pt
    WHERE pt.post_id = p.id ORDER BY pt.name) AS tags
FROM post_likes pl
JOIN posts p ON pl.post_id = p.id
JOIN users u ON p.owned_by = u.id
LEFT JOIN posts pp ON p.reply_to = pp.id
LEFT JOIN users pu ON pp.owned_by = pu.id
WHERE pl.liked_by = 0x0001000000000013
ORDER BY pl.created_at DESC OFFSET 0 LIMIT 20;

liked_byでの絞り込みにインデックスが利きさえすれば、計算量はlistPostsと同じくO(log(P))で済むはずだ。あとは実行計画見れば、それが確認できる。

Limit (cost=1.44..106.72 rows=6 width=141)
 -> Nested Loop Left Join (cost=1.44..106.72 rows=6 width=141)
    -> Nested Loop Left Join (cost=1.15..77.90 rows=6 width=108)
       -> Nested Loop (cost=0.86..75.61 rows=6 width=100)
          -> Nested Loop (cost=0.58..73.50 rows=6 width=91)
             -> Index Scan Backward using idx_post_likes_liked_by_created_at on post_likes pl (cost=0.29..23.66 rows=6 width=16)
                Index Cond: (liked_by = '281474976710675'::bigint)
             -> Index Scan using posts_pkey on posts p (cost=0.29..8.31 rows=1 width=83)
                Index Cond: (id = pl.post_id)
          -> Index Scan using users_pkey on users u (cost=0.29..0.35 rows=1 width=17)
             Index Cond: (id = p.owned_by)
       -> Index Scan using posts_pkey on posts pp (cost=0.29..0.38 rows=1 width=16)
          Index Cond: (id = p.reply_to)
    -> Index Scan using users_pkey on users pu (cost=0.29..0.35 rows=1 width=17)
       Index Cond: (id = pp.owned_by)
    SubPlan 1
     -> Index Only Scan using post_tags_pkey on post_tags pt (cost=0.42..4.45 rows=2 width=7)
        Index Cond: (post_id = p.id)

listUsers

usersテーブルを操作するusersServiceという実装にも各種メソッドがあって、それぞれクエリを発行している。どれも軽い処理だが、ユーザの一覧を出すlistUsersだけは、注意を要する。例えば、ユーザのニックネームの前方一致条件で絞り込みを行いつつ、フォロイーもしくはフォロワーを優先して表示するという特殊機能がある。そのクエリは以下のものだ。

SELECT
  u.id, u.email, u.nickname, u.is_admin, u.snippet, u.avatar,
  u.ai_model, u.updated_at
FROM users u
LEFT JOIN user_follows f1 ON
  f1.follower_id = 0x0001000000000013 AND f1.followee_id = u.id
LEFT JOIN user_follows f2 ON
  f2.follower_id = u.id AND f2.followee_id = 0x0001000000000013
WHERE LOWER(u.nickname) LIKE 'user0002%'
ORDER BY
  (u.id = 0x0001000000000013) DESC,
  (f1.follower_id IS NOT NULL) DESC,
  (f2.follower_id IS NOT NULL) DESC,
  u.id ASC OFFSET 0 LIMIT 20;

LIKE演算子による前方一致は、インデックスが利くので、絞り込みを効率的に行うことができる。絞り込んだ上で最後にソートで順位付けするため、ヒット件数が少なければ高速に動く。EXPLAIN文の結果は以下である。

Limit (cost=25.12..25.13 rows=3 width=309)
 -> Sort (cost=25.12..25.13 rows=3 width=309)
    Sort Key: ((u.id = '281474976710675'::bigint)) DESC, ((f1.follower_id IS NOT NULL)) DESC, ((f2.follower_id IS NOT NULL)) DESC, u.id
    -> Nested Loop Left Join (cost=0.87..25.10 rows=3 width=309)
       Join Filter: (f2.follower_id = u.id)
       -> Nested Loop Left Join (cost=0.58..16.73 rows=3 width=314)
          Join Filter: (f1.followee_id = u.id)
          -> Index Scan using idx_users_nickname_id on users u (cost=0.29..8.31 rows=3 width=306)
             Index Cond: ((lower((nickname)::text) ~>=~ 'user0002'::text) AND (lower((nickname)::text) ~<~ 'user0003'::text))
             Filter: (lower((nickname)::text) ~~ 'user0002%'::text)
          -> Materialize (cost=0.29..8.33 rows=2 width=16)
             -> Index Only Scan using user_follows_pkey on user_follows f1 (cost=0.29..8.32 rows=2 width=16)
                Index Cond: (follower_id = '281474976710675'::bigint)
       -> Materialize (cost=0.29..8.31 rows=1 width=8)
          -> Index Scan using idx_user_follows_followee_created_at on user_follows f2 (cost=0.29..8.31 rows=1 width=8)
             Index Cond: (followee_id = '281474976710675'::bigint)

さて、多くの処理がインデックスを使って行われているので、このクエリは一見速そうだ。実際、絞り込みの文字列が十分に長くてヒット件数が少ない場合には、最下層の文字列インデックスが効率的に働いて、少ない数のレコードを一瞬で返し、ハッシュマップを使って各々のレコードに効率的にスコアリングを施した上で、一瞬で処理を返してくれるだろう。問題は、絞り込みの文字列が短く、ヒット数が多い場合である。その場合、ヒットしたレコードの全てにスコアリングをしてからソートすることになるため、遅くなる。全ユーザ数をUとした場合、絞り込み文字列が1文字なら、Uの何割かがヒットしてしまうので、空間計算量はO(U)となる。それをtop-kヒープでソートする時間計算量は、kが20と小さいので、O(U)である。

なお、LIKE演算子による前方一致検索を効率的に動かすには、ちょっとしたコツがある。DBを作る際に、``POSTGRES_INITDB_ARGS: "--encoding=UTF8 --locale=C --lc-collate=C --lc-ctype=en_US.UTF-8"`` などと指定して、コレーションを無効化することだ。Postgresのデフォルトでは文字列の比較を厳密なバイト比較ではなく、複数の文字を同一視するコレーションをした上で比較する。コレーションがあると、デフォルトのインデックスがLIKE演算子で使えない。その他の場面でも、コレーションのせいで効率が悪化することがありうるので、デフォルトのコレーションは切っておいた方が無難だ。後でコレーションが必要になったら、特定の列だけに指定すれば良い。なお、ロケールはen_US.UTF-8などにしておくと、LOWER/UPPERなどの関数は非ASCIIのギリシャ文字やキリル文字にも対応した挙動になる。ja_JP.UTF-8にしても挙動は同じだ。CにしてしまうとASCIIの英字しか処理してくれなくなる。

コレーションを無効化したとしても、大文字と小文字の違いを無視するILIKE演算子には、デフォルトのインデックスは使えない。よって、nicknameのインデックスは `LOWER(nickname) text_pattern_ops` として小文字に正規化したものにしている。小文字に正規化したインデックスを十全に働かせるには、上述のクエリのように、クエリ内の条件も小文字に正規化する必要がある。そうでない場合、インデックスが使われない。

# EXPLAIN SELECT id FROM users WHERE LOWER(nickname) LIKE 'user0002%' ORDER BY ID LIMIT 3;
Limit (cost=8.34..8.34 rows=3 width=8)
 -> Sort (cost=8.34..8.34 rows=3 width=8)
    Sort Key: id
    -> Index Scan using idx_users_nickname_id on users (cost=0.29..8.31 rows=3 width=8)
       Index Cond: ((lower((nickname)::text) ~>=~ 'user0002'::text) AND (lower((nickname)::text) ~<~ 'user0003'::text))
       Filter: (lower((nickname)::text) ~~ 'user0002%'::text)

# EXPLAIN SELECT id FROM users WHERE nickname LIKE 'user0002%' ORDER BY ID LIMIT 3;
Limit (cost=984.21..984.22 rows=3 width=8)
 -> Sort (cost=984.21..984.22 rows=3 width=8)
    Sort Key: id
    -> Seq Scan on users (cost=0.00..984.19 rows=3 width=8)
       Filter: ((nickname)::text ~~ 'user0002%'::text)

listFriendsByNicknamePrefix

さて、上述のlistUsersメソッドは、それに与えられた外部仕様を満たすためには最善の実装ではあるが、SNSの実運用に供するには効率が悪すぎる。そこで、仕様を単純化したlistFriendsByNicknamePrefixという専用メソッドを設けた。ユーザリストはIDの昇順か降順で返すという原則を崩して、自分、フォロイー、その他の分類順で、各分類の中ではニックネームの辞書順にするという特殊仕様だ。あまりこういう専用メソッドを作りたくはないのだが、こればっかりはやらないと仕方がない。基本戦略としては、自分、フォロイー、その他大勢、を別々に処理して絞り込んでから、最後にUNION ALL結合する。具体的なクエリは以下のものだ。

WITH
  self AS (
    SELECT
      0 AS prio,
      u.id, lower(u.nickname) AS nkey
    FROM users u
    WHERE u.id = 0x0001000000000013 AND lower(u.nickname) LIKE 'user0002%' ),
  followees AS (
    SELECT
      1 AS prio, u.id, lower(u.nickname) AS nkey
    FROM user_follows f
    JOIN users u ON u.id = f.followee_id
    WHERE f.follower_id = 0x0001000000000013 AND lower(u.nickname) LIKE 'user0002%'
    ORDER BY lower(u.nickname), u.id LIMIT 20 ),
  others AS (
    SELECT
      3 AS prio, u.id, lower(u.nickname) AS nkey
    FROM users u
    WHERE lower(u.nickname) LIKE 'user0002%'
    ORDER BY lower(u.nickname), u.id LIMIT 20 ),
  candidates AS (
    SELECT * FROM self
    UNION ALL
    SELECT * FROM followees
    UNION ALL
    SELECT * FROM others ),
  dedup AS (
    SELECT DISTINCT ON (id)
      id, prio, nkey
    FROM candidates
    ORDER BY id, prio ),
  page AS (
    SELECT
      id, prio, nkey
    FROM dedup
    ORDER BY prio, nkey, id OFFSET 0 LIMIT 20 )
SELECT
  u.id, u.email, u.nickname, u.is_admin, u.snippet, u.avatar,
  u.ai_model, u.updated_at
FROM page p
JOIN users u ON u.id = p.id
ORDER BY p.prio, p.nkey, u.id;

selfとfolloweesとothersの3つの枝のそれぞれで最大20件のレコードだけを取り出していて、それぞれが20件だけのスキャンで早期終了することを企図している。取り出すレコードも優先度とIDとニックネームだけの最低限に絞っている。そして、dedup処理では、id, prio, nkeyでソートしてから重複IDを除いていて、prioの最小値が採択されている。最後に最終順序でソートした20件だけに他の属性を肉付けして返している。

これの計算量を考えよう。全ユーザ数をUと置き、フォロイー数をFと置く。自分を調べるのは、O(log(U))だ。フォロイーの一覧を引くのは、O(log(U)+F)だ。検索文字列が短い場合、ほとんど絞り込みが働かないので、フォロイー全員のニックネームを調べることになる。よって、その計算量はO(F･log(U))だ。フォロイーのヒット全てを並び替える計算量はO(F･log(F))だ。全員を調べる枝では、検索文字列が短い場合でも、確実に早期終了するので、計算量はO(log(U))だ。つまり、FはUより十分に小さいと仮定すると、支配項はO(F･log(U))ということになる。EXPLAIN文の結果は以下である。全ての枝（Subquery）でIndex Condが働いていて、早期終了するので、効率は最善だ。フォロイーの枝でフォロイー毎にレコードを調べているのもわかる。

Nested Loop (cost=33.92..75.22 rows=5 width=342)
 -> Limit (cost=33.63..33.64 rows=5 width=44)
    -> Sort (cost=33.63..33.64 rows=5 width=44)
       Sort Key: "*SELECT* 1".prio, "*SELECT* 1".nkey, "*SELECT* 1".id
       -> Unique (cost=33.55..33.57 rows=5 width=44)
          -> Sort (cost=33.55..33.56 rows=5 width=44)
             Sort Key: "*SELECT* 1".id, "*SELECT* 1".prio
             -> Append (cost=0.29..33.49 rows=5 width=44)
                -> Subquery Scan on "*SELECT* 1" (cost=0.29..8.32 rows=1 width=44)
                   -> Index Scan using users_pkey on users u_1 (cost=0.29..8.31 rows=1 width=44)
                      Index Cond: (id = '281474976710675'::bigint)
                      Filter: (lower((nickname)::text) ~~ 'user0002%'::text)
                -> Subquery Scan on followees (cost=16.75..16.76 rows=1 width=44)
                   -> Limit (cost=16.75..16.75 rows=1 width=44)
                      -> Sort (cost=16.75..16.75 rows=1 width=44)
                         Sort Key: (lower((u_2.nickname)::text)), u_2.id
                         -> Nested Loop (cost=0.58..16.74 rows=1 width=44)
                            Join Filter: (f.followee_id = u_2.id)
                            -> Index Scan using idx_users_nickname_id on users u_2 (cost=0.29..8.31 rows=3 width=17)
                               Index Cond: ((lower((nickname)::text) ~>=~ 'user0002'::text) AND (lower((nickname)::text) ~<~ 'user0003'::text))
                               Filter: (lower((nickname)::text) ~~ 'user0002%'::text)
                            -> Materialize (cost=0.29..8.33 rows=2 width=8)
                               -> Index Only Scan using user_follows_pkey on user_follows f (cost=0.29..8.32 rows=2 width=8)
                                  Index Cond: (follower_id = '281474976710675'::bigint)
                -> Subquery Scan on others (cost=8.34..8.38 rows=3 width=44)
                   -> Limit (cost=8.34..8.35 rows=3 width=44)
                      -> Sort (cost=8.34..8.35 rows=3 width=44)
                         Sort Key: (lower((u_3.nickname)::text)), u_3.id
                         -> Index Scan using idx_users_nickname_id on users u_3 (cost=0.29..8.32 rows=3 width=44)
                            Index Cond: ((lower((nickname)::text) ~>=~ 'user0002'::text) AND (lower((nickname)::text) ~<~ 'user0003'::text))
                            Filter: (lower((nickname)::text) ~~ 'user0002%'::text)
 -> Index Scan using users_pkey on users u (cost=0.29..8.30 rows=1 width=306)
    Index Cond: (id = "*SELECT* 1".id)

fetchBatch

通知を作成するワーカーがイベントログを読み出す際には、以下のようなクエリが実行される。

SELECT
  event_id, payload
FROM event_logs
WHERE partition_id = 2 AND event_id > 1843013374800035840
ORDER BY partition_id, event_id
LIMIT 100;

主キーがpartition_idとevent_idの複合キーなので、そのインデックスを使えば効率的な実行計画になるはずだ。イベントログの件数をEとすると、計算量はO(log(E))で済む。非同期処理なので読み出すレコードの数は何件でもよいのだが、何らか理由でワーカーの起動が遅延した際に未処理のイベントを適度なペースで処理するには、100件くらいが丁度よいだろう。

このクエリには落とし穴がある。event_id単体での検索性を確保するためにevent_idにユニーク制約をつけると、そのインデックスを使ってevent_idの対象範囲をスキャンしながら該当のpartition_idのものを拾ってしまうのだ。そこで、そのユニーク制約を除外したところ、以下のような効率的な実行計画になることが確認できた。更新イベントが発生する度にこのクエリは実行されるので、この処理が非効率だと洒落にならない負荷になってしまう。理論的に最善であろうインデックスを張って安心しては不十分で、きちんと実行計画を確認しないと後で地獄を見る。

 Limit  (cost=0.42..28.02 rows=100 width=95)
   ->  Index Scan using event_logs_pkey on event_logs  (cost=0.42..8330.90 rows=30179 width=95)
         Index Cond: ((partition_id = 2) AND (event_id > '1843013374800035840'::bigint))

listFeed

作成された通知を読み出す際には、以下のようなクエリが実行される。

SELECT
  slot, term, is_read, payload, updated_at, created_at
FROM notifications
WHERE user_id = 0x0001000000000013 AND is_read = FALSE
ORDER BY updated_at DESC
LIMIT 20;

新規通知の有無は定期的に調べられるので、このクエリの効率も重要だ。user_id、is_read、updated_atの複合インデックスを設けているので、そのインデックスが使われるはずだ。通知件数をNとすると、計算量はO(log(N))になる。実行計画を見ても、そのことが確認できる。なお、未読リストと既読リストはis_readの条件値を変えて2回のクエリに分けて取得し、結合結果をIDでソートして最新20件を提示する。この方法だと、ページ送り機能がないUIでも、ひとつひとつ既読にしていくことで、全ての通知を閲覧できる。

 Limit  (cost=0.29..15.46 rows=5 width=136)
   ->  Index Scan Backward using idx_notifications_user_read_ts on notifications  (cost=0.29..15.46 rows=5 width=136)
         Index Cond: ((user_id = '281474976710675'::bigint) AND (is_read = false))

新着通知を調べる際に、毎回同じデータを返すのは無駄だ。よって、クライアントが最後に取得した通知の最新のupdated_atをパラメータとして渡すAPIになっていて、それより新しい未読レコードがなければ304を返すという仕様になっている。

SELECT 1
FROM notifications
WHERE user_id = 0x0001000000000013 AND is_read = FALSE
AND updated_at > '2025-09-12 04:17:15.536+00'
LIMIT 1;

この計算量も当然O(log(N))である。実行計画を見てもインデックスが適切に効いていることがわかる。ここで重要なのは、is_read = FALSEを指定して、未読だけを調べていることだ。インデックスの構造に合わせた条件を全て指定することでインデックスがIndex Only Scanにしている。最新の通知は常に未読なので、未読だけ調べれば十分だ。

Limit (cost=0.29..1.91 rows=1 width=4)
 -> Index Only Scan using idx_notifications_user_read_ts on notifications (cost=0.29..8.40 rows=5 width=4)
    Index Cond: ((user_id = '281474976710675'::bigint) AND (is_read = false) AND (updated_at > '2025-09-12 04:17:15.536+00'::timestamp with time zone))

総評

ここまで見てきたように、記事IDやユーザIDのリストを取得するための検索操作は全てインデックス上で行えるように、スキーマとクエリを設計している。各々のインデックスは小さいので、大部分がメモリ上にキャッシュされて、高速にランダムアクセスできる。よって、Fakebookの主要クエリは、全てスケールするものになっていると言える。

全体の最新投稿を一覧で使うlistPostsの計算量はO(log(P))だ。自分がフォローしているユーザの最新投稿を一覧で使うlistPostsByFolloweesの計算量はO(F･log(P))で済んでいる。イイネした投稿の一覧で使うlistPostsLikedByUserの計算量はO(log(P))だ。その他、全ての投稿一覧はO(log(P))以下の計算量に留めている。ユーザ一覧に関しても同様で、全文検索以外で最も重いlistFriendsByNicknamePrefixの計算量もO(F･log(U))に留めている。

最も重いlistPostsByFolloweesとlistFriendsByNicknamePrefixの計算量はフォロイー数Fに比例する。したがって、フォロイー数を定数項にするために、上限値を決める必要がある。現実的には100人以上フォローしても使い勝手が悪くなるだけなので、200人くらいを上限値にすれば問題ないだろう。Fが定数であれば、計算量はO(log(P))とO(log(U))と表せるわけで、誰がどう見ても健全なシステムになる。

UXの要求仕様でフォロイー数の制限ができない場合、毎回のクエリでフォローしている全員を対象にするのではなく、何らかの簡便法を用いるのが現実的だ。例えば、「重要フォロイー」のサブセットを定期的に抽出してキャッシュに持たせておいて、それを使いつつも、あたかも全員を対象としているかのような振りをするのだ。TwitterもFacebookも当然そうしている。

投稿記事の本文やユーザ自己紹介の本文などのでかいデータを取得する操作も、スケーラビリティの制限要因になる。主キーに紐づいたテーブル本体のレコードを読み出すという操作は、レコード数Nに対してO(log(N))の計算量に過ぎない。しかし、データの規模が大きいと遅くなる。メモリ上のキャッシュに乗り切らないので、毎回のアクセスでストレージにアクセスするからだ。HDDであればシークタイムも加算される。読み出しのデータが大きいと、ストレージとメモリの間のデータ転送量が増えることでも遅くなる。postsとusersテーブルに本文を入れずにスニペットだけを入れるのは、この問題に対する緩和策だ。計算量を対数オーダーにするのは大前提だが、計算量に現れない最適化も地味に性能に効いてくる。

限界点

個々のDBサーバが、いつどのように限界を迎えるのかについて考えておくべきだ。言い換えると、要求スループットに実際のスループットが耐えられなくなる瞬間は、いつ、どのように訪れるかだ。例えば最大100QPSのアクセスがあるなら、クエリ毎のレイテンシは0.01秒未満である必要がある。実際には並列処理能力があるのでそれより少し遅くても大丈夫だが、数倍遅いのはもう駄目だ。

リスト系クエリの処理が、インデックスのみを参照して返却対象のIDを絞り込むフェーズと、主テーブルを参照して個々のIDのレコードの属性を肉付けするフェーズから成ることは既に述べた。クエリの性能が目に見えて落ち始めるのは、インデックスがPostgreSQLのページキャッシュ（shared_buffers）に乗らなくなる瞬間である。ところで、PostgreSQLではページキャッシュは実メモリの25%程度にするのがベストプラクティスとされる。自プロセスの他プロセスのために実メモリを残しておく必要があり、またOSのページキャッシュのためにも実メモリを残しておく必要がある。PostgreSQLはOracleと違ってページキャッシュにダイレクトI/O（O_DIRECT）を使わないので、DBのページキャッシュとOSのページキャッシュの2層構造になっている。

ここで述べる試算はフェルミ推定級の概算であり、設定やデータの特性やアクセスパターンによって実際の数値は全く異なることに注意されたい。仮にメモリ16GBのマシンで運用している場合、DBのページキャッシュの容量は4GBだ。1ページは8KBなので、524288ページが使える。そのうち半分の262144ページをインデックスに使うとする。Bツリーインデックスの各エントリ（タプル）は、典型的には、以下の要素から成る。つまり合計28バイトだ。なぜUUIDでなくSnowflake IDを使うべきかを実感するところだ。

検索キー（今回の典型ではSnowflake ID）（8B）
順序キー（今回の典型ではSnowflake ID）（8B）
アイテムポインタ（6B）
インフォ（長さ・フラグ）（2B）
ラインポインタ（オフセット・タプル長・フラグ）（4B）

単純計算すると1ページに292エントリが入ることになる。しかし、実際にはページヘッダやBツリーのヘッダが入り、フィルファクタで90%までしかデータを埋めないという制約があり、さらにページ分割によるフラグメンテーションも起こるので、200エントリくらいで見ておくと安全だ。よって、システム全体で52428800エントリがキャッシュに乗る。投稿関係でそのうち80%を使うとすると、41943040エントリだ。postsテーブルには、主キーに自動的に張られるインデックスを含めて、5つのインデックスがつけられている。最終的に、約840万（41943040 / 5 = 8388608）投稿分のインデックスがキャッシュに乗るという試算になる。それよりも小さい規模だとほぼすべてのクエリはオンメモリで処理されるが、それを超えると、確率的にディスクI/Oが発生するようになる。とはいえ、インデックスには参照局所性があり、新しいデータにアクセスが偏り、OSのページキャッシュもあるので、840万件を過ぎた時にいきなりガクンと遅くなるわけではない。ジワジワと、しかし確実に、遅くなり始める。対数オーダーではあるが、インデックス内のランダムアクセス回数の増加も係数として効いてくる。

主テーブルのデータも840万とは別の閾値でキャッシュに載らなくなってくるが、その閾値はより少ない件数だろう。主テーブルの方がデータが大きいのだから、主テーブルがページキャッシュを食い尽くすという懸念もあるが、実際にはアクセス頻度が高いインデックスデータの方がページキャッシュに残りやすい。主テーブルのアクセスは絞り込みが終わってから定数回しか行われないようにクエリ設計するのはキャッシュ効率の点でも重要だ。もしも主テーブルをシーケンシャルスキャンすると、ページキャッシュが荒らされてしまう。また、SNSの場合、新しいレコードに参照が偏るので、表示するレコードだけを読み込むようにすると、参照局所性が高く維持できる。投稿の主テーブル以外にもタグのインデックスが参照されるが、それも同じアクセスパターンになる。

実際のテーブルやインデックスが占有しているデータサイズは、以下のクエリで分かる。実運用を始めたら、定期的にその結果を見て限界予測をすべきだ。人気サービスのSREに抜擢されたなら、毎日この時限爆弾を眺める栄誉が与えられる。

CREATE EXTENSION IF NOT EXISTS pageinspect;
SELECT
  n.nspname AS schema,
  c.relname AS name,
  CASE c.relkind
    WHEN 'r' THEN 'table'
    WHEN 't' THEN 'toast'
    WHEN 'i' THEN 'index'
    WHEN 'm' THEN 'mview'
    ELSE c.relkind::text
  END AS type,
  pg_size_pretty(pg_relation_size(c.oid)) AS size_pretty,
  pg_relation_size(c.oid)/8192 AS pages_8k
FROM pg_class c
JOIN pg_namespace n ON n.oid = c.relnamespace
WHERE n.nspname NOT IN ('pg_catalog','information_schema')
  AND c.relkind IN ('r','t','i','m')
ORDER BY pages_8k DESC;

投稿20万件をDBに記録した際の実際のインデックスのサイズとページ数を以下に示す。半分は返信、半分は新規投稿とする。

機能	名前	サイズ	ページ数
posts主キー	posts_pkey	6332416	773
posts著者別インデックス	idx_posts_owned_by_id	9494528	1159
posts返信別インデックス	idx_posts_reply_to_id	8888320	1085
posts非返信インデックス	idx_posts_root_id	2285568	279
posts非返信著者別インデックス	idx_posts_root_owned_by_id	3186688	389

インデックスのサイズの合計は30187520バイトであり、投稿あたり150バイトだと実測された。1.7GB（4GBの半分の80%）に乗る件数は11145万件ということになる。840件の試算よりも多くなったのは、返信別インデックスと非返信別が排他的であることと、バッチで整然と登録したのでフラグメンテーションが起きにくかったことと、そもそも試算の際のページ内エントリを厳しめに見積もっていたことに起因すると考えられる。いずれにせよ、最悪840万件、最善1145万件くらいの幅で飽和点を捉えておくと良いだろう。

ページキャッシュに乗らなくなったデータの読み書きは、ストレージのI/O性能に律速される。HDDだと速くて200 IOPSで、SSDだと遅くて500000 IOPSだ。HDDだとページキャッシュに乗らなくなった時点で即座に死亡フラグが立つのだが、SSDだとその後も耐え続ける。840万投稿程度の規模であれば100QPSとかは余裕で出るだろう。ストレージの性能は製品によって全然違うので、最終的にどの程度の規模でどの程度のスループットが出るのかは、実運用環境で実験してみないとわからない。AWSで運用する場合、RDSでもAuroraでも、設定によって性能が全く変わる。ページキャッシュの飽和点は計算で導けるが、実際のスケーラビリティの限界点はベンチマークテストを経てから判断すべきだ。

余談

スニペットをDBに保存するということは、「どう表示するか」というフロントエンド側のプレゼンテーションの知識をバックエンド側で持つことを意味するため、責任分割の観点では気持ち悪い。本文に関数従属しているスニペットを持つのは第3正規形の違反でもある。スニペットの形式や文字数制限を変えた際にDBのレコードを入れ直さなきゃならないのも嫌だ。しかし、その気持ち悪さを飲んでもやらねばならない。

投稿記事やユーザ自己紹介の本文を分離するという手法は、いわゆる垂直分割の一種である。属性データの特性に合わせて管理方法を分割する手法とも言える。本文だけDBサーバを分けてもいいし、列指向DBに入れてもいいし、S3に入れてクライアントに直接取得させたっていい。古い記事の本文は圧縮した上でアーカイブ用のストレージに入れてもいい。post_likesやuser_followsといったテーブルを別サーバで管理するのも良いだろう。

以上のことを鑑みると、リソースのリストを取得する処理は、常に二段構えで考えるべきだ。条件に該当するIDのリストを生成する段と、そのIDに紐づけて属性を収集する段だ。RDB1台運用だとその2段が一発のクエリでできるが、それでもサブクエリを使って敢えて2段に分けて書くのも良い考えだ。以下の二つのクエリは等価で、後者の方が若干遅いかもしれないが、いずれ垂直分割する際は、後者の書き方をしておく方がバグりにくい。

SELECT id, nickname, snippet
FROM USERS WHERE id > 0x0001000000000002
ORDER BY id LIMIT 10;

WITH cand_ids AS (
  SELECT id FROM users
  WHERE id > 0x0001000000000002
  ORDER BY id LIMIT 10
)
SELECT u.id, u.nickname, u.snippet
FROM users AS u
JOIN cand_ids AS c ON u.id = c.id
ORDER BY c.id;

なお、PostgreSQLでは、TOAST（The Oversized-Attribute Storage Technique）という機構があり、2KBを超える大きい列データを暗黙的に圧縮したり別領域に移動したりしてくれる。よって、明示的に分割しなくても、ある程度の最適化は勝手になされる。しかし、それでもなお、大きさや参照頻度が異なるデータは明示的に分割した方が良い。今回の例では、スニペットさえあればリスト取得時には本文を一切参照する必要がない。たとえSELECT文で属性を指定しなくても、同じテーブルにある限り、データは読み込まれてしまう。よって、本文は短くても長くても別テーブルに逃がした方が、主テーブルのページ読み出し量が少なくて済む。

指定した列の短いデータも強制的にTOASTしてくれれば、わざわざテーブル分割しなくても済むのにと思ったが、そのような指定はできない。また、テーブル分割した先では、TOASTしなくてもよいとも思ったが、そのような指定もできない。TOASTの本来の目的は参照局所性の向上ではなく、主テーブルの各レコードのサイズをページサイズ（8KB）以下に抑えることだからだ。なお、TOASTは圧縮もしてくれるが、そのデフォルトの圧縮方式はpglz（LZ77）で、遅い割には圧縮率があまり良くない。なので、今回はDB全体の圧縮設定をLZ4に変更している。LZ4は無圧縮に近い速度で動く割には、自然言語の文字列を半分くらいに圧縮する能力があるので、LZ4に変更する利点は大きい。

参照系のクエリが重い場合、マスター・スレーブのレプリケーションを導入すると簡単に負荷分散できる。DBサーバを2台立てて、更新系クエリはマスターサーバにだけ投げるようにする。その更新内容はスレーブサーバに自動的に伝搬する。参照系クエリはマスターとスレーブの双方に分散して投げると、参照系クエリの負荷はサーバあたりで半分になる。スレーブの数を増やせば参照系の負荷はもっと下げられる。マスターが死んだ時にスレーブをマスターに昇格させることで、可用性の向上にもなる。ただし、更新系クエリの負荷はこの方法では下げられない。また、マスターからスレーブに更新が伝搬するまでにタイムラグがあるので、スレーブからの結果をそのまま表示すると直前の更新操作が反映されない可能性がある。よって、更新操作直後の参照系クエリはマスターにだけ投げるとか、更新内容をキャッシュサーバに入れておいてUI上で注入するとか言った工夫が必要になる。

垂直分割やレプリケーションをしても処理しきれなくなってきたら、いよいよ水平分割をすることになる。ユーザIDを使ってパーティショニングを行うのが率直な方法だろう。ハッシュ値などで機械的に割り振っても良いが、各ユーザがどのパーティションに居るのかを管理するuser_partitionsテーブルを作るか、それに相当するKVSを運用するのが率直だ。usersテーブルを引く時はユーザIDでパーティションを特定してからそのDBサーバにアクセスし、postsテーブルを引く時は著者のユーザIDでパーティションを特定してからそのDBサーバにアクセスする。フォロー関係は、フォロー元のユーザとフォロー先のユーザのDBに二重化して持たせれば良い。垂直分割を経ているならば、もはやJOINするクエリは少なくなっていて、IDのリストを取り出してから別のDBにアクセスする作法は確立しているはずだ。あとはそのアクセス先を個々のIDに紐づいたパーティションにするだけだ。ユーザに紐づいた一連のデータをパーティション間で移動するユーティリティさえ書いておけば、運用はそんなに難しくない。

規模が大きくなると、投稿一覧の「All」のビューがほとんど意味をなさなくなってくる。見知らぬ人の投稿を全て見る奴は居ない。となると、「Pickup」とか「Topics」とかいう位置づけのビューを代わりに置くことになるだろう。最近の投稿だけを集めた小さいデータベースを作っておいて、質が高いものや個々のユーザの興味に近そうなものをバッチ処理で計算して、それを提示するのだ。

規模が大きくなると、「セレブユーザ」の存在が運用上の問題になってくる。数万人からフォローされるユーザが出てくるかもしれない。単一の投稿がものすごい勢いでイイネされたり返信されたりするかもしれない。参照系を最適化するだけでは、更新系が逼迫する問題には対処できない。その場合、セレブユーザ専用のデータ管理機構を整備すべきだろう。投稿の内容はキャッシュサーバから配信し、フォローやイイネや返信はキューに入れて非同期に処理する。通知は意味をなさないので処理を省略する。セレブユーザではなくても、突発的なバズりや炎上はあり得る。それに備えて、負荷が一定を超えたら、全体または特定ユーザを対象とする更新操作を非同期処理に切り替える機構を入れてもよいだろう。時間分散という考え方だ。非同期処理にすると更新結果がすぐに画面に反映されないという問題が起こるが、そこはキャッシュで頑張る。つまり、ユーザ毎の更新内容をキャッシュしておいて、あたかもその更新が既にDBに反映されているかのように、表示に細工をするのだ。

その他にも、キャッシュサーバでできることはたくさんある。例えば、listPostsByFolloweesの中で作っているアクティブユーザリストをキャッシュすると、それだけでDBへの負荷が激減する。各アクティブユーザの最新投稿20件の内容もキャッシュしておけば、多くの場合で、DBに全くアクセスしなくても、タイムライン表示が完結する。DB設計の話から逸脱するのでここでは詳述しないが、キャッシュ機構の設計も重要だ。ただし、キャッシュはいつだって消えるので、キャッシュがなくても満足に動くDB設計をするのが大前提だ。

おわりに

ここまでいろいろ述べたが、Fakebookの現状の目標は、スケーラビリティを追求することではない。SNSの基本機能を率直に実装した、単純で典型的で教科書的なシステムを作ることだ。規模Nに対して各種クエリの時間計算量がN未満であることが保証できていれば良い。少なくとも開発の初期段階では、見通しがよく開発と保守がしやすいスキーマを選択すべきで、現状のスキーマはそれに叶うものになっている。時期尚早の最適化をして、人気が出る前に開発が頓挫するというのでは意味がないので、単純な構成から始めるというのも重要だ。

人によっては、「既に最適化と複雑化がだいぶ進んでいるじゃないか」と突っ込みたくなるかもしれない。しかし、この程度はSNSならめちゃ単純な範疇である。これより手抜きするとユーザ数1000人とかでも破綻するという最低限の構成と言えるだろう。DB1台構成でも運用できるこのような基本的な構成で、まずは経験を詰むべきだ。基本機能の設計と実装がきちんとできる体制が作られていれば、コミュニティ機能やDM機能を追加するのも難しくないだろう。逆に言えば、ここで述べたことくらいは当然のようにできるDBエンジニアが居ないと、SNSの実運用は破綻する。ORMにスキーマを吐かせているようでは無理だ。mixiというSNSの開発に携わっていた時に、とあるエンジニアが良かれと思ってORMを導入したが、それを見たCTOが切れて即刻廃止されていた。そういう失敗を小規模なうちに繰り返しておくのが、大規模なサービスで失敗しないために必要となる。

システムを設計する際に、UXデザイナが画面設計から起こしてそれに対応するAPIとスキーマを決めるというフロントエンドアプローチと、DBエンジニアがスキーマとAPIから起こしてその範囲で実現できる画面設計をするというバックエンドアプローチがある。SNSに限って言えば、スケーラビリティに関する制限は絶対要件なので、バックエンドアプローチにならざるを得ない。そのうえで、UXを追求していくには、DBも分かるしUXにも一定の理解がある人間が設計をするとともに、開発のイテレーションを回しながら改善していくのが有効だろう。この記事がその一助となれば幸いだ。

次回以降は、メディアストレージの実装、通知機能、UIの詳細、本番環境のデプロイなどについて解説していく。

豪鬼メモ

一瞬千撃