sixsixfly

sixsixfly 查看完整档案

广州编辑  |  填写毕业院校  |  填写所在公司/组织填写个人主网站
编辑
_ | |__ _ _ __ _ | '_ \| | | |/ _` | | |_) | |_| | (_| | |_.__/ \__,_|\__, | |___/ 个人简介什么都没有

个人动态

sixsixfly 发布了文章 · 2020-10-29

TCP keepalive 概述(译)

什么是 TCP keepalive

TCP keepalive 概念很简单:当建立一个TCP连接时,会设置了一系列与该连接相关的定时器。其中有些定时器跟处理 keepalive 相关,在 keepalive 定时器倒计时变为零时,会给连接的另一方发送一个 keepalive 探针包(probe packet),包内没有数据且设置了 ACK 标识。

如果收到一个 keepalive 探针包的响应,说明连接是正常和有效的。TCP 可以处理只有协议头,但实际数据长度为零的数据包。这种机制是有用的,假如其他主机断开了连接,你可以及时注意到连接的断开。

如果 keepalive 探针没有响应,那么可以认为连接不是有效的,进而可以采取正确的操作。

TCP keepalive 的应用场景

KeepAlive 是非侵入性的,大多数情况下开启 keepalive 不会有其他风险。需要注意的是,这样做会带来额外的网络开销,例如会影响到路由器和防火墙。

  • 检测实际断掉的连接
  • 维持客户端与 NAT 间的活跃网络包

检测实际断掉的连接

设想 A、B 两端建有 TCP 连接:最开始是三次握手,A 发送 SYN 报文段给 B,B 响应 SYN/ACK 给 A,最后 A 发送 ACK 给 B。现在两端处于 established 状态,都在等待对方发送数据。如果此时 B 电源被拔掉,在没有发送任何数据的通知 A 的情况下,B 已经断开了连接。A 已经做好了准备接收数据,但不知道 B 已经宕机。之后 B 恢复供电并且系统重启,A 以为跟 B 的连接还是正常的。此时 A 试图给 B 发送数据,B 会回复 RST 包,这样 A 才关闭这个连接。

Keepalive 机制可以让 A 端避免出现上述的情况。实际上,如果连接双方有网络问题,keepalive 通过定时发送 keepalive 已经及时感知到连接断开。

    _____                                                     _____
   |     |                                                   |     |
   |  A  |                                                   |  B  |
   |_____|                                                   |_____|
      ^                                                         ^
      |--->--->--->-------------- SYN -------------->--->--->---|
      |---<---<---<------------ SYN/ACK ------------<---<---<---|
      |--->--->--->-------------- ACK -------------->--->--->---|
      |                                                         |
      |                                       system crash ---> X
      |
      |                                     system restart ---> ^
      |                                                         |
      |--->--->--->-------------- PSH -------------->--->--->---|
      |---<---<---<-------------- RST --------------<---<---<---|
      |                                                         |

维持客户端与 NAT 间的活跃网络包

keepalive 另一个用途是阻止因网络连接不活跃(长时间没有数据包)而导致的连接断开。

很多网络设备,尤其是NAT路由器,由于其硬件的限制(例如内存、CPU处理能力),无法保持其上的所有连接,因此在必要的时候会在连接池中选择一些不活跃的连接踢掉。典型做法是LRU,把最久没有数据的连接给踢掉。通过使用 TCP KeepAlive 机制,可以让连接每隔一小段时间就产生一些 ACK 包,以降低被踢掉的风险,当然,这样的代价是额外的网络和 CPU 负担。

    _____           _____                                     _____
   |     |         |     |                                   |     |
   |  A  |         | NAT |                                   |  B  |
   |_____|         |_____|                                   |_____|
      ^               ^                                         ^
      |--->--->--->---|----------- SYN ------------->--->--->---|
      |---<---<---<---|--------- SYN/ACK -----------<---<---<---|
      |--->--->--->---|----------- ACK ------------->--->--->---|
      |               |                                         |
      |               | <--- connection deleted from table      |
      |               |                                         |
      |--->- PSH ->---| <--- invalid connection                 |
      |               |                                         |

Linux 系统中的 keepalive

Linux 中跟 keepalive 相关的三个参数:

  • tcp_keepalive_time
  • tcp_keepalive_intvl
  • tcp_keepalive_probes

tcp_keepalive_time
发送最后一个数据包(只包含 ACK 的包不认为是数据包)和发送第一个 probe 包之间间隔的时间

tcp_keepalive_intvl
发送两个 keepalive probe 包之间间隔多长

tcp_keepalive_probes
连续发几个 probe 包不回复才认为连接断了

默认值

# cat /proc/sys/net/ipv4/tcp_keepalive_time
7200

# cat /proc/sys/net/ipv4/tcp_keepalive_intvl
75

# cat /proc/sys/net/ipv4/tcp_keepalive_probes
9

HTTP Keep-Alive是什么?如何工作?
TCP-Keepalive

查看原文

赞 0 收藏 0 评论 0

sixsixfly 发布了文章 · 2020-10-19

Login 和 Non-Login Shell 的区别(译)

Shell 是 Linux 用来将用户输入的指令发送给内核的接口,并将内核执行指令后的结果返回输出。

这里使用 Bash shell 作为示例,shell 可以分成两类:Login Shell 和 Non Login Shell,两种类型分别执行不同的脚本来配置 shell 执行环境。

Login Shell

用户成功登陆后使用的是 Login shell。例如,当你通过终端、SSH 或使用 “su -” 命令来切换账号时都会使用 Login Shell。

Login shell 运行一系列的前置脚本来配置 shell 环境,运行如下命令可识别是否是 login shell。

$ echo $0

如果执行命令的结果类似 "-bash" 或 “-su”,那么你当前处于 login shell(确认有 “-” 前缀符号)

Login Shell 会执行如下的前置脚本:

  • 执行文件 /etc/profile
  • 执行 /etc/profile.d/ 目录下所有脚本
  • 执行用户所属 ~/.bash_profile
  • 执行 ~/.bashrc
  • ~/.bashrc 执行文件 /etc/bashrc

Non Login Shell

Non Login Shell 是指通过 login shell 开启的 shell。例如,通过 shell 开启了一个新 shell 或者通过程序开启一个新 shell。

Non login shell 执行如下脚本来初始 shell 环境:

  • 先执行 ~/.bashrc
  • ~/.bashrc 会执行 /etc/bashrc
  • /etc/bashrc 会调用 /etc/profile.d 中脚本

判断当前是 Login 还是 Non Login Shell

为了判断当前 shell 是 login 还是 nonlogin shell,可以简单的执行如下命令:

$ echo $0

Login shell 输出的结果类似 -bash-su.

Non logins shell 输出的结果类似 bashsu

image.png

查看原文

赞 1 收藏 1 评论 0

sixsixfly 发布了文章 · 2020-10-12

HTTP/2 协议常见疑问(译)

为什么修订 HTTP 协议

HTTP/1.1 应用于 Web 已有15年的历史,协议的缺陷和不足开始显现。

对比过去,现在的 web 页面需要加载更多资源,HTTP1.x 协议规定一个 TCP connection 不能并行发起多个 request 请求,这使得页面在快速加载大量资源时变得困难。

为处理上述问题,HTTP1.1 协议允许浏览器使用多个 TCP connection 来并行发起多个 request 请求。这种处理方式存在缺陷,使用太多的 connection 会适得其反(TCP 拥塞控制会导致网络效率低下),同时也会出现不公平现象(浏览器都设法占用超出它本该分配的网络资源)。

HTTP/2 跟 SPDY 有什么关系

在 SPDY 协议被 Mozilla 和 nginx 等厂商实现后,相对于 HTTP/1.x 展现出了明显的性能提升,这时 HTTP/2 协议的讨论和指定开始提上议程。

经过一轮提议和投票,最被选择了 SPDY/2 作为 HTTP/2 协议的基础。此后,在工作组和实现者的讨论下 HTTP/2 协议又做出了一系列变更。在这个过程中,SPDY 协议的核心开发者参与了 HTTP/2 协议的开发,这其中包括 Mike Belshe 和 Roberto Peon。

2015年9月,Google 宣布为了支持 HTTP/2 协议,将来不再支持 SPDY 协议。

