Tallate

该吃吃该喝喝 啥事别往心里搁

发表于 更新于 分类于

和朋友交流的一些开放性设计问题的记录，因为是开放性问题，所以肯定是没有唯一答案的，这里只是记录我们讨论时认为比较好的回答。

阅读全文 »

发表于 更新于 分类于

背景

在pinpoint上观察到一些服务器频繁发生长时间FULL GC，直接影响业务执行效率。
一次FullGC的记录
观察gc日志发现，老年代几乎已经耗尽，也没有发生Promotion Failed、Concurrent Mode Failure，最有可能的情况是年轻代正常晋升时发现老年代的空间已经达到了-XX:CMSInitiatingOccupancyFraction，所以触发老年代回收以释放更多空间。
为此，可以采用的解决方式几乎只有2个：

  1. 物理增大老年代，可以直接把年轻代空间割让给老年代，实际上上图中年轻代:老年代≈2:1不大合理，一般根据实际情况，年轻代:老年代的比值是1:1.5到1:3都是可以的，但是不会出现年轻代比老年代大的情况，除非绝大多数对象都是朝生夕死的。
  2. 排查内存泄露，常见于一些错误配置、或者本地缓存（一个大Map）之类的。

排查方式

一、直连VisualVM

1、配置jmx启动参数，表示允许远程连接

1
2
3
4
-Dcom.sun.management.jmxremote
-Dcom.sun.management.jmxremote.port=9988
-Dcom.sun.management.jmxremote.ssl=false
-Dcom.sun.management.jmxremote.authenticate=false

2、使用VisualVM连接
使用VisualVM直连

直连有两个缺点：

  • 实时性差，问题发生可能就那么几分钟，不可能让人一直等着服务器出问题；
  • 安全性差，暴露一个端口就意味着暴露整个项目及其连接的数据库，是一个隐患。

二、配置参数实时导出

1、导出位置
-XX:HeapDumpPath=$CATALINA_BASE/logs/
2、FULL GC前DUMP
-XX:+HeapDumpBeforeFullGC
3、FULL GC后DUMP
-XX:+HeapDumpAfterFullGC
4、OOM
-XX:+HeapDumpOnOutOfMemoryError
配完这个参数后，FULL GC后内存仍不足才会DUMP，单纯System.gc或FULL GC不会引起DUMP。

三、手动dump分析

到服务器上找到JVM进程PID后执行jmap：

1
2
jmap -dump:format=b,file=<文件名> [pid]
gzip <文件名>

下载到本地，因为线上服务器没有开启下载端口，因此下载文件必须要中转一下，先上传到一台暴露到公网的服务器，再从该服务器上下载，如果没有这样的服务器也可以用github代替。
在本地使用eclipse MAT分析。

问题排查记录

手动导出内存dump文件：
robin的内存dump文件
仔细观察其中对象占用的内存空间，发现一个大对象占用了接近1/3的内存空间，发现是com.alibaba.druid.stat.JdbcDataSourceStat中有个LinkedHashMap类型的成员变量占用了大量空间没有释放，在源码中对应一个sqlStatMap。
占用大量内存空间的大对象
Druid中的sqlStatMap
从源码可知，打开开关之后，每次执行SQL前后都会把SQL记到这个sqlStatMap里，在JVM实例运行期间会一直存在（基本都在老年代），这个开关主要用于监控SQL执行情况，对SQL语句的执行本身没有影响，且我们这边统计SQL（包括慢查询等）都是基于MySQL本身的功能、并没有用到这个配置。
可以把这个开关关掉，因为我们根本没有使用Druid内置的SQL监控功能，关闭后预计可以释放25%左右的堆空间。
另外附：
1、配置_StatFilter：https://github.com/alibaba/druid/wiki/%E9%85%8D%E7%BD%AE_StatFilter
2、每个sql语句都会长期持有引用，加快FullGC频率 #1664：https://github.com/alibaba/druid/issues/1664

发表于 更新于 分类于

物理层

核心问题 - 如何实现物理连接

可以直接使用网线连接两台电脑，或者使用Hub连接多台电脑，Hub会将收到的每一个字节都复制到其他端口上去。

常见协议

略

数据链路层

数据链路层

核心问题 - 这个包是发给谁的？谁应该接收？

这里用到一个物理地址，叫作链路层地址。但是因为第二层主要解决媒体接入控制的问题，所以它常被称为MAC 地址。
数据包封装时会封装上目标MAC地址，数据包在链路上广播时，MAC的网卡就可以发现这个包是发给它的。
回传时，源MAC地址就会变成目标MAC地址，再返回给请求的机器。

核心问题 - 大家都在发，会不会产生混乱？有没有谁先发、谁后发的规则？

MAC（Medium Access Control），即媒体访问控制，主要功能其实就是控制在往媒体上发数据的时候，谁先发、谁后发的问题，防止发生混乱。这个问题中的规则，学名叫多路访问。
多路访问规则有好几种：

  • 方式一：分多个车道。每个车一个车道，你走你的，我走我的。这在计算机网络里叫作信道划分；
  • 方式二：今天单号出行，明天双号出行，轮着来。这在计算机网络里叫作轮流协议；
  • 方式三：不管三七二十一，有事儿先出门，发现特堵，就回去。错过高峰再出。我们叫作随机接入协议。著名的以太网，用的就是这个方式。

核心问题 - 如果发送的时候出现了错误，怎么办？

接收包时会进行CRC（循环冗余检测）校验，通过 XOR 异或的算法，来计算整个包是否在发送的过程中出现了错误。

常见协议 - MAC协议

数据链路层设备 - Hub

Hub太傻，每个包都广播，数据链路层使用交换机来转发数据包。

  1. 学习能力
    一开始不知道目标MAC地址在哪个端口，交换机会全发，但是之后再碰到发往该MAC地址的数据就可以直接发给对应的端口了。
    当然，每个机器的 IP 地址会变，所在的口也会变，因而交换机上的学习的结果，我们称为转发表，是有一个过期时间的。
  2. 环路问题
    交换机环路问题
    我们来想象一下机器 1 访问机器 2 的过程。一开始，机器 1 并不知道机器 2 的 MAC 地址，所以它需要发起一个 ARP 的广播。广播到达机器 2，机器 2 会把 MAC 地址返回来。主要问题是这里的广播包也会到达交换机，交换机A刚开始不知道机器2在哪个局域网（实际上在局域网1），因此它会将广播消息放到局域网二，交换机B此时又会将广播包发回局域网一，形成环路。
    解决环路的方法是STP协议（Spanning Tree Protocol / 最小生成树）。

网络层

网络层

常见协议 - ARP协议

已知IP地址，求MAC地址使用的是ARP协议。
为了知道目标主机的MAC地址，需要发送一个广播包，谁是这个 IP 谁来回答。
为了避免每次都用 ARP 请求，机器本地也会进行 ARP 缓存。当然机器会不断地上线下线，IP 也可能会变，所以 ARP 的 MAC 地址缓存过一段时间就会过期。

常用协议 - IP

