Instagram のグリッド並べ替えをシステム設計として考える

2026 年 6 月 8 日、Instagram はプロフィールのグリッドに並ぶ投稿を好きな順に並べ替える機能を、全ユーザーへ順次提供し始めました（MacRumors、ABC News）。グリッド上の投稿を長押しし、メニューの Reorder grid（英語版の表記）を選んでドラッグします。変更はすぐに保存され、プロフィールを訪れたすべての人に表示されます。それまでのグリッドは新しい投稿ほど上に来る時系列順で、例外は最大 3 件のピン留めだけでした。

利用者から見れば、ドラッグで順番を入れ替えるだけの機能です。一方、システムの側では、並び順が「投稿の作成時刻から決まる値」から「利用者が書き込むデータ」に変わります。Instagram の月間アクティブユーザーは 30 億人です（2025 年 9 月の発表、CNBC）。この規模では、並び順をどう保存し、どんな値で表し、どう配信するかによって、書き込み量やキャッシュの効き方が大きく変わり、既存の API が返す内容の意味も変わります。

Instagram 規模のサービスにこの機能を加えるなら、筆者は次のように設計します。

1. 並び順は投稿そのものではなく、プロフィールと投稿の関係に持たせる。
2. 既定の並びは時系列順のまま残し、利用者が動かした投稿にだけ並び順キーを書く。キーは時刻順に増える 64 ビットの投稿 ID と同じ範囲の整数で表し、前後の投稿のキーの中点を使う。中点が取れなくなったときだけ、近くの数件のキーを振り直す。
3. グリッドへの書き込み（移動、新規投稿、削除など）はプロフィールごとに直列化し、そのたびにグリッドの版（バージョン番号）を 1 つ進める。
4. 一覧はキーセット方式のカーソルで返し、キャッシュはグリッドの版で区別する。
5. 作成時刻の意味で使われてきた API や処理は時系列順のまま残し、表示順は新しい概念として明示的に加える。

Instagram の内部実装は公開されていないので、以下は公開情報をもとにした筆者の設計です。数値には、出典のある値、筆者がコードを実行して確かめた値、規模感をつかむための仮定があり、それぞれ区別して示します。

1. 機能の仕様と設計の前提

1.1 公開情報から分かる仕様

Instagram 責任者の Adam Mosseri は 2025 年 1 月にこの機能を予告し、同年 6 月の Meta のニュースルームでも「グリッドの投稿を並べ替えられるようにする」と書いていました（Meta、TechCrunch）。2026 年 6 月の提供開始を伝える報道と、利用者向けの解説記事から、仕様を次のように整理できます。

報道は Meta と Instagram の発表を伝える MacRumors と ABC News の記事、解説記事は TechPP と Hopper HQ の記事です。解説記事の内容は書き手が試した結果なので、細部は今後変わるかもしれません。保存の仕方は資料によって違います。報道によれば変更はすぐに保存されますが、Hopper HQ の解説は、並べ替えたあと Done を押して保存すると書いています。以下の設計は、ドラッグのたびに保存する方式（5.1 節）にも、まとめて保存する方式（5.3 節）にも対応します。

1.2 設計の前提にする要件

上の仕様に、大規模サービスとして必要な条件を加えます。ここからは筆者が置く前提です。

• 1 回の移動で書き込む量を、グリッドの投稿数に比例させない。
• 並べ替えを使わない大多数の利用者について、既存のデータを書き換えない（バックフィルをしない）。
• プロフィールの最初のページを返す速さを落とさない（閲覧は並べ替えよりはるかに多いと考えられる）。
• 並べ替えた本人には変更をすぐに見せる。ほかの閲覧者には数秒程度の遅れを許す。

2. 時系列順だから成り立っていた前提

Instagram は 2011 年のエンジニアリングブログで、投稿などの ID の採番方式を公開しています（Sharding & IDs at Instagram）。ID に求めた要件の 1 つ目は、「生成した ID を時刻順に並べられること。写真の ID のリストを、写真の情報を追加で取得せずに並べ替えられるように」でした。ID は 64 ビットで、上位から次のように構成されます。

| 41 ビット: 独自エポックからのミリ秒 | 13 ビット: 論理シャード ID | 10 ビット: 連番 |

その記事の例のようにユーザー ID からシャードを決めると、1 人の投稿は同じ論理シャードに入り、ID の大小は投稿時刻の前後と一致します。この方式が現在も使われているかは公開情報からは分かりませんが、以下では、このように時刻順に増える ID を前提にします。すると、時系列順のグリッドには次の性質があります。

• 並び順は ID だけで決まる。追加の列なしに、プロフィールごとの投稿の一覧を ID の降順にインデックスで読めば、最初のページになる。
• 次のページのカーソルは「最後に見た投稿の ID」で足りる。
• 新しい投稿は常に先頭に入る。最初のページのキャッシュは、先頭に 1 件足して末尾から 1 件落とせば更新できる。
• 先頭の N 件は「最新の N 件」と同じ意味になる。

Facebook（現 Meta）が 2013 年に発表したグラフストア TAO の論文も、同じ性質を前提にしています（Bronson ら, 2013）。TAO は関連（エッジ）の一覧を time フィールドの降順で保持し、キャッシュには一覧の先頭から連続する部分だけを持ちます。論文は、データの大半は古いのに問い合わせの多くは新しい部分に集中する性質を creation-time locality と呼び、設計の根拠にしています。time フィールドは 32 ビットで、論文の脚注によれば、実際にはアプリケーションが値を決める汎用の整数です。本文によれば、多くの関連はここに作成時刻を入れています。そこに表示順を書けば任意の順序を表せますが、この案の問題は 7.1 節で扱います。

並べ替えを許すと、これらの性質は次のように変わります。

新しい投稿が先頭に入る点は同じです。違うのは、古い投稿もどの位置へでも移れる点です。

3. データモデル：順序をどこに持たせるか

3.1 プロフィールと投稿の関係に持たせる

並び順を投稿の属性（投稿テーブルの列）にすると、3 つの問題が起きます。

1 つ目は共同投稿です。1 件の投稿が複数のプロフィールに並び、所有者はそれぞれ別の順序を付けます（1.1 節の表）。並び順は「どのプロフィールのグリッドで、どの投稿が、どこにあるか」という関係の属性です。リールタブのように別の一覧が独自の並び順を持つようになったら、一覧の種類も主キーに加えます。

2 つ目は、移動が投稿の更新として扱われることです。移動は投稿の内容を変えません。並び順を投稿の行に置くと、移動のたびに更新日時が変わり、変更データキャプチャ（CDC）で投稿の更新を購読している検索インデックスや機械学習の特徴量パイプラインに、意味のない更新イベントが流れます。

3 つ目は書き込みの重さです。PostgreSQL では、インデックスが参照する列を更新すると HOT（heap-only tuple）更新が使えず、そのテーブルのすべてのインデックスに新しいエントリーを追加します（PostgreSQL のドキュメント）。インデックスの多い投稿テーブルではなく、プロフィールと投稿の関係だけを表す、列の少ないテーブルに置けば、移動 1 回で更新するインデックスはそのテーブルのものだけで済みます。

