Geosharded rekommendationer Del 1: Sharding Approach

Författare: Frank Ren | Direktör, Backend Engineering, Xiaohu Li | Manager, Backend Engineering, Devin Thomson | Lead, Backend Engineer, Daniel Geng | Backend Engineer

Speciellt tack till: Timothy Der | Senior Site Relibility Engineer, för driftsstöd och implementeringsstöd

Introduktion

I de tidigaste stadierna av Tinders explosiva tillväxt identifierade ingenjörsteamet att sökningen skulle vara en stark komponent för att stödja rekommendationer i realtid. Sedan dess har det varit en viktig del av Tinder-rekommendationssystemet.

Tinders sökarkitektur var ganska enkel: ett Elasticsearch-kluster med ett index och fem skärvor som standard. Vi arbetade med detta i flera år och lägger till fler kopior och kraftfullare noder efter behov. Allteftersom tiden gick blev skärmen större och fler kopior lades till för att hålla latensen låg. Vi visste att vår design inte längre skulle uppfylla våra skalförväntningar när vi nådde en punkt där vi använde ett stort antal kraftfulla noder medan vi fortfarande såg hög CPU-användning och motsvarande höga infrastrukturkostnader.

Tinders rekommendationsanvändningsfall är platsbaserade med ett maximalt avstånd på 100 mil. När du betjänar en användare i Kalifornien finns det inget behov av att inkludera användarna i London. Dessutom påverkar indexstorleken signifikant indexeringen och sökkapaciteten och prestandan i tester i stor skala. Vi fann att prestandan ökar linjärt när indexstorleken minskar. Om vi ​​kan skapa fler skärvor avgränsade av plats (eller "geosharded") som skulle göra varje subindex mindre och borde öka prestandan. Med denna kunskap i åtanke blev frågan då: vad är det bästa sättet att göra det?

En snabb anteckning om termerna: Elasticsearch i sig kan ha flera datanoder, ofta benämnda skär. För att differentiera i den här artikeln använder vi "geoshard" för att representera skärning som vi lagt till ovanpå och reservera "skärva" för ett verb eller för att hänvisa till en generisk skärv.

Skärmningsstrategi

Låt oss börja med det enkla fallet: placera alla användare (globalt) i ett enda sökindex. För en användare som bor i Los Angeles skulle en sökfråga leta upp detta enda index, som har hela användarbasen i sig. De människor som bor på östkusten eller till och med i ett annat land skulle öka indexstorleken, vilket negativt påverkar frågeställningen medan de inte ger något värde för användaren i Los Angeles.

Detta indikerar en väg för optimering: om vi kan dela upp data på ett sätt som en fråga bara skulle beröra det nödvändiga indexet som innehåller de minsta dokumenten som är viktiga för frågan, skulle beräkningen vara storleksordningar mindre och frågan skulle vara mycket snabbare.

Lyckligtvis för Tinders fall är frågor geo-begränsade och har en gräns på 100 mil. Detta lämnar sig naturligtvis till en lösning baserad på geografi: lagring av användare som är fysiskt nära varandra i samma skärv.

En bra skärmningssätt bör säkerställa att geoshardarnas produktionsbelastning är balanserad. annars kommer det att ha en hot-shard-problem. Om vi ​​kan kvantifiera lasten för varje geoshard ("last score"), bör belastningsvärdena för alla geoshards vara ungefär desamma. Självklart, om vi har för få skärvor (endast 1 skär) eller för många skär (1 miljon skär) för att den ska vara effektiv måste vi hitta rätt antal skär.

Balansemission

Ett enkelt tillvägagångssätt skulle vara att dela upp världskartan i rutnät genom jämnt avstånd mellan latitud och longitud:

Detta fungerar helt klart inte bra. Vissa geosharder i havet kommer att vara tomma utan användare, medan andra geoshards i Europa kan innehålla flera stora städer. Geoshardarna kommer att vara mycket obalanserade vilket resulterar i heta skärvor när de körs i produktion. Denna världskartprojektion är mycket sned nära Jordens poler, skillnaden mellan det verkliga geografiska området som täcks av en cell mellan ekvatorn och polen kan vara tusen gånger, så vi måste hitta en bättre projektion.

Load Score

Hur kan vi bättre balansera geoshardarna? Liksom i alla typer av optimeringsproblem kan du inte optimera det du inte kan mäta.

Det finns flera sätt att beräkna belastningen:

  • Unikt användarantal
  • Aktivt användarantal
  • Användarens frågor räknas på en timme
  • Kombination av ovanstående

För enkelhetens skull, låt oss säga att vi använder unikt användarantal: det är enkelt att beräkna och enkelt att samla (bara göra en summa). Nu kan balansen i en geosskyddskonfiguration med N-skärvor representeras som standardavvikelse för belastning:

Balans (Shard1, Shard2, ..., ShardN) = Standardavvikelse (Load-score-of-shard1, ...)

Geosharding-konfigurationen med minimal standardavvikelse skulle vara den bästa balanserade. Genom att använda ovanstående enkla geosharding som exempel, genom att kombinera alla geoshardar som finns i havet kommer geoshardt uppenbarligen att vara mer balanserat. En bättre metod kommer att beskrivas i avsnittet om geosharding-algoritmer nedan.

Skärmstorlek

Hur kan vi bestämma hur många skärvor vi ska ha för en viss skärmningsmekanism? Det finns några överväganden:

  • Geoshard migration: Användare flyttar sig runt (pendlar, går runt, reser etc.), och när en användare passerar geoshard gränser måste systemet flytta användaren till det nya indexet och ta bort användaren från tidigare. Dessutom är dessa operationer inte atomära så fler drag kommer att resultera i fler inkonsekvenser i systemet. Så småningom kan vi göra det konsekvent, men en enorm mängd tillfälliga inkonsekvenser kan vara problematiska.
  • Fråga ifrån flera geoshards: Tinder begränsar användarnas sökradie till maximalt 100 miles, så om geoshardet är 100 kvadrat miles skulle en fråga behöva träffa 314 geoshards. Med dessa många parallella indexsökningar för en användarförfrågan kommer P99 och till och med P90-latensen att drabbas. Så geosharder kan inte vara för små.
  • Användartäthet: i vissa områden är användarbasen verkligen tät, till exempel i New York eller London. I dessa områden är belastningsgraden hög för fysiskt små geosharder.
"Av dessa skäl är det också en utmaning att hitta rätt geoshardstorlek."

Baserat på vårt belastningstest och belastningsresultatfördelning fann vi att 40–100 geosharder runt om i världen resulterar i en bra balans på P50, P90, P99 prestanda under Tinders genomsnittliga produktionsbelastning. Denna analys tar hänsyn till faktorer som förfrågan om fanout och parallellisering.

S2 Cell & Geosharding Algoritm

Efter omfattande forskning om geobibliotek landade vi på Google S2. S2 är baserat på Hilbert-kurvan, en rymdfylld kurva som bevarar den rumsliga lokaliteten: två punkter som ligger nära Hilbert-kurvan är nära i det fysiska utrymmet. Varje minsta Hilbert-kurvklon är en cell, och fyra intilliggande celler bildar en större cell, så det är en fyrbilsstruktur.

** (bild anpassad från Christian S. Perone)

Föreställ dig nu att det finns ett ljus i mitten av jorden. Den projicerar jordens yta till en tangerin kub där varje sida av kuben är fylld med Hilbert-kurva, och varje minsta cell representerar ett litet område på jorden - det är ungefär så S2 gör kartläggningen från en S2-cell. Observera att det kommer att bli snedvridning på kanten, speciellt på hörnen - S2 gör en icke-linjär transformation för att se till att alla projicerade cellers faktiska storlek på jordens yta är ungefär densamma. Mer information finns i Googles S2-bilder.

(bild anpassad från Sidewalk Labs)

S2 har följande fördelar:

  • Celler på samma nivåskarta till ungefär samma storlek på ytan på jordens yta. Jämförelsevis är Geohash väldigt sned när man kommer nära jordens poler.
  • Det är ett moget och stabilt bibliotek med stöd för huvudspråk som används av Tinders backend-servrar (Java och NodeJS).
  • En 2D Hilbert-kurva är en fyrhjuling, vilket gör aggregeringen ganska enkel. Detta är mycket bekvämt när du beräknar lastpoäng eftersom du kan upprätthålla en lastpoäng i lägre nivåer och aggregera till en högre nivå vid behov.
  • Biblioteket har inbyggd funktionalitet för att kartlägga en plats (lat, lång) => S2-cell, eller täcka ett geografiskt område såsom en polygon eller cirkel med S2-celler.
  • S2 har stöd för celler i olika storlekar, från kvadratcentimeter till mil.

S2 har cellnivåer från nivå-0 (33 miljoner kvadrat miles) till nivå-30 (1 kvadrat centimeter). Efter att ha utvärderat Tinder-användningsstatistiken fann vi att de flesta användares inställningar ligger inom ett område på 50 mil. Som ett resultat är S2 Level-7 (~ 45 miles) och Level-8 (~ 22.5 miles, se S2-statistik) bäst lämpade för Tinders användningsfall.

Hur skapar vi geoshards nu?

