SPSC Ring Buffer em Zig: Fila Lock-Free sem Mutex

Para construir um ring buffer SPSC em Zig, restrinja o contrato a um produtor e um consumidor, use um array circular de capacidade fixa e publique progresso com índices atômicos. O produtor avança tail depois de escrever o item; o consumidor avança head depois de ler. Sem esse ordenamento, um lado pode observar um índice novo e ainda ler memória pela metade.

SPSC não substitui a fila limitada com Mutex e Condition. Ele remove o lock do caminho quente quando o perfil já mostrou contenção e o desenho realmente tem um único escritor e um único leitor. Se a equipe ainda está decidindo entre primitiva atômica e região crítica, comece pelo guia Mutex vs Atomic.

Este artigo mostra um desenho mínimo, correto e auditável: capacidade potência de 2, máscara, padding de cache line, backpressure explícito e uma rubrica para saber quando não implementar lock-free.

Resposta rápida: use SPSC quando estes itens forem verdade

Regra prática: se você não consegue desenhar o sistema com um thread produzindo e um thread consumindo aquele buffer, não use SPSC. Crie outro canal, faça sharding por núcleo ou fique com mutex.

O contrato que o código precisa impor

Um ring buffer SPSC só é seguro se estas regras forem verdade o tempo todo:

1. somente uma thread chama push;
2. somente uma thread chama pop;
3. a capacidade é constante depois da criação;
4. um slot só é reescrito depois que o consumidor já avançou head além dele;
5. o payload é escrito antes da publicação de tail;
6. o payload é lido depois da observação de tail com ordenação adequada.

Quebrar a regra 1 ou 2 transforma o algoritmo em outro problema: MPSC, SPMC ou MPMC. Esses desenhos pedem CAS no índice, buffers por produtor, hazard pointers ou um lock. Não “estenda” o SPSC com um comentário otimista.

Implementação mínima com capacidade potência de 2

A versão abaixo usa std.atomic.Value, máscara binária e slots alinhados para reduzir falsa partilha entre head e tail. Os nomes exatos das APIs atômicas podem variar entre releases do Zig; fixe a versão no build.zig.zon e ajuste a chamada, mantendo o protocolo.

const std = @import("std");

pub fn SpscRing(comptime T: type, comptime capacity: usize) type {
    if (capacity < 2 or (capacity & (capacity - 1)) != 0) {
        @compileError("capacity must be a power of two >= 2");
    }

    return struct {
        const Self = @This();
        const mask: usize = capacity - 1;

        // Índices monotônicos: crescem sem voltar a zero.
        head: std.atomic.Value(usize) align(64) = std.atomic.Value(usize).init(0),
        tail: std.atomic.Value(usize) align(64) = std.atomic.Value(usize).init(0),
        slots: [capacity]T = undefined,

        pub fn push(self: *Self, item: T) bool {
            const tail = self.tail.load(.unordered);
            const head = self.head.load(.acquire);

            if (tail -% head == capacity) {
                return false; // cheio: backpressure para o produtor
            }

            self.slots[tail & mask] = item;
            self.tail.store(tail +% 1, .release);
            return true;
        }

        pub fn pop(self: *Self) ?T {
            const head = self.head.load(.unordered);
            const tail = self.tail.load(.acquire);

            if (head == tail) {
                return null; // vazio
            }

            const item = self.slots[head & mask];
            self.head.store(head +% 1, .release);
            return item;
        }

        pub fn len(self: *Self) usize {
            const tail = self.tail.load(.acquire);
            const head = self.head.load(.acquire);
            return tail -% head;
        }

        pub fn isEmpty(self: *Self) bool {
            return self.len() == 0;
        }

        pub fn isFull(self: *Self) bool {
            return self.len() == capacity;
        }
    };
}

Pontos que o review precisa verificar:

• tail -% head usa wrap de inteiro sem sinal e mede ocupação sem travar;
• tail & mask mapeia o índice monotônico para o slot circular;
• store(.release) no índice publicado cria o happens-before com o load(.acquire) do outro lado;
• push e pop não são reentrantes nem seguros entre múltiplos produtores/consumidores.

Por que escrever o item antes de publicar o índice

O erro clássico em filas lock-free é inverter a ordem:

