发表于

前言

每当我们聊到redis的数据结构的时候，我们总会想到string,hash,set,zet,list,但是我们有没有想过这些数据结构又是怎么实现的呢？今天就来聊一下这些常见的数据结构在底层是怎么实现的

SDS(Simple Dynamic String) 简单动态字符串

基本结构

在redis中每个sds.h/sdshdr代表一个SDS值

1
2
3
4
5
6
7
8
9
struct sdshdr {
//记录buf数组已使用字节长度
//等于SDS所保存字符串长度
int len;
//记录buf数组未使用字节长度
int free;
//字节数组，用于保存字符串，末尾以'\0'结束 遵循c风格
char buf[];
}

不采用C风格字符串的原因

  • O(1)时间复杂度获取字符串长度,c风格字符串(char数组)需要遍历整个数组的字符进行计数需要O(n)时间复杂度
  • 防止缓冲区溢出和避免手动扩容 使用c风格字符串的时候在对字符串进行修改的时候，比如字符串拼接等等需要自己考虑对字符串数组进行重新扩容，如果忘记扩容会导致与该char数组后的连续内存空间内容被覆盖，会导致一些意想不到的问题，而在使用SDS的时候，API会帮我们检查SDS的空间是否满足所需的修改要求，不满足的话API会自动的将SDS的空间扩展至执行修改所需的大小，所以使用SDS的话既不会产生缓冲区溢出的问题，也不会需要进行手动扩容
  • 确保2进制安全 使用len来确定字符串的长度而不是通过buf数组中的’\0’字符
  • 减少因修改字符串长度时引起的内存重新分配次数(通过内存预分配机制)

应用场景

  • 普通的键值对的键和值都是使用SDS来存储的
  • AOF缓冲区也是通过SDS来实现的

链表

链表是数据结构中比较常用的一种，可以想到的特性就是O(1)的增删和O(n)的随机访问，redis中的列表就是通过链表来实现的，双向的无环链表，redis构建了自己的链表实现

基本结构

链表中的每一个节点使用一个adlist.h/listNode来表示

1
2
3
4
5
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value;
}listNode;

多个listNode通过prev和next指针组成双端链表，一般情况下只用多个listNode结构就可以组成链表了，如果使用adlist.h/list来持有链表的话，操作起来会比较方便一些

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct list {
//头指针
listNode * head;
//尾指针
listNode * tail;
unsigned long len;
//节点值复制函数
void *(*dup)(void *ptr);
//节点值释放函数
void *(*free)(void *ptr);
//节点值对比函数
int (*match)(void *ptr, void *key);
}list

list提供了头尾指针和链表长度计数器len

特点

  • 应用于列表，发布与订阅、慢查询、监视器等场景
  • 双端五环链表
  • 每个链表用一个list结构来表示，这个结构带有头尾指针和长度

字典

未完待续~

发表于

前言

在平时的编程中，可能会遇到对一组数据进行排序，这个时候我们通常就是调用jdk提供的Arrays.sort()方法来帮助我们进行处理排序，往往并不清楚里面到底做了什么，其实Arrays.sort方法是用了排序算法中的一种，快速排序，那么什么是快速排序？有没有其他类型的排序算法呢？

什么是排序

在了解排序算法之前，我们先来了解下什么是排序
在计算机科学中，一个排序算法是一种能将一串数据按照制定排序方式进行排列的一种算法

排序算法

在了解上文提到的快速排序之前，我们先看看有哪些排序算法

冒泡排序

概述

冒泡排序是一种简单的排序算法，它重复的走访要排序的数列，每次比较两个元素，如果他们顺序错误，则进行交换，走访队列的工作就是重复的进行比较知道没有再需要交换的数据，也就是该数列已经排序完成，这个算法的命名是因为越小的元素会经过交换而慢慢的浮到数列的顶端.
冒泡排序对于n个元素的排序需要进行O(n^2)的比较次数，并且可以原地排序

整体工作流程

  1. 比较相邻的两个元素，如果第一个比第二个大，就交换他们两个
  2. 对每一对相邻元素进行同样的操作，从开始的那一对一直比较到结尾的最后一对，这步完成后最后的元素，将是最大元素
  3. 针对所有元素重复以上步骤，除去最后一个元素
  4. 每次持续对越来越少的元素执行上述步骤，直到没有任何一对数字需要比较

时间复杂度

时间复杂度为O(n^2)

空间复杂度

O(n) 辅助空间O(1)

最优时间复杂度

正序有序数列
O(n^2)

最差时间复杂度

逆序有序数列
O(n^2)

数据结构

数组

是否稳定

是

一些可以优化的点

如果冒泡排序在对一个有序队列进行排序的话，那么在一趟排序下来必定没有发生任何一次交换，反过来说也成立，如果一趟排序中没有发生任何一次交换，则说明队列就是有序的，那么这时候我们只需要引入一个标志，如果一趟排序没有交换发生，我们就可以退出循环，不再需要执行后续的循环了，这样可以使得冒泡排序在最优场景正序有序的数据场景，时间复杂度降为O(n)

插入排序

概述

插入排序是一种简单直观的排序算法，它的工作原理是构建有序队列，对于未排序的数据，会在已排序的队列中从后向前进行反向扫描，找到相应的位置并进行插入，插入排序在实现上只需用O(1)的额外空间，因此在从后向前的扫描的过程中，需要反复将已排序元素逐步向后挪位，从而为新元素提供插入空间。
这个过程和我们平时打扑克的时候，将牌进行一步步排序的过程比较相似，拿到一张牌的时候，我们先认为手中的牌堆是有序的，然后新抓的牌在牌堆里面找到合适的位置并进行插入，反复抓牌并重复该过程，直至牌抓完，手中的牌也就成了有序的

整体工作流程

  1. 从第一个元素开始，该元素被认定为已经有序
  2. 取出下一个元素，在已经排序的元素中从后向前进行扫描
  3. 如果该已排序的元素大于刚才取出的元素，则将该元素进行后移
  4. 重复步骤3，直到找到已排序的元素中小于或等于新元素的位置
  5. 将新元素插入到该位置
  6. 重复步骤2-5

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void sort(int[] data) {

        //选定第一位为已排序数列，从下一个元素开始排序,并逐个对新加入元素(数组后面元素)进行插入排序
        for (int i = 1; i < data.length; i++) {
            int newElement = data[i];
            int j = i - 1;
            //从后向前扫描,如果新插入的元素比已排序队列的待比较元素要小，则后移该元素
            //若新插入的元素比带比较元素大，则证明已经找到该元素的位置
            while (j >= 0 && newElement < data[j]) {
                data[j + 1] = data[j];
                j--;
            }
            //将该元素插入到该位置
            data[j + 1] = newElement;

        }
    }

时间复杂度

O(n^2)

最优时间复杂度

正序有序
O(n)

最差时间复杂度

逆序有序
O(n^2)

数据结构

数组

空间复杂度

O(n) 辅助空间 O(1)

是否稳定

是

一些可以优化的点

由于插入排序在已排序队列中找自己的位置的时候是逐次比较的，由于该队列是有序的，那么这里其实可以简单的进行一个优化，在找位置的时候可以通过二分查找法来进行减少比较次数，但是由于交换次数不变，算法的时间复杂度依旧是O(n^2)

选择排序

概述

选择排序是一种简单直观的排序算法，它的工作原理大致如下，首先在未排序的数据中找最大或者最小的元素，存放到排序队列的起始位置，然后再从剩余未排序的元素中寻找最大或者最小元素，然后放在已排序队列的队尾，以此类推，直到所有的元素均排序完毕

选择排序的优点主要跟数据移动有关，如果某个数据已经位于正确的位置上面，则它不会进行移动，选择排序每次交换一对元素，它们之中至少有一个将被移到其最终位置上面，因此对n个元素的表进行排序的话，只会涉及到至多n-1次交换，在所有完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

交换操作比比较所需要的CPU较少，而选择排序比冒泡排序交换次数要少，所以当空间复杂度要求较高的时候，可以考虑选择排序，实际适用的场景相当罕见

时间复杂度

O(n^2)

最优时间复杂度

正序有序
O(n^2)

最差时间复杂度

逆序有序
O(n^2)

数据结构

数组

空间复杂度

O(n) + 辅助空间O(1)

是否稳定

不稳定

快速排序

概述

快速排序，又称分区交换排序，简称快排，在需要对n个元素进行排序的时候需要O(nlogn)次比较，最坏的时候需要O(n^2)次比较，但这并不常见

工作流程

  1. 从数列中挑选一个基准值(通常会选定起始元素)
  2. 对数列进行分割，将所有小于基准值的放在基准值左侧，大于基准值的元素放在基准值右侧
  3. 递归地对基准值两侧的队列重复1,2步骤

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public static void sort(int[] data, int head, int tail) {
        int startIndex = head;
        int endIndex = tail;
        //递归终止条件，如果分区中元素只有 0 或1 个则已经有序
        if (tail - head <= 1) {
            return;
        }
        int selectedElement = data[startIndex];
        if (head < tail) {
            //按基准值进行分区,左面的分区都小于等于基准值,右面的分区都大于基准值
            while (head < tail) {
                //从右向左找第一个小于等于基准值的元素
                if (data[tail] <= selectedElement) {
                    //找到后，再从左至右找第一个大于基准值的元素，并交换它们
                    if (data[head] > selectedElement) {
                        swap(data, head, tail);
                    } else {
                        head++;
                    }
                } else {
                    tail--;
                }
            }
            //head和tail指针重合,此时说明除了指针处所有元素已经交换完毕,则交换基准值和head指针处元素
            swap(data, startIndex, head);
            //分区后对左右两个子分区进行递归，重复上述操作
            sort(data, startIndex, head - 1);
            sort(data, head + 1, endIndex);
        }
    }

    public static void swap(int[] data, int head, int tail) {
        if (data[head] > data[tail]) {
            //对两个元素进行交换
            data[head] = data[head] + data[tail];
            data[tail] = data[head] - data[tail];
            data[head] = data[head] - data[tail];

        }
    }

时间复杂度

O(nlogn)

最优时间复杂度

O(nlogn)

最差时间复杂度

O(n^2)

空间复杂度

快速排序所使用的空间，需要依照使用的版本决定。使用原地分割的快速排序版本，在任何递归调用前都会使用固定的额外空间，如果需要产生O(logn)次嵌套递归调用，则需要O(logn)的空间

是否稳定

否

一些可以优化的点

基准值选定问题，如果待排序数据是乱序的，基准值是第一个或者最后一个都没问题，但是如果是已经排好序的数据，如果选定第一个或者最后一个为基准值，分区的时候就会出现基准值分区后，只有一个分区有元素

希尔排序

概述

希尔排序，可以称为递减增量的排序算法，是插入排序的一种高效的改进版本
希尔排序是基于插入排序以下两点性质提出改进方法的：

  1. 插入排序在对几乎已经排好序(正序有序)的数据操作时，操作效率高，可以达到线性排序的效率(O(n))
  2. 插入排序一般来说是低效的，因为插入排序每次只能向前移动一位

希尔排序实际上是一个分组排序的过程，每一次通过一个步长对整个数列进行分组，对每个分组内的数据进行插入排序，然后缩小步长，再对每个分组内的数据进行插入排序，直到最后每个分组内的元素只有一个的时候，对该数列的排序演变为普通的插入排序，此时的数列经过方才的过程已经几乎接近有序队列，这时候再使用插入排序效率几乎能达到插入排序的最优时间复杂度即线性排序

