GoSuda

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

By Lemon Mint
views ...

Bei der Implementierung von LSM-Tree- oder B-Tree-basierten Key-Value-Stores und Datenbankindizes müssen composite Felder häufig zu einem einzigen Byte-Key kombiniert werden.

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

Schottky ist eine Go-Bibliothek, die entwickelt wurde, um multi-type composite Tuples in order-preserving Byte-Keys zu kodieren.

1go get gosuda.org/schottky@latest

Serialization vs. Sort Keys

Die Gewährleistung einer korrekten bytewise Sortierung erfordert die Berücksichtigung mehrerer low-level Datenrepräsentationsdetails:

  • Integers: Die standardmäßige Two's Complement Big-Endian-Kodierung bricht die natürliche Reihenfolge aufgrund des höchstwertigen Vorzeichenbits. Das Invertieren des Vorzeichenbits ist für korrekte unsigned Byte-Vergleiche erforderlich.
  • Floating-point numbers: Erfordert Anpassungen des Vorzeichenbits, eine invertierte Reihenfolge für negative Werte sowie eine konsistente Behandlung von NaN und -0.
  • Variable-length strings and byte slices: Feldgrenzen müssen bewahrt werden, ohne die Prefix-Sortierreihenfolge zu verletzen.
  • Composite key requirements: Unterstützung für unabhängige ASC/DESC-Sortierungen pro Feld, entkoppelte NULLS FIRST/LAST-Regeln, strenge lexikografische Präzedenz (frühere Felder bestimmen die Reihenfolge) und Kompatibilität mit Prefix-Scans.

Schottky konvertiert jeden Wert in eine kanonische Nutzlast, bevor Prätags und die direktungsbezogene Orientierung angewendet werden. Bei DESC-Feldern wird jedes Byte der ASC-Nutzlast bitweise invertiert (^b). Die NULL-Platzierung wird über dedizierte Prätags gehandhabt und arbeitet unabhängig von der Sortierrichtung.

Basic Usage

Das folgende Beispiel baut einen composite Key auf, der aus einer Account-ID (ASC, NULLS LAST) und einem Namen (DESC, NULLS FIRST) besteht:

 1package main
 2
 3import (
 4        "fmt"
 5
 6        "gosuda.org/schottky"
 7)
 8
 9func main() {
10        // Speicher vorab zuweisen
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 bietet vier explizite Sortierreihenfolge-Konfigurationen:

  • AscNullsFirst
  • AscNullsLast
  • DescNullsFirst
  • DescNullsLast

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

Prefix Scanning and Range Bounds

Schottky composite Keys enthalten keine globalen Header, Feldanzahl-Metadaten, Typ-Tags oder Trailer. Unter der Annahme, dass das Schema im Voraus bekannt ist, werden die Feldkodierungen einfach verkettet.

Aufgrund dieses Layouts bilden die kodierten Bytes führender Felder einen gültigen Prefix für Bereichsscans. Im obigen Beispiel kann accountPrefix direkt als Prefix-Filter verwendet werden, um alle Datensätze zu scannen, bei denen Account ID == 42.

Um die exklusive Obergrenze für halboffene [prefix, upper) Bereichsscans zu berechnen, verwenden Sie 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        // Halboffener [accountPrefix, upper) Bereichsscan
10} else {
11        // Unbeschränkter offener Bereichsscan
12}

Hinweis: Builder.Len() muss an sauberen Feldgrenzen gemessen werden. Das Aufteilen innerhalb des internen Byte-Streams eines Feldes erzeugt einen ungültigen Prefix.

Zero-Allocation and Buffer Management

Die Schlüsselgenerierung läuft häufig auf kritischen Datenbankpfaden. Um Heap-Allokationen und den Overhead der Puffergrößenanpassung zu eliminieren, arbeitet Builder streng innerhalb der Kapazität des vom Aufrufer bereitgestellten Slices und führt keine interne Reallokation durch.

Wenn der Puffer keine Kapazität mehr hat, wird ErrShortBuffer aufgezeichnet, ohne partielle Bytes zu schreiben. Feldwrites sind atomor, und der erste angetroffene Fehler wird beibehalten, bis er über Key() oder Err() überprüft wird. Die Bereitstellung von ausreichend Kapazität im Voraus gewährleistet eine Zero-Allocation-Kodierung.

Puffergrößen können im Voraus mithilfe von Hilfsfunktionen wie EncodedBytesSize, EncodedStringSize und EncodedDecimalSize oder über Festgrößenkonstanten berechnet werden. Der zurückgegebene Key referenziert den bereitgestellten Puffer direkt, wodurch das Speicher-Lifecycle-Management dem Aufrufer überlassen bleibt.

Der Decoder arbeitet symmetrisch: Er leiht direkt aus dem Eingabe-Key, benötigt vom Aufrufer bereitgestellte Zielpuffer für Felder variabler Länge und bietet Remaining() == 0, um nachfolgende Bytes oder Schema-Nichtübereinstimmungen zu erkennen.

Supported Data Types

  • Integers: Signed und Unsigned (8-bit bis 64-bit), Int128
  • Floating-Point & Numerics: Float32, Float64, Dezimaltext
  • Basic Types: Binärer String, Byte-Slice, Boolean, Enum-Rang
  • Date & Time: Datum, Uhrzeit, Zonenzeit, Zeitstempel, Dauer, Kalenderintervall
  • Network & Identifiers: UUID, MAC, IP, IP-Prefix, Kanonischer Netzwerk-Prefix, LSN
  • Composite Structures: Verschachtelte Tuples, Bereiche und rohe strukturelle Kodierungen
  • Collation: Unicode Collation Keys und externe kanonische Token

Das SQL-Typ-Mapping ist auf die B-Tree-Sortierregeln von PostgreSQL 18 abgestimmt. Typen, die von Datenbankkatalogen oder dem internen Engine-Zustand abhängen, werden durch die Übergabe externer kanonischer Token gehandhabt.

String Collation

Builder.String standardisiert auf rohe UTF-8-Binärreihenfolge. Für sprachabhängiges Sortieren bietet Schottky einen nebenläufigkeitssicheren, unveränderlichen Collator:

  • Deterministic Collation: Kodiert den Collation-Key zusammen mit rohen UTF-8-Bytes, um einen Tie-Breaker bereitzustellen, wenn die Collation-Gewichtungen identisch sind.
  • Nondeterministic Collation: Behandelt Collation-gleiche Strings als identisch, wobei der rohe Byte-Tie-Breaker weggelassen wird.

Unicode- und Profilversionen sollten im Metadatenschema verfolgt werden. Wenn sich Collation-Provider oder Profileinstellungen ändern, müssen bestehende Keys neu erstellt werden.

Schema Management

Da Schottky-Keys rohe Byte-Sequenzen ohne Header sind, muss die Schemaschicht Folgendes nachverfolgen:

  1. Feldsequenz und Datentypen.
  2. Sortierrichtungen (ASC/DESC) und NULL-Reihenfolge (NULLS FIRST/LAST).
  3. String-Collation- und Normalisierungsregeln.
  4. Schottky- und Collation-Profilversionen.

Das Vergleichen von Keys, die mit verschiedenen Schemas generiert wurden, oder das Dekodieren gegen ein nicht übereinstimmendes Schema bricht die Sortiergarantien.

Performance and Links

Unter Go 1.27+ kann die experimentelle portable SIMD-Beschleunigung mit GOEXPERIMENT=simd aktiviert werden. Skalare und SIMD-Pfade erzeugen byte-identische Keys.