GoSuda

Schottky: Zero-Allocation, Order-Preserving Byte-Key Encoding für Go

By Lemon Mint views ...

Bei der Implementierung von LSM-Tree- oder B-Tree-basierten Schlüssel-Wert-Speichern und Datenbankindizes müssen zusammengesetzte Felder häufig zu einem einzigen Byte-Schlüssel kombiniert werden.

Standardisierte Serialisierungsformate wie JSON oder Protocol Buffers sind für diesen Zweck nicht konzipiert, da ihre serialisierten Byte-Ausgaben die natürliche Sortierreihenfolge nicht bewahren, die für vorzeichenlose byteweise Vergleiche (bytes.Compare oder memcmp) erforderlich ist.

Schottky ist eine Go-Bibliothek, die dafür entwickelt wurde, mehrtypige zusammengesetzte Tupel in reihenfolgeerhaltende Byte-Schlüssel zu kodieren.

1go get gosuda.org/schottky@latest

Serialisierung vs. Sortierschlüssel

Eine korrekte bytweise Sortierung erfordert die Berücksichtigung mehrerer grundlegender Details der Datendarstellung:

  • Ganzzahlen: Die übliche Zweierkomplement-Kodierung in Big-Endian-Reihenfolge zerstört aufgrund des höchstwertigen Vorzeichenbits die natürliche Ordnung. Das Invertieren des Vorzeichenbits ist für korrekte vorzeichenlose Byte-Vergleiche notwendig.
  • Gleitkommazahlen: Erfordern Anpassungen des Vorzeichenbits, eine umgekehrte Ordnung für negative Werte sowie eine konsistente Behandlung von NaN und -0.
  • Variabel lange Zeichenketten und Byte-Slices: Feldgrenzen müssen erhalten bleiben, ohne die Präfix-Sortierreihenfolgen zu verletzen.
  • Anforderungen an zusammengesetzte Schlüssel: Unterstützung für unabhängige ASC/DESC-Sortierung je Feld, entkoppelte NULLS-FIRST/LAST-Regeln, strikte lexikografische Priorität (frühere Felder bestimmen die Reihenfolge) und Kompatibilität mit Präfix-Scans.

Schottky wandelt jeden Wert in eine kanonische Nutzlast um, bevor Präsenz-Tags und Richtungsorientierung angewendet werden. Bei DESC-Feldern wird jedes Byte der ASC-Nutzlast bitweise invertiert (^b). Die NULL-Platzierung erfolgt über eigene Präsenz-Tags und ist unabhängig von der Sortierrichtung.

Grundlegende Verwendung

Das folgende Beispiel erstellt einen zusammengesetzten Schlüssel aus einer Konto-ID (ASC, NULLS LAST) und einem Namen (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 bietet vier explizite Sortierkonfigurationen:

  • AscNullsFirst
  • AscNullsLast
  • DescNullsFirst
  • DescNullsLast

Die NULL-Positionierung wird niemals implizit abgeleitet. Wird ein ungültiger Order-Wert übergeben, vermerkt der Builder ErrInvalidOrder, das beim Aufruf von Key() oder Err() zurückgegeben wird.

Präfix-Scans und Bereichsgrenzen

Schottky-Schlüssel enthalten keine globalen Header, keine Metadaten zur Feldanzahl, keine Typ-Tags und keine Trailer. Unter der Voraussetzung, dass das Schema im Voraus bekannt ist, werden die Feldkodierungen einfach aneinandergereiht.

Aufgrund dieses Layouts bilden die kodierten Bytes der führenden Felder ein gültiges Präfix für Bereichsscans. Im obigen Beispiel kann accountPrefix direkt als Präfixfilter verwendet werden, um alle Datensätze mit Konto-ID == 42 zu durchsuchen.

Zur Berechnung der exklusiven oberen Grenze für halboffene [prefix, upper)-Bereichsscans wird PrefixUpperBound verwendet:

 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        // Halboffener Bereichsscan [accountPrefix, upper)
10} else {
11        // Unbegrenzter offener Bereichsscan
12}

Hinweis: Builder.Len() muss an sauberen Feldgrenzen gemessen werden. Ein Schnitt innerhalb des internen Byte-Stroms eines Feldes erzeugt ein ungültiges Präfix.