在数量较少的时候，希尔排序甚至比堆排序和快速排序要快，但是涉及到大量数据的时候希尔排序还是要比快速排序要慢

工作流程

  1. 选定步长，并建立分组
  2. 对每一个分组进行插入排序操作
  3. 将步长按照一定的规则进行处理，这里步长规则选为每次除以2
  4. 重复步骤1 2 直至步长变为最小步长1
  5. 步长变为1时 对数列的排序演变为普通插入排序，此时数列接近有序，通过最后一遍普通插入排序后所得数列即变为有序队列

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public void sort(int[] data) {
        //对数列按照gap进行分组,当gap>=1时,对每组元素进行插入排序
        for (int gap = data.length /2; gap >= 1; gap/=2) {
            //分组遍历处理
            int groups = data.length / gap;
            for (int i = 0; i <= groups; i++) {
                //对每一组中的元素进行插入排序
                insertSortAlgorithm.sort(data,i,gap);
            }
        }
    }

-------------------------------------------------------------------
//insertSortAlgorithm.sort()
public void sort(int[] data,int start, int gap) {
        for (int i = start + gap; i < data.length; i += gap) {
            int newElement = data[i];
            int j = i - gap;
            while (j >= 0 && newElement < data[j]) {
                data[j + gap] = data[j];
                j -= gap;
            }
            data[j+gap] = newElement;
        }
    }

平均时间复杂度

根据步长序列选定规则决定

最优时间复杂度

O(n)

最差时间复杂度

根据步长序列选定规则决定

步长选定规则 时间复杂度
n /2^i O(n^2)
2^k -1 O(n^3/2)
2^i * 3^j O(nlog^2n)

是否稳定

不稳定

未完待续——

堆排序

概述

时间复杂度

是否稳定

归并排序

概述

时间复杂度

是否稳定

发表于

什么是微服务？它有哪些特点？

微服务是一种软件架构风格，他是以专注于单一职责与功能的小型功能模块为基础，利用模块化的方式组合成大型的复杂应用程序，各功能模块使用与语言无关的API相互通信 —-wikipedia

微服务架构 将单体应用拆分为多个高内聚低耦合的小型服务，每个小服务运行在独立进程，由不同的团队进行开发和维护，服务间采用轻量级通信机制，独立自动部署，可以采用不同的技术进行开发和使用独立的存储空间

微服务的特点

  • 每个微服务仅对单个业务负责，且为该业务的功能负责
  • 每个微服务独立进行部署，不需要依赖其他微服务及相关资源，如数据库缓存等
  • 服务可替代,每个微服务原则上都可以使用不同的语言、框架进行实现，且更换技术实现的微服务对整个业务系统不会造成影响
  • 每个微服务拥有单独的数据存储
  • 每个微服务由小团队进行维护，服务以业务来进行拆分后，每个微服务将有人数不多的团队对其进行维护

为什么要用微服务？

为什么要用微服务，实际上就是每一种架构它的实际的使用场景是怎样的，或者说微服务架构它是为了解决哪些问题而诞生的呢？要聊这个内容实际上就要从单体应用开始讲

什么是单体应用呢?

单体应用就是将应用的所有功能都打包成一个独立的单元，最终以一个WAR或jar存在。

那么单体应用有哪些优点和缺点呢？

单体应用的优点:

  • 便于开发 只需借助IDE的开发调试功能即可完成
  • 易于测试 通过单元测试或者浏览器即可测试
  • 易于部署 打包成单一jar包或者war包，执行jar即可部署

缺点:

  • 复杂性高 随着业务的迭代，项目中的代码会急剧增多，项目模块也会随之增加，模块间的关系变得更加复杂，整个项目变得非常复杂，在
  • 可靠性差 一体化应用某块业务发生改变后，就需要整体重新测试、部署、很容易某个业务模块牵一发而动全身导致整个应用不可用， 微服务则很好的解决了这个问题，某个服务不可用仅仅是影响它自己这一个微服务
  • 扩展性差 一体化应用只能通过在负载均衡器后面放置多个整个应用实例的整体进行水平扩展，非常笨重，而微服务则则可以根据需要对某个微服务进行按需缩放或者扩展
  • 部署或者启动时间变长
  • 交付时间长 微服务架构中 假定我们有100个服务，如果有一个服务中的业务发生了变化，则只需要对这一个服务进行迭代，测试、上线，而不是部署整个应用

其实引入微服务就是为了解决单体应用中的这些缺点而产生的

微服务架构带来了哪些问题?

服务数量成倍增长 维护难度加大

在引入微服务架构后，由单体应用拆分出来的按业务职责划分的服务不可避免的爆炸式增长，使用传统方式运维，无疑就是灾难，这就使得微服务的基石–持续集成在拆分服务之前是必须解决的问题

复杂性提高，学习成本提高

由于引入了新技术，开发人员不得不从头开始学起这些新的内容，尤其是像引入微服务后，这就不可避免的带来了分布式的问题，比如分布式事务、业务体量上来之后，当数据库成为瓶颈后，可能不得不涉及到数据库层面的一些优化，比如分库分表的问题、分库分表之后又带来一些问题、分库分表后唯一主键问题，还有可能涉及到数据迁移的问题和全局表问题，这一系列的问题都是在引入微服务这一体系之后带来的问题，对于这个问题来说，只能说微服务它本身解决了一些问题，它带来的问题，我们可以再找一些别的方式去做处理，我也相信微服务它本身带来的好处要比它带来的复杂性要好的多，所以说对于增加的员工的学习成本来说，微服务是一种趋势，只能说“拥抱变化”了~

请求链路长 问题排查成本较高

引入微服务后，经常会发现，某个服务出现问题，有可能并不是它自身原因导致的，有可能是它的某个下游服务出了问题，当我们逐级排查的时候，调用链路特别长的情况下，找到最根上的出问题的那个节点才能找到真正出问题的节点在哪里，就好比如果生产环境出了问题，这就会导致我们排查问题可能非常的耗时，我们都知道，生产问题尽早排查，尽快排查出问题的根本原因，尽快地修复问题，我们的损失就会越小，所以这个时候就不得不引入”链路追踪”,链路追踪就是把我们涉及到的每一次请求调用了哪些服务，调用的顺序、调用的层级关系以及每次调用花费的时间搞清楚，把这些内容串起来从而通过调用链快速定位到底是哪里出了问题。

未完待续—

发表于

前言

锁机制不仅仅是面试中是一个很高频的面试问题，而且是我们开发中不得不了解的一个内容，今天我们就来聊聊Java中的各中锁

锁的分类

共享锁 VS 排他锁

共享锁和排它锁是针对锁的共享这方面来说的，即共享锁是可以被多个线程共享的，而排它锁不是

共享锁

共享锁又被称为读锁，可以被多个线程所持有，如果线程A对共享资源T加了共享锁，则线程A只能读取共享资源T，并不能对其进行修改，其他线程只能对共享资源T加共享锁，不能加排它锁

排它锁

排它锁又被称为写锁，如果线程A对共享资源T加了排它锁，则线程A既能对共享资源T读又能进行写操作，其他线程不能对共享资源T加任何类型的锁，其中JDK中的synchronized和Lock中写锁的实现类都是排它锁

自旋锁 VS 自适应自旋锁

自旋锁

自旋锁实际上是按照在线程获取锁失败的时候是否会是否挂起该线程来划分的，自旋锁是指在线程获取共享资源的时候获取锁失败了，认为等一小会儿(进行固定次数的自旋)，就可以获得该资源的锁，而不是通过CPU阻塞线程，切换线程的时间片这种方式，通常情况下这比CPU进行线程切换(涉及到用户态和内核态的转换)的开销要小得多，如果自旋完成后，前面锁定资源的线程已经释放了锁，那么当前线程可以拿到锁，不过这是一个不太确定的情况，有可能自旋完成后，前面的线程还没有释放该资源锁。如果锁被占用的时间很短，自旋等待的效果就会非常好。反之，如果锁被占用的时间很长，那么自旋的线程可能只是浪费CPU的时间片，所以自旋的等待时间需要有一定的限度，如果自旋超过了限定次数，没有获得资源锁，就应该挂起线程。

自旋是通过CAS实现的，类似AtomicInteger中调用unsafe进行自增(do-while循环)就是一个自旋操作，如果修改失败就通过循环修改值，直至修改成功

自适应自旋锁

自适应自旋锁是在自旋锁上面进行的改进，它的自旋时间不再是固定值，而是由在同一个自旋锁上一次的自选时间和拥有者的状态来决定的，如果同一个锁对象上，刚刚成功获取过锁，则虚拟机认定它很有可能再次成功，那么它的自旋时间可以允许变得更长，反之则更短

可重入锁

可重入锁又被称为是递归锁，是指同一个线程在外层方法已经拿到锁的情况下，在进入内层方法的时候就会自动拿到锁，java中的Synchronized和ReentrantLock都是可重入锁，可重入锁在一定程度上可以避免死锁的发生。

比如类A有两个实例方法C,D，这两个方法都被sychronized修饰，在C方法内部调用了D，那么某一个线程在进入C已经拿到锁的情况下进入D方法就会自动拿到锁

无锁 VS 偏向锁 VS 轻量级锁 VS 重量级锁

这些锁实际上是按照锁的状态来区分，并且是专门针对synchronized关键字来说的，但是在对这四种锁描述之前需要对一些概念进行了解:对象头和Monitor

一些基本概念

Hotspot虚拟机中，对象在虚拟机中的布局分为3部分，分别是对象头、实例数据、对齐填充
普通对象的对象头包括两部分:MarkWord和ClassMetaData Address(类型指针)，如果是数组对象还额外包括一个额外的数组长度部分

Markword
用于存储对象自身的运行数据，如HashCode,GC分代年龄，锁状态标志，线程持有的锁、偏向线程ID,偏向时间戳等等，占用内存大小跟虚拟机位长一致
Kclass Pointer
类型指针，指向对象的类元数据，虚拟机通过这个指针确定该对象是哪个类的实例

Array Length
数组长度

对象需要存储的数据很多，这已经超出了32bit或者是64bit能表示的限度，此外对象头信息是对象自定义的数据无关的额外存储成本，在考虑虚拟机空间效率的时候，MarkWord被设计成一个非固定的数据结构用来在极小的空间里面存储尽量多的信息，它会根据对象的状态复用自己的存储空间，也就是说MarkWord中存储的内容会伴随着锁的状态变化而变化。

例如在32bit的hotspot的虚拟机中，其各个锁状态下的存储内容如下所示


图片引用自Synchronized与三种锁态

Monitor
Monitor可以理解为一个同步工具或一种同步机制。每一个Java对象都有一个看不见的锁，称为内部锁或Monitor锁，这个Monitor锁实际上就存在于对象的对象头中，对象头中的若干标志位用于标识锁的锁定状态和被哪个线程拥有，在一个线程需要使用一个对象之前，需要先获得它的内置锁，使用之后还需要释放这个内置锁，在使用过程中其它线程无法获取这个锁。

