海量数据处理

如何从海量的 URL 中找出相同的 URL？

问题描述

给定 a、b 两个文件，各存放 50 亿个 URL，每个 URL 各占 64B，内存限制是 4G。请找出 a、b 两个文件共同的 URL。

解决思路

每个 URL 占 64B，那么 50 亿个 URL 占用的空间大小约为 320GB。

$$5,000,000,000 * 64 B ≈ 5 GB * 64 = 320 GB$$

由于内存大小只有 4G，因此，我们不可能一次性把所有 URL 加载到内存中处理。对于这种类型的题目，一般采用分治策略，即：把一个文件中的 URL 按照某个特征划分为多个小文件，使得每个小文件大小不超过 4G，这样就可以把这个小文件读到内存中进行处理了。

思路如下：

首先遍历文件 a，对遍历到的 URL 求 hash(URL) % 1000，根据计算结果把遍历到的 URL 存储到 a0, a1, a2, …, a999，这样每个大小约为 300MB。使用同样的方法遍历文件 b，把文件 b 中的 URL 分别存储到文件 b0, b1, b2, …, b999 中。这样处理过后，所有可能相同的 URL 都在对应的小文件中，即 a0 对应 b0, …, a999 对应 b999，不对应的小文件不可能有相同的 URL。那么接下来，我们只需要求出这 1000 对小文件中相同的 URL 就好了。

接着遍历 ai( i∈[0,999])，把 URL 存储到一个 HashSet 集合中。然后遍历 bi 中每个 URL，看在 HashSet 集合中是否存在，若存在，说明这就是共同的 URL，可以把这个 URL 保存到一个单独的文件中。

方案总结

• 分而治之，进行哈希取余；
• 对每个子文件进行 HashSet 统计。

如何从海量数据中找出高频词？

问题描述

有一个 1GB 大小的文件，文件里每一行是一个词，每个词的大小不超过 16B，内存大小限制是 1MB，要求返回频数最高的 100 个词(Top 100)。

解决思路

由于内存限制，无法直接将大文件的所有词一次读到内存中。因此，可以采用分治策略，把一个大文件分解成多个小文件，保证每个文件的大小小于 1MB，进而直接将单个小文件读取到内存中进行处理。

思路如下：

首先遍历大文件，对遍历到的每个词 x，执行 hash(x) % 5000，将结果为 i 的词存放到文件 Ai 中。遍历结束后，我们可以得到 5000 个小文件。每个小文件的大小为 200KB 左右。如果有的小文件大小仍然超过 1MB，则采用同样的方式继续进行分解。

接着统计每个小文件中出现频数最高的 100 个词。最简单的方式是使用 HashMap 来实现。其中 key 为词，value 为该词出现的频率。具体方法是：对于遍历到的词 x，如果在 map 中不存在，则执行 map.put(x, 1) 若存在，则执行 map.put(x, map.get(x)+1)，将该词频数加 1。

上面我们统计了每个小文件单词出现的频数。接下来，我们可以通过维护一个小顶堆来找出所有词中出现频数最高的 100 个。具体方法是：依次遍历每个小文件，构建一个小顶堆，堆大小为 100。如果遍历到的词的出现次数大于堆顶词的出现次数，则用新词替换堆顶的词，然后重新调整为小顶堆，遍历结束后，小顶堆上的词就是出现频数最高的 100 个词。

方案总结

• 分而治之，进行哈希取余；
• 使用 HashMap 统计频数；
• 求解最大的 TopN 个，用小顶堆；求解最小的 TopN 个，用大顶堆。

如何找出某一天访问百度网站最多的 IP？

问题描述

现有海量日志数据保存在一个超大文件中，该文件无法直接读入内存，要求从中提取某天访问百度次数最多的那个 IP。

解决思路

这道题只关心某一天访问百度最多的 IP，因此，可以首先对文件进行一次遍历，把这一天访问百度 IP 的相关信息记录到一个单独的大文件中。接下来采用的方法与上一题一样，大致就是先对 IP 进行哈希映射，接着使用 HashMap 统计重复 IP 的次数，最后计算出重复次数最多的 IP。

注：这里只需要找出出现次数最多的 IP，可以不必使用堆，直接用一个变量 max 即可。

方法总结

• 分而治之，进行哈希取余；
• 使用 HashMap 统计频数；
• 求解最大的 TopN 个，用小顶堆；求解最小的 TopN 个，用大顶堆。

如何在大量的数据中找出不重复的整数？

问题描述

在 2.5 亿个整数中找出不重复的整数。注意：内存不足以容纳这 2.5 亿个整数。

解决思路

方法一：分治法

与前面的题目方法类似，先将 2.5 亿个数划分到多个小文件，用 HashSet/HashMap 找出每个小文件中不重复的整数，再合并每个子结果，即为最终结果。

方法二：位图法

位图，就是用一个或多个 bit 来标记某个元素对应的值，而键就是该元素。采用位作为单位来存储数据，可以大大节省存储空间。

位图通过使用位数组来表示某些元素是否存在。它可以用于快速查找，判重，排序等。不是很清楚？我先举个小例子。

假设我们要对 [0,7] 中的 5 个元素 (6, 4, 2, 1, 5) 进行排序，可以采用位图法。0~7 范围总共有 8 个数，只需要 8bit，即 1 个字节。首先将每个位都置 0：

1

0 0 0 0 0 0 0 0

然后遍历 5 个元素，首先遇到 6，那么将下标为 6 的位的 0 置为 1；接着遇到 4，把下标为 4 的位 的 0 置为 1：

1

0 0 0 0 1 0 1 0

依次遍历，结束后，位数组是这样的：

1

0 1 1 0 1 1 1 0

每个为 1 的位，它的下标都表示了一个数：

1
2
3

for i in range(8):
    if bits[i] == 1:
        print(i)

这样我们其实就已经实现了排序。

对于整数相关的算法的求解，位图法是一种非常实用的算法。假设 int 整数占用 4B，即 32bit，那么我们可以表示的整数的个数为 232。

那么对于这道题，我们用 2 个 bit 来表示各个数字的状态：

• 00 表示这个数字没出现过；
• 01 表示这个数字出现过一次（即为题目所找的不重复整数）；
• 10 表示这个数字出现了多次。

那么这 232 个整数，总共所需内存为 232*2b=1GB。因此，当可用内存超过 1GB 时，可以采用位图法。假设内存满足位图法需求，进行下面的操作：

遍历 2.5 亿个整数，查看位图中对应的位，如果是 00，则变为 01，如果是 01 则变为 10，如果是 10 则保持不变。遍历结束后，查看位图，把对应位是 01 的整数输出即可。

方法总结

判断数字是否重复的问题，位图法是一种非常高效的方法。

如何在大量的数据中判断一个数是否存在？

题目描述

给定 40 亿个不重复的没排过序的 unsigned int 型整数，然后再给定一个数，如何快速判断这个数是否在这 40 亿个整数当中？

解答思路

方法一：分治法

依然可以用分治法解决，方法与前面类似，就不再次赘述了。

方法二：位图法

40 亿个不重复整数，我们用 40 亿个 bit 来表示，初始位均为 0，那么总共需要内存：4,000,000,000b≈512M。

我们读取这 40 亿个整数，将对应的 bit 设置为 1。接着读取要查询的数，查看相应位是否为 1，如果为 1 表示存在，如果为 0 表示不存在。

方法总结

判断数字是否存在、判断数字是否重复的问题，位图法是一种非常高效的方法。

如何查询最热门的查询串？

题目描述

搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来，每个查询串的长度不超过 255 字节。

假设目前有 1000w 个记录（这些查询串的重复度比较高，虽然总数是 1000w，但如果除去重复后，则不超过 300w 个）。请统计最热门的 10 个查询串，要求使用的内存不能超过 1G。（一个查询串的重复度越高，说明查询它的用户越多，也就越热门。）

解答思路

每个查询串最长为 255B，1000w 个串需要占用 约 2.55G 内存，因此，我们无法将所有字符串全部读入到内存中处理。

方法一：分治法

分治法依然是一个非常实用的方法。

划分为多个小文件，保证单个小文件中的字符串能被直接加载到内存中处理，然后求出每个文件中出现次数最多的 10 个字符串；最后通过一个小顶堆统计出所有文件中出现最多的 10 个字符串。

方法可行，但不是最好，下面介绍其他方法。

方法二：HashMap 法

虽然字符串总数比较多，但去重后不超过 300w，因此，可以考虑把所有字符串及出现次数保存在一个 HashMap 中，所占用的空间为 300w*(255+4)≈777M（其中，4 表示整数占用的 4 个字节）。由此可见，1G 的内存空间完全够用。

思路如下：

首先，遍历字符串，若不在 map 中，直接存入 map，value 记为 1；若在 map 中，则把对应的 value 加 1，这一步时间复杂度 O(N)。

接着遍历 map，构建一个 10 个元素的小顶堆，若遍历到的字符串的出现次数大于堆顶字符串的出现次数，则进行替换，并将堆调整为小顶堆。

遍历结束后，堆中 10 个字符串就是出现次数最多的字符串。这一步时间复杂度 O(Nlog10)。

方法三：前缀树法（字典树）

方法二使用了 HashMap 来统计次数，当这些字符串有大量相同前缀时，可以考虑使用前缀树来统计字符串出现的次数，树的结点保存字符串出现次数，0 表示没有出现。

思路如下：

在遍历字符串时，在前缀树中查找，如果找到，则把结点中保存的字符串次数加 1，否则为这个字符串构建新结点，构建完成后把叶子结点中字符串的出现次数置为 1。

最后依然使用小顶堆来对字符串的出现次数进行排序。

方法总结

前缀树经常被用来统计字符串的出现次数。它的另外一个大的用途是字符串查找，判断是否有重复的字符串等。

如何统计不同电话号码的个数？

题目描述

已知某个文件内包含一些电话号码，每个号码为 8 位数字，统计不同号码的个数。

解答思路

这道题本质还是求解数据重复的问题，对于这类问题，一般首先考虑位图法。

对于本题，8 位电话号码可以表示的号码个数为 $$10^8$$ 个，即 1 亿个。我们每个号码用一个 bit 来表示，则总共需要 1 亿个 bit，内存占用约 100M。

思路如下：

申请一个位图数组，长度为 1 亿，初始化为 0。然后遍历所有电话号码，把号码对应的位图中的位置置为 1。遍历完成后，如果 bit 为 1，则表示这个电话号码在文件中存在，否则不存在。bit 值为 1 的数量即为 不同电话号码的个数。

方法总结

求解数据重复问题，记得考虑位图法。

如何从 5 亿个数中找出中位数？

题目描述

从 5 亿个数中找出中位数。数据排序后，位置在最中间的数就是中位数。当样本数为奇数时，中位数为 第 (N+1)/2 个数；当样本数为偶数时，中位数为 第 N/2 个数与第 1+N/2 个数的均值。

解答思路

如果这道题没有内存大小限制，则可以把所有数读到内存中排序后找出中位数。但是最好的排序算法的时间复杂度都为 O(NlogN)。这里使用其他方法。

方法一：双堆法

维护两个堆，一个大顶堆，一个小顶堆。大顶堆中最大的数小于等于小顶堆中最小的数；保证这两个堆中的元素个数的差不超过 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

class MedianFinder {

    private PriorityQueue<Integer> maxHeap;
    private PriorityQueue<Integer> minHeap;

    /** initialize your data structure here. */
    public MedianFinder() {
        maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
        minHeap = new PriorityQueue<>(Integer::compareTo);
    }

    public void addNum(int num) {
        if (maxHeap.isEmpty() || maxHeap.peek() > num) {
            maxHeap.offer(num);
        } else {
            minHeap.offer(num);
        }

        int size1 = maxHeap.size();
        int size2 = minHeap.size();
        if (size1 - size2 > 1) {
            minHeap.offer(maxHeap.poll());
        } else if (size2 - size1 > 1) {
            maxHeap.offer(minHeap.poll());
        }
    }

    public double findMedian() {
        int size1 = maxHeap.size();
        int size2 = minHeap.size();

        return size1 == size2
            ? (maxHeap.peek() + minHeap.peek()) * 1.0 / 2
            : (size1 > size2 ? maxHeap.peek() : minHeap.peek());
    }
}

见 LeetCode No.295：https://leetcode.com/problems/find-median-from-data-stream/

以上这种方法，需要把所有数据都加载到内存中。当数据量很大时，就不能这样了，因此，这种方法适用于数据量较小的情况。5 亿个数，每个数字占用 4B，总共需要 2G 内存。如果可用内存不足 2G，就不能使用这种方法了，下面介绍另一种方法。

方法二：分治法

分治法的思想是把一个大的问题逐渐转换为规模较小的问题来求解。

对于这道题，顺序读取这 5 亿个数字，对于读取到的数字 num，如果它对应的二进制中最高位为 1，则把这个数字写到 f1 中，否则写入 f0 中。通过这一步，可以把这 5 亿个数划分为两部分，而且 f0 中的数都大于 f1 中的数（最高位是符号位）。

划分之后，可以非常容易地知道中位数是在 f0 还是 f1 中。假设 f1 中有 1 亿个数，那么中位数一定在 f0 中，且是在 f0 中，从小到大排列的第 1.5 亿个数与它后面的一个数的平均值。

提示，5 亿数的中位数是第 2.5 亿与右边相邻一个数求平均值。若 f1 有一亿个数，那么中位数就是 f0 中从第 1.5 亿个数开始的两个数求得的平均值。

对于 f0 可以用次高位的二进制继续将文件一分为二，如此划分下去，直到划分后的文件可以被加载到内存中，把数据加载到内存中以后直接排序，找出中位数。

注意，当数据总数为偶数，如果划分后两个文件中的数据有相同个数，那么中位数就是数据较小的文件中的最大值与数据较大的文件中的最小值的平均值。

方法总结

分治法，真香！

如何找出排名前 500 的数？

题目描述

有 20 个数组，每个数组有 500 个元素，并且有序排列。如何在这 20*500 个数中找出前 500 的数？

