java 相关总结

******************************

Java

******************************

Java 1.8 新特性

--》允许接口，实现默认方法，使用default关键字。

--》lambda 表达式

--》函数式编程

--》Optional 接口，防止空指针

--》Stream 接口，使用流式处理

--》LocalTime ，线程安全

1.ThreadLocal类：

--threadlocal 内部有一个 ThreadLocalMap类，其内部有个 Entry 类型的 hash Table

在setInitialValue函数中，会创建一个 ThreadlocalMap 对象，并保存在 Thread 类的

threadlocal变量中。

--当调用 set函数时，先从thread中获取 threadlocalmap 对象，将value放入到

该对象的hashtable中，放入过程是：1.获取 thread 的hash值，然后再计算所在槽，2.从该槽向后搜索

检查是否有相同的key，如果有则更新value，如果没有则检查entry 的key 是否为null，如果为null，则清理table

如果不符合以上条件，则创建新的 entry 放入到table中。

--get函数，同样是获取 map 对象，然后计算槽，如果 所在槽的entry的key与当前key不想等，则从当前槽向后开始搜索

找到key相等的entry，并返回value。

--hash值的计算，通过 nexthashcode 加上 一个 魔数值。该魔数值可以将key均匀的分散的 2^N 个槽中

该魔数被称为黄金分割，也就是 斐波那契散列

斐波那契数列：

long fibonacci(int n){

return n<2?n:fibonacci(n-1)+fibonacci(n-2)

}

--threadLocal 在多线程中是线程不安全的，在使用时要清除对象的引用，还可能产生内存泄露

在线程池中，使用threadLocal保存对象，由于线程复用，如果两个线程操作同一个threadlocal，

则threadlocal之前保存的对象，就会暴露给 第二个线程

2.LockSupport:

--jvm 通过调用 sleep，wait，park monitorenter ,使用 1-0 锁

--调用无参的park()方法，使用 互斥锁和条件变量，实现线程的阻塞和释放。先自旋更新_Event的值，如果更新成功，

调用pthread_mutex_lock获取互斥锁，获取锁成功

调用pthread_cond_wait() 等待信号。调用unpark(),会 调用pthread_cond_signal() 发送 信号，释放阻塞的线程。

--调用带时间参数的park()方法，显示检查是否有许可，如果有许可(这里使用的_counter：1-0),则直接返回。否则使用互斥锁

和条件变量，实现阻塞和释放。

3.【AQS】

AQS 内部维护着一个双端队列，header 指针指向 头部节点，tail 指针指向尾部节点【同步队列】；节点统一用Node类表示

Node类是维护一个双向链表，next指针指向下一个node，prev指针指向前一个节点。并使用volatile修饰，

nextWaiter:主要用于Condition状态的节点,等待相同条件变量的线程节点放在一个队列里面，该节点没有被声明为volatile变量，

主要是在添加节点时，已经持有锁。

还有 waitstate 表示节点的状态，Thread 表示当前节点维护的需要 park 和 upark 的线程。

节点状态：cancelled,signal,condition,propagate.

NODE 结构

+--------+

| prev | --> node 指向前面的节点

———-

| next | --> node 指向后面的节点

———

| waiter | --> conditionNode --> conditionNode 等待条件节点队列

———

#排他锁：

当线程请求锁时，如果获取失败，会创建一个新的node，放入到 队列里。在阻塞前会再次尝试一次请求锁，先判断头部节点的下一个节点是不是

自己，如果是，尝试获取锁，如果依然获取失败，则判断park前的条件，只有前节点的waitstate的状态是signal，才阻塞自己(需要保证队列中

的节点，没有取消CANCELLED状态的，否则后面阻塞的线程将无法被唤醒) 否则，自旋 继续上面的步骤。

释放锁时，获取头部节点，unpark 头部节点的下一个节点指向的线程。只有当头部节点的waitstate的状态小于0时，才进入unpark流程

如果头部节点的下一个节点已经无效，则从尾部向前搜索，找到离头部节点最近的一个node，然后upark 该node的线程。

为什么从尾部向前搜索？

为了最大概率减少丢失最新插入的node。在加入队列时，先把新node的前向指针指向 当前的尾节点，此时 尾结点并未指向新的节点node，

然后再将 tail 指针 新节点，此时遍历到尾节点发现 next 指针为null，就会漏掉 新加入的节点。(最后将 前节点的next 指向新加入的node)

#共享锁：

共享锁和排他锁共用一个队列，共享锁在doReleaseShared() 释放锁时，会从头部节点开始，不断的释放 类型为shared的节点。

而排他锁只释放下一个节点的线程

#Condition 条件变量：

在AQS中使用的是ConditionObject 实现了 Condition 接口；包含firstWaiter 头部节点,lastWaiter 尾部节点；Node.nextWaiter指向下一个节点

是单向链表结构，这个就是Condition 使用的条件队列

当调用 await() 时，将node 放入到条件队列中，调用signal() 时，将node 放入 同步队列；

所有使用AQS实现同步功能的，需重写 tryAcquire() 方法，告诉父类AQS，要不要把请求锁的线程，放入到阻塞队列。

同样，在释放锁，unpark下一个线程，需重写tryRelease，告诉父类AQS，要不要释放队列中阻塞的线程。

--Reentrianlock 获取锁或释放锁，通过 对state 加1 或 减1。

--ReentrianReadWritelock: 【state 整型 32位，分为两部分，高16位是读锁数量，低16位是写锁数量】

写锁：在请求写锁时，判断有没有读锁，如果没有读锁或者获取锁的线程是否是自己，如果不符合条件则放入队列阻塞。

读锁(共享锁)：如果写锁等于零，或者当前持有写锁的线程等于 当前线程，可以获取读锁。否则放入队列阻塞。

--countdownlatch：使用的是AQS；设state 为count值，调用await方法，进入【同步队列】，请求【共享锁】。如果state的值

不等于零，则返回-1，需要线程阻塞等待。当count个子线程 运行完成分别调用 countDown(int) 方法

使state 减 1并尝试release，直到 state 为零，唤醒等待队列中的所有的线程。

--CyclicBarrier: 使用的是 ReentrianLock 和 Condition 。

线程在调用 dowait() 方式，先调用 lock() 方法，获取锁，然后将condition 减 1，如果 condition 不为零，也就是不满足

触发条件，则会调用 condition await() 方法，进入 【条件队列】，并释放lock 锁，释放锁是为了防止死锁，其他线程无法进入

dowait()方法。当其他线程 调用 dowait() 方法，如果condition 满足触发条件，则 发送signal 信号，将【条件队列】中的node转移到

【同步队列】，根据条件unpark 线程。

--Semaphore 信号量. AQS

可用于生产者和消费者模式

获取锁：

使用的是 共享锁模式，线程调用 acquire() 方法，获取锁，获取锁成功的条件是 state 减去 count后，不能小于零。如果 条件不满足

则进入同步队列，阻塞等待。

释放锁：

调用 release方法，将 state 加上 count 值，然后 unpark 线程

4.HashMap:

1.为什么HashMap中的&位必须为奇数？

2.容量或扩容为什么是 2^n 次方？

1.如果不是2^n 的容量，则在resize后数据迁移槽的变动会很大，当容量是2^n次幂时，在重新resize时，数据的迁移会很小

2.为了方便 & 运算，计算 key的索引。2^n -1 从第0 bit 位到 n-1 位 都是 1.

3.负载因子 为什么是0.75?

1.node 分配在某个槽符合泊松分布，(Poisson分布 是用于描述单位时间、单位面积或者单位容积内某事件发现的频数分布情况，

通常用于描述稀有事件（即小概率）事件发生数的分布)。

每个槽遇到碰撞时的链表长度超过8个的概率 已经很小。也因此 在需要转换成红黑树的前提是：槽中的链表长度转换成红黑树的

阈值是 8。

4.在jdk1.7中，hashMap会发生循环引用的问题，在什么情况下发生的？1.8 是怎么解决的？

在并发时，两个线程操作同一个hashmap，当某时刻同时发生了resize 操作，迁移 数据如下：

原大小为2 ，现扩大为 4,将 A 和 B 迁移到 索引 3 处

node 迁移

1.7版本，迁移数据的代码：

for (Entry<K,V> e : table) {

// 元素不为空。遍历该位置链表

while(null != e) {

【 Entry<K,V> next = e.next;】

if (rehash) {

e.hash = null == e.key ? 0 : hash(e.key);

}

int i = indexFor(e.hash, newCapacity);

【 e.next = newTable[i]; 】// 头插法,新节点next指向该位置首节点

【 newTable[i] = e; 】

e = next; // 指向下一个节点，继续遍历

}

}

在1.8 中，resize时，将table[i] 设置为 null，断掉 引用链，然后 将数据分为 高位链表和低位链表，往尾部插入。

