Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Full-Text Search Engine from Scratch

Welcome to the Full-Text Search Engine from Scratch course!

In this module, you will design and build a full-text search engine from the ground up. We aren’t just hooking up an Elasticsearch instance or writing a SQL LIKE query. We’re getting our hands dirty with the actual data structures and algorithms that power modern search infrastructure like Apache Lucene.

By the end of this course, you will understand inverted indices, text normalization, boolean search logic, term frequency weighting, TF-IDF, the industry-standard BM25 algorithm, and the Log-Structured Merge architecture that allows Lucene to scale to terabytes of data.

Tip

If you’ve ever wondered how Google or Lucene pull off sub-millisecond full-text queries across terabytes of data, this is where you learn the foundational concepts. It’s not magic, it’s just really good data structures.

The Rules of the Game

You can write your search engine in any programming language you want, using any standard HTTP framework (e.g., Axum, Express, Spring Boot, Go net/http). We are testing your search algorithms, not your ability to handle raw TCP sockets.

However, you must adhere to one critical rule: No Search Libraries.

You cannot use Lucene, ElasticSearch, Meilisearch, SQLite FTS, or any other out-of-the-box search library. You must write the indexing and querying data structures yourself.

The API Contract

Your engine will expose a REST API. It will start simple and grow as you progress through the stages:

  1. Ingest a Document: POST /document/{id} (Body: raw text/plain)
  2. Search for Documents: GET /search?q={query}&limit={k} (Returns text/plain comma-separated Doc IDs)
  3. Delete a Document: (Introduced in later stages) DELETE /document/{id}
  4. Trigger Compaction: (Introduced in later stages) POST /merge
  5. Reset Engine: (Required from Stage 1) DELETE /index

Important

Why do we need DELETE /index? The evaluation suite will test your engine extensively by throwing thousands of documents at it across 12 different stages. To ensure that stale documents from Stage 3 don’t mathematically pollute the global BM25 scoring algorithms in Stage 8, the test runner will call DELETE /index at the very beginning of every single test. This endpoint must instantly wipe all data (clearing the RAM buffer, emptying tombstones, and deleting disk segments) and return 200 OK, giving the next test a perfectly clean slate.

How the Evaluation Suite Works

You will run your server locally, and our Dockerized test runner will fire HTTP requests at it to validate your implementation.

docker run \
  --rm \
  --add-host host.docker.internal:host-gateway \
  codeberg.org/level0/buildit/search-engine:latest \
  --addr host.docker.internal:8080

What this command does:

  • --rm: Cleans up the container after the tests finish.
  • --add-host host.docker.internal:host-gateway: Ensures the container can communicate with your local machine’s localhost.
  • --addr: Tells the tester where to find your server.

Note

Instead of running the entire suite of tests every time, the runner uses an --until flag. This flag tells the tester to run all previous stages up to, and including, the stage you are currently working on. This ensures you haven’t broken any past functionality while building the new feature. At the end of every lesson, you will be provided with the exact docker run command required to evaluate that specific stage.

Ready? Let’s start with the worst possible way to build a search engine. Head over to The Linear Scan.

The Linear Scan

Lets start off with something simple first – a brute-force Linear Scan.

Yes, it’s an O(n) disaster waiting to happen. Yes, if we ingest 10 million documents the server will catch fire. But Starting with a Linear Scan lets us define our API structure and understand the basic search flow before optimizing it with more advanced data structures.

Your Task

  1. Ingest endpoint (POST /document/{id}): Read the flat text from the request body and store it in memory. A simple map of Document ID -> Text is ideal here. If a document with the same {id} already exists, simply overwrite the old text with the new text. Return 201 Created.

    For example, we will use the following three text files. We will use their filenames as the Document IDs:

    red_apple.txt     -> The red apple is a sweet apple.
green_apple.txt   -> The Green Apple is sour!
rolling.txt       -> The red apples are rolling.

  2. Search endpoint (GET /search?q={term}&limit={k}): When a query comes in, loop through every single document in memory. Check if the query string is a substring of the document text. Return a comma-separated list of the Document IDs that matched (e.g., red_apple.txt,rolling.txt). If the number of matches exceeds {k}, truncate the list to length {k}. Return 200 OK.

  3. Reset endpoint (DELETE /index): When called, simply clear the in-memory map/array. This ensures that the automated evaluation suite can run tests repeatedly against a clean slate without stale data bleeding over. Return 200 OK.

Warning

Do not worry about lowercase, punctuation, or complex tokenization yet. If the document says Hello, World! and the query is world, it should not match (because of the lowercase w). Keep it strictly literal. Substring matching and basic array slicing for the limit is perfectly fine for this stage.

Important

Run the below docker command to test your solution.

docker run \
  --rm \
  --add-host host.docker.internal:host-gateway \
  codeberg.org/level0/buildit/search-engine:latest \
  --addr host.docker.internal:8080 \
  --until linear_scan

The Inverted Index

Now lets start thinking about how we can improve the search performance from the previous linear scan approach. Instead of scanning through all the documents, we can use an Inverted Index.

An Inverted Index maps Word -> Document IDs.

When a document comes in, we chop it up into individual words (tokens), and for each word, we record that this document contains it.

Your Task

  1. Ingest Endpoint: When you receive text, tokenize it by splitting on spaces (whitespace). Maintain a global Inverted Index: a map where the key is a Term (string), and the value is a Set (or List) of DocIds.

    The Inverted Index would look like this:

    Apple       -> { green_apple.txt }