解答思路

对于 TopK 问题，最常用的方法是使用堆排序。对本题而言，假设数组降序排列，可以采用以下方法：

首先建立大顶堆，堆的大小为数组的个数，即为 20，把每个数组最大的值存到堆中。

接着删除堆顶元素，保存到另一个大小为 500 的数组中，然后向大顶堆插入删除的元素所在数组的下一个元素。

重复上面的步骤，直到删除完第 500 个元素，也即找出了最大的前 500 个数。

为了在堆中取出一个数据后，能知道它是从哪个数组中取出的，从而可以从这个数组中取下一个值，可以把数组的指针存放到堆中，对这个指针提供比较大小的方法。

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

import lombok.Data;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author https://github.com/yanglbme
 */
@Data
public class DataWithSource implements Comparable<DataWithSource> {
    /**
     * 数值
     */
    private int value;

    /**
     * 记录数值来源的数组
     */
    private int source;

    /**
     * 记录数值在数组中的索引
     */
    private int index;

    public DataWithSource(int value, int source, int index) {
        this.value = value;
        this.source = source;
        this.index = index;
    }

    /**
     *
     * 由于 PriorityQueue 使用小顶堆来实现，这里通过修改
     * 两个整数的比较逻辑来让 PriorityQueue 变成大顶堆
     */
    @Override
    public int compareTo(DataWithSource o) {
        return Integer.compare(o.getValue(), this.value);
    }
}


class Test {
    public static int[] getTop(int[][] data) {
        int rowSize = data.length;
        int columnSize = data[0].length;

        // 创建一个columnSize大小的数组，存放结果
        int[] result = new int[columnSize];

        PriorityQueue<DataWithSource> maxHeap = new PriorityQueue<>();
        for (int i = 0; i < rowSize; ++i) {
            // 将每个数组的最大一个元素放入堆中
            DataWithSource d = new DataWithSource(data[i][0], i, 0);
            maxHeap.add(d);
        }

        int num = 0;
        while (num < columnSize) {
            // 删除堆顶元素
            DataWithSource d = maxHeap.poll();
            result[num++] = d.getValue();
            if (num >= columnSize) {
                break;
            }

            d.setValue(data[d.getSource()][d.getIndex() + 1]);
            d.setIndex(d.getIndex() + 1);
            maxHeap.add(d);
        }
        return result;

    }

    public static void main(String[] args) {
        int[][] data = {
                {29, 17, 14, 2, 1},
                {19, 17, 16, 15, 6},
                {30, 25, 20, 14, 5},
        };

        int[] top = getTop(data);
        System.out.println(Arrays.toString(top)); // [30, 29, 25, 20, 19]
    }
}

方法总结

求 TopK，不妨考虑一下堆排序？

如何按照 query 的频度排序？

题目描述

有 10 个文件，每个文件大小为 1G，每个文件的每一行存放的都是用户的 query，每个文件的 query 都可能重复。要求按照 query 的频度排序。

解答思路

如果 query 的重复度比较大，可以考虑一次性把所有 query 读入内存中处理；如果 query 的重复率不高，那么可用内存不足以容纳所有的 query，这时候就需要采用分治法或其他的方法来解决。

方法一：HashMap 法

如果 query 重复率高，说明不同 query 总数比较小，可以考虑把所有的 query 都加载到内存中的 HashMap 中。接着就可以按照 query 出现的次数进行排序。

方法二：分治法

分治法需要根据数据量大小以及可用内存的大小来确定问题划分的规模。对于这道题，可以顺序遍历 10 个文件中的 query，通过 Hash 函数 hash(query) % 10 把这些 query 划分到 10 个小文件中。之后对每个小文件使用 HashMap 统计 query 出现次数，根据次数排序并写入到零外一个单独文件中。

接着对所有文件按照 query 的次数进行排序，这里可以使用归并排序（由于无法把所有 query 都读入内存，因此需要使用外排序）。

方法总结

• 内存若够，直接读入进行排序；
• 内存不够，先划分为小文件，小文件排好序后，整理使用外排序进行归并。

《左耳听风》笔记

洞悉技术的本质

分布式系统架构的本质

分布式系统架构的优点：

• 高性能
• 高可用

分布式系统架构的缺点：

• 设计复杂
• 运维复杂

分布式系统的技术栈

提高性能的技术

• 缓存
• 负载均衡
• 异步
• 分片

提供可用性的技术

• 服务拆分
• 服务冗余
• 流量控制
• 高可用架构：多租户、多活架构、灾备
• 高可用运维：监控、DevOps

分布式系统的关键技术

• 服务治理
• 服务、资源调度
• DevOps
• 监控

编程范式游记

分布式系统设计模式

区块链

程序员练级攻略

面试攻略

高效学习

浅度学习和深度学习

• 高质量的信息源和第一手的知识。
• 把知识连成地图，将自己的理解反述出来。
• 不断地反思和思辨，与不同年龄段的人讨论。
• 举一反三，并践行之，把知识转换成技能。

深度，归纳和坚持实践

1. 这个技术出现的背景、初衷和目标。
2. 这个技术的优势和劣势分别是什么
3. 这个技术适用的场景
4. 技术的组成部分和关键点。
5. 技术的底层原理和关键实现。
6. 已有的实现和它之间的对比。

高效沟通

《从 0 开始学微服务》笔记

到底什么是微服务？

微服务定义

微服务是由单一应用程序构成的小服务，拥有自己的进程与轻量化处理，服务依业务功能设计，以全自动的方式部署，与其他服务使用 HTTP API 通讯。同时，服务会使用最小规模的集中管理 （例如 Docker）技术，服务可以用不同的编程语言与数据库等。

——Martin Fowler 和 James Lewis

单体应用的问题

• 部署效率低
• 团队协作开发成本高
• 单点故障问题
• 线上发布变慢

服务化：本地方法调用 转为 远程方法调用（RPC）

微服务和服务化的差异：

• 服务拆分粒度更细
• 服务独立部署、维护
• 服务治理要求高

从单体应用走向服务化

什么时候进行服务化拆分？

经验：开发人员超过 10 人（沟通成本变高），就可以考虑服务化拆分

服务化拆分的两种姿势

纵向拆分，从业务维度进行拆分。标准是按照业务的关联程度来决定，关联比较密切的业务适合拆分为一个微服务，而功能相对比较独立的业务适合单独拆分为一个微服务。

横向拆分，从公共且独立功能维度拆分。标准是按照是否有公共的被多个其他服务调用，且依赖的资源独立不与其他业务耦合。

服务化拆分的前置条件

• 服务如何定义。通过接口来约定。
• 服务如何发布和订阅。通过服务注册和发现。
• 服务如何监控。故障如何定位。服务化需要链路监控。
• 服务如何治理。超时和重试、流量控制。

初探微服务架构

微服务通过注册中心，实现发布订阅模式。

服务调用主要依赖几个基本组件：

• 服务描述：常用的服务描述方式包括 RESTful API、XML 配置以及 IDL 文件三种。
  • RESTful API 代表：Swagger
  • XML 代表：Dubbo
  • IDL 代表：Thrift、gRPC
• 注册中心
  • 服务提供者在启动时，根据服务发布文件中配置的发布信息向注册中心注册自己的服务。
  • 服务消费者在启动时，根据消费者配置文件中配置的服务信息向注册中心订阅自己所需要的服务。
  • 注册中心返回服务提供者地址列表给服务消费者。
  • 当服务提供者发生变化，比如有节点新增或者销毁，注册中心将变更通知给服务消费者。
• 服务框架
  • 通信协议：选择 TCP、UDP、HTTP，还是其他？
  • 数据传输方式：同步、异步、多路复用？
  • 序列化方式：JDK 序列化、Json、二进制（Protobuf、Thrift）？
• 服务监控
  • 数据采集
  • 数据处理
  • 数据展示
• 服务追踪
• 工作原理：通过 requestId、spanId 分别表示一次请求、请求中的某一环节
• 服务治理：
  • 超时、重试
  • 负载均衡
  • 故障转移
  • 流量控制

如何发布和引用服务？

RESTful API：主要被用作 HTTP 或者 HTTPS 协议的接口定义。代表：Eureka

XML 配置：代表：Dubbo。工作步骤：

• 服务提供者定义接口，并实现接口。
• 服务提供者进程启动时，通过加载 server.xml 配置文件将接口暴露出去。
• 服务消费者进程启动时，通过加载 client.xml 配置文件来引入要调用的接口。

IDL 文件：IDL 就是接口描述语言（interface description language）的缩写。主要用作跨语言平台的服务之间的调用。有两种最常用的 IDL：Thrift、gRPC。

如何注册和发现服务？

微服务架构下，主要有三种角色：

• 服务提供者（RPC Server）
• 服务消费者（RPC Client）
• 服务注册中心（Registry）

注册中心实现方式

注册中心必须提供以下最基本的 API，例如：

• 服务注册接口

• 服务注销接口

• 心跳汇报接口

• 服务订阅接口：服务消费者通过调用服务订阅接口完成服务订阅，获取可用的服务提供者节点列表。

• 服务变更查询接口

• 服务查询接口

• 服务修改接口

集群部署

注册中心一般都是采用集群部署来保证高可用性，并通过分布式一致性协议来确保集群中不同节点之间的数据保持一致。

以 ZooKeeper 的工作原理为例：

• 每个 Server 在内存中存储了一份数据，Client 的读请求可以请求任意一个 Server。
• ZooKeeper 启动时，将从实例中选举一个 leader（Paxos 协议）。
• Leader 负责处理数据更新等操作（ZAB 协议）。
• 一个更新操作成功，当且仅当大多数 Server 在内存中成功修改 。

目录存储

注册中心存储服务信息一般采用层次化的目录结构：

• 每个目录在 ZooKeeper 中叫作 znode，并且其有一个唯一的路径标识。
• znode 可以包含数据和子 znode。
• znode 中的数据可以有多个版本，比如某一个 znode 下存有多个数据版本，那么查询这个路径下的数据需带上版本信息。

服务健康状态检测

ZooKeeper 客户端和服务端维持的是一个长连接。连接成功后，会生成一个全局唯一的 Session ID，客户端定期发送心跳消息，服务端收到后重置会话超时时间。如果超时，则认为连接结束。

如果一个服务将 ZooKeeper 作为服务注册中心，一旦连接超时，ZooKeeper 会认为这个服务节点已经不可用，就会将其信息删除。

服务状态变更通知

ZooKeeper 支持 Watch 机制。服务消费者可以监听服务提供者的节点信息。一旦服务提供者的节点信息哟变化，就可以获取到变更状态。

白名单机制

通常注册中心会有多套环境，区分开发、测试、线上等环境。如果弄错了，会出现意想不到的后果，为此需要引入白名单保护机制。只有添加到注册中心白名单内的 RPC Server，才能够调用注册中心的注册接口，这样的话可以避免测试环境中的节点意外跑到线上环境中去。

如何实现 RPC 远程服务调用？

客户端和服务端如何建立网络连接？

• HTTP 通信：三次握手建立连接；四次挥手断开连接
• Socket 通信
  • 服务器监听
  • 客户端请求
  • 连接确认
  • 数据传输

服务端如何处理请求？

• BIO
• NIO
• AIO

数据传输采用什么协议？

• Http
• Dubbo

数据该如何序列化和反序列化？

• JDK
• JSON
• 二进制（PB、Thrift 等）

如何监控微服务调用？

监控对象

• 客户端监控
• 接口监控
• 资源监控
• 基础监控

监控指标

• 请求量
• 响应时间
• 错误率

监控维度

• 全局维度
• 机房维度
• 单机维度
• 时间维度
• 重要性维度

监控关键点

• 数据采集
  • 主动上报
  • 代理收集
• 数据传输
  • UDP
  • Kafka
• 数据处理
  • 全文检索：如 Elasticsearch
  • 时序数据库：如 InfluxDB、OpenTSDB
  • 流计算：如 Spark、Storm、Flink
• 数据展示

如何追踪微服务调用？

服务追踪的作用

• 定位整个系统的瓶颈点
• 优化链路调用
• 生成网络拓扑
• 透明传输数据

服务追踪系统原理

经典论文：Dapper, a Large-Scale Distributed Systems Tracing Infrastructure

• traceId，用于标识某一次具体的请求 ID。当用户的请求进入系统后，会在 RPC 调用网络的第一层生成一个全局唯一的 traceId，并且会随着每一层的 RPC 调用，不断往后传递，这样的话通过 traceId 就可以把一次用户请求在系统中调用的路径串联起来。
• spanId，用于标识一次 RPC 调用在分布式请求中的位置。当用户的请求进入系统后，处在 RPC 调用网络的第一层 A 时 spanId 初始值是 0，进入下一层 RPC 调用 B 的时候 spanId 是 0.1，继续进入下一层 RPC 调用 C 时 spanId 是 0.1.1，而与 B 处在同一层的 RPC 调用 E 的 spanId 是 0.2，这样的话通过 spanId 就可以定位某一次 RPC 请求在系统调用中所处的位置，以及它的上下游依赖分别是谁。
• annotation，用于业务自定义埋点数据，可以是业务感兴趣的想上传到后端的数据，比如一次请求的用户 UID。

服务追踪系统实现

服务追踪系统可以分为三层。

• 数据采集层，负责数据埋点并上报。
• 数据处理层，负责数据的存储与计算。
• 数据展示层，负责数据的图形化展示。

微服务治理的手段有哪些？

服务调用失败原因：

• 服务提供者自身问题，如宕机、进程退出等；
• 网络问题

节点管理

• 注册中心主动摘除机制：服务提供者定时发送心跳，如果超时，注册中心把节点从服务列表中删除
• 服务消费者摘除机制：如果服务消费者调用服务提供者节点失败，就将这个节点从内存中保存的可用服务提供者节点列表中移除。

负载均衡

• 随机算法
• 轮询算法
• 最少活跃调用算法
• 一致性 Hash 算法

服务路由

为什么要制定路由规则呢？

