背景介绍

Redis在工作中特别常见,在很多业务架构的分享,Redis常常是作为单纯的缓存使用,目的是缓解持久层(比如MySQL)的大流量的访问,最终起到的作用是防止持久层因为海量访问而挂掉。Redis通过将数据保存在内存中,Redis得以拥有极高的读写性能。一旦服务进程退出,Redis的数据就会全部丢失。所以,很多情况下,业务上并不会使用Redis作为数据存储层。
但是,为了解决这个问题,稍微了解些Redis的同学,至少应该听说过Redis的两个持久化方案,分别是RDB、AOF两种持久化方案,这两个方案目标是一样的,就是将内存中的数据保存到磁盘中,避免数据丢失。很多人和我应该类似,听过但从没在实践中使用Redis持久化数据,在我看来,没用过光听过,肯定不是真正的了解,咱至少也得深入了解(暂时用不上的情况下),不能光停留在“听过”。
我会带着这几个问题,去深入了解Redis的持久化机制?
问题一、Redis的持久化机制RDB如何实现?
问题二、Redis的持久化机制AOF如何实现?
问题三、Redis的持久化机制怎么保证数据高可用?
问题四、Redis的持久化机制在哪些业务场景适用?

Redis的持久化机制-RDB

Redis的持久化机制怎么实现,大白话说法,Redis持久化也是把内存数据保存到磁盘上。RDB(Redis Database)是保存内存数据库的快照(SanpShot),而AOF(Append Only File)是保存执行的写操作列表。但这里面的门道是很多的,我们先来了解下RDB的持久化。

Redis数据库状态.png

举个例子,上图展示了一个包含三个非空数据库的Redis服务器,这三个数据库以及数据库中的键值对就是该服务器的数据库状态。RDB持久化就是生成一个RDB文件,当然是经过压缩的二进制文件,通过该文件可以还原生成RDB文件时对应的数据库状态。

RDB文件持久化数据库状态.png

RDB文件是通过SAVE或者BGSAVE命令创建的,代码是rdb.c/rdbSave,有兴趣可以读一下,我这就不展开分析了,SAVE和BGSAVE最终都会调用rdbSave的函数,区别在于调用的方法不同,看名字也能猜出个大概,SAVE是阻塞运行的,而BGSAVE是非阻塞运行的,
SAVE命令调用的方式:

void saveCommand(redisClient *c) {

    // BGSAVE 已经在执行中,不能再执行 SAVE
    // 否则将产生竞争条件
    if (server.rdb_child_pid != -1) {
        addReplyError(c,"Background save already in progress");
        return;
    }

    // 执行 
    if (rdbSave(server.rdb_filename) == REDIS_OK) {
        addReply(c,shared.ok);
    } else {
        addReply(c,shared.err);
    }
}

BGSAVE

int rdbSaveBackground(char *filename) {
    pid_t childpid;
    long long start;

    // 如果 BGSAVE 已经在执行,那么出错
    if (server.rdb_child_pid != -1) return REDIS_ERR;

    ……

    if ((childpid = fork()) == 0) {
        ……
        // 执行保存操作
        retval = rdbSave(filename);
        ……

        // 向父进程发送信号
        exitFromChild((retval == REDIS_OK) ? 0 : 1);

    } else {

        /* Parent */

        // 计算 fork() 执行的时间
        server.stat_fork_time = ustime()-start;

        // 如果 fork() 出错,那么报告错误
        if (childpid == -1) {
            server.lastbgsave_status = REDIS_ERR;
            redisLog(REDIS_WARNING,"Can't save in background: fork: %s",
                strerror(errno));
            return REDIS_ERR;
        }

        ……

        // 记录数据库开始 BGSAVE 的时间
        server.rdb_save_time_start = time(NULL);

        // 记录负责执行 BGSAVE 的子进程 ID
        server.rdb_child_pid = childpid;

        ……

        return REDIS_OK;
    }

    return REDIS_OK; /* unreached */
}

