Diferenças entre edições de "Processamento de Dados Massivos/Outros ambientes"

Adicionadas referências importantes
m
(Adicionadas referências importantes)
Muitas das tarefas desenvolvidas em sistemas de processamento de dados massivos ainda se assemelham muito a consultas tradicionais em bancos de dados relacionais. Realizar uma projeção, uma seleção ou um ''join'' sobre um conjunto de linhas de entrada exige uma ou mais sequências de ''maps'' e ''reduces''. Para simplificar a tarefa dos usuários nesses casos, diversos tipos de sistemas de gerência de dados foram propostos e implementados sobre a plataforma Hadoop ou em outros contextos semelhantes. Esses sistemas costumam ser denominados de forma geral como NOSQL, usualmente interpretado como “Not Only SQL”, em contraposição à linguagem de consulta usualmente utilizada em bancos de dados relacionais.
 
Para a automação de consultas, dois dos primeiros sistemas desenvolvidos são os ambientes Pig <ref name=pig>Olston, C., Reed, B., Srivastava, U., Kumar, R., and Tomkins, A. Pig latin: a not-so-foreign language for data processing. In ''Proceedings of the 2008 ACM SIGMOD international conference on Management of data'' (New York, NY, USA, 2008), SIGMOD ’08, ACM, pp. 1099–1110.</ref> e Hive <ref name=hive>Thusoo, A., Sarma, J. S., Jain, N., Shao, Z., Chakka, P., Anthony, S., Liu, H., Wyckoff, P., and Murthy, R. Hive - a warehousing solution over a map-reduce framework. PVLDB 2, 2 (2009), 1626–1629.</ref>, desenvolvidos originalmente pela Yahoo! e Facebook, respectivamente, e posteriormente distribuídas como código aberto.
 
Pig <ref> <name=pig/ref> oferece uma linguagem de consultas procedural, algumas vezes comparada a Perl, para a expressão de tarefas sobre arquivos que representam uma base de dados organizada como linhas de texto representando registros. O trecho de código a seguir ilustra o uso de Pig para consultar um arquivo com registros de URLs com suas categorias e seu valor de ''pagerank'' (PR), calcular o PR médio para cada categoria e exibir apenas aquelas com PR acima de um mínimo e com quantidade alta de URLs.
 
<pre>urls_ok = FILTER urls BY pagerank &gt; 0.25
</pre>
 
Hive <ref> <name=hive/ref>, por outro lado, se apresenta como um sistema de armazém de dados com uma linguagem de consulta que é próxima a um subconjunto de SQL. Tabelas são normalmente definidas como arquivo textuais com campos separados por tabulações. Em Hive, a mesma consulta anterior tomaria a forma de uma consulta semelhante a SQL, como ilustrado a seguir. O ambiente de processamento se encarregaria de transformar a consulta em uma sequência de ''maps'' e ''reduces'' que geraria o resultado desejado. Comandos adicionais poderiam ser usados para produzir um arquivo como saída.
 
<pre>SELECT categoria, AVG(pagerank)
</pre>
 
