高行行的个人博客

原文地址：https://mp.weixin.qq.com/s/ktZpTSKqXjAtOAbXrSMMtg

作者：MageekChiu

segmentfault.com/a/1190000020458807

总结：

在 left join 语句中，左表过滤必须放 where 条件中，右表过滤必须放 on 条件中，这样结果才能不多不少，刚刚好。

廖雪峰的在线 SQL：https://www.liaoxuefeng.com/wiki/1177760294764384/1179611432985088

1. 现象

left join 在我们使用 mysql 查询的过程中可谓非常常见，比如博客里一篇文章有多少条评论、商城里一个货物有多少评论、一条评论有多少个赞等等。但是由于对 join、on、where 等关键字的不熟悉，有时候会导致查询结果与预期不符，所以今天我就来总结一下，一起避坑。

这里我先给出一个场景，并抛出两个问题，如果你都能答对那这篇文章就不用看了。

假设有一个班级管理应用，有一个表 classes，存了所有的班级；有一个表 students，存了所有的学生，具体数据如下（感谢廖雪峰的在线 SQL）：

1

SELECT * FROM classes;

1

SELECT * FROM students;

那么现在有两个需求：

• 找出每个班级的名称及其对应的女同学数量
• 找出一班的同学总数

对于需求 1，大多数人不假思索就能想出如下两种 sql 写法，请问哪种是对的？

1
2
3
4
5

SELECT c.name, count(s.name) as num
    FROM classes c left join students s
    on s.class_id = c.id
    and s.gender = 'F'
    group by c.name

或者

1
2
3
4
5

SELECT c.name, count(s.name) as num
    FROM classes c left join students s
    on s.class_id = c.id
    where s.gender = 'F'
    group by c.name

对于需求 2，大多数人也可以不假思索的想出如下两种 sql 写法，请问哪种是对的？

1
2
3
4
5

SELECT c.name, count(s.name) as num
    FROM classes c left join students s
    on s.class_id = c.id
    where c.name = '一班'
    group by c.name

或者

1
2
3
4
5

SELECT c.name, count(s.name) as num
    FROM classes c left join students s
    on s.class_id = c.id
    and c.name = '一班'
    group by c.name

请不要继续往下翻 ！！先给出你自己的答案，正确答案就在下面。
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~

答案是两个需求都是第一条语句是正确的，要搞清楚这个问题，就得明白 mysql 对于 left join 的执行原理，下节进行展开。

2. 根源

mysql 对于 left join 的采用类似嵌套循环的方式来进行从处理，以下面的语句为例：

1

SELECT * FROM LT LEFT JOIN RT ON P1(LT,RT)) WHERE P2(LT,RT)

其中 P1 是 on 过滤条件，缺失则认为是 TRUE，P2 是 where 过滤条件，缺失也认为是 TRUE，该语句的执行逻辑可以描述为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

FOR each row lt in LT {// 遍历左表的每一行
  BOOL b = FALSE;
  FOR each row rt in RT such that P1(lt, rt) {// 遍历右表每一行，找到满足join条件的行
    IF P2(lt, rt) {//满足 where 过滤条件
      t:=lt||rt;//合并行，输出该行
    }
    b=TRUE;// lt在RT中有对应的行
  }
  IF (!b) { // 遍历完RT，发现lt在RT中没有有对应的行，则尝试用null补一行
    IF P2(lt,NULL) {// 补上null后满足 where 过滤条件
      t:=lt||NULL; // 输出lt和null补上的行
    }
  }
}

当然，实际情况中 MySQL 会使用 buffer 的方式进行优化，减少行比较次数，不过这不影响关键的执行流程，不在本文讨论范围之内。

从这个伪代码中，我们可以看出两点：

• 如果想对右表进行限制，则一定要在 on 条件中进行，若在 where 中进行则可能导致数据缺失，导致左表在右表中无匹配行的行在最终结果中不出现，违背了我们对 left join 的理解。因为对左表无右表匹配行的行而言，遍历右表后 b=FALSE,所以会尝试用 NULL 补齐右表，但是此时我们的 P2 对右表行进行了限制，NULL 若不满足 P2(NULL 一般都不会满足限制条件，除非 IS NULL 这种)，则不会加入最终的结果中，导致结果缺失。
• 如果没有 where 条件，无论 on 条件对左表进行怎样的限制，左表的每一行都至少会有一行的合成结果，对左表行而言，若右表若没有对应的行，则右表遍历结束后 b=FALSE，会用一行 NULL 来生成数据，而这个数据是多余的。所以对左表进行过滤必须用 where。

下面展开两个需求的错误语句的执行结果和错误原因：

需求 1

需求 2

需求 1 由于在 where 条件中对右表限制，导致数据缺失（四班应该有个为 0 的结果）

需求 2 由于在 on 条件中对左表限制，导致数据多余（其他班的结果也出来了，还是错的）

3. 总结

通过上面的问题现象和分析，可以得出了结论：在 left join 语句中，左表过滤必须放 where 条件中，右表过滤必须放 on 条件中，这样结果才能不多不少，刚刚好。

SQL 看似简单，其实也有很多细节原理在里面，一个小小的混淆就会造成结果与预期不符，所以平时要注意这些细节原理，避免关键时候出错。

原文地址：https://www.bilibili.com/video/av76592342

1. 确定一件要做的、对你和周围的人都有益的事情

2. 制定做成这件事的计划

3. 把计划分解为可以着手的小计划

4. 对自己有充分了解 （一次工作多次时间会感到疲惫，一天能做到几次这样的工作）

LeetCode 215 数组中的第 K 个最大元素

题目地址：数组中的第K个最大元素

题解地址：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/solution/shu-zu-zhong-de-di-kge-zui-da-yuan-su-by-leetcode/

总结：

1. 排序
2. 堆
   • 时间复杂度 : *O(Nlog*k)**。
   • 空间复杂度 : **O(k)**，用于存储堆元素
3. 快速选择
   • 时间复杂度 : 平均情况 *O(N)*，最坏情况 *O(N^2)*。
   • 空间复杂度 : *O(1)*。

方法零：排序

最朴素的方法是先对数组进行排序，再返回倒数第 k 个元素，就像 Python 中 sorted(nums)[-k]。

算法的时间复杂度为 *O(NlogN)*，空间复杂度为 *O(1)*。这个时间复杂度并不令人满意，让我们试着用额外空间来优化时间复杂度。

方法一：堆

思路是创建一个小顶堆，将所有数组中的元素加入堆中，并保持堆的大小小于等于 k。这样，堆中就保留了前 k 个最大的元素。这样，堆顶的元素就是正确答案。

像大小为 k 的堆中添加元素的时间复杂度为 *O(logk)*，我们将重复该操作 N 次，故总时间复杂度为 *O(Nlogk)*。

在 Python 的 heapq 库中有一个 nlargest 方法，具有同样的时间复杂度，能将代码简化到只有一行。

本方法优化了时间复杂度，但需要 O(k) 的空间复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // init heap 'the smallest element first'
        PriorityQueue<Integer> heap =
            new PriorityQueue<Integer>((n1, n2) -> n1 - n2);

        // keep k largest elements in the heap
        for (int n: nums) {
          heap.add(n);
          if (heap.size() > k)
            heap.poll();
        }

        // output
        return heap.poll();        
  }
}

复杂度分析

• 时间复杂度 : *O(Nlogk)*。
• 空间复杂度 : *O(k)*，用于存储堆元素。

方法二：快速选择

快速选择算法 的平均时间复杂度为 O(N)。就像快速排序那样，本算法也是 Tony Hoare 发明的，因此也被称为 Hoare选择算法。

本方法大致上与快速排序相同。简便起见，注意到第 k 个最大元素也就是第 N - k 个最小元素，因此可以用第 k 小算法来解决本问题。

首先，我们选择一个枢轴，并在线性时间内定义其在排序数组中的位置。这可以通过 划分算法 的帮助来完成。

为了实现划分，沿着数组移动，将每个元素与枢轴进行比较，并将小于枢轴的所有元素移动到枢轴的左侧。

这样，在输出的数组中，枢轴达到其合适位置。所有小于枢轴的元素都在其左侧，所有大于或等于的元素都在其右侧。

这样，数组就被分成了两部分。如果是快速排序算法，会在这里递归地对两部分进行快速排序，时间复杂度为 *O(N logN)*。

而在这里，由于知道要找的第 N - k 小的元素在哪部分中，我们不需要对两部分都做处理，这样就将平均时间复杂度下降到 *O(N)*。

最终的算法十分直接了当 :

• 随机选择一个枢轴。
• 使用划分算法将枢轴放在数组中的合适位置 pos。将小于枢轴的元素移到左边，大于等于枢轴的元素移到右边。
• 比较 pos 和 N - k 以决定在哪边继续递归处理。

! 注意，本算法也适用于有重复的数组

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