IP、MAC数据包-图片来自(https://time.geekbang.org/column/article/8590)
发IP数据包时，网络程序会先判断目标IP地址和当前IP地址是否在同一个网段：

判断是否同一网段需要使用CIDR和子网掩码。

  1. 如果是同一网段，那就没网关什么事情，直接将源地址和目标地址放入 IP 头中，然后通过 ARP 获得 MAC 地址，将源 MAC 和目的 MAC 放入 MAC 头中，发出去就可以了；
  2. 如果不是同一网段，这时需要发往默认网关Gateway，Gateway的地址一定是和源IP地址是一个网段的。比如我们在宿舍里上网，路由器就是一个小网关。

如何发往默认网关呢？
网关不是和源 IP 地址是一个网段的么？这个过程就和发往同一个网段的其他机器是一样的：将源地址和目标 IP 地址放入 IP 头中，通过 ARP 获得网关的 MAC 地址，将源 MAC 和网关的 MAC 放入 MAC 头中，发送出去。网关所在的端口，例如 192.168.1.1/24 将网络包收进来，然后接下来怎么做，就完全看网关的了。

5类地址

IP的5类地址
A、B、C三类地址范围及私有地址

网络层设备 - 路由器

很多情况下，人们把网关就叫做路由器。其实不完全准确，而另一种比喻更加恰当：路由器是一台设备，它有五个网口或者网卡，相当于有五只手，分别连着五个局域网。每只手的 IP 地址都和局域网的 IP 地址相同的网段，每只手都是它握住的那个局域网的网关。

路由方式

路由分为静态路由和动态路由两种：

  • 静态路由：其实就是在路由器上的路由表中，配置一条一条规则，这些规则包括：想去哪（目标IP）、先去哪（下一跳的IP）、从哪去（路由器端口）。

    除了根据目标IP配置路由外，还可以配置多参数的策略路由。

  • 动态路由：使用动态路由路由器，可以根据路由协议算法生成动态路由表，随网络运行状况的变化而变化。
    具备动态路由功能的路由器能够实时计算两个节点之间的最短路径，可用的算法包括：
    • 基于Bellman-Ford算法的距离矢量路由（distance vector routing），实现为BGP（Border Gateway Protocol，外网路由协议），应用于大规模的网络中，因为大规模网络中自治系统比较少，所以不会有收敛慢、坏消息传得慢等问题。实际上BGP中使用的是路径矢量路由协议，是距离矢量路由的升级版
    • 基于Dijkstra算法的链路状态路由（link state routing），实现为OSPF（Open Shortest Path First，开放式最短路径优先），常用于组织内网中。

为了方便起见，下面讨论IP数据包的传播流程时，都是采用的静态路由。

网关类型

网关分为转发网关和NAT网关：

  • 转发网关：不改变 IP 地址。
    转发时，将下一跳的IP转换为MAC地址放入目标MAC地址字段，然后将当前主机的MAC地址放入源MAC地址字段，在这期间源IP和目标IP都是不变的，这个过程又称为跳。
  • NAT网关：改变IP地址。
    在局域网内部因为都在同一个网段内，大家都能互相通过ARP识别对方的IP地址（转换为MAC地址）。
    但是在公网上就不一样了，因为公网IP很少，所以大家都会用DHCP复用一个IP地址（即局域网），那么我们怎么从一台主机访问另一台主机呢？

IP数据包究竟是怎么从源主机发送到目标主机的？

如果是单纯的局域网通信会简单很多，网络拓扑中只需要转发网关就够了，一个IP数据包的转发流程如下：
IP数据包转发例子

  1. 网卡获取IP时已经拿到了网关的IP，因此可以方便地通过ARP解析出网关的MAC，所以初始数据包里的字段我们就可以确定了：
    源MAC：服务器A的MAC；
    目标MAC：192.168.1.1 这个网口的 MAC
    源 IP：192.168.1.101
    目标 IP：192.168.4.101
  2. 数据包发送到网关192.168.1.1后，发现MAC一致于是接收该数据包；
  3. 路由器A（也就是网关192.168.1.1所在的那个路由器）中配置了静态路由：要想访问子网192.168.4.0/24，就要从192.168.56.1这个网口出去，下一跳为192.168.56.2。于是这一次数据包是这样的：
    源 MAC：192.168.56.1 的 MAC 地址
    目标 MAC：192.168.56.2 的 MAC 地址
    源 IP：192.168.1.101
    目标 IP：192.168.4.101
  4. 同理，包到达192.168.56.2这个网口后，发现MAC一致于是接收数据包；
  5. 在路由器B中配置了静态路由：要访问子网192.168.4.0/24，直接从192.168.4.1这个口出去即可，因为这个网卡就是这个网段的，这就是最后一跳了。包内容是：
    源 MAC：192.168.4.1 的 MAC 地址
    目标 MAC：192.168.4.101 的 MAC 地址
    源 IP：192.168.1.101
    目标 IP：192.168.4.101
  6. 最后，MAC地址匹配，包到达服务器B。

在这个过程中，每经过一个局域网，MAC地址都会变化，但是IP地址不会变，数据包传播时只是将下一跳的IP地址转换为MAC地址放入MAC头。

现代的网络通信基本都不会是只有局域网的，数据包需要经过公网传递到世界的另一个角落，但是根据IPv4的特点，如果给世界上每个需要上网的人都分配一个IP地址，IP地址空间是绝对不够的，因此就需要引入NAT了。
引入NAT路由后，两个局域网内可以有相同的IP，只不过局域网内需要暴露到公网的服务器还需要有一个外网IP，比如，目标服务器 B 在公网上要有一个公网IP 192.168.56.2。在网关 B 上，我们记下来，公网IP 192.168.56.2 对应局域网IP 192.168.1.101。凡是要访问 192.168.56.2，都转成 192.168.1.101。
IP数据包转发例子

  1. 源服务器A要访问目标服务器B，要指定目标地址为192.168.56.2，因为192.168.56.2和服务器A不在一个网段内，因此要发送到网关，网关是之前已经静态配置好的192.168.1.1。这里同样通过ARP可以得到下一跳的MAC地址，因此数据包就是：
    源 MAC：服务器 A 的 MAC
    目标 MAC：192.168.1.1 这个网口的 MAC
    源 IP：192.168.1.101
    目标 IP：192.168.56.2
  2. 包到达192.168.1.1这个网口，路由器发现MAC一致就接收了这个包；
  3. 在路由器A中因为配置了静态路由：要想访问192.168.56.2/24这个网段，直接从192.168.56.1这个网口出去即可，当前路由器其实就是最后一跳了。这里，同样可以通过ARP获取到目标服务器的MAC地址：
    源 MAC：192.168.56.1 的 MAC 地址
    目标 MAC：192.168.56.2 的 MAC 地址
    源 IP：192.168.56.1
    目标 IP：192.168.56.2
  4. 数据包到达192.168.56.2这个网口，发现MAC地址一致，于是接收数据包。
    注意此时192.168.56.2所在的路由器B是一个NAT网关，它上面配置了公网IP 192.168.56.2对应着局域网IP的192.168.1.101，于是改为访问192.168.1.101。
  5. 在路由器 B 中配置了静态路由：要想访问 192.168.1.0/24，要从 192.168.1.1 这个口出去，那么接下来就是从192.168.1.1这个口发出去发给192.168.1.101了。同理可以通过ARP解析出MAC地址，得到数据包：
    源 MAC：192.168.1.1 的 MAC 地址
    目标 MAC：192.168.1.101 的 MAC 地址
    源 IP：192.168.56.1
    目标 IP：192.168.1.101
  6. 包到达服务器B，MAC地址匹配，所以最终接收该数据包。

当服务器B要发送响应数据包时，使用上面数据包中的源IP作为目标IP，而路由器A做NAT，将目标IP转换为局域网IP。
但是，上面的源IP是网关的公网IP，并不是我们的源服务器A的IP，那么路由器又怎么知道应该发给A而不是其局域网内的其他服务器呢？其实NAT协议只支持1对1转换，即一个内网IP和一个外网IP，如果需要支持一个外网IP对应多个内网IP，则需要NAPT协议的支持，协议会维护一张映射表：内网ip:port–>外网ip:空闲port。

常见协议 - ICMP（Internet Control Message Protocol / 互联网控制报文协议）

发一个带标识的数据包，发送方统计应答情况。

常用命令 - traceroute

  1. 故意设置特殊的 TTL，来追踪去往目的地时沿途经过的路由器。
    Traceroute 的参数指向某个目的 IP 地址，它会发送一个 UDP 的数据包。将 TTL 设置成 1，也就是说一旦遇到一个路由器或者一个网关，它就会过期了，于是，返回一个 ICMP 包，也就是网络差错包，类型是时间超时。
    之后，将TLL设置为2，只能探2个路由器或网关，以此类推，直到到达目标主机。这样，Traceroute 就拿到了所有的路由器 IP。
    怎么知道 UDP 有没有到达目的主机呢？Traceroute 程序会发送一份 UDP 数据报给目的主机，但它会选择一个不可能的值作为 UDP 端口号（大于 30000）。当该数据报到达时，将使目的主机的 UDP 模块产生一份“端口不可达”错误 ICMP 报文。如果数据报没有到达，则可能是超时。
  2. 故意设置不分片，从而确定路径的 MTU。
1
traceroute

常用命令 - ip

添加策略路由：

1
2
3
ip rule add from 192.168.1.0/24 table 10
ip rule add from 192.168.2.0/24 table 20
ip route add default scope global nexthop via 100.100.100.1 weight 1 nexthop via 200.200.200.1 weight 2

常用命令 - 配置IP地址

使用 net-tools：

1
2
$ sudo ifconfig eth1 10.0.0.1/24
$ sudo ifconfig eth1 up

使用 iproute2：

1
2
$ sudo ip addr add 10.0.0.1/24 dev eth1
$ sudo ip link set up eth1

常用命令 - netstat

netstat 命令一般用于统计服务器上各端口的网络连接情况，可以用于分析 IP、TCP、UDP 和 ICMP 协议相关的统计数据。

1
2
3
4
5
6
7
8
9
huanggaochi@app08:~$ netstat
Active Internet connections (w/o servers)
Proto Recv-Q Send-Q Local Address           Foreign Address         State
tcp       32      0 app08.hp.sp.tst.b:11920 123.151.71.149:https    CLOSE_WAIT
...
Active UNIX domain sockets (w/o servers)
Proto RefCnt Flags       Type       State         I-Node   Path
unix  2      [ ]         DGRAM                    1453     /run/systemd/notify
...

netstat 的输出结果主要分为两个部分：

  1. Active Internet connections，表示有源 TCP 连接，其中，
    • Recv-Q和Send-Q表示接收队列和发送队列，正常情况下，这两个值应该都是 0，否则说明数据包正在队列中堆积。
    • Proto，连接使用的协议；
    • State，套接字当前状态；
  2. Active UNIX domain sockets，表示有源 Unix 域套接字（和网络套接字一样，但是只能用于本机通信，性能可以提高很多）。
    • RefCnt，连接到本套接字上的进程号；
    • Type，套接字的类型；
    • Path，连接到套接字的其他进程使用的路径名。

可以使用选项指定目标套接字类型：

  • -t：TCP
  • -u：UDP
  • -raw：RAW 类型
  • –unix：UNIX 域类型
  • –ax25：AX25 类型
  • –ipx：ipx 类型
  • –netrom：netrom 类型

连接状态：

  • LISTEN：侦听来自远方的 TCP 端口的连接请求
  • SYN-SENT：再发送连接请求后等待匹配的连接请求（如果有大量这样的状态包，检查是否中招了）
  • SYN-RECEIVED：再收到和发送一个连接请求后等待对方对连接请求的确认（如有大量此状态，估计被 flood 攻击了）
  • ESTABLISHED：代表一个打开的连接
  • FIN-WAIT-1：等待远程 TCP 连接中断请求，或先前的连接中断请求的确认
  • FIN-WAIT-2：从远程 TCP 等待连接中断请求
  • CLOSE-WAIT：等待从本地用户发来的连接中断请求
  • CLOSING：等待远程 TCP 对连接中断的确认
  • LAST-ACK：等待原来的发向远程 TCP 的连接中断请求的确认（不是什么好东西，此项出现，检查是否被攻击）
  • TIME-WAIT：等待足够的时间以确保远程 TCP 接收到连接中断请求的确认
  • CLOSED：没有任何连接状态
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 显示网卡列表
netstat -i
# 显示组播组的关系
netstat -g
# 显示网络统计
netstat -s
# 显示监听中的udp和tcp连接，显示数字而不是尝试用符号表示（比如localhost会显示为127.0.0.1），显示进程号
netstat -lutnp
# 显示关于以太网的统计数据，输出结果增加User、Inode两个字段，列出的项目包括传送的数据报的总字节数、错误数、删除数、数据报的数量和广播的数量。这些统计数据既有发送的数据报数量，也有接收的数据报数量。这个选项可以用来统计一些基本的网络流量）
netstat -e
# 显示路由信息，也可以用route -n命令
netstat -r
# 统计机器各个状态网络连接个数
netstat -an | awk '/^tcp/ {++S[$NF]}  END {for (a in S) print a,S[a]}'
# 统计每种连接的数量
netstat -ant | awk '{print $6}' | sort | uniq -c
# 查看连接某服务端口最多的IP地址，下面假设服务器对外暴露的IP为192.168.1
netstat -ant | grep "192.168.1.*" | awk '{print $5}' | awk -F: '{print $1}' | sort -nr | uniq -c
# 显示TCP连接信息，并找出程序运行的端口，在结果中增加一列“PID/Program name”
netstat -anp | grep ssh

传输层

传输层

常见协议 - UDP

  • 面向无连接
    交互前不需要建立连接，可以直接发生数据包。
  • 提供不可靠交付
    UDP 继承了 IP 包的特性，不保证不丢失，不保证按顺序到达。
  • 基于数据报
    UDP 继承了 IP 的特性，基于数据报的，一个一个地发，一个一个地收。
  • 无拥塞控制

UDP的数据包格式：
UDP数据包格式

UDP的使用场景：

  1. 需要资源少，在网络情况比较好的内网，或者对于丢包不敏感的应用
  2. 不需要一对一沟通，建立连接，而是可以广播的应用
    UDP 的不面向连接的功能，可以使得可以承载广播或者多播的协议。DHCP 就是一种广播的形式，就是基于 UDP 协议的。
  3. 需要处理速度快，时延低，可以容忍少数丢包，即使网络拥塞也不改变发送的速率

常见协议 - TCP

  • TCP是面向连接的
    所谓的建立连接，是为了在客户端和服务端维护连接，而建立一定的数据结构来维护双方交互的状态，用这样的数据结构来保证所谓的面向连接的特性。
  • TCP 提供可靠交付
    通过 TCP 连接传输的数据，无差错、不丢失、不重复、并且按序到达。
  • TCP 是面向字节流
    发送的时候发的是一个流，没头没尾。
  • 拥塞控制
    TCP意识到包丢弃了或者网络的环境不好了，就会根据情况调整自己的行为，看看是不是发快了，要不要发慢点。

TCP 优点

  • 可靠，稳定
    TCP 的可靠体现在 TCP 在传递数据之前，会有三次握手来建立连接，而且在数据传递时，有确认、窗口、重传、拥塞控制机制，在数据传完后，还会断开连接用来节约系统资源。

TCP 缺点

慢，效率低，占用系统资源高，易被攻击
TCP 在传递数据之前，要先建连接，这会消耗时间，而且在数据传递时，确认机制、重传机制、拥塞控制机制等都会消耗大量的时间，而且要在每台设备上维护所有的传输连接，事实上，每个连接都会占用系统的 CPU、内存等硬件资源。 而且，因为 TCP 有确认机制、三次握手机制，这些也导致 TCP 容易被人利用，实现 DOS、DDOS、CC 等攻击。

TCP的数据包格式

TCP数据包格式

  1. 源端口号和目标端口号，用于确定数据应该发给哪个应用；
  2. 包序号
    用于解决乱序问题；
  3. 确认序号
    解决丢包问题，如果没有收到就重新发送，直到送达。
  4. 状态位
    例如SYN是发起一个连接；
    ACK是回复；
    RST是重新连接；
    FIN是结束连接。
  5. 窗口大小
    TCP要做到流量控制，通信双方各声明一个窗口，标识自己当前的处理能力。

连接的建立 - 三次握手

TCP三次握手
一开始，客户端和服务端都处于 CLOSED 状态。先是服务端主动监听某个端口，处于 LISTEN 状态。然后客户端主动发起连接 SYN，之后处于 SYN-SENT 状态。服务端收到发起的连接，返回 SYN，并且 ACK 客户端的 SYN，之后处于 SYN-RCVD 状态。客户端收到服务端发送的 SYN 和 ACK 之后，发送 ACK 的 ACK，之后处于 ESTABLISHED 状态，因为它一发一收成功了。服务端收到 ACK 的 ACK 之后，处于 ESTABLISHED 状态，因为它也一发一收了。
从连接建立的流程中可见，三次握手除了双方建立连接外，还能确定TCP包的序号问题。

总而言之：

  1. 首先 Client 端发送连接请求报文，Server 段接受连接后回复 ACK 报文，并为这次连接分配资源。
  2. Client 端接收到 ACK 报文后也向 Server 段发生 ACK 报文，并分配资源，这样 TCP 连接就建立了。
    TCP三次握手
    最初两端的 TCP 进程都处于 CLOSED 关闭状态，A（Client）主动打开连接，而 B（Server）被动打开连接。（A、B 关闭状态 CLOSED——B 创建 TCB，进入 LISTEN 状态，等待 A 请求——A 同步已发送状态 SYN-SENT——B 同步收到状态 SYN-RCVD——A、B 连接已建立状态 ESTABLISHED）
  3. 第一次握手：起初两端都处于 CLOSED 关闭状态，A（Client）将标志位 SYN 置为 1，随机产生一个值 seq=x，并将该数据包发送给 B（Server），A（Client）进入 SYN-SENT 状态，等待 B（Server）确认；
  4. 第二次握手：B（Server）收到连接请求报文段后，如同意建立连接，则向 A（Client）发送确认，在确认报文段中（SYN=1，ACK=1，确认号 ack=x+1，初始序号 seq=y），B（Server）TCP 服务器进程进入 SYN-RCVD（同步收到）状态；
  5. 第三次握手：TCP 客户进程收到 B（Server）的确认后，要向 B（Server）给出确认报文段（ACK=1，确认号 ack=y+1，序号 seq=x+1）（初始为 seq=x，第二个报文段所以要+1），ACK 报文段可以携带数据，不携带数据则不消耗序号。TCP 连接已经建立，A 进入 ESTABLISHED（已建立连接）。
    当 B 收到 A 的确认后，也进入 ESTABLISHED 状态。

    TCB 传输控制块 Transmission Control Block，存储每一个连接中的重要信息，如 TCP 连接表，到发送和接收缓存的指针，到重传队列的指针，当前的发送和接收序号。

一些问题：

  1. 为什么 A 还要发送一次确认呢？可以二次握手吗？
    主要为了防止已失效的连接请求报文段突然又传送到了 B，因而产生错误。如 A 发出连接请求，但因连接请求报文丢失而未收到确认，于是 A 再重传一次连接请求。后来收到了确认，建立了连接。数据传输完毕后，就释放了连接，A 发出了两个连接请求报文段，其中第一个丢失，第二个到达了 B，但是第一个丢失的报文段只是在某些网络结点长时间滞留了，延误到连接释放以后的某个时间才到达 B，此时 B 误认为 A 又发出一次新的连接请求，于是就向 A 发出确认报文段，同意建立连接，不采用三次握手，只要 B 发出确认，就建立新的连接了，此时 A 不理睬 B 的确认且不发送数据，则 B 一致等待 A 发送数据，浪费资源。
  2. Server 端易受到 SYN 攻击？
    服务器端的资源分配是在二次握手时分配的，而客户端的资源是在完成三次握手时分配的，所以服务器容易受到 SYN 洪泛攻击，SYN 攻击就是 Client 在短时间内伪造大量不存在的 IP 地址，并向 Server 不断地发送 SYN 包，Server 则回复确认包，并等待 Client 确认，由于源地址不存在，因此 Server 需要不断重发直至超时，这些伪造的 SYN 包将长时间占用未连接队列，导致正常的 SYN 请求因为队列满而被丢弃，从而引起网络拥塞甚至系统瘫痪。
    防范 SYN 攻击措施：降低主机的等待时间使主机尽快的释放半连接的占用，短时间受到某 IP 的重复 SYN 则丢弃后续请求。

连接的断开 - 四次挥手

TCP四次挥手
假设 Client 端发起中断连接请求，也就是发送 FIN 报文。Server 端接到 FIN 报文后，意思是说”我 Client 端没有数据要发给你了”，但是如果你还有数据没有发送完成，则不必急着关闭 Socket，可以继续发送数据。所以你先发送 ACK，”告诉 Client 端，你的请求我收到了，但是我还没准备好，请继续你等我的消息”。这个时候 Client 端就进入 FIN_WAIT 状态，继续等待 Server 端的 FIN 报文。当 Server 端确定数据已发送完成，则向 Client 端发送 FIN 报文，”告诉 Client 端，好了，我这边数据发完了，准备好关闭连接了”。Client 端收到 FIN 报文后，”就知道可以关闭连接了，但是他还是不相信网络，怕 Server 端不知道要关闭，所以发送 ACK 后进入 TIME_WAIT 状态，如果 Server 端没有收到 ACK 则可以重传。“，Server 端收到 ACK 后，”就知道可以断开连接了”。Client 端等待了 2MSL 后依然没有收到回复，则证明 Server 端已正常关闭，那好，我 Client 端也可以关闭连接了。Ok，TCP 连接就这样关闭了！

数据传输结束后，通信的双方都可释放连接，A 和 B 都处于 ESTABLISHED 状态。（A、B 连接建立状态 ESTABLISHED——A 进入等待 1 状态 FIN-WAIT-1——B 关闭等待状态 CLOSE-WAIT——A 进入等待 2 状态 FIN-WAIT-2——B 最后确认状态 LAST-ACK——A 时间等待状态 TIME-WAIT——B、A 关闭状态 CLOSED）

  1. A 的应用进程先向其 TCP 发出连接释放报文段（FIN=1，序号 seq=u），并停止再发送数据，主动关闭 TCP 连接，进入 FIN-WAIT-1（终止等待 1）状态，等待 B 的确认。
  2. B 收到连接释放报文段后即发出确认报文段，（ACK=1，确认号 ack=u+1，序号 seq=v），B 进入 CLOSE-WAIT（关闭等待）状态，此时的 TCP 处于半关闭状态，A 到 B 的连接释放。
  3. A 收到 B 的确认后，进入 FIN-WAIT-2（终止等待 2）状态，等待 B 发出的连接释放报文段。
  4. B 没有要向 A 发出的数据，B 发出连接释放报文段（FIN=1，ACK=1，序号 seq=w，确认号 ack=u+1），B 进入 LAST-ACK（最后确认）状态，等待 A 的确认。
  5. A 收到 B 的连接释放报文段后，对此发出确认报文段（ACK=1，seq=u+1，ack=w+1），A 进入 TIME-WAIT（时间等待）状态。此时 TCP 未释放掉，需要经过时间等待计时器设置的时间 2MSL 后，A 才进入 CLOSED 状态。

总而言之：

  1. 刚开始A发送断开连接请求，进入FIN_WAIT_1状态；
  2. B接收请求进入CLOSED_WAIT状态，并发回响应；
  3. A接收B响应，进入FIN_WAIT_2状态；
  4. B发送断开连接请求，并进入LAST_ACK状态；
  5. A接收请求，进入TIME_WAIT状态，并发回响应；
    A会在发出响应2MSL后自动进入CLOSED状态。
    MSL 是 Maximum Segment Lifetime，报文最大生存时间，它是任何报文在网络上存在的最长时间，超过这个时间报文将被丢弃。因为 TCP 报文基于是 IP 协议的，而 IP 头中有一个 TTL 域，是 IP 数据报可以经过的最大路由数，每经过一个处理他的路由器此值就减 1，当此值为 0 则数据报将被丢弃，同时发送 ICMP 报文通知源主机。协议规定 MSL 为 2 分钟，实际应用中常用的是 30 秒，1 分钟和 2 分钟等。
  6. B接收响应后进入CLOSED状态。

该流程中让人比较困惑的问题是：

  1. 为什么A断开连接后，第4步还要B在反向发起一次断开连接？
    不能直接断开，因为A单方面断开连接时，A不知道B是不是还有事情要处理。
  2. 如果第4步B没有重新发起断开连接（只有2次挥手），连接怎么断开？
    如果这期间B宕机了没有重新发起断开连接，A将永远停留在FIN_WAIT_2的状态，TCP 协议里面并没有对这个状态的处理，但是 Linux 有，可以调整 tcp_fin_timeout 这个参数，设置一个超时时间。
  3. 第5步如果A响应没有返回给B，B怎么断开？
    此时B会重新发起一次断开请求，因而TCP要求A最后等待一段时间TIME_WAIT，这个时间要足够长，长到如果B没有收到ACK，B可以重试且时间足够到达。
    不过，还有一个异常情况就是，B 超过了 2MSL 的时间，依然没有收到它发的 FIN 的 ACK，怎么办呢？按照 TCP 的原理，B 当然还会重发 FIN，这时A再收到这个包后，会直接返回RST，B就知道早已断开连接了。
  4. TIME_WAIT
    TIME_WAIT 状态容易被人误解，比如当使用三方系统的服务时，看到系统 TIME_WAIT 数量特别高，于是赖对方没有及时把连接释放掉，实际上TIME_WAIT 产生在主动断开连接的一方。
  5. 为什么 A 在 TIME-WAIT 状态必须等待 2MSL 的时间？（MSL 最长报文段寿命 Maximum Segment Lifetime，MSL=2）
    原因有 2：
    保证 A 发送的最后一个 ACK 报文段能够到达 B。这个 ACK 报文段有可能丢失，使得处于 LAST-ACK 状态的 B 收不到对已发送的 FIN+ACK 报文段的确认，B 超时重传 FIN+ACK 报文段，而 A 能在 2MSL 时间内收到这个重传的 FIN+ACK 报文段，接着 A 重传一次确认，重新启动 2MSL 计时器，最后 A 和 B 都进入到 CLOSED 状态，若 A 在 TIME-WAIT 状态不等待一段时间，而是发送完 ACK 报文段后立即释放连接，则无法收到 B 重传的 FIN+ACK 报文段，所以不会再发送一次确认报文段，则 B 无法正常进入到 CLOSED 状态。
    防止“已失效的连接请求报文段”出现在本连接中。A 在发送完最后一个 ACK 报文段后，再经过 2MSL，就可以使本连接持续的时间内所产生的所有报文段都从网络中消失，使下一个新的连接中不会出现这种旧的连接请求报文段。
  6. 为什么连接的时候是三次握手，关闭的时候却是四次握手？
    因为当 Server 端收到 Client 端的 SYN 连接请求报文后，可以直接发送 SYN+ACK 报文。其中 ACK 报文是用来应答的，SYN 报文是用来同步的。但是关闭连接时，当 Server 端收到 FIN 报文时，很可能并不会立即关闭 SOCKET，所以只能先回复一个 ACK 报文，告诉 Client 端，”你发的 FIN 报文我收到了”。只有等到我 Server 端所有的报文都发送完了，我才能发送 FIN 报文，因此不能一起发送。故需要四步握手。
  7. 为什么 TIME_WAIT 状态需要经过 2MSL(最大报文段生存时间)才能返回到 CLOSE 状态？
    虽然按道理，四个报文都发送完毕，我们可以直接进入 CLOSE 状态了，但是我们必须假象网络是不可靠的，有可能最后一个 ACK 丢失。所以 TIME_WAIT 状态就是用来重发可能丢失的 ACK 报文。
  8. 如何优化
    我们可以通过修改系统参数来优化服务器
    tcp_tw_reuse: 是否重用处于 TIME_WAIT 状态的 TCP 链接 （设为 true）
    tcp_max_tw_buckets: 处于 TIME_WAIT 状态的 SOCKET 最大数目 （调大，这个参数千万不要调小了）
    tcp_fin_timeout: 处于 FIN_WAIT_2 的时间 （调小）

TCP状态机

上面的握手和挥手流程汇总为状态机如下图所示：
TCP状态机

累计确认（cumulative acknowledgment，或称为累计应答）

TCP中并不是发1收1，而是使用一个缓冲区保存数据包，这个缓冲区称为窗口，发送端的发送窗口如下图所示：
TCP发送窗口

  1. 发送了并且已经确认的。
  2. 发送了并且尚未确认的。
  3. 没有发送，但是已经等待发送的。
  4. 没有发送，并且暂时还不会发送的。
  • LastByteAcked：第一部分和第二部分的分界线
  • LastByteSent：第二部分和第三部分的分界线
  • LastByteAcked + AdvertisedWindow：第三部分和第四部分的分界线

为什么会有第3和第4部分？难道这些不都是等待发送的吗？其实区分第3和第4部分的主要目的是流量控制，在 TCP 里，接收端会给发送端报一个窗口的大小，叫 Advertised window。这个窗口的大小应该等于上面的第2部分加上第3部分，超过了这个窗口的接收端处理不过来，就不发送了，作为第4部分。

接收端同样也有一个接收窗口：
TCP接收窗口

  1. 接受并且确认过的。
  2. 还没接收，但是马上就能接收的。
  3. 还没接收，也没法接收的。
  • MaxRcvBuffer：最大缓存的量；
  • LastByteRead 之后是已经接收了，但是还没被应用层读取的；
  • NextByteExpected 是第一部分和第二部分的分界线。

顺序问题与丢包问题

TCP中的重发有两种：

  1. 超时重试
    对每一个发送了，但是没有 ACK 的包，都有设一个定时器，超过了一定的时间，就重新尝试。
    这个时间不宜过短，时间必须大于往返时间 RTT，否则会引起不必要的重传。也不宜过长，这样超时时间变长，访问就变慢了。估计往返时间，需要 TCP 通过采样 RTT 的时间，然后进行加权平均，算出一个值，而且这个值还是要不断变化的，因为网络状况不断地变化。除了采样 RTT，还要采样 RTT 的波动范围，计算出一个估计的超时时间。由于重传时间是不断变化的，我们称为自适应重传算法（Adaptive Retransmission Algorithm）。
    超时间隔加倍：每当遇到一次超时重传的时候，都会将下一次超时时间间隔设为先前值的两倍。两次超时，就说明网络环境差，不宜频繁反复发送。
  2. 快速重传
    超时重传存在的问题是超时周期可能会比较长，为了加快重传，TCP采用一种快速重传机制：
    当接收方收到一个序号大于下一个所期望的报文段时，就会检测到数据流中的一个间隔，于是它就会发送冗余的 ACK，仍然 ACK 的是期望接收的报文段。而当客户端收到三个冗余的 ACK 后，就会在定时器过期之前，重传丢失的报文段。
    例如，接收方发现 6 收到了，8 也收到了，但是 7 还没来，那肯定是丢了，于是发送 6 的 ACK，要求下一个是 7。接下来，收到后续的包，仍然发送 6 的 ACK，要求下一个是 7。当客户端收到 3 个重复 ACK，就会发现 7 的确丢了，不等超时，马上重发。
  3. Selective Acknowledgment （SACK）
    接收方可以将缓存的地图发送给发送方，例如发送ACK6、SACK8，SACK8表示已接收但未处理的，有了地图，发送方一下子就能看出来是 7 丢了。

流量控制

当发送未确认窗口中最早的一个包接收到了确认，则窗口将前移一格：
TCP接收窗口
上图中，5接收到了确认，此时窗口前移一格，第14个包可以发送了。
TCP接收窗口移动
如果接收方处理太慢，导致缓存中没有空间了，可以通过确认信息修改窗口的大小，甚至可以设置为 0，则发送方将暂时停止发送。
假设一个极端情况，接收端的应用一直不读取缓存中的数据，当数据包 6 确认后，窗口大小就不能再是 9 了，就要缩小一个变为 8。
那么缩小后什么时候恢复呢？发送方会定时发送窗口探测数据包，看是否有机会调整窗口的大小。

拥塞控制

拥塞控制也是通过控制窗口大小来实现的，前面的滑动窗口 rwnd 是怕发送方把接收方缓存塞满，而拥塞窗口 cwnd，是怕把网络塞满。

TCP的拥塞控制主要是为了避免丢包和超时重传问题：

  • 如果窗口不经控制——像UDP那样——很有可能发送的数据量超过中间设备的承载能力，多出来的包就会被丢弃，即发生了丢包，这是我们不希望看到的。

  • 如果在这些设备上加缓存，处理不过来的先保存在缓存队列里，这样虽然不会丢失，但是会增加时延，如果时延达到一定程度，就会导致超时重传。

  • 慢启动（指数增长）
    刚开始不清楚网络情况，因此发送数据包时一次只能发1个，后来按2、4、8的指数性增长速度来增长；

  • 线性增长
    当超过一个阈值ssthresh=65535时，可能速度达到了网络性能，这时会慢下来，变成线程增长，每收到一个确认后，cwnd才会增加1/cwnd。

  • 指数递减
    当发生了丢包，需要超时重传时，会设置ssthresh=cwnd/2，并将cwnd设置为1，重新开始慢启动，这种减速方式的问题是太过激进，从原来的高速马上减到1，会造成明显的网络卡顿，因为这个问题，一般会采用快速重传算法。

  • 快速重传算法
    当接收端发现丢了一个中间包的时候，发送三次前一个包的 ACK，于是发送端就会快速地重传，不必等待超时再重传。
    TCP 认为这种情况不严重，因为大部分没丢，只丢了一小部分，cwnd 减半为 cwnd/2，然后 sshthresh = cwnd，当三个包返回的时候，cwnd = sshthresh + 3，也就是说没有立刻减到1。

应用层

应用层

常见协议 - HTTP

一次请求的历程

HTTP请求的执行过程：

  1. 先通过DNS将域名解析为IP地址；
  2. 建立TCP连接；
  3. 将HTTP请求放到TCP数据包中发出。

请求

HTTP数据包格式：
HTTP数据包格式

1
2
3
4
5
6
7
GET /somedir/page.html?query-string#anchor HTTP/1.1
　　 Host:www.xxx.com
　　 Connection:close
　　 User-agent:Mozilla/4.0
　　 Accept-language:zh-cn
    Content-length:123
　　...回车符和换行符

第一行是请求行（request line）只有固定的几个字段：
方法 Method 名称是区分大小写的。当某个请求所针对的资源不支持对应的请求方法的时候，服务器应当返回状态码 405（Method Not Allowed），当服务器不认识或者不支持对应的请求方法的时候，应当返回状态码 501（Not Implemented）。

  • GET：向指定的资源发出“显示”请求。使用 GET 方法应该只用在读取数据，而不应当被用于产生“副作用”的操作中，例如在 Web Application 中。其中一个原因是 GET 可能会被网络蜘蛛等随意访问。
  • POST：向指定资源提交数据，请求服务器进行处理（例如提交表单或者上传文件）。数据被包含在请求本文中。这个请求可能会创建新的资源或修改现有资源，或二者皆有。
  • PUT：向指定资源位置上传其最新内容。
  • DELETE：请求服务器删除 Request-URI 所标识的资源。
  • OPTIONS：这个方法可使服务器传回该资源所支持的所有 HTTP 请求方法。用“*”来代替资源名称，向 Web 服务器发送 OPTIONS 请求，可以测试服务器功能是否正常运作。
  • HEAD：与 GET 方法一样，都是向服务器发出指定资源的请求。只不过服务器将不传回资源的本文部分。它的好处在于，使用这个方法可以在不必传输全部内容的情况下，就可以获取其中“关于该资源的信息”（元信息或称元数据）。
  • TRACE：回显服务器收到的请求，主要用于测试或诊断。
  • CONNECT：HTTP/1.1 协议中预留给能够将连接改为渠道方式的代理服务器。通常用于 SSL 加密服务器的链接（经由非加密的 HTTP 代理服务器）。

对象：使用 URL 表示，有时候会带上参数（?query-string）和锚（#anchor）
版本：HTTP/1.1

第二行之后是请求头（request header），包含了很多连接的属性：

  • Host：目标主机。
  • Connection：连接属性，close 表示不适用持久连接，服务器响应后直接关闭连接。
  • User-agent：指定用户代理，这里就是产生当前请求的浏览器的类型，实际上服务器可以根据不同类型的用户代理发送同一个对象的不同版本。
  • Accept-language：指定用户希望接收的语言版本，如果没有的话，服务器应该发送其默认版本。
  • Content-length：可以表示请求体(request-body)内容长度，如果请求有 body 而 header 中没有 Content-length，则返回 400 错误。
    • multipart/form-data
      它将表单的数据组织成 Key-Value 形式，用分隔符 boundary（boundary 可任意设置）处理成一条消息。由于有 boundary 隔离，所以当即上传文件，又有参数的时候，必须要用这种 content-type 类型。如下图所示。
    • x-www-form-urlencoded
      即 application/x-www-from-urlencoded，将表单内的数据转换为 Key-Value。这种和 Get 方法把参数放在 URL 后面一样的想过，这种不能文件上传。
    • raw
      可以上传任意格式的“文本”，可以上传 Text、JSON、XML、HTML 等。
    • binary
      即 Content-Type:application/octet-stream，只可以上传二进制数据流，通常用来上传文件。由于没有键值，所以一次只能上传一个文件。

响应

HTTP响应格式如下所示：
HTTP响应数据包结构

  • 状态码
    状态代码有三位数字组成，第一个数字定义了响应的类别，共分五种类别:
    1xx：指示信息–表示请求已接收，继续处理。
    2xx：成功–表示请求已被成功接收、理解、接受。
    3xx：重定向–要完成请求必须进行更进一步的操作。
    4xx：客户端错误–请求有语法错误或请求无法实现。
    5xx：服务器端错误–服务器未能实现合法的请求。 
    1
    2
    3
    4
    5
    6
    7
    200 OK                        //客户端请求成功
    400 Bad Request               //客户端请求有语法错误，不能被服务器所理解
    401 Unauthorized              //请求未经授权，这个状态代码必须和WWW-Authenticate报头域一起使用 
    403 Forbidden                 //服务器收到请求，但是拒绝提供服务
    404 Not Found                 //请求资源不存在，eg：输入了错误的URL
    500 Internal Server Error     //服务器发生不可预期的错误
    503 Server Unavailable        //服务器当前不能处理客户端的请求，一段时间后可能恢复正常
  • Content-length
    在响应体(response-body)中表示 body 的长度，根据这个值就可以知道 body 的长度，客户端在接收 body 时，就可以根据这个长度来接收数据，而如果没有 Content-length，则客户端会一直接收数据，直到服务端主动断开连接，才表示 body 接收完了；如果是 HTTP1.1，响应头中可以用 Transfer-encoding 字段指定为 chunked 传输，则表示 body 是流式输出，body 会被分成多个块，每块的开始处会标识出当前块的长度，body 不需要通过长度来指定。
  • Keep-Alive（持久连接）
    HTTP/1.0 使用非持久连接，HTTP/1.1 默认使用持久连接，每个连接建立后可以持续用于传送多个对象。
    适合设置 keepalive 连接的场景：客户端的一次请求需要访问同一 Server 多次，比如一个网页包含多个图片，需要访问图片服务器多次才能将这些图片下全。
    持久连接的条件：HTTP1.0响应不带Content-length、HTTP1.1非 chunked 且不带Content-length，这两种情况下 body 长度是不可知的，当服务端在输出完 body 之后，可以考虑使用长连接。另外，还需要考虑客户端的请求头中的Connection字段：如果为 close，则表示客户端需要关掉长连接；如果为 Keep-Alive，那么网关（一般是 Nginx）在输出完响应体之后，会设置当前连接的 keepalive 属性，然后等待客户端的下一次请求；如果没有 Connection 这个头，则根据协议，如果是 HTTP1.0，则默认为 close，如果为 HTTP1.1，则默认为 Keep-Alive。
    但是持久连接也不可能会一直等下去，如果客户端一直不发送数据，岂不是一直占用这个连接？所以一般网关会设置一个最大等待时间，这个值是通过keepalive_timeout属性来配置的，如果值为 0，则表示关闭 keepalive，此时不管 HTTP 版本、Connection 如何设置，都强制为 close。
    如果最后决定打开 keepalive，那么在响应头里也会包含有 Connection 域，如果值为 Close，则网关在响应完数据后，会主动关掉连接。
    总而言之：如果有办法知道服务器传来的长度，都是客户端首先断开，否则一直接收数据，直到服务端断开。
    http1.0
    带 content-length，body 长度可知，客户端在接收 body 时，就可以依据这个长度来接受数据。接受完毕后，就表示这个请求完毕了。客户端主动调用 close 进入四次挥手。
    不带 content-length，body 长度不可知，客户端一直接受数据，直到服务端主动断开。
    http1.1
    带 content-length，body 长度可知，客户端主动断开。
    带 Transfer-encoding: chunked，body 会被分成多个块，每块的开始会标识出当前块的长度，body 就不需要通过 content-length 来指定了。但依然可以知道 body 的长度 客户端主动断开。
    不带 Transfer-encoding：chunked，且不带 content-length，客户端接收数据，直到服务端主动断开连接。

缓存

为了减少网络请求次数，一般可以引入缓存机制，HTTP 服务器通过两种实体头（Entity-Header）来实现缓存的过期：Expires 和 Cache-Control 的 max-age 子项。
Expires/Cache-Control 控制浏览器是否直接从浏览器缓存取数据还是重新发请求到服务器取数据。只是 Cache-Control 比 Expires 可以控制的多一些，而且 Cache-Control 会重写 Expires 的规则。
相关 Header 如下所示：

  • Cache-Control
    常用的值有：
    （1）max-age（单位为 s）指定设置缓存最大的有效时间，定义的是时间长短。当浏览器向服务器发送请求后，在 max-age 这段时间里浏览器就不会再向服务器发送请求了。 （2）s-maxage（单位为 s）同 max-age，只用于共享缓存（比如 CDN 缓存），也就是说 max-age 用于普通缓存，而 s-maxage 用于代理缓存。如果存在 s-maxage，则会覆盖掉 max-age 和 Expires header。 （3）public 指定响应会被缓存，并且在多用户间共享。如果没有指定 public 还是 private，则默认为 public。 （4）private 响应只作为私有的缓存，不能在用户间共享。如果要求 HTTP 认证，响应会自动设置为 private。 （5）no-cache 指定不缓存响应，表明资源不进行缓存，比如，设置了 no-cache 之后并不代表浏览器不缓存，而是在缓存前要向服务器确认资源是否被更改。因此有的时候只设置 no-cache 防止缓存还是不够保险，还可以加上 private 指令，将过期时间设为过去的时间。 （6）no-store 表示绝对禁止缓存。一看就知道，如果用了这个命令，当然就是不会进行缓存啦！每次请求资源都要从服务器重新获取。 （7）must-revalidate 指定如果页面是过期的，则去服务器进行获取。这个指令并不常用，就不做过多的讨论了。
  • Expires
    缓存过期时间，用来指定资源到期的时间，是服务器端的具体时间点。也就是说，Expires=max-age + 请求时间，需要和 Last-modified 结合使用。但在上面我们提到过 cache-control 的优先级更高。Expires 是 Web 服务器响应消息头字段，在响应 HTTP 请求时告诉浏览器在过期时间前浏览器可以直接从浏览器缓存取数据，而无需再次请求。
  • Last-modified
    服务器端文件的最后修改时间，需要和 cache-control 共同使用，是检查服务器端资源是否更新的一种方式。当浏览器再次进行请求时，会向服务器传送 If-Modified-Since 报头，询问 Last-Modified 时间点之后资源是否被修改过。如果没有修改，则返回码为 304，使用缓存；如果修改过，则再次去服务器请求资源，返回码和首次请求相同为 200，资源为服务器最新资源。
  • Etag
    根据实体内容生成一段 hash 字符串，标识资源的状态，由服务端产生。浏览器会将这串字符串传回服务器，验证资源是否已经修改。
    为什么要使用 Etag 呢?Etag 主要为了解决 Last-Modified 无法解决的一些问题。
    一些文件也许会周期性的更改，但是它的内容并不改变（仅仅改变的修改时间），这个时候我们并不希望客户端认为这个文件被修改了，而重新 Get。
    某些文件修改非常频繁，比如在秒以下的时间内进行修改（比方说 1s 内修改了 N 次），If-Modified-Since 能检查到的粒度是 s 级的，这种修改无法判断（或者说 UNIX 记录 MTIME 只能精确到秒）。
    某些服务器不能精确的得到文件的最后修改时间。
    缓存过程如下图所示。
    HTTP缓存

HTTP/1.1

新增方法

新增的 HTTP 方法有 PUT、PATCH、HEAD、OPTIONS、DELETE

主机名标识

在 HTTP/1.0 中 Host 头信息不是必须项，但 HTTP/1.1 中要求必须要有 Host 头信息。

持久性连接

正如前面所说，在 HTTP/1.0 中每个连接只有一个请求，且在这个请求完成后该连接就会被关闭，从而会导致严重的性能下降及延迟问题。HTTP/1.1 引入了对持久性连接的支持，例如：默认情况下连接不会被关闭，在多个连续的请求下它会保存连接的打开状态。想要关闭这些连接，需要将 Connection: close 加入到请求的头信息中。客户端通常会在最后一次请求中发送这个头信息用来安全的关闭连接。

管道机制

HTTP/1.1 也引入了对管道机制的支持，客户端可以向服务器发送多个请求，而无需等待来自同一连接上的服务器响应，并且当收到请求时服务器必须以相同的顺序来响应。但你可能会问客户端是怎么知道第一个响应下载完成和下一个响应内容开始的？要解决这个问题，必须要有 Content-Length 头信息，客户端可以用它来确定响应结束，然后开始等待下一个响应。

HTTP/2

HTTP/2 是专为低延迟传输的内容而设计，它与 HTTP/1.1 之间的差异如下所示：

二进制协议

HTTP/2 倾向于使用二进制协议来减少 HTTP/1.x 中的延迟。二进制协议更容易解析，但可读性相对较差。HTTP/2 中的数据块是帧和流。
帧和流：HTTP 消息是由一个或多个帧组成的。有一个叫做 HEADERS 的帧存放元数据，真正的数据是放在 DATA 帧中的，帧类型定义在 the HTTP/2 specs（HTTP/2 规范），如 HEADERS、DATA、RST_STREAM、SETTINGS、PRIORITY 等。每个 HTTP/2 请求和响应都被赋予一个唯一的流 ID 且放入了帧中。帧就是一块二进制数据。一系列帧的集合就称为流。每个帧都有一个流 id，用于标识它属于哪一个流，每一个帧都有相同的头。同时，除了流标识是唯一的，值得一提的是，客户端发起的任何请求都使用奇数和服务器的响应是偶数的流 id。除了 HEADERS 和 DATA， 另外一个值得说一说帧类型是 RST_STREAM，它是一个特殊的帧类型，用于中止流，如客户端发送这儿帧来告诉服务器我不再需要这个流了。在 HTTP/1.1 中只有一种方式来实现服务器停止发送响应给客户端，那就是关闭连接引起延迟增加，因为后续的请求就需要打开一个新的连接。 在 HTTP/2 中，客户端可以使用 RST_FRAME 来停止接收指定的流而不关闭连接且还可以在此连接中接收其它流。

多路复用

由于 HTTP/2 现在是一个二进制协议，且是使用帧和流来实现请求和响应，一旦 TCP 连接打开了，所有的流都通过这一连接来进行异步的发送而不需要打开额外的连接。反过来，服务器的响应也是异步的方式，如响应是无序的、客户端使用流 id 来标识属于流的包。这就解决了存在于 HTTP/1.x 中 head-of-line 阻塞问题，如客户端将不必耗时等待请求，而其他请求将被处理。如下图所示。
HTTP2.0多路复用

HPACK 头部压缩

它是一个单独的用于明确优化发送 Header RFC 的一部分。它的本质是，当我们同一个客户端不断的访问服务器时，在 header 中发送很多冗余的数据，有时 cookie 就增大 header，且消耗带宽和增加了延迟。为了解决这个问题， HTTP/2 引入了头部压缩。与请求和响应不同，header 不是使用 gzip 或 compress 等压缩格式，它有不同的机制，它使用了霍夫曼编码和在客户端和服务器维护的头部表来消除重复的 headers（如 User Agent)，在后续的请求中就只使用头部表中引用。它与 HTTP/1.1 中的一样，不过增加了伪 header，如 :method、:scheme、:host 和:path。

