Bitmappsindex i Go: sök med vild hastighet

introduktion

Jag gav den här rapporten på engelska vid GopherCon Russia 2019-konferensen i Moskva och på ryska vid ett möte i Nizhny Novgorod. Vi pratar om ett bitmappsindex - mindre vanligt än B-träd, men inte mindre intressant. Delning inspelning tal vid konferensen på engelska och textutskrifter på ryska.

Vi kommer att titta på hur ett bitmappsindex fungerar, när det är bättre, när det är sämre än andra index, och i vilka fall det är betydligt snabbare än dem; Låt oss se vilka populära DBMS som redan har bitmappsindex; Låt oss försöka skriva vårt eget i Go. Och "till efterrätt" kommer vi att använda färdiga bibliotek för att skapa vår egen supersnabba specialiserade databas.

Jag hoppas verkligen att mina verk kommer att vara användbara och intressanta för dig. Gå!

Inledning

http://bit.ly/bitmapindexes
https://github.com/mkevac/gopherconrussia2019

Hej alla! Klockan är sex på kvällen och vi är alla supertrötta. Bra tid att prata om tråkig databasindexteori, eller hur? Oroa dig inte, jag har ett par rader med källkod här och där. 🙂

Bortsett från alla skämt, rapporten är proppfull av information, och vi har inte mycket tid. Så låt oss börja.

Idag ska jag prata om följande:

• vad är index;
• vad är ett bitmappsindex;
• var den används och var den INTE används och varför;
• enkel implementering i Go och lite kamp med kompilatorn;
• något mindre enkel, men mycket mer produktiv implementering i Go assembler;
• "problem" med bitmappsindex;
• befintliga implementeringar.

Så vad är index?

Indexet är en separat datastruktur som vi underhåller och uppdaterar utöver huvuddatan. Den används för att påskynda sökningen. Utan index skulle sökning kräva att man gick igenom data helt (en process som kallas full scan), och denna process har linjär algoritmisk komplexitet. Men databaser innehåller vanligtvis enorma mängder data och den linjära komplexiteten är för långsam. Helst skulle vi få en logaritmisk eller konstant.

Det här är ett enormt komplext ämne, fyllt med finesser och avvägningar, men efter att ha tittat på årtionden av databasutveckling och forskning är jag villig att säga att det bara finns ett fåtal allmänt använda metoder för att skapa databasindex.

Det första tillvägagångssättet är att hierarkiskt minska sökutrymmet, dela upp sökutrymmet i mindre delar.

Vi brukar göra detta med olika sorters träd. Ett exempel skulle vara en stor låda med material i din garderob som innehåller mindre lådor med material uppdelade i olika ämnen. Om du behöver material, kommer du förmodligen att leta efter dem i en ruta som säger "Material" snarare än en som säger "Cookies", eller hur?

Det andra tillvägagångssättet är att omedelbart välja önskat element eller grupp av element. Vi gör detta i hashkartor eller omvända index. Att använda hashkartor är väldigt likt det tidigare exemplet, men istället för en låda med lådor har du en massa små lådor med sista föremål i din garderob.

Det tredje tillvägagångssättet är att eliminera behovet av sökning. Det gör vi med hjälp av Bloom-filter eller gökfilter. De första ger ett svar direkt, vilket gör att du slipper söka.

Det sista tillvägagångssättet är att fullt ut utnyttja all kraft som modern hårdvara ger oss. Det är precis vad vi gör i bitmappsindex. Ja, när vi använder dem behöver vi ibland gå igenom hela indexet, men vi gör det supereffektivt.

Som jag sa, ämnet databasindex är stort och fullt av kompromisser. Det gör att vi ibland kan använda flera tillvägagångssätt samtidigt: om vi behöver påskynda sökningen ännu mer, eller om vi behöver täcka in alla möjliga söktyper.

Idag kommer jag att prata om det minst kända tillvägagångssättet för dessa - bitmappsindex.

Vem är jag att tala om detta ämne?

