---
# System prepended metadata

title: 快取應用的三大問題
tags: [Redis]

---

# 快取應用的三大問題

###### tags: `Redis`
[TOC]

## 快取雪崩 (Cache Avalanche)
### 問題描述
通常發生在 cache 重啟當機或某個時刻大量的快取同時過期，或是單純redis服務掛了，此時又有大量的請求要資料，這樣大量的需求就會直接打在資料庫上，資料庫可能因此被打掛，即使DBA當下重啟資料庫，也會很快被新一波的流量打掛，從而形成一連串的連鎖反應，最終導致整個系統崩潰。
### 常見解法
* 資料庫服務為避免單點問題(single-point-of-failure)，通常會有主從(master-slave)機制來避免，redis透過cluster sentinel不斷監控master，sentinel採用cluster的原因也是避免sentinel的單點問題。
* Expiry with different TTL(Time To Live)：對於各個Cache的過期時間進行完善的規劃，也就是不要讓Cache在同個時間點過期，至於多久要過期，就取決於該資料實際上需要的更新頻率，或是設定成永不過期。
* 互斥鎖 Mutex (Locking)：在cache做一個lock的動作，也就是當多個請求併發時，只有一個請求可以跟DB做互動，取完資料後再把結果放到cache中，讓其他請求對cache取資料，如此一來，就不會有很多請求直入DB的問題發生了。
* 服務限流或降級 : 無論是快取層還是儲存層都會有出錯的機率,可以將它們視為資源。作為一個並發量較大的分散式系統，假如有一個資源不可用，可能會造成所有執行緒在取得這個資源時異常，造成整個系統不可用。
### GITHUB上較為詳細的敘述
對於系統 A，假設每天高峰期每秒 5000 個請求，本來快取在高峰期可以扛住每秒 4000 個請求，但是快取機器意外發生了全盤宕機。快取掛了，此時 1 秒 5000 個請求全部落資料庫，資料庫必然扛不住，它會報一下警，然後就掛了。此時，如果沒有採用什麼特別的方案來處理這個故障，DBA 很著急，重啟資料庫，但是資料庫立刻又被新的流量打死了

