CS Fundamentals Trainer · Guias

Idempotência e efeitos exatamente uma vez: chaves, novas tentativas e deduplicação

Por que um timeout torna as novas tentativas, e portanto as duplicatas, inevitáveis; projetos naturalmente idempotentes; chaves de idempotência e a condição de corrida do conferir-e-agir (465 cobranças extras contra nenhuma); chamadas externas e pontos de recuperação; o outbox e o inbox; e quanto custa guardar as chaves.

32 min de leitura

Um cliente toca em "Pagar", a requisição sai do celular e nada volta. O pagamento foi feito? O celular não tem como saber. A requisição pode nunca ter chegado, pode ainda estar rodando, ou pode ter terminado e a resposta se perdeu no caminho de volta. A única saída que parece segura é enviar de novo, e esse é exatamente o movimento que pode cobrar o cliente duas vezes.

Todo sistema que conversa pela rede precisa resolver isso, e a solução tem nome: tornar a operação idempotente, de modo que fazê-la duas vezes tenha o mesmo efeito de fazê-la uma vez. Este guia cobre o que isso significa, como construir do jeito certo (a implementação óbvia tem uma condição de corrida que eu reproduzo), o que fazer quando o trabalho envolve outro sistema que você não consegue desfazer, como isso se aplica a consumidores de fila e quanto custa manter.

Uma nota sobre as medições. Os números deste guia vêm de um pequeno experimento que rodei para ele: um servidor HTTP de verdade no localhost, SQLite e Python 3.13, com o código completo no apêndice. O cenário é propositalmente apertado (um cliente que desiste após 50 ms diante de um handler que leva de 30 a 120 ms) para que as novas tentativas aconteçam com frequência. Em produção elas são mais raras, mas nunca são zero, e eventos raros em escala acontecem todos os dias.

1. Por que as novas tentativas são inevitáveis, e por que machucam

Uma requisição pela rede pode falhar de três maneiras, e quem chamou vê a mesma coisa em todas: um timeout, ou uma conexão derrubada, e nenhuma resposta.

O que realmente aconteceuO que o chamador vêTentar de novo é seguro sem proteção?
A requisição nunca chegou ao servidornenhuma respostasim: nada aconteceu
O servidor ainda está trabalhando nelanenhuma resposta (ainda)não: agora duas cópias rodam
O servidor terminou, a resposta se perdeunenhuma respostanão: o trabalho é feito duas vezes

Quem chama não consegue distinguir os casos, então tem duas opções: desistir (e arriscar uma operação perdida) ou tentar de novo (e arriscar uma duplicata). Sistemas maduros tentam de novo, porque a maioria das falhas é transitória, e por isso precisam que o servidor torne o segundo caso inofensivo. As novas tentativas vêm de mais lugares do que o seu próprio código: clientes HTTP, SDKs móveis, proxies e balanceadores de carga, brokers de fila que reentregam uma mensagem e usuários que apertam o botão de novo.

Os sistemas de mensagens descrevem o mesmo problema como garantias de entrega: no máximo uma vez (nunca duplica, pode perder), pelo menos uma vez (nunca perde, pode duplicar) e exatamente uma vez. A entrega exatamente uma vez por uma rede não confiável não pode ser garantida por ninguém: quem envia nunca tem certeza de que o receptor recebeu a mensagem, que é o velho problema dos Dois Generais. O que se pode ter é exatamente um efeito, e ele é construído a partir de duas partes:

entrega pelo menos uma vez (tentar até ser confirmado) + processamento idempotente (uma repetição não muda nada) = efeito exatamente uma vez

Tudo o que vem a seguir é sobre a segunda metade.

O estrago, medido

No meu experimento, 200 pagamentos de 100 foram enviados a um servidor que cobra um cartão (simulado por um atraso de 30 a 120 ms e uma inserção no banco de dados). O cliente espera 50 ms e tenta de novo até cinco vezes, 20 pagamentos por vez:

Comportamento do servidorRequisições enviadasPagamentos que o cliente viu dar certoCobranças para 200 pagamentosCobranças extras
Sem idempotência670134665465 (um pagamento foi cobrado 5 vezes)
Uma chave, conferida antes do trabalho ("ingênua")465200315115
Uma chave, reivindicada de forma atômica antes do trabalho5052002000

