
2026/09/24 2:07
誰にも RediHashスロットのことを教えてくれなかったのか。
RSS: https://news.ycombinator.com/rss
要約▶
Japanese Translation:
高トラフィックのギグ経済向けアプリにおける重要なパフォーマンス向上により、繁忙地域の連続的なリクエストが主な原因となる経路推定サービスにおける深刻なレイテンシー問題が解決されました。地理データをキャッシュする方法を最適化したことで、配達員へのジョブオファーの配信速度は大幅に改善され、ユーザーエクスペリエンスも著しくレスポンシブになりました。核心的な課題は Redis のスロットアーキテクチャに由来し、
origin_hex:dest_hex:resolution などの鍵に含まれるユニークな H3 ヘキサゴン ID がネットワークリクエストの断片化を引き起こした点です。鍵が異なるハッシュスロットに入力されると、MSET/MGET コマンドがプライマリノード間で複数の往復を強制されました。この問題に対処するため、エンジニアは H3 ヘキサゴン ID を活用した特別の重複排除戦略を実装し、鍵を効率的にグループ化するハッシュタグを導入しました。これにより、バッチ操作をプライマリノード上で実行することができながら、本番環境のクラッシュを防ぐことができました。また、大規模なデータ取得時の CPU 負荷を大幅に削減するために、重い JSON オブジェクトから軽量なカンマ区切り文字列への切り替えを行いました。さらに、MSET コマンドにはネイティブの有効期限引数がないため、キャッシュの有効期限処理には EVAL スクリプトが採用されました。デプロイ前に厳格なベンチマークによりこれらの成果を検証し、標準的なキャッシュツールを用いて高周回のジオスペースクエリを処理し、サーバーリソースを使い尽くさずに信頼性のあるスケーラブルなパターンを確立しました。本文
配送ギグエコノミーにおける Redis スロット割り当てとパフォーマンス最適化の事例
配送ギグエコノミーアプリにおいて、注文入力から最適な配達人へのタスク提案(オファー)を決定するサービスの開発に携わりました。マッチング精度は「距離」によって左右されやすく、経路計算エンジンへの依存度が高く、システムレイテンシが最大のボトルネックとなっています。
当サービスには極めて厳格なレイテンシ目標があり、これを遵守しなければなりません。バケツの容量を超えると全ての関係者が被害を受けるため、限られた時間内に「バケツ」を常に空ける必要があります。
問題の形状:巨大な経路見積もりとキャッシュの難しさ
活発なエリアでは、単一のワーク割り当てパスに膨大な数の経路見積もりが必要となり、その処理は継続的に繰り返されます。
- 見積もりの有用性と頻度
- 隣家の住民がスーパーマーケットへ行く所要時間はほぼ一定であり、ガソリンスタンドへのドライブも似た時間特性を示す。
- レストランのような固定施設の位置は変わらないため、ブロック離れた複数の配達人が類似した経路リクエストを生成し続けます(例:30 秒後に新たな位置から同じようなリクエストが発生)。
- キャッシュ層の欠如
- もしキャッシュが存在せず、重複した作業を行わなければなりません。
- 機能上同様の距離データを数分ごとに再計算することになりかねません。
- プロセス固有キャッシュの限界
- 見積もりを計算するプロセスと、次にその結果を必要とするプロセスは稀に一致します。
- そのため、共有キャッシュとして機能させることが困難です。
安易なアプローチとその失敗:H3 と Redis ハッシュスロット
生座標上のキャッシュだけでは解決できず、重複排除のためにH3(六角形格子システム)を使用する必要があります。しかし、単純なハッシュ化は Redis クラスター環境で致命的な問題を引き起こしました。
H3 のジレンマ
- レバーの調整:解像度(六角形のサイズ)を調整することでトレードオフが発生します。
- 六角形が大きいほどヒット率が高いが、見積もりの精度が低下する。
- 六角形が小さいほど精度は高いが、キー数が爆発的に増加しキャッシュ効率が悪化する。
- 必要となるデータ構造:鍵には
を使用し、値は見積もりです(書き込みには<元六角形 ID>: <先六角形 ID>: <解像度>
を使用)。MSET
Redis クラスターとスロット割り当ての壁
Redis クラスターでは、キーとその値を均等に分散させる必要があります。Redis は 16,384 のハッシュスロットを生成し、ノード間で分布させます。
- マルチキーコマンドの制約:
やMSET
などの複数キー処理は、すべてのキーが同じハッシュスロットに割り当てられる場合에만有効です。MGET - 悲劇の実態:
- Redis は
でスロットを決定します。CRC16(key) mod 16384 - 文字が一つだけ異なる 2 つのキーでも、全く関係のないスロットに割り当てられてしまう可能性があります。
- 結果として、一意な六角形 ID 対を含む鍵は、互いに同じスロットに割り当てられることがなく、1 つの
命令が多数のスロット(往復通信)に分かれてしまいました。MGET
- Redis は
解決策:Redis ハッシュタグによる強制スロットリング
この課題に対し、Redis が用意した「エスケープハッチ」であるハッシュタグを活用しました。
ハッシュタグの仕組み
- キーの中に角括弧
間のテキストを含めると、Redis はそれ以外のキー部分を無視して、角括弧内のテキストのみをハッシュ化します。{} - これにより、特定のスロットにキーを強制的に割り当てるレバーを手に入れることができました。
クライアント側の最適化戦略
単一のプライマリノードに対して多数の往復通信を行わず、並行実行を可能にする設計を行いました。
比較:ハッシュタグ使用前后
| シナリオ | キーの扱い方 | スロット割り当て | 通信効率 |
|---|---|---|---|
| 従来(悪い) | (全体をハッシュ化) | 各キーが独自のスロットへ分散 | 1 つの が12 回の往復通信に分かれる |
| 改善後(良い) | (角括弧内のみハッシュ化) | 同じタグを持つ鍵が同じスロットへ圧縮 | 1 つの が3 つのスロットに統合され、並行実行可能に |
タグテンプレートの決定手法
出力ハッシュに対する要件は単純でした。ブルートフォース探索で最適な整数を探るのではなく、以下のプロセスで決まりました。
- 基本単位: プライマリノード 1 つあたり 5 のタグを確保します。
- アルゴリズム:
と順に整数を増やします。n = 0, 1, 2, ...- タグテンプレート:
を作成し、全体をハッシュ化してどのスロットへ割り当てられるかを確認します。{routing:v1:<n>} - すべてのプライマリノードが必要な数のキーを持つまで、この処理を繰り返します。
スロット分布の例(プライマリー 1〜5)
- プライマリー 1: スロット 0〜3276
- プライマリー 2: スロット 3277〜6553
- プライマリー 3: スロット 6554〜9830
- プライマリー 4: スロット 9831〜13107
- プライマリー 5: スロット 13108〜16383
計算の注意点:
- プライマリ 5 ノードで各ノードに 4 つ(合計 28 の整数)が必要な場合、そのうち 8 つは既に占有されたスロットに入ることになります。
- 実際にデータを保存する必要はありません。同じクラスタに対して同一のリストを取得すれば済みためです。
ファンアウト前にキーをソートする
各 Redis ノードは単一のスレッドでコマンドを実行するため、同一ノードへの大量のリクエストは実質的にキューとなります。ファンアウトにより
MGET の数は減っても、特定のノードへの負荷過多を防げない場合があります。
問題点
- チャンクが宛先に整理されておらず、複数のキーが同時に同じノードをターゲットにすると、そのノードでは順序立てて処理が行われ、他のノードはアイドル状態になります。
- リードが遅延します。
解決策:スロットベースのグループ化
ネットワークへ送出する前に、以下の手順を実行します。
- ローカル計算: すべてのキーのローカルスロットを計算し、スロットごとにグループ化します。
- ファンアウト実行: 「任意のチャンク」ではなく、「ノード単位」でリクエストを送信します。
- これにより、各リクエストが有意な処理を行い、並行実行が可能になります。
MSET は有効期限をサポートしない
キャッシュされた経路見積もりには有効期限を設定する必要がありますが、
MSET コマンドには有効期限引数がありません。
- 非効率な対処法 1: 各キーに対して
をパイプライン化し、1 つのコマンドを数千に分散する(効率が悪い)。SET ... EX - 非効率な対処法 2:
を実行後、第二のパスでMSET
を呼ぶ(コマンド数が倍増し、クラッシュリスクがある)。EXPIRE
最終的な解決策: Redis にスクリプトを実行させる
EVAL コマンドを使用しました。これにより、1 つの命令でセットと有効期限の管理を完了できます。
JSON は無料ではありません
当初、キャッシュされた値を JSON 形式で保存していましたが、スケールが大きくなるに従ってこれは大きな問題となりました。
- ペナルティ: ペイロードが小さいため影響はないと思っても、当サービスの規模では貴重な CPU 時間を浪費していました。
- 改善策: 値をカンマ区切りの文字列に変えることで、劇的な改善が見られました。
ここで何を学んだのか?
このプロジェクトを通じて得た教訓はすべて、「予想していなかった形で前段階が失敗する原因を探る作業」でした。
Rob Pike の「プログラムの 5 つの法則」の再発見
- 法則 2. 計測する。
- スピードのためにチューニングを行うのは、まず計測してからでなければなりません。
- コードの一部分だけが他の部分に比べて圧倒的に重い場合でもなければなりません。
- 法則 3.
が小さい場合、高度なアルゴリズムは遅くなります。n- 通常、
は小さいものです。n - 高度なアルゴリズムには大きな定数があります。
が頻繁に大きくなることがわからない限り、過度に複雑化するべきではありません。n
失敗の要因と教訓
- ボトルネック: 経路サービスとの相互作用が最大の原因でした。
- 過信: 「単純なアプローチ」を採用したが、扱うデータ量
は確実に大きく、予想以上に高度なアルゴリズム(スロット管理など)が必要だったことを認識していませんでした。n
ベンチマークハネスの重要性
スループットの問題に直面した際、ベンチマークテスト用のハネス(テスト枠組み)を作成しました。これにより、レバーをオン・オフして操作可能な玩具アプリを作り、各アプローチのスループット影響を測定できました。
- 本番導入前: ハネスを使って各アプローチを検証し、誠実なパフォーマンス評価を得ることができました。
- 反省点: 後付けで考えると、ベンチマークハネスを先に構築すべきだったと思います。
- 業界のデフォルトは「今すぐリリースして後で直す」ですが、これは大失敗の元になります。
- 「2 ポイントのチケットが今や 5 ポイントになっている」という事実を見逃しがちです。
新しい習慣
新しいプロジェクトを始める際、最初に包括的なベンチマークハネスを構築することから始めます。これが大きな成果につながっているため、これを習慣化しようとしています。