缓存算法FIFO的说说

1 简介

盘算机科学范畴的任何题目都可以通过增加一个间接的中心层来办理，这句话就是整个盘算机软件以及体系设计中的核心思想，而缓存对这一思想的一种实践。
缓存，总归会受到存储空间的限定，当缓存的空间不敷的时间，如果在保持肯定体系文档的情况下，还能兼顾到缓存命中率呢？这就需要我们选择合适的缓存淘汰算法。
缓存淘汰算法种类比较多，我们本次重要介绍 FIFO：
先进先出，雷同队列的特性，淘汰缓存中最早添加的记载，该算法基于"最早被添加的数据，不再被使用的可能性最大"。要想实现这种算法，只需要使用一个队列维护数据，并同时维护一个数据最大容量，每次新增数据都添加到队尾，如果内存不够，那么就先淘汰掉队头的元素。
缺点：
FIFO 算法的缺点也很明显，有些数据固然被添加的比较早，但是使用频率也会很高，在这种计谋下会被频仍添加进去，过一会又被淘汰掉，缓存命中率不高。
2 核心原理

下面是一些设计的思路：

• 存储元素使用队列，并且队列容量有肯定限定。但是为了兼顾查询效率，需要同时使用哈希表来存储 key 和 Element 的映射。
  
• 为了删除的时间，能找到前后元素，队列需要维护成 双向队列。
  

根本操纵如下，为了处理并发时程序错误，需要在修改数据的时间加锁：

• Set ：先查找是否存在，分别实行两种操纵。
  
  
  
  • 新元素，追加在队尾。
    
  • 已存在的元素，直接修改。
    
  
  
• Get：
  
  
  
  • 按照 Key 在 Hash 表中查询出来。
    
  
  
• Delete：
  
  
  
  • 先查找到元素，然后从链表以及哈希表中删除，更新缓存状态。
    
  
  
• Stat：获取存储的状态
  

3 实现

3.1 使用自带的双向链表布局

本小节是最简单粗暴的实现，直接使用原生的双向队列，下面是一些设计的思路，仅供参考。
3.1.1 实体设计

3.1.2 缓存状态

缓存总的状态维护，定义一个 stat.go 类：

1. type Stat struct {  
2.    // key 的个数  
3.    keyCount int64  
4.    // value 使用得最大的容量  
5.    maxBytes int64  
6.    // value 已使用得最大的容量  
7.    usedBytes int64  
8. }

复制代码

3.1.3 核心接口

定义底子本领接口 cache.go，除了增编削查，另有获取缓存状态：

1.   
2. type Cache interface {  
3.    Set(key string, value []byte)  
4.    Get(key string) []byte  
5.    Del(key string)  
6.    Stat() Stat  
7. }

复制代码

3.1.4 元素封装

每个元素中，保存着 key 以及值，值同一使用 byte 数组进行存储，之所以用 []byte ，不用详细的数据布局，是因为需要抽象，适配所有的类型。
但是使用 []byte 我们取值后还需要转成 struct{}，比较斲丧 CPU，为什么不使用 interface{} 呢？
网上看到的一个答案是：内存中存储过多的 interface{} 会造成较大的 GC 影响：Getting to Go: The Journey of Go's Garbage Collector - The Go Programming Language

1. type entry struct {  
2.    key   string  
3.    value []byte  
4. }

复制代码

3.1.5 整体实现

fifo.go 文件中，存储元素使用队列，并且队列容量有肯定限定。但是为了兼顾查询效率，需要同时使用哈希表来存储 key 和 Element 的映射。

1. type fifo struct {  
2.    // 为了快速找到该value  
3.    cache map[string]*list.Element  
4.    // 按照添加顺序保存的list  
5.    head *list.List  
6.    // 缓存数据  
7.    stat Stat  
8. }  

复制代码

对外的初始化方法：

1. func New(maxBytes int64) Cache {  
2.    return &fifo{  
3.       cache: map[string]*list.Element{},  
4.       head:  list.New(),  
5.       stat: Stat{  
6.          keyCount:  0,  
7.          maxBytes:  maxBytes,  
8.          usedBytes: 0,  
9.       },   }}

复制代码

下面就是详细的实现：

