如何设计一个电梯系统？

Clarify

Core Object

Core Object，就是定义几个核心的类。承上启下，成为Use case的依据

步骤：

1. 根据Input和Output线性分析 思考：电梯系统的输入和输出分别是什么呢？
2. 思考各个模块都有什么内容？ 需要注意的+Public,-Private,Protected(能被子类访问)这些属性

Use Case

就是一个个功能。 根据一个个CoreObject，列举每个CoreObject对应有哪些Use case

• ElevatorSystem
  • 处理请求，分发
• Request
• Elevator
  • 处理外部的请求（外面的人想进去，按按钮）
  • 处理内部请求
  • 开门
  • 关门
  • 检查重量
• ElevatorButton
  • 按下去

Class

类图（Class diagram）

• 遍历每一个use case

• 对每个use case更加详细描述在做什么

  • Handle request：就是要把请求分发给某个电梯。那就给ElevatorSystem加一个方法：

    一个小问题，万一没分配成功，例如现在电梯都坏了，怎么办？——使用Exceptions。加一个类：

  • Take external Request：除了电梯系统要handle，某个电梯也需要handle请求。那就给电梯加一个handleExternalRequest

    除此以外，我们还有待停list：

  • Take internal Request：需要让电梯能处理internal的请求。 除此之外，我们还需要判断现在internal的请求是不是合法的。那就再加一个isQuestValid()和两个状态变量：

  • Open gate

    给电梯加一个openGate()方法

  • Close gate

  Check weight

  press button

最终：

大纲

• Design WhatsApp ： 聊天系统
  • Work Solution
  • Real-time Service
  • Online Status: Pull vs Push
• Design Rate Limiter
• Design Datadog ：一种网站的数据统计，类似于google anaysis

这节课之后您可以学会

• 设计聊天系统的核心：Realtime Service
• Pull 与 Push 的进一步比较分析

相关设计题

• Design Facebook Messenger
• Design WeChat

聊天系统

Scenario 场景

设计功能

• 基本功能
  • 登录注册
  • 通讯录
  • 两个用户互相发消息
  • 群聊
  • 用户在线状态
• 其它功能
  • 历史消息
  • 多机登录 multi devices

系统限制

• 活跃
  • 1B 月活跃用户
  • 75% 日活跃 / 月活跃
  • 约750M日活跃用户 ——数据来自 Facebook 官方，截止2016年3月

为了计算方便起见，我们来设计一个100M日活跃的WhatsApp

• QPS：
  • 假设平均一个用户每天发20条信息
  • Average QPS = 100M * 20 / 86400 ~ 20k
  • Peak QPS = 20k * 5 = 100k
• 存储：
  • 假设平均一个用户每天发10条信息
  • 一天需要发 1B，每条记录约30bytes的话，大概需要30G的存储

Service 服务

• Message Service : 负责管理信息
• Real-time Service ：负责实时推送信息给接受者

Storage 存储

最简单方法

既然是聊天软件，自然需要一个message table。那么我们需要在message table里面存什么呢？能想到的就是：

那么如果按照这个表来存储，那么如果要查询A与B之间的对话，则需要：

1
2
3

SELECT * FROM message_table
WHERE from_user_id=A and to_user_id=B OR to_user_id=B and from_user_id=A
ORDER BY created_at DESC;

存在两个问题：

• 效率太低。
• 群聊咋办？gg了

改进——引入thread

thread表示两个的对话！如下图所示，左边是thread。右边是message。

那么thread table里面存什么呢？

看起来没什么问题。但我们漏了一个东西——如何查询我参与了哪些thread呢？

优化

thread table里面加一个owner_id

有几个拥有者，那么thread table就复制几份！——这样虽然比较浪费空间，但是thread里面有些东西是私有的，比如昵称什么的。

问题来了，那么thread table的primary key是什么呢？—— 其实就是owner_id + thread_id的组合呀

流程梳理

• message table，存储每个人发的每条消息，以及对应的thread_id。即[id, thread_id,user_id,content, created_id]
• thread table， 存储每个thread的信息，每个人独享一份数据。即[owner_id,thread_id, participant_ids, is_muted, nickname, created_at, updated_at]
• 查询我的所有thread list——从thead_table里查询给定user_id的所有thread_id即可。因此thread_table用SQL
• 查询我的某个thread的大概信息——从thread_table里查询给定owner_id+thread_id的信息
• 查询我的某个thread的具体消息——从message_table中，根据thread_id查询所有的消息，并且返回.因此message_table用NoSQL
• 查询我与另一个用户是否有一个thread?

