來自：我一定會有貓的
鏈接：https://juejin.im/post/5b604b9ef265da0f62639001
1白对、緩存來由
隨著互聯(lián)網(wǎng)系統(tǒng)發(fā)展的逐步完善，提高系統(tǒng)的qps换怖，目前的絕大部分系統(tǒng)都增加了緩存機制從而避免請求過多的直接與數(shù)據(jù)庫操作從而造成系統(tǒng)瓶頸甩恼，極大的提升了用戶體驗和系統(tǒng)穩(wěn)定性。
2沉颂、緩存問題
雖然使用緩存給系統(tǒng)帶來了一定的質的提升条摸，但同時也帶來了一些需要注意的問題。
2.1 緩存穿透
緩存穿透是指查詢一個一定不存在的數(shù)據(jù)铸屉，因為緩存中也無該數(shù)據(jù)的信息钉蒲，則會直接去數(shù)據(jù)庫層進行查詢，從系統(tǒng)層面來看像是穿透了緩存層直接達到db彻坛，從而稱為緩存穿透顷啼，沒有了緩存層的保護，這種查詢一定不存在的數(shù)據(jù)對系統(tǒng)來說可能是一種危險昌屉，如果有人惡意用這種一定不存在的數(shù)據(jù)來頻繁請求系統(tǒng)钙蒙，不，準確的說是攻擊系統(tǒng)怠益，請求都會到達數(shù)據(jù)庫層導致db癱瘓從而引起系統(tǒng)故障仪搔。
2.2 解決方案
緩存穿透業(yè)內的解決方案已經(jīng)比較成熟，主要常用的有以下幾種：
bloom filter：類似于哈希表的一種算法蜻牢，用所有可能的查詢條件生成一個bitmap烤咧，在進行數(shù)據(jù)庫查詢之前會使用這個bitmap進行過濾偏陪，如果不在其中則直接過濾，從而減輕數(shù)據(jù)庫層面的壓力煮嫌。guava中有實現(xiàn)BloomFilter算法笛谦。
空值緩存：一種比較簡單的解決辦法，在第一次查詢完不存在的數(shù)據(jù)后昌阿，將該key與對應的空值也放入緩存中饥脑，只不過設定為較短的失效時間，例如幾分鐘懦冰，這樣則可以應對短時間的大量的該key攻擊灶轰，設置為較短的失效時間是因為該值可能業(yè)務無關，存在意義不大刷钢，且該次的查詢也未必是攻擊者發(fā)起笋颤，無過久存儲的必要，故可以早點失效内地。
2.3 緩存雪崩
在普通的緩存系統(tǒng)中一般例如redis伴澄、memcache等中，我們會給緩存設置一個失效時間阱缓，但是如果所有的緩存的失效時間相同非凌，那么在同一時間失效時，所有系統(tǒng)的請求都會發(fā)送到數(shù)據(jù)庫層荆针，db可能無法承受如此大的壓力導致系統(tǒng)崩潰敞嗡。
2.4 解決方案
線程互斥：只讓一個線程構建緩存，其他線程等待構建緩存的線程執(zhí)行完祭犯，重新從緩存獲取數(shù)據(jù)才可以秸妥，每個時刻只有一個線程在執(zhí)行請求，減輕了db的壓力沃粗，但缺點也很明顯，降低了系統(tǒng)的qps键畴。
交錯失效時間：這種方法時間比較簡單粗暴最盅，既然在同一時間失效會造成請求過多雪崩，那我們錯開不同的失效時間即可從一定長度上避免這種問題起惕，在緩存進行失效時間設置的時候涡贱，從某個適當?shù)闹涤蛑须S機一個時間作為失效時間即可。
2.5 緩存擊穿
緩存擊穿實際上是緩存雪崩的一個特例惹想，大家使用過微博的應該都知道问词，微博有一個熱門話題的功能，用戶對于熱門話題的搜索量往往在一些時刻會大大的高于其他話題嘀粱，這種我們成為系統(tǒng)的“熱點“激挪，由于系統(tǒng)中對這些熱點的數(shù)據(jù)緩存也存在失效時間辰狡，在熱點的緩存到達失效時間時，此時可能依然會有大量的請求到達系統(tǒng)垄分，沒有了緩存層的保護宛篇，這些請求同樣的會到達db從而可能引起故障。擊穿與雪崩的區(qū)別即在于擊穿是對于特定的熱點數(shù)據(jù)來說薄湿，而雪崩是全部數(shù)據(jù)叫倍。
2.6 解決方案
二級緩存：對于熱點數(shù)據(jù)進行二級緩存，并對于不同級別的緩存設定不同的失效時間豺瘤，則請求不會直接擊穿緩存層到達數(shù)據(jù)庫吆倦。
這里參考了阿里雙11萬億流量的緩存擊穿解決方案https://yq.aliyun.com/articles/290865，解決此問題的關鍵在于熱點訪問坐求。由于熱點可能隨著時間的變化而變化逼庞，針對固定的數(shù)據(jù)進行特殊緩存是不能起到治本作用的，結合LRU算法能夠較好的幫我們解決這個問題瞻赶。那么LRU是什么赛糟，下面粗略的介紹一下，有興趣的可以點擊上面的鏈接查看.
LRU（Least recently used砸逊，最近最少使用）算法根據(jù)數(shù)據(jù)的歷史訪問記錄來進行淘汰數(shù)據(jù)璧南，其核心思想是“如果數(shù)據(jù)最近被訪問過，那么將來被訪問的幾率也更高”师逸。最常見的實現(xiàn)是使用一個鏈表保存緩存數(shù)據(jù)司倚，如下圖所示
這個鏈表即是我們的緩存結構，緩存處理步驟為
首先將新數(shù)據(jù)放入鏈表的頭部
在進行數(shù)據(jù)插入的過程中篓像，如果檢測到鏈表中有數(shù)據(jù)被再次訪問也就是有請求再次訪問這些數(shù)據(jù)动知，那么就其插入的鏈表的頭部，因為它們相對其他數(shù)據(jù)來說可能是熱點數(shù)據(jù)员辩，具有保留時間更久的意義
最后當鏈表數(shù)據(jù)放滿時將底部的數(shù)據(jù)淘汰盒粮，也就是不常訪問的數(shù)據(jù)
-
LRU-K算法 ，其實上面的算法也是該算法的特例情況即LRU-1奠滑，上面的算法存在較多的不合理性丹皱，在實際的應用過程中采用該算法進行了改進，例如偶然的數(shù)據(jù)影響會造成命中率較低宋税，比如某個數(shù)據(jù)即將到達底部即將被淘汰摊崭，但由于一次的請求又放入了頭部，此后再無該數(shù)據(jù)的請求杰赛，那么該數(shù)據(jù)的繼續(xù)存在其實是不合理的呢簸，針對這類情況LRU-K算法擁有更好的解決措施。結構圖如下所示：**
image LRU-K需要多維護一個隊列或者更多，用于記錄所有緩存數(shù)據(jù)被訪問的歷史根时。只有當數(shù)據(jù)的訪問次數(shù)達到K次的時候瘦赫，才將數(shù)據(jù)放入緩存。當需要淘汰數(shù)據(jù)時啸箫，LRU-K會淘汰第K次訪問時間距當前時間最大的數(shù)據(jù)耸彪。
第一步添加數(shù)據(jù)照樣放入第一個隊列的頭部
如果數(shù)據(jù)在該隊列里訪問沒有達到K次（該數(shù)值根據(jù)具體系統(tǒng)qps來定）則會繼續(xù)到達鏈表底部直至淘汰；如果該數(shù)據(jù)在隊列中時訪問次數(shù)達到了K次忘苛，那么它會被加入到接下來的2級(具體需要幾級結構也同樣結合系統(tǒng)分析)鏈表中蝉娜，按照時間順序在2級鏈表中排列
接下來2級鏈表中的操作與上面算法相同，鏈表中的數(shù)據(jù)如果再次被訪問則移到頭部扎唾，鏈表滿時召川，底部數(shù)據(jù)淘汰
相比LRU，LRU-K需要多維護一個隊列胸遇，用于記錄所有緩存數(shù)據(jù)被訪問的歷史荧呐，所以需要更多的內存空間來用來構建緩存，但優(yōu)點也很明顯纸镊，較好的降低了數(shù)據(jù)的污染率提高了緩存的命中率倍阐，對于系統(tǒng)來說可以用一定的硬件成本來換取系統(tǒng)性能也不失為一種辦法。當然還有更為復雜的緩存結構算法逗威，點擊LRU算法即可學習峰搪，例如Two Queues和Mutil Queues等等，本文不過多贅述凯旭，只為讀者提供一種解決思路概耻。
