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

[cage111]

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

[czfy]

不限成本（人力、资金、时间），理论上没什么不可实现的
但现实里不可能不限成本

[kaiki]

预备统计数据直接查询那根本要不了 1s，没数据那估计不行。

[iceecream]

这种几乎静态的数据，为什么有 1s 这种近乎实时的需求？
我只想到 elasticsearch 这个方法。

[dqzcwxb]

统计分三种:入库统计,实时统计,定时统计

[tiancaixiaoshuai]

https://www.baidu.com/s?ie=UTF-8&wd=%E4%BD%BF%E7%94%A8%E4%BA%BA%E6%95%B0%E6%9C%80%E5%A4%9A%E7%9A%84%E5%8D%81%E4%B8%AA%E5%A7%93%E5%90%8D

[kevinyyyy]

用 druid 试试？入库时以姓名为维度，TopN 问题，不过这个意义何在呢。。。离线跑 MR 是不是更节省资源一些

[rodrick]

张伟”“王伟”“李娜”“王芳”

[JJstyle]

redis 我看他的 qps 也很难达到这么高，常规方案恐怕不行

[shoaly]

假设 百家姓里面就 100 个姓,
1 每个姓准备一个数据库, 把 13 亿个名字都存进去
2 数据库的 server 提供一个接口 ( http 的都行), 随时输出 当前记录的行数
3 写一个 100 线程或者 进程或者 协程的程序, 同时抓 100 个库里面的数字
4 轻轻松松一个排序...
以上应该 1 之内 就完成了, 且没有什么性能瓶颈, 还是 实时数据

[cage111]

补充下硬件和需求：
可以给两台 128G 内存，1TSSD 服务器
需求类似这种，
1.查找 20-30 岁使用人数最多的十个姓名
2.查找南方地区和北方地区使用人数最多的十个姓名
3.查找不同性别使用人数最多的十个姓名
还用很多类似条件随意检索

[czfy]

@cage111
1. 你的补充放到主贴的附言，才能让跟多人看到
2. 我先假设你真的有所有人口的姓名数据+人口统计学信息，这种情况下，最容易想到的就是用 ES

[leeg810312]

这种静态分析需求为什么要实时查询

[kevinyyyy]

@czfy
ES 如果要排序的话，需要所有分辨排序聚合，这个量级 1 秒搞不定吧

[mapoor]

@shoaly 大概有 2 万多个姓，而且是分布极度不均匀的，每个姓准备一个数据库不可行。

[czfy]

@kevinyyyy 其实 1 秒是搞不定的，只是它提的这种查询类型，我最先想到 ES，不一定是最优解

[mapoor]

MySQL 单库 130 张表，并行统计 TOP10，最后归并排序取 TOP10.

[dongtingyue]

预估不行，mysql 亿级的 count group by 1s 不可能。es 的分组统计 1s 也不行，放宽点 10s 可以。

[cage111]

@mapoor 还得分页

[xiaoyang7545]

可以预处理数据？

[cage111]

@xiaoyang7545 可以

[cage111]

@iceecream 刚搜了下，es 的 group by 在多 shard 下好像是不精确的

[EthanDon]

直觉上 clickhouse

[jzmws]

预处理 然后丢到内存上?

[Mohanson]

字典树啊字典树!

1 秒是什么概念? 一微秒就够了.

[Mithril]

直接弄个计数器，录入数据的时候直接算好了不就完了。。。
这玩意真的有实时计算的必要吗？

[shyling]

提前算好 topN 不就好啦

[cage111]

@EthanDon clickhouse 试了 1 亿时间 group 要 5,6 秒了

[xPKK1qofAr6RR09O]

数据哪来的

[tanszhe]

clickhouse 1 核 2G， 估计都可以 1s 内出结果

[tanszhe]

@cage111 你的表结构和 sql 语句看看

[rihkddd]

@Mohanson 终于有人说字典树了，传统数据结构还是还高效的。可以做一些简单优化，比如定一个远低于 top10 的词频的阈值，去掉长尾数据，放到内存根本都不要 1 个 G 。
各种查询调节，分别建立对应的字典树。可以满足实时性和准确性。

