GoSuda

Schottky: Zero-Allocation, Order-Preserving Byte-Key Encoding for Go

By Lemon Mint
views ...

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

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

Schottky er et Go-bibliotek konstruert for å encodere flertype sammensatte tupler til rekkefølgebevarende byte-nøkler.

1go get gosuda.org/schottky@latest

Serialisering vs. Sorteringsnøkler

Garanti for korrekt byte-vis sortering krever håndtering av flere lavnivå datarepresentasjonsdetaljer:

  • Heltall: Standard toers komplement big-endian encodering bryter naturlig rekkefølge på grunn av den mest signifikante fortegnsbiten. Invertering av fortegnsbiten er nødvendig for korrekte ufortegnede byte-sammenligninger.
  • Flyttall: Krever justeringer av fortegnsbit, invertert rekkefølge for negative verdier, og konsistent håndtering av NaN og -0.
  • Strenger med variabel lengde og byte-utsnitt: Feltgrenser må bevares uten å bryte prefikssorteringsrekkefø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 avgjør rekkefølge), og kompatibilitet med prefiksskanning.

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

Grunnleggende Bruk

Følgende eksempel bygger en sammensatt nøkkel som består av en Account ID (ASC, NULLS LAST) og et Name (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 eksakte sorteringsrekkefølgekonfigurasjoner:

  • AscNullsFirst
  • AscNullsLast
  • DescNullsFirst
  • DescNullsLast

NULL-posisjonering blir aldri implisitt utledet. Hvis en ugyldig Order-verdi blir sendt, registrerer byggeren ErrInvalidOrder, som returneres ved kall på Key() eller Err().

Prefiksskanning og Områdegrenser

Schottky sammensatte nøkler inneholder ingen globale hodere, feltantallsmetadata, typetagger eller haler. Forutsatt at skjemaet er kjent på forhånd, blir feltencoderinger ganske enkelt konsatenerené.

På grunn av dette oppsettet danner de encodede bytene til ledende felt et gyldig prefiks for område skanninger. 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åde skanninger, bruk 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 [accountPrefix, upper) område skanning
10} else {
11        // Uendelig åpen område skanning
12}

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

Null-allokering og Buffer-styring

Nøkkelgenerering kjører hyppig på kritiske databankstier. For å eliminere heap-allokeringer og overhead ved bufferendring, arbeider Builder strengt innenfor kapasiteten til det innringer-leverte utsnittet og vil ikke reallokere internt.

Hvis bufferet går tom for kapasitet, registreres ErrShortBuffer uten å skrive partielle byte. Feltnedskrivninger er atomiske, og den første feilen som støtes på, bevares til den sjekkes via Key() eller Err(). Tilstrekkelig kapasitet på forhånd sikrer null-allokering encodering.

Bufferstørrelser kan beregnes på forhånd ved hjelp av hjelpefunksjoner som EncodedBytesSize, EncodedStringSize, og EncodedDecimalSize, eller via faststørrelseskonstanter. Den returnerte nøkkelen refererer direkte til det leverte bufferet, og overlater minnelivssyklushåndtering til innringeren.

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

Støttede Datatyper

  • Heltall: Fortegnede og ufortegnede (8-bit til 64-bit), Int128
  • Flyttall & Numeriske verdier: Float32, Float64, Desimaltekst
  • Grunnleggende typer: Binær streng, Byte-utsnitt, Boolsk, Enum-rangering
  • Dato & Tid: Dato, Tid, Tid med tidssone, Tidsstempel, Varighet, Kalenderintervall
  • Nettverk & Identifikatorer: UUID, MAC, IP, IP-prefiks, Kanonisk nettverksprefiks, LSN
  • Sammensatte strukturer: Nestede tupler, Områder, og rå strukturelle encoderinger
  • Kollasjon: Unicode-kollasjonsnøkler og eksterne kanoniske tokener

SQL-typemapping er på linje med PostgreSQL 18 B-tree sorteringsregler. Typer avhengig av databankkataloger eller intern motortilstand håndteres ved å sende eksterne kanoniske tokener.

Strengkollasjon

Builder.String har standard til rå UTF-8 binær rekkefølge. For lokalitetsbevisst sortering tilbyr Schottky en trådsikker, uforanderlig Collator:

  • Deterministisk kollasjon: Encoderer kollasjonsnøkkelen sammen med rå UTF-8-byte for å tilby en avgjører når kollasjonsvekter er identiske.
  • Ikke-deterministisk kollasjon: Behandler kollasjons-likestilte strenger som identiske, og utelater den rå byte-avgjøreren.

Unicode- og profilversjoner bør spores i metadatas skjema. Hvis kollasjonsleverandører eller profilinnstillinger endres, må eksisterende nøkler gjenoppbygges.

Skjemastyring

Fordi Schottky-nøkler er rå, hoderløse byte-sekvenser, 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 forskjellige skjemaer eller dekoding mot et feilmatchet skjema bryter rekkefølgegarantier.

Ytelse og Lenker

På Go 1.27+ kan eksperimentell bærbar SIMD-akselerasjon aktiveres ved hjelp av GOEXPERIMENT=simd. Skalare og SIMD-stier produserer byte-identiske nøkler.