即：

Word Solution

用户如何发送消息？

• Client 把消息和接受者信息发送给 server
• Server为每个接受者（包括发送者自己）创建一条 Thread （如果没有的话）
• 创建一条message（with thread_id)

用户如何接受消息？

• 可以每隔10秒钟问服务器要一下最新的 inbox 虽然听起来很笨，但是也是我们先得到这样一个可行解再说
• 如果有新消息就提示用户

Scale 扩展

sharding

• Message 是 NoSQL，自带 Scale 属性
• Thread 按照 user_id 进行 sharding

每隔十秒要inbox?太慢了，优化——Socket

Socket——TCP长连接

Push Service——提高Socket连接服务，可以与Client保持TCP长连接

• 当用户打开APP之后，就连接上Push Service中属于自己的socket
• 有人发消息时，Message Service收到消息，通过Push Service把消息发出去
• 如果一个用户长期不活跃（比如10分钟），就可以断开连接，释放掉网络断开
• 断开连接之后，如何收到消息？
  • 打开APP时主动pull + android GCM/IOS APNS
• Socket连接与HTTP连接的最主要区别；
  • HTTP连接下，只能客户端问服务器要数据
  • Socket连接下，服务器可以主动推送数据给客户端

流程：

什么是big table? —— 分布式数据库

Map Reduce : 对大数据的快速计算！

经典场景：统计一个网页中的单词频率。（lintcode题——word count）

大纲

• 设计一个web爬虫
• 线程安全的生产者-消费者模式
• 搜索建议系统

爬虫

搜索引擎如何爬取网页呢？也就是我们想获取如下所示的表：

那么想要用程序完成这个目标，我们首先要知道一个事实，也就是互联网上的内容其实是互相索引的，也就是就像如下的大网一样：

假设一共有1trillion个网页，而且至少一周更新一次。那么每秒要爬取1.6m网页。每页大概10k，那么些网页存储下来大概需要10p的存储空间。

单线程爬虫

一般来说，爬虫是用BFS进行爬取的。对于单线程的爬虫来说，就是搞一个队列：

生产者-消费者模型

也就是生产者一直往里怼任务，消费者拿任务。中间有一个Buffer(原因是存取速度不一样)。

那么回头看看我们的爬虫，其实URL extractor就是生产者，而Web page loader就是消费者。

但是单线程有一个问题，就是慢的很。解决——多线程爬虫

多线程爬虫

这些线程共享同一个URL队列，那么这个队列就要加锁。（DFS没有办法实现这个多线程，因此用BFS）

需要注意的是，争取共享资源，就要考虑以下三个机制：

• sleep —— 就是随机睡一会，但问题在于无法立马知道资源可以使用了
• 信号量（实现互斥）—— 相当于所有的线程都在等着，然后信号量通知他们能用的时候，就抢着占用资源
• semaphore —— 就像门上挂上五把钥匙一样，能够解决抢占资源的问题

单线程 --> 多线程：

• 线程来回切换(context switch)还是有花费（需要保存线程执行状态，还需要切换二级缓存等）的，因此线程不能太多
• 线程端口数目是有限的（TCP/IP协议中，端口只有2个字节，也就是65536个端口）

因此我们可以改进一下：

分布式爬虫

分布式爬虫虽然解决了线程不能太多的问题，但是又带来了一个问题：URL队列在内存中放不下了（假设1trillion，差不多要40T的内存）！这是不行的。那么我们考虑一下存在硬盘里，也就是数据库里。

最要命的限制是：没有办法控制网页的顺序和优先级啊！

解决：给数据库加入一个优先级的列，再加一个频率的列

每一行是一个任务：

• ID,URL
• state：是否正在运行的状态（即能去重，也能防止重复运算）
• priority：优先级
• available_time：控制抓取频率，也就是这个时刻之后再进行抓取。如果本次有更新，那么就把时间设置地更近一些；如果本次没有更新，那么就把时间设置地更远一些

• webPageStorage : 分布式存储，存储爬取的东西
• 爬虫
• Task table : 就是上面的任务表

