GoSuda

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

By Lemon Mint views ...

Wanneer LSM-tree- of B-tree-gebaseerde key-value stores en databaseindexen worden geïmplementeerd, moeten samengestelde velden vaak worden gecombineerd tot één enkele bytesleutel.

Standaard serialisatieformaten zoals JSON of Protocol Buffers zijn niet ontworpen voor dit doel, omdat hun geserialiseerde byte-uitvoer de natuurlijke sorteervolgorde niet behoudt die vereist is voor ongetekende bytevergelijkingen (bytes.Compare of memcmp).

Schottky is een Go-bibliotheek die is ontworpen om samengestelde tupels met meerdere typen te coderen in ordebehoudende bytesleutels.

1go get gosuda.org/schottky@latest

Serialisatie versus sorteersleutels

Het garanderen van correcte bytesgewijze sortering vereist het adresseren van verschillende representatiedetails op laag niveau:

  • Gehele getallen: Standaard big-endian codering in twee's complement breekt de natuurlijke ordening vanwege het meest significante tekenbit. Het inverteren van het tekenbit is noodzakelijk voor correcte ongetekende bytevergelijkingen.
  • Drijvendekommagetallen: Vereist aanpassingen van het tekenbit, een omgekeerde ordening voor negatieve waarden en een consistente behandeling van NaN en -0.
  • Variabele-lengte strings en byteslices: Veldgrenzen moeten worden behouden zonder de prefix-sorteervolgordes te verstoren.
  • Vereisten voor samengestelde sleutels: Ondersteuning voor onafhankelijke ASC/DESC-ordening per veld, losgekoppelde NULLS FIRST/LAST-regels, strikte lexicografische prioriteit (eerdere velden bepalen de ordening) en compatibiliteit met prefix-scanning.

Schottky zet elke waarde om in een canonieke payload voordat presence-tags en richtingsoriëntatie worden toegepast. Voor DESC-velden wordt elke byte van de ASC-payload bitsgewijs geïnverteerd (^b). NULL-plaatsing wordt afgehandeld via speciale presence-tags en werkt onafhankelijk van de sorteerrichting.

Basisgebruik

Het volgende voorbeeld bouwt een samengestelde sleutel bestaande uit een Account-ID (ASC, NULLS LAST) en een Naam (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 biedt vier expliciete sorteervolgorde-configuraties:

  • AscNullsFirst
  • AscNullsLast
  • DescNullsFirst
  • DescNullsLast

NULL-positionering wordt nooit impliciet afgeleid. Als een ongeldige Order-waarde wordt doorgegeven, registreert de builder ErrInvalidOrder, dat wordt geretourneerd bij het aanroepen van Key() of Err().

Prefix-scanning en bereikgrenzen

Schottky-samengestelde sleutels bevatten geen globale headers, veldtelling-metadata, typetags of trailers. Ervan uitgaande dat het schema vooraf bekend is, worden veldcoderingen eenvoudigweg aaneengeschakeld.

Door deze opbouw vormen de gecodeerde bytes van voorste velden een geldig prefix voor bereikscans. In het bovenstaande voorbeeld kan accountPrefix direct worden gebruikt als prefixfilter om alle records te scannen waarvoor Account ID == 42 geldt.

Om de exclusieve bovengrens te berekenen voor half-open [prefix, upper)-bereikscans, gebruik 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        // Half-open [accountPrefix, upper) bereikscan
10} else {
11        // Onbegrensde open bereikscan
12}

Opmerking: Builder.Len() moet worden gemeten op schone veldgrenzen. Slicing binnen de interne bytestroom van een veld levert een ongeldig prefix op.

Nulallocatie en bufferbeheer

Sleutelgeneratie draait vaak op kritieke databasepaden. Om heap-allocaties en de overhead van bufferherschaling te elimineren, werkt Builder strikt binnen de capaciteit van de door de aanroeper verstrekte slice en zal intern niet opnieuw alloceren.

Als de buffer geen capaciteit meer heeft, wordt ErrShortBuffer geregistreerd zonder gedeeltelijke bytes te schrijven. Veldschrijfacties zijn atomair, en de eerste fout die wordt tegengekomen, blijft bewaard totdat deze wordt gecontroleerd via Key() of Err(). Het vooraf voorzien van voldoende capaciteit zorgt voor nulallocatiecodering.

Buffergroottes kunnen vooraf worden berekend met behulp van hulpfuncties zoals EncodedBytesSize, EncodedStringSize en EncodedDecimalSize, of via vaste constanten. De geretourneerde sleutel verwijst rechtstreeks naar de verstrekte buffer, waarbij het beheer van de geheugenlevensduur bij de aanroeper ligt.

De Decoder werkt symmetrisch: hij leent direct van de invoersleutel, vereist door de aanroeper verstrekte doelbuffers voor velden met variabele lengte, en biedt Remaining() == 0 om overtollige bytes of schemadiscrepanties te detecteren.

Ondersteunde gegevenstypen

  • Gehele getallen: Ondertekend en ongetekend (8-bit tot 64-bit), Int128
  • Drijvendekomma & numerieke waarden: Float32, Float64, Decimale tekst
  • Basistypen: Binaire string, byteslice, boolean, enum-rang
  • Datum en tijd: Datum, tijd, tijd met zone, timestamp, duur, kalenderinterval
  • Netwerk en identifiers: UUID, MAC, IP, IP-prefix, canoniek netwerkprefix, LSN
  • Samengestelde structuren: Geneste tupels, bereiken en ruwe structurele coderingen
  • Collatie: Unicode-collatiesleutels en externe canonieke tokens

SQL-typetoewijzing is afgestemd op de B-tree-sorteerregels van PostgreSQL 18. Typen die afhankelijk zijn van databasecatalogi of interne engine-status, worden afgehandeld door externe canonieke tokens door te geven.

Stringcollatie

Builder.String gebruikt standaard de ruwe UTF-8-binaire volgorde. Voor locale-bewuste sortering biedt Schottky een concurrent-veilige, onveranderlijke Collator:

  • Deterministische collatie: Codeert de collatiesleutel naast de ruwe UTF-8-bytes om een tie-breaker te bieden wanneer collatiegewichten identiek zijn.
  • Niet-deterministische collatie: Behandelt collatie-gelijke strings als identiek, waarbij de ruwe byte-tie-breaker wordt weggelaten.

Unicode- en profielversies moeten worden bijgehouden in het metadataschema. Als collatieproviders of profielinstellingen veranderen, moeten bestaande sleutels opnieuw worden opgebouwd.

Schemabeheer

Omdat Schottky-sleutels ruwe, headerloze bytesreeksen zijn, moet de schemalaag het volgende bijhouden:

  1. Veldvolgorde en gegevenstypen.
  2. Sorteerrichtingen (ASC/DESC) en NULL-ordening (NULLS FIRST/LAST).
  3. Stringcollatie- en normalisatieregels.
  4. Schottky- en collatieprofielversies.

Het vergelijken van sleutels die met verschillende schema's zijn gegenereerd, of het decoderen met een niet-overeenkomend schema, doorbreekt de ordeningsgaranties.

Prestaties en links

Op Go 1.27+ kan experimentele draagbare SIMD-versnelling worden ingeschakeld met GOEXPERIMENT=simd. Scalaire en SIMD-paden produceren byte-identieke sleutels.