这是一个创建于 1385 天前的主题，其中的信息可能已经有所发展或是发生改变。
请教下各位大佬这种需求可以实现吗
 |
1
czfy 2021-01-25 10:34:55 +08:00
不限成本（人力、资金、时间），理论上没什么不可实现的
但现实里不可能不限成本 |
 |
2
kaiki 2021-01-25 10:37:52 +08:00
预备统计数据直接查询那根本要不了 1s，没数据那估计不行。
|
 |
3
iceecream 2021-01-25 10:38:51 +08:00  1
这种几乎静态的数据，为什么有 1s 这种近乎实时的需求？
我只想到 elasticsearch 这个方法。 |
 |
4
dqzcwxb 2021-01-25 10:40:20 +08:00 2
统计分三种:入库统计,实时统计,定时统计
|
 |
5
tiancaixiaoshuai 2021-01-25 10:46:26 +08:00 21
|
 |
6
kevinyyyy 2021-01-25 10:47:21 +08:00
用 druid 试试？入库时以姓名为维度，TopN 问题，不过这个意义何在呢。。。离线跑 MR 是不是更节省资源一些
|
 |
7
rodrick 2021-01-25 10:50:04 +08:00
张伟”“王伟”“李娜”“王芳”
|
 |
8
JJstyle 2021-01-25 10:52:07 +08:00 via iPhone
redis 我看他的 qps 也很难达到这么高，常规方案恐怕不行
|
 |
9
shoaly 2021-01-25 10:52:21 +08:00
假设 百家姓里面就 100 个姓,
1 每个姓准备一个数据库, 把 13 亿个名字都存进去 2 数据库的 server 提供一个接口 ( http 的都行), 随时输出 当前记录的行数 3 写一个 100 线程或者 进程或者 协程的程序, 同时抓 100 个库里面的数字 4 轻轻松松一个排序... 以上应该 1 之内 就完成了, 且没有什么性能瓶颈, 还是 实时数据 |
 |
10
cage111 OP 补充下硬件和需求：
可以给两台 128G 内存，1TSSD 服务器 需求类似这种， 1.查找 20-30 岁使用人数最多的十个姓名 2.查找南方地区和北方地区使用人数最多的十个姓名 3.查找不同性别使用人数最多的十个姓名 还用很多类似条件随意检索 |
|
11
czfy 2021-01-25 10:57:21 +08:00 1
|
 |
12
leeg810312 2021-01-25 11:01:17 +08:00 via Android
这种静态分析需求为什么要实时查询
|
 |
16
mapoor 2021-01-25 11:09:24 +08:00
MySQL 单库 130 张表，并行统计 TOP10，最后归并排序取 TOP10.
|
 |
17
dongtingyue 2021-01-25 11:11:30 +08:00
预估不行，mysql 亿级的 count group by 1s 不可能。es 的分组统计 1s 也不行，放宽点 10s 可以。
|
 |
19
xiaoyang7545 2021-01-25 11:17:32 +08:00
可以预处理数据？
|
|
20
cage111 OP @xiaoyang7545 可以
|
 |
22
EthanDon 2021-01-25 11:30:22 +08:00
直觉上 clickhouse
|
 |
23
jzmws 2021-01-25 11:31:20 +08:00
预处理 然后丢到内存上?
|
 |
24
Mohanson 2021-01-25 11:32:10 +08:00 3
字典树啊字典树!
1 秒是什么概念? 一微秒就够了. |
 |
25
Mithril 2021-01-25 11:34:31 +08:00
直接弄个计数器，录入数据的时候直接算好了不就完了。。。
这玩意真的有实时计算的必要吗？ |
 |
26
shyling 2021-01-25 11:37:05 +08:00
提前算好 topN 不就好啦
|
 |
28
ppbaozi 2021-01-25 11:41:13 +08:00
数据哪来的
|
 |
29
tanszhe 2021-01-25 11:41:19 +08:00
clickhouse 1 核 2G， 估计都可以 1s 内出结果
|
 |
31
rihkddd 2021-01-25 11:44:04 +08:00
@Mohanson 终于有人说字典树了，传统数据结构还是还高效的。可以做一些简单优化，比如定一个远低于 top10 的词频的阈值，去掉长尾数据，放到内存根本都不要 1 个 G 。
各种查询调节，分别建立对应的字典树。可以满足实时性和准确性。 |
 |
33
PiersSoCool 2021-01-25 11:49:35 +08:00
1s 基本忽略集群了 什么集群处理能有这么快 操作都要 prepare task 那先排除大数据方案
你要说这个数据在内存里 那就先建立最大堆 O1 你要说不在内存里 13e 的姓名 恐怕 1s 都加不到内存里 这个问题有点扯淡。。。 |
 |
34
polymerdg 2021-01-25 11:50:45 +08:00
公安部大佬？
|
|
35
cage111 OP @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)) |
 |
