Speeding Up Global Path Routing with Bloom Filters

Computer Science

Speeding Up Global Path Routing with Bloom Filters

JavaScriptNode.jsNode.js built-in assert module

Speeding Up Global Path Routing with Bloom Filters

Build a small, runnable routing simulator that uses a Bloom filter as a fast first check before falling back to an exact path lookup. You will see why false positives are acceptable, why false negatives are not, and how this pattern can reduce expensive lookups.

3 modules8 lessonsComputer ScienceJavaScriptNode.jsNode.js built-in assert moduleNode.js built-in performance API

What you learn by building this

  • Explain how Bloom filters represent set membership with compact bit arrays and hash functions
  • Distinguish false positives from false negatives and identify which error is safe in path routing
  • Implement Bloom-filter insertion and membership checks in plain JavaScript
  • Design a routing flow that returns 404 only after the filter safely rules out a path
  • Measure the practical trade-off between memory usage, false-positive rate, and exact fallback lookups

Learning Journey

1

Build the routing problem in miniature

2 lessons

Create a dependency-free routing simulator and make the costly exact lookup visible before introducing probabilistic filtering.

2

Add a Bloom filter without hiding the trade-off

3 lessons

Implement the compact membership structure needed for a fast negative check, then verify its guarantees and limitations against the routing simulator.

3

Measure why the design works

3 lessons

Turn the simulator into an experiment that connects filter configuration to memory, false positives, fallback work, and routing performance.

Public lesson

Model deployment paths and exact lookup

Predict

What will happen?

Exact paths are not prefixes

A deployment can contain a path that another deployment does not. Before trying to make routing faster, we need a small, unambiguous baseline: given a deployment and a requested path, return the page only when that exact path exists.

First, predict the result of these requests:

DeploymentRequestExpected
one deploymenta path you have storedfound
one deploymenta path you have not stored404
one deploymenta longer path beginning with a stored path404
another deploymenta path stored only in the first deployment404

That third case matters. A route such as /docs does not automatically mean that /docs/getting-started exists. We want exact membership, not a prefix guess.

Tasks

Add a small deployment model

Open the existing file that currently runs the path simulator. Keep its surrounding project structure and syntax. Replace or extend its sample data with a small collection of deployments, each containing its own paths.

Use this shape as a guide, but type the values and syntax in the style already used by the project:

deployments = {
  "deployment-a": {
    paths: [ /* several exact paths */ ]
  },
  "deployment-b": {
    paths: [ /* at least one path different from deployment-a */ ]
  }
}

Choose a few paths that make the distinction visible. For example, include a stored /docs path, but do not include /docs/getting-started unless you want that second path to exist too.

Now complete the lookup function:

function lookup(deploymentId, requestedPath) {
  deployment = deployments[deploymentId]

  if deployment does not exist:
    return a 404 result

  if requestedPath is an exact member of deployment.paths:
    return a 200 result containing the deployment and requested path

  return a 404 result
}

The important choice is the membership test. Do not use a substring test or a “starts with” test. The lookup should compare the requested path as one complete value.

If the project already represents paths with a set-like collection, use its exact membership operation. If it currently uses an array, use the project’s established way of checking whether one value is present. Do not normalize, trim, or rewrite the path yet; this first version should make the baseline rule easy to see.

Tasks

Make the check visible

Find the existing simulator check, test block, or command that prints lookup results. Add cases for:

  1. a path present in deployment-a;
  2. a path absent from deployment-a;
  3. a path that merely begins with a present path;
  4. a path present in deployment-a but absent from deployment-b.

Leave the expected result beside each case so the output is easy to inspect. In outline:

check(
  lookup("deployment-a", "an existing exact path"),
  expected status: 200
)

check(
  lookup("deployment-a", "a missing path"),
  expected status: 404
)

check(
  lookup("deployment-a", "the existing path plus another segment"),
  expected status: 404
)

check(
  lookup("deployment-b", "a path belonging only to deployment-a"),
  expected status: 404
)

Run the project with its documented command. The useful output is not merely that the program runs; it should show a clear difference between the four cases.

If the prefix case returns 200, inspect the condition in lookup. It is probably answering “does this request resemble a stored path?” rather than “is this complete path stored?” Change that condition before continuing.

Explain it back

Put it in your own words

Why keep this exact version?

The exact lookup is the authority for the simulator. It tells us whether a deployment really contains a page. That makes it a useful baseline even if a later routing check is made faster.

A faster preliminary structure may be able to say:

  • “this path definitely is not present,” or
  • “this path might be present.”

But “might be present” is not enough to serve a page. The exact lookup still has to confirm it. Keeping today’s behavior simple gives us something to compare against when we introduce a faster pre-check.

Look back at your output and ask:

  • Which result proves that deployment identity matters?
  • Which result proves that exact membership differs from prefix matching?
  • If the lookup returned 200 for a path that was not stored, what incorrect page might the simulator serve?
  • If it returned 404 for a path that was stored, what kind of failure would that be?

Leave the working exact lookup in place. It is the reference behavior for the next change.

20 more characters

Course Outline

3 modules · 8 lessons

Build the routing problem in miniature

Add a Bloom filter without hiding the trade-off

Measure why the design works

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.