GoSuda

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

By Lemon Mint
views ...

Quando si implementano key-value stores 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 in byte serializzati non preservano l'ordine di ordinamento naturale richiesto dai confronti di byte non firmati (bytes.Compare o memcmp).

Schottky è una libreria Go progettata per codificare tuple composte di tipo multiplo in chiavi di byte che preservano l'ordine.

1go get gosuda.org/schottky@latest

Serialization vs. Sort Keys

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

  • Integers: La codifica standard big-endian in complemento a due interrompe l'ordinamento naturale a causa del bit di segno più significativo. L'inversione del bit di segno è necessaria per corretti confronti di byte non firmati.
  • Floating-point numbers: Richiede regolazioni del bit di segno, ordinamento invertito per valori negativi e una gestione coerente di NaN e -0.
  • Variable-length strings and byte slices: I confini dei campi devono essere preservati senza interrompere gli ordini di ordinamento dei prefissi.
  • Composite key requirements: Supporto per ordinamento ASC/DESC indipendente per campo, regole NULLS FIRST/LAST disaccoppiate, rigida precedenza lessicografica (i campi precedenti determinano l'ordine) e compatibilità con la scansione dei prefissi.

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

Basic Usage

Il seguente esempio costruisce una chiave composta costituita da un Account ID (ASC, NULLS LAST) e un Name (DESC, NULLS FIRST):

 1package main
 2
 3import (
 4        "fmt"
 5
 6        "gosuda.org/schottky"
 7)
 8
 9func main() {
10        // Inizializza l'archiviazione e il builder
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 fornisce quattro configurazioni esplicite di ordine di ordinamento:

  • AscNullsFirst
  • AscNullsLast
  • DescNullsFirst
  • DescNullsLast

Il posizionamento dei NULL non viene mai dedotto implicitamente. Se viene passato un valore Order non valido, il builder registra ErrInvalidOrder, che viene restituito quando si chiama Key() o Err().

Prefix Scanning and Range Bounds

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

A causa di questa disposizione, i byte codificati dei campi iniziali formano un prefisso valido per le scansioni di intervallo. Nell'esempio precedente, accountPrefix può essere utilizzato direttamente come filtro di prefisso per scansionare tutti i record in cui Account ID == 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 aperta illimitata
12}

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

Zero-Allocation and Buffer Management

La generazione delle chiavi viene eseguita frequentemente su percorsi critici del database. Per eliminare le allocazioni dell'heap e il sovraccarico di ridimensionamento del buffer, Builder opera rigorosamente entro la capacità dello slice fornito dal chiamante e non si riallocherà internamente.

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

Le dimensioni dei buffer possono essere calcolate in anticipo utilizzando funzioni di supporto come EncodedBytesSize, EncodedStringSize e EncodedDecimalSize, oppure tramite costanti a 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 direttamente dalla chiave di input, richiede buffer di destinazione forniti dal chiamante per i campi a lunghezza variabile e fornisce Remaining() == 0 per rilevare byte di coda o disallineamenti dello schema.

Supported Data Types

  • Integers: Con segno e senza segno (da 8 bit a 64 bit), Int128
  • Floating-Point & Numerics: Float32, Float64, Decimal Text
  • Basic Types: Binary String, Byte Slice, Boolean, Enum Rank
  • Date & Time: Date, Time, Zoned Time, Timestamp, Duration, Calendar Interval
  • Network & Identifiers: UUID, MAC, IP, IP Prefix, Canonical Network Prefix, LSN
  • Composite Structures: Tuple annidate, intervalli e codifiche strutturali grezze
  • Collation: Chiavi di confronto Unicode e token canonici esterni

La mappatura dei tipi SQL è allineata con le regole di ordinamento B-tree di PostgreSQL 18. I tipi dipendenti dai cataloghi di database o dallo stato del motore interno vengono gestiti passando token canonici esterni.

String Collation

Builder.String utilizza per impostazione predefinita l'ordine binario UTF-8 grezzo. Per un ordinamento consapevole delle impostazioni regionali, Schottky fornisce un Collator immutabile e sicuro per la concorrenza:

  • Deterministic Collation: Codifica la chiave di collation insieme ai byte UTF-8 grezzi per fornire un criterio di scompongo (tie-breaker) quando i pesi di collation sono identici.
  • Nondeterministic Collation: Tratta le stringhe con collation uguale come identiche, omettendo il criterio di scompongo in byte grezzi.

Le versioni Unicode e dei profili dovrebbero essere tracciate nello schema dei metadati. Se i provider di collation o le impostazioni del profilo cambiano, le chiavi esistenti devono essere ricreate.

Schema Management

Poiché le chiavi Schottky sono sequenze di byte grezze e prive di intestazione, lo strato di schema deve tracciare:

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

Il confronto di chiavi generate con schemi differenti o la decodifica rispetto a uno schema non corrispondente interrompe le garanzie di ordinamento.

Performance and Links

Su Go 1.27+, è possibile abilitare l'accelerazione SIMD portabile sperimentale utilizzando GOEXPERIMENT=simd. I percorsi scalari e SIMD producono chiavi identiche nei byte.