Go LRU Cache 抛砖引玉

目录

1. LRU Cache

2. container/list.go

2.1 list 数据结构

2.2 list 使用例子

3. transport.go connLRU

4. 结尾

正文

1. LRU Cache

package cache

import (
"container/list"
"sync"
) // entry 存储的实体
type entry struct {
key, val interface{}
} // Cache 缓存结构
type Cache struct {
// m 保证 LRU Cache 访问线程安全
rw sync.RWMutex // max 标识缓存容量的最大值, = 0 标识无限缓存
max int // list 是 entry 循环双向链表
list *list.List // pond entry 缓存池子 key -> entry
pond map[interface{}]*list.Element
} // New 构建 LRU Cache 缓存结构
func New(max int) *Cache {
return &Cache{
max: max,
list: list.New(),
pond: make(map[interface{}]*list.Element),
}
} func (c *Cache) delete(key interface{}) {
element, ok := c.pond[key]
if ok {
delete(c.pond, key)
c.list.Remove(element)
return
}
} // Set 设置缓存
func (c *Cache) Set(key, val interface{}) {
c.rw.Lock()
defer c.rw.Unlock() // 看是否进入删除分支
if val == nil {
c.delete(key)
return
} element, ok := c.pond[key]
if ok {
// 重新设置 value 数据
element.Value.(*entry).val = val
// set key nil exists 进入 update 逻辑
c.list.MoveToFront(element)
return
} // 首次添加
c.pond[key] = c.list.PushFront(&entry{key, val}) // 数据过多, 删除尾巴数据
if c.list.Len() > c.max && c.max > 0 {
delete(c.pond, c.list.Remove(c.list.Back()).(*entry).key)
}
} // Get 获取缓存
func (c *Cache) Get(key interface{}) (val interface{}, ok bool) {
c.rw.RLock()
defer c.rw.RUnlock() if element, ok := c.pond[key]; ok {
// 获取指定缓存值
val, ok = element.Value.(*entry).val, true
// 调整缓存热点
c.list.MoveToFront(element)
}
return
}

原理是 1. RWLock 做线程安全 2. list 双向链表保存时间新老关系 2. map 为了让时间复杂度到 O(1).

使用教程:

// 创建
c := cache.New(1) // 设置
c.Set("123", "123")
c.Set("234", "234") // 使用
fmt.Println(c.Get("123"))
fmt.Println(c.Get("234")) // 删除
c.Set("123", nil)

2. container/list.go

2.1 list 数据结构

上面 LRU Cache 代码中引用了 "container/list" , 简单分析下 list, 加深基础数据结构的了解.

// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file. // Package list implements a doubly linked list.
//
// To iterate over a list (where l is a *List):
// for e := l.Front(); e != nil; e = e.Next() {
// // do something with e.Value
// }
//
package list // Element is an element of a linked list.
type Element struct {
// Next and previous pointers in the doubly-linked list of elements.
// To simplify the implementation, internally a list l is implemented
// as a ring, such that &l.root is both the next element of the last
// list element (l.Back()) and the previous element of the first list
// element (l.Front()).
next, prev *Element // The list to which this element belongs.
list *List // The value stored with this element.
Value interface{}
} // Next returns the next list element or nil.
func (e *Element) Next() *Element {
if p := e.next; e.list != nil && p != &e.list.root {
return p
}
return nil
} // Prev returns the previous list element or nil.
func (e *Element) Prev() *Element {
if p := e.prev; e.list != nil && p != &e.list.root {
return p
}
return nil
} // List represents a doubly linked list.
// The zero value for List is an empty list ready to use.
type List struct {
root Element // sentinel list element, only &root, root.prev, and root.next are used
len int // current list length excluding (this) sentinel element
}

它是个特殊循环双向链表数据结构, 特殊之处在于 Element::List  指向头结点(root list).

Go LRU Cache 抛砖引玉

关于业务 list.go 具体实现部分我们不表.

2.2 list 使用例子

func Test_List_Demo(t *testing.T) {

    // Persion 普通人
type Persion struct {
Name string
Age int
} pers := list.New() // 链表数据填充
pers.PushBack(&Persion{Name: "wang", Age: 31})
pers.PushFront(&Persion{Name: "zhi", Age: 31}) fmt.Printf("List Len() = %d\n", pers.Len())
if pers.Len() != 2 {
t.Fatal("pers.Len() != 2 data faild")
} // 开始遍历数据
for element := pers.Front(); element != nil; element = element.Next() {
per, ok := element.Value.(*Persion)
if !ok {
panic(fmt.Sprint("Persion list faild", element.Value))
}
fmt.Println(per)
} // 数据删除
for element := pers.Front(); element != nil; {
next := element.Next()
pers.Remove(element)
element = next
} fmt.Printf("List Len() = %d\n", pers.Len())
if pers.Len() != 0 {
t.Fatal("pers.Len() != 0 data faild")
}
}

单元测试结果:

Running tool: /usr/local/go/bin/go test -timeout 30s -run ^Test_List_Demo$ demo/src/container/list -v -count=1

=== RUN   Test_List_Demo
List Len() = 2
&{zhi 31}
&{wang 31}
List Len() = 0
--- PASS: Test_List_Demo (0.00s)
PASS
ok demo/src/container/list 0.002s

3. transport.go connLRU

抛一段 Go 源码中一处应用, 小学以小用

//
// src/net/http/transport.go
// // persistConn wraps a connection, usually a persistent one
// (but may be used for non-keep-alive requests as well)
type persistConn struct {
  ...
  ..
  .
} type connLRU struct {
ll *list.List // list.Element.Value type is of *persistConn
m map[*persistConn]*list.Element
} // add adds pc to the head of the linked list.
func (cl *connLRU) add(pc *persistConn) {
if cl.ll == nil {
cl.ll = list.New()
cl.m = make(map[*persistConn]*list.Element)
}
ele := cl.ll.PushFront(pc)
if _, ok := cl.m[pc]; ok {
panic("persistConn was already in LRU")
}
cl.m[pc] = ele
} func (cl *connLRU) removeOldest() *persistConn {
ele := cl.ll.Back()
pc := ele.Value.(*persistConn)
cl.ll.Remove(ele)
delete(cl.m, pc)
return pc
} // remove removes pc from cl.
func (cl *connLRU) remove(pc *persistConn) {
if ele, ok := cl.m[pc]; ok {
cl.ll.Remove(ele)
delete(cl.m, pc)
}
} // len returns the number of items in the cache.
func (cl *connLRU) len() int {
return len(cl.m)
}

4. 结尾

很多代码, 很多事情也都平淡无奇, 但凡事种种都离不开用心, 反复琢磨 ~ 方能长久

欢迎批评指正交流 ~ good luckly ~

上一篇:HDU 2767 Proving Equivalences (强联通)


下一篇:[LeetCode] LRU Cache 最近最少使用页面置换缓存器