缓存冷热数据 ——C#实现
最近做项目时需要实现数据冷热分离功能，现在的NOSQL框架（redis，memcached，mongodb）均已实现了这个功能，直接拿过来用就Ok了，（知其然还要知其所以然吧，呵呵）
分析如下：
这个功能核心词：“最近（远）最少使用的缓存项”移除缓存就OK了。
A.最近（远）：第一感觉不就是时间排序（正序，倒序）么。
B.最少使用：就是缓存项的get频率了 。
C.这个功能的理论支撑就是大名鼎鼎的LRU算法了，核心思想：“ 在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。反过来说，已经很久没有使用的 页面很可能在未来较长的一段时间内不会被用到。这个，就是著名的局部性原理——比内存速度还要快的 cache，也是基于同样的原理运行的。因此，我们只需要在每次 调换时，找到最近最少使用的那个页面调出内存 ” ，这个算法的详细介绍网上都有我也不贴了。
实现：
A. 最近（远），实现方式有这么几种：
1），排序最快的当然是快速排序了，快速排序的时间复杂度：平均O（nlogn），最坏O（n^2），在一个大访问量的站点实时运用这个排序可行性不高；
2），顺序添加缓存项，自然而然老的数据就在前面新的数据就在后面了，可用的数据结构：数组，链表（单练，双链）我用链表，理由：链表，添加，删除都 为O(1)，添加Dictionary字典作辅助缓存管理器，弥补链表查找缺点（链表查找速度比较慢）
B.最少使用：get缓存项给个计数器 （这个计数器不是必须？原因：我们只要每次把get的缓存项添加到链表的最后面就可了，我添加计数器的理由是：使用频率超过既定值时再移动该缓存项，否则不移动。），当集合大小超过阀值要做的就是删除链表头部的缓存项就可以了。
C.结构图如下：
D.代码
1 internal class CacheItem<K, V>
2 {
3 public CacheItem(K k, V v)
4 {
5 UseCount = 0 ;
6 Key = k;
7 Value = v;
8 }
9
10 public int UseCount = 0 ;
11 public K Key;
12 public V Value;
13 }
14
15 // Hot and cold
16 public class HCCache<K, V>
17 {
18 private int maxSize;
19 private int hot;
20 private Dictionary<K, LinkedListNode<CacheItem<K, V>>> cacheDic;
21 private LinkedList<CacheItem<K, V>> chacheList;
22 private volatile bool init = false ;
23
24 public HCCache( int maxSize, int hot = 10 )
25 {
26 if (!init)
27 {
28 this .init = true ;
29 this .hot = hot;
30 this .maxSize = maxSize;
31 this .cacheDic = new Dictionary<K, LinkedListNode<CacheItem<K, V>>>(maxSize);
32 this .chacheList = new LinkedList<CacheItem<K, V>>();
33 }
34 }
35
36 public V Get(K key)
37 {
38 LinkedListNode<CacheItem<K, V>> node;
39 if (cacheDic.TryGetValue(key, out node)) // 0(1)
40 {
41 V value = node.Value.Value;
42 Interlocked.Add( ref node.Value.UseCount, 1 );
43 // node.Value.UseCount++; // 这里按需要可改为原子递增操作
44 if (node.Value.UseCount >= hot && node.Next != null )
45 {
46 lock (chacheList)
47 {
48 chacheList.Remove(node); // O(1)
49 chacheList.AddLast(node); // O(1)
50 }
51 Console.WriteLine( " 移动:{0} " , node.Value.Value);
52 }
53 Console.WriteLine( " {0}:，使用：{1},线程:{2} " , value, node.Value.UseCount,System.Threading.Thread.CurrentThread.Name);
54 return value;
55 }
56 return default (V);
57 }
58
59 public void Add(K key, V val)
60 {
61 if (cacheDic.Count >= maxSize)
62 {
63 RemoveOldItem();
64 }
65 CacheItem<K, V> cacheItem = new CacheItem<K, V>(key, val);
66 LinkedListNode<CacheItem<K, V>> node = new LinkedListNode<CacheItem<K, V>>(cacheItem);
67 chacheList.AddLast(node); // O(1)
68 cacheDic.Add(key, node); // 0(1) -->O(n);
69 }
70
71 public void ClearAll()
72 {
73 chacheList.Clear();
74 cacheDic.Clear();
75 init = false ;
76 }
77
78 private void RemoveOldItem()
79 {
80 lock (chacheList)
81 {
82 // 移除老的数据 链表头部都为老的数据
83 LinkedListNode<CacheItem<K, V>> node = chacheList.First;
84 if (node == null ) return ;
85 Console.WriteLine( " 移除：{0}使用:{1} " , node.Value.Value, node.Value.UseCount);
86 // chacheList.Remove(node);
87 chacheList.RemoveFirst();
88 cacheDic.Remove(node.Value.Key);
89 }
90
91 }
92 }
E.测试
1 // 初始化
2 HCCache< int , int > cache = new HCCache< int , int >( 100 );
3
4 var th1 = new System.Threading.Thread(() =>
5 {
6 for ( var i = 0 ; i < 200 ; i++)
7 {
8 cache.Add(i, i);
9 }
10 }) { IsBackground = true , Name = " add_th1 " };
11
12 var th2 = new System.Threading.Thread(() =>
13 {
14 for ( var i = 0 ; i < 5 ; i++)
15 {
16 var countLRU = 10 ; // r.Next(0, 200);
17 for ( var k = 0 ; k < countLRU; k++)
18 {
19 var item = cache.Get( 100 );
20 if (k == countLRU - 1 )
21 {
22 Console.WriteLine( " 获取:{0}, " , item);
23 }
24 }
25 }
26 }) { IsBackground = true , Name = " get_th2 " };
27
28 var th3 = new System.Threading.Thread(() =>
29 {
30 for ( var i = 0 ; i < 5 ; i++)
31 {
32 var countLRU = 10 ; // r.Next(0, 200);
33 for ( var k = 0 ; k < countLRU; k++)
34 {
35 var item = cache.Get( 101 );
36 if (k == countLRU - 1 )
37 {
38 Console.WriteLine( " 获取:{0}, " , item);
39 }
40 }
41 }
42 }) { IsBackground = true , Name = " get_th3 " };
43
44 // 启动
45 th1.Start();
46 th2.Start();
47 th3.Start();
48
49 // 等待完成
50 th1.Join();
51 th2.Join();
52 th3.Join();
53
54 Console.ReadLine();
F：这是个模拟缓存冷热分离实验，可以扩展的地方为：
1），冷数据的处理策略，删除亦或是移到其他介质中去而当前缓存只保留其引用 。
2），冷数据的判定标准。（我使用get平率，因为简单啊 ）
关于大数据同步，大家来发表高见吧 战锋 2011-10-28 11:02 阅读:2782 评论:10
作者： Leo_wl
出处： http://www.cnblogs.com/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息