设计 Mint.com

注意：这个文档中的链接会直接指向System Design 主题索引中的有关部分，以避免重复的内容。您可以参考链接的相关内容，来了解其总的要点、方案的权衡取舍以及可选的替代方案。

第一步：简述用例与约束条件

搜集需求与问题的范围。 提出问题来明确用例与约束条件。 讨论假设。

我们将在没有面试官明确说明问题的情况下，自己定义一些用例以及限制条件。

用例

我们将把问题限定在仅处理以下用例的范围中

• 用户 连接到一个财务账户
• 服务 从账户中提取交易
  • 每日更新
  • 分类交易
    • 允许用户手动分类
    • 不自动重新分类
  • 按类别分析每月支出
• 服务 推荐预算
  • 允许用户手动设置预算
  • 当接近或者超出预算时，发送通知
• 服务 具有 high availability

非用例范围

• 服务 执行附加的日志记录和分析

限制条件与假设

提出假设

• 网络流量非均匀分布
• 自动账户日更新只适用于 30 天内活跃的用户
• 添加或者移除财务账户相对较少
• 预算通知不需要及时
• 1000 万用户
  • 每个用户 10 个预算类别= 1 亿个预算项
  • 示例类别:
    • Housing = $1,000
    • Food = $200
    • Gas = $100
  • 卖方确定交易类别
    • 50000 个卖方
• 3000 万财务账户
• 每月 50 亿交易
• 每月 5 亿读请求
• 10:1 读写比
  • Write-heavy，用户每天都进行交易，但是每天很少访问该网站

计算用量

如果你需要进行粗略的用量计算，请向你的面试官说明。

• 每次交易的用量:
  • user_id - 8 字节
  • created_at - 5 字节
  • seller - 32 字节
  • amount - 5 字节
  • Total: ~50 字节
• 每月产生 250 GB 新的交易内容
  • 每次交易 50 比特 * 50 亿交易每月
  • 3 年内新的交易内容 9 TB
  • Assume most are new transactions instead of updates to existing ones
• 平均每秒产生 2000 次交易
• 平均每秒产生 200 读请求

便利换算指南：

• 每个月有 250 万秒
• 每秒一个请求 = 每个月 250 万次请求
• 每秒 40 个请求 = 每个月 1 亿次请求
• 每秒 400 个请求 = 每个月 10 亿次请求

第二步：概要设计

列出所有重要组件以规划概要设计。

第三步：设计核心组件

深入每个核心组件的细节。

用例：用户连接到一个财务账户

我们可以将 1000 万用户的信息存储在一个关系 database中。我们应该讨论一下选择 SQL 或 NoSQL 之间的用例和权衡了。

• 客户端 作为一个reverse proxy，发送请求到 Web 服务器
• Web 服务器 转发请求到 账户 API 服务器
• 账户 API 服务器将新输入的账户信息更新到 SQL database 的 accounts 表

告知你的面试官你准备写多少代码。

accounts表应该具有如下结构：

id int NOT NULL AUTO_INCREMENT
created_at datetime NOT NULL
last_update datetime NOT NULL
account_url varchar(255) NOT NULL
account_login varchar(32) NOT NULL
account_password_hash char(64) NOT NULL
user_id int NOT NULL
PRIMARY KEY(id)
FOREIGN KEY(user_id) REFERENCES users(id)

