序言

  递归（英语：Recursion），又译为递回，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的。也可以理解为自我复制的过程。

  简单来讲，递归就是函数反复调用自身的过程。
  你肯定听过这个故事：从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？“从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？‘从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？……’”
  上面的故事即是递归思想的体现。

算法概述

算法分类

  十种常见排序算法可以分为两大类：

• 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破 O(nlogn) ，因此也称为非线性时间比较类排序。
• 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

算法复杂度

  相关概念:

• 稳定：若 a 原本在 b 前面，而 a=b ，排序之后 a 仍然在 b 的前面。
• 不稳定：若 a 原本在 b 的前面，而 a=b ，排序之后 a 可能会出现在 b 的后面。
• 时间复杂度：描述算法的运行时间与输入数据 n 之间的关系，反映了当 n 变化时，操作次数呈现什么规律。
• 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模 n 的函数。

选择排序（Selection Sort）

  选择排序（Selection-sort）：首先在乱序序列中找到最小（大）元素存放到排序序列的起始位置，然后再从剩余乱序序列中继续寻找最小（大）元素，放到已排序序列的末尾。以此类推，直到所有元素排序完毕。

算法描述

   n 个记录的直接选择排序可经过 n-1 趟直接选择排序得到有序结果。具体算法描述如下：

• 初始状态：无序区为 R[1..n] ，有序区为空；
• 第 i 趟排序 (i=1,2,3…n-1) 开始时，当前有序区和无序区分别为 R[1..i-1] 和 R(i..n） 。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少 1 个的新无序区；
• n-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

public class SelectSort {
    public int[] selectSort(int[] arr) {
        // 定义最小数的索引及临时保存变量
        int minIndex, temp;
        for (int i = 0; i < arr.length - 1; i++) {
            minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
        return arr;
    }

    @Test
    public void test() {
        int[] arr = {1, 3, 51, 21, 3, 2, 1};
        System.out.println(Arrays.toString(selectSort(arr)));
    }
}

算法分析

  表现最稳定的排序算法之一，因为无论什么数据进去都是 O($n^2$) 的时间复杂度，所以用到它的时候，数据规模越小越好。
  选择排序唯一的好处可能就是不占用额外的内存空间。理论上讲，选择排序可能也是平时排序一般最容易想到的排序方式了。

冒泡排序（Bubble Sort）

  冒泡排序（Bubble Sort）：重复地走访过要排序的数列，一次比较两个元素，若它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
  这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

算法描述

  冒泡排序的步骤如下：

• 比较相邻的元素：若第一个比第二个大，就交换它们两个；
• 依次对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
• 针对所有的元素重复以上的步骤，除了最后一个；
• 重复步骤 1~3 ，直到排序完成。

动图演示

代码实现

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

public class BubbleSort {
    public int[] bubbleSort(int[] arr) {
        int temp = 0;
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        return arr;
    }

    @Test
    public void test() {
        int[] arr = {1, 3, 51, 21, 3, 2, 1};
        System.out.println(Arrays.toString(bubbleSort(arr)));
    }
}

插入排序（Insertion Sort）

  插入排序（Insertion Sort）：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入，类似于玩扑克牌。

算法描述

  一般来说，插入排序都采用 in-place 在数组上实现。具体算法描述如下：

• 从第一个元素开始，该元素可以认为已经被排序；
• 取出下一个元素，在已经排序的元素序列中从后向前扫描；
• 若该元素（已排序）大于新元素，将该元素移到下一位置；
• 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
• 将新元素插入到该位置后；
• 重复步骤2~5。

动图演示

代码实现

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

public class InsertionSort {
    public int[] insertionSort(int[] arr) {
        int temp = 0;
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
                temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
            }
            // 上面为简写，详见下面
            // for (int j = i; j > 0; j--) {
            //     if (arr[j] < arr[j - 1]) {
            //         temp = arr[j];
            //         arr[j] = arr[j - 1];
            //         arr[j - 1] = temp;
            //     } else {
            //         break;
            //     }
            // }
        }
        return arr;
    }

    @Test
    public void test() {
        int[] arr = {1, 3, 51, 21, 3, 2, 1};
        System.out.println(Arrays.toString(insertionSort(arr)));
    }
}

