头像

hpstory

专注C++++




离线:2小时前


最近来访(144)
用户头像
卷心菜的卷
用户头像
Fluent
用户头像
一万小时定律
用户头像
Shmilysw
用户头像
Geralmin
用户头像
ACdefly
用户头像
17孟晓龙
用户头像
冬日
用户头像
zhsnddn
用户头像
empty0518
用户头像
xyj1
用户头像
啥也不会啊这
用户头像
记着别人的好
用户头像
歌姬
用户头像
99的手速加上1的运气
用户头像
星光璀璨
用户头像
ZhgDgE
用户头像
Chasing-
用户头像
yzj_
用户头像
zzuts


hpstory
14小时前

目录

0.基础概念

问题:需要设计一个类似Acwing新鲜事的系统

1.明确设计需求

首先列举一些需要的功能,找出核心功能:

  • 登录/注册
  • 用户信息
  • 上传图片
  • 发布新鲜事
  • 评论/点赞/收藏
  • 消息流(News Feed)
  • 时间轴(Timeline)
  • 关注/取关

接下来做一些简单的计算,假设系统每天有1百万活跃用户(问面试官),平均每个用户每天产生60个请求(猜的)。

QPS = 1M * 60 / 86400 ~ 700
峰值 QPS = 700 * 3(猜的) ~ 2k
服务器和数据库各用2~3台就足够了

2.设计服务

针对核心功能,大概可以分成以下几个服务

  • User Service: 登录/注册
  • Message Service:发布新鲜事,消息流,时间轴
  • Friendship Service:关注/取关

3.存储结构设计

什么是新鲜事

  • 登录后你可以看到的消息流
  • 包含你自己/关注的人发的消息集合
  • 每个人看到的都不一样

消息流的实现方式

消息流一般有两种实现方式,Pull和Push

Pull模式

用户查看的时候,获取每个好友的前100条内容,合并取出前100条(一般来说足够了,很少有人会去翻这么多条)。
实现算法可以参考 LeetCode 23. 合并K个升序链表

每次查看消息流,如果用户有n个关注,就会产生n次数据库读取
每次发布新鲜事,会产生1次数据库写入
pull.PNG

缺点:多次读取数据库,整个请求过程会比较慢

Push模式

为每个用户创建一个list来存储他的信息流内容,
用户发一个新鲜事后,把这条新鲜事逐个推送到被关注人的list中,
当用户需要查看的时候,从list中返回前100条。

每次查看信息流,会产生一次数据库读取
每次发布新鲜事,如果用户有n个粉丝,会产生n次数据库写入,
但是写入过程可以通过异步任务在后台执行,用户不用等待
Push2.PNG

缺点:粉丝数量过大处理不及时,磁盘空间占用较多

4.系统优化

一般从两个方面考虑,一个是系统设计缺陷/拓展,另一个是维护方面的问题

系统设计缺陷/拓展

  • Pull/Push模式的优缺点怎么处理
  • 添加一些其他功能,比如:点赞,关注,广告

维护方面

  • 服务器/数据库挂了怎么处理
  • 流量突然暴增

Pull/Push模式

  • Pull模式主要会造成数据库多次读取,响应时间较慢,一般可以通过使用缓存进行优化。
  • Push模式会占用硬盘空间,但相比于Pull模式占用的内存空间,可以不用在意。
  • Push模式对于不活跃的用户是否有必要进行推送,还有就是如果用户的粉丝数量远远大于关注数量,每次全粉丝推送依然会有很大开销,一次异步处理可能需要几个小时。

Pull和Push模式结合优化

  • 对于普通用户,仍然使用Push模式
  • 对于明星用户,不主动Push到用户的信息流
  • 当用户需要的时候,到明星用户的时间轴中取数据,合并到自己的信息流中

Pull和Push模式使用场景

