Taming P99s in OpenFGA: How We Built a Self-Tuning Strategy Planner

OpenFGA reduced P99 tail latency by up to 98% using a self-tuning strategy planner based on Thompson Sampling. The system treats graph traversal as a multi-armed bandit problem, maintaining probability distributions for each traversal strategy and continuously learning from production latency. By encoding domain knowledge through carefully tuned Normal-Gamma priors, the planner balances exploration and exploitation, automatically adapting to changing data distributions. The solution uses lock-free atomic operations for concurrency and proved more robust than static heuristics in multi-tenant production environments.