我们将在 id、user_id、created_at 字段上创建索引以加速查找（对数时间而不是全表扫描），并尽量保持数据在内存中。从内存顺序读取 1 MB 约 250 微秒，SSD 约 4 倍，机械硬盘约 80 倍。^{<a href=https://github.com/donnemartin/system-design-primer#latency-numbers-every-programmer-should-know>1}

我们将使用公开的 REST API：

$ curl -X POST --data '{ "user_id": "foo", "account_url": "bar", \
    "account_login": "baz", "account_password": "qux" }' \
    https://mint.com/api/v1/account

对于内部通信，我们可以使用 RPC。

接下来，服务从账户中提取交易。

用例：服务从账户中提取交易

如下几种情况下，我们会想要从账户中提取信息：

• 用户首次链接账户
• 用户手动更新账户
• 为过去 30 天内活跃的用户自动日更新

数据流:

• 客户端向 Web 服务器 发送请求
• Web 服务器 将请求转发到 帐户 API 服务器
• 帐户 API 服务器将 job 放在 queue 中，如 Amazon SQS 或 RabbitMQ
  • 提取交易可能需要一段时间，我们可能希望 async + queue 来做，虽然会引入额外复杂度。
• 交易提取服务 执行如下操作：
  • 从 Queue 中拉取并从金融机构提取给定用户交易，将结果作为原始日志文件存储在 对象存储区。
  • 使用 分类服务 来分类每个交易
  • 使用 预算服务 来按类别计算每月总支出
    • 预算服务 使用 通知服务 让用户知道他们是否接近或者已经超出预算
  • 更新具有分类交易的 SQL database 的 transactions 表
  • 按类别更新 SQL database 的 monthly_spending 表
  • 通过 通知服务 提醒用户交易完成
    • 使用一个 队列 (没有画出来) 来异步发送通知

transactions 表应该具有如下结构：

id int NOT NULL AUTO_INCREMENT
created_at datetime NOT NULL
seller varchar(32) NOT NULL
amount decimal NOT NULL
user_id int NOT NULL
PRIMARY KEY(id)
FOREIGN KEY(user_id) REFERENCES users(id)

我们将在 id，user_id，和 created_at字段上创建索引。

monthly_spending 表应该具有如下结构：

id int NOT NULL AUTO_INCREMENT
month_year date NOT NULL
category varchar(32)
amount decimal NOT NULL
user_id int NOT NULL
PRIMARY KEY(id)
FOREIGN KEY(user_id) REFERENCES users(id)

我们将在id，user_id字段上创建索引。

分类服务

对于 分类服务，我们可以生成一个包含热门卖家的 seller-category 字典。如果估计 50,000 个卖家、每条记录 255 bytes，这个字典大约 12 MB 内存。

告知你的面试官你准备写多少代码。

class DefaultCategories(Enum):

    HOUSING = 0
    FOOD = 1
    GAS = 2
    SHOPPING = 3
    ...

seller_category_map = {}
seller_category_map['Exxon'] = DefaultCategories.GAS
seller_category_map['Target'] = DefaultCategories.SHOPPING
...

对于一开始没有在映射中的卖家，我们可以通过评估用户提供的手动类别来进行众包。在 O(1) 时间内，我们可以用堆来快速查找每个卖家的顶端的手动覆盖。

class Categorizer(object):

    def __init__(self, seller_category_map, self.seller_category_crowd_overrides_map):
        self.seller_category_map = seller_category_map
        self.seller_category_crowd_overrides_map = \
            seller_category_crowd_overrides_map

    def categorize(self, transaction):
        if transaction.seller in self.seller_category_map:
            return self.seller_category_map[transaction.seller]
        elif transaction.seller in self.seller_category_crowd_overrides_map:
            self.seller_category_map[transaction.seller] = \
                self.seller_category_crowd_overrides_map[transaction.seller].peek_min()
            return self.seller_category_map[transaction.seller]
        return None

交易实现：

class Transaction(object):

    def __init__(self, created_at, seller, amount):
        self.timestamp = timestamp
        self.seller = seller
        self.amount = amount

用例：服务推荐预算

首先，我们可以使用根据收入等级分配每类别金额的通用预算模板。使用这种方法，我们不必存储在约束中标识的 1 亿个预算项目，只需存储用户覆盖的预算项目。如果用户覆盖预算类别，我们可以在 TABLE budget_overrides中存储此覆盖。

class Budget(object):

    def __init__(self, income):
        self.income = income
        self.categories_to_budget_map = self.create_budget_template()

    def create_budget_template(self):
        return {
            'DefaultCategories.HOUSING': income * .4,
            'DefaultCategories.FOOD': income * .2
            'DefaultCategories.GAS': income * .1,
            'DefaultCategories.SHOPPING': income * .2
            ...
        }

    def override_category_budget(self, category, amount):
        self.categories_to_budget_map[category] = amount

对于 预算服务 而言，我们可以在transactions表上运行 SQL 查询以生成monthly_spending聚合表。由于用户通常每个月有很多交易，所以monthly_spending表的行数可能会少于总共 50 亿次交易的行数。

作为替代，我们可以在原始交易文件上运行 MapReduce 作业：

• 分类每个交易
• 按类别生成每月总支出

对交易文件的分析可以显著减少 database 负载。

如果用户更新类别，我们可以调用 预算服务 重新运行分析。

告知你的面试官你准备写多少代码。

日志文件格式样例，以 tab 分割：

user_id   timestamp   seller  amount

MapReduce 实现：

class SpendingByCategory(MRJob):

    def __init__(self, categorizer):
        self.categorizer = categorizer
        self.current_year_month = calc_current_year_month()
        ...

    def calc_current_year_month(self):
        """返回当前年月"""
        ...

    def extract_year_month(self, timestamp):
        """返回时间戳的年，月部分"""
        ...

    def handle_budget_notifications(self, key, total):
        """如果接近或超出预算，调用通知API"""
        ...

    def mapper(self, _, line):
        """解析每个日志行，提取和转换相关行。

        参数行应为如下形式：

        user_id   timestamp   seller  amount

        使用分类器来将卖家转换成类别，生成如下形式的key-value对：

        (user_id, 2016-01, shopping), 25
        (user_id, 2016-01, shopping), 100
        (user_id, 2016-01, gas), 50
        """
        user_id, timestamp, seller, amount = line.split('\t')
        category = self.categorizer.categorize(seller)
        period = self.extract_year_month(timestamp)
        if period == self.current_year_month:
            yield (user_id, period, category), amount

    def reducer(self, key, value):
        """将每个key对应的值求和。

        (user_id, 2016-01, shopping), 125
        (user_id, 2016-01, gas), 50
        """
        total = sum(values)
        yield key, sum(values)

第四步：设计扩展

根据限制条件，找到并解决瓶颈。

重要提示：不要从最初设计直接跳到最终设计中！

现在你要 1) 基准测试、负载测试。2) 分析、描述 performance 瓶颈。3) 在解决瓶颈时评估替代方案与 trade-offs。4) 重复以上步骤。请阅读「设计一个系统，并将其扩大到为数以百万计的 AWS 用户服务」 了解如何逐步扩展初始设计。

