slava是作者参与的一个github开源项目，该项目的目标是用Go语言构建一个高性能K-V云数据库。
在本文中，作者将介绍Slava中内存淘汰策略的实现。Slava中目前实现了四种内存淘汰策略，分别是maxMemoryLruAllKeys,maxMemoryLfuAllKeys,maxMemoryLruTtl和maxMemoryLfuTtl。当内存淘汰被触发时，会根据配置来调用对应的内存淘汰策略，如果是前两者那么将会根据近似LRU或LFU算法从全部的Key中挑选一部分进行淘汰，如果是后两者则只会从设置了过期时间的Key中挑选一部分进行淘汰。下面作者将以回答问题的方式来进行详细介绍。

1 为什么要使用近似算法而不是传统实现

首先来看LRU（Least recently used，最近最少使用），LRU算法的核心思想是“如果数据最近被访问过，那么将来被访问的几率也高”，所以该算法会选择最近最久没有使用的内容将其淘汰。那么如何实现LRU算法呢？想要淘汰最久没有被使用的数据，那么我们或者需要记录下每个数据的使用时间，或者是维护一个数据结构，该数据结构应该满足两个需求：
（1）通过该数据结构我们能够快速的获取我们想要的最久没有被使用的数据
（2）当我们访问某个数据的时候，需要对该数据结构进行修改并且代价要够低

1.1 传统LRU/LFU算法实现存在的问题

传统的LRU借助哈希表和双向链表来维护了一个数据结构来满足LRU算法的需求，其详细实现可以参考https://juejin.cn/post/7027062270702125093
如果我们采用传统的实现（哈希表+双向链表），那么会存在两个问题：
（1）内存占用的问题，我们需要一个Map来存储每个Key对应到链表中节点的指针，还需要一个链表来维护所有当前在内存中的数据。
（2）并发安全问题，我们每次对数据进行读或写都需要对链表进行更新操作来维护LRU的正确性，由于Slava采用的是多协程并发进行业务处理的工作方式，那么对链表的操作就需要加锁来保证并发安全。那么在高并发的场景下，协程每次读/写操作都需要获取锁来修改链表，会造成大量的阻塞，过于影响运行效率。所以，这种方法不适合Slava高并发的场景。根据上述分析我们可以知道，像传统实现那样维护一个数据结构来满足需求所带来的性能损耗是难以接受的。
而LFU的传统实现同样需要借助哈希表和链表，或是借助堆，使用传统LFU方法带来的性能损耗同样是难以接受的。

1.2 如何去记录每个数据被访问的最近时间和次数

如果我们记录下每个数据最近被访问的时间或是最近被访问的次数，在需要淘汰时遍历数据找出需要淘汰的那个呢？这里首先牵扯到如何记录下每个数据被访问的时间，由于Slava内部k-v数据库对于数据对象的存储方式是将其封装为一个DataEntity对象，也就是在Slava内部数据库中每一个Key都对应了一个DataEntity对象，DataEntity结构体中Data字段被声明为接口类型，从而能够容纳各种数据。我们可以在DataEntity中新增两个字段用于记录数据被访问的最新时间和访问次数。

我们能够在对数据进行Get或Put操作时来对这两个字段进行更改，因为slava内存数据库的实现允许多个协程同时读一个key，所以这里同样可能是多协程并发的，不过这里是对具体Key的读取，除了十分热点的Key，其并发量并不会像读取同一个Map开销那么大，在这里我们可以使用原子操作来保证数据的正确性，而原子操作并不会造成多少性能开销，是可以接受的。此外，Go语言中获取系统时钟并不会进行系统调用，所以从获取时钟到依靠原子操作完成字段值更新，这一过程性能并不会有多大影响。

分析到这里可以发现，记录下每个Key最近被访问的时间和次数是可行的，但是在需要淘汰数据时，对所有数据进行遍历的时间开销过大，是难以接受的。综上所述，我们需要近似算法来实现内存淘汰策略。

2 近似算法的实现

