AskSauron

Overview

AskSauron is a distributed search engine built in Java as a four-person team project for UPenn CIS 5550, supporting the full search lifecycle from crawling and indexing to ranking and retrieval. Every component was written from scratch: the HTTP networking layer, the KVS, the Flame distributed framework, and all pipeline jobs. Each team member first implemented all of these components independently as course assignments before they were merged and hardened into the final system.

The system is powered by a custom Key-Value Store and Flame, a distributed processing framework built from scratch in Java and modeled after Apache Spark, designed to execute parallel dataflow jobs across the pipeline. The production crawl stored 1,001,925 crawl records, and the retained index contained 484,280 searchable documents. The complete set of crawl and derived KVS tables occupied approximately 238 GB on EC2.

The design was built directly around The Anatomy of a Large-Scale Hypertextual Web Search Engine (Brin & Page, 1998). The course required reading the paper and using it as the blueprint for our implementation.

Although the software architecture is fully distributed, the entire pipeline was deployed and run on a single AWS EC2 instance running multiple concurrent worker processes across the crawl, indexing, and ranking stages.

Tech Stack

Java, Custom Flame framework (Apache Spark-style), Custom KVS, TF-IDF, PageRank, AWS EC2, OpenNLP PorterStemmer

My Contributions

I was responsible for the ranking layer and was the primary author of TF-IDF scoring, phrase search, query-time stem expansion, multi-term and title boosting, query caching, and query-centered result snippets. I also handled significant integration and EC2 operational work — connecting the team’s independently developed components, running and resuming large crawl batches, validating corpus counts, monitoring storage, and optimizing PageRank under single-instance memory constraints.

Results & Core Features

• Data Pipeline Scale: Stored 1,001,925 crawl records and produced a retained index of 484,280 searchable documents after filtering invalid or unsupported content. The crawl and derived KVS tables occupied approximately 238 GB on EC2.
• Recorded Production Runs: The crawl completed in approximately 1 hour 56 minutes of active runtime across two batches. The retained PageRank job processed the production corpus in 6 hours 56 minutes, converging after 7 iterations. A later full re-index benchmark completed in approximately 4 hours 39 minutes, although that rerun was not the batch retained for deployment.
• High-Performance Frontend UX: Includes search suggestions, spellcheck (Levenshtein distance), and a capped in-memory query cache that stores complete result objects — including titles and scores — so paginated requests never re-query the distributed KVS. Autocomplete preloaded approximately 140,000 index terms when the frontend started. This introduced a roughly 44-second cold start, but moved the cost out of the request path so subsequent suggestions could be generated through fast local binary search without repeated distributed KVS reads.

• Cached Page Access: Served stored snapshots of indexed pages so content remained viewable even if the original source was down or had changed.

• Search Result Preview Snippets: Initial preview experiments returned generic page openings and occasionally exposed JavaScript or boilerplate text. I changed the selection logic to center the 350-character window around the first matching query term, highlight every matched term, and fall back to the beginning of the page only when no match existed. A teammate then tightened the content filtering to remove remaining script noise. Previews are extracted lazily — only for the current page of results being rendered, not the full result set — to minimize distributed KVS reads on every search.

• Phrase Search: The inverted index stores each term’s position sequence per document. At query time, the engine detects when all words in a multi-word query appear adjacently and applies a relevance boost to those pages, so “distributed systems” ranks pages where those words appear together over pages that merely contain both words separately.
• Linguistic Normalization: Integrated the OpenNLP PorterStemmer library to stem words at both index and query time. At query time, the expansion is bidirectional: the frontend finds every word in the index vocabulary that stems to the same root and includes all of them in the lookup — so a search for “computing” also matches pages indexed under “compute”, “computed”, and “computation” without any rewriting by the user.
• Resilient Infrastructure: Engineered stage-specific recovery mechanisms across the pipeline, including crawler queue snapshots, deterministic index buckets, and PageRank iteration checkpoints, so long-running jobs could resume after worker timeouts or Out-of-Memory (OOM) crashes.

System Architecture & Data Flow

