一线大厂面试知识点全记录

十大经典排序算法


直接插入排序

思想:第一个数默认有序。从第二个数开始,从后往前扫描。若取出数 < 当前数,则指针不断前移,直到取出数 >= 当前数时,把取出数插入到当前位置

public static int[] insertSort(int[] arr){
    int pre,cur;   //pre:当前数指针,cur: 取出数
    for(int i = 1; i < arr.length; i++){   //从第二个数(索引为1)开始遍历
        pre = i - 1;
        cur = arr[i];
                //防止索引越界,并当当前数 > 取出数时
        while(pre >= 0 && arr[pre] > cur){ 
            arr[pre+1] = arr[pre];
            --pre;
        }
        arr[pre+1] = cur;
    }
    return arr;
}

Copy

复杂度与稳定性分析:

  • 最好的情况是序列已完全有序,则程序只for循环一次,while循环不执行,复杂度为O(n);最坏的情况是序列完全倒序,for循环扫描一轮,while循环也从后往前全部两两交换了一轮,复杂度为O(n^2); 平均复杂度为O(n^2);
  • 该排序算法不改变相同元素的相对位置,所以是稳定的。

第二种写法:

public void insert(int[] arr){
    for(int i = 1; i < arr.length; i++){
        for(int j = i; j > 0; j--){
            if(arr[j] < arr[j-1])
                swap(arr,j,j-1);
        }
    }
}

Copy


二分插入排序

思想:利用二分查找,能够更快的定位元素,不用一个个向前移动寻找。该种排序只是直接插入排序的改进版本。

public void insert(int[] arr){
    for(int i = 1; i < arr.length; i++){
        int key = arr[i];
        int low = BinarySearch(arr,key,0,i-1);
        for(int j = i-1; j >= low; j--)
            arr[j+1] = arr[j];
        arr[low] = key;
    }
}

public int BinarySearch(int[] arr, int key, int low, int high){
    while(low <= high){
        int mid = ((high-low) >> 1) + low;
        if(key < arr[mid])
            high = mid - 1;
        else
            low = mid + 1;
    }
    return low;
}

Copy


希尔排序

思想:使用了一个增量,初始值为一般设为Math.floor(arr.length / 2);该增量把序列划分为几个gap,对跨gap的数进行直接插入排序,而后gap为 Math.floor(gap / 2),直到最后一轮 gap=1。希尔排序本质上就是直接插入排序。

public static int[] shellSort(int[] arr){
    for(int gap = (int)Math.floor(arr.length / 2); gap > 0; gap = Math.floor(gap / 2)){   //设置增量,划分gap
        for(int i = gap; i < arr.length; i++){    //对每个gap的数进行直接插入排序
            int j = i;
            int cur = arr[j];     //arr[j]是相对位置在后面的数,arr[j-gap]是相对位置在前面的数
            while(j-gap >= 0 && arr[j-gap] > cur){
                arr[j] = arr[j-gap];
                j = j - gap;
            }
            arr[j] = cur;
        }
    }
    return arr;
}

Copy

复杂度与稳定性分析:

  • 内层for循环从初始gap值处开始遍历数组,复杂度情况与直接插入排序一致,若序列已有序,复杂度为O(n);若完全倒序,复杂度为O(n^2);平均复杂度问题未解决,尚为数学界难题。
  • 该排序算法改变相同元素的相对位置,所以是不稳定的。


冒泡排序

思想:冒泡排序会重复遍历序列,遍历次数每次都减少1次,一次比较两个元素,前数比后数大就交换两数,每轮次比较都会把当前轮次的最大数沉底。

public static int[] bubbleSort(int[] arr){
    for(int i = 0; i < arr.length - 1; i++){ //这里-1是因为第一个元素不与自己比较
        for(int j = 0; j < arr.length - 1 - i; j++){  //这里-1是为了防止数组越界,-i表示比较次数逐次递减
            if(arr[j] > arr[j+1])        //如果前数比后数大,就交换
                swap(arr,j,j+1);
        }
    }
    return arr;
}

Copy

复杂度与稳定性分析:

  • 如果已经有序,则算法只扫描一遍序列,不交换,复杂度为O(n);若无序,则除了遍历一遍,还要所有元素两两交换一次,复杂度为O(n^2);平均复杂度为O(n^2)。
  • 该排序算法不改变相同元素的相对位置,所以是稳定的。

冒泡排序改进版1:增加一个标志位

public static int[] bubbleSort(int[] arr){
    for(int i = 0; i < arr.length - 1; i++){ //这里-1是因为第一个元素不与自己比较
        boolean flag = true;
        for(int j = 0; j < arr.length - 1 - i; j++){  //这里-1是为了防止数组越界,-i表示比较次数逐次递减
            if(arr[j] > arr[j+1]){        //如果前数比后数大,就交换
                swap(arr,j,j+1);
                flag = false;
            }
        }
        //如果flag为真则跳出外层for,flag为真的情况是内层if未执行,说明当前某趟已将序列排成有序,那就不用再做没用的剩下的外层遍历了
        if(flag)
            break;
    }
    return arr;
}

Copy

冒泡排序改进版2(又叫鸡尾酒排序,双端冒泡排序):第一个for循环从前往后将最大数沉到后面,第二个从后往前将最小数浮到前面

public static int[] bubbleSort(int[] arr){
    for(int i = 0; i < arr.length / 2; i++) {
            for(int j = 0; j < arr.length - 1 - i; j++) {
                if(arr[j] > arr[j+1])
                    swap(arr,j,j+1);
            }
            for(int j = arr.length-1; j > i; j--) {
                if(arr[j] < arr[j-1])
                    swap(arr,j,j-1);
            }
        }
    return arr;
}

Copy


快速排序

思想:以分治的思想对pivot两端的序列进行排序,每次排序都将比当前pivot小的元素放在pivot左边,大的放pivot右边

public static int[] quickSort(int[] arr, int low, int high){
    if(low < high){
        int pivot = partition(arr,low,high);
        quickSort(arr,low,pivot-1);
        quickSort(arr,pivot+1,high);
    }
    return arr;
}

public static int partition(int[] arr, int low, int high){
    int pivot = arr[low]; //以第一个数作为第一轮的pivot,其实这么做不好,若序列刚好逆序,会导致0(n^2)的复杂度
    while(low < high){
        while(low < high && arr[high] >= pivot)
            high--;
        arr[low] = arr[high]; //比pivot小的元素就放左边
        while(low < high && arr[low] <= pivot)
            low++;
        arr[high] = arr[low]; //比pivot大的元素就放右边
    }
    arr[low] = pivot; //pivot归位
    return low;
    //这两句写成   arr[high] = pivot; return high; 也行,因为跳出 while 循环时 low == high
}

Copy

复杂度与稳定性分析:

  • 如果序列已经有序(正序或逆序),复杂度为O(n^2) ; 平均和最好复杂度为O(nlogn)。
  • 该排序算法改变相同元素的相对位置,所以是不稳定的。

快速排序的改进思路:

对于一个基本有序的序列,若取最开始或最后面的数作为pivot,则复杂度升高到跟冒泡排序一样。我们可以有两种取pivot的策略进行优化:

  • 取序列中的随机一个数作为pivot
  • 三位取中:取最左边,最右边,中间这三个数的值位于中间的数作为pivot 还可以采用双轴快排,用两个pivot将序列划分为三个部分分别快排,Java里Arrays.sort方法采取的就是双轴快排。


简单选择

思路:从待排序列中选择最小的元素放在第一位,然后每趟都从待排序列中选最小的元素,放在已排序的序列末端。

public static int[] selectSort(int[] arr){
    for(int i = 0; i < arr.length - 1; i++){ //这里-1是因为第一个元素不与自己比较
        int minIndex = i;
        for(int j = i + 1; j < arr.length; j++){  //j = i+1 表示每次都从剩下序列的第一个元素开始找
            if(arr[j] < arr[minIndex])        //若改为 > 号,则排序出的序列从大到小
                minIndex = j;     // 找到最小元素的索引
        }
        swap(arr,i,minIndex);
    }
    return arr;
}

Copy

复杂度与稳定性分析:

  • 无论序列怎么样,都要遍历两轮序列,所以最好,最坏,平均复杂度都是O(n^2)。
  • 该排序算法改变相同元素的相对位置,所以是不稳定的。


堆排序

思路:

1. 将无需序列构造成一个大顶堆(又叫大根堆,若想要排出从大到小的序列,则需要构造小顶堆),构造大顶堆从最后一个非叶子结点开始(若该二叉树从0开始编号,最后一个非叶子结点应是arr.length / 2 - 1,读者可自行验证)

2. 将堆顶元素(构造完大顶堆后,堆顶元素总是当前二叉树的最大数)与最后一个元素交换(等价于把当前的最大数沉底)

3. 此时的子序列可能不满足大顶堆的要求了,就需要调整二叉树使之满足大顶堆要求。然后重复执行2,3,直至整个序列有序

注:若该二叉树从0开始编号,假设父结点编号为i,则左孩子为2i+1,右孩子为2i+2。

public static int[] heapSort(int[] arr){
    buildMaxHeap(arr);    // 构造大顶堆
    //i > 0 而不是 >= 的原因在于下一句:堆顶元素不用与自己交换
    for(int i = arr.length - 1; i > 0; i--){  //arr.length - 1是初始二叉树的最后一个元素
        swap(arr,0,i);  //将堆顶元素与最后一个元素交换
        adjustHeap(arr,0,i);   //调整二叉树
    }
    return arr;
}

public static void buildMaxHeap(int[] arr){
    //i >= 0 而不是 > 的原因在于:堆顶元素所在的最小二叉树(仅含堆顶元素及其两个孩子)也可能不满足大顶堆要求,也需要调整
    for(int i = arr.length / 2 - 1; i >= 0; i--){
        adjustHeap(arr,i,arr.length);
    }
}

public static void adjustHeap(int[] arr, int i, int length){
    //编号为i的结点为当点最小二叉树的父结点
    int father = arr[i];
    for(int child = 2 * i + 1; child < length; child = 2 * child + 1){
        //第一个条件保证右孩子存在,第二个条件保证右孩子比左孩子大
        if(child + 1 < length && arr[child] < arr[child + 1])
        //将孩子指针指向右孩子
            child++;
        if(father < arr[child]){
            //如果孩子比父亲大,则交换父亲孩子,形成当前大根堆
            swap(arr,i,child);
            //可能当前孩子还有其子树,需将当前父亲指针指向当前孩子,使之成为其孩子的父亲,进行当前孩子的子树的大根堆调整
            i = child;
        }else
            break;

        //将两个if判断改为if(child + 1 < length && arr[child] > arr[child + 1]) 和 if(father > arr[child]),
        //即为构造小顶堆,构造从大到小的序列
    }
} 

Copy

复杂度与稳定性分析:

  • 平均,最好,最坏复杂度均为O(nlogn)。
  • 该排序算法改变相同元素的相对位置,所以是不稳定的。


归并排序

思路:将序列不断切分为子序列,将子序列排序,然后归并为新的有序序列,直至最后

public static void merge(int[] arr, int low, int high){
    if(low < high){
        int mid = ((high - low) >> 1) + low; //这么求中间数可以防止(high+low)/2可能出现的加法超出int范围的错误
        merge(arr,low,mid);
        merge(arr,mid+1,high);
        mergeSort(arr,low,mid,high);
    }
}

public static void mergeSort(int[] arr, int low, int mid, int high){
    int[] temp = new int[high - low + 1];
    int i,j,k; //i表示序列里左子序列的起始索引,j表示序列里右子序列的起始索引,k表示结果数组的起始索引
    for(i = 0, j = mid + 1, k = 0, i <= mid && j <= high; k++)
        temp[k] = arr[i] < arr[j] ? arr[i++] : arr[j++]; //比较两子序列数据,将叫嚣着复制进temp中,并把索引右移

    //当有一个子序列遍历完而另一个子序列没遍历完时,将另一个子序列剩下的元素直接复制进temp中
    while(i <= mid) temp[k++] = arr[i++];
    while(j <= high) temp[k++] = arr[j++];

    //将结果数组复制回原数组
    for(int m = 0; m < temp.length; m++)
        arr[m + low] = temp[m];  
}

Copy

复杂度与稳定性分析:

  • 最好,最坏,平均复杂度都是O(nlogn),空间复杂度为O(n)
  • 该排序算法不改变相同元素的相对位置,所以不稳定的。


