Serviți clustere de hărți de 50 de ori mai rapid, folosind o memorie cache mai inteligentă

Componentele hărților care prezintă marcatori de locație sunt obișnuite în aplicațiile mobile de astăzi. De exemplu, aplicația Airbnb prezintă în mod vizibil astfel de marcatori, preluați de la un serviciu web, pentru a reprezenta proprietățile disponibile pe o hartă.

Pentru a se asigura că volumul de date preluate nu devine de negestionat pe măsură ce numărul de marcatori crește, serverul grupează acești marcatori înainte de a le trimite către client. Un cluster de hărți este un marker specializat a cărui poziție este egală cu poziția medie a markerilor pe care îi include. Este etichetat cu numărul de markeri pe care îl reprezintă.

Totuși, clusterele de servire pot crea blocaje de performanță, deoarece un serviciu web trebuie să recupereze fiecare marker dintr-o anumită regiune geografică din baza de date. Din fericire, această problemă poate fi rezolvată cu o strategie de stocare în cache. Pentru a înțelege mai bine cum să proiectăm și să întreținem un cache, să ne uităm la un exemplu de punct final API de hartă pe care l-am creat pentru aplicația Playsports.

O problemă de scalare și o soluție naivă

În harta Playsports, fiecare marcaj reprezintă o facilitate sportivă. Punctul final API al hărții trebuie să returneze o listă de marcatori și grupuri de marcatori, având în vedere un nivel de zoom și o casetă de delimitare.

Dacă numărul de markeri este suficient de mic, putem încărca toți markerii din caseta de delimitare din baza de date, grupăm după cum este necesar și returnăm markerii și clusterele rezultate către client.

La început, numărul maxim de marcatori în orice cutie de delimitare accesibilă în Playsports a fost de ~400, rezultând o viteză finală de ~0,5 secunde. Implementarea soluției naive a fost suficientă pentru acest caz de utilizare.

Cu toate acestea, pe măsură ce numărul de markeri a crescut, ineficiența mecanismului a devenit evidentă. După ce am adăugat ~ 10.000 de noi marcatori pentru instalații sportive, viteza punctului final a scăzut la ~ 4,3 secunde sub anumite niveluri de zoom. Această rată este mult sub durata de o secundă care este în general considerată a fi întârzierea maximă acceptabilă pentru o acțiune a utilizatorului într-o aplicație mobilă.

Pentru a înțelege mai bine ineficiența soluției naive, să o analizăm în contextul interogării markerului:

1. Din baza de date, preluați toți marcatorii din caseta de delimitare . Pentru majoritatea aplicațiilor, acest pas trebuie să includă preluarea detaliilor markerului dincolo de poziționarea latitudine/longitudine. De exemplu, marcatorii Airbnb includ prețul, dacă utilizatorul a văzut deja proprietatea și dacă a marcat-o ca favorită.
2. Pe marcatorii recuperați, rulați un algoritm de grupare a hărții care încorporează nivelul de zoom.
3. Returnați clustere și markeri (detaliați) către client.

Pe măsură ce numărul de markeri crește, performanța se deteriorează în pașii 1 și 2:

• Când caseta de delimitare este suficient de mare și când mai mult de 10.000 de markeri necesită o căutare de detaliu printr-un JOIN, interogarea bazei de date încetinește dramatic (cu 1 până la 2 secunde).
• Alimentarea a 10.000 de elemente la algoritmul de grupare a hărții durează încă ~250 de milisecunde.

Presupunând o dimensiune constantă a ferestrei, atunci când o casetă de delimitare este relativ mare, nivelul de zoom este de obicei scăzut (adică micșorat mult). La niveluri scăzute de zoom, rezultatele tind să favorizeze grupurile pentru a evita aglomerarea vizuală. Astfel, cel mai mare potențial de optimizare se află în primul pas al soluției, unde sunt încărcate mii de markeri individuali. Nu avem nevoie de majoritatea acestor markeri în rezultat. Avem nevoie doar ca fiecare dintre ei să conteze pentru un grup.

Arhitectarea soluției optimizate

Soluția naivă durează mult mai mult pentru a finaliza o interogare în cel mai rău caz: o casetă de delimitare maximă într-o regiune densă de markeri. În schimb, soluția optimizată ar dura doar 73 ms, reprezentând o accelerare de ~58x. De la un nivel înalt, arată astfel:

1. Strategia de caching. Preluați marcatori și grupuri într-o casetă de delimitare dintr-un cache specific nivelului de zoom.
2. Detaliu suplimentar pentru marcaj (opțional). Îmbunătățiți marcatorii cu o sarcină utilă preluată din baza de date.
3. Întoarcerea rezultatului. Returnați markerii și clusterele clientului.

Principala complexitate constă în arhitectura cache-ului (adică primul pas).

Pasul 1: Strategia de caching

Acest pas principal constă din șase componente:

Tehnologie

Redis este o bază de date rapidă, în memorie, care este folosită în mod obișnuit ca cache. Indexarea geospațială încorporată folosește algoritmul Geohash pentru stocarea și recuperarea eficientă a punctelor de latitudine-longitudine, care este exact ceea ce avem nevoie pentru markerii noștri.

Un cache pentru fiecare nivel de zoom

Gradul de grupare a hărții (dacă sunt returnați markeri unici sau clustere) este determinat de nivelul de zoom transmis punctului final.

• Pentru niveluri de zoom ridicate (de exemplu, mărite mai aproape), rezultatul va favoriza markerii individuali, cu excepția regiunilor dense de markeri.
• Pentru niveluri de zoom scăzute (de exemplu, micșorare mult), rezultatul va favoriza clusterele, cu excepția regiunilor cu markeri rarți.

Google Maps acceptă niveluri de zoom de la zero la maximum 20, în funcție de zonă. (Intervalele acceptate de alte servicii de hărți sunt similare. De exemplu, Mapbox utilizează niveluri de zoom de la zero la maximum 23.) Deoarece aceste niveluri de zoom sunt, de asemenea, valori întregi, putem crea pur și simplu un cache separat pentru fiecare nivel de zoom.

Pentru a accepta toate nivelurile de zoom din Google Maps, cu excepția nivelului zero, care este prea mic mic, vom crea 20 de cache distincte. Fiecare cache va stoca toți markerii și clusterele pentru întreaga hartă, așa cum sunt grupați pentru nivelul de zoom pe care îl reprezintă.

Tipuri de date din cache

Fiecare cache ar stoca clustere și markeri individuali. Pentru oricare dintre tipurile de intrare, va trebui să completăm mai multe câmpuri:

Cu toate acestea, Redis permite utilizatorilor să stocheze doar locația, plus un singur șir, ca valoare într-un set geospațial. Pentru a ocoli această restricție, serializăm câmpurile de mai sus într-un șir JSON. Apoi folosim acest șir ca valoare în Redis. Dimensiunea maximă atât a cheilor, cât și a valorilor în Redis este de 512 MB, ceea ce este mai mult decât suficient pentru acest caz de utilizare.

Umplerea Cache-urilor

Pentru a umple cache-urile, recuperăm toți markerii din baza de date. Pentru fiecare nivel de zoom, executăm algoritmul de grupare a hărții. Folosim GEOADD de la Redis pentru a insera markerii și clusterele rezultate în memoria cache a nivelului de zoom corespunzător și trecem de-a lungul latitudinii și longitudinii, plus șirul JSON descris anterior.

Rularea algoritmului de grupare a hărții pe întreaga hartă în această etapă (mai degrabă decât pe o casetă de delimitare de la utilizator, la cerere) ar putea produce, teoretic, unele diferențe de margine în plasarea clusterului, dar experiența generală a utilizatorului va rămâne aceeași.

Interogarea memoriei cache

Pentru o solicitare primită, trecem caseta de delimitare dată la comanda Redis GEOSEARCH , care interogează memoria cache a nivelului de zoom dat pentru a prelua candidații marker și cluster din zonă.

Proiectarea unui plan de reîmprospătare a memoriei cache

O reîmprospătare a memoriei cache pe 20 de niveluri este costisitoare, așa că cel mai bine este să reîmprospătați cât de rar permit cerințele proiectului. De exemplu, adăugarea sau eliminarea unei facilități sportive în Playsports marchează cache-ul doar ca învechit; o lucrare cron orară, apoi reîmprospătează memoria cache, dacă este necesar. Mai multe despre acest lucru în secțiunea Cache Staleness.

Pasul 2: Detalii suplimentare pentru marcaj (opțional)

În acest moment, majoritatea aplicațiilor vor trebui să preia detalii pe baza ID-urilor de marcare individuale. Am putea face acest detaliu parte a valorilor JSON încadrate în cache, dar în multe aplicații, detaliile markerului sunt specifice utilizatorului. Deoarece există un singur cache partajat pentru toți utilizatorii, nu este posibil să stocați aceste câmpuri suplimentare acolo.

