計(jì)時(shí)器TimingWheel時(shí)間輪算法-創(chuàng)新互聯(lián)

文章目錄

1. 前言
2. 什么是時(shí)間輪算法？
- 2.1 單層時(shí)間輪
- 2.2 多層時(shí)間輪
- - 2.2.1 增加輪次的概念
  - 2.2.2 多層次時(shí)間輪
- 2.3 小結(jié)
3. 實(shí)現(xiàn)案例
- 3.1 Kafka中的時(shí)間輪
- - 3.1.1 任務(wù)的添加
  - 3.1.2 時(shí)間輪的推進(jìn)
  - - SystemTimer
  - 3.1.3 小結(jié)

創(chuàng)新互聯(lián)建站專業(yè)成都網(wǎng)站建設(shè)、成都網(wǎng)站設(shè)計(jì)，集網(wǎng)站策劃、網(wǎng)站設(shè)計(jì)、網(wǎng)站制作于一體，網(wǎng)站seo、網(wǎng)站優(yōu)化、網(wǎng)站營(yíng)銷、軟文發(fā)稿等專業(yè)人才根據(jù)搜索規(guī)律編程設(shè)計(jì)，讓網(wǎng)站在運(yùn)行后，在搜索中有好的表現(xiàn)，專業(yè)設(shè)計(jì)制作為您帶來效益的網(wǎng)站！讓網(wǎng)站建設(shè)為您創(chuàng)造效益。1. 前言

計(jì)時(shí)器對(duì)于故障恢復(fù)、基于速率的流量控制、調(diào)度算法、控制網(wǎng)絡(luò)中的數(shù)據(jù)包生命周期至關(guān)重要。

而一般計(jì)時(shí)器的實(shí)現(xiàn)維護(hù)成本比較高，比如JDK自帶的 Timer、DelayQueue對(duì)于任務(wù)的進(jìn)出其時(shí)間復(fù)雜度為O(logN)。

對(duì)于要求高性能且需要保證高頻繁大量操作任務(wù)的優(yōu)先級(jí)框架，比如Kafka、Netty等框架，重排序的時(shí)間復(fù)雜度O(logN)是不能滿足其要求的。而基于一種時(shí)間輪的算法可以實(shí)現(xiàn)將這種重排序的時(shí)間復(fù)雜度降為O(1)。

2. 什么是時(shí)間輪算法？

算法來自于生活，我們?nèi)粘？磿r(shí)間使用手表，一個(gè)表盤就可以無限的去循環(huán)每一天，通過同樣的一個(gè)表盤不同的指針來指向不同維度的時(shí)間(時(shí)分秒)，日常中如果我們由大量任務(wù)需要進(jìn)行提醒，可以進(jìn)行備忘與時(shí)鐘里的時(shí)間進(jìn)行指定按時(shí)提醒。

同樣的時(shí)間輪算法數(shù)據(jù)結(jié)構(gòu)其實(shí)抽象于手表時(shí)鐘，時(shí)間輪是用環(huán)形數(shù)組抽象表盤，數(shù)組里面的每一個(gè)元素就是一個(gè)bucket(刻度之間的間隔,也可以指代時(shí)間的精度)。bucket內(nèi)部用雙向鏈表存這待執(zhí)行的任務(wù)，此時(shí)添加和刪除的鏈表操作時(shí)間復(fù)雜度都是o(1)。

2.1 單層時(shí)間輪

在這里插入圖片描述

從圖中可以看到此時(shí)指針指向的是第一個(gè)bucket，一共有八個(gè)bucket0~7，假設(shè)bucket的時(shí)間單位為 1 秒，現(xiàn)在要加入一個(gè)延時(shí) 6秒的任務(wù)，計(jì)算方式就是 6 % 8 = 6，即放在下標(biāo)為6 的那個(gè)bucket中，具體的操作只要直接添加到bucket雙向鏈表的tail尾部就行了。

2.2 多層時(shí)間輪

比如當(dāng)我們加一個(gè)延遲9s后執(zhí)行的任務(wù)，此時(shí)超出表盤的范圍時(shí)，如何解決呢？同樣借鑒于表盤中循環(huán)以及多個(gè)指針代表不同時(shí)間維度的思想，時(shí)間輪算法有兩種解決方案。

2.2.1 增加輪次的概念