1. import (     "container/list"  )    type fifo struct {  
2.    // 为了快速找到该value  
3.    cache map[string]*list.Element  
4.    // 按照添加顺序保存的list  
5.    head *list.List  
6.    // 缓存数据  
7.    stat Stat  
8. }    func (f *fifo) Set(key string, value []byte) {     if e, ok := f.cache[key]; ok && e != nil {        f.setDataExisted(e, value)     } else {        f.setDataNotExisted(key, value)     }}    func (f *fifo) setDataNotExisted(key string, value []byte) {     newEntry := &entry{        key:   key,        value: value,     }   if f.stat.maxBytes > 0 {        for f.stat.usedBytes+int64(len(key)+len(value)) > f.stat.maxBytes {           f.removeOldestElement()        }   }   e := f.head.PushBack(newEntry)     f.cache[key] = e     f.stat.usedBytes = f.stat.usedBytes + int64(len(key)+len(value))     f.stat.keyCount++    }    func (f *fifo) setDataExisted(e *list.Element, value []byte) {     originEntry := e.Value.(*entry)     originSize := len(originEntry.value)     beRemoved := false     if f.stat.maxBytes > 0 {        for (int64)(len(value))-(int64)(originSize) > f.stat.maxBytes-f.stat.usedBytes {           if f.head.Front() == e {              beRemoved = true           }           f.removeOldestElement()        }   }   if beRemoved {        f.setDataNotExisted(originEntry.key, value)        return     }     originEntry.value = value     f.stat.usedBytes = f.stat.usedBytes + (int64)(len(value)) - (int64)(originSize)    }    func (f *fifo) removeOldestElement() {     f.removeElement(f.head.Front())  }    func (f *fifo) removeElement(e *list.Element) {     if e == nil {        return     }     // 双向链表的删除     f.head.Remove(e)     originEntry := e.Value.(*entry)     f.stat.keyCount--     // 重新盘算使用空间     f.stat.usedBytes = f.stat.usedBytes - int64(len(originEntry.key)+len(originEntry.value))     // Hash表删除     delete(f.cache, originEntry.key)  }    func (f *fifo) Get(key string) []byte {     if e, ok := f.cache[key]; ok {        return e.Value.(*entry).value     }     return nil  }  func (f *fifo) Del(key string) {     if e, ok := f.cache[key]; ok {        f.removeElement(e)     }}  func (f *fifo) Stat() Stat {     return f.stat  }    func New(maxBytes int64) Cache {  
9.    return &fifo{  
10.       cache: map[string]*list.Element{},  
11.       head:  list.New(),  
12.       stat: Stat{  
13.          keyCount:  0,  
14.          maxBytes:  maxBytes,  
15.          usedBytes: 0,  
16.       },   }}

复制代码

测试一下，编写测试类 cache_test.go ：

1. import (  
2.    "Go-Cache/00_fifo/character01"  
3.    "fmt"   . "github.com/smartystreets/goconvey/convey"  
4.    "testing")  
5.   
6. func TestCache(t *testing.T) {  
7.    Convey("TestApplyFunc", t, func() {  
8.       cache := character01.New(100)  
9.       stat := fmt.Sprintf("stat:%v", cache.Stat())  
10.       So(stat, ShouldEqual, "stat:{0 100 0}")  
11.   
12.       cache.Set("hello", []byte("world"))  
13.       cache.Set("hello2", []byte("world2"))  
14.       stat = fmt.Sprintf("stat:%v", cache.Stat())  
15.       So(stat, ShouldEqual, "stat:{2 100 22}")  
16.   
17.       cache.Set("hello2", []byte("changeWorld2"))  
18.       value := cache.Get("hello2")  
19.       So(string(value), ShouldEqual, "changeWorld2")  
20.       stat = fmt.Sprintf("stat:%v", cache.Stat())  
21.       So(stat, ShouldEqual, "stat:{2 100 28}")  
22.   
23.       cache.Set("k1", []byte("longlonglonglonglonglonglonglonglonglonglonglonglonglonglonglonglonglongV1"))  
24.       stat = fmt.Sprintf("stat:%v", cache.Stat())  
25.       So(stat, ShouldEqual, "stat:{2 100 94}")  
26.   
27.       cache.Set("hello2", []byte("newHelloWorld2newHelloWorld2"))  
28.       value = cache.Get("hello2")  
29.       So(string(value), ShouldEqual, "newHelloWorld2newHelloWorld2")  
30.   
31.       stat = fmt.Sprintf("stat:%v", cache.Stat())  
32.       So(stat, ShouldEqual, "stat:{1 100 34}")  
33.   
34.       cache.Set("num", character01.IntToBytes(1))  
35.       num := cache.Get("num")  
36.       So(character01.BytesToInt(num), ShouldEqual, 1)  
37.   
38.       stat = fmt.Sprintf("stat:%v", cache.Stat())  
39.       So(stat, ShouldEqual, "stat:{2 100 45}")  
40.   
41.       cache.Set("num", nil)  
42.       So(cache.Get("num"), ShouldEqual, nil)  
43.   
44.       stat = fmt.Sprintf("stat:%v", cache.Stat())  
45.       So(stat, ShouldEqual, "stat:{2 100 37}")  
46.   
47.       cache.Del("num")  
48.       stat = fmt.Sprintf("stat:%v", cache.Stat())  
49.       So(stat, ShouldEqual, "stat:{1 100 34}")  
50.    })}