![image](https://hackmd.io/_uploads/S1qhDzLE0.png)

快取雪崩的事前事中事後的解決方案如下： 
事前：Redis 高可用，主從+哨兵，Redis cluster，避免全盤崩潰。 
事中：本地 ehcache 快取 + hystrix 限流&降級，避免 MySQL 被打死。 
事後：Redis 持久化，一旦重啟，自動從磁碟上載入數據，快速恢復快取資料。

![image](https://hackmd.io/_uploads/SkMgdzIER.png)

使用者發送一個請求，系統 A 收到請求後，先查本地 ehcache 緩存，如果沒查到再查 Redis。如果 ehcache 和 Redis 都沒有，再查資料庫，將資料庫中的結果，寫入 ehcache 和 Redis 中。

限流組件，可以設定每秒的請求，有多少能通過組件，剩餘的未通過的請求，怎麼辦？走降級！可以傳回一些預設的值，或是友情提示，或是空值。

好處：

* 資料庫絕對不會死，限流組件確保了每秒只有多少個請求能通過。
* 只要資料庫不死，就是說，對使用者來說，2/5 的請求都是可以處理的。
* 只要有 2/5 的請求可以被處理，就代表你的系統沒死，對使用者來說，可能就是點擊幾次刷不出來頁面，但是多點幾次，就可以刷出來了。

### 我的理解
增加response time來拯救整體系統，這個作法在事情發生的當下貌似是較為合理的一個。
限流的作法像是互斥鎖的延伸，上述所說的ehcache則是本地佈署的快取策略，所以拿到資料會出現的最糟狀況是ehcache->Redis->DB，這種做法可能會造成性能延遲，但對於解決快取雪崩是不錯的解決方案，並且加上了限流元件，這將使得請求到DB的請求數量會得到一定的緩解，

在系統正常運行的狀況下，我覺得混合式的解決方案可能較為妥當，但過多的話會造成反效果。如果有意外的高併發請求進入服務，這時使用互斥鎖的話可能會塞住整個serivce，這時可能需要考慮到流量應付的問題。

所以在系統(分散式Redis佈署)正常運行時，需針對某些熱點資料進行快取，並把資料過期時間設為不過期或是評估進行資料更新的時間(某個時間點)，然後透過限流服務來保障快取死掉後DB絕對不會被打爆。

最終就是犧牲掉系統部分可用性來換取穩定。

#### 一般的快取架構
![image](https://hackmd.io/_uploads/SJUVc6UN0.png)

以上圖而言，在一般場景中就足以應付日常業務，若快取過期或快取當機(死機)就有可能出現快取雪崩問題，因為快取不可用，所以所有的request所需資料都會打進DB，造成DB壓力過大死掉。

這時會衍生出兩種因為快取而產生雪崩效應
* 大量cache同時過期
![image](https://hackmd.io/_uploads/BJBPaaL40.png)

**常見的應對方式有三種 :**
1. **分散設定快取過期時間**
    若要給快取資料設定過期時間，則須避免將大量資料設定成同一個過期時間。
    多數作法建議對過期時間加上一個隨機數，如此一來將能保證這些資料不會同時過期，若有的話也是少數資料。
3. **互斥鎖**
    當request進入系統時，若發現資料未出現於cache中就使用互斥鎖，保證同一時間僅會有一個請求建構cache資料(這邊指的是快取無資料，從DB撈資料出來放到快取裏頭)，當cache資料建構完成後再釋放鎖，如此一來就不會出現一坨request全部塞進DB的問題了，而其他沒拿到鎖的請求則進行等待鎖的釋放，此時需要做一些簡單的響應讓使用者等待。
    PS. 實現互斥鎖時，須設定Time out，否則某個請求拿到鎖後這個請求發生阻塞問題出現鎖無法釋放，導致整個系統都無法響應
5. **後臺更新快取**
    不透過request去更新cache資料，也不設定過期時間，而是讓cache資料永久有效不會過期，並將更新工作交給後臺程式(排程之類)去做。
    上述說的cache不過期並不是讓資料一直放在快取裏頭，因為當快取容量快不夠時有些快取資料會被淘汰。被淘汰的資料到下一次被更新的這段時間裡，request來請求快取時可能會得到空值(被認為資料遺失)，此時有兩種方式可以解決這問題。
    1. 後臺需要頻繁檢查快取是否還有效或存在，若檢查到該問題則需要馬上從資料庫讀資料然後更新到快取裏頭。這種方式的檢查時間不能太長，太長會導致使用者獲取的資料是空值而不是真正的資料，所以檢查的間隔最好是毫秒級別，但一定會有個間隔時間，用戶體驗一般。
    2. 透過message queue傳送訊息通知後臺更新快取，後臺收到訊息後，判斷快取是否存在，存在就不執行更新快取操作；不存在就讀取資料庫資料，並將資料載入到快取.這種方式相比第一種方式快取的更新會更及時，使用者體驗也比較好。
    
* cache故障
![image](https://hackmd.io/_uploads/SJBdTTLE0.png)

**常見的應對方式有兩種 :**
1. 服務熔斷或請求限流機制
    啟動服務熔斷機制，暫停request或業務邏輯對快取服務的訪問，直接返回錯誤，不用再繼續訪問資料庫，從而降低對資料庫的存取壓力，確保資料庫系統的正常運行，然後等到快取恢復正常後，再允許應用程式存取快取服務。
    服務熔斷機制是保護資料庫的措施，但暫停了應用程式存取快取，全部業務都無法正常運作，為了減少對業務的影響，可以啟用請求限流機制，只將少部分請求發送到資料庫進行處理，其他請求就在訪問入口直接拒絕，等到快取恢復正常並把快取預熱完後，再解除請求限流的機制。
3. 建構快取高可靠集群
    服務熔斷或請求限流機制是快取雪崩發生後的應對方案，最好透過主從節點的方式建構快取高可靠叢集。如果快取的主節點故障當機，從節點可以切換成為主節點，繼續提供快取服務，避免了由於快取故障當機而導致的快取雪崩問題。

### 我會怎麼做
若未防範此問題的話，可能會造成整體系統出現死亡螺旋，快取與DB起不來，流量又瘋狂打進來，最終導致整體系統掛點，只能重啟整體系統。
為了因應這問題，我會使用上述三種解決辦法的組合。
* 首先針對快取時間進行規劃，這邊有兩個選擇，快取設定為永不過期or隨機的過期時間，永不過期的機制把快取更新的工作交給後臺程式，如此一來使用者可良好的訪問應用程式，且後臺可在離峰時間進行快取更新，但需要做到即時性的快取監控;若實作隨機過期時間，可能會出現極少數快取同時過期的狀況，低機率發生雪崩效應，所以最好搭配互斥鎖來減少意外發生。
* 佈署服務限流或溶斷機制，當快取不幸故障時，流量不會全部塞進DB，而是僅有部分流量能訪問DB，讓DB能在合理的流量處理範圍運作；甚至中斷流量進入，等待快取恢復時再重新接受流量
* 呼應上點，佈署主從式快取集群，當master故障時slave可以即時補上，繼續提供快取服務。
* 綜上想法，可良好的降低應用程式遭受雪崩效應的問題

![image](https://hackmd.io/_uploads/SJFX0Pu40.png)
![image](https://hackmd.io/_uploads/H1QTRwdNC.png)

### 相關文獻與參考資料
1. https://medium.com/@martin87713/design-pattern-cache-problem-7b721baf6301
1. https://www.php.cn/zh-tw/faq/554384.html
1. https://kkc.github.io/2020/03/27/cache-note/
1. https://github.com/doocs/advanced-java/blob/main/docs/high-concurrency/redis-caching-avalanche-and-caching-penetration.md
2. https://xiaolincoding.com/redis/cluster/cache_problem.html#%E7%BC%93%E5%AD%98%E9%9B%AA%E5%B4%A9


## 快取穿透 (Cache Penetration)
### 問題描述
請求的資料從頭到尾都不存在快取跟資料庫中。因此請求穿過快取直接打在資料庫上，但資料庫也找不到對應的資料可以返回並存入快取，導致所有類似的請求不斷地打在資料庫上，當流量一大，又會再次造成資料庫崩潰。
可能發生穿透的原因有兩種：業務上的失誤、駭客惡意攻擊。因此可以透過程式面去判斷請求參數是否合業務邏輯、有無非法字串等等，判斷為惡意則避免請求訪問緩存與資料庫

### 常見解法
* 布隆過濾器（Bloom Filter）：使用布隆過濾器可以在快取層級過濾掉一些無效的請求，從而避免無效請求直接存取資料庫。
    布隆過濾器是一種高效率的資料結構，可以快速判斷某個元素是否存在於一個集合中。透過在快取層面使用布隆過濾器，可以在查詢前快速判斷資料是否存在，如果不存在可以直接傳回結果，避免對資料庫的查詢操作。
* 快取空值處理：當查詢的資料在資料庫中確實不存在時，可以將空值也快取起來，設定一個較短的過期時間。這樣，下次查詢相同的資料時，就可以從快取中取得到空值，避免再次存取資料庫。
* Server 端快取限制： 在伺服器端限制可以訪問的資料範圍，確保無效的請求無法查詢快取和資料庫。

### GITHUB上較為詳細的敘述
![image](https://hackmd.io/_uploads/B1R2iCI4R.png)
對於系統 A，假設一秒 5000 個請求，結果其中 4000 個請求是駭客發出的惡意攻擊。
駭客發出的 4000 個攻擊，快取中查不到，每次去資料庫裡查，也查不到。
舉例。資料庫 id 是從 1 開始的，結果駭客發過來的請求 id 全部都是負數。這樣的話，快取中不會有，請求每次都“視快取於無物”，直接查詢資料庫。這種惡意攻擊場景的快取穿透就會直接把資料庫打死。

![image](https://hackmd.io/_uploads/Hyjf3A840.png)

解決方式很簡單，每次系統 A 從資料庫只要沒查到，就寫一個空值到快取裡去，例如 set -999 UNKNOWN 。然後設定一個過期時間，這樣的話，下次有相同的 key 來存取的時候，在快取失效之前，都可以直接從快取中取資料。

如果駭客如果每次使用不同的負數 id 來攻擊，寫空值的方法可能就不奏效了。更經常的做法是在快取之前增加布隆過濾器，將資料庫中所有可能的資料雜湊映射到布隆過濾器中。然後對每個請求進行如下判斷：

請求資料的 key 不存在於布隆過濾器中，可以確定資料就一定不會存在於資料庫中，系統可以立即傳回不存在。
請求資料的 key 存在於布隆過濾器中，則繼續再向快取中查詢。
使用布隆過濾器能夠對存取的請求起到了一定的初篩作用，避免了因資料不存在而引起的查詢壓力。

### 布隆過濾器 (Bloom Filter)
Bloom Filter 有兩個要素：長度為 n 的 bit array 和 m 個獨立的 hash function，當要寫入資料（x）的時候，用所有的 hash function 對 x 進行 hash 後 mod n 得到 m 個位置，把 bit array 這些位置的 bit 設為 1，就完成了一次寫入。

圖片中的例子是 m = 3
X, Y, Z 都是 int，作為 index 去設定 bit array 的值

![image](https://hackmd.io/_uploads/HJeFxkPER.png)

查詢也是同樣的流程在得到 m 個位置之後，去 bit array 取出相對應的值，如果全都是 1 的話就代表集合中有這個元素，就可以確認這個資料之前曾經出現過。

**Bloom Filter 的代價**
Bloom Filter 有機會發生 false positive
* 如果 Bloom Filter 回傳沒有（negative）：代表資料 一定沒有 在 Bloom Filter 中
* 如果 Bloom Filter 回傳有（positive）：代表資料 可能有 在 Bloom Filter 中，並不是一定有在 Bloom Filter 中

在使用 Bloom Filter 情境，是要可以忍受 false positive 的發生，且發生之後不會造成太大的影響

**Bloom Filter 使用案例**
* 搶票流量控制：
    *在搶票的大流量的狀況下，我們必須限制進來 server 的流量，但不能擋已經成功 reserve ticket 的 user 繼續進行後續付款取票的流程， 這時候就可以用 bloom filter 快速辨別該 request 的 jwt 是否在 bloom filter 中，有的話代表有訂到票，就可以直接放行，進行後續付款的步驟。記得控制好 false positive rate 跟處理流程，如果 false positive rate 太高，放行太多應該要擋掉的 request，後端流量還是會衝很高。
* Yahoo Email 確認收件者在不在連絡清單：
    在進入 Yahoo Email 的頁面後會把 user 的聯絡清單放到 client 端的 bloom filter，在 user 寄信的時候，可以快速檢查收件人是不是已經在聯絡清單中，沒有的話就可以詢問要不要新增，這樣做的好處是，在確認時不用在呼叫後端，也可以快速地得到結果。
    
### 我的看法
![image](https://hackmd.io/_uploads/SylZDCIVC.png)
**會發生快取穿透有兩種可能性:**
* 邏輯操作錯誤
* 駭客惡意攻擊

**解決方案:**
1. 非法請求的限制
    當有大量惡意請求存取不存在的資料的時候，會發生快取穿透，因此在API入口需要判斷求請求參數是否合理，請求參數是否含有非法值、請求欄位是否存在，如果判斷出是惡意請求就直接回傳錯誤，避免進一步存取快取和資料庫。
3. 快取空值或默認值
    當應用程式發現快取穿透的現象時，可以針對查詢的資料，在快取中設定一個空值或預設值，這樣後續請求就可以從快取中讀取到空值或預設值，傳回給應用程式，而不會繼續查詢資料庫。
5. 使用布隆過濾器判斷資料是否存在，避免透過查詢資料庫來判斷資料是否存在
    可以在寫入資料庫資料時，使用布隆過濾器做個標記，然後在使用者請求到來時，應用程式確認快取失效後，可以透過查詢布隆過濾器快速判斷資料是否存在，如果不存在，就不用透過查詢資料庫來判斷資料是否存在。即使發生了快取穿透，大量請求只會查詢 Redis 和布隆過濾器，而不會查詢資料庫，保證了資料庫能正常運行，Redis 本身也是支援布隆過濾器的。
    
**對於布隆過濾器的看法**
由1組bitmap array(長度N)與 M組hash function來做後續的計算，當一組寫入資料(設x)進入布隆過濾器時，會針對這組資料進行hash function得到output後再mod bitmap array的長度，即可得到m個位置(這邊指標記的index)，後續再把bitmap array中的m個index進行標記(標記為1)，如此以來就完成了一次寫入。
![image](https://hackmd.io/_uploads/r1zIryPE0.png)

當套用要查詢資料 x 是否在資料庫時，透過布隆過濾器只要查到bitmap array中對應的第m位置的值是否全為 1，只要有一個為 0，就認為資料 x 不在資料庫中。


布隆過濾器由於是基於hash function實現查找的，高效查找的同時存在hash衝突的可能性，例如資料x 和資料y 可能都落在第1、4、6 位置，而事實上，可能資料庫中並不存在資料y，有誤判的情況。

所以，布隆過濾器說資料存在，不一定證明資料庫中存在這個資料，但是查詢到資料不存在，資料庫中一定就不存在這個資料。

![image](https://hackmd.io/_uploads/BJu5cJw4C.png)

### 我會怎麼做
在快取層之前加上布隆過濾器，這可能會比事先在快取裡加上一堆空值判斷來的有效果，缺點是可能會出現誤判行為，以及需要跟DB同步一資料，但在權衡利弊下，使用布隆過濾器可能是比較好的實現。在快取前佈署的好處是，若資料被布隆過濾器判斷是不存在的，則可直接reject，若有再往下查找，如此一來快取也不會累積太多的快取而導致記憶體使用過多

![image](https://hackmd.io/_uploads/H1swjvd4A.png)




### 相關文獻與參考資料
* https://github.com/doocs/advanced-java/blob/main/docs/high-concurrency/redis-caching-avalanche-and-caching-penetration.md
* https://medium.com/@martin87713/design-pattern-cache-problem-7b721baf6301
* https://medium.com/@Kadai/%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B%E5%A4%A7%E4%BE%BF%E7%95%B6-bloom-filter-58b0320a346d


## 快取擊穿 (Hotspot Invalid)
### 問題描述
快取擊穿的狀況和雪崩有點類似，雪崩是在大量快取同時過期導致高流量請求打入資料庫；擊穿則是某個熱門的快取(高頻被訪問的快取又叫：hotspot)過期，此時又有大量請求該快取湧入，而這些流量就會又直接打在資料庫上，可能造成和雪崩一樣的結果。

快取擊穿其實就是快取雪崩的其中一個問題子集，他們最終所導致的結果是差不多的。
### 常見解法
快取擊穿的解決辦法與快取雪崩類似
* 互斥鎖，保證同一時間只有一個request更新快取，未能獲取互斥鎖的請求需等待鎖釋放後再重新讀取快取，否則就返回空值或者默認值。
* 不給熱點資料設定過期時間，由後台的message queue更新快取，或在熱點資料準備好要過期之前，提前通知後台message queue更新快取以及重新設定過期時間

有文章說可以在redis中使用SETNX設置分佈式鎖，保證同一時間只會有一個請求來訪問快取或DB
其他關於鎖的參考資料 :　https://xiaomi-info.github.io/2019/12/17/redis-distributed-lock/
### GITHUB上較為詳細的敘述
快取擊穿，就是說某個快取存取非常頻繁，在一個集中高並發存取的情況，當這個快取在瞬間失效時，大量的請求就擊穿了快取，直接請求資料庫，就像是在另一間屏障上鑿開一個洞。

不同場景下的解決方式可如下：

如果快取的資料基本上不會發生更新的，則可以嘗試設定熱點資料設定為永不過期。
若快取的資料更新不頻繁，且快取刷新的整個流程精確的情況下，則可以採用基於Redis、zookeeper等middleware的分散式互斥鎖，或者本地互斥鎖以保證僅有少量請求能訪問DB並重新建置快取，其餘request則被鎖釋放後能存取快取。
如果快取的資料更新頻繁，則可利用定時任務(crontab)在快取過期前主動重新建構快取或延後快取的過期時間，以確保所有的請求能一直存取到對應的快取。
### 我的看法
![image](https://hackmd.io/_uploads/HkvIwH_4A.png)
* 一般應用程式當中都會存在某幾個常被訪問的資料，而這些資料被放在快取的話則被稱為熱點資料
* 發生主因是熱點快取過期，導致原有流量一直打進來，導致快取層失效，流量進到DB然後DB崩潰。
* 有效的解法有二，一為設定互斥鎖，去保證當快取失效時，僅有1筆request能訪問DB並recover快取資料，但缺點就是其他的request需要等待;二為監控熱點快取，當快取時間快失效時進行更新，如此一來就能保障全部的request不會阻塞。
* 在防止快取雪崩時就能順便防掉這個問題了，所以主要還是以顧好快取雪崩為主

![image](https://hackmd.io/_uploads/BJD2edd40.png)

### 相關文獻與參考資料
* https://xiaomi-info.github.io/2019/12/17/redis-distributed-lock/
* https://medium.com/@martin87713/design-pattern-cache-problem-7b721baf6301
*　https://xiaolincoding.com/redis/cluster/cache_problem.html#%E7%BC%93%E5%AD%98%E5%87%BB%E7%A9%BF
*　https://github.com/doocs/advanced-java/blob/main/docs/high-concurrency/redis-caching-avalanche-and-caching-penetration.md


## Workshop
在Workshop中實作的架構

### 原始架構
![image](https://hackmd.io/_uploads/SkX7Ncd4C.png)

![image](https://hackmd.io/_uploads/r1XEV9ONR.png)

可以體現的問題 :　
**1. 有無快取的response差異**
    此部分有兩個架構建立未有cache與有cache的架構，主要可體現出沒有Cache時客戶端得到response的時間與佈署cache的架構有何差異。
**2. 以此架構延伸後續快取問題的解決**
使用jmeter或其他測試工具攻擊服務，讓服務出現快取問題。




### 針對快取雪崩
![image](https://hackmd.io/_uploads/SkTAH5OEC.png)
透過上圖架構，模擬本地快取無資料時，如何與外部快取取得資料，甚至在快取服務故障時，如何透過斷路器限制訪問流量。

### 針對快取穿透
![image](https://hackmd.io/_uploads/B1lWPcOEC.png)
![image](https://hackmd.io/_uploads/HJhZwcu4A.png)

上述兩圖差異為有無布隆過濾器，
解決方案1為較完善的架構，可以在惡意訪問在布隆過濾器就篩掉，這邊不會像解決方案2產生過多key，省空間，但可能有誤判行為，故加上限流保護。
解決方案2也是常見的方法之一，當資料在快取和DB都找不到時就將該查詢寫入快取中，並設定為null，防止類似請求一直打

### 針對快取穿透
![image](https://hackmd.io/_uploads/BJosF5_NC.png)
快取穿透問題算是能引發快取雪崩的問題之一，故能在預防快取雪崩時防範掉，這邊就加上一個後臺程式去定期更新快取並監控過期時間。

## 快取同步
### 常見的快取佈署策略
一般最直接的做法都是將快取放在DB之前，來當作資料前哨站，因為快取是基於記憶體寫入讀取，故速度比傳統資料庫快上許多，可將業務常用的資料放在快取當中，當請求進入應用程式時就直接到快取拿資料，省去到資料庫查詢資料的時間，如下圖。
![image](https://hackmd.io/_uploads/HysW5oFV0.png)

在使用快取服務上，我們最希望達到的效果就是，高Cache Hit Ratio，減少 Cache Miss 的機率，如此一來才能最高限度的提升效能，減少資料庫的負擔。

但快取不是只要加在DB前就好了，還需要考慮到多種層面因素，例如快取存的資料種類、快取的位置要擺哪、快取的讀寫流程都是會因場景而異的

#### 考慮因素
* 資料的種類
    通常會被放進快取的資料會有幾個特徵，「常被使用」、「不常被修改」。
    再來就需要考慮資料被讀寫的頻率有多高而去制定快取策略，例如社群媒體上的個人資料通常是寫入一次後，會有多次讀取、系統的 log 則是 write heavy，讀取的次數反而不多。
* 快取位置
    快取位置的擺放通常會有兩種策略，如下圖所示，都遵守「先到快取看看有沒有資料，有就直接回傳，沒有再去跟資料庫拿資料。」的原則。
    ![image](https://hackmd.io/_uploads/Hk3J36K4C.png)

    ![image](https://hackmd.io/_uploads/r1uS2aYNC.png)
    如果採用 Cache Aside 的讀取流程會像上面這張圖，如果快取有資料就直接拿，沒有的話就跟資料庫拿，「資料庫回傳資料後直接給 Application，再由 Application 把資料存回到快取中。」這也是業界最常見到的模式，這種策略的好處在於比較能承受 Cache Failure 的狀況，因為可以再去跟資料庫要資料（當然這對應用效能是硬傷，在高流量下也可能導致資料庫炸掉）。
    ![image](https://hackmd.io/_uploads/r1__h6KE0.png)
    如果採用 Inline Cache 的讀取流程則會如上圖，與 Cache Aside 的差別在於從資料庫取回資料後會直接存到快取中再傳回給 client ，然後去資料庫抓資料的責任也變為由 Cache Provider 負責。

* 快取的讀流程
    根據快取的位置，分為 Inline 與 Look Aside ，那麼跟 DB 要資料的角色就分為兩種狀況:
    *     Read-Through (Inline) : 快取跟 DB 要資料
    *     Read-Aside (Look Aside)：Application 跟 DB 要 (業界常用)
    業界會喜歡用Read-Aside的原因可能是怕快取故障，導致跟DB拿不到資料使得系統無法運行。
    快取的讀取流程會有一個問題，那就是在第一次讀取時，因為快取裡還沒有資料，所以一定會到資料庫拿，有些開發者會採用 「warning」 或「pre-heating」的方式手動發起 query，讓快取先存好資料，使用者第一次發出請求時快取就有資料可以回傳。
* 快取的寫流程
    「在高併發的流量下，有可能產生快取與 DB 資料不一致的問題。」，比較大的問題就是出在寫的流程，因為不同的寫入方式會造成不同的問題，而快取的寫策略就是為了解決不一致性的問題。
    快取的寫策略大致可以分為:
    *     先存 DB 後存 Cache
    *     先存快取後存 DB
    ![image](https://hackmd.io/_uploads/SkdDATtNC.png)
    有文獻建議說採用刪除快取而非修改快取，原因在於高併發狀況下修改快取，可能會導致資料不一致的問題
    
#### 場景 1 - 先存 DB 後存 Cache
![image](https://hackmd.io/_uploads/HyZey0YVR.png)
request A、B分別對快取與DB發起修改請求，最終資料正確性應該要以DB為主，正確的快取與 DB 資料應該要是 100，但卻是 200，但如上圖所示，如果透過快取去拿資料的話，可能會出現DB已經修改了，但快取存的是不同值，導致錯誤產生。

雖然刪除快取可以避免高併發「寫入」不一致的問題，但他卻會在同時有並行「讀取」時有可能會發生問題
![image](https://hackmd.io/_uploads/rkP_l0KN0.png)
上圖造成了，快取 0 ，DB 200 的不一致狀況

如果不考慮讀取的狀況的話，這種「先改快取，再改 DB 」的方式還有幾種策略，不過以下策略是採用更改快取而不是刪除快取，因為它們較依賴快取提供的資料，期望使用者可以在快取就找到資料：
* Write-Through：更新快取後，同步更新 DB。因為同時修改快取跟 DB，所以會比沒用快取還要慢，但是卻增強了一致性，如果是寫入一次後，接下來幾乎會是大量的讀取請求，那這樣的寫入 Latency 也許是值得的。
* Write-Back | Write-Behind：更新快取後，非同步更新 DB。寫入快取後就回傳給 Client，等有空閒時再慢慢修改 DB ，降低了 write lantency。為了確保用戶不會有拿不到資料的狀況，最晚也要在快取要過期並被 evict 以前完成對 DB 的更改。這種方式的缺點很明顯，通常快取資料是存在 Memory 中的，萬一快取服務 crash 了，資料很可能就永遠遺失了。
#### 場景 2 - 先改 DB，再刪除快取的狀況
即便是先改 DB，如果選擇修改快取，一樣有可能會產生不一致問題，因此這邊從刪除快取的策略來看。也就是說流程是這個樣子：
1. 用戶請求修改資料
1. 先修改 DB資料
1. 直接將快取移除

這個模式也被稱作 Cache Aside Pattern，以快取位置來看是採用 Look Aside，這個模式也是 Facebook 採用的 Policy，不過它會產生一個問題：快取操作 Failure 會產生資料不一致。
![image](https://hackmd.io/_uploads/SJ_tWCKN0.png)
但這個狀況發生的機會不高，如果 Retry 幾次刪除快取操作都不成功，很有可能是快取 Server 掛掉了，那這樣子的狀況下 Request B 應該也讀不到舊的快取資料才對，另一個解決方案則是可以在快取操作 Failure 時對 DB 做 rollback。

### 文獻與參考資料
https://oldmo860617.medium.com/%E4%B8%8D%E5%90%8C%E7%9A%84-cache-policy-%E6%95%88%E8%83%BD-%E8%88%87-%E4%B8%80%E8%87%B4%E6%80%A7-%E4%B9%8B%E9%96%93%E7%9A%84%E6%8A%89%E6%93%87-709455fa472a
https://www.ithome.com.tw/voice/67567
## 快取鎖
### 常見問題
### 常見作法
### 文獻與參考資料
https://xiaomi-info.github.io/2019/12/17/redis-distributed-lock/


## 一看就懂快取三大問題的因果關係與解決辦法 (超重點整理)
### 先看懂快取在做些甚麼 

快取資料存取的地方與資料庫不同，快取的資料存在於記憶體中，資料庫存在硬碟(HDD、SSD)當中，所以在存取速度的比較上快取佔據了較大的優勢。
資料響應速度也是對於一個系統好壞評估的一大重點，所以現今的大型系統幾乎都會使用快取機制來作為資料讀取的前哨站。

![image](https://hackmd.io/_uploads/HJSWmNh40.png)
如上圖所示，上圖為一簡單的架構圖，當Request進入服務時服務需要到資料存取層拿到資料後才能響應給客戶端，一般的架構設計會先至快取要資料，看快取是否有我們的目標資料，如果沒有再去資料庫拿。
這種架構會帶來一些好處，例如:
1. 加速使用者得到響應的速度，
2. 降低資料庫的負擔

但每種解決方案都會出現一些問題，例如快取資料如何與資料庫同步，或是後續將提到的快取三大問題。

### 快取雪崩 (Cache Avalanche)

#### 發生起因與反應過程
快取雪崩 (Cache Avalanche)，顧名思義就是由快取元件引發的問題，一連串的事故導致資料存取層(DB)失效，使得系統最終出現狀況。
一般系統設計上，流量進入系統時會先到快取拿資料以完成快速響應；當系統接收高併發請求且剛好快取當機(故障)或大量快取過期則會引發此問題，在快取失效的狀況下，request會到資料庫去拿資料(因為在快取拿不到想要的資料)，而資料庫也會有流量負載上限，當大量請求灌進資料庫時就會換資料庫無法負荷而關機(故障)，此時公司的DBA就會去重啟DB，但流量問題依舊存在所以資料庫重啟後又會被打掛，問題一直循環。

![image](https://hackmd.io/_uploads/SJd3uEhN0.png)

#### 解決辦法
最直觀的辦法就是針對負責資料處理的機器與流量進行防範。
##### 機器面向
* 在機器上為資料存取層增加主從式架構，當master快取故障時slave快取可快速補上master的工作，當然這個解決方案也會有弊端，因為如何判斷master的流量承受狀況需要一台監控機器，如果監控機器也發生故障的話，主從式快取架構等於失效。
* 若系統架構為分散式也可以在本地架一個快取服務，這樣服務就能直接在本地快取拿資料，就不用跑到外部快取集群拿資料了
##### 資料存取面向
此部分可針對兩個解法著手
1. 制定快取過期時間策略
    對於各個Cache的過期時間進行完善的規劃，也就是不要讓Cache在同個時間點過期，至於多久要過期，就取決於該資料實際上需要的更新頻率，或是設定成永不過期。
2. 利用互斥鎖
    這種狀況基本會出現在資料從資料庫寫回快取的場景，在快取層實作互斥鎖，基於其特性，同一個時間內只能有一筆請求向資料庫拿資料，拿完後寫回快取再讓其他請求從快取拿資料，如此一來就能降低請求塞爆資料庫的狀況。
    
##### 流量
對於系統管理者而言，盡量不要對硬體設備或任一服務抱有太大的信心，畢竟每個服務都會有故障的機率，因此可從最根本的流量問題進行防範。
因為無論是快取層還是資料庫都會有出錯的機率,可以將它們視為資源。若一個流量較大的系統，有一個資源不可用，可能會造成所有請求在取得這個資源時異常，造成整個系統不可用，因此可加入限流(流量限制)、服務降級的操作來減少當下流量的湧入，降低系統故障的機率。


![image](https://hackmd.io/_uploads/Sy9H_HhNR.png)

![image](https://hackmd.io/_uploads/B1xI_rhV0.png)

### 快取穿透 (Cache Penetration)

#### 發生起因與反應過程
請求的資料從頭到尾都不存在快取跟資料庫中。
因此請求穿過快取直接打在資料庫上，但資料庫也找不到對應的資料，導致所有類似的請求不斷地打在資料庫上，當流量一大，又會再次造成資料庫崩潰。

舉例常見的攻擊
* 有一組API為 api/v1/product/{$id}
id為數字，我們希望這個訪問所帶的id為正整數且資料庫存在這筆資料。
有些惡意訪問則會帶入負數(-999)或是資料庫中根本不存在的id進行"大量請求"，又因上述提及的架構，導致快取沒資料後大量請求打進DB，然後DB又作了一堆無意義的搜尋，一來一回資料庫可能就會死掉，上述這種行為就被稱為快取穿透，甚至再嚴重一點可能會造成雪崩。

#### 解決辦法
可以在快取層之前加上一些請求限制或驗證
##### 快取層前的解決方案
###### 使用布隆過濾器
布隆過濾器主要是幫我們在快取層之前過濾掉一些無效的請求，以避免過多的無效請求直接去access資料庫。

其原理就是對一個bitmap array進行index寫入，初始的index皆為0，當資料進入時會透過bitmap array的長度(N)與M個的hash function進行反應，最終得出M個數字(即為index)，最終再將bitmap array對應的index改為1。
布隆過濾器一開始的資料是空的，所以需要跟資料層進行交互，把常用的資料用上述方式寫入到布隆過濾器中，讓其記得哪些index配起來是有資料的。
後續資料請求進來時即可把資料直接丟到布隆過濾器中運算，其將自動判斷資料是否在快取或資料庫中，但布隆過濾器也會有誤判的時候，
例如某組資料算出來的index跟資料庫或快取中資料的index一致，但他們壓根不一樣，這時只能透過拉長bitmap array的長度去降低誤判率了。
但是布隆過濾器提供的機制則會比較容易判斷不存在於資料層的資料 => 他說不存在那資料一定不存在，他說存在那資料可能存在

###### 快取空值
這種方式就相對土炮一些了，不審查任何請求，就讓請求進到DB去查資料，如果資料不存在就將這筆資料在快取中紀錄為空值，如此一來下次被訪問時就知道資料不存在了。
但這樣會引發幾個問題
1. 快取空間消耗過快，在大量惡意請求下，快取一定不可能存那麼多資料，並且還有原有資料需要使用，這對於空間處理而言是不友善的
2. 一定要搭配互斥鎖，限定同一時間僅有一個請求訪問DB，否則會有大量請求塞進DB，進一步造成雪崩


![image](https://hackmd.io/_uploads/ryN66IhE0.png)

我的實作方式會使用限流+布隆過濾器進行，透過限流管制流量(這邊依照系統高峰與離峰的值去作調整)，再用布隆過濾器進一步的篩掉請求值，降低流量爆炸以及非法訪問的問題，進而避免快取擊穿


### 快取擊穿 (Hotspot Invalid)
#### 發生起因與反應過程
快取擊穿的狀況和雪崩有點類似，雪崩是在大量快取同時過期導致高流量請求打入資料庫；快取擊穿則是某個熱門的快取過期，此時又有大量請求該快取湧入，而這些流量就會又直接打在資料庫上，可能造成和雪崩一樣的結果。
快取擊穿其實就是快取雪崩的其中一個問題子集，他們最終所導致的結果是差不多的。

#### 解決辦法
問題跟雪崩類似，解法也差不多
主要是熱門快取失效，所以將這個快取寫回來基本上就可以解決了

* 互斥鎖，保證同一時間只有一個request更新快取，未能獲取互斥鎖的請求需等待鎖釋放後再重新讀取快取，否則就返回空值或者默認值，這種做法較為保險，避免快取過期時流量不會全部砸進資料庫裏頭。
* 不給熱點資料設定過期時間，這種作法通常需要第三方監控來執行，若熱門快取為產品列表之類的資料，如果對其在資料庫中進行了修改，則快取中的資料未與資料庫同步則會出現誤差，若使用在關於庫存的資料當中造成的後果會變得嚴重。通常會建立一個後台監控並對熱門資料設定過期時間，由後台去監控資料並更新快取，或在熱點資料準備好要過期之前，提前更新快取以及重新設定過期時間


![image](https://hackmd.io/_uploads/H1lgDvnNA.png)
因快取擊穿本身就可被視為快取雪崩的子集，所以在架構調整上與雪崩差不多，只加上一個後台服務來監控快取資料