Nullallokation und Pufferverwaltung

Die Schlüsselgenerierung läuft häufig auf kritischen Datenbankpfaden. Um Heap-Allokationen und den Aufwand für Pufferneuanpassungen zu vermeiden, arbeitet Builder ausschließlich innerhalb der Kapazität des vom Aufrufer bereitgestellten Slices und alloziert intern nicht neu.

Wenn der Puffer keine Kapazität mehr besitzt, wird ErrShortBuffer vermerkt, ohne teilweise Bytes zu schreiben. Feldschreibvorgänge sind atomar, und der erste aufgetretene Fehler bleibt erhalten, bis er über Key() oder Err() abgefragt wird. Eine ausreichende Kapazität im Voraus gewährleistet eine Kodierung ohne Allokationen.

Puffergrößen können im Voraus mithilfe von Hilfsfunktionen wie EncodedBytesSize, EncodedStringSize und EncodedDecimalSize oder über feste Konstanten berechnet werden. Der zurückgegebene Schlüssel verweist direkt auf den bereitgestellten Puffer, wobei die Verwaltung des Speicherlebenszyklus dem Aufrufer obliegt.

Der Decoder arbeitet symmetrisch: Er leiht sich Daten direkt aus dem Eingabeschlüssel, benötigt vom Aufrufer bereitgestellte Zielpuffer für variabel lange Felder und liefert Remaining() == 0, um nachfolgende Bytes oder Schema-Abweichungen zu erkennen.

Unterstützte Datentypen

  • Ganzzahlen: Vorzeichenbehaftet und vorzeichenlos (8 bis 64 Bit), Int128
  • Gleitkomma- und numerische Typen: Float32, Float64, Dezimaltext
  • Grundtypen: Binäre Zeichenkette, Byte-Slice, Boolean, Enum-Rang
  • Datum und Zeit: Date, Time, Zoned Time, Timestamp, Duration, Calendar Interval
  • Netzwerk und Kennungen: UUID, MAC, IP, IP Prefix, Canonical Network Prefix, LSN
  • Zusammengesetzte Strukturen: Verschachtelte Tupel, Ranges und rohe strukturelle Kodierungen
  • Kollation: Unicode-Kollationsschlüssel und externe kanonische Token

Die Zuordnung von SQL-Typen ist an den B-Tree-Sortierregeln von PostgreSQL 18 ausgerichtet. Typen, die von Datenbankkatalogen oder internem Engine-Zustand abhängen, werden durch die Übergabe externer kanonischer Token behandelt.

Zeichenkettenkollation

Builder.String verwendet standardmäßig die binäre Reihenfolge von rohem UTF-8. Für lokalisierte Sortierung stellt Schottky einen nebenläufigkeitssicheren, unveränderlichen Collator bereit:

  • Deterministische Kollation: Kodiert den Kollationsschlüssel zusammen mit den rohen UTF-8-Bytes, um einen Tie-Breaker bereitzustellen, wenn die Kollationsgewichte identisch sind.
  • Nicht-deterministische Kollation: Behandelt kollationsgleiche Zeichenketten als identisch und verzichtet auf den rohen Byte-Tie-Breaker.

Unicode- und Profilversionen sollten im Metadatenschema erfasst werden. Ändern sich Kollationsanbieter oder Profileinstellungen, müssen bestehende Schlüssel neu aufgebaut werden.

Schemaverwaltung

Da Schottky-Schlüssel rohe, headerlose Byte-Sequenzen sind, muss die Schemaebene Folgendes erfassen:

  1. Feldreihenfolge und Datentypen.
  2. Sortierrichtungen (ASC/DESC) und NULL-Reihenfolge (NULLS FIRST/LAST).
  3. Zeichenkettenkollation und Normalisierungsregeln.
  4. Versionen der Schottky- und Kollationsprofile.

Der Vergleich von Schlüsseln, die mit unterschiedlichen Schemata erzeugt wurden, oder die Dekodierung mit einem nicht passenden Schema verletzt die Garantien der Sortierreihenfolge.

Leistung und Links

Ab Go 1.27 kann eine experimentelle, portable SIMD-Beschleunigung mit GOEXPERIMENT=simd aktiviert werden. Skalare und SIMD-Pfade erzeugen byte-identische Schlüssel.