加入收藏 | 设为首页 | 会员中心 | 我要投稿 南平站长网 （https://www.0599zz.com/）- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置： 首页 > 运营中心 > 交互 > 正文

redis lru实现策略

发布时间：2016-11-01 04:34:41 所属栏目：交互 来源：站长网
导读：副标题#e# 在使用redis作为缓存的场景下，内存淘汰策略决定的redis的内存使用效率。在大部分场景下，我们会采用LRU(Least Recently Used)来作为redis的淘汰策略。本文将由浅入深的介绍redislru策略的具体实现。 首先我们来科普下，什么是LRU ？(以下来自维
副标题[/!--empirenews.page--]      在使用redis作为缓存的场景下，内存淘汰策略决定的redis的内存使用效率。在大部分场景下，我们会采用LRU(Least Recently Used)来作为redis的淘汰策略。本文将由浅入深的介绍redis lru策略的具体实现。
       首先我们来科普下，什么是LRU ？(以下来自维基百科) 
       Discards the least recently used items first. This algorithm requires keeping track of what was used when, which is expensive if one wants to make sure the algorithm always discards the least recently used item. General implementations of this technique require keeping "age bits" for cache-lines and track the "Least Recently Used"  cache-line based on age-bits. In such an implementation, every time a cache-line is used, the age of all other cache-lines changes.
      简而言之，就是每次淘汰最近最少使用的元素 。一般的实现，都是采用对存储在内存的元素采用 'age bits’ 来标记该元素从上次访问到现在为止的时长，从而在每次用LRU淘汰时，淘汰这些最长时间未被访问的元素。
    
      这里我们先实现一个简单的LRU Cache，以便于后续内容的理解 。(来自leetcod,不过这里我重新用Python语言实现了)       实现该缓存满足如下两点:
      1.get(key) - 如果该元素(总是正数)存在，将该元素移动到lru头部，并返回该元素的值，否则返回-1。
      2.set(key,value) - 设置一个key的值为value(如果该元素存在),并将该元素移动到LRU头部。否则插入一个key,且值为value。如果在设置前检查到，该key插入后，会超过cache的容量，则根据LRU策略，删除最近最少使用的key。
       分析
      这里我们采用双向链表来实现元素(k-v键值对)的存储，同时采用hash表来存储相关的key与item的对应关系。这样，我们既能在O(1)的时间对key进行操作，同时又能利用Double LinkedList的添加和删除节点的便利性。(get/set都能在O(1)内完成)。

    redis lru实现策略
 具体实现(Python语言)

点击(此处)折叠或打开

  1. class Node:
  2.       key=None
  3.       value=None
  4.       pre=None
  5.       next=None

  7. def __init__(self,key,value):
  8.       self.key=key
  9.       self.value=value

  11. class LRUCache:
  12.       capacity=0
  13.       map={} # key is string ,and value is Node object
  14.       head=None
  15.       end=None

  17. def __init__(self,capacity):
  18.       self.capacity=capacity

  20. def get(self,key):
  21.       if key in self.map:
  22.            node=self.map[key]
  23.            self.remove(node)
  24.            self.setHead(node)
  25.            return node.value
  26.       else:
  27.           return -1

  29. def getAllKeys(self):
  30.        tmpNode=None
  31.        if self.head:
  32.           tmpNode=self.head
  33.           while tmpNode:
  34.           print (tmpNode.key,tmpNode.value)
  35.           tmpNode=tmpNode.next

  37. def remove(self,n):
  38.       if n.pre:
  39.          n.pre.next=n.next
  40.       else:
  41.          self.head=n.next

  43.       if n.next:
  44.          n.next.pre=n.pre
  45.       else:
  46.          self.end=n.pre

  48. def setHead(self,n):
  49.       n.next=self.head
  50.       n.pre=None

  52.       if self.head:
  53.          self.head.pre=n

  55.       self.head=n

  57.       if not self.end:
  58.          self.end=self.head

  60. def set(self,key,value):
  61.        if key in self.map:
  62.           oldNode=self.map[key]
  63.           oldNode.value=value
  64.           self.remove(oldNode)
  65.           self.setHead(oldNode)
  66.        else:
  67.           node=Node(key,value)
  68.           if len(self.map) >= self.capacity:
  69.              self.map.pop(self.end.key)
  70.              self.remove(self.end)
  71.              self.setHead(node)
  72.           else:
  73.              self.setHead(node)

  75.           self.map[key]=node


  78. def main():
  79.        cache=LRUCache(100)

  81.        #d->c->b->a
  82.        cache.set('a','1')
  83.        cache.set('b','2')
  84.        cache.set('c',3)
  85.        cache.set('d',4)

  87.        #遍历lru链表
  88.        cache.getAllKeys()

  90.        #修改('a','1') ==> ('a',5),使该节点从LRU尾端移动到开头.
  91.        cache.set('a',5)
  92.        #LRU链表变为 a->d->c->b

  94.        cache.getAllKeys()
  95.        #访问key='c'的节点，是该节点从移动到LRU头部
  96.        cache.get('c')
  97.        #LRU链表变为 c->a->d->b
  98.        cache.getAllKeys()

  100.        if __name__ == '__main__':
  101.           main()
     通过上面简单的介绍与实现，现在我们基本已经了解了什么是LRU，下面我们来看看LRU算法在redis 内部的实现细节，以及其会在什么情况下带来问题。在redis内部，是通过全局结构体struct redisServer 保存redis启动之后相关的信息，比如:

（编辑：南平站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
相关内容
    推荐文章
    站长推荐
    热点阅读

      【免责声明】本站内容转载自互联网，其发布内容言论不代表本站观点，如果其链接、内容的侵犯您的权益，烦请提交相关链接至邮箱bqsm@foxmail.com我们将及时予以处理。

      建议您使用1920×1080分辨率、谷歌浏览器Google Chrome、Microsoft Edge以获得本站的最佳浏览效果

      Copygight © 2008-2022 https://www.0599zz.com/ All Rights Reserved. 南平站长网