In Chapter 3 the controller branched on something called the "endpoint type":
switch endpointType(perms) {
case "OPEN": ...
case "AUTHENTICATED": ...
case "ACCESS_CONTROLLED": ...
}
That branch is the most important conditional in the entire gateway. It decides whether a request even gets a token check, and whether to run authorization. This chapter is about how that decision is data, not code, and the trie that powers it.
Three kinds of endpoint
Every endpoint in our platform falls into one of three buckets:
- OPEN — no auth required at all. Health checks, public OAuth callbacks, JWKS, version, docs. The request is allowed without a token.
- AUTHENTICATED — token required, no specific permission. "Get my own profile," logout, list-my-stuff endpoints. Anyone with a valid token can call it.
- ACCESS_CONTROLLED — token required and a specific permission. Admin operations, deletes, anything that crosses a user boundary.
The Auth Service runs different pipelines for each:
The brilliance — and we say this honestly, because we did not design it this way the first time — is that an endpoint's classification is a column in a database row, not a hardcoded route. Adding a new admin route means inserting a row, not deploying the gateway. We rebuild the in-memory data structure on demand.
The data structure: a trie
When NGINX hits /auth, it forwards X-Original-URI: /user-management/v1/users/abc123 and X-Original-Method: GET. We need to turn that into an endpoint metadata record.
The naïve approach is a big map with (method, full_path) keys. That works until you have wildcards: /users/{id} should match both /users/abc and /users/xyz. Once you have wildcards you want a trie.
Our trie node looks like this:
type TrieNode struct {
children map[string]*TrieNode // exact-match segments
wildcard *TrieNode // catch-all child for {id}-style segments
Permissions map[string][]string // method -> required permissions
EndpointType string // OPEN | AUTHENTICATED | ACCESS_CONTROLLED
BitmapMask uint64 // pre-computed for bitmap fast-path (Chapter 6)
}
A trie key is a slash-segmented path. /users/{id}/roles becomes the path ["users", "{id}", "roles"]. Walking the trie is one segment at a time:
func (t *Trie) Lookup(method string, path []string) (*TrieNode, bool) {
node := t.root
for _, seg := range path {
if next, ok := node.children[seg]; ok {
node = next
continue
}
if node.wildcard != nil {
node = node.wildcard
continue
}
return nil, false
}
if _, ok := node.Permissions[method]; ok {
return node, true
}
return nil, false
}
O(depth) worst case, where depth is the number of segments. In practice a typical endpoint is 3-5 segments. We're talking nanoseconds.
A toy view of what one slug's trie looks like:
Notice me and {id} are both children of users. users/me resolves first (exact match) and gets AUTHENTICATED. users/abc123 falls through to the {id} branch and gets ACCESS_CONTROLLED + user:read. Order matters: exact wins over wildcard.
Service slug: scoping the trie
We don't have one giant trie. We have one trie per service slug. Why?
- Different services own different paths.
- A single global trie collides on ambiguous paths (multiple services exposing
/v1/usersfor different reasons). - Cache locality and refresh granularity are better when each service's routes are isolated.
For a long time the slug came from "the first segment of the URI." That was fine until services nested each other (/api/v2/user-management/users). So we added two optional headers:
-
X-Service-Slug— explicit slug. -
X-Request-Path— the path inside that slug, with the prefix already stripped.
The route resolver uses them when present:
func (r *RouteResolver) ResolveEndpointWithMetrics(ctx *gin.Context, log *AuthDecisionLog) (
slug, trieKey string, perms []string, trieExists, found bool,
) {
slug = ctx.GetHeader("X-Service-Slug")
path := ctx.GetHeader("X-Request-Path")
if slug == "" || path == "" {
// Legacy: split URI on first segment
slug, path = splitFirstSegment(log.URI)
}
trie := globalTrieRegistry.Get(slug)
if trie == nil {
return slug, path, nil, false, false
}
node, ok := trie.Lookup(log.Method, segments(path))
if !ok {
return slug, path, nil, true, false
}
return slug, path, node.Permissions[log.Method], true, true
}
Two return flags, not one: trieExists distinguishes "the service slug isn't registered" from "the service slug is registered but this path doesn't match." The first is a server problem (deploy mismatch). The second is a client problem (404). Different decision reasons, different alerts.
Loading the trie from Postgres
The source of truth is two tables:
-- Each row is one (service, method, pattern) combination
CREATE TABLE endpoint (
id uuid PRIMARY KEY,
service_slug text NOT NULL,
method text NOT NULL,
pattern text NOT NULL,
endpoint_type text NOT NULL -- OPEN | AUTHENTICATED | ACCESS_CONTROLLED
);
-- Permissions an endpoint requires (only for ACCESS_CONTROLLED)
CREATE TABLE endpoint_policy (
endpoint_id uuid REFERENCES endpoint(id),
general_policy_id uuid REFERENCES general_policy(id)
);
-- The actual policy table — name + bit_index for the bitmap path (Chapter 6)
CREATE TABLE general_policy (
id uuid PRIMARY KEY,
name text UNIQUE,
bit_index int -- nullable; assigned for bitmap-eligible permissions
);
At startup, LoadTrieAndRegistry runs one query per active service slug, joins the three tables, and builds a Trie per slug:
func LoadTrieAndRegistry(ctx context.Context, db *sql.DB) (
map[string]*helpers.Trie, *policybitmap.Snapshot, error,
) {
rows, _ := db.QueryContext(ctx, `
SELECT e.service_slug, e.method, e.pattern, e.endpoint_type,
coalesce(array_agg(gp.name) FILTER (WHERE gp.id IS NOT NULL), '{}'),
coalesce(array_agg(gp.bit_index) FILTER (WHERE gp.bit_index IS NOT NULL), '{}')
FROM endpoint e
LEFT JOIN endpoint_policy ep ON ep.endpoint_id = e.id
LEFT JOIN general_policy gp ON gp.id = ep.general_policy_id
GROUP BY e.id
`)
tries := map[string]*helpers.Trie{}
snap := policybitmap.NewSnapshot()
for rows.Next() {
var (
slug, method, pattern, etype string
permNames []string
bitIdxs []int
)
rows.Scan(&slug, &method, &pattern, &etype, pq.Array(&permNames), pq.Array(&bitIdxs))
if _, ok := tries[slug]; !ok {
tries[slug] = helpers.NewTrie()
}
node := tries[slug].Insert(segments(pattern))
node.EndpointType = etype
node.Permissions = map[string][]string{method: permNames}
node.BitmapMask = computeMask(bitIdxs) // Chapter 6
}
return tries, snap, nil
}
A single SQL query, one pass to build N tries. We measure load time and emit it as a startup log: trie_load_duration_ms. On a healthy database, hundreds of tries with thousands of routes load in well under a second.
Refreshing without a restart
Endpoint metadata changes — we onboard a new service, add a new permission, deprecate a route. We don't want to roll the gateway every time.
There are two refresh mechanisms:
1. Periodic. Every TRIE_REFRESH_INTERVAL_SECS (default: 1 hour) we re-run the loader. This is a safety net. If the live channel ever misses an event, periodic catches it within an hour.
2. Live. A Redis Pub/Sub channel called auth:trie:refresh. When admin tooling changes endpoint metadata, it PUBLISHes to that channel. Every Auth Service pod is subscribed, and refreshes within milliseconds.
The Pub/Sub message itself carries no payload. It's purely a kick. Each pod queries the database itself. Two reasons:
- We don't have to keep the message in sync with the schema. New columns, no message change.
- A pod that just booted does the same load as a pod that received a refresh kick. One code path.
The downside: every refresh kick = one query per pod. If you have 100 pods and someone bulk-edits 1000 endpoints with 1000 publishes, that's 100,000 queries. We added a debounce (coalesce events within a 200 ms window). Onboarding a service still hammers the DB once, briefly, but it doesn't spiral.
Caching the lookup
Even with a fast trie, re-walking the same path on every request is wasteful. We layer a TinyLFU cache (W-TinyLFU, via a Go port) on top of the resolver:
type RouteCache struct {
inner *tinylfu.Cache[string, RouteResult]
}
func (c *RouteCache) Get(slug, method, path string) (RouteResult, bool) {
return c.inner.Get(slug + "\x00" + method + "\x00" + path)
}
The key is service_slug + NUL + method + NUL + path. The NUL byte is a delimiter — paths can't contain it, so we can't accidentally collide a slug with the start of another slug.
The cache is bounded by entry count, not by RAM. Default: 10,000 routes with 100,000 frequency counters. TinyLFU keeps the frequently used routes hot and evicts cold ones — better than LRU when traffic has a long tail of rarely-hit paths.
Cache invalidation: on any trie reload (periodic or kick), the cache is fully cleared. We considered partial invalidation. We chose not to — the cache fills back up in milliseconds because the same handful of paths drives 99% of the traffic.
Why this beats per-route decorators
In a Python or Node service you might write:
@app.route("/users/<id>", methods=["GET"])
@requires_permission("user:read")
def get_user(id): ...
Three problems with that:
- Service-by-service drift. Each service maintains its own decorators. Different services use different permission strings, different exception types, different log shapes. The contract is informal.
- Fragile to refactor. Move the route, lose the decorator. Now anyone can call it. We've seen this happen at zero, two, and twelve months in.
- Audit is impossible at the service level. "What permission protects this URL?" requires reading every service's source.
By making endpoint metadata a database row, we get:
- One contract, in one schema.
- Decoupled from code — no rebuild to add a route.
- Auditable: a single
SELECTanswers "what does this URL require?" - Reusable: the same metadata drives the gateway and the admin UI that lets product managers tweak it.
The cost is that you can't read the auth requirements next to the handler in the upstream service's code. We mitigate that with code generation: a CI job dumps endpoint rows for each service into a routes.yaml checked into the service's repo for reference. The DB stays the source of truth.
Readiness depends on the trie
There's a subtle interaction with Kubernetes probes worth calling out. Our /readyz returns 503 if the trie isn't loaded:
func CheckTrieReadiness(tries map[string]*helpers.Trie) (int, gin.H) {
if len(tries) == 0 {
return http.StatusServiceUnavailable, gin.H{"status": "trie not loaded"}
}
return http.StatusOK, gin.H{"status": "ok"}
}
A pod that boots before Postgres is reachable will fail readiness, which keeps it out of the Service load balancer until the trie is loaded. A pod that was serving traffic and then loses access to Postgres keeps its existing trie in memory and stays ready — refreshes fail loudly via Slack, but live traffic isn't disrupted.
This split — "load fails block readiness, refresh failures don't" — is on purpose. A booting pod with no trie can't make decisions; pull it out. A serving pod with a stale trie can still make decisions correctly for endpoints that haven't changed; keep it in service while we fix Postgres.
Anti-patterns we avoided
Worth listing what we considered and rejected, because they're tempting:
- Storing the endpoint type inside the JWT. Tempting because then you don't need a trie. Wrong because a token outlives configuration changes — we'd cache stale auth requirements.
- A single hard-coded list of public paths. A previous iteration had a YAML file shipped with the gateway. Updating it required a deploy. The trie + DB replaced it.
- Per-tenant route metadata. We talked about it. We rejected it: the same service exposes the same routes for every tenant. Tenant-specific differences belong in the access-level model (Chapter 6), not the route model.
- Letting the upstream service register its own routes via API at startup. Looks elegant. Falls apart in chaos: a buggy service can register away its own auth.
What's next
Chapter 5 takes the same metadata-as-data philosophy and applies it to multi-tenancy. The trie tells us what an endpoint requires; tenant resolution tells us who it's for. We'll see how NGINX server blocks, headers, and tenant maps cooperate to never let a request through without a clear tenant identity.