Optimizing Rule Engine Performance

This guide is part of the Backend Evaluation & Server-Side SDKs series. A rule engine sits on every request path in a server-side flag system: it receives an evaluation context, walks the targeting tree for a flag, and returns a variant — all while the calling thread is waiting. When that work is slow it shows up directly in your service’s p99, not just in flag metrics.

This guide covers the engine itself: how rules move from JSON to a compiled AST, how short-circuit evaluation and regex avoidance keep the hot path fast, and how to set and enforce a latency budget. It does not cover the cache topology that sits in front of the engine (see distributed caching for flag evaluations) or the transport that keeps the rule set fresh (see polling vs streaming flag synchronization).

The reason this work matters is subtle: a flag evaluation is not a leaf operation the way a hash-map read is. It runs inside the request that is already holding a connection, a database transaction, or a lock, so its latency is pure serial overhead that no amount of downstream parallelism can hide. A service that evaluates ten flags per request — a modest number once you gate routing, pricing, and UI variants independently — pays the rule-engine cost ten times before it does any real work. That multiplier is exactly why an engine that looks “fast enough” in a microbenchmark can still add several milliseconds to a real endpoint, and why the optimisations below target the per-call cost rather than aggregate throughput. Get the per-call cost low and predictable, and the request-level tax collapses on its own.

Prerequisites

• OpenFeature server SDK ≥ 1.x installed (@openfeature/server-sdk, openfeature Python, or Go equivalent)
• flagd or a vendor provider reachable; flag definitions in JsonLogic or flagd format
• A p99 latency baseline from production traces (OpenTelemetry spans work well)
• Flag metadata fields owner, created, expiry populated per your flag taxonomy
• Prometheus (or equivalent) scraping flag_eval_duration_seconds with histogram buckets

Core Concept & Architecture

Every flag evaluation request walks a path: receive context → check cache → enter the rule engine → return a variant. The rule engine phase is the only step with non-trivial complexity: it interprets a targeting rule — usually expressed as a JsonLogic document — and applies it to the evaluation context. Two sources of overhead dominate:

Parse overhead — re-reading the JSON rule definition and building an operator tree from scratch on every call. This is pure waste and belongs at initialisation, not on the hot path.

Traversal overhead — walking the operator tree with an inefficient algorithm: no short-circuiting, regex matching on large strings, or attribute lookups that hydrate a database record.

Of the two, parse overhead is the one that surprises teams most, because it is invisible in the rule authoring experience — a JsonLogic document that reads as three lines of JSON still costs a full recursive-descent parse and a tree of small heap allocations on every call if you leave it uncompiled. Traversal overhead, by contrast, is usually something a rule author introduced deliberately (a regex, a deeply nested or) and can be reasoned about from the rule text. A useful mental model: parse overhead is a constant tax you pay for how the engine is wired, and traversal overhead is a variable tax you pay for what each rule asks the engine to do. The architecture below drives the first to zero at init and keeps the second bounded by the rule’s structure rather than its input size.

The architecture that keeps evaluation fast is:

1. Parse-once, compile-to-AST — at provider init, parse every flag’s targeting rule into an in-memory AST. Store the compiled tree keyed by flag version. Re-parse only when a flag update arrives.
2. Short-circuit evaluation — implement AND and OR in the evaluator using native boolean short-circuiting so branches that cannot affect the result are never visited.
3. Avoid regex on the hot path — prefix/suffix and equality operators are one array index or hash lookup; regex requires backtracking and blows the CPU budget for complex patterns. Replace with set membership checks where possible.
4. Thin, flat context — the engine iterates context attributes; a 50-key payload costs proportionally more than a 5-key one. Strip non-targeting keys at the API boundary.

Latency budget breakdown

A realistic per-evaluation budget for a service targeting p99 ≤ 5 ms:

If p99 exceeds 5 ms, the investigation order is: confirm the AST is compiled (not parsed on each call), profile for regex predicates, then check context payload size.

Two things about this budget are deliberate. First, the median target is set at roughly 2 ms rather than at the 5 ms ceiling — the gap between them is not slack you are free to spend, it is the reservoir that absorbs GC pauses, lock waits, and scheduler preemption that only show up in the tail. If your median creeps toward 4 ms, the p99 will breach long before the median does, because tail latency grows faster than the mean under load. Second, the numbers are per evaluation, not per request; a request that evaluates eight flags multiplies the AST-walk line eight times, so a service with flag-heavy endpoints should budget the request as a whole and divide backward to a stricter per-call target. Treat the table as a template to re-derive for your own call fan-out, not as universal constants.

