42 篇博文 含有标签「system-design」

为什么有这种框架？​

• 为了在更短的时间内处理更多的数据。
• 统一处理分布式系统中的容错问题。
• 将任务简化抽象以应对多变的业务要求。
• 分别适用于有界数据集（批处理）和无界数据集（流处理）。

批处理与流处理的发展史简介​

1. Hadoop 与 MapReduce。谷歌让批处理在一个分布式系统中像 MapRduceresult = pairs.map((pair) => (morePairs)).reduce(somePairs => lessPairs)一样简单。
2. Apache Storm 与有向图拓扑结构。MapReduce 不能很好地表示迭代算法。因此，内森·马兹（Nathan Marz）将流处理抽象成一个由 spouts 和 bolts 组件构成的图结构。
3. Spark 内存计算。辛湜（Reynold Xin）指出 Spark 在处理相同数据的时候比 Hadoop 少使用十倍机器的同时速度却快三倍
4. 基于 Millwheel 和 FlumeJava 的谷歌数据流（Google Dataflow）。谷歌使用窗口化API同时支持批处理与流处理。

等等...那么为什么 Flink 变得如此热门？​

1. Flink 快速采纳了 ==Google Dataflow== 以及 Apache Beam 的编程模式。
2. Flink 对 Chandy-Lamport checkpointing 算法的高效实现。

这些框架​

架构选择​

若要用商业机器来满足以上的需求，有这些热门的分布式系统架构……

• master-slave（中心化的）：Apache Storm + zookeeper， Apache Samza + YARN
• P2P（去中心化的）：Apache s4

功能​

1. DAG Topology 用来迭代处理 -例如Spark 中的 GraphX， Apache Storm 中的 topologies， Flink 中的 DataStream API。
2. 交付保证 (Delivery Guarantees)。如何确保节点与节点之间数据交付的可靠性？至少一次 / 至多一次 / 一次。
3. 容错性。使用cold/warm/hot standby, checkpointing 或者 active-active 来实现容错。
4. 无界数据集的窗口化API。例如 Apache 的流式窗口。Spark 的Window函数。Apache Beam 的窗口化。

不同架构的区别对照表​

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

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

用户满意度 = 函数(内容, 用户画像, 上下文)

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 可以是主题、实体、来源等。

数据依赖​

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

免责声明：以下所有内容均来自公共资源或纯粹原创。 这里不包含优步的涉密内容。

要求​

• 为全球的交通运输市场提供服务
• 大规模的实时调度
• 后端设计

架构​

为何要微服务？​

==Conway定律== 软件的系统结构会对应企业的组织结构。

结合单体 ==代码库== 和微服务可以同时利用两者的长处.

调度服务​

• 由geohash提供一致的哈希地址
• 数据在内存中是瞬态的，因此不需要复制. (CAP: AP高于CP)
• 分片中使用单线程或者锁，以防止双重调度

支付服务​

==关键是要有异步设计==, 因为跨多个系统的ACID交易支付系统通常具有非常长的延迟.

• 利用事件队列
• 支付接口集成 Braintree, PayPal, Card.io, Alipay 等
• 通过详尽的 log 来记录所有 event
• 使用具有等幂性、指数退避和随机抖动的API

用户档案服务和行程记录服务​

• 使用缓存降低延迟
• 随着 1) 支持更多的国家和地区 2) 用户角色（司机，骑手，餐馆老板，食客等）逐渐增加，为这些用户提供用户档案服务也面临着巨大的挑战。

通知推送服务​

• 苹果通知推送服务 (不可靠)
• 谷歌云消息服务GCM （它可以检测到是否成功递送) 或者
• 短信服务通常更可靠

我们为什么要在架构上费心思？​

答案是：为了减少在每做一个功能的时候所耗费的人力资源。

移动开发人员会在以下三个层面上评估一个架构的好坏：

1. 各个功能分区的职责分配是否均衡
2. 是否具有易测试性
3. 是否易于使用和维护

紧耦合MVC​

举一个例子，在一个多页面的网页Web应用程序中，当你点击一个链接导航至其他页面的时候，该页面就会被全部重新加载。该架构的问题在于视图（View）与控制器（Controller）和模型（Model）是紧密耦合的。

Cocoa MVC​

Cocoa MVC 是苹果公司建议iOS开发者使用的架构。理论上来说，该架构可以通过控制器（Controller）将模型（Model）与视图（View）剥离开。

然而，在实际操作过程中，Cocoa MVC 鼓励大规模视图控制器的使用，最终使得视图控制器完成所有操作。

尽管测试这样的耦合大规模视图控制器是十分困难的，然而在开发速度方面，Cocoa MVC是现有的这些选择里面表现最好的。

MVP​

