系统设计面试概念术语要点

• 延迟：响应请求所花费的时间（例如，提供奶酪三明治的时间）。
• 吞吐量：给定时间内处理的请求数量（例如，为多个客户提供服务）。

• 可用性：尽管出现问题（例如，一名厨师缺席）仍能正常工作。
• 以“9”衡量（例如，99.9% 的可用性）。
• 一致性：系统不同部分之间的信息同步（例如，订单副本同步）。

当您在浏览器中输入 URL 时会发生什么？

当您在浏览器中输入 URL 时：

1. URL解析：浏览器识别HTTP协议、域、路径和资源。
2. DNS 查找：它搜索域的 IP 地址，检查各种缓存。
3. TCP 连接：与服务器建立连接。
4. HTTP 请求：发送对特定资源的请求。
5. 服务器响应：服务器发回请求的内容。
6. 渲染：浏览器显示网页。

CDN 是如何运作的？

1. 域名查询：
   • 鲍勃在浏览器中输入www.jdon.com。
   • 浏览器检查域的本地 DNS 缓存。

• 如果不在本地缓存中，浏览器将联系 DNS 解析器（通常通过 ISP）。

• DNS 解析器对www.jdon.com.

• 权威名称服务器不是直接指向伦敦服务器，而是重定向到 CDN 域 ( www.jdon.cdn.com)。

• DNS 解析器查询 CDN 负载均衡器域 ( www.jdon.lb.com)。

• CDN 负载均衡器根据用户位置和服务器负载等因素选择最佳的 CDN 边缘服务器。

• 浏览器连接到所选的 CDN 边缘服务器以加载内容。
• 内容包括静态（例如图像、视频）和动态元素。
• 如果内容不在边缘服务器上，则会从更高级别的 CDN 服务器或伦敦的源服务器获取。

• 此过程是用于高效内容交付的地理分布式 CDN 网络的一部分。

时间复杂度

1. 目的：时间复杂度评估算法的性能如何随输入数据的大小而变化。
2. 复杂性类型：
   • 最坏情况复杂性：任何大小的输入的最大步骤数n。最常用，因为它提供了算法上限的保证。
   • 最佳情况复杂度：任何大小的输入的最小步骤数n。
   • 平均情况复杂度：输入大小的所有可能实例的平均步骤数n。

• 常数 - O(1)：时间与输入大小无关（例如，将两个数字相加）。
• 对数 - O(log n)：每一步将问题大小减半（例如，二分搜索）。
• 线性 - O(n)：时间随着输入大小线性增长（例如，在数组中查找最大值）。
• 超线性 - O(n log n)：结合线性和对数增长（例如，快速排序、合并排序）。
• 二次 - O(n^2)：时间随着输入大小的平方而增长（例如，插入排序）。
• 三次 - O(n^3)：涉及三重嵌套循环（例如，某些动态编程算法）。
• 指数 - O(c^n)：每次增加输入大小（例如，枚举子集），时间都会加倍。
• 阶乘 - O(n!)：时间随着输入大小的阶乘而增长（例如，生成排列）。

WhatsApp 仅用 32 名工程师就能支持每天 500 亿条消息的 8 个原因

1. 单一责任 原则：
   • 专注于核心功能：消息传递。
   • 避免功能蔓延和不必要的功能。
   • 可靠性高于一切。

• 选择 Erlang 作为服务器功能是因为它的可扩展性和对热加载的支持。
• Erlang 高效的线程和上下文切换机制有助于提高性能。

• 利用开源解决方案，例如 Ejabberd（一种基于 Erlang 的消息传递服务器）。
• 定制现有解决方案以满足特定需求。
• 用于推送通知等功能的集成第三方服务。

• 强调服务健康状况的监控和警报等方面。
• 实现了软件开发的持续集成和持续交付。

• 采用对角缩放，水平和垂直缩放相结合的方法。
• 在 FreeBSD 上运行服务器，并针对处理数百万个连接进行了优化。
• 用于处理流量峰值和潜在故障的过度配置服务器。