Synchronized概述
Synchronized在JVM里面的实现是基于进入和退出Monitor对象来获取对象锁从而实现方法同步和代码块同步，不同虚拟机的实现细节可能不一样，但都可以通过成对的MonitorEnter和MonitorExit指令来实现，而MonitorEnter和MonitorExit的执行是通过调用操作系统的互斥原语Mutex Lock来实现的，被阻塞的线程会被挂起等待重新调度，会导致CPU在用户态和内核态两个态之间进行切换，比较耗性能，这也是为什么大家对synchronized的一贯印象就是性能较差的原因，jdk在1.6之后对sychronized进行了一系列调整，后来实际上跟Lock的性能不相上下，其实默认还是推荐用synchronized的，语义清晰、操作简单、无需手动关闭

同步方法是通过ACC_SYNCHRONIZED标识符来实现同步的
同步代码块是通过MonitorEnter和MonitorExit两个指令来实现的

MonitorEnter
插入在同步代码块的起始位置，当代码执行到该指令时，将会尝试获取该对象的monitor的所有权，即尝试获取该对象的锁
MonitorExit
MonitorExit插入在方法结束和异常处，JVM保证每个MonitorEnter必须有相应的MonitorExit

无锁

无锁没有对共享资源进行锁定，所有的线程都能访问并修改资源，但是只有一个线程能修改成功，如果多个线程同时修改同一个值，一定会有一个线程会成功，其他修改失败的线程会不断重试(自旋)直到修改成功，这种无锁的情况实际上适用于竞争度不高(读多写少)的情况下，这样自旋一会儿就能获取到资源的修改权，否则自旋非常浪费CPU资源

偏向锁

简介

Hotspot虚拟机的作者发现在大多数情况下不仅不存在锁的竞争，甚至锁总是同一个线程多次获得，所以为了降低获取锁的代价而引入了偏向锁。偏向锁就是指一段代码一直被一个线程访问，那么线程会自动获取锁，直接执行同步代码块，从而降低获取锁的代价

使用场景

只有一个线程进入临界区

锁的获取

  1. 获取对象的markword
  2. 检测MarkWord是否为可偏向状态
  3. 如果为可偏向，并且markword中指向的线程是当前线程则执行同步代码
  4. 如果为可偏向，但指向的线程不是当前线程，通过cas竞争，若竞争成功，则执行同步代码，如果不成功执行5
  5. 偏向锁竞争不成功，证明存在多线程竞争情况，此时偏向锁不再适用，到达全局安全点，获得偏向锁的线程将被挂起，偏向锁升级为轻量级锁，被阻塞在安全点的线程继续往下执行同步代码

锁的释放

线程拥有的偏向锁并不会主动释放，需要等待其他线程来竞争，偏向锁的撤销需要等待全局安全点(没有正在执行的代码的时间点),步骤如下

  • 判断锁对象是否还处于锁定的状态，如果否，则将其恢复到无锁状态，允许其它线程竞争，如果还处于锁定状态，则挂起拥有偏向锁的线程，并将指向该线程的lock record的指针放入对象头的mark word中，升级为轻量级锁(00),然后恢复刚才拥有偏向锁的线程，进入轻量级锁的竞争模式

缺点

如果存在锁的竞争，会带来锁撤销的消耗

轻量级锁

简介

当锁是偏向锁的时候，被其他线程访问出现锁的竞争的时候，就会升级为偏向锁，或者显式关闭偏向锁(jdk1.6以后默认开启，并且默认加的是偏向锁，显式关闭后，默认加的就是轻量级锁),其他线程会通过自旋的方式尝试获取锁，不会阻塞，从而提高性能，一般来说，轻量级锁认为竞争存在，但是竞争的程度较轻，一般两个线程对同一个锁的操作都会错开，或者一个没有拿到锁的线程稍微自旋一会儿就可以拿到锁，如果超过一定自旋的次数后还是没有拿到锁，或者一个线程持有锁，一个线程在自旋的时候，这时候又有第三个线程来竞争锁的时候，轻量级锁就会升级为重量级锁

使用场景

多个线程交替进入临界区，同步代码执行速度较快

锁的获取

  1. 判断当前对象是否为无锁状态(是否为偏向锁位0，锁标志位01)，若是,JVM会在当前线程的栈帧中建立一个名为Lock Record的空间，用于存储锁对象目前MarkWord的拷贝
  2. 将对象头中的MarkWord拷贝到LockRecord中
  3. 拷贝成功后，JVM利用CAS尝试将对象头中MarkWord中设置为指向LockRecord的指针,如果成功执行4，否则执行5
  4. 更新成功，这个线程就拥有了这个对象的锁，并且将对象MarkWord的标志位转为00，表示此对象处于轻量级锁状态
  5. 更新失败，虚拟机会检查对象头中MarkWord是否指向当前线程的栈帧，如果是，代表当前线程已经获取到了这个对象的锁，可以直接执行同步代码，否则自旋执行步骤3，如果自旋结束还没有获得锁，则说明锁的竞争比较激烈，需要膨胀为重量级锁，将MarkWord里面的锁标志位置为10，MarkWord里面这时存放的是重量级锁的指针

    锁的释放

  6. 使用CAS用线程中MarkWord的拷贝替换对象头中的MarkWord,替换成功则执行2，否则执行3
  7. 替换成功，则锁释放成功，整个同步过程完成，对象恢复到无锁的状态
  8. 替换失败，说明有其他线程正在竞争锁，在释放锁的同时，唤醒被挂起的线程

    缺点

始终得不到锁的线程，自旋会消耗CPU资源，造成浪费

重量级锁

重量级锁依靠对象的Monitor锁实现，而Monitor锁又依赖操作系统的Mutex Lock(互斥锁)来实现的

  • 在同步代码块中，jvm通过monitorenter和monitorexit实现同步锁的获取和释放。
  • monitorenter在编译后插入到同步代码块的起始位置，monitorexit被插入到方法结束和异常处。
  • 线程执行monitorenter的时候会尝试获取对象对应的monitor的所有权，即尝试获对象锁
    线程执行monitorexit的时候将会把进入次数-1直到进入次数为0的时候释放锁
  • 同一时刻只有一个线程能够成功，其他失败的线程会放弃锁的竞争被阻塞，放到同步队列中并且等待锁的释放，状态变为Blocked状态，当这个对象锁被释放的时候，会通知队列中等待这个对象锁的线程，使其可以重新竞争锁

使用场景

多个线程同时进入临界区，同步代码执行时间较长

Synchronized用法

修饰实例方法

获取的是对象锁，锁住的是类的实例对象

修饰静态方法

被锁住的是类的class对象

修饰代码块

被锁住的是实例对象

参考文章

不可不说的Java“锁”事

Java中的锁

JAVA锁优化和膨胀过程
彻底理解synchronized
Java 8 并发篇 - 冷静分析 Synchronized（下）

发表于

Java基础之集合类

Collection

Collection接口继承自Iterable接口，Iterable接口允许使用foreach方式遍历，并且定义了一个迭代器

list

List接口继承自Collection接口，存储一组不唯一的有序(插入序)的对象。
采用线性列表存储，长度可以动态改变，可以通过索引访问

ArrayList 和LinkedList区别

ArrayList底层用数组实现，随机访问效率高(O(1)),插入删除效率低(O(n),需要移动后面元素)
LinkedList底层用链表实现，随机访问效率低(O(n)),插入删除效率高(O(1))

ArrayList 和vector的区别

Vector的所有方法都是同步方法,而ArrayList不是，如果需要用到线程安全的list可以考虑用Vector，不过即使需要用线程安全的list我们也是推荐用CopyOnWriteList而不是用Vector

ArrayList是否是线程安全的？

非线程安全，如果需要线程安全，可以使用Vector或者CopyOnWriteList

set

HashSet是如何去重的?

HashSet底层是通过HashMap实现的，HashSet中的元素放在HashMap中的K上面，我们都知道HashMap中的K是不重复的，内容相同的对象hashCode是相同的(HashCode决定元素存储在HashMap中Entry数组中的位置)，并且如果equals方法返回对象是相同的话默认会覆盖Value内容，但其实这里对Hashset来讲value覆盖与否都无所谓(hashset中放入的是PRENSENT对象每次都一样)，因为关注的是hashmap中的k

map

HashMap和HashTable的区别

  • HashTable是线程安全的(所有方法被sychronized修饰)，HashMap不是
  • HashTable不允许有空的key和value，HashMap可以

HashMap是否是线程安全的?如果在多线程环境下并发访问会不会有问题？

HashMap不是线程安全的，jdk1.7的时候HashMap在多线程下并发增加元素扩容的时候会出现环形链表，导致死循环，jdk1.8的时候采用尾插法解决了环形链表的问题，不过还是非线程安全的

HashMap底层是怎么实现的?

HashMap在jdk1.7版本的时候是通过数组+链表的方式实现的,在jdk1.8里面引入了红黑树，在使用拉链法解决hash碰撞的时候，链中元素超过8的时候会转为红黑树

红黑树和二叉排序树、AVL树的区别(延伸话题)

二叉排序树

特点:

  • 若他的左子树不为空，则他的左子树上所有的值小于根节点的值
  • 若他的右子树不为空，则它的右子树上所有的值大于根节点的值
  • 它的左子树和右子树都是平衡二叉树
  • 中序遍历二叉排序树可以得到一个正序有序的序列
  • 通常情况下，操作时间复杂度为O(logn),极端情况下退化为O(n)

这样的数据结构实际上是一个非常典型的适合进行二分法进行查找的结构，每当需要查找元素的时候，先跟根节点比较，就可以判断它在树的哪一端，每次查询都能够缩小一半的候选集，达到时间复杂度为O(logn),但是这里面有个问题，极端情况，如果二叉排序树插入的数据比较极端，比如插入了一组正序有序的数据，使得二叉排序树向右侧单侧倾斜，这时如果查找元素其实就相当于退化成了一个单链表，查找元素的时间复杂度退化为O(n),这种情况下实际上为了提高查找效率就引入了平衡二叉树和红黑树来使得二叉排序树构建的更加平衡。

平衡二叉树(AVL树、高度平衡树)
特点：

  • 是一种平衡二叉树
  • 每一个节点的左子树和右子树的高度差的绝对值不会超过1
    平衡二叉树是在构建二叉排序树的过程中，每插入或者删除一个节点，都会先检查是否破坏了树的平衡性，如果是，则找出最小的不平衡的树，通过右旋或者左旋，使之成为新的平衡树
  • 平衡二叉树的插入、查找、删除的时间复杂度是O(logn)

平衡二叉树追求的是全局平衡，在插入和删除的时候需要调整整棵树，显然这是很费时的，所以希望在调整的时候，不是整棵树进行结构性调整，而是局部性的调整，这样也就引出了红黑树

红黑树是一种二叉查找树，并在此基础上在每个节点上增加了一个存储位来表示节点的颜色，可以是红色或者黑色，通过对任何一条从根节点到叶子结点的路径的各节点着色方式的限制，确保红黑树没有任何一条路径多于其最短路径的两倍长，这保证了红黑树是大致平衡的，而且又不像平衡二叉树那样要求全局性的平衡

红黑树由以下约束保证了红黑树没有任何一条路径多于其最短路径的两倍长
特点：

  • 节点是红色或者黑色
  • 根是黑色
  • 所有叶子节点都是黑色
  • 每个红色节点必须有两个黑色的子节点(从每个叶子到根节点的所有路径上不能有两个连续的红色节点)
  • 从任一节点到其每个叶子节点的所有简单路径都包含相同数目的黑色节点

