计算机网络的层次结构

OSI 七层模型

TCP/IP 四层模型

常见概念

万维网、互联网和以太网的区别

互联网（Internet）是一个概念，是广域网的一种（WAN，Wide Area Network），在全世界被广泛使用。互联网通过 TCP/IP 协议，把全球范围内的局域网连接在一起，可以实现点对点的网络通讯。

以太网（Ethernet）是一种常见的局域网（LAN，Local Area Network）技术，工作在物理层和数据链路层。在物理层，它定义了电气特性、信号传输速率和距离限制等规范。在数据链路层，以太网定义了帧格式、帧起始和结束标记、帧同步和帧检验序列等。

从网络模型来看，互联网是在网络层及之上构建的互联网络，而以太网则是工作在数据链路层及之下的一种技术。互联网是被人普遍认为的网络，而以太网则是被广泛使用的构建局域网的技术。

万维网（World Wide Web）是一种基于英特网的信息系统，通过超文本链接的方式来组织、检索和共享文档和资源。在万维网上，不同的文档和资源通过统一的标识符（URL，统一资源定位符）进行唯一标识。万维网的核心技术是HTTP（Hypertext Transfer Protocol），它定义了在网络上传输超文本资源的规范。

MAC 地址

MAC地址（Media Access Control Address）是网络设备（如网卡、无线适配器）在出厂时固定分配的唯一标识符。它是一个由12个十六进制数（0-9，A-F）组成的字符串，通常以冒号或短横线分隔。MAC地址由两部分组成：前6个十六进制数表示厂商代码（OUI，Organizationally Unique Identifier），用于标识设备制造商；后面的6个十六进制数是设备的序列号，由制造商分配。

MAC地址是在数据链路层上使用的，用于局域网内设备之间的直接通信。当设备在局域网上发送数据时，目标设备的MAC地址用于将数据帧传送到正确的设备。

需要注意的是，MAC地址只在局域网内部有效，不会跨越路由器传输。在互联网上进行通信时，数据包会根据目标IP地址进行路由，而不是MAC地址。

常见网络工具

ping

用于判断网络联通状态。

1
2
3
4

# ipv4 地址
ping 10.0.10.1 
# ipv6 地址
ping6 2001:4860:4860::8888 

注意：

• 没有收到消息回复，不一定是网络不通，也有可能是目标设备关闭了 ping 请求相应

telnet

可以远程连接开启 telnet 服务器的目标设备，也可以判断目标设备的某个端口的连通性。

1

telnet 10.0.10.1 8080

TCP/IP

建立/断开连接

TCP状态转换图

建立连接(三次握手)

• 客户端发送一个带SYN标志的TCP报文到服务器(报文1)
• 服务器端回应客户端(报文2), 这个报文同时带ACK标志和SYN标志. 因此, 它表示对刚才客户端SYN报文的回应, 同时又发送标志SYN给客户端, 询问客户端是否准备好进行数据通讯
• 客户端必须再次回应服务端一个ACK报文(报文3)

再述三次握手。

• 客户端想要建立连接，SYN 标志置为 1，序列号每次都有，所以将首部的 seq 设置为一个随机值 i
• 服务端确认建立连接，SYN 标志置为 1，作为响应报文，ACK 标志置为 1，同样设置首部的 seq 为一个随机值 j，同时设置 ack 指明对方下一次需要发送的报文序列为 i+1
• 客户端接收到服务端的连接请求，发送确认消息，作为响应报文，ACK 标志置为 1，同时将报文序列seq置为 i+1，请求对方下一次发送序列号为 j+1 的报文，ack 置为 j+1

终止连接(四次握手)

由于TCP连接是全双工的，因此每个方向都必须单独进行关闭。当一方完成它的数据发送后发送一个FIN来终止这个方向的连接，另一端收到FIN后，仍可以发送数据。首先进行关闭的一方执行主动关闭，另一方执行被动关闭。

• TCP客户端发送一个FIN, 用来关闭客户端到服务端的数据传送
• 服务端收到FIN, 发回一个ACK, 确认序号为收到的序号加一. 和SYN一样, 一个FIN占用一个序号
• 服务端关闭客户端的连接, 发送一个FIN给客户端
• 客户端发回ACK报文确认, 并将确认序号设置为收到的序号加一

再述四次握手，终止连接。

终止连接，需要双方都发送终止请求，并回复对方。

• 客户端主动关闭，置 FIN 为 1，序列号seq置为u
• 服务端被动关闭，回复客户端的关闭请求，因为是响应报文，置ACK为 1，指明对方下一个报文序列，ack 置为 u+1
• 服务端开始主动关闭，置 FIN 为 1，序列号 seq 置为 w，指明对方下一个报文序列，ack 置为 u + 1
• 客户端被动关闭，恢复服务端的关闭请求，因为是响应报文，置ACK为1，返回对方想要的报文序列，置 seq 为 u+1，指明对方下一个报文序列，ack 置为 w+1

状态

同时关闭/打开连接

问题

为什么建立连接是三次握手, 关闭连接是四次握手?

这是因为，服务端的LISTEN状态下的SOCKET当收到SYN报文的连接请求后，它可以把ACK和SYN（ACK起应答作用，而SYN起同步作用）放在一个报文里来发送。但关闭连接时，当收到对方的FIN报文通知时，它仅仅表示对方没有数据发送给你了；但未必你所有的数据都全部发送给对方了，所以你可以未必会马上会关闭SOCKET，也即你可能还需要发送一些数据给对方之后，再发送FIN报文给对方来表示你同意现在可以关闭连接了，所以它这里的ACK报文和FIN报文多数情况下都是分开发送的。

TIME_WAIT后还需要SMSL