服务器推送

在服务器端，Server Push 是 HTTTP/2 的另外一个重要功能，我们知道，客户端是通过请求来获取资源的，它可以通过推送资源给客户端而不需客户端主动请求。例如，浏览器载入了一个页面，浏览器解析页面时发现了需要从服务器端载入的内容，接着它就发送一个请求来获取这些内容。Server Push 允许服务器推送数据来减少客户端请求。它是如何实现的呢，服务器在一个新的流中发送一个特殊的帧 PUSH_PROMISE，来通知客户端：“嘿，我要把这个资源发给你!你就不要请求了。”

请求优先级

客户端可以在一个打开的流中在流的 HEADERS 帧中放入优先级信息。在任何时间，客户端都可以发送一个 PRIORITY 的帧来改变流的优先级。如果没有优先级信息，服务器就会异步的处理请求，比如无序处理。如果流被赋予了优先级，它就会基于这个优先级来处理，由服务器决定需要多少资源来处理该请求。
安全。大家对 HTTP/2 是否强制使用安全连接（通过 TLS）进行了充分的讨论。最后的决定是不强制使用。然而，大多数厂商表示，他们将只支持基于 TLS 的 HTTP/2。所以，尽管 HTTP/2 规范不需要加密，但它已经成为默认的强制执行的。在这种情况下，基于 TLS 实现的 HTTP/2 需要的 TLS 版本最低要求是 1.2。 因此必须有最低限度的密钥长度、临时密钥等。

