GoSuda

Schottky: Pengodean Kunci Byte untuk Go yang Bebas Alokasi dan Mempertahankan Urutan

By Lemon Mint views ...

Ketika mengimplementasikan penyimpanan kunci-nilai berbasis LSM-tree atau B-tree serta indeks basis data, field komposit sering kali perlu digabungkan menjadi satu kunci byte tunggal.

Format serialisasi standar seperti JSON atau Protocol Buffers tidak dirancang untuk tujuan ini karena keluaran byte hasil serialisasinya tidak mempertahankan urutan pengurutan alami yang diperlukan oleh perbandingan bytewise tanpa tanda (bytes.Compare atau memcmp).

Schottky adalah pustaka Go yang dirancang untuk mengodekan tuple komposit multi-tipe menjadi kunci byte yang mempertahankan urutan.

1go get gosuda.org/schottky@latest

Serialisasi vs. Sort Keys

Menjamin pengurutan bytewise yang benar memerlukan penanganan beberapa detail representasi data tingkat rendah:

  • Integer: Encoding two's complement big-endian standar merusak urutan alami karena bit tanda paling signifikan. Membalik bit tanda diperlukan untuk perbandingan byte tanpa tanda yang benar.
  • Bilangan floating-point: Memerlukan penyesuaian bit tanda, urutan terbalik untuk nilai negatif, serta penanganan yang konsisten untuk NaN dan -0.
  • String dan byte slice dengan panjang variabel: Batas field harus dipertahankan tanpa merusak urutan pengurutan prefix.
  • Persyaratan kunci komposit: Dukungan untuk urutan ASC/DESC yang independen per field, aturan NULLS FIRST/LAST yang terpisah, presedensi leksikografis yang ketat (field sebelumnya menentukan urutan), serta kompatibilitas dengan prefix scanning.

Schottky mengonversi setiap nilai menjadi payload kanonik sebelum menerapkan tag keberadaan dan orientasi arah. Untuk field DESC, setiap byte dari payload ASC dibalik secara bitwise (^b). Penempatan NULL ditangani melalui tag keberadaan khusus dan beroperasi secara independen dari arah pengurutan.

Penggunaan Dasar

Contoh berikut membangun kunci komposit yang terdiri dari Account ID (ASC, NULLS LAST) dan 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        // Tulis Account ID sebagai int64 dengan urutan ASC, NULLS LAST
14        builder.Int64(42, schottky.AscNullsLast)
15        accountPrefixLen := builder.Len()
16
17        // Tulis Name sebagai string dengan urutan DESC, NULLS FIRST
18        builder.String("Ada", schottky.DescNullsFirst)
19        key, err := builder.Key()
20
21        if err != nil {
22                panic(err)
23        }
24        accountPrefix := key[:accountPrefixLen]
25        fmt.Printf("key=%x\nprefix=%x\n", key, accountPrefix)
26}

Schottky menyediakan empat konfigurasi urutan pengurutan yang eksplisit:

  • AscNullsFirst
  • AscNullsLast
  • DescNullsFirst
  • DescNullsLast

Posisi NULL tidak pernah diinferensi secara implisit. Jika nilai Order yang tidak valid diberikan, builder mencatat ErrInvalidOrder, yang dikembalikan ketika memanggil Key() atau Err().

Prefix Scanning dan Batas Rentang

Kunci komposit Schottky tidak mengandung header global, metadata jumlah field, tag tipe, maupun trailer. Dengan asumsi skema telah diketahui sebelumnya, encoding field hanya digabungkan secara berurutan.

Karena tata letak ini, byte terenkode dari field-field awal membentuk prefix yang valid untuk range scan. Dalam contoh di atas, accountPrefix dapat langsung digunakan sebagai filter prefix untuk memindai semua rekaman dengan Account ID == 42.

Untuk menghitung batas atas eksklusif bagi range scan half-open [prefix, upper), gunakan 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        // Range scan half-open [accountPrefix, upper)
10} else {
11        // Range scan terbuka tanpa batas
12}

