0%

海量数据处理

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

问题描述

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

解决思路

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

5,000,000,00064B5GB64=320GB5,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:

0 0 0 0 0 0 0 0

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

0 0 0 0 1 0 1 0

依次遍历,结束后,位数组是这样的:

0 1 1 0 1 1 1 0

每个为 1 的位,它的下标都表示了一个数:

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。

若数据总数为偶数,当这两个堆建好之后,中位数就是这两个堆顶元素的平均值。当数据总数为奇数时,根据两个堆的大小,中位数一定在数据多的堆的堆顶

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 个数。

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

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 都读入内存,因此需要使用外排序)。

方法总结

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

微服务理论

一、微服务简介

什么是微服务架构

  • 服务拆分粒度更细:根据业务拆分。
  • 独立部署:每个服务部署在物理上隔离,互不影响。
  • 独立维护:根据组织架构拆分,分团队维护。
  • 服务治理:服务数量变多,需要有统一的服务治理平台。

如何权衡微服务的利弊

优点

  • 强模块化边界
  • 可独立部署
  • 技术多样性

缺点

  • 分布式复杂度
  • 最终一致性
  • 运维复杂度
  • 测试复杂度

康威定律

  • 第一定律:组织沟通方式会通过系统设计表达出来
  • 第二定律:时间再多一件事情也不可能做的完美,但总有时间做完一件事情
  • 第三定律:线型系统和线型组织架构间有潜在的异质同态特性
  • 第四定律:大的系统组织总是比小系统更倾向于分解

如何拆分微服务

思考维度:

  • 根据业务维度聚类,业务和数据关系密切的应该放在一起。
  • 根据功能维度聚类,公共功能聚合为一个服务。
  • 根据组织架构聚类,根据实际组织架构,天然分为不同的团队,每个团队独立维护若干微服务。

前置条件:

  • 服务如何定
  • 服务如何发布和订阅
  • 服务如何监控
  • 服务如何治理
  • 故障如何定位

二、微服务技术架构

img

第一层:接入层

外部设备访问的统一接入层。

第二层:聚合服务层

对下层的基础服务做一些聚合,剪裁的工作,适配上层不同设备的数据输出。

第三层:基础服务层

比较细粒度的微服务层,提供基础的核心服务,公共服务。

img

三、服务注册发现

在微服务架构下,主要有三种角色:

  • 服务提供者(RPC Server / Provider)
  • 服务消费者(RPC Client / Consumer)
  • 服务注册中心(Registry)

注册中心的实现依赖以下机制:

  • 注册中心 API
  • 集群部署:如果注册中心是单点,无法保障高可用。
  • 元数据存储:例如 ZooKeeper 将数据以层次化的目录结构存储。
  • 服务健康检查:使用长连接或心跳探测方式检查服务健康状态。
  • 服务状态变更通知:可以基于订阅者模式实现,例如 ZooKeeper 的 Watch 机制。
  • 白名单机制

注册中心的服务注册和发现都是基于 API 的。一般需要支持以下功能:

  • 服务注册
  • 服务注销
  • 接口续约(心跳)
  • 服务订阅
  • 可用服务同步
  • 服务查询
  • 服务修改

注册中心实现模式

应用内注册和发现

采用应用内注册与发现的方式,最典型的案例要属 Netflix 开源的 Eureka,官方架构图如下。

img

对着这张图,我来介绍下 Eureka 的架构,它主要由三个重要的组件组成:

  • Eureka Server:注册中心的服务端,实现了服务信息注册、存储以及查询等功能。
  • 服务端的 Eureka Client:集成在服务端的注册中心 SDK,服务提供者通过调用 SDK,实现服务注册、反注册等功能。
  • 客户端的 Eureka Client:集成在客户端的注册中心 SDK,服务消费者通过调用 SDK,实现服务订阅、服务更新等功能。

应用外注册和发现

img

通过这张架构图,可以看出来使用 Consul 实现应用外服务注册和发现主要依靠三个重要的组件:

  • Consul:注册中心的服务端,实现服务注册信息的存储,并提供注册和发现服务。
  • Registrator:一个开源的第三方服务管理器项目,它通过监听服务部署的 Docker 实例是否存活,来负责服务提供者的注册和销毁。
  • Consul Template:定时从注册中心服务端获取最新的服务提供者节点列表并刷新 LB 配置(比如 Nginx 的 upstream),这样服务消费者就通过访问 Nginx 就可以获取最新的服务提供者信息。

注册中心选型

高可用性

集群部署,通过部署多个实例组成集群来保证高可用性。

多 IDC 部署,即部署在不止一个机房。

数据一致性

根据 CAP 理论,三者不能同时满足:

  • CP 型注册中心,牺牲可用性来保证数据强一致性,最典型的例子就是 ZooKeeper,etcd,Consul 了。ZooKeeper 集群内只有一个 Leader,而且在 Leader 无法使用的时候通过 Paxos 算法选举出一个新的 Leader。这个 Leader 的目的就是保证写信息的时候只向这个 Leader 写入,Leader 会同步信息到 Followers,这个过程就可以保证数据的强一致性。但如果多个 ZooKeeper 之间网络出现问题,造成出现多个 Leader,发生脑裂的话,注册中心就不可用了。而 etcd 和 Consul 集群内都是通过 raft 协议来保证强一致性,如果出现脑裂的话, 注册中心也不可用。
  • AP 型注册中心,牺牲一致性来保证可用性,最典型的例子就是 Eureka 了。对比下 Zookeeper,Eureka 不用选举一个 Leader,每个 Eureka 服务器单独保存服务注册地址,因此有可能出现数据信息不一致的情况。但是当网络出现问题的时候,每台服务器都可以完成独立的服务。

服务注册发现的问题

多注册中心

对于服务消费者来说,要能够同时从多个注册中心订阅服务;对于服务提供者来说,要能够同时向多个注册中心注册服务。

并行订阅服务

可以每订阅一个服务就单独用一个线程来处理,这样的话即使遇到个别服务节点连接超时,其他服务节点的初始化连接也不受影响,最慢也就是这个服务节点的初始化连接耗费的时间,最终所有服务节点的初始化连接耗时控制在了 30 秒以内。

批量注销服务

需要定时去清理注册中心中的“僵尸节点”,如果支持批量注销服务,就可以一次调用就把该节点上提供的所有服务同时注销掉。

服务变更信息同步更新

为了减少服务消费者从注册中心中拉取的服务可用节点信息的数据量,这个时候可以通过增量更新的方式,注册中心只返回变化的那部分节点信息,尤其在只有少数节点信息变更时,此举可以大大减少服务消费者从注册中心拉取的数据量,从而最大程度避免产生网络风暴。

识别服务节点是否存活

心跳开关保护机制

在网络频繁抖动的情况下,注册中心中可用的节点会不断变化,这时候服务消费者会频繁收到服务提供者节点变更的信息,于是就不断地请求注册中心来拉取最新的可用服务节点信息。当有成百上千个服务消费者,同时请求注册中心获取最新的服务提供者的节点信息时,可能会把注册中心的带宽给占满,尤其是注册中心是百兆网卡的情况下。

所以针对这种情况,需要一种保护机制,即使在网络频繁抖动的时候,服务消费者也不至于同时去请求注册中心获取最新的服务节点信息

我曾经就遇到过这种情况,一个可行的解决方案就是给注册中心设置一个开关,当开关打开时,即使网络频繁抖动,注册中心也不会通知所有的服务消费者有服务节点信息变更,比如只给 10% 的服务消费者返回变更,这样的话就能将注册中心的请求量减少到原来的 1/10。

当然打开这个开关也是有一定代价的,它会导致服务消费者感知最新的服务节点信息延迟,原先可能在 10s 内就能感知到服务提供者节点信息的变更,现在可能会延迟到几分钟,所以在网络正常的情况下,开关并不适合打开;可以作为一个紧急措施,在网络频繁抖动的时候,才打开这个开关。

服务节点摘除保护机制

服务提供者在进程启动时,会注册服务到注册中心,并每隔一段时间,汇报心跳给注册中心,以标识自己的存活状态。如果隔了一段固定时间后,服务提供者仍然没有汇报心跳给注册中心,注册中心就会认为该节点已经处于“dead”状态,于是从服务的可用节点信息中移除出去。

如果遇到网络问题,大批服务提供者节点汇报给注册中心的心跳信息都可能会传达失败,注册中心就会把它们都从可用节点列表中移除出去,造成剩下的可用节点难以承受所有的调用,引起“雪崩”。但是这种情况下,可能大部分服务提供者节点是可用的,仅仅因为网络原因无法汇报心跳给注册中心就被“无情”的摘除了。

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

这个阈值比例可以根据实际业务的冗余度来确定,我通常会把这个比例设定在 20%,就是说注册中心不能摘除超过 20% 的节点。因为大部分情况下,节点的变化不会这么频繁,只有在网络抖动或者业务明确要下线大批量节点的情况下才有可能发生。而业务明确要下线大批量节点的情况是可以预知的,这种情况下可以关闭阈值保护;而正常情况下,应该打开阈值保护,以防止网络抖动时,大批量可用的服务节点被摘除。

四、服务通信

  • 通信方式。它主要解决客户端和服务端如何建立连接、管理连接以及服务端如何处理请求的问题。例如:Dubbo 基于 TCP 通信;而 Spring Cloud 基于 HTTP REST 通信。TCP 通信方式,传输效率更高;但是 HTTP 方式天然可以提供对外服务。
  • 通信协议。它主要解决客户端和服务端采用哪种数据传输协议的问题。
  • 序列化和反序列化。它主要解决客户端和服务端采用哪种数据编解码的问题。常见的序列化方式包括:XML、JSON;二进制类如:thriftprotobufhessian、JDK

序列化方式的选型,一般基于以下考虑:

  • 支持数据结构类型的丰富度
  • 跨语言支持
  • 性能

RPC vs. REST

img

五、API 网关

API 网关是一个服务器,是系统的唯一入口。从面向对象设计的角度看,它与外观模式类似。API 网关封装了系统内部架构,为每个客户端提供一个定制的 API。它可能还具有其它职责,如身份验证、监控、负载均衡、缓存、请求分片与管理、静态响应处理。
API 网关方式的核心要点是,所有的客户端和消费端都通过统一的网关接入微服务,在网关层处理所有的非业务功能。通常,网关也是提供 REST/HTTP 的访问 API。服务端通过 API-GW 注册和管理服务。

Zuul

img

在 zuul 中, 整个请求的过程是这样的,首先将请求给 zuulservlet 处理,zuulservlet 中有一个 zuulRunner 对象,该对象中初始化了 RequestContext:作为存储整个请求的一些数据,并被所有的 zuulfilter 共享。zuulRunner 中还有 FilterProcessor,FilterProcessor 作为执行所有的 zuulfilter 的管理器。FilterProcessor 从 filterloader 中获取 zuulfilter,而 zuulfilter 是被 filterFileManager 所加载,并支持 groovy 热加载,采用了轮询的方式热加载。有了这些 filter 之后,zuulservelet 首先执行的 Pre 类型的过滤器,再执行 route 类型的过滤器,最后执行的是 post 类型的过滤器,如果在执行这些过滤器有错误的时候则会执行 error 类型的过滤器。执行完这些过滤器,最终将请求的结果返回给客户端。

六、服务治理

微服务治理平台就是与服务打交道的统一入口,无论是开发人员还是运维人员,都能通过这个平台对服务进行各种操作,比如开发人员可以通过这个平台对服务进行降级操作,运维人员可以通过这个平台对服务进行上下线操作,而不需要关心这个操作背后的具体实现。

微服务治理平台关键之处就在于它能够封装对微服务架构内的各个基础设施组件的调用,从而对外提供统一的服务操作 API,而且还提供了可视化的界面,以方便开发人员和运维人员操作。

img

服务治理的常用手段有:

  • 节点管理
    • 注册中心主动摘除机制
    • 服务消费者摘除机制
  • 负载均衡
    • 轮询
    • 随机
    • 最近最少连接
    • 一致性 Hash
  • 服务路由
    • 业务存在灰度发布的需求
    • 多机房就近访问的需求
  • 服务容错
    • FailOver:失败自动切换
    • FailBack:失败通知
    • FailCache:失败缓存
    • FailFast:快速失败

七、负载均衡

参考:负载均衡基本原理

八、服务路由

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

服务路由的应用场景

  • 分组调用。一般来讲,为了保证服务的高可用性,实现异地多活的需求,一个服务往往不止部署在一个数据中心,而且出于节省成本等考虑,有些业务可能不仅在私有机房部署,还会采用公有云部署,甚至采用多家公有云部署。服务节点也会按照不同的数据中心分成不同的分组,这时对于服务消费者来说,选择哪一个分组调用,就必须有相应的路由规则。
  • 灰度发布。在服务上线发布的过程中,一般需要先在一小部分规模的服务节点上先发布服务,然后验证功能是否正常。如果正常的话就继续扩大发布范围;如果不正常的话,就需要排查问题,解决问题后继续发布。这个过程就叫作灰度发布,也叫金丝雀部署。
  • 流量切换。在业务线上运行过程中,经常会遇到一些不可抗力因素导致业务故障,比如某个机房的光缆被挖断,或者发生着火等事故导致整个机房的服务都不可用。这个时候就需要按照某个指令,能够把原来调用这个机房服务的流量切换到其他正常的机房。
  • 读写分离。对于大多数互联网业务来说都是读多写少,所以在进行服务部署的时候,可以把读写分开部署,所有写接口可以部署在一起,而读接口部署在另外的节点上。

服务路由的规则

服务路由主要有两种规则:一种是条件路由,一种是脚本路由。

条件路由

条件路由是基于条件表达式的路由规则。

condition://0.0.0.0/dubbo.test.interfaces.TestService?category=routers&dynamic=true&priority=2&enabled=true&rule=" + URL.encode(" host = 10.20.153.10=> host = 10.20.153.11")

这里面 condition:// 代表了这是一段用条件表达式编写的路由规则,具体的规则是

host = 10.20.153.10 => host = 10.20.153.11

分隔符“=>”前面是服务消费者的匹配条件,后面是服务提供者的过滤条件。当服务消费者节点满足匹配条件时,就对该服务消费者执行后面的过滤规则。那么上面这段表达式表达的意义就是 IP 为“10.20.153.10”的服务消费者都调用 IP 为“10.20.153.11”的服务提供者节点。

如果服务消费者的匹配条件为空,就表示对所有的服务消费者应用,就像下面的表达式一样。

=> host != 10.20.153.11

