GoSuda

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

By Lemon Mint views ...

Når der implementeres LSM-træ- eller B-træbaserede nøgle-værdi-lagre og databaseindekser, skal sammensatte felter ofte kombineres til en enkelt byte-nøgle.

Standardiserede serialiseringsformater såsom JSON eller Protocol Buffers er ikke designet til dette formål, fordi deres serialiserede byte-output ikke bevarer den naturlige sorteringsrækkefølge, som kræves af usignerede bytevise sammenligninger (bytes.Compare eller memcmp).

Schottky er et Go-bibliotek designet til at kode sammensatte tupler af flere typer til ordensbevarende byte-nøgler.

1go get gosuda.org/schottky@latest

Serialisering vs. sorteringsnøgler

Sikring af korrekt bytevis sortering kræver håndtering af flere lavniveau-detaljer i datarepræsentationen:

  • Heltal: Standard big-endian-kodning i totalkomplement bryder den naturlige orden på grund af det mest betydende fortegnsbit. Invertering af fortegnsbittet er nødvendig for korrekte usignerede bytesammenligninger.
  • Flydende kommatal: Kræver justeringer af fortegnsbittet, invsome rækkefølge for negative værdier og konsistent håndtering af NaN og -0.
  • Strenge og byte-slices med variabel længde: Feltgrænser skal bevares uden at bryde præfiks-sorteringsrækkefølger.
  • Krav til sammensatte nøgler: Understøttelse af uafhængig ASC/DESC-sortering pr. felt, afkoblede NULLS FIRST/LAST-regler, streng leksikografisk prioritet (tidligere felter bestemmer rækkefølgen) og kompatibilitet med præfiksscanninger.

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

Grundlæggende brug

Følgende eksempel bygger en sammensat nøgle bestående af et 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 tilbyder fire eksplicitte sorteringskonfigurationer:

  • AscNullsFirst
  • AscNullsLast
  • DescNullsFirst
  • DescNullsLast

NULL-positionering udledes aldrig implicit. Hvis en ugyldig Order-værdi sendes, registrerer builderen ErrInvalidOrder, som returneres ved kald af Key() eller Err().

Præfiksscanning og intervalgrænser

Schottky-sammensatte nøgler indeholder ingen globale headere, feltantalsmetadata, typemarkører eller afsluttere. Forudsat at skemaet er kendt på forhånd, sammenkædes feltkodninger blot.

På grund af denne layout danner de kodede bytes fra førende felter et gyldigt præfiks for intervalscanninger. I eksemplet ovenfor kan accountPrefix direkte anvendes som præfiksfilter til at scanne alle poster, hvor Account ID == 42.

For at beregne den eksklusive øvre grænse for halvåbne [prefix, upper)-intervalscanninger anvendes 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åbent [accountPrefix, upper) intervalscanning
10} else {
11        // Ubegrænset åbent intervalscanning
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 buffergenstørrelse arbejder Builder strengt inden for kapaciteten af den slice, som kaldes leverer, og omallokerer ikke internt.

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

Bufferstørrelser kan beregnes på forhånd ved hjælp af hjælpefunktioner såsom EncodedBytesSize, EncodedStringSize og EncodedDecimalSize, eller via faste konstanter. Den returnerede nøgle refererer direkte til den angivne buffer, og hukommelsens livscyklus overlades til kalderen.

Decoder fungerer symmetrisk: den låner direkte fra inputnøglen, kræver kalderleverede destinationsbuffere for felter med variabel længde og tilbyder Remaining() == 0 til at registrere efterfølgende bytes eller skemamismatch.

Understøttede datatyper

  • Heltal: Signerede og usignerede (8-bit til 64-bit), Int128
  • Flydende kommatal og numeriske værdier: Float32, Float64, decimal tekst
  • Grundlæggende typer: Binær streng, byte-slice, boolean, enum-rang
  • Dato og tid: Dato, tid, zonet tid, tidsstempel, varighed, kalenderinterval
  • Netværk og identifikatorer: UUID, MAC, IP, IP-præfiks, kanonisk netværkspræfiks, LSN
  • Sammensatte strukturer: Indlejrede tupler, intervaller og rå strukturelle kodninger
  • Kollation: Unicode-kollationsnøgler og eksterne kanoniske tokens

SQL-typemapping er tilpasset PostgreSQL 18 B-træ-sorteringsregler. Typer, der afhænger af databasekataloger eller interne motortilstande, håndteres ved at sende eksterne kanoniske tokens.

Strengkollation

Builder.String anvender som standard rå UTF-8-binær orden. Til lokalesensitiv sortering tilbyder Schottky en samtidighedssikker, uforanderlig Collator:

  • Deterministisk kollation: Kodes kollationsnøglen sammen med rå UTF-8-bytes for at fungere som udligningsregel, når kollationsvægte er identiske.
  • Ikke-deterministisk kollation: Behandler kollationsligestillede strenge som identiske og udelader den rå byte-udligningsregel.

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

Skemahåndtering

Fordi Schottky-nøgler er rå byte-sekvenser uden headere, skal skemalaget spore:

  1. Feltsekvens og datatyper.
  2. Sorteringsretninger (ASC/DESC) og NULL-rækkefølge (NULLS FIRST/LAST).
  3. Strengkollation og normaliseringsregler.
  4. Schottky- og kollationsprofilversioner.

Sammenligning af nøgler genereret med forskellige skemaer, eller afkodning mod et uoverensstemmende skema, bryder rækkefølgegarantierne.

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.