V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
yuk1no
V2EX  ›  问与答

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

  •  
  •   yuk1no · 2020-05-19 15:32:22 +08:00 via iPhone · 4454 次点击
    这是一个创建于 1633 天前的主题,其中的信息可能已经有所发展或是发生改变。
    某大厂二面,前面算法啊项目啊还比较正常,最后直接整了这样一道题。

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


    我懵了,想了半天挤出来了一个 redis set 存数据,t+1 更新,接口接受 csv 文件,面试官不是很满意😂
    现在大厂都是这种数据量级吗,动不动就百亿?
    48 条回复    2021-01-18 16:49:07 +08:00
    luckyrayyy
        1
    luckyrayyy  
       2020-05-19 15:55:46 +08:00
    系统设计题考的就是你思维严谨逻辑缜密的能力,另外对各种分布式、高可用架构的熟悉程度。
    我也从来没设计过这么大量级的产品,如果是我的话可能会这样设计:
    0 、首先应该一个订单号对应一个用户吧,一个用户可能对应多个订单,就是有个一对多的关系。
    1 、根据用户 ID 垂直切分,可以 hash 到不同的机器上处理,Redis Memcachee 啥的怼上。
    2 、关联度高的数据放到同一台物理机或者至少同一个机房里,减少跨区域的查询。

    更详细的方案可以参考这个:
    [百亿级微信红包的高并发资金交易系统设计方案]( https://www.infoq.cn/article/2017hongbao-weixin)
    Vegetable
        2
    Vegetable  
       2020-05-19 16:11:54 +08:00
    故意说这么大的数据规模,应该是为了提示你这个必须做分布式处理吧。
    keepeye
        3
    keepeye  
       2020-05-19 16:17:30 +08:00
    上 tidb
    winnie2012
        4
    winnie2012  
       2020-05-19 16:18:36 +08:00
    用户表增长慢,分布式存储即可。
    订单表分冷热数据,热数据按用户分布式存储,冷数据放 OLDP 分布式数据库。
    vnex
        5
    vnex  
       2020-05-19 16:24:02 +08:00
    @luckyrayyy 根据 ID hash 到不同的 机器上,要怎么扩容,一扩容不就 hash 到别的机器上了吗?
    vnex
        6
    vnex  
       2020-05-19 16:25:00 +08:00
    @luckyrayyy 譬如搞活动,用户超出预想的量,能不能临时加机器,还是要等机扩容?
    vnex
        7
    vnex  
       2020-05-19 16:25:17 +08:00
    等机扩容? 停机扩容
    luckyrayyy
        8
    luckyrayyy  
       2020-05-19 16:33:04 +08:00
    @vnex 保证能 hash 到原机器上就行呗,一致性 hash,或者虚拟节点?
    Vegetable
        9
    Vegetable  
       2020-05-19 16:38:40 +08:00   ❤️ 1
    @vnex 根据用户 ID 分片的话,可以考虑不用 Hash,根据 ID 的自增属性或者 ct 来分片,避免新增数据位置不确定,扩容影响存量数据储存位置的问题,但是这样又会冷热不均。
    按照用户 ID 分片本身就是一个反直觉的设计,只是针对题面需求做出的设计吧。
    vnex
        10
    vnex  
       2020-05-19 16:40:46 +08:00
    @luckyrayyy 一致性 hash 在加减节点的时候,也会有少部分的数据落到别的节点上啊
    vnex
        11
    vnex  
       2020-05-19 16:44:16 +08:00
    @Vegetable ct 是什么 create time?
    luckyrayyy
        12
    luckyrayyy  
       2020-05-19 16:59:55 +08:00
    @vnex 那就迁移数据呗,先复制数据过去,再把之前的删掉,然后再启用新的节点。
    vnex
        13
    vnex  
       2020-05-19 17:07:01 +08:00
    @luckyrayyy 唔,你这个已经到持久层了,我是问,处理请求的时候,将同一个红包 ID 串行到同一个逻辑节点,然后这种情况要怎么动态扩容
    luckyrayyy
        14
    luckyrayyy  
       2020-05-19 17:16:48 +08:00
    @vnex 我没太明白什么意思...我设想的就跟 Redis 集群类似,扩容也是一样吧
    vnex
        15
    vnex  
       2020-05-19 17:38:16 +08:00
    @luckyrayyy 多个人抢红包,然后这些用户的抢的红包 ID 是同一个,连接层根据红包 ID hash 到同一个逻辑节点,由逻辑节点进行串行处理,那么如何对逻辑节点进行扩容,因为扩容的时候, 红包 ID 可能 hash 到别的逻辑节点了
    woodensail
        16
    woodensail  
       2020-05-19 17:39:11 +08:00
    @vnex 以前后端的同事做过这种需求。

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

    大概是这样吧,我只是跟他们聊天的时候听说过,具体细节不清楚。
    p2pCoder
        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 的数据结构性能高几百倍可能还不止,成本也更低
    woodensail
        18
    woodensail  
       2020-05-19 18:37:31 +08:00
    哈,楼上这么一提我倒是想起了布隆过滤器。楼上说的 butmap 应该就是指这个吧。
    要是对正确性要求不高的话,按楼上那样 hash 后取 hash 结果的一部分来做布隆过滤器。取的位数越多,错误概率越小,内存占用越大。40 位的布隆过滤器需要 4GB 内存。
    woodensail
        19
    woodensail  
       2020-05-19 18:37:50 +08:00
    @woodensail 啊,有个错别字,bitmap
    woodensail
        20
    woodensail  
       2020-05-19 18:43:39 +08:00   ❤️ 1
    嗯,再扩展一下,布隆过滤器的误报其实是可以解决的。用两个布隆过滤器,第一个用来标记碰撞,读取的时候先检查该过滤器,如果发现碰撞就穿透到数据库或者下一级缓存手段。没发现碰撞的话,则跟据第二个过滤器来判断是否有效。

    然后写入的时候一般往第二个过滤器写,如果发现打算写的位置已经被写过,则认为发生碰撞,去第一个过滤器写碰撞标记。
    egglin
        21
    egglin  
       2020-05-19 18:47:00 +08:00
    ES 应该不错
    ic2y
        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 里。
    ic2y
        23
    ic2y  
       2020-05-19 19:15:07 +08:00
    上面的第二句打错了。是合规的 pair 会有漏洞之鱼。 过滤器说是合规的,其实只是碰撞了。
    woodensail
        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,有不到百万分之一的概率被穿透。还算可以吧。
    woodensail
        25
    woodensail  
       2020-05-19 19:44:11 +08:00
    不对,上面这个方案总碰撞数量大概在 1 万条,随便找点什么东西存下就好。没必要为了记录碰撞额外再开 4GB 内存。
    甚至如果把 hash 数量提升到 10,那么碰撞数量的期望值应该不超过 10 个……
    vnex
        26
    vnex  
       2020-05-19 19:52:23 +08:00
    @woodensail

    你是说,对 ID 进行新旧分类处理,老的 ID, 走旧的映射,新的 ID 走新的映射?
    vnex
        27
    vnex  
       2020-05-19 20:21:56 +08:00
    @woodensail
    @luckyrayyy 那另外一个问题是,扩容后,峰值过后,怎么减少机器配置,因为像微信红包,可以存活 24 小时,如果你使用了新的 ID hash 方案,如果峰值过后,减少机器,那么 hash 方案会出现问题
    MinQ
        28
    MinQ  
       2020-05-19 20:22:41 +08:00
    我觉得应该是 Hive+ElasticSearch 吧? Hive 负责存数据,ElasticSearch 负责热数据搜索,冷数据直接 Hive SQL ?
    palfortime
        29
    palfortime  
       2020-05-19 20:25:41 +08:00 via Android
    订单 id 把日期带上,再用按天分表不就可以吗?然后再按 id hash 分多一次。只是要检查订单 id 与用户 id 是否匹配,不一定要按用户 id 查。
    woodensail
        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 相关的数据删掉了。

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

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

    最后,说真的我觉得布隆过滤器的方案赞爆了。
    reus
        31
    reus  
       2020-05-19 20:55:43 +08:00
    不就建个索引的事情嘛,用 rocksdb 存就行了,单线程读至少一万 tuple/sec,128 线程并发,一千万也就十几秒。内存越大越好,磁盘越快越好。
    逻辑太简单,根本不需要复杂技术。
    yuk1no
        32
    yuk1no  
    OP
       2020-05-19 22:09:34 +08:00 via iPhone   ❤️ 1
    @p2pCoder 谢谢指导🙏murmurhash 是个好思路。不过这里也有个问题,如果是存 local map,数据的全量加载也会很慢吧?如果重启服务都需要来一遍,可能会不太好。
    bitmap 应该不行,order id 超过了 int32 范围,对于 int64,数据太过稀疏,也就是 bitmap 太浪费了。
    @woodensail 谢谢指导🙏后来也考虑过这个,但是不能保证一定存在吧。可能存在的话,然后去查表,这样适合大多数无效的场景,如果大多数有效可能不太合适。压力还是落在了 db 上
    yuk1no
        33
    yuk1no  
    OP
       2020-05-19 22:10:47 +08:00 via iPhone
    @ic2y 谢谢指导🙏 没怎么用过 HBase,这个思路我要先了解一下
    yuk1no
        34
    yuk1no  
    OP
       2020-05-19 22:14:09 +08:00 via iPhone
    @MinQ 请问如何判断冷热数据呢,如果要判断冷数据,Hive SQL 速度应该比较慢吧

    @reus 谢谢指导,没有了解过 rocksdb,我先去学习一下
    insert000
        35
    insert000  
       2020-05-19 22:19:03 +08:00
    持续关注,菜鸡等一个标准答案。
    hanhan13
        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,保证最终一致性。
    大致想到这么多,欢迎大佬们批评指正。
    hanhan13
        37
    hanhan13  
       2020-05-19 23:00:50 +08:00
    貌似忘了应用层的设计。判断 valid 的话,最简单粗暴的方案是直接在内存里遍历 value,假设平均每人有 1 万个订单号,直接遍历速度已经足够快了。如果 orderid 有规律的话,比如有时间顺序,就可以二分查找,应该能在微秒级搞定。
    woodensail
        38
    woodensail  
       2020-05-19 23:02:49 +08:00 via Android
    @yuk1no 我上面提了只有发生碰撞才需要去查表。你需要首先校验是否在碰撞记录中,如果在就直接查表,如果不在,就用布隆过滤器去判断。
    然后上面我也列了不同参数下的过滤器碰撞概率,已经小到可以忽略了,对性能影响几乎为 0
    p2pCoder
        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
    p2pCoder
        40
    p2pCoder  
       2020-05-19 23:16:14 +08:00
    @hanhan13 方向有点错了,这其实并不是个在线的服务
    一次查询千万对数据,这其实是个批处理的接口
    输入和输出都不可能直接用 rpc 通信传输
    xy2020
        41
    xy2020  
       2020-05-19 23:43:09 +08:00 via Android
    用户和订单是一对多,但订单对用户可不是一对一:需要考虑新业务模式的需要,例如代付业务。
    tolerance
        42
    tolerance  
       2020-05-19 23:57:41 +08:00
    只是确认有没有,上 bloom filter
    MinQ
        43
    MinQ  
       2020-05-20 00:21:49 +08:00 via Android
    @yuk1no 根据订单生成时间做切分,其实 Hive SQL 在集群环境下速度不慢,大量数据返回来大概需要几分钟
    MinQ
        44
    MinQ  
       2020-05-20 00:23:28 +08:00 via Android
    @yuk1no 冷热数据判断在更新的时候处理,新数据同步进 es 和 hive,es 再去除老数据
    dingyaguang117
        45
    dingyaguang117  
       2021-01-17 04:59:26 +08:00 via iPhone
    @woodensail 标记冲突不可行吧 对于任意一个新值,都有可能冲突 第一个布隆过滤器就失效了
    woodensail
        46
    woodensail  
       2021-01-18 08:52:55 +08:00
    @dingyaguang117 为什么这么说?按我的设想凡是存在冲突的都已经标记在第一个布隆过滤器了,也就是如果发现当前数据能命中第一个布隆过滤器,则直接查库。
    dingyaguang117
        47
    dingyaguang117  
       2021-01-18 12:35:49 +08:00 via iPhone
    @woodensail 你说的存在冲突是 正确数据跟正确数据的冲突吧? 查询数据 跟正确数据冲突的情况呢
    woodensail
        48
    woodensail  
       2021-01-18 16:49:07 +08:00
    @dingyaguang117 嗯,你是说考虑业务场景类似于 INSERT ON DUPLICATE KEY 吧。这种倒是更简单了,单层过滤器即可。只要命中了就去查库,以避免假阳性。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1400 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 23:45 · PVG 07:45 · LAX 15:45 · JFK 18:45
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.