SystemDesign

Posted on Edited on In Views: Views: Word count in article: 5.8k Reading time ≈ 21 mins.

System Design

大家好，这是我从头系统整理如何学习SD的笔记，这是SD的开头。

Tips1: sd面试最重要的是和面试官沟通，找到ta想听的答案

Tips2: DDIA + Alex xu and mocks

如何准备

  1. 先看Alex Xu的书

  2. 然后直接找5个经典的case进行阅读和设计

Usful Tip

常用的几个SD答案：

https://www.1point3acres.com/bbs/thread-1068786-1-1.html

Scott Shi:

https://www.1point3acres.com/bbs/thread-683982-1-1.html

DDIA:

https://www.1point3acres.com/bbs/thread-981203-1-1.html

SD 面试问题

SD是开放式对话， 你应该领导它。

  1. 收集需求，明确问题范围。

    1.1 who is the users ?

    1.2 how do they use ?

    1.3 how many users ?

    1.4 the effect of system?

  2. 创建高级设计

    宏观有哪些大的模块

    模块之间是如何交互

  3. 核心组件设计

    深入某个核心组件的细节

    比如 要求设计一个短的url

    生成和存储完整 url 的哈希

    • MD5和DBase62

    • 哈希冲突

    • SQL 和 NoSQL

    • 数据库架构

    将散列网址转换为完整网址

    • 数据库查找

    API和面向对象设计

  4. 识别bottomnecks

    loadbalancer

    Horizontal scaling

    Cache

    Database sharding

    多个解决方案，权衡利弊，选择好的。

  5. 粗略估算

    快速手动估算

    估算系统的RPS,吞吐量，磁盘空间

SD 面试经验分享

我觉得该贴分析更多是侧重API Design方向的面试

偏product的company确实比较侧重于data model和API design，

但就算这些公司，（取决于面试的level）也会问一些deep dive的问题

比如不同的consistency level的区别，或者各种error case的处理，这些没有点内功是答不好的，做好API design就是个敲门砖，及格分

product track偏重模块API数据的设计

system track就是完全偏重分布式系统设计

设计更多关注product本身

而非底层的infra, 因为这些假定 infra team已经提供了。

有时候nosql还是 relation db都没得选

  1. 重点是 data model design 和 API 结构设计

data model design

以电商系统为例子解释

E-commerce systems need to process user and order information

Data Model Design

User and Order

User

Attributes:

UserId (Primary Key)

UserName

Email

Password

Created At

Relationships

one user === many orders

Order

Attributes:

OrderID (Primary Key)

UserID (Foreign Key from User)

OrderDate

ToalAmount

Status e.g., pending, completed, cancelled)

API Design

User API

Post /users — create new users

Get /users/{userID} get user infor

Put /users/{userID} update user infor

Delete /users/{userID} delete user

Order API

Post /users/{userID}/orders create order for specific users

Get /users/{userID}/orders get the user infor

Get /orders/{orderID} get the order infor

Put /orders/{orderID} update order infor

DELETE /orders/{orderID} delete order

request and response

  1. create new user

    POST /users

Request

1
2
3
4
5
{
  "username": "john_doe",
  "email": "john@example.com",
  "password": "securepassword123"
}

response

1
2
3
4
5
{
  "success": true,
  "userID": "12345",
  "message": "User created successfully"
}

  1. create order for a user

    POST /users/{userID}/orders

request

1
2
3
4
5
6
7
8
9
10
11
{
  "orderDate": "2021-09-15",
  "totalAmount": 299.99,
  "items": [
    {
      "itemID": "998",
      "quantity": 2,
      "price": 149.99
    }
  ]
}

response

1
2
3
4
5
{
  "success": true,
  "orderID": "56789",
  "message": "Order created successfully"
}

  1. get orders of user

    *GET/users/{userID}/orders

1
2
3
4
5
6
7
8
9
10
11
{
  "success": true,
  "orders": [
    {
      "orderID": "56789",
      "orderDate": "2021-09-15",
      "totalAmount": 299.99,
      "status": "completed"
    }
  ]
}

