分布式面试篇

一致性哈希

传统的哈希取模操作是基于当前服务器数量的，例如有三台服务器，每次算哈希值就对这三个取模，由于模只可能是0，1，2。

上述HASH算法时，会出现一些缺陷：如果服务器已经不能满足缓存需求，就需要增加服务器数量，假设我们增加了一台缓存服务器，此时如果仍然使用上述方法对同一张图片进行缓存，那么这张图片所在的服务器编号必定与原来3台服务器时所在的服务器编号不同，因为除数由3变为了4，最终导致所有缓存的位置都要发生改变，也就是说，当服务器数量发生改变时，所有缓存在一定时间内是失效的，当应用无法从缓存中获取数据时，则会向后端服务器请求数据；同理，假设突然有一台缓存服务器出现了故障，那么我们则需要将故障机器移除，那么缓存服务器数量从3台变为2台，同样会导致大量缓存在同一时间失效，造成了缓存的雪崩，后端服务器将会承受巨大的压力，整个系统很有可能被压垮。为了解决这种情况，就有了一致性哈希算法。

一致性哈希算法也是使用取模的方法，但是取模算法是对服务器的数量进行取模，而一致性哈希算法是对 2^32 取模，具体步骤如下：

步骤一：一致性哈希算法将整个哈希值空间按照顺时针方向组织成一个虚拟的圆环，称为 Hash 环；
步骤二：接着将各个服务器使用 Hash 函数进行哈希，具体可以选择服务器的IP或主机名作为关键字进行哈希，从而确定每台机器在哈希环上的位置
步骤三：最后使用算法定位数据访问到相应服务器：将数据key使用相同的函数Hash计算出哈希值，并确定此数据在环上的位置，从此位置沿环顺时针寻找，第一台遇到的服务器就是其应该定位到的服务器
下面我们使用具体案例说明一下一致性哈希算法的具体流程：

（1）步骤一：哈希环的组织：

圆环的正上方的点代表0，0点右侧的第一个点代表1，以此类推，2、3、4、5、6……直到2^32-1,也就是说0点左侧的第一个点代表2^32-1，我们把这个由 2^32 个点组成的圆环称为hash环。

（2）步骤二：确定服务器在哈希环的位置：

哈希算法：hash（服务器的IP） % 2^32

上述公式的计算结果一定是 0 到 2^32-1 之间的整数，那么上图中的 hash 环上必定有一个点与这个整数对应，所以我们可以使用这个整数代表服务器，也就是服务器就可以映射到这个环上，假设我们有 ABC 三台服务器，那么它们在哈希环上的示意图如下：

3）步骤三：将数据映射到哈希环上：

我们还是使用图片的名称作为 key，所以我们使用下面算法将图片映射在哈希环上：hash（图片名称） % 2^32，假设我们有4张图片，映射后的示意图如下，其中橘黄色的点表示图片：

那么，怎么算出上图中的图片应该被缓存到哪一台服务上面呢？我们只要从图片的位置开始，沿顺时针方向遇到的第一个服务器就是图片存放的服务器了。最终，1号、2号图片将会被缓存到服务器A上，3号图片将会被缓存到服务器B上，4号图片将会被缓存到服务器C上。

一致性 hash 算法的优点

前面提到，如果简单对服务器数量进行取模，那么当服务器数量发生变化时，会产生缓存的雪崩，从而很有可能导致系统崩溃，而使用一致性哈希算法就可以很好的解决这个问题，因为一致性Hash算法对于节点的增减都只需重定位环空间中的一小部分数据，只有部分缓存会失效，不至于将所有压力都在同一时间集中到后端服务器上，具有较好的容错性和可扩展性。

假设服务器B出现了故障，需要将服务器B移除，那么移除前后的示意图如下图所示：

一致性 hash 算法的缺点

可能会出现倾斜，当服务器的哈希值都很接近就会出现在一段区间里分布着大量的服务器，分布不够均匀。因此也有了虚拟节点这个概念。也就是对服务器用多个哈希函数进行多次运算，使其分布更加均匀。、