Diversas soluções para estruturação dos arquivos armazenados no GFS ou HDFS de forma mais eficiente para consultas já foram propostas e são largamente utilizadas. Essas soluções são em geral sistemas de armazenamento denominados “chave-valor” (''key-value stores''), onde a informação é armazenada em função de uma chave pré-definida. Esses sistemas, ao contrário da interface padrão do sistema de arquivos, permitem consultas e atualizações de conteúdo associado a qualquer chave. Exemplos de sistemas desse tipo são o BigTable <ref>Chang, F., Dean, J., Ghemawat, S., Hsieh, W. C., Wallach, D. A., Burrows, M., Chandra, T., Fikes, A., and Gruber, R. E. Bigtable: A distributed storage system for structured data. ''ACM Transactions on Computer Systems'' 26, 2 (June 2008), 4:1–4:26.</ref>, proposta original da Google, o HBase <ref>Borthakur, D., Gray, J., Sarma, J. S., Muthukkaruppan, K., Spiegelberg, N., Kuang, H., Ranganathan, K., Molkov, D., Menon, A., Rash, S., Schmidt, R., and Aiyer, A. Apache hadoop goes realtime at facebook. In ''Proceedings of the 2011 ACM SIGMOD International Conference on Management of data'' (New York, NY, USA, 2011), SIGMOD ’11, ACM, pp. 1071–1080.</ref>, uma implementação do mesmo conceito para o Hadoop, e outros, como Apache Cassandra <ref>Lakshman, A., and Malik, P. Cassandra: a decentralized structured storage system. ''SIGOPS Operating Systems Review'' 44, 2 (Apr. 2010), 35–40.</ref> e Dynamo <ref>Lakshman, A., and Malik, P. Cassandra: a decentralized structured storage system. ''SIGOPS Operating Systems Review'' 44, 2 (Apr. 2010), 35–40.</ref>. Em geral, esses sistemas garantem apenas consistência eventual do conteúdo e oferecem compromissos diferentes de implementação em função de diferentes requisitos de aplicação.
 
Outras soluções buscam novas formas de organização dos dados que ofereçam maior estrutura para os dados e poder de expressão nas consultas, bem como formas de organização que permitam a criação de bases de dados distribuídas geograficamente entre diversos ''datacenters''. Exemplos de projetos nessa linha incluem Megastore <ref> </ref>Baker, eJ., Spanner <ref>Bond, </ref>C., ambosCorbett, daJ., GoogleFurman, PNUTSJ. <ref>J., </ref>Khorlin, daA., Yahoo!Larson, Dremel <ref>J., </ref>Leon, eJ.-M., outrosLi, Y., Lloyd, A., and Yushprakh, V. Megastore: Providing scalable, highly available storage for interactive services. In ''Proceedings of the Fifth Biennial Conference on Innovative Data Systems Research (CIDR)'' (Asilomar, CA, 2011), pp. 223–234.
</ref> e Spanner <ref>Corbett, J. C., Dean, J., Epstein, M., Fikes, A., Frost, C., Furman, J., Ghemawat, S., Gubarev, A., Heiser, C., Hochschild, P., Hsieh, W., Kanthak, S., Kogan, E., Li, H., Lloyd, A., Melnik, S., Mwaura, D., Nagle, D., Quinlan, S., Rao, R., Rolig, L., Saito, Y., Szymaniak, M., Taylor, C., Wang, R., and Woodford, D. Spanner: Google’s globally-distributed database. In ''Proceedings of the Tenth Symposium on Operating System Design and Implementation (OSDI)'' (Hollywood, CA, 2012), USENIX.</ref>, ambos da Google, PNUTS <ref>Cooper, B. F., Ramakrishnan, R., Srivastava, U., Silberstein, A., Bohannon, P., Jacobsen, H.-A., Puz, N., Weaver, D., and Yerneni, R. Pnuts: Yahoo!’s hosted data serving platform. In ''Proceedings of VLDB Endoment''. 1, 2 (Aug. 2008), 1277–1288.</ref> da Yahoo!, Dremel <ref>Melnik, S., Gubarev, A., Long, J. J., Romer, G., Shivakumar, S., Tolton, M., and Vassilakis, T. Dremel: interactive analysis of web-scale datasets. In ''Proceedings of VLDB Endoment'' 3, 1-2 (Sept. 2010), 330–339.</ref> e outros.
 
== Anthill ==
 