• 业务存在灰度发布的需求
• 多机房就近访问的需求

如何配置路由规则

• 静态配置：修改服务消费者本地配置，上线后生效
• 动态配置：修改注册中心的配置，服务消费者在下一个同步周期之后，就会动态更新

服务容错

• FailOver：失败自动切换。
• FailBack：失败通知。
• FailCache：失败缓存。
• FailFast：快速失败。

一般情况下对于幂等的调用，可以选择 FailOver 或者 FailCache，非幂等的调用可以选择 FailBack 或者 FailFast。

Dubbo 框架里的微服务组件

服务发布和引用的实践

XML 配置方式的服务发布和引用流程

• 服务提供者定义接口
• 服务提供者发布接口
• 服务消费者引用接口

服务发布和引用的那些坑

如何将注册中心落地？

注册中心如何存储服务信息

服务一般会分成多个不同的分组

• 核心与非核心，从业务的核心程度来分。
• 机房，从机房的维度来分。
• 线上环境与测试环境，从业务场景维度来区分。

所以注册中心存储的服务信息一般包含三部分内容：分组、服务名以及节点信息，节点信息又包括节点地址和节点其他信息。

注册中心工作流程

• 服务提供者注册流程。
• 服务提供者反注册流程。
• 服务消费者查询流程。
• 服务消费者订阅变更流程。

如何注册节点

• 首先查看要注册的节点是否在白名单内？如果不在就抛出异常，在的话继续下一步。
• 其次要查看注册的 Cluster（服务的接口名）是否存在？如果不存在就抛出异常，存在的话继续下一步。
• 然后要检查 Service（服务的分组）是否存在？如果不存在则抛出异常，存在的话继续下一步。
• 最后将节点信息添加到对应的 Service 和 Cluster 下面的存储中。

如何反注册

• 查看 Service（服务的分组）是否存在，不存在就抛出异常，存在就继续下一步。
• 查看 Cluster（服务的接口名）是否存在，不存在就抛出异常，存在就继续下一步。
• 删除存储中 Service 和 Cluster 下对应的节点信息。
• 更新 Cluster 的 sign 值。

如何查询节点信息

首先从 localcache（本机内存）中查找，如果没有就继续下一步。

接着从 snapshot（本地快照）中查找，如果没有就继续下一步。

如何订阅服务变更

• 服务消费者从注册中心获取了服务的信息后，就订阅了服务的变化，会在本地保留 Cluster 的 sign 值。
• 服务消费者每隔一段时间，调用 getSign() 函数，从注册中心获取服务端该 Cluster 的 sign 值，并与本地保留的 sign 值做对比，如果不一致，就从服务端拉取新的节点信息，并更新 localcache 和 snapshot。

注册与发现的几个问题

• 多注册中心

• 并行订阅服务

• 批量反注册服务

• 服务变更信息增量更新

开源服务注册中心如何选型？

• 应用内注册与发现：注册中心提供服务端和客户端的 SDK，业务应用通过引入注册中心提供的 SDK，通过 SDK 与注册中心交互，来实现服务的注册和发现。典型代表：Eureka
• 应用外注册与发现：业务应用本身不需要通过 SDK 与注册中心打交道，而是通过其他方式与注册中心交互，间接完成服务注册与发现。典型代表：Consul

二者对比：

• 用内的解决方案一般适用于服务提供者和服务消费者同属于一个技术体系；
• 应用外的解决方案一般适合服务提供者和服务消费者采用了不同技术体系的业务场景

注册中心选型要考虑的两个问题

• 高可用性
• 数据一致性
  • CP 型：牺牲可用性来保证数据强一致性。代表：ZooKeeper、Etcd、Consul
  • AP 型：代表：Eureka、Nacos

而对于注册中心来说，最主要的功能是服务的注册和发现，在网络出现问题的时候，可用性的需求要远远高于数据一致性。即使因为数据不一致，注册中心内引入了不可用的服务节点，也可以通过其他措施来避免，比如客户端的快速失败机制等，只要实现最终一致性，对于注册中心来说就足够了。因此，选择 AP 型注册中心，一般更加合适。

开源 RPC 框架如何选型？

限定语言 RPC

• Dubbo：仅支持 Java
• Motan：仅支持 Java
• Tars：仅支持 C++
• Spring Cloud：仅支持 Java

跨语言 RPC

• gRPC：支持 C++、Java、Python、Go、Ruby、PHP、Android Java、Objective-C 等多种语言
• Thrift：支持 C++、Java、PHP、Python、Ruby、Erlang 等多种语言

如何搭建一个可靠的监控系统？

日志解决方案：ELK

时序数据库解决方案：Graphite、TICK和Prometheus

如何搭建一套适合你的服务追踪系统？

代表：Zipkin、PinPoint

如何识别服务节点是否存活？

心跳开关保护机制

问题：服务消费者同时并发访问注册中心获取最新服务信息导致注册中心带宽被打满

方案：需要一种保护机制，即使在网络频繁抖动的时候，服务消费者也不至于同时去请求注册中心获取最新的服务节点信息。

服务节点摘除保护机制

问题：服务提供者节点被大量摘除导致服务消费者没有足够的节点可以调用

方案：需要根据实际业务的情况，设定一个阈值比例，即使遇到刚才说的这种情况，注册中心也不能摘除超过这个阈值比例的节点。

静态注册中心

如何使用负载均衡算法？

负载均衡算法

• 随机算法

• 轮询算法

• 加权轮询算法

• 最少活跃连接算法

• 一致性 hash 算法

如何使用服务路由？

服务路由就是服务消费者在发起服务调用时，必须根据特定的规则来选择服务节点，从而满足某些特定的需求。

服务路由的应用场景

• 分组调用
• 灰度发布
• 流量切换
• 读写分离

服务路由的规则

• 条件路由
  • 排除某个服务节点
  • 白名单和黑名单功能
  • 机房隔离
  • 读写分离
• 脚本路由

服务路由的获取方式

• 本地配置
• 配置中心管理
• 动态下发

服务端出现故障时该如何应对？

微服务故障种类

• 集群故障。解决：流量控制
  • 限流
  • 降级
• 单 IDC 故障。解决：多 IDC 部署、流量切换
  • 多 IDC 部署
    • 同城多活
    • 异地多活
  • 流量切换
    • DNS 解析流量切换
    • RPC 流量切换
• 单机故障

服务调用失败时有哪些处理手段？

超时

重试

流量控制

如何管理服务配置？

配置类型：

• 本地配置
• 配置中心

配置中心代表：

• Spring Cloud Config
• Apollo

如何搭建微服务治理平台？

服务管理

• 服务上下线
• 节点添加 / 删除
• 服务查询
• 服务节点查询。这个操作会调用注册中心的节点查询接口，来查询某个服务下一共有多少个节点。

服务治理

• 限流
• 降级
• 切流量

服务监控

问题定位

日志查询

服务运维

• 发布部署
• 弹性伸缩

微服务架构该如何落地？

（略）

微服务为什么要容器化？

微服务引入的问题

设计复杂

测试复杂

运维困难

微服务容器化运维：镜像仓库和资源调度

容器运维平台的组成部分

• 镜像仓库
• 资源调度
• 容器调度
• 服务编排

微服务容器化运维：容器调度和服务编排

容器调度系统代表：Swarm、Mesos，Kubernetes

容器调度要解决的问题

• 主机过滤
  • 存活过滤
  • 硬件过滤
• 调度策略
• 服务编排
• 服务依赖：代表方案：Docker Compose
• 服务发现
  • 基于 Nginx 的服务发现
  • 基于注册中心的服务发现
  • 弹性伸缩

微服务容器化运维：微博容器运维平台 DCP

微服务如何实现 DevOps？

• CI（Continuous Integration），持续集成。开发完成代码开发后，能自动地进行代码检查、单元测试、打包部署到测试环境，进行集成测试，跑自动化测试用例。
  • 代码检查
  • 单元测试
  • 集成测试
• CD（Continuous Deploy），持续部署。代码测试通过后，能自动部署到类生产环境中进行集成测试，测试通过后再进行小流量的灰度验证，验证通过后代码就达到线上发布的要求了，就可以把代码自动部署到线上。

如何做好微服务容量规划？

微服务容量规划的问题

• 服务数量众多
• 服务的接口表现差异巨大
• 服务部署的集群规模大小不同
• 服务之间还存在依赖关系

容量规划系统的作用是根据各个微服务部署集群的最大容量和线上实际运行的负荷，来决定各个微服务是否需要弹性扩缩容，以及需要扩缩容多少台机器。

容量规划系统实施的关键在于两点：

• 容量评估
  • 选择合适的压测指标
    • 系统类指标：CPU、内存、I/O、带宽等
    • 服务类指标：响应时间、P999 耗时、错误率等
  • 压测获取单机的最大容量
    • 单机压测
      • 通过日志回放等手段，模拟线上流量来对单机进行压测；
      • 通过 TCP-Copy 的方式，把线上机器的流量拷贝过来对单机进行压测。
    • 集群压测
  • 实时和获取集群的运行负荷
• 调度决策
  • 可以使用水位线来进行调度决策：当集群的水位线位于致命线以下时，就需要立即扩容，在扩容一定数量的机器后，水位线回到安全线以上并保持一段时间后，就可以进行缩容了。
  • 扩容
    • 按数量
    • 按比例
  • 缩容
  • 逐步缩容
  • 为了避免因扩容、缩容导致的水位线抖动，可以多次采集水位线数据，超过 60% 数据满足库哦哦让条件，才真正触发扩容。

微服务多机房部署实践

多机房负载均衡：利用七层负载均衡和四层负载均衡，将流量根据用户就近访问的原则切分流量。

多机房数据同步

主从机房架构

• 由主机房的处理机来更新本机房的缓存和数据库
• 其他机房的缓存也通过主机房的处理机来更新
• 从机房的数据库则通过 MySQL 的 binlog 同步主机房的数据。

独立机房架构

• 每个机房的处理机接收到写请求后更新各自机房的缓存
• 只有主机房会更新数据库
• 从机房的数据库则通过 MySQL 的 binlog 同步主机房的数据。

WMB 消息同步组件的功能就是把一个机房的写请求发给另外一个机房

• reship，负责把本机房的写请求分发一份给别的机房。
• collector，负责从别的机房读取写请求，然后再把请求转发给本机房的处理机。

实现 WMB 的消息同步功能有两种方案：

• MQ：两个机房的 MQ 通过维护状态机来读写请求
• RPC

多机房数据一致性

微服务混合云部署实践

跨云服务的负载均衡

当服务上云后还需要考虑把一定比例的用户请求路由到云上部署的服务

跨云服务的数据同步

私有云与公有云之间的网络隔离

一般来讲，出于安全的需要，企业内部机房同公有云机房之间的网络是隔离的，为了实现互通，需要架设专门的 VPN 网络或者专线。

数据库能否上云

数据库能否上云的关键取决于数据的隐私性。

跨云服务的容器运维

跨云的主机管理：跨云主机管理的关键点在于，如何对内部私有云的机器和公有云的 ECS 进行管理，

跨云服务发现

跨云弹性扩容

跨云服务编排

下一代微服务架构 Service Mesh

为什么需要 Service Mesh

• 跨语言服务调用的需要

• 云原生应用服务治理的需要

Service Mesh 的实现原理

Service Mesh 实现的关键点：

• 轻量级网络代理 SideCar，它的作用就是转发服务之间的调用；
• 基于 SideCar 的服务治理也被叫作 Control Plane，它的作用是向 SideCar 发送各种指令，以完成各种服务治理功能。
• 服务发现
• 负载均衡
• 请求路由
• 故障处理
• 安全认证
• 监控上报
• 日志记录
• 配额控制

Istio：Service Mesh 的代表产品

Istio 整体架构

Istio 的架构可以说由两部分组成，分别是 Proxy 和 Control Plane。

• Proxy，就是前面提到的 SideCar，与应用程序部署在同一个主机上，应用程序之间的调用都通过 Proxy 来转发，目前支持 HTTP/1.1、HTTP/2、gRPC 以及 TCP 请求。
• Control Plane，与 Proxy 通信，来实现各种服务治理功能，包括三个基本组件：Pilot、Mixer 以及 Citadel。

电商

基本业务架构

订单

订单服务一般不主动调用其他服务

订单服务不负责和第三方集成

订单服务不提供优惠计算或成本分摊逻辑

订单信息管理

• 用户
• 商品
• 收货人
• 收货地址
• 收货时间
• 订单状态

优惠券

典型问题

秒杀活动

超卖

《高并发系统设计 40 问》笔记

基础篇

高并发系统：它的通用设计方法是什么？

并发、异步、缓存

架构分层：我们为什么一定要这么做？

分层架构典型代表：

• MVC（Model-View-Controller）
• 表现层、逻辑层和数据访问层
• OSI 七层网络模型

分层的好处

• 分层的设计可以简化系统设计，让不同的人专注做某一层次的事情。
• 再有，分层之后可以做到很高的复用。
• 分层架构可以让我们更容易做横向扩展。

分层架构的不足

• 增加了代码的复杂度

系统设计目标（一）：如何提升系统性能？

讲述了性能指标和性能量化方式。

系统设计目标（二）：系统怎样做到高可用？

故障转移

• 健康检查：心跳检测
• 选举：Paxos、Raft
• 负载均衡

流量控制：

• 超时与重试
• 限流
• 降级

系统运维

• 灰度发布
• 故障演练
• CI/CD

多活架构

系统设计目标（三）：如何让系统易于扩展？

拆分首先考虑的维度是业务维度

其次，当吞吐量达到单机瓶颈，针对存储做水平差费

数据库篇

池化技术：如何减少频繁创建数据库连接的性能损耗？

池化技术解决频繁创建连接、创建对象的成本

数据库优化方案（一）：查询请求增加时，如何做主从分离？

读写分离：写入时只写主库，在读数据时只读从库。通常采用一主多从架构。

读写分离的问题：主从同步的延迟

读写分离的关键：