Duas coisas se destacam. Sem proteção, todos os 200 pagamentos foram cobrados, mas o cliente foi informado de sucesso em apenas 134: 66 pagamentos foram cobrados e relatados como falhas, que é a pior combinação, porque a próxima coisa que um usuário faz é tentar de novo. E a linha do meio mostra que ter uma chave de idempotência não basta. O que basta é tê-la implementada corretamente, e a seção 4 mostra a diferença.

2. O que idempotente significa (e o que não significa)

Uma operação é idempotente se executá-la uma vez ou várias deixa o sistema no mesmo estado. Na aritmética, abs(abs(x)) == abs(x). Em APIs:

O HTTP embute isso na semântica dos seus métodos. A RFC 9110 define GET, HEAD, OPTIONS, PUT e DELETE como idempotentes (e os três primeiros também como seguros, isto é, somente leitura). POST e PATCH não são, e é justamente por isso que esses são os métodos que precisam de ajuda extra. Três esclarecimentos evitam confusões comuns:

A correção mais barata: tornar a operação naturalmente idempotente

Antes de construir qualquer mecanismo, veja se o projeto consegue evitar a necessidade dele:

Operações naturalmente idempotentes são as melhores: sem tabela de chaves, sem expiração, sem ida e volta extra. O resto deste guia é para as operações que não podem ser assim, como cobrar um cartão, criar algo cujo identificador o servidor precisa escolher ou enviar uma mensagem.

3. Chaves de idempotência

Quando uma operação não pode ser naturalmente idempotente, você a torna assim com uma chave: um valor único que identifica uma operação lógica e que o cliente envia em toda tentativa dela. O servidor lembra o que aconteceu com cada chave e, quando a chave aparece de novo, devolve o resultado lembrado em vez de refazer o trabalho.

Diagram: One logical operation, one key, several attempts

As regras do protocolo

  1. Uma chave por operação lógica, reutilizada em cada nova tentativa. Uma chave nova a cada tentativa derrota todo o mecanismo. A chave é criada quando a intenção do usuário é criada (o clique, o rascunho do pedido), não quando a chamada HTTP é feita. Uma biblioteca de cliente que tenta de novo internamente precisa gerar a chave antes da primeira tentativa.
  2. O cliente a gera. Um UUID aleatório (versão 4) tem entropia suficiente. A Stripe sugere UUIDs V4 ou outra string aleatória e permite chaves de até 255 caracteres; o rascunho do IETF também recomenda um UUID. Não use dados sensíveis, como um e-mail, como chave.
  3. O servidor guarda a chave junto com uma impressão digital (fingerprint) da requisição. Se a mesma chave chega com um corpo diferente, isso é um bug do cliente (ou um ataque), e a resposta certa é um erro, não repetir em silêncio o resultado antigo. A Stripe compara os parâmetros e dá erro se forem diferentes; a Amazon Builders' Library diz que o serviço devolve um erro de validação para uma requisição diferente sob o mesmo identificador. A Amazon prefere de propósito um identificador fornecido por quem chama a um hash dos parâmetros, porque duas requisições idênticas podem ser ambas intencionais (dois servidores idênticos lançados de propósito).
  4. Uma chave repetida devolve a resposta guardada. Não um erro como "já existe": isso devolve o problema a quem chamou, que não sabe dizer se a sua requisição criou a coisa. O artigo da AWS faz o mesmo ponto e pede uma resposta semanticamente equivalente à primeira.
  5. Delimite o escopo das chaves. Uma chave é única por chamador (por conta ou por credencial de API), não globalmente. Caso contrário, um cliente pode colidir com a chave de outro, ou reproduzi-la.

As respostas a usar

O rascunho do IETF para o cabeçalho Idempotency-Key (draft-ietf-httpapi-idempotency-key-header, versão 08 quando o li, em 26 de outubro de 2026; ainda é um Internet-Draft e não uma RFC) é uma boa referência para os códigos de status, e combina em espírito com o que a Stripe e outros fazem:

