GoSuda

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

By Lemon Mint
views ...

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

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

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

1go get gosuda.org/schottky@latest

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

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

  • Цяли числа: Стандартното допълнение до две за кодиране с най-старши байт нарушава естествената последователност поради най-значимия знак бит. Инвертирането на знаковия бит е необходимо за правилни неименувани байтови сравнения.
  • Числа с плаваща запетая: Изисква корекции на знаковия бит, инвертиран ред за отрицателни стойности и последователна обработка на 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        // Инициализираме хранилището и създателя
11        storage := make([]byte, 0, 128)
12        builder := schottky.NewBuilder(storage)
13
14        builder.Int64(42, schottky.AscNullsLast)
15        accountPrefixLen := builder.Len()
16
17        builder.String("Ada", schottky.DescNullsFirst)
18        key, err := builder.Key()
19
20        if err != nil {
21                panic(err)
22        }
23        accountPrefix := key[:accountPrefixLen]
24        fmt.Printf("key=%x\nprefix=%x\n", key, accountPrefix)
25}

Schottky предоставя четири изрични конфигурации за ред на сортиране:

  • AscNullsFirst
  • AscNullsLast
  • DescNullsFirst
  • DescNullsLast

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

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

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

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

За да изчислите ексклузивната горна граница за полуотворени [prefix, upper) сканирания на диапазон, използвайте PrefixUpperBound:

 1// Изчисляваме горната граница за префикса
 2upperStorage := make([]byte, 0, len(accountPrefix))
 3upper, finite, err := schottky.PrefixUpperBound(upperStorage, accountPrefix)
 4
 5if err != nil {
 6        panic(err)
 7}
 8
 9if finite {
10        // Полуотворено [accountPrefix, upper) сканиране на диапазон
11} else {
12        // Неограничено отворено сканиране на диапазон
13}

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

Нулево заделяне на памет и управление на буфери

Генерирането на ключове често работи по критични пътища на базата данни. За да се елиминират заделянията на памет в купата и надхитряването с преоразмеряване на буфери, 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 предоставя безопасна за нишки (concurrent-safe), неизменяема Collator:

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

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

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

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

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

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

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

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