5. 在hashmap中，如果槽中的节点少于6个，则会把红黑树转换成链表，为什么是6个呢？这是为了避开[8]的临界点,在链表长度

是超过8的时候，会转换为树，如果依然使用8作为退化链表的临界点，则会频繁出现树与链表的转换，影响性能。

5.【红黑树】

时间复杂度lg(n)

1.根节点必须是黑色

2.叶子节点是黑色 （不包含数据的节点，也就是 NULL 节点）

3.如果节点是红色，则其子节点必须是黑色

4.对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点.

插入过程：

插入节点；将节点标记为红色；调整节点(左旋，右旋)

调整过程：x 是新插入的节点，并且标记为红色 x.color=red

case 1: x 节点的父节点p是红色；p 是 p的父节点G的【左孩子】，y 为p的兄弟节点(右兄弟)，y的颜色是【红色】

【如果p节点的兄弟节点y 为 null，则当做 黑色节点的情况处理】

此时，需要重新标记颜色：p.color=black , G.color=red, y.color=black;

已 G 节点当做新加入的节点，继续调整，因为G节点的颜色被标记为红色了，可能会破坏 特性3；

case 2: p节点是红色；p节点是G节点的【左孩子】，y是p的兄弟节点(右兄弟)，y的颜色是【黑色】

case:2.1：假设 x是 p的左节点，则重新标记颜色：p.color=black, G.color=red;右旋 G 节点，

case:2.2: 假设 x是 p的右孩子，则需要将p左旋，x节点向上移。然后再执行 case 2.1的步骤。

---- 与case 1 和 case 2 相反

case 3：x节点的父节点p 是红色，p是G的【右孩子】，y是p的兄弟节点(左兄弟)，y的颜色是【红色】

此时，重新标记颜色：p.color=black, y.color=black, G.color=red, 然后 把 G节点 当做 新插入的节点，继续调整 类似case 1

case 4: x节点的父节点p 是红色，p是G的【右孩子】，y是p的兄弟节点(左兄弟)，y的颜色是【黑色】

case:4.1: 假设 x 是p的右孩子，则重新标记颜色：p.color=black, G.color=red; 左旋 G 节点。

case:4.2: 假设 x 是p的左孩子，则需要将p右旋，x节点上移，然后执行 case 4.1 的步骤

#二叉树，会存在退化成链表的问题，为了解决该问题，引入了平衡二叉树

#平衡二叉树：左右两颗子树的高度相差不超过1；并且左右子树，也是平衡树；左节点小于父节点，右节点大于父节点

5.ConcurrentHashMap 【Synchronized lock volatile】

1.为什么要使用CAS+Synchronized取代Segment+ReentrantLock?

Synchronized 锁的是 node，将锁进行细化了，当出现锁竞争时，Synchronized，先是 自旋获取锁，如果获取不到才升级为重量级锁，阻塞线程。

如果 在自旋期间，可以获取锁，则线程不会被挂起，也就不会产生上下文切换。

而 ReentrantLock，在未获取锁时，会被阻塞。直到被唤醒。期间会产生上下文的切换。所以此时 Synchronized 会优于ReentrantLock

2. 为什么 ConcurrentHashMap 的读操作不需要加锁？

因为 hash table 使用了volatile 进行修饰，在各cpu中是可见的。

3.【Synchronized】 与 lock 的区别

-- Synchronized 的三个作用范围：

#静态方法加锁 锁的是类对象

#非静态方法加锁 锁的是当前对象 this

#在代码块上加锁 锁的是指定对象

使用Synchronized 修饰方法，会在代码前后增加 monitor enter 和 monitor exit 命令

-- Synchronized 原理：

jdk6之前，syn 属于 重量级锁，主要依赖系统的互斥锁实现的，涉及到从user land 到kernel land的切换，影响性能。

jdk6之后，引入了偏向锁和轻量级锁。

# 对象存储在堆中，主要分为：对象头，对象实例数据，padding对齐，JVM要求对象占用的空间必须是8 的倍数，

如果是数组，还包括数组长度

对象头主要包括：对象的【hashcode】,锁信息，对象的年龄，GC标记，[线程id,时间戳]，monitor指针，对象的类型。

GC回收的年龄为什么默认是15,因为在markoop中age只有4bit，而4bit最大值是15。偏向锁1bit，轻量级2bit

# 只有将锁升级为重量级锁的时候，才会为对象关联一个 ObjectMonitor 对象：其中保存了等待的线程数，阻塞线程队列，等待线程队列，

当前持有锁的线程指针

class ObjectWaiter : public StackObj {

public:

enum TStates { TS_UNDEF, TS_READY, TS_RUN, TS_WAIT, TS_ENTER, TS_CXQ } ;

enum Sorted { PREPEND, APPEND, SORTED } ;

ObjectWaiter * volatile _next;

ObjectWaiter * volatile _prev;

Thread* _thread;

jlong _notifier_tid;

ParkEvent * _event;

volatile int _notified ;

volatile TStates TState ;

Sorted _Sorted ; // List placement disposition

bool _active ; // Contention monitoring is enabled

};

markOop中也保留该属性 ObjectMonito

ObjectMonitor() {

_header = NULL;

_count = 0; // 重入次数

_waiters = 0, // 等待线程数

_recursions = 0;

_owner = NULL; // 当前持有锁的线程

_WaitSet = NULL; // (ObjectWaiter) 调用了 wait 方法的线程被阻塞,

FreeNext = NULL ;

_cxq // (ObjectWaiter)最近争取锁的线程队列。自旋(默认10)后如果还没有获取锁，

// 则会被移到 _entryList 队列中 (暂时翻译为：currently mutex queue)

_EntryList = NULL ; //(ObjectWaiter) 双向链表，等待锁 处于block的线程 有资格成为候选资源的线程

_SpinFreq = 0 ;

_SpinClock = 0 ;

OwnerIsThread = 0 ;

.......

}

# Synchronized 获取锁的过程：

没有线程竞争，则设置为偏向锁

偏向锁->轻量级锁：开启偏向锁：+UseBiasedLocking

线程A访问临界区，检查对象头中是否有线程持有锁，如果没有，则CAS更新对象头的锁标记，如果成功，获取对象锁成功；

如果CAS失败，则检查对象头中的线程id是否是自己，如果是，则进入临界区，(可重入锁)。

如果获取锁失败，撤销偏向锁调用revoke_and_rebias()，升级为轻量级锁.

撤销过程：在savepoint的情况下，才能撤销偏向锁；判断当前对象的对象头中的lock是否为null，如果为null，说明无锁

然后再判断持有锁的线程，是否存活(通过扫描线程链表)，如果没有存活，设置对象头为无锁状态，返回撤销成功；

如果线程存活，检索持有该锁的线程的monitor列表中是否包含当前Object的monitor，如果有则重置monitor，否则设置对象为

无锁状态。

升级为轻量级锁：主要使用basicObjectLock和对象头markoop,竞争轻量级锁

如果当前markoop对象中没有basicObjectLock的指针(把 对象的markoop 保存在basiclock中，并使用cas 更新对象头，保存basiclock的指针

如果设置成功，则获取锁成功)，或者 markoop中的lock指针在当前线程的地址空间中，则获取轻量级锁成功。

否者获取锁失败。开始膨胀为--重量级锁

膨胀重量级锁过程：其实就是创建objectmonitor对象的过程

如果 markoop中已经标记为monitor，则说明已经膨胀了，返回monitor；

如果 正在膨胀中，当前线程进入自旋，如果自旋次数超过16次，则进入等待,直到膨胀完成后被线程唤醒

如果处于stack locked 状态，强迫锁膨胀，则线程争抢膨胀锁的权限(通过CAS更新对象头的monitor bit，如果更新成功，则获取权限)，

获取权限的线程，将执行锁膨胀，锁膨胀就是创建一个ObjectMinitor的对象，并初始化数据，将该monitor的指针赋值给markoop(对象头)。

重量级锁：

当对象头中设置了monitor bit，则说明已经处于重量级锁，获取锁的线程，都会被放入到队列中等待。

# monitor enter 竞争锁过程：

调用ObjectMonitor::enter 方法，首先争抢更新monitor的owner指针指向自己，如果更新成功，表明获取到了锁，

如果owner 已经指向了自己，需要将重入次数加1，如果更新失败，自旋一次，如果自旋未能获取到锁，则执行enter1()方法，再次自旋，如果还

不能获取锁，则创建ObjectWaiter对象，放入到cxq队列中，并调用park() 阻塞，等待其他线程唤醒后，调用trylock() 争抢锁。

# wait() 和 notify() :

使用Synchronized 锁对象 A时，当调用wait() 方法时，线程会被放入到与该对象A关联的monito