• 定期测量性能指标以识别和消除瓶颈。
• 保持持续反馈和改进的循环。

• 进行负载测试以识别和解决单点故障。
• 使用模拟生产流量进行实际测试。

• 保持工程团队规模较小（32 名工程师），以保持效率并减少沟通开销。

这就是 Quora 对 MySQL 进行分片以处理超过 13 TB 数据的方式

1. 垂直分片：
   • 实现：将表分离到不同的服务器中（领导者-跟随者模型）。
   • 目的：增强写入可扩展性。
   • 挑战：复制延迟、事务限制以及大型表的潜在性能问题。

• 采用原因：解决大型表的挑战，例如架构更改和错误风险。
• 方法：将一个逻辑表拆分为多个物理表。

• 构建与购买：选择构建自己的分片解决方案，重用垂直分片逻辑。
• 分片级别：由于二级索引的广泛使用，重点关注表级别的分片。
• 分片方法：选择基于范围的分区，有利于常见的范围查询。
• 元数据管理：将分片元数据存储在 Apache Zookeeper 中。
• 数据库 API：修改为处理分片列和键，增强针对 SQL 注入的安全性。
• 分片列选择：基于延迟敏感度和每秒查询次数 (QPS) 考虑。
• 跨分片索引：用于优化非分片列查询，但具有潜在的性能和一致性权衡。
• 分片数量：保持较低的计数以减少非分片列查询的延迟。

使您的数据库具有高可用性
冗余

• 目的：即使一台服务器发生故障，也确保数据库连续运行。
• 非备份：与备份不同，冗余涉及运行多个活动数据库实例。
• 停机成本：可能非常高，平均每分钟 7,900 美元。
• 冗余模式：
  
  • 主动-被动：一台主动服务器处理请求，而其他服务器则备用。
  • Active-Active：多个服务器同时处理请求。
  • 多主动：主动-主动的扩展，具有更复杂的设置。

• 目标：通过物理分离数据库组件来最大限度地减少灾难影响。
• 分离度：
  
  • 服务器：同一数据中心的不同服务器。
  • 机架：数据中心内的独立机架。
  • 数据中心：多个数据中心。
  • 可用区域：云提供商网络内的不同区域。
  • 区域：地理位置分散的地点。

速率限制如何运作？
速率限制 的工作原理：

1. 概念：限制发送到服务器的请求数量。
2. 实施：速率限制器用于控制服务器或 API 的流量。

1. 限制：在设定的时间范围内允许的最大请求数（例如，每天 600 个请求）。
2. Window：限制的持续时间，从秒到天不等。
3. 标识符：用于识别请求发送者的唯一属性（如用户 ID 或 IP 地址）。

• 过程：
  
  1. 计数请求：跟踪来自用户或 IP 的请求数量。
  2. 超出限制：如果计数超出限制，则阻止或限制进一步的请求。
• 注意事项：
  
  • 请求计数器的存储。
  • 速率限制规则。
  • 被阻止请求的响应策略。
  • 规则变更实施。
  • 维护应用程序性能。

• 速率限制器组件：根据规则检查传入请求和存储的数据（发出的请求数）。
• 规则引擎：定义速率限制规则。
• 缓存：存储速率限制数据以实现高吞吐量和低延迟。
• 响应处理：
  
  • 如果在限制范围内，则允许请求。
  • 如果超出限制，则阻止请求，通常使用 HTTP 状态代码 429。

• Silent Drop：通过静默丢弃多余的请求来愚弄攻击者。
• 缓存规则：通过规则引擎的缓存和规则更改的后台更新来增强性能。

缓存
缓存的概念

• 目的：通过将数据临时存储在快速访问硬件或软件层中来加速数据访问。
• 缓存命中：在缓存中找到数据。
• 缓存未命中：数据不在缓存中，必须从其原始位置获取。

• 级别：硬件、操作系统、前端、网络应用程序、数据库等。
• 角色：
  
  • 减少延迟。
  • 保存网络请求。
  • 存储资源密集型操作的结果。
  • 避免重复操作。