SituaçãoResposta
Chave ausente em um endpoint que a exige400 Bad Request
Chave já vista, terminadaa resposta guardada (mesmo status e corpo), muitas vezes com um cabeçalho que a marca como repetição
Chave já vista, a primeira requisição ainda está rodando409 Conflict (o cliente tenta de novo em instantes)
Chave já vista com um payload diferente422 Unprocessable Content

O rascunho mira POST e PATCH, os métodos que não são idempotentes por definição. Ele trata a chave como uma string de campo estruturado, diz que as chaves não devem ser reutilizadas com um payload diferente e deixa o serviço expirá-las conforme uma política publicada.

A parte A2 do meu experimento mostra isso em ação: a primeira chamada devolve 201 {'charge': 1}, a mesma chamada de novo devolve 200 {'charge': 1} (a mesma cobrança, repetida) e a mesma chave com um corpo diferente devolve 422.

4. Implementando do jeito certo: reivindique primeiro

Esta é a implementação que quase todo mundo escreve primeiro:

def charge(key, request):
    row = db.query("SELECT response FROM idempotency WHERE key = %s", key)
    if row:
        return row.response              # seen it: replay
    result = do_the_work(request)        # slow, maybe 100 ms
    db.execute("INSERT INTO idempotency (key, response) VALUES (%s, %s)", key, result)
    return result

Parece certa e tem uma condição de corrida: duas requisições com a mesma chave que chegam próximas (exatamente o que é uma nova tentativa após um timeout) executam o SELECT, ambas não acham nada, e ambas fazem o trabalho. A primeira ainda não registrou o resultado quando a segunda confere.

Eu medi. Oito threads apresentaram a mesma chave no mesmo instante, 400 vezes:

EstratégiaLinhas para 400 chavesChaves reivindicadas mais de uma vez
SELECT primeiro, depois INSERT, sem restrição3.192400 (todas as chaves)
Restrição de unicidade, INSERT OR IGNORE, vence quem inseriu4000

A correção é parar de conferir e começar a reivindicar: deixe o banco de dados decidir quem vence, usando uma restrição de unicidade, antes de fazer o trabalho.

CREATE TABLE idempotency_keys (
  account_id   bigint      NOT NULL,
  key          text        NOT NULL,
  fingerprint  text        NOT NULL,      -- hash of method, path and body
  state        text        NOT NULL,      -- 'started' | 'done'
  locked_at    timestamptz,               -- when a worker took it (see below)
  status_code  int,
  response     jsonb,
  created_at   timestamptz NOT NULL DEFAULT now(),
  PRIMARY KEY (account_id, key)
);
def charge(account, key, request):
    fp = sha256(canonical(request))
    claimed = db.execute("""
        INSERT INTO idempotency_keys (account_id, key, fingerprint, state, locked_at)
        VALUES (%s, %s, %s, 'started', now())
        ON CONFLICT DO NOTHING""", account, key, fp).rowcount == 1
    if not claimed:                                  # someone has this key
        row = db.query("SELECT * FROM idempotency_keys WHERE account_id=%s AND key=%s", account, key)
        if row.fingerprint != fp:  return 422, {"error": "key used with a different request"}
        if row.state == "started": return 409, {"error": "still being processed"}   # Retry-After
        return row.status_code, row.response                                        # replay
    with db.transaction():                           # the work and the key's result commit together
        result = do_the_work(request)                # writes to the same database
        db.execute("""UPDATE idempotency_keys SET state='done', status_code=201, response=%s
                      WHERE account_id=%s AND key=%s""", result, account, key)
    return 201, result

Três detalhes importam aqui:

A terceira linha do meu experimento é este projeto: 200 pagamentos, 505 requisições enviadas (as extras são novas tentativas e 409s), 200 confirmados, exatamente 200 cobranças.

E se a primeira tentativa travar?

