【干货】整理分布式技术框架常用的算法及策略
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【干货】整理分布式技术框架常用的算法及策略，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5891字，纯文字阅读大概需要9分钟。
内容图文
将一些零散的知识点进行整理， 以便加深理解，方便查阅，也希望能帮到大家。
一、负载均衡算法
1. 随机
- 完全随机
通过系统随机函数，根据后端服务器列表的大小值来随机选择其中一台进行访问。由概率统计理论可以得知，随着调用量的增大，其实际效果越来越接近于平均分配流量到每一台后端服务器，也就是轮询的效果。
-
加权随机
虽然还是采用的随机算法，但是为每台服务器根据不同的配置和负载情况来配置不同的权重，权重大的服务器获得的概率大一些，权重小的服务器获得的概率小一些。
2. 轮询
-
完全轮询
将请求按顺序轮流地分配到服务器上，它均衡地对待后端的每一台服务器，而不关心服务器实际的连接数和当前的系统负载情况。
-
加权轮询
根据服务器的不同处理能力，给每个服务器分配不同的权重值，使其能够将请求顺序的按照权重分配到后端服务器上，权重越大，对应的服务器每轮所获得的请求数量越多。
-
平滑加权轮询
每个服务器都有两个权重变量：
a：weight，配置文件中指定的该服务器的权重，这个值是固定不变的；
b：current_weight，服务器目前的权重（非固定权重）。一开始为0，之后会动态调整。
每次当请求到来，选取服务器时，会遍历数组中所有服务器。对于每个服务器，让它的current_weight增加它的weight；同时累加所有服务器的weight，并保存为total。
遍历完所有服务器之后，如果该服务器的current_weight是最大的，就选择这个服务器处理本次请求。最后把该服务器的current_weight减去total。
3. 哈希（Hash）法
先将后端服务器列表（如：按照地址IP）计算出哈希值，然后映射到HASH环上（如果服务器实例节点较少可以增加虚拟节点），当接收请求时，根据请求的信息（如请求的客户端IP、用户ID等）计算出哈希值，最后将请求信息的哈希值映射到HASH环上，按顺时针方向，确定落在哪个区间中，则选择区间的下一个服务器节点作为处理此次请求的服务器。
4. 最小连接数（Least Connections）法
由于后端服务器的配置不尽相同，对于请求的处理有快有慢，根据后端服务器当前的连接情况，动态地选取其中当前积压连接数最少的一台服务器来处理当前请求，尽可能地提高后端服务器的利用效率，将负载合理地分流到每一台机器。
可参见网上文章：浅谈负载均衡算法与实现 、一致性hash算法释义
二、限流算法
1. 计数器（固定窗口）算法
计数器算法是使用计数器在周期内累加访问次数，当达到设定的限流值时，触发限流策略。下一个周期开始时，进行清零，重新计数。
2. 滑动窗口算法
滑动窗口算法是将时间周期分为N个小周期，分别记录每个小周期内访问次数，并且根据时间滑动删除过期的小周期。
3. 漏桶算法
漏桶算法是访问请求到达时直接放入漏桶，如当前容量已达到上限（限流值），则进行丢弃（触发限流策略）。漏桶以固定的速率进行释放访问请求（即请求通过），直到漏桶为空。
4. 令牌桶算法
令牌桶算法是程序以r（r=时间周期/限流值）的速度向令牌桶中增加令牌，直到令牌桶满，请求到达时向令牌桶请求令牌，如获取到令牌则通过请求，否则触发限流策略。
可参见网上文章：
三、缓存淘汰（过期）策略
1. FIFO（First In First out）
先进先出，淘汰最先缓存的数据，新加入的缓存数据最迟被淘汰，完全符合队列。
2. LRU（Least recently used）
最近最少使用，淘汰一定时期内被访问次数最少的缓存数据，以次数作为参考。
3. LFU（Least frequently used）
最近使用次数最少，淘汰最长时间未被使用的页面，以时间作为参考。
4. Two queues（2Q）
2Q算法有两个缓存队列，一个是FIFO队列，一个是LRU队列。当数据第一次访问时，2Q算法将数据缓存在FIFO队列里面，当数据第二次被访问时，则将数据从FIFO队列移到LRU队列里面，两个队列各自按照自己的方法淘汰数据。
可参见网上文章：
常用缓存策略
Redis的过期策略和内存淘汰策略
四、缓存更新策略
1. Cache Aside
应用在查询数据的时候，先从缓存Cache中读取数据，如果缓存中没有，则再从数据库中读取数据，得到数据库的数据之后，将这个数据也放到缓存Cache中。如果应用要更新某个数据，也是先去更新数据库中的数据，更新完成之后，则通过指令让缓存Cache中的数据失效。
2. Read/Write Through
应用要读数据和更新数据都直接访问缓存服务，缓存服务同步的将数据更新到数据库，在应用的眼中只有缓存服务。
3. Write Behind
应用要读数据和更新数据都直接访问缓存服务，缓存服务异步的将数据更新到数据库（通过异步任务）
4. refresh-ahead
在缓存数据过期前，能自动的刷新缓存数据（在缓存过期前剩余时间区间内【可自定义】取数据时，缓存先将之前缓存的结果返回给外部应用程序，然后异步的再从数据库去更新缓存中的值，以尽可能的保证缓存的值是最新的。如果取数据的的时候超过了缓存的过期时间，就安装read-through的方式执行）
可参见网上文章：
Caching漫谈--关于Cache的几个理论
缓存服务的更新策略有哪些？
五、分库分表方式与策略
1. 分库分表方式
-
垂直分库
以表为依据，按照业务归属不同，将不同的表拆分到不同的库中。
结果：
- 每个库的结构都不一样；
- 每个库的数据也不一样，没有交集；
- 所有库的并集是全量数据；
-
垂直分表
以字段为依据，按照字段的活跃性，将表中字段拆到不同的表（主表和扩展表）中。
结果：
-
每个表的结构都不一样；
-
每个表的数据也不一样，一般来说，每个表的字段至少有一列交集，一般是主键，用于关联数据；
-
所有表的并集是全量数据；
-
-
水平分库
以字段为依据，按照一定策略（hash、range等），将一个库中的数据拆分到多个库中。
结果：
- 每个库的结构都一样；
- 每个库的数据都不一样，没有交集；
- 所有库的并集是全量数据；
-
水平分表
以字段为依据，按照一定策略（hash、range等），将一个表中的数据拆分到多个表中。
结果：
- 每个表的结构都一样；
- 每个表的数据都不一样，没有交集；
- 所有表的并集是全量数据；
2. 分库分表策略
-
hash取模
对指定的路由key（如：id）按分表总数进行取模，得到的结果即为对应的表序号
- 优点：订单数据可以均匀的放到那4张表中，这样此订单进行操作时，就不会有热点问题。
- 缺点：将来的数据迁移和扩容，会很难。
-
range范围
按一定范围路由key（如：id，时间戳）把对应的记录存放到同一张表中，多个范围区间则存放多张表【即：每个范围区间对应一张表】
- 优点：有利于将来的扩容，不需要做数据迁移
- 有热点问题，在某一个时间范围内某个表的IO压力可能会非常大
-
range+hash分组
首先用range方案让数据落地到一个范围里面（即：分组区间）。这样以后id再变大，那以前的数据是不需要迁移的。然后在这个范围里面（即：分组区间）再根据路由key（如：id）按分表总数（注意含所有分组中的所有分表总数）进行取模，得到的结果即为对应的表序号【即：在一定范围内均匀分布数据】
- 优点：避免热问题，扩容相对容易
- 缺点：实现较复杂
-
一致性hash
通过哈希函数，每个节点都会被分配到环上的一个位置，每个键值也会被映射到环上的一个位置。这个键值最终被放置在距离该它的位置最近的，且位置编号大于等于该值的节点上面，即放置到顺时针的下一个节点上面。
-
优点：避免热问题，扩容相对容易
-
缺点：实现较复杂
-
? 可参见网上文章：
海量数据分库分表方案（一）算法方案
数据库怎么分库分表，垂直？水平？
分库分表？如何做到永不迁移数据和避免热点？
内容总结
以上是互联网集市为您收集整理的【干货】整理分布式技术框架常用的算法及策略全部内容，希望文章能够帮你解决【干货】整理分布式技术框架常用的算法及策略所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。