GoSuda

Schottky: кодирование байтовых ключей для 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 работает строго в пределах ёмкости переданного вызывающей стороной среза и не выполняет внутреннего перевыделения.

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

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

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

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

  • Целые числа: знаковые и беззнаковые (от 8 до 64 бит), Int128
  • Числа с плавающей точкой и числовые типы: Float32, Float64, десятичный текст
  • Базовые типы: бинарная строка, байтовый срез, логический тип, ранг перечисления (Enum Rank)
  • Дата и время: Date, Time, Zoned Time, Timestamp, Duration, Calendar Interval
  • Сетевые типы и идентификаторы: UUID, MAC, IP, IP Prefix, Canonical Network Prefix, LSN
  • Составные структуры: вложенные кортежи, диапазоны (Ranges) и необработанные структурные кодировки
  • Collation: Unicode Collation Keys и внешние канонические токены

Сопоставление типов 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-пути производят побайтово идентичные ключи.