如果服务提供者的过滤条件为空,就表示禁止服务消费者访问,就像下面的表达式一样。

host = 10.20.153.10=>

下面我举一些 Dubbo 框架中的条件路由,来给你讲解下条件路由的具体应用场景。

  • 排除某个服务节点
=> host != 172.22.3.91

一旦这条路由规则被应用到线上,所有的服务消费者都不会访问 IP 为 172.22.3.91 的服务节点,这种路由规则一般应用在线上流量排除预发布机以及摘除某个故障节点的场景。

  • 白名单和黑名单功能
host != 10.20.153.10,10.20.153.11 =>

这条路由规则意思是除了 IP 为 10.20.153.10 和 10.20.153.11 的服务消费者可以发起服务调用以外,其他服务消费者都不可以,主要用于白名单访问逻辑,比如某个后台服务只允许特定的几台机器才可以访问,这样的话可以机器控制访问权限。

host = 10.20.153.10,10.20.153.11 =>

同理,这条路由规则意思是除了 IP 为 10.20.153.10 和 10.20.153.11 的服务消费者不能发起服务调用以外,其他服务消费者都可以,也就是实现了黑名单功能,比如线上经常会遇到某些调用方不管是出于有意还是无意的不合理调用,影响了服务的稳定性,这时候可以通过黑名单功能暂时予以封杀。

  • 机房隔离
host = 172.22.3.* => host = 172.22.3.*

这条路由规则意思是 IP 网段为 172.22.3.* 的服务消费者,才可以访问同网段的服务节点,这种规则一般应用于服务部署在多个 IDC,理论上同一个 IDC 内的调用性能要比跨 IDC 调用性能要好,应用这个规则是为了实现同 IDC 就近访问。

  • 读写分离
method = find*,list*,get*,is* => host =172.22.3.94,172.22.3.95
method != find*,list*,get*,is* => host = 172.22.3.97,172.22.3.98

这条路由规则意思是 find*、get*、is* 等读方法调用 IP 为 172.22.3.94 和 172.22.3.95 的节点,除此以外的写方法调用 IP 为 172.22.3.97 和 172.22.3.98 的节点。对于大部分互联网业务来说,往往读请求要远远大于写请求,而写请求的重要性往往要远远高于读请求,所以需要把读写请求进行分离,以避免读请求异常影响到写请求,这时候就可以应用这种规则。

脚本路由

脚本路由是基于脚本语言的路由规则,常用的脚本语言比如 JavaScript、Groovy、JRuby 等。

"script://0.0.0.0/com.foo.BarService?category=routers&dynamic=false&rule=" + URL.encode("(function route(invokers) { ... } (invokers))")

这里面“script://”就代表了这是一段脚本语言编写的路由规则,具体规则定义在脚本语言的 route 方法实现里,比如下面这段用 JavaScript 编写的 route() 方法表达的意思是,只有 IP 为 10.20.153.10 的服务消费者可以发起服务调用。

function route(invokers){
var result = new java.util.ArrayList(invokers.size());
for(i =0; i < invokers.size(); i ++){
if("10.20.153.10".equals(invokers.get(i).getUrl().getHost())){
result.add(invokers.get(i));
}
}
return result;
} (invokers));

服务路由的获取方式

服务路由的获取方式主要有三种:

  • 本地配置

顾名思义就是路由规则存储在服务消费者本地上。服务消费者发起调用时,从本地固定位置读取路由规则,然后按照路由规则选取一个服务节点发起调用。

  • 配置中心管理

这种方式下,所有的服务消费者都从配置中心获取路由规则,由配置中心来统一管理。

  • 动态下发

这种方式下,一般是运维人员或者开发人员,通过服务治理平台修改路由规则,服务治理平台调用配置中心接口,把修改后的路由规则持久化到配置中心。因为服务消费者订阅了路由规则的变更,于是就会从配置中心获取最新的路由规则,按照最新的路由规则来执行。

内部服务调用

基础服务之间的调用:结合服务注册中心以及专属的具有负载均衡功能的客户端,如 Eureka+(restTemplate+Ribbon)或者 Eureka+Feign
聚合服务调用:结合服务注册中心以及专属的具有负载均衡功能的客户端,如 Eureka+(restTemplate+Ribbon)或者 Eureka+Feign

img

外部服务调用

基于 Netflix 的 zuul,做了简单了解,SpringCloud 与 zuul 集成的方式。这里先对核心流程做个简单了解,后续会有深入的应用、分析。

Spring Cloud 很好的集成了 zuul,并且可以通过注解的形式来进行请求的反向路由以及 API 网关功能
Spring Cloud 集成 zuul,对与 url 映射的处理方式与 SpringMVC 对 url 的请求方式类似,都是通过 RequestMapping 来进行请求绑定的。核心类:ZuulHandlerMapping
zuul 的核心是 ZuulServlet,一个请求核心流程:HttpServletRequest –>ZuulHandlerMapping –>ZuulController –> ZuulServlet –> ZuulFilter –> HttpServletResponse

九、配置中心

配置中心的思路就是把服务的各种配置,如代码里配置的各种参数、服务降级的开关甚至依赖的资源等都在一个地方统一进行管理。服务启动时,可以自动从配置中心中拉取所需的配置,并且如果有配置变更的情况,同样可以自动从配置中心拉取最新的配置信息,服务无须重新发布。

配置中心一般包含下面几个功能:

  • 配置注册功能
  • 配置反注册功能
  • 配置查看功能
  • 配置变更订阅功能

Apollo

携程开源的分布式配置中心,支持 Java 和.Net 语言,客户端和配置中心通过 HTTP 长连接实现实时推送,并且有统一的管理界面来实现配置管理。

img

Spring Cloud Git

Spring Cloud 中使用的配置中心组件,只支持 Java 语言,配置存储在 git 中,变更配置也需要通过 git 操作,如果配置中心有配置变更,需要手动刷新。

img

十、服务监控

在微服务架构下,一次用户调用会因为服务化拆分后,变成多个不同服务之间的相互调用,这也就需要对拆分后的每个服务都监控起来。

监控对象

  • 客户端监控:性能、返回码、地域、运营商、版本、系统等。
  • 业务监控:核心指标、登录、登出、下单、支付等。
  • 应用监控:访问接口、访问服务、SQL、内存使用率、响应时间、TPS、QPS 等。
  • 系统监控:CPU、内存、网络、磁盘等。
  • 基础监控:网络流量、丢包数、错包数、连接数等。

系统监控原理

监控系统主要包括四个环节:数据采集、数据传输、数据处理和数据展示

数据采集

通常有两种数据收集方式:

  • 服务主动上报,这种处理方式通过在业务代码或者服务框架里加入数据收集代码逻辑,在每一次服务调用完成后,主动上报服务的调用信息。
  • 代理收集,这种处理方式通过服务调用后把调用的详细信息记录到本地日志文件中,然后再通过代理去解析本地日志文件,然后再上报服务的调用信息。

数据传输

数据传输最常用的方式有两种:

  • UDP 传输,这种处理方式是数据处理单元提供服务器的请求地址,数据采集后通过 UDP 协议与服务器建立连接,然后把数据发送过去。
  • Kafka 传输,这种处理方式是数据采集后发送到指定的 Topic,然后数据处理单元再订阅对应的 Topic,就可以从 Kafka 消息队列中读取到对应的数据。

数据处理

数据处理是对收集来的原始数据进行聚合并存储。数据聚合通常有两个维度:

  • 接口维度聚合,这个维度是把实时收到的数据按照接口名维度实时聚合在一起,这样就可以得到每个接口的实时请求量、平均耗时等信息。
  • 机器维度聚合,这个维度是把实时收到的数据按照调用的节点维度聚合在一起,这样就可以从单机维度去查看每个接口的实时请求量、平均耗时等信息。

聚合后的数据需要持久化到数据库中存储,所选用的数据库一般分为两种:

  • 全文检索数据库,比如 Elasticsearch,以倒排索引的数据结构存储,需要查询的时候,根据索引来查询。
  • 时序数据库,比如 OpenTSDB,以时序序列数据的方式存储,查询的时候按照时序如 1min、5min 等维度来查询。

数据展示

数据展示是把处理后的数据以 Dashboard 的方式展示给用户。数据展示有多种方式,比如曲线图、饼状图、格子图展示等。

监控技术

img

  • ELK 的技术栈比较成熟,应用范围也比较广,除了可用作监控系统外,还可以用作日志查询和分析。
  • Graphite 是基于时间序列数据库存储的监控系统,并且提供了功能强大的各种聚合函数比如 sum、average、top5 等可用于监控分析,而且对外提供了 API 也可以接入其他图形化监控系统如 Grafana。
  • TICK 的核心在于其时间序列数据库 InfluxDB 的存储功能强大,且支持类似 SQL 语言的复杂数据处理操作。
  • Prometheus 的独特之处在于它采用了拉数据的方式,对业务影响较小,同时也采用了时间序列数据库存储,而且支持独有的 PromQL 查询语言,功能强大而且简洁。

十一、链路追踪

链路追踪的作用

  • 优化系统瓶颈
  • 优化链路调用
  • 生成网络拓扑
  • 透明传输数据

链路追踪的原理

理解链路追踪必须先了解以下概念:

  • 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。

img

链路追踪的实现

一个服务追踪系统一般可以分为三层:

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

数据采集层

一次 RPC 请求可以分为四个阶段。

  • CS(Client Send)阶段 : 客户端发起请求,并生成调用的上下文。
  • SR(Server Recieve)阶段 : 服务端接收请求,并生成上下文。
  • SS(Server Send)阶段 : 服务端返回请求,这个阶段会将服务端上下文数据上报,下面这张图可以说明上报的数据有:traceId=123456,spanId=0.1,appKey=B,method=B.method,start=103,duration=38。
  • CR(Client Recieve)阶段 : 客户端接收返回结果,这个阶段会将客户端上下文数据上报,上报的数据有:traceid=123456,spanId=0.1,appKey=A,method=B.method,start=103,duration=38。

数据处理层

数据处理层的作用就是把数据采集层上报的数据按需计算,然后落地存储供查询使用。

  • 实时数据处理

针对实时数据处理,一般采用 Storm 或者 Spark Streaming 来对链路数据进行实时聚合加工,存储一般使用 OLTP 数据仓库,比如 HBase,使用 traceId 作为 RowKey,能天然地把一整条调用链聚合在一起,提高查询效率。

  • 离线数据处理

针对离线数据处理,一般通过运行 MapReduce 或者 Spark 批处理程序来对链路数据进行离线计算,存储一般使用 Hive。

数据展示层

数据展示层的作用就是将处理后的链路信息以图形化的方式展示给用户。

实际项目中主要用到两种图形展示,一种是调用链路图,一种是调用拓扑图。

链路追踪方案对比

img

十一、限流熔断

一般而言,集群故障的产生原因不外乎有两种:

一种是代码 bug 所导致,比如说某一段 Java 代码不断地分配大对象,但没有及时回收导致 JVM OOM 退出;

另一种是突发的流量冲击,超出了系统的最大承载能力,比如“双 11”这种购物活动,电商系统会在零点一瞬间涌入大量流量,超出系统的最大承载能力,一下子就把整个系统给压垮了。

应付集群故障的思路,主要有两种:限流降级

限流

限流就是限制流量。通常情况下,系统能够承载的流量根据集群规模的大小是固定的,可以称之为系统的最大容量。当真实流量超过了系统的最大容量后,就会导致系统响应变慢,服务调用出现大量超时,反映给用户的感觉就是卡顿、无响应。所以,应该根据系统的最大容量,给系统设置一个阈值,超过这个阈值的请求会被自动抛弃,这样的话可以最大限度地保证系统提供的服务正常。

除此之外,通常一个微服务系统会同时提供多个服务,每个服务在同一时刻的请求量也是不同的,很可能出现的一种情况就是,系统中某个服务的请求量突增,占用了系统中大部分资源,导致其他服务没有资源可用。因此,还要针对系统中每个服务的请求量也设置一个阈值,超过这个阈值的请求也要被自动抛弃,这样的话不至于因为一个服务影响了其他所有服务。

在实际项目中,可以用两个指标来衡量服务的请求量,一个是 QPS 即每秒请求量,一个是工作线程数。不过 QPS 因为不同服务的响应快慢不同,所以系统能够承载的 QPS 相差很大,因此一般选择工作线程数来作为限流的指标,给系统设置一个总的最大工作线程数以及单个服务的最大工作线程数,这样的话无论是系统的总请求量过大导致整体工作线程数量达到最大工作线程数,还是某个服务的请求量超过单个服务的最大工作线程数,都会被限流,以起到保护整个系统的作用。

降级

什么是降级呢?在我看来,降级就是通过停止系统中的某些功能,来保证系统整体的可用性。降级可以说是一种被动防御的措施,为什么这么说呢?因为它一般是系统已经出现故障后所采取的一种止损措施。

那么降级一般是如何实现的呢?根据我的实践来看, 一种可行的方案是通过开关来实现。

具体来讲,就是在系统运行的内存中开辟一块区域,专门用于存储开关的状态,也就是开启还是关闭。并且需要监听某个端口,通过这个端口可以向系统下发命令,来改变内存中开关的状态。当开关开启时,业务的某一段逻辑就不再执行,而正常情况下,开关是关闭的状态。

开关一般用在两种地方,一种是新增的业务逻辑,因为新增的业务逻辑相对来说不成熟,往往具备一定的风险,所以需要加开关来控制新业务逻辑是否执行;另一种是依赖的服务或资源,因为依赖的服务或者资源不总是可靠的,所以最好是有开关能够控制是否对依赖服务或资源发起调用,来保证即使依赖出现问题,也能通过降级来避免影响。

在实际业务应用的时候,降级要按照对业务的影响程度进行分级,一般分为三级:一级降级是对业务影响最小的降级,在故障的情况下,首先执行一级降级,所以一级降级也可以设置成自动降级,不需要人为干预;二级降级是对业务有一定影响的降级,在故障的情况下,如果一级降级起不到多大作用的时候,可以人为采取措施,执行二级降级;三级降级是对业务有较大影响的降级,这种降级要么是对商业收入有重大影响,要么是对用户体验有重大影响,所以操作起来要非常谨慎,不在最后时刻一般不予采用。

十二、DEVOPS

容器和容器平台

Mesos、Marathon、Kubernetes

十三、RPC 选型

限定语言 RPC