对象中的waitSet队列中，如果线程A已获取锁，再调用wait()方法,则线程A释放锁，并放入waitSet队列中，

使用sleep(),线程不会释放锁，当调用 notify() 时，会从monitor对象中wait队列中的线程取出一个放入到_EntryList或CXQ队列(默认cxq)

使用notifyAll 则会唤醒wait队列中的所有线程，并开始竞争锁。

#源码：InterpreterRuntime::monitorenter--> 使用synchronizer:ObjectSynchronizer:fast_ente

#lock 请参考 3 AQS

4.【 volatile 】 原理？volatile可以保证线程安全吗？

#可见性、有序性、原子性

#volatile 保证变量在各CPU中的可见性，以及防止指令重排添加内存屏障，编译器优化代码执行，对执行进行重排，

把没有依赖关系的执行，重新排列。若某个线程对声明了volatile的变量进行写操作，JVM会向处理器发送一条【LOCK前缀】的指令，

将这个变量所在缓存行的数据写回主存，LOCK前缀指令通过 “锁缓存” 可以确保回写主内存的操作是原子性的。但是，

其它处理器的缓存中存储的仍然是 “旧值” ，并不能保证可见性，因此，还要借助缓存一致性协议MESI：

每个处理器通过嗅探在总线上传播的数据来检查自己的缓存值是否过期，

当处理器发现自己缓存行对应的内存地址被修改时，就会设置当前缓存行为无效，需要对数据进行修改的时候会重新从主内存中加载。

【备注：volatile 使编译器禁止对指令重排，但无法保证 运行时 多cpu 执行的顺序。因此引入了内存屏障，使cpu同步主存】

缓存一致性协议 MESI：

M (Modify) 修改：

E (Exclusive) 独享：

S (shared) 共享

I (Invalid) 无效：

缓存行（caceh line)使用4种状态进行标记（使用额外的两位(bit)表示)

这些缓存是二级缓存，该缓存直接连接到shared bus 共享总线上，并使用snoopy[snuːpɪ]协议,监听总线上的内存改动，

如果缓存需要修改共享状态下的cache line，则处理器会发送read-with-intent-to-modify的信号。通知其他缓存，cache line被修改了

需要重新同步主存。

一个写请求只有在该缓存行是M或者E状态时才能被执行

如果缓存行处于S状态，必须先将其它缓存中该缓存行变成Invalid状态

备注：窥窃协议，参考 snoopy-protocols.pdf

【cache line 对齐】防止变量分配在同一个cache line 上，而引发对cacheline的挣用问题。

1.两个线程，操作不同的变量，变量被分配在同一cache line，

2.多个线程，操作同一个变量，变量分配在一个cache line上。

5.【CAS】：会出现ABA的问题，一般通过版本号，检查数据的有没有被修改。

6.ThreadPoolExecutor 线程池：

1.ThreadPoolExecutor 中的成员：

workerQueue：用于存放 提交的任务task线程。

workers Set ：用户存放 工作worker线程。

2.当执行execute(Runnable) 提交线程时，首先陆续创建corePoolsize 大小的 workers 线程，消费workerQueue队列中的线程，

如果worker达标则将线程放入到 线程队列中，如果放入成功，则不需要创建新的worker，如果失败（队列已满或者其他原因），

再检查当前worker的数量没有超过最大值，则创建新worker，放入到worker集合中。并运行当前worker，消费workerQueue。

否则 调用 失败的回调函数。

3.在运行期间，如果设置最大线程池大小时，小于当前的正在运行的线程数量，则将workers set中的所有worker线程中断。

构造函数：

