跳表

什么是跳表

对于一个有序数组，可以使用高效的二分查找法，其时间复杂度为 O(log n)。

但是，即使是有序的链表，也只能使用低效的顺序查找，其时间复杂度为 O(n)。

如何提高链表的查找效率呢？

我们可以对链表加一层索引。具体来说，可以每两个结点提取一个结点到上一级，我们把抽出来的那一级叫作索引或索引层。索引节点中通过一个 down 指针，指向下一级结点。通过这样的改造，就可以支持类似二分查找的算法。我们把改造之后的数据结构叫作跳表（Skip list）。

随着数据的不断增长，一级索引层也变得越来越长。此时，我们可以为一级索引再增加一层索引层：二级索引层。

随着数据的膨胀，当二级索引层也变得很长时，我们可以继续为其添加新的索引层。这种链表加多级索引的结构，就是跳表。

跳表的时间复杂度

在一个具有多级索引的跳表中，第一级索引的结点个数大约就是 n/2，第二级索引的结点个数大约就是 n/4，第三级索引的结点个数大约就是 n/8，依次类推，也就是说，第 k 级索引的结点个数是第 k-1 级索引的结点个数的 1/2，那第 k 级索引结点的个数就是 n/(2k)。所以**跳表查询数据的时间复杂度就是 O(logn)**。

跳表的空间复杂度

比起单纯的单链表，跳表需要存储多级索引，肯定要消耗更多的存储空间。

假设原始链表大小为 n，那第一级索引大约有 n/2 个结点，第二级索引大约有 n/4 个结点，以此类推，每上升一级就减少一半，直到剩下 2 个结点。如果我们把每层索引的结点数写出来，就是一个等比数列。

1

索引节点数 = n/2 + n/4 + n/8 … + 8 + 4 + 2 = n-2

所以，跳表的空间复杂度是 O(n)。

跳表的存储空间其实还有压缩空间。比如，我们增加索引节点的范围，由“每两个节点抽一个上级索引节点”改为“每五个节点抽一个上级索引节点”，可以显著节省存储空间。

实际上，在软件开发中，我们不必太在意索引占用的额外空间。在讲数据结构和算法时，我们习惯性地把要处理的数据看成整数，但是在实际的软件开发中，原始链表中存储的有可能是很大的对象，而索引结点只需要存储关键值和几个指针，并不需要存储对象，所以当对象比索引结点大很多时，那索引占用的额外空间就可以忽略了。

跳表的操作

跳表是一种各方面性能都比较优秀的动态数据结构，可以支持快速的插入、删除、查找操作，写起来也不复杂，甚至可以替代红黑树（Red-black tree）。

高效的动态插入和删除

跳表不仅支持查找操作，还支持动态的插入、删除操作，而且插入、删除操作的时间复杂度也是 O(logn)。

• 插入操作：对于纯粹的单链表，需要遍历每个结点，来找到插入的位置。但是，对于跳表来说，我们讲过查找某个结点的的时间复杂度是 O(log n)，所以这里查找某个数据应该插入的位置，方法也是类似的，时间复杂度也是 O(log n)。
• 删除操作：如果这个结点在索引中也有出现，我们除了要删除原始链表中的结点，还要删除索引中的。因为单链表中的删除操作需要拿到要删除结点的前驱结点，然后通过指针操作完成删除。所以在查找要删除的结点的时候，一定要获取前驱结点。当然，如果我们用的是双向链表，就不需要考虑这个问题了。

跳表索引动态更新

当我们不停地往跳表中插入数据时，如果我们不更新索引，就有可能出现某 2 个索引结点之间数据非常多的情况。极端情况下，跳表还会退化成单链表。

如红黑树、AVL 树这样的平衡二叉树，是通过左右旋的方式保持左右子树的大小平衡，而跳表是通过随机函数来维护前面提到的“平衡性”。

当我们往跳表中插入数据的时候，我们可以选择同时将这个数据插入到部分索引层中。如何选择加入哪些索引层呢？可以通过一个随机函数，来决定将这个结点插入到哪几级索引中，比如随机函数生成了值 K，那我们就将这个结点添加到第一级到第 K 级这 K 级索引中。

为什么需要跳表

跳表是一种动态数据结构，支持快速的插入、删除、查找操作，时间复杂度都是 O(logn)。

跳表的空间复杂度是 O(n)。不过，跳表的实现非常灵活，可以通过改变索引构建策略，有效平衡执行效率和内存消耗。虽然跳表的代码实现并不简单，但是作为一种动态数据结构，比起红黑树来说，实现要简单多了。所以很多时候，我们为了代码的简单、易读，比起红黑树，我们更倾向用跳表。

跳表的应用场景

经典实现：Redis 的 Sorted Set、JDK 的 ConcurrentSkipListMap 和 ConcurrentSkipListSet 都是基于跳表实现。

为什么 Redis 要用跳表来实现有序集合，而不是红黑树？

Redis 中的有序集合支持的核心操作主要有下面这几个：

• 插入一个数据；
• 删除一个数据；
• 查找一个数据；
• 按照区间查找数据（比如查找值在 [100, 356] 之间的数据）；
• 迭代输出有序序列。

其中，插入、删除、查找以及迭代输出有序序列这几个操作，红黑树也可以完成，时间复杂度跟跳表是一样的。但是，按照区间来查找数据这个操作，红黑树的效率没有跳表高。

参考资料

• 数据结构与算法之美

Java 控制语句

Java 控制语句大致可分为三大类：

• 选择语句
  • if, else-if, else
  • switch
• 循环语句
  • while
  • do…while
  • for
  • foreach
• 中断语句
  • break
  • continue
  • return

选择语句

if 语句

if 语句会判断括号中的条件是否成立，如果成立则执行 if 语句中的代码块，否则跳过代码块继续执行。

语法

1
2
3

if(布尔表达式) {
   //如果布尔表达式为true将执行的语句
}

示例

1
2
3
4
5
6
7
8
9
10

public class IfDemo {
    public static void main(String args[]) {
        int x = 10;
        if (x < 20) {
            System.out.print("这是 if 语句");
        }
    }
}
// output:
// 这是 if 语句

if…else 语句

if 语句后面可以跟 else 语句，当 if 语句的布尔表达式值为 false 时，else 语句块会被执行。

语法

1
2
3
4
5

