GoSuda

Schottky: Codificação de Chaves de Bytes sem Alocação e com Preservação de Ordem para Go

By Lemon Mint views ...

Ao implementar armazenamentos chave-valor baseados em LSM-tree ou B-tree e índices de banco de dados, campos compostos frequentemente precisam ser combinados em uma única chave de bytes.

Formatos de serialização padrão como JSON ou Protocol Buffers não são projetados para essa finalidade, pois suas saídas serializadas em bytes não preservam a ordenação natural exigida por comparações bytewise sem sinal (bytes.Compare ou memcmp).

Schottky é uma biblioteca em Go projetada para codificar tuplas compostas de múltiplos tipos em chaves de bytes que preservam a ordem.

1go get gosuda.org/schottky@latest

Serialização versus Chaves de Ordenação

Garantir a ordenação bytewise correta exige tratar vários detalhes de representação de dados em baixo nível:

  • Inteiros: A codificação padrão em complemento de dois com big-endian quebra a ordenação natural devido ao bit de sinal mais significativo. Inverter o bit de sinal é necessário para comparações de bytes sem sinal corretas.
  • Números de ponto flutuante: Requerem ajustes no bit de sinal, ordenação invertida para valores negativos e tratamento consistente de NaN e -0.
  • Strings e fatias de bytes de comprimento variável: Os limites dos campos devem ser preservados sem quebrar as ordens de prefixo.
  • Requisitos de chaves compostas: Suporte a ordenação ASC/DESC independente por campo, regras NULLS FIRST/LAST desacopladas, precedência lexicográfica estrita (campos anteriores determinam a ordem) e compatibilidade com varreduras por prefixo.

O Schottky converte cada valor em uma carga útil canônica antes de aplicar as etiquetas de presença e a orientação direcional. Para campos DESC, cada byte da carga útil ASC é invertido bit a bit (^b). A posição de NULL é tratada por meio de etiquetas de presença dedicadas e opera independentemente da direção de ordenação.

Uso Básico

O exemplo a seguir constrói uma chave composta formada por um ID de Conta (ASC, NULLS LAST) e um Nome (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}

O Schottky oferece quatro configurações explícitas de ordem de classificação:

  • AscNullsFirst
  • AscNullsLast
  • DescNullsFirst
  • DescNullsLast

A posição de NULL nunca é inferida implicitamente. Se um valor Order inválido for passado, o builder registra ErrInvalidOrder, que é retornado ao chamar Key() ou Err().

Varreduras por Prefixo e Limites de Intervalo

As chaves compostas do Schottky não contêm cabeçalhos globais, metadados de quantidade de campos, etiquetas de tipo ou rodapés. Presumindo que o esquema seja conhecido antecipadamente, as codificações dos campos são simplesmente concatenadas.

Devido a esse layout, os bytes codificados dos campos iniciais formam um prefixo válido para varreduras de intervalo. No exemplo acima, accountPrefix pode ser usado diretamente como filtro de prefixo para varrer todos os registros em que ID da Conta == 42.

Para calcular o limite superior exclusivo em varreduras de intervalo semiaberto [prefix, upper), use 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        // Varredura de intervalo semiaberto [accountPrefix, upper)
10} else {
11        // Varredura de intervalo aberto e sem limite
12}

Nota: Builder.Len() deve ser medido em limites de campo consistentes. Fatiar dentro do fluxo interno de bytes de um campo produz um prefixo inválido.

Alocação Zero e Gerenciamento de Buffer

A geração de chaves frequentemente executa em caminhos críticos de banco de dados. Para eliminar alocações no heap e a sobrecarga de redimensionamento de buffers, o Builder opera estritamente dentro da capacidade da fatia fornecida pelo chamador e não realiza realocação interna.

Se o buffer ficar sem capacidade, ErrShortBuffer é registrado sem gravar bytes parciais. As escritas de campos são atômicas, e o primeiro erro encontrado é preservado até ser verificado por meio de Key() ou Err(). Fornecer capacidade suficiente antecipadamente garante codificação com alocação zero.

Os tamanhos dos buffers podem ser calculados antecipadamente usando funções auxiliares como EncodedBytesSize, EncodedStringSize e EncodedDecimalSize, ou por meio de constantes de tamanho fixo. A chave retornada referencia diretamente o buffer fornecido, deixando o gerenciamento do ciclo de vida da memória a cargo do chamador.

O Decoder funciona de forma simétrica: ele empresta diretamente da chave de entrada, exige buffers de destino fornecidos pelo chamador para campos de comprimento variável e fornece Remaining() == 0 para detectar bytes residuais ou incompatibilidades de esquema.

Tipos de Dados Suportados

  • Inteiros: Com e sem sinal (de 8 a 64 bits), Int128
  • Ponto Flutuante e Numéricos: Float32, Float64, texto decimal
  • Tipos Básicos: String binária, fatia de bytes, booleano, rank de enum
  • Data e Hora: Date, Time, Zoned Time, Timestamp, Duration, Calendar Interval
  • Rede e Identificadores: UUID, MAC, IP, prefixo IP, prefixo de rede canônico, LSN
  • Estruturas Compostas: Tuplas aninhadas, Ranges e codificações estruturais brutas
  • Collation: Unicode Collation Keys e tokens canônicos externos

O mapeamento de tipos SQL está alinhado às regras de ordenação de B-tree do PostgreSQL 18. Tipos que dependem de catálogos de banco de dados ou do estado interno do motor são tratados por meio da passagem de tokens canônicos externos.

Collation de Strings

Builder.String usa, por padrão, a ordem binária UTF-8 bruta. Para ordenação sensível à localidade, o Schottky oferece um Collator imutável e seguro para uso concorrente:

  • Collation Determinística: Codifica a chave de collation juntamente com os bytes UTF-8 brutos para fornecer um critério de desempate quando os pesos de collation forem idênticos.
  • Collation Não Determinística: Trata strings iguais na collation como idênticas, omitindo o desempate por bytes brutos.

As versões de Unicode e de perfil devem ser registradas no esquema de metadados. Se os provedores de collation ou as configurações de perfil forem alterados, as chaves existentes devem ser reconstruídas.

Gerenciamento de Esquema

Como as chaves do Schottky são sequências de bytes brutas, sem cabeçalho, a camada de esquema deve registrar:

  1. A sequência de campos e os tipos de dados.
  2. As direções de ordenação (ASC/DESC) e a ordenação de NULL (NULLS FIRST/LAST).
  3. As regras de collation e normalização de strings.
  4. As versões dos perfis do Schottky e da Collation.

Comparar chaves geradas com esquemas diferentes, ou decodificar com um esquema incompatível, quebra as garantias de ordenação.

Desempenho e Links

No Go 1.27+, a aceleração SIMD portátil experimental pode ser habilitada usando GOEXPERIMENT=simd. Os caminhos escalar e SIMD produzem chaves idênticas byte a byte.