选择排序

原理

每次选择数组中的最小元素，排在第一个位置

算法步骤

1
2
3
4
5
6
7
8

[38,65,97,76,13,27,49]
13 [65 97 76 38 27 49]
13 27 [97 76 38 65 49]
13 27 38 [76 97 65 49]
13 27 38 49 [97 65 76]
13 27 38 49 65 [97 76]
13 27 38 49 65 76 [97]
13 27 38 49 65 76 97

背景

假设我们有一个分布式系统，系统中需要维护全局 id 字段，我们可以把它认为是唯一的标识，不能够重复出现，那么问题来了，我们应该如何生成这样的 id 呢？

其实很容易想到的一种解决方式就是使用 Redis 的键值对了，每次更新的时候直接调用 incr，生成的 id 也是唯一的，还有一种方式就是使用 MySQL 或者其他的数据库，因为我们知道 MySQL 中可以生成自增主键，使用这个主键作为一个分布式 id 也是可行的。

但是上面的这两种方式效率不会特别高，并且依赖于第三方，我们如果想要更高效的生成分布式 id，那么最好的方式就是尽量本地生成，不需要和其他节点进行协商，但是有一个问题出现了，如何保证 id 不重复？，我们可以使用 Snowflake 算法来解决该问题。

常见的限流算法主要有两种：令牌桶和漏桶算法，也可以使用计数器进行粗暴限流实现。

算法原理

计数器

维护一个请求数量，在一段时间里，如果请求总数超过了limit，那么我们可以把这个请求拒绝掉，也可以将其放入到缓冲队列中，等待下一个时间段再进行操作。

背景

在实际生产过程中，我们往往会通过集群的方式部署服务器，而不是单机部署，从而可以提高服务的并发能力。

但是这样部署产生了一个新的问题：如何决定某个请求发往的服务器？这就是负载均衡算法所需要解决的问题。

背景

在介绍一致性哈希之前，首先来看看集群部署可能发生的问题：比如说我现在有5台 Redis 服务器，正常运行了很久，很不巧有一天A服务器崩溃了，这个时候还有4台服务器，系统还可以正常运行，原来发送到A服务器的请求我们肯定要想办法进行重定向吧，如果说我们使用一般的哈希函数进行分配，无疑是 hash(key) % num，不过因为 num 现在变成了 num-1，那么很有可能所有的请求都会发生改变打到不同的服务器上，原来发送到B的请求重新处理之后可能发送到了C服务器了。