今回は、Jiraで使用されている「LexoRank」という並び替えシステムについて解説します。ToDoリストやタスク管理ツールでよく見かける「ドラッグ＆ドロップで並び替え」の機能がどのように実現されているのか気になったことはありませんか？このシステムは単純なように見えて、実は工夫が詰まっています。

並び替え機能の課題

まず、「リストの順序を保存する」という問題について考えてみましょう。

ユーザーがリストの項目をドラッグ＆ドロップで自由に並び替えられるようにするには、どのようにデータベースに保存すればよいでしょうか？この問題に対するアプローチをいくつか見ていきましょう。

アプローチ1: 整数の位置カラムを使う方法

もっとも直感的な方法は、各項目に数値の位置（ポジション）を割り当てる方法です。

CREATE TABLE todos (
  task TEXT,
  pos SERIAL, -- 位置を表す自動増加カラム

  UNIQUE (pos)
);

これで新しい項目を追加する場合は簡単です：

INSERT INTO todos (task)
    VALUES ('SQLを試す'),
           ('記事を書く'),
           ('休憩する'),
           ('繰り返す');

SELECT * FROM todos ORDER BY pos ASC;
/*
┌─────────────────┬─────┐
│      task       │ pos │
├─────────────────┼─────┤
│ SQLを試す       │   1 │
│ 記事を書く      │   2 │
│ 休憩する        │   3 │
│ 繰り返す        │   4 │
└─────────────────┴─────┘
*/

しかし、リストの途中に新しい項目を挿入したい場合や既存の項目を並べ替えたい場合に問題が発生します。例えば、項目2と3の間に「記事を編集する」という新しいタスクを挿入するとします。これには、位置3以降の項目を1つずつ後ろにずらし、新しい項目を位置3に挿入する必要があります。

-- 位置3以降の項目を1つ後ろにずらす
UPDATE todos SET pos = pos+1 WHERE pos >= 3;
/*
ERROR: 23505: duplicate key value violates unique constraint "todos_pos_key"
DETAIL: Key (pos)=(4) already exists.
*/

この方法では多くの行を更新する必要があり、効率的とは言えません。また、一時的に一意制約に違反する可能性があるため、制約を回避する工夫も必要かもしれません。

改良版: 間隔を空けた整数を使う

位置の値に間隔を空けておくことで、この問題を部分的に解決できます。

CREATE SEQUENCE todos_gapped_seq
  INCREMENT BY 65536;

これにより、各項目の間に65536個分の空きができます。新しい項目を挿入する際には、前後の項目の位置の中間値を使えば良いのです。しかし、何度も同じ場所に挿入を繰り返すと、結局間隔が埋まってしまい、大規模な更新が必要になります。

アプローチ2: 小数点を使う方法

整数の代わりに小数点を使うと、項目間に無限に値を挿入できるように思えます。

CREATE TABLE todos (
  task TEXT,
  pos FLOAT NOT NULL
    DEFAULT nextval('todos_seq'),

  UNIQUE (pos)
);

これで項目2と3の間に新しい項目を挿入するのは簡単です：

INSERT INTO todos (pos, task) VALUES
  ((2.0+3)/2, '記事を編集する');

しかし、浮動小数点数（FLOAT型）には精度の限界があります。例えば、1000と1001の間に繰り返し項目を挿入していくと、38回目の挿入で精度の限界に達し、1000という値に丸められてしまいます。

┌────┬──────────────────┐
│ i  │       val        │
├────┼──────────────────┤
│ 37 │ 1000.00000000001 │
│ 38 │             1000 │
│ 39 │             1000 │
└────┴──────────────────┘

これは、同じ位置に異なる項目が存在することになり、順序が壊れてしまう原因になります。

NUMERIC型（任意精度の小数）を使えば精度の問題は解決できますが、頻繁に並び替えが行われるとデータサイズが大きくなっていく問題があります。

アプローチ3: LexoRank - Jiraの解決策

Jiraでは「LexoRank」という仕組みを使って、この問題を解決しています。「LexoRank」という名前は、次の2つの要素から成り立っています：

Lexo - lexicographical（辞書順）の略で、アルファベット順のソートを意味します
Rank - 項目の順序・ランクを意味します

LexoRankでは、各項目に英数字の文字列によるランク値が割り当てられます。項目の順序を変更すると、そのランク値も更新され、前の項目のランクより大きく、後ろの項目のランクより小さい値になります。

例えば、Jiraでタスクを並び替えると、次のようにランク値が更新されます：

Key     Summary     Rank
SAN-1   テスト1     2|i019qh
SAN-2   テスト2     2|i019qn
SAN-3   テスト3     2|i019qp
SAN-4   テスト4     2|i019s3

ここで、SAN-3をSAN-2の上に移動すると、ランク値が 2|i019qp から 2|i019qk に更新されます。これは、SAN-1のランク値 2|i019qh より大きく、SAN-2のランク値 2|i019qn より小さい値です。

LexoRankのバケット機能

LexoRankの特徴的な仕組みとして「バケット」があります。バケットとは、ランク値を格納するコンテナのようなものです。Jiraは3つのバケット（0、1、2）を持っており、通常は1つのバケットだけが使用されます。

上の例では、値の先頭に「2|」という接頭辞があります。これは、バケット2が使用されていることを示しています。

長期間にわたって多くの並び替え操作が行われると、ランク値の長さが増加します。そのため、定期的にリバランス（再調整）が行われ、ランク値がより短くなるように分散されます。

リバランス中も通常通り並び替え操作を続けることができるのが特徴的です。これはバケット機能によって実現されています。リバランスが始まると、システムは新しいランク値を別のバケットに格納し始めます。例えば、バケット2からバケット0に移行する場合：

リバランス開始時、すべてのランク値はバケット2にあります
リバランス中、新しい並び替え操作はバケット0に対して行われます
同時に、バケット2の既存のランク値は徐々にバケット0に移動されます

これにより、リバランス処理中もシステム全体をロックすることなく並び替え操作が可能になります。Jiraのような大規模なシステムでは、多くのユーザーが同時にタスクの並び替えを行うことがあるため、この仕組みはユーザー体験を損なわないために非常に重要です。

まとめ

リストの並び替え機能を実装する方法はいくつかありますが、それぞれに長所と短所があります：

整数の位置を使う方法: 実装は簡単ですが、挿入や並び替えの際に多くの行を更新する必要があります。
小数点を使う方法: 実装も比較的簡単ですが、精度の限界があります。
LexoRank方式: 英数字の文字列を使った順序付けで、Jiraが採用している方法です。バケットとリバランスの仕組みにより、長期間の使用でも問題が発生しにくいのが特徴です。

実際の開発では、acadea/lexorankのようなオープンソースライブラリを活用することで、簡単にLexoRankに似た機能を実装できます。このライブラリは非常にシンプルながらも効果的なソリューションを提供しています。

アプリケーションの要件や規模に応じて最適な方法を選ぶことが重要です。小規模なアプリケーションであれば単純な整数の位置でも十分かもしれませんが、大規模で長期間使用されるアプリケーションではLexoRankのような堅牢な仕組みが適しているでしょう。

参考文献