在MVP中，Presenter与视图控制器（view controller）的生命周期没有任何关系，视图可以很轻易地被取代。我们可以认为UIViewController实际上就是视图（View）。

还有另外一种类型的MVP：带有数据绑定的MVP。如下图所示，视图（View）与模型（Model）和控制器（Controller）是紧密耦合的。

MVVM​

MVVM与MVP相似不过MVVM绑定的是视图（View）与视图模型（View Model）。

VIPER​

不同于MV(X)的三层结构，VIPER具有五层结构（VIPER View, Interactor, Presenter, Entity, 和 Routing）。这样的结构可以很好地进行职责分配但是其维护性较差。

相较于MV(X)，VIPER有下列不同点：

1. Model 的逻辑处理转移到了 Interactor 上，这样一来，Entities 没有逻辑，只是纯粹的保存数据的结构。
2. ==UI相关的业务逻辑分在Presenter中，数据修改功能分在Interactor中==。
3. VIPER为实现模块间的跳转功能引入了路由模块 Router 。

为什么需要这样一个协议？​

使用HTTP直播流的移动视频播放服务有以下问题：

1. ==手机的内存和外存有限==。
2. 受制于不稳定的网络连接以及不同的带宽，需要==在传输过程中动态调整传输视频的质量==。

解决方法​

1. 服务器层面：在典型的设置中，编码硬件接受音视频输入，将其编码为H.264格式的视频和ACC格式的音频，然后将他们以MPEG-2格式流输出。
   1. 其后通过一个软件分流器将原始输出流分割为一系列短媒体文件（长度可能为10s的.ts文件）。
   2. 分流器同时也会维护一个包含所有媒体文件列表的索引文件（.m3u8格式）。
   3. 将以上步骤生成的媒体文件和索引文件发布在网络服务器上。
2. 客户端层面：客户端读取索引，然后向服务器顺序请求所需要的媒体文件，并且流畅地将各个短媒体文件的内容播放出来。

架构​

为什么 Facebook 要自己做图片存储？​

• PB级别的Blob数据量
• 传统的基于NFS的设计（每个图像存储为文件）都存在元数据瓶颈：庞大的元数据严重限制了元数据命中率。
  • 以下是细节解释：

对于图片应用程序，图片的权限等大多数元数据是无用的，从而浪费了存储空间。然而，更大的开销在于，必须将文件的元数据从磁盘读入内存中才能找到文件本身。虽然对于小规模存储来说这微不足道，但当乘以数十亿的照片和数PB的数据时，那么访问元数据将是吞吐量的瓶颈。

解决方案​

通过把数以十万计的图像聚集到单个Haystack存储文件中，从而消除了元数据负荷。

结构​

数据布局​

索引文件（用于快速加载内存）+ 包含很多图片的haystack存储文件。

索引文件布局

储存文件

CRUD操作​

• 增: 写入存储文件，然后==异步==写入索引文件，因为建立索引并不是关键的步骤。
• 删: 通过在标志字段中标记已删除的位来进行软删除。通过紧凑操作执行硬删除。
• 改: 在更新时，只能追加 (append-only)，如果遇到了重复的键，应用程序可以选择具有最大偏移量的键去改和读。
• 查: 读取操作（偏移量，健，备用键，Cookie 以及数据大小）

用例​

上传

下载

设计一个系统，可以将用户给的网址变成短网址，用户使用这些短网址可以访问他们原来给的网址（下面简称长网址）。描述这个系统是怎么运作的，需包括但不限于下面的问题：怎么分配短网址？怎么存储短网址和长网址的映射关系？怎么实现跳转服务？怎么存储访问数据？

假设：在一开始的问题描述中不包含这些假设。一个优秀的面试者在得到一个具体设计的时候会问关于系统规模的问题。

• 长网址的域名大概有上万个
• 新的长网址流量大概是 10,000,000/天 （100/秒）
• 使用短网址访问长网址的跳转服务的流量大概是 10B/天 （100,000/秒）
• 提醒面试者这些是平均数字 - 在一些高峰期的时候这些数字会大很多（一种时间导致的高峰期，比如用户刚工作完回家的时候， 另一种是事件导致的高峰期，比如春节联欢晚会的时候）
• 最近的数据（比如今天的数据）应该被提前收集好，并且在用户想要看的时候可以在五分钟内得到。
• 每天计算历史数据

假设​

每天有1B新网址，100B的短网址访问 短网址越短越好 数据的展示（实时/每天/每个月/每年）

网址编码​

http://blog.codinghorror.com/url-shortening-hashes-in-practice/

方法1. md5(128位，16个16进制数字，冲突，生日悖论，2^(n/2) = 2^64) 再短一些？（64位，8个16进制数字，冲突 2^32）, 64进制。

