NO IMAGE

http://www.cnblogs.com/zhongwencool/p/timing_wheel.html

問題引入:遊戲裡面每個Player身上有很多buffs,在每一個tick(最小時間段)都要去檢查buff裡面的每一個buff是不是過期,產生的效果如何,造成在每個tick裡面都去遍歷一個長list,明顯很不好。

怎麼優化?

1.原始模型:

model1_thumb19

buff的狀態在每一個tick裡面都要更新!可以想象指標每移動一下,都會非常沉重地拖著所有的BuffList,好可怕……

2. 優化模型1:

我們要避免的是:原始模型在每一個tick裡面都要遍歷List,那麼我們試下以Times為key,在加入buff裡時分配好它的結束和啟作用的時間屬於哪一個Time,

model2_thumb14

這個模型要注意的問題:當要加的Buff起效果已超過了一輪Tick總數時! 比如時間輪總Tick數為12個,現在指標到了tick=2處,要加一個再經過tick為15(起效果)的buff,怎麼辦?

可以算得:2 15%12 = 5,把此buff放到tick=5的槽裡面(每個buff都會記錄下它的結束時間的),待tick從2跳一輪迴到2再跳3下到tick=5,這個buff就會執行。

這個模型完美解決原始模型(每個Tick都遍歷整個BuffList)的問題,似乎很完美哦,但是卻引入了新的問題,我們的最小tick明顯不可能以小時計算,如果我們把Tick劃分到秒級別, 一輪就有12*3600 = 43200個key,

假如有一個Buff在每3s就起一個效果:(每3秒加一次血),那麼這個buff就會被儲存43200/3 = 14400個!!!!如果有大量這種buff,資料冗餘就會非常大,儲存空間隨之也非常大……

要做到保證精度的同時,又保證效率,怎麼兩全呢?請看模型3.

3. 優化模型3

clock4_thumb14

網上下了個非常cool的時鐘圖做示例啦:

這就是要用分層時間輪模型:

複製程式碼
%%% 1.時鐘原理說明:
%%% 1.1. 初始化一個三層時間輪:秒刻盤:0~59個SecList, 分刻盤:0~59個MinList, 時刻盤:0~12個HourList;
%%% 1.2. SecTick由外界推動,每跳一輪(60格),SecTick復位至0,同時MinTick跳1格;
%%% 1.3. 同理MinTick每跳一輪(60格),MinTick復位至0,同時HourTick跳1格;
%%% 1.4. 最高層:HourTick跳一輪(12格),HourTick復位至0,一個時間輪完整週期完成.
%%% 2.事件原理說明:
%%% 2.1. 設定時間為TimeOut的事件時,根據TimeOut算出發生此事件時刻的指標位置{TriggerHour,TriggerMin,TriggerSec};
%%% 2.2. 用{TriggerHour,TriggerMin,TriggerSec}與當前指標{NowHour,NowMin,NowSec}對比得出事件存放在哪一個指標(Tick);
%%% 2.3. 所有層的指標每跳到下一格(Tick01)都會觸發格子的事件列表,處理每一個事件Event01:
%%% 2.3.1 根據事件Event01的剩餘TimeOut算出Event01應該存在上一層(跳得更快)層的位置Pos;
%%% 2.3.2 把事件更新到新的Pos(更新TimeOut);
%%% 2.3.3 重複處理完Tick01裡面所有的事件;
%%% 2.3.4 清空Tick01的事件;
%%% 2.3.5 最底層(跳最快)層所有的事件遇到指標Tick都會立即執行;
複製程式碼

我自己用Erlang實現了一個分層時間輪,有興趣也可以參觀下:)知易行難 歡迎大家用自己善長的語言造個漂亮的輪子,自己親手寫還是可以發現裡面很多有意思的細節啦.

https://gist.github.com/zhongwencool/eca6609b59ed635de164




譯文:Real-Time
Concepts for Embedded Systems
 Chapter 11 Timer and Timer Services

http://www.embeddedlinux.org.cn/RTConforEmbSys/5107final/LiB0071.html

上面buff的優化思路也是來源於此,非常簡單易懂的時間輪概念.

11.6 時間輪(time wheel)

如下圖Figure11.11所示:時間輪是一個固定大小的陣列結構,這個陣列的每一個槽(元素)代表著軟定時器的精度,(類似於時鐘的最小刻度).時間輪的優點:通過排序的時間列表來有效的更新timers.它能非常效率地安裝(instaallation),取消(cancellation)timer.(這2個操作的時間複雜度o(1)).

Figrue11.6_thumb5

Figure 11.11 timing wheel.

軟時間裝置(soft-timer facility)使用硬時間(hadware timer)來確定一個最小的刻度(tick).基於硬時間週期的timer,驅動著所有安裝在這上面的軟時間. 超時(timeout)的頻率決定著軟時間的精度,比如:如果定義tick精度為50ms,每個槽(slot)就代表50ms,這也是可以在這個timer裡面安裝的最小timeout事件了. 同時,一個雙向連結串列會把timeout的事件處理(event handlers)(也叫callback funciton or callbacks)儲存在每一個槽中,當timer
過期(expired)時會觸發callbacks呼叫。所以timers列表也代表著過期時間處理事件列表。每個時間槽描述如圖Figure11.12:

1112_thumb2

Figure 11.12: Timeout event handlers.

時鐘轉盤每過一個tick就會指向下一時間(next time),當指標指到陣列的最後一個槽時,下一時間又會回到指標最開始的槽。時間輪的概念就來自於此。因此:當安裝一個新的事件(time event)時,轉盤當前的位置決定了這個新事件到底應該放在哪一個槽,如下圖Figure11.13所描述,每經過一個槽代表過去50ms

1113_thumb3

Figure 11.13: Installing a timeout event.