跟语言平台绑定的开源 RPC 框架主要有下面几种。

  • Dubbo:国内最早开源的 RPC 框架,由阿里巴巴公司开发并于 2011 年末对外开源,仅支持 Java 语言。
  • Motan:微博内部使用的 RPC 框架,于 2016 年对外开源,仅支持 Java 语言。
  • Tars:腾讯内部使用的 RPC 框架,于 2017 年对外开源,仅支持 C++ 语言。
  • Spring Cloud:国外 Pivotal 公司 2014 年对外开源的 RPC 框架,仅支持 Java 语言,最近几年生态发展得比较好,是比较火的 RPC 框架。

所以很明显,如果你的业务场景仅仅局限于一种语言的话,可以选择跟语言绑定的 RPC 框架中的一种;如果涉及多个语言平台之间的相互调用,就应该选择跨语言平台的 RPC 框架。

仔细分析,可以看出 Spring Cloud 不仅提供了基本的 RPC 框架功能,还提供了服务注册组件、配置中心组件、负载均衡组件、断路器组件、分布式消息追踪组件等一系列组件,也难怪被技术圈的人称之为“Spring Cloud 全家桶”。如果你不想自己实现以上这些功能,那么 Spring Cloud 基本可以满足你的全部需求。而 Dubbo、Motan 基本上只提供了最基础的 RPC 框架的功能,其他微服务组件都需要自己去实现。不过由于 Spring Cloud 的 RPC 通信采用了 HTTP 协议,相比 Dubbo 和 Motan 所采用的私有协议来说,在高并发的通信场景下,性能相对要差一些,所以对性能有苛刻要求的情况下,可以考虑 Dubbo 和 Motan。

跨语言 RPC

而跨语言平台的开源 RPC 框架主要有以下几种。

  • gRPC:Google 于 2015 年对外开源的跨语言 RPC 框架,支持常用的 C++、Java、Python、Go、Ruby、PHP、Android Java、Objective-C 等多种语言。
  • Thrift:最初是由 Facebook 开发的内部系统跨语言的 RPC 框架,2007 年贡献给了 Apache 基金,成为 Apache 开源项目之一,支持常用的 C++、Java、PHP、Python、Ruby、Erlang 等多种语言。

从成熟度上来讲,Thrift 因为诞生的时间要早于 gRPC,所以使用的范围要高于 gRPC,在 HBase、Hadoop、Scribe、Cassandra 等许多开源组件中都得到了广泛地应用。而且 Thrift 支持多达 25 种语言,这要比 gRPC 支持的语言更多,所以如果遇到 gRPC 不支持的语言场景下,选择 Thrift 更合适。

但 gRPC 作为后起之秀,因为采用了 HTTP/2 作为通信协议、ProtoBuf 作为数据序列化格式,在移动端设备的应用以及对传输带宽比较敏感的场景下具有很大的优势,而且开发文档丰富,根据 ProtoBuf 文件生成的代码要比 Thrift 更简洁一些,从使用难易程度上更占优势,所以如果使用的语言平台 gRPC 支持的话,建议还是采用 gRPC 比较好。

十四、Service Mesh

img

Service Mesh 的实现原理

Service Mesh 实现的关键就在于两点:

一个是上面提到的轻量级的网络代理也叫 SideCar,它的作用就是转发服务之间的调用;

一个是基于 SideCar 的服务治理也被叫作 Control Plane,它的作用是向 SideCar 发送各种指令,以完成各种服务治理功能。下面我就来详细讲解这两点是如何实现的。

参考资料

RPC 基本原理

一、RPC 简介

什么是 RPC

RPC 的全称是 Remote Procedure Call,即远程过程调用

RPC 的主要作用是:

  • 屏蔽远程调用跟本地调用的区别。
  • 隐藏底层网络通信的复杂性。

RPC 通信

远程调用说明了,RPC 需要通信,那么 RPC 的通信过程是怎样的呢?

RPC 常用于业务系统之间的数据交互,需要保证其可靠性,所以 RPC 一般默认采用 TCP 来传输。

网络传输的数据必须是二进制数据,但调用方请求的出入参数都是对象,所以必须要将其转换,这个过程叫序列化。

img

  • RPC 拦截调用方要执行的远程方法,将方法名、参数等序列化为方便在网络中传输的二进制或 JSON 数据,然后将这些请求信息传给服务提供方;
  • 服务提供方将请求信息反序列化为本地的方法和请求参数,然后执行,最后将执行结果序列化为二进制或 JSON 数据,再回应给调用方。
  • 调用方将应答数据反序列化。

RPC 协议

既然有了现成的 HTTP 协议,还有必要设计 RPC 协议吗?

有必要。因为 HTTP 这些通信标准协议,数据包中的实际请求数据相对于数据包本身要小很多,有很多无用的内容;并且 HTTP 属于无状态协议,无法将请求和响应关联,每次请求要重新建立连接。这对于高性能的 RPC 来说,HTTP 协议难以满足需求,所以有必要设计一个紧凑的私有协议

img

二、序列化

序列化可以将对象的字节序列持久化——保存在内存、文件、数据库中

序列化是 RPC 的要点之一。

img

常见序列化方式

JDK 序列化

有兴趣深入了解 JDK 序列化方式,可以参考:深入理解 Java 序列化

JSON

jacksongsonfastjson - 适用于对序列化后的数据要求有良好的可读性(转为 json 、xml 形式)。

Hessian

hessian - 适用于对开发体验敏感,性能有要求的内外部系统。

但 Hessian 本身也有问题,官方版本对 Java 里面一些常见对象的类型不支持,比如:

  • Linked 系列,LinkedHashMapLinkedHashSet 等,但是可以通过扩展 CollectionDeserializer 类修复;
  • Locale 类,可以通过扩展 ContextSerializerFactory 类修复;
  • Byte/Short 反序列化的时候变成 Integer

Thrift / Protobuf

thriftprotobuf - 适用于对性能敏感,对开发体验要求不高的内部系统。

初次以外,还有很多其他的序列化方案。那么,RPC 的序列化方式如何选择呢?

img

综合以上,Java RPC 框架中序列化方式,一般首选 Protobuf 和 Hessian,二者在性能、通用性、安全性、兼容性、空间开销上都表现不错。其中,Protobuf 性能、通用性更好;而 Hessian 在开发体验上更为便捷。

序列化问题

Java 对象序列化,一般要关注以下问题:

常规性问题:

  • 当父类继承 Serializable 接口时,所有子类都可以被序列化。
  • 子类实现了 Serializable 接口,父类没有,则父类的属性不会被序列化(不报错,数据丢失),子类的属性仍可以正确序列化。
  • 如果序列化的属性是对象,则这个对象也必须实现 Serializable 接口,否则会报错。
  • 在反序列化时,如果对象的属性有修改或删减,则修改的部分属性会丢失,但不会报错。
  • 在反序列化时,如果 serialVersionUID 被修改,则反序列化时会失败。

设计问题:

  • 对象过于复杂、庞大 - 对象过于复杂、庞大,会降低序列化、反序列化的效率,并增加传输开销,从而导致响应时延增大。
  • 对象有复杂的继承关系 - 对象关系越复杂,就越浪费性能,同时又很容易出现序列化上的问题。
  • 使用序列化框架不支持的类作为入参类 - 比如 Hessian 框架,他天然是不支持 LinkHashMap、LinkedHashSet 等,而且大多数情况下最好不要使用第三方集合类,如 Guava 中的集合类,很多开源的序列化框架都是优先支持编程语言原生的对象。因此如果入参是集合类,应尽量选用原生的、最为常用的集合类,如 HashMap、ArrayList。

三、反射+动态代理

RPC 的远程过程调用时通过反射+动态代理实现的。

img

RPC 框架会自动为要调用的接口生成一个代理类。当在项目中注入接口的时候,运行过程中实际绑定的就是这个接口生成的代理类。在接口方法被调用时,会被代理类拦截,这样,就可以在生成的代理类中,加入远程调用逻辑。

除了 JDK 默认的 InvocationHandler 能完成代理功能,还有很多其他的第三方框架也可以,比如像 Javassist、Byte Buddy 这样的框架。

反射+动态代理更多详情可以参考:深入理解 Java 反射和动态代理

四、网络通信

一次 RPC 调用,本质就是服务消费者与服务提供者间的一次网络信息交换的过程。可见,通信时 RPC 实现的核心。

常见的网络 IO 模型有:同步阻塞(BIO)、同步非阻塞(NIO)、异步非阻塞(AIO)。

IO 多路复用

IO 多路复用(Reactor 模式)在高并发场景下使用最为广泛,很多知名软件都应用了这一技术,如:Netty、Redis、Nginx 等。

IO 多路复用分为 select,poll 和 epoll。

什么是 IO 多路复用?字面上的理解,多路就是指多个通道,也就是多个网络连接的 IO,而复用就是指多个通道复用在一个复用器上。

零拷贝

系统内核处理 IO 操作分为两个阶段——等待数据和拷贝数据。等待数据,就是系统内核在等待网卡接收到数据后,把数据写到内核中;而拷贝数据,就是系统内核在获取到数据后,将数据拷贝到用户进程的空间中。

img

应用进程的每一次写操作,都会把数据写到用户空间的缓冲区中,再由 CPU 将数据拷贝到系统内核的缓冲区中,之后再由 DMA 将这份数据拷贝到网卡中,最后由网卡发送出去。这里我们可以看到,一次写操作数据要拷贝两次才能通过网卡发送出去,而用户进程的读操作则是将整个流程反过来,数据同样会拷贝两次才能让应用程序读取到数据。

应用进程的一次完整的读写操作,都需要在用户空间与内核空间中来回拷贝,并且每一次拷贝,都需要 CPU 进行一次上下文切换(由用户进程切换到系统内核,或由系统内核切换到用户进程),这样很浪费 CPU 和性能。

所谓的零拷贝,就是取消用户空间与内核空间之间的数据拷贝操作,应用进程每一次的读写操作,可以通过一种方式,直接将数据写入内核或从内核中读取数据,再通过 DMA 将内核中的数据拷贝到网卡,或将网卡中的数据 copy 到内核。

img

Netty 的零拷贝偏向于用户空间中对数据操作的优化,这对处理 TCP 传输中的拆包粘包问题有着重要的意义,对应用程序处理请求数据与返回数据也有重要的意义。

Netty 框架中很多内部的 ChannelHandler 实现类,都是通过 CompositeByteBuf、slice、wrap 操作来处理 TCP 传输中的拆包与粘包问题的。

Netty 的 ByteBuffer 可以采用 Direct Buffers,使用堆外直接内存进行 Socketd 的读写
操作,最终的效果与我刚才讲解的虚拟内存所实现的效果是一样的。

Netty 还提供 FileRegion 中包装 NIO 的 FileChannel.transferTo() 方法实现了零拷
贝,这与 Linux 中的 sendfile 方式在原理上也是一样的。

五、RPC 架构模型

了解前面的知识点(序列化、动态代理、通信),其实已经可以实现一个点对点的 RPC 架构了。

采用微内核架构的 RPC 架构模型:

img

在 RPC 框架里面,怎么支持插件化架构的呢?我们可以将每个功能点抽象成一个接
口,将这个接口作为插件的契约,然后把这个功能的接口与功能的实现分离,并提供接口的默认实现。在 Java 里面,JDK 有自带的 SPI(Service Provider Interface)服务发现机
制,它可以动态地为某个接口寻找服务实现。使用 SPI 机制需要在 Classpath 下的 META-INF/services 目录里创建一个以服务接口命名的文件,这个文件里的内容就是这个接口的具体实现类。

但在实际项目中,我们其实很少使用到 JDK 自带的 SPI 机制,首先它不能按需加载,
ServiceLoader 加载某个接口实现类的时候,会遍历全部获取,也就是接口的实现类得全部载入并实例化一遍,会造成不必要的浪费。另外就是扩展如果依赖其它的扩展,那就做不到自动注入和装配,这就很难和其他框架集成,比如扩展里面依赖了一个 Spring Bean,原生的 Java SPI 就不支持。

六、服务注册和发现

RPC 框架必须要有服务注册和发现机制,这样,集群中的节点才能知道通信方的请求地址。

  • 服务注册:在服务提供方启动的时候,将对外暴露的接口注册到注册中心之中,注册中心将这个服务节点的 IP 和接口保存下来。
  • 服务订阅:在服务调用方启动的时候,去注册中心查找并订阅服务提供方的 IP,然后缓存到本地,并用于后续的远程调用。

基于 ZooKeeper 的服务发现

使用 ZooKeeper 作为服务注册中心,是 Java 分布式系统的经典方案。

搭建一个 ZooKeeper 集群作为注册中心集群,服务注册的时候只需要服务节点向 ZooKeeper 节点写入注册信息即可,利用 ZooKeeper 的 Watcher 机制完成服务订阅与服务下发功能

img

通常我们可以使用 ZooKeeper、etcd 或者分布式缓存(如 Hazelcast)来解决事件通知问题,但当集群达到一定规模之后,依赖的 ZooKeeper 集群、etcd 集群可能就不稳定了,无法满足我们的需求。

在超大规模的服务集群下,注册中心所面临的挑战就是超大批量服务节点同时上下线,注册中心集群接受到大量服务变更请求,集群间各节点间需要同步大量服务节点数据,最终导致如下问题:

  • 注册中心负载过高;
  • 各节点数据不一致;
  • 服务下发不及时或下发错误的服务节点列表。

RPC 框架依赖的注册中心的服务数据的一致性其实并不需要满足 CP,只要满足 AP 即可。

基于消息总线的最终一致性的注册中心

ZooKeeper 的一大特点就是强一致性,ZooKeeper 集群的每个节点的数据每次发生更新操作,都会通知其它 ZooKeeper 节点同时执行更新。它要求保证每个节点的数据能够实时的完全一致,这也就直接导致了 ZooKeeper 集群性能上的下降。

而 RPC 框架的服务发现,在服务节点刚上线时,服务调用方是可以容忍在一段时间之后
(比如几秒钟之后)发现这个新上线的节点的。毕竟服务节点刚上线之后的几秒内,甚至更长的一段时间内没有接收到请求流量,对整个服务集群是没有什么影响的,所以我们可以牺牲掉 CP(强制一致性),而选择 AP(最终一致),来换取整个注册中心集群的性能和稳定性。

img

七、健康检查

使用频率适中的心跳去检测目标机器的健康状态

  • 健康状态:建立连接成功,并且心跳探活也一直成功;
  • 亚健康状态:建立连接成功,但是心跳请求连续失败;
  • 死亡状态:建立连接失败。

可以使用可用率来作为健康状态的量化标准

