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 baz danych, pola złożone często muszą zostać połączone w jeden klucz bajtowy.

Standardowe formaty serializacji, takie jak JSON czy Protocol Buffers, nie są projektowane w tym celu, ponieważ ich bajtowe wyjścia serializacji nie zachowują naturalnej kolejności sortowania wymaganej przez porównania bajtów bez znaku (bytes.Compare lub memcmp).

Schottky to biblioteka w Go zaprojektowana do kodowania wielotypowych krotek złożonych w klucze bajtowe zachowujące porządek.

1go get gosuda.org/schottky@latest

Serializacja a klucze sortujące

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

  • Liczby całkowite: Standardowe kodowanie dwójkowe uzupełnień do dwóch w porządku big-endian łamie naturalny porządek ze względu na najbardziej znaczący bit znaku. Odwrócenie bitu znaku jest niezbędne do poprawnych porównań bajtowych bez znaku.
  • Liczby zmiennoprzecinkowe: Wymagają korekt bitu znaku, odwróconego porządku dla wartości ujemnych oraz spójnej obsługi NaN i -0.
  • Ciągi znaków o zmiennej długości i wycinki bajtów: Granice pól muszą być 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, niezależnych reguł NULLS FIRST/LAST, ścisłego pierwszeństwa leksykograficznego (wcześniejsze pola determinują porządek) oraz zgodności ze skanowaniem prefiksów.

Schottky przekształca każdą wartość w kanoniczny ładunek przed zastosowaniem znaczników obecności i orientacji kierunkowej. Dla pól DESC każdy bajt ładunku ASC jest bitowo odwracany (^b). Umieszczenie wartości NULL realizowane jest 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 (ASC, NULLS LAST) oraz nazwy (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 jawne konfiguracje porządku sortowania:

  • AscNullsFirst
  • AscNullsLast
  • DescNullsFirst
  • DescNullsLast

Pozycja NULL nigdy nie jest wnioskowana w sposób domyślny. Jeśli przekazana zostanie nieprawidłowa wartość Order, builder zapisuje ErrInvalidOrder, który zostaje zwrócony przy wywołaniu Key() lub Err().

Skanowanie prefiksów i granice zakresów

Klucze złożone Schottky nie zawierają globalnych nagłówków, metadanych liczby pól, znaczników typów ani stopek. Zakładając, że schemat jest znany z góry, kodowania pól są po prostu łączone.

Ze względu na taki układ zakodowane bajty wiodących pól tworzą prawidłowy prefiks dla skanów zakresowych. W powyższym przykładzie accountPrefix może być bezpośrednio użyty jako filtr prefiksowy do przeskanowania wszystkich rekordów, dla których Account ID == 42.

Aby obliczyć wykluczające górne ograniczenie dla skanów zakresów półotwartych [prefix, upper), należy użyć 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        // Skan zakresu półotwartego [accountPrefix, upper)
10} else {
11        // Skan zakresu otwartego bez ograniczeń
12}

Uwaga: Builder.Len() musi być mierzone na czystych granicach pól. Wycinanie wewnątrz wewnętrznego strumienia bajtów pola tworzy nieprawidłowy prefiks.

Brak alokacji i zarządzanie buforem

Generowanie kluczy często działa na krytycznych ścieżkach bazy danych. Aby wyeliminować alokacje na stercie i narzut zmiany rozmiaru bufora, Builder działa ściśle w obrębie pojemności wycinka dostarczonego przez wywołującego i nie dokonuje wewnętrznej realokacji.

Jeśli bufor wyczerpie pojemność, zapisywany jest 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 wystarczającej 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. Zwracany klucz odwołuje się bezpośrednio do dostarczonego bufora, pozostawiając zarządzanie cyklem życia pamięci wywołującemu.

Decoder działa symetrycznie: pożycza dane bezpośrednio z klucza wejściowego, wymaga dostarczonych przez wywołującego buforów docelowych dla pól o zmiennej długości i udostępnia Remaining() == 0, aby wykryć nadmiarowe bajty lub niezgodności schematu.

Obsługiwane typy danych

  • Liczby całkowite: ze znakiem i bez znaku (od 8 do 64 bitów), Int128
  • Liczby zmiennoprzecinkowe i numeryczne: Float32, Float64, tekst dziesiętny
  • Typy podstawowe: ciąg binarny, wycinek bajtów, wartość logiczna, ranga wyliczenia (Enum Rank)
  • Data i czas: Date, Time, Zoned Time, Timestamp, Duration, Calendar Interval
  • Sieć i identyfikatory: UUID, MAC, IP, IP Prefix, Canonical Network Prefix, LSN
  • Struktury złożone: zagnieżdżone krotki (Nested Tuples), zakresy (Ranges) oraz surowe kodowania strukturalne
  • Collation: Unicode Collation Keys oraz zewnętrzne kanoniczne tokeny

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

Porównania ciągów znaków

Builder.String domyślnie stosuje porządek binarny UTF-8. Do sortowania uwzględniającego ustawienia regionalne Schottky udostępnia bezpieczny współbieżnie, niezmienny Collator:

  • Deterministyczne porównywanie (Deterministic Collation): Koduje klucz porównania wraz z surowymi bajtami UTF-8, aby zapewnić rozstrzyganie remisów, gdy wagi porównania są identyczne.
  • Niedeterministyczne porównywanie (Nondeterministic Collation): Traktuje ciągi równe w porównaniu jako identyczne, pomijając rozstrzyganie remisów na podstawie surowych bajtów.

Wersje Unicode i profili powinny być śledzone w metadanych schematu. Jeśli dostawcy porównań lub ustawienia profilu ulegną zmianie, istniejące klucze muszą zostać odbudowane.

Zarządzanie schematem

Ponieważ klucze Schottky są surowymi sekwencjami bajtów bez nagłówków, warstwa schematu musi śledzić:

  1. Kolejność pól i typy danych.
  2. Kierunki sortowania (ASC/DESC) oraz porządek NULL (NULLS FIRST/LAST).
  3. Reguły porównywania i normalizacji ciągów znaków.
  4. Wersje profili Schottky i porównań.

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

Wydajność i odnośniki

W Go 1.27+ eksperymentalne przenośne przyspieszenie SIMD można włączyć za pomocą GOEXPERIMENT=simd. Ścieżki skalarne i SIMD tworzą identyczne bajtowo klucze.