系统设计面试的行家指南(中)(1)

简介: 系统设计面试的行家指南(中)(1)

九、设计

在这一章中,我们关注网络爬虫设计:一个有趣而经典的系统设计面试问题。

网络爬虫被称为机器人或蜘蛛。搜索引擎广泛使用它来发现 web 上新的或更新的内容。内容可以是网页、图像、视频、PDF 文件等。网络爬虫从收集一些网页开始,然后跟随这些网页上的链接来收集新的内容。图 9-1 显示了爬行过程的一个可视化例子。

爬虫有多种用途:

搜索引擎索引:这是最常见的用例。爬虫收集网页来为搜索引擎创建本地索引。例如,Googlebot 是谷歌搜索引擎背后的网络爬虫。

网络存档:这是从网络上收集信息以保存数据供将来使用的过程。例如,许多国家图书馆运行爬虫来存档网站。著名的例子是美国国会图书馆[1]和欧盟网络档案馆[2]。

Web 挖掘:Web 的爆炸式增长为数据挖掘带来了前所未有的机遇。Web 挖掘有助于从互联网上发现有用的知识。例如,顶级金融公司使用爬虫下载股东会议和年度报告,以了解关键的公司举措。

网络监控。这些爬虫帮助监控互联网上的版权和商标侵权行为。例如,Digimarc [3]利用爬虫来发现盗版作品和报告。

开发一个网络爬虫的复杂性取决于我们打算支持的规模。它可以是一个只需要几个小时就能完成的小型学校项目,也可以是一个需要专业工程团队不断改进的大型项目。由此,我们将在下面探讨尺度和特性来支持 。

步骤 1 -了解问题并确定设计范围

网络爬虫的基本算法很简单:

1。给定一组 URL,下载由这些 URL 寻址的所有网页。

2。从这些网页中提取网址

3。向要下载的 URL 列表中添加新的 URL。重复这三个步骤。

网络爬虫的工作真的像这个基本算法这么简单吗?不完全是。设计一个高度可扩展的网络爬虫是一项极其复杂的任务。任何人都不太可能在面试时间内设计出一个庞大的网络爬虫。在跳入设计之前,我们必须提出问题,了解需求,建立设计范围:

候选 : 爬虫的主要用途是什么?是用于搜索引擎索引,数据挖掘,还是其他?

面试官 : 搜索引擎索引。

候选 : 网络爬虫每月收集多少网页?

面试官:10 亿页。

候选 : 包含哪些内容类型?仅 HTML 还是 pdf 和图像等其他内容类型?

面试官 :只有 HTML。

候选 : 我们要考虑新增或编辑的网页吗?

面试官 : 是的,要考虑新增加或编辑的网页。

候选人 : 我们需要存储从 web 上抓取的 HTML 页面吗?

面试官 : 是的,最多 5 年

候选人 : 我们如何处理内容重复的网页?

面试官 : 内容重复的页面应忽略。

以上是你可以问面试官的一些问题。理解需求和澄清歧义是很重要的。即使你被要求设计一个像网络爬虫这样简单明了的产品,你和你的面试官可能也不会有相同的假设。

除了向你的面试官澄清功能之外,记下一个好的网络爬虫的以下特征也很重要

可扩展性:web 非常大。外面有数十亿的网页。

健壮性:网络充满陷阱。糟糕的 HTML,没有反应的服务器,崩溃,恶意链接等。都很常见。爬虫必须处理所有这些边缘情况。

礼貌:爬虫不要在短时间间隔内向一个网站提出太多请求。

可扩展性 :系统非常灵活,只需很小的改动就能支持新的内容类型。例如,如果我们将来想要抓取图像文件,我们应该不需要重新设计整个系统。

信封估算的背面

下面的估计是基于许多假设的,与面试官沟通以达成共识是很重要的。

假设每月有 10 亿个网页被下载。

QPS:30 天 / 24 小时 / 3600 秒 = 每秒 ~400 页

峰值 QPS = 2 * QPS = 800

假设平均网页大小为 500k。

10 亿页 x 500k = 每月 500 TB存储。如果你对数字存储单元不清楚,请再次阅读第二章的“2 的幂”一节。

假设数据存储五年,500 TB * 12 个月 * 5 年 = 30 PB。需要 30 PB 的存储空间来存储五年的内容。

第二步-提出高层次设计并获得认同

一旦明确了需求,我们就进入高层次的设计。受之前关于网页抓取的研究的启发[4] [5],我们提出了一个如图 9-2 所示的高级设计。

首先,我们探索每个设计组件,了解它们的功能。然后,我们一步一步地检查爬虫工作流。

种子网址

