GitHubのMilestoneでIssueの順序を保持する実装方法

GitHubのMilestoneのIssueは順番がドラッグ＆ドロップでいいかんじに入れ替えれます。
このような動作をさせるため、データベースにレコードを入れてその順序を保持するためにはどのようなスキーマにするのがいいのでしょうか。
GitHubのMilestoneでIssueの順序を保持するためにどのようにGitHubが実装しているか想像しながら考えてみます。

テーブルのスキーマとレコード

以下のようなMilestoneを考えてみます。

MilestoneでIssueの順序を変えて、そのリクエストクエリを見た感じだと、テーブルのスキーマとレコード例は以下のようになっていそうでした。

| milestone_id | issue_id | previous_issue_id |
| ------------ | -------- | ----------------- |
| 1            | 1        |                   |
| 1            | 2        | 1                 |
| 1            | 3        | 2                 |
| 1            | 4        | 3                 |

Milestoneのid=1にはissueが4つあり、上から順番に1, 2, 3, 4とIssueが並んでいるというデータです。
まさにSingly Linked List(片方向リスト)ですね。

リクエストと想像する内部処理

たとえばIssueの2をドラッグして3と入れ替えると以下のようなリクエストがフロントエンドから飛びます。
item_idはうごかしたIssueのid。prev_idは動かしたIssueの前にあるIssueのidです。
一番まえにIssueを動かした場合はprev_idは空になります。

item_id: 2
prev_id: 3
timestamp: 1594724695

サーバ側ではどのように処理をすればいいのでしょうか。

その前にSingly Linked Listの場合を考えてみると以下のようになります。

つまり入れ替える前のIssueであるissue_id=3をprevious_issue_idとして持つissue_idと当事者であるissue_id=2とissue_id=3のデータを入れ替えればよさそうです。
3つのレコードの値を更新すると以下のようになります。

| milestone_id | issue_id | previous_issue_id |
| ------------ | -------- | ----------------- |
| 1            | 1        |                   |
| 1            | 2        | 3                 |
| 1            | 3        | 1                 |
| 1            | 4        | 2                 |

マイルストーンに何レコード紐付いていようと3レコードを更新するだけで順序を入れ替えることができました。

GitHub方式のメリット

順序を実装する他の方法だと以下のようにorderのフィールドを保持しソートする方法があります。
ただこの方法だと1行目の最後の行に移動させるとすべての行のorderを更新をしなければいけません。
まさに配列と同じですね。
よってGitHub方式は更新するレコードが短くなるという利点があります。

| milestone_id | issue_id | order |
| ------------ | -------- | ----- |
| 1            | 1        | 1     |
| 1            | 2        | 2     |
| 1            | 3        | 3     |
| 1            | 4        | 4     |

GitHub方式のデメリット

レコードをソートしてフロントエンドに返すときにすべてのレコードを取得する必要があります。
orderでソートするということができないためです。
Issue一覧ではページングしているのにMilestoneのIssue一覧ではページングしていません。
これはソートができないためにすべてを取得しているのかなと想像しています。

更新時の不整合について

GitHub方式ではprevious_issue_idの不整合がおきるとリスト構造が壊れてしまいます。
そのため更新の不整合を防ぐためtimestampを送っており最新の状態が維持されていないと以下のような案内をユーザにしています。

まとめ

データベースで順序を保持するにはさまざまな方法があると思いますが今回はGitHubの方法を調べてみました。
内部的にどのようになっているかわからないですが想像できる範囲でスキーマを考えてみました。
リストとアルゴリズムの効率という古典的なものがテーブルにも反映されていそうでおもしろかったです。