• TCP协议在关闭连接的四次握手过程中，最终的ACK是由主动关闭连接的一端（后面统称A端）发出的，如果这个ACK丢失，对方（后面统称B端）将重发出最终的FIN，因此A端必须维护状态信息（TIME_WAIT）允许它重发最终的ACK。如果A端不维持TIME_WAIT状态，而是处于CLOSED 状态，那么A端将响应RST分节，B端收到后将此分节解释成一个错误（在java中会抛出connection reset的SocketException)。

  因而，要实现TCP全双工连接的正常终止，必须处理终止过程中四个分节任何一个分节的丢失情况，主动关闭连接的A端必须维持TIME_WAIT状态 。

• 允许老的重复分节在网络中消逝（实际也就是避免同一端口对应多个套接字）. TCP分节可能由于路由器异常而“迷途”，在迷途期间，TCP发送端可能因确认超时而重发这个分节，迷途的分节在路由器修复后也会被送到最终目的地，这个迟到的迷途分节到达时可能会引起问题。在关闭“前一个连接”之后，马上又重新建立起一个相同的IP和端口之间的“新连接”，“前一个连接”的迷途重复分组在“前一个连接”终止后到达，而被“新连接”收到了。为了避免这个情况，TCP协议不允许处于TIME_WAIT状态的连接启动一个新的可用连接，因为TIME_WAIT状态持续2MSL，就可以保证当成功建立一个新TCP连接的时候，来自旧连接重复分组已经在网络中消逝。

关闭TCP连接一定需要四次握手吗

不一定，4次挥手关闭TCP连接是最安全的做法。但在有些时候，我们不喜欢TIME_WAIT状态（如当MSL数值设置过大导致服务器端有太多TIME_WAIT状态的TCP连接，减少这些条目数可以更快地关闭连接，为新连接释放更多资源），这时我们可以通过设置SOCKET变量的SO_LINGER标志来避免SOCKET在close()之后进入TIME_WAIT状态，这时将通过发送RST强制终止TCP连接（取代正常的TCP四次握手的终止方式）。但这并不是一个很好的主意，TIME_WAIT 对于我们来说往往是有利的。

TCP如何保证可靠传输

• 序列号、确认和重传：每条报文指定一个序列号，接收方收到报文会发送确认，如果发送方迟迟未收到确认，就重传
• 数据校验
• 连接管理
• 窗口控制
• 流量控制
• 拥塞控制

参考

• https://www.cnblogs.com/xiaokang01/p/10033267.html

Nagle算法

规则

• 如果包长度达到MSS, 则允许发送
• 如果包还有FIN, 则允许发送
• 设置了TCP_NODELAY选项, 则允许发送
• 未设置TCP_CORK选项时, 若所有发出去的小数据包(包长度小于MSS)均被确认, 则允许发送;
• 上述条件都未满足, 但发生了超时(一般为200ms), 则立即发送

其他说明

• Nagle算法只允许一个未被ACK的包存在于网络，它并不管包的大小，因此它事实上就是一个扩展的停-等协议，只不过它是基于包停-等的，而不是基于字节停-等的
• Nagle算法完全由TCP协议的ACK机制决定，这会带来一些问题，比如如果对端ACK回复很快的话，Nagle事实上不会拼接太多的数据包，虽然避免了网络拥塞，网络总体的利用率依然很低
• Nagle算法是silly window syndrome(SWS)预防算法的一个半集。SWS算法预防发送少量的数据，Nagle算法是其在发送方的实现，而接收方要做的是不要通告缓冲空间的很小增长，不通知小窗口，除非缓冲区空间有显著的增长。这里显著的增长定义为完全大小的段（MSS）或增长到大于最大窗口的一半。
• 注意：BSD的实现是允许在空闲链接上发送大的写操作剩下的最后的小段，也就是说，当超过1个MSS数据发送时，内核先依次发送完n个MSS的数据包，然后再发送尾部的小数据包，其间不再延时等待。（假设网络不阻塞且接收窗口足够大）
• 当有一个TCP数据段不足MSS，比如要发送700Byte数据，MSS为1460Byte的情况。nagle算法会延迟这个数据段的发送，等待，直到有足够的数据填充成一个完整数据段
• 为了解决大量的小报文对通信造成的影响，提高传输效率

参考

• 参考一

其他

• ACK: 应答作用
• SYN: 同步作用

I/O

阻塞 I/O

通常I/O操作都是 阻塞I/O，以一次读操作为例，数据先被拷贝到操作系统内核的缓冲区中，然后才会从操作系统内核的缓冲区拷贝到应用程序的地址空间，对应数据准备、数据拷贝两个阶段。在数据准备阶段，线程/进程会被挂起，当数据拷贝至应用程序内存空间后，线程/进程被唤醒。

非阻塞 I/O

如果使用阻塞I/O，同时处理1000个请求，则需要1000个线程，虽然大多数线程可能被挂起，但不可避免的是频繁的线程上下文切换，非常占用系统资源，每个线程的时间槽也会非常短，导致系统整体有效负载降低，此外每个线程还会占用 512KB / 1MB 的内存。

此时，引入了 非阻塞I/O 的概念，通过调用 fcntl（POSIX）/ ioctl（Unix）设为非阻塞模式。在此模式下，如果有数据收到，就会返回数据，否则立即返回一个错误。这样虽然不会阻塞线程，但需要线程不断轮询来读取或写入。

I/O 多路复用

为了解决单线程轮询单个文件描述符效率低下的问题，有了 I/O多路复用 的概念，多路是指多个文件描述符（socket连接），复用指的是复用一个线程。

所以，I/O多路复用是指，使用一个线程来检查多个文件描述符的就绪状态，如调用 select / poll 函数，传入多个文件描述符，如果有一个就绪，则返回，否则阻塞至超时。

