限流之令牌桶和漏桶算法

限流和降级的意义:

     保证核心服务的稳定性,随着访问量的不断增加,需要为系统能够处理的服务器数量设置一个极限阀值,超过这个阀值的请求直接拒绝。同时,为保证核心服务的可用,可以对某些核心服务进行降级,通过限制服务的最大访问量进行限流,通过管理控制台对单个微服务进行人工降级;

限流的方法:

     令牌桶,漏桶,信号量等

限流的类型

     分布式限流,单机限流(可以使用nginx的限流模块); 如果实现分布式限流的话就要一个公共的后端存储服务,比如redis,在nginx节点上利用lua读取redis配置信息;

限流的方式

  方式一:

    Nginx限流,使用限流模块,一般的可以使用nginx限流解决;主要是根据实际业务场景;如果是多台nginx场景下就不适用;


  方式二:

    通过令牌桶和漏桶算法实现

令牌桶算法图解

MyAnswer博客

算法实现 php版本执行lua

<?php
/**
 * Created by PhpStorm.
 * User: myanswer
 * Date: 2019/1/15
 * Time: 4:42 PM
 */

//令牌桶算法实现,使用redis集群执行lua脚本
$redis  = new RedisCluster(null,['45.40.207.143:6391','45.40.207.143:6392','45.40.207.143:6393']);
$lua = '
    local key = KEYS[1] --hash值的key值
    --获取redis里面的哈希值
    local data = redis.call("HMGET",key,"max_burst","curr_permits","last_second")
    local max_burst =tonumber(data[1]) --桶最大容量
    local curr_permits = tonumber(data[2]) --桶里当前令牌数量
    local rate =1  --每秒生成令牌的个数
    local last_second= data[3] --最后访问的时间
    local curr_second =ARGV[1] --当前时间
    local permits = ARGV[2] --当前请求消耗令牌
    
    local local_curr_permits = 10  --最终添加的令牌数量
    
    -- 通过判断是否有最后一次的访问时间,如果满足条件,证明不是第一次获取令牌
    if(last_second) then
          --令牌消耗,补充
          --当前时间 - 最后访问时间 / 1000 * r 
          local num = (curr_second - last_second) / 1000 * rate --当前需要添加的数量
          local expect_curr_permits = num + curr_permits --当前添加的数量+桶里剩余的数量
          local_curr_permits = math.min(expect_curr_permits,max_burst) --取得参数中最小值  
    else
       --第一次获取令牌记录时间
       return redis.call("HMSET",key,"last_second",ARGV[1]) 
    end
    --当前的令牌 - 请求消耗的令牌>0
    local res = -1
    if (curr_permits - permits > -1) then
       res =1
      redis.call("HMSET",key,"last_second",ARGV[1])  --更新最后请求时间
      --应该添加令牌数量-消耗的
      redis.call("HMSET",key,"curr_permits",local_curr_permits - permits) 
    else
       --令牌不够,拒绝访问,
       res = -1
       --更新这段时间应该添加令牌
       redis.call("HMSET",key,"curr_permits",local_curr_permits)
    end
     return res
';

$lasttime=(int)microtime(true)*1000;
$consume = 1; //这次请求所消耗的令牌
var_dump($redis->eval($lua,['{limit_1_2000}',$lasttime,$consume],1));
//返回-1 表示当前不能访问, 1表示当前可以访问

纯lua算法实现

local tool = require("tool")
--分割出一个redis集群连接的方法
    local config = {
        name = "testCluster",                   --rediscluster name
        serv_list = {                           --Redis集群节点地址+端口
        { ip = "45.40.207.143", port = 6391 },
        { ip = "45.40.207.143", port = 6392 },
        { ip = "45.40.207.143", port = 6393 },
        { ip = "45.40.207.143", port = 6394 },
        { ip = "45.40.207.143", port = 6395 },
        { ip = "45.40.207.143", port = 6396 }
        },
        keepalive_timeout = -1,                 --redis connection pool idle timeout
        keepalive_cons = 100,                  --redis connection pool size
        connection_timout = 1000,               --timeout while connecting
        max_redirection = 5                     --maximum retry attempts for redirection
    }
    local redis_cluster = require "rediscluster"
    red_c,err = redis_cluster:new(config)
    if not red_c then
            ngx.say(ngx.ERR, "connect to redis error : ", err)
            return
    end
    ngx.update_time() --为避免缓存的问题
    local ok,err=red_c:eval([[
                local key=KEYS[1]
                local rateLimit=redis.call("HMGET",key,"max_burst","curr_permits","rate","last_second")
                --local max_burst=tonumber(rateLimit[1]) --最大的容量
                local max_burst=5  --最大的容量
                local curr_permits=tonumber(rateLimit[2])  --桶里的令牌数(跟这段时间的消耗有关系,上一次请求有关系)
                --local rate=tonumber(rateLimit[3])   -- 每秒生成令牌的个数
                local rate=2
                local last_second=rateLimit[4] --最后一次的访问时间
                local curr_second=ARGV[1]  --当前时间
                local permits=tonumber(ARGV[2])   --这次请求消耗的令牌
                local local_curr_permits=max_burst --默认添加10个
                 -- 通过判断是否有最后一次的访问时间,如果满足条件,证明不是第一次获取令牌
                 if(type(last_second) ~= "boolean" and  last_second ~=nil ) then
                        -- 令牌消耗,补充
                        -- 当前时间 - 最后一次访问的时间 / 1000 * r
                       local reverse_permits =math.floor( (curr_second - last_second )/1000 * rate)  --当前需要添加的令牌数
                       --这段时间消耗的令牌 +桶里的令牌
                       local expect_curr_permits = reverse_permits + curr_permits  --实际需要添加的个数
                       --不能超过最大的令牌数,最终要添加的令牌数
                       local_curr_permits= math.min(expect_curr_permits,max_burst)
                 else
                       --记录下访问时间
                      return  redis.call("HMSET",key,"last_second",ARGV[1])
                 end
                local result=-1
                -- 当前的令牌 - 请求消耗的令牌>0,就消耗令牌
                if (local_curr_permits - permits >= 0 )  then
                    redis.call("HMSET",key,"last_second",ARGV[1]) --更新了令牌获取时间
                    redis.call("HMSET",key,"curr_permits",local_curr_permits - permits) --当前令牌
                    return  KEYS[1]..":1"
                else
                   --当前令牌如果减去消耗的令牌如果不大于0,那么表示令牌不够,重新加入令牌
                    redis.call("HMSET",key,"curr_permits",local_curr_permits)
                   -- redis.call("HMSET",key,"last_second",ARGV[1])
                      return  KEYS[1]..":-1" --避免hashtag不一致导致返回不了
                end
                return  KEYS[1]..":-1"
    ]],1,'{limit_1_2000}',string.format("%.3f",ngx.now()) * 1000,1)

local result = tool.split(ok,":")
if tonumber(result[2]) ~= 1 then
   ngx.header.content_type="text/html; charset=utf-8"
   ngx.say("人潮拥挤,请稍后再试")
   return ngx.exit(200)
end


解释图:

MyAnswer博客

MyAnswer博客
请先登录后发表评论
  • 最新评论
  • 总共0条评论