• 主从复制
• 读写流量分发
• 代理：Cobar、Mycat
• 客户端：sharding-jdbc、TDDL

数据库优化方案（二）：写入数据量增加时，如何实现分库分表？

垂直拆分：从业务维度，将表分为不同的库

水平拆分：分区 key 是关键。应使用合理策略，分库分表。如：hash 取 mod 法、范围划分

发号器：如何保证分库分表后 ID 的全局唯一性？

分布式 ID：UUID、Snowflake 算法

NoSQL：在高并发场景下，数据库和 NoSQL 如何做到互补？

LSM 树：牺牲了一定的读性能来换取写入数据的高性能，Hbase、Cassandra、LevelDB 都是用这种算法作为存储的引擎。

数据首先会写入到一个叫做 MemTable 的内存结构中，在 MemTable 中数据是按照写入的 Key 来排序的。为了防止 MemTable 里面的数据因为机器掉电或者重启而丢失，一般会通过写 Write Ahead Log 的方式将数据备份在磁盘上。

MemTable 在累积到一定规模时，它会被刷新生成一个新的文件，我们把这个文件叫做 SSTable（Sorted String Table）。当 SSTable 达到一定数量时，我们会将这些 SSTable 合并，减少文件的数量，因为 SSTable 都是有序的，所以合并的速度也很快。

当从 LSM 树里面读数据时，我们首先从 MemTable 中查找数据，如果数据没有找到，再从 SSTable 中查找数据。因为存储的数据都是有序的，所以查找的效率是很高的，只是因为数据被拆分成多个 SSTable，所以读取的效率会低于 B+ 树索引。

缓存篇

缓存：数据库成为瓶颈后，动态数据的查询要如何加速？

缓存分类：静态缓存、进程内缓存、分布式缓存

缓存的使用姿势（一）：如何选择缓存的读写策略？

Cache Aside（旁路缓存）策略

先写表，再写缓存，可能会导致缓存和数据库数据不一致

更新表，删除缓存 key；读数据时，从表中读取。

读策略的步骤

• 从缓存中读取数据；
• 如果缓存命中，则直接返回数据；
• 如果缓存不命中，则从数据库中查询数据；
• 查询到数据后，将数据写入到缓存中，并且返回给用户。

写策略的步骤

• 更新数据库中的记录；
• 删除缓存记录。

Cache Aside 理论上还是有较小概率导致数据不一致。

Cache Aside 存在的最大的问题是当写入比较频繁时，缓存中的数据会被频繁地清理，这样会对缓存的命中率有一些影响。

如果你的业务对缓存命中率有严格的要求，那么可以考虑两种解决方案：

1. 一种做法是在更新数据时也更新缓存，只是在更新缓存前先加一个分布式锁，因为这样在同一时间只允许一个线程更新缓存，就不会产生并发问题了。当然这么做对于写入的性能会有一些影响；
2. 另一种做法同样也是在更新数据时更新缓存，只是给缓存加一个较短的过期时间，这样即使出现缓存不一致的情况，缓存的数据也会很快地过期，对业务的影响也是可以接受。

Read/Write Through（读穿 / 写穿）策略

Write Back（写回）策略

核心思想是在写入数据时只写入缓存，并且把缓存块儿标记为“脏”的。而脏块儿只有被再次使用时才会将其中的数据写入到后端存储中。

这种策略不能被应用到我们常用的数据库和缓存的场景中，它是计算机体系结构中的设计，比如我们在向磁盘中写数据时采用的就是这种策略。

但因为缓存一般使用内存，而内存是非持久化的，所以一旦缓存机器掉电，就会造成原本缓存中的脏块儿数据丢失。所以你会发现系统在掉电之后，之前写入的文件会有部分丢失，就是因为 Page Cache 还没有来得及刷盘造成的。

缓存的使用姿势（二）：缓存如何做到高可用？

分布式缓存的高可用方案

• 客户端方案：在客户端配置多个缓存的节点，通过缓存写入和读取算法策略来实现分布式，从而提高缓存的可用性。
• 代理层方案：客户端所有的写入和读取的请求都通过代理层，而代理层中会内置高可用策略，帮助提升缓存系统的高可用。
• 服务度方案：Redis Sentinel 方案

缓存的使用姿势（三）：缓存穿透了怎么办？

缓存穿透解決方案：

• 保存 null 值
• 布隆过滤器

消息队列篇

消息队列：秒杀时如何处理每秒上万次的下单请求？

削峰、异步处理、系统解耦

消息投递：如何保证消息仅仅被消费一次？

系统架构：每秒 1 万次请求的系统要做服务化拆分吗？

系统中，使用的资源出现扩展性问题，尤其是数据库的连接数出现瓶颈；

大团队共同维护一套代码，带来研发效率的降低，和研发成本的提升；

系统部署成本越来越高。

微服务架构：微服务化后，系统架构要如何改造？

服务拆分时要遵循哪些原则？

服务的边界如何确定？服务的粒度是怎样呢？

在服务化之后，会遇到哪些问题呢？我们又将如何来解决？

分布式服务篇

维护篇

给系统加上眼睛：服务端监控要怎么做？

CPU、内存、磁盘、网络

道路千万条，监控第一条，监控不到位，领导两行泪

监控指标

采集方式

• Agent
• 埋点
• 日志

处理和展示

应用性能管理：用户的使用体验应该如何监控？

压力测试：怎样设计全链路压力测试平台？

配置管理：成千上万的配置项要如何管理？

• 配置存储是分级的，有公共配置，有个性的配置，一般个性配置会覆盖公共配置，这样可以减少存储配置项的数量；
• 配置中心可以提供配置变更通知的功能，可以实现配置的热更新；
• 配置中心关注的性能指标中，可用性的优先级是高于性能的，一般我们会要求配置中心的可用性达到 99.999%，甚至会是 99.9999%。

实战篇

分布式算法 Gossip

Gossip 也叫 Epidemic Protocol （流行病协议），这个协议基于最终一致性以及去中心化设计思想。主要用于分布式节点之间进行信息交换和数据同步，这种场景的一个最大特点就是组成的网络的节点都是对等节点，是非结构化网络（去中心化）。

Gossip 协议最早是在 1987 年发表在 ACM 上的论文 《Epidemic Algorithms for Replicated Database Maintenance》中被提出，其理论基础来源于流行病学的数学模型，这种场景的一个最大特点就是组成的网络的节点都是去中心化的对等节点，在信息同步过程中不能保证某个时刻所有节点都收到消息，但是理论上最终所有节点都会收到消息，实现最终一致性协议。

Gossip 协议是集群中节点相互通信的内部通信技术。 Gossip 是一种高效、轻量级、可靠的节点间广播协议，用于传播数据。它是去中心化的、“流行病”的、容错的和点对点通信协议。

Gossip 的应用

在 CASSANDRA 中，节点间使用 Gossip 协议交换信息，因此所有节点都可以快速了解集群中的所有其他节点。

Consul 使用名为 SERF 的 Gossip 协议有两个作用：

• 发现新节点和宕机的节点
• 可靠且快速的事件广播，用于选举 Leader 等

Gossip 的执行过程

Gossip 协议在概念上非常简单，代码也非常简单。它们背后的基本思想是：一个节点想要与网络中的其他节点共享一些信息。然后周期性地从节点集中随机选择一个节点并交换信息。接收信息的节点做同样的事情。信息定期发送到 N 个目标，N 称为扇出（Fanout）。

• 循环：传播信息的回合数
• 扇出：一个节点在每个循环中闲聊的节点数。当一个节点想要广播一条消息时，它从系统中随机选择 t 个节点并将消息发送给它们。

Gossip 协议的执行过程：

Gossip 过程是由种子节点发起，当一个种子节点有状态需要更新到网络中的其他节点时，它会随机的选择周围几个节点散播消息，收到消息的节点也会重复该过程，直至最终网络中所有的节点都收到了消息。这个过程可能需要一定的时间，由于不能保证某个时刻所有节点都收到消息，但是理论上最终所有节点都会收到消息，因此它是一个最终一致性协议。

为了表述清楚，我们先做一些前提设定

• 种子节点周期性的散播消息，把周期限定为 1 秒
• 被感染节点随机选择 N 个邻接节点（fan-out）散播消息，这里把 fan-out 设置为 3，每次最多往 3 个节点散播。
• 节点只接收消息不反馈结果。
• 每次散播消息都选择尚未发送过的节点进行散播
• 收到消息的节点不再往发送节点散播，比如 A -> B，那么 B 进行散播的时候，不再发给 A。

注意：Gossip 过程是异步的，也就是说发消息的节点不会关注对方是否收到，即不等待响应；不管对方有没有收到，它都会每隔 1 秒向周围节点发消息。异步是它的优点，而消息冗余则是它的缺点。

Goosip 协议的信息传播和扩散通常需要由种子节点发起。整个传播过程可能需要一定的时间，由于不能保证某个时刻所有节点都收到消息，但是理论上最终所有节点都会收到消息，因此它是一个最终一致性协议。

Gossip 类型

Gossip 有两种类型：

• **Anti-Entropy(反熵)**：以固定的概率传播所有的数据。Anti-Entropy 是 SI model，节点只有两种状态，Suspective 和 Infective，叫做 simple epidemics。
• **Rumor-Mongering(谣言传播)**：仅传播新到达的数据。Rumor-Mongering 是 SIR model，节点有三种状态，Suspective，Infective 和 Removed，叫做 complex epidemics。

熵是物理学上的一个概念，代表杂乱无章，而反熵就是在杂乱无章中寻求一致。本质上，反熵是一种通过异步修复实现最终一致性的方法。反熵指的是集群中的节点，每隔段时间就随机选择某个其他节点，然后通过互相交换自己的所有数据来消除两者之间的差异，实现数据的最终一致性。由于消息会不断反复的交换，因此消息数量是非常庞大的，无限制的（unbounded），这对一个系统来说是一个巨大的开销。所以，反熵不适合动态变化或节点数比较多的分布式环境。

谣言传播模型指的是当一个节点有了新数据后，这个节点变成活跃状态，并周期性地联系其他节点向其发送新数据，直到所有的节点都存储了该新数据。在谣言传播模型下，消息可以发送得更频繁，因为消息只包含最新 update，体积更小。而且，一个谣言消息在某个时间点之后会被标记为 removed，并且不再被传播，因此，谣言传播模型下，系统有一定的概率会不一致。而由于，谣言传播模型下某个时间点之后消息不再传播，因此消息是有限的，系统开销小。

一般来说，为了在通信代价和可靠性之间取得折中，需要将这两种方法结合使用。

Gossip 中的通信模式

在 Gossip 协议下，网络中两个节点之间有三种通信方式:

• Push: 节点 A 将数据 (key,value,version) 及对应的版本号推送给 B 节点，B 节点更新 A 中比自己新的数据
• Pull：A 仅将数据 key, version 推送给 B，B 将本地比 A 新的数据（Key, value, version）推送给 A，A 更新本地
• Push/Pull：与 Pull 类似，只是多了一步，A 再将本地比 B 新的数据推送给 B，B 则更新本地

如果把两个节点数据同步一次定义为一个周期，则在一个周期内，Push 需通信 1 次，Pull 需 2 次，Push/Pull 则需 3 次。虽然消息数增加了，但从效果上来讲，Push/Pull 最好，理论上一个周期内可以使两个节点完全一致。直观上，Push/Pull 的收敛速度也是最快的。

Gossip 的特点

Gossip 的优点

• 扩展性：网络可以允许节点的任意增加和减少，新增加的节点的状态最终会与其他节点一致。
• 容错：网络中任何节点的宕机和重启都不会影响 Gossip 消息的传播，Gossip 协议具有天然的分布式系统容错特性。
• 去中心化：Gossip 协议不要求任何中心节点，所有节点都可以是对等的，任何一个节点无需知道整个网络状况，只要网络是连通的，任意一个节点就可以把消息散播到全网。
• 一致性收敛：Gossip 协议中的消息会以一传十、十传百一样的指数级速度在网络中快速传播，因此系统状态的不一致可以在很快的时间内收敛到一致。消息传播速度达到了 logN。
• 简单：Gossip 协议的过程极其简单，实现起来几乎没有太多复杂性。

Gossip 的缺陷

分布式网络中，没有一种完美的解决方案，Gossip 协议跟其他协议一样，也有一些不可避免的缺陷，主要是两个：

• 消息的延迟：由于 Gossip 协议中，节点只会随机向少数几个节点发送消息，消息最终是通过多个轮次的散播而到达全网的，因此使用 Gossip 协议会造成不可避免的消息延迟。不适合用在对实时性要求较高的场景下。
• 消息冗余：Gossip 协议规定，节点会定期随机选择周围节点发送消息，而收到消息的节点也会重复该步骤，因此就不可避免的存在消息重复发送给同一节点的情况，造成了消息的冗余，同时也增加了收到消息的节点的处理压力。而且，由于是定期发送，因此，即使收到了消息的节点还会反复收到重复消息，加重了消息的冗余。

参考资料

• Epidemic Algorithms for Replicated Database Maintenance
• P2P 网络核心技术：Gossip 协议
• INTRODUCTION TO GOSSIP
• Goosip 协议仿真动画

Java 编码和加密

关键词：Base64、消息摘要、数字签名、对称加密、非对称加密、MD5、SHA、HMAC、AES、DES、DESede、RSA

Base64 编码

Base64 原理

Base64 内容传送编码是一种以任意 8 位字节序列组合的描述形式，这种形式不易被人直接识别。

Base64 是一种很常见的编码规范，其作用是将二进制序列转换为人类可读的 ASCII 字符序列，常用在需用通过文本协议（比如 HTTP 和 SMTP）来传输二进制数据的情况下。Base64 并不是加密解密算法，尽管我们有时也听到使用 Base64 来加密解密的说法，但这里所说的加密与解密实际是指编码（encode）和解码（decode）的过程，其变换是非常简单的，仅仅能够避免信息被直接识别。

Base64 算法主要是将给定的字符以字符编码(如 ASCII 码，UTF-8 码)对应的十进制数为基准，做编码操作：

