Hxy's Ocean

共享内存上的互斥

在共享内存上实现互斥

实现互斥的根本困难：不能同时读/写共享内存

• load (环顾四周) 的时候不能写，只能 “看一眼就把眼睛闭上”
  • 看到的东西马上就过时了
• store (改变物理世界状态) 的时候不能读，只能 “闭着眼睛动手”
  • 也不知道把什么改成了什么

自旋锁(Spin Lock)

x86 原子操作：LOCK 指令前缀

用 xchg 实现互斥

实现互斥：自旋锁

• 并发编程：千万小心
  • 做详尽的测试
  • 尽可能地证明 (model-checker.py 和 spinlock.py)
• 原子指令的模型
  • 保证之前的 store 都写入内存
  • 保证 load/store 不与原子指令乱序

原子指令的诞生：Bus Lock (80486)

Lock 指令的现代实现

在 L1 cache 层保持一致性 (ring/mesh bus)

• 相当于每个 cache line 有分别的锁
• store(x) 进入 L1 缓存即保证对其他处理器可见
  • 但要小心 store buffer 和乱序执行

L1 cache line 根据状态进行协调

• M (Modified), 脏值
• E (Exclusive), 独占访问
• S (Shared), 只读共享
• I (Invalid), 不拥有 cache line

互斥锁 (Mutex Lock)

自旋锁的缺陷

性能问题 (0)

• 自旋 (共享变量) 会触发处理器间的缓存同步，延迟增加

性能问题 (1)

• 除了进入临界区的线程，其他处理器上的线程都在空转
• 争抢锁的处理器越多，利用率越低

性能问题 (2)

• 获得自旋锁的线程可能被操作系统切换出去
  • 操作系统不 “感知” 线程在做什么
  • (但为什么不能呢？)
• 实现 100% 的资源浪费

自旋锁的使用场景

• 临界区几乎不 “拥堵”
• 持有自旋锁时禁止执行流切换

使用场景：操作系统内核的并发数据结构 (短临界区)

• 操作系统可以关闭中断和抢占
  • 保证锁的持有者在很短的时间内可以释放锁
• (如果是虚拟机呢…😂)
  • PAUSE 指令会触发 VM Exit
• 但依旧很难做好

实现线程 + 长临界区的互斥

“让” 不是 C 语言代码可以做到的 (C 代码只能计算)

把锁的实现放到操作系统里就好啦！

• syscall(SYSCALL_lock, &lk);
  • 试图获得 lk，但如果失败，就切换到其他线程
• syscall(SYSCALL_unlock, &lk);
  • 释放 lk，如果有等待锁的线程就唤醒

Futex = Spin + Mutex

Futex: Fast Userspace muTexes

• Fast path: 一条原子指令，上锁成功立即返回
• Slow path: 上锁失败，执行系统调用睡眠
  • 性能优化的最常见技巧
    • 看 average (frequent) case 而不是 worst case

总结

• 软件不够，硬件来凑 (自旋锁)
• 用户不够，内核来凑 (互斥锁)
  • 找到你依赖的假设，并大胆地打破它
• Fast/slow paths: 性能优化的重要途径

Peterson 算法

A 和 B 争用厕所的包厢

想进入包厢之前，A/B 都要先举起自己的旗子

• A 确认旗子举好以后，往厕所门上贴上 “B 正在使用” 的标签
• B 确认旗子举好以后，往厕所门上贴上 “A 正在使用” 的标签
• 然后，如果对方的旗子举起来，且门上的名字不是自己，等待
  • 否则可以进入包厢
• 出包厢后，放下自己的旗子

证明

• 枚举状态机
  • 可以忽略对称状态（类似剪枝）

(自动) 画状态机理解并发程序

• Python
  • 容易 hack 的动态语言
  • 丰富的库函数
• 死循环也能返回？
  • yeild
• Generator: 也是状态机

Model Checker

Model checker 的一切就是状态机！

• Safety: 红色的状态不可到达
  • G(V,E) 上的可达性问题
• (Strong) Liveness: 从任意状态出发，都能到达绿/蓝色状态
  • G(V,E) 上的什么问题？
