Preporuke za Geosharded dio 1: Oštravanje pristupa

Autori: Frank Ren | Direktor, Backend inženjering, Xiaohu Li | Voditelj, Backend inženjering, Devin Thomson | Olovo, Backend inženjer, Daniel Geng | Backend inženjer

Posebna zahvala: Timothy Der | Stariji inženjer za pouzdanost web mjesta, za operativnu i implementacijsku podršku

Uvod

U najranijim fazama Tinterovog eksplozivnog rasta inženjerski tim utvrdio je da bi pretraga bila jaka komponenta za podršku preporukama u stvarnom vremenu. Od tada je važan dio sustava preporuka Tinder.

Tinder arhitektura pretraživanja bila je vrlo jednostavna: jedan Elasticsearch skup s jednim indeksom i zadanih pet komada. Radili smo s tim godinama, dodajući više replika i moćnije čvorove prema potrebi. Kako je vrijeme odmicalo, krhotine su postajale sve veće i dodavane su više replika da bi latencija bila niska. Znali smo da naš dizajn više neće odgovarati našim očekivanjima od skaliranja kada smo stigli do točke u kojoj koristimo veliki broj moćnih čvorova, a pritom smo još uvijek vidjeli veliko korištenje CPU-a i visoke troškove infrastrukture.

Slučajevi upotrebe Tinder-a temelje se na lokaciji, s maksimalnom udaljenošću od 100 milja. Kad služite korisniku u Kaliforniji, nema potrebe uključivati ​​korisnike u London. Uz to, veličina indeksa značajno utječe na sposobnost indeksiranja i pretraživanja te na uspješnost testova u velikoj mjeri otkrili smo da se učinkovitost linearno povećava kada se veličina indeksa smanjuje. Ako možemo stvoriti više krhotina ograničenih lokacijom (ili „geosharded“), svaki bi podindeks bio manji i povećao radne učinke. Imajući to na umu, postalo je pitanje: koji je najbolji način da to učinite?

Jedna kratka napomena o pojmovima: sama elastična pretraga može imati više čvorova podataka, koji se često nazivaju i komadići. Da bismo se razlikovali u ovom članku, koristimo „geoshard“ za predstavljanje oštrenja koje smo dodali povrh njega, a „shard“ rezerviramo za glagol ili za generički shard.

Oštri pristup

Započnimo s jednostavnim slučajem: sve korisnike (na globalnoj razini) stavite u jedan jedinstveni indeks pretraživanja. Za korisnika koji žive u Los Angelesu upit za pretraživanje potražit će ovaj jedinstveni indeks koji u sebi sadrži cjelokupnu korisničku bazu. Ljudi koji žive na istočnoj obali ili čak u nekoj drugoj zemlji povećali bi veličinu indeksa, što se negativno utječe na izvedbu upita, a korisniku u Los Angelesu ne daje vrijednost.

To ukazuje na put za optimizaciju: ako podatke možemo podijeliti na način da bi upit dotaknuo samo potrebni indeks koji sadrži minimalne dokumente koji su važni za upit, količina izračuna bila bi narednih razmjera manja i upit bi biti mnogo brži.

Srećom za Tinderin slučaj, upiti su geografski ograničeni i imaju ograničenje od 100 milja. To se, naravno, temelji na geografskom rješenju: spremanju korisnika koji su fizički blizu jedni drugima u isti dio.

Dobar pristup obrade treba osigurati da se proizvodno opterećenje geosharda izbalansira; u protivnom, to će imati problem s kratkim hlačama. Ako možemo kvantificirati opterećenje svakog geosharda („rezultat opterećenja“), vrijednosti rezultata opterećenja za sve geosharde trebale bi biti približno iste. Očito, ako imamo premalo komada (samo 1 komad) ili previše komada (1 milijun komada) da bi bilo učinkovito, moramo pronaći pravi broj komada.

Izdanje ravnoteže

