一、概述

binlog/redolog/undolog都是msql中的日志模块，其中二进制日志是mysql服务层实现的，redolog和undolog是引擎层实现的。binlog一般被称为二进制日志（也成为归档日志），redolog成为重做日志，undolog称为回滚日志。

binlog记录的数据库记录的改动日志，如：记录ID = 2这条记录的字段A加1，它主要用户数据的同步和复制。redolog记录的是物理层面的改动日志，如：记录某个扇区的某个字节修改成了1，它主要用于数据重做。undolog和binlog差不多，也是记录的逻辑日志，它主要用于MVCC中记录回滚。

redolog和undolog只存在于innodb中，myisam引擎并没有实现，这两个日志在innodb中统称为事务日志。但要注意的是，虽然undolog和redolog都能恢复数据，但undolog并不是redolog的逆向操作。undolog用于回滚，redolog用于前滚。

关于前滚和回滚：

前滚：事务提交之后，部分数据写入了磁盘，但是还有部分数据存在脏页上，并没有写入磁盘。此时设备宕机，没有写入磁盘的数据丢失。就要依赖redolog来恢复这部分数据。

回滚：事务还未提交，改动并没有完全生效，但是记录已经被修改。此时设备宕机，数据是有问题的，就要依赖undolog回滚改动。

大致的工作模型为：

二、二进制日志（bin log）

二进制日志是server层（即mysql）实现的，不用引擎单独再实现。它记录了所有对数据修改的过程，属于逻辑日志。例如当我们把某个字段增加了1，那么binlog就会记录一条日志，它是直接写入到文件系统的。binlog的主要用途是复制和同步数据，在多台设备间保持数据一致。

binlog只会保存对数据存在更改的记录，像select/show这类查询类的语句是不记录的。

开启二进制日志的方法：

[mysqld]
log-bin=[on|filename]

在my.cnf文件中添加上对应的配置段即可，可以手动指定文件名。重启服务后生效。

当开启二进制日志后，mysql数据目录就会生成对应的数据文件：

也可以在mysql中通过指令得到文件相关信息，如：

SHOW {BINARY | MASTER} LOGS # 查看使用了哪些日志文件
SHOW BINLOG EVENTS [IN 'log_name'] [FROM pos] # 查看日志中进行了哪些操作
SHOW MASTER STATUS # 显示主服务器中的二进制日志信息

三、重做日志（redolog）

redolog是工作在物理层，它的作用主要是为了减少磁盘开销。因为磁盘操作是极为耗时的，因此，不可能每次对数据的更改都直接写入磁盘。redolog的作用就是缓存起来这些数据改动（缓存到磁盘），等缓存到达一定的数量后再统一写磁盘。

redolog是引擎层实现的，MyISAM没有实现这个功能，而InooDB实现了。

一个很生动形象的例子是《孔乙己》，在这篇文章中，有记录到老板赊账的过程：酒店掌柜有一个粉板，专门用来记录客人的赊账记录。如果赊账的人不多，那么他可以把顾客名和账目写在板上。但如果赊账的人多了，粉板记不下了，这个时候掌柜一定还有一个专门记录赊账的账本。如果有人要赊账或者还账的话，掌柜一般有两种做法：

1. 直接把账本翻出来，把这次赊的账加上去或者扣除掉；
2. 另一种做法是先在粉板上记下这次的账，等打烊以后再把账本翻出来核算。

在生意红火柜台很忙时，掌柜一定会选择后者，因为前者操作实在是太麻烦了。首先，你得找到这个人的赊账总额那条记录。你想想，密密麻麻几十页，掌柜要找到那个名字，可能还得带上老花镜慢慢找，找到之后再拿出算盘计算，最后再将结果写回到账本上。

redolog的作用实际上也就是老板赊账一样，为了提高效率，先提前把修改记录到一块地方，等到修改达到一定数量后再写入磁盘，减少磁盘写入次数。

为什么会减少磁盘写入次数呢？

假设redolog记录了一条日志，是说把某个扇区的值更新为3，然后后面又来了一条日志，要修改这个扇区的值为5，那么在这种情况下，只要把5写入到磁盘就行了。

redolog和binlog的对比

