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

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

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

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

[egglin]

ES 应该不错

[ic2y]

一个用户可能有多个订单，但是一个订单只能属于 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 里。

[ic2y]

上面的第二句打错了。是合规的 pair 会有漏洞之鱼。 过滤器说是合规的，其实只是碰撞了。

[woodensail]

我又去查了下布隆过滤器的 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，有不到百万分之一的概率被穿透。还算可以吧。

[woodensail]

不对，上面这个方案总碰撞数量大概在 1 万条，随便找点什么东西存下就好。没必要为了记录碰撞额外再开 4GB 内存。
甚至如果把 hash 数量提升到 10，那么碰撞数量的期望值应该不超过 10 个……

[vnex]

@woodensail

你是说，对 ID 进行新旧分类处理，老的 ID， 走旧的映射，新的 ID 走新的映射？

[vnex]

@woodensail
@luckyrayyy 那另外一个问题是，扩容后，峰值过后，怎么减少机器配置，因为像微信红包，可以存活 24 小时，如果你使用了新的 ID hash 方案，如果峰值过后，减少机器，那么 hash 方案会出现问题

[MinQ]

我觉得应该是 Hive+ElasticSearch 吧？ Hive 负责存数据，ElasticSearch 负责热数据搜索，冷数据直接 Hive SQL ？

[palfortime]

订单 id 把日期带上，再用按天分表不就可以吗？然后再按 id hash 分多一次。只是要检查订单 id 与用户 id 是否匹配，不一定要按用户 id 查。

[woodensail]

@vnex 不是，举个例子，比如我计划扩容到原来的 5 倍，也就是新集群大小是旧集群的 4 倍。
那么我就在配置里面写下 id 0-1 结尾的进老集群，id2-9 结尾的进新集群。然后把老集群中所有 2-9 的数据往新集群复制(复制过程中的新数据需要在两边都落)。
等预热完成后，ng 把所有 2-9 结尾的流量导向新集群。然后老集群就可以把 2-9 相关的数据删掉了。

在缩容的时候，把新集群中的数据全部写回老集群，然后流量倒回，销毁新集群即可。

这套方案主要用于大促临时扩容，大促结束后还会到原状的场景，对于需要跟据负载频繁扩缩容的场景可能不合适(毕竟海量数据来回写不太现实)

最后，说真的我觉得布隆过滤器的方案赞爆了。

[reus]

不就建个索引的事情嘛，用 rocksdb 存就行了，单线程读至少一万 tuple/sec，128 线程并发，一千万也就十几秒。内存越大越好，磁盘越快越好。
逻辑太简单，根本不需要复杂技术。

[yuk1no]

@p2pCoder 谢谢指导🙏murmurhash 是个好思路。不过这里也有个问题，如果是存 local map，数据的全量加载也会很慢吧？如果重启服务都需要来一遍，可能会不太好。
bitmap 应该不行，order id 超过了 int32 范围，对于 int64，数据太过稀疏，也就是 bitmap 太浪费了。
@woodensail 谢谢指导🙏后来也考虑过这个，但是不能保证一定存在吧。可能存在的话，然后去查表，这样适合大多数无效的场景，如果大多数有效可能不太合适。压力还是落在了 db 上

[yuk1no]

@ic2y 谢谢指导🙏 没怎么用过 HBase，这个思路我要先了解一下

[yuk1no]

@MinQ 请问如何判断冷热数据呢，如果要判断冷数据，Hive SQL 速度应该比较慢吧

@reus 谢谢指导，没有了解过 rocksdb，我先去学习一下

[insert000]

持续关注，菜鸡等一个标准答案。

[hanhan13]

看起来像是一道分布式系统设计题。首先算一下，一百亿订单 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，保证最终一致性。
大致想到这么多，欢迎大佬们批评指正。

[hanhan13]

貌似忘了应用层的设计。判断 valid 的话，最简单粗暴的方案是直接在内存里遍历 value，假设平均每人有 1 万个订单号，直接遍历速度已经足够快了。如果 orderid 有规律的话，比如有时间顺序，就可以二分查找，应该能在微秒级搞定。

[woodensail]

@yuk1no 我上面提了只有发生碰撞才需要去查表。你需要首先校验是否在碰撞记录中，如果在就直接查表，如果不在，就用布隆过滤器去判断。
然后上面我也列了不同参数下的过滤器碰撞概率，已经小到可以忽略了，对性能影响几乎为 0

[p2pCoder]

@yuk1no 本地 map 速度比写入 nosql 快很多
四十核机器，开 400 个线程从 hdfs 拉去 70 亿行的数据的，处理字符串，存成 long double 的 key value
不超过十分钟，如果是分区增量，就更快了
spark 分布式 开 100 个 executor 写到 redis，与单机的本地 map 写入相比，速度距离差距也很大，要是 hbase，就更慢了
读的速度，本地 map 也快的多

有条件的话，建议找几台大机器自己折腾，做 benchamark

[p2pCoder]

@hanhan13 方向有点错了，这其实并不是个在线的服务
一次查询千万对数据，这其实是个批处理的接口
输入和输出都不可能直接用 rpc 通信传输

[xy2020]

用户和订单是一对多，但订单对用户可不是一对一：需要考虑新业务模式的需要，例如代付业务。

[tolerance]

只是确认有没有，上 bloom filter

[MinQ]

@yuk1no 根据订单生成时间做切分，其实 Hive SQL 在集群环境下速度不慢，大量数据返回来大概需要几分钟

[MinQ]

@yuk1no 冷热数据判断在更新的时候处理，新数据同步进 es 和 hive，es 再去除老数据

[dingyaguang117]

@woodensail 标记冲突不可行吧 对于任意一个新值，都有可能冲突 第一个布隆过滤器就失效了

[woodensail]

@dingyaguang117 为什么这么说？按我的设想凡是存在冲突的都已经标记在第一个布隆过滤器了，也就是如果发现当前数据能命中第一个布隆过滤器，则直接查库。

[dingyaguang117]

@woodensail 你说的存在冲突是 正确数据跟正确数据的冲突吧？ 查询数据 跟正确数据冲突的情况呢

[woodensail]

@dingyaguang117 嗯，你是说考虑业务场景类似于 INSERT ON DUPLICATE KEY 吧。这种倒是更简单了，单层过滤器即可。只要命中了就去查库，以避免假阳性。