• 如何展示这个状态机？
• 如何能避免无效的探索？

工具的故事

没有人能阻止程序员写 bug，但工具可以。

至今为止我们用过的自动化工具 (他们拯救了你无数次)

Type safety check

• -Wall -Werror
• Differential testing
• Model checker
• ……

这门课的另一个 take-away

• 操作系统是一个巨大的工程
• 没有工具 (编程、测试、调试……)，不做系统

并发的基本单位：线程

共享内存的多个执行流

执行流拥有独立的堆栈/寄存器
共享全部的内存 (指针可以互相引用)
用状态机的视角就很容易理解了！

• 放弃 (1)：原子性
• 放弃 (2)：顺序
• 放弃 (3)：可见性

并发编程：思考

并发超出了一般人类对这个世界的基础认识。我们即便假设所有的内存访问都是原子的 (被 __sync_synchronize() 包围)，根据每个线程读/写的数值恢复出一个全局的内存访问顺序也是 NP-Complete 的 (这个基本是课后习题难度)：

• The complexity of sequential consistency (SPDP’92)

这也意味着，并发程序的复杂性从根本上来说对人类是 “失控” 的。但从另一个角度，人类有在另外一个维度解决这个问题的 (工程) 办法：

作出合适的抽象，并且只写自己能控制得了的代码。

某种程度上说，这是我们和现实世界复杂性的妥协。例如，在并发编程时总是使用线程池、队列、Map-Reduce 等容易理解的并发编程工具。此外，人类还发明了很多工具来帮助我们理解并发程序，model checker 就是其中之一。OSTEP 推荐了 helgrind: 基于 Valgrind 实现的并发错误检测工具；与它类似的有 ThreadSanitizer。

Slides
Notes

1. 查询计划 Query Plan

DBMS将SQL语句转换为查询计划。operators 排列成一棵树。数据从树叶流向根部。树中根节点的输出是查询的结果。通常，operators 是二元的(1-2个子运算符)。可以以多种方式执行相同的查询计划。大多数DBMS都希望尽可能多地使用索引扫描(一种数据访问方式)。

2. 处理模型 Processing Models

DBMS处理模型 定义系统如何执行查询计划。对于不同的工作负载，不同的模型具有不同的权衡。

还可以实现这些模型以自上而下 top-to-bottom (最常见)或自下而上 bottom-to-top 地调用运算符。

Iterator Model（迭代模型）

这是最常见的处理模型，几乎每个(基于行的)DBMS都使用它。允许流水线操作，其中DBMS可以在检索下一个元组之前通过尽可能多的运算符处理元组。

每个查询计划操作符都实现 next 函数：

每次调用next时，操作符要么返回单个元组，要么返回空标记(如果没有更多的元组)。
运算符实现了一个循环，该循环在其子级上调用next以检索其元组，然后处理它们(即，在父级上调用next，在其子级上调用next)。
一些操作符会一直阻塞，直到子级发出它们的所有元组(联接、子查询、排序依据)。这些被称为管道断路器pipeline breakers。

输出控制很容易使用这种方法(LIMIT)，因为一旦拥有了所需的所有元组，操作符就可以停止对其子运算符调用next。

Materialization Model（物化模型）

每个 operator 一次处理其所有输入，然后一次发出其所有输出。operator 将其输出“物化”为单个结果。

每个查询计划操作符都实现一个Output 函数：

操作符一次处理其子代的所有元组。
此函数的返回结果是运算符将发出的所有元组。当操作符完成执行时，DBMS再也不需要返回到它来检索更多数据。
这种方法更适合于OLTP工作负载，因为查询一次通常只访问少量的元组。因此，检索元组的函数调用较少。不适合具有大型中间结果的OLAP查询，因为DBMS可能不得不在操作符之间将这些结果溢出到磁盘。

Vectorization Model

就像迭代模型，其中每个操作符实现一个next函数。但每个运算符都会发出大量数据(即向量)，而不是单个元组：

运算符实现可以针对处理批数据进行优化，而不是一次只处理一个项目。
此方法非常适合必须扫描大量元组的OLAP查询，因为调用next函数的次数较少。

3. 访问方法 Access Methods

