跳到主要内容

45 篇博文 含有标签「系统设计」

查看所有标签

设计度量系统

· 阅读需 14 分钟

需求

日志与度量:日志是发生的事件,而度量是对系统健康状况的测量。

我们假设该系统的目的是提供度量——即计数器、转化率、计时器等,用于监控系统性能和健康。如果转化率大幅下降,系统应警告值班人员。

  1. 监控商业指标,如注册漏斗的转化率
  2. 支持各种查询,如在不同平台上(IE/Chrome/Safari,iOS/Android/桌面等)
  3. 数据可视化
  4. 可扩展性和可用性

架构

构建系统的两种方式:

  1. 推送模型:Influx/Telegraf/Grafana
  2. 拉取模型:Prometheus/Grafana

拉取模型更具可扩展性,因为它减少了进入度量数据库的请求数量——没有热路径和并发问题。

服务器农场

服务器农场

写入

写入

Telegraf

Telegraf

InfluxDB

InfluxDB

REST API

REST API

Grafana

Grafana

InfluxDB 推送模型

InfluxDB 推送模型

Prometheus 拉取模型

Prometheus 拉取模型

应用程序

应用程序

导出器

导出器

客户端库

客户端库

第三方


应用程序

第三方<br>应用程序

拉取

拉取

Prometheus

Prometheus

检索

检索

服务发现

服务发现

存储

存储

PromQL

PromQL

告警管理器

告警管理器

Web UI / Grafana / API 客户端

Web UI / Grafana / API 客户端

PagerDuty

PagerDuty

邮件

邮件

特性与组件

测量注册漏斗

以移动应用的四步注册为例

输入手机号码 -> 验证短信代码 -> 输入姓名 -> 输入密码

每一步都有 IMPRESSIONPOST_VERIFICATION 阶段。并发出如下度量:

{
"sign_up_session_id": "uuid",
"step": "VERIFY_SMS_CODE",
"os": "iOS",
"phase": "POST_VERIFICATION",
"status": "SUCCESS",
// ... ts, contexts, ...
}

因此,我们可以查询 iOSVERIFY_SMS_CODE 步骤的整体转化率,如下所示:

(counts of step=VERIFY_SMS_CODE, os=iOS, status: SUCCESS, phase: POST_VERIFICATION) / (counts of step=VERIFY_SMS_CODE, os=iOS, phase: IMPRESSION)

数据可视化

Grafana 在数据可视化工作中已经相当成熟。如果您不想暴露整个网站,可以使用 嵌入面板与 iframe

设计 Square Cash 或 PayPal 转账系统

· 阅读需 21 分钟

澄清需求

设计一个类似于 Square Cash(以下称为 Cash App)或 PayPal 的转账后端系统,以实现:

  1. 从银行存款和支付
  2. 账户之间转账
  3. 高扩展性和可用性
  4. 国际化:语言、时区、货币兑换
  5. 非幂等 API 和至少一次交付的去重
  6. 跨多个数据源的一致性

架构

AWS CloudHSM

AWS CloudHSM

演示层

演示层

SDK/文档

SDK/文档

移动仪表板

移动仪表板

网页仪表板

网页仪表板

仪表板客户端

仪表板客户端

移动钱包

移动钱包

网页钱包

网页钱包

钱包客户端

钱包客户端

商户 


用户

商户 <br>用户

最终用户

最终用户

网页 Chrome 扩展

网页 Chrome 扩展

操作员

操作员

支付

支付

任务队列

任务队列

财务报告

财务报告

支付网关

支付网关

银行 / 


供应商

[不支持的查看器]

副作用制造者

副作用制造者

帮助服务门户

帮助服务门户

用户


配置文件


AuthDB


[不支持的查看器]

API 网关


单体


API 网关<br>单体<br>

支付


数据库


支付<br>数据库<br>

Aurora

Aurora

风险控制

风险控制

风险控制

风险控制

事件
队列

[不支持的查看器]

功能和组件

支付服务

支付数据模型本质上是“复式记账”。每个账户的每一笔入账都需要在另一个账户中有相应的对立入账。所有借方和贷方的总和等于零。

存款和支付

交易:新用户 Jane Doe 从银行向 Cash App 存入 100 美元。这一笔交易涉及以下数据库条目:

记账表(用于历史记录)