[rihkddd]

@rihkddd 感觉加上阈值优化，都不需要字典树，直接 hashmap 都没问题。

[PiersSoCool]

1s 基本忽略集群了 什么集群处理能有这么快 操作都要 prepare task 那先排除大数据方案
你要说这个数据在内存里 那就先建立最大堆 O1
你要说不在内存里 13e 的姓名 恐怕 1s 都加不到内存里
这个问题有点扯淡。。。

[polymerdg]

公安部大佬？

[cage111]

@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]

@polymerdg 不是，可以把姓名理解成商品，随便举例的，类似给运营人员用的爆款商品分析

[yolee599]

建树状服务器群集，把任务分下去，像比赛晋级一样一层一层往上传递结果，最高层就是最终结果。

[cage111]

@ppbaozi 姓名只是举例，怕暴露产品信息

[wyfyw]

如果你只关心"xxx 使用人数最多的十个姓名"字典树绝对可以帮你解决。

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

忽略其它姓氏、生僻汉字、更长的名字（？这点存疑，少数民族地区未必适用），因为满足任何一条的名字不可能人数最多。

[silentsee]

@cage111 order by name 才有索引

[cstj0505]

靠数据库的 group by 不可取，这不是什么数据库的问题，group by 是数据库最慢的执行操作之一，而且还需要消耗大量内存和 CPU 。
建议 lz 要么采用上面说的字典树，要么了解下现在行为分析的玩法，用数组或者在数据库里用 map 结构预聚合。别说 1s 了，我们百亿级别的数据 60ms 就能出。3 台节点的 gp 。

[magiclx]

因为问题并不是从 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]

可以先做一轮数据清洗，把那些不论选什么条件都不是 top10 的姓名给剔除掉，这样大概可以去掉一大堆？

[wms]

预处理阶段, 用元数据(姓名, 年龄,性别等)生成 SHA, SHA 值做 KEY 建立数据库, 然后根据查询条件建立查找树或者堆, 查询的时候直接取相应树,堆的 TOP 通过 SHA 值去数据库取数据

[wq2016]

百度一下

[nl101531]

es rollup 到一个新索引，查询走新的索引

[337136897]

楼主这个数据库在哪...

[SuperMild]

由于数据量很小，完全可以预存一堆静态数据，比如，只要预存了 20 岁、21 岁、22 岁... 每个年龄使用人数最多的十个姓名，那想查 20-30 岁使用人数最多的十个姓名就很快了。地区也同理。

[x2ve]

不要太执着于数据和技术角度，会很累的。 从业务角度来看 就是一个统计事件，而且这么大的数据，知道个趋势就行了；每天晚上把各个维度都清洗放多个表里就好，又能完成任务又方便

[flippydoo]

字典树

[weizhen199]

塞进 clickhouse 这种还真是分分钟出来

[crs0910]

@weizhen199 #51 分分钟莫名戳中笑点

[arvinwangzj]

@tiancaixiaoshuai 哈哈哈，机智

[lambdaq]

@cage111 试试把 String 字段换成 FixedString(N) ，只保存一个单字姓呢？

CH 的 SIMD 需要内存对齐才能提速。

[jackhe]

先数据取样？

[PopRain]

13 亿用户，简单说就是 1.3G ， 如果数据在外设上，你轮询一遍(把名字加载到内存)，1s 时间也不够吧....

[lerry]

MapReduce

[EnreIde]

trie

[0ZXYDDu796nVCFxq]

13 亿人名
1300000000
4 GHz 为 4 * 1000^3
4*1000^3/1300000000 = 3
平均每个名字的处理时间是三个时钟周期

[Rainyf]

@tiancaixiaoshuai 哈哈哈绝了

[sockpuppet9527]

假设，目前你的 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]

搞个提前算好的读模型, 写入新名字的时候累加一下就好了

[shenlanAZ]

提前 map reduce 好，存到数据库里。然后用 500ms 的速度从数据库里查出来。

[zlowly]

