Schottky: Go言語のためのゼロアロケーション、順序保持バイトキーエンコーディング
LSMツリーまたはBツリーベースのキーバリューストアおよびデータベースインデックスを実装する際、複合フィールドを単一のバイトキーに結合しなければならないことがよくあります。
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
- 複合構造: ネストされたタプル、範囲、および生の構造的エンコーディング
- 照合（Collation）: Unicode照合キーおよび外部正規トークン
SQL型のマッピングは、PostgreSQL 18のBツリーソート規則に準拠しています。データベースカタログまたは内部エンジン状態に依存する型は、外部正規トークンを渡すことによって処理されます。
文字列照合
Builder.Stringのデフォルトは、生のUTF-8バイナリ順序です。ロケールを意識したソートのために、Schottkyは並行安全で不変なCollatorを提供します：
- 決定的照合: 照合の重みが同一である場合のタイブレーカーを提供するために、生のUTF-8バイトとともに照合キーをエンコードします。
- 非決定的照合: 照合結果が等しい文字列を同一として扱い、生のバイトのタイブレーカーを省略します。
Unicodeおよびプロファイルのバージョンは、メタデータスキーマで追跡される必要があります。照合プロバイダーまたはプロファイル設定が変更された場合、既存のキーを再構築する必要があります。
スキーマ管理
Schottkyキーは生のヘッダーなしのバイトシーケンスであるため、スキーマレイヤーは以下を追跡する必要があります：
- フィールドの順序とデータ型。
- ソート方向（
ASC/DESC）およびNULLの順序付け（NULLS FIRST/LAST）。 - 文字列の照合および正規化規則。
- Schottkyおよび照合プロファイルのバージョン。
異なるスキーマで生成されたキーを比較したり、一致しないスキーマに対してデコードしたりすると、順序の保証が損なわれます。
パフォーマンスとリンク
Go 1.27以降では、実験的なポータブルSIMDアクセラレーションをGOEXPERIMENT=simdを使用して有効にできます。スカラーパスとSIMDパスは、バイト単位で同一のキーを生成します。