本周系统设计复习：

  • 3 分钟大 O 表示法
  • AirTags 如何工作？
  • 什么是死锁？
  • 搜索引擎如何工作？

AirTags 如何工作

AirTags 通过结合蓝牙技术和庞大的 Apple 设备网络帮助你定位丢失的物品。

以下是它们如何工作的分解：

1. 蓝牙信号

每个 AirTag 发射安全的蓝牙信号，可以被 Find My 网络内的附近 Apple 设备（iPhone、iPad 等）检测到。

2. Find My 网络

当 AirTag 进入 Find My 网络中 Apple 设备的范围时，该设备匿名且安全地将 AirTag 的位置信息中继到 iCloud。

3. 位置跟踪

然后你可以在自己的 Apple 设备上使用 Find My 应用在地图上查看 AirTag 的大致位置。

限制

请注意，AirTags 依赖蓝牙技术和 Find My 网络内 Apple 设备的存在。如果你的 AirTag 在 Apple 设备稀少的区域，其位置可能不会频繁或准确地更新。

死锁

死锁发生在两个或更多事务相互等待对方释放它们继续处理所需资源的锁时。这导致一种情况，其中两个事务都无法继续，最终无限期等待。

Coffman 条件

Coffman 条件以 Edward G. Coffman, Jr. 命名，他在 1971 年首次概述了这些条件，描述了必须同时存在的四个必要条件才能发生死锁：

  • 互斥（Mutual Exclusion）
  • 持有并等待（Hold and Wait）
  • 不可抢占（No Preemption）
  • 循环等待（Circular Wait）

死锁预防

  • 资源排序：对所有资源类型施加强制总排序，并要求每个进程以严格递增的顺序请求资源
  • 超时：持有资源太久的进程可以被回滚
  • 银行家算法：一种死锁避免算法，模拟资源分配给进程，并帮助基于资源的未来可用性决定是否安全授予资源请求，从而避免不安全状态

死锁恢复

  • 选择受害者：大多数现代数据库管理系统（DBMS）和操作系统实现复杂的算法来检测死锁并选择受害者，通常允许通过配置设置自定义受害者选择标准。选择可以基于资源利用率、事务优先级、回滚成本等
  • 回滚：数据库可以回滚整个事务或仅回滚足够打破死锁的部分。回滚的事务可以由数据库管理系统自动重启

搜索引擎如何工作

搜索引擎通过三个核心过程的组合工作：

1. 爬取（Crawling）

搜索引擎使用称为”爬取器”的自动程序从互联网发现并下载网页。这些爬取器从已知网页列表（种子）开始，并跟随这些页面上的链接查找新页面，创建庞大的互连内容网络。

2. 索引（Indexing）

爬取器收集的信息然后被分析并组织到称为索引的大型数据库中。这个过程涉及提取关键元素，如关键词、内容类型、新鲜度、语言和其他分类信号，以理解每个页面是关于什么的，以及它可能对不同搜索查询的相关性。

3. 提供搜索结果（Serving search results）

当用户输入查询时，搜索引擎的算法筛选索引以识别最相关和有帮助的页面。以下是它如何工作的分解：

  • 查询分析：搜索引擎分析用户的查询以理解其含义和意图。这包括识别关键词、识别同义词和解释上下文
  • 检索：搜索引擎基于查询分析从其庞大索引中检索相关页面。这涉及将查询的关键词与网页的索引内容匹配
  • 排名：然后检索的页面基于它们的相关性和其他因素排名

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

原文链接：EP138: How do AirTags work?。

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