Semaphore

• 用于限制并发访问资源线程的个数

• 基于AQS，初始化是为state赋值最大并发数，调用acquire()时即是cas将state-1，当state小于零时，令牌不足，将线程包装成node结点会入队列，然后挂起

• 有公平和非公平两个构造方法

AbstractQueuedSynchronizer

• 实现了cas方式竞争共享资源时的线程阻塞等待唤醒机制

• AQS提供了两种资源共享方式1.独占：只有一个线程能获取资源（公平，不公平）2.共享：多个进程可获取资源

• AQS使用了模板方法模式，子类只需要实现tryAcquire()和tryRelease()，等待队列的维护不需要关心

• AQS使用了CLH 队列:包括sync queue和condition queue，后者只有使用condition的时候才会产生

• 持有一个volatile int state代表共享资源，state =1 表示被占用（提供了CAS 更新 state 的方法），其他线程来加锁会失败，加锁失败的线程会放入等待队列（被Unsafe.park()挂起）

• 等待队列的队头是独占资源的线程。队列是双向链表

AtomicInteger

• 线程安全的int值，为了避免在一个变量上使用锁实现同步，这样太重了

• 在高并发的情况下，每次值成功更新了都需要将值刷到主存

• 自增使用cas+自旋+volatile

    public final int incrementAndGet() {
        for (;;) {// 自旋
            int current = get();
            int next = current + 1;
            if (compareAndSet(current, next))// cas
                return next;
        }
    }

AtomicIntegerArray

• 线程安全整形数组

• 内部持有 final int[] array，保证了使用时已经初始化，并且引用不能改变

• 对数组的操作退化为对单个元素的操作，因为数组的内存模型是连续的，并且每个元素所占空间一样大，

• 使用Unsafe带有volatile的方法进行对单个元素赋值。

AtomicReference

• 提供对象引用非阻塞原子性并发读写

• 对象引用是一个4字节的数字，代表着堆内存中的一个地址

CopyOnWriteArrayList

• 实现了线程安全的读写并发，读读并发，但不能实现写写并发（上锁了，synchronized），因为他们操纵是不同的副本

• 使用不可变 Object[] 作为容器

• 写时复制数组，写入新数组，引用指向新数组。加锁防止一次写操作导致复制了多个数组副本

• 读操作就是普通的获取数组某元素，

• 适合读多写少，因为写需要复制数组，耗时

• 适合集合不大，因为写时要复制数组，耗时，耗内存

• 实时性要求不高，因为可能会读到旧数据。(对新数组写，对数组读)

• 采用快照遍历，即遍历发起时形成一张当前数组的快照，并且迭代器不允许删除，新增元素。不会发生 ConcurrentModificationException，但可能实时性不够。

• 适用于作为观察者的容器

ArrayBlockingQueue

• 大小固定的，线程安全的顺序队列，不能读读，读写，写写并发。

• 使用Object[]作为容器，环形数组。比复制拷贝效率高。

• 存取使用同一把锁 ReentrantLock 保证线程安全+2个condition（写操作可能在notFull条件上阻塞，读操作可能在notEmpty上阻塞）

• 遍历支持remove及并发读写。

• 适用于控制内存大小的生产者消费者模式，队列满，则阻塞生产者/有限等待，队列空则阻塞消费者/有限等待。

• 适用于做缓存，缓存有大小限制，缓存是生产者消费者模型，多线程场景下需考虑线程安全。

LinkedBlockingQueue

• 线程安全的链队列，实现读写并发，不能读读，写写并发

• 存取用两把不同的 ReentrantLock，适用于读写高并发场景。

• 可实现并行存取，速度比 ArrayBlockingQueue 快，但有额外的Node结点对象的创建和销毁，可能引发 gc，若消费速度远低于生产速度，则内存膨胀

SynchronousQueue

• 以非阻塞线程安全的方式将元素从一个生产线程递交给消费线程

