Schottky：面向 Go 的零分配、保序字节键编码

在实现基于 LSM 树或 B 树的键值存储和数据库索引时，复合字段通常需要被组合为单个字节键。

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 的位置通过专用的存在标记处理，且与排序方向无关。

基本用法

以下示例构建一个复合键，包含账户 ID（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、十进制文本
基本类型：二进制字符串、字节切片、布尔值、枚举序号
日期与时间：Date、Time、Zoned Time、Timestamp、Duration、Calendar Interval
网络与标识符：UUID、MAC、IP、IP Prefix、Canonical Network Prefix、LSN
复合结构：嵌套元组、Ranges 以及原始结构编码
排序规则：Unicode Collation Keys 与外部规范令牌

SQL 类型映射与 PostgreSQL 18 的 B 树排序规则保持一致。依赖数据库目录或内部引擎状态的类型，通过传入外部规范令牌进行处理。

字符串排序规则

Builder.String 默认采用原始 UTF-8 二进制顺序。对于具备区域感知的排序，Schottky 提供了一个并发安全、不可变的 Collator：

确定性排序规则：对排序键与原始 UTF-8 字节一并编码，以便在排序权重相同时提供决胜依据。
非确定性排序规则：将排序规则下相等的字符串视为相同，省略原始字节决胜依据。

Unicode 与配置文件版本应记录在元数据模式中。若排序规则提供者或配置文件设置发生变化，现有键必须重新构建。

模式管理

由于 Schottky 键是原始的、无头部的字节序列，模式层必须跟踪以下内容：

字段顺序与数据类型。
排序方向（ASC/DESC）与 NULL 排序（NULLS FIRST/LAST）。
字符串排序规则与规范化规则。
Schottky 与排序规则的配置文件版本。

比较由不同模式生成的键，或使用不匹配的模式进行解码，都会破坏排序保证。

性能与链接

在 Go 1.27 及以上版本中，可以使用 GOEXPERIMENT=simd 启用实验性的可移植 SIMD 加速。标量路径与 SIMD 路径生成的键字节完全一致。

GitHub 仓库：https://github.com/gosuda/schottky
键布局规范：https://github.com/gosuda/schottky/blob/main/docs/03-key-layout.md
SQL 类型映射指南：https://github.com/gosuda/schottky/blob/main/docs/17-sql-type-map.md
Go API 参考：https://github.com/gosuda/schottky/blob/main/docs/18-api.md