GoSuda

Schottky: Go için Zero-Allocation, Order-Preserving Byte-Key Encoding

By Lemon Mint views ...

LSM-ağacı veya B-ağacı tabanlı anahtar-değer depolarını ve veritabanı indekslerini uygularken, bileşik alanların genellikle tek bir bayt anahtarında birleştirilmesi gerekir.

JSON veya Protocol Buffers gibi standart serileştirme biçimleri bu amaç için tasarlanmamıştır, çünkü serileştirilmiş bayt çıktıları, işsiz bayt bazlı karşılaştırmaların (bytes.Compare veya memcmp) gerektirdiği doğal sıralama düzenini korumaz.

Schottky, çok türlü bileşik demetleri sıra koruyan bayt anahtarlarına kodlamak için tasarlanmış bir Go kütüphanesidir.

1go get gosuda.org/schottky@latest

Serileştirme ve Sıralama Anahtarları

Doğru bayt bazlı sıralamayı garanti etmek, birkaç düşük seviyeli veri temsili ayrıntısının ele alınmasını gerektirir:

  • Tam sayılar: Standart iki tümleyen büyük-endian kodlaması, en anlamlı işaret biti nedeniyle doğal sıralamayı bozar. Doğru işaretsiz bayt karşılaştırmaları için işaret bitinin tersine çevrilmesi gereklidir.
  • Kayan noktalı sayılar: İşaret biti ayarlamaları, negatif değerler için ters çevrilmiş sıralama ve NaN ile -0 değerlerinin tutarlı biçimde ele alınmasını gerektirir.
  • Değişken uzunluklu dizeler ve bayt dilimleri: Alan sınırları, önek sıralama düzenleri bozulmadan korunmalıdır.
  • Bileşik anahtar gereksinimleri: Alan başına bağımsız ARTAN/AZALAN sıralama desteği, birbirinden ayrı NULLS FIRST/LAST kuralları, katı sözlükbilimsel öncelik (önceki alanlar sıralamayı belirler) ve önek taramasıyla uyumluluk.

Schottky, her değeri, mevcudiyet etiketleri ve yönelim uygulanmadan önce kanonik bir yüke dönüştürür. AZALAN alanlar için ARTAN yükün her baytı bitsel olarak tersine çevrilir (^b). NULL yerleşimi, ayrılmış mevcudiyet etiketleri aracılığıyla yönetilir ve sıralama yönünden bağımsız çalışır.

Temel Kullanım

Aşağıdaki örnek, bir Hesap Kimliği (ASC, NULLS LAST) ve bir Ad (DESC, NULLS FIRST) alanından oluşan bileşik bir anahtar oluşturur:

 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 dört açık sıralama yapılandırması sunar:

  • AscNullsFirst
  • AscNullsLast
  • DescNullsFirst
  • DescNullsLast

NULL konumlandırması asla örtük olarak çıkarılmaz. Geçersiz bir Order değeri iletilirse, oluşturucu ErrInvalidOrder hatasını kaydeder ve bu hata Key() veya Err() çağrıldığında döndürülür.

Önek Taraması ve Aralık Sınırları

Schottky bileşik anahtarları, genel başlıklar, alan sayısı meta verileri, tür etiketleri veya sonlandırıcılar içermez. Şemanın önceden bilindiği varsayıldığında, alan kodlamaları basitçe birleştirilir.

Bu düzen nedeniyle, önde gelen alanların kodlanmış baytları, aralık taramaları için geçerli bir önek oluşturur. Yukarıdaki örnekte, accountPrefix, Hesap Kimliği == 42 olan tüm kayıtları taramak için doğrudan bir önek filtresi olarak kullanılabilir.

Yarı açık [prefix, upper) aralık taramaları için özel üst sınırı hesaplamak amacıyla PrefixUpperBound kullanılır:

 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        // Yarı açık [accountPrefix, upper) aralık taraması
10} else {
11        // Sınırsız açık aralık taraması
12}

Not: Builder.Len() değeri, temiz alan sınırlarında ölçülmelidir. Bir alanın iç bayt akışının içinden dilimleme yapmak geçersiz bir önek üretir.

Sıfır Ayırma ve Arabellek Yönetimi

