Servi i cluster di mappe 50 volte più velocemente utilizzando una cache più intelligente

I componenti della mappa che presentano indicatori di posizione sono oggi comuni nelle app mobili. Ad esempio, l'app di Airbnb mette in evidenza tali indicatori, recuperati da un servizio web, per rappresentare le proprietà disponibili su una mappa.

Per garantire che il volume dei dati recuperati non diventi ingestibile all'aumentare del numero di indicatori, il server raggruppa questi indicatori prima di inviarli al client. Un cluster di mappe è un marker specializzato la cui posizione è uguale alla posizione media dei marker che sussume. È etichettato con il numero di marcatori che rappresenta.

Tuttavia, i cluster di servizio possono creare colli di bottiglia delle prestazioni perché un servizio Web deve recuperare dal database ogni singolo indicatore all'interno di una determinata area geografica. Fortunatamente, questo problema può essere risolto con una strategia di memorizzazione nella cache. Per capire meglio come progettare e gestire una cache, diamo un'occhiata a un endpoint dell'API della mappa di esempio che ho creato per l'app Playsports.

Un problema di ridimensionamento e una soluzione ingenua

Nella mappa Playsports, ogni indicatore rappresenta un impianto sportivo. L'endpoint API della mappa deve restituire un elenco di marker e cluster di marker, dati un livello di zoom e un riquadro di delimitazione.

Se il numero di marker è sufficientemente piccolo, possiamo caricare tutti i marker nel riquadro di delimitazione dal database, raggrupparli secondo necessità e restituire i marker e i cluster risultanti al client.

All'inizio, il numero massimo di marcatori in qualsiasi riquadro di delimitazione raggiungibile in Playsports era di circa 400, con una velocità finale di circa 0,5 secondi. L'implementazione della soluzione ingenua è stata sufficiente per questo caso d'uso.

Con l'aumento del numero di indicatori, tuttavia, l'inefficienza del meccanismo è diventata evidente. Dopo aver aggiunto circa 10.000 nuovi indicatori di impianti sportivi, la velocità dell'endpoint è rallentata a circa 4,3 secondi sotto alcuni livelli di zoom. Questa frequenza è di gran lunga inferiore alla durata di un secondo che è generalmente considerata il ritardo massimo accettabile per un'azione dell'utente in un'app mobile.

Per comprendere meglio le inefficienze della soluzione ingenua, analizziamola nel contesto della query del marker:

1. Dal database, recuperare tutti i marcatori nel riquadro di delimitazione . Per la maggior parte delle app, questo passaggio deve includere il recupero dei dettagli dell'indicatore oltre il posizionamento di latitudine/longitudine. Ad esempio, gli indicatori di Airbnb includono il prezzo, se l'utente ha già visualizzato la proprietà e se l'ha contrassegnata come preferita.
2. Sugli indicatori recuperati, eseguire un algoritmo di raggruppamento delle mappe che incorpora il livello di zoom.
3. Restituire cluster e marker (dettagliati) al cliente.

All'aumentare del numero di marker, le prestazioni peggiorano nei passaggi 1 e 2:

• Quando il riquadro di delimitazione è sufficientemente grande e quando più di 10.000 indicatori richiedono una ricerca dei dettagli tramite un JOIN, la query del database rallenta notevolmente (da 1 a 2 secondi).
• L'alimentazione di 10.000 elementi all'algoritmo di raggruppamento delle mappe richiede altri circa 250 millisecondi.

Assumendo una dimensione della finestra costante, quando un riquadro di delimitazione è relativamente grande, il livello di zoom è generalmente basso (cioè, rimpicciolito di molto). Con livelli di zoom bassi, i risultati tendono a favorire i cluster per evitare l'affollamento visivo. Pertanto, il maggiore potenziale di ottimizzazione risiede nella prima fase della soluzione, in cui vengono caricati migliaia di singoli marker. Non abbiamo bisogno della maggior parte di questi marcatori nel risultato. Abbiamo solo bisogno che ognuno di loro conti per un cluster.

Architettura della soluzione ottimizzata

La soluzione ingenua richiede molto più tempo per completare una query nel caso peggiore: un rettangolo di delimitazione massimo in una regione densa di marcatori. Al contrario, la soluzione ottimizzata richiederebbe solo 73 ms, il che rappresenta un aumento di velocità di circa 58x. Da un livello alto, sembra così:

