这是一个创建于 1684 天前的主题，其中的信息可能已经有所发展或是发生改变。
某大厂二面，前面算法啊项目啊还比较正常，最后直接整了这样一道题。
要求设计一个这样的系统：
1. 能够支撑一百亿订单 id，一亿个用户 id，每天增量更新
2. 提供查询“用户 id-订单 id”pair 是否 valid 的服务
3. 一次查询最多一千万对数据，响应时间越低越好
我懵了，想了半天挤出来了一个 redis set 存数据，t+1 更新，接口接受 csv 文件，面试官不是很满意😂
现在大厂都是这种数据量级吗，动不动就百亿？
要求设计一个这样的系统：
1. 能够支撑一百亿订单 id，一亿个用户 id，每天增量更新
2. 提供查询“用户 id-订单 id”pair 是否 valid 的服务
3. 一次查询最多一千万对数据，响应时间越低越好
我懵了，想了半天挤出来了一个 redis set 存数据，t+1 更新，接口接受 csv 文件，面试官不是很满意😂
现在大厂都是这种数据量级吗，动不动就百亿？
 |
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 1
@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 吧。这种倒是更简单了，单层过滤器即可。只要命中了就去查库，以避免假阳性。
|
Select Language