public int quickselect(int left, int right, int k_smallest) {
    /*
    Returns the k-th smallest element of list within left..right.
    */

    if (left == right) // If the list contains only one element,
      return this.nums[left];  // return that element

    // select a random pivot_index
    Random random_num = new Random();
    int pivot_index = left + random_num.nextInt(right - left); 
    
    pivot_index = partition(left, right, pivot_index);

    // the pivot is on (N - k)th smallest position
    if (k_smallest == pivot_index)
      return this.nums[k_smallest];
    // go left side
    else if (k_smallest < pivot_index)
      return quickselect(left, pivot_index - 1, k_smallest);
    // go right side
    return quickselect(pivot_index + 1, right, k_smallest);
  }

  public int findKthLargest(int[] nums, int k) {
    this.nums = nums;
    int size = nums.length;
    // kth largest is (N - k)th smallest
    return quickselect(0, size - 1, size - k);
  }
}

复杂度分析

• 时间复杂度 : 平均情况 *O(N)*，最坏情况 *O(N^2)*。
• 空间复杂度 : *O(1)*。

反转单链表

本文作者：@Ryan Miao

本文链接：https://www.cnblogs.com/woshimrf/p/jvm-garbage.html

1. 垃圾收集算法

1.1 标记-清除算法

最基础的收集算法是“标记-清除”(Mark-Sweep)算法，分两个阶段：首先标记出所有需要回收的对象，在标记完成后统一回收所有被标记的对象。

不足：一个是效率问题，标记和清除两个过程的效率都不高；另一个是空间问题，标记清除之后会产生大量不连续的内存碎片，空间碎片太多可能导致以后在程序运行过程需要分配较大对象时，无法找到足够的连续内存而不得不提前触发另一个的垃圾收集动作。

1.2 复制算法

为了解决效率问题，一种称为复制(Copying)的收集算法出现了，它将可用内存按容量划分为大小相等的两块，每次只使用其中的一块。当这一块内存用完了，就将还存活着的对象复制到另外一块上，然后再把已经使用过的内存空间一次清理掉。这样使得每次都是对整个半区进行内存回收，内存分配时也就不用考虑内存碎片等复杂情况，只要移动堆顶指针，按顺序分配内存即可，实现简单，运行高效。代价是内存缩小为原来的一半。

商业虚拟机用这个回收算法来回收新生代。IBM 研究表明 98%的对象是“朝生夕死“，不需要按照 1-1 的比例来划分内存空间，而是将内存分为一块较大的”Eden“空间和两块较小的 Survivor 空间，每次使用 Eden 和其中一块 Survivor。当回收时，将 Eden 和 Survivor 中还存活的对象一次性复制到另外一个 Survivor 空间上，最后清理掉 Eden 和刚才用过的 Survivor 空间。Hotspot 虚拟机默认 Eden 和 Survivor 的比例是 8-1.即每次可用整个新生代的 90%, 只有一个 survivor，即 1/10 被”浪费“。当然，98%的对象回收只是一般场景下的数据，我们没有办法保证每次回收都只有不多于 10%的对象存活，当 Survivor 空间不够时，需要依赖其他内存(老年代)进行分配担保(Handle Promotion).

如果另外一块 survivor 空间没有足够空间存放上一次新生代收集下来的存活对象时，这些对象将直接通过分配担保机制进入老年代。

1.3 eden survivor 复制过程概述

Eden Space 字面意思是伊甸园，对象被创建的时候首先放到这个区域，进行垃圾回收后，不能被回收的对象被放入到空的 survivor 区域。

Survivor Space 幸存者区，用于保存在 eden space 内存区域中经过垃圾回收后没有被回收的对象。Survivor 有两个，分别为 To Survivor、 From Survivor，这个两个区域的空间大小是一样的。执行垃圾回收的时候 Eden 区域不能被回收的对象被放入到空的 survivor（也就是 To Survivor，同时 Eden 区域的内存会在垃圾回收的过程中全部释放），另一个 survivor（即 From Survivor）里不能被回收的对象也会被放入这个 survivor（即 To Survivor），然后 To Survivor 和 From Survivor 的标记会互换，始终保证一个 survivor 是空的。

为啥需要两个 survivor？因为需要一个完整的空间来复制过来。当满的时候晋升。每次都往标记为 to 的里面放，然后互换，这时 from 已经被清空，可以当作 to 了。

1.4 标记-整理算法

复制收集算法在对象成活率较高时就要进行较多的复制操作，效率将会变低。更关键的是，如果不想浪费 50%的空间，就需要有额外的空间进行分配担保，以应对被使用的内存中所有对象都 100%存活的极端情况，所以，老年代一般不能直接选用这种算法。

根据老年代的特点，有人提出一种”标记-整理“Mark-Compact 算法，标记过程仍然和标记-清除一样，但后续步骤不是直接对可回收对象进行清理，而是让所有存活的对象都向一端移动，然后直接清理端边界以外的内存.

1.5 分代收集算法

当前商业虚拟机的垃圾收集都采用”分代收集“(Generational Collection)算法，这种算法根据对象存活周期的不同将内存划分为几块。一般把 Java 堆分为新生代和老年代，这样就可以根据各个年代的特点采用最适当的收集算法。在新生代，每次垃圾收集时都发现大批对象死去，只有少量存活，那就选用复制算法，只需要付出少量存活对象的复制成本就可以完成收集。而老年代中因为对象存活率较高，没有额外的空间对它进行分配担保，就必须使用”标记-清理“和”标记-整理“算法来进行回收。

2. HotSpot 算法实现

在 Java 语言中，可作为 GC Roots 的对象包括下面几种：

• 虚拟机栈(栈帧中的本地变量表)中引用的对象
• 方法去中类静态属性引用的对象
• 方法区中常量引用的对象
• 本地方法栈中 JNI(即一般说的 Native 方法)引用的对象

从可达性分析中从 GC Roots 节点找引用链这个操作为例，可作为 GC Roots 的节点主要在全局性的引用(例如常量或类静态属性)与执行上下文(例如栈帧中的本地变量表)中，现在很多应用仅仅方法区就有数百兆，如果要逐个检查里面的引用，必然消耗很多时间。

可达性分析对执行时间的敏感还体现在 GC 停顿上，因为这项分析工作必须在一个能确保一致性的快照中进行–这里”一致性“的意思是指整个分析期间整个执行系统看起来就像被冻结在某个时间点，不可以出现分析过程中对象引用关系还在不断变化的情况，该点不满足的话分析结果准确性就无法得到保证。这点是导致 GC 进行时必须停顿所有 Java 执行线程(Sun 公司将这件事情称为”Stop The World“)的一个重要原因，即使是在号称(几乎)不会发生停顿的 CMS 收集器中，枚举根节点时也必须停顿的。

安全点，Safepoint

3. 垃圾收集器

3.1 Serial 收集器

标记-复制。

单线程，一个 CPU 或一条收集线程去完成垃圾收集工作，收集时必须暂停其他所有的工作线程，直到它结束。

虽然如此，它依然是虚拟机运行在 Client 模式下的默认新生代收集器。简单而高效。

3.2 ParNew 收集器

ParNew 是 Serial 收集器的多线程版本。Server 模式下默认新生代收集器，除了 Serial 收集器之外，只有它能与 CMS 收集器配合工作。

3.3 并行 Parallel

指多条垃圾收集线程并行工作，但此时用户线程仍然处于等待状态。

3.4 并发 Concurrent

指用户线程与垃圾收集线程同时执行(但不一定是并行的，可能会交替执行)，用户程序再继续运行，而垃圾收集程序运行于另一个 CPU 上。

3.5 Parallel Scavenge 收集器

Parallel Scavenge 收集器是一个新生代收集器，它也是使用复制算法的收集器。看上去来 ParNew 一样，有什么特别？

Parallel Scavenge 收集器的特点是它的关注点与其他收集器不同，CMS 等收集器关注点是尽可能缩短垃圾收集时用户线程的停顿时间。而 Parallel Scavenge 收集器的目标则是达到一个可控制的吞吐量(Throughput)。所谓吞吐量就是 CPU 用于运行用户代码的时间和 CPU 总小号时间的比值，即吞吐量 = 运行用户代码时间 / (运行用户代码时间+垃圾收集时间)，虚拟机总共运行了 100min，其中垃圾收集花费了 1min，那吞吐量就是 99%.

停顿时间越短就越适合需要与用户交互的程序，良好的响应速度能提升用户体验，而高吞吐量则可以高效地利用 CPU 时间，主要适合在后台运算而不需要太多交互的任务。

Parallel Scavenge 收集器提供了两个参数用于精确控制吞吐量，分别是控制最大垃圾收集停顿时间 -XX:MaxGCPauseMillis以及直接设置吞吐量大小的-XX:GCTimeRatio。

3.6 Serial Old 收集器

Serial Old 是 Serial 收集器的老年代版本，它同样是一个单线程收集器。给 Client 模式下的虚拟机使用。

新生代采用复制算法，暂停所有用户线程；

老年代采用标记-整理算法，暂停所有用户线程；

3.7 Parallel Old 收集器

这里注意，Parallel Scavage 收集器架构中本身有 PS MarkSweep 收集器来收集老年代，并非直接使用了 Serial Old,但二者接近。本人 win10 64 位系统，jdk1.8.0_102，测试默认垃圾收集器为：PS MarkSweep 和 PS Scavenge。 也就是说 Java8 的默认并不是 G1。

这是”吞吐量优先“，注重吞吐量以及 CPU 资源敏感的场合都可以优先考虑 Parallel Scavenge 和 Parallel Old(PS Mark Sweep)。Java8 默认就是这个。

3.8 CMS 收集器

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