这样在处理1000个连接时，只需要1个线程监控就绪状态，对就绪的每个连接开一个线程处理就可以了，这样需要的线程数大大减少，减少了内存开销和上下文切换的CPU开销。

I/O多路复用（多路是指多个文件描述符（fd，file descriptor，socket 是fd的一种），复用指的是复用一个线程），主要技术有 select、poll、epoll。

select

select 会将全量fd_set从用户空间拷贝到内核空间，并注册回调函数， 在内核态空间来判断每个请求是否准备好数据 。select在没有查询到有文件描述符就绪的情况下，将一直阻塞（select是一个阻塞函数）。如果有一个或者多个描述符就绪，那么select将就绪的文件描述符置位，然后select返回。返回后，由程序遍历查看哪个请求有数据。

缺陷

• 牵扯到两次内存拷贝，第一次将 fd_set 从用户空间拷贝至内核空间；第二次是将 fd_set 从内核空间拷贝至用户空间
• 牵扯到两次集合遍历，都是对 fd_set 遍历，第一次发生在内核态，第二次发生在用户态
• select 文件描述符有上限，及 fd_set 的容量，虽然可以通过宏 FD_SETSIZE 来设置

poll

poll的实现和select非常相似，只是描述fd集合的方式不同，poll使用pollfd结构代替select的fd_set（网上讲：类似于位图）结构，其他的本质上都差不多。所以Poll机制突破了Select机制中的文件描述符数量最大为1024的限制。

缺陷

• 同样会有两次遍历和内存拷贝

epoll

epoll 对 select 的三个缺陷进行了修复。

解决内存拷贝：epoll 方式下，fd 是通过mmap共享内存的方式，避免在用户空间和内核空间的拷贝。

解决多次遍历：epoll不像select或poll一样每次都把当前线程轮流加入fd对应的设备等待队列中，而只在epoll_ctl时把当前线程挂一遍（这一遍必不可少），并为每个fd指定一个回调函数。当设备就绪，唤醒等待队列上的等待者时，就会调用这个回调函数，而这个回调函数会把就绪的fd加入一个就绪链表。那么当我们调用epoll_wait时，epoll_wait只需要检查链表中是否有存在就绪的fd即可，效率非常可观。

解决fd 数量限制：pollfd 结构代替 fd_set 解决数量限制， 使用双向链表保存就绪状态的fd。

工作模式

epoll 分为两种工作模式，LT（level trigger，水平触发） 和 ET（edge trigger，边缘触发），两种模式的区别是在于对就绪fd的处理。

• LT模式： 默认的工作模式，即当epoll_wait检测到某描述符事件就绪并通知应用程序时，应用程序可以不立即处理该事件；事件会被放回到就绪链表中，下次调用epoll_wait时，会再次通知此事件。
• ET模式： 当epoll_wait检测到某描述符事件就绪并通知应用程序时，应用程序必须立即处理该事件。如果不处理，下次调用epoll_wait时，不会再次响应并通知此事件。

异步 I/O

进程 / 线程在发起IO操作之后，内核会立刻返回，不会阻塞用户线程/进程。当内核把数据准备完毕后，向用户进程发送一个signal通知。

参考

• https://www.zhihu.com/question/28594409
• https://www.ibm.com/support/knowledgecenter/ssw_ibm_i_72/rzab6/xnonblock.htm
• https://zhuanlan.zhihu.com/p/95872805
• https://cloud.tencent.com/developer/article/1005481

简介

简单的说，netty 提供了一个NIO（异步非阻塞IO）网络框架，基于此可以轻松地开发高性能的网络应用。

优点

• 支持多种协议，且有统一的API
• 强大的线程模型
• 高性能

常见问题

reactor

reactor 模式是事件驱动的一种实现，将服务端接受请求和事件处理分离，从而提升系统处理并发的能力，java的NIO的reactor模式是基于系统内核的多路复用技术实现的。

reactor模式有三个组件，Handler、Demultiplexer、Reactor，核心是 IO复用 + 非阻塞编程 + bind/function。

reactor 和 I/O多路复用

reactor 是一种网络编程模式，其底层多使用系统实现的I/O多路复用能力。

高性能原因

• 基于Reactor模式实现的 NIO（异步阻塞IO），IO多路复用
• TCP接受和发送缓冲区使用直接内存代替堆内存，避免了内存复制
• 使用内存池的方式，循环利用 ByteBuf
• 环形数组缓冲区实现无锁化并发编程
• 关键资源的处理使用单线程串行化，避免使用锁

线程模型

在 Netty 主要靠 NioEventLoopGroup 线程池来实现具体的线程模型的 。我们实现服务端的时候，一般会初始化两个线程组，Boss Group 和 Worker Group，前者用于接收连接，后者负责具体的处理，交由对应的 Handler 处理。

Netty 可以实现多种线程模型，单线程、多线程、主从多线程模型。

启动流程

• 创建两组线程组，Boss 和 Worker
• 创建服务端启动引导/辅助类 ServerBootstrap
• 为引导类设置线程组
• 绑定端口，得到 ChannelFuture 对象
• 阻塞等待 Future 对象，知道服务器 Channel 关闭
• 关闭线程组

默认线程数量

CPU核心数 * 2。

处理流程

BIO / NIO / AIO

• BIO：阻塞IO
• NIO：非阻塞IO
• AIO：异步非阻塞IO

netty 中的 selector

Selector 能够检测多个注册的通道上是否有事件发生（多个Channel以事件的方式可以注册到同一个Selector），如果有事件发生，便获取事件然后针对每个事件进行相应的处理。这样就可以只用一个单线程去管理多个通道，也就是管理多个连接和请求。

netty 的核心组件

• Channel
  • Netty 的网络操作抽象类，包含了基本的I/O操作，bind、connect、read、write 等，降低了直接使用 Socket 的复杂度
  • 与 EventLoop 一起处理I / O