网络爬虫使用种子 URL 作为爬行过程的起点。例如,要从一所大学的网站抓取所有网页,选择种子 URL 的直观方法是使用该大学的域名。

为了抓取整个网络,我们需要在选择种子 URL 时有创意。一个好的种子 URL 是一个好的起点,爬虫可以利用它遍历尽可能多的链接。一般的策略是将整个 URL 空间分成更小的空间。第一种提出的方法是基于位置的,因为不同的国家可能有不同的流行网站。另一种方式是根据主题选择种子 URLs 例如,我们可以将 URL 空间划分为购物、运动、医疗保健等。种子 URL 选择是一个开放式问题。不指望你给出完美的答案。大声想出来。

URL 边界

大多数现代网络爬虫将抓取状态分为两种:待下载和已下载。存储要下载的 URL 的组件称为 URL Frontier。你可以称之为先进先出(FIFO)队列。有关 URL 边界的详细信息,请参考深入探讨。

HTML 下载程序

HTML 下载程序从互联网上下载网页。这些 URL 由 URL Frontier 提供。

DNS 解析器

要下载网页,必须将 URL 转换成 IP 地址。HTML 下载程序调用 DNS 解析器来获取 URL 的相应 IP 地址。例如,从 2019 年 3 月 5 日起,URL www.wikipedia.org 将转换为 IP 地址 198.35.26.96。

内容解析器

下载网页后,必须对其进行解析和验证,因为格式错误的网页会引发问题并浪费存储空间。 在爬行服务器中实现内容解析器会减慢爬行过程。因此,内容解析器是一个独立的组件。

看过的内容?

在线研究[6]显示,29%的网页是重复的内容,这可能导致相同的内容被多次存储。我们介绍“内容看过了吗?”数据结构来消除数据冗余并缩短处理时间。它有助于检测系统中先前存储的新内容。要比较两个 HTML 文档,我们可以逐字符比较。然而,这种方法既慢又耗时,尤其是当涉及数十亿个网页时。完成这项任务的有效方法是比较两个网页的哈希值[7]。

内容存储

它是一个存储 HTML 内容的存储系统。存储系统的选择取决于数据类型、数据大小、访问频率、生命周期等因素。磁盘和内存都要用。

大部分内容都存储在磁盘上,因为数据集太大,内存放不下。

流行内容被保存在内存中以减少延迟。

网址提取器

URL 提取器解析并提取 HTML 页面中的链接。图 9-3 显示了一个链接提取过程的例子。通过添加“https://en.wikipedia.org”前缀,相对路径被转换为绝对 URL。

URL 过滤器

URL 过滤器排除“黑名单”网站中的某些内容类型、文件扩展名、错误链接和 URL。

网址见过?

“网址看到了吗?”是一种数据结构,用于跟踪之前访问过的 URL 或已经在前沿访问过的 URL。"看到网址了吗?"有助于避免多次添加相同的 URL,因为这可能会增加服务器负载并导致潜在的无限循环。

布隆过滤器和哈希表是实现“URL 是否可见?”的常用技术组件。我们不会在这里讨论 bloom filter 和 hash 表的详细实现。有关更多信息,请参考参考资料[4] [8]。

网址存储

URL 存储存储已经访问过的 URL。

到目前为止,我们已经讨论了每个系统组件。接下来,我们将它们放在一起解释工作流程。

网络爬虫工作流程

为了更好地解释工作流程,在设计图中增加了顺序号,如图 9-4 所示。

步骤 1:将种子 URL 添加到 URL 边界

步骤 2: HTML 下载程序从 URL Frontier 获取一个 URL 列表。

第三步:HTML Downloader 从 DNS 解析器获取 URL 的 IP 地址,开始下载。

步骤 4:内容解析器解析 HTML 页面并检查页面是否格式错误。

步骤 5:在内容被解析和验证之后,它被传递给“内容是否被看到?”组件。

步骤 6:“内容可见”组件检查 HTML 页面是否已经在存储器中。

如果在存储中,这意味着不同 URL 中的相同内容已经被处理。在这种情况下,HTML 页面将被丢弃。

如果不在存储中,系统之前没有处理过相同的内容。内容被传递到链接提取器。

第 7 步:链接提取器从网页中提取链接。

步骤 8:提取的链接被传递给 URL 过滤器。

步骤 9:在链接被过滤后,它们被传递给“URL 是否可见?”组件。

步骤 10:“URL Seen”组件检查一个 URL 是否已经在存储器中,如果是,则它之前被处理过,并且不需要做任何事情。

步骤 11:如果一个 URL 以前没有被处理过,它被添加到 URL 边界。

