TCP协议分析

Posted on 2020-04-08 | In 计算机协议和技术 , 网络协议 |

Words count in article: 16.6k | Reading time ≈ 59

1. TCP协议概述

TCP协议，全称Transmission Control Protocol（传输控制协议），是一种全双工通信、面向连接的、可靠的、基于字节流的传输层通信协议。

全双工通信：即建立TCP连接之后，通信双方都可以发送数据。
面向连接：意味着两个使用TCP的应用（通常是一个客户和一个服务器）在彼此交换数据之前必须先建立一个TCP连接。
- 这一过程与打电话很相似，先拨号振铃，等待对方摘机说“喂”，然后才说明是谁。
可靠：IP层并不保证数据报一定被正确地递交到接收方，TCP负责在超时或者传输失败后，重传没有递交成功的数据报。
- 即使被正确递交的数据报，也可能存在错序的问题，这也是TCP的责任，它必须把接收到的数据报重新装配成正确的顺序。
基于字节流：虽然应用程序和TCP的交互是一次一个数据块（大小不等），但TCP把应用程序传来的数据块看成是一连串的无结构的字节流。由TCP传递给IP的信息单位称为报文段或段（segment）
- TCP有一个缓冲，TCP发送报文时，是将应用层数据写入TCP缓冲区中，然后由TCP协议来控制发送这里面的数据，当应用程序传送的数据块太长，TCP就可以把它划分短一些再传送。如果应用程序一次只发送一个字节，TCP也可以等待积累有足够多的字节后再构成报文段发送出去。
- 发送的状态是按字节流的方式发送的，跟应用层写下来的报文长度没有任何关系，所以说是流。

面向字节流的概念，打个比方：
一个蓄水池，有出水口和进水口，开几次进水口和开几次出水口是没有必然联系的，也就是说你可以只进一次水，然后分10次出完（即一次write，可以分10次read读取）。另外，水池里的水接多少就会少多少；往里面进多少水，就会增加多少水，但是不能超过水池的容量，多出的水会溢出。

同时，作为网络协议中举足轻重的传输层协议，TCP协议有这些优秀的机制保证其最为重视的数据可靠性：

超时重传
拥塞处理
滑动窗口

我们将在后面的篇幅中介绍他们。

1.1 TCP和UDP的区别

和UDP相比，TCP协议有如下差异：

TCP	UDP
面向连接（如打电话要先拨号建立连接）	无连接（发送数据之前不需要建立连接）
传输可靠（通过TCP连接传送的数据，无差错，不丢失，不重复，且按序到达）	传输不可靠（尽最大努力交付，即不保证可靠交付）
面向字节流（把数据看成一连串无结构的字节流）	面向报文（无脑传递上下层的报文）
适合传输大量数据	适合传输少量数据
全双工的可靠信道	不可靠信道
首部开销20字节	首部开销8个字节
连接只能是点到点	支持一对一，一对多，多对一和多对多的交互通信
速度慢（需要建立连接、发送确认包等））	速度快
对系统资源的要求较多	对系统资源的要求较少

1.2 TCP协议应用场景

TCP协议是运输层协议，其服务对象自然是应用层。

TCP主要应用在：要求通信数据可靠时，即数据要准确无误地传递给对方如：

传输文件：HTTP、HTTPS、FTP等协议；
传输邮件：POP、SMTP等协议
万维网：HTTP协议
文件传输：FTP协议
电子邮件：SMTP协议
远程终端接入：TELNET协议

1.3 如何保证可靠性

TCP通过下列方式来提供可靠性：

缓冲区：基于缓冲区，应用数据被分割成TCP认为最适合发送的数据块。
超时重传：当TCP发出一个段后，它启动一个定时器，等待目的端确认收到这个报文段。如果不能及时收到一个确认，将重发这个报文段。
接收确认：当TCP收到发自TCP连接另一端的数据，它将发送一个确认。这个确认不是立即发送，通常将推迟几分之一秒。
校验：TCP将保持它首部和数据的检验和。这是一个端到端的检验和，目的是检测数据在传输过程中的任何变化。如果收到段的检验和有差错，TCP将丢弃这个报文段和不确认收到此报文段（希望发端超时并重发）。
重新排序：既然TCP报文段作为IP数据报来传输，而IP数据报的到达可能会失序，因此TCP报文段的到达也可能会失序。如果必要，TCP将对收到的数据进行重新排序，将收到的数据以正确的顺序交给应用层。
既然IP数据报会发生重复，TCP的接收端必须丢弃重复的数据。
TCP还能提供流量控制。TCP连接的每一方都有固定大小的缓冲空间。TCP的接收端只允许另一端发送接收端缓冲区所能接纳的数据。这将防止较快主机致使较慢主机的缓冲区溢出。

1.4 TCP连接的实质

我们都知道TCP是面向连接的服务，所有要通过TCP进行通信的应用都要先建立连接才能通信，在通信完毕之后要记得关闭连接。但是TCP连接到底是什么东西呢？

这里先说结论，连接实际上是操作系统内核的一种数据结构，称为TCP控制块（TCB），对于linux而言是tcp_sock结构。不光连接，连数据包也是由一个数据结构来控制，linux里面称为sk_buff结构。

1.4.1 为什么要有TCB

当应用希望写数据时，
- 不是直接向网卡驱动发数据，而是经过先放入到一个socket发送缓冲区中
- 然后根据一定算法（达到一定数量或者调用flush之后），缓冲区中的数据就会被网卡从缓冲区中拷贝出来，再层层封装，最后经过物理层传输。
当网卡收到数据时
- 会通过DMA直接发送到内存缓冲区中（网卡驱动提前向操作系统申请的一块内存，并且驱动会提前告诉网卡这块内存的地址（注意是物理地址）和大小。如果没有这块内存缓冲区，那么网卡会直接将数据丢掉）
- 然后给CPU发送一个中断信号，通知操作系统一个数据包到了。
- 数据包要先经过校验，分用等操作，到了TCP层，处理程序此时根据TCP首部中的端口号选择一个socket，并将其载荷数据拷贝进socket接收缓冲区。
- 根据TCP首部中的端口号选择一个socket，如何选择呢？这里TCP是利用连接四元组<源IP地址，源端口号，目标IP地址，目标端口号>，并以这个四元组为key，查找hash表找到对应的socket的socket结构指针，并利用该指针找到对应socket的接收缓冲区，并将载荷数据拷贝进去。

所以到这里，我们就应该知道，每个socket结构必须要有自己独立的发送缓冲区和接收缓冲区

1.4.2 什么是Socket

socket是什么呢，实际上socket是对TCP/IP协议的封装，它的出现只是使得程序员更方便地使用TCP/IP协议栈而已。socket本身并不是协议，它是应用层与TCP/IP协议族通信的中间软件抽象层，是一组调用接口（TCP/IP网络的API函数）

或者换句话说，socket是TCP/IP协议实现的封装，和暴露给应用层的函数。他将网络底层复杂的实现统统隐藏，给应用程序方便的使用接口。

在网络通信方面，socket也有很多种，根据不同协议的实现，也有TCP通信的Socket，UDP通信的DatagramSocket，以及与SSL相关JSSE中的SSLSocket，以及这些非阻塞的SocketChannel,DatagramChannel,SSLEngine在安全方面，JCA,JCE,JAAS等等

1.4.3 HTTP短连接和长连接

对于HTTP 1.0的http标准而言，默认连接是短连接，什么是短连接？就是服务器当发送完最后一个字节的数据之后将关闭连接，也就是回收tcp_sock结构，这样，如果客户端再发送数据给服务器，将直接丢弃。即使此时客户端还有这样的结构，但是我们说连接已经关闭或者已经断了。

HTTP 1.1引入了长连接的概念，并把它搞成了默认的连接方式。什么是长连接？就是当完成一个业务之后，socket结构并不回收。这样，只要在socket结构还存在的时候，客户端发送的任何数据，服务器都可以收到，这就是所谓的长连接。

2. TCP的首部

TCP数据被封装在一个IP数据报中

注意：TCP的包是没有IP地址的，那是IP层上的事。TCP只负责源端口和目标端口的维护。

2.1 源端口和目的端口

源端口和目的端口：各占16位2个字节，分别存放源端口号和目的端口号。用于寻找发端和收端应用进程。这两个值加上IP首部中的源端IP地址和目的端IP地址，能唯一确定一个TCP连接。

2.2 序号

序号：简称seq（sequence number），占32位4个字节。序号范围是[0，2^32 - 1]，共2^32 （即4294967296）个序号。序号增加到2^32-1后，下一个序号就又回到0。

TCP是面向字节流的。在一个TCP连接中传送的字节流中的每一个字节都按顺序编号。
TCP会话建立后，会话的每一端都自己维护一个32位（bit）的序号，该序号被用来跟踪该端发送的数据量。这个端每发送一个字节的数据，它维护的序号+1；
当一个TCP会话开启时，它两端的初始序号都是随机的，可能是0和2^32 - 1(即4,294,967,295)之间的任意值
TCP会话的某一端在发送报文段时，会将计算出的报文段数据的第一个字节的序号写入首部的序号字段中。
首部中的序号字段值则是指的是本报文段所发送的数据的第一个字节的序号。
例如，一报文段的序号是301，而数据共有100字节。这就表明：本报文段的数据的第一个字节的序号是301，最后一个字节的序号是400。
- 显然，下一个报文段（如果还有的话）的数据序号应当从401开始，即下一个报文段的序号字段值应为401。这个字段的序号也叫“报文段序号”。

TCP会话建立后，每一端都要各自初始化一个seq，这个初始的seq称作ISN（Inital Sequence Number）

TCP会话的任意端的ISN为什么要是随机的而不是写死的呢？试想：假如连接建好后始终用1来做ISN，如果client发了30个segment过去，但是网络断了，于是 client重连，又用了1做ISN，但是之前连接的那些包到了，于是就被当成了新连接的包，此时，client的Sequence Number 可能是3，而Server端认为client端的这个号是30了。全乱了。

RFC793中说，ISN会和一个假的时钟绑在一起，这个时钟会在每4微秒对ISN做加一操作，直到超过2^32，又从0开始。这样，一个ISN的周期大约是4.55个小时。因为，我们假设我们的TCP Segment在网络上的存活时间不会超过Maximum Segment Lifetime（缩写为MSL – Wikipedia语条），所以，只要MSL的值小于4.55小时，那么，我们就不会重用到ISN。

2.3 确认号

确认号：简称Ack（acknowledgement number），占32位4个字节，是期望收到对方下一个报文段的第一个数据字节的序号。仅当控制位ACK = 1时确认号字段才有效。

例如，B正确收到了A发送过来的一个报文段，其序号字段值是501，而数据长度是200字节（序号501~700），这表明B正确收到了A发送的到序号700为止的数据。
因此，B期望收到A的下一个数据序号是701，于是B在发送给A的确认报文段中把确认号置为701。注意，现在确认号不是501，也不是700，而是701。
总之：B给A发送的报文确认号为= N，则表明：到序号N-1为止的所有数据B都已正确收到。

确认号（acknowledgement number）简称Ack序号，不要将确认序号Ack与下面即将介绍的控制位中的ACK搞混了。

2.4 数据偏移

数据偏移：占32位4个字节，它指出TCP报文段的数据起始处距离TCP报文段的起始处有多远。这个字段实际上是指出TCP报文段的首部长度。

由于首部中还有长度不确定的选项字段，因此数据偏移字段是必要的，但应注意，“数据偏移”的单位是32位字（即以4字节的字为计算单位）。
由于4位二进制数能表示的最大十进制数字是15，因此数据偏移的最大值是60字节，这也是TCP首部的最大字节（即选项长度不能超过40字节）。
2.4 保留

保留：占6位，保留为今后使用，但目前应置为0 。

2.6 6个控制位

6个控制位：用来说明本报文段的性质。

紧急URG（URGent） 当URG=1时，表明紧急指针字段有效。它告诉系统此报文段中有紧急数据，应尽快发送（相当于高优先级的数据），而不要按原来的排队顺序来传送。
- 例如，已经发送了很长的一个程序要在远地的主机上运行。但后来发现了一些问题，需要取消该程序的运行，因此用户从键盘发出中断命令。如果不使用紧急数据，那么这两个字符将存储在接收TCP的缓存末尾。只有在所有的数据被处理完毕后这两个字符才被交付接收方的应用进程。这样做就浪费了很多时间。
- 当URG置为1时，发送应用进程就告诉发送方的TCP有紧急数据要传送。于是发送方TCP就把紧急数据插入到本报文段数据的最前面，而在紧急数据后面的数据仍然是普通数据。这时要与首部中紧急指针（Urgent Pointer）字段配合使用。
确认ACK（ACKnowledgment） 仅当ACK = 1时确认号字段才有效，当ACK = 0时确认号无效。TCP规定，在连接建立后所有的传送的报文段都必须把ACK置为1。
推送 PSH（PuSH） 当两个应用进程进行交互式的通信时，有时在一端的应用进程希望在键入一个命令后立即就能收到对方的响应。在这种情况下，TCP就可以使用推送（push）操作。这时，发送方TCP把PSH置为1，并立即创建一个报文段发送出去。接收方TCP收到PSH=1的报文段，就尽快地（即“推送”向前）交付接收应用进程。而不用再等到整个缓存都填满了后再向上交付。
复位RST（ReSeT） 当RST=1时，表示TCP连接中出现了严重错误（如由于主机崩溃或其他原因），必须释放连接，然后再重新建立传输连接。RST置为1还用来拒绝一个非法的报文段或拒绝打开一个连接。
同步SYN（SYNchronization） 在连接建立时用来同步序号。当SYN=1而ACK=0时，表明这是一个连接请求报文段。对方若同意建立连接，则应在响应的报文段中使SYN=1和ACK=1，因此SYN置为1就表示这是一个连接请求或连接接受报文。
终止FIN（FINis，意思是“完”“终”） 用来释放一个连接。当FIN=1时，表明此报文段的发送发的数据已发送完毕，并要求释放运输连接。

ACK和SYN将在下节详述。

2.7 窗口

窗口：占16位2字节。窗口值是【0，2^16-1（65535）】之间的整数。窗口值告诉对方：从本报文段首部中的确认号算起，我目前允许你发送的数据量（以字节为单位）是这个值的量。之所以要有这个限制，是因为接收方的数据缓存空间是有限的。总之，窗口值作为接收方让发送方设置其发送窗口的依据。TCP的流量控制由连接的每一端通过声明的窗口大小来提供。

2.8 检验和

检验和：占16位2字节。检验和字段检验的范围包括首部和数据这两部分。和UDP用户数据报一样，在计算检验和时，要在TCP报文段的前面加上12字节的伪首部（具体过程可见《UDP协议分析》一文的校验过程）。伪首部的格式和UDP用户数据报的伪首部一样。但应把伪首部第4个字段中的17改为6（TCP的协议号是6）；把第5字段中的UDP中的长度改为TCP长度。接收方收到此报文段后，仍要加上这个伪首部来计算检验和。若使用TPv6,则相应的伪首部也要改变。

2.9 紧急指针

紧急指针：占16位2字节。紧急指针仅在URG=1时才有意义，它指出本报文段中的紧急数据的字节数（紧急数据排在数据的最前面，紧急数据结束后就是普通数据）。

因此，在紧急指针指出了紧急数据的末尾在报文段中的位置（紧急指针是一个正的偏移量，和序号字段中的值相加表示紧急数据最后一个字节的序号。）。当所有紧急数据都处理完时，TCP就告诉应用程序恢复到正常操作。值得注意的是，即使窗口为0时也可以发送紧急数据。
2.10 选项

选项：长度可变，最长可达4字节。当没有使用“选项”时，TCP的首部长度是20字节。

TCP最初只规定了一种选项，即最大报文段长度MSS（Maximum Segment Szie），在连接建立的时候，即在发送SYN段的时候，同时会将MSS发送给对方（MSS选项只能出现在SYN段中！！！），告诉对端他期望接收的TCP报文段数据部分最大长度。
- 注意MSS这个名词含义。MSS是每一个TCP报文段中的数据字段的最大长度。数据字段加上TCP首部才等于整个的TCP报文段。所以MSS并不是整个TCP报文段的最大长度，而是“TCP报文段长度减去TCP首部长度”。
窗口扩大选项：窗口扩大选项是为了扩大窗口。我们知道，TCP首部中窗口字段长度是16位，因此最大的窗口大小为64K字节。虽然这对早期的网络是足够用的，但对于包含卫星信道的网络，传播时延和宽带都很大，要获得高吞吐量需要更大的窗口大小。
- 窗口扩大选项占3字节，其中有一个字节表示移位值S。新的窗口值等于TCP首部中的窗口位数从16增大到（16+S）。移位值允许使用的最大值是14，相当于窗口最大值增大到2（16+14）-1=230-1。
- 窗口扩大选项可以在双方初始建立TCP连接时进行协商。如果连接的某一端实现了窗口扩大，当它不再需要扩大其窗口时，可发送S=0选项，使窗口大小回到16。
时间戳选项：时间戳选项占10字节，其中最主要的字段是时间戳字段（4字节）和时间戳回送回答字段（4字节）。时间戳选项有以下两个概念：
- 用来计算往返时间RTT。发送方在发送报文段时把当前时钟的时间值放入时间戳字段，接收方在确认该报文段时把时间戳字段复制到时间戳回送回答字段。因此，发送方在收到确认报文后，可以准确地计算出RTT来。
- 用于处理TCP序号超过2^32 的情况，这又称为防止序号绕回PAWS。我们知道，TCP报文段的序号只有32位，而每增加2 ^32 个序号就会重复使用原来用过的序号。当使用高速网络时，在一次TCP连接的数据传送中序号很可能被重复使用。
  - 例如，当使用1.5Mbit/s的速度发送报文段时，序号重复要6小时以上。但若用2.5Gbit/s的速率发送报文段，则不到14秒钟序号就会重复。为了使接收方能够把新的报文段和迟到很久的报文段区分开，则可以在报文段中加上这种时间戳。

每个选项的开始是1字节kind字段，说明选项的类型。kind字段为0和1的选项仅占1个字节。其他的选项在kind字节后还有len字节。它说明的长度是指总长度，包括kind字节和len字节。

3. TCP连接的建立与终止

TCP是一个面向连接的协议。无论哪一方向另一方发送数据之前，都必须先在双方之间建立一条连接。

一个TCP连接需要四个元组来表示是同一个连接（src_ip, src_port, dst_ip, dst_port）准确说是五元组，还有一个是协议。但因为这里只是说TCP协议，所以，这里我只说四元组。

前面我们介绍的TCP的首部字段，其中有三个字段，和TCP的连接有密切关系，他们分别是

序号（sequence number）：Seq序号，前面说过，tcp会话中的端会对它发送的每个字节进行编号，一个报文段的序号值=本报文段所发送的数据的第一个字节的序号。
确认号（acknowledgement number）：Ack序号，占32位，只有ACK标志位为1时，确认序号字段才有效，Ack=Seq+1。
标志位（Flags）：共6个，即URG、ACK、PSH、RST、SYN、FIN等。其中重点是：
- SYN：表示发起一个新连接。
- ACK：表示确认序号有效。（其实是用来确认接收到的数据）（注意，这个ACK和确认号Ack不要搞混！！！！）
- FIN：表示释放一个连接。

下图是Wireshark中截出的一段tcp交互的seq和ack变化过程。

Wireshark的seq展示的是相对序号，即以ISN=0为基准的序号相对值。并不是ISN就这么刚好是0

3.1 TCP连接的建立——三次握手

所谓的三次握手即TCP连接的建立。这个连接必须是一方主动打开，另一方被动打开的。以下为客户端主动发起连接的图解：

客户端A的TCP向服务端发出连接请求报文段，其首部中的SYN控制位应置为1，并选择序号x（前面说过，一个端的序号初始值是随机的，我们姑且认为它是x），表明传送数据时的第一个数据字节的序号是x。
- 此时客户端进入SYN-SENT状态。
服务端B的TCP收到连接请求报文段后，如同意，则发回确认：
- 服务端B在确认报文段中应将SYN置为 1，其确认号ACK置位为x + 1，同时自己这端也会给这个确认报文段写入序号=y。
- 此时服务端进入SYN-RCVD状态
客户端A收到此报文段后，向服务端B给出确认，其确认号置为 y + 1。
- 客户端的TCP通知上层应用进程，连接已经建立。客户端进入ESTABLISHED状态
- 当运行服务器进程的服务器主机B的TCP收到客户端主机A的确认后，也通知其上层应用进程，连接已经建立。服务端也进入ESTABLISHED状态

由于客户对报文段进行了编号，它知道哪些序号是期待的，哪些序号是过时的。当客户发现报文段的序号是一个过时的序号时，就会拒绝该报文段，这样就不会造成重复连接。

3.2 TCP连接的终止——四次分手

数据传输结束后，通信双方都可以释放连接。

看起来比较简单，说是四次分手，其实就是FIN-ACK的交互，由主动方和被动方先后各执行了一次而已。上图已经直观展示的过程我们不再赘述，下面说一些比较值得注意的点：

3.2.1 2MSL等待状态

TIME_WAIT状态也称为2MSL等待状态。主动关闭的端（即上图中的客户端）在发送最后一个ACK的时候，没有立刻关闭，而是等待了2个MSL的时间才关闭。

MSL（Maximum Segment Lifetime），指的是一个报文段最大的生存时间，即一个报文段被丢弃前在网络内的最长时间。我们知道这个时间是有限的，因为TCP报文段以IP数据报在网络内传输，而IP数据报则有限制其生存时间的TTL字段。不过不同的TCP实现由不同的MSL设置，我们不去管他到底是何值，只要知道它控制着报文段在网络中的最长生存时间，如果超过MSL时间报文段还没到达彼端，那么它将被丢弃。

之所以A端在发送最后一个ACK后还要等待2MSL的时间才关闭，是因为假如最后一个ACK丢失了，B端会等待ACK超时，然后再重发一个FIN过来，如果A端立刻关闭，它就可能无法响应到这个重发的FIN。只有等待2MSL后A段没有收到B端重发的FIN，A端才会关闭。

3.2.2 半关闭链接

TCP提供了连接的一端在结束它的发送后还能接收来自另一端数据的能力。这就是所谓的半关闭。

显示了一个半关闭的典型例子。假设左方的客户端开始半关闭。

初始端发出的FIN，接着是另一端对这个FIN的ACK报文段。因为接收半关闭的一方仍能发送数据（这是半关闭的基础）。
我们只显示一个数据报文段和一个ACK报文段，但可能发送了许多数据报文段。
当收到半关闭的一端在完成它的数据传送后，将发送一个FIN关闭这个方向的连接，这将传送一个文件结束符给发起这个半关闭的应用进程。当对第二个FIN进行确认后，这个连接便彻底关闭了。

3.3 总结

建连接为什么需要三次握手？
- 因为通信的双方要互相通知对方自己的ISN（也就上图中的 x 和 y）——所以需要两端各发出一个SYN（全称Synchronize Sequence Numbers，顾名思义，就是用来同步对方自己的ISN的）。ISN后续要作为数据通信的序号，以保证应用层接收到的数据不会因为网络上的传输的问题而乱序。
- 而光有SYN还不够，发端还要确认对端真的收到了我SYN，而不是我发出去SYN就了事，所以还有最后一个ACK
断连接为什么需要四次挥手
- 因为TCP是全双工的，所以，发送方和接收方都需要各一次的Fin和Ack。只不过，有一方是被动的，所以看上去就成了所谓的4次挥手。
- 其实仔细看，挥手比起握手之所以多了一次，主要是收到第一个fin包后单独回复了一个ack包，如果能回复fin+ack那么四次挥手也就变成三次了。
- 之所以被动端没有在收到fin后回复fin+ack，是因为在CLOSE_WAIT状态阶段，被动端需要去通知应用进程，会有一些时间消耗，所以先回发一个ack，等应用进程确定关闭后，再发送一个fin。否则如果应用进程没有关闭，至少还能维持一个半关闭链接。
- 如果两边同时断连接，那就会就进入到CLOSING状态，然后到达TIME_WAIT状态。

4 TCP数据的交互

我们已经在前文的叙述中大概知道了TCP的数据传输，是通过数据和ack的相互交替来确认的，TCP连接的任意一端发送数据，都会捎带一个seq（数据的第一个字节的序号），接收端接收到数据后，返回ACK（控制位）=1，Ack（确认号）=seq+len

注意，Ack=seq+len，表示的不是它要确认的data的最后一个字节的序号，而是它希望下次接收到的第一个序号。
比如，seq=90，len=1，那这唯一的1字节的data，它的序号就是90，Ack=90+1=91，表示它希望下次接受的第一个序号是从91开始。

4.1 捎带确认Delay ACK

通常TCP在接收到数据时并不立即发送ACK，相反，它推迟发送，以便将ACK与需要沿该方向发送的数据（这个数据可以是应用数据，也可以是另外一个同方向的ACK）一起发送（有时称这种现象为数据捎带确认），这样做的目的是尽量减少发往网络的报文，以提高传输的效率，节省网络资源。

为了防止产生超时重传，绝大多数情况下，这个等待时间为200ms，超过了200ms，如果没有数据要一起发送，就直接发送ACK报文。

4.2 累计确认和Duplicate ACK

在TCP会话中，发送方对段的发送速度有时候非常快，比如发送方发了A,B,C,D四个段；段A含字节0到10，段B含字节11到20，段C含字节21到30，段D包含字节31到40

接受方成功收到段A，段B，段D，只有段C丢失了。那么接受方发回一个包含确认序号21的ACK（而不是分别给段A和段B都回复一个ACK，等于是把段A和段B的ACK合并了一样），发送方收到这个合并的ACK，就知道字节0到20(段A，段B)都成功收到。

通过累积确认的方式，在发送方快速发包的场景，一个ACK可以直接确认接收方接收到的连续序号的好几个段，这样减少报文段的传输。

注意，如果段C没有收到，那么段D即便收到了，接收方也不会回复段D的ACK，因为一旦回复段D的ACK，就表示段D以前的数据都收到了，但其实段C还没收到。

因为段C丢失，之后接收端即便接收到段E，段F等数据，也只会重复回复确认序号21的ACK，这时我们可以看到，因为段C丢失，接收端重复发送了很多次Ack=21，这种ACK我们称之为冗余ACK（duplicate ACK）。

4.3 Nagle算法

在TCP传输数据流中，存在两种类型的TCP报文段，一种包含成块数据（通常是满长度的，利用缓存，使报文一次发送就携带一个报文段最多容纳的字节数），另一种则包含交互数据（通常只有携带几个字节数据）。

对于成块数据的报文段，TCP采用正常的流程发送即可，因为数据利用率很高。而对于交互数据的报文段（也就是ACK），数据利用率就显得很低（因为ACK一般就一个IP头和TCP头），在网络环境不好的情况下容易加重网络负担。所以TCP必须对交互数据单独处理

nagle算法用于处理小报文段（微小分组）的发送问题，其核心思想是允许网络中最多只能有一个小分组被发送，而待发送的其它小分组会被重新分组成一个”较大的”小分组，等收到上一个小分组的应答后再发送。

比如客户端需要依次向服务器发送大小为1,2,3,1,2字节的5个分组

在没有开启nagle算法的情况下，这些小分组会被依次发送（不需要等待上一个小分组的应答，因为没启动nagle），总共发送的报文段（分组）个数为5

当开启nagle算法时，客户端首先发送大小为1字节的第一个分组，随后其它分组到达发送缓冲区，由于上一个分组的应答还没有收到，所以TCP会先缓存新来的这4个小分组，并将其重新分组，组成一个大小为8(2+3+1+2)字节的”较大的”小分组。当第一个小分组的应答收到后，客户端将这个8字节的分组发送。总共发送的报文段（分组）个数为2。

将套接字描述符设置TCP_NODELAY选项可以禁止nagle算法

4.4 超时重传

TCP提供可靠的运输层。它使用的方法之一就是确认从另一端收到的数据。但数据和确认都有可能会丢失。TCP通过在发送时设置一个定时器来解决这种问题。如果当定时器溢出时还没有收到确认，它就重传该数据。对任何实现而言，关键之处就在于超时和重传的策略，即怎样决定超时间隔和如何确定重传的频率。

下图是一个超时重传的例子：

第1、2和3行表示正常的TCP连接建立的过程
第4行是“hello,world”（12个字符加上回车和换行）的传输过程
第5行是其确认。接着我们从svr4拔掉了以太网电缆
第6行表示“andhi”将被发送。第7~18行是这个报文段的12次重传过程，
而第19行则是发送方的TCP最终放弃并发送一个复位信号的过程。

连续重传之间不同的时间差，我们整理后发现他们分别为1.5、3、6、12、24、48和多个64秒。这个倍乘关系被称为“指数退避(exponentialbackoff)”。也就是说，每一次超时，等待的时间都会翻倍，直到等待时间为64秒为止。

首次分组传输（第6行，24.480秒）与复位信号传输（第19行，566.488秒）之间的时间差约为9分钟，该时间在目前的TCP实现中，大多数是不可变的。也就是大多数的TCP实现都要尝试9分钟才会放弃。

4.5 选择确认

4.5.1 SACK

我们知道累计确认，不会越过接收方未接受到的序号进行确认，如前例中的ABCD四个段，段A含字节0到10，段B含字节11到20，段C含字节21到30，段D包含字节31到40。

段C未收到，那么是不会返回确认号为41的ACK的。即便接收方已经收到了段D。

这种情况下，发送方只接收到了ack=21，那对于发送方而言，它可以有两种理解：

段C丢失了
段C和段D都丢失了

这时为了保险起见，发送方可能会重传段C和段D，但我们知道其实段D是没有必要重传的。

为了解决这个问题，TCP实现引入了选择确认机制。

选择确认全称叫做Selective Acknowledgment(SACK)，这种方式需要在TCP首部的选项中里加一个SACK的字段，它的工作原理也十分简单，一目了然：

这样，在发送端就可以根据回传的SACK来知道哪些数据到了，哪些没有到。

选择确认的数据包长这样：

这个确认包只有tcp首部，没有数据部分
Kind：SACK（5）用来表示这是选择确认（SACK），该字段占用一个字节。
Length表示tcp选项长度，占用一个字节，左边界和右边界各占用4字节，也就是说这里总共用掉了10字节。
其中left edge表示接收方接收到的数据块中的左边界位置（起始字节）
right edge可以理解为接收方接收到的数据块中的结束位置（右边界）

也就是说，通过左边界和右边界我们可以指明一个数据块的位置。那么我们可以根据捕获的数据报中的确认号丢失的数据块中的起始字节，也就是要重传的起始字节，再结合接收窗口，左边界和右边界。我们可以推出接收窗口中的已经接收到的数据块，和未接收到的数据块：

这样，发送方在进行选择性重传时，会从2336611189字节的位置开始重传。注意：对于已经接收到的字节数据块（2336631881 - 2336693150）是不会被重传的。

在前面学习TCP首部的时候我们知道，TCP首部中的选项部分最大是40字节，选择确认选项左边界和右边界在指明一个数据块时就用掉了8字节，那么指明4个数据块就用掉了32字节，再加上Kind：SACK（5）和Length两个字段占用的2字节，最终只剩下了6字节，换句话说，TCP选项的选择确认选项最多也就只能指明4个数据块

4.5.2 Duplicate SACK

Duplicate SACK又称D-SACK，其主要使用了SACK来告诉发送方有哪些数据被重复接收了。

作为对比，SACK是告诉发送方，接受方已经收到了哪些数据，不要混淆。

那什么样的SACK是D-SACK呢？

答案是：

如果SACK的第一个段的范围被ACK所覆盖，那么就是D-SACK
- 假如发送端已经收到了一个ACK报文，内容为：[Ack=4000, SACK=5000-5500, 4500-5500]，Ack=4000表示序号为4000以前的字节都收到了，这时候再看选项中的SACK=3000-3500，那么很显然，SACK框定的字节范围是已经被确认的范围，那么这个SACK是D-SACK，3000-3500也就是被重传的数据段。
如果SACK的第一个段的范围被SACK的第二个段覆盖，那么就是D-SACK
- 假如发送端收到一个[Ack=4000,SACK=5000-5500, 4500-5500]，那么第二个段的区间4500-5500，覆盖了第一个段的区间5000-5500，这表示该SACK是个D-SACK，5000-5499段是重复收到的。