Step-by-Step Implementation

Five optimizations move work off the hot path in priority order: compile rules once, short-circuit the AST walk, drop regex predicates, enforce a budget with alerting, and finally tune allocation and GC. The first three deliver most of the gain; the last two protect the p99 tail.

Step 1 — Compile rules to AST at provider initialisation

Move all rule parsing out of the evaluation path. At startup — and again whenever the flag update stream delivers a change — parse each flag’s targeting rule into a compiled tree and store it keyed by flag key + rule version.

import { OpenFeature, Provider, ResolutionDetails } from '@openfeature/server-sdk';

interface ASTNode {
  op: 'AND' | 'OR' | 'EQ' | 'IN' | 'GT';
  left?: ASTNode;
  right?: ASTNode;
  attr?: string;
  value?: unknown;
  values?: unknown[];
}

function compileRule(jsonLogic: Record<string, unknown>): ASTNode {
  const [op, args] = Object.entries(jsonLogic)[0];
  if (op === 'and') return { op: 'AND', left: compileRule(args[0]), right: compileRule(args[1]) };
  if (op === '==')  return { op: 'EQ',  attr: (args[0] as any).var, value: args[1] };
  if (op === 'in')  return { op: 'IN',  attr: (args[0] as any).var, values: args[1] };
  throw new Error(`Unsupported op: ${op}`);
}

// compiledRules lives at module scope — built once, read on every evaluation
const compiledRules = new Map<string, ASTNode>();

function loadFlags(flagDefs: Record<string, { targeting: Record<string, unknown>, version: number }>) {
  for (const [key, def] of Object.entries(flagDefs)) {
    compiledRules.set(`${key}@${def.version}`, compileRule(def.targeting));
  }
}

Keying the compiled tree by flag_key + version rather than by flag key alone is what makes the swap in step 4 of the FAQ safe: two versions of the same flag can coexist in the map during a rollout, and an in-flight evaluation that started against version 3 keeps resolving against version 3 even as version 4 lands. The version suffix also gives you a free cache-correctness check — if an evaluation ever asks for a key that is not in the map, you know the compile step lagged the update stream, and you can fall back to the default variant rather than parsing on the hot path.

Pitfall: calling JSON.parse + compileRule inside the evaluation function is the most common cause of evaluation latency spikes. Profile with console.time or a flag_eval_parse_duration_seconds counter to confirm the cost before and after moving compilation to init. A subtler variant of the same bug is lazy compilation — compiling on first evaluation and caching the result — which hides the cost in a cold-start p99 spike that only appears after a deploy or a scale-out event, exactly when you are least able to diagnose it. Compile eagerly at init so the cost is paid once, visibly, before the node accepts traffic.

Step 2 — Implement short-circuit evaluation in the AST walker

The evaluator must mirror how the host language’s && and || operators work: for AND, stop as soon as one branch returns false; for OR, stop as soon as one branch returns true. Never evaluate both sides unconditionally.

function walkAST(node: ASTNode, ctx: Record<string, unknown>): boolean {
  switch (node.op) {
    case 'AND':
      // Short-circuit: right branch is skipped if left is false
      return walkAST(node.left!, ctx) && walkAST(node.right!, ctx);
    case 'OR':
      return walkAST(node.left!, ctx) || walkAST(node.right!, ctx);
    case 'EQ':
      return ctx[node.attr!] === node.value;
    case 'IN':
      return (node.values as unknown[]).includes(ctx[node.attr!]);
    case 'GT':
      return (ctx[node.attr!] as number) > (node.value as number);
    default:
      return false; // safe default for unrecognised ops
  }
}

Short-circuiting is not only a CPU optimisation — it changes which predicates run at all, which has a correctness dimension worth planning around. Order your AND operands cheapest-first: put a bare equality check (tenantTier == "enterprise") before an expensive in against a large list, and the expensive branch is skipped entirely for the majority of contexts that fail the cheap check. This is the evaluator-level equivalent of predicate pushdown in a query planner, and on a rule that fans out into segments it can halve the average walk. When you control the compile step, you can even sort each AND node’s children by a static cost estimate at compile time so the ordering benefit is automatic rather than dependent on how the rule author happened to write the JSON.

