Анализ исходного кода стратегии удаления памяти Redis и реализация LFU/LRU

0. Пишите впереди

Ссылка на исходный кодgithub redis/evict.c, фиксация -d1a005ab3963c16b65e805675a76f0e40c723158

В процессе нужно напоминать себе, что чтение исходного кода — это изучение деталей реализации, но нельзя зацикливаться на деталях, последовательность анализа соответствует порядку выполнения, чтобы не публиковать большие блоки исходного кода. .

1. Реализация стратегии устранения памяти Redis

Стратегия ликвидации памяти, когда использование памяти превышает конфигурацию, очень хорошая память: без обработки/алгоритм LRU/алгоритм LFU/случайный/срок действия

• noeviction: не будет вытеснять никакие ключи

• allkeys-lru: удалить все ключи по алгоритму LRU

• volatile-lru: Используйте алгоритм LRU для удаления всех ключей с установленным сроком действия.

• allkeys-random:Случайным образом удалить все ключи

• volatile-random: случайным образом удалить все ключи с установленным сроком действия.

• volatile-ttl: Удалить ключ, срок действия которого истекает немедленно.

• allkeys-lfu: удалить все ключи с использованием алгоритма LFU

• volatile-lfu: Используйте алгоритм LFU для удаления всех ключей с установленным сроком действия.

1.1 freeMemoryIfNeededAndSafe: начать освобождать память

Он будет выполняться только тогда, когда ни один lua-скрипт не находится в состоянии тайм-аута и не находится в состоянии загрузки данных.freeMemoryIfNeeded()функция

int freeMemoryIfNeededAndSafe(void) {
    if (server.lua_timedout || server.loading) return C_OK;
    return freeMemoryIfNeeded();
}

1.2 freeMemoryIfNeeded: очистить память в соответствии со стратегией исключения

По умолчанию подчиненные узлы должны игнорироватьmaxmemoryИнструкции, просто сделайте то, что должен делать подчиненный узел

if (server.masterhost && server.repl_slave_ignore_maxmemory) return C_OK;

Если стратегия исключенияnoeviction, тогда Redis может сказать только «Я старался изо всех сил»

if (server.maxmemory_policy == MAXMEMORY_NO_EVICTION)
        goto cant_free; /* We need to free memory, but policy forbids. */

cant_freeЕсть два следующих случая, все, что он может сделать, это проверитьlazyfreeЕсли у потока (должен быть добавлен redis v4) все еще есть задачи, подождите.

• Во-первых, это стратегия устраненияnoeviction
• Во-вторых, в соответствии с текущей стратегией ликвидации «нечего освобождать».

cant_free:
    while(bioPendingJobsOfType(BIO_LAZY_FREE)) {
        if (((mem_reported - zmalloc_used_memory()) + mem_freed) >= mem_tofree)
            break;
        usleep(1000);
    }
    return C_ERR;
}

пройти черезgetMaxmemoryStateФункция (неважная, опущена), получить сколько места освободитьmem_tofrtee, выберите политику, чтобы начать очистку

size_t mem_reported, mem_tofree, mem_freed;
if (getMaxmemoryState(&mem_reported,NULL,&mem_tofree,NULL) == C_OK)
    return C_OK;
mem_freed = 0

while (mem_freed < mem_tofree) {
    // 匹配的key
    sds bestkey = NULL;
    // bestkey所在的db
    int bestdbid;
    // LRU算法/LFU算法/TTL过期时间
    if (server.maxmemory_policy & (MAXMEMORY_FLAG_LRU|MAXMEMORY_FLAG_LFU) || server.maxmemory_policy == MAXMEMORY_VOLATILE_TTL) {
        
    } 
    // 随机淘汰 
    else if (server.maxmemory_policy == MAXMEMORY_ALLKEYS_RANDOM || server.maxmemory_policy == MAXMEMORY_VOLATILE_RANDOM)) {

    }
    // 删除所选的key
    if (bestkey) {
        // 获取当前内存
        delta = (long long) zmalloc_used_memory();
        // 是否非阻塞删除
        if (server.lazyfree_lazy_eviction)
            dbAsyncDelete(db,keyobj);
        else
            dbSyncDelete(db,keyobj);
        // 计算释放了多少内存
        delta -= (long long) zmalloc_used_memory();
        mem_freed += delta;
    } else {
        goto cant_free; /* nothing to free... */
    }
}

