Question

Which specific data structure is used in Dynamo-style databases to track causality and resolve write conflicts without requiring a central coordinator?

Accepted Answer

The specific data structure used in Dynamo-style databases to track causality and resolve write conflicts without a central coordinator is the vector clock. A vector clock is a list of pairs consisting of a node identifier and a counter, maintained by each node in the distributed system. When a node performs a write operation, it increments its own counter in the vector clock. When a node receives an update from another node, it updates its local vector clock to be the maximum value for each node identifier found in both the current and received clocks. This process allows the system to determine the causal relationship between two data versions. If one vector clock has higher values for all counters than another, the data is considered a successor, meaning one update clearly followed the other. If the counters show conflicting values where one is higher for some nodes and lower for others, the system detects a concurrent write conflict. By tracking these relationships, the database can store both versions and present them to the application or user to resolve the conflict, rather than requiring a central server to decide which write is the correct one.

Home → All Courses → Engineering and Technology Courses → Distributed Systems Engineering → Flashcard

Which specific data structure is used in Dynamo-style databases to track causality and resolve write conflicts without requiring a central coordinator?