GoSuda

Schottky: codificación de claves de bytes sin asignación de memoria y con preservación del orden para Go

By Lemon Mint views ...

Al implementar almacenes clave-valor basados en árboles LSM o B-tree, así como índices de bases de datos, los campos compuestos suelen necesitar combinarse en una única clave de bytes.

Los formatos de serialización estándar, como JSON o Protocol Buffers, no están diseñados para este propósito, ya que sus salidas serializadas en bytes no preservan el orden natural de clasificación que requieren las comparaciones bytewise sin signo (bytes.Compare o memcmp).

Schottky es una biblioteca 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

Serialización frente a claves de ordenación

Garantizar una ordenación bytewise correcta requiere abordar varios detalles de bajo nivel de la representación de datos:

  • Enteros: La codificación estándar en complemento a dos con orden big-endian rompe el orden natural debido al bit de signo más significativo. Invertir el bit de signo es necesario para lograr comparaciones de bytes sin signo correctas.
  • Números de punto flotante: Requieren ajustes del bit de signo, un orden invertido para los valores negativos y un tratamiento consistente de NaN y -0.
  • Cadenas y segmentos de bytes de longitud variable: Los límites de los campos deben preservarse sin romper el orden de los prefijos.
  • Requisitos de las claves compuestas: Soporte para un orden ASC/DESC independiente por campo, reglas NULLS FIRST/LAST desacopladas, precedencia lexicográfica estricta (los campos anteriores determinan el orden) y compatibilidad con el escaneo por prefijos.

Schottky convierte cada valor en una carga canónica antes de aplicar las etiquetas de presencia y la orientación direccional. Para los campos DESC, cada byte de la carga ASC se invierte bit a bit (^b). La ubicación de los NULL se gestiona mediante etiquetas de presencia dedicadas y funciona de forma independiente de la dirección de ordenación.

Uso básico

El siguiente ejemplo construye una clave compuesta formada por 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        // Escribe el ID de cuenta como entero de 64 bits con orden ASC y NULLS LAST
14        builder.Int64(42, schottky.AscNullsLast)
15        accountPrefixLen := builder.Len()
16
17        // Escribe el nombre como cadena con orden DESC y NULLS FIRST
18        builder.String("Ada", schottky.DescNullsFirst)
19        key, err := builder.Key()
20
21        if err != nil {
22                panic(err)
23        }
24        accountPrefix := key[:accountPrefixLen]
25        fmt.Printf("key=%x\nprefix=%x\n", key, accountPrefix)
26}

Schottky proporciona cuatro configuraciones explícitas de orden de clasificación:

  • AscNullsFirst
  • AscNullsLast
  • DescNullsFirst
  • DescNullsLast

La posición de los NULL nunca se infiere de forma implícita. Si se pasa un valor de Order no válido, el builder registra ErrInvalidOrder, que se devuelve al invocar Key() o Err().

Escaneo por prefijos y límites de rango

Las claves compuestas de Schottky no contienen cabeceras globales, metadatos de número de campos, etiquetas de tipo ni trailers. Asumiendo que el esquema se conoce de antemano, las codificaciones de los campos simplemente se concatenan.

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

Para calcular el límite superior exclusivo de los 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 sin límite superior
12}

Nota: Builder.Len() debe medirse en los límites de campo correctos. Cortar dentro del flujo interno de bytes de un campo produce un prefijo no válido.

Cero asignaciones y gestión de búferes

La generación de claves se ejecuta con frecuencia en rutas críticas de la base de datos. Para eliminar las asignaciones en el heap y la sobrecarga de redimensionado de búferes, Builder trabaja estrictamente dentro de la capacidad del slice proporcionado por el llamador y no realiza reasignaciones internas.

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 conserva hasta que se consulta mediante Key() o Err(). Proporcionar capacidad suficiente desde el principio garantiza una codificación sin asignaciones.

Los tamaños de búfer pueden calcularse de antemano mediante funciones auxiliares como EncodedBytesSize, EncodedStringSize y EncodedDecimalSize, o mediante constantes de tamaño fijo. La clave devuelta hace referencia directamente al búfer proporcionado, dejando la gestión del ciclo de vida de la memoria a cargo del llamador.

El Decoder funciona de forma simétrica: toma prestados los datos directamente de la clave de entrada, requiere búferes de destino proporcionados por el llamador para los campos de longitud variable y proporciona Remaining() == 0 para detectar bytes sobrantes o discrepancias de esquema.

Tipos de datos admitidos

  • Enteros: con signo y sin signo (de 8 a 64 bits), Int128
  • Punto flotante y numéricos: Float32, Float64, texto decimal
  • Tipos básicos: cadena binaria, segmento de bytes, booleano, rango de enumeración
  • Fecha y hora: fecha, hora, hora con zona horaria, marca de tiempo, duración, intervalo de calendario
  • Red e identificadores: UUID, MAC, IP, prefijo IP, prefijo de red canónico, LSN
  • Estructuras compuestas: tuplas anidadas, rangos y codificaciones estructurales sin procesar
  • Collation: claves de collation Unicode y tokens canónicos externos

El mapeo de tipos SQL está alineado con las reglas de ordenación de los árboles B de PostgreSQL 18. Los tipos que dependen de catálogos de la base de datos o del estado interno del motor se gestionan mediante el paso de tokens canónicos externos.

Collation de cadenas

Builder.String utiliza por defecto el orden binario UTF-8 sin procesar. Para una ordenación sensible a la configuración regional, Schottky proporciona un Collator inmutable y seguro para uso concurrente:

  • Collation determinista: codifica la clave de collation junto con los bytes UTF-8 sin procesar para proporcionar un desempate cuando los pesos de collation son idénticos.
  • Collation no determinista: trata las cadenas iguales según la collation como idénticas, omitiendo el desempate por bytes sin procesar.

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

Gestión del esquema

Como las claves de Schottky son secuencias de bytes sin procesar y sin cabecera, la capa de esquema debe registrar:

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

Comparar claves generadas con esquemas distintos, o decodificar con un esquema que no coincide, rompe las garantías de ordenación.

Rendimiento y enlaces

En Go 1.27 o posterior, la aceleración SIMD portable y experimental puede activarse mediante GOEXPERIMENT=simd. Las rutas escalares y SIMD producen claves idénticas byte a byte.