A Distributed Web Search Engine: System Design and Implementation
Abstract
This project implements an end-to-end distributed web search engine in Java. The system combines an HTTP/1.1 web server, a persistent distributed key-value store (KVS), a resilient distributed dataset framework named Flame, a web crawler, an inverted index, iterative PageRank computation, and a query service using term-frequency and inverse-document-frequency-like signals. Intermediate datasets are materialized in the KVS so that storage and distributed computation share a common data model. The completed system accepts a text query and returns ranked pages from the crawled corpus. The available evaluation documents end-to-end functional integration and concurrent execution of worker processes; it does not constitute a controlled comparison of retrieval quality, throughput, or fault tolerance.
System Architecture
HTTP and Persistent Storage
The network-facing components are built on a custom HTTP/1.1 server following RFC 2616, the historical specification targeted by the course project. Persistent state is maintained by a distributed KVS organized around a master and multiple workers. Clients obtain worker information from the master and route reads and writes to the appropriate worker. This layer stores crawled documents, intermediate computation state, index entries, and ranking outputs.
Flame datasets are encoded directly in KVS tables using an abstraction derived from resilient distributed datasets (Zaharia et al., 2012). An ordinary RDD assigns each value an arbitrary unique row key and stores the value in a column named value. Randomized keys distribute rows across storage workers. A pair RDD groups all values associated with one logical key into a single KVS row; separate columns represent the multiple values paired with that key. This representation permits distributed transformations to exchange data through persistent tables rather than process-local memory.
Distributed Data Processing with Flame
Flame provides the execution layer for data-parallel jobs. A coordinator accepts a submitted job and invokes operations on Flame workers. The workers execute transformations and communicate with the KVS through a client interface, allowing the output of one distributed stage to become the input of the next. The same abstraction is used for crawling-derived data, PageRank state, and index construction. Figures 1 and 2 summarize the high-level component relationships and the execution path of a submitted Flame job.
Figure 1. High-level relationship among the client, Flame workers, and persistent KVS.
Figure 2. Execution path for a Flame job and its interaction with KVS workers.
Retrieval Pipeline
Link Analysis with PageRank
The crawler output supplies a normalized URL, page content, and outgoing links for each document. The implementation follows the iterative link-analysis structure of PageRank (Page et al., 1999). It represents each URL u with a state tuple containing its current rank, previous rank, and adjacency list L. Both rank values are initialized to 1.0. For a page with n outgoing links, the transfer stage emits 0.85 * r_current / n to every destination. Flame aggregates incoming transfers by destination URL, joins the aggregate with the previous state table, adds the 0.15 rank-source term, and constructs the next state.
The computation repeats until the maximum absolute difference between current and previous ranks falls below a convergence threshold. The maximum is computed as a distributed reduction: a transformation produces the per-page differences, and a fold selects the largest value. This implementation expresses the complete iterative algorithm through pair-RDD transformations backed by the KVS.
Inverted Index and Query Scoring
Index construction reads each crawled page, extracts and normalizes its terms, and counts occurrences within the document. The persistent index table uses a term as its key and records document identifiers together with their term frequencies. URLs are hashed before being stored in these postings.
The query service uses the project-specific score (1 + log f_t,d) * log(N / n_t), where f_t,d is the frequency of term t in document d, n_t is the number of documents containing the term, and N is the number of unique terms in the index. Conventional inverse-document-frequency weighting uses corpus document count in the numerator (Salton and Buckley, 1988); because this implementation instead uses vocabulary size for N, its expression is described here as TF-IDF-like rather than as conventional TF-IDF. The inverse-frequency component is computed lazily for query terms rather than precomputed for every indexed term. The resulting relevance signal is combined with the link-analysis output to rank pages returned to the front end.
Demonstration and Evaluation
The completed front end submits a text query and displays the ranked pages returned from the crawled corpus. Figure 3 shows results for the query apple.
Figure 3. Search results produced by the integrated query pipeline.
The crawler, indexer, PageRank job, KVS, and web server execute as multiple Java processes. Figure 4 records CPU, memory, storage, and network activity while search-engine workers exercise the distributed infrastructure.
Figure 4. Resource utilization during a distributed search-engine workload.
These observations document that the storage, processing, indexing, and query components operated together in the demonstrated run. However, the project artifacts do not report controlled latency or throughput measurements, labeled relevance judgments, comparative baselines, or a complete record of corpus size and worker configuration. The final report also notes that PageRank transfers could be emitted to normalized links outside the crawled corpus. This rank leakage caused computed values to approach the 0.15 source term and limits interpretation of the resulting authority scores. The figures should therefore be interpreted as qualitative evidence of functionality rather than a performance or information-retrieval benchmark.
Conclusion
The project demonstrates a complete search stack constructed from custom distributed-system components. A common persistent data model connects web crawling, iterative graph computation, inverted indexing, and online query processing. The principal result is architectural integration: PageRank and TF-IDF-like retrieval execute on the same Flame and KVS substrate that stores the crawled corpus. Future work should correct rank leakage and the vocabulary-size normalization before evaluating repeatable corpus sizes, worker counts, failure scenarios, latency, throughput, and relevance metrics such as precision or normalized discounted cumulative gain.
References
- L. Page, S. Brin, R. Motwani, and T. Winograd. “The PageRank Citation Ranking: Bringing Order to the Web.” Stanford InfoLab Technical Report, 1999.
- M. Zaharia et al. “Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing.” USENIX NSDI, 2012.
- G. Salton and C. Buckley. “Term-Weighting Approaches in Automatic Text Retrieval.” Information Processing & Management, 1988.