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

大佬们,问个 Java 面试题

  •  
  •   perryzou · 15 天前 · 4022 次点击

    有一个百万级数据文件,格式如下:

    手机号,name


    用 JAVA 实现功能,通过手机号查找 name,要求:

    1.并发要求至少每秒数千次,不能使用 redis,mysql,es 等

    2.内存要求,不能超过 3M

    42 条回复    2020-06-30 11:31:58 +08:00
    weijiawj
        1
    weijiawj   15 天前
    字典树行不
    sagaxu
        2
    sagaxu   15 天前 via Android
    3M 连 JVM 都启动不了
    wysnylc
        3
    wysnylc   15 天前
    ConcurrentSkipListMap,能存进去就可以
    不过你这 3M 启动应该会挂,什么脑残面试题
    perryzou
        4
    perryzou   15 天前
    @wysnylc 哈哈哈 我也觉得 这个内存要求我就很纳闷
    misaka19000
        5
    misaka19000   15 天前
    B 树
    misaka19000
        6
    misaka19000   15 天前
    数据完整的保存在磁盘上使用 B 树,内存中使用红黑树
    perryzou
        7
    perryzou   14 天前
    @misaka19000 文件已经固定了,内容格式已经定了,只让实现 java 类,
    aguesuka
        8
    aguesuka   14 天前
    1m 约等于 10^30 => log(2, 1m) 约等于 30 。文件在磁盘里排序对齐,一直打开文件不要关闭,相当于每秒位移 数千*30 次。如果没有写入文件,用 tree 不能减少搜索的复杂度,反而会增加常量时间
    smilenceX
        9
    smilenceX   14 天前
    假设手机号 11 位,不含国家代码,在内存中以 int32 ( 4 字节)存储,中文 name 按三个汉字 ,为了简单每个汉字按照占 3 字节(一共 9 字节)来算,
    ( 4+9 )*100w/1024/1024=12.39m
    因此不可能把数据全部读到内存里再查找(超过了题目 3M 的要求)。
    fancy20
        10
    fancy20   14 天前
    3MB 内存,文件全读到内存不够吧,所以看怎么个并发了,允许 async callback 查询结果的话,那就在内存里存要查询的手机号,另一个线程不停反复从头到尾扫文件,如果扫到就返回
    perryzou
        11
    perryzou   14 天前
    @smilenceX 是的,就是这个意思
    chendy
        12
    chendy   14 天前
    本来想说整个 map<手机号,文件偏移量>,然后发现光是 100 万个手机号就超过 3m 了
    文件按手机号排个序,每行长度固定,然后二分查找?建议配合 ssd 食用…
    icexin
        13
    icexin   14 天前
    按照 "手机号->记录偏移量" 作为 kv 结构排序成一个一个单独的索引文件,每个索引文件不要太大,可以在内存里面记录下每个索引文件的 range,也可以持久化成一个 manifest 文件,方便启动的时候读取。查询的时候先根据 manifest 获取索引文件,加载到内存,根据手机号找到记录偏移,再根据偏移找到 name,最后加一个手机号->name 的 lru cache 来做 cache 。
    guolaopi
        14
    guolaopi   14 天前
    我不是很理解“并发要求至少每秒数千次”是什么意思。。。
    是要求响应时间在 XX 以内吗
    CrazyEight
        15
    CrazyEight   14 天前
    建个索引(手机号,name ),不过内存小于 3M 有点难以把握。不知道你说的内存是只指程序处理请求时占用的内存吗,如果索引占用的内存也算进去,那很难也没必要
    ljzxloaf
        16
    ljzxloaf   14 天前
    这个文件就是一张表 t,有俩字段 tel 和 name,要求就是尽量提高 select name from t where tel = ?的性能,这就是要问关系型数据库的相关实现吧。
    但是数据库一般这种情况要建个索引吧,否则性能应该达不到要求,注意这里不需要建 B 树索引,因为并不需要范围查询,可以分成 100 个小索引文件,每个小索引是一棵树,每次查找先取模找到索引文件,将之整个加载到内存,再查找 name 。
    可以去搜搜关系数据库的哈希索引实现,这里肯定会有很多细节。
    为了防止大量不存在的手机号导致性能问题,还可以搞个布隆过滤器什么的。
    huntcool001
        17
    huntcool001   14 天前
    "并发要求至少每秒数千次"

    我开 10 个线程一直查一个 key,那也是并发几十万次...
    zhgg0
        18
    zhgg0   14 天前
    前缀树 存手机号
    binbinyouliiii
        19
    binbinyouliiii   14 天前
    name 做索引,索引也不是说非得在内存里,索引排序到文件里,比如 hash 做索引,索引的头 5 位放到内存里,记下每个索引文件的指针位置,不过机械硬盘性能够呛。
    而且又没说查询最小间隔,只要求了吞吐量,剩下的就把一部分数据放到内存里,LRU 算法拿。
    perryzou
        20
    perryzou   14 天前
    @binbinyouliiii 实验索引的内存就超过了 3M,不然并发达不到要求
    gejun123456
        21
    gejun123456   14 天前
    用 sqlite
    ujued
        22
    ujued   14 天前 via iPhone
    @perryzou RandomAccess 访问文件数据很快的老弟!你只需要知道你要访问的数据大致在哪个地方就行。这点数据量,这点并发,一般硬件足矣。
    johnniang
        23
    johnniang   14 天前 via Android
    先外部排序,然后二分法查找。毕竟手机号是有序的。
    liprais
        24
    liprais   14 天前 via iPhone
    手机号前七位都是有很多重复的,压缩压缩没准 3m 内存能都放下
    helloworld000
        25
    helloworld000   14 天前
    tire tree 啊,省不少内存。

    每个数字作为节点 node,最后树的叶子节点记录个名字就行了
    exch4nge
        26
    exch4nge   14 天前 via iPhone
    提个不新建文件,用原文件格式的方法,核心就是哈希表
    把 3M 分成每个桶大小为 3 字节的,1024*1024 个桶;每个桶里用 3 字节保存此电话号码开头在文件中的偏移位置,不过直接存偏移三个字节肯定不够,可以除一个系数存,三个字节够表示 100w+的位置
    哈希碰撞问题,首先是选用好的哈希函数,不过 95.37%的密度碰撞出现可能性还是蛮高,具体策略可以再评估各种后再决定,可参考 folly F14 的解决方式,约 12/13=92%来着?
    xupefei
        27
    xupefei   14 天前 via iPhone
    简单,用若干前缀树,每棵树尺寸限制到 3MB 。如果一个节点的后代是另一棵树,那么在此节点记录下一个编号 a 。包含跟节点的树定为编号 0 。

    查询的时候,首先把 0 号树读进来,然后跟着去找下一个编号的树。直到最后找到对应人名。

    存储方面:编号为 n 的树存储在 3MB*n 偏移处。

    如果有 ssd 的话,上面这方案每秒千次查询根本不是问题。

    另外还有一些可以聊的方向:树是横着切还是竖着切?在文件里怎么序列化? LRU 缓存?这方案和数据库的 page 有什么区别?
    yousabuk
        28
    yousabuk   14 天前 via iPhone
    将文件转换为二进制文件存储,在创建索引文件(肯定小于 3M ),将索引文件全部加载到内存,根据 TDMS 格式规范使用 JAVA 进行解析。

    现成的二进制文件结构:TDMS

    TDMS 是 NI 专门用于快速存储和读取大数据量波形文件的方案,速度绝对足够快,索引文件也绝对够小。
    yousabuk
        29
    yousabuk   14 天前 via iPhone
    对了,TDMS 会自动创建索引文件。
    ebony0319
        30
    ebony0319   14 天前 via Android   ❤️ 1
    如果真的是面试题,那解法大概是这样的:一行行读取文件,对每一行文件 hash(value)%1000,这样就把对应的文件分散到对应的小文件中。每次查询的时候先对手机号码 hash(手机号)%1000 求出区间,然后将小文件加载到内存查询。
    776491381
        31
    776491381   14 天前 via iPhone
    可以使用稀疏索引+顺序读,手机号作为索引文件,对应文件的相应位置指针
    mizzle
        32
    mizzle   14 天前
    文件按手机号排序,取手机号前 7 位(万号段)第一次出现的偏移量,放入数组。
    行数小于 1000w ( 2^20),一行字节数小于 4k(2^12),4 字节可以存一个偏移量;手机号前两位固定为 13/17/18,所以前 7 位 30 万排列组合,使用 1.2M 内存。
    查询时先取该万号段和下一万号段偏移量,然后在文件中二分查找。

    还可以优化:
    1 、将 name 用空格补齐到固定长度,可以直接用行数乘以每行长度得到偏移量,这样 3 字节就可以存一个行数,更省内存。(虽然不知道抠这点内存有啥意思)
    2 、既然对响应时间没有要求,剩下内存可以对请求做一个队列,按请求的手机号做排序然后批处理查询,保证每次批处理时文件扫描从头到尾或从尾到头,增加随机访问效率。
    walnsrully
        33
    walnsrully   14 天前 via Android
    @ljzxloaf 不是说禁止使用数据库吗
    BlackwithBrown
        34
    BlackwithBrown   14 天前
    用树的内存应该不够,如果叶存偏移量还不如直接就把原文件先进行分段存好了,代码判断一下还方便
    alittlehj
        35
    alittlehj   14 天前
    我等菜鸟会直接说不会 你解答给我看看 涨涨见识
    ljzxloaf
        36
    ljzxloaf   14 天前 via Android
    @walnsrully
    不是使用数据库,是实现数据库
    ztechstack
        37
    ztechstack   14 天前
    让我想起了,ipip 的 ip 数据库。
    hugedata
        38
    hugedata   14 天前
    @ztechstack 老哥跟我想一块儿去了。。。。
    lianglianglee
        39
    lianglianglee   14 天前 via Android
    文件按照手机号的 hash 分割成 200 个文件,如果是 ssd 就文件就再多点(1000),用 RandomAccess 访问小文件遍历,速度还是非常快的
    lhy0dyx
        40
    lhy0dyx   13 天前
    一棵 11 层的十叉树行吗
    Jooooooooo
        41
    Jooooooooo   13 天前
    题目本身不错, 不过有些东西没有描述清楚
    palmers
        42
    palmers   13 天前
    根据题目我更偏向于 通过类似 hash 的机制将大文件拆分为若干小文件, 小文件的大小限制需要根据 3M 来做处理 针对于第一条 这个并发不是问题
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   3467 人在线   最高记录 5168   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 10:39 · PVG 18:39 · LAX 03:39 · JFK 06:39
    ♥ Do have faith in what you're doing.