算法分析

  插入排序在实现上，通常采用 in-place 排序（即只需用到 O(1) 的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

希尔排序（Shell Sort）

  希尔排序（Shell Sort）是 1959 年由 Shell 发明，第一个突破 O(n2) 的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。
  希尔排序也叫缩小增量排序。

算法描述

  先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

• 选择一个增量序列 t1，t2，…，tk，其中 ti > tj ，tk = 1 ；
• 按增量序列个数 k，对序列进行 k 趟排序；
• 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

动图演示

代码实现

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

function shellSort(arr) {
    var len = arr.length;
    for (var gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
        // 注意：这里和动图演示的不一样，动图是分组执行，实际操作是多个分组交替执行
        for (var i = gap; i < len; i++) {
            var j = i;
            var current = arr[i];
            while (j - gap >= 0 && current < arr[j - gap]) {
                 arr[j] = arr[j - gap];
                 j = j - gap;
            }
            arr[j] = current;
        }
    }
    return arr;
}

算法分析

  希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版）》的合著者Robert Sedgewick提出的。　

快速排序（Quick Sort）

  快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

算法描述

  快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

• 从数列中挑出一个元素，称为 “基准”（pivot）；
• 进行分区（partition）操作：重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。
• 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

动图演示

代码实现

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

public class QuickSort {
    public void quickSort(int[] arr) {
        quick(arr, 0, arr.length - 1);
    }

    private void quick(int[] arr, int l, int r) {
        // 终止条件
        if (l >= r) {
            return;
        }
        // 目的
        int p = partition(arr, l, r);
        // 递归排序
        quick(arr, l, p - 1);
        quick(arr, p + 1, r);
    }

    /**
     * 分区：该过程包含 3 部分，pivot ，小于 pivot 部分，大于 pivot 部分
     * 分区完成后左边部分小于中间的 pivot ，右边大于 pivot
     */
    private int partition(int[] arr, int l, int r) {
        // 设定基准值 pivot
        int pivot = arr[l];
        int i = l;
        for (int j = l + 1; j <= r; j++) {
            // 如果当前（索引为 j ）元素小于 pivot ，则交换
            if (arr[j] < pivot) {
                swap(arr, i + 1, j);
                i++;
            }// 否则(大于) j ++
        }
        // 交换 pivot（l） 及小于 pivot 部分末尾元素
        swap(arr, l, i);
        // 返回
        return i;
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

归并排序（Merge Sort）

  归并排序是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

算法描述

• 把长度为 n 的输入序列分成两个长度为 n/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

function mergeSort(arr) {
    var len = arr.length;
    if (len < 2) {
        return arr;
    }
    var middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}
 
function merge(left, right) {
    var result = [];
 
    while (left.length>0 && right.length>0) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }
 
    while (left.length)
        result.push(left.shift());
 
    while (right.length)
        result.push(right.shift());
 
    return result;
}

算法分析

  归并排序是一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn）的时间复杂度。代价是需要额外的内存空间。

堆排序（Heap Sort）

  堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

算法描述

• 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
• 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
• 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

var len;    // 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量
 
function buildMaxHeap(arr) {   // 建立大顶堆
    len = arr.length;
    for (var i = Math.floor(len/2); i >= 0; i--) {
        heapify(arr, i);
    }
}
 
function heapify(arr, i) {     // 堆调整
    var left = 2 * i + 1,
        right = 2 * i + 2,
        largest = i;
 
    if (left < len && arr[left] > arr[largest]) {
        largest = left;
    }
 
    if (right < len && arr[right] > arr[largest]) {
        largest = right;
    }
 
    if (largest != i) {
        swap(arr, i, largest);
        heapify(arr, largest);
    }
}
 
function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
 
function heapSort(arr) {
    buildMaxHeap(arr);
 
    for (var i = arr.length - 1; i > 0; i--) {
        swap(arr, 0, i);
        len--;
        heapify(arr, 0);
    }
    return arr;
}

计数排序（Counting Sort）

