GoSuda

Schottky: Go를 위한 Zero-Allocation, Order-Preserving Byte-Key Encoding

By Lemon Mint
views ...

LSM-tree 또는 B-tree 기반 key-value 스토어 및 데이터베이스 인덱스를 구현할 때, 복합 필드(composite field)는 종종 단일 byte key로 결합되어야 합니다.

JSON 또는 Protocol Buffers와 같은 표준 serialization 형식은 직렬화된 바이트 출력 결과가 부호 없는 바이트 단위 비교(bytes.Compare 또는 memcmp)에 필요한 자연스러운 정렬 순서를 보존하지 않기 때문에 이 목적에 적합하지 않습니다.

Schottky는 다중 타입 복합 튜플을 순서 보존 byte key로 인코딩하도록 설계된 Go 라이브러리입니다.

1go get gosuda.org/schottky@latest

Serialization 대 Sort Keys

올바른 바이트 단위 정렬을 보장하려면 다음과 같은 여러 저수준 데이터 표현 세부 사항을 처리해야 합니다:

  • Integers: 표준 2의 보수 빅엔디안 인코딩은 최상위 부호 비트로 인해 자연스러운 순서가 깨집니다. 올바른 부호 없는 바이트 비교를 위해서는 부호 비트를 반전시키는 것이 필수적입니다.
  • Floating-point numbers: 부호 비트 조정, 음수 값에 대한 반전된 정렬, 그리고 NaN 및 -0의 일관된 처리가 필요합니다.
  • Variable-length strings and byte slices: 접두사(prefix) 정렬 순서를 깨지 않으면서 필드 경계가 보존되어야 합니다.
  • Composite key requirements: 필드별 독립적인 ASC/DESC 정렬 지원, 분리된 NULLS FIRST/LAST 규칙, 엄격한 사전식 우선순위(앞의 필드가 순서를 결정함), 그리고 접두사 스캔과의 호환성.

Schottky는 존재 여부 태그와 방향성을 적용하기 전에 각 값을 정규 페이로드(canonical payload)로 변환합니다. DESC 필드의 경우, ASC 페이로드의 각 바이트는 비트 단위로 반전됩니다(^b). NULL 배치는 전용 존재 여부 태그를 통해 처리되며 정렬 방향과 독립적으로 작동합니다.

Basic Usage

다음 예제는 Account ID(ASC, NULLS LAST)와 Name(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 값이 전달되면, builder는 ErrInvalidOrder를 기록하며, 이는 Key() 또는 Err()를 호출할 때 반환됩니다.

Prefix Scanning and Range Bounds

Schottky 복합 키에는 전역 헤더, 필드 개수 메타데이터, 타입 태그 또는 트레일러가 포함되지 않습니다. 스키마가 사전에 알려져 있다고 가정할 때, 필드 인코딩은 단순히 연결됩니다.

이러한 레이아웃 덕분에 선행 필드의 인코딩된 바이트는 범위 스캔을 위한 유효한 접두사를 형성합니다. 위의 예제에서 accountPrefix는 Account ID == 42인 모든 레코드를 스캔하기 위한 접두사 필터로 직접 사용될 수 있습니다.

반개구간 [prefix, upper) 범위 스캔을 위한 배타적 상한(exclusive upper bound)을 계산하려면 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()은 깨끗한 필드 경계에서 측정되어야 합니다. 필드 내부의 바이트 스트림을 조각내면(slicing) 유효하지 않은 접두사가 생성됩니다.

Zero-Allocation and Buffer Management

키 생성은 빈번하게 데이터베이스의 임계 경로(critical path)에서 실행됩니다. 힙 할당과 버퍼 리사이징 오버헤드를 제거하기 위해, Builder는 호출자가 제공한 슬라이스의 용량 내에서만 엄격하게 작동하며 내부적으로 재할당을 수행하지 않습니다.

버퍼의 용량이 부족해지면, 부분적인 바이트를 쓰지 않고 ErrShortBuffer가 기록됩니다. 필드 쓰기는 원자적(atomic)이며, 발생한 첫 번째 오류는 Key() 또는 Err()를 통해 확인할 때까지 보존됩니다. 사전에 충분한 용량을 제공하면 제로 할당 인코딩이 보장됩니다.

버퍼 크기는 EncodedBytesSize, EncodedStringSize, EncodedDecimalSize와 같은 헬퍼 함수나 고정 크기 상수를 사용하여 사전에 계산할 수 있습니다. 반환된 키는 제공된 버퍼를 직접 참조하므로, 메모리 수명 주파 관리(lifecycle management)는 호출자에게 위임됩니다.

Decoder는 대칭적으로 작동합니다. 입력 키를 직접 차용(borrow)하고, 가변 길이 필드에 대해 호출자가 제공한 대상 버퍼가 필요하며, Remaining() == 0을 제공하여 후행 바이트나 스키마 불일치를 감지합니다.

Supported Data Types

  • Integers: 부호 있는 정수 및 부호 없는 정수(8비트~64비트), Int128
  • Floating-Point & Numerics: Float32, Float64, 십진수 텍스트(Decimal Text)
  • Basic Types: 바이너리 문자열, 바이트 슬라이스, 불리언, 열거형 순위(Enum Rank)
  • Date & Time: 날짜, 시간, 시간대가 있는 시간, 타임스탬프, 기간(Duration), 캘린더 간격
  • Network & Identifiers: UUID, MAC, IP, IP 접두사, 정규 네트워크 접두사, LSN
  • Composite Structures: 중첩 튜플, 범위, 원시 구조적 인코딩
  • Collation: 유니코드 정렬 키 및 외부 정규 토큰

SQL 타입 매핑은 PostgreSQL 18 B-tree 정렬 규칙과 정렬됩니다. 데이터베이스 카탈로그나 내부 엔진 상태에 종속되는 타입은 외부 정규 토큰을 전달하여 처리됩니다.

String Collation

Builder.String은 기본적으로 원시 UTF-8 바이너리 순서로 설정됩니다. 로캘 인식 정렬을 위해 Schottky는 동시성 안전(concurrent-safe)하고 불변인(immutable) Collator를 제공합니다:

  • Deterministic Collation: 정렬 가중치가 동일할 때 동점(tie)을 해결하기 위해 원시 UTF-8 바이트와 함께 정렬 키를 인코딩합니다.
  • Nondeterministic Collation: 정렬 결과가 같은 문자열을 동일한 것으로 취급하며, 원시 바이트 동점 해결자를 생략합니다.

유니코드 및 프로필 버전은 메타데이터 스키마에서 추적되어야 합니다. 정렬 공급자나 프로필 설정이 변경되는 경우, 기존 키는 다시 빌드되어야 합니다.

Schema Management

Schottky 키는 원시 헤더리스 바이트 시퀀스이므로, 스키마 레이어는 다음을 추적해야 합니다:

  1. 필드 시퀀스 및 데이터 타입.
  2. 정렬 방향(ASC/DESC) 및 NULL 정렬(NULLS FIRST/LAST).
  3. 문자열 정렬 및 정규화 규칙.
  4. Schottky 및 Collation 프로필 버전.

서로 다른 스키마로 생성된 키를 비교하거나 일치하지 않는 스키마로 디코딩하면 정렬 보장이 깨집니다.

Performance and Links

Go 1.27 이상에서는 GOEXPERIMENT=simd를 사용하여 실험적인 휴대용 SIMD 가속을 활성화할 수 있습니다. 스칼라 경로와 SIMD 경로는 바이트가 동일한 키를 생성합니다.