A 24.6x Latency Gap That Had Almost Nothing to Do With Graph Search Copy

During the performance evaluation of Routavio, a multimodal travel planning and route optimization platform, we encountered an unexpected latency pattern.

The same route computation engine sometimes completed its first search pass in less than one second, while other executions required more than twenty seconds.

The transportation graph contained 24,774 nodes and 228,060 directed edges. It represented flight, rail, coach, and ferry connections obtained from heterogeneous transportation data sources.

Given the computational characteristics of graph traversal, our initial investigation focused on the routing algorithm.

However, the evidence eventually showed that the dominant latency component was not graph search.

It was graph loading.

This article presents the performance investigation, the experimental evidence that distinguished competing explanations, and the architectural modifications introduced to address the problem.

The measurements refer to Routavio's August 2026 pilot implementation, evaluated at repository revision 71e8cd39.

1. The Computational Context

Routavio represents transportation supply as a directed, time-aware graph.

Nodes correspond to locations such as airports, railway stations, coach terminals, and city anchors.

Edges represent transportation connections with attributes including mode, duration, provider, price evidence, and schedule information.

The routing engine performs a budget-bounded, heuristically pruned depth-first search over this network.

Unlike conventional shortest-path implementations operating on a complete static graph, the engine must accommodate incomplete transportation data and connections acquired during search.

The relevant computation pipeline can be summarized as follows:

Computation Request
        |
        v
Graph Loading / Cache Lookup
        |
        v
On-Demand Transport Data Acquisition
        |
        v
Nearby Airport and Station Expansion
        |
        v
Bounded Graph Search
        |
        v
Connection Feasibility Validation
        |
        v
Multicriteria Ranking
        |
        v
Itinerary Persistence
        |
        v
Search Result

The implementation uses PostgreSQL to persist transportation segments and computation state.

An in-memory adjacency structure is constructed from the relational transport data and reused by the worker process.

This architecture avoids introducing a separate graph database, but it introduces a potentially expensive graph materialization stage.

The original performance investigation did not initially distinguish this stage sufficiently from graph traversal.

That distinction became central to explaining the latency variation.

2. Formulating Competing Hypotheses

The performance anomaly was initially attributed to three possible causes.

Hypothesis H1: Algorithmic regression

A recent change to search heuristics might have increased graph traversal work or altered pruning effectiveness.

If this hypothesis were correct, slower searches would be expected to traverse substantially more edges, expand more nodes, or exhibit less effective pruning.

Hypothesis H2: Growth of the search space

The transportation graph could have become computationally more expensive as new segments were imported.

An increase in graph density or the number of eligible connections might produce greater traversal costs.

Hypothesis H3: Worker resource contention

The Node.js worker processed route computations through multiple logical execution slots.

Because graph traversal was synchronous JavaScript, these slots shared a single event loop.

Resource contention or event-loop blocking could therefore affect response latency.

All three explanations were technically plausible.

However, selecting the most plausible explanation is not equivalent to identifying the actual cause.

As Jain (1991) discusses in the context of computer systems performance analysis, meaningful evaluation depends on workload characterization, measurement selection, and the distinction between observed behavior and causal interpretation [1].

We therefore introduced measurements designed to distinguish these competing hypotheses.

3. Stratifying Latency by Cache State

The decisive observation was that slow executions correlated with the amount of time elapsed since the previous computation.

The graph adjacency structure was cached inside the worker process with a time-to-live.

This meant that the next search could encounter either a warm graph or an expired cache requiring reconstruction.

We grouped first-pass latency measurements by the elapsed time since the previous computation.

The August 2026 pilot measurements produced the following results.

The difference between the warm-cache and cold-cache medians was approximately:

Cold / Warm Median Ratio

22,838 ms / 927 ms = 24.6

The result revealed an important relationship between cache lifecycle state and first-pass execution time.

A request arriving shortly after a previous computation generally benefited from a resident graph.

A request arriving after cache expiration could incur the cost of rebuilding the complete adjacency structure.

However, this observation alone was not sufficient to prove the precise cause.

A change in request frequency might coincide with other factors, including provider latency, background jobs, or route complexity.

Further instrumentation was necessary.

4. Separating Graph Loading from Search Execution

The next step was to inspect the work performed by representative slow and fast computations.

The pilot telemetry recorded the following counters:

These measurements were particularly informative.

The slow computation traversed somewhat more edges and expanded somewhat more nodes, but the difference in traversal work was insufficient to explain a latency gap exceeding twenty seconds.

Both runs exhibited the same reported pruning ratio.

The event-loop lag measurements did not support the hypothesis that increased event-loop contention was responsible for the large difference.

Instead, nearly the entire additional delay was concentrated in graph loading.

The analysis therefore shifted from algorithmic complexity to cache lifecycle behavior.

5. Latency Decomposition as a Diagnostic Method

A useful conceptual model separates the first computation pass into several components.

T_pass1 =
    T_graph_load
  + T_graph_search
  + T_validation
  + T_other

