一、LRU算法
1.1 背景
目前尽量由于摩尔定律,但是在存储硬件方面始终存在着差异,并且这种差异是不在同一数量级别的区别,例如在容量方面,内存<<外存;而在硬件成本与访问效率方面,内存>>外存。而目前互联网服务平台存在的特点:
a. 读多写少,快速ms级响应,因此需要把数据搁在内存上;
b. 数据规模巨大,长尾效应,由于数据规模巨大,只能把全量数据搁在外存上。正是由于服务场景需求与存储硬件特征之间的本身矛盾,缓存及相应的淘汰算法由此产生了:
一个在线服务平台其读取数据的过程:总是优先去离CPU最近的地方内存中读取数据,当有限的内存容量空间读取命中为空被击穿时,则会去外存的数据库或文件系统中读取;而当有限的缓存空间里“人满为患”时,而又有新的热点成员需要加入时,自然需要一定的淘汰机制。本能的基础淘汰算法:最后访问时间最久的成员最先会被淘汰(LRU)。
1.2 基本原理
由于队列具有先进先出的操作特点,所以通常用队列实现LRU,按最后访问的时间先进先出。
a. 利用队列类型对象,记录最近操作的元素,总是放在队首,这样最久未操作的元素自然被相对移动到队尾;同时,当元素总数达到上限值时,优先移除与淘汰队尾元素。
b. 利用HashMap辅助对象,快速检索队列中存在的元素。
1.3 操作
a. 写入操作: 新建一个元素,把元素插入队列首,当元素总和达到上限值时,同时删除队尾元素。
b. 读取操作:利用map快速检索,队列相关联的元素。
1.4 实现源码
1.4.1 自定义链表方式
1 #pragma once 2 #ifndef LRU_h_ 3 #define LRU_h_ 4 5 #include <unordered_map> 6 #include <vector> 7 8 using namespace std; 9 10 struct Node { 11 int val; 12 int key; 13 Node* next; 14 Node* prev; 15 Node(int v = 0, int k = 0) : val(v), key(k), next(nullptr), prev(nullptr) {} 16 }; 17 class Solution { 18 public: 19 /** 20 * lru design 21 * @param operators int整型vector<vector<>> the ops 22 * @param k int整型 the k 23 * @return int整型vector 24 */ 25 vector<int> LRU(vector<vector<int> >& operators, int k) { 26 // write code here 27 cap = k; 28 cursize = 0; 29 int len = operators.size(); 30 head = nullptr; 31 tail = nullptr; 32 33 vector<int> ans; 34 for (int i = 0; i < len; i++) 35 { 36 int opt = operators[i][0]; 37 int key = operators[i][1]; 38 if (opt == 1) 39 { 40 int value = operators[i][2]; 41 if (mp.count(key)) 42 { 43 Node* node = mp[key]; 44 node->val = value; 45 Move_to_head(node); 46 } 47 else 48 { 49 Node* node = new Node(value, key); 50 add_to_head(node); 51 mp[key] = node; 52 cursize++; 53 while (cursize > cap) 54 { 55 Node* temp = tail; 56 remove_tail(); 57 mp.erase(temp->key); 58 delete temp; 59 cursize--; 60 } 61 } 62 } 63 else 64 { 65 if (mp.count(key)) 66 { 67 Node* node = mp[key]; 68 ans.push_back(node->val); 69 Move_to_head(node); 70 } 71 else 72 { 73 ans.push_back(-1); 74 } 75 } 76 } 77 return ans; 78 } 79 80 void remove_tail() 81 { 82 if (tail == head) 83 { 84 tail = nullptr; 85 head = nullptr; 86 } 87 else 88 { 89 tail = tail->prev; 90 tail->next = nullptr; 91 } 92 } 93 94 void add_to_head(Node* node) 95 { 96 if (head == nullptr) 97 { 98 head = tail = node; 99 } 100 else 101 { 102 node->next = head; 103 node->prev = nullptr; 104 head->prev = node; 105 head = node; 106 } 107 } 108 109 void Move_to_head(Node* node) 110 { 111 if (node == head) 112 { 113 return; 114 } 115 else if (node == tail) 116 { 117 remove_tail(); 118 add_to_head(node); 119 } 120 else 121 { 122 node->prev->next = node->next; 123 node->next->prev = node->prev; 124 add_to_head(node); 125 } 126 } 127 128 129 private: 130 Node* head; 131 Node* tail; 132 std::unordered_map<int, Node*> mp; 133 int cap; 134 int cursize; 135 }; 136 137 #endif // !LRU_h_
1.4.2 采用stl::list类型实现方式
1 #include <iostream> 2 #include <list> 3 #include <ext/hash_map> 4 #include <stdint.h> 5 #include <string> 6 7 template<class T1, class T2> 8 class Lru 9 { 10 public: 11 typedef std::list<std::pair<T1, T2> > List; 12 typedef typename List::iterator iterator; 13 typedef __gnu_cxx::hash_map<T1, iterator> Map; 14 15 Lru() 16 { 17 size_ = 1000; 18 resize(size_); 19 } 20 21 ~Lru() 22 { 23 clear(); 24 } 25 26 void resize(int32_t size) 27 { 28 if (size > 0) 29 { 30 size_ = size; 31 } 32 } 33 34 T2* find(const T1& first) 35 { 36 typename Map::iterator i = index_.find(first); 37 38 if (i == index_.end()) 39 { 40 return NULL; 41 } 42 else 43 { 44 typename List::iterator n = i->second; 45 list_.splice(list_.begin(), list_, n); 46 return &(list_.front().second); 47 } 48 } 49 50 void remove(const T1& first) 51 { 52 typename Map::iterator i = index_.find(first); 53 if (i != index_.end()) 54 { 55 typename List::iterator n = i->second; 56 list_.erase(n); 57 index_.erase(i); 58 } 59 } 60 61 void insert(const T1& first, const T2& second) 62 { 63 typename Map::iterator i = index_.find(first); 64 if (i != index_.end()) 65 { // found 66 typename List::iterator n = i->second; 67 list_.splice(list_.begin(), list_, n); 68 index_.erase(n->first); 69 n->first = first; 70 n->second = second; 71 index_[first] = n; 72 } 73 else if (size() >= size_ ) 74 { // erase the last element 75 typename List::iterator n = list_.end(); 76 --n; // the last element 77 list_.splice(list_.begin(), list_, n); 78 index_.erase(n->first); 79 n->first = first; 80 n->second = second; 81 index_[first] = n; 82 } 83 else 84 { 85 list_.push_front(std::make_pair(first, second)); 86 typename List::iterator n = list_.begin(); 87 index_[first] = n; 88 } 89 } 90 91 /// Random access to items 92 iterator begin() 93 { 94 return list_.begin(); 95 } 96 97 iterator end() 98 { 99 return list_.end(); 100 } 101 102 int size() 103 { 104 return index_.size(); 105 } 106 107 // Clear cache 108 void clear() 109 { 110 index_.clear(); 111 list_.clear(); 112 } 113 114 private: 115 int32_t size_; 116 List list_; 117 Map index_; 118 }; 119 120 int main(void) 121 { 122 std::cout << "hello world " << std::endl; 123 tfs::Lru<uint32_t, std::string> name_cache; 124 name_cache.insert(1, "one"); 125 name_cache.insert(2, "two"); 126 127 std::string* value = name_cache.find(1); 128 const char* v = value->c_str(); 129 std::cout << "result of the key 1 is: " << *name_cache.find(1) << std::endl; 130 131 return 0; 132 }
二、LRFU缓存算法
2.1 前言
缓存算法有许多种,各种缓存算法的核心区别在于它们的淘汰机制。通常的淘汰机制:所有元素按某种量化的重要程度进行排序,分值最低者则会被优先淘汰。而重要程度的量化指标又通常可以参考了两个维度:最后被访问的时间和最近被访问的频率次数。依次例如如下:
1. LRU(Least Recently Used ),总是淘汰最后访问时间最久的元素。这种算法存在着问题:可能由于一次冷数据的批量查询而误淘汰大量热点的数据。
2. LFU(Least Frequently Used ),总是淘汰最近访问频率最小的元素。这种算法也存在明显的问题:
a. 如果频率时间度量是1小时,则平均一天每个小时内的访问频率1000的热点数据可能会被2个小时的一段时间内的访问频率是1001的数据剔除掉;
b. 最近新加入的数据总会易于被剔除掉,由于其起始的频率值低。
本质上其“重要性”指标访问频率是指在多长的时间维度进行衡量?其难以标定,所以在业界很少单一直接使用。也由于两种算法的各自特点及缺点,所以通常在生产线上会根据业务场景联合LRU与LFU一起使用,称之为LRFU。
2.2 实现机制
正是由于LRU与LFU算法各具特点,所以在行业生产线上通常会联合两者使用。我们可以在LRU的实现基础上稍作衍生,能实现LRFU缓存机制,即可以采用队列分级的思想,例如oracle利用两个队列维护访问的数据元素,按被访问的频率的维度把元素分别搁在热端与冷端队列;而在同一个队列内,最后访问时间越久的元素会越被排在队列尾。
2.3 实现
最重要的是数据节点需要重载<运算符,从而指定节点在set容器中的规则:先按频率大小进行升序排列,频率相同则按照访问时间先后进行排序。
1 #pragma once 2 #ifndef LFU_H_ 3 #define LFU_H_ 4 5 #include <unordered_map> 6 #include <set> 7 8 struct LFUnode 9 { 10 int cnt; 11 int time; 12 int key; 13 int value; 14 LFUnode(int _cnt = 0, int _time = 0, int _key = 0, int _value) : cnt(_cnt), time(_time), key(_key), value(_value) {} 15 16 bool operator<(const LFUnode item) const 17 { 18 return cnt == item.cnt ? time < item.time : cnt < item.cnt; 19 } 20 }; 21 22 23 class LFU 24 { 25 private: 26 int capacity; 27 int time; 28 std::unordered_map<int, LFUnode> keymp; 29 std::set<LFUnode> cntmp; 30 public: 31 LFU(int _capacity) : capacity(_capacity), time(0) 32 { 33 keymp.clear(); 34 cntmp.clear(); 35 } 36 37 int get(int key) 38 { 39 if (capacity == 0) 40 return -1; 41 auto item = keymp.find(key); 42 if (item == keymp.end()) 43 return -1; 44 LFUnode node = item->second; 45 cntmp.erase(node); 46 node.cnt++; 47 node.time = ++time; 48 cntmp.insert(node); 49 item->second = ndoe; 50 return node.value; 51 } 52 53 bool put(int key, int value) 54 { 55 if (capacity == 0) 56 return false; 57 auto item = keymp.find(key); 58 if (item == keymp.end()) 59 { 60 if (keymp.size() >= capacity) 61 { 62 keymp.erase(cntmp.begin()->key); 63 cntmp.erase(cntmp.begin()); 64 } 65 LFUnode node = LFUnode(1, ++time, key, value); 66 keymp.insert({ key, node }); 67 cntmp.insert(node); 68 } 69 else 70 { 71 LFUnode node = item->second; 72 cntmp.erase(node); 73 node.value = value; 74 node.time = ++time; 75 node.cnt++; 76 cntmp.insert(node); 77 item->second = node; 78 } 79 return true; 80 } 81 }; 82 83 #endif // !
三、参考文章
https://www.cnblogs.com/gisorange/p/4947868.html