• 优点：哈希比较简单 而且 易于横向拓展。
• 缺点：太长，怎么去处理过期的网址？

方法2. 分布式的序号生成器。(62进制: az, AZ, 0~9, 62种字符, 62^7), 分区：每个节点包含一些序号。

• 优点：容易淘汰过期的网址，网址更短
• 缺点：不同分区之间的协调（zookeeper)

键值（KV）存储​

MySQL(10k 每秒访问量，慢，没有关系不需要关系型数据库)，键值（100k 每秒访问量，Redis, Memcached）

一个优秀的面试者会问关于短网址的预期使用期限，设计一套系统可以自动清理已经过期的短网址。

跟进​

问题：怎么生成短网址？

• 一个差的面试者 会提议用一个id生成器（单点故障）或者要在每个id生成的时候需要id生成器之间协同合作。 举例，使用自动增值的主键（auto-increment primary key）的数据库。
• 一个可以接受的面试者 会提议用md5，或者一些UUID生成器可以在一些结点上自己生成id的。这些方法可以在分布式系统上生成不冲突的ID，所以可以生产大量的短网址。
• 一个优秀的面试者 会设计一个方法利用一些id生成器，每个生成器先从中央协调器（例如ZooKeeper）保留一块id序列，这些id生成器可以单独从他们的id序列中分配id，有必要的时候在自己的id序列中做一些清理。

问题：怎么存储长网址和短网址之间的映射关系？

• 一个差的面试者 会建议使用一个单一的，非分布式，非关系型的数据库。它只是一个单纯的键值数据库。
• 一个优秀的面试者 会建议用简便的分布式系存储，例如 MongoDB/HBase/Voldemort 等。
• 一个更优秀的面试者 会问关于短网址的预期使用周期，然后设计一套系统==可以清理过期的短网址==。

问题：怎么实现跳转服务？

• 一个差的面试者 会从头开始设计这套系统来解决已经被解决的问题
• 一个优秀的面试者 会建议使用一个现成的HTTP服务器加上一个插件，用这个插件来翻译这个短网址的id，在数据库中找这个id，更新访问数据，返回303，跳转到长网址。 现成HTTP服务器比如 Apache/Jetty/Netty/tomcat 等。

问题：怎么存储访问数据？

• 一个差的面试者 会建议每次访问都写到数据库。
• 一个优秀的面试者 会建议由几个不同部分去做这件事情==生成访问流数据，收集整理，每过一段时间写到永久数据库中==。

问题：怎么分上一个问题优秀面试者提出的存储访问数据的不同部分？

• 一个优秀的面试者 会建议用一个延迟较低的信息系统去暂时存储访问数据，然后将数据交给收集整理部分
• 面试者可能会问访问数据多久需要被更新一次。如果每天更新，一个比较合理的方法是存储在HDFS，用map/reduce去计算数据。 如果是要近乎实时的数据，收集整理的部分就要计算出所需的数据

问题：怎么阻止访问受限的网站？

• 一个优秀的面试者 会要求在键值数据库里维护一个域名的黑名单。
• 一个好的面试者 可能会提出一些先进的技术， 可以用在系统规模变得很大的情况下， 比如bloom filter。

失效转移：失效转移（failover）是一种备份操作模式，用于提高系统稳定性和可用性。当主要组件由于失效或预定关机时间的原因而无法工作时，这种模式中的系统组件（如处理机、服务器、网络或数据库）的功能被转嫁到二级系统组件。

冷备份:冷备份是将关键性文件拷贝到另外的位置的一种说法，使用特征或指标/警报来跟踪故障。系统在发生故障时提供新的备用节点，当然，冷备份仅适用于无状态服务。对于备份Oracle数据库而言，冷备份是最快和最安全的方法。

热备份:保持两个活动系统承担相同的任务角色，也就是系统处于正常运转状态下的备份。两个系统中数据几乎是实时镜像的，且拥有相同的数据。

温备份:保持两个活动系统，除非发生故障，否则次要系统不占用流量。

检查点(或类似于Redis快照):系统在处理任务之前使用预先写入（write-ahead）日志(WAL)记录请求。备用节点在故障转移期间从日志中恢复。

• 缺点
  • 大量的日志恢复起来很耗时
  • 自上次检查点以来丢失数据
• 用户案例:Storm, WhillWheel, Samza

双主机(或全部主机)模式:将两个活动系统保留在负载平衡器之后。主机之间是平行的，且数据复制是双向的。

为什么要使用lambda架构？​

为了解决大数据所带来的三个问题

1. 准确性（好）
2. 延迟（快）
3. 吞吐量（多）

例如：以传统方式扩展网页浏览数据记录的问题

1. 首先使用传统的关系数据库
2. 然后添加一个“发布/订阅”模式队列
3. 然后通过横向分区或者分片的方式来扩展规模
4. 容错性问题开始出现
5. 数据损坏(data corruption)的现象开始出现