1. 将给定的字符串以字符为单位，转换为对应的字符编码。
2. 将获得字符编码转换为二进制
3. 对二进制码做分组转换，每 3 个字节为一组，转换为每 4 个 6 位二进制位一组（不足 6 位时低位补 0）。这是一个分组变化的过程，3 个 8 位二进制码和 4 个 6 位二进制码的长度都是 24 位（38 = 46 = 24）。
4. 对获得的 4-6 二进制码补位，向 6 位二进制码添加 2 位高位 0，组成 4 个 8 位二进制码。
5. 对获得的 4-8 二进制码转换为十进制码。
6. 将获得的十进制码转换为 Base64 字符表中对应的字符。

Base64 编码表

Base64 应用

Base64 编码可用于在 HTTP 环境下传递较长的标识信息。在其他应用程序中，也常常需要把二进制数据编码为适合放在 URL(包括隐藏表单域)中的形式。此时，采用 Base64 编码具有不可读性，即所编码的数据不会被人用肉眼所直接看到，算是起到一个加密的作用。

然而，标准的 Base64 并不适合直接放在 URL 里传输，因为 URL 编码器会把标准 Base64 中的 / 和 + 字符变为形如 %XX 的形式，而这些 % 号在存入数据库时还需要再进行转换，因为 ANSI SQL 中已将 % 号用作通配符。

为解决此问题，可采用一种用于 URL 的改进 Base64 编码，它不仅在末尾填充 = 号，并将标准 Base64 中的“+”和“/”分别改成了 - 和 _，这样就免去了在 URL 编解码和数据库存储时所要作的转换，避免了编码信息长度在此过程中的增加，并统一了数据库、表单等处对象标识符的格式。

另有一种用于正则表达式的改进 Base64 变种，它将 + 和 / 改成了 ! 和 -，因为 +, * 以及前面在 IRCu 中用到的 [ 和 ] 在正则表达式中都可能具有特殊含义。

【示例】java.util.Base64 编码、解码示例

Base64.getEncoder() 和 Base64.getDecoder() 提供了的是标准的 Base64 编码、解码方式；

Base64.getUrlEncoder() 和 Base64.getUrlDecoder() 提供了 URL 安全的 Base64 编码、解码方式（将 + 和 / 替换为 - 和 _）。

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

import java.nio.charset.StandardCharsets;
import java.util.Base64;

public class Base64Demo {

    public static void main(String[] args) {
        String url = "https://www.baidu.com";
        System.out.println("url:" + url);
        // 标准的 Base64 编码、解码
        byte[] encoded = Base64.getEncoder().encode(url.getBytes(StandardCharsets.UTF_8));
        byte[] decoded = Base64.getDecoder().decode(encoded);
        System.out.println("Url Safe Base64 encoded:" + new String(encoded));
        System.out.println("Url Safe Base64 decoded:" + new String(decoded));
        // URL 安全的 Base64 编码、解码
        byte[] encoded2 = Base64.getUrlEncoder().encode(url.getBytes(StandardCharsets.UTF_8));
        byte[] decoded2 = Base64.getUrlDecoder().decode(encoded2);
        System.out.println("Base64 encoded:" + new String(encoded2));
        System.out.println("Base64 decoded:" + new String(decoded2));
    }

}

输出：

1
2
3
4
5

url:https://www.baidu.com
Url Safe Base64 encoded:aHR0cHM6Ly93d3cuYmFpZHUuY29t
Url Safe Base64 decoded:https://www.baidu.com
Base64 encoded:aHR0cHM6Ly93d3cuYmFpZHUuY29t
Base64 decoded:https://www.baidu.com

消息摘要

消息摘要概述

消息摘要，其实就是将需要摘要的数据作为参数，经过哈希函数(Hash)的计算，得到的散列值。

消息摘要是一个唯一对应一个消息或文本的固定长度的值，它由一个单向 Hash 加密函数对消息进行作用而产生。如果消息在途中改变了，则接收者通过对收到消息的新产生的摘要与原摘要比较，就可知道消息是否被改变了。因此消息摘要保证了消息的完整性。消息摘要采用单向 Hash 函数将需加密的明文”摘要”成一串密文，这一串密文亦称为数字指纹(Finger Print)。它有固定的长度，且不同的明文摘要成密文，其结果总是不同的，而同样的明文其摘要必定一致。这样这串摘要便可成为验证明文是否是”真身”的”指纹”了。

消息摘要特点

• 唯一性：数据只要有一点改变，那么再通过消息摘要算法得到的摘要也会发生变化。虽然理论上有可能会发生碰撞，但是概率极其低。
• 不可逆：消息摘要算法的密文无法被解密。
• 不需要密钥，可使用于分布式网络。
• 无论输入的明文有多长，计算出来的消息摘要的长度总是固定的。

消息摘要常用算法

消息摘要算法包括**MD(Message Digest，消息摘要算法)、SHA(Secure Hash Algorithm，安全散列算法)、MAC(Message AuthenticationCode，消息认证码算法)**共 3 大系列，常用于验证数据的完整性，是数字签名算法的核心算法。

MD5和SHA1分别是MD、SHA算法系列中最有代表性的算法。

如今，MD5 已被发现有许多漏洞，从而不再安全。SHA 算法比 MD 算法的摘要长度更长，也更加安全。

消息摘要应用

MD5、SHA 的范例

JDK 中使用 MD5 和 SHA 这两种消息摘要的方式基本一致，步骤如下：

1. 初始化 MessageDigest 对象
2. 更新要计算的内容
3. 生成摘要

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
46
47
48
49
50
51
52
53
54

import java.security.MessageDigest;
import java.util.Base64;

public class MessageDigestDemo {

    public static byte[] encode(byte[] input, Type type) throws Exception {
        // 根据类型，初始化消息摘要对象
        MessageDigest md5Digest = MessageDigest.getInstance(type.getName());

        // 更新要计算的内容
        md5Digest.update(input);

        // 完成哈希计算，返回摘要
        return md5Digest.digest();
    }

    public static byte[] encodeWithBase64(byte[] input, Type type) throws Exception {
        return Base64.getUrlEncoder().encode(encode(input, type));
    }

    public static String encodeWithBase64String(byte[] input, Type type) throws Exception {
        return Base64.getUrlEncoder().encodeToString(encode(input, type));
    }

    public enum Type {
        MD2("MD2"),
        MD5("MD5"),
        SHA1("SHA1"),
        SHA256("SHA-256"),
        SHA384("SHA-384"),
        SHA512("SHA-512");

        private String name;

        Type(String name) {
            this.name = name;
        }

        public String getName() {
            return this.name;
        }
    }

    public static void main(String[] args) throws Exception {
        String msg = "Hello World!";
        System.out.println("MD2: " + encodeWithBase64String(msg.getBytes(), Type.MD2));
        System.out.println("MD5: " + encodeWithBase64String(msg.getBytes(), Type.MD5));
        System.out.println("SHA1: " + encodeWithBase64String(msg.getBytes(), Type.SHA1));
        System.out.println("SHA256: " + encodeWithBase64String(msg.getBytes(), Type.SHA256));
        System.out.println("SHA384: " + encodeWithBase64String(msg.getBytes(), Type.SHA384));
        System.out.println("SHA512: " + encodeWithBase64String(msg.getBytes(), Type.SHA512));
    }

}

【输出】

1
2
3
4
5
6

MD2: MV98ZyI_Aft8q0uVEA6HLg==
MD5: 7Qdih1MuhjZehB6Sv8UNjA==
SHA1: Lve95gjOVATpfV8EL5X4nxwjKHE=
SHA256: f4OxZX_x_FO5LcGBSKHWXfwtSx-j1ncoSt3SABJtkGk=
SHA384: v9dsDrvQBv7lg0EFR8GIewKSvnbVgtlsJC0qeScj4_1v0GH51c_RO4-WE1jmrbpK
SHA512: hhhE1nBOhXP-w02WfiC8_vPUJM9IvgTm3AjyvVjHKXQzcQFerYkcw88cnTS0kmS1EHUbH_nlN5N7xGtdb_TsyA==

HMAC 的范例

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

import java.nio.charset.StandardCharsets;
import java.util.Base64;
import javax.crypto.Mac;
import javax.crypto.spec.SecretKeySpec;

public class HmacMessageDigest {

    public static void main(String[] args) throws Exception {
        String msg = "Hello World!";
        byte[] salt = "My Salt".getBytes(StandardCharsets.UTF_8);
        System.out.println("原文: " + msg);
        System.out.println("HmacMD5: " + encodeWithBase64String(msg.getBytes(), salt, HmacTypeEn.HmacMD5));
        System.out.println("HmacSHA1: " + encodeWithBase64String(msg.getBytes(), salt, HmacTypeEn.HmacSHA1));
        System.out.println("HmacSHA256: " + encodeWithBase64String(msg.getBytes(), salt, HmacTypeEn.HmacSHA256));
        System.out.println("HmacSHA384: " + encodeWithBase64String(msg.getBytes(), salt, HmacTypeEn.HmacSHA384));
        System.out.println("HmacSHA512: " + encodeWithBase64String(msg.getBytes(), salt, HmacTypeEn.HmacSHA512));
    }

    public static byte[] encode(byte[] plaintext, byte[] salt, HmacTypeEn type) throws Exception {
        SecretKeySpec keySpec = new SecretKeySpec(salt, type.name());
        Mac mac = Mac.getInstance(keySpec.getAlgorithm());
        mac.init(keySpec);
        return mac.doFinal(plaintext);
    }

    public static byte[] encodeWithBase64(byte[] plaintext, byte[] salt, HmacTypeEn type) throws Exception {
        return Base64.getUrlEncoder().encode(encode(plaintext, salt, type));
    }

    public static String encodeWithBase64String(byte[] plaintext, byte[] salt, HmacTypeEn type) throws Exception {
        return Base64.getUrlEncoder().encodeToString(encode(plaintext, salt, type));
    }

    /**
     * JDK支持 HmacMD5, HmacSHA1, HmacSHA256, HmacSHA384, HmacSHA512
     */
    public enum HmacTypeEn {

        HmacMD5, HmacSHA1, HmacSHA256, HmacSHA384, HmacSHA512;
    }

}

输出

1
2
3
4
5
6

原文: Hello World!
HmacMD5: re6BLRsB1Q26SfJTwXZUSQ==
HmacSHA1: CFu8a9H6CbY9C5fo0OmJ2bnuILM=
HmacSHA256: Z1czUqDWWfYYl7qEDJ2sUH6iieHVI7o83dXMl0JYER0=
HmacSHA384: 34mKtRQBOYnwwznmQubjrDk_MsLDGqM2PmgcplZUpLsKNrG_cwfz4bLPJCbBW88b
HmacSHA512: 6n77htTZ_atc04-SsmxhSK3wzh1sAmdudCl0Cb_RZp4DpienG4LZkhXMbq8lcK7XSnz6my_wIpnStDp6PC_-5w==

数字签名

数字签名概述

数字签名算法可以看做是一种带有密钥的消息摘要算法，并且这种密钥包含了公钥和私钥。也就是说，数字签名算法是非对称加密算法和消息摘要算法的结合体。

数字签名算法要求能够验证数据完整性、认证数据来源，并起到抗否认的作用。

数字签名算法包含签名和验证两项操作，遵循私钥签名，公钥验证的方式。

签名时要使用私钥和待签名数据，验证时则需要公钥、签名值和待签名数据，其核心算法主要是消息摘要算法。

数字签名常用算法：RSA、DSA、ECDSA

数字签名算法应用

DSA 的范例

数字签名有两个流程：签名和验证。

它们的前提都是要有一个公钥、密钥对。

数字签名用私钥为消息计算签名。

【示例】用公钥验证摘要

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

public class DsaCoder {

    public static final String KEY_ALGORITHM = "DSA";

    public static final String SIGN_ALGORITHM = "SHA1withDSA";

    /**
     * DSA密钥长度默认1024位。 密钥长度必须是64的整数倍，范围在512~1024之间
     */
    private static final int KEY_SIZE = 1024;

    private KeyPair keyPair;

    public DsaCoder() throws Exception {
        this.keyPair = initKey();
    }

    private KeyPair initKey() throws Exception {
        // 初始化密钥对生成器
        KeyPairGenerator keyPairGen = KeyPairGenerator.getInstance(DsaCoder.KEY_ALGORITHM);
        // 实例化密钥对生成器
        keyPairGen.initialize(KEY_SIZE);
        // 实例化密钥对
        return keyPairGen.genKeyPair();
    }

    public byte[] signature(byte[] data, byte[] privateKey) throws Exception {
        PKCS8EncodedKeySpec keySpec = new PKCS8EncodedKeySpec(privateKey);
        KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);
        PrivateKey key = keyFactory.generatePrivate(keySpec);

        Signature signature = Signature.getInstance(SIGN_ALGORITHM);
        signature.initSign(key);
        signature.update(data);
        return signature.sign();
    }

    public byte[] getPrivateKey() {
        return keyPair.getPrivate().getEncoded();
    }

    public boolean verify(byte[] data, byte[] publicKey, byte[] sign) throws Exception {
        X509EncodedKeySpec keySpec = new X509EncodedKeySpec(publicKey);
        KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);
        PublicKey key = keyFactory.generatePublic(keySpec);

        Signature signature = Signature.getInstance(SIGN_ALGORITHM);
        signature.initVerify(key);
        signature.update(data);
        return signature.verify(sign);
    }

    public byte[] getPublicKey() {
        return keyPair.getPublic().getEncoded();
    }

    public static void main(String[] args) throws Exception {
        String msg = "Hello World";
        DsaCoder dsa = new DsaCoder();
        byte[] sign = dsa.signature(msg.getBytes(), dsa.getPrivateKey());
        boolean flag = dsa.verify(msg.getBytes(), dsa.getPublicKey(), sign);
        String result = flag ? "数字签名匹配" : "数字签名不匹配";
        System.out.println("数字签名：" + Base64.getUrlEncoder().encodeToString(sign));
        System.out.println("验证结果：" + result);
    }

}