O ambiente de processamento Anthill <ref>Ferreira, R. A., Meira, Jr., W., Guedes, D., Drummond, L. M. A., Coutinho, B., Teodoro, G., Tavares, T., Araujo, R., and Ferreira, G. T. Anthill: A scalable run-time environment for data mining applications. In ''Proceedings of the 17th International Symposium on Computer Architecture on High Performance Computing'' (Washington, DC, USA, 2005), SBAC-PAD ’05, IEEE Computer Society, pp. 159–167.</ref> foi desenvolvido no DCC/UFMG para dar suporte a um ambiente de mineração de dados em larga escala denominado Tamanduá <ref>Guedes, </ref><ref>D., Jr., W. M., and Ferreira, R. Anteater: A service-oriented architecture for high-performance data mining. ''IEEE Internet Computing'' 10, 4 (2006), 36–43.</ref>. Seu modelo de programação se basea no paradigma denominado filtro-fluxo (''filter-stream''), onde o processamento é descrito como operações executados por filtros que processam um fluxo de dados que passa por eles. Cada filtro é descrito de forma que múltiplas instâncias possam ser criadas para processar elementos do fluxo em paralelo, obtendo paralelismo de dados. Filtros podem ser encadeados de forma a executar diversas etapas de processamento sobre um fluxo, transformando os dados a cada estágio, criando paralelismo de tarefas. Um exemplo de uma aplicação com quatro filtros é ilustrada na figura a seguir.
 
[[Imagem:Exemplo_Anthill.png|Center]]
A comunicação entre filtros no Anthill se dá por canais de comunicação na rede, sem o uso de arquivo intermediários, o que reduz a latência e aumenta a possibilidade de exploração de paralelismo por operações que podem ser superpostas à comunicação. Além disso, o Anthill permite a expressão de fluxos de comunicação com realimentação, onde o resultado de uma etapa do processamento é injetado de volta em um estágio anterior da cadeia de filtros. Esse recurso possibilita a implementação eficiente de algoritmos cíclicos como os encontrados em aplicações de mineração de dados que operam com o refinamento de soluções intermediárias.
 
Alguns outros ambientes de programação também evitam as limitações do MR/Hadoop relacionadas ao uso de arquivos para comunicação. Em particular, o Dryad <ref>Isard, M., Budiu, M., Yu, Y., Birrell, A., and Fetterly, D. Dryad: distributed data-parallel programs from sequential building blocks. In ''Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems 2007'' (New York, NY, USA, 2007), EuroSys ’07, ACM, pp. 59–72.</ref>, da Microsoft, permite que o usuário represente seu processamento como um grafo direcionado, também seguindo o modelo filtro-fluxo. No caso do Dryad, uma linguagem especial oferece construtores para que o programador construa o grafo de comunicação. O ambiente de execução cuida da comunicação e o escalonamento de tarefas a partir de então.
 
== Fluxos de dados (''streams'') ==
A operação contínua de serviços em nuvem tem gerado diversas fontes de dados ininterruptas que criam novas possibilidades de processamento e novas demandas. No Observatório da Web, uma parte do processamento consiste na observação de mensagens enviadas pelo Twitter. Um extrator obtém continuamente novas mensagens (''twits'') sobre um determinado tema, de onde são extraídas as ''hashtags'' usadas e as palavras usadas para posteriormente se fazer a análise do conteúdo.
 
