阅读目录: 概述最近在看storm,发现其中的TimeCacheMap算法设计颇为高效,就简单分享介绍下。 算法介绍TimeCacheMap把要缓存的数据分拆存储到多个小容器内,这里称为桶。另外有个线程专门在一定时间内去扫描这些桶,一旦发现过期后就把整个桶的数据给删除掉。 其中第二步比较关键,它并不是传统意义上的去定时扫描,而是根据过期时间来触发,比如如果一个桶过期时间10s,那么这个线程就10秒触发一次把整个桶删除即可,当然多个桶的触发策略会有所不同,但思路是同一个。 private LinkedList<Dictionary<K, V>> buckets; private readonly object Obj = new object(); private static readonly int NumBuckets = 3; private Thread cleaner; 上面使用了k、v的形式作为缓存数据结构,每个Dictionary是一个桶,然后使用链表把多个桶存储起来。Obj是要锁的对象,NumBuckets是桶的数量,cleaner是清理线程。 为了删除性能,清理线程会定期把整个桶给删除掉,一般我们会每次把链表中最后一个桶给清理掉,然后再加入一个新桶到链表头部。
根据上面的模拟,调整到15秒触发是一个比较合理的值,因此推出缓存最长过期时间的公式为: expirationSecs * (1 + 1 / (numBuckets-1)) 如果过期时间是30秒,其最长删除时间是: 30*(1+1/(3-1))=30*(1+0.5)=45 因此其过期时间范围即为expirationSecs到expirationSecs * (1 + 1 / (numBuckets-1))之间。 清理线程如上算法的介绍,我们在类型的构造函数中,实例化并启动清理线程: public TimeCacheMap(int expirationSecs, int numBuckets, ExpiredCallBack ex) { if (numBuckets < 2) throw new ArgumentException("numBuckets must be >=2"); this.buckets = new LinkedList<Dictionary<K, V>>(); for (int i = 0; i < numBuckets; i++) buckets.AddFirst(new Dictionary<K, V>()); var expirationMillis = expirationSecs * 1000; var sleepTime = expirationMillis / (numBuckets - 1); cleaner = new Thread(() => { while (true) { Dictionary<K, V> dead = null; Thread.Sleep(sleepTime); lock (Obj) { dead = buckets.Last(); buckets.RemoveLast(); buckets.AddFirst(new Dictionary<K, V>()); } if (ex != null) ex(dead); } }); cleaner.IsBackground = true; cleaner.Start(); } 代码执行步骤:
整个桶的数据删除只需要加一次锁即可,保证其高效。 获取、插入、删除遍历整个链表,查询到第一个满足key的立即返回,这需要保证不会有重复key。 public V Get(K key) { lock (Obj) { foreach (var item in buckets) { if (item.ContainsKey(key)) return item[key]; } return default(V); } } 在插入时删除对应的key,保证不会有重复的key出现。 public void Put(K key, V value) { lock (Obj) { foreach (var item in buckets) { item.Remove(key); } buckets.First().Add(key, value); } } 删除对应的key public void Remove(K key) { lock (Obj) { foreach (var item in buckets) { if (item.ContainsKey(key)) item.Remove(key); } } } 总结在那些年我们一起追过的缓存写法(三)中有介绍过关于惰性删除及高效LRU算法优化缓存容器的过期,有兴趣的童鞋可以看看。 作者:蘑菇先生出处: http://mushroom.cnblogs.com/
本文版权归作者和博客园共有,欢迎转载。未经作者同意下,必须在文章页面明显标出原文链接及作者,否则保留追究法律责任的权利。 如果您认为这篇文章还不错或者有所收获,可以点击右下角的【推荐】按钮,因为你的支持是我继续写作,分享的最大动力! |
|
来自: 昵称10504424 > 《工作》