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

class IdempotentRedoDesign:
    """
    Demonstrates how ARIES log records enable idempotent redo.
    """
    
    # =========================================
    # NON-IDEMPOTENT DESIGN (DON'T DO THIS!)
    # =========================================
    class DeltaBasedLogRecord:
        """
        BAD: Log record stores the change (delta)
        """
        def __init__(self):
            self.lsn = None
            self.page_id = None
            self.operation = "ADD"  # Add to value
            self.delta = 100        # Amount to add
        
        def apply_redo(self, page):
            """
            Applying twice would add 200!
            This is NOT safe for recovery.
            """
            current_value = page.read_value()
            new_value = current_value + self.delta  # DANGER!
            page.write_value(new_value)
    
    # =========================================
    # IDEMPOTENT DESIGN (ARIES APPROACH)
    # =========================================
    class StateBasedLogRecord:
        """
        GOOD: Log record stores the final state
        """
        def __init__(self):
            self.lsn = None
            self.page_id = None
            self.redo_info = {
                'slot': 5,
                'field': 'balance',
                'value': 500  # The final value, not the delta!
            }
            # For undo, we also store the before-image
            self.undo_info = {
                'slot': 5,
                'field': 'balance',
                'value': 400  # What it was before
            }
        
        def apply_redo(self, page):
            """
            Applying any number of times sets value to 500.
            SAFE - this is idempotent!
            """
            page.write_value(
                self.redo_info['slot'],
                self.redo_info['field'],
                self.redo_info['value']  # Set directly, not add
            )
 
def demonstrate_idempotence():
    """
    Show the difference between idempotent and non-idempotent redo.
    """
    print("Original value: 400")
    print("User operation: Add 100 to balance")
    print("")
    print("=" * 50)
    print("NON-IDEMPOTENT LOG DESIGN")
    print("=" * 50)
    
    # Simulate delta-based redo
    value = 400
    delta_record = {"delta": 100}
    
    print(f"After 1st redo application: {value + delta_record['delta']}")
    value += delta_record['delta']
    
    print(f"After 2nd redo application: {value + delta_record['delta']}")
    value += delta_record['delta']
    
    print(f"After 3rd redo application: {value + delta_record['delta']}")
    print("WRONG! Value should be 500, not 700!")
    
    print("")
    print("=" * 50)
    print("IDEMPOTENT LOG DESIGN (ARIES)")
    print("=" * 50)
    
    # Simulate state-based redo
    value = 400
    state_record = {"new_value": 500}
    
    for i in range(1, 4):
        value = state_record['new_value']  # Set directly
        print(f"After redo application #{i}: {value}")
    
    print("CORRECT! Value is 500 regardless of repetitions!")
 
demonstrate_idempotence()

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

class PhysiologicalLogging:
    """
    Physiological logging: physical page + logical operation
    
    This combines the best of both worlds:
    - Physical: identifies exactly which page to modify
    - Logical: describes what to do within the page
    
    For idempotence, the logical operation must be designed carefully.
    """
    
    # Example: Row insertion
    def log_insert_row(self, txn_id, page_id, row_data):
        """
        Log an insertion physiologically.
        """
        return {
            'type': 'INSERT',
            'txn_id': txn_id,
            
            # PHYSICAL: exact page
            'page_id': page_id,
            
            # LOGICAL: operation within page
            'redo_info': {
                'operation': 'INSERT_ROW',
                'row_id': row_data['id'],  # Unique identifier
                'data': row_data,
            },
            'undo_info': {
                'operation': 'DELETE_ROW',
                'row_id': row_data['id'],
            }
        }
    
    def apply_insert_redo(self, page, log_record):
        """
        How to make insertion idempotent?
        
        Option 1: Check if row already exists
        Option 2: Use upsert semantics
        Option 3: Rely on LSN guard (ARIES approach)
        """
        redo_info = log_record['redo_info']
        
        # The LSN guard prevents re-execution
        # But even if we reach here twice (corrupted LSN?),
        # we need the operation itself to be safe
        
        # Idempotent approach: "ensure this row exists with these values"
        if page.row_exists(redo_info['row_id']):
            # Update to match expected state (handles partial application)
            page.update_row(redo_info['row_id'], redo_info['data'])
        else:
            page.insert_row(redo_info['row_id'], redo_info['data'])
        
        page.set_page_lsn(log_record['lsn'])
    
    # Example: B-tree operations
    def log_btree_split(self, page_id, new_page_id, separator_key, 
                        migrated_keys):
        """
        B-tree split is a complex multi-page operation.
        Each component must be designed for idempotent redo.
        """
        return [
            # Sub-operation 1: Initialize new page
            {
                'type': 'NESTED_TOP_ACTION',  # Allocation doesn't undo
                'page_id': new_page_id,
                'redo_info': {
                    'operation': 'INITIALIZE_BTREE_LEAF',
                    'keys': migrated_keys,
                    'next_page': None,  # Will be set
                }
            },
            # Sub-operation 2: Update original page
            {
                'type': 'UPDATE',
                'page_id': page_id,
                'redo_info': {
                    'operation': 'SET_KEYS',  # SET, not REMOVE
                    'remaining_keys': [k for k in original_keys 
                                       if k < separator_key],
                    'next_page': new_page_id,
                },
                'undo_info': {
                    'operation': 'SET_KEYS',
                    'remaining_keys': original_keys,
                    'next_page': original_next_page,
                }
            },
        ]
        
        # Note: Each sub-operation is state-based (SET_KEYS, not DELETE_KEYS)
        # This makes each individually idempotent

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

