Processamento de Dados Massivos/Outros ambientes

Outros ambientes

editar

Apesar de sua larga aplicação, é importante observar que o modelo MapReduce e o Hadoop têm limitações. Primeiramente, muitas aplicações requerem mais do que um passo de mapeamento e outro de redução. O programador deve, então, descrever sua aplicação com sequências de maps e reduces. Especialmente se as tarefas a serem executadas são parte de um algoritm iterativo ou consultas semelhantes às normalmente executadas em um banco de dados tradicional, isso exige um processo de codificação de cada operação.

Uma segunda limitação é o fato de toda a comunicação ser baseada em arquivos. Isso implica em maiores latências na movimentação de dados, o que pode limitar o desempenho da aplicação se não há um nível de paralelismo suficiente para o volume de processamento esperado. Esse problema se torna ainda mais visível quando a tarefa exige diversos passos Map/Reduce.

Finalmente, há certos contextos de aplicação que têm se tornado mais relevantes com o aumento do volume de dados e da importância de certos tipos de aplicações que não se adequam bem ao modelo Map/Reduce. Entre eles, podemos citar o processamento de grandes grafos e o processamento de fluxos contínuos de dados, que não se ajustam bem ao modelo de etapas do Map/Reduce e ao uso de arquivos como elementos de armazenamento e processamento.

Sistemas de gerência de dados (NOSQL)

editar

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 [1] e Hive [2], desenvolvidos originalmente pela Yahoo! e Facebook, respectivamente, e posteriormente distribuídas como código aberto.

Pig [1] 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.

urls_ok = FILTER urls BY pagerank > 0.25 
  grupos = GROUP urls_ok BY categoria 
  grupos_maiores = FILTER grupos  
                  BY COUNT(urls_ok) > 10E5
  resultado = FOREACH grupos_maiores GENERATE 
                  category, AVG(urls_ok.pagerank) 

Hive [2], 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.

SELECT categoria, AVG(pagerank) 
FROM urls 
WHERE pagerank > 0.25 
GROUP By categoria 
HAVING COUNT(*) > 10E5;

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 [3], proposta original da Google, o HBase [4], uma implementação do mesmo conceito para o Hadoop, e outros, como Apache Cassandra [5] e Dynamo [6]. Em geral, esses sistemas garantem apenas consistência posterior 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 [7] e Spanner [8], ambos da Google, PNUTS [9] da Yahoo!, Dremel [10] e outros.

Anthill

editar

O ambiente de processamento Anthill [11] foi desenvolvido no DCC/UFMG para dar suporte a um ambiente de mineração de dados em larga escala denominado Tamanduá [12]. 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.

 
Representação da estrutura de uma aplicação executando no ambiente de processamento distribuído Anthill

Ao contrário do modelo MapReduce, aplicações no Anthill podem executar operações genéricas sobre os dados em cada filtro, não estando restritas a operações apenas que se encaixem em mapeamentos e reduções. Além disso, os fluxos podem implementar diferentes padrões de distribuição dos dados entre as instâncias, como round-robin (elementos são distribuídos de forma cíclica), broadcast (elementos replicados para todas as cópias de um filtro) e labeled (rotulado, onde elementos com uma mesma chave são sempre direcionados para o mesmo destino). Com o fluxo rotulado, processamento do tipo MapReduce pode ser facilmente implementado. Uma limitação do ambiente atual é que não há um sistema de arquivos integrado como no caso de HDFS e GFS: os dados devem ser distribuídos entre os nós de processamento pelo usuário, que deve definir o filtro de leitura para extrair os dados dos diversos arquivos.

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 [13], 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)

editar

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 [14], onde os elementos de processamento são orientados a fluxos ininterruptos. Outros sistemas orientados a streams incluem o IBM S4 [15], rebatizado InfoSphere Streams, e o Twitter Storm [16], recentemente liberado como projeto de código aberto.

Grafos

editar

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 [17], baseado no paradigma de processamento bulk synchronous (BSP) [18]. 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 [19].

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 [20] 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.

Referências

editar
  1. 1,0 1,1 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.
  2. 2,0 2,1 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.
  3. 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.
  4. 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.
  5. Lakshman, A., and Malik, P. Cassandra: a decentralized structured storage system. SIGOPS Operating Systems Review 44, 2 (Apr. 2010), 35–40.
  6. DeCandia, G., Hastorun, D. , Jampani, M., Kakulapati, G. , Lakshman, A., Pilchin, A. , Sivasubramanian, S. , Vosshall, P. , Vogels, W., Dynamo: amazon's highly available key-value store, Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles, 2007, 14-17
  7. Baker, J., Bond, C., Corbett, J., Furman, J. J., Khorlin, A., Larson, J., Leon, J.-M., Li, 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.
  8. 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.
  9. 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.
  10. 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.
  11. 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.
  12. Guedes, 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.
  13. 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.
  14. 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.
  15. 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.
  16. Twitter. Storm stream processing - visitado em outubro de 2012.
  17. 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.
  18. 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.
  19. 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.
  20. 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.