CDN緩存工作過程如下：用戶發出一個請求，如果請求被命中，緩存將對用戶的請求進行響應，返回其請求的數據；如果未被命中，緩存向上拉取用戶需要的數據，并對其存儲的數據進行替換。

緩存算法的意義在于，根據用戶的請求習慣，對于緩存種的數據進行更新，使得用戶據請求的命中率提高，縮短整體響應用戶請求延時，同時提高高峰時間網絡所能承受的訪問容量。

現有的緩存替代算法主要思路有下面幾種：
1、基于訪問頻率，通過某段時間內對資源被訪問的次數進行統計，以此判斷該資源接下來是否被訪問，典型算法：LFU、2Q、LIRS
2、基于訪問時間，通過i記錄資源訪問的時間，以時間做判斷，典型算法：LRU
3、訪問時間與訪問頻率相結合，典型算法：LRFU、FBR
CDN緩存算法具體有五種典型算法：
1、“最近最少使用”緩存算法
2、“最少頻率使用”緩存算法
3、“基于分數因子”緩存算法
4、“塊等級”緩存算法

Least Recently Used算法

緩存將保留最近一段時間內經常使用的數據，而淘汰最近未被經常使用的數據。
基于事實：最近一段時間內經常被訪問的數據在未來一段時間內也會被訪問
簡單版本的實現可以參考https://leetcode-cn.com/problems/lru-cache/
缺點：最近被訪問的內容不一定是最熱門的，這將導致一些冷門內容留在緩存種，影響用戶訪問內容和服務響應用戶的效率。
另外可以看看mysql里面對于lru的改進：MySQL——Innodb改進LRU算法

Least Frequency Used算法

該算法按照內容的訪問頻率對內容進行排序。
緩存一般被分為兩部分：固定緩存（AC,Actual Cache）和隱藏緩（SC，Shadow Cache）
固定緩存是更新不頻繁，資源變動較少的那部分緩存
隱藏緩存是更新頻繁，資源變動較大的那部分緩存
當用戶發出訪問請求時，未命中的內容將先被存儲到SC種。在一定時間間隔T內，緩存中會維持一個頻率列表，記錄每個內容被訪問的次數。T時間過去之后，{AC,SC}種被請求次數最多的內容將會被更新到AC中，在下一輪T之內，AC中內容不會被替換掉。
基于事實：內容被訪問的頻率能夠反映內容的熱門程度。AC和SC的增加使得最少頻率的準確率得到提高
缺點：計算頻率的時間段T的大小不好控制，AC和SC的容量不好控制，替換時間設定不好控制
簡單版本的實現可以參考：
https://leetcode-cn.com/problems/lfu-cache/solution/lfuhuan-cun-by-leetcode-solution/
代碼如下：