关键问题在于AKF扩展立方体中，==仅有X轴的水平分割一个维度是不够的，我们还需要引入Y轴的功能分解。而 lambda 架构可以指导我们如何为一个数据系统实现扩展==。

什么是lambda架构​

如果我们将一个数据系统定义为以下形式：

Query=function(all data)

那么一个lamda架构就是

batch view = function(all data at the batching job's execution time)
realtime view = function(realtime view, new data)

query = function(batch view. realtime view)

==lambda架构 = 读写分离(批处理层 + 服务层) + 实时处理层==

跳跃表本质上是一个允许对其进行二分搜索的链表。它实现这一点的方法是添加额外的节点，使你能够“跳过”链接列表的部分。对于给定一个正反随机数来创建额外的节点，跳跃表具有O(logn)复杂度的查询、插入和删除。

用例

• LevelDB MemTable
• Redis 有序集合(Redis SortedSet)
• 倒排索引(Lucene inverted index)

布隆过滤器(Bloom filter)是一种数据结构，用于以远高于其他一般算法的空间和时间效率来检索一个元素是否在一个集合中。

使用布隆过滤器获得的结果，可能为假阳性匹配，但是不可能为假阴性匹配。换句话说，查询返回的结果是“==要么在可能不在，要么不在肯定不在==”。元素可以添加到集合中，但不能删除（尽管这可以通过额外的“计数”布隆过滤器来解决）；添加到集合中的元素越多，误报的可能性越大。

用例

• Cassandra使用布隆过滤器来确定SSTable是否有特定行的数据。
• HBase布隆过滤器是一种测试StoreFile是否包含特定行或者行列单元格的有效机制。
• 使用布隆过滤器，网站的反作弊系统可以有效地拒绝被禁止使用的用户。
• 谷歌的Chrome浏览器曾使用布隆过滤器来识别恶意链接。

目标受众​

拥有一定或较少的经验，或者是在职业生涯中没有担任过任何领导或设计职位的人（无论是正式还是非正式）。

问题描述​

描述你以前特别感兴趣或难忘的项目经历。后续的问题包括：

• 为什么你会觉得它有趣？
• 该项目最具挑战性的部分是什么，你又是如何应对这些挑战的呢？
• 你从这个项目中学习到了什么？你又希望在项目开始前了解什么？
• 你有考虑其他的设计或实现方法吗？ 你为什么选择你做的那个方案？ 如果再次选择做同样的项目，你有什么不同的做法吗？

面试官提示​

由于这里的目标是评估一个人的技术沟通能力和兴趣水平，而他们有可能参与过速成班，所以你应该准备好问他们更多的问题（无论是为了更多的细节，还是有关项目的其他方面）。如果是他们是刚写完论文的毕业生，那么毕业论文通常是很好的切入点。虽然这个问题在很多方面都类似于电话面试中的简历问题，但其内容大约是电话面试的四倍，而且应该按比例更详细地询问他们都做了些什么。因此，虽然评分标准是相似的，但应该用更高的期望和更多的数据来评估面试者。

得分​

优秀的候选人能够：

• 充分地谈论项目经历，在面试中，与面试官的互动应当是对话而不是指导

• 对整个项目具有一定的了解，而不仅仅是他们所关注的领域，并且能够清楚地表达出项目的设计和意图

• 无论是什么项目，都要充满激情，并且能够清楚地描述出激发这种激情的项目要素

• 能够清楚地解释考虑了哪些备选方案，以及他们为什么选择他们所采取的实施策略

• 是否有从他们的经历中反思并吸取教训

而好的候选人能够：

• 在面试中可能会遇到一些问题，但是能够在面试官的帮助下解决

• 可能缺乏对项目更广范围的一些了解，但仍然对与他们直接交互的部分和特定领域具有很强的了解

• 也许看起来充满激情，但无法准确解释这种激情来自何处

• 也许能够讨论他们所做的替代方案，但是考虑的不够深刻

• 从他们的过往经历中反思并汲取经验

而差的候选人则是这样的：

• 在面试交流中表现得费劲，面试官觉得面试者是在询问他，而不是与他交谈

• 即使是在他们工作的领域，也可能缺乏对项目的详细了解。他们可能不了解他们的产品为何这样设计，或者不明白产品是如何与其他系统交互的

• 当你在询问所做过最有趣的项目时，他们对产品表现得应该很感兴趣，但事实上是，他们看起来可能并不太感兴趣

• 可能不熟悉潜在替代方案的实现方法

• 似乎并没有从他们的过往项目经历中反思和学习。而判断这种情况的重要迹象是：“你学到了什么”和“你会有什么不同”的答案很短，或者几乎千篇一律