ThreadPoolExecutor(int corePoolSize, /**核心线程池大小**/

int maximumPoolSize, /**最大的线程池大小**/

long keepAliveTime, /**线程的存活时间，从队列中poll 任务线程时的超时时间 **/

TimeUnit unit,

BlockingQueue<Runnable> workQueue, /** 阻塞队列**/

ThreadFactory threadFactory, /** 线程工厂，在创建worker时使用**/

RejectedExecutionHandler handler) /** 失败时，回调函数**

【在添加worker 时，使用了ReentrantLock锁，如果优化，可以考虑将锁细化，或无锁CAS。】

4.schedualedThreadPoolExecutor ：线程调度器，可以根据线程运行设置的时间进行调度，内部使用了 DelayedWorkQueue 延迟队列

在往队列提交任务线程时(offer方法)，会根据线程的时间，序号进行排序。越靠前的线程，越是优先调度。

7.队列：

#SynchronousQueue是一个双端队列，不存放数据，一个写操作会等待一个读操作。SynchronousQueue 类似一个信号量通道，

生产者与消费者都要彼此等待对方，其中一个接收到互补条件时，两者出队列，否则阻塞，直到条件匹配为止。

#ArrayBlockingQueue: 内部使用 reentrianlock 和condition,其中 put 如果队列满，会等待，poll 方法如果队列满会立即返回失败

#PriorityBlockingQueue：优先级队列使用堆排序，将优先级最高的放在 堆顶。在get时，直接获取堆顶的数据

最小堆，父节点总比 左右孩子小，但是 左右孩子是无序的。堆使用数组表示，索引 1 的左子节点 是 i*2+1 =1*2+1=3,右节点为4

在建立最小堆时，将插入的新节点和自己的父节点做比较，(以最小堆为例) 如果父节点大于 新节点，则交换两个值

再继续向上和父节点比较，一直到根节点。

在移除堆顶元素时，需要比较左右孩子的大小，选择最小的一个，放入父节点。并和最后一个节点，做比较

一直找到比最后节点大的节点，否则继续向下搜索左右孩子。如果找到，将最后节点移动到该位置

#优先级队列的底层原理？使用最大最小堆，将最小或最大的数据，始终放入堆顶

******************************

JVM

******************************

8.【JVM】

8.1 JVM运行时数据区包含哪些?

主要是在栈上分配一个frame，frame包括：操作数栈，局部变量表，回退地址

8.2 JVM垃圾回收机制，何时触发MinorGC等操作？

当年轻代没有足够空间分配对象或enden占满

8.3 JVM的垃圾回收算法？

引用计数器，无法解决循环引用的问题；复制算法适合少量存活对象的内存区，标记-清除，老年代

8.4 JVM 调优的工具?

JPS -v 可以查看 启动时的 虚拟机内存参数设置信息，-l 可以查看启动类或jar路径。

jstat 查看内存、gc 统计信息

jmap: 生成内存快照文件

jhat：分析内存快照。

jinfo 实时查看和调整虚拟机运行参数

9.JVM参数调优详细过程

#打印GC日志：+PrintGCDetails、PrintGCTimeStamps gc时间戳；-Xloggc，设置gc保存的日志路径

#参数说明：

-Xms ：堆容量大小 (memory size)

-Xmx ：堆容量最大值(menory max)

-Xmn ：新生代大小；(menory new)

-Xss : 栈容量 (stack size)

-XX:MaxDirectMemorySize ： 直接内存大小

SurvivorRatio ： enden 和survivor的比例

XX:NewRatio ： 新生代与老年代比例，默认1:2；G1时不用设置

XX:PretenureSizeThreshold ： 设置多大的对象，会被直接分配到老年代，

XX:MaxTenuringThreshold ： 新生代晋升老年代的年龄阈值，默认15

XX:MaxGCPauseMillis ： 垃圾回收时最大停顿时间 默认200毫秒

XX:PreBlockSpin ： 阻塞前自旋次数 默认10

XX:G1ReservePercent ： G1为分配担保预留的空间比例

XX:InitiatingHeapOccupancyPercent ：堆内存占用比，用于启动GC，默认 45%

XX:G1HeapRegionSize ： 区块大小

XX:GCPauseIntervalMillis ： Gc 执行间隔

XX:G1MaxNewSizePercent ： 新生代栈堆的比例

XX:ConcGCThreads ： 并行标记线程数

XX:ParallelGCThreads ： STW期间，并行GC线程数

XX:G1OldCSetRegionThresholdPercent GC每次回收Region的数量

-XX:+UseSpinning ： 是否使用自旋锁

-XX:+UseBiasedLocking ： 是否开启偏向锁

-XX:+UseTLAB ： 使用线程本地栈空间；让线程预先分配一块属于自己的空间(64K-1M)，分配时先在自己的空间上分配，

不足时再申请，这样能就不存在内存区块锁的竞争，提高分配效率

-XX:+UseG1GC ： 使用G1回收器

UserConcMarkSweepGC : 使用 CMS 垃圾回收器

UseCMSCompactAtFullCollection： 在 full gc 时，对老年代进行压缩

CMSInitiatingOccupancyFraction： 老年代在使用多少时进行回收

UserParNewGC ： 新生代使用Parnew 回收器

HeapDumpOutOfMemoryError：内存溢出时，打印内存快照

HeapDumpPath ： 快照保存路径

DisableExplicitGC ： 禁止 system.gc()

一、JVM内存区域：

1.程序计数：正在执行的字节码指令的地址，线程独立保存私有的程序计数器，用于线程之间的切换。

2.【栈】：是线程私有的，与线程声明周期相同，主要用来存放【局部变量表】、操作数等；局部变量表中保存

各种基本数据类型，引用类型、returnaddresse(指向字节码指令的地址)

--Frames Java帧：

*每次调用一个方法都会创建一个新frame。无论调用方法是正常结速还是突然的终止，frame将被销毁。

*frame是从创建frame的线程的Java栈中分配的。每一个frame都有自己的局部变量数组，自己的操作数堆栈，

以及对当前方法类的运行时常量池的引用。

*局部变量数组和操作数堆栈的大小是在编译时确定的，并与框架相关联的方法的代码一起提供。

*如果一个frame的方法调用另一个方法，或者该frame的方法完成，则该frame将停止为当前帧。当调用一个方法时，将创建一个新frame，

并在控制转移到新方法时成为当前frame。

在方法返回时，当前frame将其方法调用的结果(如果有的话)传回前一帧。当前一frame成为当前帧时，当前frame将被丢弃。

由线程创建的frame是该线程的本地frame，不能被任何其他线程引用。

3.本地方法栈(native):主要为Native方法服务的

4.【堆】：Java堆是被所有线程共享的一块区域，所有的对象实例以及数组都在堆上分配；【逃逸分析】

堆分为：eden、from 、survivor、to，根据垃圾回收器的不同，堆结构是不同的

5.方法区：主要保存类信息、常量、静态变量等。

6.运行时常量池：用于存放编译期生成的字面量和符号引用

7.metaspace

二、对象创建过程：new

#对象创建过程：

-- 获取new后面的类标识符

-- 判断类是否被加载并解析，使用InstanceClass对象保存加载的类

-- 从常量池中获取instanceclass 对象的首地址

-- 检查instanceclass是否初始化，如果没有，调用 slow_case,slow_case 执行加载类并创建对象的过程

-- 获取instanceclass的大小

-- 尝试在TLAB 中分配对象，判断TLAB的剩余空间是否大于InstanceClass 的大小

如果无法保存对象，则在共享的eden区分配

-- 在共享eden分配，检查eden剩余空间的大小

-- 加锁，并在eden中保存对象

-- 判断 installclass 是否等于零，如果等于直接初始化对象头

-- 否则先初始化对象的field，然后在初始化对象头

-->【对象的格式】：

包括对象头(markoop)、实例数据、padding，

对象头 包括 hashcode、gc age、线程id时间戳，锁标记、类型指针、或 数组长度

类型指针指向 类元信息的指针

-->【访问对象】：线程栈中的局部变量表中保存了新创建的对象的指针。使用指针可以直接定位到堆中的对象。

-->【##对象逃逸#####################################】：

当变量（或者对象）在方法中分配后，其指针有可能被返回或者被全局引用，这样就会被其他方法或者线程所引用，

这种现象称作指针的逃逸(Escape)。

--》锁消除，如果某个对象的锁只会在一个线程上使用，则会把锁移除， -XX:+EliminateLocks

--》标量替换：标量包括：基本数据类型、对象引用

聚合量：对象。对象内有基本数据类型，对象。可以将对象分解成 标量形式。 -XX:+EliminateAllocations

--》栈上分配：当对象没有发生逃逸时，该对象就可以通过标量替换分解成成员标量分配在栈内存中，和方法的生命周期一致，

随着栈帧出栈时销毁，减少了 GC 压力

三、【垃圾回收算法】

1.标记-清除算法

标记清除算法，会导致大量的内存碎片，如果需要为较大的对象分配内存时，没有连续的内存块可以使用，则会被迫执行垃圾回收

2.复制算法：(用于新生代)

将内存按容量划分为大小相等的两块，每次使用其中一块。

将存活的对象顺序复制到另一块内存中，然后清除当前块的内存，可以减少内存碎片。但需要预留一半的空间，当存活的对象数量较大时

复制对象的时间也将增加，性能也会受到影响

3.标记-整理算法(老年代)

将所有存活的对象，像一端移动，然后清理掉边界以外的内存。

四、【垃圾回收器】

哪些内存需要回收

什么时候回收

如何回收

1.引用计数器，在对象中添加对象被使用的次数，每当引用对象时，计数器+1，释放引用时，计数器-1.

但该算法，无法解决对象之间循环引用的问题。

2.可达性分析算法：从 GC root开始，向下搜索，当一个对象与GC root未链接时，该对象是不可达的。

可作为root对象：栈中局部变量表中引用的对象、方法区中的静态属性引用的对象，常量引用的对象

3. 生存死亡：

一个对象是否被回收，需要经历2次审判，在第一次扫描时，如果对象与GC root 没有连接，则进行标记，并

进行一次筛选，如果对象没有覆盖finalize()方法或者已经执行过，则视为"没必要执行"。

如果对象有必要执行finalize()方法时，会将对象放入到 Finalized-Queue 等待队列中，由专门的线程，触发对象的finalize()方法

在第二次筛选时，对象可以在finalize()方法，把自己赋值给其他对象的成员变量，逃脱死亡。

4. 【当对象的年龄 超过阈值时，会进入老年代，默认 15】

#ParNew 回收器：

新生代 并行回收， 采用复制算法，进行垃圾收集时，必须暂停所有工作线程

#Parallel Scavenge 回收器：

新生代 并行回收，复制算法，Scavenge 回收器关注的是 cpu 的吞吐量

#【内存管理类继承关系】：

分配内存是通过 universe 类分配，其中包含属性 collectedHeap类，其子类 sharedHeap

g1CollectedHeap和 GenCollectedHeap 继承 sharedHeap;

ParallelScavengeHeap 继承collectedHeap,关系如下：

collectedHeap

--sharedHeap

--g1CollectedHeap 用于G1

--GenCollectedHeap 用于CMS

--ParallelScavengeHeap 用于Parallel

#【Concurrent Mark sweep】 并发标记清除回收器：使用的是 GenCollectedHeap 类进行内存分配

CMS 组成 background GC 、compact GC(压缩式)

#对象创建：

1.首先检查要创建的类有没有在 constantPool中，2.如果有，则能不能在线程本地堆TLab中分配内存

3.如果不能，则在share eden中创建，4.初始化 对象头包括link 类指针。5.调用类的init方法。

#内存的实现：【内存的分配与具体的使用的回收器相关，与G1分配略有不同】

如上所述，在给对象分配内存时，如果在shareeden中分配，则在PSYoungGen的 _edenspace 中申请，在allocte时，最终

都会去arena开辟内存空间。arena 是一块内存区域，由chunk 块组成，链表结构。arena 屏蔽了离散的内存空间。对上层内存的

使用，就像是连续的内存空间。

arena : 内存区域，由 chunk 组成，jvm 在分配空间的时候，最终是在arena上分配的。

chunk ：块，默认32k，块包含next指针，指向下一个块。

PSYoungGen 包括：_eden_space,_from_space,_to_space (MutableSpace 类型),

将enden对象复制到 from区后，会交换 from和to的指针

已空间换取时间。DefNewGeneration中 swap_space()方法，交换 from 和 to 指针

PSOldGen：只包含 一个MutableSpace 类型的对象，及其他属性

MutableSpace: 可变的内存区域，继承了ImmutableSpace,ImmutableSpace 是不可变的内存区域。MutableSpaceMangler？？

memRegion 类包括：起始位置和大小；一块连续的存储区域,

BitMap：使用bitmap标记对象是否被标记存活，快速查询

HeapWord，指向堆的通用指针，使用变量value保存指针，char类型的数组结构

#CMS 基本步骤：

目标是减少回收停顿时间，采用标记-清除算法，包括7个步骤：

--》初始标记：

停止线程，标记老年代中所有的GC root对象，如果对象存活，把对象头标记11

新生代引用老年代的对象

--》并发标记：

从root对象开始，遍历存活的对象，

--》 预处理

处理在并发标记阶段漏掉的对象，为了不扫描整个老年代，所有在并发标记期间更新的对象，

都会记录cardtable中，并标记为脏数据。后续扫描只需扫描cardtable就可以

【card table】： 每一个比特位可以用来表示年老代的 某一区间 中的所有对象是否被新生代对象引用，

如果 某个对象被引用，则找出该对象在region中的位置，并计算区间，然后 找到 cardTable的偏移量，设置为1

-XX:ParGCCardsPerStrideChunk=4096,设置每个线程每次扫描的Card数量

--》重新标记： 需要停止线程

该阶段主要处理新生代引用了老年代的对象，所以要扫描整个堆空间，为了减少对新生代对象的遍历

可以提前对新生代进行一次回收，通过+CMSScavengeBeforeRemark 参数，可以先进行young gc。

--》并发处理：

主要处理未使用的对象，此时会产生碎片，所以根据backgroud gc的执行次数 以及 老年代是否有空间存放从新生代迁移的对象

等条件，触发compact gc。

Compact GC 触发条件：

1.Cms 执行的次数，超过阈值CMSFullGCsBeforeCompaction

2.新生代GC是否失败，在对象晋升到老年代时，由于老年代的空间不足，导致GC失败。

3.是否清理软引用对象，CMSCompactWhenClearAllSoftRefs 参数配置

CMS的并发数默认是 （新生代gc线程数+3）/4

出现 promotion failed 提升失败：

1. 如果是因为内存碎片导致的大对象提升失败，cms需要进行空间整理压缩；

2. 如果是因为提升过快导致的，说明Survivor 空闲空间不足，那么可以尝试调大 Survivor；

3. 如果是因为老年代空间不够导致的，尝试将CMS触发的阈值调低；

#【G1】回收器 G1CollectorPolicy

【HeapRegion】 : 是最小的回收单元, 回收器在使用G1时，内存分配使用heapregion

HeapRegionRemSet* _rem_set; /*记录引用发生变化时，用来记录其他分区指向当前分区的指针*/

