GoSuda

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

By Lemon Mint views ...

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

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

Schottky je knihovna pro jazyk Go navržená pro kódování vícetypových složených n-tic do bajtových klíčů zachovávajících pořadí.

1go get gosuda.org/schottky@latest

Serializace versus klíče pro řazení

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

  • Celá čísla: Standardní kódování dvojkového doplňku v big-endian narušuje přirozené řazení kvůli nejvýznamnějšímu znaménkovému bitu. Pro správná neznaménková bajtová porovnání je nezbytné invertovat znaménkový bit.
  • Čísla s plovoucí desetinnou čárkou: Vyžadují úpravy znaménkového bitu, obrácené řazení záporných hodnot a konzistentní zpracování hodnot NaN a -0.
  • Řetězce a bajtové řezy proměnné délky: Hranice polí musí být zachovány bez narušení prefixového řazení.
  • Požadavky na složené klíče: Podpora nezávislého řazení ASC/DESC pro každé pole, oddělená pravidla NULLS FIRST/LAST, striktní lexikografická priorita (dřívější pole určují pořadí) a kompatibilita s prefixovým skenováním.

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

Základní použití

Následující příklad vytváří složený klíč sestávající z ID účtu (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 směru řazení:

  • AscNullsFirst
  • AscNullsLast
  • DescNullsFirst
  • DescNullsLast

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

Prefixové skenování a hranice rozsahu

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

Vzhledem k tomuto uspořádání tvoří zakódované bajty vedoucích polí platný prefix pro rozsahové skeny. Ve výše uvedeném příkladu lze accountPrefix přímo použít jako prefixový filtr pro skenování všech záznamů, kde ID účtu == 42.

Pro výpočet exkluzivní horní hranice pro polouzavřené rozsahové skeny [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        // Polouzavřený rozsah skenování [accountPrefix, upper)
10} else {
11        // Neohraničený otevřený rozsah skenování
12}

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

Nulová alokace a správa bufferů

Generování klíčů často probíhá na kritických databázových cestách. Aby se eliminovaly alokace na haldě a režie spojená se změnou velikosti bufferu, Builder pracuje striktně v rámci kapacity řezu poskytnutého volajícím a interně nealokuje znovu.

Pokud buffer vyčerpá kapacitu, zaznamená se ErrShortBuffer bez zápisu částečných bajtů. Zápisy polí jsou atomické a první zjištěná chyba je uchována až do kontroly přes 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 pomocí pevných konstant. Vrácený klíč odkazuje přímo na poskytnutý buffer a správa životního cyklu paměti zůstává na volajícím.

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

Podporované datové typy

  • Celá čísla: Se znaménkem i bez znaménka (8 až 64 bitů), Int128
  • Čísla s plovoucí desetinnou čárkou a numerické typy: Float32, Float64, desetinný text
  • Základní typy: Binární řetězec, bajtový řez, Boolean, Enum Rank
  • Datum a čas: Date, Time, Zoned Time, Timestamp, Duration, Calendar Interval
  • Síť a identifikátory: UUID, MAC, IP, IP Prefix, Canonical Network Prefix, LSN
  • Složené struktury: Vnořené n-tice, Ranges a surová strukturální kódování
  • Kolace: Unicode Collation Keys a externí kanonické tokeny

Mapování typů SQL je sladěno s pravidly řazení B-stromů PostgreSQL 18. Typy závislé na databázových katalozích nebo na interním stavu enginu se zpracovávají předáním externích kanonických tokenů.

Řazení řetězců

Builder.String ve výchozím nastavení používá řazení surového UTF-8 binárně. Pro řazení respektující locale poskytuje Schottky souběžně bezpečný a neměnný Collator:

  • Deterministická kolace: Kóduje klíč kolace spolu se surovými bajty UTF-8, aby poskytla rozhodovací kritérium v případě shodných vah kolace.
  • Nedeterministická kolace: Považuje řetězce shodné podle kolace za identické a vynechává rozhodovací kritérium na úrovni surových bajtů.

Verze Unicode a profilu by měly být evidovány v metadatech schématu. Pokud se změní poskytovatelé kolace nebo nastavení profilu, je nutné existující klíče znovu sestavit.

Správa schématu

Protože klíče Schottky jsou surové bajtové sekvence bez hlaviček, musí vrstva schématu evidovat:

  1. Sekvenci polí a datové typy.
  2. Směry řazení (ASC/DESC) a řazení NULL (NULLS FIRST/LAST).
  3. Pravidla kolace a normalizace řetězců.
  4. Verze profilů Schottky a kolace.

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

Výkon a odkazy

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