GoSuda

Schottky: nulla allokáció, sorrendtartó bájtkulcs-kódolás Go-hoz

By Lemon Mint views ...

Amikor LSM-fa vagy B-fa alapú kulcs-érték tárolókat és adatbázis-indexeket implementálunk, az összetett mezőket gyakran egyetlen bájtkulccsá kell összevonni.

A szabványos szerializációs formátumok, mint a JSON vagy a Protocol Buffers, nem erre a célra készültek, mivel szerializált bájtkimenetük nem őrzi meg azt a természetes rendezési sorrendet, amelyet az előjel nélküli bájtonkénti összehasonlítások (bytes.Compare vagy memcmp) igényelnek.

A Schottky egy Go könyvtár, amelyet többtípusú összetett tuple-ök rendezést megőrző bájtkulcsokká történő kódolására terveztek.

1go get gosuda.org/schottky@latest

Szerializáció vs. rendezési kulcsok

A helyes bájtonkénti rendezés garantálásához több alacsony szintű adatábrázolási részletet kell kezelni:

  • Egészek: A standard kettes komplemens nagy-endian kódolás megtöri a természetes rendezést a legmagasabb helyiértékű előjelbit miatt. Az előjelbit invertálása szükséges a helyes előjel nélküli bájtösszehasonlításhoz.
  • Lebegőpontos számok: Előjelbit-módosításokat, a negatív értékek fordított sorrendjét, valamint a NaN és a -0 következetes kezelését igényli.
  • Változó hosszúságú sztringek és bájtszeletek: A mezőhatárokat úgy kell megőrizni, hogy ne törjék meg a prefixek rendezési sorrendjét.
  • Összetett kulcsok követelményei: Mezőnként független ASC/DESC rendezés támogatása, elkülönített NULLS FIRST/LAST szabályok, szigorú lexikografikus elsőbbség (a korábbi mezők határozzák meg a sorrendet), valamint kompatibilitás prefix-szkenneléssel.

A Schottky minden értéket kanonikus adattartalommá alakít, mielőtt alkalmazná a jelenlétjelzőket és az irányultságot. DESC mezők esetén az ASC adattartalom minden bájtját bitenként invertálja (^b). A NULL-pozicionálást dedikált jelenlétjelzők kezelik, és függetlenül működnek a rendezési iránytól.

Alapvető használat

Az alábbi példa egy összetett kulcsot épít fel, amely egy Fiókazonosítóból (ASC, NULLS LAST) és egy Névből (DESC, NULLS FIRST) áll:

 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}

A Schottky négy explicit rendezési konfigurációt biztosít:

  • AscNullsFirst
  • AscNullsLast
  • DescNullsFirst
  • DescNullsLast

A NULL pozicionálása soha nem következtethető ki implicit módon. Ha érvénytelen Order értéket adunk meg, a builder ErrInvalidOrder hibát rögzít, amelyet a Key() vagy Err() hívásakor ad vissza.

Prefix-szkennelés és tartományhatárok

A Schottky összetett kulcsok nem tartalmaznak globális fejléceket, mezőszám-metaadatokat, típuscímkéket vagy lábléceket. Feltételezve, hogy a séma előre ismert, a mezőkódolások egyszerűen összefűzésre kerülnek.

Ebből a felépítésből adódóan a vezető mezők kódolt bájtjai érvényes prefixet alkotnak tartománykeresésekhez. A fenti példában az accountPrefix közvetlenül használható prefixszűrőként, amellyel minden olyan rekord lekérdezhető, ahol Account ID == 42.

A félignyitott [prefix, upper) tartománykeresések kizárt felső határának kiszámításához használja a PrefixUpperBound függvényt:

 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        // Félignyitott [accountPrefix, upper) tartománykeresés
10} else {
11        // Korlátlan, nyitott tartománykeresés
12}

Megjegyzés: A Builder.Len() értékét tiszta mezőhatároknál kell mérni. Egy mező belső bájtfolyamán belüli szeletelés érvénytelen prefixet eredményez.

