GoSudaSchottky: Go向けのゼロアロケーション・順序保存型バイトキーエンコーディング
LSM-tree や B-tree ベースのキーバリューストアおよびデータベースインデックスを実装する際には、複合フィールドを単一のバイトキーに結合する必要が生じることが多い。
JSON や Protocol Buffers などの標準的なシリアライズ形式は、この目的のために設計されていない。これらのシリアライズ後のバイト出力は、符号なしバイト単位の比較(bytes.Compare や memcmp)が要求する自然な順序を保持しないためである。
Schottky は、複数の型からなる複合タプルを順序保存型のバイトキーにエンコードするために設計された Go ライブラリである。
1go get gosuda.org/schottky@latest
シリアライズとソートキーの比較
正しいバイト単位のソートを保証するためには、いくつかの低レベルのデータ表現の詳細に対処する必要がある。
- 整数: 標準的な 2 の補数のビッグエンディアン表現は、最上位の符号ビットにより自然な順序を損なう。正しい符号なしバイト比較のためには、符号ビットを反転させることが必要である。
- 浮動小数点数: 符号ビットの調整、負の値に対する逆順序付け、および
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 は、4 つの明示的なソート順序の設定を提供する。
AscNullsFirstAscNullsLastDescNullsFirstDescNullsLast
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、10 進テキスト - 基本型: バイナリ文字列、バイトスライス、ブール値、列挙型ランク
- 日付および時刻: 日付、時刻、タイムゾーン付き時刻、タイムスタンプ、期間、暦間隔
- ネットワークおよび識別子: UUID、MAC、IP、IP プレフィックス、正規ネットワークプレフィックス、LSN
- 複合構造: ネストされたタプル、範囲、および生の構造的エンコーディング
- 照合順序: Unicode 照合キーおよび外部の正規トークン
SQL 型のマッピングは、PostgreSQL 18 の B-tree ソート規則に準拠している。データベースカタログやエンジンの内部状態に依存する型は、外部の正規トークンを渡すことで処理される。
文字列の照合
Builder.String は、デフォルトで生の UTF-8 バイナリ順序を用いる。ロケールを考慮したソートのために、Schottky は並行安全で不変の Collator を提供する。
- 決定的照合: 照合重みが同一である場合のタイブレーカーとして、照合キーとともに生の UTF-8 バイト列をエンコードする。
- 非決定的照合: 照合上等価な文字列を同一のものとして扱い、生のバイト列によるタイブレーカーを省略する。
Unicode およびプロファイルのバージョンは、メタデータスキーマにおいて追跡されるべきである。照合プロバイダーまたはプロファイル設定が変更された場合、既存のキーは再構築しなければならない。
スキーマ管理
Schottky のキーは生のヘッダーなしバイト列であるため、スキーマ層は以下を追跡しなければならない。
- フィールドの順序およびデータ型。
- ソート方向(
ASC/DESC)および NULL の順序(NULLS FIRST/LAST)。 - 文字列の照合および正規化規則。
- Schottky および照合プロファイルのバージョン。
異なるスキーマで生成されたキーを比較する場合、または不一致のスキーマに対してデコードを行う場合、順序の保証は失われる。
パフォーマンスおよびリンク
Go 1.27 以降では、GOEXPERIMENT=simd を用いて、実験的なポータブル SIMD 高速化を有効にできる。スカラーパスと SIMD パスは、バイト単位で同一のキーを生成する。