文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

golang实现时间滑动窗口的示例代码

2024-04-02 19:55

关注

一 概念

固定窗口就像是滑动窗口的一个特例,固定窗口是大小固定且不能随着时间而变化的。

滑动时间窗口就是把一段时间片分为多个样本窗口,可以通过更细粒度对数据进行统计。然后计算对应的时间落在那个窗口上,来对数据统计;滑动时间窗口,随着时间流失,最开始的样本窗口将会失效,同时会生成新的样本窗口。

例如 我们将1s划分为4个样本窗口,每个样本窗口对应250ms。

二 go-zero中的滑动窗口实现

1.Bucket 样本窗口

Bucket用于记录每个样本窗口的值

// Bucket defines the bucket that holds sum and num of additions.
type Bucket struct {
	Sum   float64 //样本窗口的值
	Count int64   //样本窗口被add的次数
}
 
func (b *Bucket) add(v float64) {
	b.Sum += v
	b.Count++
}
 
//重置样本窗口,样本窗口过期时
func (b *Bucket) reset() {
	b.Sum = 0
	b.Count = 0
}

2. window 滑动窗口

 type window struct {
	buckets []*Bucket //样本窗口
	size    int //样本窗口个数
}
 
func newWindow(size int) *window {
	buckets := make([]*Bucket, size)
	for i := 0; i < size; i++ {
		buckets[i] = new(Bucket)
	}
	return &window{
		buckets: buckets,
		size:    size,
	}
}
func (w *window) add(offset int, v float64) {
	w.buckets[offset%w.size].add(v)
}
 
func (w *window) reduce(start, count int, fn func(b *Bucket)) {
	for i := 0; i < count; i++ {
		fn(w.buckets[(start+i)%w.size])
	}
}
 
func (w *window) resetBucket(offset int) {
	w.buckets[offset%w.size].reset()
}

3. RollingWindow窗口

bucket和window的实现都很简单,逻辑很好理解。

RollingWindow相对复杂一些。

当add值时需要如下操作:

 
type (
	// RollingWindowOption let callers customize the RollingWindow.
	RollingWindowOption func(rollingWindow *RollingWindow)
 
	// RollingWindow defines a rolling window to calculate the events in buckets with time interval.
	RollingWindow struct {
		lock          sync.RWMutex
		size          int
		win           *window
		interval      time.Duration
		offset        int
		ignoreCurrent bool
		lastTime      time.Duration // start time of the last bucket
	}
)
 
// NewRollingWindow returns a RollingWindow that with size buckets and time interval,
// use opts to customize the RollingWindow.
func NewRollingWindow(size int, interval time.Duration, opts ...RollingWindowOption) *RollingWindow {
	if size < 1 {
		panic("size must be greater than 0")
	}
 
	w := &RollingWindow{
		size:     size,
		win:      newWindow(size),
		interval: interval,
		lastTime: timex.Now(),
	}
	for _, opt := range opts {
		opt(w)
	}
	return w
}
 
// Add adds value to current bucket.
func (rw *RollingWindow) Add(v float64) {
	rw.lock.Lock()
	defer rw.lock.Unlock()
	rw.updateOffset()
	rw.win.add(rw.offset, v)
}
 
// Reduce runs fn on all buckets, ignore current bucket if ignoreCurrent was set.
func (rw *RollingWindow) Reduce(fn func(b *Bucket)) {
	rw.lock.RLock()
	defer rw.lock.RUnlock()
 
	var diff int
	//获取跨度,并计算还有几个bucket还在窗口期内
	span := rw.span()
	// ignore current bucket, because of partial data
	if span == 0 && rw.ignoreCurrent {
		diff = rw.size - 1
	} else {
		diff = rw.size - span
	}
	if diff > 0 {
		offset := (rw.offset + span + 1) % rw.size
		rw.win.reduce(offset, diff, fn)
	}
}
 
//距离上次add操作跨度,
//例如 lastTime = 1s, 当前时间1777ms。样本窗口时间250ms,那么跨度为3个样本窗口
func (rw *RollingWindow) span() int {
	offset := int(timex.Since(rw.lastTime) / rw.interval)
	if 0 <= offset && offset < rw.size {
		return offset
	}
 
	return rw.size
}
 
//g
func (rw *RollingWindow) updateOffset() {
	span := rw.span()
	if span <= 0 {
		return
	}
 
	offset := rw.offset
	// reset expired buckets ,重置已经超时的bucket
	for i := 0; i < span; i++ {
		rw.win.resetBucket((offset + i + 1) % rw.size)
	}
 
	rw.offset = (offset + span) % rw.size
	now := timex.Now()
	//和样本窗口时间对齐
	rw.lastTime = now - (now-rw.lastTime)%rw.interval
}

三 使用

//1.新建一个4样本窗口,每个样本窗口250ms
rollingWindow:= NewRollingWindow(4, time.Millisecond*250,IgnoreCurrentBucket())
 
//2.add 
rollingWindow.Add(1)
rollingWindow.Add(2)
time.Sleep(time.Millisecond*250)
 
rollingWindow.Add(3)
rollingWindow.Add(4)
 
 
//3.获取滑动窗口的值
 
var Sum float64
var total int64
rollingWindow.Reduce(func(b *collection.Bucket) {
		Sum += int64(b.Sum)
		total += b.Count
	})

到此这篇关于golang 实现时间滑动窗口的文章就介绍到这了,更多相关golang 时间滑动窗口内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