GoSuda

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

By Lemon Mint
views ...

Kun toteutetaan LSM-puuhun tai B-puuhun perustuvia avain-arvo-varastoja ja tietokantaindeksejä, komposiittikentät täytyy usein yhdistää yhdeksi tavuavaimeksi.

Standardit sarjoitusmuodot, kuten JSON tai Protocol Buffers, eivät ole suunniteltu tähän tarkoitukseen, koska niiden sarjoitetut tavutulosteet eivät säilytä etumerkittömien tavukohtaisten vertailujen (bytes.Compare tai memcmp) edellyttämää luonnollista järjestysjärjestystä.

Schottky on Go-kirjasto, joka on suunniteltu koodaamaan useita eri tyyppejä sisältäviä komposiittitupletit järjestyksen säilyttäviksi tavuavaimiksi.

1go get gosuda.org/schottky@latest

Sarjoitus vs. Järjestysavaimet

Oikean tavukohtaisen järjestyksen takaaminen edellyttää useiden matalan tason datan esitysmuodon yksityiskohtien huomioimista:

  • Kokonaisluvut: Standardi kahden komplementin big-endian-koodaus rikkoo luonnollisen järjestyksen merkitsevimmän etumerkkibitin vuoksi. Etumerkkibitin kääntäminen on välttämätöntä oikeiden etumerkittömien tavuvertailujen kannalta.
  • Liukuluvut: Edellyttää etumerkkibitin säätöjä, negatiivisten arvojen käänteistä järjestystä sekä NaN- ja -0-arvojen yhdenmukaista käsittelyä.
  • Muuttuvanpituusiset merkkijonot ja tavuviipaleet: Kenttien rajat on säilytettävä rikkomatta etuliitteiden järjestysjärjestyksiä.
  • Komposiittiavaimen vaatimukset: Tuki itsenäiselle ASC/DESC-järjestykselle kenttää kohden, eriytetyt NULLS FIRST/LAST -säännöt, tiukka leksikaalinen ensisijaisuus (aiemmat kentät määräävät järjestyksen) sekä yhteensopivuus etuliitehakujen kanssa.

Schottky muuntaa jokaisen arvon kanoniseksi hyötykuormaksi ennen olemassaolotunnisteiden ja suuntasuuntauksen soveltamista. DESC-kenttien osalta ASC-hyötykuorman jokainen tavu käännetään bittikohtaisesti (^b). NULL-arvojen sijoittelu hoidetaan erillisten olemassaolotunnisteiden kautta ja se toimii riippumattomasti järjestyssuunnasta.

Peruskäyttö

Seuraava esimerkki rakentaa komposiittiavaimen, joka koostuu tilitunnuksesta (ASC, NULLS LAST) ja nimestä (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 tarjoaa neljä explicit järjestysjärjestelmäkonfiguraatiota:

  • AscNullsFirst
  • AscNullsLast
  • DescNullsFirst
  • DescNullsLast

NULL-arvojen sijoittelua ei koskaan päätellä implisiittisesti. Jos välitetään virheellinen Order-arvo, rakentaja kirjaa ErrInvalidOrder-virheen, joka palautetaan kutsuttaessa funktiota Key() tai Err().

Etuliitehaut ja Alueen Rajat

Schottkyn komposiittiavaimet eivät sisällä globaaleja otsakkeita, kenttien lukumäärän metatietoja, tyyppitunnisteita tai lopputunnisteita. Olettaen, että skeema tunnetaan etukäteen, kenttien koodaukset vain ketjutetaan yhteen.

Tämän rakenteen ansiosta johtavien kenttien koodatut tavut muodostavat kelvollisen etuliitteen aluehakuja varten. Yllä olevassa esimerkissä accountPrefix-muuttujaa voidaan käyttää suoraan etuliitesuodattimena kaikkien niiden tietueiden hakemiseen, joissa Account ID == 42.

Poissulkevan ylärajan laskemiseksi puoliavoimille [prefix, upper) -aluehauille käytetään funktiota 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        // Puoliavoin [accountPrefix, upper) aluehaku
10} else {
11        // Rajoittamaton avoin aluehaku
12}

Huomautus: Builder.Len() täytyy mitata puhtailla kenttien rajoilla. Osiointi kentän sisäisen tavuvirran sisällä tuottaa virheellisen etuliitteen.

Nolla-allokointi ja Puskurin Hallinta

