Sucesso absurdo
(marginalia.nu)- O Marginalia Search reduziu recentemente os requisitos de RAM pela metade e diminuiu muito a carga operacional de ter que derrubar o mecanismo de busca durante upgrades
- A falha apareceu no processo de troca de índice após a versão mais recente, e a estrutura que apagava o banco de dados de URLs durante upgrades levou a um período longo offline
- O armazenamento de URLs deixou de ser centrado em uma enorme tabela e índices no MariaDB e passou a usar um único banco de dados SQLite com uma estrutura de IDs de URL de 64 bits gerados pelo processo
- A criação do índice invertido abandonou o lexicon para IDs densos de termos e as grandes gravações aleatórias, passando a criar pequenos preindex e depois mesclá-los
- A nova estrutura permite backups em arquivo que podem ser restaurados em poucas horas mesmo após uma implantação ruim, além de facilitar o reaproveitamento de resultados de processamento de grandes conjuntos de dados que quase não mudam, como a Wikipedia
Em uma semana, as condições de operação do mecanismo de busca mudaram
- O Marginalia Search reduziu vários problemas de longo prazo ao mesmo tempo com uma semana de código
- Os requisitos de RAM do mecanismo de busca caíram pela metade
- Desapareceu a necessidade de colocar o sistema offline durante upgrades
- Foi removido o limite rígido para a quantidade de documentos indexáveis
- O limite flexível para a quantidade de palavras-chave que podem entrar no corpus aumentou 4 vezes
- O objetivo de longo prazo era manter o sistema operável mesmo em hardware de baixo desempenho, e esta mudança foi uma melhora ainda maior do que a anterior, quando uma máquina de desenvolvimento com 32GB de RAM já parecia folgada
A antiga estrutura de upgrade que ampliou a falha
- O Marginalia Search ficou offline por quase uma semana por causa de problemas na versão mais recente
- A causa direta foi uma cadeia de problemas de escalabilidade relativamente pequenos, mas foi preciso reiniciar várias vezes um processo que normalmente leva 1 dia, ou 2 a 3 dias quando há problemas
- A maior parte dos reinícios aconteceu por falta de RAM
- O motivo de a falha ter ficado tão visível para os usuários foi que o sistema precisava ser colocado offline durante a troca de índice
- Na estrutura antiga, o banco de dados de URLs era apagado durante o upgrade, e o trabalho de inserir e atualizar rapidamente linhas em uma tabela com quase 1 bilhão de registros se tornava um gargalo
- O processo de carregar novos dados consumia muita RAM
- Era difícil executá-lo ao mesmo tempo que o serviço de indexação, que consumia RAM de forma semelhante
- A chave primária era um inteiro de 32 bits, então havia um limite difícil para ultrapassar 2 bilhões
Redesenho do banco de dados de URLs
- O banco de dados de URLs era um componente antigo do mecanismo de busca, e decisões iniciais de projeto deixaram de se encaixar na estrutura atual do sistema
- No núcleo havia duas tabelas que só eram escritas ao carregar um novo índice e só eram lidas por consultas de chave primária
- A tabela de URL atribuía um ID numérico único a cada URL
- A tabela PAGE_DATA guardava informações como título e descrição dos links indexados
- Havia um índice adicional para manter a unicidade de caminhos dentro do domínio, mas ele era muito grande para a função que cumpria
- A nova estrutura junta as duas tabelas em um único banco de dados SQLite de tabela única, faz o processo de carregamento gerar os IDs únicos e trata a lista de URLs não indexadas em uma tabela separada
- Usar MariaDB e SQLite juntos não é uma escolha convencional, mas os dois armazenamentos atendem a necessidades diferentes
- O sistema precisa de uma visão de mundo persistente relativamente pequena
- Ao mesmo tempo, precisa conseguir trocar estados de escala em terabytes como se fossem plug and play
- As tabelas DOCUMENT e DOMAIN ficam relacionadas de forma frouxa entre bancos diferentes, mas joins reais não são necessários
- Em caso de desastre, partes importantes da tabela DOMAIN podem ser reconstruídas a partir da tabela DOCUMENT
Criando IDs de URL de 64 bits sem índice
- A antiga tabela de URL usava IDs de 32 bits, e a proximidade do overflow inteiro era um problema de escalabilidade conhecido
- Um dos motivos para apagar o banco de dados de URLs era justamente evitar que a coluna de ID estourasse
- Um contador simples não conseguiria lidar com repetição de URLs, e também era preciso evitar manter em memória uma coleção de todas as URLs já vistas
- No novo método, o banco de dados não atribui mais os IDs; os IDs de 64 bits são montados diretamente
- Os 26 bits inferiores são usados como número de sequência
- Os bits de 26 a 56 são usados como ID de documento
- Os bits mais altos ficam reservados para truques de ordenação do índice
- Esse arranjo permite cerca de 67 milhões de documentos por domínio
- Isso equivale a cerca de 10 vezes o tamanho da Wikipedia em inglês
- Até 2 bilhões de domínios são permitidos
- Isso é quase 100 vezes o número de domínios aos quais o Marginalia já viu referências em qualquer lugar da web
- A responsabilidade pela integridade dos dados sai do banco de dados e vai para o processo que gera os dados, mas o custo de impor isso ali é muito menor
Como o redesenho de URL reduziu a pressão de memória
- Ao eliminar os enormes índices e a grande tabela que misturava dados de URL quentes e frios, o servidor MariaDB deixou de precisar de 36GB de RAM
- Os dados quentes que restam no MariaDB ficam em no máximo algumas centenas de MB, e é provável que o servidor não precise de mais de 2GB de RAM alocados
- Os dados em SQLite ainda precisam de um índice de chave primária, mas a parte realmente quente do índice deve ficar abaixo de 1GB
- A quantidade de dados sendo indexada cai em uma ordem de grandeza
- O alvo do índice é um único
longde 64 bits - Não há restrição adicional de unicidade
- Como a saída do loader virou um conjunto de arquivos, ficou mais fácil criar backups automáticos
- Mesmo que ocorra uma implantação ruim, agora é possível recuperar em poucas horas em vez de quase uma semana como antes
Gargalo na criação do índice invertido
- O loader produz o banco de dados de URLs e um journal centrado em documentos no formato
(document, words[]), mas a busca precisa de um índice transposto no formato(word, documents[]) - O método antigo usava um lexicon para mapear strings de palavras-chave para IDs densos de termos
- A primeira palavra recebia o ID 0, a seguinte recebia o ID 1
- As strings eram mapeadas para
longpor hash de 64 bits - Na prática, a estrutura era um mapa hash aberto de long para int
- Essa estrutura enche facilmente em grande escala
- O Java não permite arrays com mais de 2 bilhões de elementos
- A implementação usada já trava na faixa de 1 bilhão
- Com 1 bilhão de entradas, consome 12GB de RAM
- O serviço de índice em produção usa 60GB de RAM, e a maior parte está fora do heap
- Também era um problema o fato de ser difícil usar CompressedOOPs quando o tamanho on-heap passa de 32GB
A amplificação de gravação no algoritmo antigo de índice invertido
- O algoritmo antigo encontrava o maior word ID, criava um array
countsdesse tamanho, calculava a posição dos documentos por palavra e gravava os dados de documentos em um arquivo mapeado em memória - Esse método exigia o lexicon por assumir que o domínio dos word IDs seria densamente preenchido
- O gargalo maior era gravar cerca de 1TB de dados em um arquivo mapeado em memória quase totalmente em ordem aleatória
- SSDs lidam bem com acesso aleatório em leitura, mas pequenas gravações sofrem com write amplification
- Mesmo para atualizar um único byte no disco, o SSD precisa apagar e regravar a página inteira
- Há cache para agrupar gravações adjacentes, mas isso não ajuda em gravações aleatórias em escala de terabytes
- Ao escrever 1TB, a unidade acaba escrevendo cerca de 0,5PB
- Como mitigação temporária, existia o
RandomWriteFunnel- Ele dividia as gravações primeiro em pequenos buckets de arquivo
- Depois escrevia os arquivos grandes em sequência
- Era melhor do que o método original, mas ainda muito lento
Criando pequenos preindex e mesclando depois
- A nova criação do índice invertido passa a gerar vários índices pequenos, em que todos os dados cabem na memória, e depois mesclá-los
- Mesclar listas ordenadas é rápido e funciona até para discos rígidos mecânicos
- Nesse método, o lexicon deixa de ser necessário
- O hash de string de 64 bits pode ser usado diretamente como term ID
- Os problemas iniciais estavam no fato de a entrada ser compactada e na forma de mesclar os índices
- Em vez de ler rapidamente partes da entrada compactada, são criados vários arquivos pequenos e lidos um por um
- Em vez de mesclar os índices depois de criá-los, os dados são mesclados antes da criação do índice
- A nova abstração
preindexé composta por um array de IDs de palavras, um array de contagens e um array de dados de documentos - Como a entrada é pequena, a maior parte do preindex pode ser criada em RAM, gravada em disco durante a geração e então usada para montar o preindex final em uma etapa posterior de mesclagem
- O preindex final é então transformado em índice invertido, como antes, com uma tabela de words e um índice btree estático adicionado a cada bloco de documento; esse processo é relativamente rápido
Mudanças na operação e no reaproveitamento de dados
- A remoção do lexicon reduziu a necessidade de RAM, e a nova criação do índice invertido é mais rápida do que o algoritmo antigo
- O lexicon antigo criava um dialeto separado para cada lote de dados processado
- A mesma palavra podia receber um ID em uma execução e outro diferente em outra
- Por isso, era necessário processar todos os dados ao mesmo tempo
- Ao abandonar o lexicon, passou a ser possível mesclar lotes de dados diferentes
- Isso facilita reaproveitar resultados de processamento de dados grandes e raramente alterados, como a Wikipedia, e combiná-los com dados de índice que mudam com mais frequência
- Esta mudança reduziu quase todos os problemas conhecidos de escalabilidade e inconvenientes operacionais, além de colocar o sistema em um estado em que é possível examinar mais efeitos colaterais
2 comentários
Sucesso absurdo
Opiniões no Hacker News
Dá uma satisfação enorme ver casos de sucesso como esse em projetos que vão na direção exatamente oposta ao resto do mundo
Dá vontade de chamar isso de Engildification; precisamos de mais coisas assim
Também gostei do texto Sleeping At Night e, junto com o recente “Lie Still in Bed”, parece uma opção muito simples para tentar corrigir problemas de treinamento do sono
No caso do mecanismo de busca Marginalia, o autor passou recentemente a trabalhar nele em tempo integral e, pelo que sei, o tamanho da equipe é de 1 pessoa, então está o mais longe possível do risco de enshittification. É justamente nessa escala que surgem joias, e criatividade, originalidade e visão brilham
Este comentário foi patrocinado pelo grupo “largue o trabalho de escritório e trabalhe de forma independente”
Reduziu o consumo de recursos pela metade, ficou mais produtivo do que antes em uma tela menor e dorme como uma pedra à noite
Link para quem se interessar: https://www.marginalia.nu/log/86-sleep/
Para referência, o Kagi, mecanismo de busca pago que você talvez já tenha visto no Hacker News, usa o Marginalia como uma de suas fontes de dados
https://help.kagi.com/kagi/search-details/search-sources.htm...
Ao usar a lente “non-commercial”, esses resultados são priorizados junto com resultados do próprio índice do Kagi e de algumas fontes independentes
Ao ler este texto, fiquei pensando se os seres humanos não são seres que têm dificuldade para criar algo excelente sem restrições artificiais
A razão de o Marginalia ser absurdamente eficiente é que Victor limita deliberadamente o hardware de execução e a quantidade de memória
Se simplesmente acrescentasse mais 32 GiB, provavelmente funcionaria por um tempo, mas o design ineficiente continuaria lá, e mais tarde o mesmo problema poderia estourar em um estado mais complexo, tornando-o mais difícil de corrigir
Se essa hipótese estiver certa, ela também explica por que o software de hoje é inchado, lento e cheio de bugs. Como softwares individuais quase nunca chegam ao limite de forma isolada, cada peça pode ser ineficiente, mas continua ultrapassando o ponto problemático com M2 Pro modernos e conexões na casa dos GiB
A conclusão pode ser que impor limites a si mesmo é melhor, no longo prazo, tanto para você quanto para todos
Em muitas aplicações, não faz sentido gastar tanto tempo em pequenas otimizações. Quando dá para adicionar 32 GiB de RAM a um servidor por menos de 50 dólares, comparado a gastar mais de 40 horas de um desenvolvedor a pelo menos 20 dólares por hora, a resposta do ponto de vista de negócios é óbvia. Além disso, o site ficou fora do ar por uma semana inteira, e isso por si só pode matar a maioria dos negócios
Técnicos gostam desse tipo de mergulho profundo e querem micro-otimizar código trivial por anos, mas tosquiar iaques sem fim não paga as contas. Se o código roda em pouquíssimas máquinas, normalmente não vale a pena. Esse tipo de otimização muitas vezes também acaba em código mais difícil de manter
Acho que a bloatwareização do software em apps que rodam nos dispositivos dos usuários hoje vem muito do desencontro entre as máquinas dos desenvolvedores e as dos usuários. Desenvolvedores precisam de workstations potentes para trabalhar e fazem testes básicos nelas, mas os usuários rodam em aparelhos que, cinco anos atrás, já eram intermediários para baixo
É difícil vender a um gerente “podemos economizar 150 MB de memória”, mas dá para vender “se economizarmos 150 MB de memória, para 10% dos usuários o desempenho do app passa de horrível para minimamente utilizável”
Antigamente, software era de fato criado assim. Por isso, até em máquinas como um Pentium 1, era possível rodar bem um sistema operacional com a maior parte do que esperamos hoje. Em contraste, hoje páginas web engasgam ao rolar até em smartphones que têm literalmente cerca de mil vezes mais recursos em todos os eixos. A equipe do Word 95 esbarrava o tempo todo em limites e trade-offs de desempenho, e o resultado era claramente algo que funcionava ou não funcionava
Se tivessem simplesmente adicionado mais RAM, ainda estariam presos a um design inferior e logo teriam que comprar ainda mais RAM. O surpreendente nessa mudança é que ela não apenas reduziu o uso de recursos; a RAM livre também aumentou o cache de disco, deixando o sistema mais capaz e mais rápido
[1] Por exemplo, isto roda em um único Pi e, como não permite atualizações, é muito mais rápido que a Wikipedia em produção: https://encyclopedia.marginalia.nu/article/Hacker_News
Talvez seja por isso que computadores antigos pareciam tão bons, e jogos antigos também podiam ser tão excelentes
Pode ter relação com a complexidade dos sistemas com que lidamos. Quando recursos como RAM, espaço físico, comida, materiais, tempo e dinheiro são limitados, você precisa planejar como vai usá-los, e acaba obrigado a ficar mais esperto
Com recursos praticamente infinitos, você pode construir do jeito que quiser, mas passa a ter menos necessidade de se preocupar com o estado final. Basta começar e ver no que dá quando estiver rodando
Não sou exatamente gamer, mas sempre me impressiona a capacidade humana de colocar tanta emoção, aventura e horas de diversão em cartuchos ROM de poucos KB/MB. A ROM de Ocarina Of Time tem mais ou menos o tamanho de umas 8 fotos recentes que tirei com meu iPhone
O Raspberry Pi 2 consegue processar mais de 4 bilhões de instruções Dhrystone por segundo, e o Pi 4 passa de 10 bilhões por segundo
Claro que, pelos padrões modernos, o SABRE de meados dos anos 1970 era bastante básico para um sistema central de uma companhia aérea, mas, em teoria, seria possível rodar simultaneamente em um único Pi 2 sistemas simplificados de mais de 100 companhias aéreas
Programas modernos estão muito longe de serem otimizados. Exceto em casos com muita computação matemática, melhorias de 1000x ou 10000x são possíveis
Acho que a Microsoft sofre bastante com esse problema. Mesmo um notebook de 3000 dólares de cinco anos atrás fica inaceitavelmente lento ao rodar uma chamada no Teams, alguns apps do Office e um navegador com 30 abas ao mesmo tempo
Se você testa cada um separadamente, fica tudo bem quando só um está em execução, mas pessoas reais não usam assim
Talvez a solução seja impor limites artificiais, restringindo o tempo de execução em um hardware claramente definido e só aumentando esse limite depois de uma decisão explícita
Dito isso, eu só escrevo software corporativo em que o lado de desempenho se resume a “não faça burrice no banco de dados e não se preocupe com o resto, porque o cliente não paga por essa preocupação”, então posso estar completamente errado
Sempre fico feliz quando aparece uma atualização do marginalia.nu. Sou um usuário fiel deste site e espero que continuem postando
Obrigado. Estou tocando um projeto de hobby de mecanismo de busca e, por algum motivo, eu continuava pesquisando apenas variações de “Magnolia”. Para mim, o nome Marginalia não gruda na memória. Agora estou tentando entender o Searx
Fico curioso se o Marginalia oferece suporte a buscas com filtros de tempo, como último dia ou última semana. Olhando as palavras-chave especiais, parece que os parâmetros de busca aceitam apenas filtros baseados em ano
year>2005 (beta) o documento aparentemente foi publicado depois de 2005
year=2005 (beta) o documento aparentemente foi publicado em 2005
year<2005 (beta) o documento aparentemente foi publicado antes de 2005
O filtro por ano também é bem grosseiro, e é muito difícil determinar com precisão as datas da maioria das páginas web
Fico me perguntando se a afirmação de que “sempre que um SSD atualiza um único byte em algum lugar do disco, ele precisa apagar e reescrever a página inteira” é realmente correta para SSDs
Em flash bruto, não é bem assim. É possível sobrescrever valores “vazios” all-ones ou mudar apenas 1 para 0. A escrita é algumas ordens de grandeza mais lenta que a leitura, mas também algumas ordens de grandeza mais rápida que o apagamento, e só o apagamento conta para o orçamento de desgaste
Se o controlador do SSD não aproveita isso, parece um gol contra. Mas, se internamente ele for de fato log-structured, aí imagino que talvez não consiga
Anos atrás escrevi drivers para vários chips flash populares, e todos os chips com que trabalhei na época usavam apenas E/S em páginas de tamanho fixo para leitura e escrita
Como um SSD é um conjunto de chips, eu esperaria que cada chip dentro do SSD também só oferecesse suporte a E/S em páginas de tamanho fixo
Normalmente, o controlador usa várias técnicas para evitar esse padrão de pior caso, como overprovisioning, buffering e reordenação de escritas, mas há limites
A menor unidade que pode ser escrita em um SSD é uma página, e a menor unidade que pode ser apagada é um bloco composto por várias páginas
Então, mesmo que uma operação de escrita afete apenas 1 byte dentro de uma página, o SSD não consegue apagar só esse byte. Mas isso não significa necessariamente que ele precise apagar o bloco inteiro
O SSD pode executar uma operação do tipo “ler-modificar-escrever”. Ele lê a página inteira que contém o byte alterado para o buffer de cache do SSD, modifica apenas esse byte no cache da página, apaga um novo bloco vazio, escreve a página modificada do cache no novo bloco e atualiza a tabela de mapeamento FTL para apontar para a página atualizada no novo bloco
Portanto, mesmo que só 1 byte mude, a página precisa ser reescrita. Mas é possível evitar apagar o bloco inteiro até que muitas páginas dentro dele tenham sido modificadas
À medida que ocorrem escritas, as páginas se movem dentro do dispositivo físico. O próprio drive mantém um mapa de quais endereços são usados para quê, qual é o estado de saúde deles etc. É uma espécie de armazenamento esparso
Também há comandos como TRIM, manutenção periódica e coleta de lixo
Na prática, ao escrever em um drive que não está cheio, ele encontra uma página onde os dados possam entrar, verifica se há dados ali, faz leitura/modificação/escrita se necessário, decide onde gravar os dados e então escreve. Por causa do wear leveling, é muito provável que eles não voltem para o lugar original
É verdade que o controlador executa etapas muito mais complexas por desempenho. É por isso que um drive novo e vazio funciona melhor por um tempo, e um drive antigo e cheio, sem páginas de reserva, pode de fato ficar mais lento
Para acrescentar a fonte: fui engenheiro-chefe de um acelerador flash com mapeamento em memória e coerência de cache. Ele permitia mapear o drive de forma muito eficiente no espaço de usuário do Linux, mas no fim, por um tempo, acabou cedendo ao modelo de programação “fácil” em que ele simplesmente parecia mais um disco rígido
Lembrei que meu chefe na Mojeek provavelmente percorreu um caminho muito parecido. Este texto tem muita relação com conversas antigas
A Mojeek começou em 2004, e a maior parte da estrutura foi criada por um único desenvolvedor, que construiu quase tudo em recuperação de informação e infraestrutura
Coisas como restrições de dinheiro e hardware, decisões sobre IDs de 32 bits versus 64 bits, sharding e velocidade de atualização soam muito familiares
Também me lembrei do antigo “Google dance” do Google. Naquela época, os resultados de busca eram atualizados uma vez por mês; hoje eles oscilam todos os dias. Tudo faz parte da evolução, e é bom ver a Marginalia oferecendo outra perspectiva sobre a web além das big techs
Foi uma boa leitura
Muita gente trata otimização como uma arte obscura profunda, mas na maior parte das vezes ela é até mais fácil do que corrigir bugs comuns. Basta tratar uso excessivo de recursos exatamente como um bug
Acho que a maioria dos bugs fáceis de reproduzir não exige magia para ser corrigida. Se você consegue cutucar o bug, geralmente consegue classificá-lo, e até falhas raras de projeto costumam ficar evidentes rapidamente quando se tornam reproduzíveis
Um software cujo desempenho ninguém examinou de forma crítica é como um software com centenas de bugs facilmente reproduzíveis que ninguém depurou. Dá para ir eliminando um por um por bastante tempo antes de esbarrar em algo difícil
Vejo essa atitude mais como um resquício da época em que as pessoas ajustavam o endereço-alvo de desvios para que chegasse no momento exato em que a cabeça do tambor estivesse no ponto em que a CPU precisaria da instrução. Quando os recursos eram extremamente limitados, tudo era escrito manualmente em assembly, e uma posição global de memória podia ter significados diferentes conforme a etapa do programa, pessoas já muito inteligentes examinavam o desempenho criticamente, então era preciso encontrar o que elas não tinham encontrado. Em código moderno, isso é raro
Se enviar a requisição X ao serviço Y reproduz o bug, basta reduzir o caso de teste cada vez mais até encontrar o culpado
Otimização muitas vezes é uma questão de arquitetura. Há casos em que você está copiando algo quando poderia reutilizar um buffer, mas esses casos se esgotam rápido, e o profiler informa o que você precisa saber
Grandes ganhos de desempenho muitas vezes vêm de mudar todo o fluxo de dados e eliminar partes consideráveis, para que o código faça o que precisa em tão poucas etapas quanto possível
Fico curioso para saber por que escolheram SQLite em vez de um armazenamento chave-valor. Se a necessidade é apenas ler por ID e nenhuma outra coluna parece necessária, um banco relacional parece desnecessário
O SQLite tem a vantagem de ser um único arquivo. Por isso dá para fazer coisas interessantes, como copiar ou compartilhar
Gosto porque é mais um exemplo de restrições gerando inovação. A inovação é encontrada com mais frequência nos limites do que na abundância