3.2 動かした投稿にだけキーを書く

sort_key は、投稿 ID で決まる位置を上書きする値です。利用者が動かした投稿と、再採番で振り直した近くの行にだけ書きます（例外は、3.3 節の新規投稿と、このあと述べるアーカイブからの復帰やピン留めの解除でキーを取り直す場合）。上書きがあればその値、なければ投稿 ID を実効キーと呼び、coalesce(sort_key, post_id) で求めます。グリッドは実効キーの大きい順に並べます。投稿 ID は時刻順に増えるので、一度も並べ替えていないグリッドの順序は従来と同じです。

この設計には次の利点があります。

• 並べ替えを使わない利用者の既存の行は 1 行も書き換えない。既存の一覧に NULL を許す列を足し、インデックスを作るだけで導入できる（3.3 節）。
• 新しい投稿は、ID がそれまでのキーより大きくなるので、ふつうはキーを書かずに先頭に入る。そのためには、上書きしたキーがそれまでに発行した ID を超えないようにする（4.3 節）。
• 時系列順に戻す機能も、上書きを消す（NULL に戻す）だけで作れる。解説記事によれば現在の Instagram にこの機能はないが、この設計なら書き込みは上書きした行の数で済む。
• 投稿を削除しても、ほかの投稿のキーは書き換えない。

アーカイブした投稿の行は一覧から外し、戻すときに入れ直します。戻す位置は、仕様として決める必要があります。以前の位置に戻すならキーをアーカイブの記録に残しておき、時系列の位置に戻すならキーを NULL にして入れ直します。どちらも通常は 1 行の書き込みで済みます。ただし、アーカイブしているあいだに、移動の中点や再採番で同じ実効キーがほかの行に使われていることがあります。入れ直す前に確かめ、使われていれば、その位置の前後の行のあいだに 4.3 節の方法でキーを取り直します。

ピン留めは、これまでどおり本体の一覧とは別に扱います。最大 3 件のピン留めは既存の仕組みのまま持ち、最初のページでだけ先頭に並べ、本体の一覧を読むときは除外します。ピン留めを解除した投稿は、自分の実効キーの位置に戻ります。ピン留めした行は再採番の対象にならないので、ピン留めを解除するときも、アーカイブからの復帰と同じく、実効キーがほかの行と重なっていればキーを取り直します。

3.3 スキーマとクエリー

ここでは、プロフィールごとにグリッドに載る投稿の一覧（grid_entry）が既にあると仮定します。共同投稿を複数のプロフィールに並べるために、こうした一覧を持っていることが多いと考えられます。この一覧に、NULL を許す列を 2 つ足します。1 つは並び順キーで、もう 1 つは 6.1 節でカーソルのキーを引き直すときに使う列です（引き直しをしないなら要りません）。PostgreSQL では、既定値のない列の追加はテーブルの定義を変えるだけで、既存の行を書き換えません（PostgreSQL のドキュメント）。インデックスも CREATE INDEX CONCURRENTLY で、書き込みを止めずに作れます（本番で実行するときの注意は 7.3 節）。グリッドの版を持つ grid_order の行は、そのプロフィールのグリッドが初めて変わったとき（移動、新規投稿、削除など）に作ります。行がなければ版は 0 とみなします。

-- 既存の一覧：グリッドに載る投稿 1 件につき 1 行
CREATE TABLE grid_entry (
  profile_id  bigint NOT NULL,
  post_id     bigint NOT NULL,   -- 時刻順に増える 64 ビット ID
  PRIMARY KEY (profile_id, post_id)
);
 
-- 足すのは NULL を許す列 2 つ。どちらも既存の行は書き換えない
ALTER TABLE grid_entry
  ADD COLUMN sort_key      bigint,   -- NULL なら投稿 ID の位置（時系列順）
  ADD COLUMN moved_version bigint;   -- 最後に位置を変えたときの版（6.1 節。任意）
 
-- 表示順のインデックス。実効キーの降順、同じなら投稿 ID の降順
CREATE INDEX CONCURRENTLY grid_entry_display ON grid_entry
  (profile_id, (coalesce(sort_key, post_id)) DESC, post_id DESC);
 
-- グリッドの版。最初の変更で行を作り、グリッドへの書き込みの直列化にも使う
CREATE TABLE grid_order (
  profile_id  bigint PRIMARY KEY,
  version     bigint NOT NULL DEFAULT 0   -- グリッドが変わるたびに 1 増やす
);

グリッドを変える書き込み（移動、新規投稿、削除、アーカイブとその解除、ピン留めの変更）は、どれもトランザクションの最初に版の行をロックし、版を 1 増やします（このあと示す移動のトランザクションでは、最初の INSERT 文がこれに当たります）。ロックの順序をすべての書き込みでそろえるのは、デッドロックを防ぐためです。移動は版の行をロックしてから投稿の行を更新します。削除を「投稿の行を消してから版を進める」順で書くと、同じ投稿に対する移動と削除が互いのロックを待ち合います。PostgreSQL はこれを deadlock_timeout（既定 1 秒）のあとに検出し、一方を中断します（PostgreSQL のドキュメント）。版を進める処理は 1 つのデータアクセス関数にまとめ、運営による削除や、共同投稿の相手が抜けたときのように、利用者の操作以外でグリッドが変わる経路もそこを通します。版はキャッシュとカーソル（6 章）と、まとめて送る並びの検査（5.3 節）で使います。

新規投稿をグリッドに加えるときは、ロックを取ったあとで、投稿 ID を、ピン留めを除いた先頭の実効キーと比べます。ID を発行してからロックを取るまでのあいだに、先頭への移動や、先頭まで広がった再採番が入ると、それらが書いたキーのほうが新しい投稿の ID より大きくなることがあるからです。ID のほうが小さければ、先頭への移動と同じ方法でキーを書きます。

プロフィールごとの一覧がないシステムでは、上書きだけを別のテーブルに置き、読み取り時に時刻順の一覧とマージします（3.4 節と同じ形です）。

一覧のクエリーは、最初のページと 2 ページ目以降で条件が 1 つ違うだけです。次のページは、直前のページの最後の行の実効キーと投稿 ID より後ろを読みます。

-- 最初のページ（ピン留めは別に取り出して先頭に置く）
-- $2 はピン留めの ID の配列。なければ空配列を渡す（NULL だと 1 行も返らない）
SELECT post_id, coalesce(sort_key, post_id) AS k
FROM grid_entry
WHERE profile_id = $1
  AND post_id <> ALL ($2::bigint[])
ORDER BY coalesce(sort_key, post_id) DESC, post_id DESC
LIMIT 24;
 
-- 2 ページ目以降：$3, $4 は直前のページの最後の行の (k, post_id)
SELECT post_id, coalesce(sort_key, post_id) AS k
FROM grid_entry
WHERE profile_id = $1
  AND post_id <> ALL ($2::bigint[])
  AND (coalesce(sort_key, post_id), post_id) < ($3, $4)
ORDER BY coalesce(sort_key, post_id) DESC, post_id DESC
LIMIT 24;

