When Your Search Tree Becomes the Bottleneck in a Distributed Game Server

The Problem We Were Actually Solving

In Hytales Veltrix region server, each treasure hunt request had to traverse every placed container, ore vein, and hidden chest within a 256-block radius. The server runs at 60 ticks per second with 120 concurrent players, so per-player search latency had to stay below 16ms. What I measured on a representative region was 28–42ms for a single search call, and that was with LuaJITs JIT already hot.

The real problem wasnt Luas speed; it was the index. We stored treasure locations in a flat Lua table keyed by chunk coordinates, then filtered with a hand-written loop. On regions with 12k chunks, the loop touched 12k entries per search. A profiler flame graph showed 63% of CPU time inside luaH_getstr—hash lookups—plus 22% in the Lua VM loop. The index didnt scale; the language wasnt the bottleneck.

What We Tried First (And Why It Failed)

I tried three Lua-based optimizations before touching the runtime:

1. A bloom filter over chunk coordinates to skip empty ones. Result: bloom false-positive rate 11% causing extra hash table probes, latency variance spiked to 78ms on hot paths.


2. A C module that precomputed spatial hashes in a flat array. Result: still Lua-facing memory allocations caused GC pauses up to 5ms at 95th percentile.


3. LuaJITs FFI to call quickjss JSONPath. Result: GC pressure moved from Lua to JS VM, plus the call boundary added 300ns per search—negligible per call, but multiplied across 120 players it was 36ms extra per tick.

Every fix moved the constraint but didnt remove it. At that point I accepted the truth: the problem wasnt Luas speed; it was the data structure and the runtimes GC behavior under load.

The Architecture Decision

We picked Rust for the indexer and moved the treasure search workload into a separate process. The rationale was fourfold:

1. Zero-cost abstractions: an R-tree from the rstar crate could index 2D points with O(log n) queries and no dynamic dispatch.


2. No GC: allocations in the indexer process wouldnt pause the main game loop.


3. Serialization boundary: we could use flatbuffers to serialize only the search results back to Lua, reducing cross-process data transfer.


4. Safety: we had already hit segfaults in Lua C modules when the game patched memory in-place; Rusts borrow checker eliminated that class of bugs.

The tradeoff was latency: round-trip via FlatBuffers added 150µs per search, but we gained predictability. More importantly, the indexer process could grow its heap without affecting the LuaJIT GC pause times.

What The Numbers Said After

After the switch, we ran identical 10-minute load tests on the same region with 120 bots. Metrics collected with perf_4.19 and flamegraph.pl:

• LuaJIT main loop: 2.1ms per tick median, 3.8ms 95th percentile (was 6.4ms / 12.1ms)


• Treasure search per request: 1.8ms median, 3.9ms 95th percentile (was 28ms / 42ms)


• Indexer RSS: 48MB resident, growing 2MB per 1000 searches (stable)


• GC pauses in LuaJIT: 0.1ms median, max 1.2ms at 99.9th percentile (was 4.2ms / 5.8ms)

The system still saturates CPU at 105 players, but the treasure search component is now 20x faster and no longer a contributor to tick jitter. The allocation rate in the indexer process, measured via /proc/[pid]/smaps, is 1.4 allocations per search, totaling 3.8KB per second at 120 players.

What I Would Do Differently

I would not have moved the entire treasure logic to Rust. The cross-process serialization cost is small in absolute terms, but it adds complexity in logging, debugging, and versioning the FlatBuffers schema. Next time Id keep Lua for the high-level hunt API and use Rust only for the spatial index and culling.

I would also avoid rstars default R*-tree if the dataset is static for long periods. We measured 3ms to rebuild the tree on region load; switching to a packed Hilbert R-tree from the quadtree crate cut rebuild time to 0.4ms without changing query performance.

Finally, I would instrument the indexer process with tikv-jemalloc-rs from day one. We did post hoc analysis and found the jemalloc arena used 32MB at startup; by pre-tuning arenas and background threads we shaved an extra 0.7ms off 99th percentile latency.