Anahtar üretimi sıklıkla kritik veritabanı yollarında çalışır. Heap ayırmalarını ve arabellek yeniden boyutlandırma yükünü ortadan kaldırmak için Builder, yalnızca çağıran tarafından sağlanan dilimin kapasitesi dahilinde çalışır ve dahili olarak yeniden ayırma yapmaz.

Arabelleğin kapasitesi tükenirse, kısmi bayt yazılmadan ErrShortBuffer kaydedilir. Alan yazmaları atomiktir ve karşılaşılan ilk hata, Key() veya Err() ile kontrol edilene kadar korunur. Önceden yeterli kapasite sağlamak, sıfır ayırmalı kodlamayı garanti eder.

Arabellek boyutları, EncodedBytesSize, EncodedStringSize ve EncodedDecimalSize gibi yardımcı işlevler veya sabit boyutlu sabitler aracılığıyla önceden hesaplanabilir. Döndürülen anahtar, sağlanan arabelleğe doğrudan başvurur ve bellek yaşam döngüsü yönetimini çağırana bırakır.

Decoder simetrik olarak çalışır: girdi anahtarından doğrudan ödünç alır, değişken uzunluklu alanlar için çağıran tarafından sağlanan hedef arabellekler gerektirir ve sondaki baytları veya şema uyumsuzluklarını tespit etmek için Remaining() == 0 sağlar.

Desteklenen Veri Türleri

  • Tam sayılar: İşaretli ve işaretsiz (8 bitten 64 bite), Int128
  • Kayan noktalı ve sayısal türler: Float32, Float64, Ondalık Metin
  • Temel türler: İkili Dize, Bayt Dilimi, Boolean, Enum Sırası
  • Tarih ve saat: Tarih, Saat, Bölgeli Saat, Zaman Damgası, Süre, Takvim Aralığı
  • Ağ ve tanımlayıcılar: UUID, MAC, IP, IP Öneki, Kanonik Ağ Öneki, LSN
  • Bileşik yapılar: İç içe Demetler, Aralıklar ve ham yapısal kodlamalar
  • Harmanlama: Unicode Harmanlama Anahtarları ve harici kanonik belirteçler

SQL türü eşlemesi, PostgreSQL 18 B-ağacı sıralama kurallarıyla uyumludur. Veritabanı kataloglarına veya dahili motor durumuna bağlı türler, harici kanonik belirteçler iletilerek ele alınır.

Dize Harmanlama

Builder.String, varsayılan olarak ham UTF-8 ikili düzenini kullanır. Yerel ayara duyarlı sıralama için Schottky, eşzamanlılık açısından güvenli, değiştirilemez bir Collator sunar:

  • Belirleyici Harmanlama: Harmanlama ağırlıkları aynı olduğunda bir eşitlik bozucu olarak ham UTF-8 baytlarıyla birlikte harmanlama anahtarını kodlar.
  • Belirleyici Olmayan Harmanlama: Harmanlama açısından eşit dizeleri özdeş kabul eder ve ham bayt eşitlik bozucuyu atlar.

Unicode ve profil sürümleri şema meta verilerinde izlenmelidir. Harmanlama sağlayıcıları veya profil ayarları değişirse, mevcut anahtarların yeniden oluşturulması gerekir.

Şema Yönetimi

Schottky anahtarları ham, başlıksız bayt dizileri olduğundan, şema katmanı şunları izlemelidir:

  1. Alan sırası ve veri türleri.
  2. Sıralama yönleri (ASC/DESC) ve NULL sıralaması (NULLS FIRST/LAST).
  3. Dize harmanlama ve normalleştirme kuralları.
  4. Schottky ve Harmanlama profil sürümleri.

Farklı şemalarla üretilmiş anahtarları karşılaştırmak veya uyumsuz bir şemaya karşı çözümlemek, sıralama garantilerini bozar.

Performans ve Bağlantılar

Go 1.27 ve üzeri sürümlerde, deneysel taşınabilir SIMD hızlandırması GOEXPERIMENT=simd kullanılarak etkinleştirilebilir. Skaler ve SIMD yolları bayt bazında özdeş anahtarlar üretir.