if(布尔表达式) {
   //如果布尔表达式的值为true
} else {
   //如果布尔表达式的值为false
}

示例

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

public class IfElseDemo {
    public static void main(String args[]) {
        int x = 30;
        if (x < 20) {
            System.out.print("这是 if 语句");
        } else {
            System.out.print("这是 else 语句");
        }
    }
}
// output:
// 这是 else 语句

if…else if…else 语句

• if 语句至多有 1 个 else 语句，else 语句在所有的 else if 语句之后。
• If 语句可以有若干个 else if 语句，它们必须在 else 语句之前。
• 一旦其中一个 else if 语句检测为 true，其他的 else if 以及 else 语句都将跳过执行。

语法

1
2
3
4
5
6
7
8
9

if (布尔表达式 1) {
   //如果布尔表达式 1的值为true执行代码
} else if (布尔表达式 2) {
   //如果布尔表达式 2的值为true执行代码
} else if (布尔表达式 3) {
   //如果布尔表达式 3的值为true执行代码
} else {
   //如果以上布尔表达式都不为true执行代码
}

示例

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

public class IfElseifElseDemo {
    public static void main(String args[]) {
        int x = 3;

        if (x == 1) {
            System.out.print("Value of X is 1");
        } else if (x == 2) {
            System.out.print("Value of X is 2");
        } else if (x == 3) {
            System.out.print("Value of X is 3");
        } else {
            System.out.print("This is else statement");
        }
    }
}
// output:
// Value of X is 3

嵌套的 if…else 语句

使用嵌套的 if else 语句是合法的。也就是说你可以在另一个 if 或者 else if 语句中使用 if 或者 else if 语句。

语法

1
2
3
4
5
6

if (布尔表达式 1) {
   ////如果布尔表达式 1的值为true执行代码
   if (布尔表达式 2) {
      ////如果布尔表达式 2的值为true执行代码
   }
}

示例

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

public class IfNestDemo {
    public static void main(String args[]) {
        int x = 30;
        int y = 10;

        if (x == 30) {
            if (y == 10) {
                System.out.print("X = 30 and Y = 10");
            }
        }
    }
}
// output:
// X = 30 and Y = 10

switch 语句

switch 语句判断一个变量与一系列值中某个值是否相等，每个值称为一个分支。

switch 语句有如下规则：

• switch 语句中的变量类型只能为 byte、short、int、char 或者 String。
• switch 语句可以拥有多个 case 语句。每个 case 后面跟一个要比较的值和冒号。
• case 语句中的值的数据类型必须与变量的数据类型相同，而且只能是常量或者字面常量。
• 当变量的值与 case 语句的值相等时，那么 case 语句之后的语句开始执行，直到 break 语句出现才会跳出 switch 语句。
• 当遇到 break 语句时，switch 语句终止。程序跳转到 switch 语句后面的语句执行。case 语句不必须要包含 break 语句。如果没有 break 语句出现，程序会继续执行下一条 case 语句，直到出现 break 语句。
• switch 语句可以包含一个 default 分支，该分支必须是 switch 语句的最后一个分支。default 在没有 case 语句的值和变量值相等的时候执行。default 分支不需要 break 语句。

语法

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

switch(expression){
    case value :
       //语句
       break; //可选
    case value :
       //语句
       break; //可选
    //你可以有任意数量的case语句
    default : //可选
       //语句
       break; //可选，但一般建议加上
}

示例

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

public class SwitchDemo {
    public static void main(String args[]) {
        char grade = 'C';

        switch (grade) {
        case 'A':
            System.out.println("Excellent!");
            break;
        case 'B':
        case 'C':
            System.out.println("Well done");
            break;
        case 'D':
            System.out.println("You passed");
        case 'F':
            System.out.println("Better try again");
            break;
        default:
            System.out.println("Invalid grade");
            break;
        }
        System.out.println("Your grade is " + grade);
    }
}
// output:
// Well done
// Your grade is C

循环语句

while 循环

只要布尔表达式为 true，while 循环体会一直执行下去。

语法

1
2
3

while( 布尔表达式 ) {
    //循环内容
}

示例

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

public class WhileDemo {
    public static void main(String args[]) {
        int x = 10;
        while (x < 20) {
            System.out.print("value of x : " + x);
            x++;
            System.out.print("\n");
        }
    }
}
// output:
// value of x : 10
// value of x : 11
// value of x : 12
// value of x : 13
// value of x : 14
// value of x : 15
// value of x : 16
// value of x : 17
// value of x : 18
// value of x : 19

do while 循环

对于 while 语句而言，如果不满足条件，则不能进入循环。但有时候我们需要即使不满足条件，也至少执行一次。

do while 循环和 while 循环相似，不同的是，do while 循环至少会执行一次。

语法

1
2
3

do {
    //代码语句
} while (布尔表达式);

布尔表达式在循环体的后面，所以语句块在检测布尔表达式之前已经执行了。 如果布尔表达式的值为 true，则语句块一直执行，直到布尔表达式的值为 false。

示例

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

public class DoWhileDemo {
    public static void main(String args[]) {
        int x = 10;

        do {
            System.out.print("value of x : " + x);
            x++;
            System.out.print("\n");
        } while (x < 20);
    }
}
// output:
// value of x:10
// value of x:11
// value of x:12
// value of x:13
// value of x:14
// value of x:15
// value of x:16
// value of x:17
// value of x:18
// value of x:19

for 循环

虽然所有循环结构都可以用 while 或者 do while 表示，但 Java 提供了另一种语句 —— for 循环，使一些循环结构变得更加简单。
for 循环执行的次数是在执行前就确定的。

语法

1
2
3

for (初始化; 布尔表达式; 更新) {
    //代码语句
}

• 最先执行初始化步骤。可以声明一种类型，但可初始化一个或多个循环控制变量，也可以是空语句。
• 然后，检测布尔表达式的值。如果为 true，循环体被执行。如果为 false，循环终止，开始执行循环体后面的语句。
• 执行一次循环后，更新循环控制变量。
• 再次检测布尔表达式。循环执行上面的过程。

示例

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

public class ForDemo {
    public static void main(String args[]) {
        for (int x = 10; x < 20; x = x + 1) {
            System.out.print("value of x : " + x);
            System.out.print("\n");
        }
    }
}
// output:
// value of x : 10
// value of x : 11
// value of x : 12
// value of x : 13
// value of x : 14
// value of x : 15
// value of x : 16
// value of x : 17
// value of x : 18
// value of x : 19