這個時間槽標記了如果有人想安裝一個200ms的timeout事件,就可以把這個事件放在 200的槽中,當然這個轉盤的起始位置在槽的開始位置(圖中clock dial指的位置),換句話說:當轉盤(clock dial)指向最開始的槽時,這個事件處理就會返回應該是陣列的下標(index).

11.6.1 問題(Issues)

上面這個時間輪方法存在的系列的問題:

問題1: 槽的數量是有限的(也許不同的系統會有不同的限制),比如:你可以在Figure11.13非常明顯地看出來:最大的可處理長度(總槽度)是350ms,當要安裝一個400ms的事件時怎麼辦?這個會引起時間輪溢位,為了解決這個問題:一種方法就是禁止超過範圍的事件安裝,另一個更好的方法:把這些溢位的事件放在一個統一的事件緩衝(event
buffer)裡面,等轉盤轉到下一刻度時就從buffer中取出符合範圍的事件,這樣這些事件也可以被處理了,你可仔細研究Figure11.14得到答案:

1114_thumb1

Figure 11.14: Timing wheel overflow event buffer.

比如:當轉盤位置在0刻度(圖中位置1)處時,同時要安裝一個400ms的timeout,這個事件必須暫時存在溢位緩衝buffer裡面,隨著轉盤轉到 50ms(圖中位置2處),就會從緩衝區取出這個事件安裝. 同理:500ms的事件也只能是在轉盤到 150ms(圖中位置3)處才能安裝。轉盤每指向下一刻時,都會檢查這個事件緩衝區,這就要求緩衝區裡面的事件列表是正增長,如果這個列表很長,那麼新的事件插入時代價會非常大。

問題2:這個時間輪的精度,試想一下:當tick指到time wheel 到開始指向下一個時間刻度前,如又安裝一個150ms的事件,那麼這個事件是安裝在 150ms,還是在 200呢?按平均來講,出錯的概率均等的情況下,那麼這個出錯可能會延遲或提前最小刻度的一半,在這裡就是50ms/2=25ms.

問題3:非常重要的問題:關於callbacks的安裝.理論上,每一個Callback都應該在時間過期時同時發生,但是在現實中,這是不可能的,每一個Callback的工作狀態都不可預測,因此,執行的每一個callback的長度也不可預測,導致沒有方法可以保證一個在很長列表後面的callback會被馬上執行,這個問題是不合需求的,不能引放到系統裡面。Figure11.15描述了這個問題:

1115_thumb4

Figure 11.15: Unbounded soft-timer handler invocation.

當t1 timeout剛過期時,事件處理函式1馬上發生,類似,事件處理函式n會在到過t(n-1)時被觸發,由於每一個處理函式的執行長度是不確定的,所有圖中x,y是長度也是不定的。

理論上(Ideally),這個時間處理會規定一個處理事件的上限值;比如:當執行到事件處理函式n時距離事件處理函式1開始已超過200ms時,會把沒有執行的其它事件忽略掉。這個問題很難,解決方法也是應用程式自己特定的[譯註:可以點這裡參見Linux下的實現]。

11.6.2 分層時間輪(Hierarchical Timing Wheels)

Figure11.14裡面的問題1:溢位問題可以使用分層時間輪的方法解決。

軟時間裝置需要適應事件在跨越在不同範圍的值,這個跨度可以非常大,比如:適應timers 範疇從100ms到5 分鐘需要3000((5 × 60 × 10)跨度的時間輪,因為這個時間輪的精度最少要100ms,這也是此時間輪的最小精度啦:

 10 × 100ms = 1 sec
10 entries/sec
60 sec = 1 minute
60 × 10 entries / min 
因此: 
5 × 60 × 10 =需要3000個刻度(entries).

一個分層的時間輪就好像一個數字刻盤指標型時鐘,用多個時間輪安裝在這個分層結構裡面,取代上面單一的時間輪。這裡面每個時間輪都有自己的粒度(granularity)精度,時間轉盤與所有的時間輪聯絡在一起,當最低層的時間輪轉一輪時,上一層的時間輪就轉一個單位。使用分層時間輪剛上面的需要3000entries的現在僅需要75(10 60 5)entries就可以保證timeout從100ms到5分鐘。這裡用到的多維陣列:

 

複製程式碼
 10 × 100ms = 1 sec
10 entries/sec
60 sec = 1 minute
60 entries / min
5 entries for 5 minutes
因此:
5   60   10 =只需要75個刻度(entries)
複製程式碼

1116_thumb4

Figure 11.16: A hierarchical timing wheel

這個模型不僅節省了大量的空間,並且保持著很高的精度和跨度,Figure11.16說明了這一點。
舉個例子:它可能會安裝一個2分4秒300ms處timeout事件。首先安裝2min,當2分鐘發生時,它檢查還有4.3s的事件才能timeout,所以它又安裝了4s的timeout事件槽,當4s過去後,檢查到還有300ms才能timeout,又安裝了一個300ms事件,再過300ms,真正的timeout才會被執行.

如果你覺得上面意猶未盡:這裡面還有一個大餐哦:

1.關於Linux 下定時器的實現方式分析 http://www.ibm.com/developerworks/cn/linux/l-cn-timers/

2. 淺析 Linux 中的時間程式設計和實現原理 http://www.ibm.com/developerworks/cn/linux/1308_liuming_linuxtime3/


時間輪是不是很神奇:上面譯文有說到:分層模型Figure11.16節省了大量的空間?能說說是怎麼做到的麼,想想,事件假如說有1000個事件,這些事件的空間怎麼也不可以被減少,那麼它指的是什麼空間呢?

如果你知道,請不要吝嗇 :)

寫下來是好習慣:http://www.cnblogs.com/zhongwencool/