Pull模式适合对实时性有要求,用户会经常发布新鲜事,会有明星用户问题存在的系统。
Push模式则基本相反,适合对实时性要求不高,用户不会经常发布新鲜事,用户之间一般是双向关注,例如朋友圈。

关注/取关功能

当关注了一个用户的时候,异步的将他的时间轴合并到自己的信息流中。
当取关了一个用户的时候,异步的将他发过的新鲜事从自己的信息流中删除。

好处是用户可以立刻获得反馈,操作成功。
缺点是用户取关后刷新,发现内容还在,但是过一段时间后就不见了。




hpstory
16小时前

C# 代码

public class Solution {
    public int RotatedDigits(int n) {
        int result = 0;
        for (int i = 1; i <= n; i++){
            if (Check(i)) result++;
        }

        return result;
    }

    private bool Check(int x){
        bool flag = false;
        while (x > 0){
            int t = x % 10;
            if (t == 3 || t == 4 || t == 7) return false;
            if (t == 2 || t == 5 || t == 6 || t == 9) flag = true;
            x /= 10;
        }

        return flag;
    }
}


活动打卡代码 LeetCode 788. 旋转数字

hpstory
16小时前
public class Solution {
    public int RotatedDigits(int n) {
        int result = 0;
        for (int i = 1; i <= n; i++){
            if (Check(i)) result++;
        }

        return result;
    }

    private bool Check(int x){
        bool flag = false;
        while (x > 0){
            int t = x % 10;
            if (t == 3 || t == 4 || t == 7) return false;
            if (t == 2 || t == 5 || t == 6 || t == 9) flag = true;
            x /= 10;
        }

        return flag;
    }
}



hpstory
2天前

C# 代码

public class MyLinkedList {
    private ListNode dummy;
    private int count;
    public MyLinkedList() {
        this.dummy = new ListNode();
        this.count = 0;
    }

    public int Get(int index) {
        if (index < 0 || index >= count) return -1;
        ListNode current = dummy.next;
        while (index-- > 0){
            current = current.next;
        }

        return current.val;
    }

    public void AddAtHead(int val) {
        ListNode next = dummy.next;
        dummy.next = new ListNode(val, next);
        count++;
    }

    public void AddAtTail(int val) {
        ListNode newNode = new ListNode(val);
        ListNode current = dummy;
        while (current.next != null){
            current = current.next;
        }

        current.next = newNode;
        count++;
    }

    public void AddAtIndex(int index, int val) {
        if (index > count) return;
        if (index < 0) AddAtHead(val);
        ListNode current = dummy;

        while (index-- > 0){
            current = current.next;
        }

        ListNode newNode = new ListNode(val, current.next);
        current.next = newNode;
        count++;
    }

    public void DeleteAtIndex(int index) {
        if (index < 0 || index >= count) return;
        ListNode current = dummy;
        while (index-- > 0){
            current = current.next;
        }

        current.next = current.next.next; 
        count--;
    }
}

public class ListNode{
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null){
        this.val = val;
        this.next = next;
    }
}


活动打卡代码 LeetCode 707. 设计链表

hpstory
2天前
public class MyLinkedList {
    private ListNode dummy;
    private int count;
    public MyLinkedList() {
        this.dummy = new ListNode();
        this.count = 0;
    }

    public int Get(int index) {
        if (index < 0 || index >= count) return -1;
        ListNode current = dummy.next;
        while (index-- > 0){
            current = current.next;
        }

        return current.val;
    }

    public void AddAtHead(int val) {
        ListNode next = dummy.next;
        dummy.next = new ListNode(val, next);
        count++;
    }

    public void AddAtTail(int val) {
        ListNode newNode = new ListNode(val);
        ListNode current = dummy;
        while (current.next != null){
            current = current.next;
        }

        current.next = newNode;
        count++;
    }

    public void AddAtIndex(int index, int val) {
        if (index > count) return;
        if (index < 0) AddAtHead(val);
        ListNode current = dummy;

        while (index-- > 0){
            current = current.next;
        }

        ListNode newNode = new ListNode(val, current.next);
        current.next = newNode;
        count++;
    }