Uma queda entre a reivindicação e a confirmação deixa uma chave presa em started. Se o trabalho estava na mesma transação que a atualização da chave, o trabalho também foi desfeito, então é seguro tentar de novo, mas a chave ainda diz started e uma nova tentativa receberia 409 para sempre. A correção usual é um lease (concessão com prazo): registre locked_at e trate uma linha started mais antiga que algum timeout (maior que a requisição legítima mais lenta) como abandonada, para que uma nova tentativa possa assumi-la. Faça a própria tomada de posse de forma atômica (UPDATE … SET locked_at = now() WHERE key = … AND locked_at < now() - interval '30 seconds', conferindo a contagem de linhas), pela mesma razão da reivindicação.

5. Quando o trabalho não está no seu banco de dados

Cobrar um cartão, enviar um e-mail, chamar a API de um parceiro: são mutações de estado externo, e a transação do seu banco de dados não consegue desfazê-las. O projeto limpo da seção 4 quebra, porque agora há dois sistemas, e uma queda pode acontecer entre eles:

O padrão que se sustenta, descrito em detalhe no artigo de Brandur Leach sobre como implementar chaves de idempotência no estilo da Stripe no Postgres, tem três partes:

  1. Divida a requisição em fases atômicas e guarde um ponto de recuperação (um checkpoint com nome) na linha da chave ao fim de cada fase. Uma nova tentativa lê o ponto de recuperação e retoma em vez de recomeçar.
  2. Confirme antes de sair para fora. A fase que registra "prestes a chamar a rede do cartão" é confirmada primeiro. Como diz Brandur, as fases atômicas devem ser confirmadas com segurança antes de iniciar qualquer mutação de estado externo, para que uma nova tentativa consiga ver que a chamada ao menos foi tentada.
  3. Dê à chamada externa a sua própria chave de idempotência, derivada da sua (por exemplo, "charge-" + key), de modo que, se a sua nova tentativa repetir a chamada, o outro sistema a reconheça e não cobre duas vezes. A maioria dos provedores de pagamento oferece exatamente isso.

Diagram: Recovery points around a foreign call

Se o provedor não tem suporte a idempotência, você não consegue tornar a chamada exatamente-uma-vez por conta própria. Resta escolher um modo de falha (aceitar uma duplicata rara, ou aceitar um "desconhecido" raro e resolvê-lo por reconciliação: perguntar ao outro sistema o que de fato aconteceu, em geral por uma consulta a uma referência que você enviou), que é também o que as equipes financeiras fazem como rede de segurança final, de qualquer jeito.

Mensagens como efeitos colaterais de saída: o outbox

Publicar um evento depois de uma mudança no banco de dados tem o mesmo problema de dois sistemas. O transactional outbox resolve a primeira metade: grave o evento em uma tabela outbox na mesma transação da mudança de estado e deixe um relay separado publicar as linhas no broker. Isso dá publicação pelo menos uma vez, porque o relay pode cair depois de publicar e antes de marcar a linha como enviada. O que significa que os consumidores precisam deduplicar. Esse é o assunto da próxima seção.

6. Consumidores de fila e o inbox

Um broker que garante entrega pelo menos uma vez reentrega a mensagem quando o consumidor não a confirma a tempo ou cai antes de fazê-lo. Então todo consumidor vê duplicatas. A pergunta é em que ponto da ordem de processamento fica a conferência de duplicata.

Simulei 10.000 mensagens "creditar 1" com um consumidor que cai 10% das vezes no pior momento possível, e o broker reentrega até a mensagem ser confirmada:

Estratégia do consumidorSaldo esperadoResultadoVeredito
Sem deduplicação10.00011.098 (+1.098)duplicatas
Aplicar o efeito, depois registrar o id da mensagem (dois commits)10.00011.098 (+1.098)duplicatas: a queda cai entre os dois, então o id nunca foi registrado
Registrar o id da mensagem, depois aplicar o efeito (dois commits)10.0009.011 (−989)atualizações perdidas: o id foi registrado mas o efeito nunca aconteceu, e a reentrega é ignorada
Efeito e id da mensagem em uma transação10.00010.000correto
Naturalmente idempotente (definir um estado por mensagem)10.00010.000correto

A lição é a mesma da seção 4: o que torna a operação "exatamente uma vez" precisa ser atômico com a operação. A forma padrão é uma tabela de inbox (ou de mensagens processadas) com o id da mensagem como chave primária:

BEGIN;
INSERT INTO processed_messages (message_id) VALUES ($1) ON CONFLICT DO NOTHING;  -- 0 rows? already done
-- only if a row was inserted:
UPDATE accounts SET balance = balance + $2 WHERE id = $3;
COMMIT;

Isso funciona quando o efeito vive no mesmo banco de dados que o inbox. Quando o efeito está fora dele, você volta à seção 5: torne o efeito naturalmente idempotente ou passe uma chave derivada ao sistema que o executa.

O que os brokers dão e o que não dão

Leia essas garantias com cuidado: elas protegem o log do próprio broker contra duplicatas causadas pelas suas novas tentativas. Elas não conhecem a sua operação de negócio. Se um usuário clica duas vezes e a sua API publica duas mensagens diferentes, as duas são entregues, e nenhum recurso de broker vai uni-las. A chave de idempotência da sua API (seção 3) é o que pega isso, e o inbox (esta seção) é o que pega a reentrega. Você precisa colocar cada um no lugar a que pertence.

7. Por quanto tempo guardar as chaves, e quanto custam

Uma tabela de deduplicação cresce a cada escrita, então precisa de uma janela de retenção: longa o bastante para cobrir a mais longa nova tentativa realista, curta o bastante para ser financiável.

Quanto custa? Carreguei um milhão de linhas, cada uma com uma chave UUID de 36 caracteres e uma resposta guardada de 120 bytes, no SQLite com um índice de chave primária:

MedidaResultado
Tamanho em disco229 MB, cerca de 229 bytes por chave (tabela e índice)
Tempo de carga10,7 s para um milhão de linhas
Apagar metade delas por data de criação3,8 s

Extrapolando esse tamanho para uma janela de 24 horas:

Escritas por segundoChaves por diaArmazenamento para 24 h
1008,6 milhõescerca de 2 GB
1.00086,4 milhõescerca de 20 GB
10.000864 milhõescerca de 200 GB

Então, em volumes altos, o armazenamento de chaves é um componente de verdade, que precisa ser dimensionado, particionado e expirado: particione a tabela por dia e descarte partições inteiras em vez de rodar deleções grandes, ou guarde as chaves em um armazenamento com expiração embutida (um armazenamento chave-valor com TTL). Se você usa um armazenamento com TTL, como o Redis, para a reivindicação, lembre que a atomicidade "trabalho mais chave" da seção 4 deixa de existir, porque o trabalho e a chave vivem em sistemas diferentes, e você volta à situação da seção 5.

8. Erros comuns

9. O que mencionar em uma entrevista

Resumo rápido

Apêndice: o código do experimento

Python 3.13 e apenas a biblioteca padrão (SQLite 3.45). Rode python3 idem.py para todas as partes ou python3 idem.py a b c d para as escolhidas. Os números do texto vêm dessas execuções; os tempos variam conforme a máquina, mas as contagens das partes B e C e os tamanhos da parte D são estáveis.

"""Experiments for the idempotency guide. Standard library only: a real HTTP server on localhost, SQLite, threads."""
import hashlib, json, os, random, sqlite3, threading, time, uuid
from concurrent.futures import ThreadPoolExecutor
from http.server import BaseHTTPRequestHandler, ThreadingHTTPServer
import urllib.request, urllib.error, socket

DB = "/var/tmp/g3/idem.db"

def conn():
    c = sqlite3.connect(DB, timeout=30, isolation_level=None)   # autocommit: each statement is its own transaction unless we BEGIN
    c.execute("PRAGMA journal_mode=WAL"); c.execute("PRAGMA busy_timeout=30000")
    return c

def reset():
    for f in (DB, DB + "-wal", DB + "-shm"):
        if os.path.exists(f): os.remove(f)
    c = conn()
    c.execute("CREATE TABLE charges (id INTEGER PRIMARY KEY, payment TEXT NOT NULL, amount INTEGER NOT NULL)")
    c.execute("CREATE TABLE idem (key TEXT PRIMARY KEY, fingerprint TEXT NOT NULL, state TEXT NOT NULL, response TEXT)")
    c.close()

MODE = "none"
RECEIVED = 0
LOCK = threading.Lock()