A natureza contínua dos dados torna complicado o uso de sistemas baseados em arquivos, como o Hadoop. Essa orientação a arquivos exige que os dados sejam armazenados a cada unidade de tempo (dia, hora, etc.), causando um atraso entre o momento de coleta e processamento. No DCC-UFMG, com base na experiência com o Anthill, foi desenvolvido o Watershed <ref>Alves de Souza Ramos, T. L., Oliveira, R. S., de Carvalho, A. P., Ferreira, R. A. C., and Meira Jr., W. Watershed: A high performance distributed stream processing system. In ''Proceedings of the 2011 23rd International Symposium on Computer Architecture and High Performance Computing'' (Washington, DC, USA, 2011), SBAC-PAD ’11, IEEE Computer Society, pp. 191–198.</ref>, onde os elementos de processamento são orientados a fluxos ininterruptos. Outros sistemas orientados a ''streams'' incluem o IBM S4 <ref>Neumeyer, L., Robbins, B., Nair, A., and Kesari, A. S4: Distributed stream computing platform. In ''Proceedings of the 2010 IEEE International Conference on Data Mining Workshops'' (Washington, DC, USA, 2010), ICDMW ’10, IEEE Computer Society, pp. 170–177.</ref>, rebatizado InfoSphere Streams, e o Twitter Storm <ref>Twitter. [https://github.com/nathanmarz/storm/wiki Storm stream processing] - visitado em outubro de 2012.</ref>, recentemente liberado como projeto de código aberto.
 
== Grafos ==
Outro contexto que tem ganhado atenção da comunidade é aquele das aplicações de processamento de grandes grafos, que surgem da representação de relacionamentos entre usuários em redes sociais, por exemplo. Apesar de haver muitos trabalhos sobre o uso de Hadoop nesses casos, a maioria dos algoritmos sobre grafos tem características que não se adaptam bem ao modelo MapReduce. Esses algoritmos frequentemente exigem diversas iterações sobre o conjunto de dados, bem como padrões de comunicação irregulares ditados pela estrutura dos grafos considerados. Essas oprações são difíceis de representar como etapas de mapeamento e redução isoladas.
 
Frente a esses problemas, a própria Google desenvolveu um ambiente de processamento específico para esse contexto, o Pregel <ref>Malewicz, G., Austern, M. H., Bik, A. J., Dehnert, J. C., Horn, I., Leiser, N., and Czajkowski, G. Pregel: a system for large-scale graph processing. In ''SIGMOD ’10: Proceedings of the 2010 international conference on Management of data'' (New York, NY, USA, 2010), ACM, pp. 135–146.</ref>, baseado no paradigma de processamento ''bulk synchronous'' (BSP) <ref>Goudreau, M. W., Lang, K., Rao, S. B., Suel, T., and Tsantilas, T. Portable and efficient parallel computing using the BSP model. IEEE Transactions on Computers 48, 7 (July 1999), 670–689.</ref>. Nesse modelo, os algoritmos são expressos do ponto de vista de cada nó, que pode trocar mensagens com outros nós do grafo (não só seus vizinhos). A execução progride em etapas denominadas ''supersteps'', em que cada nó primeiramente recebe todas as mensagens enviadas para ele no ''superstep'' anterior, executa o algoritmo a ele assinalado e envia mensagens para outros nós (que só serão entregues ao final do ''superstep''). Apesar de forçar a ocorrência de barreiras de sincronização, esse modelo escala bem para grafos muito grandes e simplifica as questões de consistência entre nós, já que a comunicação só ocorre entre ''supersteps''. Uma implementação de código aberto do Pregel foi realizada no DCC/UFMG, resultando no sistema Rendero <ref>Macambira, T. A., and Guedes, D. A middleware for parallel processing of large graphs. In ''Proceedings of the 8th International Workshop on Middleware for Grids, Clouds and e-Science'' (New York, NY, USA, 2010), MGC ’10, ACM, pp. 7:1–7:6.</ref>.
 
Para grafos que não atingem as dimensões daqueles para que o Pregel foi criado, o modelo BSP limita a eficiência do processamento. O ambiente GraphLab <ref>Low, Y., Bickson, D., Gonzalez, J., Guestrin, C., Kyrola, A., and Hellerstein, J. M. Distributed Graphlab: a framework for machine learning and data mining in the cloud. In ''Proceedings of VLDB Endowment'' 5, 8 (Apr. 2012), 716–727.</ref> segue uma linha completamente diferente de operação, relaxando as restrições e garantias de consistência no processamento dos nós. O algoritmo também deve ser expresso em termos de nós, mas é permitido a um nó acessar (e alterar) atributos associados às arestas e aos nós vizinhos. Esse recurso aumenta a facilidade de execução em paralelo de diversos nós, mas transfere para o programador a responsabilidade de lidar com o impacto devido a possíveis inconsistências.
 
{{AutoCat}}
49

edições