PostgreSQL 18.6（PGlite）で実行計画を確かめると、どちらも grid_entry_display を使う Index Scan になりました。2 ページ目以降の行値の比較も、インデックスの検索条件（Index Cond）として使われます。ピン留めの除外は、インデックスを読んだあとの絞り込み（Filter）です。

移動は 1 つのトランザクションで行います。移動先は「移動後にすぐ前に来る投稿（アンカー）」で指定します（理由は 5.1 節）。

BEGIN;
-- 版の行をロックして 1 増やす（行がなければ版 1 で作る）。
-- グリッドを変える書き込みは、どれもこの文から始める
INSERT INTO grid_order (profile_id, version) VALUES ($1, 1)
ON CONFLICT (profile_id) DO UPDATE SET version = grid_order.version + 1
RETURNING version;
 
-- アンカーの実効キーと、表示順でそのすぐ後ろにある投稿の実効キーを読む
-- （$pinned はピン留めの ID の配列。先頭への移動では、先頭の投稿の
--   実効キーと、新しく発行した ID とのあいだに置く）
SELECT coalesce(sort_key, post_id) AS k FROM grid_entry
 WHERE profile_id = $1 AND post_id = $anchor;
SELECT coalesce(sort_key, post_id) AS k FROM grid_entry
 WHERE profile_id = $1 AND post_id <> $moved AND post_id <> ALL ($pinned)
   AND (coalesce(sort_key, post_id), post_id) < ($anchor_k, $anchor)
 ORDER BY coalesce(sort_key, post_id) DESC, post_id DESC
 LIMIT 1;
 
-- アプリケーションで 2 つのキーの中点を計算して書く。中点が取れないときは、
-- アンカーの前後を数十件ずつ読んで再採番し、その行もここでまとめて書く
-- $version は最初の文が返した版
UPDATE grid_entry SET sort_key = $new_k, moved_version = $version
 WHERE profile_id = $1 AND post_id = $moved;
-- 更新した行が 1 行でなければ（投稿がこのグリッドにない）、ロールバックして 404 を返す
-- （ロールバックすれば版の増分も取り消される）
COMMIT;

このトランザクションは、既定の READ COMMITTED で実行します。ロックを待ったあとの SELECT が、直前にコミットされた書き込みの結果を読めるからです。REPEATABLE READ で実行すると、ロックを待たされた側は最初の文で直列化エラーになります。

3.4 ワイドカラム型ストアでの注意

Cassandra のように、パーティション内の並び順をクラスタリングキーで決めるストアでは、並び順キーをクラスタリングキーに入れたくなります。しかし、主キーの列は UPDATE で変更できないので（DataStax の CQL リファレンス）、移動は「古い行の削除と新しい行の挿入」になります。削除はトゥームストーン（削除の印）として残り、既定では 10 日（gc_grace_seconds の既定値 864,000 秒）が過ぎてコンパクションされるまで、読み取りのたびに読み飛ばされます（Apache Cassandra のドキュメント）。頻繁に並べ替えるプロフィールほど、パーティションにトゥームストーンがたまります。既定の設定では、1 回の読み取りで読んだトゥームストーンが 1,000 個を超えると警告が出て、100,000 個を超えると読み取りが失敗します（cassandra.yaml の tombstone_warn_threshold と tombstone_failure_threshold）。

並行更新でも問題が起きます。2 台の端末が同じ投稿をほぼ同時に別の位置へ動かすと、どちらも同じ古い行を削除し、それぞれ別のキーで行を挿入します。結果として、同じ投稿が 2 か所に現れます。

ワイドカラム型ストアでは、時刻順のテーブルはそのまま残し、上書きだけを「プロフィールごとの小さなパーティション（投稿 ID → キー）」に置くほうが安全です。版をそのパーティションの static 列に置けば、同じパーティションへの条件付きバッチ（IF version = ?）で、キーの書き込みと版の更新を 1 回の compare-and-set にできます（Apache Cassandra のドキュメント）。ただし、この compare-and-set で守れるのは移動だけです。新規投稿は時刻順のテーブルに書くので版の更新と 1 回の操作にまとめられず、2 つのテーブルを 1 つのスナップショットで読むこともできません。そこで、新規投稿では行を書いてから版を進め、キャッシュを埋める処理では版を読んでから行を読みます。逆の順にすると、古い並びが新しい版のキャッシュに入ることがあります。読み取りでは上書きをすべて読み、時刻順の行から上書きのある投稿を除きながら、両者をキーの順にマージします。上書きが増えたプロフィールについては、並べ替え済みの一覧を非同期に作っておくこともできます。

4. 並び順キーの選び方

4.1 6 つの候補

利用者が決める順序を保存する方法として、よく使われるものを比べます。

連番の書き込み量を、規模感をつかむための仮定で見積もります。月間アクティブユーザー 30 億人の 1% が、1 日に 20 回ずつ投稿を動かすとします。移動は 1 日 6 億回、平均で毎秒約 7,000 回です。ピークを平均の 3 倍とすると毎秒約 2 万回になります。1 回の移動を 1 行で書ける方式なら、書き込みも毎秒約 2 万行です。連番で平均 100 件離れた位置へ動かすなら、毎秒約 200 万行を書き換えます。書き換えた行ごとに、レプリケーションやキャッシュの更新も発生します。長く待たれていた機能なので、提供開始直後の移動はこの仮定よりずっと多くなると考えられます。

次のデモでは、同じ 12 件のグリッドを連番、間隔を空けた整数、可変長の小数の 3 方式で同時に管理しています。L（最も古い投稿）を先頭へ動かすと、連番は 12 行を書き換え、ほかの 2 方式は 1 行で済みます。「同じ隙間に 5 回挿入」を何度か押すと、間隔を空けた整数で再採番が起き、小数のキーが伸びていきます。

4.2 浮動小数点数では精度が足りなくなる

中点を浮動小数点数で計算する方法は、実装が最も簡単です。しかし倍精度浮動小数点数の仮数部に格納されるのは 52 ビット（精度は 53 ビット）なので、同じ隙間に挿入を続けると、中点が両端のどちらかと等しくなります。筆者が JavaScript で試すと、1 と 2 のあいだで「1 と直前に入れた値の中点」を取り続けた場合、新しい値を作れたのは 52 回まででした。

値が大きいほど、使える回数は減ります。Date.now() と同じミリ秒の時刻（2026 年で約 1.79 × 10¹²）をキーの初期値にすると、1 秒違いの 2 件のあいだには 22 回しか入りませんでした。Figma が並び順に 64 ビットの浮動小数点数ではなく任意精度の分数を使うのも、多くの編集のあとで精度が足りなくならないようにするためです（Wallace, 2017）。

4.3 投稿 ID を種にした 64 ビット整数キー

3.2 節の設計では、上書きしない投稿のキーは投稿 ID そのものです。2 章の ID の構成では、ID の値で 1 ミリ秒が 2²³ に当たります（下位 23 ビットがシャード ID と連番なので）。1 秒違いの 2 件の ID は約 8.4 × 10⁹、つまり約 2³³ 離れていて、あいだに中点を 30 回以上取れます。整数の中点が取れなくなったら、近くの数件のキーを等間隔に振り直します。Go で書くと次のようになります。