代码很明显能看到,不管是SAVE还是BGSAVE,在执行命令期间(生成RDB文件时),如果再发送SAVE或者BGSAVE都是拒绝的,原因是生成RDB文件时,保存的是全量内存数据,所以极可能产生不小的磁盘I/O和CPU算力。
再来讲讲生成RDB文件的触发方式,有两种,一种是发送SAVE和BGSAVE命令。另外一种是自动间隔性保存,举个例子:
save 1000 1
save 300 20
save 60 20000
那么只要满足以下三个条件中的任意一个,BGSAVE命令就会被执行:
服务器在1000秒之内,对数据库进行了至少1次修改。
服务器在300秒之内,对数据库进行了至少20次修改。
服务器在60秒之内,对数据库进行了至少20000次修改。
那么代码实现上,关键的数据结构是struct saveparam,如下:

struct redisServer {
    ……
    // 记录保存条件的数组
    struct saveparam * saveparams;
    ……
}

那么上面的自动保存间隔参数,在内存中就是这样保存的:
serverparams.png

OK,Redis服务器会有一个定时任务的入口redis.c/serverCron,当中就会遍历以上条件是否满足,满足的话,触犯BGSAVE操作。

// 遍历所有保存条件,看是否需要执行 BGSAVE 命令
 for (j = 0; j < server.saveparamslen; j++) {
    struct saveparam *sp = server.saveparams+j;

    /* Save if we reached the given amount of changes,
     * the given amount of seconds, and if the latest bgsave was
     * successful or if, in case of an error, at least
     * REDIS_BGSAVE_RETRY_DELAY seconds already elapsed. */
    // 检查是否有某个保存条件已经满足了
    if (server.dirty >= sp->changes &&
        server.unixtime-server.lastsave > sp->seconds &&
        (server.unixtime-server.lastbgsave_try >
         REDIS_BGSAVE_RETRY_DELAY ||
         server.lastbgsave_status == REDIS_OK))
    {
        redisLog(REDIS_NOTICE,"%d changes in %d seconds. Saving...",
            sp->changes, (int)sp->seconds);
        // 执行 BGSAVE
        rdbSaveBackground(server.rdb_filename);
        break;
    }
 }

这里面还是不少实现细节的,比如生成RDB文件的子进程如何通知主进程,已经完成了生成文件的操作(通过信号),还有异常情况的处理,主进程收到了Kill信号,这时候也需要调用RDB生成文件,优雅退出程序等等。
关于RDB二进制文件的格式,这里就先略过了,不详细记录在学习笔记上了。

Redis的持久化机制-AOF

再来是AOF持久化机制,AOF( append only file )持久化以独立日志文件的方式记录每条写命令,并在 Redis 启动时回放 AOF 文件中的命令以达到恢复数据的目的。由于AOF会以追加的方式记录每一条redis的写命令,因此随着Redis处理的写命令增多,AOF文件也会变得越来越大,命令回放的时间也会增多,为了解决这个问题,为了解决AOF文件体积膨胀的问题,Redis提供了AOF文件重写(rewrite)功能。通过该功能,Redis服务器可以创建一个新的AOF文件来替代现有的AOF文件,新旧两个AOF文件所保存的数据库状态相同,但新AOF文件不会包含任何浪费空间的冗余命令,所以新AOF文件的体积通常会比旧AOF文件的体积要小得多。在同步到AOF文件前,Redis服务程序会先把命令写入到AOF缓冲区。

AOF机制.png

在介绍“AOF文件重写”之前,先简单说下,AOF这里的触发机制,这个和RDB不同,首先没有命令手动触发的方式,完全是通过服务器的设置,appendonly和appendfsync,appendonly打开情况下,appendfsync有3个可选值,always、everysecond和no。always服务器在每个事件循环都要将aof_buf缓冲区中的所有内容写入到AOF文件,并且同步AOF文件,服务器在每个事件循环都要将aof_buf缓冲区中的所有内容写入到AOF文件,并且同步AOF文件,服务器在每个事件循环都要将aof_buf缓冲区中的所有内容写入到AOF文件,至于何时对AOF文件进行同步,则由操作系统控制。
比较妙的是,虽然Redis将生成新AOF文件替换旧AOF文件的功能命名为“AOF文件重写”,但实际上,AOF文件重写并不需要对现有的AOF文件进行任何读取、分析或者写入操作,这个功能是通过读取服务器当前的数据库状态来实现的。直接上代码不啰嗦:

// 遍历所有数据库
for (j = 0; j < server.dbnum; j++) {

     ……
    /* Iterate this DB writing every entry 
     *
     * 遍历数据库所有键,并通过命令将它们的当前状态(值)记录到新 AOF 文件中
     */
    while((de = dictNext(di)) != NULL) {
        sds keystr;
        robj key, *o;
        long long expiretime;

        // 取出键
        keystr = dictGetKey(de);

        // 取出值
        o = dictGetVal(de);
        initStaticStringObject(key,keystr);

        // 取出过期时间
        expiretime = getExpire(db,&key);

        /* If this key is already expired skip it 
         *
         * 如果键已经过期,那么跳过它,不保存
         */
        if (expiretime != -1 && expiretime < now) continue;

        /* Save the key and associated value 
         *
         * 根据值的类型,选择适当的命令来保存值
         */
        if (o->type == REDIS_STRING) {
            /* Emit a SET command */
            char cmd[]="*3\r\n$3\r\nSET\r\n";
            if (rioWrite(&aof,cmd,sizeof(cmd)-1) == 0) goto werr;
            /* Key and value */
            if (rioWriteBulkObject(&aof,&key) == 0) goto werr;
            if (rioWriteBulkObject(&aof,o) == 0) goto werr;
        } else if (o->type == REDIS_LIST) {
            if (rewriteListObject(&aof,&key,o) == 0) goto werr;
        } else if (o->type == REDIS_SET) {
            if (rewriteSetObject(&aof,&key,o) == 0) goto werr;
        } else if (o->type == REDIS_ZSET) {
            if (rewriteSortedSetObject(&aof,&key,o) == 0) goto werr;
        } else if (o->type == REDIS_HASH) {
            if (rewriteHashObject(&aof,&key,o) == 0) goto werr;
        } else {
            redisPanic("Unknown object type");
        }

        /* Save the expire time 
         *
         * 保存键的过期时间
         */
        if (expiretime != -1) {
            char cmd[]="*3\r\n$9\r\nPEXPIREAT\r\n";

            // 写入 PEXPIREAT expiretime 命令
            if (rioWrite(&aof,cmd,sizeof(cmd)-1) == 0) goto werr;
            if (rioWriteBulkObject(&aof,&key) == 0) goto werr;
            if (rioWriteBulkLongLong(&aof,expiretime) == 0) goto werr;
        }
    }

    // 释放迭代器
    dictReleaseIterator(di);
}

是不是很简单明了,但是AOF这里有一个重写一致性的问题,举例子:

AOF重写数据不一致.png

上图所示,当子进程开始进行文件重写时,数据库中只有k1一个键,但是当子进程完成AOF文件重写之后,服务器进程的数据库中已经新设置了k2、k3、k4三个键,因此,重写后的AOF文件和服务器当前的数据库状态并不一致,新的AOF文件只保存了k1一个键的数据,而服务器数据库现在却有k1、k2、k3、k4四个键。为了解决这种数据不一致问题,Redis服务器设置了一个AOF重写缓冲区,这个缓冲区在服务器创建子进程之后开始使用,当Redis服务器执行完一个写命令之后,它会同时将这个写命令发送给AOF缓冲区和AOF重写缓冲区。如下图所示:

AOF重写解决数据一致性问题.png

最右侧的虚线表示重写完之后,替换AOF文件。更详细的流程,可以参考下图:

详细AOF重写解决数据一致性问题.png

注:AOFRW表示AOF文件重写

Redis的持久化机制怎么保证数据高可用

关于这个问题,在了解上述持久化机制的实现方案后,我的理解是,不管是RDB还是AOF机制,都存在丢失数据的可能性。RDB机制下,数据丢失的概率比AOF机制更大些,而且不管是RDB还是AOF都仅仅是单机上的数据持久化,如果单机的存储磁盘挂了,是没有多备份的,关于这点,Redis也是有解决方案的,Redis的哨兵模式或者Redis集群模式就能提供多机的高可用,所以在实际业务场景中,我认为完全有可能,在清楚地评估业务丢失数据容忍度的情况下,去使用Redis的数据持久化方案。

