GoSuda

Schottky: Zero-Allocation, Order-Preserving Byte-Key Encoding för Go

By Lemon Mint
views ...

Vid implementering av LSM-träd- eller B-träd-baserade nyckel-värde-lager och databasindex behöver sammansatta fält ofta kombineras till en enda bytenyckel.

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

Schottky är ett Go-bibliotek som är utformat för att koda sammansatta tupler av flera typer till ordningsbevarande bytenycklar.

1go get gosuda.org/schottky@latest

Serialisering kontra sorteringsnycklar

För att garantera korrekt bytevis sortering krävs det att man hanterar flera detaljer på låg nivå gällande datarepresentation:

  • Heltal: Standardiserad big-endian-kodning med tvåkomplement bryter den naturliga ordningen på grund av den mest signifikanta teckenbiten. Det är nödvändigt att invertera teckenbiten för att uppnå korrekta osignerade bytejämförelser.
  • Flyttal: Kräver justeringar av teckenbiten, inverterad ordning för negativa värden samt konsekvent hantering av NaN och -0.
  • Variabellängdssträngar och bytesekvenser: Fältgränser måste bevaras utan att prefixets sorteringsordning bryts.
  • Krav på sammansatta nycklar: Stöd för oberoende ASC/DESC-ordning per fält, fristående regler för NULLS FIRST/LAST, strikt lexikografisk prioritet (tidigare fält avgör ordningen) samt kompatibilitet med prefixsökning.

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

Grundläggande användning

Följande exempel bygger en sammansatt nyckel som består 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

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

Prefixsökning och intervallgränser

Sammansatta Schottky-nycklar innehåller inga globala huvuden, metadata om fältantal, typetaggar eller svansar. Förutsatt att schemat är känt i förväg sammanfogas fältkodningarna helt enkelt.

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

För att beräkna den exklusiva övre gränsen för halvöppna intervallsökningar [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 [accountPrefix, upper) intervallsökning
10} else {
11        // Obunden öppen intervallsökning
12}

Obs: Builder.Len() måste mätas vid rena fältgränser. Att skiva inuti ett fälts interna byteströmmar ger ett ogiltigt prefix.

Nollallokering och buffertthantering

Nyckelgenerering körs frekvent på kritiska databasvägar. För att eliminera allokeringar på heapen och overhead för storleksändring av buffertar arbetar Builder uteslutande inom kapaciteten för den buffert som tillhandahållits av anroparen och kommer inte att göra omallokeringar internt.

Om bufferten får slut på kapacitet registreras ErrShortBuffer utan att partiella byte skrivs. Fältskrivningar är atomära, och det första påträffade felet bevaras tills det kontrolleras via Key() eller Err(). Genom att tillhandahålla tillräcklig kapacitet från början säkerställs nollallokeringskodning.

Buffertstorlekar kan beräknas i förväg med hjälp av hjälpfunktioner som EncodedBytesSize, EncodedStringSize och EncodedDecimalSize, eller via konstanter med fast storlek. Den returnerade nyckeln refererar direkt till den tillhandahållna bufferten, vilket överlåter hanteringen av minnets livscykel till anroparen.

Decoder fungerar på ett symmetriskt sätt: den lånar direkt från indatanyckeln, kräver destinationsbuffertar för fält med variabel längd från anroparen och tillhandahåller Remaining() == 0 för att upptäcka efterföljande byte eller schemafelaktigheter.

Datatyper som stöds

  • Heltal: Signerade och osignerade (8-bitars till 64-bitars), Int128
  • Flyttal och numeriska typer: Float32, Float64, decimaltext
  • Grundläggande typer: Binär sträng, bytesekvens, booleskt värde, enums rangordning
  • Datum och tid: Datum, tid, tidszonstestad tid, tidsstämpel, tidsrymd, kalenderintervall
  • Nätverk och identifierare: UUID, MAC, IP, IP-prefix, kanoniskt nätverksprefix, LSN
  • Sammansatta strukturer: Kapslade tupler, intervall och råa strukturella kodningar
  • Kollationering: Unicode-kollationsnycklar och externa kanoniska token

Mappning av SQL-typer är anpassad till PostgreSQL 18:s B-trädssorteringsregler. Typer som är beroende av databaskataloger eller internt motortillstånd hanteras genom att externa kanoniska token skickas med.

Strängkollationering

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

  • Deterministisk kollationering: Kodas kollationsnyckeln tillsammans med råa UTF-8-byte för att tillhandahålla en tie-breaker när kollationsvikterna är identiska.
  • Icke-deterministisk kollationering: Behandlar kollationslika strängar som identiska och utelämnar den råa bytetie-breakern.

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

Scheurahantering

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

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

Jämförelse av nycklar som genererats med olika scheman eller avkodning mot ett felaktigt schema bryter mot ordningsgarantierna.

Prestanda och länkar

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