uint _hrm_index; /*The index of this region in the heap region sequence.*/

HeapRegionType _type; /*标记是young或者 Humongous，如果是young 标记是enden还是

survivor*/

HeapRegion* _humongous_start_region; /*For a humongous region, region in which it starts.*/

HeapRegion* _next_dirty_cards_region; /*脏 card table。*/

HeapRegion* _next; // 双向链表

HeapRegion* _prev;

HeapWord* _prev_top_at_mark_start;

HeapWord* _next_top_at_mark_start;

【 FreeRegionList】 空闲 region

/**链表，指向头尾 节点**/

HeapRegion* _head;

HeapRegion* _tail;

【 YoungList 】: young_region的集合

G1CollectedHeap* _g1h;

/** enden regions 等于 young regions - survive regions **/

HeapRegion* _head; /*young region 头部节点指针*/

HeapRegion* _survivor_head; /*survive region 头指针*/

HeapRegion* _survivor_tail; /*survive region 尾部节点*/

HeapRegion* _curr; /*当前使用的region 指针*/

/*eden 的长度 = _length - _survivor_length */

uint _length; /*young regions 的 长度，也就是region数组的长度*/

uint _survivor_length; /*survive region 的长度*/

size_t _last_sampled_rs_lengths;

size_t _sampled_rs_lengths;

void empty_list(HeapRegion* list);

HeapRegionManager: region 管理器

G1HeapRegionTable _regions; /*存放有序的region地址，对应heap 地址*/

FreeRegionList _free_list; /*空闲列表*/

BitMap _available_map; /*表示 _regions 中，哪些heap region是可用的*/

uint _num_committed; /*提交region的数量 */

uint _allocated_heapregions_length; /* 分配region 的总大小*/

【G1CollectedHeap】：G1 内存管理

static size_t _humongous_object_threshold_in_words;

HeapRegionManager hrm; /*heapregion 管理器*/

FreeRegionList _secondary_free_list; /*辅助空闲列表，最后都要合并到 _free_list 上*/

HeapRegionSet _old_set; /*老年代内存区*/

HeapRegionSet _humongous_set; /*较大对象存放区域*/

YoungList* _young_list; /*新生代内存区*/

HeapRegion* _alloc_region; /*在该 region上 分配空间*/

#G1分为三种模式：youn GC，mixed GC，full GC

--》young GC：

当无法在eden区域分配空间时，就会触发一次young gc，执行完后，重新标记heapRegion的类型_type，将survivor标记为enden，

交换enden 和survivor的头部指针，回收的region 放入到 free_list中。

--》mixed Gc: 混合GC

young GC 和 对部分 Old region 进行GC，减少gc耗时。

1.初始标记，停止线程，标记从Gc root 可达的对象

2.并发标记，标记各个region 的存活对象

3.重新标记，停止线程，在并发标记阶段，对象引用会发生变化，而这些对象记录在remember set(_rem_set)中，

线程直接扫描region的_rem_set,标记这些对象。

而对于漏标的对象,线程会把发生变更的对象放入到_satb_mark_queue 队列中，在下次gc时，会依次处理队列中的对象。

4.清理

五、类加载机制：

==类加载过程：

|--------- LINK ---------|

加载--》验证--》准备--》解析 --》初始化

【加载过程】：

在执行加载之前，首先是先检查父类加载器中有没有加载此类，如果没有，则交给子类加载器进行加载。

下面是类加载器加载一个类的执行过程：

systemDictory->load_instance_class()

-->调用 ClassLoader::load_classfile(); 读取二进制流，创建 一个 InstanceKlass 的句柄 instanceKlassHandle；

-->再调用 find_or_define_instance_class(class_name, class_loader, k)方法，检查先classLoad 下有没有加载过当前类

--> 再调用 define_instance_class（）对class 进行初始化，将类添加到字典或者占位符链表中，表明该类已经加载了。

--> 再调用 eager_initialize(Thread)-->调用 link_class_impl (instanceKlassHandle,true,Thread) 方法，link过程开始

ClassLoader::load_classfile() 过程：

1.获取 class 的文件路径，然后调用 open_stream方法 打开 ClassFileStream。

stream = e->open_stream(file_name, CHECK_NULL);

ClassFileParser parser(stream); 创建 ClassFileParser 类的实例

2.调用ClassFileParser.parseClassFile 方法进行 类文件的解析，class 存放在metaspace内存区；解析出的Class放入到ClassloadData 链表中，

作为GC root的入口

3.解析并验证class文件格式：(根据class文件的内容 创建一个InstanceKlass，包含类的各种信息)

--》验证魔数、版本

--》解析常量池，提取 父类、接口、字段、方法等在常量池中的索引

--》解析父类、接口、Fields，方法，注解

--》递归处理父类信息，并创建父类句柄，并检查父类 是不是接口，是不是被 final 修饰

先判断 父类是否在字典中，如果在，则直接返回

如果不在，则在占位符字典中判断是否存在，如果都不存在，就创建

备注：

解析出的类放入到了字典中，对类名计算hash，判断类是否在字典中。

如果是正在解析中的类，则类和父类，接口会放入在 占位符字典中。

--》 创建当前类的句柄，设置类型信息 ，包括 版本，字段，方法 ，父类，接口等等

--》【把父类和接口添加到依赖关系链表中】

--》创建当前类的 InstanceKlass 的句柄

【Link 过程】

link_class_impl 实现：

--》递归 link 父类

--》link父类完成后，再 递归 link 接口

--》最后再link当前类，

--》link过程包括：验证 和 Rewriter 重写

验证：主要验证字节码格式等，类、父类、接口，以及 字段、方法与父类|接口中的变量和方法的正确性，

Rewriter: 将方法的字节码放入内存、分配运行时常量池、重新引用方法，变量赋默认值，在方法区中添加

虚拟方法表vtable 和 接口方法表 itable，用于提升搜索方法的性能。

。

--》初始化，调用 <init> 方法，初始化字段变量

触发 初始化 阶段 的 条件：

# 使用new 创建类对象，调用类的静态属性和方法，

# 使用反射机制，也需要提前对类初始化

# 如果类的父类没有初始化，则需要先初始化其父类

==双亲委派

类加载器：启动类加载器、扩展类加载器、应用类加载器

在ClassLoader 中有一个parent 父加载器，在 load class时，先调用父类类加载器去加载类，如果父类类加载器

没有不能加载该类，则由子类继续查找。如果需要解析，则调用resolveClass() 方法

双亲委派的好处：

1.保证在同一个类加载器中，类是唯一的，不会被替换。

2.防止重复加载类

--Thread 类，setContextClassLoader(),用户设置类加载器，例如 Mysql 驱动，jndi接口是由启动类加载器加载，

而Mysql驱动是由用户的应用类加载器加载的，通过设置当前线程的contextclassloader,父类类加载器就可以通过子类

类加载器，加载class。

Java 内存模型

工作内存和 主内存

线程在工作内存中分配变量，线程同步变量是通过主内存进行的，线程从主内存复制变量的副本，修改后在回写 主内存。

tomcat ：

server --> service --> engine -->host -->context(应用)-->wrapper(包装了servlet)

每一层通过pipeline 链接，使用valave 阀门，决定数据是否传入下一层。

bootstrapClassloade

extendclassloade

AppClassloader,在tomcat下，叫做 SystemClassload

--以上是JVM的类加载器

Commclassloade

|-- shareClassloader 都继承commonclassloade

|-- catalinaClassloade