可用率 = 一个时间窗口内接口调用成功次数 / 总调用次数

当可用率低于某个比例,就认为这个节点存在问题,把它挪到亚健康列表,这样既考虑了高低频的调用接口,也兼顾了接口响应时间不同的问题。

八、路由和负载均衡

对于服务调用方来说,一个接口会有多个服务提供方同时提供服务,所以我们的 RPC 在每次发起请求的时候,都需要从多个服务提供方节点里面选择一个用于发请求的节点。这被称为路由策略。

  • IP 路由:最简单的当然是 IP 路由,因为服务上线后,会暴露服务到注册中心,将自身 IP、端口等元信息告知注册中心。这样消费方就可以在向注册中心请求服务地址时,感知其存在。
  • 参数路由:但有时,会有一些复杂的场景,如:灰度发布、定点调用,我们并不希望上线的服务被所有消费者感知,为了更加细粒度的控制,可以使用参数路由。通过参数控制通信的路由策略。

除了特殊场景的路由策略以外,对于机器中多个服务方,如何选择调用哪个服务节点,可以应用负载均衡策略。RPC 负载均衡策略一般包括随机、轮询、一致性 Hash、最近最少连接等。

img

负载均衡详情可以参考:负载均衡基本原理

超时重试

超时重试机制是指:当调用端发起的请求失败或超时未收到响应时,RPC 框架自身可以进行重试,再重新发送请求,用户可以自行设置是否开启重试以及重试的次数。

img

限流、降级、熔断

限流方案:Redis + lua、Sentinel

熔断方案:Hystrix

优雅启动关闭

如何避免服务停机带来的业务损失:

img

如何避免流量打到没有启动完成的节点:

img

九、容错处理

异常重试

就是当调用端发起的请求失败时,RPC 框架自身可以进行重试,再重新发送请求,用户可以自行设置是否开启重试以及重试的次数。

当然,不是所有的异常都要触发重试,只有符合重试条件的异常才能触发重试,比如网络超时异常、网络连接异常等等(这个需要 RPC 去判定)。

注意:有时网络可能发生抖动,导致请求超时,这时如果 RPC 触发超时重试,会触发业务逻辑重复执行,如果接口没有幂等性设计,就可能引发问题。如:重发写表。

重试超时时间

连续的异常重试可能会出现一种不可靠的情况,那就是连续的异常重试并且每次处理的请求时间比较长,最终会导致请求处理的时间过长,超出用户设置的超时时间。

解决这个问题最直接的方式就是,在每次重试后都重置一下请求的超时时间。

当调用端发起 RPC 请求时,如果发送请求发生异常并触发了异常重试,我们可以先判定下这个请求是否已经超时,如果已经超时了就直接返回超时异常,否则就先重置下这个请求的超时时间,之后再发起重试。

在所有发起重试、负载均衡选择节点的时候,去掉重试之前出现过问题的那个节点,以保证重试的成功率。

业务异常

RPC 框架是不会知道哪些业务异常能够去进行异常重试的,我们可以加个重试异常的白名
单,用户可以将允许重试的异常加入到这个白名单中。当调用端发起调用,并且配置了异常重试策略,捕获到异常之后,我们就可以采用这样的异常处理策略。如果这个异常是 RPC 框架允许重试的异常,或者这个异常类型存在于可重试异常的白名单中,我们就允许对这个请求进行重试。


综上,一个可靠的 RPC 容错处理机制如下:

img

十、优雅上线下线

如何避免服务停机带来的业务损失?

优雅下线

当服务提供方正在关闭,如果这之后还收到了新的业务请求,服务提供方直接返回一个特定的异常给调用方(比如 ShutdownException)。这个异常就是告诉调用方“我已经收到这个请求了,但是我正在关闭,并没有处理这个请求”,然后调用方收到这个异常响应后,RPC 框架把这个节点从健康列表挪出,并把请求自动重试到其他节点,因为这个请求是没有被服务提供方处理过,所以可以安全地重试到其他节点,这样就可以实现对业务无损。

在 Java 语言里面,对应的是 Runtime.addShutdownHook 方法,可以注册关闭的钩子。在 RPC 启动的时候,我们提前注册关闭钩子,并在里面添加了两个处理程序,一个负责开启关闭标识,一个负责安全关闭服务对象,服务对象在关闭的时候会通知调用方下线节点。同时需要在我们调用链里面加上挡板处理器,当新的请求来的时候,会判断关闭标识,如果正在关闭,则抛出特定异常。

image-20200718205036132

优雅上线

启动预热

启动预热,就是让刚启动的服务提供方应用不承担全部的流量,而是让它被调用的次数随着时间的移动慢慢增加,最终让流量缓和地增加到跟已经运行一段时间后的水平一样。

首先,在真实环境中机器都会默认开启 NTP 时间同步功能,来保证所有机器时间的一致性。

调用方通过服务发现,除了可以拿到 IP 列表,还可以拿到对应的启动时间。我们需要把这个时间作用在负载均衡上。

image-20200718210228814

通过这个小逻辑的改动,我们就可以保证当服务提供方运行时长小于预热时间时,对服务提供方进行降权,减少被负载均衡选择的概率,避免让应用在启动之初就处于高负载状态,从而实现服务提供方在启动后有一个预热的过程。

延迟暴露

服务提供方应用在没有启动完成的时候,调用方的请求就过来了,而调用方请求过来的原因是,服务提供方应用在启动过程中把解析到的 RPC 服务注册到了注册中心,这就导致在后续加载没有完成的情况下服务提供方的地址就被服务调用方感知到了。

为了解决这个问题,需要在应用启动加载、解析 Bean 的时候,如果遇到了 RPC 服务的 Bean,只先把这个
Bean 注册到 Spring-BeanFactory 里面去,而并不把这个 Bean 对应的接口注册到注册中心,只有等应用启动完成后,才把接口注册到注册中心用于服务发现,从而实现让服务调用方延迟获取到服务提供方地址。

具体如何实现呢?

我们可以在服务提供方应用启动后,接口注册到注册中心前,预留一个 Hook 过程,让用户可以实现可扩展的
Hook 逻辑。用户可以在 Hook 里面模拟调用逻辑,从而使 JVM 指令能够预热起来,并且用户也可以在 Hook 里面事先预加载一些资源,只有等所有的资源都加载完成后,最后才把接口注册到注册中心。

image-20200718210019621

十一、限流熔断

限流算法有很多,比如最简单的计数器,还有可以做到平滑限流的滑动窗口、漏斗算法以及令牌桶算法等等。其中令牌桶算法最为常用。

服务端主要是通过限流来进行自我保护,我们在实现限流时要考虑到应用和 IP 级别,方便我们在服务治理的时候,对部分访问量特别大的应用进行合理的限流。

服务端的限流阈值配置都是作用于单机的,而在有些场景下,例如对整个服务设置限流阈值,服务进行扩容时,
限流的配置并不方便,我们可以在注册中心或配置中心下发限流阈值配置的时候,将总服务节点数也下发给服务节点,让 RPC 框架自己去计算限流阈值。

我们还可以让 RPC 框架的限流模块依赖一个专门的限流服务,对服务设置限流阈值进行精准地控制,但是这种方式依赖了限流服务,相比单机的限流方式,在性能和耗时上有劣势。

调用端可以通过熔断机制进行自我保护,防止调用下游服务出现异常,或者耗时过长影响调
用端的业务逻辑,RPC 框架可以在动态代理的逻辑中去整合熔断器,实现 RPC 框架的熔断
功能。

十二、业务分组

img

在 RPC 里面我们可以通过分组的方式人为地给不同的调用方划分出不同的小集群,从而实现调用方流量隔离的效果,保障我们的核心业务不受非核心业务的干扰。但我们在考虑问题的时候,不能顾此失彼,不能因为新加一个的功能而影响到原有系统的稳定性。

其实我们不仅可以通过分组把服务提供方划分成不同规模的小集群,我们还可以利用分组完成一个接口多种实现的功能。正常情况下,为了方便我们自己管理服务,我一般都会建议每个接口完成的功能尽量保证唯一。但在有些特殊场景下,两个接口也会完全一样,只是具体实现上有那么一点不同,那么我们就可以在服务提供方应用里面同时暴露两个相同接口,但只是接口分组不一样罢了。

动态分组

分组可以帮助服务提供方实现调用方的隔离。但是因为调用方流量并不是一成不变的,而且还可能会因为突发事件导致某个分组的流量溢出,而在整个大集群还有富余能力的时候,又因为分组隔离不能为出问题的集群提供帮助。

为了解决这种突发流量的问题,我们提供了一种更高效的方案,可以实现分组的快速伸缩。事实上我们还可以利用动态分组解决分组后给每个分组预留机器冗余的问题,我们没有必要把所有冗余的机器都分配到分组里面,我们可以把这些预留的机器做成一个共享的池子,从而减少整体预留的实例数量。

十三、链路跟踪

分布式链路跟踪就是将一次分布式请求还原为一个完整的调用链路,我们可以在整个调用链路中跟踪到这一次分布式请求的每一个环节的调用情况,比如调用是否成功,返回什么异常,调用的哪个服务节点以及请求耗时等等。

Trace 就是代表整个链路,每次分布式都会产生一个 Trace,每个 Trace 都有它的唯一标识即 TraceId,在分布式链路跟踪系统中,就是通过 TraceId 来区分每个 Trace 的。
Span 就是代表了整个链路中的一段链路,也就是说 Trace 是由多个 Span 组成的。在一个 Trace 下,每个 Span 也都有它的唯一标识 SpanId,而 Span 是存在父子关系的。还是以讲过的例子为例子,在 A->B->C->D 的情况下,在整个调用链中,正常情况下会产生 3 个 Span,分别是 Span1(A->B)、Span2(B->C)、Span3(C->D),这时 Span3 的父 Span 就是 Span2,而 Span2 的父 Span 就是 Span1。

RPC 在整合分布式链路跟踪需要做的最核心的两件事就是“埋点”和“传递”。

我们前面说是因为各子应用、子服务间复杂的依赖关系,所以通过日志难定位问题。那我们就想办法通过日志定位到是哪个子应用的子服务出现问题就行了。

其实,在 RPC 框架打印的异常信息中,是包括定位异常所需要的异常信息的,比如是哪类异常引起的问题(如序列化问题或网络超时问题),是调用端还是服务端出现的异常,调用端与服务端的 IP 是什么,以及服务接口与服务分组都是什么等等。具体如下图所示:

img

十四、泛化调用

在一些特定场景下,需要在没有接口的情况下进行 RPC 调用。例如:

场景一:搭建一个统一的测试平台,可以让各个业务方在测试平台中通过输入接口、分组名、方法名以及参数值,在线测试自己发布的 RPC 服务。

img

场景二:搭建一个轻量级的服务网关,可以让各个业务方用 HTTP 的方式,通过服务网关调用其它服务。

img

为了解决这些场景的问题,可以使用泛化调用。

就是 RPC 框架提供统一的泛化调用接口(GenericService),调用端在创建 GenericService 代理时指定真正需要调用的接口的接口名以及分组名,通过调用 GenericService 代理的 $invoke 方法将服务端所需要的所有信息,包括接口名、业务分组名、方法名以及参数信息等封装成请求消息,发送给服务端,实现在没有接口的情况下进行
RPC 调用的功能。

class GenericService {
Object $invoke(String methodName, String[] paramTypes, Object[] params);
CompletableFuture<Object> $asyncInvoke(String methodName, String[] paramTypes
}

而通过泛化调用的方式发起调用,由于调用端没有服务端提供方提供的接口 API,不能正常地进行序列化与反序列化,我们可以为泛化调用提供专属的序列化插件,来解决实际问题。

时钟轮

时钟轮这个机制很好地解决了定时任务中,因每个任务都创建一个线程,导致的创建过多线程的问题,以及一个线程扫描所有的定时任务,让 CPU 做了很多额外的轮询遍历操作而浪费 CPU 的问题。

时钟轮的实现机制就是模拟现实生活中的时钟,将每个定时任务放到对应的时间槽位上,这样可以减少扫描任务时对其它时间槽位定时任务的额外遍历操作。

在时间轮的使用中,有些问题需要你额外注意:

时间槽位的单位时间越短,时间轮触发任务的时间就越精确。例如时间槽位的单位时间是 10 毫秒,那么执行定时任务的时间误差就在 10 毫秒内,如果是 100 毫秒,那么误差就在 100 毫秒内。

时间轮的槽位越多,那么一个任务被重复扫描的概率就越小,因为只有在多层时钟轮中的任务才会被重复扫描。比如一个时间轮的槽位有 1000 个,一个槽位的单位时间是 10 毫秒,那么下一层时间轮的一个槽位的单位时间就是 10 秒,超过 10 秒的定时任务会被放到下一层时间轮中,也就是只有超过 10 秒的定时任务会被扫描遍历两次,但如果槽位是 10 个,那么超过 100 毫秒的任务,就会被扫描遍历两次。

结合这些特点,我们就可以视具体的业务场景而定,对时钟轮的周期和时间槽数进行设置。

在 RPC 框架中,只要涉及到定时任务,我们都可以应用时钟轮,比较典型的就是调用端的超时处理、调用端与服务端的启动超时以及定时心跳等等。

流量回放

所谓的流量就是某个时间段内的所有请求,我们通过某种手段把发送到 A 应用的所有请求录制下来,然后把这些请求统一转发到 B 应用,让 B 应用接收到的请求参数跟 A 应用保持一致,从而实现 A 接收到的请求在 B 应用里面重新请求了一遍。整个过程称之为“流量回放”。

流量回放可以做什么?

为了保障应用升级后,我们的业务行为还能保持和升级前一样,我们在大多数情况下都是依靠已有的 TestCase 去验证,但这种方式在一定程度上并不是完全可靠的。最可靠的方式就是引入线上 Case 去验证改造后的应用,把线上的真实流量在改造后的应用里面进行回放,这样不仅节省整个上线时间,还能弥补手动维护 Case 存在的缺陷。

应用引入了 RPC 后,所有的请求流量都会被 RPC 接管,所以我们可以很自然地在 RPC 里面支持流量回放功能。虽然这个功能本身并不是 RPC 的核心功能,但对于使用 RPC 的人来说,他们有了这个功能之后,就可以更放心地升级自己的应用了。

RPC 高级

RPC 性能

如何提升单机吞吐量?

大多数情况下,影响到 RPC 调用的吞吐量的原因也就是业务逻辑处理慢了,CPU 大部分时间都在等待资源。

为了解决等待的耗时,可以使用异步。异步可以使用 Future 或 Callback 方式,Future 最为简单。

image-20200719081257192

另外,我们可以通过对 CompletableFuture 的支持,实现 RPC 调用在调用端与服务端之间的完全异步,同时提升两端的单机吞吐量。

RPC 安全

虽然 RPC 经常用于解决内网应用之间的调用,内网环境相对公网也没有那么恶劣,但我们也有必要去建立一套可控的安全体系,去防止一些错误行为。对于 RPC 来说,我们所关心的安全问题不会有公网应用那么复杂,我们只要保证让服务调用方能拿到真实的服务提供方 IP 地址集合,且服务提供方可以管控调用自己的应用就够了。

服务提供方应用里面放一个用于 HMAC 签名的私钥,在授权平台上用这个私钥为申请调用的调用方应用进行签名,这个签名生成的串就变成了调用方唯一的身份。服务提供方在收到调用方的授权请求之后,我们只要需要验证下这个签名跟调用方应用信息是否对应得上就行了,这样集中式授权的瓶颈也就不存在了。

参考资料

效率提升方法论

在智力水平相当的前提下,常常会发现:有些人做事,事倍功半;有些人做事,事半功倍。

做任何事,如果有了清晰的思路,正确的指导方针,肯定是比毫无头绪要高效很多。所以,现实中,常常会看到这样一种现象,优秀的人,往往全面优秀,干什么都出彩;而平庸的人,做什么都出不了成绩。

大多数人不是天才,想要变得优秀,唯一的途径就是:按照正确的习惯(方式方法),坚持不懈的努力进步(自律)。

我们日复一日做的事情,决定了我们是怎样的人。因此所谓卓越,并非指行为,而是习惯

We are what we repeatedly do. Excellence, then, is not an act, but a habit.

——莎士比亚

5W2H

5W2H 分析法是一种思考问题的启发式思维方式。5W2H 分析法用五个以 W 开头的英语单词和两个以 H 开头的英语单词进行设问,得到关键性问题的答案,最后总结归纳出问题的目标、解决思路、处理方法等,这就叫做 5W2H 法。

5W2H 分析法又叫七问分析法,是二战中美国陆军兵器修理部首创。这种分析法广泛用于企业管理和技术活动,对于决策和执行性的活动措施也非常有帮助,也有助于弥补考虑问题的疏漏。

5W2H 分析法的意义在于:避免遇到一个问题后,不知从何入手。通过设问方式,由点成线,由线成面,把问题的关键点串联起来,整理出问题的解决思路。

5W2H