  计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

算法描述

• 找出待排序的数组中最大和最小的元素；
• 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
• 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
• 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

动图演示

代码实现

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

function countingSort(arr, maxValue) {
    var bucket = new Array(maxValue + 1),
        sortedIndex = 0;
        arrLen = arr.length,
        bucketLen = maxValue + 1;
 
    for (var i = 0; i < arrLen; i++) {
        if (!bucket[arr[i]]) {
            bucket[arr[i]] = 0;
        }
        bucket[arr[i]]++;
    }
 
    for (var j = 0; j < bucketLen; j++) {
        while(bucket[j] > 0) {
            arr[sortedIndex++] = j;
            bucket[j]--;
        }
    }
 
    return arr;
}

算法分析

  计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是 O(n+k) ，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。

桶排序（Bucket Sort）

  桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

算法描述

• 设置一个定量的数组当作空桶；
• 遍历输入数据，并且把数据一个一个放到对应的桶里去；
• 对每个不是空的桶进行排序；
• 从不是空的桶里把排好序的数据拼接起来。

图片演示

代码实现

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

function bucketSort(arr, bucketSize) {
    if (arr.length === 0) {
      return arr;
    }
 
    var i;
    var minValue = arr[0];
    var maxValue = arr[0];
    for (i = 1; i < arr.length; i++) {
      if (arr[i] < minValue) {
          minValue = arr[i];                // 输入数据的最小值
      } else if (arr[i] > maxValue) {
          maxValue = arr[i];                // 输入数据的最大值
      }
    }
 
    // 桶的初始化
    var DEFAULT_BUCKET_SIZE = 5;            // 设置桶的默认数量为5
    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
    var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;  
    var buckets = new Array(bucketCount);
    for (i = 0; i < buckets.length; i++) {
        buckets[i] = [];
    }
 
    // 利用映射函数将数据分配到各个桶中
    for (i = 0; i < arr.length; i++) {
        buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
    }
 
    arr.length = 0;
    for (i = 0; i < buckets.length; i++) {
        insertionSort(buckets[i]);                      // 对每个桶进行排序，这里使用了插入排序
        for (var j = 0; j < buckets[i].length; j++) {
            arr.push(buckets[i][j]);                     
        }
    }
 
    return arr;
}

算法分析

  桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。

基数排序（Radix Sort）

  基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

算法描述

• 取得数组中的最大数，并取得位数；
• arr为原始数组，从最低位开始取每个位组成radix数组；
• 对radix进行计数排序（利用计数排序适用于小范围数的特点）；

动图演示

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

var counter = [];
function radixSort(arr, maxDigit) {
    var mod = 10;
    var dev = 1;
    for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        for(var j = 0; j < arr.length; j++) {
            var bucket = parseInt((arr[j] % mod) / dev);
            if(counter[bucket]==null) {
                counter[bucket] = [];
            }
            counter[bucket].push(arr[j]);
        }
        var pos = 0;
        for(var j = 0; j < counter.length; j++) {
            var value = null;
            if(counter[j]!=null) {
                while ((value = counter[j].shift()) != null) {
                      arr[pos++] = value;
                }
          }
        }
    }
    return arr;
}

算法分析

  基数排序基于分别排序，分别收集，所以是稳定的。但基数排序的性能比桶排序要略差，每一次关键字的桶分配都需要O(n)的时间复杂度，而且分配之后得到新的关键字序列又需要O(n)的时间复杂度。假如待排数据可以分为d个关键字，则基数排序的时间复杂度将是O(d*2n) ，当然d要远远小于n，因此基本上还是线性级别的。

  基数排序的空间复杂度为 O(n+k)，其中 k 为桶的数量。一般来说 n>>k ，因此额外空间需要大概n个左右。

二分查找

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

