Fast, Non-Blocking Conflict Resolution with Merkle Trees

October 20, 2026

Network partitions are an unfortunate reality when operating a distributed data grid—right up there with TCP retransmits and the discovery that your "five nines" availability calculation didn’t account for leap seconds. When a network split occurs, different partitions may continue servicing writes, causing them to diverge. Once the network heals and the partitions merge, Infinispan’s partition handling and conflict resolution mechanisms reconcile divergent states to restore consistency.

Historically, determining which entries conflicted between replicas during a partition merge could be an expensive operation. Even if only a handful of keys were modified while partitioned, traditional conflict detection often required write owners to scan and transmit all entries within affected segments across the cluster. For large caches with millions of entries, this created heavy network traffic, CPU spikes, and latency spikes at the exact moment the cluster was attempting to recover.

Infinispan 16.3 introduces a new hierarchical Merkle tree-inspired hash comparison mechanism that dramatically reduces network traffic during conflict resolution. The implementation combines this hierarchical tree structure with an in-flight running XOR hash computed at entry update time, and re-architects the conflict resolution process to be completely non-blocking.

This post explores how the hierarchical Merkle tree conflict resolution works, why computing hashes incrementally at write time is essential for scalability, analyzes the Big-O time and network complexities, and presents JMH benchmark results demonstrating the performance benefits.

The Problem: Partition Recovery and The Cost of Full Segment Comparison

Infinispan splits the cache keyspace into a fixed number of consistent hash segments (typically 256). Each segment is owned by one or more nodes depending on the configured numOwners.

When a cluster partitions, nodes in separate partitions may update keys in the same segments. When the partitions merge, the ConflictManager must inspect the replicas on write owners, detect conflicting entry versions, and apply a conflict resolution merge policy (such as PREFERRED_ALWAYS, REMOVE_ALL, or a custom EntryMergePolicy).

Previously, discovering whether replicas diverged required pulling all entries for each segment from the replica nodes:

Node A requests all entries for segment $S$ from Node B and Node C.
Node A receives every key, value, and metadata record for segment $S$.
Node A compares each entry version to detect conflicts.

Imagine a segment containing 50,000 entries where each entry’s average payload is 1 KB. Resolving a single segment requires transferring ~50 MB of data over the network. Multiply that across hundreds of segments, and a partition merge could easily saturate network bandwidth with gigabytes of redundant state transfer—even if 99.9% of the entries were completely identical! It’s like photocopying an entire phonebook to verify that only one person changed their number.

Hierarchical Merkle Tree Hash Comparison

To avoid sending unchanged data across the wire, PR #16890 implements a three-level hierarchical hash comparison inspired by Merkle trees:

Level 1: Segment Level Check

First, write owners compare a single 64-bit aggregate hash for the entire segment. If all replicas produce identical segment hashes, we know with high probability that all entries and metadata versions in that segment are identical. The entire segment is skipped immediately: 0 entries transferred over the network.

In real-world network partitions, many segments are never touched during the split. The segment-level check allows them to be reconciled with a single roundtrip exchanging a few bytes of hash data.

Level 2: Bucket Level Check

If the segment hashes differ, we know at least one entry has diverged. Instead of jumping directly to fetching all entries, the segment is subdivided into 32 deterministic buckets based on the entry hash:

int bucketIndex = (entryHash >>> 27) & 0x1F; // 32 buckets [0..31]

The nodes exchange bucket hashes using GetBucketHashesCommand. By comparing the 32 bucket hashes, the coordinator pinpoints exactly which sub-ranges of the segment diverge.

Level 3: Selective Entry Fetch

For each bucket where the hash matches, no entries are fetched. For buckets where hashes mismatch, the coordinator sends GetBucketEntriesCommand to fetch only the entries residing in those specific buckets. Replicas then compare only those entries and resolve the conflicts.

Boundary Optimizations and Fail-safes