访问方法是DBMS访问 表中存储的数据 的方式。这些将是查询计划中的底部操作符，它们将数据“feed”到树中它上面的操作符中。关系代数中没有相应的运算符。

顺序扫描 Sequential Scan
对于表中的每一页，迭代每一页并从缓冲池中检索它。对于每个页面，迭代所有元组并计算谓词以决定是否包含元组。

优化：

• 预取 Prefetching：提前获取下几个页面，以便DBMS在访问每个页面时不必阻塞。
• 并行化 Parallelization：使用多个线程/进程并行执行扫描。
• 缓冲池绕过 Buffer Pool Bypass：扫描操作符将其从磁盘获取的页面存储在其本地内存中，而不是缓冲池中。这避免了顺序洪泛问题。
• 区域映射 Zone Map：预计算页面中每个元组属性的聚合。然后，DBMS可以通过首先检查其区域映射来检查它是否需要访问页面。每个页面的区域映射存储在单独的页面中，并且每个区域映射页面中通常有多个条目。因此，可以减少在顺序扫描中检查的总页数。
• 延迟物化 Late Materialization：每个操作符传递给下一个操作符所需的最少量信息(例如，记录ID)。这仅在列存储系统(即DSM)中有用。
• 堆聚簇 Heap Clustering：元组按照聚簇索引指定的顺序存储在堆页面中。

索引扫描 Index Scan

DBMS选择一个(或多个)索引来查找查询所需的元组。

当使用多个索引时，DBMS对每个索引执行搜索并生成一组匹配的记录ID。可以使用位图、哈希表或Bloom过滤器来实现此记录ID。DBMS根据查询的谓词(UNION和INTERSECT)组合这些集合。然后，它检索记录并应用任何剩余的术语。更高级的DBMS支持多索引扫描。

按元组在非聚簇索引中出现的顺序检索元组效率较低。DBMS可以首先找出它需要的所有元组，然后根据它们的页面ID对它们进行排序。

4. 表达评估 Expression Evaluation

DBMS将查询计划表示为树。运算符内部将是一个表达式树。例如，filter 操作符的 WHERE 子句。

树中的节点代表不同的表达式类型：

• 比较(=、<、>、！=)
• 交集(AND)、并集(OR)
• 算术运算符(+、-、*、/、%)
• 常量和参数V值
• 元组属性引用

为了在运行时计算表达式树，DBMS维护一个上下文句柄，该句柄包含执行的元数据，如当前元组、参数和表架构。然后，DBMS遍历树以计算其操作符并生成结果。

Slides
Notes

1. Joins 连接

好的数据库设计的目标是将信息重复量降至最低。这就是我们基于规范化理论编写表的原因。因此，重建原始表需要连接。

Operator Output

对于在联接属性上匹配的元组 r∈R 和元组 s∈S ，联接运算符会将 r 和 s 连接到一个新的输出元组中。

实际上，连接操作符生成的输出元组的内容各不相同。它取决于DBMS的处理模型、存储模型和查询本身：

• 数据：将外部表和内部表中属性的值复制到元组中，并将其放入仅用于该操作符的中间结果表中。这种方法的优点是，查询计划中的未来运算符永远不需要返回到基表来获取更多数据。缺点是这需要更多的内存来物化整个元组。
• 记录ID：DBMS只复制连接 key 和匹配元组的记录ID。这种方法非常适合列存储，因为DBMS不会复制查询不需要的数据。这就是所谓的后期物化。

Cost 分析

我们将用来分析不同联接算法的 cost 指标将是用于计算 joins 的磁盘I/O数量。这包括从磁盘读取数据以及将中间数据写出磁盘所引起的I/O。

本课程使用的变量：表 R 中有 M 个页面，M 个元组；表 S 中 N 个页面，N 个元组。

2. Nested Loop Join 嵌套循环连接

在high-level 上，这种类型的联接算法由两个嵌套的for循环组成，这两个循环迭代两个表中的元组并比较每个唯一的元组。如果元组与连接谓词匹配，则输出它们。外部for循环中的表称为外部表，而内部for循环中的表称为内表。

