CAP Theorem: Fundamental Trade-offs in Distributed Systems

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

class CPSystemDesignPatterns:
    """
    Common patterns used by CP systems to achieve strong consistency
    while maintaining reasonable availability when possible.
    """
    
    def consensus_based_replication(self):
        """
        Pattern: Use a consensus protocol (Raft, Paxos) for all writes.
        
        Systems: etcd, ZooKeeper, CockroachDB
        
        How it works:
        1. Client sends write to any node
        2. Node forwards to leader (or is leader)
        3. Leader proposes write to followers
        4. Majority must acknowledge (quorum)
        5. Leader commits and responds to client
        
        Partition behavior:
        - Partition with majority continues operating
        - Partition with minority refuses writes
        - Reads can also require quorum (linearizable) or not (stale possible)
        """
        pass
    
    def primary_with_synchronous_replication(self):
        """
        Pattern: Single primary handles all writes, synchronously replicates.
        
        Systems: PostgreSQL (sync replication), MySQL (semi-sync)
        
        How it works:
        1. All writes go to primary
        2. Primary writes locally AND waits for replica ack
        3. Only then acknowledges to client
        4. If replica unreachable, write blocks or fails
        
        Partition behavior:
        - If primary loses connection to replicas, writes block
        - Can be configured to timeout or continue (trading consistency)
        - Failover requires careful handling to avoid split-brain
        """
        pass
    
    def two_phase_commit(self):
        """
        Pattern: Coordinate distributed transactions across nodes.
        
        Systems: Spanner, CockroachDB (internal), traditional XA
        
        How it works:
        1. Coordinator sends "prepare" to all participants
        2. Participants vote yes/no
        3. If all yes, coordinator sends "commit"
        4. If any no, coordinator sends "abort"
        
        Partition behavior:
        - If coordinator or any participant unreachable during prepare: abort
        - If coordinator fails after prepare-yes: participants block
        - This is why 2PC has availability concerns
        
        Spanner mitigation:
        - Uses Paxos *groups* as participants, not single nodes
        - A Paxos group can survive minority failures
        - Coordinator is also replicated for durability
        """
        pass
    
    def hybrid_clock_ordering(self):
        """
        Pattern: Use hybrid logical clocks for transaction ordering.
        
        Systems: CockroachDB, YugabyteDB
        
        How it works:
        - Each node maintains a Hybrid Logical Clock (HLC)
        - HLC combines physical time with logical counter
        - Provides ordering even when physical clocks drift
        - Transactions stamped with HLC values
        
        Partition behavior:
        - Partitioned nodes' clocks may drift
        - When partition heals, clocks resynchronize
        - Transactions from partition period are correctly ordered retroactively
        
        Trade-off:
        - Works without GPS/atomic clocks (unlike Spanner)
        - But may require occasional clock-wait for consistency
        """
        pass
 
 
# Example: Evaluating a CP system for an application
#
# Scenario: Building a banking application
#
# Requirements:
# - Account balances must be accurate
# - Transfers must be atomic (no double-spending)
# - Customers would rather see "temporarily unavailable" than wrong balance
#
# Evaluation of CP systems:
#
# | System         | Pros                           | Cons                        |
# |----------------|--------------------------------|-----------------------------|
# | Spanner        | Gold standard for consistency  | Requires GCP, expensive     |
# | CockroachDB    | Open source, PostgreSQL compat | Less mature than Spanner    |
# | PostgreSQL     | Proven, extensive ecosystem    | Scaling requires sharding   |
# | FoundationDB   | Apple-proven at scale          | Requires custom layers      |
#
# Decision: CockroachDB for new systems (modern, scalable, consistent)
#          PostgreSQL for simpler needs (proven, well-understood)
#          Spanner if already on GCP and need global scale

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158

