LexoRank とは何か？
世の中に転がってる LexoRank の日本語解説記事がどうにも腑に落ちない内容だったので、この記事をしたためることにしました。
はじめに
つい先日、とある記事を読んで LexoRank なるアルゴリズムの存在を初めて知りました。この LexoRank がどのような類のアルゴリズムかを自分の理解をもとに端的に述べると、リスト状に並べられた要素を任意の順序で並べ替えするために、個々の要素に「順序関係を示す情報」をいい感じに割り振るアルゴリズムの一つ、ということができるかと思います。
この類のアルゴリズムの利用に適したサービスの具体例としては、GitHub Projects や Trello などのタスク管理サービスが挙げられます1。これらのサービスでは往々にしてリスト表示されたタスク (イシュー) の順序をユーザーが自由に並べ替えできる機能が備わっていますが、この並べ替え機能の実現に一役買っているアルゴリズムである、と言えば何をするアルゴリズムなのかはなんとなく理解していただけるのではないでしょうか？
要素を順序付けする
さてここで LexoRank の説明に入る前の準備として、ごく単純なアルゴリズムを考えてみることにします。何らかの要素群に対する順序付けをナイーブに実現しようとすると、それぞれの要素に 0 から始まり 1 ずつ増加する数値を順序値として割り振って順序を表現する方法がすぐにでも思いつくことでしょう。例えば以下のように。
| 名前 | 順序値 |
|---|---|
| 石 | 0 |
| 部屋 | 1 |
| 囚人 | 2 |
| ゴブレット | 3 |
この方法で順序を入れ替える場合、移動する要素とその移動先との間にある要素すべての順序値を更新します。たとえば「石」を「囚人」と「ゴブレット」の間に移動するときは、順序値を以下のように更新することになります。
| 名前 | 順序値 |
|---|---|
| 部屋 | (1 →) 0 |
| 囚人 | (2 →) 1 |
| 石 | (0 →) 2 |
| ゴブレット | 3 |
この例から分かるように、単純なアルゴリズムでは順序の入れ替え操作において一つ以上の要素の順序値を更新する必要があります。これがせいぜい数十個程度の要素の順序を入れ替える程度であれば多少非効率であっても許容できるかと思いますが、数千もしくは数万の規模の要素の入れ替えをこのアルゴリズムで実現しようとすると、性能劣化が生じるであろうことは想像に難くないことでしょう。
次にこの入れ替え操作における順序値の更新をできる限り削減したアルゴリズムを考えてみます。今回は順序値に 1 ずつ増加する値ではなく、0 から 999 までの区間の整数を概ね均等な間隔になるように割り振ってみることにします。
| 名前 | 順序値 |
|---|---|
| 石 | 200 |
| 部屋 | 400 |
| 囚人 | 600 |
| ゴブレット | 800 |
ここで先ほどと同じように、「石」を「囚人」と「ゴブレット」の間に移動するとして、更新後の順序値として、隣り合う要素の順序値の中間値を採用することにします。この例だと 600 と 800 の中間なので 700 となります。
| 名前 | 順序値 |
|---|---|
| 部屋 | 400 |
| 囚人 | 600 |
| 石 | (200 →) 700 |
| ゴブレット | 800 |
この例では入れ替え対象である「部屋」の順序値だけを、「石」と「ゴブレット」の順序値の中間値で更新することで入れ替えを済ませることができました。このように、移動先の前後の要素の順序値の中間の値をもって入れ替え対象の順序値を更新することができれば、順序値更新は一回だけに抑えられるわけです。素敵ですね！
さてこの方法なら万事解決か？ というと、当然のことながら話はそう簡単ではありません。入れ替え操作を繰り返すたびに、場所によっては順序値の区間が徐々に狭まっていく可能性があります。さらに操作次第では、以下のように順序値が極端に偏ってしまう状況も十分発生し得ます。
| 名前 | 順序値 |
|---|---|
| 部屋 | 0 |
| 石 | 1 |
| ゴブレット | 998 |
| 囚人 | 999 |
この上記の状況において「石」を「ゴブレット」と「囚人」の間に移動しようすると… ああなんということでしょう！ 998 と 999 の間にはもう中間値として利用できる整数が不在すなわち枯渇してしまい、新たな順序値を割り振れなくなってしまいました。
このような状況に陥ってしまった場合 (というよりも、そのような状況が起こりそうになる前にそれを検知してやるべきことではあるのですが…)、順序値が均等な間隔となるように順序値を振り直す「リバランシング」をする必要が出てきます。このリバランシングによる順序値の振り直しそのものは比較的単純で、以下のように先頭から順にそれぞれ所定の値を割り振ればよいわけです。ね、簡単でしょ？
| 名前 | 順序値 |
|---|---|
| 部屋 | 0 → 200 |
| 石 | 1 → 400 |
| ゴブレット | 998 → 600 |
| 囚人 | 999 → 800 |
ただここで注意しなければならないことが一つあります。それはこの順序値の更新を逐次的に (先頭 or 末尾から順に) 処理して都度その更新された値を反映する場合、処理の最中に順序値に基づく順序関係が損なわれた状態が生じうる点です。上記のリバランシング例でいうと、「部屋」の順序値を 0 → 200 に更新した直後は、更新前の順序値 1 を持つ「石」との順序関係が一時的に崩れてしまうことがわかります。
このように逐次的なリバランシングでは処理中の順序関係の維持が保証できないため、RDBMS で順序付けされた要素を管理している場合は一つのトランザクションですべての順序値を一括更新する方法を採用することになるかと思います。
しかしトランザクションを使うとして、仮にリバランシングの対象となる要素が数万以上の規模で存在していた場合にはそれなりの処理時間を要することになるでしょう。またリバランシング中に行える操作もかなり限定されたもの、具体的には入れ替え操作や要素の追加・削除操作などは当然できません。共有ロックをかける必要のある操作も難しいでしょうし、できることは一切ロックをかけることなく、単に順序値に従って要素をソートし参照するぐらいになるでしょう。ここまでできることが制限されてしまうと、サービスによってはリバランシング中は縮退した状態でのサービス提供、もしくはサービスの一時停止を余儀なくされるかもしれません。
小数点数を採用すればリバランシングを回避できるか？
ここまでは順序値に整数を利用したアルゴリズムを見てきました。さてここで、悩ましいリバランシング問題の回避を試みることを目的に、整数の代わりに 0 以上 1 未満の小数点数を利用する方法を考えてみます。これまでと同じ例で、小数点数の順序値を割り振ったものが以下になります。
| 名前 | 順序値 |
|---|---|
| 石 | 0.2 |
| 部屋 | 0.4 |
| 囚人 | 0.6 |
| ゴブレット | 0.8 |
こちらもこれまでと同様に、「石」を「囚人」と「ゴブレット」の間に移動しようとすると、順序値の更新は以下のように「囚人」と「ゴブレット」の中間値を取って 0.7 となります。
| 名前 | 順序値 |
|---|---|
| 部屋 | 0.4 |
| 囚人 | 0.6 |
| 石 | (0.2 →) 0.7 |
| ゴブレット | 0.8 |
そしてこれが小数点数を利用することの利点になるのですが、整数を順序値として利用していたときとは異なり、理論上は中間値が枯渇することはありません。例えば上記の例で、「部屋」を「石」と「ゴブレット」の間に移動すると、中間値は 0.7 と 0.8 の中間値である 0.75 となります。このように小数点以下の桁数を無限に伸ばしていけば、どんな状況であっても要素の入れ替え操作が実現できるようになるわけです！ そう、無限の精度で小数点数を表現できる手段があれば、の話ですが…
もちろん、無限の精度で小数点数を表現するのはコンピュータの諸々のリソース的に簡単な話ではありません。なのでそこは妥協し、ある程度余裕をもった精度の上限を設定してその上限のもとで可変長での小数点数を表現するのが現実的な解になるかと思われます。しかし、そうなるとやはりいつかは中間値が作り出せない枯渇状態に陥る可能性が出てくるわけで、結局のところ小数点数をもってしても精度的な制約から「リバランシング」の問題がついて回ることになります。
LexoRank による順序の表現
このように、順序値を整数だろうが小数点数だろうがどのような手段で表現するにしても「リバランシング」の問題からは逃れられないわけですが、LexoRank はこのリバランシングの問題とは向き合いつつも、そのリバランシング中の不自由さを低減する仕組みを導入したことがこれまで見てきたアルゴリズムと異なる点になります。
その「リバランシング中の不自由さを低減する仕組み」については次のセクションで説明するとして、まずは LexoRank が一般的にどのような順序値を割り振るのかを見ていきましょう。実は LexoRank には厳格な仕様が存在するわけではなく、各種実装によって割り振られる順序値はまちまちである可能性はありますが、概ね以下のようになっています。
- Lexicographic order すなわち辞書式順序で順序関係を評価できる書式の文字列で表現される
- 「バケット」、「固定長の文字列」、「可変長の文字列 (最小0文字)」の 3 つの要素で順序値の文字列を構成する
- 「バケット」は、状況に応じて 0, 1, 2 のいずれかの値が使われる
- 「固定長の文字列」と「可変長の文字列」は、基数を 36 とした数値を alphanumeric (英語アルファベットと数字) で文字列化したものに相当する
- 「固定長の文字列」が整数部に、「可変長の文字列」が小数部の数値に相当する
- 実装によっては、この基数が異なる可能性がある
LexoRank の順序値の具体的な文字列は、例えば LexoRank の TypeScript 実装である lexorank-ts では 0|000000: や 0|aaaaaa: 、 0|bbbbbb:c のような文字列となり、これは以下の書式に従います。
バケット|固定長の文字列:可変長の文字列
「辞書式順序」というのは辞書における語句の並べ方のことであり、例えば 0|aaaaaa: 、 0|aaaaaa:b 、 0:aaabbb: の三つの順序は 0|aaaaaa: < 0:aaaaaa:b < 0|aaabbb: となります。
ここまでの説明を見てすでにお気づきのかたもいらっしゃるとは思いますが、実は LexoRank の順序値は前述した小数点数による順序値と本質的には同じものになります。つまり精度の上限は LexoRank における順序値の文字列に課す長さの上限 (最大長) に相当し、この最大長に達するまではリバランシングを必要とせずに自由に入れ替え操作ができるわけです。実際に二つの順序が隣り合う要素があったとして、それらの LexoRank による順序値が 0:hzzzzz: と 0:i00000: であった場合、この場合の中間値は元の文字列より 1 文字長い 0:hzzzzz:i で表すことができます。
「バケット」の本当の役割
ここまでの LexoRank の説明は世の中にすでに存在する LexoRank 解説記事とさほど違いはないわけですが、ここからこの記事を書いた理由である「バケット」の解説に入っていきます。
この「バケット」は他の解説記事では「中間値が割り振れない場合に使われるもの」みたいな説明をよくみるのですが、これは明らかに間違った説明です。前述したように、中間値を割り振ろうとしたときに隣接し合う順序値 (の長い方) の文字列と同じ長さを維持できない場合は、末尾に 1 文字追加し文字列を 1 文字分長くして対応するのであって、この目的でバケットを利用することはありません。そもそもバケットは LexoRank の順序値の文字列において先頭に位置しており、このバケットを変更するということはつまり、辞書式順序の下での順序を大きく変えることになってしまい、結果的に順序関係の破壊を引き起こしてしまいます。
では、LexoRank の「バケット」は何のために存在するのでしょうか？ それはこれまでに何度か言及してきた「リバランシング」に深く関係しています。LexoRank においてもリバランシングは避けて通れない問題であることはすでに示唆した通りで、バケットはこのリバランシングの処理を逐次的に実行できる余地を作り出すのです。
バケットの導入がどのように逐次的なリバランシングを実現するのかを、以下の例を用いて説明します (この例では、LexoRank の順序値を構成する可変長の文字列長を最大 10 文字に制限し、また理解のしやすさを優先して 10 を基数として数値を文字列表現、つまり数値をそのまま文字列で表すものとします)。
| 名前 | 順序値 |
|---|---|
| 石 | 0|000000:0000000000 |
| 部屋 | 0|000000:0000000001 |
| 囚人 | 0|999999:9999999998 |
| ゴブレット | 0|999999:9999999999 |
見ての通り、「石」と「部屋」、および「囚人」「ゴブレット」の間はそれぞれ中間値が枯渇しており、リバランシングが今すぐ必要な状態にあります。この場合のリバランシングは最も大きな順序値をもつ (すなわち順序的に末尾の) 要素から先頭に戻る形で逐次的に処理をしていきます。
リバランシングによって割り振られる順序値は、数値部分は均等な間隔となるような数値、バケットについてはこの場合は 1 が設定されます。更新前後の順序値は以下のようになり、これが「ゴブレット」→「囚人」→「部屋」→「石」の順に更新されることになります。
| 名前 | 順序値 |
|---|---|
| 石 | 0|000000:0000000000 → 1|200000: |
| 部屋 | 0|000000:0000000001 → 1|400000: |
| 囚人 | 0|999999:9999999998 → 1|600000: |
| ゴブレット | 0|999999:9999999999 → 1|800000: |
ここで注目したいのが、逐次更新途中のどこをみても元々の順序が完全に保たれるという特性です。つまりLexoRank を順序値に採用している場合は、要素の順序値を一つずつ更新する方法であってもリバランシング中の要素の順序は損なわれることはなく、ゆえにリバランシング中に行える操作の幅がトランザクションを利用する方法よりも広がりうるわけです2。
バケットはリバランシングの都度、0→1、1→2、2→0 のように変化します。またバケットの変化が 0→1、1→2 の場合は、リバランシングでは最も大きな順序値から先頭に向かって処理し、2→0 の場合は逆に最も小さな順序値から末尾に向かって処理することになります。リバランシングの最中を除き、バケットの値は必ず 0, 1, 2 のいずれか一つの値だけが使われます。バケットの値が 2 つ使われるのはリバランシングの最中だけとなります。
まとめ
このように、LexoRank を採用して順序値を割り振っていたとしてもリバランシングの問題からは逃れられない一方で、リバランシング中に実施できる操作はトランザクションを利用したリバランシングよりも広がる可能性があります。ゆえに、LexoRank を利用することでリバランシング中のサービス縮退の範囲を小さくしたり、サービス提供の一時停止といった事態を回避できる可能性が出てくるわけです。
参考サイト
- Lexorank — Managing Sorted Tables With Ease
- LexoRank におけるリバランシングの必要性やバケットの利用目的について適切な解説がなされています
- Jira의 이슈 정렬 방식이 Integer 방식이 아니라고?!
- Google 翻訳を通して読む限りでは、LexoRank の実装と利用における工夫にまで踏み込んだ解説がされているようです