Conflict-Free Replicated Data Types (CRDTs): Convergence Without Coordination

Summary

☕ Welcome to The Coder Cafe! Today, we will explore CRDTs, why they matter in distributed systems, and how they keep nodes in sync. Get cozy, grab a coffee, and let’s begin!CRDTs, short for Conflict-Free Replicated Data Types, are a family of data structures built for distributed systems. At first sight, CRDTs may look intimidating. Yet at their core, the idea is not that complex. What makes them special is that they allow updates to happen independently on different nodes while still guaranteeing that all replicas eventually converge to the same state.To understand how CRDTs achieve this, we first need to step back. We need to talk about concurrent operations and what coordination means in a distributed system. Let’s take it step by step.What does concurrent operations mean? Our first intuition might be to say they happen at the same time. That’s not quite right. Here’s a counterargument based on a collaborative editing example.While on a plane, Alice connects to a document and makes an offline change to a sentence.An hour later, Bob connects to the same document and edits the very same sentence, but online.Later, when Alice lands, both versions have to sync.The two edits (1. and 2.) were separated by an hour. They didn’t happen at the same time, yet they are concurrent.So what’s a better definition for concurrent operations? Two operations that are not causally related.In the previous example, neither operation was made with knowledge of the other. They are not causally related, which makes them concurrent. Yet, if Bob had first seen Alice’s update and then made his own, his edit would depend on hers. In that case, the two operations wouldn’t be concurrent anymore.We should also understand concurrent ≠ conflict:If Alice fixes a missing letter in a word while Bob removes the whole word, that’s a conflict.If Alice edits one sentence while Bob edits another, that’s not a conflict.Concurrency is about independence in knowledge. Conflict is about whether the effects of...