一、RTT和RTO的概念

TCP作为一个面向连接的、可靠的传输协议，内部实现了一个重传计时器来保证数据能传输到对方。每发送一个数据包，就给这个数据设置一个重传计时器。如果在计时器超时之前收到了针对这个数据包的ack，就取消这个计时器。如果没有收到，则开始发起重传。计时器超时的时间被称为RTO，这个时间的确定取决于RTT。

关于两者详细的解释：

• RTT(Round Trip Time)：一个连接的往返时间，即数据发送时刻到接收到确认的时刻的差值；
• RTO(Retransmission Time Out)：重传超时时间，即从数据发送时刻算起，超过这个时间便执行重传。

关于RTT和RTO值的确定一直以来都是值得讨论的地方，如何让RTO能适应网络变化。

二、RTT的测量

每发送一个分组，TCP都会进行RTT采样，这个采样并不会每一个数据包都采样，同一时刻发送的数据包中，只会针对一个数据包采样，这个采样数据被记为sampleRTT，用它来代表所有的RTT。

采样的方法一般有两种：

1. TCP Timestamp选项：在TCP选项中添加时间戳选项，发送数据包的时候记录下时间，收到数据包的时候计算当前时间和时间戳的差值就能得到RTT。这个方法简单并且准确，但是需要发送段和接收端都支持这个选项。
2. 重传队列中数据包的TCP控制块：每个数据包第一次发送出去后都会放到重传队列中，数据包中的TCP控制块包含着一个变量，tcp_skb_cb->when，记录了该数据包的第一次发送时间。如果没有时间戳选项，那么RTT就等于当前时间和when的差值。

linux内核中，更新rtt的函数为tcp_ack_update_rtt：

三、RTO的计算

3.1 经典方法

为了避免单次RTT波动，计算RTO时新引入了变量SRTT，表示更加平滑的RTT数值，它的计算方法：

SRTT = x(SRTT) + (1 - x)RTT;

x被称为平滑因子，一般建议设置在[0.8, 0.9]，意思是SRTT值百分之八十来自于之前的值，百分之二十来自于当前值。然后计算RTO的方法为：

RTO = min(ubound, max(lbound, y(SRTT)));

y是时延离散因子，推荐值为[1.3, 2.0]，ubound是RTO的上边界，lbound是RTO的下边界。

算法的缺点

在RTT波动较大时，RTO不能明显适应网络变化。

3.2 标准方法

标准方法引入了平均偏差的概念，它类似于统计学里面的方差，但是因为方差的计算过程代价较大，对于快速TCP来说不太适合。假设rtt的值为M，RTO的计算方式为：

srtt = (1 - g)srtt + g(M);
rttval = (1 - h)rttval + h(|M - rttval|);
RTO = srtt + 4(rttval);

其中g设置为1/8，h设置为1/4，对srtt而言，它有1/8取决于当前值，7/8取决于现有值。当RTT变化时，偏差增量越大，RTO的增量也越大。

关于计算RTT和RTO的算法，还有很多种，历史上针对这个的探讨从未停止过。

比较出名的拥塞算法还有谷歌的bbr算法，高版本的linux内核已经合入了bbr算法作为拥塞控制算法。

四、其他

4.1 TCP Timestamps选项

时间戳选项的作用是为了方便计算RTT，每发出一个数据包，就记录下发送时间，收到数据包时就能准确的获知到数据包往返时间了。

通过TCPDUMP抓包很容易就能看到Timestamps选项：

数据结构之B树

一、B树的基本概念

B树是一种多叉树，被广泛应用于数据库索引中。它也是一种特殊的搜索树，和搜索树最大的不同在于它的每个节点都包含了n个关键字和n+1个指向子节点的指针。它的表现形式为：

B树的特点：

1. 假设x.key为当前节点中的关键字，x.child.key是子节点中的关键字，那么它们之间存在以下关系：
   x.child.key <= x.key1 <= x.child2.key <= x.key2 <= x.child3.key <= ... <= x.keyn
2. 每个节点的关键字个数都有上界和下界，上下界用B树的最小度数t ≥ 2来表示。
3. 除了根节点以外，每个节点必须有t - 1个关键字，除了根节点以外，每个节点都有t个孩子。
4. 每个节点最多有2t - 1个关键字，最多有2t个孩子。当一个节点恰好有2t - 1个关键字时，称该节点是满的。
5. t = 2的时候B树最简单，每个内部节点有2、3或者3个孩子，也被称作2-3-4树。
6. t值越大，B的高度就越小。