计数排序

思路:适合数量大,但是数字范围小的序列。本质就是桶排序

public static void countSort(int[] arr, int minV, int maxV){ // minV和maxV是该序列里的最小值和最大值
    int[] result = new int[arr.length];
    int[] bucket = new int[maxV - minV + 1];

    for(int i = 0; i < arr.length; i++)
        bucket[arr[i] - minV]++;

    //统计bucket数组的前j位共有多少个数
    for(int i = 1; i < bucket.length; i++)
        bucket[i] += bucket[i-1];

    //按子关键字对指定的数据进行排序 ,因为开始是从前往后放,现在从后往前读取,保证计数排序的稳定性
    for(int i = arr.length - 1; i >= 0; i--)
        result[--bucket[arr[i]- minV]] = arr[i];
}

Copy

复杂度与稳定性分析:

  • 涉及桶排序的复杂度问题跟桶数有关,研究该复杂度并无太大意义。
  • 该排序算法不改变相同元素的相对位置,所以是稳定的。


基数排序

思路:分最高位优先法和最低位优先法,这里使用的是最低位优先法。从低位到高位将以位的角度将每个数排序,整个基数排序里对每一位的排序都是一次计数排序。

public static void radixSort(int[] arr, int d){ // d是该序列里最大数的位数
    int[] result = new int[arr.length];
    int[] bucket = new int[10];

    for(int i = 0; i < d; i++){
        int division = (int)Math.pow(10,i);
        Arrays.fill(bucket,0);          //重置bucket数组 
        System.arraycopy(arr,0,result,0,arr.length); //将arr中的元素复制到result数组中  

        //计算每个待排序数据的子关键字  
        for(int j = 0; j < arr.length; j++){
            int num = (result[j] / division) % 10;
            bucket[num]++;
        }

        //统计bucket数组的前j位共有多少个数
        for(int j = 1; j < bucket.length; j++)
            bucket[j] += bucket[j-1];

        //按子关键字对指定的数据进行排序 ,因为开始是从前往后放,现在从后往前读取,保证基数排序的稳定性
        for(int j = arr.length - 1 ; j >= 0; j--){
            int num = (result[j] / division) % 10;
            arr[--bucket[num]] = result[j];
        }
    }
}

Copy

复杂度与稳定性分析:

  • 涉及桶排序的复杂度问题跟桶数有关,研究该复杂度并无太大意义。
  • 该排序算法不改变相同元素的相对位置,所以是稳定的。


JVM


JVM运行时数据区

截屏2020-04-0523.13.01.png


程序计数器 (Program Counter Register, PCR)

由于多线程是通过线程切换争夺CPU的方式执行的,故在任一时刻,CPU其实只会执行一个线程。所以为了切换线程后CPU还能回到正确的执行位置,每一个线程都应该又一个独立的PCR,互不影响。所以 PCR是线程私有的一块较小的内存空间, 可以看作是当前线程所执行的字节码的行号指示器。

若当前执行的是非Native方法,则PCR记录的是当前字节码指令的地址;若是Native方法,则PCR为空(Undefined)。

PCR所在的内存区域是运行时数据区里唯一不会发生OOM (OutOfMemoryError) 异常的区域。


虚拟机栈 (VM Stack)

每个线程拥有自己的虚拟机栈,所以虚拟机栈也是线程私有的且生命周期与线程一样。虚拟机栈是用来专门描述Java中非Native方法的内存模型。每个方法在执行时就会在当前线程的虚拟机栈中创建一个栈帧(包括局部变量表,操作数栈,动态链接,方法出口等信息)。

每一个方法从调用到执行完成,就是虚拟机栈中一个栈帧压栈到弹栈的全部过程。

若当前线程请求的栈深超过虚拟机栈允许的深度时,就抛出 StackOverflowError异常。若虚拟机栈允许动态扩展内存,但扩展时无法申请到足够的内存,则会抛出OOM异常。


本地方法栈 (Native Method Stack)

与虚拟机栈十分相似,只不过对应处理的时Java中Native方法。


方法区 (Method Area)

用于存储已被JVM加载的类 (Class) 信息,静态常量 (static final),静态变量等信息,当方法去无法满足内存分配时抛出OOM异常。

很多人将方法区与 “永久代 (Permanent Generation, permGen)” 混为一谈,实际上二者并不等价,永久代是方法区的具体实现 (方法区是《JVM规范》中定义的概念,永久代是HotSpot虚拟机(当前使用最广,JDK中自带的虚拟机)对方法区这一概念的具体实现,而其他虚拟机并没有永久代这一概念)。

方法区里包括运行时常量池,用于存放编译器生成的各种字面量(字符串常量)与符号引用(也就是说运行时常量池包含了字符串常量池与符号引用),但运行时也可以将新的常量放入池中,如用String.intern()方法。

注:在JDK 1.7之前,运行时常量池放在方法区中,HotSpot对方法区的实现是永久代;

在JDK1.7时,将运行时常量池中的字符串常量池从方法区中移到堆里(原因大概是因为字符串常量池有时太大,方法区放不下),剩下的东西还在方法区中

在JDK1.7之后,字符串常量池还在堆中,运行时常量池还在方法区中,只不过HotSpot 移除了永久代 , 使用 元空间 (Metaspace) 代替永久代,永久代退出历史舞台(原因有永久代垃圾回收效率低等)。元空间使用的是物理内存,直接受到本机内存的限制。


堆 (Heap)

堆在JVM启动时就创建了,该区域的卫一木的就是存放对象实例与数组。

堆是垃圾收集器管理的主要区域,因此堆又被称为 “GC (Garbage Collected) 堆”。按照垃圾回收的角度看堆还可以分为新生代,老年代,详情见我的其他博客。

如果堆中没有足够的内存完成对象实例的分配且也无法扩展时,抛出OOM异常。


对象的创建与定位

截屏2020-04-0523.20.21.png


对象的创建

对象在堆内存中的存储布局主要分三块:对象头,实例数据,对齐填充

  • 对象头包括两部分: 1) Mark Work: 包含哈希码,GC分代年龄等自身信息;2) 类型指针:虚拟机通过这个指针确定这个对象是哪个类的实例。
  • 实例数据:代码中所定义的各字段内容,包括从父类继承的
  • 对齐填充:注意这一块不是必须存在的,仅起到占位符的作用。HotSpot要求对象大小必须是8的整数倍,所以若前二者加起来占的内存和不是8的整数倍时,就需要对齐填充补全内存,使之成为8的整数倍。


对象的定位

Java程序通过栈上的一个引用来定位到堆上的对象,定位的方式有两种:句柄,直接指针

  • 句柄:堆中会划分出一块句柄池,栈中的某个引用存的是其实是对象的句柄地址,句柄地址中包含了对象的实例地址与对象类类型数据地址。其好处是当对象被频繁移动时,修改的只是句柄中的对象实例地址,而引用本身不变。
  • 截屏2020-04-0523.21.49.png
  • 直接指针:直接存储对象的实例地址(HotSpot采用这种方式)。其好处是节省了一次指针定位的时间开销,速度快。
  • 截屏2020-04-0523.22.02.png


类加载机制和双亲委派机制


类加载机制

JVM加载一个类共分为3个步骤:加载,链接,初始化。其中链接又分为3个步骤:验证,准备,解析。

这些阶段通常是互相交叉混合式进行的(即可以相互调用),但必须是按这个顺序开始的(解析过程不一定,它可以在初始化之后开始,这是为了支持动态绑定(即多态))。

截屏2020-04-0523.23.41.png


加载

加载共分为3步:1)获取定义此类的二进制字节流;2)将字节流代表的静态存储结构转化为方法区的运行时数据结构;3)在堆中实例化一个这个类的Class对象,作为方法区这个类的入口

截屏2020-04-0523.24.38.png


链接

链接分为验证、准备、解析三步:

  • 验证:主要是确认字节流包含的信息符合虚拟机的要求,不含有害信息危害虚拟机安全,主要有4个阶段:文件格式验证,元数据验证,字节码验证,符号引用验证。
  • 准备:为类中的静态变量赋初始值(零值),但如果是静态常量(即被final修饰),在准备阶段直接就它设置为真正的初始值了。
  • 解析:将符号引用转为直接引用。


初始化

实际上是执行类构造器 () 方法的过程,为静态变量真正赋值的过程。虚拟机保证父类的() 优于子类的执行(这也是父类的静态代码块(static {})优于子类静态代码块执行的原因),所以虚拟机中执行第一个() 的类永远是Object。

JVM规定了有且只有5种引用方式必须对类与接口初始化,称为主动引用:1)new对象;2)使用反射时;3)初始化一个类时,若其父类还没初始化,先初始化父类(接口不同,只有用到父接口时才初始化);4)JVM启动时,初始化主类(public class)。第五种不必要掌握。


类加载器

执行加载阶段的第一步的代码模块,称为“类加载器”。只有在同一类加载器的情况下,比较两个类是否“相等”才有意义,否则即使有两个同名的类(来自同一Class文件),它们也不等。(这里的相等包括equal() 方法,instanceof,isAssignableFrom()方法)。

JVM预定义了3种类加载器:启动类加载器 (BootStrap ClassLoader),扩展类加载器 (Extension ClassLoader),系统类加载器(又叫应用程序加载器) (System ClassLoader)。

  • 启动类加载器:用于加载%JAVA_HOME%\lib 下的Java和心累,不允许开发者直接引用。
  • 扩展类加载器:用于加载JRE的扩展类,即JRE目录下的 lib\ext,开发者可直接引用。
  • 系统类加载器:用于加载CLASSPATH下的类,开发者可直接引用。


双亲委派机制

某个类收到了类加载的请求,当前类会把这个请求交给父加载器完成,依次向上递归,直到传到最顶层的启动类加载器;若父加载器可以完成,则成功返回,若不能完成,子加载器才会尝试自己加载。

截屏2020-04-0523.28.13.png

双亲委派机制的好处:1)防止类重复加载;2)防止Java核心类库被篡改(如:网络中传来一个java.lang.Object类,通过双亲委派传递到启动类加载器,JVM在Java核心类中发现有java.lang.Object类,则加载这个,而不加载网络传来的java.lang.Object类)。


堆内存的划分与垃圾回收


堆的划分

可以把Java堆分为新生代(Young Generation)和老年代(Old Generation),又将新生代分为Eden区,From Survivor区,To Survivor区,它们默认的内存分配比例为8:1:1。

截屏2020-04-1119.52.57.png


区分Minor GC、Major GC、Full GC

GC分为3种:Minor GC, Major GC,Full GC

  • Minor GC发生在新生代中,采用复制算法;
  • Major GC发生在老年代中,采用标记—清除算法或标记—整理算法;
  • Full GC包括一次Minor GC和一次Major GC。

Java对象具有“朝生夕灭”的特点(即生命周期很短),所以Minor GC十分频繁,速度快;而Major GC比Minor GC速度一般慢十倍以上。


对象的分配

新建的对象一般被分配到Eden和From区(需要较大连续空间的对象直接被移入老年代),经过一次Minor GC后,Eden和From中存活的对象被移入To区,然后这个To区成为下一次Minor GC的From区,继续扫描(由此可见,From区和To区时不断交替互相成为的,且这两区在任一时刻必有一区为空,所以每次新生代中可用的内存空间为整个新生代空间的90%(80%+10%))。以后对象每熬过一次Minor GC,对象的年龄 +1 岁,当年龄到某个值时(默认15岁),对象晋升到老年代。

注:当移入To区时如果To区空间不够用,就会将To区无法容纳的对象放入老年代,这一机制成为“分配担保”。


判断对象的是否需要回收

首先判断对象是否可用(有两种算法):引用计数算法,可达性分析算法。

  • 引用计数算法:给对象添加一个引用计数器,被引用一次则+1,当引用失效就-1,当计数器为0时该对象就是不可再被引用。(这种算法实现简单效率也高,但很难处理对象间相互循环引用的情况)。
  • 可达性分析算法:在Java中,通过可达性分析算法来判断对象是否存活。 通过一系列称为 GC Roots 的对象作为起点,向下搜索,走过的路径称为引用链 (Reference Chain),当有对象与GC Roots不可达时,该对象不可再被引用。

下图绿色对象为存活对象,红色对象为不可用对象。

截屏2020-04-0523.33.15.png