HTTP/2 跟 HTTP/1.x 的区别

总体来说区别有以下几点:

  • 使用二进制来代替文本格式
  • 使用多路复用来代替有序和阻塞
  • 使用一个 connection 来处理并行请求
  • 使用 header 压缩来减小 header 大小
  • 允许服务端使用 push 来预先推送客户端需要的 cache

为什么 HTTP/2 是二进制的

二进制协议解析效率更高,更节省网络资源,相对于 HTTP/1.1 协议使用文本格式的空格或空行来解析数据,二进制协议更不容易出错

例如, HTTP/1.1 定义了四种不同解析消息的方式,HTTP/2 只有一种解析方式

虽然 HTTP/2 不能通过 telnet 来使用,但是可以使用 Wireshark 等工具

为什么 HTTP/2 是多路复用

HTTP/1.x 存在所谓的“头部阻塞”问题,也就是每个 TCP connection 只能同时发起一个 request 请求。

HTTP/1.1 尝试使用 pipelining 来解决这个问题,这没有完全陈述清楚该问题(一个大的或者慢的响应会阻塞这之后的其他请求)。同时 pipelining 被证明很难部署,因为许多中间件和服务器不能正确的处理它。

这使得客户只能通过猜测确定与站点的哪个连接发起请求,使用实际可用连接数的10倍来加载页面是很常见的,这会严重影响性能,通常会导致请求阻塞。

多路复用允许多个请求和响应的 message 在一个 TCP 连接上并行处理来解决这个问题,甚至可以让不同 message 的内容同时混合在一起处理,也就是客户端可以使用单个 TCP connection 来加载完整的页面

为什么只有一个 TCP connection

使用 HTTP/1,浏览器可以在每个域名上打开四个到八个连接。很多网站同时使用多个子域,这样加载单个页面会打开多达30个 TCP 连接。

一个应用并发使用太多的连接打破了构建 TCP 协议的基础设计,每个连接会响应大量数据让网络的缓冲区溢出,从而触发 TCP 的拥塞控制和 TCP 重传机制

查看原文

赞 0 收藏 0 评论 0

sixsixfly 发布了文章 · 2020-10-09

A 类,B 类和 C 类网络地址(译)

A类 B类 和 C 类