37
yolee599 2021-01-25 11:55:27 +08:00
建树状服务器群集，把任务分下去，像比赛晋级一样一层一层往上传递结果，最高层就是最终结果。
|
 |
39
wyfyw 2021-01-25 12:01:21 +08:00
如果你只关心"xxx 使用人数最多的十个姓名"字典树绝对可以帮你解决。
简化为 100 个姓，最长三 /四个字的名字，使用常用汉字 3500 。如果最长三字的名字，空间才 100*3500*3500 忽略其它姓氏、生僻汉字、更长的名字（？这点存疑，少数民族地区未必适用），因为满足任何一条的名字不可能人数最多。 |
 |
41
cstj0505 2021-01-25 12:07:44 +08:00 via Android
靠数据库的 group by 不可取，这不是什么数据库的问题，group by 是数据库最慢的执行操作之一，而且还需要消耗大量内存和 CPU 。
建议 lz 要么采用上面说的字典树，要么了解下现在行为分析的玩法，用数组或者在数据库里用 map 结构预聚合。别说 1s 了，我们百亿级别的数据 60ms 就能出。3 台节点的 gp 。 |
 |
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 内。 |
 |
43
chocovon 2021-01-25 12:08:53 +08:00
可以先做一轮数据清洗，把那些不论选什么条件都不是 top10 的姓名给剔除掉，这样大概可以去掉一大堆？
|
 |
44
wms 2021-01-25 12:20:48 +08:00
预处理阶段, 用元数据(姓名, 年龄,性别等)生成 SHA, SHA 值做 KEY 建立数据库, 然后根据查询条件建立查找树或者堆, 查询的时候直接取相应树,堆的 TOP 通过 SHA 值去数据库取数据
|
 |
45
wq2016 2021-01-25 12:21:34 +08:00 via Android 2
百度一下
|
 |
46
nl101531 2021-01-25 12:24:29 +08:00 via iPhone
es rollup 到一个新索引，查询走新的索引
|
 |
47
337136897 2021-01-25 12:26:04 +08:00
楼主这个数据库在哪...
|
 |
48
SuperMild 2021-01-25 12:59:16 +08:00
由于数据量很小，完全可以预存一堆静态数据，比如，只要预存了 20 岁、21 岁、22 岁... 每个年龄使用人数最多的十个姓名，那想查 20-30 岁使用人数最多的十个姓名就很快了。地区也同理。
|
 |
49
x2ve 2021-01-25 13:22:14 +08:00 via iPhone
不要太执着于数据和技术角度，会很累的。 从业务角度来看 就是一个统计事件，而且这么大的数据，知道个趋势就行了；每天晚上把各个维度都清洗放多个表里就好，又能完成任务又方便
|
 |
50
flippydoo 2021-01-25 13:25:48 +08:00
字典树
|
 |
51
weizhen199 2021-01-25 13:26:11 +08:00
塞进 clickhouse 这种还真是分分钟出来
|
 |
52
crs0910 2021-01-25 13:32:55 +08:00
@weizhen199 #51 分分钟莫名戳中笑点
|
 |
53
arvinwangzj 2021-01-25 13:40:07 +08:00
@tiancaixiaoshuai 哈哈哈，机智
|
 |
54
lambdaq 2021-01-25 13:40:20 +08:00
|
 |
55
jackhe 2021-01-25 13:49:01 +08:00
先数据取样？
|
 |
56
PopRain 2021-01-25 13:49:19 +08:00
13 亿用户，简单说就是 1.3G ， 如果数据在外设上，你轮询一遍(把名字加载到内存)，1s 时间也不够吧....
|
 |
57
lerry 2021-01-25 13:49:49 +08:00 1
MapReduce
|
 |
58
EnreIde 2021-01-25 13:54:15 +08:00
trie
|
 |
59
0ZXYDDu796nVCFxq 2021-01-25 13:54:38 +08:00 via Android 1
13 亿人名
1300000000 4 GHz 为 4 * 1000^3 4*1000^3/1300000000 = 3 平均每个名字的处理时间是三个时钟周期 |
 |
60
Rainyf 2021-01-25 14:10:44 +08:00
@tiancaixiaoshuai 哈哈哈绝了
|
 |
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 就能算出来。这完全取决于你汇编写的怎么样，以及你的硬件条件。 |
 |
62
namelosw 2021-01-25 14:22:38 +08:00
搞个提前算好的读模型, 写入新名字的时候累加一下就好了
|
 |
63
shenlanAZ 2021-01-25 14:29:10 +08:00
提前 map reduce 好，存到数据库里。然后用 500ms 的速度从数据库里查出来。
|
 |
64
zlowly 2021-01-25 14:39:53 +08:00
不用说现在的 ES 这种方式可以做到（结果不精确），就算是以前的集中式关系数据库来说，这种需求也真没什么（结果精确）。例如用 Oracle，直接对姓名统计使用物化视图即可，其核心原理就是在原始数据变更时通过触发器更新统计数据而已。
|
 |