注:当对象与GC Roots不可达时,也不意味着对象已经死亡了,真正宣布对象死亡还需要两次标记过程:1)第一次标记并筛选,筛选的条件为该对象是否有必要执行 finalize() 方法,若对象没有覆盖 finalize() 方法,或该方法已经被JVM调用过的,则认为没有必要执行 finalize() 方法,回收该对象;2)若该对象有必要执行 finalize() 方法,则该对象会被放入一个叫 F-Queue的队列中,并由JVM创建的 Finalizer 线程执行 finalize() 方法进行回收。


垃圾回收算法

垃圾回收算法分为三种:复制算法,标记—清除算法,标记—整理算法。

  • 复制算法:将可用内存划分为两块,每次只是用一半,当这一半的内存用完了,就把存活的对象复制到另一半上,然后把已使用的内存清理(由此也可验证From区与To区必有一区为空,因为一旦复制到To区,From区的内存就被清理了)。

  • 标记—清除算法:标记出需要回收的对象,然后回收所有被标记的对象。这种方法会产生大量不连续的内存碎片。
  • 标记—整理算法:标记—清除算法的改进版,在标记完后,先让存活的对象向一端移动,然后清理掉端边界以外的内存。这样就不会造成许多不连续的内存碎片了。

HotSpot采用分代收集算法,即新生代采用复制算法,老年代采用标记—整理算法。


垃圾收集器

垃圾收集器截至JDK1.8,共分为7种:Serial收集器,ParNew收集器,Parallel Scavenge收集器,CMS收集器,Serial Old收集器,Parallel Old收集器,G1收集器(JDK1.8之后还有ZGC,Shenandoah)。下图是它们搭配使用关系,有连线说明它们可以相互搭配使用。

截屏2020-04-0523.36.15.png


Serial

仅使用一个线程完成垃圾回收,在垃圾回收时暂停其他所有线程(称为Stop The World),直到回收结束。

截屏2020-04-0523.36.58.png


ParNew

Serial收集器的并发版本。

截屏2020-04-0523.37.34.png


Parallel Scavenge

与ParNew类似,不过Parallel Scavenge收集器关注的是CPU的吞吐量,而其他收集器关注的是如何缩短垃圾回收时用户线程的停顿时间(也就是缩短Stop The World的时间)。吞吐量 = 运行代码时间 / (运行代码时间 + 垃圾回收时间)。

截屏2020-04-0523.38.07.png


CMS(Concurrent Mark Sweep)

使用标记—清除算法,整个过程分为4步:初始标记,并发标记,重新标记,并发清除。(其中初始标记和重新标记会触发Stop The World)。

有3个缺点:1)对CPU资源非常敏感;2)无法处理“浮动垃圾”,可能会出现Concurrent Mode Failure(在并发清除时用户线程也在运行,自然就会同时产生新的垃圾,这些垃圾只能留在下次清理,称为“浮动垃圾”),所以并发清楚时需要预留一定内存空间(给“浮动垃圾”),若预留的空间无法满足程序需要,则发生Concurrent Mode Failure,启动后备预案,临时启用Serial Old收集器,导致有一次Major GC);3)产生大量的内存碎片,这是标记—清除算法导致的。


Serial Old

Serial收集器的老年代版本,除此之外还可作为CMS收集器发生Concurrent Mode Failure时的后备预案。


Parallel Old

Parallel Scavenge收集器的老年代版本。

截屏2020-04-0523.39.20.png


G1(Garbage First)

整个过程分为4步:初始标记,并发标记,最终标记,筛选回收。

有以下4个特点:

  • 并行与并发:可以并行执行以减少Stop The World的停顿时间,也可以并发的执行垃圾回收线程与用户线程。
  • 分代收集:虽然保留了分代(新生代与老年代)概念,但G1将堆分为多个大小相等的独立区域(Region)。
  • 空间整合:从整体上看是使用的标记—整理算法,实际上是两个Region之间的“复制”算法。
  • 可预测的停顿:G1可以建立可预测的停顿时间模型是因为G1跟踪各个Region里面的垃圾堆积的价值大小,在后台维护了一个优先列表,每次根据允许的收集时间,优先回收价值最大的Region,这也是G1名字中First(价值优先)的含义。


Java并发编程


锁的四种状态

在JDK 1.6后,JVM引入了四种锁状态对synchronized进行了优化:无锁状态,偏向锁,轻量级锁,重量级锁。通过CAS在对应对象的Mark Word中设置标记实现。

  • 无锁状态:当线程间不发生对资源对争抢时,这个资源是无锁状态。
  • 偏向锁:大多数情况,资源不仅不存在争抢,还总是被同一个线程获得,这时候为了消除获取释放锁时的CAS开销(当获取或释放锁时,都要通过CAS操作奖线程id记录到锁对象的Mark Word中),将资源里的锁标记设置为偏向锁的标记,看起来像是某个线程得到了偏护。当第二个线程也来争抢这个资源时,偏向锁升级为轻量级锁。
  • 轻量级锁:当获得偏向锁的资源发生线程争抢时,偏向锁升级为轻量级锁。
  • 重量级锁:当获得轻量级锁的资源发生线程争抢时,轻量级锁升级为重量级锁。

注:锁的状态只能升级,不能降级。


volatile关键字和JMM内存模型


volatile关键字

volatile只能保证变量的可见性,有序性,却不能保证原子性。

  • 可见性:当一个线程修改了被volatile修饰的变量后,会马上通知其他线程,那么其他线程在读的时候,都会读到最新的变量值。
  • 有序性:volatile通过内存屏障禁止了指令间的重排序(当指令或者操作间没有依赖关系时,编译器可能会通过指令或操作重排序,提高程序性能),详见下文。
  • 原子性:如i++这类涉及多个操作语句,volatile是无法保证这类操作的正确性的,如果想保证原子性,可以用Atomic原子类里的对象,也可以直接对变量加锁。


JMM内存模型

Java并发采用共享内存模型。对类中对一个成员变量来说,它是存储在主内存中的,每个线程要操作这个变量时,都会拷贝一份它的副本,到线程自己的工作内存中,等操作完了,再将操作后的变量的值,刷新回主内存中。

上述操作通过8个内存指令完成:

  • lock:将一个变量标识为线程独占状态
  • read:将变量的值读到线程的工作内存中
  • load:创建一个变量副本,将读到的值存储
  • use:线程可以使用这个变量副本了
  • assign:线程操作这个变量副本
  • store:将修改后的变量值刷新回主内存中
  • write:将刷新回来的值存储到变量中,完成变量的更新
  • unlock:解除变量的独占状态

截屏2020-04-0523.44.31.png

其中通过load和store指令的结合,形成了四种内存屏障(loadload,loadstore,storeload,storestore),volatile通过在上述流程中插入这四种内存屏障,禁止了可能会发生的指令重排序。

注:JMM不保证对64位的long和double的写操作有原子性,会将他们拆成两个32位的“半数”处理,目的是为了兼容以前32位的系统。所以针对这两种类型的数,建议一定要用Atomic包下面的原子类来声明。


happens-before和as-if-serial语义

在执行程序时,为提高性能,编译器和处理器常常会对指令做重排序(这种重排序往往导致了可见性的问题)。然而具有happens-before和as-if-serial关系的操作,是无法被重排序的。

  • happens-before:如果一个操作的执行需要对另一个操作可见(不论是在一个线程里还是跨线程),那么两个操作之间存在happens-before关系,无法被重排序。
  • as-if-serial:保证了不论指令如何重排序,单线程程序的执行结果总是不变的。

如:int a = 1; int b = 1; int c = a + b; 我们发现,指令1和指令2不论谁先执行,对结果都没有影响,而指令3却不能先与指令1和指令2执行,所以最终程序的执行序列可能是1->2->3或者2->1->3。 as-if-serial给人一种错觉:单线程程序是按照程序书写的顺序执行的,实际上是遵守了这一关系,并不是一定按顺序执行的。

在多线程中,对上述指令有1 happens-before 3, 2 happens-before 3,而指令1和指令2之间没有happens-before关系,所以对指令1和指令2,在多线程环境中,也可以重排。

综上来看,其实happens-before和as-if-serial的本质是一样的,只要保证了这两种关系,执行的顺序则可以重排序,只不过前者针对多线程来说,后者针对单线程来说。


synchronized和ReentantLock的比较

  • synchronized:synchronized在JDK1.6以前,默认是重量级锁,所以不管资源发生争抢的情况如何,加锁强度都很高(姑且么说吧。。。不知道怎么表达能说出这种意思),所以会有一些争抢不严重的情况下,反而性能下降的表现。在JDK1.6以后,引入了锁消除,锁的四种状态等优化机制,使得synchronized得表现没有那么糟糕了(这也是concurrentHashMap在JDK1.8之后取消ReentrantLock使用synchronized的原因)。
  • ReentantLock:对锁对控制更加灵活,且可以使用newCondition方法对不同线程进行监视。


相同点

它们都是可重入锁。所谓可重入,指的就是如果线程持有的监视器(加锁本质上就是持有某个资源的监视器)为同一对象时,那么对这一段代码块,就可以不断的重入,举例来说:

//代码块的监视器为同一对象,所以可以再次进入内部的synchronized块,这就叫做重入
synchronized(Person.class){
    synchronized(Person.class){
        ...
    }
}

Copy

重入的本质:

对于同步代码块来说,synchronized其实就是两个指令:monitorenter和monitorexit,进入synchronized块就意味着执行monitorenter指令。对任何资源来说,都有一个monitor与之关联,当对应的monitor被持有后,该资源就被锁定,无法再被其他线程获得。monitor有一个entry count与之关联,默认为0,当monitor被持有后,entry count自增为1,发生重入后,就再自增,… 。退出synchronized块意味着执行monitorexit指令,entry conut自减,什么时候减为0,就意味着该monitor不被持有了,资源释放。

对同步方法来说,则是设置了该方法的ACC_SYNCHRONIZED标志,当线程调用方法时,会检查方法有没有设置这一标志,如果有(对于静态方法,监视器是类的class对象,对非静态方法,监视器是当前类的对象(this) ),则获取相应的monitor,执行上述流程。

注:synchronized里发生异常会直接释放监视器,也就是释放锁;对ReentrantLock来说,重入实际上是不断自增AQS中state的值


不同点

  • ReentrantLock可以依靠lockInterruptly方法相应外部的interrupt方法实现可中断锁(线程t1持有资源,线程t2在等待,等太久不想等了,通过在t2中设置lockInterruptly方法响应外部等interrupt实现中断)
  • ReentrantLock通过构造函数参数实现公平锁的设置,默认非公平(synchronized是非公平的)(非公平锁可能会带来吞吐量的提升,但是当线程持有资源时间较长,或请求的平均时长差不多时,带来的提升可能并不明显)
  • ReentrantLock通过tryLock实现超时锁的功能(里面可以设置时间,当线程等待的时候超过这一时间时,就不等了,做其他事情)
  • ReentrantLock通过condition使一个lock对象绑定多个监视器,实现对持有不同监视器对象对线程的通知。

总结:synchronized使用简洁,而ReentrantLock对锁的控制更加细腻,且引入了锁消除,锁的四种状态等优化机制后,synchronized的性能和ReentrantLock也差不多了。在生产环境中,除非要用到ReentrantLock的特有功能,应优先使用synchronized。


Java中关于锁的全部分类

  • 可重入锁:表示可以对一个资源重复加锁而不阻塞。
  • 公平锁:锁的获取是按顺序的,也就是说等待时间最长的线程优先获得锁。
  • 非公平锁:无法保证获取锁的顺序,但可能会保证更大的吞吐量,性能更好。
  • 排他锁(互斥锁,独享锁):在同一时刻只允许一个线程持有这个资源,比如写锁。
  • 共享锁:在同一时刻只允许多个线程持有这个资源,比如写锁。
  • 乐观锁:这是一种思想,认为对同一数据的并发操作,是不会发生安全问题的,那么在更新数据时就不加锁了,乐观地认为不加锁的并发操作是安全的。在Java中的体现就是CAS算法,具体类是Atomic包下的所有类。
  • 悲观锁:这是一种思想,认为对同一数据的并发操作,必然发生安全问题,那么在更新数据时一定要加锁,悲观地认为不加锁的并发操作一定是不安全的。具体体现就是synchronized等各种加锁操作。
  • 自旋锁:这是一种形象的称呼,实际上是乐观锁里CAS算法的表现,CAS操作在Java里一般被套在一个do-while循环中,线程以这种方式不断循环,尝试获取锁,循环形象地看起来就是线程在一个do-while块里不断来回循转等着,所以称为自旋。
  • 分段锁:这是JDK1.7前对concurrentHashMap锁的一种设计。在concurrentHashMap中,默认将这个map分为16个片段(segment),每个片段持有一个数组,数组里的每个位置放的是一个entry链表。当put元素时,先靠indexfor方法判断要把entry放在哪个segment中。并发时,如果put的entry不是放在同一个segment里,肯定线程安全。如果放在同一个segment里,只需要对这个segment加锁就行,其他segment不用加锁。