offline workflows

what is offline workflows?

计算环境中进行的Data handling activity活动，这些活动不依赖Real-time data(real time users interactions)

handle Batch processing task

large amount of data / resource-intensive tasks

batch processing

offline workflows 通常处理累积的数据批量，而不是Instant processing of each data. 这种方式适合于需要处理大量数据的情况，例如log analysis、Data Warehouse Synchronization或Report generation.

举例子解释 —> 设计一个product catalog service(产品目录服务)

  1. 这个System有哪些data
  2. 每个object之间是什么关系

搞清楚 data relation model之后

  1. API design

    这些data如何read/write

    每个API的 request/response长什么样子

  2. data processsing 需不需要 offline workflows

  3. 为了scaling需不需要拆分service加入message queue

  4. 如何handle failures

  5. 数据可以暂时存在server local cache里面吗

  6. 给client 的response是sync还是async？

  7. 如何retry

  1. 暂停 加 交流

还有一个是交流很重要 —> 需要pause然后问一下feedback，比如 design 是tradeoff decision

明白面试官打断你的时候对方的concern在哪，自己的设计哪些方面没有考虑？

  1. 写 function requirements/non-function requirements

  2. 画high level design

  3. 别花太多时间计算traffic，storage size，

    除非面试官明确要求你计算，不然可以直接问peak QPS以及数据多大

Basic Concept

延迟和吞吐量

latency 延迟： 执行某些操作或产生某些结果的时间。

假设你在网上购物，当你点击“提交订单”按钮时，系统需要处理你的订单请求，

包括验证支付信息、更新库存、生成订单确认等。延迟就是从你点击“提交订单”按钮到你在屏幕上看到订单确认页面所花费的时间。如果这个时间是200毫秒，那么延迟就是200毫秒。

Throughput 吞吐量： 单位时间内此类操作或结果的数量。—>RPS

在一定时间内系统能够处理的请求数量

the request per second for a System.

CAP

Consistency

每次读取都会收到最近的写入或错误

Avaliability

每个请求都会收到响应，但不保证它包含最新版本的信息

Partition Tolerancy

尽管由于网络故障导致任意分区，系统仍继续运行

CP: 一致性和分区容错

等待来自分区节点的响应可能会导致超时错误。

AP: 可用性和分区容错

响应返回任何节点上可用的最容易获得的数据版本，这可能不是最新的。

Cassandra 是可以调配consisteny 的level

如果调成strong，就是 CP

调成低level，就是AP

除了cassandra以外，CockroachDB(SQL)， Amazon DynamoDB, MongoDB(NonSQL)

都可以调节consistency

zookeeper是偏向于CP的。

严格的CP和AP是没有的，只可以说是倾向于CP还是AP。

Weak consistency —> 弱一致性

写入后，读取可能会或可能不会看到它。采取了尽力而为的方法。

real time case: video talking, Real-time multiplayer

Final Consistency—> 最终一致性

写入后，读取最终会看到它（通常在几毫秒内）。数据是异步复制的。

DNS and email

Strong Consistency —> 强一致性

写入后，读取将看到它。数据同步复制。

RDBMS

Availability model

There gonna be two models to support avaliability: Failover and replication.

Failover

主动–被动

有两台，主服务器 运行 和 处理流量。

被动服务器，在备动状态。

只有当主动服务器坏了，切换到被动服务器运行。

Eg:

假设有一个在线电商网站，正常情况下，所有用户的请求都由主服务器处理。如果主服务器发生故障（例如，硬件故障或软件崩溃），系统会自动将用户请求转移到被动服务器，以确保网站持续可用。在这个过程中，被动服务器从备用状态切换到活动状态，接管所有用户请求。

主动-主动

两台，服务器都在运行，同时处理流量，并且load balance.

但其中一台坏了，另一台会处理所有的流量。

Eg:

假设有两台服务器 A 和 B，平时用户请求分散到两台服务器上共同处理。如果服务器 A 出现故障，服务器 B 会接管所有用户请求，而不会中断服务。