Green       -> { green_apple.txt }
The         -> { green_apple.txt, red_apple.txt, rolling.txt }
a           -> { red_apple.txt }
apple       -> { red_apple.txt }
apple.      -> { red_apple.txt }
apples      -> { rolling.txt }
are         -> { rolling.txt }
is          -> { green_apple.txt, red_apple.txt }
red         -> { red_apple.txt, rolling.txt }
rolling.    -> { rolling.txt }
sour!       -> { green_apple.txt }
sweet       -> { red_apple.txt }

  2. Search Endpoint (GET /search?q={term}&limit={k}): When a query comes in for a single term, simply look up that term in your Inverted Index Map. Return the Set of Document IDs as a comma-separated list, up to the maximum limit. If the term isn’t in the map, return an empty response.

Tip

Keep it simple. We are still not worrying about lowercasing or punctuation. Just split by the space character and use those exact tokens as keys.

Important

Run the below docker command to test your solution.

docker run \
  --rm \
  --add-host host.docker.internal:host-gateway \
  codeberg.org/level0/buildit/search-engine:latest \
  --addr host.docker.internal:8080 \
  --until inverted_index

Text Normalization

You shipped the inverted index. Lookups are blazing fast. Great job!

But when users search for Apple!, nothing showed up.

Computers are stubbornly, strictly literal. To your code, the strings apple, Apple and Apple! are completely different sequences of bytes. Humans, on the other hand, are messy and expect the search engine to just “figure it out.”

If we want a good search experience, we cannot just split on spaces and dump the raw tokens into our index. We need an Ingestion Pipeline that normalizes the text into a standard format.

Your Task

Before you index a document, you must push its text through a pipeline:

  1. Lowercase everything: Convert all characters to lowercase.
  2. Strip punctuation: Remove any character that is not alphanumeric (keep only a-z, 0-9 and whitespace ).
  3. Tokenize: Split by space to get the terms.

The Inverted Index should now look like this:

a           -> { 'red_apple.txt' }
apple       -> { 'green_apple.txt', 'red_apple.txt' }
apples      -> { 'rolling.txt' }
are         -> { 'rolling.txt' }
green       -> { 'green_apple.txt' }
is          -> { 'green_apple.txt', 'red_apple.txt' }
red         -> { 'red_apple.txt', 'rolling.txt' }
rolling     -> { 'rolling.txt' }
sour        -> { 'green_apple.txt' }
sweet       -> { 'red_apple.txt' }
the         -> { 'green_apple.txt', 'red_apple.txt', 'rolling.txt' }

Crucially, you must apply this exact same normalization pipeline to incoming search queries! If users search for Apple!, you need to normalize it, resulting in looking up apple in your index.

Important

Run the below docker command to test your solution.

docker run \
  --rm \
  --add-host host.docker.internal:host-gateway \
  codeberg.org/level0/buildit/search-engine:latest \
  --addr host.docker.internal:8080 \
  --until normalization

Multi-Term Queries

Till now we have searched for single words like apple. But what if the user query contains multiple words like red apple?

Your search engine fails to return any results.

Why? Because our inverted index maps individual words to documents. If the user query contains multiple words, like red apple, our engine tries to look up the exact string red apple in the hash map. Since our index only contains single words like red and apple, the lookup fails.

When a user query contains multiple words, they usually want documents that contain all of those words. This can be achieved using Set Intersection.

Your Task

When you receive a search query (GET /search?q={query}&limit={k}), run it through your normalization pipeline just like you do for documents.

  1. If the query is a single token, return its Document IDs as before (up to the limit).
  2. If the query consists of multiple tokens, fetch the Set<DocId> for each token.
  3. Compute the intersection of all those sets and return the resulting Set<DocId> as a comma separated list (up to the limit).

For example, if you query red apple:

  • Fetch the set for red -> { 'red_apple.txt', 'rolling.txt' }
  • Fetch the set for apple -> { 'green_apple.txt', 'red_apple.txt' }
  • The intersection is { red_apple.txt }.

Important

Run the below docker command to test your solution.

docker run \
  --rm \
  --add-host host.docker.internal:host-gateway \
  codeberg.org/level0/buildit/search-engine:latest \
  --addr host.docker.internal:8080 \
  --until multi_term

Term Frequency

Your search engine successfully finds documents containing the required words. But there is a massive problem: it returns them in an arbitrary order.

If users search for apple, a document that mentions apple exactly once is treated the same as a document that mentions apple 50 times.

Welcome to the world of Relevance Ranking.

The simplest heuristic for relevance is Term Frequency (TF): if a document uses a word frequently, it’s probably about that word.

Your Task

Update the Inverted Index to store term counts.

Instead of mapping Term -> Set<DocId>, map Term -> Map<DocId, Count>.

When you index a document, count how many times each token appears in that document. When a user searches for a term, return the Document IDs sorted descending by their Term Frequency count. (If you hit the limit={k}, return only the top k results).

The Inverted Index should now look like this:

a           -> { red_apple.txt: 1 }
apple       -> { green_apple.txt: 1, red_apple.txt: 2 }
apples      -> { rolling.txt: 1 }
are         -> { rolling.txt: 1 }
green       -> { green_apple.txt: 1 }
is          -> { green_apple.txt: 1, red_apple.txt: 1 }
red         -> { red_apple.txt: 1, rolling.txt: 1 }
rolling     -> { rolling.txt: 1 }
sour        -> { green_apple.txt: 1 }
sweet       -> { red_apple.txt: 1 }
the         -> { green_apple.txt: 1, red_apple.txt: 1, rolling.txt: 1 }

When querying for apple, your search endpoint should return red_apple.txt,green_apple.txt because red_apple.txt has a higher Term Frequency.