IP 地址由管理网络的 InterNIC 组织分配 (http://www.internic.net )
IP 地址分成不同的类别,常见的有 A 类,B 类 和 C 类 IP 地址,D 类和 E 类地址通常不被使用
每种网络地址有对应的默认的子网掩码,查看 IP 地址的前八个 bit 可以快速识别出网络地址类型

A 类地址使用 255.0.0.0 作为默认子网掩码,前八个二进制位取值范围是 [1,126],
例如 10.52.36.11 是个 A 类地址,它的前八位是 10,在 [1,126] 范围内

B 类地址使用 255.255.0.0 作为默认子网掩码,前八个二进制位取值范围是 [128,191],
例如 172.16.52.63 是个 B 类地址,它的前八位 172,属于 [128,191] 范围。

C 类地址使用 255.255.255.0 作为默认子网掩码,前面八个二进制位取值范围是 [192,223],
例如 192.168.123.132 是一个 C 类地址,前八位归属于 [192,223] 范围

Class A Network (/ 8 Prefixes)

IPv4 地址由32个二进制位组成,A 类地址前面八位属于网络地址,第一个 bit 被设置为$\color{red}{0}$,后面 24 bit 属于主机地址,排除所有 bit 是 0 和 1 的地址后(0.0.0.0, 255.255.255.255 用于广播),A 类地址可以用来划分 126($2^7$ - 2 = 126)个网络,每个网络最大支持 16,777,214 ($2^{24}$ - 2) 台主机。

A 类地址总共包含 $2^{31}$ (2,147,483,648) 个独立的地址,而 IPv4 总共包含 $2^{32}$ (4,294,967,296) 个地址,所以 A 类地址占总地址数量的 50%。

Class B Networks (/16 Prefixes)

B 类地址前 16 bit 属于网络地址,前面 2 bit 被设置为 $\color{red}{10}$,它由 14 bit 网络地址和 16 bit 主机地址组成。

B 类地址可以划分 16,384 ($2^{14}$)/16 个子网络,每个子网络地址最大支持 65,534 ($2^{16}$ - 2) 台主机,B 类地址总共有 (1,073,741,824) = $2^{30}$ 个地址,占 IPv4 地址总数的 25%。

Class C Networks (/24 Prefixes)

C 类地址前面 24 bit 属于网络地址,前面 3 bit 被设置为$\color{red}{110}$,C 类地址由 21 bit 的网络地址和 8 bit 主机地址构成。

C 类地址可以划分 2,097,152 ($2^{21}$) 个子网络,每个子网络最大支持 254 ($2^8$ - 2) 台主机,B 类地址共有 $2^{29}$ (536,870,912) 个地址,占 IPv4 地址总数的 12.5%。

Host Capacities

地址类型网络位/主机位标志位识别网络类型位数可用网络位数子网络数子网主机数
Class A8 / 240xxx xxxx18-1 = 7$2^7$-2 = 126$2^{24}$-2 = 16,277,214
Class B16 / 1610xx xxxx216-2 = 14$2^{14}$ = 16,384$2^{16}$-2 = 65,534
Class C24 / 8110x xxxx324-3 = 21$2^{21}$ = 2,097,152$2^8$-2 = 254

私有地址

每种类型的网络有一部保留地址用来作为私有地址或内部地址,这些地址不能用于外网,因为他们不可路由。在家里或者办公室网络中,可以把打印机或者文件服务器设置为私有 IP 地址。

A 类私有地址范围:10.0.0.0 到 10.255.255.255

B 类私有 APIPA 地址范围:169.254.0.0 到 169.254.255.255
B 类私有地址范围:172.16.0.0 到 171.31.255.255

C 类私有地址范围:192.168.0.0 到 192.168.255.255

Automatic Private IP Addressing (APIPA) 是微软 windows 系列计算机上当 DHCP 服务不可用时用来自动设置 IP 地址的机制

特殊地址

地址范围:127.0.0.1 到 127.255.255.255 属于网络测试地址,也称为 loop-back 回环地址

参考资料

The Five IPv4 Classes - Quick Reference

A B and C Classes of Networks

查看原文

赞 0 收藏 0 评论 0

sixsixfly 发布了文章 · 2020-09-24

理解 TCP 拥塞控制(译)

TCP Congestion Control

TCP 通过减小发送窗口大小来处理拥塞,发送窗口的大小由以下两个因素共同决定:

  1. 接收窗口大小(Receiver window)
  2. 拥塞窗口大小(Congestion window)

接收窗口大小

接收窗口大小是一种接收端对发送端的告知:用来说明接收者总计能接收多少字节未确认数据

  • 发送端发送的数据量不得大于接收窗口大小,否则会存在 TCP 报文丢失进而导致 TCP 重传(TCP Retransmission)
  • 发送端发送的数据量应小于等于接收窗口大小,发送者通过 TCP 头(TCP Header)得知接收者接收窗口大小

拥塞窗口大小

  • 发送端发送的未确认数据不得大于拥塞窗口大小,否则会使得 TCP 报文段丢弃进而导致 TCP 重传
  • 发送者发送的未确认数据应小于等于拥塞窗口大小,拥塞窗口的概念只存在于发送端

发送窗口的大小取接收窗口和拥塞窗口的最小值

Sender window size = Minimum (Receiver window size, Congestion window size)

TCP 应对拥塞的策略

TCP 应对拥塞的策略由三阶段组成:慢启动(Slow Start),拥塞避免(Congestion Avoidance)和拥塞探知(Congestion Detection)

image.png

慢启动阶段

一开始发送端设置拥塞窗口等于一个最大报文段(1 MSS)。在接收到确认 ACK 后,发送端把拥塞窗口增加 1 MSS,整个过程中拥塞窗口按照预设规则增大(指数级)

Congestion window size = Congestion window size + Maximum segment size

image.png

一轮 ACK 过后,拥塞窗口 = $(2)^1$ = 2 MSS
二轮 ACK 过后,拥塞窗口 = $(2)^2$ = 4 MSS
三轮 ACK 过后,拥塞窗口 = $(2)^3$ = 8 MSS
......

整个过程一直持续,直到拥塞窗口大小达到慢启动阈值(slow start threshold)

Threshold = Maximum number of TCP segments that receiver window can accommodate / 2
= (Receiver window size / Maximum Segment Size) / 2

拥塞避免阶段

拥塞窗口达到阈值后,为避免拥塞发送端改为线性的增加拥塞窗口大小
接收到每个 ACK 后,发送端只对拥塞窗口增加 1 MSS

Congestion window size = Congestion window size + 1

整个过程一直持续,直到拥塞窗口大小增大到接收窗口大小
image.png

拥塞感知阶段

发送端检测到报文丢失时,根据不同方式感知到的报文丢失会采取不同的策略来处理

方式一:通过超时感知拥塞(Time Out)
接收者经历超时时间后却没收到报文确认 ACK,说明有大概率存在网络拥塞,这时报文段可能已经丢失

发送端的应对策略:

  • 设置慢启动阈值为当前拥塞窗口大小的一半
  • 设置拥塞窗口大小为 1 MSS
  • 恢复到慢启动阶段

方式二:收到三个重复 ACK 感知拥塞
发送端接收到三个重复的 ACK 说明存在小概率网络拥塞,
虽然报文存在丢失的可能,但接下来发送的报文应该可以顺利到达

发送端的应对策略:

  • 设置慢启动阈值为当前拥塞窗口大小的一半
  • 拥塞窗口减小到慢启动阈值
  • 恢复到拥塞避免阶段
查看原文

赞 0 收藏 0 评论 0

sixsixfly 发布了文章 · 2020-09-18

RSA 非对称加密和 DH 密钥交换(译)

Diffie-Hellman 密钥交换(Key Exchange)

问题:

通信双方使用一个对称加密的密钥进行通信,这时不能让通信双方之外任何人知道此对称加密的密钥,也就是密钥不能公开出来。

特点:

密钥不通过网络传输,可以在通信双方各自生成一致的密钥

解决方案/步骤:

  1. 通信双方各自挑选一个数字并各自保密(设为 x 和 y)
  2. 通信双方约定两个对外公开的质数(设为 g 和 n)
  3. 一方计算 $g^x$ mod n = A,另一方计算 $g^y$ mod n = B,相互告知 A 和 B
  4. 一方计算 $B^x$ mod n,另一方计算 $A^y$ mod n(双方计算结果相等)

举例:

  1. x = 4, y = 3
  2. g = 5, n = 23
  3. A = $g^x$ mod n = $5^4$ mod 23 = 4,B = $g^y$ mod n = $5^3$ mod 23 = 10
  4. $B^x$ mod n = $10^4$ mod 23 = 18,$A^y$ mod n = $4^3$ mod 23 = 18
  5. 18 即是双方共享的密钥

RSA 非对称加密(Asymmetric Encryption)

问题:

与我通信的任何一方都可以对信息进行加密,唯独我可以解密信息内容,我不与任何人共享解密密钥。

解决方案/步骤:

  1. 选择两个不相等的质数 p 和 q
  2. 计算 p 和 q 的乘积 n
  3. 计算 n 的欧拉函数 φ(n) = (p-1)(q-1) = t
  4. 随机选择一个整数 e,条件是 1< e < t,且 e 与 t 互质
  5. 计算 e 对于 t 的模反元素 d(存在一到多个整数 d,使得 ed-1 被 t 整除)
  6. 将 (e, n) 封装为公钥,(d, n) 封装为私钥
  7. 原始信息 m 加密后 c = $m^e$ mod n,通过 c 计算原始信息 m = $c^d$ mod n

举例:

  1. p = 11,q = 13
  2. n = p$\times$q = 11$\times$13 = 143
  3. t = (p-1)(q-1) = (11-1)*(13-1) = 120
  4. e 随机选择 7
  5. d = 103 (ed - 1 = 720 可以被 120 整除)
  6. 公钥 (e, n)=(7, 143),私钥 (d, n)=(103, 143)
  7. $m^e$ mod n = $9^{7}$ mod 143 = 48 = c,$c^d$ mod n = $48^{103}$ mod 143 = 9 = m

RSA算法原理(一)
RSA算法原理(二)
How RSA Works With Examples

查看原文

赞 0 收藏 0 评论 0

sixsixfly 发布了文章 · 2020-09-08

理解分布式共识算法

从 RocketMQ 支持自动故障转移说起


在 RocketMQ 4.5 版本之前,RocketMQ 只有 Master/Slave 一种部署方式,一组 Broker 中有一个 Master,有零到多个 Slave,Slave 通过同步复制或异步复制方式去同步 Master 的数据。Master/Slave 部署模式,提供了一定的高可用性。
但这样的部署模式有一定缺陷。比如故障转移方面,如果主节点挂了还需要人为手动的进行重启或者切换,无法自动将一个从节点转换为主节点。因此,我们希望能有一个新的多副本架构,去解决这个问题。

RocketMQ 实现高可用多副本架构的关键:基于 Raft 协议的 commitlog 存储库 DLedger
Apache RocketMQ - Version 4.5.0 基于 Raft 协议实现高可用多副本架构

master broker 宕机后失去写消息能力

由于 master broker 同时支持读写,slave broker 只支持读,甚至只有 brokerId = 1 的 broker 才支持消息的读负载(rocketmq 根据 brokerId 来确定主从,brokerId = 0 表示 master,brokerId 非 0 表示 slave)

我们商城现在使用的是 RocketMQ 3.2.6 版本,两个节点(broker a 和 broker c)每个 broker 一主一从

除了一主一从,RocketMQ 中的 broker 还支持其他多种部署方式:

  • 单 master 单 slave
  • 单 master 多 slave 同步复制
  • 单 master 多 slave 异步复制
  • 多 master 零 slave

kafka 领导者选举

作为对比我们来看看 Kafka 是怎么做的(淘宝中间件团队在对 Kafka 做过充分 Review 之后用 Java 实现了 RocketMQ)。Kafka 中的副本分为追随者副本(Follower Replica)和领导者副本(Leader Replica),追随者副本不对外提供服务,仅用来备份数据(不提供读,也不提供写)优点是不存在从节点消息延迟的情况,缺点是失去了读操作的横向扩展

Kafka Leader 选举大致思路如下:

Leader 在 zookeeper 上创建一个临时节点,所有 Follower 对此节点注册监听,当 Leader 宕机时 ISR 里的所有 Follower 都尝试创建该节点,而创建成功者(Zookeeper 保证只有一个能创建成功)即是新的Leader,其它 Replica 即为Follower

RocketMQ 最佳实践
RocketMQ architecture
RocketMQ 的相关概念

那什么是 Raft 协议

事情一开始是这样的,有个叫 Lamport 的提出一种分布式共识算法(命名 paxos,一个希腊岛屿,古希腊城邦流行民主选举),由于这个算法原本不好理解,加上表述又不够简洁(但并不妨碍人家拿图灵奖,1990 年提出相关算法,后来被互联网公司应用到许多项目中,2013 年获得图灵奖)
最后有人在 2014 年提出了 一种 raft 协议用来替代 paxos 算法并做了简化或者说是优化,raft 协议共有三种角色:

  • 领导者(leader)
  • 追随者(follower)
  • 和候选人(candidate)

raft 协议将问题拆分为数个子问题来解决:

  • 领导者选举(leader election)
  • 日志复制(log replication)
  • 安全规则(safty)

领导者选举

  • 在算法初始化阶段或者当现有的领导者宕机/失联时,follower 将以新的任期编号(term)发起一轮领导者选举。
  • 如果一轮选举成功则新的领导者开始工作,反之则视此选举结束,下一轮选举将使用一个新的任期编号。
  • 当追随者节点接收领导者心跳超时后会选择自己作为候选人发起一轮新的选举。候选人先为自己投一票然后向其他服务器发起投票请求。
  • 每个节点在每个任期编号内只允许一次投票,并且遵循先到先服务原则。
  • 如果有候选人收到过半的选票就当选为新的领导者,如果超时仍没有选出新领袖则此任期自动终止,将使用新的任期编号开始下一轮选举。

注意:如果候选人(A)在选举过程中有收到其他节点(B)的心跳消息,且心跳包含的任期编号不小于 A 的任期编号,那么 A 会立即恢复为追随者状态,并认定 B 为领导者。

两个随机时间
Raft 使用了两个随机时间来简化 split vote 问题,可以降低多服务同时竞选的几率,也降低了两个竞选人得票都不过半而选举失败的几率

  • 每个 follower 等待 leader 发送心跳的超时时间是随机的(150 ms -> 300 ms)
  • 两个 candidate 同时选举并获得了相同的票数,这时 candidate 将随机推迟一段时间后再向其他节点重新发出投票请求

Raft 协议特点:

  • 系统只存在一个 Leader 角色,接受 Clients 发过来的所有读写请求
  • Leader 负责与所有的 Followers 通信,将提案/Value/变更复制到所有 Followers,同时收集多数派 Followers 的应答
  • 少数派宕机,不会影响系统整体的可用性
  • Leader 日常维护与所有 Followers 的心跳
  • Leader 宕机,会触发系统自动重新选主,选主期间系统对外不可服务

日志复制

领导者接收到客户端的请求(包含一个执行的命令)后负责复制日志。领导者收到请求后创建一个新日志项,并附加到本地日志中,然后将新的日志项复制到其他追随者节点。如果追随者节点不可用,则领导者会无限期地重试发送添加日志项消息,直到所有追随者最终接收并存储为止。

当领导者从多数追随者那收到该日志项已被复制的确认消息后,领导者会将该日志项在本地提交。接下来领导者向追随者发送日志项提交消息,通知追随者将日志项应用于其本地状态机。这样也就完成了集群服务器间的日志一致性。

在领导者崩溃的情况下日志可能会不一致,也就是旧领导者的某些日志没在集群中完全复制。新领导者通过强制追随者复制自己的日志来处理不一致问题。大致过程是领导者将每个追随者的日志与自己的日志进行比较,找到跟随者节点上与自己日志相同的最大日志项,然后删除追随者日志中此关键日志项之后的所有日志(此前的日志是完全一致的了)。通过这种机制来恢复故障集群的日志一致性。

看动画理解 Raft 算法

演示动画
动画演示中文翻译
斯坦福 Raft lecture


相关算法的工程实践

项目算法时间
mongodbbully -> raft2007 - 2009 开源
zookeeperzab(multi-paxos)Yahoo 2008
chubbypaxosGoogle
mysql 5.7 group replicationpaxos2013 - 2015
rocketmqnull -> raft2012 年开源
kafkazookeeper -> raftLinked 2011 年开源
etcdraftCoreOS 2018 年 CNCF

大致技术的趋势是:master/slave -> raft,paxos -> raft

使用 Raft 协议的中间件
Kafka 在讨论用 Raft 算法替换 zookeeper
MySQL 5.7 Group Replication Background
RocketMQ Add store with dledger

有 raft 之前先有 paxos

Paxos是一种算法,用于在通过异步网络进行通信的一组分布式计算机之间达成共识。一个或多个客户端向 Paxos 提出了一个提议值,当大多数运行 Paxos 的系统都同意其中一个提议值时,将达成共识。Paxos 被广泛使用并且在计算机科学领域具有传奇色彩,因为它是第一个被严格证明是正确的共识算法。

Paxos 只需从提议的一个或多个值中选择一个值,然后让所有人知道该值是什么。如果需要使用 Paxos 创建复制日志(例如,复制状态机),则需要重复运行 Paxos。这称为 multi-Paxos。对于多 multi-Paxos,可以实现一些优化,但是这里不再讨论。

相关角色

Paxos 有三个角色:

  1. 提议者:接收来自客户的请求(值),并尝试说服接受者接受其提议的值。
  2. 接受者:接受提议者的某些提议值,并让提议者知道之前是否接受了其他提议。接受者的回复表示对特定提案的投票。
  3. 学习者:保存备份达成共识的投票结果。

Basic Paxos 协议

该协议是 Paxos 系列中最基础的协议,Basic Paxos 协议成功达成共识后会得到一个提议值。如果一轮协商不成功,通常会进行了几轮协商,一轮成功协商的过程有两个阶段:阶段1(分为 ab )和阶段2(分为 ab )。

image.png

第一阶段
阶段 1a: 准备(prepare)

一个提议者创建了一个消息,我们称之为“准备”,用数字 n 标识。请注意, n 不是要提议的值或要商定的值,而只是一个数字,该数字由提议者唯一标识此初始消息(发送给接受者)。数字 n 必须大于此提议者在先前的任何 Prepare 消息中使用过的数字。然后,它发送包含消息 nPrepare 消息给接受者。请注意, Prepare 消息仅包含数字 n (也就是说,它不必包含建议值,通常用 v 表示)。如果提议者不能与任意一个接受者进行通信,则他不应启动 Paxos 协商流程。

阶段 1b: 承诺(promise)

任何 接受者 在等待来自任何 提议者prepare 消息时,如果接受方收到一条 prepare 消息,则接受方必须查看刚刚收到的 prepare 消息的提案编号 n ,此时有两种情况。

如果 n 大于接受者此前从任意提议者处接收到的提案编号,则接受者必须向提议者返回一条消息,我们称其为“承诺”,以忽略将来所有的提案编号小于 n 的提议请求。如果接受者过去某个时候 accepted 了提案,则它必须在对提案者的响应中附带上先前的提案编号(例如 m )和相应的接受值(例如 w )。

否则(即: n小于或等于接受者收到过的先前提议编号),接受者可以忽略收到的提议。在这种情况下,接受者可以不响应提议者的请求。但是,为了优化起见,发送一个拒绝( Nack )响应将告诉提议者它可以停止使用提案编号 n 来尝试建立提议共识了。

第二阶段
阶段 2a: 提议/接受(propose/accept)

如果提议者从接受者中获得了大部分承诺,则需要为其提案设置提案值 v 。如果接受者先前已接受过提案值,那么他们会将其值发送给提议者,该提议者现在必须将其提案值 v 设置为与接受者响应的最高提案编号相关联的值,我们称之为 z 。如果到目前为止,没有一个接受者 accepted 过提案值,则提议者可以选择任意提案值(例如 x )。

提议者将 accept 消息 [n,v] 发送给接受者,提案编号为 n (与先前发送给提议者的 prepare 消息中包含的编号相同),提案值为 vv = z 或者 v = x )。