如何实现近似算法呢？前文已经说过，记录下每个Key最近被访问的时间和次数是可行的。我们是否可以不去遍历所有的Key而只随机挑选一些Key，从这些Key中找出最近访问时间最久的一个或是多个去淘汰呢？
事实上在Redis中，对于LRU和LFU的实现采取的正是类似的近似算法，并且证明了其可行性。https://redis.io/docs/reference/eviction/

但作者在了解了Redis的具体实现后发现其实现也并不适合Slava采用（redis对于这部分的具体实现可以参考https://blog.csdn.net/qq_41688840/article/details/122403038），这是因为Redis采用C语言实现，其对于内存的管理是自己来操作的，Redis服务中维护了xxx变量来记录了程序当前使用的内存，在创建/销毁对象时都会更新当前使用内存。Redis在淘汰了一个Key之后会根据当前内存使用量来决定，是否继续进行内存淘汰，由于内存使用量是程序自己维护的，所以判断内存是否超量这一操作几乎没有开销，但在Golang中不同，go的内存并不是由程序员自己管理，如果我们想要获取当前内存的使用量，需要调用`ReadMemStats`函数。而该函数所造成的开销太大，每一次都要stop the world, 也就是停下所有协程。如果我们采取像redis那样的策略，每次删除一个key都要调用`ReadMemStats`函数来让所有协程停下工作，这样造成的开销太大，对于高并发的场景下是不可接受的(作者也在考虑有没有代价更小的获取程序当前内存使用的方式)。

2.1 近似淘汰策略设计

由于没删除一个Key就进行一次内存检查太过奢侈，于是作者就结合了Slava自身的特点（内存数据库由多个分库组成），提出了以下方案：每次随机挑选几个分数据库，然后每个数据库都从自己所存储的Key中进行随机挑选，从挑选中的Key中删除一个，之后再检查内存占用，必要情况下循环进行。这么做的优势有以下几点：

• 基于gorountine，多个分数据库可以异步同时进行操作，同时进行Key的随机挑选，以及遍历挑选出的Key从而确定要删除的数据。同时，由于和业务线程是异步进行的，挑选Key的数量可以设置较大一些，各分库之间操作独立也不会有影响

• 基于sycn.WaitGroup，可以使得我们实现同步等待机制，等待各个协程执行完分库中内容的淘汰策略后，再就行内存占用情况读取，之后再决定是否需要循环执行
• 可以充分利用slava中的分数据库策略，在挑选分数据库时可以优先挑选优先级不高的分数据库进行淘汰，这样可以使得我们优先淘汰优先级不高的数据

2.2 近似淘汰策略实现代码

1. 判断是否需要进行内存淘汰，并根据策略调用具体对应逻辑

func (server *Server) freeMemoryIfNeeded(keyNumsOneRound int, dbNumsOneRound int) {
	var memUsed uint64
	var memStats runtime.MemStats

	for {
		runtime.ReadMemStats(&memStats)
		//memUsed = memStats.HeapAlloc + memStats.HeapIdle // question
		memUsed = memStats.HeapAlloc

		// 不需要清除，直接return
		if memUsed <= server.maxMemory {
			return
		}

		if dbNumsOneRound > len(server.dbSet) {
			dbNumsOneRound = len(server.dbSet)
		}

		// 挑选需要释放key的db，挑选策略可以更改，目前采用简单的随机方式
		dbIds := randomSelectDB(len(server.dbSet), dbNumsOneRound)
		var wg sync.WaitGroup

		for i := 0; i < dbNumsOneRound; i++ {
			slavaDb, _ := server.selectDB(dbIds[i])

			// 暂时不支持random 只支持lru和lfu
			if server.maxMemoryPolicy == maxMemoryLruAllKeys || server.maxMemoryPolicy == maxMemoryLruTtl {
				wg.Add(1)
				if server.maxMemoryPolicy == maxMemoryLruTtl {
					// ttl
					go func() {
						defer wg.Done()
						approximateLruTtl(slavaDb, keyNumsOneRound)
					}()
				} else {
					go func() {
						defer wg.Done()
						approximateLruAll(slavaDb, keyNumsOneRound)
					}()
				}
			}

			if server.maxMemoryPolicy == maxMemoryLfuAllKeys || server.maxMemoryPolicy == maxMemoryLfuTtl {
				wg.Add(1)
				if server.maxMemoryPolicy == maxMemoryLfuTtl {
					// ttl
					go func() {
						defer wg.Done()
						approximateLfuTtl(slavaDb, keyNumsOneRound)
					}()
				} else {
					func() {
						defer wg.Done()
						approximateLfuAll(slavaDb, keyNumsOneRound)
					}()
				}
			}
		}

		// 等待该轮多个db的清除操作完成后再循环
		wg.Wait()
	}
}