This is a conceptual decomposition rather than a claim that every component was independently measured with identical precision.

The distinction matters because a metric named search_duration can be misleading if it includes database acquisition, graph construction, and actual traversal.

In Routavio's investigation, the performance problem was initially examined as a search regression because the recorded phase timer did not make the graph-loading contribution sufficiently visible.

Separating the graph-loading term provided the evidence needed to reject the earlier explanations.

The case illustrates a broader methodological problem in performance engineering.

An aggregate latency measurement identifies the existence of a delay, but not necessarily the subsystem responsible for it.

Useful instrumentation should distinguish between competing causal explanations rather than simply confirming that an operation was slow.

This principle is consistent with the experimental methodology developed in Jain's The Art of Computer Systems Performance Analysis [1].

6. Why Graph Cache Lifecycle Matters

The adjacency structure was maintained as a process-local cache.

Transportation segments were stored in PostgreSQL, and the worker materialized the graph in memory when required.

This arrangement provided several architectural advantages:

• Relational storage supported reporting, auditing, and data integrity.
• Graph traversal operated on an in-memory representation.
• A dedicated graph database was unnecessary.
• The system avoided additional stateful infrastructure components.

However, the approach also created a substantial cold-loading cost.

The relevant distinction was not simply between cached and uncached data.

It was between a graph that remained resident inside the correct process and a graph that required reconstruction before an interactive computation could proceed.

A scheduled operation running in a different process could not warm the worker's module-scoped graph cache.

The cached object belonged to the worker's runtime.

This type of locality problem has conceptual connections to Denning's working-set model [2].

Denning's original work concerned virtual memory and program locality rather than application-level transportation graph caches. Nevertheless, the general principle that frequently required data should remain accessible within an appropriate memory residency policy is relevant.

For Routavio, the problem was especially visible because transportation graph materialization had a much higher cost than reusing an existing adjacency structure.

7. Correcting the Cache Lifecycle

The selected corrective approach consisted of two mechanisms.

7.1 Refresh-ahead

Rather than waiting for cache expiration to force an interactive request to rebuild the graph, the worker refreshes the graph ahead of expiry.

The existing cached representation remains available while the refresh operation is performed.

This approach reduces the probability that a user-facing computation encounters an expensive cold path.

It does not eliminate the underlying cost of graph construction.

Instead, it changes when that cost is incurred.

This distinction is important when interpreting a performance improvement.

Reducing user-visible latency is not necessarily equivalent to reducing the total computational work performed by the system.

7.2 Cache warming during worker startup

A second mechanism warms the graph cache when the worker process starts.

Without startup warming, the first request after deployment or process restart could become responsible for constructing the entire graph.

With an explicit warm-up mechanism, graph initialization can occur before an interactive route computation requires the structure.

The implementation therefore addresses two separate lifecycle events:

1. Routine cache expiration during operation.
2. Process startup following deployment or restart.

Both events previously risked exposing expensive graph loading to users.

8. Why Increasing the Cache TTL Was Not Sufficient

Extending cache lifetime would appear to be the simplest response to the problem.

If a longer TTL reduces cache misses, it should also reduce the frequency of expensive graph reconstruction.

However, transportation supply is not static.

Routavio periodically imports new transportation connections and acquires additional information from upstream providers.

A graph retained for too long may exclude newly available routes.

The application could continue operating without an exception while silently returning incomplete itinerary results.

This creates a trade-off between computation latency and transportation-data freshness.

Let A(t) represent the age of the graph since its last successful refresh.

Let L(t) represent the time required to access or reconstruct the graph.

A longer retention interval may reduce expected reconstruction frequency, but it can increase the age of the transportation data represented by the search.

The relevant engineering objective is therefore not simply to minimize cache misses.

It is to preserve an acceptable combination of response latency, data freshness, memory consumption, and itinerary quality.

For Routavio, increasing the TTL alone was rejected in favor of refresh-ahead and startup warming.

9. Dynamic Edge Insertion and Memory Pressure

The cache architecture also interacted with on-demand transportation data acquisition.

During an active search, an upstream provider could introduce flight connections that were not present in the initial graph.

These new edges needed to become visible to the ongoing computation.

The direct implementation approach was to invalidate the graph cache and reload the entire structure.

However, the old graph could still be referenced by an active computation.

Reconstructing a second graph under these conditions temporarily increased memory consumption.

In the pilot environment, this behavior caused worker crash loops.

The implemented correction was incremental graph splicing.

Newly persisted edges were incorporated into the existing cached adjacency structure, while stale entries for corresponding segment identifiers were replaced.

This avoided constructing a second complete graph merely to introduce newly acquired transportation connections.

The incident demonstrates why memory management must be considered alongside algorithmic complexity.

An operation with acceptable theoretical computational complexity may still be unsuitable when its allocation behavior exceeds the limits of a constrained runtime.

10. Interpreting the Results Through Tail Latency Research

Dean and Barroso (2013) discuss the importance of latency variability in large-scale interactive systems [3].

Their research emphasizes that average performance alone is insufficient when occasional slow operations can significantly affect user experience.

