Fractional indexingによる並び替えAPIとデータ構造

ぺりー

·

Follow

Published in

Pairs Engineering

·

15 min read

·

Dec 15, 2023

--

Share

🎅🏻 This post is part of the Eureka Advent Calendar 2023 🎅🏻

こんにちは！明日納車予定でわくわくが止まらない 23新卒 Eureka Back-end Engineerのぺりーです！

本記事では更新頻度の高いユーザーコンテンツ(以下UGC)の順序を保持し、自由に並び替えるAPIとデータ設計について考えてみたいと思います。

本記事ではPairsのユーザーコンテンツをソートする機能の代表格であるプロフィール画像を例に説明していきます。
Pairsでは複数のプロフィール画像を設定することができ、その中からドラッグ&ドロップでメイン画像を決めたり、サブ画像の順序を並び替えたりすることができます。

Pairsのプロフィール画像の並べ替えでは、一度のドラッグ&ドロップで理想の並び順になることは少なく、数回に分けてドラッグ&ドロップを行い、ユーザーの理想の並び順になることが一般的です。

1. Background

UGCの順序を更新する際のデータ更新が非効率だなと思っていたのがこの記事を書こうと思ったきっかけです。

Pairsでは、インクリメンタルなインデックスを付与することでUGCの順序を保持しています。

type UserImage struct {
 ID     int
 UserID int
 Index  int    // 0が最小の並び順のインデックス
 Path   string // 画像のパス
}

type UserImages []UserImage

func (e *UserImages) Sort() {
 sort.Slice(e, func(i, j int) bool {
  return e[i].Index < e[j].Index
 })
}

var userImages = UserImages{
 {ID: 1, UserID: 200, Index: 1, Path: "image1.png"},
 {ID: 2, UserID: 200, Index: 2, Path: "image2.png"},
 {ID: 3, UserID: 200, Index: 3, Path: "image3.png"},
 {ID: 4, UserID: 200, Index: 4, Path: "image4.png"},
 {ID: 5, UserID: 200, Index: 5, Path: "image5.png"},
}

順序の並び替えを行う際には、以下のように新しい並び順の配列を受け取り、アプリケーション側で全てのインデックスを振り直して更新を行なっています。

そのため、ID: 1の要素を最後の画像にする際はユーザー画像の全インデックスを更新してしまいます。

curl -XPUT 'https://api/image'
-d "{\"image_ids\":[2, 3, 4, 5, 1]}"

 var userImages = UserImages{
+ {ID: 2, UserID: 200, Index: 1, Path: "image2.png"},
+ {ID: 3, UserID: 200, Index: 2, Path: "image3.png"},
+ {ID: 4, UserID: 200, Index: 3, Path: "image4.png"},
+ {ID: 5, UserID: 200, Index: 4, Path: "image5.png"},
+ {ID: 1, UserID: 200, Index: 5, Path: "image1.png"},
 }

更新頻度の少ないマスターデータや、データ量が多くない場合であれば、特に問題はないかもしれませんが、更新頻度が高い場合には、より効率的にデータ更新を行いたいです。

調べてみるとFigmaでは複数人の同時編集を可能にするためにFractional indexingを導入していることがわかりました

Pairsの特性上、画像の並び替えできるのはログインユーザーの画像のみで1ユーザーが自身のリソースにシーケンシャルにアクセスをするという点でFigmaとは大きく異なります。

とはいえ、全更新する場合にはデッドロックを引き起こしたり、リクエストペイロードや通信量も大きくなりがちです。

* なおクライアント側のリクエストタイミングの調整によって全更新の頻度を下げ、負荷を下げる方法も考えられますが、本ケースではこれを考慮しません。

この点に注意しながら、より効率的な並び替えのAPIとデータ設計について考えてみたいと思います。

いくつかの並び替えのアルゴリズムと比較しながら整理していきます。

2. 様々な並び替えアルゴリズム

2.1. Swap

Swapは2要素の交換をすることで並び替えを行います。
そのため、必ずデータ更新対象は2になり、とても効率が良いことがわかります。

一方、2要素の交換以外にSwapを適用する場合はこの限りではありません。

a, b, c, dの順に並んだ要素があるとき、aを最後に並べることで、b, c, d, aという順序になるようにするとします。

要素を入れ替えてb, c, d, aの順序にする場合はO(N)となるため、あまり効率的とは言えません。

このようにSwapアルゴリズムは2要素の交換に適しており、逆に言えばUIに影響されることも多く、ドラッグ&ドロップで並び替えができるPairsでは採用されませんでした。

2.2. 全更新

次に一度で全て置き換える場合を考えてみます。
この場合にはすべてのインデックスを一度に更新する必要があります。

要素数が多い場合にはデッドロックの誘因になったり、payload自体も大きくなりがちです。

1つの要素の順序を変えるだけなら1つだけを更新対象にするのが理想的です。

2.3. Fractional indexing

Fractional indexing(部分インデックス)とは整数インデックスに代えて、分数や少数を使用することで既存のインデックスを変更せずに位置を指定することができるアルゴリズムです。

まずは数値をソートキーにする例を取り上げます。

2.3.1. 数値をソートキーにする

全てのインデックスを0<index<1の少数にして、0または1で平均値を取るようにします。

可読性はそのままで、更新対象も一つだけになりました。
次に要素と要素の間に要素を入れる例を見てみます。

b, cの中間にaを移動させるとき、b, cのインデックスの平均値になっていることがわかります。