  • why - 为什么?为什么要这么做?理由何在?原因是什么?

  • what - 是什么?目的是什么?作什么工作?

  • where - 何处?在哪里做?从哪里入手?

  • when - 何时?什么时间完成?什么时机最适宜?

  • who - 谁?有谁来承担?谁来完成?谁负责?

  • how - 怎么做?如何提高效率?如何实施?方法怎么样?

  • how much - 多少?做到什么程度?数量如何?质量水平如何?费用产出如何?

四象限原则

四象限原则是一种时间管理方式

有首歌唱出了大多数职场人的心声:时间都去哪儿了?

事情、任务太多,时间太少,分身乏术。

时间管理四象限法则是美国的管理学家科维提出的一个时间管理的理论,按处理顺序划分为:紧急又重要、重要不紧急、紧急不重要、不紧急不重要。

img

  • 第一象限(重要而紧急

    • 案例:应付难缠的客户、准时完成工作、住院开刀等等。
    • 这是考验我们的经验、判断力的时刻,也是可以用心耕耘的园地。如果荒废了,我们很会可能变成行尸走肉。但我们也不能忘记,很多重要的事都是因为一拖再拖或事前准备不足,而变成迫在眉睫。
    • 该象限的本质是缺乏有效的工作计划导致本处于“重要但不紧急”第二象限的事情转变过来的,这也是传统思维状态下的管理者的通常状况,就是“忙”。
  • 第二象限(重要但不紧急)

    • 案例:学习新技能、建立人际关系、保持身体健康、长期的规划、问题的发掘与预防、参加培训、向上级提出问题处理的建议等等事项。
    • 荒废这个领域将使第一象限日益扩大,使我们陷入更大的压力,在危机中疲于应付。反之,多投入一些时间在这个领域有利于提高实践能力,缩小第一象限的范围。做好事先的规划、准备与预防措施,很多急事将无从产生。这个领域的事情不会对我们造成催促力量,所以必须主动去做,这是发挥个人领导力的领域。
    • 这更是传统低效管理者与高效卓越管理者的重要区别标志,建议管理者要把 80%的精力投入到该象限的工作,以使第一象限的“急”事无限变少,不再瞎“忙”。
  • 第三象限(紧急但不重要)

    • 案例:电话、会议、突发的访客都属于这一类。
    • 表面看似第一象限,因为迫切的呼声会让我们产生“这件事很重要”的错觉——实际上就算重要也是对别人而言。我们花很多时间在这个里面打转,自以为是在第一象限,其实不过是在满足别人的期望与标准。
  • 第四象限(不紧急也不重要)

    • 案例:阅读无聊小说、看毫无内容的电视节目、办公室聊天、刷微博、刷朋友圈等。
    • 简而言之就是浪费生命,所以根本不值得花半点时间在这个象限。但我们往往在一、三象限来回奔走,忙得焦头烂额,不得不到第四象限去疗养一番再出发。这部分范围倒不见得都是休闲活动,因为真正有创造意义的休闲活动是很有价值的。然而像阅读令人上瘾的无聊小说、毫无内容的电视节目、办公室聊天等。这样的休息不但不是为了走更长的路,反而是对身心的毁损,刚开始时也许有滋有味,到后来你就会发现其实是很空虚的。

Travis CI 入门教程

一、简介

Travis CI 提供的是持续集成服务(Continuous Integration,简称 CI)。我们在软件开发过程中,有构建、测试、部署这些必不可少的步骤,而这些会花掉我们很多的时间。为了提高软件开发的效率,现在涌现了很多自动化工具。Travis CI 是目前市场份额最大的一个,而且有很详细的文档以及可以和 Github 很好的对接。

Travis CI 是 Github 项目最流行的持续集成工具。

持续集成

持续集成(Continuous integration,缩写 CI)是一种软件工程流程,即团队开发成员经常集成他们的工作,通常每个成员每天至少集成一次,也就意味着每天可能会发生多次集成。每次集成都通过自动化的构建(包括编译,发布,自动化测试)来验证,从而尽早地发现集成错误。

二、使用

加载 Github 项目

首先打开官方网站 travis-ci.org,然后使用 Github 账号登入 Travis CI,然后 Travis 中会列出你 Github 上面所有的仓库,以及你所属于的组织。

然后,勾选你需要 Travis 帮你自动构建的仓库,打开仓库旁边的开关,打开以后,Travis 就会监听这个仓库的所有变化了。

travis-ci-1

配置 .travis.yml

Travis 要求项目的根目录下面,必须有一个 .travis.yml 文件。这是配置文件,指定了 Travis 的行为。该文件必须保存在 Github 仓库里面,一旦代码仓库有新的 Commit,Travis 就会去找这个文件,执行里面的命令。

所以呢,我们就可以在这个文件里,配置我们任务(Travis 监测到仓库有 commit 后会自动执行)。

一个简单的 .travis.yml 文件如下:

language: node_jsscript: true

所以呢,我在 .travis.yml 里,配置了一个执行脚本的任务;那么现在 Travis 监测到我仓库有 commit 后就会找到 .travis.yml 这个文件,然后就执行了我的那个脚本了。

install 字段

install 字段用来指定安装脚本,如果有多个脚本,可以写成下面的形式。

install:  - command1  - command2

上面代码中,如果 command1 失败了,整个构建就会停下来,不再往下进行
如果不需要安装,即跳过安装阶段,就直接设为 true

install: true

script 字段

script 字段用来配置构建或者测试脚本,如果有多个脚本,可以写成下面的形式。

script:  - command1  - command2

注意,scriptinstall 不一样,如果 command1 失败,command2 会继续执行。但是,整个构建阶段的状态是失败。

如果 command2 只有在 command1 成功后才能执行,就要写成下面这样。

script: command1 && command2

三、构建

四、部署

现在脚本是由 Travis CI 来执行的,部署的时候,怎么让 Travis 有权限往 Github 提交代码呢?

Github 有提供一个 Personal access tokens,这个 Token 与 账号密码 以及 SSH Keys 同样具有 Github 写入能力。

前往 Github 帐号 Settings 页面,在左侧选择 Personal Access Token,然后在右侧面板点击 “Generate new token” 来新建一个 Token。需要注意的是,创建完的 Token 只有第一次可见,之后再访问就无法看见(只能看见他的名称),因此要保存好这个值。

travis-ci-2

那么,这个 Token 怎么使用呢。

方案一、

一个比较方便快捷的方式,是通过 Travis 网站,写在每个仓库的设置页面里,有一个 Environment Variables 的配置项,给我们的 Token 起一个名字 gh_token 添加进去。这样以来,脚本内部就可以使用这个环境变量了。
travis-ci-1
你可以在你脚本内部使用 ${gh_token} 的形式来使用这个 Token 了。【当然了,你还可以添加其他的环境变量进去。】【官方文档在这里

使用 Personal access tokens 向 GitHub 提交代码的命令格式如下:

# ${GH_TOKEN} 对应就是 Personal access tokens , GH_TOKEN 是环境变量名# ${GH_REF} 对应的是你的 Github 仓库地址,GH_REF 是变量名git push -f "https://${GH_TOKEN}@${GH_REF}" master:gh-pages

这里需要注意的是:
1、GitHub 生成的这个 Token ,只有生成的时候可以看到明文,后面就看不到明文了,所以你使用的时候最好一次操作成功。
2、Travis CI 中添加 Token 时,记得用密文,要不然在 build log 中是可以被看到的。

方案二、

你还可以使用 Travis CI 提供的加密工具来加密我们的这个 Token。加密原理机制如下:

travis-ci-encrypt

首先,安装 Ruby 的包 travis

# 安装 Travis CI 命令行工具$ gem install travis

然后,就可以用 travis encrypt 命令加密信息。
在项目的根目录下,执行下面的命令。

$ travis encrypt name=secretvalue

上面命令中,gh_token 是要加密的变量名,secretvalue 是要加密的变量值。执行以后,屏幕上会输出如下信息。

secure: "... encrypted data ..."

现在,就可以把这一行加入 .travis.yml

env:  global:    - GH_REF: github.com/Neveryu/xxxxx.git    - secure: "... entrypted data ..."

然后,脚本里面就可以使用环境变量 gh_token 了,Travis 会在运行时自动对它解密。

# ${gh_token} 对应就是 Personal access tokens , gh_token 是环境变量名# ${GH_REF} 对应的是你的 Github 仓库地址,GH_REF 是变量名git push -f "https://${gh_token}@${GH_REF}" master:gh-pages

travis encrypt 命令的 --add 参数会把输出自动写入 .travis.yml,省掉了修改 env 字段的步骤。

$ travis encrypt name=secretvalue --add

详细信息请看官方文档

可以参考我的 vue-cms 这个项目中的 .travis.yml 文件

FAQ

如何显示 Status Image

Build Status

travis-ci-4

如何跳过自动构建

如果 commit 不想让 Travis 构建,那么就在 commit message 里加上 [ci skip] 就行了。

git commit -m "[ci skip] commit message"

权限问题

如果遇到脚本权限不够的提示或者问题,你可以给你的脚本加上权限:

chmod u+x deploy.sh

或者在 .travis.yml 里加:

before_install:  - chmod u+x deploy.sh

参考资料

网络通信之 VPN

📦 本文已归档到:「blog

img

简介

虚拟专用网络(VPN)的功能是:在公用网络上建立专用网络,进行加密通讯。在企业网络中有广泛应用。VPN 网关通过对数据包的加密和数据包目标地址的转换实现远程访问。VPN 可通过服务器、硬件、软件等多种方式实现。

VPN 属于远程访问技术,简单地说就是利用公用网络架设专用网络。例如某公司员工出差到外地,他想访问企业内网的服务器资源,这种访问就属于远程访问。
在传统的企业网络配置中,要进行远程访问,传统的方法是租用 DDN(数字数据网)专线或帧中继,这样的通讯方案必然导致高昂的网络通讯和维护费用。对于移动用户(移动办公人员)与远端个人用户而言,一般会通过拨号线路(Internet)进入企业的局域网,但这样必然带来安全上的隐患。
让外地员工访问到内网资源,利用 VPN 的解决方法就是在内网中架设一台 VPN 服务器。外地员工在当地连上互联网后,通过互联网连接 VPN 服务器,然后通过 VPN 服务器进入企业内网。为了保证数据安全,VPN 服务器和客户机之间的通讯数据都进行了加密处理。有了数据加密,就可以认为数据是在一条专用的数据链路上进行安全传输,就如同专门架设了一个专用网络一样,但实际上 VPN 使用的是互联网上的公用链路,因此 VPN 称为虚拟专用网络,其实质上就是利用加密技术在公网上封装出一个数据通讯隧道。有了 VPN 技术,用户无论是在外地出差还是在家中办公,只要能上互联网就能利用 VPN 访问内网资源,这就是 VPN 在企业中应用得如此广泛的原因。

VPN 的作用

隐藏 IP 和位置

img

VPN 可以隐藏使用者的 IP 地址和位置。

使用 VPN 的最常见原因之一是屏蔽您的真实 IP 地址。

您的 IP 地址是由 ISP 分配的唯一数字地址。 您在线上所做的所有事情都链接到您的 IP 地址,因此可以用来将您与在线活动进行匹配。 大多数网站记录其访问者的 IP 地址。

广告商还可以使用您的 IP 地址,根据您的身份和浏览历史为您提供有针对性的广告。

连接到 VPN 服务器时,您将使用该 VPN 服务器的 IP 地址。 您访问的任何网站都会看到 VPN 服务器的 IP 地址,而不是您自己的。

您将能够绕过 IP 地址阻止并浏览网站,而不会将您的活动作为一个个人追溯到您。

通信加密

img

使用 VPN 时,可以对信息进行加密,使得密码,电子邮件,照片,银行数据和其他敏感信息不会被拦截。

如果在公共场所使用公共 WiFi 连接网络时,敏感数据有被盗的风险。黑客可以利用开放和未加密的网络来窃取重要数据,例如您的密码,电子邮件,照片,银行数据和其他敏感信息。

VPN 可以加密信息,使黑客更难以拦截和窃取数据。

翻墙

img

轻松解除对 Facebook 和 Twitter,Skype,YouTube 和 Gmail 等网站和服务的阻止。 即使您被告知您所在的国家/地区不可用它,或者您所在的学校或办公室网络限制访问,也可以获取所需的东西。

某些服务(例如 Netflix 或 BBC iPlayer)会根据您访问的国家/地区限制访问内容。使用 VPN 可以绕过这些地理限制并解锁“隐藏”内容的唯一可靠方法。

避免被监听

img

使用 VPN 可以向政府、ISP、黑客隐藏通信信息。

您的 Internet 服务提供商(ISP)可以看到您访问的所有网站,并且几乎可以肯定会记录该信息。

在某些国家/地区,ISP 需要长时间收集和存储用户数据,并且政府能够访问,存储和搜索该信息。

在美国,英国,澳大利亚和欧洲大部分地区就是这种情况,仅举几例。

由于 VPN 会加密从设备到 VPN 服务器的互联网流量,因此您的 ISP 或任何其他第三方将无法监视您的在线活动。

要了解有关监视技术和全球大规模监视问题的更多信息,请访问 EFF 和 Privacy International。 您还可以在此处找到全球监视披露的更新列表。

工作原理

VPN 会在您的设备和私人服务器之间建立私人和加密的互联网连接。 这意味着您的数据无法被 ISP 或任何其他第三方读取或理解。 然后,私有服务器将您的流量发送到您要访问的网站或服务上。

img

VPN 的基本处理过程如下:

  1. 要保护主机发送明文信息到其他 VPN 设备。
  2. VPN 设备根据网络管理员设置的规则,确定是对数据进行加密还是直接传输。
  3. 对需要加密的数据,VPN 设备将其整个数据包(包括要传输的数据、源 IP 地址和目的 lP 地址)进行加密并附上数据签名,加上新的数据报头(包括目的地 VPN 设备需要的安全信息和一些初始化参数)重新封装。
  4. 将封装后的数据包通过隧道在公共网络上传输。
  5. 数据包到达目的 VPN 设备后,将其解封,核对数字签名无误后,对数据包解密。

VPN 协议

img

  • OpenVPN

  • IKEv2 / IPSec

  • SSTP

  • PPTP

  • Wireguard

VPN 服务

你可以选择付费 VPN 或自行搭建 VPN。

VPN 服务商:

开源 VPN:

参考资料

深入剖析共识性算法 Paxos

📦 本文已归档到:「blog

Paxos 是一种基于消息传递且具有容错性的共识性(consensus)算法。

Paxos 算法解决的问题正是分布式一致性问题。在一个节点数为 N 的分布式集群中,只要半数以上的节点(N/2 + 1)还正常工作,整个系统仍可以正常工作。

img

一、Paxos 背景

Paxos 是 Leslie Lamport 于 1990 年提出的一种基于消息传递且具有高度容错特性的共识(consensus)算法。

为描述 Paxos 算法,Lamport 虚拟了一个叫做 Paxos 的希腊城邦,这个岛按照议会民主制的政治模式制订法律,但是没有人愿意将自己的全部时间和精力放在这种事情上。所以无论是议员,议长或者传递纸条的服务员都不能承诺别人需要时一定会出现,也无法承诺批准决议或者传递消息的时间。

二、Basic Paxos 算法

角色

Paxos 将分布式系统中的节点分为以下角色:

  • 提议者(Proposer):发出提案(Proposal)。Proposal 信息包括提案编号 (Proposal ID) 和提议的值 (Value)。
  • 决策者(Acceptor):参与决策,回应 Proposer 的提案。收到 Proposal 后可以接受提案,若 Proposal 获得多数 Acceptor 的接受,则称该 Proposal 被批准。
  • 学习者(Learner):不参与决策,从 Proposers/Acceptors 学习最新达成一致的提案(Value)。

在复制状态机中,每个副本都同时具有 Proposer、Acceptor、Learner 三种角色。

img

算法

Paxos 算法通过一个决议分为两个阶段(Learn 阶段之前决议已经形成):

  1. 第一阶段:Prepare 阶段。Proposer 向 Acceptors 发出 Prepare 请求,Acceptors 针对收到的 Prepare 请求进行 Promise 承诺。
  2. 第二阶段:Accept 阶段。Proposer 收到多数 Acceptors 承诺的 Promise 后,向 Acceptors 发出 Propose 请求,Acceptors 针对收到的 Propose 请求进行 Accept 处理。
  3. 第三阶段:Learn 阶段。Proposer 在收到多数 Acceptors 的 Accept 之后,标志着本次 Accept 成功,决议形成,将形成的决议发送给所有 Learners。

Paxos 算法流程中的每条消息描述如下:

  • Prepare: Proposer 生成全局唯一且递增的 Proposal ID (可使用时间戳加 Server ID),向所有 Acceptors 发送 Prepare 请求,这里无需携带提案内容,只携带 Proposal ID 即可。

  • Promise: Acceptors 收到 Prepare 请求后,做出“两个承诺,一个应答”。

    • 两个承诺:

      • 不再接受 Proposal ID 小于等于当前请求的 Prepare 请求。
      • 不再接受 Proposal ID 小于当前请求的 Propose 请求。
    • 一个应答:

      • 不违背以前作出的承诺下,回复已经 Accept 过的提案中 Proposal ID 最大的那个提案的 Value 和 Proposal ID,没有则返回空值。
  • Propose: Proposer 收到多数 Acceptors 的 Promise 应答后,从应答中选择 Proposal ID 最大的提案的 Value,作为本次要发起的提案。如果所有应答的提案 Value 均为空值,则可以自己随意决定提案 Value。然后携带当前 Proposal ID,向所有 Acceptors 发送 Propose 请求。

  • Accept: Acceptor 收到 Propose 请求后,在不违背自己之前作出的承诺下,接受并持久化当前 Proposal ID 和提案 Value。

  • Learn: Proposer 收到多数 Acceptors 的 Accept 后,决议形成,将形成的决议发送给所有 Learners。

实例

Paxos 算法实例 1

下面举几个例子,实例 1 如下图:

img

图中 P 代表 Prepare 阶段,A 代表 Accept 阶段。3.1 代表 Proposal ID 为 3.1,其中 3 为时间戳,1 为 Server ID。X 和 Y 代表提议 Value。

实例 1 中 P 3.1 达成多数派,其 Value(X)被 Accept,然后 P 4.5 学习到 Value(X),并 Accept。

imgPaxos 算法实例 2

实例 2 中 P 3.1 没有被多数派 Accept(只有 S3 Accept),但是被 P 4.5 学习到,P 4.5 将自己的 Value 由 Y 替换为 X,Accept(X)。

imgPaxos 算法实例 3

实例 3 中 P 3.1 没有被多数派 Accept(只有 S1 Accept),同时也没有被 P 4.5 学习到。由于 P 4.5 Propose 的所有应答,均未返回 Value,则 P 4.5 可以 Accept 自己的 Value (Y)。后续 P 3.1 的 Accept (X) 会失败,已经 Accept 的 S1,会被覆盖。

Paxos 算法可能形成活锁而永远不会结束,如下图实例所示:

imgPaxos 算法形成活锁

回顾两个承诺之一,Acceptor 不再应答 Proposal ID 小于等于当前请求的 Prepare 请求。意味着需要应答 Proposal ID 大于当前请求的 Prepare 请求。

两个 Proposers 交替 Prepare 成功,而 Accept 失败,形成活锁(Livelock)。

三、Multi Paxos 算法

Basic Paxos 的问题

Basic Paxos 有以下问题,导致它不能应用于实际:

  • Basic Paxos 算法只能对一个值形成决议
  • Basic Paxos 算法会消耗大量网络带宽。Basic Paxos 中,决议的形成至少需要两次网络通信,在高并发情况下可能需要更多的网络通信,极端情况下甚至可能形成活锁。如果想连续确定多个值,Basic Paxos 搞不定了。

Multi Paxos 的改进

Multi Paxos 正是为解决以上问题而提出。Multi Paxos 基于 Basic Paxos 做了两点改进:

  • 针对每一个要确定的值,运行一次 Paxos 算法实例(Instance),形成决议。每一个 Paxos 实例使用唯一的 Instance ID 标识。
  • 在所有 Proposer 中选举一个 Leader,由 Leader 唯一地提交 Proposal 给 Acceptor 进行表决。这样没有 Proposer 竞争,解决了活锁问题。在系统中仅有一个 Leader 进行 Value 提交的情况下,Prepare 阶段就可以跳过,从而将两阶段变为一阶段,提高效率。

Multi Paxos 首先需要选举 Leader,Leader 的确定也是一次决议的形成,所以可执行一次 Basic Paxos 实例来选举出一个 Leader。选出 Leader 之后只能由 Leader 提交 Proposal,在 Leader 宕机之后服务临时不可用,需要重新选举 Leader 继续服务。在系统中仅有一个 Leader 进行 Proposal 提交的情况下,Prepare 阶段可以跳过。

Multi Paxos 通过改变 Prepare 阶段的作用范围至后面 Leader 提交的所有实例,从而使得 Leader 的连续提交只需要执行一次 Prepare 阶段,后续只需要执行 Accept 阶段,将两阶段变为一阶段,提高了效率。为了区分连续提交的多个实例,每个实例使用一个 Instance ID 标识,Instance ID 由 Leader 本地递增生成即可。

Multi Paxos 允许有多个自认为是 Leader 的节点并发提交 Proposal 而不影响其安全性,这样的场景即退化为 Basic Paxos。

Chubby 和 Boxwood 均使用 Multi Paxos。ZooKeeper 使用的 Zab 也是 Multi Paxos 的变形。

参考资料

分布式基础原理

img

📦 本文已归档到:「blog

大型网站几乎都是分布式系统。分布式系统的最大难点,在于各节点的状态如何同步。CAP 定理是这方面的基本定理,也是理解分布式系统的起点。

一、拜占庭将军问题

拜占庭将军问题是由莱斯利·兰波特在其同名论文中提出的分布式对等网络通信容错问题。

分布式计算中,不同的节点通过通讯交换信息达成共识而按照同一套协作策略行动。但有时候,系统中的节点可能出错而发送错误的信息,用于传递信息的通讯网络也可能导致信息损坏,使得网络中不同的成员关于全体协作的策略得出不同结论,从而破坏系统一致性。拜占庭将军问题被认为是容错性问题中最难的问题类型之一。

问题描述:

一群拜占庭将军各领一支军队共同围困一座城市。

为了简化问题,军队的行动策略只有两种:进攻(Attack,后面简称 A)或撤退(Retreat,后面简称 R)。如果这些军队不是统一进攻或撤退,就可能会造成灾难性后果,因此将军们必须通过投票来达成一致策略:同进或同退

因为将军们分别在城市的不同方位,所以他们只能通过信使互相联系。在投票过程中,每位将军都将自己的投票信息(A 或 R)通知其他所有将军,这样一来每位将军根据自己的投票和其他所有将军送来的信息就可以分析出共同的投票结果而决定行动策略。

这个抽象模型的问题在于:将军中可能存在叛徒,他们不仅会发出误导性投票,还可能选择性地发送投票信息。

由于将军之间需要通过信使通讯,叛变将军可能通过伪造信件来以其他将军的身份发送假投票。而即使在保证所有将军忠诚的情况下,也不能排除信使被敌人截杀,甚至被敌人间谍替换等情况。因此很难通过保证人员可靠性及通讯可靠性来解决问题。

假使那些忠诚(或是没有出错)的将军仍然能通过多数决定来决定他们的战略,便称达到了拜占庭容错。在此,票都会有一个默认值,若消息(票)没有被收到,则使用此默认值来投票。

上述的故事映射到分布式系统里,将军便成了机器节点,而信差就是通信系统。

二、CAP

CAP 定理是加州大学计算机科学家埃里克·布鲁尔提出来的猜想,后来被证明成为分布式计算领域公认的定理。

CAP 定理又称为 CAP 原则,指的是:在一个分布式系统中, 一致性(C:Consistency)可用性(A:Availability)分区容忍性(P:Partition Tolerance),最多只能同时满足其中两项

分区容错性

分区容错性(Partition Tolerance)指 分布式系统在遇到任何网络分区故障的时候,仍然需要能对外提供一致性和可用性的服务,除非是整个网络环境都发生了故障

大多数分布式系统都分布在多个子网络,每个子网络就叫做一个区(Partition)。分区容错的意思是,区间通信可能失败。比如,一台服务器放在中国,另一台服务器放在美国,这就是两个区,它们之间可能无法通信。

img

上图中,G1 和 G2 是两台跨区的服务器。G1 向 G2 发送一条消息,G2 可能无法收到。系统设计的时候,必须考虑到这种情况。

一般来说,分区容错无法避免,因此可以认为 CAP 的 P 总是成立。CAP 定理告诉我们,剩下的 C 和 A 无法同时做到。

一致性

一致性(Consistency)指的是多个数据副本是否能保持一致的特性。

在一致性的条件下,分布式系统在执行写操作成功后,如果所有用户都能够读取到最新的值,该系统就被认为具有强一致性。

数据一致性又可以分为以下几点:

  • 强一致性 - 数据更新操作结果和操作响应总是一致的,即操作响应通知更新失败,那么数据一定没有被更新,而不是处于不确定状态。
  • 最终一致性 - 即物理存储的数据可能是不一致的,终端用户访问到的数据可能也是不一致的,但系统经过一段时间的自我修复和修正,数据最终会达到一致。

举例来说,某条记录是 v0,用户向 G1 发起一个写操作,将其改为 v1。

img

接下来,用户的读操作就会得到 v1。这就叫一致性。

img

问题是,用户有可能向 G2 发起读操作,由于 G2 的值没有发生变化,因此返回的是 v0。G1 和 G2 读操作的结果不一致,这就不满足一致性了。

img

为了让 G2 也能变为 v1,就要在 G1 写操作的时候,让 G1 向 G2 发送一条消息,要求 G2 也改成 v1。

img

这样的话,用户向 G2 发起读操作,也能得到 v1。

img

可用性

可用性指分布式系统在面对各种异常时可以提供正常服务的能力,可以用系统可用时间占总时间的比值来衡量,4 个 9 的可用性表示系统 99.99% 的时间是可用的。

在可用性条件下,系统提供的服务一直处于可用的状态,对于用户的每一个操作请求总是能够在有限的时间内返回结果。

权衡

在分布式系统中,分区容忍性必不可少,因为需要总是假设网络是不可靠的。因此,CAP 理论实际在是要在可用性和一致性之间做权衡

可用性和一致性往往是冲突的,很难都使它们同时满足。在多个节点之间进行数据同步时,

  • 为了保证一致性(CP),就需要让所有节点下线成为不可用的状态,等待同步完成;
  • 为了保证可用性(AP),在同步过程中允许读取所有节点的数据,但是数据可能不一致。

三、BASE

BASE 是 基本可用(Basically Available)软状态(Soft State)最终一致性(Eventually Consistent) 三个短语的缩写。

BASE 理论是对 CAP 中一致性和可用性权衡的结果,它的理论的核心思想是:即使无法做到强一致性,但每个应用都可以根据自身业务特点,采用适当的方式来使系统达到最终一致性。

img

基本可用

基本可用(Basically Available)指分布式系统在出现故障的时候,保证核心可用,允许损失部分可用性

例如,电商在做促销时,为了保证购物系统的稳定性,部分消费者可能会被引导到一个降级的页面。

软状态

软状态(Soft State)指允许系统中的数据存在中间状态,并认为该中间状态不会影响系统整体可用性,即允许系统不同节点的数据副本之间进行同步的过程存在延时

最终一致性

最终一致性(Eventually Consistent)强调的是系统中所有的数据副本,在经过一段时间的同步后,最终能达到一致的状态

ACID 要求强一致性,通常运用在传统的数据库系统上。而 BASE 要求最终一致性,通过牺牲强一致性来达到可用性,通常运用在大型分布式系统中。

在实际的分布式场景中,不同业务单元和组件对一致性的要求是不同的,因此 ACID 和 BASE 往往会结合在一起使用。

参考资料

深入剖析共识性算法 Raft

📦 本文已归档到:「blog

img

一、Raft 简介

Raft _是一种为了管理日志复制的分布式一致性算法*。

Raft 出现之前,Paxos 一直是分布式一致性算法的标准。Paxos 难以理解,更难以实现。Raft 的设计目标是简化 Paxos,使得算法既容易理解,也容易实现

Paxos 和 Raft 都是分布式一致性算法,这个过程如同投票选举领袖(Leader),参选者(Candidate)需要说服大多数投票者(Follower)投票给他,一旦选举出领袖,就由领袖发号施令。Paxos 和 Raft 的区别在于选举的具体过程不同。

Raft 可以解决分布式 CAP 理论中的 CP,即 一致性(C:Consistency)分区容忍性(P:Partition Tolerance),并不能解决 可用性(A:Availability) 的问题。

分布式一致性

分布式一致性 (distributed consensus) 是分布式系统中最基本的问题,用来保证一个分布式系统的可靠性以及容错能力。简单来说,分布式一致性是指多个服务器的保持状态一致

在分布式系统中,可能出现各种意外(断电、网络拥塞、CPU/内存耗尽等等),使得服务器宕机或无法访问,最终导致无法和其他服务器保持状态一致。为了应对这种情况,就需要有一种一致性协议来进行容错,使得分布式系统中即使有部分服务器宕机或无法访问,整体依然可以对外提供服务。

以容错方式达成一致,自然不能要求所有服务器都达成一致状态,只要超过半数以上的服务器达成一致就可以了。假设有 N 台服务器, 大于等于 N2+1\frac{N}{2}+1 台服务器就算是半数以上了 。

复制状态机

复制状态机(Replicated State Machines) 是指一组服务器上的状态机产生相同状态的副本,并且在一些机器宕掉的情况下也可以继续运行。一致性算法管理着来自客户端指令的复制日志。状态机从日志中处理相同顺序的相同指令,所以产生的结果也是相同的。

img

复制状态机通常都是基于复制日志实现的,如上图。每一个服务器存储一个包含一系列指令的日志,并且按照日志的顺序进行执行。每一个日志都按照相同的顺序包含相同的指令,所以每一个服务器都执行相同的指令序列。因为每个状态机都是确定的,每一次执行操作都产生相同的状态和同样的序列。

保证复制日志相同就是一致性算法的工作了。在一台服务器上,一致性模块接收客户端发送来的指令然后增加到自己的日志中去。它和其他服务器上的一致性模块进行通信来保证每一个服务器上的日志最终都以相同的顺序包含相同的请求,尽管有些服务器会宕机。一旦指令被正确的复制,每一个服务器的状态机按照日志顺序处理他们,然后输出结果被返回给客户端。因此,服务器集群看起来形成一个高可靠的状态机。

实际系统中使用的一致性算法通常含有以下特性:

  • 安全性保证(绝对不会返回一个错误的结果):在非拜占庭错误情况下,包括网络延迟、分区、丢包、冗余和乱序等错误都可以保证正确。
  • 可用性:集群中只要有大多数的机器可运行并且能够相互通信、和客户端通信,就可以保证可用。因此,一个典型的包含 5 个节点的集群可以容忍两个节点的失败。服务器被停止就认为是失败。他们当有稳定的存储的时候可以从状态中恢复回来并重新加入集群。
  • 不依赖时序来保证一致性:物理时钟错误或者极端的消息延迟只有在最坏情况下才会导致可用性问题。
  • 通常情况下,一条指令可以尽可能快的在集群中大多数节点响应一轮远程过程调用时完成。小部分比较慢的节点不会影响系统整体的性能。

RAFT 应用

RAFT 可以做什么?

通过 RAFT 提供的复制状态机,可以解决分布式系统的复制、修复、节点管理等问题。Raft 极大的简化当前分布式系统的设计与实现,让开发者只关注于业务逻辑,将其抽象实现成对应的状态机即可。基于这套框架,可以构建很多分布式应用:

  • 分布式锁服务,比如 Zookeeper
  • 分布式存储系统,比如分布式消息队列、分布式块系统、分布式文件系统、分布式表格系统等
  • 高可靠元信息管理,比如各类 Master 模块的 HA

二、Raft 基础

Raft 将一致性问题分解成了三个子问题:

  • 选举 Leader
  • 日志复制
  • 安全性

在后续章节,会详细讲解这个子问题。现在,先了解一下 Raft 的一些核心概念。

服务器角色

在 Raft 中,任何时刻,每个服务器都处于这三个角色之一 :

  • Leader - 领导者,通常一个系统中是一主(Leader)多从(Follower)。Leader 负责处理所有的客户端请求
  • Follower - 跟随者,不会发送任何请求,只是简单的 响应来自 Leader 或者 Candidate 的请求
  • Candidate - 参选者,选举新 Leader 时的临时角色。

img

💡 图示说明:

  • Follower 只响应来自其他服务器的请求。在一定时限内,如果 Follower 接收不到消息,就会转变成 Candidate,并发起选举。
  • Candidate 向 Follower 发起投票请求,如果获得集群中半数以上的选票,就会转变为 Leader。
  • 在一个 Term 内,Leader 始终保持不变,直到下线了。Leader 需要周期性向所有 Follower 发送心跳消息,以阻止 Follower 转变为 Candidate。

任期

img

Raft 把时间分割成任意长度的 **任期(Term),任期用连续的整数标记。每一段任期从一次选举开始。Raft 保证了在一个给定的任期内,最多只有一个领导者

  • 如果选举成功,Leader 会管理整个集群直到任期结束。
  • 如果选举失败,那么这个任期就会因为没有 Leader 而结束。

不同服务器节点观察到的任期转换状态可能不一样

  • 服务器节点可能观察到多次的任期转换。
  • 服务器节点也可能观察不到任何一次任期转换。

任期在 Raft 算法中充当逻辑时钟的作用,使得服务器节点可以查明一些过期的信息(比如过期的 Leader)。每个服务器节点都会存储一个当前任期号,这一编号在整个时期内单调的增长。当服务器之间通信的时候会交换当前任期号。

  • 如果一个服务器的当前任期号比其他人小,那么他会更新自己的编号到较大的编号值。
  • 如果一个 Candidate 或者 Leader 发现自己的任期号过期了,那么他会立即恢复成跟随者状态。
  • 如果一个节点接收到一个包含过期的任期号的请求,那么他会直接拒绝这个请求。

RPC

Raft 算法中服务器节点之间的通信使用 ***远程过程调用(RPC)***。

基本的一致性算法只需要两种 RPC:

  • RequestVote RPC - 请求投票 RPC,由 Candidate 在选举期间发起。
  • AppendEntries RPC - 附加条目 RPC,由 Leader 发起,用来复制日志和提供一种心跳机制。

三、选举 Leader

选举规则

Raft 使用一种心跳机制来触发 Leader 选举

Leader 需要周期性的向所有 Follower 发送心跳消息,以此维持自己的权威并阻止新 Leader 的产生。

每个 Follower 都设置了一个随机的竞选超时时间,一般为 150ms ~ 300ms,如果在竞选超时时间内没有收到 Leader 的心跳消息,就会认为当前 Term 没有可用的 Leader,并发起选举来选出新的 Leader。开始一次选举过程,Follower 先要增加自己的当前 Term 号,并转换为 Candidate

Candidate 会并行的向集群中的所有服务器节点发送投票请求(RequestVote RPC,它会保持当前状态直到以下三件事情之一发生:

  • 自己成为 Leader
  • 其他的服务器成为 Leader
  • 没有任何服务器成为 Leader

自己成为 Leader

  • 当一个 Candidate 从整个集群半数以上的服务器节点获得了针对同一个 Term 的选票,那么它就赢得了这次选举并成为 Leader。每个服务器最多会对一个 Term 投出一张选票,按照先来先服务(FIFO)的原则。要求半数以上选票的规则确保了最多只会有一个 Candidate 赢得此次选举
  • 一旦 Candidate 赢得选举,就立即成为 Leader。然后它会向其他的服务器发送心跳消息来建立自己的权威并且阻止新的领导人的产生。

其他的服务器成为 Leader

等待投票期间,Candidate 可能会从其他的服务器接收到声明它是 Leader 的 AppendEntries RPC

  • 如果这个 Leader 的 Term 号(包含在此次的 RPC 中)不小于 Candidate 当前的 Term,那么 Candidate 会承认 Leader 合法并回到 Follower 状态。
  • 如果此次 RPC 中的 Term 号比自己小,那么 Candidate 就会拒绝这个消息并继续保持 Candidate 状态。

没有任何服务器成为 Leader

如果有多个 Follower 同时成为 Candidate,那么选票可能会被瓜分以至于没有 Candidate 可以赢得半数以上的投票。当这种情况发生的时候,每一个 Candidate 都会竞选超时,然后通过增加当前 Term 号来开始一轮新的选举。然而,没有其他机制的话,选票可能会被无限的重复瓜分。

Raft 算法使用随机选举超时时间的方法来确保很少会发生选票瓜分的情况,就算发生也能很快的解决。为了阻止选票起初就被瓜分,竞选超时时间是一个随机的时间,在一个固定的区间(例如 150-300 毫秒)随机选择,这样可以把选举都分散开。

  • 以至于在大多数情况下,只有一个服务器会超时,然后它赢得选举,成为 Leader,并在其他服务器超时之前发送心跳包。
  • 同样的机制也被用在选票瓜分的情况下:每一个 Candidate 在开始一次选举的时候会重置一个随机的选举超时时间,然后在超时时间内等待投票的结果;这样减少了在新的选举中另外的选票瓜分的可能性。

理解了上面的选举规则后,我们通过动图来加深认识。

单 Candidate 选举

(1)下图表示一个分布式系统的最初阶段,此时只有 Follower,没有 Leader。Follower A 等待一个随机的选举超时时间之后,没收到 Leader 发来的心跳消息。因此,将 Term 由 0 增加为 1,转换为 Candidate,进入选举状态。

img

(2)此时,A 向所有其他节点发送投票请求。

img

(3)其它节点会对投票请求进行回复,如果超过半数以上的节点投票了,那么该 Candidate 就会立即变成 Term 为 1 的 Leader。

img

(4)Leader 会周期性地发送心跳消息给所有 Follower,Follower 接收到心跳包,会重新开始计时。

img

多 Candidate 选举

(1)如果有多个 Follower 成为 Candidate,并且所获得票数相同,那么就需要重新开始投票。例如下图中 Candidate B 和 Candidate D 都发起 Term 为 4 的选举,且都获得两票,因此需要重新开始投票。

img

(2)当重新开始投票时,由于每个节点设置的随机竞选超时时间不同,因此能下一次再次出现多个 Candidate 并获得同样票数的概率很低。

img

四、日志复制

日志格式

日志由含日志索引(log index)的日志条目(log entry)组成。每个日志条目包含它被创建时的 Term 号(下图中方框中的数字),和一个复制状态机需要执行的指令。如果一个日志条目被复制到半数以上的服务器上,就被认为可以提交(Commit)了。

  • 日志条目中的 Term 号被用来检查是否出现不一致的情况。
  • 日志条目中的日志索引(一个整数值)用来表明它在日志中的位置。

img

Raft 日志同步保证如下两点:

  • 如果不同日志中的两个日志条目有着相同的日志索引和 Term,则它们所存储的命令是相同的
    • 这个特性基于这条原则:Leader 最多在一个 Term 内、在指定的一个日志索引上创建一条日志条目,同时日志条目在日志中的位置也从来不会改变。
  • 如果不同日志中的两个日志条目有着相同的日志索引和 Term,则它们之前的所有条目都是完全一样的
    • 这个特性由 AppendEntries RPC 的一个简单的一致性检查所保证。在发送 AppendEntries RPC 时,Leader 会把新日志条目之前的日志条目的日志索引和 Term 号一起发送。如果 Follower 在它的日志中找不到包含相同日志索引和 Term 号的日志条目,它就会拒绝接收新的日志条目。

日志复制流程

img

  1. Leader 负责处理所有客户端的请求。
  2. Leader 把请求作为日志条目加入到它的日志中,然后并行的向其他服务器发送 AppendEntries RPC 请求,要求 Follower 复制日志条目。
  3. Follower 复制成功后,返回确认消息。
  4. 当这个日志条目被半数以上的服务器复制后,Leader 提交这个日志条目到它的复制状态机,并向客户端返回执行结果。

注意:如果 Follower 崩溃或者运行缓慢,再或者网络丢包,Leader 会不断的重复尝试发送 AppendEntries RPC 请求 (尽管已经回复了客户端),直到所有的跟随者都最终复制了所有的日志条目。

下面,通过一组动图来加深认识:

(1)来自客户端的修改都会被传入 Leader。注意该修改还未被提交,只是写入日志中。

img

(2)Leader 会把修改复制到所有 Follower。

img

(3)Leader 会等待大多数的 Follower 也进行了修改,然后才将修改提交。

img

(4)此时 Leader 会通知的所有 Follower 让它们也提交修改,此时所有节点的值达成一致。

img

日志一致性

一般情况下,Leader 和 Followers 的日志保持一致,因此日志条目一致性检查通常不会失败。然而,Leader 崩溃可能会导致日志不一致:旧的 Leader 可能没有完全复制完日志中的所有条目。

Leader 和 Follower 日志不一致的可能

Leader 和 Follower 可能存在多种日志不一致的可能。

img

💡 图示说明:

上图阐述了 Leader 和 Follower 可能存在多种日志不一致的可能,每一个方框表示一个日志条目,里面的数字表示任期号 。

当一个 Leader 成功当选时,Follower 可能出现以下情况(a-f):

  • 存在未更新日志条目,如(a、b)。
  • 存在未提交日志条目,如(c、d)。
  • 两种情况都存在,如(e、f)。

例如,场景 f 可能会这样发生,某服务器在 Term2 的时候是 Leader,已附加了一些日志条目到自己的日志中,但在提交之前就崩溃了;很快这个机器就被重启了,在 Term3 重新被选为 Leader,并且又增加了一些日志条目到自己的日志中;在 Term 2 和 Term 3 的日志被提交之前,这个服务器又宕机了,并且在接下来的几个任期里一直处于宕机状态

Leader 和 Follower 日志一致的保证

Leader 通过强制 Followers 复制它的日志来处理日志的不一致,Followers 上的不一致的日志会被 Leader 的日志覆盖

  • Leader 为了使 Followers 的日志同自己的一致,Leader 需要找到 Followers 同它的日志一致的地方,然后覆盖 Followers 在该位置之后的条目。

  • Leader 会从后往前试,每次日志条目失败后尝试前一个日志条目,直到成功找到每个 Follower 的日志一致位点,然后向后逐条覆盖 Followers 在该位置之后的条目。

五、安全性

前面描述了 Raft 算法是如何选举 Leader 和复制日志的。

Raft 还增加了一些限制来完善 Raft 算法,以保证安全性:保证了任意 Leader 对于给定的 Term,都拥有了之前 Term 的所有被提交的日志条目。

选举限制

拥有最新的已提交的日志条目的 Follower 才有资格成为 Leader。

Raft 使用投票的方式来阻止一个 Candidate 赢得选举除非这个 Candidate 包含了所有已经提交的日志条目。 Candidate 为了赢得选举必须联系集群中的大部分节点,这意味着每一个已经提交的日志条目在这些服务器节点中肯定存在于至少一个节点上。如果 Candidate 的日志至少和大多数的服务器节点一样新(这个新的定义会在下面讨论),那么他一定持有了所有已经提交的日志条目。

RequestVote RPC 实现了这样的限制:RequestVote RPC 中包含了 Candidate 的日志信息, Follower 会拒绝掉那些日志没有自己新的投票请求

如何判断哪个日志条目比较新?

Raft 通过比较两份日志中最后一条日志条目的日志索引和 Term 来判断哪个日志比较新。

  • 先判断 Term,哪个数值大即代表哪个日志比较新。
  • 如果 Term 相同,再比较 日志索引,哪个数值大即代表哪个日志比较新。

提交旧任期的日志条目

一个当前 Term 的日志条目被复制到了半数以上的服务器上,Leader 就认为它是可以被提交的。如果这个 Leader 在提交日志条目前就下线了,后续的 Leader 可能会覆盖掉这个日志条目。

img

💡 图示说明:

上图解释了为什么 Leader 无法对旧 Term 的日志条目进行提交。

  • 阶段 (a) ,S1 是 Leader,且 S1 写入日志条目为 (Term 2,日志索引 2),只有 S2 复制了这个日志条目。
  • 阶段 (b),S1 下线,S5 被选举为 Term3 的 Leader。S5 写入日志条目为 (Term 3,日志索引 2)。
  • 阶段 ©,S5 下线,S1 重新上线,并被选举为 Term4 的 Leader。此时,Term 2 的那条日志条目已经被复制到了集群中的大多数节点上,但是还没有被提交。
  • 阶段 (d),S1 再次下线,S5 重新上线,并被重新选举为 Term3 的 Leader。然后 S5 覆盖了日志索引 2 处的日志。
  • 阶段 (e),如果阶段 (d) 还未发生,即 S1 再次下线之前,S1 把自己主导的日志条目复制到了大多数节点上,那么在后续 Term 里面这些新日志条目就会被提交。这样在同一时刻就同时保证了,之前的所有旧日志条目就会被提交。

Raft 永远不会通过计算副本数目的方式去提交一个之前 Term 内的日志条目。只有 Leader 当前 Term 里的日志条目通过计算副本数目可以被提交;一旦当前 Term 的日志条目以这种方式被提交,那么由于日志匹配特性,之前的日志条目也都会被间接的提交。

当 Leader 复制之前任期里的日志时,Raft 会为所有日志保留原始的 Term,这在提交规则上产生了额外的复杂性。在其他的一致性算法中,如果一个新的领导人要重新复制之前的任期里的日志时,它必须使用当前新的任期号。Raft 使用的方法更加容易辨别出日志,因为它可以随着时间和日志的变化对日志维护着同一个任期编号。另外,和其他的算法相比,Raft 中的新领导人只需要发送更少日志条目(其他算法中必须在他们被提交之前发送更多的冗余日志条目来为他们重新编号)。

六、日志压缩

在实际的系统中,不能让日志无限膨胀,否则系统重启时需要花很长的时间进行恢复,从而影响可用性。Raft 采用对整个系统进行快照来解决,快照之前的日志都可以丢弃。

每个副本独立的对自己的系统状态生成快照,并且只能对已经提交的日志条目生成快照。

快照包含以下内容:

  • 日志元数据。最后一条已提交的日志条目的日志索引和 Term。这两个值在快照之后的第一条日志条目的 AppendEntries RPC 的完整性检查的时候会被用上。
  • 系统当前状态。

当 Leader 要发送某个日志条目,落后太多的 Follower 的日志条目会被丢弃,Leader 会将快照发给 Follower。或者新上线一台机器时,也会发送快照给它。

img

生成快照的频率要适中,频率过高会消耗大量 I/O 带宽;频率过低,一旦需要执行恢复操作,会丢失大量数据,影响可用性。推荐当日志达到某个固定的大小时生成快照。

生成一次快照可能耗时过长,影响正常日志同步。可以通过使用 copy-on-write 技术避免快照过程影响正常日志同步。

说明:本文仅阐述 Raft 算法的核心内容,不包括算法论证、评估等

参考资料

Markdown Cheat Sheet

📦 本文已归档到:「blog

目录

标题

Markdown 支持六个级别的标题。

语法:
# 一级标题
## 二级标题
### 三级标题
#### 四级标题
##### 五级标题
###### 六级标题

文本样式

💡 粗体、斜体、删除线可以混合使用。

在 Markdown 中,粗体文本、斜体文本可以使用 *_ 符号标记。建议统一风格,始终只用一种符号。

语法 效果
普通文本 普通文本
*斜体文本* _斜体文本_ 斜体文本 斜体文本
**粗体文本** __粗体文本__ 粗体文本 粗体文本
~~删除文本~~ 删除文本
***粗斜体文本*** ___粗斜体文本___ 粗斜体文本 粗斜体文本

列表

无序列表

  • RED
  • YELLOW
  • BLUE

有序列表

  1. 第一步
  2. 第二步
  3. 第三步

任务列表

  • [x] 完成任务
  • [ ] 计划任务

多级列表

  • 数据结构
    • 线性表
      • 顺序表
      • 链表
        • 单链表
        • 双链表
      • 二叉树
        • 二叉平衡树

分割线

***---___ 都可以作为分割线。




链接

普通链接

语法:

[我的博客](https://dunwu.github.io/blog/)
  • [] 中标记链接名。类似 HTML 中 <a> 元素的 title 属性。
  • () 中标记链接的 url,也支持相对路径(前提是资源可以访问)。类似 HTML 中 <a> 元素的 href 属性。

效果:

图片

Markdown 引用图片的语法:

![alt](url title)

alt 和 title 即对应 HTML 中 img 元素的 alt 和 title 属性(都可省略):

  • alt - 表示图片显示失败时的替换文本。

  • title - 表示鼠标悬停在图片时的显示文本(注意这里要加引号)

  • url - 即图片的 url 地址

logo

图片链接

可以将图片和链接混合使用。

logo

锚点

其实呢,每一个标题都是一个锚点,和 HTML 的锚点(#)类似,比如:回到顶部

引用

普通引用:

❓ 什么是 Markdown

Markdown是一种轻量级标记语言,创始人为约翰·格鲁伯(英语:John Gruber)。它允许人们“使用易读易写的纯文本格式编写文档,然后转换成有效的XHTML(或者HTML)文档”。[4]这种语言吸收了很多在电子邮件中已有的纯文本标记的特性。 —— 摘自 Wiki

嵌套引用:

数据结构

二叉树

平衡二叉树

满二叉树

代码高亮

标签

语法:

`Markdown` `Doc`

效果:

Markdown, Doc

代码块

语法一:在文本前后都使用三个反引号进行标记。【✔️ 推荐】

这是一个文本块。
这是一个文本块。
这是一个文本块。

语法二:在连续几行的文本开头加入 1 个 Tab 或者 4 个空格。【❌ 不推荐】

这是一个文本块。
这是一个文本块。
这是一个文本块。

语法

在三个反引号后面加上编程语言的名字,另起一行开始写代码,最后一行再加上三个反引号。

public static void main(String[]args){} //Java
int main(int argc, char *argv[]) //C
echo "hello GitHub" #Bash
document.getElementById('myH1').innerHTML = 'Welcome to my Homepage' //javascipt
string &operator+(const string& A,const string& B) //cpp

表格

一般表格:

表头 1 表头 2
表格单元 表格单元
表格单元 表格单元

表格可以指定对齐方式:

序号 商品 价格
1 电脑 6000.0
2 鼠标 100.0
3 键盘 200.0

Emoji 表情

💡 注意:部分 Markdown 引擎支持 Emoji。

合理使用 Emoji 表情,往往可以使得文章内容更加丰富生动。例如:✔️ ❌ 💡 🔔 ❗️ ❓

更多 Emoji 表情请参考:

注脚

💡 注意:部分 Markdown 引擎支持注脚。

一个具有注脚的文本。[1]

数学公式

💡 注意:部分 Markdown 引擎支持 Latex。

很多文档中,需要引入一些数学符号、特殊符号,其排版问题比较头疼。这种问题,可以用 Latex 来解决,大部分 Markdown 引擎都支持 Latex。

Latex 可以使用 $ 符号来标记 Latex 表达式,下面是一个数学公式示例:

Γ(z)=0tz1etdt.\Gamma(z) = \int_0^\infty t^{z-1}e^{-t}dt\,.

列举一些常用数学符号:

符号 语法 描述
\leq $\leq$ 小于等于
\geq $\geq$ 大于等于
\neq $\neq$ 不等于
\approx $\approx$ 约等于
\infty $\infty$ 无穷
xy\prod_{x}^{y} $\prod_{x}^{y}$ 累乘
i=0n\sum_{i=0}^n $\sum_{i=0}^n$ 求和
\int $\int$ 积分
\iint $\iint$ 双重积分
logxy\log_x{y} $\log_x{y}$ 对数
xy+1x^{y+1} $x^{y+1}$ 上标
xy+1x_{y+1} $x_{y+1}$ 下标
xy\frac{x}{y} $\frac{x}{y}$ 分数
xy\sqrt[y]{x} $\sqrt[y]{x}$ 开方
sin\sin $\sin$ 正弦
cos\cos $\cos$ 余弦
tan\tan $\tan$ 正切

更多数学符号支持请参考:

Diff

💡 注意:部分 Markdown 引擎支持 Diff。

版本控制的系统中都少不了 diff 的功能,即展示一个文件内容的增加与删除。
GFM 中可以显示的展示 diff 效果。可以用 + 开头表示新增,- 开头表示删除。

+ 新增内容
- 删除内容

UML 图

💡 注意:部分 Markdown 引擎支持 mermaid

mermaid 提供了多种 UML 图。详情请参考:mermaid 文档

流程图

graph LR
A[Hard edge] -->|Link text| B(Round edge)
B --> C{Decision}
C -->|One| D[Result one]
C -->|Two| E[Result two]

时序图

sequenceDiagram
Alice->>Bob: Hello Bob, how are you?
alt is sick
Bob->>Alice: Not so good :(
else is well
Bob->>Alice: Feeling fresh like a daisy
end
opt Extra response
Bob->>Alice: Thanks for asking
end

甘特图

gantt
dateFormat YYYY-MM-DD
title Adding GANTT diagram functionality to mermaid

section A section
Completed task :done, des1, 2014-01-06,2014-01-08
Active task :active, des2, 2014-01-09, 3d
Future task : des3, after des2, 5d
Future task2 : des4, after des3, 5d

section Critical tasks
Completed task in the critical line :crit, done, 2014-01-06,24h
Implement parser and jison :crit, done, after des1, 2d
Create tests for parser :crit, active, 3d
Future task in critical line :crit, 5d
Create tests for renderer :2d
Add to mermaid :1d

section Documentation
Describe gantt syntax :active, a1, after des1, 3d
Add gantt diagram to demo page :after a1 , 20h
Add another diagram to demo page :doc1, after a1 , 48h

section Last section
Describe gantt syntax :after doc1, 3d
Add gantt diagram to demo page :20h
Add another diagram to demo page :48h

HTML

有些 Markdown 引擎支持在文档中嵌入的 html 元素。

有些 Markdown 语法所不支持的特性,可以使用 html 元素来支持。

折叠

折叠内容一

展开才能看到的内容

折叠内容二

展开才能看到的内容

居中

居中显示的文本

图片尺寸

编辑器

推荐 Markdown 编辑器

  • Typora - 个人认为是功能最强的 Markdown 编辑器。
  • Visual Studio Code - 可以通过安装插件,量身打造 Markdown 编辑器。
  • marktext - 一款简单优雅的 Markdown 编辑器。
  • StackEdit - 在线 Markdown 编辑器。
  • Editor.md - 在线 Markdown 编辑器。
  • Marxico - 一款专为印象笔记(Evernote)打造的 Markdown 编辑器。

想了解更多 Markdown 编辑器可以参考:主流 Markdown 编辑器推荐

参考资料


  1. 注脚的解释 ↩︎