// 緩存的數據結構
struct cacheNode {int cnt;    // 緩存使用的頻率int time;   // 緩存使用的時間int key;    // 緩存的鍵int value;  // 緩存的值cacheNode(int _cnt, int _time, int _key, int _value) {cnt = _cnt;time = _time;key = _key;value = _value;}// 實現一個cacheNode的比較函數// 頻率小的排前面，如果頻率一樣，時間短的排前面bool operator< (const cacheNode& rhs) const {return cnt == rhs.cnt ? time < rhs.time : cnt < rhs.cnt;}};
class lfuCache {
private:// 緩存的容量，時間數int capcity;int time;std::unordered_map<int, cacheNode> keyTable;std::set<cacheNode> balanceTree;
public:lfuCache(int cap) {capcity = cap;time = 0;keyTable.clear();balanceTree.clear();}int get(int key) {if (capcity == 0) return -1;auto it = keyTable.find(key);if (it == keyTable.end()) return -1;cacheNode cache = it->second;balanceTree.erase(cache);cache.cnt += 1;cache.time = ++time;balanceTree.insert(cache);it->second = cache;return cache.value;}void put(int key, int value) {if (capcity == 0) return;auto it = keyTable.find(key);if (it == keyTable.end()) {if (keyTable.size() == capcity) {keyTable.erase(balanceTree.begin()->key);balanceTree.erase(balanceTree.begin());}cacheNode cache = cacheNode(1, ++time, key, value);keyTable.insert(std::make_pair(key, cache));balanceTree.insert(cache);} else {cacheNode cache = it->second;balanceTree.erase(cache);cache.cnt += 1;cache.time = ++time;cache.value = value;balanceTree.insert(cache);it->second = cache;}}
};

Scoring based Caching算法

1、定義：對每一個視頻(Vi),都維護一個分數(Si)。每個視頻i在被放入緩存時，都會得到一個初始化分數Si = B。
每一次視頻i被請求，該視頻都會得到一個新的分數，而其余視頻分數也會相應調整：Si = Si + A，其余視頻Sk = Sk - 1(k != i)
2、替換規則：在維護一個分數上，有兩種替換策略：

• 區間分數法：定義一個有效分數區間【M，N】。若某個視頻的分數在這個區間內，且不再緩存中，則把這個視頻放入緩存。如果某個在緩存中的視頻的分數不在這個區間內，則在緩存中刪除該視頻
• 最優分數法：根據一個節點的最大存儲能力，如能存L個視頻，選擇最優分數的內容進行緩存。每次有一部視頻的分數有改變，則進行排序，凡分數不在前L的視頻從緩存中刪除，凡分數在前L的視頻加入緩存中

3、請求處理：對于每個CDN視頻的請求，會出現以下三種處理事件

• 1、請求的視頻已在緩存中，請求命中。此時只需要對視頻的分數做出調整，不需要在緩存中刪除內容，也不需要向上級節點請求內容。CDN內部沒有流量消耗
• 2、請求的視頻不在緩存中而算法要求節點緩存該視頻。節點向上級節點賦值被請求的視頻，然后在復制之后向用戶發送被請求的視頻，將視頻加入緩存，調整分數。此時CDN內部有流量消耗，邊緣節點向中心節點復制了視頻內容
• 3、請求的視頻不在緩存中而算法不要求節點緩存該視頻，調整分數，不需要從中心點復制內容，請求被轉發到中心節點。CDN內部沒有流量消耗

4、其他
1、一般來說，節點應該維護每一部視頻的分數，但實際上分數過低的視頻，一般不維護分數，而是從關注列表中移除
2、Shadow Cache。每個節點存儲能力被分為兩個部分。較大的部分用來存儲內容，較小的部分用來存儲視頻列表、分數等與管理有關的內容。兩個存儲空間嚴格分開。宏觀上看，節點有部分存儲能看不可見，稱為Shadow Cache
最后，基于分數因子的緩存算法不是一個獨立的算法，而是其他算法的基礎或者框架。例如LRU和LFU可以看作對于分數不同定義的最優分數法的分數因子緩存。

Chunk-level Caching算法

1、定義：基于塊等級的緩存算法， 時在分數因子緩存算法基礎上，把每個視頻分成大小相同、內容連續的k塊分別存儲，然后每個視頻塊的分數Sk繼承原視頻的分數Si。定義第i個視頻的第k塊視頻的分數為Si,k
2、計分策略：
每部視頻被訪問，則對視頻i內的所有塊都進行+1：Si,k = Si,k +1
若第k塊被完整觀看，則Si,k = Si,k + 1
若停止觀看（退出、快進、快退），則說明用戶對該塊不感興趣，則Si,k = Si,k - 1;
3、請求處理
大部分時候，塊等級的緩存算法，與基于分數因子的緩存算法十分相像，即上面SC出現的3種請求處理的情況都會出現。不同之處在于之前是比較Si來進行取舍，現在是比較Si,k。
4、其他
基于塊等級的緩存算法，主要用于單個內容較大的內容分發網絡，如視頻分發網絡。它考慮了以下一個事實，即人們可能對視頻的某一段感興趣，把整個視頻存儲下來會產生浪費；或者人們只瀏覽了視頻的開頭，就會選擇看或者不看。因此，在計分規則中，充分考慮了這些事實。
① 一個用戶請求了某個視頻，則可能對這個視頻的其他部分都感興趣，因此計分策略1體現了這個需求。
② 一個用戶看完了某一塊，則可能不會再回去看了，因此計分策略2體現了這個需求。
③ 一個用戶停止觀看某段視頻，則可能不會再看這段視頻之后的其他視頻塊，因此計分策略3體現了這個需求。