1.3 ветки allkeys-random и volatile-random

При выборе случайного исключения он будет проходить через каждую базу данных текущего экземпляра Redis, если все ключи будут удалены и выбраны случайным образом.db->dict, в противном случае выберите набор с установленным временем срока действия:db->expires, Если каждая БДdictSize(dict)все 0, он войдет в вышеупомянутыйcant_freeвторой случай

for (i = 0; i < server.dbnum; i++) {
    j = (++next_db) % server.dbnum;
    db = server.db+j;
    dict = (server.maxmemory_policy == MAXMEMORY_ALLKEYS_RANDOM) ? db->dict : db->expires;
    if (dictSize(dict) != 0) {
        de = dictGetRandomKey(dict);
        bestkey = dictGetKey(de);
        bestdbid = j;
        break;
    }
}

1.4 Ветка lfu/lru/ttl

Связанные определения, известно, что основным полем стратегии исключения являетсяidleэто свойство

#define EVPOOL_SIZE 16
#define EVPOOL_CACHED_SDS_SIZE 255
// 样本集类型
struct evictionPoolEntry {
    unsigned long long idle;    /* Object idle time (inverse frequency for LFU) */
    sds key;                    /* Key name. */
    sds cached;                 /* Cached SDS object for key name. */
    int dbid;                   /* Key DB number. */
};
static struct evictionPoolEntry *EvictionPoolLRU;

Во-первых, инициализируем выборку, и эта часть lru/lfu/ttl отношения не имеет, ядроevictionPoolPopulateфункция

// 初始化样本集合
struct evictionPoolEntry *pool = EvictionPoolLRU;

while (bestkey == NULL) {
    unsigned long total_keys = 0, keys;
    // 遍历每一个db，更新/维护pool样本集
    for (i = 0; i < server.dbnum; i++) {
        db = server.db+i;
        dict = (server.maxmemory_policy & MAXMEMORY_FLAG_ALLKEYS) ? db->dict : db->expires;
        if ((keys = dictSize(dict)) != 0) {
            // 四个参数可以理解为：dbid, 候选集合(db->dict/db->expires), 完整集合(db->dict), 样本集合
            evictionPoolPopulate(i, dict, db->dict, pool);
            total_keys += keys;
        }
    }
    // 无key可淘汰
    if (!total_keys) break;
    // 从后向前遍历, 并重置样本集
    for (k = EVPOOL_SIZE-1; k >= 0; k--) {
        if (pool[k].key == NULL) continue;
        bestdbid = pool[k].dbid;
       
        if (server.maxmemory_policy & MAXMEMORY_FLAG_ALLKEYS) {
            de = dictFind(server.db[pool[k].dbid].dict,pool[k].key);
        } else {
            de = dictFind(server.db[pool[k].dbid].expires,pool[k].key);
        }
        pool[k].key = NULL;
        pool[k].idle = 0;

        // 寻找到bestkey，break
        if (de) {
            bestkey = dictGetKey(de);
            break;
        }
    }    
}

1.5 evictionPoolPopulate: алгоритм LRU/LFU

Во-первых, согласноmaxmemory_samplesКонфигурация, выберите определенное количество выборок, это значение по умолчанию равно 5, чем выше значение, тем ближе к реальному алгоритму LRU/LFU, чем ниже значение, тем выше производительность, поэтому его необходимо сбалансировать

count = dictGetSomeKeys(sampledict,samples,server.maxmemory_samples);
for (j = 0; j < count; j++) {
    // 见下一个代码块
}

Траверс, вычисление значения каждой выборки в соответствии со стратегиейidleЗначение, чем выше значение, тем выше степень соответствия, приоритет для удаления

• volatile-ttlРасчет полисаidleМетод значения: поставить те, срок действия которых скоро истечет
• lruМетод расчета стратегии: ставить на первое место те, которые давно не посещались
• lfuМетод расчета полиса: Частота доступа ниже, а частота такая же.Сравните кто давно не заходил.

if (server.maxmemory_policy & MAXMEMORY_FLAG_LRU) {
    idle = estimateObjectIdleTime(o);
} else if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
    idle = 255-LFUDecrAndReturn(o);
} else if (server.maxmemory_policy == MAXMEMORY_VOLATILE_TTL) {
    idle = ULLONG_MAX - (long)dictGetVal(de);
} else {
    serverPanic("Unknown eviction policy in evictionPoolPopulate()");
}
// 然后维护样本集即可，后面的代码省略了