• 适用于生产的内容总是可以被瞬间消费的场景，比如容量为 Int.MAX_VALUE 的线程池，即当新请求到来时，总是可以找到新得线程来执行请求，不管是老的空闲线程，还是新建线程。

• 存储结构是一个链，使用 cas + 自旋的方式实现线程安全

PriorityBlockingQueue

• 使用 Object[] 作为容器实现堆

• 使用 ReentrantLock 保证线程安全，读和取同一把锁

• 每次存取会引发排序，使用堆排序提高性能

1. 每次写，都写到数组末尾，然后堆向上调整

1. 每次读都读取数组头，并将数组末尾元素放到数组头。然后执行一次向下调整

ConcurrentLinkedQueue

• 是一个链式队列，使用非阻塞方式实现并发读写的线程安全，而是使用轮询+CAS保证了修改头尾指针的线程安全

• 存储结构是带头尾指针的单链表。

• 头尾指针和结点next域都使用 volatile 保证可见性。

• 出队时，通过 cas 保证结点 item 域置空的线程安全，更新头指针也使用了 cas。

• 入队时，通过 cas 保证结点 next 域指向新结点的线程安全，更新尾指针也使用了 cas。

• 出于性能考虑，头尾指针的更新都是延迟的。每插入两个结点，更新一下尾指针，每取出两个结点，更新一下头指针。

• 适用于生产者消费者场景

• 入队算法：总是从当前tail指向的尾部向后寻找真正的尾部（因为tail更新滞后，并且可能被另一个入队线程抢占），找到后通过cas值next域

ConcurrentHashMap

• 1.7 使用的是开散列表，数组+链表

• 1.7 Segment 数组，Segment 是一个 ReentrantLock，分段锁，并发数是 Segment 的数量。每个 Segment 持有一个 Entry 数组（桶）。（一个entry就是一条链）

• 1.7 定位一个元素需要两次hash，先定位到 Segment 再定位到元素所在链表头。

• 1.7 put()先尝试非阻塞的获取锁，失败则自旋重试，并计算出对应桶的位置，到达最大尝试次数后阻塞式的获取。

• 1.7 ConcurrentHashMap.get()不需要上锁是因为键值对实体中将value声明成了volatile，能够在线程之间保持可见性

• 1.7 如果ConcurrentHashMap的元素数量增加导致ConrruentHashMap需要扩容，ConcurrentHashMap不会增加Segment的数量，而只会增加Segment中链表数组的容量大小，扩容的时候首先会创建一个两倍于原容量的数组，然后将原数组里的元素进行再 hash 后插入到新的数组里

• 1.7 遍历链表是个相对耗时的操作

• 1.8 将重入锁改成synchronized，因为它被优化过了

• 1.8 也是开散列表，数组+链表（或者红黑树），当链表长度大于8时，则将链表转换为红黑树，增加查找效率

• 1.8 使用cas方式保证只有一个线程初始化成功

• 1.8 put操作：对key进行hash得到数组索引，若数组未初始化则初始化，如果索引位置为null 则直接cas写（失败则自旋保持成功），（后面的部分synchronize了）如果索引位置为链头指针，则进行链插入，往后遍历找到相同的key 则覆盖，否则链尾插入，若索引位置是红黑树，则进行红黑树插入。

• 1.8 锁的粒度更细了，一个桶一个锁。

• 1.8 Node.next 用volatile修饰

红黑树

• 二叉树是一个父节点有两个子节点的递归结构

• 二叉排序树是一种特殊的二叉树，它规定左孩子 < 父亲 < 右孩子，它解决了二叉树退化为单链表的情况（查找时间复杂度退化为O(n)）

• 平衡二叉排序树是一种特殊的二叉排序树。它规定每一个结点的左右子树高度差不大于1

• 红黑树是没有那么严格的平衡二叉排序树。因为频繁的调整子树是耗时的。

• 二叉排序树是二分查找，最大查找次数为树高度

• 红黑树插入结点后通过变色和旋转来保持红黑树的平衡。保证了没有任何一条路径会比其他路径长出两倍。

