GoSuda

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

By Lemon Mint views ...

Kun toteutetaan LSM-puihin tai B-puihin perustuvia avain-arvo-varastoja ja tietokantaindeksejä, yhdistettyjä kenttiä on usein yhdistettävä yhdeksi tavuavaimeksi.

Standardit serialisointimuodot, kuten JSON tai Protocol Buffers, eivät ole suunniteltuja tähän tarkoitukseen, koska niiden serialisoidut tavutulosteet eivät säilytä luonnollista järjestystä, jota etumerkittömät tavukohtaiset vertailut (bytes.Compare tai memcmp) edellyttävät.

Schottky on Go-kirjasto, joka on suunniteltu koodaamaan usean tyypin yhdistettyjä monikkoja järjestystä säilyttäviksi tavuavaimiksi.

1go get gosuda.org/schottky@latest

Serialisointi vs. lajitteluavaimet

Oikean tavukohtaisen lajittelun takaaminen edellyttää useiden matalan tason datan esitystapojen huomioimista:

  • Kokonaisluvut: Tavanomainen 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: Vaatii etumerkkibitin säätöjä, käänteisen järjestyksen negatiivisille arvoille sekä johdonmukaisen käsittelyn arvoille NaN ja -0.
  • Vaihtelevanpituiset merkkijonot ja tavutaulukot: Kenttärajat on säilytettävä rikkomatta etuliitejärjestyksiä.
  • Yhdistettyjen avainten vaatimukset: Tuki kenttäkohtaiselle ASC/DESC-järjestykselle, erillisille NULLS FIRST/LAST-säännöille, tiukalle leksikografiselle etusijalle (aiemmat kentät määräävät järjestyksen) sekä yhteensopivuudelle etuliitehakujen kanssa.

Schottky muuntaa jokaisen arvon kanoniseksi hyötykuormaksi ennen presenssitunnisteiden ja suuntautumisen soveltamista. DESC-kentissä ASC-hyötykuorman jokainen tavu invertoidaan bitittäin (^b). NULL-sijoittelu hoidetaan erillisillä presenssitunnisteilla, ja se toimii riippumatta lajitteluSuunnasta.

Peruskäyttö

Seuraava esimerkki rakentaa yhdistetyn avaimen, 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ä eksplisiittistä lajittelujärjestyksen asetusta:

  • AscNullsFirst
  • AscNullsLast
  • DescNullsFirst
  • DescNullsLast

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

Etuliitehaku ja väliraja-arvot

Schottky-yhdistetyissä avaimissa ei ole globaaleja otsikoita, kenttälaskurin metatietoja, tyyppitunnisteita eikä loppumerkintöjä. Olettaen, että skeema tunnetaan etukäteen, kenttien koodaukset yksinkertaisesti liitetään peräkkäin.

Tämän rakenteen vuoksi johtavien kenttien koodatut tavut muodostavat kelvollisen etuliitteen väli-indeksihauille. Yllä olevassa esimerkissä accountPrefix voidaan käyttää suoraan etuliitesuodattimena kaikkien tietueiden hakemiseksi, joissa Account ID == 42.

Puoliavoimen [prefix, upper) -välihaun eksklusiivisen yläraja-arvon laskemiseksi käytetään PrefixUpperBound-funktiota:

 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) -välihaku
10} else {
11        // Rajaton avoin välihaku
12}

Huomautus: Builder.Len()-arvo on mitattava puhtailta kenttärajoilta. Leikkaaminen kentän sisäisen tavuvirran sisältä tuottaa virheellisen etuliitteen.

Nollaallokaatio ja puskurinhallinta

Avainten generointi suoritetaan usein kriittisillä tietokantapoluilla. Kasaallokaatioiden ja puskurin uudelleenkokoamisen ylikuormituksen poistamiseksi Builder toimii tiukasti kutsujan antaman siivun kapasiteetin rajoissa eikä varaa muistia uudelleen sisäisesti.

Jos puskurin kapasiteetti loppuu, tallennetaan virhe ErrShortBuffer kirjoittamatta osittaisia tavuja. Kenttien kirjoitukset ovat atomisia, ja ensimmäinen kohdattu virhe säilyy, kunnes se tarkistetaan kutsulla Key() tai Err(). Riittävän kapasiteetin varaaminen etukäteen takaa nollaallokaatiokoodauksen.

Puskurikoot voidaan laskea etukäteen apufunktioilla, kuten EncodedBytesSize, EncodedStringSize ja EncodedDecimalSize, tai kiinteillä vakioilla. Palautettu avain viittaa suoraan annettuun puskuriin, ja muistin elinkaren hallinta jätetään kutsujan vastuulle.

Decoder toimii symmetrisesti: se lainaa tavut suoraan syötteenä annetusta avaimesta, vaatii kutsujan antamat kohdepuskurit vaihtelevanpituisille kentille ja tarjoaa Remaining() == 0-tarkistuksen jäljelle jääneiden tavujen tai skeemavirheiden havaitsemiseksi.

Tuetut tietotyypit

  • Kokonaisluvut: Etumerkilliset ja etumerkittömät (8-bitistä 64-bittiseen), Int128
  • Liukuluvut ja numeeriset arvot: Float32, Float64, desimaaliteksti
  • Perustyypit: Binäärimerkkijono, tavutaulukko, totuusarvo, enum-järjestysluku
  • Päivämäärä ja aika: Päivämäärä, kellonaika, aikavyöhykkeellinen kellonaika, aikaleima, kesto, kalenterijakso
  • Verkko ja tunnisteet: UUID, MAC, IP, IP-prefiksi, kanoninen verkkoprefiksi, LSN
  • Yhdistetyt rakenteet: Sisäkkäiset monikot, välit ja raakarakenteiden koodaukset
  • Kollaatio: Unicode-kollaatioavaimet ja ulkoiset kanoniset tunnisteet

SQL-tyyppien kuvaus on linjassa PostgreSQL 18 B-puun lajittelusääntöjen kanssa. Tietokantakatalogeista tai sisäisestä moottoritilasta riippuvat tyypit käsitellään välittämällä ulkoisia kanonisia tunnisteita.

Merkkijonojen kollaatio

Builder.String käyttää oletuksena raakaa UTF-8-binäärijärjestystä. Kielialueen mukaista lajittelua varten Schottky tarjoaa samanaikaisuuden kannalta turvallisen, muuttumattoman Collator-rakenteen:

  • Deterministinen kollaatio: Koodaa kollaatioavaimen raakojen UTF-8-tavujen rinnalla, jotta tasapainotilanteessa, jossa kollaatiopainot ovat identtiset, on käytettävissä tasaaja.
  • Ei-deterministinen kollaatio: Käsittelee kollaatiovertailussa yhtäsuuret merkkijonot identtisinä, jättäen pois raakatavujen tasaajan.

Unicode- ja profiiliversiot on kirjattava metatietoskeemaan. Jos kollaatiotarjoajat tai profiiliasetukset muuttuvat, olemassa olevat avaimet on rakennettava uudelleen.

Skeeman hallinta

Koska Schottky-avaimet ovat raakoja, otsikottomia tavujonoja, skeemakerroksen on seurattava:

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

Eri skeemoilla generoitujen avainten vertailu tai dekoodaus ristiriitaisella skeemalla rikkoo järjestystakuut.

Suorituskyky ja linkit

Go 1.27:stä alkaen kokeellinen portable SIMD -kiihdytys voidaan ottaa käyttöön asetuksella GOEXPERIMENT=simd. Skalaari- ja SIMD-polut tuottavat tavutasolla identtiset avaimet.