Redis的持久化机制在哪些业务场景适用

对持久化有要求,又特别适合使用Redis的场景主要有这么两个,特点数据量不大,写入和查询比例差不多。

  • 排行榜相关问题

关系型数据库在排行榜方面写入和查询速度较慢,可能不太适合使用关系型数据库,太重。
比如在线上PK类型的活动中,需要实时展示参与作品的点赞排行榜, 点赞数随着活动进行会不断变化,可能还涉及关联点赞用户的基础信息,那么可以使用到redis中的数据结构,SortedSet和hashmap,来组合使用,满足业务场景。

  • 好友关系、黑白名单等的存储

在微博应用中,每个用户关注的人存在一个集合中,就很容易实现求两个人的共同好友功能,或者黑白名单的存储,都可以使用Redis作为持久存储,写入和查询速度较快,也不会比关系型数据库重,而且可以快速响应需求。

RDB和AOF的优劣对比

RDB和AOF的对比.png

背景

之前有篇文章介绍了TCP建立连接和断开连接时的状态转移流程,没有详细去讲建立完连接之后的传输控制。这篇文章会就几个常见的TCP传输相关的问题做下简单分享,因为TCP/IP协议很复杂,也不可能通过一篇文章完全写清楚。可能更多的内容,还是要查阅专业的相关书籍和网站。好了,废话不多说,今天会涉及这么几个问题的初步探讨:

  1. TCP滑动窗口机制作用是什么?
  2. TCP的重传机制和快速重传机制是什么?有什么区别?
  3. TCP拥塞控制机制是什么?

TCP滑动窗口机制

滑动窗口其实就是用来控制发送速率,因为网络是复杂多变的,有时候就会阻塞住,而有时候又很通畅。不让让网络抖动的时候,去加剧网络质量的下降,从而造成不必要的雪崩。所以发送方需要知道接收方的情况,好控制一下发送的速率,不至于蒙着头一个劲儿的发然后接受方都接受不过来。因此 TCP 就有个叫滑动窗口的东西来做流量控制,也就是接收方告诉发送方我还能接受多少数据,然后发送方就可以根据这个信息来进行数据的发送。
以下是发送方维护的窗口,就是黑色圈起来的。
TCP滑动窗口示意图.png
图中的 #1 是已收到 ACK 的数据,#2 是已经发出去但是还没收到 ACK 的数据,#3 就是在窗口内可以发送但是还没发送的数据。#4 就是还不能发送的数据。
然后此时收到了 36 的 ACK,并且发出了 46-51 的字节,于是窗口向右滑动了。
TCP滑动窗口示意图2.jpg
TCP/IP Guide 上还有一张完整的图,画的十分清晰,大家看一下。
完整TCP滑动窗口示意图.png
那么如果接受方回复的窗口一直是0,那怎么办?
上文已经说了发送方式根据接收方回应的 window 来控制能发多少数据,如果接收方一直回应 0,那发送方就杵着?你想一下,发送方发的数据都得到 ACK 了,但是呢回应的窗口都是 0 ,这发送方此时不敢发了啊,那也不能一直等着啊,这 Window 啥时候不变 0 啊?于是 TCP 有一个 Zero Window Probe 技术,发送方得知窗口是 0 之后,会去探测探测这个接收方到底行不行,也就是发送 ZWP 包给接收方。具体看实现了,可以发送多次,然后还有间隔时间,多次之后都不行可以直接 RST。
假设接收方每次回应窗口都很小怎么办?
你想象一下,如果每次接收方都说我还能收 1 个字节,发送方该不该发?TCP + IP 头部就 40 个字节了,这传输不划算啊,如果傻傻的一直发这就叫 Silly Window。那咋办,一想就是发送端等着,等养肥了再发,要么接收端自己自觉点,数据小于一个阈值就告诉发送端窗口此时是 0 算了,也等养肥了再告诉发送端。发送端等着的方案就是纳格算法,这个算法相信看一下代码就知道了。
伪代码.png
简单的说就是当前能发送的数据和窗口大于等于 MSS 就立即发送,否则再判断一下之前发送的包 ACK 回来没,回来再发,不然就攒数据。
接收端自觉点的方案是 David D Clark’s 方案,如果窗口数据小于某个阈值就告诉发送方窗口 0 别发,等缓过来数据大于等于 MSS 或者接受 buffer 腾出一半空间了再设置正常的 window 值给发送方。
对了提到纳格算法不得不再提一下延迟确认,纳格算法在等待接收方的确认,而开启延迟确认则会延迟发送确认,会等之后的包收到了再一起确认或者等待一段时候真的没了再回复确认。
这就相互等待了,然后延迟就很大了,两个不可同时开启。

