GoSuda

Schottky: Enkode Kunci-Byte Tanpa-Alokasi dan Pelindung-Urutan untuk Go

By Lemon Mint
views ...

Saat mengimplementasikan penyimpanan key-value berbasis LSM-tree atau B-tree dan indeks basis data, bidang komposit sering kali perlu digabungkan menjadi satu byte key.

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

Schottky adalah sebuah Pustaka Go yang dirancang untuk mengenkode tuple komposit multi-tipe menjadi byte key yang mempertahankan urutan.

1go get gosuda.org/schottky@latest

Serialisasi vs. Key Pengurutan

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

  • Bilangan Bulat: Enkoding big-endian two's complement standar merusak urutan alami karena bit tanda yang paling signifikan. Membalikkan bit tanda diperlukan untuk perbandingan byte tanpa tanda yang benar.
  • Bilangan Titik Mengambang: Membutuhkan penyesuaian bit tanda, pengurutan terbalik untuk nilai negatif, serta penanganan yang konsisten terhadap NaN dan -0.
  • String Panjang Variabel dan Irisan Byte: Batas bidang harus dipertahankan tanpa merusak urutan pengurutan prefiks.
  • Persyaratan Key Komposit: Dukungan untuk pengurutan ASC/DESC independen per bidang, aturan NULLS FIRST/LAST yang terlepas, prioritas leksikografis yang ketat (bidang sebelumnya menentukan urutan), serta kompatibilitas dengan pemindaian prefiks.

Schottky mengubah setiap nilai menjadi payload kanonis sebelum menerapkan tag keberadaan dan orientasi direksional. Untuk bidang 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 sebuah key komposit yang terdiri dari ID Akun (ASC, NULLS LAST) dan Nama (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 menyediakan empat konfigurasi urutan pengurutan yang eksplisit:

  • AscNullsFirst
  • AscNullsLast
  • DescNullsFirst
  • DescNullsLast

Posisi NULL tidak pernah disimpulkan secara implisit. Jika nilai Order yang tidak valid diteruskan, pembangun akan mencatat ErrInvalidOrder, yang dikembalikan saat memanggil Key() atau Err().

Pemindaian Prefiks dan Batas Rentang

Key komposit Schottky tidak berisi tajuk global, metadata jumlah bidang, tag tipe, atau trailer. Dengan asumsi skema telah diketahui sebelumnya, enkoding bidang cukup digabungkan.

Karena tata letak ini, byte terenkode dari bidang terdepan membentuk prefiks yang valid untuk pemindaian rentang. Pada contoh di atas, accountPrefix dapat langsung digunakan sebagai filter prefiks untuk memindai semua catatan di mana Account ID == 42.

Untuk menghitung batas atas eksklusif bagi pemindaian rentang setengah terbuka [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        // Pemindaian rentang setengah terbuka [accountPrefix, upper)
10} else {
11        // Pemindaian rentang terbuka tak terbatas
12}

Catatan: Builder.Len() harus diukur pada batas bidang yang bersih. Mengiris di dalam aliran byte internal suatu bidang menghasilkan prefiks yang tidak valid.

Alokasi Nol dan Manajemen Buffer

Pembuatan key sering kali berjalan pada jalur kritis basis data. Untuk menghilangkan alokasi heap dan overhead perubahan ukuran buffer, Builder bekerja secara ketat dalam kapasitas irisan yang disediakan oleh pemanggil dan tidak akan melakukan alokasi ulang secara internal.

Jika buffer kehabisan kapasitas, ErrShortBuffer akan dicatat tanpa menulis byte parsial. Penulisan bidang bersifat atomik, dan kesalahan pertama yang ditemukan dipertahankan hingga diperiksa melalui Key() atau Err(). Menyediakan kapasitas yang memadai sejak awal memastikan enkoding tanpa alokasi.

Ukuran buffer dapat dihitung sebelumnya menggunakan fungsi pembantu seperti EncodedBytesSize, EncodedStringSize, dan EncodedDecimalSize, atau melalui konstanta berukuran tetap. Key yang dikembalikan merujuk langsung ke buffer yang disediakan, menyerahkan manajemen siklus hidup memori kepada pemanggil.

Decoder bekerja secara simetris: meminjam langsung dari key masukan, memerlukan buffer tujuan yang disediakan oleh pemanggil untuk bidang panjang variabel, dan menyediakan Remaining() == 0 untuk mendeteksi byte penutup atau ketidakcocokan skema.

Tipe Data yang Didukung

  • Bilangan Bulat: Bertanda dan Tanpa Tanda (8-bit hingga 64-bit), Int128
  • Titik Mengambang & Numerik: Float32, Float64, Teks Desimal
  • Tipe Dasar: String Biner, Irisan Byte, Boolean, Peringkat Enum
  • Tanggal & Waktu: Tanggal, Waktu, Waktu Berzona, Stempel Waktu, Durasi, Interval Kalender
  • Jaringan & Pengidentifikasi: UUID, MAC, IP, Prefiks IP, Prefiks Jaringan Kanonis, LSN
  • Struktur Komposit: Tuple Bersarang, Rentang, dan enkoding struktural mentah
  • Kolasi: Key Kolasi Unicode dan token kanonis eksternal

Pemetaan tipe SQL selaras dengan aturan pengurutan B-tree PostgreSQL 18. Tipe yang bergantung pada katalog basis data atau keadaan mesin internal ditangani dengan meneruskan token kanonis eksternal.

Kolasi String

Builder.String secara default menggunakan urutan biner UTF-8 mentah. Untuk pengurutan yang sadar lokal (locale-aware), Schottky menyediakan Collator yang aman secara konkuren dan tidak dapat diubah (immutable):

  • Kolasi Deterministik: Mengenkode key kolasi beserta byte UTF-8 mentah untuk menyediakan pemecah seri (tie-breaker) ketika bobot kolasi identik.
  • Kolasi Nondeterministik: Memperlakukan string yang setara secara kolasi sebagai identik, dengan menghilangkan pemecah seri byte mentah.

Versi Unicode dan profil harus dilacak dalam skema metadata. Jika penyedia kolasi atau pengaturan profil berubah, key yang sudah ada harus dibangun ulang.

Manajemen Skema

Karena key Schottky adalah urutan byte mentah tanpa tajuk, lapisan skema harus melacak:

  1. Urutan bidang dan tipe data.
  2. Arah pengurutan (ASC/DESC) dan pengurutan NULL (NULLS FIRST/LAST).
  3. Kolasi string dan aturan normalisasi.
  4. Versi profil Schottky dan Kolasi.

Membandingkan key yang dihasilkan dengan skema yang berbeda atau mendekode terhadap skema yang tidak cocok akan merusak jaminan pengurutan.

Performa dan Tautan

Pada Go 1.27+, akselerasi SIMD portabel eksperimental dapat diaktifkan menggunakan GOEXPERIMENT=simd. Jalur skalar dan SIMD menghasilkan key yang identik secara byte.