探索c#之storm的TimeCacheMap

阅读目录:

  1. 概述
  2. 算法介绍
  3. 清理线程
  4. 获取、插入、删除
  5. 总结

概述

最近在看storm,发现其中的TimeCacheMap算法设计颇为高效,就简单分享介绍下。 思考一下如果需要一个带过期淘汰的缓存容器,我们通常会使用定时器或线程去扫描容器,以便判断是否过期从而删除。但这样性能并不友好,在数据量较大时O(n)检查是一笔不小的开销,并且在大量过期数据删除时需要频繁对容器加锁,这会多少会影响到正常的数据读写删除。 Storm设计了一种比较高效的时间缓存容器TimeCacheMap,它的算法可以在某个时间周期内将数据批量删除,一次批量删除只需要加一次锁即可,并且其读写删除复杂度均为O(1)。

算法介绍

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是清理线程。 在缓存初始化的时候,会实例三个空桶加入到buckets,清理线程开始启动循环检查,假设过期时间时30秒,桶的数量为3,当有新数据进来时,会全部加入到第一个桶中。

为了删除性能,清理线程会定期把整个桶给删除掉,一般我们会每次把链表中最后一个桶给清理掉,然后再加入一个新桶到链表头部。 这种情况下就不能按照缓存过期时间去触发线程清理了,因为有三个桶,如果每30秒触发线程清理掉最后一个桶,那么第三个桶要等到第90秒才开始清理,很明显这样是不合理的。 正确的应该是第30秒开始清理,这时就需要调整线程触发时间,比如调整成10秒,继续模拟下:

  1. 触发前1秒插入新数据到第一个桶,如果调整成10秒触发,等到触发删除这个桶时才过了20秒,跟缓存过期时间30秒不一致同样不合理,不管是1秒还是9秒都会导致提前删除数据,需要继续调整触发时间。
  2. 如上缓存提前删除不能允许的,但延迟删除一般是可以接受的,因此可以加入一些冗余时间来保证不会提前删除。 这里调整到15秒触发,触发前1秒插入的缓存桶正好在30秒后触发删除,达到不会提前删除的目的。
  3. 如上在触发前14秒插入数据,那就需要过了30秒+14秒才能删除。

根据上面的模拟,调整到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();
    }

代码执行步骤:

  1. 初始化桶加入到链表
  2. 计算缓存数据最长过期时间,并作为线程休眠的时间。
  3. 线程触发时删除最后一个桶并加入新的桶
  4. 不断循环休眠触发触发
  5. 启动线程

整个桶的数据删除只需要加一次锁即可,保证其高效。

获取、插入、删除

遍历整个链表,查询到第一个满足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算法优化缓存容器的过期,有兴趣的童鞋可以看看。 完整代码中有容器Size、ContainsKey的实现,github-TimeCacheMap.c#。 在storm中,spout发射的消息和acker的消息即保存在各自的TimeCacheMap里,如果消息超时后会自动通知spout的fail方法。 在storm0.8后TimeCacheMap被弃用了,使用的是新的RotatingMap,但设计和实现基本没变,github-TimeCacheMap.javagithub-RotatingMap.java

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏spring源码深度学习

重拾python爬虫之urllib

学习一门技术,总是要踩好多坑,然后收货一大堆疑惑,这么多相似的方式该学哪个呢?外面公司常用的是哪个呢? 就比如python爬虫,可以作为网络请求的方式有四种,...

14520
来自专栏张善友的专栏

Contact Manager Web API 示例[2] Web API Routing

联系人管理器web API是一个Asp.net web api示例程序,演示了通过ASP.NET Web API 公开联系信息,并允许您添加和删除联系人,示例地...

19190
来自专栏码农阿宇

asp.net core轻松入门之MVC中Options读取配置文件

接上一篇中讲到利用Bind方法读取配置文件 ASP.NET Core轻松入门Bind读取配置文件到C#实例 那么在这篇文章中,我将在上一篇文章的基础上,利...

26640
来自专栏农夫安全

代码审计入门总结

0x00 简介 ---- 之前看了seay写的PHP代码审计的书,全部浏览了一遍,作为一个代码审计小白,希望向一些和我一样的小白的人提供一下我的收获,以及一个整...

36970
来自专栏小狼的世界

Python3.6学习笔记(五)

网络程序出现的比互联网要早很多,实现方式主要依靠网络上不同主机间进程的通信,通信协议最重要的是TCP/IP协议。在这两个协议基础上还有很多更高级的协议,包括HT...

14720
来自专栏13blog.site

Spring+SpringMVC+MyBatis+easyUI整合基础篇(八)mysql中文查询bug修复

前言   在测试搜索时出现的问题,mysql通过中文查询条件搜索不出数据,但是英文和数字可以搜索到记录,中文无返回记录。本文就是写一下发现问题的过程及解决方法...

34550
来自专栏大内老A

WCF技术剖析之二十三:服务实例(Service Instance)生命周期如何控制[上篇]

服务调用的目的体现在对某项服务功能的消费上,而功能的实现又定义在相应的服务类型中。不论WCF服务端框架处理服务调用请求的流程有多么复杂,最终都落实在服务实例的激...

25080
来自专栏H2Cloud

C++任务队列与多线程

摘要:       很多场合之所以使用C++,一方面是由于C++编译后的native code的高效性能,另一方面是由于C++优秀的并发能力。并行方式有多进程 ...

71740
来自专栏前端之心

为什么全球只有13组根域名服务器?

根域名服务器是域名解析系统(DNS)中最为顶级的域名服务器,它们负责管理顶级域的权威域名服务器地址。作为互联网基础设施的重要部分,所有域名的解析操作均离不开它们...

91270
来自专栏张善友的专栏

Contact Manager Web API 示例[2] Web API Routing

联系人管理器web API是一个Asp.net web api示例程序,演示了通过ASP.NET Web API 公开联系信息,并允许您添加和删除联系人,示例地...

20360

扫码关注云+社区

领取腾讯云代金券