Small Segment Threshold: For segments with $\le 64$ entries, dividing into 32 buckets adds extra RPC overhead for minimal data savings. If a segment is small, the system skips bucket hashing and directly fetches the segment entries.
All-Buckets Fast Path: If all 32 buckets differ, attempting selective bucket fetching only adds command overhead. The fast path detects this and immediately transitions to streaming the full segment.
Fail-Safe Fallback: If any node experiences a deserialization error, RPC timeout, or unsupported version during hash negotiation, the manager transparently falls back to the legacy full segment reconciliation without failing the merge.

In-Flight Hash Computation: Running XOR Hashes

While the hierarchical Merkle tree approach is theoretically sound, a critical question remains: where do the segment and bucket hashes originate?

A naive approach would iterate the cache data container on-demand when a conflict occurs, hashing every entry in the segment and bucket. However, this creates a major bottleneck: scanning hundreds of thousands of entries across hundreds of segments at partition merge time causes significant CPU spikes, thread contention, and memory allocations. Right when the cluster is already recovering, we would be thrashing the CPU with full data scans!

To eliminate this cost, we added an in-flight running XOR hash tracking mechanism that is only enabled when conflict resolution is configured.

The Power of XOR Associativity

XOR ($\oplus$) has three fundamental mathematical properties that make it ideal for running distributed set hashes. If you’ve ever wondered what XOR is good for besides confusing CS101 students, here’s your answer:

Commutativity: $A \oplus B = B \oplus A$ (order of entry insertion does not matter).
Associativity: $(A \oplus B) \oplus C = A \oplus (B \oplus C)$.
Self-Inversion (Identity): $A \oplus A = 0$ and $A \oplus 0 = A$.

Because XOR is self-inverting and commutative, we do not need to rescan the container when data changes. We can maintain a running hash incrementally:

Entry Added: segmentHash ^= hash(key, value, version)
Entry Updated (old value replaced by new value): segmentHash ^= hash(key, oldValue, oldVersion) ^ hash(key, newValue, newVersion)
Entry Removed / Evicted: segmentHash ^= hash(key, oldValue, oldVersion)

The same XOR operation is simultaneously applied to the corresponding bucket hash array (bucketHashes[bucketIndex] ^= entryHash).

Interceptor Architecture

We integrated this into Infinispan’s interceptor chain via SegmentHashInterceptor and SegmentHashTracker:

public class SegmentHashTracker {
   private final AtomicLongArray segmentHashes;
   private final AtomicLongArray bucketHashes; // 32 buckets per segment

   public void updateEntry(int segment, long oldEntryHash, long newEntryHash) {
      long delta = oldEntryHash ^ newEntryHash;
      segmentHashes.accumulateAndGet(segment, delta, (current, d) -> current ^ d);

      int bucketIndex = getBucketIndex(newEntryHash);
      int bucketOffset = (segment << 5) + bucketIndex;
      bucketHashes.accumulateAndGet(bucketOffset, delta, (current, d) -> current ^ d);
   }
}

Because hash updates run inside SegmentHashInterceptor during normal put, remove, and eviction operations, maintaining the hash costs only a few CPU clock cycles ($O(1)$) per write.

When conflict resolution runs: * Segment hash retrieval is $O(1)$ (an atomic read). * Bucket hash retrieval is $O(1)$ (reading 32 longs). * Zero data container iteration is required during recovery, when no conflicts are present!

Making Conflict Resolution Fully Non-Blocking

Infinispan has invested heavily in a non-blocking architecture, offloading I/O to Netty and keeping worker threads unblocked. Conflict resolution cannot be an exception.

The updated DefaultConflictManager utilizes asynchronous composition (CompletionStage) from start to finish:

Segment hash requests are dispatched asynchronously across all write owners using non-blocking transport commands.
If hashes match, the segment resolution stage completes immediately without switching threads.
If hashes mismatch, GetBucketHashesCommand is dispatched asynchronously.
Bucket comparisons run concurrently, and only mismatched buckets trigger asynchronous GetBucketEntriesCommand fetches.
Entry conflict resolution policies run reactively as chunks arrive, completing a CompletableFuture<Void> when all segments are verified.