DBMS总是希望使用“较小”的表作为外部表。较小的可以是元组的数量或页面的数量。DBMS还希望在内存中缓冲尽可能多的外部表。如果可能，利用索引在内部表中查找匹配项。

Simple Nested Loop Join

对于外部表中的每个元组，将其与内表中的每个元组进行比较。这是最糟糕的情况，假设每个元组都有一个磁盘I/O要读取(即没有缓存或访问局部性)。Cost：M+(m×N)

Block Nested Loop Join

对于外部表中的每个块，从内表中获取每个块，并比较这两个块中的所有元组。该算法执行的磁盘访问较少，因为我们针对每个外部表块而不是每个元组扫描内部表。Cost：M+(M×N)

如果DBMS具有可用于计算联接的B个缓冲区，则它可以使用B−2个缓冲区来扫描外部表。它将使用1个缓冲区来保存来自内部表的一个块，并使用1个缓冲区来存储连接的输出。

Index Nested Loop Join

以前的嵌套循环连接算法执行得很差，因为DBMS必须执行顺序扫描来检查内表中的匹配。但是，如果数据库已经为连接键上的一个表建立了索引，则可以使用该索引来加快比较速度。外层的表将是没有索引的表。内表将是带有索引的表。

假设每个索引探测器的成本是每个元组的某个常量值C。成本：M+(m×C)

3. Sort-Merge Join

High-level是根据这两个表的 join key 对它们进行排序。然后对已排序的表执行顺序扫描，以计算联接。如果一个或两个表已按联接属性排序，则此算法非常有用。

此算法的最坏情况是两个表中所有元组的联接属性包含相同的值。这在真实的数据库中不太可能发生。

• 阶段1-排序：首先根据连接属性对两个输入表进行排序。
• 阶段2-合并：并行扫描两个已排序的表，并发出匹配的元组。

假设DBMS有B个缓冲区可用于该算法：

4. Hash Join

哈希联接算法的high-level思想是使用哈希表根据它们的联接属性将元组分割成更小的块。这减少了DBMS计算联接时每个元组需要执行的比较次数。哈希联接只能用于完整联接键上的等联接 equi-joins。

如果元组 r∈R 和元组 s∈S 满足联接条件，则它们的联接属性值相同。如果该值被hash为某个值i，则R元组必须在桶 ri 中，而S元组必须在桶 si 中。因此，只需要将桶 ri 中的R个元组与桶 si 中的S个元组进行比较。

Basic Hash Join

• 阶段1-Build：扫描外部关系并使用连接属性上的hash函数 h1 填充hash表。哈希表中的key 是联接属性。该值取决于实施情况。
• 阶段2-Probe：扫描内部关系，对每个元组使用哈希函数 h1，跳到哈希表中的某个位置，找到匹配的元组。由于哈希表中可能存在冲突，因此DBMS将需要检查联接属性的原始值，以确定元组是否真正匹配。
  如果DBMS知道外部表的大小，则联接可以使用静态哈希表。如果它不知道大小，则联接必须使用动态哈希表或允许溢出页面。

Grace Hash Join / Hybrid Hash Join (Grace哈希连接/混合哈希连接)

当表不能放入主内存时，您不希望缓冲池管理器不断地调入和调出表。Grace Hash Join是基本Hash Join的扩展，它还将内部表 hash 到写到磁盘的分区中。Grace 这个名字来自20世纪80年代在日本开发的格蕾丝数据库机器。

• 阶段＃1-构建：扫描外部表和内部表，并使用连接属性上的哈希函数 h1 填充哈希表。散列表的桶根据需要写入磁盘。如果单个桶不适合内存，则用户使用第二个散列函数h2（其中h1！=h2）进行分区以进一步划分该桶。
• 阶段＃2-探测：对于每个桶级，检索外部和内部表的相应页面。然后在这两页中对元组执行嵌套循环连接。页面将适合内存，因此此加入操作将很快。
  分区阶段Cost：2×(M+N) —— 两次：从磁盘中读数据 和将数据写出到磁盘

探测阶段Cost：(M+N)

总Cost：3×(M+N)

什么是程序？（源代码视角）

程序就是状态机

