私はギグエコノミーの配送プラットフォームで、注文をどの配達員に割り当てるかを決めるサービスを担当している。あなたがアプリを開き、配達を依頼すると、どこかのコードがその注文を誰に割り当てるべきか判断しなければならない。その割り当てを出しているのが我々だ。具体的な判断にどのパラメータが関わるかは明かせないが、かなり明白なパラメータが一つあり、内部を詳しく知らなくても外から推測できる。距離だ。マッチングをうまくやるには、それぞれがどれだけ離れているかを知る必要がある。直線距離では、橋のない川を渡るのに10分かかると言ってしまう。そこで我々は経路探索エンジンに頼っているが、これが我々自身のレイテンシの最大の要因であり、他の追随を許さない。守るべきレイテンシ目標は非常に明確だ。基本的に、決まった時間内にバケットを空にし続ける必要があり、バケットがあふれれば全員が被害を受ける。先に言っておくと、仕事で使っている具体的な数字や用語は明かせない。あるサービスが大幅に高速化したとは言えるが、600msから100msになったとは言えない、そういうことだ。

問題の形

ある繁忙地域では、1回の配車処理の中で大量の経路推定が必要になり、しかもビジネスが動いている限り、そうした推定を絶え間なく取得し続ける必要がある。この規模への対応は長期的な難題だ。これらの推定には便利な性質がある。しばしば重複するのだ。私の家から3軒先の人が食料品店に行くのにかかる時間は、私と比べて目立って多いわけでも少ないわけでもないし、その食料品店まで車で行くのと、その駐車場にあるガソリンスタンドまで車で行くのを、我々の誰も区別できない。レストランに至っては、そもそも動かない。1ブロック離れた2人の配達員は、ほぼ同一の経路リクエストを2つ生み出す。30秒後には、2つの新しい位置からまた2つ生まれる。我々と経路探索エンジンの間にキャッシュ層が一切なければ、同じ作業を繰り返すことになる。実質的に同一の距離を、一定のリズムで何分間も計算し続けるのだ。プロセス内キャッシュもここでは役に立たない。ある推定を計算するプロセスが、次にそれを必要とするプロセスであることはほとんどない。だからキャッシュは共有でなければならない。

素朴なやり方

生の座標をそのままキャッシュするのは全く通用しない。まず H3 で座標を重複排除する必要がある。H3は世界を大きさの異なる六角形に切り分け、座標のペアを与えればその六角形のIDを引ける。解像度は調整可能なレバーだ。六角形が大きすぎればヒット率は上がるが、推定は不正確になる。小さすぎれば、ある座標識別子を別の座標識別子に置き換えているだけだ。つまりkeyは::、valueは推定値で、書き込み経路はMSETになる。楽勝だ、そうだろう？

そう単純ではない

我々が使っているのはRedisのクラスタで、クラスタはkeyと対応するvalueを均等に分散させなければならない。Redisは16,384個のハッシュスロットを作り、それをクラスタ内の各ノードに割り当てる。MSETやMGETのように複数のkeyに関わるコマンドは、すべてのkeyが同じスロットに収まっている場合にのみ有効だ。これはtraceを見て初めて気づいた。1回の読み取りが、trace上ではそれぞれが単一keyに対応する数十個のMGET spanとして現れる。しかもこれは、Otel collectorが関連するspanの多くをほぼ確実にすでに捨てている状況での話だ。我々の最大読み取りレイテンシ指標は、想定していた最悪ケースをはるかに超えている。スロットというものの存在を、私はこうして知った。

スロットとは何か

あるkeyがどのスロットに入るかは、Redisが実行するCRC16(key) mod 16384によって決まる。1文字しか違わない2つのkeyが、全く無関係なスロットに落ちる。これはバッチ処理にとって致命的だ。私のkeyはどれも一対の一意な16進数IDを含んでいるので、実際には決して同じスロットに落ちない。複数keyのコマンドは1つのスロットしか対象にできない。だからよくできたクライアントは、大量のkeyを含むMGETを所属スロットごとにグループ分けし、各グループを個別の接続で送る。私が与えているものに関して言えば、その動作は正しい。解決策は、それほど多くの異なるスロットに散らばらないkeyを渡すことだ。書き込み経路にも同じ問題がある。

