Bitmap-index i Go: sökning i vild hastighet

Inledande ord

Jag presenterade detta föredrag på engelska vid GopherCon Russia 2019 i Moskva och på ryska vid meet-up i Nizjnij Novgorod. Det handlar om bitmap-index — ett som är mindre vanligt än B-tree, men inte mindre intressant. Jag delar med mig av en inspelning från föredraget på konferensen på engelska och en texttranskription på ryska.

Vi kommer att titta på hur bitmap-index är uppbyggda, när de är bättre, när de är sämre än andra index och i vilka fall de är betydligt snabbare; se vilka populära DBMS som redan har bitmap-index; försöka skriva vårt eget i Go. Som "dessert" kommer vi att använda färdiga bibliotek för att skapa vår supersnabba specialiserade databas.

Jag hoppas verkligen att mitt arbete kommer att vara användbart och intressant för er. Då kör vi!

Introduktion

Hej alla! Klockan är sex på kvällen, vi är alla supertrötta. En utmärkt tid att prata om tråkig teori kring databasindex, eller hur? Oroa er inte, jag har några rader källkod här och där. 🙂

Om vi ska vara seriösa är föredraget fyllt med information och vi har inte så mycket tid. Låt oss börja.

Idag kommer jag att prata om följande:

• vad index är;
• vad ett bitmap-index är;
• var det används och var det INTE används och varför;
• en enkel implementering i Go och lite kamp med kompileraren;
• en något mindre enkel, men mycket mer effektiv implementering i GoAssembly;
• "problem" med bitmap-index;
• befintliga implementationer.

Vad är då index?

Ett index är en separat datastruktur som vi håller och uppdaterar i tillägg till huvuddata. Den används för att påskynda sökningen. Utan index skulle en sökning kräva en fullständig genomgång av datan (en process kallad full scan), och denna process har linjär algoritmisk komplexitet. Men databaser innehåller vanligtvis enorma mängder data och linjär komplexitet är för långsam. Idealiskt sett vill vi ha logarithmisk eller konstant.

Detta är ett stort komplext ämne, fyllt med nyanser och kompromisser, men efter att ha sett på åratal av utveckling och forskningen kring olika databaser är jag beredd att påstå att det finns ett fåtal allmänt använda tillvägagångssätt för att skapa databaser.

Den första metoden innebär hierarkisk minskning av sökområdet, där sökområdet delas upp i mindre delar.

Vanligtvis gör vi detta genom att använda olika typer av träd. Ett exempel kan vara en stor låda med material i ditt skåp, som innehåller mindre lådor med material uppdelade efter olika teman. Om du behöver material kommer du förmodligen att leta efter dem i lådan som är märkt "Material", och inte i den som har ordet "Kakor" på sig, eller hur?

Den andra metoden innebär att direkt identifiera det önskade elementet eller en grupp av element. Vi gör detta i hash maps eller omvända index. Användningen av hash maps liknar det föregående exemplet, men istället för en låda med lådor har du en massa små lådor med slutliga objekt i ditt skåp.

Den tredje metoden är att eliminera behovet av sökning. Detta gör vi med hjälp av Bloom-filter eller cuckoo-filter. De första ger svar ögonblickligen, vilket befriar dig från att behöva söka.

Den sista metoden handlar om att utnyttja alla resurser som modern hårdvara ger oss. Det är just vad vi gör med bitmap-index. Ja, när vi använder dem måste vi ibland gå igenom hela indexet, men vi gör det supereffektivt.

Som jag redan nämnt är temat databasindex omfattande och fyllt med kompromisser. Det betyder att vi ibland kan använda flera metoder samtidigt: om vi behöver snabba upp sökningen ännu mer eller om vi behöver täcka alla möjliga typer av sökningar.

Idag kommer jag att prata om den minst kända metoden bland de nämnda - bitmap-index.

Vem är jag för att prata om detta ämne?

Jag arbetar som teamledare på Badoo (kanske känner du bättre till vår andra produkt - Bumble). Vi har redan över 400 miljoner användare världen över och många funktioner som arbetar med att matcha dem med den bästa partnern. Vi gör detta med hjälp av skräddarsydda tjänster, inklusive bitmap-index.