1. redolog写入的是对磁盘的更改，binlog写入的是对记录行的修改。
2. redolog是一个环形缓冲区，有大小限制，缓冲区满后把数据写入磁盘。而binlog是直接记录文件，没有文件大小限制， 大小超出后重新生成一个文件继续记录。
3. redolog是引擎层实现，binlog是server层实现。

四、回滚日志（undo log）

回滚日志主要的用途是多版本并发控制中的回滚，多个事务同时更新数据时会生成回滚日志：

图片来源：极客时间《MySQL实战45讲》。

其中U1/U2/U3表示的就是回滚日志，当记录要从V4回滚到V1时，要先依次通过U3和U2回滚到V2，再通过U1回滚到V1。

四、关于二阶段提交

二阶段提交的意思是：redolog和binlog都写入了之后再提交数据，确保日志数据都正常了才写入磁盘。

以下是binlog和redolog的工作流程：

写入redolog后，事务处于prepare状态，然后写入binlog，再commit。

这样做的目的就是避免两个日志中的某一个没有被正确写入出现异常，一旦两个日志行为不一致，后续的同步和恢复数据就不准确。

使用binlog和redolog恢复数据

如何使用binlog和redolog来恢复数据呢，一般是以下几个过程：

1. 找到最近一次的全量备份
2. 从备份的时间点开始执行binlog，重放到需要的时间点。

一、友元

友元可以允许其他类或者函数访问自己的非共有成员，如果类想把它的函数作为友元，只需要增加一条以friend开头的函数声明即可。

1.1 添加外部函数作为友元

以下一个学生类，类中保存了学生的年龄、名字以及性别信息：

class stu_st {
private:
    int age;
    string name;
    char sex;
};

现在希望在类外面以函数的形式来计算两个学生的年龄之和，因为age成员是私有的，所以目前类外部的函数是无法获取到学生年龄，这个想法无法完成。但是有了友元之后，这个想法就能实现了。只要在类中添加友元定义，外部再实现函数就可以了：

class stu_st {
    friend int figure_age(const stu_st &a, const stu_st &b);
    // ...
};

// 实现计算年龄函数
int figure_age(const stu_st &a, const stu_st &b) {
    return a.age + b.age;
}

友元是不区分共有和私有的，以友元修饰的函数即使声明在private域，外部也是能访问的。

1.2 以外部类作为友元

新增一个老师类，老师能获取学生的年龄：

class teacher_st;
class stu_st {
    friend class teacher_st;
    // ...
};

class teacher_st {
public:
    unsigned int get_stu_age(const stu_st &stu) {
        return stu.age;
    }
};

1.3 静态成员变量

当类中存在静态变量时，友元类和函数也是能直接访问这个变量的。

以下代码声明了一个teacher_st作为老师类，声明了一个stu_st作为学生类，学生类中有一个静态变量total_count表示学生的总数，老师作为友元类来获取这个数量：

#include <iostream>

using namespace std;

class teacher_st;
class stu_st {
    friend class teacher_st;
private:
    static unsigned int total_count;
};

class teacher_st {
public:
    unsigned int get_stu_count() {
        return stu_st::total_count;
    }
};

unsigned int stu_st::total_count = 10;

int main() {
    teacher_st t;
    cout << t.get_stu_count() << endl;
    return 0;
}

运行结果：

二、运算符重载

2.1 运算符重载语法

运算符重载给类提供了大大的便利性，使得自定义类型也能和内置类型一样使用系统操作符。

运算符重载的语法：

void operator+(const stu_st &s);

各元素说明：

• void：返回值类型
• operator+：表示重载运算符+
• s：运算符的参数

运算符重载有几种不同的写法，可以写在类中，也可以写在类外面。

在类中声明

以学生类为例，重载小于符号<使得类可以直接通过年龄大小作为对比：

class stu_st {
private:
    unsigned int age;
    string name;
public:
    stu_st(int age, string name) : age(age), name(name) {
    }
    // 重载小于符号
    bool operator<(const stu_st &x) const {
        return this->age < x.age;
    }
};

在类外面声明

因为类外面的函数无法直接访问类内部数据，因此，类外面的函数需要被声明为类的友元函数。

class stu_st {
private:
    unsigned int age;
    string name;
public:
    // 声明重载操作符>
    friend bool operator>(const stu_st &, const stu_st &);
};

bool operator>(const stu_st &a, const stu_st &b) {
    return a.age > b.age;
}

注意

在类内部重载操作符，编译器默认会把this作为第一个参数传入，因此，重载时无需再传入当前类对象本身。例如：