class APSystemDesignPatterns:
    """
    Common patterns used by AP systems to maintain availability
    while providing eventual consistency.
    """
    
    def gossip_based_replication(self):
        """
        Pattern: Nodes gossip state changes to random peers.
        
        Systems: Cassandra, Riak, DynamoDB (internal)
        
        How it works:
        1. Node A receives write
        2. A acknowledges to client immediately (or after local ack)
        3. A gossips update to random nodes periodically
        4. Those nodes gossip to other random nodes
        5. Eventually, all nodes have the update
        
        Partition behavior:
        - Gossip within a partition continues normally
        - Updates queue up for unreachable nodes
        - When partition heals, gossip catches up stragglers
        - Conflicts (concurrent writes) resolved by LWW or vector clocks
        
        Trade-off:
        + Very high availability
        + No coordination bottleneck
        - Eventual consistency only
        - Conflict resolution needed
        """
        pass
    
    def hinted_handoff(self):
        """
        Pattern: Store hints for unreachable nodes to deliver later.
        
        Systems: Cassandra, Riak, DynamoDB
        
        How it works:
        1. Write targets nodes A, B, C (replication factor = 3)
        2. Node C is unreachable
        3. Node A stores "hint" containing the write for C
        4. When C comes back, A delivers the hint
        5. C applies the update
        
        Partition behavior:
        - Writes don't fail just because one replica is down
        - Hints accumulate during partitions
        - After partition heals, hints are replayed
        
        Trade-off:
        + Improves availability (don't fail if minority of replicas down)
        + Data eventually reaches all replicas
        - Hints can accumulate, causing burst when partition heals
        - If hinting node dies, hints are lost
        """
        pass
    
    def anti_entropy_repair(self):
        """
        Pattern: Background process compares and repairs divergent replicas.
        
        Systems: Cassandra, Riak, DynamoDB
        
        How it works:
        1. Periodically, nodes compare data using Merkle trees
        2. Merkle tree: hierarchical hash of data, efficient comparison
        3. If trees differ, exchange and reconcile differing portions
        4. Conflicts resolved by configured strategy (LWW, etc.)
        
        Partition behavior:
        - During partition, replicas can diverge
        - Anti-entropy can't run across partition
        - After healing, anti-entropy detects and repairs divergence
        
        Trade-off:
        + Repairs inconsistencies over time
        + Catches missed updates (failed hints, node recovery)
        - Resource intensive (CPU, network, disk)
        - May not catch all issues quickly
        """
        pass
    
    def read_repair(self):
        """
        Pattern: Repair stale replicas during read operations.
        
        Systems: Cassandra, Riak
        
        How it works:
        1. Read contacts multiple replicas (for QUORUM, majority)
        2. Compare responses - find most recent value
        3. Return most recent to client
        4. Asynchronously update stale replicas with correct value
        
        Partition behavior:
        - Works within a partition
        - After healing, reads trigger repairs across former partitions
        
        Trade-off:
        + Read path naturally repairs inconsistencies
        + Hot keys get repaired more often
        - Cold keys may stay inconsistent longer
        - Adds latency to digested reads
        """
        pass
    
    def conflict_resolution_strategies(self):
        """
        Various strategies for resolving concurrent writes in AP systems.
        """
        
        # Last-Write-Wins (LWW)
        # - Simple: highest timestamp wins
        # - Danger: can lose concurrent writes
        # - Use when: losing updates is acceptable
        
        # Vector Clocks
        # - Track causality, detect true conflicts
        # - Return all conflicting versions ("siblings")
        # - Application must choose winner
        # - Use when: application can merge or user can choose
        
        # CRDTs (Conflict-free Replicated Data Types)
        # - Data structures designed to merge automatically
        # - E.g., G-Counter (only increments, sum to merge)
        # - E.g., OR-Set (observed-remove set, union to merge)
        # - Use when: data type fits CRDT semantics
        
        # Application-Level Resolution
        # - Store all versions, let application logic decide
        # - Most flexible but most complex
        # - Use when: domain-specific merge logic required
        pass
 
 
# Example: Evaluating an AP system for an application
#
# Scenario: Building a social media "likes" counter
#
# Requirements:
# - Must always accept "like" requests
# - Counts don't need to be perfectly accurate
# - Minor discrepancies are acceptable
# - Global scale, low latency required
#
# Evaluation of AP systems:
#
# | System      | Pros                           | Cons                        |
# |-------------|--------------------------------|-----------------------------|
# | Cassandra   | Proven, high write throughput  | LWW can lose counts         |
# | Riak        | Built-in CRDTs for counters    | Smaller community           |
# | DynamoDB    | Managed, auto-scaling          | Vendor lock-in              |
# | Redis-Cluster | Ultra-low latency            | Complex cluster management  |
#
# Decision: Cassandra with counter columns (using CRDT-like behavior internally)
#          OR DynamoDB if already on AWS and want ease of management

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149

