Lexorank
並び替え機能付きリストで、個々の要素に割り振られるランキング情報を扱うアルゴリズム
GreenHopperなランク管理アルゴリズムが持つ、リバランシング時の問題をいい感じに扱う
仕組み
ランク情報として辞書順キーを使う
3つのパートから構成されるランク値を持つ
Bucket
リバランシング時に順序関係を壊さないようにするための値
FixedKey
基本的なランクとして使用される固定長キー
VariableKey
FixedKey 枯渇時に割り当てられる可変長キー
並べ替え
GreenHopperと同様に、前後のアイテムの間にある値のキーに更新する
リバランシング(再インデックス)
更新処理中のどの時点を見てもランキング順序が壊れないようにできる
Bucket が最大値でないとき
ランキングの最下位要素から処理
Bucket の値を辞書順で+1して、FixedKey (, VariableKey) にbalancedなキーを割り当てていく
Bucketが最大値のとき
ランキングの最上位要素から処理
Bucket の値を辞書順の最小値に戻して、FixedKey (, VariableKey) にbalancedなキーを割り当てていく
周辺情報
kvandake/lexorank-ts: A reference implementation of a list ordering system like JIRA's Lexorank algorithm
Lexorank の TypeScript 実装
Bucket のデフォルトは 0~2 の三種類 (変更可)
キーは36進の値
JIRAのチームが開発し、チケットの並び替えに使っているらしい
Managing LexoRank | Administering Jira applications Data Center 10.3 | Atlassian Documentation
リスト状に並べられた要素を任意の順序で並べ替えするために、個々の要素に「順序関係を示す情報」をいい感じに割り振るアルゴリズムの一つ
LexoRank とは何か? - k11i.biz
資料
LexoRank とは何か? - k11i.biz
1. Sequential integer index な ランキング
優先度の高い(低い)順に整数値を割り当てていく
最もシンプルな実装方法
整数の順序関係を用いる
並べ替えの変更コストが高いのが問題
2. GreenHopper (integer) なランキング
並べ替えのコストを解消している
ランキング値が枯渇する点が問題
リバランシング(ランキング値の振り直し)が必要になる
リバランシングでは処理中のランキングが壊れる点が問題
3. GreenHopper (float) なランキング
integerに比べランキング値は枯渇しづらくなるが、いつか枯渇する点は変わらない
浮動小数点数は小数そのものではないため
2.と同様にリバランシングの問題を持つ
4. Lexorank
リバランシング問題を解消する仕組みとして導入
Lexorank — Managing Sorted Tables With Ease | by Çağdaş Alagöz | turkcell | Medium
1. Basic ranking
Sequential Integer index なランキングを紹介
データが多いと並べ替えの変更コストによるパフォーマンス問題につながる
2. GreenHopper Ranking
Green Hopper (integer) を例として紹介
再インデックス時にロックが必要
3. Lexorank
Lexorank 自体の仕組みと、そのTypeScript 実装の中身 kvandake/lexorank-ts について少し紹介
再インデックス中でも順序が保持されたデータを取得できると紹介
Jira의 이슈 정렬 방식이 Integer 방식이 아니라고?!
既存のランキングシステムと、それぞれの問題点を紹介
1. Integer方式
sequential integer index なランキングを紹介
順序変更時の修正範囲が大きい (O(N))
2. GreenHopper方式
例は integer
ランクの枯渇・リバランス時のシステム停止
3. Linked List方式
ランク変更コストはあまり重くない
クエリしようとするとフルスキャンになる
それらを解決するものとして Lexorank を紹介
キーの説明がわかりやすい
リバランスのタイミングの話・実装など、応用めな話が詳しく書いてある
JIRA lexorank explained - YouTube
Managing LexoRank | Administering Jira applications Data Center 10.3 | Atlassian Documentation