锁消除,锁粗化,锁升级,锁降级


锁消除

锁消除是基于逃逸分析的,如果一个对象随着方法对应栈帧的压栈而创建,弹栈而销毁,即该对象无法逃脱出这个方法,则这个方法里对该对象的加锁操作可以消除。

public String concat(String s1, String s2){
    StringBuffer sb = new StringBuffer();
    sb.append(s1);
    sb.append(s2);
    return sb.toString();
}

Copy

经过逃逸分析,发现StringBuffer对象无法逃出这个方法,且对方法来说是线程私有的(虚拟机栈是线程私有的),那么对append方法的加锁就可以消除,免去加锁的开销。


锁粗化

JVM探测到对一系列动作都要加锁,就会将加锁范围扩大

public String concat(String s1, String s2){
    StringBuffer sb = new StringBuffer();
    sb.append(s1);
    sb.append(s2);
    return sb.toString();
}

Copy

将加锁加在第一个append方法前,释放锁加在最后一个append后,这样只要加锁一次,而不用两次了。(例子不大准确。。因为这里其实已经锁消除了,但是差不多描述的就是这么个意思)。


锁升级

针对ReentrantReadWriteLock来说,锁升级就是读锁升级为写锁的过程,在持有读锁的情况下,中间加入写锁,随后释放读锁的整个过程中,读锁升级为写锁。

readLock.lock();
    ...
    writeLock.lock();
    ...
readLock.lock();

Copy

锁升级会造成死锁!


锁降级

针对ReentrantReadWriteLock来说,锁降级就是写锁降级为读锁的过程,在持有写锁的情况下,中间加入读锁,随后释放写锁的整个过程中,写锁降级为读锁。

writeLock.lock();
    ...
    readLock.lock();
    ...
writeLock.lock();

Copy

锁降级不会造成死锁!


CAS(Compare and Swap)

CAS(Compare and Swap):CAS操作使用一个期望值与当前值比较,如果比较后发现相等,则用一个新值替代当前值。现可用java.util.concurrent.atomic包下的原子类使用compareAndSet()方法显示调用,实际上该包下的所有原子类的方法,基本都是CAS操作。

但是CAS操作伴随着三个问题:

  • ABA问题:依照上文所说,CAS操作实际上是在检查值有没有发生变化,如果没有则更新。此时假如有一个变量原来值是A,更改为B,又更改为A,则CAS操作会认为该变量的值没有发生过修改,但是实际上是发生过了,这就发生了逻辑混乱。在Java中可以用atomic包下的AtomicStampedReference类解决ABA问题,这个类在更新值时会在值前加入一个版本号,版本戳为int类型。针对上述问题若采用了AtomicStampedReference之后,就是1A -> 1B -> 2A,就可以完美解决问题。还有一个AtomicMarkableReference类与之类似,只不过版本戳是boolean类型。
  • 自旋(循环)时间可能过长:先看一下CAS的源码,以AtomicInteger.getAndIncrement()为例,可以看到,真正的CAS操作被套在一个do-while循环里,这就意味着如果线程长时间得不到资源,就会一直循环等待,这个过程持续在占用CPU资源。
funciton getAndIncrement(){
    return unsafe.getAndAddInt();
}

function getAndAddInt(){
    ...
    do{
        v = getIntVolatile();
    }while(!compareAndSwapInt());
}

Copy

  • 只能保证一个变量的原子操作,当我们要实现对多个变量的原子操作时,就只能用比如synchronized或者ReentrantLock等的悲观锁了。


常用JUC并发工具类与AQS框架


JUC并发工具类

  • CountDownLatch(倒计时门闩):允许一个或者多个线程等待其他线程完成操作(与join操作类似,join操作里实际调用的是wait方法),CountDownLatch初始化了一个int变量,每次调用countDown方法时这个变量都减1,await方法就是判断这个变量是否为0,如果为0就不阻塞了(门闩打开),不为0则调用countDown的线程阻塞(还被锁在门内)。
  • CyclicBarrier(回环屏障):让多个线程到达同一状态(屏障)时被阻塞,直到最后一个线程也到达时,才打开屏障一起执行,构造方法的参数可以指定屏障要拦截的线程数量(每个线程调用await方法告诉CyclicBarrier我到达屏障了,被阻塞),如果想在所有线程到达屏障后执行一个动作(注意:这个动作是在打开屏障前,所有线程到达屏障后),可把这个动作写在构造函数的第二个参数里。 如果屏障设置数大与总的线程数,则屏障就永远无法打开,程序无法向下进行。

注意:CyclicBarrier可以重用,CountDownLatch不能重用。

  • Semaphore(信号量):Semaphore通过取得(acquire方法)许可证(permit)的方式,控制同时访问资源的线程数量,访问完了线程通过release方法释放许可证,供其他线程获取。Semaphore可用来控制并发数,限流。
  • Exchanger(交换者):使用Exchanger的exchange方法,可以完成两个线程间的数据交换。Exchanger提供了一个同步点,若第一个线程先执行exchange方法,会一直等待第二个线程执行,当二者都到达同步点了就交换数据,不然就一直等待。若又超过2个线程使用同一exchanger,则随机2个线程会交换数据,剩下未交换数据的线程会一直等待。


AQS(AbstractQueuedSynchronizer)框架

AQS(AbstractQueuedSynchronizer)队列同步器,是用来构建ReentrantLock和上述并发工具的基本框架。AQS使用了一个volatile int state表示同步状态,state为1表示获得锁,为0表示释放资源,对于ReentrantLock的可重入表现为state的持续自增。AQS还使用了一个叫CLH的双向链表完成线程的排队工作,每一个结点表示了一个线程及其相关信息。

所有的并发工具和ReentrantLock都是重写了以下5个方法,完成锁的获取、释放和查看是否获得锁:

  • tryAcquire:尝试获取锁
  • tryRelease:尝试释放锁
  • tryAcquireShared:尝试获取共享锁
  • tryReleaseShared:尝试释放共享锁
  • isHeldExclusively:判断当前资源是不是线程独占状态

而以上5个方法是通过下列3个方法来获取、改变同步状态的:

  • getState
  • setState
  • compareAndSetState


线程池

为了统一管理线程和免去频繁创建销毁线程带来的不必要开销,引入了线程池,统一管理线程。


线程池分类

Java线程池基本分为5类:FixThreadPool,SingleThreadPool,CachedThreadPool,ScheduledThreadPool,ForkJoinPool,前4种通过Executors的方式直接创建,最后一种比较特殊,单独说明。

  • FixThreadPool:固定线程数的线程池
function newFixedThreadPool(int nThreads){
 return new ThreadPoolExecutor(nThreads, nThreads, 0L, TimeUnit.MILLISECONDS, new LinkedBlockingQueue<Runnable\>()); 
 }

Copy

  • SingleThreadPool:只有一个线程的线程池
function newSingleThreadPool(){
 return new ThreadPoolExecutor(1, 1, 0L, TimeUnit.MILLISECONDS, new LinkedBlockingQueue<Runnable\>()); 
 }

Copy

  • CachedThreadPool:创建一个不设线程上限的线程池
function newCachedThreadPool(){
 return new ThreadPoolExecutor(0, Integer.MAX_VALUE, 60L, TimeUnit.SECONDS, new SynchronousQueue<Runnable\>()); 
 }

Copy

  • ScheduledThreadPool:延迟定期执行任务的线程
function newScheduledThreadPool(){
 super(corePoolSize, Integer.MAX_VALUE, 0, NANOSECONDS, new DelayedWorkQueue<Runnable\>()); //这里的super就是ThreadPoolExecutor
 }

Copy

  • ForkJoinPool涉及到JDK 1.7之后的Fork/Join框架,这个框架的思想是把大任务分割成若干小任务,最终汇总每个小任务的结果得到大任务的结果(很像MapReduce的思想)。这个框架里应用了一种工作窃取算法,具体思想是:线程池中每个线程都有自己的工作队列,当自己的工作都完成了,就会从其他线程的工作队列中偷一个任务执行,以提高整个线程池的工作效率,窃取时则会访问到某线程的工作队列了,为了减少线程争抢,通常采用双端队列的方式实现工作队列,被窃取的线程永远从队列头拿任务执行,窃取任务的线程则从队列的末端窃取任务(注意,当队列里只剩一个任务时,不可避免的会发生线程争抢)。 这个框架的使用就是创建了ForkJoinPool对象,在它的submit方法中传入ForkJoinTask。ForkJoinTask是一个抽象类,我们只需要继承它的子类,并重写compute方法就可以使用fork和join方法了。ForkJoinTask有两个子类:RecursiveAction(用于无返回值的任务),RecursiveTask(用于有返回值的任务)。具体的任务逻辑写在compute方法里。


ThreadPoolExecutor

从上面可以看到,所有线程池的重点就是ThreadPoolExecutor,这也是核心。在《阿里开发规范》里说到,我们应尽量直接new ThreadPoolExecutor来创建线程池,而避免使用上述的方式创建,这样可以更直观的体现出线程池的各个参数,有利于调优。

ThreadPoolExecutor有7个参数:

  • corePoolSize:核心线程的数量,核心线程默认会一直存活,即使是没工作闲置状态
  • maximunPoolSize:允许的最大线程数(等于核心线程数+非核心线程数)
  • keepAliveTime:非核心线程的闲置存活时间,若非核心线程闲置时间超过keepAliveTime,则会被销毁(所以如果线程池没有非核心线程,这个参数并没有用),若线程池调用allowsCoreThreadTimeOut,则该参数对核心线程也有效
  • unit:上述参数的时间单位
  • workQueue:线程池使用的任务队列,目前常用的有7种
  • threadFactory:线程池中创建线程的方式
  • handler:线程无法执行新任务时,拒绝任务的策略


线程池执行新任务的流程

当向线程池提交一个新任务后,而当前线程数<corePoolSize时,会创建一个核心线程执行,若线程数已到corePoolSize,则会被放入某核心线程的工作队列中排队等待,若所有核心线程的队列已满,则会创建一个非核心线程执行,若非核心线程的数量到达maximumPoolSize,则会由配置的handler拒绝该任务。

corePoolSize -> 任务队列排队 -> 新建非核心线程执行 -> 拒绝任务


向线程池提交任务的方法

  • void execute(Runnable):不关心任务的返回结果
  • Future submit(Runnable):不关心任务的返回结果,Future的get方法会返回null
  • Future submit(Runnable, T):关心任务的返回结果,Future的get方法会返回T
  • Future submit(Callable):关心任务的返回结果,Future的get方法会返回T


拒绝策略

  • CallerRunsPolicy:由提交任务者执行被拒绝的任务
  • AbortPolicy:丢弃任务并抛出异常(默认)
  • DiscardPolicy:丢弃任务不抛出异常
  • DiscardOldestPolicy:丢弃队列里最前面(最老)的任务,然后重新执行这个任务


获取任务的结果和设置超时时间

  • 对于一个任务的单个结果可使用Future.get,get方法里可设置超时时间
  • 对于多个任务的多个结果可使用ExecutorCompletionService.take,该方法总是阻塞等待一个任务完成,然后返回该任务的Future,再用get即可获得任务结果,多个任务的超时时间可借用CountDownLatch实现


BlockingQueue