class H(BaseHTTPRequestHandler):
    protocol_version = "HTTP/1.1"
    def log_message(self, *a): pass
    def reply(self, code, body, headers=()):
        raw = json.dumps(body).encode()
        self.send_response(code); self.send_header("Content-Type", "application/json")
        self.send_header("Content-Length", str(len(raw)))
        for k, v in headers: self.send_header(k, v)
        self.end_headers()
        try: self.wfile.write(raw)
        except (BrokenPipeError, ConnectionResetError): pass       # the client gave up; the work was done anyway
    def do_POST(self):
        global RECEIVED
        with LOCK: RECEIVED += 1
        body = self.rfile.read(int(self.headers["Content-Length"]))
        req = json.loads(body); key = self.headers.get("Idempotency-Key")
        fp = hashlib.sha256(body).hexdigest()
        c = conn()
        def do_work():
            time.sleep(random.uniform(0.03, 0.12))                 # talking to the card network
        if MODE == "none" or key is None:
            do_work()
            cur = c.execute("INSERT INTO charges (payment, amount) VALUES (?, ?)", (req["payment"], req["amount"]))
            return self.reply(201, {"charge": cur.lastrowid})
        if MODE == "naive":                                        # check, then act, then remember
            row = c.execute("SELECT response FROM idem WHERE key=?", (key,)).fetchone()
            if row: return self.reply(200, json.loads(row[0]), [("Idempotent-Replayed", "true")])
            do_work()
            cur = c.execute("INSERT INTO charges (payment, amount) VALUES (?, ?)", (req["payment"], req["amount"]))
            resp = {"charge": cur.lastrowid}
            c.execute("INSERT OR REPLACE INTO idem VALUES (?,?,?,?)", (key, fp, "done", json.dumps(resp)))
            return self.reply(201, resp)
        # MODE == "atomic": claim the key first, with a unique constraint deciding who wins
        try:
            c.execute("INSERT INTO idem (key, fingerprint, state) VALUES (?,?,'started')", (key, fp))
        except sqlite3.IntegrityError:
            f2, state, resp = c.execute("SELECT fingerprint, state, response FROM idem WHERE key=?", (key,)).fetchone()
            if f2 != fp: return self.reply(422, {"error": "this key was used with a different request"})
            if state == "started": return self.reply(409, {"error": "still being processed"}, [("Retry-After", "1")])
            return self.reply(200, json.loads(resp), [("Idempotent-Replayed", "true")])
        do_work()
        c.execute("BEGIN IMMEDIATE")                               # the charge and the key's result commit together
        cur = c.execute("INSERT INTO charges (payment, amount) VALUES (?, ?)", (req["payment"], req["amount"]))
        resp = {"charge": cur.lastrowid}
        c.execute("UPDATE idem SET state='done', response=? WHERE key=?", (json.dumps(resp), key))
        c.execute("COMMIT")
        return self.reply(201, resp)

def post(port, payment, key, timeout, body_extra=None):
    data = json.dumps({"payment": payment, "amount": 100, **(body_extra or {})}).encode()
    req = urllib.request.Request(f"http://127.0.0.1:{port}/charge", data=data, method="POST",
                                 headers={"Content-Type": "application/json", **({"Idempotency-Key": key} if key else {})})
    try:
        with urllib.request.urlopen(req, timeout=timeout) as r: return r.status, json.loads(r.read())
    except urllib.error.HTTPError as e: return e.code, json.loads(e.read())
    except (socket.timeout, TimeoutError, urllib.error.URLError, ConnectionError): return None, None

def client(port, payment, use_key, timeout=0.05, attempts=5):
    key = str(uuid.uuid4()) if use_key else None                   # ONE key per payment, reused on every retry
    sent = 0
    for i in range(attempts):
        sent += 1
        st, _ = post(port, payment, key, timeout)
        if st in (200, 201): return sent, True
        time.sleep(0.02 * (i + 1))                                 # timeout or 409: wait a little and retry
    return sent, False