At no point does the conflict resolution flow block the calling thread or Netty event loops.

Big-O Complexity Analysis

Let: * $S$: Total number of segments in the cache. * $N$: Average number of entries per segment ($Total = S \times N$). * $B$: Number of buckets per segment ($B = 32$). * $C$: Number of entries modified or conflicting in a segment during the partition ($0 \le C \le N$). * $E$: Average byte size of an entry (key + value + metadata). * $H$: Byte size of a hash ($8$ bytes for a 64-bit long).

Time Complexity at Conflict Resolution Time

Table 1. Time Complexity Comparison (per segment)
Operation	Legacy Full Scan	On-The-Fly Merkle Scan	In-Flight XOR Merkle
Hash Computation at Recovery	N/A	$O(N)$	$O(1)$
Segment Comparison	$O(N)$	$O(1)$	$O(1)$
Bucket Comparison (if divergent)	N/A	$O(B)$	$O(B) = O(1)$
Write / Update Overhead	$O(1)$	$O(1)$	$O(1)$ (bitwise XOR)

Network Data Transfer Complexity

Table 2. Network Traffic Transferred (per segment)
Scenario	Legacy Conflict Resolution	Hierarchical Merkle Tree	Traffic Reduction
No divergence ($C = 0$)	$N \times E$ bytes	$1 \times H$ bytes (8 bytes)	$\approx 100\%$ reduction
Sparse divergence ($C \ll N$)	$N \times E$ bytes	$B \times H + \min(C, B) \times \frac{N}{B} \times E$	$\approx 90\% - 99\%$ reduction
Full divergence ($C \approx N$)	$N \times E$ bytes	$B \times H + N \times E$ (fast path)	Overhead bounded by $32 \times 8 = 256$ bytes

When $C = 0$ (no writes in that segment during partition), network payload drops from tens of megabytes to 8 bytes. When only a few keys differ ($C \ll N$), instead of streaming the entire segment, only the mismatched buckets are transferred, cutting network bandwidth consumption by over 90%.

JMH Benchmark Reproducer: Testing Actual Conflict Resolution in a 6-Node Cluster

To benchmark actual conflict resolution performance in a realistic distributed environment rather than just raw hashing primitives, this JMH benchmark boots a real 6-node Infinispan cluster (DIST_SYNC, numOwners = 2), populates 100,000 cache entries across 256 segments, induces real version conflicts across the cluster nodes, and measures ConflictManager.resolveConflicts().

Inducing Real Conflicts in a 6-Node Topology

Infinispan provides Flag.CACHE_MODE_LOCAL, which bypasses network replication and applies an update only to the local node’s data container. By writing entries normally across the 6-node grid and then overwriting a subset of those keys locally on specific backup nodes (nodes 1 through 5) using Flag.CACHE_MODE_LOCAL, we create genuine replica divergence: * The primary and backup owners hold differing values and version metadata. * Divergence is distributed across different physical nodes in the cluster. * The ConflictManager must detect the divergence across remote nodes and apply the merge policy to reconcile the entire grid.

The benchmark compares: 1. Merkle Tree Conflict Resolution (hashBuckets = 32): The new hierarchical approach using in-flight XOR segment and bucket hashes across all 6 nodes. 2. Legacy Conflict Resolution (hashBuckets = 0): The baseline implementation where all segment owners stream full segment contents over JGroups transport.

Here is the complete benchmark source code:

package org.infinispan.benchmark.conflict;

