open-courses
  • 公开课笔记
  • CMU 15-445/645 Database Systems
    • Relational Data Model
    • Advanced SQL
    • Database Storage
    • Buffer Pools
    • Hash Tables
    • Tree Indexes
    • Index Concurrency Control
    • Query Processing
    • Sorting&Aggregations
    • Join Algorithms
    • Query Optimization
    • Parallel Execution
    • Embedded Database Logic
    • Concurrency Control Theory
    • Two Phase Locking
    • Timestamp Ordering Concurrency Control
    • Multi-Version Concurrency Control
    • Logging Schemes
    • Database Recovery
    • Introduction to Distributed Databases
    • Distributed OLTP Databases
    • Distributed OLAP Databases
  • UCB - CS162
    • OS intro
    • Introduction to the Process
    • Processes, Fork, I/O, Files
    • I/O Continued, Sockets, Networking
    • Concurrency: Processes & Threads
    • Cooperating Threads, Synchronization
    • Semaphores, Condition Variables, Readers/Writers
    • Scheduling
    • Resource Contention & Deadlock
    • Address Translation, Caching
    • File System (18,19,20)
    • Distributed Systems, Networking, TCP/IP, RPC (21,22)
    • Distributed Storage, Key-Value Stores, Security (23)
    • Security & Cloud Computing (24)
    • Topic: Ensuring Data Reaches Disk
  • MIT - 6.006
    • Sequence and Set Interface
    • Data Structure for Dynamic Sequence Interface
    • Computation Complexity
    • Algorithms and Computation
    • Structure Of Computation
    • Graph & Search
    • Tree & Search
    • Weighted Shortest Paths
    • String Matching, Karp-Rabin
    • Priority Queue Interface & Implementation
    • Dictionary Problem & Implementation
    • Sorting
    • Dynamic Programming
    • Backtracking
    • Self-Balancing Tree
  • MIT - 6.824
    • 2PC & 3PC
    • Introduction and MapReduce
    • RPC and Threads
    • Primary/Backup Replication
    • Lab: Primary/Backup Key/Value Service
    • Google File System (GFS)
    • Raft
    • Lab: Raft - Leader Election
    • Lab: Raft - Log Replication
  • Stanford-CS107
    • 原始数据类型及相互转化
    • 指鹿为马
    • 泛型函数
    • 泛型栈
    • 运行时内存结构
    • 从 C 到汇编
    • 函数的活动记录
    • C 与 C++ 代码生成
    • 编译的预处理过程
    • 编译的链接过程
    • 函数的活动记录续、并发
    • 从顺序到并发和并行
    • 信号量与多线程 1
    • 信号量与多线程 2
    • 复杂多线程问题
    • 函数式编程 - Scheme 1
    • 函数式编程 - Scheme 2
    • 函数式编程 - Scheme 3
    • 函数式编程 - Scheme 4
    • 函数式编程 - Scheme 5
    • Python 基础
  • MIT - 6.001 - SICP
    • 什么是程序
    • 程序抽象
    • 替代模型
    • 时间/空间复杂度
    • 数据抽象
    • 高阶函数
    • Symbol
    • 数据驱动编程与防御式编程
    • 数据抽象中的效率与可读性
    • 数据修改
    • 环境模型
    • 面向对象-消息传递
    • 面向对象 - Scheme 实现
    • 构建 Scheme 解释器
    • Eval-Apply Loop
    • Normal Order (Lazy) Evaluation
    • 通用机
    • 寄存器机器
    • 子程序、栈与递归
    • 在寄存器机器中执行
    • 内存管理
  • MIT - 6.046
    • Randomized Algorithms
    • Skip Lists
  • System Design
    • Twitter
    • Cache Consistency & Coherence
  • DDIA 笔记
    • Replication
    • Transactions
    • The Trouble with Distributed Systems
    • Consistency & Consensus
  • Papers We Love
    • Consistent Hashing and Random Trees (1997)
    • Dynamic Hash Tables (1988)
    • LFU Implementation With O(1) Complexity (2010)
    • Time, Clocks, and the Ordering of Events in a Distributed System (1978)
    • Dapper, a Large-Scale Distributed Systems Tracing Infrastructure (2010)
    • Gorilla: A Fast, Scalable, In-Memory Time Series Database (2015)
  • Release It 笔记
    • Anti-patterns & Patterns in Microservice Architecture
  • Database Design
    • Log Structured Merge (LSM) Tree & Usages in KV Stores
    • Prometheus
Powered by GitBook
On this page
  • Concurrency Control
  • 本节大纲:
  • Latch Modes
  • B+ Tree Concurrency Control
  • Latch Crabbing/Coupling
  • Better Latching Algorithm
  • Horizontal Scan
  • Delayed Parent Updates
  • Conclusion
  • 参考
  1. CMU 15-445/645 Database Systems

Index Concurrency Control

在前两节中讨论的数据结构中,我们都只考虑单线程访问的情况。实践中,绝大多数情况下,我们需要在并发访问情况下保证我们的数据结构还能够正常工作。除了 VoltDB,它用一个线程处理所有请求,彻底排除了并发的需要。

Concurrency Control