不用说现在的 ES 这种方式可以做到（结果不精确），就算是以前的集中式关系数据库来说，这种需求也真没什么（结果精确）。例如用 Oracle，直接对姓名统计使用物化视图即可，其核心原理就是在原始数据变更时通过触发器更新统计数据而已。

[neetrorschach]

如果数据不是实时更新的话用 kylin，会将选定维度的所有组合创建成索引保存在内存里。查询时只要限定字段在索引维度里，基本上是亚秒查询。

[AkideLiu]

可能性是有的，你看 Google 存的数据比你大，响应也在毫毛级别。重点是有没有这个技术实力

[Takamine]

昨天晚上算完，今天调接口都返回这个值。

[tanszhe]

@cage111 看楼主这个需求 1 个字段就够了，order by name; 肯定非常快

[anonyp]

clickhouse name 索引就行了吧，更快的话可以试试物化视图，这个场景应该很适合

[DollarKiller]

多台机器一起 MapReduce

[est]

@gstqc 并行优化下。

[cage111]

@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]

@anonyp 有查询条件也能做视图吗

[tanszhe]

@cage111 我造点数据试试

[anonyp]

@cage111 summingmergetree 这个引擎试试

[northisland]

1.3G 次( 字符串摘要 + 哈希表 )

按 0.9s 速度进行并发执行。0.1s 留个多个哈系表合并 + top10 排序。

[tanszhe]

@cage111 我 1 核 2G 内测 虚拟机 可以正常运行 13.5 亿数据，不过时间有点长 23s

[tanszhe]

https://v2ex.com/t/748196#reply6

[hehe12980]

@shoaly 开 100 个线程 .... 一共也没几个核 开那么多有啥用

[DrJoseph]

坐等蚂蚁的同学提供 OceanBase 的可行方案，毕竟隔壁已经用 ClickHouse 解决了
传送门： https://www.v2ex.com/t/748196#reply8

[yuankui]

1. 面向列的
2. 姓氏映射成一个 bit
3. bitmap

ClickHouse 应该很简单

[yuankui]

这是哪个公司的面试题吗？

[lovecy]

这个是静态数据，维护一份统计数据，每次更新静态数据时同时更新统计数据。
1s 内找出十个最多的人名，就是一条查询而已

[skies457]

查询模式固定的话可以考虑自己用 C++写索引和查询，13 亿短字符串对于单机而言也不是很大的量级

[786375312123]

@Mohanson 使用最多，看清楚了兄弟。你还是要把整个树过一遍才能知道那些频率最高

[yuyueMJ]

@tiancaixiaoshuai 哈哈哈 牛逼

[fs418082760]

百家姓拿来干吗的，老祖宗都统计好了。。。

[Mohanson]

@786375312123 设计成父节点的 count 是其所有子节点的 count 和，即使不做任何优化，最多循环一个 3500*3 长度的数组就能找到最大值；找到最大值后排除该根节点继续找最大值，往复 10 次就是 3500*3*10 次循环。

这是我想到的没任何优化的算法，仔细设计的话提个数量级也不是不可能

[ltoddy]

使用字典树，循环一次就出来了。

[Mohanson]

如果在插入和移出数据时保证所有子树的顺序的话，那么查找一次最大值的时间复杂度就是 O(1)，代价是插入和删除的时候计算量会变大很多，不过不是大问题，毕竟是读优先的

[xcstream]

插入的时候就排好了， 只需 0.0001 秒

[786375312123]

@Mohanson 可是你依然需要遍历所有的名字以后才能知道某个子节点上对应的数字是多少。建立树的成本依然是 o(n)

[moult]

结合实际情况，如果可行的话，预处理的时候，把那些独一无二的名字先全部踢掉，数据少一大半。

[lululau]

select * from top_names;

[iluckypig]

@cage111 建表的索引错了吧，应该是 order by name

[tedzhou1221]

感觉你是想做用户画像，精准推送

[alazysun]

数据录入的时候不就统计好了吗？

[v2sir]

@mapoor 你这个算法是错的

[ericls]

用 columnar 数据库

[lxfxf]

统计学方法，直接随机落点一百万次，再统计不就好
这题应该改一下，找出最少的十个姓