=======================================

ZooKeeper

=======================================

1.各种状态

enum ServerState { || enum ZabState {

LOOKING, || ELECTION

FOLLOWING, || DISCOVERY

LEADING, || SYNCHRONIZATION

OBSERVING || BROADCAST }

}

enum SyncMode {

NONE,

DIFF,

SNAP,

TRUNC

}

2.树结构：

DataTree{

NodeHashMap nodes; //主要用于存放数据

PathTrie pTrie = new PathTrie(); // 存放目录树结构

}

NodeHashMap{

ConcurrentHashMap<String, DataNode> nodes; // path 为key，

boolean digestEnabled;

AdHash hash;

}

DataNode{

volatile long digest; // 摘要

byte[] data; // 存放数据

Set<String> children = null; // 存放孩子 的路径

Long acl; // 访问控制

public StatPersisted stat; // 数据节点的状态

}

PathTrie {

TrieNode rootNode; // 根节点

}

TrieNode {

final String value; // 当前节点的子路径值 value=config 例如：/zookeeper/config/data，也就是 分割 "/" 后的字符串

final Map<String, TrieNode> children; // 孩子节点，key 是子路径值，使用hashmap

boolean property;

TrieNode parent; // 前一个路径

}

3.选举过程：

服务间的通信，发送数据，通过 sendqueue 队列，接收数据通过recvqueue 队列

LinkedBlockingQueue<ToSend> sendqueue;

LinkedBlockingQueue<Notification> recvqueue;

ToSend{

long leader; // leader id

long zxid; // 事务id

long electionEpoch; // 选举的纪元

QuorumPeer.ServerState state; // 状态

long sid; // 接收消息的服务器id

byte[] configData; // 发送数据

long peerEpoch; // Leader 的epoch

}

Vote{ 投票

this.version = 0x0;

this.id = id; // 推举的leader id

this.zxid = zxid; // 事务id

this.electionEpoch = -1;// 选举时期的纪元，

this.peerEpoch = -1; // 前一个纪元

this.state = ServerState.LOOKING; // 状态

}

主循环不断监听当前serverstate，如果是looking 则执行选举流程(lookForLeader方法)

--先将自己的epoch 加1，设置新的epoch

--更新投票信息，设置为自己，给其他服务器发送通知

--循环监听serverstate，如果是looking，从 recvQueue中取出投票信息。否则退出循环体

--检查投票信息：如果对方的新的epoch 大于等于 当前实例的epoch，则更新本地的epoch，保持epoch一致

然后在比较双方前一个epoch的大小，如果相等，再比较zxid，如果zxid相等，再比较serverid，选择最大的

做为候选leader。更新本地投票为候选leader，发送通知。

--保存对方的投票信息，

--检查投票，判断投票是否有达到多数的情况，如果有，设置投票信息和实例状态。(如果proposedLeader等于 当前server的id，

设值当前server的state 为 Leading 状态，否者设置为Following.) 退出选举流程。

此时，当前实例的状态更新为Leading 或者 Following，主循环依旧在监听实例状态，如果状态是leading 则重新创建leade

如果是following，则重新创建follower，开始follower 同步数据

4.同步数据：

1.follower 在与 leader 建立连接之后，会发出 FOLLOWERINFO 信息，获取新的epoch值。

2.leader 向 follower 发送 LEADERINFO 信息，告知 follower 新的 epoch 值

3.follower 接收解析 LEADERINFO 信息，更新本地的epoch。

4.follower 向 leader 发送 ACKEPOCH 信息，反馈 leader 已收到新的 epoch 值，并附带 follower 节点的 last zxid

5.leader 比较 zxid 和本地minCommittedLog(已经提交的事务ID，也就是与其他follower commit后的zxid)

maxCommittedLog(提交本地日志的id)，

#如果 zxid 大于 maxCommittedID ，则follower需要做 TRUNC 回滚

#如果 zxid 大于 minCommittedID ，小于 maxCommittedID ,则需要回滚，再增量同步

#如果 zxid 小于 minCommittedID，则执行全量同步

5.数据更新，提交提案 【ZAB 协议】

当zk实例接收到数据更新请求时，将请求发送到leader，leader 将请求包装成提案(增加事务zxid+1)，发送给follower，follower接收到提案后，

返回应答，如果leader接收到大多数follower的应答后，(如果follower接收到的事务id小于本地的事务id，则抛弃)，

发送commit通知，要求follower提交数据。最终一致性。

--》paxos 分布式一致性协议：

1.proposer 生成一个提案编号，向acceptor 发送prepare 请求，并携带 提案编号，(prepare 阶段,为了达成value的一致)

2.acceptor 如果接收到prepare请求，比较 已经接收到的提案号，选择最大的提案号，并更新本地提案号

返回 提案号 和 value

3.proposer 接受到过半的acceptor的应答，则向acceptor发送accept 请求，并携带 提案号和value，

proposer 比较 acceptor应答的编号是否比自己的大

如果大于本地编号，则更新提案编号，以及value。如果value为null，则发送自己的value

如果没有收到多数acceptor的应答，则回到 步骤1.

4.acceptor 接受accept请求，如果在接受accep请求之前，acceptor 响应了 其他proposer的prepare请求并且 提案编号

比 当前 accept 请求中的提案编号大 则拒绝接收提案。

6.zk的节点类型：

永久节点，临时节点，顺序节点

===================================

Redis

===================================

--Redis 单线程模型，主从，cluster，

1.分布式锁，redis、zk

redis 分布式锁：

通过命令setnx 命令设置并设置超时时间。此操作存在两个问题：

1.时间超时，但业务操作未完成。可以通过刷新超时时间，解决

2.当client A 请求锁，并持有锁，此时client A执行业务代码，此时master down掉了，但锁未同步到slave

3.client B，请求锁，并成功获取锁。引发安全性问题。可以使用以下算法解决，主要思想是通过多个master实例获取锁，

达到多数表示获取锁成功：

1.获取当前的毫秒数

2.它尝试在所有N个实例中按顺序获取锁，在所有实例中使用相同的密钥名和随机值。在步骤2中，当在每个实例中设置锁时，

客户端使用一个比锁自动释放总时间小的超时来获取它。例如，如果自动释放时间为10秒，则超时可能在~5-50毫秒范围内。

这可以防止客户端在尝试与关闭的Redis节点通信时长时间处于阻塞状态：如果某个实例不可用，我们应该尽快尝试与下一个实例通信。

3.客户机通过从当前时间减去在步骤1中获得的时间戳来计算获得锁所经过的时间。如果且仅当客户端能够在大多数实例（至少3个）

中获取锁，并且获取锁所用的总时间小于锁有效时间，则认为该锁已被获取

4.如果获得了锁，则其有效时间被视为初始有效时间减去经过的时间，

5.如果客户端由于某种原因无法获取锁（要么无法锁定N/2+1个实例，要么有效期为负数），它将尝试解锁所有实例

（即使是它认为无法锁定的实例）。

redis锁，会引发羊群效应，zk锁，可以通过使用有序节点，每个获取锁的client 监听 前一个节点。这样可以避免锁释放后引发的羊群效应

但是两种锁都会因为网络的抖动，引发 锁 不安全性。

2.数据类型：字符串sds,list,ziplist,map,set,dict,hyperloglog,raxtree

dict：scan 方法中使用到了 reverse cursor 算法，保证在dict 扩容时，不会漏掉数据，但一条数据可能会返回多次

在遇到冲突时，采用链表解决，且采用头插法的，将新的元素添加到槽的头部

zset:

skiplist的结构：

typedef struct zskiplistNode {

sds ele; /* value值 */

double score; /* 分值 */

struct zskiplistNode *backward; /*指向节点前面的节点指针，A->B->C B.backward->A*/

struct zskiplistLevel {

struct zskiplistNode *forward; /*指向后面的节点指针*/

} level[]; /* 当前 节点有几层*/

} zskiplistNode;

typedef struct zskiplist {

struct zskiplistNode *header, *tail;/* 指向头节点和尾节点 */

unsigned long length; 总数据大小

int level; 当前总层数

} zskiplist;

在使用skiplist时，redis 采用随机层插入节点：

int zslRandomLevel(void) {

int level = 1; // ZSKIPLIST_P=0.25

while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))

level += 1;

return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;

}

其中采用了【幂律分布】：例如 二八定律

曲线图

3.击穿、穿透、雪崩:

击穿：key对应的数据存在，但在内存中过期，大量的请求发送到数据源。

穿透：请求的key 不在缓存中，且key对应的数据在数据源也不存在，请求被发送到数据源。

解决方法：使用Bloom Filter，来判断数据是否存在。如果数据量比较大，可以使用table，一个bit 表示一个区间

雪崩：服务器重启，需要加载大量的数据放入缓存中，而大量的请求被发送到数据源，对数据源造成压力。

