1
luckyrayyy 2020-05-19 15:55:46 +08:00
系统设计题考的就是你思维严谨逻辑缜密的能力,另外对各种分布式、高可用架构的熟悉程度。
我也从来没设计过这么大量级的产品,如果是我的话可能会这样设计: 0 、首先应该一个订单号对应一个用户吧,一个用户可能对应多个订单,就是有个一对多的关系。 1 、根据用户 ID 垂直切分,可以 hash 到不同的机器上处理,Redis Memcachee 啥的怼上。 2 、关联度高的数据放到同一台物理机或者至少同一个机房里,减少跨区域的查询。 更详细的方案可以参考这个: [百亿级微信红包的高并发资金交易系统设计方案]( https://www.infoq.cn/article/2017hongbao-weixin) |
2
Vegetable 2020-05-19 16:11:54 +08:00
故意说这么大的数据规模,应该是为了提示你这个必须做分布式处理吧。
|
3
keepeye 2020-05-19 16:17:30 +08:00
上 tidb
|
4
winnie2012 2020-05-19 16:18:36 +08:00
用户表增长慢,分布式存储即可。
订单表分冷热数据,热数据按用户分布式存储,冷数据放 OLDP 分布式数据库。 |
5
vnex 2020-05-19 16:24:02 +08:00
@luckyrayyy 根据 ID hash 到不同的 机器上,要怎么扩容,一扩容不就 hash 到别的机器上了吗?
|
6
vnex 2020-05-19 16:25:00 +08:00
@luckyrayyy 譬如搞活动,用户超出预想的量,能不能临时加机器,还是要等机扩容?
|
7
vnex 2020-05-19 16:25:17 +08:00
等机扩容? 停机扩容
|
8
luckyrayyy 2020-05-19 16:33:04 +08:00
@vnex 保证能 hash 到原机器上就行呗,一致性 hash,或者虚拟节点?
|
9
Vegetable 2020-05-19 16:38:40 +08:00 1
@vnex 根据用户 ID 分片的话,可以考虑不用 Hash,根据 ID 的自增属性或者 ct 来分片,避免新增数据位置不确定,扩容影响存量数据储存位置的问题,但是这样又会冷热不均。
按照用户 ID 分片本身就是一个反直觉的设计,只是针对题面需求做出的设计吧。 |
10
vnex 2020-05-19 16:40:46 +08:00
@luckyrayyy 一致性 hash 在加减节点的时候,也会有少部分的数据落到别的节点上啊
|
12
luckyrayyy 2020-05-19 16:59:55 +08:00
@vnex 那就迁移数据呗,先复制数据过去,再把之前的删掉,然后再启用新的节点。
|
13
vnex 2020-05-19 17:07:01 +08:00
@luckyrayyy 唔,你这个已经到持久层了,我是问,处理请求的时候,将同一个红包 ID 串行到同一个逻辑节点,然后这种情况要怎么动态扩容
|
14
luckyrayyy 2020-05-19 17:16:48 +08:00
@vnex 我没太明白什么意思...我设想的就跟 Redis 集群类似,扩容也是一样吧
|
15
vnex 2020-05-19 17:38:16 +08:00
@luckyrayyy 多个人抢红包,然后这些用户的抢的红包 ID 是同一个,连接层根据红包 ID hash 到同一个逻辑节点,由逻辑节点进行串行处理,那么如何对逻辑节点进行扩容,因为扩容的时候, 红包 ID 可能 hash 到别的逻辑节点了
|
16
woodensail 2020-05-19 17:39:11 +08:00
@vnex 以前后端的同事做过这种需求。
似乎是这样:使用 ng 来进行流量分发。 执行扩容时,先把新集群进行预热,按配置文件将特定 id 范围的数据从老集群复制到新集群。(包括新的写入) 预热完毕后 ng 切到新规则,部分 id 段打到老集群,部分 id 段打到新集群,集群内部再分片,从而平衡新老集群的负载 大概是这样吧,我只是跟他们聊天的时候听说过,具体细节不清楚。 |
17
p2pCoder 2020-05-19 17:56:36 +08:00
可以考虑用本地 map
把用户 id-订单 id 的拼接字符串取 murmurhash,可以用 48 位或者 64 位的 我在项目中曾用 64 位整型存过 50 亿-100 亿个 string key 的 map,把 string 用 murmurhash 转为 64 位整型后,测过几次,碰撞个数为 0,内存占用在 一百多 G 左右,map 是 key 为 64 位整型,value 位 double,你这个问题,占用的内存更小 高端点,可以考虑设计个 bitmap 之类,这样查找速度会更快,这种还需要懂算法的更精细的设计 存到 nosql 里面会慢很多,你找几个 128 核 500G 内存的机器,存个本地 map,肯定比用 nosql 的数据结构性能高几百倍可能还不止,成本也更低 |
18
woodensail 2020-05-19 18:37:31 +08:00
哈,楼上这么一提我倒是想起了布隆过滤器。楼上说的 butmap 应该就是指这个吧。
要是对正确性要求不高的话,按楼上那样 hash 后取 hash 结果的一部分来做布隆过滤器。取的位数越多,错误概率越小,内存占用越大。40 位的布隆过滤器需要 4GB 内存。 |
19
woodensail 2020-05-19 18:37:50 +08:00
@woodensail 啊,有个错别字,bitmap
|
20
woodensail 2020-05-19 18:43:39 +08:00 1
嗯,再扩展一下,布隆过滤器的误报其实是可以解决的。用两个布隆过滤器,第一个用来标记碰撞,读取的时候先检查该过滤器,如果发现碰撞就穿透到数据库或者下一级缓存手段。没发现碰撞的话,则跟据第二个过滤器来判断是否有效。
然后写入的时候一般往第二个过滤器写,如果发现打算写的位置已经被写过,则认为发生碰撞,去第一个过滤器写碰撞标记。 |
21
egglin 2020-05-19 18:47:00 +08:00
ES 应该不错
|
22
ic2y 2020-05-19 19:12:13 +08:00
一个用户可能有多个订单,但是一个订单只能属于 1 个用户。 而且订单是百亿级,还每天增量更新。那么感觉常规数据库应该满足不了这个需求。
具体的存储,可以考虑用 HBase,用 用户 id+订单 id,作为 rowkey 进行信息存储。 1.查看 用户 id-订单 id 组合是否有效时。如果内存全量建模存储,应该是资源要求蛮高的。可以考虑用布隆过滤器。因为属于用户 1 的订单 111,永远都属于用户 1,具有不变性。所以布隆过滤器,适合这种场景,可以一直叠加。 通过第一层过滤,快速过滤出来不能 vaild 的 pair 。 2.鉴于布隆过滤器的误报的特点。不合规的 pair 会有漏网之鱼,但是到这一层数量会很少了。组装这些 pair,做成 TreeSet,找到 rowkey 的上界和下界,然后使用 HBase 的 OnlyRawKey 的 Scanner 的 Filter,只扫描 rowkey 。因为 rowkey 本来是 b 树的,线性扫描的时候,判断 rowkey 是否在 TreeSet 里。 |
23
ic2y 2020-05-19 19:15:07 +08:00
上面的第二句打错了。是合规的 pair 会有漏洞之鱼。 过滤器说是合规的,其实只是碰撞了。
|
24
woodensail 2020-05-19 19:36:37 +08:00
我又去查了下布隆过滤器的 wiki 。算了下误报率。
按 4GB 的过滤器存储 100 亿条数据来算,如果是最简单的只用 1 个 hash,则误判率约为 0.01 ; 而理论最佳值是用约 70 个 hash,此时误报率是 1e-23 。碰撞概率微乎其微。 不过 70 个 hash 代价有些大,可以折中一下,10 个 hash 时误报率 6e-11,5 个 hash 时误报率 2.8e-7 。个人认为 5 个 hash 是个不错的选择,穿透缓存的概率不算大,计算效率也不算太低。 所以最终方案 100 亿条数据,使用双布隆过滤器一共消耗 8GB 内存,hash 数量 5,有不到百万分之一的概率被穿透。还算可以吧。 |
25
woodensail 2020-05-19 19:44:11 +08:00
不对,上面这个方案总碰撞数量大概在 1 万条,随便找点什么东西存下就好。没必要为了记录碰撞额外再开 4GB 内存。
甚至如果把 hash 数量提升到 10,那么碰撞数量的期望值应该不超过 10 个…… |
26
vnex 2020-05-19 19:52:23 +08:00
|
27
vnex 2020-05-19 20:21:56 +08:00
@woodensail
@luckyrayyy 那另外一个问题是,扩容后,峰值过后,怎么减少机器配置,因为像微信红包,可以存活 24 小时,如果你使用了新的 ID hash 方案,如果峰值过后,减少机器,那么 hash 方案会出现问题 |
28
MinQ 2020-05-19 20:22:41 +08:00
我觉得应该是 Hive+ElasticSearch 吧? Hive 负责存数据,ElasticSearch 负责热数据搜索,冷数据直接 Hive SQL ?
|
29
palfortime 2020-05-19 20:25:41 +08:00 via Android
订单 id 把日期带上,再用按天分表不就可以吗?然后再按 id hash 分多一次。只是要检查订单 id 与用户 id 是否匹配,不一定要按用户 id 查。
|
30
woodensail 2020-05-19 20:43:32 +08:00
@vnex 不是,举个例子,比如我计划扩容到原来的 5 倍,也就是新集群大小是旧集群的 4 倍。
那么我就在配置里面写下 id 0-1 结尾的进老集群,id2-9 结尾的进新集群。然后把老集群中所有 2-9 的数据往新集群复制(复制过程中的新数据需要在两边都落)。 等预热完成后,ng 把所有 2-9 结尾的流量导向新集群。然后老集群就可以把 2-9 相关的数据删掉了。 在缩容的时候,把新集群中的数据全部写回老集群,然后流量倒回,销毁新集群即可。 这套方案主要用于大促临时扩容,大促结束后还会到原状的场景,对于需要跟据负载频繁扩缩容的场景可能不合适(毕竟海量数据来回写不太现实) 最后,说真的我觉得布隆过滤器的方案赞爆了。 |
31
reus 2020-05-19 20:55:43 +08:00
不就建个索引的事情嘛,用 rocksdb 存就行了,单线程读至少一万 tuple/sec,128 线程并发,一千万也就十几秒。内存越大越好,磁盘越快越好。
逻辑太简单,根本不需要复杂技术。 |
32
yuk1no OP @p2pCoder 谢谢指导🙏murmurhash 是个好思路。不过这里也有个问题,如果是存 local map,数据的全量加载也会很慢吧?如果重启服务都需要来一遍,可能会不太好。
bitmap 应该不行,order id 超过了 int32 范围,对于 int64,数据太过稀疏,也就是 bitmap 太浪费了。 @woodensail 谢谢指导🙏后来也考虑过这个,但是不能保证一定存在吧。可能存在的话,然后去查表,这样适合大多数无效的场景,如果大多数有效可能不太合适。压力还是落在了 db 上 |
34
yuk1no OP |
35
insert000 2020-05-19 22:19:03 +08:00
持续关注,菜鸡等一个标准答案。
|
36
hanhan13 2020-05-19 22:46:42 +08:00
看起来像是一道分布式系统设计题。首先算一下,一百亿订单 id 和一亿用户 id 一共 10G 左右(假设每个 id 占 8byte),数据量不算大,就算每天都新增一百亿订单,5 年的存储需求也不过 20T 左右。但问题在于并发很高,可以粗略认为系统的 QPS 要求达为一千万。
设计思路如下: 1. 系统架构。自上而下分为 4 层:网关层--->应用层--->缓存层--->数据层。 2. 存储系统。 首先考虑数据模型,系统里涉及到的数据为用户 id 和订单 id,两者为一对多的关系。由于 QPS 的高需求以及无事务需求,应该优先选择 NoSQL 。针对一对多的关系,可以考虑列存储数据库,比如 HBase 和 Cassandra 。每个用户对应一行数据,大约这个样子:uid(主键) | "orderid1, orderid2......" 。其次是缓存层的设计,可以使用 redis 或 memcached 对请求结果进行缓存,使用 LFU 策略,缓存 20%的数据(根据 28 原则),当然一开始这小数据量,全缓存也没关系。 3. 扩展性。高 QPS 以及系统持续增长决定了必须考虑可扩展。扩展主要是两点:i). 分表分库分片; ii). 请求的负载均衡。对于 i,可以考虑按照 userid 对数据进行 hash 分片,范围 hash 和一致性 hash 都可以满足要求,一致性 hash 更万金油一些。可以考虑直接做 100 个分区,前期可以将每 10 个分区物理上放在一起,后期需求上来了再迁移。对于 ii,上面提到的 4 层两两之间都可以添加负载均衡,目的是避免出现热点,以及保障每层功能高可用。 4. 容错。一是缓存层需要使用副本,主要用来分担读请求,防止数据库击穿。二是分区的数据库需要副本,主要是保存数据,也能分担读请求。副本方案一般是单 master 多 slavor,保证最终一致性。 大致想到这么多,欢迎大佬们批评指正。 |
37
hanhan13 2020-05-19 23:00:50 +08:00
貌似忘了应用层的设计。判断 valid 的话,最简单粗暴的方案是直接在内存里遍历 value,假设平均每人有 1 万个订单号,直接遍历速度已经足够快了。如果 orderid 有规律的话,比如有时间顺序,就可以二分查找,应该能在微秒级搞定。
|
38
woodensail 2020-05-19 23:02:49 +08:00 via Android
@yuk1no 我上面提了只有发生碰撞才需要去查表。你需要首先校验是否在碰撞记录中,如果在就直接查表,如果不在,就用布隆过滤器去判断。
然后上面我也列了不同参数下的过滤器碰撞概率,已经小到可以忽略了,对性能影响几乎为 0 |
39
p2pCoder 2020-05-19 23:11:59 +08:00
@yuk1no 本地 map 速度比写入 nosql 快很多
四十核机器,开 400 个线程从 hdfs 拉去 70 亿行的数据的,处理字符串,存成 long double 的 key value 不超过十分钟,如果是分区增量,就更快了 spark 分布式 开 100 个 executor 写到 redis,与单机的本地 map 写入相比,速度距离差距也很大,要是 hbase,就更慢了 读的速度,本地 map 也快的多 有条件的话,建议找几台大机器自己折腾,做 benchamark |
40
p2pCoder 2020-05-19 23:16:14 +08:00
|
41
xy2020 2020-05-19 23:43:09 +08:00 via Android
用户和订单是一对多,但订单对用户可不是一对一:需要考虑新业务模式的需要,例如代付业务。
|
42
tolerance 2020-05-19 23:57:41 +08:00
只是确认有没有,上 bloom filter
|
43
MinQ 2020-05-20 00:21:49 +08:00 via Android
@yuk1no 根据订单生成时间做切分,其实 Hive SQL 在集群环境下速度不慢,大量数据返回来大概需要几分钟
|
45
dingyaguang117 2021-01-17 04:59:26 +08:00 via iPhone
@woodensail 标记冲突不可行吧 对于任意一个新值,都有可能冲突 第一个布隆过滤器就失效了
|
46
woodensail 2021-01-18 08:52:55 +08:00
@dingyaguang117 为什么这么说?按我的设想凡是存在冲突的都已经标记在第一个布隆过滤器了,也就是如果发现当前数据能命中第一个布隆过滤器,则直接查库。
|
47
dingyaguang117 2021-01-18 12:35:49 +08:00 via iPhone
@woodensail 你说的存在冲突是 正确数据跟正确数据的冲突吧? 查询数据 跟正确数据冲突的情况呢
|
48
woodensail 2021-01-18 16:49:07 +08:00
@dingyaguang117 嗯,你是说考虑业务场景类似于 INSERT ON DUPLICATE KEY 吧。这种倒是更简单了,单层过滤器即可。只要命中了就去查库,以避免假阳性。
|