在通过插入和删除时，会使得红黑树不再符合红黑树的性质，这时，需要少量(O(logn))的颜色变更和不超过三次的树旋转，牺牲了部分平衡性以换取插入删除时少量的旋转操作，整体性能优于AVL树

ConcurrentHashMap是怎么实现的？

Java基础之关键字

final关键字

作用
final可以用来修饰类、方法、变量

修饰类的时候表示该类不能被继承
修饰方法的时候表示该方法在子类中不能被重写
修饰变量的时候，如果修饰的是基本数据类型，一旦被赋值就不能被再次赋值，如果是引用数据类型，只能保证引用所指向的地址不改变，而引用的对象的属性是可以改变的

String为什么是不可变类(延伸问题)

序列化

泛型

接口和抽象类的区别

既然要聊接口和抽象类的区别，就得先聊一下接口和抽象类分别是什么，他们的共同点，然后再聊区别更容易理解一些。

抽象类概述:

当我们在设计一些行为和属性差不多的类的时候其实可以想到面向对象中的继承，用来抽取一个基类，既可以减少重复代码，又可以让代码变得简洁，抽象类的作用就是如此，用于抽取子类通用属性的一种类，只能用作父类，用于给子类继承并且不能够实例化，作为继承的模板，也是多态的一种表现形式
因此我们可以总 结下抽象类的特点

  • 不能被实例化，可以有构造函数
  • 可以包含具体方法，也可以包含抽象方法(必须被子类(非抽象子类)实现)
  • 可以包含成员变量和静态成员变量
  • 子类的抽象方法不可以与父类的抽象方法同名

接口概述:
接口是抽象方法的集合，如果某一个类实现了某个接口，那么他就必须实现这个接口的抽象方法，接口本身并不能做任何事情

接口的特点：

  • 接口中不能有构造方法
  • 接口中可以定义”成员变量”,但是会自动转换为 public static final,即Java中的常量，并且必须被显式初始化
  • 接口中的所有方法都是抽象方法，不能包含具体的方法，也不能包含静态的方法(jdk 8可以包含)
  • 不可以通过new来实例化接口

有了这些内容，我们就可以来回答接口和抽象类的区别了

参数 抽象类 接口
默认的方法实现 可以有 jdk 8之后可以提供，之前不允许有
关键字 子类通过extends继承抽象类 子类通过implements实现接口
访问修饰符 抽象方法可以用public protected这些修饰符 接口方法默认public，不可以用其他修饰符
添加新方法 如果需要往抽象类中添加新的方法，可以提供默认的实现方法，不需要改变现有代码 jdk8以后可以提供默认方法，jdk8之前不可以，所以之前子类必须实现所有接口中的方法
构造方法 可以有 不可以有
设计理念 is-a的关系，是一种关系的延续 like-a的关系，体现的是一种功能扩展

static关键字

作用

  • 修饰成员变量 static可以用来修饰成员变量，也叫静态变量，在内存中只有一个副本，可通过类名访问
    应用场景:
    对象间传值
  • 修饰方法 一般用来抽取工具方法，通过类名直接访问，不可以访问实例变量和实例方法。
  • 修饰代码块
  • 静态内部类
  • 静态导入 写代码的时候可以导入某个类或者某个静态方法或静态变量，用来节省代码

sychronized怎么用的，里面是怎么实现的？

Java基础之数据结构

Java基础之面向对象

面向对象的特点或者说谈谈面向对象的理解？

面向过程的特点是封装、继承、多态
聊到面向对象其实就不得不提面向过程，

面向过程是一种以事件为中心的变成思想，把解决问题的步骤分析出来，使用函数将这一个个步骤实现，使用的时候直接依次调用即可，简单的问题可以通过面向过程的思路来解决，直接有效，但是问题的规模很大时，面向过程的思想就不太够用了，慢慢的出现了面向对象的编程思想
而面向对象是一种以对象为核心的编程思想，把要解决的问题分解成各个对象，建立对象的目的不是为了完成一个步骤，而是为了描述某个对象在解决问题中步骤中的属性和行为。

面向过程和面向对象的优缺点:

面向过程:
优点：

  • 流程化，编程任务明确
  • 效率高，面向过程强调代码的短小精悍，善于结合数据结构来开发高效率的程序
    缺点：
    需要深入思考，耗费精力，代码重用性差，扩展能力差，后期维护难度较大

面向对象：
优点：

  • 结构清晰，模块化结构化，符合人类思维方式
  • 易扩展，代码重用率高，可继承，可覆盖，可以设计出低耦合的系统
  • 易维护，系统低耦合的特点有利于减少后期维护工作量
    缺点：
  • 开销大，修改更改对象内部时，对象的属性不允许直接存取，所以需要增加很多无意义，只负责读写的行为，使得编程工作增加负担，增加运行开销，程序变得臃肿

Java为什么不支持多继承

多继承会产生继承的二义性问题，比如B，C同时继承于A；D又多继承于B和C,这时候如果A中定义了一个f()方法，D到底是会调用谁呢？支持多继承的语言像C++是引入了虚继承来解决这个问题的，十分的晦涩难懂，Java的设计者在这里秉持着简单易用的原则，就把类的多继承给移除了

发表于

前言

今天花了点时间把这段时间需要学习的内容列了一个思维导图，感觉之前的学习方式方法有问题，我们先对需要学习的内容列一个整体的知识体系，对自己有一个整体的把控之后，这时候再去某个细枝末节不断的去探索，去钻研，不至于学习漫无目的，毫无章法可言，以至于“东一榔头，西一棒槌”。

这个知识树会在后续的学习中不断的去扩充，复习的时候会对某一个节点进行系统的展开，持续更新中…

发表于

前言

在讲以下内容之前，我们先通过一个思维导图了解一下本文的大致内容

该图片引用自深入理解Java虚拟机总结-思维导图

————————————————

内存区域划分

这一部分我们主要来详细了解一下运行时数据区的内容

Java虚拟机栈

特点
线程私有区域，生命周期与线程相同

作用
Java虚拟机栈是描述的Java中方法执行的内存模型: 每个方法在执行的同时会创建一个栈帧(stack frame),用于存储局部变量表、操作数栈、动态链接、方法出口等信息。每一个方法调用至执行完成的时候，都对应着一个栈帧在虚拟机栈中从入栈到出栈的过程

局部变量表存放了各种编译器可知的基本数据类型、引用数据类型和returnAddress指令(指向了下一条字节码指令的地址)，我们平时常说的栈指的就是Java虚拟机栈里面的局部变量表的内容

程序计数器

特点
线程私有区域
概述
程序计数器是一块较小的内存空间，可以看作是当前线程执行的字节码的行号指示器。在虚拟机的概念模型里，字节码解释器工作时就是通过改变这个计数器的值来选取下一条需要执行的字节码指令，分支、循环、跳转、异常处理、线程恢复等功能都需要依赖这个计数器来完成

本地方法栈

本地方法栈跟Java虚拟机栈的作用是类似的，他们的区别是Java虚拟机栈执行的是Java方法，而本地方法栈执行的是虚拟机用到的Native方法

Java堆

特点
所有线程共享区域，开发人员关注的核心区域，垃圾收集器管理的主要区域，Java虚拟机中内存最大的一块
概述
该内存区块是Java虚拟机中最大的一块内存区域，在虚拟机启动时创建，几乎所有的对象实例都会在这里进行分配，根据内存回收的角度来看，现在的大多数收集器大多采用分代收集算法，所以Java堆还可以进行进一步的细分:新生代和老年代，新生代再细致一点可分为Eden空间，from survivor空间，to survivor空间。

方法区

特点
所有线程共享区域
概述
方法区与Java堆一样，是各个线程共享的内存区域，用于存储已被虚拟机加载的类信息、常量、静态变量、即时编译器编译后的代码数据等，平时说的常量池就位于该区域。虽然虚拟机规范把方法区作为堆的一个逻辑部分，但他还有另外的一个别名叫非堆，目的就是和Java堆进行区分

运行时常量池

概述
运行时常量池是方法区中的一部分，Class文件中除了有类的版本、字段、方法、接口等描述信息外，还有一项信息是常量池，用于存放编译期生成的各种字面量和符号引用，这部分内容在类加载后进入方法区中的运行时常量池中存放

直接内存

直接内存并不是虚拟机运行时数据区的一部分，也不是Java虚拟机规范中定义的内存区域，但是这部分内存也被频繁的使用，也可能导致OOM异常，在JDK1.4中新加入了NIO,引入了一种基于Channel与Buffer的I/O方式，它可以通过native函数库直接分配堆外内存，然后通过一个存储在Java堆中的DirectByteBuffer对象作为这块内存的引用进行操作，在一些场景中能显著提升性能，因为避免了再Java堆和native堆上来回复制数据

如何判断对象已死？

在Java堆里面几乎存放着Java世界中所有的对象实例，垃圾收集器在进行垃圾回收前，第一件事情就是需要判断哪些对象还“存活”着，哪些对象已经“死去”

引用计数算法

给对象添加一个引用计数器，每当有一个地方引用它时，计数器就+1，引用失效时，计数器就-1，任何时刻计数器为0的对象即不再使用的对象，即可以理解为这个对象已经“死去”了，在下次进行垃圾回收的时候，就可以将这些对象收集。引用计数实现简单，判定效率也很高，但是他很难解决对象之间的相互循环引用的问题

根搜索算法(可达性分析算法)

通过一系列的被称为GC Roots的对象作为起始点，从这些节点开始向下进行搜索，搜索所走过的路径为引用链，当一个对象到GC Roots没有任何引用链相连的话，则证明是对象不可用的。

哪些对象可以用来当做GC ROOTS呢？

  • 虚拟机栈中局部变量表中引用的对象
  • 方法区中类静态属性引用的对象
  • 方法区中常量引用的对象
  • 本地方法栈中JNI引用的对象

垃圾收集算法

复制收集算法

缺点

  • 可用内存大小变为原来的一半
  • 如果对象存活率较高，会出现大量复制，效率会降低

将可用内存按容量分为大小相等的两块，每次可使用其中的一块，当一块中的内存耗尽时，对这块内存区域进行垃圾收集，将这块内存中所有还存活的对象复制到另一块，再把这块的内存区域一次性清理掉，这样每次只对整个半区进行内存回收，分配的时候就不用了考虑内存碎片的问题了

标记清除算法

缺点

  • 先标记，后清除，两阶段效率都不高
  • 产生大量内存碎片

先标记出所有需要回收的对象，标记完成后统一进行回收，后续的垃圾收集算法都是基于这种算法进行改进而得到的，缺点是标记和清除效率都不高，并且标记清除后会有大量的不连续的内存碎片

标记-整理算法

与标记清除算法类似，但是不是直接清除，而是将所有可存活的对象向一端移动，然后直接清理掉边界外的内存。

新生代对象特点

大部分情况都是朝生夕死

老年代对象特点

对象存活率较高，没有额外空间进行分配担保

垃圾收集器

如果说垃圾收集算法是内存回收的方法论，那么垃圾收集器就是内存回收的具体表现。

Serial垃圾收集器

特点

  • 单线程收集
  • 新生代收集器
  • 收集时停止所有工作线程的工作(STOP THE WORLD)
  • 跟其他垃圾收集器相比简单而高效(单个CPU环境下，不存在线程上下文切换的开销，可以获得最高的单线程收集效率)
  • client模式下新生代默认垃圾收集器

