GoSuda

Schottky: Go를 위한 할당 없음(Zero-Allocation), 순서 보존(Order-Preserving) 바이트 키 인코딩

By Lemon Mint views ...

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는 존재 태그(presence tag)와 방향 조정을 적용하기 전에 각 값을 정규 페이로드로 변환합니다. 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) 범위 스캔을 위한 排他적 상한(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()은 명확한 필드 경계에서 측정되어야 합니다. 필드의 내부 바이트 스트림 내부에서 슬라이싱하면 유효하지 않은 접두사가 생성됩니다.

제로 할당 및 버퍼 관리

키 생성은 빈번히 중요한 데이터베이스 경로에서 실행됩니다. 힙 할당과 버퍼 재크기 조정 오버헤드를 제거하기 위해, Builder는 호출자가 제공한 슬라이스의 용량 내에서만 엄격하게 동작하며 내부적으로 재할당하지 않습니다.

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

버퍼 크기는 EncodedBytesSize, EncodedStringSize, EncodedDecimalSize와 같은 헬퍼 함수나 고정 크기 상수를 통해 미리 계산할 수 있습니다. 반환된 키는 제공된 버퍼를 직접 참조하며, 메모리 수명 관리는 호출자에게 맡겨집니다.

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

지원 데이터 타입

  • 정수: 부호 있음 및 부호 없음(8비트부터 64비트까지), Int128
  • 부동소수점 및 수치: Float32, Float64, 십진수 텍스트
  • 기본 타입: 이진 문자열, 바이트 슬라이스, 불리언, 열거형 순위(Enum Rank)
  • 날짜 및 시간: Date, Time, Zoned Time, Timestamp, Duration, Calendar Interval
  • 네트워크 및 식별자: UUID, MAC, IP, IP Prefix, Canonical Network Prefix, LSN
  • 복합 구조: 중첩 튜플, 범위(Ranges), 그리고 원시 구조적 인코딩
  • 콜레이션: Unicode Collation Keys 및 외부 정규 토큰(external canonical tokens)

SQL 타입 매핑은 PostgreSQL 18 B-트리 정렬 규칙에 맞춰져 있습니다. 데이터베이스 카탈로그 또는 내부 엔진 상태에 의존하는 타입은 외부 정규 토큰을 전달하여 처리합니다.

문자열 콜레이션

Builder.String은 기본적으로 원시 UTF-8 바이너리 순서를 사용합니다. 로케일을 인식하는 정렬을 위해, Schottky는 동시성에 안전하고 불변인 Collator를 제공합니다.

  • 결정적 콜레이션(Deterministic Collation): 콜레이션 키를 원시 UTF-8 바이트와 함께 인코딩하여, 콜레이션 가중치가 동일한 경우 동점 결정자(tie-breaker)를 제공합니다.
  • 비결정적 콜레이션(Nondeterministic Collation): 콜레이션상 동일한 문자열을 동일하게 취급하며, 원시 바이트 동점 결정자를 생략합니다.

Unicode 및 프로필 버전은 메타데이터 스키마에서 추적되어야 합니다. 콜레이션 제공자 또는 프로필 설정이 변경되면, 기존 키를 반드시 재생성해야 합니다.

스키마 관리

Schottky 키는 원시적인 헤더 없는 바이트 시퀀스이므로, 스키마 계층은 다음 항목을 추적해야 합니다.

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

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

성능 및 링크

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