class LSNGuardedRedo:
    """
    The LSN guard provides absolute idempotence protection.
    
    Guarantee: An operation is applied to a page at most once,
    because once applied, page_lsn >= record.lsn.
    """
    
    def apply_redo_with_guard(self, page, log_record):
        """
        The complete redo application with LSN guard.
        """
        record_lsn = log_record.lsn
        page_lsn = page.get_page_lsn()
        
        # THE CRITICAL GUARD
        if page_lsn >= record_lsn:
            # This operation is ALREADY reflected in the page
            # Do NOT apply again, regardless of operation type
            return False, "Skipped: already applied"
        
        # Safe to apply - this is the first (and only) time
        self._apply_operation(page, log_record.redo_info)
        
        # CRITICAL: Update page LSN BEFORE marking dirty
        # This prevents re-application if we crash between
        # these two operations
        page.set_page_lsn(record_lsn)
        
        # Now mark dirty for eventual flush
        page.mark_dirty()
        
        return True, "Applied successfully"
    
    def _apply_operation(self, page, redo_info):
        """Apply the actual modification."""
        # Even if this operation has side effects,
        # the LSN guard ensures single application
        pass
 
def demonstrate_lsn_guard_scenarios():
    """
    Show how LSN guard handles various scenarios.
    """
    
    scenarios = [
        {
            "name": "Normal redo - first time",
            "page_lsn": 100,
            "record_lsn": 150,
            "expected": "Apply",
            "explanation": "100 < 150: operation not on page, must apply"
        },
        {
            "name": "Already applied",
            "page_lsn": 150,
            "record_lsn": 150,
            "expected": "Skip",
            "explanation": "150 >= 150: operation already reflected"
        },
        {
            "name": "Later operation already applied",
            "page_lsn": 200,
            "record_lsn": 150,
            "expected": "Skip",
            "explanation": "200 >= 150: a later operation is on page, so this one is too"
        },
        {
            "name": "Crash during previous redo - op applied",
            "page_lsn": 150,
            "record_lsn": 150,
            "expected": "Skip",
            "explanation": "If page was written with new LSN, skip"
        },
        {
            "name": "Crash during previous redo - op not applied",
            "page_lsn": 100,
            "record_lsn": 150,
            "expected": "Apply",
            "explanation": "If page wasn't updated, safely re-apply"
        },
    ]
    
    print("=" * 60)
    print("LSN GUARD SCENARIOS")
    print("=" * 60)
    
    for s in scenarios:
        guard_result = "Apply" if s['page_lsn'] < s['record_lsn'] else "Skip"
        print(f"\n{s['name']}:")
        print(f"  page_lsn={s['page_lsn']}, record_lsn={s['record_lsn']}")
        print(f"  Decision: {guard_result}")
        print(f"  Reason: {s['explanation']}")
        assert guard_result == s['expected'], "Logic error!"
    
    print("\n" + "=" * 60)
    print("All scenarios handled correctly by LSN guard!")
 
demonstrate_lsn_guard_scenarios()

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

class IdempotencePatterns:
    """
    Common patterns for achieving idempotence in various contexts.
    """
    
    # Pattern 1: Unique Operation ID
    class UniqueOperationID:
        """
        Each operation has a unique ID.
        Check processed IDs before execution.
        """
        def __init__(self):
            self.processed_ids = set()  # In practice: persistent store
        
        def process_payment(self, payment_id, amount, recipient):
            if payment_id in self.processed_ids:
                return "Already processed"
            
            # Execute the payment
            self.execute_transfer(amount, recipient)
            
            # Mark as processed
            self.processed_ids.add(payment_id)
            return "Success"
        
        # Client retries safely:
        # process_payment("pay-123", 100, "Alice")  -> Success
        # process_payment("pay-123", 100, "Alice")  -> Already processed
    
    # Pattern 2: Version Vectors / ETags
    class VersionedUpdate:
        """
        Updates include expected version.
        Rejects if version mismatch (another update happened).
        """
        def __init__(self):
            self.data = {"balance": 1000}
            self.version = 1
        
        def update_balance(self, new_balance, expected_version):
            if self.version != expected_version:
                return "Conflict: version mismatch"
            
            self.data["balance"] = new_balance
            self.version += 1
            return "Success"
        
        # First request: update_balance(1100, 1) -> Success, version=2
        # Retry:         update_balance(1100, 1) -> Conflict!
        # Client must re-read and retry with version=2
    
    # Pattern 3: Conditional Writes (CAS - Compare And Swap)
    class ConditionalUpdate:
        """
        Only update if current value matches expectation.
        """
        def atomic_increment(self, key, delta, expected_current):
            current = self.read(key)
            if current != expected_current:
                return False, "Condition failed"
            
            self.write(key, current + delta)
            return True, "Success"
        
        # To increment X from 100 to 150 safely:
        # atomic_increment("X", 50, 100)  -> Success if X was 100
        # If X is now 150, retry would fail: atomic_increment("X", 50, 100)
    
    # Pattern 4: Tombstones for Deletes
    class TombstoneDelete:
        """
        Instead of removing, mark as deleted.
        Idempotent: marking already-deleted item as deleted is no-op.
        """
        def delete_user(self, user_id):
            user = self.get_user(user_id)
            if user is None or user.deleted:
                return "Already deleted or doesn't exist"
            
            user.deleted = True
            user.deleted_at = now()
            return "Deleted"
        
        # delete_user("alice")  -> Deleted
        # delete_user("alice")  -> Already deleted
 
