GoSuda

Schottky: Codificação de Byte-Key Zero-Allocation e Order-Preserving para Go

By Lemon Mint
views ...

Ao implementar armazenamento de chave-valor e índices de banco de dados baseados em árvores LSM ou B-trees, 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 esse propósito, pois suas saídas de bytes serializadas não preservam a ordem natural de classificação exigida por comparações sem sinal byte a byte (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 ordenação.

1go get gosuda.org/schottky@latest

Serialização vs. Chaves de Classificação

Garantir a classificação correta byte a byte requer abordar vários detalhes de representação de dados de 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 corretas de bytes sem sinal.
  • 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 de comprimento variável e fatias de bytes: Os limites dos campos devem ser preservados sem quebrar as ordens de classificação de prefixo.
  • Requisitos de chaves compostas: Suporte a ordenação ASC/DESC independente por campo, regras de NULLS FIRST/LAST desacopladas, precedência lexicográfica estrita (campos anteriores determinam a ordem) e compatibilidade com varredura de prefixo.

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

Uso Básico

O exemplo a seguir constrói uma chave composta consistindo em 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 fornece quatro configurações explícitas de ordem de classificação:

  • AscNullsFirst
  • AscNullsLast
  • DescNullsFirst
  • DescNullsLast

O posicionamento de NULL nunca é inferido implicitamente. Se um valor de Order inválido for passado, o construtor registra ErrInvalidOrder, que é retornado ao chamar Key() ou Err().

Varredura de Prefixo e Limites de Intervalo

As chaves compostas do Schottky não contêm cabeçalhos globais, metadados de contagem de campos, tags de tipo ou trailers. Assumindo que o esquema seja conhecido com antecedência, as codificações dos campos são simplesmente concatenadas.

Devido a essa disposição, os bytes codificados dos campos iniciais formam um prefixo válido para varreduras de intervalo. No exemplo acima, accountPrefix pode ser usado diretamente como um filtro de prefixo para varrer todos os registros onde Account ID == 42.

Para calcular o limite superior exclusivo para varreduras de intervalo semi-abertas [prefix, upper), utilize 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 semi-aberta [accountPrefix, upper)
10} else {
11        // Varredura de intervalo aberto não limitado
12}

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

Alocação Zero e Gerenciamento de Buffer

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

Se o buffer esgotar sua capacidade, ErrShortBuffer é registrado sem gravar bytes parciais. As gravações de campos são atômicas, e o primeiro erro encontrado é preservado até ser verificado via Key() ou Err(). Fornecer capacidade suficiente antecipadamente garante a codificação sem alocação.

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

O Decoder opera de forma simétrica: ele empresta diretamente da chave de entrada, requer 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 (8 bits a 64 bits), Int128
  • Ponto Flutuante e Numéricos: Float32, Float64, Texto Decimal
  • Tipos Básicos: String Binária, Fatia de Bytes, Booleano, Classificação de Enum (Enum Rank)
  • Data e Hora: Data, Hora, Hora com Fuso Horário, Carimbo de Data/Hora, Duração, Intervalo de Calendário
  • Rede e Identificadores: UUID, MAC, IP, Prefixo de IP, Prefixo de Rede Canônico, LSN
  • Estruturas Compostas: Tuplas Aninhadas, Intervalos e codificações estruturais brutas
  • Colação: Chaves de Colação Unicode e tokens canônicos externos

O mapeamento de tipos SQL está alinhado com as regras de classificação B-tree do PostgreSQL 18. Tipos dependentes de catálogos de banco de dados ou do estado interno do motor são tratados passando tokens canônicos externos.

Colação de Strings

Builder.String usa por padrão a ordem binária UTF-8 pura. Para classificação sensível à localidade, o Schottky fornece um Collator imutável e seguro para concorrência:

  • Colação Determinística: Codifica a chave de colação junto com os bytes UTF-8 puros para fornecer um critério de desempate quando os pesos de colação forem idênticos.
  • Colação Não Determinística: Trata strings com igualdade de colação como idênticas, omitindo o desempate por bytes puros.

As versões de Unicode e de perfil devem ser rastreadas no esquema de metadados. Se os provedores de colação ou as configurações de perfil mudarem, as chaves existentes devem ser reconstruídas.

Gerenciamento de Esquema

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

  1. Sequência de campos e tipos de dados.
  2. Direções de classificação (ASC/DESC) e ordenação de NULL (NULLS FIRST/LAST).
  3. Regras de colação e normalização de strings.
  4. Versões de perfil do Schottky e de Colação.

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

Desempenho e Links

Em Go 1.27+, a aceleração SIMD portátil experimental pode ser habilitada usando GOEXPERIMENT=simd. Os caminhos escalares e SIMD produzem chaves idênticas em termos de bytes.