redis的内存满了之后,redis如何回收内存

原创
06/22 16:50
阅读数 1.2W

作者:沈熠辉

来源:恒生LIGHT云社区

Redis使用场景

现在公司的业务越来越复杂,我们需要抽出一个用户系统,向各个业务系统提供用户的基本信息。

业务001.jpg

 

业务方对用户信息的查询频率很高,一定要注意性能问题哦。

用户信息当然是存放在数据库里,但是由于我们对用户系统的性能要求比较高,显然不能在每一次请求时都去查询数据库。

所以,在内存中创建了一个哈希表作为缓存,每当查找一个用户时会先在哈希表中进行查询,以此来提高访问的性能。

业务002.jpg

很快发现了个问题

线上服务器宕机了!

糟了,是内存溢出了,用户数量越来越多,当初设计的哈希表把内存给撑爆了,赶紧重启吧!

可是以后该怎么办呢?我们能不能给服务器的硬件升级,或者加几台服务器呀?

那我能不能在内存快耗尽的时候,随机删掉一半用户缓存呢?

唉,这样也不妥,如果删掉的用户信息,正好是被高频查询的用户,会影响系统性能的。

你听说过LRU算法吗?

LRU全称Least Recently Used,也就是最近最少使用的意思,是一种内存管理算法,该算法最早应用于Linux操作系统。

这个算法基于一种假设:长期不被使用的数据,在未来被用到的概率也不大。因此,当数据所占内存达到一定阈值时,我们要移除最近最少被使用的数据。

原来如此,这个算法正好对我的用户系统有帮助!可以在内存不够时,从哈希表中移除一部分很少被访问的用户。

可是,我怎么知道哈希表中哪些Key-Value最近被访问过,哪些没被访问过?总不能给每一个Value加上时间戳,然后遍历整个哈希表吧?

这就能展现LRU算法的精妙所在了。在LRU算法中,使用了一种有趣的数据结构,这种数据结构叫作哈希链表。

什么是哈希链表呢?

我们都知道,哈希表是由若干个Key-Value组成的。在“逻辑”上,这些Key-Value是无所谓排列顺序的,谁先谁后都一样。

哈希链表01.jpg

在哈希链表中,这些Key-Value不再是彼此无关的了,而是被一个链条串了起来。每一个Key-Value都具有它的前驱Key-Value、后继Key-Value,就像双向链表中的节点一样。

用户信息02.jpg

这样一来,原本无序的哈希表就拥有了固定的排列顺序。

可是,这哈希链表和LRU算法有什么关系呢?

依靠哈希链表的有序性,我们可以把Key-Value按照最后的使用时间进行排序。

让我们以用户信息的需求为例,来演示一下LRU算法的基本思路。

1.假设使用哈希链表来缓存用户信息,目前缓存了4个用户,这4个用户是按照被访问的时间顺序依次从链表右端插入的。

用户信息03.jpg

用户信息04.jpg

4.接下来,如果业务方请求修改用户4的信息。同样的道理,我们会把用户4从原来 的位置移动到链表的最右侧,并把用户信息的值更新。这时,链表的最右端是最新被访问的用户4,最左端仍然是最近最少被访问的用户1。

用户信息05.jpg

用户信息06.jpg

5.后来业务方又要访问用户6,用户6在缓存里没有,需要插入哈希链表中。假设这时缓存容量已经达到上限,必须先删除最近最少被访问的数据,那么位于哈希链表最左端的用户1就会被删除,然后再把用户6插入最右端的位置。

用户信息07.jpg用户信息08.jpg

以上,就是LRU算法的基本思路。

明白了,这真是个巧妙的算法!那么LRU算法怎么用代码来实现呢?

简单实现

class LRUCache:
    def __init__(self,limit):
        self.limit=limit
        self.hash={}
        self.head=None
        self.end=None
    def get(self,key):
        node=self.hash.get(key)
        if node is None:
            return None
        self.refresh_node(node)
        return node.value
    def put(self,key,value):
        node=self.hash.get(key)
        if node is None:
            #如果key不存在,插入key-value
            if len(self.hash) >= self.limit:
                old_key=self.remove_node(self.head)
                self.hash.pop(old_key)
            node=Node(key,value)
            self.add_node(node)
            self.hash[key]=node
        else:
            #如果key存在,刷新key-value
            node.value=value
            self.refresh_node(node)
    def remove(self,key):
        node=self.hash.get(key)
        self.remove_node(node)
        self.hash.remove(key)
    def refresh_node(self,node):
        #如果访问的是尾节点,无需移动节点
        if node==self.end:
           return
        #移除节点
        self.remove_node(node)
        #重新插入节点
        self.add_node(node)
    def remove_node(self,node):
        if node==self.head and node==self.end:
            #移除唯一的节点
            self.head=None
            self.end=None
        elif node==self.end:
            #移除节点
            self.end=self.end.pre
            self.end.next=None
        elif node==self.head:
            #移除头节点
            self.head=self.head.next
            self.head.pre=None
        else:
            #移除中间节点
            node.pre.next=node.next
            node.next.pre=node.pre
        return node.key
    def add_node(self,node):
        if self.end is not None:
            self.end.next=node
            node.pre=self.end
            node.next=None
        self.end=node
        if self.head is None:
           self.head=node

class Node:
    def __init__(self,key,value):
        self.key=key
        self.value=value
        self.pre=None
        self.next=None

lruCache=LRUCache(5)

lruCache.put("001","用户1信息")
lruCache.put("002","用户2信息")
lruCache.put("003","用户3信息")
lruCache.put("004","用户4信息")
lruCache.put("005","用户5信息")

print(lruCache.get("001"))
print(lruCache.get("002"))
print(lruCache.get("003"))
print(lruCache.get("004"))
print(lruCache.get("005"))
lruCache.refresh_node(lruCache.hash.get("002"))
print(lruCache.hash.get("001").next.value)
print(lruCache.hash.get("003").pre.value)

print(lruCache.hash.get("002").value)
展开阅读全文
打赏
1
8 收藏
分享
加载中
#移除中间节点
node.pre.next=node.pre
node.next.pre=node.pre
是不是写的不对啊,
node.pre.next=node.next 应该是这样吧?
06/25 11:54
回复
举报
恒生LIGHT云社区恒生电子股份有限公司博主
感谢提醒!已更正
06/25 14:25
回复
举报
更多评论
打赏
2 评论
8 收藏
1
分享
返回顶部
顶部