几种限流算法的Go语言实现("Go语言实现常见限流算法详解")

原创

ithorizon 4个月前 (10-20) 阅读数 17 #后端开发

Go语言实现常见限流算法详解

一、限流算法概述

限流算法是用于控制系统资源使用的一种技术，它可以防止系统在短时间内被过度使用，从而避免系统崩溃。常见的限流算法包括：令牌桶、漏桶、固定窗口计数器、滑动窗口计数器等。下面我们将详细介绍这些算法，并提供Go语言的实现。

二、令牌桶算法

令牌桶算法是一种常见的限流算法，它可以平滑地处理请求，允许突发请求。算法的核心思想是：在固定时间间隔内，向桶中添加固定数量的令牌，当请求到来时，需要从桶中获取一个令牌才能执行。如果桶中没有令牌，则请求会被阻塞或丢弃。

2.1 Go语言实现令牌桶算法


package main
import (
    "time"
    "fmt"
    "golang.org/x/time/rate"
)
func main() {
    // 创建一个令牌桶，每秒添加1个令牌，桶的容量为3
    limiter := rate.NewLimiter(1, 3)
    // 模拟请求
    for i := 0; i < 10; i++ {
        if err := limiter.Wait(context.Background()); err != nil {
            fmt.Println("请求被限流")
        } else {
            fmt.Println("请求被处理")
        }
        time.Sleep(time.Millisecond * 500)
    }
}

三、漏桶算法

漏桶算法是一种易懂的限流算法，它的核心思想是：所有请求都进入一个“漏桶”，桶中的请求按照固定速率流出。如果桶满了，新来的请求会被丢弃或阻塞。

3.1 Go语言实现漏桶算法


package main
import (
    "time"
    "fmt"
)
type LeakyBucket struct {
    capacity int
    rate     time.Duration
    queue    []time.Time
}
func NewLeakyBucket(capacity int, rate time.Duration) *LeakyBucket {
    return &LeakyBucket{
        capacity: capacity,
        rate:     rate,
        queue:    make([]time.Time, 0),
    }
}
func (lb *LeakyBucket) Allow() bool {
    now := time.Now()
    for len(lb.queue) > 0 && now.Sub(lb.queue[0]) >= lb.rate {
        lb.queue = lb.queue[1:]
    }
    if len(lb.queue) < lb.capacity {
        lb.queue = append(lb.queue, now)
        return true
    }
    return false
}
func main() {
    lb := NewLeakyBucket(3, time.Second)
    // 模拟请求
    for i := 0; i < 10; i++ {
        if lb.Allow() {
            fmt.Println("请求被处理")
        } else {
            fmt.Println("请求被限流")
        }
        time.Sleep(time.Millisecond * 500)
    }
}

四、固定窗口计数器算法

固定窗口计数器算法是一种易懂的限流算法，它将时间划分为固定长度的窗口，并在每个窗口内记录请求的次数。如果请求次数超过设定的阈值，则后续请求会被约束。

4.1 Go语言实现固定窗口计数器算法


package main
import (
    "sync"
    "time"
    "fmt"
)
type FixedWindowCounter struct {
    limit    int
    interval time.Duration
    counter  int
    lastTime time.Time
    mu       sync.Mutex
}
func NewFixedWindowCounter(limit int, interval time.Duration) *FixedWindowCounter {
    return &FixedWindowCounter{
        limit:    limit,
        interval: interval,
        counter:  0,
        lastTime: time.Now(),
    }
}
func (fwc *FixedWindowCounter) Allow() bool {
    fwc.mu.Lock()
    defer fwc.mu.Unlock()
    now := time.Now()
    if now.Sub(fwc.lastTime) >= fwc.interval {
        fwc.counter = 0
        fwc.lastTime = now
    }
    if fwc.counter < fwc.limit {
        fwc.counter++
        return true
    }
    return false
}
func main() {
    fwc := NewFixedWindowCounter(3, time.Second)
    // 模拟请求
    for i := 0; i < 10; i++ {
        if fwc.Allow() {
            fmt.Println("请求被处理")
        } else {
            fmt.Println("请求被限流")
        }
        time.Sleep(time.Millisecond * 500)
    }
}

五、滑动窗口计数器算法

滑动窗口计数器算法是对固定窗口计数器算法的改进，它将时间划分为多个窗口，并在每个窗口内记录请求的次数。当请求到来时，算法会计算当前窗口及其之前的窗口内的请求次数总和，如果超过设定的阈值，则约束后续请求。

5.1 Go语言实现滑动窗口计数器算法


package main
import (
    "container/ring"
    "sync"
    "time"
    "fmt"
)
type SlidingWindowCounter struct {
    limit    int
    interval time.Duration
    window   *ring.Ring
    mu       sync.Mutex
}
func NewSlidingWindowCounter(limit int, interval time.Duration, windowSize int) *SlidingWindowCounter {
    r := ring.New(windowSize)
    for i := 0; i < windowSize; i++ {
        r.Value = 0
        r = r.Next()
    }
    return &SlidingWindowCounter{
        limit:    limit,
        interval: interval,
        window:   r,
    }
}
func (swc *SlidingWindowCounter) Allow() bool {
    swc.mu.Lock()
    defer swc.mu.Unlock()
    now := time.Now()
    windowIndex := int(now.UnixNano() / int64(swc.interval))
    currentWindow := swc.window.Value.(int)
    // 更新当前窗口的计数
    swc.window.Value = currentWindow + 1
    // 移动窗口
    swc.window = swc.window.Next()
    // 计算窗口内的请求次数总和
    count := 0
    for i := 0; i < swc.window.Len(); i++ {
        count += swc.window.Value.(int)
        swc.window = swc.window.Next()
    }
    // 判断是否超过阈值
    if count <= swc.limit {
        return true
    }
    return false
}
func main() {
    swc := NewSlidingWindowCounter(3, time.Millisecond*500, 10)
    // 模拟请求
    for i := 0; i < 10; i++ {
        if swc.Allow() {
            fmt.Println("请求被处理")
        } else {
            fmt.Println("请求被限流")
        }
        time.Sleep(time.Millisecond * 200)
    }
}