// Entry はグリッド上の投稿です。Key は実効キーで、上書きがあればその値、
// なければ時刻順に増える投稿 ID です。グリッドは Key の大きい順に並べます。
type Entry struct {
	PostID int64
	Key    int64
}
 
// keyBetween は lo と hi のあいだの整数を返します。
// 間に整数がなければ ok = false を返し、呼び出し側が再採番します。
func keyBetween(lo, hi int64) (key int64, ok bool) {
	if hi-lo < 2 {
		return 0, false
	}
	return lo + (hi-lo)/2, true // (lo+hi)/2 は大きな ID どうしで桁あふれする
}
 
// minGap は再採番のあとに隣どうしのあいだに残す間隔です。
const minGap = 1 << 16
 
var errKeySpace = errors.New("grid: key space exhausted")
 
// place は post を es[g-1] と es[g] のあいだに置き、書き込む行を返します。
// es は Key の昇順で、post 自身は含みません。ceiling は新しく発行した
// 投稿 ID で、先頭（g == len(es)）に置くときや、再採番の窓が先頭に
// 達したときの上限になります。呼び出し側は毎回渡します。
func place(es []Entry, g int, post, ceiling int64) ([]Entry, error) {
	lo, hi := bounds(es, g, g, ceiling)
	if k, ok := keyBetween(lo, hi); ok {
		return []Entry{{post, k}}, nil
	}
	// 隙間がなくなったので、g の周りの窓を 2 倍ずつ広げ、隣どうしに
	// minGap 以上の間隔を取れるところで窓の中を等間隔に振り直す。
	for size := 2; ; size *= 2 {
		from, to := max(g-size/2, 0), min(g+size/2, len(es))
		lo, hi := bounds(es, from, to, ceiling)
		n := to - from + 1 // 窓の中の投稿と、動かす投稿
		whole := from == 0 && to == len(es)
		if (hi-lo)/int64(n+1) < minGap && !whole {
			continue
		}
		step := (hi - lo) / int64(n+1)
		if step < 1 {
			return nil, errKeySpace
		}
		out := make([]Entry, 0, n)
		next := lo
		add := func(id int64) { next += step; out = append(out, Entry{id, next}) }
		for _, e := range es[from:g] {
			add(e.PostID)
		}
		add(post)
		for _, e := range es[g:to] {
			add(e.PostID)
		}
		return out, nil
	}
}
 
func bounds(es []Entry, from, to int, ceiling int64) (lo, hi int64) {
	lo, hi = 0, ceiling
	if from > 0 {
		lo = es[from-1].Key
	}
	if to < len(es) {
		hi = es[to].Key
	}
	return lo, hi
}

2 章の ID の構成に従って作った ID でこのコードを試しました。移動のたびに、単純な配列で並べ替えた結果と順序が一致すること、キーが狭義単調増加であること、どのキーも上限未満であることを確かめています。

• 300 件のグリッド（投稿の間隔は 1 秒から 1 日のあいだで無作為）で無作為な移動を 10 万回行うと、書き込みは 1 回あたり平均 1.005 行で、再採番は 30 回でした。
• 最悪の場合として、グリッドの中ほどの同じ隙間に 2 万回続けて挿入しました。1 秒違いの投稿のあいだでは、32 回目までは中点が取れ、33 回目で初めて再採番が起きました。1 日違いなら 49 回目まで取れました。2 万回の平均は 1 回あたり 1.2 行（1 秒違いの場合）で、1 回の再採番で書き換えた行は最大 65 行でした。

挿入のたびに順序を保つ整数ラベルを振り、隙間がなくなったら振り直す問題は、順序維持問題（order-maintenance problem）やリストラベリング問題として研究されてきました。Bender らは、ラベルの範囲が要素数の多項式程度の大きさなら、挿入 1 回あたりの振り直しを償却 O(log n) 件に抑えられることを、単純なアルゴリズムで示しています（Bender ら, 2002）。上のコードは窓を要素数で広げる単純な実装で、この理論上の保証はありませんが、2⁶³ という範囲は 1 つのプロフィールの投稿数よりはるかに大きく、上の実験では十分でした。

実装では、次の 3 点に注意します。

• 中点の桁あふれ。(lo + hi) / 2 は、ID が 2⁶² を超えると符号付き 64 ビット整数の上限を超えます。この方式（2011 年起点の 41 ビットのミリ秒）では、2028〜2029 年ごろに作られる ID がこの値を超えます。lo + (hi - lo) / 2 と書けば、lo と hi が 0 以上である限り桁あふれしません。二分探索で知られる不具合と同じ形です（Bloch, 2006）。さらにエポックから 2⁴⁰ ミリ秒（2045〜2046 年ごろ）を過ぎると ID の最上位ビットが立ち、符号付き整数としては負になるので、「0 以上で時刻順に増える」という前提そのものが崩れます。
• 先頭への移動。上限には、その場で新しく発行した ID を使います。ID は新規投稿と同じ採番器（同じシャード）で発行します。こうすると上書きしたキーがそれまでに発行した ID を超えないので、同じ採番器で後から発行される ID の投稿は、その上に来ます。別のサーバーの時計で作った値を上限に使うと、時計のずれによって、後から作った投稿の ID のほうが小さくなることがあります。共同投稿のように別のシャードで採番された投稿にも、同じずれが起こりえます。
• 同順の扱い。不具合で実効キーが同じ行ができても表示順が揺れないように、インデックスとクエリーの並び順には投稿 ID を 2 番目の列として加えます（3.3 節）。

4.4 可変長の文字列キーと照合順序

可変長の文字列を使えば、隙間がなくなることはありません。Figma は 0 と 1 のあいだの分数を文字列で表し、並べ替えでは 1 つの値を書き換えるだけにしています（Wallace, 2017）。David Greenspan の方法を実装した fractional-indexing は、62 進の数字（0-9A-Za-z）でキーを作ります。

代わりにキーが伸びます。fractional-indexing 4.0.0 で筆者が測ると、同じ隙間に 1,000 回挿入したキーは 169 文字になりました。1 文字で約 6 ビット（log₂ 62 ≈ 5.95）の分解能が増えるので、約 6 回の挿入で 1 文字伸びる計算です。一方、先頭への追加や末尾への追加を 1 万回続けても、キーは 4 文字でした。

伸びるキーには、上限と再採番が必要です。Jira が課題の順位に使う LexoRank では、順位の文字列が 128 文字に達すると 12 時間以内の再採番が予約され、160 文字に達するとすぐに再採番が始まります。254 文字以上になる順位の操作は止められます。再採番のあいだも、順位の操作は通常どおり行えます（Atlassian のドキュメント）。

文字列キーはバイト順で比較する前提で作られているので、照合順序にも注意が要ります。