def run_mode(mode, n=200):
    global MODE, RECEIVED
    MODE = mode; RECEIVED = 0; reset(); random.seed(7)
    srv = ThreadingHTTPServer(("127.0.0.1", 0), H); srv.daemon_threads = True
    threading.Thread(target=srv.serve_forever, daemon=True).start()
    port = srv.server_address[1]
    t0 = time.time()
    with ThreadPoolExecutor(20) as ex:
        res = list(ex.map(lambda i: client(port, f"order-{i}", mode != "none"), range(n)))
    time.sleep(0.3)                                                # let abandoned requests finish on the server
    srv.shutdown()
    c = conn()
    charges = c.execute("SELECT COUNT(*) FROM charges").fetchone()[0]
    paid = c.execute("SELECT COUNT(DISTINCT payment) FROM charges").fetchone()[0]
    worst = c.execute("SELECT MAX(n) FROM (SELECT COUNT(*) n FROM charges GROUP BY payment)").fetchone()[0]
    print(f"   {mode:7s} {n} payments, {sum(s for s, _ in res)} requests sent ({RECEIVED} reached the handler), "
          f"{sum(1 for _, ok in res if ok)} acknowledged, {charges} charges for {paid} payments "
          f"-> {charges - paid} extra charges (worst payment charged {worst}x)  [{time.time()-t0:.1f}s]")

def part_a():
    print("A. a real HTTP server, a client with a 50 ms timeout, 5 attempts, 200 payments, 20 at a time")
    for m in ("none", "naive", "atomic"): run_mode(m)

def part_a2():
    print("A2. same key, different body, and the key being retried after completion")
    global MODE; MODE = "atomic"; reset()
    srv = ThreadingHTTPServer(("127.0.0.1", 0), H); srv.daemon_threads = True
    threading.Thread(target=srv.serve_forever, daemon=True).start(); port = srv.server_address[1]
    print("   first call     ", post(port, "order-1", "k1", 2))
    print("   same again     ", post(port, "order-1", "k1", 2))
    print("   other body     ", post(port, "order-1", "k1", 2, {"amount_note": "x"}))
    srv.shutdown()

def part_b(keys=400, threads=8):
    print(f"B. {threads} threads present the same key at the same moment, {keys} keys")
    for variant in ("select-then-insert, no constraint", "unique constraint, INSERT OR IGNORE"):
        for f in (DB, DB + "-wal", DB + "-shm"):
            if os.path.exists(f): os.remove(f)
        c = conn()
        c.execute("CREATE TABLE claims (key TEXT" + (" PRIMARY KEY" if "unique" in variant else "") + ", who INTEGER)"); c.close()
        for k in range(keys):
            bar = threading.Barrier(threads)
            def worker(w):
                cc = conn(); bar.wait()
                if "unique" in variant:
                    cur = cc.execute("INSERT OR IGNORE INTO claims VALUES (?,?)", (f"k{k}", w))
                    won = cur.rowcount == 1
                else:
                    if cc.execute("SELECT 1 FROM claims WHERE key=?", (f"k{k}",)).fetchone() is None:
                        cc.execute("INSERT INTO claims VALUES (?,?)", (f"k{k}", w))
                cc.close()
            ts = [threading.Thread(target=worker, args=(w,)) for w in range(threads)]
            [t.start() for t in ts]; [t.join() for t in ts]
        c = conn()
        rows = c.execute("SELECT COUNT(*) FROM claims").fetchone()[0]
        dup = c.execute("SELECT COUNT(*) FROM (SELECT key FROM claims GROUP BY key HAVING COUNT(*)>1)").fetchone()[0]
        print(f"   {variant:36s}: {rows} rows for {keys} keys; {dup} keys claimed more than once")