Jag arbetar som teamleader på Badoo (du kanske är mer bekant med vår andra produkt, Bumble). Vi har redan mer än 400 miljoner användare runt om i världen och många funktioner som väljer den bästa matchningen för dem. Vi gör detta med hjälp av anpassade tjänster, inklusive bitmappsindex.

Så vad är ett bitmappsindex?

Bitmappsindex, som namnet antyder, använder bitmappar eller bituppsättningar för att implementera ett sökindex. Ur fågelperspektiv består detta index av en eller flera sådana bitmappar som representerar alla enheter (som människor) och deras egenskaper eller parametrar (ålder, ögonfärg, etc.), och en algoritm som använder bitoperationer (AND, OR, NOT) ) för att svara på sökfrågan.

Vi får höra att bitmappsindex är bäst lämpade och mycket presterande för fall där det finns sökningar som kombinerar sökfrågor över många kolumner med låg kardinalitet (tänk "ögonfärg" eller "äktenskaplig status" kontra något som "avstånd från centrum" ). Men jag ska visa senare att de fungerar utmärkt även för kolumner med hög kardinalitet.

Låt oss titta på det enklaste exemplet på ett bitmappsindex.

Föreställ dig att vi har en lista över restauranger i Moskva med binära egenskaper som dessa:

• nära tunnelbana;
• det finns privat parkering;
• det finns en veranda (har terrass);
• du kan boka bord (accepterar reservationer);
• lämplig för vegetarianer (veganvänlig);
• dyrt (dyrt).

Låt oss ge varje restaurang ett sekvensnummer som börjar från 0 och allokera minne för 6 bitmappar (en för varje egenskap). Vi kommer sedan att fylla i dessa bitmappar beroende på om restaurangen har den här egenskapen eller inte. Om restaurang 4 har en veranda kommer bit nr 4 i bitmappen "har en veranda" att sättas till 1 (om det inte finns någon veranda, då till 0).

Nu har vi det enklaste bitmappsindexet som är möjligt, och vi kan använda det för att svara på frågor som:

• "Visa mig vegetariska restauranger";
• "Visa mig billiga restauranger med en veranda där du kan boka bord."

Hur? Låt oss ta en titt. Den första begäran är mycket enkel. Allt vi behöver göra är att ta den "vegetarvänliga" bitmappen och förvandla den till en lista över restauranger vars bitar är exponerade.


Den andra begäran är lite mer komplicerad. Vi måste använda NOT-bitmappen på den "dyra" bitmappen för att få en lista över billiga restauranger, sedan OCH den med bitmappen "kan jag boka bord" och OCH resultatet med bitmappen "det finns en veranda". Den resulterande bitmappen kommer att innehålla en lista över anläggningar som uppfyller alla våra kriterier. I det här exemplet är detta bara restaurangen Yunost.


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

Var används bitmappsindex?

Om du Google bitmappsindexerar kommer 90% av svaren att vara relaterade till Oracle DB på ett eller annat sätt. Men andra DBMS:er stöder säkert också en sådan cool grej, eller hur? Inte riktigt.

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