Catatan: Builder.Len() harus diukur pada batas field yang bersih. Memotong slice di dalam aliran byte internal sebuah field menghasilkan prefix yang tidak valid.

Zero-Allocation dan Manajemen Buffer

Pembuatan kunci sering dijalankan pada jalur kritis basis data. Untuk menghilangkan alokasi heap dan overhead pengubahan ukuran buffer, Builder bekerja secara ketat dalam kapasitas slice yang disediakan pemanggil dan tidak akan melakukan realokasi secara internal.

Jika kapasitas buffer habis, ErrShortBuffer dicatat tanpa menulis byte parsial. Penulisan field bersifat atomik, dan error pertama yang ditemui tetap dipertahankan hingga diperiksa melalui Key() atau Err(). Menyediakan kapasitas yang memadai sejak awal memastikan encoding tanpa alokasi.

Ukuran buffer dapat dihitung di muka menggunakan fungsi bantu seperti EncodedBytesSize, EncodedStringSize, dan EncodedDecimalSize, atau melalui konstanta berukuran tetap. Kunci yang dikembalikan mereferensikan buffer yang disediakan secara langsung, sehingga pengelolaan siklus hidup memori diserahkan kepada pemanggil.

Decoder bekerja secara simetris: ia meminjam langsung dari kunci masukan, memerlukan buffer tujuan yang disediakan pemanggil untuk field dengan panjang variabel, dan menyediakan Remaining() == 0 untuk mendeteksi byte sisa atau ketidaksesuaian skema.

Tipe Data yang Didukung

  • Integer: Bertanda dan tanpa tanda (8-bit hingga 64-bit), Int128
  • Floating-Point & Numerik: Float32, Float64, Decimal Text
  • Tipe Dasar: Binary String, Byte Slice, Boolean, Enum Rank
  • Tanggal & Waktu: Date, Time, Zoned Time, Timestamp, Duration, Calendar Interval
  • Jaringan & Identifier: UUID, MAC, IP, IP Prefix, Canonical Network Prefix, LSN
  • Struktur Komposit: Nested Tuples, Ranges, dan raw structural encodings
  • Collation: Unicode Collation Keys dan external canonical tokens

Pemetaan tipe SQL selaras dengan aturan pengurutan B-tree PostgreSQL 18. Tipe yang bergantung pada katalog basis data atau state internal engine ditangani dengan melewatkan external canonical tokens.

Collation String

Builder.String secara default menggunakan urutan biner UTF-8 mentah. Untuk pengurutan yang sadar locale, Schottky menyediakan Collator yang aman untuk konkurensi dan bersifat immutable:

  • Collation Deterministik: Mengodekan kunci collation bersama byte UTF-8 mentah untuk menjadi pemutus seri ketika bobot collation identik.
  • Collation Nondeterministik: Memperlakukan string yang setara menurut collation sebagai identik, dengan menghilangkan pemutus seri byte mentah.

Versi Unicode dan profil harus dicatat dalam skema metadata. Jika penyedia collation atau pengaturan profil berubah, kunci yang ada harus dibangun ulang.

Manajemen Skema

Karena kunci Schottky berupa urutan byte mentah tanpa header, lapisan skema harus melacak:

  1. Urutan field dan tipe data.
  2. Arah pengurutan (ASC/DESC) dan urutan NULL (NULLS FIRST/LAST).
  3. Aturan collation dan normalisasi string.
  4. Versi profil Schottky dan Collation.

Membandingkan kunci yang dihasilkan dengan skema berbeda, atau mendekode terhadap skema yang tidak cocok, merusak jaminan urutan.

Performa dan Tautan

Pada Go 1.27+, akselerasi SIMD portabel yang bersifat eksperimental dapat diaktifkan menggunakan GOEXPERIMENT=simd. Jalur scalar dan SIMD menghasilkan kunci yang identik byte per byte.