CMS 基于 标记-清除算法实现。整个过程分为 4 个步骤：

1. 初始标记(CMS initial mark) -stop the world
2. 并发标记(CMS concurrent mark)
3. 重新标记(CMS remark) -stop the world
4. 并发清除(CMS concurrent sweep)

初始标记，重新标记这两个步骤仍然需要 Stop The World, 初始标记仅仅标记以下 GC Roots 能直接关联的对象，速度很快。

并发标记就是进行 GC Roots Tracing 的过程；

而重新标记阶段则是为了修正并发标记期间因为用户程序继续运作而导致标记产生变动的那一部分对象的标记记录。这个阶段停顿比初始标记稍微长，但远比并发标记的时间短。

整个过程耗时最长的并发标记和并发清除过程，收集器都可以与用户线程一起工作。总体上来说，CMS 收集器的内存回收过程与用户线程一起并发执行的。

CMS 特点：并发收集，低停顿。

缺点

1. CMS 收集器对 CPU 资源非常敏感。默认启动的回收线程数是(CPU+3)/4. 当 CPU 4 个以上时，并发回收垃圾收集线程不少于 25%的 CPU 资源。

2. CMS 收集器无法处理浮动垃圾(Floating Garbage), 可能出现”Concurrent Mode Failure“失败而导致另一次 Full GC 的产生。由于 CMS 并发清理时，用户线程还在运行，伴随产生新垃圾，而这一部分出现在标记之后，只能下次 GC 时再清理。这一部分垃圾就称为”浮动垃圾“。

   由于 CMS 运行时还需要给用户空间继续运行，则不能等老年代几乎被填满再进行收集，需要预留一部分空间提供并发收集时，用户程序运行。JDK1.6 中，CMS 启动阈值为 92%. 若预留内存不够用户使用，则出现一次Concurent Mode Failure失败。这时虚拟机启动后备预案，临时启用 Serial Old 收集老年代，这样停顿时间很长。

3. CMS 基于”标记-清除“算法实现的，则会产生大量空间碎片，空间碎片过多时，没有连续空间分配给大对象，不得不提前触发一次 FUll GC。当然可以开启-XX:+UseCMSCompactAtFullCollection(默认开)，在 CMS 顶不住要 FullGC 时开启内存碎片合并整理过程。内存整理过程是无法并发的，空间碎片问题没了，但停顿时间变长。

面试题：CMS 一共会有几次 STW

首先，回答两次，初始标记和重新标记需要。

然后，CMS 并发的代价是预留空间给用户，预留不足的时候触发 FUllGC，这时 Serail Old 会 STW.

然后，CMS 是标记-清除算法，导致空间碎片，则没有连续空间分配大对象时，FUllGC, 而 FUllGC 会开始碎片整理， STW.

即 2 次或多次。

4. CMS 什么时候 FUll GC

除直接调用 System.gc 外，触发 Full GC 执行的情况有如下四种。

4.1 旧生代空间不足

旧生代空间只有在新生代对象转入及创建为大对象、大数组时才会出现不足的现象，当执行 Full GC 后空间仍然不足，则抛出如下错误： java.lang.OutOfMemoryError: Java heap space 为避免以上两种状况引起的 FullGC，调优时应尽量做到让对象在 Minor GC 阶段被回收、让对象在新生代多存活一段时间及不要创建过大的对象及数组。

4.2 Permanet Generation 空间满

PermanetGeneration 中存放的为一些 class 的信息等，当系统中要加载的类、反射的类和调用的方法较多时，Permanet Generation 可能会被占满，在未配置为采用 CMS GC 的情况下会执行 Full GC。如果经过 Full GC 仍然回收不了，那么 JVM 会抛出如下错误信息： java.lang.OutOfMemoryError: PermGen space 为避免 Perm Gen 占满造成 Full GC 现象，可采用的方法为增大 Perm Gen 空间或转为使用 CMS GC。

4.3 CMS GC 时出现 promotion failed 和 concurrent mode failure

对于采用 CMS 进行旧生代 GC 的程序而言，尤其要注意 GC 日志中是否有 promotion failed 和 concurrent mode failure 两种状况，当这两种状况出现时可能会触发 Full GC。 promotionfailed 是在进行 Minor GC 时，survivor space 放不下、对象只能放入旧生代，而此时旧生代也放不下造成的；concurrent mode failure 是在执行 CMS GC 的过程中同时有对象要放入旧生代，而此时旧生代空间不足造成的。 应对措施为：增大 survivorspace、旧生代空间或调低触发并发 GC 的比率，但在 JDK 5.0+、6.0+的版本中有可能会由于 JDK 的 bug29 导致 CMS 在 remark 完毕后很久才触发 sweeping 动作。对于这种状况，可通过设置-XX:CMSMaxAbortablePrecleanTime=5（单位为 ms）来避免。

4.4 统计得到的 Minor GC 晋升到旧生代的平均大小大于旧生代的剩余空间

这是一个较为复杂的触发情况，Hotspot 为了避免由于新生代对象晋升到旧生代导致旧生代空间不足的现象，在进行 Minor GC 时，做了一个判断，如果之前统计所得到的 Minor GC 晋升到旧生代的平均大小大于旧生代的剩余空间，那么就直接触发 Full GC。 例如程序第一次触发 MinorGC 后，有 6MB 的对象晋升到旧生代，那么当下一次 Minor GC 发生时，首先检查旧生代的剩余空间是否大于 6MB，如果小于 6MB，则执行 Full GC。 当新生代采用 PSGC 时，方式稍有不同，PS GC 是在 Minor GC 后也会检查，例如上面的例子中第一次 Minor GC 后，PS GC 会检查此时旧生代的剩余空间是否大于 6MB，如小于，则触发对旧生代的回收。 除了以上 4 种状况外，对于使用 RMI 来进行 RPC 或管理的 Sun JDK 应用而言，默认情况下会一小时执行一次 Full GC。可通过在启动时通过- java-Dsun.rmi.dgc.client.gcInterval=3600000 来设置 Full GC 执行的间隔时间或通过-XX:+ DisableExplicitGC 来禁止 RMI 调用 System.gc。

5. G1

5.1 什么是垃圾回收

首先，在了解 G1 之前，我们需要清楚的知道，垃圾回收是什么？简单的说垃圾回收就是回收内存中不再使用的对象。

垃圾回收的基本步骤

回收的步骤有 2 步：

1. 查找内存中不再使用的对象

2. 释放这些对象占用的内存

5.1.1 查找内存中不再使用的对象

那么问题来了，如何判断哪些对象不再被使用呢？我们也有 2 个方法：

1. 引用计数法 引用计数法就是如果一个对象没有被任何引用指向，则可视之为垃圾。这种方法的缺点就是不能检测到环的存在。

2. 根搜索算法

根搜索算法的基本思路就是通过一系列名为”GC Roots”的对象作为起始点，从这些节点开始向下搜索，搜索所走过的路径称为引用链(Reference Chain)，当一个对象到 GC Roots 没有任何引用链相连时，则证明此对象是不可用的。

现在我们已经知道如何找出垃圾对象了，如何把这些对象清理掉呢？

5.1.2 释放这些对象占用的内存

常见的方式有复制或者直接清理，但是直接清理会存在内存碎片，于是就会产生了清理再压缩的方式。

总得来说就产生了三种类型的回收算法。

1. 标记-复制

2. 标记-清理

3. 标记-整理

基于分代的假设

由于对象的存活时间有长有短，所以对于存活时间长的对象，减少被 gc 的次数可以避免不必要的开销。这样我们就把内存分成新生代和老年代，新生代存放刚创建的和存活时间比较短的对象，老年代存放存活时间比较长的对象。这样每次仅仅清理年轻代，老年代仅在必要时时再做清理可以极大的提高 GC 效率，节省 GC 时间。

5.2 Java 垃圾收集器的历史

第一阶段，Serial（串行）收集器

在 jdk1.3.1 之前，java 虚拟机仅仅能使用 Serial 收集器。 Serial 收集器是一个单线程的收集器，但它的“单线程”的意义并不仅仅是说明它只会使用一个 CPU 或一条收集线程去完成垃圾收集工作，更重要的是在它进行垃圾收集时，必须暂停其他所有的工作线程，直到它收集结束。

PS：开启 Serial 收集器的方式

1

-XX:+UseSerialGC

第二阶段，Parallel（并行）收集器

Parallel 收集器也称吞吐量收集器，相比 Serial 收集器，Parallel 最主要的优势在于使用多线程去完成垃圾清理工作，这样可以充分利用多核的特性，大幅降低 gc 时间。

PS:开启 Parallel 收集器的方式

1

-XX:+UseParallelGC -XX:+UseParallelOldGC

第三阶段，CMS（并发）收集器

CMS 收集器在 Minor GC 时会暂停所有的应用线程，并以多线程的方式进行垃圾回收。在 Full GC 时不再暂停应用线程，而是使用若干个后台线程定期的对老年代空间进行扫描，及时回收其中不再使用的对象。

PS:开启 CMS 收集器的方式

1

-XX:+UseParNewGC -XX:+UseConcMarkSweepGC

第四阶段，G1（并发）收集器

G1 收集器（或者垃圾优先收集器）的设计初衷是为了尽量缩短处理超大堆（大于 4GB）时产生的停顿。相对于 CMS 的优势而言是内存碎片的产生率大大降低。