#ハッシュタグ

Redisはまさにこの状況のために裏口を用意している。hash tagだ。keyの中に波括弧で囲まれた部分があれば、Redisは波括弧内のテキストだけをハッシュし、keyの残りは無視する。これが、keyを指定したスロットに強制的に押し込むためのレバーになる。

クライアントプロセス

primary 1

primary 2

primary 3

#01

#02

#03

#04

#05

#06

#07

#08

#09

#10

#11

#12

1/4 · 一批のkey、まだ 0 回のラウンドトリップの途中

89283082a53ffff:892830828efffff:9

12 個のルーティングキー、3 つのプライマリノード。全体をハッシュ化すると、各キーがそれぞれ 1 スロットを占め、1 回の MGET が 12 回のラウンドトリップになる。共有タグを波括弧で囲み、波括弧の中身だけをハッシュ対象にすると、同じ 12 個のキーが 3 スロットに収束する。3 回のラウンドトリップ、各ノードに 1 回ずつ、同時に。

鍵となるのは波括弧の中に何を入れるかだ。私はビットコインを一度も持ったことがないが、この問題を考えていて、ビットコインブロックチェーンが意味のない数字をブロックに詰め込み、最終的なハッシュが特定の性質を満たすようにしていることを思い出した。ここで必要なのは本質的にこれと同じ仕組みで、出力ハッシュに課す条件はずっと単純だ。

私は整数を 1 つ選び、ブロックチェーンのマイナーのように総当たりで探し出した。タグは実際にはテンプレートで、おおよそ {routing:v1:} のような形をしている。起動時に 0 から順に試し、毎回タグ全体をハッシュ化して、どのスロットに落ちるかを調べる。各プライマリノードが必要な数を受け取るまで続ける。

タグが動き始めれば、数千個のキーのバッチを、少数の正当なマルチキーコマンドに分割できる。各コマンドは正確に 1 つのノードを指す。

n = 0, 1, 2, … 各プライマリノードが 4 つずつ受け取るまで 12345 スロット 0 16383

プライマリ 1 0–3276 プライマリ 2 3277–6553 プライマリ 3 6554–9830 プライマリ 4 9831–13107 プライマリ 5 13108–16383 試行済み 0/28 · スキップ 0 0 / 20 保持 anchors = [ ]

タグテンプレートは routing:v1:%d。各整数は Redis が実際に使うのと同じ方法でハッシュ化され、そのスロットを持つプライマリノードに割り当てられる。そのノードに空きがあれば整数は保持され、なければ捨てて次に進む。5 つのプライマリノードがそれぞれ 4 つ必要で、28 個の整数を要し、うち 8 個はすでに埋まった場所に落ちた。何も保存しない。同じクラスタに対して同じ走査を実行すれば、どのプロセスでも同じリストが得られる。

ファンアウトの前にキーをソートする

各 Redis ノードはシングルスレッドでコマンドを実行するので、20 個の並行リクエストが同じノードに届けば、実質的には順番待ちになる。収束ファンアウトは、送らなければならない MGET リクエストの数を減らすが、そのリクエストで特定のノードを叩き続けることまでは防げない。

3 コマンド
3 コマンド
3 コマンド
2 コマンド
2 コマンド
3 コマンド

primary 1 primary 2 primary 3 0123456 コマンド数 · 16 コマンド 0.0 完了

