一道面试题给我整懵了，求指导

[yuk1no]

某大厂二面，前面算法啊项目啊还比较正常，最后直接整了这样一道题。

要求设计一个这样的系统：
1. 能够支撑一百亿订单 id，一亿个用户 id，每天增量更新
2. 提供查询“用户 id-订单 id”pair 是否 valid 的服务
3. 一次查询最多一千万对数据，响应时间越低越好


我懵了，想了半天挤出来了一个 redis set 存数据，t+1 更新，接口接受 csv 文件，面试官不是很满意😂
现在大厂都是这种数据量级吗，动不动就百亿？

[luckyrayyy]

系统设计题考的就是你思维严谨逻辑缜密的能力，另外对各种分布式、高可用架构的熟悉程度。
我也从来没设计过这么大量级的产品，如果是我的话可能会这样设计：
0 、首先应该一个订单号对应一个用户吧，一个用户可能对应多个订单，就是有个一对多的关系。
1 、根据用户 ID 垂直切分，可以 hash 到不同的机器上处理，Redis Memcachee 啥的怼上。
2 、关联度高的数据放到同一台物理机或者至少同一个机房里，减少跨区域的查询。

更详细的方案可以参考这个：
[百亿级微信红包的高并发资金交易系统设计方案]( https://www.infoq.cn/article/2017hongbao-weixin)

[Vegetable]

故意说这么大的数据规模，应该是为了提示你这个必须做分布式处理吧。

[keepeye]

上 tidb

[winnie2012]

用户表增长慢，分布式存储即可。
订单表分冷热数据，热数据按用户分布式存储，冷数据放 OLDP 分布式数据库。

[vnex]

@luckyrayyy 根据 ID hash 到不同的 机器上，要怎么扩容，一扩容不就 hash 到别的机器上了吗？

[vnex]

@luckyrayyy 譬如搞活动，用户超出预想的量，能不能临时加机器，还是要等机扩容？

[vnex]

等机扩容？ 停机扩容

[luckyrayyy]

@vnex 保证能 hash 到原机器上就行呗，一致性 hash，或者虚拟节点？

[Vegetable]

@vnex 根据用户 ID 分片的话，可以考虑不用 Hash，根据 ID 的自增属性或者 ct 来分片，避免新增数据位置不确定，扩容影响存量数据储存位置的问题，但是这样又会冷热不均。
按照用户 ID 分片本身就是一个反直觉的设计，只是针对题面需求做出的设计吧。

[vnex]

@luckyrayyy 一致性 hash 在加减节点的时候，也会有少部分的数据落到别的节点上啊

[vnex]

@Vegetable ct 是什么 create time?

[luckyrayyy]

@vnex 那就迁移数据呗，先复制数据过去，再把之前的删掉，然后再启用新的节点。

[vnex]

@luckyrayyy 唔，你这个已经到持久层了，我是问，处理请求的时候，将同一个红包 ID 串行到同一个逻辑节点，然后这种情况要怎么动态扩容

[luckyrayyy]

@vnex 我没太明白什么意思...我设想的就跟 Redis 集群类似，扩容也是一样吧

[vnex]

@luckyrayyy 多个人抢红包，然后这些用户的抢的红包 ID 是同一个，连接层根据红包 ID hash 到同一个逻辑节点，由逻辑节点进行串行处理，那么如何对逻辑节点进行扩容，因为扩容的时候， 红包 ID 可能 hash 到别的逻辑节点了

[woodensail]

@vnex 以前后端的同事做过这种需求。

似乎是这样：使用 ng 来进行流量分发。
执行扩容时，先把新集群进行预热，按配置文件将特定 id 范围的数据从老集群复制到新集群。（包括新的写入）
预热完毕后 ng 切到新规则，部分 id 段打到老集群，部分 id 段打到新集群，集群内部再分片，从而平衡新老集群的负载

大概是这样吧，我只是跟他们聊天的时候听说过，具体细节不清楚。

[p2pCoder]

可以考虑用本地 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 的数据结构性能高几百倍可能还不止，成本也更低

[woodensail]

哈，楼上这么一提我倒是想起了布隆过滤器。楼上说的 butmap 应该就是指这个吧。
要是对正确性要求不高的话，按楼上那样 hash 后取 hash 结果的一部分来做布隆过滤器。取的位数越多，错误概率越小，内存占用越大。40 位的布隆过滤器需要 4GB 内存。

[woodensail]

@woodensail 啊，有个错别字，bitmap

[woodensail]

嗯，再扩展一下，布隆过滤器的误报其实是可以解决的。用两个布隆过滤器，第一个用来标记碰撞，读取的时候先检查该过滤器，如果发现碰撞就穿透到数据库或者下一级缓存手段。没发现碰撞的话，则跟据第二个过滤器来判断是否有效。

然后写入的时候一般往第二个过滤器写，如果发现打算写的位置已经被写过，则认为发生碰撞，去第一个过滤器写碰撞标记。