服务器开发设计之算法宝典

1. 调度算法

在服务器逻辑开发设计中，调度算法随处可见，资源的调度，请求的分配，负载均衡的策略等等都与调度算法相关。调度算法没有好坏之分，最适合业务场景的才是最好的。

1.1. 轮询

轮询是非常简单且常用的一种调度算法，轮询即将请求依次分配到各个服务节点，从第一个节点开始，依次将请求分配到最后一个节点，而后重新开始下一轮循环。最终所有的请求会均摊分配在每个节点上，假设每个请求的消耗是一样的，那么轮询调度是最平衡的调度（负载均衡）算法。

1.2. 加权轮询

有些时候服务节点的性能配置各不相同，处理能力不一样，针对这种的情况，可以根据节点处理能力的强弱配置不同的的权重值，采用加权轮询的方式进行调度。

加权轮询可以描述为：

1. 调度节点记录所有服务节点的当前权重值，初始化为配置对应值。

2. 当有请求需要调度时，每次分配选择当前权重最高的节点，同时被选择的节点权重值减一。

3. 若所有节点权重值都为零，则重置为初始化时配置的权重值。

最终所有请求会按照各节点的权重值成比例的分配到服务节点上。假设有三个服务节点{a,b,c}，它们的权重配置分别为{2,3,4}，那么请求的分配次序将是{c,b,c,a,b,c,a,b,c}，如下所示：

1.3. 平滑权重轮询

加权轮询算法比较容易造成某个服务节点短时间内被集中调用，导致瞬时压力过大，权重高的节点会先被选中直至达到权重次数才会选择下一个节点，请求连续的分配在同一个节点上的情况，例如假设三个服务节点{a,b,c}，权重配置分别是{5,1,1}，那么加权轮询调度请求的分配次序将是{a,a,a,a,a,b,c}，很明显节点 a 有连续的多个请求被分配。

为了应对这种问题，平滑权重轮询实现了基于权重的平滑轮询算法。所谓平滑，就是在一段时间内，不仅服务节点被选择次数的分布和它们的权重一致，而且调度算法还能比较均匀的选择节点，不会在一段时间之内集中只选择某一个权重较高的服务节点。

平滑权重轮询算法可以描述为：

1. 调度节点记录所有服务节点的当前权重值，初始化为配置对应值。

2. 当有请求需要调度时，每次会先把各节点的当前权重值加上自己的配置权重值，然后选择分配当前权重值最高的节点，同时被选择的节点权重值减去所有节点的原始权重值总和。

3. 若所有节点权重值都为零，则重置为初始化时配置的权重值。

同样假设三个服务节点{a,b,c}，权重分别是{5,1,1}，那么平滑权重轮询每一轮的分配过程如下表所示：

割环法实现复杂度略高，时间复杂度为 O(log(vn)),（其中，n 是服务节点个数，v 是每个节点拥有的虚拟节点数），它具有很好的单调性，而平衡性和稳定性主要取决于虚拟节点的个数和虚拟节点生成规则，例如 ketama hash 割环法采用的是通过服务节点 ip 和端口组成的字符串的 MD5 值，来生成 160 组虚拟节点。

1.8.3. 二次取模

取模哈希映射是一种简单的一致性哈希方式，但是简单的一次性取模哈希单调性很差，对于故障容灾非常不好，一旦某台服务节点不可用，会导致大部分的请求被重新分配到新的节点，造成缓存的大面积迁移，因此有了二次取模的一致性哈希方式。

二次取模算法即调度节点维护两张服务节点表：松散表（所有节点表）和紧实表（可用节点表）。请求分配过程中，先对松散表取模运算，若结果节点可用，则直接选取；若结果节点已不可用，再对紧实表做第二次取模运算，得到最终节点。如下图示：

最终，洗牌的结果为 3，5，2，4，1。

运用占位洗牌算法实现的随机抽样的方式称为占位洗牌随机抽样，同样的，我们依然可以只抽取到前 m 个数据即可。这种算法对原数组不做任何修改，代价是增加不大于 的临时空间。

2.3. 选择抽样技术抽样

洗牌算法是对一个已经预初始化好的数据列表进行洗牌，需要在内存中全量缓存数据列表，如果数据总量 n 很大，并且单条记录的数据也很大，那么在内存中缓存所有数据记录的做法会显得非常的笨拙。而选择选择抽样技术算法，它不需要预先全量缓存数据列表，从而可以支持流式处理。

选择抽样技术算法可以描述为：

1. 生成 1 到 n 之间的随机数 U

2. 如果 U≥m，则跳转到步骤 4

3. 把这个记录选为样本，m 减 1，n 减 1。如果 m>0，则跳转到步骤 1，否则取样完成，算法终止

