こんにちは！YOUTRUSTでエンジニアをやっているやまでぃ（YOUTRUST/Twitter)です！
外は春の陽気が心地よく、部屋の中もそよ風が吹き抜けていてとても気持ちが良いです。
最近のYOUTRUST社の話なのですが、先日3年振りに全社合宿を湯河原で行いました。
現地集合現地解散とのことだったので、折角なので僕は家から片道90km6時間の道のりを自転車で往復しました。普段はオンラインで直接顔を見合わせない人達とも交流が持ててとても有意義な時間でした。
さて今回の本記事ではスケーラブルなリスト取得ロジックについて書いていきます。
タイムラインの投稿やユーザー検索等、Webサービスでは何かとリソースのリストを取得する処理がありますよね。
「リスト取得なんて持ってくるだけじゃん？簡単じゃん？」かと思いきや、実はちゃんと気をつけて設計しておかないと、サービスの成長と共に重くなってしまいユーザー体験を著しく損ねてしまいます。
結構奥が深いリスト取得の話を少しだけ深ぼってみます。
Too long, don't read.
YOUTRUSTはパフォーマンスを気にしてリスト取得のロジックを色々工夫して頑張っているよ、という話です。
もっとこうした方が良いんじゃない？等ございましたら こちら からこっそり教えてください。
ソートとフィルターって大変だよね
何かしらのリソースのリストを取得する際にはソートとフィルター処理がよく要件として求められます。
- ソート（並び替える）
- 例. ABCDE→ACEDB
- フィルター（絞り込んで数を減らす）
- 例. ABCDE→ACD
例えば、タイムラインの投稿リソースの場合、投稿日時順にソートされているだろうし、自分がフォローしているユーザーの投稿に絞り込みが行われていることでしょう。
さて、このソートとフィルター機能を実現しつつ、どのようにリスト取得を行っていくかを考えていきます。
実現方法その1. 全件取得
まず最初に思い付くシンプルなものは、クライアントの要求する条件を満たすものを全て取得して全部返すやり方でしょう。実にシンプル。
サービスのリリースからしばらくの間はこの実装で問題ないと思います。
ですが、サービスの成長と共にこの方法は限界を迎えます…
- リソース数の増加に伴い、ソートに時間がかかるようになる。
- リソース数の増加に伴い、フィルターに時間がかかるようになる。
- リソース数の増加に伴い、APIレスポンスサイズが大きくなり、通信時間が長くなる。
- リソース数の増加に伴い、クライアント側でのレンダリング等に時間がかかる。
つまりユーザーさんからみたらサービスが「重くなる」のです。これは良くない。
「重いから」というマイナスな体験が先行してしまい、サービス本来の価値を知ってもらう前にブラウザのタブやアプリをそっ閉じして去っていってしまうかもしれない。まずい。
改善しよう改善しよう。
実現方法その2. 分割取得
条件を満たすリソースを「全件返すから」重くなるんだ！…ということで分割して返すことを思いつきます。所謂ページング処理です。
サーバーはクライアントからリクエストを受け取ったら条件を満たすリソースを全部返すのではなく、まず最初は1ページ目に含まれる分だけを取得して返します。
そして、もしユーザーさんがUAの画面をスクロール等して2ページ目を要求してきたら、その時に必要な分だけをまた取得して返します。
もしかしたらユーザーさんは2ページ目を要求せずに別の画面に遷移しちゃうかもしれないですしね。必要な分だけ返しましょう。全く無駄がないですね、素晴らしい。
…ですが、この分割取得方式を導入するとまた別の問題が発生します。
そう、リソースの「重複や欠損」問題です。
各ページの取得タイミングによってはソートやフィルター処理が参照する変数の値が変わり得て、ページ間でリソースの重複や欠損が発生してしまう可能性があります。
具体例でいうと下記のような感じです。
- 時間 T1
- この時点での実際のリソースの並び（A, B, C, D, E, F, G）
- 1ページ目（1〜3件目）→（A, B, C）
- 時間 T2
- この時点での実際のリソースの並び（A, C, D, B, E, F, G）
- T1から時間が経過しており、並びが同一である保証が無い。
- 2ページ目（4〜6件目）→（B, E, F）
- またBが返っている（重複）。Dが1ページ目の位置に移動していて取得できなくなっている（欠損）。
- この時点での実際のリソースの並び（A, C, D, B, E, F, G）
重複や欠損が発生する確率はまぁまぁ低いと見積もって「たまに重複や欠損がでちゃうかもだけど許容する！何も対処しない！」という選択肢を取るのも勿論ありだと思います。サービスの性質を考慮して判断すると良いと思います。
我々YOUTRUSTの場合は、確率が低そうとはいえ、システム側の都合でユーザーさんが不利益を被る（例えばユーザー検索結果に出てこなくてスカウトをもらう機会を逃してしまう等）のは許容しないと判断したので、この問題に真正面から向き合っています。
次にこの問題に対してYOUTRUSTがどう対処しているのかについて説明します。
リスト内リソースの重複・欠損を防ぐ対処法
結論から言うと「最初の1ページ目の取得時に2ページ目以降も全部計算しちゃってるよ！」です。
1ページ目の取得リクエストの処理時に、2ページ目以降のソートとフィルターも全部計算してそのIDだけを返します。（IDのサイズはリソース本体と比べて十分小さいので、全件返すことをサイズ的に許容できます）
この方法だと1ページ目の取得時に2ページ目以降のリソースと並びが全て確定するので、重複や欠損が生じません。
また2ページ目以降の取得はID指定で行うので高速にもなります（ソートやフィルター処理が行われず、ただ指定されたIDのリソースを返すだけなので）。
これにて一件落着！…かと思いきや、もちろんそんな事はなくて、今度は「2ページ目以降のソートとフィルター処理」が重くなる（スケールしない）という問題が発生してきます。
この問題を解決するために、そのリストの性質に応じた対応策を取っています。
最近作成されたリソースが大事なリストの場合（タイムラインの投稿等）
ソートロジックが、大まかには定数である作成日時に依存していると言えるので、リソース全体を時間範囲でリソース群に区切って扱うことができます。（取得タイミングによって並びが変わらないので）
そして1ページ目の取得時には最新の時間範囲のリソース群のみを検索対象とすることで、サービスの成長に伴うレコード数の増加を一定数に抑え込んでいます。（つまり2ページ目以降のリソース数が一定数に落ち着くので、計算量が爆発しにくいということ）
ユーザーさんの画面スクロールが進むにつれ、範囲内のリソース群内のリソースが分割取得されます。
その範囲のリソースが全て取得し終わったら、次の時間範囲のリソース群を取り出し、またこれを分割取得していきます。（二段階に分割取得しています）
全リソースが検索対象なリストの場合（ユーザー検索等）
2ページ目以降のソート・フィルター処理を非同期化することによって計算時間を隠蔽しています。
1ページ目の計算が終わったらAPI自体はすぐレスポンスを返して、2ページ目以降の処理は非同期ジョブに投げます。
クライアント側で1ページ目がレンダリングされユーザーがリソースを閲覧している間に、非同期ジョブがゆっくりと2ページ目以降の計算を行います。
ジョブの計算が終わったらWebSocketによりサーバー側からクライアント側にデータをサーバープッシュします。
この方式により、2ページ目以降のソート・フィルター処理という計算時間を隠蔽しています。
※YOUTRUSTのユーザー検索対象の母集団は「リクルーターの2次友達の和集合」であり、フィルターには「意欲の閲覧判定（とても複雑）」が入るので、検索処理がとても重たい。今はなんとかなっているが、今後サービス成長につれてどこまで耐えられるものか…これをここまで読んでくださっているエンジニアの方、タスケテクダサイ…！
終わりだよ
以上がYOUTRUST上でのスケーラブルなリストを実現するための設計概要です。
また機会があれば、詳細で具体的な実装例と共に解説するかもしれません。
こんな文字ばっかりの記事を最後まで読んでくれてありがとうございます！（感謝）
そんなあなたに僕が以前住んでいた所の近くのラーメン屋の写真を置いておきますね。多分200〜300杯くらい食べたんじゃないかなぁ。
それではまた次回の記事をお楽しみにしてていただければと思います！あざました！