【输出】

1
2

数字签名：MCwCFDPUO_VrONl5ST0AWary-MLXJuSCAhRMeMnUVhpizfa2H2M37tne0pUtoA==
验证结果：数字签名匹配

对称加密

对称加密概述

对称加密算法主要有 DES、3DES（TripleDES）、AES、IDEA、RC2、RC4、RC5 和 Blowfish 等。

对称加密算法是应用较早的加密算法，技术成熟。在对称加密算法中，数据发信方将明文（原始数据）和加密密钥（mi yao）一起经过特殊加密算法处理后，使其变成复杂的加密密文发送出去。收信方收到密文后，若想解读原文，则需要使用加密用过的密钥及相同算法的逆算法对密文进行解密，才能使其恢复成可读明文。在对称加密算法中，使用的密钥只有一个，发收信双方都使用这个密钥对数据进行加密和解密，这就要求解密方事先必须知道加密密钥。

对称加密特点：

• 优点：计算量小、加密速度快、加密效率高。
• 缺点：算法是公开的，安全性得不到保证。

通信双方每次使用对称加密算法时，都需要使用其他人不知道的惟一密钥，这会使得通信双方所拥有的密钥数量呈几何级数增长，密钥管理成为用户的负担。对称加密算法在分布式网络系统上使用较为困难，主要是因为密钥管理困难，使用成本较高。

而与公钥、密钥加密算法比起来，对称加密算法能够提供加密和认证却缺乏了签名功能，使得使用范围有所缩小。

对称加密原理

对称加密要求加密与解密使用同一个密钥，解密是加密的逆运算。由于加密、解密使用同一个密钥，这要求通信双方必须在通信前商定该密钥，并妥善保存该密钥。

对称加密体制分为两种：

一种是对明文的单个位（或字节）进行运算，称为流密码，也称为序列密码；

一种是把明文信息划分为不同的组（或块）结构，分别对每个组（或块）进行加密、解密，称为分组密码。

假设甲乙方作为通信双方。假定甲乙双方在消息传递前已商定加密算法，欲完成一次消息传递需要经过如下步骤。

对称加密工作模式

以 DES 算法的工作模式为例，DES 算法根据其加密算法所定义的明文分组的大小（56 位），将数据分割成若干 56 位的加密区块，再以加密区块为单位，分别进行加密处理。如果最后剩下不足一个区块的大小，称之为短块。短块的处理方法有填充法、流密码加密法、密文挪用技术。

根据数据加密时每个加密区块见得关联方式来区分，可以分为以下种工作模式：

(1) 电子密码本模式(Electronic Code Book, ECB)

用途：适合加密密钥，随机数等短数据。例如，安全地传递 DES 密钥，ECB 是最合适的模式。

(2) 密文链接模式(Cipher Booki Chaining, CBC)

用途：可加密任意长度的数据，适用于计算产生检测数据完整性的消息认证 MAC。

(3) 密文反馈模式(Cipher Feed Back, CFB)

用途：因错误传播无界，可以用于检查发现明文密文的篡改。

(4) 输出反馈模式(Output Feed Back, OFB)

用途：使用于加密冗余性较大的数据，比如语音和图像数据。

AES 算法除了以上 4 中模式外，还有一种新的工作模式：

(5) 计数器模式(Counter, CTR)

用途：适用于各种加密应用。

本文对于各种工作模式的原理展开描述。个人认为，作为工程应用，了解其用途即可。

对称加密填充方法

Java 中对称加密对于短块的处理，一般是采用填充方式。

常采用的是：NoPadding（不填充）、Zeros 填充（0 填充）、PKCS5Padding 填充。

ZerosPadding

方式：全部填充为 0 的字节

结果如下：

F1 F2 F3 F4 F5 F6 F7 F8 //第一块

F9 00 00 00 00 00 00 00 //第二块

PKCS5Padding

方式：每个填充的字节都记录了填充的总字节数

结果如下：

F1 F2 F3 F4 F5 F6 F7 F8 //第一块

F9 07 07 07 07 07 07 07 //第二块

对称加密应用

基于密钥加密的流程（DES、DESede、AES 和 IDEA）

DES、DESede、AES 和 IDEA 等算法都是基于密钥加密的对称加密算法，它们的实现流程也基本一致。步骤如下：

（1）生成密钥

1
2
3
4

KeyGenerator kg = KeyGenerator.getInstance("DES");
SecureRandom random = new SecureRandom();
kg.init(random);
SecretKey secretKey = kg.generateKey();

建议使用随机数来初始化密钥的生成。

（2）初始化密码对象

1
2

Cipher cipher = Cipher.getInstance("DES/ECB/PKCS5Padding");
cipher.init(Cipher.ENCRYPT_MODE, secretKey);

ENCRYPT_MODE：加密模式

DECRYPT_MODE：解密模式

（3）执行

1
2

String plaintext = "Hello World";
byte[] ciphertext = cipher.doFinal(plaintext.getBytes());

一个完整的 DES 加密解密范例

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

import java.nio.charset.StandardCharsets;
import java.security.*;
import java.util.Base64;
import javax.crypto.*;
import javax.crypto.spec.IvParameterSpec;

/**
 * DES安全编码：是经典的对称加密算法。密钥仅56位，且迭代次数偏少。已被视为并不安全的加密算法。
 *
 * @author Zhang Peng
 * @since 2016年7月14日
 */
public class DESCoder {

    public static final String KEY_ALGORITHM_DES = "DES";

    public static final String CIPHER_DES_DEFAULT = "DES";

    public static final String CIPHER_DES_ECB_PKCS5PADDING = "DES/ECB/PKCS5Padding"; // 算法/模式/补码方式

    public static final String CIPHER_DES_CBC_PKCS5PADDING = "DES/CBC/PKCS5Padding";

    public static final String CIPHER_DES_CBC_NOPADDING = "DES/CBC/NoPadding";

    private static final String SEED = "%%%today is nice***"; // 用于生成随机数的种子

    private Key key;

    private Cipher cipher;

    private String transformation;

    public DESCoder() throws NoSuchAlgorithmException, NoSuchPaddingException, NoSuchProviderException {
        this.key = initKey();
        this.cipher = Cipher.getInstance(CIPHER_DES_DEFAULT);
        this.transformation = CIPHER_DES_DEFAULT;
    }

    /**
     * 根据随机数种子生成一个密钥
     *
     * @return Key
     * @throws NoSuchAlgorithmException
     * @throws NoSuchProviderException
     * @author Zhang Peng
     * @since 2016年7月14日
     */
    private Key initKey() throws NoSuchAlgorithmException, NoSuchProviderException {
        // 根据种子生成一个安全的随机数
        SecureRandom secureRandom = null;
        secureRandom = new SecureRandom(SEED.getBytes());

        KeyGenerator keyGen = KeyGenerator.getInstance(KEY_ALGORITHM_DES);
        keyGen.init(secureRandom);
        return keyGen.generateKey();
    }

    public DESCoder(String transformation)
        throws NoSuchAlgorithmException, NoSuchPaddingException, NoSuchProviderException {
        this.key = initKey();
        this.cipher = Cipher.getInstance(transformation);
        this.transformation = transformation;
    }

    /**
     * 加密
     *
     * @param input 明文
     * @return byte[] 密文
     * @throws InvalidKeyException
     * @throws IllegalBlockSizeException
     * @throws BadPaddingException
     * @throws InvalidAlgorithmParameterException
     * @author Zhang Peng
     * @since 2016年7月20日
     */
    public byte[] encrypt(byte[] input) throws InvalidKeyException, IllegalBlockSizeException, BadPaddingException,
        InvalidAlgorithmParameterException {
        if (transformation.equals(CIPHER_DES_CBC_PKCS5PADDING) || transformation.equals(CIPHER_DES_CBC_NOPADDING)) {
            cipher.init(Cipher.ENCRYPT_MODE, key, new IvParameterSpec(getIV()));
        } else {
            cipher.init(Cipher.ENCRYPT_MODE, key);
        }
        return cipher.doFinal(input);
    }

    /**
     * 解密
     *
     * @param input 密文
     * @return byte[] 明文
     * @throws InvalidKeyException
     * @throws IllegalBlockSizeException
     * @throws BadPaddingException
     * @throws InvalidAlgorithmParameterException
     * @author Zhang Peng
     * @since 2016年7月20日
     */
    public byte[] decrypt(byte[] input) throws InvalidKeyException, IllegalBlockSizeException, BadPaddingException,
        InvalidAlgorithmParameterException {
        if (transformation.equals(CIPHER_DES_CBC_PKCS5PADDING) || transformation.equals(CIPHER_DES_CBC_NOPADDING)) {
            cipher.init(Cipher.DECRYPT_MODE, key, new IvParameterSpec(getIV()));
        } else {
            cipher.init(Cipher.DECRYPT_MODE, key);
        }
        return cipher.doFinal(input);
    }

    private byte[] getIV() {
        String iv = "01234567"; // IV length: must be 8 bytes long
        return iv.getBytes();
    }

    public static void main(String[] args) throws Exception {
        DESCoder aes = new DESCoder(CIPHER_DES_CBC_PKCS5PADDING);

        String msg = "Hello World!";
        System.out.println("原文: " + msg);
        byte[] encoded = aes.encrypt(msg.getBytes(StandardCharsets.UTF_8));
        String encodedBase64 = Base64.getUrlEncoder().encodeToString(encoded);
        System.out.println("密文: " + encodedBase64);

        byte[] decodedBase64 = Base64.getUrlDecoder().decode(encodedBase64);
        byte[] decoded = aes.decrypt(decodedBase64);
        System.out.println("明文: " + new String(decoded));
    }

}

输出

1
2
3

原文: Hello World!
密文: TtnEu9ezNQtxFKpmq_37Qw==
明文: Hello World!

基于口令加密的流程（PBE）

DES、DESede、AES、IDEA 这几种算法的应用模型几乎如出一辙。

但是，并非所有对称加密算法都是如此。

基于口令加密(Password Based Encryption, PBE)是一种基于口令加密的算法。其特点是：口令由用户自己掌管，采用随机数（这里叫做盐）杂凑多重加密等方法保证数据的安全性。

PBE 没有密钥概念，密钥在其他对称加密算法中是经过计算得出的，PBE 则使用口令替代了密钥。

流程：

步骤如下：

（1）产生盐

1
2

SecureRandom secureRandom = new SecureRandom();
byte[] salt = secureRandom.generateSeed(8); // 盐长度必须为8字节

（2）根据密码产生 Key

1
2
3
4

String password = "123456";
PBEKeySpec keySpec = new PBEKeySpec(password.toCharArray());
SecretKeyFactory keyFactory = SecretKeyFactory.getInstance(KEY_ALGORITHM);
SecretKey secretKey = keyFactory.generateSecret(keySpec);

（3）初始化加密或解密对象

1
2
3

PBEParameterSpec paramSpec = new PBEParameterSpec(salt, ITERATION_COUNT);
Cipher cipher = Cipher.getInstance(KEY_ALGORITHM);
cipher.init(Cipher.ENCRYPT_MODE, secretKey, paramSpec);

（4）执行

1
2

byte[] plaintext = "Hello World".getBytes();
byte[] ciphertext = cipher.doFinal(plaintext);

（5）完整 PBE 示例

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

import java.security.Key;
import java.security.SecureRandom;
import java.util.Base64;
import javax.crypto.Cipher;
import javax.crypto.SecretKey;
import javax.crypto.SecretKeyFactory;
import javax.crypto.spec.PBEKeySpec;
import javax.crypto.spec.PBEParameterSpec;

/**
 * 基于口令加密(Password Based Encryption, PBE)，是一种对称加密算法。 其特点是：口令由用户自己掌管，采用随机数（这里叫做盐）杂凑多重加密等方法保证数据的安全性。
 * PBE没有密钥概念，密钥在其他对称加密算法中是经过计算得出的，PBE则使用口令替代了密钥。
 *
 * @author Zhang Peng
 * @since 2016年7月20日
 */
public class PBECoder {

    public static final String KEY_ALGORITHM = "PBEWITHMD5andDES";

    public static final int ITERATION_COUNT = 100;

    private Key key;

    private byte[] salt;

    public PBECoder(String password) throws Exception {
        this.salt = initSalt();
        this.key = initKey(password);
    }

    private byte[] initSalt() {
        SecureRandom secureRandom = new SecureRandom();
        return secureRandom.generateSeed(8); // 盐长度必须为8字节
    }

    private Key initKey(String password) throws Exception {
        PBEKeySpec keySpec = new PBEKeySpec(password.toCharArray());
        SecretKeyFactory keyFactory = SecretKeyFactory.getInstance(KEY_ALGORITHM);
        return keyFactory.generateSecret(keySpec);
    }

    public byte[] encrypt(byte[] plaintext) throws Exception {
        PBEParameterSpec paramSpec = new PBEParameterSpec(salt, ITERATION_COUNT);
        Cipher cipher = Cipher.getInstance(KEY_ALGORITHM);
        cipher.init(Cipher.ENCRYPT_MODE, key, paramSpec);
        return cipher.doFinal(plaintext);
    }

    public byte[] decrypt(byte[] ciphertext) throws Exception {
        PBEParameterSpec paramSpec = new PBEParameterSpec(salt, ITERATION_COUNT);
        Cipher cipher = Cipher.getInstance(KEY_ALGORITHM);
        cipher.init(Cipher.DECRYPT_MODE, key, paramSpec);
        return cipher.doFinal(ciphertext);
    }

    public static void test1() throws Exception {

        // 产生盐
        SecureRandom secureRandom = new SecureRandom();
        byte[] salt = secureRandom.generateSeed(8); // 盐长度必须为8字节

        // 产生Key
        String password = "123456";
        PBEKeySpec keySpec = new PBEKeySpec(password.toCharArray());
        SecretKeyFactory keyFactory = SecretKeyFactory.getInstance(KEY_ALGORITHM);
        SecretKey secretKey = keyFactory.generateSecret(keySpec);

        PBEParameterSpec paramSpec = new PBEParameterSpec(salt, ITERATION_COUNT);
        Cipher cipher = Cipher.getInstance(KEY_ALGORITHM);
        cipher.init(Cipher.ENCRYPT_MODE, secretKey, paramSpec);

        byte[] plaintext = "Hello World".getBytes();
        byte[] ciphertext = cipher.doFinal(plaintext);
        new String(ciphertext);
    }