foreach 循环

Java5 引入了一种主要用于数组的增强型 for 循环。

语法

1
2
3

for (声明语句 : 表达式) {
    //代码句子
}

声明语句：声明新的局部变量，该变量的类型必须和数组元素的类型匹配。其作用域限定在循环语句块，其值与此时数组元素的值相等。

表达式：表达式是要访问的数组名，或者是返回值为数组的方法。

示例

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

public class ForeachDemo {
    public static void main(String args[]) {
        int[] numbers = { 10, 20, 30, 40, 50 };

        for (int x : numbers) {
            System.out.print(x);
            System.out.print(",");
        }

        System.out.print("\n");
        String[] names = { "James", "Larry", "Tom", "Lacy" };

        for (String name : names) {
            System.out.print(name);
            System.out.print(",");
        }
    }
}
// output:
// 10,20,30,40,50,
// James,Larry,Tom,Lacy,

中断语句

break 关键字

break 主要用在循环语句或者 switch 语句中，用来跳出整个语句块。

break 跳出最里层的循环，并且继续执行该循环下面的语句。

示例

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

public class BreakDemo {
    public static void main(String args[]) {
        int[] numbers = { 10, 20, 30, 40, 50 };

        for (int x : numbers) {
            if (x == 30) {
                break;
            }
            System.out.print(x);
            System.out.print("\n");
        }

        System.out.println("break 示例结束");
    }
}
// output:
// 10
// 20
// break 示例结束

continue 关键字

continue 适用于任何循环控制结构中。作用是让程序立刻跳转到下一次循环的迭代。在 for 循环中，continue 语句使程序立即跳转到更新语句。在 while 或者 do while 循环中，程序立即跳转到布尔表达式的判断语句。

示例

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

public class ContinueDemo {
    public static void main(String args[]) {
        int[] numbers = { 10, 20, 30, 40, 50 };

        for (int x : numbers) {
            if (x == 30) {
                continue;
            }
            System.out.print(x);
            System.out.print("\n");
        }
    }
}
// output:
// 10
// 20
// 40
// 50

return 关键字

跳出整个函数体，函数体后面的部分不再执行。

示例

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

public class ReturnDemo {
    public static void main(String args[]) {
        int[] numbers = { 10, 20, 30, 40, 50 };

        for (int x : numbers) {
            if (x == 30) {
                return;
            }
            System.out.print(x);
            System.out.print("\n");
        }

        System.out.println("return 示例结束");
    }
}
// output:
// 10
// 20

🔔 注意：请仔细体会一下 return 和 break 的区别。

最佳实践

• 选择分支特别多的情况下，switch 语句优于 if...else if...else 语句。
• switch 语句不要吝啬使用 default。
• switch 语句中的 default 要放在最后。
• foreach 循环优先于传统的 for 循环
• 不要循环遍历容器元素，然后删除特定元素。正确姿势应该是遍历容器的迭代器（Iterator），删除元素。

参考资料

• Java 编程思想
• Java 核心技术（卷 1）

深入理解 Java 泛型

什么是泛型

Java 泛型（generics）是 JDK 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

public class NoGenericsDemo {
    public static void main(String[] args) {
        List list = new ArrayList<>();
        list.add("abc");
        list.add(18);
        list.add(new double[] {1.0, 2.0});
        Object obj1 = list.get(0);
        Object obj2 = list.get(1);
        Object obj3 = list.get(2);
        System.out.println("obj1 = [" + obj1 + "]");
        System.out.println("obj2 = [" + obj2 + "]");
        System.out.println("obj3 = [" + obj3 + "]");

        int num1 = (int)list.get(0);
        int num2 = (int)list.get(1);
        int num3 = (int)list.get(2);
        System.out.println("num1 = [" + num1 + "]");
        System.out.println("num2 = [" + num2 + "]");
        System.out.println("num3 = [" + num3 + "]");
    }
}
// Output:
// obj1 = [abc]
// obj2 = [18]
// obj3 = [[D@47089e5f]
// Exception in thread "main" java.lang.ClassCastException: java.lang.String cannot be cast to java.lang.Integer
// at io.github.dunwu.javacore.generics.NoGenericsDemo.main(NoGenericsDemo.java:23)

示例说明：

在上面的示例中，List 容器没有指定存储数据类型，这种情况下，可以向 List 添加任意类型数据，编译器不会做类型检查，而是默默的将所有数据都转为 Object。

假设，最初我们希望向 List 存储的是整形数据，假设，某个家伙不小心存入了其他数据类型。当你试图从容器中取整形数据时，由于 List 当成 Object 类型来存储，你不得不使用类型强制转换。在运行时，才会发现 List 中数据不存储一致的问题，这就为程序运行带来了很大的风险（无形伤害最为致命）。

引入泛型机制，正是为了解决这种类型安全问题。“泛型”提供了编译时类型安全检测机制，该机制会在编译时检测到非法的类型。

泛型具有以下优点：

• 编译时的强类型检查 - 泛型要求在声明时指定实际数据类型，Java 编译器在编译时会对泛型代码做强类型检查，并在代码违反类型安全时发出告警。早发现，早治理，把隐患扼杀于摇篮，在编译时发现并修复错误所付出的代价远比在运行时小。

• 避免了类型转换

未使用泛型：

1
2
3

List list = new ArrayList();
list.add("hello");
String s = (String) list.get(0);

使用泛型：

1
2
3

List<String> list = new ArrayList<String>();
list.add("hello");
String s = list.get(0);   // no cast

• 泛型编程可以实现通用算法 - 通过使用泛型，程序员可以实现通用算法，这些算法可以处理不同类型的集合，可以自定义，并且类型安全且易于阅读。

泛型声明

“泛型类型”是被参数化的类或接口。

泛型类

泛型类的语法形式：

1

class name<T1, T2, ..., Tn> { /* ... */ }

泛型类的声明和非泛型类的声明类似，除了在类名后面添加了类型参数声明部分。由尖括号（<>）分隔的类型参数部分跟在类名后面。它指定类型参数（也称为类型变量）T1，T2，…和 Tn。

一般将泛型中的类名称为原型，而将 <> 指定的参数称为类型参数。

• 未应用泛型的类

