Redisのハッシュスロットについて誰も教えてくれなかったのはなぜか?
Why didn't anybody tell me about Redis hash slots? (blog.verygoodsoftwarenotvirus.dev)
要約
ギグエコノミーのデリバリーアプリで、配車決定に関わるサービスでパフォーマンス問題が発生しました。大量のルート見積もりリクエストを効率的にキャッシュするために、Redisのハッシュスロットとハッシュタグの概念を理解する必要がありました。キーが異なるスロットに分散される問題に対し、ハッシュタグを使用してキーを特定のノードに集約することで、MGET/MSETコマンドの効率を劇的に改善し、レイテンシを削減しました。
全文翻訳
Redisのハッシュスロットについて、なぜ誰も教えてくれなかったのか?
私は、ギグエコノミーの配達アプリで、どの配達員にあなたの配達をオファーするかを決定するサービスを担当しています。アプリを開いて何かを配達してもらうよう依頼すると、どこかのコードがどの配達員にその仕事をオファーすべきかを決定しなければなりません。そのオファーを行うのが私たちのチームです。
決定要因となる無数のパラメータについて話すことは許されていませんが、外部から比較的容易に推測できる明白な要因の一つに距離があります。適切なマッチングを行うためには、全員がどれくらい離れているのかを知る必要があります。直線距離では、橋のない川を渡るのに10分かかることがわかります。そのため、私たちはルーティングエンジンに依存しており、それが私たちのレイテンシの最大の要因です。私たちは非常に具体的なレイテンシ目標を遵守しなければなりません。基本的に、常に一定時間内にバケットを空にしようとしており、バケットが溢れると、全員が濡れてしまいます。
念のため申し上げておきますが、仕事で使っている具体的な数値や用語について話すことは許可されていません。サービスが劇的に高速化したと言うことはできますが、例えば600msから100msになったと言うことはできません。
問題の形状
忙しいエリアでは、単一の作業割り当てパスを通過するために膨大な量のルート推定値が必要であり、ビジネスが実行されている間は継続的にそれらが再び必要になります。この規模に対処することは常に懸念事項です。
これらの推定値の有用な点は、それらが頻繁に繰り返し計算されることです。私の3軒隣の人が食料品店に行くのにかかる時間と私がかかる時間には、意味のある差はありません。また、私たちどちらも、その食料品店に行くのと、その駐車場にあるガソリンスタンドに行くのとで、運転時間に違いを言うことはできません。一方、レストランは全く動きません。1ブロック離れた2人の配達員は、ほぼ同一のルートリクエストを2つ生成し、30秒後には、2つの新しい位置から、さらに2つのリクエストを生成します。
ルーティングエンジンとの間にキャッシュレイヤーがない場合、必然的に作業が重複し、数分間にわたって定期的に機能的に同じ距離を再計算することになります。
プロセスローカルキャッシュもここでは機能しません。推定値を計算するプロセスは、次にそれを必要とするプロセスとは異なることが多いため、キャッシュは共有される必要があります。
素朴なアプローチ
生の座標でのキャッシュは現実的ではありません。座標を重複排除するには、H3を使用する必要があります。H3は世界を異なるサイズの六角形に分割し、与えられた座標ペアから六角形のIDを取得できるようにします。
解像度はレバーです。六角形サイズが広すぎるとヒット率が高くなり、推定精度が低下します。小さすぎると、実質的に一方の座標識別子をもう一方に置き換えることになります。
したがって、キーは <origin hex>:<dest hex>:<resolution>、値は推定値、書き込みパスは MSET でした。簡単ですよね?
そうは問屋が卸さない
私たちはRedis クラスターを使用しており、クラスターはキーとその値を均等に分散する必要があります。
Redisは16,384個のハッシュスロットを作成し、それらをクラスターのノードに分散します。MSET や MGET のような複数のキーを扱うコマンドは、すべてのキーが同じスロットに入る場合にのみ有効です。
私はトレースを見てこれを学びました。単一の読み取りが、単一キーごとの多数の個別の MGET スパンとして表示されていました。そして、これはOtelコレクターが関連するスパンの多くをほぼ確実にドロップしていたことを考慮しています。私たちの最大読み取りレイテンシメトリックは、予想される最悪ケースよりもはるかに高くなっていました。こうして私はスロットが存在することを知りました。
スロット化する
キーがどのスロットに入るかは、Redisが CRC16(key) mod 16384 を実行することで決定されます。1文字だけ異なる2つのキーは、互いに関連性のないスロットに入るため、バッチ処理にとっては壊滅的です。私のキーはそれぞれユニークな16進数IDのペアを持っており、そのため実質的に同じスロットに入ることはありませんでした。
マルチキーコマンドは1つのスロットしかアドレス指定できないため、適切に構築されたクライアントは、大量のキーの単一の MGET を受け取り、各キーが属するスロットごとにグループ化し、各グループを個別のワイヤーに載せます。私が渡したものでは、それが正しい処理でした。修正は、それほど多くの異なるスロットに存在しないキーを渡すことです。書き込みパスも同様の問題を抱えていました。
#ハッシュタグ
Redisにはこれにまさに対応する「エスケープハッチ」があり、ハッシュタグと呼ばれます。キーに中括弧 {} で囲まれたテキストチャンクが含まれている場合、Redisはその中括弧内のテキストのみをハッシュし、キーの残りの部分は無視します。これにより、キーを特定のスロットに強制的に配置するレバーが得られます。
graph LR
client_process["client process"]
primary1["primary 1"]
primary2["primary 2"]
primary3["primary 3"]
subgraph Redis Cluster
primary1
primary2
primary3
end
client_process --> primary1
client_process --> primary2
client_process --> primary3
subgraph Slots
slot01[#01]
slot02[#02]
slot03[#03]
slot04[#04]
slot05[#05]
slot06[#06]
slot07[#07]
slot08[#08]
slot09[#09]
slot10[#10]
slot11[#11]
slot12[#12]
end
primary1 --- slot01
primary1 --- slot02
primary1 --- slot03
primary2 --- slot04
primary2 --- slot05
primary2 --- slot06
primary3 --- slot07
primary3 --- slot08
primary3 --- slot09
primary1 --- slot10
primary1 --- slot11
primary1 --- slot12
1/4 · キーのバッチ、まだプロセス 0 ラウンドトリップ
89283082a53ffff:892830828efffff:9
12個のルートキー、3つのプライマリ。全体をハッシュすると、各キーは独自の Слот に入り、1つの MGET は12回のラウンドトリップに変わります。共有タグを中括弧で囲むと、中括弧だけがハッシュされるため、同じ12個のキーは3つの Слот に収束します:3回のラウンドトリップ、ノードごとに1回、同時に実行されます。
中括弧に何を入れるかが重要です。私はビットコインを所有したことはありませんが、この問題はビットコインブロックチェーンがブロックに無意味な数字を入れてエンドハッシュが特定のプロパティに一致するようにする方法を思い出させました。ここでは、はるかに単純な出力ハッシュの要件で、基本的にそれが必要でした。
私は整数を選択し、ブロックチェーンマイナーのように総当たりで見つけました。タグは実際にはテンプレートのようなもので、{routing:v1:<n>} のようなものです。起動時にゼロから反復し、毎回タグ全体のハッシュをチェックして、どのスロットに入るかを確認します。必要な数だけ各ノードが持つまでこれを行います。
タグがその仕事をするようになると、数千のキーのバッチは、正確に1つのノードを対象とする少数の合法的なマルチキーコマンドに分割できます。
graph LR
subgraph Redis Cluster
primary1["primary 1"]
primary2["primary 2"]
primary3["primary 3"]
primary4["primary 4"]
primary5["primary 5"]
primary6["primary 6"]
end
subgraph Slots
slot0[slot 0]
slot16383[16383]
slot3276[3276]
slot6553[6553]
slot9830[9830]
slot13107[13107]
end
subgraph Tag Assignment
primary1 -- 0-3276 --> slot0
primary2 -- 3277-6553 --> slot3276
primary3 -- 6554-9830 --> slot6553
primary4 -- 9831-13107 --> slot9830
primary5 -- 13108-16383 --> slot13107
primary6 -- 5 tags per primary 4 --> primary1
primary6 -- n = 0, 1, 2, … until every primary has 4 --> primary2
primary6 -- --> primary3
primary6 -- --> primary4
primary6 -- --> primary5
end
subgraph Walk Results
walk_results[0/28 tried · 0 skipped **0** of 20 kept]
end
タグテンプレートは routing:v1:%d です。各整数はRedisがハッシュするのと同じ方法でハッシュされ、そのスロットを所有するプライマリに配置されます。そのプライマリにまだ空きがあれば、整数は保持されます。そうでなければ破棄され、ウォークは続行されます。5つのプライマリがそれぞれ4つずつ持つ場合、28個の整数が必要で、そのうち8個はすでに満杯のスロットに配置されます。何も保存されていません。同じウォークを同じクラスターに対して実行するすべてのプロセスは、同じリストを取得します。
ファンアウトする前にキーをソートする
各Redisノードは単一スレッドでコマンドを実行するため、同じノードに向けられた20件の同時リクエストは実質的にキューになります。ファンアウトを収束させることで、実行する必要のある MGET リクエストの数は減りましたが、特定のノードにそれらをスパムするのを防ぐことはできませんでした。
graph TD
subgraph Chunks
chunk1[keys per chunk 4]
cmd1[1. 3 commands]
cmd2[2. 3 commands]
cmd3[3. 3 commands]
cmd4[4. 2 commands]
cmd5[5. 2 commands]
cmd6[6. 3 commands]
end
subgraph Primary Nodes
primary1["primary 1"]
primary2["primary 2"]
primary3["primary 3"]
end
subgraph Command Times
command_times[command times · 16 commands **0.0** to finish]
end
chunk1 --> cmd1
chunk1 --> cmd2
chunk1 --> cmd3
chunk1 --> cmd4
chunk1 --> cmd5
chunk1 --> cmd6
cmd1 --> primary1
cmd2 --> primary2
cmd3 --> primary3
cmd4 --> primary1
cmd5 --> primary2
cmd6 --> primary3
primary1 --> command_times
primary2 --> command_times
primary3 --> command_times
24個のタグ付けされたキー、3つのスロット、3つのプライマリ、各コマンドはそれが何を運んでいても同じラウンドトリップコストがかかります。リストをチャンクに分割すると、各チャンクは複数のスロットのキーを保持するため、クライアントはそれを分割し、各プライマリはチャンクごとに1つのコマンドを受け取り、次々と実行します。スロットごとにグループ化すると、プライマリごとに1つのコマンドになり、すべてが同時にインフライトになります。チャンクサイズは全体のダイヤルであり、間違った方向に実行されます。細かくカットするほどコマンド数は増え、より多くのゴルーチンにファンアウトすることが読み取りを遅くする理由です。
チャンクが宛先で整理されていない場合、複数のチャンクが同時に同じノードをターゲットにし、そのノードは他のノードがアイドル状態の間、それらを順番に処理します。そのため、ワイヤーに何も送信する前に、ローカルですべてのキーのスロットを計算し、それによってグループ化します。次に、ファンアウトはノードごとになり、各リクエストは有用な作業を行います。
MSET は有効期限を扱わない
キャッシュされたルート推定値には有効期限が必要です。MSET には有効期限引数がありません。
通常の回避策は、キーごとに SET ... EX をパイプライン化することですが、これは1つのコマンドを数千に増やします。または、MSET を実行してから2番目のパスで EXPIRE を実行することもできます。これはコマンドを倍増させ、さらに、2つのパスの間にクラッシュが発生した場合、キャッシュにキーが永久に残ってしまうウィンドウを残します。
答えは、代わりにRedisにスクリプトを実行させることになりました。EVAL を使用します。
JSON は無料ではない
最後の点は、後から考えると恥ずかしいです。キャッシュされた値はJSONとして始まりました。いつもそうしてきたからです。ペイロードは小さいので、それほど影響はないだろうと思っていました。私たちの規模では、貴重なCPU時間を浪費していました。値をカンマ区切り値(CSV)に切り替えたところ、劇的に改善しました。
では、ここで何を学んだのか?
この試みで私が学んだすべては、予測していなかった方法で前のステップが失敗した理由を解明することによって必要とされました。
Goの熱狂的なファンとして、私は自然にRob Pikeに敬意を払っており、特に彼のプログラミングの5つのルールを尊敬しています。最近、これらのルールについてよく考えています。
ルール2。測定せよ。測定するまで速度チューニングをするな。そして、コードの一部分が他を圧倒しない限り、それをするな。
ルール3。n が小さい場合、派手なアルゴリズムは遅い。そしてn は通常小さい。n が頻繁に大きくなることがわかっているまで、派手にするな。
ルーティングサービスとのやり取りが私たちの最大のボトルネックであることを測定し、Redisとのインターフェースのためのシンプルなアルゴリズムアプローチが私の「ハックルベリー」になると考えました。n が私たちにとって常に大きいことを認識するのを怠り、私が予想していたよりも派手なアルゴリズムが必要でした。
上記で説明したスループットの問題に初めて遭遇したとき、一歩下がってベンチマークハーネスをいくつか書くことにしました。レバーをオンオフして結果のスループットを測定できるおもちゃのアプリです。それらのハーネスは、本番環境に導入する前に各アプローチを検証し、ますます複雑になるコードでどのようなパフォーマンスを購入しているかについて正直な答えを与える能力を与えてくれました。
後から考えると、最初にベンチマークハーネスを構築すべきでした。私はこの業界で主に初期のスタートアップで経験を積んできましたが、そこでは「今すぐ出荷して後で修正する」のがデフォルトです。ベンチマークはハーネスを意味し、ハーネスは本番環境に似た入力を発明することを意味し、それらすべては関心のない聴衆に2ポイントのチケットが5になったことを説明することを意味しました。
プログラミングのポスト・クロード時代では、そのようなベンチマークハーネスは仕様を提供して10分待つだけで済むため、これはもはや許容されないと思います。私は、まず広範なベンチマークハーネスを構築することから新しい取り組みを開始しており、それは私にとって非常にうまくいっているので、習慣にしようとしています。