Determining Redo Point: Where Recovery Begins

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

LSN AnalysisPhase::calculateRedoLSN() {
    // Component 1: Minimum recLSN from Dirty Page Table
    // This is the LSN of the earliest operation that might not be on disk
    LSN min_rec_lsn = MAX_LSN;
    
    for (const auto& [page_id, entry] : dirty_page_table) {
        if (entry.recovery_lsn < min_rec_lsn) {
            min_rec_lsn = entry.recovery_lsn;
        }
    }
    
    // If DPT is empty, no dirty pages means no redo needed (from DPT perspective)
    if (dirty_page_table.empty()) {
        min_rec_lsn = MAX_LSN;  // Will be replaced if txn table has entries
    }
    
    // Component 2: Minimum firstLSN from Transaction Table (optional but safer)
    // In standard ARIES, DPT contains all relevant pages, but some implementations
    // use this as an additional safety check
    LSN min_txn_lsn = MAX_LSN;
    
    for (const auto& [txn_id, entry] : transaction_table) {
        if (entry.first_lsn < min_txn_lsn) {
            min_txn_lsn = entry.first_lsn;
        }
    }
    
    // RedoLSN is the minimum of both
    LSN redo_lsn;
    
    if (min_rec_lsn == MAX_LSN && min_txn_lsn == MAX_LSN) {
        // No dirty pages and no active transactions
        // This means nothing needs redo - start from end of log
        redo_lsn = log_manager.getLastLSN();
        log_info("RedoLSN: No redo needed (no dirty pages or active txns)");
    } else {
        redo_lsn = min(min_rec_lsn, min_txn_lsn);
        log_info("RedoLSN: %d (min_rec: %d, min_txn: %d)", 
                 redo_lsn, min_rec_lsn, min_txn_lsn);
    }
    
    return redo_lsn;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

Log Timeline (LSN increasing rightward):
═══════════════════════════════════════════════════════════════
        0    1000   2000   3000   4000   5000   6000   7000
        |      |      |      |      |      |      |      |
                
Page 100:          [recLSN=2000]─────────────────────────────────────
                   ↑ First dirty since last flush
                   
Page 200:                         [recLSN=3500]─────────────────────
                                  ↑ First dirty since last flush
                                  
Page 300:                                      [recLSN=4500]────────
                                               ↑ First dirty
 
RedoLSN = min(2000, 3500, 4500) = 2000
 
Everything at LSN < 2000 is GUARANTEED on disk:
- Page 100's recLSN is 2000, so it was flushed including everything up to some point < 2000
- Page 200's recLSN is 3500 > 2000, so it was flushed even more recently  
- Page 300's recLSN is 4500 > 2000, same logic
 
Therefore, Redo safely starts at LSN 2000.

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

/*
 * Scenario: Fuzzy Checkpoint Without Aggressive Flushing
 * 
 * Time 0: Page 100 dirtied at LSN 1000
 * Time 1: Page 200 dirtied at LSN 1500
 * Time 2: Checkpoint at LSN 2000
 *         DPT snapshot: {P100: recLSN=1000, P200: recLSN=1500}
 * Time 3: Page 300 dirtied at LSN 2500
 * Time 4: CRASH at LSN 3000
 * 
 * Analysis Result:
 *   DPT: {P100: recLSN=1000, P200: recLSN=1500, P300: recLSN=2500}
 *   RedoLSN = 1000  (older than checkpoint!)
 * 
 * Redo must process 2000 log records (1000 to 3000)
 */
 
/*
 * Scenario: Checkpoint With Aggressive Flushing
 * 
 * Time 0: Page 100 dirtied at LSN 1000
 * Time 1: Page 200 dirtied at LSN 1500
 * Time 2: Checkpoint at LSN 2000
 *         - Checkpoint also flushes all dirty pages!
 *         - DPT snapshot after flush: {} (empty)
 * Time 3: Page 300 dirtied at LSN 2500
 * Time 4: CRASH at LSN 3000
 * 
 * Analysis Result:
 *   DPT: {P300: recLSN=2500}
 *   RedoLSN = 2500  (after checkpoint!)
 * 
 * Redo must process only 500 log records (2500 to 3000)
 */
 
void RecoveryManager::performAggressiveCheckpoint() {
    // Standard checkpoint steps plus page flushing
    LSN begin_lsn = log_manager.appendLog(BEGIN_CHECKPOINT);
    
    // Snapshot tables first (for consistency)
    auto dpt_snapshot = dirty_page_table.snapshot();
    auto txn_snapshot = transaction_table.snapshot();
    
    // Flush ALL dirty pages to disk
    buffer_manager.flushAllDirtyPages();
    
    // Now DPT can be cleared (pages are clean)
    // But we already took snapshot, so checkpoint contains pre-flush state
    
    log_manager.appendLog(END_CHECKPOINT, dpt_snapshot, txn_snapshot);
    log_manager.flush();
    
    // Update master record
    updateMasterRecord(begin_lsn);
}

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

/*
 * Edge Case: Transaction Table Required
 * 
 * Consider this scenario with physiological logging:
 * 
 * LSN 1000: T1 begins
 * LSN 1100: T1 INSERT into table (affects B-tree pages 10, 11, 12)
 *           - Log record: INSERT key=42 into table
 *           - This is a logical operation, not physical page updates
 *           - DPT might only track the leaf page, not internal pages
 * LSN 1200: Buffer manager evicts page 11 (writes to disk)
 *           - Page 11 removed from DPT
 * LSN 1300: CRASH
 * 
 * DPT at crash might only have:
 *   Page 10: recLSN = 1100
 *   Page 12: recLSN = 1100
 *   (Page 11 was evicted clean)
 * 
 * Transaction Table:
 *   T1: firstLSN = 1000, lastLSN = 1100, state = ACTIVE
 * 
 * If we use only DPT: RedoLSN = 1100
 * If we consider Txn Table: RedoLSN = min(1100, 1000) = 1000
 * 
 * The safer choice is 1000, ensuring we don't miss any operations
 * that might have affected pages we don't know about.
 */
 
LSN AnalysisPhase::calculateRedoLSNSafe() {
    LSN from_dpt = getMinRecLSNFromDPT();
    LSN from_txn = getMinFirstLSNFromTransactionTable();
    
    // Take the minimum for safety
    LSN redo_lsn = min(from_dpt, from_txn);
    
    // Log if there's a significant difference (might indicate a problem)
    if (from_dpt != MAX_LSN && from_txn != MAX_LSN) {
        LSN diff = abs((long)from_dpt - (long)from_txn);
        if (diff > 10000) {  // Threshold for concern
            log_warn("RedoLSN sources differ significantly: DPT=%d, TxnTable=%d",
                    from_dpt, from_txn);
        }
    }
    
    return redo_lsn;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

LSN AnalysisPhase::calculateRedoLSN() {
    if (dirty_page_table.empty() && transaction_table.empty()) {
        // No redo needed - database is consistent
        log_info("Database clean: no redo required");
        return END_OF_LOG;  // Special marker meaning "skip redo"
    }
    
    // ... normal calculation
}
 
bool RedoPhase::shouldRun(LSN redo_lsn) {
    if (redo_lsn == END_OF_LOG) {
        log_info("Redo phase skipped: nothing to redo");
        return false;
    }
    return true;
}

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

void AnalysisPhase::detectProblematicDirtyPages() {
    LSN current_lsn = log_manager.getLastLSN();
    LSN checkpoint_lsn = getLastCheckpointLSN();
    
    for (const auto& [page_id, entry] : dirty_page_table) {
        LSN age = current_lsn - entry.recovery_lsn;
        
        // Flag pages dirty since before the last checkpoint
        if (entry.recovery_lsn < checkpoint_lsn) {
            log_warn("Page %d dirty since before checkpoint! recLSN=%d, ckpt=%d",
                    page_id, entry.recovery_lsn, checkpoint_lsn);
            
            // This might indicate:
            // 1. Long-running transaction holding the page
            // 2. Buffer manager thrashing (pages not being flushed)
            // 3. Checkpoint not flushing aggressively enough
        }
        
        // Flag excessively old dirty pages
        if (age > CONFIG_MAX_DIRTY_PAGE_AGE) {
            log_error("Page %d has been dirty for %d LSN units - investigate!",
                     page_id, age);
        }
    }
}
 
/*
 * Optimization: Proactive Flushing
 * 
 * Some systems periodically flush pages whose recLSN is getting too old,
 * preventing RedoLSN from drifting too far into the past.
 */
void BufferManager::proactiveFlush() {
    LSN threshold = log_manager.getLastLSN() - CONFIG_FLUSH_AGE_THRESHOLD;
    
    for (Page& page : buffer_pool) {
        if (page.isDirty() && page.getRecLSN() < threshold) {
            flushPage(page);
            log_debug("Proactively flushed page %d (old recLSN)", page.id);
        }
    }
}