GoSuda

Schottky: Codificare a cheilor de octeți fără alocări de memorie și cu păstrarea ordinii pentru Go

By Lemon Mint views ...

Atunci când implementați magazine cheie-valoare bazate pe arbori LSM sau pe arbori B și indecși de baze de date, câmpurile compuse trebuie adesea combinate într-o singură cheie de tip octeți.

Formatele standard de serializare precum JSON sau Protocol Buffers nu sunt concepute în acest scop, deoarece ieșirile lor serializate în octeți nu păstrează ordinea naturală de sortare impusă de comparațiile octet cu octet fără semn (bytes.Compare sau memcmp).

Schottky este o bibliotecă Go concepută pentru a codifica tupluri compuse cu mai multe tipuri în chei de octeți care păstrează ordinea.

1go get gosuda.org/schottky@latest

Serializare versus chei de sortare

Garantarea unei sortări corecte la nivel de octeți necesită abordarea mai multor detalii de reprezentare a datelor de nivel scăzut:

  • Întregi: Codificarea standard în complement față de doi, big-endian, încalcă ordinea naturală din cauza bitului de semn cel mai semnificativ. Inversarea bitului de semn este necesară pentru comparații corecte ale octeților fără semn.
  • Numere în virgulă mobilă: Necesită ajustări ale bitului de semn, ordine inversată pentru valorile negative și tratare consecventă a valorilor NaN și -0.
  • Șiruri de lungime variabilă și secvențe de octeți: Limitele câmpurilor trebuie păstrate fără a încălca ordinea de sortare a prefixelor.
  • Cerințe pentru cheile compuse: Suport pentru ordonare ASC/DESC independentă pentru fiecare câmp, reguli NULLS FIRST/LAST decuplate, precedență lexicografică strictă (câmpurile anterioare determină ordinea) și compatibilitate cu scanarea pe prefix.

Schottky convertește fiecare valoare într-o sarcină utilă canonică înainte de aplicarea etichetelor de prezență și a orientării direcționale. Pentru câmpurile DESC, fiecare octet al sarcinii utile ASC este inversat bit cu bit (^b). Plasarea valorilor NULL este gestionată prin etichete de prezență dedicate și operează independent de direcția de sortare.

Utilizare de bază

Exemplul următor construiește o cheie compusă formată dintr-un ID de cont (ASC, NULLS LAST) și un nume (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) // Scrie un întreg pe 64 de biți cu ordine ascendentă, NULL-urile la final
14        accountPrefixLen := builder.Len()
15
16        builder.String("Ada", schottky.DescNullsFirst) // Scrie un șir cu ordine descendentă, NULL-urile la început
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 oferă patru configurații explicite de ordine de sortare:

  • AscNullsFirst
  • AscNullsLast
  • DescNullsFirst
  • DescNullsLast

Poziționarea valorilor NULL nu este niciodată dedusă implicit. Dacă se transmite o valoare Order invalidă, constructorul înregistrează ErrInvalidOrder, care este returnată la apelul Key() sau Err().

Scanarea pe prefix și limitele intervalelor

Cheile compuse Schottky nu conțin antete globale, metadate privind numărul de câmpuri, etichete de tip sau sufixe. Presupunând că schema este cunoscută dinainte, codificările câmpurilor sunt pur și simplu concatenate.

Datorită acestei structuri, octeții codificați ai câmpurilor principale formează un prefix valid pentru scanările de interval. În exemplul de mai sus, accountPrefix poate fi utilizat direct ca filtru de prefix pentru a scana toate înregistrările unde Account ID == 42.

Pentru a calcula limita superioară exclusivă pentru scanările de interval semideschis [prefix, upper), se utilizează 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        // Scanare de interval semideschis [accountPrefix, upper)
10} else {
11        // Scanare de interval deschis, nelimitat
12}

Notă: Builder.Len() trebuie măsurat la limitele curate ale câmpurilor. Tăierea în interiorul fluxului intern de octeți al unui câmp produce un prefix invalid.

Zero alocări și gestionarea bufferului

Generarea cheilor rulează frecvent pe căile critice ale bazei de date. Pentru a elimina alocările în heap și costul redimensionării bufferului, Builder lucrează strict în limita capacității sliceului furnizat de apelant și nu realocă intern.

Dacă bufferul rămâne fără capacitate, se înregistrează ErrShortBuffer fără a scrie octeți parțiali. Scrierile câmpurilor sunt atomice, iar prima eroare întâlnită este păstrată până la verificarea prin Key() sau Err(). Furnizarea din timp a unei capacități suficiente asigură o codificare fără alocări.

Dimensiunile bufferelor pot fi calculate în avans cu ajutorul funcțiilor auxiliare precum EncodedBytesSize, EncodedStringSize și EncodedDecimalSize, sau prin constante de dimensiune fixă. Cheia returnată referențiază direct bufferul furnizat, lăsând gestionarea ciclului de viață al memoriei în sarcina apelantului.

Decoder funcționează simetric: împrumută direct din cheia de intrare, necesită buffere de destinație furnizate de apelant pentru câmpurile de lungime variabilă și oferă Remaining() == 0 pentru a detecta octeții în exces sau nepotrivirile de schemă.

Tipuri de date suportate

  • Întregi: Cu semn și fără semn (de la 8 la 64 de biți), Int128
  • Virgulă mobilă și valori numerice: Float32, Float64, text zecimal
  • Tipuri de bază: Șir binar, secvență de octeți, boolean, rang de enumerare
  • Dată și oră: Dată, oră, oră cu fus orar, timestamp, durată, interval calendaristic
  • Rețea și identificatori: UUID, MAC, IP, prefix IP, prefix de rețea canonic, LSN
  • Structuri compuse: Tupluri imbricate, intervale și codificări structurale brute
  • Colaționare: Chei de colaționare Unicode și token-uri canonice externe

Mapările tipurilor SQL sunt aliniate cu regulile de sortare B-tree din PostgreSQL 18. Tipurile care depind de cataloagele bazei de date sau de starea internă a motorului sunt gestionate prin transmiterea unor token-uri canonice externe.

Colaționarea șirurilor

Builder.String utilizează implicit ordinea binară UTF-8 brută. Pentru sortarea sensibilă la limbă, Schottky oferă un Collator concurent-sigur și imutabil:

  • Colaționare deterministă: Codifică cheia de colaționare împreună cu octeții UTF-8 bruti, pentru a oferi un criteriu de departajare atunci când ponderile de colaționare sunt identice.
  • Colaționare nedeterministă: Tratează șirurile egale din punct de vedere al colaționării ca fiind identice, omițând criteriul de departajare pe octeți bruti.

Versiunile Unicode și ale profilurilor trebuie urmărite în schema de metadate. Dacă furnizorii de colaționare sau setările profilurilor se schimbă, cheile existente trebuie reconstruite.

Gestionarea schemei

Deoarece cheile Schottky sunt secvențe brute de octeți, fără antet, stratul de schemă trebuie să urmărească:

  1. Secvența câmpurilor și tipurile de date.
  2. Direcțiile de sortare (ASC/DESC) și ordinea NULL (NULLS FIRST/LAST).
  3. Regulile de colaționare și normalizare ale șirurilor.
  4. Versiunile profilurilor Schottky și Collation.

Compararea cheilor generate cu scheme diferite sau decodificarea față de o schemă nepotrivită încalcă garanțiile de ordonare.

Performanță și linkuri

Pe Go 1.27+, accelerarea SIMD portabilă experimentală poate fi activată folosind GOEXPERIMENT=simd. Căile scalare și cele SIMD produc chei identice la nivel de octeți.