public class BinarySearch {
    public int binarySearch(int[] arr, int target) {
        int l = 0, r = arr.length - 1;
        while (l <= r) {
            // 防止溢出
            int mid = l + (r - l) / 2;
            if (target == arr[mid]) {
                return mid;
            } else if (target < arr[mid]) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return -1;
    }
}

参考资料

• 十大经典排序算法（动图演示）

文章信息

索引的 Maping 优化

• 对于不需要建立倒排索引的字段，可以将该值设置为index属性设置为false，提高 ES 性能，比如说用户图片的地址就不需要进行搜索，可以这么设置
• 数值型的类型字段尽量选择范围小的类型，提高搜索效率
• 对于浮点型的类型尽量用比例因子，使用比例因子的好处是整型比浮点型更易压缩，节省磁盘空间。比如一个价格字段，单位为元，将比例因子设置为 100，在 ES 中会按分存储。由于比例因子为 100， 如果我们输入的价格是 23.45，则 ES 中会将 23.45 乘以 100 存储在 ES 中。如果输入的价格是 23.456， ES会将 23.456 乘以 100 再取一个接近原始值的数，得出 2346。此时字段映射如下:

1
2
3
4
5
6

{
  "price": {
    "type": "scaled_float",
    "sca1ing_factor": 100
  }
}

疑问

• 索引分片怎么设置？
• 索引如何重建？
• 索引别名如何查询的？

磁盘

  磁盘在现代服务器.上通常都是瓶颈。Elasticsearch重度使用磁盘，你的磁盘能处理的吞吐量越大，你的节点就越稳定。这里有一些优化磁盘I/0 的技巧：

• 使用 SSD，这比机械磁盘优秀多了
• 使用 RAID 0。条带化 RAID 会提高磁盘 /O，代价显然就是当一块硬盘故障时整个就故障了。不要使用镜像或者奇偶校验RAID因为副本已经提供了这个功能
• 使用多块硬盘，并允许 Elasticsearch 通过多个path.data 目录配置把数据条带化分配到它们上面
• 不要使用远程挂载的存储，比如 NFS。这个引入的延迟对性能来说完全是背道而驰的

分片策略

合理分片

  分片和副本的设计为 ES 提供了支持分布式和故障转移的特性，但并不意味着分片和副本是可以无限分配的。而且由于索引主分片的路由机制，一旦主分片完成分配后，无法重新修改主分片的数量。
  可能有人会说，我不知道这个索引将来会变得多大，并且过后我也不能更改索引的大小，所以为了保险起见，还是给它设为 100 个分片吧。这样并不合理，因为配置分片时并不是没有代价的：

• 一个分片的底层即为一个 Lucene 索引，会消耗一定文件句柄、内存、以及 CPU 运转
• 每一个搜索请求都需要命中索引中的每一个分片，如果每一个分片都处于不同的节点还好，但如果多个分片都需要在同一个节点上竞争使用相同的资源，那么会降低一部分性能
• 用于计算相关度的词项统计信息是基于分片的。如果有许多分片，每一个都只有很少的数据会导致很低的相关度

  一个业务索引具体需要分配多少分片可能需要架构师和技术人员对业务的增长有个预先的判断，横向扩展应当分阶段进行， 为下一阶段准备好足够的资源。 只有当你进入到下一个阶段，你才有时间思考需要作出哪些改变来达到这个阶段。一般来说， 我们遵循一些原则

• 控制每个分片占用的硬盘容量不超过 ES 的最大 JVM 的堆空间设置（一般设置不超过 32G，参考下文的 JVM 设置原则），因此，如果索引的总容量在 500G 左右，那分片大小在 16 个左右即可；当然，最好同时考虑原则

• 考虑一下node数量，一般一个节点有时候就是一台物理机， 如果分片数过多，大大超过了节点数，很可能会导致一个节点上存在多个分片，一旦该节点故障，即使保持了1个以上的副本，同样有可能会导致数据丢失，集群无法恢复。所以，一般都设置分片数不超过节点数的 3 倍

• 主分片，副本和节点最大数之间数量，我们分配的时候可以参考以下关系：节点数<=主分片数*（副本数+1）

推迟分片分配

  对于节点瞬时中断的问题，默认情况， 集群会等待一分钟来查看节点是否会重新加入，如果节点在此期间重新加入， 重新加入的节点会保持其现有的分片数据，不会触发新的分片分配。这样就可以减少 ES 在自动再平衡可用分片时所带来的极大开销。

  通过修改参数 delayed timeout，可以延长再均衡的时间，可以全局设置也可以在索引级别进行修改：

1
2
3
4
5
6

PUT /_all/_settings
{
  "settings": {
    "index.unassigned.node_left.delayed_timeout": "5m"
  }
}

选择性路由

