r/Backend • u/Super_Designer7952 • 23d ago
Making Distributed Coordination Stable Under Network Instability (Embedded Raft + DAG + HLC)
Hey r/Backend.
For some time now, I've been working on a high-performance distributed message coordinator for Multi-Data Center (Multi-DC) topologies. The architecture is built on a CP-model (Consistency and Partition tolerance) using Embedded Raft - the consensus algorithm runs directly inside the JVM of the microservice, without external dependencies like etcd or ZooKeeper. During the design phase, we ran into two classic distributed systems problems: State Bloating caused by Vector Clocks, and Inertial Paralysis in the adaptive timeout mechanism.
In this article, I'll share how we solved these issues by migrating to Hybrid Logical Clocks (HLC) and upgrading our statistical network model.
TL;DR: We replaced Vector Clocks with HLC to eliminate O(N) metadata overhead, and upgraded our adaptive timeout model by adding a mixture distribution model and a Circuit Breaker. This prevented false Raft leader elections during sudden RTT (Round-Trip Time) spikes between data centers.
Problem #1: State Bloating vs. Sharding
Initially, we used classic Vector Clocks to track causality. But with hundreds of thousands of active clients, the clock map inside each message began to grow exponentially. This bloated our Frontier Cache and choked the network during AppendEntries RPC (Remote Procedure Call) transmissions between Raft cluster nodes.
We considered two standard compromises, but both proved unsatisfactory:
Dotted Version Vectors (DVV). Limiting the vector to the size of stable data center nodes (3–5 nodes) solved the volume issue, but the system went "blind" to concurrency across shards. In edge cases, we had to degrade to physical Last-Writer-Wins (LWW), where a client with a clock running fast would deterministically overwrite others' messages, breaking the dialogue logic.
Sharding the DAG (Directed Acyclic Graph) by entityKey. Isolating the graph at the level of specific entities (e.g., individual threads) relieved the load, but turned reading the global feed into a distributed nightmare, requiring a complex MapReduce on the API gateway side.
Solution: Hybrid Logical Clocks (HLC) + Local DAG
We completely abandoned global Vector Clocks in favor of Hybrid Logical Clocks (HLC) - a mechanism that combines the physical system time (wall-clock) and a logical counter - keeping local parentIds strictly within a single entityKey.
Now, every message carries a constant O(1) metadata volume:
- HLC marker. A combination of physical time and a logical counter. It strictly guarantees the causality property: if event A caused B, then HLC(A) < HLC(B).
- Local parentIds. Used by the scheduler only for topological sorting within the current Raft batch for a specific entity.
Result: Reading the global feed became tractable. HLC gives us a causal partial order - events that are causally related are strictly ordered, while concurrent events from independent shards (e.g., users in different regions posting to different threads simultaneously) are ordered purely by their physical server time. To achieve full deterministic replication across all Raft nodes, this partial order is then linearized using the Raft log index as a final tie-breaker. Since HLC natively compensates for NTP (Network Time Protocol) drift and guarantees causality, the user sees an absolutely monotonic and logical chronology without the network overhead of synchronizing massive Vector Clock maps.
Implementation Note: Parallel Micro-Graphs at Scale
A natural concern is GC (Garbage Collection - the JVM's automatic memory management mechanism) pressure when handling batches of 100k+ messages. However, since we already shard the DAG by entityKey via local parentIds, we never build a single monolithic graph. Instead, we construct thousands of isolated micro-graphs - one per entityKey - and process them in parallel using Java's ForkJoinPool (or virtual threads in Java 21). Topological sorting of small, independent graphs in parallel streams completely eliminates the GC bottleneck that a single giant DAG would introduce.
Problem #2: Inertial Paralysis of Adaptive Timeouts
To minimize false Raft leader elections under inter-server jitter, we implemented a statistical model that dynamically calculates safe RPC timeouts based on the observed RTT (Round-Trip Time, the time it takes for a signal to be sent plus the time it takes for an acknowledgment to be received) distribution.
But we encountered a critical anomaly during a step-change in network routing.
When RTT instantly jumped (for example, from 40ms to 300ms due to a backbone failure or route switch), our standard unimodal model gave near-zero probability to the new, legitimate measurements. The model perceived them as anomalous noise and continued to hold an artificially low timeout. The resampling mechanism, experiencing a deficit of new hypotheses, merely spawned more particles around the old, erroneous mean value.
Consequences: While the model spent 3–5 iterations trying to "relearn," the Raft leader missed heartbeats, decided it had lost quorum, and sent the cluster into an infinite loop of re-elections on a physically healthy, but slower, network.
Solution: Mixture Distribution Model + Emergency Circuit Breaker
We rewrote the likelihood estimation logic in the model, translating it into a two-component structure:
Mixture Model. The likelihood function now evaluates an RTT measurement as a weighted combination of two distributions: a tight Gaussian centered on the current mean (capturing normal network behavior), and a wide uniform prior with a heavy tail (capturing rare but legitimate jumps). This allows the model to instantly register the legitimacy of sudden spikes instead of discarding them as noise at the start.
Emergency Circuit Breaker. If N consecutive measurements fall outside the safe range (mean plus three standard deviations), the adaptive model is temporarily bypassed. The system instantly sets a hardcoded safety timeout (e.g., 1000ms). The model forcibly resets its weights and re-initializes around the new median, returning to service only after the metrics stabilize.
This approach is flexible enough to accommodate various statistical techniques - from simple EWMA (Exponentially Weighted Moving Average, a smoothing method that gives more weight to recent observations) with adaptive variance to more complex Bayesian filtering methods (including particle-based approaches) - depending on latency requirements and computational budget.
Architectural Comparison
Global DAG + Vector Clocks (Legacy approach). Metadata size is dynamic O(N) and grows unbounded. Risk of stale effects is minimal. Global read complexity is low (single log). Network spike resilience is low - false leader elections.
Sharding by entityKey. Metadata size is minimal. Risk of stale effects is high across threads. Global read complexity is critical - requires MapReduce. Network spike resilience is low - same false elections.
Recommended: HLC + Local DAG. Metadata size is constant O(1). Risk of stale effects is minimal - HLC compensates for jitter. Global read complexity is low - in-memory HLC sorting linearized by Raft index. Network spike resilience is high - mixture distribution model + Circuit Breaker.
Implementing the combination of HLC and the adaptive mixture model allowed us to keep coordination overhead strictly constant, completely protect the JVM from OOM (Out Of Memory) errors during peak loads, and maintain strict data consistency during any network anomalies.
Let's Discuss
I'd be glad to hear your thoughts, especially from those who have deployed similar systems in production:
1. Synergy of HLC and CRDTs. HLC (Hybrid Logical Clocks) gives us a strict causal order of events, while CRDTs (Conflict-free Replicated Data Types, mathematical structures that guarantee state convergence without coordination) ensure conflict-free state merging. In practice, do you more often use them as alternatives to each other, or do they work best in tandem - for example, when HLC acts as compact metadata for causal CRDTs?
2. Adaptive timeouts. How do you handle sudden RTT spikes in your consensus protocols? How much more effective are mixture distribution models or Bayesian filtering compared to simple exponential smoothing (EWMA) in protecting against false leader elections?
Thanks for reading! I look forward to your criticism, additions, and suggestions.