    public static void main(String[] args) throws Exception {
        PBECoder encode = new PBECoder("123456");
        String message = "Hello World!";
        byte[] ciphertext = encode.encrypt(message.getBytes());
        byte[] plaintext = encode.decrypt(ciphertext);

        System.out.println("原文：" + message);
        System.out.println("密文：" + Base64.getUrlEncoder().encodeToString(ciphertext));
        System.out.println("明文：" + new String(plaintext));
    }

}

非对称加密

非对称加密概述

非对称加密常用算法：DH(Diffie-Hellman，密钥交换算法)、RSA

非对称加密算法和对称加密算法的主要差别在于非对称加密算法用于加密和解密的密钥是不同的。一个公开，称为公钥（public key）；一个保密，称为私钥（private key）。因此，非对称加密算法也称为双钥加密算法或公钥加密算法。

非对称加密特点：

• 优点：非对称加密算法解决了对称加密算法的密钥分配问题，并极大地提高了算法安全性。
• 缺点：算法比对称算法更复杂，因此加密、解密速度都比对称算法慢很多。

非对称加密算法实现机密信息交换的基本过程是：甲方生成一对密钥并将其中的一把作为公用密钥向其它方公开；得到该公用密钥的乙方使用该密钥对机密信息进行加密后再发送给甲方；甲方再用自己保存的另一把专用密钥对加密后的信息进行解密。

另一方面，甲方可以使用乙方的公钥对机密信息进行签名后再发送给乙方；乙方再用自己的私匙对数据进行验证。

甲方只能用其私钥解密，由其公钥加密后的任何信息。 非对称加密算法的保密性比较好，它消除了最终用户交换密钥的需要。

非对称加密算法应用

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140

import java.nio.charset.StandardCharsets;
import java.security.*;
import java.security.spec.PKCS8EncodedKeySpec;
import java.security.spec.X509EncodedKeySpec;
import java.util.Base64;
import javax.crypto.Cipher;

/**
 * RSA安全编码：非对称加密算法。它既可以用来加密、解密，也可以用来做数字签名
 *
 * @author Zhang Peng
 * @since 2016年7月20日
 */
public class RSACoder {

    public final static String KEY_ALGORITHM = "RSA";

    public final static String SIGN_ALGORITHM = "MD5WithRSA";

    private KeyPair keyPair;

    public RSACoder() throws Exception {
        this.keyPair = initKeyPair();
    }

    private KeyPair initKeyPair() throws Exception {
        // KeyPairGenerator类用于生成公钥和私钥对，基于RSA算法生成对象
        KeyPairGenerator keyPairGen = KeyPairGenerator.getInstance(KEY_ALGORITHM);
        // 初始化密钥对生成器，密钥大小为1024位
        keyPairGen.initialize(1024);
        // 生成一个密钥对
        return keyPairGen.genKeyPair();
    }

    public byte[] encryptByPrivateKey(byte[] plaintext, byte[] key) throws Exception {
        PKCS8EncodedKeySpec keySpec = new PKCS8EncodedKeySpec(key);
        KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);
        PrivateKey privateKey = keyFactory.generatePrivate(keySpec);
        Cipher cipher = Cipher.getInstance(keyFactory.getAlgorithm());
        cipher.init(Cipher.ENCRYPT_MODE, privateKey);
        return cipher.doFinal(plaintext);
    }

    public byte[] decryptByPublicKey(byte[] ciphertext, byte[] key) throws Exception {
        X509EncodedKeySpec keySpec = new X509EncodedKeySpec(key);
        KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);
        PublicKey publicKey = keyFactory.generatePublic(keySpec);
        Cipher cipher = Cipher.getInstance(keyFactory.getAlgorithm());
        cipher.init(Cipher.DECRYPT_MODE, publicKey);
        return cipher.doFinal(ciphertext);
    }

    public byte[] encryptByPublicKey(byte[] plaintext, byte[] key) throws Exception {
        X509EncodedKeySpec keySpec = new X509EncodedKeySpec(key);
        KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);
        PublicKey publicKey = keyFactory.generatePublic(keySpec);
        Cipher cipher = Cipher.getInstance(keyFactory.getAlgorithm());
        cipher.init(Cipher.ENCRYPT_MODE, publicKey);
        return cipher.doFinal(plaintext);
    }

    public byte[] decryptByPrivateKey(byte[] ciphertext, byte[] key) throws Exception {
        PKCS8EncodedKeySpec keySpec = new PKCS8EncodedKeySpec(key);
        KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);
        PrivateKey privateKey = keyFactory.generatePrivate(keySpec);
        Cipher cipher = Cipher.getInstance(keyFactory.getAlgorithm());
        cipher.init(Cipher.DECRYPT_MODE, privateKey);
        return cipher.doFinal(ciphertext);
    }

    public byte[] signature(byte[] data, byte[] privateKey, RsaSignTypeEn type) throws Exception {
        PKCS8EncodedKeySpec keySpec = new PKCS8EncodedKeySpec(privateKey);
        KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);
        PrivateKey key = keyFactory.generatePrivate(keySpec);

        Signature signature = Signature.getInstance(type.name());
        signature.initSign(key);
        signature.update(data);
        return signature.sign();
    }

    public byte[] getPrivateKey() {
        return keyPair.getPrivate().getEncoded();
    }

    public boolean verify(byte[] data, byte[] publicKey, byte[] sign, RsaSignTypeEn type) throws Exception {
        X509EncodedKeySpec keySpec = new X509EncodedKeySpec(publicKey);
        KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);
        PublicKey key = keyFactory.generatePublic(keySpec);

        Signature signature = Signature.getInstance(type.name());
        signature.initVerify(key);
        signature.update(data);
        return signature.verify(sign);
    }

    public byte[] getPublicKey() {
        return keyPair.getPublic().getEncoded();
    }

    public enum RsaSignTypeEn {

        MD2WithRSA,
        MD5WithRSA,
        SHA1WithRSA
    }

    public static void main(String[] args) throws Exception {
        String msg = "Hello World!";
        RSACoder coder = new RSACoder();
        // 私钥加密，公钥解密
        byte[] ciphertext = coder.encryptByPrivateKey(msg.getBytes(StandardCharsets.UTF_8), coder.keyPair.getPrivate().getEncoded());
        byte[] plaintext = coder.decryptByPublicKey(ciphertext, coder.keyPair.getPublic().getEncoded());

        // 公钥加密，私钥解密
        byte[] ciphertext2 = coder.encryptByPublicKey(msg.getBytes(), coder.keyPair.getPublic().getEncoded());
        byte[] plaintext2 = coder.decryptByPrivateKey(ciphertext2, coder.keyPair.getPrivate().getEncoded());

        byte[] sign = coder.signature(msg.getBytes(), coder.getPrivateKey(), RsaSignTypeEn.SHA1WithRSA);
        boolean flag = coder.verify(msg.getBytes(), coder.getPublicKey(), sign, RsaSignTypeEn.SHA1WithRSA);
        String result = flag ? "数字签名匹配" : "数字签名不匹配";

        System.out.println("原文：" + msg);
        System.out.println("公钥：" + Base64.getUrlEncoder().encodeToString(coder.keyPair.getPublic().getEncoded()));
        System.out.println("私钥：" + Base64.getUrlEncoder().encodeToString(coder.keyPair.getPrivate().getEncoded()));

        System.out.println("============== 私钥加密，公钥解密 ==============");
        System.out.println("密文：" + Base64.getUrlEncoder().encodeToString(ciphertext));
        System.out.println("明文：" + new String(plaintext));

        System.out.println("============== 公钥加密，私钥解密 ==============");
        System.out.println("密文：" + Base64.getUrlEncoder().encodeToString(ciphertext2));
        System.out.println("明文：" + new String(plaintext2));

        System.out.println("============== 数字签名 ==============");
        System.out.println("数字签名：" + Base64.getUrlEncoder().encodeToString(sign));
        System.out.println("验证结果：" + result);
    }

}

输出

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

原文：Hello World!
公钥：MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCzPtRLErTUcYtr8GmIpvbso7FN18thuEq02U21mh7TA4FH4TjvNgOZrZEORYu94dxrPdnrPjh0p62P5pDIjx_dtGlZr0aGWgtTvBbPwAKE4keXyPqv4VV6iXRzyQ2HdOvFOovim5eu0Tu_TxGeNpFfp0pYj2LXCzpsgSrdUPuPmwIDAQAB
私钥：MIICdwIBADANBgkqhkiG9w0BAQEFAASCAmEwggJdAgEAAoGBALM-1EsStNRxi2vwaYim9uyjsU3Xy2G4SrTZTbWaHtMDgUfhOO82A5mtkQ5Fi73h3Gs92es-OHSnrY_mkMiPH920aVmvRoZaC1O8Fs_AAoTiR5fI-q_hVXqJdHPJDYd068U6i-Kbl67RO79PEZ42kV-nSliPYtcLOmyBKt1Q-4-bAgMBAAECgYBJxOXiL8S0WjajKcKFNxIQuh3Sh6lwgkRcwcI1p0RgW-TtDEg-SuCYctJsKTsl3rq0eDQjmOvrNsc7ngygPidCiTdbD1H6m3tLrebBB-wZdXMSWPsHtQJsq4dE0e93mmfysciOP6QExOs0JqVjTyyBSK37LpUcLdalj2IJDtC0gQJBAPfMngZAuIPmXued7PUuWNBuwxnkmdMcs308eC_9vnLLXWhDB9xKMuXCMwqk16MJ6j1FQWtJu62T21yniWWQHIsCQQC5LWqKfRxVukgnBg0Pa95NVWWY01Yttnb125JsLxeKbR97KU4VgBaBcB9TyUdPr9lxAzGFg6Y3A1wfsfukaGsxAkEA1l719oLXHYSWZdmBvTozK14m-qeBS9lwjc9aSmpB8B1u2Vvj2Pd3wLyYW4Tv5-QT-J2JUr-e1TMseqOVgX-CsQJAETRoBq_zFv_0vjNwuTMTd2nsw5M3GY4vZU5eP1Dsxf63gxDmYVcCQEpzjqxPxNaYxEhArJ_7rHbSc1ts_ux4sQJBAIlbGQC4-92foXGzWT80rsqZlMQ8J8Nbjpoo7RUN9tgx60Vkr3xv26Vos77oqdufWlt5IiBZBS9acTA2suav6Qg=
============== 私钥加密，公钥解密 ==============
密文：qn6iGjSJV45EnH21RYRx2UZfMueqplbm1g3VIpBBQBuF63RdHdSgMJsVPAuB__V0rxpPlU3gR6qLyWu1mpaJ-ix_6KogAH64wqTWqPRh7E6aj767rybNpt9JyVlCmmpy9DiqHAUFWtBJDo34q-a7Fhq9c8bWrJ6jnn47IdmzHfU=
明文：Hello World!
============== 公钥加密，私钥解密 ==============
密文：fsz2IFs69d7JDrH-yoe5pi5WKQU1Zml7SDSpPqTZUn6muSCjNp6x312deQCXKMGSeAdMpVeb01yZBfa0MT_6eYJYVseU7Rd6bDf6YIg3AZFC41yh5ITiTvQ-XzxugnppS12sLpXSWg0faa5qjcVZnoTX9p7nHr8n20y4CNMI6Rw=
明文：Hello World!
============== 数字签名 ==============
数字签名：dTtUUlWX1wRQbW1PcA8O6WJcWcrHinEZRXwgLKEwBOm2DpvHnynvV_HYKS-qFE5_4vJQcPGJ2hZqWbfv1VKLHMUWuiXM7VJk70g3g7BF8i8RWbrCDOxgTR77jrEwidpr1PYJzWJVGq_HP36MxInGFLcVh2sN0fu8MppzsXUENZQ=
验证结果：数字签名匹配

术语

• **明文(Plaintext)**：指待加密信息。明文可以是文本文件、图片文件、二进制数据等。
• **密文(Ciphertext)**：指经过加密后的明文。密文通常以文本、二进制等形式存在。
• **加密(Encryption)**：指将明文转换为密文的过程。
• **解密(Decryption)**：指将密文转换为明文的过程。
• **加密密钥(Encryption Key)**：指通过加密算法进行加密操作用的密钥。
• **解密密钥(Decryption Key)**：指通过解密算法进行解密操作用的密钥。
• **信道(Channel)**：通信的通道，是信号传输的媒介。

参考资料

• 《Java 核心技术 卷 II 高级特性》
• 《Java 加密与解密的艺术》

JVM 体系结构

JVM 能跨平台工作，主要是由于 JVM 屏蔽了与各个计算机平台相关的软件、硬件之间的差异。

JVM 简介

计算机体系结构

真实的计算机体系结构的核心部分包含：

• 指令集
• 计算单元（CPU）
• 寻址方式
• 寄存器
• 存储单元

JVM 体系结构简介

JVM 体系结构与计算机体系结构相似，它的核心部分包含：

• JVM 指令集
• 类加载器
• 执行引擎 - 相当于 JVM 的 CPU
• 内存区 - JVM 的存储
• 本地方法调用 - 调用 C/C++ 实现的本地方法

Hotspot 架构

Hotspot 是最流行的 JVM。

Java 虚拟机的主要组件，包括类加载器、运行时数据区和执行引擎。

Hotspot 虚拟机拥有一个架构，它支持强大特性和能力的基础平台，支持实现高性能和强大的可伸缩性的能力。举个例子，Hotspot 虚拟机 JIT 编译器生成动态的优化，换句话说，它们在 Java 应用执行期做出优化，为底层系统架构生成高性能的本地机器指令。另外，经过它的运行时环境和多线程垃圾回收成熟的进化和连续的设计， Hotspot 虚拟机在高可用计算系统上产出了高伸缩性。

