GoSuda

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

By Lemon Mint
views ...

Bij het implementeren van op LSM-tree of B-tree gebaseerde key-value stores en database-indexen moeten samengestelde velden vaak worden gecombineerd tot één enkele byte-key.

Standaard serialisatieformaten zoals JSON of Protocol Buffers zijn niet ontworpen voor dit doel omdat hun geserialiseerde byte-uitvoer niet de natuurlijke sortering volgorde behoudt die vereist is door unsigned bytewise vergelijkingen (bytes.Compare of memcmp).

Schottky is een Go library ontworpen om multi-type samengestelde tuples te encoderen naar order-preserving byte keys.

1go get gosuda.org/schottky@latest

Serialization vs. Sort Keys

Het garanderen van correcte bytewise sortering vereist het adresseren van verschillende low-level data-representatiedetails:

  • Integers: Standaard two's complement big-endian encodering verbreekt de natuurlijke volgorde vanwege de most significant sign bit. Het inverteren van de sign bit is noodzakelijk voor correcte unsigned byte vergelijkingen.
  • Floating-point numbers: Vereist sign bit aanpassingen, geïnverteerde volgorde voor negatieve waarden en consistente behandeling van NaN en -0.
  • Variable-length strings en byte slices: Veldgrenzen moeten behouden blijven zonder prefix sort orders te verbreken.
  • Composite key requirements: Ondersteuning voor onafhankelijke ASC/DESC sortering per veld, ontkoppelde NULLS FIRST/LAST regels, strikte lexicografische precedentie (eerdere velden bepalen de volgorde) en compatibiliteit met prefix scanning.

Schottky converteert elke waarde naar een canonical payload voordat presence tags en directional orientation worden toegepast. Voor DESC velden wordt elke byte van de ASC payload bitwise geïnverteerd (^b). NULL plaatsing wordt afgehandeld via dedicated presence tags en werkt onafhankelijk van de sort direction.

Basic Usage

Het volgende voorbeeld bouwt een composite key bestaande uit een Account ID (ASC, NULLS LAST) en een Name (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 sort order configuraties:

  • AscNullsFirst
  • AscNullsLast
  • DescNullsFirst
  • DescNullsLast

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

Prefix Scanning and Range Bounds

Schottky composite keys bevatten geen globale headers, field count metadata, type tags of trailers. Aannemende dat het schema van tevoren bekend is, worden veldencoderingen simpelweg geconcateneerd.

Vanwege deze layout vormen de geencodeerde bytes van leading fields een valide prefix voor range scans. In het bovenstaande voorbeeld kan accountPrefix direct worden gebruikt als een prefix filter om alle records te scannen waar Account ID == 42.

Om de exclusieve upper bound te berekenen voor half-open [prefix, upper) range scans, gebruikt u 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) range scan
10} else {
11        // Unbounded open range scan
12}

Opmerking: Builder.Len() moet worden gemeten op schone veldgrenzen. Slicing binnen de interne byte stream van een veld produceert een ongeldige prefix.

Zero-Allocation and Buffer Management

Key generation draait frequent op kritieke database paden. Om heap allocaties en buffer resizing overhead te elimineren, werkt Builder strikt binnen de capaciteit van de door de aanroeper verstrekte slice en zal deze niet intern heralloceren.

Als de capaciteit van de buffer op is, wordt ErrShortBuffer geregistreerd zonder partiële bytes te schrijven. Veldweergaven zijn atomic, en de eerst aangetroffen fout blijft behouden totdat deze wordt gecontroleerd via Key() of Err(). Het vooraf verstrekken van voldoende capaciteit zorgt voor zero-allocation encodering.

Buffergroottes kunnen vooraf worden berekend met behulp van helperfuncties zoals EncodedBytesSize, EncodedStringSize en EncodedDecimalSize, of via fixed-size constanten. De geretourneerde key refereert direct naar de verstrekte buffer, waardoor memory lifecycle management aan de aanroeper wordt gelaten.

De Decoder werkt symmetrisch: hij leent direct van de input key, vereist door de aanroeper verstrekte destination buffers voor variable-length velden, en biedt Remaining() == 0 om trailing bytes of schema mismatches te detecteren.

Supported Data Types

  • Integers: Signed en Unsigned (8-bit tot 64-bit), Int128
  • Floating-Point & Numerics: Float32, Float64, Decimal Text
  • Basic Types: Binary String, Byte Slice, Boolean, Enum Rank
  • Date & Time: Date, Time, Zoned Time, Timestamp, Duration, Calendar Interval
  • Network & Identifiers: UUID, MAC, IP, IP Prefix, Canonical Network Prefix, LSN
  • Composite Structures: Nested Tuples, Ranges en raw structural encodings
  • Collation: Unicode Collation Keys en externe canonical tokens

SQL type mapping is afgestemd op PostgreSQL 18 B-tree sortering regels. Typen die afhankelijk zijn van database catalogi of interne engine state worden afgehandeld door het doorgeven van externe canonical tokens.

String Collation

Builder.String valt standaard terug op raw UTF-8 binary order. Voor locale-aware sortering biedt Schottky een concurrent-safe, immutable Collator:

  • Deterministic Collation: Encodeert de collation key naast raw UTF-8 bytes om een tie-breaker te bieden wanneer collation weights identiek zijn.
  • Nondeterministic Collation: Behandelt collation-equal strings als identiek, waarbij de raw byte tie-breaker wordt weggelaten.

Unicode en profile versies moeten worden bijgehouden in het metadata schema. Als collation providers of profile settings wijzigen, moeten bestaande keys opnieuw worden opgebouwd.

Schema Management

Omdat Schottky keys rauwe, headerloze byte sequenties zijn, moet de schemalaag het volgende bijhouden:

  1. Field sequence en data types.
  2. Sort directions (ASC/DESC) en NULL sortering (NULLS FIRST/LAST).
  3. String collation en normalisatie regels.
  4. Schottky en Collation profile versies.

Het vergelijken van keys gegenereerd met verschillende schema's of decoderen tegen een afwijkend schema verbreekt de sortering garanties.

Performance and Links

Op Go 1.27+ kan experimentele portable SIMD acceleration worden ingeschakeld met GOEXPERIMENT=simd. Scalar en SIMD paden produceren byte-identieke keys.