总结

场景：多少网页？频率？有多大？

服务：爬虫、Task Service、存储系统

存储：用db存储task，一个超大的BigTable存储web pages

遇到的问题

task table 最终会非常大！1 trillion 个task，而且会越来越大

解决——拆表，加速select

那么拆表就有一个细节需要注意，需要一个scheduler，用来安排去哪里要数据。

网页抓取频率问题

如何控制抓取频率呢？有一个暴力的方法：

• 如果本次抓了有更新，那就把下次抓取的时间提前一半
• 如果本次抓了没更新，就把下次抓取的时间往后移2倍

如何处理死循环问题？

有些网站是互相指向的，比如sina.com。而且所有的URL都是与sina.com差不多的。这样就会使用大量的资源去抓取这种巨型网站，太耗费资源了。对于那些小博客就不公平。

解决办法：单位时间对同一个网站，不要分配过多的计算资源就好啦。

Typeahead

Google Type ahead ——

我们以google Suggesion为例

场景

• 日活跃：500m
• 搜索量：4 x 6 x 500m = 12b （每人搜索6次，输入4个单词 = 使用了typeahead四次）
• QPS : 12b / 86400 = 138k
• Peak QPS = QPS X 2 = 276k

服务

要求：敲下一个字母，就赶紧返回热门词才行

• QuerySerivce : 完成typeahead行为
• DataCollectionService : 收集数据、将热门词数据提供给QueryService

影响QueryService的执行时间的最关键因素就是数据结构，其实用Trie树就够了。这里不做过多的介绍。

DataCollectionService对Trie的更新就是个问题。当然不可以直接更新线上Memory中的索引。解决方式，就是在另一台机器上进行更新，另一台机器上的Trie跟这台机器磁盘上的Trie一样的。那就在另一台机器上先加载Trie树到内存，然后更新，再写入硬盘。再同步过去。

Trie树一台机器的内存存不下咋办？

分机器存哇。

那么怎么分呢？

• 按照字母分？ 会存在严重的不平衡问题，因为有的字母的词超多。
• 分布式存：

存储

常见的排序算法有以下几种：

• 递归性排序
  • 算法-归并排序 ：归并排序的主要思想是分治，也就是先把数组分成两部分，当两部分都有序时，然后再将两部分进行二路归并。需要注意的是归并排序的时间复杂度分析方法，就是画出\(T(n) = 2T(n/2) + cn\) 的递归树，并计算最终时间复杂度。但是要注意的是，归并排序在进行二路归并时，可能会产生额外的空间复杂度。
  • 算法-快速排序 ：快速排序的思路也是分治，但分治之前需要选择一个主元作为基准，将主元放在应该在的位置，并且数组左边比主元小，右边比主元大。这样如果当左边有序和右边有序时，整个数组就有序了。假设主元位置为i，快速排序复杂度为\(T(n) = T(i) + T(n - i - 1) + cn​\) 。由于i的不确定性导致快速排序的最坏情况下时间复杂度为\(T(n) = T(n-1) + T(0) + cn = O(n^2)\) ，而平均情况下是\(T(n) = 2T(\frac{n-1}{2}) +cn = nlogn\)。 快速排序不需要额外的空间。
• 非递归型排序
  • 算法-插入排序 ：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。
  • 算法-选择排序 ：每次从无序区选择一个最小的放大有序区的最后
  • 算法-冒泡排序 ：依次比较相邻的两个数据，如果前面的比后面的大，就将其交换；这样交换一轮之后，整个序列中最大的就“沉”到了最后面的位置；重复上述过程，依次把第二大、第三大…的数字放到后面的位置。
  • 算法-希尔排序 ：分组插入排序
• 非比较排序：非比较排序的时间复杂度可以达到\(O(n)\) 。
  • 算法-计数排序、基数排序、桶排序
    • 计数排序：已知最大值K。利用数组int[K] 统计每个数字的小于等于它的个数，将这个个数作为这个数字的idx
    • 基数排序：分别对数字的个位、十位、...、d位依次进行计数排序
    • 桶排序：将数字分别放入桶里。

因此我们做出如下总结：

红黑树本质上是一种二叉查找树，但它在二叉查找树的基础上额外添加了一个标记（颜色），同时具有一定的规则。这些规则使红黑树保证了一种平衡，插入、删除、查找的最坏时间复杂度都为 O(logn)。