MySQL stöder ännu inte bitmappsindex, men det finns ett förslag som föreslår att du lägger till det här alternativet (https://dev.mysql.com/worklog/task/?id=1524).

PostgreSQL stöder inte bitmappsindex, men använder enkla bitmappar och bitoperationer för att kombinera sökresultat över flera andra index.

Tarantool har bituppsättningsindex och stöder enkla sökningar på dem.

Redis har enkla bitfält (https://redis.io/commands/bitfield) utan möjlighet att söka efter dem.

MongoDB stöder ännu inte bitmappsindex, men det finns också ett förslag som föreslår att detta alternativ läggs till https://jira.mongodb.org/browse/SERVER-1723

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

• Men en ny granne har dykt upp i vårt hus: Pilosa. Detta är en ny icke-relationell databas skriven i Go. Den innehåller bara bitmappsindex och baserar allt på dem. Vi ska prata om det lite senare.

Implementering i Go

Men varför används bitmappsindex så sällan? Innan jag svarar på den här frågan skulle jag vilja visa dig hur du implementerar ett mycket enkelt bitmappsindex i Go.

Bitmaps är i huvudsak bara bitar av data. I Go, låt oss använda byte-skivor för detta.

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

Vi kommer att behöva två hjälpfunktioner. En kommer att användas för att fylla våra bitmappar med slumpmässiga data. Slumpmässigt, men med en viss sannolikhet att restaurangen har varje fastighet. Till exempel tror jag att det finns väldigt få restauranger i Moskva där man inte kan boka bord, och det förefaller mig som om cirka 20 % av anläggningarna är lämpliga för vegetarianer.

Den andra funktionen konverterar bitmappen till en lista över restauranger.


För att svara på frågan "Visa mig billiga restauranger som har en uteplats och kan göra reservationer" behöver vi två bitars operationer: NOT och AND.

Vi kan förenkla vår kod lite genom att använda den mer komplexa AND NOT-operatorn.

Vi har funktioner för var och en av dessa operationer. Båda går igenom skivorna, tar motsvarande element från var och en, kombinerar dem med lite operation och lägger resultatet i den resulterande skivan.

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

Prestanda är inte så hög, även om funktionerna är väldigt enkla och vi sparade mycket pengar genom att inte returnera en ny resulterande skiva varje gång funktionen anropades.

Efter att ha gjort lite profilering med pprof, märkte jag att Go-kompilatorn saknade en mycket enkel men mycket viktig optimering: funktionsinförande.

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

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

Och, som du kan se, nu kommer kompilatorn med glädje att infoga vår funktion! Som ett resultat lyckas vi spara cirka 2 mikrosekunder. Inte dåligt!

Den andra flaskhalsen är lätt att se om man tittar noga på monteringsutdata. Kompilatorn lade till en skivgränskontroll mitt i vår hetaste loop. Faktum är att Go är ett säkert språk, kompilatorn är rädd att mina tre argument (tre skivor) är av olika storlek. När allt kommer omkring kommer det att finnas en teoretisk möjlighet att ett så kallat buffertspill inträffar.

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

När kompilatorn ser detta hoppar kompilatorn glatt över kontrollen och det slutar med att vi sparar ytterligare 500 nanosekunder.

Stora butcher

Okej, vi lyckades pressa ut lite prestanda ur vår enkla implementering, men detta resultat är faktiskt mycket sämre än vad som är möjligt med nuvarande hårdvara.

Allt vi gör är grundläggande bitoperationer, och våra processorer utför dem mycket effektivt. Men tyvärr "matar" vi vår processor med mycket små bitar av arbete. Våra funktioner utför operationer på en byte-för-byte-basis. Vi kan mycket enkelt justera vår kod så att den fungerar med 8-byte-bitar med UInt64-skivor.

Som du kan se påskyndade denna lilla förändring vårt program åtta gånger genom att öka batchstorleken med åtta gånger. Förstärkningen kan sägas vara linjär.

Implementering i assembler

Men detta är inte slutet. Våra processorer kan arbeta med bitar på 16, 32 och till och med 64 byte. Sådana "breda" operationer kallas single-instruction multiple data (SIMD; en instruktion, många data), och processen att transformera kod så att den använder sådana operationer kallas vektorisering.

Tyvärr är Go-kompilatorn långt ifrån utmärkt på vektorisering. För närvarande är det enda sättet att vektorisera Go-kod att ta och lägga dessa operationer manuellt med Go assembler.

Go assembler är ett konstigt odjur. Du vet säkert att assemblerspråk är något som är starkt knutet till arkitekturen på datorn du skriver för, men så är det inte i Go. Go assembler är mer som ett IRL (intermediate representation language) eller mellanspråk: det är praktiskt taget plattformsoberoende. Rob Pike gjorde en utmärkt prestation Rapportera om detta ämne för flera år sedan på GopherCon i Denver.

Dessutom använder Go ett ovanligt Plan 9-format, som skiljer sig från de allmänt accepterade AT&T- och Intel-formaten.

Det är säkert att säga att det inte är det roligaste att skriva Go assembler för hand.

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

Dessa verktyg förenklar saker som registertilldelning, skrivning av loopar och förenklar i allmänhet processen att komma in i en värld av monteringsprogrammering 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 main()-funktion, som inom sig definierar Add()-funktionen, vars betydelse är att addera två tal. Det finns hjälpfunktioner här för att få parametrar efter namn och få ett av de gratis och lämpliga processorregistren. Varje processoroperation har en motsvarande funktion på avo, som ses i ADDQ. Slutligen ser vi en hjälpfunktion för att lagra det resulterande värdet.

Genom att anropa go generera kommer vi att köra programmet på avo och som ett resultat kommer två filer att genereras:

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

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

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

Liksom i föregående exempel ber vi om ett gratis och giltigt register för allmänt ändamål, vi behöver inte beräkna offset och storlekar för argumenten. avo gör allt detta för oss.

Vi brukade använda etiketter och goto (eller hopp) för att förbättra prestanda och lura Go-kompilatorn, men nu gör vi det från början. Poängen är att cykler är ett begrepp på högre nivå. I assembler har vi bara etiketter och hopp.

Den återstående koden bör redan vara bekant och förståelig. Vi emulerar en slinga med etiketter och hopp, tar en liten bit data från våra två skivor, kombinerar dem med en bitoperation (OCH INTE i det här fallet) och lägger sedan in resultatet i den resulterande skivan. Allt.

Så här ser den slutliga assemblerkoden ut. Vi behövde inte beräkna offset och storlekar (markerade i grönt) eller hålla reda på vilka register som användes (markerade i rött).

Om vi ​​jämför prestandan för implementeringen av assemblerspråket med prestandan för den bästa implementeringen i Go kommer vi att se att det är samma sak. Och detta förväntas. Vi gjorde trots allt inget speciellt – vi återgav bara vad en Go-kompilator skulle göra.

Tyvärr kan vi inte tvinga kompilatorn att infoga våra funktioner skrivna på assemblerspråk. Go-kompilatorn har för närvarande inte en sådan funktion, även om det har funnits en begäran om att lägga till den under ganska lång tid.

Det är därför det är omöjligt att få någon nytta av små funktioner i assemblerspråk. Vi måste antingen skriva stora funktioner, eller använda det nya math/bits-paketet, eller kringgå assembler-språket.

Låt oss nu titta på vektorversionerna av våra funktioner.

För det här exemplet bestämde jag mig för att använda AVX2, så vi kommer att använda operationer som fungerar på 32-byte bitar. Strukturen på koden är mycket lik den skalära versionen: ladda parametrar, be om ett gratis delat register, etc.

En innovation är att bredare vektoroperationer använder speciella breda register. I fallet med 32-byte bitar är dessa register prefixerade med Y. Det är därför du ser YMM()-funktionen i koden. Om jag använde AVX-512 med 64-bitars bitar, skulle prefixet vara Z.

Den andra innovationen är att jag bestämde mig för att använda en optimering som kallas loop unrolling, vilket innebär att man gör åtta loopoperationer manuellt innan man hoppar till början av loopen. Denna optimering minskar antalet filialer i koden och begränsas av antalet tillgängliga gratisregister.

Tja, hur är det med prestanda? Hon är vacker! Vi uppnådde en speedup på cirka sju gånger jämfört med den bästa Go-lösningen. Imponerande, eller hur?

Men även denna implementering skulle potentiellt kunna accelereras genom att använda AVX-512, förhämtning eller en JIT (just-in-time kompilator) för frågeschemaläggaren. Men detta är verkligen ett ämne för en separat rapport.

Problem med bitmappsindex

Nu när vi redan har tittat på en enkel implementering av ett bitmappsindex i Go och ett mycket mer produktivt i assemblerspråk, låt oss äntligen prata om varför bitmappsindex används så sällan.

I äldre tidningar nämns tre problem med bitmappsindex, men nyare tidningar och jag hävdar att de inte längre är relevanta. Vi kommer inte att fördjupa oss i vart och ett av dessa problem, utan kommer att titta på dem ytligt.

Problemet med hög kardinalitet

Så vi får veta att bitmappsindex endast är lämpliga för fält med låg kardinalitet, det vill säga de som har få värden (till exempel kön eller ögonfärg), och anledningen är att den vanliga representationen av sådana fält (ett bit per värde) vid hög kardinalitet kommer det att ta upp för mycket utrymme och dessutom kommer dessa bitmappsindex att vara dåligt (sällan) fyllda.


Ibland kan vi använda en annan representation, till exempel den standard vi använder för att representera siffror. Men det var tillkomsten av komprimeringsalgoritmer som förändrade allt. Under de senaste decennierna har forskare och forskare kommit fram till ett stort antal komprimeringsalgoritmer för bitmappar. Deras främsta fördel är att det inte finns något behov av att dekomprimera bitmappar för att utföra bitoperationer - vi kan utföra bitoperationer direkt på komprimerade bitmappar.

Nyligen har hybridmetoder börjat dyka upp, som rytande bitmappar. De använder samtidigt tre olika representationer för bitmappar – själva bitmappar, arrayer och så kallade bitkörningar – och balanserar mellan dem för att maximera prestanda och minimera minnesförbrukningen.

Du kan hitta brusande bitmappar i de mest populära applikationerna. Det finns redan ett stort antal implementeringar för en mängd olika programmeringsspråk, inklusive mer än tre implementeringar för Go.

Ett annat tillvägagångssätt som kan hjälpa oss att hantera hög kardinalitet kallas binning. Föreställ dig att du har ett fält som representerar en persons längd. Höjd är ett flyttal, men vi människor tänker inte på det så. För oss är det ingen skillnad mellan höjd 185,2 cm och 185,3 cm.

Det visar sig att vi kan gruppera liknande värden i grupper inom 1 cm.

Och om vi dessutom vet att väldigt få människor är kortare än 50 cm och längre än 250 cm, så kan vi i princip förvandla ett fält med oändlig kardinalitet till ett fält med en kardinalitet på cirka 200 värden.

Vid behov kan vi naturligtvis göra ytterligare filtrering i efterhand.

Problem med hög bandbredd

Nästa problem med bitmappsindex är att det kan bli mycket dyrt att uppdatera dem.

Databaser måste kunna uppdatera data medan potentiellt hundratals andra frågor söker efter data. Vi behöver lås för att undvika problem med samtidig dataåtkomst eller andra delningsproblem. Och där det finns ett stort lås, finns det ett problem - låsstrid, när detta lås blir en flaskhals.

Detta problem kan lösas eller kringgås genom att använda sharding eller använda versionsindex.

Sharding är en enkel och välkänd sak. Du kan dela ett bitmappsindex på samma sätt som andra data. Istället för ett stort lås kommer du att få ett gäng små lås och därmed bli av med låsstriden.

Det andra sättet att lösa problemet är att använda versionerade index. Du kan ha en kopia av indexet som du använder för att söka eller läsa, och en som du använder för att skriva eller uppdatera. Och en gång under en viss tidsperiod (till exempel en gång var 100:e ms eller 500 ms) duplicerar du dem och byter ut dem. Naturligtvis är detta tillvägagångssätt endast tillämpligt i de fall din applikation kan hantera ett något eftersläpande sökindex.

Dessa två tillvägagångssätt kan användas samtidigt: du kan ha ett fragmenterat versionsindex.

Mer komplexa frågor

Det sista problemet med bitmappsindex är att vi får höra att de inte är väl lämpade för mer komplexa typer av frågor, såsom span-frågor.

Faktum är att om du tänker efter så är bitoperationer som AND, OR, etc. inte särskilt lämpliga för frågor a la "Visa mig hotell med rumspriser 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 bitvis ELLER-operation.

En lite bättre lösning skulle vara att använda gruppering. Till exempel i grupper om 50 dollar. Detta skulle påskynda vår process med 50 gånger.

Men problemet löses också enkelt genom att använda en vy som skapats specifikt för denna typ av förfrågningar. I vetenskapliga artiklar kallas det för avståndskodade bitmappar.

I den här representationen ställer vi inte bara in en bit för något värde (till exempel 200), utan ställer in detta värde och allt högre. 200 och uppåt. Samma för 300:300 och uppåt. Och så vidare.

Med den här representationen kan vi svara på den här typen av sökfrågor genom att gå igenom indexet bara två gånger. Först kommer vi att få en lista över hotell där rummet kostar mindre eller $300, och sedan tar vi bort de där rummet kostar mindre eller $199. Redo.

Du kommer att bli förvånad, men även geoqueries är möjliga med hjälp av bitmappsindex. Tricket är att använda en geometrisk representation som omger din koordinat med en geometrisk figur. Till exempel S2 från Google. Figuren ska vara möjlig att representera i form av tre eller flera korsande linjer som kan numreras. På så sätt kan vi förvandla vår geoquery till flera frågor "langs gapet" (längs dessa numrerade rader).

Klara lösningar

Jag hoppas att jag intresserade dig lite och att du nu har ytterligare ett användbart verktyg i din arsenal. Om du någon gång behöver göra något sånt här, vet du vart du ska leta.

Men alla har inte tid, tålamod eller resurser att skapa bitmappsindex från början. Särskilt mer avancerade, med till exempel SIMD.

Som tur är finns det flera färdiga lösningar som hjälper dig.

Rytande bitmappar

För det första finns det samma rytande bitmapsbibliotek som jag redan pratat om. Den innehåller alla nödvändiga behållare och bitoperationer som du behöver för att göra ett fullfjädrat bitmappsindex.

Tyvärr, för tillfället använder ingen av Go-implementeringarna SIMD, vilket innebär att Go-implementationer är mindre prestanda än C-implementationer, till exempel.

hår

En annan produkt som kan hjälpa dig är Pilosa DBMS, som faktiskt bara har bitmappsindex. Detta är en relativt ny lösning, men den vinner hjärtan i hög hastighet.

Pilosa använder brusande bitmappar internt och ger dig möjligheten att använda dem, förenklar och förklarar allt jag pratade om ovan: gruppering, avståndskodade bitmappar, konceptet med ett fält osv.

Låt oss ta en snabb titt på ett exempel på hur du använder Pilosa för att svara på en fråga du redan är bekant med.

Exemplet är väldigt likt det du såg tidigare. Vi skapar en klient till Pilosa-servern, skapar ett index och de nödvändiga fälten, fyller sedan våra fält med slumpmässiga data med sannolikheter och, slutligen, exekverar vi den välbekanta frågan.

Efter det använder vi INTE på fältet "dyrt", skär sedan resultatet (eller OCH det) med fältet "terrass" och med fältet "reservationer". Och äntligen får vi slutresultatet.

Jag hoppas verkligen att den här nya typen av index inom en överskådlig framtid också kommer att dyka upp i DBMS som MySQL och PostgreSQL - bitmappsindex.

Slutsats

Om du inte har somnat än, tack. Jag var tvungen att kort beröra många ämnen på grund av begränsad tid, men jag hoppas att föredraget var användbart och kanske till och med motiverande.

Bitmapindex är bra att veta om, även om du inte behöver dem just nu. Låt dem vara ytterligare ett verktyg i din verktygslåda.

Vi har tittat på olika prestandatrick för Go och saker som Go-kompilatorn inte hanterar särskilt bra ännu. Men detta är absolut användbart för alla Go-programmerare att veta.

Det var allt jag ville berätta för dig. Tack!

Källa: will.com