截止JDK 1.8,常用的工作队列有7种:

  • ArrayBlockingQueue:底层由一个数组维护,需传入一个参数作为可容纳任务数量的上界,并且可以设置的公平策略
  • LinkedBlockingQueue:底层由一个链表维护,需传入一个参数作为可容纳任务数量的上界,若不传则使用Integer.MAX_VALUE作为界
  • LinkedBlockingDeque:与LinkedBlockingQueue一样,只不过底层是双端队列
  • SynchronoueQueue:这是一个没有容量的BlockingQueue,消费者消费数据时若无数据,就会一直阻塞,直到等到一个生产者生产了数据。相当于一个消费者在等数据消费时,如果没等到,就一直等着啥也不干,直到等到数据
  • LinkedTransferQueue:可以看作是SynchronoueQueue的进化版,消费者消费数据时若无数据,就先生成一个空元素(篮子)入队(占坑),等生产者生产时发现有一个空元素,就直接把元素填入(放入篮子),相当于一个消费者在等数据消费时,如果没等到,就放个篮子,消费者也不傻等而是去干其他事,直到有生产者来了看见有篮子就直接把数据放进去,等到消费者再来时看见篮子里有数据,直接拿走就行。该过程不再阻塞
  • PriorityBlockingQueue:底层维护了一个基于数组的小顶堆,需传入一个参数作为可容纳任务数量的上界,如果不传则使用默认容量11
  • DelayQueue:底层维护了一个PriorityQueue,优先级按元素的延迟时间决定,延迟时间小的元素放在堆顶。常用来实现延时任务,比如60s后给用户发短信,订单超过30分钟用户未付款则自动取消订单。


线程数设置的参考方案

首先要区分线程池执行的任务是CPU密集型任务,还是IO密集型任务。


线程池的最大线程数

  • CPU密集型任务指的是硬盘、内存性能比CPU可能好的多,所以系统大部分计算时间都用在CPU上,按照这样的说法,CPU密集型任务也需要很多的线程完成,但是线程越多,花在线程上下文切换的时间也就更多,所以我们不能过多的设置线程,应充分发挥CPU性能。一般对于CPU密集型任务,线程池的最大线程数设置为CPU可用核心数+1或者就是CPU可用核心数。CPU可用核心线程数可通过Runtime.getRuntime().availableProcessors()获得。
  • IO密集型任务指的是CPU性能比较好,所以系统大部分时间都花在IO上,CPU资源消耗很少,所以对于IO密集型任务来说,我们可以设置更多的线程,充分利用CPU。一般对于IO密集型任务,线程池的最大线程数设置为2 * CPU可用核心数。


线程池的核心线程数

对于核心线程数来说,可以用过一个公式来设置:核心线程数 = CPU可用核心数 / (1 - 阻塞系数),其中阻塞系数∈(0, 1)。CPU密集型任务的阻塞系数接近0,IO密集型任务的阻塞系数接近1。

阻塞系数要采用性能分析工具确定IO密集型任务消耗时间与CPU密集型任务消耗时间的比值来确定,或者通过经验来设置。


集合框架——Collection

以下类和接口,类与类之间的关系不是严格标准,中间省去了很多不是太重要的接口和类。

截屏2020-04-0600.25.17.png


线程安全

所有不同步的Collection和Map都可以通过Collections工具类下的synchrnoized系列方法使之成为同步容器,但这种方法的效率不如一些容器特定对应的同步容器效率高

xxx name = Collections.synchronizedxxx(new xxx)


ArrayList

  • 底层是一个Object数组
  • 默认容量为10
  • 有一个不可反序列化的modCount,表示ArrayList被修改的次数,增、删、清空操作都会修改modCount,在迭代器里会持有一个modCount的副本,若在迭代器里对ArrayList进行增删改而不适用迭代器提供的add,remove等方法,就会造成modCount和副本的值不一致,从而引发快速失败(fail-fast)抛出异常,规避之后可能会发生的线程安全问题
  • 扩容是扩为原来的1.5倍 newCapacity = oldCapacity + oldCapacity >> 1
  • add,addAll,remove,removeAll等方法,几乎调用的都是System.arraycopy


Vector

  • 与ArrayList基本相同,但是是线程安全的,所有方法都时同步方法(加了synchronized)
  • Vector可以设置增量,如果设置了,扩容时就按照设置的增量加,若没有,扩为原来的2倍


CopyOnWriteArrayList

  • 使用ReentrantLock实现了线程安全的ArrayList。
  • 顾名思义,这是写时复制的ArrayList,所以在写操作(add,remove)时都是新建一个Object数组,然后将旧的Object数组拷贝到新的Object数组上,这是很消耗性能的。所以其实CopyOnWriteArrayList其实适合读多写少的场景。
  • CopyOnWriteArrayList底层的Object数组是volatile的,保证了不同线程间读写的可见性。
  • CopyOnWriteArrayList的迭代器使用的是快照风格(snapshot),也就是直接拷贝的原数组,所以不支持迭代器的写操作。因为CopyOnWriteArrayList已经是线程安全的了,不会发生线程安全问题,所以也就不用支持fail-fast了。


LinkedList

  • 基于双向链表,由于链表的固有特点,LinkedList不支持随机访问,但是增删速度快
  • 与ArrayList有modCount,支持fail-fast
  • add方法默认尾插法,也可以显示的使用addFirst或addLast指定用头插法还是尾插法


PriorityQueue

  • Java中唯一一个使用堆结构的集合
  • 底层是一个Object数组,维护了一个最小堆,不允许存null值,可以自己写comparator进行元素排序 默认容量11
  • 有modCount,支持fail-fast
  • 扩容:若容量<64,则扩容为原来的2倍+2,若容量>64,则扩容为原来的1.5倍 int newCapacity = oldCapacity + ((oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1));
  • 增、删都按照堆的方式进行,需要随时调整堆


集合框架——Map

以下类和接口,类与类之间的关系不是标准的,中间省去了很多不是太重要的接口和类。

截屏2020-04-0600.30.01.png


HashMap

截屏2020-04-0600.30.37.png

  • HashMap的底层实际上是数组+链表+红黑树(JDK1.8之后,JDK1.8之前只是数组+链表),数组的每个位置存的都是Entry链表,每一个位置又称为哈希桶。
  • 采用红黑树的原因是:当链表很长时,HashMap在get查找时,可能会遍历链表,这会造成O(n)的复杂度。而采用红黑树后,因为红黑树是平衡查找树,所以红黑树的查找是二分的,复杂度只有O(logn)。
  • 空参HashMap容量是16,装填因子0.75,阈值是容量 * 装填因子,当HashMap容量大于阈值之后就会扩容,扩容为原来容量的2倍。
  • 当链表里加入新Node之后,若此时链表长度 >= 8且HashMap总Entry数 > 64时(这里笔者要吐槽一下,很多文章写这段的时候都写到>=8条件就满足,然而实际上再点到对应源码处的treeifyBin方法处之后会发现还有一个Entry数 > 64的条件,并且在观察HashMap的成员变量时也会发现有一个MIN_TREEIFY_CAPACITY变量的约束,难道写那些文章的人都不好奇这个变量存在的意义是什么么。。。),链表就转化成红黑树;当链表长度 >= 8但HashMap总Entry数 < 64时,只会进行HashMap的扩容;执行remove后,当红黑树长度 < 6时,当前红黑树又转化为链表。
  • 不论给HashMap设置多大的初始容量,都会转变为大于等于设置的初始容量的最小2次幂数,比如设置了初始容量为23,其实底层会维护一个容量为32的HashMap,这是通过tableSizeFor方法完成的。
  • 扩容后所有元素都要重新hash散列,所以这是很耗费性能的,所以我们初始化一个HashMap时,应充分考虑可能会有多少元素放到HashMap里,避免扩容。重新hash散列后,看元素新hash值新增的一位是1还是0,如果是0则元素新index与原来保持一致,如果是1则新index = 原index + 原容量大小。
  • 将key的hashcode放入hash函数计算得到的hash值,该hash值 & (table.length - 1),即为在table中的下标,也就是Entry存储的位置。
  • hash函数又称为“扰动函数”,是为了让元素散列的更平均。JDK1.8后,函数变为 hash(Object key) { int h = key.hashcode(); reutrn (key == null) ? 0 : h ^ (h >>> 16);},由此也可见,HashMap是允许null键的,且null键默认存在table的第一个位置。
  • put元素的过程:1. 对key求hash值,计算出下标;2. 若当前下标位置没有元素则存入;3.若当前下标位置有元素,再用equals方法判断key是否是同一对象,若是同一对象,用新value覆盖旧value,若不是则发生hash碰撞,用拉链法解决hash碰撞,将新Entry用尾插法(JDK1.8之前是头插法)链在当前哈希桶的末尾;4.若链表程度 >= 8且HashMap总Entry数 > 64时,链表就是转化成红黑树;当链表长度 >= 8但HashMap总Entry数 < 64时,会进行HashMap的扩容;5.更新HashMap的size,若大于阈值,则扩容。
  • get元素的过程:1.根据key求hash值,计算出下标;2. 看这个哈希桶里的头结点是不是该key,是就返回value,不是就按链表或者红黑树的方式继续向下搜索。


HashMap线程不安全的原因

  • JDK1.8之前线程不安全发生在扩容的时候,具体说是发生在resize方法里的transfer方法里,由于扩容时涉及到链表的重新链接,如果有多个线程同时操作同一元素很可能造成环形链表和数据丢失;
  • JDK1.8之后解决了上述问题(取消了transfer方法),但是还是线程不安全的,发生在put方法里,会导致数据覆盖的问题。具体是指:(线程A在判断完某个位置没有元素准备插入时时间片耗尽阻塞,这是线程B也来判断,发现该位置没有元素所以就插入了。此时线程A获得时间片恢复运行,因为之前已经做过判断操作了,所以直接将元素插入,导致线程B刚才插入的元素被覆盖了)。此外put方法里的++size更新容量的操作是非原子性的,所以这个操作也不是线程安全的。


为什么HashMap的容量是2的次幂

因为哈希表在散列元素时用的是除留余数法(index = hash % length),可是%操作比较耗时,设计者打算将%替换为&位运算以提高效率,而hash % length 和 hash & (length - 1) 只有在length是2的次幂数时才等价。所以设计者将HashMap的容量设定为2的次幂。


为什么每次扩容是2倍

因为要保证HashMap的容量是2的次幂。


LinkedHashMap

继承自HashMap,拥有和HashMap几乎一致的特性,但是由于底层是双向链表,所以是有序的,构造参数可以设置一个布尔值指定迭代时元素输出的顺序


Hashtable

  • 老旧的线程安全的HashMap
  • 所有方法都加上了synchrnoized保证线程安全
  • 初始容量11,装填因子0.75,扩容为原来的2倍+1,使用拉链法(头插)解决Hash冲突,并没有采用红黑树

为什么Hashtable扩容是2倍+1而HashMap扩容是2倍:

在Hashtable里求元素存的位置用的是除留余数法(index = hash % length),根据《算法导论》,这个hash是素数的时候,元素在哈希表里会分散的更为平均,由于初始容积是11,发现11*2+1 = 23,23*2+1 = 47 … 经过大量实验,发现*2+1这种方式得到素数的概率更大,所以采用了这种方式。


ConcurrentHashMap

  • 线程安全的HashMap,具有和HashMap一样的参数 -put过程:1. 使用与HashMap相同的方法算出下标;2.若该下标处无元素,则用CAS的方式插入;3.若当前map正在扩容,则当前线程先协助其他线程完成扩容,再插入;4. 若发生hash碰撞,则加上synchrnoized(锁粒度为一个Node)解决碰撞,解决方式与HashMap一样
  • get过程:与HashMap一样
  • JDK1.8之前,ConcurrentHashMap采用segment分段锁设计,使用ReentrantLock保证线程安全,默认将map分为16个segment,每个segment里是一个数组,锁粒度是segment;JDK1.8之后,synchrnoized经过优化,且因为锁粒度下降为node,即使发生线程争抢,使用CAS的方式自旋几十次也差不多能够解决问题了,synchrnoized根本升级不要重量锁,所以在JDK1.8以后,ConcurrentHashMap放弃segment设计,采用CAS+synchronized的方式实现线程安全。 截屏2020-04-0600.39.50.png截屏2020-04-0600.40.08.png


ConcurrentSkipListMap

  • 单线程下实现自定义顺序用TreeMap,多线程下实现自定义顺序用ConcurrentSkipListMap
  • ConcurrentSkipListMap通过在结点上建立索引的方式快速实现插入、删除,redis底层使用了这一数据结构,Java中每一个索引都维护了down和right指针。

跳表的查询过程存疑,笔者在查询资料时还看到了跳表另一种形式的查询方式,笔者尚未确认哪一种是正确的,若有读者详细了解跳表,可与笔者联系

