Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

【干货】整理分布式技术框架常用的算法及策略

梦在旅途 2020-06-16 20:48:00 阅读数:107 评论数:0 点赞数:0 收藏数:0

将一些零散的知识点进行整理, 以便加深理解,方便查阅,也希望能帮到大家。

一、负载均衡算法

1. 随机

  1. 完全随机

通过系统随机函数,根据后端服务器列表的大小值来随机选择其中一台进行访问。由概率统计理论可以得知,随着调用量的增大,其实际效果越来越接近于平均分配流量到每一台后端服务器,也就是轮询的效果。

  1. 加权随机

    虽然还是采用的随机算法,但是为每台服务器根据不同的配置和负载情况来配置不同的权重,权重大的服务器获得的概率大一些,权重小的服务器获得的概率小一些。

2. 轮询

  1. 完全轮询

    将请求按顺序轮流地分配到服务器上,它均衡地对待后端的每一台服务器,而不关心服务器实际的连接数和当前的系统负载情况。

  2. 加权轮询

    根据服务器的不同处理能力,给每个服务器分配不同的权重值,使其能够将请求顺序的按照权重分配到后端服务器上,权重越大,对应的服务器每轮所获得的请求数量越多。

  3. 平滑加权轮询

    每个服务器都有两个权重变量:

    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=时间周期/限流值)的速度向令牌桶中增加令牌,直到令牌桶满,请求到达时向令牌桶请求令牌,如获取到令牌则通过请求,否则触发限流策略。

可参见网上文章:

常用4种限流算法介绍及比较

限流相关的算法

三、缓存淘汰(过期)策略

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. 分库分表方式

  1. 垂直分库

    为依据,按照业务归属不同,将不同的拆分到不同的中。

    结果:

    • 每个结构都不一样;
    • 每个数据也不一样,没有交集;
    • 所有并集是全量数据;
  2. 垂直分表

    字段为依据,按照字段的活跃性,将中字段拆到不同的(主表和扩展表)中。

    结果

    • 每个结构都不一样;

    • 每个数据也不一样,一般来说,每个表的字段至少有一列交集,一般是主键,用于关联数据;

    • 所有并集是全量数据;

  3. 水平分库

    字段为依据,按照一定策略(hash、range等),将一个中的数据拆分到多个中。

    结果:

    • 每个结构都一样;
    • 每个数据都不一样,没有交集;
    • 所有并集是全量数据;
  4. 水平分表

    字段为依据,按照一定策略(hash、range等),将一个中的数据拆分到多个中。

    结果:

    • 每个结构都一样;
    • 每个数据都不一样,没有交集;
    • 所有并集是全量数据;

2. 分库分表策略

  1. hash取模

    对指定的路由key(如:id)按分表总数进行取模,得到的结果即为对应的表序号

    • 优点:订单数据可以均匀的放到那4张表中,这样此订单进行操作时,就不会有热点问题。
    • 缺点:将来的数据迁移和扩容,会很难。
  2. range范围

    按一定范围路由key(如:id,时间戳)把对应的记录存放到同一张表中,多个范围区间则存放多张表【即:每个范围区间对应一张表】

    • 优点:有利于将来的扩容,不需要做数据迁移
    • 有热点问题,在某一个时间范围内某个表的IO压力可能会非常大
  3. range+hash分组

    首先用range方案让数据落地到一个范围里面(即:分组区间)。这样以后id再变大,那以前的数据是不需要迁移的。然后在这个范围里面(即:分组区间)再根据路由key(如:id)按分表总数(注意含所有分组中的所有分表总数)进行取模,得到的结果即为对应的表序号【即:在一定范围内均匀分布数据】

    • 优点:避免热问题,扩容相对容易
    • 缺点:实现较复杂
  4. 一致性hash

    通过哈希函数,每个节点都会被分配到环上的一个位置,每个键值也会被映射到环上的一个位置。这个键值最终被放置在距离该它的位置最近的,且位置编号大于等于该值的节点上面,即放置到顺时针的下一个节点上面。

    • 优点:避免热问题,扩容相对容易

    • 缺点:实现较复杂

​ 可参见网上文章:

海量数据分库分表方案(一)算法方案
数据库怎么分库分表,垂直?水平?
分库分表?如何做到永不迁移数据和避免热点?

版权声明
本文为[梦在旅途]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/zuowj/p/13144583.html