V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
rikka
V2EX  ›  程序员

[数据结构算法求助] 如何实现这样一个数据容器,缓存 key-value 数据?(javascript)

  •  
  •   rikka · 2020-07-11 15:32:23 +08:00 · 2611 次点击
    这是一个创建于 1356 天前的主题,其中的信息可能已经有所发展或是发生改变。

    背景需求是,需要一个简单的数据容器对一堆 key-value 进行缓存(什么 redis,memcache 通通都不要,我就想简单的在内存存点数据而已)

    容器有两个要求

    1.固定容量,满了之后插入新数据就要删除旧数据,删除算法的指导思想是,删除那些越旧读取次数越少的数据

    2.数据有效时间,比如设置 10 分钟,10 分钟后读取里面某条数据就应该删掉这条数据并返回 undefined

    感觉很简单啊,我用个 Map 来实现就可以了

    data = new Map()
    data.set(key,{
      value:'',//存放的具体数据
      timestamp:0,//时间戳,判断是否过期用
      count:0//数据被读取的次数
    })
    

    但是问题来了,要插入新数据容器已经满了,怎么删除?

    我不得根据 timestamp 和 count 这 2 个字段对全部数据进行排序?

    排序就得遍历啊,极端情况要是 10 万条数据,每次删除都得遍历一下,这哪受得了

    卡在这了,Map 似乎不行?应该选择什么样数据结构和算法来实现这个容器最合适?

    第 1 条附言  ·  2020-07-12 15:22:35 +08:00
    大家都提到了 LRU,我就学习研究一番,感觉很精妙啊,目前我用 LRU 实现出来了



    然后发现 LRU 实现出来有点问题,我的要求之一是数据有个有效期,而 LRU 只会删除队列最后一个

    这样存在一种情况,队列最后一个数据没过期,但是倒数第二个是过期了,LRU 会把最后这个没过期的删掉了,但是实际上倒数第二个更加应该被删除才对
    第 2 条附言  ·  2020-07-12 16:03:36 +08:00
    补充下删除算法要求,数据过期是最优先应该被删除的,然后数据的新旧程度和读取次数这 2 个权重,我感觉哪个优先都行
    第 3 条附言  ·  2020-07-13 17:22:17 +08:00
    记录下

    LRU 已经学习理解得很 OK 代码也写出来了,然后继续学习 LFU,这个就有点复杂了

    看了这篇文章 https://leetcode-cn.com/problems/lfu-cache/solution/chao-xiang-xi-tu-jie-dong-tu-yan-shi-460-lfuhuan-c/
    基本上弄懂了

    总结下:
    LRU 是根据数据的读取时间这一个维度来排列数据,关键点就是数据一旦被读取就会把数据调到队头去,它的实现是需要一个哈希表+一个双向链表
    LFU 是根据数据的读取时间和访问频率两个维度来排列数据,LFU 实际上是包含了 LRU 的思想在里面,实现是需要两个哈希表+N 个双向链表,代码复杂点,空间复杂度也会高点

    LFU 感觉更加科学合理一点,更加符合我的要求
    第 4 条附言  ·  2020-07-14 18:37:32 +08:00
    最终,在 LRU 的基础上,增加一个双向链表按时间顺序记录时间戳,以实现“不定时不遍历”,去最优先删除过期数据的目标~~任务圆满完成~~

    代码以更新


    感谢参与讨论的各位
    39 条回复    2020-07-15 16:55:56 +08:00
    aijam
        1
    aijam  
       2020-07-11 15:37:18 +08:00
    luckyrayyy
        2
    luckyrayyy  
       2020-07-11 15:39:01 +08:00
    第一个要求不就是 lfu 么,然后用懒删除策略,每次操作的时候判断创建的时间戳是不是超过了十分钟,超过的话就删除并且返回 undefined 。
    DonaldY
        3
    DonaldY  
       2020-07-11 15:41:27 +08:00
    LRU 。

    删除的话:
    1. 定时遍历删除
    2. 获取数据时,判断时间是否过期,过期则删除。

    唉,这个我之前写过。
    nightwitch
        4
    nightwitch  
       2020-07-11 15:41:29 +08:00
    维护一个堆结构,保持大致有序就可以了
    rikka
        5
    rikka  
    OP
       2020-07-11 15:51:23 +08:00
    @luckyrayyy #2
    @DonaldY #3
    过期这个都比较好处理
    极端情况 10 万条,都没过期,现在要插入新的,怎么删,不得遍历

    定时删除暂不考虑,这不还得额外弄个线程干这事,增加复杂度,你要是做 redis,memcache 这样的东西,定时就很合理很必要
    rabbbit
        6
    rabbbit  
       2020-07-11 15:56:54 +08:00
    必须用 map 吗, key 的类型没有限制?
    rikka
        7
    rikka  
    OP
       2020-07-11 16:02:38 +08:00
    @rabbbit #6 map 我感觉不行,key 类型不是关键啊
    kamal
        8
    kamal  
       2020-07-11 16:04:27 +08:00   ❤️ 1
    如果时间和读取次数没有冲突的话,把条件改成时间久的删除,正常的读取变成删除+插入。
    chihiro2014
        9
    chihiro2014  
       2020-07-11 16:11:37 +08:00
    @rikka 不得遍历,hash 直接 O(1)查找然后删除不行么?
    rabbbit
        10
    rabbbit  
       2020-07-11 16:16:06 +08:00
    js 是单线程的, 大量数据定时遍历不就卡死了吗?
    还是建议访问的时候再删.

    class Cache {
      time = {};
      data = {};
      constructor(cleanInterval = 1000 * 60 * 10) {
       this.cleanInterval = cleanInterval;
     }
      get(key) {
       if (this.data[key]) {
        if (Date.now() - this.time[key] < this.cleanInterval) {
         return this.data[key];
       } else {
         delete this.data[key];
         delete this.time[key];
       }
      }
     }

      set(key, value) {
       this.data[key] = value;
       this.time[key] = Date.now();
     }
    }

    const c = new Cache(100);
    c.set('a', 1);
    setTimeout(() => {
      console.log(c.get('a'));
    }, 1000);
    ipwx
        11
    ipwx  
       2020-07-11 16:16:36 +08:00
    @rikka 就是 LRU 。你随便找个语言看看别人怎么实现 LRU cache 的就懂了。
    rikka
        12
    rikka  
    OP
       2020-07-11 16:17:18 +08:00
    @kamal #8 时间和读取次数本来就没啥冲突啊,你这意思是读取变成会更新时间??
    ipwx
        13
    ipwx  
       2020-07-11 16:17:18 +08:00
    顺便常见的 LRU 实现方案是一个哈希表 + 一个链表。细节自己去搜索。
    ipwx
        14
    ipwx  
       2020-07-11 16:17:57 +08:00
    emmm 可能是一个哈希表 + 两个链表…… 这不是重点,反正是有方案的
    rikka
        15
    rikka  
    OP
       2020-07-11 16:19:19 +08:00
    @chihiro2014 #9 O(1)前提是你得知道 key 啊,问题是删除的时候根本不知道 key 是什么,得遍历根据条件去找符合要求的 key 然后删除啊
    rikka
        16
    rikka  
    OP
       2020-07-11 16:20:19 +08:00
    @ipwx #14 行吧都说是 LRU,我研究学习下。。。
    noe132
        17
    noe132  
       2020-07-11 16:20:40 +08:00
    leapV3
        18
    leapV3  
       2020-07-11 16:24:27 +08:00
    LRU
    hashmap
    kamal
        19
    kamal  
       2020-07-11 16:29:35 +08:00
    @rikka #12 是的,变成了按照时间排序的数组或者链表。
    正常读取:读取-删除-(未过期)-插入队首-返回
    超时:读取-删除-(已过期)-返回空
    长度超出;读取-删除-插入队首-删除队尾-返回
    rabbbit
        20
    rabbbit  
       2020-07-11 16:34:08 +08:00
    抱歉,我看错帖子要求了.我上面那个回复真是错到离谱了.
    rikka
        21
    rikka  
    OP
       2020-07-11 16:47:56 +08:00
    @kamal #19 这思路感觉有点行啊,这么搞,如果一个数据(没过期)频繁被读取就会一直保持在队列前面,需要删除的时候就不容易被删,那些没怎么被读取的就会随着队列调整落在队尾,随时准备被删除~~
    renmu123
        22
    renmu123  
       2020-07-11 17:08:34 +08:00 via Android
    你看一下 Redis 的实现就可以了
    di94sh
        23
    di94sh  
       2020-07-11 20:31:22 +08:00 via iPhone
    找个 cachetools 之类的库呗
    xiaoming1992
        24
    xiaoming1992  
       2020-07-12 05:01:04 +08:00 via Android
    删除算法的指导思想是,删除那些越旧读取次数越少的数据

    权重怎么样呢?一个 1s 前读取 1 次的数据、和一个 2s 前读取 2 次的数据,应该删除哪个呢?
    zifangsky
        25
    zifangsky  
       2020-07-12 13:27:05 +08:00
    “删除那些越旧读取次数越少的数据”?到底是删除最旧的数据( LRU )还是删除访问次数最少的数据( LFU )?
    rikka
        26
    rikka  
    OP
       2020-07-12 15:20:01 +08:00
    @xiaoming1992 #24
    @zifangsky #25

    其实都可以,目前我用 LRU 实现出来了
    https://gist.github.com/mkanako/e8a279aa2ffd946bf7b3fd9c26479ef7


    然后发现 LRU 实现出来有点问题,我的要求之一是数据有个有效期,而 LRU 只会删除队列最后一个

    这样存在一种情况,队列最后一个数据没过期,但是倒数第二个是过期了,LRU 把最后这个没过期的删掉了,但是实际上倒数第二个更加应该被删除才对
    stardust21
        27
    stardust21  
       2020-07-12 15:32:22 +08:00
    @rikka 如果没满不删除也没影响,满了就先遍历删除过期的,再走 LRU 的逻辑
    rikka
        28
    rikka  
    OP
       2020-07-12 15:49:19 +08:00
    @stardust21 #27 删除肯定是满了才进行删除的,遍历也不太行,极端情况存了 10 万个数据,准备删除,难道先遍历看看谁过期了在删除?好吧,那万一要是全都没过期,那就很尴尬白忙活,只能乖乖按照 LRU 删最后一个
    saberlong
        29
    saberlong  
       2020-07-12 18:33:11 +08:00 via Android
    LRU 变种啊,你是需要按时间删除和按最少访问删除。那么用 2 个链表。定时对超时部分删除。每次满的时候针对最少访问删除。
    shellus
        30
    shellus  
       2020-07-12 21:54:45 +08:00
    0:在写入 key 的时候,将其索引写到要删除的按 10 分钟一个的数组里面,例如 15 分钟过期,就 deleteArr[20].push(key)
    1:在第 20 分钟删除这些 keys,就不用遍历了
    2:读取 key 的时候,检查 key 的过期时间,过期就返回 null (这时候真实删除 key 也可以,因为读取到 null 一般紧跟着缓存更新)
    2:如果在定时删除前,有新的 key 要使用同样的 name,就真实删除这个 key,也不用遍历
    rikka
        31
    rikka  
    OP
       2020-07-12 22:57:57 +08:00
    @saberlong #29
    @shellus #30

    你说“定时”什么的,这不就得依赖系统时钟,增加额外的线程。当然实际项目完全可以这么干,有了“定时”,事情也就变得很简单了

    而我其实是希望用纯数据结构纯算法来完成这个事,给自己增加点挑战~~
    saberlong
        32
    saberlong  
       2020-07-12 23:54:58 +08:00 via Android
    @rikka 定时只是清理策略实现方式上的选择,不影响核心数据结构。只是将超时的判定和超过内存阀值这两个条件分开写,各管各的,实现起来更清晰,并且及时清理超时而已。合并起来也可以做清理策略。比如在触发清理时,先清理超时的,然后判定是否清理得足够多,不够再清理最少访问的就行了。然后需要在查询的地方补上超时判定。本质还是 LRU,只是根据需要做简单修改而已。我觉得你自己思考就明白了
    wangritian
        33
    wangritian  
       2020-07-13 10:29:16 +08:00
    LRU 的基础上,增加一块环形内存,记录时间戳和缓存 key 或地址,从左向右是时间递增的,指针 P 记录当前环形起点。当缓存队列已满需要 set 时,优先读取 P 指向的时间戳,如果没过期,执行 LRU 算法;如果过期,则替换 P 指向的 key 、value 、时间戳,然后 P 右移一位,不执行 LRU 。不知道这个方案有没有问题。
    rikka
        34
    rikka  
    OP
       2020-07-13 15:54:13 +08:00
    @saberlong #32 能明白,不过暂时不考虑这种方式
    rikka
        35
    rikka  
    OP
       2020-07-13 15:58:05 +08:00
    @wangritian #33 我也差不多想到这了,感觉很行啊

    需要增加一个双向链表,按时间顺序放入数据
    当需要删除的时候,首先到这个链表取第一个数据,看看有没有过期,过期就删这个数据,没有就继续走 LRU 的逻辑

    等我抽空来实现~~
    zifangsky
        36
    zifangsky  
       2020-07-13 17:38:28 +08:00
    你可以再参考下我实现的 LRU 算法,自我感觉还是比较完善的,不过我是用的 Java 实现: https://gitee.com/zifangsky/DataStructure/tree/master/src/main/java/cn/zifangsky/hashtable/lru
    zifangsky
        37
    zifangsky  
       2020-07-13 17:40:14 +08:00
    当然,LFU 算法我也实现了,你看上一层目录就可以看到。
    rikka
        38
    rikka  
    OP
       2020-07-13 18:59:41 +08:00
    @zifangsky #37 看了,基本都差不多~~
    xieranmaya
        39
    xieranmaya  
       2020-07-15 16:55:56 +08:00
    LRU+定时器
    这做个面试题是真不错
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1042 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 53ms · UTC 22:36 · PVG 06:36 · LAX 15:36 · JFK 18:36
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.