• 应用程序缓存：集成到应用程序代码中，在数据库访问之前检查缓存。示例：Memcached、Redis。
• 数据库缓存：内置于数据库中，无需更改代码，优化数据检索。

• 缓存缺失率：高缺失率会增加更多延迟。
• 过时数据：确保缓存数据是最新的且相关的。

1. 缓存旁置（延迟加载）：
   • 直接从缓存中读取。如果未命中，则从数据库读取并更新缓存。
   • 优点：适合读取繁重的工作负载。缓存只存储必要的数据。
   • 缺点：可以提供陈旧的数据。初始缓存未命中。

• 仅与缓存交互。缓存管理从数据库获取的数据。
• 简化了应用程序代码，但使缓存实现变得复杂。

• 同时将数据写入缓存和数据库。
• 确保数据一致性。更高的写入延迟。

• 将数据写入缓存，然后异步写入数据库。
• 更低的写入延迟。适合写入繁重的工作负载。

• 直接写入DB，缓存仅存储读取的数据。
• 适合不经常读取的数据。新数据的读取延迟较高。

• 取决于数据访问模式。
• Cache-Around：适合通用、读取密集型应用程序。
• 写繁重的工作负载：回写方法是有益的。
• 不频繁读取：Write-around 策略。

• 管理有限的缓存空间：
  
  • FIFO：先进先出。
  • LIFO：后进先出。
  • LRU：最近最少使用。
  • MRU：最近使用过。
  • LFU：最不常用。
  • RR：随机替换。

数据库复制的幕后黑手
基于语句的复制

• 工作原理：领导者记录每个 SQL 写入语句（INSERT、UPDATE、DELETE）并将这些语句转发到跟随者节点。
• 优点：
  
  • 有效节省网络带宽，仅传输SQL语句。
  • 可跨不同数据库版本移植。
  • 实施起来更简单。
• 限制：
  
  • 非确定性函数（例如 NOW()、UUID()）在副本上产生不同的值。
  • 涉及自动递增列的事务必须以相同的顺序执行。
  • 由于触发器或存储过程而导致潜在的不可预见的影响。

• 概念：WAL 是所有写入的仅附加序列，与跟随者节点共享。
• 用法：常见于 PostgreSQL 等数据库。
• 优点：创建领导者数据结构的精确副本。
• 缺点：与存储引擎紧密耦合，数据库版本变更灵活性较差，不利于零停机升级。

• 功能：使用逻辑日志以行格式显示写入。
• 操作详情：
  
  • 为所有列插入日志新值。
  • 删除已删除行的日志标识符。
  • 更新日志标识符和已修改列的新值。
• 优点：与存储引擎解耦，允许领导者数据库和跟随者数据库之间的向后兼容性和版本灵活性。

• 选择取决于系统的具体要求，例如：
  
  • 网络效率。
  • 一致性要求。
  • 数据库版本兼容性。
• 基于语句的复制：最适合简单、并发较少的环境。
• WAL Shipping：适用于精确副本和数据完整性至关重要的系统。
• 基于行的复制：非常适合需要跨不同数据库版本的灵活性和兼容性的环境。

一致性哈希
缓存服务器

• 使用案例：将经常访问的数据存储在快速的内存缓存中。
• 哈希作用：通过哈希请求属性（IP、用户名等）确保将相同的请求发送到同一服务器。
• 挑战：添加或删除服务器时保持有效的缓存。

• 目的：跨多个数据库服务器分发数据。
• 散列函数：对数据密钥进行散列以确定存储数据的服务器。
• 限制：与缓存类似，添加或删除服务器会使数据分发变得复杂。

• 目标：有效地将键（数据标识符或工作负载请求）映射到服务器。
• 所需特性：
  
  • 平衡：在服务器之间平均分配密钥。
  • 可扩展性：轻松添加或删除服务器，只需最少的重新配置。
  • 查找速度：快速查找给定密钥的服务器。