• PostgreSQL で en_US などの言語向けの照合順序を使うと、大文字と小文字をまず同じ文字として比べるので、'a' < 'B' が真になります。バイト順では 'B'（0x42）のほうが 'a'（0x61）より小さいので、キーの順序が狂います。列には COLLATE "C" を指定するか、bytea 型を使います。
• MySQL 8.0 の utf8mb4 の既定の照合順序 utf8mb4_0900_ai_ci は大文字と小文字を区別しないので、a0 と A0 が等しいと判定されます。バイナリーの照合順序を使います。
• アプリケーション側でも、JavaScript の localeCompare で並べると誤った順序になります。fractional-indexing の README は通常の文字列比較を使うよう求めています。

4.5 この規模での選択

Instagram の規模なら、筆者は投稿 ID を種にした 64 ビット整数キーを選びます。キーは 8 バイトの固定長で、比較は整数の比較で済み、照合順序の問題もありません。既存の投稿を書き換えずに導入でき、4.3 節の実験のとおり、再採番を含めても、1 回の移動で書く行は平均でほぼ 1 行です。

可変長の文字列は、時刻のような自然な種がない一覧や、Figma のようにクライアントがサーバーの応答を待たずにキーを作る場合に向いています。

5. 書き込み：移動 API と並行更新

5.1 位置ではなく、すぐ前に来る投稿で指定する

移動 API は、移動先を位置の番号ではなく、移動後にすぐ前（グリッドを左上から読んだときの 1 つ前）に来る投稿で指定します。この投稿をアンカーと呼びます。位置の番号は、ほかの端末からの移動や新規投稿でずれますが、アンカーは投稿を名指しするので、ほかの投稿が動いても指す先は変わりません。

POST /v1/me/grid/moves HTTP/1.1
Content-Type: application/json
Idempotency-Key: "8e0c1f6a-2b7d-4c39-9f4e-5d1a7b3c6e20"
 
{"post_id": "4197176259380573189", "after": "4197170219582813190"}

HTTP/1.1 200 OK
Content-Type: application/json
 
{"grid_version": 42}

after を null にすると先頭（ピン留めの直後）への移動です。after にピン留めの投稿を指定した要求も、先頭への移動として扱います。動かす投稿がピン留めなら 409 を返し、アプリは先にピン留めを外すよう利用者に伝えます。after と post_id が同じ要求は 400 で拒否し、post_id がこのグリッドにない要求には 404 を返します。after の投稿が見つからないときは、削除やアーカイブの直後かもしれないので、409 と現在の版を返します（5.2 節）。

「A の直後へ」という要求は、続けて 2 回届いても、並びは 1 回届いたときと同じです。「1 つ上へ」のような相対的な操作は、2 回届くと 2 回動いてしまいます。ただし、タイムアウトした要求の再送が、そのあとに送った別の移動よりも遅れて届くと、古い操作をもう一度適用してしまいます。そこでアプリはドラッグ 1 回ごとに一意な値を Idempotency-Key ヘッダーに付け、サーバーは処理済みのキーと応答を一定時間保存して、同じキーの要求には保存した応答を返します（IETF の Internet-Draft）。重複した要求で版が進み、キャッシュが作り直されることもなくなります。

Idempotency-Key の値は、要求の中身から作ったフィンガープリントや応答と一緒に、移動と同じトランザクションで保存します。別々に書くと、移動をコミットしてから記録するまでのあいだにサーバーが落ちたとき、再送された移動がもう一度適用されます。保存済みかどうかは版の行をロックしたあとで調べ、見つかればロールバックして（版の増分も取り消されます）保存した応答を返します。そうすれば、処理中の要求と同じキーの再送はロックを待ち、元の要求がコミットしたあとで保存済みの応答を受け取ります。

この Internet-Draft は、キーの保存期間などの扱いを文書にして公開することも求めています。同じキーで中身の違う要求には 422 Unprocessable Content を、元の要求の処理中に届いた同じキーの要求には 409 Conflict を返すとしています。再送を待たせずに 409 にするなら、トランザクションの最初に pg_try_advisory_xact_lock でキーのハッシュ値のロックを試み、取れなければ 409 を返します。

取り消し（Undo）は、元のアンカーへの移動として送れます。移動で書き換えたのがその 1 行だけで、そのあとに版が変わっていなければ、移動前の sort_key（NULL を含む）をそのまま書き戻すこともできます。

ID は文字列で送ります。64 ビットの ID は、JavaScript の数値（倍精度浮動小数点数）が整数を正確に表せる 2⁵³ までの範囲を超えるからです。たとえば JSON.parse("4197176259380573189") が返す数値の正確な値は 4197176259380573184 で（コンソールには 4197176259380573000 と表示されます）、1 だけ大きい ID も同じ数値になります。Instagram Graph API も ID を文字列で返しています。

並び順キーはサーバーだけが計算し、クライアントには返しません。並び順キーを API の契約に含めなければ、再採番や表現の変更（整数から文字列へ、など）をクライアントに影響させずに行えます。

5.2 プロフィール単位で直列化する

同じプロフィールの並びを同時に書き換えるのは、同じ人が使う複数の端末か、1 つのアカウントを運用する複数の人です。3.3 節のとおり、グリッドへの書き込みはどれも版の行（grid_order）をロックしてから行います。1 つのプロフィールへの書き込みは、ふつうは人が操作する速さでしか届かないので、直列化しても待ちはほとんど生じず、プロフィールが違えば並行に処理できます。grid_entry と grid_order はプロフィールと同じシャードに置き、移動のトランザクションを 1 つのシャードで完結させます。共同投稿の行はそれぞれのプロフィールのシャードにあるので、共同投稿を削除したときや相手が抜けたときは、プロフィールごとに別のトランザクションで更新します。トランザクションのないストアでは、版を条件にした書き込み（compare-and-set）で同じように直列化します。

直列化しておくと、並行操作の結果は次のように決まります。

• 2 台の端末が同じ投稿を同時に動かした。後にコミットした移動が残ります。キーは 1 行の 1 列なので、投稿が 2 か所に現れることはありません。Kleppmann は、移動を「削除と挿入」で表すリストの CRDT では、同じ要素を同時に動かすと要素が重複することを示しました。そのうえで、要素ごとの位置を last-writer-wins レジスターに持たせて移動を表す方法を提案しています（Kleppmann, 2020）。この設計の sort_key は、要素ごとのレジスターに当たります。3.4 節の「削除と挿入」で起きた重複は、これと同じ問題です。
• 2 台が同じ隙間へ別々の投稿を入れた。後の移動は、前の移動が書いたキーを読んでから中点を計算するので、同じキーは生じません。Figma も、同じ位置への同時挿入ではサーバーが 2 件目に別の位置を割り当てるとしています。
• アンカーが同時に削除・アーカイブされた。409 Conflict と現在の版を返し、アプリに並びを読み直させます。

移動の応答では、増やしたあとの版を返します（アプリでの使い方は 6.3 節）。自動化した操作で並べ替えを繰り返されても再採番やキャッシュの作り直しが続かないように、プロフィールごとに移動の頻度を制限します。

5.3 まとめて並べ替えたときは最長増加部分列を使う

