CMU 15-721 14-数据库调度 Scheduling

简介: 查询执行查询计划是由运算符组成的,而运算符实例就是操作符运算在一段数据上的一次调用,任务就是一系列这样的操作符实例的执行序列。数据库调度对于每一个查询计划,数据库系统需要决定什么时候,在什么地方,怎么样去执行。

查询执行

查询计划是由运算符组成的,而运算符实例就是操作符运算在一段数据上的一次调用,任务就是一系列这样的操作符实例的执行序列。

数据库调度

对于每一个查询计划,数据库系统需要决定什么时候,在什么地方,怎么样去执行。
→ 应该使用多少个任务?
→ 应该使用多少个CPU核?
→ 任务应该在哪个CPU核上执行?
→ 任务应该将它的输出存储到哪里?
数据库系统永远要比操作系统知道这些。

今天我们来讲一下:

  • 进程模型
  • 数据放置
  • 数据库调度

进程模型

数据库系统中的进程模型定义了一个系统架构,可以支撑多用户应用的并发请求。Worker是数据库的一个组件,负责代表客户端执行任务并返回结果。

  • 1: 一个进程一个Worker

  • 2: 进程池

  • 3: 一个线程一个Worker

一个进程一个Worker

每一个Worker就是一个独立的OS进程
→ 依赖于OS系统调度
→ 对全局数据结构使用共享内存。
→ 进程崩溃不会让整个系统崩溃。
→ 例子: IBM DB2, Postgres, Oracle
image

进程池

一个Worker可以使用任意进程池中空闲的进程。
→ 仍然依赖于OS系统调度和共享内存。
→ 不利于 CPU 缓存的局部性..
→ 例子: IBM DB2, Postgres (2015)
image

一个线程一个Worker

具有多个Worker线程的单个进程。
→ DBMS必须管理自己的调度。
→ 选择使用调度线程。
→ 线程崩溃可能会让整个系统崩溃。
→ 例子: IBM DB2, MSSQL, MySQL, Oracle (2014)
image

进程模型PROCESS MODELS

用多线程架构有下面几个好处:
→ 很少的上下文切换的开销
→ 不用管理共享内存

观察

不管DBMS使用什么Worker的分配策略或任务分配策略,Worker对本地数据的操作都是非常重要的。DBMS的调度程序必须知道其底层硬件的内存配置。
→ Uniform vs. Non-Uniform Memory Access

UNIFORM MEMORY ACCESS

image

NON-UNIFORM MEMORY ACCESS

image

数据放置

数据库系统可以为数据库划分内存分区,并将每个分区分配给CPU。通过控制和跟踪分区的位置,它可以调度操作符在最近的CPU核的Worker上执行。

内存分配

当DBMS调用malloc时会发生什么?
→ 假设分配器没有可以释放的内存块。
实际上,几乎什么都没有:
→ 分配器将扩展进程数据段。
→ 但是这个新的虚拟内存并没有立即得到实际的物理内存。
→ 操作系统只在有页错误时分配物理内存。

内存分配位置

现在在发生页面错误之后,操作系统在哪里分配NUMA系统中的物理内存?

  • 1: Interleaving

    → 在CPU之间统一分配的内存。

  • 2: First-Touch

    → 在访问导致页面错误的内存位置的线程的CPU上。

数据放置OLTP

image

数据放置OLAP

image

分区vs放置

使用分区方案根据某些策略对数据库进行拆分。
→ 轮询 Round-robin
→ 属性范围 Attribute Ranges
→ 哈希 Hashing
→ 部分/完全复制 Partial/Full Replication
一个放置方案告诉DBMS将这些分区放在哪里。
→ 轮询 Round-robin
→ 跨核交错 Interleave across cores

数据库调度

静态数据库调度

数据库系统在生成执行计划时决定使用多少个线程来执行查询,在执行过程中不可以改变。
→ 最简单的方法是使用与核数相同的任务数

碎屑驱动(MORSEL-DRIVEN)调度

任务的动态调度,这些任务运行在被称为“碎屑”的水平分区上,这些分区分布在各个核上。
→ 一个worker一个CPU核
→ 基于Pull的任务分配
→ 循环的数据放置
支持并行的,NUMA感知的操作符实现。

HYPER架构

没有单独的调度线程,线程使用单个任务队列对每个查询计划执行协作调度。
→ 每个Worker都试图选择本地碎屑上执行的任务。
→ 如果没有本地任务,worker才会从全局队列拉去下一个任务。

HYPER数据分区

image

HYPER执行的例子

按照任务队列,任务A1/A2/A3先执行
image
如果由于filter导致数据分布不均,A3并未执行成功,那么B1/B2可以分配到前两个CPU核及他们的本地内存中,继续执行创建hash
image
如果B1此时执行完毕,A3/B2仍然在执行,那B3被分配到第一个CPU核,但是需要跨本地内存读取B3的数据分布
image

因为一个CPU核一个Worker,他们必须采取偷窃的方式,否则空闲的就会等待那些仍然在执行的任务。用一个lock-free的哈希表去维护全局队列。

SAP HANA NUMA感知的调度

基于多Worker的Pull方式的调度被组织成分组或者池。
→ 每个CPU可以有多个分组
→ 每个组可以有个软和硬优先级的队列
使用一个单独的watchdog线程检查各组是否饱和,并可以重新动态分配任务。

SAP HANA线程组

