V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
zijing07
V2EX  ›  问与答

遇到一道面试题,分布式 LRU 的设计。

  •  
  •   zijing07 · 2019-06-07 01:45:26 +08:00 · 1811 次点击
    这是一个创建于 1757 天前的主题,其中的信息可能已经有所发展或是发生改变。
    这道题总共分了以下几层来问的(答案是我想的,不一定对哈,欢迎指正):

    1. 纯内存 LRU,那么就是 leetcode 的原题,双向链表+HashMap
    2. 内存放不下了怎么办,文件操作 + HashMap
    3. 多线程怎么做,HashMap 分 bucket 加锁,文件共用一把锁(答到这里我已经觉得不太好了,因为最后多线程还是会锁在文件这里,造成等待)
    4. 分布式怎么做,Hash 到对应的分片拿数据,但是怎么在多台机器之间实现类似双向链表的逻辑,我就没答上来了。

    希望大家有想法的一起讨论一下。
    3 条回复    2020-05-07 17:06:46 +08:00
    raynor2011
        1
    raynor2011  
       2019-06-07 16:31:49 +08:00 via Android
    分布式 LRU 难道不是一致性哈希加单机 LRU 吗,然后文件是干嘛的,LRU 到内存阈值了就释放啊,要不然为什么叫 LRU
    zijing07
        2
    zijing07  
    OP
       2019-06-08 01:21:28 +08:00
    对对,是一致性哈希。我这块没整明白,上面是我乱讲的。多谢!
    jianzhiyao020
        3
    jianzhiyao020  
       2020-05-07 17:06:46 +08:00
    1.LRU 就普通的 LRU,但是实际使用上来说,需要提供 evict 事件,提供持久化缓存数据的操作机会
    2.内存放不下,提供 onCacheMiss 事件和 OnEvict 事件,喜欢咋搞咋搞
    3.多线程就加锁嘛,这里怕锁的堆积的话,可以把读文件和写文件搞到队列里面进行
    4.分布式一致性 hash,hash 到分片操作
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   4692 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 01:08 · PVG 09:08 · LAX 18:08 · JFK 21:08
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.