LRU算法及实现

1.什么是LRU

LRU是一个数据缓存结构,它的英文名称是Least recently used,用于解决缓存中占用资源过多的问题,该结构只会存放固定数量的最近使用的数据,也就是应用的热点数据(假设应用的数据有一些经常被访问,而一些则偶尔被访问到),在满足大部分查询需求的情况下,实现内存占用最小化。同时LRU算法基于该数据最近是否被使用来完成对于多余数据元素的清理操作。

下面是一个LRU的数据存储管理实例,可以看做是一个列表结构,我们设置的缓存大小是5,当我们依次写入A,B, C, D, E的时候,由于不超过原始的数据存储空间,因此依次将数据写入列表头部,写入过程中其他的则往后移动。

  • 当写入F的时候,超出最大范围,列表的尾部数据被删除,插入F元素到列表头部
  • 当写入C的时候,由于C在列表中,则需要将C从原列表位置移动到列表的头部,前面的元素依次后移.
  • 当写入G的时候,G不存在列表,则删除原来列表尾部数据,插入G元素到列表头部

2. 程序实现

由于LRU操作虽然简单,但是由于涉及到查询,移位等操作,需要选择合适的数据结构来完成,才能实现高效的数据处理。比如如果使用数组来存放原始数据的话,则每次插入和更新元素位移数据至少需要O(n)的操作。而使用链表结构则只需要O(1)的操作,但是不管我们使用数组还是链表,查询缓存是否存在在链表中也需要O(n)的操作。我们知道Hash表可以实现O(1)的操作,其实我们可以使用链表和Hash表结合的自定义数据结构来实现LRU,Hash表存储的是链表元素的位置信息,这样我们就能够在O(1)的时间内实现整个的操作。

定义数据结构
type LRU struct {
	mutex sync.RWMutex
	size  int
	l     *list.List
	m     map[string]*list.Element
}

这里使用锁来保护多个goroutine在同时访问元素的时候的安全的进行并发更新,当然如果可以保证该数据结构仅仅在单线程内的使用,可以忽略锁的内容。 size代表缓存最大的容量。后面的l是一个go语言内置的链表容器,内部实现为双端链表。m则为一个hash表,使用string作为key,存储的为链表的元素指针。

基本方法实现
  • NewLRU 初始化方法,设置最大的容器容量
  • Set 更新操作,设置元素数据,并跟新缓存
  • Get 取值操作,获取元素数据,并更新缓存
  • EvictOldest 用于删除最早的数据仅仅用于设置数据的时候使用。
func NewLRU(size int) *LRU {
	return &LRU{
		size: size,
		l:    list.New(),
		m:    make(map[string]*list.Element, size),
	}
}

func (lru *LRU) Get(key string) (interface{}, bool) {
	lru.mutex.RLock()
	defer lru.mutex.RUnlock()

	if element, ok := lru.m[key]; ok {
		// Move element to the front
		lru.l.MoveToFront(element)
		return element.Value, ok
	}
	return nil, false
}

func (lru *LRU) Set(key string, value interface{}) {
	lru.mutex.Lock()
	defer lru.mutex.Unlock()
	if element, ok := lru.m[key]; ok {
		element.Value = &Entity{Key: key, Value: value}
		lru.l.MoveToFront(element)
		return
	}
	element := lru.l.PushFront(&Entity{Key: key, Value: value})
	lru.m[key] = element
	if lru.size != 0 && lru.l.Len() > lru.size {
		lru.EvictOldest()
	}
}
func (lru *LRU) EvictOldest() {
	element := lru.l.Back()
	if element != nil {
		lru.l.Remove(element)
		delete(lru.m, element.Value.(*Entity).Key)
	}
}

测试数据

关于性能测试,这里给出两个简单的测试方法,在我自己的笔记本电脑上测试,一秒大概可以处理2000万左右的读或者500万次写,由于Set内部可涉及不止一次的Hash操作,因此总体上速度和Get还是相差很大。具体的测试程序和结果如下:

func BenchmarkLRUSet(b *testing.B) {
	lru := NewLRU(5)
	data := []string{"A", "B", "C", "D", "E", "F", "C", "G"}
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		item := data[i%8]
		lru.Set(item, item)
	}
}

func BenchmarkLRUGet(b *testing.B) {
	lru := NewLRU(5)
	data := []string{"A", "B", "C", "D", "E", "F", "C", "G"}
	for _, item := range data {
		lru.Set(item, item)
	}
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		item := data[i%8]
		lru.Get(item)
	}
}

# BenchmarkLRUSet-6   	 5905830	       198 ns/op	      84 B/op	       2 allocs/op
# BenchmarkLRUGet-6   	23332682	        51.3 ns/op	       0 B/op	       0 allocs/op

发表评论

电子邮件地址不会被公开。 必填项已用*标注