延遲9s任務(wù)存放的bucket 下標(biāo) = 9%8 = 1，輪數(shù)記為 9/8 = 1。
意思就是當(dāng)循環(huán)1輪后，指針指向下表為1的bucket就會(huì)觸發(fā)這個(gè)任務(wù)。Netty 中的 HashedWheelTimer 使用的就是這種方式。

2.2.2 多層次時(shí)間輪

在這里插入圖片描述
這種概念，就和我們手表里的時(shí)分秒不同指針代表不同維度時(shí)間概念一樣了，只不過這里是分層的設(shè)計(jì)。
實(shí)現(xiàn)的方式如同手表里的指針轉(zhuǎn)動(dòng)，當(dāng)秒針走一圈，分針走一格，分針走一圈，時(shí)針走一格。
這里三層的時(shí)間輪，一共是38=24格bucket, 最多可以延遲88*8=512秒。

多層時(shí)間輪，任務(wù)存放的位置還會(huì)隨著時(shí)間進(jìn)行降層變動(dòng)，比如一個(gè)延遲65秒的任務(wù)，剛才是放在第三層，時(shí)間過了1s后，此時(shí)只需要64s就會(huì)執(zhí)行，那么這個(gè)任務(wù)就會(huì)被降層到第二層，隨著時(shí)間的不斷的進(jìn)行，這個(gè)任務(wù)最終會(huì)降層到第一層等待執(zhí)行。

為什么要進(jìn)行降層操作呢？這是為了保證時(shí)間精度的一致性，Kakfa內(nèi)部用的就是多層次時(shí)間輪算法。

2.3 小結(jié)

時(shí)間輪是一種實(shí)現(xiàn)延遲功能（定時(shí)器）的高效調(diào)度模型算法。其設(shè)計(jì)思想類似于手表時(shí)鐘的設(shè)計(jì)，主要的數(shù)據(jù)結(jié)構(gòu)為數(shù)組+鏈表，多層時(shí)間輪有兩種實(shí)現(xiàn)方案，一種是輪次時(shí)間輪，一種是多層時(shí)間輪方案。

3. 實(shí)現(xiàn)案例 3.1 Kafka中的時(shí)間輪

Kafka的時(shí)間輪(TimingWheel)是一個(gè)存儲(chǔ)定時(shí)任務(wù)的環(huán)形隊(duì)列，底層采用數(shù)組實(shí)現(xiàn)，數(shù)組中的每個(gè)元素可以存放一個(gè)定時(shí)任務(wù)鏈表(TimerTaskList)，或者稱之為任務(wù)槽。TimerTaskList是一個(gè)環(huán)形的雙向鏈表，鏈表中的每一項(xiàng)表示的均是定時(shí)任務(wù)(TimerTaskEntry)，其中封裝了真正的定時(shí)任務(wù)(TimerTask)。

時(shí)間輪由多個(gè)時(shí)間格組成，每個(gè)時(shí)間格代表當(dāng)前時(shí)間輪的基本時(shí)間跨度(tickMs) 。時(shí)間輪的時(shí)間格個(gè)數(shù)是固定的，可用wheelSize來表示，那么整個(gè)時(shí)間輪的總體時(shí)間跨度(interval)可以通過公式tickMs × wheelSize計(jì)算得出。時(shí)間輪還有一個(gè)表盤指針(currentTime)，用來表示時(shí)間輪當(dāng)前所處的時(shí)間，currentTime是tickMs的整數(shù)倍。currentTime可以將整個(gè)時(shí)間輪劃分為到期部分和未到期部分，currentTime當(dāng)前指向的時(shí)間格也屬于到期部分，表示剛好到期，需要處理此時(shí)間格所對(duì)應(yīng)的TimerTaskList中的所有任務(wù)。

3.1.1 任務(wù)的添加