+ 借方, 美元, 100, CashAppAccountNumber, txId
- 贷方, 美元, 100, RoutingNumber:AccountNumber, txId

交易表

txId, 时间戳, 状态(待处理/已确认), [记账条目], 叙述

一旦银行确认交易,更新上述待处理状态和以下资产负债表,均在一笔交易中完成。

资产负债表

CashAppAccountNumber, 美元, 100

在 Cash App 内部账户之间转账

与上述情况类似,但没有待处理状态,因为我们不需要慢速外部系统来更改其状态。所有记账表、交易表和资产负债表的更改都在一笔交易中完成。

国际化

我们在三个维度上解决国际化问题。

  1. 语言:所有文本,如文案、推送通知、电子邮件,均根据 accept-language 头部进行选择。
  2. 时区:所有服务器时区均为 UTC。我们在客户端将时间戳转换为本地时区。
  3. 货币:所有用户转账交易必须使用相同货币。如果他们想要跨货币转移,必须先以对 Cash App 有利的汇率兑换货币。

例如,Jane Doe 想以 0.2 的汇率将 1 美元兑换为 6.8 人民币。

记账表

- 贷方, 美元, 1, CashAppAccountNumber, txId
+ 借方, 人民币, 6.8, CashAppAccountNumber, txId, @7.55 人民币/美元
+ 借方, 美元, 0.1, ExpensesOfExchangeAccountNumber, txId

交易表、资产负债表等与存款和支付中讨论的交易类似。主要区别在于银行或供应商提供兑换服务。

如何在交易表和外部银行及供应商之间同步?

  • 使用幂等性重试以提高外部调用的成功率并确保没有重复订单
  • 检查待处理订单是否已完成或失败的两种方法。
    1. 轮询:定时作业(SWF、Airflow、Cadence 等)轮询待处理订单的状态。
    2. 回调:为外部供应商提供回调 API。
  • 优雅关闭。银行网关调用可能需要数十秒才能完成,重启服务器可能会从数据库恢复未完成的交易。该过程可能会创建过多连接。为减少连接,在关闭之前停止接受新请求,并等待现有的外发请求完成。

去重

为什么去重是一个问题?

  1. 不是所有端点都是幂等的
  2. 事件队列可能是至少一次的。

不是所有端点都是幂等的:如果外部系统不是幂等的怎么办?

对于上述 轮询 情况,如果外部网关不支持幂等 API,为了不淹没重复条目,我们必须记录外部系统给我们的订单 ID 或参考 ID,并通过订单 ID 查询 GET,而不是一直使用 POST

对于 回调 情况,我们可以确保实现幂等 API,并且无论如何我们将 待处理 更改为 已确认

事件队列可能是至少一次的

  • 对于事件队列,我们可以使用一个完全一次的 Kafka,生产者吞吐量仅下降 3%。
  • 在数据库层,我们可以使用 幂等性密钥或去重密钥
  • 在服务层,我们可以使用 Redis 键值存储。

可用性和扩展性

设计支付 webhook

· 阅读需 5 分钟

1. 澄清需求

  1. 一旦支付成功,webhook 将回调商家。
    1. 商家开发者向我们注册 webhook 信息。
    2. 可靠且安全地向 webhook 发起 POST HTTP 请求。
  2. 高可用性、错误处理和故障恢复。
    1. 异步设计。假设商家的服务器分布在全球,可能会有高达 15 秒的延迟。
    2. 至少一次交付。幂等密钥。
    3. 顺序无关。
    4. 强大且可预测的重试和短路机制。
  3. 安全性、可观察性和可扩展性。
    1. 防伪造。
    2. 当商家的接收器出现故障时通知商家。
    3. 易于扩展和规模化。

2. 概述高层设计

异步设计 + 重试 + 排队 + 可观察性 + 安全性

3. 功能和组件

核心功能

  1. 用户访问仪表板前端向我们注册 webhook 信息 - 例如要调用的 URL、他们希望订阅的事件范围,然后从我们这里获取 API 密钥。
  2. 当有新事件时,将其发布到队列中,然后被调用者消费。调用者获取注册信息并向外部服务发起 HTTP 调用。

