Projeto e análise de sistemas de busca na web

Exportado OPUSMade available in DSpace on 2019-08-11T12:56:57Z (GMT). No. of bitstreams: 1 claudinebadue.pdf: 3260579 bytes, checksum: 582b2f9d101bf8fbb15fa283b8b98319 (MD5) Previous issue date: 27Mecanismos de busca na Web são caros para manter, caros para operar, e difíceis de projetar. Mecanismos modernos de busca contam com clusters de máquinas servidoras para processamento de consultas. Assim, o desempenho do processamento paralelo de consultas num cluster de servidores de índice é crucial para os mecanismos modernos de busca na Web. O objetivo desta tese é prover um arcabouço para o projeto e análise da infra-estrutura de mecanismos de busca na Web. Neste arcabouço (i) investigamos e analisamos a questão do desbalanceamento num cluster computacional composto por servidores de índice homogêneos e (ii) propomos um modelo de planejamento de capacidade para mecanismos de busca na Web.Num cluster de servidores de índice, o tempo de resposta depende basicamente do tempo de serviço do servidor mais lento para gerar uma resposta ordenada parcial. Abordagens anteriores investigam questões de desempenho neste contexto usando simulação, modelagem analítica, experimentação, ou uma combinação delas. Entretanto, estas abordagens simplesmente assumem tempos de serviço balanceados entre os servidores de índice homogêneos, um cenário que não observamos em nossa experimentação. Ao contrário, verificamos que mesmo com uma distribuição balanceada da coleção de documentos entre os servidores de índice, relações entre a freqüência de uma consulta na coleção e o tamanho de suas listas invertidas correspondentes levam a desbalanceamentos nos tempos de serviço de uma consulta nestes mesmos servidores, porque estas relações afetam o comportamento do cache do disco. Além disso, os tamanhos relativos da memória principal em cada servidor de índice (com referência ao uso do espaço em disco) e o número de servidores que participam do processamento paralelo de consultas também afetam o desbalanceamento nos tempos locais de serviço de uma consulta.A predição do desempenho de um mecanismo de busca na Web é usualmente feita empiricamente através de experimentação, requerendo uma configuração custosa. Assim, a modelagem tem um apelo natural neste contexto. Introduzimos um modelo de planejamento de capacidade para mecanismos de busca na Web que considera o desbalanceamento nos tempos de serviço de uma consulta entre os servidores de índice homogêneos. Nosso modelo, que é baseado numa rede de filas, é simples e razoavelmente preciso. Discutimos como ajustá-lo e como usá-lo para predizer, por exemplo, o impacto no tempo de resposta da consulta quando parâmetros tais como CPUs e discos são alterados. Isto permite ao gerente da máquina de busca determinar a priori se uma nova configuração do sistema irá manter o tempo de resposta sob determinadas restrições. Nossa abordagem é distinta e, acreditamos, útil para predizer o desempenho de mecanismos de busca reais.Web search engines are expensive to maintain, expensive to operate, and hard to design. Modern search engines rely on clusters of server machines for query processing. Thus, the performance of parallel query processing in a cluster of index servers is crucial for modern Web search engines. The objective of this thesis is to provide a performance framework for the design and analysis of the infrastructure of Web search engines. In this framework we (i) investigate and analyze the imbalance issue in a computational cluster composed of homogeneous index servers and (ii) propose a capacity planning model for Web search engines.In a cluster of index servers, the response time basically depends on the service time of the slowest server to generate a partial ranked answer. Previous approaches investigate performance issues in this context using simulation, analytical modeling, experimentation, or a combination of them. Nevertheless, these approaches simply assume balanced service times among homogeneous index servers, a scenario that we did not observe in our experimentation. On the contrary, we found that even with a balanced distribution of the document collection among index servers, relations between the frequency of a query in the collection and the size of its corresponding inverted lists lead to imbalances in query service times at these same servers, because these relations affect disk cache behavior. Further, the relative sizes of the main memory at each index server (with regard to disk space usage) and the number of servers participating in the parallel query processing also affect imbalance of local query service times.Predicting the performance of a Web search engine is usually done empirically through experimentation, requiring a costly setup. Thus, modeling is of natural appeal in this context. We introduce a capacity planning model for Web search engines that considers the imbalance in query service times among homogeneous index servers. Our model, which is based on a queueing network, is simple and yet reasonably accurate. We discuss how we tune it up and how we apply it to predict, for instance, the impact on the query response time when parameters such as CPUs and disks are changed. This allows the manager of the search engine to determine a priori whether a new configuration of the system will keep the query response under specified constraints. Our approach is distinct and, we believe, useful to predict the performance of real Web search engines