偷偷摘套内射激情视频,久久精品99国产国产精,中文字幕无线乱码人妻,中文在线中文a,性爽19p

討論一下LRU緩存的實現(xiàn)算法

作者：蛙蛙
開發(fā) 開發(fā)工具 算法
本文將討論一下LRU緩存的實現(xiàn)算法，LRU是Least Recently Used最近最久未使用算法。Oracle系統(tǒng)使用的一種算法,對于在內(nèi)存中但最近又不用的數(shù)據(jù)塊(內(nèi)存塊)叫做LRU。

業(yè)務(wù)模型

讀、寫、刪的比例大致是7:3:1，至少要支持500w條緩存，平均每條緩存6k，要求設(shè)計一套性能比較好的緩存算法。

算法分析

不考慮MemCached，Velocity等現(xiàn)成的key-value緩存方案，也不考慮脫離.NET gc自己管理內(nèi)存,不考慮隨機讀取數(shù)據(jù)及順序讀取數(shù)據(jù)的場景，目前想到的有如下幾種LRU緩存方案

算法

分析

SortedDictionary

.NET自帶的，內(nèi)部用二叉搜索樹（應(yīng)該不是普通樹，至少是做過優(yōu)化的樹）實現(xiàn)的，檢索為O(log n)，比普通的Dictionay（O(1)）慢一點。
插入和刪除都是O(log n)，而且插入和刪除，會實時排序。
但是.NET 2.0的這個類沒有First屬性

Dictionary + PriorityQueue

Dictionay可以保證檢索是O(1)；
優(yōu)先隊列可以保證插入和刪除都為O(log n)；
但是優(yōu)先隊列刪除指定的項不支持（至少我找到的優(yōu)先隊列不支持），所以在刪除緩存的時候不知道咋實現(xiàn)

Dictionay + Binary heap

二叉堆也是優(yōu)先隊列，分析應(yīng)該同上，我沒有詳細評估。

b樹

查找，刪除，插入效率都很好，數(shù)據(jù)庫都用它，但實現(xiàn)復(fù)雜，寫一個沒有BUG的B樹幾乎不可能。有人提到stl:map是自頂向下的紅黑樹，查找，刪除，插入都是O(log n)，但咱不懂c++，沒做詳細測試。

Dictionay + List

Dict用來檢索；
List用來排序；
檢索、添加、刪除都沒問題，只有在清空的時候需要執(zhí)行List的排序方法，這時候緩存條目比較多的話，可能比較慢。

Dictionay + LinkedList

Dict用來檢索；
LinkedList的添加和刪除都是O(1)，添加緩存時在鏈表頭加節(jié)點，獲取緩存時把特定節(jié)點移動（先刪除特定節(jié)點(O(n))，再到頭部添加節(jié)點(O(1))）到頭，緩存滿地時候截斷掉尾部的一些節(jié)點。

目前幾種方案在多線程下應(yīng)該都需要加鎖，不太好設(shè)計無鎖的方案，下面這個鏈接是一個支持多線程的方案，但原理至今沒搞特明白

A High Performance Multi-Threaded LRU Cache
http://www.codeproject.com/KB/recipes/LRUCache.aspx

用普通鏈表簡單實現(xiàn)LRU緩存

以下是最后一種方案的簡單實現(xiàn)，大家討論下這個方案值不值得優(yōu)化，或者其它的哪個方案比較合適 

  1. public class LRUCacheHelper {  
  2.     readonly Dictionary _dict;  
  3.     readonly LinkedList _queue = new LinkedList();  
  4.     readonly object _syncRoot = new object();  
  5.     private readonly int _max;  
  6.     public LRUCacheHelper(int capacity, int max) {  
  7.         _dict = new Dictionary(capacity);  
  8.         _max = max;  
  9.     }  
  10.    
  11.     public void Add(K key, V value) {  
  12.         lock (_syncRoot) {  
  13.             checkAndTruncate();  
  14.             _queue.AddFirst(key);   //O(1)  
  15.             _dict[key] = value;     //O(1)  
  16.         }  
  17.     }  
  18.    
  19.     private void checkAndTruncate() {  
  20.         lock (_syncRoot) {  
  21.             int count = _dict.Count;                        //O(1)  
  22.             if (count >= _max) {  
  23.                 int needRemoveCount = count / 10;  
  24.                 for (int i = 0; i < needRemoveCount; i++) {  
  25.                     _dict.Remove(_queue.Last.Value);        //O(1)  
  26.                     _queue.RemoveLast();                    //O(1)  
  27.                 }  
  28.             }  
  29.         }  
  30.     }  
  31.    
  32.     public void Delete(K key) {  
  33.         lock (_syncRoot) {  
  34.             _dict.Remove(key); //(1)  
  35.             _queue.Remove(key); // O(n)  
  36.         }  
  37.     }  
  38.     public V Get(K key) {  
  39.         lock (_syncRoot) {  
  40.             V ret;  
  41.             _dict.TryGetValue(key, out ret);    //O(1)  
  42.             _queue.Remove(key);                 //O(n)  
  43.             _queue.AddFirst(key);               //(1)  
  44.             return ret;  
  45.         }  
  46.     }  
  47. }  