Jedan jednostavan pristup bila bi podjela mape svijeta u rešetke ravnomjernim raspoređivanjem širine i dužine:

To očito neće uspjeti. Neki geoshardi u oceanu bit će prazni bez korisnika, dok bi drugi geoshardi u Europi mogli sadržavati nekoliko velikih gradova. Geoshardi će biti vrlo neuravnoteženi što će rezultirati vrućim komadima tijekom rada. Ova projekcija zemljovida vrlo je nagnuta u blizini zemaljskih stupova, razlika stvarnog zemljopisnog područja obuhvaćenog ćelijom između ekvatora i pola mogla bi biti tisuću puta, tako da moramo pronaći bolju projekciju.

Učitavanje rezultata

Kako možemo bolje uravnotežiti geosharde? Kao i u bilo kojoj vrsti problema s optimizacijom, ne možete optimizirati ono što ne možete mjeriti.

Postoji više načina izračunavanja opterećenja:

  • Broj jedinstvenih korisnika
  • Broj aktivnih korisnika
  • Korisnikov upiti broje se za sat vremena
  • Kombinacija gore navedenog

Radi jednostavnosti, recimo da koristimo jedinstveno brojanje korisnika: to je jednostavno izračunati i lako se agregirati (samo napraviti zbroj). Sada se ravnoteža geosharding konfiguracije s N dijelovima može predstaviti kao standardno odstupanje opterećenja:

Ravnoteža (Shard1, Shard2,…, ShardN) = Standardno odstupanje (Load-score-of-shard1,…)

Konfiguracija geoshardiranja s minimalnim standardnim odstupanjem bila bi najbolje izbalansirana. Korištenjem gornjeg jednostavnog geosharda kao primjera, kombiniranjem svih geosharda koji se nalaze u oceanu geoshard će očito biti uravnoteženiji. Bolji pristup bit će opisan u nastavku o algoritmu geoshardinga.

Veličina oštrice

Kako možemo odrediti koliko komada bismo trebali imati za određeni mehanizam za oštrenje? Postoji nekoliko razloga:

  • Geoshard migracija: korisnici se kreću (putuju na posao, šetaju, putuju itd.), A kad korisnik prijeđe granice geosharda, sustav mora premjestiti korisnika u novi indeks i ukloniti ga iz prethodnog. Nadalje, ove operacije nisu atomske, pa će više poteza rezultirati s više nedosljednosti u sustavu. Na kraju to možemo učiniti dosljednim, ali ogromna količina privremenih nedosljednosti mogla bi biti problematična.
  • Upiti više geosharda: Tinder ograničava korisnikov radijus pretraživanja na najviše 100 milja, tako da ako je geoshard 100 kvadratnih milja, jedan bi upit trebao pogoditi 314 geosharda. S ovolikim zahtjevima za paralelno pretraživanje indeksa za jedan zahtjev korisnika, pateće P99, pa čak i P90. Tako geoshardi ne mogu biti premali.
  • Gustoća korisnika: u nekim je područjima baza korisnika zaista gusta, kao što je New York City ili London. U ovim područjima rezultat opterećenja je visok za fizički male geosharde.
"Iz tih razloga, pronalazak prave veličine geosharda također je izazov."

Na temelju testa opterećenja i raspodjele rezultata opterećenja otkrili smo da 40–100 geosharda širom svijeta rezultira dobrom ravnotežom performansi P50, P90, P99 pod Tinderovim prosječnim opterećenjem. Ova analiza uzima u obzir čimbenike kao što su provjera zahtjeva i paralelizacija zahtjeva.

S2 Cell & Geosharding algoritam

Nakon sveobuhvatnih istraživanja o geo knjižnicama, sletili smo na Google S2. S2 se temelji na Hilbertovoj krivulji, krivulji popunjavanja prostora koja čuva prostorni lokalitet: dvije točke koje su blizu Hilbertove krivulje su blizu fizičkog prostora. Svaki najmanji klon Hilbertove krivulje je ćelija, a 4 susjedne stanice tvore veću ćeliju, pa je to kvadratna struktura.