• 方法：对服务器进行编号，用于hash(key) % N为服务器分配密钥。
• 缺点：不可扩展。更改服务器数量 (N) 需要重新映射所有密钥。

• 概念：将哈希值视为循环空间。将密钥和服务器映射到这个圆圈上。
• 操作：按顺时针方向将每个密钥分配给圆圈上最近的服务器。
• 优点：
  
  • 添加/删除服务器时，只有一小部分密钥需要重新映射。
  • 更好的可扩展性。
• 问题：不保证均匀的密钥分配（平衡）。

• 策略：为哈希环上的每台服务器引入副本或虚拟节点。
• 好处：
  
  • 由于更小的范围和更均匀的密钥分布，更好的平衡。
  • 添加或删除服务器时重新平衡速度更快。
  • 支持服务器容错和异构性。
• 实现：将更多的虚拟节点分配给更强大的服务器以实现负载平衡。

为什么数据库会出现复制延迟

• 概念：复制延迟是数据库系统中领导节点上的写入操作与跟随节点上的复制操作之间的延迟。
• 基于领导者的复制设置：
  
  • 写入由单个节点（领导者）处理。
  • 读取查询可以由任何副本（追随者）提供服务。
  • 常见于读取多于写入的系统。
• 异步复制与同步复制：
  
  • 同步：所有副本必须确认写入操作，如果副本出现故障，可能会导致不可用。
  • 异步：允许在关注者之间分配读取，但如果关注者滞后，可能会导致过时的读取。
• 复制延迟是如何发生的：
  
  1. 用户A更新领导节点上的数据。
  2. 领导者将复制数据发送给追随者。
  3. 用户 B 在更新之前从关注者（副本 2）中读取内容，收到过时的信息。
  4. 副本 2 最终得到更新。
• 影响：
  
  • 滞后时间从几分之一秒到几分钟不等。
  • 导致临时数据不一致（最终一致性）。
  • 较大的滞后会显着影响应用程序性能。
• 挑战：管理复制延迟以最大限度地减少数据不一致并确保高效运行。

数据库复制引起的问题

1. 消失的更新
   • 场景：用户在领导节点上更新数据，但随后对滞后副本的读取请求显示过时的数据。
   • 问题：用户感到沮丧，因为他们的更新似乎消失了。
   • 解决方案：实现写后读一致性。方法包括：
     • 从领导者那里读取用户修改的数据。
     • 使用时间戳跟踪最近的写入。
     • 监视和限制对滞后副本的查询。

• 问题：用户看到更新（例如，新评论），然后由于副本滞后，更新在刷新后消失。
• 用户体验：混乱和不一致。
• 解决方案：确保单调读取。
  
  • 用户始终从同一个副本读取。
  • 使用基于用户 ID 的哈希来进行副本选择。

• 问题：在分片数据库中，复制滞后会导致通信顺序混乱（例如，回复出现在原始消息之前）。
• 结果：看起来好像因果颠倒了。
• 解决方案：提供一致的前缀读取。
  
  • 确保按照写入的顺序读取写入。

请求合并的工作原理
概念：请求合并是一种通过减少对相同数据的冗余请求来优化数据库查询的技术。
应用：Discord 成功使用它来有效管理数万亿条消息。
功能：

1. setup：涉及API层和数据库之间的中间数据服务。
2. 过程：
   • 当发出第一个请求时，数据服务中会启动一个工作任务。
   • 对相同数据的后续请求将订阅此现有任务。
   • 工作任务查询数据库一次，并将结果同时返回给所有订阅者。

1. 请求启动：在请求合并中，只有第一个请求才会触发数据库查询。后续的等待其结果。在缓存中，所有请求都会命中缓存。
2. 与缓存一起使用：请求合并可以通过减少对缓存的命中次数来补充缓存。

• 每个工作任务都维护一个包含请求和请求者列表的本地状态。
• 响应将在到达后传播给所有等待的请求者。

• 请求合并对于具有高并发和冗余请求的系统特别有用。
• 这项技术的必要性取决于系统的规模和具体挑战。