D-SACK在如下场景发挥比较积极的作用：

ACK丢包
- 如果一个发送端发送序号为3000-3999的段，却没收到对应的ACK，那么过一段时间发送端重传该段，紧接着却收到了[Ack=4000,SACK=3000-3999]，那么发送端就知道，之前的那个ACK丢失了。
发送延误
- 发送端发送序号为1000-1499的段，这个段因为网络延迟，导致接收端迟迟没有收到。发送端继续发送后面的段，但接收端因为没有收到1000-1499的段，所以只会回复[Ack=1500]
- 发送端收到3次[Ack=1500]，就会重传这个1000-1499的段，在重传的期间，接收端也收到了姗姗来迟的原来的1000-1499的段，这时面对重传的新段，接收端返回了[Ack=4000, SACK=1000-1499]
- 发送端通过这个D-SACK，就知道之前发出去的段，是因为网络延迟才迟到的。

可见，引入了D-SACK，有这么几个好处：

可以让发送方知道，是发出去的包丢了，还是回来的ACK包丢了。
是不是自己的timeout太小了，导致重传。
网络上出现了先发的包后到的情况（又称reordering）
网络上是不是把我的数据包给复制了。

5 RTT算法

从前文的TCP重传机制我们知道Timeout的设置对于重传非常重要：

设长了，重发就慢，丢了老半天才重发，没有效率，性能差；
设短了，会导致可能并没有丢就重发。于是重发的就快，会增加网络拥塞，导致更多的超时，更多的超时导致更多的重发。

而且，这个超时时间在不同的网络的情况下，根本没有办法设置一个死的值。由于路由器和网络流量均会变化，因此我们认为这个时间可能经常会发生变化，TCP应该跟踪这些变化并相应地改变其超时时间。

我们把这里的超时时间命名为RTO（Retransmission TimeOut），为了动态地设置RTO，TCP引入了RTT的概念——Round Trip Time，也就是一个数据包从发出去到回来的时间。

听起来似乎很简单，好像就是在发送端发包时记下t0，然后接收端再把这个ack回来时再记一个t1，于是RTT = t1 – t0。但其实没那么简单，这只是一个采样，不能代表普遍情况。

5.1 经典算法

RFC793中定义的经典算法是这样的：

首先，先采样RTT，记下最近好几次的RTT值。
然后做平滑计算SRTT（ Smoothed RTT）。公式为：（其中的 α 取值在0.8 到 0.9之间，这个算法英文叫Exponential weighted moving average，中文叫：加权移动平均）

SRTT = ( α * SRTT ) + ((1- α) * RTT)

开始计算RTO。公式如下：

RTO = min [UBOUND, max [ LBOUND, (β * SRTT) ] ]

其中：
UBOUND是最大的timeout时间，上限值
LBOUND是最小的timeout时间，下限值
β 值一般在1.3到2.0之间。

5.2 Karn / Partridge 算法

但是上面的这个算法在重传的时候会出有一个终极问题——你是用第一次发数据的时间和ack回来的时间做RTT样本值，还是用重传的时间和ACK回来的时间做RTT样本值？

这个问题无论你选那头都是按下葫芦起了瓢。如下图所示：

情况（a）是ack没回来，所以重传。如果你计算第一次发送和ACK的时间，那么，明显算大了。
情况（b）是ack回来慢了，但是导致了重传，但刚重传不一会儿，之前ACK就回来了。如果你是算重传的时间和ACK回来的时间的差，就会算短了。

所以1987年的时候，搞了一个叫Karn / Partridge算法，这个算法的最大特点是——忽略重传，不把重传的RTT做采样（你看，你不需要去解决不存在的问题）。

但是，这样一来，又会引发一个大BUG——如果在某一时间，网络闪动，突然变慢了，产生了比较大的延时，这个延时导致要重传所有的包（因为之前的RTO很小，所以很容易就超时），于是，因为重传的不算，所以，RTO就不会被更新，导致包仍非常容易超时，这是一个灾难。

于是Karn算法用了一个取巧的方式——只要一发生重传，就对现有的RTO值翻倍（这就是所谓的 Exponential backoff），很明显，这种死规矩对于一个需要估计比较准确的RTT也不靠谱。

5.3 Jacobson / Karels 算法

前面两种算法用的都是“加权移动平均”，这种方法最大的毛病就是如果RTT有一个大的波动的话，很难被发现，因为被平滑掉了。所以，1988年，又有人推出来了一个新的算法，这个算法叫Jacobson / Karels Algorithm（参看RFC6289）。这个算法引入了最新的RTT的采样和平滑过的SRTT的差距做因子来计算。

我们每次采样，都能得到一个新的RTT，即RTT[新]，除此之外，还引入了

SRTT（Smoothed RTT）——平滑 RTT
DevRTT（Deviation RTT）——滑 RTT 和真实的差距

这二者的值，每次采样之后都会更新，于是得到公式如下：

SRTT[新] = SRTT[旧] + α ( RTT[新] – SRTT[旧] ) —— 计算平滑 RTT

DevRTT[新] = ( 1-β ) * DevRTT + β * ( | RTT[新] - SRTT[旧] | ) ——计算平滑 RTT 和真实的差距（加权移动平均）

RTO= µ * SRTT + ∂ * DevRTT

其中：α、β、μ、∂ 是可以调整的参数，在 RFC6298 中给出了对应的参考值，而在Linux下，α = 0.125，β = 0.25， μ = 1，∂ = 4；

Jacobson / Karels算法在被用在今天的TCP协议中（Linux的源代码在：tcp_rtt_estimator）。

6 滑动窗口

6.1 背景

我们知道TCP正常的交互是这样的：

这带来了一个问题：吞吐量非常的低。我们发完包1，一定要等确认包1.我们才能发送第二个包。

那如何提高吞吐量？我们可不可以连发几个包等他一起确认呢？

这样确实可以提高吞吐量，发送两个包，所花的时间只是原来一个来回的时间。

但是，新的问题又来了，如果我一次把太多的包连发，超过了接收端的处理上限，导致中途一直重传超时的包，即占用了带宽，又提高不了太多的吞吐量，如何制定最优解呢？TCP实现了一种被称为滑动窗口的流控机制

6.2 发送窗口和接受窗口

滑动窗口解决的是TCP流量控制的问题，即如果接收端和发送端对数据包的处理速度不同，如何让双方达成一致。

我们知道TCP是全双工的协议，会话的双方都可以同时接收和发送数据。TCP会话的双方都各自维护一个发送窗口（本质是一个缓存） 和一个 接收窗口（本质是一个缓存） 。

各自的接收窗口大小取决于应用、系统、硬件的限制（TCP传输速率不能大于应用的数据处理速率）。
各自的发送窗口的大小，则取决于对端的接收窗口。

在TCP的首部中，我们知道有个窗口（Window Size）字段，它是指接收端的窗口大小（单位字节），即接收窗口的大小。用来告知发送端自己所能接收的数据量，从而达到一部分流控的目的。

同时，选项中还有一个窗口扩展选项（Window Scaling)，前文我们也简单介绍过。窗口扩展选项和窗口字段，这二者由接收端通知发送端，最终确定了发送端的发送窗口大小。

因为接受窗口不是恒定的，所以在会话中，接收端可以不断的通知发端改变窗口大小。

假设，我们设定两边的接受窗口为20*MSS（Maxitum Segment Size），那么我们一个窗口，就可以发送20个满数据的段。如下图（方框内的数字为段的编号）：

其中发送端的段可以分成以下四类

已发送，已收到ACK
已发送，未收到ACK（属于发送窗口）
未发送，但允许发送（属于发送窗口）
未发送，但不允许发送

接收端的段可以分成以下三类

已接收
未接收但允许接收（属于接收窗口）
未接收而且不允许接收

6.3 滑动机制

发送窗口只有收到发送窗口内的段的ACK确认，才会移动发送窗口的左边界。
接收窗口只有在前面所有的段都确认的情况下才会移动左边界。当在前面还有段未接收到，但先收到后面段的情况下，窗口不会移动，也不对窗口外的段进行确认。以此确保对端会对这些数据重传。
- 没有收到G的情况下，窗口不会左移，就算收到窗口外的段，也不会进行确认
遵循累计确认、选择确认等规则。

6.4 滑动过程

flash来自一个模拟TCP滑动窗口的动画：动画地址

假定窗口大小为4*MSS，首先发送端发送A,B,C,D四个包，但是A,B丢失，只有C,D到达接收端。
接收端没有收到A，所以不回复ACK包。发送端重传的A,B,C,D四个包。
这次发送端重传的A,B,C,D四个包全都到达了，接收端先获得A，发ACK包A，但是中途丢失；接收端获得B后，根据累计确认的原则，发D的ACK包，然后窗口滑动。再次获得C,D后，连续回复2个D的ACK包，其中C对应的ACK包丢失。
发送端连收2个D的ACK包，说明4个包对方都已收到，窗口滑动，发E,F,G,H包，其中G包丢失。现在整个序列的状态：ABCD是已发送已确认，EFGH是已发送未确认，I~S是不能发送。
收端先收到E，发E的ACK包；收到F后发F的ACK包；未收到G；收到H，还是发F的ACK包。不幸的是，后两个ACK包全都丢失。
送端收到E的ACK包，窗口向右滑动一位，发送I包，然后再发送F,G,H，其中F丢失。
接收端获得I，因为没有G，只好回复F的ACK包(不过紧接着这个包丢了)。还好，接收端相继收到G,H包。
接收端根据累计确认，连发两个I包，其中H的ACK丢失。窗口向右滑动。
发送端接收I的ACK包后，向右滑动四位。发送J,K,L,M四个包，后面不再分析。

我们之前说过，在会话过程中，窗口大小也是随时可能发生改变的，下图就展示了一次动态的滑动窗口变动过程：

我们可以看到：

发送方不必发送一个全窗口大小的数据。
正如从报文段7到报文段8中变化的那样，窗口的大小可以减小，但是窗口的右边沿却不能够向左移动
接收方在发送一个 ACK前不必等待窗口被填满。在前面我们看到许多实现每收到两个报文段就会发送一个ACK。

6.5 零窗口（Zero Window）

上图，我们可以看到一个处理缓慢的Server（接收端）是怎么把Client（发送端）的TCP Sliding Window给降成0的。此时，你一定会问，如果Window变成0了，TCP会怎么样？是不是发送端就不发数据了？是的，发送端就不发数据了，你可以想像成“Window Closed”，那你一定还会问，如果发送端不发数据了，接收方一会儿Window size 可用了，怎么通知发送端呢？

解决这个问题，TCP使用了Zero Window Probe技术，缩写为ZWP，也就是说，发送端在窗口变成0后，会发ZWP的包给接收方，让接收方来ack他的Window尺寸，一般这个值会设置成3次，第一次大约30-60秒（不同的实现可能会不一样）。如果3次过后还是0的话，有的TCP实现就会发RST把链接断了。

6.6 糊涂窗口综合症（Silly Window Syndrome）

我们知道，发送端的发送窗口大小是受馈于接收端通知的接收窗口大小的，如果接收方太忙了，来不及取走Receive Windows里的数据，那么，就会导致发送方窗口越来越小。到最后，如果接收方腾出几个字节并告诉发送方现在有几个字节的window，而我们的发送方会义无反顾地发送这几个字节。

要知道，我们的TCP+IP头有40个字节，为了几个字节，要达上这么大的开销，这太不经济了。糊涂窗口综合症这个现象就像是你本来可以坐200人的飞机里只做了一两个人。要解决这个问题也不难，就是避免对小的window size做出响应，直到有足够大的window size再响应，这个思路可以同时实现在sender和receiver两端。

如果这个问题是由Receiver端引起的，那么就会使用David D Clark’s 方案。在receiver端，如果收到的数据导致window size小于某个值，可以直接ack(0)回sender，这样就把window给关闭了，也阻止了sender再发数据过来，等到receiver端处理了一些数据后windows size 大于等于了MSS（以太网MSS为1500字节），或者，receiver buffer有一半为空，就可以把window打开让send 发送数据过来。
如果这个问题是由Sender端引起的，那么就会使用前文介绍的Nagle’s算法。我们知道这个算法的思路也是延时处理，积攒数据，等于一架飞机在等待客人，以便一次能多拉一些人。

7 拥塞控制

上面我们知道了，TCP通过Sliding Window来做流控（Flow Control），但是TCP觉得这还不够，因为Sliding Window需要依赖于连接的发送端和接收端，其并不知道网络中间发生了什么。

TCP的设计者觉得，一个伟大而牛逼的协议仅仅做到流控并不够，因为流控只是网络模型4层以上的事，TCP的还应该更聪明地知道整个网络上的事。

如果网络上的延时突然增加，那么，TCP对这个事做出的应对只有重传数据，但是，重传会导致网络的负担更重，于是会导致更大的延迟以及更多的丢包，于是，这个情况就会进入恶性循环被不断地放大。

试想一下，如果一个网络内有成千上万的TCP连接都这么行事，那么马上就会形成“网络风暴”，TCP这个协议就会拖垮整个网络。这是一个灾难。

所以，TCP不能忽略网络上发生的事情，而无脑地一个劲地重发数据，对网络造成更大的伤害。对此TCP的设计理念是：TCP不是一个自私的协议，当拥塞发生的时候，要做自我牺牲。就像交通阻塞一样，每个车都应该把路让出来，而不要再去抢路了。

拥塞控制为发送方增加了另一个窗口：拥塞窗口(congestionwindow)，记为cwnd。它以字节为单位，和接收方通告发送方的窗口（我们叫做通告窗口）一起，控制发送方的窗口大小——发送方取拥塞窗口与通告窗口中的最小值作为发送上限。拥塞窗口是发送方使用的流量控制，而通告窗口则是接收方使用的流量控制。

TCP拥塞控制算法发展的过程中出现了如下几种不同的思路：

基于丢包的拥塞控制：将丢包视为出现拥塞，采取缓慢探测的方式，逐渐增大拥塞窗口，当出现丢包时，将拥塞窗口减小，如Reno、Cubic等。
基于时延的拥塞控制：将时延增加视为出现拥塞，延时增加时增大拥塞窗口，延时减小时减小拥塞窗口，如Vegas、FastTCP等。
基于链路容量的拥塞控制：实时测量网络带宽和时延，认为网络上报文总量大于带宽时延乘积时出现了拥塞，如BBR。
基于学习的拥塞控制：没有特定的拥塞信号，而是借助评价函数，基于训练数据，使用机器学习的方法形成一个控制策略，如Remy。

7.1 Reno算法

Reno现有的众多拥塞控制算法的基础，它将拥塞控制的过程分为四个阶段：

慢启动
拥塞避免
快速重传
快速恢复

这四个阶段的相关算法和处理策略不是一天都搞出来的，这个四阶段算法的发展经历了很多时间，到今天都还在优化中。

Reno算法将收到ACK这一信号作为拥塞窗口增长的依据，在早期低带宽、低时延的网络中能够很好的发挥作用，但是随着网络带宽和延时的增加，Reno的缺点就渐渐体现出来了，发送端从发送报文到收到ACK经历一个RTT，在高带宽延时（High Bandwidth-Delay Product，BDP）网络中，RTT很大，导致拥塞窗口增长很慢，传输速度需要经过很长时间才能达到最大带宽，导致带宽利用率将低。

适用场景：适用于低延时、低带宽的网络。

7.1.1 慢启动（Slow Start）

首先，我们来看一下TCP的慢启动。慢启动的意思是，刚刚加入网络的连接，一点一点地提速，不要一上来便无脑向网络发送多个报文段，把现有的传输秩序搞乱。

慢启动的算法如下：

连接建好的开始先初始化cwnd = 1个MSS，表明可以传一个MSS大小的数据。
每当收到一个ACK，cwnd+1，即相当于每轮次（一个RTT，无拥塞情况下共可收到cwnd个ACK）发送窗口增加一倍，呈指数增长
- 换句话说，一次交互cwnd * 2;
还有一个慢启动门限ssthresh（slow start threshold），是一个上限，当cwnd >= ssthresh时，就会进入“拥塞避免算法”（下文介绍）

所以，我们可以看到，如果网速很快的话，ACK也会返回得快，RTT也会短，那么，这个慢启动就一点也不慢。下图说明了这个过程：

这里需要提一下的是一篇Google的论文《An Argument for Increasing TCP’s Initial Congestion Window》（http://static.googleusercontent.com/media/research.google.com/zh-CN//pubs/archive/36640.pdf）
Linux 3.0后采用了这篇论文的建议——把cwnd 初始化成了 10个MSS。
而Linux 3.0以前，比如2.6，Linux采用了RFC3390，cwnd是跟MSS的值来变的，如果MSS< 1095，则cwnd = 4；如果MSS>2190，则cwnd=2；其它情况下，则是3。

7.1.2 拥塞避免

前面说过，还有一个ssthresh（slow start threshold），是一个上限，当cwnd >= ssthresh时，就会进入“拥塞避免算法”。一般来说ssthresh的值是65535，单位是字节，当cwnd达到这个值时后，算法如下：

收到一个ACK时，cwnd = cwnd + 1/cwnd，即相当于每轮次（一个RTT，无拥塞情况下共可收到cwnd个ACK）发送窗口+1 * MSS，呈线性增长
- 换句话说，一次交互cwnd + 1 * MSS ;

这样就可以避免增长过快导致网络拥塞，慢慢的增加调整到网络的最佳值。很明显，是一个线性上升的算法。

所以我们可以看到：

当cwnd<ssthresh时，使用慢开始算法。
当cwnd>ssthresh时，改用拥塞避免算法。

7.1.3快速重传

在介绍拥塞发生时tcp选择的策略时，我们要先了解快速重传策略。

7.1.3.1 快速重传策略

现有的超时重传机制，还有一些问题：

当一个报文段丢失时，会等待一定的超时周期然后才重传分组，增加了端到端的时延。
当一个报文段丢失时，在其等待超时的过程中，可能会出现这种情况：其后的报文段已经被接收端接收但却迟迟得不到确认，发送端会认为也丢失了，从而引起不必要的重传，既浪费资源也浪费时间。

幸运的是，由于TCP采用的是累计确认机制，即当接收端收到比期望序号大的报文段时，便会重复发送最近一次确认的报文段的确认信号，我们称之为冗余ACK（duplicate ACK）。
如图所示，报文段1成功接收并被确认ACK 2，接收端的期待序号为2，当报文段2丢失，报文段3失序到来，与接收端的期望不匹配，接收端重复发送冗余ACK 2。

这样，如果在超时重传定时器溢出之前，接收到连续的三个重复冗余ACK（其实是收到4个同样的ACK，第一个是正常的，后三个才是冗余的），发送端便知晓哪个报文段在传输过程中丢失了，于是重发该报文段，不需要等待超时重传定时器溢出，大大提高了效率。这便是快速重传机制。

为什么需要3次冗余ACK才会触发快速重传？因为即使发送端是按序发送，由于TCP包是封装在IP包内，IP包在传输时乱序，意味着TCP包到达接收端也是乱序的，乱序的话也会造成接收端发送冗余ACK。如果阈值设置的过小，那么快速重传机制很容易被乱序引发的冗余ACK干扰。

7.1.3.2 拥塞发生时的策略选择

如果慢启动和拥塞避免算法，仍然无法避免TCP连接进入拥塞状态（发生丢包的情况），那么这时，就要采取非常手段了。

对于丢包，我们知道有两种情况会发生：

收到3个duplicate ACK
还没收到3个duplicate ACK，就RTO超时

这两种情况下，TCP选择的算法也不一样，我们先讲比较严重的情况2，再讲程度稍好的情况1。（情况1还能收到3个ACK，情况2直接连ACK都超时或者丢了，网络拥塞更严重）

情况2：还没收到3个duplicate ACK，就RTO超时
- 设置sshthresh = cwnd /2
- cwnd 重置为 1
- 如此一来，cwnd必然小于sshthresh，进入慢启动过程
情况1：收到3个duplicate ACK
- 那毫无疑问，快速重传继续，重发数据段。
- cwnd = cwnd /2
- sshthresh = cwnd
- 进入快速恢复算法——Fast Recovery

上面我们可以看到RTO超时后，sshthresh会变成cwnd的一半，这意味着，如果cwnd<=sshthresh时出现的丢包，那么TCP的sshthresh就会减少一半，然后等cwnd又很快地以指数级增长爬到cwnd=sshthresh这个地方时，就会成慢慢的线性增长。

我们可以看到，TCP是怎么通过这种强烈地震荡快速而小心得找到网站流量的平衡点的。

7.1.4 快速恢复（Fast Recovery）

这个算法定义在RFC5681。快速重传和快速恢复算法一般同时使用（都在情况1中），因为情况1还有ACK能回来，说明了网络还不是那么的糟糕，所以没有必要像RTO超时那么强烈。

注意，正如前面所说，进入Fast Recovery之前，cwnd 和 sshthresh已被更新：cwnd = cwnd /2以及sshthresh = cwnd

然后，真正的Fast Recovery算法如下：

cwnd = sshthresh + 3 * MSS （3的意思是确认有3个数据包被收到了）
重传Duplicated ACKs指定的数据包，这时会有两种结果
- 如果再收到 duplicated Acks，那么cwnd = cwnd +1
- 如果收到了新的Ack，那么，cwnd = sshthresh ，然后就进入了拥塞避免的算法了。

7.2 Vegas算法

该算法的论文是《TCP Vegas: End to End Congestion Avoidance on a Global Internet》

Vegas将时延RTT的增加作为网络出现拥塞的信号，RTT增加，拥塞窗口减小，RTT减小，拥塞窗口增加。

具体来说，Vegas通过比较实际吞吐量和期望吞吐量来调节拥塞窗口的大小：

期望吞吐量：Expected = cwnd / BaseRTT
实际吞吐量：Actual = cwnd / RTT，diff = (Expected-Actual) * BaseRTT

其中，BaseRTT是所有观测来回响应时间的最小值，一般是建立连接后所发的第一个数据包的RTT，cwnd是目前的拥塞窗口的大小。

Vegas定义了两个阈值a，b，当diff > b时，拥塞窗口减小，当a <= diff <=b时，拥塞窗口不变，当diff < a时，拥塞窗口增加。

Vegas算法采用RTT的改变来判断网络的可用带宽，能精确地测量网络的可用带宽，效率比较好。但是，网络中Vegas与其它算法共存的情况下，基于丢包的拥塞控制算法会尝试填满网络中的缓冲区，导致Vegas计算的RTT增大，进而降低拥塞窗口，使得传输速度越来越慢，因此Vegas未能在Internet上普遍采用。

适用场景：适用于网络中只存在Vegas一种拥塞控制算法，竞争公平的情况。

参考资料

UDP协议分析

Posted on 2020-03-18 | In 计算机协议和技术 , 网络协议 |

Words count in article: 1.5k | Reading time ≈ 5

1. UDP的概述

UDP是User Datagram Protocol（用户数据报协议）的缩写，它是传输层的协议，功能即为在IP的数据报服务之上增加了最基本的服务：复用和分用以及差错检测。

UDP提供不可靠的服务（它把应用程序传给IP层的数据发送出去，但是并不保证它们能到达目的地。），具有TCP所没有的优势：

UDP无连接，时间上不存在建立连接需要的时延。空间上，TCP需要在端系统中维护连接状态，需要一定的开销。此连接装入包括接收和发送缓存，拥塞控制参数和序号与确认号的参数。UCP不维护连接状态，也不跟踪这些参数，开销小。空间和时间上都具有优势。
- 举个例子：
- DNS如果运行在TCP之上而不是UDP，那么DNS的速度将会慢很多。
- HTTP使用TCP而不是UDP，是因为对于基于文本数据的Web网页来说，可靠性很重要。
- 同一种专用应用服务器在支持UDP时，一定能支持更多的活动客户机。
分组首部开销小，TCP首部20字节，UDP首部8字节。
UDP没有拥塞控制，应用层能够更好的控制要发送的数据和发送时间，网络中的拥塞控制也不会影响主机的发送速率。某些实时应用要求以稳定的速度发送，能容忍一些数据的丢失，但是不能允许有较大的时延（比如实时视频，直播等）
UDP提供尽最大努力的交付，不保证可靠交付。所有维护传输可靠性的工作需要用户在应用层来完成。没有TCP的确认机制、重传机制。如果因为网络原因没有传送到对端，UDP也不会给应用层返回错误信息
UDP是面向报文的，对应用层交下来的报文，添加首部后直接向下交付为IP层，既不合并，也不拆分，保留这些报文的边界。对IP层交上来UDP用户数据报，在去除首部后就原封不动地交付给上层应用进程，报文不可分割，是UDP数据报处理的最小单位。
- 正是因为这样，UDP显得不够灵活，不能控制读写数据的次数和数量。比如我们要发送100个字节的报文，我们调用一次sendto函数就会发送100字节，对端也需要用recvfrom函数一次性接收100字节，不能使用循环每次获取10个字节，获取十次这样的做法。

UDP常用于一次性传输比较少量数据的网络应用，如DNS，SNMP等，因为对于这些应用，若是采用TCP，为连接的创建，维护和拆除带来不小的开销。UDP也常用于多媒体应用（如IP电话，实时视频会议，流媒体等）数据的可靠传输对他们而言并不重要，TCP的拥塞控制会使他们有较大的延迟，也是不可容忍的

2. UDP首部格式

UDP数据报分为首部和用户数据部分，整个UDP数据报作为IP数据报的数据部分封装在IP数据报中，UDP数据报文结构如图所示：

UDP首部有8个字节，由4个字段构成，每个字段都是两个字节，

源端口：源端口号，需要对方回信时选用，不需要时全部置0.
目的端口：目的端口号，在终点交付报文的时候需要用到。
长度：记录UDP的数据报的长度（包括首部+数据），单位是字节，其最小值为8（表示只有首部，没有数据）
校验和：UDP检验和是一个端到端的检验和。它由发送端计算，然后由接收端验证。其目的是为了发现UDP首部和数据在发送端到接收端之间是否发生变动，有则丢弃。UDP中该字段是可选的（TCP是必须的），当源主机不想计算校验和，则直接令该字段全为0。

当传输层从IP层收到UDP数据报时，就根据首部中的目的端口，把UDP数据报通过相应的端口，上交给应用进程。如果接收方UDP发现收到的报文中的目的端口号不正确（不存在对应端口号的应用进程0,），就丢弃该报文，并由ICMP发送“端口不可达”差错报文给对方

3 UDP校验

UDP检验和的基本计算方法与IP首部检验和计算方法相类似（16bit字的二进制反码和）。

在计算校验和的时候，需要在UDP数据报之前增加12字节的伪首部，伪首部并不是UDP真正的首部。只是在计算校验和，临时添加在UDP数据报的前面，得到一个临时的UDP数据报。校验和就是按照这个临时的UDP数据报计算的。伪首部既不向下传送也不向上递交，而仅仅是为了计算校验和。这样的校验和，既检查了UDP数据报，又对IP数据报的源IP地址和目的IP地址进行了检验。

校验过程如下：