通常我们会从两个层面上来理解并发控制的正确性:

  • Logical Correctness:(17 节)我是否能看到我应该要看到的数据?

  • Physical Correctness:(本节)数据的内部表示是否安好?

本节大纲:

  • Latch Modes

  • Index Crabbing/Coupling

  • Leaf Scans

  • Delayed Parent Updates

Latch Modes

Read Mode

  • 多个线程可以同时读取相同的数据

  • 针对相同的数据,当别的线程已经获得处于 read mode 的 latch,新的线程也可以继续获取 read mode 的 latch

Write Mode

  • 同一时间只有单个线程可以访问

  • 针对相同的数据,如果获取前已经有别的线程获得任何 mode 的 latch,新的线程就无法获取 write mode 的 latch

B+ Tree Concurrency Control

我们希望在最大程度上允许多个线程同时读取、更新同一个 B+ Tree index,主要需要考虑两种情况:

  • 多个线程同时修改同一个 node

  • 一个线程正在遍历 B+ Tree 的同时,另一个线程正在 splits/merges nodes

举例如下:

T1 想要删除 44,T2 想要查询 41。删除 44 时,DBMS 需要 rebalance D 节点,将 H 节点拆分成两个节点。若在拆分前,T2 读取到 D 节点,发现 41 在 H 节点,此时时间片轮转到了 T1,T1 把 D 节点拆分成 H、I 两个节点,同时把 41 转移到 I 节点,之后 CPU 交还给 T2,T2 到 H 节点就找不到 41,如下图所示:

如何解决该问题?由于 B+ Tree 是树状结构,有明确的访问顺序,因此很容易想到沿着访问路径加锁的方法,即 Latch Crabbing/Coupling

Latch Crabbing/Coupling

Latch Crabbing 的基本思想如下:

  • 获取 parent 的 latch

  • 获取 child 的 latch

  • 如果安全,则可以释放 parent 的 latch

这里的“安全”指的是,当发生更新操作时,该节点不会发生 split 或 merge 的操作,即:

  • 在插入元素时,节点未满

  • 在删除元素时,节点超过半满

Search

从 root 往下,不断地:

  • 获取 child 的 read latch

  • 释放 parent 的 read latch

举例如下:Search 38

Insert/Delete

从 root 往下,按照需要获取 write latch,一旦获取了 child 的 write latch,检查它是否安全,如果安全,则释放之前获取的所有 write latch。

例 1 如下:Delete 38

例 2 如下:Insert 45

例 3:Insert 25

Better Latching Algorithm

在实际应用中:

  • 更新操作每次都需要在路径上获取 write latch 容易成为系统并发瓶颈

  • 通常 Node 的大小为一个 page,可以存储很多 keys,因此更新操作的出现频率不算高

我们能否在 Latch Crabbing 的基础上做得更好?

可以采用类似乐观锁的思想,假设 leaf node 是安全(更新操作仅会引起 leaf node 的变化)的,在查询路径上一路获取、释放 read latch,到达 leaf node 时,若操作不会引起 split/merge 发生,则只需要在 leaf node 上获取 write latch 然后更新数据,释放 write latch 即可;若操作会引起 split/merge 发生,则重新执行一遍,此时在查询路径上一路获取、释放 write latch,即 Latch Crabbing 原始方案。

举例:Delete 38

Better Latching Algorithm 小结

  • Search:与 Latch Crabbing 相同

  • Insert/Delete:

    • 使用与 Search 相同的方式在查询路径上获取、释放 latch,在 leaf node 上获取 write latch

    • 如果 leaf node 不安全,可能会引起其它节点的变动,则使用 Latch Crabbing 的策略再执行一遍

该方法乐观地假设整个操作只会引起 leaf node 的变化,若假设错误,则使用 Latch Crabbing 的原始方案。

Horizontal Scan

之前的分析中我们仅仅关注了从上到下的访问模式,而没有考虑到左右方向的访问模式,在 range query 中,常常需要横向访问相邻的 nodes。

例1:T1: Find Keys < 4

如果此时刚好有另一个线程作相反方向的访问:T2: Find Keys > 1:

由于 read latch 允许被多次获取,因此并发读的情况不会产生负面影响。

例 2:T1: Delete 4,T2: Find Keys > 1

当遇到横向扫描无法获取下一个节点的 latch 时,该线程将释放 latch 后自杀。这种策略逻辑简单,尽管有理论上的优化空间,但在实践中是常见的避免死锁的方式。

Delayed Parent Updates

从上文中,我们可以观察到:每当 leaf node 溢出时,我们都需要更新至少 3 个节点:

  • 即将被拆分的 leaf node

  • 新的 leaf node

  • parent node

修改的成本较高,因此 B-link Tree 提出了一种优化策略:每当 leaf node 溢出时,只是标记一下而暂时不更新 parent node,等下一次有别的线程获取 parnet node 的 write latch 时,一并修改。

举例如下:Insert 25

Delayed Parent Updates 仅用在 insert 操作中。

Conclusion

让一个数据结构具备并发安全的特点知难行易,尽管本节只是介绍 B+ Tree 上的相关技术,但这些技术同样适用于其他数据结构。

参考

PreviousTree IndexesNextQuery Processing

Last updated 6 years ago

slides