4. 跳过这个记录，不选为样本，n 减 1，跳转到步骤 1

选择抽样技术算法过程演示如下：

最终，抽样的结果为 1，5。

可以证明，每个数据被选中且留在蓄水池中的概率为 。

2.5. 随机分值排序抽样

洗牌算法也可以认为就是将数据按随机的方式做一个排序，从 n 个元素集合中随机抽取 m 个元素的问题就相当于是随机排序之后取前 m 排名的元素，基于这个原理，我们可以设计一种通过随机分值排序的方式来解决随机抽样问题。

随机分值排序算法可以描述为：

1. 系统维护一张容量为 m 的排行榜单

2. 对于每个元素都给他们随机一个（0,1] 区间的分值，并根据随机分值插入排行榜

3. 所有数据处理完成，最终排名前 m 的元素即为抽样结果

尽管随机分值排序抽样算法相比于蓄水池抽样算法并没有什么好处，反而需要增加额外的排序消耗，但接下来的带权重随机抽样将利用到它的算法思想。

2.6. 朴素的带权重抽样

很多需求场景数据元素都需要带有权重，每个元素被抽取的概率是由元素本身的权重决定的，诸如全服消费抽奖类活动，需要以玩家在一定时间段内的总消费额度为权重进行抽奖，消费越高，最后中奖的机会就越大，这就涉及到了带权重的抽样算法。

朴素的带权重随机算法也称为轮盘赌选择法，将数据放置在一个假想的轮盘上，元素个体的权重越高，在轮盘上占据的空间就越多，因此就更有可能被选中。

由于权重 45 处于四等奖的累加权重值当中，因此最后抽样结果为四等奖。

若要不放回的选取 m 个元素，则需要先选取一个，并将该元素从集合中踢除，再反复按同样的方法抽取其余元素。

这种抽样算法的复杂度是 ，并且将元素从集合中删除破坏了原数据的可读属性，更重要的是这个算法需要多次遍历数据，不适合在流处理的场景中应用。

2.7. 带权重的 A-Res 算法蓄水池抽样

朴素的带权重抽样算法需要内存足够容纳所有数据，破坏了原数据的可读属性，时间复杂度高等缺点，而经典的蓄水池算法高效的实现了流处理场景的大数据不放回随机抽样，但对于带权重的情况，就不能适用了。

A-Res（Algorithm A With a Reservoir） 是蓄水池抽样算法的带权重版本，算法主体思想与经典蓄水池算法一样都是维护含有 m 个元素的结果集，对每个新元素尝试去替换结果集中的元素。同时它巧妙的利用了随机分值排序算法抽样的思想，在对数据做随机分值的时候结合数据的权重大小生成排名分数，以满足分值与权重之间的正相关性，而这个 A-Res 算法生成随机分值的公式就是：

其中 为第 i 个数据的权重值， 是从（0,1]之间的一个随机值。

A-Res 算法可以描述为：

1. 对于前 m 个数, 计算特值 ，直接放入蓄水池中

2. 对于从 m+1,m+2,…,n 的第 i 个数，通过公式 计算特征值 ，如若特征值超过蓄水池中最小值，则替换最小值

该算法的时间复杂度为 ，且可以完美的运用在流式处理场景中。

2.8. 带权重的 A-ExpJ 算法蓄水池抽样

A-Res 需要对每个元素产生一个随机数，而生成高质量的随机数有可能会有较大的性能开销，《Weighted random sampling with a reservoir》论文中给出了一种更为优化的指数跳跃的算法 A-ExpJ 抽样（Algorithm A with exponential jumps），它能将随机数的生成量从 减少到 ，原理类似于通过一次额外的随机来跳过一段元素的特征值 的计算。

A-ExpJ 算法蓄水池抽样可以描述为：

1. 对于前 m 个数， 计算特征值 ，其中 为第 i 个数据的权重值， 是从（0,1]之间的一个随机值，直接放入蓄水池中

2. 对于从 m+1,m+2,…,n 的第 i 个数，执行以下步骤

3. 计算阈值 ， ，其中 r 为（0,1]之间的一个随机值， 为蓄水池中的最小特征值

4. 跳过部分元素并累加这些元素权重值 ，直到第 i 个元素满足

5. 计算当前元素特征值 ，其中 为(,1]之间的一个随机值，, 为蓄水池中的最小特征值， 为当前元素权重值

6. 使用当前元素替换蓄水池中最小特征值的元素

7. 更新阈值 ，

有点不好理解，show you the code:

3. 排序算法

3.1. 基础排序

基础排序是建立在对元素排序码进行比较的基础上进行的排序算法。