状态机

• 状态机 = 状态 + 迁移

C语言的语义

C 程序的状态机模型 (语义，semantics)

• 状态 = stack frame 的列表 (每个 frame 有 PC) + 全局变量
• 初始状态 = main(argc, argv), 全局变量初始化
• 迁移 = 执行 top stack frame PC 的语句; PC++
  • 函数调用 = push frame (frame.PC = 入口)
  • 函数返回 = pop frame

应用：将任何递归程序就地变为非递归

什么是程序？（二进制视角）

还是状态机

• 状态 = 内存M + 寄存器R
• 初始状态 = (稍后回答)
• 迁移 = 执行一条指令
  • 我们花了一整个《计算机系统基础》解释这件事
  • gdb 同样可以观察状态和执行

一条特殊的指令

调用操作系统 syscall

• 把 (M,R) 完全交给操作系统，任其修改
  • 一个有趣的问题：如果程序不打算完全信任操作系统？
• 实现与操作系统中的其他对象交互
  • 读写文件/操作系统状态 (例如把文件内容写入M)
  • 改变进程 (运行中状态机) 的状态，例如创建进程/销毁自己

程序 = 计算 + syscall

计算机系统不存在玄学

• 一切都建立在确定的机制上
• 理解操作系统的重要工具：gcc, binutils, gdb, strace

什么是操作系统？

• 管理软件硬资源，为程序提供服务
• 边界是模糊的，精确的定义无意义

今天的操作系统

空前复杂的系统之一

• 更复杂的处理器和内存
  • 非对称多处理器 (ARM big.LITTLE; Intel P/E-cores)
  • Non-uniform Memory Access (NUMA)
  • 更多的硬件机制 Intel-VT/AMD-V, TrustZone/SGX, TSX, …
• 更多的设备和资源
  • 网卡、SSD、GPU、FPGA…
• 复杂的应用需求和应用环境
  • 服务器、个人电脑、智能手机、手表、手环、IoT/微控制器……

理解操作系统：三个根本问题

操作系统服务谁？

• 程序 = 状态机
• 课程涉及：多线程 Linux 应用程序

(设计/应用视角) 操作系统为程序提供什么服务？

• 操作系统 = 对象 + API
• 课程涉及：POSIX + 部分 Linux 特性

(实现/硬件视角) 如何实现操作系统提供的服务？

• 操作系统 = C 程序
  • 完成初始化后就成为 interrupt/trap/fault handler
• 课程涉及：xv6, 自制迷你操作系统

怎么学操作系统？

是一个合格的操作系统用户

• 会 STFW/RTFM 自己动手解决问题
• 不怕使用任何命令行工具
  • vim, tmux, grep, gcc, binutils, …
    不惧怕写代码
• 能管理一定规模 (数千行) 的代码
• 能在出 bug 时默念 “机器永远是对的、我肯定能调出来的”
  • 然后开始用正确的工具/方法调试

【课程简介】

什么是操作系统？

操作系统是一个典型的 “system”——它完成对计算机硬件系统的抽象，提供应用程序的运行环境：

• 从应用程序的视角看，操作系统定义了一系列的对象 (进程/线程、地址空间、文件、设备……) 和操纵它们的 API (系统调用)。这组强大的 API 把计算机的硬件资源有序地管理起来，它不仅能实现应用程序 (浏览器、游戏……)，还支持着各类神奇的系统程序 (容器、虚拟机、调试器、游戏外挂……)

我们会使用操作系统 API 实现一系列 “黑科技”，包括在 Linux 中复刻三类经典游戏外挂：金山游侠、按键精灵、变速齿轮，并用它们修改真正的游戏

• 从硬件的视角看，操作系统是一个拥有访问全部硬件功能的程序 (操作系统就是个 C 程序，不用怕)。硬件会帮助操作系统完成最初的初始化和加载，之后，操作系统加载完第一个程序后，从此作为 “中断处理程序” 在后台管理整个计算机系统

我们会在课堂上调试 xv6 和 Linux 内核，理解真实操作系统的执行

课程组织

