GoSuda

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

By Lemon Mint
views ...

Pri implementácii úložiska typu kľúč-hodnota a databázových indexov založených na LSM-stromoch alebo B-stromoch je často potrebné skombinovať kompozitné polia do jediného bajtového kľúča.

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

Schottky je knižnica pre jazyk Go navrhnutá na kódovanie viac-typových kompozitných tuple 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 si vyžaduje riešenie viacerých nízkoúrovňových detailov reprezentácie dát:

  • Celé čísla: Štandardné dvojkové doplnkové kódovanie pre veľkú endianitu narúša prirodzené usporiadanie kvôli najvýznamnejšiemu znamienkovému bitu. Inverzia znamienkového bitu je nevyhnutná pre správne bez znamienkové bajtové porovnania.
  • Čísla s plávajúcou rádovou čiarkou: Vyžadujú úpravy znamienkového bitu, inverzné usporiadanie pre záporné hodnoty a konzistentné zaobchádzanie s NaN a -0.
  • Reťazce s promlivou dĺžkou a bajtové rezy: Hranice polí musia byť zachované bez narušenia prefixových poradí triedenia.
  • Požiadavky na kompozitný kľúč: Podpora nezávislého ASC/DESC usporiadania pre každé pole, oddelené pravidlá NULLS FIRST/LAST, prísna lexikografická priorita (skkoršie polia určujú poradie) a kompatibilita s prefixovým skenovaním.

Schottky konvertuje každú hodnotu na kanonický payload pred aplikovaním značiek prítomnosti a smerovej orientácie. Pre DESC polia je každý bajt ASC payloadu bitovo invertovaný (^b). Umiestnenie NULL je riadené prostredníctvom špecializovaných značiek prítomnosti a funguje nezávisle od smeru triedenia.

Základné použitie

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

  • AscNullsFirst
  • AscNullsLast
  • DescNullsFirst
  • DescNullsLast

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

Prefixové skenovanie a medze rozsahu

Kompozitné kľúče Schottky neobsahujú žiadne globálne hlavičky, metadáta počtu polí, typové značky ani prívesy. Za predpokladu, že schéma je vopred známa, kódovania polí sa jednoducho zreťazia.

Kvôli tomuto rozloženiu tvoria kódované bajty vedúcich polí platný prefix pre skenovania rozsahov. V príklade vyššie môže byť accountPrefix priamo použitý ako prefixový filter na skenovanie všetkých záznamov, kde Account ID == 42.

Na výpočet exkluzívnej hornej medze pre poloodvorené rozsahy 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        // Poloodvorené [accountPrefix, upper) skenovanie rozsahu
10} else {
11        // Neohraničené otvorené skenovanie rozsahu
12}

Poznámka: Builder.Len() sa musí merať na čistých hraniciach polí. Rezanie vo vnútri vnútorného bajtového prúdu pola vytvorí neplatný prefix.

Nulová alokácia a správa vyrovnávacej pamäte

Generovanie kľúčov často prebieha na kritických databázových cestách. Na elimináciu alokácií haldy a réžie spojenej so zmenou veľkosti vyrovnávacej pamäte pracuje Builder striktne v rámci kapacity rezu poskytnutého volajúcim a interne nebude prerializovávať.

Ak vyrovnávacej pamäti dôjde kapacita, zaznamená sa ErrShortBuffer bez zápisu čiastočných bajtov. Zápisy polí sú atomické a prvá zistená chyba sa zachováva, kým sa neskontroluje cez Key() alebo Err(). Poskytnutie dostatočnej kapacity vopred zabezpečuje kódovanie s nulovou alokáciou.

Veľkosti vyrovnávacej pamäte je možné vopred vypočítať pomocou pomocných funkcií ako EncodedBytesSize, EncodedStringSize a EncodedDecimalSize, alebo prostredníctvom konštánt s pevnou veľkosťou. Vrátený kľúč odkazuje priamo na poskytnutú vyrovnávaciu pamäť, pričom správu životného cyklu pamäte ponecháva na volajúceho.

Decoder funguje symetricky: požičiava si priamo zo vstupného kľúča, vyžaduje cieľové vyrovnávacie pamäte poskytnuté volajúcim pre polia s premenlivou dĺžkou a poskytuje Remaining() == 0 na detekciu koncových bajtov alebo nezhôd schém.

Podporované dátové typy

  • Celé čísla: So znamienkom aj bez znamienka (8-bitové až 64-bitové), Int128
  • Čísla s plávajúcą rádovou čiarkou a numerické typy: Float32, Float64, Desatinný text
  • Základné typy: Binárny reťazec, Bajtový rez, Boolean, Poradie výčtu (Enum Rank)
  • Dátum a čas: Dátum, Čas, Čas s časovým pásmom, Časová pečiatka, Trvanie, Interval kalendára
  • Sieť a identifikátory: UUID, MAC, IP, IP prefix, Kanonický sieťový prefix, LSN
  • Kompozitné štruktúry: Vnorené tuple, Rozsahy a surové štrukturálne kódovania
  • Porovnávanie (Collation): Unicode kľúče porovnávania a externé kanonické tokeny

Mapovanie typov SQL je zarovnané s pravidlami triedenia B-stromov PostgreSQL 18. Typy závislé od databázových katalógov alebo vnútorného stavu enginu sú spracované odovzdaním externých kanonických tokenov.

Porovnávanie reťazcov (Collation)

Builder.String má štandardne nastavené surové binárne poradie UTF-8. Pre triedenie rešpektujúce lokálne nastavenia poskytuje Schottky nemenný Collator bezpečný pre súbežné použitie:

  • Deterministické porovnávanie: Kóduje kľúč porovnávania popri surových bajtoch UTF-8, čím poskytuje rozstrel (tie-breaker), keď sú váhy porovnávania identické.
  • ** Nedeterministické porovnávanie**: Považuje reťazce rovnaké z hľadiska porovnávania za identické, pričom vynecháva rozstrel zo surových bajtov.

Verzie Unicode a profilov by sa mali sledovať v schéme metadát. Ak sa zmenia poskytovatelia porovnávania alebo nastavenia profilu, existujúce kľúče sa musia prebudovať.

Správa schémy

Pretože kľúče Schottky sú surové bajtové sekvencie bez hlavičky, vrstva schémy musí sledovať:

  1. Sekvenciu polí a dátové typy.
  2. Smer triedenia (ASC/DESC) a usporiadanie NULL (NULLS FIRST/LAST).
  3. Pravidlá porovnávania a normalizácie reťazcov.
  4. Verzie profilov Schottky a Collation.

Porovnávanie kľúčov vygenerovaných s rôznymi schémami alebo dekódovanie oproti nezhodnej schéme narúša záruky usporiadania.

Výkon a odkazy

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