GoSuda

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

By Lemon Mint views ...

Pri implementácii úložísk kľúč-hodnota založených na LSM-stromoch alebo B-stromoch a databázových indexoch je často potrebné skombinovať zložené polia do jedného bajtového kľúča.

Štandardné serializačné formáty, ako sú JSON alebo Protocol Buffers, nie sú navrhnuté na tento účel, pretože ich serializované bajtové výstupy nezachovávajú prirodzené poradie triedenia vyžadované nepodpísanými bajtovými porovnaniami (bytes.Compare alebo memcmp).

Schottky je knižnica pre jazyk Go navrhnutá na kódovanie viactypových zložených n-tic do bajtových kľúčov zachovávajúcich poradie.

1go get gosuda.org/schottky@latest

Serializácia vs. triediace kľúče

Zaručenie správneho bajtového triedenia vyžaduje riešenie niekoľkých nízkoúrovňových detailov reprezentácie dát:

  • Celé čísla: Štandardné big-endian kódovanie v dvojkovom doplnku narúša prirodzené poradie kvôli najvýznamnejšiemu bitu znamienka. Na správne nepodpísané bajtové porovnania je nevyhnutné invertovanie bitu znamienka.
  • Čísla s pohyblivou desatinnou čiarkou: Vyžadujú úpravy bitu znamienka, obrátené poradie pre záporné hodnoty a konzistentné spracovanie hodnôt NaN a -0.
  • Reťazce a bajtové rezy premenlivej dĺžky: Hranice polí musia byť zachované bez narušenia poradia prefixového triedenia.
  • Požiadavky na zložené kľúče: Podpora nezávislého poradia ASC/DESC pre jednotlivé polia, oddelené pravidlá NULLS FIRST/LAST, striktná lexikografická precedencia (skoršie polia určujú poradie) a kompatibilita s prefixovým skenovaním.

Schottky prevádza každú hodnotu na kanonický užitočný obsah pred aplikovaním značiek prítomnosti a smerovej orientácie. Pri poliach DESC je každý bajt užitočného obsahu ASC bitovo invertovaný (^b). Umiestnenie NULL sa zabezpečuje pomocou vyhradených značiek prítomnosti a je nezávislé od smeru triedenia.

Základné použitie

Nasledujúci príklad vytvára zložený kľúč pozostávajúci z ID účtu (ASC, NULLS LAST) a mena (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 štyri explicitné konfigurácie poradia triedenia:

  • AscNullsFirst
  • AscNullsLast
  • DescNullsFirst
  • DescNullsLast

Umiestnenie NULL sa nikdy neodvodzuje implicitne. Ak je odovzdaná neplatná hodnota Order, builder zaznamená ErrInvalidOrder, ktorá sa vráti pri volaní Key() alebo Err().

Prefixové skenovanie a hranice rozsahov

Zložené kľúče Schottky neobsahujú globálne hlavičky, metadáta o počte polí, typové značky ani záverečné časti. Za predpokladu, že schéma je vopred známa, kódovania polí sa jednoducho spájajú.

Vďaka tejto štruktúre kódované bajty vedúcich polí tvoria platný prefix pre rozsahové skenovania. V uvedenom príklade možno accountPrefix priamo použiť ako prefixový filter na skenovanie všetkých záznamov, kde ID účtu == 42.

Na výpočet exkluzívnej hornej hranice pre polouzavreté rozsahové skenovania [prefix, upper) použite 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        // Polouzavreté rozsahové skenovanie [accountPrefix, upper)
10} else {
11        // Neohraničené otvorené rozsahové skenovanie
12}

Poznámka: Builder.Len() sa musí merať na čistých hraniciach polí. Rezanie vo vnútri vnútorného bajtového toku poľa vytvára neplatný prefix.

Bezalokačné použitie a správa bufferov

Generovanie kľúčov sa často vykonáva na kritických databázových cestách. Aby sa odstránili alokácie na halde a režijné náklady na zmenu veľkosti bufferov, Builder pracuje striktne v rámci kapacity slice poskytnutého volajúcim a interne nealokuje nanovo.

Ak buffer vyčerpá kapacitu, zaznamená sa ErrShortBuffer bez zápisu čiastočných bajtov. Zápisy polí sú atomické a prvá zistená chyba sa uchováva, kým sa neskontroluje pomocou Key() alebo Err(). Poskytnutie dostatočnej kapacity vopred zabezpečuje kódovanie bez alokácií.

Veľkosti bufferov možno vopred vypočítať pomocou pomocných funkcií, ako sú EncodedBytesSize, EncodedStringSize a EncodedDecimalSize, alebo pomocou pevných konštánt. Vrátený kľúč priamo odkazuje na poskytnutý buffer a správa životného cyklu pamäte je ponechaná na volajúcom.

Decoder funguje symetricky: priamo vypožičiava dáta zo vstupného kľúča, pre polia premenlivej dĺžky vyžaduje cieľové buffery poskytnuté volajúcim a sprístupňuje Remaining() == 0 na zistenie nadbytočných bajtov alebo nezhôd schémy.

Podporované typy dát

  • Celé čísla: So znamienkom a bez znamienka (8-bitové až 64-bitové), Int128
  • Čísla s pohyblivou desatinnou čiarkou a numerické typy: Float32, Float64, desatinný text
  • Základné typy: Binárny reťazec, bajtový rez, logická hodnota, poradie enumerácie
  • Dátum a čas: Dátum, čas, čas so zónou, časová pečiatka, trvanie, kalendárny interval
  • Sieť a identifikátory: UUID, MAC, IP, IP prefix, kanonický sieťový prefix, LSN
  • Zložené štruktúry: Vnorené n-tice, rozsahy a surové štrukturálne kódovania
  • Collation: Unicode collation kľúče a externé kanonické tokeny

Mapovanie typov SQL je zosúladené s pravidlami triedenia B-stromov v PostgreSQL 18. Typy závislé od databázových katalógov alebo interného stavu engine sa spracúvajú odovzdaním externých kanonických tokenov.

Porovnávanie reťazcov

Builder.String predvolene používa binárne poradie surového UTF-8. Pre triedenie zohľadňujúce lokalitu poskytuje Schottky súbežne bezpečný a nemenný Collator:

  • Deterministické porovnávanie (collation): Kódovanie kľúča porovnávania spolu so surovými bajtmi UTF-8 poskytuje rozhodujúce kritérium pri rovnakých váhach porovnávania.
  • Nedeterministické porovnávanie (collation): Reťazce rovnaké podľa porovnávania sa považujú za identické a surové bajtové kritérium sa vynecháva.

Verzie Unicode a profilu by mali byť evidované v metadátach schémy. Ak sa zmenia poskytovatelia porovnávania alebo nastavenia profilu, existujúce kľúče je nutné znovu zostaviť.

Správa schémy

Keďže kľúče Schottky sú surové bajtové sekvencie bez hlavičiek, vrstva schémy musí evidovať:

  1. Poradie polí a typy dát.
  2. Smery triedenia (ASC/DESC) a poradie NULL (NULLS FIRST/LAST).
  3. Pravidlá porovnávania a normalizácie reťazcov.
  4. Verzie profilov Schottky a porovnávania.

Porovnávanie kľúčov vygenerovaných pomocou rôznych schém alebo dekódovanie voči nezhodnej schéme narúša záruky poradia.

Výkon a odkazy

Na Go 1.27+ je možné povoliť experimentálnu prenosnú akceleráciu SIMD pomocou GOEXPERIMENT=simd. Skalárne cesty a cesty SIMD produkujú bajtovo identické kľúče.