Continuous Anti-Entropy Data Repair for Sustainable Operations

Wide-area networks inevitably experience transient failures, packet loss, and latency spikes, all of which can disrupt inter-site communication and lead to missed replication updates. Over time, data divergence is not a possibility; it is a certainty unless there is an explicit reconciliation mechanism.

Anti-entropy (as an allusion to thermodynamics) refers to the process of detecting and repairing divergence between replicas, restoring consistency across distributed datasets. Many criticisms of eventual consistency stem not from the model itself but from operational challenges such as manual repair procedures, prolonged inconsistencies, and limited visibility into reconciliation processes.

Stratum’s continuous anti-entropy process is implemented as a built-in background repair loop that:

• Detects and repairs missed replication updates
• Reconciles divergence after prolonged network partitions
• Synchronizes data after site restarts or failures
• Bootstraps new sites by automatically converging them to current state

Anti-entropy is a well-established concept in distributed storage systems, with similar mechanisms appearing in widely deployed databases through repair processes, read-repair techniques, and background synchronization. However, in many deployments, achieving full data convergence still requires scheduled or operator-driven repair actions, increasing operational overheads and recovery times.

Stratum instead embeds anti-entropy as a continuous, automated process while still exposing tuning controls, metrics, and alarms that give operators visibility and control without requiring manual intervention. Production experience has shown that the CPU cost and impact on clients associated with anti-entropy is minimal, even under failure or bootstrap conditions that require a high degree of data repair. This efficiency is achieved by leveraging the system’s distributed architecture and by using optimized data structures, such as the elastic binary Merkle tree.

Combined with scalable push-based replication, this design enables rapid replica convergence under normal conditions. The vast majority of replication updates propagate successfully on the first attempt and converge within the inter-site network latency window. For the very small fraction of updates affected by transient network failures, the background anti-entropy process detects and reconciles divergence at configurable intervals, allowing operators to balance system performance considerations against acceptable time windows of data staleness. It should be noted that because each replication update conveys the current state of the record, any updates lost due to transient failures are corrected by the next successful replication update, eliminating the need for explicit repair in chains of successive writes.

As a result, the system delivers behavior that appears strongly consistent from a client perspective during normal operation, while preserving availability during severe failure scenarios such as network partitions.

Probabilistically Bounded Staleness (PBS) is often utilized as a consistency model that quantifies the probability of data staleness between database replicas in an eventually consistent system. PBS provides a systematic explanation for why eventually consistent databases often appear strongly consistent in practice, even without deterministic bounds on staleness.

To illustrate, we used a Monte Carlo simulation that repeatedly generates random executions of the system under a given set of parameters, observing the frequency of stale reads. The simulation accounts for factors such as inter-replica network latency, replication failure probability, and the configured anti-entropy check interval.

Figure 7: Merge of two concurrent Add operations for the same record on different datacenters.

For example, consider a system with 3 replicas and a 30 millisecond inter-replica network latency, a variable probability of network failure, and a 300 millisecond anti-entropy check interval.

The resulting PBS curves exhibit a sharp increase at the network latency boundary (30ms), indicating that reads become fresh in the majority of cases as soon as the replication update reaches the remote replica. A small probabilistic tail represents rare situations in which the replication message is lost due to the configured network failure rate and reconciliation must occur through the anti-entropy mechanism.

As the probability of network failures increases, the likelihood that anti-entropy requires multiple reconciliation rounds also increases. Nevertheless, the probability distribution shows that replicas converge rapidly, and data becomes consistent with very high probability within only a few anti-entropy cycles.

This demonstrates that the likelihood of observing stale data beyond the network latency window remains extremely small under normal network conditions, causing the system to appear effectively strongly consistent from the perspective of an external client.

It is important to note that this scenario does not include full network partitions or severe network degradation failures; such failures would fall under the network partition category, where PACELC necessitates a trade-off favoring availability over strict consistency.