目录

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次数据库写入

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

Push模式

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

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

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

4.系统优化

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

系统设计缺陷/拓展

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

维护方面

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

Pull/Push模式

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

Pull和Push模式结合优化

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

Pull和Push模式使用场景

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

关注/取关功能

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

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

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;
    }
}

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;
    }
}

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;
    }
}

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;
    }
}

网站服务器 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. 考虑系统还有那些缺陷，如何优化系统，是否支持扩展

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];
    }
}

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];
    }
}

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;
    }
}

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;
    }
}