2. 分数据库挑选逻辑

func randomSelectDB(dbNums int, selectNums int) []int {
	rand.Seed(time.Now().UnixNano()) // 设置随机数种子，使用当前时间戳

	nums := make(map[int]struct{})

	for i := 0; i < selectNums; i++ {
		num := rand.Intn(dbNums)
		if _, ok := nums[num]; !ok {
			nums[num] = struct{}{}
		}
	}

	result := make([]int, selectNums)
	i := 0
	for key := range nums {
		result[i] = key
		i++
	}

	return result
}

3. 对于某分数据库，从全部Key中挑选部分Key进行比较，并进行淘汰

func approximateLruAll(slavaDb *DB, nums int) {
	data := slavaDb.data.(*dict.ConcurrentDict)
	keyLruMap := data.RandomDistinctKeysWithTime(nums)

	if len(keyLruMap) < 1 {
		return
	}
	var earliestTimestamp int64
	var earliestKey string
	i := 0
	for key, ts := range keyLruMap {
		ts64 := int64(ts)
		t := time.Unix(ts64, 0)
		if i == 0 || t.Before(time.Unix(earliestTimestamp, 0)) {
			earliestTimestamp = ts64
			earliestKey = key
		}
		i++
	}

	slavaDb.Remove(earliestKey)
	return
}

func approximateLfuAll(slavaDb *DB, nums int) {
	data := slavaDb.data.(*dict.ConcurrentDict)
	keyLfuMap := data.RandomDistinctKeysWithCount(nums)

	if len(keyLfuMap) < 1 {
		return
	}
	var minimumCount uint32
	var minimumKey string

	i := 0
	for key, count := range keyLfuMap {
		if i == 0 || count > minimumCount {
			minimumCount = count
			minimumKey = key
		}
		i++
	}

	slavaDb.Remove(minimumKey)
	return
}

4. 对于某分数据库，从设置了过期时间的Key中挑选部分Key进行比较，并进行淘汰

func approximateLruTtl(slavaDb *DB, nums int) {
	data := slavaDb.data.(*dict.ConcurrentDict)
	ttlMap := slavaDb.ttlMap

	candidateKeys := ttlMap.RandomDistinctKeys(nums)
	if len(candidateKeys) < 1 {
		return
	}

	// len(keyLruMap) 可能小于nums
	var earliestTimestamp int64
	var earliestKey string

	for i, key := range candidateKeys {
		val, ok := data.Get(key)
		if ok {
			ts := int64(val.(*database.DataEntity).Lru)
			t := time.Unix(ts, 0)
			if i == 0 || t.Before(time.Unix(earliestTimestamp, 0)) {
				earliestTimestamp = ts
				earliestKey = key
			}
		}
	}

	slavaDb.Remove(earliestKey)
	return
}

func approximateLfuTtl(slavaDb *DB, nums int) {
	data := slavaDb.data.(*dict.ConcurrentDict)
	ttlMap := slavaDb.ttlMap

	candidateKeys := ttlMap.RandomDistinctKeys(nums)
	if len(candidateKeys) < 1 {
		return
	}

	// len(keyLruMap) 可能小于nums
	var minimumCount uint32
	var minimumKey string

	for i, key := range candidateKeys {
		val, ok := data.Get(key)
		if ok {
			count := val.(*database.DataEntity).Lfu
			if i == 0 || count > minimumCount {
				minimumCount = count
				minimumKey = key
			}
		}
	}

	slavaDb.Remove(minimumKey)
	return
}