Pitfall: an evaluator that materialises the full result of both branches before applying the operator defeats short-circuiting. Watch for Promise.all, eager list comprehensions, or any pattern that forces evaluation of an operand before the logical result is known. This bites hardest when a predicate has a side effect or a lookup cost — an attribute resolver that hits a cache or hydrates a record — because eager evaluation runs that lookup even on branches the result never needed. Keep predicate evaluation lazy and side-effect-free so the walker is free to skip whatever the boolean algebra allows.

Step 3 — Replace regex predicates with set membership or prefix checks

Regex matching in targeting rules is disproportionately expensive: even a simple ^enterprise-.* pattern requires backtracking machinery and prevents branch prediction. Replace with explicit set membership or prefix operators wherever rule authors have the option.

# flagd rule definition — AVOID regex in targeting
# Slow:
targeting:
  if:
    - { "regex": [ { "var": "tenantId" }, "^enterprise-" ] }
    - "on"
    - "off"

# Fast: explicit set membership
flags:
  api.search.semantic-rerank:
    state: ENABLED
    variants: { "on": true, "off": false }
    defaultVariant: "off"
    targeting:
      if:
        - { "in": [ { "var": "tenantTier" }, [ "enterprise", "business-plus" ] ] }
        - "on"
        - "off"

# If a custom evaluator must match patterns, compile once and cache the compiled pattern
import re
from functools import lru_cache

@lru_cache(maxsize=256)
def _compile(pattern: str) -> re.Pattern:
    return re.compile(pattern)

def match_regex_predicate(pattern: str, value: str) -> bool:
    return bool(_compile(pattern).match(value))

There is a security dimension to this beyond raw speed. A regex predicate whose pattern comes from flag configuration and whose input comes from user-controlled context is a catastrophic-backtracking risk — a pattern like (a+)+$ against a crafted input can take exponential time, turning a single evaluation into a multi-second CPU stall that pins a worker thread. This is a denial-of-service vector reachable through an ordinary flag config change, which is precisely the kind of change that skips the scrutiny a code deploy would get. Preferring set membership and prefix operators removes the vector entirely; where a pattern is genuinely required, run it under a timeout or use a linear-time engine (RE2, Rust’s regex) rather than a backtracking one.

Pitfall: a regex predicate compiled fresh inside the evaluator on every call adds 5–50 µs per match depending on pattern complexity. Cache compiled patterns at the rule level, not at call time. Note too that a prefix like startsWith("enterprise-") is not just faster than the equivalent ^enterprise- regex — it is O(prefix length) regardless of input size, whereas the regex engine may scan or backtrack across the whole string, so the gap widens as tenant IDs or user agents grow longer.

Step 4 — Set and enforce a latency budget with alerting

An SLO without enforcement decays. Add a histogram metric to every evaluation call, set a Prometheus alert at the p99 threshold, and fail CI if a benchmark exceeds the budget.

package flags

import (
    "context"
    "time"

    "github.com/open-feature/go-sdk/pkg/openfeature"
    "github.com/prometheus/client_golang/prometheus"
)

var evalDuration = prometheus.NewHistogramVec(prometheus.HistogramOpts{
    Name:    "flag_eval_duration_seconds",
    Help:    "Feature flag evaluation latency",
    Buckets: []float64{.0005, .001, .002, .005, .010, .025},
}, []string{"flag_key", "variant"})

func EvaluateWithBudget(ctx context.Context, client openfeature.IClient, key string, defaultVal bool) bool {
    start := time.Now()
    val, _ := client.BooleanValue(ctx, key, defaultVal, openfeature.EvaluationContext{})
    evalDuration.WithLabelValues(key, fmt.Sprintf("%v", val)).Observe(time.Since(start).Seconds())
    return val
}

# prometheus-alerts.yaml
groups:
  - name: flag_evaluation
    rules:
      - alert: FlagEvalP99Breach
        expr: histogram_quantile(0.99, rate(flag_eval_duration_seconds_bucket[5m])) > 0.005
        for: 2m
        labels: { severity: critical }
        annotations:
          summary: "Flag evaluation p99 exceeds 5 ms budget"
          description: "Check AST compilation, regex predicates, or context payload size."

Choose the histogram buckets to straddle the budget, not to look tidy. The buckets above (.0005, .001, .002, .005, .010, .025) put a boundary exactly at the 5 ms SLO so histogram_quantile interpolates accurately near the threshold you actually alert on; buckets that are all far below or all far above the SLO give you a p99 estimate with error bars wider than the decision you are trying to make. The for: 2m clause on the alert is equally deliberate — it suppresses the single-scrape spikes that a GC pause or a deploy will always produce, so the page only fires on a sustained breach that represents a real regression rather than noise.