截屏2020-04-0600.41.11.png

截屏2020-04-0600.43.04.png

down指针高度的随机形式请读者参见源码

截屏2020-04-0600.43.28.png


TreeMap

底层使用红黑树进行排序,可以自己传入一个Comparator,重写compare方法。


Hadoop


HDFS逻辑模型

  • HDFS系统中,文件线性按字节切割成块(Block),且每个块都有偏移量(offset)和id
  • 截屏2020-04-0600.46.44.png
  • 各文件block大小可以不一样,比如A的块大小为4KB,B的块大小为8KB,但是每个文件中,除了最后一个块大小可以与其余块不同,其余块大小必须相同
  • block块应根据硬件的I/O特性调整,在Hadoop 1.x版本时,block块大小默认为64MB,在Hadoop 2.x版本时,block块大小默认为128MB
  • 由于是分布式环境,所以block块被分散在集群的各个节点中,但是block具有location(也就是说每个block块会有一个属性记录当前block块的地址)
  • block块具有副本(replication),副本是满足可靠性和性能的关键,副本不能出现在同一节点(为了容灾考虑)上,副本之间没有主从概念,所有副本“地位”一致,比如block 1有3个副本,则说明整个集群中有3个block 1
  • 文件上传时可以指定block块的大小和副本数,上传之后只能修改副本数,不能再更改block块的大小了
  • 文件是一次写入多次读取的,且不支持修改文件,相当于只读。不修改的原因很简单,因为这会造成block块大小不一致,offset不成规律。但是允许在文件后追加数据,因为这不会更改前面block块的大小,不影响offset


HDFS架构设计

  • HDFS是主从架构(Master/Slave)
  • 由一个Namenode(主)和一些Datanode(从)组成
  • 每个文件都包括:文件数据本身(data)和文件的元数据(metadata)
  • Namenode存储和管理metadata,也就是与文件数据无关的元数据,并维护了一个层次型的文件目录树
  • Datanode负责存储data,也就是文件数据本身,并提供block块的读写
  • 客户端(client)与Namenode交互文件元数据,与Datanode交互文件数据

我称Namenode和Datanode为角色,反映到Java中,一个角色对应一个进程。


HDFS角色功能

  • 不论集群有多少台机器,Namenode只有一台,由于要记录所有datanode上的文件元数据、目录结构等信息,且当client并发很高时,Namenode压力其实很大,所以Namenode必须响应很快,所有Namenode完全基于内存存储metadata、目录结构、block映射等信息
  • 但是也正是因为其完全基于内存,所以受内存大小,机器断电丢失数据等客观因素限制,Namenode需要持久化方案保证数据可靠性 (下文具体阐述)
  • Namenode提供副本放置策略 (下文具体阐述)
  • Datanode基于当前操作系统的本地磁盘以文件形式存储block (所以由此可见,HDFS存数据,最终还是将数据存到了磁盘上,HDFS实际本质上就是管理block的存储位置映射)
  • 除了block块本身,还会存每个block块的校验和(类似于MD5字符串的一个东西),以便未来client取走block时做校验,若校验成功,则代表block块没有被破坏,client将block块取走并还能拼回源文件,这保证了数据的可靠性
  • 与Namenode保持心跳,汇报block列表状态

现如今解决数据持久化有两种方案:

  • 日志文件:记录实时发生的操作。完整性好但是占空间,且因文件大记录操作多的原因,恢复比较慢
  • 镜像(或快照,dump):内存全量数据在某一时间点向磁盘的溢写,一般隔一段时间做一次。优点恢复速度快,但因为有时间间隔,所以必然会丢失一部分数据(要注意不能设置太短的时间间隔,因为溢写涉及到IO,IO速度很慢)

HDFS结合以上两种方案:在HDFS中,日志文件叫做Editlog,镜像叫做FsImage。如果能做到日志体积小,记录少,就凸显了日志的优势;如果能做到间隔时间短,就凸显了镜像的优势。于是HDFS给出的Namenode持久化方案就是:最近时间的FsImage+增量的Editlog

比如现在10点Namenode关机,假如有一个9点的FsImage和一个9点到10点的Editlog,接下来重启Namenode后,先加载FsImage,再加载Editlog,就可以得到断电前的全量数据了。**那么问题是:怎么做到恰好会有一个最近时间的FsImage和小体量的Editlog呢?

答案是:滚动地将Editlog更新到FsImage中,以保证最近时间的FsImage和小体量的Editlog。 那么问题是:怎么滚动更新FsImage呢?**

有两种方法:

  • 直接设置较短时间间隔的FsImage
  • 假设现在8点Namenode刚开机,就做一次FsImage,到9点时,将8点到9点的Editlog更新到FsImage中,这样之前8点的FsImage就变成了9点的FsImage (这过程由SecondaryNamenode,也就是另一个机器,另一个进程完成)

Namenode每次启动时还会做一件事情,以刚搭载好Hadoop集群第一次启动为例。

  • Hadoop集群刚搭载好会涉及到格式化过程,格式化操作会产生一个空的FsImage
  • 当Namenode启动时,它从硬盘中读取Editlog和FsImage
  • 将所有Editlog中的事务作用在内存中的FsImage上
  • 并将这个新版本的FsImage从内存中保存到本地磁盘上
  • 然后删除旧的Editlog,因为这个旧的Editlog的事务都已经作用在FsImage上了

同时Namenode在每次启动时,都会先进入一个称为安全模式的状态。

由于Namenode持久化只会持久化文件的metadata,而文件具体每个块的location信息是跟着文件数据存在各Datanode中的,所以Namenode刚启动时会丢失文件所有块的位置信息,也就无法满足client的关于block的请求。所以Namenode每次启动后,会先跟所有Datanode建立心跳,等Datanode汇报块的状态。每当Namenode检测确认某个block的副本数目达到某个最小值之后,那么该block就会被认为是副本安全的(safely replicated)。在一定百分比的block被Namenode检测确认是副本安全之后(加上一个额外的30秒等待时间),Namenode才会退出安全模式。接下来Namenode还会确认哪些数据块的副本没有达到指定数目,并将这些数据块复制到其他Datanode上。

在非Ha(High Available 高可用)模式下,SecondaryNamenode一般是独立节点,SecondaryNamenode不与client产生任何交互,SNN的唯一工作就是将Editlog更新到FsImage中。在core-site.xml文件中有两个参数与这有关:fs.checkpoint.period表示多长时间记录一次FsImage,默认3600秒,fs.checkpoint.size表示一次记录多大的Editlog,也就是Editlog文件的最大值,默认64MB。若FsImage没有间隔1小时,但Editlog超过64MB了,也会触发更新。

截屏2020-04-0600.55.05.png

最后谈一下副本的放置策略:假定当前block副本至少有3个

  • 第一个副本:放置在上传文件的Datanode服务器,如果该服务器在集群外,则随机挑选集群内的一个磁盘不太满,CPU不太忙的节点
  • 第二个副本:放置在与第一个副本不同的机架的节点上 (若放置在同一机架,若当前机架断电或者出现其他故障,则两个副本都会找不到)
  • 第三个副本:放置在与第二个副本相同的机架的其他节点上 (之所以不再另选其他机架的原因是为了节约成本,跨机架通信是需要时间和其他操作的)
  • 更多副本:随机节点 注意在Hadoop1.x版本时,第一个副本和第二个副本放在同一机架,这就会造成上述所述问题,所以官方在Hadoop2.x版本时修正为上述设置

截屏2020-04-0600.55.58.png


HDFS读写流程


写流程

也就是client上传文件到HDFS的流程

1. Client和NN连接创建文件元数据

2. NN判定元数据是否有效,比如判定client有没有权限创建文件,当前HDFS里有没有相同的同级同名文件

3. NN触发副本放置策略,返回一个有序的DN列表

4. Client和DN建立Pipeline连接(为降低带宽消耗和上传延时,client会根据距离,挑选一个与自己最近的DN建立连接)

5. Client将block以更小的packet(64KB)的形式发送,并使用更小的数据chunk(512B)+ chucksum(校验和,4B)(每一个chuck对应一个chucksum)填充这个packet,每填充满一个packet,就发送这个packet

6. Client将packet放入发送队列dataqueue中,并向第一个DN发送

7. 第一个DN收到packet后本地保存并发送给第二个DN

8. 第二个DN收到packet后本地保存并发送给第三个DN,这一个过程中,上游节点同时发送下一个packet,也就是第一个DN给第二个DN发送packet时,client可以同时并行地给第一个DN发第二个packet。这种形式就是流水线的形式,并且各个DN的传输过程是并行的。

9. Hdfs使用这种传输方式,副本数对于client是透明的,也就是client并不需要管要发多少副本,只需要给跟它连接的那个DN发送就行

10. 当block传输完成,DN们各自向NN汇报block状态,汇报的同时client也还在传输下一个block

所以,client的传输和block的汇报也是并行的

截屏2020-04-0600.58.53.png

注意:

  • client只和第一个DN连接,并不和其他DN连接,所以整个传输的形式是pipeline的而不是client与所有DN分发式的连接。
  • 所有连接都是TCP连接。
  • 可能会有DN宕机的现象,如果是最后一个DN宕机影响不大,如果是第一个DN宕机,则client会立刻跟第二个DN建立连接,如果是第二个DN宕机,第一个DN会立刻跟第三个DN建立连接。在这个过程中因为宕机会出现副本数目不足的情况,所以在最后DN跟NN汇报block状态时,NN会通知某一个不太忙的DN在本机再复制一个副本,保证副本数目的可靠性。


读流程

也就是client从HDFS下载文件的流程。

  • 为了降低整体的带宽消耗和读取延时,HDFS会尽量让读取程序读取离它最近的副本。
  • 如果在读取程序的同一个机架上有一个副本,那么就读取该副本。
  • 如果一个HDFS集群跨越多个数据中心,那么客户端也将首先读本地数据中心的副本。
  • Client和NN交互文件元数据获取fileBlockLocation
  • NN会按距离策略排序返回给client
  • Client尝试下载block并校验数据完整性

截屏2020-04-0601.00.17.png

重点:下载

一个文件其实是获取文件的所有的block元数据!


Hadoop HA模式与联邦机制

虽说主从结构相对简单,但是公司中不会采用这种简单的主从结构,因为这会带来两个严重问题

  • 若主节点发生故障,即单点故障,会造成整个集群不可用
  • 主节点内存受限,压力过大

这是两个独立的问题,业内对于这两个问题给出了不同的解决方案,下面具体说明。


Hadoop—高可用解决方案(HA)

所谓Hadoop高可用(HA)实际上就是配置多个Namenode,一个作为主机(Active),其他作为备机(Standby),以便主机出现故障时进行主备切换。Hadoop 2.x只支持一主一备,Hadoop 3.x最高支持一主五备。在HA模式中,只有Active对外提供服务,Standby只是正常运行,不与外界产生交互。高可用的最终目的就是:即使发生了主备切换,在外界看来没有发生任何变化,所以这个方案重点就在于,如何保证主备机子的数据一致、可用、低延迟。

下图是高可用解决方案的示意图

截屏2020-04-0601.03.19.png

下面具体解释这张图

当主机挂机了,client切换至standby遇到的第一个问题就是:Namenode间的数据同步问题。

Namenode上的元数据实际上可分为两类:1. 由client交互操作产生(如mkdir之类的操作);2. 由Datanode提交的数据。

由于Datanode的block汇报同时向Active和Standby汇报,所以由Datanode提交的元数据不会遇到数据同步问题,于是关键就在于由client交互产生的元数据。

同步client交互操作产生的元数据实际上就是同步Namenode的Editlog,由如下几种方案(以mkdir操作为例):

1. 同步阻塞:client需要mkdir,将指令告诉Active,Active告诉Standby有一个mkdir要执行,当Standby执行完了,返回OK给Active,Active返回OK给客户端,这样mkdir才执行完成。

截屏2020-04-0601.04.47.png

这种方案若Standby宕机了,则client的mkdir就永远执行不成功,所以这种方案是强一致性的但是破坏了可用性。

  1. 异步非阻塞:client需要mkdir,将指令告诉Active,Active告诉Standby有一个mkdir要执行,但Active返回OK给client,并不关心Standby是否成功执行了mkdir。 这种方案保证了可用性,但Standby可能在接受到mkdir时就宕机了,所以无法保证一致性。