Serial收集器是最基本发展最悠久的垃圾收集器，曾经(JDK1.3.1之前)是虚拟机新生代的收集的唯一选择，看名字就可以看出来，这个收集器是一个单线程的收集器，但他的单线程不仅仅体现在它只会使用一个垃圾回收线程去完成垃圾回收工作，更重要的是，在进行垃圾回收的时候必须暂停其他所有的工作线程，直至收集结束。这项工作实际上是虚拟机在后台自动发起和自动完成的，在用户不可见的情况下把用户正常工作的线程全部停掉，这对很多应用来说都是难以接受的。


Serial/Serial Old垃圾收集器运行示意图

ParNew收集器

特点

  • 新生代收集器
  • Serial收集器的多线程版本
  • 许多运行在server模式下的虚拟机中首选的新生代收集器

ParNew收集器实际上就是Serial收集器的多线程版本，除了使用多条线程进行垃圾手机外，其余的控制参数、垃圾收集算法，Stop The World、对象分配规则、回收策略都跟Serial垃圾收集器完全一样。许多运行在server模式下的虚拟机中首选的新生代收集器，除了Serial外，只有Parnew能配合CMS垃圾收集器工作，单CPU场景下，不会比Serial收集器有更好的效果(存在线程切换的开销)，


ParNew 收集器运行示意图

Parallel Scavenge收集器

特点

  • 新生代收集器
  • 使用复制算法，多线程收集
  • 关注点与其他收集器不同，关注的是达到一个可控制的吞吐量

Parallel Scavenge收集器的特点是他关注的是可控制的吞吐量，即CPU运行用户代码的时间/(CPU运行用户代码时间+ 垃圾收集时间)，举例来说，虚拟机运行100分钟，垃圾收集时间为1分钟，那吞吐量就是99%，该收集器提供了两个参数用于精准控制吞吐量，分别是控制最大垃圾收集时间的-XX:MaxGCPauseMillis参数以及直接设置吞吐量大小的-XX:GCTimeRatio参数

MaxGCPauseMillis 是一个大于0的毫秒数，当然并不是设置的越小越好，GC停顿时间的缩短是以牺牲吞吐量和新生代空间来换取的: 比如把新生代调小，收集300M的新生代肯定比500M要快，这会导致垃圾收集会变得比之前更频繁, 举个例子 原来10秒收集一次，每次停顿100毫秒，现在每5秒收集一次，每次停顿70毫秒，停顿时间是缩小了，但是吞吐量也下来了

吞吐量 = CPU运行用户代码的时间/(CPU运行用户代码时间+ 垃圾收集时间)
GCTimeRatio 相当于 1 / 吞吐量

Serial-Old 收集器

特点

  • 老年代收集器
  • 单线程，回收时暂停所有用户线程
  • 使用标记-整理算法

Parallel Old收集器

特点

  • 老年代收集器
  • Parallel Scanvenge的老年代版本，使用多线程
  • 使用标记-整理算法

CMS垃圾收集器

特点

  • 老年代收集器
  • 采用标记-清除算法
  • 并发收集，低停顿
  • CMS MinorGC时会暂停所有的用户线程，并以多线程的方式进行垃圾回收。FullGC时不再暂停应用线程，而是使用若干个后台进程定期的对老年代空间进行扫描，及时回收不再使用的对象

CMS(Concurrent Mark Sweep)收集器是一种以获取最短回收停顿时间为目标的垃圾收集器,很大一部分Java应用集中在互联网网站和B/S系统的服务端上，这类应用重视服务的响应速度，希望系统停顿时间较短，CMS就比较符合这类应用的需求

垃圾收集过程

  • 初始标记 标记GCRoots 能直接关联的对象，速度很快 暂停所有用户线程
  • 并发标记 进行GCRoots Tracing的过程
  • 重新标记 修正并发标记期间 因用户程序继续工作导致标记产生变动的那一部分对象的标记记录，停顿时间比初始标记时间稍长一些，远比并发标记时间短 暂停所有用户线程
  • 并发清除

缺点

  • 因为使用标记-清除算法，易产生大量内存碎片，内存碎片较多时，将会给分配大对象带来很大麻烦 可以通过开启FullGC时候进行内存整理，但是会延长停顿时间
  • CMS收集器无法处理浮动垃圾，可能出现Concurrent Mode Failure而导致另一次的FullGC产生
  • 对CPU资源敏感

浮动垃圾: 并发清除阶段，垃圾收集线程和用户线程并行执行，伴随着程序的运行，就会不断有垃圾产生，这些新产生的垃圾在标记过程之后产生，CMS无法在当次垃圾收集进行


CMS收集器运行示意图

G1垃圾收集器

G1的主要关注点在于达到可控的停顿时间，在这个基础上尽可能提高吞吐量，G1被设计用来长期取代CMS垃圾收集器，和CMS的相同点在于都属于并发收集器，大部分收集阶段都不需要挂起应用程序。区别在于G1没有CMS的碎片化问题，同时提供更加可控的停顿时间

G1将整个堆划分为一个个大小相等的小块，每一块的内存是连续的。和分代算法一样，G1中每个块也会充当Eden,Survivor,Old角色，但是他们不是固定的，这使得内存使用更加灵活

特点

  • 引入分区概念
  • 合理利用垃圾收集各个周期的资源，解决了CMS及其他收集器的缺陷
  • 使用标记-整理算法

对比CMS

  • 不再基于标记-清除算法，不会产生内存碎片
  • 停顿时间可控 G1可以通过设置预期停顿时间来控制垃圾收集时间来避免应用雪崩现象
  • 并行与并发 G1 能够充分的利用CPU，多核环境下的硬件优势来缩短STW的停顿时间

垃圾大致收集过程

  • 新生代垃圾收集
  • 并发收集，和用户线程同时执行
  • 混合垃圾收集
  • 必要的时候FullGC
G1的堆结构

传统的GC收集器将内存空间划分为新生代老年代和永久代(JDK1.8去除了永久代，引入了元空间metaspace)，这种划分的特点是各代的存储地址是连续的，而在G1收集器中则引入了分区的概念，弱化了分代的概念。

  1. 整个堆默认分为2048份均分，每块大小是一致的(1M-32M)
  2. 逻辑上，也会分为Eden,Survivor,Old区，但是各个区的大小是不固定的
  3. 未分配区域可以为任何一个代使用

应用场景

  • 服务器多核CPU,JVM所占内存较大的情况(至少大于4G)
  • 应用在运行过程中会产生大量内存碎片，需要经常压缩空间
  • 想要更可控，可预期的GC停顿周期，防止高并发下应用雪崩现象

内存分配与垃圾回收策略

TODO

虚拟机类加载机制

在了解类加载过程之前，我们其实需要了解一下什么是类加载，Java虚拟机把类的描述数据从Class文件加载到内存，并对数据进行校验、转换解析和初始化，最终形成可以被虚拟机直接使用的Java类型，这就是虚拟机的类加载机制。Class文件由类加载器加载后，在JVM中形成一份描述Class结构的元信息对象，通过该元信息对象可以知晓Class文件的结构信息：如构造函数，属性和方法等，Java允许用户借由这个Class相关的元信息对象间接调用Class对象的功能，这里就是我们经常能见到的Class类

类加载的过程

从图中我们可以看到类加载的过程分为加载、连接和初始化这么几个过程

  • 加载 查找并导入class文件
  • 连接 把类的二进制数据合并至jre中
    • 验证 检查载入class文件数据的正确性
    • 准备 给类的静态变量分配存储空间
    • 解析 将符号引用转成直接引用
  • 初始化 对类的静态变量，静态代码块执行初始化操作

类的加载

加载这一步是指将类的.class文件中的二进制数据读入到内存中，将其放在运行时数据区中的方法区内，然后在堆区创建一个java.lang.Class对象，用来封装类在方法区中的数据结构。类加载的最终产物是位于堆区的Class对象，向开发者提供了访问方法区中数据结构的接口

加载.class文件的方式有以下几种

  • 本地系统直接加载
  • 通过网络下载.class文件
  • 从zip,jar等归档文件中加载.class文件
  • 从专有数据库中提取.class文件
  • 将java文件编译为.class文件

JVM需要通过以下步骤完成对类的加载

  • 通过类的全名获取该类的二进制字节流
  • 将这个字节流代表的静态存储结构转化为方法区的运行时数据结构
  • 在JVM堆区域生成一个代表这个类的java.lang.Class对象，作为方法区这些数据的访问入口

验证

验证主要是为了确保class中的字节流中包含的信息符合当前虚拟机的要求，并且不会危害虚拟机自身的安全。大致会经历以下四个阶段的验证

  • 文件格式验证 验证字节流是否符合Class文件格式的规范，并且能被当前版本的虚拟机所处理，该验证的主要目的就是保证输入的字节流能正确的解析并存储与方法区内，只有经过该阶段的验证，字节流才会进入内存中的方法区进行存储
  • 元数据验证 对类的元数据信息进行语义校验,保证不存在不符合java语言规范的元数据信息
  • 字节码验证 该阶段主要工作是进行数据流和控制流分析，对类的方法进行校验分析，以保证被验证的类的方法在运行时不会做危害虚拟机安全的行为
  • 符号引用验证 最后一阶段的验证 发生在虚拟机将符号引用转变为直接引用的时候，主要是对类以外的信息进行匹配性校验(常量池中的各种符号引用)

准备

解析

什么是双亲委派机制？

双亲委派机制就是说，当类加载器收到类加载请求的时候，该类加载器并不会去加载该类，而是将请求委派给父加载器，如果父加载器上层还有父加载器的话，还会将请求委派给更上层的父加载器，最终会将传送到最顶层的类加载器，只有当父加载器范围内找不到所需的类的时候，会将结果返回给子类加载器，然后由子类加载器尝试自己加载

为什么要使用双亲委派机制？

如果不用双亲委派机制的话，有可能出现同一个类被不同的加载器加载多次的情况，如果发生这种情况，那么同一份字节码可能会在内存中出现多份，并且不同由不同类加载器加载的字节码对象又各不相同，从而导致一些意想不到的结果(相同的类通过不同的classLoader加载后生成的实例，通过instanceof发现不是同一个类)，所以为了安全性考虑，防止核心API被随意篡改，这里采用了双亲委派机制，如果一个类已经被父类加载器加载过了，那么就直接返回，子类加载器不做任何事情。

那么为什么又要破坏双亲委派机制呢？

因为父类的类加载器范围是有限的，有些情况需要委托子类加载器去加载class文件，比如说java.sql.Driver接口是jdk提供的接口，而实现是需要各个厂商来自行实现的，这个时候根本就没有必要用父类加载器去加载了，因为父类加载器是肯定没有该类的(父类加载器只能加载JAVA_HOME/lib下的jar中的class文件)，所以这个时候就需要委托子类加载器去自行加载厂商的driver实现了，从而破坏了默认的双亲委派机制

JVM如何判断两个类是否相同？

前面在双亲委派模型中曾经提到过，当由一个类加载器进行类的加载的时候，首先不由该类加载器进行加载，而是把这个工作交给父加载器，那么这个过程其实就说明了一个问题，当我们需要判断两个类是否是同一个类的时候，实际上需要判断两个内容是否相同

  • 类全名
  • 类加载器
    类全名相同的时候，如果类加载器不同的话，实际上这两个类也会被判定为两个完全不同的类