// TimerTaskEntry的就是包裝了任務(wù)，并且記錄任務(wù)的執(zhí)行時(shí)間 = 延時(shí)+當(dāng)前時(shí)間
def add(timerTaskEntry: TimerTaskEntry): Boolean = {val expiration = timerTaskEntry.expirationMs
	if (timerTaskEntry.cancelled) {  // Cancelled
	  false
	} else if (expiration< currentTime + tickMs) {// 如果到期
	  // Already expired
	  false
	} else if (expiration< currentTime + interval) {// 如果還在本層
	  // Put in its own bucket
	  val virtualId = expiration / tickMs
	  val bucket = buckets((virtualId % wheelSize.toLong).toInt) // 計(jì)算bucket
	  bucket.add(timerTaskEntry) // 添加到bucket中的雙向鏈表中

	  // Set the bucket expiration time
	  if (bucket.setExpiration(virtualId * tickMs)) {// 更新bucket過期時(shí)間
		// The bucket needs to be enqueued because it was an expired bucket
		// We only need to enqueue the bucket when its expiration time has changed, i.e. the wheel has advanced
		// and the previous buckets gets reused; further calls to set the expiration within the same wheel cycle
		// will pass in the same value and hence return false, thus the bucket with the same expiration will not
		// be enqueued multiple times.
		queue.offer(bucket) // 將bucket加入delayQueue
	  }
	  true
	} else {  // Out of the interval. Put it into the parent timer
	  if (overflowWheel == null) addOverflowWheel()
	  overflowWheel.add(timerTaskEntry)
	}
}

從上面的 add 方法我們知道每次對(duì)比都是根據(jù)expiration< currentTime + interval 來進(jìn)行對(duì)比的，那currentTime 如何進(jìn)行推進(jìn)的呢？

3.1.2 時(shí)間輪的推進(jìn)

Netty 中是通過固定的時(shí)間間隔掃描，時(shí)候未到就等待來進(jìn)行時(shí)間輪的推動(dòng)。
而 Kafka 就利用了空間換時(shí)間的思想，通過 DelayQueue，來保存每個(gè)槽，通過每個(gè)槽的過期時(shí)間排序。這樣擁有最早需要執(zhí)行任務(wù)的槽會(huì)有優(yōu)先獲取。如果時(shí)候未到，那么 delayQueue.poll 就會(huì)阻塞著，這樣就不會(huì)有空推進(jìn)的情況發(fā)送。

SystemTimer

我們先看下SystemTimer構(gòu)造器如下:

@threadsafe
class SystemTimer(executorName: String,
                  tickMs: Long = 1,
                  wheelSize: Int = 20,
                  startMs: Long = Time.SYSTEM.hiResClockMs) extends Timer {// timeout timer
  private[this] val taskExecutor = Executors.newFixedThreadPool(1,
    (runnable: Runnable) =>KafkaThread.nonDaemon("executor-" + executorName, runnable))

  private[this] val delayQueue = new DelayQueue[TimerTaskList]()
  private[this] val taskCounter = new AtomicInteger(0)
  private[this] val timingWheel = new TimingWheel(
    tickMs = tickMs,
    wheelSize = wheelSize,
    startMs = startMs,
    taskCounter = taskCounter,
    delayQueue
  )

其中SystemTimer.advanceClock即為推進(jìn)的方法

在這里插入圖片描述

3.1.3 小結(jié)

Kafka 用了多層次時(shí)間輪來實(shí)現(xiàn)，并且是按需創(chuàng)建時(shí)間輪，采用任務(wù)的絕對(duì)時(shí)間來判斷延期，并且對(duì)于每個(gè)bucket槽(槽內(nèi)存放的也是任務(wù)的雙向鏈表)都會(huì)維護(hù)一個(gè)過期時(shí)間，利用 DelayQueue 來對(duì)每個(gè)槽的過期時(shí)間排序，來進(jìn)行時(shí)間的推進(jìn)，防止空推進(jìn)的存在。
每次推進(jìn)都會(huì)更新 currentTime 為當(dāng)前時(shí)間戳，當(dāng)然做了點(diǎn)微調(diào)使得 currentTime 是 tickMs 的整數(shù)倍。并且每次推進(jìn)都會(huì)把能降級(jí)的任務(wù)重新插入降級(jí)。
可以看到這里的 DelayQueue 的元素是每個(gè)槽，而不是任務(wù)，因此數(shù)量就少很多了，這應(yīng)該是權(quán)衡了對(duì)于槽操作的延時(shí)隊(duì)列的時(shí)間復(fù)雜度與空推進(jìn)的影響。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

分享名稱：計(jì)時(shí)器TimingWheel時(shí)間輪算法-創(chuàng)新互聯(lián)
本文地址：http://muchs.cn/article0/ideio.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供標(biāo)簽優(yōu)化、全網(wǎng)營(yíng)銷推廣、網(wǎng)站建設(shè)、網(wǎng)站排名、網(wǎng)站收錄、做網(wǎng)站

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容