所以最终我们应当折中这两个方案,产生的一致性称为弱一致性,或称为最终一致性。这时我们需要在Active和Standby中间加入一个相对可靠的组件,Active将mkdir写入该组件且信任该组件(相信mkdir绝对会成功写入组件,且可靠安全),这样即使Standby宕机了,将来都可以从跟这个组件中读到这个操作并恢复(从而也说明了这个组件具有存储的功能)。

若这个组件是单点的,根据墨菲定律也必将不可靠,所以组件也是集群的(上图中的JN),可是此时产生了新的问题,Active要将mkdir写到一个JN,两个JN,还是几个JN中。

于是我们考虑,Active给过半的JN都传递了mkdir,我们就返回OK给client,Standby在读的时候,判断存储了mkdir操作的JN数量过半,这样就保证了mkdir最终会被Standby执行到,且是最新的操作,这就解决了消息一致性的问题。

Paxos算法是一种基于消息传递的一致性算法,该算法覆盖全部场景的一致性问题,各技术会根据自己的技术特种简化算法并实现,该算法的具体内容这里不再赘述,主要说明一下Paxos在这里的体现。

简化一下Paxos的思路,JN的具体方案是这么做的:首先要明确JN的数量,明确JN的权重,在启动集群瞬间,JN就根据权重选举出一个主JN,在JN集群中也构建出了主从结构。以后Active发来的关于增删改查的功能由主JN负责,从JN只负责查询的功能,若从JN收到增删改的请求,也会将该信息传递给主JN,主JN做完增删改再将结果同步到所有的从JN中,有超过一半的从JN同步成功,就给Active返回OK。若主JN宕机了,则会马上再选举出新的主JN。权重可手动分配,也可根据ip地址(全网唯一)由算法算出一个不与其他JN冲突的唯一权重。

截屏2020-04-0601.06.21.png

综上,Namenode的高可用已基本实现,但还有一个问题,设置Namenode为Active还是Standby,以及Active宕机之后切换Standby为Active是我们手工完成的,如何自动化完成这件事?

使用分布式协调服务Zookeeper就可以完成这件事,这也是一个可靠性很高的服务,符合CAP原则并采用了Paxos算法,实现了自己的算法Zab(Paxos的一个简化实现)。

这时我们要向集群中增加新的角色—ZKFC (Zookeeper FailoverController,Zookeeper故障转移),注意这是一个实实在在的JVM进程,与Namenode运行在同一个机器上。这个进程用于

  1. 监视Namenode状态
  2. 连接Zookeeper(下文简称ZK)

接下来说明如何实现自动化确定主备,下文用NN简称Namenode。

当ZKFC与ZK和NN连上之后,两个ZKFC都会尝试在ZK的目录树下某结点上创建一把锁(简单说明一下Zookeeper,Zookeeper的数据结构有点像Linux的文件系统,可以看作是一个树,树中每一个节点代表一个文件路径,称这个树为目录树,结点分为两种:临时(Ephemeral)和永久(Persistent),当连接断开,临时结点会自动删除,永久结点则不会),谁创建成功,对应的NN就是Active,失败的NN就是Standby,这一过程成为抢锁。注意:抢锁时ZKFC还会在该锁上注册一个回调函数,以便ZK通知ZKFC下次抢锁。之后若Active宕机了,对应的ZKFC就会删去这把锁,这时ZK就会触发删除事件,然后ZK就会触发当初所有ZKFC们注册的回调函数(注意:当时ZKFC只是在ZK上注册了一个回调函数以便ZK触发,触发之后真正的具体业务逻辑代码还是在ZKFC上运行的,而不是在ZK上运行),通知其余ZKFC重新抢锁。当有一个ZKFC抢到锁后,该ZKFC会去check刚才宕机的NN是否真的宕机,只有确认了才会将自己对应的NN升级为Active。

可是,ZKFC也是一个进程,若对应的Active还活着而ZKFC发生异常宕机了怎么办?注意:当时创建锁的结点可以是临时结点,那么当ZKFC宕机与ZK连接断开之后,这个结点就会被自动删除,对应的锁也就不复存在了,这时同样触发删除事件,触发回调函数通知其余ZKFC来抢锁,抢到锁的ZKFC同样会去check刚才的Active NN,将其降级为Standby,再将自己对应的NN升级为Active。

综上就是Hadoop的HA方案,谨记Datanode是向所有的NN汇报block信息的,且在HA模式中没有SecondaryNamenode(由于只有Active对外服务,Standby只是正常运行着不对外服务,所以Standby可以周期性地生成FsImage,并及时给Active推送,可以说在HA模式中,Standby替代了SecondaryNamenode的工作)。


Hadoop—联邦机制(Federation)

联邦机制比较简单,就是多设置几个Namenode,将数据对应的元数据分别存在不同的Namenode中,以缓解单点Namenode的压力。所以联邦机制的特点是:元数据分治,复用Datanode存储,不同Namenode的元数据有隔离性,无法互相访问。

截屏2020-04-0601.09.27.png


MapReduce详解

MapReduce(MapReduce是批量计算模型,只有一批数据全部Map完,才会开启Reduce阶段)。

Map(映射):以一条记录为单位做映射,在处理当前记录时不关心其他记录的状态。

Reduce:以一组记录为单位做计算,所以计算前要分组,分组的数据是key-value的形式,分组由map完成。

截屏2020-04-0601.10.48.png

Map:负责数据的映射,过滤,变换,1条记录进,n条记录出

Reduce:负责数据的分解,缩小,归纳,1组记录进,n条记录出


MR过程示意

截屏2020-04-0601.11.36.png

  • Map阶段一个棕色框(叫做一个MapTask)代表一个并行度,并行度的数量由split数量决定。split表示切片,一个split对应一个map计算。一个切片默认代表hdfs里的一个block,block是真实物理存在的,split则是逻辑上定义的。split可以调整大小,使得split可代表多个block,或小于一个block块的数据,这使得我们可以灵活地控制一个并行度要计算多少数据
  • Reduce阶段一个棕色框(叫做一个ReduceTask,也可称为一个分区(partition))代表一个并行度,并行度的数量由开发人员自行决定。同key的数据归为一组,一般而言一个partition里只有一组数据,但是由于并行度数量可人为控制,所以一个partition里也可以有多组数据(即不同的key)。

所以可以总结出如下比例

block : split 的数量比可以是1:1,N:1,1:N

split : map 的数量比只能是1:1

MapTask : ReduceTask 的数量比可以是1:1,N:1,1:N,N:N

分组 : 分区 的数量比可以是1:1,N:1(即所有分组放到一个分区里计算),N:N(即一个分组使用一个分区计算),1:N(即将一个分组放到一个分区计算,剩余分区空闲)


MapTask和Reduce过程细化示意图

截屏2020-04-0601.15.49.png

  • 切片会格式化输出,以记录为单位调用map方法
  • map的输出映射成kv形式,kv会参与一次分区计算,也就是拿着k算出分区号p,所以最终的结果应是(k, v, p)
  • 其实算完之后的结果可以直接存磁盘了,但是每有一条输出就存一次,如果数据量很大,那么IO开销将会很大,所以在内存中开辟一个默认100M的缓冲区,先输出到缓冲区,当缓冲区满时,再全部溢写到磁盘
  • 这时的buffer里完全是乱序的,所以这时可以做两次排序。1.在各分区内按key做一次排序(图中对应的partition, sort and spill to disk)。2.按分区号做一次排序(图中的merge on disk)。这样在fetch时,就不用对文件从头到尾扫描了,且在分区内做reduce计算时,key已按照顺序排在了一次。(第一个排序在内存中发生,速度很快;第二个排序使用归并,只产生一次IO)。这时存在磁盘上的文件,已是分区间有序,分区内有序的了。
  • ReduceTask阶段,因为一个分组中的各数据来自不同的MapTask,所以它们之间是乱序的,还得对它们做一次排序,依旧使用归并排序。
  • 由于迭代器模式的支持,reduce的归并排序和reduce方法的计算可以同时发生。


JobTracke、TaskTracker、Yarn

计算向数据移动面临着诸多问题,如:怎么让机器自动移动,面对block的许多副本,怎么判别移动到的是最合适的Datanode

这个问题牵扯到两个概念:资源管理,任务调度

  • 资源管理:掌握各机器当前可用内存,可用CPU等情况

  • 任务调度:根据可用资源,进行计算任务的分配(也就是任务向哪个Datanode移动)
  • JobTracker:负责资源管理,任务调度
  • TaskTracker:管理被分到Datandoe的计算任务,资源汇报(TaskTracker与JobTracker之间维持心跳,实时汇报当前Datanode资源所剩情况)

截屏2020-04-0601.18.28.png

下面具体阐述client到底做了什么

  1. 根据每次需要计算的数据,咨询NN元数据,得到block信息,算出所需的split数,得到一个split清单,这样map的并行度就得到了。且由于咨询过了元数据,所以得到的split清单还带有block location信息,这样就知道各split的map应该移动到哪些Datanode了。
  2. 生成计算程序未来运行时需要的配置文件(xml)
  3. 移动过程应是可靠安全的,所以client会将计算程序上传到HDFS(这就是移动过程),未来TaskTracker只需要去HDFS下载就行
  4. 调用JobTracker,通知JobTracker需要启动计算了,并告诉JobTracker计算程序放在了HDFS的哪些地方 用大白话说就是:计算向数据移动 -> 那么哪些节点可以移动(需要对整体资源有把控,需要资源管理) -> 确定了节点后怎么通知对方(任务调度)

用大白话说就是:计算向数据移动 -> 那么哪些节点可以移动(需要对整体资源有把控,需要资源管理) -> 确定了节点后怎么通知对方(任务调度)

然而JobTracker还存在三个问题,这也是Hadoop非HA模式遇到的问题

JobTracker是单点的,必存在单点故障问题,存在压力过大问题,且因为JobTracker集成了资源管理和任务调度,所以未来若有新的非MapReduce计算框架,则不能复用资源管理,故而必将各自实现自己的资源管理,但又因为它们部署在同一批硬件上,所以肯定会造成资源争抢。

上述JobTracker为Hadoop 1.x 采用的方案,后面为解决该问题,放弃了这种资源调度方案,在Hadoop 2.x 中引入了全新的资源调度方案,也就是Yarn


Yarn

Yarn就是把资源管理和任务调度分开,也就是解耦了JobTracker的功能

Yarn与MapReduce无关,Yarn是独立的资源层,除了支持MapReduce计算框架,还支持Spark等其他计算模型。

Yarn架构图

截屏2020-04-0601.20.28.png

  • 黄色框代表了一个节点,可以看出Yarn也是主从架构的
  • Yarn取消了JobTracker和TaskTracker,将资源管理放在了Resource Manager,将任务调度放在了Application Master,图中Container代表资源

下面具体阐述一下图中的流程:

  1. Client首先完成上文1.x方案中阐述的1.2.3.步
  2. Client通知Resource Manager(RM),RM挑一个不繁忙的节点通知对应的Node Manager(NM)启动一个Application Manager(AM),AM去HDFS下载split清单,反向从RM申请生成Container RM根据自己掌握的资源情况,找到合适的节点通知NM启动一批Container(注意Container由NM启动,NM与RM之间保持心跳)。Container在逻辑上是一个对象,里面定义了未来在这个节点中要消耗多少内存,多少CPU等属性;物理上是一个进程,占用定义好的内存等资源
  3. Container启动之后会反向注册回AM,这时AM才知道在集群中有多少资源,也就是有多少Container供自己调度
  4. AM将需要下载xml和计算程序的消息发给各Container,各Container自行去HDFS下载,最后执行

总结:RM用于调配资源,与NM保持联系,NM负责启动AM和Container(AM本质上也是一个Container),最终计算任务由AM调度给Container,Container自行下载执行

Yarn的方案成功将JobTracker解耦,不发生资源争抢,即使有一组AM与Container挂了,也不妨碍其他组AM和Container运行。由于有多个AM了,也不会出现单点故障和压力过大的问题。

Yarn架构有完善的消息通信,AM与Container挂机,RM都会重新调度,让NM重启

同样RM也存在单点故障问题,所以Yarn也有对应的HA模式解决该问题,Yarn的主备切换同样由Zookeeper协调。


Zookeeper

Zookeeper是一种用于分布式应用程序的分布式协调服务