操作系统使用正确的抽象使构造庞大的计算机软件/硬件生态从不可能变为可能。这门课围绕操作系统是如何设计 (应用程序视角)、怎样实现 (硬件视角) 两个角度展开，分为两个主要部分：

• 原理课 (并发/虚拟化/持久化):

  • 以教科书内容为主，介绍操作系统的原理性内容。课程同时注重讲解操作系统相关的代码实现和编程技巧，包括操作系统中常用的命令行/代码工具、教学操作系统 xv6 的代码讲解等

• 理解操作系统最重要的实验部分：

  • Mini labs (应用程序视角；设计)：通过实现一系列有趣的 (黑科技) 代码理解操作系统中对象存在的意义和操作系统 API 的使用方法、设计理念
  • OS labs (计算机硬件视角；实现)：基于一个简化的硬件抽象层实现多处理器操作系统内核，向应用程序提供一些基础操作系统 API

【授课老师】

蒋炎岩

【课程主页】

操作系统：设计与实现 (2022 春季学期)

【Tips】

课程已更新到2024，但2023、2024的课程视频是线下实录的，2022的课程视频是线上录的，观感更好。

引用《上海交通大学生存手册》的一段话：“国内绝大部分大学的本科教学，不是濒临崩溃，而是早已崩溃。” 那么蒋老师就是在这样的环境下，少有的对本科CS教学怀有使命感的好老师，这门OS课的质量也绝对可以对标到世界顶尖高校。

---

Slides
Notes

1. 排序 Sorting

我们需要排序，因为在关系模型中，表中的元组没有特定的顺序排序(可能)用于 ORDER BY、GROUP BY、JOIN和 DISTINCT 操作符。

我们可以通过从左到右扫描叶节点来使用聚集B+树来加速排序。然而，如果我们使用非聚集B+树进行排序，这不是一个好主意，因为它会导致大量I/O读取(通过指针跟踪进行随机访问)。

如果我们需要排序的数据适合在内存中，则DBMS可以使用标准排序算法(例如，快速排序)。如果数据不适合，则DBMS需要使用能够根据需要溢出到磁盘的外部排序，并且更喜欢顺序I/O而不是随机I/O。

2. 外部归并排序

分而治之的排序算法，将数据集分成多个独立的 runs，然后分别对它们进行排序。它可以根据需要将 runs 溢出到磁盘，然后一次读回一个。

阶段1-排序：对可放入主内存的小块数据进行排序，然后写回磁盘。

阶段2-合并：将已排序的子文件合并为更大的单个文件。

2-路归并排序

• 过程#0：将表的每 B 页读入内存。对它们进行排序，并将它们写回磁盘。每一组已排序的页面都称为 run。
• 过程#1，2，3…：递归地将多对 runs 合并为两倍长的 runs。

通用归并排序（K-路）

• 过程#0：使用 B 缓冲区页，生成大小为 B 的 N / B 个排好序的 runs。
• 过程#1、2、3…：递归合并 B−1 个 runs。（因为至少要留 1 个作为整合的页）

双缓冲优化

在后台预取下一次 run，并在系统处理当前 run 时将其存储在第二个缓冲区中。这通过持续利用磁盘，减少了每个步骤的I/O请求等待时间。

3. 聚合

查询计划中的聚合 operators 将一个或多个元组的值折叠为单个标量值。

首先聚合函数有5个，分别为：

• count：统计记录数
• sum：求和，多个记录求和
• avg：平均数
• Max：最大值
• min：最小值

分组是经常跟聚合函数一起使用的，分组关键字为：group by

使用聚合函数删除重复值（关键字DISTINCT）

实现聚合有两种方法：(1)排序；(2)hashing。

Sorting

DBMS首先在 GROUP BY 的 key(s) 上对元组进行排序。如果所有内容都适合缓冲池，则可以使用内存内排序算法（例如快速排序），如果数据大小超过内存，则可以使用外部合并排序算法。

然后，DBMS对排序后的数据执行顺序扫描，以计算聚合。operators 的输出将按 key 进行排序。

Hashing

对于计算聚合，hashing 可能比排序的计算成本更低。DBMS在扫描表时填充临时哈希表。对于每条记录，检查哈希表中是否已有条目并执行适当的修改。

