GoSuda

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

By Lemon Mint
views ...

Při implementaci klíč-hodnota úložišť a databázových indexů založených na LSM-tree nebo B-tree je často nutné kombinovat kompozitní pole do jediného bajtového klíče.

Standardní serializační formáty jako JSON nebo Protocol Buffers nejsou pro tento účel navrženy, protože jejich serializované bajtové výstupy nezachovávají přirozené řazení vyžadované beznaménkovými porovnáními po bajtech (bytes.Compare nebo memcmp).

Schottky je knihovna pro jazyk Go navržená k encodování více-typových kompozitních tuplů do bajtových klíčů zachovávajících řazení.

1go get gosuda.org/schottky@latest

Serializace versus řadicí klíče

Zaručení správného řazení po bajtech vyžaduje řešení několika nízkoúrovňových detailů reprezentace dat:

  • Celá čísla: Standardní kódování pomocí doplňku dvou ve formátu big-endian narušuje přirozené řazení kvůli znaménkovému bitu s nejvyšší váhou. Invertování znaménkového bitu je nezbytné pro správné porovnání beznaménkových bajtů.
  • Plovoucí čárka: Vyžaduje úpravy znaménkového bitu, invertované řazení pro záporné hodnoty a konzistentní zacházení s hodnotami NaN a -0.
  • Řetězce a řezové proměnné délky: Hranice polí musí být zachovány bez porušení řazení prefixů.
  • Požadavky na kompozitní klíč: Podpora pro nezávislé řazení ASC/DESC pro každé pole, oddělená pravidla NULLS FIRST/LAST, přísná lexikografická precedence (dřívější pole určují pořadí) a kompatibilita s prefixovým vyhledáváním.

Schottky převádí každou hodnotu na kanonický payload před aplikací značek přítomnosti a směrové orientace. Pro pole typu DESC je každý bajt payloadu ASC bitově invertován (^b). Umístění hodnot NULL je řešeno pomocí vyhrazených značek přítomnosti a funguje nezávisle na směru řazení.

Základní použití

Následující příklad vytváří kompozitní klíč sestávající z Account ID (ASC, NULLS LAST) a jména (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 poskytuje čtyři explicitní konfigurace řazení:

  • AscNullsFirst
  • AscNullsLast
  • DescNullsFirst
  • DescNullsLast

Pozicování NULL není nikdy odvozeno implicitně. Pokud je předána neplatná hodnota Order, builder zaznamená ErrInvalidOrder, která je vrácena při volání Key() nebo Err().

Prefixové vyhledávání a hranice rozsahu

Kompozitní klíče Schottky neobsahují žádné globální hlavičky, metadadata o počtu polí, typové značky ani trailery. Za předpokladu, že schéma je známo předem, jsou kódování polí jednoduše zřetězena.

Kvůli tomuto uspořádání tvoří encodované bajty vedoucích polí platný prefix pro vyhledávání v rozsahu. V příkladu výše lze accountPrefix použít přímo jako prefixový filtr pro prohledání všech záznamů, kde Account ID == 42.

Pro výpočet exkluzivní horní hranice pro polootevřené vyhledávání v rozsahu [prefix, upper) použijte 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        // Polootevřené [accountPrefix, upper) range scan
10} else {
11        // Neomezené otevřené range scan
12}

Poznámka: Builder.Len() musí být měřeno na čistých hranicích polí. Slicování uvnitř vnitřního bajtového proudu pole produkuje neplatný prefix.

Nulová alokace a správa vyrovnávací paměti

Generování klíčů často probíhá na kritických databázových cestách. Aby se eliminovaly alokace haldy a režie přizpůsobování velikosti bufferu, Builder pracuje striktně v rámci kapacity slice poskytnutého volajícím a nebude provádět vnitřní realokaci.

Pokud buffer vyčerpá svou kapacitu, zaznamená se ErrShortBuffer bez zápisu částečných bajtů. Zápisy polí jsou atomické a první zjištěná chyba je zachována, dokud není zkontrolována prostřednictvím Key() nebo Err(). Poskytnutí dostatečné kapacity předem zajišťuje kódování bez alokací.

Velikosti bufferů lze předem vypočítat pomocí pomocných funkcí, jako jsou EncodedBytesSize, EncodedStringSize a EncodedDecimalSize, nebo prostřednictvím konstant pevné velikosti. Vrácený klíč odkazuje přímo na poskytnutý buffer, což ponechává správu životního cyklu paměti na volajícím.

Decoder funguje symetricky: vypůjčuje si data přímo ze vstupního klíče, vyžaduje cílové buffery poskytnuté volajícím pro pole proměnné délky a poskytuje Remaining() == 0 pro detekci koncových bajtů nebo nesouladu schémat.

Podporované datové typy

  • Celá čísla: Se znaménkem i bez znaménka (8-bit až 64-bit), Int128
  • Plovoucí čárka a numerické typy: Float32, Float64, Decimal Text
  • Základní typy: Binární řetězec, Byte Slice, Boolean, Enum Rank
  • Datum a čas: Date, Time, Zoned Time, Timestamp, Duration, Calendar Interval
  • Síťové typy a identifikátory: UUID, MAC, IP, IP Prefix, Kanonický síťový prefix, LSN
  • Kompozitní struktury: Vnořené tuple, rozsahy a raw strukturální kódování
  • Kolace: Unicode Collation Keys a externí kanonické tokeny

Mapování typů SQL je sladěno s pravidly B-tree řazení v PostgreSQL 18. Typy závislé na databázových katalozích nebo vnitřním stavu engine jsou zpracovány předáním externích kanonických tokenů.

Kolace řetězců

Builder.String standardně používá raw UTF-8 binární pořadí. Pro řazení zohledňující národní prostředí poskytuje Schottky konkurentně bezpečný, neměnný Collator:

  • Deterministická kolace: Encoduje kolační klíč spolu s raw UTF-8 bajty pro poskytnutí rozhodujícího kritéria (tie-breaker), když jsou kolační váhy identické.
  • Nedeterministická kolace: Považuje řetězce se stejnou kolací za totožné, přičemž vynechává raw bajtový tie-breaker.

Verze Unicode a profilů by měly být sledovány v metadatovém schématu. Pokud se změní poskytovatelé kolace nebo nastavení profilu, existující klíče je nutné přebudovat.

Správa schématu

Jelikož klíče Schottky jsou raw bajtové sekvence bez hlavičky, vrstva schématu musí sledovat:

  1. Sekvenci polí a datové typy.
  2. Směry řazení (ASC/DESC) a řazení NULL (NULLS FIRST/LAST).
  3. Kolaci řetězců a normalizační pravidla.
  4. Verze profilů Schottky a Collation.

Porovnávání klíčů vygenerovaných s různými schématy nebo dekódování oproti neodpovídajícímu schématu porušuje záruky řazení.

Výkon a odkazy

V Go 1.27+ lze experimentální přenositelnou SIMD akceleraci povolit pomocí GOEXPERIMENT=simd. Skalární a SIMD cesty produkují bajtově identické klíče.