去字節(jié)面試被面這題能答上來嗎?談?wù)勀銓r間輪的理解?
?1.什么是時間輪
時間輪,簡單理解就是一種=個用來存儲定時任務(wù)的環(huán)狀數(shù)組,它的工作原理和鐘表的表盤類似。
它由兩個部分組成, 一個是環(huán)狀數(shù)組,另一個是遍歷環(huán)狀數(shù)組的指針。
首先,要定義一個固定長度的環(huán)狀數(shù)組,然后數(shù)組的每一個元素代表一個時間刻度,假設(shè)每個刻度間隔是 1s,那么長度為 8 的數(shù)組,就代表 8 秒鐘。
然后,就是有一個指針,這個指針按照順時針無限地循環(huán)這個數(shù)組,每隔1個最小的時間單位就前進一個數(shù)組索引。
這個指針完整地轉(zhuǎn)1圈,就代表 8 秒鐘,轉(zhuǎn)兩圈表示 16 秒,假設(shè)從 0 點 0 分 0 秒開始,轉(zhuǎn)
一圈以后就到了 0 點 0 分 9 秒鐘。
2.工作原理
時間輪,環(huán)狀數(shù)組里面的每個元素,都是用來存儲定時任務(wù)的容器,當我們向時間輪里面添加一個定時任務(wù)的時候,我們會根據(jù)定時任務(wù)的執(zhí)行時間計算它所存儲的數(shù)組下標。當然,有可能在某個時間刻度上會存在多個定時任務(wù),這個時候會采用雙向鏈表的方式來存儲。
當指針指向某個數(shù)組的時候,就會把這個數(shù)組中存儲的任務(wù)取出來,然后遍歷這個鏈表逐個運行里面的任務(wù)。
那如果某個定時任務(wù)的執(zhí)行時間大于環(huán)形數(shù)組所表示的長度,一般可以使用一個圈數(shù)來表示該任務(wù)的延遲執(zhí)行時間。比如,1個第 16 秒要執(zhí)行的任務(wù),那意味著這個任務(wù)應(yīng)該是在第2圈的數(shù)組下標 為0 的位置執(zhí)行。
3.優(yōu)、缺點分析
使用時間輪的方式來管理多個定時任務(wù)的好處有很多,我認為有兩個比較重要的優(yōu)點:
(1)減少定時任務(wù)添加和刪除的時間復(fù)雜度,提升性能。
(2)可以保證每次執(zhí)行定時器任務(wù)都是 O(1)復(fù)雜度,在定時器任務(wù)密集的情況下,性能優(yōu)勢非常明顯。
當然,時間輪也有缺點,對于執(zhí)行時間非常嚴格的任務(wù),時間輪不是很適合,因為時間輪算法的精度取決于最小時間單元的粒度。假設(shè)以 1s 為一個時間刻度,那小于 1s 的任務(wù)就無法被時間輪調(diào)度。
時間輪算法在很多框架中都有用到,比如 Dubbo、Netty、Kafka 等。
時間輪算法也是一個比較經(jīng)典的設(shè)計。使用范圍比較廣,但是在實際應(yīng)用中,大部分同學(xué)接觸非常少。我認為這種設(shè)計思想或者這種數(shù)據(jù)結(jié)構(gòu),在我們實際應(yīng)用中的某些特定場景也是可以借鑒和使用的。比如定時重試、衰減重試等等。