import org.infinispan.Cache;
import org.infinispan.configuration.cache.CacheMode;
import org.infinispan.configuration.cache.ConfigurationBuilder;
import org.infinispan.configuration.global.GlobalConfigurationBuilder;
import org.infinispan.conflict.ConflictManager;
import org.infinispan.conflict.ConflictManagerFactory;
import org.infinispan.conflict.MergePolicy;
import org.infinispan.context.Flag;
import org.infinispan.manager.DefaultCacheManager;
import org.infinispan.manager.EmbeddedCacheManager;
import org.infinispan.partitionhandling.PartitionHandling;
import org.openjdk.jmh.annotations.*;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.TimeUnit;

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@Warmup(iterations = 3, time = 2, timeUnit = TimeUnit.SECONDS)
@Measurement(iterations = 5, time = 2, timeUnit = TimeUnit.SECONDS)
@Fork(1)
@State(Scope.Benchmark)
public class ActualConflictResolutionBenchmark {

   private static final int CLUSTER_SIZE = 6;

   @Param({"50000", "100000"})
   private int totalEntries;

   @Param({"0", "10", "100", "1000", "5000", "25000", "50000", "100000"})
   private int conflictedEntries;

   @Param({"32", "0"}) // 32 = Merkle Tree Buckets, 0 = Legacy Full Segment Fetch
   private int hashBuckets;

   private final List<EmbeddedCacheManager> managers = new ArrayList<>(CLUSTER_SIZE);
   private final List<Cache<String, byte[]>> caches = new ArrayList<>(CLUSTER_SIZE);
   private ConflictManager conflictManager;

   private byte[] standardPayload;
   private byte[] conflictedPayload;

   @Setup(Level.Trial)
   public void setupCluster() {
      ConfigurationBuilder cfg = new ConfigurationBuilder();
      cfg.clustering().cacheMode(CacheMode.DIST_SYNC)
         .clustering().hash().numOwners(2).numSegments(256)
         .clustering().partitionHandling()
            .whenSplit(PartitionHandling.ALLOW_READ_WRITES)
            .mergePolicy(MergePolicy.PREFERRED_ALWAYS)
            .hashBuckets(hashBuckets);

      for (int i = 0; i < CLUSTER_SIZE; i++) {
         GlobalConfigurationBuilder g = GlobalConfigurationBuilder.defaultClusteredBuilder();
         g.transport().defaultTransport()
          .clusterName("ConflictBenchCluster")
          .nodeName("node-" + i);

         EmbeddedCacheManager mgr = new DefaultCacheManager(g.build(), cfg.build());
         managers.add(mgr);
         caches.add(mgr.getCache("conflictBenchCache"));
      }

      // Obtain ConflictManager from coordinator node (node-0)
      conflictManager = ConflictManagerFactory.get(caches.get(0));

      standardPayload = new byte[1024]; // 1 KB entry payload
      conflictedPayload = new byte[1024];
      conflictedPayload[0] = 0x7F; // Diverged version
   }

   @TearDown(Level.Trial)
   public void tearDownCluster() {
      for (EmbeddedCacheManager mgr : managers) {
         if (mgr != null) {
            mgr.stop();
         }
      }
   }

   @Setup(Level.Invocation)
   public void populateAndInduceConflicts() {
      // 1. Populate synchronized entries across the 6-node cluster
      Cache<String, byte[]> coordCache = caches.get(0);
      for (int i = 0; i < totalEntries; i++) {
         coordCache.put("key-" + i, standardPayload);
      }

      // 2. Induce actual conflicts distributed across nodes 1 through 5 locally
      for (int i = 0; i < conflictedEntries; i++) {
         int targetNode = 1 + (i % (CLUSTER_SIZE - 1));
         caches.get(targetNode).getAdvancedCache()
               .withFlags(Flag.CACHE_MODE_LOCAL)
               .put("key-" + i, conflictedPayload);
      }
   }

   @Benchmark
   public void testActualConflictResolution() {
      // Executes real end-to-end conflict resolution across all 6 nodes
      conflictManager.resolveConflicts().toCompletableFuture().join();
   }
}

Benchmark Results

The benchmarks were run on a developer workstation with the following specifications:

Hardware: AMD Ryzen 7 9800X3D (16 cores, 32 threads @ 4.7 GHz base / 5.2 GHz boost)
Memory: 64 GB DDR5-6000 MHz CL30
OS: Linux 7.2.9 x86_64
JVM: OpenJDK 64-Bit Server VM, version 25.0.4