用雙頭鏈表代替普通鏈表
 
突然想起來了，可以把鏈表換成雙頭鏈表，然后在字典里保存鏈表節(jié)點，在Get方法的時候直接從字典里獲取到要移動的節(jié)點，然后把這個節(jié)點的上一個節(jié)點的Next指針指向給下一個節(jié)點，下一個節(jié)點的Previous指針指向上一個節(jié)點，這樣就把移動節(jié)點的操作簡化成O(1)了，提高了緩存讀取的效率。

_dict.TryGetValue(key, out ret);    //O(1)
ret.Next.Previous = ret.Previous     //O(1)
ret. Previous.Next. = ret.Next         //O(1)
  _queue.AddFirst(key);                      //O(1)

我改進后的鏈表就差不多滿足需求了，

操作

基本操作

復(fù)雜度

讀取

Dict.Get

Queue.Move

O 1

O 1

刪除

Dict.Remove

Queue.Remove

O 1

O 1

增加

Dict.Add

Queue.AddFirst

O 1

O 1

截斷

Dict.Remove

Queue.RemoveLast

O k

O k

K表示截斷緩存元素的個數(shù)

其中截斷的時候可以指定當緩存滿的時候截斷百分之多少的最少使用的緩存項。

其它的就是多線程的時候鎖再看看怎么優(yōu)化，字典有線程安全的版本，就把.NET 3.0的讀寫鎖扣出來再把普通的泛型字典保證成ThreadSafelyDictionay就行了，性能應(yīng)該挺好的。

鏈表的話不太好用讀寫鎖來做線程同步，大不了用互斥鎖，但得考慮下鎖的粒度，Move,AddFirst,RemoveLast的時候只操作一兩個節(jié)點，是不是想辦法只lock這幾個節(jié)點就行了，Truncate的時候因為要批量操作很多節(jié)點，所以要上個大多鏈表鎖，但這時候怎么讓其它操作停止得考慮考慮，類似數(shù)據(jù)庫的表鎖和行鎖。

LRU緩存實現(xiàn)代碼

  1. public class DoubleLinkedListNode {  
  2.     public T Value { get; set; }  
  3.    
  4.     public DoubleLinkedListNode Next { get; set; }  
  5.    
  6.     public DoubleLinkedListNode Prior { get; set; }  
  7.    
  8.     public DoubleLinkedListNode(T t) { Value = t; }  
  9.    
  10.     public DoubleLinkedListNode() { }  
  11.    
  12.     public void RemoveSelf() {  
  13.         Prior.Next = Next;  
  14.         Next.Prior = Prior;  
  15.     }  
  16.    
  17. }  
  18. public class DoubleLinkedList {  
  19.     protected DoubleLinkedListNode m_Head;  
  20.     private DoubleLinkedListNode m_Tail;  
  21.    
  22.     public DoubleLinkedList() {  
  23.         m_Head = new DoubleLinkedListNode();  
  24.         m_Tail = m_Head;  
  25.     }  
  26.    
  27.     public DoubleLinkedList(T t)  
  28.         : this() {  
  29.         m_Head.Next = new DoubleLinkedListNode(t);  
  30.         m_Tail = m_Head.Next;  
  31.         m_Tail.Prior = m_Head;  
  32.     }  
  33.    
  34.     public DoubleLinkedListNode Tail {  
  35.         get { return m_Tail; }  
  36.     }  
  37.    
  38.     public DoubleLinkedListNode AddHead(T t) {  
  39.         DoubleLinkedListNode insertNode = new DoubleLinkedListNode(t);  
  40.         DoubleLinkedListNode currentNode = m_Head;  
  41.         insertNode.Prior = null;  
  42.         insertNode.Next = currentNode;  
  43.         currentNode.Prior = insertNode;  
  44.         m_Head = insertNode;  
  45.         return insertNode;  
  46.     }  
  47.     public void RemoveTail() {  
  48.         m_Tail = m_Tail.Prior;  
  49.         m_Tail.Next = null;  
  50.         return;  
  51.     }  
  52. }  
  53. public class LRUCacheHelper {  
  54.     class DictItem {  
  55.         public DoubleLinkedListNode Node { get; set; }  
  56.         public V Value { get; set; }  
  57.     }  
  58.     readonly Dictionary _dict;  
  59.     readonly DoubleLinkedList _queue = new DoubleLinkedList();  
  60.     readonly object _syncRoot = new object();  
  61.     private readonly int _max;  
  62.     public LRUCacheHelper(int capacity, int max) {  
  63.         _dict = new Dictionary(capacity);  
  64.         _max = max;  
  65.     }  
  66.    
  67.     public void Add(K key, V value) {  
  68.         lock (this)  
  69.         {  
  70.    
  71.             checkAndTruncate();  
  72.             DoubleLinkedListNode v = _queue.AddHead(key);   //O(1)  
  73.             _dict[key] = new DictItem() { Node = v, Value = value }; //O(1)  
  74.         }  
  75.     }  
  76.    
  77.     private void checkAndTruncate() {  
  78.         int count = _dict.Count;                        //O(1)  
  79.         if (count >= _max) {  
  80.             int needRemoveCount = count / 10;  
  81.             for (int i = 0; i < needRemoveCount; i++) {  
  82.                 _dict.Remove(_queue.Tail.Value);        //O(1)  
  83.                 _queue.RemoveTail();                    //O(1)  
  84.             }  
  85.         }  
  86.     }  
  87.    
  88.     public void Delete(K key) {  
  89.         lock (this) {  
  90.             _dict[key].Node.RemoveSelf();  
  91.             _dict.Remove(key); //(1)   
  92.         }  
  93.     }  
  94.     public V Get(K key) {  
  95.         lock (this) {  
  96.             DictItem ret;  
  97.             if (_dict.TryGetValue(key, out ret)) {  
  98.                 ret.Node.RemoveSelf();  
  99.                 _queue.AddHead(key);  
  100.                 return ret.Value;  
  101.             }  
  102.             return default(V);   
  103.         }  
  104.     }  
  105. } 
 