accept 消息应解释为“请求”,类似于“请接受此提议!”。

阶段 2b: 已接受(accepted)

如果一个接受者接收到 accept 消息 [n,v] ,那么只要 n 大于等于接受者已承诺过(在的协议的 1b 阶段)的最大提案编号 maxN,就必须接受这个提议

如果接受者尚未承诺过(在1b 阶段中)提案编号大于 n 提议,则应将刚收到的 accept 消息的值 v 登记为的接受的提案值,并作为已通过的提案值发送给提议者和每个学习者。

否则,它可以忽略这条 accept 消息或请求。

请注意,接受者可以接受多个提议。例如,当一个新的提议者不知道正在协商的原有提案值,以较大的提案编号 n 开始新的一轮提议时,即使接受者之前已接受了一个提案值,它也可以承诺并稍后接受新的提案值。存在某些故障的情况下,这些提议甚至可能具有不同的提案值。但是,Paxos 协议将保证接受者最终会就单个值达成一致。

talk is cheap show me the code

阶段1a:提案人(prepare)

提议者启动 prepare 消息,选择一个唯一的,不断增加的值。

ID 等同于上文的 n,Value 等同于上文的 v
ID = cnt++;
send PREPARE(ID) 
阶段1b:接受者(promoise)

接受者收到 prepare[n, ] 消息:

    if (ID <= max_id)
        do not respond (or respond with a "fail" message)
    else
        max_id = ID     // save highest ID we've seen so far
        if (proposal_accepted == true) // was a proposal already accepted?
            respond: PROMISE(ID, accepted_ID, accepted_VALUE)
        else
            respond: PROMISE(ID) 
第2a阶段:提案人(propose)

现在,提议者检查是否可以使用其提议,或者是否必须使用从所有响应中收到的编号最高的提议:

did I receive PROMISE responses from a majority of acceptors?
if yes
    do any responses contain accepted values (from other proposals)?
    if yes
        val = accepted_VALUE //value in PROMISE with the highest acceptedID
    if no
        val = VALUE     // we can use our proposed value
    send PROPOSE(ID, val) to at least a majority of acceptors 
