閱讀目錄：

1. 概述
2. 算法介紹
3. 清理線程
4. 獲取、插入、刪除
5. 總結(jié)

概述

最近在看storm，發(fā)現(xiàn)其中的TimeCacheMap算法設(shè)計(jì)頗為高效，就簡(jiǎn)單分享介紹下。
思考一下如果需要一個(gè)帶過(guò)期淘汰的緩存容器，我們通常會(huì)使用定時(shí)器或線程去掃描容器，以便判斷是否過(guò)期從而刪除。但這樣性能并不友好，在數(shù)據(jù)量較大時(shí)O(n)檢查是一筆不小的開銷，并且在大量過(guò)期數(shù)據(jù)刪除時(shí)需要頻繁對(duì)容器加鎖，這會(huì)多少會(huì)影響到正常的數(shù)據(jù)讀寫刪除。
Storm設(shè)計(jì)了一種比較高效的時(shí)間緩存容器TimeCacheMap，它的算法可以在某個(gè)時(shí)間周期內(nèi)將數(shù)據(jù)批量刪除，一次批量刪除只需要加一次鎖即可，并且其讀寫刪除復(fù)雜度均為O(1)。

算法介紹

TimeCacheMap把要緩存的數(shù)據(jù)分拆存儲(chǔ)到多個(gè)小容器內(nèi)，這里稱為桶。另外有個(gè)線程專門在一定時(shí)間內(nèi)去掃描這些桶，一旦發(fā)現(xiàn)過(guò)期后就把整個(gè)桶的數(shù)據(jù)給刪除掉。 其中第二步比較關(guān)鍵，它并不是傳統(tǒng)意義上的去定時(shí)掃描，而是根據(jù)過(guò)期時(shí)間來(lái)觸發(fā)，比如如果一個(gè)桶過(guò)期時(shí)間10s，那么這個(gè)線程就10秒觸發(fā)一次把整個(gè)桶刪除即可，當(dāng)然多個(gè)桶的觸發(fā)策略會(huì)有所不同，但思路是同一個(gè)。
為了更詳細(xì)的描述，用代碼和例子介紹如下：

    private LinkedList<Dictionary<K, V>> buckets;
    private readonly object Obj = new object();
    private static readonly int NumBuckets = 3;
    private Thread cleaner;

上面使用了k、v的形式作為緩存數(shù)據(jù)結(jié)構(gòu)，每個(gè)Dictionary是一個(gè)桶，然后使用鏈表把多個(gè)桶存儲(chǔ)起來(lái)。Obj是要鎖的對(duì)象，NumBuckets是桶的數(shù)量，cleaner是清理線程。
在緩存初始化的時(shí)候，會(huì)實(shí)例三個(gè)空桶加入到buckets，清理線程開始啟動(dòng)循環(huán)檢查，假設(shè)過(guò)期時(shí)間時(shí)30秒，桶的數(shù)量為3，當(dāng)有新數(shù)據(jù)進(jìn)來(lái)時(shí)，會(huì)全部加入到第一個(gè)桶中。

為了刪除性能，清理線程會(huì)定期把整個(gè)桶給刪除掉，一般我們會(huì)每次把鏈表中最后一個(gè)桶給清理掉，然后再加入一個(gè)新桶到鏈表頭部。
這種情況下就不能按照緩存過(guò)期時(shí)間去觸發(fā)線程清理了，因?yàn)橛腥齻€(gè)桶，如果每30秒觸發(fā)線程清理掉最后一個(gè)桶，那么第三個(gè)桶要等到第90秒才開始清理，很明顯這樣是不合理的。 正確的應(yīng)該是第30秒開始清理，這時(shí)就需要調(diào)整線程觸發(fā)時(shí)間，比如調(diào)整成10秒，繼續(xù)模擬下：

