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

阿里面试, redis 里存有 10 亿键值对,找出一个指定前缀的所有键,说出实现原理。

  •  
  •   linxiaoziruo · 2020-07-25 19:37:50 +08:00 · 4641 次点击
    这是一个创建于 1563 天前的主题,其中的信息可能已经有所发展或是发生改变。
    18 条回复    2020-07-27 11:33:31 +08:00
    ruanimal
        1
    ruanimal  
       2020-07-25 21:24:27 +08:00
    前缀树?不然只能遍历吧
    wangyzj
        2
    wangyzj  
       2020-07-26 00:44:35 +08:00
    他是让你造 java 代码的火箭
    还是让你造 redis 内部数据结构的火箭啊?
    izzy27
        3
    izzy27  
       2020-07-26 09:19:08 +08:00
    倒排?
    SingeeKing
        4
    SingeeKing  
       2020-07-26 10:39:19 +08:00
    官方做法就是遍历所有键
    https://redis.io/commands/keys
    https://github.com/redis/redis/blob/unstable/src/db.c#L630

    自己实现的话,之前我遇到这个需求时做法是用另一个键存。比如存了 a::b::c 和 a::b::d,就在 a::b 中存储 c 和 d
    linxiaoziruo
        5
    linxiaoziruo  
    OP
       2020-07-26 11:49:52 +08:00 via Android
    @SingeeKing 有个 scan 命令
    jeffh
        6
    jeffh  
       2020-07-26 14:01:05 +08:00
    scan 遍历吧,具体 scan 内部是不是遍历就不清楚了
    useben
        7
    useben  
       2020-07-26 17:12:01 +08:00
    前面的在答什么。。。
    gabon
        8
    gabon  
       2020-07-26 21:09:15 +08:00 via Android
    scan,之前有个 Redis key 迁移的场景就是用的 scan,axxx-》 bxxx
    hangszhang
        9
    hangszhang  
       2020-07-26 21:40:40 +08:00
    这还能怎么办?sacn 啊
    linxiaoziruo
        10
    linxiaoziruo  
    OP
       2020-07-27 09:11:35 +08:00 via Android
    scan 都知道,关键是 scan 怎么实现大数据查找的,面试官想问 scan 的原理,本质是想知道我有没有看过 scan 的源码。
    BlackwithBrown
        11
    BlackwithBrown  
       2020-07-27 09:47:38 +08:00
    scan 0 MATCH X* COUNT 1000
    遗憾的是 redis 的底层也是先根据游标遍历再根据 match 筛选的
    Aresxue
        12
    Aresxue  
       2020-07-27 10:45:15 +08:00
    自己设计结构的话仿照 mysql 的索引使用 B+树去处理,多层 hash,这样速度会有提升,但索引本身是一份冗余数据,相当于空间换时间了
    palmers
        13
    palmers  
       2020-07-27 10:53:41 +08:00
    我觉得这道题就是简单的考察 redis 命令 scan 以及 scan 大致的原理 就是利用游标什么的 就是具体怎么使用的 这样基本应该可以及格了 深层次应该不会是主要考察点 否则就是不是应用了 但答对了 肯定是加分不少
    linxiaoziruo
        14
    linxiaoziruo  
    OP
       2020-07-27 10:55:24 +08:00
    @palmers 只是考察 scan 的话就没必要特意加上 10 亿数据这个前提,还着重跟我确认 10 亿数据。
    palmers
        15
    palmers  
       2020-07-27 11:08:12 +08:00
    @linxiaoziruo 对啊 数量级大 是应该用 scan 啊 否则 keys 会阻塞 业务会受影响
    acainiao
        16
    acainiao  
       2020-07-27 11:19:05 +08:00 via iPhone
    n 叉树,每个节点最多 26 个字节点,可以确保常数事件
    IMXT
        17
    IMXT  
       2020-07-27 11:31:21 +08:00 via Android
    tire
    portlet
        18
    portlet  
       2020-07-27 11:33:31 +08:00
    字典树
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1211 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 18:04 · PVG 02:04 · LAX 10:04 · JFK 13:04
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.