阶段2b:接受者(accepted)

每个接受者都从提议者接收一条PROPOSE(ID,VALUE)消息。如果 ID 是已处理的最大提案编号,则接受该提议并将该值传播给提议者和所有学习者。

if (ID == max_id) // is the ID the largest I have seen so far?
    proposal_accepted = true     // note that we accepted a proposal
    accepted_ID = ID             // save the accepted proposal number
    accepted_VALUE = VALUE       // save the accepted proposal data
    respond: ACCEPTED(ID, VALUE) to the proposer and all learners
else
    do not respond (or respond with a "fail" message) 

如果大多数接受者接受提议,则可以达成共识。注意:达成共识的是提案值 value,而不是提案 ID。

Understanding Paxos

看视频学习 paxos
斯坦福 Paxos lecture
视频部分截图的中文翻译

可以通过下图来帮助理解
image.png
图解分布式一致性协议Paxos

查看原文

赞 0 收藏 0 评论 0

sixsixfly 发布了文章 · 2020-05-16

应用频繁 FullGC 该怎么办

内存溢出与内存泄漏

  • 堆内存溢出(OutOfMemoryError: Java heap space)
内存溢出是指程序运行过程中申请的内存大于系统能够提供的内存,导致无法申请到足够的内存,于是就发生了内存溢出

会导致 JVM 内存溢出的一些场景:

  1. JVM 启动参数堆内存值设定的过小
  2. 内存中加载的数据量过于庞大(一次性从 Mysql、Redis 取出过多数据)
  3. 对象的引用没有及时释放,使得JVM不能回收
  4. 代码中存在死循环或循环产生过多重复的对象实体
内存溢出问题一般分为两种,一种是由于大峰值下瞬间创建大量对象而导致的内存溢出;另一种则是由于内存泄漏而导致的内存溢出。第一种问题可通过限流来处理,第二种问题需要分析程序是否存在 Bug

  • 内存泄漏(Memory Leak)
内存泄漏是存在一些被分配的对象,这些对象有下面两个特点,首先,这些对象是可达的,即在有向图中,存在通路可以与其相连;其次,这些对象是无用的,即程序以后不会再使用这些对象。如果对象满足这两个条件,这些对象就可以判定为Java中的内存泄漏,这些对象不会被GC所回收,然而它却占用内存。

会导致 Java 内存泄漏的一些场景

  1. 过度使用静态成员属性(static fields)
  2. 忘记关闭已打开的资源链接(unclosed Resources)
  3. 没有正确的重写 equals 和 hashcode 方法(HashMap HashSet)

哪些对象该被回收?一般有可达性分析和引用计数两种算法来识别可回收的对象:

  • 可达性分析
目前 Java 虚拟机的主流垃圾回收器采取的是可达性分析算法。这个算法的实质在于将一系列 GC Roots 作为初始的存活对象合集(live set),然后从该合集出发,探索所有能够被该集合引用到的对象,并将其加入到该集合中,这个过程我们也称之为标记(mark)。最终,未被探索到的对象便是死亡的,是可以回收的。
  • 引用计数的循环引用问题
可达性分析可以解决引用计数法所不能解决的循环引用问题。举例来说,即便对象 a 和 b 相互引用,只要从 GC Roots 出发无法到达 a 或者 b,那么可达性分析便不会将它们加入存活对象合集之中。

GC Roots 我们可以暂时理解为由堆外指向堆内的引用

Java 虚拟机中的垃圾回收器采用可达性分析来探索所有存活的对象。它从一系列 GC Roots 出发,边标记边探索所有被引用的对象。

一般而言,GC Roots 包括(但不限于)如下几种:

  1. Java 方法栈桢中的局部变量;
  2. 已加载类的静态变量;
  3. JNI handles;
  4. 已启动且未停止的 Java 线程。

jmap 命令

  • jmap -heap

查看堆内存初始化配置信息已经堆内存使用情况,垃圾收集器类型

jmap -heap pid
  • jmap -histo

统计各个类的实例数目以及占用内存,并按照内存使用量从多至少的顺序排列

jmap -histo:live pid
  • jmap -dump

把堆内存的使用情况 dump 到文件中,live 只保存堆中的存活对象

jmap -dump:live,format=b,file=dump.bin pid
Heap dump 是Java进程在特定时间点的一个内存快照,快照包含在dump时间点java堆中的对象和类的信息。 通常在dump时, 会触发一个完整的GC, 故而Heap Dump文件中只包含哪些未被回收的对象的信息

  • jmap 参数详细说明

image.png

输出 GC 日志

  • 当堆内存空间溢出时输出堆的内存快照
-XX:+HeapDumpOnOutOfMemoryError -XX:HeapDumpPath=/data/java/logs/
  • 输出 GC 详细日志并指定日志路径
-XX:+PrintGCDetails 输出GC的详细日志
-XX:+PrintGCTimeStamps 以基准时间的形式输出GC的时间戳(JVM 启动时间为起点的相对时间)
-XX:+PrintGCDateStamps 以日期的形式输出GC的时间戳(2013-05-04 T21:53:59.234+0800)
-XX:+PrintHeapAtGC 在进行GC的前后打印出堆的信息
-Xloggc:/data/java/logs/usercenter/gc.log 日志文件的输出路径

Eclipse MAT

Eclipse MAT(Memory Analyzer Tool)是一个强大的基于Eclipse的内存分析工具,可以帮助我们找到内存泄露,减少内存消耗

MAT 计算对象占据内存分为 Shallow Heap 和 Retained Heap 两种方式

  • Shallow heap
对象自身所占据的内存
  • Retained heap
当对象不再被引用时,垃圾回收器所能回收的总内存,包括对象自身所占据的内存,以及仅能够通过该对象引用到的其他对象所占据的内存

