Rinha de Backend - 2024/Q1

Posted on in c++, docker, firebird, postgresql, web, rinha

Hoje, dia 10/03/2024, se encerra o prazo para submissão de projetos para a Rinha de Backend - 2024/Q1, que é a segunda edição da Rinha de Backend. Resumindo, era preciso entregar um projeto que simule um serviço bancário com extrato e criação de transações concorrentemente, onde as contas nunca podem ficar com saldo negativo abaixo do limite de cada cliente. Além disso, era necessário rodar em docker, com um load balancer distribuindo a carga para no mínimo dois serviços de API, sendo que todos os serviços juntos poderiam usar no máximo 1,5 unidades de CPU e 550MB de memória.

Não participei da primeira edição em 2023 pois só fiquei sabendo depois de encerrada.

Após essa primeira edição da Rinha de Backend, houve uma Rinha de Compiladores (e interpretadores) onde consegui participar e meu projeto ficou em 9º no ranking.

Um fato interessante das rinhas é que o critério do ranking final não é muito claro antecipadamente. O objetivo é se divertir e aprender.

Voltando a Rinha de Backend 2024/Q1, outro ponto interessante é que para o ranking, os testes são executados nessa máquina. Eu fiz meus testes em duas máquinas diferentes, um desktop Ryzen 9 com 24 cores e um notebook Core i7 de 7ª geração com 4 cores. No Ryzen 9 qualquer coisa rodava muito rápido, mesmo com a limitação de CPU no docker. Algumas técnicas que melhoravam o desempenho no desktop, pioravam no notebook. Nesses casos priorizei as técnicas que melhoravam no notebook.

Submeti 3 projetos construídos com uma mesma stack base:

  • C++20 como linguagem de programação
  • mongoose como lib http
  • vcpkg como gerenciador de pacotes
  • haproxy como load balancer

Nos projetos usei diferentes bancos de dados e algumas alterações no código:

PostgreSQL

A grande maioria dos (até então) 677 projetos usou o PostgreSQL como banco de dados. Resolvei fazer uma versão com ele e no ranking provisório esse projeto ficou com um p75 de 1ms.

Ficou um projeto com um modelo de dados bastante tradicional:

create unlogged table account (
    id integer primary key not null,
    balance integer not null,
    overdraft integer not null
);

create unlogged table transaction (
    id serial not null,
    account_id integer not null,
    val integer not null,
    description varchar(10) not null,
    datetime timestamp with time zone not null
);

create index idx_transaction_account_id_id_desc on transaction (
    account_id,
    id desc
);

Usei 0,5 CPU e 390MB para o container do PostgreSQL, 0,2 CPU e 50MB para cada um dos dois containers de API e 0,6 CPU e 60MB para o haproxy.

Em cada instância da API usei um thread pool de 8 workers HTTP e um connection pool de 8 conexões para o banco de dados. Cada request que chega pela mongoose é enviado para o thread pool e respondido de forma assíncrona.

A conexão com o banco foi realizada usando a libpqxx por meio de Unix Domain Socket, que se mostrou mais rápido do que TCP/IP.

Deixei no projeto duas views que mostram possíveis inconsistências nos dados e em nenhum teste isso aconteceu.

create or replace view account_check
as
select a.*,
       t.*
    from account a
    left join (
        select account_id,
               sum(val) trans_balance
            from transaction
            group by account_id
    ) t
        on t.account_id = a.id
    where a.balance < a.overdraft or
          coalesce(t.trans_balance, 0) <> a.balance;

create or replace view transaction_check
as
select t.*
    from (
        select id,
               account_id,
               sum(val) over (partition by account_id order by id) balance
            from transaction
    ) t
    join account a
        on a.id = t.account_id
    where t.balance < a.overdraft
    order by t.account_id, t.id;

Firebird

A versão com o Firebird também ficou com um p75 de 1ms, mas pra conseguir isso tive que inovar no modelo de dados, pois o MVCC do Firebird não se comportou tão bem com múltiplos updates concorrentes nos mesmos registros para atualizar o saldo. Interessante é que esse problema de performance só aconteceu no notebook. No desktop, mesmo usando um modelo tradicional o desempenho foi bom.

Assim ficou o modelo:

create table transaction (
    account_id integer not null,
    seq integer not null,
    balance integer /*not null*/,
    overdraft integer /*not null*/,
    val integer /*not null*/,
    description varchar(10) /*not null*/,
    datetime timestamp with time zone /*not null*/,
    constraint transaction_pk primary key (account_id, seq) using desc index transaction_pk_desc
);

Com uma stored procedure PSQL usando vários recursos interessantes do Firebird, foi possível resolver todos os problemas de concorrência dessa forma:

create or alter procedure post_transaction(
    account_id integer,
    val integer,
    description varchar(10)
) returns (
    status_code integer,
    balance integer,
    overdraft integer
)
as
begin
    while (true) do
    begin
        /*
        If this does not raise exception, it means one of these:
        - the transaction succeded (status_code = 200)
        - bankrupt (only when val < 0)
        - account does not exists
        */
        in autonomous transaction do
            insert into transaction (account_id, seq, balance, overdraft, val, description, datetime)
                select :account_id,
                       seq + 1,
                       new_balance,
                       overdraft,
                       :val,
                       :description,
                       'now'   -- with current_timestamp it will be fixed during the whole execution
                    from (
                        select seq,
                               balance + :val new_balance,
                               overdraft
                            from transaction
                            where account_id = :account_id
                            order by seq desc
                            rows 1
                    )
                    where new_balance >= overdraft
                returning 200, balance, overdraft
                into status_code, balance, overdraft;

        if (status_code is null) then
            status_code =
                case
                    when val < 0 then
                        coalesce(
                            (select 422  -- account exists, so it is bankrupt
                                 from transaction
                                 where account_id = :account_id and
                                       seq = 0
                            ),
                            404  -- account does not exists
                        )
                    else 404  -- account does not exists
                end;

        exit;
    when gdscode unique_key_violation do
        /*
        Here we know the account exist.
        If the insert do not raise exception in the next round, it will overwrite status_code with 200
        or it will leave the status code as 422 meaning the account is bankrupt.
        */
        status_code = 422;
    end