PS:开启 G1 收集器的方式

1

-XX:+UseG1GC

5.3 了解 G1

G1 的第一篇 paper（附录 1）发表于 2004 年，在 2012 年才在 jdk1.7u4 中可用。oracle 官方计划在 jdk9 中将 G1 变成默认的垃圾收集器，以替代 CMS。为何 oracle 要极力推荐 G1 呢，G1 有哪些优点

首先，G1 的设计原则就是简单可行的性能调优

开发人员仅仅需要声明以下参数即可：

1

-XX:+UseG1GC -Xmx32g -XX:MaxGCPauseMillis=200

其中-XX:+UseG1GC 为开启 G1 垃圾收集器，-Xmx32g 设计堆内存的最大内存为 32G，-XX:MaxGCPauseMillis=200 设置 GC 的最大暂停时间为 200ms。如果我们需要调优，在内存大小一定的情况下，我们只需要修改最大暂停时间即可。

其次，G1 将新生代，老年代的物理空间划分取消了。

这样我们再也不用单独的空间对每个代进行设置了，不用担心每个代内存是否足够。

取而代之的是，G1 算法将堆划分为若干个区域（Region），它仍然属于分代收集器。不过，这些区域的一部分包含新生代，新生代的垃圾收集依然采用暂停所有应用线程的方式，将存活对象拷贝到老年代或者 Survivor 空间。老年代也分成很多区域，G1 收集器通过将对象从一个区域复制到另外一个区域，完成了清理工作。这就意味着，在正常的处理过程中，G1 完成了堆的压缩（至少是部分堆的压缩），这样也就不会有 cms 内存碎片问题的存在了。

在 G1 中，还有一种特殊的区域，叫 Humongous 区域。 如果一个对象占用的空间超过了分区容量 50%以上，G1 收集器就认为这是一个巨型对象。这些巨型对象，默认直接会被分配在年老代，但是如果它是一个短期存在的巨型对象，就会对垃圾收集器造成负面影响。为了解决这个问题，G1 划分了一个 Humongous 区，它用来专门存放巨型对象。如果一个 H 区装不下一个巨型对象，那么 G1 会寻找连续的 H 分区来存储。为了能找到连续的 H 区，有时候不得不启动 Full GC。

PS：在 java 8 中，持久代也移动到了普通的堆内存空间中，改为元空间。

5.4 对象分配策略

说起大对象的分配，我们不得不谈谈对象的分配策略。它分为 3 个阶段：

1. TLAB(Thread Local Allocation Buffer)线程本地分配缓冲区

2. Eden 区中分配

3. Humongous 区分配

TLAB 为线程本地分配缓冲区，它的目的为了使对象尽可能快的分配出来。如果对象在一个共享的空间中分配，我们需要采用一些同步机制来管理这些空间内的空闲空间指针。在 Eden 空间中，每一个线程都有一个固定的分区用于分配对象，即一个 TLAB。分配对象时，线程之间不再需要进行任何的同步。

对 TLAB 空间中无法分配的对象，JVM 会尝试在 Eden 空间中进行分配。如果 Eden 空间无法容纳该对象，就只能在老年代中进行分配空间。

最后，G1 提供了两种 GC 模式，Young GC 和 Mixed GC，两种都是 Stop The World(STW)的。下面我们将分别介绍一下这 2 种模式。

5.5 G1 Young GC

Young GC 主要是对 Eden 区进行 GC，它在 Eden 空间耗尽时会被触发。在这种情况下，Eden 空间的数据移动到 Survivor 空间中，如果 Survivor 空间不够，Eden 空间的部分数据会直接晋升到年老代空间。Survivor 区的数据移动到新的 Survivor 区中，也有部分数据晋升到老年代空间中。最终 Eden 空间的数据为空，GC 停止工作，应用线程继续执行。

这时，我们需要考虑一个问题，如果仅仅 GC 新生代对象，我们如何找到所有的根对象呢？ 老年代的所有对象都是根么？那这样扫描下来会耗费大量的时间。于是，G1 引进了 RSet 的概念。它的全称是 Remembered Set，作用是跟踪指向某个 heap 区内的对象引用。

在 CMS 中，也有 RSet 的概念，在老年代中有一块区域用来记录指向新生代的引用。这是一种 point-out，在进行 Young GC 时，扫描根时，仅仅需要扫描这一块区域，而不需要扫描整个老年代。

但在 G1 中，并没有使用 point-out，这是由于一个分区太小，分区数量太多，如果使用 point-out 的话，会造成大量的扫描浪费，有些根本不需要 GC 的分区引用也扫描了。于是 G1 中使用 point-in 来解决。point-in 的意思是哪些分区引用了当前分区中的对象。这样，仅仅将这些对象当做根来扫描就避免了无效的扫描。由于新生代有多个，那么我们需要在新生代之间记录引用吗？这是不必要的，原因在于每次 GC 时，所有新生代都会被扫描，所以只需要记录老年代到新生代之间的引用即可。

需要注意的是，如果引用的对象很多，赋值器需要对每个引用做处理，赋值器开销会很大，为了解决赋值器开销这个问题，在 G1 中又引入了另外一个概念，卡表（Card Table）。一个 Card Table 将一个分区在逻辑上划分为固定大小的连续区域，每个区域称之为卡。卡通常较小，介于 128 到 512 字节之间。Card Table 通常为字节数组，由 Card 的索引（即数组下标）来标识每个分区的空间地址。默认情况下，每个卡都未被引用。当一个地址空间被引用时，这个地址空间对应的数组索引的值被标记为”0″，即被标记为脏引用，此外 RSet 也将这个数组下标记录下来。一般情况下，这个 RSet 其实是一个 Hash Table，Key 是别的 Region 的起始地址，Value 是一个集合，里面的元素是 Card Table 的 Index。

Young GC 阶段：

阶段 1：根扫描

静态和本地对象被扫描

阶段 2：更新 RS

处理 dirty card 队列更新 RS

阶段 3：处理 RS

检测从年轻代指向年老代的对象

阶段 4：对象拷贝

拷贝存活的对象到 survivor/old 区域

阶段 5：处理引用队列

软引用，弱引用，虚引用处理

5.6 G1 Mix GC

Mix GC 不仅进行正常的新生代垃圾收集，同时也回收部分后台扫描线程标记的老年代分区。

它的 GC 步骤分 2 步：

1. 全局并发标记（global concurrent marking）
2. 拷贝存活对象（evacuation）

在进行 Mix GC 之前，会先进行 global concurrent marking（全局并发标记）。 global concurrent marking 的执行过程是怎样的呢？

在 G1 GC 中，它主要是为 Mixed GC 提供标记服务的，并不是一次 GC 过程的一个必须环节。global concurrent marking 的执行过程分为五个步骤：

初始标记（initial mark，STW）

在此阶段，G1 GC 对根进行标记。该阶段与常规的 (STW) 年轻代垃圾回收密切相关。

根区域扫描（root region scan

G1 GC 在初始标记的存活区扫描对老年代的引用，并标记被引用的对象。该阶段与应用程序（非 STW）同时运行，并且只有完成该阶段后，才能开始下一次 STW 年轻代垃圾回收。

并发标记（Concurrent Marking）

G1 GC 在整个堆中查找可访问的（存活的）对象。该阶段与应用程序同时运行，可以被 STW 年轻代垃圾回收中断

最终标记（Remark，STW）

该阶段是 STW 回收，帮助完成标记周期。G1 GC 清空 SATB 缓冲区，跟踪未被访问的存活对象，并执行引用处理。

清除垃圾（Cleanup，STW）

在这个最后阶段，G1 GC 执行统计和 RSet 净化的 STW 操作。在统计期间，G1 GC 会识别完全空闲的区域和可供进行混合垃圾回收的区域。清理阶段在将空白区域重置并返回到空闲列表时为部分并发。

5.7 三色标记算法

提到并发标记，我们不得不了解并发标记的三色标记算法。它是描述追踪式回收器的一种有用的方法，利用它可以推演回收器的正确性。 首先，我们将对象分成三种类型的。

黑色:根对象，或者该对象与它的子对象都被扫描

灰色:对象本身被扫描,但还没扫描完该对象中的子对象

白色:未被扫描对象，扫描完成所有对象之后，最终为白色的为不可达对象，即垃圾对象

当 GC 开始扫描对象时，按照如下图步骤进行对象的扫描：

根对象被置为黑色，子对象被置为灰色。

继续由灰色遍历,将已扫描了子对象的对象置为黑色。

遍历了所有可达的对象后，所有可达的对象都变成了黑色。不可达的对象即为白色，需要被清理。

这看起来很美好，但是如果在标记过程中，应用程序也在运行，那么对象的指针就有可能改变。这样的话，我们就会遇到一个问题：对象丢失问题

我们看下面一种情况，当垃圾收集器扫描到下面情况时:

这时候应用程序执行了以下操作：

1
2

A.c=C
B.c=null

这样，对象的状态图变成如下情形：

这时候垃圾收集器再标记扫描的时候就会下图成这样：

很显然，此时 C 是白色，被认为是垃圾需要清理掉，显然这是不合理的。那么我们如何保证应用程序在运行的时候，GC 标记的对象不丢失呢？有如下 2 种可行的方式：

