V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
UserNameisNull
V2EX  ›  程序员

朋友遇到一个面试题,微信朋友圈怎么设计?

  •  1
     
  •   UserNameisNull · 2021-04-23 17:00:48 +08:00 · 8580 次点击
    这是一个创建于 1308 天前的主题,其中的信息可能已经有所发展或是发生改变。
    假设微信朋友圈的
    读 QPS 100w
    写 QPS 10w
    每个用户最多 400 个朋友,
    发朋友圈和刷朋友圈该怎么设计?
    数据怎么存储?
    求大佬解答。
    第 1 条附言  ·  2021-04-23 22:34:28 +08:00
    抖音技术 leader 。
    写扩散,400 * 10w = 4000w 被否决
    读扩散的话 100w qps,redis 扛不住为由否决。。。。。。。
    除了 redis,还有什么高并发解决方案呢?
    第 2 条附言  ·  2021-04-23 22:35:30 +08:00
    收藏的人好多啊
    30 条回复    2021-04-28 16:45:51 +08:00
    THESDZ
        1
    THESDZ  
       2021-04-23 17:04:23 +08:00
    查阅 feed 流
    brader
        2
    brader  
       2021-04-23 17:09:47 +08:00
    这种面试不就是在空手套白狼?白嫖人家的高并发设计架构
    hejw19970413
        3
    hejw19970413  
       2021-04-23 17:11:13 +08:00
    我感觉 面试想问 数据表和缓存怎么设计,可以参考评论系统。
    ch2
        4
    ch2  
       2021-04-23 17:13:07 +08:00   ❤️ 2
    这种有时间先后顺序的 timeline,就是用 redis 的 list(双向链表)专门为每个人保存一个缓存
    如果关注者数量不多,就采用采用 push 模式,否则采用 pull 模式
    push 模式是一个人发了朋友圈往他朋友们的 timeline 里同步,删除了就全删掉
    点赞也是先临时修改对应的链表结点,再定期落到关系数据库里
    PiersSoCool
        5
    PiersSoCool  
       2021-04-23 17:45:30 +08:00
    空手套白狼倒是也没那么浮夸,这种就算你说了,如果对方没做过,也做不了
    mlcq
        6
    mlcq  
       2021-04-23 17:47:22 +08:00
    这个好像之前有个帖子讨论过,读扩散与写扩散
    p2pCoder
        7
    p2pCoder  
       2021-04-23 17:48:29 +08:00
    feed 流系统设计
    有很多博客系统性讲这个
    zhuzhibin
        8
    zhuzhibin  
       2021-04-23 20:58:13 +08:00 via iPhone
    发发帖子老哥们
    binux
        9
    binux  
       2021-04-24 00:12:03 +08:00 via Android
    读写又不是单机实时的,4000w 怎么了?
    nicebird
        10
    nicebird  
       2021-04-24 00:17:15 +08:00
    才 400 好友,写扩散就行了
    iseki
        12
    iseki  
       2021-04-24 00:38:32 +08:00
    写扩散吧,读扩散更吓人,按他这么算,读扩散不得 400*100w = 40000w ? 每秒 4 亿?

    感觉还是从优化的方向想办法,不是每个人都有 400 朋友,更不是每个人都每秒不停刷刷刷
    securityCoding
        13
    securityCoding  
       2021-04-24 00:55:17 +08:00
    https://www.v2ex.com/t/768603

    并发写:分库分表+mq 异步没什么扛不住的
    并发读:一个集群扛不住那就多集群,做好 uid 分片策略
    cassyfar
        14
    cassyfar  
       2021-04-24 05:58:44 +08:00
    100w qps 为啥 redis 扛不住了?我们组也是 100w 读 qps 。用的 redis 。至少 3 个 9 uptime 。我怀疑面试官水平不行吧,估计都没接触过百万 qps 服务。
    cassyfar
        15
    cassyfar  
       2021-04-24 06:00:13 +08:00
    读扩扇( pull )没啥毛病
    xuanbg
        16
    xuanbg  
       2021-04-24 08:15:22 +08:00
    时间线索引,这量级不单独建一个和内容分离的索引表是不可能的
    ifhwhlwpto
        17
    ifhwhlwpto  
       2021-04-24 10:05:44 +08:00   ❤️ 1
    发朋友圈的时候给每个朋友发一条消息
    刷朋友圈的时候从手机本地读缓存的消息
    把用户的手机用来做缓存,并把问题转化为了如何实现一个高并发的 IM
    hejw19970413
        18
    hejw19970413  
       2021-04-24 10:11:55 +08:00
    你就算是 100w 的请求量,其中有好多都是重复拉取相同的数据吧, 那么就是用 redis + memacache 做多级缓存,利用 kafka 来做消息的队列 ,可以利用 kafka 不同的主题概念,将用户的行为做不同的主题投放,如果一台 Kafka 扛不住这些,那么用不同的 kafka 做不同的主题,起个 job 服务来消费这些消息 ,memacache 可以做内容的缓存,redis 可以做内容消息的索引缓存。根据不同的用户的用户量进行轻重隔离,例如朋友多的用户和朋友少的用户做不同的集群处理。如果有用户很频繁的拉取,可以在你的客户端都拉取限制,然后将这种更新频繁的用户做为热点处理,把缓存的级别提升,做到内存缓存。然后如果用户的拉的内容相同,利用单飞让这些相同的内容,全部命中一个点。 然后你这些服务启动链路追踪 ,调优系统调用的性能。
    samun
        19
    samun  
       2021-04-24 12:28:46 +08:00
    朋友圈内容可以设置查看权限的 这个怎么搞
    leimao
        20
    leimao  
       2021-04-24 12:37:33 +08:00
    完全不知道
    pkupyx
        21
    pkupyx  
       2021-04-24 13:21:09 +08:00
    先得聊聊什么叫 redis 扛不住,你给的方案难道是主备?
    UserNameisNull
        22
    UserNameisNull  
    OP
       2021-04-24 16:34:37 +08:00
    @ifhwhlwpto 和我想法一样
    cholerae
        23
    cholerae  
       2021-04-25 13:29:16 +08:00
    你可以反问一下他,抖音是怎么做的
    ZhaoHuiLiu
        24
    ZhaoHuiLiu  
       2021-04-25 14:59:34 +08:00
    假设微信朋友圈的
    读 QPS 100w
    写 QPS 10w
    每个用户最多 400 个朋友,

    这里读每秒 100 万此,写每秒 10 万次。
    按照要求来算,无论是 SQL 还是 NOSQL 单台机器都完成不了任务。
    只能按照分布式方式,把数据拆散储存。

    创建一个 users 二进制文件,储存所有用户信息。
    创建一个 friends 二进制文件,储存了所有朋友关联信息。
    创建一个 user_friends 二进制文件,储存了关联用户和朋友的信息。

    此时分布式文件系统储存了以下 3 个文件。
    /users.db
    /friends.db
    /user_friends.db

    发朋友圈信息,把数据写到 /message/用户名 /sent.db 这个文件中。
    再从 user_friends.db 读取 400 个朋友的用户名,再分别更新文件 /message/用户名 /received.db 文件。
    这个读取更新操作是自动完成的,当用户读取朋友圈的时候,会根据上次更新时间来判断是否更新,比如上次更新在 1-3 分钟内,根据负载来判断是否更新,负载很高的情况下,并且上次更新少于 3 分钟就不更新。
    如果少于 3 分钟,就立即更新信息。更新方式就是读取 400 个朋友用户名,然后再分别读取 /message/用户名 /sent.db 文件,以当前日期为准读取,比如今天是 2020-1-1 日,就读这一天的,然后聚集 400 个朋友的 2020-1-1 这天的信息,根据时间戳来排序。

    由于上面采用的是分布式文件系统储存方式,读写压力完全根据有多少台服务器来判定,所以理论上不存在读写限制。

    想完成上面操作,推荐用 C++ 或者 Go 语言,上面需求并不复杂。
    ZhaoHuiLiu
        25
    ZhaoHuiLiu  
       2021-04-25 15:02:07 +08:00
    上面只是说了个大概实现,实际可以进行更详细的拆分,不过拆分越细,整体工程就越复杂,我从简设计的。
    ginjedoad
        26
    ginjedoad  
       2021-04-25 21:25:13 +08:00
    这不就是我去腾讯面试的时候的题目吗?
    ansyx
        27
    ansyx  
       2021-04-26 18:45:51 +08:00
    @PiersSoCool 小哥连云港人吗,我有个连云港人在上海的老乡群,可以加一下哈,我的 wechat:ansyxo
    UserNameisNull
        28
    UserNameisNull  
    OP
       2021-04-27 11:21:10 +08:00
    @ansyx 你是怎么知道他是连云港的?
    pkupyx
        29
    pkupyx  
       2021-04-28 03:25:43 +08:00   ❤️ 1
    没做过这么大量级的,瞎想了想

    1.先定义下要持久化的表:朋友圈:moment,用户的跟随者:user_follower,用户跟随了谁:user_followee
    用户:user (无关,外部服务)

    2.moment(user_id,data...)表
    moment 表 10W QPS 写,一天按 10W 秒算,每天新增 100 亿,每年新增 4W 亿。这个量级需要同时做 sharding 和冷热库了。然后热库存最近一年的,剩下全同步给冷库,应该是够用的。
    热库:一年需要存 4W 亿,按单表 1KW 算(其实 SSD 了可以多点),需要 40W 个表,2^19=524288 。按照实体机每台 32 个库,每个库 32 个表分,需要 512 台 mysql 实体机,还可以。
    冷库:复制一个同规模的集群,随时同步超过一年的数据。正常业务的冷查询不会很多,做好冷库的防刷是另外一个话题。这边要计算下磁盘够不够用,按照一条 moment 2KB 来算,冷库设计存 10 年,需要存 40W 亿( 40T ) * 2KB = 80PB,平均每台 160TB,现在密集写的服务器等级的 SSD 主要是 3.84TB 的? girigiri 够。热库除以 10,16TB 一台物理机,肯定够用了。
    sharding 维度:按按发布用户 id 吧,my_moment_ids 的查询直接命中了。

    3.follower(user_id,follower_id) & followee(user_id,followee_id)表
    user_follower 和 user_followee 是等价量级的,可以认为都是热数据。这个增量还比较可控,每人 400 个好友,按 1W 亿规模计算,上面那个方案够用。两个库分别按 user_id 做 sharding,一个对应我关注的用户列表,一个对应关注我的用户列表,写关系时候同步写 2 个表,主要是方便查方便写缓存。

    4.发布&查询朋友圈
    增加缓存:moment 实体,user_follower_ids,user_followee_ids 的缓存,我发的朋友圈的 id 索引 my_moment_ids(user_id->[{my_moment_id,time},...]),重点是我看的朋友圈的 id 关系索引 mix_moment_ids(user_id->[{followee_moment_id,time},...]):
    全量写到 my_moment_idx 缓存,好办。
    读 moment 实体,这块甚至能做到 99%命中缓存。

    维护 mix_moment_ids:
    全量写:如果 mix_moment_ids 要全量写全量存,量级是 moment 表量级的 400 倍,每年要新增 1600 万亿( 1.6P )条数据,按上面的计算,就算放宽 sharding 到单表 1 亿,也需要一个上万台的 mysql 集群,估计 GG 。全量写扩散到 redis 不丢弃,每条关系按 10 字节算,一年 16PB,集群内存估计一个月也存不下,GG 。

    部分写:
    mix_moment_ids 只写前 100 条的 ID,按 100 亿(10G)用户每条 10 字节计算,10TB 数据,redis 集群内存富裕。总之这里策略合适抗住 95%的 mix_moment_idx 查询,剩下 5W 读 qps 需要计算。命中不够就多缓存点,100TB 的 redis 集群还是有的。全量写到 mix_moment_ids 前 100 条的话,写操作先需要读 my_follower_ids,再写到对应人的 mix_moment_ids,集群需要 4KW 的写 QPS,理论上可以做得到。。。吧?不行就只写热点用户。

    剩余 5Wqps 变成了读扩散:这里包含没命中缓存的和冷用户,需要取 user_followee_ids,再取 400 个我关注的人的 my_moment_ids 按时间聚合,这样变成 2KW 读 QPS,95%打到 redis 集群上,剩下 100Wqps 命中 mysql 集群的 moment 表,全热库的话每台 2KQPS,够了。这块应该有很大的做各种 trick 优化的空间。

    纸上谈兵的话就是这样了,欢迎做过这个量级的来指点迷津
    ---
    感谢头条群友逆天之剑半夜讨论启发
    ansyx
        30
    ansyx  
       2021-04-28 16:45:51 +08:00
    @UserNameisNull 我是用 V2EX 搜索时候,看到的一个关于上海还有连云港帖子的留言,具体内容我忘了
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5180 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 05:54 · PVG 13:54 · LAX 21:54 · JFK 00:54
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.