GoSuda

Schottky: Nullallokering, rekkefølgebevarende byte-nøkkelkoding for Go

By Lemon Mint views ...

Når man implementerer LSM-tree- eller B-tree-baserte nøkkel-verdi-lagre og databaseindekser, må sammensatte felt ofte kombineres til en enkelt byte-nøkkel.

Standard serialiseringsformater som JSON eller Protocol Buffers er ikke utformet for dette formålet, fordi deres serialiserte byte-utdata ikke bevarer den naturlige sorteringsrekkefølgen som kreves av usignerte bytevise sammenligninger (bytes.Compare eller memcmp).

Schottky er et Go-bibliotek utviklet for å kode sammensatte tupler med flere typer til bevarende-rekkefølge byte-nøkler.

1go get gosuda.org/schottky@latest

Serialisering kontra sorteringsnøkler

Å garantere korrekt bytevis sortering krever håndtering av flere lavnivådetaljer knyttet til datarepresentasjon:

  • Heltall: Standard big-endian-koding med tosekomplement bryter den naturlige rekkefølgen på grunn av det mest signifikante fortegnsbitet. Invertering av fortegnsbitet er nødvendig for korrekte usignerte bytesammenligninger.
  • Flyttall: Krever justeringer av fortegnsbitet, invertert rekkefølge for negative verdier, og konsekvent håndtering av NaN og -0.
  • Strenger og byte-slices med variabel lengde: Feltgrenser må bevares uten å bryte prefiks-sorteringsrekkefølger.
  • Krav til sammensatte nøkler: Støtte for uavhengig ASC/DESC-rekkefølge per felt, frakoblede NULLS FIRST/LAST-regler, streng leksikografisk prioritet (tidligere felt bestemmer rekkefølgen) og kompatibilitet med prefiksskanning.

Schottky konverterer hver verdi til en kanonisk nyttelast før presenseringskoder og retningsorientering anvendes. For DESC-felt inverteres hver byte i ASC-nyttelasten bitvis (^b). NULL-plassering håndteres via dedikerte presenseringskoder og opererer uavhengig av sorteringsretning.

Grunnleggende bruk

Følgende eksempel bygger en sammensatt nøkkel bestående av en konto-ID (ASC, NULLS LAST) og et navn (DESC, NULLS FIRST):

 1package main
 2
 3import (
 4        "fmt"
 5
 6        "gosuda.org/schottky"
 7)
 8
 9func main() {
10        storage := make([]byte, 0, 128)
11        builder := schottky.NewBuilder(storage)
12
13        builder.Int64(42, schottky.AscNullsLast)
14        accountPrefixLen := builder.Len()
15
16        builder.String("Ada", schottky.DescNullsFirst)
17        key, err := builder.Key()
18
19        if err != nil {
20                panic(err)
21        }
22        accountPrefix := key[:accountPrefixLen]
23        fmt.Printf("key=%x\nprefix=%x\n", key, accountPrefix)
24}

Schottky tilbyr fire eksplisitte konfigurasjoner for sorteringsrekkefølge:

  • AscNullsFirst
  • AscNullsLast
  • DescNullsFirst
  • DescNullsLast

NULL-posisjonering utledes aldri implisitt. Hvis en ugyldig Order-verdi sendes inn, registrerer builderen ErrInvalidOrder, som returneres ved kall til Key() eller Err().

Prefiksskanning og områdegrenser

Schottky-sammensatte nøkler inneholder ingen globale headere, metadata om antall felt, typekoder eller avsluttende markører. Forutsatt at skjemaet er kjent på forhånd, sammenkobles feltkodingene ganske enkelt.

På grunn av denne oppbyggingen danner de kodede bytene til ledende felt et gyldig prefiks for områdeskanninger. I eksemplet ovenfor kan accountPrefix brukes direkte som et prefiksfilter for å skanne alle poster der Account ID == 42.

