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

如何在 1s 内统计出 13 亿人口数据找出使用人数最多的十个姓名

  •  
  •   cage111 · 2021-01-25 10:32:21 +08:00 · 12769 次点击
    这是一个创建于 681 天前的主题,其中的信息可能已经有所发展或是发生改变。

    请教下各位大佬这种需求可以实现吗

    104 条回复    2021-01-26 23:43:31 +08:00
    1  2  
    czfy
        1
    czfy  
       2021-01-25 10:34:55 +08:00
    不限成本(人力、资金、时间),理论上没什么不可实现的
    但现实里不可能不限成本
    kaiki
        2
    kaiki  
       2021-01-25 10:37:52 +08:00
    预备统计数据直接查询那根本要不了 1s,没数据那估计不行。
    iceecream
        3
    iceecream  
       2021-01-25 10:38:51 +08:00   ❤️ 1
    这种几乎静态的数据,为什么有 1s 这种近乎实时的需求?
    我只想到 elasticsearch 这个方法。
    dqzcwxb
        4
    dqzcwxb  
       2021-01-25 10:40:20 +08:00   ❤️ 2
    统计分三种:入库统计,实时统计,定时统计
    kevinyyyy
        6
    kevinyyyy  
       2021-01-25 10:47:21 +08:00
    用 druid 试试?入库时以姓名为维度,TopN 问题,不过这个意义何在呢。。。离线跑 MR 是不是更节省资源一些
    rodrick
        7
    rodrick  
       2021-01-25 10:50:04 +08:00
    张伟”“王伟”“李娜”“王芳”
    JJstyle
        8
    JJstyle  
       2021-01-25 10:52:07 +08:00 via iPhone
    redis 我看他的 qps 也很难达到这么高,常规方案恐怕不行
    shoaly
        9
    shoaly  
       2021-01-25 10:52:21 +08:00
    假设 百家姓里面就 100 个姓,
    1 每个姓准备一个数据库, 把 13 亿个名字都存进去
    2 数据库的 server 提供一个接口 ( http 的都行), 随时输出 当前记录的行数
    3 写一个 100 线程或者 进程或者 协程的程序, 同时抓 100 个库里面的数字
    4 轻轻松松一个排序...
    以上应该 1 之内 就完成了, 且没有什么性能瓶颈, 还是 实时数据
    cage111
        10
    cage111  
    OP
       2021-01-25 10:53:31 +08:00
    补充下硬件和需求:
    可以给两台 128G 内存,1TSSD 服务器
    需求类似这种,
    1.查找 20-30 岁使用人数最多的十个姓名
    2.查找南方地区和北方地区使用人数最多的十个姓名
    3.查找不同性别使用人数最多的十个姓名
    还用很多类似条件随意检索
    czfy
        11
    czfy  
       2021-01-25 10:57:21 +08:00   ❤️ 1
    @cage111
    1. 你的补充放到主贴的附言,才能让跟多人看到
    2. 我先假设你真的有所有人口的姓名数据+人口统计学信息,这种情况下,最容易想到的就是用 ES
    leeg810312
        12
    leeg810312  
       2021-01-25 11:01:17 +08:00 via Android
    这种静态分析需求为什么要实时查询
    kevinyyyy
        13
    kevinyyyy  
       2021-01-25 11:02:52 +08:00
    @czfy
    ES 如果要排序的话,需要所有分辨排序聚合,这个量级 1 秒搞不定吧
    mapoor
        14
    mapoor  
       2021-01-25 11:03:58 +08:00
    @shoaly 大概有 2 万多个姓,而且是分布极度不均匀的,每个姓准备一个数据库不可行。
    czfy
        15
    czfy  
       2021-01-25 11:04:37 +08:00
    @kevinyyyy 其实 1 秒是搞不定的,只是它提的这种查询类型,我最先想到 ES,不一定是最优解
    mapoor
        16
    mapoor  
       2021-01-25 11:09:24 +08:00
    MySQL 单库 130 张表,并行统计 TOP10,最后归并排序取 TOP10.
    dongtingyue
        17
    dongtingyue  
       2021-01-25 11:11:30 +08:00
    预估不行,mysql 亿级的 count group by 1s 不可能。es 的分组统计 1s 也不行,放宽点 10s 可以。
    cage111
        18
    cage111  
    OP
       2021-01-25 11:11:57 +08:00
    @mapoor 还得分页
    xiaoyang7545
        19
    xiaoyang7545  
       2021-01-25 11:17:32 +08:00
    可以预处理数据?
    cage111
        20
    cage111  
    OP
       2021-01-25 11:23:00 +08:00
    @xiaoyang7545 可以
    cage111
        21
    cage111  
    OP
       2021-01-25 11:26:45 +08:00
    @iceecream 刚搜了下,es 的 group by 在多 shard 下好像是不精确的
    EthanDon
        22
    EthanDon  
       2021-01-25 11:30:22 +08:00
    直觉上 clickhouse
    jzmws
        23
    jzmws  
       2021-01-25 11:31:20 +08:00
    预处理 然后丢到内存上?
    Mohanson
        24
    Mohanson  
       2021-01-25 11:32:10 +08:00   ❤️ 3
    字典树啊字典树!

    1 秒是什么概念? 一微秒就够了.
    Mithril
        25
    Mithril  
       2021-01-25 11:34:31 +08:00
    直接弄个计数器,录入数据的时候直接算好了不就完了。。。
    这玩意真的有实时计算的必要吗?
    shyling
        26
    shyling  
       2021-01-25 11:37:05 +08:00
    提前算好 topN 不就好啦
    cage111
        27
    cage111  
    OP
       2021-01-25 11:41:08 +08:00
    @EthanDon clickhouse 试了 1 亿时间 group 要 5,6 秒了
    ppbaozi
        28
    ppbaozi  
       2021-01-25 11:41:13 +08:00
    数据哪来的
    tanszhe
        29
    tanszhe  
       2021-01-25 11:41:19 +08:00
    clickhouse 1 核 2G, 估计都可以 1s 内出结果
    tanszhe
        30
    tanszhe  
       2021-01-25 11:42:06 +08:00
    @cage111 你的表结构和 sql 语句看看
    rihkddd
        31
    rihkddd  
       2021-01-25 11:44:04 +08:00
    @Mohanson 终于有人说字典树了,传统数据结构还是还高效的。可以做一些简单优化,比如定一个远低于 top10 的词频的阈值,去掉长尾数据,放到内存根本都不要 1 个 G 。
    各种查询调节,分别建立对应的字典树。可以满足实时性和准确性。
    rihkddd
        32
    rihkddd  
       2021-01-25 11:45:16 +08:00
    @rihkddd 感觉加上阈值优化,都不需要字典树,直接 hashmap 都没问题。
    PiersSoCool
        33
    PiersSoCool  
       2021-01-25 11:49:35 +08:00
    1s 基本忽略集群了 什么集群处理能有这么快 操作都要 prepare task 那先排除大数据方案
    你要说这个数据在内存里 那就先建立最大堆 O1
    你要说不在内存里 13e 的姓名 恐怕 1s 都加不到内存里
    这个问题有点扯淡。。。
    polymerdg
        34
    polymerdg  
       2021-01-25 11:50:45 +08:00
    公安部大佬?
    cage111
        35
    cage111  
    OP
       2021-01-25 11:51:38 +08:00
    @tanszhe
    CREATE TABLE china.base_person_info
    (
    `id` String,
    `birthday` Nullable(String),
    `location` Nullable(String),
    `name` Nullable(String),
    `type` Nullable(String),
    `category` Nullable(String),
    )
    ENGINE = MergeTree
    ORDER BY id
    SETTINGS index_granularity = 8192

    查询语句
    select name,count(*) from group by name limit 10,1
    又加了点数据报错了...
    Code: 241, e.displayText() = DB::Exception: Memory limit (for query) exceeded: would use 9.32 GiB (attempt to allocate chunk of 4718592 bytes), maximum: 9.31 GiB: While executing AggregatingTransform (version 20.5.2.7 (official build))
    cage111
        36
    cage111  
    OP
       2021-01-25 11:54:23 +08:00
    @polymerdg 不是,可以把姓名理解成商品,随便举例的,类似给运营人员用的爆款商品分析
    yolee599
        37
    yolee599  
       2021-01-25 11:55:27 +08:00
    建树状服务器群集,把任务分下去,像比赛晋级一样一层一层往上传递结果,最高层就是最终结果。
    cage111
        38
    cage111  
    OP
       2021-01-25 11:55:29 +08:00
    @ppbaozi 姓名只是举例,怕暴露产品信息
    wyfyw
        39
    wyfyw  
       2021-01-25 12:01:21 +08:00
    如果你只关心"xxx 使用人数最多的十个姓名"字典树绝对可以帮你解决。

    简化为 100 个姓,最长三 /四个字的名字,使用常用汉字 3500 。如果最长三字的名字,空间才 100*3500*3500

    忽略其它姓氏、生僻汉字、更长的名字(?这点存疑,少数民族地区未必适用),因为满足任何一条的名字不可能人数最多。
    silentsee
        40
    silentsee  
       2021-01-25 12:04:08 +08:00
    @cage111 order by name 才有索引
    cstj0505
        41
    cstj0505  
       2021-01-25 12:07:44 +08:00 via Android
    靠数据库的 group by 不可取,这不是什么数据库的问题,group by 是数据库最慢的执行操作之一,而且还需要消耗大量内存和 CPU 。
    建议 lz 要么采用上面说的字典树,要么了解下现在行为分析的玩法,用数组或者在数据库里用 map 结构预聚合。别说 1s 了,我们百亿级别的数据 60ms 就能出。3 台节点的 gp 。
    magiclx
        42
    magiclx  
       2021-01-25 12:08:26 +08:00
    因为问题并不是从 13 亿短字符串中统计出现频率最高的 10 个,而是 13 亿人口姓名数据。

    人口姓名是相对稳定的,你只要计算一次存量数据,然后计算增量即可随时把结果拿出来。具体来说:

    1 、通过 Google 获知我国每日平均出生人数 2 万多,每日死亡人数为 1 万多,具体数值不重要,知道规模为 5 万以下即可。
    2 、建一张统计表 S 存目前排名前 5 万的姓名和人数,当人员出生,人数增加,把该姓名人数加 1 后 REPLACE INTO 到表 S 中,当人员死亡,人数减少,如果死亡人员姓名在表 S 中,则人数减一。
    3 、定时删除表 S 中大于 5 万的数据。
    4 、当需要统计出 13 亿人口中使用人数最多的十个姓名时,只要 SELECT TOP 10 即可,因为只有 5 万数据,所以无论如何都会在 1S 内。
    chocovon
        43
    chocovon  
       2021-01-25 12:08:53 +08:00
    可以先做一轮数据清洗,把那些不论选什么条件都不是 top10 的姓名给剔除掉,这样大概可以去掉一大堆?
    wms
        44
    wms  
       2021-01-25 12:20:48 +08:00
    预处理阶段, 用元数据(姓名, 年龄,性别等)生成 SHA, SHA 值做 KEY 建立数据库, 然后根据查询条件建立查找树或者堆, 查询的时候直接取相应树,堆的 TOP 通过 SHA 值去数据库取数据
    wq2016
        45
    wq2016  
       2021-01-25 12:21:34 +08:00 via Android   ❤️ 2
    百度一下
    nl101531
        46
    nl101531  
       2021-01-25 12:24:29 +08:00 via iPhone
    es rollup 到一个新索引,查询走新的索引
    337136897
        47
    337136897  
       2021-01-25 12:26:04 +08:00
    楼主这个数据库在哪...
    SuperMild
        48
    SuperMild  
       2021-01-25 12:59:16 +08:00
    由于数据量很小,完全可以预存一堆静态数据,比如,只要预存了 20 岁、21 岁、22 岁... 每个年龄使用人数最多的十个姓名,那想查 20-30 岁使用人数最多的十个姓名就很快了。地区也同理。
    x2ve
        49
    x2ve  
       2021-01-25 13:22:14 +08:00 via iPhone
    不要太执着于数据和技术角度,会很累的。 从业务角度来看 就是一个统计事件,而且这么大的数据,知道个趋势就行了;每天晚上把各个维度都清洗放多个表里就好,又能完成任务又方便
    flippydoo
        50
    flippydoo  
       2021-01-25 13:25:48 +08:00
    字典树
    weizhen199
        51
    weizhen199  
       2021-01-25 13:26:11 +08:00
    塞进 clickhouse 这种还真是分分钟出来
    crs0910
        52
    crs0910  
       2021-01-25 13:32:55 +08:00
    @weizhen199 #51 分分钟莫名戳中笑点
    arvinwangzj
        53
    arvinwangzj  
       2021-01-25 13:40:07 +08:00
    @tiancaixiaoshuai 哈哈哈,机智
    lambdaq
        54
    lambdaq  
       2021-01-25 13:40:20 +08:00
    @cage111 试试把 String 字段换成 FixedString(N) ,只保存一个单字姓呢?

    CH 的 SIMD 需要内存对齐才能提速。
    jackhe
        55
    jackhe  
       2021-01-25 13:49:01 +08:00
    先数据取样?
    PopRain
        56
    PopRain  
       2021-01-25 13:49:19 +08:00
    13 亿用户,简单说就是 1.3G , 如果数据在外设上,你轮询一遍(把名字加载到内存),1s 时间也不够吧....
    lerry
        57
    lerry  
       2021-01-25 13:49:49 +08:00   ❤️ 1
    MapReduce
    EnreIde
        58
    EnreIde  
       2021-01-25 13:54:15 +08:00
    trie
    gstqc
        59
    gstqc  
       2021-01-25 13:54:38 +08:00 via Android   ❤️ 1
    13 亿人名
    1300000000
    4 GHz 为 4 * 1000^3
    4*1000^3/1300000000 = 3
    平均每个名字的处理时间是三个时钟周期
    Rainyf
        60
    Rainyf  
       2021-01-25 14:10:44 +08:00
    @tiancaixiaoshuai 哈哈哈绝了
    sockpuppet9527
        61
    sockpuppet9527  
       2021-01-25 14:16:49 +08:00   ❤️ 1
    假设,目前你的 13 亿个名字都在内存里面。每个名字都是两个字的,13 亿*2byte ≈ 2.42G(连续内存,且无对齐)

    你机器用的是 intel 的 cpu,还存在 AVX512,现在一条 vmovups 指令,他的 latency 是 7,它的 throughput 是 0.5,那么对于 ZMM0-32 来说,你要调用 32 次,throughput 就是 16,latency 是 112 。

    而这条 vmovups 指令,这能读多大的数据呢? 2kb 。(这前提还是你没有任何辅助寄存器的情况下)也就是说将 13 亿名字全部 load 到 ZMM 寄存器组的次数是:2.42G / 2kb = 1269531.25 次。

    总 latency 是 1269531.25*112 = 142187500, 总 throughput 为 1269531.25*16=20312500

    (以上结果是抛开内存频率,内存寻址时间计算,如果加上其他因素,可能需要乘个 100 或者更大。)

    是不是觉得 latency 和 throughput 都还行?

    那其实你把数据打散在一万个内存里面,每个内存中单独配 N 个 CPU,也许不用 1s 就能算出来。这完全取决于你汇编写的怎么样,以及你的硬件条件。
    namelosw
        62
    namelosw  
       2021-01-25 14:22:38 +08:00
    搞个提前算好的读模型, 写入新名字的时候累加一下就好了
    shenlanAZ
        63
    shenlanAZ  
       2021-01-25 14:29:10 +08:00
    提前 map reduce 好,存到数据库里。然后用 500ms 的速度从数据库里查出来。
    zlowly
        64
    zlowly  
       2021-01-25 14:39:53 +08:00
    不用说现在的 ES 这种方式可以做到(结果不精确),就算是以前的集中式关系数据库来说,这种需求也真没什么(结果精确)。例如用 Oracle,直接对姓名统计使用物化视图即可,其核心原理就是在原始数据变更时通过触发器更新统计数据而已。
    neetrorschach
        65
    neetrorschach  
       2021-01-25 14:41:40 +08:00
    如果数据不是实时更新的话用 kylin,会将选定维度的所有组合创建成索引保存在内存里。查询时只要限定字段在索引维度里,基本上是亚秒查询。
    AkideLiu
        66
    AkideLiu  
       2021-01-25 14:41:52 +08:00 via iPhone
    可能性是有的,你看 Google 存的数据比你大,响应也在毫毛级别。重点是有没有这个技术实力
    Takamine
        67
    Takamine  
       2021-01-25 14:42:20 +08:00 via Android
    昨天晚上算完,今天调接口都返回这个值。
    tanszhe
        68
    tanszhe  
       2021-01-25 15:09:46 +08:00
    @cage111 看楼主这个需求 1 个字段就够了,order by name; 肯定非常快
    anonyp
        69
    anonyp  
       2021-01-25 15:16:32 +08:00 via iPhone
    clickhouse name 索引就行了吧,更快的话可以试试物化视图,这个场景应该很适合
    DollarKiller
        70
    DollarKiller  
       2021-01-25 15:32:43 +08:00
    多台机器一起 MapReduce
    est
        71
    est  
       2021-01-25 15:33:02 +08:00
    @gstqc 并行优化下。
    cage111
        72
    cage111  
    OP
       2021-01-25 15:43:37 +08:00
    @tanszhe 不加 where 内存不够用了,测试机器只配了 16g 内存,加了类似性别的字段过滤后用时 4s 。
    结果如下
    china> select name ,count(*) from person where category = 'XXX' group by name order by count(1) desc limit 0,10
    [2021-01-25 15:34:03] 10 rows retrieved starting from 1 in 3 s 995 ms (execution: 3 s 973 ms, fetching: 22 ms)
    cage111
        73
    cage111  
    OP
       2021-01-25 15:45:18 +08:00
    @anonyp 有查询条件也能做视图吗
    tanszhe
        74
    tanszhe  
       2021-01-25 15:45:34 +08:00
    @cage111 我造点数据试试
    anonyp
        75
    anonyp  
       2021-01-25 16:04:30 +08:00 via iPhone
    @cage111 summingmergetree 这个引擎试试
    northisland
        76
    northisland  
       2021-01-25 16:23:31 +08:00
    1.3G 次( 字符串摘要 + 哈希表 )

    按 0.9s 速度进行并发执行。0.1s 留个多个哈系表合并 + top10 排序。
    tanszhe
        77
    tanszhe  
       2021-01-25 16:25:11 +08:00
    @cage111 我 1 核 2G 内测 虚拟机 可以正常运行 13.5 亿数据,不过时间有点长 23s
    tanszhe
        78
    tanszhe  
       2021-01-25 16:26:20 +08:00
    hehe12980
        79
    hehe12980  
       2021-01-25 16:27:23 +08:00
    @shoaly 开 100 个线程 .... 一共也没几个核 开那么多有啥用
    DrJoseph
        80
    DrJoseph  
       2021-01-25 16:51:00 +08:00
    坐等蚂蚁的同学提供 OceanBase 的可行方案,毕竟隔壁已经用 ClickHouse 解决了
    传送门: https://www.v2ex.com/t/748196#reply8
    yuankui
        81
    yuankui  
       2021-01-25 17:02:02 +08:00
    1. 面向列的
    2. 姓氏映射成一个 bit
    3. bitmap

    ClickHouse 应该很简单
    yuankui
        82
    yuankui  
       2021-01-25 17:03:23 +08:00
    这是哪个公司的面试题吗?
    lovecy
        83
    lovecy  
       2021-01-25 17:05:14 +08:00
    这个是静态数据,维护一份统计数据,每次更新静态数据时同时更新统计数据。
    1s 内找出十个最多的人名,就是一条查询而已
    skies457
        84
    skies457  
       2021-01-25 17:08:53 +08:00
    查询模式固定的话可以考虑自己用 C++写索引和查询,13 亿短字符串对于单机而言也不是很大的量级
    786375312123
        85
    786375312123  
       2021-01-25 17:24:00 +08:00
    @Mohanson 使用最多,看清楚了兄弟。你还是要把整个树过一遍才能知道那些频率最高
    yuyueMJ
        86
    yuyueMJ  
       2021-01-25 17:32:46 +08:00
    @tiancaixiaoshuai 哈哈哈 牛逼
    fs418082760
        87
    fs418082760  
       2021-01-25 19:03:24 +08:00
    百家姓拿来干吗的,老祖宗都统计好了。。。
    Mohanson
        88
    Mohanson  
       2021-01-25 19:46:50 +08:00 via Android
    @786375312123 设计成父节点的 count 是其所有子节点的 count 和,即使不做任何优化,最多循环一个 3500*3 长度的数组就能找到最大值;找到最大值后排除该根节点继续找最大值,往复 10 次就是 3500*3*10 次循环。

    这是我想到的没任何优化的算法,仔细设计的话提个数量级也不是不可能
    ltoddy
        89
    ltoddy  
       2021-01-25 19:54:33 +08:00
    使用字典树,循环一次就出来了。
    Mohanson
        90
    Mohanson  
       2021-01-25 19:54:52 +08:00 via Android
    如果在插入和移出数据时保证所有子树的顺序的话,那么查找一次最大值的时间复杂度就是 O(1),代价是插入和删除的时候计算量会变大很多,不过不是大问题,毕竟是读优先的
    xcstream
        91
    xcstream  
       2021-01-25 20:00:06 +08:00
    插入的时候就排好了, 只需 0.0001 秒
    786375312123
        92
    786375312123  
       2021-01-25 21:39:26 +08:00
    @Mohanson 可是你依然需要遍历所有的名字以后才能知道某个子节点上对应的数字是多少。建立树的成本依然是 o(n)
    moult
        93
    moult  
       2021-01-25 22:12:12 +08:00
    结合实际情况,如果可行的话,预处理的时候,把那些独一无二的名字先全部踢掉,数据少一大半。
    lululau
        94
    lululau  
       2021-01-25 22:18:41 +08:00
    select * from top_names;
    iluckypig
        95
    iluckypig  
       2021-01-25 23:58:10 +08:00
    @cage111 建表的索引错了吧,应该是 order by name
    tedzhou1221
        96
    tedzhou1221  
       2021-01-26 00:03:01 +08:00 via iPhone
    感觉你是想做用户画像,精准推送
    alazysun
        97
    alazysun  
       2021-01-26 00:44:46 +08:00
    数据录入的时候不就统计好了吗?
    v2sir
        98
    v2sir  
       2021-01-26 01:09:32 +08:00
    @mapoor 你这个算法是错的
    ericls
        99
    ericls  
       2021-01-26 01:22:04 +08:00 via iPhone
    用 columnar 数据库
    lxfxf
        100
    lxfxf  
       2021-01-26 06:23:05 +08:00   ❤️ 1
    统计学方法,直接随机落点一百万次,再统计不就好
    这题应该改一下,找出最少的十个姓
    1  2  
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   1229 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 71ms · UTC 20:19 · PVG 04:19 · LAX 12:19 · JFK 15:19
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.