ConcurrentModificationException

• 当遍历数组的同时删除其中元素就会发生这个异常，这叫fast-fail机制。

• 因为调用next()时会检查 modCount和expectModCount是否一致，不一致则抛这个异常。

• 但单线程下如何解决这个问题：使用iterator.remove，他会同步modCount和expectModeCount

ThreadPoolExecutor

• 这是java的线程池。

• ThreadPoolExecutor构造参数如下：

1. 核心线程数：线程池中一直存活的线程数量，当新的任务请求到来时,如果线程池中线程数小于核心线程数,则会新建线程,默认情况下核心线程会一直存活,只有当allowCoreThreadTimeOut设置为true时且发生超时才会被销毁

2. 最大线程数,线程池中线程的上限

3. keepAlive：非核心线程允许空闲的最大时长，超过空闲时间则会被销毁(当池中线程数>=核心线程数时创建出来的线程都是非核心线程)

• ThreadPoolExecutor线程池管理策略

if 线程池中正在运行的线程数 < corePoolSize
  {新建线程来处理任务(即使线程池中有线程处于空闲状态)}
else if 线程池中正在运行的线程数 >= corePoolSize
  {
  if 缓冲队列未满
    任务被放入缓冲队列
  else 缓冲队列满
    if maximumPoolSize > 线程池中正在运行的线程数 > corePoolSize
      新建线程来处理任务 此时的任务会被立即执行
    else if 线程池中正在运行的线程数 = maximunPoolSize
      通过handler所指定的策略来处理此任务
        拒绝策略(丢弃策略)
          ThreadPoolExecutor.AbortPolicy 悄悄地丢弃一个任务
          ThreadPoolExecutor.DiscardOldestPolicy 丢弃最旧的任务，重新提交最新的
          ThreadPoolExecutor.CallerRunsPolicy 在调用者的线程中执行被拒绝的任务
          ThreadPoolExecutor.DiscardPolicy() 丢弃当前任务
  }

网络

网络分层的好处是下层的可重用性，tcp不需要知道它传输的是http还是ftp亦或是SSH。

1. 物理层

• 二进制在物理媒体上传输

2. 数据链路层

在物理层的基础上提供差错校验。

3. 网络层（ip）

为数据包路由

4. 传输层（tcp，udp）

提供端到端接口

tcp

• 传输控制协议，是传输层协议，解决数据如何传输，是面向连接的，可靠的点到点传输协议。

• tcp头包括 sequence number（32位） 用于标识报文中第一个字节在整个数据流中的序号，确保有序。

• tcp头包括 ack number（32位），表示对上一个接收到的sequence number的确认，解决丢包。只有当ack位为1时才有效

• tcp 头部包含滑动窗口大小

• tcp 头部包含 tcp flag，有6个标志位 URG，ACK，PSH，RST，SYN，FIN

• tcp 头部包含两个16位的端口号（源+目的）

• tcp是基于字节流的

• 采用确认和超时重传策略保证可靠传输

• 确认：接收方检测出帧出错是不会返回确认帧并直接丢弃该帧

• 超时重传：发送方发送数据报后启动倒计时，若规定时间内未收到确认才重传数据报

• 提供拥塞控制和流量控制

• 采用大小可变的滑动窗口实现流量控制，窗口大小即是发送方发送但未收到确认的数据报数量

• 慢启动：每个rtt将滑动窗口翻倍。

• 拥塞控制对链接是独立的

• 但拥塞控制会导致tcp队头阻塞（tcp必须接收到完整正确顺序的数据包后才能提交给上层），使得单路 http/2 的速度没有多路 http/1 的快

• TCP通信过程太复杂并且开销大，一次TCP交换需要9个包： 三个连接包，四个断开包，一个request包，一个响应包。

• UDP通信过程简单，只需要一个查询包和一个响应包。

tcp三次握手建立连接

