设计Twitter时间线和搜索功能

设计Twitter时间线和搜索功能

设计 facebook feed 和 设计 facebook search是相同的问题

第一步:定义用例和约束

定义问题的需求和范围,询问问题去声明用例和约束,讨论假设
ps: 没有一个面试官会展示详细的问题,我们需要定义一些用例和约束

用例:

我们定义问题的范围,只是去处理以下Use Cases

  1. User 发布一个 tweet
  • Service push tweets 给 followers, 发送 push notification 和 email
  1. User 查看这个 user 的 timeline (行为发生来自 user)
  2. User 查看 home 的 timeline (行为发生来自 User follow的人)
  3. User 搜搜关键词
  4. Service 有高可用

问题域外

  1. Service 推送 tweets 到 Twitter Firehose 和其他的 stream
  2. Service 拉取 tweet 基于User的可视化设置
  • 隐藏 @reply 如果这个 User 不能回复被这个人 follow 的人
  • 添加 ‘hide retweets’ 设置
  1. Analystics

约束和假设:

状态假设

  1. 常用
  • Traffic 最终不被分发出去
  • 发布一个 tweet 应该是很快的
  • 发广播给所有的 followers 应该是快的,除非你有数百万的 followers
  • 1000 万活跃用户
  • 5000 万 tweet 每天 或者 150 亿 tweet 每个月
    每条推文的平均传播量为10次
    50 亿个tweet被传播一天
    1500亿tweet被传播每个月
  • 2500 亿个读请求每个月
  • 100 亿搜索每个月
  1. 时间线
  • 展示这个时间线应该很快
  • Twitter是读多写少 (优化为了快速的tweet的Read)
  • Ingesting tweets是写重的
  1. 搜索
  • 搜索应该很快
  • 搜索是读重的

计算使用量:

和面试官说明你是否需要进行粗略使用量估算

  1. 每 tweet 尺寸:
  • tweet_id - 8 bytes
  • user_id - 32 bytes
  • text - 140 bytes
  • media - 10 kb average
  • Total: ~10kb
  1. 每个月有150 TB的新 tweet 内容
  • 10 kb/tweet * 5000 万 tweet / day * 30 天 / 月
  • 三年内会有5.4 PB的新 tweet
  1. 10w read请求 / S
  • 2500 亿读请求每个月 * (400 请求每秒 / 10亿 请求每个月)
  1. 6000 tweets / s
  • 150 亿tweet每个月 * (400 请求每秒 / 10w 请求每个月)
  1. 6w 个 tweet 被广播 / 每秒
  • 1500 亿 tweet 每个月 * (400 请求每秒 / 10 w请求每个月)
  1. 4000 搜索请求每秒
  • 100亿搜索每个月 * (400 请求每秒 / 10 亿请求每个月)

转换规则:
250 万秒每个月
1 request/s = 250 万 request/ 月
40 request/s = 1000 万 request/月
400 request/s = 10 亿 request/月

高视角组件设计

描绘所有重要组件的 high level design

Twitter设计

设计核心组件

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

  1. Client 发送一个 tweet 到 Web Server
  2. Web Server 转发这个 request到 Write API server
  3. Write API 存储 tweet 进 SQL 数据库在用户的时间线
  4. 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 n+2                   tweet n+1                   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/tweet

Response:

{"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
  1. Client 发送一个 home timeline request 到 Web Server
  2. Web Server 转发请求到 Read API server
  3. Read 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_id=123

Response:

{"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
  1. Client 发送一个 user timeline request 到 Web Server
  2. Web Server 转发这个 request 到 Read API server
  3. Read API 从SQL 数据库接收 User Timeline

这个 Rest API应该是和 home timeline相同的,除了所有的 tweets应该才子与 User,而不是User 的 follower

Case04: User searches keywords
  1. Client 发送一个 search request 到 Web Server
  2. Web Server 转发 request 到 Search API server
  3. Search 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?query=hello+world

扩展设计

开始思考这四件事:

  1. 负载测试
  2. 分析系统瓶颈
  3. 定位瓶颈和分析不同方案和好处
  4. 重复

讨论初始化的Design,定位瓶颈的过程是非常重要的。比如:添加 Load Balancer到多Web Server会产生什么问题? CDN 呢?数据库主从架构呢?什么是最优解?

我么将介绍一些组件来完成这个Design并且去定位扩展性问题,内部的load balancer不被展示去减少
杂乱。

  • DNS
  • CDN
  • Load balancer
  • Horizontal scaling
  • Web server (reverse proxy)
  • API server (application layer)
  • Cache
  • Relational database management system (RDBMS)
  • SQL write master-slave failover
  • Master-slave replication
  • Consistency patterns
  • Availability 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 Service
  • Search Cluster 有可能需要保存 tweets 进内存去保证低延迟

我们也想要定位在数据库中的瓶颈。

尽管 Memory Cache 可以减少数据库的负载,仅仅SQL读取副本不足以处理缓存缺失。我们可能需要采用额外的SQL扩展模式。

大量的写入将压倒单个SQL写主从,这也表明需要额外的扩展技术。

  • Federation
  • Sharding
  • Denormalization
  • SQL 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 store
  • Document store
  • Wide column store
  • Graph database
  • SQL vs NoSQL

Caching

  • Where to cache
    • Client caching
    • CDN caching
    • Web server caching
    • Database caching
    • Application caching
  • What to cache
    • Caching at the database query level
    • Caching at the object level
  • When to update the cache
    • Cache-aside
    • Write-through
    • Write-behind (write-back)
    • Refresh ahead

Asynchronism and microservices

  • Message queues
  • Task queues
  • Back pressure
  • Microservices

Communications

  • Discuss tradeoffs:
    • External communication with clients - HTTP APIs following REST
    • Internal 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 up
  • Scaling is an iterative process

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/239751.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

服务器推送数据你还在用 WebSocket么?

当涉及到推送数据时,人们首先会想到 WebSocket。 的确,WebSocket 允许双向通信,可以自然地用于服务器到浏览器的消息推送。 然而,如果只需要单向的消息推送,HTTP 通过服务器发送的事件也有这种功能。 WebSocket 的通信过程如下: 首先,通过 HTTP 切换协议。服务器返回 101 状…

U-Boot学习(4):u-boot.lds链接脚本分析

在之前的文章中有介绍U-Boot的编译流程,但我们知道,不同的存储介质可能会接在不同的接口上,如NOR Flash、EMMC和SDRAM等内存的接口是不同的,而不同的接口对应CPU就会映射到不同的内存中。所以如果我们需要运行U-Boot的话&#xff…

介绍下Redis?Redis有哪些数据类型?

一、Redis介绍 Redis全称(Remote Dictionary Server)本质上是一个Key-Value类型的内存数据库,整个数据库统统加载在内存当中进行操作,定期通过异步操作把数据库数据flush到硬盘上进行保存。因为是纯内存操作,Redis的性…

Matlab深度学习进行波形分割(二)

🔗 运行环境:Matlab 🚩 撰写作者:左手の明天 🥇 精选专栏:《python》 🔥 推荐专栏:《算法研究》 🔐#### 防伪水印——左手の明天 ####🔐 💗 大家…

02.部署LVS-DR群集

技能展示: 了解LVS-DR群集的工作原理 会构建LVS-DR负载均衡群集 2.1 LVS-DR 集群 LVS-DR( Linux Virtual Server Director Server )工作模式,是生产环境中最常用的一种工作模式。 2.1.1.LVS-DR 工作原理 LVS-DR 模式&…

react、Vue打包直接运行index.html不空白方法

react vue 在根目录下创建 vue.config.js 文件,写入 module.exports {publicPath: ./, }

【SpringBoot框架篇】35.kafka环境搭建和收发消息

kafka环境搭建 kafka依赖java环境,如果没有则需要安装jdk yum install java-1.8.0-openjdk* -y1.下载安装kafka kafka3.0版本后默认自带了zookeeper,3.0之前的版本需要单独再安装zookeeper,我使用的最新的3.6.1版本。 cd /usr/local wget https://dlcdn.apache.…

C语言——编译和链接

(图片由AI生成) 0.前言 C语言是最受欢迎的编程语言之一,以其接近硬件的能力和高效性而闻名。理解C语言的编译和链接过程对于深入了解其运行原理至关重要。本文将详细介绍C语言的翻译环境和运行环境,重点关注编译和链接的各个阶段…

蓝桥杯AcWing学习笔记 8-2数论的学习(下)

蓝桥杯 我的AcWing 题目及图片来自蓝桥杯C AB组辅导课 数论(下) 蓝桥杯省赛中考的数论不是很多,这里讲几个蓝桥杯常考的知识点。 约数个数定理 我们如何去求一个数的约数个数呢? N N N分解质因数的结果: N P 1 α…

kubeSphere DevOps部署vue项目

devops部署vue项目 🌔环境说明🌏创建DevOps工程🌏填写流水线信息🌏创建流水线 🌔部署应用所需脚本JenkinsfileDockerfile 🌔脚本一些参数如何设置说明🌏deploy.yaml中的:imagePullSecrets:name属…

部署 LVS-DR 群集

本章内容: -了解LVS-DR群集的工作原理 -会构建LVS-DR负载均衡群集 2.1 LVS-DR 集群 LVS-DR ( Linux Virtual Server Director Server )工作模式,是生产环境中最常用的一 种工作模式。 2.1.1 . LVS-DR 工作原理 …

JVM运行时数据区(下篇)

紧接上篇:JVM运行时数据区(上篇)-CSDN博客 堆 一般Java程序中堆内存是空间最大的一块内存区域。创建出来的对象都存在于堆上。 栈上的局部变量表中,可以存放堆上对象的引用。静态变量也可以存放堆对象的引用,通过静态…

记录Qt和opencv 新环境配置过程

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、Qt是什么?二、Qt的版本三、安装步骤1.下载Qt2.双击安装包.exe开始安装3. 需要登陆才能继续安装,没有的就用邮箱注册账号4.注意安装路…

linux创建文件

创建文件夹: mkdir folder_name其中,folder_name是想要创建的文件夹的名称。 例如,如果想在当前目录下创建一个名为 "my_folder" 的文件夹,可以运行以下命令: mkdir my_folder如果想在特定路径下创建文件…

element-ui el-table表格勾选框条件禁用,及全勾选按钮禁用, 记录

项目场景: 表格的部分内容是可以被勾选的,部分内容是不可以被勾选的 使用的是 “element-plus”: “^2.2.22”, 以上应该都是兼容的 问题描述 要求el-table表格中,部分内容不可以被勾选,全选框在没有可选内容时,是禁…

RK3566RK3568安卓11隐藏状态栏带接口

文章目录 前言一、创建全局变量二、设置应用添加隐藏导航栏按钮三、添加按钮功能四、动态隐藏还有显示功能五、创建系统导航栏广播接口总结 前言 关于Android系统的状态栏,不同的客户有不同的需求: 有些客户需要永久隐藏状态栏,有些客户需要在设置显示中…

Flask框架小程序后端分离开发学习笔记《1》网络知识

Flask框架小程序后端分离开发学习笔记《1》网络知识 Flask是使用python的后端,由于小程序需要后端开发,遂学习一下后端开发。 一、网址组成介绍 协议:http,https (https是加密的http)主机:g.cn zhihu.com之类的网址…

通义灵码 - 免费的阿里云 VS code Jetbrains AI 编码辅助工具

系列文章目录 前言 通义灵码,是阿里云出品的一款基于通义大模型的智能编码辅助工具,提供行级/函数级实时续写、自然语言生成代码、单元测试生成、代码注释生成、代码解释、研发智能问答、异常报错排查等能力,并针对阿里云 SDK/OpenAPI 的使用…

【Java 设计模式】创建型之建造者模式

文章目录 1. 定义2. 应用场景3. 代码实现4. 应用示例结语 在软件开发中,建造者模式是一种创建型设计模式,它将一个复杂对象的构建与其表示分离,使得同样的构建过程可以创建不同的表示。建造者模式通常包括一个指导者(Director&…

如何在 SwiftUI 中实现音频图表

文章目录 前言DataPoint 结构体BarChartView 结构体ContentView 结构体实现协议实现线图总结 前言 在可访问性方面,图表是复杂的事物之一。iOS 15 引入了一项名为“音频图表”的新功能。 下面我们将学习如何通过使用 accessibilityChartDescriptor 视图修饰符为任…