3.1.1. 冒泡排序

冒泡排序是一种简单直观的排序算法。它每轮对每一对相邻元素进行比较，如果相邻元素顺序不符合规则，则交换他们的顺序，每轮将有一个最小（大）的元素浮上来。当所有轮结束之后，就是一个有序的序列。

过程演示如下：

3.1.3. 选择排序

选择排序首先在未排序序列中找到最小（大）元素，存放到已排序序列的起始位置。再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。直到所有元素处理完毕。

过程演示如下：

3.1.5. 归并排序

归并排序是建立在归并操作上的一种有效的排序算法，也是采用分治法的一个非常典型的应用。归并排序首先将序列二分成最小单元，而后通过归并的方式将两两已经有序的序列合并成一个有序序列，直到最后合并为一个最终有序序列。

过程演示如下：

3.1.7. 希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本，但希尔排序是非稳定排序算法。

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。

希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。

过程演示如下：

3.2.2. 桶排序

桶排序是计数排序的升级版，它利用了函数的映射关系，桶排序高效与否的关键就在于这个映射函数的确定。比如我们可以将排序数据进行除 10 运算，运算结果中具有相同的商值放入相同的桶中，即每十个数会放入相同的桶中。

过程演示如下：

基数排序也是一种桶排序。桶排序是按值区间划分桶，基数排序是按数位来划分，基数排序可以看做是多轮桶排序，每个数位上都进行一轮桶排序。

3.3. 多路归并排序

多路归并排序算法是将多个已经有序的列表进行归并排序，合成为一组有序的列表的排序过程。

k 路归并排序可以描述为：

1. 初始时取出 k 路有序列表中首个元素放入比较池。

2. 从比较池中取最小（大）的元素加入到结果列表，同时将该元素所在有序列表的下一个元素放入比较池（若有）。

3. 重新复进行步骤 2，直到所有队列的所有元素都已取出。

每次在比较池中取最小（大）的元素时，需要进行一次 k 个数据的比较操作，当 k 值较大时，会严重影响多路归并的效率，为提高效率，可以使用“败者树”来实现这样的比较过程。

败者树是完全二叉树，败者树相对的是胜者树，胜者树每个非终端结点（除叶子结点之外的其它结点）中的值都表示的是左右孩子相比较后的胜者。

如下图所示是一棵胜者树：

叶子节点的值是：{7,4,8,2,3,5,6,1}，7 与 4 比较，7 是败者，4 是胜者，因此他们的双亲节点是 7，同样 8 与 2 比较，8 是败者，表示在他们双亲节点上，而 7 与 8 的双亲节点需要用他们的胜者去比较，即用 4 与 2 比较，4 是败者，因此 7 与 8 的双亲节点记录的是 4，依此类推。

假设 k=8，败者树归并排序的过程演示如下所示：

在查找目标元素时，从顶层列表、头元素起步，沿着每层链表搜索，直至找到一个大于或等于目标的元素，或者到达当前层列表末尾。如果该元素等于目标元素，则表明该元素已被找到；如果该元素大于目标元素或已到达链表末尾，则退回到当前层的上一个元素，然后转入下一层进行搜索。依次类推，最终找到该元素或在最底层底仍未找到（不存在）。

当 p 值越大，快速通道就越稀疏，占用空间越小，但查找速度越慢，反之，则占用空间大查找速度快，通过选择不同 p 值，就可以在查找代价和存储代价之间获取平衡。

由于跳跃表使用的是链表，加上增加了近似于以二分方式的辅助节点，因此查询，插入和删除的性能都很理想。在大部分情况下，跳跃表的效率可以和平衡树相媲美，它是一种随机化的平衡方案，在实现上比平衡树要更为简单，因而得到了广泛的应用，如 redis 的 zset，leveldb，我司的 apollo 排行榜等都使用了跳跃表排序方案。

3.5. 百分比近似排序

在流处理场景中，针对大容量的排序榜单，全量存储和排序需要消耗的空间及时间都很高，不太现实。实际应用中，对于长尾数据的排序，一般也只需要显示百分比近似排名，通过牺牲一定的精确度来换取高性能和高实时性。

3.5.1. HdrHistogram 算法

HdrHistogram 使用的是直方图统计算法，直方图算法类似于桶排序，原理就是创建一个直方图，以一定的区间间隔记录每个区间上的数据总量，预测排名时只需统计当前值所在区间及之前区间的所有数量之和与总数据量之间的比率。

区间分割方式可以采用线性分割和指数分割方式：

1. 线性分割，数据以固定长度进行分割，假设数据范围是[1-1000000]，以每 100 的间隔划分为 1 个区间，总共需要划分 10000 个区间桶。

2. 声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！