GoSuda

Schottky: Allokeringsfri, ordningsbevarande kodning av bytenycklar för Go

By Lemon Mint views ...

När man implementerar nyckel-värde-lager baserade på LSM-träd eller B-träd samt databasindex behöver sammansatta fält ofta kombineras till en enda byte-nyckel.

Standardiserade serialiseringsformat som JSON eller Protocol Buffers är inte utformade för detta ändamål, eftersom deras serialiserade bytesekvenser inte bevarar den naturliga sorteringsordningen som krävs för osignerade bytevisa jämförelser (bytes.Compare eller memcmp).

Schottky är ett Go-bibliotek utformat för att koda sammansatta tupler med flera typer till ordningsbevarande byte-nycklar.

1go get gosuda.org/schottky@latest

Serialisering kontra sorteringsnycklar

För att garantera korrekt bytevis sortering måste flera lågnivådetaljer i datarepresentationen hanteras:

  • Heltal: Standardkodning i tvåkomplement med big-endian bryter den naturliga ordningen på grund av den mest signifikanta teckenbiten. Inversion av teckenbiten är nödvändig för korrekta osignerade bytejämförelser.
  • Flyttal: Kräver justeringar av teckenbiten, omvänd ordning för negativa värden samt konsekvent hantering av NaN och -0.
  • Strängar och byteslices med variabel längd: Fältgränser måste bevaras utan att prefixens sorteringsordning bryts.
  • Krav på sammansatta nycklar: Stöd för oberoende ASC/DESC-ordning per fält, frikopplade regler för NULLS FIRST/LAST, strikt lexikografisk prioritet (tidigare fält avgör ordningen) samt kompatibilitet med prefixskanning.

Schottky omvandlar varje värde till en kanonisk nyttolast innan närvaromarkeringar och riktningsorientering tillämpas. För DESC-fält inverteras varje byte i ASC-nyttolasten bitvis (^b). NULL-placering hanteras via dedikerade närvaromarkeringar och är oberoende av sorteringsriktningen.

Grundläggande användning

Följande exempel bygger en sammansatt nyckel bestående av ett konto-ID (ASC, NULLS LAST) och ett namn (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 tillhandahåller fyra explicita konfigurationer för sorteringsordning:

  • AscNullsFirst
  • AscNullsLast
  • DescNullsFirst
  • DescNullsLast

NULL-positionering härleds aldrig implicit. Om ett ogiltigt Order-värde skickas registrerar builder ErrInvalidOrder, vilket returneras vid anrop av Key() eller Err().

Prefixskanning och intervallgränser

Schottky-nycklar innehåller inga globala huvuden, metadata om antal fält, typtaggar eller avslutningar. Förutsatt att schemat är känt i förväg sammanfogas fältkodningarna helt enkelt.

På grund av denna layout utgör de kodade bytena för ledande fält ett giltigt prefix för intervallskanningar. I exemplet ovan kan accountPrefix direkt användas som ett prefixfilter för att skanna alla poster där Account ID == 42.

För att beräkna den exklusiva övre gränsen för halvöppna intervallskanningar [prefix, upper) används 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öppen intervallskanning [accountPrefix, upper)
10} else {
11        // Obegränsad öppen intervallskanning
12}

Observera: Builder.Len() måste mätas vid rena fältgränser. Att skära inne i ett fälts interna bytesström ger ett ogiltigt prefix.

Nollallokering och bufferhantering

Nyckelgenerering körs ofta på kritiska databasvägar. För att eliminera heap-allokeringar och overhead från buffertomallokering arbetar Builder strikt inom kapaciteten hos den slice som anropande kod tillhandahåller och omallokerar aldrig internt.

Om bufferten får slut på kapacitet registreras ErrShortBuffer utan att några partiella bytes skrivs. Fältskrivningar är atomära, och det första fel som uppstår bevaras tills det kontrolleras via Key() eller Err(). Att tillhandahålla tillräcklig kapacitet i förväg säkerställer nollallokerande kodning.

Bufferstorlekar kan beräknas i förväg med hjälpfunktioner såsom EncodedBytesSize, EncodedStringSize och EncodedDecimalSize, eller via fasta konstanter. Den returnerade nyckeln refererar direkt till den tillhandahållna bufferten, och ansvaret för minneslivscykeln ligger hos anropande kod.

Decoder fungerar symmetriskt: den lånar direkt från indatanyckeln, kräver av anropande kod tillhandahållna destinationsbuffertar för fält med variabel längd, och tillhandahåller Remaining() == 0 för att upptäcka avslutande bytes eller schemafel.

Stödda datatyper

  • Heltal: Signerade och osignerade (8 till 64 bitar), Int128
  • Flyttal och numeriska värden: Float32, Float64, decimal text
  • Grundläggande typer: Binär sträng, byteslice, boolean, enum-rang
  • Datum och tid: Date, Time, Zoned Time, Timestamp, Duration, Calendar Interval
  • Nätverk och identifierare: UUID, MAC, IP, IP Prefix, Canonical Network Prefix, LSN
  • Sammansatta strukturer: Kapslade tupler, Ranges samt råa strukturella kodningar
  • Kollation: Unicode-kollationsnycklar och externa kanoniska tokens

SQL-typmappningen är anpassad till sorteringsreglerna för PostgreSQL 18 B-träd. Typer som beror av databaskataloger eller internt motortillstånd hanteras genom att externa kanoniska tokens skickas in.

Strängkollation

Builder.String används som standard med rå UTF-8-binärordning. För lokalmedveten sortering tillhandahåller Schottky en samtidighetssäker, oföränderlig Collator:

  • Deterministisk kollation: Kodar kollationsnyckeln tillsammans med rå UTF-8-bytes för att utgöra en tiebreaker när kollationsvikterna är identiska.
  • Icke-deterministisk kollation: Behandlar kollationsekvivalenta strängar som identiska och utelämnar den råa bytetiebreakern.

Unicode- och profilversioner bör spåras i metadataschemat. Om kollationsleverantörer eller profilinställningar ändras måste befintliga nycklar byggas om.

Schemahantering

Eftersom Schottky-nycklar är råa byte-sekvenser utan huvuden måste schemalagret spåra:

  1. Fältsekvens och datatyper.
  2. Sorteringsriktningar (ASC/DESC) och NULL-ordning (NULLS FIRST/LAST).
  3. Strängkollations- och normaliseringsregler.
  4. Versioner av Schottky- och kollationsprofiler.

Att jämföra nycklar genererade med olika scheman eller att avkoda mot ett avvikande schema bryter ordningsgarantierna.

Prestanda och länkar

På Go 1.27+ kan experimentell portabel SIMD-acceleration aktiveras med GOEXPERIMENT=simd. Skalära och SIMD-vägar producerar byte-identiska nycklar.