系统设计案例实战

• 存储结构： • row_key = thread_id • column_key = created_at 因为要按照时间倒序 • value = 其他信息

如果使用 NoSQL 存储 Thread Table 并同时支持按照 thread_id 和 participant_hash_code 进行查询，我们需要两张表：

存储结构： • row_key = user_id • column_key = updated_at 按照更新时间倒序 • value = 其他信息

• A 发送消息到 Web Server • Web Server 创建信息存入数据库之后通知 APNS • APNS 告诉 B 有新消息了 • B 去 Web Server 抓取下新的消息（可选） • 如果消息比较短的话，也可以直接通过 APNS 传递 • 无需 B 再次访问 Web Server 获取

无法支持 Web 端

• 用户A打开App后，问 Web Server 要一个 Push Service 的连接地址 • A通过 socket 与push server保持连接 • 用户B发消息给A，消息先被发送到服务器 • 服务器把消息存储之后，告诉 Push Server 让他通知 A • A 收到及时的消息提醒

Q: Channel Service 中的数据是什么结构？
A: key-value 的结构。key 为 channel name，可以是一个字符串比如 “#personal::user_1”。value是一个
set 代表哪些人订阅到了这个 channel 下。
Q: Channel Service 用什么数据存储？
A: 根据上面所提到的 key-value 结构以及 value 需要是一个 set，Redis 是一个很好的选择。
Q: 如何知道一个用户该订阅到哪些 Channels?
A: 首先用户需要订阅自己的 personal channel，如 #personal::user_1，与该用户有关的私聊信息都在这 个 channel 里发送。小于一定人数的群聊可以依然通过 personal channel 推送，超过一定人数的群聊，
可以采用 lazy subscribe 的方式，在用户打开 APP 且群处于比较靠前的位置的时候才订阅，用户没有主
动订阅的群聊靠 Poll 的模式获取最新消息。
Q: 用户关闭 APP 以后还能收到提醒么？
A: 如果真的关闭了 APP 是不行的。所以很多 APP 会常驻后台，保证至少 Poll 模式还能工作即可。

如从手机登陆时，查询是否已经有其他手机处于登陆状态 • 如果没有，则创建新的 session • 如果有，将对应的 session 设为 expire 或者删除，并发送 push notification 让已经登录的手机 logout • 如果 Push Notification 失败也没有关系 • 该手机会在下次访问任何API的时候发现自己已经logout了并跳转至登入界面

是否可以用 Push Server 中的 socket 连接情况？

使用数据库存储 online status 的信息

使用 Web Server 直接访问数据库的获取该信息

OnlineStatus Table 中存储什么信息？

是 Pull 还是 Push?

150M * 30 / 86400 秒 = 52083 视频/秒，即每天视频观看数为45亿

52083 / 500 = 104 视频/秒

104 * 5 = 520 分钟/秒，即每分钟上传视频时长520小时

520 * 50 = 26000 MB/s = 26 GB/s

520 * 60 * 166 = 5179200 KB/s = 5 G/s

在编码方式上传中，在前端我们 只要先获取文件的二进制内容， 然后对其内容进行拆分，最后将 每个切片上传到服务端即可。

在JavaScript中，文件FIle对象 是Blob对象的子类，Blob对象 包含一个重要的方法slice，通 过这个方法，我们就可以对二进 制文件进行拆分。

• 视频切分后，在客户端根据哈希算法生成所 有视频切片的 chunk_id
 • 客户端发起上传请求，将所有 chunk_id 带 到服务端 
• 服务端生成 video_id & 保存目录并返回给 客户端 • 客户端开始上传 chunk

当上传完一个 chunk 之后，服务端告诉客户端需 要传下一个 chunk

用户可能上传各种格式的视频，需要转换成 Youtube 兼 容的格式在网页端进行播放。

用户根据网络环境的不同，会有不同清晰度视频的需求。

用户视频关系表以用户ID做Sharding

视频表、Chunk表以视频ID做Sharding

• Average Driver QPS = 600k / 4 = 150k  • Driver report locations by every 4 seconds • Peak Driver QPS = 150k * 2 = 300 k • Uber 官方自己的说法：2015 新年夜的 Peak QPS 是 170K，当时 Uber 约有 1M 的司机 • Read More: http://bit.ly/1FBSgMK • Rider QPS 可以忽略 • 无需随时汇报位置 • 一定远小于Driver QPS