// Errado: publica o índice antes do payload estar visível.
self.tail.store(tail +% 1, .release);
self.slots[tail & mask] = item;

Nesse caso, o consumidor pode observar tail novo, ler o slot e obter lixo, valor antigo ou uma struct pela metade. Em Zig isso não “parece data race no índice”; é um bug de protocolo de memória.

A ordem correta é sempre:

1. verificar espaço/item disponível;
2. escrever ou ler o payload no slot;
3. só então publicar o novo índice com release.

A mesma lógica vale no consumidor: copie ou consuma o item e só depois avance head, liberando o slot para reuso.

Backpressure sem Condition

SPSC responde “cheio” ou “vazio”. Ele não coloca a thread para dormir. Em produção, escolha uma política explícita:

Se o desenho passa a maior parte do tempo dormindo e acordando, a fila com Mutex e Condition costuma ser mais simples e suficiente. SPSC brilha quando ambos os lados já estão ativos e o lock virou ruído mensurável.

Exemplo: produtor e consumidor em threads dedicadas

const std = @import("std");

const Queue = SpscRing(u64, 1024);

fn producer(q: *Queue) void {
    var i: u64 = 0;
    while (i < 10_000) {
        if (q.push(i)) {
            i += 1;
        } else {
            std.atomic.spinLoopHint();
        }
    }
}

fn consumer(q: *Queue, sum: *std.atomic.Value(u64)) void {
    var got: u64 = 0;
    while (got < 10_000) {
        if (q.pop()) |value| {
            _ = sum.fetchAdd(value, .monotonic);
            got += 1;
        } else {
            std.atomic.spinLoopHint();
        }
    }
}

pub fn main() !void {
    var queue = Queue{};
    var sum = std.atomic.Value(u64).init(0);

    const t1 = try std.Thread.spawn(.{}, producer, .{&queue});
    const t2 = try std.Thread.spawn(.{}, consumer, .{ &queue, &sum });
    t1.join();
    t2.join();

    std.debug.print("sum={}\n", .{sum.load(.unordered)});
}

Esse exemplo é didático. Em serviço real, combine timeout, métricas de ocupação, contador de push rejeitado e um caminho de shutdown que interrompa os dois lados sem deixar o consumidor spinando para sempre.

Padding de cache line e falsa partilha

head e tail são escritos por threads diferentes. Se eles caírem na mesma linha de cache, cada atualização invalida a linha do outro núcleo. O align(64) no exemplo reduz essa falsa partilha.

Checklist adicional:

• não coloque contadores de métricas quentes ao lado de head/tail;
• evite um grande struct de estatísticas atualizado a cada push;
• meça com número de núcleos e arquitetura de produção; x86-64 e ARM diferem;
• se o payload for grande, considere armazenar ponteiros/ids e manter o corpo fora do ring.

Falsa partilha parece “lock-free lento”. O flamegraph mostra tempo em coerência de cache, não em Mutex.lock.

Encaixe em pipelines de rede e parsing

Um uso comum em serviços Zig é separar o thread que faz I/O do thread que interpreta mensagens:

1. o leitor de socket preenche frames e faz push de descritores leves;
2. o worker consome com pop, valida e executa a lógica;
3. respostas voltam por outro SPSC ou por um caminho com lock, se houver vários writers.

Isso combina bem com o guia de protocolo binário, framing e endianness: o ring transporta um handle (offset, len, conn_id), não uma struct gigante copiada em cada hop. O buffer de bytes permanece no allocator da conexão; o SPSC só move o bilhete de trabalho.

Evite empurrar para o ring:

• slices que apontam para o buffer de leitura ainda em reuso;
• arenas que serão resetadas antes do pop;
• arquivos ou sockets sem ownership claro.

Se o frame precisa sobreviver, copie para um bump/arena do worker ou transfira ownership de forma documentada. O ring não gerencia lifetime; ele só ordena a entrega.

Métricas mínimas para operar o buffer

Sem instrumentação, SPSC vira caixa-preta. Exponha pelo menos:

Atualize contadores com atomics locais ou por thread e agregue fora do caminho quente. Não faça log formatado dentro de push/pop.

SPSC vs thread pool vs fila com lock