LRU緩存性能測試

用雙頭鏈表測試了一下，感覺性能還可以接受，每秒鐘讀取可達80多w，每秒鐘寫操作越20多w。

程序初始化200w條緩存，然后不斷的加，每加到500w，截斷掉10分之一，然后繼續(xù)加。

測試模型中每秒鐘的讀和寫的比例是7:3，以下是依次在3個時間點截取的性能計數(shù)器圖。
圖1

性能計數(shù)器圖1

圖2

性能計數(shù)器圖2


圖3

性能計數(shù)器圖3


內(nèi)存最高會達到1g，cpu也平均百分之90以上，但測試到后期會發(fā)現(xiàn)每隔一段時間，就會有一兩秒，吞吐量為0，如最后一張截圖，后來觀察發(fā)現(xiàn)，停頓的那一兩秒是二代內(nèi)存在回收，等不停頓的時候# gen 2 collections就會加1，這個原因應(yīng)該是鏈表引起的，對鏈表中節(jié)點的添加和刪除是很耗費GC的，因為會頻繁的創(chuàng)建和銷毀對象。 

LRU緩存后續(xù)改進

1、 用游標鏈表來代替普通的雙頭鏈表，程序起來就收工分配固定大小的數(shù)組，然后用數(shù)組的索引來做鏈表，省得每次添加和刪除節(jié)點都要GC的參與，這相當于手工管理內(nèi)存了，但目前我還沒找到c#合適的實現(xiàn)。

 

2、 有人說鏈表不適合用在多線程環(huán)境中，因為對鏈表的每個操作都要加互斥鎖，連讀寫鎖都用不上，我目前的實現(xiàn)是直接用互斥鎖做的線程同步，每秒的吞吐量七八十萬，感覺lock也不是瓶頸，如果要改進的話可以把Dictionary用ThreadSafelyDictionary來代替，然后鏈表還用互斥鎖（剛開始設(shè)想的鏈表操作只鎖要操作的幾個節(jié)點以降低并發(fā)沖突的想法應(yīng)該不可取，不嚴謹）。

3、 還有一個地方就是把鎖細分以下，鏈表還用鏈表，但每個鏈表的節(jié)點是個HashSet，對HashSet的操作如果只有讀，寫，刪，沒有遍歷的話應(yīng)該不需要做線程同步（我感覺不用，因為Set就是一個集合，一個線程往里插入，一個線程往里刪除，一個線程讀取應(yīng)該沒問題，頂多讀進來的數(shù)據(jù)可能馬上就刪除了，而整個Set的結(jié)構(gòu)不會破壞）。然后新增數(shù)據(jù)的時候往鏈表頭頂Set里插入，讀取某個數(shù)據(jù)的時候把它所在的節(jié)點的Set里刪除該數(shù)據(jù)，然后再鏈表頭的Set里插入一個數(shù)據(jù)，這樣反復(fù)操作后，鏈表的最后一個節(jié)點的Set里的數(shù)據(jù)都是舊數(shù)據(jù)了，可以安全的刪除了，當然這個刪除的時候應(yīng)該是要鎖整個鏈表的。每個Set應(yīng)該有個大小上限，比如20w，但set不能安全的遍歷，就不能得到當前大小，所以添加、刪除Set的數(shù)據(jù)的時候應(yīng)該用Interlocked.Decrement()和 Interlocked.Increment()維護一個Count，一遍一個Set滿的時候，再到鏈表的頭新增一個Set節(jié)點。

