系统设计面试的 12 个算法
- 布隆过滤器（Bloom Filter）：在执行磁盘操作前检查请求项是否在缓存中
- 地理哈希（Geohash）：用于构建基于位置的服务
- HyperLogLog：统计用户在搜索中执行的唯一查询数量
- 一致性哈希（Consistent Hashing）：用于集群节点间高效数据分布
- Merkle 树（Merkle Tree）：用于检测多个节点间数据副本不一致
- Raft 算法（Raft Algorithm）：用于实现日志复制共识
- Lossy Count：网络流量分析、Web 分析、识别重击者
- 四叉树（QuadTree）：用于构建基于位置的服务
- 操作转换（Operational Transformation）：用于支持协作编辑系统
- 漏桶（Leaky Bucket）：用于速率限制
- Rsync：在两个不同系统间同步文件和目录
- 光线投射（Ray Casting）：用于地理空间分析、视频游戏碰撞检测、计算机图形学
Kubernetes 如何工作
Kubernetes（K8S）是开源容器编排平台最初由 Google 开发现在由云原生计算基金会（CNCF）维护。
开发者如何与 Kubernetes 交互
- 开发者创建清单文件描述应用
- Kubernetes 获取这些清单文件，验证它们，并在其工作节点集群上部署应用
- Kubernetes 管理应用整个生命周期
Kubernetes 两个主要组件
控制平面（Control Plane）
像 Kubernetes 大脑，包括以下部分：
- API 服务器（API Server）：接收所有来自用户或 CLI 的传入请求
- 调度器（Scheduler）：决定新 pods 在哪里运行基于资源可用性和约束
- 控制器管理器（Controller Manager）：确保集群期望状态匹配实际状态
- Etcd：键值存储 Kubernetes 保存所有数据，包括配置、集群状态和应用期望状态
工作节点（Worker Nodes）
集群中的工作者。每个节点有以下子组件：
- Kubelet：每个节点上主要工作者。它与 API 服务器通信，获取指令，确保容器按预期运行
- Kube-proxy：处理每个节点上网络
- 容器运行时（Container runtime）
PostgreSQL 101：万能数据库
使用 C 语言构建，PostgreSQL 是最流行数据库选择从小型 Web 应用到企业系统。它作为多进程系统运行并遵循 ACID 原则。
PostgreSQL 架构关键点
- PostgreSQL 支持并发客户端连接独立。每个客户端连接到 PostgreSQL 创建专用服务器进程
- Postmaster 进程是主要监督者管理所有其他 PostgreSQL 进程。它控制整个数据库实例
- 后台工作者（Background workers）在需要时运行并行进程处理专门任务
- PostgreSQL 共享内存是中央内存区域包含多个缓冲区如共享、WAL、Clog 和临时缓冲区。所有组件通过这个共享内存通信
- PostgreSQL 也有几个辅助进程如：
- BG Writer：管理后台写入
- WAL Writer：处理预写日志
- Auto Vacuum：维护数据库清洁
- Checkpointer：确保数据一致性
- Stats Collector：收集统计
- System Logger：管理日志
- Archiver：处理归档
- Replication launcher：管理复制
PostgreSQL 物理文件类型
- 数据文件（Data Files）：存储实际数据库数据
- WAL 文件（WAL Files）：预写日志存储
- 归档文件（Archive Files）：备份和恢复数据
- 日志文件（Log Files）：系统和错误日志
API 安全 12 个顶级技巧
- 使用 HTTPS
- 使用 OAuth2
- 使用 WebAuthn
- 使用分级 API 密钥
- 授权
- 速率限制
- API 版本控制
- 白名单
- 检查 OWASP API 安全风险
- 使用 API 网关
- 错误处理
- 输入验证
本文为学习目的的个人翻译，译文仅供参考。
原文链接：EP150: 12 Algorithms for System Design Interviews。
版权归原作者或原刊登方所有。本文为非官方译本；如有不妥，请联系删除。