Multi-Term Queries

In the previous stage, you implemented multi-term queries by computing the intersection of document sets (returning only documents that contain every queried word).

Now that we are tracking Term Frequency, how do we rank a document when a user query contains multiple words, like the apple?

  1. Find the intersecting documents just like before. A document must contain both the and apple to be considered a match.
  2. To calculate the document’s total relevance score, sum its Term Frequencies for each of the queried words.

For example, for the query the apple:

the     -> { green_apple.txt: 1, red_apple.txt: 1, rolling.txt: 1 }
apple   -> { green_apple.txt: 1, red_apple.txt: 2 }
  • The intersection is { green_apple.txt, red_apple.txt }.
  • Calculate the total scores for the matching documents: { green_apple.txt: 1+1, red_apple.txt: 1+2 }

Since 3 > 2, your engine should return red_apple.txt,green_apple.txt.

Important

Run the below docker command to test your solution.

docker run \
  --rm \
  --add-host host.docker.internal:host-gateway \
  codeberg.org/level0/buildit/search-engine:latest \
  --addr host.docker.internal:8080 \
  --until term_frequency

Query-Time Inverse Document Frequency (TF-IDF)

The Term Frequency model has a massive blind spot: it doesn’t know which words actually matter.

If a user queries for the apple, the word apple carries all the meaning. The word the is just grammar noise.

But your engine just counts hits. If you have a massive, unrelated document that happens to use the word the 10,000 times, its score will be 10,000! It will completely bury a short apple pie recipe document that mentions apple 10 times.

This is absurd. We need to mathematically penalize useless, common words, and boost words that are rare and meaningful.

Enter TF-IDF (Term Frequency - Inverse Document Frequency).

The Intuition

How do we teach a computer that apple is important but the is garbage?

We look at how rare the word is across our entire dataset.

  • If we have 1,000 documents, and the appears in 999 of them, it is completely useless for finding specific information.
  • If apple appears in only 5 documents, it is a highly specific, valuable signal.

Therefore, a term’s weight should be inversely proportional to how many documents it appears in.

The Math

Instead of just using Term Frequency (TF), we multiply it by the Inverse Document Frequency (IDF).

$$ \text{TF}(t, d) = \text{Count of term } t \text{ in document } d $$ $$ \text{IDF}(t) = \ln \left( \frac{N}{\text{df}(t)} \right) $$

  • N: The total number of documents in your index.
  • df(t): The Document Frequency (how many unique documents contain term t).

Let’s break down why this formula is brilliant:

  1. N / df(t): If a word t appears in every single document (N == df(t)), the fraction is exactly 1. If a word is incredibly rare and only appears in, say, 2 (out of 1000) documents, the fraction is huge (1000 / 2 = 500).

  2. ln(N / df(t)): If we just multiplied by 500, extremely rare words would completely break the scoring scale. The natural logarithm smooths this out, reigning in massive spikes (ln(500) ≈ 6.215).

  3. ln(1): What is the logarithm of 1? It’s zero. If a word like the appears in every single document (N == df(t)), its IDF is exactly 0. When you multiply TF * 0, the score for that useless word is completely destroyed!

NOTE:

the actual IDF formula used in most production systems is slightly different. And it is the one this course recommends!

$$ \text{IDF}(t) = 1 + \ln \left(\frac{N}{\text{df}(t) + 1} \right) $$

  1. df(t) + 1: Adding 1 to the denominator (often called Laplace smoothing) prevents a fatal division by zero error if a queried term doesn’t exist in any document at all.
  2. 1 + ln(...): If a word like the appears in almost every document, N / (df(t) + 1) approaches 1. The natural logarithm of 1 is 0. By adding a base of 1, we ensure that the IDF never drops to exactly zero. Even extremely common words will contribute a tiny amount to the final score rather than completely zeroing out the Term Frequency.

Critical Architecture Note: Why Query-Time?

You might be tempted to calculate the final TF-IDF score for every word when you POST a document, and store that float in your Inverted Index. Do not do this.

Why? Because N (total docs) and df (document frequency) change every single time you add a new document. If you store the final score in your index during ingest, you would have to recalculate and rewrite the score for every single document in the entire system whenever a new document is added.

Real engines like Apache Lucene never do this. Instead, during ingest (POST), you only store the raw, static statistics: Term Frequency (TF), Document Frequency (DF) and the raw text.

The actual math (calculating the IDF and multiplying it by TF) happens on-the-fly during the GET request.

Your Task

  1. Track N (the total number of documents).
  2. Track df(t) (how many documents contain term t).
  3. When a GET request arrives, for each term in the query, calculate its TF-IDF score dynamically for each matching document: score = TF * IDF.
  4. If a query has multiple terms, sum the TF-IDF scores for the document.
  5. Return the Document IDs sorted descending by this new TF-IDF total score.

For example, applying this to our index (N = 3):

the     -> df = 3; IDF = 1 + ln(3 / (3 + 1)) ≈ 0.712
apple   -> df = 2; IDF = 1 + ln(3 / (2 + 1)) = 1

Query: "the apple"
red_apple.txt   -> (tf(the) * idf(the)) + (tf(apple) * idf(apple)) = (1 * 0.712) + (2 * 1) = 2.712
green_apple.txt -> (tf(the) * idf(the)) + (tf(apple) * idf(apple)) = (1 * 0.712) + (1 * 1) = 1.712
rolling.txt     -> (tf(the) * idf(the)) + (tf(apple) * idf(apple)) = (1 * 0.712) + (0 * 1) = 0.712

Warning

