GoSuda

Schottky : Encodage de clés d'octets sans allocation et préservant l'ordre pour Go

By Lemon Mint
views ...

Lors de l'implémentation de magasins clé-valeur et d'index de bases de données basés sur des LSM-tree ou des B-tree, les champs composites doivent souvent être combinés en une seule clé d'octets.

Les formats de sérialisation standard tels que JSON ou Protocol Buffers ne sont pas conçus à cet effet, car leurs sorties d'octets sérialisés ne préservent pas l'ordre de tri naturel requis par les comparaisons d'octets non signés (bytes.Compare ou memcmp).

Schottky est une bibliothèque Go conçue pour encoder des tuples composites multi-types en clés d'octets préservant l'ordre.

1go get gosuda.org/schottky@latest

Serialization vs. Sort Keys

La garantie d'un tri correct au niveau des octets nécessite de traiter plusieurs détails de bas niveau de la représentation des données :

  • Integers: L'encodage standard big-endian en complément à deux brise l'ordre naturel en raison du bit de signe le plus significatif. L'inversion du bit de signe est nécessaire pour des comparaisons d'octets non signés correctes.
  • Floating-point numbers: Nécessite des ajustements du bit de signe, un ordre inversé pour les valeurs négatives et un traitement cohérent de NaN et -0.
  • Variable-length strings and byte slices: Les frontières des champs doivent être préservées sans rompre les ordres de tri par préfixe.
  • Composite key requirements: Prise en charge d'un tri ASC/DESC indépendant par champ, de règles NULLS FIRST/LAST dissociées, d'une présécedence lexicographique stricte (les champs précédents déterminent l'ordre) et d'une compatibilité avec le balayage par préfixe.

Schottky convertit chaque valeur en une charge utile canonique avant d'appliquer les balises de présence et l'orientation directionnelle. Pour les champs DESC, chaque octet de la charge utile ASC subit une inversion au niveau des bits (^b). Le placement des NULL est géré via des balises de présence dédiées et fonctionne indépendamment de la direction du tri.

Basic Usage

L'exemple suivant construit une clé composite composée d'un ID de compte (ASC, NULLS LAST) et d'un nom (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 propose quatre configurations explicites d'ordre de tri :

  • AscNullsFirst
  • AscNullsLast
  • DescNullsFirst
  • DescNullsLast

Le positionnement des NULL n'est jamais déduit implicitement. Si une valeur de Order invalide est transmise, le constructeur enregistre ErrInvalidOrder, qui est renvoyé lors de l'appel de Key() ou de Err().

Prefix Scanning and Range Bounds

Les clés composites Schottky ne contiennent aucun en-tête global, métadonnée de comptage de champs, balise de type ou fin de chaîne (trailer). En supposant que le schéma est connu à l'avance, les encodages de champs sont simplement concaténés.

En raison de cette disposition, les octets encodés des champs de tête forment un préfixe valide pour les balayages par plage. Dans l'exemple ci-dessus, accountPrefix peut être utilisé directement comme filtre de préfixe pour balayer tous les enregistrements où Account ID == 42.

Pour calculer la borne supérieure exclusive pour les balayages par plage semi-ouverts [prefix, upper), utilisez 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        // Balayage par plage semi-ouvert [accountPrefix, upper)
10} else {
11        // Balayage par plage ouvert non borné
12}

Remarque : Builder.Len() doit être mesuré à des frontières de champs propres. Le découpage (slicing) à l'intérieur du flux d'octets interne d'un champ produit un préfixe invalide.

Zero-Allocation and Buffer Management

La génération de clés s'exécute fréquemment sur des chemins critiques de base de données. Pour éliminer les allocations de tas (heap allocations) et les surcharges de redimensionnement de tampons, Builder fonctionne strictement dans la capacité du tampon fourni par l'appelant et ne réallouera pas en interne.

Si le tampon s'épuise, ErrShortBuffer est enregistré sans écrire d'octets partiels. Les écritures de champs sont atomiques, et la première erreur rencontrée est préservée jusqu'à ce qu'elle soit vérifiée via Key() ou Err(). Fournir une capacité suffisante en amont garantit un encodage sans allocation.

Les tailles de tampon peuvent être calculées à l'avance à l'aide de fonctions d'assistance telles que EncodedBytesSize, EncodedStringSize et EncodedDecimalSize, ou via des constantes de taille fixe. La clé renvoyée référence directement le tampon fourni, laissant la gestion du cycle de vie de la mémoire à l'appelant.

Le Decoder fonctionne de manière symétrique : il emprunte directement les données de la clé d'entrée, nécessite des tampons de destination fournis par l'appelant pour les champs à longueur variable, et fournit Remaining() == 0 pour détecter les octets de fin ou les incompatibilités de schéma.

Supported Data Types

  • Integers: Signés et non signés (8 bits à 64 bits), Int128
  • Floating-Point & Numerics: Float32, Float64, Texte décimal
  • Basic Types: Chaîne binaire, tranche d'octets (byte slice), booléen, rang d'énumération
  • Date & Time: Date, Heure, Heure avec fuseau horaire, Horodatage, Durée, Intervalle de calendrier
  • Network & Identifiers: UUID, MAC, IP, Préfixe IP, Préfixe réseau canonique, LSN
  • Composite Structures: Tuples imbriqués, plages et encodages structurels bruts
  • Collation: Clés de collation Unicode et jetons canoniques externes

Le mappage des types SQL est aligné sur les règles de tri des B-tree de PostgreSQL 18. Les types dépendant des catalogues de la base de données ou de l'état interne du moteur sont traités en passant des jetons canoniques externes.

String Collation

Builder.String utilise par défaut l'ordre binaire brut UTF-8. Pour un tri tenant compte des paramètres régionaux (locale), Schottky fournit un Collator immuable et sûr pour la concurrence :

  • Deterministic Collation: Encode la clé de collation avec les octets bruts UTF-8 pour fournir un départage lorsque les poids de collation sont identiques.
  • Nondeterministic Collation: Traite les chaînes dont la collation est égale comme identiques, en omettant le départage par octets bruts.

Les versions Unicode et de profil doivent être suivies dans le schéma de métadonnées. Si les fournisseurs de collation ou les paramètres de profil changent, les clés existantes doivent être reconstruites.

Schema Management

Puisque les clés Schottky sont des séquences d'octets brutes et sans en-tête, la couche de schéma doit suivre :

  1. La séquence des champs et les types de données.
  2. Les directions de tri (ASC/DESC) et l'ordre des NULL (NULLS FIRST/LAST).
  3. La collation des chaînes et les règles de normalisation.
  4. Les versions des profils Schottky et Collation.

La comparaison de clés générées avec des schémas différents ou le décodage par rapport à un schéma incompatible brise les garanties de tri.

Performance and Links

Sur Go 1.27+, l'accélération SIMD portable expérimentale peut être activée à l'aide de GOEXPERIMENT=simd. Les chemins scalaires et SIMD produisent des clés identiques au niveau des octets.