1. La strategia di memorizzazione nella cache. Recupera indicatori e cluster in un riquadro di delimitazione da una cache specifica del livello di zoom.
2. Dettagli aggiuntivi dell'indicatore (opzionale). Migliora i marker con un payload recuperato dal database.
3. Restituzione del risultato. Restituire marker e cluster al cliente.

La complessità principale risiede nell'architettura della cache (cioè il primo passaggio).

Passaggio 1: la strategia di memorizzazione nella cache

Questo passaggio principale è composto da sei componenti:

Tecnologia

Redis è un database in memoria veloce che viene comunemente utilizzato come cache. La sua indicizzazione geospaziale incorporata utilizza l'algoritmo Geohash per l'archiviazione e il recupero efficiente dei punti di latitudine-longitudine, che è esattamente ciò di cui abbiamo bisogno per i nostri marker.

Una cache per ogni livello di zoom

Il grado di clustering della mappa (se vengono restituiti singoli marker o cluster) è determinato dal livello di zoom passato all'endpoint.

• Per livelli di zoom elevati (ad esempio, ingrandimenti ravvicinati), il risultato favorirà i singoli marker, tranne che nelle regioni ad alta densità di marker.
• Per i livelli di zoom bassi (ovvero, rimpiccioliti di molto), il risultato favorirà i cluster, ad eccezione delle regioni con marcatori sparpagliati.

Google Maps supporta livelli di zoom da zero a un massimo di 20, a seconda dell'area. (Gli intervalli supportati da altri servizi di mappe sono simili. Ad esempio, Mapbox utilizza livelli di zoom da zero a un massimo di 23.) Poiché questi livelli di zoom sono anche valori interi, possiamo semplicemente creare una cache separata per ogni livello di zoom.

Per supportare tutti i livelli di zoom in Google Maps, eccetto il livello zero, che è troppo ingrandito, creeremo 20 cache distinte. Ogni cache memorizzerà tutti i marker e i cluster per l'intera mappa, raggruppati per il livello di zoom che rappresenta.

Tipi di dati della cache

Ogni cache memorizzerebbe cluster e singoli marker. Per entrambi i tipi di voci, dovremo compilare diversi campi:

Tuttavia, Redis consente agli utenti di memorizzare solo la posizione, più una singola stringa, come valore in un set geospaziale. Per aggirare questa restrizione, serializziamo i campi sopra in una stringa JSON. Usiamo quindi questa stringa come valore in Redis. La dimensione massima di chiavi e valori in Redis è 512 MB, che è più che sufficiente per questo caso d'uso.

Riempimento delle cache

Per riempire le cache, recuperiamo tutti i marker dal database. Per ogni livello di zoom, eseguiamo l'algoritmo di raggruppamento delle mappe. Utilizziamo il GEOADD di Redis per inserire i marcatori e i cluster risultanti nella cache del livello di zoom corrispondente e passare lungo la latitudine e la longitudine, oltre alla stringa JSON precedentemente descritta.

L'esecuzione dell'algoritmo di raggruppamento delle mappe sull'intera mappa in questa fase (piuttosto che su un riquadro di delimitazione dell'utente, su richiesta) potrebbe teoricamente produrre alcune differenze di bordo nel posizionamento del cluster, ma l'esperienza utente complessiva rimarrà la stessa.

Interrogazione della cache

Per una richiesta in arrivo, passiamo il riquadro di delimitazione specificato al comando Redis GEOSEARCH , che interroga la cache del livello di zoom specificato per recuperare marker e cluster candidati nell'area.

Progettazione di un piano di aggiornamento della cache

Un aggiornamento della cache a 20 livelli è costoso, quindi è meglio eseguire l'aggiornamento con la frequenza consentita dai requisiti del progetto. Ad esempio, l'aggiunta o la rimozione di un impianto sportivo in Playsports contrassegna solo la cache come obsoleta; un cron job ogni ora aggiorna la cache, se necessario. Maggiori informazioni su questo nella sezione Cache Staleness.

Passaggio 2: dettagli aggiuntivi sull'indicatore (opzionale)

A questo punto, la maggior parte delle app dovrà recuperare i dettagli in base ai singoli ID marker. Potremmo rendere questo dettaglio parte dei valori JSON in formato stringa nella cache, ma in molte app i dettagli del marcatore sono specifici dell'utente. Poiché esiste un'unica cache condivisa per tutti gli utenti, non è possibile archiviare questi campi aggiuntivi lì.