复制代码

3.2 增加锁

但是明显上面的代码是有题目的，当并发到肯定程度，就会出现并发写的 panic：

1. func TestNoLock(t *testing.T) {  
2.         // 包名是上面小节的包名
3.    cache := no_lock.New(100000)  
4.    num := 1000  
5.    var wg sync.WaitGroup  
6.    for i := 0; i < num; i++ {  
7.       index := i  
8.       wg.Add(1) //  
9.       go func() {  
10.          cache.Set("hello"+string(rune(index)), []byte("world"+string(rune(index))))  
11.          wg.Done() //5  
12.       }()  
13.    }   wg.Wait()  
14.    fmt.Printf("stat:%v\n", cache.Stat())  
15. }

复制代码

panic 的报错：

1. fatal error: concurrent map read and map write
3. goroutine 40 [running]:
4. runtime.throw({0x1125cae?, 0x1?})
5.         /usr/local/go/src/runtime/panic.go:992 +0x71 fp=0xc000133698 sp=0xc000133668 pc=0x1033791
6. runtime.mapaccess2_faststr(0x2?, 0x0?, {0xc0000960a8, 0x6})
7.         /usr/local/go/src/runtime/map_faststr.go:117 +0x3d4 fp=0xc000133700 sp=0xc000133698 pc=0x1011c74
8. Go-Cache/00_fifo/character01.(*fifo).Set(0xc00006e4b0, {0xc0000960a8, 0x6}, {0xc0000960a0, 0x6, 0x8})

复制代码

那为了实现并发安全，我们需要增加一把锁：

1. type fifo struct {  
2.    // 为了快速找到该value  
3.    cache map[string]*list.Element  
4.    // 按照添加顺序保存的list  
5.    head *list.List  
6.    // 缓存数据  
7.    stat  Stat  
8.    mutex sync.Mutex  
9. }

复制代码

在所有可能修改数据的操纵之前，加上锁, 比如 set ：

1. func (f *fifo) Set(key string, value []byte) {  
2.    f.mutex.Lock()  
3.    defer f.mutex.Unlock()  
4.    if e, ok := f.cache[key]; ok && e != nil {  
5.       f.setDataExisted(e, value)  
6.    } else {  
7.       f.setDataNotExisted(key, value)  
8.    }}

复制代码

fifo.go 文件改造如下：