TCP的重传机制和快速重传机制

前面我们提到 TCP 要提供可靠的传输,那么网络又是不稳定的如果传输的包对方没收到却又得保证可靠那么就必须重传。
TCP 的可靠性是靠确认号的,比如我发给你1、2、3、4这4个包,你告诉我你现在要 5 那说明前面四个包你都收到了,就是这么回事儿。
不过这里要注意,SeqNum 和 ACK 都是以字节数为单位的,也就是说假设你收到了1、2、4 但是 3 没有收到你不能 ACK 5,如果你回了 5 那么发送方就以为你5之前的都收到了。
所以只能回复确认最大连续收到包,也就是 3。
而发送方不清楚 3、4 这两个包到底是还没到呢还是已经丢了,于是发送方需要等待,这等待的时间就比较讲究了。
如果太心急可能 ACK 已经在路上了,你这重传就是浪费资源了,如果太散漫,那么接收方急死了,这死鬼怎么还不发包来,我等的花儿都谢了。
所以这个等待超时重传的时间很关键,怎么搞?聪明的小伙伴可能一下就想到了,你估摸着正常来回一趟时间是多少不就好了,我就等这么长。
这就来回一趟的时间就叫 RTT,即 Round Trip Time,然后根据这个时间制定超时重传的时间 RTO,即 Retransmission Timeout。
不过这里大概只好了 RTO 要参考下 RTT ,但是具体要怎么算?首先肯定是采样,然后一波加权平均得到 RTO。
RFC793 定义的公式如下:
先采样 RTT 2、SRTT = ( ALPHA SRTT ) + ((1-ALPHA) RTT) 3、RTO = min[UBOUND,max[LBOUND,(BETA*SRTT)]]
ALPHA 是一个平滑因子取值在 0.8~0.9之间,UBOUND 就是超时时间上界-1分钟,LBOUND 是下界-1秒钟,BETA 是一个延迟方差因子,取值在 1.3~2.0。
但是还有个问题,RTT 采样的时间用一开始发送数据的时间到收到 ACK 的时间作为样本值还是重传的时间到 ACK 的时间作为样本值?
采样RTT.png
从图中就可以看到,一个时间算长了,一个时间算短了,这有点难,因为你不知道这个 ACK 到底是回复谁的。
所以怎么办?发生重传的来回我不采样不就好了,我不知道这次 ACK 到底是回复谁的,我就不管他,我就采样正常的来回。
这就是 Karn / Partridge 算法,不采样重传的RTT。
但是不采样重传会有问题,比如某一时刻网络突然就是很差,你要是不管重传,那么还是按照正常的 RTT 来算 RTO, 那么超时的时间就过短了,于是在网络很差的情况下还疯狂重传加重了网络的负载。
因此 Karn 算法就很粗暴的搞了个发生重传我就将现在的 RTO 翻倍,哼!就是这么简单粗暴。
但是这种平均的计算很容易把一个突然间的大波动,平滑掉,所以又搞了个算法,叫 Jacobson / Karels Algorithm。
它把最新的 RTT 和平滑过的 SRTT 做了波计算得到合适的 RTO,公式我就不贴了,反正我不懂,不懂就不哔哔了。
那快速重传机制又是什么,既然有了重传机制,为啥又要这个?超时重传是按时间来驱动的,如果是网络状况真的不好的情况,超时重传没问题,但是如果网络状况好的时候,只是恰巧丢包了,那等这么长时间就没必要。
于是又引入了数据驱动的重传叫快速重传,什么意思呢?就是发送方如果连续三次收到对方相同的确认号,那么马上重传数据。
因为连续收到三次相同 ACK 证明当前网络状况是 ok 的,那么确认是丢包了,于是立马重发,没必要等这么久。
快速重传机制.png
看起来好像挺完美的,但是你有没有想过我发送1、2、3、4这4个包,就 2 对方没收到,1、3、4都收到了,然后不管是超时重传还是快速重传反正对方就回 ACK 2。这时候要重传 2、3、4 呢还是就 2 呢?
所以就引入了SACK,即 Selective Acknowledgment,它的引入就是为了解决发送方不知道该重传哪些数据的问题。我们来看一下下面的图就知道了。
SACK.png
SACK 就是接收方会回传它已经接受到的数据,这样发送方就知道哪一些数据对方已经收到了,所以就可以选择性的发送丢失的数据。
如图,通过 ACK 告知我接下来要 5500 开始的数据,并一直更新 SACK,6000-6500 我收到了,6000-7000的数据我收到了,6000-7500的数据我收到了,发送方很明确的知道,5500-5999 的那一波数据应该是丢了,于是重传。
而且如果数据是多段不连续的, SACK 也可以发送,比如 SACK 0-500,1000-1500,2000-2500。就表明这几段已经收到了。
说完了SACK,不得不提D-SACK,这又是什么东西?D-SACK 其实是 SACK 的扩展,它利用 SACK 的第一段来描述重复接受的不连续的数据序号,如果第一段描述的范围被 ACK 覆盖,说明重复了,比如我都 ACK 到6000了你还给我回 SACK 5000-5500 呢?
说白了就是从第一段的反馈来和已经接受到的 ACK 比一比,参数是 tcp_dsack,Linux 2.4 之后默认开启。
那知道重复了有什么用呢?1、知道重复了说明对方收到刚才那个包了,所以是回来的 ACK 包丢了。2、是不是包乱序的,先发的包后到?3、是不是自己太着急了,RTO 太小了?4、是不是被数据复制了,抢先一步呢?