Pitfall: aggregating evaluation latency across all flags hides per-flag outliers. Include flag_key as a histogram label so a single complex rule doesn’t obscure a healthy average. Watch the cardinality, though: flag_key is bounded and safe, but never label the histogram with targetingKey or any user-derived attribute — that turns one time series into millions and will take down your metrics backend faster than a slow rule ever hurt your service.

Step 5 — Tune GC and memory allocation

Evaluation allocates on every call: context map reads, intermediate boolean results, variant strings. In GC-managed runtimes (JVM, Go, Python) this creates back-pressure at p99 when GC pauses spike.

// Pre-allocate a context struct rather than building a new map per evaluation
type EvalContext struct {
    TargetingKey string
    TenantTier   string
    Region       string
    // Only fields the rule engine actually reads
}

// Reuse via a sync.Pool to avoid per-request heap allocation
var ctxPool = sync.Pool{
    New: func() interface{} { return &EvalContext{} },
}

func getContext(req *http.Request) *EvalContext {
    ctx := ctxPool.Get().(*EvalContext)
    ctx.TargetingKey = req.Header.Get("X-User-ID")
    ctx.TenantTier   = req.Header.Get("X-Tenant-Tier")
    ctx.Region       = req.Header.Get("X-Region")
    return ctx
}

func releaseContext(ctx *EvalContext) {
    *ctx = EvalContext{} // zero before returning
    ctxPool.Put(ctx)
}

Reach for pooling only after you have confirmed with a profiler that allocation is actually your tail’s problem — it usually is not the first thing to fix, and a sync.Pool adds real complexity and a class of use-after-free bugs that the garbage collector normally protects you from. The higher-leverage move in most runtimes is to allocate less rather than to recycle: read context attributes directly off the incoming struct instead of copying them into a fresh map, avoid boxing booleans into interface{}, and let escape analysis keep the small intermediates on the stack where they cost nothing to reclaim. In the JVM specifically, prefer keeping the evaluation path allocation-light so the young generation stays small and minor GCs stay short; a shift to a low-pause collector (ZGC, Shenandoah) helps the tail but is no substitute for not producing the garbage in the first place.

Pitfall: returning a pooled struct to the caller creates a dangling reference once releaseContext is called. Pool context objects only if evaluation is synchronous and the struct does not escape the call frame. If any code path stashes the context in a goroutine, a channel, or a response object, the pool will hand the same struct to a second request while the first still holds it — a data race that manifests as one tenant occasionally seeing another tenant’s targeting. That failure is intermittent, impossible to reproduce locally, and far more expensive than the allocation you were trying to save.

Verification & Testing

Confirm the optimisations are working with a benchmark that measures compiled vs. uncompiled throughput:

// BenchmarkCompiledAST vs BenchmarkParsedRule — run with: go test -bench=. -benchtime=5s
func BenchmarkCompiledAST(b *testing.B) {
    ctx := map[string]interface{}{"tenantTier": "enterprise", "region": "us-east-1"}
    // compiledRules already populated at init
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        walkAST(compiledRules["api.search.semantic-rerank@3"], ctx)
    }
}

func BenchmarkParsedRule(b *testing.B) {
    raw := `{"if":[{"==":[{"var":"tenantTier"},"enterprise"]},"on","off"]}`
    ctx := map[string]interface{}{"tenantTier": "enterprise"}
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        var rule map[string]interface{}
        json.Unmarshal([]byte(raw), &rule) // the cost we're eliminating
        evaluateJsonLogic(rule, ctx)
    }
}

Expected result: BenchmarkCompiledAST should run 10–50× faster than BenchmarkParsedRule. If the ratio is lower, confirm the compile step runs before the benchmark loop, not inside it.

Troubleshooting & FAQ

Why is p99 high even though p50 is under 1 ms?

p99 outliers with a healthy median usually point to GC pauses, lock contention, or OS scheduling jitter — not to the rule logic itself. Add a histogram metric for allocation count per evaluation and look for correlation with GC events. In Go, runtime/trace will show you GC stop-the-world pauses alongside your goroutine schedule.

How do I know if AST compilation is actually running at init?

Add a log line and a counter (flag_rules_compiled_total) in loadFlags. On startup you should see one log entry per flag per version, and the counter should reach its final value before the first HTTP request is served. If you see parse-related log lines at evaluation time, the compiled tree is not being used.