    public void DeleteAtIndex(int index) {
        if (index < 0 || index >= count) return;
        ListNode current = dummy;
        while (index-- > 0){
            current = current.next;
        }

        current.next = current.next.next; 
        count--;
    }
}

public class ListNode{
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null){
        this.val = val;
        this.next = next;
    }
}



hpstory
3天前

网站服务器 WebServer/ApplicationServer

我们经常访问的网站背后都有一台或者若干台机器,提供HTTP/HTTPS服务,这样的机器就是网站服务器。
一台性能较好的服务器大约每秒钟可以处理1000次访问请求.

数据库 Database

  • 顾名思义,就是存储数据的仓库,一般在内网中使用,不会向外网开放访问端口。
    数据库配合服务器实现对数据的增删改查。
  • 一般在系统架构中,数据库和WebServer会放在不同的机器上。

常见数据库

数据库一般分成关系型数据库(Relational database)和非关系型数据库(NoSQL)
常见的有以下几种

  1. MySQL, PostgreSQL, SQLServer, Oracle
    最常见的关系型数据库,按照结构化存储数据,要求数据有较高的稳定性,不会轻易修改,表之间的关系比较复杂。
  2. Memcached, Redis
    Key-Value NoSQL数据库,一般用作缓存系统,内存级别的访问速度,效率高,memcached要快于redis,
    但是redis支持更多的数据结构,并且memcached不支持数据持久化。适合用在存储比较耗时的计算结果,或者频繁查询的数据。
  3. MongoDB
    DocumentBased NoSQL,适合写多读少的数据
  4. Cassandra, HBase
    Column Family Based NoSQL, 也是Key-Value的结构,只不过Key,一般分为row-key和column-key,
    适合放查询请求简单的数据。

文件系统 FileSystem

操作系统的组成部分,一般是目录结构。数据库是基于文件系统存在,
换句话就是数据库系统依赖于文件系统。但是数据库系统提供了更加丰富的数据操作,
文件系统的接口比较单一。适合存储非结构化的数据,如图片,视频等等。

缓存 Cache

在系统设计中一般使用Memcache,也就是内存中的缓存。可以理解成哈希表,key-value结构。
常用的缓存软件是Memcached。由于空间有限,需要淘汰掉一些不常用的数据。
常用的算法有LRU(Least Recently Used),简易版的可以参考 LeetCode 146.LRU缓存

分析方法

  1. 明确设计需求
    • 需要实现哪些功能,找出核心功能
    • 有多大的访问量
      关注几个数值:DAU(Daily Active Users)日活跃用户,MAU(Monthly Active Users)月活跃用户,QPS(Queries Per Second)每秒查询次数。要有对应的计算过程,具体数值并不重要,可以按照自己的想法或者对方的要求进行预估。
      并发用户(Concurrent User):
      计算QPS
      - DAU * 单个用户请求次数 / 一天的秒数
      - 峰值在上面数值的基础上乘以一个系数,这个结果可以作为读频率
      - 写频率一般遵循二八原则,不超过读频率的20%
      计算出QPS之后考虑服务器和数据库的数量
      - 单台服务器QPS=1000
      - 单台SQL数据库QPS=1000
      - 单台NoSQL数据库QPS=10000
      - 单台Memcached QPS=1000000
  2. 把所有需求浏览一遍,添加服务,把同一类问题或者相同逻辑的服务合并到一起
  3. 为每个服务选择适合的存储结构,定义数据表的结构
  4. 考虑系统还有那些缺陷,如何优化系统,是否支持扩展



hpstory
3天前

C# 二维DP 代码

