【九章系统设计】新鲜事系统

发表于 | 分类于 | 浏览 次
字数统计: 1,805 | 阅读时长 ≈ 8

系统涉及面试的两种形式及常见问题

设计某某系统

设计微博、滴滴、微信、短网址系统、nosql数据库

找问题

  • 网站挂了怎么办
  • 网站太慢怎么办
  • 流量增长怎么

面试官：请设计Twitter

系统设计问题的4S分析法

  • Scenario场景
    • 需要设计哪些功能，设计的多牛
    • 向面试官提问：features/QPS/DAU(日活跃用户)/inerfaces
  • Servece服务
    • 将大系统拆分成小服务
    • Split/Application/Module
  • Storage存储
    • 数据如何存储与访问
    • Schema(表头字段)/data/sql/nosql/File System
  • Scale升级
    • 解决缺陷，处理可能遇到的问题
    • Sharding/optimize/soecial case

Twitter

Scenario场景-Ask

询问面试官：

  1. 需要设计哪些功能
  2. 需要承受多大的访问量？
    1. 日活跃用户DAU
    2. Twitter:MAU ：313M+ DAU：150M+（一般MAU是DAU的2倍）

Scenario场景-Analyze&predict

  • 根据DAU计算并发用户数：
    • 日活跃*每个用户平均请求次数/一天多少秒 = 150M*60/86400 ~100k
    • 峰值peak = 3*QPS ~300k
    • 快速增长的产品：
      • max peak users in 3 months = peak users*2
  • 读频率Read QPS(Queries per second)
    • 300k
  • 写频率Write QPS
    • 5k

QPS有什么用

  • QPS = 100
    • 用笔记本做web服务器就可以
  • QPS = 1k
    • 用一台好一点的web服务器就差不多
    • 需要考虑Single Point Failure
  • QPS = 1m
    • 需要假设一个1000台web服务器的集群
    • 需要考虑如何Maintanance(某一台挂了怎么办)
  • QPS和web server/database之间的关系
    • 一台web service 承受量是1k QPS
    • 一台SQL Database 承受量是1k QPS
    • 一台 no SQL Database 承受量是10k QPS

Scenario场景-需要设计哪些功能

  • step1:列举需要的功能

    • 注册、登录
    • 用户信息展示、编辑
    • 上传照片、视频
    • 搜索
    • 发送、分享推文
    • 时间轴
    • 关注、取关用户

  • step2:sort按功能优先级排序

    ​

Service服务

将大的系统拆分为小服务

  1. replay重放需求
  2. merge归并需求

storage存储——数据如何存储与访问（最重点占50%）

  • 关系型数据库SQL Database（结构化数据）MySQL
    • 用户信息
  • 非关系型数据库（非结构化数据）MangoDB
    • 推文
    • 社交图谱
  • 文件系统
    • 图片、视频（Media files）

Step1：为每个service选择合适的存储结构

Step2：选好合适的存储结构之后，设计数据表的结果，需要存储哪些字段

新鲜事系统News Feed

  • 什么是新鲜事News Feed?
    • 登录Faebook/Twitter/朋友圈之后看到的信息流
    • 你的所有朋友发的信息的集合
  • 典型新鲜事系统
    • Facebook
    • Twitter
    • 朋友圈
    • RSS Reader（头条）
  • 新鲜事系统的核心因素
    • 关注与被关注
    • 每个人看到的新鲜事是不同的

解决方案

  • Pull模型：

    用merge K sorted arrays的思想
    用户的时间线：		->		整合成		->		feed流
    A：An1,An2,...			↘
    B: Bn1,Bn2,...		  	  →			An1,n2,Bn1,Cn1,Cnw,Bn2.....
    C：Cn1,Cn2,... 			↗
    ...
    • 当用户查看News Feed时，获取其每一个好友的最近100条推文，merge这些推文，按时间排序展示给用户
    • 复杂度分析：
      • News Feed:加入用户关注了N个对象，则时间为N此DB read的时间（读取数据库）+ N路归并的时间（在内存中计算的O(logK)，时间忽略）读取数据库耗时很长
      • Post a tweet:一次DB write（写入数据库）时间

  • Push模型：

    用户的News Feed List：				用户D\E\F发了tweet，推送到其好友的List中
    A：D,E...			↘
    B: F,...		  	  →			An1,n2,Bn1,Cn1,Cnw,Bn2.....
    C：E,F,... 			↗
    ...

    • 为每个用户建立一个List存储池存储其好友的News Feed信息，当用户发送一个tweet之后，将该推文推送到每一个关注了他的用户的News Feed中.用户需要查看News Feed时只需要从他的News Feed中读取最近的100条即可

      关键词：Fanout

    • 复杂度分析

      • News Feed：1次DB read(相比push模型快很多)
      • post a tweet：N个粉丝需要N次DB writes
        • 如果粉丝数量N巨大，写入粉丝News Feed List耗时大
        • 但好处是可以用异步任务在后台执行，无需用户等待

      所有的用户公用一个表格，当一个用户发送推文时，他自己和他的关注着都将看到，所以插入n+1条数经验，owner_id为他自己和他的好友们，然后读取时在数据表中select owner_id为自己的。

      Web Server 到Asynct是通过消息队列发送，比如RabitMQ，拿到任务后，先去好友关系表中拿到发文用户的关注者们，然后把消息加入News Feed Table

      缺陷：

      1. 浪费数据库，但硬盘很便宜，不需要考虑存储数据量大

      2. 如果粉丝数量很大，异步操作需要时间，有些粉丝不能及时看到大V发送的tweet

        ​