Soluția noastră optimizată preia ID-urile markerilor individuali din rezultatul cache și preia detaliile acestora din baza de date. Acum căutăm doar marcatorii individuali care au rămas după grupare. Nu vor fi prea multe dintre acestea atunci când harta este micșorat (pentru că vom avea în mare parte clustere) și nici când măriți (pentru că zona va fi mică).

În schimb, soluția naivă caută toți markerii din caseta de delimitare (și detaliile acestora) înainte de grupare. Astfel, acest pas – opțional, dar pentru multe aplicații, crucial – rulează acum mult mai rapid.

Pasul 3: returnarea rezultatului

Odată cu clusterele construite și cu markerii individuali îmbunătățiți, acum le putem livra clientului. În afară de unele cazuri marginale nesemnificative, datele rezultate sunt aproape identice cu soluția naivă, dar le putem livra mult mai rapid.

Considerații suplimentare

Acum să ne uităm la doi factori suplimentari:

Nevoile de resurse

Să presupunem că harta unei aplicații conține în total N markeri. Deoarece există până la 20 de niveluri de zoom, ar trebui să stocăm, cel mult, 20 N de elemente cache. În practică, totuși, numărul real de elemente din cache este adesea mult mai mic datorită grupării, în special la nivelurile inferioare de zoom. De fapt, numărul total de articole cache distribuite între toate cache-urile Playsports este de numai ~2N.

În plus, dacă presupunem că lungimea unei valori cache (JSON-ul stringificat) este de ~250 de caractere (o presupunere rezonabilă, cel puțin pentru Playsports) și dimensiunea șirului este de 1 octet per caracter, atunci cantitatea de stocare cache necesară pentru Valorile JSON ar fi de aproximativ 2 * N * 250 de octeți.

La această figură adăugăm structurile de date interne ale Redis pentru seturile sortate utilizate de GEOADD . Redis folosește 85 MB de memorie pentru 1 milion de perechi cheie-valoare mici, așa că putem presupune că elementele interne Redis reprezintă mai puțin de 100 de octeți per element de cache. Asta înseamnă că am putea folosi o instanță Redis de 1 GB-RAM pentru a suporta până la 1,4 milioane de markeri. Chiar și în scenariul improbabil în care marcatorii sunt răspândiți uniform pe întreaga hartă, ceea ce duce la un număr de elemente din cache aproape de 20N, N ar putea ajunge până la ~140.000. Deoarece o instanță Redis poate gestiona mai mult de 4 miliarde de chei (2 ³² , mai exact), acesta nu este un factor limitativ.

Cache Staleness

În funcție de cazul de utilizare, este posibil să nu fie suficient să reîmprospătați memoria cache doar periodic. În astfel de cazuri, am putea folosi o coadă de sarcini cu rate limitate. Ar reduce starea cache-ului, limitând în același timp numărul de reîmprospătări ale memoriei cache și, prin urmare, încărcarea sistemului.

După fiecare actualizare a bazei de date, punem în coadă un job de reîmprospătare a cache-ului. Această coadă ar limita numărul de sarcini la M pe oră. Acest compromis permite actualizări mai rapide decât o oră, menținând în același timp o sarcină relativ scăzută a sistemului (în funcție de M).

Strategiile de stocare în cache depășesc algoritmii de grupare a hărților

Soluția optimizată pentru Playsports – de peste 50 de ori mai rapidă decât soluția naivă – a funcționat bine. Ar trebui să continue să funcționeze bine, până când ajungem la 1,4 milioane de markeri sau de peste 100 de ori datele existente.

Pentru majoritatea solicitărilor de servicii web bazate pe hărți, este necesară o formă de precalculare pentru a permite scalabilitate. Tipul de tehnologie care va fi utilizat, precum și designul specific, ar depinde de cerințele afacerii. Nevoile de învechire a memoriei cache, creșterea markerilor și numărul de markeri sunt caracteristici importante de luat în considerare atunci când proiectați o soluție.

Citiți suplimentare pe blogul Toptal Engineering:

• Sondaj cu cele mai bune instrumente de cartografiere online pentru dezvoltatorii web: foaia de parcurs către foaia de parcurs
• Aventuri în programarea și dezvoltarea GPS: un tutorial geospațial