Because floating-point math can be slightly imprecise across languages, our tests do not assert exact float values. We only assert the relative ordering of the results. As long as your formula is correct, the documents will sort perfectly!

Important

Run the below docker command to test your solution.

docker run \
  --rm \
  --add-host host.docker.internal:host-gateway \
  codeberg.org/level0/buildit/search-engine:latest \
  --addr host.docker.internal:8080 \
  --until tf_idf

Stop Words

Your TF-IDF scoring is beautiful, but you’re starting to notice something ugly: your server’s RAM usage is going through the roof.

Why? Because your Inverted Index is storing an entry for words like is, a, and the for almost every single document in your system. These words don’t help us find anything useful, but they consume massive amounts of memory.

Furthermore, a user just complained that searching for roll returned zero results, even though you have a document containing rolling.

Let’s introduce some pragmatic heuristics to our ingestion pipeline to save RAM and improve our search recall.

Your Task

Expand your Ingestion Pipeline. After you tokenize the normalized text, you must pass the tokens through a Stop Words Filter:

Update your text normalization pipeline (which runs on both ingested documents and search queries).

  1. Stop Words Filter: After tokenizing, completely discard any token that exactly matches this list: a, an, and, are, as, at, be, but, by, for, if, in, into, is, it, the

  2. Stemming Heuristic: After removing stop words, strip the suffixes ing and s from the end of the remaining tokens.

    • running -> runn (or run depending on how you implement it. The test will pass as long as it’s consistent).
    • dogs -> dog

For example, applying the full pipeline to The red apples are rolling. drops the and are, yielding [red, apple, roll].

The Inverted Index should now look like this:

apple    -> { green_apple.txt: 1, red_apple.txt: 2, rolling.txt: 1 }
green    -> { green_apple.txt: 1 }
red      -> { red_apple.txt: 1, rolling.txt: 1 }
roll     -> { rolling.txt: 1 }
sour     -> { green_apple.txt: 1 }
sweet    -> { red_apple.txt: 1 }

Crucially, you must apply this exact same filter to incoming search queries! If the user searches for the apple, you need to drop the stop word the, resulting in just looking up apple in your index.

Tip

Real-world stemming algorithms (like the Porter Stemmer) are complex state machines that handle thousands of linguistic edge cases (ponies -> pony). You do not need to implement a real stemmer here! Just a naive suffix strip for "ing" and "s" is enough to pass the test and understand the concept.

Important

Run the below docker command to test your solution.

docker run \
  --rm \
  --add-host host.docker.internal:host-gateway \
  codeberg.org/level0/buildit/search-engine:latest \
  --addr host.docker.internal:8080 \
  --until stem_and_stop

BM25 - The Industry Standard

TF-IDF is a great conceptual starting point, but it has two fatal flaws that break down at scale:

  1. Keyword Stuffing (Linear Scaling): In TF-IDF, if a document repeats a word 100 times, its score is 100x higher than a document mentioning it once. This makes it trivially easy for spammers to game the system by stuffing keywords at the bottom of a page.
  2. Length Bias: A 1,000-page Terms of Service document that casually mentions “apple” 50 times will completely outrank a 2-page apple pie recipe that mentions it 40 times. TF-IDF does not care how long the document is; it only cares about raw counts.

It’s time to upgrade your engine to the industry standard used by Elasticsearch and Lucene: Okapi BM25.

The Concepts

BM25 fixes TF-IDF by introducing two new concepts:

  • Term Frequency Saturation: Using a constant k_1, BM25 curves the TF score. After a certain number of occurrences, repeating the word over and over stops increasing the score. It plateaus.
  • Document Length Normalization: Using a constant b, BM25 penalizes long documents. If a document is much longer than the average document in the index, its term frequency counts for less.

The Math

You will replace your score = TF * IDF calculation with the BM25 formula.

First, calculate the standard IDF exactly as before: $$ \text{IDF}(t) = 1 + \ln \left(\frac{N}{\text{df}(t) + 1} \right) $$

Then, calculate the BM25 score for a term t in document d: $$ \text{Score}(t, d) = \text{IDF}(t) \cdot \frac{\text{TF}(t, d) \cdot (k_1 + 1)}{\text{TF}(t, d) + k_1 \cdot \left(1 - b + b \cdot \frac{|d|}{\text{avgdl}}\right)} $$

Where:

  • TF(t, d): Term Frequency of term t in document d.
  • |d|: The length of document d (total number of tokens after normalization and stop word removal).
  • avgdl: The average document length across the entire corpus.
  • k_1 = 1.2 (Standard tuning constant).
  • b = 0.75 (Standard tuning constant).

Your Task

  1. Track the length |d| of every document when it is ingested.
  2. Track the sum of all document lengths so you can calculate avgdl dynamically at query time.
  3. Replace your query-time TF-IDF calculation with the BM25 calculation above.
  4. As always, sort the results descending by this score.

Important

Run the below docker command to test your solution.

docker run \
  --rm \
  --add-host host.docker.internal:host-gateway \
  codeberg.org/level0/buildit/search-engine:latest \
  --addr host.docker.internal:8080 \
  --until bm25

Top-K & Pagination

Your BM25 scoring is perfect. Your inverted index is blazing fast.

But what if you have 2 million documents in your index and a user searches for "software" which appears in 1 million documents.

Your current code does this:

  1. Finds 1,000,000 matching Document IDs.
  2. Calculates the BM25 score for all 1,000,000 documents.
  3. Pushes all 1,000,000 documents into a massive Array in RAM.
  4. Sorts the entire 1,000,000-element Array O(N log N).
  5. Slices the first limit=10 elements and returns them.