1. 在插入的时候记录对象

2. 在删除的时候记录对象

刚好这对应 CMS 和 G1 的 2 种不同实现方式：

在 CMS 采用的是增量更新（Incremental update），只要在写屏障（write barrier）里发现要有一个白对象的引用被赋值到一个黑对象 的字段里，那就把这个白对象变成灰色的。即插入的时候记录下来。

在 G1 中，使用的是 STAB（snapshot-at-the-beginning）的方式，删除的时候记录所有的对象，它有 3 个步骤：

1. 在开始标记的时候生成一个快照图标记存活对象

2. 在并发标记的时候所有被改变的对象入队（在 write barrier 里把所有旧的引用所指向的对象都变成非白的）

3. 可能存在游离的垃圾，将在下次被收集

这样，G1 到现在可以知道哪些老的分区可回收垃圾最多。 当全局并发标记完成后，在某个时刻，就开始了 Mix GC。这些垃圾回收被称作“混合式”是因为他们不仅仅进行正常的新生代垃圾收集，同时也回收部分后台扫描线程标记的分区。混合式垃圾收集如下图：

混合式 GC 也是采用的复制的清理策略，当 GC 完成后，会重新释放空间。

5.8 调优实践

MaxGCPauseMillis调优

前面介绍过使用 GC 的最基本的参数：

1

-XX:+UseG1GC -Xmx32g -XX:MaxGCPauseMillis=200

前面 2 个参数都好理解，后面这个 MaxGCPauseMillis 参数该怎么配置呢？这个参数从字面的意思上看，就是允许的 GC 最大的暂停时间。G1 尽量确保每次 GC 暂停的时间都在设置的 MaxGCPauseMillis 范围内。 那 G1 是如何做到最大暂停时间的呢？这涉及到另一个概念，CSet(collection set)。它的意思是在一次垃圾收集器中被收集的区域集合。

Young GC：选定所有新生代里的 region。通过控制新生代的 region 个数来控制 young GC 的开销。

Mixed GC：选定所有新生代里的 region，外加根据 global concurrent marking 统计得出收集收益高的若干老年代 region。在用户指定的开销目标范围内尽可能选择收益高的老年代 region。

在理解了这些后，我们再设置最大暂停时间就好办了。 首先，我们能容忍的最大暂停时间是有一个限度的，我们需要在这个限度范围内设置。但是应该设置的值是多少呢？我们需要在吞吐量跟 MaxGCPauseMillis 之间做一个平衡。如果 MaxGCPauseMillis 设置的过小，那么 GC 就会频繁，吞吐量就会下降。如果 MaxGCPauseMillis 设置的过大，应用程序暂停时间就会变长。G1 的默认暂停时间是 200 毫秒，我们可以从这里入手，调整合适的时间。

其他调优参数

1

-XX:G1HeapRegionSize=n

设置的 G1 区域的大小。值是 2 的幂，范围是 1 MB 到 32 MB 之间。目标是根据最小的 Java 堆大小划分出约 2048 个区域。

1

-XX:ParallelGCThreads=n

设置 STW 工作线程数的值。将 n 的值设置为逻辑处理器的数量。n 的值与逻辑处理器的数量相同，最多为 8。

如果逻辑处理器不止八个，则将 n 的值设置为逻辑处理器数的 5/8 左右。这适用于大多数情况，除非是较大的 SPARC 系统，其中 n 的值可以是逻辑处理器数的 5/16 左右。

1

-XX:ConcGCThreads=n

设置并行标记的线程数。将 n 设置为并行垃圾回收线程数 (ParallelGCThreads) 的 1/4 左右。

1
2

-XX:InitiatingHeapOccupancyPercent=45

设置触发标记周期的 Java 堆占用率阈值。默认占用率是整个 Java 堆的 45%。

避免使用以下参数：

避免使用 -Xmn 选项或 -XX:NewRatio 等其他相关选项显式设置年轻代大小。固定年轻代的大小会覆盖暂停时间目标。

5.9 触发 Full GC

在某些情况下，G1 触发了 Full GC，这时 G1 会退化使用 Serial 收集器来完成垃圾的清理工作，它仅仅使用单线程来完成 GC 工作，GC 暂停时间将达到秒级别的。整个应用处于假死状态，不能处理任何请求，我们的程序当然不希望看到这些。那么发生 Full GC 的情况有哪些呢？

5.9.1 并发模式失败

G1 启动标记周期，但在 Mix GC 之前，老年代就被填满，这时候 G1 会放弃标记周期。这种情形下，需要增加堆大小，或者调整周期（例如增加线程数-XX:ConcGCThreads 等）。

5.9.2 晋升失败或者疏散失败

G1 在进行 GC 的时候没有足够的内存供存活对象或晋升对象使用，由此触发了 Full GC。可以在日志中看到(to-space exhausted)或者（to-space overflow）。解决这种问题的方式是：

a. 增加 -XX:G1ReservePercent 选项的值（并相应增加总的堆大小），为“目标空间”增加预留内存量。

b. 通过减少-XX:InitiatingHeapOccupancyPercent 提前启动标记周期。

c. 也可以通过增加 -XX:ConcGCThreads 选项的值来增加并行标记线程的数目。

5.9.3 巨型对象分配失败

当巨型对象找不到合适的空间进行分配时，就会启动 Full GC，来释放空间。这种情况下，应该避免分配大量的巨型对象，增加内存或者增大-XX:G1HeapRegionSize，使巨型对象不再是巨型对象。

6. 参考

• 转载 深入理解 JVM 虚拟机 第三章
• 转载 《深入理解 Java G1 垃圾收集器》

作者：火丁笔记

原文地址：https://blog.huoding.com/2016/01/19/488

总结：

1. CLOSE_WAIT：被动关闭的一方响应 ACK 包后进入的等待关闭状态，直到被动关闭的一方发出 FIN 包后结束。

2. 出现大量的 CLOSE_WAIT 状态的原因：

   • 程序问题

   • 响应太慢或者超时设置过小

   • BACKLOG 太大

TCP 有很多连接状态，每一个都够聊十块钱儿的，比如我们以前讨论过 TIME_WAIT 和 FIN_WAIT1，最近时不时听人提起 CLOSE_WAIT，感觉有必要梳理一下。

所谓 CLOSE_WAIT，借用某位大牛的话来说应该倒过来叫做 WAIT_CLOSE，也就是说「等待关闭」，如果你还不理解其含义，可以看看 TCP 关闭连接时的图例：

不要被图中的 client 和 server 所迷惑，你只要记住：主动关闭的一方发出 FIN 包，被动关闭的一方响应 ACK 包，此时，被动关闭的一方就进入了 CLOSE_WAIT 状态。如果一切正常，稍后被动关闭的一方也会发出 FIN 包，然后迁移到 LAST_ACK 状态。

通常，CLOSE_WAIT 状态在服务器停留时间很短，如果你发现大量的 CLOSE_WAIT 状态，那么就意味着被动关闭的一方没有及时发出 FIN 包，一般有如下几种可能：

• 程序问题：如果代码层面忘记了 close 相应的 socket 连接，那么自然不会发出 FIN 包，从而导致 CLOSE_WAIT 累积；或者代码不严谨，出现死循环之类的问题，导致即便后面写了 close 也永远执行不到。
• 响应太慢或者超时设置过小：如果连接双方不和谐，一方不耐烦直接 timeout，另一方却还在忙于耗时逻辑，就会导致 close 被延后。响应太慢是首要问题，不过换个角度看，也可能是 timeout 设置过小。
• BACKLOG 太大：此处的 backlog 不是 syn backlog，而是 accept 的 backlog，如果 backlog 太大的话，设想突然遭遇大访问量的话，即便响应速度不慢，也可能出现来不及消费的情况，导致多余的请求还在队列里就被对方关闭了。

如果你通过「netstat -ant」或者「ss -ant」命令发现了很多 CLOSE_WAIT 连接，请注意结果中的「Recv-Q」和「Local Address」字段，通常「Recv-Q」会不为空，它表示应用还没来得及接收数据，而「Local Address」表示哪个地址和端口有问题，我们可以通过「lsof -i:」来确认端口对应运行的是什么程序以及它的进程号是多少。

如果是我们自己写的一些程序，比如用 HttpClient 自定义的蜘蛛，那么八九不离十是程序问题，如果是一些使用广泛的程序，比如 Tomcat 之类的，那么更可能是响应速度太慢或者 timeout 设置太小或者 BACKLOG 设置过大导致的故障。

此外还有一点需要说明：按照前面图例所示，当被动关闭的一方处于 CLOSE_WAIT 状态时，主动关闭的一方处于 FIN_WAIT2 状态。 那么为什么我们总听说 CLOSE_WAIT 状态过多的故障，但是却相对少听说 FIN_WAIT2 状态过多的故障呢？这是因为 Linux 有一个「tcp_fin_timeout」设置，控制了 FIN_WAIT2 的最大生命周期。坏消息是 CLOSE_WAIT 没有类似的设置，如果不重启进程，那么 CLOSE_WAIT 状态很可能会永远持续下去；好消息是如果 socket 开启了 keepalive 机制，那么可以通过相应的设置来清理无效连接，不过 keepalive 是治标不治本的方法，还是应该找到问题的症结才对。