一次网络请求的历程

  1. 暴露服务器IP
    外网 IP 是放在虚拟网关的外网网口上的，这个 IP 是通过 BGP 路由协议让全世界知道的，也就是说网络上能找到某个IP的服务器的所在位置了。
  2. 域名解析
    通过DNS解析域名为IP.

    当这个 DNS 本地有缓存，则直接返回；如果没有缓存，本地 DNS 才需要递归地从根 DNS 服务器，查到.com 的顶级域名服务器，最终查到权威 DNS 服务器。

  3. 建立连接
    HTTP是基于TCP的，要传输HTTP数据包自然是需要先建立TCP连接。
    HTTPS的连接需要在TCP连接建立完毕后再建立一层TLS连接，连接建立完毕后即可进行对称加密传输。
  4. 发送数据包
    上层的数据交给下层时会首先进行一次封装，附加上下层协议规定的参数，比如TCP就是源、目标端口号、IP等。
  5. 转发：从私网到公网
    每个局域网一般都是通过NAT网关与外界相连的，从NAT网关出去后IP会被更换为公网可识别的IP地址，或者可以说——数据包进入了互联网。
  6. 转发：从公网到私网
    在虚拟网关节点的外网网口上，会有一个 NAT 规则，将公网 IP 地址转换为 VPC 里面的私网 IP 地址，这个私网 IP 地址就是 SLB 的 HAProxy 所在的虚拟机的私网 IP 地址。