Så vad är ett bitmap-index?

Bitmap-indexar, som namnet antyder, använder bitmaps eller bitset för att implementera ett sökindex. I ett fågelperspektiv består detta index av en eller flera sådana bitmaps som representerar entiteter (som människor) och deras egenskaper eller parametrar (ålder, ögonfärg etc.), samt en algoritm som använder bitoperationer (OCH, ELLER, INTE) för att svara på sökfrågor.

Det sägs att bitmap-indexar är allra mest lämpliga och mycket effektiva för situationer där sökningar kombinerar frågor över många kolumner med låg kardinalitet (tänk dig "ögonfärg" eller "civilstånd" mot något som "avstånd från stadens centrum"). Men senare ska jag visa att de fungerar utmärkt även med kolumner med hög kardinalitet.

Låt oss titta på ett enkelt exempel på ett bitmap-index.

Tänk dig att vi har en lista över restauranger i Moskva med binära egenskaper som dessa:

• nära tunnelbanan (near metro);
• har privat parkering (has private parking);
• har terrass (has terrace);
• accepterar bokningar (accepts reservations);
• veganvänlig (vegan friendly);
• dyr (expensive).

Låt oss ge varje restaurang ett ordningsnummer som börjar på 0 och avsätta minne för 6 bitmaps (en för varje egenskap). Sedan kommer vi att fylla dessa bitmaps beroende på om restaurangen har denna egenskap eller inte. Om restaurang 4 har en terrass, kommer bit nr 4 i bitmapen "har terrass" att sättas till 1 (om det inte finns en terrass, sätts det till 0).

Nu har vi det enklaste bitmap-indexet som finns, och vi kan använda det för att svara på frågor som:

• "Visa mig restauranger som är veganvänliga";
• "Visa mig prisvärda restauranger med terrass där man kan boka bord."

Hur? Låt oss titta. Den första frågan är mycket enkel. Det vi behöver göra är att ta bitmapen "veganvänlig" och omvandla den till en lista över restauranger vars bitar är satt.


Den andra förfrågan är lite mer komplicerad. Vi behöver använda bitoperatören NOT på bitmappen "dyr", för att få en lista över prisvärda restauranger, och sedan AND:a den med bitmappen "kan boka bord" och AND:a resultatet med bitmappen "har terrass". Den resulterande bitmappen kommer att innehålla en lista över ställen som uppfyller alla våra kriterier. I det här exemplet är det endast restaurangen "Ungdom".


Det finns mycket teori här, men oroa dig inte, vi kommer snart att se koden.

Var används bitmap-index?

Om du "googlar" bitmap-index kommer 90% av svaren på ett eller annat sätt att relatera till Oracle DB. Men andra databashanteringssystem stödjer säkert också den här fantastiska funktionen, eller hur? Inte riktigt.

Låt oss gå igenom listan över huvudmisstänkta.