• ChannelHandler
  • 用于处理各种事件，以支持各种协议和处理数据的方式
  • 比如，连接、数据接收、异常、数据转换等
• ChannelPipeline
  • 提供了 ChannelHandler 链的容器
• EventLoop
  • EventLoop 定义了Netty的核心抽象，用于处理连接的生命周期中所发生的事件
  • 负责监听网络事件，并调用事件处理器进行相关的 I/O 操作的处理

Channel 和 EventLoop 联系

Channel 是为 Netty 网络操作的抽象类，EventLoop 负责处理注册到其上的Channel，处理I/O操作，两者配合完成I/O操作

EventloopGroup 和 EventLoop 关系

EventLoopGroup 是一组 EventLoop 的抽象，提供了 next 接口，从一组 EventLoop 中按规则选择一个 EventLoop 来处理任务。

BootStrap 和 ServerBootStrap

BootStrap 通过 connect 方法连接远程主机，作为TCP协议的客户端，或通过bind方法绑定本地端口，作为UDP协议的一端。只需配置一组 EventLoopGroup。

ServerBootStrap 通过 bind 方法绑定本地端口，等待客户端连接。需配置两组 EventLoopGroup ，一个用于接收，一个用于处理，即 Boss EventLoopGroup 和 Worker EventLoopGroup。

应用场景

• RPC框架的网络通讯工具
• 搭建网络应用，http 或其他

参考

• https://www.cnblogs.com/lihonglin2016/p/9774957.html
• https://zhuanlan.zhihu.com/p/148726453
• https://www.jianshu.com/p/eef7ebe28673
• https://www.zhihu.com/question/320829696
• http://www.blogjava.net/DLevin/archive/2015/09/02/427045.html

[toc]

简述

架构

redis的部署模式分为集群模式和哨兵模式，哨兵模式下的角色有主 + 从 + sentinel。无论哪种模式，主从模式都是存在的，起到读写分离、数据备份的作用。

哨兵模式

哨兵是一个独立与数据节点的进程，具备集群监控、消息通知、故障自动转移、配置中心的功能，用于解决高可用的问题。

这里了解两个概念，主观下线和客观下线。单个哨兵判断一个主节点下线，为主观下线；该哨兵向其他哨兵确认主节点是否下线，当一半以上哨兵确定主节点下线，则判定该主节点为客观下线。主节点被判定为客观下线后，哨兵会启动Raft选主程序，最终被投为领导者的哨兵节点完成主从自动切换的过程。

集群模式

官方提供的分布式方案，包含槽指派、重新分片、故障转移。

哨兵模式和集群模式的区别

• 监控：哨兵模式下，监控权交给了哨兵系统；集群模式下，工作节点自己监控
• 故障转移：哨兵模式下，哨兵发起选举，得到一个leader来处理故障转移；集群模式下，是在从节点中选举一个新的主节点，来处理故障的转移

数据安全

数据丢失

• 主从复制
  • 由于复制是异步的，如果在未复制前主节点宕机，数据丢失
• 脑裂
  • 网络分区间不可访问导致某个master节点和集群失联，但是客户端依然在写入数据，这部分数据会丢失

数据类型

string

string 类型是二进制安全的，一个键最大能存储512MB数据。存储结构分位整数、EmbeddingString、SDS，整数存储字符串长度小于21且能转化为整数的字符串；EmbeddingString 存储字符串长度小于 39 的字符串；SDS 存储不满足上述条件的字符串。

• 只对长度小于或等于 21 字节，并且可以被解释为整数的字符串进行编码，使用整数存储

• 尝试将 RAW 编码的字符串编码为 EMBSTR 编码，使用EMBSTR 编码

• 这个对象没办法进行编码，尝试从 SDS 中移除所有空余空间，使用SDS编码

SDS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

/*
 * 保存字符串对象的结构
 */
struct sdshdr {
    
    // buf 中已占用空间的长度
    int len;

    // buf 中剩余可用空间的长度
    int free;

    // 数据空间
    char buf[];
};

/*
 * 返回 sds 实际保存的字符串的长度
 *
 * T = O(1)
 */
static inline size_t sdslen(const sds s) {
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
    return sh->len;
}

/*
 * 返回 sds 可用空间的长度
 *
 * T = O(1)
 */
static inline size_t sdsavail(const sds s) {
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
    return sh->free;
}

SDS扩容

当字符串长度小于SDS_MAX_PREALLOC (1024*1024)，那么就以2倍的速度扩容，当字符串长度大于SDS_MAX_PREALLOC，那么就以+SDS_MAX_PREALLOC的速度扩容。

SDS缩容

释放内存的过程中修改len和free字段，并不释放实际占用内存。

hash / 字典

底层使用哈希表实现，结构为数组+链表。redis 字典包含两个哈希表，用于在 redis 扩缩容时的渐进式rehash。

线程

redis 4.0 之后，新增了后台线程处理重操作，比如清理脏数据、无用连接的释放、大 key 的删除，但是工作线程仍然是单线程。基于内存的redis，性能瓶颈不在处理器，主要受限于内存和网络。redis 6.0 新增 I/O 线程，用于处理处理 I/O 的读写，使多个socket的读写可以并行，为工作线程减压。

其他

rehash

在集群模式下，一个 redis 实例对应一个 RedisDB，一个RedisDB对应一个Dict，一个Dict对应两个Dictht（dict hash table），正常情况下只用到 ht[0]；ht[1] 在 rehash 时使用。

rehash 是redis在字典扩缩容时进行的操作，rehash 过程中，字典同时持有两个哈希表，删除、查找、更新等操作都会在两个哈希表上进行，新增操作只在新的哈希表进行，原有的数据的搬迁通过后续的客户端指令（hset、hdel）及定时任务完成。