Um pool de threads resolve distribuição de trabalho. Um ring SPSC resolve transferência ordenada e barata entre dois papéis fixos. São peças diferentes. Dá para combinar: cada worker tem um SPSC de entrada alimentado por um demultiplexador, ou um SPSC por núcleo em telemetria.

Testes que realmente encontram bug

Testes single-threaded não validam o protocolo. No mínimo:

1. Produtor rápido, consumidor lento até encher a fila e exercitar push == false;
2. Consumidor rápido, produtor lento até esvaziar e exercitar pop == null;
3. Capacidade mínima (2) para forçar wrap cedo;
4. Interleaving longo com dezenas de milhões de itens e checksum final;
5. ASAN/GPA em debug se o payload aloca ou guarda ponteiros;
6. Shutdown: garantir que ninguém publica índice depois de destruir o buffer.

Para payloads com ponteiros, o tempo de vida precisa sobreviver até o pop. Arena por lote, refcount ou cópia defensiva entram aqui; o ring só transporta o valor.

Erros comuns

Usar SPSC com dois produtores “porque quase não colidem”. Colidem. O bug aparece em pico, não no notebook.

Publicar o índice com monotonic e achar que o payload fica visível. Em muitas arquiteturas você precisa do par release/acquire para ordenar a escrita do slot.

Tratar capacidade cheia como impossível. Sem política de backpressure, o produtor ou spinna para sempre ou descarta sem métrica.

Guardar ponteiros para stack do produtor. O consumidor lê depois que o frame já morreu.

Misturar leitura não atômica de tail no consumidor “para ganhar performance”. O protocolo inteiro depende desses carregamentos.

Copiar o desenho SPSC para MPMC trocando só o nome. MPMC é outro algoritmo.

Checklist de code review

• o tipo documenta “1 produtor / 1 consumidor” no nome ou no comentário de módulo;
• capacidade é potência de 2 validada em comptime;
• payload é escrito antes do store de tail;
• payload é lido depois do load de tail com acquire;
• head só avança no consumidor; tail só avança no produtor;
• push cheio e pop vazio têm política e métrica;
• head/tail não compartilham cache line sem necessidade;
• testes cobrem wrap, burst e checksum;
• a versão do Zig está fixada e a API atômica confere com ela;
• existe um plano claro para não crescer esse canal até N:N.

Quando não escreva um ring lock-free

Escolha outra peça se:

• a equipe ainda não mediu contenção de mutex;
• o fluxo tem N produtores naturais (várias conexões, vários workers);
• o consumidor fica ocioso e precisa acordar barato;
• a invariável inclui mais do que a fila (créditos, janela, deduplicação);
• o benefício esperado é teórico e o prazo de entrega é real.

Nesses casos, a fila com lock, o std.Thread.Pool ou um pipeline com canais por shard entregam progresso com menos risco. Lock-free é ferramenta de precisão, não distintivo de senioridade.

Rubrica de decisão em quatro perguntas

1. O canal é realmente 1:1? Se a resposta depender de “na prática quase sempre”, use mutex.
2. Os dois lados já estão acordados na maior parte do tempo? Se não, você precisa de espera bloqueante além do ring.
3. O perfil mostrou o lock no flamegraph? Sem evidência, a complexidade não se paga.
4. O payload tem ownership óbvio até o pop? Se não, resolva lifetime antes de remover o mutex.

Se três das quatro respostas forem dúvidas, não implemente SPSC ainda. Documente o gargalo, escreva o teste de carga e só então substitua o trecho quente.

Conclusão

Um SPSC ring buffer em Zig é uma fila circular de contrato estreito: um escritor, um leitor, capacidade fixa e publicação atômica dos índices depois do payload. Use-o no hot path quando o perfil mostrar que o mutex custa de verdade e o desenho já é naturalmente 1:1. Para o restante do sistema, prefira padrões mais simples e compostáveis — Condition para espera, Pool para fan-out e Mutex para estado composto.

Se você está montando o caminho de dados completo, encaixe este buffer entre o parsing e o worker dedicado, meça ocupação e rejeições, e só então considere variantes MPSC. A disciplina do contrato SPSC vale mais do que micro-otimizações no & mask.