发送方首先把全零放入校验和字段并且添加伪首部
把UDP数据报看成是由许多16位的子串连接起来，若UDP数据报的数据部分不是偶数个字节，则要在数据部分末尾增加一个填充字节(全零字节，此字节不发送）。
按照二进制反码计算出这些16位字的和。

TCP/IP协议学习导览

Posted on 2020-03-17 | In 计算机协议和技术 , 网络协议 |

Words count in article: 7.4k | Reading time ≈ 26

前言

从字面意义上讲，有人可能会认为TCP/IP是指TCP和IP两种协议。实际生活当中有时也确实就是指这两种协议。然而在很多情况下，它只是利用IP进行通信时所必须用到的协议群的统称。具体来说，IP或ICMP、TCP或UDP、TELNET或FTP、以及HTTP等都属于TCP/IP协议。

该文章主要为《TCP-IP详解卷1：协议》归纳笔记

1. 网络的分层

网络协议通常分不同层次进行开发，每一层分别负责不同的通信功能。一个协议族，比如TCP/IP，是一组不同层次上的多个协议的组合。TCP/IP通常被认为是一个四层的协议系统。

链路层
- 有时也称作数据链路层或网络接口层，通常包括操作系统中的设备驱动程序和计算机中对应的网络接口卡。它们一起处理与电缆（或其他任何传输媒介）的物理接口细节。
网络层
- 有时也称作互联网层，处理分组在网络中的活动，例如分组的选路。在TCP/IP协议族中，网络层协议包括IP协议（网际协议），ICMP协议（Internet互联网控制报文协议），以及IGMP协议（Internet组管理协议）。
运输层
- 主要为两台主机上的应用程序提供端到端的通信。在TCP/IP协议族中，有两个互不相同的传输协议：TCP（传输控制协议）和UDP（用户数据报协议）。
- TCP为两台主机提供高可靠性的数据通信。它所做的工作包括把应用程序交给它的数据分成合适的小块交给下面的网络层，确认接收到的分组，设置发送最后确认分组的超时时钟等。由于运输层提供了高可靠性的端到端的通信，因此应用层可以忽略所有这些细节。
- 而另一方面，UDP则为应用层提供一种非常简单的服务。它只是把称作数据报的分组从一台主机发送到另一台主机，但并不保证该数据报能到达另一端。任何必需的可靠性必须由应用层来提供。
应用层
- 负责处理特定的应用程序细节。几乎各种不同的TCP/IP实现都会提供下面这些通用的应用程序：
  - Telnet 远程登录。
  - FTP 文件传输协议。
  - SMTP 简单邮件传送协议。
  - SNMP 简单网络管理协议。

2. TCP/IP协议的分层

在TCP/IP协议族中，有很多种协议。如下图

TCP和UDP是两种最为著名的运输层协议，二者都使用IP作为网络层协议。TCP提供一种可靠的运输层服务，而UDP是不可靠的，它不能保证数据报能安全无误地到达最终目的。
IP是网络层上的主要协议，同时被TCP和UDP使用。TCP和UDP的每组数据都通过端系统和每个中间路由器中的IP层在互联网中进行传输。
ICMP是IP协议的附属协议。IP层用它来与其他主机或路由器交换错误报文和其他重要信息。
IGMP是Internet组管理协议。它用来把一个UDP数据报多播到多个主机。
ARP（地址解析协议）和RARP（逆地址解析协议）是某些网络接口（如以太网和令牌环网）使用的特殊协议，用来转换IP层和网络接口层使用的地址。

3. 网络基础概念

3.1 IP地址——互联网的地址

互联网上的每个接口必须有一个唯一的Internet地址（也称作IP地址）。IP地址长32bit。IP地址具有一定的结构，五类不同的互联网地址格式如图

总体来说，IP地址由网络号和主机号组成，网络号相当于某个网络的编号，主机号相当于相同网络内的主机编号。只有相同网络地址的两台主机才能通信，因此不同网络地址的主机，需要借助路由器转发才能通信。

这些32位的地址通常写成四个十进制的数，其中每个整数对应一个字节。这种表示方法称作“点分十进制表示法（Dotteddecimalnotation）”。例如，140.252.13.33就是一个B类地址。

3.1.1 子网寻址

现在所有的主机都要求支持子网编址。不是把IP地址看成由单纯的一个网络号和一个主机号组成，而是把主机号再分成一个子网号和一个主机号。

子网的出现是基于以下原因：

因为A类和B类地址为主机号分配了太多的空间，可分别容纳的主机数为2^24-2和2^16-2。事实上，在一个网络中人们并不安排这么多的主机
随着互联的发展IPV4地址资源可能会耗尽，如果不划分子网直接将一个C类地址分给一个企业，C类地址可容纳256台主机，但是可能该企业只有20台计算机，这就造成极大浪费
减少网络流量，优化网络性能：隔离数据在整个网络内广播，提高信息传输速率。

3.1.2 子网掩码

子网掩码又叫网络掩码，我们现在把主机号拆分成子网号和主机号了，那拆分后，IP地址的哪些位是表示子网号，哪些位是表示主机号呢？我们需要有一种方式来标识它。这就是子网掩码。

子网掩码是一个32bit的值，其中值为1的比特用来标识网络号和子网号，为0的比特用来标识主机号。

3.2 域名

尽管通过IP地址可以识别主机上的网络接口，进而访问主机，但是人们最喜欢使用的还是主机名。在TCP/IP领域中，域名系统（DNS）是一个分布的数据库，由它来提供IP地址和主机名之间的映射信息。

3.3 封装

每个分层中，都会对所发送的数据附加一个首部，在这个首部中包含了该层必要的信息，如发送的目标地址以及协议相关信息。通常，为协议提供的信息为包首部，所要发送的内容为数据。在下一层的角度看，从上一层收到的包全部都被认为是本层的数据。

TCP传给IP的数据单元称作TCP报文段或简称为TCP段（TCP segment）。IP传给链路层的数据单元称作IP数据报(IP datagram)。通过以太网传输的比特流称作帧(Frame)。

3.4分用

当目的主机收到一个以太网数据帧时，数据就开始从协议栈中由底向上升，同时去掉各层协议加上的报文首部。每层协议盒都要去检查报文首部中的协议标识，以确定接收数据的上层协议。这个过程称作分用（Demultiplexing）。如下图

3.5 端口

正常情况下，IP能锁定一台物理机器，对应着一张网卡，外界发来的数据包网卡都会接收。网卡给程序提供了接口，你监听一下我，要是有消息来了，我就转发给你。这样应用程序就能收到数据了。

紧接着问题来了，一台物理机器上有无数个程序，每个程序都需要监听网卡接发数据，如果网卡把接收到的数据都转发给所有的程序，那么程序将会被大量本不是发送给自己的数据淹没。

为了隔离不同程序的数据，我们添加了一个标识：端口，来作为区分。如果程序A的端口是8080，那么我收到有8080标识的数据，就只会转发给程序A，以此类推。

3.6 MTU

最大传输单元（Maximum Transmission Unit，MTU）是指一种通信协议的某一层上面所能通过的最大数据包大小（以字节为单位）。

如果在IP层要传输一个数据报比链路层的MTU还大，那么IP层就会对这个数据报进行分片。一个数据报会被分为若干片，每个分片的大小都小于或者等于链路层的MTU值。

当同一网络上的主机互相进行通信时，该网络的MTU对通信双方非常重要。但当主机间要通过很多网络才能通信时，对通信双方最重要的是通信路径中最小的MTU，因为在通信路径上不同网络的链路层MTU不同。通信路径中最小的MTU被称为路径MTU(木桶原理)。

网络中一些常见链路层协议MTU的缺省数值如下：

FDDI协议：4352字节
以太网（Ethernet）协议：1500字节
PPPoE（ADSL）协议：1492字节
X.25协议（Dial Up/Modem）：576字节
Point-to-Point：4470字节

3.7 IP分片

因为有MTU的存在，我们要对长度大于MTU的IP数据报进行分片。

任何时候IP层接收到一份要发送的IP数据报时，它要判断向本地哪个接口发送数据（选路），并查询该接口获得其MTU。IP把MTU与数据报长度进行比较，如果需要则进行分片。分片可以发生在原始发送端主机上，也可以发生在中间路由器上。

把一份IP数据报分片以后，只有到达目的地才进行重新组装。重新组装由目的端的IP层来完成，其目的是使分片和重新组装过程对运输层（TCP和UDP）是透明的。

IP首部中，有如下这些字段和分片操作有关：

标识字段：标识字段是IP数据报的唯一主键，同一个数据报分出来的分片，拥有相同的标识字段。在重新组装的时候，通过这个字段，目的端IP层可以知道哪些分片原来是一体的。
片偏移字段：该字段指的是该片的数据在原始数据报中，离开始处的偏移量。通过它，在组装时，可以确定各个分片的次序。
标志字段“不分片”位：还是标志字段中有一个比特称作“不分片”位。如果将这一比特置1，IP将不对数据报进行分片。这时如果遇到IP数据报长度大于MTU的场景，则会把数据报丢弃并发送一个ICMP差错报文给起始端。

4. 链路层协议

在TCP/IP协议族中，链路层主要有三个目的：

为IP模块发送和接收IP数据报；
为ARP模块发送ARP请求和接收ARP应答；
为RARP发送RARP请求和接收RARP应答。

TCP/IP支持多种不同的链路层协议，这取决于网络所使用的硬件，如以太网、令牌环网、FDDI（光纤分布式数据接口）及RS-232串行线路

链路层的协议数据单元是帧——IP层（网络层）的数据报添加首部和尾部，即可封装成帧。

帧主要有两种封装格式IEEE 802封装和以太网封装，其中以太网封装格式是目前的主流。除此之外，还有SLIP（Serial Line IP）封装和PPP（点对点协议）封装。

4.1 IEEE 802封装和以太网封装

IEEE802.2/802.3封装协议
1. 两个6字节的目的地址和源地址，这个地址指的是物理地址，也就是MAC地址(48bit)。ARP和RARP协议对32bit的IP地址和48bit的硬件地址进行映射。
2. 2字节的长度字段，值为后续数据的字节长度，但不包括CRC检验码。
3. 3字节的802.2LLC，
  1. 目的服务访问点（DestinationServiceAccessPoint,DSAP）和源服务访问点（SourceServiceAccessPoint,SSAP）的值都设为0xaa。
  2. Ctrl字段的值设为3。
4. 一共5字节的802.2SNAP。
  1. 3个字节orgcode字段都置为0。
  2. 2字节的类型字段，和以太网帧格式一样，其比较常见的类型字段为：0X0800（IP帧），0X0806（ARP请求/应答帧），0X8035（PARP请求/应答帧），0X8137（NovellIPX），0X809b（AppleTalk）。
5. 数据
6. CRC，CRC字段用于帧内后续字节差错的循环冗余码检验（检验和）（它也被称为FCS或帧检验序列）。
以太网封装协议（RFC 894）
1. 两个6字节的目的地址和源地址，这个地址指的是物理地址，也就是MAC地址(48bit)。ARP和RARP协议对32bit的IP地址和48bit的硬件地址进行映射。
2. 2字节的类型字段，其比较常见的类型字段为：0X0800（IP帧），0X0806（ARP请求/应答帧），0X8035（PARP请求/应答帧），0X8137（NovellIPX），0X809b（AppleTalk）。
3. 数据
4. CRC，CRC字段用于帧内后续字节差错的循环冗余码检验（检验和）（它也被称为FCS或帧检验序列）。

4.2 SLIP：串行线路IP封装协议

SLIP的全称是Serial Line IP。它是一种在串行线路上对IP数据报进行封装的简单形式，在RFC1055中有详细描述。SLIP适用于家庭中每台计算机几乎都有的RS-232串行端口和高速调制解调器接入Internet。

其封装规则十分简单，一图道尽：

给IP数据报的前后端都加上一个称作END（0xc0）的特殊字符。
END（0xc0）SLIP协议中是特殊字符，所以如果IP报文中某个字符为END（0xc0），那么就要连续传输两个字节0xdb和0xdc来取代它。
0xdb这个特殊字符被称作SLIP的ESC字符，如果IP报文中某个字符为SLIP的ESC字符，那么就要连续传输两个字节0xdb和0xdd来取代它。

SLIP是一种简单的帧封装方法，还有一些值得一提的缺陷：

因为缺少源地址字段，SLIP没有办法把本端的IP地址通知给另一端，所以每一端必须知道对方的IP地址。。
数据帧中没有类型字段，如果一条串行线路用于SLIP，那么它不能同时使用其他协议。
SLIP没有在数据帧中加上检验和（类似于以太网中的CRC字段）。如果SLIP传输的报文被线路噪声影响而发生错误，只能通过上层协议来发现

4.3 PPP：点对点封装协议

同样作为常用于低速的串行链路的封装协议，PPP（Point to Point Protocol）点对点协议修改了SLIP协议中的所有缺陷。如图：

每一帧都以标志字符0x7e开始和结束。
一个字节的地址字段，值始终是0xff。
一个字节的控制字段，值始终是0x03。
协议字段，类似于以太网中类型字段的功能。
- 值为0x0021时，表示信息字段是一个IP数据报；
- 值为0xc021时，表示信息字段是链路控制数据；
- 值为0x8021时，表示信息字段是网络控制数据。
数据
CRC字段（或FCS，帧检验序列）是一个循环冗余检验码，以检测数据帧中的错误。

PPP比SLIP具有下面这些优点：

PPP支持在单根串行线路上运行多种协议，不只是IP协议；
每一帧都有循环冗余检验；
通信双方可以进行IP地址的动态协商(使用IP网络控制协议)；
与CSLIP类似，对TCP和IP报文首部进行压缩；
链路控制协议可以对多个数据链路选项进行设置。为这些优点付出的代价是在每一帧的首部增加3个字节，当建立链路时要发送几帧协商数据，以及更为复杂的实现。

5. 网络层协议

5.1 IP协议

IP是TCP/IP协议族中最为核心的协议。所有的TCP、UDP、ICMP及IGMP数据都以IP数据报格式传输。

IP提供不可靠、无连接的数据报传送服务

不可靠（unreliable）的意思是它不能保证IP数据报能成功地到达目的地。IP仅提供最好的传输服务。如果发生某种错误时，如某个路由器暂时用完了缓冲区，IP有一个简单的错误处理算法：丢弃该数据报，然后发送ICMP消息报给信源端。任何要求的可靠性必须由上层来提供（如TCP）。
无连接（connectionless）这个术语的意思是IP并不维护任何关于后续数据报的状态信息。每个数据报的处理是相互独立的。这也说明，IP数据报可以不按发送顺序接收。如果一信源向相同的信宿发送两个连续的数据报（先是A，然后是B），每个数据报都是独立地进行路由选择，可能选择不同的路线，因此B可能在A到达之前先到达。

5.1.1 IP首部

IP数据报的格式如下图所示。普通的IP首部长为20个字节，即160位（不包含选项字段）。

版本号，目前是4或者6，我们平常看到的IPv4和IPv6由此区分。
首部长度，指的是首部（包括任何选项）有多少个4字节（32bit）的数目（也就是首部总位数/32）。由于它每个bit位代表4个字节，且是一个4bit字段，因此首部最长为60个字节。
服务类型，共8bit，其中：
- 3bit优先权字段(现在已被忽略)，默认值是000
- 4bit的TOS子字段，其值分布和含义如下：
  - 1000 – minimize delay #最小延迟：对应于对延迟敏感的应用，如telnet和人login
  - 0100 – maximize throughput #最大吞吐量：对应于对吞吐量要求比较高的应用，如FTP文件应用，对文件传输吞吐量有比较高的要求。
  - 0010 – maximize reliability #最高可靠性：对网络传输可靠性要求高的应用，如使用SNMP的应用、路由协议等等。
  - 0001 – minimize monetary cost #最小费用：如NNTP这种用户网络新闻等。
  - 0000 – normal service #一般服务
- 1bit未用位，但必须置0。
总长度字段，16bit，是指整个IP数据报的长度，以字节为单位。
标识字段，16bit，唯一地标识主机发送的每一份数据报，也就是主机发送报文的id，通常每发送一份报文它的值就会加1。如果IP报文在数据链路层被分片了，那么每一个片里面的这个id字段相同。
标志字段，3bit，第一位保留，第二位置为1，标识禁止分片，这时候如果IP报文大于MTU，IP模块就会丢弃报文；第3位表示更多分片，如果分片了的话，最后一个分片置为1，其他都是0，类似于一个结束标记
分片偏移字段，是分片相对于原始IP报文开始处的偏移，单位是bit，故而实际偏移的字节数为该值 * 8，因此，除了最后一个报文之外，其它的报文长度必须是8的整数倍，否则报文不连续。
TTL（time-to-live）生存时间字段，表示数据报可以经过最多多少个路由器。其初始值由源主机设置（通常为32或64），每经过一个路由器，值减1。值为0时，数据报就被丢弃，并发送ICMP报文通知源主机。该字段是为了防止出现路由循环而设。
协议字段，指在上层（TCP/IP的传输层）使用的协议，可能的协议有UDP、TCP、ICMP、IGMP、IGP等。TCP协议为6，UDP协议为17，ICMP为1。
首部校验和，用于检验IP报文头部在传播的过程中是否出错，主要校验报文头中是否有某一个或几个bit被污染或修改了。
- 首先把检验和字段置为0。以抓包得到的该首部为例：
- 然后，对首部中每16bit进行二进制反码求和，结果存在检验和字段中。
- 当收到一份IP数据报后，同样对首部中每个16bit进行二进制反码的求和。
- 由于接收方在计算过程中包含了发送方存在首部中的检验和，因此，如果首部在传输过程中没有发生任何差错，那么接收方计算的结果应该为全1（也就是0xffff）。如果结果不是全1（即检验和错误），那么IP就丢弃收到的数据报。
- ICMP、IGMP、UDP和TCP都采用相同的检验和算法
源IP地址，32位，4个字节，每一个字节为0～255之间的整数
目的IP地址，32位，4个字节，每一个字节为0～255之间的整数
选项，是数据报中的一个可变长的可选信息。选项可用于：
- 安全和处理限制（用于军事领域）
- 记录路径（让每个路由器都记下它的IP地址）
- 时间戳（让每个路由器都记下它的IP地址和时间）
- 宽松的源站选路（为数据报指定一系列必须经过的IP地址）
- 严格的源站选路（与宽松的源站选路类似，但是要求只能经过指定的这些地址，不能经过其他的地址）。

选项字段很少被使用，并非所有的主机和路由器都支持这些选项。选项字段一直都是以32bit作为界限，在必要的时候插入值为0的填充字节。这样就保证IP首部始终是32bit的整数倍（这是首部长度字段所要求的）。

5.2 ARP协议和RARP协议

ARP协议是“Address Resolution Protocol”（地址解析协议）的缩写。在以太网环境中，数据的传输所依懒的是MAC地址而非IP地址，ARP协议的作用是将已知的IP地址转换为MAC地址。

RARP协议是“Reverse Address Resolution Protocol”（反向地址转换协议）的缩写。具有本地磁盘的系统引导时，一般是从磁盘上的配置文件中读取 IP地址。但是无盘机，如X终端或无盘工作站，则需要采用其他方法来获得IP地址。RARP协议的作用就是将已知的MAC地址转换为IP地址

5.2.1 协议原理

5.2.1.1 APR原理

ARP发送一份称作ARP请求的以太网数据帧给以太网上的每个主机。这个过程称作广播，如下图的虚线所示。ARP请求数据帧中包含目的主机的IP地址（假设主机名为bsdi），其意思是“如果你是这个IP地址的拥有者，请回答你的硬件地址。”

目的主机的ARP层收到这份广播报文后，识别出这是发送端在寻问它的IP地址，于是发送一个ARP应答。这个ARP应答包含IP地址及对应的硬件地址。收到ARP应答后，使ARP进行请求—应答交换的IP数据报现在就可以传送了。

5.2.1.2 RAPR原理

同理：

网络上的每个系统都具有唯一的硬件地址，它是由网络接口生产厂家配置的。无盘系统的RARP实现过程是从接口卡上读取唯一的硬件地址，然后发送一份RARP请求（一帧在网络上广播的数据），请求某个主机响应这个无盘系统的IP地址（在RARP应答中）。从而得到这个MAC地址对应的IP地址

5.2.2 ARP高速缓存

ARP高效运行的关键是由于每个主机上都有一个ARP高速缓存。这个高速缓存存放了最近Internet地址到硬件地址之间的映射记录，从中直接读取，缓解链路压力。高速缓存中每一项的生存时间一般为20分钟，起始时间从被创建时开始算起

我们可以用arp命令来检查ARP高速缓存。参数-a的意思是显示高速缓存中所有的内容。

1
2
3

$ arp -a
> sun (140.252.13.33) at 8:0:20:3:f6:42
> svr4 (140.252.13.34) at 0:0:c0:c2:9b:26

5.2.3 ARP/RARP的分组格式

在以太网上解析IP地址时，ARP/RARP请求和应答分组的格式如图所示

目标mac地址：ARP请求的目的以太网地址，全1时，代表广播地址。
源mac地址：发送ARP请求的以太网地址。
帧类型：以太网帧类型表示后面的数据类型，ARP请求和ARP应答此字段为：0x0806。
硬件类型：硬件类型字段表示硬件地址的类型。它的值为1即表示以太网地址。
协议类型：表示要映射的协议地址类型。它的值为0x0800即表示IP地址。它的值与包含IP数据报的以太网数据帧中的类型字段的值相同，这是有意设计的
硬件地址长度、协议地址长度：表示硬件地址长度和协议地址长度，MAC地址占6字节，IP地址占4字节。
操作类型：值为1，表示进行ARP请求；值为2，表示进行ARP应答；值为3，表示进行RARP请求；值为4，表示进行RARP应答。
发送端以太网地址和协议地址：发送端的硬件地址（在本例中是以太网地址）和协议地址（IP地址）
目的端的硬件地址和目的端的协议地址：目的端的硬件地址（在本例中是以太网地址）和协议地址（IP地址）。（这是重复数据，在以太网的数据帧报头中和ARP请求数据帧中都有发送端的硬件地址。）

对于一个ARP/RARP请求来说，除目的端硬件地址外的所有其他的字段，都已经有填充值。当系统收到一份目的端为本机的ARP请求报文后，它就把硬件地址填进去，然后用两个目的端地址分别替换两个发送端地址，并把操作字段置为2，最后把它发送回去。

ARP/RARP二者的分组格式，除了操作类型字段以外，其他字段都一样

5.3 ICMP协议

ICMP协议，全称是Internet Control Message Protocol，意思是Internet控制消息协议。它是TCP/IP协议族的一个子协议，用于在IP主机、路由器之间传递控制消息（可以理解为回来报信的信鸽）。控制消息是指网络通不通、主机是否可达、路由是否可用等网络本身的消息。这些控制消息虽然并不传输用户数据，但是对于用户数据的传递起着重要的作用。

ICMP 的内容是放在IP数据包的数据部分里来互相交流的。也就是，从ICMP的报文格式来说，ICMP 是IP 的上层协议。但是，正如RFC所记载的，ICMP是分担了IP的一部分功能。所以，被认为是与IP 同层的协议。

5.3.1 ICMP的分类

在RFC，将ICMP 大致分成两种功能：

差错报文：在IP数据包被对方的计算机处理的过程中，发生了某些错误时被使用。不仅传送发生了错误这个事实，也传送错误原因等消息。
查询报文：是在送信方的计算机向对方计算机询问信息时被使用。被询问内容的种类非常丰富，如：目标IP地址的机器是否存在，调查自己网络的子网掩码，取得对方机器的时间信息等。

5.3.2 ICMP的报文

如上图，我们将完整的IP首部+ICMP报文都展示了出来，IP首部各字段，前文已经有过描述。

用来传送ICMP报文的IP数据包上实际上有不少字段。但是实际上与ICMP协议相关的只有7个子段。

协议：ICMP协议的IP数据包，该字段为1；
源IP 地址：顾名思义，不再赘述。
目的IP 地址：顾名思义，不再赘述。
生存时间：TTL，不再赘述。

上述这四个包含在IP 首部的字段。

类型；
代码；
选项数据；

上述这三个包含在ICMP数据部分的字段。

其中类型和代码字段是ICMP报文的核心，这两个字段的组合，可以用来标识ICMP的差错报文和查询报文的大多数场景，如下图：

至于选项数据字段，当ICMP需要传送额外数据时，则放置在选项数据字段中。

6. 运输层协议

6.1 TCP协议

详见文章《TCP协议分析》

6.2 UDP协议

详见文章《UDP协议分析》

参考资料

太厉害了，终于有人能把TCP/IP协议讲的明明白白了！

以太网协议封装格式

完全理解icmp协议

ElasticSearch核心概念详解（index/type/doc/node/shard/replica/segment）

Posted on 2020-02-20 | In 中间件 , ElasticSearch |

Words count in article: 9.8k | Reading time ≈ 34

前言

ElasticSearch，简称ES，是一个基于Lucene的搜索服务器。要想了解ES，必须先了解Lucene。

数据和搜索

我们知道，生活中我们有两类的数据：

结构化数据：也称作行数据，是由二维表结构来逻辑表达和实现的数据，严格地遵循数据格式与长度规范，主要通过关系型数据库进行存储和管理。指具有固定格式或有限长度的数据，如数据库，元数据等。
非结构化数据：又可称为全文数据，不定长或无固定格式，不适于由数据库二维表来表现，包括所有格式的办公文档、XML、HTML、word文档，邮件，各类报表、图片和咅频、视频信息等。

根据两种数据分类，搜索也相应的分为两种：结构化数据搜索和非结构化数据搜索。对于结构化数据，因为它们具有特定的结构，所以我们一般都是可以通过关系型数据库（mysql，oracle等）的二维表（table）的方式存储和搜索，也可以建立索引。

对于非结构化数据，也即对全文数据的搜索主要有两种方法：顺序扫描法，全文检索。

顺序扫描：通过文字名称也可了解到它的大概搜索方式，即按照顺序扫描的方式查询特定的关键字。例如给你一张报纸，让你找到该报纸中“平安”的文字在哪些地方出现过。你肯定需要从头到尾把报纸阅读扫描一遍然后标记出关键字在哪些版块出现过以及它的出现位置。

这种方式无疑是最耗时的最低效的，如果报纸排版字体小，而且版块较多甚至有多份报纸，等你扫描完你的眼睛也差不多了。

全文搜索：对非结构化数据顺序扫描很慢，我们是否可以进行优化？把我们的非结构化数据想办法弄得有一定结构不就行了吗？将非结构化数据中的一部分信息提取出来，重新组织，使其变得有一定结构，然后对此有一定结构的数据进行搜索，从而达到搜索相对较快的目的。

这种方式就构成了全文检索的基本思路。这部分从非结构化数据中提取出的然后重新组织的信息，我们称之索引。这种方式的主要工作量在前期索引的创建，但是对于后期搜索却是快速高效的。

Lucene

通过对生活中数据的类型作了一个简短了解之后，我们知道关系型数据库的SQL检索是处理不了这种非结构化数据的。这种非结构化数据的处理需要依赖全文搜索，而目前市场上开放源代码的最好全文检索引擎工具包就属于 apache 的 Lucene了。

但是 Lucene 只是一个工具包，它不是一个完整的全文检索引擎。Lucene的目的是为软件开发人员提供一个简单易用的工具包，以方便的在目标系统中实现全文检索的功能，或者是以此为基础建立起完整的全文检索引擎。

目前以 Lucene 为基础建立的开源可用全文搜索引擎主要是 Solr 和 Elasticsearch。

Solr 和 Elasticsearch 都是比较成熟的全文搜索引擎，能完成的功能和性能也基本一样。但是 ES 本身就具有分布式的特性和易安装使用的特点，而Solr的分布式需要借助第三方来实现，例如通过使用ZooKeeper来达到分布式协调管理。

不管是 Solr 还是 Elasticsearch 底层都是依赖于 Lucene，而 Lucene 能实现全文搜索主要是因为它实现了倒排索引的查询结构。（稍后展开）

1. ES基本概念详解

ElasticSearch提供了一个分布式多用户能力的全文搜索引擎，基于RESTful web接口。Elasticsearch是用Java语言开发的，并作为Apache许可条款下的开放源码发布，是一种流行的企业级搜索引擎。

ElasticSearch用于云计算中，能够达到实时搜索，稳定，可靠，快速，安装使用方便。其官方客户端在Java、.NET（C#）、PHP、Python、Apache Groovy、Ruby和许多其他语言中都是可用的。根据DB-Engines的排名显示，Elasticsearch是最受欢迎的企业搜索引擎，其次是Apache Solr，也是基于Lucene。

不过，Elasticsearch不仅仅是Lucene和全文搜索，我们还能这样去描述它：

分布式的实时文件存储，每个字段都被索引并可被搜索
分布式的实时分析搜索引擎
可以扩展到上百台服务器，处理PB级结构化或非结构化数据

es和lucene，solr一样，都是无模式的基于列式的存储格式，这和大多数的NoSQL数据库是一样的，非常灵活，下面我们通过一张图，来看下关系型数据库映射到es里面，对应的名词关系

1.1 Index

Index，索引，是文档(Document)的容器，是一类文档的集合。

ElasticSearch将它的数据存储在一个或多个索引（index）中。索引就像数据库，可以向索引写入文档或者从索引中读取文档

索引这个词在 ElasticSearch 会有两种意思:

索引(名词)
- 类比传统的关系型数据库领域来说，索引相当于SQL中的一个数据库(Database)。索引由其名称(必须为全小写字符)进行标识。
索引(动词)
- 保存一个文档到索引(名词)的过程。这非常类似于SQL语句中的 INSERT关键词。如果该文档已存在时那就相当于数据库的UPDATE。

1.2 Type

Type，类型，可以理解成关系数据库中Table（虽然不完全一致）。用于区分同一个集合中的不同细分。

但和Table不同的是，不同表中的字段可以同名，但他们还是独立的，比如表A的a字段可以是VARCHAR类型，表B的a字段可以是INT类型。

而不同类型的同名字段，他们其实是同一个字段，所以无法独立，实际上，es在底层，也是将不同type的字段都映射为扁平的模式。而不是为每种type分配单独的映射空间。

这导致了type不适合于描述完全不同类型的数据，如type A有a，b，c三个字段，type B有d，e，f三个字段，那么这种情况建议不要使用type。

A { a,b,c}和B{b,c,d}这种情况才适用，即二者间大部分的数据是相同的，这种情况下，es的扁平化映射，可以复用这部分重合的数据。

之前的版本中，索引和文档中间还有个类型的概念，每个索引下可以建立多个类型，文档存储时需要指定index和type。从6.0.0开始单个索引中只能有一个类型，

7.0.0以后将将不建议使用，8.0.0 以后完全不支持。

1.2.1弃用该概念的原因：

我们虽然可以通俗的去理解Index比作 SQL 的 Database，Type比作SQL的Table。但这并不准确，因为如果在SQL中，Table 之前相互独立，同名的字段在两个表中毫无关系。

但是在ES中，同一个Index 下不同的 Type 如果有同名的字段，他们会被Luecence当作同一个字段，并且他们的定义必须相同。所以我觉得Index现在更像一个表，而Type字段则并没有多少意义。

目前Type已经被Deprecated，在7.0开始，一个索引只能建一个Type为_doc

1.3 Document

Document，文档，Index 里面单条的记录称为Document。等同于关系型数据库表中的行。

我们来看下一个文档的源数据

_index文档所属索引名称。
_type文档所属类型名。
_idDoc的主键。在写入的时候，可以指定该Doc的ID值，如果不指定，则系统自动生成一个唯一的UUID值。
_version文档的版本信息。Elasticsearch通过使用version来保证对文档的变更能以正确的顺序执行，避免乱序造成的数据丢失。
_seq_no严格递增的顺序号，每个文档一个，Shard级别严格递增，保证后写入的Doc的_seq_no大于先写入的Doc的_seq_no。
primary_termprimary_term也和_seq_no一样是一个整数，每当Primary Shard发生重新分配时，比如重启，Primary选举等，_primary_term会递增1
found查询的ID正确那么ture, 如果 Id 不正确，就查不到数据，found字段就是false。
_source文档的原始JSON数据。

2. ES分布式概念详解

2.1 集群(cluster)

ElasticSearch集群实际上是一个分布式系统，它需要具备两个特性：

高可用性
- 服务可用性：允许有节点停止服务；
- 数据可用性：部分节点丢失，不会丢失数据；
可扩展性
- 随着请求量的不断提升，数据量的不断增长，系统可以将数据分布到其他节点，实现水平扩展；

一个集群中可以有一个或者多个节点；

我们采用集群健康值来衡量一个集群的状态

green：所有主要分片和复制分片都可用
yellow：所有主要分片可用，但不是所有复制分片都可用
red：不是所有的主要分片都可用

当集群状态为 red，它仍然正常提供服务，它会在现有存活分片中执行请求，我们需要尽快修复故障分片，防止查询数据的丢失；

2.2 节点(Node)

es集群是通过多台服务器来搭建，它们拥有一个共同的clustername比如叫做“escluster”，每台服务器叫做一个节点，用于存储数据并提供集群的搜索和索引功能。

节点拥有自己的唯一名字，默认在节点启动时会生成一个uuid作为节点名，该名字也可以手动指定。

单个集群可以由任意数量的节点组成。如果只启动了一个节点，则会形成一个单节点的集群。其配置文件如下：

集群名称，用于定义哪些elasticsearch节点属同一个集群。
cluster.name: bigdata
节点名称，用于唯一标识节点，不可重名
node.name: server3
设置索引的分片数,默认为5 
index.number_of_shards: 5 
设置索引的副本数,默认为1: 
index.number_of_replicas: 1

节点是一个ElasticSearch的实例，其本质就是一个Java进程；一台机器上可以运行多个ElasticSearch实例，但是建议在生产环境中一台机器上只运行一个ElasticSearch实例；

2.2.1 四种普通节点

在es节点的yml文件中可以配置节点的类型

1
2
3

conf/elasticsearch.yml:
	node.master: true/false
	node.data: true/false

其中node.master配置表示节点是否具有成为主节点的资格节点。

此属性的值为true，并不意味着这个节点就是主节点。因为真正的主节点，是由多个具有主节点资格的节点进行选举产生的。所以，这个属性只是代表这个节点是不是具有主节点选举资格。

node.data配置表示节点是否存储数据。

node.master和node.data的取值可以有四种情况，表示四种节点类型。

node.master: true并且node.data: true
- 这种组合表示这个节点即有成为主节点的资格，又存储数据。这个时候如果某个节点被选举成为了真正的主节点，那么他还要存储数据，这样对于这个节点的压力就比较大了。elasticsearch默认每个节点都是这样的配置，在测试环境下这样做没问题。实际工作中建议不要这样设置，这样相当于主节点和数据节点的角色混合到一块了。
node.master: false并且node.data: true
- 这种组合表示这个节点没有成为主节点的资格，也就不参与选举，只会存储数据。这个节点我们称为data(数据)节点。在集群中需要单独设置几个这样的节点负责存储数据，后期提供存储和查询服务
node.master: true并且node.data: false
- 这种组合表示这个节点不会存储数据，有成为主节点的资格，可以参与选举，有可能成为真正的主节点。对于master节点而言，这样的配置是最适合的。
node.master: false并且node.data: false
- 这种组合表示这个节点即不会成为主节点，也不会存储数据，这个节点的意义是作为一个client(客户端)节点，主要是针对海量请求的时候，这些节点负责处理用户请求，实现请求转发，负载均衡等功能。

2.2.2 master节点

拥有选举成为master节点资格的节点经过选举，成为了master节点，

Elasticsearch中的master并不像mysql、hadoop集群的master那样，它既不是集群数据的唯一流入点，也不是所有元数据的存放点。所以，一般情况下Elasticsearch的Master负载是很低的。

master集群的主要工作有：

同步集群状态：集群状态信息，由master节点进行维护，并且同步到集群中所有节点。也就是说集群中的任何节点都存储着集群状态信息（经过master的同步），但只有Master能够改变信息。我们可以通过接口读取它，如：/_cluster/state
- 集群状态中包括：
  1. 集群层面的设置
  2. 集群内有哪些节点的信息
  3. 各索引的设置，映射，分析器和别名等设置
  4. 索引内各分片所在的节点位置
集群状态的修改：集群状态的修改通过Master节点完成，比如索引的创建删除，mapping的修改等等。
- 我们知道配置项dynamic=true表示对于未mapping的新字段，es会尝试猜测该字段的类型，并mapping它。此时数据节点需要跟Master通信，通知Master修改Mapping。这个时候的index写入是阻塞的。等Master修改了集群状态之后，再同步到所有节点，才可以继续写入。

2.2.3 master选举

详见另一篇文章ElasticSearch Master选举机制浅析

2.3 分片(Shared)

分片是什么？简单来讲就是咱们在ES中所有数据的文件块，也是数据的最小单元块，整个ES集群的核心就是对所有分片进行分布、索引、负载、路由等操作，来达到惊人的速度。

文档存储在分片中，然后分片分配到集群中的节点上。当集群扩容或缩小，Elasticsearch 将会自动在节点间迁移分片，以使集群保持平衡。

假设 IndexA 有2个分片，我们向 IndexA 中插入10条数据 (10个文档)，那么这10条数据会尽可能平均的分为5条存储在第一个分片，剩下的5条会存储在另一个分片中。

一个分片(shard)是一个最小级别“工作单元(worker unit)”，大多数情况下，它只是保存了索引中所有数据的一部分。

这类似于 MySql 的分库分表。

2.3.1 分片的种类

一个分片就是一个运行的 lucene 实例，一个节点可以包含多个分片，这些分片可以是：

主分片（primary shard）
- 用于解决数据水平扩展的问题，一个索引的所有数据是分布在所有主分片之上的（每个主分片承担一部分数据，主分片又分布在不同的节点上）
- 一个索引的主分片数量只能在创建时指定，es默认情况下数量为5，主分片数量一经指定后期无法修改，除非对数据进行重新构建索引（reindex操作）。
副分片（replica shard）
- 用于解决数据高可用的问题，一个副本分片即一个主分片的拷贝，其数量可以动态调整，通过增加副本分片也可以实现提升系统读性能的作用。
- 副本分片还可以实现es的故障转移，如果持有主分片的节点挂掉了，一个副本分片就会晋升为主分片的角色。
  - 为了达到故障转移的作用，主分片和其对应的副本分片是不会在同一个节点上的。
- 对文档的新建、索引和删除请求都是写操作，必须在主分片上面完成之后才能被复制到相关的副本分片。
  - 为了提高写入的能力，ES这个过程是并发写的，同时为了解决并发写的过程中数据冲突的问题，ES 通过乐观锁的方式控制，每个文档都有一个 _version （版本）号，当文档被修改时版本号递增。一旦所有的副本分片都报告写成功才会向协调节点报告成功，协调节点向客户端报告成功。
- es默认情况下为每个主分片创造一个副本

2.3.2 分片的优势

突破单节点容量上限，例如我们有10TB大小的总文档，分成20个分片分布于10台节点上，那么每个节点只需要1T的容量即可。
服务高可用，由于有副本分片的存在，只要不是存储某个文档的node全挂了，那么这个文档数据就不会丢。副本分片提供了灾备的能力。
故障转移，当主分片节点故障后，可升级一个副分片为新的主分片来应对节点故障。
扩展性能，通过在所有replicas上并行搜索来提高读性能.由于replicas上的数据是近实时的(near realtime),因此所有replicas都能提供搜索功能,通过设置合理的replicas数量可以极高的提高搜索吞吐量

2.3.3 分片的配置

创建 IndexName 索引时候，在 Mapping 中可以如下设置分片 (curl)

PUT indexName
{
	"settings": {
		...
		"number_of_shards": 5,
		"number_of_replicas": 1
		...
	}
}

或者

curl -H "Content-Type: application/json" -XPUT localhost:9200/indexName -d '
{
	"settings": {
		...
		"number_of_shards": 5,
		"number_of_replicas": 1
		...
	}
}'

当索引创建完成的时候，主分片的数量就固定了，但是复制分片的数量可以随时调整，根据需求扩大或者缩小规模。如把复制分片的数量从原来的 1 增加到 2 ：

curl -H "Content-Type: application/json" -XPUT localhost:9200/indexName/_settings -d '
{
    "number_of_replicas": 2
}'

2.3.4 分片数量

对于生产环境中分片的设定，需要提前做好容量规划，因为主分片数是在索引创建时预先设定的，后续无法修改。

那么分片的数量是否越大越好呢？答案当然是否定的。

分片数设置过小
- 导致后续无法通过增加节点进行水平扩展。
- 导致分片的数据量太大，数据在重新分配时耗时；
分片数设置过大
- 每个分片都是一个小的lucene索引，会消耗相应的资源;
- 影响搜索结果的相关性打分，影响统计结果的准确性；
- 单个节点上过多的分片，会导致资源浪费，同时也会影响性能（每个搜索请求会调度到索引的每个分片中.但当分片位于同一个节点，就会开始竞争相同的硬件资源时, 性能便会逐步下降）；

默认情况下，ES会为每个索引创建5个分片，即使是在单机环境下。这种冗余被称作过度分配（Over Allocation），目前看来这么做完全没有必要，仅在散布文档到分片和处理查询的过程中就增加了更多的复杂性，好在ES的优秀性能掩盖了这一点。但我们要知道在单机环境下配置5个分片是没有必要的。

分片的数量和大小没有定例，可以参考官方的文档我在 Elasticsearch 集群内应该设置多少个分片？，提取核心要素就是：

“我应该有多少个分片？”
- 答：每个节点的分片数量应该保持在保持在低于每1GB堆内存对应集群的分片在20-25之间。
- 也就是shared number/node GBs <20 或shared number/node GBs <25，即shared number<20 * node GBs 或 shared number<25 * node GBs
“我的分片应该有多大”？
- 答：分片大小为50GB通常被界定为适用于各种用例的极限，即不应该超过50GB。但实际上，根据经验，小于30GB更为合理

2.3.5 分片和副本的分布

配置一套高可用的集群，我们必须要了解es集群的数据分布和负载原理，我们先来看下es如何分布分片。

2.3.5.1 主分片分布

假设我们只有三个主分片：

单机分片分布：
2个节点分片分布：
3个节点分片分布：
9个节点分片分布：

可以看到，es尽量根据我们指定的分片数来平均分配到各个节点上

2.3.5.2 副本分布

假设我们有3个节点，3个主分片，和若干个副本（下图边框有粗有细，粗的是主分片，细的是副本分片）

1个副本
2个副本
3个副本

可以看到，es依旧尽量根据我们指定的主副分片数来平均分配到各个节点上，但是不会把存着相同数据的主副分片放在同一个节点上。

如果分片数量太多（如3个副本的情况），由于此时每台机器都已经占满自己的3个分片了，所以此时需要增加新的机器来存放每个主分片的第三个副本，如果没有新的机器。es不会允许同一个节点有多余的分片，所以提示了Unassigned，表示这些分片未指定。

2.3.5.3 多个索引的分片分布

2.3.6 分片分配策略和原理

详见ELASTICSEARCH ALLOCATION 分析

2.3.7 读写数据时的分片路由

加入我们有一个拥有3个节点的集群，共拥有12个分片，其中有4个主分片（S0、S1、S2、S3）和8个副本分片（R0、R1、R2、R3），每个主分片对应两个副本分片，节点1是主节点（Master节点）负责整个集群的状态。

2.3.7.1 对特定doc的读写操作

写数据是只能写在主分片上，然后同步到副本分片。这里有四个主分片，数据是根据什么规则写到特定分片上的呢？这条索引数据为什么被写到S0上而不写到S1或S2上？那条数据为什么又被写到S3上而不写到S0上了？

首先这肯定不会是随机的，否则将来要获取文档的时候我们就不知道从何处寻找了。实际上，这个过程是根据下面这个公式决定的：

shard = hash(routing) % number_of_primary_shards

routing 是一个可变值，默认是文档的 _id ，也可以设置成一个自定义的值。routing 通过 hash 函数生成一个数字，然后这个数字再除以 number_of_primary_shards （主分片的数量）后得到余数。这个在 0 到 numberofprimary_shards-1 之间的余数，就是我们所寻求的文档所在分片的位置。

这就解释了为什么我们要在创建索引的时候就确定好主分片的数量并且永远不会改变这个数量：因为如果数量变化了，那么所有之前路由的值都会无效，文档也再也找不到了。

由于在ES集群中每个节点通过上面的计算公式都知道集群中的文档的存放位置，所以每个节点都有处理读写请求的能力。

在一个写请求被发送到某个节点后，该节点即为前面说过的协调节点，协调节点会根据路由公式计算出需要写到哪个分片上，再将请求转发到该分片的主分片节点上。

假如此时数据通过路由计算公式取余后得到的值是 shard = hash(routing) % 4 = 0，则具体流程如下：

客户端向ES1节点（协调节点）发送写请求，通过路由计算公式得到值为0，则当前数据应被写到主分片S0上。
ES1节点将请求转发到S0主分片所在的节点ES3，ES3接受请求并写入到磁盘。
并发将数据复制到两个副本分片R0上，其中通过乐观并发控制数据的冲突。一旦所有的副本分片都报告成功，则节点ES3将向协调节点报告成功，协调节点向客户端报告成功。

2.3.7.2 搜索时的读操作

es最强大的是做全文检索

客户端发送请求到一个coordinate node。
协调节点将搜索请求转发到所有的shard对应的primary shard 或 replica shard ，都可以。
query phase：每个shard将自己的搜索结果（其实就是一些doc id）返回给协调节点，由协调节点进行数据的合并、排序、分页等操作，产出最终结果。
fetch phase：接着由协调节点根据doc id去各个节点上拉取实际的document数据，最终返回给客户端。

写请求是写入primary shard，然后同步给所有的replica shard

读请求可以从primary shard 或者 replica shard 读取，采用的是随机轮询算法。

2.4 段（segment）

数据被分配到特定的分片和副本上之后，最终是存储到磁盘上的，这样在断电的时候就不会丢失数据。

具体的存储路径可在配置文件 ../config/elasticsearch.yml中进行设置，默认存储在安装目录的data文件夹下。建议不要使用默认值，因为若ES进行了升级，则有可能导致数据全部丢失。

1 2	path.data: /path/to/data //索引数据 path.logs: /path/to/logs //日志记录

segment是实现ES近实时搜索的关键，是数据索引（动词）过程中的重要载体。在说segment前，我们先要了解ES数据的存储和检索原理。

2.4.1 倒排索引

倒排索引从逻辑结构和基本思路上来讲非常简单。下面我们通过具体实例来进行说明，使得读者能够对倒排索引有一个宏观而直接的感受。

假设文档集合包含五个文档，每个文档内容下图所示，在图中最左端一栏是每个文档对应的文档编号。我们的任务就是对这个文档集合建立倒排索引。

中文和英文等语言不同，单词之间没有明确分隔符号，所以首先要用分词系统将文档自动切分成单词序列。这样每个文档就转换为由单词序列构成的数据流，为了系统后续处理方便，需要对每个不同的单词赋予唯一的单词编号，同时记录下哪些文档包含这个单词，在如此处理结束后，我们可以得到最简单的倒排索引：

“单词ID”一栏记录了每个单词的单词编号，第二栏是对应的单词，第三栏即每个单词对应的倒排列表。比如单词“谷歌”，其单词编号为1，倒排列表为{1,2,3,4,5}，说明文档集合中每个文档都包含了这个单词。

之所以说上图所示倒排索引是最简单的，是因为这个索引系统只记载了哪些文档包含某个单词，而事实上，索引系统还可以记录除此之外的更多信息：

单词ID：记录每个单词的单词编号；
单词：对应的单词；
文档频率：代表文档集合中有多少个文档包含某个单词
倒排列表：包含单词ID及其他必要信息
DocId：单词出现的文档id
TF：单词在某个文档中出现的次数
POS：单词在文档中出现的位置

以单词“加盟”为例，其单词编号为6，文档频率为3，代表整个文档集合中有三个文档包含这个单词，对应的倒排列表为{(2;1;<4>),(3;1;<7>),(5;1;<5>)}，含义是在文档2，3，5出现过这个单词，在每个文档的出现过1次，单词“加盟”在第一个文档的POS是4，即文档的第四个单词是“加盟”，其他的类似。

2.4.2 倒排索引的不变性

写到磁盘的倒序索引是不变的：写到磁盘后，倒排索引就再也不变。

这会有很多好处：

不需要添加锁。如果你从来不用更新索引，那么你就不用担心多个进程在同一时间改变索引。
因为不变，所以可以很好的做缓存。只要内核有足够的缓存空间，绝大多数的读操作会直接从内存而不需要经过磁盘。这大大提升了性能。
写一个单一的大的倒序索引可以让数据压缩，减少了磁盘I/O的消耗以及缓存索引所需的RAM。

然而，索引的不变性也有缺点。如果你想让新修改过的文档可以被搜索到，你必须重新构建整个索引。

我们来试想一下这样一个场景：对于一个索引内的所有文档，我们将其分词，建立了一个很大的倒排索引，并将其写入磁盘中。

如果索引有更新，那就需要重新全量创建一个索引来替换原来的索引。这种方式在数据量很大时效率很低，并且由于创建一次索引的成本很高，更无法保证时效性。

2.4.3 分段存储

如何在不丢失不变形的好处下让倒序索引可以更改？答案是：使用不只一个的索引。新添额外的索引来反映新的更改来替代重写所有倒序索引的方案。

为了解决这个问题，Lucene引入了段（segment）的概念，简单来说，一个段segment存储着若干个文档，以及这些文档的索引信息（如词频，词向量，域（field）索引等），也就是说，一个segment是一个完整的倒序索引的子集。

segment文件中存储的内容，可见【Lucene】Lucene 学习之索引文件结构

所以现在index在Lucene中的含义就是多个segments的集合。文档被成功存储的整个过程如下：

延迟写策略
- 如果每次将数据写入磁盘，磁盘的I/O消耗会严重影响性能。故而Lucene采用延迟写策略，新的文档建立时首先在内存中建立索引buffer：
Refresh
- 当达到默认的时间（1秒钟）或者内存的数据达到一定量时，会触发一次刷新（Refresh），将内存中的数据整合，生成到一个新的段。
- 此时，按理来说，应该将新生成的段刷进磁盘当中，但是将新的segment提交到磁盘需要fsync来保障物理写入。fsync是很耗时的，它不能在每次文档更新时就被调用，否则性能会很低。
- 在内存和磁盘之间是文件系统缓存，于是，ES先将新生成的段先写入到内核的文件系统缓存中，这个过程很轻量。
- 默认情况下每个分片会每秒自动refresh一次。可以通过参数index.refresh_interval来修改这个刷新间隔
- 我们也可以手动触发 refresh，
  - POST/_refresh 刷新所有索引。
  - POST/nba/_refresh刷新指定的索引。
- 在这个阶段，新生成的segment（下图灰色）虽然还未写入磁盘，但已经能够被搜索了，这也是es近实时搜索的原理。
Flush
- 新增的段被刷新到磁盘中。
- 段被写入到磁盘后会生成一个提交点，提交点是一个用来记录所有提交后段信息的文件。
- 一般Flush的时间间隔会比较久，默认30分钟，或者当translog（后文介绍）达到了一定的大小（超过512M），也会触发flush操作。

这里的内存使用的是ES的JVM内存，而文件缓存系统使用的是操作系统的内存。

新的数据会继续的被写入内存，但内存中的数据并不是以段的形式存储的，因此不能提供检索功能。由内存刷新到文件缓存系统的时候会生成了新的段，并将段打开以供搜索使用，而不需要等到被刷新到磁盘。

注意，在内存中的新文档不一定能够被索引，只有生成段后，新文档才可以被索引。

以上是新增文档操作，删除和更新操作过程有些类似：

删除，由于不可修改，所以对于删除操作，不会把文档从旧的段中移除，而是通过新增一个 .del文件，文件中会列出这些被删除文档的段信息。
- 这个被标记删除的文档仍然可以被查询匹配到，但它会在最终结果被返回前从结果集中移除。
更新，不能修改旧的段来进行反映文档的更新，其实更新相当于是删除和新增这两个动作组成。
- 会将旧的文档在 .del文件中标记删除，然后文档的新版本被索引到一个新的段中。
- 可能两个版本的文档都会被一个查询匹配到，但被删除的那个旧版本文档在结果集返回前就会被移除。

2.4.4 事务日志（Translog）

虽然通过延时写的策略可以减少数据往磁盘上写的次数，提升了整体的写入能力，但是我们知道文件缓存系统也是内存空间，属于操作系统的内存，只要是内存都存在断电或异常情况下丢失数据的危险。

为了避免丢失数据，Elasticsearch添加了事务日志（Translog），事务日志记录了所有还没有持久化到磁盘的数据。添加了事务日志后整个写索引的流程如下图所示。

一个新文档被索引（动词）之后，先被写入到内存中，但是为了防止数据的丢失，会追加一份数据到事务日志中。不断有新的文档被写入到内存，同时也会不断被记录到事务日志中。这时新数据还不能被检索和查询。
当达到默认的刷新时间或内存中的数据达到一定量后，会触发一次refresh，将内存中的数据以一个新段形式刷新到文件缓存系统中并清空内存。这时虽然新段未被提交到磁盘，但是可以提供文档的检索功能且不能被修改。
随着新文档索引不断被写入，当日志数据大小超过512M或者时间超过30分钟时，会触发一次flush。内存中的数据被写入到一个新段同时被写入到文件缓存系统，文件系统缓存中数据通过 fsync 刷新到磁盘中，生成提交点，日志文件被删除，创建一个空的新日志。
- 2.4.5 es写操作总结

先写入内存buffer，在buffer里的时候数据是搜索不到的；同时将数据写入translog日志文件。
如果buffer快满了，或者到一定时间，就会将内存buffer数据refresh 到一个新的segment file中，但是此时数据不是直接进入segment file磁盘文件，而是先进入os cache。这个过程就是 refresh。
每隔1秒钟，es将buffer中的数据写入一个新的segment file，每秒钟会写入一个新的segment file，这个segment file中就存储最近1秒内 buffer中写入的数据。

2.4.6 段合并

由于自动刷新流程（refresh）每秒会创建一个新的段，这样会导致短时间内的段数量暴增。而段数目太多会带来较大的麻烦，比如每一个段都会消耗文件句柄、内存和cpu运行周期。更重要的是，每个搜索请求都必须轮流检查每个段然后合并查询结果，所以段越多，搜索也就越慢。

Elasticsearch通过在后台定期进行段合并来解决这个问题。小的段被合并到大的段，然后这些大的段再被合并到更大的段。段合并的时候会将那些旧的已删除文档从文件系统中清除。被删除的文档不会被拷贝到新的大段中。合并的过程中不会中断索引和搜索。

段合并在进行索引和搜索时会自动进行，合并进程选择一小部分大小相似的段，并且在后台将它们合并到更大的段中，这些段既可以是未提交的也可以是已提交的。合并结束后老的段会被删除，新的段被 flush 到磁盘，同时写入一个包含新段且排除旧的和较小的段的新提交点，新的段被打开可以用来搜索。

段合并的计算量庞大，而且还要吃掉大量磁盘 I/O，段合并会拖累写入速率，如果任其发展会影响搜索性能。Elasticsearch在默认情况下会对合并流程进行资源限制，所以搜索仍然有足够的资源很好地执行。

参考资料

ElasticSearch Master选举机制浅析

Posted on 2020-02-18 | In 中间件 , ElasticSearch |

Words count in article: 2k | Reading time ≈ 8

前言

在ElasticSearch集群中，master负责处理集群层面配置的变更和同步工作，所有yml文件配置node.master: true的节点都有资格经过选举成为master节点

es集群的master选举采用Bully算法

Bully算法

Leader选举的基本算法之一。

它假定所有节点都有一个惟一的ID，该ID对节点进行排序。任何时候的当前Leader都是参与集群的最高id节点。

具体来说，Bully算法要求每个节点都投票给ID最高的那个节点，通过这一强制性的条件，让集群非常简单的协调一致。

该算法的优点是易于实现，但是，当拥有最大ID的节点处于不稳定状态的场景下会有问题，例如Master负载过重而假死，集群拥有第二大ID的节点被选为新主，这时原来的Master恢复，再次被选为新主，然后又假死…

而且该算法会有脑裂的问题。

elasticsearch通过控制触发时机来解决反复去世的问题，即当前的Master失效才会触发选举。

同时es又要求法定得票人数过半才能选出master，以此来解决脑裂。

es实际上是从具有master资格的节点中选id最小的节点作为master，而不是id最大的节点

选举触发时机

集群启动：
- 后台启动线程去ping集群中的节点，按照上述策略从具有master资格的节点中选举出master
Master失效
- 非Master节点运行的MasterFaultDetection检测到Master失效，在其注册的listener中执行handleMasterGone，执行rejoin操作，重新选主。注意，即使一个节点认为Master失效，也会进入选主流程。

我们需要在候选集群中的节点的配置文件中设置参数 discovery.zen.munimum_master_nodes的值，这个参数表示在选举主节点时需要参与选举的候选主节点的节点数，默认值是1，官方建议取值 (master_eligibel_nodes/2)+1，其中 master_eligibel_nodes为候选主节点的个数。

这样做既能防止脑裂现象的发生，也能最大限度地提升集群的高可用性，因为只要不少于discovery.zen.munimum_master_nodes个候选节点存活，选举工作就能正常进行。当小于这个值的时候，无法触发选举行为，集群无法使用，不会造成分片混乱的情况。

选举过程

Master选举主要逻辑在ZenDiscovery.findMaster（基于es 5.2版本）中：

开始

1 2	private DiscoveryNode findMaster() { logger.trace("starting to ping");

每个节点ping集群下的其他节点，等待所有节点的返回。

//pingAndWait用于获取其他节点的状态，这里只介绍下大致实现，不再展开具体源码：
//pingAndWait主要是使用上面介绍的ZenPing去ping配置中的所有host
//通过函数名称可以知道这是个同步调用，同步的具体实现和ElasticSearch大部分需要等待
//远程通信返回的行为类似，采用计数器记录发送的请求个数，每次有请求响应时递减计数器，
//当计数器递减为0时表示所有请求都得到了响应。
List<ZenPing.PingResponse> fullPingResponses = pingAndWait(pingTimeout).toList();
if (fullPingResponses == null) {
	logger.trace("No full ping responses");
	return null;
}
if (logger.isTraceEnabled()) {
	StringBuilder sb = new StringBuilder();
	if (fullPingResponses.size() == 0) {
		sb.append(" {none}");
	} else {
		for (ZenPing.PingResponse pingResponse : fullPingResponses) {
			sb.append("\n\t--> ").append(pingResponse);
		}
	}
	logger.trace("full ping responses:{}", sb);
}
	
final DiscoveryNode localNode = clusterService.localNode();
	
// add our selves
assert fullPingResponses.stream().map(ZenPing.PingResponse::node)
	.filter(n -> n.equals(localNode)).findAny().isPresent() == false;
//在获取的装填集中加入当前节点自己的状态，因为自己也需要加入选举，也可能被选举为主节点
fullPingResponses.add(new ZenPing.PingResponse(localNode, null, clusterService.state()));

根据其他节点的返回，过滤掉没有资格参加选举的节点

1
2
3

// filter responses
// 过滤PingResponse, 排除掉client节点，单纯的data节点
final List<ZenPing.PingResponse> pingResponses = filterPingResponses(fullPingResponses, masterElectionIgnoreNonMasters, logger);

根据反馈，收集当前集群已经存在的master塞入activeMasters

//activeMasters用来记录当前已经存在的主节点
List<DiscoveryNode> activeMasters = new ArrayList<>();
for (ZenPing.PingResponse pingResponse : pingResponses) {
	// We can't include the local node in pingMasters list, otherwise we may up electing ourselves without
	// any check / verifications from other nodes in ZenDiscover#innerJoinCluster()
	//如果返回的信息表明自己当前已经是主节点，那么不会把自己加入到activeMasters中去
	if (pingResponse.master() != null && !localNode.equals(pingResponse.master())) {
		activeMasters.add(pingResponse.master());
	}
}

根据反馈，收集当前集群已经存在的具有选举资格的node塞入masterCandidates

	
// nodes discovered during pinging
//masterCandidates用来记录配置为可以成为主节点的候选节点
List<ElectMasterService.MasterCandidate> masterCandidates = new ArrayList<>();
//这里将返回节点中配置为可以作为主节点的节点加入候选节点中
for (ZenPing.PingResponse pingResponse : pingResponses) {
	//这里要注意isMasterNode并不是说明该节点是不是主节点，而是表明该节点能不能成为主节点
	if (pingResponse.node().isMasterNode()) {
		masterCandidates.add(new ElectMasterService.MasterCandidate(pingResponse.node(), pingResponse.getClusterStateVersion()));
	}
}

如果集群中已经有master，那么加入它，否则，开始选举

//如果当前存在的主节点列表activeMasters为空，则从候选节点列表masterCandidates中选取主节点
if (activeMasters.isEmpty()) {
	//判断是否有足够的候选节点
	if (electMaster.hasEnoughCandidates(masterCandidates)) {
		//进行节点选举
		final ElectMasterService.MasterCandidate winner = electMaster.electMaster(masterCandidates);
		logger.trace("candidate {} won election", winner);
		return winner.getNode();
	} else {
		// if we don't have enough master nodes, we bail, because there are not enough master to elect from
		logger.trace("not enough master nodes [{}]", masterCandidates);
		return null;
	}
} else {//activeMasters不为空，表示当前集群已经有master了
	assert !activeMasters.contains(localNode) : "local node should never be elected as master when other nodes indicate an active master";
	//如果当前存在的主节点列表activeMasters不为空，则从中选取主节点
	// lets tie break between discovered nodes
	return electMaster.tieBreakActiveMasters(activeMasters);
}

如果集群中现在没有master，那么选出master

选举主要算法集中在electMaster.electMaster()方法中，我们来看下：

/**
 * Elects a new master out of the possible nodes, returning it. Returns <tt>null</tt>
 * if no master has been elected.
 */
public MasterCandidate electMaster(Collection<MasterCandidate> candidates) {
	//保证有足够的候选者，逻辑是判断有资格参选的node数量大于yml配置的minimumMasterNodes
	assert hasEnoughCandidates(candidates);
	List<MasterCandidate> sortedCandidates = new ArrayList<>(candidates);
	//对候选者进行排序，
	sortedCandidates.sort(MasterCandidate::compare);
	//取队首的node即为master
	return sortedCandidates.get(0);
}

/**
 * compares two candidates to indicate which the a better master.
 * A higher cluster state version is better
 *
 * @return -1 if c1 is a batter candidate, 1 if c2.
 */
public static int compare(MasterCandidate c1, MasterCandidate c2) {
	// we explicitly swap c1 and c2 here. the code expects "better" is lower in a sorted
	// list, so if c2 has a higher cluster state version, it needs to come first.
	//先根据节点的clusterStateVersion比较，clusterStateVersion越大，优先级越高。
	//这是为了保证新Master拥有最新的clusterState(即集群的meta)，避免已经commit的meta变更丢失。
	//因为Master当选后，就会以这个版本的clusterState为基础进行更新。
	int ret = Long.compare(c2.clusterStateVersion, c1.clusterStateVersion);
	if (ret == 0) {
		//clusterStateVersion相同时，进入compareNodes，其内部按照节点的Id比较(Id为节点第一次启动时随机生成)
		ret = compareNodes(c1.getNode(), c2.getNode());
	}
	return ret;
}

	
/** master nodes go before other nodes, with a secondary sort by id **/
 private static int compareNodes(DiscoveryNode o1, DiscoveryNode o2) {
 	//isMasterNode方法是判断该节点yml文件是否配置了data.master=true，即是否有资格参选
	//有资格参选的优先（其实从findMaster进入这里，所有的node都是有资格的）
	if (o1.isMasterNode() && !o2.isMasterNode()) {
		return -1;
	}
	if (!o1.isMasterNode() && o2.isMasterNode()) {
		return 1;
	}
	//根据id排序升序排序
	return o1.getId().compareTo(o2.getId());
}

如果集群中已经有master，找到这个master

/** selects the best active master to join, where multiple are discovered */
public DiscoveryNode tieBreakActiveMasters(Collection<DiscoveryNode> activeMasters) {
	//同理，也是默认id最小的node就是master
	return activeMasters.stream().min(ElectMasterService::compareNodes).get();
}

选举过程简图

Raft算法分析

Posted on 2020-01-21 | In 分布式算法&理论 , 分布式事务和数据一致性 |

Words count in article: 4.8k | Reading time ≈ 17

前言

在了解Ratf算法前，我们需要了解如下的一些概念名词：

状态机复制 (State Machine Replication)
- 在分布式系统设计中，需要遵循CAP理论，如果我们要让一个服务具有容错能力，那么会让一个服务的多个副本同时运行在不同的节点上。此时，状态的改变就需要在各个副本之间做同步，实现这种同步方法就是所谓的状态机复制（State Machine Replication）。
- 状态机复制的理论基础是：如果集群里的每一个节点上都运行着相同的确定性状态机S，并且所有的状态机刚开始都处于同样的初始状态s0，那么给予这些状态机相同的输入序列: {i1, i2, i3, i4, i5, i6, …, in}, 这些状态机必然会经过相同的状态转换路径: s0->s1->s2->s3->…->sn最终达到相同的状态sn, 同时生成相同的输出序列 {o1(s1), o2(s2), o3(s3), …, on(sn)}。（典型的例子就是Redis的AOF和MySQL集群的binlog）
- 在执行输入序列I的过程中，根据同步方式的不同，系统就有了强一致性和最终一致性。如果我们要求对于序列I中的每一个in, 都需要所有的服务副本确认执行了in，才能执行in+1，那么这个系统就是强一致性的系统。如果我们取消掉这个限制，仅仅要求所有的服务副本执行相同的输入序列I，但是完全各自独立执行，而不需要在中间同步，那么就有了最终一致性（各服务都会达到相同的最终状态，但是达到的时间不确定）。
拜占庭将军问题
- 问题很简单，拜占庭帝国要攻打一个城池，兵分多路，城池很难攻下，要多路军队同时进攻才能攻下，为了完成目标，各路的将军需要通过信使来约定一个攻打的时间，而信使有可能死亡或者叛变（传递假消息）。
- 基于以上的问题，我们需要在行动时达成共识。互联网上，每台计算机都是一个个完全相等的节点，只能靠通信来协调，没有权威背书或信任，是一个急需解决的问题。

拜占庭将军问题的本质：如何让众多完全平等的节点针对某一状态达成共识。

Raft算法

拜占庭将军问题是分布式领域最复杂、最严格的容错模型。但在日常工作中使用的分布式系统面对的问题不会那么复杂，更多的是计算机故障挂掉了，或者网络通信问题而没法传递信息，这种情况不考虑计算机之间互相发送恶意信息，极大简化了系统对容错的要求，最主要的是达到一致性。

所以将拜占庭将军问题根据常见的工作上的问题进行简化：假设将军中没有叛军，信使的信息可靠但有可能被暗杀的情况下，将军们如何达成一致性决定？

对于这个简化后的问题，有许多解决方案，第一个被证明的共识算法是 Paxos，由拜占庭将军问题的作者 Leslie Lamport 在1990年提出，最初以论文难懂而出名，后来这哥们在2001重新发了一篇简单版的论文 Paxos Made Simple，然而还是挺难懂的。

因为 Paxos 难懂，难实现，所以斯坦福大学的教授在2014年发表了新的分布式协议 Raft。与 Paxos 相比，Raft 有着基本相同运行效率，但是更容易理解，也更容易被用在系统开发上。paxos见我的另一篇文章分布式一致性理论和paxos算法

Raft算法主要分为如下几个关键步骤：

leader选举：
- Raft开始时在集群中选举出Leader负责日志复制的管理；
日志复制：
- Leader接受来自客户端的事务请求（日志），并将它们复制给集群的其他节点，然后负责通知集群中其他节点提交日志，Leader负责保证其他节点与他的日志同步。
故障转移：
- 当Leader宕掉后集群其他节点会发起选举选出新的Leader；

raft算法有如下特点：

强leader语义：
- 相比其他一致性算法，Raft使用增强形式的leader语义。举个例子，日志只能由leader复制给其它节点。这简化了日志复制需要的管理工作，使得Raft易于理解。
leader的选择：
- Raft使用随机计时器来选择leader，它的实现只是在心跳机制(任何一致性算法中都必须实现)上多做了一点“文章”，不会增加延迟和复杂性。
关系改变：
- Raft使用了一个新机制joint consensus允许集群动态在线扩容，保障Raft的可持续服务能力。

1 Ratf名词速览

1.1 Raft节点状态

从拜占庭将军的故事映射到分布式系统上，每个将军相当于一个分布式网络节点，每个节点有三种状态：Follower（跟随者），Candidate（候选者），Leader（领导者），状态之间是互相转换的，可以参考下图，具体的后面说。

1.2 term任期

从上面可以看出，哪个节点做leader是大家投票选举出来的，每个leader工作一段时间，然后选出新的leader继续负责。这和民选社会的选举很像，每一届新的履职期称之为一届任期，在raft协议中，也是这样的，对应的术语叫term。

上图蓝色表示选举期，绿色表示履职期。

每个任期都有一个对应的整数与之关联，称为“任期号”，任期号用单词“Term”表示，这个值是一个严格递增的整数值。

如果一个candidate在一次选举中赢得leader，那么这个节点将在这个任期中担任leader的角色。但并不是每个任期都一定对应有一个leader的，比如上面的t3中，可能在选举超时到来之前都没有产生一个新的leader，那么此时将递增任期号开始一次新的选举。

2. Raft算法流程

2.1 leader选举

2.1.1 心跳机制

raft算法是使用心跳机制来触发leader选举的。

在节点刚开始启动时，初始状态是follower状态。一个follower状态的节点，只要一直收到来自leader或者candidate的正确RPC消息的话，将一直保持在follower状态。

leader节点通过周期性的发送心跳请求（一般使用带有空数据的AppendEntries RPC来进行心跳）来维持着leader节点状态。

2.1.2 选举超时（election timeout）

每个follower有一个选举超时（election timeout）定时器，这个定时器的值，对于每个节点都是不同的，其值在150ms到300ms之前随机。

如果某个节点在这个定时器超时之前都没有收到来自leader的心跳请求，那么该follower将认为当前集群中没有leader了，它会改变自己的状态为candidate，如下图Node A。然后开启一个新的term，节点本地的任期号term+1。

2.1.3 请求投票（RequestVote）

成为candidate的节点，会先投自己一票，然后并行给其他节点发送请求投票的消息RequestVote RPCs

那么一个节点在接收到RequestVote RPCs时，它会遵循以下约束来决定是否将票投给请求的发送者。

在任一任期内，单个节点最多只能投一票
候选人知道的信息不能比自己的少（这一部分，后面介绍log replication和safety的时候会详细介绍）
first-come-first-served 先来先得

如果一个节点在接收到RequestVote RPCs时，上述约束都满足，那么他将投发送者一票，重置自己的election timeout，并给予响应。

2.1.4 票仓分布

对于一个candidate而言，它发出了请求RequestVote RPCs后，就开始等待其他节点的回复，这时可能会有三种结果：

全局就它一个candidate，其他的节点election timeout还没结束就接到了它的RequestVote RPCs，那么这时，这个candidate无疑会获得大多数票，成为新的leader。
有多个节点或先后或同时成为了candidate，但基于“每个节点一个任期内只能投一票”和“先到先得”的约束，以及请求的通信时间的随机性，还是有一个candidate运气好，获得了超过半数的票。

那么这个新的leader胜选后，会广播心跳，其他candidate发现心跳中携带的term信息不低于自己，知道有已经有leader被选举出来了，于是放弃选举，转换成follower。

有多个节点或先后或同时成为了candidate，但票数分布均匀，没有任何节点获得超过半数的票（这种情况称作split vote）。
- 此时所有的candidate都在等待能使自己选票超过半数的响应，等啊等，直到超时后重新发起选举。
- 如果出现split vote的情况，那么就延长了系统不可用的时间（没有leader是不能处理客户端写请求的），因此raft才引入randomized election timeouts来尽量避免平票情况。同时，leader-based 共识算法中，节点的数目都是奇数个，尽量保证majority的出现。

2.1.5 诞生leader

一个leader诞生以后，就像我们在前文2.1.1 心跳机制所述的那样，在这个新的任期内每隔heartBeat timeout时间，不停的向follower发送心跳请求（append entries）。

而每个follower则维持着自己的election timeout计时器，如果election timeout时间内没有收到来自leader的心跳，那么说明leader故障。将自己变成candidate，并开始下次选举。

2.2 日志复制（Log Replication）

前文我们说过了状态机复制(State Machine Replication)，状态机复制有多种实现，在Raft中，也有一套基于Append-Only Log的状态机复制实现。

Raft 是分布式一致性算法，保证的实际上是多台机器上数据的一致性。前面讨论的 leader 选举，其实都是为了保证日志复制的一致性而做的前提。Raft的状态机复制实现，我们称作日志复制（Log Replication）。

Leader 选举只是为了保证日志相同的辅助工作。实际上，在更为学术的 Paxos 里面，是没有 leader 的概念的（大部分 Paxos 的实现通常会加入 leader 机制提高性能）。

这里的日志，指的是命令日志，对于客户端发来的命令请求，leader会将其封装成一个Log Entry作为传输的载体。

在 Raft 中，leader会接收客户端的所有需求（follower会将写请求转发给leader），leader会将数据以Log Entry的方式通过AppendEntries RPC同步给所有followers

只要超过半数以上的follower反馈成功（返回ack），这条日志就成功提交了。如果RPC请求超时，leader就不停的进行AppendEntries RPC重试。

简单来说，保证复制日志相同，才是分布式一致性算法的最终任务。

2.2.1 Log和Log Entry

Raft中每个节点，都会维护一个本地Log数组，其数据结构如下图：

其构成有：

创建日志时的任期号（用来检查节点日志是否出现不一致的情况）
状态机需要执行的指令（真正的内容）
索引：整数索引，表示日志条目在日志数组中位置

上图显示，共有 8 条日志，提交了 7 条。提交的日志都将通过状态机持久化到磁盘中，防止宕机。

2.2.2 一致性校验

然后谈谈主从日志的一致性问题，这个是分布式一致性算法要解决的根本问题。

Raft 主从日志的一致性，这个最终的目标，可以分解成一个假设和一个充分条件。

我们可以假设：如果在不同的日志中的两个日志条目的任期号 和 索引下标 相同，那么他们的指令就是相同的。

leader 最多在一个任期里的一个日志索引位置创建一条日志条目，而所有follower的日志来源都是leader，日志条目在日志的位置从来不会改变，所以基本上可以用任期号和索引下标当做Log Entry的主键
那么，主从日志一致性的充分条件可以是：如果在不同节点的日志里，任意2个拥有相同的任期号和索引的日志条目，他们之前的日志项都是相同的，那么这些节点的日志就都是一致的。

达成了上述的这个充分条件，就达成了主从日志一致的最终条件，那如何达成这个充分条件呢？Raft引入了一种一致性校验约束。

每次 RPC 发送附加日志时，leader 会把当前这条日志Entry的前一个日志Entry的下标和任期号一起发送给 follower，如果 follower 发现发来前一个日志Entry的下标和任期号和自己队尾的日志Entry不匹配，那么就拒绝接受这条日志，这个称之为一致性校验

如果每一步都严格遵守该校验，就达成了主从日志一致的最终条件。

2.2.3 日志复制过程

有了这个一致性校验，我们再反过头来看下日志复制的过程。

在Raft协议中有两个主要的消息，一个是在第二节讲到的RequestVote RPC，用于选主投票时leader发出的消息。一个就是AppendEntries RPC，用于心跳和日志复制。对于心跳，只需要发送空内容的AppendEntries RPC就可以了，我们主要关注日志复制的消息，看看Raft是怎么操作的。

leader接受客户端的操作请求，如“将X赋值为3”。
- 假如leader当前的任期为term1，那么leader就会向自己本地log的最后添加一个entry，比如索引为K，内容为“term1：X赋值为3”。
leader向集群中其他follower并行发送AppendEntries RPC消息。这个消息里面包含：
1. 这个新的entry和索引，即“term1：X赋值为3”和K。
2. 前一个entry的内容和索引，比如“term1：Y赋值为2”和K-1。
当一个follower收到一个AppendEntries RPC消息时，会查看自己本地的log中的K-1位置的entry的内容。（一致性校验）
- 假如本地log中K-1位置的entry内容与接收到的来自leader的K-1的entry内容一致（下标和任期号一致），那么就将leader发来的K位置的entry保存在自己的K位置（当然要做并发控制），并返回true，告诉leader保存成功了
- 假如本地log中K-1位置的entry内容与接收到的来自leader的K-1的entry内容不一致（下标和任期号不一致），那么就返回false，告诉leader不一致。
leader收到消息。
- 如果得到的反馈为true，即某个follower保存成功了，那么这个Log Entry的复制完成。
- 否则，见下文2.2.4 特殊情况的日志复制过程。
leader得到了超过半数的follower反馈的true消息，leader会执行这条Log Entry中的命令，并反馈客户端该命令已经提交，同时向其他follower广播这条Log Entry被commit的消息。
follower接收到Log Entry被commit的消息，执行该Log Entry中的命令。在当前日志被提交的过程中，如果leader先前的某些日志还没有被提交，则将会一同提交。

在Raft中，一切以leader为主。因此本地日志不是最新的话，就不能成为leader。因此在选主的时候，会进行日志比较。假如在投票阶段，一个follower收到的选主请求中，包含的日志信息比自己的要旧，那么也会拒绝给这个请求投赞成票。如何比较新旧呢？一是看任期term，一是看最后一个entry的索引号。任期大的新，任期相同的索引大的新。

2.2.4 特殊情况的日志复制过程

上面说的都是日志在正常情况下的表现，没有考虑到一些异常情况。

即，正常情况下，leader和follower的日志保持一致性，所以附加日志 RPC 的一致性检查从来不会失败。但如果我们将leader或者follower崩溃的情况考虑进来，那么将可能会出现三种情况：

follower缺失当前leader上存在的日志条目。如a，b
follower存在当前leader不存在的日志条目。如c，d(比如旧的leader仅仅将AppendEntries RPC消息发送到一部分follower就崩溃掉，然后新的当选leader的服务器恰好是没有收到该AppendEntries RPC消息的服务器)
或者follower即缺失当前leader上存在的日志条目，也存在当前leader不存在的日志条目。如e，f

这种情况如何处理呢？

Raft 给出了一个方案（补丁）

强制follower直接复制leader的日志（意味着follower中的和leader冲突的日志将被覆盖）。

要使得follower的日志和leader进入一致状态，leader必须找到follower最后一条和leader匹配的日志，然后从这条日志开始，用leader的日志条目，覆盖follower的日志条目

依据这个方案，上图中的 a follower和b follower从队尾直接复制即可。c follower最后一个条目将被覆盖，d follower最后2个任期为7的条目将被覆盖，e最后2个任期为4的条目将被覆盖，f 则比较厉害，需要覆盖下标为3之后的所有条目。

实现逻辑如下：

leader向集群中的follower发送AppendEntries RPC，内容为最新的Log Entry和其索引K，以及前一个Log Entry及其索引K-1，这里不再赘述。
一致性检验失败，follower向leader反馈false。
leader会将K自减1，然后再次重新发AppendEntries RPC给失败的follower，直到follower返回true。那么此时的K，就是follower最后一条和leader匹配的日志的下标。

最坏的情况是K=0时才得到true回复，这表示follower的Log和leader完全不一致。K=0得到的回复一定是true，因为没有K-1了

此时leader将匹配的位置和最新的位置中间的内容都发送给follower，follower会将接收到的内容，并覆盖到对应的位置。

实际上leader对每个follower都维护了一个nextIndex字段，来存上述过程中一直递减的K值，描述中我没有引入nextIndex字段的概念，力求精简，以便理解。

参考资料

状态机复制 (State Machine Replication)
Raft算法详解

Raft算法原理
 Raft算法之日志复制

Raft协议详解（一）前言：子问题分解

Raft 日志复制 Log replication

Redis事件模型/主从复制/哨兵模型/集群模式

Posted on 2020-01-08 | In 中间件 , Redis |

Words count in article: 15.1k | Reading time ≈ 55

1. Redis的事件模型

Redis服务器需要处理两类事件：文件事件和时间事件。

1.1 文件事件

Redis服务器通过套接字与客户端进行连接，而文件事件就是服务器对套接字操作的抽象。

Redis基于Reactor模式开发了网络事件处理器，由四部分组成：套接字、I/O多路复用程序、文件事件分派器以及事件处理器。

套接字：当有一个套接字准备好执行连接应答、写入、读取、关闭等操作时，就会产生一个文件事件（多个套接字就会有多个文件事件产生；
- 事件类型有AE_READABLE和AE_WRITABLE
  - 如果客户端对套接字执行write或close操作，或者客户端对服务端的监听套接字执行connect操作，那么产生一个AE_READABLE事件。
  - 如果客户端对套接字执行read操作，那么产生一个AE_WRITABLE事件。
  - 如果一个事件既可读又可写，则先处理AE_READABLE事件，再处理AE_WRITABLE事件。
I/O多路复用程序：负责监听多个套接字，并向文件事件分派器传送产生事件的套接字。
- I/O多路复用程序会将产生的所有事件的套接字放在一个队列中，以有序（sequentially）、同步（synchronously）、每次一个的方式向文件事件分派器传送套接字，只有一个套接字的事件处理完成后才会再发下一个：
- I/O多路复用的功能是evport、epoll、kqueue和select这些常见的I/O多路复用函数的包装。Redis会在编译时自动选择系统中性能最高的I/O多路复用函数。默认实现是epoll。关于I/O多路复用可见本博客文章《详解IO多路复用和其三种模式——select/poll/epoll》
文件事件分派器
- 接收I/O多路复用程序传来的套接字，根据套接字产生的事件类型，调用相应事件处理器
文件事件处理器
- 连接应答处理器：acceptTCPhandler
  - 对连接服务器的各个客户端进行应答
  - Redis初始化时，将监听套接字的AE_READABLE事件与该处理器关联
  - 客户端连接服务器时，监听套接字产生AE_READABLE事件，触发该处理器执行。
  - 服务器将会创建一个redisClient结构的实例，并添加进自身的RedisServer结构的clients链表中。
  - 处理器对客户端请求进行应答，并创建客户端套接字，将客户端套接字的AE_READABLE事件与命令请求处理器关联。
- 命令请求处理器：readQueryFromClient
  - 接收客户端传来的命令请求
  - 客户端成功连接服务器后，连接应答处理器将该客户端套接字的AE_READABLE事件与命令请求处理器关联
  - 客户端向服务器发送命令请求时，客户端套接字产生AE_READABLE事件
  - 命令请求处理器读取命令内容，传给相关程序执行。
- 命令回复处理器：sendReplyToClient
  - 向客户端返回命令执行结果
  - 服务器有命令执行结果要传送给客户端时，将客户端套接字的AE_WRITABLE事件始终与该处理器关联
  - 客户端准备好接收命令执行结果时，客户端套接字产生AE_WRITABLE事件，触发命令回复处理器执行。
  - 将全部回复写入套接字后，关联解除

1.2 时间事件

一个时间事件包括三要素：

id
- 时间时间的全局唯一表示，新事件id大于旧事件。
when
- 毫秒精度的unix时间戳，记录了时间事件的到达时间。
timeproc（时间事件处理器）
- 时间事件处理器，一个函数，时间事件到达时，服务器调用对应处理器来执行。

时间事件分为两类：

定时事件：让一段程序在指定时间后执行一次。
- 定时事件的处理器返回值是固定的数值，存在ae.h/AE_NOMORE中，如果一个事件的返回为该值，那么该事件在到达一次后，就会被删除
周期事件：让一段程序每隔一段指定时间就执行一次。
- 周期事件的处理器返回值是非ae.h/AE_NOMORE的值，这时，返回值会覆写when值。让这个时间过一段时间再次到达，以此类推。

服务器将时间事件都放在一个无序链表中（不是按时间顺序排序，而是按照ID排序，新产生的时间事件放在链表的表头），每次时间事件执行器运行时，processTimeEvents函数遍历整个链表，查找所有已经到达的时间事件，并调用相应的事件处理器。

1.2.1 serverCron函数

时间时间最典型的实例就是serverCron函数，它平均100毫秒执行一次，负责Redis定期对自身资源和状态的调整，包括：

更新服务器的统计信息：时间，内存，数据库占用情况
清理过期键值对
关闭失效的连接
尝试进行aof\rdb持久化操作
对从服务器进行定期同步
集群模式下的定期同步，连接测试

1.3 事件调度与执行

aeProcessEvents函数负责何时处理文件事件、何时处理时间事件，以及花费多久的时间

将aeProcessEvents函数放置在循环中，加上初始化、清理函数，就构成了redis服务器的主函数

文件事件和时间事件是合作关系，服务器会轮流处理这两种事件，并且处理过程中也不会抢占线程。因此时间事件的实际处理时间要比设定的时间晚一些。

2. Redis主从复制

关系数据库通常会使用一个主服务器向多个从服务器发送更新，并使用从服务器来处理所有的读请求，Redis采用了同样方法来实现自己的复制特性。

2.1 旧版复制功能

Redis 2.8以前采用的复制都为旧版复制，主要使用SYNC命令同步复制，SYNC存在很大的缺陷严重消耗主服务器的资源以及大量的网络连接资源。Redis 2.8之后采用PSYNC命令替代SYNC，解决完善这些缺陷，但在介绍新版复制功能之前，必须先介绍旧版复制过程，这样才能更好地形成对比。

复制功能有两种模式，分为同步sync与命令传播（command propagate），两个过程配合执行才能实现Redis复制。

SYNC命令同步操作
- 通过从服务器发送到SYNC命令给 主服务器
- 主服务器 执行BGSAVE命令，在后台生成RDB文件，并从现在开始将所有写命令记录进缓冲区
- 并发送给 从服务器，同时发送缓冲区保存的所有写命令给 从服务器。
- 从服务器 清空之前数据并执行解释RDB文件，然后执行缓冲区的写命令。
- 保持数据基本一致（还需要命令传播过程才能保持一致）
命令传播操作：
- 在同步之后，主服务器 仍然在不断的接受写命令，这会导致好不容易一致的主从状态再次不一致。
- 通过发送让主从服务器不一致的命令（主服务器接收到的新写命令）给从服务器并执行，让主从服务器的数据库重新回到一致状态。

SYNC命令的缺陷：如果因为网络问题，导致主从断开链接一段时间，那么重新同步的时候， SYNC无法做到断点继续，而是仍要清空之前数据，并重新开始复制操作。

SYNC命令非常消耗资源，原因有三点：

主服务器执行BGSAVE命令生成RDB文件，这个生成过程会大量消耗主服务器资源（CPU、内存和磁盘I/O资源）
主服务器需要将自己生成的RBD文件发送给从从服务器，这个发送操作会消耗主从服务器大量的网络资源（带宽与流量）
接收到RDB文件你的从服务器需要载入RDB文件，载入期间从服务器会因为阻塞而导致没办法处理命令请求。

2.2 新版复制功能

为了解决旧版本中断线情况下SYNC低效问题，在Redis 2.8之后使用PSYNC命令代替SYNC命令执行复制同步操作，自然PSYNC具备完整重同步和部分重同步模式

完整重同步：跟旧版复制基本是一致的，可以理解为“全量”复制。
部分重同步：在命令传播阶段，断线重复制只需要发送主服务器在断开期间执行的写命令给从服务器即可，可以理解为“增量”复制。

2.3 复制的实现

Redis不管是旧版还是新版，复制的实现都可以分为七个步骤，流程图如下：

设置主服务的地址与端口
- 当客户端向从服务器发送一下命令时或者在配置文件中配置slaveof选项
- 127.0.0.1:12345> SLAVEOF 127.0.0.1 6379
建立套接字连接
- 从服务器根据设置的套接字创建连向主服务器的套接字连接
- 主服务器接收从服务器的套接字连接之后，为该套接字创建响应的客户端状态，并将此时的从服务器看做是主服务器的客户端，也就是该从服务器同时具备服务器与客户端两个身份。
发送PING命令
- 从服务器成为主服务器的客户端之后，做的第一件事就是向主服务器发送PING命令。PING命令主要有两种作用：
  1. 虽然建立了套接字连接，但是还未使用过，通过发送PING命令检查套接字的读写状态是否正常
  2. 通过发送PING命令检查主服务器能否正常处理命令请求
- 从服务器在发送PING命令之后将遇到以下三种情况的其中一种：
身份验证
- 从服务器接收到主服务器返回的“PONG”回复，接下来就需要考虑身份验证的事。
发送端口信息
- 在身份验证步骤之后，从服务器将执行命令REPLCONF listening-port <port>，向主服务器发送从服务器的监听端口号。
同步
- 就是上述所指的同步操作，从服务器向主服务器发送PSYNC命令，执行同步操作，值得注意的是开始只有从服务器是主服务器的客户端，但是执行同步操作之后，主服务器也会成为从服务器的客户端。
命令传播
- 主从服务器就会进入命令传播阶段，主服务器只要将自己执行的写命令发送给从服务器，而从服务器只要一直执行并接收主服务器发来的写命令（上述已经介绍过，这里不过多介绍）

3. Redis哨兵模型

Sentinel(哨兵、哨岗)是Redis 的高可用性的解决方案：有一个或多个Sentinel实例组成的Sentinel系统可以监视任意多个主服务器，以及这些主服务器属下的所有从服务器，并在被监视的主服务器进入下线状态时，自动将下线主服务器属下的某个从服务器升级为主服务器，然后由新的主服务器代替已下线的主服务器继续处理命令请求。

在替换了新的主服务器之后，如果之前下线的主服务器上线了，就会被降为新的主服务器的从服务器。

3.1 Sentinel的启动

1
2
3

$ redis-sentinel /path/to/your/sentinel.conf
或者
$ redis-sentinel /path/to/your/sentinel.conf --sentinel

这两个命令都能启动Sentinel，效果都是一样的。

Sentinel启动后，会有五个步骤：

初始化服务器
- Sentinel的本质是一个运行在特殊模式下的Redis服务器，因此启动时必须对其进行初始化，但是由于Sentinel与普通的服务器不同，它的初始化需要执行的操作也不同。
- 下表是Sentinel 模式下Redis服务器的主要功能的使用情况
使用Sentinel专用代码
- 启动Sentinel的第二步，就是将普通Redis服务器使用的代码替换成Sentinel专用的代码。
- 比如普通Redis服务器使用 redis.h/REDIS_SERVERPORT常量作为服务端口(#define REDIS_SERVERPORT 6379),使用 redis.h/redisCommandTable 作为服务器的命令表。
- 而Sentinel使用 reids.h/REDIS_SENTINEL_PORT 常量作为服务器端口，默认26379，使用 redis.h/sentinelcmds 作为服务器的命令表

初始化Sentinel状态

接下来，服务器会初始化一个 sentinel.c/sentinelState 结构(简称“Sentinel状态”)，这个结构保存了服务器所有和Sentinel功能有关的状态，服务器的一般状态仍然由 redis.h/redisServer 结构保存：

typedef struct sentinelState{
	// 当前纪元，用于实现故障转移
	uint64_t current_epoch;
	// 保存了所有被这个 Sentinel监视的主服务器
	// 字典的键是主服务器的名字
	// 字典的值是一个指向 sentinelRedisInstance 结构的指针
	dict *masters;
	// 是否进入了 TILT 模式
	int tilt;
	// 目前正在执行的脚本数量
	int running_scripts;
	// 进入 TILT 模式的时间
	mstime_t tilt_start_time;
	// 最后一次执行事件处理器的时间
	mstime_t previous_time;
	// 一个 FIFO 队列，包含了所有需要执行的用户脚本
	list *scripts_queue;
}sentinel;

初始化Sentinel状态的 masters 属性

接下来要做的是将sentinel状态的 masters 属性进行初始化，上面已经说过了，masters 里面保存的是所有被监视的主服务器的信息。master属性是字典，键是主服务器的名字，值是一个指向 sentinelRedisInstance 结构的指针。

我们先介绍一下 sentinelRedisInstance 结构(简称“实例结构”)，这个结构代表着一个被Sentinel监视的Redis服务器实例，可以是主服务器、从服务器或者另外一个Sentinel.

ypedef struct sentinelRedisInstance {
	// 标识值，记录了当前Redis实例的类型和状态
	int flags;      /* See SRI_... defines */
	// 实例的名字
	// 主节点的名字由用户在配置文件中设置
	// 从节点以及Sentinel节点的名字由Sentinel自动设置，格式为：ip:port
	char *name;     /* Master name from the point of view of this sentinel. */
	//实例的运行 ID
	char *runid;    /* Run ID of this instance, or unique ID if is a Sentinel.*/
	//配置纪元，用于实现故障转移
	uint64_t config_epoch;  /* Configuration epoch. */
	//实例的地址:ip和port
	sentinelAddr *addr; /* Master host. */
	//实例的连接，有可能是被Sentinel共享的
	instanceLink *link; /* Link to the instance, may be shared for Sentinels. */
	 // 最近一次通过 Pub/Sub 发送信息的时间
	mstime_t last_pub_time;   /* Last time we sent hello via Pub/Sub. */
	// 只有被Sentinel实例使用
	// 最近一次接收到从Sentinel发送来hello的时间
	mstime_t last_hello_time; /* Only used if SRI_SENTINEL is set. Last time
								 we received a hello from this Sentinel
								 via Pub/Sub. */
	// 最近一次回复SENTINEL is-master-down的时间                             
	mstime_t last_master_down_reply_time; /* Time of last reply to
											 SENTINEL is-master-down command. */
	// 实例被判断为主观下线的时间                                         
	mstime_t s_down_since_time; /* Subjectively down since time. */
	// 实例被判断为客观下线的时间
	mstime_t o_down_since_time; /* Objectively down since time. */
	 // 实例无响应多少毫秒之后才会被判断为主观下线（subjectively down）
	mstime_t down_after_period; /* Consider it down after that period. */
	 // 从实例获取INFO命令回复的时间
	mstime_t info_refresh;  /* Time at which we received INFO output from it. */

	/* Role and the first time we observed it.
	 * This is useful in order to delay replacing what the instance reports
	 * with our own configuration. We need to always wait some time in order
	 * to give a chance to the leader to report the new configuration before
	 * we do silly things. */
	// 实例的角色 
	int role_reported;
	// 角色更新的时间
	mstime_t role_reported_time;
	// 最近一次从节点的主节点地址变更的时间
	mstime_t slave_conf_change_time; /* Last time slave master addr changed. */

	/* Master specific. */
	 /*----------------------------------主节点特有的属性----------------------------------*/
	 // 其他监控相同主节点的Sentinel
	dict *sentinels;    /* Other sentinels monitoring the same master. */
	// 如果当前实例是主节点，那么slaves保存着该主节点的所有从节点实例
	// 键是从节点命令，值是从节点服务器对应的sentinelRedisInstance
	dict *slaves;       /* Slaves for this master instance. */
	  // 判定该主节点客观下线（objectively down）的投票数
	// 由SENTINEL monitor <master-name> <ip> <port> <quorum>配置
	unsigned int quorum;/* Number of sentinels that need to agree on failure. */
	 // SENTINEL parallel-syncs <master-name> <number> 选项的值
	// 在执行故障转移操作时，可以同时对新的主服务器进行同步的从服务器数量
	int parallel_syncs; /* How many slaves to reconfigure at same time. */
	  // 连接主节点和从节点的认证密码
	char *auth_pass;    /* Password to use for AUTH against master & slaves. */

	/* Slave specific. */
	/*----------------------------------从节点特有的属性----------------------------------*/
	 // 从节点复制操作断开时间
	mstime_t master_link_down_time; /* Slave replication link down time. */
	 // 按照INFO命令输出的从节点优先级
	int slave_priority; /* Slave priority according to its INFO output. */
	 // 故障转移时，从节点发送SLAVEOF <new>命令的时间
	mstime_t slave_reconf_sent_time; /* Time at which we sent SLAVE OF <new> */
	 // 如果当前实例是从节点，那么保存该从节点连接的主节点实例
	struct sentinelRedisInstance *master; /* Master instance if it's slave. */
	// INFO命令的回复中记录的主节点的IP
	char *slave_master_host;    /* Master host as reported by INFO */
	// INFO命令的回复中记录的主节点的port
	int slave_master_port;      /* Master port as reported by INFO */
	 // INFO命令的回复中记录的主从服务器连接的状态
	int slave_master_link_status; /* Master link status as reported by INFO */
	// 从节点复制偏移量
	unsigned long long slave_repl_offset; /* Slave replication offset. */

	/* Failover */
	 /*----------------------------------故障转移的属性----------------------------------*/
	// 如果这是一个主节点实例，那么leader保存的是执行故障转移的Sentinel的runid
	// 如果这是一个Sentinel实例，那么leader保存的是当前这个Sentinel实例选举出来的领头的runid
	char *leader;       /* If this is a master instance, this is the runid of
						   the Sentinel that should perform the failover. If
						   this is a Sentinel, this is the runid of the Sentinel
						   that this Sentinel voted as leader. */
	// leader字段的纪元                       
	uint64_t leader_epoch; /* Epoch of the 'leader' field. */
	// 当前执行故障转移的纪元
	uint64_t failover_epoch; /* Epoch of the currently started failover. */
	// 故障转移操作的状态
	int failover_state; /* See SENTINEL_FAILOVER_STATE_* defines. */
	// 故障转移操作状态改变的时间
	mstime_t failover_state_change_time;
	// 最近一次故障转移尝试开始的时间
	mstime_t failover_start_time;   /* Last failover attempt start time. */
	//  更新故障转移状态的最大超时时间
	mstime_t failover_timeout;      /* Max time to refresh failover state. */
	// 记录故障转移延迟的时间
	mstime_t failover_delay_logged; /* For what failover_start_time value we
									   logged the failover delay. */
	// 晋升为新主节点的从节点实例                                   
	struct sentinelRedisInstance *promoted_slave; /* Promoted slave instance. */
	/* Scripts executed to notify admin or reconfigure clients: when they
	 * are set to NULL no script is executed. */
	// 通知admin的可执行脚本的地址，如果设置为空，则没有执行的脚本 
	char *notification_script;
	 // 通知配置的client的可执行脚本的地址，如果设置为空，则没有执行的脚本
	char *client_reconfig_script;
	// 缓存INFO命令的输出 
	sds info; /* cached INFO output */
} sentinelRedisInstance;

其中的 addr 属性是一个指向 sentinel.c/sentinelAddr 结构的指针，这个结构保存实例的IP地址和端口号:
1
2
3
4
typedef struct sentinelAddr{
char *p;
int port;
}sentinelAddr;
对Sentinel 状态的初始化将引发对 masters 字典的初始化,而 masters 字典的初始化是根据被载入的Sentinel配置文件来进行的。假设我们有master1和master2，由如下图1的配置文件导入：
那么我们得到两个sentinelRedisInstance：
最终sentinelRedisInstance为：

创建连向主服务器的网络连接
- 这是最后一步啦，这一步是创建连向被监视主服务器的网络连接，Sentinel将成为主服务器的客户端，可以向主服务器发送命令，并从命令回复中获取相关的信息。
- 每个被Sentinel监视的主服务器，Sentinel会创建两个连向主服务器的异步网络连接：
  1. 命令连接，用于向主服务器发送命令，并接收命令回复
  2. 订阅连接，用于订阅主服务器的__sentinel__:hello频道
- 3.2 Sentinel与服务器的交互

Sentinel作为一个监视Redis服务器的监控系统，必然需要有如下的权利或者义务：

要能掌握被自己监视的主服务器和其从服务器的状态信息
- INFO命令：每十秒一次，通过命令链接向被监视的主服务和从服务器发送INFO命令。分析主服务器的应答得到主服务器的状态信息。
要有为“与自己监视了相同服务器的其他Sentinel”感知到自己提供便利的义务。
- 广播频道消息：Sentinel每两秒一次，通过命令链接向所有被自己监视的主服务器和从服务器发送PUBLISH命令，发布自己的一些状态信息到对应主服务器的sentinel:hello频道，以便让其他监视了同一服务器的Sentinel（当然这些Sentinel也订阅了该服务器的sentinel:hello频道）感知到自己的存在，宣誓主权。
要能感知到“与自己监视了同一服务器的其他Sentinel”的状态信息。
- 接收频道消息：Sentinel在与主服务器创建订阅链接后就会通过订阅命令来订阅主服务器的sentinel:hello频道。通过订阅链接，Sentinel能接收到该频道上其他Sentinel发布的他们各自的状态信息。从而感知到他们的存在。
- 创建Sentinel之间的链接：Sentinel A 感知到另一个Sentinel B 时，如果是第一次感知到，那么A会创建连向B的命令链接。当然B也会有一个发现A的过程，所以对于监视相同服务器的Sentinel来说，他们是这样相互关联的。

归纳完毕，现在我们来一一展开介绍：

3.2.1 INFO命令

假设有个主服务器和三个从服务器。

Sentinel 默认每十秒一次，通过命令连接向被监视的主服务器发送 INFO 命令，得到如下信息：

关于服务器本身的信息
- 包括 run_id 域记录的服务器运行ID，以及 role 域记录的服务器角色
关于主服务器属下的所有从服务器信息
- 每个从服务器都由一个“slave”字符串开头的行记录，每行的 ip= 域记录了从服务器的IP地址, port= 域记录了从服务器的端口号。根据这些IP地址和端口号，Sentinel无须用户提供从服务器的地址信息，就可以自动发现从服务器。

根据 run_id 域和 role 域的信息，Sentinel将对主服务器的实例结构（sentinelRedisInstance）进行更新。而主服务器返回的从服务器信息，将会被用于更新主服务器实例结构（sentinelRedisInstance）的 slaves 字典(记录了属下从服务器的名单，key为ip:port格式，值指向从服务器的sentinelRedisInstance实例)。

Sentinel 分析 INFO 命令中包含的从服务器信息时，会检查这个从服务器实例结构(sentinelRedisInstance）是否已经存在于主服务器的 slaves 字典：如果存在，就对从服务器的实例结构进行更新，如果不存在(表明这个从服务器是新发现的从服务器)，Sentinel会在 slaves 字典中为这个从服务器创建一个新的实例结构。

当Sentinel发现主服务器有新的服务器出现时，除了会为这个新从服务器创建相应的实例结构之外，还会创建连接到从服务器的命令连接和订阅连接。

创建了命令连接之后，每10秒一次向从服务器发送 INFO 命令，依次来维护从服务器的实例结构(sentinelRedisInstance）的状态。

主服务器实例结构的 flags 值为 SRI_MASTER,从服务器是 SRI_SLAVE

3.2.2 广播频道消息

Sentinel会每两秒一次，通过命令连接向所有被监视的主服务器和从服务器发送以下格式的命令：

1 2	PUBLISH __sentinel__:hello "<s_ip>,<s_port>,<s_runid>,<s_epoch>, <m_name>,<m_ip>,<m_port>,<m_epoch>"

这条命令就表示向服务器的 __sentinel__:hello 频道发送一条信息，信息由一下部分组成：

以 s_ 开头的参数记录Sentinel本身的信息
以 m_ 开头的参数则是该频道所属的主服务器的信息，当然如果监视的是从服务器，这个信息表示的就是所属的从服务器的信息
具体含义如下图

3.2.3 接收频道消息

在建立起订阅连接之后，Sentinel会通过这个连接，向服务器发送SUBSCRIBE __sentinel__:hello命令，也就是订阅这个频道，这个订阅关系会一直持续到Sentinel与服务器的连接断开之后。

对于监视同一服务器的多个Sentinel来说，一个Sentinel发送的信息会被其他的Sentinel接收到，并用于更新其他Sentinel对发送信息Sentinel的认知，和被用于更新其他Sentinel对被监视服务器的认知。

假如该Sentinel A从其监控的主服务器M的 __sentinel__:hello频道中，接收到其他Sentinel B发来的<s_ip>,<s_port>,<s_runid>,<s_epoch>,<m_name>,<m_ip>,<m_port>,<m_epoch>格式的信息后，Sentinel A会从信息中分析出以下信息：

与Sentinel相关的参数：Sentinel B的IP、port、run_id、配置纪元
与主服务器相关参数：Sentinel B 正在监视的这个主服务器（也就是主服务器M）的名字、IP、port、配置纪元

服务器实例结构（sentinelRedisInstance）中除了slave字典外，还有一个sentinels字典，存放着其他共同监控着这个主服务器的sentinels的状态信息。这个字典的键是Sentinel的名字，格式：ip:port。值是对应Sentinel的实例结构(还是sentinelRedisInstance结构)。

根据之前那些主服务器参数，Sentinel A 会在自己的Sentinel状态（sentinelState）的 masters 字典中查找相应的主服务器实例结构（sentinelRedisInstance），然后根据Sentinel参数，检查主服务器实例结构的 sentinels 字典中，Sentinel B的实例结构是否存在：

存在，就对Sentinel B的实例结构进行更新
存在，说明Sentinel B是才开始监视主服务器的新Sentinel，Sentinel A 会为Sentinel B创建一个新的实例结构，并将这个结构添加到 sentinels 字典里面

3.2.4 创建Sentinel之间的链接

当Sentinel通过频道信息发现了一个新的Sentinel时，它不仅会为新的Sentinel在 sentinels 字典中创建相应的实例结构，还会创建一个连向新Sentinel的命令连接。

新的Sentinel同样会创建连向这个Sentinel的命令连接，最终监视同一主服务器的多个Sentinel将形成相互连接的网络：SentinelA有连向SentinelB的命令连接，SentinelB也有连向SentinelA的命令连接。

Sentinel之间不会创建订阅连接

3.3 监控下线和故障转移

了解了Sentinel与服务器/其他Sentinel的交互方式后，就可以来着手解决实际问题了，Sentinel的使命主要有两点：

监控下线
选举领头sentinel
故障转移

3.3.1 监控下线

3.3.1.1 检测主观下线状态

主观下线状态，即单个sentinel认为某个主服务器/从服务器/sentinel下线了，至于是不是真的已经下线，则不一定。

默认情况下，Sentinel会以每秒一次的频率向所有与它创建了命令连接的实例(包括主服务器、从服务器、其他Sentinel在内)发送 PING 命令，并通过实例返回的 PING 命令回复来判断实例是否在线。
对 PING 命令的回复，Redis只认两种含义：
- 有效回复：实例返回 +PONG 、 -LOADING 、-MASTERDOWN 三种其中一种
- 无效回复，除了上面三种之外的其它回复，或者在指定时限内没有返回任何回复
Sentinel配置文件中的 down-after-millseconds 选项指定了Sentinel判断实例进入主观下线所需的时间长度：如果一个实例在 down-after-millseconds 毫秒内，连续向Sentinel返回无效回复，那么Sentinel会修改这个实例所对应的实例结构，在结构的 flags 属性中打上 SRI_S_DOWN 标识，用于表示这个实例已经进入主观下线状态。（也就是我认为你已经下线了）

主观下线时长选项，即 down-after-millseconds 的值，不仅会被Sentinel用于判断其监控的主服务器的主观下线状态，还会被用于判断该主服务器属下的所有从服务器，以及所有同样监视这个主服务器的其他Sentinel的主观下线状态。

多个Sentinel设置的主观下线时长可能不同，对于监视同一个主服务器的多个Sentinel来说，这些Sentinel设置的 down-after-milliseconds 选项的值可能不同，因此，当一个Sentinel将主服务器判断为主观下线时，其它Sentinel可能任然会认为主服务器处于在线状态。

3.3.1.2 检测客观下线状态

客观下线状态，即经过确认后，可断定为事实上确实下线了。

当Sentinel将一个主服务器判断为主观下线之后，为确定这个服务器是否真的下线，它会向同样监视这个主服务器的其它Sentinel进行询问，当接收到足够数量的已下线判断之后，Sentinel就会将从服务器判定为客观下线，并对主服务器进行故障转移操作。

发送 SENTINEL is-master-down-by-addr 命令
- entinel会发送下面的命令询问其它Sentinel是否同意主服务器下线：
- SENTINEL is-master-down-by-addr <ip> <port> <current_epoch> <runid>
接收 SENTINEL is-master-down-by-addr 命令
- 当一个Sentinel(目标Sentinel)接收到另外一个Sentinel(源Sentinel)发来的 SENTINEL is-master-by-addr命令时，目标Sentinel会分析并取出命令请求中包含的各个参数，并根据其中的IP和port，判断主服务器是否已经下线，然后向源Sentinel返回一个包含三个参数的 Multi Bulk 回复作为这个命令的回复。这三个参数分别是：
  1. ：返回目标Sentinel对主服务器的检查结果，1表示主服务器已下线，0表示主服务器未下线
  2. ：可以是 * 符号或者目标Sentinel的局部领头Sentinel的运行ID，*表示命令仅仅用于检测主服务器的下线状态，而局部领头Sentinel的运行ID则用于选举领头Sentinel
  3. ：目标Sentinel的局部领头Sentinel的配置纪元，用于选举领头Sentinel。仅在 leader_runid 值不为 * 时有效，如果其值为 * ,这个参数总为0
接收 SENTINEL is-master-down-by-addr 命令之后
- 根据其他Sentinel发回的 SENTINEL is-master-down-by-addr回复，Sentinel会统计反馈了“同意这个主服务器已经下线”这个信息的sentinel数量。
- 当这个值达到配置指定的判断客观下线所需的数量时(即 quorum 属性的值)，Sentinel会将主服务器实例结构中（sentinelRedisInstance） flags 属性的 SRI_O_DOWN 标识打开，标识主服务器已经进入客观下线状态。

3.3.2 选举领头sentinel

当一个Master服务器客观下线后，监控这个Master服务器的所有Sentinel将会选举出一个领头Sentinel。并由领头Sentinel对客观下线的Master进行故障转移。

选举领头Sentinel的规则和方法:

所有监控客观下线Master的Sentinel都有可能成为领头Sentinel。每次进行领头Sentinel选举之后，不论是否选举成功，所有Sentinel的配置纪元（configuration epoch）的值都会自动增加一次。
在一个配置纪元里面，所有Sentinel都有一次将某个Sentinel设置为局部领头Sentinel的机会，并且局部领头Sentinel一旦设置，在这个配置纪元里面将不能再更改。
监视Master客观下线的所有在线Sentinel都有要求其它Sentinel将自己设置为局部领头Sentinel的机会。
当一个Sentinel（源Sentinel）向另一个Sentinel（目标Sentinel）发送SENTINEL is-master-down-by-addr命令，并且命令中的runid参数不是“*”符号而是当前Sentinel的运行ID时，这表示当前Sentinel要求目标Sentinel将自己设置为领头Sentinel。
Sentinel设置局部领头Sentinel的规则是先到先得。即最先向目标Sentinel发送设置要求的Sentinel将会成为局部领头Sentinel，之后接受到的请求都会被拒绝。
目标Sentinel接收到SENTINEL is-master-down-by-addr命令后，将向源Sentinel返回一条命令回复，回复中的leader_runid参数和leader_epoch参数分别记录了目标Sentinel的局部领头Sentinel的运行ID和配置纪元。
源Sentinel在接收到目标Sentinel返回的命令回复之后，会检查回复中leader_epoch参数的值和自己的配置纪元是否相同，如果相同的话，那么源Sentinel继续取出回复中的leader_runid参数，如果leader_runid参数的值和源Sentinel的运行ID一直，那么表示目标Sentinel将源Sentinel设置成了局部领头Sentinel，记录下来。
记录之后，如果有某个Sentinel发现自己已经被半数以上的Sentinel设置成了局部领头Sentinel，那么这个Sentinel就会成为领头Sentinel。
领头Sentinel的产生需要半数以上的Sentinel支持，并且每个Sentinel在每个配置纪元里面只能设置一次局部Sentinel，所以在一个配置纪元里面，只会出现一个领头Sentinel。
如果在给定时限内，没有一个Sentinel被选举为领头Sentinel，那么各个Sentinel将在一段时间之后再次进行选举，直到选出领头Sentinel为止，（所以建议哨兵设置奇数个，且数量不小于3）。

3.3.3 故障转移

接收到SENTINEL is-master-down-by-addr命令回复的源Sentinel可以统计出有多少个Sentinel将自己设置成局部领头Sentinel。如果超过半数，则当前Sentinel就会被选为领头Sentinel并进行故障转移。

故障转移包括以下三步：

在已下线的Master主机下面挑选一个他的Slave服务器，并将其转换为主服务器。
让其余所有Slave服务器复制新的Master服务器。
让已下线的Master服务器变成新的Master服务器的Slave。当已下线的服务器再次上线后将复新的Master的数据。

3.3.3.1 选举新的主服务器的过程

领头Sentinel会在所有Slave中选出新的Master，发送SLAVEOF no one命令，将这个服务器确定为主服务器。

领头Sentinel会将已下线Master的所有从服务器保存在一个列表中，按照以下规则，一项一项进行过滤。

删除列表中所有处于下线或者短线状态的Slave。（保证剩下都是在线的）
删除列表中所有最近5s内没有回复过领头Sentinel的INFO命令的Slave。（保证剩下都是近期成功通信过的）
删除所有与下线Master连接断开超过down-after-milliseconds * 10毫秒的Slave。（过滤掉过早的和下线Master断开连接的，这样可以保证剩下的Slave，数据都比较新）
领头Sentinel将根据Slave优先级，对列表中剩余的Slave进行排序，并选出其中优先级最高的Slave。
如果有多个具有相同优先级的Slave，那么领头Sentinel将按照Slave复制偏移量，选出其中偏移量最大的Slave。（复制偏移量的slave就是保存的最新数据的slave）
如果有多个优先级最高，偏移量最大的Slave，那么根据运行ID最小原则选出新的Master。

确定新的Master之后，领头Sentinel会以每秒一次的频率向新的Master发送INFO命令，当得到确切的回复：role由slave变为master之后，当前服务器顺利升级为Master服务器。

3.3.3.2 修改从服务器的复制目标

选出新的Master服务器后，领头Sentinel会向下线Master的剩余Slave发送SLAVEOF命令，让它们复制新的Master。

3.3.3.3 将旧的Master变成Slave

当已下线的Master重新上线后，领头Sentinel会向此服务器发送SLAVEOF命令，将当前服务器变成新的Master的Slave。

4. 集群模式

Redis集群是Redis的分布式数据库方案，通过分片来进行数据共享，并提供复制和故障转移功能。集群为Redis提供了更加便利的水平拓展能力，是现代企业级Redis实现高吞吐高并发的重要实现。

集群模式和主从模式的区别：
- 主从模式
  - 指的是针对多台redis实例时候，只存在一台主服务器master，提供读写的功能，同时存在依附在这台主服务器的从服务器slaver，只提供读服务。
  - 主从作用是：读写分离，分散访问量，提高访问可读性，同时保证数据的冗余和备份。
- 集群模式
  - 指的是针对多个redis实例，去中心化，去中间件，集群中的每个节点都是平等的关系，都是对等的。
  - 集群的作用是：实现扩容、分摊压力、无中心配置相对简单。

4.1 节点

节点，指的就是我们之前说的Redis服务器。

一个Redis 集群通常由多个节点组成，在刚开始的时候，每个节点都是独立的，只处于只包含自己的集群中（也就是之前我们说到的单机模式），当要组成一个真正可工作的集群时，就需要将这些独立的节点连接起来，构建成一个包含多个节点的集群。

如何连接各个节点？使用CLUSTER MEET命令

CLUSTER MEET <ip> <port>

向一个节点发送CLUSTER MEET命令，可以让节点与ip和port所指定的节点进行握手，握手成功，节点就会将ip和port指定的节点添加到当前的集群中。

节点A向节点B发送CLUSTER MEET命令，那么B将会加入A的集群中。反之，A加入B的集群中。

在启动时，服务器会根据 cluster-enabled 配置选项来决定是否开启集群模式。

4.2 集群数据结构

Redis使用clusterNode结构来保存一个节点的状态：

//一个节点的当前状态
struct clusterNode{    
    // 创建节点的时间    
    mstime_t ctime;    
    // 节点的名字，由40个16进制字符组成    
    char name[REDIS_CLUSTER_NAMELEN];    
    // 节点标识    
    int flags;    
    // 节点当前的配置纪元，用于实现故障转移    
    uint64_t configEpoch;    
    // 节点的ip地址    
    char ip[REDIS_IP_STR_LEN];    
    // 节点的端口号    
    int port；    
    // 保存连接节点所需的有关信息   
    clusterLink *link；    
    //……
};

clusterNode 结构的 link 属性：

typedef struct clusterLink {

    // 连接的创建时间
    mstime_t ctime;

    // TCP 套接字描述符
    int fd;

    // 输出缓冲区，保存着等待发送给其他节点的消息（message）。
    sds sndbuf;

    // 输入缓冲区，保存着从其他节点接收到的消息。
    sds rcvbuf;

    // 与这个连接相关联的节点，如果没有的话就为 NULL
    struct clusterNode *node;

} clusterLink;

最后，每个节点都保存着一个clusterState结构，这个结构记录了在当前节点的视角下集群目前所处的状态，比如集群是在线还是下线，包含多少个节点，当前的配置纪元等：

typedef struct clusterState {

    // 指向当前节点的指针
    clusterNode *myself;

    // 集群当前的配置纪元，用于实现故障转移
    uint64_t currentEpoch;

    // 集群当前的状态：是在线还是下线
    int state;

    // 集群中至少处理着一个槽的节点的数量
    int size;

    // 集群节点名单（包括 myself 节点）
    // 字典的键为节点的名字，字典的值为节点对应的 clusterNode 结构
    dict *nodes;

    // ...
} clusterState;

4.2.1 CLUSTER MEET 命令的实现

向节点A发送 CLUSTER MEET 命令，能让接收命令的节点A将另一个节点B（ip和port指向的节点）添加到节点A当前所处的集群里。

收到命令的节点A 和节点B进行握手，以此来确认彼此的存在，并为将来的进一步通信打好基础：

节点A为节点B创建一个clusterNode结构，并将该结构添加到节点A自己的clusterState.nodes字典中。
节点A根据ip和port发送meet消息给节点B。
如果一切顺利，节点B收到meet消息，为节点A创建一个clusterNode结构，并将该结构添加到节点B自己的clusterState.nodes字典中。
如果一切顺利，节点B向节点A发送PONG消息
如果一切顺利，节点A向节点B返回PING消息
如果一切顺利，至此，握手完成
最后节点A会向自己处于的集群内的其他节点发送信息，让其他节点也和B节点握手，最终达到集群内的所有节点都相互认识彼此。至此，B节点加入进集群。

4.3 redis负载均衡算法——hash slot

Redis使用分片的方式来保存数据库中的键值对：整个集群被分为16384个槽(slot)，数据库中的每个键都位于这其中的某个槽上，集群中的节点，最少可以处理0个槽，最多可以处理16384个槽。

当数据库中的 16384 个槽都有节点在处理时，集群处于上线状态，否则，处于下线状态。

我们可以使用CLUSTER ADDSLOTS命令来给某个节点指派要处理的槽：

CLUSTER ADDSLOTS [slot ...]

这个命令接受一个或多个槽的编号作为参数，并将所有输入的槽指派给接收该命令的节点负责。

如CLUSTER ADDSLOTS 0 1 2 3 ... 1000

表示将槽0到槽1000指派给接收到命令的整个节点负责。

4.3.1 记录节点的槽指派信息

clusterNode结构中的slots数组和numslots字段记录了该节点负责处理的槽。

// 一个节点的当前状态
struct clusterNode{
    //……
    // 记录处理那些槽
    // 二进制位数组，长度为 2048 个字节，包含 16384 个二进制位
    // 如果slots数组在索引i上的二进制位的值为1，那么表示节点负责处理槽i；否则表示节点不负责处理槽i
    unsigned char slots[16384/8];
    //记录自己负责处理的槽的数量
    int numslots;
    //……
};

slots数组有16384个二进制位，第i项上的二进制值如果为1，则表示槽i由自己负责。为0则表示槽i不是由自己负责。

数组的定位时间复杂度是O(1)，这样的设计可以让节点非常快速的知道某个槽到底是不是由自己负责。

4.3.2 传播节点的槽指派信息

一个节点除了会将自己负责处理的槽记录在clusterNode结构的slots属性和numslots属性之外，它还会将自己的slots数组通过消息发送给集群中其他的节点，以此来告知其他节点自己目前负责处理哪些槽。

当节点A通过消息从节点B那里接收到节点B的slots数组时，节点A会在自己的clusterState.nodes字典中查找节点B对应的clusterNode结构，并对该clusterNode结构中的slots数组进行保存或者更新。

每个节点都相互分享自己的槽指派信息，每个节点又在自己的clusterState.nodes字典中保存其他节点的槽指派信息，因此，集群中的每个节点都会知道整个集群数据库的全部槽，都分别被分派给了哪些节点。

4.3.3 记录集群所有槽的指派信息

我们知道，每个节点都保存着一个clusterState结构，这个结构，我们可以看做节点自己对整个集群所描绘的详细概念地图。

节点除了会在clusterState.nodes字典中维护每个节点的槽分派信息外，还会在clusterState结构结构中维护一个clusterNode *slots[16384]数组。

clusterState.slots数组有16384项，每个数组项都是一个指向clusterNode的指针：

如果slots[i]指向NULL，那么表示槽i尚未指派给任何节点。
如果slots[i]指向一个clusterNode，那么表示槽i已经指派给了这个clusterNode所对应的节点

假设槽被指派给了集群中的三个节点，那么slots数组结构如下图：

clusterState.nodes[i].slots
- 节点A在自己的clusterState.nodes字典中的某个clusterNode结构（假设对应节点B）中保存的槽分派信息，是以单节点（节点B）为视角的槽分派信息，即——我这个节点负责如下这些槽。
clusterState.slots
节点A在自己的clusterState.slots数组中保存的槽分派信息，是以每个槽为视角的槽分派信息。即——我这个槽被某个节点负责。

4.4 集群处理命令

当集群中的所有槽都被指派之后，集群就会进入上线状态，这是客户端就可以向集群中的节点发送命令了。

一张图解释如下过程：

4.4.1 计算键属于哪个槽

节点用以下算法计算给定键 key 属于哪个槽：

1 2	def slot_number(key): return CRC16(key) & 16383 //CRC16(key) 计算key的CRC-16校验和，然后和16383与出一个0-16383的序号来。

1 2	# 用于查看一个给定键属于哪个槽 CLUSTER KETSLOT <key>

4.4.2 判断某个槽是否由当前节点负责

当节点计算出键所属槽 i 之后，节点会检查自己在 clusterState.slots 数组中的项 i ，判断键所处的槽是否由自己负责：

如果 clusterState.slots[i] 等于 clusterState.myself ，那么说明槽 i 由当前节点负责，节点可以执行客户端发送的命令；
否则，槽 i 不由当前节点负责,节点会根据 clusterState.slots[i] 所指向的 clusterNode 结构所记录的节点IP和端口号，向客户端返回 MOVED 错误并指引客户端转向正在处理槽i的节点，格式如下：
- MOVED <slot> <ip>:<port>
- 客户端接收到 MOVED 命令之后，根据其提供的IP和端口，转向负责处理槽 slot 的节点，并向节点重新发送之前想要执行的命令。
- 客户端会和每个节点创建套接字连接，所谓的转向，其实就是换一个套接字来发送命令。

4.5 节点数据库的实现

我们在文章Redis数据库结构/键空间/过期字典/事务/锁/持久化中讨论过Redis服务器的键空间（即如何存储键值对）redisDb结构的dict字典数组，保存了所有的键值对。redisDb结构的expires字典数组，保存了所有的过期字典。

单机服务器和集群服务器（节点）的保存键值对以及键值对过期时间，实现都是一样的。只不过节点只能使用 0 号数据库，单机服务器没有限制。

和单机服务器不同的是，除了键值对之外，节点还需要维护槽和键的关系，节点会用 clusterState 结构中的 slots_to_keys 跳跃表来保存槽和键之间的关系：

typedef struct clusterState{
    // ...
    zskiplist *slots_to_keys;
    // ...
} clusterState;

这个跳跃表每个节点的分值( score )都是一个槽号，节点的成员( member )都是一个数据库键：

每当节点往数据库中添加一个新的键值对时，节点就会将这个键以及键的槽号关联到 slots_to_key s跳跃表
当节点删除数据库中的某个键值对时，节点就会在slots_to_keys跳跃表解除被删除键与槽号的关联

图例：

该图表示：

键”book”所在跳跃表节点的分值为1337.0，这表示键”book”所在的槽为1337
键”date”所在跳跃表节点的分值为2022.0，这表示键”date”所在的槽为2022
键”lst”所在跳跃表节点的分值为3347.0，这表示键”lst”所在的槽为3347

slots_to_keys 的存在是为了使节点可以很方便的对属于某个或者某些槽的所有键做批量操作。例如命令CLUSTER GETKEYSINSLOT <slot> <count>命令可以返回最多count个属于槽slot的数据库键，而这个命令就是通过遍历 slots_to_keys跳跃表来实现的

4.6 重新分片

Redis集群的重新分片操作可以将任意数量已经指派给某个节点（源节点）的槽改为指派给另一个节点（目标节点，并且相关槽所属的键值对也会从源节点移动到目标节点。 重新分片可以在线进行，在这过程中，集群不用下线，且源节点和目标节点都可以继续处理命令。

重新分片由Redis的集群管理软件 redis-trib 负责执行，redis-trib 通过向源节点和目标节点发送命令来进行重新分片：

redis-trib对集群的单个槽 slot 进行重新分片的步骤如下：
1. redis-trib 对目标节点发送 CLUSTER SETSLOT <slot> IMPORTING <source_id> 命令，让目标节点准备好从源节点导入槽 slot 的键值对
2. redis-trib 对源节点发送 CLUSTER SETSLOT <slot> MIGRATING <source_id>命令，让源节点准备好将属于槽 slot的键值对迁移至目标节点
3. redis-trib 对源节点发送 CLUSTER GETKEYSINSLOT<slot> <count> 命令，获得最多 count 个属于槽 slot 的键值对的键名。
4. 对于步骤三获得的每个键名，redis-trib 都向源节点发送一个MIGRATE <target_ip> <target_port> <key_name> 0 <timeout> 命令，将被选中的键原子的从源节点迁移至目标节点。
  1. 重复步骤3和4，直到源节点保存的所有属于槽slot的键值对都被迁移到目标节点为止。
  2. redis-trib向集群中的任意一个节点发送 CLUSTER SETSLOT <slot> NODE <target_id> 命令，将槽slot指派给目标节点的信息发送给整个集群。
如果重新分片涉及多个槽，那么 redis-trib 将对每个给定的槽 分别执行上面给出的步骤。

重新分片的实战操作，可以参考该篇文章：redis cluster管理工具redis-trib.rb详解

4.6 ASK 错误

在重新分片期间，源节点向目标节点迁移一个槽的过程中，可能会出现这样一种中间状态：属于被迁移槽的一部分键值对保存在源节点里面，而另一部分键值对保存在目标节点中。

这时候如果客户端向源节点发送了一个key的操作请求，就可能会触发ASK 错误。

当客户端向源节点发送关于键key的命令，源节点先在自己的数据库里查找这个键，如果找到就直接返回执行客户端命令，如果没找到，这个键可能已经被迁移到了目标节点，源节点向客户端返回一个 ASK 错误，指引客户端转向正在导入槽的目标节点，并再次发送之前要执行的命令。

接到ASK 错误的客户端会根据错误提供的IP地址和端口号，转向至正在导入槽的目标节点，然后向目标节点发送一个 ASKING 命令，之后再重新发送原本想要执行的命令。

4.6.1 ASKING 命令的实现

在重新分片过程中，我们对目标节点执行了 CLUSTER SETSLOT <slot> IMPORTING <source_id>命令，这会使得clusterState状态的importing_slots_from数组会记录当前节点的哪些槽正在从哪些节点导入：

typedef struct clusterState{
	// ……
    // 如果importing_slots_from[i]的值不为NULL，而是指向一个clusterNode结构，表示当前节点正在从
    // clusterNode所代表的节点导入槽i
    clusterNode *importing_slots_from[16384];
     // ……
}clusterState;

在重新分片过程中，我们对源节点执行了CLUSTER SETSLOT <slot> MIGRATING <source_id>命令，这会使得clusterState状态的migrating_slots_to数组会记录当前节点正在迁移至其他节点的槽：

typedef struct clusterState{
    // ……
    // 如果migrating_slots_to[i]的值不为NULL，而是指向一个clusterNode结构，表示当前节点正在将
    // 槽i迁移至clusterNode所代表的节点
    clusterNode *migrating_slots_to[16384];
    // ……
}clusterState;

ASKING命令要做的就是打开发送该命令的客户端的 REDIS_ASKING 标识。

如果该客户端的 REDIS_ASKING 标识未打开，直接发送请求，由于槽的迁移过程还未完成，请求的键还属于源节点，此时直接请求目标节点，目标节点会返回一个MOVED错误。(因为迁移未完成，所以虽然部分的键已经迁移至目标节点了，但这部分键的归属，还是记在源节点上)

但是，如果节点的clusterState.importing_slots_from[i]显示节点正在导入槽 i ,并且发送命令的客户端带有 REDIS_ASKING 标识，那么节点将破例执行这个关于槽 i 的命令一次。

客户端的 REDIS_ASKING 标识是一个一次性标识，当节点执行了一个带有 REDIS_ASKING 标识的客户单发送的命令之后，客户端的这个表示就会被移除。

ASK错误和MOVED错误的区别:
MOVED错误代表槽的负责全已经从一个结点转移到了另一个节点
ASK错误只是两个节点在迁移槽的过程中使用的一种临时措施

4.7 节点的复制与故障转移

集群中的节点分为主节点和从节点，主节点负责处理槽，而从节点负责复制某个主节点，并在被复制的主节点下线时，替代下线主节点继续处理命令请求。

4.7.1 设置从节点

向一个节点发送命令：CLUSTER REPLICATE <node_id>

这个命令可以让接收命令的节点成为 node_id 所指定的从节点，并开始对主节点进行复制：

这个节点会先在自己的 clusterState.nodes 字典中找到 node_id 所对应节点的 clusterNode 结构，并将自己的 clusterState.myself.slaveof指针指向这个结构，以此来记录这个节点正在复制的主节点
然后节点修改自己在 clusterState.myself.flags 中的属性，关闭原本的 REDIS_NODE_MASTER标识，打开 REDIS_NODE_SLAVE标识，表示这个节点由原来的主节点变成了从节点
最后，节点调用复制代码，并跟据 clusterState.myself.slaveof 指向的 clusterNode 结构所保存的IP地址和端口号，对主节点进行复制。就是相当于向从节点发送命令 SLAVEOF <master_ip> <maste_port>

一个节点开始成为从节点的时候，会向集群广播这一事实，以便集群中的其他节点更新从节点和主节点的关系。

4.7.2 故障检测

集群中的每个节点都会定期地向集群中的其他节点发送 PING 消息，以此来检测对方是否在线

如果接受 PING 消息的节点没有在规定时间内返回 PONG ，那么发送 PING 的节点就会将该节点标记为疑似下线(PFAIL)。

当一个主节点A通过消息得知主节点B认为主节点C进入疑似下线状态，主节点A会在自己的 clusterState.nodes 字典中找到主节点C所对应的 clusterNode 结构，并将主节点B的下线报告添加到这个结构的 fail_reports 链表里面

struct clusterNode{
    // ...
    // 一个链表，记录了所有其他节点对该节点的下线报告
    list *fail_reports;
    // ...
}

如果一个集群里，半数以上负责处理槽的主节点都将某个主节点X报告为疑似下线，那么这个主节点X将被标记为已下线(FAIL)，将主节点X标记为已下线的节点会向集群广播一条关于主节点X的FAIL消息，所有收到这条FAIL消息的节点都会立即将主节点X标记为已下线。

比较绕，我们来举例：假设一个集群有ABCD四个节点，A和B节点都认为D节点进入了疑似下线状态，这时刚好半数的主节点认为D疑似下线。然后，C节点通过消息交换，也将D节点标记为疑似下线状态。这时候数量就超过了半数了，于是C节点会将D节点标记为已下线，并向整个集群广播一条D节点已下线的消息。这时A和B接到消息，会将D节点标记为已下线。

4.7.3 故障转移

当一个从节点发现自己正在复制的主节点进入了已下线状态，从节点将开始对下线主节点进行故障转移:

复制下线主节点的所有从节点里面，会有一个从节点被选中
被选中的从节点将执行 slaveof no one 命令，成为新的主节点
新的主节点撤销已下线主节点对指派槽的管理，并将这些槽全部指派给自己
新的主节点向集群广播一条PONG消息，告诉集群中的其他节点自己成为了新的主节点。
新的主节点开始接收和自己负责处理的槽有关的命令请求，故障转移完成。

这里面涉及到新的主节点的选举：

集群的配置纪元是一个自增计数器，初始值为0
当集群里的某个节点开始一次故障转移操作时，集群配置纪元的值就会加一
对于每个配置纪元，集群中的每个负责处理槽的主节点都有一次投票机会，而第一个向主节点要求投票的从节点将获得主节点的投票
当从节点发现自己正在复制的主节点进入已下线状态时，从节点会向集群广播一条 CLUSTERMSG_TYPE_FAILOVER_AUTH_REQUEST 消息，要求所有收到这条消息、并具有投票权的主节点向这个从节点投票
如果一个主节点具有投票权(它正在负责处理槽),并且这个主节点尚未投票给其他从节点，那么主节点将向要求投票的从节点返回一条 CLUSTERMSG_TYPE_FAILOVER_AUTH_ACK 消息，表示这个主节点支持从节点成为新的主节点
每个参与选举的从节点都会接受 CLUSTERMSG_TYPE_FAILOVER_AUTH_ACK 消息，并根据自己受到了多少条这种消息来统计自己获得了多少主节点的支持
如果集群库有N个具有投票权的朱及诶单，那么当一个从节点收集到大于等于N/2+1张支持票，这个从节点当选为新的主节点
因为在每个配置纪元里面，每个具有投票权的主节点只能投一次票，所以如果有N个节点进行投票，那么具有大于等于N/2+1张支持票的从节点只会有一个，这确保了新的主节点只会有一个
如果在一个配置纪元里没有从节点能搜集到足够多的支持票，那么集群进入一个新的配置纪元，并再次进行选举，直到选出新的主节点为止。

和选举领头sentinel的算法一样，都是基于raft算法。

Redis数据库结构/键空间/过期字典/事务/锁/持久化

Posted on 2019-12-25 | In 中间件 , Redis |

Words count in article: 3.6k | Reading time ≈ 12

1 Redis服务器结构

Redis服务器将所有数据库都保存在redis.h/redisServer结构中，这里面最重要的一个结构是 redisDb *db，这是一个数组，保存着服务器中的所有数据库。
在redis初始化的时候，程序会根据dbnum属性来决定创建多少个数据库，这个属性由配置文件里的database选项来决定，默认是16，故而redis服务器默认创建16个数据库。

1.1 目标数据库

每个redis客户端都有自己的目标数据库，redis的读写操作都是针对目标数据库的。

默认情况下，redis的目标数据库是0号数据库，用户可以使用select命令来切换目标数据库。SELECT 1命令即为使目标数据库为1号数据库。

用来存储客户端状态的redisClient对象中的db属性记录了客户端当前的目标数据库，这个指针指向了redisDb数组的某个节点。

Select就是通过改变db属性的指针而切换目标数据库的。

1.2 数据库键空间

上文说过redisDb结构表示一个数据库，其中的dict字典保存了数据库中的所有键值对，我们将这个字典称为键空间。我们对键值对的增删改查，都是对这个键空间的操作。

使用字典的好处是，随着数据量的增大，定位到某个键值对的时间复杂度并不会增加太厉害。很适合redis数据库的情况。

1.3 过期字典

要理解过期字典，先知道生存时间这一概念：

1.3.1 设置过期时间

Redis可以设置键的生存时间或过期时间：

expire命令或者pexpire命令，客户端可以以秒（前者）或者毫秒（后者）精度，为数据库中某个键设置生存时间。

expire命令或者pexpire命令为一个key设置生存时间，注意，这个生存时间设置在key上，除非是用新的k-v来取代这个k-v，否则，只改变其value（可能是链表，集合，哈希等等）的结构，或者只是重命名这个key，或者对key进行自增自减操作，本质上都不会改变key上的生存时间。

Persist命令可以移除一个键的生存时间设置。
TTL 命令可以查看一个带有生存时间限制的键的剩余时间，以秒为单位，底层实现是以过期时间戳减去当前时间。（PTTL以毫秒为单位）

1.3.2 过期字典空间

回到我们的redisDb结构，我们可以看到一个dict数组叫做expires

Expires字典保存了数据库中所有键的过期时间，这个键就是过期字典。

过期字典的键是一个指针，指向了键空间中的某个键对象（所以才说生存时间是针对key的）
过期字典的值是一个long long 类型的整数，这个整数保存了键所指向的键对象的过期时间——以毫秒为精度的一个时间戳（所以底层其实都是用PEXPIREAT命令）

1.3.3 过期键删除策略

Redis使用了惰性删除（在使用到键时才去判断是否过期以及删除）和定期删除（每隔一段时间删除库中的过期键）两种结合的删除策略

db.c/expireIfNeeded函数负责惰性删除，
redis.c/activeExpireCycle函数实现定期删除，它在规定的时间内，分多次遍历服务器中的各个数据库，从过期字典中随机检查一部分键的过期时间，并删除过期键。

2 Redis的事务

//我们首先使用MULTI命令告诉Redis：
//“下面我发给你的命令属于同一个事务，你先不要执行，而是把它们暂时存起来。”Redis回答：“OK。

redis > MULTI
OK

//而后我们发送了两个SADD命令来实现关注和被关注操作.
//可以看到Redis遵守了承诺，没有执行这些命令，
//而是 返回QUEUED表示这两条命令已经进入等待执行的事务队列中了。
redis > 命令1
QUEUED
redis > 命令2
QUEUED

//当把所有要在同一个事务中执行的命令都发给Redis后，
//我们 使用EXEC命令告诉Redis将等待执行的事务队列中的所有命令（即刚才所有返回QUEUED的命令）
//按照发送顺序依次执行。
//EXEC命令的返回值就是这些命令的返回值组成的列表，返回值顺序和命令的顺序相同。

redis > EXEC

Redis的事务和其他的事务一样保证最基本的原子性，只要执行exec命令，事务就会执行，执行过程中，一个命令失败，事务中的命令就全部取消。

redis没有类似关系型数据库的回滚功能，烂摊子只能自己收拾。

3 Redis的锁

Redis的Watch命令具有乐观锁的功能，WATCH命令可以监控一个或多个键，一旦其中有一个键被修改（或删除），之后的事务就不会执行。

监控一直持续到EXEC命令（事务中的命令是在EXEC之后才执行的，所以在MULTI命令后可以修改WATCH监控的键值）

WATCH只负责当被监控的键值被修改后阻止紧随其后的一个事务的执行，而不能保证其他客户端不修改这一键值。

redis > SET key 1
OK
redis > WATCH key
OK
redis > SET key 2
OK
redis > MULTI
OK
redis > SET key 3
QUEUED
redis > EXEC
(nil)
redis > GET key   //得到2，说明SET key 3命令没有实现，事务被取消了
"2"

4 Redis的持久化

为了防止因为突发情况，导致Redis数据库的数据丢失，我们需要对Redis做持久化。Redis如何做持久化呢？有两种方式：

RDB（快照）持久化
AOF

4.1 RDF

RDB（快照）持久化：保存某个时间点的全量数据快照，生成RDB文件在磁盘中。RDB文件是一个压缩过的二进制文件，可以还原为Redis的数据。

4.1.1 触发和载入方式

手动触发方式
- SAVE命令：阻塞Redis的服务器进程，直到RDB文件被创建完毕，阻塞期间服务器不能处理任何命令请求。
- BGSAVE命令：Fork出一个子进程来创建RDB文件，不阻塞服务器进程。lastsave 指令可以查看最近的备份时间。
载入方式
- Redis没有主动载入RDB文件的命令，RDB文件是在服务器启动时自动载入，只要Redis服务器检测到RDB文件的存在，即会载入。且载入过程，服务器也会是阻塞状态。

自动触发方式

根据redis.conf配置里的save m n定时触发（用的是BGSAVE），m表示多少时间内，n表示修改次数。save可以设置多个条件，任意条件达到即会执行BGSAVE命令。

1
2
3

save 900 1  //设置条件1，即服务器在900秒内，对数据库进行了至少1次修改，即会触发BGSAVE
save 300 10 //设置条件2，即服务器在300秒内，对数据库进行了至少10次修改，即会触发BGSAVE
save 60 1000  //设置条件3，即服务器在60秒内，对数据库进行了至少1000次修改，即会触发BGSAVE

redis如何保存自动触发方式的save配置呢？
- redisServer结构中维护了一个saveParam的数组，数组每个saveParam都存储着一个save条件，如下图：
- 前文所述三个save，其saveParam的数组将会是下图的样子
自动触发方式如何实现的呢？
- redisServer结构维护了一个dirty计数器和lastsave属性。
- dirty计数器记录了上次SAVE或者BGSAVE之后，数据库执行了多少次的增删改，当服务器成功执行一个修改命令后，程序就会对该值+1，（对集合操作n个元素，dirty+n）。SAVE或者BGSAVE命令执行后，dirty计数器清零。
- lastsave属性是一个unix时间戳，记录了服务器上次成功执行SAVE或者BGSAVE命令的时间。
- Redis服务器有个周期性操作函数serverCron，默认每100毫秒执行一次，它其中一项工作就是检查saveParam保存的条件，并根据dirty和lastsave字段判断是否有哪一条条件已经被满足。

4.1.2 RDB文件的结构

不加赘述，详见让你彻底了解RDB存储结构

4.2 AOF

除了RDB持久化以外，Redis还提供了AOF（append only file）持久化功能，和RDB通过保存数据库的键值对来记录状态不同，AOF持久化是通过保存Reids服务器所执行的写命令来记录数据库状态的。

4.2.1 AOF持久化的实现

AOF持久化功能的实现可以分为命令追加（append）、文件写入、文件同步（sync）三个步骤。

命令追加
- 当AOF持久化功能处于打开状态时，服务器在执行完一个写命令后，会以协议格式将被执行的写命令追加到服务器状态的aof_buf缓存区的末尾。
AOF文件的写入和同步
- Redis的服务器进程就是一个事件循环。
- 每次结束一个事件循环之前，都会调用flushAppendOnlyFile函数，考虑是否将缓冲区的内容写入和保存到AOF文件里面。
- flushAppendOnlyFile函数根据配置项appendsync的不同选值有不同的同步策略。

4.2.2 AOF文件的载入

Redis读取AOF文件并还原数据库状态的详细步骤如下：

服务器创建一个不带网络连接的伪客户端（fake client）（因为Redis的命令只能在客户端上下文中执行）；
从AOF文件中分析并读取出一条写命令。
执行命令。
一直执行步骤2和步骤3，直到AOF文件中的所有写命令都被处理完毕为止。

4.2.3 AOF重写

体积过大的AOF文件很可能对Redis服务器、甚至整个宿主计算机造成影响，并且AOF文件的体积越大，使用AOF文件来进行数据还原所需的时间就越多。

为了解决AOF文件体积膨胀的问题，Redis提供了AOF文件重写（rewrite）功能。

通过该功能，Redis服务器可以创建一个新的AOF文件来替代现有的AOF文件，新旧两个AOF文件所保存的数据库状态相同，但新AOF文件不会包含任何浪费空间的冗余命令，所以新AOF文件的体积通常会比旧AOF文件的体积要小得多。

我们称新的AOF文件为AOF重写文件，AOF重写文件不是像AOF一样记录每一条的写命令，也不是对AOF文件的简单复制和压缩。AOF重写是通过读取当前Redis数据库状态来实现的。

比如一个animals键，我们有如下操作：

在AOF中，我们要保存四条写命令，而在AOF重写文件中，我们使用一条SADD animals "Dog" "Panda" "Tiger" "Lion" "Cat"来替代四条命令。

从数据库中读取键现在的值，然后用一条命令去记录键值对，代替之前记录这个键值对的多条命令，即直接从结果反推命令，这就是AOF重写功能的实现原理。（比如连续6条RPUSH命令会被整合成1条）

在实际中，为了避免在执行命令时造成客户端输入缓冲区溢出，重写程序在处理列表、哈希表、集合、有序集合这四种可能会带有多个元素的键时，会先检查键所包含的元素数量，如果元素的数量超过了redis.h/REDIS_AOF_REWRITE_ITEMS_PER_CMD常量(默认为64)的值，那么重写程序将使用多条命令来记录键的值，而不单单使用一条命令。例如如果SADD后面加入的元素为90条，那么会分成两条SADD，第一条SADD 64个元素，第二条SADD 36个元素。

4.2.3 AOF后台重写

Redis服务器是单线程，如果由服务器发起AOF重写，那么服务器将阻塞。为了防止这个情况，Redis使用子进程进行AOF重写，在这同时主进程仍然在接受并处理客户端的请求。

因为在子线程重写的过程中，主线程也在处理请求导致数据库状态变化，为了解决数据不一致问题，Redis服务器设置了一个AOF重写缓冲区，这个缓冲区在服务器创建子进程之后开始使用。

在子线程重写的过程中，当Redis服务器执行完一个写命令之后，它会同时将这个写命令发送给AOF缓冲区和AOF重写缓冲区。

这样一来可以保证：

AOF缓冲区的内容会定期被写入和同步到AOF文件，对现有AOF文件的处理工作会如常进行。
从创建子进程开始，服务器执行的所有写命令都会被记录到AOF重写缓冲区里面。

当子进程完成AOF重写工作之后，它会向父进程发送一个信号，父进程在接到该信号之后，会调用一个信号处理函数，并执行以下工作：

将AOF重写缓冲区中的所有内容写入到AOF重写文件中，这时AOF重写文件所保存的数据库状态将和服务器当前的数据库状态一致。
对新的AOF文件进行改名，原子地（atomic）覆盖现有的AOF文件，完成新旧两个AOF文件的替换。

在整个AOF后台重写过程中，只有信号处理函数执行时会对服务器进程（父进程）造成阻塞，在其他时候，AOF后台重写都不会阻塞父进程，这将AOF重写对服务器性能造成的影响降到了最低。

Redis的5种数据类型

Posted on 2019-12-19 | In 中间件 , Redis |

Words count in article: 2.6k | Reading time ≈ 9

前言

Redis是一个key-value存储系统，由C语言编写。

Redis使用对象来表示数据库中的键和值，每次当我们在Redis的数据库中新创建一个键值对时，我们至少会创建两个对象，一个对象用作键值对的键(key对象)，另一个对象用作键值对的值(value对象)。

Redis的每种数据类型全都是套用一种结构的对象(redisObject)。

Redis支持5种对象类型，分别是字符串(string)、列表(list)、哈希(hash)、集合(set)、有序集合(zset)，redisObject使用type字段记录自身属于哪种类型。

而每种对象类型至少使用了两种底层数据结构来实现，redisObject使用编码字段（encoding字段）记录了自己使用的是哪种底层数据结构实现。而*ptr指针则会直接指向这个对应的底层数据结构。

每个对象会用到的编码以及对应的数据结构详见下表，即共8种底层数据结构：

Redis中的键，都是用字符串对象来存储的，即对于Redis数据库中的键值对来说，键总是一个字符串对象，而值可以是字符串对象、列表对象、哈希对象、集合对象或者有序集合对象中的其中一种。

Redis的8种数据结构，我们已经在Redis的8种底层数据结构一文中有过介绍，本文我们来讲Redis支持的5种对象类型

统一的对象——redisObject

Redis的五种数据类型全都是套用一种结构的对象：

redisObject对象实现了基于引用计数技术的内存回收机制和对象共享机制。

因为redis是k-v键值对的缓存数据库，所以每一次我们新建一个k-v键值对时，redis都会创建两个redisObject对象，键总是字符串对象。

这几个属性我们拆开一个个讲：

Type
- redisObject对象根据type的不同会有五种类型，这个字段就是用来标记不同类型的对象的。
- 命令TYPE keyname 可以得到这个type属性。
- 具体值见下表：
- Redis基于类型的多态就是根据type字段来判断的，如DEL,EXPIRE等命令可以针对任何类型的键操作，而SET/GET只能针对字符串键操作，HDEL,HSET只能针对哈希键操作等，这种针对特定类型的命令实现，其实就是在执行命令前先检查一下这个type值。
Ptr内存指针
- Ptr是一个指针，用来指向对象的底层数据结构。
Encoding
- 对象ptr指针指向对象的底层实现数据结构，而到底取用哪个数据结构，则在encoding中标记。
- 后续Redis命令在针对对象进行操作时，也会根据encoding自动选择合适的函数，这是Redis命令的多态。
- 下面是encoding的字面值和各种数据结构的对应：
- 上图中值得注意的是 “跳跃表和字典”。其实在redis中，在使用跳跃表时（其实也就用于有序集合），总会辅助一个字典来提升效率的。这时字典的k-v会分别保存一个元素的成员地址和分值地址。跳跃表和字典的指针共同指向一个数据，这样既不会占用内存，也能利用字典实现 常数级的 定位查找。
Refcount
- Refcount是redisObject对象的引用计数器，redis的内存回收是引用计数法，规则如下：
  - 当一个新对象创建时，refcount被设置为1。
  - 当对象被一个程序引用时，refcount +1
  - 不再被某个对象引用时，refcount – 1
  - Refcount为0时，对象被释放
- Refcount的功能为redis的对象共享提供了可能性，为了节约内存，Redis中大量使用了指针，前面就说过，跳跃表和字典的结合中就大量用到了内存共享。他们相互对应的节点中，指针被指向了同一个对象。
- 比如为键A新创建了一个整数值为100的字符串对象C，如果键B的值也是100，那么value指针就会指向C，C对象的refcount+1
- 限于cpu时间的限制，redis只对包含整数值的字符串对象进行共享。
Lru
- Lru属性记录了该对象最后一次被命令访问的时间
- 通过它，Redis可以得到这个对象的闲置时间，从而在服务器被占用的内存大小超过maxmenmory时，空转时间长的对象会被优先释放。

1 字符串对象

字符串对象的编码可以是int、raw或者embstr。或者说，字符串对象的encoding只能是REDIS_ENCODING_INT，REDIS_ENCODING_EMBSTR和REDIS_ENCODING_RAW。

场景	prt和encoding的值
如果保存的字符串是整数值，并且这个整数值可以用long类型来表示	Ptr属性中，void*会转化成long，encoding改为REDIS_ENCODING_INT
保存的字符串不是整数值，且长度大于39字节（包含可以用long double 类型保存的浮点数）	Ptr属性中，void*会转化成SDS，encoding为REDIS_ENCODING_RAW
保存的字符串保存的字符串不是整数值，且长度小于等于39字节	Ptr属性中，void*会转化成embstr，encoding为REDIS_ENCODING_EMBSTR

下图展示了一个当ptr指向SDS时的字符串对象的结构：

注意：当字符串改变，直到不满足上述各自条件时，embstr和int会被转换为raw类型。

注意：Embstr实际上是只读的，因为redis没有为它编写任何的修改函数，所以对它进行任何操作，它都会先转换为raw，然后再执行命令，且不会变回来。

2 列表对象

列表对象的编码可以是压缩链表ziplist或者双端链表linkedlist，encoding取值REDIS_ENCODING_ZIPLIST或者REDIS_ENCODING_LINKEDLIST。

场景	prt和encoding的值
当列表保存的所有字符串元素的长度都小于64字节，且元素的数量小于512	Ptr指向一个ziplist，encoding改为REDIS_ENCODING_ZIPLIST
否则	Ptr指向一个linkedlist，encoding改为REDIS_ENCODING_LINKEDLIST

当列表对象被改变，使其无法满足上述条件时，ziplist会向linkedlist迁移

2.1 列表对象中的Ziplist

Ziplist是一种压缩链表，它的好处是更能节省内存空间，因为它所存储的内容都是在连续的内存区域当中的。
当列表对象元素不大，每个元素也不大的时候，就采用Ziplist存储。
但当数据量过大时就ziplist就不是那么好用了。因为为了保证他存储内容在内存中的连续性，插入的复杂度是O(N)，即每次插入都会重新进行realloc。
如下图所示，对象结构中ptr所指向的就是一个Ziplist。整个Ziplist只需要malloc一次，它们在内存中是一块连续的区域。

2.2 列表对象中的Linkedlist

linkedlist是一种双向链表。它的结构比较简单，节点中存放pre和next两个指针，还有节点相关的信息。
当每增加一个node的时候，就需要重新malloc一块内存。

3 哈希对象

哈希对象的底层实现可以是ziplist或者dict。Encoding的值可以是压缩链表REDIS_ENCODING_ZIPLIST或者字典REDIS_ENCODING_HT

场景	prt和encoding的值
对象保存的所有键值对的键和值的字符串长度都小于64字节，且键值对数量小于512	Ptr指向一个ziplist，encoding改为REDIS_ENCODING_ZIPLIST
否则	Ptr指向一个dict，encoding改为REDIS_ENCODING_HT

3.1 哈希对象中的ziplist

ziplist中的哈希对象是按照key1,value1,key2,value2这样的顺序存放来存储的。
新的键值插入表尾，先是key节点，紧接着value节点。因此同一键值对的两个节点总是紧挨在一起，key在前，value在后。
先添加的k-v靠近表头，后添加的靠近表尾，当对象数目不多且内容不大时，这种方式效率是很高的。

3.2 哈希对象中的dict

之前已经介绍过dict了，字典中，dicht[0] 是用于真正存放数据，dicht[1]一般在哈希表元素过多进行rehash的时候用于中转数据。

dictht中的table用于真正存放元素，每个key/value对用一个dictEntry表示，放在dictEntry数组中。

4 集合对象

集合对象的编码可以是intset或者dict。Encoding可以是整数集合REDIS_ENCODING_INTSET或者字典REDIS_ENCODING_HT。

场景	prt和encoding的值
当集合对象保存的所有元素都是整数值，且元素数量不超过512个	Ptr指向一个intset，encoding改为REDIS_ENCODING_ZIPLIST
否则	Ptr指向一个dict，encoding改为REDIS_ENCODING_HT

注意：当使用哈希表作为集合对象的底层实现时，字典的每一个键都是一个字符串对象，用来保存集合元素，而字段的值都被设置为null。联想一下JAVA的keySet，这方式跟set和hashmap的关系是一样的。

5 有序集合对象

有序集合的编码可能两种，一种是ziplist，另一种是skiplist与dict的结合。

场景	prt和encoding的值
有序集合保存的元素数量小于128，且所有成员的长度都小于64字节	Ptr指向一个ziplist，encoding改为REDIS_ENCODING_ZIPLIST
否则	Ptr指向一个skiplist和dict的结合体，encoding改为REDIS_ENCODING_SKIPLIST

4.1 有序集合对象中的ziplist

ziplist作为集合和作为哈希对象是一样的，member和score顺序紧凑的存放。
按照score从小到大顺序排列。它的结构不再复述。

4.2 有序集合对象中的跳跃表和字典合用

前面讲过：
在使用跳跃表时（其实也就用于有序集合），总会辅助一个字典来提升效率的。这时字典的k-v会分别保存一个元素的成员地址和分值地址。跳跃表和字典的指针共同指向一个数据，这样既不会占用内存，也能利用字典实现常数级的定位查找。

例如：

如果我们只使用字典，那么虽然我们可以以O(1)复杂度查找成员的分值，但是因为字典以无序的方式存储，所以在执行注入zrank之类的范围型命令时，还需要重排序。至少需要O(NlogN)的时间复杂度和O(N)的空间复杂度。
反之，我们查找分值这一操作，将需要O(logN)的复杂度。

Redis的8种底层数据结构

Posted on 2019-12-19 | In 中间件 , Redis |

Words count in article: 10.6k | Reading time ≈ 40

前言

Redis是一个key-value存储系统，由C语言编写。和Memcached类似，它支持存储的value类型相对更多，包括string(字符串)、list(链表)、set(集合)、zset(sorted set –有序集合)和hash（哈希类型），这些数据类型都支持push/pop、add/remove及取交集并集和差集及更丰富的操作，而且这些操作都是原子性的。
在此基础上，Redis支持各种不同方式的排序。与memcached一样，为了保证效率，数据都是缓存在内存中。区别的是Redis会周期性的把更新的数据写入磁盘或者把修改操作写入追加的记录文件，并且在此基础上实现了master-slave(主从)同步。

Redis是一个高性能的key-value数据库。 Redis的出现，很大程度补偿了memcached这类key/value存储的不足，在部分场合可以对关系数据库起到很好的补充作用。它提供了Java，C/C++，C#，PHP，JavaScript，Perl，Object-C，Python，Ruby，Erlang等客户端，使用很方便。
Redis支持主从同步。数据可以从主服务器向任意数量的从服务器上同步，从服务器可以是关联其他从服务器的主服务器。这使得Redis可执行单层树复制。存盘可以有意无意的对数据进行写操作。由于完全实现了发布/订阅机制，使得从数据库在任何地方同步树时，可订阅一个频道并接收主服务器完整的消息发布记录。同步对读取操作的可扩展性和数据冗余很有帮助。

Redis的作者叫Salvatore Sanfilippo，来自意大利的西西里岛，现在居住在卡塔尼亚。目前供职于Pivotal公司。他使用的网名是antirez。

Redis的5种对象与8种数据结构

Redis的每种数据类型全都是套用一种结构的对象(redisObject)。

Redis支持5种对象类型，分别是字符串(string)、列表(list)、哈希(hash)、集合(set)、有序集合(zset)，redisObject使用type字段记录自身属于哪种类型。

每个对象会用到的编码以及对应的数据结构详见下表，即共8种底层数据结构：

Redis中的键，都是用字符串对象来存储的，即对于Redis数据库中的键值对来说，键总是一个字符串对象，而值可以是字符串对象、列表对象、哈希对象、集合对象或者有序集合对象中的其中一种。

那么，我们首先先从底层开始，了解一下Redis的8种数据结构。

Reids的8种底层数据结构

1 整数

如果保存的字符串是整数值，并且这个整数值可以用long类型来表示，那么ptr指针的void*则转化为C语言源生的long类型，这个无须多言。

2 简单动态字符串SDS

在Redis中，只有在使用到不会被修改的字符串字面量时（比如打印日志），Redis才会采用c语言传统的字符串（以空字符结尾的字符数组），而在Redis数据库中，所有的字符串在底层都由SDS来实现的。

2.1 SDS数据结构

被重新定义过的字符串对象（SDS）是Redis的基本存储类型，一个SDS字符串的完整结构，由在内存地址上前后相邻的两部分组成（header和char数组）。如下图，SDS字符串有多种类型，不同类型的SDS字符串是为了保存不同长度的内容。

header——我们把上图中非char数组（变量名为buf）的部分都统称为header，其成员有：
- 第一个成员变量len记录的是为buf分配的内存空间已使用的长度，即我们看见的，有效的字符串；
- 第二个成员变量alloc记录的是为buf分配的内存空间的总长度，alloc – len 就是未使用的空间，当然这长度不包括SDS字符串头和结尾NULL。
- 第三个字符flags只使用了低三位表示类型，值为0-4，分别表示sdshdr5到sdshdr64这五种类型。高五位没有用处，目的是根据字符串的长度的不同选择不同的sds结构体。
  - 为何要定义不同的结构体：结构体的主要区别是len和alloc的类型（uint8，uint16等等），定义不同的结构体是为了存储不同长度的字符串，根据不同长度定义不同的类型是为了节省一部分空间大小，毕竟在Redis字符串非常多，哪怕一点点优化积累起来都很可观。
  - flags字段的用处：由于SDS字符串结构的设计，在我们需要访问header中成员变量时，需要通过sds指针向前回溯一个头结构体的长度，然后通过这个地址去访问。至于回溯多长，则要视该SDS字符串的类型而定，而这个信息就保存在sds指针前一个unsigned char长度的空间中——即flags。
char数组
- 这是一个没有指明长度的字符数组，这是C语言中定义字符数组的一种特殊写法，称为柔性数组（flexible array member），只能定义在一个结构体的最后一个字段上。它在这里只是起到一个标记的作用，表示在flags字段后面就是一个字符数组，或者说，它指明了紧跟在flags字段后面的这个字符数组在结构体中的偏移位置。而程序在分配内存的时候，一开始它并不占用内存空间。
- 这个字符数组的长度等于最大容量+1。之所以字符数组的长度比最大容量多1个字节，就是为了在字符串长度达到最大容量时仍然有1个字节NULL结束符，即ASCII码为0的’\0’字符，这样字符串可以和c语言源生的字符串兼容。
- 与其他的结构体不同，sdshdr5没有定义char数组和alloc字段，他的值存储在flag没有被使用的高五位中，所以sdshdr5对应的SDS_TYPE_5类型字符串只能保存原串长度小于等于2^5 = 32，因此，它不能为字符串分配空余空间。如果字符串需要动态增长，那么它就必然要重新分配内存才行。所以说，这种类型的sds字符串更适合存储静态的短字符串
  
  2.2 sds的代码

sdsnewlen()方法可以用来申请sds。

1	sds sdsnewlen(const void *init, size_t initlen);

第一个参数是sds中字符串的内容,initlen则是第一次初始化的长度。

首先会根据第一次初始化所需要的长度根据其所占位数通过sdsReqType()得到内存的结构体。

static inline char sdsReqType(size_t string_size) {
    if (string_size < 1<<5)
        return SDS_TYPE_5;
    if (string_size < 1<<8)
        return SDS_TYPE_8;
    if (string_size < 1<<16)
        return SDS_TYPE_16;
#if (LONG_MAX == LLONG_MAX)
    if (string_size < 1ll<<32)
        return SDS_TYPE_32;
    return SDS_TYPE_64;
#else
    return SDS_TYPE_32;
#endif
}

但是，如果一开始申请的是一个初试长度为0的空字符串，那么并不是按照最小的5位容量，还是为了方便这类空字符串的后续添加，直接申请8位容量。

1	if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;

sds的扩容，如果原有结构的长度已经无法满足扩容后的需要的长度，那么会根据新扩容的长度重新确定存储的结构体。

if (type == SDS_TYPE_5) type = SDS_TYPE_8;
    hdrlen = sdsHdrSize(type);
    if (oldtype==type) {
        newsh = s_realloc(sh, hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else {
        /* Since the header size changes, need to move the string forward,
         * and can't use realloc */
        newsh = s_malloc(hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        memcpy((char*)newsh+hdrlen, s, len+1);
        s_free(sh);
        s = (char*)newsh+hdrlen;
        s[-1] = type;
        sdssetlen(s, len);
    }
    sdssetalloc(s, newlen);
    return s;

2.3 使用sds结构的优点

1.有利于减少内存碎片，提高存储效率
- 在各个header的定义中使用了attribute ((packed))，是为了让编译器以紧凑模式来分配内存。如果没有这个属性，编译器可能会为struct的字段做优化对齐，在其中填充空字节。那样的话，就不能保证header和sds的数据部分紧紧前后相邻，也不能按照固定向低地址方向偏移1个字节的方式来获取flags字段了。这样利于获取header字段，提高性能。
2.常数复杂度获取字符串长度
- C语言源生的获取字符串长度的方式是遍历整个char数组，因此复杂度为O(N)，SDS采用len字段记录长度，且header和char数组紧凑排列，获取的复杂度为O(1)。设置和更新SDS长度的工作是由SDS的api在执行时自动完成的。
3.杜绝缓冲区溢出
- C语言字符串不记录自身长度，也容易造成缓冲区溢出。而当SDS对自身字符串进行修改时，API会先检查SDS的剩余空间是否满足需要（获取alloc减len），如果不满足，则会先拓展空间，再执行API。
4.空间预分配
- SDS在重新分配空间的时候，会预分配一些空间来作为冗余。当SDS的len属性长度小于1MB时，Redis会分配和len相同长度的free空间。至于为什么这样分配呢，上次用了len长度的空间，那么下次程序可能也会用len长度的空间，所以Redis就为你预分配这么多的空间。
- 但是当SDS的len属性长度大于1MB时，程序将多分配1M的未使用空间。这个时候我在根据这种惯性预测来分配的话就有点得不偿失了。所以Redis是将1MB设为一个风险值，没过风险值你用多少我就给你多少，过了的话那这个风险值就是我能给你临界值。
5.惰性空间释放
- Redis的内存回收采用惰性回收，即你把字符串变短了，那么多余的内存空间也不会立刻还给操作系统，先留着，用header的字段将其记录下来，以防接下来又要被使用呢。
6.二进制安全
- 因为’\0’字符串在SDS中没有意义，他作为结束符的任务已经被header字段给替代了，所以与c语言不一样的，SDS是二进制安全的。
  3 embstr

embstr编码是专门用来保存短字符串的一种优化编码方式，其实他和raw编码一样，底层都会使用SDS，只不过raw编码是调用两次内存分配函数分别创建redisObject和SDS，而embstr只调用一次内存分配函数来分配一块连续的空间，embstr编码的的redisObject和SDS是紧凑在一起的。

其优势是：

embstr的创建只需分配一次内存，而raw为两次（一次为sds分配对象，另一次为objet分配对象，embstr省去了第一次）。
相对地，释放内存的次数也由两次变为一次。
embstr的objet和sds放在一起，更好地利用缓存带来的优势。

不过很显然，紧凑型的方式只适合短字符串，长字符串占用空间太大，就没有优势了。

如果字符串对象保存的是一个字符串值，并且这个字符串值的长度小于等于 39 字节，那么字符串对象将使用 embstr 编码的方式来保存这个字符串值。否则采用raw编码的SDS来存储。这在3.0以上版本的Redis出现。

至于为什么是39?
embstr是一块连续的内存区域，由redisObject和sdshdr组成。其中redisObject占16个字节，当buf内的字符串长度是39时，sdshdr的大小为8+8+39+1=56，那一个字节是’\0’。加起来刚好64。

从2.4版本开始，Redis开始使用jemalloc内存分配器。在这里可以简单理解，jemalloc会分配8，16，32，64等字节的内存。embstr中即便sdshdr的buf为空，最小空间占用也为16+8+8+1=33，所以jemalloc低三档的分配粒度无法满足embstr，最少也要分配64字节。故而当字符数小于39时，都会分配64字节。默认39就是这么来的。

4 双端链表 linkedlist

C语言中没有内置链表结构，Redis构建了自己的链表实现。list的容量是2的32次方减1个元素，即最多有4294967295个元素数量。

4.1 链表的数据结构

列表的节点（注意不是列表的定义）定义如上，除了双向链表必须的前后指针外，为了实现通用性，支持不同类型数据的存储，Redis将节点类型的数据域定义为void *类型，从而模拟了“泛型”。
整个列表定义如下：

在链表结构中，Redis定义了三个字段和三个函数：

字段：
- listNode *head; // 指向链表的头结点
- listNode *tail; // 指向链表的尾节点
- unsigned long len; // 链表长度
函数：
- void *(*dup)(void *ptr); // 节点值复制函数，用于复制某个节点的值
- void (*free)(void *ptr); // 节点值释放函数，用于释放某个节点的值
- int (*match)(void *ptr, void *key); // 节点值对比函数，用于对比节点的值和另一个输入值是否相等

5 字典 dict

在Redis中，字典的结构可以简单归纳如下：

5.1 Dict的数据结构

Redis定义了dictEntry、dictType、dictht和dict四个结构体来实现哈希表的功能。它们具体定义如下：

5.1.1 dictEntry结构体

/* 保存键值（key - value）对的结构体，类似于STL的pair。*/
typedef struct dictEntry {
    // 关键字key定义
    void *key;  
    // 值value定义，只能存放一个被选中的成员
    union {
        void *val;      
        uint64_t u64;   
        int64_t s64;    
        double d;       
    } v;
    // 指向下一个键值对节点
    struct dictEntry *next;
} dictEntry;

5.1.2 dictType结构体

/* 定义了字典操作的公共方法，类似于adlist.h文件中list的定义，将对节点的公共操作方法统一定义。搞不明白为什么要命名为dictType */
typedef struct dictType {
    /* hash方法，根据关键字计算哈希值 */
    unsigned int (*hashFunction)(const void *key);
    /* 复制key */
    void *(*keyDup)(void *privdata, const void *key);
    /* 复制value */
    void *(*valDup)(void *privdata, const void *obj);
    /* 关键字比较方法 */
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    /* 销毁key */
    void (*keyDestructor)(void *privdata, void *key);
    /* 销毁value */
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

5.1.3 dictht结构体

/* 哈希表结构 */
typedef struct dictht {
    // 散列数组。
    dictEntry **table;
    // 散列数组的长度
    unsigned long size;
    // sizemask等于size减1
    unsigned long sizemask;
    // 散列数组中已经被使用的节点数量
    unsigned long used;
} dictht;

5.1.4 dict结构体

/* 字典的主操作类，对dictht结构再次包装  */
typedef struct dict {
    // 字典类型
    dictType *type;
    // 私有数据
    void *privdata;
    // 一个字典中有两个哈希表
    dictht ht[2];
    //rehash的标记，rehashidx==-1，表示没在进行rehash
    long rehashidx; 
    // 当前正在使用的迭代器的数量
    int iterators; 
} dict;

5.1.5 dict结构总结

上面的结构体如果看得你头昏脑胀，没有关系，下面两张图让你理清他们的关系：

可以很清楚的看到，字典通过“拉链法”来解决冲突问题的，dictEntry结构体的*next指针指向了其拉链列表的下一个节点。

上图中，dict是字典的包装对象，居于最外层。
ht[2]是包含两个项的哈希表的数组，一般情况下，只使用h[0]，h[1]只有在rehash的时候才会使用

dictht是哈希表的结构，他除了一个数组table用来存放键值对以外，还有used字段表示目前已有键值对，size表示数组大小，sizemark=size-1，用来hash索引。
dictType是类型特定函数，上图中从上到下，依次是：
1. HashFunction 计算哈希值的函数
2. KeyDup 复制键的函数
3. ValDup 复制值的函数
4. KeyCompare 对比键的函数
5. KeyDestructor 销毁键的函数
6. ValDestructor 销毁值的函数

5.2 dict的哈希算法

Redis提供了三种不同的散列函数，分别是：

使用Thomas Wang’s 32 bit Mix哈希算法，对一个整型进行哈希，该方法在dictIntHashFunction函数中实现。

unsigned int dictIntHashFunction(unsigned int key)      //用于计算int整型哈希值的哈希函数
{
	key += ~(key << 15);
	key ^=  (key >> 10);
	key +=  (key << 3);
	key ^=  (key >> 6);
	key += ~(key << 11);
	key ^=  (key >> 16);
	return key;
}

使用MurmurHash2哈希算法对字符串进行哈希，该方法在dictGenHashFunction函数中实现。(当字典被用作数据库的底层实现，或者哈希键的底层实现时，Redis用MurmurHash2算法来计算哈希值，能产生32-bit或64-bit哈希值。)

unsigned int dictGenHashFunction(const void *key, int len) {  //用于计算字符串的哈希值的哈希函数
	//m和r这两个值用于计算哈希值，只是因为效果好。
	uint32_t seed = dict_hash_function_seed;
	const uint32_t m = 0x5bd1e995;
	const int r = 24;
	/* Initialize the hash to a 'random' value */
	uint32_t h = seed ^ len;    //初始化
	/* Mix 4 bytes at a time into the hash */
	const unsigned char *data = (const unsigned char *)key;
	//将字符串key每四个一组看成uint32_t类型，进行运算的到h
	while(len >= 4) {
		uint32_t k = *(uint32_t*)data;
		k *= m;
		k ^= k >> r;
		k *= m;
		h *= m;
		h ^= k;
		data += 4;
		len -= 4;
	}
	/* Handle the last few bytes of the input array  */
	switch(len) {
	case 3: h ^= data[2] << 16;
	case 2: h ^= data[1] << 8;
	case 1: h ^= data[0]; h *= m;
	};
	/* Do a few final mixes of the hash to ensure the last few
	 * bytes are well-incorporated. */
	h ^= h >> 13;
	h *= m;
	h ^= h >> 15;
	return (unsigned int)h;
}

在dictGenCaseHashFunction函数中提供了一种比较简单的djb哈希算法，对字符串进行哈希。（djb哈希算法，算法的思想是利用字符串中的ascii码值与一个随机seed，通过len次变换，得到最后的hash值。）

unsigned int dictGenCaseHashFunction(const unsigned char *buf, int len) {   //用于计算字符串的哈希值的哈希函数
	unsigned int hash = (unsigned int)dict_hash_function_seed;

	while (len--)
		hash = ((hash << 5) + hash) + (tolower(*buf++)); /* hash * 33 + c */
	return hash;
}

5.3 dict的rehash

当哈希表的大小不能满足需求，就可能会有两个或者以上数量的键被分配到了哈希表数组上的同一个索引上，于是就发生冲突（collision），在Redis中解决冲突的办法我们提到过是拉链法（separate chaining）。

但是我们仍然需要尽可能避免冲突，希望哈希表的负载因子（load factor），维持在一个合理的范围之内，就需要对哈希表进行扩展或收缩。

Rehsh会根据负载因子（load_factor = ht[0].used/ht[0].size）调整，当满足如下任意条件时，哈希表会rehash拓展：

在服务器没有执行BGSAVE或BGREWRITEAOF，即没有持久化数据的时候，如果负载因子大于等于1
在服务器正在执行BGSAVE或BGREWRITEAOF时，如果负载因子大于等于5

Rehash扩展有三个步骤:

扩展备用的ht[1]，将它的容量扩张到第一个大于ht[0].used*2的 2的n次方
将ht[0]的值重新经过hash索引之后迁移到ht[1]上。
释放ht[0]，将ht[1]设为ht[0]，创建新的空表ht[1]。

注意：当负载因子小于0.1时，进行收缩操作，步骤将上述三步中的大于变为小于就是

5.3.1 Rehash是渐进式的

Rehash不是一步完成的，而是在操作过程中渐进式的。字典维持一个索引计数器rehashidx用来记录当前正在操作的索引，从ht[0]的0号索引上开始，一个项一个项的迁移到ht[1]，直到完成所有迁移，rehashidx变成-1。

在rehash期间，所有新增字段添加在ht[1]中，而删除，更新操作会在两个表上同时进行。查找时先找ht[0]，再找ht[1]。

6 跳跃表 skiplist

跳跃表是有序集合zset的底层实现之一（另一个是压缩列表），当元素数量比较多，或者元素成员是比较长的字符串时，底层实现采用跳跃表。

跳跃表是一种有序数据结构，他在一个节点中维持多个指向其他节点的指针

跳跃表的平均复杂度为O(logN)，最坏为O(N)，其效率可以和平衡树相媲美，而且跟平衡树相比，实现简单；

6.1 平衡的跳跃表

如图：每一个竖列其实是一个节点。如果能通过在节点中维持多个指向不同节点的指针（比如node4（值为21）就有三个指针，分别指向node5（33），node6（37），node8（55）），那么就会得到一个平衡的跳跃表。

在平衡的跳跃表中是左右对称的，node2两层，node4三层，node8四层。这样查到某一个节点的复杂度都为O(logN)：

比如要查46，可以走L4到55，再用55的后退指针得到46。
比如要查37，先走L2层到21，再前进一步得到33。

可以看到，上述表中，找到任何一个节点，时间复杂度不超过两次跳跃。

但是，跳跃表最难的，就是保持平衡，维持平衡的跳跃表难度要大于维持平衡的二叉树。故而易于实现的，是实现概率平衡，而不是强制平衡

6.1.1 跳跃表的查询

跳跃表的查询是从顶层往下找，那么会先从第顶层开始找，方式就是循环比较，如过顶层节点的下一个节点为空说明到达末尾，会跳到第二层，继续遍历，直到找到对应节点。

例子：查找元素 117

比较 21，比 21 大，且21有后继，向后面找
比较 37, 比 37大，且37节点同层没有后继了，则从 37 的下面一层开始找
比较 71, 比 71 大，且71节点同层没有后继了，则从 71 的下面一层开始找
比较 85，比 85 大，且85有后继，向后面找
比较 117，等于 117，找到了节点。

6.1.2 跳表的删除

使用标准的 delete from list 方法删除该节点。

6.2 Redis中的跳跃表的实现

为了尽可能的维持理想的跳跃表，Redis根据幂次定律来使跳跃表尽可能的平衡，我们先看Redis中跳跃表和跳跃表节点的结构：

我们逐个分析

zskiplistNode 表示跳跃表节点结构
- ele是个SDS，是有序集合的值element。
- Score是double结构，存储分数值。
- Backward，后退指针，指向列表前一个node。
- Level [ ]数组，表示一个节点可以有多个层。
  - 数组里面的项是zskiplistLevel结构，可以看到，每一层都有一个跳跃指针forward。
  - 跨度span，顾名思义，就是用来记录跨度的，相邻的节点跨度为1。
  - 注意：跨度的用处是用来计算某个节点在跳跃表中的排位的，zset的排序按score从小到大排序。比如我查找到node7，通过将沿途的所有跨度累加，我们可以得到其排在列表中的序列。
zskiplist 表示跳跃表结构
- zskiplist中有指向整个跳跃表两端的head指针和tail指针
- 记录跳跃表长度的leng字段。
- Int型的level用来记录目前整个跳跃表中最高的层数。

6.3 一般情况下维持平衡跳跃表的实现

在跳跃表中插入一个新的节点时，程序需要确定两个要素：该节点的位置，以及层数
因为有序集合按照score排序，故而位置可以按照score比出，确定位置。
确定了位置后，再确定node的层数，可以采用抛硬币的方式，一次正面，层数+1，直到反面出现为止。因为抛硬币会使层数L的值满足参数为 p = 1/2 的几何分布，在数量足够大时，可以近似平衡。
用抛硬币的方式，可以使level+1的概率为2分之一，也就是说，k层节点的数量是k+1层的1/2 ，你可以把它看成是一个二叉树。

6.4 Redis维持平衡跳跃表的实现

与上述抛硬币的方式大同小异，Redis根据幂次定律维持一个尽可能理想的跳跃表（即节点数尽可能大时，整个链表尽可能平衡。）

6.4.1 幂次定律

含义是：如果某件事的发生频率和它的某个属性成幂关系，那么这个频率就可以称之为符合幂次定律。
表现是：少数几个事件的发生频率占了整个发生频率的大部分，而其余的大多数事件只占整个发生频率的一个小部分。
说人话版：越大的数，出现的概率越小。

6.4.2 实现算法

当Redis在跳跃表中插入一个新的节点时，程序需要确定两个要素：该节点的位置，以及层数
Redis的实现与一般维持平衡跳跃表的实现大同小异，Redis中跳跃表的层数也是在插入的时候确定，按照分数找好位置后，Redis会生成一个1-32的数作为层数。
Redis的level+1的概率是1/4,所以Redis的跳跃表是一个四叉树。

level = zslRandomLevel();

//下面是 zslRandomLevel() 函数的具体实现：
/* Returns a random level for the new skiplist node we are going to create.
 * The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL
 * (both inclusive), with a powerlaw-alike distribution where higher
 * levels are less likely to be returned. */
 //这个函数返回一个随机值，范围在：1 到 ZSKIPLIST_MAXLEVEL 之间，最小值为 1。
int zslRandomLevel(void) {
    int level = 1;

    //(random()&0xFFFF 得到 <= 0xFFFF的随机数，这个随机数比ZSKIPLIST_P * 0xFFFF小的概率为ZSKIPLIST_P。
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;

    //最大不会超过ZSKIPLIST_MAXLEVEL
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;

    //每一次while为true的概率都为ZSKIPLIST_P，换个角度想就是level n的概率为 ZSKIPLIST_P ^ (n-1)。
}

ZSKIPLIST_P=0.25，所以Redis的跳跃表是一个四叉树。

7 整数集合 intset

整数集合是set的底层实现之一，当一个集合中只包含整数值，并且元素数量不多时，redis使用整数集合作为set的底层实现。

7.1 数据结构

Encoding 存储编码方式
Length inset的长度，即元素数量
Content Int数组，用来保存元素，各个项在数组中按数值从小到大排序，不包含重复项

注意：虽然content数组的结构是int8_t，但其实他不会存储任何int8_t类型的值，当encoding=INTSET_ENC_INT16，那么他存的就是int16_t。以此类推，还有int32和int64。

7.2 整数集合的升级

当在一个int16类型的整数集合中插入一个int32类型的值，整个集合的所有元素都会转换成32类型。
整个过程有三步：

根据新元素的类型（比如int32），扩展整数集合底层数组的空间大小，并为新元素分配空间。
将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放置到正确的位上，而且在放置元素的过程中，需要继续维持底层数组的有序性质不变。
最后改变encoding的值，length+1。

举个例子，假设现在有一个INTSET_ENC_INT16编码的整数集合，集合中包含三个 int16_t 类型的元素。

因为每个元素都占用 16 位空间，所以整数集合底层数组的大小为 3 * 16 = 48 位，图 6-4 展示了整数集合的三个元素在这 48 位里的位置。

现在，假设我们要将类型为 int32_t 的整数值 65535 添加到整数集合里面，因为 65535 的类型 int32_t 比整数集合当前所有元素的类型都要长，所以在将 65535 添加到整数集合之前，程序需要先对整数集合进行升级。

升级首先要做的是，根据新类型的长度，以及集合元素的数量（包括要添加的新元素在内），对底层数组进行空间重分配。

整数集合目前有三个元素，再加上新元素 65535 ，整数集合需要分配四个元素的空间，因为每个 int32_t 整数值需要占用 32 位空间，所以在空间重分配之后，底层数组的大小将是 32 * 4 = 128 位，如图 6-5 所示。

虽然程序对底层数组进行了空间重分配，但数组原有的三个元素 1 、 2 、 3 仍然是 int16_t 类型，这些元素还保存在数组的前 48 位里面，所以程序接下来要做的就是将这三个元素转换成 int32_t 类型，并将转换后的元素放置到正确的位上面，而且在放置元素的过程中，需要维持底层数组的有序性质不变。

首先，因为元素 3 在 1 、 2 、 3 、 65535 四个元素中排名第三，所以它将被移动到 contents 数组的索引 2 位置上，也即是数组 64 位至 95位的空间内。因为元素 2 在 1 、 2 、 3 、 65535 四个元素中排名第二，所以它将被移动到 contents 数组的索引 1 位置上，也即是数组的 32 位至 63 位的空间内，如图 6-7 所示。

之后，因为元素 1 在 1 、 2 、 3 、 65535 四个元素中排名第一，所以它将被移动到 contents 数组的索引 0 位置上，也即是数组的 0 位至 31位的空间内，如图 6-8 所示。

然后，因为元素 65535 在 1 、 2 、 3 、 65535 四个元素中排名第四，所以它将被添加到 contents 数组的索引 3 位置上，也即是数组的 96 位至 127 位的空间内，如图 6-9 所示。

最后，程序将整数集合 encoding 属性的值从 INTSET_ENC_INT16 改为 INTSET_ENC_INT32 ，并将 length 属性的值从 3 改为 4 ，设置完成之后的整数集合如图 6-10 所示。

因为每次向整数集合添加新元素都可能会引起升级，而每次升级都需要对底层数组中已有的所有元素进行类型转换，所以向整数集合添加新元素的时间复杂度为 O(N) 。

注意，整数集合只支持升级操作，不支持降级操作

升级之后新元素的摆放位置如何确定？因为引发升级的新元素的长度总是比整数集合现有所有元素的长度都大，所以这个新元素的值要么就大于所有现有元素，要么就小于所有现有元素（负数）：

在新元素小于所有现有元素的情况下，新元素会被放置在底层数组的最开头（索引 0 ）；

在新元素大于所有现有元素的情况下，新元素会被放置在底层数组的最末尾（索引 length-1 ）。

8 压缩列表 ziplist

压缩列表是list，hash和zset的底层实现之一，当一个列表只包含少量元素，并且每个元素要么就是小整数值，要么就是长度比较短的字符串，那么Redis使用ziplist作为列表实现。

压缩表是为了节约内存而开发的，压缩表可以包含任意个节点，每个节点保存一个字节数组（字符串）或一个整数值。

8.1 压缩表数据结构

Zlbytes 类型：uint32_t 记录整个压缩表占用的内存字节数，对压缩表进行内存重分配和或者计算zlend位置时被使用
Zltail_offset 类型：uint32_t 记录压缩列表尾节点entryN距离压缩列表的起始地址的字节数。用来快速确定表尾节点的地址。
Zllength 类型：uint16_t 若不超过uint16的极值65535，就是记录着压缩表节点的数量。否则，真实的节点数量需要遍历压缩表才能得出
Zlend 类型：uint8_t 特殊值0xFF（十进制255），用于标记表的末端。
Entry char[]或uint 长度不定，节点的长度随保存的内容而改变。

8.2 压缩表节点的结构

prevrawlen：前置节点的长度（以字节为单位）
prevrawlensize：存储 prevrawlen 的值所需的字节大小
len：当前节点的长度
lensize：存储 len 的值所需的字节大小
headersize：当前节点 header 的大小，等于 prevrawlensize + lensize
encoding：当前节点值所使用的编码类型
p：指向当前节点的指针

虽然定义了这个结构体，但是Redis根本就没有使用zlentry结构来作为压缩列表中用来存储数据节点中的结构，这个结构总共在32位机占用了28个字节(32位机)，在64位机占用了32个字节。这不符合压缩列表的设计目的：提高内存的利用率。

ziplist在存储节点信息时，并没有将zlentry数据结构所有属性保存，而是做了简化。

虽然在压缩列表中使用的是”压缩版”的zlentry结构，但是在对节点操作时，还是要将”压缩版” “翻译”到zlentry结构中，因为我们无法对着一串字符直接进行操作。

因此，就有了下面的函数：

/* Return a struct with all information about an entry. */
// 将p指向的列表节点信息全部保存到zlentry中，并返回该结构
static zlentry zipEntry(unsigned char *p) {
    zlentry e;

    // e.prevrawlensize 保存着编码前一个节点的长度所需的字节数
    // prevrawlen 保存着前一个节点的长度
    ZIP_DECODE_PREVLEN(p, e.prevrawlensize, e.prevrawlen);  //恢复前驱节点的信息

    // p + e.prevrawlensize将指针移动到当前节点信息的起始地址
    // encoding保存当前节点的编码格式
    // lensize保存编码节点值长度所需的字节数
    // len保存这节点值的长度
    ZIP_DECODE_LENGTH(p + e.prevrawlensize, e.encoding, e.lensize, e.len);  //恢复当前节点的信息

    //当前节点header的大小 = lensize + prevrawlensize
    e.headersize = e.prevrawlensize + e.lensize;    
    e.p = p;    //保存指针
    return e;
}

//ZIP_DECODE_PREVLEN和ZIP_DECODE_LENGTH都是定义的两个宏，在ziplist.c文件中

8.2.1 prev_entry_len

prev_entry_len成员实际上就是zlentry结构中prevrawlensize(记录存储prevrawlen值的所需的字节个数)和prevrawlen(记录着上一个节点的长度)这两个成员的压缩版。

如果前一节点的长度小于254（即2^8-1）字节，则pre_entry_len用一个字节记录其长度。
当前驱节点的长度大于等于255（即2^8-1）字节，那么prev_entry_len使用5个字节表示。
- 并且用5个字节中的最高8位(最高1个字节)用 0xFE来标志prev_entry_len占用了5个字节，后四个字节才是真正保存前驱节点的长度值。
pre_entry_len最大的用处是用来从后向前遍历，因为前一个节点的指针c = 当前节点指针p –pre_entry_len，可以快速往前上溯。

因为，对于访问的指针都是char 类型，它能访问的范围为1个字节，如果这个字节的大小等于0xFE，那么就会继续向后访问四个字节来获取前驱节点的长度，如果该字节的大小小于0xFE，那么该字节就是要获取的前驱节点的长度。因此这样就使prev_entry_len同时具有了prevrawlen和prevrawlensize的功能，而且更加节约内存。

8.2.2 encoding

prev_entry_len一样，encoding成员同样可以看做成zlentry结构中lensize（记录存储 len 所需的字节大小）和len（当前节点的长度）的压缩版。

Encoding记录了节点内容（value）的类型和长度。value可存的类型有两种，整数和字符串（字节数组）。Redis对字节数组和整数编码提供了一组宏定义，定义在ziplist.c中：

/* Different encoding/length possibilities */
#define ZIP_STR_MASK 0xc0               //1100 0000     字节数组的掩码
#define ZIP_STR_06B (0 << 6)            //0000 0000
#define ZIP_STR_14B (1 << 6)            //0100 0000
#define ZIP_STR_32B (2 << 6)            //1000 0000

#define ZIP_INT_MASK 0x30               //0011 0000     整数的掩码
#define ZIP_INT_16B (0xc0 | 0<<4)       //1100 0000
#define ZIP_INT_32B (0xc0 | 1<<4)       //1101 0000
#define ZIP_INT_64B (0xc0 | 2<<4)       //1110 0000
#define ZIP_INT_24B (0xc0 | 3<<4)       //1111 0000
#define ZIP_INT_8B 0xfe                 //1111 1110

//掩码个功能就是区分一个encoding是字节数组编码还是整数编码
//如果这个宏返回 1 就代表该enc是字节数组，如果是 0 就代表是整数的编码
#define ZIP_IS_STR(enc) (((enc) & ZIP_STR_MASK) < ZIP_STR_MASK)

上面这些常量被如下代码使用：

//从ptr中取出节点信息，并将其保存在encoding、lensize和len中
#define ZIP_DECODE_LENGTH(ptr, encoding, lensize, len) do {                         \
    /*从ptr数组中取出节点的编码格式并将其赋值给encoding*/                                  \
    ZIP_ENTRY_ENCODING((ptr), (encoding));                                          \
    /*如果是字符串编码格式*/                                                            \
    if ((encoding) < ZIP_STR_MASK) {                                                 \
        if ((encoding) == ZIP_STR_06B) {   /*6位字符串编码格式*/                        \
            (lensize) = 1;                 /*编码长度需要1个字节*/                      \
            (len) = (ptr)[0] & 0x3f;       /*当前字节长度保存到len中*/                  \
        } else if ((encoding) == ZIP_STR_14B) {    /*14位字符串编码格式*/               \
            (lensize) = 2;                 /*编码长度需要2个字节*/                      \
            (len) = (((ptr)[0] & 0x3f) << 8) | (ptr)[1]; /*当前字节长度保存到len中*/    \
        } else if (encoding == ZIP_STR_32B) {   /*32串编码格式*/                       \
            (lensize) = 5;                   /*编码长度需要5节*/                        \
            (len) = ((ptr)[1] << 24) |         /*当前字节长度保存到len中*/               \
                    ((ptr)[2] << 16) |                                                \
                    ((ptr)[3] <<  8) |                                                \
                    ((ptr)[4]);                                                       \
        } else {                                                                      \
            assert(NULL);                                                             \
        }                                                                             \
    } else {    /*整数编码格式*/                                                        \
        (lensize) = 1;            /*需要1个字节*/                                      \
        (len) = zipIntSize(encoding);                                                 \
    }                                                                                 \
} while(0);

看不懂没关系，简单归纳就是：

编码格式	value类型	encoding长度	value保存的值长度	解释
00xxxxxx	字节数组	1字节	长度小于等于 2^6−1 字节	encoding长8bit，后6个bit，最多承载数量2^6−1的数字，说明其最多能为长度为2^6−1的字节数组计数
01xxxxxx xxxxxxxx	字节数组	2字节	长度小于等于2^14−1字节	encoding长16bit，后14个bit，最多承载数量2^14−1的数字，说明其最多能为长度为2^14−1的字节数组计数
10—— xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx	字节数组	5字节	长度小于等于2^32−1字节	encoding长40bit，前两位bit10表示该encoding5字节，然后6bit留空，最后32个bit，最多承载数量2^32−1的数字，说明其最多能为长度为2^32−1的字节数组计数
1100 0000	整数	1字节	int16_t类型整数	—–
1101 0000	整数	1字节	int32_t类型整数	—–
1110 0000	整数	1字节	int64_t类型整数	—–
1111 0000	整数	1字节	24 bit 有符号整数	—–
1111 1110	整数	1字节	8 bit 有符号整数	—–
1111 xxxx	整数	1字节	4 bit 无符号整数,[0,12]	encoding为该值的节点是没有value的，因为xxxx已经足够存储0-12的值了，value直接存在encoding中。xxxx首先最小值应该是0001（0000已经被占用），最大值应该是1101（1110与1111均已经被占用），因此，可被编码的值实际上只能是 1 至 13，由于还需要减1，所以实际只能编码[0,12]，至于减1的理由，我的理解是方便编码0。

8.2.3 value

根据encoding来保存字节数组或整数。我们举例说明：

假设这是一个压缩列表的头两个节点，因此：

第一个节点信息：
- prev_entry_len成员值为0，占1字节空间，因为前驱节点长度为0，小于254。
- encoding成员值为0000 0101，最高两位为00，因此encoding占1个字节且可以算出value为字符数组，根据剩下的6位00 0101，可以算出value长度为5字节。
- value成员根据encoding成员算出长度为5字节，因此，会读5个字节的字节数组，值为”Redis”。
第二个节点信息：
- prev_entry_len成员值为0x07，占一个字节，因为前驱节点长度为7，小于254。
  encoding成员编码值为1101 0000，最高两位为11，因此encoding占1个字节且可以算出value为整数，在根据encoding编码可以得出value值为占32位，4个字节int32_t类型的有符号整数。
- value成员根据encoding编码，读出4个字节的整数，值为 1234。
压缩列表的表头信息：
- zlbytes为整个压缩列表所占字节数24。
- zltail_offset为从压缩列表的首地址到最后一个entry节点的偏移量17。
- zlength为节点个数2。
- zlend为常数255(0xFF)。

8.3 连锁更新

因为有如下的前提，所以才会出现连锁更新的场景：

如果前驱节点的长度小于254（2^8-1），那么prev_entry_len成员需要用1字节长度来保存这个长度值。
如果前驱节点的长度大于等于254（2^8-1），那么prev_entry_len成员需要用5字节长度来保存这个长度值。

如果在一个压缩列表中，有多个连续、长度介于250字节到253字节之间的节点，因此记录这些节点只需要1个字节的prev_entry_len，如果要插入一个长度大于等于254的新节点e0到压缩列表的头部，然而原来的头节点e1的prev_entry_len成员长度仅仅为1个字节，无法保存新节点的长度，这会使得e1的prev_entry_len必须扩容到5个节点。e1的长度本来就在[250,254]之间，一扩容又大于了254，使得e2又要扩容，以此类推，引发连锁扩展。

反之，也会引发连锁收缩。

参考资料

为什么redis小等于39字节的字符串是embstr编码，大于39是raw编码？

【Redis源码剖析】 - Redis内置数据结构之字典dict

SkipList 浅析

整数集合

Redis源码剖析和注释（六）— 压缩列表(ziplist)

cherish-ls

纸上得来终觉浅

GitHub

1. TCP协议概述

1.1 TCP和UDP的区别

1.2 TCP协议应用场景

1.3 如何保证可靠性

1.4 TCP连接的实质

1.4.1 为什么要有TCB

1.4.2 什么是Socket

1.4.3 HTTP短连接和长连接

2. TCP的首部

2.1 源端口和目的端口

2.2 序号

2.3 确认号

2.4 数据偏移

2.4 保留

2.6 6个控制位

2.7 窗口

2.8 检验和

2.9 紧急指针

2.10 选项

3. TCP连接的建立与终止

3.1 TCP连接的建立——三次握手

3.2 TCP连接的终止——四次分手

3.2.1 2MSL等待状态

3.2.2 半关闭链接

3.3 总结

4 TCP数据的交互

4.1 捎带确认Delay ACK

4.2 累计确认和Duplicate ACK

4.3 Nagle算法

4.4 超时重传

4.5 选择确认

4.5.1 SACK

4.5.2 Duplicate SACK

5 RTT算法

5.1 经典算法

5.2 Karn / Partridge 算法

5.3 Jacobson / Karels 算法

6 滑动窗口

6.1 背景

6.2 发送窗口和接受窗口

6.3 滑动机制

6.4 滑动过程

6.5 零窗口（Zero Window）

6.6 糊涂窗口综合症（Silly Window Syndrome）

7 拥塞控制

7.1 Reno算法

7.1.1 慢启动（Slow Start）

7.1.2 拥塞避免

7.1.3快速重传

7.1.3.1 快速重传策略

7.1.3.2 拥塞发生时的策略选择

7.1.4 快速恢复（Fast Recovery）

7.2 Vegas算法

参考资料

1. UDP的概述

2. UDP首部格式

3 UDP校验

前言

1. 网络的分层

2. TCP/IP协议的分层

3. 网络基础概念

3.1 IP地址——互联网的地址

3.1.1 子网寻址

3.1.2 子网掩码

3.2 域名

3.3 封装

3.4分用

3.5 端口

3.6 MTU

3.7 IP分片

4. 链路层协议

4.1 IEEE 802封装和以太网封装

4.2 SLIP：串行线路IP封装协议

4.3 PPP：点对点封装协议

5. 网络层协议

5.1 IP协议

5.1.1 IP首部

5.2 ARP协议和RARP协议

5.2.1 协议原理

5.2.1.1 APR原理