  当我们查询文档的时候，Elasticsearch 如何知道一个文档应该存放到哪个分片中呢？它其实是通过下面这个公式来计算出来：

1

shard = hash(routing) % number_of primary_shards

routing 默认值是文档的 id， 也可以采用自定义值，比如用户 id。

不带 routing 查询

  在查询的时候因为不知道要查询的数据具体在哪个分片上， 所以整个过程分为 2 个步骤：

• 分发：请求到达协调节点后， 协调节点将查询请求分发到每个分片上
• 聚合：协调节点搜集到每个分片上查询结果， 在将查询的结果进行排序，之后给用户返回结果

带 routing 查询（更快）

  查询的时候，可以直接根据 routing 信息定位到某个分配查询， 不需要查询所有的分配，经过协调节点排序。
  向上面自定义的用户查询，如果 routing 设置为 userid 的话， 就可以直接查询出数据来，效率提升很多。

写入速度优化

  ES 的默认配置，是综合了数据可靠性、写入速度、搜索实时性等因素。

  实际使用时， 我们需要根据公司要求，进行偏向性的优化。

  针对于搜索性能要求不高，但是对写入要求较高的场景，我们需要尽可能的选择恰当写优化策略。

  综合来说，可以考虑以下几个方面来提升写索引的性能：

• 加大 Translog Flush，目的是降低 Iops、 Writeblock
• 增加 Index Refresh 间隔，目的是减少 Segment Merge 的次数
• 调整 Bulk 线程池和队列
• 优化节点间的任务分布
• 优化 Lucene 层的索引建立，目的是降低 CPU 及 IO

批量数据提交

  ES 提供了 Bulk API 工支持批量操作，当我们有大量的写任务时，可以使用 Bulk 来进行批量写入。
  通用的策略如下：Bulk 默认设置批量提交的数据量不能超过 100M。数据条数一般是根据文档的大小和服务器性能而定的，但是单次批处理的数据大小应从 5MB~15MB 逐渐增加，当性能没有提升时，把这个数据量作为最大值。

优化存储设备

  ES 是一种密集使用磁盘的应用，在段合并的时候会频繁操作磁盘，所以对磁盘要求较高，当磁盘速度提升之后，集群的整体性能会大幅度提高。

合理使用合并

  Lucene以段的形式存储数据。当有新的数据写入索引时，Lucene 就会自动创建一个新的段。
  随着数据量的变化，段的数量会越来越多，消耗的多文件句柄数及CPU就越多，查询效率就会下降。
  由于Lucene 段合并的计算量庞大，会消耗大量的I/O， 所以ES默认采用较保守的策略，让后台定期进行段合并

减少Refresh的次数

  Lucene在新增数据时，用了延迟写入的策略，默认情况下索引的refiesh interval 为1秒。
  Lucene将待写入的数据先写到内存中，超过1秒（默认）时就会触发一次 Refesh， 然后Refresh会把内存中的的数据刷新到操作系统的文件缓存系统中。
  如果我们对搜索的实效性要求不高，可以将Refresh 周期延长，例如30秒。
这样还可以有效地减少段刷新次数，提高写的效率，但这同时意味着需要消耗更多的 Heap 内存。

加大 Flush 设置

  Flush的主要目的是把文件缓存系统中的段持久化到硬盘，当Translog 的数据量达到512MB或者30分钟时，会触发一次Flush.
  index.translog. flush threshold size参数的默认值是 512MB，我们进行修改。
  增加参数值意味着文件缓存系统中可能需要存储更多的数据，所以我们需要为操作系统的文件缓存系统留下足够的空间。

减少副本的数量

  ES 为了保证集群的可用性，提供了Replica（副本）支持，由于每个副本也会执行分析、索引及可能的合并过程，所以 Replica 的数量会影响写索引的效率。

  当写索引时，除了把数据写入主分片节点中，还会并行将数据写入到所有副本分片节点，副本节点越多，写索引的效率就越慢。

  因此，如果我们需要大批量进行写入操作，可以先禁止 Replica 复制，设置index.number.of_replicas: 0关闭副本；在写入完成后，再将 Replica 修改回正常的状态。

内存设置

  ES 默认安装后设置的内存是基于服务器总内存设置的，如果安装 ES 的机器还存在其他应用，那么会影响到它们。