# MongoDB: Using write and read concerns for different operations
 
from pymongo import MongoClient, WriteConcern, ReadPreference
from pymongo.read_concern import ReadConcern
 
client = MongoClient('mongodb://cluster/')
db = client['myapp']
 
# ==========================================
# STRONG CONSISTENCY: Financial operations
# ==========================================
 
def transfer_money(from_account: str, to_account: str, amount: float):
    """
    Money transfer: Use majority write concern and linearizable read.
    
    This ensures the write is durable on majority of nodes,
    and any subsequent read reflects this write.
    """
    accounts = db.get_collection(
        'accounts',
        write_concern=WriteConcern(w='majority', j=True),
        read_concern=ReadConcern('linearizable')
    )
    
    with client.start_session() as session:
        with session.start_transaction():
            # Debit from source
            accounts.update_one(
                {'_id': from_account},
                {'$inc': {'balance': -amount}},
                session=session
            )
            # Credit to destination
            accounts.update_one(
                {'_id': to_account},
                {'$inc': {'balance': amount}},
                session=session
            )
    # Transaction commits with majority write concern
 
 
# ==========================================
# SESSION CONSISTENCY: User profile updates
# ==========================================
 
def update_profile(user_id: str, updates: dict, session_token: str):
    """
    Profile update: User should see their own changes immediately.
    
    Use session consistency - same session always reads its writes.
    """
    profiles = db.get_collection(
        'profiles',
        write_concern=WriteConcern(w='majority'),  # Durable
        read_concern=ReadConcern('majority')       # Read committed data
    )
    
    # Get or create a client session for this user's browser session
    with client.start_session(causal_consistency=True) as session:
        # Update profile
        profiles.update_one(
            {'_id': user_id},
            {'$set': updates},
            session=session
        )
        
        # Read back will see the update (causal consistency)
        return profiles.find_one({'_id': user_id}, session=session)
 
 
# ==========================================
# EVENTUAL CONSISTENCY: Analytics events
# ==========================================
 
def log_event(event_type: str, data: dict):
    """
    Analytics: Fire-and-forget, eventually consistent.
    
    We don't need to wait for replication or even disk sync.
    Maximum throughput, minimal latency.
    """
    events = db.get_collection(
        'events',
        write_concern=WriteConcern(w=0),  # Don't wait at all
        read_concern=ReadConcern('local')  # Read local data
    )
    
    events.insert_one({
        'type': event_type,
        'data': data,
        'timestamp': datetime.utcnow()
    })
    # Returns immediately, write happens asynchronously
 
 
# ==========================================
# HYBRID: Shopping cart
# ==========================================
 
def add_to_cart(user_id: str, product_id: str, quantity: int):
    """
    Shopping cart: Fast writes, eventual reads are fine.
    
    Use low write concern for speed, but read from local for low latency.
    Cart contents aren't critical - user can refresh if needed.
    """
    carts = db.get_collection(
        'carts',
        write_concern=WriteConcern(w=1),  # Just primary
        read_concern=ReadConcern('local')
    )
    
    carts.update_one(
        {'_id': user_id},
        {'$push': {'items': {'product_id': product_id, 'quantity': quantity}}},
        upsert=True
    )
 
 
def checkout(user_id: str):
    """
    Checkout: Now we need strong consistency!
    
    When converting cart to order, switch to majority concern.
    """
    carts = db.get_collection('carts')
    orders = db.get_collection(
        'orders',
        write_concern=WriteConcern(w='majority', j=True),
        read_concern=ReadConcern('majority')
    )
    
    with client.start_session() as session:
        with session.start_transaction():
            cart = carts.find_one({'_id': user_id}, session=session)
            
            # Create durable order
            orders.insert_one({
                'user_id': user_id,
                'items': cart['items'],
                'status': 'placed',
                'created_at': datetime.utcnow()
            }, session=session)
            
            # Clear cart
            carts.delete_one({'_id': user_id}, session=session)
    
    # Transaction committed with majority - order is durable

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

