GoSuda

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

By Lemon Mint
views ...

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

A szabványos szerializációs formátumok, mint például a JSON vagy a Protocol Buffers, nem erre a célra lettek tervezve, mivel a szerializált bájtkimenetük nem őrzi meg a predikátumok nélküli bájtalapú összehasonlítások (bytes.Compare vagy memcmp) által megkövetelt természetes rendezési sorrendet.

A Schottky egy olyan Go könyvtár, amelyet arra terveztek, hogy a többtípusú összetett tuple-öket sorrendmegőrző bájtkulcsokká kódoljon.

1go get gosuda.org/schottky@latest

Szerializáció vs. Rendezési kulcsok

A helyes bájtalapú rendezés garantálása számos alacsony szintű adatmegjelenítési részlet kezelését igényli:

  • Egész számok: A szabványos kettes komplemens szerinti big-endian kódolás a legmagasabb helyi értékű előjeles bit miatt megtöri a természetes rendezést. Az előjeles bit invertálása elengedhetetlen a helyes előjel nélküli bájt-összehasonlításokhoz.
  • Lebegőpontos számok: Előjeles bit módosításokat, a negatív értékek esetében megfordított sorrendet, valamint a NaN és -0 konzisztens kezelését igényli.
  • Változó hosszúságú karakterláncok és bájt-szeletek: A mezőhatárokat meg kell őrizni anélkül, hogy az előtag szerinti rendezési sorrend megtörne.
  • Összetett kulcsra vonatkozó követelmények: Mezőnkénti független ASC/DESC rendezés támogatása, függetlenített NULLS FIRST/LAST szabályok, szigorú lexikografikus precedencia (a korábbi mezők határozzák meg a sorrendet), valamint az előtagalapú tartománykereséshez való kompatibilitás.

A Schottky minden értéket kanonikus hasznos adattá (payload) konvertál, mielőtt alkalmazná a jelenléti címkéket és az irányultságot. A DESC mezők esetében az ASC hasznos adat minden egyes bájtja bitenként invertálásra kerül (^b). A NULL elhelyezése dedikált jelenléti címkéken keresztül történik, és a rendezési iránytól függetlenül működik.

Alapvető használat

Az alábbi példa egy olyan összetett kulcsot hoz létre, amely egy fiókazonosítóból (Account ID, ASC, NULLS LAST) és egy névből (Name, 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 sorrend konfigurációt biztosít:

  • AscNullsFirst
  • AscNullsLast
  • DescNullsFirst
  • DescNullsLast

A NULL pozicionálás soha nem következtethető ki implicit módon. Ha érvénytelen Order érték kerül átadásra, az építő (builder) rögzíti az ErrInvalidOrder hibát, amely a Key() vagy az Err() hívásakor adódik vissza.

Előtagalapú keresés és tartományhatárok

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

Ezen elrendezés miatt a vezető mezők kódolt bájtjai érvényes előtagot képeznek a tartománykeresésekhez. A fenti példában az accountPrefix közvetlenül felhasználható előtag-szűrőként az összes olyan rekord keresésére, ahol az Account ID == 42.

A félig nyitott [prefix, upper) tartománykeresések exkluzív 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élig nyitott [accountPrefix, upper) tartománykeresés
10} else {
11        // Korlátlan nyitott tartománykeresés
12}

Megjegyzés: A Builder.Len() értéket tiszta mezőhatároknál kell mérni. A mező belső bájtfolyamatán belüli szeletelés érvénytelen előtagot eredményez.

Nullás allokáció és púffermenedzsment

A kulcsgenerálás gyakran kritikus adatbázis-útvonalakon fut. A heap-allokációk és a púffer-átméretezési többletterhelés kiküszöbölése érdekében a Builder szigorúan a hívó által biztosított szelet kapacitásán belül működik, és nem végez belső újrafoglalást.

Ha a púfferből kifogy a kapacitás, az ErrShortBuffer rögzítésre kerül anélkül, hogy részleges bájtokat írna. A mezőbeírások atomiak, és az elsőként észlelt hiba megmarad mindaddig, amíg azt a Key() vagy az Err() segítségén keresztül le nem ellenőrzik. A megfelelő kapacitás előzetes biztosítása nullás allokációt eredményező kódolást garantál.

A púfferméretek előre kiszámíthatók olyan segédfüggvények használatával, mint az EncodedBytesSize, az EncodedStringSize és az EncodedDecimalSize, vagy rögzített méretű konstansok révén. A visszatérési kulcs közvetlenül a megadott púferre hivatkozik, a memória életciklus-kezelését a hívóra bízva.

A Decoder szimmetrikusan működik: közvetlenül a bemeneti kulcsból kölcsönöz, a változó hosszúságú mezőkhöz a hívó által biztosított célpúffereket igényel, és a Remaining() == 0 metódust biztosítja a trailing bájtok vagy sémaeltérések detektálásához.

Támogatott adattípusok

  • Egész számok: Előjeles és előjel nélküli (8 bittől 64 bitig), Int128
  • Lebegőpontos és numerikus adatok: Float32, Float64, decimális szöveg
  • Alaptípusok: Bináris karakterlánc, bájt-szelet, logikai (boolean), enum rang
  • Dátum és idő: Dátum, idő, időzónával ellátott idő, időbélyeg (timestamp), időtartam (duration), naptári intervallum
  • Hálózat és azonosítók: UUID, MAC, IP, IP-előtag, kanonikus hálózati előtag, LSN
  • Összetett struktúrák: Beágyazott tuple-ök, tartományok és nyers strukturális kódolások
  • Karakterfüggvények (Collation): Unicode Collation kulcsok és külső kanonikus tokenek

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

Karakterlánc-összehasonlítás (Collation)

A Builder.String alapértelmezés szerint a nyers UTF-8 bináris sorrendet használja. A területi beállításokat (locale) figyelembe vevő rendezéshez a Schottky egy konkurens módon biztonságos, megváltoztathatatlan (immutable) Collator összetevőt biztosít:

  • Determinisztikus összehasonlítás: Az összehasonlítási kulcsot a nyers UTF-8 bájtok mellett kódolja, hogy döntetlen esetén tie-brakert biztosítson, amikor a rendezési súlyok azonosak.
  • Nem-determinisztikus összehasonlítás: Az összehasonlítás szempontjából egyenlő karakterláncokat azonosnak tekinti, kihagyva a nyers bájtalapú tie-brakert.

Az Unicode- és profilverziókat a metaadat-sémában kell nyomon követni. 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étegnek nyomon kell követnie a következőket:

  1. A mezők sorrendjét és az adattípusokat.
  2. A rendezési irányokat (ASC/DESC) és a NULL rendezést (NULLS FIRST/LAST).
  3. A karakterlánc-összehasonlítási és normalizációs szabályokat.
  4. A Schottky és Collation profil verzióit.

A különböző sémákkal generált kulcsok összehasonlítása vagy az eltérő sémával történő dekódolás megsérti a rendezési garanciákat.

Teljesítmény és hivatkozások

Go 1.27+ verziókon a kísérleti hordozható SIMD-gyorsítás a GOEXPERIMENT=simd használatával engedélyezhető. A skalár és a SIMD útvonalak bájtazonos kulcsokat állítanak elő.