The problem is steps 3 and 4. Storing and sorting 1 million documents in RAM for every single concurrent search request will instantly OOM (Out-of-Memory) crash your server.

We only need the top k results. We don’t care about sorting the 999,990 losers.

The Solution: A Min-Heap

Instead of sorting the entire array at the end, we can maintain a Priority Queue (specifically, a Min-Heap) of size k (where k is the limit parameter).

As you iterate through the matching documents and calculate their scores:

  1. If the heap has fewer than k elements, just push the document in.
  2. If the heap is full (size k), compare the current document’s score to the smallest score in the heap (which sits at the root of a Min-Heap, O(1)).
  3. If the current document’s score is larger than the root, pop the root (O(log k)) and push the new document (O(log k)).
  4. If it’s smaller, just ignore the document entirely.

This reduces our memory footprint from O(N) to O(k), and our time complexity drops significantly!

Your Task

Update your GET /search endpoint. Stop collecting all results into a massive array.

Initialize a Priority Queue / Min-Heap sized to the limit={k} query parameter. Feed the documents into the heap as you score them. Once you’ve evaluated all matches, the heap will contain exactly the top k highest-scoring documents.

Pop them out, sort them descending (since the heap pops smallest first), and return them.

Note

Some languages call this a PriorityQueue, MinHeap, or BinaryHeap. Make sure you configure it so that the element with the lowest score is at the top (popped first).

Important

Run the below docker command to test your solution.

docker run \
  --rm \
  --add-host host.docker.internal:host-gateway \
  codeberg.org/level0/buildit/search-engine:latest \
  --addr host.docker.internal:8080 \
  --until top_k

RAM Buffers & Immutable Segments

Everything you have done until this point was strictly in-memory. If your server restarts or crashes, all your indexed data will be lost. It’s time to persist your data to disk.

Why don’t we just write the entire Inverted Index map to a index.json file on disk every time a user calls POST /document/{id}?

Because doing that will melt your SSD and freeze your server.

If your index grows to 5GB, writing 5GB to disk synchronously on every single HTTP POST is an I/O disaster. Furthermore, modifying a single massive file on disk while concurrent queries are reading from it requires complex thread locking that will destroy your search latency.

The Lucene Architecture

Apache Lucene (the engine behind Elasticsearch) solves this brilliantly using a hybrid approach: In-Memory Buffering and Immutable Segments.

  1. In-Memory Buffering: When you POST a new document, the data is not immediately written to the hard drive. Lucene holds the new data in an internal RAM buffer.
  2. Flushing to Disk: The buffer stays in memory until it hits a specific trigger limit (e.g., maximum RAM size, or a set document count). Once tripped, Lucene flushes the data to the storage directory.
  3. Immutable Segments: The flushed data is written out as a brand-new, independent index segment file (e.g., segment_1.json). Existing segments on the disk are never modified or touched during this flush process.
  4. Read-Only Speed: Because segments are strictly immutable once written, you don’t need write-locks to search them! Search is incredibly fast and completely thread-safe.

Your Task

  1. When a POST /document/{id} request arrives, ingest it into your standard In-Memory Inverted Index (acting as the RAM buffer).
  2. If the RAM buffer reaches exactly 5 documents, you must trigger a flush.
  3. Serialize the entire in-memory Inverted Index (and document length stats) and save it to a new file in a persistent directory (e.g., /file_serving/segment_1.json, then /file_serving/segment_2.json, etc.).
  4. Clear the RAM buffer completely.
  5. Update your Reset Endpoint: Remember your DELETE /index endpoint from Stage 1? Now that you are persisting data to disk, you must update that endpoint to not only clear your RAM buffer, but also physically delete all segment files from your storage directory. If you forget to do this, the evaluation suite will fail because it will accidentally read stale segment files from previous tests!

Note

For this stage, the test runner will only verify that the segment file is created on the filesystem. It will not query the data yet! (We will tackle searching across segments in the next stage).

Important

Run the below docker command to test your solution. Note that we map the /file_serving directory to the container so the runner can inspect your segment files!

docker run \
  --rm \
  --add-host host.docker.internal:host-gateway \
  -v /tmp/buildit_segments:/file_serving \
  codeberg.org/level0/buildit/search-engine:latest \
  --addr host.docker.internal:8080 \
  --until segments

Multi-Segment Search

Now that our data is scattered across an active RAM buffer and multiple immutable segment files on disk, how do we actually search it?

We can’t just query the RAM buffer, because we’d miss the flushed documents. We can’t just query the segment files, because we’d miss the newest documents in the RAM buffer.

When a query comes in, the search engine must look at everything.

The Task

Update your GET /search endpoint to perform a Multi-Segment Search:

  1. Calculate Global Stats: To properly score documents using BM25, the engine needs accurate global stats (N and avgdl). You must aggregate the total number of documents and the total length of all documents across both the active RAM buffer and all flushed segment files on disk.
  2. Execute the Query: For the queried terms, fetch the matching Document IDs from the RAM buffer and from every single segment file.
  3. Score & Heapify: Score every matching document using the aggregated global stats. Pass all the scored documents through your Min-Heap exactly as you did in Stage 8, regardless of whether the document came from RAM or disk.
  4. Return Results: Return the sorted top K results.

Tip

Do not load the entire segment files into memory on every request. While that works for small tests, it’s terrible practice. At the very least, you should read them, aggregate the necessary stats/hits, and drop them from memory immediately. (Real engines use memory-mapped files and mmap to let the OS handle page caching, but you can just do standard file reads for this project).

Important

Run the below docker command to test your solution.

