GoSuda

Schottky：Go语言的零分配、保序字节键编码

By Lemon Mint
views ...

当实现基于 LSM-tree 或 B-tree 的键值存储与数据库索引时，复合字段通常需要组合成单个字节键。

诸如 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 复合键不包含全局标头、字段计数元数据、类型标记或尾部。假设模式（schema）已提前知晓，字段编码只需简单拼接即可。

由于这种布局，前导字段的编码字节构成了范围扫描的有效前缀。在上面的示例中，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、十进制文本
  • 基本类型：二进制字符串、字节切片、布尔值、枚举排位
  • 日期与时间：日期、时间、带时区时间、时间戳、时间段、日历间隔
  • 网络与标识符：UUID、MAC、IP、IP 前缀、规范网络前缀、LSN
  • 复合结构：嵌套元组、范围以及原始结构编码
  • 排序规则：Unicode 排序规则键和外部规范令牌

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

字符串排序规则

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

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

Unicode 和配置版本应在元数据模式中进行跟踪。如果排序规则提供程序或配置设置发生更改，则必须重新构建现有键。

模式管理

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

  1. 字段序列和数据类型。
  2. 排序方向（ASC/DESC）与 NULL 排序（NULLS FIRST/LAST）。
  3. 字符串排序和规范化规则。
  4. 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