MySQL stöder ännu inte bitmap-index, men det finns ett förslag om att lägga till den här funktionen (https://dev.mysql.com/worklog/task/?id=1524).

PostgreSQL stöder inte bitmap-index, men använder enkla bitmaps och bitoperationer för att kombinera sökresultat från flera andra index.

Tarantool har bitset-index och stöder enkel sökning med dem.

Redis har enkla bitfält (https://redis.io/commands/bitfield) utan möjlighet till sökning.

MongoDB stöder ännu inte bitmap-index, men det finns också ett förslag om att lägga till denna funktion. https://jira.mongodb.org/browse/SERVER-1723

Elasticsearch använder bitmaps internt (https://www.elastic.co/blog/frame-of-reference-and-roaring-bitmaps).

• Men i vårt hus har vi fått en ny granne: Pilosa. Det är en ny icke-relationell databas skriven i Go. Den innehåller endast bitmap-index och bygger allt på dem. Vi kommer att prata om den lite senare.

Implementation i Go

Men varför används bitmap-index så sällan? Innan jag svarar på den frågan skulle jag vilja visa dig en implementation av ett mycket enkelt bitmap-index i Go.

Bitmaps representeras i grunden som bara bitar av data. I Go låt oss använda byte-slices för detta.

Vi har en bitmap för en restaurangegenskap, och varje bit i bitmappen anger om en viss restaurang har den egenskapen eller inte.

Vi behöver två hjälpfunktioner. Den ena kommer att användas för att fylla våra bitmaps med slumpmässiga data. Slumpmässiga, men med en viss sannolikhet för att restaurangen har varje egenskap. Till exempel anser jag att det finns väldigt få restauranger i Moskva där man inte kan boka bord, och jag tror att ungefär 20 % av ställena är lämpliga för vegetarianer.

Den andra funktionen kommer att konvertera bitmappen till en lista över restauranger.


För att svara på frågan "Visa mig billiga restauranger som har en veranda och där man kan boka bord" behöver vi två bitoperationer: NOT och AND.

Vi kan förenkla vår kod något genom att använda en mer avancerad operation AND NOT.

Vi har funktioner för var och en av dessa operationer. Båda går igenom skivor, tar motsvarande element från varje, förenar dem med en bitoperation och lägger resultatet i en resultatlista.

Och nu kan vi använda våra bitmaps och funktioner för att svara på sökfrågan.

Prestandan är inte så hög, trots att funktionerna är mycket enkla och vi sparade en del resurser genom att inte returnera en ny resultatlista vid varje funktionsanrop.

Efter att ha profilerat lite med pprof märkte jag att Go-kompilatorn missade en mycket enkel men viktig optimering: funktionsinlining.

Problemet är att Go-kompilatorn är fruktansvärt rädd för loopar som går igenom skivor och vägrar kategoriskt att inlinera funktioner som innehåller sådana loopar.

Men jag är inte rädd och kan lura kompilatorn genom att använda goto istället för en loop, precis som på gamla goda tider.

Och som ni ser, nu inlinar kompilatorn gladeligen vår funktion! I slutändan lyckas vi spara omkring 2 mikrosekunder. Inte dumt!

Det andra flaskhalsen är inte svårt att se om man noggrant tittar på assemblerutdata. Kompilatorn har lagt till en gränskontroll för skivan direkt inuti vår mest frekventa loop. Problemet är att Go är ett säkert språk, och kompilatorn är orolig för att mina tre argument (tre skivor) har olika storlekar. Det skulle annars teoretiskt kunna leda till så kallad buffertöverskridning.

Låt oss lugna kompilatorn genom att visa att alla slice har samma storlek. Vi kan göra detta genom att lägga till en enkel kontroll i början av vår funktion.

När kompilatorn ser detta hoppar den glatt över kontrollen och vi sparar ytterligare 500 nanosekunder.

Stora batchar

Okej, vi har lyckats pressa ut någon prestanda från vår enkla implementering, men detta resultat är faktiskt mycket sämre än vad som är möjligt med den aktuella hårdvaran.

Allt vi gör är grundläggande bitoperationer, och våra processorer utför dem mycket effektivt. Men tyvärr "matade" vi vår processor med väldigt små jobb. Våra funktioner utför operationer byte för byte. Vi kan enkelt finjustera vår kod så att den arbetar med 8-byte tillskott genom att använda UInt64 slices.

Som ni ser har denna lilla ändring ökat hastigheten på vårt program åtta gånger genom att öka batchstorleken åtta gånger. Vinsten kan sägas vara linjär.

Assemblerimplementation

Men det är inte slutet. Våra processorer kan arbeta med block på 16, 32 och till och med 64 byte. Sådana "bredare" operationer kallas single instruction multiple data (SIMD; en instruktion, flera data), och processen att omvandla koden så att den använder dessa operationer kallas vektorisering.

Tyvärr är Go-kompilatorn långt ifrån en mästare på vektorisering. För tillfället är det enda sättet att vektorisera kod i Go att manuellt lägga in dataoperationerna med hjälp av Go-assembler.

Go-assembler är ett konstigt djur. Du vet förmodligen att assembler är något som är starkt kopplat till den datorarkitektur du skriver för, men så är det inte i Go. Go-assembler liknar mer IRL (intermediate representation language) eller ett mellanliggande språk: det är praktiskt taget plattformsoberoende. Rob Pike hade en utmärkt med en presentation presentation om detta för några år sedan på GopherCon i Denver.

Utöver detta använder Go ett ovanligt format, Plan 9, som skiljer sig från de vedertagna formaten AT&T och Intel.

Man kan med säkerhet säga att det inte är det roligaste att skriva Go-assembler för hand.

Men lyckligtvis finns det redan två högpresterande verktyg som hjälper oss att skriva Go-assembler: PeachPy och avo. Båda verktygen genererar Go-assembler från mer hög nivå kod skriven i Python och Go respektive.

Dessa verktyg förenklar saker som registerallokering, skrivning av loopar och i allmänhet gör det enklare att komma in i världen av assemblerprogrammering i Go.

Vi kommer att använda avo, så våra program kommer att vara nästan vanliga Go-program.

Så här ser det enklaste exemplet på ett avo-program ut. Vi har en funktion main() som definierar en funktion Add() vars syfte är att addera två tal. Här finns hjälpfunktioner för att hämta parametrar efter namn och för att få ett av de lediga och lämpliga processorregistren. Varje processoroperation har en motsvarande funktion i avo, som kan ses i ADDQ. Och slutligen har vi en hjälpfunktion för att spara det resulterande värdet.

Genom att anropa go generate kommer vi att köra programmet på avo, och i slutändan kommer två filer att genereras:

• add.s med den resulterande koden i Go-assembler;
• stub.go med funktionshuvuden för att förena de två världarna: Go och assembler.

Nu när vi har sett vad och hur avo gör, låt oss titta på våra funktioner. Jag har implementerat både de skalära och vektoriserade (SIMD) versionerna av funktionerna.

Låt oss först titta på de skalära versionerna.

Som i det föregående exemplet ber vi om ett ledigt och korrekt allmänt register, vi behöver inte beräkna förskjutningar och storlekar för argumenten. Allt detta gör avo åt oss.

Tidigare använde vi etiketter och goto (eller hopp) för att öka prestandan och för att lura Go-kompilatorn, men nu gör vi detta från grunden. Poängen är att loopar är ett högre begrepp. I assembler har vi endast etiketter och hopp.

Den kvarstående koden bör redan vara bekant och förståelig. Vi emulerar en loop med etiketter och hopp, tar en liten del av data från våra två skivor, kombinerar dem med en bitoperation (AND NOT i detta fall) och lägger sedan resultatet i den resulterande skivan. Det är allt.

Så här ser den slutliga koden i assembler ut. Vi behövde inte beräkna förskjutningar och storlekar (markerade i grönt) eller hålla koll på använda register (markerade i rött).

Om vi jämför prestandan för en implementation i assembler med prestandan för den bästa implementationen i Go, kommer vi att se att de är likvärdiga. Och det är förväntat. Vi har ju inte gjort något speciellt – vi har bara återskapat vad Go-kompilatorn skulle göra.

Tyvärr kan vi inte få kompilatorn att inlinera våra funktioner skrivna i assembler. Go-kompilatorn har för närvarande inte den möjligheten, trots att efterfrågan på att lägga till det har funnits under ganska lång tid.

Det är därför det är omöjligt att få några fördelar från små funktioner i assembler. Vi måste antingen skriva stora funktioner eller använda det nya paketet math/bits, eller så måste vi undvika assembler helt.

Låt oss nu titta på de vektoriserade versionerna av våra funktioner.

För detta exempel har jag valt att använda AVX2, så vi kommer att använda operationer som arbetar med 32-byte-block. Koden har en struktur som liknar den skalära varianten: läsa in parametrar, be om ett ledigt gemensamt register, och så vidare.

En nyhet är att bredare vektoroperationer använder speciella breda register. När det gäller 32-byte-block är det registrets som har prefixet Y. Det är därför du ser funktionen YMM() i koden. Om jag hade använt AVX-512 med 64-byte-block skulle prefixet vara Z.

En andra nyhet är att jag har valt att använda en optimering som kallas loop unrolling, vilket innebär att jag gör åtta loopoperationer manuellt innan jag hoppar tillbaka till början av loopen. Denna optimering minskar antalet förgreningar i koden, och den är begränsad av antalet tillgängliga register.

Men hur är det med prestanda? Den är fantastisk! Vi har fått en acceleration på cirka sju gånger jämfört med den bästa lösningen i Go. Imponerande, eller hur?

Men även denna implementation skulle potentiellt kunna accelereras ytterligare genom att använda AVX-512, prefetching eller JIT (just-in-time kompilator) för frågeplaneraren. Men det är definitivt ett ämne för ett separat föredrag.

Problem med bitmap-index

Nu när vi har gått igenom en enkel implementation av bitmap-index i Go och en mycket mer prestandakraftig i assembler, låt oss äntligen prata om varför bitmap-index så sällan används.

I äldre vetenskapliga arbeten nämns tre problem med bitmap-index, men nyare studier och jag hävdar att dessa inte längre är aktuella. Vi ska inte gå djupt in på varje problem, men vi kommer att behandla dem ytligt.

Problemet med hög kardinalitet

Så, vi får veta att bitmap-index endast är lämpliga för fält med låg kardinalitet, det vill säga sådana som har få värden (till exempel kön eller ögonfärg), och anledningen är att den vanliga representationen av sådana fält (en bit per värde) vid hög kardinalitet skulle ta för mycket plats, och dessutom skulle dessa bitmap-index vara svagt (sällan) fyllda.


Ibland kan vi använda en annan representation, till exempel den standard som vi använder för att representera tal. Men det var verkligen introduktionen av komprimeringsalgoritmer som förändrade allt. Under de senaste decennierna har forskare och forskare kommit på ett stort antal komprimeringsalgoritmer för bitmaps. Deras huvudsakliga fördel är att vi inte behöver dekomprimera bitmaps för att utföra bitoperationer — vi kan utföra bitoperationer direkt på de komprimerade bitmaps.

På senare tid har också hybrida metoder dykt upp, som till exempel roaring bitmaps. De använder samtidigt tre olika representationer för bitmaps — själva bitmaps, arrayer och så kallade bit runs — och balanserar mellan dem för att maximera prestanda och minimera minnesanvändning.

Du kan se roaring bitmaps i många populära applikationer. Det finns redan ett stort antal implementationer för de mest olika programmeringsspråken, inklusive mer än tre implementationer för Go.

En annan metod som kan hjälpa oss att hantera hög kardinalitet kallas gruppering (binning). Tänk dig att du har ett fält som representerar en persons höjd. Höjd är ett flyttal, men vi människor tänker inte på det på det sättet. För oss spelar det ingen roll mellan en höjd på 185,2 cm och en på 185,3 cm.

Detta innebär att vi kan gruppera liknande värden i grupper inom 1 cm.

Och om vi dessutom vet att mycket få människor har en höjd lägre än 50 cm och högre än 250 cm, kan vi i princip omvandla ett fält med oändlig kardinalitet till ett fält med kardinalitet på cirka 200 värden.

Självklart, om så behövs kan vi göra ytterligare filtrering efteråt.

Problemet med hög genomströmning

Nästa problem med bitmap-index är att deras uppdatering kan vara väldigt kostsam.

Databaser måste möjliggöra uppdateringar av data samtidigt som potentiellt hundratals andra förfrågningar söker i dessa data. Vi behöver lås för att undvika problem med samtidig åtkomst till data eller andra problem med delad åtkomst. Och där det finns ett stort lås, finns det ett problem med lock contention, där detta lås blir en flaskhals.

Detta problem kan lösas eller kringgås genom sharding eller användning av versionshanterade index.

Sharding är en enkel och välkänd teknik. Du kan sharda bitmap-index precis som du shardar andra data. Istället för ett stort lås får du flera små lås och på så sätt undviker du lock contention.

Ett andra sätt att lösa problemet är att använda versionshanterade index. Du kan ha en kopia av indexet som du använder för sökning eller läsning, och en för skrivning eller uppdatering. Och med jämna mellanrum (till exempel var 100 ms eller 500 ms) duplicerar du dem och byter plats. Naturligtvis är denna metod endast tillämplig när din applikation kan fungera med ett något fördröjt sökindex.

Dessa två metoder kan användas samtidigt: du kan ha ett shardat versionshanterat index.

Mer komplexa frågor

Det sista problemet med bitmap-index är att de sägs vara dåligt lämpade för mer komplexa typer av frågor, till exempel frågor "inom intervall".

Och faktiskt, om vi tänker efter, är bitoperationer som AND, OR osv. inte riktigt lämpliga för frågor som "Visa mig hotell med priser från 200 till 300 dollar per natt".

En naiv och mycket oklok lösning skulle vara att ta resultaten för varje dollarvärde och kombinera dem med en bitoperation OR.

En något mer korrekt lösning skulle vara att använda gruppering. Till exempel, i grupper om 50 dollar. Detta skulle snabba upp vår process med 50 gånger.

Men problemet löses lika enkelt med hjälp av en representation som skapats speciellt för denna typ av frågor. Inom vetenskapliga arbeten kallas det range-encoded bitmaps.

I en sådan representation sätter vi inte bara en bit för ett visst värde (till exempel 200), utan vi anger det värdet och allt som är högre. 200 och högre. Samma sak gäller för 300: 300 och högre. Och så vidare.

Genom att använda denna representation kan vi svara på denna typ av sökfråga genom att gå igenom indexet endast två gånger. Först får vi en lista med hotell där rummet kostar mindre än 300 dollar, och sedan tar vi bort de där rumspriserna är lägre än 199 dollar. Klart.

Du kommer att bli förvånad, men även geosökningar är möjliga med hjälp av bitmap-index. Tricket är att använda en geopresentation som omger dina koordinater med en geometrisk figur. Till exempel, S2 från Google. Figuren måste kunna representeras med tre eller fler skärande linjer som kan numreras. På så sätt kan vi omvandla vår geosökning till flera ”intervall”-frågor (via dessa numrerade linjer).

Färdiga lösningar

Jag hoppas att jag har väckt ditt intresse lite och att du nu har ett användbart verktyg i din verktygslåda. Om du någonsin behöver göra något liknande, vet du vilken väg du ska titta.

Men inte alla har tid, tålamod och resurser för att skapa bitmap-index från grunden. Särskilt mer avancerade som använder SIMD, till exempel.

Lyckligtvis finns det flera färdiga lösningar som kan hjälpa dig.

Roaring bitmaps

Först finns det det som kallas roaring bitmaps-biblioteket, som jag redan nämnt. Det innehåller alla nödvändiga containrar och bitoperationer som du behöver för att skapa ett fullständigt bitmap-index.

Tyvärr använder ingen av Go-implementationerna för närvarande SIMD, vilket innebär att Go-implementationerna är mindre effektiva än de i C, till exempel.

Pilosa

En annan produkt som kan hjälpa dig är databasen Pilosa, som i grunden bara har bitmap-index. Det är en relativt ny lösning, men den vinner snabbt hjärtan.

Pilosa använder roaring bitmaps internt och ger dig möjlighet att använda dem, förenklar och förklarar alla de saker jag nämnde ovan: gruppering, range-encoded bitmaps, begreppet fält osv.

Låt oss snabbt titta på ett exempel på hur Pilosa används för att svara på en fråga som ni redan känner till.

Exemplet liknar mycket det ni har sett tidigare. Vi skapar en klient till Pilosa-servern, skapar ett index och nödvändiga fält, fyller sedan våra fält med slumpmässiga data med sannolikheter och utför slutligen den bekanta förfrågan.

Efter detta använder vi NOT på fältet "expensive", sedan korsar vi resultatet (eller AND-ar) med fältet "terrace" och fältet "reservations". Och till slut får vi det slutgiltiga resultatet.

Jag hoppas verkligen att inom en snar framtid kommer också databaser som MySQL och PostgreSQL att få denna nya typ av index — bitmap-index.

Slutsats

Om du ännu inte har somnat, tack. Jag var tvungen att snabbprata om många ämnen på grund av tidsbegränsningar, men jag hoppas att presentationen varit nyttig och kanske till och med motiverande.

Det är bra att känna till bitmap-index, även om du just nu kanske inte behöver dem. Låt dem vara ytterligare ett verktyg i din verktygslåda.

Vi har sett olika trick för att öka prestandan för Go och de saker som Go-kompilatorn fortfarande inte hanterar särskilt bra. Och detta är definitivt något varje Go-programmerare bör veta.

Det är allt jag ville berätta. Tack!

Källa: habr.com