在泛型出现之前，如果一个类想持有一个可以为任意类型的数据，只能使用 Object 做类型转换。示例如下：

1
2
3
4
5
6
7
8
9
10
11

public class Info {
	private Object value;

	public Object getValue() {
		return value;
	}

	public void setValue(Object value) {
		this.value = value;
	}
}

• 单类型参数的泛型类

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

public class Info<T> {
    private T value;

    public Info() { }

    public Info(T value) {
        this.value = value;
    }

    public T getValue() {
        return value;
    }

    public void setValue(T value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Info{" + "value=" + value + '}';
    }
}

public class GenericsClassDemo01 {
    public static void main(String[] args) {
        Info<Integer> info = new Info<>();
        info.setValue(10);
        System.out.println(info.getValue());

        Info<String> info2 = new Info<>();
        info2.setValue("xyz");
        System.out.println(info2.getValue());
    }
}
// Output:
// 10
// xyz

在上面的例子中，在初始化一个泛型类时，使用 <> 指定了内部具体类型，在编译时就会根据这个类型做强类型检查。

实际上，不使用 <> 指定内部具体类型，语法上也是支持的（不推荐这么做），如下所示：

1
2
3
4
5
6
7

public static void main(String[] args) {
    Info info = new Info();
    info.setValue(10);
    System.out.println(info.getValue());
    info.setValue("abc");
    System.out.println(info.getValue());
}

示例说明：

上面的例子，不会产生编译错误，也能正常运行。但这样的调用就失去泛型类型的优势。

• 多个类型参数的泛型类

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

public class MyMap<K,V> {
    private K key;
    private V value;

    public MyMap(K key, V value) {
        this.key = key;
        this.value = value;
    }

    @Override
    public String toString() {
        return "MyMap{" + "key=" + key + ", value=" + value + '}';
    }
}

public class GenericsClassDemo02 {
    public static void main(String[] args) {
        MyMap<Integer, String> map = new MyMap<>(1, "one");
        System.out.println(map);
    }
}
// Output:
// MyMap{key=1, value=one}

• 泛型类的类型嵌套

1
2
3
4
5
6
7
8
9

public class GenericsClassDemo03 {
    public static void main(String[] args) {
        Info<String> info = new Info("Hello");
        MyMap<Integer, Info<String>> map = new MyMap<>(1, info);
        System.out.println(map);
    }
}
// Output:
// MyMap{key=1, value=Info{value=Hello}}

泛型接口

接口也可以声明泛型。

泛型接口语法形式：

1
2
3

public interface Content<T> {
    T text();
}

泛型接口有两种实现方式：

• 实现接口的子类明确声明泛型类型

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

public class GenericsInterfaceDemo01 implements Content<Integer> {
    private int text;

    public GenericsInterfaceDemo01(int text) {
        this.text = text;
    }

    @Override
    public Integer text() { return text; }

    public static void main(String[] args) {
        GenericsInterfaceDemo01 demo = new GenericsInterfaceDemo01(10);
        System.out.print(demo.text());
    }
}
// Output:
// 10

• 实现接口的子类不明确声明泛型类型

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

public class GenericsInterfaceDemo02<T> implements Content<T> {
    private T text;

    public GenericsInterfaceDemo02(T text) {
        this.text = text;
    }

    @Override
    public T text() { return text; }

    public static void main(String[] args) {
        GenericsInterfaceDemo02<String> gen = new GenericsInterfaceDemo02<>("ABC");
        System.out.print(gen.text());
    }
}
// Output:
// ABC

泛型方法

泛型方法是引入其自己的类型参数的方法。泛型方法可以是普通方法、静态方法以及构造方法。

泛型方法语法形式如下：

1

public <T> T func(T obj) {}

是否拥有泛型方法，与其所在的类是否是泛型没有关系。

泛型方法的语法包括一个类型参数列表，在尖括号内，它出现在方法的返回类型之前。对于静态泛型方法，类型参数部分必须出现在方法的返回类型之前。类型参数能被用来声明返回值类型，并且能作为泛型方法得到的实际类型参数的占位符。

使用泛型方法的时候，通常不必指明类型参数，因为编译器会为我们找出具体的类型，这称为“类型参数推断（type argument inference）”。类型推断只对赋值操作有效，其他时候并不起作用。如果将一个返回类型为 T 的泛型方法调用的结果作为参数，传递给另一个方法，这时编译器并不会执行推断。编译器会认为：调用泛型方法后，其返回值被赋给一个 Object 类型的变量。

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

public class GenericsMethodDemo01 {
    public static <T> void printClass(T obj) {
        System.out.println(obj.getClass().toString());
    }

    public static void main(String[] args) {
        printClass("abc");
        printClass(10);
    }
}
// Output:
// class java.lang.String
// class java.lang.Integer

泛型方法中也可以使用可变参数列表。示例如下：

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

public class GenericVarargsMethodDemo {
    public static <T> List<T> makeList(T... args) {
        List<T> result = new ArrayList<T>();
        Collections.addAll(result, args);
        return result;
    }