QA

网络为什么需要分层？

将网络请求这种复杂的任务拆解，每层做该层需要做的事，可以让每层的协议实现尽量精简。

UDP 与 TCP 之间的区别？

TCP 和 UDP 的区别

为什么TCP建立连接是3次握手而不是2次或4次？

  • 如果是2次握手
    比如A和B建立连接时，A可能会重试发送，但此时可能前面的请求由于网络等情况没有及时送到B，后来重试的请求先建立了连接，然后先发出的请求才送到，这个连接仍然建立了，但是却没有任何作用（因为A已经默认之前发出的请求都失败了）。
    TCP如果是2次握手可能存在的问题
    为了解决上面的问题，必须要有一个“应答之应答”，A需要告诉B这个连接的建立是有效的，因此需要3次握手。
    那么为什么不是4次握手或更多次的握手呢？主要是因为很多次也不能保证就真的可靠了，而且太多次对效率也会有比较大的影响。

为什么TCP关闭连接是4次挥手而不是2次或6次？

发表于 更新于 分类于

二叉树、平衡树、AVL 树和红黑树

二叉树是一类特殊的树形结构，其他类似的还有三叉树、B 树、B+树等，二叉树的特征是 1 对 2，即每个节点都有 2 个子节点（这里认为空节点也算子节点）。

这么定义主要是为了避免将二叉树的实现局限于指针，实际上我们也可以使用数组来实现二叉树，也就是二叉堆。

二叉树所有操作的时间复杂度为O(logN)，但是它存在的主要问题是不稳定，比如数据是从小到大依次插入的情况下，最终结果是得到一条斜线，这时二叉树会退化为链表。
平衡树的特点是在每次写入操作后会进行一次重平衡，让树的高度保持在O(logN)。
AVL 树是平衡树的一种，它严格保证树的高度为O(logN)，每次都会根据高度重平衡，其缺点是过于严格，会导致旋转操作占用比较多的时间。
红黑树作为 AVL 树的一种替代，通过红黑规则控制树的旋转，能以较少次旋转作为代价得到较为平衡的树。

AVL 树严格保证树的高度在[logN, logN + 1]，红黑树理论上极端情况可以出现高度达到 2*logN，但是现实中很难遇到。

红黑树的起源 - 23树

23树的分裂
23树并不是指3叉树，23树是一种平衡树，不过它维持平衡的方式并不是旋转，而是分裂，如上图所示：

  • 一个节点有至多3个元素，当达到3个元素后会发生分裂；
  • 分裂后中间元素上移，与父节点合并。

23树可以证明高度在log3(N)=(lgN)/(lg3)（如果都是3-nodes即2元素节点）到lgN（如果都是2-nodes即1元素节点），从而保证查询时顶多查lgN个节点。
23树的缺点是实现的额外开销过大，比如要变更节点类型、比较是否相等时要比较节点中的所有元素值等，有时候23树的性能甚至不如普通的BST，因此Sedgewick之后便提出了红黑树。

红黑树的定义

红黑树是从23树演化而来的，它将原来2-3树中的3-nodes表示为使用红线连接的两个节点，因为每个节点只有一条线连上它，因此为了简单起见把颜色字段保存到节点里。
23树和红黑树
红黑树的定义：

  1. Red links lean left. - 红色节点必须在左边
  2. No node has two red links connected to it. - 3个红色节点不能连一起
  3. The tree has perfect black balance: every path from the root to a null link has the same number of black links. - 红黑树是完美黑平衡的，从root沿任意路径到达叶节点的黑节点数量都是一样的。

以上3个定义其实和2-3树的定义是一一对应的：

  1. 和左红节点连一块可以看作2-3树中的一个3-node；
  2. 2-3树中一个节点中塞满3个元素后就会分裂；
  3. 把红黑树中节点和其左红子节点合并后，最终的树其实和2-3树等价。

红黑树的红黑规则：

  1. 任何一个节点都有颜色，黑色或者红色；
  2. 根节点是黑色的；
  3. 空节点（有些实现中叶节点是哨兵节点nil）被认为是黑色的。
  4. 父子节点之间不能出现两个连续的红节点（如果父节点是红色，则它的两个儿子都是黑色）；
  5. 任何一个节点向下遍历到其子孙的叶子节点，所经过的黑节点个数必须相等；

红黑树操作 - 查询

红黑树的查询就是普通的二叉树查询。

红黑树操作 - 旋转

左旋操作将右子节点旋转到父节点位置，并改变二者的颜色。
红黑树左旋
右旋同理：
红黑树右旋

红黑树操作 - 插入

红黑树的插入操作和 BST 差不多，只不过插入后可能会破坏上面红黑树的定义，因此需要做一些旋转和颜色修改操作来恢复。
很多地方描述红黑树的方式并不一致，这里还是以《算法》中的实现为主。
插入节点到一个3-node的3种情况

  • 可以看到上面3种情况最终都转换成了一个三角形的形状，然后进行了颜色的翻转，实际上相当于2-3树中一个3元素节点分裂成了3个。

下图是一个插入节点到红黑树中的例子，其中被红线连接的子节点是红色的节点：
红黑树节点插入轨迹

红黑树操作 - 删除

参考

  1. 《Algorithms》 - Robert_Sedgewick
    红黑树原来是从23树演化而来，之前以为是凭空编出来的。
  2. 《Algorithms》中的红黑树实现

发表于 更新于 分类于

实验内容

1-3：了解 Linux 的启动过程、用户空间是如何与内核空间进行交互的。
4-5：了解进程的执行原理、状态的转换过程，及进程之间是如何转换的。
6：通过信号量机制了解内核是如何实现同步的。
7、9：了解内核的内存和文件系统的实现原理。
8：了解内核如何实现设备管理，明白驱动是如何实现的。
10：图形界面是开课老师提到的扩展实验。

阅读全文 »

发表于 更新于 分类于

分布式一致性协议的演化

2PC

3PC

与 2PC 的区别是：

  1. 将 2PC 的 prepare 阶段拆为 CanCommit 和 PreCommit 两个阶段，其中：
    • CanCommit 阶段：参与者需要判断是否可以执行事务提交操作
      这个阶段如果出现超时、某个参与者返回 No 等情况，事务直接失败；
      在所有参与者 CanCommit 阶段都返回 Yes 响应后可以进入 PreCommit 阶段；
    • PreCommit 阶段：预提交即执行事务操作，并记录 undo 和 redo 日志，这时本地事务还未 commit
      这个阶段如果有任何一个参与者向协调者返回了 No 响应或超时协调者还未接收到参与者的响应，则协调者会开始执行事务的 abort；
      如果所有参与者都返回了 ACK 响应，则可以进入最终的 doCommit 阶段；
    • abort：上一步，如果要开始执行中断事务，协调者会向所有参与者发送 abort 请求，参与者接收
    • doCommit 阶段：

Paxos

与 2PC（及其衍生协议）区别