The system operates through a coordinator-worker model using Flame, our Spark-like distributed processing engine. Flame provides RDD-style functional operators (flatMap, flatMapToPair, foldByKey, join) that allow us to write large-scale jobs as parallel dataflow pipelines. At runtime, the Flame coordinator assigns each worker a non-overlapping key range from the KVS table, so workers scan and process their slice of the data independently in parallel — the same data-partitioning model at the core of Apache Spark.

1. Distributed Crawler: Discovers and archives raw HTML into a persistent KVS table, enforcing robots.txt rules and crawl delays per host, filtering non-HTML and non-English content, normalizing relative URLs to absolute URLs to prevent duplicate crawling, and blacklisting calendar/archive URL patterns to avoid infinite crawl loops.
2. Inverted Indexer: A distributed Flame job that strips boilerplate tags, tokenizes text with positional tracking, and computes TF-IDF scores across the corpus.
3. Offline Ranking Engine: Computes global authority via iterative PageRank jobs and outputs pt-pageranks for online lookup.
4. Search Retrieval Frontend: A low-latency service that computes score online using pt-index + pt-pageranks, applies dynamic boosts, reads titles from pt-documentStats, and lazily extracts 350-character contextual previews from cached HTML.
5. Distributed Key-Value Store (KVS): A thread-safe persistent storage layer built from scratch, backing all pipeline stages. Implements atomic row versioning, compare-and-swap conditional writes, and partitioned on-disk storage across worker nodes — giving the pipeline a reliable, concurrent foundation without an off-the-shelf database.

Ranking Engine: TF-IDF & PageRank

TF-IDF (Relevance)

Term Frequency-Inverse Document Frequency measures how relevant a page is to your search. A term’s final weight is normalizedTF × IDF, where visibility weighting is incorporated into the TF step (see Weights below).

• TF: How often your word appears on a page, normalized against the most frequent term in that same document. This prevents a long page where “apple” appears 5 times from automatically beating a short, focused page where “apple” is the dominant word.
• IDF: Computed as log(N / df), where N is the total indexed corpus size (484,280 documents in the retained production batch) and df is the number of documents containing the term. A word like “the” appears in nearly every document, so its IDF score approaches zero. A rare word gets a much higher weight.
• Weights: Visible page text is weighted at 1.0; metadata, scripts, and hidden tags at 0.001 — preventing hidden SEO keyword stuffing from inflating scores.

Iterative PageRank (Authority)

PageRank measures “trust” by treating links as votes. Our implementation is based on the original Brin & Page (1998) PageRank formula — reading the paper and deriving the algorithm from it was part of the course — computing scores on hashed URLs using an iterative loop. Each page state tracks currentRank, previousRank, and outlinks.

Link Graph Construction: During crawling, each page’s outbound hyperlinks are extracted from its HTML and stored alongside the page content in the KVS. PageRank reads this stored link graph — treating each hyperlink as a directed vote of authority from one page to another — and iterates over it until scores converge across the corpus.

1. Transfer Step: A page takes 85% of its rank and divides it equally among its outlinks. A link from a page with few outlinks provides a “stronger” vote than one with thousands.
2. Aggregation: Pages sum all incoming contributions and add a 0.15 baseline to find their newRank.
3. Convergence: The job continues until 95% of pages are “stable”—meaning their score changed by less than 0.01 since the last loop. This specific threshold ensures accuracy without wasting compute time or crashing the server due to OOM.

Final Scoring: Typing vs. Searching

Our system distinguishes between quick suggestions and full search results:

• The Suggestions (/suggest): When you type, the engine uses a fast binary search on a sorted dictionary to finish your words. No complex scoring happens here.

• The Full Search (/search): Once you hit enter, the engine runs the full retrieval pipeline:

  1. Batch KVS Read: All term rows are fetched from pt-index in parallel through a bounded thread pool — rather than one blocking network round trip per search term to the distributed KVS — then pt-pageranks and pt-documentStats are joined in memory. Parallelizing minimizes distributed latency on every query.
  2. Core Combine: (base_tfidf * phrase_boost) * (1.0 + pagerank) where phrase_boost = 1.5× if all query terms appear adjacently in the document, 1.0 otherwise.
  3. Heuristic Multipliers:
     • Multi-term coverage: Documents matching all query terms get a 4.0x boost.
     • Title Alignment: Matches in the page <title> receive up to a 4.0x boost.
     • URL Matching: Terms found in the URL path grant up to a 5.0x boost.