Failover 会存在数据丢失的问题。

在主服务坏掉，有一些request会发送给主服务器，这些数据会丢失的。

Replication

999和9999

99.9%

期间 可接受的停机时间
每年停机时间 8小时45分57秒
每月停机时间 43分49.7秒
每周停机时间 10分4.8秒
每天停机时间 1分26.4秒

如果某个服务承诺提供99.9%的可用性，那么意味着每年可以接受的最大停机时间为8小时45分57秒。

例如，一个在线购物网站在一年中可能因为各种原因（如系统维护、网络故障等）累计停机时间达到了8小时以内，这对于提供99.9%可用性的网站来说是可以接受的。

99.99%

期间 可接受的停机时间
每年停机时间 52分35.7秒
每月停机时间 4分23秒
每周停机时间 1分5秒
每天停机时间 8.6秒

如果某个服务承诺提供99.99%的可用性，那么意味着每年可以接受的最大停机时间为52分35.7秒。

例如，同样是一个在线购物网站，如果它的服务目标是99.99%的可用性，那么在一年中，该网站因为任何原因累计的停机时间不应超过52分钟。这样的网站对停机时间的要求更严格，可能需要更加完善的容错和冗余措施以确保高可用性。

并行和顺序的可用性

sequences

当可用性<100% 的两个组件按顺序排列时，整体可用性会降低：

Availability (Total) = Availability (Foo) * Availability (Bar)

在parallelism下

当可用性<100% 的两个组件并行时，整体可用性会提高：

Availability (Total) = 1 - (1 - Availability (Foo)) * (1 - Availability(Bar))

如果两者 Foo 都 Bar 具有99.9%的可用性，那么它们并行的总可用性将为 99.9999%。

Classic Example

Tiny URL —> Design Pastebin.com (or Bit.ly)

设计一个缩短url的网站

1. Outline use cases and constraints

clarify questions, define use cases and constraints

Questions:

1.1 users

User enters a block of text and gets a randomly generated link

Expiration

default setting: not

but can set timed expirartion’

user enter the generated link and views the contents

user annymous

1.2 service

tracks analytics of pages

deletes expired pastes

high availability

Out of Scope

  • User registers for an account

    • User verifies email

    用户访问 Bit.ly 网站，选择“注册”或“创建账户”。用户需要填写必要的信息，如电子邮件地址、用户名和密码。提交这些信息后，用户的账户将被创建。

  • User logs into a registered account

    • User edits the document

    在注册过程中，Bit.ly 会发送一封验证邮件到用户提供的电子邮件地址。用户需要打开这封邮件并点击其中的验证链接，以确认他们的电子邮件地址是有效的，完成注册过程。

    在注册过程中，Bit.ly 会发送一封验证邮件到用户提供的电子邮件地址。用户需要打开这封邮件并点击其中的验证链接，以确认他们的电子邮件地址是有效的，完成注册过程。

  • User can set visibility

    用户可以设置他们的短链接的可见性选项。例如，他们可以决定这个链接是否公开可见，或者仅对特定的人群可见。这有助于控制谁可以查看和使用这个链接。

  • User can set the shortlink

    “编辑文档”指的是用户在创建或修改一个链接的过程中，用户可以输入一个长链接，并选择“缩短”来生成一个短链接。用户也可以编辑该链接的后缀，使之更符合个人或品牌的风格。

    用户可以自定义短链接，而不是使用自动生成的随机字符串。例如，如果用户是一家公司，他们可能希望链接包含公司名或相关的关键词，以增强品牌识别度和相关性。

Constrains and assumptions

state assumption

Traffic is not evenly distributed

Following a short link should be fast Pastes are text only

Page view analytics do not need to be realtime 10 million users

10 million paste writes per month

100 million paste reads per month

10:1 read to write ratio

Back of Envelop

下面是面试的一个快速估计的例子

our system support 1 trillion urls

One usr space is 1 kb(kill byte)