参考文章

《深入理解Java虚拟机》 第2版

Java类加载机制
【JVM】浅谈双亲委派和破坏双亲委派

发表于

前言

在工作和面试中，Spring作为一个高频出现的框架，不能只是会用，还要对他有一定深入的了解，这样出现问题或者别人跟你交流起Spring的内容的时候，不至于哑口无言，今天我们就来聊聊Spring中我们必须要知道或者掌握的内容

IOC 和AOP

可以说IOC和AOP是Spring的灵魂，我们无时无刻不在用这两个特性，下面就来讲讲IOC和AOP分别都是什么

什么是IOC

IOC(Inversion of Controll)控制反转，什么是控制反转呢？原来需要开发者手动创建对象，现在这个过程交给Spring容器，Spring预先把对象创建好，你需要的时候声明一个属性直接给注入进来，这样把原来创建对象的控制权给反转过来，就叫控制反转，那在这里我们反转的是什么内容呢？实际上这里我们反转的是获取依赖对象的过程，这样其实IOC其实还有另外一个名字，叫依赖注入，这实际上就是Spring来实现IOC的方式，通过提供一个IOC容器，在容器运行期间，利用依赖关系动态地将某种依赖关系注入到对象中。这样的好处就是最大的程度实现对象之间的解耦合。

比如我有一块业务，分别交给了三个人来实现这一块业务中的三个部分，那么只有这三个人的功能组合到一起才能实现这一块业务，那么每个人都必须要清楚自己的那部分业务什么时候要依赖对方的那一部分的业务，什么时候产生交互，这样沟通成本就很高，每个人都要做一次业务串线的操作，而不是专心于自己的业务，那这个时候，假如我们能引入第4个人，由第4个人来负责怎么样组合起这3个人的业务，什么时候交互，那么这三个人就完全不用处理和其他人之间的业务对接，完全专心于自己那一部分的业务开发了，这其实跟SpringIOC容器的思想就是类似的。

什么是AOP

1
2
3
4
5
面向切面的程序设计是计算机科学中的一种程序设计思想，旨在将横切关注点与业务主体进行进一步分离，  
以提高代码模块化的程度。通过在现有代码基础上增加额外的通知机制，能够对被声明为切点(pointcut)  
的代码进行统一的管理和装饰，如对所有‘set*’开头的方法都加上后台日志。该思想能够使得开发人员能够将  
与代码核心业务并不是那么密切相关的功能添加至程序中，同时又不降低业务代码的可读性，面向切面的程序  
设计是面向切面开发的基础   ---摘自WIKIPEDIA

看了维基百科上面的这么长的一段话，想必头都大了，那么到底AOP是什么呢，其实这是一种思想，一种将核心逻辑与边缘逻辑拆分的思想，我们把我们的一块业务进行拆分，把业务强相关的逻辑称为核心逻辑，将不是特别相关的业务逻辑称为边缘逻辑，那么AOP就是把核心逻辑作为关注点，将非核心逻辑也就是边缘逻辑从原有代码剥离出来，形成一个个的切面，在我们的关注点(核心逻辑)前后的连接点插入一系列的切面，将核心逻辑和边缘逻辑通过这种方式编织起来的过程就叫做AOP。这样的好处就是有一些重复的工作像事务管理、日志管理、权限控制等功能封装起来，减少重复代码，并降低模块间的耦合度，有利于系统的拓展性和可维护性。

AOP中的几个重要概念

Advice

切面的工作被称为通知，通知定义了切面是什么以及何时使用，除了描述切面的工作外，通知还解决了何时执行这个工作

JoinPoint 连接点

连接点是指应用执行过程中可以插入切面的一个点

PointCut 切点

一个切面并不需要通知应用所有的连接点，切点有助于缩小切面通知的连接点范围，通知中定义了切面的“什么”和“何时”，而切点则定义了“何处”

Aspect 切面

切面是通知和切点的集合，通知和切点定义了切面的全部内容，它们是什么，在何时何处完成其功能

Introduction 引入

Introduction允许我们向现有的类添加新方法和属性

weaving 织入

织入是将切面应用到目标对象并创建新的代理对象的过程，切面在指定的连接点被织入到目标对象中。在目标对象的生命周期中有很多个点进行织入

  • 编译期 切面在目标类编译时被织入。这种方式需要特殊的编译器，AspectJ的织入编译器就是以这种方式织入切面的
  • 类加载期 切面在目标类加载到JVM时候被织入，这种方式需要特殊的类加载器，它可以在目标类被引入到应用程序之前，增强该目标类的字节码。AspectJ 5就支持这种方式织入切面
  • 运行期 切面在应用运行的某个时刻被织入。一般情况下，在织入切面时候AOP容器会为目标对象动态的创建一个代理对象。SpringAOP就是以这种方式织入切面的。

Spring AOP原理

Spring是在运行时通知对象，通过在代理类中包裹切面，Spring在运行期间把切面织入到Spring管理的Bean中。如下图所示，代理类封装了目标类，并拦被通知方法的调用，再把调用转发给真正的目标bean.当代理拦截到方法调用的时候，在调用bean方法之前，会执行切面逻辑。

Spring在运行时创建代理对象，代理勒种包裹了切面和目标对象，并拦截被通知方法的调用，在执行bean方法之前或之后执行切面逻辑，之后再将请求转发给目标对象


图片引用自Spring AOP 之 通知、连接点、切点、切面
直到应用需要用到被代理的bean时，spring才会创建代理对象，如果是ApplicationContext的话，在ApplicationContext从BeanFactory中加载所有bean的时候，Spring才会创建被代理的对象。因为Spring运行时才创建代理对象，所以我们不需要特殊的编译器就能织入AOP切面

Spring IOC怎么实现的？

IOC实际上是通过在Spring内部持有一个beanfactory 在Spring容器启动的时候将被加上注解的类加载到容器中，当你在使用bean的时候去管Spring的容器拿的一个过程

动态代理和静态代理

要讲动态代理和静态代理，实际上要先从代理模式说起，什么是代理模式呢？代理模式提供了对目标对象的额外访问方式，即通过代理对象访问目标对象这样可以在不修改目标对象的前提下、提供额外的功能操作，扩展目标对象的功能。说完了什么是代理模式，那么静态代理和动态代理分别是什么呢？其实静态代理还是动态代理是从代理类创建的时间节点来看的，静态代理是在程序运行期前，代理类已经存在了(通过developer由ide编写源代码后，对其编译)，而动态代理是在程序运行期间才会创建相应的代理类，也就是每需要使用静态代理来对目标对象进行增强的时候，就需要创建一个目标对象的代理类，这样就可能带来很多的代理类

静态代理中的角色

  1. subject抽象主题类，定义了代理对象和真实对象共同的接口方法，既可以是接口又可以是抽象类
  2. real subject 真实主题类，也就是被委托类或被代理类，该类定义了代理对象表示的真实对象，实现了subject接口，client通过代理对象间接地调用真实主题类中的方法，由real subject来执行真正的业务逻辑
  3. proxy subject 代理类，该类也被称为委托类或代理类，该类中持有一个真实主题类的引用，实现了subject接口，在其实现的接口方法中调用真实主题类中对应的接口方法，起到代理的作用
  4. client 客户端，使用代理

spring中bean的生命周期

  1. 实例化bean实例及
  2. 按照spring上下文对实例化的bean设置对象属性(也就是进行IOC注入)
  3. 如果这个bean实现了BeanNameAware接口，会调用它实现的setBeanName方法，此处传递的就是spring配置文件中id的值
  4. BeanPostProcessor前置处理
  5. 是否实现InitialBean接口
  6. 是否配置自定义的init-method
  7. BeanPostProcessor后置处理
  8. 注册


Spring的启动流程

applicationContext继承体系

通过SpringApplication.run启动主类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
//启动一个计时器,记录应用启动花费的时间()
      StopWatch stopWatch = new StopWatch();
stopWatch.start();
ConfigurableApplicationContext context = null;
FailureAnalyzers analyzers = null;
configureHeadlessProperty();
//
SpringApplicationRunListeners listeners = getRunListeners(args);
listeners.starting();
try {
	//封装命令行启动应用时的参数
	ApplicationArguments applicationArguments = new DefaultApplicationArguments(
			args);
	//1.准备应用运行时环境，
	//2.加载外部配置文件(发布ApplicationEnvironmentPreparedEvent，SpringApplicationRunListeners监听到后，分发给下面的listeners,ConfigFileApplicationListener收到事件后去各个目录扫配置文件(xml,yaml,properties))
	//3.发布ApplicationEnvironmentPreparedEvent 
	ConfigurableEnvironment environment = prepareEnvironment(listeners,
			applicationArguments);
	//打印启动banner图
	Banner printedBanner = printBanner(environment);
	//创建ConfigurableEnvironment的实例(反射)，即创建IOC容器
	context = createApplicationContext();
	analyzers = new FailureAnalyzers(context);
	//容器刷新前调用，允许对容器做进一步的设置和处理
	prepareContext(context, environment, listeners, applicationArguments,
			printedBanner);
	refreshContext(context);
	afterRefresh(context, applicationArguments);
	//容器启动完成，通知关注的listeners(发布ApplicationReadyEvent)
	listeners.finished(context, null);
	//计时器停止计时，打印启动所花费的时间
	stopWatch.stop();
	if (this.logStartupInfo) {
		new StartupInfoLogger(this.mainApplicationClass)
				.logStarted(getApplicationLog(), stopWatch);
	}
	return context;
}
catch (Throwable ex) {
	handleRunFailure(context, listeners, analyzers, ex);
	throw new IllegalStateException(ex);
}

refreshContext

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//设置启动时间，启动标志，移除所有类元数据缓存，准备刷新时的应用上下文
prepareRefresh();
//告子类刷新内部beanFactory
// Tell the subclass to refresh the internal bean factory.
ConfigurableListableBeanFactory beanFactory = obtainFreshBeanFactory();

// Prepare the bean factory for use in this context.
//准备在此上下文中使用的beanfatory(设置classloader和postProcessors,注册环境以及系统变量bean)
prepareBeanFactory(beanFactory);

try {
	// Allows post-processing of the bean factory in context subclasses.
	postProcessBeanFactory(beanFactory);

	// Invoke factory processors registered as beans in the context.
	invokeBeanFactoryPostProcessors(beanFactory);

	// Register bean processors that intercept bean creation.
	//注册bean后置处理器
	registerBeanPostProcessors(beanFactory);
	//做国际化处理i18n
	// Initialize message source for this context.
	initMessageSource();

	// Initialize event multicaster for this context.
	initApplicationEventMulticaster();

	// Initialize other special beans in specific context subclasses.
	onRefresh();

	// Check for listener beans and register them.
	registerListeners();

	// Instantiate all remaining (non-lazy-init) singletons.
	//初始化剩余的所有单例bean
	finishBeanFactoryInitialization(beanFactory);

	// Last step: publish corresponding event.
	//完成容器初始化，发布容器刷新完成事件
	finishRefresh();
}

Spring和SpringBoot的区别

  • SpringBoot内嵌了tomcat容器，不用再使用独立的web容器
  • SpringBoot相对于Spring来说，使用约定由于配置的原则，不在通过以前那种大量的xml配置和引入一大堆依赖，大大简化了开发人员的工作
  • 可以实现自动装配
  • 通过一系列的starter，简化maven或gradle中的配置