編集画面で何件も動かしてから最後に保存する UI や、計画ツールで決めた並びを取り込む API では、クライアントが範囲内の新しい並びをまとめて送ってきます。範囲内のキーをすべて振り直すと、書き込みもレプリケーションも範囲の長さに比例します。

書き換えが必要なのは、相対的な順序が変わった投稿だけです。新しい並びの各投稿について元の位置を並べた列を作ると、その最長増加部分列（LIS）に入る投稿は互いの順序が保たれているので、キーをそのまま使えます。LIS に入らない投稿にだけ、前後にある LIS の投稿のキーのあいだで新しいキーを振ります。隙間が足りる限り、書き換えは「範囲の長さ − LIS の長さ」件で、これが最小です。1 つの隙間に何件も入れるときは、中点を繰り返し取らずに隙間を等分します。30 件を約 2³³ の隙間に入れる場合、1 件ずつ、直前に入れた投稿と隙間の下端との中点に置いていくと、最後の隣どうしの間隔は約 2³ まで縮みますが、等分すれば約 2²⁸ ずつ残ります。

// keep は、クライアントが送ってきた新しい並びのうち、キーを書き換えずに
// 済む投稿に true を立てます。old[i] は、新しい並びで i 番目に来る投稿の
// 移動前の位置です。old の最長増加部分列に入る投稿は互いの順序が
// 変わっていないので、それ以外の投稿だけに新しいキーを振れば足ります。
func keep(old []int) []bool {
	res := make([]bool, len(old))
	if len(old) == 0 {
		return res
	}
	tails := []int{}              // tails[k]: 長さ k+1 の増加列の末尾の添字
	prev := make([]int, len(old)) // 列を復元するための 1 つ前の添字
	for i, v := range old {
		lo, hi := 0, len(tails)
		for lo < hi { // old[tails[k]] >= v となる最初の k を二分探索する
			mid := lo + (hi-lo)/2
			if old[tails[mid]] < v {
				lo = mid + 1
			} else {
				hi = mid
			}
		}
		prev[i] = -1
		if lo > 0 {
			prev[i] = tails[lo-1]
		}
		if lo == len(tails) {
			tails = append(tails, i)
		} else {
			tails[lo] = i
		}
	}
	for i := tails[len(tails)-1]; i >= 0; i = prev[i] {
		res[i] = true
	}
	return res
}

たとえば A B C D E F を E A B C D F に並べ替えると、元の位置の列は [4 0 1 2 3 5] で、LIS は A B C D F の 5 件です。書き換えるのは E の 1 件だけです。Vue 3 も、キー付きの子要素を更新するときに同じ方法（renderer.ts の getSequence）で、動かす DOM ノードを最小にしています。LIS の求め方は動的計画法の記事で扱いました。

まとめて送る並びのために、並び（投稿 ID の列）だけを返すリソース（たとえば GET /v1/me/grid/order）を用意し、その応答に版を ETag: "42" のように付けます。クライアントは新しい並びを同じリソースへ送るとき（たとえば PATCH /v1/me/grid/order）に、その並びを作ったときの版を If-Match で添えます。サーバーは、版が違えば 412 Precondition Failed で、If-Match がなければ 428 Precondition Required（RFC 6585）で拒否します。単発の移動はアンカーさえ残っていれば適用できますが、範囲全体の並びは、ほかの端末の変更と組み合わせて解釈し直せないからです。

版を ETag にできるのは、このリソースが並びしか返さないからです。いいね数のような投稿の本体も返す応答に付けると、版が同じまま中身が変わるので、If-None-Match で再検証したキャッシュに 304 Not Modified が返り、古い数字が残ります（RFC 9110 の 8.8.1 節）。そうした応答では、版は本文の grid_version で返します。

版はグリッドが変わるたびに進むので、ほかの端末からの移動だけでなく、新規投稿でも 412 になります。編集画面では利用者の操作をアンカー指定の移動の列として覚えておき、412 を受け取ったら並びを読み直して操作を適用し直し、新しい版で送り直します。アンカーが消えていた操作だけを利用者に確かめれば、長い編集を最初からやり直させずに済みます。

6. 読み取り：ページネーションとキャッシュ

6.1 並びが変わる一覧のページネーション

次のページを OFFSET で取ると、並びが変わったときに、動かしていない投稿まで重複したり抜けたりします。キーセット方式（直前のページの最後の行のキーより後ろを読む方式）なら、影響を受けるのは、動かした投稿と、まれに起きる再採番でキーが書き換わった近くの数件だけです。次のデモでは、閲覧者がページを読み込む合間に所有者が 2 回並べ替えたとき、2 つの方式で閲覧者に届く投稿を比べています。

OFFSET の端末では、J が先頭へ入ったことで後ろの投稿が 1 つずつずれ、C が 2 回届きました。B が後ろへ移ると今度は前に詰まり、F が一度も届きませんでした。F は誰も動かしていない投稿で、端末には F が抜けたことを知る手段がありません。キーセットの端末で起きたのは、動かした B が 2 回届き、先頭へ移った J が届かなかったことだけです（この 2 つは OFFSET の端末でも起きています）。B の重複は投稿 ID で取り除け、J は次に読み直したときに表示されます。

TAO の API にも、一覧の位置で範囲を指定する assoc_range と、time の値で範囲を指定する assoc_time_range があります。後者は、時刻順の一覧に対するキーセット方式です。

カーソルには、直前のページの最後の行の実効キーと投稿 ID に加えて、そのページを読んだときの版を入れ、署名した不透明なトークンとして返します（トークンの作り方はRPC と REST の記事の 4.5 節）。サーバーは次のページを読むときに版が変わったことに気づけるので、応答に「グリッドが変わった」という印を付けられます。印を受け取った端末が読み直しを促すか、そのまま読み進めるかは、仕様として決めます。

再採番の影響もなくすには、次のページを読むときに、カーソルに入れた投稿 ID からその投稿の現在の実効キーを引き直します。再採番は窓の中の相対的な順序を変えないので、カーソルの投稿自身の位置が変わっていなければ、引き直したキーより後ろが正しい続きになります。位置が変わったかどうかは、3.3 節の moved_version とカーソルの版を比べて判定します。この列には、再採番以外で位置が変わったとき（移動、アーカイブからの復帰、時系列順へのリセット）に、そのときの版を書きます。位置が変わっていた場合や、行がなくなっていた場合（削除やアーカイブ）は、カーソルに入れたキーをそのまま使います。この判定のために、カーソルに入れる版は、ページの行と同じスナップショットで読むか、行より先に読みます。行のあとに読むと、そのあいだに動いた投稿を動いていないと判定し、動いた先から続きを読んでしまいます。

6.2 キャッシュの持ち方と無効化

最初のページはプロフィールを開くたびに必ず読まれるので、キャッシュが最も効く部分です。キャッシュには、並び（投稿 ID と実効キーの組）と投稿の本体を分けて持たせます。こうすると、いいね数やキャプションが変わっても並びのキャッシュは捨てずに済み、移動しても投稿の本体のキャッシュは捨てずに済みます。実効キーも持たせるのは、2 ページ目のカーソルに最後の行のキーが要るからです。

