よりスマートなキャッシングを使用して、マップクラスターに50倍高速にサービスを提供

ロケーションマーカーを備えたマップコンポーネントは、今日のモバイルアプリでは一般的です。 たとえば、Airbnbアプリは、ウェブサービスから取得したこのようなマーカーを目立つように備えており、地図上で利用可能なプロパティを表します。

マーカーの数が増えてもフェッチされたデータの量が管理不能にならないようにするために、サーバーはそれらのマーカーをクライアントに送信する前にグループ化します。 マップクラスターは、その位置が含まれるマーカーの平均位置に等しい特殊なマーカーです。 それが表すマーカーの数でラベル付けされています。

それでも、Webサービスはデータベースから特定の地理的領域内のすべてのマーカーを取得する必要があるため、クラスターにサービスを提供するとパフォーマンスのボトルネックが発生する可能性があります。 幸い、この問題はキャッシュ戦略で解決できます。 キャッシュを設計および維持する方法をよりよく理解するために、Playsportsアプリ用に作成したマップAPIエンドポイントの例を見てみましょう。

スケーリングの問題と単純な解決策

Playsportsマップでは、各マーカーはスポーツ施設を表しています。 マップのAPIエンドポイントは、ズームレベルと境界ボックスを指定して、マーカーとマーカークラスターのリストを返す必要があります。

マーカーの数が十分に少ない場合は、バウンディングボックス内のすべてのマーカーをデータベースからロードし、必要に応じてクラスター化して、結果のマーカーとクラスターをクライアントに返すことができます。

当初、Playsportsの到達可能なバウンディングボックス内のマーカーの最大数は約400であり、エンドポイントの速度は約0.5秒でした。 このユースケースでは、ナイーブなソリューションを実装するだけで十分でした。

しかし、マーカーの数が増えるにつれて、メカニズムの非効率性が明らかになりました。 〜10,000の新しいスポーツ施設マーカーを追加した後、一部のズームレベルでは、エンドポイントの速度が〜4.3秒に低下しました。 このレートは、モバイルアプリでのユーザーアクションの最大許容遅延と一般に考えられている1秒の期間をはるかに下回っています。

ナイーブソリューションの非効率性をよりよく理解するために、マーカークエリのコンテキストで分析してみましょう。

1. データベースから、バウンディングボックス内のすべてのマーカーを取得します。 ほとんどのアプリでは、この手順に緯度/経度の位置を超えたマーカーの詳細の取得を含める必要があります。 たとえば、Airbnbのマーカーには、価格、ユーザーがすでに物件を閲覧したかどうか、お気に入りとしてマークしたかどうかが含まれます。
2. 取得したマーカーで、ズームレベルを組み込んだマップクラスタリングアルゴリズムを実行します。
3. クラスターと（詳細な）マーカーをクライアントに返します。

マーカーの数が増えると、ステップ1と2でパフォーマンスが低下します。

• バウンディングボックスが十分に大きい場合、および10,000を超えるマーカーがJOINを介した詳細ルックアップを必要とする場合、データベースクエリは劇的に遅くなります（1〜2秒）。
• 10,000個のアイテムをマップクラスタリングアルゴリズムにフィードするには、さらに約250ミリ秒かかります。

ウィンドウサイズが一定であると仮定すると、バウンディングボックスが比較的大きい場合、ズームレベルは通常低くなります（つまり、ズームアウトします）。 ズームレベルが低い場合、結果は視覚的な混雑を避けるためにクラスターを優先する傾向があります。 したがって、最適化の最大の可能性は、数千の個別のマーカーがロードされるソリューションの最初のステップにあります。 結果にこれらのマーカーのほとんどは必要ありません。 クラスターにカウントするために必要なのは、それぞれだけです。

最適化されたソリューションの設計

単純なソリューションは、最悪の場合のクエリ（マーカーが密集した領域の最大バウンディングボックス）を完了するのにかなり長い時間がかかります。 対照的に、最適化されたソリューションはわずか73ミリ秒かかり、約58倍のスピードアップに相当します。 大まかに見ると、次のようになります。

