https://www.youtube.com/playlist?list=PLSE8ODhjZXjaKScG3l0nuOiDTTqpfnWFf
这门课程主要讨论数据库管理系统的设计与实现。
课程不会教如何使用数据库或设计使用数据库的应用,这门课会在另一门课上 teaching。
课程重点是从内部了解如何构建系统执行查询和存储数据。
所有项目都将在名为Bus Stop的学术数据库系统中进行,用C++实现。
关系模型是数据库管理系统中重要的理论基础。关系是二维表,包含若干属性列。关系的记录(元组)通过唯一键来标识。
关系代数操作包括:
选择(Selection) - 根据条件过滤元组。
并集(Union) - 合并两个关系中的元组。
差集(Difference) - 求两个关系的差集。
交集(Intersection) - 求两个关系的交集。
并联(Join) - 关联两个关系中的共同属性。
导出(Projection) - 从关系中投影(选择)必要的属性列。
重命名(Rename) - 重命名关系或属性的名称。
SQL的主要语句包括:SELECT, FROM, WHERE, GROUP BY, HAVING, ORDER BY。这些语句可以组合起来完成复杂的查询操作。
SQL语言由IBM研究人员Chamberlain和Boyce于1970年代开发,用于IBM的关系数据库系统System R。
早期SQL语言被称为SEQUEL(结构化查询语言),后简称SQL。
其他早期关系数据库系统包括伯克利开发的Ingress系统及其查询语言QUEL。
IBM将SQL推广应用,Oracle公司也开始支持SQL语言。SQL于1986年成为ANSI标准,1987年成为国际标准。
SQL语言标准不断更新,当前版本为SQL 2016。新增了JSON支持等新的功能特性。
支持SQL的最小要求是1992年SQL标准中的数据操纵语言、数据定义语言和数据控制语言功能。
SQL语法包含三部分:
数据操作语言(DML),用于读取和修改数据库中的数据。
数据定义语言(DDL),用于定义数据库中的 schema,如表、索引、触发器等。
数据控制语言(DCL),用于管理数据权限和安全性。
虽有SQL标准,但不同数据库系统对标准支持程度不完全一致。
Oracle支持标准最好,PostgreSQL支持也较好。但各数据库对标准扩展语法和关键字的实现还是不同的。
数据库查询优化实现也各有差异。优化成为数据库系统设计的关键技术难点。
数据库系统的存储层次结构从速度快但容量小到速度慢但容量大分为几个层级:
CPU注册存储:容量极小但访问速度极快,只有几十字节。
主内存:容量较小但访问速度快,如果断电数据会丢失。
固态硬盘(SSD):容量大于内存,访问速度次于内存,不断电也不会丢失数据。
转化硬盘:容量最大,访问速度最慢。文件的连续读取速度比随机读取快。
数据库软件的设计基于“外存导向”架构,即:
数据库 primariy 存储在非易失性外存设备如硬盘、SSD上。
软件管理数据在外存和内存之间的流动,内存是临时存储,外存是永久存储。
数据访问需要将外存数据载入内存进行处理,这会影响系统设计。
数据库文件存储于外存采用分区(page)方式:
外存支持分块访问但不支持精确地址访问。
页面为基本分配和传输单元,大小一般2KB到8KB。
读取页面时会一次性将整个页面读入内存用于后续访问。
连续读取页面比随机读取更高效。
本课开始介绍数据库存储层各个组成部分的实现,以支持面向磁盘的数据库操作。
页式存储结构中的数据库被划分为page,每个page存储一批tuple。这种结构存在几个问题:
碎片问题。在更新tuple时,可能需要更新多个page,效率低下。
将要更新的tuple可能分布在多个页面中,这时需要随机读写多个页面,效率低。
每次只能读取整个page,会读取很多不需要的tuple。
存在覆盖写入的限制,一些存储系统只允许添加新数据,无法覆盖更新。
日志式存储结构没有page概念,每次操作都写一个日志条目(log entry)到日志文件中。
每次操作都需要一个唯一的ID,可以是递增计数器。
支持两种操作:put和delete。put可以重复覆盖写数据。
每次操作都写一个日志条目,包含操作类型和数据,顺序append到日志文件中。日志文件以时间顺序排列,旧日志在前,新日志在后。
支持原子性地并行读写。读操作根据日志重放执行结果。
通过定期合并日志文件提高查询效率。
元数据:描述数据库本身结构的结构,如表名、列名、约束等信息。存储在系统目录和系统表中。
不同类型的数据(整数、浮点数、字符串等)使用不同的格式存储。
日志式存储结构解决了页式结构的问题,支持高并发读写,可扩展性好。已成为NoSQL和新一代关系数据库的主流存储模型。
数据库工作负载主要分为三类:
OLTP(在线事务处理):读写少量数据,并且操作简单。比如Amazon网站上用户的购物车操作。
OLAP(在线分析处理):查询大量数据,操作复杂,比如对历史数据进行复杂统计和数据分析。
HTAP(混合事务和分析处理):既进行事务也进行分析。
对OLAP工作负载来说,传统的行存储格式不太优化,因为OLAP查询需要扫描整张表,但数据分散在不同页中,磁盘寻址开销大。
列式数据库将同一列的数据存储在一起,这样对OLAP查询更有优势,因为只需顺序读取相关列的数据,而不是乱序读取各行。
数据库同样可以对存储在磁盘中的数据进行压缩,以减少磁盘占用和传输开销。
压缩算法包括:
字典编码:将频率高的值替换为索引。
径向压缩:针对浮点/定点类型,只存储小数部分。
运行长度压缩:针对固定域类型,记录域的实际长度而不是最大长度。
Δ编码:只记录值与前一个值的差异。
压缩对OLAP来说也很重要,因为大量读取压缩后的数据,解压开销相对较小。
本节介绍了列式数据库和数据压缩技术,这两者都对OLAP工作负载的优化至关重要。列式存储更符合OLAP的整表扫描查询特点,压缩能最大限度减少磁盘和网络传输开销。
数据库系统需要管理超过内存大小的数据集,无法直接在磁盘上运行操作。因此需要将部分数据从磁盘加载到内存中运行操作。
数据库系统中设计一块内存区域称为Buffer Pool,负责管理数据从磁盘加载到内存和从内存写入回磁盘的交互。
Buffer Pool 中划分等长的Frame,用于存储从磁盘加载来的Fixed Size Page。数据库系统其他模块请求Page时,通过Page Table找到在Buffer Pool对应的Frame指针返回。
如果Buffer Pool没有该Page,需要从磁盘加载该Page到任意一个空Frame。加载后更新Page Table,返回Frame指针。
加载Page后,Page Table记录Page与Frame之间的映射关系。如果Page在内存中修改,此时Page为”脏页”,但不会立即写入磁盘,等待事务安全点后批量写入。
管理数据在磁盘与内存之间移动的顺序性(Spatial Control)和时机(Temporal Control)。
顺序性考虑Page在磁盘与内存的物理位置,将相关Page排列在一起,减少随机访问开销。
时机管理考虑何时从磁盘读取数据,何时写入,这必须由数据库系统根据使用情况主动控制,不能由操作系统自动完成,以保证数据一致性。
Buffer Pool容量受限,需要根据访问优先级决定裁剪哪些Frame以腾出空间。常用算法有LRU和近似LRU。
数据库系统可以根据需要设计其他专用内存池,如不同大小Page对应的不同Buffer Pool。
Project一需要实现Buffer Pool管理模块,包括内存布局、Page Table、加载数据、脏页管理、内存替换等功能。
散列表是一种无序关联数组,它通过计算键值的散列值映射键到值,实现快速查找。散列表使用固定长度的键值对,并通过散列函数计算键的散列值以获取数组中的偏移量。
散列表具有以下特点:
散列表通过数组存储键值对,采用散列函数将键映射到数组中的索引位置。但直接映射可能造成碰撞,不同键散列值相同。
常见的解决冲突方式有:
此外,为减少碰撞概率和处理冲突带来的性能损失,通常会预留2-4倍空间。
散列表广泛应用于数据库系统不同场景:
它的优点是查找速度快,但并发访问难度大。后续将介绍如何实现线程安全的散列表。
B+树是另一种重要的数据库索引数据结构,将在后续课程中详细介绍。
B+树是一种平衡的查找树,可以高效地实现查询、插入和删除操作,时间复杂度为O(logN)。它允许每个节点有多个子节点, generalization了二叉查找树。
B+树最早于1973年提出,它可以保持键值的有序性,实现优化的顺序访问性能。与1970年代有限的内存和磁盘随机访问开销相比,B+树强调顺序访问可以减少I/O开销。
虽然随着SSD的普及,随机访问速度有所提高,但是B+树在大多数情况下仍然是优秀的索引数据结构选择。
B+树每个节点包含的键值数量在一个范围内(称为“顺序”),内部节点指针数量等于键值数量加一。叶节点仅包含键值,内部节点同时包含键值和子节点指针。
叶节点之间使用“兄弟指针”链接成一个双向链表,以支持顺序遍历。这来自于B-Link树设计。
通过对键值范围的划分,可以保证树的平衡性。树的高度为O(logBN),其中B为节点顺序,N为键值数量。这样可以实现日志级时间复杂度的操作。
B+树广泛用于关系型数据库管理系统内的索引实现。
为表建立B+树索引,可以提升查询性能。数据系统负责维护索引与数据表的一致性。
在事务型 workload中,99-100%的查询可能通过索引进行。否则需要全表扫描,性能会下降几个数量级。
在分析型工作负载中,主要用于加速联合查询。对较小表建立索引。
实际的B+树 Index实现还可能借鉴其他树结构的设计,比如B-link树的兄弟指针。同时还可以引入更多优化,比如组块或组页等技术。
B+树的页面大小取决于存储设备的性能:
对于性能较慢的旧式硬盘,页面大小建议为1MB,可以最大限度提升顺序I/O访问效率;
对于SSD,页面大小建议为10KB;
内存中的B+树,页面大小取512字节,保持与缓存对齐但不会浪费太多空间。
页面大小也与访问模式有关:针对单个键查询更适合较小页面;针对范围扫描更适合较大页面。
B+树节点的容量低于一半时应进行合并,但也可以采取更宽松的策略:
仅当节点为空时才进行合并;
允许节点容量低于一半但高于某个阈值,避免频繁修改导致的性能损失。
具体阈值需要考虑硬件性能及访问模式。
处理变长键的常见方法:
存储键指针而不是实际值,查询时需要二次查找,性能较低;
定长填充,将所有键补齐到同一长度再存储;
键映射表,每个节点内部建立一个映射表对应关系。
搜索键是否存在的常用方法:
线性搜索,直接扫描节点内所有键是否匹配;
二分搜索,但需保证键存储有序;
使用SIMD指令向量化线性搜索,以单条指令批量处理多组数据。
数据库系统首先要知道如何将数据存放在磁盘中,然后再读取到内存中。接着要了解如何基于索引等方式从内存中访问数据。现在我们将讨论如何执行查询请求。
数据库系统会将SQL查询转化为抽象语法树,然后转换成查询计划树。在树的底部是访问方法,比如顺序扫描表或索引。节点通过传递数据实现上级操作,如过滤、连接等。叶节点扫描数据并上送,内部节点对数据进行处理后下发。
这里显示的是一个逻辑计划,它只描述了数据流向,而不是实际访问和算法。在后的课程将介绍物理操作的实现,如各种连接算法。
同时要注意,由于数据量大,中间结果可能不再是内存完全容纳的情况。因此需要使用缓冲池,可能需要将部分结果写回磁盘。此时,选择算法时不仅看时间复杂度,还要考虑磁盘读写次数及顺序性。
排序操作在数据库中很重要。关系模型本身是无序的,但许多查询需要有序结果,如TOPN排名。此外,有时为了提升后续操作,数据库系统会主动对数据进行排序,比如使用排序去重。
接下来将分别介绍排序和聚合算法的 physical 实现方法。这与过去以时间复杂度为主的评判标准不同,重点在于利用内存和顺序I/O达到最佳效率。
连接操作是关系型数据库中常用的运算操作之一。它用于从两个或多个关系中重构数据,回答用户查询时需要将关系中的数据放到一起。
连接操作主要包括:
内连接:主要用于找出两个关系中匹配字段相等的元组组成的结果关系。
外连接:包括左外连接和右外连接。用于找出一个关系中所有元组与另一个关系中匹配字段相等的元组以及只存在于该关系中的元组组成的结果关系。
本节主要介绍二元内连接中的等值连接算法:
两表连接指连接两个表;
内连接指仅返回两个表中匹配字段相等的记录;
等值连接指连接条件中使用的运算符为等于。
主要的等值连接算法包括:
不同的连接算法在处理速度和内存要求上都有差异。
连接中的两张表一般会将小表设为外表,大表设为内表。但具体的表顺序由数据库查询优化器决定。
连接过程中,外表称为驱动表,内表称为被驱动表。优化器需要选择合适的表顺序和连接算法,以求获得最佳查询计划。
数据库系统在执行查询时需要决定采用何种查询执行模式。
迭代器模式是最基本和常见的模式。在这个模式下,每个操作节点都提供一个next()方法,用于获取下一个返回元组。
父操作节点通过调用子节点的next()方法获取数据,在获取到所有子节点数据后返回结果。
在迭代器模式下,每个next()调用只返回一个元组。而在物化模式下,会先将子节点的所有结果集存入内存,然后返回。
与迭代器模式类似,每个操作返回一批元组。但与迭代器模式不同的是,它采用向量运算的方式一次处理整批数据,效率更高。通常用于数据仓库场景。
数据库管理系统在执行扫描操作时,主要有顺序扫描和索引扫描两种访问方法:
对表数据进行插入、删除或更新时,需要记录日志或维护其他关联信息,来支持事务一致性、回滚等操作。
where子句、聚合等地方需要对表达式进行求值计算,如比较运算> < = 等。
项目二难度较大,且截止日期将近,所以建议同学们尽早开始进行,不要放到最后一周才开始。可以使用断点和程序分析工具来调试和优化代码。
具体地,可以采用以下方法:
可以更充分地利用CPU的多核资源,实现更高的吞吐量和更低的延迟。
现代服务器的CPU一般都集成多个核心,如果不能实现并行查询执行就无法充分利用CPU能力。
通过并行执行,即使部分查询线程等待I/O操作,其他线程还可以继续运行,从而提高响应速度。
只需要部署少量服务器即可满足需要,从而降低总拥有成本(TCO)。
并行数据库:资源如CPU、内存、磁盘等都部署在同一物理机器上,线程间通信速度快、可靠。
分布数据库:资源可能部署在不同数据中心或地理位置上,线程间通信速度慢、不可靠,可能丢包。
并行数据库对外呈现为单个逻辑数据库,但内部使用多线程并行执行查询。
分布数据库同样对外统一,但数据和计算可能分布在多个物理节点上。
进程模型决定系统如何支持同时来自多个用户的请求。它应当支持:
多个查询请求的同时执行。
当一个查询线程在等待I/O时,其他线程可以继续运行。
应用层不必关心内部是否使用了多线程。
通过将查询计划拆分为多个操作节点,与数据移动组织多个工作线程来执行不同节点任务,实现查询的并行执行。
需要考虑数据传输与负载均衡问题,使各工作线程执行效率达到最大。
I/O通常是性能瓶颈。系统需要了解I/O状况,将I/O操作和计算结合进行调度,实现I/O与计算的重叠执行。
查询优化器的工作是对给定的SQL查询找到执行成本最小且结果正确的执行计划。
执行成本是相对概念,在本课程中假设执行成本代表执行速度最快的计划。但实际上,执行成本也可以指网络消息数量、能耗等其他标准。
查询优化是一个NP完全问题,没有任何优化器能为所有可能的查询找到最优计划。优化器通过启发式和假设来限制可能的计划数量,寻找一个足够好的近似最优计划。
逻辑计划是查询中各操作的高级描述,如“表扫描表A”。
物理计划代表执行逻辑操作的确切算法,如“使用索引扫描表A上的索引”。
一个逻辑操作可能对应多个物理操作,反过来一个物理操作也可能实现多个逻辑操作。
SQL查询进入数据库系统后,首先可能经过SQL重写变换SQL字符串。然后解析出抽象语法树。查询优化器根据统计信息和代价模型生成候选计划,并选择成本最小的计划。优化器生成逻辑计划后,物理执行引擎将其转化为可执行的物理计划。执行引擎再依次运行各个物理算子,返回结果。
有研究开始探讨使用深度学习在某些限定场景下提升查询优化,如学习从历史执行数据中获取成本估计特征。但深度学习还不足以取代完整的成本模型。需要搭建完整的基础数据库知识体系作为基础。
交易是一个或多个操作的执行,从数据库系统的视角来看,只会看到读写操作。这些操作会执行一些更高级的应用程序任务或功能,以实现数据库状态的某种变化,反映现实世界中的某个方面。
交易是一个基本的数据库状态变化单位。关键点在于,不允许部分完成的交易。要么完成所有操作,要么一个也不做。即使只有一条操作,也被视为一个交易。
如果有两个线程在同一时间更新同一记录,可能导致数据损坏。这称为损失更新问题。
或者在从一个账户取款同时,系统崩溃。恢复后数据状态应该如何?
ACID是关于正确处理交易的4个数据库特性:
原子性(Atomicity):交易是一个原子单位,不可分割。要么全部成功,要么都不成功。
一致性(Consistency):交易前后数据状态一致,满足所有定义,业务规则和约束。
隔离性(Isolation):多个并发交易,它们之间不会互相影响,可以顺序执行般相当于串行执行。
持久性(Durability):已提交事务的效果,即使系统崩溃也不会丢失。
采用串行执行模型,从任务队列中顺序取出事务进行执行:
拷贝原数据库文件,交易操作写入新的文件
成功提交后,新的文件重命名为原文件,实现持久化
如果提交失败,保留原文件不变
可以保证事务原子性、隔离性和持久性,但无法支持并发执行。
数据库系统中有两种主要的锁类型:
除此之外,实际数据库系统中还可能支持更多细致的锁类型。
数据库系统需要明确处理事务之间可能出现的死锁情况。死锁可能发生在事务在同时申请彼此互相等待的锁资源时。
处理死锁的主要方法有:
后台线程定期检测死锁,选择一个事务强制回滚以解除死锁。
在事务申请锁时就检查是否存在潜在的死锁,如果检测到就直接回滚事务。
为保证事务串行化,数据库系统主要使用两阶段锁协议。其过程如下:
申请阶段:事务依次申请所需要的所有锁资源。如果资源可用就立即获取,否则进入等待状态。
提交阶段:事务完成后,将持有的所有锁资源全部释放。
两阶段锁协议可以保证任何一个时刻,数据库的锁图都是冲突分割的,从而实现串行化执行。
数据库锁的粒度可以配置在表、页或行等级别。不同粒度带来的并发能力与开销也不尽相同。
Two-phase locking协议有局限性,无法有效处理死锁情况。所以提出了时间戳顺序协议(Timestamp-ordering concurrency control)来解决这个问题。
Timestamp-ordering控制方法的基本思想是:每一个事务在开始时会被赋予一个时间戳,这个时间戳代表事务的顺序列号。事务根据其时间戳的顺序来执行,较早的事务优先执行。
具体操作如下:
事务在开始时会被数据库系统随机分配一个时间戳。
如果一个事务Ti需要访问一个数据obj,它首先检查obj的时间戳(如果obj之前没有被访问,其时间戳为0)。
如果Ti的时间戳小于obj的时间戳,那么Ti需要等待,直到其时间戳比obj的时间戳大为止。
如果Ti的时间戳大于等于obj的时间戳,Ti可以访问obj了。在访问过程中,obj的时间戳会被更新为当前最大的时间戳。
所有事务都按时间戳的顺序完整提交。
采用时间戳顺序可以避免死锁,因为它强制事务按时间戳大小顺序执行,从不会出现环路等待的情况。而且由于时间戳的随机分配,也可以避免优先级颠倒问题。但它的效率比两阶段锁低,因为频繁检查和更新时间戳的开销较大。
在上一课中,我们讨论了事务隔离级别以及采取锁机制(如2PL)可以实现可串行化。但是,只有基于锁机制的事务隔离级别在数据增加或删除时,可能会出现“幻影问题”。
下面是一个例子:
T1运行查询SELECT COUNT(*) FROM表得到结果为99。
T2运行INSERT INTO表新增一条记录。
T1再次运行相同的查询会得到结果100。这就出现了“幻影”–在T1运行过程中,虽然没有实际更新,但结果变了。
在T1事务提交前,数据库系统会重新执行T1中每个查询的扫描部分,看是否得到与原始执行结果一致。如果一致,则不存在幻影。
利用物理属性建立多维空间,对应每条WHERE子句锁定一个区域,判断是否与其他事务区域重叠冲突。理论上可靠但难以实现。
利用B树索引锁定索引键值或键范围,既可以锁定实际键也可以锁定虚拟键,避免插入导致的幻影。包括:
这是数据库系统常用的一种幻影解决方案。
Multi-Version Concurrency Control,多版本并发控制。系统维护每个版本的数据副本,每次事务都只会看到数据库在它开始时的版本。这种机制可以避免锁而不会产生幻影。
数据库系统可能面临的故障包括:
事务故障:事务处理过程中出现错误,如网络错误等。
系统故障:计算机硬件错误,如内存错误、断电等导致操作系统故障。
存储媒介故障:硬盘 read/write 错误,或物理损坏数据丢失。
数据库系统使用缓存池管理内存资源,将脏数据刷新磁盘。避免系统故障导致缓存数据丢失,数据库进入不一致状态。
每次写入缓存时,都同时将日志记录写入磁盘。系统重启后通过日志恢复缓存到磁盘的效果。但恢复时间长,磁盘开销大。
系统运行时先将所有数据修改写入日志,然后再 commit。系统重启通过重放日志将数据库恢复到一致状态。日志记录内容包括操作类型、页面地址和前后图片等。
周期性将所有脏页写入磁盘形成检查点,将过期日志清理,减少重启恢复时间。同时也能在系统运行期间进行错误检测。
相比影子分页,日志记录恢复速度快,磁盘开销小,更适合大多数数据库系统。它可以提供数据库ACID特性中的持久性保证。
ARIES 是一种数据库恢复算法。它由IBM在20世纪90年代初提出。
数据库系统在正常工作过程中,会记录所有事务对数据库的修改到redo日志中。redo日志条目必须先写盘,然后才能将脏页写盘。这样可以实现 Steel / NoForce 策略。
在恢复时,会重放redo日志中的操作,将数据库恢复到崩溃前的状态。还会回滚未提交事务中的修改,同时会记录回滚操作增加的redo日志条目。这可以防止在恢复过程中再次崩溃时导致不一致。
数据库系统使用逻辑日志记录号来追踪恢复顺序。检查点可以减少需要扫描的redo日志数量。三个恢复阶段分别是初始化、重放和回滚阶段。
ARIES 通过重复redo日志中的历史操作来实现数据库的可靠恢复能力。其采取的措施很小心,比如在恢复时也会将redo日志和脏页写入磁盘,以确保恢复的安全性和正确性。
CPU节点分布在不同机器上,但通过某种消息通道共享部分内存空间。例如RDMA技术。
每个节点有独立的CPU和内存,但共享一块存储磁盘,通过网络读取和写入数据。例如NAS或云存储S3。
每个节点拥有独立的CPU、内存和磁盘。节点间只能通过网络通信,比如TCP协议。
将数据拆分存储到不同节点上,根据业务需求选择 hash 、key range等策略进行分区。
如何在多节点环境下实现两阶段锁或OCC模式?答案是可以,但效率低下和实现难度大。
分布式数据库比单机数据库更加复杂,但利用独立节点可以实现更高的可用性、扩展性和容错能力。
分布式数据库系统可以通过水平拆分将数据库分区到不同节点上存储。通常采用共享 nothing 架构,每个节点只存储自己本地的数据分区。
事务处理(OLTP)工作负载中的事务通常需要对少量数据进行小规模读写操作,但同时可能有大量事务同时执行。为支持事务原子性,需要一个主节点来协调所有参与事务的节点,确保它们采用一致的状态。
申请事务的客户端首先联系主节点开始事务。主节点下发查询指令让其他参与节点执行操作。完成后,客户端向主节点申请提交,主节点再与其他节点协调是否可以提交。
选举主节点和判断事务是否可以一致提交,实质上都是要决定数据库新的状态。
分布式系统中可能出现节点暂时或永久失效的情况。需要考虑消息延迟、失联等情况下如何处理。
假设所有参与事务的节点都是受控的、守法的。否则需要更复杂的禁用分散节点协议。
自动提交协议和共识协议如Paxos、Raft可以帮助节点达成一致决定,实现事务的原子提交。
要实现高可用,还需要将每个节点的数据同步复制到多个备份节点,形成主从复制结构。
传统应用与数据库交互采用对话式API。应用连接到数据库服务,发送SQL查询,等待结果返回,然后等待下一个动作。
每个数据库系统都会实现自己的网络协议。客户端API如JDBC和ODBC用于与数据库服务通信。
每个查询都需要数据库服务进行解析、规划、优化和执行。且每次查询完成都需要等待应用的下一个指令。
可以减少网络通信往返次数
数据库服务能够及时感知数据变化并定义相应操作
数据库可以减少等待应用下命令的时间,提高事务执行效率
重要业务逻辑直接由数据库维护,不需要应用层重复实现
用户定义函数(UDF)允许扩展数据库系统本身没有的功能。
UDF通过输入参数计算返回值。计算逻辑可以用SQL语句定义,也可以用其他编程语言实现。
SQL定义的UDF仅由一系列SQL查询语句组成,按顺序执行,最后一个查询的结果作为函数结果返回。
可以在SELECT列表或FROM子句中使用UDF,但不能在WHERE子句中使用。
除UDF外,还可以使用存储过程、触发器定义事件反应、自定义数据类型以及视图来定义业务逻辑。
之后会通过Postgres实例展示UDF和触发器的使用方法。
Snowflake 在云基础设施提供弹性、可扩展性。它可以独立扩展计算和存储资源。软件作为服务提供,随时更新。云平台提供客户交流合作空间。
传统数据库架构迁移到云需要重构。Snowflake 采用原生云架构,自2012年开始研发。支持AWS、GCP、Azure等公有云。
使用云对象存储如AWS S3来存储数据。采用分块式存储,每个分块为数十MB不可修改列式文件。文件头存储各列信息用于快速访问。每个分块生成元数据如最大最小值等用于筛选文件。
使用云计算实例如AWS EC2。可以独立扩展Compute资源规模。提供计算隔离。用户秒级创建扩缩容计算资源。
负责客户端交互、元数据管理、查询优化等。实现享有和其他功能。
列式存储数据,支持向量运算批处理多行数据。采用推式执行模型下推结果。支持树形和复杂计划执行。
简单性不主动暴露参数。自适应性在执行时根据实际情况动态决策。提供多功能数据云平台。
利用元数据数据筛选跳过无关文件下载。向量化批处理减少 RepeatedMemory访问提速。树形计划下推模式高效处理。
以上总结了Snowflake数据库在云环境下的架构设计思路及优点,包含存储计算服务三大层次以及查询执行细节。
期末考试时间: 16日(下周一周加一天),下午1点。地点:疾塔4401教室一楼。
考试内容范围:中期考试内容到本学期最后一节课所有内容。不考核客座演讲和最后一节课的内容。
可以使用的考试工具:如电池计算器、笔和橡皮擦。可以使用单面纸手写总结,但不可以直接复制PPT内容。
考试前需要准备的知识:数据库管理系统的各环节如查询优化、事务处理、复旋等的高层次概念。不考核算法细节。
查询优化:逻辑查询计划到物理计划的转换,简单重写规则,统计信息收集与估算等。
事务处理:隔离级别、幻象、一致性检测模型、并发控制协议等。
跨地轰击机制:日志记录机制、ARIES recovered协议、崩溃恢复策略等。
分布式数据库:系统架构、数据复制、分区策略、两阶段提交协议等。
联接算法:广播联接Vs抛洒联接的场景选择。
其他:数据库存储结构、缓冲管理、垃圾回收等。