全てのインデックスは 0.から始まるため、アプリケーション側では 0. を省略して文字列で格納します。

文字列として扱うことで数値よりも高い分解能でインデックスを表現でき、数値と比較してオーバーフローやインデックスの衝突を先延ばしにできます。

 type UserImage struct {
   ID     int
   UserID int
-  Index  int
+  Index  string
   Path   string
 }

 type UserImages []UserImage

 func (e *UserImages) Sort() {
   sort.Slice(e, func(i, j int) bool {
     return e[i].Index < e[j].Index
   })
 }

　var userImages = UserImages{
+ {ID: 1, UserID: 200, Index: "45", Path: "image1.png"},
+ {ID: 2, UserID: 200, Index: "4", Path: "image2.png"},
+ {ID: 3, UserID: 200, Index: "5", Path: "image3.png"},
+ {ID: 4, UserID: 200, Index: "6", Path: "image4.png"},
+ {ID: 5, UserID: 200, Index: "7", Path: "image5.png"},
　}

一方、文字列で保存した場合には数値に変換せずに平均値を求める必要があります。

また、並び替えを何度も繰り返した場合には上限超過によって丸められ、衝突が発生します。

衝突した場合、インデックスを再度振り直す必要があり、これをリバランシングと呼びます。

データレンジが広がるとリバランシングの頻度は低くなります。

リバランシングはコストの高い処理になるため、リバランシングの頻度を抑えるべく、文字列をソートキーにしてみます。

2.3.2. 文字列をソートキーにする

例えば16進数を採用してみると10進数の時と比べて、一桁あたり6通り増えることになり、その分データレンジが広がりました

Figmaで採用されたのはbase95ですが、base95を採用すると10進数と比較して一桁あたり85通り増えることになり、その分データレンジが広がることになります。

もちろんbase95にエンコードする前のバイナリのまま保存することもできますが、Databaseのカラム制限やデバッグ時の可読性がトレードオフになります。

また、クライアントにソートキーをインデックスをそのまま使用して返す場合、printable ascii以外を含むbase95以上を採用するとクライアント側に何らかの不具合が起きてしまうことも考えられます。

3. Fractional indexを採用したAPI

次にFractional indexを採用した場合のAPIのインターフェースを考えてみます。

Requestには更新対象のIDと前後のIDを受け取ります。
PrevIDがnullの時は先頭、NextIDがnullの時は末尾に追加します。

type ReorderRequest struct {
  UserImageID int  `json:"user_image_id"`
  PrevID      *int `json:"prev_id"`
  NextID      *int `json:"next_id"`
}

a, b, c, dのIDをそれぞれ1, 2, 3, 4とするとき、下記のようなRequestで表現できます。

curl -XPUT 'https://api/images/reoder' \
-d "{\"user_image_id\": 1, \"prev_id\": 2, \"next_id\": 3}"

このように全ての並び順をペイロードに必要としないため、Request時のデータ量を削減できます。

内部では、PrevID, NextIDそれぞれのインデックスを取得して更新対象の新しいインデックスを文字列のまま計算します。

衝突した場合のみ、リバランシングが必要になりますが、ほとんどの場合はリバランシングが必要なく、1要素のみを更新するためとても効率的です。

また、下記例では同期的にリバランシングを行っていますが、予めリバランシングが必要な場合を検知し、非同期処理に逃すことで負荷を軽減することもできます。

func Reorder(ctx context.Context, userID int, req ReorderRequest) error {
  // 先頭に移動する場合は予め決めた最小値とreq.NextIDの平均値を計算する
  if req.BringTop() {
    return bringTop(ctx, userID, req)
  }
  // 末尾に移動する場合は予め決めた最大値とreq.PrevIDの平均値を計算する
  if req.BringBottom() {
    return bringBottom(ctx, userID, req)
  }
  images, err := repository.GetByIDs(ctx, userID, []int{req.UserImageID, req.PrevID, req.NextID})
  if err != nil {
    return err
  }
  // 紐づく画像が存在しない場合.
  if len(images) != 3 {
    return errors.New("not found")
  }
  imageMap := images.ToIDMap()
  midIndex := image.CalculateMidpoint(imageMap[req.PrevID], imageMap[req.NextID])
  // 衝突していた場合は全対象にインデックスを再割り当てするリバランスを行う.
  if midIndex == imageMap[req.PrevID].Index ||
    midIndex == imageMap[req.NextID].Index {
    return rebalance(ctx, userID)
  }
  imageMap[req.UserImageID].Index = midIndex
  return repository.Update(ctx, imageMap[req.UserImageID])
}

// package image
func CalculateMidpoint(prevIndex, nextIndex string) string {
  next := []byte(nextIndex)
  prev := make([]byte, len(next))
  // 文字列操作のためにnextの長さに合わせる
  for i, j := len(prevIndex)-1, len(next)-1; i >= 0; i-- {
    prev[j] = prevIndex[i]
    j--
  }
  return add(divideByTwo(prev), divideByTwo(next))
}

まとめ

本記事では、並び替えAPIとデータ構造にFractional indexingを採用することでデータ更新を最小限にできることがわかりました。

まだまだ導入事例が少ないFractional indexingですが、アプリケーションの属性とリバランシングの頻度を考えることで、並び替えのユースケースに最適なデータ構造とAPIのインターフェースを決めることができそうです。

サンプル実装のリポジトリが公開できるようになったら改めてシェアしたいと思います。

References