** (slika adaptirana od Christian S. Perone)

Zamislite sada da u središtu zemlje postoji svjetlost. Ona projicira površinu globusa u kocku mandarina gdje je svako lice kocke ispunjeno Hilbertovom krivuljom, a svaka najmanja ćelija predstavlja malo zemaljsko područje - to otprilike glasi na način kako S2 radi preslikavanje iz S2 ćelije. Primijetite da će doći do izobličenja na rubu, posebno na uglovima - S2 vrši nelinearnu transformaciju kako bi bio siguran da je bilo koja projicirana stvarna veličina ćelije na Zemljinoj površini približno ista. Više pojedinosti može se naći u Googleovim slajdovima S2.

(slika prilagođena iz Sidewalk Labs)

S2 ima sljedeće prednosti:

  • Stanice se nalaze na istoj mapi s približno istom veličinom područja na Zemljinoj površini. Za usporedbu, Geohash je vrlo iskrivljen kada se približi Zemljim polovima.
  • To je zrela i stabilna knjižnica s podrškom za glavne jezike koje koriste Tinder-ovi pozadinski poslužitelji (Java i NodeJS).
  • 2D Hilbert krivulja je četvero stablo, što agregaciju čini prilično laganom. Ovo je vrlo prikladno za izračunavanje opterećenja, budući da možete održavati ocjenu opterećenja u nižim razinama i prema potrebi agregirati na višu razinu.
  • Biblioteka ima ugrađenu funkcionalnost za mapiranje lokacije (lat, duga) => S2 ćelija ili za pokrivanje zemljopisnog područja poput poligona ili kruga sa S2 ćelijama.
  • S2 ima podršku za stanice različitih veličina, u rasponu od kvadratnih centimetara do milja.

S2 ima razinu stanica u rasponu od razine 0 (33 milijuna četvornih milja) do razine 30 (1 kvadratni centimetar). Nakon što smo procijenili statistiku upotrebe Tinder-a, ustanovili smo da se većina postavki korisnika nalazi u krugu od 50 milja. Kao rezultat toga, S2 Level-7 (~ 45 milja) i Level-8 (~ 22,5 milje, vidi S2 statistiku) su najprikladniji za Tinderov slučaj upotrebe.

Kako sada stvaramo geosharde?

Primijetite da se sa S2 cijeli globus može preslikati u liniju S2 stanica. Zamislite sada da svaka ćelija sadrži vodu proporcionalnu njihovoj količini opterećenja (npr. Ocjena 10 sadrži 10 ml vode, a ona sa ocjenom 100,5 sadrži 100,5 ml). Držite spremnik veličine 1000ml, hodate duž linije ćelija i ulijevate svu vodu u ćeliju kroz koju ste prošli u spremnik, sve dok niste sreli ćeliju koja sadrži dovoljno vode koja će spremnik preliti.

Sada svu vodu iz spremnika prelijte u vrećicu i nastavite. Ponavljajte postupak sve dok ne stignete do kraja linije - napravili ste mnogo vrećica, a svaka je vrećica geoshard. Budući da S2 (i ispod Hilbertove krivulje) čuva lokalitet, stanice unutar tako dobivenog sjemena bit će geografski zajedno.

S obzirom na sve ćelije s unaprijed izračunanim rezultatima opterećenja, veličina spremnika je jedini faktor koji utječe na rezultate rezanja.

Ako nabrojimo sve moguće veličine spremnika i izračunamo standardno odstupanje svake konfiguracije izoštravanja, onaj s najmanjim standardnim odstupanjem bit će najuravnoteženija konfiguracija geoshardiranja koju tražimo.

Algoritam za pronalaženje najbolje geoshardove konfiguracije izgleda ovako za S2 Level-7 (pseudo-kodni pseudo kod):