解决方法：使用数据预热任务，先把数据加载到内存。使用全局线程池同步数据。

方案：添加注解，@FromCache(fromDb="Method",setCache='Method')将注解添加到方法上，表示先从缓存获取数据,

fromDb 属性表示从数据库获取数据需要执行的方法

SetCache 属性 表示 从数据库获取到数据后，需要设置缓存的方法,

使用切面，拦截要执行的方法，使用反射执行fromCache的方法，如果没有获取到数据，找到该类的fromDb="Method" 的方法并执行，执行该

方法放入到线程池里面执行，等获取到数据后，调用SetCache方法，将获取到的数据放入缓存。

如果是缓存预热，可以使用分布式任务，并发加载数据。

4.redis 事务原理：

当调用watch key命令时，将client 放入到监听列表中(wacthkeys)，当数据库执行更新操作时，触发回调函数，将client标记为dirty状态

multi 命令，将client 要执行的命令，放入到 待执行的命令列表中 client->mstate.commands,

当client 执行 exec 命令时，会循环执行 mstate.commands中的命令，如果client的被标记为dirty，执行事务失败。

【 CAS 】-->使用watch 对key进行getandset操作 watch key; get key ; 操作后; Mult set key

5.aof rdb

一个是基于命令，一个是基于数据。在主从实时同步(增量)数据时使用的是rdb。环形缓冲区。服务器之前发送数据使用的 块(chunk) 链表结构。

6.集群与主从

集群：多个master 分摊 16384 个槽， master 可以配置多个从节点，防止master down机后，集群不可用的情况；

从节点复制进程从master上负责数据，如果master挂掉了，则选择从节点中的一个升级为master，参与选择的是集群中的

master节点，优先选择复制偏移量大的，其次是服务器id 小的。选举过程类似zk的选举过程，slave 将自己的epoch+1，防止老master启动后执行

错误的请求。

#Redis 故障转移，选择master：

--如果master状态为fail，salve计算master所有slave的排名rank;根据偏移量和name进行排名，如果偏移量越大，rank值越小

--根据计算出的rank值，计算发送failover请求的等待时间，rank越小，等待时间越小，就可以提前发送选举的请求,获胜的机会就越大。

--其他master接受到请求后，会验证epoch，然后投票给slave，发送ack响应报文，期间该master不会给其他slave投票。

-- slave接受ack报文，如果投票是自己，则将投票数加1，检查是否达到了多数，如果达到了多数，则声明自己为master。

7.槽迁移：

有两个列表，一个列表表示从该实例需要往外迁移的槽记录，一个是需要迁移到本实例的槽记录。

将槽里的数据写入rdb，然后发送给对方。迁移的过程中，client 可以写入，也可以读取。

8.缓存失效，LRU LFU

LRU算法：使用双向链表，将新加入的数据放入表头，如果链表中的node命中，则将该node放入到表头，当数据满的时候，删除表尾的node。

(表头的数据是最近访问过的，越靠后的node，被访问的机会越少)

LFU 算法：需要记录node 访问的次数和访问的时间，并且需要实现comparable 接口，提供比较方式。

=========================

队列

=========================

1.rocketmq，重复消费，顺序消息，事务消息，高可用，消息丢失，挤压场景，整个消息发送消费的流程

# Producer、Consume

# NameServer：是一个非常简单的Topic路由注册中心，支持Broker的动态注册与发现，实现路由信息管理功能；

# BrokerServer：Broker主要负责消息的存储、投递和查询以及服务高可用保证

# 消息存储结构：

1.commitlog：存放消息的文件，文件名以最后的偏移命名，名的长度20位，左补零，默认1G；

2.consumerQueue：基于topic的commitlog的索引文件，保存了 指定topic下的队列消息在commitlog中的

物理偏移量，消息的大小和tag的hash值。

3.indexFile: hashmap 结构，对key 进行hash，放入到map里。

4.消息过滤：通过tag做数据过滤

5.负载均衡：

6.事务消息：写入的如果事务消息，对消息的Topic和Queue等属性进行替换，同时将原来的Topic和Queue信息存储到消息的属性中，

正因为消息主题被替换，故消息并不会转发到该原主题的消息消费队列，消费者无法感知消息的存在，不会消费。

其实改变消息主题是RocketMQ的常用“套路”，

7.消息查询：

#根据messageId：包括目标ip、端口号、commitLog的偏移量

#按照messagekey：对messagekey 进行hash，从 indexFile中取出对应的值

kafka

kafka 特性：

顺序保证性

批量发送

消息持久

1.消息

kafka 以集群的方式运行，可以自由伸缩，实时数据流

kafka 发布与订阅的消息系统，基于pull的方式

消息在kafka中以字节数组的形式存在的，消息有可选的元数据，也就是键，键也是字节数组，键用于topic的partition

2.主题

主题可以分为若干个分区，一个分区就是一个提交日志，由于主题可以有多个分区，因此不能够在主题内保证消息的有序性

但在每个分区中，可以保证消息的有序性。每个分区有多个副本

kafka通过分区来实现数据冗余和伸缩性，分区可以分布在不同的服务器上，也就是说，一个主题可以分布在多个服务器上

num.partitions 配置主题的分区数，分区的个数不能减少，如果消息是按照键值写入分区的，则增加 分区数 会涉及数据的重分配，

也就比较困难

3.生产者与消费者

#生产者：

acks 设置必须有多少分区副本接受到消息，生产者才会认为消息写入成功。

acks=0: 不等待任何服务器的响应，此时生产者无法确定消息是否被服务器接收。

acks=1：只要分区的 首领节点 接收到消息，生产者就会收到成功的响应，但此时也会存在消息丢失的情况，如果首领节点失败

其他未收到消息的broker成为了leader，那么消息就会被丢失

acks=all 分区的各个复制节点都收到消息后，生产者才会收到成功的响应消息

buffer.memory 用于设置生产者缓存的大小，生产者用它来缓存发送到服务器的消息。

【 生产者在发送消息到服务器时，由于某些原因，导致分区中的消息的顺序或者消息重复，所以，从全局要考虑请求的幂等性处理。】

#消费者

消费者 通过 偏移量 来区分已经读取过的消息，在给定的分区里，每个消息的偏移量都是唯一的，偏移量会保存在zk或kafka上

在消费者组中，每个分区只会被一个消费者读取，但一个消费者可以读取多个分区。一个主题可以由多个消费者组读取，相互独立。

enable.auto.commit = true ,消费者自动提交偏移量(提交到kafka _consumer_offset的特殊主题上)

通过调用seek()方法可以设置从分区的那个偏移量读取消息

#再均衡

当一个消费者组中的一个消费者失效后，分区的所有权会迁移到另一个消费者中，这种行为叫再均衡 Rebalance，在Rebalance期间

消费者将无法读取消息，导致整个 消费者组 不可用。

消费者通过向群组协调器broker发送心跳来维持 他们和群组的的从属关系、分区的所有权关系。如果协调器认为某个消费者失效，就会

出发一次Rebalance，

4.broke

broker 是集群的组成部分，每个集群都有一个broker 做作为leader，leader负责将分区分配给broker以及监控每个broker。

一个分区可以分配给多个broker，其中一个broker作为其他分区的首领，其他分区从首领分区复制数据(作为副本)，如果分区首领broke

失效，则有其他broker接管，与其相关的消费者和生产者需要切换到接管的broker上。

broker配置：

broker.id

port

zookeeper.connect

log.di

5.集群

kafka只能在单集群中复制消息，不能跨集群之间复制，kafka提供一个工具可以实现集群之间的消息复制 [MirrorMaker]

kafka使用zk维护集群成员的信息，在broker 启动时，会在zk上创建临时节点，并订阅 zk中的brokers/ids 节点，用来监听

其他broker。

# 控制器：也是一个broker，用于分区leader的选举，第一个成功在zk上创建节点/controller的broker，将成为控制器，通过

在zk上创建临时节点controller 来确保集群中有一个控制器。同时使用epoch 防止脑裂现象。

如果broker下线，控制器就会收到通知，并获取该broker中的主题分区信息，从中获取leader分区的信息以及分区的复制节点

然后，选举出新的leader分区，并发送通知给复制节点，复制节点会重定向到新的leader，并复制消息

# 复制

【kafka使用零复制，直接将文件中的数据发送到网络缓冲区。减少了数据的copy】

复制节点使用 与消费者 同样的方式 获取需要复制的数据。

生产者与消费者都会把请求发送给分区的leader，由leader处理请求。客户端(生产者与消费者)通过发送 元数据请求 获取

主题分区、分区的副本以及分区首领等信息，客户端会缓存这些信息，以确保请求应该发送给哪个broker。broker只会把 同步到

