title: Cache 常見問題

tags:

• cache

categories:

• Tech

comments: true
date: 2018-06-18 22:00:00

去年的時(shí)候在做系統(tǒng)性能優(yōu)化的工作中叁幢，花費(fèi)了大量的精力為業(yè)務(wù)定制化緩存方案，當(dāng)時(shí)感覺盡善盡美了，但前些天不經(jīng)意再聊起緩存時(shí)發(fā)現(xiàn)在一些細(xì)節(jié)上還欠考慮忌锯。在這里總結(jié)一下做 cache 需要考慮的問題。

大綱如下：

• 緩存模式(Cache Pattern）
• 緩存置換(Cache Replacement)
• 緩存穿透(Cache Penetration)
• 緩存雪崩(Cache Avalanche)

緩存模式/Cache Pattern

比較常見的模式有分為兩大類： Cache-aside 以及 Cache-as-SoR歧譬。其中 Cache-as-SoR(System of Record, 即直接存儲(chǔ)數(shù)據(jù)的DB) 又包括 Read-through滤否、Write-through、Write-behind祠乃。

Cache-aside

Cache-aside 是比較通用的緩存模式，在這種模式兑燥，讀數(shù)據(jù)的流程可以概括：

1. 讀 cache亮瓷，如果 cache 存在，直接返回降瞳。如果不存在嘱支，則執(zhí)行2
2. 讀 SoR，然后更新 cache挣饥，返回
   代碼如下：

# 讀 v1
def get(key):
    value = cache.get(key)
    if value is None:
      value = db.get(key)
      cache.set(key, value)
    return value

寫數(shù)的流程為：

1. 寫 SoR
2. 寫 cache
   代碼如下：

# 寫 v1
def set(key, value):
    db.set(key,  value)
    cache.set(key, value)

邏輯看似很簡(jiǎn)單除师，但是如果在高并發(fā)的分布式場(chǎng)景下，其實(shí)還有很多驚喜的扔枫。

Cache-as-SoR

在 Cache-aside 模式下汛聚，cache 的維護(hù)邏輯要業(yè)務(wù)端自己實(shí)現(xiàn)和維護(hù)，而 Cache-as-SoR 則是將 cache 的邏輯放在存儲(chǔ)端短荐，即 SoR + cache 對(duì)于業(yè)務(wù)調(diào)用方而言是透明的一個(gè)整體倚舀，業(yè)務(wù)無(wú)須關(guān)心實(shí)現(xiàn)細(xì)節(jié)叹哭，只需 get/set 即可。Cache-as-SoR 模式常見的有 Read Through痕貌、Write Through风罩、Write Behind。

• Read Through: 發(fā)生讀操作時(shí)舵稠，查詢 cache超升，如果 Miss，則由 cache 查詢 SoR 并更新柱查，下次訪問 cache 即可直接訪問（即在存儲(chǔ)端實(shí)現(xiàn) cacha-aside）
• Write Through：發(fā)生寫操作時(shí)廓俭，查詢 cache，如果 Hit唉工，則更新 cache研乒，然后交由 cache model 去更新 SoR
• Write Behind：發(fā)生寫操作時(shí)，不立即更新 SoR淋硝，只更新緩存雹熬，然后立即返回，同時(shí)異步的更新 SoR（最終一致）

Read/Write Through 模式比較好理解谣膳，就是同步的更新 cache 和 SoR竿报，讀取得場(chǎng)景也是 cache 優(yōu)先，miss 后才讀 SoR继谚。 這類模式主要意義在意緩解讀操作的場(chǎng)景下 SoR 的壓力以及提升整體響應(yīng)速度烈菌，對(duì)寫操作并沒有什么優(yōu)化，適用于讀多寫少的場(chǎng)景花履。Write Behind 的的 cache 和 SoR 的更新是異步芽世，可以在異步的時(shí)候通過(guò) batch、merge 的方式優(yōu)化寫操作诡壁，所以能提升寫操作的性能济瓢。

下面兩圖是取自 wikipedia 的 Write Through 和 Write Behind 的流程圖:

Write Through 和 Write Behind

小結(jié)

當(dāng)前很多 DB 都自帶基于內(nèi)存的 cache ，能更快的響應(yīng)請(qǐng)求妹卿，比如 Hbase 以 Block 為單位的 cache旺矾，mongo 的高性能也一定程度依托于其占用大量的系統(tǒng)內(nèi)存做 cache 。不過(guò)在程序本地再做一層 local cache 效果會(huì)更加明顯夺克，省去了大量的網(wǎng)絡(luò)I/O箕宙，會(huì)使系統(tǒng)的處理延時(shí)大幅提升，同時(shí)降低下游 cache + db 的壓力铺纽。

緩存置換/ Cache Replacement

緩存淘汰算是比較老的一個(gè)話題扒吁，常用的緩存策略也就那么幾個(gè)，比如 FIFO、LFU雕崩、LRU。而且 LRU 算是緩存淘汰策略的標(biāo)配了融撞，當(dāng)然在根據(jù)不同的的業(yè)務(wù)場(chǎng)景盼铁，也可能其他策略更合適。

FIFO 的淘汰策略通常使用 Queue + Dict尝偎， 畢竟 Queue 先天就是 FIFO 的饶火，新的緩存對(duì)象放在隊(duì)尾，而當(dāng)隊(duì)列滿時(shí)將隊(duì)首的對(duì)象出隊(duì)過(guò)期致扯。

LFU （Least Frequently Used）的核心思想是最近最少被使用的數(shù)據(jù)最先被淘汰肤寝，即統(tǒng)計(jì)每個(gè)對(duì)象的使用次數(shù)，當(dāng)需要淘汰時(shí)抖僵，選擇被使用次數(shù)最少的淘汰鲤看。所以通常基于最小堆 + Dict 實(shí)現(xiàn) LFU耍群。因?yàn)樽钚《衙看巫兓膹?fù)雜度為 O(logn)义桂，所以LFU算法效率為 O(logn)，相比 FIFO蹈垢、LRU O(1) 的效率略低慷吊。