1.   import (     "container/list"     "sync"   "time")    type fifo struct {  
2.    // 为了快速找到该value  
3.    cache map[string]*list.Element  
4.    // 按照添加顺序保存的list  
5.    head *list.List  
6.    // 缓存数据  
7.    stat  Stat  
8.    mutex sync.Mutex  
9. }
10.     func (f *fifo) Set(key string, value []byte) {  
11.    f.mutex.Lock()  
12.    defer f.mutex.Unlock()  
13.    if e, ok := f.cache[key]; ok && e != nil {  
14.       f.setDataExisted(e, value)  
15.    } else {  
16.       f.setDataNotExisted(key, value)  
17.    }}    func (f *fifo) setDataNotExisted(key string, value []byte) {     newEntry := &entry{        key:   key,        value: value,     }   if f.stat.maxBytes > 0 {        for f.stat.usedBytes+int64(len(key)+len(value)) > f.stat.maxBytes {           f.removeOldestElement()        }   }   e := f.head.PushBack(newEntry)     f.cache[key] = e     f.stat.usedBytes = f.stat.usedBytes + int64(len(key)+len(value))     f.stat.keyCount++    }    func (f *fifo) setDataExisted(e *list.Element, value []byte) {     originEntry := e.Value.(*entry)     originSize := len(originEntry.value)     beRemoved := false     if f.stat.maxBytes > 0 {        for (int64)(len(value))-(int64)(originSize) > f.stat.maxBytes-f.stat.usedBytes {           if f.head.Front() == e {              beRemoved = true           }           f.removeOldestElement()        }   }   if beRemoved {        f.setDataNotExisted(originEntry.key, value)        return     }     originEntry.value = value     f.stat.usedBytes = f.stat.usedBytes + (int64)(len(value)) - (int64)(originSize)    }    func (f *fifo) removeOldestElement() {     f.removeElement(f.head.Front())  }    func (f *fifo) removeElement(e *list.Element) {     if e == nil {        return     }     // 双向链表的删除     f.head.Remove(e)     originEntry := e.Value.(*entry)     f.stat.keyCount--     // 重新盘算使用空间     f.stat.usedBytes = f.stat.usedBytes - int64(len(originEntry.key)+len(originEntry.value))     // Hash表删除     delete(f.cache, originEntry.key)  }    func (f *fifo) Get(key string) []byte {     f.mutex.Lock()     defer f.mutex.Unlock()     if e, ok := f.cache[key]; ok {        return e.Value.(*entry).value     }     return nil  }  func (f *fifo) Del(key string) {     f.mutex.Lock()     defer f.mutex.Unlock()     if e, ok := f.cache[key]; ok {        f.removeElement(e)     }}  func (f *fifo) Stat() Stat {     return f.stat  }    func New(maxBytes int64) Cache {  
18.    return &fifo{  
19.       cache: map[string]*list.Element{},  
20.       head:  list.New(),  
21.       stat: Stat{  
22.          keyCount:  0,  
23.          maxBytes:  maxBytes,  
24.          usedBytes: 0,  
25.       },   }}

复制代码

再测试一下, 一切正常：

1. func TestCache(t *testing.T) {  
2.    cache := character02.New(100000)  
3.    num := 100  
4.    var wg sync.WaitGroup  
5.    for i := 0; i < num; i++ {  
6.       index := i  
7.       wg.Add(1) //  
8.       go func() {  
9.          cache.Set("hello"+string(rune(index)), []byte("world"+string(rune(index))))  
10.          wg.Done() //5  
11.       }()  
12.    }   wg.Wait()  
13.    fmt.Printf("stat:%v\n", cache.Stat())  
14. }

复制代码

3.3 读写锁

上面的锁，是全局锁，也就是不管是读照旧写，都会上锁，如果是读多写少的情况，我们盼望读是可以并发的，只有写是独占的，这个时间就需要考虑读写锁了。（缓存不肯定适合使用读写锁，这只是个思路，抛砖引玉。）

1.   import (     "container/list"     "sync"   "time")    type fifo struct {     // 为了快速找到该value     cache map[string]*list.Element     // 按照添加次序保存的list     head *list.List     // 缓存数据     stat  Stat     mutex sync.RWMutex  }    func (f *fifo) Set(key string, value []byte) {  
2.    f.mutex.Lock()  
3.    defer f.mutex.Unlock()  
4.    if e, ok := f.cache[key]; ok && e != nil {  
5.       f.setDataExisted(e, value)  
6.    } else {  
7.       f.setDataNotExisted(key, value)  
8.    }}    func (f *fifo) setDataNotExisted(key string, value []byte) {     newEntry := &entry{        key:   key,        value: value,     }   if f.stat.maxBytes > 0 {        for f.stat.usedBytes+int64(len(key)+len(value)) > f.stat.maxBytes {           f.removeOldestElement()        }   }   e := f.head.PushBack(newEntry)     f.cache[key] = e     f.stat.usedBytes = f.stat.usedBytes + int64(len(key)+len(value))     f.stat.keyCount++    }    func (f *fifo) setDataExisted(e *list.Element, value []byte) {     originEntry := e.Value.(*entry)     originSize := len(originEntry.value)     beRemoved := false     if f.stat.maxBytes > 0 {        for (int64)(len(value))-(int64)(originSize) > f.stat.maxBytes-f.stat.usedBytes {           if f.head.Front() == e {              beRemoved = true           }           f.removeOldestElement()        }   }   if beRemoved {        f.setDataNotExisted(originEntry.key, value)        return     }     originEntry.value = value     f.stat.usedBytes = f.stat.usedBytes + (int64)(len(value)) - (int64)(originSize)    }    func (f *fifo) removeOldestElement() {     f.removeElement(f.head.Front())  }    func (f *fifo) removeElement(e *list.Element) {     if e == nil {        return     }     // 双向链表的删除     f.head.Remove(e)     originEntry := e.Value.(*entry)     f.stat.keyCount--     // 重新盘算使用空间     f.stat.usedBytes = f.stat.usedBytes - int64(len(originEntry.key)+len(originEntry.value))     // Hash表删除     delete(f.cache, originEntry.key)  }    func (f *fifo) Get(key string) []byte {     f.mutex.RLock()     defer f.mutex.RUnlock()     // time.Sleep(1000000)     if e, ok := f.cache[key]; ok {        return e.Value.(*entry).value     }     return nil  }  func (f *fifo) Del(key string) {     f.mutex.Lock()     defer f.mutex.Unlock()     if e, ok := f.cache[key]; ok {        f.removeElement(e)     }}  func (f *fifo) Stat() Stat {     return f.stat  }    func New(maxBytes int64) Cache {  
9.    return &fifo{  
10.       cache: map[string]*list.Element{},  
11.       head:  list.New(),  
12.       stat: Stat{  
13.          keyCount:  0,  
14.          maxBytes:  maxBytes,  
15.          usedBytes: 0,  
16.       },   }}