65
neetrorschach 2021-01-25 14:41:40 +08:00
如果数据不是实时更新的话用 kylin，会将选定维度的所有组合创建成索引保存在内存里。查询时只要限定字段在索引维度里，基本上是亚秒查询。
|
 |
66
AkideLiu 2021-01-25 14:41:52 +08:00 via iPhone
可能性是有的，你看 Google 存的数据比你大，响应也在毫毛级别。重点是有没有这个技术实力
|
 |
67
Takamine 2021-01-25 14:42:20 +08:00 via Android
昨天晚上算完，今天调接口都返回这个值。
|
 |
69
anonyp 2021-01-25 15:16:32 +08:00 via iPhone
clickhouse name 索引就行了吧，更快的话可以试试物化视图，这个场景应该很适合
|
 |
70
DollarKiller 2021-01-25 15:32:43 +08:00
多台机器一起 MapReduce
|
|
72
cage111 OP @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) |
 |
76
northisland 2021-01-25 16:23:31 +08:00
1.3G 次( 字符串摘要 + 哈希表 )
按 0.9s 速度进行并发执行。0.1s 留个多个哈系表合并 + top10 排序。 |
|
78
tanszhe 2021-01-25 16:26:20 +08:00
|
 |
80
DrJoseph 2021-01-25 16:51:00 +08:00
坐等蚂蚁的同学提供 OceanBase 的可行方案，毕竟隔壁已经用 ClickHouse 解决了
传送门： https://www.v2ex.com/t/748196#reply8 |
 |
81
yuankui 2021-01-25 17:02:02 +08:00
1. 面向列的
2. 姓氏映射成一个 bit 3. bitmap ClickHouse 应该很简单 |
|
82
yuankui 2021-01-25 17:03:23 +08:00
这是哪个公司的面试题吗？
|
 |
83
lovecy 2021-01-25 17:05:14 +08:00
这个是静态数据，维护一份统计数据，每次更新静态数据时同时更新统计数据。
1s 内找出十个最多的人名，就是一条查询而已 |
 |
84
skies457 2021-01-25 17:08:53 +08:00
查询模式固定的话可以考虑自己用 C++写索引和查询，13 亿短字符串对于单机而言也不是很大的量级
|
 |
85
786375312123 2021-01-25 17:24:00 +08:00
@Mohanson 使用最多，看清楚了兄弟。你还是要把整个树过一遍才能知道那些频率最高
|
 |
86
yuyueMJ 2021-01-25 17:32:46 +08:00
@tiancaixiaoshuai 哈哈哈 牛逼
|
 |
87
fs418082760 2021-01-25 19:03:24 +08:00
百家姓拿来干吗的，老祖宗都统计好了。。。
|
|
88
Mohanson 2021-01-25 19:46:50 +08:00 via Android
@786375312123 设计成父节点的 count 是其所有子节点的 count 和，即使不做任何优化，最多循环一个 3500*3 长度的数组就能找到最大值；找到最大值后排除该根节点继续找最大值，往复 10 次就是 3500*3*10 次循环。
这是我想到的没任何优化的算法，仔细设计的话提个数量级也不是不可能 |
 |
89
ltoddy 2021-01-25 19:54:33 +08:00
使用字典树，循环一次就出来了。
|
|
90
Mohanson 2021-01-25 19:54:52 +08:00 via Android
如果在插入和移出数据时保证所有子树的顺序的话，那么查找一次最大值的时间复杂度就是 O(1)，代价是插入和删除的时候计算量会变大很多，不过不是大问题，毕竟是读优先的
|
 |
91
xcstream 2021-01-25 20:00:06 +08:00
插入的时候就排好了， 只需 0.0001 秒
|
|
92
786375312123 2021-01-25 21:39:26 +08:00
@Mohanson 可是你依然需要遍历所有的名字以后才能知道某个子节点上对应的数字是多少。建立树的成本依然是 o(n)
|
 |
93
moult 2021-01-25 22:12:12 +08:00
结合实际情况，如果可行的话，预处理的时候，把那些独一无二的名字先全部踢掉，数据少一大半。
|
 |
94
lululau 2021-01-25 22:18:41 +08:00
select * from top_names;
|
 |
96
tedzhou1221 2021-01-26 00:03:01 +08:00 via iPhone
感觉你是想做用户画像，精准推送
|
 |
97
alazysun 2021-01-26 00:44:46 +08:00
数据录入的时候不就统计好了吗？
|
 |
99
ericls 2021-01-26 01:22:04 +08:00 via iPhone
用 columnar 数据库
|
 |
100
lxfxf 2021-01-26 06:23:05 +08:00 1
统计学方法，直接随机落点一百万次，再统计不就好
这题应该改一下，找出最少的十个姓 |
Select Language