Redisのハッシュスロットについて誰も教えてくれなかったのはなぜか？

ギグエコノミーのデリバリーアプリで、あなたの配達をどの配達員にオファーするかを決定するサービスで働いています。アプリを開いて何かを届けてほしいと依頼すると、どこかのコードがどの配達員にその仕事をオファーすべきかを決定しなければなりません。私たちはそのオファーを行う人たちです。決定に至る無数のパラメータについては話せませんが、外部から知ることができるかなり明白なものの一つは距離です。良いマッチングをするためには、全員がどれだけ離れているかを知る必要があります。直線距離では、橋のない川を渡るのに10分かかると言われます。そのために、私たちはルーティングエンジンに依存しており、これは私たちのレイテンシの最大の貢献者です。私たちは非常に具体的なレイテンシターゲットを尊重する必要があります。私たちは基本的に常に一定の時間内にバケットを空にしようとしており、バケットがあふれると、全員が濡れます。念のためですが、具体的な数値や私たちが職場で使用する用語については話せません。サービスが劇的にスピードアップしたとは言えますが、例えば600msから100msになったとは言えません。 問題の形状 忙しい地域では、単一の作業割り当てパスを通過するために大量のルート見積もりが必要であり、ビジネスが実行されている限り、継続的にそれらが再び必要になります。これらの見積もりの便利な点は、それらが頻繁に繰り返されることです。私の3軒隣にいる人が食料品店に行くのにかかる時間と、私が食料品店に行くのにかかる時間には、意味のある差はありません。また、その駐車場にあるガソリンスタンドに行くのと、その食料品店に行くのとを区別することもできません。一方、レストランは全く動きません。1ブロック離れた2人の配達員は、2つのほぼ同一のルートリクエストを生成し、30秒後、2つの新しい位置から、さらに2つのリクエストを生成します。私たちとルーティングエンジンの間にキャッシュレイヤーがない場合、あなたは必然的に作業を重複させ、数分間、定期的な間隔で機能的に同じ距離を再計算することになります。プロセスローカルキャッシュもここでは機能しません。見積もりを計算するプロセスは、次にそれを必要とするプロセスとはめったに一致しないため、キャッシュは共有される必要があります。 素朴なアプローチ 生の座標でのキャッシュは、開始点になりません。座標を重複排除するためにH3を使用する必要があります。H3は世界を異なるサイズの六角形に分割し、与えられた座標ペアから六角形のIDを取得できるようにします。解像度はレバーです。六角形サイズが広すぎると、ヒット率が高くなり、見積もりの精度が低下します。六角形が小さすぎると、実質的に1つの座標識別子を別のものに置き換えます。したがって、キーは<origin hex>:<dest hex>:<resolution>であり、値は見積もりであり、書き込みパスはMSETでした。簡単でしょう？そうはうまくいきません。 スロット化 Redisクラスターを使用しており、クラスターはキーとその値を均等に分散する必要があります。Redisは16,384個のハッシュスロットを作成し、それらをクラスターのノードに配布します。MSETやMGETのような複数のキーを扱うコマンドは、すべてのキーが同じスロットに入る場合にのみ有効です。私はトレースを見てこれを学びました。単一の読み取りは、単一のキーごとの多数の個別のMGETスパンとして表示されていました。そして、Otelコレクターが関連するスパンの多くを確実にドロップしていたことを考慮してもです。私たちの最大読み取りレイテンシメトリックは、予想される最悪の場合よりもはるかに高かったです。これがスロットが存在することを知った方法です。 私にスロットを キーがどのスロットに入るかは、RedisがCRC16(key) mod 16384を実行することによって決定されます。1文字だけ異なる2つのキーは、互いに関連性のないスロットに入るため、バッチ処理には壊滅的です。私のキーにはそれぞれユニークなペアの六角形IDがあったため、それらは同じスロットに収まることはほとんどありませんでした。マルチキーコマンドは1つのスロットしかアドレス指定できないため、適切に構築されたクライアントは、多数のキーの単一のMGETを受け取り、それぞれが属するスロットごとにグループ化し、各グループを独自のワイヤーに配置します。私が提供したものからすると、それは正しいことでした。修正は、それほど多くの異なるスロットに存在しないキーを提供することです。書き込みパスも同様の問題を抱えていました。 #ハッシュタグ Redisには、ハッシュタグと呼ばれるエスケープハッチがあります。キーに中括弧で囲まれたテキストチャンクが含まれている場合、Redisはその中括弧の間のテキストのみをハッシュし、キーの残りは無視します。これにより、キーを特定のスロットに強制するためのレバーが得られます。 クライアントプロセスプライマリ1プライマリ2プライマリ3 #01#02#03#04#05#06#07#08#09#10#11#12 1/4・キーのバッチ、まだプロセス内 0ラウンドトリップ 89283082a53ffff:892830828efffff:9 Play Step Twelve ルートキー、3つのプライマリ。 すべてのキーが独自の Слот に入り、1つのMGETが12ラウンドトリップに変わります。 共有タグを中括弧で囲むと、中括弧のみがハッシュされるため、同じ12個のキーが3つのスロットに収まります。 3ラウンドトリップ、ノードごとに1つ、同時に実行されます。 重要なのは、中括弧に何を入れるかです。私はビットコインを所有したことはありませんが、この問題はビットコインブロックチェーンが意味のない数値をブロックに入れてハッシュが特定のプロパティに一致するようにする方法を思い出させました。ここでは、はるかに単純な要件でこれを行う必要がありました。私は整数を選択し、ブロックチェーンマイナーのように総当たりで見つけました。タグは実際にはテンプレートのようなもので、{routing:v1:<n>} のようなものです。起動時にゼロから反復し、その都度タグ全体のハッシュをチェックして、どのスロットに入るかを確認します。必要なスロットがすべて得られるまでこれを繰り返します。タグが機能すると、数千のキーのバッチは、正確に1つのノードを対象とする少数の合法的なマルチキーコマンドに分割できます。 プライマリ5タグ/プライマリ4 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スキップ・20のうち10を保持 anchors = [] Play Step Finish タグテンプレートは routing:v1:%d です。各整数はRedisがハッシュするのと同じ方法でハッシュされ、そのスロットを所有するプライマリに配置されます。そのプライマリにまだ空きがあれば、整数は保持されます。そうでなければ、破棄され、ウォークは続行されます。プライマリ5つでそれぞれ4つずつだと、28個の整数が必要で、そのうち8個はすでに満杯のスロットに配置されます。何も保存されません。同じウォークを同じクラスターに対して実行するすべてのプロセスは、同じリストを取得します。 キーをソートしてからファンアウトする 各Redisノードは単一のスレッドでコマンドを実行するため、同じノードを対象とする20の同時リクエストは、実質的にキューになります。ファンアウトを折りたたむことで、実行する必要のあるMGETリクエストの数は減りましたが、特定のノードにそれらをスパムすることを妨げるものではありませんでした。リストをチャンク化する グループ化/ Слот チャンクあたりのキー 4 3コマンド 3コマンド 3コマンド 2コマンド 2コマンド 3コマンド プライマリ1プライマリ2プライマリ3 0123456 コマンド時間・16コマンド 0.0で完了 チャンクにカットし、各チャンクには複数のスロットのキーが含まれるため、クライアントはそれを分割し、各プライマリはチャンクごとに1つのコマンドを受け取り、次々と実行します。 Слотごとにグループ化すると、プライマリごとに1つのコマンドになり、すべて同時にインフライト状態になります。 チャンクサイズはダイヤル全体であり、間違った方向に実行されます。細かくカットするほどコマンドが増えるため、より多くのゴルーチンにファンアウトすることが読み取りを遅くします。チャンクが宛先で整理されていない場合、それらのいくつかは同時に同じノードをターゲットにし、そのノードはそれらを1つずつ処理し、他のノードはアイドル状態になります。そのため、ワイヤーに何も出る前に、ローカルで各キーのスロットを計算し、それによってグループ化します。次に、ファンアウトは任意のチャンクではなくノードに対して行われ、各リクエストは有用な作業を行います。 MSETは有効期限を設定しない キャッシュされたルート見積もりには有効期限が必要です。MSETには有効期限引数がありません。通常の回避策は、キーごとにSET ... EXをパイプライン化することですが、これは1つのコマンドを数千に変換します。または、MSETしてから2番目のパスでEXPIREすることもできますが、