系统设计案例实战
2022-12-22 15:42:35 0 举报AI智能生成
系统设计案例实战
作者其他创作
大纲/内容
• * 用户登录注册• * 通讯录• 两个用户互相发消息• 群聊
基本功能
其他功能
• 微信• 10.8亿 月活跃用户 • 日发送量 450 亿 • ——数据来自 2019 年微信公开课PRO• QPS： • Average QPS = 45B / 86400 ~ 520k• Peak QPS = 520k * 3 ~ 1.5m• 存储： • 假设每条记录约30bytes的话，大概需要 1.3T 的存储
Scenario 场景
Message Service 负责信息相关的存取
Realtime Service 负责信息的实时推送
Service 服务
数据量很大，不需要修改，一条聊天信息就像一条log一样
• 存储结构：• row_key = thread_id• column_key = created_at 因为要按照时间倒序• value = 其他信息
sharding key （row key）是什么
Message Table
• Thread Table 存储公有的 Thread 信息• 如果使用 SQL 需要同时 index by• thread_id 用于查询某个对话的信息• participant_hash_code 用户查询某些用户之间是否已经有 thread
• 表1：Thread Table• row_key = thread_id• column_key = null• value = 其他的基本信息• 表2：ParticipantHashCode Table• row_key = participant_hash_code• column_key = null• value = thread_id
如果使用 NoSQL 存储 Thread Table 并同时支持按照 thread_id 和participant_hash_code 进行查询，我们需要两张表：
如果使用 NoSQL 该如何存储？
Thread Table
UserThread Table 存储私有的 Thread 信息
存储结构：• row_key = user_id• column_key = updated_at 按照更新时间倒序• value = 其他信息
用什么做 sharding key（row_key）
User Thread Table
在 Thread Table 中增加一个participants_hash_code
该值由所有参与者的user_id排序之后hash得到，即：partcipants_hash_code = any_hashfunc(sorted(participants_user_ids))不直接使用排序之后的 user_ids 是因为如果是群聊的话，会太长如果只需要考虑两人对话的话，可以自定义一个格式：private::user1::user2采用uuid之类的hash方式则不需要考虑hash collision的问题
当用户 A 给用户 B 发消息的时候，可能并不知道他们之间的thread_id 是什么，如何在服务器上查询？
• 用户 A 发送一条消息给 用户 B• 服务器收到消息，查询是否有 A 和 B 的对话记录（Thread），如果没有则创建对应的 Thread• 根据 Thread id 创建 Message• B 每隔 10s 访问一次服务器获取最新的信息（Poll） • B 收到信息
一个可行解的流程
Storage 存储
• A 发送消息到 Web Server• Web Server 创建信息存入数据库之后通知 APNS• APNS 告诉 B 有新消息了• B 去 Web Server 抓取下新的消息（可选） • 如果消息比较短的话，也可以直接通过 APNS 传递• 无需 B 再次访问 Web Server 获取
GCM / APNS 都是依赖于手机操作系统的无法支持 Web 端或者桌面端的信息推送如 Web 微信，Facebook Messenger
无法支持 Web 端
使用手机的推送系统
• 用户A打开App后，问 Web Server 要一个 Push Service 的连接地址• A通过 socket 与push server保持连接 • 用户B发消息给A，消息先被发送到服务器 • 服务器把消息存储之后，告诉 Push Server 让他通知 A• A 收到及时的消息提醒
Socket
每隔10秒钟收一次消息太慢了，聊天体验很差，不实时
假如一个群有500人（1m用户也同样道理）• 如果不做任何优化，需要给这 500 人一个个发消息• 但实际上 500 人里只有很少的一些人在线（比如10人）• 但Message Service仍然会尝试给他们发消息• Message Service (web server) 无法知道用户和Push Server的socket连接是否已经断开• 至于 Push Server 自己才知道• 消息到了Push Server 才发现490个人根本没连上 • Message Service 与 Push Server 之间白浪费490次消息传递
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 模式还能工作即可。
• 解决• 增加一个Channel Service（频道服务） • 为每个聊天的Thread增加一个Channel信息• 对于较大群，在线用户先需要订阅到对应的 Channel 上 • 用户上线时，Web Server (message service) 找到用户所属的频道（群），并通知 Channel Service 完成订阅• Channel就知道哪些频道里有哪些用户还活着• 用户如果断线了，Push Service 会知道用户掉线了，通知 Channel Service 从所属的频道里移除• Message Service 收到用户发的信息之后• 找到对应的channel• 把发消息的请求发送给 Channel Service• 原来发500条消息变成发1条消息• Channel Service 找到当前在线的用户 • 然后发给 Push Service 把消息 Push 出去
如何支持群聊？
如从手机登陆时，查询是否已经有其他手机处于登陆状态 • 如果没有，则创建新的 session• 如果有，将对应的 session 设为 expire 或者删除，并发送 push notification 让已经登录的手机 logout• 如果 Push Notification 失败也没有关系• 该手机会在下次访问任何API的时候发现自己已经logout了并跳转至登入界面
如何限制多台客户端同时登录一个账户？
缺陷1：如果用户的网络不稳定，会导致连接时断时连缺陷2：如果在 Push Service 中使用数据库来存储在线信息，Push Service 的结构会变得复杂，通用性会变差，依赖会增多。
是否可以用 Push Server 中的 socket 连接情况？
使用数据库存储 online status 的信息
使用 Web Server 直接访问数据库的获取该信息
OnlineStatus Table 中存储什么信息？
是 Pull，每隔3-5s pull 一次（heartbeat）
原因：1. Pull 更简单，依赖更少（不依赖于 Push Service），代码量更少2. 在告诉服务器我在线的时候，还可以顺带更新所有好友的在线状况，用于客户端显示a. 更新好友在线状态如果用 Push 的方式来做存在很多问题，比如用户如果掉线了，还需要由 Push Server 通知 Web Server 来更新在线状态，然后再通过 Web Server 通知所有的好友他掉线了。总而言之就是 Pull 更简单，Push 更复杂，对实时性要求不高的时候，用 Pull 更好。
是 Pull 还是 Push?
如何支持用户在线状态显示？
拓展问题1：多机登录
Scale 升级
聊天系统设计
用户可以上传视频 用户可以观看和分享视频 生成缩略图 用户可以点赞、评论
系统的高可用 观看视频的流畅度 视频的实时推荐
功能点
150M * 30 / 86400 秒 = 52083 视频/秒，即每天视频观看数为45亿
根据数据，我们有150M的日活跃用户(DAU)，如果用户平均每天观看30个视频，则每秒视频的观看 数为：
52083 / 500 = 104 视频/秒
根据经验值上传视频数总是小于观看视频数，因此假设每上传一个视频，我们就会观看500部视频， 则每秒视频的上传数为：
104 * 5 = 520 分钟/秒，即每分钟上传视频时长520小时
假设平均每个视频时长为5分钟，则每秒上传的视频时长为
520 * 50 = 26000 MB/s = 26 GB/s
存储空间估算：假设在平均的情况下，一分钟视频需要50MB的存储空间（视频需要以多种格式存 储），则一秒钟内上传的视频所需的总存储量为：
520 * 60 * 166 = 5179200 KB/s = 5 G/s
带宽估算：每秒上传520分钟的视频，并假设每次上传的视频占用的带宽为 166KB/s，那么：
容量评估
用户服务 UserService
在编码方式上传中，在前端我们 只要先获取文件的二进制内容， 然后对其内容进行拆分，最后将 每个切片上传到服务端即可。
在JavaScript中，文件FIle对象 是Blob对象的子类，Blob对象 包含一个重要的方法slice，通 过这个方法，我们就可以对二进 制文件进行拆分。
视频切分
• 视频切分后，在客户端根据哈希算法生成所 有视频切片的 chunk_id • 客户端发起上传请求，将所有 chunk_id 带 到服务端 • 服务端生成 video_id & 保存目录并返回给 客户端 • 客户端开始上传 chunk
当上传完一个 chunk 之后，服务端告诉客户端需 要传下一个 chunk
断点续传
上传服务 UploadService
用户可能上传各种格式的视频，需要转换成 Youtube 兼 容的格式在网页端进行播放。
格式转码
用户根据网络环境的不同，会有不同清晰度视频的需求。
清晰度转码
转码服务 EncodeService
缩略图服务 ThumbService
视频服务 VideoService
视频表 Video Table
视频分片表 Chunk Table
缩略图表 Thumbnail Table
用户表 User Table
用户视频关系表 User Video Table
独立出一个文件系统来存储文件，将文件与 webserver 独立。
如何用 CDN 优化读取
用户视频关系表以用户ID做Sharding
查询用户数据
视频表、Chunk表以视频ID做Sharding
查询视频数据
如何对数据库做 sharding
视频流系统设计
第一阶段：
• Driver deny / accept a request• Driver cancel a matched request• Rider cancel a request• Driver pick up a rider / start a trip• Driver drop off a rider / end a trip
第二阶段：
• Uber Pool• Uber Eat
第三阶段 *
2018年每天有 2M 司机载客
• 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
假设同时在线的司机平均约为 600k（猜的）
假如每条Location都记录：600 k * 86400 / 4 * 100bytes (每条位置记录）~ 1.3 T / 天
假如只记录当前位置信息：600 k * 100 bytes = 60 M
存储估算
设计得多牛
记录车的位置 GeoService
匹配打车请求 DispatchService
Uber 主要干的事情就两件
Trip Table
Location Table
Driver Table
• 首先需要对 geohash 建索引• CREATE INDEX on geohash;• 使用 Like Query • SELECT * FROM location WHERE geohash LIKE` 9q9hv%`;
SQL 数据库
NoSQL - Cassandra
用户发出打车请求，查询给定位置周围的司机
匹配司机成功，用户查询司机所在位置
打车用户的角度
司机汇报自己的位置
• 修改 Trip 状态 • 用户发出请求时就已经在 Trip Table 中创建一次旅程༌并Match上最近的司机• 在Driver Table 中标记自己的状态进入不可用状态
司机接受打车请求
• 在 Trip Table 中修改旅程状态 • 在Driver Table 中标记自己的状态进入可用状态
司机完成接送༌结束一次Trip
司机的角度
NoSQL - Redis
Geohash
如何存储和查询地理位置信息？
可行解 Work Solution
数据怎么查询就怎么拆分查询是按照 4-6位的 geohash那么拆分就可以按照 4位的 geohash 来 sharding
按照前4位 Geohash
Uber 的做法：按城市 Sharding
DB Sharding
Redis Master Slave
Redis server is down
既然一定要用多台机器的话，我们可以用 1000 台 Cassandra / Riak 这样的 NoSQL 数据库，平均每台分摊 300 的 QPS 就不大了这类数据库会帮你更好的处理 Replica 和挂掉之后恢复的问题
让更强大的 NoSQL 数据库来处理
Uber打车系统设计
分布式计算MapReduce
推特搜索系统设计
抓取互联网上的“所有”网页内容信息
并存储下来供索引器(Indexer)建立倒排索引(Inverted Index)
10天之内抓取下 1B 网页 (1k webpages per sec)需要 10T 的存储 (10k per webpage)
爬取目标
解析抓取到的网页，并将新的URL存入到对应域名下面的待抓取 URL 列表中
从队列中获取需要抓取的 URL 并抓取
Web Crawler
(Store crawler tasks
Message Queue
存网页
Distributed File System
Database
获得可以抓取的 Domain 和待抓取的 URL List
从 URL List 中获得 URL(每次1个或者若干个，根据 Robots 协 议而定)，扔进抓取队列
Scheduler
在不同的地区部署 Crawler 系统每个地区只抓取所在地区被分配的 domain 下的网页可以通过 domain 的 whois 信息来确定网站所属地区
很多时候网页会不断更新，爬虫也需要不断的抓取同一个网页有的时候可能网站挂了一小段时间，此时网页正好无法被抓取
增加对每个 URL 的信息记录记录下这个 URL 下一次需要被重新抓取的时间可以通过 Expenential Backoff 的方式计算
• URL 抓取成功以后，默认 1 小时以后重新抓取• 如果 1 小时以后抓取到的网页没有变化，则设为 2 小时以后再次抓取• 2小时以后还是没有变化，则设为 4 小时以后重新抓取，以此类推 • 如果 1 小时以后抓取到的网页发生变化了，则设为 30 分钟以后再次抓取• 30分钟以后又变化了，设为 15 分钟以后重新抓取。• 设置抓取时间的上下边界，如至少 30 天要抓取一次，至多 5 分钟抓取一次
如何处理网页更新
• URL 抓取失效以后，默认 1 小时以后重新抓取• 如果 1 小时以后依然抓不到，则设置为 2 小时 • 其他步骤类似网页更新的情况
如何处理网页失效
如何处理网页的更新和失效？
在中国抓取美国的网页会比较慢
爬虫系统设计
用户输入一段想要搜索的内容的前缀，返回可能匹配的 Top 10 Suggest Queries尽量返回被其他人搜索得较多的 Queries
输入与输出
DAU = 500M假设每天每人搜索 6 次，每次平均输入 10 个字符用户每输入一个字符，都会访问一次 Suggestion API 来获得 Top 10 QueriesAverage QPS = 500M * 6 * 10 / 86400 = 30B / 86400 ~ 340kPeak QPS ~ Average QPS * 3 ~ 1M
推算 QPS
提供 Top 10 Queries 的查询
QueryService
记录用户的 Queries 提供给 QueryService
CollectionService
CollectionService 负责统计每个 Query 的搜索次数
Key-value Storage
并不是每条 Query 都会成为 Top 10会浪费很多存储在记录永远不会成为 Top 10 的 Queries 上
不记录所有的 Queries，以 1/10000 的概率来记录即 if get_random(10000) == 0 则对应的 Query 计数+1否则就直接扔掉因为我们不关心具体的 Query 次数，只需要一个相对的排名该是 Top 10 的还是 Top 10
如何优化 CollectionService
循环遍历每一个 Query 然后打擂台的方式非常慢假设计算资源足够，有什么办法可以优化效率？
优化 Prefix → Top 10 的构建速度
在 frontend 设置一个 delay当用户停止输入超过 200ms 时，才发送请求
用户输入速度很快怎么办
要应对 1M+ 的 QPS我们还需要进一步极尽所能的优化这个系统的响应速度
Backend Cache： 每次更新 prefix -> top 10 的数据时都主动更新 Backend Cache避免更新带来的 Cache miss
Frontend-cache & Prefetch： 即在前端进行缓存Pre-fetch 即预加载一些用户可能搜索的 prefix 和 top 10
如何优化响应速度
每天重新计算一次 Prefix → Top 10 则可能会有一些延迟且一些短期内的热门的搜索应该获得更高的权重
构建一套一样的系统，只是查询的内容是最近 2 小时内的热门搜索这套系统每 2 小时更新一次数据用户的请求需要汇总普通搜索结果和热门搜索结果汇总时可以用一些算法来提高热门搜索的权重（2小时内被搜索的次数肯定会员小于历史被搜索次数）网页搜索结果的展示也有类似的架构
如何获得实时热门 Queries
搜索建议系统设计
数据库索引与事务
具体描述
评论系统设计
日活跃 * 每个用户平均请求次数 / 一天多少秒 = 150M * 60 / 86400~ 100k
峰值 Peak = Average Concurrent User * 3 ~ 300k
MAX peak users in 3 months = Peak users * 2
快速增长的产品 Fast Growing
并发用户 Concurrent User
300k
读频率 Read QPS (Queries Per Second)
5k
写频率 Write QPS
SQL
User Service
SQL/NOSQL
FriendShip Service
NOSQL
Tweet Service
File System
Media Service
图片
在用户查看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的时间
复杂度分析
N次DB Reads非常慢 且发生在用户获得News Feed的请求过程中
getNewsFeed(request)
缺陷
Pull Model
为每个用户建一个List存储他的News Feed信息
关键词：Fanout
用户发一个Tweet之后，将该推文逐个推送到每个用户的News Feed List中
用户需要查看News Feed时，只需要从该News Feed List中读取最新的100条即可
News Feed => 1次DB Read
Post a tweet => N个粉丝，需要N次DB Writes
好处是可以用异步任务在后台执行，无需用户等待
• getNewsFeed(request) • return DB.getNewsFeed(request.user)
异步执行
followers的数 目可能很大
Push Model
Facebook – Pull
Instagram – Push + Pull
Twitter – Pull
朋友圈
Pull VS Push
最慢的部分发生在用户读请求时（需要耗费用户等待时间）
在 DB 访问之前加入Cache
N次DB请求 → N次Cache请求 (N是你关注的好友个数)
Trade off: Cache所有的？Cache最近的1000条？
Cache 每个用户的 Timeline
没有Cache News Feed的用户：归并N个用户最近的100条Tweets，然后取出结果的前100条
有Cache News Feed的用户༚ 归并N个用户的在某个时间戳之后的所有Tweets
Cache 每个用户的 News Feed
解决Pull的缺陷
与Pull模型将News Feed存在内存(Memory)中相比
Push模型将News Feed存在硬盘(Disk)里完全不是个事儿
Disk is cheap
浪费更多的存储空间 Disk
不活跃用户 Inactive Users
Fanout 的过程可能需要几个小时！
Push 的挑战
比如多加几台用于做 Push 任务的机器，Problem Solved!
尝试在现有的模型下做最小的改动来优化
对长期的增长进行估计，并评估是否值得转换整个模型
粉丝数目 followers >> 关注数目 following
• 普通的用户仍然 Push • 将 Lady Gaga 这类的用户，标记为明星用户 • 对于明星用户，不 Push 到用户的 News Feed 中 • 当用户需要的时候，来明星用户的 Timeline 里取，并合并到 News Feed 里
Push 结合 Pull 的优化方案
为 User 增加一个 is_superstar 的属性
一个用户被标记为 superstar 之后，就不能再被取消标记
是不是明星不能在线动态计算，要离线计算
如何定义明星
解决Push的缺陷
• 资源少 • 想偷懒，少写代码 • 实时性要求不高 • 用户发帖比较少 • 双向好友关系，没有明星问题（比如朋友圈）
什么时候用 Push？
• 资源充足 • 实时性要求高 • 用户发帖很多 • 单向好友关系，有明星问题
什么时候用 Pull ?
Pull vs Push
Merge timeline into news feed asynchronously.
Follow 一个用户之后，异步地将他的 Timeline 合并到你的 News Feed 中
Pick out tweets from news feed asynchronously.
Unfollow 一个用户之后，异步地将他发的 Tweets 从你的 News Feed 中移除
因为这个过程一点都不快呀
为什么需要异步 Async？
用户迅速得到反馈，似乎马上就 follow / unfollow 成功了
异步的好处？
Unfollow 之后刷新 News Feed，发现好像他的信息还在
不过最终还是会被删掉的
异步的坏处？
如何实现 follow & unfollow ?
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
当有人取消赞的时候：
想要获得一个 Tweet 的点赞数时，因为 num_of_likes 就存在 tweet 里，故无需额外的 SQL Queries
如何存储 likes?
拓展问题
新鲜事系统
平日每秒 1000 人访问该页面。
秒杀时每秒数10万人访问该页面。
QPS 增加 100 倍以上。
QPS 分析
商品购买和下单流程
服务器、数据库等能承载的 QPS 有限，如数据库一般是单机 1000 QPS。需要根据业务预估并发量。
瞬时大流量高并发
库存是有限的，需要精准地保证，就是卖掉了 N 个商品。不能超卖，当然也不能少卖了。
有限库存，不能超卖
使用脚本模拟用户购买，模拟出十几万个请求去抢购。
黄牛恶意请求
时间到了才能购买，提前一秒都不可以（以商家「京东」「淘宝」的时间为准）。
固定时间开启
一个用户，只能购买 1 个或 N 个。
严格限购
秒杀系统需要解决问题
新建秒杀活动
配置秒杀活动
商家侧（京东自营、淘宝天猫店家）
商品秒杀页面（前端或客户端）
购买
下单
付款
用户侧
需求拆解
秒杀服务 Seckill Service
商品信息和 库存服务 Commodity Info & Stock Service
订单服务 Order Service
支付服务 Payment Service
数据库设计
数据流
使用 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 来判断并扣减库存。
库存预热
因为 Redis 和 MySQL 处理能力的巨大差异。实际下沉到 MySQL 的量还是巨大，MySQL 无法承受。
如果秒杀数量是1万台，或者10万台呢？
可不可以在通过 Redis 扣库存后，到 MySQL 的请求慢一 点？
解决思路
通过消息队列（Message Queue，MQ）进行削峰(Peak Clipping)操作。
解决方案
通过 Redis 扣减库存
子主题
通过消息队列异步地创建订单
秒杀操作 减库存
使用 Redis 提供的集合数据结构，将扣减 Redis 库存的用户 ID 写入。
流程图
Redis 数据校验
如何限购
CDN
前端限流
服务熔断
验证码机制
黑名单IP地址
黑名单用户ID
恶意防刷
限流
秒杀系统与订票系统设计
哪个需求量最大？
注册、登录、查询、用户信息修改
支持 100M DAU
• 100M * 0.1 / 86400 ~ 100 • 0.1 = 平均每个用户每天登录+注册+信息修改 • Peak = 100 * 3 = 300
注册，登录，信息修改 QPS 约
• 100 M * 100 / 86400 ~ 100k• 100 = 平均每个用户每天与查询用户信息相关的操作次数（查看好友，发信息，更新消息主页）• Peak = 100k * 3 = 300 k
查询的QPS 约
• 用户 Login 以后，为他创建一个 session 对象• 并把 session_key 返回给浏览器，让浏览器存储起来 • 浏览器将该值记录在浏览器的 cookie 中 • 用户每次向服务器发送的访问，都会自动带上该网站所有的 cookie • 此时服务器拿到 cookie 中的 session_key，在 Session Table 中检测是否存在，是否过期 • Cookie：HTTP 协议中浏览器和服务器的沟通机制，服务器把一些用于标记用户身份的信息，传递给 浏览器，浏览器每次访问任何网页链接的时候，都会在 HTTP 请求中带上所有的该网站相关的 Cookie 信息。Cookie 可以理解为一个 Client 端的 hash table。
Session 会话
一个 AuthenticationService 负责登录注册
一个 UserService 负责用户信息存储与查询
• 例子：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
Cassandra
Friendship Table适合什么数据库？
大部分的情况，用SQL也好，用NoSQL也好，都是可以的
需要支持 Transaction 的话不能选 NoSQL
你想在什么地方偷懒很大程度决定了选什么数据库 SQL：结构化数据，自由创建索引 NoSQL：分布式，Auto-scale，Replica
一般一个网站会同时用多种数据库系统 不同的表单放在不同的数据库里
SQL 和 NoSQL 的选择标准是什么？
大部分公司选择了 SQL 原因：信任度，Multi-Index
User Table 存在哪儿？
大部分公司选择了 NoSQL 原因：数据结构简单，都是 key-value 的查询/存储需求 NoSQL效率更高
Friendship 存在哪儿？
SQL vs NoSQL
一个 FriendshipService 负责好友关系存储
用户系统特点： 读非常多，写非常少
一个读多写少的系统，一定要使用 Cache 进行优化
任何一个 cache 中的 key 都不要永久有效，设置一个短暂的有效时间，如 7 天 那么即便在极低概率下出现了数据不一致，也就最多不一致 7 天
即，我们允许数据库和缓存有“短时间”内的不一致，但最终会一致。
巧妙利用 cache 的 ttl（time to live / timeout） 机制
Cache
key=user_id
value= set of friend_user_id (粉丝表就是粉丝ID， 关注表就是关注的用户ID)
查看A是否关注了B，使用Redis的SISMEMBER 操作查询A的关注用户里有没有B
Redis
row_key=user_id
cloumn_key=friendship_user_id(粉丝表就是粉丝ID， 关注表就是关注的用户ID)
查看A是否关注了B，在关注表中查询row_key=A， cloumn_key=B的数据是否存在
扩展练习1： NOSQL存储单向好友关系
如果使用不支持Muti-Index的NOSQL存储User， 如何同时支持按emial、username、phone等检索用户
key=user_id value=用户信息
cloumn_key=任何你想放的信息
value=用户信息
User相关的所有数据存储在UserTable中
row_key=key=emial、username、phone等
cloumn_key=任何你想放的数据
value=其他用户信息
其他再同时创建多张表单， 用作index
扩展练习2： NOSQL存储User
获取A的好友列表
获取B的好友列表
求交集
使用缓存储用户的好友列表->两次数据库查询变成两次缓存查询
优化：
列出A和B之间的共同好友
扩展练习3-共同好友
切入点： 大于3度是没有现实意义的，对于超出3度的，直接显示3度+
一度表：
二度表：
提前算好所有的一度关系和二度关系在NQSQL中
一度关系和二度关系并集： set1
对于指定不超过10个需要查询六度关系的用户列表查询他们的一度关系、得到set2(10次query)
在set1和set2求交集，根据交集结果推导10人和我的关系距离
方法
扩展练习4-六度好友关系
用户系统设计
长网站->短网站
http://www.jiuzhang.com=>http://bit.ly/1UIoQB6
根据LongURL生成一个ShortURL
http://bit.ly/1UIoQB6=>http://www.jiuzhang.com
根据 Short URL 还原 Long URL，并跳转
Long Url 和 Short Url 之间必须是一一对应的关系么？
Short Url 长时间没人用需要释放么？
不同的要求设计出来的系统完全不一样！
场景
询问面试官微博日活跃用户： 约100M
• 假设每个用户平均每天发 0.1 条带 URL 的微博• Average Write QPS = 100M * 0.1 / 86400 ~ 100• Peak Write QPS = 100 * 2 = 200
推算产生一条Tiny URL的QPS
• 假设每个用户平均点1个Tiny URL• Average Read QPS = 100M * 1 / 86400 ~ 1k• Peak Read QPS = 2k
推算点击一条Tiny URL的QPS
• 100M * 0.1 ~ 10M 条 • 每一条 URL 长度平均 100 算，一共1G• 1T 的硬盘可以用 3 年
推算每天产生的新的 URL 所占存储
QPS
• 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
API设计
URL Service
如何将 Long Url 转换为一个 6位的 Short Url？
随机一个 6 位的 ShortURL，如果没有被用过，就绑定到该 LongURL
• 优点：实现简单• 缺点：生成短网址的速度随着短网址越来越多变得越来越慢
如果选择用 SQL 型数据库，表结构如下：并且需要对 shortKey 和 longURL 分别建索引（index）。
需要根据 Long 查询 Short，也需要根据 Short 查询 Long。
随机生成ShortURL + 数据库去重
优点：效率高• 缺点：依赖于全局的自增ID
因为需要用到自增ID（Sequential ID），因此只能选择使用 SQL 型数据库。 表单结构如下，shortURL 可以不存储在表单里，因为可以根据 id 来进行换算
进制转换 Base62
• 利用缓存提速（Cache Aside） • 缓存里需要存两类数据：• long to short（生成新 short url 时需要）• short to long（查询 short url 时需要）
优化服务器访问速度• 不同的地区，使用不同的 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 台数据库查询
• 使用 Cache 缓存所有的 Long to Short• 在为一个 Long Url 创建 Short Url 的时候，如果 cache miss 则去直接创建新的 short url 即可
如果一个 Long 可以对应多个 Short
• 两张表单，一张存储 Long to Short，一张存储 Short to Long• 每个映射关系存两份，则可以同时支持 long to short 和 short to long 的查询
如果使用随机生成 Short Url 的算法
• 这里有一个很严重的问题是，多台机器之间如何维护一个全局自增的 ID？ • 一般关系型数据库只支持在一台机器上实现这台机器上全局自增的 ID
• 使用 Hash(long_url) % 62 作为 Sharding key• 并将 Hash(long_url) % 62 直接放到 short url 里 • 如果原来的 short key 是 AB1234 的话，现在的 short key 是 • hash(long_url) % 62 + AB1234• 如果 hash(long_url) % 62 = 0 那就是 0AB1234 • 这样我们就可以同时通过 short_url 和 long_url 得到 Sharding Key• 缺点：数据库的机器数目不能超过 62
基于 base62 的方法下的 Sharding key 策略
如果使用 base62 的进制转换法
如果一个 Long 只能对应一个 Short：
Sharding Key
按数据分片
• 中国的用户访问时，会被DNS分配中国的服务器 • 中国的用户访问的网站一般都是中国的网站• 所以我们可以按照网站的地域信息进行 Sharding• 如何获得网站的地域信息？只需要将用户比较常访问的网站弄一张表就好了• 中国的用户访问美国的网站怎么办？ • 那就让中国的服务器访问美国的数据好了，反正也不会慢多少• 中国访问中国是主流需求，优化系统就是要优化主要的需求
按地域分片
Sharding
短网址系统设计
发券的方式：同步发送 or 异步 发送
发券
谁能领：所有用户 or 指定的用户 领取上限：一个优惠券最多能领取 多少张？ 领取方式：用户主动领取 or 自动 发放被动领取
领券
作用范围：商品、商户、类目 计算方式：是否互斥、是否达到 门槛等
用券
创建优惠券
发送优惠券
商家侧
领取优惠券
使用优惠券
支付
1. 新建规则
. 新建优惠券批次
建券
短信
邮件
我们先考虑用户量很少的情况，如果商家要给所有人发站内信，则先遍历用户表，再按照用户表 中的所有用户依次将站内信插入到 message 表中。这样，如果有100个用户，则群发一条站内信 要执行100个插入操作。
这样发一条站内信VX：，s就tu要dy重32复2其插他入均上为万翻条录数倒据卖。而且这上万条数据的content是一样的，假设一条站内信占100个字节，发一次站内信就要消耗十几MB。因此我们可以将原来的表拆成两个表。
信息表 message Table
信息内容表message_contentTable
系统发站内信的时候，只在message_content插入站内信的主体内容，message里不插入记录
用户用户登录后，首先查询message_content中的那些没有在message中有记录的数据，表示是未读的站内信。在查阅站内信的内容时，再将相关的记录插入到message中。
如果系统的用户量达到上万呢？
站内信
触达系统
优惠券服务 Coupon Service
触达服务 Touch Service
券的分布式事务，使用券的过程会出现的分布式问题分析
1. 运营提供满足条件的用户文件，上传到发券管理后台并选择要发送的 优惠券
2. 管理服务器根据用户ID和券批次ID生成消息，发送到消息中间件中
3. 优惠券服务器消费消息
如何大批量给用户发券
如何防止超发
1. 返回可用券
SELECTbatch_idFROMconpou WHEREuser_id=1001ANDstatus=0;SELECTrule_idFROMcoupon_batch WHEREbatch_id=1111;
2. 选择可用券，并返回结果
如何限制券的使用条件
语法：SISMEMBER KEY VALUE 作用：判断成员元素是否是集合的成员。 实例：SISMEMBER batch_id:1111:user_id 1001
1. 在领券前先查缓存
2. 领券
语法：SADD KEY VALUE1......VALUEN 作用：将一个或多个成员元素加入到集合中，已经存在于集合的成员元素将被忽略。 实例：SADD batch_id:1111:user_id 1001
3. 领券后更新缓存
如何防止用户重复领券
难点
券批次表 coupon_batch Table
'{ 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 // 使用结束时间 }'
规则表 rule Table
优惠券表 coupon Table
表单设计
通知信息表 Notify_msg Table
1.在创建优惠券的时候就将需要提醒 的记录插入提醒表中notify_msg
2.把用户ID+批次ID+通知日期 作为 一个唯一索引，防止同一个批次有重 复的记录通知，保证每天只会被通知 一次
3.建立notify_time，通知时间索引，每 日的通知扫描通过该索引列查询，通过 索引列来提高查询的效率
4.通知完成后该表中的数据变 失去了意义，通过定时任务将 该数据删除
新 增通 知 表
快过期券提醒
batch_id
券批次表
coupon_id
user_id
order_id
优惠券表
数据库层面优化
点击一次后，按钮 短时间内置灰
部分请求直接 跳转到「繁忙页」
后端限流
发券接口限流保护
优惠券系统设计
当访问量越来越大以后，如何让你的系统 Scale？
User Table 放一台数据库
Friendship Table 放一台数据库
Message Table 放一台数据库
纵向拆分 Vertical Sharding
不一致 hash
无论是 SQL 还是 NoSQL 都可以用这个方法进行 Sharding
大部分 NoSQL 都帮你实现好了这个算法，帮你自动 Sharding很多 SQL 数据库也逐渐加入 Auto-scaling 的机制了，也开始帮你做自动的 Sharding
• 将取模的底数从 360 拓展到 2^64• 将 0~2^64-1 看做一个很大的圆环(Ring)• 将数据和机器都通过 hash function 换算 到环上的一个点• 数据取 key / row_key 作为 hash key• 机器取MAC地址，或者机器固定名字如database01，或者固定的 IP 地址• 每个数据放在哪台机器上，取决于在Consistent Hash Ring 上顺时针碰到的下一个机器节点
一致性哈希算法 Consistent Hashing
引入分身的概念（Virtual nodes)• 一个实体机器（Real node) 对应若干虚拟机器（Virtual Node） • 通常是 1000 个 • 分身的KEY可以用实体机器的KEY+后缀的形式• 如 database01-0001• 好处是直接按格式去掉后缀就可以得到实体机器• 用一个数据结构存储这些 virtual nodes• 支持快㏿的查询比某个数大的最小数• 即顺时针碰到的下一个 virtual nodes• 哪种数据结构可以支持？
虚拟节点 Virtual Node
一致性 Hash 算法
横向拆分 Horizontal Sharding
• 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，因此这个做法问题不大
User Table 如何 Sharding
Friendship Table 如何 Sharding
Session Table 如何 Sharding
News Feed / Timeline 按照什么Sharding？
数据拆分 Sharding
• 一般是周期性的，比如每天晚上进行一次备份 • 当数据丢失的时候，通常只能恢复到之前的某个时间点 • Backup 不用作在线的数据服务，不分摊读
Backup
• 是实时的， 在数据写入的时候，就会以复制品的形式存为多份• 当数据丢失的时候，可以马上通过其他的复制品恢复• Replica 用作在线的数据服务，分摊读
Replica
数据复制 Replica
数据库拆分与一致性算法
分布式文件系统GFS
文档协调编辑系统设计
分布式数据库BigTable
系统设计
0 条评论
回复 删除
下一页