如果哈希表太大，内存无法容纳，则DBMS必须将其溢出到磁盘：

• 阶段1-分区 Partation：使用 hash 函数 h1 根据目标 hash key 将元组分割为磁盘上的分区。这将把所有匹配的元组放到同一个分区中。DBMS通过输出缓冲区将分区溢出到磁盘。
• 阶段2-重新散列 Rehash：对于磁盘上的每个分区，将其页面读入内存，并基于第二个散列函数 h2 (其中h1 != h2)构建内存中的hash 表。然后遍历这个哈希表的每个桶，将匹配的元组集合在一起来计算聚合。请注意，这假设每个分区都可以放入内存。

在重新散列阶段，DBMS可以存储以下形式的对( GroupByKey→RunningValue)来计算聚合。RunningValue 的内容取决于聚合函数。要将新的元组插入哈希表，请执行以下操作：

• 如果找到匹配的GroupByKey，则相应地更新RunningValue。
• 否则插入新的(GroupByKey→RunningValue)对。

Slides
Notes

1. 索引并发控制

并发控制协议是DBM用来确保对共享对象进行并发操作的“正确”结果的方法。协议的正确性标准可以有所不同：

• 逻辑正确性：我可以看到我应该看到的数据吗？这意味着线程能够读取它应该被允许读取的值。
• 物理正确性：物体的内部表示是否正确？这意味着我们的数据结构中没有会导致线程读取无效内存位置的指针。

索引的逻辑内容是我们在这堂课中唯一关心的事情。它们与其他数据库元素不太一样，因此我们可以区别对待它们。

2. Locks vs. Latches

Locks ：

• 保护索引的逻辑内容不受其他事务的影响。
• 在交易的整个持续时间内(主要)持有。
• DBMS需要能够回滚更改。

Latches：

• 保护索引内部数据结构的临界区不受其他线程的影响。
• 持有操作持续时间。
• DBMS不需要能够回滚更改。

两种模式：

• READ：允许多个线程同时读同一项目。如果另一个线程处于读取模式，则线程可以获取读取latch
• WRITE：只允许访问一个线程。如果另一个线程以任何模式保持latch，线程就无法获得写latch。

3. Latch 实现

我们可以用来实现latch的底层原语是通过现代CPU提供的原子比较和交换(CAS)指令。这样，线程就可以检查内存位置的内容，以确定它是否具有某个值。如果是，则CPU将用新值交换旧值。否则，内存位置保持不变。

在DBMS中实现latch有几种方法。每种方法在工程复杂性和运行时性能方面都有不同的权衡。这些测试和设置( test-and-set，TAS)步骤是自动执行的(即，在一个线程检查它之后，但在它更新它之前，没有其他线程可以更新值)。

Blocking OS Mutex

使用操作系统内置的互斥基础设施作为 latch。Futex(快速用户空间互斥锁)由(1)用户空间中的自旋锁和(2)操作系统级互斥锁组成。如果DBMS可以获取用户空间锁，则设置锁。它显示为DBMS的单个latch，即使它包含两个内部 latch。如果DBMS无法获取用户空间latch，则它会进入内核并尝试获取更昂贵的 Mutex 。如果DBMS无法获取第二个Mutex，则线程通知OS它在锁上被阻止，然后取消调度。

在DBMS中，OS Mutex 通常不是一个好主意，因为它由操作系统管理，并且开销很大。

• Example：std::mutex
• 优点：使用简单，不需要在DBMS中额外编码。
• 缺点：由于操作系统调度，价格昂贵且不可伸缩(每次锁定/解锁调用约25 ns)。

测试和设置自旋锁存器(TAS)

自旋锁是操作系统互斥锁的更有效的替代方案，因为它由DBMS控制。自旋锁实质上是线程试图更新的内存中的位置(例如，将布尔值设置为真)。线程执行CAS以尝试更新内存位置。如果它不能，那么它会不停地在 while 循环中旋转，试图更新它。