end

Como a tabela transaction tem uma primary key em (account_id, seq) e a busca da próxima sequencia é feita incrementando o valor da última sequencia (comitada) da conta, quando mais de uma tentativa de inserção de transação para uma conta é feita simultaneamente, só a primeira passa e as outras geram um erro de violação de chave primária.

Quando esse erro acontece, o loop é reiniciado e uma nova transação é iniciada, podendo ler os últimos dados comitados pelas transações concorrentes já finalizadas.

Usei 0,5 CPU e 390MB para o container do Firebird, 0,2 CPU e 50MB para cada um dos dois containers de API e 0,6 CPU e 60MB para o haproxy. Idêntico ao projeto com PostgreSQL.

Mas as similaridades param aí. O Firebird ainda não tem conexão via Unix Domain Socket, então usei TCP/IP com a API OO nativa do Firebird.

Usei 8 workers HTTP em cada container API de forma bastante diferente do que fiz com o projeto do PostgreSQL. Todos os threads iniciam conexões de escuta na mesma porta (usando a flag SO_REUSEPORT). Cada thread possui uma conexão dedicada ao Firebird usando TLS (thread_local). Dessa forma foi possível usar a mongoose de forma síncrona.

Deixei no projeto uma view que mostra possíveis inconsistências nos dados e em nenhum teste isso aconteceu.

create or alter view transaction_check
as
select *
    from (
        select t.*,
               sum(val) over (partition by account_id order by seq) calc_balance
            from transaction t
    )
    where balance < overdraft or
          calc_balance <> balance
    order by account_id, seq;

LMDB

Queria fazer uma versão com um banco de dados chave/valor que conseguisse compartilhar o banco de dados em diferentes processos sem necessidade de usar um container específico. Descobri o LMDB, ou Lightning Memory-Mapped Database.

O LMDB mapeia um arquivo de disco em memória (mmap) e pode ser usado simultaneamente por diferentes processos.

A versão com o LMDB ficou com um p75 de 0ms.

Defini o modelo com uma chave com o código da conta e os dados como abaixo:

struct __attribute__((packed)) TransactionData
{
	uint8_t reverseSeq[4];
	int64_t dateTime;
	std::array<char, 11> description;
	int value;
	int balance;
	int overdraft;
};

Precisei adicionar uma chave reverseSeq que é uma auto-decrement para os registros ficarem ordenados iniciando pelos últimos inseridos. Apesar do LMDB ser transacional, para gerar essa chave de forma única, criei um mutex compartilhado (boost::interprocess::named_mutex) entre os dois containers de API. Pra isso foi necessário colocá-los no mesmo pid namespace do docker.

Usei 0,4 CPU e 150MB para cada um dos dois containers de API e 0,7 CPU e 150MB para o haproxy. A mongoose foi usada como no Firebird, com SO_REUSEPORT. O LMDB permite (e requer) que apenas uma conexão seja feita para cada banco de dados em um mesmo processo.

Uma técnica interessante

Cheguei a testar uma técnica interessante que mostrou ter um desempenho muito bom, mas com alguns picos que atrapalhavam. Não debuguei o problema e não coloquei em nenhum dos projetos.

A técnica foi criar um load balancer próprio com a mongoose e repassar os sockets abertos para as APIs responderem diretamente aos clientes, sem rotear as respostas usando o load balancer. Essa técnica é chamada socket takeover e foi detalhada aqui, embora com motivação diferente.

A ideia inicial

Inicialmente minha ideia era desenvolver a API usando GRPC e colocar o envoy como load balancer fazendo a conversão de HTTP para GRPC. Isso até foi possível usando esse filtro, com algumas dificuldades de conversão de respostas GRPC para status code HTTP nos casos de erros, onde foi necessário usar scrips LUA. Porém o desempenho não foi bom.

Curiosidades

  • A mongoose não suporta o uso de SO_REUSEPORT mas se tiver um #define com o nome SO_EXCLUSIVEADDRUSE ela seta essa flag nos sockets. Como esse define não existe no Linux, criei um triplet vcpkg e um toolchain cmake para passar SO_REUSEPORT no lugar:
set(CMAKE_C_FLAGS "-DSO_EXCLUSIVEADDRUSE=SO_REUSEPORT")

  • Usei o haproxy no modo tcp para ter o mínimo overhead possível

  • Usei o gerenciador de memória mimalloc da Microsoft para economizar alguns ciclos de CPU

  • A função mg_match da mongoose foi mais rápida do que deixar uma regex C++ pré-compilada

  • std::format_to_n foi mais rápida que sprintf

  • g++ (com libstdc++) foi mais rapido que clang++ com libstdc++ e libc++

  • Usando a experiência que adquiriram na rinha de 2023, usei network_mode: host em todos os containers, embora nas minhas máquinas não tenha tido vantagens

← Back to home