Routavio's pilot represents a different scale and architecture, but the measurement problem is related.

The overall latency distribution contained requests operating under different cache conditions.

Aggregating these observations without separating the relevant runtime states obscured an important source of variability.

The warm-cache median of 927 ms and the cold-cache median of 22,838 ms described substantially different operating regimes.

These were not measurements of two competing route optimization algorithms.

They were observations of the same system under different cache lifecycle conditions.

This distinction changes the interpretation of the result.

It would be incorrect to claim that Routavio's graph search algorithm became 24.6 times faster.

The evidence instead indicates that cold graph loading was responsible for a major component of first-pass latency variation.

The corrective mechanisms were designed to remove that expensive cold path from the normal user-facing experience.

11. Experimental Limitations

The investigation was conducted in a deployed pilot environment rather than under fully isolated laboratory conditions.

Measurements were recorded on 26 and 27 August 2026, using a single-host environment running application containers, PostgreSQL, background computation, and observability components.

Several limitations must be acknowledged.

First, the cache-state measurements were observational.

Request characteristics, scheduled jobs, and upstream data acquisition were not fully controlled across groups.

Second, the comparison between representative slow and fast runs supported the diagnosis but did not constitute a randomized experiment.

Third, the reported 24.6 ratio compared medians from different cache-state populations.

It was not a directly measured universal speedup produced by a subsequent deployment.

Fourth, the measured first-pass durations should not be confused with complete end-to-end user response times.

A separate seven-day sample of 2,864 interactive computation runs reported a median time to provisional result publication of 7,284 ms. That metric covers a different operational boundary and should not be compared directly with the first-pass medians.

Finally, the load-testing results did not establish the maximum capacity of the application.

At ten virtual users, the CDN began rate-limiting the load generator before the origin application reached saturation.

The actual application saturation point remained unmeasured.

These distinctions prevent performance measurements from being interpreted beyond the evidence available.

12. Implications for Route Optimization Systems

The investigation produced several practical conclusions for multimodal travel planning architectures.

12.1 Algorithmic optimization should follow latency attribution

A complex graph search system may contain expensive operations outside traversal itself.

Reducing path exploration is not necessarily useful if most user-visible latency originates from loading or constructing the graph.

12.2 Cache state should be treated as a measurement variable

Latency samples collected under different cache states should be separated where the difference is operationally meaningful.

Otherwise, changes in traffic frequency may appear to be changes in algorithm performance.

12.3 Freshness and performance must be evaluated together

Transportation data changes over time.

An aggressive caching policy that improves response speed while hiding newly available routes may reduce the practical quality of the travel planner.

12.4 Process boundaries determine cache behavior

A graph cached inside one worker process is not automatically available to another process.

Cache warming and invalidation policies must respect the runtime topology of the application.

12.5 Dynamic updates require explicit memory management

Reloading a complete graph after every on-demand data acquisition can introduce avoidable allocation pressure.

Incremental updates may offer a more appropriate trade-off, provided graph consistency is maintained.

Conclusion

The most important optimization in this investigation was not a modification to the route search algorithm.

It was identifying that the apparent search latency problem belonged primarily to graph-loading lifecycle management.

Once graph construction and traversal were measured separately, previously plausible explanations could be rejected.

The findings supported a revised cache architecture with refresh-ahead, worker startup warming, and incremental graph updates.

More broadly, the investigation demonstrates that performance engineering requires a precise understanding of what a measurement includes.

For multimodal route optimization systems, improving the quality of a pathfinding algorithm is only one part of delivering useful travel recommendations.

The system must also make transportation data available to that algorithm within a predictable computational budget.

Previous Article

Why Dijkstra Was Not Our Default for Multimodal Route Optimization

Related Engineering Research

Engineering a Multimodal Travel Planner on a 228,060-Edge Graph

References

[1] Jain, R. (1991). The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation, and Modeling. John Wiley & Sons. ISBN 978-0-471-50336-1. https://www.cs.wustl.edu/~jain/books/perfbook.htm

[2] Denning, P. J. (1968). The Working Set Model for Program Behavior. Communications of the ACM, 11(5), 323–333. https://doi.org/10.1145/363095.363141

[3] Dean, J., & Barroso, L. A. (2013). The Tail at Scale. Communications of the ACM, 56(2), 74–80. https://doi.org/10.1145/2408776.2408794

[4] Kleppmann, M. (2017). Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems. O'Reilly Media.

[5] Çınar, H. (2026). Design and Implementation of a Multimodal Door-to-Door Travel Metasearch Platform with a Bounded Graph-Based Route Computation Engine and an Observability-Driven Deployment Pipeline. Sabancı University. Public technical edition, repository revision 71e8cd39, Sections 5.1.1, 5.1.4, 6.2.2–6.2.3, and 7.1.2.

Project: Routavio | Multimodal Travel Planner and Route Optimization

All reported measurements refer to the evaluated August 2026 pilot environment. They are historical observations rather than guarantees of current platform performance.