GoSuda

Livfull bitmapp

By snowmerak views ...

Vad är en bitmap?

Här är bitmap ett slags index. Om du kom hit med tanke på grafik, kan du gå tillbaka.

Grundläggande begrepp

Bitmap är en form av indexeringsteknik i databaser. Värdena i en viss kolumn representeras som en bitvektor eller som ett element i en vektor, och varje bit anger om ett visst värde i kolumnen förekommer. Den mest grundläggande formen innebär därför att varje row tilldelas ett bitindex och att förekomst uttrycks med 0 och 1.

Låt oss till exempel anta att det finns en tabell med en könskolumn. Antag att tabellen har 5 rows och att värdena i könskolumnen är följande:

  1. Man
  2. Kvinna
  3. Man
  4. Kvinna
  5. Annat

I detta fall kan bitmapindexet för könskolumnen uttryckas på följande sätt:

  • Man: 10100
  • Kvinna: 01010
  • Annat: 00001

Så var används det egentligen

Många kommer nog att tänka att det inte bara handlar om att representera detta. För att på allvar använda ett bitmapindex, låt oss betrakta följande fall.

1CREATE TABLE IF NOT EXISTS Users (
2    id INT PRIMARY KEY,
3    name VARCHAR(100),
4    active BOOLEAN,
5    sex BOOLEAN,
6    age INT
7);

Låt oss anta att denna tabell har 1 000 000 rows. Och anta att vi kör följande fråga.

1SELECT * FROM Users WHERE active = TRUE AND SEX = TRUE;

Denna fråga hittar de rows där kolumnerna active och sex båda är TRUE. Det snabbaste sättet att hitta rows som uppfyller villkoret att båda kolumnerna är TRUE är då att använda bitvis AND-operation.

  • Bitmapindexet för kolumnen active är redan indexerat som 1100110011... (en bitvektor med 1 000 000 bitar),
  • och bitmapindexet för kolumnen sex är redan indexerat som 1010101010... (en bitvektor med 1 000 000 bitar).

Genom att utföra en bitvis AND-operation på de två bitmapindexen kan man snabbt hitta de rows där båda kolumnerna är TRUE. Eftersom det är en enkel bitoperation kan resultatet erhållas betydligt snabbare än med andra indexskanningar.

Avvägningar

Bitmapindex kan vara mycket effektiva, men de har vissa avvägningar. Det finns många andra nackdelar, men här tar vi bara upp en.

Den är att bitmapindex passar bättre för låg kardinalitet (det vill säga när antalet möjliga värden i kolumnen är litet). Om man använder bitmapindex på en kolumn med hög kardinalitet kan bitmaporna bli mycket stora.

När man använder bitmapindex på en kolumn med hög kardinalitet måste en separat bitmap skapas för varje unikt värde, vilket kan kräva mycket lagringsutrymme. Om kolumnen till exempel har 1 000 000 unika värden måste 1 000 000 bitmaps skapas, vilket kan vara mycket ineffektivt.

Så här gör vi

Man kan ersätta de bitmaps som uppstår vid hög kardinalitet med något som kallas Roaring Bitmap. Roaring Bitmap har flera egenskaper, men dess viktigaste grundfilosofi och egenskap är att dynamiskt välja den mest lämpliga lagringsmetoden utifrån datans täthet för att maximera både komprimeringsgrad och beräkningshastighet.

Grundläggande begrepp i Roaring Bitmap

Tvånivåindexering

Roaring Bitmap genomgår följande två steg för att lagra ett heltal. Trots namnet tvånivåindexering kan man helt enkelt betrakta det som en tvådimensionell array.

  • Extrahera de övre 16 bitarna: De övre 16 bitarna av heltalet extraheras och används som index. Det är index för den yttre arrayen, som är en tvådimensionell array med längden 65536. Denna array lagrar adressen till den container som beskrivs nedan.
  • Extrahera de nedre 16 bitarna: De nedre 16 bitarna av heltalet extraheras och används som position inom containern.

Container

Denna container motsvarar den inre arrayen i den tvådimensionella arrayen som nyss jämfördes. Till skillnad från den yttre arrayen för de övre 16 bitarna varierar dock containerns interna struktur beroende på hur mycket data den innehåller. Roaring Bitmap stöder följande 3 typer av containers.

  • Array Container: Denna container används när den lagrar få data. Mer specifikt används den när den lagrar 4096 element eller färre. Den implementeras helt enkelt som en sorterad heltalsarray. Elementen kan hittas med binärsökning.
  • Bitmap Container: Denna container används när den lagrar mycket data. Mer specifikt används den när den lagrar fler än 4096 element. Den implementeras som en bitmap med 65536 bitar (8192 byte). Varje bit anger om motsvarande heltal finns eller inte.
  • Run Container: Denna container används för att lagra kontinuerliga intervall av heltal. Den är till exempel effektiv för att lagra sammanhängande heltal som 1, 2, 3, 4, 5. Den implementeras som en lista med par (startvärde, längd). Om alla värden finns? Det innebär att allt från början till slut finns, så det räcker att lagra (0, 65536) en gång.

Detta sätt gör att Roaring Bitmap använder minnet mycket effektivt och kan ge optimal prestanda för olika datatätheter.

Funktioner i Roaring Bitmap

Grundläggande funktioner