1. 发送方请求建立连接Syn报文，syn位置1(表示链接建立请求) ack位置0，seq number =x

2. 接收方确认请求 syn位置1，ack位置1，seq number = y  ack number = x+1

3. 发送方确认的确认 ack number = y+1

• 为啥不能两次：防止超时的连接请求报文到达服务器再次建立连接。

tcp四次挥手释放连接

• 4次挥手：发送方请求释放连接（Fin报文）-> 接收方确认（ACK置1）-> 接收方请求释放连接（Fin报文）-> 发送方确认-客户端等待 2MSL（报文最大生存时间） 的时间后依然没有收到回复（服务端没收到ack，则服务端会重新发送fin），则证明服务端已正常关闭，那么客户端也可以关闭连接了

• 为啥挥手要四次，因为TCP全双工，客户端请求释放连接时，只表示客户端没东西发了，但服务器还有数据要返回。

tcp粘包，tcp分包

1. 半包：如果数据包太大，导致服务器没有接收完整的包

2. 粘包：tcp基于字节流，不关心上层传输的具体内容，在一个tcp报文中可能存在多个http包（发送端粘包：http包太小，tcp为了提高效率，所以粘包，接收端粘包：接收端没有及时处理接收缓冲区的数据，读取时出现粘包）

3. 分包：tcp基于字节流，tcp不关心上层传输的具体内容，一个大的http包可能被分在多个tcp报文上（发送http太大）

• 粘包分包解决方案：定长消息，用特殊字符标记消息边界，将消息长度写在消息头中

tcp心跳包

• 通信双方处于idle状态时确保长链接的有效性，需要发送的特殊数据包给对方（ping），接收方给予回复（pong）

• tcp自带心态机制SO_KEEPALIVE，但不够灵活，所以在应用层上实现心跳

• Netty 使用  IdleStateHandler 根据超时时间监听读写事件，若发生超时则会触发回调，这个时候可以发送心跳包

socket

• 套接字 = {传输层协议,源地址,源端口,目标地址,目标端口}，其中协议可以是tcp或udp，是不同主机进程间通信的端点

udp

• 用户数据包协议

• UDP提供的是无连接 无确认 不可靠服务的点到多点传输协议

• udp是基于报文的

• 发送前无需握手，发送完无需释放连接，传输效率高

• 每个数据包独立发送，不同数据包可能传输路径可能不同

• 没有拥塞控制

• 有差错校验，对udp头部和数据段都进行校验，服务端通过校验和发现出错时直接丢弃

• udp 依赖网络层的ip，udp数据包被包在ip数据包外层

5. 应用层

https

• https 是安全的 http，它 = http + ssl（Secure Sockets Layer）

• 是应用层协议，解决如何封装数据

• 无状态协议，服务器对用户操作没有记忆

• http 1.1 开始有keep-alive，保持链接，网页打开后，客户端和服务器的连接不会断开而是保持一段时间，为了效率（Connection：keep-alive，请求头部的该字段决定了链接是否会复用）

• 明文通信，可能被窃听；不验证身份，可能被劫持；无法验证报文完整性，可能被篡改。

• HTTP协议使用默认80端口，HTTPS协议使用443端口

• http1.1 新增了pipeline，多个http资源可以并发地在一条tcp链接上发送（发送方不需要等待第一个资源确认了才发送第二个资源）。但接收方只能串行的处理响应，一个慢响应会阻塞所有快请求向上层提交（管道解决了请求的队头阻塞）

• 证书: 是服务器下发给客户端的，客户端用证书验证服务端身份。证书需要购买

• 证书包含：认证机构(CA)信息,公钥,域名,有效期,指纹(对证书进行hash运算,即证书摘要),指纹算法,数字签名(CA私钥加密的指纹)等

HTTP2.0

• 1.0 每个http请求都要重新建立一条tcp链接，结束时要关闭链接，临时链接。

• 1.0 不压缩header，且每次通信都要重复发送head

• 1.0 不支持请求优先级