webhook 调用者

  1. 订阅由支付状态机或其他服务发布的支付成功事件队列。

  2. 一旦调用者接受事件,从用户设置服务获取 webhook URI、密钥和设置。根据这些设置准备请求。为了安全...

  • 所有来自用户设置的 webhook 必须使用 HTTPS。

  • 如果负载很大,预期延迟很高,并且我们希望确保目标接收器是活跃的,我们可以通过携带挑战的 ping 验证其存在。例如,Dropbox 通过发送带有“challenge”参数(一个随机字符串)的 GET 请求来验证 webhook 端点,您的端点需要将其回显作为响应。

  • 所有回调请求都带有头部 x-webhook-signature。这样接收者可以验证请求。

    • 对于对称签名,我们可以使用 HMAC/SHA256 签名。其值为 HMAC(webhook secret, raw request payload); Telegram 使用此方法。
    • 对于非对称签名,我们可以使用 RSA/SHA256 签名。其值为 RSA(webhook private key, raw request payload); Stripe 使用此方法。
    • 如果是敏感信息,我们还可以考虑对负载进行加密,而不仅仅是签名。
  1. 向外部商家的端点发起带有事件负载和安全头的 HTTP POST 请求。

API 定义

// POST https://example.com/webhook/
{
"id": 1,
"scheduled_for": "2017-01-31T20:50:02Z",
"event": {
"id": "24934862-d980-46cb-9402-43c81b0cdba6",
"resource": "event",
"type": "charge:created",
"api_version": "2018-03-22",
"created_at": "2017-01-31T20:49:02Z",
"data": {
"code": "66BEOV2A", // 或用户需要履行的订单 ID
"name": "主权个体",
"description": "掌握信息时代的过渡",
"hosted_url": "https://commerce.coinbase.com/charges/66BEOV2A",
"created_at": "2017-01-31T20:49:02Z",
"expires_at": "2017-01-31T21:49:02Z",
"metadata": {},
"pricing_type": "CNY",
"payments": [
// ...
],
"addresses": {
// ...
}
}
}
}

商家服务器应以 200 HTTP 状态码响应以确认收到 webhook。

错误处理

如果没有收到确认,我们将使用幂等性密钥和指数退避重试,最长可达三天。最大重试间隔为 1 小时。 如果达到某个限制,则短路/标记为损坏。向商家发送电子邮件。

指标

Webhook 调用者服务将状态发射到时序数据库以获取指标。

使用 Statsd + Influx DB 还是 Prometheus?

  • InfluxDB:应用程序将数据推送到 InfluxDB。它有一个用于指标和索引的单体数据库。
  • Prometheus:Prometheus 服务器定期从运行的应用程序中拉取指标值。它使用 LevelDB 进行索引,但每个指标存储在自己的文件中。

或者如果您有宽裕的预算,可以使用昂贵的 DataDog 或其他 APM 服务。

设计股票交易所

· 阅读需 17 分钟

需求

  • 买入卖出 订单的订单匹配系统。订单类型:
    • 市场订单
    • 限价订单
    • 止损订单
    • 完全成交或取消订单
    • 订单有效期
  • 为数百万用户提供高可用性和低延迟
    • 异步设计 - 广泛使用消息队列(顺便提一下,副作用:工程师在一个服务上发布到队列,不知道下游服务具体在哪里,因此无法做坏事。)

架构

反向代理

反向代理

API 网关

API 网关

订单匹配

订单匹配

用户存储

用户存储

结算

结算

订单

订单

股票元数据

股票元数据

认证

认证

缓存

缓存

余额与记账

余额与记账

外部定价

外部定价

清算


清算<br>所

银行,ACH,Visa 等

银行,ACH,Visa 等

支付

支付

审计与报告

审计与报告

组件及其相互作用