步骤 3 -设计深度潜水

到目前为止,我们已经讨论了高层设计。接下来,我们将深入讨论最重要的建筑构件和技术:

深度优先搜索(DFS) vs 广度优先搜索(BFS)

网址前沿

HTML 下载工具

鲁棒性

扩展性

检测并避免有问题的内容

DFS 与 BFS 的比较

你可以把网络想象成一个有向图,网页作为节点,超链接(URL)作为边。爬行过程可以被视为从一个网页到另一个网页遍历有向图。两种常见的图遍历算法是 DFS 和 BFS。但是,DFS 通常不是一个好的选择,因为 DFS 的深度可能非常深。

BFS 通常由网络爬虫使用,并通过先进先出(FIFO)队列来实现。在 FIFO 队列中,URL 按照它们入队的顺序出队。然而,这种实现有两个问题:

来自同一个网页的大多数链接都链接回同一个主机。在图 9-5 中,wikipedia.com 的所有链接都是内部链接,使得爬虫忙于处理来自同一主机(wikipedia.com)的 URL。当爬虫试图并行下载网页时,维基百科服务器会被请求淹没。这被认为是“不礼貌的”。


标准 BFS 不考虑 URL 的优先级。网络很大,不是每个页面都有相同的质量和重要性。因此,我们可能希望根据 URL 的页面排名、web 流量、更新频率等来确定它们的优先级。

URL 边界

URL frontier 有助于解决这些问题 。URL 边界是存储要下载的 URL 的数据结构。URL 边界是确保礼貌、URL 优先级和新鲜度的重要组成部分。参考资料[5] [9]中提到了几篇值得注意的关于 URL 边界的论文。这些论文的研究结果如下:

礼貌

一般来说,网络爬虫应该避免在短时间内向同一个主机服务器发送太多请求。发送过多的请求被认为是“不礼貌的”,甚至会被视为拒绝服务(DOS)攻击。例如,在没有任何约束的情况下,爬虫每秒钟可以向同一个网站发送数千个请求。这可能会使 web 服务器不堪重负。

加强礼貌的总体思路是从同一个主机上一次下载一个页面。可以在两个下载任务之间添加延迟。通过维护从网站主机名到下载(工作)线程映射来实现礼貌约束。每个下载器线程都有一个单独的 FIFO 队列,并且只下载从该队列获得的 URL。图 9-6 显示了管理礼貌的设计。

队列路由器:它确保每个队列(b1,b2,… bn)只包含来自同一个主机的 URL。

映射表:将每台主机映射到一个队列。

FIFO 队列 b1b2bn:每个队列包含来自同一主机的 URL。

队列选择器:每个工作线程被映射到一个 FIFO 队列,它只从那个队列下载 URL。队列选择逻辑由队列选择器完成。

工作线程 1 到 n 一个工作线程从同一个主机上一个接一个的下载网页。可以在两个下载任务之间添加延迟。

优先级

来自苹果产品论坛的随机帖子与苹果主页上的帖子具有非常不同的权重。尽管它们都有“Apple”关键字,但对于爬虫来说,首先爬取 Apple 主页是明智的。

我们根据有用性对 URL 进行优先排序,有用性可以通过 PageRank [10]、网站流量、更新频率等来衡量。“优先排序器”是处理 URL 优先排序的组件。请参考参考资料[5] [10]以深入了解这一概念。

图 9-7 显示了管理 URL 优先级的设计。

优先级排序器:它将 URL 作为输入并计算优先级。

队列 f1 到 fn:每个队列都有一个指定的优先级。具有高优先级的队列以较高的概率被选择。

队列选择器:随机选择一个偏向高优先级队列的队列。

图 9-8 展示了 URL 边界设计,它包含两个模块:

前排队列:管理优先级

后排:管理礼貌

新鲜度

网页不断地被添加、删除和编辑。网络爬虫必须定期重新抓取下载的页面,以保持我们的数据集新鲜。重新搜索所有的 URL 既耗时又耗费资源。下面列出了一些优化新鲜度的策略:

基于网页更新历史重新抓取。

优先处理网址,首先更频繁地重新抓取重要网页。

URL 边界的存储

在搜索引擎的真实世界抓取中,前沿的 URL 数量可能是数亿个[4]。把所有东西都放在内存中既不耐用也不可伸缩。将所有东西都保存在磁盘中也是不可取的,因为磁盘很慢;这很容易成为爬行的瓶颈。

我们采用了混合方法。大多数 URL 都存储在磁盘上,所以存储空间不是问题。为了降低从磁盘读取和向磁盘写入的成本,我们在内存中维护用于入队/出队操作的缓冲区。缓冲区中的数据会定期写入磁盘。