Zookeeper提供了一些简单的原语操作(create,delete,exists,get data,set data,get children,sync),分布式程序可以使用这些原语,来实现更高级别的服务,实现同步,配置维护等等。(可以理解为Zookeeper本身比较简单,但复杂的分布式程序可以使用它的操作,封装出复杂的功能)。

在庞杂的集群中,要自己实现协调很容易出现死锁或资源竞争等问题,Zookeeper本是为此而生。

Zookeeper下每一个目录可理解为一个命名空间,Zookeeper使得分布式进程通过共享命名空间实现相互协调。

Zookeeper的数据保存在内存中,这意味着Zookeeper拥有高吞吐量和低延迟。

Zookeeper是复制集群模式,也是主从模式,这意味着客户端可以跟任何一个Zookeeper服务进行查询,但是只能跟leader做增删改。

Zookeeper集群只有一个leader,其余都是follower,所以leader存在单点故障。那么Zookeeper怎么解决这个问题?

实际上,当Zookeeper的leader故障之后,Zookeeper会进入不可用状态(此时无主),会采用一种技术极快的修复故障(官方压测在910个客户端40000+的并发请求下,恢复只需要低于200毫秒)

截屏2020-04-0601.39.58.png

与标准的文件系统不同,Zookeeper命名空间中的节点(znode)及其子节点都可以存储数据(但是因为Zookeeper旨在协调服务不是存储数据,所以每个节点允许存储的数据量很小,最多1MB,所以千万不要把Zookeeper把数据库用)。

znode分为持久节点(persistent)和临时节点(ephemeral)。znode维护了一个stat结构,包含数据更改,访问控制列表,带时间戳的版本号,方便协调更新与验证。临时节点由客户端连接Zookeeper的一个session维护,session断开临时节点就被删除。

Zookeeper还有一些特点:

  • 顺序一致性:来自客户端的更新请求都会按照顺序被应用(因为支持写操作的只有一个唯一的leader,由单机执行更新操作,不容易造成顺序错乱)
  • 原子性:更新操作要么成功要么失败,不会产生多余的中间结果(然而事实上,更新操作在集群中,只要过半的机子成功了,就视为成功) 单系统映像:不论服务端连到集群的哪个机子,都看到同样的服务视图(因为集群是复制集群模式)
  • 可靠性:一旦更新操作被集群应用了,产生的效果就一定会持续到客户端执行更新操作成功(就是说一旦相应了这个更新操作,则客户端那绝不会失败)
  • 及时性:这实际上表示的是最终一致性

下面解析一下Zookeeper的配置文件

截屏2020-04-0601.41.15.png

  • tickTime:leader和follower之间维持心跳每次汇报的间隔时间
  • initLimit:当一个follower想要追随一个leader时,leader最多忍受tickTime * initLimit,也就是默认20秒的初始延迟,超时将会连接失败
  • syncLimit:当leader需要向follower同步操作时,如果超过tickTime * syncLimit,也就是默认10秒时,同步失败
  • dataDir:Zookeeper持久化节点的目录
  • clientPort:客户端连服务的端口号
  • maxClientCnxns:当前Zookeeper节点允许连接的客户端最大值在这里插入图片描述

最后在配置文件的最后配置集群的机器和端口

截屏2020-04-0601.42.14.png

  • 3888:当leader宕机或者还没有leader的时候,节点都通过3888这个端口进行通信,投票选主
  • 2888:当选主完之后leader启2888端口,其他节点连leader的2888端口建立连接,后续在有leader节点的情况下,再有新的follower连接等行为都通过这个端口连接
  • 选主过程实际上是一个节点谦让过程,根据server.X这个x与一个事务id共同考量,让值最大的直接当主,所以这个选主过程极快。


Paxos算法

Paxos算法有一个前提,就是说Paxos只有在一个完全可信稳定的计算环境中才成立,这个环境永不因为网络问题,黑客入侵等原因被破坏。

Paxos描述了这样一个场景,有一个叫做Paxos的小岛(Island)(zookeeper)上面住了一批居民,岛上面所有的事情由一些特殊的人决定,他们叫做议员(Senator)(server)。议员的总数(Senator Count)是确定的(在zoo.cfg中配置的server数量已经确定),不能更改。岛上每次环境事务的变更都需要通过一个提议(Proposal)(zookeeper里的事务改变),每个提议都有一个编号(PID),这个编号是一直增长的,不能倒退(zookeeper里的事务id)。每个提议都需要超过半数((Senator Count)/2 +1)的议员同意才能生效(follower选主投票机制,读写操作)。每个议员只会同意大于当前编号的提议,包括已生效的和未生效的。如果议员收到小于等于当前编号的提议,他会拒绝,并告知对方:你的提议已经有人提过了。这里的当前编号是每个议员在自己记事本上面记录的编号(记录在日志里),他不断更新这个编号(zookeeper必须处理最新的事务,不处理过期的事务)。整个议会不能保证所有议员记事本上的编号总是相同的(因为读写操作,选主等事情,只要过半的server成功通过就行)。现在议会有一个目标:保证所有的议员对于提议都能达成一致的看法。

好,现在议会开始运作,所有议员一开始记事本上面记录的编号都是0。有一个议员发了一个提议:将电费设定为1元/度。他首先看了一下记事本,嗯,当前提议编号是0,那么我的这个提议的编号就是1,于是他给所有议员发消息:1号提议,设定电费1元/度。其他议员收到消息以后查了一下记事本,哦,当前提议编号是0,这个提议可接受,于是他记录下这个提议并回复:我接受你的1号提议,同时他在记事本上记录:当前提议编号为1。发起提议的议员收到了超过半数的回复,立即给所有人发通知:1号提议生效!收到的议员会修改他的记事本,将1号提议由记录改成正式的法令,当有人问任意一个议员电费为多少时,他会查看法令并告诉对方:1元/度。(zookeeper中当更新操作给到leader之后,leader同步给所有follower,只要有超过一半的follower成功同步,就代表事务成功(之后的时间里,leader最终会将这个操作同步到follower的,称为最终一致性)

现在看冲突的解决:假设总共有三个议员S1-S3,S1和S2同时发起了一个提议:1号提议(server1和server2看到自己的事务id都是0,但是又不知道对方想有事务,所以两个人都想发提交事务id为0的事务),设定电费。S1想设为1元/度, S2想设为2元/度。结果S3先收到了S1的提议,于是他做了和前面同样的操作。紧接着他又收到了S2的提议,结果他一查记事本,咦,这个提议的编号小于等于我的当前编号1(server1的事务已生效,事务id变为1了,而server2提交的事务编号还是1),于是他拒绝了这个提议:对不起,这个提议先前提过了。于是S2的提议被拒绝,S1正式发布了提议: 1号提议生效。S2向S1或者S3打听并更新了1号法令的内容,然后他可以选择继续发起2号提议(在server1发布时,server2记事本上的事务id也变为1了,此时server2就以事务id2发出事务,这时server3就会采纳)。

但是现在会出现一个问题,就是可能因为server的数量差异,永远投票无法过半,这就导致了所有server都存活者,但是永远无法解决问题。这是Paxos提出了一个概念——总统(Leader)。只有总统有权提出提议,如果议员有自己的提议,必须发给总统并由总统来提出(这就是zookeeper中follower将更新操作交给leader完成)。


Zab协议(Zookeeper Atomic Broadcast)

Zab协议是Paxos算法的简化版本,只作用在有leader的状态下。

下面是Zab协议具体流程,以create操作举例,每个follewer和leader都维护一个队列进行通信传输

截屏2020-04-0601.43.53.png


Watch机制

watch是客户端对server的一种行为,见下图

截屏2020-04-0601.44.25.png

假如client1已经连接到了server,并创建了一个临时节点(ephemeral)list,现在client2也连接到了server,通过get /list获取到了list里的数据。

如果现在client1与server连接的连接断开,那么临时节点list就应该消失,可是client2如何得知这件事???

其实在使用get命令时,同时client2会对当前目录list及其子目录(如果有)进行监视,当list目录及其子目录发生变化时,就会触发事件(比如client1的连接断开就会触发list的delete事件),此时server会通过回调函数通知client2,list2已被删除。这样client2再做操作时就不会出错(如用get /list时就会发现没有该节点)

实际上也可以通过client1与client2建立心跳来通信,互相告知状态,不过这种方式时效性太慢,而zookeeper本身内部的回调机制,速度极快。


设计模式

设计模式旨在让我们写出更好更优美的代码,其中有六大原则需要我们在日常的代码行为中尽力遵守。本章仅对各模式做简单说明,具体案例篇幅过多不便写出。

  • 单一职责:一个类负责一个功能或领域(高内聚)
  • 开闭原则:对扩展开放,对修改关闭,一个类应在尽量不修改源码的情况下扩展(抽象化和多态是开闭原则的关键)
  • 里氏替换:所有引用父类的地方必须能使用子类和不报错
  • 依赖倒置:抽象不依赖于具体,具体依赖于抽象,我们应面向接口而不是具体实现类编程
  • 接口隔离:每个接口承担单一职责
  • 迪米特原则:尽量减少对象间交互(低耦合)


单例模式

有的类只需要一个类就够了,比如各种Factory和Property、数据库的连接池、日志文件

下面是线程安全的单例模式

private static volatile Single s;
private Single(){}
public static Single getInstance(){
    if(s == null){
        synchronized(Single.class){
            if(s == null)
                s = new Single();
        }
    }
}

Copy


策略模式

根据不同的策略而改变行为,比如java.util.Comparator,我们只需要实现这个接口,不同的类实现自己的compare方法,就有自己的策略。面向接口编程就是策略模式的体现


工厂模式

任何可以产生对象的方法或类,都可以称之为工厂,所以单例其实也是一种工厂,可以称为静态工厂。一个工厂只生产一种产品,而抽象工厂则是生产工厂的工厂,用于针对抽取多个产品的共性,扩展产品簇。


门面模式

提供一个接口供其他人访问,以隐藏内部系统的复杂性,比如java.lang.class


中介者模式

使用一个对象进行消息分发,以减少类之间的直接依赖,也就是解耦,消息中间件就是中介者模式的最好产品


装饰器模式

向现有对象添加新功能而不改变其结构,比如BufferedInputStream(InputStream)...


责任链模式

把一个请求从一个对象传递到下一个对象,直到请求被处理完毕,将请求的发送者与接收者解耦,比如Servlet监听器里的filterChain


观察者模式

一个被观察者可以有多个观察者,并需要把观察者与被观察者解耦以便于扩展观察者,比如在责任链模式中,我们可以对每一个请求处理器设置一个观察者以便于监听。Java中的各种Listener和hook函数,都是观察者模式的体现


组合模式

将多个对象组合起来,看起来是同等的,比如map.putAll(Map m),List.addAll(Collection c)


享元模式

使用池化思想重复利用对象,减少对象创建的次数。比如Integer里-128~127的缓存池,字符串常量池也是典型应用


代理模式

用一个简单对象来代替一个复杂或创建耗时的对象。静态代理比较死板只能代理一个对象,动态代理则可以将代理行为和被代理对象分离,比如java.lang.Proxy


迭代器模式

专属于容器迭代的模式,比如java.util.Iterator


访问者模式

在不改变对象的前提下,为对象增加新的操作,修改或扩展对象的行为,适合一些结构固定的对象,应用场景不广


建造模式

在构造方法入参复杂的情况下使用,以便于轻松灵活的使用构造函数


适配器模式

把一个接口转为另一个接口,比如InputStreamReader(InputStream)把字节流转为字符流,还有Arrays.asList把数组转为List


桥接模式

由于接口与接口的实现有其自己的衍变拓展,所以把抽象与具体实现分离,只在抽象的顶层与具体类的顶层提供一个桥梁链接,从而避免具体类与接口复杂的实现关系


命令模式

将一个操作封装在对象内,以便调用,Java里有Runnable.run。该模式与访问者模式很像


原型模式

使得类的实例能够获得自身的拷贝,比如Object.clone


备忘录模式

生成对象状态里的一个快找,以便对象可以恢复原始状态,常见用于记录状态、回滚或序列化到磁盘


模版模式

父类定义方法模版,子类根据自己的需求具体实现,回调函数就是模版模式的体现


状态模式

根据对象不同的状态,改变对象的行为


解释器模式

一般用作解析器(解析脚本语言等),比如java.util.Format

评论区
Rick ©2018