GoSuda

Schottky: Codifica di chiavi in byte senza allocazioni e con preservazione dell'ordine per Go

By Lemon Mint views ...

Quando si implementano key-value store basati su LSM-tree o B-tree e indici di database, i campi compositi devono spesso essere combinati in un'unica chiave di byte.

I formati di serializzazione standard come JSON o Protocol Buffers non sono progettati per questo scopo, poiché i loro output serializzati in byte non preservano l'ordinamento naturale richiesto dai confronti bytewise senza segno (bytes.Compare o memcmp).

Schottky è una libreria Go progettata per codificare tuple composite multi-tipo in chiavi di byte che preservano l'ordinamento.

1go get gosuda.org/schottky@latest

Serializzazione vs. Chiavi di Ordinamento

Garantire un corretto ordinamento bytewise richiede di affrontare diversi dettagli di rappresentazione dei dati a basso livello:

  • Interi: la codifica standard in complemento a due big-endian interrompe l'ordinamento naturale a causa del bit di segno più significativo. L'inversione del bit di segno è necessaria per confronti byte senza segno corretti.
  • Numeri in virgola mobile: richiedono aggiustamenti del bit di segno, un ordinamento invertito per i valori negativi e una gestione coerente di NaN e -0.
  • Stringhe e slice di byte di lunghezza variabile: i confini dei campi devono essere preservati senza compromettere gli ordinamenti dei prefissi.
  • Requisiti delle chiavi composite: supporto per l'ordinamento ASC/DESC indipendente per ciascun campo, regole NULLS FIRST/LAST disaccoppiate, precedenza lessicografica rigorosa (i campi precedenti determinano l'ordine) e compatibilità con la scansione per prefisso.

Schottky converte ciascun valore in un payload canonico prima di applicare i tag di presenza e l'orientamento direzionale. Per i campi DESC, ogni byte del payload ASC viene invertito bit per bit (^b). Il posizionamento dei NULL è gestito tramite tag di presenza dedicati e opera indipendentemente dalla direzione di ordinamento.

Utilizzo di Base

Il seguente esempio costruisce una chiave composita costituita da un ID Account (ASC, NULLS LAST) e da un Nome (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 fornisce quattro configurazioni esplicite dell'ordine di ordinamento:

  • AscNullsFirst
  • AscNullsLast
  • DescNullsFirst
  • DescNullsLast

La posizione dei NULL non viene mai dedotta implicitamente. Se viene passato un valore Order non valido, il builder registra ErrInvalidOrder, che viene restituito alla chiamata di Key() o Err().

Scansione per Prefisso e Limiti di Intervallo

Le chiavi composite di Schottky non contengono intestazioni globali, metadati sul numero di campi, tag di tipo o trailer. Assumendo che lo schema sia noto in anticipo, le codifiche dei campi vengono semplicemente concatenate.

Grazie a questa struttura, i byte codificati dei campi iniziali formano un prefisso valido per le scansioni di intervallo. Nell'esempio sopra, accountPrefix può essere utilizzato direttamente come filtro per prefisso per scansionare tutti i record in cui ID Account == 42.

Per calcolare il limite superiore esclusivo per le scansioni di intervallo semi-aperte [prefix, upper), utilizzare 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        // Scansione di intervallo semi-aperta [accountPrefix, upper)
10} else {
11        // Scansione di intervallo aperto illimitata
12}

Nota: Builder.Len() deve essere misurato in corrispondenza di confini di campo puliti. Eseguire un'operazione di slicing all'interno del flusso di byte interno di un campo produce un prefisso non valido.

Zero Allocazioni e Gestione del Buffer

La generazione delle chiavi viene spesso eseguita su percorsi critici del database. Per eliminare le allocazioni nello heap e il sovraccarico dovuto al ridimensionamento dei buffer, Builder opera rigorosamente entro la capacità della slice fornita dal chiamante e non effettua riallocazioni internamente.

Se il buffer esaurisce la capacità, viene registrato ErrShortBuffer senza scrivere byte parziali. Le scritture dei campi sono atomiche e il primo errore incontrato viene conservato fino a quando non viene verificato tramite Key() o Err(). Fornire una capacità sufficiente in anticipo garantisce una codifica senza allocazioni.

Le dimensioni dei buffer possono essere calcolate in anticipo utilizzando funzioni di supporto come EncodedBytesSize, EncodedStringSize e EncodedDecimalSize, oppure tramite costanti di dimensione fissa. La chiave restituita fa riferimento direttamente al buffer fornito, lasciando la gestione del ciclo di vita della memoria al chiamante.

Il Decoder funziona in modo simmetrico: prende in prestito dati direttamente dalla chiave di input, richiede buffer di destinazione forniti dal chiamante per i campi di lunghezza variabile e fornisce Remaining() == 0 per rilevare byte residui o disallineamenti dello schema.

Tipi di Dati Supportati

  • Interi: con e senza segno (da 8 a 64 bit), Int128
  • Numeri in virgola mobile e numerici: Float32, Float64, testo decimale
  • Tipi di base: stringa binaria, slice di byte, booleano, rango di enumerazione
  • Data e ora: date, orari, orari con fuso, timestamp, durate, intervalli di calendario
  • Rete e identificatori: UUID, MAC, IP, prefisso IP, prefisso di rete canonico, LSN
  • Strutture composite: tuple annidate, intervalli (range) e codifiche strutturali grezze
  • Collation: chiavi di collation Unicode e token canonici esterni

Il mapping dei tipi SQL è allineato alle regole di ordinamento dei B-tree di PostgreSQL 18. I tipi che dipendono da cataloghi di database o dallo stato interno del motore vengono gestiti tramite il passaggio di token canonici esterni.

Collation delle Stringhe

Builder.String utilizza per impostazione predefinita l'ordine binario UTF-8 grezzo. Per un ordinamento sensibile alla localizzazione, Schottky fornisce un Collator immutabile e sicuro per l'accesso concorrente:

  • Collation deterministica: codifica la chiave di collation insieme ai byte UTF-8 grezzi per fornire un criterio di spareggio quando i pesi di collation sono identici.
  • Collation non deterministica: tratta le stringhe equivalenti per collation come identiche, omettendo lo spareggio sui byte grezzi.

Le versioni di Unicode e del profilo devono essere tracciate nei metadati dello schema. Se cambiano i provider di collation o le impostazioni del profilo, le chiavi esistenti devono essere ricostruite.

Gestione dello Schema

Poiché le chiavi Schottky sono sequenze di byte grezze prive di intestazione, il livello dello schema deve tenere traccia di:

  1. Sequenza dei campi e tipi di dati.
  2. Direzioni di ordinamento (ASC/DESC) e ordinamento dei NULL (NULLS FIRST/LAST).
  3. Regole di collation e normalizzazione delle stringhe.
  4. Versioni dei profili di Schottky e Collation.

Confrontare chiavi generate con schemi diversi o decodificarle con uno schema non corrispondente compromette le garanzie di ordinamento.

Prestazioni e Collegamenti

Su Go 1.27+, l'accelerazione SIMD portabile sperimentale può essere abilitata tramite GOEXPERIMENT=simd. I percorsi scalare e SIMD producono chiavi identiche byte per byte.