  对于解压安装的 ES，则其中包含一个jvm.option配置文件，可通过以下参数设置 ES 堆大小：

1
2
3

# Xms 表示堆的初始大小，Xmx 表示可分配的最大内存
-Xms4g
-Xmx4g

  确保 Xmx 和 Xms 的大小是相同的，其目的是为了能够在 Java 垃圾回收机制清理完堆区后不需要重新分隔计算堆区的大小而浪费资源，可以减轻伸缩堆大小带来的压力。

  假设你有一个 64G 内存的机器，按照正常思维思考，你可能会认为把 64G 内存都给ES比较好，但现实是这样吗，越大越好？

  虽然内存对 ES 来说至关重要，但是答案是否定的！因为 ES 堆内存的分配需要满足以下两个原则：

• 不要超过物理内存的 50%：Lucene 的设计目的是把底层 OS 里的数据缓存到内存中。Lucene 的段是分别存储到单个文件中的，这些文件都是不会变化的，所以很利于缓存，同时操作系统也会把这些段文件缓存起来，以便更快的访问。因此如果设置的堆内存过大，Lucene 可用的内存将会减少，就会严重影响降低 Lucene 的全文本查询性能。
• 堆内存的大小最好不要超过 32GB： 在 Java 中，所有对象都分配在堆上，然后有一个 Class Pointer指针指向它的类元数据。这个指针在 64 位的操作系统上为 64 位，64 位的操作系统可以使用更多的内存（2^64）。在 32 位的系统上为 32 位，32 位的操作系统的最大寻址空间为 4GB（2^32）。但是 64 位的指针意味着更大的浪费，因为你的指针本身大了。浪费内存不算，更糟糕的是，更大的指针在主内存和缓存器（例如 LLC，L1 等）之间移动数据的时候，会占用更多的带宽。

  最终我们都会采用 31G 设置

1
2

-Xms 31g
-Xmx 31g

更新速度优化

ES版本5.6，数据量在3000万左右，数据更新频率比较频繁，总共的更新速度大概是1w/s-5w/s。
最新的数据先进kafka，再由flink消费写入ES。
目前发现在默认的ES配置下，bulk update或者upsert的速度始终上不去，所有节点的cpu使用率才25%左右，速度最高只能到1w/s左右。
如果改成这些数据全部是插入，不做更新操作，那么cpu可以跑满，而且kafka的消费绝对没有积压。
试过增加节点，效果很小，速度看起来有一点点的增加。试过增加分片数，有效果，但仍然不是很明显。

请问是什么原因导致这个现象呢，增加分片对写入速度有提升又是为什么呢？
像这种场景，有没有办法直接的提升update/upsert速率，或者间接解决，比如全部用插入的方式写入，查询时同一个id的记录取时间最近的数据。那么查询方式还有删除旧数据这块怎么设计比较好

1.update是先get再insert然后再delete（标记删除）旧的文档，和insert相比，肯定update耗时多
2.由于一次操作完成时长多，线程池数量有限，导致cpu只有25%（猜测…）
3.适当增加ES分片，对写入是有一点提高，因为相当于多出来了lucene进程，可以接收的请求多了，付出的代价就是分片多了之后同步数据是需要消耗性能的，然后查询更是会性能降低
4.客户端使用层面：可以全部使用insert提高性能，然后定时去delete，定时（低峰期）合并segment，优化数据结构
5.集群本身层面：可以控制refresh的频率，translog设置，副本可以先干掉（写完再补回来），线程池参数修改——-这些都是危险操作，评估后再进行实践

在上面基础上补充：

1. 使用ES自动的id，不要指定id
2. 提高操作系统 filesystem cache
3. 关注下 index_buffer_size 这个参数

在不改业务逻辑的情况下，只能指定id来做更新。
改线程池大小、设置translog异步写、加大refresh interval、index buffer size这些以前测试过都没有明显提高，或者说几乎没有提高。

改业务逻辑的话，不知道怎么样保持像不改业务逻辑那样的效果。例如有10条数据，9条更新频繁，1条几天都不更新一次。那么如果我每次都是新写入，查询时取时间最近的记录，这个好办，但删旧数据时，怎么办呢，如果根据时间删掉当天之前的全部数据，那么原来的10条数据可能只剩下9条了。

集群规模及索引规划

集群规模评估

集群规模的评估主要评估以下三个方面：

• 计算资源评估：计算资源的评估主要是评估单节点的CPU和内存。ES的计算资源一般消耗在写入和查询过程，经过总结大量ES集群的运维经验，2C8G 的配置大概能支持 5k doc/s 的写入，32C64G 的配置大概能支撑 5w doc/s的写入能力；
• 存储资源评估：存储资源的评估主要是评估磁盘的类型及容量大小。例如ES集群使用什么类型的磁盘，SSD或者高性能云盘，以及每块盘的容量大小，是选择单盘多容量，还是多盘少容量。而对于冷热分离的集群，则默认使用SSD作为热节点，高性能云盘作为温节点。另外腾讯云ES支持单节点挂载多块云硬盘，且经过性能压测，3块盘相比于1块盘，吞吐量大约有2.8倍的提升。因此如果对写入速度及IO性能要求较高，可选择挂载多块 SSD 磁盘；

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

PUT /user_gift_202401
{
  "aliases" : {
    "user_gift" : {} 
  }
}
PUT /user_gift_202402
{
  "aliases" : {
    "user_gift" : {} 
  }
}
......
POST /user_gift/_rollover
{
  "conditions": {
    "max_age":   "7d",
    "max_docs":  30000000,
    "max_size": "40gb"
  }
}

参考

ES 7.17——优化说明

序言