扩展：如果服务器之间有权重，如何设计负载均衡算法：

1. 轮盘赌：多个服务器的权重按百分比进行分配，每次有访问请求就生成随机数，这样权重大的就有更大的概率被选中。缺点是如果服务器进行扩展，这个规则需要更改
2. 一致性哈希的虚拟节点：可以根据权重分配更多的虚拟节点，但是效果有待验证，因为毕竟也是随机的，增加节点并不一定就能获得更大的访问范围。

分布式限流算法

• 固定窗口计数器算法：在一分钟内设定n次访问量，如果超过了n次就拒绝访问。缺点是限流不够平滑，如果在1分钟内前30秒就处理了n个，后面半分钟就等于空转；也无法保证限流速率和攻击，如果服务器的承载力就是1分钟n个请求，在这分钟的后30s给出n个请求，后面一分钟的前半部分给出n个，也能将服务器击垮
• 滑动窗口计数器算法：划分的更细了，例如划分一秒多少个请求，这样可以应对突发的请求增大，但是也有不平滑的问题，也不好控制速率
• 漏桶算法：请求进入桶，慢慢漏下来，满了就丢弃请求。这样优点是可以控制速率，但是同时也会导致漏请求
• 令牌桶算法：桶里面是令牌，可以通过控制令牌的流速改变处理速度

分布式ID生成算法

• UUID：jdk自带就有这个算法，有五个版本。优点是生成很简单，本地就可以生成；缺点是要用到mac地址，安全性不好，而且不是连续的，对于InnoDB非顺序的id插入可能造成页分裂的问题，影响性能，而且长度也很长，mysql不建议这么长的id
• 雪花算法：时间戳+机房id+机器id+序列号。正常情况下一毫秒一个机器可以生成4096个。大致是有序的，只不过时间戳是在高位；缺点是高度依赖时间系统，如果服务器出现时间回退就会导致出错
• 数据库自增：用一个专门的表来插入自增，然后需要id的时候找这个表插入一条，返回的id即为自己的id。优点是简单；缺点是自增的太明显了，而且不适合分布式
• 美团开源生成算法leaf

分布式事务

• 2pc：两阶段提交。分布式事务有两个角色，一个是事务管理者，一个是事务执行者（比如mysql或者redis）。两个阶段指的是准备阶段和提交阶段。事务管理者会询问当前事务下所有的执行器是否已经准备就绪，执行器接到这个询问后开始执行自己的逻辑，如果没有出错就返回yes，出错了返回no；第二阶段是提交，如果所有都返回yes，管理者就会让其提交事务，如果有一个是no就会回滚。缺点是会有单点问题，极度依赖事务管理者，如果宕机就会一直卡住，其次是会有阻塞，在事务执行期间会阻塞其他事务
• 3pc：三阶段提交，比上面的多了一个开始的询问阶段，首先是准备阶段，事务管理者只会问他们准备好了吗，而不会实际的执行自己的任务；如果此时有人返回no就会回滚，但是由于没有执行任务所以回滚的代价小很多；二阶段是预提交阶段，当所有人都准备好了就会执行自己的任务，此时跟上面的一样，如果有no就回滚，这是最后的回滚机会了；三阶段是提交，如果所有都返回为yes，事务管理器就会让他们提交事务。优点是这里都有超时机制，避免了阻塞；但是还是有不一致的现象，3pc用的比较少
• TCC：需要代码实现的两阶段提交，分为try，confirm，cancel。首先try是预留业务资源；confirm确认执行业务逻辑，并且消耗try的业务资源，如果出现错误就会cancel，取消这个操作并且释放try的资源
• AT：seata的一种模式，可以视为2pc的一种实现模式。原理一阶段是通过代理sql，先解析sql保存执行前后的数据快照和undolog；二阶段如果有出错就按照这个undolog进行回滚。
• saga：将事务变成线性链表，然后一个一个做，中间某个事务出现了问题就会给前面已经提交的事务一个补偿措施。