什么是緩存

緩存就是數(shù)據(jù)交換的緩沖區(qū)（稱作Cache）拳芙，是存貯數(shù)據(jù)（使用頻繁的數(shù)據(jù)）的臨時(shí)地方薛夜。有cpu緩存袱蚓、文件系統(tǒng)緩存枚碗、應(yīng)用層緩存等逾一；今天講的是應(yīng)用層緩存:應(yīng)用層緩存指的是從代碼層面上，通過代碼邏輯和緩存策略肮雨，實(shí)現(xiàn)對數(shù)據(jù)遵堵、頁面、圖片等資源的緩存怨规，可以根據(jù)實(shí)際情況選擇將數(shù)據(jù)存在文件系統(tǒng)或者內(nèi)存中陌宿，減少數(shù)據(jù)庫查詢或者讀寫瓶頸，提高響應(yīng)效率波丰。
緩存的本質(zhì)就是用空間換時(shí)間壳坪，犧牲數(shù)據(jù)的實(shí)時(shí)性，以服務(wù)器內(nèi)存中的數(shù)據(jù)暫時(shí)代替從數(shù)據(jù)庫讀取最新的數(shù)據(jù)掰烟，減少數(shù)據(jù)庫IO爽蝴，減輕服務(wù)器壓力沐批，減少網(wǎng)絡(luò)延遲，加快頁面打開速度蝎亚。

以下介紹一些常用緩存的設(shè)計(jì)模式（結(jié)構(gòu)模式）及數(shù)據(jù)模式（數(shù)據(jù)結(jié)構(gòu)）

緩存設(shè)計(jì)模式

Cache-Aside

image.png

最常用模式九孩。應(yīng)用程序 先查 緩存，緩存存在 則直接返回颖对；不存在時(shí)查數(shù)據(jù)庫捻撑，緩存并返回。
缺點(diǎn)：緩存與數(shù)據(jù)庫可能不一致缤底，一般需要設(shè)置緩存過期時(shí)間
這種一般用于數(shù)據(jù)變動(dòng)不太頻繁、或者實(shí)時(shí)性要求不高的場景番捂。

Read-Through Cache

image.png

類似cache-aside个唧，不同的是 緩存是獨(dú)立的，應(yīng)用程序不和數(shù)據(jù)庫直接打交道设预。一般結(jié)合下面的write-through一起使用

Write-Through Cache

image.png

數(shù)據(jù)修改時(shí)先將數(shù)據(jù)寫入緩存徙歼，緩存再更新到數(shù)據(jù)庫。與read-through結(jié)合可解決數(shù)據(jù)不一致問題鳖枕；麻煩的是數(shù)據(jù)變動(dòng)都要通知緩存變動(dòng)（如有多個(gè)途徑修改數(shù)據(jù)則比較麻煩）魄梯，還有就是數(shù)據(jù)變動(dòng)較多時(shí)數(shù)據(jù)庫壓力還是不小的，可用于數(shù)據(jù)表懂較少宾符，但一致性要求高的場景酿秸。

image.png

Write-Around

image.png

相對于write-through，它是由應(yīng)用程序?qū)⒕彺鎸懭霐?shù)據(jù)庫魏烫；配合cache-aside使用辣苏，更新也是由應(yīng)用程序發(fā)起的，但是先寫入數(shù)據(jù)庫哄褒，再更新緩存（不能如write-through一樣先更新緩存稀蟋，后更新數(shù)據(jù)庫；因?yàn)樵诟虏僮鱽砗竽派模绻彺嫖磳懭肭捌渌M(jìn)程/線程未命中緩存退客，就會(huì)查數(shù)據(jù)庫的舊數(shù)據(jù)并可能覆蓋數(shù)據(jù)）

image.png

Write-Back

write-through改良，就是多次更新都是會(huì)只更新到緩存链嘀，特定時(shí)間/特定次數(shù)時(shí)才會(huì)更新到數(shù)據(jù)庫萌狂。能夠在多修改的場景下降低數(shù)據(jù)庫負(fù)擔(dān)。缺點(diǎn)是緩存崩潰時(shí)為持久化數(shù)據(jù)會(huì)丟失

image.png

緩存選擇

緩存的數(shù)據(jù)結(jié)構(gòu)

哈希表(散列表)

根據(jù)key 獲取/設(shè)置 value管闷，時(shí)間復(fù)雜度為O(1)
redis里h開頭的命令基本就是對哈希表的操作

image.png

集合類（數(shù)組/隊(duì)列）

根據(jù)index獲取/設(shè)置vale粥脚，根據(jù)index查找時(shí)間復(fù)雜度為O(1)，根據(jù)value查找時(shí)間復(fù)雜度為O(n)
ruby數(shù)組是數(shù)組與隊(duì)列的結(jié)合包个，既可以使用index操作刷允，也可以進(jìn)行push,pop等操作
redis的list為雙向鏈表冤留，查找時(shí)間復(fù)雜度為o(n)

image.png

對可消費(fèi)資源進(jìn)行緩存，如消息隊(duì)列等树灶。特點(diǎn)是一次取一個(gè)值（非特定值）

有序集合類（搜索二叉樹/跳躍表）

