Understanding Leaderless Replication for Distributed Data

Leaderless replication is another fundamental replication approach for distributed systems. It alleviates problems of multi-leader replication while, at the same time, it introduces its own problems. 

Write conflicts in multi-leader replication are tackled in leaderless replication with quorum-based writes and systematic conflict resolution (e.g., version vectors). Cascading failures, synchronization overhead, and operational complexity can be handled in leaderless replication via its decentralized architecture. Removing leaders can simplify cluster management, failure handling,g and recovery mechanisms.

Any replica can handle writes/reads. This way, we do not rely on specific nodes or regions, which means that single points of failure are potentially avoided.

This article is focused on the trade-offs involved in leaderless replication. Two distinct approaches are identified: Direct writes and coordination-based replication. The two approaches are compared based on failure handling and performance characteristics. For example, commercial databases are also highlighted for leaderless replication and summarized in a table.

Direct Writes and Coordination-Based Replication

Direct writes, and coordination-based replication are the most common approaches in leaderless replication. In the first approach, clients write directly to node replicas, while in the second approach, there exist coordinator-mediated writes. It is worth mentioning that, unlike the leader-follower concept, coordinators in leaderless replication do not enforce a particular ordering of writes. Let's have a more detailed look:

Direct Writes

1. Client selects replicas: The client uses consistent hashing or another mechanism to determine which replicas are responsible for the data.
2. Client sends writes: The client directly sends write requests to multiple replicas in parallel.
3. Replica writes data: Each replica writes the data and returns an acknowledgment to the client.
4. Quorum achieved: Once a quorum (e.g., majority of replicas) acknowledges the write, the client considers the operation successful.

Coordination-Based

1. Client sends write to coordinator: The client sends the write request to a designated coordinator node.
2. Coordinator forwards to replicas: The coordinator forwards the write request to multiple replicas.
3. Replica writes data: Each replica writes the data and returns an acknowledgment to the coordinator.
4. Coordinator confirms to client: Once a quorum of replicas acknowledges the write, the coordinator informs the client that the operation is successful.

Trade-Offs Involved

I will focus on three main trade-offs. Performance vs. consistency, network usage, and failure handling. 

• Performance vs. consistency: Direct writes can be faster but may lead to temporary inconsistencies. Coordination-based approaches can provide stronger consistency but with higher latency.
• Network usage: Direct writes require more client-to-node connections but less inter-node communication. Coordination-based approaches have more inter-node traffic but fewer client connections.
• Failure handling: Direct writes are potentially more resilient to node failures since they can succeed with partial acknowledgments. Coordination-based approaches may block if required nodes are unavailable.

Locating Complexity

The choice between direct writes and coordinator-based approaches often leads to a decision about complexity location. Direct writes push complexity to the client side, while coordinator-based approaches centralize it. This has significant implications for application development and system maintenance.

With direct writes, the complexity manifests in several ways on the client side: 

1. Clients Must Handle Retry Logic and Conflict Resolution

When a write fails due to network issues or conflicts with other writes, the client needs sophisticated logic to determine when and how to retry. This often involves exponential back-off strategies and careful handling of different error conditions. The client must also implement conflict resolution strategies, like last-write-wins or custom merge functions. This can be especially complex when dealing with concurrent updates.

2. Clients Need to Understand Consistency Models and Their Implications

They must be aware of whether they're dealing with eventual, causal, or strong consistency. This affects how they structure their writes and what guarantees they can expect. Developers need to carefully consider read-after-write consistency and implement appropriate waiting or verification mechanisms.

3. Clients Are Responsible for Managing Write Ordering and Dependencies

Applications must track causal relationships between different writes. They need to make sure that dependent operations are properly ordered. For example, creating a user profile must happen before adding items to that user's shopping cart. This often requires maintaining vector clocks or other ordering mechanisms on the client side.

4. Clients Must Implement Failover Handling for Node Outages

