Hash consistente como uma ferramenta para distribuição de tarefas em sistemas distribuídos reconfiguráveis

• André Ribeiro da Silva UFMG
• Hélio Marcos Paz de Almeida UFMG
• Tiago Macambira UFMG
• Dorgival Olavo Guedes UFMG
• Wagner Meira Jr. UFMG
• Renato Antonio C. Ferreira UFMG

DOI: https://doi.org/10.5753/wscad.2005.18990

Resumo

Sistemas distribuídos que incluem processos replicados em várias máquinas têm que oferecer soluções para o problema de distribuição dinâmica de tarefas. No caso em que a aplicação requer a manutenção de algum de estado entre tarefas é preciso um esquema consistente de endereçamento. Isso é usualmente feito através de uma função de hash tradicional, que entretanto não funciona bem em ambientes com reconfiguração dinâmica. Neste trabalho avaliamos o uso de hash consistente, uma forma de hash onde a função de distribuição se altera pouco com a alteração da sua faixa de operação, como uma solução para esse problema. Comparamos o desempenho de duas soluções de hash consistente com soluções tradicionais em termos da uniformidade do padrão de distribuição, do número de mensagens trocadas quando de uma reconfiguração e do padrão de comunicação envolvido. Nossos resultados mostram que hash consistente tem um overhead de comunicação muito menor que a solução tradicional (até 35 vezes em alguns testes), com um aumento aceitável da variância na distribuição de tarefas.

Referências

D. P. Anderson, J. Cobb. E. Korpela. M. Lebofsky, and D. Werthimer. SETI@home: an experiment in public resource computing. Communications of the ACM, 45(11):56-61, nov. 2002.

S. Androutsellis-Theotokis and D. Spinellis. A survey of peer-to-peer content distribution technologies. ACM Comput. Surv., 36(4):335-371, 2004.

V. Cardellini, M. Colajanni, and P. S. Yu. Request redirection algorithms for distributed Web systems. IEEE Transactions on Parallel and Distributed Systems, 14(4):355-368, abr. 2003.

N. Carriero. D. Gelenrter, and J. Leichter. Distributed data structures in linda. In POPL '86: Proceedings of the 13th ACM SIGACT-SIGPLAN Symposium on Principles of programming languages, págs. 236-242, New York. NY. USA. 1986. ACM Press.

W. Cirne, F. Brasileiro, N. Andrade, L. Costa, D. Paranhos. E. Santos-Neto, C. DeRose. T. Ferreto, M. Mowbray, R. Scheer, and J. Jornada. Scheduling in bag-of-task grids: The Pauá case. In Proceedings of the 16th Symposiun on Computer Architecture and High Performance Computing (SBAC-PAD'2004). SBC, 2004.

J. Dean and S. Ghemawat. Mapreduce: Simplified data processing on large clusters. In Proceedings of the 6th Symposium on Operating Systems Design and Implementation (OSDJ). USENIX, 2004.

R. Fonseca. W. Meira Jr., D. Guedes. and L. Drummond. Anthill: A scalable run-time environment for data mining applications. In Proceedings of the 17th Symposium on Computer Architecture and High-Performance Computing (SBACPAD ). SBC, 2005.

P. B. Godfrey and I. Stoica. Heterogeneity and load balance in distributed hash tables. In Proceedings of the INFOCOM Conference. IEEE. 2005.

D. Karger, E. Lehman. T. Leighton. R. Panigrahy, M. Levine, and D. Lewin. Consistem hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web. In Proceedings of the twenty-ninth annual ACM Symposium on Theory of Computing. págs. 654-663. ACM. 1997.

D. Karger. A. Sherman. A. Berkheirner. B. Bogstad. R. Dhanidinia. K. Iwarnoto, B. Kim. L. Matkins, and Y. Yerushalmi. Web caching with consistem hashing. In Proceedings of the eighth international conference on World Wide Web, págs. 1203-1213. ElsevierNorth-Holland, Inc., 1999.

D. Lowenthal and G. Andrews. An adaptive approach to data placement. In Proceedings of the 10th International Parallel Processing Symposium (IPPS '96). IEEE. 1996.

G. Manku. Routing networks for distributed hash tables. In Proceedings of the 22nd ACM PODC. 2003.

S. Ratnasarny. P. Francis, M. Handley. R. Karp. and S. Schenker. A scalable content-addressable network. In SIGCOMM '01: Proceedings of the 2001 conference on Applications. technologies, architectures, and protocols for Computer communications, págs. 161-172. New York. NY. USA, 2001. ACM Press.

S. Ratnasarny. I. Stoica. and S. Shenker. Routing algorithms for DHTs: Some open questions. In IPTPS '01: Revised Papers from the First International Workshop on Peer-to-Peer Systems, págs. 45-52. London. UK. 2002. Springer-Verlag.

A. I. T. Rowstron and P. Druschel. Pastry: Scalable. decentralized object location, and routing for large-scale peer-to-peer systems. In Middleware 2001: Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg. págs. 329-350, London. UK.. 2001. SpringerVerlag.

I. Stoica, R. Morris, D. Karger. M. F. Kaashoek, and H. Balakrishnan. Chord: A scalable peer-to-peer lool-up service for internet applications. In SIGCOMM '01: Proceedi11gs of the 2001 conference on Applications, technologies. architectures, and protocols for Computer communications, págs. 149-160, New York, NY. USA. 2001. ACM Press.

G. Teodoro, T. Tavares, B. Coutinho. W. Meira Jr., and D. Guedes. Load balancing on stateful clustered web servers. In Proceedings of the 15th Symposium on Computer Architecture and High-Peiformance Computing (SBAC-PAD). SBC, 2003.

A. Veloso, W. Meira Jr., R. Ferreira. D. Guedes. and S. Parthasarathy. Asynchronous and anticipatory filterstrearn based parallel algorithm for frequent itemset mining. In Proceedings of the European Conference on Principies of Data Mining and Knowledge Discovery (PKDD). 2004.