Zatim ponovite isto za S2 L8. Na kraju postupka generirat će se najbolje uravnotežena konfiguracija geoshardiranja s obzirom na metodu. Vizualizacija generiranog geoshard karata može izgledati na sljedećem grafikonu. Možete vidjeti da Hilbert krivulja čuva lokalitet vrlo dobro, tako da su geoshardi uglavnom fizički zajedno, a geoshard fizički velik za područja s malim opterećenjem.

** (55-geoshard primjer zasnovan na hipotetskim podacima, nadahnuo Leaflet) **

Generirani geoshardi pohranjuju se kao presjek json-a:

(Primjetite da razina S2 stanice 16 i više može biti predstavljena ili ID-om LONG broja ili nizom tokena. Ali različite biblioteke na jezicima kao što je Node / Java / Go generiraju različite bajtove LONG id-a za istu ćeliju u isto vrijeme, reprezentacija tokenskih tokena je dosljedna u svim bibliotekama, tako da smo odabrali token za predstavljanje S2 ćelije.)

Korištenje geoshard mapiranja

Potrebno je razmotriti dvije vrste upotrebe:

  • Indeksiranje: korisniku dodijeljeno (lat, dugo), preslikati ga u geoshardu
  • Upit: s obzirom na krug (lat, dugačak, polumjer) dobili smo sve geosharde s kojima moramo ispitivati

S2 knjižnice pruža dvije funkcije:

  • S obzirom na točku lokacije (lat, duga), vratite S2 ćeliju koja je sadrži
  • S obzirom na krug (lat, dug, polumjer) vratite sve S2 ćelije koje su dovoljno samo da pokrijete taj krug

Primijetite da već imamo preslikavanje iz S2 ćelije u geoshard u gornjoj konfiguraciji mapiranja oštrica. Tako:

  • Za zahtjev za indeksiranje, usluga je prvo pretvara u S2 ćeliju, a zatim pomoću preslikavanja ombre preslikajte S2 ćeliju u geoshard
  • Za zahtjev za upit, usluga dobiva S2 ćelije koje su dovoljno samo da pokrije krug upita pomoću S2 knjižnice, a zatim preslikava sve S2 ćelije na geosharde pomoću mapiranja oštrine

Sljedeća slika prikazuje kako funkcionira mapiranje upita. Jasno je da će ovaj upit s krugom od 100 milja potražiti samo 3 od 55 geosharda.

(Upit: krug => S2 ćelije => geoshards)

O Reshardingu

U praksi smo ostavili dovoljno prostora tako da neće biti potrebe za ponovnim otkrivanjem godina. No po potrebi, ponovno izmjenjivanje može se obaviti ručno pokretanjem dva paralelna skupa indeksa s dva preslikavanja dijelova u isto vrijeme, a zatim izvanmrežno ponovno indeksirati sve postojeće dokumente na nove geoshard indekse, nakon čega slijedi presjek i čišćenje.

takeaways

Prema našem mjerenju u proizvodnji, geosharded indeks pretraživanja može raditi 20 puta više izračuna u odnosu na pojedinačni indeks. Izvrsna je stvar što se gore prikazana metoda može primijeniti na sve proračune koji se temelje na lokaciji i mogu se prikupiti.

Ključni dijelovi:

  • Za uslugu utemeljenu na lokaciji koja se suočava s izazovom opterećenja, razmislite o geosardingu
  • S2 je dobra knjižnica za geosharding, a Hilbert krivulje su fantastične za očuvanje lokaliteta
  • Razmislite kako izmjeriti opterećenje (rezultat opterećenja) za bolju ravnotežu opterećenja između komadića

Jeste li zainteresirani za izgradnju rješenja složenih problema poput ovih na globalnoj razini? Uvijek tražimo vrhunske talente i inventivne rješavatelje problema koji bi se pridružili našem inženjerskom timu. Pogledajte naše otvore ovdje!