Nulla allokáció és pufferkezelés

A kulcsgenerálás gyakran kritikus adatbázis-útvonalakon fut. A heap-allokációk és a pufferátméretezési többletterhelés megszüntetése érdekében a Builder szigorúan a hívó által megadott szelet kapacitásán belül dolgozik, és belsőleg nem allokál újra.

Ha a puffer kapacitása kimerül, az ErrShortBuffer hiba kerül rögzítésre, részleges bájtok írása nélkül. A mezőírások atomikusak, és az első előforduló hiba mindaddig megmarad, amíg a Key() vagy Err() hívással nem ellenőrzik. Az elegendő kapacitás előzetes biztosítása garantálja a nulla allokációs kódolást.

A pufferméretek előre kiszámíthatók olyan segédfüggvényekkel, mint az EncodedBytesSize, EncodedStringSize és EncodedDecimalSize, vagy fix méretű konstansokkal. A visszaadott kulcs közvetlenül a megadott pufferre hivatkozik, a memória életciklusának kezelése pedig a hívóra marad.

A Decoder szimmetrikusan működik: közvetlenül a bemeneti kulcsból kölcsönzi az adatokat, a változó hosszúságú mezőkhöz a hívó által megadott célpuffereket igényel, és a Remaining() == 0 értéket biztosítja a záró bájtok vagy sématévesztések felderítéséhez.

Támogatott adattípusok

  • Egészek: Előjeles és előjel nélküli (8 bites től 64 bitesig), Int128
  • Lebegőpontos és numerikus típusok: Float32, Float64, decimális szöveg
  • Alaptípusok: Bináris sztring, bájtszelet, logikai érték, enum rang
  • Dátum és idő: Dátum, idő, zónás idő, időbélyeg, időtartam, naptári intervallum
  • Hálózat és azonosítók: UUID, MAC, IP, IP-prefix, kanonikus hálózati prefix, LSN
  • Összetett struktúrák: Beágyazott tuple-ök, tartományok és nyers szerkezeti kódolások
  • Collation: Unicode collation kulcsok és külső kanonikus tokenek

Az SQL-típusleképezés a PostgreSQL 18 B-fa rendezési szabályaihoz igazodik. Az adatbázis-katalógusoktól vagy belső motorállapottól függő típusok külső kanonikus tokenek átadásával kezelhetők.

Sztringek egybevetése (collation)

A Builder.String alapértelmezetten a nyers UTF-8 bináris sorrendet használja. Nyelvi érzékeny rendezéshez a Schottky párhuzamosan biztonságos, változtathatatlan Collator típust biztosít:

  • Determinisztikus collation: A collation kulcsot a nyers UTF-8 bájtokkal együtt kódolja, hogy azonos collation súlyok esetén tie-breakert biztosítson.
  • Nemdeterminisztikus collation: A collation szerint egyenlő sztringeket azonosnak kezeli, a nyers bájtos tie-breakert elhagyva.

A Unicode- és profilverziókat a metaadat-sémában nyilván kell tartani. Ha a collation szolgáltatók vagy a profilbeállítások megváltoznak, a meglévő kulcsokat újra kell építeni.

Sémakezelés

Mivel a Schottky kulcsok nyers, fejléc nélküli bájtsorozatok, a sémaréteg az alábbiakat köteles nyilván tartani:

  1. A mezősorrendet és az adattípusokat.
  2. A rendezési irányokat (ASC/DESC) és a NULL-rendezést (NULLS FIRST/LAST).
  3. A sztring-collation és normalizálási szabályokat.
  4. A Schottky és a Collation profilverziókat.

Különböző sémákkal generált kulcsok összehasonlítása, vagy eltérő sémával történő dekódolás megtöri a rendezési garanciákat.

Teljesítmény és hivatkozások

Go 1.27+ verzión a kísérleti, hordozható SIMD gyorsítás a GOEXPERIMENT=simd beállítással engedélyezhető. A skaláris és a SIMD útvonalak bájtra azonos kulcsokat állítanak elő.