Paxos 协议和 2PC 协议在分布式系统中所起的作用并不相同。Paxos 协议用于保证同一个数据分片的多个副本之间的数据一致性。当这些副本分布到不同的数据中心时，这个需求尤其强烈。2PC 协议用于保证属于多个数据分片上的操作的原子性。这些数据分片可能分布在不同的服务器上，2PC 协议保证多台服务器上的操作要么全部成功，要么全部失败。
Paxos 协议有两种用法：一种用法是用它来实现全局的锁服务或者命名和配置服务，例如 Google Chubby 以及 Apache Zookeeper。另外一种用法是用它来将用户数据复制到多个数据中心，例如 Google Megastore 以及 Google Spanner。
2PC 协议最大的缺陷在于无法处理协调者宕机问题。如果协调者宕机，那么，2PC 协议中的每个参与者可能都不知道事务应该提交还是回滚，整个协议被阻塞，执行过程中申请的资源都无法释放。因此，常见的做法是将 2PC 和 Paxos 协议结合起来，通过 2PC 保证多个数据分片上的操作的原子性，通过 Paxos 协议实现同一个数据分片的多个副本之间的一致性（一般）。另外，通过 Paxos 协议解决 2PC 协议中协调者宕机问题。当 2PC 协议中的协调者出现故障时，通过 Paxos 协议选举出新的协调者继续提供服务，可以解决单点故障问题（但是你确定服务参与者足够多能够发起一次选举吗？）。

Paxos

Basic Paxos（单值Paxos）

目前在多个proposer可以同时发起提议的情况下，满足P1、P2a即能做到确定并只确定一个值。如果再加上节点宕机恢复、消息丢包的考量呢？
假设acceptor c 宕机一段时间后恢复，c 宕机期间其他acceptor已经确定了一项值为v的决议但c 因为宕机并不知晓；c 恢复后如果有proposer马上发起一项值不是v的提议，由于条件P1，c 会接受该提议，这与P2a矛盾。为了避免这样的情况出现，进一步地我们对proposer作约束：

1
P2b. 如果一项值为v的提议被确定，那么proposer后续只发起值为v的提议

满足P2b则P2a成立 (P2b => P2a => P2)。
P2b约束的是提议被确定(chosen)后proposer的行为，我们更关心提议被确定前proposer应该怎么做：

1
P2c. 对于提议(n,v)，acceptor的多数派S中，如果存在acceptor最近一次(即ID值最大)接受的提议的值为v'，那么要求v = v'；否则v可为任意值

满足P2c则P2b成立 (P2c => P2b => P2a => P2)。

条件P2c是Basic Paxos的核心，光看P2c的描述可能会觉得一头雾水，我们通过 The Part-Time Parliament中的例子加深理解：
BasicPaxos例子
假设有A~E 5个acceptor，- 表示acceptor因宕机等原因缺席当次决议，x 表示acceptor不接受提议，o 表示接受提议；多数派acceptor接受提议后提议被确定，以上表格对应的决议过程如下：
ID为2的提议最早提出，根据P2c其提议值可为任意值，这里假设为a
acceptor A/B/C/E 在之前的决议中没有接受(accept)任何提议，因而ID为5的提议的值也可以为任意值，这里假设为b
acceptor B/D/E，其中D曾接受ID为2的提议，根据P2c，该轮ID为14的提议的值必须与ID为2的提议的值相同，为a
acceptor A/C/D，其中D曾接受ID为2的提议、C曾接受ID为5的提议，相比之下ID 5较ID 2大，根据P2c，该轮ID为27的提议的值必须与ID为5的提议的值相同，为b；该轮决议被多数派acceptor接受，因此该轮决议得以确定
acceptor B/C/D，3个acceptor之前都接受过提议，相比之下C、D曾接受的ID 27的ID号最大，该轮ID为29的提议的值必须与ID为27的提议的值相同，为b
以上提到的各项约束条件可以归纳为3点，如果proposer/acceptor满足下面3点，那么在少数节点宕机、网络分化隔离的情况下，在“确定并只确定一个值”这件事情上可以保证一致性(consistency)：
B1(ß): ß中每一轮决议都有唯一的ID标识
B2(ß): 如果决议B被acceptor多数派接受，则确定决议B
B3(ß): 对于ß中的任意提议B(n,v)，acceptor的多数派中如果存在acceptor最近一次(即ID值最大)接受的提议的值为v’，那么要求v = v’；否则v可为任意值
(注: 希腊字母ß表示多轮决议的集合，字母B表示一轮决议)
另外为保证P2c，我们对acceptor作两个要求：

  1. 记录曾接受的ID最大的提议，因proposer需要问询该信息以决定提议值
  2. 在回应提议ID为n的proposer自己曾接受过ID最大的提议时，acceptor同时保证(promise)不再接受ID小于n的提议
    至此，proposer/acceptor完成一轮决议可归纳为prepare和accept两个阶段。prepare阶段proposer发起提议问询提议值、acceptor回应问询并进行promise；accept阶段完成决议，图示如下：
    accept流程
    还有一个问题需要考量，假如proposer A发起ID为n的提议，在提议未完成前proposer B又发起ID为n+1的提议，在n+1提议未完成前proposer C又发起ID为n+2的提议…… 如此acceptor不能完成决议、形成活锁(livelock)，虽然这不影响一致性，但我们一般不想让这样的情况发生。解决的方法是从proposer中选出一个leader，提议统一由leader发起。
    最后我们再引入一个新的角色：learner，learner依附于acceptor，用于习得已确定的决议。以上决议过程都只要求acceptor多数派参与，而我们希望尽量所有acceptor的状态一致。如果部分acceptor因宕机等原因未知晓已确定决议，宕机恢复后可经本机learner采用pull的方式从其他acceptor习得。

Multi Paxos（多值Paxos）

通过以上步骤分布式系统已经能确定一个值，“只确定一个值有什么用？这可解决不了我面临的问题。” 你心中可能有这样的疑问。
其实不断地进行“确定一个值”的过程、再为每个过程编上序号，就能得到具有全序关系(total order)的系列值，进而能应用在数据库副本存储等很多场景。我们把单次“确定一个值”的过程称为实例(instance)，它由proposer/acceptor/learner组成，下图说明了A/B/C三机上的实例：
MultiPaxos
不同序号的实例之间互相不影响，A/B/C三机输入相同、过程实质等同于执行相同序列的状态机(state machine)指令 ，因而将得到一致的结果。
proposer leader在Multi Paxos中还有助于提升性能，常态下统一由leader发起提议，可节省prepare步骤(leader不用问询acceptor曾接受过的ID最大的提议、只有leader提议也不需要acceptor进行promise)直至发生leader宕机、重新选主。

总结

以上介绍了Paxos的推演过程、如何在Basic Paxos的基础上通过状态机构建Multi Paxos。
微信后台开发同学实现并开源了一套基于Paxos协议的多机状态拷贝类库PhxPaxos，PhxPaxos用于将单机服务扩展到多机，其经过线上系统验证并在一致性保证、性能等方面作了很多考量。

Paxos变种和优化

如果想把Paxos应用于工程实践，了解基本原理还不够。
有很多基于Paxos的优化，在保证一致性协议正确(safety)的前提下，减少Paxos决议通信步骤、避免单点故障、实现节点负载均衡，从而降低时延、增加吞吐量、提升可用性，下面我们就来了解这些Paxos变种。

Multi Paxos

首先我们来回顾一下Multi Paxos，Multi Paxos在Basic Paxos的基础上确定一系列值，其决议过程如下：
MultiPaxos例子
phase1a: leader提交提议给acceptor
phase1b: acceptor返回最近一次接受的提议(即曾接受的最大的提议ID和对应的value)，未接受过提议则返回空
phase2a: leader收集acceptor的应答，分两种情况处理
phase2a.1: 如果应答内容都为空，则自由选择一个提议value
phase2a.2: 如果应答内容不为空，则选择应答里面ID最大的提议的value
phase2b: acceptor将决议同步给learner
Multi Paxos中leader用于避免活锁，但leader的存在会带来其他问题，一是如何选举和保持唯一leader(虽然无leader或多leader不影响一致性，但影响决议进程progress)，二是充当leader的节点会承担更多压力，如何均衡节点的负载。Mencius[1]提出节点轮流担任leader，以达到均衡负载的目的；租约(lease)可以帮助实现唯一leader，但leader故障情况下可导致服务短期不可用。

Fast Paxos

在Multi Paxos中，proposer -> leader -> acceptor -> learner，从提议到完成决议共经过3次通信，能不能减少通信步骤？
对Multi Paxos phase2a，如果可以自由提议value，则可以让proposer直接发起提议、leader退出通信过程，变为proposer -> acceptor -> learner，这就是Fast Paxos[2]的由来。
FastPaxos例子
Multi Paxos里提议都由leader提出，因而不存在一次决议出现多个value，Fast Paxos里由proposer直接提议，一次决议里可能有多个proposer提议、出现多个value，即出现提议冲突(collision)。leader起到初始化决议进程(progress)和解决冲突的作用，当冲突发生时leader重新参与决议过程、回退到3次通信步骤。
Paxos自身隐含的一个特性也可以达到减少通信步骤的目标，如果acceptor上一次确定(chosen)的提议来自proposerA，则当次决议proposerA可以直接提议减少一次通信步骤。如果想实现这样的效果，需要在proposer、acceptor记录上一次决议确定(chosen)的历史，用以在提议前知道哪个proposer的提议上一次被确定、当次决议能不能节省一次通信步骤。

EPaxos

除了从减少通信步骤的角度提高Paxos决议效率外，还有其他方面可以降低Paxos决议时延，比如Generalized Paxos[3]提出不冲突的提议(例如对不同key的写请求)可以同时决议、以降低Paxos时延。
更进一步地，EPaxos[4](Egalitarian Paxos)提出一种既支持不冲突提议同时提交降低时延、还均衡各节点负载、同时将通信步骤减少到最少的Paxos优化方法。
为达到这些目标，EPaxos的实现有几个要点。一是EPaxos中没有全局的leader，而是每一次提议发起提议的proposer作为当次提议的leader(command leader)；二是不相互影响(interfere)的提议可以同时提交；三是跳过prepare，直接进入accept阶段。EPaxos决议的过程如下：
EPaxos的accept过程

小结

以上介绍了几个基于Paxos的变种，Mencius中节点轮流做leader、均衡节点负载，Fast Paxos减少一次通信步骤，Generalized Paxos允许互不影响的决议同时进行，EPaxos无全局leader、各节点平等分担负载。

Raft

Paxos 偏向于理论、对如何应用到工程实践提及较少。理解的难度加上现实的骨感，在生产环境中基于 Paxos 实现一个正确的分布式系统非常难。
Raft 在 2013 年提出，提出的时间虽然不长，但已经有很多系统基于 Raft 实现。相比 Paxos，Raft 的优点就是更利于理解、更易于实行。
为达到更容易理解和实行的目的，Raft 将问题分解和具体化：Leader 统一处理变更操作请求，一致性协议的作用具化为保证节点间操作日志副本(log replication)一致，以 term 作为逻辑时钟(logical clock)保证时序，节点运行相同状态机(state machine)得到一致结果。Raft 协议具体过程如下：

Raft执行流程

  1. Client 发起请求，每一条请求包含操作指令
  2. 请求交由 Leader 处理，Leader 将操作指令(entry)追加(append)至操作日志，紧接着对 Follower 发起 AppendEntries 请求、尝试让操作日志副本在 Follower 落地
  3. 如果 Follower 多数派(quorum)同意 AppendEntries 请求，Leader 进行 commit 操作、把指令交由状态机处理
  4. 状态机处理完成后将结果返回给 Client

指令通过 log index(指令 id)和 term number 保证时序，正常情况下 Leader、Follower 状态机按相同顺序执行指令，得出相同结果、状态一致。
宕机、网络分化等情况可引起 Leader 重新选举(每次选举产生新 Leader 的同时，产生新的 term)、Leader/Follower 间状态不一致。Raft 中 Leader 为自己和所有 Follower 各维护一个 nextIndex 值，其表示 Leader 紧接下来要处理的指令 id 以及将要发给 Follower 的指令 id，LnextIndex 不等于 FnextIndex 时代表 Leader 操作日志和 Follower 操作日志存在不一致，这时将从 Follower 操作日志中最初不一致的地方开始，由 Leader 操作日志覆盖 Follower，直到 LnextIndex、FnextIndex 相等。
Paxos 中 Leader 的存在是为了提升决议效率，Leader 的有无和数目并不影响决议一致性，Raft 要求具备唯一 Leader，并把一致性问题具体化为保持日志副本的一致性，以此实现相较 Paxos 而言更容易理解、更容易实现的目标。

Zab

Zab 的全称是 Zookeeper atomic broadcast protocol，是 Zookeeper 内部用到的一致性协议。相比 Paxos，Zab 最大的特点是保证强一致性(strong consistency，或叫线性一致性 linearizable consistency)。
和 Raft 一样，Zab 要求唯一 Leader 参与决议，Zab 可以分解成 discovery、sync、broadcast 三个阶段：
Zab原理

  • discovery
    选举产生PL(prospective leader)，PL 收集Follower epoch(cepoch)，根据Follower的反馈 PL 产生newepoch(每次选举产生新 Leader 的同时产生新 epoch，类似 Raft 的 term)。
  • sync
    PL 补齐相比 Follower 多数派缺失的状态、之后各 Follower 再补齐相比 PL 缺失的状态，PL 和 Follower 完成状态同步后 PL 变为**正式 Leader(established leader)**。
  • broadcast
    Leader 处理 Client 的写操作，并将状态变更广播至 Follower，Follower多数派通过之后 Leader 发起将状态变更**提交(deliver/commit)**。