1.6 Реализация Redis LRU

Redis поддерживает 24-битные глобальные часы, которые можно просто понимать как отметку времени текущей системы.Эти часы будут обновляться через регулярные промежутки времени, которые здесь не будут раскрываться.

// server.h 595行
#define LRU_BITS 24  // 24bit的时钟
#define LRU_CLOCK_MAX ((1<<LRU_BITS)-1) // obj->lru时钟的最大值
#define LRU_CLOCK_RESOLUTION 1000 // 时钟精度，毫秒

// server.h 1017行
stuct redisServer {
    // Clock for LRU eviction
    _Atomic unsigned int lruclock;
}

Каждый ключевой объект также поддерживает 24-битные часы, которые будут использоваться позже.o->lruОтносится к

// server.h 600行
typedef struct redisObject {
    // LRU time (relative to global lru_clock)
    unsigned lru:LRU_BITS
}

Установите глобальные lruclock, когда значение lruclock превысит LRU_CLOCK_MAX, оно начнется с нуля

// src/evict.c 70行
unsigned int getLRUClock(void) {
    return (mstime()/LRU_CLOCK_RESOLUTION) & LRU_CLOCK_MAX;
}

настраиватьo->lru, при добавлении ключевого объекта системные часы будут назначены этим внутренним часам объекта

// src/evict.c 78行
unsigned int LRU_CLOCK(void) {
    unsigned int lruclock;
    if (1000/server.hz <= LRU_CLOCK_RESOLUTION) {
        lruclock = server.lruclock;
    } else {
        lruclock = getLRUClock();
    }
    return lruclock;
}

Например, если вы хотите выполнить LRU сейчас, вам нужно сравнитьlruclockа такжеo->lru, у них два корпуса

• lruclock >= o->lru: Это обычно дело
• lruclock < o->lru: когда значение lruclock превышает LRU_CLOCK_MAX, оно будет рассчитываться с самого начала, поэтому возникает такая ситуация, и необходимо рассчитывать дополнительное время.

// src/evict.c 88行
unsigned long long estimateObjectIdleTime(robj *o) {
    unsigned long long lruclock = LRU_CLOCK();
    if (lruclock >= o->lru) {
        return (lruclock - o->lru) * LRU_CLOCK_RESOLUTION;
    } else {
        return (lruclock + (LRU_CLOCK_MAX - o->lru)) * LRU_CLOCK_RESOLUTION;
    }
}

Реализацию redis lfu можно охарактеризовать как невнятную, скучная, лучше делать leetcode

2. Реализация LRU golang

package problem0146

// 双向链表结构
type LinkNode struct {
	key, value int
	pre, next  *LinkNode
}

// LRU结构
type LRUCache struct {
	m          map[int]*LinkNode
	cap        int
	head, tail *LinkNode
}

func Constructor(capacity int) LRUCache {
	head := &LinkNode{0, 0, nil, nil}
	tail := &LinkNode{0, 0, nil, nil}
	head.next = tail
	tail.pre = head
	return LRUCache{make(map[int]*LinkNode, capacity), capacity, head, tail}
}

func (this *LRUCache) moveToHead(node *LinkNode) {
	this.removeNode(node)
	this.addNode(node)
}

func (this *LRUCache) removeNode(node *LinkNode) {
	node.pre.next = node.next
	node.next.pre = node.pre
}

func (this *LRUCache) addNode(node *LinkNode) {
	head := this.head
	node.next = head.next
	node.next.pre = node
	node.pre = head
	head.next = node
}

// 如果有，将这个元素移动到首位置，返回值
// 如果没有，返回-1
func (this *LRUCache) Get(key int) int {
	if v, exist := this.m[key]; exist {
		this.moveToHead(v)
		return v.value
	} else {
		return -1
	}
}

// 如果元素存在，将其移动到最前面，并更新值
// 如果元素不存在，插入到元素首，放入map（判断容量）
func (this *LRUCache) Put(key int, value int) {
	tail := this.tail
	cache := this.m
	if v, exist := cache[key]; exist {
		v.value = value
		this.moveToHead(v)
	} else {
		v := &LinkNode{key, value, nil, nil}
		if len(this.m) == this.cap {
			delete(cache, tail.pre.key)
			this.removeNode(tail.pre)
		}
		this.addNode(v)
		cache[key] = v
	}
}