Roaring Bitmap tillhandahåller följande grundläggande funktioner.

  • Insättning: Lägger till ett nytt heltal i bitmapen. Under denna process kan lämplig container väljas, eller containern konverteras vid behov.
  • Borttagning: Tar bort ett befintligt heltal från bitmapen. Även i denna process sker lämplig hantering beroende på containerns tillstånd.
  • Sökning: Kontrollerar om ett visst heltal finns i bitmapen. Denna process utförs mycket snabbt.

Mängdoperationer

Roaring Bitmap stöder dessutom följande mängdoperationer.

  • Union: Skapar en ny bitmap som innehåller alla element från de två bitmapparna.
  • Snitt (Intersection): Skapar en ny bitmap som endast innehåller element som finns i båda bitmapparna.
  • Symmetrisk differens (Symmetric Difference): Skapar en ny bitmap som innehåller element som finns i endast en av de två bitmapparna.

Dessa operationer optimeras efter bitmapens containertyp och utförs därmed mycket snabbt.

I Go-språket

I Go kan man enkelt använda Roaring Bitmap genom paketet github.com/RoaringBitmap/roaring. Paketet tillhandahåller alla funktioner i Roaring Bitmap och är optimerat för Go-språkets egenskaper.

Installation

1go get github.com/RoaringBitmap/roaring/v2

Användningsexempel

 1package main
 2
 3import (
 4	"log"
 5
 6	"github.com/RoaringBitmap/roaring/v2"
 7)
 8
 9func main() {
10	b1 := roaring.BitmapOf(1, 2, 3, 4)     // initialiserad med 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // initialiserad med 2, 4, 6, 8, 12
12
13	b1.Add(5)  // lägg till 5
14	b2.Add(10) // lägg till 10
15
16	b2.Remove(12) // ta bort 12
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// bitmap-operationer ändrar originalet, så använd en kopia
22	xor := b1.Clone()
23	xor.Xor(b2)
24
25	log.Printf("and result: %v", and.ToArray())
26	log.Printf("or result: %v", or.ToArray())
27	log.Printf("xor result: %v", xor.ToArray())
28}

12025/09/08 22:16:27 and result: [2 4]
22025/09/08 22:16:27 or result: [1 2 3 4 5 6 8 10]
32025/09/08 22:16:27 xor result: [1 3 5 6 8 10]

Följande är viktiga funktioner som inte förekommer i exemplet ovan:

  • Contains(x uint32) bool: Kontrollerar om ett visst värde finns i bitmapen
  • GetCardinality() uint64: Returnerar antalet element i bitmapen
  • Rank(x uint32) uint64: Returnerar antalet element som är mindre än eller lika med ett visst värde
  • ToBytes() ([]byte, error): Serialiserar bitmapen till en byteslice
  • FromBytes(data []byte) error: Återställer bitmapen från en byteslice
  • Clone() *Bitmap: Skapar en kopia av bitmapen
  • Clear(): Återställer bitmapen
  • NextValue(x uint32) int64: Returnerar nästa element som är större än eller lika med x
  • PreviousValue(x uint32) int64: Returnerar föregående element som är mindre än eller lika med x
  • Maximum() uint32: Returnerar det största elementet i bitmapen
  • Minimum() uint32: Returnerar det minsta elementet i bitmapen

Det finns sådana funktioner. För mer information, se den officiella dokumentationen.

Observera även att paketet roaring innehåller ett paket som stöder uint64 utöver uint32. Det tillhandahåller nästan samma gränssnitt, så det kan bytas ut direkt.

 1package main
 2
 3import (
 4	"log"
 5
 6	"github.com/RoaringBitmap/roaring/v2/roaring64"
 7)
 8
 9func main() {
10	b1 := roaring64.BitmapOf(1, 2, 3, 4)     // initialiserad med 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // initialiserad med 2, 4, 6, 8, 12
12
13	b1.Add(5)  // lägg till 5
14	b2.Add(10) // lägg till 10
15
16	b2.Remove(12) // ta bort 12
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// bitmap-operationer ändrar originalet, så använd en kopia
22	xor := b1.Clone()
23	xor.Xor(b2)
24
25	log.Printf("and result: %v", and.ToArray())
26	log.Printf("or result: %v", or.ToArray())
27	log.Printf("xor result: %v", xor.ToArray())
28}

Avslutning

Roaring Bitmap är ett kraftfullt verktyg för att effektivt lagra och manipulera mängder av heltal med hög kardinalitet. Genom att använda paketet github.com/RoaringBitmap/roaring i Go kan man enkelt utnyttja alla funktioner i Roaring Bitmap. Paketet maximerar minnesanvändning och prestanda genom olika containertyper och optimerade operationer. Roaring Bitmap kan användas för effektiv databehandling inom många områden, till exempel databasindexering, logganalys och statistiska beräkningar.

Roaring Bitmap presterar särskilt väl på storskaliga datamängder och kan användas i många olika tillämpningar. Kombinerat med Go-språkets koncisa och effektiva syntax ger Roaring Bitmap utvecklare ett kraftfullt verktyg. Vi ser fram emot att Roaring Bitmap utvecklas vidare med fler funktioner och optimeringar.

Varför gjorde jag detta? För att indexera varje tagg i en tidsseriedatabas och för snabba unionsoperationer.