• Example：std::atomic
• 优点：锁/解锁操作高效(单条指令锁定/解锁)。
• 缺点：伸缩性差，缓存也不友好，因为有多个线程，CAS指令会在不同的线程中多次执行。这些浪费的指令将堆积在竞争激烈的环境中；这些线程在操作系统看来很忙，即使它们没有做有用的工作。这会导致缓存一致性问题，因为线程正在轮询其他CPU上的缓存线。

读-写 锁

Mutex和自旋锁存不区分读/写(即，它们不支持不同的模式)。我们需要一种允许并发读取的方法，因此如果应用程序具有繁重的读取，它将具有更好的性能，因为读取器可以共享资源而不是等待。

读-写 锁允许在读或写模式下保持锁。它跟踪在每种模式下有多少线程持有锁并等待获取锁。

示例：这是在自旋锁上实现的。
优点：支持并发读取器。
缺点：DBMS必须管理读/写队列以避免饥饿。由于额外的元数据，存储开销比自旋锁更大。

4. 哈希表 latching

由于线程访问数据结构的方式有限，因此很容易在静态哈希表中支持并发访问。例如，当从一个槽移动到下一个槽(即，自上而下)时，所有线程都以相同的方向移动。线程一次也只能访问一个页面/槽。因此，死锁在这种情况下是不可能的，因为没有两个线程可以竞争对方持有的锁。要调整表的大小，需要对整个表(即header 页中的表)进行全局锁。

动态哈希方案(例如，可扩展的)中的锁稍微复杂一些，因为有更多的共享状态要更新，但一般方法是相同的。

• Page Latches：每个页面都有自己的读写器 latches，以保护其整个内容。线程在访问页面之前获取读取latch或写入latch。这降低了并行度，因为一次可能只有一个线程可以访问一个页面，但访问页面中的多个槽将会很快，因为一个线程只需要获取一个latch。
• Slot Latches：每个插槽都有自己的latches。这提高了并行度，因为两个线程可以访问同一页中的不同槽。但是它增加了访问表的存储和计算开销，因为线程必须为它们访问的每个槽获取一个latch。DBMS可以使用单latch(即，自旋锁)来减少元数据和计算开销。

5. B+ Tree latching

Lock crabbing / coupling 是一种允许多个线程同时访问/修改B+树的协议：

Get latch for parent.
Get latch for child.
Release latch for parent if it is deemed safe. A safe node is one that will not split or merge when updated (not full on insertion or more than half full on deletion).

基本的Latch Crabbing 协议:

查找：从根目录开始向下搜索，反复获取子级上的锁，然后解锁父级。
插入/删除：从根开始向下，根据需要获取 X 锁（write 锁）。一旦孩子锁上，检查它是否安全。如果孩子是安全的，就解开所有祖先上的锁。

改进的 Lock Crabbing 协议：

基本锁抓取算法的问题在于，对于每个插入/删除操作，事务始终获取根上的独占锁。这限制了并发性。

相反，我们可以假设很少需要调整大小(即拆分/合并节点)，因此事务可以获取向下到叶节点的共享锁。每个事务将假定到目标叶节点的路径是安全的，并使用读锁和爬行来到达它，并进行验证。如果路径中的任何节点不安全，则执行先前的算法(即获取写锁)。

• 查找：与之前的算法相同。
• 插入/删除：设置读锁，就像查找一样，转到叶节点，在叶节点上设置写锁。如果叶节点不安全，则释放所有先前的锁，并使用先前的插入/删除协议重新启动事务。

6. 叶子结点扫描

这些协议中的线程以“自上而下”的方式获取锁。这意味着线程只能从低于其当前节点的节点获取锁。如果所需的锁不可用，则线程必须等待，直到它变为可用。有鉴于此，不可能出现死锁。

叶节点扫描容易发生死锁，因为现在我们有多个线程试图同时获取两个不同方向的锁(即从左到右和从右到左)。索引锁不支持死锁检测或避免。

因此，我们处理这个问题的唯一方法是通过编码规程（coding discipline）。叶节点同级锁获取协议必须支持“无等待”模式。也就是说，B+树码必须处理失败的锁获取。这意味着，如果线程试图获取叶节点上的锁，但该锁不可用，则它将立即中止其操作(释放它持有的所有锁)，然后重新启动该操作。