3. Реализация LFU golang

package problem0460

// LRU: Least Recently Used，缓存满的时候，删除缓存里最久未使用的数据，然后放入新元素
// LFU: Least Frequently Used，缓存满的时候，删除缓存里使用次数最少的元素，然后放入新元素，如果使用频率一样，删除缓存最久的元素

// 节点：包含key, value, frequent访问次数, pre前驱指针, next后继指针
type Node struct {
	key, value, frequent int
	pre, next            *Node
}

// 双向链表：包含head头指针, tail尾指针, size尺寸
type ListNode struct {
	head, tail *Node
	size       int
}

// 双向链表辅助函数：添加一个节点到头节点后
func (this *ListNode) addNode(node *Node) {
	head := this.head
	node.next = head.next
	node.next.pre = node
	node.pre = head
	head.next = node
}

// 双向链表辅助函数，删除一个节点
func (this *ListNode) removeNode(node *Node) {
	node.pre.next = node.next
	node.next.pre = node.pre
}

// LFUCache结构：包含capacity容量, size当前容量, minFrequent当前最少访问频次, cacheMap缓存哈希表, frequentMap频次哈希表
// minFrequent当前最少访问频次：
// 1. 插入一个新节点时，之前肯定没访问过，minFrequent = 1
// 2. put和get时，如果移除后双向链表节点个数为0，且恰好是最小访问链表, minFrequent++
type LFUCache struct {
	capacity, size, minFrequent int
	cacheMap                    map[int]*Node
	frequentMap                 map[int]*ListNode
}

func Constructor(capacity int) LFUCache {
	return LFUCache{
		capacity:    capacity,
		size:        0,
		minFrequent: 0,
		cacheMap:    make(map[int]*Node),
		frequentMap: make(map[int]*ListNode),
	}
}

// LFUCache辅助函数：将节点从对应的频次双向链表中删除
func (this *LFUCache) remove(node *Node) {
	this.frequentMap[node.frequent].removeNode(node)
	this.frequentMap[node.frequent].size--
}

// LFUCache辅助函数：将节点添加进对应的频次双向链表，没有则创建
func (this *LFUCache) add(node *Node) {
	if listNode, exist := this.frequentMap[node.frequent]; exist {
		listNode.addNode(node)
		listNode.size++
	} else {
		listNode = &ListNode{&Node{}, &Node{}, 0}
		listNode.head.next = listNode.tail
		listNode.tail.pre = listNode.head
		listNode.addNode(node)
		listNode.size++
		this.frequentMap[node.frequent] = listNode
	}
}

// LFUCache辅助函数：移除一个key
func (this *LFUCache) evictNode() {
	listNode := this.frequentMap[this.minFrequent]
	delete(this.cacheMap, listNode.tail.pre.key)
	listNode.removeNode(listNode.tail.pre)
	listNode.size--
}

// LFUCache辅助函数：获取一个key和修改一个key都会增加对应key的访问频次，可以独立为一个方法，完成如下任务：
// 1. 将对应node从频次列表中移出
// 2. 维护minFrequent
// 3. 该节点访问频次++，移动进下一个访问频次链表
func (this *LFUCache) triggerVisit(node *Node) {
	this.remove(node)
	if node.frequent == this.minFrequent && this.frequentMap[node.frequent].size == 0 {
		this.minFrequent++
	}
	node.frequent++
	this.add(node)
}

func (this *LFUCache) Get(key int) int {
	if node, exist := this.cacheMap[key]; exist {
		this.triggerVisit(node)
		return node.value
	}
	return -1
}

func (this *LFUCache) Put(key int, value int) {
	if this.capacity == 0 {
		return
	}
	if node, exist := this.cacheMap[key]; exist {
		this.triggerVisit(node)
		this.cacheMap[key].value = value
	} else {
		newNode := &Node{key, value, 1, nil, nil}
		if this.size < this.capacity {
			this.add(newNode)
			this.size++
			this.minFrequent = 1
		} else {
			this.evictNode()
			this.add(newNode)
			this.minFrequent = 1
		}
		this.cacheMap[key] = newNode
	}
}