GoSuda

Schottky: Zero-Allocation, Order-Preserving Byte-Key Encoding за Go

By Lemon Mint views ...

Когато се реализират key-value хранилища и индекси на бази данни, базирани на LSM-дърво или B-дърво, съставните полета често трябва да бъдат комбинирани в един байтов ключ.

Стандартните формати за сериализация, като JSON или Protocol Buffers, не са проектирани за тази цел, тъй като техните сериализирани байтови изходи не запазват естествения ред на сортиране, изискван от непознатото побайтово сравнение (bytes.Compare или memcmp).

Schottky е Go библиотека, проектирана за кодиране на композитни кортежи от множество типове в байтови ключове със запазен ред.

1go get gosuda.org/schottky@latest

Сериализация срещу ключове за сортиране

Гарантирането на коректно побайтово сортиране изисква отчитане на няколко дребнозърнести детайла за представяне на данните:

  • Цели числа: Стандартното кодиране в big-endian по допълнение до две нарушава естествения ред поради най-значимия знаков бит. Инвертирането на знаковия бит е необходимо за коректни непознати побайтови сравнения.
  • Числа с плаваща запетая: Изисква корекции на знаковия бит, обратен ред за отрицателни стойности и последователна обработка на NaN и -0.
  • Низове и байтови масиви с променлива дължина: Границите между полетата трябва да се запазват, без да се нарушават префиксните редове на сортиране.
  • Изисквания към композитните ключове: Поддръжка на независим ред ASC/DESC за всяко поле, отделени правила NULLS FIRST/LAST, строга лексикографска предимство (предходните полета определят реда) и съвместимост с префиксно сканиране.

Schottky преобразува всяка стойност в каноничен полезен товар преди прилагането на таговете за наличие и посоката на сортиране. За DESC полета всеки байт от ASC полезния товар се инвертира битово (^b). Разположението на NULL се обработва чрез специални тагове за наличие и действа независимо от посоката на сортиране.

Основна употреба

Следният пример изгражда композитен ключ, състоящ се от идентификатор на акаунт (ASC, NULLS LAST) и име (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 предоставя четири изрично определени конфигурации на реда на сортиране:

  • AscNullsFirst
  • AscNullsLast
  • DescNullsFirst
  • DescNullsLast

Позицията на NULL никога не се извежда неявно. Ако бъде подадена невалидна стойност на Order, билдърът записва ErrInvalidOrder, която се връща при извикване на Key() или Err().

Префиксно сканиране и граници на диапазони

Композитните ключове на Schottky не съдържат глобални заглавни части, метаданни за брой полета, типови тагове или опашки. При условие че схемата е известна предварително, кодираните полета просто се конкатенират.

Поради това оформление кодираните байтове на водещите полета образуват валиден префикс за диапазонни сканирания. В горния пример accountPrefix може директно да се използва като префиксен филтър за сканиране на всички записи, за които Account ID == 42.

За изчисляване на изключващата горна граница при полуотворени диапазонни сканирания [prefix, upper) използвайте 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        // Полуотворено диапазонно сканиране [accountPrefix, upper)
10} else {
11        // Диапазонно сканиране без горна граница
12}

Забележка: Builder.Len() трябва да се измерва на коректни граници между полетата. Разрязването във вътрешния байтов поток на дадено поле създава невалиден префикс.

Нулева алокация и управление на буфери

Генерирането на ключове често се извършва по критични пътища в базата данни. За да се елиминират алокациите в heap и разходите за преоразмеряване на буфери, Builder работи строго в рамките на капацитета на подадения от извикващия слайс и не извършва вътрешно повторно разпределяне.

Ако буферът изчерпи капацитета си, се записва ErrShortBuffer без записване на частични байтове. Записите на полета са атомарни, а първата срещната грешка се запазва до проверка чрез Key() или Err(). Осигуряването на достатъчен капацитет предварително гарантира кодиране без алокации.

Размерите на буферите могат да се изчислят предварително с помощни функции като EncodedBytesSize, EncodedStringSize и EncodedDecimalSize, или чрез константи с фиксиран размер. Върнатият ключ директно препраща към подадения буфер, като управлението на жизнения цикъл на паметта се оставя на извикващия.

Decoder работи симетрично: той заема директно от входния ключ, изисква подадени от извикващия целеви буфери за полетата с променлива дължина и предоставя Remaining() == 0 за откриване на излишни байтове или несъответствия в схемата.

Поддържани типове данни

  • Цели числа: Знакови и беззнакови (от 8 до 64 бита), Int128
  • Числа с плаваща запетая и числови стойности: Float32, Float64, десетичен текст
  • Основни типове: Двоичен низ, байтов масив, булева стойност, ранг на изброяване
  • Дата и време: Дата, време, време със зона, времева марка, продължителност, календарен интервал
  • Мрежи и идентификатори: UUID, MAC, IP, IP префикс, каноничен мрежов префикс, LSN
  • Композитни структури: Вложени кортежи, диапазони и сурови структурни кодирания
  • Колация: Ключове за колация на Unicode и външни канонични токени

Съпоставянето на SQL типове е съобразено с правилата за сортиране на B-дървета в PostgreSQL 18. Типовете, зависещи от системните каталози на базата данни или от вътрешното състояние на енджина, се обработват чрез подаване на външни канонични токени.

Колация на низове

Builder.String по подразбиране използва сортиране по сурови двоични UTF-8 байтове. За сортиране, отчитащо локалните особености, Schottky предоставя Collator, който е безопасен при едновременен достъп и неизменяем:

  • Детерминистична колация: Кодира ключа за колация заедно със сурови UTF-8 байтове, за да осигури разрешаване на равенства при идентични тегла на колацията.
  • Недетерминистична колация: Третира низове, равни по колация, като идентични, като пропуска суровия байтов разрешител на равенства.

Версиите на Unicode и профилите трябва да се проследяват в метаданните на схемата. Ако доставчиците на колация или настройките на профила се променят, съществуващите ключове трябва да бъдат презаписани.

Управление на схемата

Тъй като ключовете на Schottky са сурови байтови последователности без заглавна част, слоят на схемата трябва да следи:

  1. Последователността на полетата и типовете данни.
  2. Посоките на сортиране (ASC/DESC) и реда на NULL (NULLS FIRST/LAST).
  3. Правилата за колация и нормализация на низове.
  4. Версиите на профилите на Schottky и колацията.

Сравняването на ключове, генерирани с различни схеми, или декодирането спрямо несъвпадаща схема нарушава гаранциите за ред.

Производителност и връзки

На Go 1.27+ експерименталното преносимо SIMD ускорение може да се активира чрез GOEXPERIMENT=simd. Скаларните и SIMD пътищата produce побайтово идентични ключове.