TCP拥塞控制机制

有滑动窗口了为什么还要拥塞控制,前面已经提到了,加了拥塞控制是因为 TCP 不仅仅就管两端之间的情况,还需要知晓一下整体的网络情形,毕竟只有大家都守规矩了道路才会通畅。前面我们提到了重传,如果不管网络整体的情况,肯定就是对方没给 ACK ,那我就无脑重传。如果此时网络状况很差,所有的连接都这样无脑重传,是不是网络情况就更差了,更加拥堵了?然后越拥堵越重传,一直冲冲冲!然后就 GG 了。
主要有以下几个步骤来搞:1、慢启动,探探路。2、拥塞避免,感觉差不多了减速看看 3、拥塞发生快速重传/恢复。
拥塞控制.png
这块确实还不怎么理解,晚点有机会再补充,

总结

TCP/IP实在是很复杂的一个协议,其中的工程设计凝结了很多大师的智慧,在下不才,这篇文章也只能管中窥豹,略作启发,更多详细内容,还是推荐阅读专业的书籍。

引用内容

http://www.tcpipguide.com/
https://www.ionos.com/digitalguide/server/know-how/introduction-to-tcp/
https://www.ibm.com/developerworks/cn/linux/l-tcp-sack/
https://coolshell.cn/articles/11564.html/
https://tools.ietf.org/html/rfc793https://nmap.org/book/tcpip-ref.html

背景介绍

在《UNIX网络编程》经典书籍中,对TCP连接建立和断开描述了11种TCP状态,书里面有一张经典图片。

TCP的11种状态转移图.png

头一次看(或者过一段时间看)上面这张图,脑袋都会变大,我写这篇文章,就想记录下如何理解这张完整的状态转移图。作用有两个:
一、深入理解TCP的状态转移;
二、针对实际工作种会出现的大量TCP状态(比如TIME_WAIT、CLOSE_WATI),有针对性解决问题的思路。

整体理解