Leader 和 Follower 之间通过心跳判别健康状态，正常情况下 Zab 处在 broadcast 阶段，出现 Leader 宕机、网络隔离等异常情况时 Zab 重新回到 discovery 阶段。

Zookeeper介绍

Zookeeper是一个开源的分布式协调服务，其设计目标是将那些复杂的且容易出错的分布式一致性服务封装起来，构成一个高效可靠的原语集，并以一些列简单的接口提供给用户使用。其是一个典型的分布式数据一致性的解决方案，分布式应用程序可以基于它实现诸如数据发布/发布、负载均衡、命名服务、分布式协调/通知、集群管理、Master选举、分布式锁和分布式队列等功能。其可以保证如下分布式一致性特性。

  1. 顺序一致性，从同一个客户端发起的事务请求，最终将会严格地按照其发起顺序被应用到Zookeeper中去。
  2. 原子性，所有事务请求的处理结果在整个集群中所有机器上的应用情况是一致的，即整个集群要么都成功应用了某个事务，要么都没有应用。
  3. 单一视图，无论客户端连接的是哪个Zookeeper服务器，其看到的服务端数据模型都是一致的。
  4. 可靠性，一旦服务端成功地应用了一个事务，并完成对客户端的响应，那么该事务所引起的服务端状态变更将会一直被保留，除非有另一个事务对其进行了变更。
  5. 实时性，Zookeeper保证在一定的时间段内，客户端最终一定能够从服务端上读取到最新的数据状态。

设计目标

Zookeeper致力于提供一个高性能、高可用、且具有严格的顺序访问控制能力（主要是写操作的严格顺序性）的分布式协调服务，其具有如下的设计目标。

  1. 简单的数据模型，Zookeeper使得分布式程序能够通过一个共享的树形结构的名字空间来进行相互协调，即Zookeeper服务器内存中的数据模型由一系列被称为ZNode的数据节点组成，Zookeeper将全量的数据存储在内存中，以此来提高服务器吞吐、减少延迟的目的。
  2. 可构建集群，一个Zookeeper集群通常由一组机器构成，组成Zookeeper集群的而每台机器都会在内存中维护当前服务器状态，并且每台机器之间都相互通信。
  3. 顺序访问，对于来自客户端的每个更新请求，Zookeeper都会分配一个全局唯一的递增编号，这个编号反映了所有事务操作的先后顺序。
  4. 高性能，Zookeeper将全量数据存储在内存中，并直接服务于客户端的所有非事务请求，因此它尤其适用于以读操作为主的应用场景。

基本概念

  1. 集群角色，最典型的集群就是Master/Slave模式（主备模式），此情况下把所有能够处理写操作的机器称为Master机器，把所有通过异步复制方式获取最新数据，并提供读服务的机器为Slave机器。Zookeeper引入了Leader、Follower、Observer三种角色，Zookeeper集群中的所有机器通过Leader选举过程来选定一台被称为Leader的机器，Leader服务器为客户端提供写服务，Follower和Observer提供读服务，但是Observer不参与Leader选举过程，不参与写操作的过半写成功策略，Observer可以在不影响写性能的情况下提升集群的性能。
  2. 会话，指客户端会话，一个客户端连接是指客户端和服务端之间的一个TCP长连接，Zookeeper对外的服务端口默认为2181，客户端启动的时候，首先会与服务器建立一个TCP连接，从第一次连接建立开始，客户端会话的生命周期也开始了，通过这个连接，客户端能够心跳检测与服务器保持有效的会话，也能够向Zookeeper服务器发送请求并接受响应，同时还能够通过该连接接受来自服务器的Watch事件通知。
  3. 数据节点，第一类指构成集群的机器，称为机器节点，第二类是指数据模型中的数据单元，称为数据节点-Znode，Zookeeper将所有数据存储在内存中，数据模型是一棵树，由斜杠/进行分割的路径，就是一个ZNode，如/foo/path1，每个ZNode都会保存自己的数据内存，同时还会保存一些列属性信息。ZNode分为持久节点和临时节点两类，持久节点是指一旦这个ZNode被创建了，除非主动进行ZNode的移除操作，否则这个ZNode将一直保存在Zookeeper上，而临时节点的生命周期和客户端会话绑定，一旦客户端会话失效，那么这个客户端创建的所有临时节点都会被移除。另外，Zookeeper还允许用户为每个节点添加一个特殊的属性：SEQUENTIAL。一旦节点被标记上这个属性，那么在这个节点被创建的时候，Zookeeper会自动在其节点后面追加一个整形数字，其是由父节点维护的自增数字。
  4. 版本，对于每个ZNode，Zookeeper都会为其维护一个叫作Stat的数据结构，Stat记录了这个ZNode的三个数据版本，分别是version（当前ZNode的版本）、cversion（当前ZNode子节点的版本）、aversion（当前ZNode的ACL版本）。
  5. Watcher，Zookeeper允许用户在指定节点上注册一些Watcher，并且在一些特定事件触发的时候，Zookeeper服务端会将事件通知到感兴趣的客户端。
  6. ACL，Zookeeper采用ACL（Access Control Lists）策略来进行权限控制，其定义了如下五种权限：
    · CREATE：创建子节点的权限。
    · READ：获取节点数据和子节点列表的权限。
    · WRITE：更新节点数据的权限。
    · DELETE：删除子节点的权限。
    · ADMIN：设置节点ACL的权限。

ZAB协议

Zookeeper使用了Zookeeper Atomic Broadcast（ZAB，Zookeeper原子消息广播协议）的协议作为其数据一致性的核心算法。ZAB协议是为Zookeeper专门设计的一种支持崩溃恢复的原子广播协议。
Zookeeper依赖ZAB协议来实现分布式数据的一致性，基于该协议，Zookeeper实现了一种主备模式的系统架构来保持集群中各副本之间的数据的一致性，即其使用一个单一的主进程来接收并处理客户端的所有事务请求，并采用ZAB的原子广播协议，将服务器数据的状态变更以事务Proposal的形式广播到所有的副本进程中，ZAB协议的主备模型架构保证了同一时刻集群中只能够有一个主进程来广播服务器的状态变更，因此能够很好地处理客户端大量的并发请求。
ZAB协议的核心是定义了对于那些会改变Zookeeper服务器数据状态的事务请求的处理方式，即：所有事务请求必须由一个全局唯一的服务器来协调处理，这样的服务器被称为Leader服务器，余下的服务器则称为Follower服务器，Leader服务器负责将一个客户端事务请求转化成一个事务Proposal（提议），并将该Proposal分发给集群中所有的Follower服务器，之后Leader服务器需要等待所有Follower服务器的反馈，一旦超过半数的Follower服务器进行了正确的反馈后，那么Leader就会再次向所有的Follower服务器分发Commit消息，要求其将前一个Proposal进行提交。
ZAB协议包括两种基本的模式：崩溃恢复和消息广播。
当整个服务框架启动过程中或Leader服务器出现网络中断、崩溃退出与重启等异常情况时，ZAB协议就会进入恢复模式并选举产生新的Leader服务器。当选举产生了新的Leader服务器，同时集群中已经有过半的机器与该Leader服务器完成了状态同步之后，ZAB协议就会退出恢复模式，状态同步时指数据同步，用来保证集群在过半的机器能够和Leader服务器的数据状态保持一致。
当集群中已经有过半的Follower服务器完成了和Leader服务器的状态同步，那么整个服务框架就可以进入消息广播模式，当一台同样遵守ZAB协议的服务器启动后加入到集群中，如果此时集群中已经存在一个Leader服务器在负责进行消息广播，那么加入的服务器就会自觉地进入数据恢复模式：找到Leader所在的服务器，并与其进行数据同步，然后一起参与到消息广播流程中去。Zookeeper只允许唯一的一个Leader服务器来进行事务请求的处理，Leader服务器在接收到客户端的事务请求后，会生成对应的事务提议并发起一轮广播协议，而如果集群中的其他机器收到客户端的事务请求后，那么这些非Leader服务器会首先将这个事务请求转发给Leader服务器。
当Leader服务器出现崩溃或者机器重启、集群中已经不存在过半的服务器与Leader服务器保持正常通信时，那么在重新开始新的一轮的原子广播事务操作之前，所有进程首先会使用崩溃恢复协议来使彼此到达一致状态，于是整个ZAB流程就会从消息广播模式进入到崩溃恢复模式。一个机器要成为新的Leader，必须获得过半机器的支持，同时由于每个机器都有可能会崩溃，因此，ZAB协议运行过程中，前后会出现多个Leader，并且每台机器也有可能会多次成为Leader，进入崩溃恢复模式后，只要集群中存在过半的服务器能够彼此进行正常通信，那么就可以产生一个新的Leader并再次进入消息广播模式。如一个由三台机器组成的ZAB服务，通常由一个Leader、2个Follower服务器组成，某一个时刻，加入其中一个Follower挂了，整个ZAB集群是不会中断服务的。

  1. 消息广播，ZAB协议的消息广播过程使用原子广播协议，类似于一个二阶段提交过程，针对客户端的事务请求，Leader服务器会为其生成对应的事务Proposal，并将其发送给集群中其余所有的机器，然后再分别收集各自的选票，最后进行事务提交。

在ZAB的二阶段提交过程中，移除了中断逻辑，所有的Follower服务器要么正常反馈Leader提出的事务Proposal，要么就抛弃Leader服务器，同时，ZAB协议将二阶段提交中的中断逻辑移除意味着我们可以在过半的Follower服务器已经反馈Ack之后就开始提交事务Proposal，而不需要等待集群中所有的Follower服务器都反馈响应，但是，在这种简化的二阶段提交模型下，无法处理Leader服务器崩溃退出而带来的数据不一致问题，因此ZAB采用了崩溃恢复模式来解决此问题，另外，整个消息广播协议是基于具有FIFO特性的TCP协议来进行网络通信的，因此能够很容易保证消息广播过程中消息接受与发送的顺序性。再整个消息广播过程中，Leader服务器会为每个事务请求生成对应的Proposal来进行广播，并且在广播事务Proposal之前，Leader服务器会首先为这个事务Proposal分配一个全局单调递增的唯一ID，称之为事务ID（ZXID），由于ZAB协议需要保证每个消息严格的因果关系（顺序一致性>因果一致性），因此必须将每个事务Proposal按照其ZXID的先后顺序来进行排序和处理。

  1. 崩溃恢复，在Leader服务器出现崩溃，或者由于网络原因导致Leader服务器失去了与过半Follower的联系，那么就会进入崩溃恢复模式，在ZAB协议中，为了保证程序的正确运行，整个恢复过程结束后需要选举出一个新的Leader服务器，因此，ZAB协议需要一个高效且可靠的Leader选举算法，从而保证能够快速地选举出新的Leader，同时，Leader选举算法不仅仅需要让Leader自身知道已经被选举为Leader，同时还需要让集群中的所有其他机器也能够快速地感知到选举产生的新的Leader服务器。
  2. 基本特性，ZAB协议规定了如果一个事务Proposal在一台机器上被处理成功，那么应该在所有的机器上都被处理成功，哪怕机器出现故障崩溃。ZAB协议需要确保那些已经在Leader服务器上提交的事务最终被所有服务器都提交，假设一个事务在Leader服务器上被提交了，并且已经得到了过半Follower服务器的Ack反馈，但是在它Commit消息发送给所有Follower机器之前，Leader服务挂了。如下图所示