the total storage will be 1 pb(petabyte)

  1. definately do partitioning

  2. based on the actual use pattern,

    people who use short url, more click than genrate links

size per paste:

Content: 1kb

Example: about 200 words

short url: 7 bye

Eg: 7 characters in total

http://bit.ly/abc123X

expiration_length_in_minutes: 5 bytes

Create_at: 5 bytes

Paste_path: 255bytes

total: 1.27 KB

userage calcumation:

Store:

we will generate 10 million text fragement each month

one month: 1.27kb * 10 000 000 = 1.27 gb

one year: 12.7 gb * 36 = 450 GB

three year: 360 million shortlinks in 3 years

DAU:

Average number of write operations per second: 4

Average read requests per second: 40

2.5 million seconds per month

writen each month: 2.5 million request

read each month: 1000 miliion request

main function

link generation

url evenly distributed

we use hash function to make sure the len of generated url evenly distributed

hash (longURL, userId, craeteTimeStamp)

How many characters do we need in our output of hash function?

assume we gonna use 0-9 and a-z, it will be 36 in total.

If the len is n ----> 36^n

n is the num of chars we gonna generated.

n == 8

we gnna have around 2 trillion combinations

hash collisions

  1. Channing

    have a linkedlist out of each hash key

    image-20240618162159046

  2. probing

    this bucket is already taken, move the another next empty position

in database, we cannot have linkedlist, so we gnnna use probing.

assign the url

2. Create a high level design

image-20240618155504491

3. Design core components

4. Scale the Design

5. Additional talking points

Design Slack

