go-zero 應(yīng)對海量定時/延遲任務(wù)的技巧

timingWheel, err := NewTimingWheel(time.Second, slots, func(k, v interface{}) {
 key, ok := k.(string)
 if !ok {
 return
 }
 cache.Del(key)
})
if err != nil {
 return nil, err
}

cache.timingWheel = timingWheel

// 真正做初始化
func newTimingWheelWithClock(interval time.Duration, numSlots int, execute Execute, ticker timex.Ticker) (
	*TimingWheel, error) {
	tw := TimingWheel{
		interval:  interval,      // 單個時間格時間間隔
		ticker:  ticker,      // 定時器，做時間推動，以interval為單位推進(jìn)
		slots:   make([]*list.List, numSlots), // 時間輪
		timers:  NewSafeMap(),     // 存儲task{key, value}的map [執(zhí)行execute所需要的參數(shù)]
		tickedPos:  numSlots - 1,     // at previous virtual circle
		execute:  execute,      // 執(zhí)行函數(shù)
		numSlots:  numSlots,      // 初始化 slots num
		setChannel: make(chan timingEntry),  // 以下幾個channel是做task傳遞的
		moveChannel: make(chan baseEntry),
		removeChannel: make(chan interface{}),
		drainChannel: make(chan func(key, value interface{})),
		stopChannel: make(chan lang.PlaceholderType),
	}
	// 把 slot 中存儲的 list 全部準(zhǔn)備好
	tw.initSlots()
	// 開啟異步協(xié)程，使用 channel 來做task通信和傳遞
	go tw.run()

	return tw, nil
}

func (tw *TimingWheel) run() {
	for {
		select {
  // 定時器做時間推動 -> scanAndRunTasks()
		case -tw.ticker.Chan():
			tw.onTick()
  // add task 會往 setChannel 輸入task
		case task := -tw.setChannel:
			tw.setTask(task)
		...
		}
	}
}

func (c *Cache) Set(key string, value interface{}) {
	c.lock.Lock()
	_, ok := c.data[key]
	c.data[key] = value
	c.lruCache.add(key)
	c.lock.Unlock()

	expiry := c.unstableExpiry.AroundDuration(c.expire)
	if ok {
		c.timingWheel.MoveTimer(key, expiry)
	} else {
		c.timingWheel.SetTimer(key, value, expiry)
	}
}

func (tw *TimingWheel) moveTask(task baseEntry) {
	// timers: Map => 通過key獲取 [positionEntry「pos, task」]
	val, ok := tw.timers.Get(task.key)
	if !ok {
		return
	}

	timer := val.(*positionEntry)
 	// {delay  interval} => 延遲時間比一個時間格間隔還小，沒有更小的刻度，說明任務(wù)應(yīng)該立即執(zhí)行
	if task.delay  tw.interval {
		threading.GoSafe(func() {
			tw.execute(timer.item.key, timer.item.value)
		})
		return
	}
	// 如果 > interval，則通過 延遲時間delay 計算其出時間輪中的 new pos, circle
	pos, circle := tw.getPositionAndCircle(task.delay)
	if pos >= timer.pos {
		timer.item.circle = circle
    // 記錄前后的移動offset。為了后面過程重新入隊
		timer.item.diff = pos - timer.pos
	} else if circle > 0 {
		// 轉(zhuǎn)移到下一層，將 circle 轉(zhuǎn)換為 diff 一部分
		circle--
		timer.item.circle = circle
		// 因為是一個數(shù)組，要加上 numSlots [也就是相當(dāng)于要走到下一層]
		timer.item.diff = tw.numSlots + pos - timer.pos
	} else {
		// 如果 offset 提前了，此時 task 也還在第一層
		// 標(biāo)記刪除老的 task，并重新入隊，等待被執(zhí)行
		timer.item.removed = true
		newItem := timingEntry{
			baseEntry: task,
			value:  timer.item.value,
		}
		tw.slots[pos].PushBack(newItem)
		tw.setTimerPosition(pos, newItem)
	}
}

// 定時器 「每隔 internal 會執(zhí)行一次」
func (tw *TimingWheel) onTick() {
  // 每次執(zhí)行更新一下當(dāng)前執(zhí)行 tick 位置
	tw.tickedPos = (tw.tickedPos + 1) % tw.numSlots
  // 獲取此時 tick位置 中的存儲task的雙向鏈表
	l := tw.slots[tw.tickedPos]
	tw.scanAndRunTasks(l)
}

func (tw *TimingWheel) scanAndRunTasks(l *list.List) {
	// 存儲目前需要執(zhí)行的task{key, value} [execute所需要的參數(shù)，依次傳遞給execute執(zhí)行]
	var tasks []timingTask

	for e := l.Front(); e != nil; {
		task := e.Value.(*timingEntry)
    // 標(biāo)記刪除，在 scan 中做真正的刪除 「刪除map的data」
		if task.removed {
			next := e.Next()
			l.Remove(e)
			tw.timers.Del(task.key)
			e = next
			continue
		} else if task.circle > 0 {
			// 當(dāng)前執(zhí)行點已經(jīng)過期，但是同時不在第一層，所以當(dāng)前層即然已經(jīng)完成了，就會降到下一層
      // 但是并沒有修改 pos
			task.circle--
			e = e.Next()
			continue
		} else if task.diff > 0 {
			// 因為之前已經(jīng)標(biāo)注了diff，需要再進(jìn)入隊列
			next := e.Next()
			l.Remove(e)
			pos := (tw.tickedPos + task.diff) % tw.numSlots
			tw.slots[pos].PushBack(task)
			tw.setTimerPosition(pos, task)
			task.diff = 0
			e = next
			continue
		}
		// 以上的情況都是不能執(zhí)行的情況，能夠執(zhí)行的會被加入tasks中
		tasks = append(tasks, timingTask{
			key: task.key,
			value: task.value,
		})
		next := e.Next()
		l.Remove(e)
		tw.timers.Del(task.key)
		e = next
	}
	// for range tasks，然后把每個 task->execute 執(zhí)行即可
	tw.runTasks(tasks)
}

// interval: 4min, d: 60min, numSlots: 16, tickedPos = 15
// step = 15, pos = 14, circle = 0
func (tw *TimingWheel) getPositionAndCircle(d time.Duration) (pos int, circle int) {
	steps := int(d / tw.interval)
	pos = (tw.tickedPos + steps) % tw.numSlots
	circle = (steps - 1) / tw.numSlots
	return
}

steps = d / interval
pos = step % numSlots - 1
circle = (step - 1) / numSlots