1. キャッシング戦略。 ズームレベル固有のキャッシュからバウンディングボックス内のマーカーとクラスターを取得します。
2. 追加のマーカーの詳細（オプション）。 データベースからフェッチされたペイロードでマーカーを拡張します。
3. 結果を返します。 マーカーとクラスターをクライアントに返します。

主な複雑さは、キャッシュのアーキテクチャ（つまり、最初のステップ）にあります。

ステップ1：キャッシング戦略

このメインステップは、次の6つのコンポーネントで構成されています。

テクノロジー

Redisは、キャッシュとして一般的に使用される高速のインメモリデータベースです。 組み込みの地理空間インデックスは、ジオハッシュアルゴリズムを使用して、緯度と経度のポイントを効率的に保存および取得します。これは、まさにマーカーに必要なものです。

各ズームレベルのキャッシュ

マップのクラスタリングの程度（単一のマーカーまたはクラスターが返されるかどうか）は、エンドポイントに渡されるズームレベルによって決定されます。

• ズームレベルが高い場合（つまり、ズームインした場合）、マーカーが密集している領域を除いて、結果は個々のマーカーを優先します。
• ズームレベルが低い場合（つまり、ズームアウトが遠い場合）、マーカーがまばらな領域を除いて、結果はクラスターに有利になります。

Googleマップは、エリアに応じて、ゼロから最大20までのズームレベルをサポートしています。 （他のマップサービスでサポートされている範囲も同様です。たとえば、Mapboxはゼロから最大23までのズームレベルを使用します。）これらのズームレベルも整数値であるため、ズームレベルごとに個別のキャッシュを作成できます。

Googleマップのすべてのズームレベルをサポートするために（ズームアウトが大きすぎるレベル0を除く）、20個の個別のキャッシュを作成します。 各キャッシュには、マップ全体のすべてのマーカーとクラスターが、それが表すズームレベルでクラスター化されて保存されます。

キャッシュデータ型

各キャッシュには、クラスターと個々のマーカーが格納されます。 どちらのタイプのエントリでも、いくつかのフィールドに入力する必要があります。

ただし、Redisでは、地理空間セットの値として、場所と1つの文字列のみを保存できます。 この制限を回避するために、上記のフィールドをJSON文字列でシリアル化します。 次に、この文字列をRedisの値として使用します。 Redisのキーと値の両方の最大サイズは512MBであり、このユースケースには十分すぎるほどです。

キャッシュを埋める

キャッシュを埋めるために、データベースからすべてのマーカーを取得します。 ズームレベルごとに、マップクラスタリングアルゴリズムを実行します。 RedisのGEOADDを使用して、結果のマーカーとクラスターを対応するズームレベルのキャッシュに挿入し、緯度と経度に加えて、前述のJSON文字列を渡します。

この段階で（ユーザーからのバウンディングボックスではなく、オンデマンドで）マップ全体でマップクラスタリングアルゴリズムを実行すると、理論的にはクラスターの配置にエッジの違いが生じる可能性がありますが、全体的なユーザーエクスペリエンスは同じままです。

キャッシュのクエリ

着信リクエストの場合、指定された境界ボックスをRedis GEOSEARCHコマンドに渡します。このコマンドは、指定されたズームレベルのキャッシュをクエリして、エリア内のマーカーとクラスターの候補を取得します。

キャッシュ更新計画の設計

20レベルのキャッシュの更新にはコストがかかるため、プロジェクトの要件が許す限り、頻繁に更新しないことをお勧めします。 たとえば、Playsportsでのスポーツ施設の追加または削除は、キャッシュを古いものとしてマークするだけです。 その後、1時間ごとのcronジョブにより、必要に応じてキャッシュが更新されます。 これについては、「キャッシュの古さ」セクションで詳しく説明します。

ステップ2：追加のマーカーの詳細（オプション）

