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 basés sur des arbres LSM ou B-tree, ainsi que d'index de bases de données, 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 à cette fin, car leurs sorties sérialisées en octets ne préservent pas l'ordre de tri naturel requis par les comparaisons d'octets non signées (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

Sérialisation contre clés de tri

Garantir un tri octet par octet correct nécessite de traiter plusieurs détails bas niveau de représentation des données :

  • Entiers : L'encodage standard en complément à deux, en gros-boutiste, rompt l'ordre naturel en raison du bit de signe de poids fort. L'inversion du bit de signe est nécessaire pour des comparaisons d'octets non signées correctes.
  • Nombres à virgule flottante : Nécessitent des ajustements du bit de signe, un ordre inversé pour les valeurs négatives, et une gestion cohérente de NaN et de -0.
  • Chaînes de longueur variable et tranches d'octets : Les frontières des champs doivent être préservées sans rompre l'ordre de tri des préfixes.
  • Exigences des clés composites : Prise en charge d'un ordre ASC/DESC indépendant par champ, de règles NULLS FIRST/LAST découplées, d'une précédence lexicographique stricte (les champs précédents déterminent l'ordre) et de la compatibilité avec le parcours par préfixe.

Schottky convertit chaque valeur en une charge utile canonique avant d'appliquer les étiquettes de présence et l'orientation directionnelle. Pour les champs DESC, chaque octet de la charge utile ASC est inversé bit à bit (^b). Le placement des valeurs NULL est assuré par des étiquettes de présence dédiées et fonctionne indépendamment de la direction de tri.

Utilisation de base

L'exemple suivant construit une clé composite composée d'un identifiant 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 fournit quatre configurations explicites d'ordre de tri :

  • AscNullsFirst
  • AscNullsLast
  • DescNullsFirst
  • DescNullsLast

La position des valeurs NULL n'est jamais déduite implicitement. Si une valeur Order invalide est transmise, le builder enregistre ErrInvalidOrder, qui est renvoyée lors de l'appel à Key() ou Err().

Parcours par préfixe et bornes d'intervalle

Les clés composites Schottky ne contiennent ni en-têtes globaux, ni métadonnées de nombre de champs, ni étiquettes de type, ni fins de données. En supposant que le schéma soit connu à l'avance, les encodages des 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 parcours d'intervalle. Dans l'exemple ci-dessus, accountPrefix peut être directement utilisé comme filtre de préfixe pour parcourir tous les enregistrements où Account ID == 42.

Pour calculer la borne supérieure exclusive des parcours d'intervalle 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        // Parcours d'intervalle semi-ouvert [accountPrefix, upper)
10} else {
11        // Parcours d'intervalle ouvert non borné
12}

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

Absence d'allocation et gestion des tampons

La génération de clés s'exécute fréquemment sur des chemins critiques de bases de données. Pour éliminer les allocations sur le tas et le surcoût de redimensionnement des tampons, Builder travaille strictement dans la capacité de la tranche fournie par l'appelant et ne procède à aucune réallocation interne.

Si le tampon manque de capacité, ErrShortBuffer est enregistrée sans écriture partielle d'octets. Les écritures de champs sont atomiques, et la première erreur rencontrée est conservée jusqu'à sa vérification via Key() ou Err(). Fournir une capacité suffisante dès le départ garantit un encodage sans allocation.

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

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

Types de données pris en charge

  • Entiers : Signés et non signés (8 à 64 bits), Int128
  • Nombres à virgule flottante et numériques : Float32, Float64, Decimal Text
  • Types de base : Binary String, Byte Slice, Boolean, Enum Rank
  • Date et heure : Date, Time, Zoned Time, Timestamp, Duration, Calendar Interval
  • Réseau et identifiants : UUID, MAC, IP, IP Prefix, Canonical Network Prefix, LSN
  • Structures composites : Tuples imbriqués, Ranges, et encodages structurels bruts
  • Collation : Unicode Collation Keys et jetons canoniques externes

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

Collation des chaînes

Builder.String utilise par défaut l'ordre binaire UTF-8 brut. Pour un tri tenant compte de la locale, Schottky fournit un Collator immuable et sûr en contexte concurrent :

  • Collation déterministe : Encode la clé de collation accompagnée des octets UTF-8 bruts afin de fournir un critère de départage lorsque les poids de collation sont identiques.
  • Collation non déterministe : Traite les chaînes égales selon la collation comme identiques, en omettant le critère de départage sur les 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.

Gestion du schéma

Les clés Schottky étant des séquences d'octets brutes 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 valeurs NULL (NULLS FIRST/LAST).
  3. Les règles de collation et de normalisation des chaînes.
  4. Les versions des profils Schottky et de collation.

Comparer des clés générées avec des schémas différents, ou décoder avec un schéma incompatible, rompt les garanties d'ordre.

Performance et liens

Sur Go 1.27 et versions ultérieures, une accélération SIMD portable et expérimentale peut être activée à l'aide de GOEXPERIMENT=simd. Les chemins scalaire et SIMD produisent des clés identiques octet pour octet.