两种面试官disagree

  1. Fundamental disagree

  2. 不是best design

    不是最好的，但是符合当下的

  1. 搞定出business sense

    use case

    MVP(Minimun Active Users) (discuss with the interviewer)

    • Direct Message

    • Channel: Group Chat

    • Multimedia msg

    • Link preview

    Goal:

    • High available

    • High reliable

    • Consistent

    • High performance: real-time

    Bonus features

    • Group Membership

    • Msg Notification

    • Hightlight unread msg

    Non-Goals

    • Authentication/Authorization

    • Mobile/Web Client Side

    首先说分为两个部分： 第一个部分是MVP部分，另一个是Bonus features

    然后 问 有哪些assumption (Goals)

    这个System是为什么服务的—> HA HR C Real-Time

  2. Constraints

    one domain

    这意味着整个应用或服务将在一个单一的域名下运行。

    DAU: 10 million active users

    peak Direct Message: 5 * 10M * 100 / 86400 = 50K Msg/s

    高峰时刻和普通时刻数量的差距倍数 —> 5

    The multiple of the gap between peak time and ordinary times

    86400s ----> 1 day’s seconds

    1个user，每天发100条信息，peak hour 是 normal的5倍

    1 msg: 100 bytes

    10M是日活跃用户数，每个用户在普通时发送100条消息，高峰翻5倍，总消息数除以一天的秒数（86400秒）得到每秒平均50,000条直接消息。

    Throughout: 50k * 100 = 5 MBs

    每秒 50k

    每条消息100 byte

    每秒throughout为5MB

    Storage: 5MB * 86400 * 365 * 10 = 1200 TB

    一天产生100MB，一年需要10TB

    Group chat #

    1000 members in a group

    每个群有1000个成员

    主要集中在两个方面 QPS 和 Data storage

    QPS ==> 50k

    Throughout ==> 5MB

    Database ==> 1200TB / 1.2 PB

    Tips

    B -> KB -> MB -> GB -> TB -->PB 每个间隔之间差1000个

    QPS 超过 1k —> 至少2台 ， 超过1w 一定要多台

    Constraints 通常在下面找

    limitation 基本上都是database read 和 write

    memory utilization read

    disk utilization read

    network bandwidth

  3. Architecture && DataBase

    Account service: manage user account info.

    Friends service: manage user friendship info. May not need in slack

    Group service: manage group membership info

    Media service: process multi-media / link info.

    Message Storage Service: store message.

    Notification Service: notify the users.

    Channel service: master service serve all requests from user.

    Message search service: manage mssage searching index and lookup.

    image-20240619002732847

    Friend service 这里用Mysql

    我读了facebook套的paper，

    所有的graph的问题 可以用 normalized mysql 来解决， 而且没有 fundamental red flag。

    Emoji service 要独立于 redis， 而不是和message service 关联

    emoji 可以经常unpdate，而mesg 不需要经常update。

  4. API design

    4.1打开界面需要查看不同的channel

    4.2也需要发msg

    GetChannels(user_id):

    • Store last viewed channel
    • Store visible channels: recent direct message/membership of the group
    • Show unread msg / last msg preview: denormalized data

    SendMessage(Sender_id, receiver_id, message_type, message, media_id)

    • message_type is one of [direct message, group message]
    • create_timestamp, update_timestamp, expired_time, STATE will be appended by channel service.
    • STATE could be one of [received, sent, viewed,notification_sent, deleted], the multimedia message may need to be processed, therefore need some time between received and sent

    Script API 和 Rest API

    还有一个grp API

    Script API 是基于language-specific脚本的API

    REST API (Representational State Transfer) 利用http标准方法获取和操作资源。

    Script API

    以python script为例子

    get 获取user信息

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    import requests
    def get_user_info(user_id):
        url = f'https://yourapi.com/api/users/{user_id}'
        headers = {'Authorization': 'Bearer your_token_here'}  # 如果API需要认证

        # 发送GET请求
        response = requests.get(url, headers=headers)

        # 检查响应状态码
        if response.status_code == 200:
            print("用户信息获取成功！")
            # 打印响应内容
            print(response.json())
        else:
            print("获取失败：", response.status_code)
            print(response.text)

    # 使用示例
    get_user_info(123)

    post 创建user

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    import requests

    def create_user(name, email):
        url = 'https://yourapi.com/api/users'
        headers = {'Authorization': 'Bearer your_token_here', 'Content-Type': 'application/json'}  # 如果API需要认证
        data = {
            'name': name,
            'email': email
        }

        # 发送POST请求
        response = requests.post(url, json=data, headers=headers)

        # 检查响应状态码
        if response.status_code == 201:
            print("用户创建成功！")
            # 打印响应内容
            print(response.json())
        else:
            print("创建失败：", response.status_code)
            print(response.text)

    # 使用示例
    create_user("Alice Johnson", "alice.johnson@example.com")

    Rest API

    GET

    POST

    PUT

    DELETE

    Eg: Get API

    Request

    请求ID为123的用户信息

    1
    GET /api/users/123

    response

    获得一个包含用户ID、姓名、电子邮件和状态的JSON对象

    1
    2
    3
    4
    5
    6
    {
      "id": 123,
      "name": "John Doe",
      "email": "johndoe@example.com",
      "status": "active"
    }

    Eg: Post API

    创建一个新用户: (包含用户的姓名和电子邮件信息)

    1
    2
    3
    4
    5
    6
    POST /api/users
    Content-Type: application/json
    {
      "name": "Alice Johnson",
      "email": "alice.johnson@example.com"
    }

    response

    可能会返回一个包含新创建用户的详细信息的响应

    Reponse返回新用户分配的唯一ID和其他可能的默认设置或状态信息

    1
    2
    3
    4
    5
    6
    7
    {
      "id": 201,
      "name": "Alice Johnson",
      "email": "alice.johnson@example.com",
      "status": "active",
      "createdAt": "2024-06-01T12:00:00Z"
    }

    一个完成的前后端交互使用REST的例子

    前端

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    // 获取任务
    fetch('/api/tasks')
      .then(response => response.json())
      .then(tasks => console.log(tasks));

    // 创建任务
    fetch('/api/tasks', {
      method: 'POST',
      headers: {
        'Content-Type': 'application/json'
      },
      body: JSON.stringify({ title: 'Buy groceries', due_date: '2024-06-30' })
    })
    .then(response => response.json())
    .then(task => console.log(task));

    // 更新任务
    fetch('/api/tasks/123', {
      method: 'PUT',
      headers: {
        'Content-Type': 'application/json'
      },
      body: JSON.stringify({ title: 'Buy groceries', due_date: '2024-07-05', completed: false })
    })
    .then(response => response.json())
    .then(updatedTask => console.log(updatedTask));

    // 删除任务
    fetch('/api/tasks/123', {
      method: 'DELETE'
    })
    .then(() => console.log('Task deleted'));

  5. DB choice

  6. Data model

