Estruturas de dados para aplicações intensivas em dados [PDF]
(cs-people.bu.edu)- As estruturas de dados chave-valor são componentes centrais de sistemas orientados a dados, e o desempenho pode variar bastante conforme a carga de trabalho e as condições de hardware
- A estrutura física se divide em layout dos dados, metadados para navegação e algoritmos de armazenamento e recuperação; também é chamada de métodos de acesso, contêineres de dados ou estruturas de busca
- A carga de trabalho pode ser expressa como uma combinação de consultas pontuais, consultas por intervalo, inserções, exclusões e atualizações, e a capacidade e o custo de memória e armazenamento persistente também entram como requisitos de projeto
- A B+-tree é forte em leitura e consultas por intervalo, mas quando inserções e atualizações aumentam, a reorganização dos nós folha se torna custosa; a LSM-tree lida com muitas inserções por meio de buffering e mesclagem
- Em ambientes onde a movimentação de dados se torna gargalo, é preciso escolher estruturas existentes ou projetar novas estruturas de acordo com novas aplicações, mudanças no hardware e crescimento dos dados
O problema que as estruturas de dados chave-valor resolvem
- As estruturas de dados chave-valor são amplamente usadas em aplicações intensivas em dados e, por causa da versatilidade do modelo chave-valor, servem de base para vários sistemas
- Uma chave é mapeada para um valor, mas o mesmo valor pode estar associado a várias chaves
- O significado do valor varia conforme a aplicação
- Pode ser um registro de banco de dados relacional
- Pode ser um Pandas DataFrame
- Pode ser um conjunto de campos que a aplicação interpreta e usa em um sistema NoSQL
- Em sistemas que lidam com dados de redes sociais, pode incluir referências a objetos grandes como imagens ou vídeos
Composição física e escopo de aplicação
- Fisicamente, uma estrutura de dados chave-valor é composta por três elementos
- Dados armazenados em um layout específico
- Metadados opcionais que ajudam a localizar os dados
- Algoritmos que dão suporte às operações de armazenamento e busca
- Estruturas de dados são usadas de várias formas em sistemas de dados, sistemas operacionais, sistemas de arquivos, compiladores e sistemas de rede
- Os exemplos do livro se concentram principalmente em sistemas de dados de grande escala e dispositivos de armazenamento secundário, mas a análise e a forma de projeto também se aplicam a sistemas em memória
- Esta análise é voltada a ambientes com duas ou mais camadas na hierarquia de memória e armazenamento
Carga de trabalho e custo determinam o projeto
- A aplicação ou carga de trabalho pode ser representada como uma combinação de operações chave-valor
-
Consulta pontual
-
Consulta por intervalo
- Inserção
- Exclusão
- Atualização
- A capacidade necessária e o custo de memória e armazenamento persistente também fazem parte dos requisitos da aplicação
- A estrutura de dados a ser otimizada muda conforme o tipo de sistema
- Sistemas de arquivos gerenciam metadados e conteúdo de arquivos com estruturas de dados otimizadas para atualizações frequentes
- Compiladores gerenciam variáveis com hash maps durante o ciclo de vida das variáveis e representam a forma geral do programa como uma abstract syntax tree
- Dispositivos de rede precisam de estruturas de dados especializadas para armazenar e acessar tabelas de roteamento com eficiência
-
As escolhas contrastantes de B+-tree e LSM-tree
- A B+-tree é muito usada para equilibrar custo de leitura e custo de escrita em cargas de trabalho com poucas inserções e atualizações e muitas consultas pontuais e por intervalo
- O alto fan-out dos nós reduz os acessos necessários à memória auxiliar no percurso da raiz até as folhas, e os níveis superiores ficam em cache em camadas de memória mais rápidas
- Mantém todas as chaves ordenadas nos nós folha e conecta os nós folha em uma lista encadeada para dar suporte a consultas por intervalo
- Quando inserções e atualizações aumentam, a reorganização ou divisão dos nós folha se torna necessária e pode virar gargalo de desempenho
- A LSM-tree usa uma abordagem diferente para cargas de trabalho com muitas inserções
- Coloca todas as atualizações em um buffer de memória compartilhado
- Quando o buffer enche, faz flush para o disco
- Conforme os buffers se acumulam, faz a mesclagem em coleções maiores de dados ordenados
- As atualizações são tratadas com uma política out-of-place, e podem existir vários pares chave-valor com a mesma chave dentro da estrutura
- O valor atual de uma determinada chave é o do par chave-valor inserido mais recentemente
Estruturas de dados adaptativas
- Além da abordagem de projetar estruturas de dados prevendo antecipadamente a carga de trabalho, o texto também trata de estruturas que se aproximam gradualmente de uma forma ideal durante a execução
- As B+-tree e LSM-tree em seu projeto original impõem ordenação dentro de nós residentes em disco para responder a todas as consultas pontuais ou por intervalo
- As estruturas de dados adaptativas podem começar com um ou mais nós não ordenados e ordenar gradualmente quando surgir oportunidade
- Database cracking usa os padrões de acesso das consultas recebidas para reorganizar fisicamente os dados subjacentes de forma contínua e incremental
- O objetivo é melhorar o desempenho de consultas futuras
Hierarquia de hardware e a parede de memória
- A evolução do hardware cria novos desafios e oportunidades para o projeto de estruturas de dados
- Nas camadas de armazenamento, os níveis inferiores oferecem mais espaço por menor preço, mas com maior latência de acesso; os níveis superiores, mais próximos do processador, são mais rápidos, porém menores e com custo por byte mais alto
- A camada que se torna gargalo em uma aplicação específica varia conforme o tamanho dos dados da aplicação e a capacidade de armazenamento de cada camada
- A B+-tree foi originalmente pensada para maximizar o fan-out e reduzir acessos a disco, mas com o aumento da memória e com os dados passando a caber em RAM ou em memória secundária não volátil, os trade-offs mudaram bastante
- B+-trees em memória apresentam o melhor desempenho com fan-out pequeno
- A parede de memória (memory wall) se refere à tendência de aumento da diferença entre a velocidade do processador e a velocidade da memória off-chip
- Desde o início dos anos 2000, sistemas operacionais e sistemas de gerenciamento de dados vêm sendo reprojetados para otimizar o uso da memória cache
Espaço de projeto e diretrizes
- O texto organiza o espaço de escolhas no projeto de estruturas de dados e mostra como selecionar a estrutura adequada aos objetivos da aplicação e à carga de trabalho
- Como hardware e propriedades dos dados continuam mudando, o projeto de estruturas de dados também exige inovação contínua
- O espaço de projeto organizado e as diretrizes servem para escolher a estrutura mais adequada entre as existentes ou projetar uma nova estrutura para uma carga de trabalho específica
1 comentários
Opiniões no Hacker News
Ainda só dei uma olhada por cima, mas este texto é um material de pesquisa excelente que cobre uma área enorme
Ele não se limita a listar estruturas de dados; ajuda a organizar mentalmente os fatores a considerar ao criar ou usar estruturas de dados em aplicações
Um dos autores deste livro dirige um laboratório de pesquisa nessa área
Também há uma ferramenta interessante que ajuda a projetar estruturas de dados ideais: http://daslab.seas.harvard.edu/datacalculator/
Gostaria de saber mais recomendações de materiais sobre este tema
O artigo é excelente, e também conheço Designing Data-Intensive Applications, de Martin Klepmann, mas esse livro é mais voltado a bancos de dados do que a estruturas de dados
Falta a comparação entre array de estruturas e estrutura de arrays, muito importante se você estiver projetando uma estrutura para armazenar algum tipo de dado analítico
Portanto, a discussão existe, mas não é explicada usando os termos array de estruturas/estrutura de arrays
Queria comprar um exemplar, mas está 100 dólares na Amazon
É uma estrutura quebrada em que tanto o autor quanto o leitor saem perdendo
É preciso um sumário
Foi o mesmo mesmo quando pedi para ignorar cabeçalhos e rodapés das páginas, e eu achava que o estado da arte mais recente já estava muito melhor