如何迁移 MySQL 数据库
背景：Tumblr 的 MySQL 数据库跨越 200 多台服务器，容量达 21 TB，包含 60 多亿行数据，因此需要一种能够最大程度地减少对用户影响的迁移策略。
挑战：

• 保持高可用性和可扩展性。
• 最大限度地减少迁移过程中的停机时间和用户影响。

1. CQRS 模式（命令和查询职责分离）：
   • 数据库的读写操作分开。
   • 确保迁移期间的连续读取可用性。

• 领导者在远程数据中心处理读写操作。
• 本地数据中心有处理读取请求的追随者。
• 使用持久连接来减少延迟问题。

• 位于本地数据中心。
• 保持与远程领导者的持久连接。
• 启用连接池，提高性能并减少断开连接。

1. 准备：
   • 在每个数据中心存储领导者、追随者和代理的元数据。

• 将数据库领导者从数据中心 A 转移到 B。
• 自动化工具将追随者和代理人重定向到新的领导者。

• 关注者继续响应阅读请求。
• 写入请求短暂停止或缓冲，对用户的影响最小。

• Leader-Leader Replication：可以增强写入可用性，但会带来数据冲突的风险。
• 不使用的原因：潜在的冲突可能是 Tumblr 选择反对这种方法的原因。

耐用性
核心目标：持久性，确保即使发生断电、系统崩溃或硬件问题等故障，数据也不会丢失。
单节点数据库持久化

1. 持久性方法：数据写入非易失性存储（硬盘、SSD）。
2. 事务处理：
   • 日志写入：在进行实际数据更新之前，数据首先写入日志文件。
   • 更新执行：日志输入后，数据库更新实际数据。
   • 日志的作用：启用事务重新处理以恢复故障后的一致状态。
   • 效率：由于其仅附加性质，日志写入速度很快，从而最大限度地减少了寻道时间。

1. 复杂性：由于需要跨多个服务器进行协调，因此复杂性较高。
2. 两阶段提交协议：
   • 协调者角色：指定的服务器协调提交过程。
   • 过程：
     • 协调器向所有参与者服务器发送提交指令。
     • 等待所有参与者的确认。
     • 根据响应提交或回滚来完成事务。

Redis
Redis概述：

• Redis 代表远程字典服务器。
• 它是一个开源的键值数据库存储。
• 作为数据结构服务器，支持各种数据结构，如字符串、列表、集合、哈希、排序集和 HyperLogLogs。

• 由 Salvatore Sanfilippo 在 2000 年代末创建。
• 开发用于解决实时分析中 MySQL 的扩展问题。
• 由于其效率和灵活性而受到欢迎和广泛采用。

• 基本操作包括GET和SET。
• 支持多种数据结构，每种数据结构都有特定的用例和操作。

1. 单实例：最简单的形式，在相同或单独的服务器上运行。
2. 复制实例：主实例在辅助实例之间复制，以实现并行读取请求和备份。
3. Sentinel：管理高可用性、监控和故障处理。
4. 集群：使用分片在多台机器上分布数据。

• 提供两种方法：
  
  • RDB（Redis 数据库备份）：基于快照的备份。
  • AOF（仅附加文件）：记录最近备份的每个更改。
• RDB 和 AOF 之间的选择取决于速度需求与数据新近度。

• 利用单线程模型进行操作，避免多线程开销。
• 性能通常受内存和网络而非 CPU 的限制。

• 数据库：作为主键值存储。
• 缓存：用于存储频繁查询或缓存 API 请求。
• Pub/Sub：用于可扩展且快速的消息传递系统。

salt-and-pepper
1.哈希

• 方法：将纯文本密码转换为随机字符串。
• 流程：对用户密码进行哈希处理，并在登录期间与存储的哈希值进行比较。
• 常用算法：MD5、SHA 系列。然而，这些很容易受到彩虹表攻击。

• 目的：通过防御彩虹表等预计算攻击来增强散列。
• 执行：
  
  • 为每个密码生成唯一的盐。
  • 将salt与密码结合并散列结果。
  • 将salt以纯文本形式存储，并将散列密码存储在数据库中。
