Como o GitLab reduziu o tempo de backup de repositórios de 48 horas para 41 minutos

 (about.gitlab.com)
5 pontos por GN⁺ 2025-06-07 | 1 comentários | Compartilhar no WhatsApp
  • O GitLab identificou e corrigiu um problema de lentidão nos backups de repositórios de grande porte
  • A causa principal era a complexidade O(N²) de uma função do Git com 15 anos de existência, e a otimização do algoritmo melhorou drasticamente o desempenho
  • Como resultado da otimização, o tempo de backup do maior repositório caiu de 48 horas para 41 minutos
  • O método aprimorado oferece eficiência de recursos e confiabilidade, além de impactar positivamente outras ferramentas baseadas em Git e a comunidade
  • A partir da versão 18.0 do GitLab, todos os usuários poderão aproveitar esses benefícios sem configuração adicional

A importância e os desafios do backup de repositórios

  • O backup de repositórios é um elemento central de uma estratégia de recuperação de desastres
  • À medida que o tamanho dos repositórios cresce, também aumenta a complexidade de um processo de backup confiável
  • O repositório interno em Rails do GitLab levava 48 horas para ser copiado, o que criava um dilema entre a frequência de backup e o desempenho do sistema
  • Em repositórios de grande escala, surgem diversos problemas como tempo, recursos, risco de falha e condições de corrida
    • Isso levava cada organização a adotar estratégias inconsistentes, como dificuldade para agendar backups, dependência de ferramentas externas ou redução da frequência dos backups

Análise do gargalo de desempenho e identificação da causa

  • O recurso de backup do GitLab usa o comando git bundle create para gerar snapshots dos repositórios
  • No processo de implementação desse comando, surgiu um gargalo de desempenho à medida que o número de references aumentava
  • Em repositórios grandes com milhões de references, o backup podia levar mais de 48 horas

Análise da causa

  • O gargalo foi identificado por meio de análise com Flame Graph durante a execução do comando
  • Com 10.000 references, cerca de 80% do tempo de execução era consumido pela função object_array_remove_duplicates()
  • Essa função foi introduzida em 2009 por meio deste commit para lidar com references duplicadas
    • Ao usar git bundle create, ela evitava problemas quando references duplicadas eram incluídas
    • Porém, a detecção de duplicatas era feita com loops for aninhados, gerando complexidade O(N²)
    • Quanto maior o número de references, mais severo se tornava o gargalo

Da complexidade O(N²) para um mapeamento eficiente

  • O GitLab contribuiu com um patch para o Git que substitui os loops aninhados por uma abordagem com estrutura de dados de mapa
    • Cada reference é adicionada ao mapa, removendo duplicatas automaticamente e processando os dados com mais eficiência
  • Essa mudança melhorou drasticamente o desempenho de git bundle create e trouxe escalabilidade para ambientes com grande volume de references
  • Nos benchmarks, foi observada uma melhora de desempenho de mais de 6 vezes com 100 mil references

Redução drástica no tempo de backup e seus efeitos

  • O tempo máximo de backup de repositório caiu de 48 horas para 41 minutos (cerca de 1,4% do valor anterior)
  • Passou a ser possível oferecer desempenho consistente independentemente do tamanho do repositório
  • Houve benefícios adicionais, como redução da carga no servidor e melhoria de desempenho em comandos Git relacionados a backup
  • O patch foi aplicado ao upstream do Git, e o GitLab o adotou imediatamente para que os clientes tivessem acesso rápido à melhoria

Mudanças práticas para clientes do GitLab

  • Grandes clientes corporativos agora podem executar backups noturnos contínuos sem conflito com o fluxo de trabalho de desenvolvimento
  • Com a redução do objetivo de ponto de recuperação (RPO), o risco de perda de dados em situações de desastre diminuiu bastante
  • Também houve redução no consumo de recursos, no tempo de manutenção e nos custos operacionais, incluindo custos de nuvem
  • Mesmo com o crescimento do repositório, já não é mais necessário escolher entre frequência de backup e desempenho do sistema
  • Agora, todos os usuários do GitLab podem obter esses benefícios sem mudar a configuração