Design Twitter

import javax.jws.soap.SOAPBinding;
import java.util.*;
public class DesignTwitter {
    class Twitter {
        HashMap<Integer,User> UsersList;
        int tweetTimeStamp = 0;
        class Tweet{
            int id;
            int userId;
            int timeStamp;
            Tweet(int id,int useId,int timeStamp){
                this.id = id;
                this.userId = useId;
                this.timeStamp = timeStamp;
            }
        }
        class User{
            int uid;
            List<Tweet> tweets = new ArrayList<>();
            List<Integer> followers = new ArrayList<>();//被谁关注
            List<Integer> followees = new ArrayList<>();//关注了谁
            User(int uid){
                this.uid = uid;
            }
        }
        /** Initialize your data structure here. */
        public Twitter() {
            UsersList = new HashMap<>();
        }
        /** Compose a new tweet. */
        public void postTweet(int userId, int tweetId) {
            if(!UsersList.containsKey(userId)){
                User user = new User(userId);
                UsersList.put(userId,user);
            }
            Tweet tweet = new Tweet(tweetId,userId,tweetTimeStamp);
            UsersList.get(userId).tweets.add(tweet);
            tweetTimeStamp++;
        }
        /** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */
        public List<Integer> getNewsFeed(int userId) {
            List<Integer> feeds = new ArrayList<>();
            if(!UsersList.containsKey(userId)){
                User user = new User(userId);
                UsersList.put(userId,user);
                return feeds;
            }
            Comparator<Tweet> cmp = new Comparator<Tweet>(){
                public int compare(Tweet t1,Tweet t2){
                    return t2.timeStamp - t1.timeStamp;
                }
            };
            Queue<Tweet> heap = new PriorityQueue<>(10,cmp);
            //先处理自己的新鲜事
            List<Tweet> ownTweets = UsersList.get(userId).tweets;
            for(int i = ownTweets.size()-1;i >= ownTweets.size() - 10 && i >= 0;i--){
                heap.add(ownTweets.get(i));
            }
            //处理关注的人的新鲜事
            List<Integer> followees = UsersList.get(userId).followees;
            for(Integer followee : followees){
                List<Tweet> tweets = UsersList.get(followee).tweets;
                for(int i = tweets.size()-1;i >= tweets.size() - 10 && i >= 0;i--){
                    heap.add(tweets.get(i));
                }
            }
            int k = 10;
            while (k > 0 && !heap.isEmpty()){
                feeds.add(heap.poll().id);
                k--;
            }
            return feeds;
        }
        /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
        public void follow(int followerId, int followeeId) {
            //如果没有用户，新建用户
            if(!UsersList.containsKey(followeeId)){
                User user = new User(followeeId);
                UsersList.put(followeeId,user);
            }
            if(!UsersList.containsKey(followerId)){
                User user = new User(followerId);
                UsersList.put(followerId,user);
            }
            if(followeeId == followerId || UsersList.get(followerId).followees.contains(followeeId)){return;}
            //更新用户关注和被关注列表
            UsersList.get(followeeId).followers.add(followerId);
            UsersList.get(followerId).followees.add(followeeId);
        }
        /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
        public void unfollow(int followerId, int followeeId) {
            if(followeeId == followerId || !UsersList.containsKey(followeeId) || !UsersList.containsKey(followerId) ||
                    !UsersList.get(followerId).followees.contains(followeeId) || !UsersList.get(followeeId).followers.contains(followerId)){
                return;
            }
            Iterator<Integer> iterator =  UsersList.get(followeeId).followers.iterator();
            while(iterator.hasNext()){
                int i = iterator.next();
                if(i == followerId){
                    iterator.remove();
                }
            }
            Iterator<Integer> iterator2 =  UsersList.get(followerId).followees.iterator();
            while(iterator2.hasNext()){
                int i = iterator2.next();
                if(i == followeeId){
                    iterator2.remove();
                }
            }
        }
    }
    public void test(){
        Twitter obj = new Twitter();
        obj.postTweet(1,5);
        List<Integer> param_2 = obj.getNewsFeed(1);
        obj.follow(1,2);
        obj.postTweet(2,6);
        List<Integer> param_3 = obj.getNewsFeed(1);
        obj.unfollow(1,2);
        List<Integer> param_4 = obj.getNewsFeed(1);
    }
    public static void main(String[] args){
        DesignTwitter test = new DesignTwitter();
        test.test();
    }
}

其实这里有个问题，就是follow unfollow post这些都是用户的操作，应该放在用户类里面的，然后再外部调用。有时间重写一下。