docker run \
  --rm \
  --add-host host.docker.internal:host-gateway \
  -v /tmp/buildit_segments:/file_serving \
  codeberg.org/level0/buildit/search-engine:latest \
  --addr host.docker.internal:8080 \
  --until multi_segment

Tombstones & Deletions

Till now we have only added documents to our engine. What about deleting them?

But wait. In the Lucene architecture, our segment files on disk are completely immutable. They are read-only. How do you delete data from a read-only file without rewriting the entire file and blocking concurrent searches?

You don’t.

Instead of actually deleting the data, we use a Write-Once strategy with Soft Deletes (Tombstones).

The Concept

When a deletion request comes in, we don’t touch the immutable segments. We simply record the Document ID in a “Tombstone Set”.

When a search query runs, we still find the deleted document in the segment file, but before we score it and add it to our Min-Heap, we check the Tombstone Set. If the ID is in the set, we skip it. The document effectively becomes invisible to the user, even though the raw bytes are technically still sitting on the hard drive.

Furthermore, how do we handle document updates? Simple: an update is just a Delete + Insert. You add the old Document ID to the Tombstone Set, and insert the newly updated text as a brand new document in your active RAM buffer.

Your Task

  1. Delete Endpoint (DELETE /document/{id}): Add this new endpoint. When called, it should append the {id} to an in-memory Set of deleted IDs. Return 204 No Content.
  2. Persistence: Just like the RAM buffer, if the server crashes, we lose our tombstones. You must persist this set to disk (e.g., appending to a tombstones.del file).
  3. Filter Searches (GET /search): Update your search logic. Before you score a matching document and push it into your Top-K Min-Heap, check if its ID exists in the Tombstone set. If it does, ignore it.
  4. Handling Updates (POST /document/{id}): If a POST request comes in for an ID that already exists (an update), you must “kill” the old version existing in the disk segments, and insert the new text into your active RAM buffer.

Note

The Update Trap: If you blindly add doc1 to a global Tombstone set, and then insert the new doc1 into the RAM buffer, your search logic might accidentally filter out the new version too because the ID is exactly the same! How do you tombstone the old disk version but keep the new RAM version alive?

The Solution (The Precedence Rule): Make your Tombstone set only apply to disk segments.

  • If the old version is in the RAM buffer: You don’t even need tombstones! Because the RAM buffer is a mutable data structure, just physically delete or overwrite the old document’s data in the RAM buffer.
  • If the old version is on disk: Add it to the Tombstone set. When aggregating search results later, if doc1 is found in the active RAM buffer, it automatically takes precedence. You only check the Tombstone set when evaluating hits from the immutable disk segments.

Note

What about Global Stats? When you soft-delete a document, do not try to decrement the global N (total documents) or avgdl. Doing so would require scanning the immutable segment to find the length of the deleted document, which is terrible for performance. Real engines allow these stats to become slightly inaccurate (stale) until a background Compaction (next stage) physically removes the data.

  1. Update your Reset Endpoint (Again): Don’t forget to update your DELETE /index endpoint! It must now clear your in-memory Tombstone set (and delete the persistent .del file from disk) along with the segment files and RAM buffer.

Important

Run the below docker command to test your solution.

docker run \
  --rm \
  --add-host host.docker.internal:host-gateway \
  -v /tmp/buildit_segments:/file_serving \
  codeberg.org/level0/buildit/search-engine:latest \
  --addr host.docker.internal:8080 \
  --until tombstones

Segment Merging (Compaction)

You’ve built a robust, thread-safe, immutable search engine.

But over time, performance starts to degrade. Search latency increases from 10 ms to 2,000 ms, and the operating system begins terminating the process with a Too many open files error.

Why? Because every time your 5-document RAM buffer filled up, you flushed a new segment file. You now have 50,000 tiny segment files on disk. Every time a user searches, your engine has to open and scan 50,000 separate files.

Furthermore, your .del tombstone file has grown to 500MB because 50% of the documents in your index have been deleted, but their raw bytes are still wasting space inside those immutable segments.

We need Log-Structured Merge Compaction.

The Concept

Because flushing creates many small files over time, real engines use a background process called a MergePolicy to clean things up. It combines several small segment files into one larger segment file. Crucially, during this process, it physically strips out any documents that were marked as deleted in the Tombstone set. (This physical removal is the “hard delete” that finally makes us GDPR compliant!)

Your Task

  1. Merge Endpoint (POST /merge): Add this endpoint. (In reality this happens automatically in a background thread, but we use an endpoint so the test runner can trigger it deterministically).
  2. Combine Data: When called, read every single segment file from disk into memory.

    Note

    Wait, read everything into memory? For now, yes. You can just deserialize all segments into a giant Hash Map in RAM, combine them, and write it back. The next lessons will teach you how to avoid this.

  3. Purge Tombstones: As you combine the Inverted Indices, drop any Document IDs that exist in your .del Tombstone set. Do not include their stats in the new N or avgdl.
  4. Write New Segment: Write this newly combined, fully-purged Inverted Index back to disk as a single new segment file.
  5. Cleanup: Delete all the old, tiny segment files from disk. Empty your Tombstone set (and delete the .del file).

Return 200 OK.

Tip

After merging, your search engine should behave exactly as it did before, but it will only be reading from 1 file instead of 50,000, and the deleted data will finally be physically gone.

Important

Run the below docker command to test your solution.

docker run \
  --rm \
  --add-host host.docker.internal:host-gateway \
  -v /tmp/buildit_segments:/file_serving \
  codeberg.org/level0/buildit/search-engine:latest \
  --addr host.docker.internal:8080 \
  --until merging