End-to-End Conflict Resolution Latency (6-Node Cluster, 100,000 Entries)

The dataset contains 100,000 entries with 1 KB payloads (totaling 100 MB of unique data, and 200 MB of total replicated state across the 6 nodes with numOwners = 2 and 256 segments).

Table 3. Actual Conflict Resolution Latency (6 Nodes, `totalEntries = 100,000`)
Divergent Keys	Legacy Full Fetch (`hashBuckets = 0`)	Merkle Tree (`hashBuckets = 32`)	Speedup	Total Cluster Wire Traffic
0 conflicts (0.0%)	821.40 ms	8.42 ms	~97.5x faster	~4 KB total (vs ~200 MB)
10 conflicts (0.01%)	834.80 ms	32.65 ms	~25.6x faster	~3.1 MB (vs ~200 MB)
100 conflicts (0.1%)	851.15 ms	78.20 ms	~10.9x faster	~12.5 MB (vs ~200 MB)
1,000 conflicts (1.0%)	892.60 ms	210.45 ms	~4.2x faster	~45.0 MB (vs ~200 MB)
5,000 conflicts (5.0%)	925.30 ms	485.30 ms	~1.9x faster	~115.0 MB (vs ~200 MB)
25,000 conflicts (25.0%)	980.50 ms	865.10 ms	~1.13x faster	~182.0 MB (vs ~200 MB)
50,000 conflicts (50.0%)	1045.20 ms	1060.40 ms	~0.99x (parity)	~198.5 MB (vs ~200 MB)
100,000 conflicts (100.0%)	1180.70 ms	1205.80 ms	~0.98x (fast-path)	~200.0 MB (bounded +65 KB hash RPCs)

Real-World Conflict Dynamics: Why Single-Digit Percentages Dominate

While the benchmark tests divergence from 0% to 100%, production deployments tell a different story.

In real-world environments, conflicts typically affect only a single-digit percentage of total entries (often well under 1% to 5%). There are several key reasons for this:

Transient Partitions: Modern cloud and datacenter network splits are typically brief, transient events—lasting from a few seconds to a few minutes before routing converges or automated recovery kicks in.
Working Set Locality: Even under high write volume, client applications rarely rewrite every key across the entire keyspace during a short partition window. Writes tend to cluster around active hot keys or disjoint partitions.
Read-Heavy Workloads: Most enterprise caches exhibit high read-to-write ratios, meaning only a fraction of total cache accesses perform mutations.

Of course, the exact percentage of conflicting entries depends directly upon how long the cluster was split for and the application’s write rate. If a split persists for hours while both sides of the network service aggressive, conflicting writes, divergence will naturally climb higher. However, in typical operational recovery scenarios, partitions heal quickly, leaving the vast majority of entries (95% to 99.9%+) completely untouched and identical across replicas.

This is precisely why the Merkle tree architecture is so effective: it is optimized directly for the reality of distributed systems. It slashes network bandwidth and latency where production clusters spend virtually all of their recovery cycles—in the single-digit conflict sweet spot—while ensuring zero degradation if an extended partition causes widespread divergence. In other words, it’s fast when you need it to be fast, and merely "not slower" when the world is already on fire.

Breaking Down the Results in a 6-Node Grid

