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

2020-07-14

目次

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

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

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

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(片方向リスト)ですね。

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の場合を考えてみると以下のようになります。

list2

つまり入れ替える前のIssueであるissue_id=3をpreviousissueidとして持つissue_idと当事者であるissue_id=2issue_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方式ではpreviousissueidの不整合がおきるとリスト構造が壊れてしまいます。 そのため更新の不整合を防ぐためtimestampを送っており最新の状態が維持されていないと以下のような案内をユーザにしています。

invalid

まとめ

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

Loading...