Final Score = Core Combine * Coverage Boost * Title Boost * URL Boost

Engineering Challenges

Making Search Results Reliable on Messy Web Data

A major challenge was that real web pages are noisy. Many pages contained broken HTML, repeated boilerplate, metadata-heavy scripts, and SEO-stuffed keyword blocks that made irrelevant pages look more important than they were. In some cases, a document ranked highly even though the query terms barely appeared in the visible page content; they were buried in <meta> tags or keyword fields.

To improve relevance, we changed the indexing pipeline to separate visible text from metadata. Visible page text was weighted normally at 1.0, while metadata keywords were given only a tiny contribution at 0.001, so hidden SEO tricks could not overpower the actual page content. We retained stopwords and their positions for phrase matching, skipped unnecessary stemmed variants, capped their posting lists more aggressively, and avoided distributed lookups for single-term stopword queries.

This was also a performance problem. Malformed HTML and regex-heavy cleaning slowed the indexer at scale, so we moved toward faster character-level tokenization and reduced unnecessary intermediate key-value pairs. These changes made the indexer both more accurate and more scalable across hundreds of thousands of pages.

Keeping Distributed Jobs Stable at Scale

Long-running crawl, index, and PageRank jobs exposed a different kind of challenge: reliability. The system had to handle oversized pages, unstable network responses, unexpected content types, worker timeouts, and large intermediate data structures. Early versions could stall, crash, or slow down significantly under load.

The most severe instance of this was the indexer itself: early versions couldn’t get past a few hundred thousand crawled pages — well short of the eventual 1,001,925-record production crawl — before exhausting memory. The root cause was that it reloaded document-length and max-term-frequency stats from pt-documentStats on every hash bucket instead of once, and merged the existing index into memory in bulk rather than lazily. I moved that stats load to happen a single time before the bucket loop and switched index merging to a lazy, per-bucket read instead of materializing the whole index up front. That fix is what let the full-scale crawl finish indexing at all.

PageRank had a parallel version of the same problem. Each iteration pulled all intermediate page-rank state back to a single coordinator with .collect(), then wrote it out row-by-row with individual kvs.put() calls — and separately called kvs.count(), a full table scan, just to log a progress number. I replaced the collect-and-loop with a distributed saveAsTable() write and dropped the repeated count() scans. On an 18,000-page benchmark this took the job from approximately 45 minutes to 21–22 minutes on clean runs (about 30 minutes under a thermally throttled one) — more than halving runtime by removing the same coordinator-concentration bottleneck that had been choking the indexer.

We improved stability through defensive parsing, stricter validation, retry logic, and system-level tuning. Adjusting worker counts, coordinator concurrency, thread pools, and hash bucket sizes helped us find a better balance between parallelism and overhead. We also added stage-specific recovery mechanisms so the crawler could restore its queue, the indexer could skip completed buckets, and PageRank could resume from a completed iteration instead of restarting the entire pipeline.

Constant-Factor Wins vs. Real Complexity Changes

Not every large speedup comes from changing an algorithm’s complexity class, and it’s worth being able to tell the two apart. The indexer’s record-parsing hot path — which ran on every token across the entire corpus — was dominated by String.split() calls using regex patterns like "\\|" and "\\s+". Replacing them with manual indexOf/substring scans that extract only the needed fields cut real wall-clock time by skipping regex compilation and full-array tokenization on every call. But it’s still O(n) in the length of the string being parsed — same complexity class, smaller constant factor.

The frontend’s query cache (see above) is the actual complexity-class change: without it, every search — including an exact repeat of a query someone had just run — recomputed the full TF-IDF/PageRank scoring pass, work that scales with the size of the matching postings lists, O(n). Keying a HashMap on the normalized query turns a repeat search into a single O(1) lookup. The parsing rewrite was worth doing but wouldn’t have saved us at scale on its own; the cache is the one change that makes repeat traffic essentially free regardless of corpus size.

Validating the Pipeline Through Internal Tooling

One of the trickiest debugging moments came from our internal KVS UI, which we used to inspect worker tables and verify that the crawl/index pipeline was producing the expected data. During testing, the UI reported about 5x more pagination pages than the actual number of indexed rows, which initially suggested that the indexer might be emitting empty rows, duplicate output, or incorrect intermediate data.

