打电话推销好还是做网站推广好,做减肥网站,织梦网站怎么做301跳转,网站制作教程迅雷下载设计Twitter时间线和搜索功能 设计 facebook feed 和 设计 facebook search是相同的问题 第一步#xff1a;定义用例和约束 定义问题的需求和范围#xff0c;询问问题去声明用例和约束#xff0c;讨论假设 ps: 没有一个面试官会展示详细的问题#xff0c;我们需要定义一些用…设计Twitter时间线和搜索功能 设计 facebook feed 和 设计 facebook search是相同的问题 第一步定义用例和约束 定义问题的需求和范围询问问题去声明用例和约束讨论假设 ps: 没有一个面试官会展示详细的问题我们需要定义一些用例和约束 用例
我们定义问题的范围只是去处理以下Use Cases
User 发布一个 tweet
Service push tweets 给 followers, 发送 push notification 和 email
User 查看这个 user 的 timeline (行为发生来自 user)User 查看 home 的 timeline (行为发生来自 User follow的人)User 搜搜关键词Service 有高可用
问题域外
Service 推送 tweets 到 Twitter Firehose 和其他的 streamService 拉取 tweet 基于User的可视化设置
隐藏 reply 如果这个 User 不能回复被这个人 follow 的人添加 ‘hide retweets’ 设置
Analystics
约束和假设
状态假设
常用
Traffic 最终不被分发出去发布一个 tweet 应该是很快的发广播给所有的 followers 应该是快的除非你有数百万的 followers1000 万活跃用户5000 万 tweet 每天 或者 150 亿 tweet 每个月 每条推文的平均传播量为10次 50 亿个tweet被传播一天 1500亿tweet被传播每个月2500 亿个读请求每个月100 亿搜索每个月
时间线
展示这个时间线应该很快Twitter是读多写少 优化为了快速的tweet的ReadIngesting tweets是写重的
搜索
搜索应该很快搜索是读重的
计算使用量 和面试官说明你是否需要进行粗略使用量估算 每 tweet 尺寸
tweet_id - 8 bytesuser_id - 32 bytestext - 140 bytesmedia - 10 kb averageTotal: ~10kb
每个月有150 TB的新 tweet 内容
10 kb/tweet * 5000 万 tweet / day * 30 天 / 月三年内会有5.4 PB的新 tweet
10w read请求 / S
2500 亿读请求每个月 * 400 请求每秒 / 10亿 请求每个月
6000 tweets / s
150 亿tweet每个月 * 400 请求每秒 / 10w 请求每个月
6w 个 tweet 被广播 / 每秒
1500 亿 tweet 每个月 * 400 请求每秒 / 10 w请求每个月
4000 搜索请求每秒
100亿搜索每个月 * 400 请求每秒 / 10 亿请求每个月
转换规则: 250 万秒每个月 1 request/s 250 万 request/ 月 40 request/s 1000 万 request/月 400 request/s 10 亿 request/月
高视角组件设计 描绘所有重要组件的 high level design 设计核心组件
Case01: User post a tweet
我们可以存储用户自己的tweet来填充这个用户时间线我们应该讨论这个用户Case的取舍在SQL和NoSQL之间 传播tweets和构建这个home timeline 是一个笑话传播tweets给所有的follower(6w tweets delivered on fanout per second) 将 过载一个传统的关系型数据库。我们或许想选择一个数据存储速度快的写比如No SQL数据库和内存从内存中序列化的读1MB数据需要250微秒当从SSD需要4X,从硬盘中读需要 80X.
我们可以存储媒体文件比如图片和视频在 Object Store
Client 发送一个 tweet 到 Web ServerWeb Server 转发这个 request到 Write API serverWrite API 存储 tweet 进 SQL 数据库在用户的时间线Write API 连接 Fan Out Service会做下面的事情
使用 User Graph Service去查询这个User的 follower(存储在Cache中)存储tweet进用户的follower的home timeline在内存里面存储tweet进 Search Index Service用来开启fast searching存储 media 进 Object Store使用 notification service去发送push 的notifications 给 follower 使用一个 Queue 去异步发送 notifications
向你的面试官说明多少代码你期望去写
如果Cache是使用Redis我们可以使用原生的Redis List伴随着如下结构 tweet n2 tweet n1 tweet n
| 8 bytes 8 bytes 1 byte | 8 bytes 8 bytes 1 byte | 8 bytes 8 bytes 1 byte |
| tweet_id user_id meta | tweet_id user_id meta | tweet_id user_id meta |新的 tweet 将会被放进 Memory Cache, 将填充这个User 的 home timeline
我们将使用一个 public REST API:
$ curl -X POST --data { user_id: 123, auth_token: ABC123, \status: hello world!, media_ids: ABC987 } \https://twitter.com/api/v1/tweetResponse:
{created_at: Wed Sep 05 00:37:15 0000 2012,status: hello world!,tweet_id: 987,user_id: 123,...
}内部的服务通信我们可以使用 Remote Procedure Calls
Case02: User view the home timeline
Client 发送一个 home timeline request 到 Web ServerWeb Server 转发请求到 Read API serverRead API server 连接 Timeline Service会做下面的事情
得到存储在内存中的timeline数据包含 tweet ids 和 user ids查询 Tweet Info Service 去得到额外的喜喜关于 tweet ids查询 User Info Service去得到额外的信息关于 user ids
REST API:
curl https://twitter.com/api/v1/home_timeline?user_id123Response:
{user_id: 456,tweet_id: 123,status: foo
},
{user_id: 789,tweet_id: 456,status: bar
},
{user_id: 789,tweet_id: 579,status: baz
}Case03: User views the user timeline
Client 发送一个 user timeline request 到 Web ServerWeb Server 转发这个 request 到 Read API serverRead API 从SQL 数据库接收 User Timeline 这个 Rest API应该是和 home timeline相同的除了所有的 tweets应该才子与 User,而不是User 的 follower Case04: User searches keywords
Client 发送一个 search request 到 Web ServerWeb Server 转发 request 到 Search API serverSearch API 和 Search Service通信会做下面的事情
Parses/tokenizes 查询 query决定什么需要被 search 移除 markup 分解 text 进 terms 修复 typos 格式化首字母 转换query去使用bool操作查询 Search Cluster(比如 Lucene) 为了结果 去集群中查询 query 合并排名排序然后返回结果
Rest API:
$ curl https://twitter.com/api/v1/search?queryhelloworld扩展设计
开始思考这四件事
负载测试分析系统瓶颈定位瓶颈和分析不同方案和好处重复 讨论初始化的Design,定位瓶颈的过程是非常重要的。比如添加 Load Balancer到多Web Server会产生什么问题 CDN 呢数据库主从架构呢什么是最优解 我么将介绍一些组件来完成这个Design并且去定位扩展性问题内部的load balancer不被展示去减少 杂乱。
DNSCDNLoad balancerHorizontal scalingWeb server (reverse proxy)API server (application layer)CacheRelational database management system (RDBMS)SQL write master-slave failoverMaster-slave replicationConsistency patternsAvailability patterns
分析设计发现Fanout Service是潜在的瓶颈Twitter 用户的数百万 follower会花费数分钟来完成广播流程。这可能导致推文 replies 出现竞争状况我们可以通过在服务时重新排序堆文件来缓解这种情况。
我们还可以避免将来自高关注度用户的推文散开代替我们可以搜索去找到高关注度用户的 tweet合并搜索结果伴随着用户的 home timeline结果。然后重新排序 tweet 在服务器时间。
额外的优化包括
保持每个 home timeline只有若百个 tweets 在内存中保持只有活跃用户的 home timeline info在内存中 如果一个 user 在过去的30天不活跃的化我们可以从 SQL Database重新构建timeline 查询 User Graph Service 去决定谁是这个 user 正在 following从数据库获取到 tweets 然后添加他们进内存 只存储一个月的tweets进 Tweet Info Service只存储活跃用户进 User Info ServiceSearch Cluster 有可能需要保存 tweets 进内存去保证低延迟
我们也想要定位在数据库中的瓶颈。
尽管 Memory Cache 可以减少数据库的负载仅仅SQL读取副本不足以处理缓存缺失。我们可能需要采用额外的SQL扩展模式。
大量的写入将压倒单个SQL写主从这也表明需要额外的扩展技术。
FederationShardingDenormalizationSQL Tuning
We should also consider moving some data to a NoSQL Database.
Additional talking points Additional topics to dive into, depending on the problem scope and time remaining. NoSQL
Key-value storeDocument storeWide column storeGraph databaseSQL vs NoSQL
Caching
Where to cache Client cachingCDN cachingWeb server cachingDatabase cachingApplication caching What to cache Caching at the database query levelCaching at the object level When to update the cache Cache-asideWrite-throughWrite-behind (write-back)Refresh ahead
Asynchronism and microservices
Message queuesTask queuesBack pressureMicroservices
Communications
Discuss tradeoffs: External communication with clients - HTTP APIs following RESTInternal communications - RPC Service discovery
Security
Refer to the security section.
Latency numbers
See Latency numbers every programmer should know.
Ongoing
Continue benchmarking and monitoring your system to address bottlenecks as they come upScaling is an iterative process
