GoSuda

Schottky: Zero-Allocation, Order-Preserving Byte-Key Encoding for Go

By Lemon Mint
views ...

Al implementar almacenes de clave-valor e índices de bases de datos basados en LSM-tree o B-tree, a menudo es necesario combinar campos compuestos en una sola clave de bytes.

Los formatos de serialización estándar como JSON o Protocol Buffers no están diseñados para este propósito porque sus salidas de bytes serializados no preservan el orden de clasificación natural requerido por las comparaciones de bytes sin signo (bytes.Compare o memcmp).

Schottky es una librería de Go diseñada para codificar tuplas compuestas de múltiples tipos en claves de bytes que preservan el orden.

1go get gosuda.org/schottky@latest

Serialization vs. Sort Keys

Garantizar una clasificación correcta a nivel de bytes requiere abordar varios detalles de representación de datos de bajo nivel:

  • Integers: La codificación estándar en complemento a dos en orden big-endian rompe el orden natural debido al bit de signo más significativo. Invertir el bit de signo es necesario para realizar comparaciones correctas de bytes sin signo.
  • Floating-point numbers: Requiere ajustes en el bit de signo, un orden invertido para los valores negativos y un manejo consistente de NaN y -0.
  • Variable-length strings and byte slices: Los límites de los campos deben preservarse sin romper los órdenes de clasificación por prefijo.
  • Composite key requirements: Soporte para un ordenamiento independiente ASC/DESC por campo, reglas desacopladas NULLS FIRST/LAST, precedencia lexicográfica estricta (los campos anteriores determinan el orden) y compatibilidad con el escaneo de prefijos.

Schottky convierte cada valor en una carga útil canónica antes de aplicar etiquetas de presencia y orientación direccional. Para los campos DESC, cada byte de la carga útil ASC se invierte a nivel de bits (^b). La colocación de NULL se gestiona mediante etiquetas de presencia dedicadas y opera de forma independiente a la dirección de clasificación.

Basic Usage

El siguiente ejemplo construye una clave compuesta que consta de un ID de cuenta (ASC, NULLS LAST) y un Nombre (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 proporciona cuatro configuraciones explícitas de orden de clasificación:

  • AscNullsFirst
  • AscNullsLast
  • DescNullsFirst
  • DescNullsLast

El posicionamiento de NULL nunca se infiere de manera implícita. Si se pasa un valor de Order inválido, el generador registra ErrInvalidOrder, el cual se devuelve al llamar a Key() o Err().

Prefix Scanning and Range Bounds

Las claves compuestas de Schottky no contienen cabeceras globales, metadatos de conteo de campos, etiquetas de tipo ni registros de cierre (trailers). Asumiendo que el esquema se conoce de antemano, las codificaciones de los campos simplemente se concadenan.

Debido a esta disposición, los bytes codificados de los campos principales forman un prefijo válido para los escaneos de rango. En el ejemplo anterior, accountPrefix se puede utilizar directamente como un filtro de prefijo para escanear todos los registros donde Account ID == 42.

Para calcular el límite superior exclusivo para escaneos de rango semiabiertos [prefix, upper), utilice 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        // Escaneo de rango semiabierto [accountPrefix, upper)
10} else {
11        // Escaneo de rango abierto no acotado
12}

Nota: Builder.Len() debe medirse en límites de campo limpios. Dividir dentro del flujo de bytes interno de un campo produce un prefijo inválido.

Zero-Allocation and Buffer Management

La generación de claves se ejecuta frecuentemente en rutas críticas de bases de datos. Para eliminar las asignaciones en el montón (heap allocations) y la sobrecarga de redimensionamiento de búferes, Builder trabaja estrictamente dentro de la capacidad del sector (slice) proporcionado por el invocador y no se reasignará internamente.

Si el búfer se queda sin capacidad, se registra ErrShortBuffer sin escribir bytes parciales. Las escrituras de campos son atómicas, y el primer error encontrado se preserva hasta que se verifique mediante Key() o Err(). Proporcionar suficiente capacidad por adelantado garantiza una codificación sin asignaciones.

Los tamaños de los búferes se pueden calcular de antemano utilizando funciones auxiliares como EncodedBytesSize, EncodedStringSize y EncodedDecimalSize, o mediante constantes de tamaño fijo. La clave devuelta hace referencia directa al búfer proporcionado, dejando la gestión del ciclo de vida de la memoria en manos del invocador.

El Decoder funciona de manera simétrica: toma prestado directamente de la clave de entrada, requiere búferes de destino proporcionados por el invocador para campos de longitud variable, y proporciona Remaining() == 0 para detectar bytes al final o discrepancias en el esquema.

Supported Data Types

  • Integers: Con signo y sin signo (de 8 bits a 64 bits), Int128
  • Floating-Point & Numerics: Float32, Float64, texto decimal
  • Basic Types: Cadena binaria, sector de bytes, booleano, rango de enumeración (enum rank)
  • Date & Time: Fecha, hora, hora con huso horario, marca de tiempo, duración, intervalo de calendario
  • Network & Identifiers: UUID, MAC, IP, prefijo IP, prefijo de red canónico, LSN
  • Composite Structures: Tuplas anidadas, rangos y codificaciones estructurales sin procesar
  • Collation: Claves de ordenación Unicode y tokens canónicos externos

El mapeo de tipos SQL está alineado con las reglas de clasificación de B-tree de PostgreSQL 18. Los tipos dependientes de los catálogos de bases de datos o del estado interno del motor se manejan pasando tokens canónicos externos.

String Collation

Builder.String toma por defecto el orden binario UTF-8 sin procesar. Para la clasificación consciente de la configuración regional (locale-aware), Schottky proporciona un Collator inmutable y seguro para concurrencia:

  • Deterministic Collation: Codifica la clave de ordenación junto con los bytes UTF-8 sin procesar para proporcionar un desempate cuando los pesos de ordenación son idénticos.
  • Nondeterministic Collation: Trata las cadenas con igual ordenación como idénticas, omitiendo el desempate de bytes sin procesar.

Las versiones de Unicode y de perfiles deben rastrearse en el esquema de metadatos. Si los proveedores de ordenación o la configuración de los perfiles cambian, las claves existentes deben reconstruirse.

Schema Management

Debido a que las claves de Schottky son secuencias de bytes sin procesar y sin cabecera, la capa de esquema debe realizar un seguimiento de:

  1. La secuencia de campos y los tipos de datos.
  2. Las direcciones de clasificación (ASC/DESC) y el orden de los valores NULL (NULLS FIRST/LAST).
  3. La ordenación de cadenas (string collation) y las reglas de normalización.
  4. Las versiones de los perfiles de Schottky y de Collation.

Comparar claves generadas con diferentes esquemas o decodificar contra un esquema discrepante rompe las garantías de orden.

Performance and Links

En Go 1.27+, se puede habilitar la aceleración SIMD portátil experimental usando GOEXPERIMENT=simd. Las rutas escalares y SIMD producen claves con bytes idénticos.