Hotspot 关键组件

Java 虚拟机有三个组件关注着什么时候进行性能优化，堆空间是对象所存储的地方，这个区域被启动时选择的垃圾回收器管理，大部分调优选项与调整堆大小和根据你的情况选择最适当的垃圾收集器相关。即时编译器对性能也有很大的影响，但是使用新版本的 Java 虚拟机时很少需要调整。

性能指标

Java 虚拟机的性能指标主要有两点：

• 停顿时间 - 响应延迟是指一个应用回应一个请求的速度有多快。对关注响应能力的应用来说，长暂停时间是不可接受的，重点是在短的时间周期内能做出响应。
  • 桌面 UI 响应事件的速度
  • 网站返回网页的速度
  • 数据查询返回的速度
• 吞吐量 - 吞吐量关注在特定的时间周期内一个应用的工作量的最大值。对关注吞吐量的应用来说长暂停时间是可以接受的。由于高吞吐量的应用关注的基准在更长周期时间上，所以快速响应时间不在考虑之内。
  • 给定时间内完成事务的数量
  • 一小时内批处理程序完成的工作数量
  • 一小时内数据查询完成的数量

参考资料

• 《深入理解 Java 虚拟机》

编码和加密

关键词：Base64、消息摘要、数字签名、对称加密、非对称加密、MD5、SHA、HMAC、AES、DES、DESede、RSA

Base64 编码

Base64 原理

Base64 内容传送编码是一种以任意 8 位字节序列组合的描述形式，这种形式不易被人直接识别。

Base64 是一种很常见的编码规范，其作用是将二进制序列转换为人类可读的 ASCII 字符序列，常用在需用通过文本协议（比如 HTTP 和 SMTP）来传输二进制数据的情况下。Base64 并不是加密解密算法，尽管我们有时也听到使用 Base64 来加密解密的说法，但这里所说的加密与解密实际是指编码（encode）和解码（decode）的过程，其变换是非常简单的，仅仅能够避免信息被直接识别。

Base64 算法主要是将给定的字符以字符编码(如 ASCII 码，UTF-8 码)对应的十进制数为基准，做编码操作：

1. 将给定的字符串以字符为单位，转换为对应的字符编码。
2. 将获得字符编码转换为二进制
3. 对二进制码做分组转换，每 3 个字节为一组，转换为每 4 个 6 位二进制位一组（不足 6 位时低位补 0）。这是一个分组变化的过程，3 个 8 位二进制码和 4 个 6 位二进制码的长度都是 24 位（38 = 46 = 24）。
4. 对获得的 4-6 二进制码补位，向 6 位二进制码添加 2 位高位 0，组成 4 个 8 位二进制码。
5. 对获得的 4-8 二进制码转换为十进制码。
6. 将获得的十进制码转换为 Base64 字符表中对应的字符。

Base64 编码表

Base64 应用

Base64 编码可用于在 HTTP 环境下传递较长的标识信息。在其他应用程序中，也常常需要把二进制数据编码为适合放在 URL(包括隐藏表单域)中的形式。此时，采用 Base64 编码具有不可读性，即所编码的数据不会被人用肉眼所直接看到，算是起到一个加密的作用。

然而，标准的 Base64 并不适合直接放在 URL 里传输，因为 URL 编码器会把标准 Base64 中的 / 和 + 字符变为形如 %XX 的形式，而这些 % 号在存入数据库时还需要再进行转换，因为 ANSI SQL 中已将 % 号用作通配符。

为解决此问题，可采用一种用于 URL 的改进 Base64 编码，它不仅在末尾填充 = 号，并将标准 Base64 中的“+”和“/”分别改成了 - 和 _，这样就免去了在 URL 编解码和数据库存储时所要作的转换，避免了编码信息长度在此过程中的增加，并统一了数据库、表单等处对象标识符的格式。

另有一种用于正则表达式的改进 Base64 变种，它将 + 和 / 改成了 ! 和 -，因为 +, * 以及前面在 IRCu 中用到的 [ 和 ] 在正则表达式中都可能具有特殊含义。

消息摘要

消息摘要概述

消息摘要，其实就是将需要摘要的数据作为参数，经过哈希函数(Hash)的计算，得到的散列值。

消息摘要是一个唯一对应一个消息或文本的固定长度的值，它由一个单向 Hash 加密函数对消息进行作用而产生。如果消息在途中改变了，则接收者通过对收到消息的新产生的摘要与原摘要比较，就可知道消息是否被改变了。因此消息摘要保证了消息的完整性。消息摘要采用单向 Hash 函数将需加密的明文”摘要”成一串密文，这一串密文亦称为数字指纹(Finger Print)。它有固定的长度，且不同的明文摘要成密文，其结果总是不同的，而同样的明文其摘要必定一致。这样这串摘要便可成为验证明文是否是”真身”的”指纹”了。

消息摘要特点

• 唯一性：数据只要有一点改变，那么再通过消息摘要算法得到的摘要也会发生变化。虽然理论上有可能会发生碰撞，但是概率极其低。
• 不可逆：消息摘要算法的密文无法被解密。
• 不需要密钥，可使用于分布式网络。
• 无论输入的明文有多长，计算出来的消息摘要的长度总是固定的。

消息摘要常用算法

消息摘要算法包括**MD(Message Digest，消息摘要算法)、SHA(Secure Hash Algorithm，安全散列算法)、MAC(Message AuthenticationCode，消息认证码算法)**共 3 大系列，常用于验证数据的完整性，是数字签名算法的核心算法。

MD5和SHA1分别是MD、SHA算法系列中最有代表性的算法。

如今，MD5 已被发现有许多漏洞，从而不再安全。SHA 算法比 MD 算法的摘要长度更长，也更加安全。

数字签名

数字签名算法可以看做是一种带有密钥的消息摘要算法，并且这种密钥包含了公钥和私钥。也就是说，数字签名算法是非对称加密算法和消息摘要算法的结合体。

数字签名算法要求能够验证数据完整性、认证数据来源，并起到抗否认的作用。

数字签名算法包含签名和验证两项操作，遵循私钥签名，公钥验证的方式。

签名时要使用私钥和待签名数据，验证时则需要公钥、签名值和待签名数据，其核心算法主要是消息摘要算法。

数字签名常用算法：RSA、DSA、ECDSA

对称加密

对称加密算法主要有 DES、3DES（TripleDES）、AES、IDEA、RC2、RC4、RC5 和 Blowfish 等。

对称加密算法是应用较早的加密算法，技术成熟。在对称加密算法中，数据发信方将明文（原始数据）和加密密钥（mi yao）一起经过特殊加密算法处理后，使其变成复杂的加密密文发送出去。收信方收到密文后，若想解读原文，则需要使用加密用过的密钥及相同算法的逆算法对密文进行解密，才能使其恢复成可读明文。在对称加密算法中，使用的密钥只有一个，发收信双方都使用这个密钥对数据进行加密和解密，这就要求解密方事先必须知道加密密钥。

对称加密特点：

• 优点：计算量小、加密速度快、加密效率高。
• 缺点：算法是公开的，安全性得不到保证。

通信双方每次使用对称加密算法时，都需要使用其他人不知道的惟一密钥，这会使得通信双方所拥有的密钥数量呈几何级数增长，密钥管理成为用户的负担。对称加密算法在分布式网络系统上使用较为困难，主要是因为密钥管理困难，使用成本较高。

而与公钥、密钥加密算法比起来，对称加密算法能够提供加密和认证却缺乏了签名功能，使得使用范围有所缩小。

对称加密原理

对称加密要求加密与解密使用同一个密钥，解密是加密的逆运算。由于加密、解密使用同一个密钥，这要求通信双方必须在通信前商定该密钥，并妥善保存该密钥。

对称加密体制分为两种：

一种是对明文的单个位（或字节）进行运算，称为流密码，也称为序列密码；

一种是把明文信息划分为不同的组（或块）结构，分别对每个组（或块）进行加密、解密，称为分组密码。

假设甲乙方作为通信双方。假定甲乙双方在消息传递前已商定加密算法，欲完成一次消息传递需要经过如下步骤。

对称加密工作模式

以 DES 算法的工作模式为例，DES 算法根据其加密算法所定义的明文分组的大小（56 位），将数据分割成若干 56 位的加密区块，再以加密区块为单位，分别进行加密处理。如果最后剩下不足一个区块的大小，称之为短块。短块的处理方法有填充法、流密码加密法、密文挪用技术。

根据数据加密时每个加密区块见得关联方式来区分，可以分为以下种工作模式：

(1) 电子密码本模式(Electronic Code Book, ECB)

用途：适合加密密钥，随机数等短数据。例如，安全地传递 DES 密钥，ECB 是最合适的模式。

(2) 密文链接模式(Cipher Booki Chaining, CBC)

用途：可加密任意长度的数据，适用于计算产生检测数据完整性的消息认证 MAC。

(3) 密文反馈模式(Cipher Feed Back, CFB)

用途：因错误传播无界，可以用于检查发现明文密文的篡改。

(4) 输出反馈模式(Output Feed Back, OFB)

用途：使用于加密冗余性较大的数据，比如语音和图像数据。

AES 算法除了以上 4 中模式外，还有一种新的工作模式：

(5) 计数器模式(Counter, CTR)

用途：适用于各种加密应用。

本文对于各种工作模式的原理展开描述。个人认为，作为工程应用，了解其用途即可。

对称加密填充方法

Java 中对称加密对于短块的处理，一般是采用填充方式。

常采用的是：NoPadding（不填充）、Zeros 填充（0 填充）、PKCS5Padding 填充。

ZerosPadding

方式：全部填充为 0 的字节

结果如下：

F1 F2 F3 F4 F5 F6 F7 F8 //第一块

F9 00 00 00 00 00 00 00 //第二块

PKCS5Padding

方式：每个填充的字节都记录了填充的总字节数

结果如下：

F1 F2 F3 F4 F5 F6 F7 F8 //第一块

F9 07 07 07 07 07 07 07 //第二块

基于口令加密的流程（PBE）

DES、DESede、AES、IDEA 这几种算法的应用模型几乎如出一辙。

但是，并非所有对称加密算法都是如此。

基于口令加密(Password Based Encryption, PBE)是一种基于口令加密的算法。其特点是：口令由用户自己掌管，采用随机数（这里叫做盐）杂凑多重加密等方法保证数据的安全性。

PBE 没有密钥概念，密钥在其他对称加密算法中是经过计算得出的，PBE 则使用口令替代了密钥。

流程：

非对称加密

非对称加密常用算法：DH(Diffie-Hellman，密钥交换算法)、RSA

非对称加密算法和对称加密算法的主要差别在于非对称加密算法用于加密和解密的密钥是不同的。一个公开，称为公钥（public key）；一个保密，称为私钥（private key）。因此，非对称加密算法也称为双钥加密算法或公钥加密算法。

非对称加密特点：

• 优点：非对称加密算法解决了对称加密算法的密钥分配问题，并极大地提高了算法安全性。
• 缺点：算法比对称算法更复杂，因此加密、解密速度都比对称算法慢很多。

非对称加密算法实现机密信息交换的基本过程是：甲方生成一对密钥并将其中的一把作为公用密钥向其它方公开；得到该公用密钥的乙方使用该密钥对机密信息进行加密后再发送给甲方；甲方再用自己保存的另一把专用密钥对加密后的信息进行解密。

另一方面，甲方可以使用乙方的公钥对机密信息进行签名后再发送给乙方；乙方再用自己的私匙对数据进行验证。

甲方只能用其私钥解密，由其公钥加密后的任何信息。 非对称加密算法的保密性比较好，它消除了最终用户交换密钥的需要。

术语

• **明文(Plaintext)**：指待加密信息。明文可以是文本文件、图片文件、二进制数据等。
• **密文(Ciphertext)**：指经过加密后的明文。密文通常以文本、二进制等形式存在。
• **加密(Encryption)**：指将明文转换为密文的过程。
• **解密(Decryption)**：指将密文转换为明文的过程。
• **加密密钥(Encryption Key)**：指通过加密算法进行加密操作用的密钥。
• **解密密钥(Decryption Key)**：指通过解密算法进行解密操作用的密钥。
• **信道(Channel)**：通信的通道，是信号传输的媒介。

参考资料

• 《Java 核心技术 卷 II 高级特性》
• 《Java 加密与解密的艺术》

面向对象设计六大原则

单一职责原则

单一职责原则（Single Responsibility Principle），应该有且仅有一个原因引起类的变更。

简单点说，一个类，最好只负责一件事。

开放-封闭原则

开放-封闭原则（Open Close Principle），软件实体（类、模块、函数）等应该可以扩展，但是不可修改。

对于扩展是开放的；对于更改是封闭的。

里氏替换原则

里氏替换原则（Liskov Substitution Principle），子类可以替换父类。

依赖倒置原则

依赖倒置原则（Dependency Inversion Principle），抽象不应该依赖于细节，细节应当依赖于抽象。换言之，要针对接口编程，而不是针对实现编程。

关键点：

• 高层模块不应该依赖低层模块，两者都应该依赖其抽象
• 抽象不应该依赖细节
• 细节应该依赖抽象

接口隔离原则

接口隔离原则（Interface Segregation Principle）使用多个专门的接口，而不使用单一的总接口，即客户端不应该依赖那些它不需要的接口。

• 客户端不应依赖它不需要的接口
• 类间的依赖关系应该建立在最小的接口上

迪米特原则

迪米特原则（Least Knowledge Principle）又称最少知识原则，一个软件实体应当尽可能少地与其他实体发生相互作用。

一个类应该对自己需要调用的类知道得最少，类的内部如何实现、如何复杂都与调用者或者依赖者没关系，调用者或者依赖者只需要知道他需要的方法即可，其他的我一概不关心。

参考资料

• 《Head First 设计模式》
• 《大话设计模式》