为什么B树广泛应用于索引中

因为磁盘读取的最小单位是扇区，每个扇区是512字节。操作系统读取磁盘的最小单位是块，一个块包含了若干个扇区（一般一个块是4096字节，包含8个扇区）。如果和红黑树或其他二叉搜索树一样，每个节点只保存一个数据，那么磁盘读取的效率就相当低了。如果需要读取多个数据，就要执行多次磁盘IO操作才能完成任务了，而磁盘IO在系统中属于较为耗时的操作，因此多次IO势必导致效率大大降低。

B树就是为了改进这一问题而衍生出来的，B树的节点一般设置为磁盘的块大小，也就是4K，里面包含了多个数据节点的内容，这样一次IO就能读到多个数据内容。并且由于B树也具有搜索树的性质，因此很快就能定位到数据内容。

二、B树操作

B树的主要操作有两个：分裂和合并。因为B树的每个节点包含关键字的数量为[t - 1, 2t - 1]，当节点的关键字数量超出后，就要对节点进行分裂操作，分裂操作会导致B树高度增加。当节点关键字被删除，数量不满足条件时就要合并两个节点，合并节点会导致B树高度下降。

3.1 增加节点

以一个度为4的B树为例，插入S后，B树节点的关键字数量变成了7，需要进行分裂。

此时对节点的分裂过程为：

1. 新生成节点，将S右边的关键字和子节点移到新节点中。
2. S左边的关键字和子节点保存在当前节点。
3. S节点往上提，放到父节点中的合适位置。
4. 如果S节点上提导致父节点的数量也超出了，还需要继续对父节点进行分裂。

注意：每次上提到父亲节点的关键字都是被分裂节点的中间关键字。

分裂示例

以下是度为3的B树分裂的过程，每个节点最多有5个关键字，最少2个关键字。

初始时的B树：

插入B，这只是一个简单的对叶节点插入的过程，插入后不会影响其他节点，B树的条件也还满足，直接插入就行：

插入Q，因为插入Q后会导致RSTUV节点关键字超出，因此要分裂这个节点。T节点作为中间节点放到父节点中（也可以把S提到父节点，T放在UV节点）：

插入L，它被放到JK节点之后，也是一个简单的叶节点插入。但是因为根节点的关键字满了，所以对根节点分裂，此时将P提出来作为根节点，树的高度加1：

插入F，放在ABCDE节点之后，插入后将导致节点分裂，节点C提到父节点：

2.3 删除节点

在B树中删除节点，将会引发节点的合并。相对于增加节点来说，删除节点的远比增加节点要复杂。

以上面的B树为例，初始状态为：

删除关键字F，作为叶子节点，删除F后并没有影响到B树的性质，直接删除即可。得到以下B树：

删除关键字M，因为M所处的节点是内部节点，删除M后会导致NO关键字所在的节点没有父节点。此时需要把M的前驱关键字L替换掉M，然后删掉L：

也可以把M的后继关键字N替换上来，但是M替换后会导致子节点不满足关键字数量条件。

删除关键字G，G所处的节点也是内部节点，删除后会导致DE或者JK所处的节点没有父节点，此时也需要和上面删除M一样在子节点中找到前驱或者后继替换上来。但是这里不同的是，两个子节点都是只有t - 1个关键字，再从中拿掉一个关键字后会导致子节点关键字数量不满足。此时就需要合并两个子节点，然后直接删除G节点：

删除关键字D，D所处的节点是叶子节点，可以和删除节点F一样，直接删除。但是这里也有一个不同的点是，父节点和父节点的兄弟节点此时都只有t - 1个节点，此时除了删除节点D以外，还要合并父亲节点，此时树的高度减一：

删除关键字B，B所在的节点关键字数量是t - 1，删除B后会导致节点的最小关键字数量不满足条件。因此要从父节点或者兄弟节点借一个关键字。此时就分为两种情况：

