Built by

core-check2-1784838524666

Computer Science

Build a Bloom-Filter Router: Fast Global Path Lookup

JavaScriptNode.jsNode.js built-in crypto module

Build a Bloom-Filter Router: Fast Global Path Lookup

Build a small, runnable Node.js routing simulator that replaces repeated path-list scans with a Bloom filter. You will see why Bloom filters can reject missing paths quickly, why false positives are acceptable when they trigger an exact-check fallback, and how the design improves lookup work without changing routing correctness.

3 modules8 lessonsComputer ScienceJavaScriptNode.jsNode.js built-in crypto moduleNode.js built-in perf_hooks module

What you learn by building this

Explain the Bloom-filter guarantees: no false negatives and possible false positives
Implement bit-array hashing and membership checks in plain Node.js
Use a Bloom filter as a fast pre-check before exact route lookup
Generate and measure false positives with a controlled test workload
Explain why false positives are acceptable when correctness is preserved by fallback verification
Compare routing lookup work and latency between a baseline scan and the Bloom-filter design

Learning Journey

See the Routing Problem and Build the Baseline

2 lessons

Create a small route dataset and a command-line lookup program. The project first makes the expensive repeated path-list scan visible, giving the Bloom filter a concrete job to solve.

Build and Test the Bloom Filter

3 lessons

Implement the core probabilistic data structure in plain JavaScript, then make its behavior observable through controlled membership tests.

Turn the Filter into a Correct Fast Router

3 lessons

Integrate the Bloom filter into the routing simulator without allowing probabilistic results to change correctness. The finished command shows fast rejection, exact fallback, and equivalent routing answers.

Public lesson

Create a Global-Style Path Workload

A deterministic global-style path workload

The Vercel article describes using a Bloom filter as a fast preliminary check during global routing. That kind of check is useful because most paths can be rejected cheaply, while a possible match can continue to a more exact lookup. A Bloom filter may report a false positive, but it must not report a false negative.

Before thinking about that optimization, create the workload it would operate on: route records, paths that should be found, and paths that should not. The exact lookup below is the ground truth. Later, a probabilistic filter could be compared against it.

Predict

What will happen?

1. Make a prediction

Imagine a routing service with these records:

/
/docs
/docs/intro
/pricing
/status

What should happen when the service receives:

/docs
/pricing
/missing
/docs/intro/

The last path is deliberately different from /docs/intro. Exact path lookup should not silently treat a trailing slash as equivalent.

Tasks

2. Add the workload

Open the existing workload entry file documented by the project. Keep its surrounding project structure, and add or adapt a section like this:

const routeRecords = [
  // Add route records with a path, handler, and region.
  { path: "/", handler: "home", region: "iad1" },
  { path: "/docs", handler: "docs-index", region: "fra1" },

  // Add at least three more records, including /docs/intro,
  // /pricing, and /status.
];

const knownPaths = [
  // These should be paths that appear in routeRecords.
  "/",
  "/docs",
  // Add the remaining paths that should be found.
];

const unknownLookupPaths = [
  "/missing",
  "/docs/intro/",
  // Add one more path that does not appear in routeRecords.
];

const routeIndex = new Map(
  routeRecords.map((record) => [record.path, record])
);

function lookup(path) {
  // Return an object with:
  //   path
  //   found: true or false
  //   handler: the matching handler, or null
  //   region: the matching region, or null
  //
  // Use routeIndex for the lookup. Do not search by partial path.
}

const lookupPaths = [...knownPaths, ...unknownLookupPaths];
const results = lookupPaths.map(lookup);

console.table(results);

const expectedFound = new Map([
  ["/", true],
  ["/docs", true],
  ["/docs/intro", true],
  ["/pricing", true],
  ["/status", true],
  ["/missing", false],
  ["/docs/intro/", false],
  ["/does-not-exist", false],
]);

for (const result of results) {
  const expected = expectedFound.get(result.path);

  console.assert(
    expected !== undefined,
    `No expectation was provided for ${result.path}`
  );

  console.assert(
    result.found === expected,
    `Unexpected result for ${result.path}: expected found=${expected}, got found=${result.found}`
  );

  if (!result.found) {
    console.assert(
      result.handler === null && result.region === null,
      `Unknown path ${result.path} should not have route details`
    );
  }
}

console.log(`Checked ${results.length} deterministic lookups.`);

