GoSuda

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

By Lemon Mint
views ...

Ved implementering af LSM-tree- eller B-tree-baserede nøgle-værdi-lagre og databaseindekser er det ofte nødvendigt at kombinere sammensatte felter til en enkelt bytenøgle.

Standardiseringsformater for serialisering såsom JSON eller Protocol Buffers er ikke designet til dette formål, fordi deres serialiserede byte-outputs ikke bevarer den naturlige sorteringsrækkefølge, der kræves af usignerede bytewise sammenligninger (bytes.Compare eller memcmp).

Schottky er et Go-bibliotek, der er designet til at kodetilpasse flerty-sammensatte tupler til rækkefølgebevarende bytenøgler.

1go get gosuda.org/schottky@latest

Serialisering vs. Sorteringsnøgler

Garantien for korrekt bytewise sortering kræver håndtering af flere lavniveau-datarepræsentationsdetaljer:

  • Heltal: Standard to'er-komplement big-endian-kodning bryder den naturlige rækkefølge på grund af det mest signifikante fortegnstegn. Invertering af fortegnstegnet er nødvendigt for korrekte usignerede byte-sammenligninger.
  • Flydende kommatal: Kræver justeringer af fortegnstegn, inverteret rækkefølge for negative værdier og konsekvent håndtering af NaN og -0.
  • Strenglængder med variabel længde og byte-snit: Feltgrænser skal bevares uden at bryde præfikssorteringsrækkefølger.
  • Krav til sammensatte nøgler: Understøttelse af uafhængig ASC/DESC-rækkefølge pr. felt, afkopplet NULLS FIRST/LAST-regler, streng leksikografisk præcedens (tidligere felter bestemmer rækkefølgen) og kompatibilitet med prædikatsøgning.

Schottky konverterer hver værdi til en kanonisk nyttelast, før tilstedeværelsestags og retningsbestemt orientering anvendes. For DESC-felter inverteres hver byte af ASC-nyttelasten bitvis (^b). NULL-placering håndteres via dedikerede tilstedeværelsestags og fungerer uafhængigt af sorteringsretningen.

Grundlæggende Anvendelse

Følgende eksempel bygger en sammensat nøgle bestående af et Account 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 leverer fire eksplicitte sorteringsrækkefølgekonfigurationer:

  • AscNullsFirst
  • AscNullsLast
  • DescNullsFirst
  • DescNullsLast

NULL-positionering udledes aldrig implicit. Hvis der videregives en ugyldig Order-værdi, registrerer builder-objektet ErrInvalidOrder, som returneres ved kald til Key() eller Err().

Prædikatsøgning og Områdegrænser

Schottky sammensatte nøgler indeholder ingen globale overskrifter, feltantal-metadata, typetags eller trailers. Under forudsætning af at skemaet er kendt på forhånd, samkøres feltkodningerne blot.

På grund af dette layout danner de kodede bytes af de foranstående felter et gyldigt præfiks for omfangssøgninger. I eksemplet ovenfor kan accountPrefix bruges direkte som et præfiksfilter til at gennemse alle poster, hvor Account ID == 42.

For at beregne den eksklusive øvre grænse for halvåbne [prefix, upper) omfangssøgninger bruges 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åben [accountPrefix, upper) omfangssøgning
10} else {
11        // Uafgrænset åben omfangssøgning
12}

Bemærk: Builder.Len() skal måles ved rene feltgrænser. Udskæring inde i et felts interne bytestrøm producerer et ugyldigt præfiks.

Nul-Allokering og Bufferhåndtering

Nøglegenerering kører ofte på kritiske databasestier. For at eliminere heap-allokeringer og overhead ved buffer-skalering arbejder Builder strengt inden for kapaciteten af det af kalderen leverede snit og vil ikke genallokere internt.

Hvis bufferen løber tør for kapacitet, registreres ErrShortBuffer uden at skrive delvise bytes. Feltkørsler er atomare, og den første opståede fejl bevares, indtil den kontrolleres via Key() eller Err(). Tilvejebringelse af tilstrækkelig kapacitet på forhånd sikrer nul-allokeringskodning.

Bufferstørrelser kan beregnes på forhånd ved hjælp af hjælpefunktioner som EncodedBytesSize, EncodedStringSize og EncodedDecimalSize, eller via konstanter med fast størrelse. Den returnerede nøgle refererer direkte til den leverede buffer, hvilket overlader hukommelsens livscyklusadministration til kalderen.

Decoder-objektet fungerer symmetrisk: det låner direkte fra inputnøglen, kræver kalder-leverede destinationsbuffer til felter med variabel længde og leverer Remaining() == 0 til at detektere efterfølgende bytes eller skemafejlmatcher.

Understøttede Datatyper

  • Heltal: Signerede og Usignerede (8-bit til 64-bit), Int128
  • Flydende Kommatal & Numeriske: Float32, Float64, Decimaltekst
  • Basistyper: Binær streng, Bytesnit, Booleansk, Enum-rang
  • Dato & Tid: Dato, Tid, Zonet tid, Tidsstempel, Varighed, Kalenderinterval
  • Netværk & Identifikatorer: UUID, MAC, IP, IP-præfiks, Kanonisk netværkspræfiks, LSN
  • Sammensatte Strukturer: Indlejrede tupler, Områder og rå strukturelle kodninger
  • Kollation: Unicode-kollationsnøgler og eksterne kanoniske tokens

SQL-typetilknytning er afstemt efter PostgreSQL 18 B-tree-sorteringsregler. Typer, der er afhængige af databankataloger eller intern motortilstand, håndteres ved at overføre eksterne kanoniske tokens.

Strengkollation

Builder.String er som standard indstillet til rå UTF-8 binær rækkefølge. Til lokalitetsbevidst sortering leverer Schottky en trådsikker, uforanderlig Collator:

  • Deterministisk Kollation: Koder kollationsnøglen sammen med rå UTF-8 bytes for at levere en afgørelse, når kollationsvægte er identiske.
  • Ikke-deterministisk Kollation: Behandler kollations-ligemæssige strenge som identiske og udelader den rå byte-afgørelse.

Unicode- og profilversioner bør spores i metadatakemaet. Hvis kollationsudbydere eller profilindstillinger ændres, skal eksisterende nøgler genopbygges.

Skemastyring

Da Schottky-nøgler er rå, overskriftsløse bytesekvenser, skal skemalaget spore:

  1. Feltsekvens og datatyper.
  2. Sorteringsretninger (ASC/DESC) og NULL-sortering (NULLS FIRST/LAST).
  3. Strengkollations- og normaliseringsregler.
  4. Schottky- og Kollationsprofilversioner.

Sammenligning af nøgler genereret med forskellige skemaer eller dekodning mod et uoverensstemmende skema bryder sorteringsgarantier.

Ydeevne og Links

På Go 1.27+ kan eksperimentel bærbar SIMD-acceleration aktiveres ved hjælp af GOEXPERIMENT=simd. Skalare og SIMD-stier producerer byte-identiske nøgler.