复制代码

假设读取 Cache 是比较耗时的，我们加点耗时在 Get 操纵中：
func (f *fifo) Get(key string) []byte { f.mutex.RLock() defer f.mutex.RUnlock() time.Sleep(1000000) if e, ok := f.cache[key]; ok { return e.Value.(*entry).value } return nil }
测试的数据如下，值得注意的是：如果读竞争以及耗时不高，读写锁会拔苗助长。

• 读写锁：cost time: 4.560145ms
  
• 独占锁：cost time:12.012624518s
  

1. // cost time:4.560145ms  
2. func TestRWLock(t *testing.T) {  
3.    cache := character03.New(100000000000)  
4.    num := 10000  
5.    var wg sync.WaitGroup  
6.   
7.    for i := 0; i < num; i++ {  
8.       index := i  
9.       wg.Add(1) //  
10.       go func() {  
11.          cache.Set("hello"+string(rune(index)), []byte("world"+string(rune(index))))  
12.          wg.Done() //5  
13.       }()  
14.    }   wg.Wait()  
15.    startTime := time.Now()  
16.    for i := 0; i < num; i++ {  
17.       index := i  
18.       wg.Add(1) //  
19.       go func() {  
20.          cache.Get("hello" + string(rune(index)))  
21.          wg.Done()  
22.       }()   }   wg.Wait()  
23.    endTime := time.Now()  
24.    fmt.Printf("stat:%v\n", cache.Stat())  
25.    // cost time:31.587204813s  
26.    fmt.Printf("cost time:%v\n", endTime.Sub(startTime))  
27. }  
28.   
29. //cost time:12.012624518s  
30. func TestLock(t *testing.T) {  
31.    cache := lock.New(100000000000)  
32.    num := 10000  
33.    var wg sync.WaitGroup  
34.   
35.    for i := 0; i < num; i++ {  
36.       index := i  
37.       wg.Add(1) //  
38.       go func() {  
39.          cache.Set("hello"+string(rune(index)), []byte("world"+string(rune(index))))  
40.          wg.Done()  
41.       }()   }   wg.Wait()  
42.    startTime := time.Now()  
43.    for i := 0; i < num; i++ {  
44.       index := i  
45.       wg.Add(1) //  
46.       go func() {  
47.          cache.Get("hello" + string(rune(index)))  
48.          wg.Done() //5  
49.       }()  
50.    }   wg.Wait()  
51.    endTime := time.Now()  
52.    fmt.Printf("stat:%v\n", cache.Stat())  
53.    //cost time:31.765169643s  
54.    fmt.Printf("cost time:%v\n", endTime.Sub(startTime))  
55. }

复制代码

3.4 自实现双向队列

使用原生的双向队列，确实可以省事，但是作为一个程序员，照旧有一种造轮子的想法，那就自己写个双向队列，够用就行，不用实现所有的方法:

1.   
2. type List struct {  
3.    head *Node // 表头节点  
4.    tail *Node // 表尾节点  
5.    len  int   // 长度  
6. }  
7.   
8. type Node struct {  
9.    next, prev *Node  
10.    list       *List  
11.    Value      any  
12. }  
13.   
14. func NewList() *List {  
15.    return &List{}  
16. }  
17.   
18. func NewNode(v any) *Node {  
19.    return &Node{  
20.       Value: v,  
21.    }}  
22.   
23. func (l *List) Front() *Node {  
24.    return l.head  
25. }  
26.   
27. func (l *List) Remove(node *Node) {  
28.    index := l.Find(node)  
29.    if index == -1 {  
30.       return  
31.    }  
32.    prev := node.prev  
33.    next := node.next  
34.    if prev == nil && next == nil {  
35.       l.len = 0  
36.       l.tail = nil  
37.       l.head = nil  
38.       return   }  
39.    if prev == nil {  
40.       next := node.next  
41.       next.prev = nil  
42.       l.head = next  
43.       l.len--  
44.       return  
45.    }  
46.    if next == nil {  
47.       prev := node.prev  
48.       prev.next = nil  
49.       l.tail = prev  
50.       l.len--  
51.       return  
52.    }  
53.    prev.next = next  
54.    next.prev = prev  
55.    l.len--  
56.    return  
57. }  
58.   
59. func (l *List) Find(node *Node) int {  
60.    if l.len == 0 || node == nil {  
61.       return -1  
62.    }  
63.    index := 0  
64.    head := l.head  
65.    for head != nil {  
66.       if head != node {  
67.          head = head.next  
68.          index++  
69.       } else {  
70.          return index  
71.       }  
72.    }   return -1  
73. }  
74.   
75. func (l *List) PushBack(v any) *Node {  
76.    node := NewNode(v)  
77.    if l.len == 0 {  
78.       node.prev = nil  
79.       node.next = nil  
80.       l.head = node  
81.       l.tail = node  
82.    } else {  
83.       tempTail := l.tail  
84.       tempTail.next = node  
85.       node.prev = tempTail  
86.   
87.       l.tail = node  
88.    }  
89.    l.len++  
90.    return node  
91. }

复制代码

但凡使用到原生的 List 和 Node 的地方，都替换成自己实现的：

1.   
2. import (  
3.    "errors"  
4.    "log"   "sync")  
5.   
6. type fifo struct {  
7.    // 为了快速找到该value  
8.    cache map[string]*Node  
9.    // 按照添加顺序保存的list  
10.    list *List  
11.    // 缓存数据  
12.    stat  Stat  
13.    mutex sync.RWMutex  
14. }  
15.   
16. func (f *fifo) Set(key string, value []byte) {  
17.    f.mutex.Lock()  
18.    defer f.mutex.Unlock()  
19.    err := f.checkMaxBytes(key, value)  
20.    if err != nil {  
21.       log.Fatalf("checkMaxBytes err:%v\n", err)  
22.       return  
23.    }  
24.    if e, ok := f.cache[key]; ok && e != nil {  
25.       f.setDataExisted(e, value)  
26.    } else {  
27.       f.setDataNotExisted(key, value)  
28.    }}  
29.   
30. func (f *fifo) checkMaxBytes(key string, value []byte) error {  
31.    if f.stat.maxBytes > 0 {  
32.       if f.stat.maxBytes < int64(len(key)+len(value)) {  
33.          return errors.New("over maxBytes")  
34.       }   }   return nil  
35. }  
36.   
37. func (f *fifo) setDataNotExisted(key string, value []byte) {  
38.    newEntry := &entry{  
39.       key:   key,  
40.       value: value,  
41.    }   if f.stat.maxBytes > 0 {  
42.       for f.stat.usedBytes+int64(len(key)+len(value)) > f.stat.maxBytes {  
43.          f.removeOldestElement()  
44.       }   }   e := f.list.PushBack(newEntry)  
45.    f.cache[key] = e  
46.    f.stat.usedBytes = f.stat.usedBytes + int64(len(key)+len(value))  
47.    f.stat.keyCount++  
48.   
49. }  
50.   
51. func (f *fifo) setDataExisted(e *Node, value []byte) {  
52.    originEntry := e.Value.(*entry)  
53.    originSize := len(originEntry.value)  
54.    beRemoved := false  
55.    if f.stat.maxBytes > 0 {  
56.       for (int64)(len(value))-(int64)(originSize) > f.stat.maxBytes-f.stat.usedBytes {  
57.          if f.list.Front() == e {  
58.             beRemoved = true  
59.          }  
60.          f.removeOldestElement()  
61.       }   }   if beRemoved {  
62.       f.setDataNotExisted(originEntry.key, value)  
63.       return  
64.    }  
65.    originEntry.value = value  
66.    f.stat.usedBytes = f.stat.usedBytes + (int64)(len(value)) - (int64)(originSize)  
67.   
68. }  
69.   
70. func (f *fifo) removeOldestElement() {  
71.    f.removeElement(f.list.Front())  
72. }  
73.   
74. func (f *fifo) removeElement(e *Node) {  
75.    if e == nil {  
76.       return  
77.    }  
78.    // 双向链表的删除  
79.    f.list.Remove(e)  
80.    originEntry := e.Value.(*entry)  
81.    f.stat.keyCount--  
82.    // 重新计算使用空间  
83.    f.stat.usedBytes = f.stat.usedBytes - int64(len(originEntry.key)+len(originEntry.value))  
84.    // Hash表删除  
85.    delete(f.cache, originEntry.key)  
86. }  
87.   
88. func (f *fifo) Get(key string) []byte {  
89.    f.mutex.RLock()  
90.    defer f.mutex.RUnlock()  
91.    // time.Sleep(1000000)  
92.    if e, ok := f.cache[key]; ok {  
93.       return e.Value.(*entry).value  
94.    }  
95.    return nil  
96. }  
97. func (f *fifo) Del(key string) {  
98.    f.mutex.Lock()  
99.    defer f.mutex.Unlock()  
100.    if e, ok := f.cache[key]; ok {  
101.       f.removeElement(e)  
102.    }}  
103. func (f *fifo) Stat() Stat {  
104.    return f.stat  
105. }  
106.   
107. func New(maxBytes int64) Cache {  
108.    return &fifo{  
109.       cache: map[string]*Node{},  
110.       list:  NewList(),  
111.       stat: Stat{  
112.          keyCount:  0,  
113.          maxBytes:  maxBytes,  
114.          usedBytes: 0,  
115.       },   }}