所有分区副本的消息发送给消费者，如果broker间的消息复制变慢，也会导致消费者读取消息变慢

# 分区日志文件

分区文件分成为若干个片段，默认情况下一个片段的大小为 1G或 一周的数据，如果当前活跃的片段 写入的数据达到阈值，则关闭

当前活跃的片段，并打开一个新的片段文件，kafka 会为每个片段打开一个文件的句柄，如果存在大量的片段则系统就会存在大量被

打开的文件句柄，且有一大部分句柄已不在使用。

消息格式：

------------------------------------------------------

|偏移量|魔数|压缩算法|时间戳|值大小|值 |

------------------------------------------------------

同一批次的消息会被压缩在一起，并打包在一起发送给消费者

# 【索引】

kafka为每个分区维护了一个索引，索引把 偏移量 映射到 具体的片段文件以及 在文件中的偏移量 。

例如 ：偏移量 1002 保存在片段 fragment.001上，且在文件的 512 的位置上，可以使用文件的seek方法，快速定位消息的具体位置。

从而，不用将消息保存在内存，直接从文件到网络缓冲区，减少复制数据的代价

删除键：发送一个包含 NULL 值的键，kafka 清理线程会删除该键的历史数据，并保留null值键 一段时间。

=========================

网络

=========================

--网络，udp，7层网络协议等

TCP 报文头：

报文格式

【flags ： FIN,SYN,RST,PSH,ACK,URG 六种状态】

FIN: 表示sender发完数据。通常用在sender发送完数据的最后一个包中。

SYN：表示 tcp 三次握手建立连接时 使用

RST：重置连接标记

PSH：通知接收端处理接收到的报文，而不是将报文缓存在buffer中

ACK：响应标记，表示已经成功接收数据

URG：紧急标记

1.TCP 三次握手：

TCP 在连接过程中，通过Flags标志位来表示传输过程中的连接状态

1. client 发送 链接请求报文；设置 sequence=n，flags=SYN

2. server 响应 客户端；sequence =k；acknum=n+1 flags=ACK

3. client 发送 acknum=k+1 flags=ACK，建立链接完成。

备注：A-->B

--第一个包，即A发给B的SYN 中途被丢，没有到达B;则A周期性的重试，直到收到B的确认包，否则超时

--第二个包，即B发给A的SYN +ACK 中途被丢，没有到达A；则 B会周期性的重试，直到收到A的确认包

--第三个包，即A发给B的ACK 中途被丢，没有到达B：

1.如果双方没有数据发送，则B会重试，直到收到A的确认包，如果收到，B的状态为"建立状态"

2.如果A有数据发送，B收到A的数据时，将状态切换为“建立状态”

3.B在发送数据之前，要先收到A的确认包，才可以发送数据，所以B依然会周期性的发送syn+ack包

直到收到A的回复

为什么采用三次握手？

假如 A 发送给B的 syn 包在网络中由于阻塞被延迟发送了，但此时A已经与B断开了链接，在此情况下

B收到了A的请求，会认为A再次发送了连接请求，B向A发送syn+ack，但A收到B的包后，不发送 确认包

则B认为该连接有效并保持该连接，这样会消耗系统资源，由于系统连接描述符是有限的，如果这样无效的

连接占满了，服务将无法提供服务。

2.TCP 四次断开连接

端链

# TIME_WAIT 需要等待2倍的数据包最大存活时间。确保服务器B接收到了ACK包

3. HTTPS

1.client 下载服务器公钥

2.client 随机生成密钥

3.使用服务器的公钥加密这个随机密钥

4.服务接受到client的随机密钥时，使用私钥解密，解析出客户端的随机密钥

随后的数据传输都通过这个随机密钥进行加解密。

4.UDP

报文格式：源端口 目的端口，校验和，数据内容

5.HTTP:

Http:1.0 :

# 在一个tcp连接上，一次只允许发送一个请求，后来添加了请求队列，但只能解决部分并发，在浏览器上针对一个域名

创建几个tcp链接，用于提高并发性，但依然存在头部阻塞的影响

Http:2.0:

#在未知服务器是否支持http2.0的情况下，客户端以1.0的方式携带协议升级的header(Upgrade:h2或者h2c;http2-setting)，

服务接受到请求后 如果不支持2.0则正常返回；如果支持，则返回状态码：101 Switching Protocols(切换协议),如下

HTTP/1.1 101 Switching Protocols

Connection: Upgrade

Upgrade: h2c

#多路复用：发送请求被分割成更小的帧进行发送，帧可以乱序发送，每个帧都有编号，方便组装信息。

#优先级

#头部压缩：通过保存客户端的头信息，更新或则增量添加header 字段。而不是 每次全部发送所有的header 字段

使用二进制流进行压缩，

(哈夫曼编码 :根据字符在字符串出现的次数作为权值，构建树，每次选择两个最小的节点进行合并,两个节点的

值相加，作为其父节点，不断重复，直到所有节点加入到树中

)

#服务push

#重置

#流量控制，流量限制是针对数据帧进行限制的

Http3.0:基于UDP开发的可靠传输协议，在 Tcp 和 http 层之间加入的一层协议(QUIC) quick UDP internet connection

==========================

算法

==========================

--归并排序：

需要额外的内存空间，在mapreduce的框架中使用；

将两个有序的数组，有序的放入新的数组中，挨着比较两个数组的中的值，按照比较的结果，放入新数组的index下；

--快速排序sort(array,left,right)：

1.从 left 开始 ，right 结束，从right开始，向left 移动，找到第一个小于array[left]的索引 k，放入到array[left];

2.从left开始，向 right移动指针，找出第一个大于array[left]的元素，放入到array[k]中，

3.递归调用 sort(array,left,l-1);sort(array,l+1,right)

--堆排序：

建堆，不断放入元素，然后调整堆。保证 父节点，左节点小于父节点，右节点大于父节点

在数组中 ，根元素是array[0],左子节点是array[1],右 array[2]; array[2]的左右孩子分别为array[5],array[6]

leftindex=i*2 +1 ; rightindex=i*2+2

--链表反转：类似头插法

header--> A-->B-->C-->D-->E<--tail

已知:header,和tail指针。

int tempTail 记录临时的尾节点

while(head->point != tail->point){

int A=header.point;

tail->point.next=A; // E节点的next指针指针A

header->point=A->next; //移动header指针

tempTail->point=A

}

tail=temptail

--链表环路

设置两个指针fast和slow，初始值都指向头，slow每次前进1步，fast每次前进2步，(此方法也可以找到中间的节点)

链表存在环：则fast必定先进入环，而slow后进入环，两个指针必定相遇。(当然，fast先行头到尾部为NULL，则是无环链表)。

寻找环的入口点：

当fast按照每次2步，slow每次1步的方式走，发现fast和slow重合，确定了单向链表有环路。

接下来，让fast回到链表的头部，重新走，每次步长1，那么当fast和slow再次相遇的时候，就是环路的入口了。

--回文 ：abc cba，两边的值对称

设置头尾指针，分别向中间移动，如果其中的值不相等，则表示不是回文，直到指针移到中间位置。

--限流算法

令牌环：匀速地往桶里面放令牌，获取到令牌，才允许转发数据，每次可以获取m个令牌。可以应对突发流量

漏桶：均匀的发送n个数据，可以控制数据注入到网络的速率

--最大子数组：元素相加值最大的子数组

利用动态规划思想，使用迭代，记录上一次最的值，

for(i=1;i<arr.len;i++){mx[i]=max(mx[i-1]+arr[i], arr[i])}

--数组出现最多的 前k个数

首要要记录每个值出现的次数，还要排序获取前k个值；

--放入hashmap中 计算值的出现的次数

--建立最大堆，前k个就是出现次数最多的

--最长公共子序列：

1.设数组X,长度m，数组Y长度n, 构建一个两位数组 K[m,n]

for(i=1;i<m;i++){

for(j=1;j<n;j++)

if(x[i]==y[j]){

k[i,j]=k[i-1,j-1]+1;

k[i,j] 打标记，记录字符串的路径；记录为左上方；‘\’;

}else if(){ // 如果不想等， k[i,j] 上方‘|’ 大于等于 左方([i-1,j]-->上方；[i,j-1]-->左方)

k[i,j]=k[i-1,j]

k[i,j] 打标记为 ‘|’

}else{

k[i,j]=k[i,j-1];

k[i,j] 打标记为 ‘——’

}

}

2.则k[m-1,n-1] 的值就是最长公共子串的值，如果需要输出字符串，需要从最后k[m-1,n-1],回退搜索

--遇到 左上方箭头‘\’ 则 k[i-1,j-1];

--遇到 上方 箭头‘|’，则 k[i-1，j];

--遇到 左方箭头‘——’，则 k[i,j-1]; 输出的值就是公共部分