

原文链接
https://zhenghe.gitbook.io/open-courses/cmu-15-445-645-database-systems/database-recovery

https://mp.weixin.qq.com/s/tT-vFRTVwieCz3x2uUAQmg

https://mp.weixin.qq.com/s/zw0ASpVDGroZAfUrCban9A

https://mp.weixin.qq.com/s/Kc13g8OHK1h_f7eMlnl4Aw

ARIES

## Index
- Failure Classification
- Buffer Pool Policies
- Shadow Paging
- Write-Ahead Log
- Logging Schemes
- Checkpoints



### Failure Classification
世上并不存在能够容忍任何故障的容错机制，即便做了异地多活，一次小行星撞地球也能将你的系统一举歼灭，因此在讨论故障恢复之前，我们必须先为故障分类，明确需要容忍的故障类型。
一般故障类型可以分为 3 种：
- 事务故障 (Transaction Failures)
- 系统故障 (System Failures)
- 存储介质故障 (Storage Media Failures)
### ransaction Failures
事务故障可以分为两种：
- 
- 逻辑错误 (Logical Errors)：由于一些内部约束，如数据一致性约束，导致事务无法正常完成
- 内部错误 (Internal State Errors)：由于数据库内部调度、并发控制，如死锁，导致事务无法正常提交
### System Failures
系统故障可以分为两种：
- 软件故障 (Software Failure)：如 DBMS 本身的实现问题 (NPE, Divide-by-zero)
- 硬件故障 (Hardware Failure)：DBMS 所在的宿主机发生崩溃，如断电。且一般假设非易失性的存储数据在宿主机崩溃后不会丢失
### Storage Media Failures
如果存储介质发生故障，通常这样的故障就是无法修复的，如发生撞击导致磁盘部分或全部受损。所有数据库都无法从这种故障中恢复，这时候数据库只能从归档的备份记录中恢复数据。
### Buffer Pool Policies
修改数据时，DBMS 需要先把对应的数据页从持久化存储中读到内存中，然后在内存中根据写请求修改数据，最后将修改后的数据写回到持久化存储。在

整个过程中，DBMS 需要保证两点：
DBMS 告知用户事务已经提交成功前，相应的数据必须已经持久化
如果事务中止，任何数据修改都不应该持久化
如果真的遇上事务故障或者系统故障，DBMS 有两种基本思路来恢复数据一致性，向用户提供上述两方面保证：
- Undo：将中止或未完成的事务中已经执行的操作回退
- Redo：将提交的事务执行的操作重做


DBMS 如何支持 undo/redo 取决于它如何管理 buffer pool。我们可以从两个角度来分析 buffer pool 的管理策略：Steal Policy 和 Force Policy。


原文链接

https://www.jianshu.com/p/646961b93c7e

https://zhuanlan.zhihu.com/p/35841956

https://help.aliyun.com/zh/polardb/polardb-for-mysql/innodb-physiological-logging

Logging Schemes