class CRDTExamples:
    """
    Conflict-free Replicated Data Types enable AP systems
    to merge concurrent updates automatically without conflicts.
    """
    
    class GCounter:
        """
        Grow-only Counter: Can only increment.
        Each node maintains its own count; total is sum of all.
        
        Use case: Page view counts, like counts
        """
        def __init__(self, node_id: str):
            self.node_id = node_id
            self.counts = {}  # node_id -> count
        
        def increment(self):
            self.counts[self.node_id] = self.counts.get(self.node_id, 0) + 1
        
        def value(self) -> int:
            return sum(self.counts.values())
        
        def merge(self, other: 'GCounter'):
            """
            Merge with another GCounter by taking max per node.
            This is commutative, associative, and idempotent.
            """
            for node_id, count in other.counts.items():
                self.counts[node_id] = max(
                    self.counts.get(node_id, 0),
                    count
                )
        
        # Example:
        # Node A: {A: 5}           total = 5
        # Node B: {B: 3}           total = 3
        # After merge: {A: 5, B: 3} total = 8
        # Merge order doesn't matter - same result!
    
    class PNCounter:
        """
        Positive-Negative Counter: Can increment and decrement.
        Maintains two G-Counters: one for increments, one for decrements.
        
        Use case: Stock levels, upvotes/downvotes
        """
        def __init__(self, node_id: str):
            self.node_id = node_id
            self.positive = {}
            self.negative = {}
        
        def increment(self):
            self.positive[self.node_id] = self.positive.get(self.node_id, 0) + 1
        
        def decrement(self):
            self.negative[self.node_id] = self.negative.get(self.node_id, 0) + 1
        
        def value(self) -> int:
            return sum(self.positive.values()) - sum(self.negative.values())
        
        def merge(self, other: 'PNCounter'):
            for node_id, count in other.positive.items():
                self.positive[node_id] = max(self.positive.get(node_id, 0), count)
            for node_id, count in other.negative.items():
                self.negative[node_id] = max(self.negative.get(node_id, 0), count)
    
    class ORSet:
        """
        Observed-Remove Set: Supports both add and remove.
        Each add gets unique tag; remove removes specific tags.
        
        Use case: Shopping cart items, group membership
        """
        def __init__(self, node_id: str):
            self.node_id = node_id
            self.elements = {}  # element -> set of (tag, present)
            self.counter = 0
        
        def add(self, element):
            self.counter += 1
            tag = f"{self.node_id}:{self.counter}"
            if element not in self.elements:
                self.elements[element] = set()
            self.elements[element].add((tag, True))
        
        def remove(self, element):
            # Mark all observed tags as removed
            if element in self.elements:
                self.elements[element] = {
                    (tag, False) for tag, _ in self.elements[element]
                }
        
        def lookup(self, element) -> bool:
            if element not in self.elements:
                return False
            # Present if any tag is still "present"
            return any(present for _, present in self.elements[element])
        
        def merge(self, other: 'ORSet'):
            for element, tags in other.elements.items():
                if element not in self.elements:
                    self.elements[element] = set()
                # Complex merge logic: handle concurrent add/remove
                for tag, present in tags:
                    existing = [(t, p) for t, p in self.elements[element] if t == tag]
                    if not existing:
                        self.elements[element].add((tag, present))
                    else:
                        # If either has marked it removed, it's removed
                        old_present = existing[0][1]
                        new_present = present and old_present
                        self.elements[element].discard((tag, True))
                        self.elements[element].discard((tag, False))
                        self.elements[element].add((tag, new_present))
 
 
# Use CRDTs in Riak:
# Riak natively supports CRDTs (called Riak Data Types):
#   - Counters (PN-Counters)
#   - Sets (OR-Sets)
#   - Maps (nested CRDTs)
#   - Flags (boolean)
#   - Registers (LWW)
 
# Example Riak counter:
# curl -XPOST 'http://riak:8098/types/counters/buckets/likes/datatypes/post-123' \
#      -H 'Content-Type: application/json' \
#      -d '{"increment": 1}'
# 
# Multiple nodes can increment concurrently - they'll merge correctly!