Speeding Up Global Path Routing with Bloom Filters
Computer Science
Speeding Up Global Path Routing with Bloom Filters
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.
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
Build the routing problem in miniature
2 lessonsCreate a dependency-free routing simulator and make the costly exact lookup visible before introducing probabilistic filtering.
Add a Bloom filter without hiding the trade-off
3 lessonsImplement the compact membership structure needed for a fast negative check, then verify its guarantees and limitations against the routing simulator.
Measure why the design works
3 lessonsTurn 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:
| Deployment | Request | Expected |
|---|---|---|
| one deployment | a path you have stored | found |
| one deployment | a path you have not stored | 404 |
| one deployment | a longer path beginning with a stored path | 404 |
| another deployment | a path stored only in the first deployment | 404 |
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 */ ]
}
}
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
}
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:
- a path present in
deployment-a; - a path absent from
deployment-a; - a path that merely begins with a present path;
- a path present in
deployment-abut absent fromdeployment-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
)
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
200for a path that was not stored, what incorrect page might the simulator serve? - If it returned
404for 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.