本文代碼已上傳github隙赁，歡迎交流垦藏。
最近在學(xué)習(xí)go語言，正好有遇到需要使用緩存的地方伞访，于是決定自己造個(gè)輪子掂骏。主要特性如下：
- 線程安全；
- 支持被動(dòng)觸發(fā)的過期時(shí)間咐扭；
- 支持key和value任意類型芭挽；
- 基于雙向鏈表和hash表實(shí)現(xiàn)；
雙向鏈表的插入蝗肪、刪除和元素移動(dòng)效率非常高袜爪，LRU緩存通常都有大量的以上操作。使用hash表來存儲(chǔ)每個(gè)key對(duì)應(yīng)的元素的指針薛闪，避免每次查詢緩存都需要遍歷整個(gè)鏈表辛馆，提高效率。
被動(dòng)的過期的時(shí)間表示并不會(huì)主動(dòng)的刪除緩存中已經(jīng)過期的元素豁延，而是在需要使用的時(shí)候才去檢查是否過期昙篙，如果過期的話再去刪除。
數(shù)據(jù)結(jié)構(gòu)
每個(gè)緩存的元素至少包含兩個(gè)：緩存的關(guān)鍵字key诱咏、緩存的數(shù)據(jù)data苔可；為了支持過期時(shí)間，每個(gè)元素還要有一個(gè)值來表示其過期時(shí)間袋狞；另外基于雙向鏈表實(shí)現(xiàn)焚辅，還需要指向前一個(gè)元素和后一個(gè)元素的指針；于是苟鸯，每個(gè)緩存元素的結(jié)構(gòu)定義：
type elem struct {
key interface{}
data interface{}
expireTime int64
next *elem
pre *elem
}
那么對(duì)于整個(gè)緩存來說同蜻，事實(shí)上就是一個(gè)個(gè)元素組成的列表，但是為了更高效的查詢早处，使用一個(gè)hash表來存放key對(duì)應(yīng)的元素的指針湾蔓，提升查詢效率，于是cache的結(jié)構(gòu)定義：
type lrucache struct {
maxSize int
elemCount int
elemList map[interface{}]*elem
first *elem
last *elem
mu sync.Mutex
}
保存鏈表首尾元素的指針是為了在淘汰元素和插入元素的時(shí)候更高效砌梆。
基本方法
一個(gè)緩存基本的方法應(yīng)該包括新建緩存默责、添加元素贬循、刪除元素、查詢?cè)亍?/p>
新建緩存
新建一個(gè)緩存實(shí)際上就是新建一個(gè)lrucache結(jié)構(gòu)體傻丝，并對(duì)里面的元素進(jìn)行初始化：
// 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)⒈硎具@個(gè)緩存最多能存放的元素的個(gè)數(shù)甘有，當(dāng)?shù)竭_(dá)最大個(gè)數(shù)的時(shí)候就開始淘汰最久沒使用的元素。
添加元素
添加元素使用Set方法來實(shí)現(xiàn)葡缰，如果緩存中已經(jīng)存在該key，就更新值忱反；否則新建一個(gè)緩存元素并保存泛释。過期時(shí)間是可選的，如果沒傳入過期時(shí)間温算，這個(gè)元素就會(huì)一直存在知道被淘汰怜校。
// 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
}
如果一個(gè)key已經(jīng)存在就更新它所對(duì)應(yīng)的值，并將這個(gè)key對(duì)應(yīng)的元素移動(dòng)到鏈表的最前面注竿；如果key不存在就需要新建一個(gè)鏈表元素茄茁，流程如下：
由于采用的是過期時(shí)間是被動(dòng)觸發(fā)的方式，因此在元素滿的時(shí)候并不能確定是否存在過期的元素巩割，因此目前采用的方式是裙顽，當(dāng)滿了之后每次新增元素就去遍歷的檢查一次過期的元素，時(shí)間復(fù)雜度為O(n)宣谈，感覺這種實(shí)現(xiàn)方式不太好愈犹，但是目前沒想到更好的實(shí)現(xiàn)方式。
上面使用到的內(nèi)部方法實(shí)現(xiàn)如下：
// updateKeyPtr 更新對(duì)應(yīng)key的指針闻丑，放到鏈表的第一個(gè)
func (c *lrucache) mvKeyToFirst(key interface{}) {
elem := c.elemList[key]
if elem.pre == nil {
// 當(dāng)key是第一個(gè)元素時(shí)扩劝，不做動(dòng)作
return
} else if elem.next == nil {
// 當(dāng)key不是第一個(gè)元素炕檩，但是是最后一個(gè)元素時(shí)，提到第一個(gè)元素去
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 {
// 當(dāng)key是第一個(gè)元素時(shí)，清空元素列表扛禽，充值指針和元素計(jì)數(shù)
c.elemList = make(map[interface{}]*elem)
c.elemCount = 0
c.last = nil
c.first = nil
return
} else if v.next == nil {
// 當(dāng)key不是第一個(gè)元素，但是是最后一個(gè)元素時(shí),修改前一個(gè)元素的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方法來獲取嘗試獲取一個(gè)緩存的元素，在獲取的時(shí)候同時(shí)會(huì)檢查是否過期卑硫，如果過期的話會(huì)返回響應(yīng)的錯(cuò)誤并刪掉該元素：
// 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來實(shí)現(xiàn)徒恋，實(shí)際上在之前的內(nèi)部方法中已經(jīng)實(shí)現(xiàn)了刪除一個(gè)元素的功能，只需要封裝給外部調(diào)用即可:
// 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方法的效率，使用讀寫鎖替換互斥鎖硝拧。径筏。葛假。。
歡迎討論滋恬。