public class Solution {
    public int NumSquares(int n) {
        List<int> nums = new List<int>();
        for (int i = 1; i * i <= n; i++){
            nums.Add(i * i);
        }

        int m = nums.Count;
        int[,] dp = new int[m + 1, n + 1];
        for (int j = 1; j <= n; j++) dp[0, j] = 10000;

        for (int i = 1; i <= m; i++){
            for (int j = 0; j <= n; j++){
                dp[i, j] = dp[i - 1, j];
                if (j >= nums[i - 1]){
                    dp[i, j] = Math.Min(dp[i, j], dp[i, j - nums[i - 1]] + 1);
                }               
            }
        }

        return dp[m, n];
    }
}

C# 一维DP 代码

public class Solution {
    public int NumSquares(int n) {
        List<int> nums = new List<int>();
        for (int i = 1; i * i <= n; i++){
            nums.Add(i * i);
        }

        int m = nums.Count;
        int[] dp = new int[n + 1];
        for (int j = 1; j <= n; j++) dp[j] = 10000;

        for (int i = 1; i <= m; i++){
            for (int j = nums[i - 1]; j <= n; j++){
                dp[j] = Math.Min(dp[j], dp[j - nums[i - 1]] + 1);          
            }
        }

        return dp[n];
    }
}


活动打卡代码 LeetCode 279. 完全平方数

hpstory
3天前
public class Solution {
    public int NumSquares(int n) {
        List<int> nums = new List<int>();
        for (int i = 1; i * i <= n; i++){
            nums.Add(i * i);
        }

        int m = nums.Count;
        int[] dp = new int[n + 1];
        for (int j = 1; j <= n; j++) dp[j] = 10000;

        for (int i = 1; i <= m; i++){
            for (int j = nums[i - 1]; j <= n; j++){
                dp[j] = Math.Min(dp[j], dp[j - nums[i - 1]] + 1);          
            }
        }

        return dp[n];
    }
}



hpstory
4天前

C# 代码

public class Solution {
    private bool[] used;
    public bool CanPartitionKSubsets(int[] nums, int k) {
        int sum = nums.Sum();
        if (sum % k != 0) return false;
        used = new bool[nums.Length];
        int s = sum / k;
        foreach (int num in nums){
            if (num > s) return false;
        }

        Array.Sort(nums);
        Array.Reverse(nums);
        return DFS(0, 0, nums, k, s);
    }

    private bool DFS(int index, int subset, int[] nums, int k, int s){
        // 所有子集已经分完
        if (k == 0) return true;
        if (subset == s) return DFS(0, 0, nums, k - 1, s);
        for (int i = index; i < nums.Length; i++){
            if (!used[i]){                
                if (subset + nums[i] <= s){
                    used[i] = true;
                    if (DFS(i + 1, subset + nums[i], nums, k, s)) return true;
                    used[i] = false;
                }

                // nums[i]已经超了,后面所有相同的数字都无法使用
                while (i < nums.Length - 1 && nums[i] == nums[i + 1]) i++;
            }
        }

        return false;
    }
}



hpstory
4天前
public class Solution {
    private bool[] used;
    public bool CanPartitionKSubsets(int[] nums, int k) {
        int sum = nums.Sum();
        if (sum % k != 0) return false;
        used = new bool[nums.Length];
        int s = sum / k;
        foreach (int num in nums){
            if (num > s) return false;
        }

        Array.Sort(nums);
        Array.Reverse(nums);
        return DFS(0, 0, nums, k, s);
    }

    private bool DFS(int index, int subset, int[] nums, int k, int s){
        // 所有子集已经分完
        if (k == 0) return true;
        if (subset == s) return DFS(0, 0, nums, k - 1, s);
        for (int i = index; i < nums.Length; i++){
            if (!used[i]){                
                if (subset + nums[i] <= s){
                    used[i] = true;
                    if (DFS(i + 1, subset + nums[i], nums, k, s)) return true;
                    used[i] = false;
                }

                // nums[i]已经超了,后面所有相同的数字都无法使用
                while (i < nums.Length - 1 && nums[i] == nums[i + 1]) i++;
            }
        }

        return false;
    }
}