什么是緩存

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

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

緩存設(shè)計模式

Cache-Aside

image.png

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

Read-Through Cache

image.png

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

Write-Through Cache

image.png

數(shù)據(jù)修改時先將數(shù)據(jù)寫入緩存，緩存再更新到數(shù)據(jù)庫。與read-through結(jié)合可解決數(shù)據(jù)不一致問題；麻煩的是數(shù)據(jù)變動都要通知緩存變動（如有多個途徑修改數(shù)據(jù)則比較麻煩），還有就是數(shù)據(jù)變動較多時數(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ù)庫；因為在更新操作來后，如果緩存未寫入前其他進程/線程未命中緩存，就會查數(shù)據(jù)庫的舊數(shù)據(jù)并可能覆蓋數(shù)據(jù)）

image.png

Write-Back

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

image.png

緩存選擇

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

哈希表(散列表)

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

image.png

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

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

image.png

對可消費資源進行緩存，如消息隊列等。特點是一次取一個值（非特定值）

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

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

image.png

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

緩存淘汰策略

先進先出 /FIFO(First Input First Output)

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

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

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

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

按照訪問次數(shù)，最近最少使用的緩存數(shù)據(jù)，先淘汰。有多個最少使用的緩存數(shù)據(jù)，再按照LRU淘汰。
缺點：命中次數(shù)需要記錄，計算，多占用內(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