本来想多写点的，但是着急回家，就写到这吧，推荐两个案例：

• PHP 升级导致系统负载过高问题分析
• 又见 CLOSE_WAIT

写得都比我好，建议大家仔细阅读。

作者：火丁笔记

原文地址：https://blog.huoding.com/2013/12/31/316

总结：

1. 为什么会存在 TIME_WAIT？

   主动关闭的一方收到被动关闭的一方发出的 FIN 包后，回应 ACK 包，同时进入 TIME_WAIT 状态，但是因为网络原因，主动关闭的一方发送的这个 ACK 包很可能延迟，从而触发被动连接一方重传 FIN 包。极端情况下，这一去一回，就是两倍的 MSL 时长。如果主动关闭的一方跳过 TIME_WAIT 直接进入 CLOSED，或者在 TIME_WAIT 停留的时长不足两倍的 MSL，那么当被动关闭的一方早先发出的延迟包到达后，就可能出现类似下面的问题：

   • 旧的 TCP 连接已经不存在了，系统此时只能返回 RST 包

   • 新的 TCP 连接被建立起来了，延迟包可能干扰新的连接

2. 如何控制 TIME_WAIT 的数量？

   • ip_conntrack：顾名思义就是跟踪连接，不建议使用。
   • tcp_tw_recycle：回收 TIME_WAIT 连接
   • tcp_tw_reuse：顾名思义就是复用 TIME_WAIT 连接。既然我们要复用连接，那么当然应该在连接的发起方使用，而不能在被连接方使用。
   • tcp_max_tw_buckets：顾名思义就是控制 TIME_WAIT 总数。
   • 如果客户端可控的话，那么在服务端打开 KeepAlive，尽可能不让服务端主动关闭连接，而让客户端主动关闭连接，如此一来问题便迎刃而解了。

之所以起这样一个题目是因为很久以前我曾经写过一篇介绍 TIME_WAIT 的文章，不过当时基本属于浅尝辄止，并没深入说明问题的来龙去脉，碰巧这段时间反复被别人问到相关的问题，让我觉得有必要全面总结一下，以备不时之需。

讨论前大家可以拿手头的服务器摸摸底，记住「ss」比「netstat」快：

1
2
3

shell> ss -ant | awk '
    NR>1 {++s[$1]} END {for(k in s) print k,s[k]}
'

如果你只是想单独查询一下 TIME_WAIT 的数量，那么还可以更简单一些：

1

shell> cat /proc/net/sockstat

我猜你一定被巨大无比的 TIME_WAIT 网络连接总数吓到了！以我个人的经验，对于一台繁忙的 Web 服务器来说，如果主要以短连接为主，那么其 TIME_WAIT 网络连接总数很可能会达到几万，甚至十几万。虽然一个 TIME_WAIT 网络连接耗费的资源无非就是一个端口、一点内存，但是架不住基数大，所以这始终是一个需要面对的问题。

1. 为什么会存在 TIME_WAIT？

TCP 在建立连接的时候需要握手，同理，在关闭连接的时候也需要握手。为了更直观的说明关闭连接时握手的过程，我们引用「The TCP/IP Guide」中的例子：

[](https://blog.huoding.com/wp-content/uploads/2013/12/tcp_close.png)

TCP Close

因为 TCP 连接是双向的，所以在关闭连接的时候，两个方向各自都需要关闭。先发 FIN 包的一方执行的是主动关闭；后发 FIN 包的一方执行的是被动关闭。主动关闭的一方会进入 TIME_WAIT 状态，并且在此状态停留两倍的MSL时长。

穿插一点 MSL 的知识：MSL 指的是报文段的最大生存时间，如果报文段在网络活动了 MSL 时间，还没有被接收，那么会被丢弃。关于 MSL 的大小，RFC 793协议中给出的建议是两分钟，不过实际上不同的操作系统可能有不同的设置，以 Linux 为例，通常是半分钟，两倍的 MSL 就是一分钟，也就是 60 秒，并且这个数值是硬编码在内核中的，也就是说除非你重新编译内核，否则没法修改它：

1

#define TCP_TIMEWAIT_LEN (60*HZ)

如果每秒的连接数是一千的话，那么一分钟就可能会产生六万个 TIME_WAIT。

为什么主动关闭的一方不直接进入 CLOSED 状态，而是进入 TIME_WAIT 状态，并且停留两倍的 MSL 时长呢？这是因为 TCP 是建立在不可靠网络上的可靠的协议。例子：主动关闭的一方收到被动关闭的一方发出的 FIN 包后，回应 ACK 包，同时进入 TIME_WAIT 状态，但是因为网络原因，主动关闭的一方发送的这个 ACK 包很可能延迟，从而触发被动连接一方重传 FIN 包。极端情况下，这一去一回，就是两倍的 MSL 时长。如果主动关闭的一方跳过 TIME_WAIT 直接进入 CLOSED，或者在 TIME_WAIT 停留的时长不足两倍的 MSL，那么当被动关闭的一方早先发出的延迟包到达后，就可能出现类似下面的问题：

• 旧的 TCP 连接已经不存在了，系统此时只能返回 RST 包
• 新的 TCP 连接被建立起来了，延迟包可能干扰新的连接

不管是哪种情况都会让 TCP 不再可靠，所以 TIME_WAIT 状态有存在的必要性。

2. 如何控制 TIME_WAIT 的数量？

从前面的描述我们可以得出这样的结论：TIME_WAIT 这东西没有的话不行，不过太多可能也是个麻烦事。下面让我们看看有哪些方法可以控制 TIME_WAIT 数量，这里只说一些常规方法，另外一些诸如 SO_LINGER 之类的方法太过偏门，略过不谈。

ip_conntrack：顾名思义就是跟踪连接。一旦激活了此模块，就能在系统参数里发现很多用来控制网络连接状态超时的设置，其中自然也包括 TIME_WAIT：

1
2

shell> modprobe ip_conntrack
shell> sysctl net.ipv4.netfilter.ip_conntrack_tcp_timeout_time_wait

我们可以尝试缩小它的设置，比如十秒，甚至一秒，具体设置成多少合适取决于网络情况而定，当然也可以参考相关的案例。不过就我的个人意见来说，ip_conntrack 引入的问题比解决的还多，比如性能会大幅下降，所以不建议使用。

tcp_tw_recycle：顾名思义就是回收 TIME_WAIT 连接。可以说这个内核参数已经变成了大众处理 TIME_WAIT 的万金油，如果你在网络上搜索 TIME_WAIT 的解决方案，十有八九会推荐设置它，不过这里隐藏着一个不易察觉的陷阱：

当多个客户端通过 NAT 方式联网并与服务端交互时，服务端看到的是同一个 IP，也就是说对服务端而言这些客户端实际上等同于一个，可惜由于这些客户端的时间戳可能存在差异，于是乎从服务端的视角看，便可能出现时间戳错乱的现象，进而直接导致时间戳小的数据包被丢弃。参考：tcp_tw_recycle 和 tcp_timestamps 导致 connect 失败问题。

tcp_tw_reuse：顾名思义就是复用 TIME_WAIT 连接。当创建新连接的时候，如果可能的话会考虑复用相应的 TIME_WAIT 连接。通常认为「tcp_tw_reuse」比「tcp_tw_recycle」安全一些，这是因为一来 TIME_WAIT 创建时间必须超过一秒才可能会被复用；二来只有连接的时间戳是递增的时候才会被复用。官方文档里是这样说的：如果从协议视角看它是安全的，那么就可以使用。这简直就是外交辞令啊！按我的看法，如果网络比较稳定，比如都是内网连接，那么就可以尝试使用。

不过需要注意的是在哪里使用，既然我们要复用连接，那么当然应该在连接的发起方使用，而不能在被连接方使用。举例来说：客户端向服务端发起 HTTP 请求，服务端响应后主动关闭连接，于是 TIME_WAIT 便留在了服务端，此类情况使用「tcp_tw_reuse」是无效的，因为服务端是被连接方，所以不存在复用连接一说。让我们延伸一点来看，比如说服务端是 PHP，它查询另一个 MySQL 服务端，然后主动断开连接，于是 TIME_WAIT 就落在了 PHP 一侧，此类情况下使用「tcp_tw_reuse」是有效的，因为此时 PHP 相对于 MySQL 而言是客户端，它是连接的发起方，所以可以复用连接。

说明：如果使用 tcp_tw_reuse，请激活 tcp_timestamps，否则无效。

tcp_max_tw_buckets：顾名思义就是控制 TIME_WAIT 总数。官网文档说这个选项只是为了阻止一些简单的 DoS 攻击，平常不要人为的降低它。如果缩小了它，那么系统会将多余的 TIME_WAIT 删除掉，日志里会显示：「TCP: time wait bucket table overflow」。

需要提醒大家的是物极必反，曾经看到有人把「tcp_max_tw_buckets」设置成 0，也就是说完全抛弃 TIME_WAIT，这就有些冒险了，用一句围棋谚语来说：入界宜缓。

…

有时候，如果我们换个角度去看问题，往往能得到四两拨千斤的效果。前面提到的例子：客户端向服务端发起 HTTP 请求，服务端响应后主动关闭连接，于是 TIME_WAIT 便留在了服务端。这里的关键在于主动关闭连接的是服务端！在关闭 TCP 连接的时候，先出手的一方注定逃不开 TIME_WAIT 的宿命，套用一句歌词：把我的悲伤留给自己，你的美丽让你带走。如果客户端可控的话，那么在服务端打开KeepAlive，尽可能不让服务端主动关闭连接，而让客户端主动关闭连接，如此一来问题便迎刃而解了。

参考文档：

1. tcp 短连接 TIME_WAIT 问题解决方法大全（1）——高屋建瓴
2. tcp 短连接 TIME_WAIT 问题解决方法大全（2）——SO_LINGER
3. tcp 短连接 TIME_WAIT 问题解决方法大全（3）——tcp_tw_recycle
4. tcp 短连接 TIME_WAIT 问题解决方法大全（4）——tcp_tw_reuse
5. tcp 短连接 TIME_WAIT 问题解决方法大全（5）——tcp_max_tw_buckets

ARTS是由左耳朵耗子陈皓在极客时间专栏《左耳听风》中发起的一个每周学习打卡计划。

1
2
3
4
5
6
7

Algorithm：至少做一个 LeetCode 的算法题。主要为了编程训练和学习。

Review：阅读并点评至少一篇英文技术文章。主要为了学习英文，如果你英文不行，很难成为技术高手。

Tip：学习至少一个技术技巧。主要是为了总结和归纳你日常工作中所遇到的知识点。

Share：分享一篇有观点和思考的技术文章。主要为了输出你的影响力，能够输出你的价值观。

Algorithm(算法)

Leetcode 26 将数组中的重复元素删除

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/

思路

使用快慢指针

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

package a26_删除排序数组中的重复项;

/**
 * @Description
 * @Author Gao Hang Hang
 * @Date 2019-11-17 19:54
 **/
public class Solution2 {

    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;
        int i = 0;
        for (int j = 1; j < nums.length; j++) {
            /*
                当我们遇到 nums[j] != nums[i] 时，跳过重复项的运行已经结束，
                因此我们必须把它（nums[j]）的值复制到 nums[i+1]。然后递增 i
             */
            if (nums[j] != nums[i]) {
                i++;
                nums[i] = nums[j];
            }
        }
        return i + 1;
    }

}