它的统计性能要好于平衡二叉树（AVL树），因此，红黑树在很多地方都有应用。比如在 Java 集合框架中，很多部分(TreeMap, TreeSet 等)都有红黑树的应用，这些集合均提供了很好的性能。

由于 TreeMap 就是由红黑树实现的，因此本文将使用 TreeMap 的相关操作的代码进行分析、论证。

什么是分布式系统

用多台机器解决一台机器不能解决的问题。比如存储不够？QPS太大？

谷歌三剑客

• 分布式文件系统
  • 怎么有效存储数据？
  • NoSQL底层需要一个文件系统
• Map Reduce
  • 怎么快速处理系统？
• Big table = No-SQL Database
  • 怎么连接底层存储和上层数据

本节课内容：

• Master Slave Pattern
• How to check and handle system failure and error
• How to design Distributed File System

XGBoost

XGBoost作为一款经过优化的分布式梯度提升（Gradient Boosting）库，具有高效，灵活和高可移植性的特点。基于梯度提升框架，XGBoost实现了并行方式的决策树提升(Tree Boosting)，从而能够快速准确地解决各种数据科学问题。XGBoost不仅支持各种单机操作系统（如：Windows，Linus和OS X），而且支持集群分布式计算(如：AWS，GCE，Azure和Yarn)和云数据流系统（如：Flink和Spark）。

XGBoost是由华盛顿大学（University of Washington）的陈天奇作为 Distributed (Deep) Machine Learning Community (DMLC) 组员所开发的一个研究项目。在陈天奇与队友一起赢得了Higgs Machine Learning Challenge后，许多的数据科学竞赛队伍使用XGBoost并获得了冠军，促进了该工具在数据科学应用中的广泛使用。

LightGBM

LightGBM（Light Gradient Boosting Machine）同样是一款基于决策树算法的分布式梯度提升框架。为了满足工业界缩短模型计算时间的需求，LightGBM的设计思路主要是两点：1. 减小数据对内存的使用，保证单个机器在不牺牲速度的情况下，尽可能地用上更多的数据；2. 减小通信的代价，提升多机并行时的效率，实现在计算上的线性加速。由此可见，LightGBM的设计初衷就是提供一个快速高效、低内存占用、高准确度、支持并行和大规模数据处理的数据科学工具。

LightGBM是微软旗下的Distributed Machine Learning Toolkit （DMKT）的一个项目，由2014年首届阿里巴巴大数据竞赛获胜者之一柯国霖主持开发。虽然其开源时间才仅仅2个月，但是其快速高效的特点已经在数据科学竞赛中崭露头角。Allstate Claims Severity竞赛中的冠军解决方案里就使用了LightGBM，并对其大嘉赞赏。

出栈顺序问题

今天看到一道出栈顺序的面试题，很心的思路。特来注意一下。

问题定义

一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列?

解题思路

1. 假设进栈序列为\([a,b,c,d]\) . 设\(f(k)\) 表示还剩k个元素时的出栈序列数目（元素内容并不影响数目，例如abc与abd的出栈序列数目是一样的）
2. 如果a第1个出栈，那么只有可能就是a进栈后马上出栈。还剩bcd等待操作。那么就是子问题\(f(3)\)
3. 如果a第2个出栈，那么一定有一个元素先比a进栈，这个元素只可能是b。那么就是子问题\(f(1)\)。 而还剩下cd等待操作，那么cd就是子问题\(f(2)\)
4. 如果a第3个出栈，那么一定有2个元素比a先出栈，这2个元素只可能是bc，就是子问题\(f(2)\) 。而剩下的d就是\(f(1)\)
5. 如果a第4个出栈，那么一定是a进栈后，等到bcd都出栈后再出栈。那么bcd就是\(f(3)\)

结合以上所有情况，即\(f(4) = f(3) + f(2)\times f(1) + f(1) \times f(2) + f(3)\)

为了好看，我们定义\(f(0) = 1\) ，然后推广到n，那么可以得到：

\[f(n) =f(0)\times f(n) + f（1)\times f(n-1) +...+f(k)(n-k)+...+ f(n-1) \times f(1) + f(n) \times f(0)\]

\[ = \sum_{i=0}^{n-1} f(i)f(n-i)\]