For å beregne den eksklusive øvre grensen for halvåpne [prefix, upper)-områdeskanninger brukes PrefixUpperBound:

 1upperStorage := make([]byte, 0, len(accountPrefix))
 2upper, finite, err := schottky.PrefixUpperBound(upperStorage, accountPrefix)
 3
 4if err != nil {
 5        panic(err)
 6}
 7
 8if finite {
 9        // Halvåpen skanning av [accountPrefix, upper)
10} else {
11        // Åpen skanning uten øvre grense
12}

Merk: Builder.Len() må måles ved rene feltgrenser. Oppdeling inne i et felts interne byte-strøm gir et ugyldig prefiks.

Null allokeringer og bufferhåndtering

Nøkkelgenerering kjøres ofte på kritiske databaseveier. For å eliminere heap-allokeringer og overhead ved bufferendring opererer Builder strengt innenfor kapasiteten til det kallerleverte skiven og vil ikke reallokere internt.

Hvis bufferen går tom for kapasitet, registreres ErrShortBuffer uten at delvise byte skrives. Feltskrivinger er atomiske, og den første feilen som oppstår bevares til den kontrolleres via Key() eller Err(). Tilstrekkelig kapasitet på forhånd sikrer koding uten allokeringer.

Bufferstørrelser kan beregnes på forhånd ved hjelp av hjelpefunksjoner som EncodedBytesSize, EncodedStringSize og EncodedDecimalSize, eller via faste størrelseskonstanter. Den returnerte nøkkelen refererer direkte til den oppgitte bufferen, og ansvaret for minnelivssyklusen overlates til kalleren.

Decoder fungerer symmetrisk: den låner direkte fra inndatanøkkelen, krever kallerleverte destinasjonsbuffere for felt med variabel lengde, og tilbyr Remaining() == 0 for å oppdage etterfølgende byte eller skjemaavvik.

Støttede datatyper

  • Heltall: Signerte og usignerte (8-bit til 64-bit), Int128
  • Flyttall og numeriske verdier: Float32, Float64, desimaltekst
  • Grunnleggende typer: Binær streng, byte-slice, boolsk verdi, enum-rang
  • Dato og tid: Dato, tid, tid med sonesone, tidsstempel, varighet, kalenderintervall
  • Nettverk og identifikatorer: UUID, MAC, IP, IP-prefiks, kanonisk nettverksprefiks, LSN
  • Sammensatte strukturer: Nøstede tupler, områder og rå strukturkodinger
  • Kollasjon: Unicode-kollasjonsnøkler og eksterne kanoniske tokens

SQL-typeoversettelse er tilpasset sorteringsreglene for PostgreSQL 18 B-tree. Typer som avhenger av databasekataloger eller intern motortilstand håndteres ved å sende inn eksterne kanoniske tokens.

Strengkollasjon

Builder.String bruker som standard rå UTF-8-binær rekkefølge. For lokalitetsbevisst sortering tilbyr Schottky en samtidighetssikker, uforanderlig Collator:

  • Deterministisk kollasjon: Koder kollasjonsnøkkelen sammen med rå UTF-8-byte for å gi en tie-breaker når kollasjonsvektene er identiske.
  • Ikke-deterministisk kollasjon: Behandler kollasjonslike strenger som identiske, og utelater den rå byte-tie-breaker.

Unicode- og profilversjoner bør spores i metadataskjemaet. Dersom kollasjonsleverandører eller profilinnstillinger endres, må eksisterende nøkler bygges på nytt.

Skjemahåndtering

Fordi Schottky-nøkler er rå byte-sekvenser uten header, må skjemalaget spore:

  1. Feltsekvens og datatyper.
  2. Sorteringsretninger (ASC/DESC) og NULL-rekkefølge (NULLS FIRST/LAST).
  3. Strengkollasjon og normaliseringsregler.
  4. Schottky- og kollasjonsprofilversjoner.

Sammenligning av nøkler generert med ulike skjemaer, eller dekoding mot et avvikende skjema, bryter rekkefølgegarantiene.

Ytelse og lenker

På Go 1.27+ kan eksperimentell portabel SIMD-akselerasjon aktiveres med GOEXPERIMENT=simd. Skalare og SIMD-stier produserer byte-identiske nøkler.