触发条件

扩容条件：数据量大于哈希表数组长度时触发，如果数据量大于数组长度5倍，则进行强制扩容；缩容条件：数据量小于数组长度的10%。

问题

• 满容驱逐，由于 rehash 过程中会为新的哈希表申请空间，导致满容状态下大范围淘汰key

lpush

epoll

redis中使用IO多路复用（多路是指多个socket连接，复用指的是复用一个线程）的epoll方式。

问题

为什么吞吐量高？

• IO多路复用
• 基于内存的数据操作

过期机制？

可从过期策略和淘汰策略来分析。过期策略分位被动删除和主动删除两类，被动删除主要是读取过期key，惰性删除；主动删除，包括定期清理和内存超过阈值触发主动清理。

淘汰策略有多种。

注：

• LRU：Least Recently Used，即最近最久未使用。如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。通常使用map+链表的方式实现，map判断key是否存在，链表保存顺序。
• LFU：Least Frequently Used，最近最少使用算法。与LRU算法的不同之处，LRU的淘汰规则是基于访问时间，而LFU是基于访问次数的。
• FIFO：First in First out，先进先出。

参考

• https://www.cnblogs.com/madashu/p/12832766.html
• https://www.cnblogs.com/aspirant/p/9166944.html
• https://i6448038.github.io/2019/12/01/redis-data-struct/

mutex lock

所谓锁，在计算机中，本质是内存中的一块空间，其值被赋予了加锁/未加锁的含义，其底层实现，是基于计算机系统中的原子操作。

mutex lock 核心包含两点。

• Compare And Set（CAS）
  • 互斥锁是对临界区的保护，能否进入临界区即能否获取到锁，思路都是判断并置位一个标志位，这个标志位本身可以是一个普通的内存变量，关键在于，对于这个变量的"判断并置位"操作需要是原子的。
  • 计算机实现原子操作，对于单核机器，关中断防止调度即可；多核理论上可使用 spinlock 保护，实际一般通过原子汇编语言实现，比如x86的tsl指令（test and set），可以用一条“无法继续分割的”汇编指令实现判断变量值并根据是否为0进行置位，具体这个指令实现原子性一般通过锁总线实现，也就是我执行这条指令时，其它核都不能访问这个地址了。
• 根据所是否获得，决定执行策略
  • 如果锁持有，则继续运行
  • 如果所没有获取到，常规做法是将当前任务挂起，并附在 mutex 变量对应的链表上，一旦锁被释放，查找锁上挂起的任务并唤醒

简述

进程（Process）是计算机中的程序关于某数据集合上的一次运行活动，是系统进行资源分配和调度的基本单位，是操作系统结构的基础。

线程（Thread）是操作系统能够进行运算调度的最小单位。它被包含在进程之中，是进程中的实际运作单位。一条线程指的是进程中一个单一顺序的控制流，一个进程中可以并发多个线程，每条线程并行执行不同的任务。

协程 （coroutine）是可暂停和恢复执行的过程，是一种编程思想。

协程

子程序，或者称为函数，在所有语言中都是层级调用。子程序调用是通过栈实现的，一个线程同一时间就是执行一个子程序。协程本质上也是子程序，协程作为子程序最大的特征是可中断可恢复。

关联

Java 中的线程

green threads VS native threads

green threads 是一种由运行环境或虚拟机(VM)调度，而不是由本地底层操作系统调度的线程。绿色线程并不依赖底层的系统功能，模拟实现了多线程的运行，这种线程的管理调配发生在用户空间而不是内核空间，所以它们可以在没有原生线程支持的环境中工作。
在Java 1.1中，绿色线程（至少在 Solaris 上）是JVM 中使用的唯一一种线程模型。 由于绿色线程和原生线程比起来在使用时有一些限制，随后的 Java 版本中放弃了绿色线程，转而使用native threads。[2]

在 Java1.2 之后. Linux中的JVM是基于pthread实现的，即 现在的Java中线程的本质，其实就是操作系统中的线程。

参考

• https://zhuanlan.zhihu.com/p/133275094
• https://zhuanlan.zhihu.com/p/172471249
• https://www.zhihu.com/question/50185085
• https://www.zhihu.com/question/342261454/answer/800062080

对比

map VS unordered_map

• map
  • 底层为红黑树
• unordered_map
  • 底层为哈希表

对比

• map 有序，unordered_map 无序
• unordered_map 查找效率更高

addr2line

1

addr2line -f -e path/to/binary <address>

nm

列出对象文件中的符号

1
2

nm libssl.a 
nm -an libssl.a 

1
2

# 安装
$ yum install binutils

ldd

1
2
3
4
5
6
7
8

$ ldd main
	linux-vdso.so.1 (0x00007ffe5458c000)
	libresolv.so.2 => /lib/x86_64-linux-gnu/libresolv.so.2 (0x00007f74d9d1a000)
	libm.so.6 => /lib/x86_64-linux-gnu/libm.so.6 (0x00007f74d9c33000)
	libstdc++.so.6 => /lib/x86_64-linux-gnu/libstdc++.so.6 (0x00007f74d9a07000)
	libgcc_s.so.1 => /lib/x86_64-linux-gnu/libgcc_s.so.1 (0x00007f74d99e7000)
	libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007f74d97be000)
	/lib64/ld-linux-x86-64.so.2 (0x00007f74dc649000)

strings

strings 程序的主要功能是找出文件（包括文本文件、二进制文件等）内容中的可打印字符串。

1

strings /usr/lib/libstdc++.so.6 | grep GLIBCXX

简述

• Function<A, B> : 一个参数 + 返回值
• Supplier<A> : 无参数 + 返回值

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

public class FunctionTest {