Clients need logic to detect when a node is down and redirect writes to alternate nodes. This includes maintaining lists of available nodes and their health status. They must also handle partial failures where some writes succeed and others fail, potentially requiring complex reconciliation logic.

What's particularly interesting is how this choice impacts system evolution over time. A direct write system might be simpler to initially deploy. However, as the application grows in complexity, maintaining consistent behavior across an expanding client base can become increasingly challenging. Conversely, while coordinator-based systems require more upfront infrastructure investment, they often prove easier to maintain and extend as the system scales. 

Coordination-based benefits include the following:

1. Simplified Client Libraries and Application Code

Clients can operate at a higher level of abstraction, simply submitting writes without worrying about the underlying complexity. This results in cleaner, more maintainable application code. Error handling becomes more straightforward as many failure scenarios can be handled transparently by the coordinator.

2. Easier Monitoring and Debugging of Write Patterns

With all writes flowing through a central point, it's easier to observe system behavior, detect anomalies, and troubleshoot issues. Logging and metrics collection can be more comprehensive and consistent.

3. Centralized Conflict Resolution Strategies

Complex conflict resolution logic can be implemented once and reused across all writes. It doesn't need to be duplicated in each client.

Along with the benefits, there are also challenges involved with coordination-based leaderless replication. A sample of the challenges include the following:

1. The Coordinator Becomes a Potential Bottleneck

As the write volume increases, the coordinator must handle more concurrent requests. This can lead to increased latency and resource contention. Every write must make an additional network hop through the coordinator. This adds latency to all operations. The coordinator's processing time adds to the overall latency budget of each write. As such, the coordinator's capacity often determines the overall system's maximum throughput.

2. It Introduces an Additional Point of Failure

If the coordinator fails, the entire write path can be affected, even if the underlying storage nodes are healthy. This requires careful design of coordinators, high availability and coordinator-failover mechanisms.

3. Scaling the Coordinator Layer Requires Careful Design

As the system grows, the coordinator layer must be scaled horizontally while maintaining consistency. This often involves partitioning the coordinator layer or implementing hierarchical coordination structures.

Failure Handling

Failure handling is one of the most challenging aspects of both approaches. While direct writes provide better theoretical availability, they can be problematic during failure scenarios. Coordinator-based systems can provide clearer failure semantics but at the cost of potential coordinator bottlenecks.

Direct Writes

For direct writes, when everything is working normally, a client can write data directly to multiple replicas in parallel. This provides good theoretical availability since there's no single point of failure. However, when partial failures occur (some replicas accept the write while others don't), we can face difficult questions:

• Should we consider the write successful if only some replicas acknowledged it?
• How do we handle inconsistencies when failed nodes come back online?
• What happens if the client crashes mid-write?
• How do we detect and resolve conflicts when different clients write to different subsets of replicas?

The system needs sophisticated conflict resolution and recovery mechanisms to handle these scenarios. Each edge case requires careful consideration and can lead to complex failure modes that are hard to predict and test.

Coordination-Based

A coordinator-based leaderless replication system provides clearer semantics because:

• There's a single source of truth for write-ordering
• The coordinator can enforce invariants and consistency rules
• Failed writes have clear outcomes - either the coordinator accepted the write, or it didn't
• Recovery procedures are more straightforward since the coordinator knows the global state

Unfortunately, this clarity comes at a cost. The coordinator can become a performance bottleneck since all writes must go through it. It may become a single point of failure - if it goes down, no writes can proceed. It may also become an availability bottleneck - high latency to the coordinator affects all writes.

When the coordinator fails, the system typically needs to elect a new one, which may cause temporary unavailability. But once the new coordinator is established, the system's behavior is well-defined again. It all boils down to the following trade-off between direct writes and coordinator-based approaches:

• Direct writes: Better theoretical availability but more complex failure modes and recovery modes
• Coordinator-based: Clearer failure handling but potential bottlenecks and brief periods of unavailability during coordinator failures