MAT 包含了两个比较重要的视图 直方图(histogram)和支配树(Dominator Tree

  • 直方图
MAT 的直方图类似 jmap -histo 命令输出的结果,能够展示各个类的实例数目以及这些实例的 Shallow heap 总和,并且可以根据 Shallow 或 Retained heap 从大到小排序
  • 支配树
支配树是由一些对象组成的图,在支配树中每个对象都是它子节点的直接支配者
  • 支配者
如果从入口节点到 b 节点的所有路径都要经过 a 节点,那么 a 支配(dominate)b
如果从 a 节点到 b 节点的所有路径中不存在支配 b 的其他节点,那么 a 直接支配(immediate dominate)b

注意点:对象的引用型字段未必对应支配树中的父子节点关系。假设对象 a 拥有两个引用型字段,分别指向 b 和 c。而 b 和 c 各自拥有一个引用型字段,但都指向 d。如果没有其他引用指向 b、c 或 d,那么 a 直接支配 b、c 和 d,而 b(或 c)和 d 之间不存在支配关系


使用 List objects 查看引用关系图

  • with outgoing references
查看当前对象持有的外部对象引用(在对象关系图中为从当前对象指向外的箭头)
  • with incoming references
查看当前对象被哪些外部对象所引用(在对象关系图中为指向当前对象的箭头)

  • Paths to GC Roots
可以通过该功能反向列出该对象到 GC Roots 的引用路径,这个路径解释了为什么当前对象还能存活,对分析内存泄露很有帮助,这个查询只能针对单个对象使用

image.png

  • Merge Shortest Paths to GC roots
通过下图我们可以看到 Context 直接支配 CtEntry,只要释放 Context 的引用,CtEntry 占用的内存就可以被回收

image.png


  • 线程视图(Thread Overview)
可以看到线程对象/线程栈信息、线程名、Shallow Heap、Retained Heap、类加载器、是否Daemon线程等信息

image.png

Sentinel 内存泄漏 bug 导致 full GC

image.png

sentinel-apache-dubbo-adapter Entry leak cause full GC #1416

这个问题首次出现在 Sentinel 1.7.1 版本,且只在如下场景发生:

A,B,C 三个应用,A 是服务消费者,B 是服务提供者并且是服务消费者,C 是服务提供者
A 请求 B 提供的服务,B 在处理 A 请求的同时调用 C 提供的服务
A(consumer) -> B(provider and consumer) -> C(provider)

B 应用 dubbo 业务线程池配置如下:

<dubbo:protocol name="dubbo" port="20077" threadpool="cached" threads="200"/>

cached 类型代表缓存线程池,如果空闲一分钟会自动删除,需要时重建(如果不间断每分钟都有请求需要处理,那么部分线程会一直存活)

  • RpcContext 和 Context

这里涉及到的两个 context 分别是 Dubbo 框架的 rcpContext,另外一个是 Sentinel 的 context

RpcContext 用来存储一些临时状态,这些状态会随着每次 request 的发送或者接收而改变
Sentinel context 也是用来存储一些调用的元数据
  • Entry 和 CtEntry
SphU#entry() 方法每次调用都会返回一个 Entry,Entry 存储着当前的调用信息
CtEntry 在 Entry 的基础上增加了 parent 和 child 的链式关联

image.png

  • Context 和 CtEntry 相互引用,应该释放哪个引用才会释放内存 ?
  • 为什么会存在 CtEntry 递归引用堆积的问题,并最终指向了同一个 Context ?
  • 为什么 providerFilter 没有正常执行 ContextUtil.exit() ?
  • 为什么 consumerFilter 不需要执行 ContextUtil.exit() ?

public class SentinelDubboConsumerFilter extends BaseSentinelDubboFilter {
    @Override
    public Result invoke(Invoker<?> invoker, Invocation invocation) throws RpcException {
        Entry interfaceEntry = null;
        Entry methodEntry = null;
        RpcContext rpcContext = RpcContext.getContext();
        try {
            String methodResourceName = DubboUtils.getResourceName(invoker, invocation, DubboConfig.getDubboConsumerPrefix());
            String interfaceResourceName = DubboConfig.getDubboInterfaceGroupAndVersionEnabled() ? invoker.getUrl().getColonSeparatedKey()
                    : invoker.getInterface().getName();
            InvokeMode invokeMode = RpcUtils.getInvokeMode(invoker.getUrl(), invocation);

            if (InvokeMode.SYNC == invokeMode) {
                interfaceEntry = SphU.entry(interfaceResourceName, ResourceTypeConstants.COMMON_RPC, EntryType.OUT);
                rpcContext.set(DubboUtils.DUBBO_INTERFACE_ENTRY_KEY, interfaceEntry);
                methodEntry = SphU.entry(methodResourceName, ResourceTypeConstants.COMMON_RPC, EntryType.OUT, invocation.getArguments());
            } else {
                // should generate the AsyncEntry when the invoke model in future or async
                interfaceEntry = SphU.asyncEntry(interfaceResourceName, ResourceTypeConstants.COMMON_RPC, EntryType.OUT);
                rpcContext.set(DubboUtils.DUBBO_INTERFACE_ENTRY_KEY, interfaceEntry);
                methodEntry = SphU.asyncEntry(methodResourceName, ResourceTypeConstants.COMMON_RPC, EntryType.OUT, 1, invocation.getArguments());
            }
            rpcContext.set(DubboUtils.DUBBO_METHOD_ENTRY_KEY, methodEntry);
            return invoker.invoke(invocation);
        } catch (BlockException e) {...}
    }
}
public class SentinelDubboProviderFilter extends BaseSentinelDubboFilter {
    @Override
    public Result invoke(Invoker<?> invoker, Invocation invocation) throws RpcException {
        // Get origin caller.
        String application = DubboUtils.getApplication(invocation, "");
        RpcContext rpcContext = RpcContext.getContext();
        Entry interfaceEntry = null;
        Entry methodEntry = null;
        try {
            String methodResourceName = DubboUtils.getResourceName(invoker, invocation, DubboConfig.getDubboProviderPrefix());
            String interfaceResourceName = DubboConfig.getDubboInterfaceGroupAndVersionEnabled() ? invoker.getUrl().getColonSeparatedKey()
                    : invoker.getInterface().getName();
            // Only need to create entrance context at provider side, as context will take effect
            // at entrance of invocation chain only (for inbound traffic).
            ContextUtil.enter(methodResourceName, application);
            interfaceEntry = SphU.entry(interfaceResourceName, ResourceTypeConstants.COMMON_RPC, EntryType.IN);
            rpcContext.set(DubboUtils.DUBBO_INTERFACE_ENTRY_KEY, interfaceEntry);
            methodEntry = SphU.entry(methodResourceName, ResourceTypeConstants.COMMON_RPC, EntryType.IN, invocation.getArguments());
            rpcContext.set(DubboUtils.DUBBO_METHOD_ENTRY_KEY, methodEntry);
            return invoker.invoke(invocation);
        } catch (BlockException e) {...}
    }
}
public abstract class BaseSentinelDubboFilter extends ListenableFilter {
    static void traceAndExit(Throwable throwable, URL url) {
        Entry interfaceEntry = (Entry) RpcContext.getContext().get(DubboUtils.DUBBO_INTERFACE_ENTRY_KEY);
        Entry methodEntry = (Entry) RpcContext.getContext().get(DubboUtils.DUBBO_METHOD_ENTRY_KEY);
        if (methodEntry != null) {
            Tracer.traceEntry(throwable, methodEntry);
            methodEntry.exit();
            RpcContext.getContext().remove(DubboUtils.DUBBO_METHOD_ENTRY_KEY);
        }
        if (interfaceEntry != null) {
            Tracer.traceEntry(throwable, interfaceEntry);
            interfaceEntry.exit();
            RpcContext.getContext().remove(DubboUtils.DUBBO_INTERFACE_ENTRY_KEY);
        }
        if (CommonConstants.PROVIDER_SIDE.equals(url.getParameter(CommonConstants.SIDE_KEY))) {
            ContextUtil.exit();
        }
    }
}

其他 JVM 监控和诊断工具

其他 JVM 监控和诊断指令

  • jstat
可用来打印目标 Java 进程的性能数据,以-gc为前缀的子命令,它们将打印垃圾回收相关的数据
  • jstack
可以用来打印目标 Java 进程中各个线程的栈轨迹,以及这些线程所持有的锁
  • jcmd

参考资料:

  1. Memory Analyzer Concepts
  2. MAT 中文翻译
  3. Eclipse Memory Analyzer Tool 的使用
  4. Understanding Memory Leaks in Java
查看原文

赞 0 收藏 0 评论 0

sixsixfly 发布了文章 · 2019-10-27

MySQL 索引

索引的大小限制

  • CHAR、VARCHAR、BINARY 和 VARBINARY 类型的字段创建索引时可以指定索引占用字节数
  • BLOB 和 TEXT 类型的字段创建索引时必须指定索引占用字节数(取对应字段的前缀)
  • InnoDB 表创建的索引最多不能超过 767 个字节(REDUNDANT or COMPACT row format)或 3072 个字节(DYNAMIC or COMPRESSED row format)
  • MyISAM 引擎创建的索引不能超过 1000 字节(超出时会报错,或者自动减少为限制的最大值)

compact row format
A row format for InnoDB tables. It was the default row format from MySQL 5.0.3 to MySQL 5.7.8. In MySQL 8.0, the default row format is defined by the innodb_default_row_format configuration option, which has a default setting of DYNAMIC. The COMPACT row format provides a more compact representation for nulls and variable-length columns than the REDUNDANT row format.

https://dev.mysql.com/doc/refman/8.0/en/innodb-row-format.html

row_format

查看原文

赞 0 收藏 0 评论 0

sixsixfly 发布了文章 · 2019-10-05

redis mysql 中的跳表(skip list) 查找树(btree)

跳表(skip list)

image.png

数组和链表对比:

  • 数组支持随机访问,根据下标随机访问的时间复杂度是 O(1)
  • 数组的插入和删除操作效率不高,平均情况下的时间复杂度是 O(logN)
  • 链表随机访问性能没有数组好,平均情况下的时间复杂度是 O(logN)
  • 链表插入和删除操作只需要改变相邻节点的指针,时间复杂度是 O(1)

二分查找底层依赖数组结构,跳表通过构建多级索引来提高查询效率,实现了基于链表结构的“二分查找”(查找、删除、添加等操作都可以拥有对数时间复杂度)

跳表时间和空间复杂度:

  • 查询操作的平均时间复杂度是 O(logN),最坏时间复杂度 O(N)
  • 插入操作的平均时间复杂度是 O(logN),最坏时间复杂度 O(N)
  • 删除操作的平均时间复杂度是 O(logN),最坏时间复杂度 O(N)
  • 平均空间复杂度是 O(N),最坏空间复杂度 O(N logN)

跳表时间复杂度分析:

  • 设原始链表有 N 个节点,每两个节点抽取一个节点作为上一级索引节点,这样第 k 层索引有 N/(2^k)个节点
  • 设共有 h 级索引,最高一级索引有 2 个节点,结合上面的分析知道 N/2^h = 2,所以 h + 1 = log2(N)
  • 加上原始链表这一层,整个跳表的高度是 log2(N)
  • 查找某个数据时若每层需比较 m 个节点,总的时间复杂度是 log2(m*N),可简化为 O(logN)(m 是个常数)

跳表索引动态更新:

  • 往跳表中插入数据时会选择性的将这个数据同步插入部分索引层中
  • 由随机函数来确定需要插入哪些索引层级,这样在可以避免在插入大量数据后跳表查询性能退化

Redis 有序集合(Sorted Set)

Reids 有序集合支持的核心操作有:插入数据、查找数据、删除数据、根据 score 按照区间查找数据

Redis 有序集合的底层编码有两种实现,分别是 ziplist 和 skiplist,当有序集合的元素个数小于 zset-max-ziplist-entries 配置(默认128个),并且每个元素的值都小于 zset-max-ziplist-value 配置(默认64字节)时,Redis 会用 ziplist 来作为有序集合的内部实现,上述两个条件之一不满足时,Redis 启用 skiplist 作为有序集合的内部实现(转换过程是不可逆转,只能从小内存编码向大内存编码转换)

下面演示了先查看 redis 的默认配置,并演示了往 zset 中添加元素时由于元素大于 64 字节,Redis 内部存储结构由开始的 ziplist 转变为一个 dict 加一个 skiplist (dict 用来查询数据到分数的对应关系,而 skiplist 用来根据分数查询数据)
clipboard.png

Redis 实现的跳跃表:

  • Redis 的跳跃表实现由 zskiplist 和 zskiplistNode 两个结构组成, 其中 zskiplist 用于保存跳跃表信息(比如表头节点、表尾节点、长度), 而 zskiplistNode 则用于表示跳跃表节点
  • 每个跳跃表节点的层高都是 1 至 32 之间的随机数(程序根据幂定律生成,越大的数出现的概率越小)
  • 在同一个跳跃表中,多个节点可以包含相同的分值,但每个节点的成员对象必须是唯一的
  • 跳跃表中的节点按照分值大小进行排序, 当分值相同时, 节点按照成员对象的大小进行排序
  • 原始链表层的每个节点有一个指向前继节点的指针,用于从表尾方向向表头方向迭代(当执行 ZREVRANGE 或 ZREVRANGEBYSCORE 等逆序处理有序集的命令时用到)

image.png

为什么 Redis 用跳表而不是查找树实现有序集合:

  • 针对数据插入、查询、删除及序区间查找等操作,跳表的时间复杂度不会比平衡树差
  • 跳表比树的结构更简洁,这样代码更容易实现、更容易维护和调试
  • 可以灵活的调整索引节点个数和原始链表节点个数之间的比例来平衡索引对内存的消耗和查询效率

有序结合使用字典结构的优势:

  • 可以在 O(1) 时间复杂度内检查给定 member 是否存在于有序集
  • 可以在 O(1) 时间复杂度内取出 member 对应的 score 值(实现 ZSCORE 命令)

为什么 Redis 使用 skiplist 转换 ziplist:

  • 压缩列表是 Redis 为了节约内存而开发的, 由一系列特殊编码的连续内存块组成的顺序型(sequential)数据结构
  • 压缩列表编码应用范围广泛,可以分别作为hash、list、zset类型的底层数据结构实现
  • 压缩列表新增删除操作涉及内存重新分配或释放,加大了操作的复杂性,适合存储小对象和长度有限的数据
  • Redis 提供了 {type}-max-ziplist-value 和 {type}-max-ziplist-entries 相关参数来控制 ziplist 编码转换

Redis 每种数据类型(type)可以采用的编码方式(encoding)对应关系

image.png

参考资料:
Redis Zset 源代码
Redis ZipList 源代码
Redis ziplist 设计与实现
Redis skiplist 设计与实现
Redis ziplist 实现有序集合
Redis skiplist 实现有序集合

Lucene 倒排索引列表

image.png

倒排索引/反向索引(Inverted index):

  • 倒排索引用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射,如果把一本书的目录理解为书的正向索引,那么书最后的索引页就是书的倒排索引

Lucene 是一个开源的高性能、可扩展的信息检索引擎,Lucene 的索引是基于倒排索引结构组织的,倒排列表本质上是基于 Term 的反向列表,倒排索引由 Term index,Term Dictionary 和 Posting List 组成

  • 单词词典(Term Dictionary)记录所有文档的单词,并记录单词到倒排列表的关联关系
  • 倒排列表(Posting list)记录了单词对应的文档集合,倒排链由有序的倒排索引项组成
  • 倒排索引项(Posting)中包含了文档Id(docId)、词频(TF)、位置(Position)和偏移量(Offset)

为了能够快速进行倒排链的查找和 docid 查找,Lucene 倒排列表采用了 SkipList 结构,这样可以快速的对两个倒排列集合求交集和并集

Elasticsearch 搜索服务器底层依赖于 Lucene 检索引擎,Elasticsearch 在处理多个索引查询合并操作时支持 skip list、bitmap 和 Roaring bitmap 三种实现方式,如果查询的 filter 缓存到了内存中(以 bitset 的形式),那么合并就是两个 bitset 的 AND,如果查询的 filter 没有缓存就用 skip list 的方式去遍历两个 on disk 的 posting list

参考资料:
Multi-level skipping on posting lists
Frame of Reference and Roaring Bitmaps
MultiLevelSkipListWriter.java
MultiLevelSkipListReader.java
时间序列数据库的秘密——索引
Lucene 查询原理及解析
基于Lucene查询原理分析Elasticsearch的性能

B-树(B-Tree)

二叉查找树(binary search tree):

  • 每个节点其左子树上所有节点值要小于该节点值,右子树上所有节点的值要大于该节点值

平衡二叉树查找树:

  • 二叉树查找树中任意节点的左子树和右子树的高度差不大于一

B-Tree 遵循如下规则:

  • B-Tree 是一种自平衡的 M 叉查找树
  • 根节点至少存在两个子节点,至多存在 M 个子节点
  • 除了根节点和叶子节点,每节点包含 k-1 个关键字和 k 个指向子节点的指针(k 的取值范围[M/2,M])
  • 叶子节点包含 k-1 个关键字(k 的取值范围 [M/2,M] )
  • 所有叶子节点在树的同一层

B+树(B+Tree)

image.png

B+ 树遵循如下规则:

  • B+Tree 是一颗自平衡的查找树
  • 每个节点最多有 M 个子节点(下文 MySQL 索引部分说明 M 取值)
  • 除根节点外,每个节点至少有 M/2 个子节点,根节点至少有两个子节点
  • 非叶子节点中只存储关键字和指向子节点的指针,不存储指向实际数据的指针
  • 通过双向链表将叶子节点串联起来,可以方便按区间查找(不用每次返回根节点)

B+ 树时间和空间复杂度:

  • 查询数据的时间复杂度是 O(logN)
  • 插入操作的时间复杂度是 O(logN)
  • 删除操作的时间复杂度是 O(logN)
  • 空间复杂度是 O(N)

B+ 树动态更新索引节点:

  • 写入数据后若某节点的子节点个数大于 M,会将对应节点分裂为两个节点,父节点如有需要会级联分裂
  • 删除数据后,如某节点的子节点个数小于 M/2,将相邻的兄弟节点合并

B+Tree 与 B-Tree 不同点:

  • 每个节点有 k 个关键字就有 k 个子节点(B-Tree 有 k 个关键字时有 k+1 个子节点)
  • 非叶子节点的关键字也存在于子节点中,并且是子节点中的最小/最大关键字
  • B+Tree 非叶子节点只用于索引,不保存数据记录(B-Tree 中非叶子节点既保存索引也保存数据记录)
  • B+Tree 关键字只出现在叶子节点,并且构成有序链表(按关键字从小到大排列)

MySQL InnoDB 索引

文件系统和数据库系统通常使用 B+Tree 来存储索引,MySQL 的大部分索引(PRIMARY KEY、UNIQUE INDEX)使用 B+Tree 结构存储,也有一些特例,如 InnoDB 使用倒排索引(inverted lists)作为全文索引(FULLTEXT)的存储结构 (MongoDB 也是使用 b-tree 构造索引

  • MySQL 的索引分为聚簇索引(clustered index)和二级索引(secondary index)
  • 可以把 MySQL 的索引理解为一颗聚簇索引 B+Tree 和其他一到多颗二级索引 B+Tree
  • 聚簇索引树的叶子节点保存了主键和实际数据记录行
  • 二级索引树的叶子节点保存了指向主键的指针和创建二级索引的列数据

聚簇索引:
mysql cluster index.png
二级索引:
mysql secondary index.png

MySQL 不同存储引擎支持的索引存储结构如下

image.png

为什么 MySQL 使用 B+Tree 结构实现索引:

  • 对于数据存储在磁盘中的数据库系统而言,I/O 操作次数是影响性能的重要因素
  • 操作系统是按页(getconf PAGESIZE,默认 4K)读取磁盘中数据,一次读取一页数据
  • 如果读取的数据量超过一页大小,会触发多次 I/O 操作
  • 若 M 的取值让每个节点大小等于页大小,这时读取一个节点只需要一次磁盘 I/O 操作
  • B+Tree 的非叶子结点只保存关键字和指向子结点的指针,相同的页大小可以存储更多的节点数,同时减少了树的高度增加了树的分叉数,进而减少了磁盘 I/O 操作次数
  • 删除数据时更简单,因为 B+Tree 实际数据只保存在叶子结点,所以不需要删除非叶子结点

为什么 MySQL InnoDB 索引遵循最左匹配原则

  • InnoDB 存储引擎使用 B+Tree 保存索引
  • B+Tree 是一颗所有节点有序的查找树,每次查找从根节点开始对比,根据比较的结果确定继续查找左子树或右子树

处理从右到左匹配的需求:

方案一:表结构新增一列用来存储需要从右到左匹配列的倒序字符并构建索引,缺点是新增列和索引都需要占用磁盘空间
方案二:Mysql 5.7 版本提供了虚拟列功能,使用 reverse 函数构建虚拟列并创建索引
具体脚本可以参考 mysql innodb 索引使用指南

参考资料:
create-index
https://dev.mysql.com/doc/internals/en/innodb-fil-header.html
高性能 mysql
mysql 5.7 virtual generated columns index
create-table-generated-columns

红黑树(Red-Black Tree)

Diagram of binary tree. The black root node has two red children and four black grandchildren. The child nodes of the grandchildren are black nil pointers or red nodes with black nil pointers.

红黑树是一颗自平衡的二叉查找树(只做到了近似平衡)

红黑树遵循如下规则:

  • 每个节点要么是红色要么是黑色
  • 根节点始终是黑色的
  • 没有相邻的两个红色节点(每个红色节点的两个子节点都是黑色)
  • 从任意节点到任意叶子节点的路径,包含相同数量的黑色节点

红黑树与 B+Tree 对比:

  • B+Tree 比红黑树的查询性能更好,因为 B+Tree 是严格的平衡树
  • 红黑树比 B+Tree 的插入和删除性能更好(红黑树有更松散的平衡性,插入和删除数据后树的节点再平衡操作更少,性能更稳定)
  • 红黑树适合用于构建存储在内存中的索引如 JDK 中 HashMap,B+Tree 适合用来构建存储在磁盘中的索引,如 MySQL 和 Oracle 中的索引

JDK HashMap

Java 7 以及之前版本的 HashMap 同一个桶(Bucket)里面的节点(Entry)使用链表(Linked list)串联起来,当同一个桶里面存在过多节点时(对不同 key 的 hashcode 函数取值相等),查询时间的复杂度会从哈希 O(1) 退化到链表 O(N),为了避免上述问题, Java 8 的 HashMap 同一个桶中的节点个数在满足一定条件时会使用红黑树结构代替链表结构

红黑树和链表相互转换规则:

  • 当单个桶中的节点个数大于 TREEIFY_THRESHOLD( 默认 8),并且桶的个数大于 MIN_TREEIFY_CAPACITY( 默认 64),对应的桶会使用红黑树替代链表结构
  • 当移除元素后单个桶中的节点个数小于 UNTREEIFY_THRESHOLD( 默认 6),对应的桶会从红黑树恢复到链表结构
/**
 * The bin count threshold for using a tree rather than list for a bin.  
 * Bins are converted to trees when adding an element to a bin with at least this many 
 * nodes The value must be greater than 2 and should be at least 8 to mesh with 
 * assumptions in tree removal about conversion back to plain bins upon shrinkage.
 */
static final int TREEIFY_THRESHOLD = 8;
/**
 * The bin count threshold for untreeifying a bin during a resize operation.Should be less
 * than TREEIFY_THRESHOLD, and at most 6 to mesh with shrinkage detection under removal.
 */
static final int UNTREEIFY_THRESHOLD = 6;
/**
 * The smallest table capacity for which bins may be treeified. (Otherwise the table is 
 * resized if too many nodes in a bin.) Should be at least 4 plus TREEIFY_THRESHOLD to 
 * avoid conflicts between resizing and treeification thresholds.
 */
static final int MIN_TREEIFY_CAPACITY = 64;

JDK ConcurrentSkipListMap

  • ConcurrentSkiplistMap 对插入,删除,更新和获取元素支持并发操作
  • map 的元素根据创建时 key 的自然顺序排序
  • 针对 containsKey、get、put 和 remove 操作确保了 O(log(n)) 的平均时间复杂度
  • ConcurrentSkiplistMap 是基于 skiplist 结构实现的
/**
 * A scalable concurrent ConcurrentNavigableMap implementation.The map is sorted 
 * according to the {@linkplain Comparable natural ordering} of its keys, or by a 
 * Comparator provided at map creation time, depending on which constructor is used.
 *
 * <p>This class implements a concurrent variant of SkipLists providing expected 
 * average <i>log(n)</i> time cost for the {@code containsKey}, {@code get}, 
 * {@code put} and {@code remove} operations and their variants.  Insertion, removal,
 * update, and access operations safely execute concurrently by multiple threads.
 */

JDK TreeMap 与 TreeSet

  • JDK TreeMap 是基于红黑树实现了 java.util.NavigableMap 接口
  • TreeMap 的元素根据创建时 key 的自然顺序排序
  • TreeMap 提供了在 log(N) 平均时间复杂度下的 get,put,containsKey 和 remove 操作
/**
 * A Red-Black tree based {@link NavigableMap} implementation. The map is sorted according 
 * to the {@linkplain Comparable natural ordering} of its keys, or by a {@link Comparator} 
 * provided at map creation time, depending on which constructor is used.
 * 
 * This implementation provides guaranteed log(n) time cost for the {@code containsKey}, 
 * {@code get}, {@code put} and {@code remove} operations.  Algorithms are adaptations of 
 * those in Cormen, Leiserson, and Rivest's Introduction to Algorithms.
 */
  • JDK TreeSet 是基于 TreeMap 实现了 java.util.NavigableSet 接口
  • TreeSet 的元素根据创建时 key 的自然顺序排序
  • TreeSet 提供了在 log(N) 平均时间复杂度下的 add,remove 和 contains 操作
/**
 * A {@link NavigableSet} implementation based on a {@link TreeMap}.
 * The elements are ordered using their {@linkplain Comparable natural
 * ordering}, or by a {@link Comparator} provided at set creation
 * time, depending on which constructor is used.
 *
 * <p>This implementation provides guaranteed log(n) time cost for the basic
 * operations ({@code add}, {@code remove} and {@code contains}).
 */

常见数据结构空间时间复杂度

image.png
参考资料:
https://www.bigocheatsheet.com/

查看原文

赞 1 收藏 1 评论 0

认证与成就

  • 获得 3 次点赞
  • 获得 2 枚徽章 获得 0 枚金徽章, 获得 1 枚银徽章, 获得 1 枚铜徽章

擅长技能
编辑

(゚∀゚ )
暂时没有

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 2014-10-29
个人主页被 1.2k 人浏览