• 1.0 必须串行的地完成地发送资源（造成队头阻塞）

• 1.1 允许持久链接，接收方只能串行地处理不同请求，两个请求生命周期不能重叠，因为接收方无法确认数据的开始和结束（有效负荷字段写在header中），这会造成队头阻塞，多个并行请求需建立多条 tcp链接，无法复用。关闭链接只要在头部带上Connection:Close

• 2.0 支持header压缩，通讯双方缓存一个 header field 表，避免重复 header 传输

• 2.0 多路复用，将数据流分解成更小的帧（通过在头部廷加stream id，和帧大小），不同数据流的帧可以交错在一条tcp连接上发送，再根据所属流重新组装，实现了多请求并行传输的效果（时间片），解决了http层的队头阻塞（减轻了服务端的压力，每个客户端只建立了一条链接，服务器可以给更多的客户端建立连接）

• 2.0 支持优先级

加密解密

加密算法分为两类：对称加密和非对称加密。

• 对称加密：加密和解密用的都是相同的秘钥，优点是速度快，缺点是安全性低。常见的对称加密算法有DES、AES等等。

• 非对称加密：非对称加密有一个秘钥对，分为公钥和私钥。一般来说，私钥自己持有，公钥可以公开给对方，优点是安全性比对称加密高，缺点是数据传输效率比对称加密低。采用公钥加密的信息只有对应的私钥可以解密。常见的非对称加密包括RSA等。

数字摘要

• 是明文摘要成128位密文的过程，比如MD5，SHA1

数字签名

• 是用于验证信息完整性的和身份验证。

• 发送方将内容摘要并用私钥加密并发送，接收方用公钥解密摘要，再对原文求摘要，比对两个摘要，若相同则未被篡改

数字证书

• 是为了解决公钥置信的问题、

TLS

• 是 ssl3.0 的后续版本

• 分为 tls记录和tls握手

• tls 实现了加密数据，验证数据完整性，认证身份

tls握手过程

是一个借助于数字证书协商出对称加密密钥的过程

1. 客户端发出请求，说明支持的协议，客户端生成的随机数，支持的加密方法

2. 服务端返回证书，服务端生成的随机数

3. 客户端验证证书

4. 客户端使用证书中的公钥加密另一个新得随机数。并发送给服务器

5. 生成会话密钥：客户端和服务器分别用三个随机数生成相同的对称密钥

6. 服务器通知握手结束，之后就通过对称密钥通信

• 验证过程:

1. 客户端 TLS 解析证书

2. 证书是否过期

3. CA是否可靠(查询信任的本地根证书)

4. 证书是否被篡改(用户使用CA根公钥解密签名得到原始指纹,再对证书使用指纹算法得到新指纹,两指纹若不一样,则被篡改)

5. 服务器域名和证书上的域名是否匹配

QUIC

• quic建立在UDP之上，但实现了可靠传输，它更应是TCP 2.0，它包含tcp的所有特性 ：可靠性，拥塞控制，流量控制。

• quic 将 http2的流和帧的概念下移到了传输层，给每个数据流一个stream id，以及跟踪该字节流的字节范围（比如包1是从0-200，包2是从201-300），这将不能保证数据包的有序性，单个资源流的有序，多个流的顺序无法保证（比如服务器发送资源1.1-1.2-2，接收方的顺序可能是2-1.1-1.2），

队头阻塞

• 一个大的（慢的）响应会阻塞其后面的响应。

• http1.0 通过多个http链接缓解该问题

• http2.0回到单个 TCP 连接，解决队头阻塞问题。这在 HTTP/1.1 中是不可能的，因为没有办法分辨一个块属于哪个资源，或者它在哪里结束，另一个块从哪里开始。HTTP/2 非常优雅地解决了这一问题，它在资源块之前添加了帧（frames）

• http2.0解决了http层的队头阻塞。但还有tcp队头阻塞，当发生丢包，tcp会先将失序数据存在缓冲区，待重传数据到来时才按照正确的顺序提交给上层，此时丢失的包会阻塞后续包提交给上层。