We traced the issue across worker tables, intermediate outputs, and coordinator logic, then validated the indexed rows directly. This confirmed that the production pipeline was correct: the inflated count came from the debugging UI’s pagination logic, which counted empty worker partitions as pages even though they did not represent actual indexed documents.

By separating a true pipeline defect from an internal observability issue, we avoided spending more time on non-critical tooling and stayed focused on the search path that mattered most: crawling, indexing, ranking, and retrieval.

Concurrency: Bucketing and Thread Safety

AskSauron runs multiple Flame workers, a bounded 16-thread index-write pool, and concurrent frontend requests at the same time. The core challenge is making sure no two things ever corrupt the same piece of data without adding so many locks that everything slows to a crawl.

The strategy: partition the work first, lock only what you can’t avoid.

Hash Bucket Partitioning (Indexer)

The indexer can’t process all 484,280 retained documents at once because that would exhaust memory. Instead, every URL is deterministically assigned to one of 100 buckets based on its hash: Math.abs(url.hashCode()) % 100. Bucket 0 always contains the same set of URLs, bucket 1 always contains a different set, and so on.

The indexer processes one bucket at a time. Within a bucket, a 16-thread pool writes computed index entries to the KVS in parallel. This is safe because each term maps to its own unique KVS row — two threads writing entries for “apple” and “banana” are touching completely separate rows, so no locking is needed between them. Every 5 buckets, plus the final one, a checkpoint row is written to pt-indexer-batch-checkpoint. If the job crashes mid-run, it reads that table on resume and skips buckets already marked complete.

Thread Safety by Layer

The key insight is that most of the system never needs an explicit lock at all. The per-row file layout in the KVS and hash bucket partitioning in the indexer mean threads are working on entirely separate data by design. Where shared state is unavoidable, primitives like ConcurrentHashMap, AtomicInteger, and Collections.synchronizedSet() handle locking internally. An explicit synchronized block only appears in the frontend search cache — because evicting an entry and inserting a new one must happen as a single atomic unit across three steps, which no single ConcurrentHashMap call can guarantee.

Reflections: What We’d Do Differently

Cache Eviction Strategy

The search result cache evicts arbitrarily — when the 1,000-entry cap is hit, it removes whatever .keySet().iterator().next() returns, with no recency or frequency tracking. LRU (LinkedHashMap with accessOrder=true and removeEldestEntry()) would be a straightforward improvement, always evicting the least recently used entry. For a search engine specifically, LFU (Least Frequently Used) would likely be even better: chronically popular queries like “weather” or “news” should stay cached even when they haven’t been queried recently, since they represent steady traffic that benefits most from caching. LRU can evict them when briefly displaced by a burst of novel queries; LFU would keep them.

Multi-Node Deployment

The entire pipeline ran on a single server due to project timeline constraints. The software architecture is fully distributed — KVS coordinator, KVS workers, Flame coordinator, and Flame workers all communicate over HTTP and are designed to run on separate hosts — but hardening for real multi-node operation would require revisiting load balancing across KVS workers, fault-tolerant coordinator state, and partial-failure handling that we didn’t have time to build out.

BM25 Instead of TF-IDF

TF-IDF has two practical problems that become obvious at scale:

1. No document-length normalization. Consider two pages both focused on apples: a 5,000-word guide and a 50-word summary. If “apple” is the most frequent term in both, our TF normalization gives them the same score. The shorter, denser page is likely more relevant — but without accounting for overall document length, the ranking can’t tell.

2. Unbounded term frequency. A page that repeats “apple” 200 times ranks 200× higher than one that mentions it twice. After a few mentions, more repetitions don’t signal more relevance — the page is either just very long or keyword-stuffing for SEO.

BM25 fixes both: it adds a length normalization factor so short focused pages compete fairly with long ones, and a TF saturation curve so the 200th mention barely moves the needle over the 10th. It is the default ranking algorithm in Elasticsearch and Apache Lucene, the two most widely deployed open-source search engines, precisely because it consistently outperforms plain TF-IDF in practice. It would have been a near-direct replacement in our indexer.