大规模去重系统

方案 1：使用 Set 数据结构

检查 URL 是否已存在。Set 很快，但空间效率不高。

方案 2：存储在数据库中

将 URL 存储在数据库中并检查新 URL 是否在数据库中。这可以工作但数据库负载会非常高。

方案 3：布隆过滤器（推荐）

这是首选方案。布隆过滤器由 Burton Howard Bloom 于 1970 年提出。它是一种概率数据结构，用于测试元素是否是集合的成员。

  • false：元素肯定不在集合中
  • true：元素可能在集合中

假阳性匹配是可能的，但假阴性是不可能的。

下图说明了布隆过滤器如何工作。布隆过滤器的基本数据结构是位向量。每个位代表一个哈希值。

工作原理

步骤 1：要将元素添加到布隆过滤器，我们将其输入到 3 个不同的哈希函数（A、B 和 C）并设置结果位置的位。注意 “www.myweb1.com” 和 “www.myweb2.com” 都在索引 5 处将同一位标记为 1。假阳性是可能的，因为一位可能被另一个元素设置。

步骤 2：测试 URL 字符串的存在时，相同的哈希函数 A、B 和 C 应用于 URL 字符串。如果所有三个位都是 1，则 URL 可能存在于数据集中；如果任何位是 0，则 URL 肯定不存在于数据集中。

哈希函数选择很重要。它们必须均匀分布且快速。例如，RedisBloom 和 Apache Spark 使用 murmur，InfluxDB 使用 xxhash。

问题：在我们的示例中，我们使用了三个哈希函数。现实中应该使用多少个哈希函数？权衡是什么？

系统设计面试技巧

在我们的 4 步系统设计面试框架中，第二步是”提出高层设计并获得认可”。此步骤的目标是为手头的问题提出高层设计图，并建立共同基础以进一步探索。

在这一步过早陷入过早优化是一个危险信号。例如，一些候选人喜欢在这一步谈论缓存和分片。

优化很复杂且昂贵。它们需要充分的理由来证明增加的复杂性是合理的。在这个早期阶段，理由往往是模糊的。增加的复杂性会分散面试官的注意力，阻止他们理解高层设计。

专注于手头的任务。如果你发现自己被优化想法分散注意力，将它们搁置。列出一个想法列表，在深入探讨部分重新审视。

保持高层设计简单。这一步应该花费约 15 分钟。

问题：还有哪些过早优化可以搁置？

虚拟化 vs. 容器化

下图说明了虚拟化和容器化的分层架构。

虚拟化是一种技术，允许你从单个物理硬件系统创建多个模拟环境或专用资源。

容器化是将软件代码与其所有必要组件（如库、框架和其他依赖项）打包在一起，以便它们隔离在自己的”容器”中。

主要区别

  • 虚拟化：管理程序在硬件上创建抽象层，以便多个操作系统可以彼此并行运行。这被认为是第一代云计算。
  • 容器化：被认为是轻量级版本的虚拟化，虚拟化操作系统而不是硬件。无需管理程序，容器享受更快的资源配置。运行应用程序或微服务所需的所有资源（包括代码、依赖项）都打包在一起，因此应用程序可以在任何地方运行。

问题：你在生产中观察到虚拟化、容器化和裸机之间的性能差异有多大？

云厂商大数据方案对比

下图详细比较了 AWS、Google Cloud 和 Microsoft Azure。

解决方案的共同部分

  1. 结构化或非结构化数据的数据摄取
  2. 原始数据存储
  3. 数据处理，包括过滤、转换、归一化等
  4. 数据仓库，包括键值存储、关系数据库、OLAP 数据库等
  5. 带有仪表板和实时通知的表示层

有趣的是看到不同的云厂商对同一类型产品有不同的名称。

例如，第一步和最后一步都使用无服务器产品。该产品在 AWS 中称为”lambda”，在 Azure 和 Google Cloud 中称为”function”。

问题：你在生产中使用过哪些产品？你用它做什么类型的应用？

为什么 SSD 快

“固态硬盘的读取速度比机械硬盘快 up to 10 倍，写入速度快 up to 20 倍。”

“SSD 是基于闪存的数据存储设备。位存储在单元中，单元由浮栅晶体管组成。SSD 完全由电子组件组成，没有像硬盘驱动器那样的移动或机械部件。”

下图说明了 SSD 架构。

SSD 工作原理

步骤 1：“命令通过主机接口来自用户”。接口可以是 Serial ATA (SATA) 或 PCI Express (PCIe)。

步骤 2：“SSD 控制器中的处理器接收命令并将其传递给闪存控制器”。

步骤 3：“SSD 还嵌入了 RAM 内存，通常用于缓存目的和存储映射信息”。

步骤 4：“NAND 闪存包组织在多个通道上的 gang 中”。

第二张图说明了逻辑页和物理页如何映射，以及为什么这种架构很快。

SSD 控制器并行操作多个 FLASH 粒子，大大提高了底层带宽。当我们需要写入多个页时，SSD 控制器可以并行写入它们，而 HDD 只有一个磁头，一次只能从一个磁头读取。

每次写入 HOST 页时，SSD 控制器找到一个物理页来写入数据，并记录此映射。有了这个映射，下次 HOST 读取 HOST 页时，SSD 知道从哪里从 FLASH 读取数据。

本文为学习目的的个人翻译，译文仅供参考。

原文链接：Large scale deduplication | System design interview tip | Virtualization vs Containerization | Big data solution | Why is SSD fast。

版权归原作者或原刊登方所有。本文为非官方译本；如有不妥，请联系删除。