Hone logo
Hone
Problems

Concurrent Register-Increment Counter (CRDT) Implementation in Go

Conflict-free Replicated Data Types (CRDTs) are essential for building distributed systems where data consistency is crucial without requiring strict coordination. This challenge asks you to implement a Register-Increment Counter (RIC), a simple yet fundamental CRDT, in Go. Successfully implementing this will provide a foundation for understanding more complex CRDTs and their application in distributed environments.

Problem Description

You are tasked with creating a Go implementation of a Register-Increment Counter (RIC) CRDT. An RIC counter allows multiple replicas to independently increment a counter value. The key property of a CRDT is that when replicas are merged, the final counter value will be consistent across all replicas, regardless of the order in which increments and merges occur.

What needs to be achieved:

  • Implement a RICounter struct in Go.
  • Provide methods for:
    • Increment(value int): Increments the counter by the given value. value can be positive or negative.
    • Merge(other *RICounter): Merges the state of this counter with another RICounter. This operation must ensure eventual consistency.
    • Value() int: Returns the current value of the counter.

Key Requirements:

  • The RICounter must be thread-safe. Multiple goroutines should be able to concurrently call Increment without data races.
  • The Merge operation must correctly combine the states of two counters, ensuring that the resulting counter's value reflects all increments from both original counters.
  • The Value method should return the current, accurate counter value.

Expected Behavior:

  • Multiple concurrent Increment calls should correctly update the counter's value.
  • Merging two counters should result in a counter whose value is the sum of the values of the two original counters.
  • Merging a counter with itself should have no effect.
  • The implementation should be reasonably efficient.

Important Edge Cases to Consider:

  • Negative increment values.
  • Concurrent increments and merges.
  • Merging with counters that have significantly different values.
  • Zero increment values.

Examples

Example 1:

Input:
Counter 1: Initial value = 0
Counter 2: Initial value = 0
Counter 1: Increment(5)
Counter 2: Increment(3)
Counter 1: Merge(Counter 2)
Output: Counter 1 Value() = 8
Counter 2 Value() = 8
Explanation: Counter 1 increments to 5, Counter 2 increments to 3.  Merging combines the values, resulting in 8. Counter 2's value is also updated to 8 after the merge.

Example 2:

Input:
Counter 1: Initial value = 10
Counter 2: Initial value = 20
Counter 1: Increment(-5)
Counter 2: Increment(10)
Counter 1: Merge(Counter 2)
Output: Counter 1 Value() = 25
Counter 2 Value() = 25
Explanation: Counter 1 becomes 5, Counter 2 becomes 30. Merging results in 35.

Example 3: (Edge Case - Concurrent Operations)

Input:
Counter 1: Initial value = 0
Counter 2: Initial value = 0
Goroutine 1: Increment(1)
Goroutine 2: Increment(2)
Goroutine 3: Increment(3)
Counter 1: Merge(Counter 2)
Output: Counter 1 Value() = 6
Counter 2 Value() = 6
Explanation:  The increments happen concurrently. The merge operation must correctly combine the values, resulting in 6.  Thread safety is crucial here.

Constraints

  • The Increment method should handle integer values between -10000 and 10000 (inclusive).
  • The Merge method should be efficient; avoid unnecessary copying of data.
  • The implementation must be thread-safe, meaning it should be safe for concurrent access from multiple goroutines without data races. Use appropriate synchronization primitives (e.g., sync.Mutex).
  • The Value() method should return the correct value within 100 microseconds.

Notes

  • Consider using a sync.Mutex to protect the counter's value from concurrent access.
  • The core idea of an RIC is that each increment is associated with a unique identifier (in this simplified case, we're implicitly using the order of operations as identifiers). The merge operation simply adds up all the increments.
  • Focus on correctness and thread safety first. Performance optimizations can be considered later.
  • This is a simplified CRDT. Real-world CRDTs often involve more complex data structures and algorithms to handle more complex data types and operations.
Loading editor...
go