LRU（Least recently Used），基于局部性原理曹抬，即如果數(shù)據(jù)最近被使用溉瓶，那么它在未來(lái)也極有可能被使用，反之谤民，如果數(shù)據(jù)很久未使用堰酿，那么未來(lái)被使用的概率也較低。

LRU 過(guò)期通常使用雙端鏈表 + Dict
實(shí)現(xiàn)（在生產(chǎn)環(huán)境使用鏈表一般都是雙鏈表）赖临，將最近被訪問的數(shù)據(jù)從原位置移動(dòng)到鏈表首部胞锰，這樣在鏈?zhǔn)孜恢玫臄?shù)據(jù)都是最近被使用過(guò)的，而鏈尾都是最久未使用的兢榨，在 O(1) 的時(shí)間復(fù)雜度內(nèi)即可找到要被刪除的數(shù)據(jù)嗅榕。

# LRU 緩存過(guò)期概要邏輯, 無(wú)鎖版

data_dict = dict()
link = DoubleLink() # 雙端隊(duì)列

def get(key):
    node = data_dict.get(key) 
    if node is not None:
        link.MoveToFront(node)
    return node
    
def add(key, value):
    link.PushFront(Node(key,value))
    if link.size()>max_size:
        node = link.back()
        del(data_dict[node.key])
        link.remove_back()

Ps：

1. py3 functools 中 lru_cache 的實(shí)現(xiàn)
2. golang 實(shí)現(xiàn) lru cache

緩存穿透/Penetration

當(dāng)請(qǐng)求訪問的數(shù)據(jù)是一條并不存在的數(shù)據(jù)時(shí)，一般這種不存在的數(shù)據(jù)是不會(huì)寫入 cache吵聪，所以訪問這種數(shù)據(jù)的請(qǐng)求都會(huì)直接落地到下游 SoR凌那，當(dāng)這種請(qǐng)求量很大時(shí)，同樣會(huì)給下游 db 帶來(lái)風(fēng)險(xiǎn)吟逝。

解決方法：

1. 可以考慮適當(dāng)?shù)木彺孢@種數(shù)據(jù)一小段時(shí)間帽蝶，將這種空數(shù)據(jù)緩存為一段特殊的值。

2. 另一種更嚴(yán)謹(jǐn)?shù)淖龇ㄊ鞘褂?BloomFilter, BloomFilter 的特點(diǎn)在檢測(cè) key 是否存在時(shí)块攒，不會(huì)漏報(bào)（BloomFilter 不存在時(shí)励稳，一定不存在）佃乘，但有可能誤報(bào)（BloomFilter 存在時(shí)，有可能不存在）驹尼。Hbase 內(nèi)部即使用 BloomFilter 來(lái)快速查找不存在的行趣避。

基于 BloomFilter 的預(yù)防穿透：

# 讀 v3
r = redis.StrictRedis()
def get(key, retry=3):
    def _get(k):
        value = cache.get(k)
        if value is None:
            if not Bloomfilter.get(k): 
                # cache miss 時(shí)先查 Bloomfilter
                # Bloomfilter 需要在 Db 寫時(shí)同步事務(wù)更新
                return None, true
            if r.set(k,1,ex=1,nx=true):
                value = db.get(k)
                cache.set(k, value)
                return true, value
            else:
                return None, false
        else:
            return value, true
    while retry:
        value, flag = _get(key)
        if flag == True:
            return value
        time.sleep(1)
        retry -= 1
    raise Exception("獲取失敗")

