架构师训练营 4 期 第 5 周

作业一：课后练习

1. 用你熟悉的编程语言实现一致性 hash 算法。

一致性Hash算法实现

1. 编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。

第一次计算结果：

初始节点数量 ： 10 , 额外虚拟节点数量：0 , 标准差： 194670.8769初始节点数量 ： 10 , 额外虚拟节点数量：10 , 标准差： 77887.5163初始节点数量 ： 10 , 额外虚拟节点数量：50 , 标准差： 29501.9697初始节点数量 ： 10 , 额外虚拟节点数量：100 , 标准差： 37135.9962初始节点数量 ： 10 , 额外虚拟节点数量：150 , 标准差： 22138.6286初始节点数量 ： 10 , 额外虚拟节点数量：200 , 标准差： 24229.9253初始节点数量 ： 10 , 额外虚拟节点数量：250 , 标准差： 20770.7953初始节点数量 ： 10 , 额外虚拟节点数量：300 , 标准差： 19717.2285初始节点数量 ： 10 , 额外虚拟节点数量：400 , 标准差： 17308.2784初始节点数量 ： 10 , 额外虚拟节点数量：500 , 标准差： 13470.1134初始节点数量 ： 10 , 额外虚拟节点数量：800 , 标准差： 12544.8851初始节点数量 ： 10 , 额外虚拟节点数量：1000 , 标准差： 10916.2339

第二次计算结果

初始节点数量 ： 10 , 额外虚拟节点数量：0 , 标准差： 194812.5116初始节点数量 ： 10 , 额外虚拟节点数量：10 , 标准差： 77715.3383初始节点数量 ： 10 , 额外虚拟节点数量：50 , 标准差： 29100.8077初始节点数量 ： 10 , 额外虚拟节点数量：100 , 标准差： 37129.9169初始节点数量 ： 10 , 额外虚拟节点数量：150 , 标准差： 22057.2922初始节点数量 ： 10 , 额外虚拟节点数量：200 , 标准差： 24287.8920初始节点数量 ： 10 , 额外虚拟节点数量：250 , 标准差： 20724.3688初始节点数量 ： 10 , 额外虚拟节点数量：300 , 标准差： 20066.3782初始节点数量 ： 10 , 额外虚拟节点数量：400 , 标准差： 17309.8450初始节点数量 ： 10 , 额外虚拟节点数量：500 , 标准差： 13314.3771初始节点数量 ： 10 , 额外虚拟节点数量：800 , 标准差： 12670.8190初始节点数量 ： 10 , 额外虚拟节点数量：1000 , 标准差： 10807.4067

从两次计算标准差对比来看，一致性 hash 算法在虚拟节点大于 150 之后，标准差有大幅度下降趋势 那么是不是可以无限的增加虚拟节点的数量呢？我认为不是的，选择合理的虚拟节点数量应该考虑以下因素：

1. 一个物理节点对应的虚拟节点与其他物理节点产生 hash 冲突的概率

2. 增加或删除虚拟节点后，需要移动的数据量大小

3. 其他因素

作业二：根据当周学习情况，完成一篇学习总结

本周主要讲解的是分布式系统中的技术选型，包括：分布式缓存，消息队列，负载均衡

缓存

缓存介于数据访问者与数据源之间的一种高速存储，当数据需要多次读取时，提高数据读取的速度 所以可以在各个层级之间加入缓存，比如：

1. CPU 缓存

2. 数据库缓存

3. JVM 编译缓存

4. 应用程序缓存

5. 分布式对象缓存

6. 。。。

关键指标：命中率

其他相关指标：

1. 缓存大小

2. 内存空间

3. 对象生存周期

缓存和 Buffer 有区别，缓存一般只用于读取，Buffer 一般即可写入又可读取。

在分布式系统缓存可能遇某些问题：

1. 缓存穿透 可以用缓存空值或使用布隆过滤器解决

2. 缓存雪崩 缓存时间随机设置，使用集群等

3. 缓存失效 加锁重构缓存

一致性 hash 算法

普通的 hash 算法在分布式应用中的不足：

比如，在分布式的存储系统中，要将数据存储到具体的节点上，如果我们采用普通的 hash 算法进行路由，将数据映射到具体的节点上，如 key%N，key 是数据的 key，N 是机器节点数，如果有一个机器加入或退出这个集群，则所有的数据映射都无效了，如果是持久化存储则要做数据迁移，如果是分布式缓存，则其他缓存就失效了。

一致性 Hash 算法是对 2^32 取模，将整个哈希值空间组织成一个虚拟的圆环，使用 hash 函数将服务器放到该环上，在使用的时候. 将数据 key 使用相同的函数 Hash 计算出哈希值，并确定此数据在环上的位置，从此位置沿环顺时针“行走”，第一台遇到的服务器就是其应该定位到的服务器！

好处：

1. 当增加或减少服务节点时，只需要对一部分的服务节点的数据进行处理，不会全部失效

不足：

1. 可能会导致数据分布不均衡 上文中的对比数据（可以增加虚拟节点来避免该情况）

消息队列

消息队列中间件是分布式系统中重要的组件，主要解决应用耦合，异步消息，流量削锋等问题。

1. 应用耦合 生产端和消费端不需要相互依赖

2. 异步消息 生产端不需要等待消费端响应，直接返回，提高了响应时间和吞吐量

3. 流量削锋 消费端可以按照自己的频率来处理，无需在高峰期增加太多资源，提高资源利用率

负载均衡架构

负载均衡服务器的实现

1. HTTP 重定向负载均衡

2. DNS 负载均衡

3. 反向代理负载均衡

4. IP 负载均衡

5. 数据链路负载均衡

常见的负载均衡算法：

1. 负载均衡算法

2. 轮询

3. 加权轮询

4. 随机

5. 最小连接

6. 原地址散列