HTML 下载程序

HTML 下载器使用 HTTP 协议从互联网下载网页。在讨论 HTML 下载器之前,我们先来看看 Robots 排除协议。

Robots.txt

Robots.txt,称为 Robots Exclusion Protocol,是网站用来与爬虫通信的标准。它指定允许爬虫下载哪些页面。在尝试对网站进行爬网之前,爬网程序应首先检查其对应的 robots.txt 并遵循其规则。

为了避免重复下载 robots.txt 文件,我们缓存了该文件的结果。文件会定期下载并保存到缓存中。这里有一段来自 https://www.amazon.com/robots.txtrobots.txt 文件,其中一些目录如 creatorhub 是谷歌机器人不允许的。

User Agent: Googlebot
Disallow: /creatorhub/*
Disallow: /rss/people/*/reviews
Disallow: /gp/pdp/rss/*/reviews
Disallow: /gp/CDP/会员评论/
Disallow: /gp/aw/cr/

除了 robots.txt,性能优化是我们将为 HTML 下载器介绍的另一个重要概念。

性能优化

下面是 HTML 下载程序的性能优化列表。

1。分布式抓取

为了实现高性能,爬行作业被分布到多个服务器上,并且每个服务器运行多个线程。URL 空间被分割成更小的部分;因此,每个下载器负责 URL 的一个子集。图 9-9 显示了一个分布式抓取的例子。

2。缓存 DNS 解析器

DNS 解析器是爬虫的瓶颈,因为由于许多 DNS 接口的同步性质,DNS 请求可能需要时间。DNS 响应时间从 10 毫秒到 200 毫秒不等。一旦 crawler 线程执行了对 DNS 的请求,其他线程就会被阻塞,直到第一个请求完成。维护我们的 DNS 缓存以避免频繁调用 DNS 是一种有效的速度优化技术。我们的 DNS 缓存保存域名到 IP 地址的映射,并由 cron 作业定期更新。

3。地点

在地理上分布爬行服务器。当爬网服务器离网站主机越近,爬网程序的下载时间就越快。设计局部性适用于大多数系统组件:爬网服务器、缓存、队列、存储等。

4。短暂超时

一些网络服务器响应缓慢或者根本没有响应。为了避免长时间等待,规定了最大等待时间。如果主机在预定义的时间内没有响应,crawler 将停止作业并搜索其他一些页面。

鲁棒性

除了性能优化,健壮性也是一个重要的考虑因素。我们提出了几种提高系统鲁棒性的方法:

一致哈希:这有助于在下载者之间分配负载。可以使用一致哈希来添加或删除新的下载器服务器。更多细节请参考第五章:设计一致哈希。

保存抓取状态和数据:为了防止失败,抓取状态和数据被写入存储系统。通过加载保存的状态和数据,可以轻松重启中断的爬网。

异常处理:在大规模系统中,错误是不可避免的,也是常见的。爬虫必须在不使系统崩溃的情况下优雅地处理异常。

数据验证:这是防止系统出错的重要措施。

扩展性

随着几乎每个系统的发展,设计目标之一是使系统足够灵活以支持新的内容类型。爬行器可以通过插入新模块来扩展。图 9-10 显示了如何添加新模块。

插入 PNG 下载器模块,下载 PNG 文件。

新增网络监控模块,监控网络,防止侵犯版权和商标。

检测并避免有问题的内容

本节讨论检测和预防多余的、 无意义的或有害的内容。

1。冗余内容

如前所述,近 30%的网页是重复的。哈希或校验和有助于检测重复[11]。

2。蜘蛛陷阱

蜘蛛陷阱是一个网页,它会使爬虫陷入无限循环。例如,一个无限深的目录结构如下所示:www.spidertrapexample.com/foo/bar/foo/bar/foo/bar/…

通过设置 URL 的最大长度可以避免这种蜘蛛陷阱。然而,不存在一种通用的解决方案来检测蜘蛛陷阱。包含蜘蛛陷阱的网站很容易识别,因为在此类网站上发现的网页异常多。很难开发自动算法来避免蜘蛛陷阱;但是,用户可以手动验证和识别蜘蛛陷阱,并从 crawler 中排除这些网站或应用一些定制的 URL 过滤器。

3。数据噪声

有些内容几乎没有价值,例如广告、代码片段、垃圾网址等。这些内容对爬网程序没有用,应该尽可能排除。

第四步——总结

在这一章中,我们首先讨论了优秀爬虫的特征:可伸缩性、礼貌性、可扩展性和健壮性。然后,我们提出了一个设计方案,并讨论了关键部件。构建一个可伸缩的网络爬虫并不是一个简单的任务,因为网络非常庞大,充满了陷阱。尽管我们已经涵盖了许多主题,但我们仍然错过了许多相关的话题:

服务器端渲染:许多网站使用 JavaScript、AJAX 等脚本动态生成链接。如果我们直接下载和解析网页,我们将无法检索动态生成的链接。为了解决这个问题,我们在解析页面之前先执行服务器端渲染(也称为动态渲染)[12]。

过滤掉不想要的页面:在有限的存储容量和抓取资源下,反垃圾邮件组件有利于过滤掉低质量和垃圾页面[13] [14]。

数据库复制和分片:复制和分片等技术用于提高数据层的可用性、可伸缩性和可靠性。

横向扩展:对于大规模的抓取,需要数百甚至数千台服务器来执行下载任务。关键是保持服务器无状态。

可用性、一致性和可靠性:这些概念是任何大型系统成功的核心。我们在第一章中详细讨论了这些概念。请回忆一下这些话题。

分析:收集和分析数据是任何系统的重要组成部分,因为数据是微调的关键因素。

祝贺你走到这一步!现在给自己一个鼓励。干得好!

参考资料

[1] US Library of Congress: https://www.loc.gov/websites/
[2] EU Web Archive: http://data.europa.eu/webarchive
[3] Digimarc: https://www.digimarc.com/products/digimarc-services/piracy-intelligence
[4] Heydon A., Najork M. Mercator: A scalable, extensible web crawler World Wide Web, 2 (4) (1999), pp. 219-229
[5] By Christopher Olston, Marc Najork: Web Crawling. http://infolab.stanford.edu/~olston/publications/crawling_survey.pdf
[6] 29% Of Sites Face Duplicate Content Issues: https://tinyurl.com/y6tmh55y
[7] Rabin M.O., et al. Fingerprinting by random polynomials Center for Research in Computing Techn., Aiken Computation Laboratory, Univ. (1981)
[8] B. H. Bloom, “Space/time trade-offs in hash coding with allowable errors,”
Communications of the ACM, vol. 13, no. 7, pp. 422–426, 1970.
[9] Donald J. Patterson, Web Crawling:
https://www.ics.uci.edu/~lopes/teaching/cs221W12/slides/Lecture05.pdf
[10] L. Page, S. Brin, R. Motwani, and T. Winograd, “The PageRank citation
ranking: Bringing order to the web,” Technical Report, Stanford University,
1998.
[11] Burton Bloom. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7), pages 422--426, July 1970.
[12] Google Dynamic Rendering: https://developers.google.com/search/docs/guides/dynamic-rendering
[13] T. Urvoy, T. Lavergne, and P. Filoche, “Tracking web spam with hidden style similarity,” in Proceedings of the 2nd International Workshop on Adversarial Information Retrieval on the Web, 2006.
[14] H.-T. Lee, D. Leonard, X. Wang, and D. Loguinov, “IRLbot: Scaling to 6 billion pages and beyond,” in Proceedings of the 17th International World Wide Web Conference, 2008.

十、设计通知系统

近年来,通知系统已经成为许多应用程序中非常流行的功能。通知提醒用户重要信息,如突发新闻、产品更新、事件、产品等。它已经成为我们日常生活中不可或缺的一部分。在这一章中,你被要求设计一个通知系统。

通知不仅仅是移动推送通知。三种通知格式是:移动推送通知、SMS 消息和电子邮件。图 10-1 显示了这些通知的一个例子。

第一步——了解问题并确定设计范围

构建一个每天发送数百万条通知的可扩展系统并不是一件容易的事情。它需要对通知生态系统有深刻的理解。面试问题特意设计成开放式的,模棱两可的,你有责任提问明确要求。

候选人 :系统支持什么类型的通知?

面试官 :推送通知、短信、邮件。

候选: 是实时系统吗?

面试官: 姑且说是软实时系统吧。我们希望用户尽快收到通知。但是,如果系统工作负载较高,稍微延迟是可以接受的。

候选: 支持哪些设备?

面试官: iOS 设备,android 设备,以及笔记本电脑/台式机。

候选: 什么触发通知?

面试官: 客户端应用程序可以触发通知。它们也可以在服务器端进行调度。

候选人: 用户可以选择退出吗?

面试官: 是的,选择退出的用户将不再收到通知。

候选人: 每天发出多少通知?

面试官:1000 万条移动推送通知,100 万条短信,500 万封邮件。

第二步——提出高水平的设计并获得认同

本节展示了支持各种通知类型的高级设计:iOS 推送通知、Android 推送通知、短信和电子邮件。其结构如下:

不同类型的通知

联系信息采集流程

通知收发流程

不同类型的通知

我们先来看看每种通知类型在高层次上是如何工作的。

iOS 推送通知

我们主要需要三个组件来发送 iOS 推送通知:

提供者。提供商构建通知请求并将其发送给苹果推送通知服务(APNS)。为了构造推送通知,提供商提供以下数据:

设备令牌:这是用于发送推送通知的唯一标识符。

有效负载:这是一个 JSON 字典,包含通知的有效负载。下面是一个例子:

APNS:这是苹果提供的一项远程服务,用于向 iOS 设备传播推送通知。

iOS 设备:是终端客户端,接收推送通知。

安卓推送通知

Android 采用了类似的通知流程。Firebase Cloud Messaging (FCM)通常用于向 android 设备发送推送通知,而不是使用 APN。

短信

对于短信,通常使用 Twilio [1]、Nexmo [2]等第三方短信服务。大部分是商业服务。

电子邮件

虽然公司可以建立自己的电子邮件服务器,但许多公司选择商业电子邮件服务。Sendgrid [3]和 Mailchimp [4]是最受欢迎的电子邮件服务,它们提供更好的投递率和数据分析。

图 10-6 显示了包含所有第三方服务后的设计。

联系信息收集流程

为了发送通知,我们需要收集移动设备令牌、电话号码或电子邮件地址。如图 10-7 所示,当用户安装我们的应用程序或者第一次注册时,API 服务器收集用户的联系信息并存储在数据库中。

图 10-8 显示了存储联系信息的简化数据库表。电子邮件地址和电话号码存储在 用户 表中,而设备令牌存储在 设备 表中。一个用户可以有多个设备,这表明推送通知可以被发送到所有的用户设备。

通知发送/接收流程

我们将首先展示最初的设计;然后,提出一些优化。

高–水平设计

图 10-9 显示了设计,每个系统组件解释如下。

服务 1 到 N :服务可以是微服务、cron 作业,也可以是触发通知发送事件的分布式系统。例如,一个账单服务发送电子邮件提醒客户他们的到期付款,或者一个购物网站通过短信告诉客户他们的包裹将于明天送达。

通知系统 :通知系统是发送/接收通知的核心。从简单的开始,只使用一个通知服务器。它为服务 1 到 N 提供 API,并为第三方服务构建通知有效负载。

第三方服务: 第三方服务负责向用户发送通知。在与第三方服务集成的同时,我们需要额外关注可扩展性。良好的可扩展性意味着一个灵活的系统,可以很容易地插入或拔出第三方服务。另一个重要的考虑是,第三方服务可能在新的市场或未来不可用。例如,FCM 在中国是不可用的。因此,替代的第三方服务,如 Jpush,PushY 等,在那里使用。

iOS、Android、短信、电子邮件 :用户在其设备上接收通知。

在本设计中发现了三个问题:

单点故障(SPOF):单一通知服务器是指 SPOF。

难以扩展:通知系统在一台服务器上处理与推送通知相关的一切。独立扩展数据库、缓存和不同的通知处理组件是一项挑战。

性能瓶颈:处理和发送通知可能是资源密集型的。例如,构建 HTML 页面和等待第三方服务的响应可能需要时间。在一个系统中处理所有事情会导致系统过载,尤其是在高峰时段。

高级设计(改进)

在列举了初始设计中的挑战后,我们对设计进行了如下改进:

将数据库和缓存移出通知服务器。

添加更多通知服务器并设置自动水平缩放。

引入消息队列来分离系统组件。

图 10-10 显示了改进的高层设计。

浏览上图的最佳方式是从左到右:

服务 1 到 N :它们代表通过通知服务器提供的 API 发送通知的不同服务。

通知服务器 :提供以下功能:

为发送通知的服务提供 API。这些 API 只能在内部访问或由经过验证的客户端访问,以防止垃圾邮件。

进行基本验证,以验证电子邮件、电话号码等。

查询数据库或缓存以获取呈现通知所需的数据。

将通知数据放入消息队列进行并行处理。

下面是发送电子邮件的 API 示例:

职务

请求体

缓存 :缓存用户信息、设备信息、通知模板。

DB :存储用户、通知、设置等数据。

消息队列 :它们移除组件之间的依赖关系。当要发送大量通知时,消息队列充当缓冲区。每种通知类型都分配有不同的消息队列,因此一个第三方服务的中断不会影响其他通知类型。

Workers:Workers 是从消息队列中拉出通知事件并发送给相应的第三方服务的服务器列表。

第三方服务 :已在初步设计中说明。

iOS、Android、短信、邮箱 :在初步设计中已经说明。

接下来,让我们看看每个组件如何协同工作来发送通知:

1。服务调用通知服务器提供的 API 来发送通知。

2。通知服务器从缓存或数据库中获取元数据,如用户信息、设备令牌和通知设置。

3。通知事件被发送到相应的队列进行处理。例如,iOS 推送通知事件被发送到 iOS PN 队列。

4。工作人员从消息队列中提取通知事件。

5。工作人员向第三方服务发送通知。

6。第三方服务向用户设备发送通知。

步骤 3 -设计深度潜水

在概要设计中,我们讨论了不同类型的通知、联系信息收集流程和通知发送/接收流程。我们将深入探讨以下内容:

可靠性。

附加组件和考虑事项:通知模板、通知设置、速率限制、重试机制、推送通知中的安全性、监控排队通知和事件跟踪。

更新设计。

可靠性

在分布式环境中设计通知系统时,我们必须回答几个重要的可靠性问题。

如何防止数据丢失?

通知系统中最重要的要求之一是不能丢失数据。通知通常可以延迟或重新排序,但永远不会丢失。为了满足这一要求,通知系统将通知数据保存在数据库中,并实现重试机制。如图 10-11 所示,包含通知日志数据库是为了数据持久化。

收件人会收到一次通知吗?

简短的回答是否定的。尽管大多数情况下通知只发送一次,但分布式的本质可能会导致重复的通知。为了减少重复的发生,我们引入了重复数据删除机制,并仔细处理每个故障情况。下面是一个简单的重复数据删除逻辑:

当一个通知事件第一次到达时,我们通过检查事件 ID 来检查它以前是否被看到过。如果是之前看到的,就丢弃。否则,我们将发出通知。感兴趣的读者可以参考参考资料[5],探究为什么我们不能一次交货。

附加组件和注意事项

我们已经讨论了如何收集用户联系信息、发送和接收通知。通知系统远不止于此。这里我们讨论其他组件,包括模板重用、通知设置、事件跟踪、系统监控、速率限制等。

通知模板

大型通知系统每天会发出数百万条通知,其中许多通知都遵循相似的格式。引入通知模板是为了避免从头开始构建每个通知。通知模板是一种预先格式化的通知,通过自定义参数、样式、跟踪链接等来创建您的独特通知。下面是推送通知的一个示例模板。

正文:

你梦见了它。我们敢于挑战。[项目名称]已恢复—仅到[日期]为止。

CTA:

现在订购。或者,保存我的【物品名称】

使用通知模板的好处包括保持格式一致、减少误差和节省时间。

通知设置

用户通常每天会收到太多的通知,他们很容易感到不知所措。因此,许多网站和应用程序允许用户对通知设置进行精细控制。该信息存储在通知设置表中,具有以下字段:

用户标识 bigInt

channel varchar #推送通知、电子邮件或短信

opt_in boolean # opt-in 接收通知

在向用户发送任何通知之前,我们首先检查用户是否选择接收此类通知。

速率限制

为了避免过多的通知让用户不知所措,我们可以限制用户可以接收的通知数量。这很重要,因为如果我们发送得太频繁,接收者可能会完全关闭通知。

重试机制

当第三方服务未能发送通知时,该通知将被添加到消息队列中进行重试。如果问题仍然存在,将向开发人员发出警告。

推送通知中的安全性

对于 iOS 或 Android 应用,appKey 和 appSecret 用于保护推送通知 API[6]。只有经过认证或验证的客户端才允许使用我们的 API 发送推送通知。感兴趣的用户可以参考参考资料[6]。

监控排队通知

要监控的一个关键指标是排队通知的总数。如果数量很大,则工作线程处理通知事件的速度不够快。为了避免通知传递的延迟,需要更多的工人。图 10-12 显示了一个待处理的排队消息的例子。

图 10-12

事件跟踪

打开率、点击率和参与度等通知指标对于了解客户行为非常重要。分析服务实现事件跟踪。通知系统和分析服务之间的集成通常是必需的。图 10-13 显示了出于分析目的可能被跟踪的事件的例子。

更新设计

图 10-14 显示了更新后的通知系统设计。

与之前的设计相比,本次设计增加了许多新部件。

通知服务器配备了两个更关键的功能:身份验证和速率限制。

我们还增加了重试机制来处理通知失败。如果系统未能发送通知,它们将被放回消息队列,工作人员将重试预定义的次数。

此外,通知模板提供了一致且高效的通知创建流程。

最后,增加了监控和跟踪系统,用于系统健康检查和未来改进。

步骤 4 -总结

通知是必不可少的,因为它们让我们了解重要的信息。它可能是网飞上关于你最喜欢的电影的推送通知,一封关于新产品折扣的电子邮件,或者一条关于你的网上购物支付确认的消息。

在本章中,我们描述了支持多种通知格式的可扩展通知系统的设计:推送通知、SMS 消息和电子邮件。我们采用消息队列来分离系统组件。

除了高级设计,我们还深入研究了更多组件和优化。

可靠性:我们提出了一个健壮的重试机制来最小化故障率。

安全性:AppKey/appSecret 对用于确保只有经过验证的客户端才能发送通知。

跟踪和监控:这些在通知流的任何阶段都可以实现,以捕获重要的统计数据。

尊重用户设置:用户可以选择不接收通知。我们的系统在发送通知前会先检查用户设置。

速率限制:用户会喜欢对他们收到的通知数量设置频率上限。

祝贺你走到这一步!现在给自己一个鼓励。干得好!

参考资料

[1] Twilio SMS:  https://www.twilio.com/sms
[2] Nexmo SMS: https://www.nexmo.com/products/sms
[3] Sendgrid: https://sendgrid.com/
[4] Mailchimp: https://mailchimp.com/
[5] You Cannot Have Exactly-Once Delivery: https://bravenewgeek.com/you-cannot-have-exactly-once-delivery/
[6] Security in Push Notifications: https://cloud.ibm.com/docs/services/mobilepush?topic=mobile-pushnotification-security-in-push-notifications
[7] RadditMQ: https://bit.ly/2sotIa6


系统设计面试的行家指南(中)(2)https://developer.aliyun.com/article/1481940

相关文章
|
3天前
|
数据采集 消息中间件 监控
Flume数据采集系统设计与配置实战:面试经验与必备知识点解析
【4月更文挑战第9天】本文深入探讨Apache Flume的数据采集系统设计,涵盖Flume Agent、Source、Channel、Sink的核心概念及其配置实战。通过实例展示了文件日志收集、网络数据接收、命令行实时数据捕获等场景。此外,还讨论了Flume与同类工具的对比、实际项目挑战及解决方案,以及未来发展趋势。提供配置示例帮助理解Flume在数据集成、日志收集中的应用,为面试准备提供扎实的理论与实践支持。
38 1
|
8月前
|
消息中间件 缓存 监控
GitHub上获赞上万的阿里亿级并发系统设计手册,让你吊打面试官
金九银十已经接近尾声,很多没有在这个时间段找到工作的小伙伴已经开始备战秋招了,在这里给大家分享一份阿里10亿级并发系统设计手册,专门给没有系统设计相关经验的小伙伴应对面试用的,下面将这么手册的内容以截图的形式展示给大家,有需要的小伙伴可以文末获取↓↓↓此份手册又份为六个部分,基础篇、数据库篇、缓存篇、消息队列篇、分布式服务篇、维护篇、实战篇共计328页 目录总览 基础篇 高并发代表着大流量,高并发系统设计的魅力就在于我们能够凭借自己的聪明才智设计巧妙的方案,从而抵抗巨大流量的冲击,带给用户更好的使用体验。这些方案好似能操纵流量,让流量更加平稳得被系统中的服务和组件处理。
GitHub上获赞上万的阿里亿级并发系统设计手册,让你吊打面试官
|
3天前
|
存储 缓存 移动开发
系统设计面试的行家指南(上)(3)
系统设计面试的行家指南(上)(3)
43 0
|
3天前
|
存储 缓存 算法
系统设计面试的行家指南(上)(2)
系统设计面试的行家指南(上)(2)
48 1
|
3天前
|
存储 缓存 数据库
系统设计面试的行家指南(上)(1)
系统设计面试的行家指南(上)(1)
54 0
|
2天前
|
Java 程序员
Java this关键字详解(3种用法),Java程序员面试必备的知识点
Java this关键字详解(3种用法),Java程序员面试必备的知识点
|
2天前
|
缓存 安全 Java
7张图带你轻松理解Java 线程安全,java缓存机制面试
7张图带你轻松理解Java 线程安全,java缓存机制面试
|
1天前
|
移动开发 前端开发 JavaScript
Java和web前端,IT新人该如何选择?,2024年最新Web前端内存优化面试
Java和web前端,IT新人该如何选择?,2024年最新Web前端内存优化面试
|
1天前
|
安全 Java 数据库
Spring boot 入门教程-Oauth2,java面试基础题核心
Spring boot 入门教程-Oauth2,java面试基础题核心
|
1天前
|
Java
Java中int[]与Integer[]相互转化的方法,java基础知识面试重点总结
Java中int[]与Integer[]相互转化的方法,java基础知识面试重点总结