    public static void main(String[] args) {
        List<String> ls = makeList("A");
        System.out.println(ls);
        ls = makeList("A", "B", "C");
        System.out.println(ls);
    }
}
// Output:
// [A]
// [A, B, C]

泛型要点

类型擦除

Java 语言引入泛型是为了在编译时提供更严格的类型检查，并支持泛型编程。不同于 C++ 的模板机制，Java 泛型是使用“类型擦除”来实现的，使用泛型时，任何具体的类型信息都被擦除了。

那么，类型擦除做了什么呢？它做了以下工作：

• 把泛型中的所有类型参数替换为 Object，如果指定类型边界，则使用类型边界来替换。因此，生成的字节码仅包含普通的类，接口和方法。
• 擦除出现的类型声明，即去掉 <> 的内容。比如 T get() 方法声明就变成了 Object get() ；List<String> 就变成了 List。如有必要，插入类型转换以保持类型安全。
• 生成桥接方法以保留扩展泛型类型中的多态性。类型擦除确保不为参数化类型创建新类；因此，泛型不会产生运行时开销。

让我们来看一个示例：

1
2
3
4
5
6
7
8
9
10
11

public class GenericsErasureTypeDemo {
    public static void main(String[] args) {
        List<Object> list1 = new ArrayList<Object>();
        List<String> list2 = new ArrayList<String>();
        System.out.println(list1.getClass());
        System.out.println(list2.getClass());
    }
}
// Output:
// class java.util.ArrayList
// class java.util.ArrayList

示例说明：

上面的例子中，虽然指定了不同的类型参数，但是 list1 和 list2 的类信息却是一样的。

这是因为：使用泛型时，任何具体的类型信息都被擦除了。这意味着：ArrayList<Object> 和 ArrayList<String> 在运行时，JVM 将它们视为同一类型。

Java 泛型的实现方式不太优雅，但这是因为泛型是在 JDK5 时引入的，为了兼容老代码，必须在设计上做一定的折中。

泛型和继承

泛型不能用于显式地引用运行时类型的操作之中（例如：转型、instanceof 操作和 new 表达式），因为所有关于参数的类型信息都丢失了。当你在编写泛型代码时，必须时刻提醒自己，你只是看起来好像拥有有关参数的类型信息而已。

正是由于泛型时基于类型擦除实现的，所以，泛型类型无法向上转型。

向上转型是指用子类实例去初始化父类，这是面向对象中多态的重要表现。

Integer 继承了 Object；ArrayList 继承了 List；但是 List<Interger> 却并非继承了 List<Object>。

这是因为，泛型类并没有自己独有的 Class 类对象。比如：并不存在 List<Object>.class 或是 List<Interger>.class，Java 编译器会将二者都视为 List.class。

1
2

List<Integer> list = new ArrayList<>();
List<Object> list2 = list; // Erorr

类型边界

有时您可能希望限制可在参数化类型中用作类型参数的类型。“类型边界”可以对泛型的类型参数设置限制条件。例如，对数字进行操作的方法可能只想接受 Number 或其子类的实例。

要声明有界类型参数，请列出类型参数的名称，然后是 extends 关键字，后跟其限制类或接口。

类型边界的语法形式如下：

1

<T extends XXX>

示例：

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

public class GenericsExtendsDemo01 {
    static <T extends Comparable<T>> T max(T x, T y, T z) {
        T max = x; // 假设x是初始最大值
        if (y.compareTo(max) > 0) {
            max = y; //y 更大
        }
        if (z.compareTo(max) > 0) {
            max = z; // 现在 z 更大
        }
        return max; // 返回最大对象
    }

    public static void main(String[] args) {
        System.out.println(max(3, 4, 5));
        System.out.println(max(6.6, 8.8, 7.7));
        System.out.println(max("pear", "apple", "orange"));
    }
}
// Output:
// 5
// 8.8
// pear

示例说明：

上面的示例声明了一个泛型方法，类型参数 T extends Comparable<T> 表明传入方法中的类型必须实现了 Comparable 接口。

类型边界可以设置多个，语法形式如下：

1

<T extends B1 & B2 & B3>

🔔 注意：extends 关键字后面的第一个类型参数可以是类或接口，其他类型参数只能是接口。

示例：

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

public class GenericsExtendsDemo02 {
    static class A { /* ... */ }
    interface B { /* ... */ }
    interface C { /* ... */ }
    static class D1 <T extends A & B & C> { /* ... */ }
    static class D2 <T extends B & A & C> { /* ... */ } // 编译报错
    static class E extends A implements B, C { /* ... */ }

    public static void main(String[] args) {
        D1<E> demo1 = new D1<>();
        System.out.println(demo1.getClass().toString());
        D1<String> demo2 = new D1<>(); // 编译报错
    }
}

类型通配符

“类型通配符”一般使用 ? 代替具体的类型参数。例如 List<?> 在逻辑上是 List<String> ，List<Integer> 等所有 List<具体类型实参> 的父类。

上界通配符

可以使用“上界通配符”来缩小类型参数的类型范围。

它的语法形式为：<? extends Number>

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

public class GenericsUpperBoundedWildcardDemo {
    public static double sumOfList(List<? extends Number> list) {
        double s = 0.0;
        for (Number n : list) {
            s += n.doubleValue();
        }
        return s;
    }

    public static void main(String[] args) {
        List<Integer> li = Arrays.asList(1, 2, 3);
        System.out.println("sum = " + sumOfList(li));
    }
}
// Output:
// sum = 6.0

下界通配符

“下界通配符”将未知类型限制为该类型的特定类型或超类类型。

🔔 注意：上界通配符和下界通配符不能同时使用。

它的语法形式为：<? super Number>

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

public class GenericsLowerBoundedWildcardDemo {
    public static void addNumbers(List<? super Integer> list) {
        for (int i = 1; i <= 5; i++) {
            list.add(i);
        }
    }

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        addNumbers(list);
        System.out.println(Arrays.deepToString(list.toArray()));
    }
}
// Output:
// [1, 2, 3, 4, 5]

无界通配符

无界通配符有两种应用场景：

• 可以使用 Object 类中提供的功能来实现的方法。
• 使用不依赖于类型参数的泛型类中的方法。

语法形式：<?>

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

