Elixir Cluster Series

  1. Leveraging CRDTs for eventual consistency
  2. Elixir: Resilient distributed systems
  3. Elixir: Running a cluster of nodes
  4. Elixir: Running a cluster of dynamic nodes
  5. Elixir and Mnesia: Running a cluster with state
  6. Elixir and Raft: Running a cluster with state

Erlang’s “location transparency” allows processes to run seamlessly across different instances, machines, or even regions. Out of the box, Erlang is designed to operate smoothly in a distributed environment, where processes are not tied to any specific physical location.

In such an environment, the notion of “current state” is a myth; it’s really just a snapshot of some past point in time. By the time data is received and actions are taken, the system may have already changed—new messages could have been sent, processes might have failed, and data could have been updated. This reflects the reality that “now” varies across different parts of the system, influenced by the time it takes for information to travel—the inevitable network latency. To manage this uncertainty, developers often design systems with eventual consistency in mind, acknowledging that perfect synchronization is neither practical nor necessary in most distributed systems.

Conflict-Free Replicated Data Types (CRDTs)

CRDTs (Conflict-Free Replicated Data Types) are data structures designed to handle the challenges of eventual consistency in distributed systems. They ensure that, despite possible conflicts and divergence, data will eventually converge to a consistent state. To achieve this, CRDTs rely on several key properties:

  1. Associativity
    Allows operations to be grouped differently without affecting the outcome, facilitating flexible processing across nodes.

  2. Commutativity
    Ensures that the order of operations does not impact the final state, guaranteeing consistent results regardless of the operation sequence.

  3. Idempotence
    Operations applied multiple times have the same effect as if applied once, preventing duplicates from altering the intended state.

Last-Write-Wins (LWW)

The Last-Write-Wins Element Set is a conflict resolution strategy used in CRDTs that employs timestamps to determine which operation should prevail when conflicts occur.

defp converge_superhero(data_a, data_b) do
  combined_superheroes =
    Map.merge(data_a.superheroes, data_b.superheroes, fn _id, sh1, sh2 ->
      if sh1.last_updated > sh2.last_updated, do: sh1, else: sh2
    end)

  %{superheroes: combined_superheroes}
end

The converge_superhero function merges superhero data from two sources, each tagged with a last_updated timestamp. When the same superhero appears in both sources, indicating a conflict, the function retains the version with the more recent timestamp, ensuring that the most up-to-date information is always preserved.

LWW-Tombstone Set

The LWW-Tombstone Set effectively manages updates and deletions across distributed systems by incorporating tombstones.

defp converge_superhero(data_a, data_b) do
  combined_superheroes =
    Map.merge(data_a.superheroes, data_b.superheroes, fn _id, sh1, sh2 ->
      if sh1.last_updated > sh2.last_updated, do: sh1, else: sh2
    end)

  combined_tombstones =
    Map.merge(data_a.tombstones, data_b.tombstones, fn _id, d1, d2 ->
      d1 or d2
    end)

  filtered_superheroes =
    Map.filter(combined_superheroes, fn {id, _} ->
      not Map.has_key?(combined_tombstones, id)
    end)

  %{superheroes: filtered_superheroes, tombstones: combined_tombstones}
end

Function Breakdown:

  • Merging Superheroes: The function merges superhero data from two sources, resolving conflicts by selecting the entry with the more recent update based on the last_updated timestamp.
  • Merging Tombstones: It also merges tombstone records, which mark deleted entries. A logical OR operation ensures that if an entry is marked as deleted in any dataset, it is recognized across all.
  • Filtering Deletions: Finally, the function filters out any superheroes identified in the tombstone records, effectively acknowledging deletions.

This method ensures that all updates and deletions are consistently propagated, maintaining accurate and synchronized state information across multiple nodes.

Conclusion

Distributed systems must manage the challenges of data consistency while allowing nodes to run independently, without relying on a central leader. CRDTs ensure eventual consistency without the need for complex coordination or locking mechanisms.