LRU緩存性能測試腳本

  1. class Program {  
  2.     private static PerformanceCounter _addCounter;  
  3.     private static PerformanceCounter _getCounter;  
  4.    
  5.     static void Main(string[] args) {  
  6.         SetupCategory();  
  7.         _addCounter = new PerformanceCounter("wawasoft.lrucache", "add/sec", false);  
  8.         _getCounter = new PerformanceCounter("wawasoft.lrucache", "get/sec", false);  
  9.         _addCounter.RawValue = 0;  
  10.         _getCounter.RawValue = 0;  
  11.    
  12.         Random rnd = new Random();  
  13.         const int max = 500 * 10000;  
  14.    
  15.    
  16.         LRUCacheHelper<int, int> cache = new LRUCacheHelper<int, int>(200 * 10000, max);  
  17.    
  18.         for (int i = 10000*100000 - 1; i >= 0; i--)  
  19.         {  
  20.             if(i % 10 > 7)  
  21.             {  
  22.                 ThreadPool.QueueUserWorkItem(  
  23.                     delegate  
  24.                         {  
  25.                             cache.Add(rnd.Next(0, 10000), 0);  
  26.                             _addCounter.Increment();   
  27.                         });  
  28.             }  
  29.             else 
  30.             {  
  31.                 ThreadPool.QueueUserWorkItem(  
  32.                    delegate  
  33.                    {  
  34.                        int pop = cache.Get(i);  
  35.                        _getCounter.Increment();  
  36.                    });  
  37.             }  
  38.         }  
  39.         Console.ReadKey();  
  40.     }  
  41.    
  42.     private static void SetupCategory() {  
  43.         if (!PerformanceCounterCategory.Exists("wawasoft.lrucache")) {  
  44.    
  45.             CounterCreationDataCollection CCDC = new CounterCreationDataCollection();  
  46.    
  47.             CounterCreationData addcounter = new CounterCreationData();  
  48.             addcounter.CounterType = PerformanceCounterType.RateOfCountsPerSecond32;  
  49.             addcounter.CounterName = "add/sec";  
  50.             CCDC.Add(addcounter);  
  51.    
  52.    
  53.             CounterCreationData getcounter = new CounterCreationData();  
  54.             getcounter.CounterType = PerformanceCounterType.RateOfCountsPerSecond32;  
  55.             getcounter.CounterName = "get/sec";  
  56.             CCDC.Add(getcounter);  
  57.    
  58.             PerformanceCounterCategory.Create("wawasoft.lrucache","lrucache",CCDC);  
  59.    
  60.         }  
  61.     }  
  62.    
  63. } 

【編輯推薦】

  1. .net緩存應(yīng)用與分析
  2. Hibernate緩存機制探討
  3. 充分利用ASP.NET的三種緩存提高站點性能
  4. ASP.NET緩存使用中的幾點建議
  5. 緩存設(shè)計詳解：低成本的高性能Web應(yīng)用解決方案
責任編輯：彭凡 來源： cnblogs
LRU緩存
相關(guān)推薦

2009-07-06 13:23:12

C#面向集合

2020-07-29 10:20:28

Redis數(shù)據(jù)庫字符串

2022-06-17 07:49:14

緩存LRU

2022-03-08 08:02:44

Java系統(tǒng)錯誤碼

2020-10-30 11:30:15

Least Recen

2020-02-19 19:18:02

緩存查詢速度淘汰算法

2015-07-29 10:31:16

Java緩存算法

2023-04-14 07:34:19

2022-03-31 09:13:49

Cache緩存高并發(fā)

2021-07-26 21:15:10

LRU緩存MongoDB

2021-05-18 08:31:46

緩存HTTP服務(wù)器

2023-09-12 14:56:13

MyBatis緩存機制

2023-07-06 12:39:14

RedisLRULFU

2025-03-10 07:05:07

2024-09-19 09:30:39

緩存框架抽象

2015-07-15 10:19:16

Java代碼使用緩存

2020-09-18 10:31:47

LRU算法數(shù)組

2023-09-06 07:58:45

數(shù)據(jù)緩存Redis

2020-07-30 07:58:36

加密算法

2024-03-15 07:17:51

MySQLLRU算法緩存池
點贊
收藏

51CTO技術(shù)棧公眾號