Do I need to recompile all rules when one flag changes?

No. Compile rules keyed by flag_key + rule_version. When the provider receives an update for a single flag, recompile only that flag’s targeting tree. This keeps the recompile cost proportional to the size of the change, not the total number of flags. See precompiling targeting rules into an AST for the incremental update pattern.

What happens to evaluations during a recompile?

Swap the compiled map atomically: build the new AST into a fresh map, then replace the pointer in a single atomic store or mutex-protected assignment. In-flight evaluations finish against the old tree; new evaluations pick up the updated tree. Never mutate the live map in place while evaluations may be reading it.

Should I cache evaluation results instead of just compiling the rules?

They solve different problems and often stack. Compiling to an AST removes parse cost from every call; caching the result removes the walk cost for repeated (flag, context) pairs. Result caching pays off when the same context evaluates the same flag many times in a short window — but it is only safe when the cache key captures every context attribute the rule reads, or you will serve a stale variant to a context that should have flipped. Keep the key derived from the rule’s referenced attributes, keep the TTL short, and treat the compiled AST as the always-correct fallback. See distributed caching for flag evaluations for the invalidation model.

Is a compiled AST faster than a bytecode or table-driven evaluator?

For the rule sizes typical of feature flags — a handful of predicates joined by and/or — a tree-walking AST interpreter is fast enough and far simpler to debug, so start there. Bytecode compilation (flattening the tree into a linear instruction sequence) mainly helps by improving instruction-cache locality and removing pointer-chasing on very large or very hot rules, and only becomes worth the complexity once profiling shows the tree walk itself, not parsing or attribute lookup, dominating your budget. Measure before you reach for it; most teams never need to.

How many predicates before a rule needs restructuring?

There is no hard limit, but a targeting rule that grows past roughly a dozen predicates or nests more than three or four levels deep is usually encoding something that belongs in a reusable segment instead. Beyond the latency cost, deep rules are hard for humans to reason about and become a source of targeting bugs. Extract the shared condition into a named segment, reference it from the flag, and the engine evaluates it once with a cheaper, flatter tree. If a single rule is genuinely large and hot, that is the signal to profile the walk and consider the bytecode approach above.

Does context attribute order or count affect evaluation speed?

Count does, order does not. The walker looks up attributes by key, so a hash-map read is O(1) regardless of where the key sits, but a fatter context still costs more to build, serialise, and hand across the SDK boundary before evaluation even starts. Strip non-targeting keys at the API edge so the engine receives a thin, flat context — five keys the rules actually read, not the fifty-key user object your handler happens to have in scope. See context enrichment strategies for targeting for where to draw that boundary.

Performance & Scale

At high request rates the rule engine is evaluated millions of times per minute across nodes in the fleet. The key insight is that the cost is additive: every extra predicate, every unindexed context key, every avoidable regex adds a fixed overhead to every request. A 0.3 ms per-evaluation improvement on a service processing 10,000 req/s saves 3 CPU-seconds per second — enough to remove a replica.

Propagating rule changes to all nodes in the fleet without a latency spike requires that recompilation happen in a background goroutine, not inline with the update event. See server-side SDK integration patterns for the lifecycle hooks that make this safe.

The additive-cost framing also changes how you reason about scaling out. Adding replicas hides a per-call regression from your dashboards — average latency stays flat because each node is doing the same slow work in parallel — but it does nothing for the tax itself; you are simply paying it on more machines. This is why a rule-engine regression is easy to miss in a horizontally scaled fleet and expensive once found: the symptom is a creeping infrastructure bill and a p99 that no capacity increase seems to fix, not an outage. The discipline that catches it is per-evaluation instrumentation with a CI benchmark gate, so a rule or code change that adds 0.2 ms to the walk fails the build instead of silently consuming a replica’s worth of capacity three deploys later.

A second scale effect worth naming is the memory footprint of the compiled trees themselves. Compiling every flag to an AST trades CPU on the hot path for resident memory that scales with flag count times rule complexity times, if you keep old versions during rollouts, version depth. For a few hundred flags this is negligible — kilobytes — but a fleet with tens of thousands of flags, or one that never evicts superseded versions, can grow the compiled map into hundreds of megabytes per process. Cap the version history you retain (two or three versions is plenty to cover in-flight evaluations during a swap) and evict the rest, or the parse-once win quietly turns into a memory-pressure problem that itself provokes GC.