订单匹配系统

  • 按股票代码分片
  • 订单的基本数据模型(其他元数据省略):Order(id, stock, side, time, qty, price)
  • 订单簿的核心抽象是匹配算法。有许多匹配算法(参考 stackoverflow参考 medium
  • 示例 1:价格-时间 FIFO - 一种将二维向量投射或展平为一维向量的方式
    • x 轴是价格
    • y 轴是订单。价格/时间优先队列,FIFO。
      • 买方:按价格升序,按时间降序。
      • 卖方:按价格升序,按时间升序。
    • 换句话说
      • 买方:价格越高,订单越早,越接近匹配中心。
      • 卖方:价格越低,订单越早,越接近匹配中心。

x 轴

价格线

y 轴投射到 x 轴上

Id   Side    Time   Qty   Price   Qty    Time   Side
---+------+-------+-----+-------+-----+-------+------
#3 20.30 200 09:05 卖出
#1 20.30 100 09:01 卖出
#2 20.25 100 09:03 卖出
#5 买入 09:08 200 20.20
#4 买入 09:06 100 20.15
#6 买入 09:09 200 20.15

来自 Coinbase Pro 的订单簿

单一股票交易所模拟器

  • 示例 2:按比例分配

纯按比例分配

如何实现价格-时间 FIFO 匹配算法?

  • 按股票分片,CP 优于 AP:一股一个分区
  • 有状态的内存树图
    • 定期迭代树图以匹配订单
  • 使用 Cassandra 进行数据持久化
  • 订单匹配服务的进出请求通过消息队列进行
  • 故障转移
    • 内存树图快照到数据库
    • 在错误情况下,从快照恢复并与缓存去重

如何实时将订单簿数据传输到客户端?

  • websocket

如何支持不同类型的订单?

  • 在树图中使用相同的 卖出或买入:数量 @ 价格,但具有不同的创建设置和匹配条件
    • 市场订单:以最后市场价格下单。
    • 限价订单:以特定价格下单。
    • 止损订单:以特定价格下单,并在特定条件下匹配。
    • 完全成交或取消订单:以特定价格下单,但仅匹配一次。
    • 订单有效期:以特定价格下单,但仅在给定时间范围内匹配。

订单服务

  • 保留所有活动订单和订单历史。
  • 接收到新订单时写入订单匹配。
  • 接收匹配的订单并与外部清算所结算(异步外部网关调用 + 定时任务同步数据库)

参考文献

建筑导论

· 阅读需 4 分钟

什么是架构?

架构是软件系统的形状。将其视为物理建筑的全景。

  • 范式是砖块。
  • 设计原则是房间。
  • 组件是建筑。

它们共同服务于特定的目的,例如医院是为治愈病人而设,学校是为教育学生而设。

我们为什么需要架构?

行为与结构

每个软件系统为利益相关者提供两种不同的价值:行为和结构。软件开发人员负责确保这两种价值都保持高水平。

==软件架构师由于其工作描述,更加关注系统的结构,而不是其特性和功能。==

终极目标 - ==每个功能节省人力资源成本==

架构为软件系统的整个生命周期提供服务,使其易于理解、开发、测试、部署和操作。目标是最小化每个业务用例的人力资源成本。

O’Reilly的书《软件架构模式》由Mark Richards撰写,是对这五种基本架构的简单而有效的介绍。

1. 分层架构

分层架构是最常见的架构,开发人员广泛熟知,因此是应用程序的事实标准。如果您不知道使用什么架构,请使用它。

示例

  • TCP / IP模型:应用层 > 传输层 > 网络层 > 网络接入层
  • Facebook TAO:网页层 > 缓存层(跟随者 + 领导者) > 数据库层

优缺点

  • 优点
    • 易于使用
    • 职责分离
    • 可测试性
  • 缺点
    • 单体
      • 难以调整、扩展或更新。您必须对所有层进行更改。

2. 事件驱动架构

状态变化将向系统发出事件。所有组件通过事件相互通信。

一个简单的项目可以结合中介、事件队列和通道。然后我们得到一个简化的架构:

示例

  • QT:信号和插槽
  • 支付基础设施:银行网关通常具有非常高的延迟,因此在其架构设计中采用异步技术。

3. 微内核架构(即插件架构)

软件的职责被划分为一个“核心”和多个“插件”。核心包含最基本的功能。插件彼此独立,并实现共享接口以实现不同的目标。

示例

  • Visual Studio Code,Eclipse
  • MINIX操作系统

4. 微服务架构

一个庞大的系统被解耦为多个微服务,每个微服务都是一个单独部署的单元,它们通过RPCs相互通信。

uber architecture

示例

5. 基于空间的架构

该模式得名于“元组空间”,意为“分布式共享内存”。没有数据库或同步数据库访问,因此没有数据库瓶颈。所有处理单元在内存中共享复制的应用数据。这些处理单元可以弹性启动和关闭。

示例:见维基百科

  • 主要在Java用户中采用:例如,JavaSpaces

今日头条推荐系统:P2 内容分析

· 阅读需 5 分钟

今日头条推荐系统:P1 概述 中,我们了解到内容分析和用户标签的数据挖掘是推荐系统的基石。

什么是内容分析?

内容分析 = 从原始文章和用户行为中提取中间数据。

以文章为例。为了建模用户兴趣,我们需要对内容和文章进行标记。为了将用户与“互联网”标签的兴趣关联起来,我们需要知道用户是否阅读了带有“互联网”标签的文章。

我们为什么要分析这些原始数据?

我们这样做的原因是 …

  1. 标记用户(用户画像)
    • 标记喜欢带有“互联网”标签的文章的用户。标记喜欢带有“小米”标签的文章的用户。
  2. 根据标签向用户推荐内容
    • 向带有“小米”标签的用户推送“小米”内容。向带有“Dota”标签的用户推送“Dota”内容。
  3. 按主题准备内容
    • 将“德甲”文章放入“德甲主题”。将“饮食”文章放入“饮食主题”。

案例研究:一篇文章的分析结果

以下是“文章特征”页面的示例。文章特征包括分类、关键词、主题、实体。

一篇文章的分析结果

一篇文章的分析结果:详细信息

文章特征是什么?

  1. 语义标签:人类预定义这些标签,具有明确的含义。

  2. 隐含语义,包括主题和关键词。主题特征描述了单词的统计数据。某些规则生成关键词。

  3. 相似性。重复推荐曾是我们从客户那里获得的最严重反馈之一。

  4. 时间和地点。

  5. 质量。滥用、色情、广告或“心灵鸡汤”?

文章特征的重要性

  • 并不是说没有文章特征推荐系统就完全无法工作。亚马逊、沃尔玛、Netflix可以通过协同过滤进行推荐。
  • 然而,在新闻产品中,用户消费的是当天的内容。没有文章特征的引导是困难的。协同过滤无法帮助引导。
    • 文章特征的粒度越细,启动的能力就越强。

更多关于语义标签的信息

我们将语义标签的特征分为三个层次:

  1. 分类:用于用户画像、过滤主题内容、推荐召回、推荐特征
  2. 概念:用于过滤主题内容、搜索标签、推荐召回(喜欢)
  3. 实体:用于过滤主题内容、搜索标签、推荐召回(喜欢)

为什么要分成不同的层次?我们这样做是为了能够以不同的粒度捕捉文章。

  1. 分类:覆盖全面,准确性低。
  2. 概念:覆盖中等,准确性中等。
  3. 实体:覆盖低,准确性高。它仅覆盖每个领域的热门人物、组织、产品。

分类和概念共享相同的技术基础设施。

我们为什么需要语义标签?

  • 隐含语义
    • 一直运作良好。
    • 成本远低于语义标签。
  • 但是,主题和兴趣需要一个明确的标签系统。
  • 语义标签还评估公司的NPL技术能力。

文档分类

分类层级

  1. 科学、体育、金融、娱乐
  2. 足球、网球、乒乓球、田径、游泳
  3. 国际、国内
  4. A队、B队

分类器:

  • SVM
  • SVM + CNN
  • SVM + CNN + RNN

计算相关性

  1. 对文章进行词汇分析
  2. 过滤关键词
  3. 消歧义
  4. 计算相关性

今日头条推荐系统:P1 概述

· 阅读需 10 分钟

我们优化的目标是什么?用户满意度

我们正在寻找以下最佳 function 以最大化 用户满意度

用户满意度 = function(内容, 用户资料, 上下文)
  1. 内容:文章、视频、用户生成内容短视频、问答等的特征。
  2. 用户资料:兴趣、职业、年龄、性别和行为模式等。
  3. 上下文:在工作空间、通勤、旅行等情况下的移动用户。

如何评估满意度?

  1. 可测量的目标,例如:

    • 点击率
    • 会话持续时间
    • 点赞
    • 评论
    • 转发
  2. 难以测量的目标:

    • 广告和特殊类型内容(问答)的频率控制
    • 低俗内容的频率控制
    • 减少点击诱饵、低质量、恶心内容
    • 强制/置顶/高度权重重要新闻
    • 低权重来自低级账户的内容

如何优化这些目标?机器学习模型

找到上述最佳 function 是一个典型的监督机器学习问题。为了实施该系统,我们有以下算法:

  1. 协同过滤
  2. 逻辑回归
  3. 深度神经网络
  4. 因子分解机
  5. GBDT

一个世界级的推荐系统应该具备 灵活性,以进行 A/B 测试并结合上述多种算法。现在结合逻辑回归和深度神经网络变得流行。几年前,Facebook 使用了逻辑回归和 GBDT。

模型如何观察和测量现实?特征工程

  1. 内容特征与用户兴趣之间的相关性。 显式相关性包括关键词、类别、来源、类型。隐式相关性可以从 FM 等模型的用户向量或项目向量中提取。

  2. 环境特征,如地理位置、时间。 可以用作偏见或在其基础上建立相关性。

  3. 热门趋势。 有全球热门趋势、类别热门趋势、主题热门趋势和关键词热门趋势。热门趋势在我们对用户信息较少时非常有助于解决冷启动问题。

  4. 协同特征,帮助避免推荐内容越来越集中。 协同过滤不是单独分析每个用户的历史,而是根据用户的点击、兴趣、主题、关键词或隐式向量找到用户的相似性。通过找到相似用户,可以扩展推荐内容的多样性。

实时大规模训练

  • 用户喜欢看到根据我们从他们的行为中跟踪到的内容实时更新的新闻源。
  • 使用 Apache Storm 实时训练数据(点击、展示、收藏、分享)。
  • 收集数据到达阈值后更新推荐模型
  • 在高性能计算集群中存储模型参数,如数十亿的原始特征和数十亿的向量特征。

它们的实现步骤如下:

  1. 在线服务实时记录特征。
  2. 将数据写入 Kafka
  3. 从 Kafka 向 Storm 导入数据
  4. 填充完整的用户资料并准备样本
  5. 根据最新样本更新模型参数
  6. 在线建模获得新知识

如何进一步减少延迟?召回策略

考虑到所有内容的超大规模,无法用模型预测所有事情。因此,我们需要召回策略来关注数据的代表性子集。性能在这里至关重要,超时时间为 50 毫秒。

召回策略

在所有召回策略中,我们采用 InvertedIndex<Key, List<Article>>

Key 可以是主题、实体、来源等。

兴趣标签相关性文档列表
电子商务0.3
娱乐0.2
历史0.2
军事0.1

数据依赖

  • 特征依赖于用户端和内容端的标签。
  • 召回策略依赖于用户端和内容端的标签。
  • 用户标签的内容分析和数据挖掘是推荐系统的基石。

什么是内容分析?

内容分析 = 从原始文章和用户行为中推导中间数据。

以文章为例。为了建模用户兴趣,我们需要对内容和文章进行标记。为了将用户与“互联网”标签的兴趣关联起来,我们需要知道用户是否阅读了带有“互联网”标签的文章。

我们为什么要分析这些原始数据?

我们这样做的原因是 …

  1. 标记用户(用户资料)
    • 标记喜欢带有“互联网”标签的文章的用户。标记喜欢带有“小米”标签的文章的用户。
  2. 通过标签向用户推荐内容
    • 向带有“小米”标签的用户推送“小米”内容。向带有“Dota”标签的用户推送“Dota”内容。
  3. 按主题准备内容
    • 将“德甲”文章放入“德甲主题”。将“饮食”文章放入“饮食主题”。

案例研究:一篇文章的分析结果

这是“文章特征”页面的示例。文章特征包括分类、关键词、主题、实体。

文章分析结果

文章分析结果:详细信息

文章特征是什么?

  1. 语义标签:人类预定义这些标签并赋予明确的含义。

  2. 隐式语义,包括主题和关键词。主题特征描述了单词的统计信息。某些规则生成关键词。

  3. 相似性。重复推荐曾是我们客户反馈中最严重的问题。

  4. 时间和地点。

  5. 质量。滥用、色情、广告或“心灵鸡汤”?

文章特征的重要性

  • 推荐系统并非完全无法在没有文章特征的情况下工作。亚马逊、沃尔玛、Netflix 可以通过协同过滤进行推荐。
  • 然而,在新闻产品中,用户消费的是同一天的内容。没有文章特征的引导是困难的。协同过滤无法帮助引导。
    • 文章特征的粒度越细,启动的能力越强。

更多关于语义标签

我们将语义标签的特征分为三个层次:

  1. 分类:用于用户资料、过滤主题内容、推荐召回、推荐特征
  2. 概念:用于过滤主题内容、搜索标签、推荐召回(喜欢)
  3. 实体:用于过滤主题内容、搜索标签、推荐召回(喜欢)

为什么要分为不同层次?我们这样做是为了能够以不同的粒度捕捉文章。

  1. 分类:覆盖全面,准确性低。
  2. 概念:覆盖中等,准确性中等。
  3. 实体:覆盖低,准确性高。它仅覆盖每个领域的热门人物、组织、产品。

分类和概念共享相同的技术基础设施。

我们为什么需要语义标签?

  • 隐式语义
    • 一直运作良好。
    • 成本远低于语义标签。
  • 但是,主题和兴趣需要一个明确的标记系统。
  • 语义标签还评估了公司在 NPL 技术方面的能力。

文档分类

分类层次结构

  1. 科学、体育、金融、娱乐
  2. 足球、网球、乒乓球、田径、游泳
  3. 国际、国内
  4. A 队、B 队

分类器:

  • SVM
  • SVM + CNN
  • SVM + CNN + RNN

计算相关性

  1. 对文章进行词汇分析
  2. 过滤关键词
  3. 消歧义
  4. 计算相关性

今日头条推荐系统:P1 概述

· 阅读需 6 分钟

我们优化的目标是什么?用户满意度

我们正在寻找以下最佳 函数 以最大化 用户满意度

用户满意度 = 函数(内容, 用户画像, 上下文)
  1. 内容:文章、视频、用户生成内容短视频、问答等的特征。
  2. 用户画像:兴趣、职业、年龄、性别和行为模式等。
  3. 上下文:工作空间、通勤、旅行等场景下的移动用户。

如何评估满意度?

  1. 可测量的目标,例如:

    • 点击率
    • 会话时长
    • 点赞
    • 评论
    • 转发
  2. 难以测量的目标:

    • 广告和特殊类型内容(问答)的频率控制
    • 低俗内容的频率控制
    • 减少点击诱饵、低质量、恶心内容
    • 强制/固定/高度权重重要新闻
    • 低权重来自低级账户的内容

如何优化这些目标?机器学习模型

寻找上述最佳 函数 是一个典型的监督机器学习问题。为了实现系统,我们有以下算法:

  1. 协同过滤
  2. 逻辑回归
  3. 深度神经网络
  4. 因子分解机
  5. GBDT

一个世界级的推荐系统应该具备 灵活性,能够进行 A/B 测试并结合上述多种算法。现在结合逻辑回归和深度神经网络的做法越来越流行。Facebook 多年前就同时使用了逻辑回归和 GBDT。

模型如何观察和测量现实?特征工程

  1. 内容特征与用户兴趣之间的相关性。 显性相关性包括关键词、类别、来源、类型。隐性相关性可以从用户向量或模型如因子分解机中的物品向量中提取。

  2. 环境特征,如地理位置、时间。 可以作为偏差或在其基础上建立相关性。

  3. 热门趋势。 有全球热门趋势、类别热门趋势、主题热门趋势和关键词热门趋势。热门趋势在我们对用户信息较少时非常有助于解决冷启动问题。

  4. 协同特征,有助于避免推荐内容越来越集中。 协同过滤不是单独分析每个用户的历史,而是根据用户的点击、兴趣、主题、关键词或隐性向量找到用户之间的相似性。通过找到相似用户,可以扩展推荐内容的多样性。

大规模实时训练

  • 用户喜欢看到根据我们从他们的行为中跟踪到的信息实时更新的新闻推送。
  • 使用 Apache Storm 实时训练数据(点击、展示、收藏、分享)。
  • 收集数据直到达到阈值,然后更新推荐模型
  • 在高性能计算集群中存储模型参数,如数百亿的原始特征和数十亿的向量特征。

它们的实现步骤如下:

  1. 在线服务实时记录特征。
  2. 将数据写入 Kafka
  3. 从 Kafka 向 Storm 进件数据
  4. 填充完整的用户画像并准备样本
  5. 根据最新样本更新模型参数
  6. 在线建模获得新知识

如何进一步减少延迟?召回策略

考虑到所有内容的超大规模,无法用模型预测所有事情。因此,我们需要召回策略来关注数据的代表性子集。性能在这里至关重要,超时为 50 毫秒。

召回策略

在所有召回策略中,我们采用 反向索引<Key, List<Article>>

Key 可以是主题、实体、来源等。

兴趣标签相关性文档列表
电子商务0.3
娱乐0.2
历史0.2
军事0.1

数据依赖

  • 特征依赖于用户端和内容端的标签。
  • 召回策略依赖于用户端和内容端的标签。
  • 用户标签的内容分析和数据挖掘是推荐系统的基石。

流处理与批处理框架

· 阅读需 3 分钟

为什么需要这样的框架?

  • 以低延迟处理高吞吐量。
  • 分布式系统中的容错能力。
  • 通用抽象以满足多变的业务需求。
  • 适用于有界数据集(批处理)和无界数据集(流处理)。

批处理/流处理的简史

  1. Hadoop 和 MapReduce。Google 使批处理在分布式系统中变得简单,如 MR result = pairs.map((pair) => (morePairs)).reduce(somePairs => lessPairs)
  2. Apache Storm 和 DAG 拓扑。MR 无法有效表达迭代算法。因此,Nathan Marz 将流处理抽象为喷口和螺栓的图。
  3. Spark 内存计算。Reynold Xin 表示,Spark 使用 10 倍更少的机器3 倍更快 的速度对相同数据进行排序。
  4. 基于 Millwheel 和 FlumeJava 的 Google Dataflow。Google 支持批处理和流处理计算,使用窗口 API。
  1. 它快速采用了 ==Google Dataflow==/Beam 编程模型。
  2. 它对 Chandy-Lamport 检查点的高效实现。

如何?

架构选择

为了用商品机器满足上述需求,流处理框架在这些架构中使用分布式系统……

  • 主从(集中式):apache storm 与 zookeeper,apache samza 与 YARN。
  • P2P(去中心化):apache s4。

特性

  1. DAG 拓扑用于迭代处理。例如,Spark 中的 GraphX,Apache Storm 中的拓扑,Flink 中的数据流 API。
  2. 交付保证。如何保证从节点到节点的数据交付?至少一次 / 至多一次 / 精确一次。
  3. 容错能力。使用 冷/热备用、检查点或主动-主动
  4. 无界数据集的窗口 API。例如,Apache Flink 中的流窗口。Spark 窗口函数。Apache Beam 中的窗口处理。

比较

框架StormStorm-tridentSparkFlink
模型原生微批处理微批处理原生
保证至少一次精确一次精确一次精确一次
容错能力记录确认记录确认检查点检查点
容错开销中等中等
延迟非常低
吞吐量中等

键值缓存

· 阅读需 4 分钟

KV 缓存就像一个巨大的哈希映射,用于减少数据访问的延迟,通常通过

  1. 将来自慢速且便宜介质的数据转移到快速且昂贵的介质上。
  2. 从基于树的数据结构的 O(log n) 索引转为基于哈希的数据结构的 O(1) 进行读写。

有各种缓存策略,如读穿/写穿(或写回)和旁路缓存。总体而言,互联网服务的读写比为 100:1 到 1000:1,因此我们通常会优化读取。

在分布式系统中,我们根据业务需求和上下文选择这些策略,并在 CAP 定理 的指导下进行选择。

常规模式

  • 读取
    • 读穿:客户端通过缓存层从数据库读取数据。当读取命中缓存时,缓存返回;否则,它从数据库获取数据,缓存后再返回值。
  • 写入
    • 写穿:客户端写入缓存,缓存更新数据库。缓存在完成数据库写入后返回。
    • 写后 / 写回:客户端写入缓存,缓存立即返回。在缓存写入的背后,缓存异步写入数据库。
    • 绕过写入:客户端直接写入数据库,绕过缓存。

旁路缓存模式

当缓存不支持原生的读穿和写穿操作,并且资源需求不可预测时,我们使用这种旁路缓存模式。

==在这种模式下仍然存在缓存变脏的可能性。== 当满足以下两个条件时,会发生这种情况:

  1. 读取数据库并更新缓存
  2. 更新数据库并删除缓存

缓存放在哪里?

  • 客户端
  • 独立层
  • 服务器端

如果数据量达到缓存容量怎么办?使用缓存替换策略

  • LRU(最近最少使用):检查时间,驱逐最近使用的条目,保留最近使用的条目。
  • LFU(最不常用):检查频率,驱逐最常用的条目,保留最常用的条目。
  • ARC(自适应替换缓存):其性能优于 LRU。通过同时保留最常用和频繁使用的条目,以及驱逐历史来实现。(保留 MRU + MFU + 驱逐历史。)

谁是缓存使用的王者?

Facebook TAO