每个线程组可以有软和硬优先级的任务队列
→ 线程可以去偷窃其他组软队列的任务
每个组有四个不同的线程池:
→ Working: 正在执行一个任务
→ Inactive: 被latch阻塞在内核中
→ Free: 睡眠一会, 然后被唤醒去看是否有新的任务执行
→ Parked: 和Free一样,但是不能自己唤醒自己
image

可以根据任务是CPU还是内存瓶颈来动态调整thread pinning,发现worker偷窃并不适合具有较多套接字的系统。使用线程分组允许内核执行其他任务,而不仅仅是查询。
image

观察

如果请求到达数据库系统的速度快于其执行速度,那么系统就会超载。
操作系统在这里帮不了我们:
→ CPU瓶颈: 啥也不做
→ Memory瓶颈: 内存溢出 OOM
数据库系统最简单的处理方式就是:崩溃

流程控制

  • 2: 接收控制

    → 如果系统确认没有资源去执行新的请求,直接中止新的请求

  • 1: 扼杀

    → 推迟对客户的答复,以增加请求之间的时间

→ 这假定了同步提交方案

一些思考

数据库管理系统是一个设计精妙,意志坚强的独立的一件软件,但是它需要确保它使用下列硬件是正确的:
→ 数据位置是这方面的一个重要方面。
→ 跟踪单节点数据库系统中的内存位置与在分布式数据库系统中跟踪Shard是相同的。
不要让操作系统毁了你的人生。

image

参考链接和文献:

[- 课程原文CMU 15-721 14-数据库调度 scheduling
](https://15721.courses.cs.cmu.edu/spring2019/slides/14-scheduling.pdf)
- V. Leis, et al., Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age, in SIGMOD, 2014
- I. Psaroudakis, et al., Scaling Up Concurrent Main-Memory Column-Store Scans: Towards Adaptive NUMA-aware Data and Task Placement, in VLDB, 2015 (Optional)
- I. Psaroudakis, et al., Task Scheduling for Highly Concurrent Analytical and Transactional Main-Memory Workloads, in ADMS, 2013 (Optional)
- D. Porobic, et al., OLTP on Hardware Islands, in VLDB, 2012 (Optional)

相关文章
|
7月前
|
存储 Oracle 关系型数据库
Dataphin常见问题之想要周期执行任务如何解决
Dataphin是阿里云提供的一站式数据处理服务,旨在帮助企业构建一体化的智能数据处理平台。Dataphin整合了数据建模、数据处理、数据开发、数据服务等多个功能,支持企业更高效地进行数据治理和分析。
|
5月前
|
消息中间件 缓存 架构师
对抗软件复杂度问题之降低代码的复杂度,如何解决
对抗软件复杂度问题之降低代码的复杂度,如何解决
|
5月前
|
DataWorks 关系型数据库 MySQL
DataWorks操作报错合集之从OceanBase(OB)数据库调度数据到MySQL数据库时遇到连接报错,该怎么办
DataWorks是阿里云提供的一站式大数据开发与治理平台,支持数据集成、数据开发、数据服务、数据质量管理、数据安全管理等全流程数据处理。在使用DataWorks过程中,可能会遇到各种操作报错。以下是一些常见的报错情况及其可能的原因和解决方法。
|
7月前
|
调度 数据库 数据库管理
数据库事务中调度串行化、冲突可串行化、前趋图(优先图)
数据库事务中调度串行化、冲突可串行化、前趋图(优先图)
394 0
|
存储 算法 数据库
CMU 15-445 数据库课程第五课文字版 - 缓冲池(上)
CMU 15-445 数据库课程第五课文字版 - 缓冲池(上)
CMU 15-445 数据库课程第五课文字版 - 缓冲池(上)
|
机器学习/深度学习 SQL 人工智能
CMU专家团队创业,OtterTune让数据库插上AI的翅膀
CMU专家团队创业,OtterTune让数据库插上AI的翅膀
121 0
|
缓存 资源调度 Serverless
《Serverless数据库技术研究报告》——三、 Serverless数据库技术趋势——(五)资源快速调度,提升资源利用率
《Serverless数据库技术研究报告》——三、 Serverless数据库技术趋势——(五)资源快速调度,提升资源利用率
119 0
|
机器学习/深度学习 人工智能 自动驾驶
全球名校AI课程库(12)| CMU卡内基梅隆 · 数据库系统进阶课程『Advanced Database Systems』
数据库进阶课程,讨论了很多数据库方向的新技术,适合有数据库基础又想在该方向有深入研究的同学。
2352 1
全球名校AI课程库(12)| CMU卡内基梅隆 · 数据库系统进阶课程『Advanced Database Systems』
|
SQL 机器学习/深度学习 人工智能
全球名校AI课程库(11)| CMU卡内基梅隆 · 数据库系统导论课程『Database System』
数据库方向的专业课程,详尽介绍了数据库的基本知识、底层原理、效率优化、查询优化、新数据库等,是数据库管理系统设计与实施方向的权威好课。
2180 1
全球名校AI课程库(11)| CMU卡内基梅隆 · 数据库系统导论课程『Database System』
|
存储 缓存 自然语言处理
CMU 15-445 数据库课程第五课文字版 - 缓冲池(下)
CMU 15-445 数据库课程第五课文字版 - 缓冲池(下)
CMU 15-445 数据库课程第五课文字版 - 缓冲池(下)