const routeRecords = [
  // Add route records with a path, handler, and region.
  { path: "/", handler: "home", region: "iad1" },
  { path: "/docs", handler: "docs-index", region: "fra1" },

  // Add at least three more records, including /docs/intro,
  // /pricing, and /status.
];

const knownPaths = [
  // These should be paths that appear in routeRecords.
  "/",
  "/docs",
  // Add the remaining paths that should be found.
];

const unknownLookupPaths = [
  "/missing",
  "/docs/intro/",
  // Add one more path that does not appear in routeRecords.
];

const routeIndex = new Map(
  routeRecords.map((record) => [record.path, record])
);

function lookup(path) {
  // Return an object with:
  //   path
  //   found: true or false
  //   handler: the matching handler, or null
  //   region: the matching region, or null
  //
  // Use routeIndex for the lookup. Do not search by partial path.
}

const lookupPaths = [...knownPaths, ...unknownLookupPaths];
const results = lookupPaths.map(lookup);

console.table(results);

const expectedFound = new Map([
  ["/", true],
  ["/docs", true],
  ["/docs/intro", true],
  ["/pricing", true],
  ["/status", true],
  ["/missing", false],
  ["/docs/intro/", false],
  ["/does-not-exist", false],
]);

for (const result of results) {
  const expected = expectedFound.get(result.path);

  console.assert(
    expected !== undefined,
    `No expectation was provided for ${result.path}`
  );

  console.assert(
    result.found === expected,
    `Unexpected result for ${result.path}: expected found=${expected}, got found=${result.found}`
  );

  if (!result.found) {
    console.assert(
      result.handler === null && result.region === null,
      `Unknown path ${result.path} should not have route details`
    );
  }
}

console.log(`Checked ${results.length} deterministic lookups.`);

There are two meaningful pieces for you to complete:

Finish the route records and the two path lists.
Implement lookup.

The route records represent the exact routing data. The region field makes the data feel like a global routing workload: a successful lookup identifies not only what handles a path, but where that route is associated. The Map gives you an exact answer for each path, which is useful as a reference result.

Make sure /does-not-exist is included in unknownLookupPaths, because the check expects it. Also make sure every path in knownPaths has a corresponding record. That relationship is part of the workload's correctness, not just sample data.

Check: Complete the route records, both path lists, and lookup in the existing workload entry file.

Tasks

3. Run and inspect the check

Run the project's documented command.

The table should contain one row for every path in lookupPaths. Successful rows should have a handler and region. Unknown rows should have found: false and null route details. The final line should report:

Checked 8 deterministic lookups.

Checked 8 deterministic lookups.

There should be no failed console.assert messages.

If /docs/intro/ is reported as found, inspect the lookup carefully. The route record is /docs/intro; this workload uses exact paths, so a trailing slash is a different lookup. If an unknown path receives a handler or region, the not-found branch is leaking details from a previous or partial match.

Check: Confirm the table, final count, and assertions match the expected results.

Tasks

4. Make one small route change

Add this route record:

{ path: "/blog", handler: "blog-index", region: "sfo1" }

{ path: "/blog", handler: "blog-index", region: "sfo1" }

Then add /blog to knownPaths and add /blog/archive to unknownLookupPaths.

Run the project again. The count should increase by two, and the new results should be:

/blog: found, handled by blog-index, associated with sfo1
/blog/archive: not found, with no handler or region

This is worth checking because routing systems often deal with many paths that look related. A prefix such as /blog must not accidentally make /blog/archive appear to exist.

Check: Confirm the count increases by two and the two new results match the stated behavior.

What this workload gives you

You now have three separate things that are easy to confuse:

Route records: the exact paths the service knows.
Known lookup paths: requests expected to match.
Unknown lookup paths: requests expected to be rejected.

The Map is the exact reference implementation. A future fast filter can answer “definitely not present” before this lookup, but its answers can be judged against these deterministic results. For every path that is truly known, the fast check must allow the exact lookup to continue; for an unknown path, it may reject immediately. The important observation is that speed changes the path to the answer, not the answer itself.

Course Outline

3 modules · 8 lessons

See the Routing Problem and Build the Baseline

Build and Test the Bloom Filter

Turn the Filter into a Correct Fast Router

Learn by building your own version.

Remix this public project to open the workspace, follow the guided build, and let the AI mentor teach you through the work instead of doing it for you.