Smith

这篇文章围绕数据库查询执行中的几个核心算子展开，重点从 I/O cost 的角度梳理排序、聚合和连接操作的实现原理。正文先介绍 External Merge Sort 的两阶段流程、pass 数量与总 I/O 开销计算，以及利用 B+ 树索引完成排序的不同场景；随后讨论 GROUP BY、DISTINCT 等聚合操作如何通过排序或哈希实现；后半部分则系统比较多种 Join 策略，包括 Nested Loop Join、Block Nested Loop Join、Index Nested Loop Join、Sort-Merge Join 和 Hash Join，并分析它们在不同内存与索引条件下的代价与适用场景。

这篇文章记录了作者参加 PingCAP Talent Plan TinyKV 学习营、完成 TinyKV 项目后的整体复盘，并汇总了配套白皮书、经验和踩坑总结。正文先说明比赛结果、性能评分异常的猜测以及白皮书各章节入口，随后从硬件准备、测试方式和心态管理谈起，分析 TinyKV 在文档完整性、测试覆盖度和事务实现理解上的几个难点，并给出各个 Project 的难度排序与推荐完成顺序。文章最后补充了参考资料、批量跑测试脚本，以及对整个 TinyKV 学习过程的个人反思。

这篇文章围绕 Extendible Hash Table 的工程实现展开，重点补足很多资料只讲扩容不讲收缩、只讲概念不讲代码的空白。正文先约定 directory、bucket、page、global depth、local depth 和 split image bucket 等术语与规则，再分别说明如何根据深度生成 mask、如何计算兄弟 bucket、以及 directory 的 grow 和 shrink 逻辑。后半部分详细拆解插入、删除和收缩流程，解释桶分裂时 page 的重新分配、directory 指针和 local depth 的更新方式，以及在 bucket 为空时如何与 split image bucket 合并并尝试压缩 directory。

这篇文章记录了作者完成 2021 CS144 实验过程中的设计思路、调试方法以及配套的网络协议笔记，内容覆盖从应用层到传输层的多个实验。正文先介绍开发环境、远程调试和测试技巧，再按 Lab 0 到 Lab 4 的顺序总结 ByteStream、TCP Receiver、TCP Sender 等模块的实现要点，包括乱序重组、序列号与 buffer index 的换算、ACK 计算、窗口填充、重传计时等细节；同时穿插梳理了五层网络模型、常见应用层协议、DHCP 流程等背景知识，方便把实验代码和网络原理对应起来。

这篇文章总结了作者完成 2021 MIT 6.824 四个实验过程中的设计思路和踩坑经验，内容覆盖 MapReduce、Raft、KV Raft 和 Sharded KV。正文先说明 Lab 1 中 task 分发与超时重试的实现方式，再重点展开 Lab 2 里 Raft 的后台线程、超时控制、日志同步、持久化和 snapshot 处理，以及常见的死锁、过期回复和 Figure 8 等关键问题；后半部分继续介绍基于 Raft 的 KV 服务如何做请求去重、日志压缩，以及在分片 KV 场景下如何处理 shard controller、配置变更和 shard 迁移。

这篇文章尝试用更易读的方式梳理 FLP-Impossibility 论文，解释为什么在异步消息系统中，即使最多只有一个进程故障，也不存在能够同时满足 Validity、Agreement 和 Termination 的真正共识算法。正文先定义论文里的大量术语和系统模型，包括 process、configuration、schedule、bivalent、univalent 等概念，再围绕几个关键 lemma 逐步展开证明思路，说明系统总能停留在无法保证做出决议的状态。最后文章结合 Paxos、Raft 等现实算法讨论 FLP 的实际意义，即它证明的是最坏情况的存在，而工程系统必须通过随机化、时序假设或其他约束来换取可用性。

这篇文章以笔记方式系统梳理了 TCP 的核心机制。正文先从 TCP 头部出发，解释序列号、确认号、窗口大小、MSS、SACK、时间戳等字段和选项的作用，再结合 RTT 测量与 PAWS 说明时间戳在高性能网络中的意义；随后讨论 MTU、MSS、TSO、临时端口等基础概念，并详细展开 TCP 三次握手、半连接队列与全连接队列、SYN Flood 与 SYN Cookie、TCP Fast Open，以及四次挥手、同时关闭和 TIME_WAIT 等连接建立与断开的关键过程。

这篇文章围绕操作系统并发控制中的几个核心主题做了系统梳理。正文先定义 critical section、race condition、mutual exclusion 等基本术语，再逐步比较关闭中断、简单自旋锁、基于 Test-And-Set、CAS 和 Fetch-And-Add 的锁实现，以及 ticket lock、sleep/wakeup、two-phase lock 在正确性、公平性和性能上的差异。后半部分则转向 condition variable、生产者消费者模型和 semaphore 的实现与使用细节，最后简要提到 event-based concurrency 中的 select、poll 等思路。

这篇文章系统梳理了操作系统中常见的 CPU 调度算法及其取舍。正文先介绍 turnaround time 和 response time 两个核心衡量指标，再依次讨论 FIFO、Shortest Job First、STCF、Round Robin、MLFQ、Lottery Scheduling 和 Stride Scheduling 的基本思路、优缺点与适用场景，随后重点展开 Linux Completely Fair Scheduler 的 vruntime、sched_latency、min_granularity、nice/weight 和红黑树实现方式，最后补充了多处理器环境下 single-queue 与 multi-queue 调度在负载均衡、锁竞争和 cache affinity 上的差异。

这篇文章不再重复 Bloom Filter 的基础原理，而是把重点放在如何用 Java 实现一个真正可用、可持久化的布隆过滤器。正文先从误算率 False Positive 出发，说明 bits 数量和 hash 函数个数的计算方式，再介绍使用 Murmur Hash 3 作为哈希函数、用 long[] 自定义 Bitset 的实现思路，以及如何通过 protobuf 保存 numHashFunctions 和 bitset 完成序列化。最后文章给出了完整的测试示例，演示如何写入数据、落盘并重新加载后进行成员判断。