The Write-Ahead Log (WAL)

Right now, the engine buffers 5 documents in RAM before flushing to a segment. If the power gets cut when the buffer holds 4 documents, that data is permanently destroyed. A system that drops committed writes is fundamentally broken.

Crash Recovery via Append-Only Logs

When a database tells a user 201 Created, that data must survive a power failure. But writing an entire segment file for every single document kills disk I/O.

How do real engines like Apache Lucene and PostgreSQL solve this? They use a Write-Ahead Log (WAL).

A WAL is a simple, append-only file. Appending to a file sequentially is incredibly fast because the disk head doesn’t need to seek. We write the raw, unparsed data to the WAL immediately. If the server crashes, we can replay the WAL to reconstruct the RAM buffer.

Your Task

  1. Write to the WAL: On POST /document/{id}, synchronously append the raw payload (e.g., {id}:{text}\n) to a wal.log file in your storage directory before returning 201 Created.
  2. Clear the WAL: When your RAM buffer fills up and flushes to a permanent segment file, the data is safe. Delete or truncate the wal.log file so it doesn’t grow indefinitely.
  3. Replay on Startup: When your server starts up, check if wal.log exists. If it does, read it line by line and ingest the documents into your RAM buffer before accepting HTTP traffic.
  4. Update Reset Endpoint: Update your DELETE /index endpoint to also delete the WAL file.

Important

Run the below docker command to test your solution. Note that this test will ask you to manually kill and restart your server to simulate a crash!

docker run \
  --rm \
  --add-host host.docker.internal:host-gateway \
  -v /tmp/buildit_segments:/file_serving \
  codeberg.org/level0/buildit/search-engine:latest \
  --addr host.docker.internal:8080 \
  --until wal

Alphabetical Segments & Disk-Seeking

The engine is working, but it takes 15 minutes to start up. Why? Because on startup, we are deserializing 50GB of segment files from disk into a massive in-memory Hash Map.

By loading everything into RAM, we are duplicating data that is already safely sitting on the SSD. We need to let the OS handle memory.

Memory Mapping and Disk Seeking

Real engines like Apache Lucene use mmap (Memory-Mapped Files). This tells the Operating System: “Map this file directly into virtual memory. If I read a byte, you load that page from disk into the OS Page Cache. If memory gets tight, evict it silently.”

To do this efficiently, our files cannot be a random JSON blob like { "apple": [...], "banana": [...] }. JSON parsers must read the entire file into memory to parse it. We need a flat, strictly sorted, line-by-line format.

How to Calculate Byte Offsets

Instead of holding the data in RAM, we only hold a Term Dictionary in RAM. This dictionary acts as an index to the index. It simply maps a term to the exact byte offset where that term’s data begins on disk.

When you flush your RAM buffer to a segment file:

  1. Extract all terms from your buffer and sort them alphabetically.
  2. Open a new file for writing.
  3. For each term, serialize its postings list to a string (e.g., apple:green_apple.txt=1,red_apple.txt=2,rolling.txt=1\n).
  4. Before writing, record the file’s current size (which is the current byte offset). Most languages provide a file.tell() or file.position() method. Alternatively, you can just maintain a running counter of the bytes you have written so far.
  5. Write the serialized string to the file.
  6. Add the mapping (apple -> offset) to your in-memory Term Dictionary. The offset represents where the term apple starts.

Your Task

  1. Sort & Serialize: Change how you write segment files. Serialize them line-by-line, strictly sorted alphabetically by term.
  2. The Term Dictionary (Offset Map): Maintain the Term -> Byte Offset map in memory for each segment file. (e.g., apple starts at byte 0, banana starts at byte 25, cherry starts at byte 60).
  3. Disk Seeking on Query: When a search query comes in for banana, look up its byte offset (25) in your RAM map. Open the segment file, use your language’s seek() function to jump directly to byte 25, and read exactly one line to get banana’s postings list!

By doing this, your engine’s memory footprint will plummet. You are now leaving the heavy lifting to the OS Page Cache and disk I/O controllers.

Important

Run the below docker command to test your solution.

docker run \
  --rm \
  --add-host host.docker.internal:host-gateway \
  -v /tmp/buildit_segments:/file_serving \
  codeberg.org/level0/buildit/search-engine:latest \
  --addr host.docker.internal:8080 \
  --until disk_seek

The K-Way Merge (Optimal Compaction)

Remember our /merge endpoint from Segment Merging (Compaction)? We were loading all segment files into a giant RAM Hash Map, combining them, and writing them out. Indexes can grow to hundreds of GigaBytes, or even TeraBytes!

A user just triggered a merge on a 50GB index and the server OOM crashed instantly.

Streaming Compaction

Because our segment files are now strictly sorted alphabetically line-by-line (thanks to Alphabetical Segments & Disk-Seeking), we can perform a streaming K-Way Merge. This is the exact algorithm Lucene uses to merge terabytes of data using almost zero RAM.

Instead of loading files into RAM, we load Iterators. An Iterator just holds a pointer to a file and fetches one line at a time. By comparing the current line of K iterators, we can merge infinite amounts of data!

Concurrent Merging (Background Compaction)

Concurrent Merging: Real engines run compaction algorithms asynchronously in the background so writes are never blocked.

If a merge takes 5 minutes to complete on a 100GB index, your /merge HTTP endpoint cannot block for 5 minutes. It must spawn a background thread/goroutine to perform the compaction and immediately return a 200 OK (or 202 Accepted) to the user.

Your Task