この時点で、ほとんどのアプリは個々のマーカーIDに基づいて詳細を取得する必要があります。 この詳細をキャッシュ内の文字列化されたJSON値の一部にすることもできますが、多くのアプリでは、マーカーの詳細はユーザー固有です。 すべてのユーザーに単一の共有キャッシュがあるため、これらの追加フィールドをそこに保存することはできません。

最適化されたソリューションは、キャッシュ結果から個々のマーカーのIDを取得し、データベースからそれらの詳細をフェッチします。 現在、クラスタリング後に残っている個々のマーカーのみを検索しています。 マップをズームアウトしたとき（ほとんどの場合クラスターがあるため）、またはズームインしたとき（領域が小さくなるため）、これらの数はそれほど多くありません。

対照的に、単純なソリューションは、クラスタリングの前にバウンディングボックス内のすべてのマーカー（およびそれらの詳細）を検索します。 したがって、このステップ（オプションですが、多くのアプリにとって重要です）は、はるかに高速に実行されるようになりました。

ステップ3：結果を返す

クラスターが構築され、個々のマーカーが強化されたので、これらをクライアントに配信できるようになりました。 いくつかの重要でないエッジケースを除けば、結果のデータは単純なソリューションとほぼ同じですが、はるかに高速に配信できます。

さらなる考慮事項

次に、2つの追加要素を見てみましょう。

リソースのニーズ

アプリのマップに合計N個のマーカーが含まれていると仮定します。 最大20のズームレベルがあるため、最大で20Nのキャッシュアイテムを保存する必要があります。 ただし、実際には、特にズームレベルが低い場合、クラスタリングのために実際のキャッシュアイテム数ははるかに少なくなることがよくあります。 実際、Playsportsのすべてのキャッシュに分散されているキャッシュアイテムの総数はわずか2Nです。

さらに、キャッシュ値（文字列化されたJSON）の長さが約250文字（少なくともPlaysportsの場合は妥当な仮定）であり、文字列サイズが1文字あたり1バイトであると仮定すると、 JSON値は約2*N*250バイトになります。

この図に、 GEOADDで使用されるソート済みセットのRedisの内部データ構造を追加します。 Redisは100万の小さなキーと値のペアに85MBのメモリを使用するため、Redisの内部アカウントがキャッシュアイテムあたり100バイト未満であると想定できます。 つまり、1 GB-RAMのRedisインスタンスを使用して、140万ものマーカーをサポートできるということです。 マーカーがマップ全体に均等に分散され、キャッシュアイテムの数が20Nに近づくというありそうもないシナリオでも、Nは最大140,000に達する可能性があります。 Redisインスタンスは40億を超えるキー（正確には2 ³² ）を処理できるため、これは制限要因ではありません。

キャッシュの古さ

ユースケースによっては、キャッシュを定期的に更新するだけでは不十分な場合があります。 このような場合、レート制限されたタスクキューを使用できます。 キャッシュの更新回数を制限しながら、キャッシュの古さを減らし、システムの負荷を軽減します。

データベースを更新するたびに、キャッシュ更新ジョブをキューに入れます。 このキューは、タスクの数を1時間あたりMに制限します。 この妥協により、システムの負荷を比較的低く維持しながら、1時間よりも速い更新が可能になります（Mによって異なります）。

キャッシング戦略はマップクラスタリングアルゴリズムよりも重要です

Playsports用に最適化されたソリューション（単純なソリューションよりも50倍以上高速）はうまく機能しました。 140万個のマーカー、または既存のデータの100倍以上に達するまで、引き続き正常に機能するはずです。

ほとんどのマップベースのWebサービス要求では、スケーラビリティを考慮して、何らかの形式の事前計算が必要です。 使用するテクノロジの種類、および特定の設計は、ビジネス要件によって異なります。 キャッシュの古さのニーズ、マーカーの増強、およびマーカーの数は、ソリューションを設計する際に考慮すべき重要な特性です。

Toptal Engineeringブログでさらに読む：

• Web開発者向けの最高のオンラインマッピングツールの調査：ロードマップからロードマップへ
• GPSプログラミングと開発の冒険：地理空間チュートリアル