public class GenericsUnboundedWildcardDemo {
    public static void printList(List<?> list) {
        for (Object elem : list) {
            System.out.print(elem + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        List<Integer> li = Arrays.asList(1, 2, 3);
        List<String> ls = Arrays.asList("one", "two", "three");
        printList(li);
        printList(ls);
    }
}
// Output:
// 1 2 3
// one two three

通配符和向上转型

前面，我们提到：泛型不能直接向上转型；但是，我们可以通过使用通配符来间接向上转型。

1
2
3
4
5
6
7
8
9

public class GenericsWildcardDemo {
    public static void main(String[] args) {
        List<Integer> intList = new ArrayList<>();
        List<Number> numList = intList;  // Error

        List<? extends Integer> intList2 = new ArrayList<>();
        List<? extends Number> numList2 = intList2;  // OK
    }
}

扩展阅读：Oracle 泛型文档

泛型的约束

• 泛型类型的类型参数不能是值类型

1

Pair<int, char> p = new Pair<>(8, 'a');  // 编译错误

• 不能创建类型参数的实例

1
2
3
4

public static <E> void append(List<E> list) {
    E elem = new E();  // 编译错误
    list.add(elem);
}

• 不能声明类型为类型参数的静态成员

1
2
3
4
5

public class MobileDevice<T> {
    private static T os; // error

    // ...
}

• 类型参数不能使用类型转换或 instanceof

1
2
3
4
5

public static <E> void rtti(List<E> list) {
    if (list instanceof ArrayList<Integer>) {  // 编译错误
        // ...
    }
}

1
2

List<Integer> li = new ArrayList<>();
List<Number>  ln = (List<Number>) li;  // 编译错误

• 不能创建类型参数的数组

1

List<Integer>[] arrayOfLists = new List<Integer>[2];  // 编译错误

• 不能创建、catch 或 throw 参数化类型对象

1
2
3
4
5

// Extends Throwable indirectly
class MathException<T> extends Exception { /* ... */ }    // 编译错误

// Extends Throwable directly
class QueueFullException<T> extends Throwable { /* ... */ // 编译错误

1
2
3
4
5
6
7
8

public static <T extends Exception, J> void execute(List<J> jobs) {
    try {
        for (J job : jobs)
            // ...
    } catch (T e) {   // compile-time error
        // ...
    }
}

• 仅仅是泛型类相同，而类型参数不同的方法不能重载

1
2
3
4

public class Example {
    public void print(Set<String> strSet) { }
    public void print(Set<Integer> intSet) { } // 编译错误
}

泛型最佳实践

泛型命名

Java 泛型有一些约定俗成的命名：

• E - Element
• K - Key
• N - Number
• T - Type
• V - Value
• S、U、V - 2nd, 3rd, 4th types

使用泛型的建议

• 消除类型检查告警
• List 优先于数组
• 优先考虑使用泛型来提高代码通用性
• 优先考虑泛型方法来限定泛型的范围
• 利用有限制通配符来提升 API 的灵活性
• 优先考虑类型安全的异构容器

参考资料

• Java 编程思想
• Java 核心技术（卷 1）
• Effective java
• Oracle 泛型文档
• Java 泛型详解

ShardingSphere 简介

简介

shardingsphere-jdbc 定位为轻量级 Java 框架，在 Java 的 JDBC 层提供的额外服务。 它使用客户端直连数据库，以 jar 包形式提供服务，无需额外部署和依赖，可理解为增强版的 JDBC 驱动，完全兼容 JDBC 和各种 ORM 框架。

• 适用于任何基于 JDBC 的 ORM 框架，如：JPA, Hibernate, Mybatis, Spring JDBC Template 或直接使用 JDBC。
• 支持任何第三方的数据库连接池，如：DBCP, C3P0, BoneCP, Druid, HikariCP 等。
• 支持任意实现 JDBC 规范的数据库，目前支持 MySQL，Oracle，SQLServer，PostgreSQL 以及任何遵循 SQL92 标准的数据库。

ShardingSphere 组件

ShardingSphere 是一套开源的分布式数据库中间件解决方案组成的生态圈，它由 Sharding-JDBC、Sharding-Proxy 和 Sharding-Sidecar（计划中）这 3 款相互独立的产品组成。 他们均提供标准化的数据分片、分布式事务和数据库治理功能，可适用于如 Java 同构、异构语言、云原生等各种多样化的应用场景。

ShardingSphere-JDBC

定位为轻量级 Java 框架，在 Java 的 JDBC 层提供的额外服务。 它使用客户端直连数据库，以 jar 包形式提供服务，无需额外部署和依赖，可理解为增强版的 JDBC 驱动，完全兼容 JDBC 和各种 ORM 框架。

• 适用于任何基于 JDBC 的 ORM 框架，如：JPA, Hibernate, Mybatis, Spring JDBC Template 或直接使用 JDBC。
• 支持任何第三方的数据库连接池，如：DBCP, C3P0, BoneCP, Druid, HikariCP 等。
• 支持任意实现 JDBC 规范的数据库，目前支持 MySQL，Oracle，SQLServer，PostgreSQL 以及任何遵循 SQL92 标准的数据库。

Sharding-Proxy

定位为透明化的数据库代理端，提供封装了数据库二进制协议的服务端版本，用于完成对异构语言的支持。 目前提供 MySQL 和 PostgreSQL 版本，它可以使用任何兼容 MySQL/PostgreSQL 协议的访问客户端(如：MySQL Command Client, MySQL Workbench, Navicat 等)操作数据，对 DBA 更加友好。

• 向应用程序完全透明，可直接当做 MySQL/PostgreSQL 使用。
• 适用于任何兼容 MySQL/PostgreSQL 协议的的客户端。

Sharding-Sidecar（TODO）

定位为 Kubernetes 的云原生数据库代理，以 Sidecar 的形式代理所有对数据库的访问。 通过无中心、零侵入的方案提供与数据库交互的的啮合层，即 Database Mesh，又可称数据库网格。

Database Mesh 的关注重点在于如何将分布式的数据访问应用与数据库有机串联起来，它更加关注的是交互，是将杂乱无章的应用与数据库之间的交互进行有效地梳理。 使用 Database Mesh，访问数据库的应用和数据库终将形成一个巨大的网格体系，应用和数据库只需在网格体系中对号入座即可，它们都是被啮合层所治理的对象。

混合架构

ShardingSphere-JDBC 采用无中心化架构，适用于 Java 开发的高性能的轻量级 OLTP 应用；ShardingSphere-Proxy 提供静态入口以及异构语言的支持，适用于 OLAP 应用以及对分片数据库进行管理和运维的场景。

Apache ShardingSphere 是多接入端共同组成的生态圈。 通过混合使用 ShardingSphere-JDBC 和 ShardingSphere-Proxy，并采用同一注册中心统一配置分片策略，能够灵活的搭建适用于各种场景的应用系统，使得架构师更加自由地调整适合与当前业务的最佳系统架构。

功能列表

数据分片

• 分库 & 分表
• 读写分离
• 分片策略定制化
• 无中心化分布式主键

分布式事务

• 标准化事务接口
• XA 强一致事务
• 柔性事务

数据库治理

• 分布式治理
• 弹性伸缩
• 可视化链路追踪
• 数据加密

快速入门

引入 maven 依赖

1
2
3
4
5

<dependency>
    <groupId>org.apache.shardingsphere</groupId>
    <artifactId>shardingsphere-jdbc-core</artifactId>
    <version>${latest.release.version}</version>
</dependency>

注意：请将 ${latest.release.version} 更改为实际的版本号。

规则配置

ShardingSphere-JDBC 可以通过 Java，YAML，Spring 命名空间和 Spring Boot Starter 这 4 种方式进行配置，开发者可根据场景选择适合的配置方式。 详情请参见配置手册。

创建数据源

通过 ShardingSphereDataSourceFactory 工厂和规则配置对象获取 ShardingSphereDataSource。 该对象实现自 JDBC 的标准 DataSource 接口，可用于原生 JDBC 开发，或使用 JPA, MyBatis 等 ORM 类库。

1

DataSource dataSource = ShardingSphereDataSourceFactory.createDataSource(dataSourceMap, configurations, properties);

概念和功能

单一数据节点难于满足互联网的海量数据场景。

从性能方面来说，由于关系型数据库大多采用 B+ 树类型的索引，在数据量超过阈值的情况下，索引深度的增加也将使得磁盘访问的 IO 次数增加，进而导致查询性能的下降；同时，高并发访问请求也使得集中式数据库成为系统的最大瓶颈。

在传统的关系型数据库无法满足互联网场景需要的情况下，将数据存储至原生支持分布式的 NoSQL 的尝试越来越多。 但 NoSQL 对 SQL 的不兼容性以及生态圈的不完善，使得它们在与关系型数据库的博弈中始终无法完成致命一击，而关系型数据库的地位却依然不可撼动。

数据分片指按照某个维度将存放在单一数据库中的数据分散地存放至多个数据库或表中以达到提升性能瓶颈以及可用性的效果。数据分片的有效手段是对关系型数据库进行分库和分表。分库和分表均可以有效的避免由数据量超过可承受阈值而产生的查询瓶颈。 除此之外，分库还能够用于有效的分散对数据库单点的访问量；分表虽然无法缓解数据库压力，但却能够提供尽量将分布式事务转化为本地事务的可能，一旦涉及到跨库的更新操作，分布式事务往往会使问题变得复杂。 使用多主多从的分片方式，可以有效的避免数据单点，从而提升数据架构的可用性。

通过分库和分表进行数据的拆分来使得各个表的数据量保持在阈值以下，以及对流量进行疏导应对高访问量，是应对高并发和海量数据系统的有效手段。 数据分片的拆分方式又分为垂直分片和水平分片。

垂直分片

按照业务拆分的方式称为垂直分片，又称为纵向拆分，它的核心理念是专库专用。 在拆分之前，一个数据库由多个数据表构成，每个表对应着不同的业务。而拆分之后，则是按照业务将表进行归类，分布到不同的数据库中，从而将压力分散至不同的数据库。 下图展示了根据业务需要，将用户表和订单表垂直分片到不同的数据库的方案。

垂直分片往往需要对架构和设计进行调整。通常来讲，是来不及应对互联网业务需求快速变化的；而且，它也并无法真正的解决单点瓶颈。 垂直拆分可以缓解数据量和访问量带来的问题，但无法根治。如果垂直拆分之后，表中的数据量依然超过单节点所能承载的阈值，则需要水平分片来进一步处理。

水平分片

水平分片又称为横向拆分。 相对于垂直分片，它不再将数据根据业务逻辑分类，而是通过某个字段（或某几个字段），根据某种规则将数据分散至多个库或表中，每个分片仅包含数据的一部分。 例如：根据主键分片，偶数主键的记录放入 0 库（或表），奇数主键的记录放入 1 库（或表），如下图所示。

水平分片从理论上突破了单机数据量处理的瓶颈，并且扩展相对自由，是分库分表的标准解决方案。

数据分片带来的问题

• 数据路由：需要知道数据需要从哪个具体的数据库的分表中获取。
• SQL 不兼容：分表导致表名称的修改，或者分页、排序、聚合、分组等操作的不正确处理。
• 跨库事务：合理采用分表，可以在降低单表数据量的情况下，尽量使用本地事务，善于使用同库不同表可有效避免分布式事务带来的麻烦。 在不能避免跨库事务的场景，有些业务仍然需要保持事务的一致性。 而基于 XA 的分布式事务由于在并发度高的场景中性能无法满足需要，并未被互联网巨头大规模使用，他们大多采用最终一致性的柔性事务代替强一致事务。

ShardingSphere 内核剖析

ShardingSphere 的 3 个产品的数据分片主要流程是完全一致的。 核心由 SQL 解析 => 执行器优化 => SQL 路由 => SQL 改写 => SQL 执行 => 结果归并的流程组成。

• QL 解析：分为词法解析和语法解析。 先通过词法解析器将 SQL 拆分为一个个不可再分的单词。再使用语法解析器对 SQL 进行理解，并最终提炼出解析上下文。 解析上下文包括表、选择项、排序项、分组项、聚合函数、分页信息、查询条件以及可能需要修改的占位符的标记。
• 执行器优化：合并和优化分片条件，如 OR 等。
• SQL 路由：根据解析上下文匹配用户配置的分片策略，并生成路由路径。目前支持分片路由和广播路由。
• SQL 改写：将 SQL 改写为在真实数据库中可以正确执行的语句。SQL 改写分为正确性改写和优化改写。
• SQL 执行：通过多线程执行器异步执行。
• 结果归并：将多个执行结果集归并以便于通过统一的 JDBC 接口输出。结果归并包括流式归并、内存归并和使用装饰模式的追加归并这几种方式。

解析引擎

抽象语法树

解析过程分为词法解析和语法解析。 词法解析器用于将 SQL 拆解为不可再分的原子符号，称为 Token。并根据不同数据库方言所提供的字典，将其归类为关键字，表达式，字面量和操作符。 再使用语法解析器将 SQL 转换为抽象语法树。

例如，以下 SQL：

1

SELECT id, name FROM t_user WHERE status = 'ACTIVE' AND age > 18

解析之后的为抽象语法树见下图。

为了便于理解，抽象语法树中的关键字的 Token 用绿色表示，变量的 Token 用红色表示，灰色表示需要进一步拆分。

最后，通过对抽象语法树的遍历去提炼分片所需的上下文，并标记有可能需要改写的位置。 供分片使用的解析上下文包含查询选择项（Select Items）、表信息（Table）、分片条件（Sharding Condition）、自增主键信息（Auto increment Primary Key）、排序信息（Order By）、分组信息（Group By）以及分页信息（Limit、Rownum、Top）。 SQL 的一次解析过程是不可逆的，一个个 Token 按 SQL 原本的顺序依次进行解析，性能很高。 考虑到各种数据库 SQL 方言的异同，在解析模块提供了各类数据库的 SQL 方言字典。

SQL 解析引擎

SQL 解析作为分库分表类产品的核心，其性能和兼容性是最重要的衡量指标。 ShardingSphere 的 SQL 解析器经历了 3 代产品的更新迭代。

第一代 SQL 解析器为了追求性能与快速实现，在 1.4.x 之前的版本使用 Druid 作为 SQL 解析器。经实际测试，它的性能远超其它解析器。

第二代 SQL 解析器从 1.5.x 版本开始，ShardingSphere 采用完全自研的 SQL 解析引擎。 由于目的不同，ShardingSphere 并不需要将 SQL 转为一颗完全的抽象语法树，也无需通过访问器模式进行二次遍历。它采用对 SQL 半理解的方式，仅提炼数据分片需要关注的上下文，因此 SQL 解析的性能和兼容性得到了进一步的提高。

第三代 SQL 解析器则从 3.0.x 版本开始，ShardingSphere 尝试使用 ANTLR 作为 SQL 解析的引擎，并计划根据 DDL -> TCL -> DAL –> DCL -> DML –>DQL 这个顺序，依次替换原有的解析引擎，目前仍处于替换迭代中。 使用 ANTLR 的原因是希望 ShardingSphere 的解析引擎能够更好的对 SQL 进行兼容。对于复杂的表达式、递归、子查询等语句，虽然 ShardingSphere 的分片核心并不关注，但是会影响对于 SQL 理解的友好度。 经过实例测试，ANTLR 解析 SQL 的性能比自研的 SQL 解析引擎慢 3-10 倍左右。为了弥补这一差距，ShardingSphere 将使用 PreparedStatement 的 SQL 解析的语法树放入缓存。 因此建议采用 PreparedStatement 这种 SQL 预编译的方式提升性能。

第三代 SQL 解析引擎的整体结构划分如下图所示。

参考资料

• shardingsphere Github
• shardingsphere 官方文档

MongoDB CRUD

::: info 概述

CRUD 由英文单词 Create, Read, Update, Delete 的首字母组成，即增删改查。

本文通过介绍基本的 MongoDB CRUD 方法，向读者呈现如何访问 MongoDB 数据。

:::

MongoDB 索引

::: info 概述

索引通常能够极大的提高查询的效率。如果没有索引，MongoDB 在读取数据时必须扫描 collection 中的每个 document 并选取那些符合查询条件的记录。这种扫描全集合的查询是非常低效的，特别是在处理大量的数据时。查询可能要花费几十秒甚至几分钟，这种性能开销是不可接受的。索引可提高查询性能，但添加索引会影响写入操作的性能。对于写入读取率高的集合，由于每次插入操作都必须同时更新所有索引，因此会带来较高的索引成本。

本文介绍了 MongoDB 的基本索引操作、索引类型，和设置索引的策略。掌握了 MongoDB 索引的要点，有助于提高访问 MongoDB 数据的效率。

:::

MongoDB 聚合

::: info 概述

聚合操作处理多个文档并返回计算结果。可以使用聚合操作来：

• 将多个文档中的值组合在一起。
• 对分组数据执行操作，返回单一结果。
• 分析一段时间内的数据变化。

在 MongoDB 中，支持以下聚合方式：

• 聚合管道，这是执行聚合的首选方法。
• 单一目的聚合方法，这些方法很简单，但缺乏聚合管道的功能。
• Map-Reduce，从 MongoDB 5.0 开始，Map-Reduce 已被弃用。聚合管道提供的性能和可用性比 Map-Reduce 更优越。

本文将逐一介绍这三种聚合方式的要点和使用方法。

:::

MongoDB 事务

::: info 概述

通俗的说，事务将多个读、写操作捆绑在一起成为一个逻辑操作单元。事务中的所有读写是一个执行的整体，整个事务要么成功（提交）、要么失败（中止或回滚）。如果失败，应用程序可以安全地重试。这样，由于不需要担心部分失败的情况（无论出于任何原因），应用层的错误处理就变得简单很多。

大多数 NoSQL 只能部分支持事务，甚至完全不支持事务。但是，MongoDB 支持 ACID 事务，这是它的一大优势。

本文主要介绍了 MongoDB 对于事务的支持力度，以及如何应用事务。

:::

MongoDB 分片

::: info 概述

分区通常是这样定义的，即每一条数据（或者每条记录，每行或每个文档）只属于某个特定分区。实际上，每个分区都可以视为一个完整的小型数据库，虽然数据库可能存在一些跨分区的操作。

在不同系统中，分区有着不同的称呼，例如它对应于 MongoDB, Elasticsearch 和 SolrCloud 中的 shard, HBase 的 region, Bigtable 中的 tablet, Cassandra 和 Riak 中的 vnode ，以及 Couch base 中的 vBucket。

数据量如果太大，单台机器进行存储和处理就会成为瓶颈，因此需要引入数据分区机制。分区的目地是通过多台机器均匀分布数据和查询负载，避免出现热点。这需要选择合适的数据分区方案，在节点添加或删除时重新动态平衡分区。

分区通常与复制结合使用，即每个分区在多个节点都存有副本。这意味着某条记录属于特定的分区，而同样的内容会保存在不同的节点上以提高系统的容错性。一个节点上可能存储了多个分区。每个分区都有自己的主副本，例如被分配给某节点，而从副本则分配在其他一些节点。一个节点可能既是某些分区的主副本，同时又是其他分区的从副本。

:::

MongoDB 复制

::: info 概述

复制主要指通过网络在多台机器上保存相同数据的副本。

复制数据，可能出于各种各样的原因：

• 提高可用性 - 当部分组件出现位障，系统依然可以继续工作，系统依然可以继续工作。
• 降低访问延迟 - 使数据在地理位置上更接近用户。
• 提高读吞吐量 - 扩展至多台机器以同时提供数据访问服务。

综上可知，复制是所有分布式系统的核心特性，是高可用的重要保证。

MongoDB 本身是一个分布式数据库，自然也需要具备复制的能力。MongoDB 复制采用了经典的主从架构。所有的写入操作都发送到主节点，由主节点负责将数据更改事件发送到从节点，每个从节点都可以接收读请求。

本文将逐一阐述 MongoDB 复制的各个要点，以及如何基于复制来保证 MongoDB 的高可用。

:::