再聊一道xue微簡單點兒的面試題
- 2020 年 4 月 7 日
- 筆記
大家好，我是我心永恆的老李。
今天下午的時候，我看到來自於大洋彼岸的短視頻：一些擦腚紙販子都在囤積居奇，高價兜售擦腚紙，看到這些消息真的是雛菊一緊。沙雕肺炎病毒全球肆虐的時候，難道不應該是買口罩保護上面的口么，怎麼搶着買擦腚紙招呼下邊那個眼了？算了，管不了那麼多了，我也囤點兒擦腚紙得了。
買擦腚紙這件小事兒，在這個物慾橫流而又窮人窮橫的年代，必須要貨比三家：「匋玉」和「並夕夕」橫向比了下還是「並夕夕」以絕對的優勢勝出了！看着「匋玉」上昂貴的擦腚紙價格，我心如刀絞，這公司啥時候墮落成這樣了？你看人家「並夕夕」，包郵到家還僅售一塊三…
大概三年多以前吧好像是，我曾經有緣去「匋玉」所屬的母公司「四十大盜」集團望京總部面試過，大概夭折在了第三輪：
主要不是我差勁，而是競爭對手們太厲害，還因為那條狗子
那天我白嫖了一輛鎖已經被暴力開拔的免費ofo到了「四十大盜」望京中心後，剛把ofo橫着放倒藏到草叢裡，就看到一條狗子瘋狂地沖我跑了過來，旁邊還有個驚慌失措的小姐姐。當時我心裏一橫就一個想法：這沙雕狗子竟然敢咬小姐姐，我必須得衝上去擋在前面狠狠地咬這條沙雕狗子。於是我「嗷」地一聲衝著狗子猛撲過去，把狗子嚇得猛一哆嗦，夾起來的尾巴這一明顯的特徵已然透露出這狗子已經被我征服了，就在這關鍵時刻，這姐們兒突然抱起那狗子慌裡慌張地跑了，中間還撇了我幾眼，從她的眼神中我可以讀取到信息：這tm哪兒來的神經病…
實際上人家問了我很多問題，但我今天就想說其中一個：
Redis中Key的過期刪除原理大概是怎樣的？
題外話：之所以能記起這個問題，完全是因為有個泥腿子說MongoDB支持定時刪除數據。
當時這問題可給我整懵了，我那會兒可沒怎麼深入研究過Redis，所以當時我就開啟了胡謅模式，而且一定程度上說我應該是胡謅對了一部分：先胡謅Redis對於過期Key處理的三種策略，再胡謅定時器，但是胡謅定時器的時候實際上心裏已經很虛了，和三種策略連貫性上串聯地並不好。
現在想想，這個問題真挺簡單的，當時只要我再狠狠地吃口屎冷靜一下，沒準能全部胡謅對了。回到正題上來，Redis到底是如何結合Key的過期策略實現對過期Key刪除的？
首先說下業界通用的關於過期Key處置的三種策略：
- 定時刪除：這種策略最狠的，假如你搞了個key叫做「lurenjia」，五分鐘後刪除，那麼五分鐘後這個key就一定會被及時地刪除掉。因為在這種策略下，當你給一個key搞了一個過期時間的同時，會創建一個定時器，這個定時器會在按時啟動，然後不幹別的，只干刪除。但是這種策略實在太TM狠了，如果你有10萬個帶過期時間的key，就要搞10萬個定時器，而Redis作為主業務流程為單進程單線程的典範，到底是忙着響應正規業務需求，還是忙着啟動這10萬個定時器刪除過期key呢？男人，請善待CPU。友情提示：Redis里沒有實現這種策略，如我說錯了糾正我。
- 惰性刪除：這種策略也是最狠的，只不過是狠在了另外一個極端。就算給一個路人甲key指定了過期時間，這個key到期也不會被刪除。你深愛着這個key以至於你每次獲取這個key的時候，都會計算一下這個key距離過期時間還有多長時間，終於到最後一次用這個key的時候你發現這個key過期了，你就再也不愛這個key了；如果很不幸你給一個key設定了過期時間後再也沒用過這個key，那這個key可能將永遠躺在內存里，那這也太TM狠了，提起褲子不認人？男人，請善待內存。
- 定期刪除：比較溫和折衷的策略。大概就是每隔一段固定的時間，就去掃描一波兒，按照算法刪除一些過期的key，這個刪除操作的執行時長也是有限制的。所以這個策略需要注意的就是兩點：執行間隔和執行時長，這個需要根據自己的業務場景在定了，總之，TA一定程度既解決了CPU被浪費的問題又解決內存被浪費的問題。
以上內容，我默認大家都應該是100%知道的。而且請務必注意：以上三種策略是通用策略，而不是Redis的三種策略。Redis里，實現了惰性刪除和定期刪除兩種策略。
這就完了？並沒有，我們需要聊下定時器！定時器一般說來是分兩種的：
- 一種是定時發生的事件，比如今天晚上9點執行打卡一次，但只執行這一次，執行過了就算OK了
- 另一種是周期性發生的事件，比如每隔30分鐘寫一次日報給你的老闆原上草同志
在Redis里應該大多數定時器都是周期性的（我沒怎麼太詳細讀過Redis源碼，按場景說的話，Redis里應該大量都是周期性定時器，至於定時發生的定時器我不確定是否一定有），那麼問題來了：
定時器是怎麼實現的呢？
- 利用IO復用的超時時間。《PHP網絡編程》里在講select系統調用時候，還記得有個timeout參數嗎？因為服務器會陷入到select循環中，每次都是阻塞在select調用處，你可以指定一個超時時間，表示過了這個超時時間依然沒有文件描述符變成「可讀」「可寫」那麼將重新開始下一次；同樣，epoll中可以在epoll_wait()中指定超時時間。這是一種解決方案。你可以通過PHP調用下select系統調用來試試看。
- Linux下有個叫做settimer()的系統調用（你就粗暴當函數理解就行了），你們可以去感受一下。settimer會在滿足時間的時候發出信號，所以你需要在相關進程/線程上安裝好信號處理。PHP是沒指望了，老老實實在Linux下用C去寫一寫試試吧。
- Linux下的timerfd，提供了了一系列timerfd_*函數來創建、銷毀定時器，比如timerfd_create()、timerfd_settime()。不過有意思的timerfd創建出來的定時器都是以文件描述符形式體現的，你可以很方便地監聽讀寫事件。雖然我這麼說，不過可能還有會有一部分小老弟感受不到這意味着啥。PHP依然沒戲，老老實實在Linux下用C去寫一寫試試吧。
- Libevent全家桶系列。嗯，這個之前在《PHP網絡編程》里我做過演示的，只要你安裝了event擴展，直接複製粘貼代碼就能飛起，這個PHP寫一寫沒問題的。但是Libevent底層可能也是通過epoll/select來實現的，我沒看過Libevent源碼實現，此處我主動保留意見。
好了上面就是就是一些常見的定時器實現的方法，講這個就是就是為了鋪墊Redis里過期key處理的實現，還是回到面試題本身來。不要妖魔化定時器，實際上TA就是個串串兒。
在Redis里，有一個叫做struct叫做redisDb，這個struct里有一個指針叫做expires的指針，這個指針指向了一個dict（你就粗暴理解為hashtable），然後這個dict（就是個hashtable）里存了所有的被設置了過期時間的key，TA大概是這樣樣子的：
// 僅僅為演示，具體redis里具體數據結構請參考redis源碼 struct redisDb { dict * expires; // 指向一個dict（就是hashtable，就k=>v） } // 就key=>value，key就是鍵值，value就是過期時間 dict hashtable { key1 => 1234567 // 過期時間的unix時間戳 key2 => 1234567 // 過期時間的unix時間戳 key3 => 1234567 // 過期時間的unix時間戳 . .. ... }
所以對於惰性刪除這種策略，本質上就是每當你從Redis里獲取一個key的時候，系統都會對比當前時間戳與key的過期時間戳，對比一下，這個邏輯我們在常規CURD業務里都經常用，Redis竟然與我們雷同，一定是Redis抄我們的。具體在Redis里，這個業務邏輯流程的函數叫做expireIfNeeded()，有興趣同學可以仔細關注下。
所以對於定期刪除這種策略，就是Redis本身的定期啟動掃描，但是每次都是掃描一定數量的key，等掃描一段時間後系統記錄下當前掃描位置然後強制結束，等下次再次掃描時候接着從上次終止的地方繼續掃描。具體體現在Redis里就是activeExpireCycle()函數，這個函數會定期啟動，每次挑選出一定數量的庫，然後從每個庫中挑選出一定數量的key，進行主動的刪除處理，而且每次都是在有限時間內，避免Redis響應主業務出現問題。
那麼我們接着嘮下「定時刪除」這種策略，敞開了嘮，放飛自我！如果在Redis里要實現「定時刪除」這種策略，方案上應該是要為「每個設置了過期時間的key同時創建一個定時器」，這種定時器會在到達的時候定時器啟動主動刪除掉key。而目前的Redis里，定時器事件大概是這樣的（請注意定時器與定時器事件的區別）：
// 僅僅為演示的偽結構 time_event { int id // 定時器的id，反正是一個數字 long expire_time // 何時執行... callback process // 到期執行時候要執行哪個函數，就是回調 }
然後所有的定時器事件以「鏈表」這種數據結構形式串在一起成了一個串串兒，新的定時器事件一定會被添加到「鏈表」的最前邊，成為最強插隊者。這個串串兒是無序的，這個無序是說expire_time是無序的，並不是說id無序。
假如說我們為每個設置了過期時間的key都要添加一個定時器事件，那麼這個「無序的鏈表」將會承載很多東西了。因為串串兒是「expire_time」無序的，所以一個key的過期時間到了後定時器會執行後需要遍歷整個串串兒找出滿足「expire_time」條件的時間事件，這個時間複雜度是O(N)。Redis是一個主流程業務為單進程單線程的服務器，這種定時器以及定時器事件毫無疑問將會要了TA的小命。
所以我們繼續放飛自我，還記得前面那張圖裡一個泥腿子說「Mongodb可以設置數據過期」這個事兒么？如果說下次你面試有面試官問你Mongodb這個大概是如何實現的，雖然你沒有接觸過Mongodb，但是你總是能根據目前已有的底層原理去大膽猜測一下吧？連推論都不敢推，你還敢對HR說你熱愛這家公司？其實這裡是個面試的小技巧，雖然面試官問的東西你沒有接觸過，但是你一定要嘗試根據已有的基礎知識去推測一下，面試是雙向的，面試官對你循循善誘，你也要引導對面試官。
面試官：你能說下Mongodb刪除過期數據的怎麼實現的嗎？
老李想像中的泥：雖然我沒接觸過，但是我想推測一下，你看我設計的合不合理。
真實的泥：…呃，那個，沒怎麼用過Mongodb…
然後我們接着放飛自我，你們一定遇到過這種業務場景：當Redis某個key過期後，能不能通知一下我？…寶貝兒們，深入思考下，如果要實現一個穩定靠譜的通知功能，你覺得以目前Redis的現狀，能實現么？友情提示：Redis有個關鍵字叫做keyspace，了解一下？
最後說明一下什麼叫「Redis是一個主流程業務為單進程單線程的服務器」，大家雖然都說Redis單進程單線程，這個意思是說Redis的主要邏輯是單進程單線程的，而不是所有流程。眾所周知（我假裝你知道）Redis在開啟了rdb備份後，每次從內存向硬盤dump rdb文件的時候，都是fork出一個子進程執行的dump任務。如果不fork子進程執行這個dump任務，那Redis在dump期間一定是停止響應客戶端請求的。所以說，你能說TA單進程單線程嗎？所以一般說某某軟件為單進程單線程，都是指其主業務流程為單進程單線程。
最後說明一下什麼叫「Redis是一個主流程業務為單進程單線程的服務器」，大家雖然都說Redis單進程單線程，這個意思是說Redis的主要邏輯是單進程單線程的，而不是所有流程。眾所周知（我假裝你知道）Redis在開啟了rdb備份後，每次從內存向硬盤dump rdb文件的時候，都是fork出一個子進程執行的dump任務。如果不fork子進程執行這個dump任務，那Redis在dump期間一定是停止響應客戶端請求的。所以說，你能說TA單進程單線程嗎？所以一般說某某軟件為單進程單線程，都是指其主業務流程為單進程單線程。