How to design a Twitter

Online social networking websites

Post Tweet —> 发布tweet

Timeline —> 展示主页

Follw —> 关注别的用户

面试官考察点

  1. 系统设计能力 work solution

    是否了解 和 设计 常见应用模式

  2. 分析和交流能力 analysis and communication

  3. tradeoff pros and cons

    提出不同的解决方案

    评估不同解决方案的优缺点

    根据需求和条件 做取舍

  4. 知识面深度

    过滤掉只对 系统一知半解的candidate

    eg:

    cache

    cache的存放位置

    cache的存放内容

    更新cache的算法

系统设计主要步骤

Step 1: Clarify the requirements

Step 2: Capacity Estimation

Step 3: System APIs

Step 4: High-level System Design

Step 5: Data Storage

Step 6: Scalability

Step 1: Clarify the requirements

requirements

traffic size（DAU）

没有人期待你设计一个SD在30-45min

设计重点的features就可以

设计features注意两点

  1. 本系统特有的features(Functional Requirement)

  2. 所有系统的common features(Non-Functional Requirement)

  3. Functional Requirement

    特有feature

    1.1 Tweet： 发布和删除tweet

    create tweet

    post tweet

    1.2 timeline/feed: Home 和 user

    Home Timeline

    用户刷新自己的home，会展示 他 follow的人的Tweet

    image-20240619225131031

    User Timeline

    每个用户都有timeline，会展示他自己最近的Tweet

    比如 你follow elon musk，点开home page of elon musk，你就会看到 musk最近所有的tweets.

    image-20240619225207966

    1. 4 follow a user

    2. 5 like a tweet

    3. 6 search tweets

  4. Non-Functional Requirement

所有系统的common features

CAP

Consistency

musk发了一条tweet，我follow了他，但是第一时间没有出来，我refresh了一下之后，才出来。

就是enventual consistency。

Availability

each request都可以收到 non-error response,而不是return error or empty page.

系统是scalable—> System接收到很多traffic时候，也可以返回response。

Partition tolerance

System有几个disk坏掉了，也不影响System 运行。

Step 2: Capacity Estimation

这里要跟面试官沟通得到parameters

DAU: 200M

How many tweet we gnna have per day: 100 M

每天有多少tweet产生

Timeline:

each user visit home timeline 5 times

each user visit other user timeline 3 times

ceach timeline/pages has 20 tweets

Tweet

each tweet has size 280(140 characters) bytes, metadata 30 bytes

Metadata: tweet public time and location

per photo: 200 KB, 20% tweet has images

per video: 2MB, 10% tweet has video, 30% video will be watched(影响stream video的估算)

Storage Evaluation

write size daily:

Text:

100M * (280 + 30) = 31000 MB = 31 GB

Image:

100M * 0.2 * 200KB = 20 * 200GB = 4TB

Video

100M * 0.1 * 2MB = 10M * 2M = 20 TB

Total

24TB

Bandwidth estimate

Daily Read Tweets Volume:

200M * (5 + 3) * 20 = 200M * 8 * 20 = 4000M * 8 = 32 GB

每个user 访问home page 5次，user page 3次

每个page 有 20个 tweet

Daily Read Bandwidth

Text: 32GB * 280/86400 = 9000 / 90000 = 0.1 GB = 100 MB/s

Image: 32GB * 200KB * 0.2/86400= 32GB * 40KB / 1000 00 = 32GB * 4B / 10 = 120 GB /10 = 12 GB/s

