GoSuda

Schottky: Go için Sıfır-Tahsisli, Sıralamayı Koruyan Bayt-Anahtar Kodlaması

By Lemon Mint
views ...

LSM ağacı veya B ağacı tabanlı anahtar-değer depoları ve veritabanı indeksleri uygulanırken, bileşik alanların genellikle tek bir bayt anahtarda 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şaretsiz bayt bazlı karşılaştırmaların (bytes.Compare veya memcmp) gerektirdiği doğal sıralama düzenini korumaz.

Schottky, çok tipli bileşik demetleri sıralamayı koruyan bayt anahtarlara 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 detayının ele alınmasını gerektirir:

  • Tamsayılar: Standart ikiye tümleyen büyük-uçlu kodlama, en anlamlı işaret bitinden ötürü doğal sıralamayı bozar. Doğru işaretsiz bayt karşılaştırmaları için işaret bitinin ters çevrilmesi gereklidir.
  • Kayan noktalı sayılar: İşaret biti ayarlamaları, negatif değerler için tersine çevrilmiş sıralama ve NaN ile -0 değerlerinin tutarlı bir şekilde işlenmesini gerektirir.
  • Değişken uzunluklu dizgiler ve bayt dilimleri: Önek sıralama düzenleri bozulmaksızın alan sınırları korunmalıdır.
  • Bileşik anahtar gereksinimleri: Alan başına bağımsız ART/AZAL (ASC/DESC) sıralama desteği, ayrıştırılmış ÖNCE BOŞ/SONRA BOŞ (NULLS FIRST/LAST) kuralları, katı sözlükbilimsel öncelik (daha önceki alanlar sırayı belirler) ve önek taramalarıyla uyumluluk.

Schottky, mevcudiyet etiketleri ve yönsel yönelimi uygulamadan önce her değeri kurallı bir yüke dönüştürür. AZAL (DESC) alanları için ART (ASC) yükünün her baytı bit düzeyinde ters çevrilir (^b). Boş (NULL) yerleşimi, özel mevcudiyet etiketleri aracılığıyla yönetilir ve sıralama yönünden bağımsız olarak çalışır.

Temel Kullanım

Aşağıdaki örnek, bir Hesap Kimliği (ASC, NULLS LAST) ve bir İsimden (DESC, NULLS FIRST) 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 düzeni yapılandırması sağlar:

  • AscNullsFirst
  • AscNullsLast
  • DescNullsFirst
  • DescNullsLast

Boş (NULL) konumlandırması asla örtük olarak çıkarılmaz. Geçersiz bir Order değeri geçirilirse, derleyici Key() veya Err() çağrılırken döndürülen ErrInvalidOrder değerini kaydeder.

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

Schottky bileşik anahtarları genel üstbilgiler, alan sayısı metadverileri, tip etiketleri veya kuyruklar içermez. Şemanın önceden bilindiği varsayılırsa, alan kodlamaları basitçe birleştirilir.

Bu yerleşim nedeniyle, önde gelen alanların kodlanmış baytları aralık taramaları için geçerli bir önek oluşturur. Yukarıdaki örnekte, accountPrefix, Account ID == 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 üzere PrefixUpperBound kullanın:

 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() temiz alan sınırlarında ölçülmelidir. Bir alanın dahili bayt akışı içinde dilimleme yapmak geçersiz bir önek üretir.

Sıfır Tahsisli ve Bellek Tamponu Yönetimi

Anahtar üretimi sıklıkla kritik veritabanı yollarında çalışır. Yığın tahsislerini ve bellek tamponu yeniden boyutlandırma yükünü ortadan kaldırmak için Builder katı bir şekilde çağrı yapan tarafından sağlanan dilimin kapasitesi dahilinde çalışır ve dahili olarak yeniden tahsis yapmaz.

Tampon kapasitesi tükenirse, kısmi baytlar yazılmadan ErrShortBuffer kaydedilir. Alan yazımları atomiktir ve karşılaşılan ilk hata, Key() veya Err() aracılığıyla kontrol edilene kadar korunur. Önceden yeterli kapasitenin sağlanması, sıfır tahsisli kodlama sağlar.

Tampon boyutları, EncodedBytesSize, EncodedStringSize ve EncodedDecimalSize gibi yardımcı fonksiyonlar aracılığıyla veya sabit boyutlu sabitler vasıtasıyla önceden hesaplanabilir. Döndürülen anahtar, sağlanan tampona doğrudan referans verir ve bellek yaşam döngüsü yönetimini çağrı yapan tarafa bırakır.

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

Desteklenen Veri Tipleri

  • Tamsayılar: İşaretli ve İşaretsiz (8 bitten 64 bite), Int128
  • Kayan Noktalı ve Sayısal Değerler: Float32, Float64, Ondalık Metin (Decimal Text)
  • Temel Tipler: İkili Dizgi (Binary String), Bayt Dilimi, Boole, Sıralama Derecesi (Enum Rank)
  • Tarih ve Zaman: Tarih, Zaman, Zaman Dilimli Zaman, Zaman Damgası, Süre, Takvim Aralığı
  • Ağ ve Tanımlayıcılar: UUID, MAC, IP, IP Öneki, Kurallı Ağ Öneki, LSN
  • Bileşik Yapılar: İç İçe Demetler, Aralıklar ve ham yapısal kodlamalar
  • Harmanlama (Collation): Unicode Harmanlama Anahtarları ve harici kurallı belirteçler

SQL tip eşlemesi, PostgreSQL 18 B ağacı sıralama kurallarıyla uyumludur. Veritabanı kataloglarına veya dahili motor durumuna bağımlı tipler, harici kurallı belirteçler geçilerek işlenir.

Dizgi Harmanlaması (String Collation)

Builder.String, varsayılan olarak ham UTF-8 ikili düzenine döner. Yerel ayara duyarlı sıralama için Schottky, eşzamanlılığa güvenli, değiştirilemez bir Collator sağlar:

  • Deterministik Harmanlama: Harmanlama ağırlıkları aynı olduğunda bir eşitliği bozucu (tie-breaker) sağlamak için harmanlama anahtarını ham UTF-8 baytlarının yanında kodlar.
  • Deterministik Olmayan Harmanlama: Ham bayt eşitlik bozucuyu atlayarak harmanlama açısından eşit dizgileri aynı olarak kabul eder.

Unicode ve profil sürümleri meta veri şemasında izlenmelidir. Harmanlama sağlayıcıları veya profil ayarları değişirse, mevcut anahtarlar yeniden oluşturulmalıdır.

Şema Yönetimi

Schottky anahtarları ham, üstbilgisiz bayt dizileri olduğundan, şema katmanı şunları izlemelidir:

  1. Alan dizisi ve veri tipleri.
  2. Sıralama yönleri (ASC/DESC) ve Boş sıralaması (NULLS FIRST/LAST).
  3. Dizgi harmanlama ve normalleştirme kuralları.
  4. Schottky ve Harmanlama profil sürümleri.

Farklı şemalarla üretilen anahtarları karşılaştırmak veya uyumsuz bir şemaya karşı kod çözmek sıralama garantilerini bozar.

Performans ve Bağlantılar

Go 1.27 ve üzer sürümlerde, deneysel taşınabilir SIMD hızlandırması GOEXPERIMENT=simd kullanılarak etkinleştirilebilir. Skaler ve SIMD yolları bayt cinsinden aynı anahtarları üretir.