# Real-world example: Idempotent HTTP APIs
def http_idempotence_example():
    """
    HTTP methods and idempotence.
    """
    print("=" * 50)
    print("HTTP METHOD IDEMPOTENCE")
    print("=" * 50)
    
    methods = [
        ("GET", True, "Reading same resource returns same result"),
        ("PUT", True, "Setting resource to state X is idempotent"),
        ("DELETE", True, "Deleting already-deleted is still 'deleted'"),
        ("POST", False, "Creating new resource may create duplicates"),
        ("PATCH", "Depends", "Depends on patch semantics"),
    ]
    
    for method, idempotent, reason in methods:
        status = "✓" if idempotent == True else "✗" if idempotent == False else "?"
        print(f"{status} {method}: {reason}")
    
    print("\nTo make POST idempotent:")
    print("  - Include idempotency key in request header")
    print("  - Server checks if key was already processed")
    print("  - Stripe, PayPal, etc. use this pattern")
 
http_idempotence_example()

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

class IdempotencePitfalls:
    """
    Examples of operations that can break idempotence and their fixes.
    """
    
    # Pitfall 1: Time-dependent operations
    class TimePitfall:
        """
        BAD: Using current time in the operation
        """
        def set_expiry_bad(self, item_id):
            # Each execution computes a different expiry!
            item = self.get_item(item_id)
            item.expires_at = datetime.now() + timedelta(hours=1)
            self.save(item)
        
        def set_expiry_good(self, item_id, computed_expiry):
            # GOOD: Time is computed ONCE during logging, not redo
            # Log record contains: {'expires_at': '2024-01-15T10:00:00'}
            item = self.get_item(item_id)
            item.expires_at = computed_expiry  # Fixed value from log
            self.save(item)
    
    # Pitfall 2: External effects
    class ExternalEffectPitfall:
        """
        External systems may not have idempotency tracking.
        """
        def process_order_bad(self, order_id):
            order = self.get_order(order_id)
            
            # Redo charges card multiple times!
            self.payment_gateway.charge(order.amount)  # DANGER!
            
            order.status = 'paid'
            self.save(order)
        
        def process_order_good(self, order_id, idempotency_key):
            """
            GOOD: Use idempotency key with payment provider
            """
            order = self.get_order(order_id)
            
            # Payment provider tracks this key, only charges once
            result = self.payment_gateway.charge(
                order.amount,
                idempotency_key=idempotency_key  # From log record
            )
            
            if result.status in ['success', 'already_processed']:
                order.status = 'paid'
                self.save(order)
    
    # Pitfall 3: Sequence numbers
    class SequencePitfall:
        """
        Sequence generators are not idempotent.
        """
        def create_invoice_bad(self, customer_id):
            # Each execution gets a new invoice number!
            invoice_number = self.sequence.next_val()  # DANGER!
            
            self.create_invoice(
                number=invoice_number,
                customer=customer_id
            )
        
        def create_invoice_good(self, customer_id, preassigned_number):
            """
            GOOD: Number assigned ONCE during transaction logging
            """
            # Log record contains: {'invoice_number': 'INV-1234'}
            self.create_invoice(
                number=preassigned_number,  # Fixed from log
                customer=customer_id
            )
 
# ARIES solution for time/random values
def aries_solution_for_nondeterminism():
    """
    ARIES handles non-deterministic values by logging them.
    
    During normal operation:
    1. Generate the value (time, random, sequence)
    2. Include it in the log record
    3. Apply to page
    
    During redo:
    - Use the value FROM THE LOG RECORD
    - Value is determined, not generated anew
    """
    print("ARIES Solution for Non-Determinism:")
    print("-" * 40)
    print("")
    print("Example: INSERT with auto-generated timestamp")
    print("")
    print("During normal execution:")
    print("  1. Generate timestamp: 2024-01-15 10:30:45")
    print("  2. Log: INSERT row(id=5, created_at='2024-01-15 10:30:45')")
    print("  3. Apply to page with that specific timestamp")
    print("")
    print("During redo:")
    print("  1. Read log: created_at='2024-01-15 10:30:45'")
    print("  2. Apply that exact value (not current time)")
    print("")
    print("Result: Same timestamp regardless of when redo runs!")
 
aries_solution_for_nondeterminism()