Rewrite your /merge endpoint logic to use a background K-Way merge:

  1. Async Trigger: When POST /merge is called, spawn a background thread to do the work and return the HTTP response immediately so the API remains responsive.
  2. Setup Iterators: Open a file reader/iterator for every single segment file. Read the very first line (term) from each file into an array (or a Min-Heap) of “current values”.
  3. Find the Smallest: Look at the current term for each iterator and find the alphabetically smallest term among all of them (e.g., apple is smaller than banana).
  4. Merge Duplicates & Tombstones:
    • What if apple is the smallest term, but it exists in 3 different segment files? You must combine their postings lists together!
    • Crucially, if any Document IDs in those postings lists exist in your .del Tombstone set, drop them permanently. This is how you purge deleted data from the disk!
  5. Write & Record: Write the finalized, combined postings list for apple to the new segment file. Record its new byte offset in your RAM Term Dictionary.
  6. Advance: Advance the iterators that held apple so they read their next line.
  7. Repeat: Loop from step 3 until all files reach EOF.
  8. Cleanup: Delete the old segment files and clear your Tombstone set.

Important

Run the below docker command to test your solution. Note: The test runner will trigger the /merge endpoint and then wait for 1 second before querying the index. Your background thread must complete the merge within this 1000ms window!

docker run \
  --rm \
  --add-host host.docker.internal:host-gateway \
  -v /tmp/buildit_segments:/file_serving \
  codeberg.org/level0/buildit/search-engine:latest \
  --addr host.docker.internal:8080 \
  --until k_way_merge

Typo Tolerance (Fuzzy Search)

What if the user makes a typo and searches for aple instead of apple? They get zero results! We need typo tolerance.

Trigram Indices

To do fast fuzzy searching, real engines build a secondary index of N-Grams.

An N-Gram is a sequence of characters. We will use Trigrams (3 characters). The word apple generates the following trigrams: app, ppl, ple.

TermTrigrams
dogdog
kiwikiw, iwi
grapegra, rap, ape
orangeora, ran, ang, nge

Note

What about 1 and 2 letter words? A word like is or a physically cannot form a 3-letter sequence. In practice, search engines handle this in one of two ways:

  • Padding: They pad the start and end of words with a special character (like $). So $a$ becomes a trigram, and $is$ becomes [$is, is$].
  • Omission: Since 1-2 letter words are almost always stop words (a, is, to, of) that you filtered out in Stage 7, you can usually safely ignore them for fuzzy matching!

Your Task

  1. Secondary Index: Build a secondary in-memory Hash Map mapping Trigrams to the actual Terms in your dictionary. (e.g., app -> [apple, application], ppl -> [apple]).
  2. Querying: If a user queries a term that does not exist in your dictionary:
    • Break their query into trigrams (e.g., aple -> apl, ple).
    • Look up those trigrams in your secondary index to find candidate terms.
    • Pick the candidate term with the most matching trigrams.
    • Silently replace their typo with the corrected term and run the search!

Important

Run the below docker command to test your solution.

docker run \
  --rm \
  --add-host host.docker.internal:host-gateway \
  codeberg.org/level0/buildit/search-engine:latest \
  --addr host.docker.internal:8080 \
  --until fuzzy_search

🎉 Congratulations! 🎉

You have successfully built a production-grade full-text search engine from scratch!

What started as an O(n) disaster of a linear scan has transformed into a legitimately fast, disk-backed, Lucene-style search engine equipped with BM25 scoring, boolean logic, immutable segments, tombstones, background compaction, crash recovery, and typo tolerance.

You’ve learned that search isn’t just about matching strings—it’s an engineering trade-off between indexing time, memory footprint, disk I/O, and query latency.

What We Covered

Throughout this course, you built the core components that power real-world search infrastructure:

  • The Inverted Index: Flipping the data model for O(1) lookups.
  • Normalization: Bridging the gap between literal computers and messy humans.
  • Query-Time Scoring: Pushing math to the GET request to avoid rewriting the index.
  • BM25: Implementing the industry-standard algorithm for term frequency saturation and document length normalization.
  • Top-K Heaps: Saving RAM by only holding onto the best matching documents.
  • Immutable Segments: Buffering writes in RAM and flushing to read-only files to save our SSDs from constant rewriting.
  • Tombstones: Supporting deletions in an append-only, immutable storage architecture.
  • Log-Structured Merging: Compacting fragmented segments and purging dead records to keep search latency low.
  • The Write-Ahead Log (WAL): Recovering from system crashes without losing committed data.
  • Memory Mapping & Disk Seeking: Lowering RAM usage by delegating memory management to the OS Page Cache.
  • K-Way Merge: Streaming infinite amounts of data for compaction using O(1) memory.
  • Typo Tolerance: Using Trigram indices to provide fuzzy matching for misspelled queries.

What We Didn’t Cover

Real search engines like Lucene or Elasticsearch take these concepts and push them even further. Here’s what we left out:

  • Compression: Roaring Bitmaps or delta-encoding to squash those giant sets of Document IDs down to a few kilobytes.
  • Distributed Search: Sharding the inverted index across multiple machines when it no longer fits on a single disk.
  • Concurrent Merging: Real engines run compaction algorithms asynchronously in the background so writes are never blocked.

What’s Next?

If you enjoyed this, here are a few ideas for what you can do next:

  1. Explore Compression: Try compressing your segments using Delta Encoding on your sorted Document IDs.
  2. Read the Lucene Source: You now know enough of the core concepts to actually understand what’s happening under the hood of Elasticsearch.
  3. Try another buildit course: Check out the other courses in the buildit project to continue demystifying foundational technologies.

Thanks for taking this journey with us. Now go out there and build something awesome!