24 個のタグ付きキー、3 スロット、3 プライマリ。1 コマンドあたりのデータ量がどれだけ多くても、ラウンドトリップのコストは同じだ。リストをチャンクに切っても、各チャンクには複数のスロットに属するキーがまだ含まれるので、クライアントがそれを分割し、各プライマリがチャンクごとに 1 コマンドを受け取り、順に実行する。先にスロットでグループ化すれば、各プライマリのコマンドは 1 つだけになり、すべてが同時に飛ぶ。チャンクの大きさが唯一の調整つまみだが、その回り方は逆だ。細かく切るほどコマンドが増える。だからタスクをより多くの goroutine に分散させると、かえって読み取りが遅くなる。

チャンクが宛先ごとに整理されていなければ、そのうちのいくつかが同時に同じノードを指し、そのノードは 1 つずつしか実行できず、他のノードは遊んでいる。だからデータをネットワークに送る前に、各キーのスロットをローカルで計算し、スロットごとにグループ化する。こうしてファンアウトは任意のチャンクではなくノードに分散し、すべてのリクエストが有効な仕事をする。

MSET は有効期限をサポートしない

キャッシュしたルーティング推定値には有効期限が必要だが、MSET には期限の引数がない。

よくある回避策は、キーごとに SET ... EX をパイプラインで流すことだが、1 コマンドが数千コマンドになる。あるいは MSET してから 2 回目のパスで EXPIRE することもできるが、コマンド数が倍になり、しかも 2 つのパスの間に窓ができる。クラッシュするとキーがキャッシュに永久に残る。

最終的な答えは、EVAL に切り替えて Redis にスクリプトを実行させることだった。

JSON はタダではない

最後のこれは後から思うと恥ずかしい。キャッシュの値は最初 JSON だった。いつもそうしているからだ。データ量は小さく、この選択が大した影響を与えるとは思わなかった。しかし私たちの規模では、貴重な CPU 時間を食っていた。値をカンマ区切り形式に変えると、状況は大きく改善した。

では、何を学んだのか？

この件で学んだことはすべて、前のステップがなぜ予想外の形で失敗したのかを突き止めることから来ている。

Go の熱狂的なファンとして、私は当然 Rob Pike に敬意を抱いている。特に彼のプログラミングに関する 5 つのルールに。最近、このいくつかを繰り返し噛みしめている。

ルール 2。 まず計測せよ。計測する前に速度のためにチューニングするな。計測したとしても、ある部分のコードのコストが他すべてを圧倒していない限り、手を入れるな。ルール 3。 凝ったアルゴリズムは n が小さいとき遅く、そして n はたいてい小さい。凝ったアルゴリズムは定数項が大きい。n が頻繁に大きくなると確信するまで、凝ったことをするな。

私は計測し、ルーティングサービスとのやり取りが最大のボトルネックだと突き止めた。そして単純なアルゴリズムで Redis に接続するのが自分に合っていると思い込んだ。見落としていたのは、私たちにとって n は安定して大きく、仕事を成し遂げるには予想よりも凝ったアルゴリズムが必要だということだった。

上で述べたスループットの問題に最初に直面したとき、私は一歩引いてベンチマーク用の枠組みを書くことにした。さまざまなレバーを切り替え、それに応じたスループットを測れるおもちゃのアプリだ。この枠組みのおかげで、方案を本番に投入する前に一つずつ検証でき、このますます複雑になるコードが一体何を買っているのかを正直に答えられた。

後から思えば、まずベンチマークの枠組みを作るべきだった。この業界での自分の初期の経験は、ほとんどができたばかりのスタートアップでのものだ。そこでは、まずリリースして後から直すのが当たり前だった。ベンチマークとなれば枠組みを作ることになり、枠組みを作るとなれば本番に近い入力を用意することになり、そしてそれは、まったく関心のない人たちに、2ポイントのチケットがなぜ5ポイントになったのかを説明することを意味していた。

Claude 以降のコーディング時代では、そんなベンチマークの枠組みを作るのは仕様を書いて10分待つだけの話だ。これを言い訳に使うのはもう通用しないと思う。今は新しいプロジェクトを始めるとき、まずベンチマークの枠組みを一通り作り上げるようにしていて、効果は絶大なので、習慣にしようと努めている。