    // Function<A, B> : 一个参数 + 返回值
    // Supplier<A>    : 无参数 + 返回值
    static class FC implements Function<String, String> {
        private final Function<String, String> f;
        private final Supplier<Long> spl;
        private final Function<String[], String> mf;

        public FC(Function<String, String> f,
                  Supplier<Long> spl,
                  Function<String[], String> mf) {
            this.f = f;
            this.spl = spl;
            this.mf = mf;
        }

        @Override
        public String apply(String s) {
            return spl.get() + " " + f.apply(s);
        }

        public String rmf(String[] ss) {
            return mf.apply(ss);
        }
    }

    public static void main(String[] args) {
        FC fc = new FC((item) -> "Hello " + item,
                System::currentTimeMillis,
                (ags) -> String.join(",", ags));
        System.out.println(fc.apply(fc.rmf(new String[]{"Tom", "Kitty"})));
    }
}

锁分类

• 公平锁 / 非公平锁
• 可重入锁 / 不可重入锁
• 独享锁 / 共享锁
• 互斥锁 / 读写锁
• 乐观锁 / 悲观锁
• 分段锁
• 偏向锁 / 轻量级锁 / 重量级锁
• 自旋锁

公平锁 & 非公平锁

以多线程申请及获取锁的顺序区分，先申请先得则为公平锁。非公平锁容易造成饥饿现象，但吞吐量优于公平锁（公平锁实现会先判断是否有前驱线程在等待）。

ReentrantLock 可通过构造参数指定为公平锁，默认非公平锁，基于AQS实现线程调度。

synchronized 没有线程调度机制，所以为非公平锁。

可重入锁 & 不可重入锁

可重入锁可重复可递归调用的锁，行为为一个线程可以对同一对象多次加锁。

独享锁 & 共享锁

独享锁一次只能被一个线程加锁，共享锁可被多个线程加锁。

互斥锁 & 读写锁

互斥锁

访问临界资源前加锁，访问后解锁。加锁后，再次加锁会被阻塞，直到当前进程解锁。同一时间，只有一个线程，能够访问被互斥锁保护的资源。

读写锁

读写锁由read模式的共享锁和write模式的互斥锁组成，读写锁有三种状态，读加锁状态、写加锁状态、不加锁状态。

乐观锁 & 悲观锁

悲观锁

总是假设最坏情况，每次去拿数据的时候都认为别人会修改，所以每次在拿数据的时候都会上锁，这样别人想拿这个数据就会阻塞直到它拿到锁（共享资源每次只给一个线程使用，其它线程阻塞，用完后再把资源转让给其它线程）。传统的关系型数据库里边就用到了很多这种锁机制，比如行锁，表锁等，读锁，写锁等，都是在做操作之前先上锁。Java中synchronized和ReentrantLock等独占锁就是悲观锁思想的实现。

乐观锁

总是假设最好的情况，每次去拿数据的时候都认为别人不会修改，所以不会上锁，但是在更新的时候会判断一下在此期间别人有没有去更新这个数据，可以使用版本号机制和CAS算法实现。乐观锁适用于多读的应用类型，这样可以提高吞吐量，像数据库提供的类似于write_condition机制，其实都是提供的乐观锁。在Java中java.util.concurrent.atomic包下面的原子变量类就是使用了乐观锁的一种实现方式CAS实现的。

分段锁

分段锁是一种锁的设计，通过减小锁的粒度，提升多并发程序性能。

偏向锁 & 轻量级锁 & 重量级锁

JVM为了提高锁的获取与释放效率，在对象头中添加字段，使得对象监视器可获取其锁的状态，锁的状态如下。

• 无锁状态
• 偏向锁状态
• 轻量级锁状态
• 重量级锁状态

偏向锁

偏向锁是指一段同步代码一直被一个线程所访问，那么该线程会自动获取锁。降低获取锁的代价。

轻量级

轻量级锁是指当锁是偏向锁的时候，被另一个线程所访问，偏向锁就会升级为轻量级锁，其他线程会通过自旋的形式尝试获取锁，不会阻塞，提高性能。

重量级锁

重量级锁是指当锁为轻量级锁的时候，另一个线程虽然是自旋，但自旋不会一直持续下去，当自旋一定次数的时候，还没有获取到锁，就会进入阻塞，该锁膨胀为重量级锁。重量级锁会让其他申请的线程进入阻塞，性能降低。

自旋锁

自旋锁（spinlock）：是指当一个线程在获取锁的时候，如果锁已经被其它线程获取，那么该线程将循环等待，然后不断的判断锁是否能够被成功获取，直到获取到锁才会退出循环。

它是为实现保护共享资源而提出一种锁机制。其实，自旋锁与互斥锁比较类似，它们都是为了解决对某项资源的互斥使用。无论是互斥锁，还是自旋锁，在任何时刻，最多只能有一个保持者，也就说，在任何时刻最多只能有一个执行单元获得锁。但是两者在调度机制上略有不同。对于互斥锁，如果资源已经被占用，资源申请者只能进入睡眠状态。但是自旋锁不会引起调用者睡眠，如果自旋锁已经被别的执行单元保持，调用者就一直循环在那里看是否该自旋锁的保持者已经释放了锁，”自旋”一词就是因此而得名。

实现示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public class SpinLock {
   private AtomicReference<Thread> cas = new AtomicReference<Thread>();
   public void lock() {
       Thread current = Thread.currentThread();
       // 利用CAS
       while (!cas.compareAndSet(null, current)) {
           // DO nothing
       }
   }
   public void unlock() {
       Thread current = Thread.currentThread();
       cas.compareAndSet(current, null);
   }
}