Lägg märke till att med S2 kan hela världen mappas till en rad S2-celler. Föreställ dig nu att varje cell innehåller vatten som är proportionellt mot deras belastningsscore (t.ex., belastningsscore 10 innehåller 10 ml vatten, de med belastningsscore 100,5 innehåller 100,5 ml). Du håller en behållare med storlek 1000 ml, går längs linjen med celler och häller allt vatten i cellen som du passerade förbi behållaren tills du träffade en cell som innehåller tillräckligt med vatten som får behållaren att flyta över.

Häll nu allt vatten ur behållaren i en påse och fortsätt. Upprepa processen tills du kommer till slutet av linjen - du har gjort många väskor, varje påse är i själva verket en geoshard. Eftersom S2 (och den underliggande Hilbert-kurvan) bevarar lokalitet kommer cellerna i ett skärv som genereras på detta sätt geografiskt tillsammans.

Med tanke på alla celler med förberäknade belastningsresultat är behållarstorleken den enda faktorn som påverkar skärmningsresultaten.

Om vi ​​räknar upp alla möjliga behållarstorlekar och beräknar standardavvikelsen för varje skärvningskonfiguration, är den med minsta standardavvikelse den mest balanserade geoshardingkonfigurationen vi letar efter.

Algoritmen för att hitta den bästa geoshardkonfigurationen ser ut så här för S2 Level-7 (pythonliknande pseudokod):

Upprepa sedan samma sak för S2 L8. I slutet av processen kommer det att generera den bästa balanserade geosharding-konfigurationen med metoden. En visualisering av genererad geoshard-mappning kan se ut som följande graf. Du kan se Hilbert-kurvan bevarar lokaliteten riktigt bra, så geosharder är mestadels fysiskt tillsammans, och geoshardet är fysiskt stort för områden med låg belastning.

** (ett 55-geoshardt exempel baserat på hypotetiska data, inspirerad av Leaflet) **

De genererade geoshardarna lagrar som en skärdapning som json:

(Lägg märke till att S2-cellnivå 16 och högre kan representeras av antingen ett LONG-nummer-ID eller ett strängtoken. Men olika bibliotek på språk som Node / Java / Go genererar olika LONG-id-byte för samma cell, på samma gång, string token-representation är konsekvent över dessa bibliotek, så vi har valt att använda token för att representera en S2-cell.)

Använd geoshard-mappning

Det finns två typer av användningsfall som vi måste överväga:

  • Indexering: ges en användare på (lat, long), kartlägg den till en geoshard
  • Fråga: med tanke på en cirkel (lat, lång, radie), få ​​alla geoshards som vi behöver fråga med

S2-bibliotek har två funktioner:

  • Med tanke på en platspunkt (lat, lång) ska du returnera S2-cellen som innehåller den
  • Med en cirkel (lat, lång, radie) ska du returnera alla S2-celler som är tillräckligt för att täcka cirkeln

Lägg märke till att vi redan har en kartläggning från S2-cell till geoshard i ovanstående skärmkartningskonfiguration. Så:

  • För en indexeringsbegäran konverterar tjänsten först den till en S2-cell, använd sedan skärmkartläggningen för att kartlägga S2-cellen till en geoshard
  • För en frågeförfrågan får tjänsten S2-celler som är tillräckligt för att täcka frågecirkeln med S2-biblioteket, och sedan kartlägga alla S2-celler till geosharder med skärmkartläggningen

Följande bild visar hur frågekartläggningen fungerar. Det är uppenbart att den här frågan med en 100 mil cirkel bara kommer att slå upp 3 av 55 geoshards.

(Fråga: Circle => S2 Cells => geoshards)

Om Resharding

I praktiken har vi lämnat tillräckligt med utrymme så att det inte kommer att behöva reshard på flera år. Men vid behov kan återskärning göras manuellt genom att köra två parallella index-uppsättningar med två skärvkartläggningar samtidigt, sedan offlineindexierar alla befintliga dokument till nya geoshard-index följt av en cutover och sanering.

takeaways

Enligt vår mätning i produktionen kan det geoshärdade sökindex hantera 20 gånger fler beräkningar jämfört med inställningen av ett enda index. Det fantastiska är att metoden som visas ovan kan tillämpas på alla beräkningar som är platsbaserade och aggregerbara.

Viktiga takeaways:

  • För en platsbaserad tjänst inför belastningsutmaning, fundera på geosharding
  • S2 är ett bra bibliotek för geosharding, och Hilbert-kurvor är fantastiska för att bevara lokaliteten
  • Överväg hur man mäter belastning (lastpoäng) för bättre lastbalans mellan skärvor

Är du intresserad av att bygga lösningar på komplexa problem som dessa i global skala? Vi letar alltid efter högsta talang och uppfinningsrika problemlösare för att gå med i vårt ingenjörsteam. Kolla in våra öppningar här!