讨论初始设计可能遇到的瓶颈及对应方案很重要。例如多台 Web 服务器 + load balancer 是否足够？CDN 呢？主从复制 呢？它们各自的替代方案与 trade-offs 是什么？

我们将介绍一些组件来完成设计并解决扩展问题。内置的 load balancer 不再展开。

为了避免重复讨论，请参考System Design 主题索引相关部分来了解其要点、方案的权衡取舍以及可选的替代方案。

• DNS
• load balancer
• 水平拓展
• reverse proxy（web 服务器）
• API 服务（应用层）
• cache
• 关系型 database 管理系统 (RDBMS)
• SQL 故障主从切换
• 主从复制
• 异步
• consistency 模式
• availability 模式

我们将增加一个额外的用例：用户 访问摘要和交易数据。

用户会话、按类别统计信息、最近交易可以放在 内存 cache（如 Redis / Memcached）中。

• 客户端 发送读请求给 Web 服务器
• Web 服务器 转发请求到 读 API 服务器
  • 静态内容可通过 对象存储（例如 cache 在 CDN 上的 S3）提供
• 读 API 服务器做如下动作:
  • 检查 内存 cache 的内容
    • 如果 URL 在 内存 cache 中，返回 cache 内容
    • 否则
      • 如果 URL 在 SQL database 中，获取该内容
        • 以其内容更新 内存 cache

参考 何时更新 cache 中的 trade-offs。以上方法描述了 cache-aside 模式。

我们可以使用诸如 Amazon Redshift 或者 Google BigQuery 等数据仓库解决方案，而不是将monthly_spending聚合表保留在 SQL database 中。

我们可能只想在 database 中存储一个月的交易数据，而将其余数据存储在数据仓库或者 对象存储区 中。对象存储区 （如 Amazon S3) 能够舒服地解决每月 250 GB 新内容的限制。

为了解决每秒 平均 2000 次读请求数（峰值时更高），受欢迎的内容流量应由 内存 cache 而不是 database 处理。内存 cache 也可用于处理不均匀分布的流量和流量尖峰。只要副本不陷入重复写入的困境，SQL 读副本 应该能够处理高速 cache 未命中。

平均 200 次交易写入每秒（峰值时更高）对于单个 SQL 写入主-从服务 来说可能是棘手的。我们可能需要考虑其它的 SQL performance 拓展技术：

• 联合
• 分片
• 非规范化
• SQL 调优

我们也可以考虑将一些数据移至 NoSQL database。

其它要点

是否深入这些额外的主题，取决于你的问题范围和剩下的时间。

NoSQL

• 键-值存储
• 文档类型存储
• 列型存储
• 图 database
• SQL vs NoSQL

cache

• 在哪 cache
  • 客户端 cache
  • CDN cache
  • Web 服务器 cache
  • database cache
  • 应用 cache
• 什么需要 cache
  • database 查询级别的 cache
  • 对象级别的 cache
• 何时更新 cache
  • cache 模式
  • 直写模式
  • 回写模式
  • 刷新

异步与 microservices

• message queue
• task queue
• 背压
• microservices

通信

• 可权衡选择的方案：
  • 与客户端的外部通信 - 使用 REST 作为 HTTP API
  • 服务器内部通信 - RPC
• service discovery

安全性

请参阅「安全」一章。

latency 数值

请参阅「每个程序员都应该知道的 latency 数」。

持续探讨

• 持续进行基准测试并监控你的系统，以解决他们提出的瓶颈问题。
• 架构拓展是一个迭代的过程。

参考与下载