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

[yuk1no]

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

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


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

[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 通信传输