lock() 方法利用的CAS，当第一个线程A获取锁的时候，能够成功获取到，不会进入while循环，如果此时线程A没有释放锁，另一个线程B又来获取锁，此时由于不满足CAS，所以就会进入while循环，不断判断是否满足CAS，直到A线程调用unlock方法释放了该锁。

问题

1、如果某个线程持有锁的时间过长，就会导致其它等待获取锁的线程进入循环等待，消耗CPU。使用不当会造成CPU使用率极高。
2、上面Java实现的自旋锁不是公平的，即无法满足等待时间最长的线程优先获取锁。不公平的锁就会存在“线程饥饿”问题。

优点

1. 自旋锁不会使线程状态发生切换，一直处于用户态，即线程一直都是active的；不会使线程进入阻塞状态，减少了不必要的上下文切换，执行速度快
2. 非自旋锁在获取不到锁的时候会进入阻塞状态，从而进入内核态，当获取到锁的时候需要从内核态恢复，需要线程上下文切换。（线程被阻塞后便进入内核（Linux）调度状态，这个会导致系统在用户态与内核态之间来回切换，严重影响锁的性能）

总结

1. 自旋锁：线程获取锁的时候，如果锁被其他线程持有，则当前线程将循环等待，直到获取到锁。
2. 自旋锁等待期间，线程的状态不会改变，线程一直是用户态并且是活动的(active)。
3. 自旋锁如果持有锁的时间太长，则会导致其它等待获取锁的线程耗尽CPU。
4. 自旋锁本身无法保证公平性，同时也无法保证可重入性。
5. 基于自旋锁，可以实现具备公平性和可重入性质的锁。

关键词

• CAS
  • Compare And Swap（比较并交换）
  • AQS 中使用 CAS 设置 State
• AQS
  • AbstractQueuedSynchronizer 的简称
  • 提供了原子式管理同步状态、阻塞和唤醒线程功能以及队列模型的简单框架
• CLH
  • CLH（Craig, Landin, and Hagersten locks）：是一个自旋锁，能确保无饥饿性，提供先来先服务的公平性。
• ReentrantLock
  • 可重入锁，线程可对一个临界资源重复加锁
• synchronized
  • 可重入独享锁
• volatile
• ReeReentrantLock
  • 可重入独享锁，AQS
• ReentrantReadWriteLock
  • 可重入共享锁，AQS

synchronized

jdk 1.5 之前，synchronized 是一种独占式的重量级锁，底层使用系统的 mutex lock 实现。jdk 1.6 之后，做了大量优化，加入了CAS，轻量级锁和偏向锁的功能，性能上已经跟ReentrantLock相差无几。

同步代码块

monitorenter指令插入到同步代码块的开始位置，monitorexit指令插入到同步代码块的结束位置，JVM需要保证每一个monitorenter都有一个monitorexit与之相对应。任何对象都有一个monitor与之相关联，当且一个monitor被持有之后，他将处于锁定状态。线程执行到monitorenter指令时，将会尝试获取对象所对应的monitor所有权，即尝试获取对象的锁。

同步方法

synchronized方法则会被翻译成普通的方法调用和返回指令如:invokevirtual、areturn指令，有一个ACC_SYNCHRONIZED标志，JVM就是通过该标志来判断是否需要实现同步的，具体过程为：当线程执行该方法时，会先检查该方法是否标志了ACC_SYNCHRONIZED，如果标志了，线程需要先获取monitor，获取成功后才能调用方法，方法执行完后再释放monitor，在该线程调用方法期间，其他线程无法获取同一个monitor对象。其实本质上和synchronized块相同，只是同步方法是用一种隐式的方式来实现，而不是显式地通过字节码指令。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

public class TestLock {
    private static final ExecutorService es = Executors.newFixedThreadPool(16);