首先,这张图画的是TCP所有的11种状态,以及他们之间转移的条件,可以这样理解,图描述的是一个整体全貌,是所有状态拼在一起的内容,这也就是为啥,我们看着觉得特别复杂。简单来说,我认为在单一的一次TCP传输数据(建立连接->传输数据->断开连接),不会出现所有的11种状态。我总结下来,某一次的TCP连接会有如下几种情况:
一、客户端建立连接,客户端和服务端传输数据,客户端关闭连接;
二、客户端建立连接,客户端和服务端传输数据,服务端关闭连接;
三、客户端建立连接,客户端和服务端传输数据,客户端和服务端同时关闭连接;
也很容易理解,建立连接,只能是客户端主动,只有关闭连接,我们才需要分类讨论。

客户端关闭连接

这个应该是最常规的流程了,从整体图中分离得到的状态转移图如下:

TCP客户端断开连接示意图.png

如果转化位流程图,如下:
TCP客户端断开连接流程图.png

上面这两张图,应该是比较清晰,也不用太多的解释了吧?有时间补充实际操作的代码,结合代码能够看到状态转移,我想理解会更加深刻的。

服务端关闭连接

和上面客户端关闭连接一样,我也整理两张容易理解的图,
服务端关闭连接示意图.png
服务端关闭连接流程图.png

客户端和服务端同时关闭连接

这个情况就相对复杂些,分2种情况讨论下。第一种情况两端同时关闭连接,也同时收到对方发送的FIN包,如下图:

两边同时关闭同时收到FIN包.png

第二种情况两端同时关闭连接,但其中一方先收到FIN包(以客户端先收到FIN包为例,反之亦然),如下图:

双方同时关闭连接一方先收到FIN包.png

异常状态的讨论

实际工作中,会经常遇到服务器出现大量TIME_WAIT或者CLOSE_WATI的状态。
TIME_WAIT根据上面的分析,主动关闭连接方在ACK对端FIN包后处于的状态,也被称为2MSL等待状态。每个具体 TCP 实现必须选择一个报文段最大生存时间 MSL(Maximum Segment Lifetime)。它是任何报文段被丢弃前在网络内的最长时间。这个时间是有限的,因为TCP报文段以IP数据报在网络内传输,而IP数据报则有限制其生存时间的TTL字段。所以TIME_WAIT状态保证了两点:1. 可靠地实现 TCP 全双工连接的终止;2. 允许老的重复分节在网络中消逝。如果服务器上出现大量的TIME_WAIT状态,很可能是有大量的短连接,此时有可能的措施有这么几个,减少MSL的时长、短连接变为长连接。
CLOSE_WAIT状态时被动关闭连接的一方会处于的状态,只要收到了对端的FIN包,回复了对应的ACK包,就变成了CLOSE_WAIT状态,但是如果此时我们服务程序(异常原因)没有继续调用close()函数,导致未发送FIN包,就会造成这个连接一直处于CLOSE_WAIT状态,此时需要排查程序,弄清楚在什么异常场景下,导致程序未发送FIN包。

参考资料:
https://zhuanlan.zhihu.com/p/78540103
https://www.jianshu.com/p/eb0d3e4744f1
https://blog.csdn.net/yu616568/article/details/44677985

导言

什么是主定理,引用维基百科的介绍,在算法分析中,主定理(英语:master theorem)提供了用渐近符号(大O符号)表示许多由分治法得到的递推关系式的方法。所以,在算法复杂度分析时,我们经常需要使用主定理做复杂度的推导,尤其是各种类型的分治算法,比如二分搜索、归并排序、二叉树的遍历等算法。

理论

算法存在递推关系式
WechatIMG40.jpeg

证明

WechatIMG41.jpeg

总结

以上的证明手写输出,在电脑上面打公式太麻烦,另外证明过程采用的比较简单直接的方式,没有使用特别严格的数学证明方法,便于理解,简单来说,如果a<b^d,那么T(n)主要看O(n^d)这项,如果a==b^d,那么T(n)需要看展开的每一项,如果a>b^d,那么最主要的是看展开后的最后一层子问题,后面有时间,会补充一篇根据主定理推导算法复杂度的文章。