bool operator<(const stu_st &x) const

这就表示用当前对象和x对象作对比。而外部声明的函数，因为没有封装在类中，不能传入this指针，因此声明时需要传入对象本身。即：

friend bool operator>(const stu_st &, const stu_st &);

2.3 重载输入输出运算符

重载输入和输出运算符需要注意的一个问题是：与iostream标准库相关的运算符重载，必须是非成员函数。

#include <iostream>
#include <ostream>
#include <string>

using namespace std;

class stu_st {
private:
    unsigned int age;
    string name;
public:
    stu_st() {};

    friend istream &operator>>(istream &, stu_st &);
    friend ostream &operator<<(ostream &os, const stu_st &stu);
};

// 重载输出运算符
ostream &operator<<(ostream &os, const stu_st &stu) {
    os << "Name: " << stu.name << "\tAge: " << stu.age;
    return os;
}

// 重载输入运算符
istream &operator>>(istream &is, stu_st &stu) {
    is >> stu.name >> stu.age;
    return is;
}

int main() {
    stu_st stu;
    cin >> stu;
    cout << stu;
}

测试效果：

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/add-two-numbers

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储一位数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字0之外，这两个数都不会以0开头。

示例：

• 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
• 输出：7 -> 0 -> 8
• 原因：342 + 465 = 807

二、题解

思路：

我们使用变量来跟踪进位，并从包含最低有效位的表头开始模拟逐位相加的过程。：

算法：

就像你在纸上计算两个数字的和那样，我们首先从最低有效位也就是列表l1和l2的表头开始相加。由于每位数字都应当处[0, 9]的范围内，我们计算两个数字的和时可能会出现 “溢出”。例如，5 + 7 = 12。在这种情况下，我们会将当前位的数值设置为2，并将进位carry = 1带入下一次迭代。进位carry必定是0或1，这是因为两个数字相加（考虑到进位）可能出现的最大和为 9 + 9 + 1 = 19。

伪代码如下：

• 将当前结点初始化为返回列表的哑结点。
• 将进位carry初始化为 00。
• 将p和q分别初始化为列表l1和l2的头部。

• 遍历列表l1和l2直至到达它们的尾端。

  • 将x设为结点p的值。如果p已经到达l1的末尾，则将其值设置为0。
  • 将 y设为结点q的值。如果q已经到达 l2l2 的末尾，则将其值设置为0。
  • 设定sum = x + y + carry。
  • 更新进位的值，carry = sum / 10。
  • 创建一个数值为 (sum % 10) 的新结点，并将其设置为当前结点的下一个结点，然后将当前结点前进到下一个结点。
  • 同时，将 pp 和 qq 前进到下一个结点。
• 检查carry = 1是否成立，如果成立，则向返回列表追加一个含有数字 11 的新结点。
• 返回哑结点的下一个结点。

请注意，我们使用哑结点来简化代码。如果没有哑结点，则必须编写额外的条件语句来初始化表头的值。

特别注意以下情况：

1. 当一个列表比另一个列表长时
2. 当一个列表为空时，即出现空列表
3. 求和运算最后可能出现额外的进位，这一点很容易被遗忘

三、代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *rs, *p, *q, *cur;
        int carry = 0, sum, x, y;

        rs = new ListNode(0);
        cur = rs;

        p = l1;
        q = l2;

        // [1] 注意循环终止的条件是两个链表都不为空了才停止
        while (p || q) {
            // [2] 注意p或者q等于NULL的清情况
            x = p ? p->val : 0;
            y = q ? q->val : 0;

            // [3] 注意加上进位
            sum = x + y + carry;

            cur->next = new ListNode(sum % 10);
            carry = sum / 10;

            // [4] 注意处理p或q节点等于NULL的情况
            p = p ? p->next : NULL;
            q = q ? q->next : NULL;
            cur = cur->next;
        }

        // [5] 注意最后的进位
        if (carry) {
            cur->next = new ListNode(carry);
        }
        
        // [6] 返回rs的下一个节点
        return rs->next;
    }
};

复杂度分析：

• 时间复杂度：O(max(m,n))，假设m和n分别表示l1和 l2的长度，上面的算法最多重复max(m,n)次。
• 空间复杂度：O(max(m,n))， 新列表的长度最多为max(m,n)+1。