1. 觸發(fā)前1秒插入新數(shù)據(jù)到第一個(gè)桶，如果調(diào)整成10秒觸發(fā)，等到觸發(fā)刪除這個(gè)桶時(shí)才過(guò)了20秒，跟緩存過(guò)期時(shí)間30秒不一致同樣不合理，不管是1秒還是9秒都會(huì)導(dǎo)致提前刪除數(shù)據(jù)，需要繼續(xù)調(diào)整觸發(fā)時(shí)間。
2. 如上緩存提前刪除不能允許的，但延遲刪除一般是可以接受的，因此可以加入一些冗余時(shí)間來(lái)保證不會(huì)提前刪除。 這里調(diào)整到15秒觸發(fā)，觸發(fā)前1秒插入的緩存桶正好在30秒后觸發(fā)刪除，達(dá)到不會(huì)提前刪除的目的。
3. 如上在觸發(fā)前14秒插入數(shù)據(jù)，那就需要過(guò)了30秒+14秒才能刪除。

根據(jù)上面的模擬，調(diào)整到15秒觸發(fā)是一個(gè)比較合理的值，因此推出緩存最長(zhǎng)過(guò)期時(shí)間的公式為：

expirationSecs * (1 + 1 / (numBuckets-1))

如果過(guò)期時(shí)間是30秒，其最長(zhǎng)刪除時(shí)間是：

30*(1+1/(3-1))=30*(1+0.5)=45  

因此其過(guò)期時(shí)間范圍即為expirationSecs到expirationSecs * (1 + 1 / (numBuckets-1))之間。

清理線程

如上算法的介紹，我們?cè)陬愋偷臉?gòu)造函數(shù)中，實(shí)例化并啟動(dòng)清理線程：

 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();
    }

代碼執(zhí)行步驟：

1. 初始化桶加入到鏈表
2. 計(jì)算緩存數(shù)據(jù)最長(zhǎng)過(guò)期時(shí)間，并作為線程休眠的時(shí)間。
3. 線程觸發(fā)時(shí)刪除最后一個(gè)桶并加入新的桶
4. 不斷循環(huán)休眠觸發(fā)觸發(fā)
5. 啟動(dòng)線程

整個(gè)桶的數(shù)據(jù)刪除只需要加一次鎖即可，保證其高效。

獲取、插入、刪除

遍歷整個(gè)鏈表，查詢到第一個(gè)滿足key的立即返回，這需要保證不會(huì)有重復(fù)key。

   public V Get(K key)
        {
            lock (Obj)
            {
                foreach (var item in buckets)
                {
                    if (item.ContainsKey(key))
                        return item[key];
                }
                return default(V);
            }
        }

在插入時(shí)刪除對(duì)應(yīng)的key，保證不會(huì)有重復(fù)的key出現(xiàn)。

 public void Put(K key, V value)
    {
        lock (Obj)
        {
            foreach (var item in buckets)
            {
                item.Remove(key);
            }
            buckets.First().Add(key, value);
        }
    }

刪除對(duì)應(yīng)的key

    public void Remove(K key)
    {
        lock (Obj)
        {
            foreach (var item in buckets)
            {
                if (item.ContainsKey(key))
                    item.Remove(key);
            }
        }
    }

總結(jié)

在那些年我們一起追過(guò)的緩存寫法(三)中有介紹過(guò)關(guān)于惰性刪除及高效LRU算法優(yōu)化緩存容器的過(guò)期，有興趣的童鞋可以看看。
完整代碼中有容器Size、ContainsKey的實(shí)現(xiàn)，github-TimeCacheMap.c#。
在storm中，spout發(fā)射的消息和acker的消息即保存在各自的TimeCacheMap里，如果消息超時(shí)后會(huì)自動(dòng)通知spout的fail方法。 在storm0.8后TimeCacheMap被棄用了，使用的是新的RotatingMap，但設(shè)計(jì)和實(shí)現(xiàn)基本沒變，github-TimeCacheMap.java及github-RotatingMap.java。