精华内容
下载资源
问答
  • 限流算法, 以 Golang 方式

    万次阅读 2021-06-11 15:07:31
    限流算法, 以 Golang 方式 速率限制 在 Web Server、TCP 通讯、API 交互等领域中,速率限制,Rate Limit,一般是面向请求次数、流量等参数进行速率控制。有的时候它又被称作流量控制。 谈论流量控制时,大抵上要考虑...

    限流算法, 以 Golang 方式

    速率限制

    在 Web Server、TCP 通讯、API 交互等领域中,速率限制,Rate Limit,一般是面向请求次数、流量等参数进行速率控制。有的时候它又被称作流量控制。

    谈论流量控制时,大抵上要考虑到如下两个方面:

    1. 恒定速率(Constant Bit Rate,CBR)
    2. 变速速率(Varible Bit Rate,VBR)

    这并不是 TCP 通讯专有的概念。事实上,速率控制是个跨越多学科存在的通用概念。例如在音视频播放时(特别是在流媒体播放时),解码速率也是需要被控制的:如果硬件的视频缓冲区速率不够,解码就要等等;如果流数据获取的太慢,也会导致解码停滞——但在这时候,播放却不可以暂停/或者至少声音不可以停顿。此时同样涉及到流控问题。

    除了流控的速率问题之外,Rate Limit 最重要的一个设计与编码因素是进项流量的可抛弃性。

    对于 TCP 底层的带宽控制和流控来说,流量是不准许被抛弃的,相反,TCP 协议强制要求保证包的可达性。所以在TCP协议中反而会为失败包做重传。

    在微服务网关中,出于为下游服务提供平滑稳定的服务请求的目的,流控可能被要求是不可抛弃的,此时流控会摊平峰值请求到更长的时间片中,降低下游的瞬时功率。

    不过,对于提供公众 API 服务的厂商来说,他们会在服务网关中加入限流逻辑,如果你尝试发出高频请求,那么这些请求中越限的部分将被网关抛弃,网关内部的下游服务不会见到这部分越限请求。

    所以流控与限流相似也不相似,你需要明确区分他们。

    但在 Rate Limiter 的设计过程中,是可以在一个软件组件中同时提供这两者的,只是需要设计者时时清醒就行。

    实现方案

    为了下面的论述方便,我们以每秒钟100次(100 r/s)请求作为速率限制的指标。

    计数器方式

    反应在脑海里的关于速率限制的实现方案,首先自然会是计数器法。它很简单明了,假定你有一个 counter,初值为 100,每次请求则 counter 减 1,直到 counter 为零时才根据条件(例如时间已经超过了 1s)重置为初值。

    type counter struct {
    	Maximal int
    	Period  time.Duration
    	count   int
    	tick    int64 // in nanosecond
    }
    
    func (s *counter) Take(count int) bool {
    	if time.Now().UnixNano() > s.tick {
    		// if timeout, reset counter regally at first
    		s.count = 0
    		s.tick = time.Now().Add(s.Period).UnixNano()
    	}
    
    	s.count += count            // it's acceptable in HPC scene
    	return s.count <= s.Maximal // it's acceptable in HPC scene
    }
    

    计数器法的显著特点是缺乏均匀性。也就是说若在计时周期之中突发大批量请求时,Take() 也许仍会成功(只要计数器尚未超标)。但很显然,此时被准许的一批请求实际上是过于频繁,超标的。

    这种情形下我们的限流规则尚且算是符合。但当在计时周期末尾,以及下一个计时周期开始时,如果分别进入了大量的请求,尽管这些请求仍被通过了,但我们的限流规则实际上已经被打破了:如果我们考察的周期以前一计时周期的中点开始到下一周期的中点的话,这一段时间内所通过的请求数可能达到我们的限流规则的两倍。

    有时候,计数器法被表述为固定窗口法(Fixed Window),这和滑动窗口(Sliding Window)是相对应的。你可以将计数器法中的时间范围(也即案例中的1s)称作 1s 的统计窗口、或者计算窗口、或者观察窗口。

    Sliding Log

    有时候,Sliding Log 法被单列为一种算法。

    此时大家认为它是和滑动窗口有所不同的一种方法:它将消费者请求按照时间戳进行序列化存储,并追踪这个序列。在一个请求进入时,此前的一组时间戳序列将被求和,这个 Sum 值与相应的 Duration 相除就能得到这一段时间内的请求频率。如果频率太高则请求被拒绝,否则则通过。为了尽可能节省内存,系统只保留一定容量的时间戳记。

    但在我们看来,Sliding Log 实际上只是滑窗法的一种特定实现方案。

    滑动窗口法

    前文的讨论已经介绍到,要想解决计数器法的不平滑问题,我们需要更细的时间片粒度。不过,这显然是不怎么容易的。一方面,高精度时钟受制于硬件设施的不同,支持的力度也大不相同。另一方面,多细的粒度才叫细呢,1ms,还是 1ns,这是个问题——不同的场景对此可能会有不同的想法。

    所以我们还需要更换一下思考角度,为了求得细腻的时间片,改用滑动窗口的方式来间接达到任意时间片粒度。

    所谓滑动窗口法,实际上是指在请求发生时,向前检查一个观察窗口(例如 1s)的时间片,如果这段时间内的已经接纳的请求数尚未超标,就通过请求,反之拒绝。这样,无论请求以何种速率到来,我们始终在请求点向前的一个计时周期中做速率限制检测,这个时间片是随着请求点而推移的,所以我们将其称作滑动窗口。

    滑动窗口是在计算机科学中被广泛应用的一个通用概念。例如在 LZW(LZ77)压缩算法中,字符串匹配中,TCP 通讯流控等等场景都有滑窗出没。

    滑窗法的算法思路很容易理解。

    但对于速率限制场景来说,它的编程实现并不容易,因为要想向前追踪和统计任意窗口已授权请求数,其内务计算量也不小。

    我们已经知道可以存储每次请求的时间戳记(Sliding Log 法),然后按时钟方向反向求和来确定新请求是否已经越限。这是一种行得通的法子。如果你在做一个高吞吐量的 API Server,它的存储和计算代价可能也不小。

    另一种方法是,将时间片窗口硬性划分为 8 个小片(pieces),分别记录每个小片中的已授权数,当新请求到来需要做滑窗内追踪时,只需要固定向前计算8个小片的累计和即可。这样可以大幅度降低计算量、内存消耗量,但是也就算是滑窗法的粗糙版:至少比较于计数器法精细度有大幅度提高。

    对于高频交易来说,在速率限制这一任务上消耗大量的CPU或内存是不可接受的。所以生产环境中未必会采用滑窗思路落地到代码实现上。

    漏桶法(Leaky Bucket)

    基本原理

    任意窗口中,已经授权的请求数不容易获取、或者计算量偏大,既然如此,我们可以反其道而行:假设一个恒定容量(100 滴水)的水桶接水,水龙头出水的速率取决于请求的多少,而水桶下方有一开口,正好能以 10ms 的速率匀速出水。那么无论进入的请求有多少,他们被这个水桶以特定的方式所约束,始终最多只能有等同于水桶容量的请求能被放过。

    如果请求量过量,水龙头出水过多,则水桶溢出,这些多余的请求就被抛弃了。

    如果不想抛弃溢出的请求,那么一般是采用自旋的方式等待水桶不满,然后再提交请求,直到所有请求都被放过,这就是以时间为代价做放过了。换句话说,我们找个足够大的额外的桶吧溢出的水接下来,然后重新送到水龙头上去滴水好了。

    如此,我们就得到了速率限制的水桶思维版:漏桶法。

    根据出水策略的不同,非匀速的进入请求只要被准许,则可以被原样放出,或者是被整形后以恒定的速率放出(例如每 10ms 放出一个请求)。

    很明显,如果不想抛弃多余的请求,那么你必须保证一段时间内的总请求量不会超过速率限制。否则这些阻塞的请求会造成瓶颈问题。

    开源实现

    在很多开源实现方案中,漏桶法被限定为古典式,也就是所谓的匀速出水模式(又称作带流量整形 Traffic Shaping 的漏桶算法)。

    这类实现中,采用的是速率计算算法,典型的实现(例如 kevinms/leakybucket-go)可能是这样的:

    // Makes it easy to test time based things.
    var now = time.Now
    
    // LeakyBucket represents a bucket that leaks at a constant rate.
    type LeakyBucket struct {
    	// The identifying key, used for map lookups.
    	key string
    
    	// How large the bucket is.
    	capacity int64
    
    	// Amount the bucket leaks per second.
    	rate float64
    
    	// The priority of the bucket in a min-heap priority queue, where p is the
    	// exact time the bucket will have leaked enough to be empty. Buckets that
    	// are empty or will be the soonest are at the top of the heap. This allows
    	// for quick pruning of empty buckets that scales very well. p is adjusted
    	// any time an amount is added to the Queue().
    	p time.Time
    
    	// The index is maintained by the heap.Interface methods.
    	index int
    }
    
    func NewLeakyBucket(rate float64, capacity int64) *LeakyBucket {
    	return &LeakyBucket{
    		rate:     rate,
    		capacity: capacity,
    		p:        now(),
    	}
    }
    
    func (b *LeakyBucket) Add(amount int64) int64 {
    	count := b.Count()
    	if count >= b.capacity {
    		// The bucket is full.
    		return 0
    	}
    
    	if !now().Before(b.p) {
    		// The bucket needs to be reset.
    		b.p = now()
    	}
    	remaining := b.capacity - count
    	if amount > remaining {
    		amount = remaining
    	}
    	t := time.Duration(float64(time.Second) * (float64(amount) / b.rate))
    	b.p = b.p.Add(t)
    
    	return amount
    }
    

    在上面的实现中,Add() 返回 0 表示水桶已满,也即请求获准失败。

    它的实现稍微有些不利于我们按惯性去理解。

    此外,uber-go/ratelimit 实现的就是完整的漏桶法匀速出水方案,为了做到匀速出水,在它的 Take() 中以阻塞方式进行检测,除非到达 10ms 边界,否则不会返回,从而达到了精确的匀速出水。由于涉及到的每个请求的状态量有多个,因此 uber 使用了 unsafe.pointer 的原子操作,这就使得其代码不是那么直观。所以我们没有在这里列举它的实现代码。

    我们的版本

    这类古典算法有时候也许并不是特别好的选择。他们的问题在于在请求进入时会在 Take() 处被阻塞,如此一来入口处可能产生请求堆积而无法有效地抛弃多余请求。进一步的表现为防 DDOS 能力较差。当然,其好处在于,只要生产场景要求的是进入请求不准许被抛弃,那么它们将被有效地堆积直到下游服务最终吃进,这样的特性对于微服务削峰是恰当的。

    非阻塞实现

    根据这些实作上的认识,我们另行实现了一套漏桶算法(完整 repo),允许提供非阻塞入口方式:

    func New(maxCount int64, d time.Duration) *leakyBucket {
    	return (&leakyBucket{
    		int64(maxCount),
    		make(chan struct{}),
    		int64(d) / int64(maxCount),
    		time.Now().UnixNano(),
    		0,
    	}).start(d)
    }
    
    type leakyBucket struct {
    	Maximal     int64
    	exitCh      chan struct{}
    	rate        int64
    	refreshTime int64 // in nanoseconds
    	count       int64
    }
    
    func (s *leakyBucket) Count() int64            { return atomic.LoadInt64(&s.count) }
    func (s *leakyBucket) Available() int64        { return int64(s.count) }
    func (s *leakyBucket) Capacity() int64         { return int64(s.Maximal) }
    
    func (s *leakyBucket) Close() {
    	close(s.exitCh)
    }
    
    func (s *leakyBucket) start(d time.Duration) *leakyBucket {
    	if s.rate < 1000 {
    		log.Errorf("the rate cannot be less than 1000us, it's %v", s.rate)
    		return nil
    	}
    
    	// fmt.Printf("rate: %v\n", time.Duration(s.rate))
    
    	// go s.looper(d)
    	return s
    }
    
    func (s *leakyBucket) looper(d time.Duration) {
    	// nothing to do
    }
    
    func (s *leakyBucket) max(a, b int64) int64 {
    	if a < b {
    		return b
    	}
    	return a
    }
    
    func (s *leakyBucket) take(count int) (requestAt time.Time, ok bool) {
    	requestAt = time.Now()
    
    	s.count = s.max(0, s.count-(requestAt.UnixNano()-s.refreshTime)/s.rate*int64(count))
    	s.refreshTime = requestAt.UnixNano()
    
    	if s.count < s.Maximal {
    		s.count += int64(count)
    		ok = true
    	}
    
    	return
    }
    
    func (s *leakyBucket) Take(count int) (ok bool) {
    	_, ok = s.take(count)
    	return
    }
    
    func (s *leakyBucket) TakeBlocked(count int) (requestAt time.Time) {
    	var ok bool
    	requestAt, ok = s.take(count)
    	for !ok {
    		time.Sleep(time.Duration(s.rate - (1000 - 1)))
    		_, ok = s.take(count)
    	}
    	time.Sleep(time.Duration(s.rate-int64(time.Now().Sub(requestAt))) - time.Millisecond)
    	return
    }
    

    在这套实现方案中,利用 Take() 的无阻塞效果,你可以有以下的自定义选择:

    1. 首先你要通过非阻塞的 Take() 尝试获得准许
    2. 如果未能获准通过:
      1. 如果你不想抛弃请求,则自行建立一个 queue 来缓存和延后重新尝试获得准许。
      2. 如果你需要抛弃越限请求,那么什么都不做好了
    3. 对于获准的请求,在 Take() 返回后得到的是不经过匀速整形的出水。

    兼容于 uber-go/ratelimit

    不过,如果你是在制作一份用于削峰目的的 rate limiter 中间件的话,你可能还是希望像 uber 那样的效果:不抛弃未获准请求,且匀速出水。这没有关系——尽管有点粗劣——我们还是提供了一份阻塞版本 TakeBlocked(),它能够让获准请求匀速流出。以测试函数为例:

    import "github.com/hedzr/rate/leakybucket"
    
    func TestLeakyBucketLimiter(b *testing.T) {
    	var counter int
    	l := leakybucket.New(100, time.Second, false) // one req per 10ms
    	defer l.Close()
    	time.Sleep(300 * time.Millisecond)
    	prev := time.Now()
    	for i := 0; i < 20; i++ {
    		ok := l.TakeBlocked(1)
    		now := time.Now()
    		counter++
    		fmt.Println(i, now.Sub(prev))
    		prev = now
    		time.Sleep(1 * time.Millisecond)
    	}
    	b.Logf("%v requests allowed.", counter)
    }
    

    运行后的结果是这样的:

    $ go test -v -race -test.run='^TestLeakyBucketLimiter$' ./leakybucket
    ==== RUN   TestLeakyBucketLimiter
    0 9.468477ms
    1 10.47512ms
    2 12.589327ms
    3 10.364861ms
    4 11.820381ms
    5 10.353834ms
    6 12.504309ms
    7 10.167151ms
    8 11.623466ms
    9 10.487361ms
    10 10.72498ms
    11 12.435839ms
    12 11.73813ms
    13 10.956558ms
    14 11.893156ms
    15 11.964504ms
    16 11.856545ms
    17 11.094344ms
    18 10.978074ms
    19 10.632583ms
        lb_test.go:36: 20 requests allowed.
    --- PASS: TestLeakyBucketLimiter (0.53s)
    PASS
    ok      github.com/hedzr/rate/leakybucket       0.957s
    

    而如果没有能够获准时,该请求将会一直阻塞下去,直到下一次获取成功——由于rate=10ms(即1000ms/100次)的约束的存在,所以阻塞也不会超出 rate 边界太多。

    虽然不那么精确,也很有点拙劣,但是我们弄了一个,对吧。

    面向 Public API - 简化的 Gin 中间件

    如果要建立 Public API 的场景的话,越限请求(尤其是恶意的请求)必须是被抛弃的,这时候 uber 的 ratelimit 版本就不合适了,此时非阻塞版本才是恰当的选择。

    一个简化的 gin 中间件可以这样来写:

    func (r *Limiter) getRL(ctx gin.Context) rateapi.Limiter {
    	if r.limiter == nil {
    		r.limiter = leakybucket.New(100, time.Second, false)
    	}
    	return r.limiter
    }
    
    func (r *Limiter) SimpleMiddleware() gin.HandlerFunc {
    	return func(ctx *gin.Context) {
    		limiter := r.getRL(ctx)
    		if err != nil {
    			ctx.AbortWithError(429, err)
    		} else if limiter != nil {
    			if limiter.Take(1) {
    				ctx.Writer.Header().Set("X-RateLimit-Remaining", fmt.Sprintf("%d", limiter.Available()))
    				ctx.Writer.Header().Set("X-RateLimit-Limit", fmt.Sprintf("%d", limiter.Capacity()))
    				ctx.Next()
    			} else {
    				err = errors.New("Too many requests")
    				ctx.Writer.Header().Set("X-RateLimit-Remaining", fmt.Sprintf("%d", limiter.Available()))
    				ctx.Writer.Header().Set("X-RateLimit-Limit", fmt.Sprintf("%d", limiter.Capacity()))
    				ctx.AbortWithError(429, err)
    			}
    		} else {
    			ctx.Next()
    		}
    	}
    }
    

    按照约定俗成的标准,被抛弃的请求会得到 response header 通知:

    Gin 中间件

    作为上述简化代码的完善版本,我们提供了一个 gin ratelimit 中间件,你可以直接取用:

    import "github.com/hedzr/rate/middleware"
    
    func engine() *gin.Engine {
      r := gin.Default()
      r.Use(middleware.NewLimiterForGin(time.Second, 100, func(ctx *gin.Context) (string, error){
        key := ctx.Request.Header.Get("X-API-KEY")
    		if key != "" {
    			return key, nil
    		}
    		ctx.JSON(403, gin.H{"code": 2901, "message": "API key is missing"})
    		return "", errors.New("API key is missing")
      }))
      return r
    }
    

    在示例中,你提供一个 keygenFunc 给中间件,这个函数应该返回一个唯一的 key,例如某个 API Client 所申请得到的 API KEY,然后中间件就会为这个 key 单独维护一个 rate limiter。

    根据你的业务场景,你可以选择更恰当的 keygenFunc 因子。比方说不是在检测 X-API-KEY header,而是检测 header 中的 X-USER-TOKEN,或者以 IP/GeoIP 为 key 的依据,那么我们可以获得对特定用户、不同IP、特定地区的限流政策。

    当然,在 HPC 场景,你可能还需要在我们提供的这个中间件的基础上进一步地拓展,例如对大规模 API KEYs 场景你需要有分区分节点的措施、以防止单个节点上的大量 rate limiters 导致内存溢出,等等。

    而一旦采用了多节点分布式计算策略时,你更需要改造和采用分布式的 ratelimit 核心算法——我们所提供的完整 repo并不直接支持分布式计算场景。

    令牌法(Token Bucket)

    漏桶法面向进入请求进行整形(去掉多余的,仅获准者被漏下),但是它虽然是我们面对滑窗难以编码而转换的新思路,却和滑窗的差异略大。

    所以令牌法才是更接近滑窗法思路的调优算法。

    总的来说,我们假设一个 producer 以恒定速率(每 10ms 一个)制造令牌,而一个请求被获准时则消耗一块令牌。如此一来,单位时间片中已经授权了多少请求就不再是重点,重点现在变为令牌桶中有否可用令牌的问题。

    由于令牌总是被匀速制造的,所以进入请求会被均匀地限流(也就是在 10ms 周期的所有多余的请求都不被获准),令牌法比较于前面几种方法来说在这个领域有绝对优势。

    反过来说,如果进入请求不可以被抛弃的话,令牌法就会带来额外的阻塞开销:未能获准的请求需要在一个更慢的队列中(或者直接就地阻塞的方式)重试直到获取到令牌而通过时为止。

    于是我们有这样的实现代码:

    func New(maxCount int64, d time.Duration) *tokenBucket {
    	return (&tokenBucket{
    		int32(maxCount),
    		d,
    		int64(d) / int64(maxCount),
    		make(chan struct{}),
    		int32(maxCount),
    	}).start(d)
    }
    
    type tokenBucket struct {
    	Maximal int32
    	period  time.Duration
    	rate    int64
    	exitCh  chan struct{}
    	count   int32
    }
    
    func (s *tokenBucket) Count() int32            { return atomic.LoadInt32(&s.count) }
    func (s *tokenBucket) Available() int64        { return int64(s.count) }
    func (s *tokenBucket) Capacity() int64         { return int64(s.Maximal) }
    
    func (s *tokenBucket) Close() {
    	close(s.exitCh)
    }
    
    func (s *tokenBucket) start(d time.Duration) *tokenBucket {
    	if s.rate < 1000 {
    		log.Errorf("the rate cannot be less than 1000us, it's %v", s.rate)
    		return nil
    	}
    
    	go s.looper(d)
    	return s
    }
    
    func (s *tokenBucket) looper(d time.Duration) {
    	ticker := time.NewTicker(d / time.Duration(s.Maximal))
    	// fmt.Printf("token building spped is: 1req/%v\n", d/time.Duration(s.Maximal))
    	defer func() {
    		ticker.Stop()
    	}()
    	for {
    		select {
    		case <-s.exitCh:
    			return
    		case <-ticker.C:
    			vn := atomic.AddInt32(&s.count, 1)
    			if vn < s.Maximal {
    				continue
    			}
    
    			vn %= s.Maximal
    			if vn > 0 {
    				atomic.StoreInt32(&s.count, s.Maximal)
    			}
    		}
    	}
    }
    
    func (s *tokenBucket) take(count int) bool {
    	if vn := atomic.AddInt32(&s.count, -1*int32(count)); vn >= 0 {
    		return true
    	}
    	atomic.StoreInt32(&s.count, 0)
    	return false
    }
    
    func (s *tokenBucket) Take(count int) bool {
    	ok := s.take(count)
    	return ok
    }
    
    func (s *tokenBucket) TakeBlocked(count int) (requestAt time.Time) {
    	requestAt = time.Now().UTC()
    	ok := s.take(count)
    	for !ok {
    		time.Sleep(time.Duration(s.rate - (1000 - 1)))
    		ok = s.take(count)
    	}
    	// time.Sleep(time.Duration(s.rate-int64(time.Now().Sub(requestAt))) - time.Millisecond)
    	return requestAt
    }
    

    在我们的这份实现中,与漏桶法相似地支持了一些高级特性,例如支持非阻塞或者阻塞版本,等等。Line 76 目前被我们注释掉了,因为暂时我们不希望在 Token Bucket 算法中做匀速出水的额外处理:事实上,由于令牌本身的产出是均匀的,所以在除开一些边界条件的其它多数情况中,我们直接就能获得相对均匀的出水。而加上 Line 76 的效果只是相对更加均匀而已,我认为这不一定是必须的。

    其它特性

    在我们的令牌桶实现中,由于已经做了算法抽象,所以在漏桶法中已经描述过的特性,可以毫无障碍地改为令牌桶法。具体来说,使用我们的 rate 组件的方式是这样的:

    package main
    
    import (
    	"fmt"
    	"github.com/hedzr/rate"
    	"time"
    )
    
    func main() {
      // rate.LeakyBucket, rate.TokenBucket, ...
    	l := rate.New(rate.LeakyBucket, 100, time.Second)
    	for i := 0; i < 120; i++ {
    		ok := l.Take(1)
    		if !ok {
    			fmt.Printf("#%d Take() returns not ok, counter: %v\n", i, rate.CountOf(l))
    			time.Sleep(50 * time.Millisecond)
    		}
    	}
    }
    

    与其相似地,在 web server 框架中以中间件的方式使用我们的 rate 组件:

    import (
      "github.com/hedzr/rate"
      "github.com/hedzr/rate/middleware"
    )
    
    func engine() *gin.Engine {
    	config := &middleware.Config{
    		Name:          "A",
    		Description:   "A",
    		Algorithm:     stirng(rate.TokenBucket),
    		Interval:      time.Second,
    		MaxRequests:   1000,
    		HeaderKeyName: "X-API-TOKEN",
    		ExceptionKeys: nil,
    	}
    	r := gin.Default()
      rg := r.Group("/api")
      rg.Use(middleware.ForGin(config))
      // ...
      
      config2 := ...
      r.Post("/login", middleware.ForGin(config2), loginHandler)
    	return r
    }
    

    如果你也在采用我们的 cmdr,middleware.LoadConfig(“server.rate-limites”) 或者 middleware.LoadConfigForGin(“server.rate-limits”, rg) 还可以进一步简化你的代码编写。

    对 looper 做增强

    在 looper() 的实现方法中,我们采用了一个匀速 producer 来生产令牌。

    考虑到更多潜在的限流策略可能性,在这里实际上可以考虑采用变速方案。一些典型的可能性有:

    1. logN 或者 ln 加速器方案
    2. 平滑变比匀速:以一个时间片为统计单位,时刻调整 rate 值,从而在突发流量消耗了大部分令牌之后,降低今后一段时间的令牌发放速度。在 Google Guava 中它被称为 SmoothBusrty。
    3. 平滑预热匀速:又被称作 SmoothWarmUp。在一个时间片的前一部分时间里以较快速度发放较多令牌,此时发放令牌的速度呈现出负加速度;随后,剩余时间内剩余令牌以匀速放出。
    4. 其它更多方式:取决于具体的生产场景,可以通过定制 looper 算法来提供更多的策略(示例代码中未予以实现)。

    值得注意的是,令牌法不但思路易于理解,代码实现也极其容易。不仅如此,令牌法的运行开销也差不多在各类实现中是最小的。

    在开源实现中,juju/ratelimit 同样地实现了令牌桶算法。

    比较

    在前面的思考中,我们已经提到了各个算法的一些特点。

    在本文范围内,最后的一点时间,姑且简单总结一下几种典型算法的异同:

    • 计数器方式:最容易实现,但应变能力最差,效率较高
    • 滑动窗口法:理论易于理解,即尽可能地缩小计量粒度,从而将计数器的应变能力平滑地提高。然而很难以代码高效实现。
    • 漏桶法:较好的取舍,针对进项流量进行整形,(通常)以匀速放出流量。
    • 令牌法:相对最优的取舍,针对出口进行整形,(通常或可选地)以近似匀速放出流量。非常容易拓展为针对业务场景进行整形定制。

    取决于进项流量可否被抛弃,在 ratelimit 实现时要注意采用恰当的方法:

    1. 考虑是否采用异步方式(另行处理被抛弃流量)/ 非阻塞模式(由调用者自行处理被抛弃流量)
      1. 异步方式不适用于 API 接口的限流场所或者用作 web server middlerware
      2. 异步方式、或者非阻塞方式有最好的进项流量接收性能
    2. 非阻塞模式或阻塞方式的选择
    展开全文
  • 网关限流算法及实现总结

    千次阅读 2019-12-14 16:51:16
    在高并发的系统中,往往需要在系统中做限流,一方面是为了防止大量的请求使服务器过载,导致服务不可用,另一方面是为了防止网络攻击。 常见的限流场景有: 限制总并发数(比如数据库连接池、线程池) 限制瞬时...

    在高并发的系统中,往往需要在系统中做限流,一方面是为了防止大量的请求使服务器过载,导致服务不可用,另一方面是为了防止网络攻击。

    常见的限流场景有:

    • 限制总并发数(比如数据库连接池、线程池)
    • 限制瞬时并发数(如 nginx 的 limit_conn 模块,用来限制瞬时并发连接数)
    • 限制时间窗口内的平均速率(如 Guava 的 RateLimiter、nginx 的 limit_req 模块,限制每秒的平均速率)
    • 其他还有如限制远程接口调用速率、限制 MQ 的消费速率
    • 另外还可以根据网络连接数、网络流量、CPU 或内存负载等来限流。

    1.算法篇

    常用的限流算法有:计数器,漏桶,令牌桶。

    1.1.计数器算法

    请求限流简单的做法是维护一个单位时间内的计数器,每次请求计数器加1,当单位时间内计数器累加到大于设定的阈值,则之后的请求都被拒绝,直到单位时间已经过去,再将计数器 重置为零。
    这种方式有个缺点:如果在单位时间1s内允许100个请求,在10ms已经通过了100个请求,那后面的990ms,只能眼巴巴的把请求拒绝,我们把这种现象称为“突刺现象”。

    计数器算法在生产实践中使用较少,在工业界常用的是更平滑的限流算法:漏桶算法令牌桶算法

    1.2.漏桶算法

    漏桶算法很简单,水(请求)先进入到漏桶里,漏桶以一定的速度出水(接口有响应速率),当水流入速度过大会直接溢出(访问频率超过接口响应速率),然后就拒绝请求,可以看出漏桶算法能强行限制请求的处理速率。

    漏桶算法

    算法思想是:

    1. 水(请求)从上方倒入水桶,从水桶下方流出(被处理);
    2. 来不及流出的水存在水桶中(缓冲),以固定速率流出;
    3. 水桶满后水溢出(丢弃)。
      这个算法的核心是:缓存请求、匀速处理、多余的请求丢弃。

    漏桶算法中主要有两个变量:

    • 一个是桶大小(burst),即支持流量突发增多时可以存多少的水;
    • 另一个是漏斗大小(rate),即漏桶漏出速率的固定参数;

    所以,即使网络中不存在资源冲突(没有发生拥塞),漏桶算法也不能使流突发(burst)到端口速率。因此,漏桶算法对突发流量不做额外处理,无法应对存在突发特性的流量。

    1.3.令牌桶算法

    令牌桶算法 和漏桶算法 效果一样但方向相反的算法,更加容易理解。随着时间流逝,系统会按恒定 1/QPS 时间间隔(如果 QPS=100,则间隔是 10ms)往桶里加入 Token(想象和漏洞漏水相反,有个水龙头在不断的加水),如果桶已经满了就不再加了。新请求来临时,会各自拿走一个 Token,如果没有 Token 可拿了就阻塞或者拒绝服务。
    令牌桶算法

    算法思想是:

    1. 令牌以固定速率产生,并缓存到令牌桶中;
    2. 令牌桶放满时,多余的令牌被丢弃;
    3. 请求要消耗等比例的令牌才能被处理;
    4. 令牌不够时,请求被丢弃。

    漏桶和令牌桶算法最明显的区别就是是否允许突发流量(burst)的处理,漏桶算法能够强行限制数据的实时传输(处理)速率,对突发流量不做额外处理;而令牌桶算法能够在限制数据的平均传输速率的同时允许某种程度的突发流量处理(桶内可累计缓存最大令牌数量)。

    2.实践篇

    在生产实践中,请求限流通常依赖于api网关来实现,常用网关基本都支持限流功能,例如常用的nginx和springcloud-gateway。

    2.1.nginx限流

    Nginx按请求速率限速模块使用的是优化漏桶算法(支持突发量请求处理,详见nodelay参数),即能够强行保证请求的实时处理速度不会超过设置的阈值。Nginx官方版本限制IP的连接和并发分别有两个模块:

    • ngx_http_limit_req_module 用来限制单位时间内的请求数,即速率限制,采用的漏桶算法 “leaky bucket”。
    • ngx_http_limit_conn_module 用来限制同一时间连接数,即并发限制。

    2.1.1.Module ngx_http_limit_req_module

    参数配置

    Syntax: limit_req_zone key zone=name:size rate=req/time; 
    Default: — 
    Context: http
    
    # 语法
    Syntax: limit_req zone=name [burst=number] [nodelay];
    # 默认值(无)
    Default: -
    # 作用域
    Context: http, server, location
    

    示例

    http{
    
     # 声明请求限流存储区
     limit_req_zone $binary_remote_addr zone=req_one:10m rate=1r/s
     server{
      ...
      limit_req zone=req_one burst=5 nodelay;
      ...
     }
    }
    

    配置说明:

    limit_req_zone $binary_remote_addr zone=req_one:10m rate=1r/s

    • 第一个参数:$binary_remote_addr 表示通过remote_addr这个标识来做限制,“binary_”目的是缩写内存占用量,是限制同一客户端ip地址。
    • 第二个参数:zone=one:10m 表示生成一个大小为10M,名字为one的内存区域,用来存储访问的频次信息。
    • 第三个参数:rate=1r/s表示允许相同标识的客户端的访问频次,这里限制的是每秒1次,还可以有比如30r/m的。

    limit_req zone=one burst=5 nodelay;

    • 第一个参数:zone=one 设置使用哪个配置区域来做限制,与上面limit_req_zone 里的name对应。
    • 第二个参数:burst=5,重点说明一下这个配置,burst爆发的意思,这个配置的意思是设置一个大小为5的缓冲区当有大量请求(爆发)过来时,超过了访问频次限制的请求可以先放到这个缓冲区内,缓冲区容量为5。
    • 第三个参数:nodelay 该参数允许请求在排队的时候就立即被处理,也就是说只要请求能够进入burst队列,就会立即被后台worker处理,请注意,这意味着burst设置了nodelay时,系统瞬间的QPS可能会超过rate设置的阈值。nodelay参数要跟burst一起使用才有作用。否则所有请求会等待排队按漏桶固定速度处理。

    其他参数:

    • limit_req_log_level 当服务器由于限速或缓存,设置写入日志的级别。
    Syntax: limit_req_log_level info | notice | warn | error;
    Default: limit_req_log_level error; 
    Context: http, server, location
    
    • limit_req_status 设置拒绝请求的返回值,只能设置400-599之间
    Syntax: limit_req_status code; 
    Default: limit_req_status 503;
    Context: http, server, location
    

    2.1.2.Module ngx_http_limit_conn_module

    这个模块用来限制单个IP的连接数,并非所有的连接都被计数,只有在服务器处理了请求并已经读取了完整的请求头时,才被计数。
    参数配置:

    Syntax: limit_conn_zone key zone=name:size; 
    Default: — 
    Context: http
    
    Syntax: limit_conn zone number; 
    Default: — 
    Context: http, server, location
    

    示例:
    只允许每个IP保持一个连接

    limit_conn_zone $binary_remote_addr zone=addr:10m; 
    server {
        location /download/ { 
            limit_conn addr 1; 
        }
    

    可以配置多个limit_coon指令,例如配置客户端每个IP连接数,同时限制服务端最大保持连接数

    limit_conn_zone $binary_remote_addr zone=perip:10m; 
    limit_conn_zone $server_name zone=perserver:10m; 
    server {
        ... 
        limit_conn perip 10; 
        limit_conn perserver 100; 
        ...
    }
    

    在这里,客户端IP地址作为键,不是$remote_addr,而是使用$binary_remote_addr变量。
    $remote_addr 变量的大小可以从7到15个字节不等。存储的状态在32位平台上占用32或64字节的内存,在64位平台上总是占用64字节。对于IPv4地址,$binary_remote_addr变量的大小始终为4个字节,对于IPv6地址则为16个字节。存储状态在32位平台上始终占用32或64个字节,在64位平台上占用64个字节。一个兆字节的区域可以保持大约32000个32字节的状态或大约16000个64字节的状态。如果区域存储耗尽,服务器会将错误返回给所有其他请求。

    其他参数

    • limit_conn_log_level 当超出连接数时,设置日志记录级别
    Syntax: limit_conn_log_level info | notice | warn | error;
    Default: limit_conn_log_level error;
    Context: http, server, location
    
    • limit_conn_status 设置拒绝请求时返回码
    Syntax: limit_conn_status code; 
    Default: limit_conn_status 503; 
    Context: http, server, location
    

    实例一 限制访问速率

    limit_req_zone $binary_remote_addr zone=mylimit:10m rate=2r/s; 
    server {
        location / { 
            limit_req zone=mylimit; 
            }
        }
    

    上述规则限制了每个IP访问的速度为2r/s,并将该规则作用于根目录。如果单个IP在非常短的时间内并发发送多个请求,结果会怎样呢?
    在这里插入图片描述

    我们使用单个IP在10ms内发并发送了6个请求,只有1个成功,剩下的5个都被拒绝。我们设置的速度是2r/s,为什么只有1个成功呢,是不是Nginx限制错了?当然不是,是因为Nginx的限流统计是基于毫秒的,我们设置的速度是2r/s,转换一下就是500ms内单个IP只允许通过1个请求,从501ms开始才允许通过第二个请求。

    实例二 burst缓存处理

    短时间内发送大量请求,Nginx按照毫秒级精度统计,超出限制的请求直接拒绝。这在实际场景中未免过于苛刻,真实网络环境中请求到来不是匀速的,很可能有请求“突发”的情况,也就是“一股子一股子”的。Nginx考虑到了这种情况,可以通过burst关键字开启对突发请求的缓存处理,而不是直接拒绝。

    limit_req_zone $binary_remote_addr zone=mylimit:10m rate=2r/s; 
    server { 
        location / { 
            limit_req zone=mylimit burst=4; 
        } 
    }
    

    我们加入了burst=4,意思是每个key(此处是每个IP)最多允许4个突发请求的到来。如果单个IP在10ms内发送6个请求,结果会怎样呢?
    在这里插入图片描述

    相比实例一成功数增加了4个,这个我们设置的burst数目是一致的。具体处理流程是:1个请求被立即处理,4个请求被放到burst队列里,另外一个请求被拒绝。通过burst参数,我们使得Nginx限流具备了缓存处理突发流量的能力。
    但是请注意:burst的作用是让多余的请求可以先放到队列里,慢慢处理。如果不加nodelay参数,队列里的请求不会立即处理,而是按照rate设置的速度,以毫秒级精确的速度慢慢处理。

    实例三 nodelay降低排队时间

    实例二中我们看到,通过设置burst参数,我们可以允许Nginx缓存处理一定程度的突发,多余的请求可以先放到队列里,慢慢处理,这起到了平滑流量的作用。但是如果队列设置的比较大,请求排队的时间就会比较长,用户角度看来就是响应变长了,这对用户很不友好。有什么解决办法呢?nodelay参数允许请求在排队的时候就立即被处理,也就是说只要请求能够进入burst队列,就会立即被后台worker处理,请注意,这意味着burst设置了nodelay时,系统瞬间的QPS可能会超过rate设置的阈值。nodelay参数要跟burst一起使用才有作用。

    limit_req_zone $binary_remote_addr zone=mylimit:10m rate=2r/s;
    server { 
        location / { 
            limit_req zone=mylimit burst=4 nodelay;
        } 
    }
    

    单个IP 10ms内并发发送6个请求,结果如下:
    在这里插入图片描述

    跟实例二相比,请求成功率没变化,但是总体耗时变短了。这怎么解释呢?实例二中,有4个请求被放到burst队列当中,工作进程每隔500ms(rate=2r/s)取一个请求进行处理,最后一个请求要排队2s才会被处理;实例三中,请求放入队列跟实例二是一样的,但不同的是,队列中的请求同时具有了被处理的资格,所以实例三中的5个请求可以说是同时开始被处理的,花费时间自然变短了。

    但是请注意,虽然设置burst和nodelay能够降低突发请求的处理时间,但是长期来看并不会提高吞吐量的上限,长期吞吐量的上限是由rate决定的,因为nodelay只能保证burst的请求被立即处理,但Nginx会限制队列元素释放的速度,就像是限制了令牌桶中令牌产生的速度。看到这里你可能会问,加入了nodelay参数之后的限速算法,到底算是哪一个“桶”,是漏桶算法还是令牌桶算法?当然还算是漏桶算法。

    在令牌桶算法中,令牌桶算法的token为耗尽时会怎么做呢?由于它有一个请求队列,所以会把接下来的请求缓存下来,缓存多少受限于队列大小。但此时缓存这些请求还有意义吗?如果server已经过载,缓存队列越来越长,响应时间越来越长,即使过了很久请求被处理了,对用户来说也没什么价值。所以当token不够用时,最明智的做法就是直接拒绝用户的请求,这就成了漏桶算法。

    2.2.springcloud-gateway限流

    Spring Cloud Gateway是Spring官方基于Spring 5.0,Spring Boot 2.0和Project Reactor等技术开发的网关,Spring Cloud Gateway旨在为微服务架构提供一种简单而有效的统一的API路由管理方式。Spring Cloud Gateway作为Spring Cloud生态系统中的网关,目标是替代Netflix ZUUL,其不仅提供统一的路由方式,并且基于Filter链的方式提供了网关基本的功能,例如:安全,监控/埋点,和限流等。

    Spring Cloud Gateway 已经内置了一个基于令牌桶算法实现的限流器RequestRateLimiterGatewayFilterFactory,我们可以直接使用。RequestRateLimiterGatewayFilterFactory的实现依赖于 Redis,所以我们还要引入spring-boot-starter-data-redis-reactive。

    pom.xml

    <dependency>
        <groupId>org.springframework.cloud</groupId>
        <artifactId>spring-cloud-starter-gateway</artifactId>
    </dependency>
    
    <dependency>
        <groupId>org.springframework.boot</groupId>
        <artifatId>spring-boot-starter-data-redis-reactive</artifactId>
    </dependency>
    

    application.yml

    server:
      port: 8080
    spring:
      cloud:
        gateway:
          routes:
            - id: limit_route
              uri: http://www.baidu.com/
              predicates:
              - After=2019-02-26T00:00:00+08:00[Asia/Shanghai]
              filters:
              - name: RequestRateLimiter
                args:
                  key-resolver: '#{@hostAddrKeyResolver}'
                  redis-rate-limiter.replenishRate: 1
                  redis-rate-limiter.burstCapacity: 3
      application:
        name: gateway-limiter
      redis:
        host: localhost
        port: 6379
        database: 0
    

    在上面的配置文件,配置了 redis的信息,并配置了RequestRateLimiter的限流过滤器,该过滤器需要配置三个参数:

    • burstCapacity:令牌桶总容量。
    • replenishRate:令牌桶每秒填充平均速率。
    • key-resolver:用于限流的键的解析器的 Bean 对象的名字。它使用 SpEL 表达式根据#{@beanName}从 Spring 容器中获取 Bean 对象。

    实例一 IP限流

    获取请求用户ip作为限流key,KeyResolver是获取限流键的接口。

        @Bean
        public KeyResolver hostAddrKeyResolver() {
            return new IpKeyResolver();  
        }
    

    实例二 用户限流

    获取请求用户id作为限流key

    @Bean
    public KeyResolver userKeyResolver() {
        return exchange -> Mono.just(exchange.getRequest().getQueryParams().getFirst("userId"));
    }
    

    实例三 接口限流

    获取请求地址的uri作为限流key

    @Bean
    public KeyResolver apiKeyResolver() {
        return exchange -> Mono.just(exchange.getRequest().getPath().value());
    }
    
    展开全文
  • Java实现漏斗限流算法

    千次阅读 2018-09-28 17:38:09
    最近在学习老钱的《Redis深度历险:核心原理与应用实践》,其中讲到了漏斗限流,在Redis中可以使用 Redis-Cell 模块来做基于Redis的限流方案。在讲解原理的时候,老钱给出了 Python 和 Java 版的实现,看完之后发现...

    前言

    最近在学习老钱的《Redis深度历险:核心原理与应用实践》,其深入浅出的讲解,让我爱不释手。其中讲到了漏斗限流,在Redis中可以使用 Redis-Cell 模块来做基于Redis的限流方案。在讲解原理的时候,老钱给出了 Python 和 Java 版的实现,看完之后发现其设计非常精妙,于是自己也根据其原理自己动手敲了一下代码,把 Java 版本的漏斗实现出来了。

    实现代码

    import java.util.Map;
    import java.util.concurrent.ConcurrentHashMap;
    
    /**
     * 漏斗限流算法
     *
     * @author dadiyang
     * @date 2018/9/28
     */
    public class FunnelRateLimiter {
        private Map<String, Funnel> funnelMap = new ConcurrentHashMap<>();
        
        public static void main(String[] args) throws InterruptedException {
            FunnelRateLimiter limiter = new FunnelRateLimiter();
            int testAccessCount = 30;
            int capacity = 5;
            int allowQuota = 5;
            int perSecond = 30;
            int allowCount = 0;
            int denyCount = 0;
            for (int i = 0; i < testAccessCount; i++) {
                boolean isAllow = limiter.isActionAllowed("dadiyang", "doSomething", 5, 5, 30);
                if (isAllow) {
                    allowCount++;
                } else {
                    denyCount++;
                }
                System.out.println("访问权限:" + isAllow);
                Thread.sleep(1000);
            }
            System.out.println("报告:");
            System.out.println("漏斗容量:" + capacity);
            System.out.println("漏斗流动速率:" + allowQuota + "次/" + perSecond + "秒");
    
            System.out.println("测试次数=" + testAccessCount);
            System.out.println("允许次数=" + allowCount);
            System.out.println("拒绝次数=" + denyCount);
        }
    
        /**
         * 根据给定的漏斗参数检查是否允许访问
         *
         * @param username   用户名
         * @param action     操作
         * @param capacity   漏斗容量
         * @param allowQuota 每单个单位时间允许的流量
         * @param perSecond  单位时间(秒)
         * @return 是否允许访问
         */
        public boolean isActionAllowed(String username, String action, int capacity, int allowQuota, int perSecond) {
            String key = "funnel:" + action + ":" + username;
            if (!funnelMap.containsKey(key)) {
                funnelMap.put(key, new Funnel(capacity, allowQuota, perSecond));
            }
            Funnel funnel = funnelMap.get(key);
            return funnel.watering(1);
        }
    
        private static class Funnel {
            private int capacity;
            private float leakingRate;
            private int leftQuota;
            private long leakingTs;
    
            public Funnel(int capacity, int count, int perSecond) {
                this.capacity = capacity;
                // 因为计算使用毫秒为单位的
                perSecond *= 1000;
                this.leakingRate = (float) count / perSecond;
            }
    
            /**
             * 根据上次水流动的时间,腾出已流出的空间
             */
            private void makeSpace() {
                long now = System.currentTimeMillis();
                long time = now - leakingTs;
                int leaked = (int) (time * leakingRate);
                if (leaked < 1) {
                    return;
                }
                leftQuota += leaked;
                // 如果剩余大于容量,则剩余等于容量
                if (leftQuota > capacity) {
                    leftQuota = capacity;
                }
                leakingTs = now;
            }
    
            /**
             * 漏斗漏水
             *
             * @param quota 流量
             * @return 是否有足够的水可以流出(是否允许访问)
             */
            public boolean watering(int quota) {
                makeSpace();
                int left = leftQuota - quota;
                if (left >= 0) {
                    leftQuota = left;
                    return true;
                }
                return false;
            }
        }
    }
    
    
    展开全文
  • 限流算法的原理

    2020-08-24 19:42:47
    在一定时间间隔内,若计数器数字超限,则进行限流。 该算法的问题是,在两端临界点附加可能出现两倍的流速。 滑动窗口算法 基于计数器算法那,把时间间隔分片。例如服务限流每秒处理100个请求,把1秒分为10个窗口。...

    计数器算法

    在一定时间内,对处理的请求数进行计数,每次到达时间临界点则计数器清零。在一定时间间隔内,若计数器数字超限,则进行限流。
    在这里插入图片描述
    该算法的问题是,在两端临界点附加可能出现两倍的流速。

    滑动窗口算法

    基于计数器算法那,把时间间隔分片。例如服务限流每秒处理10000个请求,把1秒分为10个窗口。每100毫秒移动一次,内存中保留每次的请求次数。每次移动判断一下总次数是否超出10000限制。

    当滑动窗口的格子划分的越多,滑动窗口的滚动就越平滑,限流的统计就会越精确。
    在这里插入图片描述
    滑动窗口算法可以有效规避计数器算法中时间临界点问题。但实现起来相对比较复杂。

    Hystrix的限流基于滑动窗口算法实现。

    令牌桶算法

    系统已一个恒定的速率往桶放入令牌。若有请求需要处理,则从令牌桶里获取令牌,当桶里没有令牌,则拒绝服务。
    在这里插入图片描述
    令牌桶算法并不能实际的控制速率。比如,10秒往桶里放入10000个令牌桶,即10秒内只能处理10000个请求,那么qps就是1000。但这种模型可以出现1秒内把10000个令牌全部消费完,即qps为10000。所以令牌桶算法实际是限制的平均流速。具体控制的粒度以放令牌的间隔和每次的量来决定。若想要把流速控制的更加稳定,就要缩短间隔时间。

    Google Guava中的RateLimter就是利用的令牌桶原理。

    漏桶算法

    水滴先进入漏桶,漏桶以一定速度向外出水。当水流入速度过大,桶会直接溢出。

    即Request进入一个固定容量的Queue,若Queue满,则拒绝新的Request,可以阻塞,也可以抛异常。

    这种模型其实非常类似MQ的思想,利用漏桶削峰填谷,使得Queue的下游具有一个稳定流量。

    原文链接:https://www.cnblogs.com/shijiaqi1066/p/10508115.html

    展开全文
  • 上一章讲了常见的限流算法,本章我们来看看,Spring Cloud中的Hystrix组件在对请求进行熔断、限流与服务保护操作时的算法实践。 一、雪崩 分布式系统环境下,服务间依赖非常常见,一个业务调用通常依赖多个基础...
  • 基于内存(linkedlist为例)的限流 基于木桶算法限流 本次介绍,主要关注实现策略、控制粒度及时间窗口问题,示例代码中可能存在编码不规范的情况,请忽略 1. 基于数据库的统计进行限流  基于数据库的统计进行...
  • 工作中对外提供的API 接口设计都要考虑限流,如果不考虑限流,会成系统的连锁反应,轻者响应缓慢,重者系统宕机,整个业务线崩溃,如何应对这种情况呢,我们可以对请求进行引流或者直接拒绝等操作,保持系统的可用性...
  • 限流算法和Nginx配置限流

    千次阅读 2021-05-12 13:44:37
    1.限流算法: 1.计数器算法 计数器算法采用计数器实现限流有点简单粗暴,一般会限制一秒钟的能够通过的请求数,比如限流qps为100,算法的实现思路就是从第一个请求进来开始计时,在接下去的1s内,每来一个请求,就把...
  • 常用的限流算法有:滑动窗口、漏斗以及令牌桶。 滑动窗口算法rolling Window 以限制用户行为为例子,比如一秒内进行某个操作50次,这种行为应该进行限制。 滑动窗口就是记录一个滑动的时间窗口内的操作次数,操作...
  • 为什么需要限流? 由于互联网公司的流量巨大,系统上线会做一个流量峰值的评估,尤其是像各种秒杀促销活动,为了保证系统不被巨大的流量压垮,会在系统流量到达一定阈值时,拒绝掉一部分流量。 限流会导致用户在短...
  • 分布式常用限流算法

    千次阅读 2017-11-22 21:23:58
    1. 限流场景 在开发高并发系统时,有很多种方法可用来保护系统:缓存、降级、限流等。 缓存:提升系统访问速度,增大系统处理能力降级:服务出现问题或影响核心流程的性能时,需要暂时屏蔽,待高峰过去或问题...
  • 常用的限流算法有两种:漏桶算法和令牌桶算法。 漏桶算法思路很简单,水(请求)先进入到漏桶里,漏桶以一定的速度出水,当水流入速度过大会直接溢出,可以看出漏桶算法能强行限制数据的传输速率。 图1 漏桶...
  • 微服务拆分之后,系统之间的调用关系错综复杂,平台的整体复杂熵升高...服务治理本身的概念比较大,包括鉴权、限流、降级、熔断、监控告警等等,本文聚焦于限流,根据笔者的实战经验,分享一些对微服务接口限流的思考。
  • Eureka的限流算法类RateLimiter源码解读

    千次阅读 2017-07-06 11:36:04
    Eureka的限流算法类RateLimiter是基于令牌桶算法来实现的,下面看一看令牌桶算法的原理:对于很多应用场景来说,除了要求能够限制数据的平均传输速率外,还要求允许某种程度的突发传输。这时候漏桶算法可能就不合适...
  • 操作系统的内存管理算法

    千次阅读 2020-07-23 20:59:59
    关注、星标公众号,不错过精彩内容转自:LiteOS物联网操作系统本文主要介绍内存的基本概念以及操作系统的内存管理算法。一、内存的基本概念内存是计算机系统中除了处理器以外最重要的资源,用于...
  • 工作中对外提供的API 接口设计都要考虑限流,如果不考虑限流,会成系统的连锁反应,轻者响应缓慢,重者系统宕机,整个业务线崩溃,如何应对这种情况呢,我们可以对请求进行引流或者直接拒绝等操作,保持系统的可用性...
  • 高并发系统有三把利器:缓存、降级和限流; 限流的目的是通过对并发访问/请求进行限速来保护系统,一旦达到...最简单粗暴的限流算法就是计数器法了,而比较常用的有漏桶算法和令牌桶算法; 1.1计数器 计数器法是限流
  • 使用Pillow库处理图像文件 第三章 程序流程控制 几个例题 选择题:1、2、3 填空题:6 思考题:3~6 上机实践:2~14 案例研究:使用嵌套循环实现图像处理算法 第四章 常用内置数据类型 几个例题 选择题:11 填空题:4...
  • 相关历史文章(阅读本文之前,您可能需要先看下之前的系列????) 国内最全的SpringBoot系列之三 版本号命名的前世今生-值得收藏-第299篇 ...没有预热,不叫高并发「限流算法第三把法器:令牌桶算法...
  • 知识的广度来自知识的深度,学习如果不成体系那是多可怕的一件事儿,希望...令牌桶算法限流算法漏桶算法令牌桶算法RateLimiter 用法预消费能力令牌桶算法VS漏桶算法 工作中对外提供的API 接口设计都要考虑限流,如果.
  • Java知识体系最强总结(2021版)

    万次阅读 多人点赞 2019-12-18 10:09:56
    其他 Zookeeper 微服务与分布式 Spring Boot Spring Cloud 服务注册发现 服务配置 负载均衡 服务调用 服务限流 熔断降级 网关路由 服务权限 链路追踪 分布式事务 分布式缓存 分布式会话 日志收集 服务监控 消息驱动 ...
  • 微服务接口限流的设计、思考

    千次阅读 2018-11-29 10:13:59
    服务治理本身的概念比较大,包括鉴权、限流、降级、熔断、监控告警等等,本文聚焦于限流,根据笔者的实战经验,分享一些对微服务接口限流的思考。 本文试图讲清楚以下问题,如果您对限流也有类似的疑问或对某一话题...
  • 一、限流算法 1、固定窗口 固定窗口就是定义一个固定的统计周期,比如 1 分钟或者 30 秒、10 秒这样,然后在每个周期统计当前周期中接收到的请求数量,经过计数器累加后如果达到设定的阈值就触发流量干预。直到进入...
  • 高并发系统时有三把利器用来保护系统:缓存、降级和限流。缓存的目的是提升系统访问速度和增大系统能处理的容量,可谓是抗高并发流量的银弹;而降级是当服务出问题或者影响到核心流程的性能则需要暂时屏蔽掉,待高峰...
  • Spring Cloud限流详解 -- Zuul实现

    千次阅读 2018-11-26 11:13:40
    原文地址: Spring Cloud限流详解 在高并发的应用中,限流往往是一个绕不开的话题。...常见的限流算法有漏桶算法以及令牌桶算法。这个可参考 https://www.cnblogs.com/LBSer/p/4083131.html ,写得通...
  • Java基础知识面试题(2020最新版)

    万次阅读 多人点赞 2020-02-19 12:11:27
    import java和javax有什么区别 IO java 中 IO 分为几种? BIO,NIO,AIO 有什么区别? Files的常用方法都有哪些? 反射 什么是反射机制? 反射机制优缺点 反射机制的应用场景有哪些? Java获取反射的三种方法 网络...
  • 相关历史文章(阅读本文之前,您可能需要先看下之前的系列????) 「定制SpringBootAdminUI的页面」-第298篇 国内最全的SpringBoot系列之三 ...精度不够,滑动时间来凑「限流算法第二把法器:滑动时间窗口算法」-...
  • 本文提供粒子群算法简介和一个算法举例,提供粒子群算法仿真PID的M文件代码及simulink仿真。另外,本文还提供了一种动态simulink仿真方法,可以让M文件和simulink文件之间互相交换数据,实现仿真与程序的反馈,增加...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 120,764
精华内容 48,305
关键字:

内存限流算法