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 保证线程安全，读和取同一把锁
- 每次存取会引发排序，使用堆排序提高性能
- 每次写，都写到数组末尾，然后堆向上调整
- 每次读都读取数组头，并将数组末尾元素放到数组头。然后执行一次向下调整
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构造参数如下：
- 核心线程数：线程池中一直存活的线程数量，当新的任务请求到来时,如果线程池中线程数小于核心线程数,则会新建线程,默认情况下核心线程会一直存活,只有当allowCoreThreadTimeOut设置为true时且发生超时才会被销毁
- 最大线程数,线程池中线程的上限
- 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三次握手建立连接
- 发送方请求建立连接Syn报文，syn位置1(表示链接建立请求) ack位置0，seq number =x
- 接收方确认请求 syn位置1，ack位置1，seq number = y ack number = x+1
- 发送方确认的确认 ack number = y+1
- 为啥不能两次：防止超时的连接请求报文到达服务器再次建立连接。
tcp四次挥手释放连接
- 4次挥手：发送方请求释放连接（Fin报文）-> 接收方确认（ACK置1）-> 接收方请求释放连接（Fin报文）-> 发送方确认-客户端等待 2MSL（报文最大生存时间） 的时间后依然没有收到回复（服务端没收到ack，则服务端会重新发送fin），则证明服务端已正常关闭，那么客户端也可以关闭连接了
- 为啥挥手要四次，因为TCP全双工，客户端请求释放连接时，只表示客户端没东西发了，但服务器还有数据要返回。
tcp粘包，tcp分包
- 半包：如果数据包太大，导致服务器没有接收完整的包
- 粘包：tcp基于字节流，不关心上层传输的具体内容，在一个tcp报文中可能存在多个http包（发送端粘包：http包太小，tcp为了提高效率，所以粘包，接收端粘包：接收端没有及时处理接收缓冲区的数据，读取时出现粘包）
- 分包：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握手过程
是一个借助于数字证书协商出对称加密密钥的过程
- 客户端发出请求，说明支持的协议，客户端生成的随机数，支持的加密方法
- 服务端返回证书，服务端生成的随机数
- 客户端验证证书
- 客户端使用证书中的公钥加密另一个新得随机数。并发送给服务器
- 生成会话密钥：客户端和服务器分别用三个随机数生成相同的对称密钥
- 服务器通知握手结束，之后就通过对称密钥通信
- 验证过程:
- 客户端 TLS 解析证书
- 证书是否过期
- CA是否可靠(查询信任的本地根证书)
- 证书是否被篡改(用户使用CA根公钥解密签名得到原始指纹,再对证书使用指纹算法得到新指纹,两指纹若不一样,则被篡改)
- 服务器域名和证书上的域名是否匹配
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的解决方案是将加解密分散处理，这样会拖慢加解密速度。
一次网络请求
- 请求dns服务器解析ip地址
- 三次握手建立TCP链接
- tls握手
- 请求内容封装成http报文---tcp分包 在链路上发送出去
- 服务器解析报文响应
- 关闭链接，四次握手
网络优化
- 请求预热：发送无body的head请求，提前建立好tcp，tls链接，省掉dns，tcp，tls时间
- 统一域：不同的业务的域名在客户端发出请求之前进行合并（因为若域名不同，请求不同业务时都需要dns解析，且都需要建立不同的tcp链接），使用统一的域，将请求不同的部分往后挪到接口部分，请求到达后端SLB后进行域名还原。okhttp链接复用最多保持5个空闲链接（通过调整最大空闲请求数，一个connection在内存中5k）
- 有了统一的域之后，可以进行网络嗅探，择优进行IP直连，app启动时，拉取域对应的ip列表，并对所有ip进行嗅探ping接口，选择其中最优的ip 最为后续请求的直连ip，不需要进行dns解析
- 对于可靠性要求高的请求，先入库，失败后重试
- 网络切换时，自动关闭缓存池中现有的链接（客户端网络地址发生变化，原先的链接失效）
- 减少数据传输量，protocolBuffer，图片压缩，webp，请求合适大小的图片
- 无网环境下， 添加强制缓存的拦截器，对请求添加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方法））
- 特点
- 链接池，HTTP/2复用连接
- 默认支持GZIP，告诉服务器支持gzip压缩格式，请求添加Accept-Encoding: gzip，响应中返回Content-Encoding: gzip（使用哈夫曼算法，重复度越高压缩效果越好）
- 响应缓存
- 方便添加拦截器
OkHttp 调度器 Dispatcher
- 在 OkHttpClient.build 中构建
- 维护三个队列和一个线程池来并发处理网络请求，分别是同步运行队列，正在运行的异步队列，等待请求异步队列
- 持有 ExecutorService ，核心线程数为0，表示不保留空闲线程。最大线程数为 Int.max，表示随时会新建线程，使用同步队列，使得请求的生产不会被阻塞
