本文代碼已上傳github，歡迎交流。

最近在學習go語言，正好有遇到需要使用緩存的地方，于是決定自己造個輪子。主要特性如下：

• 線程安全；
• 支持被動觸發(fā)的過期時間；
• 支持key和value任意類型；
• 基于雙向鏈表和hash表實現(xiàn)；

雙向鏈表的插入、刪除和元素移動效率非常高，LRU緩存通常都有大量的以上操作。使用hash表來存儲每個key對應的元素的指針，避免每次查詢緩存都需要遍歷整個鏈表，提高效率。

被動的過期的時間表示并不會主動的刪除緩存中已經(jīng)過期的元素，而是在需要使用的時候才去檢查是否過期，如果過期的話再去刪除。

數(shù)據(jù)結構

每個緩存的元素至少包含兩個：緩存的關鍵字key、緩存的數(shù)據(jù)data；為了支持過期時間，每個元素還要有一個值來表示其過期時間；另外基于雙向鏈表實現(xiàn)，還需要指向前一個元素和后一個元素的指針；于是，每個緩存元素的結構定義：

type elem struct {
    key        interface{}
    data       interface{}
    expireTime int64
    next       *elem
    pre        *elem
}

那么對于整個緩存來說，事實上就是一個個元素組成的列表，但是為了更高效的查詢，使用一個hash表來存放key對應的元素的指針，提升查詢效率，于是cache的結構定義：

type lrucache struct {
    maxSize   int
    elemCount int
    elemList  map[interface{}]*elem
    first     *elem
    last      *elem
    mu        sync.Mutex
}

保存鏈表首尾元素的指針是為了在淘汰元素和插入元素的時候更高效。

基本方法

一個緩存基本的方法應該包括新建緩存、添加元素、刪除元素、查詢元素。

新建緩存

新建一個緩存實際上就是新建一個lrucache結構體，并對里面的元素進行初始化：

// New create a new lrucache
// size: max number of element
func New(size int) (*lrucache, error) {
    newCache := new(lrucache)
    newCache.maxSize = size
    newCache.elemCount = 0
    newCache.elemList = make(map[interface{}]*elem)
    return newCache, nil
}

入?yún)⒈硎具@個緩存最多能存放的元素的個數(shù)，當?shù)竭_最大個數(shù)的時候就開始淘汰最久沒使用的元素。

添加元素

添加元素使用Set方法來實現(xiàn)，如果緩存中已經(jīng)存在該key，就更新值；否則新建一個緩存元素并保存。過期時間是可選的，如果沒傳入過期時間，這個元素就會一直存在知道被淘汰。

// Set create or update an element using key
//      key:    The identity of an element
//      value:  new value of the element
//      ttl:    expire time, unit: second
func (c *lrucache) Set(key interface{}, value interface{}, ttl ...int) error {

    // Ensure ttl are correct
    if len(ttl) > 1 {
        return errors.New("wrong para number, 2 or 3 expected but more than 3 received")
    }
    var elemTTL int64
    if len(ttl) == 1 {
        elemTTL = int64(ttl[0])
    } else {
        elemTTL = -1
    }

    c.mu.Lock()
    defer c.mu.Unlock()

    if e, ok := c.elemList[key]; ok {
        e.data = value
        if elemTTL == -1 {
            e.expireTime = elemTTL
        } else {
            e.expireTime = time.Now().Unix() + elemTTL
        }
        c.mvKeyToFirst(key)
    } else {
        if c.elemCount+1 > c.maxSize {
            if c.checkExpired() <= 0 {
                c.eliminationOldest()
            }
        }
        newElem := &elem{
            key:        key,
            data:       value,
            expireTime: -1,
            pre:        nil,
            next:       c.first,
        }
        if elemTTL != -1 {
            newElem.expireTime = time.Now().Unix() + elemTTL
        }
        if c.first != nil {
            c.first.pre = newElem
        }
        c.first = newElem
        c.elemList[key] = newElem

        c.elemCount++
    }
    return nil
}

如果一個key已經(jīng)存在就更新它所對應的值，并將這個key對應的元素移動到鏈表的最前面；如果key不存在就需要新建一個鏈表元素，流程如下：

