GoSuda

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

By Lemon Mint
views ...

При реализации хранилищ «ключ-значение» и индексов баз данных на основе LSM-деревьев или B-деревьев составные поля часто требуется объединять в единый байтовый ключ.

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

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

1go get gosuda.org/schottky@latest

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

Обеспечение корректной побайтовой сортировки требует учета нескольких низкоуровневых деталей представления данных:

  • Целые числа: Стандартное представление отрицательных чисел в дополнительном коде (two's complement 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() необходимо измерять на четких границах полей. Нарезка внутри внутреннего байтового потока поля создает недопустимый префикс.

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

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

Если емкость буфера исчерпывается, фиксируется ErrErrShortBuffer без записи частичных байтов. Запись полей является атомарной, и первая обнаруженная ошибка сохраняется до проверки через Key() или Err(). Предоставление достаточной емкости заранее обеспечивает кодирование без выделения памяти.

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

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

Поддерживаемые типы данных

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

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

Строковое сопоставление (Collation)

Builder.String по умолчанию использует исходный двоичный порядок UTF-8. Для сортировки с учетом локали Schottky предоставляет потокобезопасный, неизменяемый Collator:

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

Версии Unicode и профилей должны отслеживаться в схеме метаданных. При изменении провайдеров сопоставления или настроек профиля существующие ключи должны быть перестроены.

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

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

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

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

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

В Go 1.27+ экспериментальное переносимое SIMD-ускорение можно включить с помощью GOEXPERIMENT=simd. Скалярные и SIMD пути генерируют побитово идентичные ключи.