By

[TOC]

golang-lru包学习 - 2Q算法

2Q算法

代码:2Q
论文:A low overhead high performance buffer replacement algorithm

2Q算法的描述:

2Q与LRU/2对于LRU的改进在某种程度上存在互补性，2Q并不是通过直接将冷页从主缓存中剔出，而是通过将热页换入的形式来实现。与LRU/2算法类似，2Q以该页的第二次被访问时间来计算。简单来说，在某一页第一次被访问的时候，2Q将其放入一个特殊的缓冲区，称为A1 queue，其实现就是一个FIFO队列，如果该页在A1 queue的生存周期内被再次访问，则可能是热页，将其置入Am queue，其实就是一个LRU。如果在A1 queue的生存期内没有再次被访问到，则将其换出。

理论简易版本2Q算法实现:

首次添加  Add("A")
          | A1(FIFO) |           | Am (LRU)|
          |----------|           |---------|
ele(A)->  | ele(A)   |           |         |
          |----------|           |---------|
		
第二次添加或者访问 Add("A") Get("A")
          | A1(FIFO) |           | Am (LRU)|
	  |----------|           |---------|
          |          |    ->     | ele(A)  |
	  |----------|           |---------|

理论2Q算法实现:

首次添加  Add("A")
          | A1in(FIFO)|      |A1out(FIFO)|       | Am (LRU)|
          |-----------|      |-----------|       |---------|
ele(A)->  | ele(A)    |      |           |       |         |
	  |-----------|      |-----------|       |---------|
		
第二次添加或者访问 Add("A") Get("A")
          | A1in(FIFO)|      |A1out(FIFO)|       | Am (LRU)|
	  |-----------|      |-----------|       |---------|
          |           |  ->  |   ele(A)  |       |         |
          |-----------|      |-----------|       |---------|
		
第三次添加或者访问 Add("A") Get("A")
          | A1in(FIFO)|      |A1out(FIFO)|       | Am (LRU)|
	  |-----------|      |-----------|       |---------|
          |           |      |           |   ->  | ele(A)  |
	  |-----------|      |-----------|       |---------|

2Q算法特点是:

结合FIFO和LRU特性,把新加入的条目放到FIFO,如果有二次访问再换入LRU队列中,确保LRU队列中的都是热页,减少偶发性数据的影响,其添加、删除、查找操作都需要分别对FIFO和LRU两个队列进行执行。

理论上2Q算法设计中使用的是FIFO队列进行,但在当前包中FIFO队列使用的与LRU队列一样都是simple-lru。另外一个特点是,本包的2Q算法是基于simple版本的2Q算法,包含A1和Am队列,但是增加了A1淘汰队列,对于从A1中淘汰下来的元素会添加到A1evict队列中,当缓存再次添加A1evict中的元素时候,元素不会重新进入A1队列,而是直接进入LRU队列中。

需要注意的是2Q算法的三个队列长度具有比例关系,初始时候需要设置队列大小比例,默认比例关系: LRU:A1:A1evict = 1:0.5:0.25 队列大小比例设置会影响冷页的置换。

recent -> A1
recentEvict -> A1淘汰队列 frequent -> Am

本包2Q算法实现:

首次添加  Add("A")
          | A1(LRU)   |      |A1evict(LRU)|       | Am (LRU)|
          |-----------|      |------------|       |---------|
ele(A)->  | ele(A)    |      |            |       |         |
          |-----------|      |------------|       |---------|
		
第二次添加或者访问 Add("A") Get("A")
          | A1(LRU)   |      |A1evict(LRU)|       | Am (LRU)|
          |-----------|      |------------|       |---------|
          |           |      |            |   ->  | ele(A)  |
	  |-----------|      |------------|       |---------|
		
对于已被A1淘汰的数据,再次添加访问 Add("A")
          | A1(LRU)   |       |A1evict(LRU)|       | Am (LRU)|
          |-----------|      |------------|       |---------|
          |           |      |    ele(A)  |       |         |
	  |-----------|      |------------|       |---------|		
		
          | A1(LRU)   |      |A1evict(LRU)|       | Am (LRU)|
	  |-----------|      |------------|       |---------|
          |           |      |            |   ->  | ele(A)  |
	  |-----------|      |------------|       |---------|

type TwoQueueCache struct {
	size       int					// 队列既定长度
	recentSize int					// FIFO队列既定长度

	recent      simplelru.LRUCache			// A1队列
	recentEvict simplelru.LRUCache			// A1淘汰队列
	frequent    simplelru.LRUCache			// LRU队列
	lock        sync.RWMutex			// 读写锁
}

函数

type 2QCache interface {
  New2Q(size int) (*TwoQueueCache, error) 				// 创建一个2Q算法的缓存对象,队列长度参数使用默认参数 1:0.5:0.25
  New2QParams(size int, recentRatio float64, ghostRatio float64) (*TwoQueueCache, error) // 创建一个2Q算法的缓存对象,队列长度参数使用自定义参数
  Add(key, value interface{})  				// 添加元素,若元素不存在则添加元素,若元素存在则更新元素
  Get(key interface{}) (value interface{}, ok bool) 	// 获取元素
  Contains(key interface{}) (ok bool) 			// 查看该元素是否存在,但不会更新元素位置
  Peek(key interface{}) (value interface{}, ok bool)	// 获取元素,但不会更新元素位置
  Remove(key interface{}) bool				// 删除元素
  Len() int						// 返回队列中元素数量
  Purge()						// 清除队列中全部元素
}

过程

2Q算法核心过程是Get和Add,我们针对这两个方法进到代码里看看

Add() 添加元素

// Add adds a value to the cache.
func (c *TwoQueueCache) Add(key, value interface{}) {
	c.lock.Lock()
	defer c.lock.Unlock()

	if c.frequent.Contains(key) {					// 如果在LRU队列,直接更新
		c.frequent.Add(key, value)
		return
	}

	if c.recent.Contains(key) {					// 如果在A1队列,则移动到LRU队列
		c.recent.Remove(key)
		c.frequent.Add(key, value)
		return
	}

	if c.recentEvict.Contains(key) {				// 如果在A1淘汰队列,则移动到LRU队列
		c.ensureSpace(true)					// 对执行淘汰,腾出空间 1.对于A1in队列如果超出预设长度,则淘汰末端到Alevict 2.对于LRU队列,直接淘汰末端
		c.recentEvict.Remove(key)
		c.frequent.Add(key, value)
		return
	}

	c.ensureSpace(false)						// 对执行淘汰,腾出空间 1.对于LRU队列,直接淘汰末端
	c.recent.Add(key, value)					// 添加元素到A1队列
	return
}

Get() 获取元素

func (c *TwoQueueCache) Get(key interface{}) (value interface{}, ok bool) {
	c.lock.Lock()
	defer c.lock.Unlock()

	if val, ok := c.frequent.Get(key); ok {			// 从LRU队列获取
		return val, ok
	}

	if val, ok := c.recent.Peek(key); ok {			// 从A1in队列获取
		c.recent.Remove(key)				// 获取成功,移动到LRU队列
		c.frequent.Add(key, val)
		return val, ok
	}

	// No hit
	return nil, false
}

总结

  • 2Q算法实现是基于simple 2Q算法,底层包括 A1、Am和A1淘汰队列
  • 2Q算法可以减弱偶发性的数据对缓存的影响
  • 2Q算法需要设置队列长度比例

文章目录