LogFold: Compressing Logs with Structured Tokens and Hybrid Encoding

Resumo Técnico: LogFold

1. O Problema

Os logs de sistemas são essenciais para manutenção, auditoria de segurança e modelagem de desempenho, exigindo armazenamento de longo prazo. No entanto, o volume de dados gerados cresce exponencialmente, criando desafios significativos de custo e capacidade de armazenamento.

As soluções existentes apresentam duas limitações principais:

1. Compressores Genéricos (ex: Gzip, Bzip2): Falham em reconhecer padrões recorrentes específicos de logs, como templates repetidos e estruturas complexas dentro de tokens.
2. Compressores Específicos de Logs (ex: LogZip, LogReducer): Embora utilizem análise de templates e codificação de dicionário, eles sofrem de duas falhas críticas:
   • Ignorância de Tokens Estruturados: Não exploram redundâncias dentro de tokens complexos (ex: datas 2015-07-09 ou IDs de processo service[1234]), tratando-os como unidades opacas.
   • Falta de Estratégia de Codificação Híbrida: Aplicam estratégias de codificação grosseiras (ex: codificação numérica apenas para números puros), negligenciando tokens de tipos mistos (strings + números) que possuem características estruturais distintas.

2. Metodologia: LogFold

O LogFold é um novo método de compressão que introduz uma abordagem consciente de tokens estruturados e utiliza uma codificação híbrida. A arquitetura consiste em quatro componentes principais:

A. Analisador de Tokens (Token Analyzer)

• Diferente de abordagens anteriores que quebram logs em templates primeiro, o LogFold trata a entrada de log de forma holística.
• Classifica cada token em três tipos: Estruturado (com delimitadores internos, ex: datas), Não Estruturado (strings puras) e Estático (texto fixo).
• Substitui tokens dinâmicos por placeholders (<-> para estruturados, <*> para não estruturados), preservando a sequência original.

B. Processador de Tokens Estruturados (Structured Token Processor)
Este componente é o núcleo da inovação, explorando redundâncias dentro dos tokens estruturados em duas fases:

1. Agrupamento Consciente do Esqueleto de Delimitadores: Agrupa tokens estruturados que compartilham o mesmo "esqueleto" (padrão de caracteres não alfanuméricos, ex: <>-<>-<> para datas). Isso reduz a redundância do formato.
2. Mineração de Padrões (Pattern Mining): Analisa as matrizes de sub-tokens resultantes para identificar "posições críticas" (colunas com valores dominantes ou constantes).
   • Utiliza heurísticas baseadas em histogramas, razão de dominância e entropia de Shannon para identificar colunas que podem ser fixadas no esqueleto.
   • Realiza um Re-agrupamento Condicional: Divide os grupos em subgrupos mais homogêneos com esqueletos refinados (ex: transformar 2015-<>-<> em 2015-07-<> se Julho for dominante).

C. Codificador Híbrido (Hybrid Encoder)
Aplica estratégias de codificação otimizadas baseadas no tipo de dado:

1. Codificação Numérica Otimizada: Usa codificação delta dinâmica e codificação elástica (var-length integer). Inclui uma otimização de "colunas combinadas" para entidades compostas (ex: timestamps), concatenando sub-tokens numéricos antes de calcular deltas.
2. Codificação de Dicionário: Aplicada a tokens não estruturados e padrões de esqueleto refinados.
3. Codificação de Tipo Misto (Inovação Chave): Para matrizes contendo tanto números quanto strings (ex: service[4305]), mapeia strings para IDs numéricos contíguos e aplica uma transformação de paridade (números originais tornam-se pares, IDs de strings tornam-se ímpares). Isso permite codificar toda a coluna uniformemente como dados numéricos, explorando a homogeneidade de colunas.

D. Empacotador (Packer)

• Integra os arquivos intermediários (dicionários e dados binários) e aplica um compressor genérico final (ex: LZMA) para gerar o arquivo de archive compactado.

3. Contribuições Principais

1. Identificação de Limitações: Revelou que compressores atuais negligenciam redundâncias intra-token em tokens estruturados e carecem de estratégias de codificação finas para tipos mistos.
2. Novo Algoritmo (LogFold): Propôs um compressor que decompõe tokens estruturados em esqueletos e sub-tokens, explorando padrões recorrentes e homogeneidade de colunas.
3. Estratégia Híbrida: Introduziu uma codificação unificada para tokens de tipo misto, permitindo compressão numérica eficiente em dados que contêm strings e números.
4. Validação Empírica: Demonstrou superioridade em 16 conjuntos de dados públicos, superando o estado da arte (SOTA) em taxa de compressão e mantendo velocidade competitiva.

4. Resultados Experimentais

O LogFold foi avaliado em 16 conjuntos de dados públicos (supercomputadores, sistemas distribuídos, sistemas móveis, etc.), totalizando mais de 77 GB de dados.

• Taxa de Compressão (Compression Ratio - CR):
  • Alcançou uma taxa média de 89.519, superando o melhor baseline (Denum) em 11.11% e o Gzip em 494.19%.
  • Obteve a melhor taxa de compressão em 12 dos 16 conjuntos de dados.
• Velocidade de Compressão:
  • Média de 9.842 MB/s. Embora mais lento que compressores puramente numéricos (como Denum), é competitivo e justificado pelo ganho massivo em armazenamento.
• Estudos de Ablação: Confirmaram que tanto o Processador de Tokens Estruturados quanto o Codificador Híbrido são essenciais; a remoção de qualquer um resulta em queda significativa na taxa de compressão.
• Análise de Sensibilidade: O sistema demonstrou ser robusto a variações nos parâmetros internos (thresholds de identificação de posição crítica e re-agrupamento).
• Descompressão: A velocidade de descompressão é limitada principalmente pela reconstrução de tokens numéricos (passo computacionalmente intensivo), mas garante recuperação sem perdas.

5. Significado e Impacto

O LogFold representa um avanço significativo na gestão de logs, oferecendo uma solução prática para cenários onde a eficiência de armazenamento é prioritária, como:

• Arquivamento de Longo Prazo: Redução drástica de custos em armazenamento em nuvem (ex: S3 Glacier).
• Agregação Centralizada: Redução da largura de banda necessária para enviar logs para servidores centrais.
• Análise Retroativa: Permite manter volumes massivos de dados históricos para auditoria e forense sem custos proibitivos.

Ao tratar tokens estruturados não como unidades opacas, mas como estruturas decomponíveis, e ao criar uma codificação híbrida inteligente, o LogFold estabelece um novo padrão de referência (SOTA) para compressão de logs, equilibrando alta taxa de compressão com viabilidade de processamento.