Slava項目（1）：實現近似LRU/LFU記憶體淘汰策略

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中新增兩個欄位用於記錄數據被訪問的最新時間和訪問次數。

分析到這裡可以發現，記錄下每個Key最近被訪問的時間和次數是可行的，但是在需要淘汰數據時，對所有數據進行遍歷的時間開銷過大，是難以接受的。綜上所述，我們需要近似演算法來實現記憶體淘汰策略。

2 近似演算法的實現

如何實現近似演算法呢？前文已經說過，記錄下每個Key最近被訪問的時間和次數是可行的。我們是否可以不去遍歷所有的Key而只隨機挑選一些Key，從這些Key中找出最近訪問時間最久的一個或是多個去淘汰呢？
事實上在Redis中，對於LRU和LFU的實現採取的正是類似的近似演算法，並且證明瞭其可行性。https://redis.io/docs/reference/eviction/

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
}