SpringMVC工作流程

请求发送至DispatcherServlet,遍历所有的handlermapping，通过请求url找到,找到对应的HandlerExecutionChain，并看是否有前置拦截器，有的话则执行，通过handlermapping执行对应controller方法返回modelAndView给DispatcherServlet，最终返回给客户端

AbstractHandlerMethodMapping#mappingRegistry#mappingLookUp是一个hashMap，存放了url到 类全名+方法名的映射，当请求到达的时候会通过url去这个找到对应的Controller中对应的方法

Spring Cloud中用过哪些组件

注册中心 配置中心 网关

eureka、zookeeper做注册中心有什么区别

feign是如何保证负载均衡和熔断策略的

常用负载均衡策略

Round Robin轮询 将请求依次分配给后端服务，实现简单，请求均匀分配
Weight Round Robin加权轮询 一种改进的轮询算法 在服务上自行设置权值，按比例进行分配请求数的比例
Random 将请求随机分配给后端服务
Hash 根据ip、url或其他信息计算hash值或md5，然后按照服务器数量取模

Docker swarm 负载均衡是怎么处理的

docker swarm它是有路由网格 service mesh提供的一个负载均衡的功能，在docker内部是通过linux 的ipvs(内核级的4层负载均衡)来实现的

Docker swarm的服务发现

在部署一个docker服务时，会在docker内置的DNS服务器中注册服务名+VIP(虚拟IP),我们在通过服务名去请求某一个服务的时候，会去docker的DNS服务器中解析并返回目标容器的虚拟IP,然后再docker网络内部进行路由，最终请求被发送到目标服务

发表于

前言

之前文章提到过，redis的常见使用场景之一就是缓存，那么既然聊到缓存，那么肯定会聊到缓存和数据库双写一致性的问题，今天就来聊聊缓存跟数据库双写一致性的问题

缓存双写一致性问题

只要系统用缓存，就可能涉及到缓存和数据库双写，只要设计到双写，就可能存在一致性问题

缓存更新的策略

先删除缓存，再更新数据库

为什么是删除缓存而不是更新缓存？

  • 缓存更新的代价可能比较高，数据更新如果不是热点数据存在资源浪费
    写多读少的场景，缓存根本没有被读到，反而进行了大量的更新，浪费性能
    写入数据库的值不是直接写入缓存，而是还需要进行一些计算，每次写完数据库再进行一些计算，浪费性能，相比之下，删除缓存反而比较适合

  • 存在脏数据问题,并发更新缓存
    A,B同时更新一条缓存，B先更新完的，A再执行就把B更新过来的数据给覆盖掉了

再回到先删除缓存再更新数据库这里，也存在数据不一致的情况

场景：请求A进行更新操作，请求B进行查询操作

1） 请求A进行写操作，删除缓存
2）请求B进行读操作,查询缓存发现缓存不存在
3）请求B查询数据库，将数据库中的旧值
4）请求B将旧值写入缓存
5) 请求A将新值写入数据库

如果不设置过期时间，请求B写入的脏数据就会一直存在，这种问题如何解决呢？
可以通过延时双删策略,如下述所示

1）删除缓存
2）更新数据库
3）延时等待(等待刚才的读请求完成操作)
4）再次删除缓存

这个延时的时间需要自行评估自己项目中读请求B的操作时间，并在读请求B的耗时上+几百毫秒来确保读请求结束

这种延时会降低吞吐量，怎么办？
将第二次删除改为异步删除，写请求更新完数据库直接返回，不必再延时等待了

如果第二次删除失败了，怎么办？

提供保障机制:删除重试策略

先更新数据库，再删除缓存

这种方案又名为《cache-aside pattern》

  • 读的时候，先读缓存，缓存中如果没有再读数据库，然后取出后放入缓存，同时返回响应
  • 更新的时候，先更新数据库，再删除缓存

这里实际上是应用了一种懒加载的思路，什么时候用，什么时候再去计算缓存

存在的问题

有可能存在脏数据问题

  • 并发读写
  1. 缓存刚好失效
  2. 请求A过来查询缓存，发现没有查询数据库得到一个旧值
  3. 请求B更新数据库
  4. 请求B删除缓存
  5. 请求A将查到的旧值更新到缓存中

这种情况要求3中写操作比2中读操作要快，才有可能导致4比5要快，但是一般来说数据库读的远快于数据库的写操作，因此这一情形比较难出现，但不是不会出现，那么如果出现了这种问题要如何解决呢？

  • 设置缓存的有效期
  • 在请求B更新完数据库后，采用异步延时删除的策略，并确保此时没有操作这一缓存的读请求后再删除缓存
  • 删除缓存失败导致脏数据

一个写操作将新值写入数据库，然后删除缓存时失败，(无论先删缓存还是后删缓存都会存在这个问题)导致缓存数据库数据不一致

解决方案: 提供一个保障重试的机制即可，确保最终缓存被清除

缓存雪崩问题

简介 Redis服务重启或者宕机，或者大量缓存在同一时刻失效，此时大量的请求全部打到DB上，DB有可能扛不住从而导致宕机

解决方案:

  • 给每个缓存设置不同的失效时间(比如用当前时间+随机时间段)，避免大量缓存在同一时间失效
  • 如果是集群部署，将热点数据均匀分布在不同的redis节点上也能避免全部失效的问题，或者热点数据压根就不设置过期时间

缓存穿透

简介 要查询的数据在缓存和数据库内都不存在，用户不断用这样的数据发起请求，导致数据库压力激增，严重时候可能拖垮数据库

解决方案:

  1. 接口层增加校验，用户添加鉴权，接口参数做校验，不合法参数直接返回，缓存和数据库中都取不到的数据，也可以将对应的key value(置为null)缓存起来，过期时间设置短一点，这样可以保证同一个用户无法反复用一个数据暴力攻击
  2. 可以使用布隆过滤器

缓存击穿

缓存击穿其实跟缓存雪崩有点类似，只不过缓存击穿是指单个key值非常热点，在不停的接收并发，当这个key失效的瞬间持续的并发将缓存击穿，流量直接打到DB上面

解决方案:

  • 设置热点数据永不过期
  • 查缓存时候没有拿到去数据库查询，更新缓存的这一步加上互斥锁，拿不到的读请求需要进行一个自旋，等一会儿再去拿数据，拿到互斥锁的请求将数据更新到缓存后，后续的请求全都自旋完毕后直接从缓存中拿数据了，相当于给缓存“续了个费”

参考文章

分布式之数据库和缓存双写一致性方案解析
《我们一起进大厂》系列-缓存雪崩、击穿、穿透

发表于 | 分类于

为什么要进行持久化

为了避免数据丢失

redis作为一个键值对的内存数据库，数据全存储在内存当中，当遇到进程退出或者服务器重启宕机的情况，内存中的数据就会消失，那这样存在redis中的数据就全丢了，如果业务场景仅仅是缓存，数据丢失影响或许不大，重新去数据库加载下再次写入redis就行了，但是如果把业务数据存储在redis中，拿redis当数据库使用的话，数据的丢失可能是毁灭性的打击，所以为了避免数据丢失，redis提供了持久化的支持，可以选择不同的方式将数据从内存保存到磁盘上面，使数据可以持久化保存。

redis持久化机制

RDB

RDB 是一种快照存储持久化方式，持久化的时候fork一个子进程，通过COW机制生成RDB文件保证持久化

具体就是将某一时刻的内存数据保存为一个快照存储到磁盘中，默认文件名为dump.rdb,在redis服务启动的时候会将dump.rdb文件加载到内存中恢复数据。

RDB触发条件

手动触发

通过在redis服务上面执行以下命令触发

  • save 阻塞当前redis服务，执行save期间，redis服务不能处理其他命令，直到RDB过程完成为止，线上环境不建议使用
  • bgsave 执行该命令时，redis会在后台异步进行快照操作，此时redis服务仍然可以响应客户端请求。
    具体操作是执行该命令时，redis会执行fork操作创建一个子进程，由子进程来负责RDB持久化过程，完成后自动结束。这里需要注意的是在fork的时候需要阻塞主进程，一般时间比较短，但是如果redis服务中的数据量比较大的话，fork时间就会变长，且占用内存会加倍。

自动触发

自动触发是通过redis.conf配置自动触发 通过save “”来停用自动触发RDB

主从同步时，从节点向主节点发起同步请求，主节点收到sync命令后，开始执行bgsave

etc: 

1
2
save 60 1 60s内如果 >= 1个key值发生变化则会触发RDB
save 600 10 600s内如果 >= 10个key值发生变化会触发RDB

bgsave流程

  1. 查看是否正在进行RDB或者AOF持久化，是则直接返回
  2. 当前不在进行持久化，fork子进程，子进程和父进程共享内存数据，父进程发生新的写入操作时，会对影响的数据拷贝一个新的内存段(存在疑问)，在新的内存段上面进行处理，不影响子进程的数据
  3. 子进程将数据集写入到一个临时的RDB文件中
  4. 子进程对临时RDB文件写入完成后，用新的RDB文件替换老的RDB文件，并删除旧的RDB文件，并通过信号通知父进程

AOF

AOF(Append Only File)是指把每次执行的写命令追加写入到日志中，当需要恢复数据的时候重新执行AOF中的命令就行了。实际上redis每次写入并没有直接写入到日志文件里，而是写入到一个缓冲区(aof_buf)中，而后通过缓冲区同步策略对缓冲区的数据进行落盘操作

AOF执行流程

AOF不需要设置任何触发条件，对redis服务的所有写命令都会记录到AOF文件中

AOF的写入流程可以分为以下3个步骤

  1. 命令追加(append): 将redis的写命令追加到AOF的缓冲区aof_buf
  2. 文件写入(write)和文件同步(fsync):AOF根据策略将aof_buf中的数据同步到磁盘
  3. 文件重写(rewrite):由于AOF文件会越来越大，定期对AOF文件进行重写，从而对写命令进行压缩

命令追加

redis使用单线程处理客户端命令，如果每次一有写命令就写磁盘的话，磁盘IO就成为redis的性能瓶颈了，所以redis会预先将执行的写命令追加(append)到一个缓冲区(aof_buf)，而不是直接写入文件

文件写入和文件同步

  1. write()
    为了提高文件写入效率，当用户调用write函数将数据写入文件时，操作系统会先把数据写入到一个内存缓冲区中，当缓冲区被填满或者超过了指定时限时，才真正将缓冲区的数据写入磁盘中
  2. fsync()
    虽然操作系统对write函数进行了优化，但是也带来了安全问题，如果宕机内存缓冲区中的数据会丢失，因此操作系统同时提供了同步函数fsync(),强制操作系统把缓冲区内部的数据写入到磁盘中，从而保证了数据持久化

redis提供了appendfsync配置项来控制AOF缓冲区的文件同步策略，可以配置以下三种策略

  • appendfsync always: 每执行一次命令就保存一次