La nostra soluzione ottimizzata prende gli ID dei singoli marker dal risultato della cache e ne recupera i dettagli dal database. Ora stiamo solo cercando i singoli marcatori rimasti dopo il raggruppamento. Non ce ne saranno troppi quando la mappa viene ingrandita (perché avremo per lo più cluster) né quando viene ingrandita (perché l'area sarà piccola).

Al contrario, la soluzione ingenua cerca tutti i marcatori nel riquadro di delimitazione (e i relativi dettagli) prima del raggruppamento. Pertanto, questo passaggio, facoltativo, ma cruciale per molte app, ora viene eseguito molto più velocemente.

Passaggio 3: restituzione del risultato

Con i cluster creati e i singoli marker migliorati, ora possiamo consegnarli al cliente. A parte alcuni casi limite irrilevanti, i dati risultanti sono quasi identici alla soluzione ingenua, ma siamo in grado di fornirli molto più velocemente.

Ulteriori considerazioni

Ora diamo un'occhiata a due fattori aggiuntivi:

Bisogni di risorse

Supponiamo che la mappa di un'app contenga N marcatori in totale. Dato che sono disponibili fino a 20 livelli di zoom, avremmo bisogno di memorizzare al massimo 20 N elementi della cache. In pratica, tuttavia, il numero effettivo di elementi della cache è spesso molto più basso a causa del raggruppamento, specialmente nei livelli di zoom inferiori. In effetti, il numero totale di elementi della cache distribuiti tra tutte le cache di Playsports è solo ~ 2N.

Inoltre, se assumiamo che la lunghezza di un valore della cache (il JSON stringato) sia di circa 250 caratteri (un presupposto ragionevole, almeno per Playsports) e la dimensione della stringa sia di 1 byte per carattere, la quantità di memoria cache necessaria per il I valori JSON sarebbero circa 2 * N * 250 byte.

A questa figura aggiungiamo le strutture dati interne di Redis per gli insiemi ordinati utilizzati da GEOADD . Redis utilizza 85 MB di memoria per 1 milione di piccole coppie chiave-valore, quindi possiamo supporre che gli interni di Redis rappresentino meno di 100 byte per elemento della cache. Ciò significa che potremmo utilizzare un'istanza Redis da 1 GB-RAM per supportare fino a 1,4 milioni di marker. Anche nell'improbabile scenario in cui i marker siano distribuiti uniformemente sull'intera mappa, con il risultato che il numero di elementi della cache si avvicina a 20N, N potrebbe comunque salire a ~140.000. Poiché un'istanza Redis può gestire più di 4 miliardi di chiavi (2 ³² , per l'esattezza), questo non è un fattore limitante.

Stanchezza della cache

A seconda del caso d'uso, potrebbe non essere sufficiente aggiornare la cache solo periodicamente. In questi casi, potremmo utilizzare una coda di attività a velocità limitata. Ridurrebbe la obsolescenza della cache, pur limitando il numero di aggiornamenti della cache e quindi il carico sul sistema.

Dopo ogni aggiornamento del database, accodiamo un processo di aggiornamento della cache. Questa coda limiterebbe il numero di attività a M all'ora. Questo compromesso consente aggiornamenti più rapidi dell'orario mantenendo un carico relativamente basso sul sistema (a seconda di M).

Le strategie di memorizzazione nella cache superano gli algoritmi di raggruppamento di mappe

La soluzione ottimizzata per Playsports, più di 50 volte più veloce della soluzione ingenua, ha funzionato bene. Dovrebbe continuare a funzionare bene, fino a raggiungere 1,4 milioni di marcatori o più di 100 volte i dati esistenti.

Per la maggior parte delle richieste di servizi Web basate su mappe, è necessaria una qualche forma di precalcolo per consentire la scalabilità. Il tipo di tecnologia da utilizzare, così come il design specifico, dipenderebbero dalle esigenze aziendali. Le esigenze di obsolescenza della cache, l'aumento dei marker e il numero di marker sono caratteristiche importanti da tenere in considerazione durante la progettazione di una soluzione.

Ulteriori letture sul blog di Toptal Engineering:

• Sondaggio sui migliori strumenti di mappatura online per sviluppatori Web: dalla roadmap alla roadmap
• Avventure nella programmazione e sviluppo GPS: un tutorial geospaziale