新增key流程圖

由于采用的是過期時間是被動觸發(fā)的方式，因此在元素滿的時候并不能確定是否存在過期的元素，因此目前采用的方式是，當滿了之后每次新增元素就去遍歷的檢查一次過期的元素，時間復雜度為O(n)，感覺這種實現(xiàn)方式不太好，但是目前沒想到更好的實現(xiàn)方式。

上面使用到的內(nèi)部方法實現(xiàn)如下：

// updateKeyPtr 更新對應key的指針，放到鏈表的第一個
func (c *lrucache) mvKeyToFirst(key interface{}) {
    elem := c.elemList[key]
    if elem.pre == nil {
        // 當key是第一個元素時，不做動作
        return
    } else if elem.next == nil {
        // 當key不是第一個元素，但是是最后一個元素時，提到第一個元素去
        elem.pre.next = nil

        c.last = elem.pre

        elem.pre = nil
        elem.next = c.first
        c.first = elem

    } else {
        elem.pre.next = elem.next
        elem.next.pre = elem.pre

        elem.next = c.first
        elem.pre = nil
        c.first = elem
    }
}

func (c *lrucache) eliminationOldest() {
    if c.last == nil {
        return
    }
    if c.last.pre != nil {
        c.last.pre.next = nil
    }
    key := c.last.key
    c.last = c.last.pre
    delete(c.elemList, key)
}

func (c *lrucache) deleteByKey(key interface{}) {
    if v, ok := c.elemList[key]; ok {
        if v.pre == nil && v.next == nil {
            // 當key是第一個元素時，清空元素列表，充值指針和元素計數(shù)
            c.elemList = make(map[interface{}]*elem)
            c.elemCount = 0
            c.last = nil
            c.first = nil
            return
        } else if v.next == nil {
            // 當key不是第一個元素，但是是最后一個元素時,修改前一個元素的next指針并修改c.last指針
            v.pre.next = v.next
            c.last = v.pre
        } else if v.pre == nil {
            c.first = v.next
            c.first.pre = nil
        } else {
            // 中間元素，修改前后指針
            v.pre.next = v.next
            v.next.pre = v.pre
        }
        delete(c.elemList, key)
        c.elemCount--
    }
}

// 遍歷鏈表，檢查并刪除已經(jīng)過期的元素
func (c *lrucache) checkExpired() int {
    now := time.Now().Unix()
    tmp := c.first
    count := 0
    for tmp != nil {
        if tmp.expireTime != -1 && now > tmp.expireTime {
            c.deleteByKey(tmp.key)
            count++
        }
        tmp = tmp.next
    }
    return count
}

獲取元素

使用Get方法來獲取嘗試獲取一個緩存的元素，在獲取的時候同時會檢查是否過期，如果過期的話會返回響應的錯誤并刪掉該元素：

// Get Get the value of a cached element by key. If key do not exist, this function will return nil and a error msg
//      key:    The identity of an element
//      return:
//          value:  the cached value, nil if key do not exist
//          err:    error info, nil if value is not nil
func (c *lrucache) Get(key interface{}) (value interface{}, err error) {
    if v, ok := c.elemList[key]; ok {
        if v.expireTime != -1 && time.Now().Unix() > v.expireTime {
            // 如果過期了
            c.deleteByKey(key)
            return nil, errors.New("the key was expired")
        }
        c.mvKeyToFirst(key)
        return v.data, nil
    }
    return nil, errors.New("no value found")
}

刪除元素

刪除元素通過Delete來實現(xiàn)，實際上在之前的內(nèi)部方法中已經(jīng)實現(xiàn)了刪除一個元素的功能，只需要封裝給外部調用即可:

// Delete delete an element
func (c *lrucache) Delete(key interface{}) error {
    c.mu.Lock()
    defer c.mu.Unlock()
    if _, ok := c.elemList[key]; !ok {
        return errors.New(fmt.Sprintf("key %T do not exist", key))
    }
    c.deleteByKey(key)
    return nil
}

算是熟悉了go語言的基本使用，但是還有很多需要優(yōu)化的地方，比如優(yōu)化Set方法的效率，使用讀寫鎖替換互斥鎖。。。。
歡迎討論。