常用的搜索二叉樹是紅黑樹纤怒，平衡了搜索二叉樹的退化和平衡二叉樹的維護(hù)開銷。
跳躍表就是在鏈表的基礎(chǔ)上增加了多級(jí)索引天通，從而實(shí)現(xiàn)查找時(shí)間復(fù)雜度為O(㏒n)
跳表對比紅黑樹

image.png

他肯定比hash要慢像寒，但提供排序烘豹，以及按范圍查找數(shù)據(jù)。業(yè)務(wù)場景 如 定時(shí)任務(wù)诺祸、排行榜等携悯。
我們的業(yè)務(wù)我感覺 在 分配類業(yè)務(wù)時(shí)，可根據(jù)不同的維度 使用不同的跳表筷笨；如分配公司時(shí)根據(jù) 員工 現(xiàn)有公司數(shù)憔鬼、重點(diǎn)公司數(shù)等進(jìn)行排序后分配，這部分?jǐn)?shù)據(jù)可以緩存并在數(shù)據(jù)變化時(shí)更新score胃夏；分配時(shí)按條件取到符合的 數(shù)據(jù)的交集轴或，這樣就減少了每次分配都要計(jì)算的時(shí)間消耗。

緩存淘汰策略

先進(jìn)先出 /FIFO(First Input First Output)

ruby直接hash就可實(shí)現(xiàn)仰禀，先設(shè)置的 shift即移除照雁。
缺點(diǎn)：太過簡單粗暴，先緩存的 哪怕后來比其他使用更多悼瘾，時(shí)間更近依然會(huì)被淘汰囊榜。

最近最少使用/ LRU(Least Recently Used):

LRU算法又叫淘汰算法,根據(jù)數(shù)據(jù)歷史訪問記錄進(jìn)行淘汰數(shù)據(jù),其核心思想是“如果數(shù)據(jù)最近被訪問過,那么將來被訪問的幾率也更高”。
每次get時(shí)把最后訪問的放到隊(duì)尾亥宿，每次緩存滿時(shí)移除隊(duì)首緩存
缺點(diǎn)：未考慮命中率的問題
https://github.com/SamSaffron/lru_redux

最不經(jīng)常使用/LFU(Least Frequently Used)

按照訪問次數(shù)卸勺，最近最少使用的緩存數(shù)據(jù)，先淘汰烫扼。有多個(gè)最少使用的緩存數(shù)據(jù)曙求，再按照LRU淘汰。
缺點(diǎn)：命中次數(shù)需要記錄映企，計(jì)算悟狱，多占用內(nèi)存和cpu。

# Observation

# LFU least frequently used
# key's frequency needs to be tracked

# get(key) -> exist -> freq ++
#          -> x -> -1
# put(k, v) -> exist -> modify the node val, freq ++
#           -> x -> store and evict (if size is full)
          
# maintain the HashMap of key the frequency, the value DDL of LRU within that frequency           
# 1. frequency map
# 2. node map
# get -> get node -> take that out of frequency map -> put that into the head of now appropriate frequency map list
# put -> (found) get node -> same as get
#     -> (new)   init node with frequency 1, put that into the map
#                -> (if full)
#                   freq_map[1], remove_from_tail
# {
#   1 => h -> 3 -> 2 -> t
#   2 => h -> 
# }

# ["LFUCache","put","put","get","put","get","get","put","get","get","get"]
# [[2],       [1,1],[2,2],[1],[3,3],[2],[3],[4,4],[1],[3],[4]]

Node = Struct.new(:key, :val, :usage, :next, :prev)
  
class DLinkedList
  def initialize
    @head = Node.new
    @tail = Node.new
    @head.next = @tail
    @tail.prev = @head
  end
  
  def empty?
    @head.next == @tail
  end
  
  def remove(node)
    node.prev.next = node.next
    node.next.prev = node.prev
    node.next = nil
    node.prev = nil
    node
  end
  
  def add_to_top(node)
    tmp = @head.next
    @head.next = node
    node.next = tmp
    tmp.prev = node
    node.prev = @head
  end
  
  def remove_from_tail
    raise if empty?
    remove(@tail.prev)
  end
end

class LFUCache
  def initialize(size)
    @size = size
    @memo = {} # key value map
    @freq_map = Hash.new { |h,k| h[k] = DLinkedList.new }
    @min_freq = nil
  end
  
  def get(key)
    return -1 if @size == 0 || @memo[key].nil?
    
    node = @memo[key]
    @freq_map[node.usage].remove(node)
    
    # if this has been recorded as min, needs to increment the min_freq lookup counter
    @min_freq += 1 if @freq_map[node.usage].empty? && @min_freq == node.usage
    
    node.usage += 1
    @freq_map[node.usage].add_to_top(node)
    node.val
  end
  
  def put(key, value)
    return if @size == 0
    
    if node = @memo[key]
      node.val = value
      get(key)
    else
      evict if @memo.keys.length == @size
      
      new_node = Node.new(key, value, 1)
      @freq_map[1].add_to_top(new_node)
      @min_freq = 1
      @memo[key] = new_node
    end
  end
  
  private
  
  def evict
    deleted = @freq_map[@min_freq].remove_from_tail
    @memo.delete(deleted.key)
  end
end

參考：https://cloud.tencent.com/developer/article/2077083