复制代码

简单测试一下，符合预期：

1. func TestMyQueue(t *testing.T) {  
2.    Convey("TestApplyFunc", t, func() {  
3.       cache := character04.New(100)  
4.       stat := fmt.Sprintf("stat:%v", cache.Stat())  
5.       So(stat, ShouldEqual, "stat:{0 100 0}")  
6.   
7.       cache.Set("hello", []byte("world"))  
8.       cache.Set("hello2", []byte("world2"))  
9.       stat = fmt.Sprintf("stat:%v", cache.Stat())  
10.       So(stat, ShouldEqual, "stat:{2 100 22}")  
11.   
12.       cache.Set("hello2", []byte("changeWorld2"))  
13.       value := cache.Get("hello2")  
14.       So(string(value), ShouldEqual, "changeWorld2")  
15.       stat = fmt.Sprintf("stat:%v", cache.Stat())  
16.       So(stat, ShouldEqual, "stat:{2 100 28}")  
17.   
18.       cache.Set("k1", []byte("longlonglonglonglonglonglonglonglonglonglonglonglonglonglonglonglonglongV1"))  
19.       stat = fmt.Sprintf("stat:%v", cache.Stat())  
20.       So(stat, ShouldEqual, "stat:{2 100 94}")  
21.   
22.       cache.Set("hello2", []byte("newHelloWorld2newHelloWorld2"))  
23.       value = cache.Get("hello2")  
24.       So(string(value), ShouldEqual, "newHelloWorld2newHelloWorld2")  
25.   
26.       stat = fmt.Sprintf("stat:%v", cache.Stat())  
27.       So(stat, ShouldEqual, "stat:{1 100 34}")  
28.   
29.       cache.Set("num", character01.IntToBytes(1))  
30.       num := cache.Get("num")  
31.       So(character01.BytesToInt(num), ShouldEqual, 1)  
32.   
33.       stat = fmt.Sprintf("stat:%v", cache.Stat())  
34.       So(stat, ShouldEqual, "stat:{2 100 45}")  
35.   
36.       cache.Set("num", nil)  
37.       So(cache.Get("num"), ShouldEqual, nil)  
38.   
39.       stat = fmt.Sprintf("stat:%v", cache.Stat())  
40.       So(stat, ShouldEqual, "stat:{2 100 37}")  
41.   
42.       cache.Del("num")  
43.       stat = fmt.Sprintf("stat:%v", cache.Stat())  
44.       So(stat, ShouldEqual, "stat:{1 100 34}")  
45.    })}

复制代码

3.5 http 改造

