MoTLab -GO Inc. Engineering Blog-MoTLab -GO Inc. Engineering Blog-

カーソルページネーションを実装した話

バックオフィス
May 31, 2023

バックオフィス基盤第2グループの名嘉眞です。私の担当しているプロダクトにカーソルページネーションを実装したので、その経緯と実装内容を記事にしたいと思います。これからカーソルページネーションを実装しようとしている方の参考になれば幸いです。

カーソルページネーションを実装したきっかけ

カーソルページネーションを実装したきっかけは、1ユースケースでデータ量が大きくなるAPIを追加する必要があったためです。 具体的にいうとある特定の種別の決済情報を蓄積しているマイクロサービスがあり、そのマイクロサービスを利用する管理画面のサービスが存在していて、管理画面でその特定の決済情報を表示したり、CSVダウンロードしたいという機能追加がありました。サービス間の通信はgRPCです。 この要件だけだとオフセットページネーションでも良さそうなのですが、以下のような課題がありました。 ※オフセットページネーションとは: 1ページあたりのオブジェクト数とページ番号をもとにSQLのLIMITとOFFSET句を使ってページネーションを行う方法で以下のようなSQLとなります。

SELECT id, name FROM books LIMIT :1ページあたりのオブジェクト数 OFFSET :ページ番号

課題点

  • 決済情報は常に追加され続けていて、管理画面は利用者の任意のタイミングで利用される。そのため利用中に新しい決済情報が追加されるとページがズレる可能性がある。特にCSVダウンロード時に複数ページの決済情報を取得する場合で発生すると問題になる可能性がある。

管理画面では決済日時の降順で決済情報を扱っています。ページ番号を指定するオフセットページネーションだと、新しい決済情報が追加されるとそのページの最後の決済が次のページで表示されるようになります。 CSVダウンロード時に連続して決済情報を取得している途中で決済情報が追加されると、決済情報を重複して取得してしまう可能性があります。 ※ちなみにこれ以上新しいオブジェクトが増えない取得範囲を指定して実行してもらう分にはページがズレる問題にならない(例: 過去の日時で範囲指定して取得するなど)

オフセットページネーションだと利用者の使用方法やタイミングによっては期待した挙動にならない可能性があると考え別の方法がないか検討しました。 この時点でカーソルページネーションは頭にありましたが、マイクロサービス間の通信ではgRPCを採用していることもあり、gRPCの Server streaming はどうかと考えました。 ※ 明確にstreamを推奨とは記載ないですが大きいデータを扱うことについてドキュメントにも記載があります。 protobuf 巨大データの扱いついて

unaryでは4MBのレスポンス容量制限を超過する可能性があるため難しいですが、streamingであればCSVダウンロード時の決済情報の重複は発生しないように実装できるので良さそうと思いました。 しかしSREチームのレビューで以下のようなコメントがありました。

streamを使うとAPIリクエストでサーバが固定されてしまって負荷分散できない

例 サーバがa,b,c と3つ存在、10万レコードを取得したい時:
- ページネーションの場合、例えば1万件を取得する10リクエストに分けるため、 
a/b/cそれぞれ 3 ~ 4 リクエスト（3~4万レコード分)を処理すれば良い

- streamの場合、a podが10万レコード分を処理しないといけない --> aの負荷が高くて、bとcが暇

grpc streamの場合どうしてもそうなっていてある意味しょうがいないですが、
場合によっては問題になる可能性があるのでシンプルなunaryでいけるならそのほうが良い

このコメントを受けて、なるほどたしかに。。と思いstreamingは採用しませんでした。 gRPCで大量のデータを扱う場合の手法でstreamingは、上位の選択肢になると考えていましたが負荷分散を考えると微妙な点もあると学びになりました。

上記のような流れを経てカーソルページネーションを採用することにしました。

カーソルページネーションとは

カーソルページネーションについては多くの記事があるのでここでは簡単に記載します。 公式なドキュメントでは RelayのCursor Connections が有名です。 データ量が多い場合や、Twitterのタイムラインのような機能(無限スクロール)などで使われます。 RelayはGraphQLのライブラリですが、カーソルページネーションはGraphQL以外でも実装できます。 またカーソルページネーションと明記されているわけではないですが、 Google API設計ガイドのリストのページ分割のドキュメント に記載されている内容はそのままカーソルページネーションAPIの参考になります。

以下は Google API設計ガイドのリストのページ分割のドキュメント に記載の例です。

rpc ListBooks(ListBooksRequest) returns (ListBooksResponse);

message ListBooksRequest {
  string parent = 1;
  int32 page_size = 2;
  string page_token = 3;
}

message ListBooksResponse {
  repeated Book books = 1;
  string next_page_token = 2;
}

オフセットページネーションと違いは以下のようになります。

  • リクエストパラメータに page_token(カーソル) を設定する
  • レスポンスに next_page_token を設定する(必要であれば prev_page_token のような前ページへのカーソルも)

カーソルとは、 このカーソルに対応するオブジェクト(レコード)より前または後 という条件となるパラメータです。 つまりカーソルは対象のオブジェクト全体でユニークになる順序性のあるものになる必要があります。 連番のIDなどでも要件を満たすことができますが、IDなど対象のカラムをそのままカーソルとするのではなく、エンコードしたトークンとしてやり取りすることが推奨されています。

カーソルページネーションの全体的な流れが以下のようになります。

  1. 初回リクエストはpage_token なしのリクエストが行われ、サーバは指定された数+1のオブジェクトのリストを取得する。レスポンスするオブジェクトはリクエストパラメータで指定されたサイズ分を含めて、カーソルをnext_page_token に設定してレスポンス
  2. クライアント側は次のページを取得するリクエストの際、初回リクエストのレスポンスに設定されていたnext_page_tokenをpage_tokenに設定する。サーバはpage_tokenに設定されたカーソルをもとにSQLの条件を組み立てオブジェクトのリストを取得しレスポンスする