• 验证过程：
  
  1. 从数据库中检索salt。
  2. 将输入的密码与salt和哈希值结合起来。
  3. 与存储的哈希值进行比较以进行验证。
• 唯一性：确保每个存储的哈希值都是唯一的，即使密码相同。

• 功能：为salt添加额外的安全层。
• 机制：
  
  • 在散列之前向密码添加pepper。
  • pepper未存储在数据库中。
• 登录流程：
  
  • 尝试密码和pepper的组合，直到找到匹配项。
• 好处：显着增加暴力攻击所需的工作量。

• 组合技术：同时使用盐腌和胡椒粉可提供强大的保护。
• 独特性的重要性：独特的盐和胡椒使每个哈希值都不同。
• 更新做法：不断更新和改进密码存储方法，以对抗新的黑客技术。

从单体转向微服务
1.模块化整体方法

• 概念：将模块化设计融入整体架构中。
• 特征：
  
  • 松散耦合的模块。
  • 明确的边界。
  • 显式依赖关系。
• 结构：应用程序分为独立的模块。
• 部署：仍然保持单一应用程序部署。
• 优点：
  
  • 简化开发和维护。
  • 提供类似微服务的好处，但没有相关的复杂性。

• 设计转变：从业务功能的水平层到垂直切片。
• 好处：
  
  • 针对特定业务领域的范围变更。
  • 更容易添加和修改功能。
• 微服务潜力：垂直模块可以逐渐演变成独立的微服务。
• 学习机会：提供对领域和功能划分的见解。

• 平衡：微服务相对于整体架构并没有固有的优势，反之亦然。
• 进化方法：使架构适应不断变化的应用程序需求。
• 实用主义：选择最适合项目要求和环境的架构。

高可用性的秘密技巧
静态稳定性策略

1. 双活高可用性：
   • 实施：在多个可用区 (AZ) 的实例之间分配流量。
   • 示例：如果需要两个实例，则创建三个（50% 超额配置）。
   • 优点：即使整个可用区发生故障，也能保持满容量。

• 用例：用于数据库等有状态服务。
• 设置：一个可用区中的主实例和另一个可用区中的备用实例。
• 功能：如果原始主可用区出现故障，则备用变为主用。

• 批评：由于过度配置而被视为资源浪费。
• 理由：
  
  • 对于停机时间不可接受的关键任务应用程序至关重要。
  • AWS（EC2、S3、RDS）等主要云服务使用它来防止中断。

• 中断成为常态：中断是不可避免的；为他们做好规划至关重要。
• 风险管理：过度配置是减轻停机风险的战略选择。
• 上下文相关：所需的静态稳定性水平根据系统的关键程度而变化。

4 种 NoSQL 数据库
1.文档数据库

• 示例：MongoDB、Couchbase、RavenDB。
• 数据存储：以 JSON、BSON 或 XML 文档的形式。
• 优点：与应用程序中的域级数据对象紧密结合。
• 使用案例：非常适合需要接近应用程序数据的结构的项目。

• 示例：Redis、etcd、DynamoDB。
• 结构：以键值对形式存储的数据。
• 简单性：类似于两列表（键和值）。
• 使用案例：缓存、购物车、用户配置文件。

• 示例：Apache Cassandra、Apache HBase。
• 存储方式：数据存储在列而不是行中。
• 优点：对特定列进行高效的分析和聚合。
• 注意事项：不强一致；写操作可能很复杂。

• 示例：Neo4j、亚马逊海王星。
• 概念：重点关注数据元素（节点和链接）之间的关系。
• 优点： 消除了 SQL 数据库中对多个表连接的需要。
• 使用案例：知识图、社交网络、类似地图的应用程序。

• 文档数据库：多功能，适合大多数传统上使用 SQL 的应用程序。
• 键值存储：适用于需要快速读/写访问数据项的应用程序。
• 面向列：对大型数据集的分析和操作。
• 图形数据库：关系是数据模型核心的应用程序。