Video: 32GB * 0.1 * 0.3 * 2MB/86400 = 1.8G * M/1000 00 = 18 GB/s

Total 30GB/s

bandwidth的估算 可以帮助我们找到System的bottomneck----> how to scale system

Step 3: System APIs

定义SD的API来cover SD的requirements

  1. 发布tweet

    postTweet(userToken, string tweet)

  2. 删除tweet

    deleteTweet(userToken, string tweetId)

  3. LikeOrUnlike

    likeOrUnlikeTweet(userToken, string tweetId, bool like)

  4. Timeline

    4.1 readHomeTimeLine(userToken, int pageSize, opt string pageToken)

    pageToken是optional ----> 当前读到tweet的位置

    pageSize重要，因为不同user使用不同设备，应该返回不同条的tweets

    4.2 readUserTimeLine(userToken, int pageSize, opt string pageToken, int userId)

    int userld to specify the user

Step 4: High-level System Design

  1. Post Tweets —> 用户想发布一条tweet

Loadbalancer: divers user requests and distribute them to relatively idle servers.

Tweet Writer: 是一组服务器，处理tweet的发布，把用户发布的内容写到后台数据库。

image-20240619234646207

  1. UserTime

    用户点击user，访问其主页

    请求到达 loadbalancer

    loadbalancer 把 request发送到 对应的服务器

    timeline service去DB 获取 elon musk的最近的tweet，然后返回给用户

    这里有个bottomneck是直接去DB读，速度慢

    为了solve 这个 latency，采用cache —> 把user最近的tweet写入到cache里面

    timeline直接从cache读，获取

    当musk发布新的tweet的时候，除了写入DB，也写入Cache。

    image-20240619234938960

  2. Home TimeLine

    用来展示用户follow的人的最近tweet动态。

    image-20240619235515287

TimeLine Service 从DB获取这个user follow的人

然后再去cache里获取这些人最近的tweets —> merge all of them into a List

return the list to our users

因为上面获取 该用户follow的人需要读取DB，消耗时间

在cache中，存好要展示给每个用户的timeline

这样 timeline service 就可以通过 query cache直接获取 homeTimeLine返还给user

我们如何存储数据到cache中呢，当用户在post tweet的时候，我们除了直接写入到DB，还需要找到该用户的fans, 拿到他们在cache中的timeline。

也就是说 马斯克发了一个tweet，根据他的followers，将他们的timeline跟新到cache中

Hometimeline的两种更新方法

方法1： pull mode

获取user timeline的时候，从DB中读取user的idols的信息, 获取他们的latest tweet，merge list —> return it.

好处：write的时候快。O（1）

坏处：read的时候比较慢。O（n）

方法2：push mode

在cache里maintain每个用户的timeline

当用户发表tweet时候，将其更新到其followers的 cache中的 timelines —> fan out on write

好处： read 快

坏处：write的时候，比较慢。

但是使用eventual consistency 更新，每个followers最终都会看到跟新的tweet。

基于fan out strategy的优化

使用fan out

Not efficient for users with huge amount of followers (~>10k)

比如 对于 泰勒来说。使用fan out write方法

她有很多粉丝，有一些是活跃粉丝，有一些是僵尸粉

如果都需要更新cache的话，速度回很慢

可以采用 hybrid的 solution方法

Non-hot users

Hot users

Step 5: Data Storage

Step 6: Scalability

参考资料

Scott Shi

https://gist.github.com/vasanthk/485d1c25737e8e72759f

https://www.youtube.com/watch?v=-UXWETzHG38&t=574s

DDIA 电子书：

http://ddia.vonng.com/#/en-us/

SD从零开始 github

https://github.com/donnemartin/system-design-primer/blob/master/README-zh-Hans.md#如何处理一个系统设计的面试题

Design Twitter

https://www.youtube.com/watch?v=wqSnp49gGbg&t=946s

一亩三分地 面经

https://www.1point3acres.com/bbs/thread-1086103-1-1.html

https://www.1point3acres.com/bbs/thread-828490-1-1.html