PfU28資訊網(wǎng)——每日最新資訊28at.com

本文繼續(xù)討論 Netty 相關(guān)的面試題，今天咱們來看一道 Netty 中的高頻面試題：說說 Netty 延遲任務(wù)的時(shí)間輪調(diào)度算法？PfU28資訊網(wǎng)——每日最新資訊28at.com

Netty 框架是以性能著稱的框架，因此在它的框架中使用了大量提升性能的機(jī)制，例如 Netty 用于實(shí)現(xiàn)延遲隊(duì)列的時(shí)間輪調(diào)度算法就是一個(gè)典型的例子。使用時(shí)間輪算法可以實(shí)現(xiàn)海量任務(wù)新增和取消任務(wù)的時(shí)間度為 O(1)，那么什么是時(shí)間輪調(diào)度算法呢？接下來我們一起來看。PfU28資訊網(wǎng)——每日最新資訊28at.com

1.延遲任務(wù)實(shí)現(xiàn)

在 Netty 中，我們需要使用 HashedWheelTimer 類來實(shí)現(xiàn)延遲任務(wù)，例如以下代碼：PfU28資訊網(wǎng)——每日最新資訊28at.com

public class DelayTaskExample {    public static void main(String[] args) {        System.out.println("程序啟動(dòng)時(shí)間：" + LocalDateTime.now());        NettyTask();    }    private static void NettyTask() {        // 創(chuàng)建延遲任務(wù)實(shí)例        HashedWheelTimer timer = new HashedWheelTimer(3, // 間隔時(shí)間                TimeUnit.SECONDS, // 間隔時(shí)間單位                100); // 時(shí)間輪中的槽數(shù)        // 創(chuàng)建任務(wù)        TimerTask task = new TimerTask() {            @Override            public void run(Timeout timeout) throws Exception {                System.out.println("執(zhí)行任務(wù)時(shí)間：" + LocalDateTime.now());            }        };        // 將任務(wù)添加到延遲隊(duì)列中        timer.newTimeout(task, 0, TimeUnit.SECONDS);    }}

以上程序的執(zhí)行結(jié)果如下：PfU28資訊網(wǎng)——每日最新資訊28at.com

程序啟動(dòng)時(shí)間：2024-06-04T10:16:23.033PfU28資訊網(wǎng)——每日最新資訊28at.com

執(zhí)行任務(wù)時(shí)間：2024-06-04T10:16:26.118PfU28資訊網(wǎng)——每日最新資訊28at.com

從上述執(zhí)行結(jié)果可以看出，我們使用 HashedWheelTimer 實(shí)現(xiàn)了延遲任務(wù)的執(zhí)行。PfU28資訊網(wǎng)——每日最新資訊28at.com

2.時(shí)間輪調(diào)度算法

那么問題來了，HashedWheelTimer 是如何實(shí)現(xiàn)延遲任務(wù)的？什么是時(shí)間輪調(diào)度算法？PfU28資訊網(wǎng)——每日最新資訊28at.com

查看 HashedWheelTimer 類的源碼會(huì)發(fā)現(xiàn)，其實(shí)它是底層是通過時(shí)間輪調(diào)度算法來實(shí)現(xiàn)的，以下是 HashedWheelTimer 核心實(shí)現(xiàn)源碼（HashedWheelTimer 的創(chuàng)建源碼）如下：PfU28資訊網(wǎng)——每日最新資訊28at.com

private static HashedWheelBucket[] createWheel(int ticksPerWheel) {    // 省略其他代碼    ticksPerWheel = normalizeTicksPerWheel(ticksPerWheel);    HashedWheelBucket[] wheel = new HashedWheelBucket[ticksPerWheel];    for (int i = 0; i < wheel.length; i ++) {        wheel[i] = new HashedWheelBucket();    }    return wheel;}private static int normalizeTicksPerWheel(int ticksPerWheel) {    int normalizedTicksPerWheel = 1;    while (normalizedTicksPerWheel < ticksPerWheel) {        normalizedTicksPerWheel <<= 1;    }    return normalizedTicksPerWheel;}private static final class HashedWheelBucket {    private HashedWheelTimeout head;    private HashedWheelTimeout tail;    // 省略其他代碼}

在 HashedWheelTimer  中，使用了 HashedWheelBucket 數(shù)組實(shí)現(xiàn)時(shí)間輪的概念，每個(gè) HashedWheelBucket 表示時(shí)間輪中一個(gè) slot（時(shí)間槽），HashedWheelBucket 內(nèi)部是一個(gè)雙向鏈表結(jié)構(gòu)，雙向鏈表的每個(gè)節(jié)點(diǎn)持有一個(gè) HashedWheelTimeout 對(duì)象，HashedWheelTimeout 代表一個(gè)定時(shí)任務(wù)，每個(gè) HashedWheelBucket 都包含雙向鏈表 head 和 tail 兩個(gè) HashedWheelTimeout 節(jié)點(diǎn)，這樣就可以實(shí)現(xiàn)不同方向進(jìn)行鏈表遍歷，如下圖所示：PfU28資訊網(wǎng)——每日最新資訊28at.com

PfU28資訊網(wǎng)——每日最新資訊28at.com

時(shí)間輪算法的設(shè)計(jì)思想就來源于鐘表，如上圖所示，時(shí)間輪可以理解為一種環(huán)形結(jié)構(gòu)，像鐘表一樣被分為多個(gè) slot 槽位。每個(gè) slot 代表一個(gè)時(shí)間段，每個(gè) slot 中可以存放多個(gè)任務(wù)，使用的是鏈表結(jié)構(gòu)保存該時(shí)間段到期的所有任務(wù)。時(shí)間輪通過一個(gè)時(shí)針隨著時(shí)間一個(gè)個(gè) slot 轉(zhuǎn)動(dòng)，并執(zhí)行 slot 中的所有到期任務(wù)。PfU28資訊網(wǎng)——每日最新資訊28at.com

任務(wù)的添加是根據(jù)任務(wù)的到期時(shí)間進(jìn)行取模，然后將任務(wù)分布到不同的 slot 中。如上圖所示，時(shí)間輪被劃分為 8 個(gè) slot，每個(gè) slot 代表 1s，當(dāng)前時(shí)針指向 2 時(shí)，假如現(xiàn)在需要調(diào)度一個(gè) 3s 后執(zhí)行的任務(wù)，應(yīng)該加入 2+3=5 的 slot 中；如果需要調(diào)度一個(gè) 12s 以后的任務(wù)，需要等待時(shí)針完整走完一圈 round 零 4 個(gè) slot，需要放入第 (2+12)%8=6 個(gè) slot。PfU28資訊網(wǎng)——每日最新資訊28at.com

那么當(dāng)時(shí)針走到第 6 個(gè) slot 時(shí)，怎么區(qū)分每個(gè)任務(wù)是否需要立即執(zhí)行，還是需要等待下一圈 round，甚至更久時(shí)間之后執(zhí)行呢？所以我們需要把 round 信息保存在任務(wù)中。例如圖中第 6 個(gè) slot 的鏈表中包含 3 個(gè)任務(wù)，第一個(gè)任務(wù) round=0，需要立即執(zhí)行；第二個(gè)任務(wù) round=1，需要等待 1*8=8s 后執(zhí)行；第三個(gè)任務(wù) round=2，需要等待 2×8=8s 后執(zhí)行。所以當(dāng)時(shí)針轉(zhuǎn)動(dòng)到對(duì)應(yīng) slot 時(shí)，只執(zhí)行 round=0 的任務(wù)，slot 中其余任務(wù)的 round 應(yīng)當(dāng)減 1，等待下一個(gè) round 之后執(zhí)行。PfU28資訊網(wǎng)——每日最新資訊28at.com

可以看出時(shí)間輪有點(diǎn)類似 HashMap，如果多個(gè)任務(wù)如果對(duì)應(yīng)同一個(gè) slot，處理沖突的方法采用的是拉鏈法。在任務(wù)數(shù)量比較多的場(chǎng)景下，適當(dāng)增加時(shí)間輪的 slot 數(shù)量，可以減少時(shí)針轉(zhuǎn)動(dòng)時(shí)遍歷的任務(wù)個(gè)數(shù)。PfU28資訊網(wǎng)——每日最新資訊28at.com

時(shí)間輪定時(shí)器最大的優(yōu)勢(shì)就是，任務(wù)的新增和取消都是 O(1) 時(shí)間復(fù)雜度，而且只需要一個(gè)線程就可以驅(qū)動(dòng)時(shí)間輪進(jìn)行工作。PfU28資訊網(wǎng)——每日最新資訊28at.com

本文鏈接：http://www.tebozhan.com/showinfo-26-92120-0.html面試官：說說延遲任務(wù)的時(shí)間輪調(diào)度算法？

聲明：本網(wǎng)頁內(nèi)容旨在傳播知識(shí)，若有侵權(quán)等問題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。郵件：2376512515@qq.com

上一篇： 利用Spring Boot和Elasticsearch進(jìn)行人臉數(shù)據(jù)的高效檢索

下一篇： 微服務(wù)下認(rèn)證授權(quán)框架的探討