1. 如果兄弟节点的关键字个数也是t - 1，那么直接和兄弟节点合并，从父节点提取一个关键字下来（下面删除C时候的场景）。
2. 如果兄弟节点的关键字个数大于t - 1（目前就是这个情况，兄弟节点有3个关键字），此时就从父节点借一个关键字C替换掉B，借掉C后，就相当于删除了一个内置节点的元素，所以父亲节点要从它后继节点中找一个关键字补上，也就是E。最终的结果就是用C覆盖B，再用E覆盖原来C的位置，再删除E。

删除节点C，此时的情况就是上面的第一种情况了，兄弟节点的关键字个数是t - 1，要合并两个节点，得到：

一、磁盘的基本元素

磁盘由多个盘片组成，每个盘片的基本结构为：

各标识含义：

• A是磁道，多个磁盘的同一个磁道重叠起来叫做柱面，它包含了很多个扇区。
• B是几何上的扇区，只做标示，此处无特殊含义。
• C是扇区，扇区是磁盘的最小组成单元，通常是512字节（有的磁盘时4096字节）。
• D是磁盘块（簇），块/簇是操作系统虚拟出来的概念，它由多个扇区组成。

读取磁盘数据时，磁盘上的磁头不断旋转变道，然后读取数据。因此寻道时间越短，I/O操作越快，目前磁盘的平均寻道时间一般在3－15ms，一般都在10ms左右。

关于随机IO和顺序IO

一般在测试磁盘性能的时候，都会额外测试一个功能点就是随机读写的性能。与随机读写相对的是顺序读写，他们的区别在于本次IO和上一次IO地址的差别。如果本次IO给出的初始扇区地址，和上一次IO的结束扇区地址，是不是完全连续的，或者相隔不多，则本次IO算是一个顺序IO。如果相差太大，则算一次随机IO。顺序IO，因为本次初始扇区和上次结束扇区相隔很近，则磁头几乎不用换道或换道时间极短，所以读写速度快；而随机IO中磁头需要很长的换道时间，导致磁头不停换道，读写速度非常慢。

为什么存在磁盘块？（簇）

1. 读取方便：由于扇区的数量比较小，数目众多在寻址时比较困难，所以操作系统就将相邻的扇区组合在一起，形成一个块，再对块进行整体的操作。
2. 分离对底层的依赖：操作系统忽略对底层物理存储结构的设计。通过虚拟出来磁盘块的概念，在系统中认为块是最小的单位。

我们平常所说的4K对齐也就是指的块大小，它表示操作系统读取磁盘时一次读取的数据大小。如果操作系统一次读取4K，但是块大小只有2K，就相当于一次IO要做2次磁盘寻址。而如果磁盘块大小刚好也是4K，那么一次IO就只需一次寻址。相对而言，磁盘寻址效率是很低的，多一次磁盘寻址肯定会更加导致IO效率低，因此对磁盘进行4K对齐也是提高了系统的IO性能。

二、linux系统下的查看扇区和磁盘块

使用fdisk -l可以看到磁盘的扇区大小：

使用tune2fs -l 可以看到读取磁盘的块大小，下面这个磁盘的块大小是4096：

linux内核中的container_of函数

一、container_of的用途

众所周知，linux内核是用C写的，并且内核中是存在许多数据结构的，栈、链表、哈希表以及红黑树等等。但是C语言中一个致命的缺点就是没有泛型，没有泛型的话所有的数据结构就无法通过一套代码来实现。那有没有办法可以使得这些数据结构成为通用的呢？答案肯定是有的，不然如果每个结构体都要实现一套自己的链表，内核将会变得臃肿、复杂且不好维护。要知道C语言虽然没有泛型，但是它有指针，实现内核的大佬们就通过指针来实现了属于C的泛型。

以链表为例，首先定义一个全局通用的链表节点：

struct list_node {
    struct list_node *prev, *next;
}

节点中只包含了prev和next两个成员，不含有任何数据内容。所有的数据内容都要另外再定义结构体，把这个链表节点包含进来，再通过这个链表节点实现链表移动。例如实现一个lru缓存节点的链表：

struct lru_cache {
    int page_addr;
    struct list_node ln;
}

数据节点说的是lru_cache结构类型的节点，链表节点是lru_cache中ln成员节点。

它通过ln元素串起来的数据形式为：

图片看起来很好理解，关键的问题就在于如何通过这个节点来组成链表，以及如何通过这个链表节点找到本身的数据节点呢？这便是container_of发挥作用的时候了。