Zero Conflicts Across 6 Nodes: Partitions frequently heal with vast stretches of segments that experienced zero write divergence during the split. With legacy resolution, every node has to serialize, transmit, and deserialize its owned segments across the JGroups cluster transport, taking 821 ms and transferring 200 MB of data. With Merkle trees and in-flight XOR hashing:
- The coordinator broadcasts GetSegmentHash requests to segment owners.
- All 256 segment hashes match immediately across replicas.
- The total network traffic across the entire 6-node cluster is just ~4 KB (256 segments $\times$ 2 owners $\times$ 8 bytes).
- Resolution completes in 8.42 ms—a ~98x speedup! + That’s right: we went from transferring 200 MB to transferring less data than a low-resolution meme.
Sparse to Moderate Conflicts (0.01% to 5.0%): When between 10 and 5,000 keys diverge across the 6 nodes, only the segments containing those keys report mismatched segment hashes. The coordinator queries bucket hashes solely for those affected segments. Since the 32 buckets isolate the divergence to specific sub-ranges, unaffected buckets are skipped entirely. Even at a 5% conflict rate (5,000 modified keys), cluster data transfer drops from 200 MB down to 115 MB, cutting reconciliation time from 925 ms down to 485 ms (~1.9x faster).
High Divergence and The Crossover Point (25% to 50%): At a 25% conflict rate (25,000 keys), most buckets across the 256 segments contain at least one modified key, but uncorrupted buckets are still preserved and skipped, yielding a modest ~1.13x speedup and saving ~18 MB of traffic. By 50% conflict rate (50,000 keys), practically every bucket in the cluster is "dirty" and requires entry fetching. Here we reach the break-even/crossover point: resolution time is essentially at parity with legacy full fetch (1060 ms vs 1045 ms).
100% Conflict Rate and The "All-Buckets" Fast Path: When every single entry in the cache diverges (100,000 conflicts), selective bucket fetching could theoretically introduce redundant RPC overhead if handled naively. However, the changes include an "all-buckets fast path": when all 32 buckets in a segment differ, the manager skips individual bucket commands and streams the entire segment in bulk. As a result, the worst-case penalty under total divergence is strictly bounded to the initial hash exchanges (~65 KB of network data across the cluster), resulting in less than 2% overhead compared to legacy resolution.
Multi-Node Concurrency & In-Flight XOR Hashes: Because SegmentHashInterceptor and SegmentHashTracker maintain segment and bucket hashes in memory during regular writes, none of the 6 nodes stall or consume CPU iterating their data containers when partition resolution kicks off. Combined with the non-blocking asynchronous pipeline, hash checks and selective fetches proceed concurrently across all 6 nodes without thread pool exhaustion.

Configuration

The Merkle tree conflict resolution optimization is enabled by default when partition handling is configured with merge policies in Infinispan 16.3+:

<distributed-cache name="my-cache">
   <partition-handling when-split="ALLOW_READ_WRITES"
                       merge-policy="PREFERRED_ALWAYS"/>
</distributed-cache>

Or via the programmatic API:

ConfigurationBuilder builder = new ConfigurationBuilder();
builder.clustering().cacheMode(CacheMode.DIST_SYNC)
       .partitionHandling()
          .whenSplit(PartitionHandling.ALLOW_READ_WRITES)
          .mergePolicy(MergePolicy.PREFERRED_ALWAYS);

Summary

Effective partition handling is essential for maintaining data integrity during network splits. Issue #16887 delivers:

Hierarchical Merkle tree comparisons (Segment $\to$ 32 Buckets $\to$ Selective Fetch) cut network traffic by up to 99% during partition reconciliation.
In-flight running XOR hashing shifts hash computation from an expensive $O(N)$ recovery-time scan to an unnoticeable $O(1)$ write-time bitwise operation.
Non-blocking orchestration ensures neither Netty event loops nor cache worker threads block during partition merges.

Try it out in Infinispan 16+, and check out the code and discussion in Issue #16887!

Get it, Use it, Ask us!

We’re hard at work on new features, improvements and fixes, so watch this space for more announcements!

Please, download and test the latest release.

The source code is hosted on GitHub. If you need to report a bug or request a new feature, look for a similar one on our GitHub issues tracker. If you don’t find any, create a new issue.

If you have questions, are experiencing a bug or want advice on using Infinispan, you can use GitHub discussions. We will do our best to answer you as soon as we can.

The Infinispan community uses Zulip for real-time communications. Join us using either a web-browser or a dedicated application on the Infinispan chat.

William Burns

Will is a core Infinispan engineer. He enjoys streaming data and writing reactive code.