  通过传统的 JDBC 去连接数据源存在很多问题：

• ① 每次都需要输入数据库的基本信息，可否抽离一次固定以复用？
• ② Connection 是什么？每次都需要新建，大量创建与关闭会不会比较消耗资源，可否优化？
• ③ 如何保证数据的读写正确性？即事务是如何管理控制的？
• ④ SQL 语句定义、参数设置、结果集处理存在硬编码，不同的 SQL 零散地分布在各处，能否做成动态参数定义方式，并统一管理？
• ⑤ 每次都需要手动映射获取的数据到 POJO 对象，好麻烦呀，能不能自动映射？

  为了解决这些问题，ORM 框架应运而生，本文介绍的 Mybatis 就是这么一个 ORM 框架。

简介

  哈希表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做哈希函数，存放记录的数组称做哈希表。

  一个通俗的例子是，为了查找电话簿中某人的号码，可以创建一个按照人名首字母顺序排列的表（即建立人名 x 到首字母 F(x) 的一个函数关系），在首字母为 W 的表中查找“王”姓的电话号码，显然比直接查找就要快得多。这里使用人名作为关键字，“取首字母”是这个例子中哈希函数的函数法则 F(x) ，存放首字母的表对应哈希表。关键字和函数法则理论上可以任意确定。

简介

  映射，或者射影，在数学及相关的领域经常等同于函数。基于此，部分映射就相当于部分函数，而完全映射相当于完全函数。

简介

  在计算机科学中，集合是一组可变数量的数据项（也可能是0个）的组合，这些数据项可能共享某些特征，需要以某种操作方式一起进行操作。一般来讲，这些数据项的类型是相同的，或基类相同（若使用的语言支持继承 “继承 (计算机科学)”)）。列表（或数组）通常不被认为是集合，因为其大小固定，但事实上它常常在实现中作为某些形式的集合使用。

简介

  堆（英语：Heap）是计算机科学中的一种特别的树状数据结构。若是满足以下特性，即可称为堆：“给定堆中任意节点 P 和 C，若 P 是 C 的母节点，那么 P 的值会小于等于（或大于等于） C 的值”。若母节点的值恒小于等于子节点的值，此堆称为最小堆（英语：min heap）；反之，若母节点的值恒大于等于子节点的值，此堆称为最大堆（英语：max heap）。在堆中最顶端的那一个节点，称作根节点（英语：root node），根节点本身没有母节点（英语：parent node）。

简介

  在计算机科学中，二叉树（英语：Binary tree）是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序，不能随意颠倒。

简介

  链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针)(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到 O(1) 的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要 O(n) 的时间，而顺序表相应的时间复杂度分别是 O(logn) 和 O(1)。