def part_c(n=10_000, crash=0.10, seed=3):
    print(f"C. at-least-once delivery of {n} 'credit 1' messages; the consumer crashes {crash:.0%} of the time at the worst moment")
    def run(strategy):
        random.seed(seed)
        for f in (DB, DB + "-wal", DB + "-shm"):
            if os.path.exists(f): os.remove(f)
        c = conn()
        c.execute("CREATE TABLE acct (id INTEGER PRIMARY KEY, balance INTEGER)"); c.execute("INSERT INTO acct VALUES (1, 0)")
        c.execute("CREATE TABLE seen (msg INTEGER PRIMARY KEY)"); c.execute("CREATE TABLE st (msg INTEGER PRIMARY KEY, paid INTEGER)")
        deliveries = 0
        for m in range(n):
            while True:                                            # the broker redelivers until the consumer acks
                deliveries += 1
                boom = random.random() < crash
                if strategy == "effect, then record":              # two separate commits; crash between them
                    if c.execute("SELECT 1 FROM seen WHERE msg=?", (m,)).fetchone(): break
                    c.execute("UPDATE acct SET balance=balance+1 WHERE id=1")
                    if boom: continue
                    c.execute("INSERT INTO seen VALUES (?)", (m,)); break
                if strategy == "record, then effect":              # crash between them loses the effect for good
                    if c.execute("SELECT 1 FROM seen WHERE msg=?", (m,)).fetchone(): break
                    c.execute("INSERT INTO seen VALUES (?)", (m,))
                    if boom: continue
                    c.execute("UPDATE acct SET balance=balance+1 WHERE id=1"); break
                if strategy == "same transaction":
                    c.execute("BEGIN IMMEDIATE")
                    if c.execute("SELECT 1 FROM seen WHERE msg=?", (m,)).fetchone(): c.execute("COMMIT"); break
                    c.execute("UPDATE acct SET balance=balance+1 WHERE id=1"); c.execute("INSERT INTO seen VALUES (?)", (m,))
                    if boom: c.execute("ROLLBACK"); continue       # crash before commit: nothing happened
                    c.execute("COMMIT"); break
                if strategy == "no dedupe at all":
                    c.execute("UPDATE acct SET balance=balance+1 WHERE id=1")
                    if boom: continue
                    break
                if strategy == "set a state (naturally idempotent)":
                    c.execute("INSERT OR REPLACE INTO st VALUES (?, 1)", (m,))
                    if boom: continue
                    break
        bal = c.execute("SELECT balance FROM acct").fetchone()[0]
        if strategy.startswith("set a state"): bal = c.execute("SELECT COUNT(*) FROM st WHERE paid=1").fetchone()[0]
        print(f"   {strategy:38s}: expected {n}, got {bal} ({bal - n:+d}), {deliveries} deliveries")
    for s in ("no dedupe at all", "effect, then record", "record, then effect", "same transaction", "set a state (naturally idempotent)"): run(s)

def part_d(rows=1_000_000):
    print(f"D. what a dedupe table costs: {rows:,} keys (36-character UUID) with a 120-byte stored response")
    for f in (DB, DB + "-wal", DB + "-shm"):
        if os.path.exists(f): os.remove(f)
    c = conn(); c.execute("CREATE TABLE idem (key TEXT PRIMARY KEY, created INTEGER, response TEXT)")
    resp = "x" * 120
    c.execute("BEGIN")
    t = time.time()
    c.executemany("INSERT INTO idem VALUES (?,?,?)", ((str(uuid.UUID(int=random.getrandbits(128), version=4)), i, resp) for i in range(rows)))
    c.execute("COMMIT"); c.execute("PRAGMA wal_checkpoint(TRUNCATE)")
    size = os.path.getsize(DB)
    print(f"   {size/1e6:.0f} MB on disk = {size/rows:.0f} bytes per key (table + primary-key index), loaded in {time.time()-t:.1f}s")
    for rps in (100, 1_000, 10_000):
        per_day = rps * 86_400
        print(f"   at {rps:>6,} writes/s kept for 24 h: {per_day:>13,} keys ~ {per_day * size / rows / 1e9:6.1f} GB")
    # deleting an expired day: a range delete by created
    c.execute("CREATE INDEX idem_created ON idem (created)")
    t = time.time(); c.execute("DELETE FROM idem WHERE created < ?", (rows // 2,)); print(f"   deleting half of them by created: {time.time()-t:.2f}s")

if __name__ == "__main__":
    import sys
    parts = sys.argv[1:] or ["a", "a2", "b", "c", "d"]
    for p in parts: globals()["part_" + p]()

Fontes

Pratique este tema: System Design System Design › Distributed systems

Mais guias