Golang 第三方库golang-lru基于双向链表实现了三种LRU及变种Cache:LRU,Q2,ARC。LRU算法:若数据已经在缓存中,将其移到队首,并返回结果。若数据不在缓存中,将新记录添加到队首。若缓存超长,清理队尾缓存数据。

2Q算法有两个缓存队列,一个是FIFO队列,用于保存最近访问的数据;一个是LRU队列,用于保存热点数据。recent 用于保存最近访问的数据,frequent用于保存热点数据,recentEvict保存从最近队列中剔除的数据。当增加一个新记录时:

如果frequent队列中存在该数据则更新,否则下一步;

如果recent队列存在该数据,则将其移至frequent队列,否则下一步;

如果recentEvict队列存在该数据,则确保队列有空间后将其移至frequent,否则下一步;

确保队列有空闲,并将其添加至recent。

第一步,frequent 长度不变,整个2q Cache长度不变;第二步recent长度减一,frequent长度加一,总长度不变;第三步,recentEvict长度减一,frequent要增加新数据,由于recentEvict不计算在cache size内,总长度加一,所以需要确认队列是否有空闲,如果没有则remove oldest;第四步,recent长度加1,总长度加一,需要判断队列是否有空闲。

1.安装缓存库: go get "github.com/hashicorp/golang-lru"

2.导入缓存库:import "github.com/hashicorp/golang-lru"

3.创建给定大小3的LRU:kvch, err := lru.New(3)

4.将值添加到缓存:kvch.Add("1", "9")

5.获得缓存中key对应的value,不存在返回nil,false:kvch.Get("1")

6.获得缓存长度:Kvch.Len()

示例源码:阅读原文,用法文档:https://godoc.org/github.com/hashicorp/golang-lru#New