[H指数](https://leetcode.cn/classic/problems/h-index-ii/description/)



![image.png](/static/img/72ae690342075f503982e64db4dd82e9.image.webp)

```cpp
class Solution {
public:
    int hIndex(vector<int>& citations) {
int n = citations.size();

    int left = 0, right = n - 1;

    int hIndex = 0;

    while (left <= right) {

        int mid = left + (right - left) / 2;

        if (citations[mid] >= n - mid) {

            hIndex = n - mid;  // 更新h指数

            right = mid - 1;

        } else {

            left = mid + 1;

        }

    }

    return hIndex;
    }
};
```
[插入位置](https://leetcode.cn/classic/problems/search-insert-position/description/)

![image.png](/static/img/baea14ae49aecfe8f16ad5a7908af019.image.webp)
```cpp
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;

    while (left <= right) {

        int mid = left + (right - left) / 2;

        if (nums[mid] == target) {

            return mid;  // 找到目标值，返回索引

        } else if (nums[mid] < target) {

            left = mid + 1;  // 目标值在右半部分，更新左边界

        } else {

            right = mid - 1;  // 目标值在左半部分，更新右边界

        }

    }

    return left;  // 目标值不存在于数组中，返回它将会被按顺序插入的位置
    }
};
```



[第一个错误的版本](https://leetcode.cn/classic/problems/first-bad-version/description/)

![image.png](/static/img/908e761cad9fd60d37af78cf8ab99f84.image.webp)
```cpp
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
      int left = 1, right = n;

    while (left < right) {

        int mid = left + (right - left) / 2;

        if (isBadVersion(mid)) {

            right = mid;  // 当前版本是错误的，继续在左半部分查找

        } else {

            left = mid + 1;  // 当前版本是正确的，继续在右半部分查找

        }

    }

    return left;  // left和right相等，指向第一个错误的版本  
    }
};
```

[两个数组的交集](https://leetcode.cn/classic/problems/intersection-of-two-arrays/description/)

![image.png](/static/img/414b25b903ddb30bc3e9d63d7263b528.image.webp)
```cpp
class Solution {
public:
    bool binarySearch(const std::vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    
![image.png](/static/img/414b25b903ddb30bc3e9d63d7263b528.image.webp)
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) {
            return true;  // 找到目标元素
        } else if (nums[mid] < target) {
            left = mid + 1;  // 目标元素在右半部分
        } else {
            right = mid - 1;  // 目标元素在左半部分
        }
    }
    
    return false;  // 没有找到目标元素
}

std::vector<int> intersection(std::vector<int>& nums1, std::vector<int>& nums2) {
    std::sort(nums2.begin(), nums2.end());  // 对nums2进行排序
    std::vector<int> result;
    
    for (int num : nums1) {
        if (binarySearch(nums2, num)) {
            result.push_back(num);  // num在nums2中存在，加入结果数组
        }
    }
    
    std::sort(result.begin(), result.end());  // 对结果数组进行排序
    result.erase(std::unique(result.begin(), result.end()), result.end());  // 去除重复元素
    
    return result;
}
};
```

[排列硬币](https://leetcode.cn/classic/problems/arranging-coins/description/)

![image.png](/static/img/0238981045ff0d794a378fb5e71df5cc.image.webp)
```cpp
class Solution {
public:
    int arrangeCoins(int n) {
    long left = 1;
    // long rught = n ;
    long right = static_cast<long>(sqrt(2 * static_cast<long long>(n))) + 1;// 适当缩小范围


  
    while (left <= right) {

        long mid = left + (right - left) / 2;

        long totalCoins = mid * (mid + 1) / 2;

        

        if (totalCoins == n) {

            return mid;  // 正好能排满，返回当前行数

        } else if (totalCoins < n) {

            left = mid + 1;  // 硬币总数小于n，在右半部分继续查找

        } else {

            right = mid - 1;  // 硬币总数大于n，在左半部分继续查找

        }

    }

    

    return right;  // 返回硬币总数小于等于n的最大行数
    }
};
```
[猜数字](https://leetcode.cn/classic/problems/guess-number-higher-or-lower/description/)

![image.png](/static/img/a2a0b38ad1af3afc03dbefe1154354a2.image.webp)
```cpp
class Solution {
public:
    int guessNumber(int n) {
        int left = 1, right = n;

    while (left <= right) {

        int mid = left + (right - left) / 2;

        int result = guess(mid);

        if (result == 0) {

            return mid;

        } else if (result == 1) {

            left = mid + 1;

        } else {

            right = mid - 1;

        }

    }

    return -1; // 如果未找到目标数字，返回 -1 表示异常情况
    }
};
```

[有序数组的单一元素](https://leetcode.cn/classic/problems/single-element-in-a-sorted-array/description/)

![image.png](/static/img/1fde160813da9d5447bcef159cfc5b43.image.webp)

```cpp
#include <vector>

int singleNonDuplicate(std::vector<int>& nums) {
    int left = 0;
    int right = nums.size() - 1;

    while (left < right) {
        int mid = left + (right - left) / 2;

        // 确保 mid 是偶数索引
        if (mid % 2 == 1) {
            mid--;
        }

        // 如果 mid 对应的元素与它的下一个元素相等，说明只出现一次的数在 mid 的右侧
        if (nums[mid] == nums[mid + 1]) {
            left = mid + 2;
        }
        // 否则，只出现一次的数在 mid 的左侧
        else {
            right = mid;
        }
    }

    return nums[left];
}
```

二分查找集合练习

https://mp.weixin.qq.com/s/4z8slS7QkHro083SfQqHuw


https://mp.weixin.qq.com/s/W5V3iIOyc6dGCj1nLkM30A

https://mp.weixin.qq.com/s/XhzmmV_3U3XEGipaTmG0eA

VFS详解

https://mp.weixin.qq.com/s/Ddonv6FdY4oroIT32IGxOw


https://mp.weixin.qq.com/s/0M9EgP1Sn4X4xXh93BTYqg