qq怎么做自己的网站,高校校园网站建设的要求,莆田网站建设培训,谷歌seo是什么职业CDN缓存工作过程如下#xff1a;用户发出一个请求#xff0c;如果请求被命中#xff0c;缓存将对用户的请求进行响应#xff0c;返回其请求的数据#xff1b;如果未被命中#xff0c;缓存向上拉取用户需要的数据#xff0c;并对其存储的数据进行替换。
缓存算法的意义在…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和隐藏缓SCShadow 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_mapint, cacheNode keyTable;std::setcacheNode 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、替换规则在维护一个分数上有两种替换策略
区间分数法定义一个有效分数区间【MN】。若某个视频的分数在这个区间内且不再缓存中则把这个视频放入缓存。如果某个在缓存中的视频的分数不在这个区间内则在缓存中删除该视频最优分数法根据一个节点的最大存储能力如能存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内的所有块都进行1Si,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体现了这个需求。