grid:{profile_id}:v{version}   ピン留め（最大 3 件）と、それに続く 2 ページ分（48 件）の投稿 ID と実効キー（表示順）
post:{post_id}                 投稿の本体（画像の URL、キャプション、いいね数など）

並びのキャッシュのキーには、グリッドの版を含めます。版はグリッドを変える書き込みのたびに進むので（3.3 節）、最初のページの中身が変われば必ず別のキーになります。読み取り側は、プロフィールの基本情報と一緒に現在の版を受け取り、その版の並びを読みます。版が進むと古い版の並びは読まれなくなり、TTL で消えます。基本情報のキャッシュは版が変わるたびに消す必要がありますが、投稿数を表示している以上、新規投稿や削除のときにはもともと消しているはずです。

キャッシュを埋める処理は、版とピン留めと並びを 1 つのスナップショットで読み、読んだ版のキャッシュに書きます。PostgreSQL の既定の分離レベルである READ COMMITTED では、同じトランザクションの中でも SELECT ごとに見えるデータが変わりうるので（PostgreSQL のドキュメント）、1 つの SQL 文で読むか、REPEATABLE READ の読み取り専用トランザクションで読みます。REPEATABLE READ はホットスタンバイのレプリカでも使えます（PostgreSQL のドキュメント）。遅れているレプリカから、要求された版より古い結果しか読めなければ、キャッシュには書かずにプライマリーから読み直します。これで版ごとのキャッシュには常に同じ並びが入るので、無効化の通知が遅れたり順序が入れ替わったりしても、古い並びを新しい版として返すことはありません。

版ごとのキャッシュに常に同じ並びが入るには、版の番号を使い回さないことも必要です。非同期レプリケーションのデータベースでフェイルオーバーが起きると、最後のいくつかのコミットが失われ、同じ番号の版が別の並びで再び発行されることがあります。キャッシュには失われた版の並びが残っているので、フェイルオーバーのたびに変わる世代番号を並びのキャッシュのキーに加えるか、そのシャードの並びのキャッシュを捨てます。世代番号は、版を比べるほかの場所（5.3 節の ETag、6.1 節のカーソル、6.3 節で端末が覚える版）にも含めます。比べるときは世代番号を先に比べ、世代が新しいほうを新しい版として扱います。grid_order の行も、時系列順に戻すときを含めて削除しません。消して作り直すと、版がまた 1 から数え直されるからです。

フォロワーの多いアカウントでは、移動のたびに基本情報のキャッシュが消えるので、多くのリクエストが同時にデータベースへ向かいます。Facebook の memcache の論文は、キャッシュミスしたクライアントの 1 つにだけ値を埋め直す権利（リース）を与え、ほかのクライアントには少し待ってから読み直させる仕組みを紹介しています。リースはキーごとに既定で 10 秒に 1 回しか発行しません。この仕組みで、特にこの問題が起きやすいキーの集合について、データベースへの問い合わせのピークが毎秒 1.7 万件から 1,300 件に下がったと報告されています（Nishtala ら, 2013）。リースは、無効化と埋め直しの順序が入れ替わって古い値が書き込まれる問題（stale set）も防ぎます。

TAO は、関連の一覧に書き込みがあったとき、キャッシュを消すのではなく、最新の一覧を取り直させます（refill）。キャッシュに持つのは一覧の先頭から連続する部分なので、消すと失う範囲が大きいからです。この設計でも、書き込み側はコミットしたあとで新しい版の並びをキャッシュに置き（読み方はキャッシュを埋めるときと同じです）、それから基本情報のキャッシュを消します（5.2 節の図）。逆の順にすると、新しい版を知った読み取りが、まだない並びを取りにデータベースへ向かいます。

基本情報のキャッシュに新しい版を書き込まずに消すのは、同じプロフィールへの 2 つの書き込みを別々のサーバーが処理すると、キャッシュへの書き込みの順序が入れ替わることがあるからです。v6 が書かれたあとに v5 が書かれると、TTL が切れるまで古い版の並びが返ります。消すだけなら順序が入れ替わっても結果は同じで、次の読み取りがリースを取って埋め直します。memcache の論文も、削除は何度実行しても結果が変わらないので、キャッシュを更新せずに削除すると書いています。

ただし、埋め直す読み取りが、書き込みをまだ反映していないレプリカに向かうと、消した直後に古い版が書き戻されます。そこで、キャッシュが埋め直しに使うデータベースのコミットログからも削除を送ります。この削除はそのデータベースが書き込みを反映したあとに届くので、古い版が残るのはレプリケーションの遅れのあいだだけです。COMMIT のあとで API サーバーが落ちて削除を送れなかった場合も、この削除で消えます。memcache の論文の mcsqueal は、各データベース（別の地域のレプリカを含む）がコミットした文から削除を取り出してキャッシュに送り、データの複製より先に無効化が届く競合を避けています。TAO も同じ配信経路を使い、無効化と refill の通知を、その地域のレプリカに書き込みが反映された直後に届けています。別の地域から転送した書き込みでは、書き込みが成功したときと、レプリカに反映されたときの 2 回、通知が届きます。

6.3 本人にはすぐ反映し、ほかの閲覧者には数秒の遅れを許す

並べ替えた本人は、変更がすぐ反映されることを期待します。アプリは移動を画面上で先に反映し、応答で受け取った版を覚えておきます。その後の読み取りでは、その版以上の並びを要求します。レプリカやキャッシュの版が古ければ、プライマリーから読み直します。

ほかの閲覧者には、レプリケーションとキャッシュの更新にかかる数秒の遅れを許します（6.2 節）。

7. 後方互換性：「先頭が最新」に頼っていた処理

7.1 作成時刻と表示順を別の概念にする

時系列順のグリッドでは、作成時刻の順と表示の順が一致していました。並べ替えを入れると、この 2 つは別の概念になります。作成時刻は「いつ投稿したか」で、「3 日前」のような表示、フィードの順位付け、分析に使います。表示順は「プロフィールのどこに置くか」で、プロフィールのグリッドにだけ使います。2 章で見た TAO の time フィールドに表示順を書くと、その値を時刻として読む処理がすべて誤るので、作成時刻と表示順は別の値として持ちます。

これまで「グリッドの先頭 N 件」を読んでいた処理は、そのどちらを意図していたのかを 1 つずつ確かめます。たとえば次のような処理です。

• 最新の投稿を、通知や検索結果のプレビューに出す処理
• 「最後の投稿から何日たったか」を特徴量にする機械学習のパイプライン
• 外部のサイトに最新の投稿を埋め込むウィジェット
• 新しい投稿から順に確認する審査や分析のジョブ

ハイラムの法則（Hyrum's Law）によれば、API の利用者が十分に多ければ、契約で何を約束したかに関係なく、観測できる振る舞いには、どれも誰かが依存するようになります。15 年以上「先頭が最新」だった一覧には、こうした暗黙の依存があるものと考えて確認します。

7.2 公開 API は作成時刻の意味を保つ