假如每条Location都记录：600 k * 86400 / 4 * 100bytes (每条位置记录）~ 1.3 T / 天

假如只记录当前位置信息：600 k * 100 bytes = 60 M

SQL 数据库

NoSQL - Cassandra

NoSQL - Redis

按照前4位 Geohash

Uber 的做法：按城市 Sharding

很多时候网页会不断更新，爬虫也需要不断的抓取同一个网页 有的时候可能网站挂了一小段时间，此时网页正好无法被抓取

增加对每个 URL 的信息记录 记录下这个 URL 下一次需要被重新抓取的时间 可以通过 Expenential Backoff 的方式计算

如何处理网页更新

如何处理网页失效

key=query, value=被搜索次数

MAX peak users in 3 months = Peak users * 2

在用户查看News Feed时，获取每个好友的前100条Tweets，合并出前100条News Feed

K路归并算法 Merge K Sorted Arrays

News Feed => 假如有N个关注对象，则为N次DB Reads的时间 + N路归并时间(可忽略)

Post a tweet => 1次DB Write的时间

getNewsFeed(request)

postTweet(request, tweet)

为每个用户建一个List存储他的News Feed信息

用户发一个Tweet之后，将该推文逐个推送到每个用户的News Feed List中

用户需要查看News Feed时，只需要从该News Feed List中读取最新的100条即可

News Feed => 1次DB Read

Post a tweet => N个粉丝，需要N次DB Writes

好处是可以用异步任务在后台执行，无需用户等待

getNewsFeed(request)

postTweet(request, tweet_info)

AsyncService::fanoutTweet(user, tweet)

N次DB请求 → N次Cache请求 (N是你关注的好友个数)

Trade off: Cache所有的？Cache最近的1000条？

没有Cache News Feed的用户：归并N个用户最近的100条Tweets，然后取出结果的前100条

有Cache News Feed的用户༚ 归并N个用户的在某个时间戳之后的所有Tweets

与Pull模型将News Feed存在内存(Memory)中相比

Push模型将News Feed存在硬盘(Disk)里完全不是个事儿

Disk is cheap

粉丝排序 Rank followers by weight (for example, last login time)

Push 的挑战

尝试在现有的模型下做最小的改动来优化

对长期的增长进行估计，并评估是否值得转换整个模型

• 普通的用户仍然 Push 
• 将 Lady Gaga 这类的用户，标记为明星用户 
• 对于明星用户，不 Push 到用户的 News Feed 中 
• 当用户需要的时候，来明星用户的 Timeline 里取，并合并到 News Feed 里

是不是明星不能在线动态计算，要离线计算

• 资源少 
• 想偷懒，少写代码 
• 实时性要求不高 
• 用户发帖比较少 
• 双向好友关系，没有明星问题（比如朋友圈）

• 资源充足 
• 实时性要求高 
• 用户发帖很多 
• 单向好友关系，有明星问题

Merge timeline into news feed asynchronously.

Pick out tweets from news feed asynchronously.

因为这个过程一点都不快呀

用户迅速得到反馈，似乎马上就 follow / unfollow 成功了

Unfollow 之后刷新 News Feed，发现好像他的信息还在

不过最终还是会被删掉的

UPDATE like_table SET num_of_likes = num_of_likes + 1 where tweet_id = xxx

UPDATE like_table SET num_of_likes = num_of_likes - 1 where tweet_id = xxx

服务器、数据库等能承载的 QPS 有限，如数据库一般是单机 1000 QPS。需要根据业务预估并发量。

库存是有限的，需要精准地保证，就是卖掉了 N 个商品。不能超卖，当然也不能少卖了。

使用脚本模拟用户购买，模拟出十几万个请求去抢购。

时间到了才能购买，提前一秒都不可以（以商家「京东」「淘宝」的时间为准）。

一个用户，只能购买 1 个或 N 个。

新建秒杀活动

配置秒杀活动

商品秒杀页面（前端或客户端）

购买

下单

付款

使用 UPDATE 语句自带的行锁 超卖问题解决了，其他问题呢？ 
1. 大量请求都访问 MySQL，导致 MySQL 崩溃。 
SELECT stock FROM `stock_info` WHERE commodity_id = 189 AND seckill_id = 28; 
1. 查询库存余量
 UPDATE `stock_info` SET stock = stock - 1 WHERE commodity_id = 189 AND seckill_id = 28 AND stock > 0; 
2. 扣减库存 对于抢购活动来说，可能几十万人抢 100 台 iPhone，实际大部分请求都是无效的，不需要下沉到 MySQL。

秒杀的本质，就是对库存的抢夺。 
每个秒杀的用户来都去数据库查询库存校验库存，然后扣减库存，导致数据库崩溃。 
MySQL 数据库单点能支撑 1000 QPS，但是 Redis 单点能支撑 10万 QPS，
可以考 虑将库存信息加载到 Redis 中。 直接通过 Redis 来判断并扣减库存。

如果秒杀数量是1万台，或者10万台呢？

解决思路

解决方案

子主题

使用 Redis 提供的集合数据结构，将扣减 Redis 库存的用户 ID 写入。

流程图

黑名单IP地址

黑名单用户ID

• 用户 Login 以后，为他创建一个 session 对象
• 并把 session_key 返回给浏览器，让浏览器存储起来 
• 浏览器将该值记录在浏览器的 cookie 中 
• 用户每次向服务器发送的访问，都会自动带上该网站所有的 cookie 
• 此时服务器拿到 cookie 中的 session_key，在 Session Table 中检测是否存在，是否过期 
• Cookie：HTTP 协议中浏览器和服务器的沟通机制，服务器把一些用于标记用户身份的信息，传递给 浏览器，浏览器每次访问任何网页链接的时候，都会在 HTTP 请求中带上所有的该网站相关的 Cookie 信息。Cookie 可以理解为一个 Client 端的 hash table。

• 例子：Twitter、Instagram、微博 
• 存在 SQL 数据库时 • 查询x所有的关注对象： 
• select * from friendship where from_user_id=x 
• 查询x所有的粉丝： 
• select * from friendship where to_user_id=x

• 例子：微信，Facebook，WhatsApp 
• 方案1：存储为一条数据 
• select * from friendship  where smaller_user_id = x or bigger_user_id=x 
• 问：为什么需要区分 smaller / bigger？ • SQL 可以按照这种方案 • NoSQL 很多不支持 Multi-index 不能使用这种方案

• 方案2：存储为两条数据 
• select * from friendship where from_user_id=x 
• NoSQL 和 SQL 都可以按照这种方案

• Cassandra 是一个三层结构的 NoSQL 数据库 
• http://www.lintcode.com/problem/mini-cassandra/ 
• 第一层：row_key 
• 第二层：column_key 
• 第三层：value 
• Cassandra 的 Key = row_key + column_key 
• 同一个 row_key + column_key 只对应一个 value

Row Key

Column Key

Friendship Table适合什么数据库？

SQL 和 NoSQL 的选择标准是什么？

User Table 存在哪儿？

Friendship 存在哪儿？

任何一个 cache 中的 key 都不要永久有效，设置一个短暂的有效时间，如 7 天 那么即便在极低概率下出现了数据不一致，也就最多不一致 7 天

即，我们允许数据库和缓存有“短时间”内的不一致，但最终会一致。

key=user_id

value= set of friend_user_id (粉丝表就是粉丝ID， 关注表就是关注的用户ID)

查看A是否关注了B，使用Redis的SISMEMBER 操作查询A的关注用户里有没有B

row_key=user_id

cloumn_key=friendship_user_id(粉丝表就是粉丝ID， 关注表就是关注的用户ID)

查看A是否关注了B，在关注表中查询row_key=A， cloumn_key=B的数据是否存在

Redis

Cassandra

Redis

Cassandra

获取A的好友列表

获取B的好友列表

求交集

优化：

提前算好所有的一度关系和二度关系在NQSQL中

一度关系和二度关系并集： set1

对于指定不超过10个需要查询六度关系的用户列表查询他们的一度关系、得到set2(10次query)

在set1和set2求交集，根据交集结果推导10人和我的关系距离

• 假设每个用户平均每天发 0.1 条带 URL 的微博 • Average Write QPS = 100M * 0.1 / 86400 ~ 100 • Peak Write QPS = 100 * 2 = 200

• 假设每个用户平均点1个Tiny URL • Average Read QPS = 100M * 1 / 86400 ~ 1k • Peak Read QPS = 2k

• 100M * 0.1 ~ 10M 条 • 每一条 URL 长度平均 100 算，一共1G • 1T 的硬盘可以用 3 年

• UrlService.encode(long_url) • UrlService.decode(short_url)

• GET /<short_url> • return a Http redirect response • POST /data/shorten/ • Data = {url: http://xxxx } • Return short url

随机一个 6 位的 ShortURL，如果没有被用过，就绑定到该 LongURL

• 优点：实现简单 • 缺点：生成短网址的速度随着短网址越来越多变得越来越慢

需要根据 Long 查询 Short，也需要根据 Short 查询 Long。

• Base62
•   将 6 位的short url看做一个62进制数（0-9, a-z, A-Z)
• 每个short url 对应到一个整数
• 该整数对应数据库表的Primary Key —— Sequential ID
• 6 位可以表示的不同 URL 有多少？
• 5 位 = 625
 = 0.9B = 9 亿 • 6 位 = 626
 = 57 B = 570 亿 • 7 位 = 627
 = 3.5 T = 35000 亿

优点：效率高 • 缺点：依赖于全局的自增ID

需要根据 Long 查询 Short，也需要根据 Short 查询 Long。

优化服务器访问速度 • 不同的地区，使用不同的 Web 服务器 • 通过DNS解析不同地区的用户到不同的服务器

• 优化数据访问速度 • 使用Centralized MySQL+Distributed Memcached • 一个MySQL配多个Memcached，Memcached跨地区分布

如果用 ID / ShortUrl 做Sharding Key • 做 long to short 查询的时候，只能广播给 N 台数据库查询 • 为什么会需要查 long to short？创建的时候避免重复创建 • 如果不需要避免重复创建，则这样可行

如果用 Long Url 做Sharding Key • 做 short to long 查询的时候，只能广播给 N 台数据库查询

Sharding Key

• 中国的用户访问时，会被DNS分配中国的服务器 • 中国的用户访问的网站一般都是中国的网站 • 所以我们可以按照网站的地域信息进行 Sharding • 如何获得网站的地域信息？只需要将用户比较常访问的网站弄一张表就好了 • 中国的用户访问美国的网站怎么办？ • 那就让中国的服务器访问美国的数据好了，反正也不会慢多少 • 中国访问中国是主流需求，优化系统就是要优化主要的需求

1. 新建规则

. 新建优惠券批次

短信

邮件

站内信

1. 运营提供满足条件的用户文件，上传到发券管理后台并选择要发送的 优惠券

2. 管理服务器根据用户ID和券批次ID生成消息，发送到消息中间件中

3. 优惠券服务器消费消息

1. 返回可用券

2. 选择可用券，并返回结果

1. 在领券前先查缓存

2. 领券

3. 领券后更新缓存

'{ threshold: 5.01 // 使用门槛 amount: 5 // 优惠金额 use_range: 3 // 使用范围，0—全场，1—商家，2—类别，3—商品 commodity_id: 10 // 商品 id receive_count: 1 // 每个用户可以领取的数量 is_mutex: true // 是否互斥，true 表示互斥，false 表示不互斥 receive_started_at: 2020-11-1 00:08:00 // 领取开始时间 receive_ended_at: 2020-11-6 00:08:00 // 领取结束时间 use_started_at: 2020-11-1 00:00:00 // 使用开始时间 use_ended_at: 2020-11-11 11:59:59 // 使用结束时间 }'

通知信息表 Notify_msg Table

1.在创建优惠券的时候就将需要提醒 的记录插入提醒表中notify_msg

2.把用户ID+批次ID+通知日期 作为 一个唯一索引，防止同一个批次有重 复的记录通知，保证每天只会被通知 一次

3.建立notify_time，通知时间索引，每 日的通知扫描通过该索引列查询，通过 索引列来提高查询的效率

4.通知完成后该表中的数据变 失去了意义，通过定时任务将 该数据删除

batch_id

coupon_id

user_id

batch_id

order_id

点击一次后，按钮 短时间内置灰

部分请求直接 跳转到「繁忙页」

User Table 放一台数据库

Friendship Table 放一台数据库

Message Table 放一台数据库

不一致 hash

一致性 Hash 算法

• User Table Sharding 之后，多台数据库无法维护一个全局的自增ID怎么办？ • 手动创建一个 UUID 来作为用户的 user_id • 创建用户时还没有用户的 user_id，如何知道该去哪个数据库创建呢？ • Web Server 负责创建用户的 user_id，如用 UUID 来作为 user_id • 创建之后根据 consistent_hash(user_id) 的结果来获得所在的实体数据库信息 • 更进一步的问题：如果 User Table 没有 sharding 之前已经采用了自增ID该怎么办？ • UUID 通常是一个字符串，自增 id 是一个整数，并不兼容 • 单独用一个 UserIdService 负责创建用户的 ID，每次有新用户需要创建时，问这个 Service 要一个新的 ID。这个 Service 是全局共享的，专门负责创建 UserId。负责记录当前 UserId 的最大值是多少了，然后每 次 +1 即可。这个 Service 会负责加锁来保证数据操作的原子性（Atomic）。 • 因为创建用户不是一个很大的 QPS，因此这个做法问题不大

• 一般是周期性的，比如每天晚上进行一次备份 
• 当数据丢失的时候，通常只能恢复到之前的某个时间点 
• Backup 不用作在线的数据服务，不分摊读

• 是实时的， 在数据写入的时候，就会以复制品的形式存为多份 • 当数据丢失的时候，可以马上通过其他的复制品恢复 • Replica 用作在线的数据服务，分摊读