以上兩種通用的方法對(duì)于不同的場(chǎng)景，各有優(yōu)劣新翎。緩存空數(shù)據(jù)的方案程帕，在應(yīng)對(duì)惡意的穿透攻擊時(shí)效果會(huì)很差，因?yàn)閻阂庹?qǐng)求的一般特點(diǎn)是 key 隨機(jī)偽造地啰，請(qǐng)求量巨大愁拭，所以此時(shí)緩存空數(shù)據(jù)的方案會(huì)大量緩存無(wú)意義的數(shù)據(jù)，這些數(shù)據(jù)往往不會(huì)被二次訪問亏吝，因此對(duì)惡意攻擊不會(huì)產(chǎn)生任何效果岭埠，此時(shí)使用 bloomfilter 的方案更優(yōu)。相反的顺呕，如果不存的 key 是可預(yù)估的枫攀，或者有限的的，比如是通過(guò)一定規(guī)則生成的株茶，難以偽造来涨，此時(shí)緩存空數(shù)據(jù)的方案較優(yōu)。

緩存雪崩/Avalanches

雪崩启盛，即在某些場(chǎng)景下蹦掐，緩存宕機(jī)、失效僵闯、過(guò)期等等因素會(huì)導(dǎo)致大量的請(qǐng)求直接落到下游的 DB卧抗，對(duì) DB 造成極大的壓力，甚至一波打死 DB 業(yè)務(wù)掛掉鳖粟。

不同場(chǎng)景下社裆，導(dǎo)致雪崩的原因各不相同。

Case 1

在高并發(fā)場(chǎng)景下（比如秒殺）向图，如果某一時(shí)間一個(gè) key 失效了泳秀，但同時(shí)又有大量的請(qǐng)求訪問這個(gè) key，此時(shí)會(huì)發(fā)生大量的 cache miss榄攀，可能引發(fā)雪崩嗜傅。

這種情況下比較通用的保護(hù)下游的方法是通過(guò)互斥鎖訪問下游 DB，獲得鎖的線程/進(jìn)程負(fù)責(zé)讀取 DB 并更新 cache檩赢，而其他 acquire lock 失敗的進(jìn)程則重試整個(gè) get的邏輯吕嘀。

以 redis 的 set 方法實(shí)現(xiàn)此邏輯如下：

# 讀 v2
r = redis.StrictRedis()
def get(key, retry=3):
    def _get(k):
        value = cache.get(k)
        if value is None:
            if r.set(k,1,ex=1,nx=true): # 加鎖
                value = db.get(k)
                cache.set(k, value)
                return true, value
            else:
                return None, false
        else:
            return value, true
    while retry:
        value, flag = _get(key)
        if flag == True:
            return value
        time.sleep(1) # 獲取鎖失敗，sleep 后重新訪問
        retry -= 1
    raise Exception("獲取失敗")

Case 2

大量 key 同時(shí)過(guò)期，導(dǎo)致大量 cache miss偶房。冷啟動(dòng)或流量突增等都有可能導(dǎo)致在極短時(shí)間內(nèi)有大量的數(shù)據(jù)寫入緩存趁曼，如果它們的過(guò)期時(shí)間相同，則很可能在相似的時(shí)間內(nèi)過(guò)期棕洋。

解決方法：

1. 一個(gè)比較簡(jiǎn)單的方法是隨機(jī)過(guò)期彰阴，即每條 data 的過(guò)期時(shí)間可以設(shè)置為 expire + random。

2. 另一個(gè)比較好的方案是可以做一個(gè)二級(jí)緩存拍冠，比如之前做緩存時(shí)設(shè)計(jì)的一套 local_cache + redis 的存儲(chǔ)方案，或者 redis + redis 的模式簇抵。

另外庆杜，就是合理的降級(jí)方案。在高并發(fā)場(chǎng)景下碟摆，當(dāng)檢測(cè)到過(guò)高的并發(fā)可能或已經(jīng)對(duì)資源造成影響后晃财，通過(guò)限流降級(jí)的方案保護(hù)下游資源，避免整個(gè)資源被打垮而不可用典蜕，在限流期間逐步構(gòu)建緩存断盛，當(dāng)緩存逐漸恢復(fù)后取消限流，恢復(fù)降級(jí)愉舔。

參考

https://medium.com/@mena.meseha/3-major-problems-and-solutions-in-the-cache-world-155ecae41d4f
http://www.ehcache.org/documentation/3.5/caching-patterns.html
https://docs.microsoft.com/en-us/azure/architecture/patterns/cache-aside
https://coolshell.cn/articles/17416.html
https://en.wikipedia.org/wiki/Cache_(computing)
https://docs.oracle.com/cd/E13924_01/coh.340/e13819/readthrough.htm