    void sleep() {
        try {
            Thread.sleep(5000);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    void fe() {
        System.out.println("fe: " + LocalDateTime.now());
        sleep();
    }

    synchronized void fd() {
        System.out.println("fd: " + LocalDateTime.now());
    }

    synchronized void fc() {
        System.out.println("fc: " + LocalDateTime.now());
    }

    synchronized void fb() {
        System.out.println("fb: " + LocalDateTime.now());
        fc();
        es.submit(this::fd);
        sleep();
    }

    synchronized void fa() {
        System.out.println("fa: " + LocalDateTime.now());
        sleep();
    }

    public static void main(String[] args) {
        TestLock tl = new TestLock();
        es.submit(tl::fa);
        es.submit(tl::fb);
        es.submit(tl::fe);
    }
}

// output
fe: 2021-03-11T19:57:10.698877
fa: 2021-03-11T19:57:10.698912
fb: 2021-03-11T19:57:15.703141
fc: 2021-03-11T19:57:15.703565
fd: 2021-03-11T19:57:20.708362
  
// description
1. 普通同步方法，锁粒度为当前实例对象
2. synchronized 为可重入锁，在 fb 中调用 fc 需要重复为当前实例对象上锁
3. 重入锁不适用于子线程

AQS

AQS：AbstractQuenedSynchronizer抽象的队列式同步器。是除了java自带的synchronized关键字之外的锁机制。

核心思想，如果被请求的共享资源空闲，那么将当前请求资源的线程设置为有效的工作线程，将共享资源设置为锁定状态；如果共享资源被占用，就需要一定的阻塞等待机制来保证锁分配。这个机制主要用的是CLH队列的变体实现的，将暂时获取不到锁的线程加入到队列中。

AQS是将每一条请求共享资源的线程封装成一个CLH锁队列的一个结点（Node），来实现锁的分配。

CLH：Craig、Landin and Hagersten队列，是单向链表，AQS中的队列是CLH变体的虚拟双向队列（FIFO），AQS是通过将每条请求共享资源的线程封装成一个节点来实现锁的分配。

AQS使用一个volatile的int类型的成员变量来表示同步状态，通过内置的FIFO队列来完成资源获取的排队工作，通过CAS完成对State值的修改。

CAS

CAS是英文单词Compare and Swap（比较并交换），是一种有名的无锁算法。无锁编程，即不使用锁的情况下实现多线程之间的变量同步，也就是在没有线程被阻塞的情况下实现变量的同步，所以也叫非阻塞同步（Non-blocking Synchronization）。CAS算法涉及到三个操作数

1. 需要读写的内存值 V

2. 进行比较的值 A

3. 拟写入的新值 B

更新一个变量的时候，只有当变量的预期值A和内存地址V当中的实际值相同时，才会将内存地址V对应的值修改为B，否则不会执行任何操作。一般情况下是一个自旋操作，即不断的重试。

指令重排

为了提高程序执行的性能，编译器和执行器（处理器）通常会对指令做一些优化（重排序）。

volatile

并发编程的三大特性，原子性、可见性、有序性。synchronized可保证三大特性（保护的代码块通知只能有一个线程执行，单线程没有指令重排的问题），volatile 可以保证可见性（把工作内存中的最新变量强制刷新至主存）和有序性（编译器在生成字节码时，在指令序列中添加“内存屏障”来禁止指令重排序）。

对比

ReentrantLock VS Synchronized

关联

• ConcurrentHashMap
  • Jdk 1.7 VS Jdk 1.8

ConcurrentHashMap

JDK 1.7

Jdk 1.7 中，HashMap 底层为数组+链表实现，ConcurrentHashMap与其不同的是，添加了 Segment 作为数组+链表的上层结构，Concurrent 继承 ReentrantLock，对 Segment 加锁，实现不同 Segment 可以同时读写。在写入获取key所在Segment是需要保证可见性，ConcurrentHashMap使用如下方法保证可见性，取得最新的Segment。

1

Segment<K,V> s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)

写入 Segment 时，需要获取锁，先使用自旋锁，超过重试次数后，通过 lock 获取锁（会被阻塞，切换至内核态等待）。

JDK 1.8

Jdk 1.8 中的 ConcurrentHashMap 刨除了 Segment 的设计，直接 <大数组+[链表|红黑树]> 的方式，如果数组对应的链表超过一定阈值后，转换为红黑树。大数组使用 volatile 关键字修饰。

对于写操作，key对应的数组元素，使用 synchronized 关键字申请锁（当然，如果为null，则不需要加锁），然后进行操作。

对于读操作，数组使用 volatile 保证可见性，数组的每个元素为Node实例（jdk 1.7 为 HashEntry），他的 key 和 hash 值都使用 final 修饰，无需担心可见性。value 和下一个元素的引用由 volatile 修饰，保证可见性。

1
2
3
4
5
6

static class Node<K,V> implements Map.Entry<K,V> {
  final int hash;
  final K key;
  volatile V val;
  volatile Node<K,V> next;
}

对于 key 对应的数组元素的可见性，使用 Unsafe 的 getObjectVolatile 方法保证。

1
2
3

static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
  return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}

mutex lock

所谓锁，在计算机中，本质是内存中的一块空间，其值被赋予了加锁/未加锁的含义，其底层实现，是基于计算机系统中的原子操作。

mutex lock 核心包含两点。

• Compare And Set
  • 互斥锁是对临界区的保护，能否进入临界区即能否获取到锁，思路都是判断并置位一个标志位，这个标志位本身可以是一个普通的内存变量，关键在于，对于这个变量的"判断并置位"操作需要是原子的。
  • 计算机实现原子操作，对于单核机器，关中断防止调度即可；多核理论上可使用 spinlock 保护，实际一般通过原子汇编语言实现，比如x86的tsl指令（test and set），可以用一条“无法继续分割的”汇编指令实现判断变量值并根据是否为0进行置位，具体这个指令实现原子性一般通过锁总线实现，也就是我执行这条指令时，其它核都不能访问这个地址了。
• 根据所是否获得，决定执行策略
  • 如果锁持有，则继续运行
  • 如果所没有获取到，常规做法是将当前任务挂起，并附在 mutex 变量对应的链表上，一旦锁被释放，查找锁上挂起的任务并唤醒

参考

• https://www.cnblogs.com/jyroy/p/11365935.html
• https://mp.weixin.qq.com/s/KxYZlBu0ctB50XtkbfB4iQ
• https://www.cnblogs.com/hustzzl/p/9343797.html
• https://www.cnblogs.com/barrywxx/p/8678698.html
• https://www.cnblogs.com/xckxue/p/8685675.html
• https://blog.csdn.net/liao0801_123/article/details/85888657
• https://stackoverflow.com/questions/7855700/why-is-volatile-used-in-double-checked-locking
• https://tech.meituan.com/2019/12/05/aqs-theory-and-apply.html
• https://mp.weixin.qq.com/s?__biz=MjM5NjQ5MTI5OA==&mid=2651749434&idx=3&sn=5ffa63ad47fe166f2f1a9f604ed10091
• http://www.jasongj.com/java/concurrenthashmap/
• https://www.zhihu.com/question/332113890/answer/762392859

Executor

1
2
3
4
5
6
7
8
9
10
11
12

// 创建 executor
private static final ExecutorService executor = Executors.newFixedThreadPool(8);

// 异步提交 
executor.submit(Callable<V> / Runnable);
executor.execute(Runnable);

// 同步等待
executor.invokeAll(Collection<Callable<V>>);
  
// shutdown 
executor.shutdown();

Tips

• submit VS execute
  • 参数不同，submit 可接受 Callable 和 Runable 类型变量，execute 只接受 Runable
  • submit 提交任务后可在主线程同步等待，execute 由于没有返回值，则不行
  • submit 可以通过 Future.get() 在主线程捕获异常，execute 则不行