search

justtreee / blog

31 stars 8 forks source link

【整理】知识图谱整理 #19

Closed justtreee closed 6 years ago

justtreee commented 6 years ago

一、算法

1. 贪心

2. 动态规划

public class zhaolingqian { public int caldp(int n,int[] money){ // dp[i] 金额为i时找的零钱数目 int[] dp = new int[n + 5]; for (int i = 1; i<dp.length; i++){ dp[i] = Integer.MAX_VALUE; //!!!!!!!!!!!! } dp[0] = 0; for (int i = 0; i < money.length; i++){ for (int j = money[i]; j <= n; j++){ dp[j] = Math.min(dp[j - money[i]] + 1 , dp[j]); } } return dp[n]; }

public static void main(String[] args) {
    int[] money = {1,2,5,10,20,50,100};
    zhaolingqian zq = new zhaolingqian();
    System.out.println(zq.caldp(625, money)); //8
}

}

## 3. 排序算法
[各种排序算法原理与比较](https://github.com/francistao/LearningNotes/blob/master/Part3/Algorithm/Sort/%E9%9D%A2%E8%AF%95%E4%B8%AD%E7%9A%84%2010%20%E5%A4%A7%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E6%80%BB%E7%BB%93.md)

[七大查找算法](http://www.cnblogs.com/maybe2030/p/4715035.html)
> 查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算，例如编译程序中符号表的查找。本文简单概括性的介绍了常见的七种查找算法，说是七种，其实二分查找、插值查找以及斐波那契查找都可以归为一类——插值查找。插值查找和斐波那契查找是在二分查找的基础上的优化查找算法。树表查找和哈希查找会在后续的博文中进行详细介绍。 >
>
> - **查找定义**：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。
>
> - **查找算法分类**：  
> 　　- 静态查找和动态查找；  
> 　　　　注：静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。  
> 　　- 无序查找和有序查找。  
> 　　　　无序查找：被查找数列有序无序均可；  
> 　　　　有序查找：被查找数列必须为有序数列。
> - **平均查找长度**（Average Search Length，ASL）：需和指定key进行比较的关键字的个数的期望值，称为查找算法在查找成功时的平均查找长度。  
> 　　对于含有n个数据元素的查找表，查找成功的平均查找长度为：ASL = Pi*Ci的和。  
> 　　Pi：查找表中第i个数据元素的概率。  
> 　　Ci：找到第i个数据元素时已经比较过的次数。

[不仅详细介绍了诸如树表查找、分块查找等查找方式，还引申了B树红黑树等数据结构的优缺点与使用场景](http://www.cnblogs.com/maybe2030/p/4715035.html)

- O(N)查找有哪些数据结构？
    - 答：顺序查找
- O(logN)查找有哪些数据结构？
    - 答：二分查找、斐波那契查找、二叉查找树（最坏有O(n)的复杂度）、红黑树。
- O(1)查找有哪些数据结构？
    - 答：hash（无冲突的情况）
- 其他：插值查找时间复杂度均为O(log2(log2n))。
#### 堆排序  
- 堆排序（使用大堆，升序）从基本实现原理来说也是一种选择排序。
- 所谓大根堆，就是根节点大于子节点的完全二叉树。
- 首先将所有元素都构建在一个初始堆中，并重建为大堆。这时当前堆中的最大元素就在堆的顶部，也就是数组a[0]，这时将该最大元素与数组中的最后一个元素交换，使其移到最末尾，表明该元素已经到应该在得位置了，之后的堆重建也不需要管他，所以last--，对缩小后的目标堆重建。就这样，将顶端最大的元素与最后一个元素不断的交换，交换后又不断的调用堆以重新维持最大堆的性质，最后，一个一个的，从大到小的，把堆中的所有元素都清理掉，也就形成了一个有序的序列。这就是堆排序的全部过程。
```cpp
#include <bits/stdc++.h>
using namespace std;
int a[100];
void rebuild(int a[], int size, int rt)
{
  int left_child = 2*rt+1;

  if(left_child < size)
  {
    int right_child = left_child+1;
    if(right_child < size)
    {
      if(a[left_child] > a[right_child]) // < shengxu
        left_child = right_child;
    }
    if(a[rt] > a[left_child]) // 用 < 代表大根堆 升序
    {
      swap(a[rt], a[left_child]);
      rebuild(a, size, left_child);
    }
    //注意rebuild的if框
  }
}
void heapSort(int a[], int size)
{
  //第一步 构造初始堆
  for(int i=size-1 ;i>=0 ;i--)
  {
    rebuild(a,size, i);
  }
  int last = size - 1;
  for(int i=1; i<=size; i++, last--)
  {
    swap(a[0],a[last]);
    rebuild(a,last, 0);//把最大的元素沉入堆底之后就可以不用管了，last--
  }
}
int main()
{
  int n;
  cin>>n;
  for(int i=0 ;i<n; i++)
  {
    cin>>a[i];
  }
  heapSort(a,n);
  for(int i=0; i<n; i++)
    cout<<a[i]<<" ";
  cout<<endl;
  return 0;
}

4. 图论

图的遍历和图的连通性**

即BFS、DFS和Kruskal、Prim 算法

拓扑排序

由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。 (1) 选择一个入度为0的顶点并输出之； (2) 从网中删除此顶点及所有出边。 循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列。

5. 数据结构

5.1 栈

public class TwoStackQueue {

Stack<Integer> s1 = new Stack<>();
Stack<Integer> s2 = new Stack<>();

public static void main(String[] args) {
    TwoStackQueue twoStackQueue = new TwoStackQueue();
    twoStackQueue.push(1);
    twoStackQueue.push(2);
    System.out.println(twoStackQueue.pop());
}

private int pop() {
    while(!s1.empty()){
        s2.push(s1.pop());
    }
    int res = s2.pop();
    //重新pop回去
    while(!s2.empty()){
        s1.push(s2.pop());
    }
    return res;

}

private void push(int i) {
    s1.push(i);
}

}

### 5.2 链表
- 链表反转
    [链接](https://blog.csdn.net/fx677588/article/details/72357389)
```java
//遍历反转法：递归反转法是从后往前逆序反转指针域的指向，而遍历反转法是从前往后反转各个结点的指针域的指向。
//        基本思路是：将当前节点cur的下一个节点 cur.getNext()缓存到temp后，然后更改当前节点指针指向上一结点pre。也就是说在反转当前结点指针指向前，先把当前结点的指针域用tmp临时保存，以便下一次使用，其过程可表示如下：
//        pre：上一结点
//        cur: 当前结点
//        tmp: 临时结点，用于保存当前结点的指针域（即下一结点）

public class LinkedListReverse {
    private void Display(Node node){
        while (null != node){
            System.out.println(node.getData() + " ");
            node = node.getNext();
        }
        System.out.println("====");
    }
    private Node Reverse(Node head){
        if (head == null)
            return head;
        Node pre = head;
        Node cur = head.getNext();
        Node tmp;
        while(null != cur){
            tmp = cur.getNext();
            cur.setNext(pre);

            pre = cur;
            cur = tmp;
        }
        head.setNext(null);

        return pre;
    }
    public static void main(String[] args) {
        Node head = new Node(0);Node n1 = new Node(1);
        Node n2 = new Node(2);Node n3 = new Node(3);

        head.setNext(n1);n1.setNext(n2);
        n2.setNext(n3);n3.setNext(null);

        LinkedListReverse linkedListReverse = new LinkedListReverse();
        linkedListReverse.Display(head);

        Node rvs = linkedListReverse.Reverse(head);
        linkedListReverse.Display(rvs);
    }

}

class Node{
    private int data;
    private Node next;
}

5.4. 哈希表

6. 经典问题

Top k 问题

Java使用异或交换两个整数或者字符串的用法及原理

Java实现字符串反转的8种或9种方法

public static String reverse(String s){
    char[] a = s.toCharArray();
    int first = 0, last = a.length-1;
    while(first < last){
        a[first] = (char)(a[first] ^ a[last]);
        a[last] = (char)(a[last] ^ a[first]);
        a[first] = (char)(a[last] ^ a[first]);
        first ++;
        last --;
    }
    return new String(a);
}

7. 大数据相关

二、操作系统

1. 进程与线程

进程是资源分配的基本单位。 进程控制块 (Process Control Block, PCB) 描述进程的基本信息和运行状态，所谓的创建进程和撤销进程

1.1 进程与线程的区别

例：QQ 和浏览器是两个进程，浏览器进程里面有很多线程，例如 HTTP 请求线程、事件响应线程、渲染线程等等，线程的并发执行使得在浏览器中点击一个新链接从而发起 HTTP 请求时，浏览器还可以响应用户的其它事件。
进程和线程的区别？

1.2 并发与并行的区别

并发和并行的区别就是一个处理器同时处理多个任务和多个处理器或者是多核的处理器同时处理多个不同的任务。 前者是逻辑上的同时发生（simultaneous），而后者是物理上的同时发生．

2. 进程

2.1 现代操作系统的进程内存分布

一个linux进程分为几个部分(从一个进程的地址空间的低地址向高地址增长):

  1. text段，就是存放代码，可读可执行不可写，也称为正文段，代码段。
  2. data段，存放已初始化的全局变量和已初始化的static变量(不管是局部static变量还是全局static变量)
  3. bss段,存放全局未初始化变量和未初始化的static变量(也是不区分局部还是全局static变量)
    以上这3部分是确定的，也就是不同的程序，以上3部分的大小都各不相同，因程序而异，若未初始化的全局变量定义的多了，那么bss区就大点，反之则小点。
  4. heap,也就是堆，堆在进程空间中是自低地址向高地址增长，你在程序中通过动态申请得到的内存空间(c中一般为malloc/free,c++中一般为new/delete)，就是在堆中动态分配的。
  5. stack,栈，程序中每个函数中的局部变量，都是存放在栈中，栈是自高地址向低地址增长的。起初，堆和栈之间有很大一段空间，然后随着，程序的运行，堆不断向高地址增长，栈不断向高地址增长，这样，堆跟栈之间的空间总有一个最大界限，超过这个最大界限，就会出现堆跟栈重叠，就会出错，所以一般来说，Linux下的进程都有其最大空间的。
  6. 再往上，也就是一个进程地址空间的顶部，存放了命令行参数和环境变量。

Hello World程序在Linux下的诞生与消亡

2.2 Linux进程的状态转换图

1

Linux进程间通信的几种方式总结

2.4.1 管道（TODO）

2.4.2 信号量、互斥体和自旋锁（TODO）

2.5 进程间如何同步(Synchronization)

  1. 因竞争资源发生死锁 现象：系统中供多个进程共享的资源的数目不足以满足全部进程的需要时，就会引起对诸资源的竞争而发生死锁现象

  2. 进程推进顺序不当发生死锁

死锁的四个必要条件

（1）互斥条件：进程对所分配到的资源不允许其他进程进行访问，若其他进程访问该资源，只能等待，直至占有该资源的进程使用完成后释放该资源

（2）请求和保持条件：进程获得一定的资源之后，又对其他资源发出请求，但是该资源可能被其他进程占有，此事请求阻塞，但又对自己获得的资源保持不放

（3）不可剥夺条件：是指进程已获得的资源，在未完成使用之前，不可被剥夺，只能在使用完后自己释放

（4）环路等待条件：是指进程发生死锁后，必然存在一个进程--资源之间的环形链

处理死锁的基本方法

预防死锁（破坏四个必要条件）：

避免死锁（银行家算法）

预防死锁的几种策略，会严重地损害系统性能。因此在避免死锁时，要施加较弱的限制，从而获得 较满意的系统性能。由于在避免死锁的策略中，允许进程动态地申请资源。因而，系统在进行资源分配之前预先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，进程等待。其中最具有代表性的避免死锁算法是银行家算法。

在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。

检测死锁

首先为每个进程和每个资源指定一个唯一的号码；

然后建立资源分配表和进程等待表，例如：

解除死锁

当发现有进程死锁后，便应立即把它从死锁状态中解脱出来，常采用的方法有：

剥夺资源：从其它进程剥夺足够数量的资源给死锁进程，以解除死锁状态；

撤消进程：可以直接撤消死锁进程或撤消代价最小的进程，直至有足够的资源可用，死锁状态.消除为止；所谓代价是指优先级、运行代价、进程的重要性和价值等。

3. 线程

3.1 线程间如何通讯

3.2 线程间同步

3.3 是否需要线程安全

3.4 线程间的同步和互斥是怎么做的

自旋锁

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

5. 内存管理 段式页式

5.1 存储方式：页式段式（TODO）

分段，分页与段页式存储管理

5.2 页面置换算法

在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生 缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。

5.3 缺页中断

页缺失指的是当软件试图访问已映射在虚拟地址空间中，但是目前并未被加载在物理内存中的一个分页时，由中央处理器的内存管理单元所发出的中断。
通常情况下，用于处理此中断的程序是操作系统的一部分。如果操作系统判断此次访问是有效的，那么操作系统会尝试将相关的分页从硬盘上的虚拟内存文件中调入内存。而如果访问是不被允许的，那么操作系统通常会结束相关的进程。

5.4 常见的置换算法

  1. 先进先出置换算法（FIFO）

最简单的页面置换算法是先入先出（FIFO）法。这种算法的实质是，总是选择在主存中停留时间最长（即最老）的一页置换，即先进入内存的页，先退出内存。理由是：最早调入内存的页，其不再被使用的可能性比刚调入内存的可能性大。建立一个FIFO队列，收容所有在内存中的页。被置换页面总是在队列头上进行。当一个页面被放入内存时，就把它插在队尾上。

  1. 最近最久未使用（LRU）算法

它的实质是，当需要置换一页时，选择在之前一段时间里最久没有使用过的页面予以置换。
其问题是怎么确定最后使用时间的顺序，对此有两种可行的办法：

  1. 计数器。最简单的情况是使每个页表项对应一个使用时间字段，并给CPU增加一个逻辑时钟或计数器。每次存储访问，该时钟都加1。每当访问一个页面时，时钟寄存器的内容就被复制到相应页表项的使用时间字段中。这样我们就可以始终保留着每个页面最后访问的“时间”。在置换页面时，选择该时间值最小的页面。这样做， [1] 不仅要查页表，而且当页表改变时（因CPU调度）要 [1] 维护这个页表中的时间，还要考虑到时钟值溢出的问题。
  2. 栈。用一个栈保留页号。每当访问一个页面时，就把它从栈中取出放在栈顶上。这样一来，栈顶总是放有目前使用最多的页，而栈底放着目前最少使用的页。由于要从栈的中间移走一项，所以要用具有头尾指针的双向链连起来。在最坏的情况下，移走一页并把它放在栈顶上需要改动6个指针。每次修改都要有开销，但需要置换哪个页面却可直接得到，用不着查找，因为尾指针指向栈底，其中有被置换页。

6. IO多路复用

6.0 IO五种模型（阻塞IO、非阻塞IO、多路复用IO、信号驱动IO、异步IO）

同步就是当一个进程发起一个函数（任务）调用的时候，一直等待直到函数（任务）完成，而进程继续处于激活状态。而异步情况下是当一个进程发起一个函数（任务）调用的时候，不会等函数返回，而是继续往下执行当，函数返回的时候通过状态、通知、事件等方式通知进程任务完成。

阻塞是当请求不能满足的时候就将进程挂起，而非阻塞则不会阻塞当前进程，即阻塞与非阻塞针对的是进程或线程而同步与异步所针对的是功能函数。

IO复用：为了解释这个名词，首先来理解下复用这个概念，复用也就是共用的意思，这样理解还是有些抽象，为此，咱们来理解下复用在通信领域的使用，在通信领域中为了充分利用网络连接的物理介质，往往在同一条网络链路上采用时分复用或频分复用的技术使其在同一链路上传输多路信号，到这里我们就基本上理解了复用的含义，即公用某个“介质”来尽可能多的做同一类(性质)的事，那IO复用的“介质”是什么呢？为此我们首先来看看服务器编程的模型，客户端发来的请求服务端会产生一个进程来对其进行服务，每当来一个客户请求就产生一个进程来服务，然而进程不可能无限制的产生，因此为了解决大量客户端访问的问题，引入了IO复用技术，即：一个进程可以同时对多个客户请求进行服务。

同步 ： 自己亲自出马持银行卡到银行取钱（使用同步IO时，Java自己处理IO读写）；
异步 ： 委托一小弟拿银行卡到银行取钱，然后给你（使用异步IO时，Java将IO读写委托给OS处理，需要将数据缓冲区地址和大小传给OS(银行卡和密码)，OS需要支持异步IO操作API）；
阻塞 ： ATM排队取款，你只能等待（使用阻塞IO时，Java调用会一直阻塞到读写完成才返回）；
非阻塞 ： 柜台取款，取个号，然后坐在椅子上做其它事，等号广播会通知你办理，没到号你就不能去，你可以不断问大堂经理排到了没有，大堂经理如果说还没到你就不能去（使用非阻塞IO时，如果不能读写Java调用会马上返回，当IO事件分发器会通知可读写时再继续进行读写，不断循环直到读写完成）

IO五种模型（阻塞IO、非阻塞IO、多路复用IO、信号驱动IO、异步IO）:

select，poll，epoll都是IO多路复用的机制。I/O多路复用就通过一种机制，可以监视多个描述符，一旦某个描述符就绪（一般是读就绪或者写就绪），能够通知程序进行相应的读写操作。

6.1 前言：系统层面概念说明

在进行解释之前，首先要说明几个概念：

6.1.1 用户空间与内核空间

现在操作系统都是采用虚拟存储器，那么对32位操作系统而言，它的寻址空间（虚拟存储空间）为4G（2的32次方）。操作系统的核心是内核，独立于普通的应用程序，可以访问受保护的内存空间，也有访问底层硬件设备的所有权限。为了保证用户进程不能直接操作内核（kernel），保证内核的安全，操心系统将虚拟空间划分为两部分，一部分为内核空间，一部分为用户空间。针对linux操作系统而言，将最高的1G字节（从虚拟地址0xC0000000到0xFFFFFFFF），供内核使用，称为内核空间，而将较低的3G字节（从虚拟地址0x00000000到0xBFFFFFFF），供各个进程使用，称为用户空间。

6.1.2 进程切换

为了控制进程的执行，内核必须有能力挂起正在CPU上运行的进程，并恢复以前挂起的某个进程的执行。这种行为被称为进程切换。因此可以说，任何进程都是在操作系统内核的支持下运行的，是与内核紧密相关的。

从一个进程的运行转到另一个进程上运行，这个过程中经过下面这些变化：

  1. 保存处理机上下文，包括程序计数器和其他寄存器。
  2. 更新PCB信息。
  3. 把进程的PCB移入相应的队列，如就绪、在某事件阻塞等队列。
  4. 选择另一个进程执行，并更新其PCB。
  5. 更新内存管理的数据结构。
  6. 恢复处理机上下文。

注：总而言之就是很耗资源。

6.1.3 进程的阻塞

正在执行的进程，由于期待的某些事件未发生，如请求系统资源失败、等待某种操作的完成、新数据尚未到达或无新工作做等，则由系统自动执行阻塞原语(Block)，使自己由运行状态变为阻塞状态。可见，进程的阻塞是进程自身的一种主动行为，也因此只有处于运行态的进程（获得CPU），才可能将其转为阻塞状态。

当进程进入阻塞状态，是不占用CPU资源的。

6.1.4 文件描述符

文件描述符（File descriptor）是计算机科学中的一个术语，是一个用于表述指向文件的引用的抽象化概念。

文件描述符在形式上是一个非负整数。实际上，它是一个索引值，指向内核为每一个进程所维护的该进程打开文件的记录表。当程序打开一个现有文件或者创建一个新文件时，内核向进程返回一个文件描述符。在程序设计中，一些涉及底层的程序编写往往会围绕着文件描述符展开。但是文件描述符这一概念往往只适用于UNIX、Linux这样的操作系统。

6.1.5 缓存 I/O

缓存 I/O 又被称作标准 I/O，大多数文件系统的默认 I/O 操作都是缓存 I/O。在 Linux 的缓存 I/O 机制中，操作系统会将 I/O 的数据缓存在文件系统的页缓存（ page cache ）中，也就是说，数据会先被拷贝到操作系统内核的缓冲区中，然后才会从操作系统内核的缓冲区拷贝到应用程序的地址空间。

所以，I/O 多路复用的特点是通过一种机制一个进程能同时等待多个文件描述符，而这些文件描述符（套接字描述符）其中的任意一个进入读就绪状态，select()函数就可以返回。

所以，如果处理的连接数不是很高的话，使用select/epoll的web server不一定比使用多线程multi-threading + 阻塞blocking IO的web server性能更好，可能延迟还更大。select/epoll的优势并不是对于单个连接能处理得更快，而是在于能处理更多的连接。）

在IO多路复用中，实际中，对于每一个socket，一般都设置成为非阻塞non-blocking，但是，整个用户的process其实是一直被阻塞block的。只不过process是被select这个函数block，而不是被socket IO给block。

6.3 select、poll、epoll详解

6.3.1 select

select的工作流程： 单个进程就可以同时处理多个网络连接的io请求（同时阻塞多个io操作）。基本原理就是程序呼叫select，然后整个程序就阻塞了，这时候，select会将需要监控的readfds集合拷贝到内核空间（假设监控的仅仅是socket可读），kernel就会轮询检查所有select负责的fd，当找到一个client中的数据准备好了，select就会返回，这个时候程序就会系统调用，将数据从kernel复制到进程缓冲区。

通过上面的select逻辑过程分析，相信大家都意识到，select存在两个问题：

  1. 被监控的fds需要从用户空间拷贝到内核空间。为了减少数据拷贝带来的性能损坏，内核对被监控的fds集合大小做了限制，并且这个是通过宏控制的，大小不可改变(限制为1024)。
  2. 被监控的fds集合中，只要有一个有数据可读，整个socket集合就会被遍历一次调用sk的poll函数收集可读事件。由于当初的需求是朴素，仅仅关心是否有数据可读这样一个事件，当事件通知来的时候，由于数据的到来是异步的，我们不知道事件来的时候，有多少个被监控的socket有数据可读了，于是，只能挨个遍历每个socket来收集可读事件。

6.3.2 Poll

poll的原理与select非常相似，差别如下：

poll机制虽然改进了select的监控大小1024的限制，但以下两个性能问题还没有解决。略显鸡肋。

  1. fds集合需要从用户空间拷贝到内核空间的问题，我们希望不需要拷贝
  2. 当被监控的fds中某些有数据可读的时候，我们希望通知更加精细一点，就是我们希望能够从通知中得到有可读事件的fds列表，而不是需要遍历整个fds来收集。

    6.3.3 epoll 解决问题

    假设现实中，有1百万个客户端同时与一个服务器保持着tcp连接，而每一个时刻，通常只有几百上千个tcp连接是活跃的，这时候我们仍然使用select/poll机制，kernel必须在搜寻完100万个fd之后，才能找到其中状态是active的，这样资源消耗大而且效率低下。

(a) fds集合拷贝问题的解决

对于IO多路复用，有两件事是必须要做的(对于监控可读事件而言)：1. 准备好需要监控的fds集合；2. 探测并返回fds集合中哪些fd可读了。细看select或poll的函数原型，我们会发现，每次调用select或poll都在重复地准备(集中处理)整个需要监控的fds集合。然而对于频繁调用的select或poll而言，fds集合的变化频率要低得多，我们没必要每次都重新准备(集中处理)整个fds集合。

于是，epoll引入了epoll_ctl系统调用，将高频调用的epoll_wait和低频的epoll_ctl隔离开。同时，epoll_ctl通过(EPOLL_CTL_ADD、EPOLL_CTL_MOD、EPOLL_CTL_DEL)三个操作来分散对需要监控的fds集合的修改，做到了有变化才变更，将select/poll高频、大块内存拷贝(集中处理)变成epoll_ctl的低频、小块内存的拷贝(分散处理)，避免了大量的内存拷贝。

(b) 按需遍历就绪的fds集合

为了做到只遍历就绪的fd，我们需要有个地方来组织那些已经就绪的fd。为此，epoll引入了一个中间层，一个双向链表(ready_list)，一个单独的睡眠队列(single_epoll_wait_list)，并且，与select或poll不同的是，epoll的process不需要同时插入到多路复用的socket集合的所有睡眠队列中，相反process只是插入到中间层的epoll的单独睡眠队列中，process睡眠在epoll的单独队列上，等待事件的发生。

6.3.4 小结

就像一本书有封面、目录和正文一样。在文件系统中，超级块就相当于封面，从封面可以得知这本书的基本信息； inode 块相当于目录，从目录可以得知各章节内容的位置；而数据块则相当于书的正文，记录着具体内容。

7.2 Inode是什么

三、计算机网络

1. 七层网络结构

3

  1. 物理层
  2. 数据链路层
    • 数据链路层为网络层提供可靠的数据传输；
    • 基本数据单位为帧；
    • 主要的协议：以太网协议；
  3. 网络层
    网络层中涉及众多的协议，其中包括最重要的协议，也是TCP/IP的核心协议——IP协议。IP协议非常简单，仅仅提供不可靠、无连接的传送服务。IP协议的主要功能有：无连接数据报传输、数据报路由选择和差错控制。与IP协议配套使用实现其功能的还有地址解析协议ARP、逆地址解析协议RARP、因特网报文协议ICMP、因特网组管理协议IGMP。具体的协议我们会在接下来的部分进行总结，有关网络层的重点为：
    • IP协议（Internet Protocol，因特网互联协议）;
    • ICMP协议（Internet Control Message Protocol，因特网控制报文协议）;
    • ARP协议（Address Resolution Protocol，地址解析协议）;
    • RARP协议（Reverse Address Resolution Protocol，逆地址解析协议）。
  4. 传输层
    • 传输层负责将上层数据分段并提供端到端的、可靠的或不可靠的传输以及端到端的差错控制和流量控制问题；
    • TCP协议（Transmission Control Protocol，传输控制协议）
    • UDP协议（User Datagram Protocol，用户数据报协议）；
  5. 会话层
  6. 表示层
  7. 应用层
    • 数据传输基本单位为报文；
    • 包含的主要协议：FTP（文件传送协议）、Telnet（远程登录协议）、DNS（域名解析协议）、SMTP（邮件传送协议），POP3协议（邮局协议），HTTP协议（Hyper Text Transfer Protocol）。

      2. TCP/IP协议

      TCP/IP协议是Internet最基本的协议、Internet国际互联网络的基础，由网络层的IP协议和传输层的TCP协议组成。通俗而言：TCP负责发现传输的问题，一有问题就发出信号，要求重新传输，直到所有数据安全正确地传输到目的地。而IP是给因特网的每一台联网设备规定一个地址。

IP层接收由更低层（网络接口层例如以太网设备驱动程序）发来的数据包，并把该数据包发送到更高层---TCP或UDP层；相反，IP层也把从TCP或UDP层接收来的数据包传送到更低层。IP数据包是不可靠的，因为IP并没有做任何事情来确认数据包是否按顺序发送的或者有没有被破坏，IP数据包中含有发送它的主机的地址（源地址）和接收它的主机的地址（目的地址）。

TCP是面向连接的通信协议，通过三次握手建立连接，通讯完成时要拆除连接，由于TCP是面向连接的所以只能用于端到端的通讯。TCP提供的是一种可靠的数据流服务，采用“带重传的肯定确认”技术来实现传输的可靠性。TCP还采用一种称为“滑动窗口”的方式进行流量控制，所谓窗口实际表示接收能力，用以限制发送方的发送速度。

4

2.1 TCP重要知识点

2.1.1 三次握手

TCP连接建立过程：首先Client端发送连接请求报文，Server段接受连接后回复ACK报文，并为这次连接分配资源。Client端接收到ACK报文后也向Server段发生ACK报文，并分配资源，这样TCP连接就建立了。

为什么要三次挥手？

在只有两次“握手”的情形下，假设Client想跟Server建立连接，但是却因为中途连接请求的数据报丢失了，故Client端不得不重新发送一遍；这个时候Server端仅收到一个连接请求，因此可以正常的建立连接。但是，有时候Client端重新发送请求不是因为数据报丢失了，而是有可能数据传输过程因为网络并发量很大在某结点被阻塞了，这种情形下Server端将先后收到2次请求，并持续等待两个Client请求向他发送数据...问题就在这里，Cient端实际上只有一次请求，而Server端却有2个响应，极端的情况可能由于Client端多次重新发送请求数据而导致Server端最后建立了N多个响应在等待，因而造成极大的资源浪费！所以，“三次握手”很有必要！

2.1.2 四次挥手

TCP连接断开过程：假设Client端发起中断连接请求，也就是发送FIN报文。Server端接到FIN报文后，意思是说"我Client端没有数据要发给你了"，但是如果你还有数据没有发送完成，则不必急着关闭Socket，可以继续发送数据。所以你先发送ACK，"告诉Client端，你的请求我收到了，但是我还没准备好，请继续你等我的消息"。这个时候Client端就进入FIN_WAIT状态，继续等待Server端的FIN报文。当Server端确定数据已发送完成，则向Client端发送FIN报文，"告诉Client端，好了，我这边数据发完了，准备好关闭连接了"。Client端收到FIN报文后，"就知道可以关闭连接了，但是他还是不相信网络，怕Server端不知道要关闭，所以发送ACK后进入TIME_WAIT状态，如果Server端没有收到ACK则可以重传。“，Server端收到ACK后，"就知道可以断开连接了"。Client端等待了2MSL后依然没有收到回复，则证明Server端已正常关闭，那好，我Client端也可以关闭连接了。Ok，TCP连接就这样关闭了！

为什么要四次挥手？

试想一下，假如现在你是客户端你想断开跟Server的所有连接该怎么做？第一步，你自己先停止向Server端发送数据，并等待Server的回复。但事情还没有完，虽然你自身不往Server发送数据了，但是因为你们之前已经建立好平等的连接了，所以此时他也有主动权向你发送数据；故Server端还得终止主动向你发送数据，并等待你的确认。其实，说白了就是保证双方的一个合约的完整执行！

2.1.3 TIME-WAIT 和 CLOSE-WAIT 的区别

TCP协议规定，对于已经建立的连接，网络双方要进行四次握手才能成功断开连接，如果缺少了其中某个步骤，将会使连接处于假死状态，连接本身占用的资源不会被释放。网络服务器程序要同时管理大量连接，所以很有必要保证无用连接完全断开，否则大量僵死的连接会浪费许多服务器资源。在众多TCP状态中，最值得注意的状态有两个：CLOSE_WAIT和TIME_WAIT。

TIME_WAIT

TIME_WAIT 是主动关闭链接时形成的，等待2MSL时间，约4分钟。主要是防止最后一个ACK丢失。 由于TIME_WAIT 的时间会非常长，因此server端应尽量减少主动关闭连接

CLOSE_WAIT CLOSE_WAIT是被动关闭连接是形成的。根据TCP状态机，服务器端收到客户端发送的FIN，则按照TCP实现发送ACK，因此进入CLOSE_WAIT状态。但如果服务器端不执行close()，就不能由CLOSE_WAIT迁移到LAST_ACK，则系统中会存在很多CLOSE_WAIT状态的连接。此时，可能是系统忙于处理读、写操作，而未将已收到FIN的连接，进行close。此时，recv/read已收到FIN的连接socket，会返回0。

为什么需要 TIME_WAIT 状态？ 假设最终的ACK丢失，server将重发FIN，client必须维护TCP状态信息以便可以重发最终的ACK，否则会发送RST，结果server认为发生错误。TCP实现必须可靠地终止连接的两个方向(全双工关闭)，client必须进入 TIME_WAIT 状态，因为client可能面 临重发最终ACK的情形。

为什么 TIME_WAIT 状态需要保持 2MSL 这么长的时间？ 如果 TIME_WAIT 状态保持时间不足够长(比如小于2MSL)，第一个连接就正常终止了。第二个拥有相同相关五元组的连接出现，而第一个连接的重复报文到达，干扰了第二个连接。TCP实现必须防止某个连接的重复报文在连接终止后出现，所以让TIME_WAIT状态保持时间足够长(2MSL)，连接相应方向上的TCP报文要么完全响应完毕，要么被丢弃。建立第二个连接的时候，不会混淆。

TIME_WAIT 和CLOSE_WAIT状态socket过多

如果服务器出了异常，百分之八九十都是下面两种情况：

  1. 服务器保持了大量TIME_WAIT状态
  2. 服务器保持了大量CLOSE_WAIT状态，简单来说CLOSE_WAIT数目过大是由于被动关闭连接处理不当导致的。

因为linux分配给一个用户的文件句柄是有限的，而TIME_WAIT和CLOSE_WAIT两种状态如果一直被保持，那么意味着对应数目的通道就一直被占着，而且是“占着茅坑不使劲”，一旦达到句柄数上限，新的请求就无法被处理了，接着就是大量Too Many Open Files异常，Tomcat崩溃。

2.1.4 流量控制和拥塞控制

利用滑动窗口实现流量控制

定义: 流量控制往往指的是点对点通信量的控制，是个端到端的问题。流量控制所要做的就是控制发送端发送数据的速率，以便使接收端来得及接受。如果发送方把数据发送得过快，接收方可能会来不及接收，这就会造成数据的丢失。所谓流量控制就是让发送方的发送速率不要太快，要让接收方来得及接收。

设A向B发送数据。在连接建立时，B告诉了A：“我的接收窗口是 rwnd = 400 ”(这里的 rwnd 表示 receiver window) 。因此，发送方的发送窗口不能超过接收方给出的接收窗口的数值。请注意，TCP的窗口单位是字节，不是报文段。TCP连接建立时的窗口协商过程在图中没有显示出来。再设每一个报文段为100字节长，而数据报文段序号的初始值设为1。大写ACK表示首部中的确认位ACK，小写ack表示确认字段的值ack。 20140509220855687

从图中可以看出，B进行了三次流量控制。第一次把窗口减少到 rwnd = 300 ，第二次又减到了 rwnd = 100 ，最后减到 rwnd = 0 ，即不允许发送方再发送数据了。这种使发送方暂停发送的状态将持续到主机B重新发出一个新的窗口值为止。B向A发送的三个报文段都设置了 ACK = 1 ，只有在ACK=1时确认号字段才有意义。

拥塞控制

定义: 在某段时间，若对网络中某资源的需求超过了该资源所能提供的可用部分，网络的性能就要变坏。

20140509221015859

  1. 慢开始：在主机刚刚开始发送报文段时可先将拥塞窗口 cwnd 设置为一个最大报文段 MSS 的数值。在每收到一个对新的报文段的确认后，将拥塞窗口增加至多一个 MSS 的数值。用这样的方法逐步增大发送端的拥塞窗口 cwnd，可以使分组注入到网络的速率更加合理。每经过一个传输轮回，拥塞窗口(发送端)就加倍。
  2. 拥塞避免：让拥塞窗口缓慢增大，每经过一个往返时间就加1，而不是加倍，按线性规律缓慢增长。拥塞窗口大于慢开始门限，就执行拥塞避免算法。“乘法减小”：指不论在慢开始还是拥塞避免阶段，只要出现超时重传就把慢开始门限值减半。"加分增大“:指执行拥塞避免算法后，使拥塞窗口缓慢增大，以防止网络过早出现拥塞。合起来叫AIMD算法。
  3. 快重传算法：发送方只要一连收到三个重复确认就应当重传对方尚未收到的报文。而不必等到该分组的重传计时器到期。
  4. 快恢复算法：(1)当发送端收到连续三个重复的确认时，就执行“乘法减小”算法，把慢开始门限 ssthresh 减半。但接下去不执行慢开始算法。(2)由于发送方现在认为网络很可能没有发生拥塞，因此现在不执行慢开始算法，即拥塞窗口 cwnd 现在不设置为 1，而是设置为慢开始门限 ssthresh 减半后的数值，然后开始执行拥塞避免算法（“加法增大”），使拥塞窗口缓慢地线性增大.

3. UDP协议

UDP与TCP位于同一层，但它不管数据包的顺序、错误或重发。因此，UDP不被应用于那些使用虚电路的面向连接的服务，UDP主要用于那些面向查询---应答的服务，例如NFS。相对于FTP或Telnet，这些服务需要交换的信息量较小。

3.1 TCP 与 UDP 的区别

TCP是面向连接的，可靠的字节流服务；UDP是面向无连接的，不可靠的数据报服务。 20151018103115179

TCP的优点

TCP的缺点

UDP的优点

UDP的缺点

I. 所谓 安全的 意味着该操作用于获取信息而非修改信息。换句话说，GET请求一般不应产生副作用。就是说，它仅仅是获取资源信息，就像数据库查询一样，不会修改，增加数据，不会影响资源的状态。

II. 幂等 的意味着对同一URL的多个请求应该返回同样的结果。

  • GET在浏览器回退时是无害的，而POST会再次提交请求。
  • GET请求会被浏览器主动cache，而POST不会，除非手动设置。
  • GET请求只能进行url编码，而POST支持多种编码方式。
  • GET请求参数会被完整保留在浏览器历史记录里，而POST中的参数不会被保留
  • GET请求在URL中传送的参数是有长度限制的，而POST么有。
  • GET参数通过URL传递，POST放在Request body中。

但GET和POST本质上没有区别 GET和POST是什么？HTTP协议中的两种发送请求的方法。
HTTP是什么？HTTP是基于TCP/IP的关于数据如何在万维网中如何通信的协议。

TCP就像汽车，我们用TCP来运输数据，它很可靠，从来不会发生丢件少件的现象。但是如果路上跑的全是看起来一模一样的汽车，那这个世界看起来是一团混乱，送急件的汽车可能被前面满载货物的汽车拦堵在路上，整个交通系统一定会瘫痪。为了避免这种情况发生，交通规则HTTP诞生了。HTTP给汽车运输设定了好几个服务类别，有GET, POST, PUT, DELETE等等，HTTP规定，当执行GET请求的时候，要给汽车贴上GET的标签（设置method为GET），而且要求把传送的数据放在车顶上（url中）以方便记录。如果是POST请求，就要在车上贴上POST的标签，并把货物放在车厢里。当然，你也可以在GET的时候往车厢内偷偷藏点货物，但是这是很不光彩；也可以在POST的时候在车顶上也放一些数据，让人觉得傻乎乎的。HTTP只是个行为准则，而TCP才是GET和POST怎么实现的基本。

GET和POST本质上就是TCP链接，并无差别。但是由于HTTP的规定和浏览器/服务器的限制，导致他们在应用过程中体现出一些不同。

GET和POST还有一个重大区别，简单的说：

GET产生一个TCP数据包；POST产生两个TCP数据包。

也就是说，GET只需要汽车跑一趟就把货送到了，而POST得跑两趟，第一趟，先去和服务器打个招呼“嗨，我等下要送一批货来，你们打开门迎接我”，然后再回头把货送过去。

因为POST需要两步，时间上消耗的要多一点，看起来GET比POST更有效。因此Yahoo团队有推荐用GET替换POST来优化网站性能。但这是一个坑！跳入需谨慎。为什么？

  1. GET与POST都有自己的语义，不能随便混用。

  2. 据研究，在网络环境好的情况下，发一次包的时间和发两次包的时间差别基本可以无视。而在网络环境差的情况下，两次包的TCP在验证数据包完整性上，有非常大的优点。

  3. 并不是所有浏览器都会在POST中发送两次包，Firefox就只发送一次。

    99%的人都理解错了HTTP中GET与POST的区别

4.2 HTTP流程

HTTP 把客户端浏览器的请求发送到服务器，并把相应的网页内容由服务器返回客户端浏览器。

1. 地址解析

如用客户端浏览器请求这个页面：http://localhost.com:8080/index.htm

从中分解出协议名、主机名、端口、对象路径等部分，对于我们的这个地址，解析得到的结果如下：

在这一步，需要 域名系统DNS 解析域名 localhost.com,得主机的IP地址。

2. 封装HTTP请求数据包

把以上部分结合本机自己的信息，封装成一个HTTP请求数据包

3. 封装成TCP包，建立TCP连接（TCP的三次握手）

在HTTP 工作开始之前，客户机（Web浏览器）首先要通过网络与服务器建立连接，该连接是通过TCP来完成的，该协议与IP协议共同构建Internet，即著名 的TCP/IP协议族，因nternet又被称作是TCP/IP网络。HTTP是比TCP更高层次的应用层协议，根据规则，只有低层协议建立之后才 能，才能进行更层协议的连接，因此，首先要建立TCP连接，一般TCP连接的端口号是80。这里是8080端口

4. 客户机发送请求命令

建立连接后，客户机发送一个请求给服务器，请求方式的格式为：统一资源标识符（URL）、协议版本号，后边是MIME信息包括请求修饰符、客户机信息和可内容。

5. 服务器响应

服务器接到请求后，给予相应的响应信息，其格式为一个状态行，包括信息的协议版本号、一个成功或错误的代码，后边是MIME信息包括服务器信息、实体信息和可能的内容。

实体消息是服务器向浏览器发送头信息后，它会发送一个空白行来表示头信息的发送到此为结束，接着，它就以Content-Type应答头信息所描述的格式发送用户所请求的实际数据

6. 服务器关闭TCP连接

一般情况下，一旦Web服务器向浏览器发送了请求数据，它就要关闭TCP连接，然后如果浏览器或者服务器在其头信息加入了这行代码

Connection:keep-alive

TCP连接在发送后将仍然保持打开状态，于是，浏览器可以继续通过相同的连接发送请求。保持连接节省了为每个请求建立新连接所需的时间，还节约了网络带宽。

客户机发起一次请求的时候：

客户机会将请求封装成http数据包-->封装成Tcp数据包-->封装成Ip数据包--->封装成数据帧--->硬件将帧数据转换成bit流（二进制数据）-->最后通过物理硬件（网卡芯片）发送到指定地点。

服务器硬件首先收到bit流....... 然后转换成ip数据包。于是通过ip协议解析Ip数据包，然后又发现里面是tcp数据包，就通过tcp协议解析Tcp数据包，接着发现是http数据包通过http协议再解析http数据包得到数

小结：输入一个网站执行后的过程

事件顺序

  1. 浏览器获取输入的域名 www.baidu.com
  2. 浏览器向DNS请求解析www.baidu.com的IP地址
  3. 域名系统DNS解析出百度服务器的IP地址
    • 客户端浏览器通过DNS解析到www.baidu.com的IP地址220.181.27.48，通过这个IP地址找到客户端到服务器的路径。客户端浏览器发起一个HTTP会话到220.161.27.48，然后通过TCP进行封装数据包，输入到网络层。
  4. 浏览器与该服务器建立TCP连接(默认端口号80)
    • 在客户端的传输层，把HTTP会话请求分成报文段，添加源和目的端口，如服务器使用80端口监听客户端的请求，客户端由系统随机选择一个端口如5000，与服务器进行交换，服务器把相应的请求返回给客户端的5000端口。然后使用IP层的IP地址查找目的端。
  5. 浏览器发出HTTP请求，请求百度首页
    • 客户端的网络层不用关系应用层或者传输层的东西，主要做的是通过查找路由表确定如何到达服务器，期间可能经过多个路由器，这些都是由路由器来完成的工作，不作过多的描述，无非就是通过查找路由表决定通过那个路径到达服务器。
    • 客户端的链路层，包通过链路层发送到路由器，通过邻居协议查找给定IP地址的MAC地址，然后发送ARP请求查找目的地址，如果得到回应后就可以使用ARP的请求应答交换的IP数据包现在就可以传输了，然后发送IP数据包到达服务器的地址。
  6. 服务器通过HTTP响应把首页文件发送给浏览器
  7. TCP连接释放
  8. 浏览器将首页文件进行解析，并将Web页显示给用户。

涉及到的协议

  1. 应用层：HTTP(WWW访问协议)，DNS(域名解析服务)DNS解析域名为目的IP，通过IP找到服务器路径，客户端向服务器发起HTTP会话，然后通过运输层TCP协议封装数据包，在TCP协议基础上进行传输
  2. 传输层：TCP(为HTTP提供可靠的数据传输)，UDP(DNS使用UDP传输) HTTP会话会被分成报文段，添加源、目的端口；TCP协议进行主要工作
  3. 网络层：IP(IP数据数据包传输和路由选择)，ICMP(提供网络传输过程中的差错检测)，ARP(将本机的默认网关IP地址映射成物理MAC地址)为数据包选择路由，IP协议进行主要工作

HTTP协议概念及工作流程

4.3. HTTP与HTTPS的关系

HTTPS是在HTTP上建立SSL加密层，并对传输数据进行加密，是HTTP协议的安全版。http和https使用的是完全不同的连接方式，用的端口也不一样，前者是80，后者是443。

https = http + ssl

SSL介于应用层和TCP层之间。应用层数据不再直接传递给传输层，而是传递给SSL层，SSL层对从应用层收到的数据进行加密，并增加自己的SSL头。

有两种基本的加解密算法类型：

  1. 对称加密（symmetrcic encryption）：密钥只有一个，加密解密为同一个密码，且加解密速度快，典型的对称加密算法有DES、AES，RC5，3DES等；

    • 对称加密主要问题是共享秘钥，除你的计算机（客户端）知道另外一台计算机（服务器）的私钥秘钥，否则无法对通信流进行加密解密。解决这个问题的方案非对称秘钥。

  2. 非对称加密：使用两个秘钥：公共秘钥和私有秘钥。私有秘钥由一方密码保存（一般是服务器保存），另一方任何人都可以获得公共秘钥。

    • 这种密钥成对出现（且根据公钥无法推知私钥，根据私钥也无法推知公钥），加密解密使用不同密钥（公钥加密需要私钥解密，私钥加密需要公钥解密），相对对称加密速度较慢，典型的非对称加密算法有RSA、DSA等。

过程大致如下：

  1. SSL客户端通过TCP和服务器建立连接之后（443端口），并且在一般的tcp连接协商（握手）过程中请求证书。

    • 即客户端发出一个消息给服务器，这个消息里面包含了自己可实现的算法列表和其它一些需要的消息，SSL的服务器端会回应一个数据包，这里面确定了这次通信 所需要的算法，然后服务器向客户端返回证书。（证书里面包含了服务器信息：域名。申请证书的公司，公共秘钥）。

  2. Client在收到服务器返回的证书后，判断签发这个证书的公共签发机构，并使用这个机构的公共秘钥确认签名是否有效，客户端还会确保证书中列出的域名就是它正在连接的域名。

  3. 如果确认证书有效，那么生成对称秘钥并使用服务器的公共秘钥进行加密。然后发送给服务器，服务器使用它的私钥对它进行解密，这样两台计算机可以开始进行对称加密进行通信。

4.4 HTTP错误代码

四、数据库

1. 底层原理

1.1 B树 B+树

B-树,这类似普通的平衡二叉树，不同的一点是B-树允许每个节点有更多的子节点。下图是 B-树的简化图 1 B+树是B-树的变体，也是一种多路搜索树, 它与 B- 树的不同之处在于:

简化 B+树 如下图 2

1.2 为什么使用B-/B+ Tree

红黑树等数据结构也可以用来实现索引，但是文件系统及数据库系统普遍采用B-/+Tree作为索引结构。MySQL 是基于磁盘的数据库系统,索引往往以索引文件的形式存储的磁盘上,索引查找过程中就要产生磁盘I/O消耗,相对于内存存取，I/O存取的消耗要高几个数量级,索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。为什么使用B-/+Tree，还跟磁盘存取原理有关。

由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用。程序运行期间所需要的数据通常比较集中。

由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。

由于磁盘的存取速度与内存之间鸿沟,为了提高效率,要尽量减少磁盘I/O.磁盘往往不是严格按需读取，而是每次都会预读,磁盘读取完需要的数据,会顺序向后读一定长度的数据放入内存。而这样做的理论依据是计算机科学中著名的局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用，程序运行期间所需要的数据通常比较集中

1.3 索引为什么使用 B+树

一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。而B-/+/*Tree，经过改进可以有效的利用系统对磁盘的块读取特性，在读取相同磁盘块的同时，尽可能多的加载索引数据，来提高索引命中效率，从而达到减少磁盘IO的读取次数。

Mysql是一种关系型数据库，区间访问是常见的一种情况，B+树叶节点增加的链指针,加强了区间访问性，可使用在范围区间查询等，而B-树每个节点 key 和 data 在一起，则无法区间查找。

由 B-/B+树看 MySQL索引结构 数据库索引为什么使用B+树？

2. 索引

索引优化是对查询性能优化的最有效手段，它能够轻松地将查询的性能提高几个数量级。

InnoDB 存储引擎在绝大多数情况下使用 B+ 树建立索引，这是关系型数据库中查找最为常用和有效的索引，但是 B+ 树索引并不能找到一个给定键对应的具体值，它只能找到数据行对应的页，然后正如上一节所提到的，数据库把整个页读入到内存中，并在内存中查找具体的数据行。

B+ 树是平衡树，它查找任意节点所耗费的时间都是完全相同的，比较的次数就是 B+ 树的高度；

2.1 聚集索引和辅助索引

数据库中的 B+ 树索引可以分为聚集索引（clustered index）和辅助索引（secondary index），它们之间的最大区别就是，聚集索引中存放着一条行记录的全部信息，而辅助索引中只包含索引列和一个用于查找对应行记录的『书签』。

2.1.1 聚集索引

InnoDB 存储引擎中的表都是使用索引组织的，也就是按照键的顺序存放；该索引中键值的逻辑顺序决定了表中相应行的物理顺序。 聚集索引就是按照表中主键的顺序构建一颗 B+ 树，并在叶节点中存放表中的行记录数据。

在数据库中创建一张表，B+ 树就会使用 id 作为索引的键，并在叶子节点中存储一条记录中的所有信息。

聚集索引对于那些经常要搜索范围值的列特别有效。使用聚集索引找到包含第一个值的行后，便可以确保包含后续索引值的行在物理相邻。例如，如果应用程序执行 的一个查询经常检索某一日期范围内的记录，则使用聚集索引可以迅速找到包含开始日期的行，然后检索表中所有相邻的行，直到到达结束日期。这样有助于提高此 类查询的性能。同样，如果对从表中检索的数据进行排序时经常要用到某一列，则可以将该表在该列上聚集（物理排序），避免每次查询该列时都进行排序，从而节 省成本。 　　　　 当索引值唯一时，使用聚集索引查找特定的行也很有效率。例如，使用唯一雇员 ID 列 emp_id 查找特定雇员的最快速的方法，是在 emp_id 列上创建聚集索引或 PRIMARY KEY 约束。

2.1.2 辅助索引（非聚集索引）

该索引中索引的逻辑顺序与磁盘上行的物理存储顺序不同。

  • 聚集索引一个表只能有一个，而非聚集索引一个表可以存在多个，这个跟没问题没差别，一般人都知道。
  • 聚集索引存储记录是物理上连续存在，而非聚集索引是逻辑上的连续，物理存储并不连续，这个大家也都知道。

2.2 索引使用策略及优化

MySQL的优化主要分为结构优化（Scheme optimization）和查询优化（Query optimization）。本章的内容完全基于上文的理论基础，实际上一旦理解了索引背后的机制，那么选择高性能的策略就变成了纯粹的推理，并且可以理解这些策略背后的逻辑。

2.2.1 联合索引及最左前缀原理

a. 联合索引（复合索引）

首先介绍一下联合索引。联合索引其实很简单，相对于一般索引只有一个字段，联合索引可以为多个字段创建一个索引。它的原理也很简单，比如，我们在（a,b,c）字段上创建一个联合索引，则索引记录会首先按照A字段排序，然后再按照B字段排序然后再是C字段，因此，联合索引的特点就是：

其实联合索引的查找就跟查字典是一样的，先根据第一个字母查，然后再根据第二个字母查，或者只根据第一个字母查，但是不能跳过第一个字母从第二个字母开始查。这就是所谓的最左前缀原理。

b. 前缀索引

除了联合索引之外，对mysql来说其实还有一种前缀索引。前缀索引就是用列的前缀代替整个列作为索引key，当前缀长度合适时，可以做到既使得前缀索引的选择性接近全列索引，同时因为索引key变短而减少了索引文件的大小和维护开销。

一般来说以下情况可以使用前缀索引：

2.2.2 索引优化策略

2.2.3 索引使用的注意点

  1. 一般说来，索引应建立在那些将用于JOIN,WHERE判断和ORDER BY排序的字段上。尽量不要对数据库中某个含有大量重复的值的字段建立索引。对于一个ENUM类型的字段来说，出现大量重复值是很有可能的情况。
  2. 应尽量避免在 where 子句中对字段进行 null 值判断，否则将导致引擎放弃使用索引而进行全表扫描。最好不要给数据库留NULL，尽可能的使用 NOT NULL填充数据库.
  3. 应尽量避免在 where 子句中使用 != 或 <> 操作符，否则将引擎放弃使用索引而进行全表扫描。
  4. 应尽量避免在 where 子句中使用 or 来连接条件，如果一个字段有索引，一个字段没有索引，将导致引擎放弃使用索引而进行全表扫描。
  5. 一般情况下不鼓励使用like操作，如果非使用不可，如何使用也是一个问题。like “%aaa%” 不会使用索引，而like “aaa%”可以使用索引。

数据库索引原理及优化 MySQL优化系列（三）--索引的使用、原理和设计优化

3. 锁

3.1 乐观锁与悲观锁

乐观锁和悲观锁其实都是并发控制的机制，同时它们在原理上就有着本质的差别；

悲观锁

正如其名，它指的是对数据被外界（包括本系统当前的其他事务，以及来自外部系统的事务处理）修改持保守态度(悲观)，因此，在整个数据处理过程中，将数据处于锁定状态。 悲观锁的实现，往往依靠数据库提供的锁机制 （也只有数据库层提供的锁机制才能真正保证数据访问的排他性，否则，即使在本系统中实现了加锁机制，也无法保证外部系统不会修改数据）

它假设多用户并发的事务在处理时不会彼此互相影响，各事务能够在不产生锁的情况下处理各自影响的那部分数据。在提交数据更新之前，每个事务会先检查在该事务读取数据后，有没有其他事务又修改了该数据。如果其他事务有更新的话，正在提交的事务会进行回滚。

乐观锁与悲观锁

CAS

3.2 锁的种类: 共享锁和互斥锁

对数据的操作其实只有两种，也就是读和写，而数据库在实现锁时，也会对这两种操作使用不同的锁；InnoDB 实现了标准的行级锁，也就是共享锁（Shared Lock）和互斥锁（Exclusive Lock）；共享锁和互斥锁的作用其实非常好理解：

4. 事务与隔离级别

4.1 事务的四个特性 ACID

（1）原子性Atomicity：指整个数据库事务是不可分割的工作单位。只有使据库中所有的操作执行成功，才算整个事务成功；事务中任何一个SQL语句执行失败，那么已经执行成功的SQL语句也必须撤销，数据库状态应该退回到执行事务前的状态。
（2）一致性Correspondence：指数据库事务不能破坏关系数据的完整性以及业务逻辑上的一致性。例如对银行转帐事务，不管事务成功还是失败，应该保证事务结束后ACCOUNTS表中Tom和Jack的存款总额为2000元。
（3）隔离性Isolation：指的是在并发环境中，当不同的事务同时操纵相同的数据时，每个事务都有各自的完整数据空间。由并发事务所做的修改必须与任何其他并发事务所做的修改隔离。事务查看数据更新时，数据所处的状态要么是另一事务修改它之前的状态，要么是另一事务修改它之后的状态，事务不会查看到中间状态的数据。
（4）持久性Durability：指的是只要事务成功结束，它对数据库所做的更新就必须永久保存下来。即使发生系统崩溃，重新启动数据库系统后，数据库还能恢复到事务成功结束时的状态。

4.2 事务实现原理

事务原理可以分几个部分说：acid，事务ACID的实现，事务的隔离级别，InnoDB的日志。

4.3 事务隔离级别

数据库事务的隔离级别有4个，由低到高依次为Read uncommitted（读未提交）、Read committed（读提交）、Repeatable read（重复读）、Serializable（序列化），这四个级别可以逐个解决脏读、不可重复读、幻读这几类问题。

1. READ UNCOMMITTED(未提交读)

事务中的修改,即使没有提交,对其它事务也是可见的. 脏读(Dirty Read).

2. READ COMMITTED(提交读)

一个事务开始时,只能"看见"已经提交的事务所做的修改. 这个级别有时候也叫不可重复读(nonrepeatable read).

3. REPEATABLE READ(可重复读)

该级别保证了同一事务中多次读取到的同样记录的结果是一致的. 但理论上,该事务级别还是无法解决另外一个幻读的问题(Phantom Read).

4. SERIALIZABLE (可串行化)

强制事务串行执行,避免了上面说到的 脏读,不可重复读,幻读 三个的问题.

什么是脏读，不可重复读，幻读

事务隔离级别
什么是脏读，不可重复读，幻读

5. MVCC(TODO)

https://blog.csdn.net/tangkund3218/article/details/47704527

6. 其他基本概念

7. Mysql性能提升

7.1 sql语句效率提升(TODO)

https://jianshu.com/p/5dd73a35d70f

数据库SQL优化大总结之 百万级数据库优化方案

7.2 其他

  1. 搜索引擎的选取，MySQL默认innodb(支持事务)，可以选择MYISAM(有b-tree算法查询)还有其他不同引擎
  2. 服务器的硬件提升
  3. 索引方面
  4. 建表的时候尽量使用notnull
  5. 字段尽量固定长度
  6. 垂直分隔（将很多字段多分成几张表）,水平分隔（将大数据的表分成几个小的数量级，分成几张表，还可以分开放在几个数据库中，利用集群的思想）
  7. 优化sql语句（查询执行速度比较慢的sql语句））
  8. 添加适当存储过程，触发器，事务等
  9. 表的设计要符合三范式。
  10. 读写分离（主从数据库）

『浅入浅出』MySQL 和 InnoDB

8. NOSQL

8.1 MongoDB

8.2 Redis

五、Java

5.1 基本知识

Java的Integer和int有什么区别

  1. equals只能用来比较引用类型,它只判断内容。该函数存在于老祖宗类 java.lang.Object

java中的数据类型，可分为两类： 1.基本数据类型，也称原始数据类型。byte,short,char,int,long,float,double,boolean 他们之间的比较，应用双等号（==）,比较的是他们的值。 2.复合数据类型(类) 当他们用（==）进行比较的时候，比较的是他们在内存中的存放地址， 所以，除非是同一个new出来的对象，他们的比较后的结果为true，否则比较后结果为false。

java在静态类中能引用非静态方法吗

面向对象的三个基本特征

构造器的调用顺序

  1. 父类静态代码块
  2. 子类静态代码块
  3. 父类代码块
  4. 父类构造
  5. 子类代码块
  6. 子类构造 java 子类继承父类运行顺序

    抽象类和接口的区别

    • 抽象类是用来捕捉子类的通用特性的 。它不能被实例化，只能被用作子类的超类。抽象类是被用来创建继承层级里子类的模板。
    • 接口是抽象方法的集合。如果一个类实现了某个接口，那么它就继承了这个接口的抽象方法。这就像契约模式，如果实现了这个接口，那么就必须确保使用这些方法。
    • 什么时候使用抽象类和接口
    • 如果你拥有一些方法并且想让它们中的一些有默认实现，那么使用抽象类吧。
    • 如果你想实现多重继承，那么你必须使用接口。由于Java不支持多继承，子类不能够继承多个类，但可以实现多个接口。因此你就可以使用接口来解决它。
    • 如果基本功能在不断改变，那么就需要使用抽象类。如果不断改变基本功能并且使用接口，那么就需要改变所有实现了该接口的类。
    • 抽象类和接口有什么区别，什么情况下会使用抽象类和什么情况你会使用接口

      匿名内部类

    • 类名规则 定位$1
    • test方法中的匿名内部类的名字被起为 Test$1

String、StringBuffer以及StringBuilder的区别

1. 为了安全

在hashmap等映射时体现。

2. 不可变性支持线程安全

还有一个大家都知道，就是在并发场景下，多个线程同时读一个资源，是不会引发竟态条件的。只有对资源做写操作才有危险。不可变对象不能被写，所以线程安全。

3. 不可变性支持字符串常量池

最后别忘了String另外一个字符串常量池的属性。像下面这样字符串one和two都用字面量"something"赋值。它们其实都指向同一个内存地址。

在java中String类为什么要设计成final？

String.GetHashCode()复杂度

String不变性

那么对于这句代码：Sting str=new String("abc");

不妨这样写

String s="abc"; String str=new String(s);

先定义一个字符串常量，然后用这个字符串常量作为字符串构造方法的参数再new出一个字符串出来。在定义字符串常量“abc”时，JVM会在 驻留池里创建出一个对象 来保存“abc”（注意这个对象 不是被new出来的，所以不会被放在堆中 ）当再用s作为构造参数new出一个对象时，会被放在堆内存中，所以一共创建了两个对象。

5.3 数据结构

Map --> HashMap / ConcurrentHashMap / TreeMap / LinkedHashMap

1. HashMap

1.1 结构与参数

系统在初始化HashMap时，会创建一个 长度为 capacity 的 Entry 数组，这个数组里可以存储元素的位置被称为“桶（bucket）”，每个 bucket 都有其指定索引，系统可以根据其索引快速访问该 bucket 里存储的元素。

在HashMap中有两个很重要的参数，容量(Capacity)和负载因子(Load factor)：

Capacity就是buckets的数目，Load factor就是buckets填满程度的最大比例。如果对迭代性能要求很高的话不要把capacity设置过大，也不要把load factor设置过小。当bucket填充的数目（即hashmap中元素的个数）大于capacity*load factor时就需要调整buckets的数目为当前的2倍。

无论何时，HashMap 的每个“桶”只存储一个元素（也就是一个 Entry），由于 Entry 对象可以包含一个引用变量（就是 Entry 构造器的的最后一个参数）用于指向下一个 Entry，
因此可能出现的情况是：HashMap 的 bucket 中只有一个 Entry，但这个 Entry 指向另一个 Entry ——这就形成了一个 Entry 链。（也就是冲突了）

entry

当 HashMap 的每个 bucket 里存储的 Entry 只是单个 Entry ——也就是没有通过指针产生 Entry 链时（没有哈希冲突），此时的 HashMap 具有最好的性能：当程序通过 key 取出对应 value 时，系统只要先计算出该 key 的 hashCode() 返回值，在根据该 hashCode 返回值找出该 key 在 table 数组中的索引，然后取出该索引处的 Entry，最后返回该 key 对应的 value 即可。

在发生“Hash 冲突”的情况下，单个 bucket 里存储的不是一个 Entry，而是一个 Entry 链，系统只能必须按顺序遍历每个 Entry，直到找到想搜索的 Entry 为止——如果恰好要搜索的 Entry 位于该 Entry 链的最末端（该 Entry 是最早放入该 bucket 中），那系统必须循环到最后才能找到该元素。

当创建 HashMap 时，有一个默认的负载因子（load factor），其默认值为 0.75，这是时间和空间成本上一种折衷：增大负载因子可以减少 Hash 表（就是那个 Entry 数组）所占用的内存空间，但会增加查询数据的时间开销，而查询是最频繁的的操作（HashMap 的 get() 与 put() 方法都要用到查询）；减小负载因子会提高数据查询的性能，但会增加 Hash 表所占用的内存空间。 通常情况下，程序员无需改变负载因子的值。

1.2 put()函数的实现

put函数大致的思路为：

  1. 对key的hashCode()做hash，然后再计算index;
  2. 如果没碰撞直接放到bucket里；
  3. 如果碰撞了，以链表的形式存在buckets后；
  4. 如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树参考此链接：Java 8：HashMap的性能提升；
  5. 如果节点已经存在就替换old value(保证key的唯一性)
  6. 如果bucket满了(超过load factor*current capacity)，就要resize。
1.3 get()函数的实现

大致思路如下：

  1. bucket里的第一个节点，直接命中；
  2. 如果有冲突，则通过key.equals(k)去查找对应的entry
    • 若为树，则在树中通过key.equals(k)查找，O(logn)；
    • 若为链表，则在链表中通过key.equals(k)查找，O(n)。
      1.4 hash函数的实现

      过程如下图： hashindex

      static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

      高16bit不变，低16bit和高16bit做了一个异或。

这样的一个hash函数实现，主要是权衡了速度与碰撞率。

设计者还解释到因为现在大多数的hashCode的分布已经很不错了，就算是发生了碰撞也用O(logn)的tree去做了。仅仅异或一下，既减少了系统的开销，也不会造成的因为高位没有参与下标的计算(table长度比较小时)，从而引起的碰撞。

如果发生了碰撞：

在Java 8之前的实现中是用链表解决冲突的，在产生碰撞的情况下，进行get时，两步的时间复杂度是O(1)+O(n)。因此，当碰撞很厉害的时候n很大，O(n)的速度显然是影响速度的。 因此在Java 8中，利用红黑树替换链表，这样复杂度就变成了O(1)+O(logn)了，这样在n很大的时候，能够比较理想的解决这个问题，在Java 8：HashMap的性能提升一文中有性能测试的结果。

注意：hash和计算下标是不一样的，hash是计算下标过程的一部分

1.5 RESIZE 的实现

当put时，如果发现目前的bucket占用程度已经超过了Load Factor所希望的比例，为了减少碰撞率，就会执行resize。resize的过程，简单的说就是把bucket扩充为2倍，之后重新计算index，把节点再放到新的bucket中。

怎么理解呢？例如我们从16扩展为32时，具体的变化如下所示：

rehash

因此元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：

resize

因此，我们在扩充HashMap的时候，不需要重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。可以看看下图为16扩充为32的resize示意图：

resize16-32

这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。

1.6 Hashmap为什么容量是2的幂次

最理想的效果是，Entry数组中每个位置都只有一个元素，这样，查询的时候效率最高，不需要遍历单链表，也不需要通过equals去比较K，而且空间利用率最大。那如何计算才会分布最均匀呢？我们首先想到的就是%运算，哈希值%容量=bucketIndex。

static int indexFor(int h, int length) {  
    return h & (length-1);  
}

这个等式实际上可以推理出来，2^n转换成二进制就是1+n个0，减1之后就是0+n个1，如16 -> 10000，15 -> 01111，那根据&位运算的规则，都为1(真)时，才为1，那0≤运算后的结果≤15，假设h <= 15，那么运算后的结果就是h本身，h >15，运算后的结果就是最后三位二进制做&运算后的值，最终，就是%运算后的余数，我想，这就是容量必须为2的幂的原因。

1.7 总结

1. 什么是HashMap？你为什么用到它？ 是基于Map接口的实现，存储键值对时，它可以接收null的键值，是非同步的，HashMap存储着Entry(hash, key, value, next)对象。

2. 你知道HashMap的工作原理吗？ 通过hash的方式，以键值对<K,V>的方式存储(put)、获取(get)对象。存储对象时，我们将K/V传给put方法时，它调用hashCode计算hash从而得到bucket位置，进一步存储，HashMap会根据当前bucket的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍)。获取对象时，我们将K传给get，它调用hashCode计算hash从而得到bucket位置，并进一步调用equals()方法确定键值对。如果发生碰撞的时候，Hashmap通过链表将产生碰撞冲突的元素组织起来，在Java 8中，如果一个bucket中碰撞冲突的元素超过某个限制(默认是8)，则使用红黑树来替换链表，从而提高速度。

3. 你知道get和put的原理吗？equals()和hashCode()的都有什么作用？ 通过对key的hashCode()进行hashing，并计算下标( n-1 & hash)，从而获得buckets的位置。如果产生碰撞，则利用key.equals()方法去链表或树中去查找对应的节点。

4. 你知道hash的实现吗？为什么要这样实现？ 在Java 1.8的实现中，是通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在bucket的n比较小的时候，也能保证考虑到高低bit都参与到hash的计算中，同时不会有太大的开销。

5. 如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？ 如果超过了负载因子(默认0.75)，则会重新resize一个原来长度两倍的HashMap，并且重新调用hash方法。

6. 什么是哈希冲突？如何解决的？ 以Entry[]数组实现的哈希桶数组，用Key的哈希值取模桶数组的大小可得到数组下标。
插入元素时，如果两条Key落在同一个桶（比如哈希值1和17取模16后都属于第一个哈希桶），我们称之为哈希冲突。

JDK的做法是链表法，Entry用一个next属性实现多个Entry以单向链表存放。查找哈希值为17的key时，先定位到哈希桶，然后链表遍历桶里所有元素，逐个比较其Hash值然后key值。
在JDK8里，新增默认为8的阈值，当一个桶里的Entry超过閥值，就不以单向链表而以红黑树来存放以加快Key的查找速度。 当然，最好还是桶里只有一个元素，不用去比较。所以默认当Entry数量达到桶数量的75%时，哈希冲突已比较严重，就会成倍扩容桶数组，并重新分配所有原来的Entry。扩容成本不低，所以也最好有个预估值。

7. HashMap在高并发下引起的死循环

Java 集合类实现原理

2. ConcurrentHashMap

ConcurrentHashMap 同样也分为 1.7 、1.8 版，两者在实现上略有不同。

【1.7】
原理上来说：ConcurrentHashMap 采用了分段锁技术，其中 Segment 继承于 ReentrantLock。不会像 HashTable 那样不管是 put 还是 get 操作都需要做同步处理，理论上 ConcurrentHashMap 支持 CurrencyLevel (Segment 数组数量)的线程并发。每当一个线程占用锁访问一个 Segment 时，不会影响到其他的 Segment。
1

PUT

在put时，首先是通过 key 定位到 Segment，之后在对应的 Segment 中进行具体的 put。

虽然 HashEntry 中的 value 是用 volatile 关键词修饰的，但是并不能保证并发的原子性，所以 put 操作时仍然需要加锁处理。

首先第一步的时候会尝试获取锁，如果获取失败肯定就有其他线程存在竞争，则利用 scanAndLockForPut() 自旋获取锁

GET

get 逻辑比较简单：

只需要将 Key 通过 Hash 之后定位到具体的 Segment ，再通过一次 Hash 定位到具体的元素上。

由于 HashEntry 中的 value 属性是用 volatile 关键词修饰的，保证了内存可见性，所以每次获取时都是最新值。

ConcurrentHashMap 的 get 方法是非常高效的，因为整个过程都不需要加锁。

【1.8】

2
看起来是不是和 1.8 HashMap 结构类似？
其中 抛弃了原有的 Segment 分段锁 ，而采用了 CAS + synchronized 来保证并发安全性。

PUT

GET

3. 使用LinkedHashMap设计实现一个LRU Cache

实际上就是 HashMap 和 LinkedList 两个集合类的存储结构的结合。在 LinkedHashMapMap 中，所有 put 进来的 Entry 都保存在哈希表中，但它又额外定义了一个 head 为头结点的空的双向循环链表，每次 put 进来 HashMapEntry ，除了将其保存到对哈希表中对应的位置上外，还要将其插入到双向循环链表的尾部。

public class LRUCache{
private int capacity;
private Map<Integer, Integer> cache;

public LRUCache(int capacity) {
    this.capacity = capacity;
    this.cache = new LinkedHashMap<Integer, Integer> (capacity, (float) 0.75, true){
        @Override
        protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
            return size() > capacity;
        }
    };
}

public void set(int key, int value){
    cache.put(key, value);
}

public int get(int key){
    if(cache.containsKey(key))
        return cache.get(key);
    return -1;
}

Set --> HashSet / TreeSet(TODO)

Java 集合类实现原理

5.4 多线程 并发

JAVA多线程之线程间的通信方式

  1. 同步
    这里讲的同步是指多个线程通过synchronized关键字这种方式来实现线程间的通信。
    由于线程A和线程B持有同一个MyObject类的对象object，尽管这两个线程需要调用不同的方法，但是它们是同步执行的，比如：线程B需要等待线程A执行完了methodA()方法之后，它才能执行methodB()方法。这样，线程A和线程B就实现了 通信。 这种方式，本质上就是“共享内存”式的通信。多个线程需要访问同一个共享变量，谁拿到了锁（获得了访问权限），谁就可以执行。
  2. while轮询的方式
    这种方式下，线程A不断地改变条件，线程ThreadB不停地通过while语句检测这个条件(list.size()==5)是否成立 ，从而实现了线程间的通信。但是这种方式会浪费CPU资源。
  3. wait/notify机制
    A,B之间如何通信的呢？也就是说，线程A如何知道 list.size() 已经为5了呢？ 这里用到了Object类的 wait() 和 notify() 方法。 当条件未满足时(list.size() !=5)，线程A调用wait() 放弃CPU，并进入阻塞状态。---不像②while轮询那样占用CPU 当条件满足时，线程B调用 notify()通知 线程A，所谓通知线程A，就是唤醒线程A，并让它进入可运行状态。 这种方式的一个好处就是CPU的利用率提高了。 但是也有一些缺点：比如，线程B先执行，一下子添加了5个元素并调用了notify()发送了通知，而此时线程A还执行；当线程A执行并调用wait()时，那它永远就不可能被唤醒了。因为，线程B已经发了通知了，以后不再发通知了。这说明：通知过早，会打乱程序的执行逻辑。
  4. 管道通信
    而管道通信，更像消息传递机制，也就是说：通过管道，将一个线程中的消息发送给另一个。

JAVA多线程之线程间的通信方式

线程池ThreadPoolExecutor参数设置

内存可见性与volatile 关键字

线程在工作时，需要将主内存中的数据拷贝到工作内存中。这样对数据的任何操作都是基于工作内存(效率提高)，并且不能直接操作主内存以及其他线程工作内存中的数据，之后再将更新之后的数据刷新到主内存中。
这里所提到的主内存可以简单认为是堆内存，而工作内存则可以认为是栈内存。

3 所以在并发运行时可能会出现线程 B 所读取到的数据是线程 A 更新之前的数据。

显然这肯定是会出问题的，因此 volatile 的作用出现了：

当一个变量被 volatile 修饰时，任何线程对它的写操作都会立即刷新到主内存中，并且会强制让缓存了该变量的线程中的数据清空，必须从主内存重新读取最新数据。

volatile 修饰之后并不是让线程直接从主内存中获取数据，依然需要将变量拷贝到工作内存中。

实现原理

Synchronized 与 ReentrantLock 的区别

相似点

这两种同步方式有很多相似之处，它们都是加锁方式同步，而且都是阻塞式的同步，也就是说当如果一个线程获得了对象锁，进入了同步块，其他访问该同步块的线程都必须阻塞在同步块外面等待，而进行线程阻塞和唤醒的代价是比较高的（操作系统需要在用户态与内核态之间来回切换，代价很高，不过可以通过对锁优化进行改善）。

区别

这两种方式最大区别就是：

类别 synchronized Lock
存在层次 Java的关键字，在jvm层面上 是一个类
锁的释放 1、以获取锁的线程执行完同步代码，释放锁 2、线程执行发生异常，jvm会让线程释放锁 在finally中必须释放锁，不然容易造成线程死锁
锁的获取 假设A线程获得锁，B线程等待。如果A线程阻塞，B线程会一直等待 分情况而定，Lock有多个锁获取的方式，具体下面会说道，大致就是可以尝试获得锁，线程可以不用一直等待
锁状态 无法判断 可以判断
锁类型 可重入 不可中断 非公平 可重入 可判断 可公平（两者皆可）
性能 少量同步 大量同步

在资源竞争不是很激烈的情况下，Synchronized的性能要优于ReetrantLock，但是在资源竞争很激烈的情况下，Synchronized的性能会下降几十倍，但是ReetrantLock的性能能维持常态；

1. Synchronized

Synchronized经过编译，会在同步块的前后分别形成monitorenter和monitorexit这个两个字节码指令。在执行monitorenter指令时，首先要尝试获取对象锁。如果这个对象没被锁定，或者当前线程已经拥有了那个对象锁，把锁的计算器加1，相应的，在执行monitorexit指令时会将锁计算器就减1，当计算器为0时，锁就被释放了。如果获取对象锁失败，那当前线程就要阻塞，直到对象锁被另一个线程释放为止。

2. ReentrantLock

由于ReentrantLock是java.util.concurrent包(J.U.C)下提供的一套互斥锁，相比Synchronized，ReentrantLock类提供了一些高级功能，主要有以下3项：

  1. 等待可中断，持有锁的线程长期不释放的时候，正在等待的线程可以选择放弃等待，这相当于Synchronized来说可以避免出现死锁的情况。

  2. 公平锁，多个线程等待同一个锁时，必须按照申请锁的时间顺序获得锁，Synchronized锁非公平锁，ReentrantLock默认的构造函数是创建的非公平锁，可以通过参数true设为公平锁，但公平锁表现的性能不是很好。

  3. 锁绑定多个条件，一个ReentrantLock对象可以同时绑定对个对象。

public class SynDemo{
    public static void main(String[] arg){
        Runnable t1=new MyThread();
        new Thread(t1,"t1").start();
        new Thread(t1,"t2").start();
    }
}
class MyThread implements Runnable {
    private Lock lock=new ReentrantLock();
    public void run() {
            lock.lock(); //加锁
            try{
                for(int i=0;i<5;i++)
                    System.out.println(Thread.currentThread().getName()+":"+i);
            }finally{
                lock.unlock(); //解锁
            }
    }
}

java的两种同步方式， Synchronized与ReentrantLock的区别 Synchronized与Lock锁的区别

Callable、Future和FutureTask（TODO）

JDK8 的 CompletableFuture（TODO）

5.5 Java 中的锁

锁

锁的粒度

5.6 NIO

概述

IO和NIO的关键就在你读取的过程中，假设一个情况，你正在读取一个数据，它的长度是500字节，但是目前传输而来的数据只有200字节，还有300在路上。这时候你有两种方式，一种是继续阻塞，等待那些数据到达。不过这显然不是个好方法，因为你不知道那些数据还有多久到达（有可能网络中断了，它们永远不会到达了）。另外一种方法是将已经读取的数据先记录到缓冲中，然后继续等待运行（一般就是再等待接口可读），等数据到达了再拼接起来。而NIO就是帮你搭建了第二种方法的基础，帮你把缓冲等问题处理好了，这样虽然两个读取都是阻塞的，但是第一种阻塞是网络IO的阻塞，第二种阻塞是本地缓冲IO的阻塞，显然第二种更有确定性、更可靠。特别实在读取数据到下一次等等套接字可读的过程中，你还需要做一些其他的响应或处理时，这个线程就要保障不能长时间阻塞，所以NIO是个很好的解决办法。

总的来说NIO只是在BIO上做一个简单封装，让你专注到实现功能中去，不用再考虑网络IO阻塞的问题。

NIO是怎么工作的

所有的系统I/O都分为两个阶段：等待就绪和操作。举例来说，读函数，分为等待系统可读和真正的读；同理，写函数分为等待网卡可以写和真正的写。

需要说明的是等待就绪的阻塞是不使用CPU的，是在“空等”；而真正的读写操作的阻塞是使用CPU的，真正在"干活"，而且这个过程非常快，属于memory copy，带宽通常在1GB/s级别以上，可以理解为基本不耗时。

以socket.read()为例子：

传统的BIO里面socket.read()，如果TCP RecvBuffer里没有数据，函数会一直阻塞，直到收到数据，返回读到的数据。

对于NIO，如果TCP RecvBuffer有数据，就把数据从网卡读到内存，并且返回给用户；反之则直接返回0，永远不会阻塞。

最新的AIO(Async I/O)里面会更进一步：不但等待就绪是非阻塞的，就连数据从网卡到内存的过程也是异步的。

换句话说，BIO里用户最关心“我要读”，NIO里用户最关心"我可以读了"，在AIO模型里用户更需要关注的是“读完了”。

NIO一个重要的特点是：socket主要的读、写、注册和接收函数，在等待就绪阶段都是非阻塞的，真正的I/O操作是同步阻塞的（消耗CPU但性能非常高）。

结合事件模型使用NIO同步非阻塞特性

回忆BIO模型，之所以需要多线程，是因为在进行I/O操作的时候，一是没有办法知道到底能不能写、能不能读，只能"傻等"，即使通过各种估算，算出来操作系统没有能力进行读写，也没法在socket.read()和socket.write()函数中返回，这两个函数无法进行有效的中断。所以除了多开线程另起炉灶，没有好的办法利用CPU。

NIO的读写函数可以立刻返回，这就给了我们不开线程利用CPU的最好机会：如果一个连接不能读写（socket.read()返回0或者socket.write()返回0），我们可以 把这件事记下来，记录的方式通常是在Selector上注册标记位，然后切换到其它就绪的连接（channel）继续进行读写。

下面具体看下如何利用事件模型单线程处理所有I/O请求：

NIO的主要事件有几个：读就绪、写就绪、有新连接到来。

我们首先需要注册当这几个事件到来的时候所对应的处理器。然后在合适的时机告诉事件选择器：我对这个事件感兴趣。对于写操作，就是写不出去的时候对写事件感兴趣；对于读操作，就是完成连接和系统没有办法承载新读入的数据的时；对于accept，一般是服务器刚启动的时候；而对于connect，一般是connect失败需要重连或者直接异步调用connect的时候。

其次，用一个死循环选择就绪的事件，会执行系统调用（Linux 2.6之前是select、poll，2.6之后是epoll（这几个概念后文专门解释），Windows是IOCP），还会阻塞的等待新事件的到来。新事件到来的时候，会在selector上注册标记位，标示可读、可写或者有连接到来。

注意，select是阻塞的，无论是通过操作系统的通知（epoll）还是不停的轮询(select，poll)，这个函数是阻塞的。所以你可以放心大胆地在一个while(true)里面调用这个函数而不用担心CPU空转。

程序大概的模样是：

//IO线程主循环:
class IoThread extends Thread{
    public void run(){
        Channel channel;
        while(channel=Selector.select()){//选择就绪的事件和对应的连接
            if(channel.event==accept){
                registerNewChannelHandler(channel);//如果是新连接，则注册一个新的读写处理器
            }
            if(channel.event==write){
                getChannelHandler(channel).channelWritable(channel);//如果可以写，则执行写事件
            }
            if(channel.event==read){
                getChannelHandler(channel).channelReadable(channel);//如果可以读，则执行读事件
            }
        }
    }
    Map<Channel，ChannelHandler> handlerMap;//所有channel的对应事件处理器
}

这个程序很简短，也是最简单的Reactor模式：注册所有感兴趣的事件处理器，单线程轮询选择就绪事件，执行事件处理器。

BIO、NIO两者的主要区别

BIO（IO） NIO
面向流 面向缓冲
阻塞IO 非阻塞IO
无 选择器（selector）

面向流与面向缓冲

Java BIO面向流意味着每次从流中读一个或多个字节，直至读取所有字节，它们没有被缓存在任何地方。此外，它不能前后移动流中的数据。如果需要前后移动从流中读取的数据，需要先将它缓存到一个缓冲区。

Java NIO的缓冲导向方法略有不同。数据读取到一个它稍后处理的缓冲区，需要时可在缓冲区中前后移动。这就增加了处理过程中的灵活性。但是，还需要检查是否该缓冲区中包含所有您需要处理的数据。而且，需确保当更多的数据读入缓冲区时，不要覆盖缓冲区里尚未处理的数据。

阻塞与非阻塞IO

Java BIO的各种流是阻塞的。这意味着，当一个线程调用read() 或 write()时，该线程被阻塞，直到有一些数据被读取，或数据完全写入。该线程在此期间不能再干任何事情了。

Java NIO的非阻塞模式，使一个线程从某通道发送请求读取数据，但是它仅能得到目前可用的数据，如果目前没有数据可用时，就什么都不会获取。而不是保持线程阻塞，所以直至数据变的可以读取之前，该线程可以继续做其他的事情。 非阻塞写也是如此。一个线程请求写入一些数据到某通道，但不需要等待它完全写入，这个线程同时可以去做别的事情。 线程通常将非阻塞IO的空闲时间用于在其它通道上执行IO操作，所以一个单独的线程现在可以管理多个输入和输出通道（channel）。

NIO的核心部分

NIO主要有三大核心部分：Channel(通道)，Buffer(缓冲区), Selector。传统IO基于字节流和字符流进行操作，而NIO基于Channel和Buffer(缓冲区)进行操作，数据总是从通道读取到缓冲区中，或者从缓冲区写入到通道中。Selector(选择区)用于监听多个通道的事件（比如：连接打开，数据到达）。因此，单个线程可以监听多个数据通道Channel。

2.1 Channel

首先说一下Channel，国内大多翻译成“通道”。Channel和IO中的Stream(流)是差不多一个等级的。只不过Stream是单向的，譬如：InputStream, OutputStream.而Channel是双向的，既可以用来进行读操作，又可以用来进行写操作。 NIO中的Channel的主要实现有：

将数据从用户空间拷贝到系统空间。 从系统空间往网卡写。同理，读操作也分为两步：

  1. 将数据从网卡拷贝到系统空间；
  2. 将数据从系统空间拷贝到用户空间。 对于NIO来说，缓存的使用可以使用DirectByteBuffer和HeapByteBuffer。如果使用了DirectByteBuffer，一般来说可以减少一次系统空间到用户空间的拷贝。但Buffer创建和销毁的成本更高，更不宜维护，通常会用内存池来提高性能。

如果数据量比较小的中小应用情况下，可以考虑使用heapBuffer；反之可以用directBuffer。

2.3 Selectors 选择器

Java NIO的选择器允许一个单独的线程同时监视多个通道，可以注册多个通道到同一个选择器上，然后使用一个单独的线程来“选择”已经就绪的通道。这种“选择”机制为一个单独线程管理多个通道提供了可能。

Selector运行单线程处理多个Channel，如果你的应用打开了多个通道，但每个连接的流量都很低，使用Selector就会很方便。例如在一个聊天服务器中。要使用Selector, 得向Selector注册Channel，然后调用它的select()方法。这个方法会一直阻塞到某个注册的通道有事件就绪。一旦这个方法返回，线程就可以处理这些事件，事件的例子有如新的连接进来、数据接收等。

2.4 Proactor与Reactor

I/O 复用机制需要事件分发器（event dispatcher）。 事件分发器的作用，即将那些读写事件源分发给各读写事件的处理者，就像送快递的在楼下喊: 谁谁谁的快递到了， 快来拿吧！开发人员在开始的时候需要在分发器那里注册感兴趣的事件，并提供相应的处理者（event handler)，或者是回调函数；事件分发器在适当的时候，会将请求的事件分发给这些handler或者回调函数。

NIO存在的问题

适用范围

六、JVM

6.1 JVM 内存模型

1

JVM中堆和栈

栈：

堆：

链接

Java中的内存泄漏

什么是java的内存泄漏

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

2

因此，通过以上分析，我们知道在Java中也有内存泄漏，但范围比C++要小一些。因为Java从语言上保证，任何对象都是可达的，所有的不可达对象都由GC管理。

Java内存泄漏引起的原因

Java内存泄漏的根本原因是什么呢？长生命周期的对象持有短生命周期对象的引用就很可能发生内存泄漏，尽管短生命周期对象已经不再需要，但是因为长生命周期持有它的引用而导致不能被回收，这就是Java中内存泄漏的发生场景。具体主要有如下几大类：

（1）静态集合类引起内存泄漏：

（2）当集合里面的对象属性被修改后，再调用remove()方法时不起作用。

public static void main(String[] args)
{
    Set<Person> set = new HashSet<Person>();
    Person p1 = new Person("唐僧","pwd1",25);
    Person p2 = new Person("孙悟空","pwd2",26);
    Person p3 = new Person("猪八戒","pwd3",27);
    set.add(p1);
    set.add(p2);
    set.add(p3);
    System.out.println("总共有:"+set.size()+" 个元素!"); //结果：总共有:3 个元素!
    p3.setAge(2); //修改p3的年龄,此时p3元素对应的hashcode值发生改变

    set.remove(p3); //此时remove不掉，造成内存泄漏

    set.add(p3); //重新添加，居然添加成功
    System.out.println("总共有:"+set.size()+" 个元素!"); //结果：总共有:4 个元素!
    for (Person person : set)
    {
        System.out.println(person);
    }
}

（3）单例模式

不正确使用单例模式是引起内存泄漏的一个常见问题，单例对象在初始化后将在JVM的整个生命周期中存在（以静态变量的方式），如果单例对象持有外部的引用，那么这个对象将不能被JVM正常回收，导致内存泄漏，考虑下面的例子：

class A{
    public A(){
    B.getInstance().setA(this);
    }
    ....
}
    //B类采用单例模式
class B{
    private A a;
    private static B instance=new B();
    public B(){}
    public static B getInstance(){
        return instance;
    }
    public void setA(A a){
        this.a=a;
    }
    //getter...
} 
显然B采用singleton模式，它持有一个A对象的引用，而这个A类的对象将不能被回收。想象下如果A是个比较复杂的对象或者集合类型会发生什么情况

6.2 JVM 堆

堆内存 分布

Java 中的堆是 JVM 所管理的最大的一块内存空间，主要用于存放各种类的实例对象。 在 Java 中，堆被划分成两个不同的区域：新生代 ( Young )、老年代 ( Old )。新生代 ( Young ) 又被划分为三个区域：Eden、From Survivor、To Survivor。 这样划分的目的是为了使 JVM 能够更好的管理堆内存中的对象，包括内存的分配以及回收。 堆的内存模型大致为：

1

从图中可以看出： 堆大小 = 新生代 + 老年代。其中，堆的大小可以通过参数 –Xms、-Xmx 来指定。 链接:Java 堆内存

为什么需要把堆分代

我们知道了必须设置Survivor区。假设现在只有一个survivor区，我们来模拟一下流程：

20160516173704870

碎片化带来的风险是极大的，严重影响JAVA程序的性能。堆空间被散布的对象占据不连续的内存，最直接的结果就是，堆中没有足够大的连续内存空间.

那么，顺理成章的，应该建立两块Survivor区，刚刚新建的对象在Eden中，经历一次Minor GC，Eden中的存活对象就会被移动到第一块survivor space S0，Eden被清空；等Eden区再满了，就再触发一次Minor GC，Eden和S0中的存活对象又会被复制送入第二块survivor space S1（这个过程非常重要，因为这种复制算法保证了S1中来自S0和Eden两部分的存活对象占用连续的内存空间，避免了碎片化的发生）

20160516174938778

6.3 垃圾回收

什么时候回收

如何判断一个对象需要被回收？

GC的两种判定方法：引用计数与引用链

Java虚拟机GC根节点的选择

  1. 虚拟机栈（栈帧中的本地变量表）中引用的对象
  2. 本地方法栈中JNI（即一般说的Native方法）引用的对象
  3. 方法区中类静态属性引用的对象
  4. 方法区中常量引用的对象

垃圾回收算法

标记清除、标记整理、复制算法的原理:

5张动图带你看懂垃圾回收算法

Minor GC、Major GC(或称为 Major GC)之间的区别

Java 中的堆也是 GC 收集垃圾的主要区域。GC 分为两种：Minor GC、Full GC ( 或称为 Major GC )。

Minor GC

6.4 垃圾收集器

JVM垃圾收集器－对比Serial、Parallel、CMS和G1

  1. 串行收集器Seiral Collector

    串行收集器是最简单的，它设计为在单核的环境下工作（32位或者windows），你几乎不会使用到它。它在工作的时候会暂停整个应用的运行，因此在所有服务器环境下都不可能被使用。

    使用方法：-XX:+UseSerialGC

  2. 并行／吞吐优先收集器Parallel/Throughput Collector

    这是JVM默认的收集器，跟它名字显示的一样，它最大的优点是使用多个线程来扫描和压缩堆。缺点是在minor和full GC的时候都会暂停应用的运行。并行收集器最适合用在可以容忍程序停滞的环境使用，它占用较低的CPU因而能提高应用的吞吐（throughput）。

    使用方法：-XX:+UseParallelGC

  3. CMS收集器CMS Collector

    CMS 收集器的 GC 周期由 6 个阶段组成。其中 4 个阶段 (名字以 Concurrent 开始的) 与实际的应用程序是并发执行的，而其他 2 个阶段需要暂停应用程序线程。

    初始标记 ：在这个阶段，需要虚拟机停顿正在执行的任务，官方的叫法STW(Stop The Word)。这个过程从垃圾回收的”根对象”开始，只扫描到能够和”根对象”直接关联的对象，并作标记。所以这个过程虽然暂停了整个JVM，但是很快就完成了。

    并发标记 ：这个阶段紧随初始标记阶段，在初始标记的基础上继续向下追溯标记。并发标记阶段，应用程序的线程和并发标记的线程并发执行，所以用户不会感受到停顿。

    并发预清理 ：并发预清理阶段仍然是并发的。在这个阶段，虚拟机查找在执行并发标记阶段新进入老年代的对象(可能会有一些对象从新生代晋升到老年代， 或者有一些对象被分配到老年代)。通过重新扫描，减少下一个阶段”重新标记”的工作，因为下一个阶段会Stop The World。

    重新标记 ：这个阶段会暂停虚拟机，收集器线程扫描在CMS堆中剩余的对象。扫描从”跟对象”开始向下追溯，并处理对象关联。

    并发清理 ：清理垃圾对象，这个阶段收集器线程和应用程序线程并发执行。

    并发重置 ：这个阶段，重置CMS收集器的数据结构，等待下一次垃圾回收。

    接下来是CMS收集器，CMS是Concurrent-Mark-Sweep的缩写，并发的标记与清除。这个算法使用多个线程并发地（concurrent）扫描堆，标记不使用的对象，然后清除它们回收内存。在两种情况下会使应用暂停（Stop the World, STW）：1. 当初次开始标记根对象时initial mark。2. 当在并行收集时应用又改变了堆的状态时，需要它从头再确认一次标记了正确的对象final remark。

    这个收集器最大的问题是在年轻代与老年代收集时会出现的一种竞争情况（race condition），称为提升失败promotion failure。对象从年轻代复制到老年代称为提升promotion，但有时侯老年代需要清理出足够空间来放这些对象，这需要一定的时间，它收集的速度可能赶不上不断产生的要提升的年轻代对象的速度，这时就需要做STW的收集。STW正是CMS想避免的问题。为了避免这个问题，需要增加老年代的空间大小或者增加更多的线程来做老年代的收集以赶上从年轻代复制对象的速度。

    除了上文所说的内容之外，CMS最大的问题就是内存空间碎片化的问题。CMS只有在触发FullGC的情况下才会对堆空间进行compact。如果线上应用长时间运行，碎片化会非常严重，会很容易造成promotion failed。为了解决这个问题线上很多应用通过定期重启或者手工触发FullGC来触发碎片整理。

    对比并行收集器它的一个坏处是需要占用比较多的CPU。对于大多数长期运行的服务器应用来说，这通常是值得的，因为它不会导致应用长时间的停滞。但是它不是JVM的默认的收集器。

    使用CMS需要仔细分析自己的应用对象生命周期，尤其是在应用要求高性能，高吞吐。需要仔细分析自己应用所需要的heap大小，老年代，新生代的分配比例，以及survival区的大小。设置不合理会很容易造成性能问题。后续会有专门的文章来介绍。

    使用方法：-XX：+UseConcMarkSweepGC，此时可同时使用-XX:+UseParNewGC将并行收集作用于年轻代，新的JVM自动打开这一配置

  4. G1收集器Garbage First Collector

    如果你的堆内存大于4G的话，那么G1会是要考虑使用的收集器。它是为了更好支持大于4G堆内存在JDK 7 u4引入的。G1收集器把堆分成多个区域，大小从1MB到32MB，并使用多个后台线程来扫描这些区域，优先会扫描最多垃圾的区域，这就是它名称的由来，垃圾优先Garbage First。

    如果在后台线程完成扫描之前堆空间耗光的话，才会进行STW收集。它另外一个优点是它在处理的同时会整理压缩堆空间，相比CMS只会在完全STW收集的时候才会这么做。

    使用过大的堆内存在过去几年是存在争议的，很多开发者从单个JVM分解成使用多个JVM的微服务（micro-service）和基于组件的架构。其他一些因素像分离程序组件、简化部署和避免重新加载类到内存的考虑也促进了这样的分离。

    除了这些因素，最大的因素当然是避免在STW收集时JVM用户线程停滞时间过长，如果你使用了很大的堆内存的话就可能出现这种情况。另外，像Docker那样的容器技术让你可以在一台物理机器上轻松部署多个应用也加速了这种趋势。

    使用方法：－XX:+UseG1GC

6.5 从实际案例聊聊Java应用的GC优化

发生Stop-The-World的GC

然后，我们来逐一分析一下：

找到原因后解决方法有两种：

  1. 通过把-XX:PermSize参数和-XX:MaxPermSize设置成一样，强制虚拟机在启动的时候就把永久代的容量固定下来，避免运行时自动扩容。
  2. CMS默认情况下不会回收Perm区，通过参数CMSPermGenSweepingEnabled、CMSClassUnloadingEnabled ，可以让CMS在Perm区容量不足时对其回收。

由于该服务没有生成大量动态类，回收Perm区收益不大，所以我们采用方案1，启动时将Perm区大小固定，避免进行动态扩容。

请求高峰期发生GC，导致服务可用性下降

  1. Init-mark初始标记(STW) ，该阶段进行可达性分析，标记GC ROOT能直接关联到的对象，所以很快。
  2. Concurrent-mark并发标记，由前阶段标记过的绿色对象出发，所有可到达的对象都在本阶段中标记。
  3. Remark重标记(STW) ，暂停所有用户线程，重新扫描堆中的对象，进行可达性分析，标记活着的对象。因为并发标记阶段是和用户线程并发执行的过程，所以该过程中可能有用户线程修改某些活跃对象的字段，指向了一个未标记过的对象，如下图中红色对象在并发标记开始时不可达，但是并行期间引用发生变化，变为对象可达，这个阶段需要重新标记出此类对象，防止在下一阶段被清理掉，这个过程也是需要STW的。特别需要注意一点，这个阶段是以新生代中对象为根来判断对象是否存活的。
  4. 并发清理，进行并发的垃圾清理。

GC频繁

image2018-5-25 16_24_18

从实际案例聊聊Java应用的GC优化

6.6 类的加载

6.6.1 类加载的五个过程：加载、验证、准备、解析、初始化

类加载器的工作过程：如果一个类加载器收到类类加载的请求，他首先不会自己去加载这个类，而是把类委派个父类加载器去完成，因此所有的请求最终都会传达到顶 层的启动类加载器中，只有父类反馈无法加载该类的请求（在自己的搜索范围类没有找到要加载的类）时候，子类才会试图去加载该类。

七、Spring

Spring IOC、DI、AOP原理和实现

1. Spring IOC原理

解释1：

IOC的意思是控件反转也就是由容器控制程序之间的关系，这也是spring的优点所在，把控件权交给了外部容器，之前的写法，由程序代码直接操控，而现在控制权由应用代码中转到了外部容器，控制权的转移是所谓反转。换句话说之前用new的方式获取对象，现在由spring给你至于怎么给你就是di了。

解释2：

IOC的意思是控件反转也就是由容器控制程序之间的关系，把控件权交给了外部容器，之前的写法，由程序代码直接操控，而现在控制权由应用代码中转到了外部容器，控制权的转移是所谓反转。网上有一个很形象的比喻：

我们是如何找女朋友的？常见的情况是，我们到处去看哪里有长得漂亮身材又好的mm，然后打听她们的兴趣爱好、qq号、电话号、ip号、iq号………，想办法认识她们，投其所好送其所要，然后嘿嘿……这个过程是复杂深奥的，我们必须自己设计和面对每个环节。传统的程序开发也是如此，在一个对象中，如果要使用另外的对象，就必须得到它（自己new一个，或者从JNDI中查询一个），使用完之后还要将对象销毁（比如Connection等），对象始终会和其他的接口或类藕合起来。那么IoC是如何做的呢？有点像通过婚介找女朋友，在我和女朋友之间引入了一个第三者：婚姻介绍所。婚介管理了很多男男女女的资料，我可以向婚介提出一个列表，告诉它我想找个什么样的女朋友，比如长得像李嘉欣，身材像林熙雷，唱歌像周杰伦，速度像卡洛斯，技术像齐达内之类的，然后婚介就会按照我们的要求，提供一个mm，我们只需要去和她谈恋爱、结婚就行了。简单明了，如果婚介给我们的人选不符合要求，我们就会抛出异常。整个过程不再由我自己控制，而是有婚介这样一个类似容器的机构来控制。Spring所倡导的开发方式就是如此，所有的类都会在spring容器中登记，告诉spring你是个什么东西，你需要什么东西，然后spring会在系统运行到适当的时候，把你要的东西主动给你，同时也把你交给其他需要你的东西。所有的类的创建、销毁都由 spring来控制，也就是说控制对象生存周期的不再是引用它的对象，而是spring。对于某个具体的对象而言，以前是它控制其他对象，现在是所有对象都被spring控制，所以这叫控制反转。

2. 什么是DI机制？

解释1：

这里说DI又要说到IOC，依赖注入（Dependecy Injection）和控制反转（Inversion of Control）是同一个概念，具体的讲：当某个角色 需要另外一个角色协助的时候，在传统的程序设计过程中，通常由调用者来创建被调用者的实例。但在spring中 创建被调用者的工作不再由调用者来完成，因此称为控制反转。创建被调用者的工作由spring来完成，然后注入调用者 因此也称为依赖注入。
spring以动态灵活的方式来管理对象 ， 注入的四种方式： 1. 接口注入 2. Setter方法注入 3. 构造方法注入 4.注解注入(@Autowire)

解释2：

IoC的一个重点是在系统运行中，动态的向某个对象提供它所需要的其他对象。这一点是通过DI（Dependency Injection， 依赖注入）来实现的。比如对象A需要操作数据库，以前我们总是要在A中自己编写代码来获得一个Connection对象，有了 spring我们就只需要告诉spring，A中需要一个Connection，至于这个Connection怎么构造，何时构造，A不需要知道。 在系统运行时，spring会在适当的时候制造一个Connection，然后像打针一样，注射到A当中，这样就完成了对各个对象之间关系 的控制。A需要依赖 Connection才能正常运行，而这个Connection是由spring注入到A中的，依赖注入的名字就这么来的。

3. 什么是 AOP 面向切面编程

解释1:

IOC依赖注入，和AOP面向切面编程，这两个是Spring的灵魂。
主要用到的设计模式有工厂模式和代理模式。

  • IOC就是典型的工厂模式，通过sessionfactory去注入实例。
  • AOP就是典型的代理模式的体现。

Spring IoC容器的初始化(TODO)

Spring AOP 的实现机制（TODO）

实现的两种代理实现机制，JDK动态代理和CGLIB动态代理。

代理机制-CGLIB

  1. 静态代理
    • 静态代理在使用时,需要定义接口或者父类
    • 被代理对象与代理对象一起实现相同的接口或者是继承相同父类

但是我们知道，实现接口，则必须实现它所有的方法。方法少的接口倒还好，但是如果恰巧这个接口的方法有很多呢，例如List接口。 更好的选择是： 使用动态代理！

  1. JDK动态代理
    • 动态代理对象特点:
    • 代理对象,不需要实现接口

    • 代理对象的生成,是利用JDK的API,动态的在内存中构建代理对象(需要我们指定创建代理对象/目标对象实现的接口的类型)

    • JDK实现代理只需要使用newProxyInstance方法
    • JDK动态代理局限性
    • 其代理对象必须是某个接口的实现，它是通过在运行期间床i教案一个接口的实现类来完成目标对象的代理。但事实上并不是所有类都有接口，对于没有实现接口的类，便无法使用该方方式实现动态代理。 如果Spring识别到所代理的类没有实现Interface，那么就会使用CGLib来创建动态代理，原理实际上成为所代理类的子类。
  2. Cglib动态代理
- 上面的静态代理和动态代理模式都是要求目标对象是实现一个接口的目标对象,Cglib代理,也叫作子类代理,是基于asm框架，实现了无反射机制进行代理，利用空间来换取了时间，代理效率高于jdk ,它是在内存中构建一个子类对象从而实现对目标对象功能的扩展. 它有如下特点:
- JDK的动态代理有一个限制,就是使用动态代理的对象必须实现一个或多个接口,如果想代理没有实现接口的类,就可以使用Cglib实现.
- Cglib是一个强大的高性能的代码生成包,它可以在运行期扩展java类与实现java接口.它广泛的被许多AOP的框架使用,例如Spring AOP和synaop,为他们提供方法的interception(拦截)
- Cglib包的底层是通过使用一个小而块的字节码处理框架ASM来转换字节码并生成新的类.不鼓励直接使用ASM,因为它要求你必须对JVM内部结构包括class文件的格式和指令集都很熟悉.
- 目标对象的方法如果为final/static,那么就不会被拦截,即不会执行目标对象额外的业务方法.

----

对比JDK动态代理和CGLib代理，在实际使用中发现CGLib在创建代理对象时所花费的时间却比JDK动态代理要长，所以CGLib更适合代理不需要频繁实例化的类。

Bean的加载

整个bean加载的过程步骤相对繁琐，主要步骤有以下几点：

  1. 转换beanName 要知道平时开发中传入的参数name可能只是别名，也可能是FactoryBean，所以需要进行解析转换，一般会进行以下解析：
    （1）消除修饰符，比如name="&test"，会去除&使name="test"；
    （2）取alias表示的最后的beanName，比如别名test01指向名称为test02的bean则返回test02。

  2. 从缓存中加载实例 实例在Spring的同一个容器中只会被创建一次，后面再想获取该bean时，就会尝试从缓存中获取；如果获取不到的话再从singletonFactories中加载。

  3. 实例化bean 缓存中记录的bean一般只是最原始的bean状态，这时就需要对bean进行实例化。如果得到的是bean的原始状态，但又要对bean进行处理，这时真正需要的是工厂bean中定义的factory-method方法中返回的bean，上面源码中的getObjectForBeanInstance就是来完成这个工作的。

  4. 检测parentBeanFacotory 从源码可以看出如果缓存中没有数据会转到父类工厂去加载，源码中的!containsBeanDefinition(beanName)就是检测如果当前加载的xml配置文件中不包含beanName所对应的配置，就只能到parentBeanFacotory去尝试加载bean。

  5. 存储XML配置文件的GernericBeanDefinition转换成RootBeanDefinition之前的文章介绍过XML配置文件中读取到的bean信息是存储在GernericBeanDefinition中的，但Bean的后续处理是针对于RootBeanDefinition的，所以需要转换后才能进行后续操作。

  6. 初始化依赖的bean 这里应该比较好理解，就是bean中可能依赖了其他bean属性，在初始化bean之前会先初始化这个bean所依赖的bean属性。

  7. 创建bean Spring容器根据不同scope创建bean实例。 整个流程就是如此，下面会讲解一些重要步骤的源码。

Bean生命周期（TODO）

Spring Bean的生命周期 Bean的生命周期 Spring中Bean的生命周期是怎样的？zhihu 1

1. 实例化Bean

对于BeanFactory容器，当客户向容器请求一个尚未初始化的bean时，或初始化bean的时候需要注入另一个尚未初始化的依赖时，容器就会调用createBean进行实例化。 对于ApplicationContext容器，当容器启动结束后，便实例化所有的bean。 容器通过获取BeanDefinition对象中的信息进行实例化。并且这一步仅仅是简单的实例化，并未进行依赖注入。 实例化对象被包装在BeanWrapper对象中，BeanWrapper提供了设置对象属性的接口，从而避免了使用反射机制设置属性。

2. 设置对象属性（依赖注入）

实例化后的对象被封装在BeanWrapper对象中，并且此时对象仍然是一个原生的状态，并没有进行依赖注入。 紧接着，Spring根据BeanDefinition中的信息进行依赖注入。 并且通过BeanWrapper提供的设置属性的接口完成依赖注入。

3. 注入Aware接口

紧接着，Spring会检测该对象是否实现了xxxAware接口，并将相关的xxxAware实例注入给bean。

4. BeanPostProcessor

当经过上述几个步骤后，bean对象已经被正确构造，但如果你想要对象被使用前再进行一些自定义的处理，就可以通过BeanPostProcessor接口实现。 该接口提供了两个函数：postProcessBeforeInitialzation( Object bean, String beanName ) 当前正在初始化的bean对象会被传递进来，我们就可以对这个bean作任何处理。 这个函数会先于InitialzationBean执行，因此称为前置处理。 所有Aware接口的注入就是在这一步完成的。postProcessAfterInitialzation( Object bean, String beanName ) 当前正在初始化的bean对象会被传递进来，我们就可以对这个bean作任何处理。 这个函数会在InitialzationBean完成后执行，因此称为后置处理。

5. InitializingBean与init-method

当BeanPostProcessor的前置处理完成后就会进入本阶段。 InitializingBean接口只有一个函数：afterPropertiesSet()这一阶段也可以在bean正式构造完成前增加我们自定义的逻辑，但它与前置处理不同，由于该函数并不会把当前bean对象传进来，因此在这一步没办法处理对象本身，只能增加一些额外的逻辑。 若要使用它，我们需要让bean实现该接口，并把要增加的逻辑写在该函数中。然后Spring会在前置处理完成后检测当前bean是否实现了该接口，并执行afterPropertiesSet函数。当然，Spring为了降低对客户代码的侵入性，给bean的配置提供了init-method属性，该属性指定了在这一阶段需要执行的函数名。Spring便会在初始化阶段执行我们设置的函数。init-method本质上仍然使用了InitializingBean接口。

6. DisposableBean和destroy-method

和init-method一样，通过给destroy-method指定函数，就可以在bean销毁前执行指定的逻辑。

Spring是如果解决循环依赖

八、Spring Boot

Spring Boot 启动、事件通知与配置加载原理

源码解读@SpringBootApplication与SpringApplication.run

一. @SpringBootApplication

@Target(ElementType.TYPE)
@Retention(RetentionPolicy.RUNTIME)
@Documented
@Inherited
@SpringBootConfiguration    // 从源代码中得知 @SpringBootApplication 被 @SpringBootConfiguration、@EnableAutoConfiguration、@ComponentScan 注解
@EnableAutoConfiguration    // 所修饰，换言之 Springboot 提供了统一的注解来替代以上三个注解，简化程序的配置。下面解释一下各注解的功能。
@ComponentScan(excludeFilters = {
        @Filter(type = FilterType.CUSTOM, classes = TypeExcludeFilter.class),
        @Filter(type = FilterType.CUSTOM, classes = AutoConfigurationExcludeFilter.class) })
public @interface SpringBootApplication {
    @AliasFor(annotation = EnableAutoConfiguration.class)
    Class<?>[] exclude() default {};

    @AliasFor(annotation = EnableAutoConfiguration.class)
    String[] excludeName() default {};

    @AliasFor(annotation = ComponentScan.class, attribute = "basePackages")
    String[] scanBasePackages() default {};

    @AliasFor(annotation = ComponentScan.class, attribute = "basePackageClasses")
    Class<?>[] scanBasePackageClasses() default {};

}

1. @SpringBootConfiguration

进入之后可以看到这个注解是继承了 @Configuration 的，二者功能也一致，标注当前类是配置类，并会将当前类内声明的一个或多个以@Bean注解标记的方法的实例纳入到srping容器中，并且实例名就是方法名。

@Target(ElementType.TYPE)
@Retention(RetentionPolicy.RUNTIME)
@Documented
@Configuration
public @interface SpringBootConfiguration {

}

通俗的讲 @Configuration 一般与 @Bean 注解配合使用，用 @Configuration 注解类等价与 XML 中配置 beans，用 @Bean 注解方法等价于 XML 中配置 bean 。举例说明：

2. @EnableAutoConfiguration

@EnableAutoConfiguration的作用启动自动的配置，@EnableAutoConfiguration注解的意思就是Springboot根据你添加的jar包来配置你项目的默认配置，比如根据spring-boot-starter-web ，来判断你的项目是否需要添加了webmvc和tomcat，就会自动的帮你配置web项目中所需要的默认配置。

Auto-configuration类是常规的 Spring 配置 Bean。它们使用的是 SpringFactoriesLoader 机制（以 EnableAutoConfiguration 类路径为 key）。通常 auto-configuration beans 是 @Conditional beans（在大多数情况下配合 @ConditionalOnClass 和 @ConditionalOnMissingBean 注解进行使用）。

无论是 basePackageClasses() 或是 basePackages() （或其 alias 值）都可以定义指定的包进行扫描。如果指定的包没有被定义，则将从声明该注解的类所在的包进行扫描。

注意， 元素有一个 annotation-config 属性（详情：http://www.cnblogs.com/exe19/p/5391712.html），但是 @ComponentScan 没有。这是因为在使用 @ComponentScan 注解的几乎所有的情况下，默认的注解配置处理是假定的。此外，当使用 AnnotationConfigApplicationContext， 注解配置处理器总会被注册，以为着任何试图在 @ComponentScan 级别是扫描失效的行为都将被忽略。

通俗的讲，@ComponentScan 注解会自动扫描指定包下的全部标有 @Component注解 的类，并注册成bean，当然包括 @Component 下的子注解@Service、@Repository、@Controller。@ComponentScan 注解没有类似的属性。

4. 更多

根据上面的理解，HelloWorld的入口类SpringboothelloApplication，我们可以使用：

@ComponentScan
//@SpringBootApplication
public class SpringboothelloApplication {

    public static void main(String[] args) {
        SpringApplication.run(SpringboothelloApplication.class, args);
    }
}

使用@ComponentScan注解代替@SpringBootApplication注解，也可以正常运行程序。原因是@SpringBootApplication中包含@ComponentScan，并且springboot会将入口类看作是一个@SpringBootConfiguration标记的配置类，所以定义在入口类Application中的SpringboothelloApplication也可以纳入到容器管理。

参考链接

2.1 入口 run 方法执行流程

  1. 创建计时器，用于记录SpringBoot应用上下文的创建所耗费的时间。
  2. 开启所有的SpringApplicationRunListener监听器，用于监听Sring Boot应用加载与启动信息。
  3. 创建应用配置对象(main方法的参数配置) ConfigurableEnvironment
  4. 创建要打印的Spring Boot启动标记 Banner
  5. 创建 ApplicationContext应用上下文对象，web环境和普通环境使用不同的应用上下文。
  6. 创建应用上下文启动异常报告对象 exceptionReporters
  7. 准备并刷新应用上下文，并从xml、properties、yml配置文件或数据库中加载配置信息，并创建已配置的相关的单例bean。到这一步，所有的非延迟加载的Spring bean都应该被创建成功。
  8. 打印Spring Boot上下文启动耗时到Logger中
  9. Spring Boot启动监听
  10. 调用实现了*Runner类型的bean的callRun方法，开始应用启动。
  11. 如果在上述步骤中有异常发生则日志记录下才创建上下文失败的原因并抛出IllegalStateException异常。
public ConfigurableApplicationContext run(String... args) {
    // 1. 创建计时器，用于记录SpringBoot应用上下文的创建所耗费的时间
    StopWatch stopWatch = new StopWatch();
    stopWatch.start();//stopWatch就是计时器
    ConfigurableApplicationContext context = null;
    Collection<SpringBootExceptionReporter> exceptionReporters = new ArrayList<>();
    configureHeadlessProperty();
    // 2. 开启所有的SpringApplicationRunListener监听器，用于监听Sring Boot应用加载与启动信息。
    SpringApplicationRunListeners listeners = getRunListeners(args);
    listeners.starting();// 监听器启动 主要用在log方面？
    try {
        ApplicationArguments applicationArguments = new DefaultApplicationArguments(
                args);
        // 3. 创建应用配置对象(main方法的参数配置) ConfigurableEnvironment
        ConfigurableEnvironment environment = prepareEnvironment(listeners,
                applicationArguments);
        configureIgnoreBeanInfo(environment);
        // 4. 创建要打印的Spring Boot启动标记 Banner
        Banner printedBanner = printBanner(environment);
        // 5. 创建 ApplicationContext应用上下文对象，web环境和普通环境使用不同的应用上下文。
        context = createApplicationContext();
        // 6. 创建应用上下文启动异常报告对象 exceptionReporters
        exceptionReporters = getSpringFactoriesInstances(
                SpringBootExceptionReporter.class,
                new Class[] { ConfigurableApplicationContext.class }, context);
        // 7. 准备并创建刷新应用上下文，并从xml、properties、yml配置文件或数据库中加载配置信息，并创建已配置的相关的单例bean。到这一步，所有的非延迟加载的Spring bean都应该被创建成功。
        prepareContext(context, environment, listeners, applicationArguments,
                printedBanner);
        refreshContext(context);// 刷新上下文
        afterRefresh(context, applicationArguments);
        stopWatch.stop();//计时结束
        // 8. 打印Spring Boot上下文启动耗时到Logger中
        if (this.logStartupInfo) {
            new StartupInfoLogger(this.mainApplicationClass)
                    .logStarted(getApplicationLog(), stopWatch);
        }
        // 9. Spring Boot启动监听
        listeners.started(context);
        // 10. 调用实现了*Runner类型的bean的callRun方法，开始应用启动。
        callRunners(context, applicationArguments);
    }
    catch (Throwable ex) {
        handleRunFailure(context, ex, exceptionReporters, listeners);
        throw new IllegalStateException(ex);
    }

    try {
        listeners.running(context); //完成listeners监听
    }
    // 11. 如果在上述步骤中有异常发生则日志记录下才创建上下文失败的原因并抛出IllegalStateException异常。
    catch (Throwable ex) {
        handleRunFailure(context, ex, exceptionReporters, null);
        throw new IllegalStateException(ex);
    }
    return context;
}

2.2 运行事件 深入各方法

事件就是Spring Boot启动过程的状态描述，在启动Spring Boot时所发生的事件一般指：

  • 开始启动事件
  • 环境准备完成事件
  • 上下文准备完成事件
  • 上下文加载完成
  • 应用启动完成事件

2.2.1 开始启动运行监听器 SpringApplicationRunListeners

上一层调用代码：SpringApplicationRunListeners listeners = getRunListeners(args);

顾名思意，运行监听器的作用就是为了监听 SpringApplication 的run方法的运行情况。在设计上监听器使用观察者模式，以总信息发布器 SpringApplicationRunListeners 为基础平台，将Spring启动时的事件分别发布到各个用户或系统在 META_INF/spring.factories文件中指定的应用初始化监听器中。使用观察者模式，在Spring应用启动时无需对启动时的其它业务bean的配置关心，只需要正常启动创建Spring应用上下文环境。各个业务'监听观察者'在监听到spring开始启动，或环境准备完成等事件后，会按照自己的逻辑创建所需的bean或者进行相应的配置。观察者模式使run方法的结构变得清晰，同时与外部耦合降到最低。

spring-boot-2.0.3.RELEASE-sources.jar!/org/springframework/boot/context/event/EventPublishingRunListener.java


class SpringApplicationRunListeners {
...
// 在run方法业务逻辑执行前、应用上下文初始化前调用此方法
public void starting() {
for (SpringApplicationRunListener listener : this.listeners) {
listener.starting();
}
}
// 当环境准备完成，应用上下文被创建之前调用此方法
public void environmentPrepared(ConfigurableEnvironment environment) {}
// 在应用上下文被创建和准备完成之后，但上下文相关代码被加载执行之前调用。因为上下文准备事件和上下文加载事件难以明确区分，所以这个方法一般没有具体实现。
public void contextPrepared(ConfigurableApplicationContext context) {}
// 当上下文加载完成之后，自定义bean完全加载完成之前调用此方法。
public void contextLoaded(ConfigurableApplicationContext context) {}
public void started(ConfigurableApplicationContext context) {}

public void running(ConfigurableApplicationContext context) {}
// 当run方法执行完成，或执行过程中发现异常时调用此方法。
public void failed(ConfigurableApplicationContext context, Throwable exception) {
    for (SpringApplicationRunListener listener : this.listeners) {
        callFailedListener(listener, context, exception);
    }
}

private void callFailedListener(SpringApplicationRunListener listener,
        ConfigurableApplicationContext context, Throwable exception) {}
    }
}

}


默认情况下Spring Boot会实例化EventPublishingRunListener作为运行监听器的实例。在实例化运行监听器时需要SpringApplication对象和用户对象作为参数。其内部维护着一个事件广播器（被观察者对象集合，前面所提到的在META_INF/spring.factories中注册的初始化监听器的有序集合 ），当监听到Spring启动等事件发生后，就会将创建具体事件对象，并广播推送给各个被观察者。

#### 2.2.2 环境准备 创建应用配置对象 ConfigurableEnvironment
> 上一层调用代码：ConfigurableEnvironment environment = prepareEnvironment(listeners

将通过`ApplicationArguments`将环境`Environment`配置好，并与SpringApplication绑定
```java
private ConfigurableEnvironment prepareEnvironment(
        SpringApplicationRunListeners listeners,
        ApplicationArguments applicationArguments) {
    // 获取或创建环境 Create and configure the environment
    ConfigurableEnvironment environment = getOrCreateEnvironment();
    configureEnvironment(environment, applicationArguments.getSourceArgs());
    // 持续监听
    listeners.environmentPrepared(environment);
    // 将环境与SpringApplication绑定（调用到 binder.java 未看）
    bindToSpringApplication(environment);
    if (this.webApplicationType == WebApplicationType.NONE) {
        environment = new EnvironmentConverter(getClassLoader())
                .convertToStandardEnvironmentIfNecessary(environment);
    }
    ConfigurationPropertySources.attach(environment);
    return environment;
}

根据this.webApplicationType来判断是什么环境，web环境和普通环境使用不同的应用上下文。再使用反射相应实例化。

spring-boot-2.0.3.RELEASE-sources.jar!/org/springframework/boot/SpringApplication.java

protected ConfigurableApplicationContext createApplicationContext() {
Class<?> contextClass = this.applicationContextClass;
if (contextClass == null) {
try {
switch (this.webApplicationType) {
case SERVLET:// 判断
contextClass = Class.forName(DEFAULT_WEB_CONTEXT_CLASS); // 反射
break;
case REACTIVE:
contextClass = Class.forName(DEFAULT_REACTIVE_WEB_CONTEXT_CLASS);
break;
default:
contextClass = Class.forName(DEFAULT_CONTEXT_CLASS);
}
}
catch (ClassNotFoundException ex) {
throw new IllegalStateException(
"Unable create a default ApplicationContext, "
+ "please specify an ApplicationContextClass",
ex);
}
}
return (ConfigurableApplicationContext) BeanUtils.instantiateClass(contextClass);
}

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

Class.forName() 的作用

2.2.4 创建上下文启动异常报告对象 exceptionReporters

上一层调用：
exceptionReporters = getSpringFactoriesInstances(SpringBootExceptionReporter.class,
new Class[] { > ConfigurableApplicationContext.class }, context);

通过getSpringFactoriesInstances创建SpringBootExceptionReporter接口的实现，而该接口的实现的就是FailureAnalyzers——上下文启动失败原因分析对象。

spring-boot-2.0.3.RELEASE-sources.jar!/org/springframework/boot/diagnostics/FailureAnalyzers.java


final class FailureAnalyzers implements SpringBootExceptionReporter {
...
FailureAnalyzers(ConfigurableApplicationContext context, ClassLoader classLoader) {}
private List<FailureAnalyzer> loadFailureAnalyzers(ClassLoader classLoader) {}
private void prepareFailureAnalyzers(List<FailureAnalyzer> analyzers,
        ConfigurableApplicationContext context) {}
private void prepareAnalyzer(ConfigurableApplicationContext context,
        FailureAnalyzer analyzer) {}

@Override
public boolean reportException(Throwable failure) {}
private FailureAnalysis analyze(Throwable failure, List<FailureAnalyzer> analyzers) {}
private boolean report(FailureAnalysis analysis, ClassLoader classLoader) {}

}


#### 2.2.5 准备上下文 prepareContext
> 上一层调用：prepareContext(context, environment, listeners, applicationArguments,printedBanner);

xml、properties、yml配置文件或数据库中加载的配置信息封装到`applicationArguments`中，并创建已配置的相关的单例bean。到这一步，所有的非延迟加载的Spring bean都应该被创建成功。

```java
private void prepareContext(ConfigurableApplicationContext context,
        ConfigurableEnvironment environment, SpringApplicationRunListeners listeners,
        ApplicationArguments applicationArguments, Banner printedBanner) {
    context.setEnvironment(environment);
    postProcessApplicationContext(context);
    applyInitializers(context);
    listeners.contextPrepared(context);
    if (this.logStartupInfo) {
        logStartupInfo(context.getParent() == null);
        logStartupProfileInfo(context);
    }

    // 创建已配置的相关的单例 bean 
    // Add boot specific singleton beans
    context.getBeanFactory().registerSingleton("springApplicationArguments",
            applicationArguments);
    if (printedBanner != null) {
        context.getBeanFactory().registerSingleton("springBootBanner", printedBanner);
    }

    // Load the sources
    Set<Object> sources = getAllSources();
    Assert.notEmpty(sources, "Sources must not be empty");
    load(context, sources.toArray(new Object[0]));
    listeners.contextLoaded(context);
}

2.2.6

上一层调用：refreshContext(context);

2.2.7

上一层调用：

参考链接

九、设计模式（TODO）

十、Linux命令行使用