GoSuda

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

By Lemon Mint
views ...

Podczas implementacji magazynów klucz-wartość opartych na LSM-tree lub B-tree oraz indeksów bazodanowych, pola złożone często muszą być połączone w pojedynczy klucz bajtowy.

Standardowe formaty serializacji, takie jak JSON czy Protocol Buffers, nie zostały zaprojektowane do tego celu, ponieważ ich zserializowane wyjścia bajtowe nie zachowują naturalnego porządku sortowania wymaganego przez bezznakowe porównywania bajtowe (bytes.Compare lub memcmp).

Schottky jest biblioteką języka Go przeznaczoną do kodowania wielotypowych krotek złożonych w klucze bajtowe zachowujące porządek.

1go get gosuda.org/schottky@latest

Serializacja a Klucze Sortowania

Zagwarantowanie poprawnego sortowania bajtowego wymaga uwzględnienia kilku niskopoziomowych szczegółów reprezentacji danych:

  • Liczby całkowite: Standardowe kodowanie uzupełnień do dwóch w reprezentacji wielkoendianowej (big-endian) zaburza naturalny porządek z powodu najbardziej znaczącego bitu znaku. Odwrócenie bitu znaku jest niezbędne dla poprawnych bezznakowych porównań bajtowych.
  • Liczby zmiennoprzecinkowe: Wymagają modyfikacji bitu znaku, odwróconego porządku dla wartości ujemnych oraz spójnej obsługi wartości NaN oraz -0.
  • Ciągi znaków o zmiennej długości i wycinki bajtów: Granice pól muszą zostać zachowane bez naruszania porządku sortowania prefiksów.
  • Wymagania dotyczące kluczy złożonych: Obsługa niezależnego porządku ASC/DESC dla każdego pola, rozłączne reguły NULLS FIRST/LAST, ścisły priorytet leksykograficzny (wcześniejsze pola decydują o kolejności) oraz kompatybilność ze skanowaniem prefiksowym.

Schottky konwertuje każdą wartość do kanonicznej ładunku przed zastosowaniem znaczników obecności i orientacji kierunkowej. W przypadku pól DESC, każdy bajt ładunku ASC jest negowany bitowo (^b). Umiejscowienie wartości NULL jest obsługiwane za pomocą dedykowanych znaczników obecności i działa niezależnie od kierunku sortowania.

Podstawowe Użycie

Poniższy przykład buduje klucz złożony składający się z identyfikatora konta Account ID (ASC, NULLS LAST) oraz nazwy Name (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 udostępnia cztery wyraźne konfiguracje porządku sortowania:

  • AscNullsFirst
  • AscNullsLast
  • DescNullsFirst
  • DescNullsLast

Pozycjonowanie wartości NULL nigdy nie jest wnioskowane w sposób implikowany. Jeśli przekazana zostanie nieprawidłowa wartość Order, builder rejestruje błąd ErrInvalidOrder, który jest zwracany podczas wywoływania metody Key() lub Err().

Skanowanie Prefiksowe i Granice Zakresów

Klucze złożone Schottky nie zawierają żadnych globalnych nagłówków, metadanych liczby pól, znaczników typów ani elementów końcowych. Zakładając, że schemat jest znany wcześniej, kodowania pól są po prostu konkatenowane.

Z uwagi na taki układ, zakodowane bajty wiodących pól tworzą poprawny prefiks dla skanowania zakresów. W powyższym przykładzie accountPrefix może zostać bezpośrednio użyty jako filtr prefiksowy do przeskanowania wszystkich rekordów, w których Account ID == 42.

Aby obliczyć wyłączną górną granicę dla lewostronnie domkniętych i prawostronnie otwartych skanowań zakresu [prefix, upper), należy użyć funkcji 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        // Lewostronnie domknięte i prawostronnie otwarte skanowanie zakresu [accountPrefix, upper)
10} else {
11        // Nieograniczone otwarte skanowanie zakresu
12}

Uwaga: Metoda Builder.Len() musi być mierzona na czystych granicach pól. Wycinanie wewnątrz wewnętrznego strumienia bajtów pola generuje niepoprawny prefiks.

Alokacja Zerowa i Zarządzanie Buforem