サーバが先頭から指定された数+1取得する理由としては、次のページに入るレコードが存在するか判定するためでして、そのレコードがカーソルとなります。

次のページをリクエストした際のSQLとしては以下のようになります。

SELECT id, name FROM books WHERE id >= :カーソル LIMIT :1ページあたりのオブジェクト数

オフセットページネーションでは、SQLの対象となるレコード数が多いとページの後半になるにつれて効率が悪くなります。SQLのOFFSET句に設定する値が大きくなるとSQLが参照するレコード数もその分多くなるためです。 カーソルページネーションでは、指定したカーソルで絞り込むことができるため効率は悪くなりづらいです。(カーソルの対象となるカラムにindexが必要)

具体的なの実装について

カーソルページネーションの仕組みとしては上記のような流れになりますが、実際のユースケースに対応した実装についても記載します。 例えば以下のような要件がありました。

  • 決済日時の降順でレスポンスする必要がある
  • 前ページへの対応

以下は実装例です。実際の実装とは異なるのと、詳細な処理は割愛しているためそのままでは実行できないですが、大まかな処理の流れが伝わればと思います。

// 検索結果
type Payment struct {
    ID uint64
    StoreID string
    SettlementAt time.Time
    Price int64
}

// ページネーション情報
type Page struct {
    PageSize int
    NextPageToken string
    PrevPageToken string
}

func (r *repository) SearchPayments(ctx context, page Page) ([]*Payment, Page, error) {
    if page.NextPageToken != "" && page.PrevPageToken != "" {
        return nil, Page{}, errors.New("nextとprevのtokenが両方設定されることはNG")
    }

    // page_size+1取得する。+1分がカーソル対象の決済となる
    limit = page.PageSize + 1

    args := map[string]interface{}{
        "limit": limit,
    }

    // tokenが指定されていない最初のページのリクエストの場合は以下のようなSQLを発行する
    query := "SELECT id, store_id, settlement_at, price FROM prices ORDER BY settlement_ad, id DESC LIMIT :limit"

    // 次のページ(1ページ分古い決済)のリクエストの場合は以下のようなSQLを発行する
    if page.NextPageToken != "" {
        query = "SELECT id, store_id, settlement_at, price FROM prices WHERE (settlement_at, id) <= (:settlement_at, :id) ORDER BY settlement_ad, id DESC LIMIT :limit"

        settlementAt, id := parseToken(page.NextPageToken)
        args["settlementAt"] = settlementAt
        args["id"] = id
    }

    // 前のページ(1ページ分新しい決済)のリクエストの場合は以下のようなSQLを発行する
    if page.PrevPageToken != "" {
        subQuery := "SELECT id, store_id, settlement_at, price FROM prices WHERE (settlement_at, id) >= (:settlement_at, :id) ORDER BY settlement_ad, id ASC LIMIT :limit"

        query = fmt.Sprintf("SELECT id, store_id, settlement_at, price FROM %s ORDER BY settlement_ad, id DESC LIMIT :limit", subQuery)

        settlementAt, id := parseToken(page.PrevPageToken)
        args["settlementAt"] = settlementAt
        args["id"] = id
    }

    payments := []*Payment{}

    // SQLの実行
    if err := r.Select(ctx, &payments, query, args...); err != nil {
        return err
    }

    // SQLでpageSize+1取得しているので実際にレスポンスしたいレコード数に合わせることと
　　　　　　　　// tokenの生成を行う
    return newPaymentsPerPageToken(payments, page)
}

func newPaymentsPerPageToken(ps []*Payment, page Page) ([]*Payment, Page, error) {
  // 実装は割愛しますが、カーソルとなるレコードの決済日時と内部IDをもとにtokenの生成を行う
  // 取得結果がリクエストされたpageSizeより多い場合次(または前)のページが存在する
  // ページが存在する場合tokenの生成が必要でになる
  // この時リクエストでnextとprevのどちらが指定されたリクエストなのかで生成するパターンが変わる
}

記事の冒頭にも記載しているように決済情報のリストを扱うということもあり、決済日時の降順でレスポンスする必要がありました。 そのためORDER BYでは決済日時と内部IDを指定するようにし、カーソルとなるtokenを生成する箇所は、対象の決済の決済日時と内部IDでtokenを生成するようにしました。そして次のページを取得するリクエストで実行するSQLでも決済日時と内部IDを条件に絞り込みました。

また前ページの場合は少し複雑で、最終的に決済日時の降順にする必要があるため、前ページの検索では一度決済日時と内部IDの昇順でカーソルとなるレコード分取得した後、決済日時とIDの降順に直す必要がありました。

tokenを生成する仕組みは例では割愛しておりますが社内でライブラリ化されており、内部的にはencoding/gob packageを使用しています。

最後に

カーソルページネーションの方がオフセットページネーションに比べて、レコード数が増えても効率が良いのですが、実装は少し複雑になります。

またUIでページ番号を表示したい場合は、カーソルページネーションだとページ番号を指定した検索が出来ず採用が難しいです。

カーソルページネーションを採用した経緯と実装例の紹介は以上です。誰かの参考になれば嬉しいです。

We're Hiring!

📢
GO株式会社ではともに働くエンジニアを募集しています。

興味のある方は 採用ページ も見ていただけると嬉しいです。

Twitter @goinc_techtalk のフォローもよろしくお願いします！