在集群正常运行过程中的某一个时刻，Server1是Leader服务器，其先后广播了P1、P2、C1、P3、C2（C2是Commit Of Proposal2的缩写），其中，当Leader服务器发出C2后就立即崩溃退出了，针对这种情况，ZAB协议就需要确保事务Proposal2最终能够在所有的服务器上都被提交成功，否则将出现不一致。
ZAB协议需要确保丢弃那些只在Leader服务器上被提出的事务。如果在崩溃恢复过程中出现一个需要被丢弃的提议，那么在崩溃恢复结束后需要跳过该事务Proposal，如下图所示
假设初始的Leader服务器Server1在提出一个事务Proposal3之后就崩溃退出了，从而导致集群中的其他服务器都没有收到这个事务Proposal，于是，当Server1恢复过来再次加入到集群中的时候，ZAB协议需要确保丢弃Proposal3这个事务。
在上述的崩溃恢复过程中需要处理的特殊情况，就决定了ZAB协议必须设计这样的Leader选举算法：能够确保提交已经被Leader提交的事务的Proposal，同时丢弃已经被跳过的事务Proposal。如果让Leader选举算法能够保证新选举出来的Leader服务器拥有集群中所有机器最高编号（ZXID最大）的事务Proposal，那么就可以保证这个新选举出来的Leader一定具有所有已经提交的提议，更为重要的是如果让具有最高编号事务的Proposal机器称为Leader，就可以省去Leader服务器查询Proposal的提交和丢弃工作这一步骤了。

  1. 数据同步，完成Leader选举后，在正式开始工作前，Leader服务器首先会确认日志中的所有Proposal是否都已经被集群中的过半机器提交了，即是否完成了数据同步。Leader服务器需要确所有的Follower服务器都能够接收到每一条事务Proposal，并且能够正确地将所有已经提交了的事务Proposal应用到内存数据库中。Leader服务器会为每个Follower服务器维护一个队列，并将那些没有被各Follower服务器同步的事务以Proposal消息的形式逐个发送给Follower服务器，并在每一个Proposal消息后面紧接着再发送一个Commit消息，以表示该事务已经被提交，等到Follower服务器将所有其尚未同步的事务Proposal都从Leader服务器上同步过来并成功应用到本地数据库后，Leader服务器就会将该Follower服务器加入到真正的可用Follower列表并开始之后的其他流程。
    下面分析ZAB协议如何处理需要丢弃的事务Proposal的，ZXID是一个64位的数字，其中32位可以看做是一个简单的单调递增的计数器，针对客户端的每一个事务请求，Leader服务器在产生一个新的事务Proposal时，都会对该计数器进行加1操作，而高32位则代表了Leader周期epoch的编号，每当选举产生一个新的Leader时，就会从这个Leader上取出其本地日志中最大事务Proposal的ZXID，并解析出epoch值，然后加1，之后以该编号作为新的epoch，低32位则置为0来开始生成新的ZXID，ZAB协议通过epoch号来区分Leader周期变化的策略，能够有效地避免不同的Leader服务器错误地使用不同的ZXID编号提出不一样的事务Proposal的异常情况。当一个包含了上一个Leader周期中尚未提交过的事务Proposal的服务器启动时，其肯定无法成为Leader，因为当前集群中一定包含了一个Quorum（过半）集合，该集合中的机器一定包含了更高epoch的事务的Proposal，因此这台机器的事务Proposal并非最高，也就无法成为Leader。
    2.4 ZAB协议原理
    ZAB主要包括消息广播和崩溃恢复两个过程，进一步可以分为三个阶段，分别是发现（Discovery）、同步（Synchronization）、广播（Broadcast）阶段。ZAB的每一个分布式进程会循环执行这三个阶段，称为主进程周期。
    · 发现，选举产生PL(prospective leader)，PL收集Follower epoch(cepoch)，根据Follower的反馈，PL产生newepoch(每次选举产生新Leader的同时产生新epoch)。
    · 同步，PL补齐相比Follower多数派缺失的状态、之后各Follower再补齐相比PL缺失的状态，PL和Follower完成状态同步后PL变为正式Leader(established leader)。
    · 广播，Leader处理客户端的写操作，并将状态变更广播至Follower，Follower多数派通过之后Leader发起将状态变更落地(deliver/commit)。
    在正常运行过程中，ZAB协议会一直运行于阶段三来反复进行消息广播流程，如果出现崩溃或其他原因导致Leader缺失，那么此时ZAB协议会再次进入发现阶段，选举新的Leader。
    2.4.1 运行分析
    每个进程都有可能处于如下三种状态之一
    · LOOKING：Leader选举阶段。
    · FOLLOWING：Follower服务器和Leader服务器保持同步状态。
    · LEADING：Leader服务器作为主进程领导状态。
    所有进程初始状态都是LOOKING状态，此时不存在Leader，此时，进程会试图选举出一个新的Leader，之后，如果进程发现已经选举出新的Leader了，那么它就会切换到FOLLOWING状态，并开始和Leader保持同步，处于FOLLOWING状态的进程称为Follower，LEADING状态的进程称为Leader，当Leader崩溃或放弃领导地位时，其余的Follower进程就会转换到LOOKING状态开始新一轮的Leader选举。
    一个Follower只能和一个Leader保持同步，Leader进程和所有与所有的Follower进程之间都通过心跳检测机制来感知彼此的情况。若Leader能够在超时时间内正常收到心跳检测，那么Follower就会一直与该Leader保持连接，而如果在指定时间内Leader无法从过半的Follower进程那里接收到心跳检测，或者TCP连接断开，那么Leader会放弃当前周期的领导，比你转换到LOOKING状态，其他的Follower也会选择放弃这个Leader，同时转换到LOOKING状态，之后会进行新一轮的Leader选举，并在选举产生新的Leader之后开始新的一轮主进程周期。
    2.5 ZAB与Paxos的联系和区别
    联系：
  2. 都存在一个类似于Leader进程的角色，由其负责协调多个Follower进程的运行。
  3. Leader进程都会等待超过半数的Follower做出正确的反馈后，才会将一个提议进行提交。
  4. 在ZAB协议中，每个Proposal中都包含了一个epoch值，用来代表当前的Leader周期，在Paxos算法中，同样存在这样的一个标识，名字为Ballot。
    区别：
    Paxos算法中，新选举产生的主进程会进行两个阶段的工作，第一阶段称为读阶段，新的主进程和其他进程通信来收集主进程提出的提议，并将它们提交。第二阶段称为写阶段，当前主进程开始提出自己的提议。
    ZAB协议在Paxos基础上添加了同步阶段，此时，新的Leader会确保存在过半的Follower已经提交了之前的Leader周期中的所有事务Proposal。
    ZAB协议主要用于构建一个高可用的分布式数据主备系统，而Paxos算法则用于构建一个分布式的一致性状态机系统。

Zab 如何保证强一致

Zab 通过约束事务先后顺序达到强一致性，先广播的事务先 commit、FIFO，Zab 称之为**primary order(以下简称 PO)**。实现 PO 的核心是zxid。
Zab 中每个事务对应一个 zxid，它由两部分组成：<e, c>，e 即 Leader 选举时生成的 epoch，c 表示当次 epoch 内事务的编号、依次递增。假设有两个事务的 zxid 分别是 z、z’，当满足 z.e < z'.e 或者 z.e = z'.e && z.c < z'.c 时，定义 z 先于 z’发生(z < z')。
为实现 PO，Zab 对 Follower、Leader 有以下约束：

  1. 有事务 z 和 z’，如果 Leader 先广播 z，则 Follower 需保证先 commit z 对应的事务
  2. 有事务 z 和 z’，z 由 Leader p 广播，z’由 Leader q 广播，Leader p 先于 Leader q，则 Follower 需保证先 commit z 对应的事务
  3. 有事务 z 和 z’，z 由 Leader p 广播，z’由 Leader q 广播，Leader p 先于 Leader q，如果 Follower 已经 commit z，则 q 需保证已 commit z 才能广播 z’

第 1、2 点保证事务 FIFO，第 3 点保证 Leader 上具备所有已 commit 的事务。
相比 Paxos，Zab 约束了事务顺序、适用于有强一致性需求的场景。

Paxos、Raft、Zab 比较

除 Paxos、Raft 和 Zab 外，Viewstamped Replication(简称 VR)也是讨论比较多的一致性协议。这些协议包含很多共同的内容(Leader、quorum、state machine 等)，因而我们不禁要问：Paxos、Raft、Zab 和 VR 等分布式一致性协议区别到底在哪，还是根本就是一回事？
Paxos、Raft、Zab 和 VR 都是解决一致性问题的协议，Paxos 协议原文倾向于理论，Raft、Zab、VR 倾向于实践，一致性保证程度等的不同也导致这些协议间存在差异。下图帮助我们理解这些协议的相似点和区别
Paxos、Raft、Zab比较

参考

Paxos

  1. 分布式系统理论进阶 - Paxos
  2. Paxos Made Simple
  3. The Part-Time Parliament
  4. Tencent/phxpaxos

Raft

  1. [1] Paxos made live - An engineering perspective, Tushar Chandra, Robert Griesemer and Joshua Redstone, 2007
  2. [2] In Search of an Understandable Consensus Algorithm, Diego Ongaro and John Ousterhout, 2013
  3. [3] In Search of an Understandable Consensus Algorithm (Extended Version), Diego Ongaro and John Ousterhout, 2013
  4. [4] Implementing Fault-Tolerant Services Using the State Machine, Fred B. Schneider, 1990

Zab

  1. [5] Zab:High-performance broadcast for primary-backup systems, FlavioP.Junqueira,BenjaminC.Reed,andMarcoSerafini, 2011
  2. [6] ZooKeeper’s atomic broadcast protocol: Theory and practice, Andr´e Medeiros, 2012
  3. [7] Viewstamped Replication A New Primary Copy Method to Support Highly-Available Distributed Systems, Brian M.Oki and Barbar H.Liskov, 1988
  4. [8] Viewstamped Replication Revisited, Barbara Liskov and James Cowling, Barbara Liskov and James Cowling ,2012
  5. [9] Can’t we all just agree? The morning paper, 2015
  6. [10] Vive La Difference: Paxos vs. Viewstamped Replication vs. Zab, Robbert van Renesse, Nicolas Schiper and Fred B. Schneider, 2014

Paxos 变种和优化

  1. [1] Mencius: Building Efficient Replicated State Machines for WANs, Yanhua Mao,Flavio P. Junqueira,Keith Marzullo, 2018
  2. [2] Fast Paxos, Leslie Lamport, 2005
  3. [3] Generalized Consensus and Paxos, Leslie Lamport, 2004
  4. [4] There Is More Consensus in Egalitarian Parliaments, Iulian Moraru, David G. Andersen, Michael Kaminsky, 2013

发表于 更新于 分类于

RocketMQ 启动流程中的服务注册

RocketMQ 的消息队列集群结构主要包含 NameServer、Broker（Master/Slave）、Producer、Consumer 4 个部分，基本通信流程如下：

  1. Broker 启动后需要完成一次将自己注册至 NameServer 的操作；随后每隔 30s 时间定时向 NameServer 上报 Topic 路由信息。
    Broker 启动入口：org.apache.rocketmq.broker.BrokerController#start
    注册到每个 NameServer：org.apache.rocketmq.broker.out.BrokerOuterAPI#registerBrokerAll
  2. 消息生产者 Producer 作为客户端发送消息时候，需要根据消息的 Topic 从本地缓存的 TopicPublishInfoTable 获取路由信息。如果没有则更新路由信息会从 NameServer 上重新拉取，同时 Producer 会默认每隔 30s 向 NameServer 拉取一次路由信息。
  3. 消息生产者 Producer 根据2中获取的路由信息选择一个队列（MessageQueue）进行消息发送；Broker 作为消息的接收者接收消息并落盘存储。
  4. 消息消费者 Consumer 根据2中获取的路由信息，并再完成客户端的负载均衡后，选择其中的某一个或者某几个消息队列来拉取消息并进行消费。

服务发现

Broker

Broker端启动时会向NameServer注册，并开启一个定时任务，用于每隔十秒向所有NameServer发送心跳请求，将Topic信息注册到NameServer。

NameServer

除了Broker可以向NameServer注册服务信息，NameServer也会启动一个定时任务来定时清理不活动的Broker，默认情况下是清除两分钟没有向NameServer发送心跳更新的Broker。
NameServer的结构比较简单，主要类只有6个：

  • NamesrvStartup：程序入口。
  • NamesrvController：NameServer 的总控制器，负责所有服务的生命周期管理。
  • RouteInfoManager：NameServer 最核心的实现类，负责保存和管理集群路由信息。
    topicQueueTable 保存的是主题和队列信息，其中每个队列信息对应的类 QueueData 中，还保存了 brokerName。需要注意的是，这个 brokerName 并不真正是某个 Broker 的物理地址，它对应的一组 Broker 节点，包括一个主节点和若干个从节点。
    brokerAddrTable 中保存了集群中每个 brokerName 对应 Broker 信息，每个 Broker 信息用一个 BrokerData 对象表示。
    brokerLiveTable 中保存了集群中所有活跃的Broker。
    定时每10秒一次扫描并清除不活跃的Broker，代码见：RouteInfoManager#scanNotActiveBroker。
  • BrokerHousekeepingService：监控 Broker 连接状态的代理类。
  • DefaultRequestProcessor：负责处理客户端和 Broker 发送过来的 RPC 请求的处理器。
    先用读写锁保证并发安全，然后比较所有路由信息Map并更新。
  • ClusterTestRequestProcessor：用于测试的请求处理器。

Producer

Producer是只能发给Broker集群里的Master的，如果Master挂掉，那么Producer也不能继续发消息了，只能等集群重新选举出一个新的Master，虽然可用性会降低，但是也给顺序消息的实现提供了方便。

Consumer

定时从NameServer拉取topicRouteTable更新本地的brokerAddrTable，也就是说，只要NameServer会把宕掉的Broker清掉，那么Consumer最终（注意并不能实时）也可以取到拿到一份活跃的Broker列表。
MQClientInstance#updateTopicRouteInfoFromNameServer(final String topic, boolean isDefault, DefaultMQProducer defaultMQProducer)
Consumer端是定时地上Broker拉取消息。
org.apache.rocketmq.common.ServiceThread#start
如果某次消费出错了，就会触发Fallback方案，改为稍后再重试。
org.apache.rocketmq.client.impl.MQClientAPIImpl#pullMessageAsync

0%