外部に公開した API は、作成時刻の意味を変えずに残します。Instagram Graph API の IG User Media は since と until による時間ベースのページネーションに対応し、2026 年 11 月時点のドキュメントでは「最も新しく作成されたメディアを最大 1 万件まで返す」と説明されています（Meta のドキュメント）。この一覧を表示順に変えると、until で区切った範囲が表示順の連続した区間にならず、作成時刻で範囲を指定してきた連携が誤った結果を受け取ります。表示順が必要な連携には、表示順を明示的に指定する新しいパラメーターやフィールドを追加します。並べ替えの提供に合わせて Meta が Graph API をどう扱ったかは、公開資料では確認できませんでした。

7.3 古いアプリと段階的な公開

モバイルアプリには、更新されない古いバージョンが長く残ります。古いバージョンでも、サーバーが表示順で返せばその順に表示されるはずです。ただし、端末内のキャッシュを作成時刻や ID で並べ直す実装があれば、所有者が並べ替えた順序が崩れます。利用の多い古いバージョンをサーバーの新しい応答で試し、並べ替えの編集画面は新しいバージョンのアプリにだけ出します。

公開では、版を進める処理、新しい読み取り経路、並べ替えの書き込みの順に有効にします。版で区別するキャッシュを読み始めるのは、グリッドを変えるすべての書き込み経路が版を進めるようになってからです。版を進めない古いサーバーが残っているうちに読み始めると、新しい投稿が載っていない並びが同じ版のキャッシュから返り続けます。並べ替えの書き込みを読み取りより先に有効にすると、古い読み取り経路を通る閲覧者には時系列順が表示され、所有者が見ている並びと食い違います。

段階 0 はサービスを止めずに進められますが、PostgreSQL では次の 2 点に注意します（ALTER TABLE と CREATE INDEX のドキュメント）。

• ADD COLUMN は行を書き換えませんが、ACCESS EXCLUSIVE ロックを取ります。長いトランザクションの後ろでロックを待つあいだ、そのテーブルへの後続の読み書きもすべて待たされるので、lock_timeout を短く設定し、ロックを取れなければやり直します。3.3 節のように 2 つの列を 1 つの ALTER TABLE で足せば、ロックを取るのも 1 回で済みます。
• CREATE INDEX CONCURRENTLY は既存の行をすべて読むので時間がかかります。また、トランザクションの中では実行できません。途中で失敗すると無効（INVALID）なインデックスが残り、検索には使われないまま更新の負荷だけがかかるので、削除してから作り直します。

上書きのないプロフィールについては、新しいクエリーの結果は古いクエリーと完全に一致するはずです。公開前に、本番の読み取りの一部で両方を実行して比べれば、新しい読み取り経路の誤りを利用者に見せる前に見つけられます。問題が起きたときは、上書きを読まない設定に切り替え、編集画面も隠します。キャッシュには上書きを反映した並びが残っているので、並びのキャッシュも捨てるか、キーを変えます。全員のグリッドが時系列順に戻り、誰にも表示されない並びを編集し続けることもなくなります。上書きのデータは残るので、設定を戻せば並べ替えた順序も戻ります。

8. 運用で見る指標

公開後は、次の指標を見ます。

• 移動の遅延とエラー率（ロック待ちのタイムアウト、デッドロック、409 の割合）
• 再採番の頻度と、1 回で書き換えた行数の分布。ふだんはほとんど起きないので、急に増えたら自動化した操作による乱用か不具合を疑う
• 最初のページのキャッシュヒット率と、リースで待たされたリクエストの数
• 上書きのないプロフィールについて、新旧のクエリーの結果が一致しなかった割合（0 であるべき）
• キャッシュから抜き取った並びのうち、データベースの現在の版と同じ版のものについて、データベースから読んだ並びと一致しなかった割合（0 であるべき）
• 端末が重複として取り除いた投稿の数と、「グリッドが変わった」という印を返した割合
• プロフィールごとの移動の頻度と、頻度の制限に達した回数

あわせて、ピン留めした行を除いて実効キーが重複している行や、存在しない投稿を指す行を定期的に探します。ピン留めした行は再採番の対象から外れるので、ほかの行と同じキーになることがあります。投稿 ID で同順を決めているので表示順は一意に定まりますが、それ以外の重複は採番の不具合の兆候です。

9. まとめ

時刻や ID の順で並んでいた一覧に、利用者が決める順序を加える場面は珍しくありません。プレイリスト、カンバンボード、課題のバックログ、お気に入りの一覧などです。既定の順序を残して差分だけを持つこと、順序をデータそのものではなく一覧と要素の関係に持たせること、表示順と作成時刻を別の概念として扱うこと。既定の順序がある一覧なら、この 3 点はそのまま使えます。

参考文献

• Hartley Charlton, Instagram Now Lets Users Reorder Posts on Their Profile Grid, MacRumors, 2026-06-09
• Angeline Jane Bernabe, Meta debuts new Instagram feature that allows users to rearrange posts on profile grid, ABC News, 2026-06-08
• Adam Mosseri, Inspiring Creativity That Brings People Together, Meta Newsroom, 2025-06-12
• Aisha Malik, Instagram will finally let you rearrange your grid, TechCrunch, 2025-06-12
• Ramesh Reddy, How to Rearrange Your Instagram Profile Grid in Any Order, TechPP, 2026-06-09
• Paula, How to Rearrange Your Instagram Grid (and Plan It Before You Touch Anything), Hopper HQ, 2026-10-07
• Jonathan Vanian, Instagram now has 3 billion monthly active users, CNBC, 2025-09-24
• Mike Krieger, Sharding & IDs at Instagram, Instagram Engineering, 2011（Medium への再掲は 2012 年）
• Nathan Bronson ほか, TAO: Facebook's Distributed Data Store for the Social Graph, USENIX ATC 2013
• Rajesh Nishtala ほか, Scaling Memcache at Facebook, NSDI 2013
• Evan Wallace, Realtime editing of ordered sequences, Figma, 2017
• David Greenspan, Implementing Fractional Indexing
• rocicorp/fractional-indexing
• Atlassian, Managing LexoRank
• Michael A. Bender ほか, Two Simplified Algorithms for Maintaining Order in a List, ESA 2002
• Martin Kleppmann, Moving Elements in List CRDTs, PaPoC 2020
• Joshua Bloch, Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken, Google Research, 2006
• PostgreSQL, Heap-Only Tuples (HOT)
• PostgreSQL, Modifying Tables
• PostgreSQL, ALTER TABLE
• PostgreSQL, CREATE INDEX
• PostgreSQL, Transaction Isolation
• PostgreSQL, Hot Standby
• PostgreSQL, Lock Management
• DataStax, CQL UPDATE
• Apache Cassandra, Tombstones
• Apache Cassandra, cassandra.yaml file configuration
• Apache Cassandra, Good use of BATCH statement
• IETF, The Idempotency-Key HTTP Header Field（Internet-Draft）
• IETF, RFC 6585: Additional HTTP Status Codes
• IETF, RFC 9110: HTTP Semantics
• Meta, IG User Media
• Hyrum Wright, Hyrum's Law
• vuejs/core: packages/runtime-core/src/renderer.ts