Review(点评)

Tip(技巧)

原文地址：https://blog.csdn.net/qq_32917699/article/details/81486060

今天做了一天@ApiModel希望Swagger生成的文档出现返回的内容注释，发现需要用到@ApiModel注解到你需要返回的类上

1

@ApiModelProperty作为字段的描述

例如：

之后文档还是不显示返回内容的注释，

原来是因为封装的返回类没做泛型 需要加入泛型

封装的返回类加入泛型之后，还需要在你Controller返回的数据也加上泛型，不然还是展示不出来的

这样，返回的数据就带上注释了

完美解决了返回内容不带注释的问题

Share(分享)

Arrays.sort() VS Arrays.parallelSort()

视频地址：https://www.bilibili.com/video/av75537322

1. 什么是第一原理

第一性原理，又称“第一原理”，是古希腊哲学家亚里士多德提出的一个哲学术语：每个系统中存在一个最基本的命题，它不能被违背或删除。亚里士多德认为，我们要掌握第一原理才能拥有正确知识。从第一原理思考的人，会从果实到树根，由表及里来理解知识，他们会把那些零散的知识，全都形成一个有条理的整体。

亚里士多德认为所有事物都能分为类别和子类别，每个领域最小的子类别就是我们所说的第一原理

2. 第一原理的益处

• 创新：改造它或以不同方式把它们结合形成新的知识
• 优化：思考或实体能通过改造以获得优化
• 融合：当你理解了知识的根本之后，把新知识融入你的知识系统，就简单多了
• 传播：有益于把复杂知识传递给别人

3. 如何成为从第一原理思考的人呢？

构建层次，了解零散的知识是如何相互联系的，Why 和 How，把你感兴趣的学科知识搜集起来，并像写文章那样，将各部分等级化，从而使知识具有系统性

原文地址：https://www.javaboy.org/2019/0418/springboot-schedule-task.html

在 Spring + SpringMVC 环境中，一般来说，要实现定时任务，我们有两种方案，一种是使用 Spring 自带的定时任务处理器 @Scheduled 注解，另一种就是使用第三方框架 Quartz ，Spring Boot 源自 Spring+SpringMVC ，因此天然具备这两个 Spring 中的定时任务实现策略，当然也支持 Quartz，本文我们就来看下 Spring Boot 中两种定时任务的实现方式。

1. @Scheduled

使用 @Scheduled 非常容易，直接创建一个 Spring Boot 项目，并且添加 web 依赖 spring-boot-starter-web，项目创建成功后，添加 @EnableScheduling 注解，开启定时任务：

1
2
3
4
5
6
7
8
9

@SpringBootApplication
@EnableScheduling
public class ScheduledApplication {

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

}

接下来配置定时任务：

1
2
3
4
5
6
7
8
9
10
11
12

@Scheduled(fixedRate = 2000)
public void fixedRate() {
    System.out.println("fixedRate>>>"+new Date());    
}
@Scheduled(fixedDelay = 2000)
public void fixedDelay() {
    System.out.println("fixedDelay>>>"+new Date());
}
@Scheduled(initialDelay = 2000,fixedDelay = 2000)
public void initialDelay() {
    System.out.println("initialDelay>>>"+new Date());
}

1. 首先使用 @Scheduled 注解开启一个定时任务。
2. fixedRate 表示任务执行之间的时间间隔，具体是指两次任务的开始时间间隔，即第二次任务开始时，第一次任务可能还没结束。
3. fixedDelay 表示任务执行之间的时间间隔，具体是指本次任务结束到下次任务开始之间的时间间隔。
4. initialDelay 表示首次任务启动的延迟时间。
5. 所有时间的单位都是毫秒。

上面这是一个基本用法，除了这几个基本属性之外，@Scheduled 注解也支持 cron 表达式，使用 cron 表达式，可以非常丰富的描述定时任务的时间。cron 表达式格式如下：

[秒] [分] [小时] [日] [月] [周] [年]

具体取值如下：

这一块需要大家注意的是，月份中的日期和星期可能会起冲突，因此在配置时这两个得有一个是 ?

通配符含义：

• ? 表示不指定值，即不关心某个字段的取值时使用。需要注意的是，月份中的日期和星期可能会起冲突，因此在配置时这两个得有一个是 ?
• * 表示所有值，例如:在秒的字段上设置 *,表示每一秒都会触发
• , 用来分开多个值，例如在周字段上设置 “MON,WED,FRI” 表示周一，周三和周五触发
• - 表示区间，例如在秒上设置 “10-12”,表示 10,11,12秒都会触发
• / 用于递增触发，如在秒上面设置”5/15” 表示从5秒开始，每增15秒触发(5,20,35,50)
• # 序号(表示每月的第几个周几)，例如在周字段上设置”6#3”表示在每月的第三个周六，(用 在母亲节和父亲节再合适不过了)
• 周字段的设置，若使用英文字母是不区分大小写的 ，即 MON 与mon相同
• L 表示最后的意思。在日字段设置上，表示当月的最后一天(依据当前月份，如果是二月还会自动判断是否是润年), 在周字段上表示星期六，相当于”7”或”SAT”（注意周日算是第一天）。如果在”L”前加上数字，则表示该数据的最后一个。例如在周字段上设置”6L”这样的格式,则表示”本月最后一个星期五”
• W 表示离指定日期的最近工作日(周一至周五)，例如在日字段上设置”15W”，表示离每月15号最近的那个工作日触发。如果15号正好是周六，则找最近的周五(14号)触发, 如果15号是周未，则找最近的下周一(16号)触发，如果15号正好在工作日(周一至周五)，则就在该天触发。如果指定格式为 “1W”,它则表示每月1号往后最近的工作日触发。如果1号正是周六，则将在3号下周一触发。(注，”W”前只能设置具体的数字,不允许区间”-“)
• L 和 W 可以一组合使用。如果在日字段上设置”LW”,则表示在本月的最后一个工作日触发(一般指发工资 )

例如，在 @Scheduled 注解中来一个简单的 cron 表达式，每隔5秒触发一次，如下：

1
2
3
4

@Scheduled(cron = "0/5 * * * * *")
public void cron() {
    System.out.println(new Date());
}

上面介绍的是使用 @Scheduled 注解的方式来实现定时任务，接下来我们再来看看如何使用 Quartz 实现定时任务。

2. Quartz

一般在项目中，除非定时任务涉及到的业务实在是太简单，使用 @Scheduled 注解来解决定时任务，否则大部分情况可能都是使用 Quartz 来做定时任务。在 Spring Boot 中使用 Quartz ，只需要在创建项目时，添加 Quartz 依赖即可：

项目创建完成后，也需要添加开启定时任务的注解：

1
2
3
4
5
6
7

@SpringBootApplication
@EnableScheduling
public class QuartzApplication {
    public static void main(String[] args) {
        SpringApplication.run(QuartzApplication.class, args);
    }
}

Quartz 在使用过程中，有两个关键概念，一个是JobDetail（要做的事情），另一个是触发器（什么时候做），要定义 JobDetail，需要先定义 Job，Job 的定义有两种方式：

第一种方式，直接定义一个Bean：

1
2
3
4
5
6