Avaimen luonti suoritetaan usein tietokannan kriittisillä poluilla. Heap-allokointien ja puskurin koon muuttamisen aiheuttamien yleiskustannusten poistamiseksi Builder toimii tiukasti kutsujan tarjoaman viipaleen kapasiteetin puitteissa eikä allokoi muistia sisäisesti uudelleen.

Jos puskurin kapasiteetti loppuu kesken, ErrShortBuffer kirjaustietueeseen ilman osittaisten tavujen kirjoittamista. Kenttäkirjoitukset ovat atomisia, ja ensimmäinen kohdattu virhe säilytetään siihen asti, kunnes se tarkistetaan funktioiden Key() tai Err() kautta. Riittävän kapasiteetin tarjoaminen etukäteen varmistaa nolla-allokointisen koodauksen.

Puskurikoot voidaan laskea etukäteen apufunktioiden, kuten EncodedBytesSize, EncodedStringSize ja EncodedDecimalSize, avulla tai kiinteänkokoisten vakioiden kautta. Palautettu avain viittaa suoraan tarjottuun puskuriin jättäen muistin elinkaaren hallinnan kutsujalle.

Decoder toimii symmetrisesti: se lainaa suoraan syöteavaimesta, edellyttää kutsujan tarjoamia kohdepuskureita muuttuvanpituuksisille kentille ja tarjoaa ehdon Remaining() == 0 perässä olevien tavujen tai skeemavirheiden havaitsemiseen.

Tuetut Datan Tyypit

  • Kokonaisluvut: Etumerkilliset ja etumerkittömät (8-bittisistä 64-bittisiin), Int128
  • Liukuluvut & Numeeriset arvot: Float32, Float64, Desimaaliteksti
  • Perustyypit: Binäärimerkkijono, Tavuviipale, Totuusarvo, Enum-arvojärjestys
  • Päivämäärä & Aika: Päivämäärä, Aika, Aikavyöhykkeellinen aika, Aikaleima, Kesto, Kalenteriväli
  • Verkko & Tunnisteet: UUID, MAC, IP, IP-etuliite, Kanoninen verkkoetuliite, LSN
  • Komposiittirakenteet: Sisäkkäiset tuplet, Alueet ja raa'at rakenteelliset koodaukset
  • Lajittelu: Unicode-lajitteluavaimet ja ulkoiset kanoniset tunnisteet

SQL-tyyppien vastaavuus on yhdenmukainen PostgreSQL 18 -versioiden B-puun lajittelusääntöjen kanssa. Tietokantaluetteloista tai sisäisestä moottorin tilasta riippuvaiset tyypit käsitellään välittämällä ulkoisia kanonisia tunnisteita.

Merkkijonojen Lajittelu

Builder.String käyttää oletusarvoisesti raakaa UTF-8-binäärijärjestystä. Aluekohtaista lajittelua varten Schottky tarjoaa rinnakkaisuusturvallisen, muuttumattoman Collator-olion:

  • Deterministinen Lajittelu: Koodaa lajitteluavaimen raakojen UTF-8-tavujen ohella ratkaisevan tekijän tarjoamiseksi silloin, kun lajittelupainot ovat identtiset.
  • Epädeterministinen Lajittelu: Käsittelee lajittelun mukaan samanarvoisia merkkijonoja identtisinä jättäen pois raakojen tavujen tasapelin ratkaisijan.

Unicode- ja profiiliversioita tulee seurata metatietoskeemassa. Jos lajittelupalvelimet tai profiiliasetukset muuttuvat, olemassa olevat avaimet täytyy rakentaa uudelleen.

Skeeman Hallinta

Koska Schotky-avaimet ovat raakoja, otsakkeettomia tavujonoja, skeemakerroksen täytyy seurata:

  1. Kenttien järjestystä ja datatyyppejä.
  2. Lajittelusuuntia (ASC/DESC) ja NULL-järjestystä (NULLS FIRST/LAST).
  3. Merkkijonojen lajittelu- ja normalisointisääntöjä.
  4. Schottky- ja Lajitteluprofiiliversioita.

Eri skeemojen avulla luotujen avainten vertaaminen tai dekoodaus epäsopivaa skeemaa vasten rikkoo järjestystakuut.

Suorituskyky ja Linkit

Go 1.27+:ssa kokeileva siirrettävä SIMD-kiihdytys voidaan ottaa käyttöön komennolla GOEXPERIMENT=simd. Skalaari- ja SIMD-polut tuottavat tavutasolla identtisiä avaimia.