• quic 将http2 流和帧的概念下移到了传输层，解决了 tcp队头阻塞

• tls队头阻塞：tls加解密是整块进行的，tls记录可能分散在多个tcp包上，若tcp丢包则tls队头阻塞，quic的解决方案是将加解密分散处理，这样会拖慢加解密速度。

一次网络请求

1. 请求dns服务器解析ip地址

2. 三次握手建立TCP链接

3. tls握手

4. 请求内容封装成http报文---tcp分包 在链路上发送出去

5. 服务器解析报文响应

6. 关闭链接，四次握手

网络优化

1. 请求预热：发送无body的head请求，提前建立好tcp，tls链接，省掉dns，tcp，tls时间

2. 统一域：不同的业务的域名在客户端发出请求之前进行合并（因为若域名不同，请求不同业务时都需要dns解析，且都需要建立不同的tcp链接），使用统一的域，将请求不同的部分往后挪到接口部分，请求到达后端SLB后进行域名还原。okhttp链接复用最多保持5个空闲链接（通过调整最大空闲请求数，一个connection在内存中5k）

3. 有了统一的域之后，可以进行网络嗅探，择优进行IP直连，app启动时，拉取域对应的ip列表，并对所有ip进行嗅探ping接口，选择其中最优的ip 最为后续请求的直连ip，不需要进行dns解析

4. 对于可靠性要求高的请求，先入库，失败后重试

5. 网络切换时，自动关闭缓存池中现有的链接（客户端网络地址发生变化，原先的链接失效）

6. 减少数据传输量，protocolBuffer，图片压缩，webp，请求合适大小的图片

7. 无网环境下， 添加强制缓存的拦截器，对请求添加cache-control:max-age:1年

OkHttp & Retrofit

Retrofit

• Retrofit 是一个 RESTful 的 HTTP 网络请求框架的封装

• Retrofit将Http请求抽象成预定义请求接口，使用运行时注解配置请求参数，通过动态代理生成请求对象 （调用Call.Factory生成OkHttp.call），并将response转换成业务数据

• 使用建造者模式，构建retrofit实例

• 使用工厂模式：Convert.Factory构建序列化/反序列化工厂，将ResponseBody转换成业务层数据，将请求转换成一个requestBody

• 使用装饰者模式：通过装饰者模式将响应回调抛到主线程，真正发起请求的是OkhttpCall，他外面又套了一层 ExecutorCallbackCall 扩展了该功能

• 使用了外观模式，create(),隐藏了动态代理生成接口实例，通过Call.Factory生成请求的细节

• Retrofit.crate()将接口请求动态代理给了ServiceMethod的invoke方法（查找接口对应的ServiceMethod对象（没找到就当场使用反射遍历接口中的注解，并生成ServiceMethod对象对应一个业务接口，接口中的参数都会成为它的成员变量，存在ConcurrentHashMap中，键是Method）），在该方法中生成retrofit的call对象（内部会生成Okhttp3的call对象并发起同步或异步请求），并调用CallAdapter将call适配成response（CallAdapter，它负责将retrofit.call 转换成业务层喜欢的消费方式（比如 observable，suspend方法））

• 特点

1. 链接池，HTTP/2复用连接

2. 默认支持GZIP，告诉服务器支持gzip压缩格式，请求添加Accept-Encoding: gzip，响应中返回Content-Encoding: gzip（使用哈夫曼算法，重复度越高压缩效果越好）

3. 响应缓存

4. 方便添加拦截器

OkHttp 调度器 Dispatcher

• 在 OkHttpClient.build 中构建

• 维护三个队列和一个线程池来并发处理网络请求，分别是同步运行队列，正在运行的异步队列，等待请求异步队列

• 持有 ExecutorService ，核心线程数为0，表示不保留空闲线程。最大线程数为 Int.max，表示随时会新建线程，使用同步队列，使得请求的生产不会被阻塞