container_of的作用就是给定结构体类型和数据成员名返回结构体本身的地址，它需要三个参数：

1. 数据节点指针，表示当前某个数据节点中的链表节点地址，即某个lru_cache节点中ln的地址。
2. 当前数据节点的数据类型，即struct lru_cache这个结构体。
3. 链表节点在数据节点中的名字，即ln。

假设ptr是某个节点中ln元素的地址，那么通过container_of(ptr, struct lru_cache, ln)就能得到这个节点的地址了。通过它来完成一次节点遍历的过程可以描述为：

struct list_node *p = head;
struct lru_cache *lru_node;
while (p) {
    lur_node = container_of(ptr, struct lru_cache, ln);
    // 处理节点
    // print(lru_node);
    // ...
    
    p = p->next == head ? NULL : p->next;
}

二、container_of的实现

container_of的宏定义：

#define container_of(ptr, type, member) ({          \  
    const typeof( ((type *)0)->member ) *__mptr = (ptr); \  
    (type *)( (char *)__mptr - offsetof(type,member) );})

宏定义有三个变量，展开后一共有两行语句：

1. const typeof( ((type *)0)->member ) *__mptr = (ptr);
2. (type *)( (char *)__mptr - offsetof(type,member) );}

这两行语句的解析：

先通过传入的type生成一个该类型的指针，(type *)0表示指向NULL的type类型的指针，假设这个指针为p，语句就变成了：

const typeof( p->member ) *__mptr = (ptr);

然后定义一个链表节点类型的指针__mptr指向ptr，因为不知道ptr的数据类型，所以要通过typeof (p->member)得到数据类型。此时__mptr的指向是：

因此，到这里想要得到lru_cache的地址，只要把__mptr的地址减去ln成员在结构体中的偏移就行了。

这也正是第二个语句的作用：先通过offset_of获取到偏移，再通过(char *)强制转换__mptr的数据类型，使得它的步长是1。最后减去偏移就得到数据节点的地址。

一、概述

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。

一、关于Basic Authentication

HTTP本身提供了一种基础的认证方式Basic Authentication，使得访问者在访问时需要输入账号密码认证之后才能访问到页面：

如果没有输入密码访问，服务器将会返回401：

当服务端开启认证后，通过认证的方式有两种：

1. 在访问URL的时候主动代码账号和密码信息，如http://user:password@www.baidu.com，其中user是账户名，password是密码。
2. 在请求头部加上Authorization头部，并将值设置为Basic xxxx，xxxx是账号和密码的base64编码结果。

一般我们使用的是第二种方式：如果网站需要认证，浏览器会自动会弹出登录框，手动输入账号密码后浏览器在头部带上认证信息访问。以下是一个抓包示例：

最下面一行的Authorization是授权信息，最后的bWFxaWFuOnF3ZTEyMw==即是经过base64加密后的账号密码。使用base64命令解码即可得到认证信息：

> printf "bWFxaWFuOnF3ZTEyMw==" | base64 -d
maqian:qwe123

关于认证状态保持

浏览器如何做到保持状态的呢？根据抓包分析发现，认证成功后，浏览器会自动记住当前页面的账号信息。后续的每一个请求，浏览器都自动加上认证头部，无需每次都再输入账号密码，这样就达到了认证状态保持的效果。

二、使用nginx开启basic authentication

nginx默认提供了ngx_http_auth_basic_module模块以支持basic authentication，该指令为：

location / {
    auth_basic "auth test";
    auth_basic_user_file conf/htpasswd;
}

其中auth_basic认证信息的提示语句，他的值可以是一个字符串或者off，如果值是off表示访问无需认证，如果值是一个字符串，表示需要提供认证信息才能访问。并且大部分浏览器会把这个字符串返回到前端，测试发现chrome不会，edge会：

auth_basic_user_file的值是密钥文件的路径，里面保存了所有的账号密码，内容格式为：

# comment
name1:password1
name2:password2:comment
name3:password3

nginx支持以下密码类型：