Generowanie kluczy często odbywa się na krytycznych ścieżkach bazodanowych. Aby wyeliminować alokacje na stosie i narzut związany ze zmianą rozmiaru bufora, Builder działa ściśle w ramach pojemności dostarczonego przez wywołującego wycinka i nie dokonuje realokacji wewnętrznych.

Jeśli bufor wyczerpie swoją pojemność, rejestrowany jest błąd ErrShortBuffer bez zapisywania częściowych bajtów. Zapisy pól są atomowe, a pierwszy napotkany błąd jest zachowywany do momentu sprawdzenia przez Key() lub Err(). Zapewnienie odpowiedniej pojemności z góry gwarantuje kodowanie bez alokacji.

Rozmiary buforów można obliczyć wcześniej za pomocą funkcji pomocniczych, takich jak EncodedBytesSize, EncodedStringSize i EncodedDecimalSize, lub za pomocą stałych o stałym rozmiarze. Zwrócony klucz odwołuje się bezpośrednio do dostarczonego bufora, pozostawiając zarządzanie cyklem życia pamięci wywołującemu.

Komponent Decoder działa symetrycznie: pożycza dane bezpośrednio z klucza wejściowego, wymaga dostarczenia przez wywołującego buforów docelowych dla pól o zmiennej długości oraz udostępnia metodę Remaining() == 0 do wykrywania końcowych bajtów lub niedopasowań schematu.

Obsługiwane Typy Danych

  • Liczby całkowite: Ze znakiem i bez znaku (od 8-bitowych do 64-bitowych), Int128
  • Liczby zmiennoprzecinkowe i numeryczne: Float32, Float64, Decimal Text
  • Typy podstawowe: Binary String, Byte Slice, Boolean, Enum Rank
  • Data i Czas: Date, Time, Zoned Time, Timestamp, Duration, Calendar Interval
  • Sieć i Identyfikator: UUID, MAC, IP, IP Prefix, Canonical Network Prefix, LSN
  • Struktury złożone: Zagnieżdżone krotki, zakresy i surowe kodowania strukturalne
  • Kolacja (Collation): Unicode Collation Keys oraz zewnętrzne tokeny kanoniczne

Odwzorowanie typów SQL jest zgodne z regułami sortowania B-tree systemu PostgreSQL 18. Typy zależne od katalogów bazy danych lub wewnętrznego stanu silnika są obsługiwane poprzez przekazywanie zewnętrznych tokenów kanonicznych.

Kolacja Ciągów Znaków

Builder.String domyślnie używa surowego porządku binarnego UTF-8. W przypadku sortowania uwzględniającego ustawienia regionalne, Schottky udostępnia bezpieczną współbieżnie i niemutowalną strukturę Collator:

  • Kolacja deterministyczna: Koduje klucz kolacji wraz z surowymi bajtami UTF-8, aby zapewnić rozstrzyganie remisów, gdy wagi kolacji są identyczne.
  • Kolacja niedeterministyczna: Traktuje ciągi znaków o równej kolacji jako identyczne, pomijając surowy mechanizm rozstrzygania remisów na poziomie bajtów.

Wersje standardu Unicode i profilu powinny być śledzone w schematach metadanych. W przypadku zmiany dostawców kolacji lub ustawień profilu, istniejące klucze muszą zostać przebudowane.

Zarządzanie Schematem

Ponieważ klucze Schottky to surowe sekwencje bajtów pozbawione nagłówków, warstwa schematu musi śledzić:

  1. Sekwencję pól i typy danych.
  2. Kierunki sortowania (ASC/DESC) oraz porządek wartości NULL (NULLS FIRST/LAST).
  3. Kolację ciągów znaków i reguły normalizacji.
  4. Wersje profili Schottky oraz Collation.

Porównywanie kluczy wygenerowanych przy użyciu różnych schematów lub dekodowanie względem niedopasowanego schematu narusza gwarancje porządku.

Wydajność i Odnośniki

W środowisku Go 1.27+ eksperymentalna, przenośna akceleracja SIMD może zostać włączona za pomocą zmiennej GOEXPERIMENT=simd. Ścieżki skalarne i SIMD generują klucze identyczne bajtowo.