Próximos passos e significado

  • Essa melhoria faz parte do esforço contínuo do GitLab para construir uma infraestrutura Git corporativa altamente escalável
  • As mudanças contribuídas pelo GitLab também foram incorporadas ao projeto upstream do Git, gerando impacto positivo em todo o setor e na comunidade open source
  • Esse tipo de trabalho de infraestrutura está se tornando um modelo para outras melhorias centrais de desempenho

Uma visão mais aprofundada da abordagem de desempenho do GitLab pode ser conferida no evento virtual de lançamento do GitLab 18

Leituras relacionadas

1 comentários

 
GN⁺ 2025-06-07
Comentários do Hacker News

  • Compartilhamento da informação de que o código de melhoria de desempenho que o GitLab contribuiu ao Git está previsto para ser lançado na v2.50.0 link do commit relacionado

  • Com base na experiência direta, destaca-se que remover operações n^2 do código que se escreve sempre foi a escolha correta. Há surpresa com o fato de que, mesmo sem criar um algoritmo especial, o problema aparece facilmente até com valores de n muito pequenos

    • Citação da primeira lei da computação de Bruce Dawson: O(n^2) é o ponto em que surgem os piores problemas de escalabilidade. Em produção, parece suficientemente rápido, mas depois do deploy causa degradação de desempenho fatal link do texto relacionado

    • Compartilhamento de experiência pessoal de já ter visto várias vezes situações em que a complexidade de tempo O(N^2) parece rápida nos testes, mas explode gravemente em produção

    • Na experiência da pessoa, na maioria dos problemas (80~90%), se é necessário um algoritmo complexo isso é sinal de que o próprio modelo de dados não está correto. Acredita-se que algoritmos complexos só sejam essencialmente necessários em alguns casos especiais, como compiladores, internals de banco de dados e planejamento de rotas

    • Menciona como exceção apenas casos limitados a hardware de pequena escala com n menor que 10 (como interfaces CAN). Se n puder aumentar sem trocar o hardware, é obrigatório evitar operações n^2, e recomenda-se limitar isso no design ou detectar antes para reconhecer a necessidade de redesenho

    • A pessoa relata a frustração de ainda não ter encontrado uma solução para um gargalo causado por uma operação n^3, que já aparece com apenas 10.000 elementos

  • Avalia-se como uma descoberta interessante, mas também se compartilha a frustração de que o texto teria se comunicado de forma igualmente eficaz mesmo com apenas 1/10 do tamanho. Ainda assim, há o lado positivo de que, por não ser conteúdo em vídeo, foi fácil de escanear rapidamente

    • Para quem ainda não leu o artigo, fica a dica de que, para captar o essencial com mais eficiência, basta ler até a parte após o flame graph e parar antes da menção ao backport

    • Impressão de que o estilo do artigo inteiro era tão longo que parecia ter sido gerado por um LLM (modelo de linguagem de grande porte), e isso foi o que mais ficou na memória

    • Acha que não haveria problema se o artigo fosse ainda mais longo, e continua em dúvida sobre por que o bundle de backup foi feito com dois refs

  • Considera-se muito tempo tanto as 48 horas para comprimir a pasta git (vários GB) quanto até mesmo os 41 minutos. Levanta-se a dúvida sobre por que não simplesmente fazer um snapshot/archive do repo Git inteiro, em vez de insistir em usar git bundle. Pergunta-se que vantagem o git bundle teria em relação a backups frequentes com ZFS

    • No FAQ oficial do git, menciona-se que esse tipo de abordagem é arriscado porque contorna os procedimentos normais de verificação de integridade do Git. Nesses casos, recomenda-se git fsck para validar a integridade da coleção. Em uso pessoal, apenas Syncthing e snapshots de Btrfs já seriam rápidos e confiáveis o suficiente. documentação relacionada

    • Menciona-se que há limitações para fazer backup off-site de snapshots do ZFS para uma base não-ZFS como S3. Como um recurso pouco conhecido do git bundle, é possível especificar uma localização em git clone --bundle-uri, e se o servidor informar ao cliente onde está o bundle, o cliente pode baixá-lo, expandi-lo rapidamente e receber do servidor apenas as atualizações delta, reduzindo bastante a carga de clonar repos grandes

    • No fim, parece que apenas adicionaram cache onde era necessário. Normalmente, como um repo Git é distribuído por natureza, fica a dúvida se não bastaria espelhar em outro repositório e gerenciar com ferramentas de snapshot/backup de filesystem. O ponto principal é que a informação importante de controle de versão em si precisa estar distribuída

  • Não há muita experiência com backup de Git, mas transmite-se a curiosidade sobre por que surgiria uma race condition ao criar um backup diretamente de um repo local

  • Se isso já é tão trabalhoso por causa do protocolo de dados de camada superior, questiona-se por que não usar snapshots em nível de bloco. O fato de o Git não ter algo como WAL (Write Ahead Logging) é um obstáculo, mas no SQLite já se usa em ambiente real uma estratégia de snapshot de bloco de forma simples apenas com a adição do modo WAL. Acredita-se que, se uma arquitetura assim fosse aplicada ao Git, seria possível uma estratégia de backup muito mais estável

    • Há concordância com o problema causado pelo fato de o Git não ter um mecanismo semelhante a WAL, e compartilha-se a experiência de um problema crítico em que confiar apenas em snapshots fez com que o repositório viesse quebrado na restauração. Dá para recuperar, mas é uma dor de cabeça enorme

    • Compartilha-se a dica de que recentemente surgiu uma solução melhor no SQLite: sqlite3_rsync

    • Explica-se a perspectiva do GitLab: não é apenas um serviço gerenciado simples, mas um produto que pode ser instalado pelo próprio usuário em vários ambientes, então cada usuário tem filesystem, suporte a snapshot e condições de sistema operacional diferentes. Ou seja, o GitLab quer um sistema de backup independente que funcione de forma universal em todos os ambientes

  • Ao ver a expressão “reduziu exponencialmente o tempo de backup com uma mudança de algoritmo”, surge a dúvida se isso significaria ter passado de O(n^2) para O(n^2/2^n). Supõe-se que obviamente não seja isso

    • Explica-se que a complexidade algorítmica da função modificada ficou na prática 6 vezes mais rápida, e que em outros contextos de uso o tempo operacional total caiu para 1%, então, nesse caso, “melhoria exponencial” pode ser uma forma de marketing aceitável. A definição exata da complexidade não teria tanta importância

    • Esclarece-se que, na conversa do dia a dia, “exponential” não é usado num sentido matemático rigoroso, mas como metáfora para “melhorou muito”

    • Na interpretação da pessoa, pode ser que n tenha sido reduzido a log(n). Menciona-se uma situação em que a complexidade muda de n^2 para nlogn, de modo semelhante ao contexto em que se costuma dizer que a transformada quântica de Fourier é exponencialmente mais rápida que a DFT tradicional

    • Substituir um algoritmo n^2 por um método de consulta log(n) realmente seria uma melhora exponencial em velocidade, mas na prática muitas vezes chega-se até O(1), como em buscas com hashmap, sendo ainda mais rápido

    • Considera-se que toda essa discussão em si é uma implicância improdutiva

  • Opinião de que escrever em C não garante desempenho elevado por si só, e que estruturas de dados e algoritmos vêm antes disso; este seria um bom exemplo disso

    • Como em C é muito difícil implementar containers adequados, esse tipo de problema de performance acontece com mais frequência. Em C++ ou Rust, graças a estruturas embutidas como unordered_set/HashSet, os desenvolvedores tendem naturalmente a otimizar em vez de simplesmente deixar passar com um for loop. Analisa-se que, neste caso, o Git também tem um string set, mas como não é algo padronizado, é possível que o autor original nem soubesse da existência

  • Menciona-se a lição de que é preciso equilíbrio entre otimização prematura e otimização antecipatória. Em geral, costuma-se alertar contra otimizações apressadas, mas propõe-se a regra de que, em funções chamadas com altíssima frequência, vale a pena aplicar de antemão otimizações óbvias e fáceis

    • Supõe-se que, se a linguagem-fonte usada na implementação tivesse um set-of-strings embutido, o desenvolvedor original teria aplicado esse tipo de otimização com facilidade. No fim, considera-se que esse problema vem de uma limitação estrutural de linguagens pobres em containers, como C

  • Compartilhamento direto do link do commit relacionado (detalhes da melhoria de algoritmo) link do commit relacionado

    • Informa-se que, graças a isso, foi possível encontrar a submission relacionada e a thread de discussão na kernel mailing list link da discussão relacionada