1. encrypted with the crypt() function; can be generated using the “htpasswd” utility from the Apache HTTP Server distribution or the “openssl passwd” command;
2. hashed with the Apache variant of the MD5-based password algorithm (apr1); can be generated with the same tools;
3. specified by the “{scheme} data” syntax (1.0.3+) as described in RFC 2307; currently implemented schemes include PLAIN (an example one, should not be used), SHA (1.3.13) (plain SHA-1 hashing, should not be used) and SSHA (salted SHA-1 hashing, used by some software packages, notably OpenLDAP and Dovecot).

通常，我们可以使用htpasswd和openssl命令来生成密码，如：

> openssl passwd -crypt qwe123 # qwe123是生成的密码信息
wMEiqshd7n3YQ

指令放置上下文

这个指令可以放置在：

http, server, location, limit_except

三、参考

Module ngx_http_auth_basic_module

进入到数据库，过滤出当前用户的信息：

select uid, name, password from typecho_users where name = 'xxxx';

修改第三列的密码为e10adc3949ba59abbe56e057f20f883e：

update typecho_users set password = 'e10adc3949ba59abbe56e057f20f883e' where name = 'xxxx';

然后使用密码123456登陆，重新修改密码就可以了。

一、问题回顾

问题现象：线上业务，某个进程被卡住了，所有任务都不响应，导致业务中断。

问题原因：程序中调用了system命令，执行了一次pidof命令，然而作者万万没想到这个pidof命令会卡住了，导致整个进程都阻塞了。

排查过程

第一步，确定进程状态，看看进程在干什么：先通过ps命令得到进程的pid，然后执行strace -p ${pid}挂进去。

执行完strace后发现进程一直卡在wait调用上，但是因为程序卡住了，没有更多的信息可以输出了，也不知道程序执行到哪了，所以并不能知道为什么会执行wait卡住。

于是分析执行wait的场景：wait只会出现在创建了子进程、父进程在等待子进程退出的情况下。会不会是某个子进程卡住了导致父进程阻塞呢？这个是很有可能的，但是反复检查代码，没有发现有创建子进程的地方，并且程序就是单进程设计的，没有主动调用wait的场景。所以这一点上被排除了。

那还会是什么原因导致程序卡在wait了？会不会是strace程序分析有问题导致的？当然这种可能性很小，基本可以排除。

然后又想，程序没有主动创建子进程，会不会是通过其他系统函数间接创建了子进程？很多系统函数都会创建子进程出来，典型的是system和popen函数，代码中是不是调用这两个函数？这很有可能！

于是，就在代码中搜索system和popen，还真找到了一处调用system的地方，但是system调用的都是系统命令：

sh -c kill -usr2 `pidof xxx`

看到命令后想到的第一个问题就是：这个会卡住吗？没听说过kill会阻塞，也没听说过pidof会阻塞啊。虽然我不太相信真的是它卡住了，但是我还是不自觉的打开了gdb。。。使用gdb -p ${pid}挂进去，直接输入bt打印出堆栈调用，映入眼帘的刚好就是这个代码所在的system调用。说明，真的就是这个system卡住了。

为了确定到底是kill卡住了还是pidof卡住了，使用ps过滤出来所有执行这个命令的进程：

可以看到，所有执行pid命令的pid是大于kill的，说明是pidof卡住了才导致kill卡住。

再仔细看，系统已经存在多个被卡住的pidof命令了，最早的可以追溯到一个月前。难以相信一个pidof命令会执行一个月。

本想着再查查为什么pidof命令会卡住，但线上业务着急恢复，执行strace和gdb没看出什么信息后就先恢复了业务。后来本地再也无法重现了，也没有找到pidof卡住的真正原因。

解决方案

1. 去掉了system机制，kill命令直接通过signal函数来完成。
2. 进程启动的时候，保存一份pid变量，不再执行pidof命令来获取pid。

二、总结和思考

1. 程序中少使用system或popen调用外部命令。这点是我一直以来都提倡的，排斥使用system是因为调用system要创建子进程，要屏蔽信号，会有各种不确定的因素在里面，不如系统调用简单、安全。我认为一个好的系统，要尽量减少调用外部命令（但我们公司的传统就是喜欢各种脚本、命令调来调去，实在令人头疼）。
2. 尽可能减少重复的复杂的逻辑。这里的体现就是pidof命令，是否有必要每次都通过外部pidof命令来获取pid？现在大部分的程序都是把pid保存到一个pidfile中，需要用的时候从文件中读取，这种方式来设计是不是会好一些？