ilogtail icon indicating copy to clipboard operation
ilogtail copied to clipboard

feat: processor rate limit

Open Abingcbc opened this issue 1 year ago • 0 comments

算法设计

限速插件基于令牌桶算法的设计:

  1. 在获取令牌桶时,会根据距离上次填充的时间长度,向令牌桶中补充相应数量的令牌。
  2. 如果无法获取到令牌(令牌桶中的数量小于等于0),那么该日志就会被丢弃掉。

数据结构

令牌桶

type tokenBucket struct {
	mu sync.Mutex

	limit   rate
	buckets sync.Map

	// GC thresholds and metrics
	gc struct {
		thresholds tokenBucketGCConfig
		metrics    struct {
			numCalls atomic.Int32
		}
	}
}
  1. mu:GC操作的并发锁
  2. limit:限速的速率
  3. buckets:map,存储了key到对应的令牌桶之间的关系。 key的计算方法为:
    1. 对field名进行排序
    2. 按照排序后的顺序,取出field的值,并拼接成一个字符串
    3. 计算该字符串的hash值(uint64)作为key,节约内存空间
  4. gc:GC配置参数
type bucket struct {
	tokens        float64
	lastReplenish time.Time
}
  1. tokens:该桶内剩余的令牌数量。由于距离上一次补充的时间间隔不一定是完整的秒,所以可能会补充非整数的令牌。
  2. lastReplenish:上次补充令牌的时间。

垃圾回收

令牌桶中一旦出现了key所对应的一条日志,那么无论其后续还是否出现,都会在内存中占用一个bucket。因此,引入了一个垃圾回收机制:

  1. 在处理了一定数量的日志后(默认10000条),触发垃圾回收
  2. 垃圾回收会重新补充每个桶的令牌
  3. 如果该桶的令牌大于等于了limit的令牌数,那么说明该桶所对应key,在一段时间内都没有出现
  4. 回收这些桶

Abingcbc avatar Jan 13 '24 07:01 Abingcbc