@Component
public class MyJob1 {
    public void sayHello() {
        System.out.println("MyJob1>>>"+new Date());
    }
}

关于这种定义方式说两点：

1. 首先将这个 Job 注册到 Spring 容器中。
2. 这种定义方式有一个缺陷，就是无法传参。

第二种定义方式，则是继承 QuartzJobBean 并实现默认的方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public class MyJob2 extends QuartzJobBean {
    HelloService helloService;
    public HelloService getHelloService() {
        return helloService;
    }
    public void setHelloService(HelloService helloService) {
        this.helloService = helloService;
    }
    @Override
    protected void executeInternal(JobExecutionContext jobExecutionContext) throws JobExecutionException {
        helloService.sayHello();
    }
}
public class HelloService {
    public void sayHello() {
        System.out.println("hello service >>>"+new Date());
    }
}

和第1种方式相比，这种方式支持传参，任务启动时，executeInternal 方法将会被执行。

Job 有了之后，接下来创建类，配置 JobDetail 和 Trigger 触发器，如下：

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
43
44
45

@Configuration
public class QuartzConfig {
    @Bean
    MethodInvokingJobDetailFactoryBean methodInvokingJobDetailFactoryBean() {
        MethodInvokingJobDetailFactoryBean bean = new MethodInvokingJobDetailFactoryBean();
        bean.setTargetBeanName("myJob1");
        bean.setTargetMethod("sayHello");
        return bean;
    }
    @Bean
    JobDetailFactoryBean jobDetailFactoryBean() {
        JobDetailFactoryBean bean = new JobDetailFactoryBean();
        bean.setJobClass(MyJob2.class);
        JobDataMap map = new JobDataMap();
        map.put("helloService", helloService());
        bean.setJobDataMap(map);
        return bean;
    }
    @Bean
    SimpleTriggerFactoryBean simpleTriggerFactoryBean() {
        SimpleTriggerFactoryBean bean = new SimpleTriggerFactoryBean();
        bean.setStartTime(new Date());
        bean.setRepeatCount(5);
        bean.setJobDetail(methodInvokingJobDetailFactoryBean().getObject());
        bean.setRepeatInterval(3000);
        return bean;
    }
    @Bean
    CronTriggerFactoryBean cronTrigger() {
        CronTriggerFactoryBean bean = new CronTriggerFactoryBean();
        bean.setCronExpression("0/10 * * * * ?");
        bean.setJobDetail(jobDetailFactoryBean().getObject());
        return bean;
    }
    @Bean
    SchedulerFactoryBean schedulerFactoryBean() {
        SchedulerFactoryBean bean = new SchedulerFactoryBean();
        bean.setTriggers(cronTrigger().getObject(), simpleTriggerFactoryBean().getObject());
        return bean;
    }
    @Bean
    HelloService helloService() {
        return new HelloService();
    }
}

关于这个配置说如下几点：

1. JobDetail 的配置有两种方式：MethodInvokingJobDetailFactoryBean 和 JobDetailFactoryBean 。
2. 使用 MethodInvokingJobDetailFactoryBean 可以配置目标 Bean 的名字和目标方法的名字，这种方式不支持传参。
3. 使用 JobDetailFactoryBean 可以配置 JobDetail ，任务类继承自 QuartzJobBean ，这种方式支持传参，将参数封装在 JobDataMap 中进行传递。
4. Trigger 是指触发器，Quartz 中定义了多个触发器，这里向大家展示其中两种的用法，SimpleTrigger 和 CronTrigger 。
5. SimpleTrigger 有点类似于前面说的 @Scheduled 的基本用法。
6. CronTrigger 则有点类似于 @Scheduled 中 cron 表达式的用法。

全部定义完成后，启动 Spring Boot 项目就可以看到定时任务的执行了。

3. 总结

这里主要向大家展示了 Spring Boot 中整合两种定时任务的方法，整合成功之后，剩下的用法基本上就和在 SSM 中使用一致了，不再赘述。

原文地址：https://mp.weixin.qq.com/s/y0pjtNUZhOW2ZBOy4m-xsA

参考文章：mysql索引回表

真实面试题：https://www.nowcoder.com/discuss/342185?type=2&order=3&pos=2&page=1

所谓的回表查询，就是先通过普通索引定位到主键值，再通过聚集索引定位到行记录，需要扫码两遍索引树，因此它的性能较扫一遍索引树更低。

《迅猛定位低效 SQL？》留了一个尾巴：

1
2

select id,name where name='shenjian'
select id,name,sex where name='shenjian'

多查询了一个属性，为何检索过程完全不同？

• 什么是回表查询？

• 什么是索引覆盖？

• 如何实现索引覆盖？

• 哪些场景，可以利用索引覆盖来优化 SQL？

这些，这是今天要分享的内容。

画外音：本文试验基于 MySQL5.6-InnoDB。

一、什么是回表查询？

这先要从 InnoDB 的索引实现说起，InnoDB 有两大类索引：

• 聚集索引(clustered index)
• 普通索引(secondary index)

InnoDB 聚集索引和普通索引有什么差异？

InnoDB聚集索引的叶子节点存储行记录，因此， InnoDB 必须要有，且只有一个聚集索引：

（1）如果表定义了 PK，则 PK 就是聚集索引；

（2）如果表没有定义 PK，则第一个 not NULL unique 列是聚集索引；

（3）否则，InnoDB 会创建一个隐藏的 row-id 作为聚集索引；

画外音：所以 PK 查询非常快，直接定位行记录。

InnoDB普通索引的叶子节点存储主键值。

画外音：注意，不是存储行记录头指针，MyISAM 的索引叶子节点存储记录指针。

举个栗子，不妨设有表：

1

t(id PK, name KEY, sex, flag);

画外音：id 是聚集索引，name 是普通索引。

表中有四条记录：

1
2
3
4

1, shenjian, m, A
3, zhangsan, m, A
5, lisi, m, A
9, wangwu, f, B

两个 B+树索引分别如上图：

（1）id 为 PK，聚集索引，叶子节点存储行记录；

（2）name 为 KEY，普通索引，叶子节点存储 PK 值，即 id；

既然从普通索引无法直接定位行记录，那普通索引的查询过程是怎么样的呢？

通常情况下，需要扫码两遍索引树。

例如：

1

select * from t where name='lisi';

是如何执行的呢？

如粉红色路径，需要扫码两遍索引树：

（1）先通过普通索引定位到主键值 id=5；

（2）再通过聚集索引定位到行记录；

这就是所谓的回表查询，先定位主键值，再定位行记录，它的性能较扫一遍索引树更低。

二、什么是索引覆盖(Covering index)？

额，楼主并没有在 MySQL 的官网找到这个概念。

画外音：治学严谨吧？

借用一下 SQL-Server 官网的说法。

MySQL 官网，类似的说法出现在 explain 查询计划优化章节，即 explain 的输出结果 Extra 字段为 Using index 时，能够触发索引覆盖。

不管是 SQL-Server 官网，还是 MySQL 官网，都表达了：只需要在一棵索引树上就能获取 SQL 所需的所有列数据，无需回表，速度更快。

三、如何实现索引覆盖？

常见的方法是：将被查询的字段，建立到联合索引里去。

仍是《迅猛定位低效 SQL？》中的例子：

1
2
3
4
5
6

create table user (
id int primary key,
name varchar(20),
sex varchar(5),
index(name)
)engine=innodb;

第一个 SQL 语句：

1

select id,name from user where name='shenjian';

能够命中 name 索引，索引叶子节点存储了主键 id，通过 name 的索引树即可获取 id 和 name，无需回表，符合索引覆盖，效率较高。

画外音，Extra：Using index。

第二个 SQL 语句：

1

select id,name,sex from user where name='shenjian';

能够命中 name 索引，索引叶子节点存储了主键 id，但 sex 字段必须回表查询才能获取到，不符合索引覆盖，需要再次通过 id 值扫码聚集索引获取 sex 字段，效率会降低。

画外音，Extra：Using index condition。

如果把(name)单列索引升级为联合索引(name, sex)就不同了。

1
2
3
4
5
6

create table user (
id int primary key,
name varchar(20),
sex varchar(5),
index(name, sex)
)engine=innodb;

可以看到：

1
2

select id,name ... where name='shenjian';
select id,name,sex ... where name='shenjian';

都能够命中索引覆盖，无需回表。

画外音，Extra：Using index。

四、哪些场景可以利用索引覆盖来优化 SQL？

场景 1：全表 count 查询优化

原表为：

1

user(PK id, name, sex);

直接：

1

select count(name) from user;

不能利用索引覆盖。

添加索引：

1

alter table user add key(name);

就能够利用索引覆盖提效。

场景 2：列查询回表优化

1

select id,name,sex ... where name='shenjian';

这个例子不再赘述，将单列索引(name)升级为联合索引(name, sex)，即可避免回表。

场景 3：分页查询

1

select id,name,sex ... order by name limit 500,100;

将单列索引(name)升级为联合索引(name, sex)，也可以避免回表。

InnoDB 聚集索引普通索引，回表，索引覆盖，希望这 1 分钟大家有收获。

提示，如果你不清楚 explain 结果 Extra 字段为 Using index 的含义，请阅读前序文章：《如何利用工具，迅猛定位低效 SQL？》