命令写入aof_buf后立即调用系统函数fsync函数同步到aof文件，fsync操作完成后线程返回，整个过程是阻塞的，这种情况下，每次写命令都要同步到AOF文件，硬盘IO成为性能瓶颈,redis只能支持大约几百TPS写入，严重降低了redis的性能

  • appendfsync no: 不强制保存，由操作系统决定什么时候写入磁盘
    命令写入aof_buf中缓冲区调用系统write操作，不对AOF文件做fsync操作，同步由操作系统负责，通常同步周期为30秒，这种情况下、文件同步时间不可控制，且缓冲区内的数据会很多，数据安全性无法得到保证

  • appendfsync everysec: 每秒钟保存一次
    命令写入aof_buf缓冲区后，调用系统write操作，write完成后立即返回，fsync同步操作由单独的进程每秒调用一次，everysec是前两种策略的折中方案，是性能和数据安全性的平衡，因此也是redis的默认设置，也是比较推崇的选项

文件同步策略 write 阻塞 fsync阻塞 宕机时丢失的数据量
always 阻塞 阻塞 最多只丢失一个命令的数据量
no 阻塞 不阻塞 操作系统最后一次对AOF文件fsync后的数据
everysec 阻塞 不阻塞 一般不超过一秒的数据

文件重写

AOF重写过程提供了手动触发和自动触发两种方式

  • 手动触发: 直接调用bgrewriteaof,执行方式类似于bgsave，fork子进程执行具体的操作，fork时阻塞
  • 自动触发: 使用auto-aof-rewrite-min-size和auto-aof-rewrite-percentage配置项以及aof_current_size和aof_base_size的状态确定触发时机
    • auto-aof-rewrite-min-size: 执行AOF重写时,文件的最小体积，默认64M
    • auto-aof-rewrite-percentage: 执行AOF重写时，当前AOF文件的大小(aof_current_size)和上一次AOF重写时AOF文件大小(aof_base_size)的比值

文件重写流程

这里以手动调用bgrewriteaof为例，叙述下AOF重写的流程

  1. 客户端通过bgrewriteaof对redis主进程发起AOF重写请求

  2. 当前不存在bgsave/bgrewriteaof的子进程时，redis主进程fork子进程(阻塞)，如果发现bgrewriteaof子进程则直接返回，如果发现bgsave子进程则等待bgsave操作完成后再fork操作

  3. 主进程fork操作执行完毕后，继续处理其他命令，同时把新的写命令追加到aof_buf中和aof_rewrite_buf缓冲区中

    • 文件重写完成之前，主进程会继续把写命令追加到aof_buf缓冲区，根据appendfsync策略将写命令同步到老的AOF文件内，这样可以避免AOF重写失败造成数据丢失，保证原有AOF文件的正确性
    • 由于fork操作时运用写时复制技术，子进程共享fork操作时的内存数据，主进程会把新命令追加到一个aof_rewrite_buf缓冲区中，避免AOF重写失败造成数据丢失这部分数据

  4. 子进程读取redis进程中的数据快照，生成写入命令后按照命令合并规则批量写入到新的AOF文件

  5. 子进程写完新的AOF文件后，向主进程发信号，主进程更新统计信息，具体可以通过info persistence指令查看

  6. 主进程接收到子进程的写入完成信号后，将aof_rewrite_buf缓冲区的写命令追加到新的AOF文件

  7. 主进程使用新的AOF文件替换旧的AOF文件，AOF重写完成

压缩机制

文件重写之所以能够压缩AOF文件的大小，主要在于以下原因

  • 过期的数据不再写入AOF文件
  • 无效的命令不再写入AOF文件(比如重复的key值设置，set key1 v1 set key1 v2,已经删除的数据)
  • 多条命令可以合并为单个 sadd testset v1 sadd testset v2 sadd testset v3可以合并为 sadd testset v1 v2 v3

RDB、AOF对比

RDB优点

  • 与AOF相比，通过rdb文件恢复数据比较快
  • rdb十分紧凑，适合用来做数据备份
  • 通过RDB进行数据备份，由于使用子进程生成，所以对redis服务器性能影响较小

缺点

  • 如果服务器宕机的话，使用RDB方式会造成某个时间段内的数据丢失，比如设置10分钟同步一次，或者5分钟写入1000次就同步一次，如果在这个过程中服务器宕机，则这个时间段的数据就会丢失
  • 使用save方式会造成服务器阻塞，同步完成后才能响应后续请求
  • 使用bgsave命令的时候，如果内存中的数据太大，fork也会发生阻塞，另外fork子进程会耗费内存
  • redis子进程向磁盘写入数据会带来IO压力

AOF优点：

  • AOF只是追加日志文件，对服务器性能影响较小，速度比RDB要快，消耗的内存较少
    AOF的缺点:
  • AOF生成的日志太大，即使有重写操作，文件体积仍然很大
  • 恢复数据的速度比RDB要慢很多
  • AOF文件重写也是通过fork子进程的方式处理的，存在fork时阻塞问题

RDB还是AOF，如何去选择？

其实策略的选择主要是看业务中对数据丢失的容忍度，如果可以接受十几分钟或者更多的数据丢失，那么就可以选择RDB,性能更好，如果只能接受秒级别的数据丢失，选择AOF方案更为合适

主从复制原理

为什么这里会牵扯到主从复制原理呢？因为主从复制的内容实际上部分内容就是通过RDB来实现的，所以我们在这篇文章一同就给处理了，下面就来讲解下主从复制的原理

如何开启主从复制

  • redis服务启动后，执行slaveof 命令
  • 配置文件配置 slaveof
  • 启动命令后面加 –slaveof

主从复制的开启完全是在从节点发起的，不需要主节点做任何事情

保存主节点信息

保存主节点信息 从节点服务器内部维护了masterhost和masterport两个字段用于存储主节点ip和端口
一般redis节点通过slaveof host port命令来将当前redis服务器变为指定服务器的从属服务器，从而使得从服务器对该主服务器进行复制(实际的复制操作在slaveof命令执行后并返回OK之后才开始进行)

建立socket连接

从节点每秒1次调用复制定时函数replicationCron(),如果发现有主节点可以连接，便会根据主节点的ip和port，创建socket连接，如果连接成功，则：
从节点： 为该socket建立一个专门处理复制工作的文件事件处理器，负责后续复制工作，收接收RDB文件，接收命令传播

主节点:接收到从节点的socket连接后，并将从节点当作是连接到主节点的一个客户端，后续的命令会以从节点向主节点发送命令请求的形式来进行

发送ping命令

从节点向主节点发送ping命令,主要有以下作用

  • 检测主从之间套接字是否可用
  • 检测主节点是否可以接收处理命令

可能有以下三种情况

  • 主节点返回pong,socket 正常，主节点可以处理请求，复制过程继续
  • 超时，一定时间内仍未收到主节点的回复，说明socket连接不可用，从节点断开socket连接并重连
  • 返回pong以外的结果，如果主节点返回其他结果，如果处理正在超时运行的脚本，说明主节点当前无法处理命令，断开socket连接并重连

身份验证

如果从节点设置了masterauth选项，则从节点需要进行身份验证，没有配置则跳过
身份验证是通过从节点向主节点发送auth命令进行的，auth的参数为配置文件中masterauth的值，如果从节点masterauth和主节点requirepass状态一致，则身份验证通过，复制过程继续，不一致，则断开socket连接，并重连

发送从节点端口信息

身份验证通过后，从节点会向主节点发送其监听的端口号,主节点将信息保存到该从节点对应的客户端的slave_listen_port中，这个端口信息是用来在主节点查询主从复制状态的时候显示的端口信息，没什么别的作用(info replication)

同步数据

主从节点的连接建立后，便可以开始数据同步

  • 从节点第一次/重新连接主节点，发起数据同步指令(2.8之前是SYNC,2.8之后是PSYNC)
  • 主节点接收到同步指令后，根据主从节点状态的不同，可以分为全量复制和部分复制

    全量复制

    用于初次复制或者其他无法进行部分复制的情况，将主节点的所有数据发送给从节点，是一个非常重型的操作

全量复制过程

  • 从节点判断无法进行部分复制，向主节点发送全量复制请求(或从节点发送部分复制请求，主节点判断无法进行部分复制)
  • 主节点接收到全量复制的指令后，执行bgsave, 在后台生成RDB文件，并用一个缓冲区记录记录从生成快照的时间节点后开始执行的写命令
  • 主节点bgsave执行完毕后，将RDB文件发送给从节点，从节点首先清除自己的旧数据，然后载入收到的RDB文件，将状态更新至主节点执行bgsave时候的状态
  • 主节点将缓冲区中的所有写命令发给从节点，从节点执行这些命令，从节点更新至主节点最新状态

通过全量复制的过程，可以发现全量复制是非常重型的操作

  • 主节点通过bgsave fork子进程进行RDB持久化，该过程非常耗费CPU，内存，硬盘IO
  • 主节点通过网络节点将RDB文件发送给从节点，对主从节点的带宽消耗很大
  • 从节点清空老数据、载入RDB文件的过程是阻塞的，无法响应客户端的命令

部分复制

用于网络中断后等情况的复制，只将中断期间主节点执行的写命令发送给从节点，比全量复制更加高效，但是如果网络中断时间过长，主节点没有能够完整地保存中断期间的写命令，仍然无法用部分复制还是使用全量复制

由于全量复制在主节点数据量较大的时候效率太低，redis从2.8开始提供部分复制，部分复制的实现依赖于三个重要的概念：

复制偏移量

主节点和从节点分别维护了一份复制偏移量(offset),代表的是主节点向从节点传递的字节数，主节点每次向从节点传播N个字节数据时，主节点offset增加N,从节点每次收到主节点N字节的数据时，从节点的offset增加N
offset用于判断主从节点状态是否不一致，二者offset相同，则一致，二者offset不一致，可以根据offset找出从节点缺少的那部分数据，比如主节点offset是1000，从节点offset是500，则需要把主节点501-1000的数据传递给从节点

复制积压缓冲区

主节点维护的、固定长度的、先进先出的队列，默认大小1MB,当主节点开始有从节点时创建，其作用是备份主节点最近发给从节点的数据，无论有几个从节点，复制积压缓冲区都只有一个，命令传播阶段，主节点除了将写命令发送给从节点，还会发送一份给复制积压缓冲区，作为写命令的备份，复制积压缓冲区还存储了每个字节对应的复制偏移量，由于复制缓冲区定长且先进先出，所以它保存的是主节点最近执行的写命令，时间较早的会被挤出缓冲区

从节点将offset发送给主节点后，主节点根据offset和缓冲区大小判断能否进行部分复制

  • 如果从节点offset偏移量之后的数据，还在主节点复制缓冲区里面，则执行部分复制
  • 如果从节点offset偏移量之后的数据，已不在复制积压缓冲区内，则执行全量复制
服务器运行ID(runid)

每个redis节点(主从均适用)都有一个runid(启动时随机生成的，每次启动都不一样),主节点初次复制的时候，主节点将自己的runid发送给从节点,从节点保存起来，断线重连后从节点将保存的runid发送给主节点，主节点根据runid判断是否能够进行部分复制

  • 如果从节点传过来的runid和和主节点现在的runid相同，证明之前跟主节点同步过，尝试进行部分复制(具体能不能复制还要看offset和复制积压缓冲区情况)
  • 如果传过来的runid和主节点现在的runid不同，说明断线前同步的节点不是当前主节点，只能进行全量复制
psync命令的执行


图片来源《redis设计与实现》

命令传播阶段

数据同步完成后，主节点进入命令传播阶段，主节点将自己执行的写命令发送给从节点，从节点接收命令并执行，从而保持主从节点的数据一致性

参考文章

一文深度揭秘Redis的磁盘持久化机制

Redis 主从复制 原理与用法

redis命令参考#slaveof