一般缓存集成启动后，除了能使用代码直接操纵，还会支持以 http 的方式操纵，我们的也不能少了这个本领，那就来改造一下吧！
先封装一个 server, 监听 12345 端口，操纵 Cache 和查询状态分别对应 cacheHandler 和 statHandler。

1. import (  
2.    "Go-Cache/00_fifo/character05"  
3.    "net/http")  
4.   
5. type Server struct {  
6.    cache character05.Cache  
7. }  
8.   
9. func New(c character05.Cache) *Server {  
10.    return &Server{  
11.       c,  
12.    }}  
13.   
14. func (s *Server) Listen() {  
15.    // 注意是 /cache/  包括下面的子页面  
16.    http.Handle("/cache/", s.cacheHandler())  
17.    http.Handle("/stat", s.statHandler())  
18.    http.ListenAndServe(":12345", nil)  
19. }  
20.   
21. func (s *Server) cacheHandler() *cacheHandler {  
22.    return &cacheHandler{  
23.       Server: s,  
24.    }}  
25.   
26. func (s *Server) statHandler() *statHandler {  
27.    return &statHandler{  
28.       Server: s,  
29.    }}

复制代码

状态查询的 handler 实现：

1.   
2. import (  
3.    "encoding/json"  
4.    "log"   "net/http")  
5.   
6. type statHandler struct {  
7.    *Server  
8. }  
9.   
10. func (h *statHandler) ServeHTTP(w http.ResponseWriter, r *http.Request) {  
11.    if r.Method != http.MethodGet {  
12.       w.WriteHeader(http.StatusMethodNotAllowed)  
13.       return  
14.    }  
15.    b, e := json.Marshal(h.cache.Stat())  
16.    if e != nil {  
17.       w.WriteHeader(http.StatusInternalServerError)  
18.       return  
19.    }  
20.    res, err := w.Write(b)  
21.    if err != nil {  
22.       log.Fatalln(err)  
23.    }   log.Printf(string(rune(res)))  
24. }

复制代码

操纵缓存 handler 的实现：

1.   
2. import (  
3.    "io/ioutil"  
4.    "net/http"   "strings")  
5.   
6. type cacheHandler struct {  
7.    *Server  
8. }  
9.   
10. func (h *cacheHandler) ServeHTTP(w http.ResponseWriter, r *http.Request) {  
11.    key := strings.Split(r.URL.EscapedPath(), "/")[2]  
12.    if len(key) == 0 {  
13.       w.WriteHeader(http.StatusBadRequest)  
14.       return  
15.    }  
16.    m := r.Method  
17.    if m == http.MethodGet {  
18.       b := h.cache.Get(key)  
19.       if len(b) == 0 {  
20.          w.WriteHeader(http.StatusNotFound)  
21.          return  
22.       }  
23.       w.Write(b)  
24.       return  
25.    }  
26.    if m == http.MethodPut {  
27.       b, _ := ioutil.ReadAll(r.Body)  
28.       if len(b) != 0 {  
29.          h.cache.Set(key, b)  
30.       }      return  
31.    }  
32.    if m == http.MethodDelete {  
33.       h.cache.Del(key)  
34.       return  
35.    }  
36.    w.WriteHeader(http.StatusMethodNotAllowed)  
37. }

复制代码

启动类如下：

1. import (  
2.    "Go-Cache/00_fifo/character05"  
3.    "Go-Cache/00_fifo/character05/server")  
4.   
5. func main() {  
6.    c := character05.New(0)  
7.    server.New(c).Listen()  
8. }

复制代码

启动之后，我们打开 http://localhost:12345/stat, 可以看到以下内容，就是启动乐成了：

下面是 curl 命令行操纵：

1. ~  curl -X PUT -d "world" http://localhost:12345/cache/hello
2. ~  curl http://localhost:12345/stat
3. {"KeyCount":1,"MaxBytes":0,"UsedBytes":10}%
4. ~  curl http://localhost:12345/cache/hello
5. world%
6. ~  curl -X PUT -d "world2" http://localhost:12345/cache/hello
7. ~  curl http://localhost:12345/cache/hello
8. world2%
9. ~  curl -X PUT -d "smart" http://localhost:12345/cache/xiaoming
10. ~  curl http://localhost:12345/cache/xiaoming
11. smart%

复制代码

4 小结一下

总的来说，FIFO 是极其简单的缓存淘汰算法，思路很清楚，初学者可以试试，它并不高效，但是它是最简单粗暴的处理方法，先进先出，不会区别对待。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。