This is why many practical systems (like databases and distributed caches) opt for coordinator-based approaches. This is true despite the theoretical availability advantages of direct writes. The clarity in failure handling often outweighs the potential bottleneck concerns. 

We also need to keep in mind that coordinator bottlenecks can be addressed through techniques like partitioning and hierarchical coordination. The choice between these approaches often depends on specific requirements around consistency, availability, and failure tolerance. Systems that absolutely cannot afford any write bottlenecks might choose direct writes. On the other hand, systems prioritizing clear semantics and easier operations might prefer coordinator-based approaches.

Salient Performance Characteristics

Performance characteristics can be counter-intuitive. While direct writes might seem faster due to fewer hops, the additional complexity of client-side conflict resolution and retry logic can sometimes lead to higher overall latency variance.

The Intuitive Expectation

When writing data directly (for example, a client writing straight to a database or storage system), you might expect better performance because the data takes a shorter path. After all, if data goes directly from point A to B without intermediate stops, it should arrive faster than if it had to go through points C and D along the way.

The Counter-Intuitive Reality

However, in distributed systems, this direct path often comes with hidden complexity that can actually degrade performance in unexpected ways. I will focus on client-side conflict resolution, retry logic, and latency variance.

Client-Side Conflict Resolution

When multiple clients write directly to storage, they need to handle situations where their changes conflict with each other. For example:

• Client 1 reads a value as "X"
• Client 2 reads the same value as "X"
• Client 1 changes it to "Y"
• Client 2 tries to change it to "Z"

Now, the client needs to detect this conflict and implement logic to resolve it. This might involve reading the latest version again, applying business rules to merge changes, comparing timestamps, or retrying the entire operation. 

Retry Logic

Direct writes require clients to handle various failure scenarios like network timeouts, partial failures where the write may or may not have succeeded, system overload conditions, or temporary service unavailability. Each retry attempt adds an unpredictable delay. The client needs sophisticated logic to handle edge cases like "at-least-once" vs. "exactly-once" delivery semantics.

Latency Variance

The combination of conflict resolution and retries leads to higher latency variance. While some operations might be completed very quickly, others could take much longer. This may happen due to multiple round trips to resolve conflicts or due to exponential backoff during retries. Other reasons can be queue buildup during retry storms or resource contention during conflict resolution. In contrast, a system with intermediate coordination (like using a message queue or orchestration service) might have slightly higher average latency but more predictable performance because:

• Conflict resolution can have a consistent view of the system
• Retry logic is centralized and can be optimized globally
• Back-pressure mechanisms can prevent overload
• The system can make intelligent routing and scheduling decisions

This is why many high-scale systems opt for apparently "slower" architectures that provide better consistency guarantees and more predictable performance characteristics. The small additional latency from extra network hops is often worth the benefit of reduced complexity and variance in the overall system.

Commercial Databases

Some databases are designed to support both direct and coordination-based writes, offering flexibility in deployment and consistency models. Others adhere strictly to a single replication strategy to optimize for specific use cases. 

In the table that follows, I summarized a sample of commercial database systems that can be used for leaderless replication. Keep in mind that commercial databases change and evolve as distributed systems evolve. Consequently, their data replication features are also evolving to improve existing capabilities as well as to accommodate new needs and trends.

Wrapping Up

Alternatives to the leader-follower concept in data replication are not new in distributed systems. In fact, leaderless models have existed since the 1970s, and they can be useful in a range of cases. In distributed databases and storage systems, for example, they can can provide high availability, fault tolerance, and scalability. In distributed caching systems they can maintain cache consistency across multiple nodes. Systems that require real-time data and cannot afford the latency introduced by leader election can also benefit from leaderless replication. This flexibility is essential for industries such as e-commerce, finance, and IoT.

This article analyzed the direct writes and the coordinator-mediated leaderless replication approaches. They align with the demands of modern cloud-native architectures. A fundamental ingredient for the seamless operation across geographically dispersed data centers in today's increasingly distributed world.