GoSuda

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

By Lemon Mint
views ...

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

Formatele standard de serializare precum JSON sau Protocol Buffers nu sunt concepute în acest scop deoarece rezultatele lor în octeți serializați nu păstrează ordinea naturală de sortare cerută de comparațiile fără semn la nivel de octet (bytes.Compare sau memcmp).

Schottky este o bibliotecă Go concepută pentru a coda tuple compozite de tipuri multiple î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 octet necesită abordarea mai multor detalii de reprezentare a datelor de nivel inferior:

  • Întregi: Codificarea standard cu complementul lui doi în format big-endian rupe ordinea naturală din cauza bitului de semn cel mai semnificativ. Inversarea bitului de semn este necesară pentru comparațiile corecte de octeți fără semn.
  • Numere în virgulă mobilă: Necesită ajustări ale bitului de semn, ordonare inversată pentru valorile negative și gestionarea consistentă a valorilor NaN și -0.
  • Șiruri de caractere și felii de octeți de lungime variabilă: Limitele câmpurilor trebuie păstrate fără a rupe ordinele de sortare ale prefixului.
  • Cerințe pentru cheile compozite: Suport pentru ordonare independentă ASC/DESC per câmp, reguli decuplate NULLS FIRST/LAST, precedență lexicografică strictă (câmpurile anterioare determină ordinea) și compatibilitate cu scanarea prefixelor.

Schottky convertește fiecare valoare într-o sarcină utilă canonică înainte de a aplica etichete de prezență și orientare direcțională. Pentru câmpurile DESC, fiecare octet al sarcinii utile ASC este inversat la nivel de biți (^b). Amplasarea valorilor NULL este gestionată prin intermediul unor etichete de prezență dedicate și operează independent de direcția de sortare.

Utilizare de Bază

Următorul exemplu construiește o cheie compozită constând 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        // Inițializează stocarea și constructorul
11        storage := make([]byte, 0, 128)
12        builder := schottky.NewBuilder(storage)
13
14        builder.Int64(42, schottky.AscNullsLast)
15        accountPrefixLen := builder.Len()
16
17        builder.String("Ada", schottky.DescNullsFirst)
18        key, err := builder.Key()
19
20        if err != nil {
21                panic(err)
22        }
23        accountPrefix := key[:accountPrefixLen]
24        fmt.Printf("key=%x\nprefix=%x\n", key, accountPrefix)
25}

Schottky oferă patru configurații explicite de ordine de sortare:

  • AscNullsFirst
  • AscNullsLast
  • DescNullsFirst
  • DescNullsLast

Poziționarea NULL nu este niciodată dedusă implicit. Dacă este transmisă o valoare Order invalidă, constructorul înregistrează ErrInvalidOrder, care este returnată la apelarea funcției Key() sau Err().

Scanarea Prefixelor și Limitele de Interval

Cheile compozite Schottky nu conțin anteturi globale, metadate privind numărul de câmpuri, etichete de tip sau remorci. Presupunând că schema este cunoscută din timp, codificările câmpurilor sunt pur și simplu concatenate.

Datorită acestei dispuneri, octeții codați ai câmpurilor de la început 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 semi-deschise [prefix, upper), utilizați 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 semi-deschisă [accountPrefix, upper)
10} else {
11        // Scanare de interval deschis nemărginit
12}

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

Alocare Zero și Gestionarea Memoriei Tampon

Generarea cheilor rulează frecvent pe căi critice ale bazei de date. Pentru a elimina alocările în memoria heap și costul suplimentar de redimensionare a memoriei tampon, Builder lucrează strict în limitele capacității feliei furnizate de apelant și nu se va realoca intern.

Dacă memoria tampon rămâne fără capacitate, ErrShortBuffer este înregistrat fără a scrie octeți parțiali. Scrierile de câmpuri sunt atomice, iar prima eroare întâlnită este păstrată până când este verificată prin Key() sau Err(). Furnizarea unei capacități suficiente în prealabil asigură o codificare fără alocare.

Dimensiunile memoriei tampon pot fi calculate în avans utilizând funcții auxiliare precum EncodedBytesSize, EncodedStringSize și EncodedDecimalSize, sau prin constante de dimensiune fixă. Cheia returnată face referire directă la memoria tampon furnizată, lăsând gestionarea ciclului de viață al memoriei în seama apelantului.

Componenta Decoder funcționează simetric: împrumută direct din cheia de intrare, necesită memorii tampon de destinație furnizate de apelant pentru câmpurile de lungime variabilă și oferă Remaining() == 0 pentru a detecta octeții de la sfârșit sau neconcordanțele de schemă.

Tipuri de Date Suportate

  • Întregi: Cu semn și fără semn (de la 8 biți la 64 de biți), Int128
  • Virgulă Mobilă și Numerice: Float32, Float64, Text Zecimal
  • Tipuri de Bază: Șir binar, Felie de octeți, Boolean, Rang Enum
  • Dată și Oră: Dată, Oră, Oră cu Fus Orar, Marcaj de Timp, Durată, Interval de Calendar
  • Rețea și Identificatori: UUID, MAC, IP, Prefix IP, Prefix de Rețea Canonic, LSN
  • Structuri Compozite: Tuple imbricate, Intervale și codificări structurale brute
  • Colație: Chei de colație Unicode și jetoane canonice externe

Maparea tipurilor SQL este aliniată cu regulile de sortare B-tree din PostgreSQL 18. Tipurile dependente de cataloagele bazei de date sau de starea internă a motorului sunt gestionate prin transmiterea unor jetoane canonice externe.

Colația Șirurilor

Builder.String are ca implicit ordinea binară UTF-8 brută. Pentru sortarea conștientă de localizare, Schottky oferă un Collator imutabil și sigur pentru concurență:

  • Colație Deterministă: Codează cheia de colație alături de octeții UTF-8 bruți pentru a oferi un element de departajare atunci când ponderile de colație sunt identice.
  • Colație Nedeterministă: Tratează șirurile egale prin colație ca fiind identice, ommițând elementul de departajare bazat pe octeți bruți.

Versiunile Unicode și de profil ar trebui urmărite în schema de metadate. Dacă furnizorii de colație sau setările de profil se schimbă, cheile existente trebuie reconstruite.

Gestionarea Schemelor

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

  1. Secvența de câmpuri și tipurile de date.
  2. Direcțiile de sortare (ASC/DESC) și ordonarea NULL (NULLS FIRST/LAST).
  3. Colația șirurilor și regulile de normalizare.
  4. Versiunile de profil Schottky și Colație.

Compararea cheilor generate cu scheme diferite sau decodarea în raport cu o schemă necorespunzătoare rupe garanțiile de ordonare.

Performanță și Legături

Pe Go 1.27+, accelerarea SIMD portabilă experimentală poate fi activată utilizând GOEXPERIMENT=simd. Căile scalare și SIMD produc chei identice la nivel de octet.