https://www.youtube.com/playlist?list=PLYp4IGUhNFmw8USiYMJvCUjZe79fvyYge
数据库指的是大规模有组织的数据集合。数据库管理系统(DBMS)是用于管理和访问数据的软件。关系型数据库管理系统(RDBMS)是目前最成熟的数据库系统类型。
数据库管理系统主要功能包括存储数据,提供数据访问工具,确保数据一致性和安全性,提供数据描述语言和数据操作语言。关系型数据库管理系统支持SQL语言。
最早的数据库系统肇始于20世纪50年代的大型计算机。1956年IBM造就了第一台磁盘存储机,容量5MB。1964年,IBM与美国航空公司合作设计了Sabre航班预订系统,这是早期数据库系统的一个代表案例。
70年代,随着关系模型的提出,Oracle与IBM分别开发了第一个商用和研究型的关系数据库管理系统软件。80年代多家公司也在此基础上推出了商用RDBMS产品。
随着需求的不断演进,现今市场上出现了许多特殊领域的数据库管理系统,比如内存数据库、时序数据库、图数据库等,它们针对不同数据类型提供了优化。
NoSQL数据库代表产品包括键值存储、文档型数据库和列存储数据库。Hadoop与Spark则专注于大规模离线数据分析。
关系数据库管理系统支持复杂查询语言SQL,它是一种非程序式的声明性语言。数据库通过ACID原则实现事务一致性。
主要的商业RDBMS产品包括Oracle、MySQL、SQL Server、PostgreSQL等。这些系统广泛应用于企业数据库部署中。
数据库软件市场规模超过500亿美元。云计算推动数据库迁移到公有云,NoSQL在云中使用率较高。关系数据库仍然是首选,如AWS RDS业务最速增长。
特殊数据库将越来越受重视。内存数据库在大数据量小的场景中表现优异。随着互联网应用producto深化,数据库技术形态将持续演进。
该课程的讲师是Joe Hellerstein教授,已在加州大学伯克利分校执教23年。他主要研究实时智能、可信和可解释系统。同时也是数据库领域杂志的主编。
本课程助教包括Ben、Brian、Daphne、Jaime ku、Kimmy、Kimberly、Locke Shaw、Michael等8名助教。他们都具有丰富的186课程教学经验,会在讨论班和办公时间对同学问题进行答疑。
学生需要按时观看视频、完成在线小测验、每周作业本和讨论班,以确保学习进度。助教和教授也会定期举行面对面答疑时间。学生需要自觉按计划学习,利用各种学习资源完成功课。
课程视频、作业和测验都提供在线学习。每周将有讨论班学生互相交流探讨。助教和教授也定期举行面对面答疑辅导。学生需要掌握视频内容,按时完成作业测验,以确保平顺完成本门课程。
这门课程采用在线视频教学的方式。每个视频为3-5分钟,每段视频结束后会有一个简短的测验,用来检查学生是否跟上节奏。这堂课的讲义和作业及测验都会发布在edX平台上。
每周都需要完成视频学习任务。视频后的快速测验是可选的。但每个周都需要完成必修的“weekly vitamins”测验来评估学生的理解程度。此外还有5个编程作业需要个人独立完成。会有两个期中考试和一个期末考试。考试作业等时间地点都会定期在官网和Piazza上公布。
编程作业包括使用PostgreSQL数据库操作 SQL 查询,查询橄榄球数据并进行分析。还包括实现B+树索引,实现多种Join算法,实现查询优化器和并发控制等内容,这些都需要用Java语言实现。
课程所有的交流都通过Piazza论坛进行。学生需要每天检查Piazza,以获得最新公告和通知。不建议直接给教师或助教发电子邮件,除非是私密问题。大部分问题都应该在Piazza论坛上发布。
有两次期中考,分数算入总成绩是以高分作准,分别是18%和12%。编程作业上可以使用三天的宽限期。每种“weekly vitamins”都可以放弃两次,但建议都完成以跟上学习进度。
如果学习压力大,可以寻求校方的心理辅导或健康保健服务帮助。如遇健康或家庭问题无法完成课程,可以申请休学。教师和助教也提供定期咨询,欢迎学生就学习或其他问题进行讨论。
SQL语言起源于1970年代IBM的系统R研究项目。系统R和伯克利加州大学的Ingres项目共同试图实践关系模型的设想。两项目各自有自己的查询语言,系统R使用SQL,Ingres使用QUEL。 1980年代,两种语言被应用到商业产品中,最终SQL在市场上占据主导地位。
SQL语法于1986年被标准化。历史上曾多次有人提议替换SQL,比如以面向对象数据库和OQL语言,但未能在市场上占领主导地位。2000年代Web应用兴起时也有XML与XQuery等,但同样没有取代SQL。最近十年有NoSQL运动主张废除SQL,但SQL依然被广泛应用。
SQL是声明性语言,开发者描述查询结果但不描述计算过程,后者由数据库系统决定。SQL实现广泛,范围从手机SQLite到云端大规模系统。SQL标准涵盖广泛但并非万能语言,更适用于数据查询与操作。SQL可与其他语言结合使用,实现高度表达能力。
尽管SQL不易全面替代,但40多年来它依然是处理结构化数据最广泛使用的标准语言。它声明性、特征丰富、可扩展性强,适合大多数数据操作场景。这门课将深入研究SQL使用方法和实现原理。
关系数据库包含一系列命名关系(表)。关系包含架构(字段名称和类型)和实例(数据记录)两部分。属性是字段,元组是行。关系、表、属性、字段和元组中的数据都可互换称呼。
关系架构通常固定,每个字段名字唯一,字段类型必须是基本类型而不能是复合类型。关系实例中的数据可重复,存储重复元组的集合称为多重集。
实例未满足架构要求,如第二行数据字段数不匹配
字段名不唯一,如两个名称为”num”的字段
字段数据类型为复合类型,如内含元组的数据类型字段”address”
关系的定义要求架构严格,实例必须与架构一致,字段名唯一,字段类型为基本类型。这有利于语义清晰和查询效率。
SQL包含数据定义语言(DDL)和数据操作语言(DML)两部分。DDL用于定义和修改数据库架构,如创建或删除表。DML用于操纵数据库实例数据,如查询、插入、更新和删除记录。
使用create table语句创建表,指定表名和各字段名及类型。可以为表指定主键,主键列的值不能重复。
如创建航海俱乐部数据库的“水手”表:
create table sailors(
s_id integer,
s_name char(20),
rating integer,
age float,
primary key(s_id)
)
同理创建“船只”和“预约”表,其中“预约”表的主键使用三列组合。
可以为表指定外键,用来表示表与其他表的关系。例如“预约”表中的“s_id”列指定为外键,引用“水手”表的主键“s_id”,表示记录对应的水手。外键默认引用引用表的主键列。
数据库管理系统负责根据DDL语句创建表结构并维护数据完整性。
SQL查询的基本格式是:
SELECT 项目列表
FROM 表名
WHERE 条件语句(谓词)
项目列表可以包括表中的字段或者表达式。WHERE条件语句选取符合条件的记录。
使用DISTINCT关键字可以去除结果集中的重复行。
ORDER BY子句可以按照指定字段顺序排列查询结果。顺序默认为ASC(升序),也可以使用DESC(降序)。排序可以使用多个字段,按照字典序依次排列。
LIMIT子句用于限制返回的记录条数。通常与ORDER BY一起使用,返回排序后的前N条记录。不使用ORDER BY时,返回结果不确定。
如一个查询学生表,选择名称、GPA、双倍年龄大小重命名为a2,条件为专业为计算机科学,排序根据GPA、名称、a2,取前3行。
SELECT name, GPA, age*2 AS a2
FROM students
WHERE department='CS'
ORDER BY GPA, name, a2
LIMIT 3
SQL支持使用聚合函数对查询结果进行汇总,常用聚合函数包括:AVG()平均值、SUM()总和、COUNT()计数、MAX()最大值、MIN()最小值等。
GROUP BY子句可以将表中的记录分组,每组计算一个聚合结果。可以按一个或多个列进行分组。组别可以出现在SELECT和HAVING子句中。
HAVING子句用于过滤分组后的结果。它会在GROUP BY分组和计算聚合函数后起作用,通过聚合表达式条件筛选组。
查询学生表,按部门分组,统计每个部门的人数并筛选人数大于2的部门:
SELECT department, COUNT(*)
FROM students
GROUP BY department
HAVING COUNT(*) > 2
单表查询主要语法有:
SQL支持COUNT、SUM、AVG、MAX、MIN等聚合函数,用于统计总数、和、平均值等。
DISTINCT可以放在SELECT后面去除重复行,也可以放在聚合函数内部如COUNT(DISTINCT)先去除重复再聚合。
如果SELECT字段未在GROUP BY中且未嵌套在聚合函数内,查询将报错,因为无法将多行值聚合成单行。
SQL支持重复行、聚合函数、顺序限制输出额外特性,扩展了关系模型,但语义仍然明确定义。同一个查询还可以有不同写法,数据库将选择最优执行计划。
SQL单表查询从以下几个 clauses 进行解释:
例如:
SELECT Department, AVG(GPA)
FROM students
WHERE gender='F'
GROUP BY Department
HAVING COUNT(*) >= 2
ORDER BY Department
顺序解释不同查询部分,可以清晰 comprehend查询语义和操作流程。
多表查询从句包含多个表,将表进行笛卡尔积(交叉乘积)。
给定两个表Students(id,name)和Courses(id,title),会生成包含所有可能组合的结果集Students X Courses。
给定Sailors表和Reserves表:
SELECT S.id, S.name, R.bid
FROM Sailors S, Reserves R
WHERE S.id = R.sid
多表查询先生成所有表组合,然后WHERE和SELECT进一步过滤结果,得到最终查询答案。这提供了一个概念模型,但是实际执行可能采用更高效的join算法。
SQL支持为表和列指定别名,解决表/列命名重复的问题:
FROM Sailors SSELECT S.name AS sailor_name自联接允许表自己进行连接,如连接Sailors表两次:
FROM Sailors S, Sailors R
WHERE S.age > R.age
SELECT子句中的列可以使用别名替换默认的列名:
SELECT
S.name AS sailor_name,
R.name AS sailor_name2
FROM ...
别名可以让SQL语句更简洁明了,解决潜在的歧义问题。
SELECT子句除可以查询列外,还支持各种算数和字符串表达式:
SELECT
age-5 AS age1,
2*age AS age2
FROM Sailors
WHERE name = 'Popeye'
WHERE子句的条件表达式也可以包含算术和字符串操作:
FROM Sailors S1, Sailors S2
WHERE S1.rating*2 = S2.rating-1
SQL支持两种方式进行字符模糊匹配:
LIKE关键字配合_%和%通配符
TILDE符合~结合正则表达式,更强大
没有FROM语句的查询可以作为计算器使用,直接返回表达式结果。
SQL还支持丰富的字符串函数,例如LENGTH(),SUBSTRING()等,扩展查询能力。
总之,SQL表达能力强大,不限于表查询,算术和字符串操作也全面支持。
WHERE子句支持使用AND、OR、NOT进行布尔逻辑运算,连接多个筛选条件。
使用布尔逻辑可以表达同样的查询选择,也可以使用集合运算如UNION、INTERSECT等表达。
但二者不完全等价,有时候一个表达方式更合理。
查找预定红色或绿色船只的水手ID:
WHERE color = 'red' OR color = 'green'
UNION
(SELECT ... WHERE color = 'red')
(SELECT ... WHERE color = 'green')
查找预定红色和绿色船只的水手ID:
WHERE color = 'red' AND color = 'green' //不正确
INTERSECT
(SELECT ... WHERE color = 'red')
(SELECT ... WHERE color = 'green')
第一个查询条件不站得住脚,第二种表达方式更合理。
总之,WHERE子句布尔逻辑和集合运算在某些情况下是等价的,但也有细微差别,需选择更合理的表达形式。
关系可以看作一个集合,其元素是各个元组。
集合语义下,关系视为离散集合,不包含重复元素。
多集语义下,关系视为包含重复元素的多集,记录每个元素出现的次数。
集合语义下为取并集,结果去除重复元素;
多集语义下为 UNION ALL,结果为各元素计数的和。
集合语义下为取交集,结果去除重复元素;
多集语义下为 INTERSECT ALL,结果为各元素在两个关系中的最小计数。
集合语义下为关系差,结果去除重复元素;
多集语义下为 EXCEPT ALL,结果为关系之间元素计数差的绝对值。
上述集合和多集操作符都按对应的集合数学规律进行处理,有别于传统关系操作。
SQL支持使用子查询将多个查询语句嵌套在一起。
根据子查询是否含参照主查询字段:
非关联子查询:子查询独立执行,不参照主查询字段
关联子查询:子查询中参照主查询字段,为每个主查询行执行一次子查询
使用IN/NOT IN比较主查询结果是否在子查询结果中;
使用EXISTS/NOT EXISTS判断子查询是否有结果;
使用>ANY/SOME比较主查询字段是否大于子查询可能的最大值中的任意一个值等。
参照主查询字段,为每行执行一次子查询,能实现非等值关联查询。
也称为除法子查询,查找预定了所有船只的水手。
查找没有未预定船只的水手作为结果
使用 NOT EXISTS 判断某水手是否存在未预定的船只。
最外层查询水手表;
中间子查询遍历所有船只表;
内层子查询检查水手对当前船只是否有预定记录。
最内层和中间层使用 boat 字段关联
中间层和最外层使用 sailor 字段关联
如果内层存在记录,则外层剔除此水手
没有剔除即意味没有未预定船只
找出在俱乐部预定过所有船只的水手
查询水手表中率评最高的水手。
返回最大率评,但不返回水手信息。
包含聚合函数但没有分组,会报错。
子查询找出所有率评,外层查询找出大于或等于所有率评的水手。
子查询找出最大率评,外层查询找出等于最大率评的水手。
排序后限制1条,返回率评最高水手,但无法返回并列第一的水手。
第一种可能返回并列第一水手,第二三种可能任意返回一位。
Arc Max定义对并列情况处理不明确,上述查询结果在并列情况下会有差异。
表之间根据条件进行连接,返回匹配行。条件写在ON子句中。
自动根据列名匹配进行等值连接,不需要写ON子句。连接列取两个表中名称匹配的列。
返回内连接结果与左边表不匹配的所有行,右表字段用NULL填充。
返回内连接结果与右边表不匹配的所有行,左表字段用NULL填充。
返回内连接结果与两边表不匹配的所有行,两边NULL填充。
视图是带有名字的查询语句,可以把复杂查询拆分成多个视图查询组合使用。
视图支持在查询中命名复用定义好的查询,但数据库不会实际储存视图结果,每次查询都重新计算。
可以使用视图控制权限,只授权访问简单视图而非 underlying表。
直接在from子句定义子查询,不单独命名,只在当前查询内使用。
使用WITH子句定义在同一语句内可重复使用的子查询作为临时表,支持多级子查询引用。
使用子查询分组求每个组最大值,外层查询匹配最大值的行返回同组最大值记录。
对SQL查询进行测试时,需要构建不同的数据集来测试查询正确性:
空数据库可能会使错误查询也返回无结果,无法发现bug
需要考虑测试数据中可能出现的异常情况,如特殊值、重复值等
只依赖默认测试数据可能错过部分实际bug
所以要负责构建各种测试用例,风险用例,来调试查询逻辑,找出潜在bug。
不要仅靠默认测试数据或结果来判断查询是否正确。
NULL表示未知值,任何数据类型都可能包含NULL。
表达式“变量 运算符 NULL”结果都为NULL。
可以使用“IS NULL”或“IS NOT NULL”判断NULL。
WHERE条件中如果有子表达式结果为NULL,则该行不包含。
AND、OR、NOT运算需要根据真值表处理可能为NULL的情况。
COUNT(*)包含NULL行,但COUNT(列)会忽略NULL列值。
SUM、AVG也会忽略NULL列值。
SQL是一种声明式查询语言,可以用来表达从数据库中查询数据的意图,而不用关心查询的实现细节。
数据库管理系统通过实现查询优化和相关算法,将SQL查询翻译成具体的查询执行计划。
理解SQL查询处理涉及到的数据结构与算法,这些知识不仅对关系型数据库实现重要,也支持NoSQL数据库、数据挖掘与机器学习等领域。
当掌握了查询优化知识后,就可以构建各种可扩展的计算系统。下一阶段会详细学习数据库实现的相关知识。
SQL学习的目的不仅用于关系数据库操作,更重要的是获取处理大规模数据的技能工具箱。
数据库管理系统是一个分层架构,各层之间通过抽象接口进行交互。
客户端提交SQL查询,数据库管理系统(DBMS)解析查询并生成执行计划。
DBMS主要模块有:查询解析优化、关系运算、文件与索引管理、缓冲管理、磁盘管理。
将SQL执行计划翻译为关系操作符组成的数据流,通过算子传递处理记录生成结果。
管理表记录组成的文件分页制,每个页存两张表记录。
将磁盘块映射到内存,为上层提供内存数据库的假象。
将页请求转换为物理磁盘块操作。
concurrency控制和恢复模块与存储管理模块互动,支持多用户并保证数据一致性。
将重点放在磁盘管理入口介绍DBMS各层。
磁盘通过页读写数据,一个页大小一般为32KB。读取和写入成为基础API。
磁盘读写速度极慢,相对CPU要慢数百万倍。需要优化读写策略。
从速度快到慢:寄存器>内存>固态硬盘>磁盘> tapes或网络存储。
数据库和日志常存储于磁盘或二级存储。小型数据库可能存储于固态硬盘。
访问L1缓存需0.5ns。读取1MB磁盘需2000万ns。
Jim Gray比喻:寄存器如头脑,内存如驾车1.5小时,磁盘如飞往冥王星2年。
数据库系统关注内存与磁盘间差异极大的执行效率问题。
磁盘由多个磁盘铱片和磁头组成。磁盘铱片以每分钟15000转的角速度旋转。
磁头可以移动到不同磁道读取数据。同一位置上的所有磁头对应的数据区域称为柱面。
磁道按扇区划分,每个扇区大小固定,可以读取写入数据的基本单位。页面通常为多个扇区组成。
读取磁盘块有三个时间开销:寻道时间、旋转延迟时间和实际读取时间。
寻道时间和旋转延迟时间是性能瓶颈,需要优化以减少这部分开支。
当前主流的闪存技术是NAND闪存。它支持细粒度的随机读,但写入单位较大,写操作涉及更多数据的移动。
单个闪存单元只可擦除2-3千次,需要对数据进行移动来均衡磨耗。这导致写入大于实际大小。
相比磁盘,闪存单价容量较低,一般为磁盘的10分之一。但读取速度大幅提升。
本地性能优于磁盘,但写放大效应导致顺序写优于随机写。技术不断优化随机写性能。
很多重要数据库实际规模很小,如日常气象数据25GB,美国人口普查200GB。但数据量快速增长,飞机每班产生0.5TB数据。
SSD性能提升巨大,但磁盘单价仍优于SSD。随着SSD价格下降,小规模数据库全采用SSD部署。
非易失性Ram可实现RAM级读速度但数据持久存储。新技术可能取代磁盘作为大容量存储。
小数据和大数据都将继续存在。近期大数据依赖磁盘。软硬件技术进步,SSD/NVMe替代磁盘速度加快。数据库系统将兼顾不同规模需求。
硬盘驱动器是一种机械式存储设备。它通过在磁盘旋转时使用磁头读取和写入磁盘中的数据块来工作。这给读写带来延迟:寻道延迟和旋转延迟。
固态硬盘(SSD)速度更快,但写入比读写更慢,除此之外也存在写入放大问题。
磁盘驱动器与内存之间的数据传输单位为磁盘块。一般大小为64KB。
磁盘块按顺序放置,相邻块之间读取速度更快。同轨道块、同地道块、相邻地道块读写速度依次降低。
数据库常使用文件系统接口管理磁盘空间。会将整个数据库映射到一个大文件中。文件系统优化顺序访问,保持文件块顺序性,满足数据库对顺序访问的需求。
文件系统限制文件在单盘。数据库会将逻辑文件分布到多个文件系统文件中实现跨盘存储。
磁盘空间管理层实现读写页面API,管理数据库在磁盘上的逻辑空间。它跨文件系统保持块(页面)的顺序性,隐藏细节,为上层提供连贯的顺序访问。
它的职责是:
主要技术包括:缓存、预取、写缓冲等,实现读写效率和利用率的提升。
数据库中的表在磁盘上以文件形式存储,文件包含多个页面,页面包含多个记录。数据库会将表映射到逻辑文件上。
记录在内存中以字节数组形式表示,多个记录按页面方式打包保存到内存页面中。文件系统管理物理磁盘上的文件和页面,页面可加载到内存中。
数据库文件可以跨多个操作系统文件和机器,也可以直接在磁盘设备上实现而非通过文件系统。
数据库文件可以采用无序堆文件、聚集堆文件、排序文件和索引文件等多种方式组织。
无序堆文件记录在页面和页面内没有特定顺序,它实现为双链表,包含头页面和数据页面。
头页面指向全页和有剩余空间的页面链表。这样查找需要遍历链表比较低效。
改进方案采用页面目录,包含多个头页面组成链表。每个头页面记录每个数据页面的剩余字节和指针。
通过扫描头页面 quicker找到满足需求的页面,仅需要加载少量页面,效率更高。头页面本身也更易缓存。
所以总结来说,数据库表对应磁盘文件,文件由页面组成,页面由记录组成,记录以字节形式存储。
页面包含头部区域和数据区域。头部区域包含该页面的元数据,如记录数量、空闲空间大小等。
对于固定长度记录,有两种页面布局:
记录紧密排列在数据区域,通过记录编号直接计算记录在页面中的偏移地址。这种布局下,删除记录后需要重排记录空间并更新目标记录的地址。
使用位图 tracks 每个槽位是否占用。记录 ID 由页面 ID 和槽位数组成。这种布局下,删除记录只需清除相应的位,无需移动其他记录,记录 ID 保持不变。
仅需要存储位图作为开销。这种布局下插入和删除更高效,记录 ID 更稳定,是较好的选择。
在固定长度记录的情况下,页面可以有效利用空余空间来保存额外记录,节省存储开销。
对于变长记录,有以下问题需要解决:
如何确定每个记录的边界?
插入和删除记录后如何管理空格?
为解决这些问题,采用目录式页格式:
将元数据放在页尾,方便管理。
使用槽目录管理每条记录。每个槽包含记录长度和偏移地址。
删除记录时修改对应槽即可,而无需移动其他记录。
插入记录时,查找槽目录中空闲槽或页尾空间,然后记录长度、偏移地址。
为避免内部碎片,可以定期重新整理记录位置。但这对外部查询无影响。
可以立即或惰性地进行重新布置。
用槽计数器追踪槽使用情况。需要时可以增加槽数量。
总体来说,目录式页格式适用于变长和固定长度记录,支持高效的插入、删除和重新布局操作。它是最通用的页面存储结构。
固定长度字段布局:
字段类型信息存储在系统目录中,记录本身无需存储类型。
直接使用内存格式存储,无需进行格式转换,性能高效。
可以通过字段长度之和计算某个字段在记录中的偏移量。
可变长度字段布局:
将所有可变长度字段移动至记录尾部。
记录头部包含指向每一个可变长度字段的指针。
固定长度字段按顺序排列在记录头部。
处理空值时,相应指针指向下一个字段指针所指位置。
以上布局可以直接、高效访问任何字段。改善了使用定分隔符方式的一些问题。
总体来说,采用记录头指针访问可变字段的方法,同时保留固定顺序布局固定字段,可以很好地支持查询任一字段的需求。
这节课主要探讨了关系型数据库物理存储结构的抽象与逻辑结构对应关系:
逻辑结构是表,对应于文件中的多个页。
抽象结构是记录,它包含多个字段,实现二进制表示存储。
记录字段可采用固定长度或可变长度布局。固定长度直接计算偏移,可变长度使用指针访问。
将记录存储在页中,例如使用槽式页框架。每个槽包含记录长度和偏移地址。
系统目录存储表结构定义。记录无需携带类型信息,从而保证高效紧凑。
总之,通过层层映射关系,实现了逻辑结构表到物理存储结构记录和页的对照,支持关系模型的快速查询与操作。这奠定了关系数据库兴起的基础。
数据库管理系统的底层包括文件管理与索引管理层。
文件组织结构包括:
堆文件:适用于全表扫描,无固定顺序。
排序文件:适用于需要顺序访问范围内记录。
集群文件与索引:通过将相关记录分组实现快速查找与更新。
访问成本估算必须考虑文件组织方式和访问模式的匹配程度。
此次讲授目标:
总览各文件组织方式原理及适用场景;
明确假设,并以具体成本估算量化比较不同方案;
以简化的模型提供成本参考,目的在于理解影响因素关系;
为后续查询优化搭建基础,需要识别不同访问策略成本以选择最优方法。
通过分层逐步深入,理解关系数据库底层实现的核心思想。
本次学习以简单模式和假设阐述文件组织成本影响 proportional,为后续优化打基础。鼓励提高假设质量深入研究。
堆文件与排序文件的区别:
简单示意:
扫描所有记录成本计算:
对于堆文件和排序文件:
原因:
本次介绍从简单示例视角介绍堆文件和排序文件在全表扫描时的相同成本模型。
期望成本计算:
所以排序文件等值查询成本为log2B,优于堆文件的B/2。
本次概述等值查询在堆文件和排序文件中的具体操作和成本模型计算。
范围查询不同于等值查询:
所以堆文件需要全扫描,排序文件可以利用排序属性优化成本。 但取决于匹配块数量,可能比堆文件更高。
本次介绍范围查询在不同文件组织方式下的具体操作和成本模型。
总成本=log2BD + BD/2 = O(B log B)
数据插入需要找到正确位置并修改后续记录,相较堆文件多一步定位操作。 但排序文件可以利用有序特性,平均情况下成本仅仅高出一个对数项。
本次总结了数据插入在不同文件组织方式下的具体操作和成本模型。
成本分析:
总成本:log2B + B
数据删除需要找到具体记录并修改后续记录,不论是堆文件还是排序文件都需要额外操作来“填补”删除位置。 但排序文件利用有序性,定位成本优于堆文件。两种文件在删除后续记录上的成本相当。
本次总结了数据删除在不同文件组织方式下的具体操作和成本模型。
本次总结了不同数据库操作在堆文件和排序文件下的时间复杂度,并给出可以使用索引来进一步优化的提示。
但是索引本身也会带来一定开销,实际选择需要综合考虑查询和修改频率以及数据量大小来权衡成本。
这为后续内容引入索引技术打下基础。
索引是一种数据结构,它支持通过搜索键快速查找和修改数据库中的数据项。
索引支持不同类型的查找操作,如等值查找、范围查找、地理形状查找等。
搜索键可以通过关系表的任意子集字段组合而成。
索引中存储的典型数据项为“键-记录ID”对。键对应关系表中的搜索键值,记录ID指向堆文件中的实际元组。
索引应支持插入和删除操作,及时维护与数据一致性。
B+树是最常见的索引结构。还有哈希索引、R树用于空间数据等。
本节简要介绍了索引在数据库系统中的功能和原理思想。为后续详细介绍各种索引数据结构奠定基础。
首先对输入堆文件内容进行排序,以搜索键为排序依据生成有序文件。
建立关键字-页面指针对的搜索文件,用于二分搜索。但文件规模随数据线性增长。
重复对搜索文件建立搜索文件,构建高树状索引结构。顶层索引文件仅包含一页。
每个节点包含关键字-指针对。对任意节点,关键字在KL 和 KR之间的Tuple都在左侧,大于或等于KR的在右侧。
这样构建的递归索引结构查询效率较高,参与查询的页面块少,且索引规模随数据增长较缓慢。它解决了直接对有序文件建立二分搜索时,树深度和单次IO次数大的问题。
在ISAM树中搜索关键字,从根节点开始进行二分搜索,依次到达叶子节点对应的数据页。复杂度为O(logF N)。
插入新节点后,需要对包含该节点的数据页进行排序,确保顺序正确。如果数据页已满,则分配溢出页存储额外数据。
如果数据集始终增长,溢出页将形成链表结构占据大部分文件空间。最终导致插入和搜索效率退化成线性时间。
ISAM文件存储数据页和索引页,数据页位于前,根索引节点优先,其他节点以广度搜索顺序排列。
支持顺序扫描,每个索引页包含大量指针实现高弹性。
插入操作添加溢出页易导致性能下降。不适合频繁修改的场景。
ISAM可以支持有效搜索,但插入性能不佳是其主要短板。后续索引结构将针对此问题进行优化。
B+树是ISAM的改进版本,具有动态平衡和高效插入删除算法。关键区别在于B+树不会产生溢出页问题。
Interior节点和ISAM相同,采用(key,pointer)对格式。叶节点存储实数据。
叶节点数据无需顺序排列,通过previous和next指针链接。
树的秩D决定每个节点可包含的最大entry数为2D+1。除根节点外,其他节点填充度需≥1/2。
以128KB页和秩1600为例,单层树容量超过450万条,双层树近10亿条。 B+树体积能高效支持大数据量访问。
与ISAM相同,从根依次效二分搜索到叶子节点对应数据。时间复杂度O(logBN)。
B+树通过动态平衡、高填充度和链式存储等设计,有效支持大量数据的随机访问与动态修改。
从根节点开始,依次对比每个内节点的关键字,选择分界点指针所指向的子树继续搜索。直到找到对应叶子节点数据项。
每个叶子节点数据项包含一个关键字及指向实际记录的指针。指针使用页面ID和记录ID唯一定位一个记录项。
通过B+树搜索找到对应关键字对应的叶子节点项,从中获得记录指针,就可以在数据文件中直接访问该记录。从而实现根据关键字高效查找特定记录的功能。
与ISAM相同,为O(logBN),B为树的阶,N为数据量级。随数据规模的增加,路径长度几何增加,但仍保持在对数级别,支持高效大数据访问。
B+树搜索算法简单明了,利用分治思想高效定位到对应数据项,为数据库索引提供了重要支持。
1.搜索找到合适的叶子节点。2.如果有空间直接插入,否则分裂叶子节点。3.更新next/previous指针。4.如果分裂引起父节点溢出,递归分裂内部节点。
将节点数据平均分成两半,新增一个节点。关键字下截至叶子节点,不上传。
将2D+1个项平均分成两组,低值组留在原节点,高值组和中间关键字上传至新父节点。关键字上传替换原值。
生成新的根节点,原根节点和新节点作为子树。树高加1。
搜索、插入:O(logBN) 删除:O(logBN)
B+树通过动态平衡和高效分裂策略,支持大容量数据的有序快速搜索和动态修改。
1.搜索找到合适的叶子节点。2.如果有空间直接插入,否则分裂叶子节点。3.如果分裂,将数据平均分为两组。4.新建节点,更新指针。5.如果分裂引起父节点溢出,递归分裂内部节点。
将数据平均分为两组,新增节点。关键字下截至叶子节点,不上传。
将数据平均分为两组,低值组留在原节点,高值组上传至新父节点。
所有搜索路径长度相同。插入时增加树高或树宽,保持平衡。
数据只存储在叶子节点。每个非叶子节点指向子树,存储访问子树的关键字。支持高效搜索和动态修改。
多次插入效率低,网页杂乱无序。批量加载数据按顺序写入,缓存命中率高。
先填充叶子节点,指针指向完整页面。分层建立内部节点指针。插入数据会增加树宽或树高,保持平衡。未填充部分为空置,后续插入不断向右填充。
批量加载B+树通过排序、顺序写入等方法,大幅提高构建过程效率。是实际应用中常用的优化方法。
ISAM:只能修改叶子节点,使用溢写链会降低效率。
B+树:支持高效插入删除,保持树平衡,查询效率O(logn)。支持动态调整结构。
通常深度3-4,经测试后插入删除后的利用率为2/3。适用于大多数需求,数据库系统优化度高。
批量加载数据库能极大提升构建速度。内存优化页面布局。并发插入删除需要并发控制。
B+树广泛应用,热点优化点。内存数据库可能使用新版B+树结构。保证高并发操作效率。
B+树通过自适应增长和多种优化,为数据库索引提供了高效的通用解决方案。是数据库中最重要也是发展最成熟的索引结构之一。
1.支持的查询类型 2.索引键的选择 3.数据存储方式 4.可变长索引键处理 5.成本模型
1.查询类型决定索引使用场景 2.键选择影响查询种类 3.存储决定性能 4.键长影响效率 5.成本模型衡量各项因素
分析任何索引结构都需要考虑上述几个方面:支持查询、键选择、存储实现、长度优化和成本比较。这可以指导索引的设计和应用。
B+树支持一维等值和范围查询。哈希索引只支持等值查询。
重点介绍一维等值和范围查询支持。其他类型如高维、近邻、字符串查询在实际应用中也很常见,但需针对不同数据和查询设计适当索引。
用多个字段组成查询键,按照指定顺序对记录进行排列。
用第一个字段比较,相同则用第二个字段比较,以此类推直至所有字段比较完毕。
前M个字段是等值查询,第M+1个字段可以是范围查询。
以年龄和工资作为复合键。等值查询直接定位,范围查询扫描匹配记录。顺序决定匹配范围。
优先等值匹配,剩余记录按范围查询。需要检查始末以确定结果。
索引中可以直接存储数据的值(Alternative 1),或存储指向数据位置的指针(Alternative 2、3)。
在叶子节点直接存储元组值,数据仅存储在索引中。
在叶子节点存储关键字和记录ID(如页号+位置),数据存储在外部文件中。
类似Alternative 2,但对同一关键字的记录ID采用一个列表的方式存储,篇省空间。
如果索引采用指针方式,外部文件数据可以是聚集存储或非聚集存储。
Alternative 1占用 más 存储空间。Alternative 2、3支持多索引,但需要外部文件存储实数据。
聚集索引是指索引引用的外部数据文件中的记录,保持与索引顺序基本对应的顺序。这可以提高回读效率。
非聚集索引是指索引引用的数据文件中记录的顺序与索引顺序无关,指针可能指向任何位置。
聚集索引回读效率高,顺序读取外部文件。但插入时可能导致非聚集,需要重新排序。非聚集索引插入速度快,但回读性能差。
聚集索引适用于范围查询,支持压缩。顺序读取减少I/O操作。
聚集索引插入后可能导致非聚集,需要重新排序外部文件。需要留足插入位置。
长期插入后可能变为非聚集,需要周期性重新排序。也可以背景 incrementally 重新排序。
对于可变长度的字符串键,原有按条目数定义的占用率需要重新定义。提出按已使用字节数来定义占用率,页至少达半满。
只保存键与左邻键之间的区分前缀。partition 略有不同但可正确操作。
共同前缀提取为页头,剩余部分作为分割键存储。可与前缀压缩同时使用。
在页分裂时计算最小区分前缀,作为新的分割键。
高频第一列值可以提取为页头,只对低频后续列进行分割。大幅减少重复存储。
定义新的占用率,提出压缩策略可以有效增加页容量,支持字符串和复合键建立B+树索引。
使用聚集索引相比顺序文件,每页记录个数减半,扫描成本由BD变为1.5BD。
成本为log_F(B/E)D+D,F为内节点粗粒度,E为叶子节点记录数。
成本为log_F(B/E)D + 1.5BD,范围扫描叶子节点和数据文件页。
成本为log_F+3D,修改叶子节点和数据页。
聚集索引使树遍历和数据扫描顺序连续,减少随机I/O。SSD降低随机I/O成本,更优势聚集B+树。但顺序I/O比随机I/O贵100倍,范围必须足够小 select。
研究复合查询关键字的词汇顺序与查询谓词匹配情况。
alternative 1:索引存储完整元组;alternative 2:存储记录ID引用数据;alternative 3:各索引列存储记录ID列表。
仅针对alternative 2和3,聚集索引能大幅提升性能。
修改满度概念按字节数定义,提出前缀压缩和后缀压缩技术。
大O分析优于顺序文件,但顺序I/O比随机I/O效率高100倍,范围查询必须选择性强。
提及多维空间、字符串等更复杂查询需求的索引结构。
DBMS包含SQL客户端、文件及索引管理、缓存管理、磁盘管理模块。
实现文件和索引管理对页操作的内存API,实现磁盘管理对块操作的模拟。
文件索引管理要求RAM页操作API,磁盘管理要求磁盘块操作,缓存管理作为中间层,将二者连接起来。
缓存管理模块主要配置内存缓冲区,实现页面读取写回、页面置换等功能,为上层提供虚拟内存页服务。
缓冲管理模块在内存中管理称为缓冲池的一组页大小的内存块(帧)。
高层请求读取指定页,缓存管理将其从磁盘读取到空闲帧内存,建立请求页与帧间映射关系。
后续对同一页的访问,直接使用帧内存地址而无需磁盘I/O。
读请求的新页无法在缓冲池找到空闲帧时,需要选择一个占用帧下放到磁盘,以腾出空间给新页。
缓存管理维护页表,记录每个请求页当前映射的帧位置,实现内存与磁盘页地址转换。
内存页内容修改后与磁盘内容不一致,称为脏页。
缓存管理通过每个帧附加一个脏比特,标记其映射页是否为脏页。
需要将脏页写入磁盘,实现内容持久化。缓存管理通过磁盘管理将脏页写回。
多线程对同一页独立读写时需要并发控制,防止数据不一致。
若崩溃时存在脏页,需要通过恢复模块来保证数据一致性。
并发控制模块管理多线程页访问同步;恢复模块在崩溃后重新构建页状态。
初始化时将一大段内存割成固定大小的帧,模拟缓冲池结构。
使用数组数据结构存储各帧对应的页ID、脏比特、锁定计数等状态信息。
通过页表可以快速查找页在帧中的物理位置,并追踪其是否脏页、锁定状态等动态信息。
缓存管理将帧当作内存页使用,动态管理其中页面的读写和替换工作。
绘制缓冲池及页表示例,清晰显示各帧页所对应状态信息的细节存储实现。
使用锁定计数记录页访问次数。读者将页锁定,操作完成后解锁。
修改页后,读者将脏位设置为1,告知缓存管理器。脏页替换时写入磁盘。
缓存管理器选取锁定计数为0的页替换。若全部锁定,则等待解锁后再选取替换页。
决定缓冲池满时,按何种标准选择待替换页,常见策略有LRU、FIFO等。
描述缓冲池状态变化过程:读者读页->锁定->操作->设置脏位->解锁;缓存管理器替换尾页写入磁盘。
回答预设问题:如何识别脏页?如何处理脏页?如何知悉页使用状况?如何选择替换页?等。
tracking每个帧最后一次使用时间。选择使用时间最久的帧替换。
在页表中添加最后使用时间字段。每次访问更新该页最后使用时间。替换时选择时间最早的页。
直接扫描选择时间最早页效率低,时间复杂度O(n)。
使用优先级队列维护最后使用时间,找出最小时间页复杂度降为O(Logn),加快速度。
近似LRU,复杂度常量级别,进一步提升替换效率。
适用于当前高热点数据重复访问场景。但实现成本较高,Clock策略效率更高。
假设缓存页排成一个圆圈, equivalence“时钟指针”指向下一替换页。每次指针顺时针移动一格。
每页设置一个标记位记录最近被访问。指针遇到标记位为1的页将标记位置0,继续寻找。
近似LRU,但实现简单高效。每个页有两次机会免换,较好利用缓存。
详细描述读页、写页、标记位更新和指针移动规则。
连续扫描一个大文件,每次扫完都从头开始。
顺序访问导致页面访问不具有时间局部性。LRU无法很好利用缓存。
更适合顺序访问的缓存替换策略,如FIFO。也可以采取预读技术,提前将后续可能用到的页读入缓存。
通过跟踪每次请求类型和命中率,描绘LRU在顺序扫描下的缓存未命中问题。
最常使用页(MRU)替换策略,以最近使用的页优先保留在缓存中。
首次扫描完全缓存未命中。但之后:
缓冲池大小B,文件大小N(大于B)
LRU重复扫描表现很差,命中率长期为0。而MRU能很好利用缓存,支持顺序访问场景。
MRU优于LRU处理重复顺序扫描访问,体现出它考虑了最近访问的优先性。
预读是提前读入后续可能访问的页,掩盖I/O延迟,提高单个I/O操作的利用率。
数据库系统实现自己的缓存池,提高跨操作系统/文件系统的可移植性。
操作系统缓存有强制刷新 API 限制,数据正确性无法保证。
数据库系统拥有更多页访问模型信息,可进行更智能的预读和替换。
LRU适用于随机访问,MRU适用于顺序扫描。数据库系统可以根据查询类型选择合适策略,或设计出兼顾两者优点的新策略。
大小位于物理内存和打开文件的实际大小之间,考虑空间换时间的平衡。
数据库系统独立实现缓存机制,利用查询信息进行优化,提高单个请求的性能和整体吞吐量。
在文件管理器和磁盘管理器之间提供中间层,动态映射磁盘页到内存地址,确保请求页在内存被固定。
页固定计数用于防止替换,脏位记录页是否被修改过需要写回磁盘。
LRU、MRU、Clock等策略旨在替换引用可能性低的页,预读可能被使用的页,降低缓存失效率。
顺序扫描会影响LRU和Clock策略,LRU命中率长期为0,MRU和Clock会逐步增加命中率窗口。
了解页固定计数和脏位用途;熟悉各策略区别和工作原理;能独立执行替换策略模拟。
SQL是一种声明性语言,关系算术是一种操作性语言,用关系算术表达的操作符树可以实现SQL查询。
关系演算源于逻辑学,声明性;关系代数源于集合论,操作性,提供关系变换的顺序描述。
Ted Codd证明关系演算与关系代数在表面上等价,允许使用操作性关系代数实现声明性关系演算查询。这为SQL的实现奠定了重要基础。
SQL查询经解析生成关系代数表达式树,优化器生成执行计划,按迭代器模式顺序执行单表操作。
关系代数主要操作符定义与功能描述,为后面查询执行层肩负重要基础任务。
关系代数是一组从关系映射到关系的操作符,结果依然是关系。操作符可嵌套使用。
包括投影(选择关系中的某些属性)和选择(根据条件选择部分元组)。
以π表示,结果遗留指定属性列。如果有重复值,默认去重。
以σ表示,根据条件过滤数据。结果类型与原关系一致,无需去重。
π{姓名,年龄}只保留关系中姓名和年龄两列。
σ评级>8过滤评级大于8的元组。
π和σ可以组合,例如:σ评级>8(π姓名),先过滤后投影。但π前操作可能导致类型错误。
交集与连接常用,提供更高层次的操作。但底层还是使用基本操作符实现。
关系代数操作具有明确的输入输出类型,可实现静态检验。
并运算符符号为U,需求两个关系的结构兼容,即字段数和类型一致。
使用集合表示法,并运算取两集合的并集,去除重复元组。
差运算符符号为-,需求两个关系的结构兼容。
使用集合表示法,差运算取第一个关系中不在第二个关系中的元组。顺序影响结果,不具有交换律。
交运算指标为∩,需求两个关系的结构兼容。
使用集合表示法,交运算取两个关系中共同包含的元组。
交运算可定义为:S1∩S2= S1 - (S1 - S2)
笛卡尔积不需求两个关系的结构兼容,直接连接各自的结构作为输出结构。
笛卡尔积取第一个关系中的每个元组与第二个关系中的每个元组进行配对组合。
重命名操作仅改变关系和属性的名称,不影响数据内容。用于修改结构定义。
连接操作允许从多个表中获取数据,是关系数据库常用操作之一。
连接操作是复合操作,可以定义为先执行笛卡尔积,然后在连接条件theta上进行选择。
等值连接 theta 为多个等值条件的逻辑AND联合,如联系多个字段相等。
自然连接是等值连接的特例,其theta隐含为匹配字段相等。连接后会去除重复字段,只保留唯一字段。
例如通过字段s_id实现预订表与水手表的等值连接,获取预订信息和相关水手数据。
也可以通过一个表自身实现自连接,比如查询每个水手的年长水手等。
自然连接常用于外键关系,如预订表通过s_id连接水手表获取水手信息。
连接需要效率高的算法实现,避免笛卡尔积后选择的低效方式。
关系代数中常用γ符号表示分组和聚合操作。
γ接受分组字段和聚合函数作为参数,可以实现对输入关系进行分组和聚合计算。
例如γ age, average(rating) 对关系按age字段分组,计算每个组的rating平均值。
也可以在γ后添加having子句条件,只输出满足条件的分组,如γ age, average(rating) having count(*) > 2仅输出行数大于2的分组。
有书本将γ拆分为两个操作:
分组操作γ实现分组和聚合但不添加过滤条件
having操作实现根据聚合条件过滤分组结果
此外回顾了关系代数基本操作:选择、投影、笛卡尔积、并集、差集等,以及衍生的交集和连接等复合操作。
关系代数通过指定操作顺序,更接近程序语言,而不像关系算术语言只关注结果。
为大数据量排序设计高效算法称为出内核算法。常用策略有流式单次扫描和分治。
对元组进行汇聚操作时需要把相关元组聚集在一起,如去重、分组统计。
用户查询结果需要排序输出,如SQL的order by子句。
建立B+树索引需排序插入。
数据库数据量往往远大于内存,无法直接将文件读入内存排序。
虚存无法理解排序算法,会导致大量随机磁盘IO,性能极差。
以固定大小缓冲区流式处理:
如此设计只用两个固定大小缓冲区,就可以高效地处理超出内存的数据集。
为提高流式处理算法的并行性,可以采用双缓冲优化。
使用两个线程分别处理计算和IO操作
计算线程将数据从输入缓冲读入,处理后写入输出缓冲
IO线程负责清空输出缓冲、写入磁盘,并填充输入缓冲
两线程通过交换已处理完毕的缓冲来实现流水线式运作
计算线程在IO线程等待磁盘响应时可以继续计算,利用磁盘本身并行特性。
计算和IO同时进行,提高效率
计算线程可以预读数据,缓冲交替利用,消除阻塞等待
实际实现要考虑内存开销。后续分析将抽象为单线程模型,方便理解算法本质。
双缓冲广泛应用于数据库等将IO与计算耦合的系统,是基础优化策略。
给定文件F存储n块记录,两个辅助磁盘每个大小大于n块,内存B块大小小于n块。
排序目标:输出有序文件F_s,记录顺序按指定条件排序存储在磁盘。
哈希目标:输出文件F_H,记录按哈希值顺序存储,相同哈希值记录连续存储,不同值记录不相隔。
F_H顺序未定,但相同哈希值记录依然连续存储。
考量参数:
提供统一标准,方便后续算法分析。
采用分治思想,将文件分批次排序合并:
首轮(Pass 0)分页读取数据,内存快速排序每页数据,写入磁盘。
后续轮次(Pass 1, Pass 2…)依次合并前一轮生成的子序列:”运行”(运行长度为每轮页数)。
Pass 0: 每页数据在内存快速排序,生成单页运行存储在磁盘。
Pass 1: 取两页运行 Loading到缓冲区,顺序插入输出缓冲并写入磁盘,生成长度2页的运行
Pass 2: 合并长度2页的运行,生成长度4页的运行。
两路排序给出基本思路,后续算法会采用更高效的多路合并方式。
优于两路合并,利用更多内存缓冲区B:
Pass 0:每次读B页数据快速排序,输出长度为B的运行
Pass 1起:每次并行读取B-1个运行,并入输出,运行长度变为B*(B-1)
Pass 0: 生成n/B条长度为B的短运行
Pass 1: 并行读取B-1条短运行,合并输出长运行
趟数为O(log_{B-1}(n/B))
每趟I/O成本2n
整体时间复杂度为O(nlog_{B-1}(n/B))
约需要√B块内存才能在两趟内完成排序
外部排序充分利用 disks I/O 并行特性,以对数级时间完成大规模排序任务。
外部Hashing用于大数据集合中元素分组,同值元素位于同一位置。
Divide阶段:读入数据流,根据Hash函数HP将数据分区写入B-1个输出缓冲区。
Conquer阶段:读入分区,形成内存Hash表,根据另一Hash函数HR将表写入磁盘,同值元素相邻。
1) 输入流经过一个输入缓冲区,根据HP寻址输出缓冲区,生成分区。
2) 读入分区形成内存Hash表,再根据HR逐桶写入磁盘。
1)Divide和Conquer阶段I/O成本均为2n。
2)整体时间复杂度为4n。
3)√n块内存可以处理n项数据集。
若分区大小不均,需要采用递归分区,继续划分过大分区。
当Generate的输出分区大于B-1页时,需要对其进行递归分区。
使用新的Hash函数HsubP1对过大分区进行递归划分。
继续进行Divide和Conquer阶段,生成子分区。
退出递归后,过大分区被劈成一个整体输出分区。
若有极为高频的值,例如性别只有几种,则递归分区后依然会生成相同的子分区。
当识别出子分区完全包含相同值时,直接将其作为一个分区输出,而非继续递归。
递归分区可以解决分区大小不均匀的问题,但需要处理高频值会产生的分区递归闭环情况。
外部排序和外部哈希在IO行为上非常相似:
都需要4n次IO进行输入和输出。
IO包含相同数量的随机IO和顺序IO,只是在不同阶段。
读取B块,排序,生成运行。
重复上述过程,生成多条运行。
合并运行,顺序写入最终输出。
读取输入,分区,并写出多个分区。
读取每一分区,建立哈希表,顺序写出结果。
将所有分区结果合并输出。
外部排序和外部哈希在IO模式上表现为对称关系,可以认为是一对“对偶”算法。这有利于理解和转换两种算法。
后续会讨论如何利用多台计算机来解决大数据问题。
使用第三个哈希函数HN对数据进行网络分区,将数据按机器划分。
每台机器上执行相同的外部哈希算法:分区、聚集。
第一个阶段所有机器同时扫描输入,第二阶段所有机器同时输出。
I/O成本不变,但通过N台机器并发执行,能够提升N倍速度。
三个机器代表网络,之间通过高速网络连接。
磁盘读取数据送往内存,内存再根据HN值发送到指定机器。
每台机器独立执行标准外部哈希算法。
简单加入HN函数,利用网络并发执行算法,实现外部哈希的并行化。
将数据随机洗牌到各个机器,让每台机器独立进行排序,无需跨机器协调。
按键值范围将数据划分到各个机器:低值到机器1,中值到机器2,高值到机器3等。
每台机器接收B块数据,进行本地排序生成运行。
数据在各机器上按范围顺序存储。
如何保证各机器工作量均匀,避免数据倾斜。
需要快速获取键值分布,智能设定分区点,让各区数据量相近。
扫描输入,根据范围发送数据到指定机器。
每台机器执行标准排序算法,产生局部运行。
各机器运行合并,完成排序任务。
通过范围分区和本地排序,实现并行排序的思路。
内存需求和I/O成本相同,具有对称性。
数据分布更均衡,不容易产生倾斜。
第二阶段所需内存仅与不同值成比例增长,与记录数量无关。
如果需要有序输出,只能使用排序。
处理重复值更简单,不需去重。
需要有序结果使用排序。
重复值多使用排序。
不同值少使用哈希,内存开销小。
数据分布难掌握使用哈希分布更均匀。
总体来说,两者在不同场景下优势不同,需根据实际问题选择使用。
排序是采用合并的方式,对应于分治的逆过程。哈希则是典型的分治思想。
哈希和排序算法中都存在数据流概念,涉及到分区与聚合两个阶段。
如果只是需要把相同值分组,可以使用哈希。
如需要排序结果,则只能选择排序算法。
双缓冲可以隐藏I/O延迟,提升CPU利用率。
分治/合并阶段适合采用此技术优化。
忽略主观看法,重点概括算法思想、流程和选择标准。
总的来说,掌握了这两类算法的理论模型和实现思路,能够在实际问题中选择更优解。
SQL查询优化器使用关系代数搭建逻辑查询计划,然后转换为物理计划。每个关系操作符对应一个迭代器实现。
关系代数表达式可以看作数据流图,边表示处理流向,顶点是操作符。底层是表扫描,顶点是操作符。
初始化(init)、获取下个元组(next)、关闭(close)。init设置流连接,next返回单个元组,close关闭迭代器。
选择操作是流式(On-The-Fly)操作符:
init调用子迭代器init设置连接。
next循环子迭代器next并过滤,直到符合条件或结束。
close仅调用子迭代器close。
它只是过滤通过子迭代器返回的元组,本身状态简单。
初始化(init)会传入关系名,打开对应关系的文件指针。设置初始页面和槽位。
getNext()每次返回一个元组,同时将当前页面和槽位指针往后移,实现流式扫描。
关闭(close)会释放文件资源。
初始化(init)会递归调用子迭代器初始化,将子迭代器产出的元组缓冲到内存,进行首次排序写到磁盘运行文件。
getNext()实现外部合并排序算法。每次比对各个运行文件的当前最小元组,返回并指针后移。直到迭代完所有运行文件。
关闭(close)会释放运行文件资源,并递归关闭子迭代器。
排序迭代器需要消费完整个输入,是阻塞式操作符。复杂逻辑实现多轮排序。
初始化会递归调用子迭代器的初始化函数,设置当前分组为null。
getNext()会从子迭代器不断获取元组,聚合相同分组的值,最后输出聚合结果。
关闭会递归关闭子迭代器。
常见聚合函数如计数、求和、平均值、最小值等,都需要维护不同的状态来计算结果。
如计数的状态是当前计数,求和是累加和,平均值需要记录计数和总和等。
分组迭代器一次只保留一个元组在内存中,通过不断合并来实现增量聚合计算。
| R | 表示关系R记录总数,等于P_R乘以[]R |
后续内容将参考关系规模,分析迭代算法性能
这样设置的代价模型能够为后续分析迭代算法性能提供静态输入,有利于对比算法优劣。
算法是:对R表的每条记录,对S表的每条记录进行匹配。
成本为:扫描R一次 + 每条R记录扫描S全部记录。
可以改变连接顺序,影响成本。
算法是:对R表每页,对S表每页,实现内页连接。
成本为:扫描R一次 + R页数×S页数。较简单嵌套循环大幅降低。
也叫块连接。
algorithms是:对R表分块B-2页,对S表每页,在内存中实现连接。
成本为:扫描R一次 + R块数×S页数。与页结构化连接比,通过优化内存访问效率再次降低成本。
连接算法通过身利用内存,可以大幅优化IO次数,提高性能。块连接应该成为默认的嵌套循环连接实现方案。
如果S表上有Join列的索引:
算法是:对每条R记录,使用索引在S表查找匹配记录。
成本包含:
扫描R表
每条R记录,检索索引找到匹配S记录的成本
根据索引类型收集S记录的成本
非聚集索引:每匹配S记录独立IO
聚集索引:同一R值匹配S记录可能在同一块,只需要一块IO
给定关系规模和B+树高度,分别计算非聚集和聚集索引的成本。
聚集索引成本较低,因为可以充分利用顺序IO优化。
但实际匹配记录数有影响,需要综合考虑多个影响因素评估算法成本。
对参与连接的表R和S按Join键进行排序
扫描已排序的R和S表,匹配记录进行连接
使用标记记忆S表当前位置,配合R表新记录重新定位S表位置
匹配成功输出结果,继续匹配下一个记录对
到达文件尾结束迭代
使用迭代器方式实现
临时存储R、S迭代器和标记变量
匹配成功输出,移动S迭代器指针
不匹配时使用标记重置S迭代器位置
逐步输出所有匹配结果对
仅适用于等值连接,Join条件里存在等值约束。
输入表必须事先已经排序,否则需要额外排序开支。
需要对R表和S表进行排序,成本包含R表和S表排序成本
在内存中扫描并合并已经排序的R表和S表,匹配输出结果
如果Join键完全相同,可能退化成直积联机
一般假设Join键有区分度,避免直积情况
给定R表大小1000页,S表大小500页,假设内存容量满足两表同时排序,排序成本为:
R表排序:4 1000 = 4000
S表排序:4 500 = 2000
扫描成本:1000 + 500 = 1500
总成本:7500
将第二扫描阶段合并到第一阶段排序的最后一趟合并中,实现在排序的同时进行连接:
例子中节省4000 + 2000 = 6000,新的总成本为4500
假设R表大小可以适合内存,S表可以任意大小
将R表加载到内存哈希表中
扫描S表,对每个tuple查找R表匹配输出结果
根据Join键对R表和S表进行分区,每个分区写入磁盘
对每个分区,如果小表可以适合内存则构建内存哈希表
否则继续对该分区递归分区直至满足条件
构建内存哈希表后,扫描匹配分区的大表查找匹配结果
划分阶段:根据Join键哈希值对R表和S表进行分区
构建阶段:对每个R表分区构建内存哈希表
探测阶段:扫描对应的S表分区,在内存哈希表中查找匹配结果输出
可以递归地对不满足内存条件的分区继续分区,直到满足内存算法条件
演示过程有两阶段:分区阶段和构建探测阶段
R表用蓝色表示,S表用橘色表示,Join键用不同形状和颜色的图案表示
分区阶段:根据Join键对R表和S表进行划分,同一个Join键值被分到同一分区
构建阶段:对每个R表分区构建内存哈希表
探测阶段:扫描对应S表分区,在内存哈希表中查找匹配结果
匹配结果形成Join输出后刷新到输出缓冲区,缓冲区满后Flush到磁盘
逐个处理每个R表和S表分区,完成整个格里斯哈希连接算法
分区可能分布在不同磁盘或机器上,为并行计算提供可能
哈希函数会导致重复Join键值分布不均,引起负载不平衡问题
分区阶段:读取和写入R表和S表,开销为3(R+S)
构建探测阶段:读取R表和S表,并将匹配结果输出,开销为R+S
总开销为分区和构建探测阶段之和,即3(R+S)
构建R表的哈希表需要B-2个内存块
分区阶段将R表分成B-1个等分区,每个分区大小为R/(B-1)
每个分区需小于B-2个内存块,则R需小于B^2
朴素哈希连接扫描R表和S表各一次,开销为1/3格里斯哈希连接
格里斯哈希连接支持R表规模至B^2,动态范围更大
对小R表,朴素哈希连接效率更高;对大R表,格里斯哈希连接效率更高
杂合哈希连接尝试平滑两个算法,但调优难,实用性不高
查询优化位于数据库管理系统栈的最后一个阶段
查询优化可以自动从高级语言SQL转换为执行查询的低级程序
查询优化属于软件自动生成领域,可以从高级描述自动生成程序
查询优化通过启发式搜索在大量计划空间中选择最优计划
1979年,Patricia Selinger等人在IBM首次提出查询优化概念
查询优化首次应用于System R关系数据库系统中
System R优化器架构被广泛采用,后来出现Cascades优化器架构
Cascades与System R优化器在整体思路上类似,但有细微差别
本课程将重点介绍System R优化器原始设计
查询优化分为查询解析、查询重写和查询优化三个阶段
查询解析将SQL语句转换为抽象语法树形式的内部表示
查询重写将查询转换为标准形式,如展开视图、将子查询转换为连接查询等
查询优化将抽象语法树转换为高效执行计划
执行计划生成子组件产生各种可能计划,成本估计子组件对每个计划估算执行成本
成本基于优化器使用目录统计信息选择预计成本最低的执行计划
优化目标是找到真实执行成本最低的计划,但实际上选择预计成本最小 planar
优化包含三个部分:计划空间、成本估计和搜索策略
计划空间决定可能的执行方式和算法组合;成本估计评估每个计划成本
搜索策略高效地在大量计划中找到预计成本最小计划
商业数据库查询重写与开源数据库相比更复杂完善
选择操作满足联合等效性:将多个条件的选择等效为单个条件依次选择。选择操作满足交换等效性。
项目操作满足级联等效性:对部分字段的项目等效为对超集字段的联合项目。
排他乘积满足结合律和交换律。
内连接也满足结合律和交换律,但需要注意一些结合可能导致外连接。
使用结合律改变内连接顺序可能产生外连接结果。正确表达应该是INNER JOIN ON多个条件。
查询计划树满足不同等效性时可能产生不同物理实现方式。应选择避免外连接的计划树。
联结顺序不当可能产生笛卡尔积连接,效率较低。需要注意表之间的连接条件来排除此情况。
查询重写可采用一些启发式将查询改写为等效但更优形式
选择下推:将选择条件推迟到能计算时,范围性能。
项目下推:只保留下游所需列。降低内存占用。
避免笛卡尔积连接:用条件连接替代,但有时用小表的笛卡尔积反而更好。
条件选择交换和联合可将选择尽早评估,减小 joins 输入大小。
启发式结果一定优于原始查询,但有例外情况。应了解其局限性。
查询重写目标是找到执行成本预计最低的计划树,而非一定的最佳选择。
细致分析不同情况下启发式的好处与局限,有助于选择适当应用和理解优化限制。
物理等效是指算法实现可以互换的情况。
单表扫描可以选择堆扫描或索引扫描,如果索引匹配选择条件则优先使用索引。
等值连接可以使用嵌套循环连接、索引嵌套循环连接、排序 mergesort 连接、哈希连接。
嵌套循环连接算法有基于块的版本,相对其他嵌套循环更高效。
排序 mergesort 连接表规模相近时效果好,大小差异大时用哈希连接。
小表一方用索引时,索引嵌套循环连接效率高。
非等值连接只能用嵌套循环连接,应使用基于块的版本。
算法选择应考虑表规模、索引使用情况以及内存效率来选择最佳实现。
例子查询为查询船只ID为100,评分为5的船员信息。
表 Reserves 每行40字节,每页100行,1000页,总共10万行。
表Sailors 每行50字节,每页80行,500页,各评分等可能。
第一个查询计划为页嵌套循环Join, scanning游算选择投影,性能很差。
成本计算:读取Sailors 500页,每页读取Reserves 1000页,共500,000次IO。
这个计划没有利用选择下推,索引,等优化手法,将作为基准对比优化计划。
优化目标是找到执行成本更低但输出结果相同的等效查询计划。
例子将通过应用等效知识和启发式,找出性能更好的查询计划。
对查询提出选择下推优化,将选择条件下推到更早时机执行。
将评分大于5的选择下推到Sailors表扫描,可以过滤部分行。
扫描Sailors 500页,剩余高评分行250页。每页轮询Reserves1000页。
成本下降至500+250*1000=250,000次I/O,效率提高一半。
将boatID=100下推到Reserves也可以,但对于嵌套循环Join来说,选择过滤在I/O后执行。
所以右边选择下推对成本没有影响,仍需扫描Reserves之后过滤。成本未改变。
选择下推主要目的是在扫描阶段尽早过滤行,提高后续操作效率。但对于嵌套循环Join,右表选择下推效果有限。
更改连接顺序,Reserves在前Sailors在后。
扫描Reserves 1000行,boatID=100的行10行。每行扫描Sailors500次,共6000次I/O。
将Sailors右表选择下推,加入临时表进行嵌套循环。
扫描Reserves1000行,Sailors500行。写临时表250行。循环10次扫临时表250行,成本4050次I/O。
再次改变连接顺序,Sailors在前Reserves在后,但Reserves选择下推到临时表。
扫描Sailors500行,Reserves1000行。写临时表10行。循环500页扫临时表10行,成本4010次I/O。
改变连接顺序和使用临时表下推选择,可以有效降低查询成本。
将嵌套循环连接改为排序合并连接(Sort Merge Join)。
扫描Reserves 1000行,Sailors 500行,排序连接各自的选择输出。
排序Reserves需要2趟,Sailors需要3趟。成本为1000+500+20+3×250+260=3630次I/O。
考虑块嵌套循环连接。扫描Sailors500行,Reserves1000行,将选择写临时表10行。
每4行块Sailors轮询临时表10行。块数为250/4=63趟。成本为500+1000+10+63×10=2140次I/O。
排序合并连接和块嵌套循环连接都优于原来的页面嵌套循环连接。块嵌套循环连接效率最高。
连接算法选择对查询优化很重要。应考虑数据特点选择最佳算法。
在连接前向下推投影操作,在左右表上分别只输出s_id列。
右表选择后的数据仅有原始大小的1/100,投影后只取s_id一列,其大小仅为原始大小的1/10。
右表选择输出10行,投影后1行。左表扫描Reservers 1000行。
使用块嵌套循环连接算法。右表投影结果仅需1个内存块读取。左表扫描Sailors500行。
总成本为左表扫描1000行+右表1行+左表扫描500行=1500次I/O。
通过向下推投影压缩右表数据大小,实现高效块循环连接,走读次数最少。投影下推可以有效降低查询成本。
假设Reserves建有boat_id聚集索引,Sailors建有s_id非聚集索引,且两个索引都在内存中。
通过Reserves索引获取boat_id=100的元组,只需10次I/O。
每个Reserves元组与Sailors表进行关联,由于s_id是主键,每次只需要1次I/O。
Reserves元组数量为1000条(原始100000条的1/100)。
总I/O为获取Reserves10次+Reserves元组与Sailors关联1000次=1020次。
使用索引关联比之前任何算法的成本都低,说明利用索引有效降低了I/O成本。但前提是索引在内存中。
对于一个相对简单的查询,其实存在很多可能的查询计划。
人类不是很好地管理和评估所有查询计划细节,选择最优计划的能力很差,这是AI可以胜过人类的场景。
人工编写访问和分析策略比机器更难将所有计划均枚举考虑。
算法优化器可以通过简化假设和启发式方法,使机器更快地搜索优良计划,比全面枚举更高效。
后续将探讨如何通过优化器算法自动选择优化查询计划,而不是人工编写。这是数据库管理系统的一个重要功能。
本次课程详细介绍了不同查询计划的消耗,帮助理解优化器工作原理和选择计划的依据。
查询优化需要考虑的主要内容包括:关系操作集合、查询计划空间、成本估算、搜索算法。
关系操作集合包括物理实现,如索引扫描、排序等。
根据关系等价规则和物理等价规则定义可能的查询计划空间。
需要设计成本模型估算每个计划成本,考虑I/O成本和CPU成本。
需要统计信息估算表大小、选择率等,描述表规模提供基础。
需要搜索算法在plan空间中找到最优计划,系统R使用动态规划算法。
需要剪枝策略降低搜索复杂度,如剔除高成本子计划。
系统R优化器适用于10-15张表Join,对更大查询需要其他策略。
今天主要介绍成本估算和搜索算法实现原理。
SQL查询会被优化器拆分成多个query block(查询块),优化器一次只能处理一个block。
需要尽量把嵌套的query block展平成一个block,以进行全局优化。
非关联的嵌套块可以预处理结果,关联块需要每次处理外层块的一个tuple。
在一个block内,考虑各基表的访问方法和所有左深式查询计划。
查询计划可能具有物理属性,如输出被排序或散列形式。
索引扫描、排序等可以产生排序输出,散列联合产生散列形式输出。
合并联接需要输入被排序,嵌套循环联接保留外层关系的排序顺序。
物理属性对下游操作产生影响,影响算法选择和性能,需在优化考虑。
优化目标是找到一个查询计划,使其输出满足请求的物理属性。
系统R只考虑左深查询计划,可以限制搜索空间,包含所有流式计划。
左深树不一定就是流式计划,例如排序归并连接是阻塞操作。
态树可以并行计算子计划,但需要Materialize中间结果。
查询块划分后,每个块内考虑各基表的访问方法和所有左深join树。
充分利用等价转换规则扩大等价查询计划空间。
需要考虑物理属性如排序,利用上游已有属性避免再排序。
采用启发式优先选择和投影下推等降低搜索空间。
避免笛卡尔积以减少计划数量。
后续运算可能依赖于上游物理属性,需要保持或强制属性。
查询优化目标是找到计划成本最低,同时满足请求的物理属性。
需要对每个查询计划进行成本估计,常用I/O次数作为成本度量。
先估计每个算子的成本,然后将其相加得到总成本。
算子成本根据其输入元组的基数来定义。
需要估计算子输入和输出的基数,输出作为下游输入。
假设选择和连接谓词间 Statistical Independent。
成本估计需要元组基数、页面数等统计信息来源于数据库目录。
目录记录每个表的元组数、页面数等统计信息。
条件表达式的选择率是输出基数/输入基数。
查询最大输出是输入基数的乘积。
每个选择/连接谓词都有选择率,反映其减小输出的程度。
选择率大意味着输出元组比率大,英语含义相反需注意区分。
where子句每个条件表达式都有单独的选择率需要估计。
存储等频或等宽直方图更好地描述列值分布。
等频直方图每个bin包含相同数量值,宽度不均等。
等宽直方图每个bin宽度均等,数量不一致。
根据直方图估计选择条件选择率。
单条件选择率为满足条件bin中值数量/总值数量。
两个条件选择率乘积,假设条件独立。
多个条件求并集选择率时要减去重复满足条件的元组。
并集选择率=各条件选择率之和-重复部分选择率。
在bin内假设值分布均匀来估计边界值情况。
直方图提供了各值范围选择率,提高了选择估算精度。
两个表R和S的连接条件P的选择率为SP。
R连接S等同于R表上P条件的选择。
连接选择率SP乘以R表和S表的笛卡尔积行数即为输出行数。
R连接带Q条件的S等同于R表上P条件选择,S表上Q条件选择的交集。
可将P和Q条件合并,连接选择率为SP×SQ。
假设P和Q条件独立,连接选择率计算则 captured 此假设。
对列不等值连接,假设直方图bin内值匀称分布。
对某值V,实例化连接概率等于Rbin和Sbin中V数量之积。
逐值求和概率,但效率低下,需考虑bin边界来迭代计算。
需要计算基本条件和逻辑表达式的选择率。
对只知道列最小值、最大值、唯一值数量和行数的表,假设值匀称分布。
对知道直方图的表,在直方图bin内假设值匀称分布。
假设条件之间独立, logical AND 选择率为乘积,OR选择率为差集,NOT为1减原选择率。
连接视为特殊选择,连接条件选择率乘以表大小即为输出行数。
逻辑表达式中, OR应减去重合部分来避免重复计数。
成本估算需要计算所有条件的选择率,并在连接时考虑表的笛卡格积大小的影响。
搜索左深查询计划时,通过动态规划算法枚举所有可能计划。
根据贝尔曼最优子结构原理,宽松计划成分可以复用已经计算过的最优子计划成分。
动态规划表的键为从子句中的表集合,值为每个表集合对应的最优访问计划及其成本。
考虑物理属性可能破坏最优子结构,扩展动态规划表使键包含排序属性。
只保存将来可能使用的有趣排序,如排序列进行连接、Group By或Order By操作。
递归构建高度为i+1的最优计划,结合高度为i的子计划与单表访问计划。
避免无条件笛卡儿积连接,只在where条件完全满足或连接条件成立时生成连接。
动态规划缩小了搜索空间但问题规模仍与表数呈指数增长,实际上限在15表。
使用三张表 sailors、reserves 和 boats 作为示例,演示动态规划搜索查询计划的过程。
根据表中索引结构,确定各张表的最佳单表访问计划:sailors 和 reserves 为全表扫描,boats 为颜色索引查找。
构建动态规划表,记录单表计划和考虑物理排序属性的两表计划。
第二轮动态规划连接两个表生成三表左深计划,记录到动态规划表。
第三轮动态规划使用两表计划作为外连接,生成全表左深计划。
计算结果排序代价,选择全表计划成本最小计划。如果有适当索引排序,可能省去结果排序。
最终获得该查询的最优访问计划,考虑到不同表的索引结构及可能的排序属性利用。
学习查询优化知识可以帮助开发数据库系统中查询优化器模块。
可以通过设计表结构和建立索引来影响查询优化器选择查询计划,避开优化器执行不佳的情况。
了解优化器搜索和成本计算机制,可以引导它选择更优计划,规避弱点。
智能设计表结构和索引可以避免优化器选择差计划,给导致高开销。
查询优化器使用提示可以影响其选择计划,不同系统提供不同级别的提示功能。
熟悉优化知识能解决因优化器选择差计划引起的查询性能问题,有助于高效使用关系数据库。
通过条件过滤、添加索引等方式改写查询语句,也可以引导优化器选择更佳计划。
并行查询的早期研究起源于提高磁盘I/O带宽,1980年代开始利用多机并行提高查询性能。
并行度直接影响查询的吞吐量。抽取数据分区并行和流水线操作并行是两个主要方式提高并行度。
并行度规模与速度成正比称为速度提升,数据与并行规模一致吞吐率不变称为可扩展性。
关系数据库具有自然的分区能力和流水线作业,并行化后不影响应用,满足逻辑数据独立原则。
数据库内置的求解分治算法易于分区任务,单表操作天然具有流水线特性,有助实现并行。
实现并行主要包括数据分区并行和pipeline流水线操作并行,亦可结合使用,提供更高并行度。
并行查询旨在通过增加I/O带宽缩短总体执行时间,实现快速地处理大量数据。
1980年代,自动并行化常规C程序和变体C语言尝试实现软件并行化,但多数失败。
专门为并行查询数据库设计的硬件,如Teradata,采用了共用基础设施实现软硬件协同良好,形成成功范例。
关系数据库天然支持数据独立性,独立于硬件结构,应用层无需改变。同时分治算法适用于多机集群。
关系数据库首先实现了磁盘与多节点之间的分治并行,为大数据科学家日后在大规模集群上重新学习和借鉴经验奠定基础。
大多大数据系统从未了解并行数据库之前的经验教训,重复探索已有解决方案。
Teradata等公司采用关系模型和标准硬件,在软硬件一体化下实现可靠的并行查询,奠定了企业数据库市场。
并行计算系统主要有三种硬件架构:共享内存、共享磁盘、共享无存储网络连接。
早期研究项目探索不同架构,如Berkeley Express、Wisconsin Gamma、Colorado Volcano等,多为共享无存储结构。
产业代表TeraData和Tandem采用共享无存储结构,影响深远。TeraData至今仍在,Tandem后被HP收购。
云计算大致继承上述三种结构,当前各有优势,未具共识优劣。
本课重点介绍共享无存储结构,因为广泛应用与分析、搜索、大数据等,成本低运行稳定。
共享无存储架构使用标准设备,对软件开发有利,易控制和学习原理,也是主流云服务模型。
本课将基于共享无存储结构介绍并行查询技术细节。
查询并行有两种:互查询并行和内查询并行。
互查询并行指多个SQL查询在不同处理器上同时执行,即不同查询间并行。主要管理并行任务调度。
内查询并行分为:
运算符间并行,如管道并行、树形并行。
运算符内并行,单个运算符如联接通过分区在多个节点上执行。
管道并行即查询计划多个操作依次处理不同记录。
树形并行指查询计划左右子树独立运算,中间加入materialization后再连接。
内查询并行指单个查询内不同级别获得并行,互查询指跨查询获得并行。
Latin词缀Inter和Inter的含义也给出。
并行访问数据前需要讨论如何 across 多个磁盘进行数据分区。常见方式有范围分区与哈希分区。
范围分区按键值范围将数据分散到不同节点,哈希分区通过哈希函数分散。这两种方式均能优化等值连接和范围查询。
每个节点上也可以建立本地B+树索引加快访问。
表扫描可以并行在多个磁盘上同时进行,相当于平行读多个块。
如果过滤条件涉及分区键,可能跳过整个无匹配数据的节点。
按键查找如果按键范围或哈希分区,可以直接路由到节点;否则需要广播搜索所有节点。
插入如果按键分区,也可以直接路由到节点;否则可以分散插入到任意节点。但如果有唯一键,需要检查是否重复。
并行哈希算法的三个阶段:首先用哈希函数Hn将数据分区到不同节点;然后在每个节点用局部哈希函数Hp将数据划分分区;最后在每个分区建立哈希表,用局部哈希函数Hr完成匹配。
并行哈希联接分为两种方式:朴素哈希联接和 Grace 哈希联接。
朴素哈希联接将两表分区后,分别建立哈希表和进行探查,所有节点并行执行。
Grace 哈希联接也是先将两表分区,但每个节点仅执行Grace哈希联接算法。第一阶段为并行流式处理,第二阶段每个节点独立执行。
两种算法第一阶段都利用并行流式处理充分利用各节点硬件资源,实现接近理想的线性加速。第二阶段节点独立工作避免等待。
可能存在某些节点处理数据速度慢的“倒榜兵”情况,需要等待它才能进入第二阶段,影响扩展性。
并行排序通过取样获得值分布情况,划分数据范围分区。每个节点本地快速排序生成大小为B的运行。
对两个表R和S分别进行并行排序,分别在每个节点上生成排序运行。
之后每个节点本地完成排序合并联接三步:先 Merger R表,再和S表进行排序合并联接。
取样和范围分区阶段利用网络并行传输数据,充分利用各节点计算和IO资源,实现近乎理想的扩展性。
本地排序和联接阶段节点间独立工作,无通信开销,也充分利用各节点资源。
整个算法分布式实现了排序和排序合并联接,并行度高,扩展性强。采样选择优化的范围分区规避数据倾斜,每个节点负载均衡。
并行聚合采用分层聚合方法,每个节点独立完成局部聚合,最后进行全局聚合得到最终结果。
局部聚合函数包括求和、计数等,全局聚合函数包括求和。
并行分组采用哈希或排序两种方法。并行排序实现分组的方法与之前类似。
并行哈希分组的确切实现细节:每个节点根据分组键建立哈希表保存局部聚合值。
全局聚合阶段,将局部聚合值根据分组键再次哈希,相同分组的值传送到同一接收节点进行全局聚合。
也可以采用两 pass 的优化哈希算法(Grace 哈希),在数据集过大时避免在单节点内存内完成。
排序法实现原理为:并行排序后按键值范围分组,每个组内完成聚合即可。
管道分区需要每个操作完成后输出,而排序和哈希表构建会打断管道。
对称哈希连接是完全流式的算法,支持管道分区。
每个节点分别为左表和右表构建哈希表。当元组到达时,根据连接键在对方表查找匹配,输出结果。
无论左表还是右表先到,匹配项都可以在对方表找到,并且每个结果只输出一次。保证正确性。
它是并行流处理的数据模型,支持源无限流进入。也可以加快查询长运行查询的数据输出。
并行版本通过上游流式分区阶段,再在每个节点运行对称哈希连接,实现分布式执行。
若数据不能全部放入内存,可以使用外存优化算法如XJoin处理大数据集连接问题。也有其他变种算法如流式合并连接避免排序造成块塞。
查询处理中,管道分区和数据分区都很自然。数据分区是最大的优化点,随数据规模扩大;管道分区随查询树深度增加。
共享内存、共享磁盘和无共享三种体系结构模式及优缺点。
查询并行包括操作内、操作间及查询间并行。
数据布局影响数据访问成本。
排序、哈希和许多操作支持分区并行。管道和子树并行亦可能。
事务处理需两阶段提交协议,单点故障会导致系统停顿。
共享无需真正共享内存,通过共享磁盘方式模拟。但数据访问需处理节点间通信。
将来学习分布式死锁检测和两阶段提交等事务协议,以提升可用性和性能。
事务管理器包含锁管理器和日志恢复管理器,负责优化并发性和容错性。
数据库应用程序依赖数据库系统来管理状态和保证数据正确性、可靠性。
并发控制旨在为多用户提供快速正确的访问。日志恢复旨在容错。
允许并发可以提升吞吐量和降低延迟。
服务器利用IO和多核资源运行多个事务,实现更高效利用。
并发可以让快速事务不受慢事务影响,降低平均响应时间。
数据库系统提供隔离编程员关心并发和容错问题的环境,提升开发效率。
下一步将介绍锁机制如何保证事务一致性,以及日志如何实现数据库的容错功能。
三个更新事务同时对某表进行更新,但取决于运行顺序,计算总和的查询会获取不同结果。
用户1用两个事务操作原子性移动表中记录,用户2查询过程跨越用户1操作,产生不一致读。
用户1更新表,用户2查询后更新同一行,但用户1更新被覆盖,数据丢失。
用户1更新表并提交,用户2查询同一行后又更新提交,但用户1更新被覆盖。
用户1更新账户余额,用户2在事务未提交前查询并据之行动,若事务回滚,导致问题。
多个事务读取脏数据可能导致意外结果,如用户行为基于未提交事务状态数据。
并发控制目标是控制事务执行顺序,避免上述不一致、丢失或脏数据问题发生。
事务是解决并发问题的一种机制,它允许用户指定正确的行为,也提供实现方法来保证系统在并发和故障环境下也能达到正确行为。
事务是数据库系统的主要组成部分,对许多应用来说也是极为重要的。事务的概念比SQL更具有数据库理论贡献。
在事务模型中,事务从DBMS的视角看来就是一系列对数据库对象的读写操作序列。这些读写必须以原子性的方式提交或回滚。
事务管理器控制事务的执行。在大多数数据库系统中,SQL查询和其他逻辑对事务管理器都是不可见的,它只看到读写操作。
数据库在事务之间只保存最终一致状态,不知晓读写之间的任何计算逻辑。这要求通过读写来保证安全性。
简单事务例子展示了从事务管理器视角看一项转账的读写操作序列,而忽略了具体的SQL和计算逻辑。
事务管理器保证事务具有四大属性:原子性(Atomicity)、一致性(Consistency)、隔离性(Isolation)、持久性(Durability),称为ACID属性。
原子性是指事务的所有操作要么全执行,要么不执行。一致性是指事务在未来状态保持一致性约束。隔离性是指并发执行的事务相互隔离,每个事务看不到其他事务的操作。持久性是指如果事务提交,其效果将一直存在。
事务结束有两种情况:提交或回滚。只有提交事务才会永久保存到数据库,回滚事务看作没有执行。日志可以实现原子性和持久性。
隔离性通过串行化效果来 Hide 并发,让每个事务独立执行而不受其他事务影响。读提交隔离级别可以实现该目的。
一致性通过事务开始和结束前后的数据库状态是否满足完整性约束来定义。一旦事务违背约束即回滚。
事务管理器通过两阶段锁机制实现并发控制,通过写日志机制实现事务恢复能力。
并发控制的目的是实现隔离性,即多个事务的执行看起来像串行执行一样。
事务调度定义为一系列事务的操作顺序。可以用表格或字符串表示。
串行调度指每笔事务从开始到结束没有其他事务插入的执行顺序。
两个调度等价 iff:1)包含相同事务 2)每个事务内操作顺序一致 3)最终数据库状态一致。
可串行性定义:如果某个调度等价于某个串行调度,则此调度称为可串行的。
示例中,尽管S3不是串行调度,但等价于S1,因此S3是可串行的。
可串行性保证了并发执行的效果等同于某个串行执行顺序,从而实现隔离性。但不需要知道实际顺序。
判断两个调度是否等价很难,需要更简洁的冲突等价性测试。
操作间冲突定义:1同不同事务2同一对象3至少一个是写。
非冲突操作顺序对最终状态无影响,可以任意交换。
两个调度称为冲突等价,如果同一事务同一操作的顺序一致,所有冲突操作顺序一致。
调度S是冲突可串行的,如果S和某个串行调度冲突等价。
例子通过交换非冲突操作,将非串行调度变换成串行调度,证明其冲突可串行。
另一个例子中存在多处冲突,无法通过交换得到串行调度,因此它不冲突可串行。
冲突可串行性比可串行性更保守,可能错过实际可串行的一些调度,但测试更简单有效。
为判断冲突可串行性,构建冲突依赖图。每个事务为一个节点。
如果操作O1在时间上早于操作O2,且O1和O2冲突,则从事务T1到T2添加有向边。
定理:一个调度是冲突可串行的当且仅当其冲突依赖图无环。
由于冲突操作无法重新排序,有环图中的操作无法形成线性顺序。
例子构建一个有两个事务T1和T2的调度,T1的操作早于T2部分操作,形成T1→T2边。
T2后操作与T1中的某操作冲突,形成T2→T1边,构成环。
由于环关系,无法将T1排前T2,无法获得串行调度,故不是冲突可串行的。
该例子通过依赖图解释了为什么此调度不冲突可串行。
视图可串行性允许更多可串行调度,但检测难度更大。
两个调度如果初始读写、相关读写和最终写操作均相同,则视图等价。
允许盲目写,即不依赖读的写,因为它们互不影响。
例子中t3的写不依赖t1、t2,使得t1、t2间的冲突可以忽略。
视图可串行性包含冲突可串行性,且误检率更低,但检测难度大。
冲突可串行性效率高,广泛应用。个别系统支持更专业案例允许更高并发性。
随着对操作含义的理解,可以允许更高并发,但也更复杂难用。
一般学习冲突可串行性的理论和实现是重要的。
两阶段锁定是实现冲突可串行性最常用的方法。
事务在读取前需要获取S锁,在写入前需要获取X锁。
S锁和X锁之间存在兼容性关系:S锁能共存,但X锁只允许一个持有。
事务获取锁的阶段称为获取阶段,释放锁的阶段称为释放阶段。
事务在获取阶段时间点接触到的所有对象都已锁定,称为锁定点。
任何在锁定点之后冲突的事务,要么已释放锁,要么正等待获取锁。
锁定点的顺序给出了一个等价的串行化调度。
两阶段锁定不防止级联失效问题。
级联回滚是指一个事务回滚需要引起其他事务也回滚的情况。
例如事务T1读写数据A,然后回滚,但T2已经读取了T1写入的值,那么T2也需要回滚。
两阶段锁定无法防止级联回滚问题。
严格两阶段锁定是将所有锁在事务完成时同时释放。
事务完成时会统一写入提交记录或回滚所有效果,使结果在事务结束时原子可见。
这样可以防止事务回滚导致其他事务也需回滚的级联回滚问题。
事务结束时系统会选择性地提交或回滚事务,并同时释放事务持有的所有锁。
并发计划1不是两阶段锁定计划,T2在T1之前获取锁B,违反原子性。
并发计划2是两阶段锁定计划,T1和T2操作顺序相同,保证了串行化等价。
严格两阶段锁定计划中,T1和T2一次性释放所有的锁,防止级联回滚。
所有可能的计划集合中,可串行化计划是其子集。冲突可串行计划要求读写隔离。
允许盲写的可视化串行计划更宽松,但可能导致不一致。
防止级联回滚计划与冲突可串行计划有交集部分,这就是严格两阶段锁定可实现的计划集合。
串行计划同时满足可串行和防止级联回滚。Venn图显示了不同方法的关系与包含关系。
锁管理器实际上是一个简单的协议,数据库系统内部的事务根据此协议进行操作。
锁管理器使用哈希表记录各锁对象,每个对象包含已获得集、锁模式和等待队列。
已获得集记录已获得锁的事务,锁模式为共享锁或排他锁。等待队列记录等待该锁的事务。
当事务申请锁时,锁管理器首先检查是否有冲突。如果无冲突直接添加到已获得集,否则加入等待队列。
已获得锁的事务也可以请求升级锁模式,如从共享锁升级为排他锁。
如果两个事务互相持有对方需要的锁对象,即二者都在对方的等待队列中,就形成了死锁。
死锁情况下,任一事务都无法继续执行,系统需要采取措施解决死锁,如选择补偿终止其中一个事务。
死锁是事务等待对方释放锁的循环关系。
处理死锁的方法为:预防、避免和检测及解决。
预防方式不适用于数据库,因为无法强制顺序访问表中的记录。
死锁可能场景一:事务顺序查询不同表导致。
死锁可能场景二:锁升级实现不当,如将升级放在等待队列尾部。
避免死锁的方法是:锁升级放在等待队列头部。
死锁也可能发生在多个事务同时申请锁升级。
系统可以设置超时中止似死锁事务,但效率不高,可能误中止。
最可靠方式是检测死锁,如图算法检查是否存在锁环,然后补偿中止一个事务。
避免死锁通过事务优先级来实现。优先级可以根据事务启动时间计算出来。
等待-死亡(wait-die)协议:高优先级事务等待,低优先级事务中止。
伤害-等待(wound-wait)协议:高优先级事务继续,低优先级事务中止。
两种协议能保证无死锁是因为事务之间按优先级顺序依次等待,不存在闭环关系。
事务重启后还是使用原始优先级,而不是重启时间,保证事务能最终获高优先级。
优先级也可以根据事务执行过程中获得的资源量来决定,如持有锁数量等。
目标是让执行工作多的事务最终能完成,而不是一直中止重跑浪费资源。
事务优先级不仅可以用启动时间,其他参数如资源使用量也可以作为优先级依据。
死锁检测构建事务等待图,记录事务之间的等待关系。
定期检查等待图是否存在闭环,闭环代表死锁情况。
等待图中的边表示一个事务等待另一个事务释放锁。
检测到闭环后需要解决死锁,方法是中止闭环中的一个事务。
可以根据事务优先级或使用时间长短决定中止对象。
死锁检测需要定期构建等待图并查找闭环,对系统影响不大。
实际应用中,大多数死锁链路都很短,常见两个或三个事务组成闭环。
中止一个事务解决闭环对性能影响很小。死锁检测是数据库系统的主流处理方式。
锁的粒度划分影响并发度和开销,较细粒度可获得更高并发但开销更大。
多层粒度锁允许事务以不同粒度上锁,灵活满足不同访问需要。
可以将数据对象组织成树结构,粗粒度对象位于树顶层,细粒度对象位于树底层。
事务上锁一个对象时,也隐式上锁该对象下所有子对象。
粗粒度上锁对象少,开销小但并发低;细粒度上锁对象多,开销大但并发高。
事务可以根据访问模式选择粒度,如需要少量数据则采用细粒度,大量数据采用粗粒度。
多层粒度锁通过灵活匹配事务访问需要,实现锁粒度和并发性能之间的均衡优化。
意向锁包括IS(意向共享锁)、IX(意向独占锁)、SIU(意向共享加意向独占锁)三种。
数据对象组织成树形结构,事务从顶层开始获取意向锁,直到目标层次获取共享锁或独占锁。
获取某节点锁前需持有其父节点相应意向锁,以保证区级独占性。
意向锁的兼容性矩阵根据各层次下锁的兼容性而构建。
在页面P含有元组t1、t2的情况下,S锁与X锁在t1、t2上的兼容性就决定了IS锁与IX锁在P上的兼容性。
事务按照顶下获取、底上解锁的顺序执行分层锁协议,同时支持两阶段锁定协议和锁兼容性规则。
分层锁允许事务根据访问需求灵活选择锁粒度,相当于面向对象的隐式锁定,兼顾并发和开销。
索引采用二相锁时,根结点锁定将导致所有查询发生冲突,降低并发度。
有专门的索引锁定方法采用短时间的轻量锁(latches),包括B-链接树和BW树等。
索引上层结点仅用于路由,无需保证串行化,下层实际存储数据需要保证一致性。
幻影出现于范围查询时,未锁定新插入匹配范围的数据。
范围锁需要支持将来可能匹配范围的元组,但一般锁表只支持等值锁。
下一键锁定法锁定匹配范围后继键值,可以避免幻影问题,但实现较为复杂。
参考性内容不作为考核范围,需要自行研究以深入了解相关主题知识。
隔离级别的正确性标准为串行化,其形式定义为串行化。
实际实现采用冲突串行化,它是串行化的保守实现,检测方式更简单。
采用两阶段锁定协议,特别是严格两阶段锁定来实现冲突串行化。
锁管理器追踪锁,允许或阻止事务操作以保证串行化。
两阶段锁定可能导致死锁,通常通过检测后回滚来解决。
支持不同粒度的锁,事务可以在层次结构不同层级获取锁。
数据库并发控制是一个广泛的研究领域,仍在不断创新,具有丰富的理论和技术。
简要回顾课程介绍的主要数据库并发控制理论和技术。
数据库管理系统由多个组件构成,理解各组件之间关系对设计DBMS很重要。
使用SQL查询数据库只是一个方面,事前必须定义数据库模式和建立数据表结构。
在学术研究中容易低估数据库设计的难度,实践中必须考虑各种复杂因素。
这节课将介绍如何设计数据库模式而不是DBMS,强调数据库设计需要深思熟虑周到各个细节。
相比查询语言,数据库设计涉及更多方面知识,难度也大,需要考虑的数据完整性等问题。
目的在于澄清数据库设计与DBMS设计的区别,说明数据库设计的重要性和难点所在。
数据库设计包含需求分析、概念设计、逻辑设计、物理设计和安全设计五个阶段。
需求分析涉及用户交互,了解信息处理需求。概念设计用实体关系模型概述数据存储内容。
逻辑设计将实体关系模型转化为关系数据库模型。物理设计处理索引设计和分布式等细节问题。
安全设计负责访问控制,确定不同用户对数据的查看和操作权限。
框架如Hibernate支持对象关系映射,帮助从面向对象视角进行概念设计。
后续阶段包括校对模式一致性、范式化等问题。DBMS可以自动完成部分逻辑设计任务。
本次课主要关注概念设计阶段,使用实体关系模型对数据进行初级结构化。
数据表述需要数据模型定义概念,再通过模式描述具体数据集。
关系模型主要概念为关系(表)、行、列、模式(结构描述)。
关系模型开展三个抽象层级:外部模式(用户视图)、概念模式(物理结构)、物理模式(文件与索引)。
用户通过视图访问数据的子集或聚合,不同用户视图不同。
概念模式定义全局关系及属性的逻辑结构。
物理模式描述文件组织方式和索引结构实现逻辑模式的数据存储。
例如学生数据库,外部模式展示课程报数,策略用户无法查看具体人员; 其他模式定义不同层级的数据结构细节。
多层抽象允许隐藏实现细节,通过查询计算视图实现访问控制。
数据独立性是关系型模型原始设计目标,实现应用与数据结构分离。
逻辑数据独立性保证视图不变即使概念模式发生变化。物理数据独立性保证概念模式不变即使物理模式变化。
数据独立性适用于数据库系统,因为数据库应用和数据长期持续运行。
计算环境更快变化,但应用程序变化往往较慢。这就产生了”应用变化速度小于环境变化速度”的不等式。
面对快速变化的环境和工作负载,需要通过层次分离和独立式规范,实现不同层级之间的自由适应。
数据独立思想在数据库里发源,现在对许多计算场景也很重要,有利于应用程序的长期稳定运行。
ER模型中的实体代表对象,属性描述实体值。实体集包含具有相同属性的实体。
每个实体集都有主属性组成的主键唯一标识实体。属性也有类型需符合预设范围。
关系使用菱形表示两个或多个实体的关联。关系集包含相似关系。关系也可以有属性。
例如“员工”实体集的主键为社会安全号,“部门”实体集,属性有名称等。
“works in”关系集关联员工与部门实体,属性包含工作时间。
实体集可以参与多个关系集,甚至在同一关系集中以不同角色出现,如员工作为主管与下属两种角色。
弱实体指只能通过参考其他实体集(主实体)主键 attribute 来定义唯一性的实体集。
例如”保险赔付对像(Dependents)”是弱实体,只能通过”员工(Employees)”主实体中的社保号与之对应唯一定义。
弱实体集必须与主实体集通过一对多关系集进行关联。如Dependents通过”被保险人”关系集与Employees关联。
弱实体集与关联关系集使用粗实线边界线表示。关系集使用粗箭头线表示。
弱实体集只有一部分主键属性,需要通过相关关系集连接到主实体集主键属性,才能形成完整主键。
如Dependents集中的姓名属性不是完整主键,需要连接社保号属性才能形成完整主键定义某保险对象。
另一种ER图符号表达为Crows Foot符号,使用不同符号表达实体集、关系集的参与程度。
Crows Foot符号使用圆、竖线表示0个或更多、1个或更多、1个或0个、恰好1个等参与程度。
数学关系理论中的函数、部分函数、全函数可对应到ER图关系集的参与程度表达。
函数表示每个输入只对应唯一输出。部分函数允许部分输入没有输出。全函数每个输入都对应唯一输出。
relations可被描述为射影或单射。射影关系每个集合元素都有对应关系。单射关系每个输出只对应唯一输入。
双射关系代表每个输入都对应唯一输出,输出也同样唯一对应输入,即显示双向一一对应关系。
不同符号可互相转换,便于与不同背景人员交流。ER理论源于数学关系理论,不同表达方法更好理解关系本质。
关系不仅限于二元关系,也可以是三元关系或多元关系。
三元关系例子:保险被保险人依赖保单和员工,表示一个被保险人通过“被保险”关系依赖一个保单,保单通过“购买”关系依赖一个员工。
二元关系无法表达三元关系的完整语义,如一个保单只能被一个被保险人使用。
另例中,部门通过“合同”三元关系 SET订购供应商提供的零件数量,无法用二元关系表达。
二元关系SETS之间可能没有明确对应,如部门要零件—供应商提供零件—部门与供应商联系,但无法表达实际订购数量详情。
不同关系表达需考虑实际语义,如弱实体与拥有实体的依赖关系。关系类型与属性需精确定义语义。
关系设计决定关系集与实体集之间的参与程度与属性,关系类型影响实体间联系的表达方式。
关系集只能连接实体集,不可以直接连接其他关系集。可以使用聚合解决这个限制。
聚合使用虚线框将部分实体集和关系集合在一起,视为一个新的实体集。
例如部门承办项目和关系集可以视为一个新的实体集“项目承办”,然后关系集“管理”可以连接此集合。
三元关系集可以直接连接三个或更多实体集,而无需聚合。
在设计中需要权衡使用聚合或者三元关系来表达需求。
关系属性可能需要一并更改,应一起定义,如startdate和enddate。
例如使用两个关系集定义startdate和enddate,更改一个关系就不影响另一个。而定义在一个三元关系集中,更改一个属性需要同步其他属性。
实体和关系间不断改变也需要考虑属性定义方式,权衡使用聚合或关系集来满足需求变化。
在ER图中需判断某些事物是否为实体或属性。
这需要考虑语义含义和数据使用情况。
如果一个属性如地址可能对应多个值,则必须设计为实体。如员工有工作地址和家庭地址实体。
在关系数据模型中,属性必须是单值的。无法使用集合属性来存储多个地址值。
如果属性包含内在结构,也可以设计为实体。如地址包含城市、街道等子属性。
实体可以包含多个属性。属性定义时必须是单值的。
若要对属性值进行分解,可以定义一个新实体来对应原属性,然后定义此实体的各子属性。
所以在ER图设计中,需要根据实际语义和需求判断是将事物定义为单值属性,还是新建实体来表示其内在的结构特征。
在ER图中,工作时间关系可以定义为关系,但如果允许员工在同一部门工作多个时间段,则应将工作时间设计为实体。
如果属性可能对应多个值,则应该设计为实体。如工作关系可以对应多个时间段。
也可以考虑将一个新概念设计为实体,而不是模型为属性或关系。如负责人额外预算可以设计为一个新的实体和关系。
将新概念设计为属性,可能导致数据不一致,如负责多个部门但预算需要重复。
将新概念设计为关系,可能不恰当,如预算适用于负责人,而非工作关系。
合理设计可以增加实体和关系定义问题实体,比如增设“负责人职位”实体与相关关系定义额外预算。
在ER图设计中,需要根据语义和需求的变化合理区分实体、属性和关系,得出高内聚低耦合的结构。
ER图实体集转换为表,实体集的主键属性作为表的主键。
多对多关系集定义为一张关系表,包含参与实体集的主键作为外键,以及关系集的属性。
一对多关系集可将参与实体集主键作为主键,捕获 keypoints。
也可以合并关系集表和参与实体集表,使用实体集主键作为合并表的主键。
要表达强参与约束,可以使用非空外键和删除限制。如部门必须有负责人,使用非空SSN外键。
表达参与约束时需确保关系集为二元关系,否则需要使用检查约束。
SQL使用主键、非空外键、删除限制来表达ER图中的主键约束、参与约束等概念。
在将ER图转换为relation模式时,需要考虑主键、参与约束等语义,设计出数据完整性和一致性的结构。
弱实体集只能通过其他实体集的主键来唯一标识。
弱实体集和所有者实体集之间是一对多关系,且弱实体集对该关系有强参与约束。
将弱实体集表示为粗边,所属实体集表示为普通线条。弱实体集的部分主键表示为点线。
弱实体集的主键是其部分主键与所属实体集主键的连接。
弱实体集表格的外键包含弱实体集部分主键和所属实体集主键。
可以设置外键删除规则为级联删除,即删除所属实体对应记录时同时删除弱实体记录。
也可以设置为不允许删除,不允许删除所属实体记录如果该记录对应弱实体记录。
外键删除规则需要根据实际业务规则来设置。
概念设计跟随需求分析,产出高层次的数据描述,通常使用ER图。
ER图表达性强,符合我们思考应用程序的方式。
ER图在绘制和概念上有细微差异,需要根据实际情况选择。
ER图可以表达主键约束、参与约束等完整性约束。
但不能表达函数依赖约束,需要使用关系模型。
约束保证只能写入合法数据,防止错误。
ER设计存在主观性,同一场景下有多种模型表述,取决于对问题的理解。
要分析设计选择的优缺点,如实体 VS 属性,单纯 VS N对N关系等。
后续需要利用函数依赖与范式理论进一步优化关系模式。
数据库设计包含需求分析、概念设计、逻辑设计几个步骤。
现在处于逻辑设计阶段,需要 refine 模式来减少冗余。
冗余会增加插入、删除、更新时的异常风险。
功能依赖是完整性约束,可以识别模式中的冗余。
将单表分解成多表可以去除冗余,这叫分解。
功能依赖表示X字段决定Y字段,记为X→Y。
主键等价于全部字段的功能依赖。
首键须满足最小依赖和唯一性。
实体集的属性可以推导出其功能依赖。
功能依赖是约束,禁止违反其规则的数据库更新操作。
更新异常:如果修改一个属性的值,可能会导致其他相关属性值不一致,需要同时更新其他属性。
插入异常:如果插入一个记录但缺少属性值,则不能确定该属性的值应为何值。
删除异常:如果删除含有某属性值的所有记录,则会丢失该属性对应的标准值信息。
功能依赖R→W导致异常,因为R不是候选键,同一R值可能重复出现。
S→W不导致异常,因为S是主键,每一个S值在表中只出现一次,没有冗余。
出现异常的原因是关系模式中的冗余。
将关系分解成两个关系可以去除R→W功能依赖中的冗余,一个关系没有W,一个关系中R→W中R是候选键,实现功能依赖约束。
功能依赖可以组合成新的功能依赖规则。
书编号决定出版社和作者,可以推出它决定出版社和决定作者。
无法将一个功能依赖的左侧属性分割后,直接推断右侧属性。
阿姆斯特朗公理是推断功能依赖集闭包的规则。
自反性:如果X包含于Y,则X决定Y。
增广性:如果X决定Y,则XZ决定YZ。
传递性:如果X决定Y,Y决定Z,则X决定Z。
阿姆斯特朗公理是完备且正确的推理规则。
联合规则和分解规则是阿姆斯特朗公理的简单应用。
根据给定的功能依赖和阿姆斯特朗公理,可以推断更多功能依赖。
计算功能依赖闭包F+的复杂度是属性数量的指数级。
但检查一个功能依赖是否在F+中只需计算属性闭包。
X+是所有X决定的属性集合。
初始化X+为X,重复添加满足条件“U决定V,U在X+中”的V到X+。
检查关键属性时,如果X+包含所有属性则X是候选键。
检查候选键时,移除X中的一个属性A,如果X-A+不等于关系,则A是必要的。
例子中计算BCDE关系和功能依赖F下,BD决定E是否在F+,以及D和AD是否是候选键。
通过属性闭包,快速判断给定功能依赖在F+中的存在性和候选键。
关系模式和功能依赖关键信息及其属性闭包关系,可以解决许多DB设计问题。
正常形式帮助判断关系是否需要分解,避免冗余。
第一范式要求属性是不可分割的。
第二、三范式用处不大,理论上较弱。
波伊斯-科德范式(BCNF)提供清晰理论:关系R满足每个非平凡函数依赖(左组是一个候选键)即为BCNF。
BCNF关系中每个属性记录有用信息,不存在通过其他属性推导出来的冗余属性。
候选键约束关系无冗余,非候选键约束可能存在冗余。
通过函数依赖分析,可以判断关系是否满足BCNF,从而规范化到BCNF消除冗余。
正常形式理论指导数据库设计,帮助构建高内聚低耦合的关系模式。
拆分关系可将其分解成多个规范化关系,消除冗余。
拆分应为无损拆分,即通过自然联结可完整重建原始关系。
无损拆分的条件是:交集属性确定左表或右表。
例如以日期属性拆分订票信息,日期同时作为轨迹和飞机表主键。
但有时拆分后需跨表检查依赖,使更新成本上升。
例如表ABC以C决定B拆成AC、BC,但A决定B需join检验。
正常形态理论指导拆分,但实际操作需结合实际查询成本进行优化。
拆分后表结构需满足BCNF,且应尽量避免跨表检查依赖提高效率。
BCNF是一种规范化形式,每个字段中存储的数据不能通过函数依赖推导得到。
BCNF旨在消除关系中的冗余性,适用于大多数情况下,但有时查询性能需考虑。
如果表不能分解为BCNF关系,需选择较宽松的第三范式。
第三范式允许部分冗余,需要程序控制冗余导致的越界问题。
若无法找到保留依赖的BCNF分解,可采用第三范式,但需注意将带来的冗余。
还存在更高级别的范式,用于满足额外属性,但不在本课程范畴内。
如果对这门知识感兴趣,可以自行学习更深入的范式理论知识。
信息检索与数据库管理系统从历史上来看是两个独立的研究领域。
1959年,IBM的汉斯·列文开发了第一个信息检索系统Keyword in Context。
1960-1970年代,康奈尔大学的杰里·索尔顿研发了SMART系统,标志着信息检索领域的一个重要阶段。
随着网络时代的来临,信息检索得到快速发展,重点从收集信息变为网络信息检索。
信息检索系统采用索引和查询算法实现非结构化文本的检索,而数据库管理系统主要用于结构化数据的管理。
信息检索与数据库管理虽有不同,但在系统设计与实现手段上存在较多相同之处,如文件管理、缓冲管理等。
信息检索系统的关键组成为索引和查询排序算法。数据库管理系统重在事务处理与完整结果返回。
信息检索系统通过抓取增量更新索引,数据库管理系统使用事务机制保证一致性。
信息检索中常采用的模型是词袋模型,其中的基本概念是文档是一个包含词汇袋的对象。
词汇袋意味着文档中词汇的顺序无关紧要,但词汇出现的频率是重要的。
停用词指那些对信息检索无意义的常用词,如英语中的冠词the等,我们需要将其从词袋中过滤掉。
在SGML/HTML等编码文件中,标签代码同样也需要从词袋中去除。
词根提取,也称为还原,指根据语言规则将不同词形压缩到相同词根,如将surfing和surfed还原为相同词根surf。
词根提取应根据不同语言设定不同规则,因为不同语言中的词变化形式不同。目前为止,词根提取已经在各主流语言中得到很好解决。
信息检索软件包如NLTK自然语言处理库中通常内置了不同语言的词根提取模块。
信息检索中的基本查询是布尔文本搜索,它使用布尔表达式来查询单词的存在与否。
查询会像处理文档一样进行停用词过滤和词根提取。
文本索引既包含关系数据库的表结构,也包含物理索引文件用于快速搜索。
文档集合称为语料库(Corpus),它可以视为一个关系包含文档ID和内容。
倒排文件以词为键,值为包含该词的文档ID列表。它建立在词的倒排索引上。
倒排索引使用B树将单词映射到posting lists,即包含该单词的文档ID顺序列表。
查询单个单词时,通过倒排索引定位posting lists快速获取包含该词的文档ID。
信息检索系统会将查询词与文档进行相同的处理,如stopwords过滤和词根提取,以进行匹配。
倒排索引可以很简单地支持布尔逻辑查询。
term1 或 term2 查询,通过B树分别查找term1和term2,合并其posting lists。
term1 和 term2 查询,通过排序合并term1和term2的posting lists来找出其交集。
term1 且不包含 term2 查询,通过排序合并term1和term2的posting lists,保留term1中不包含在term2中的记录。
不被允许的查询包括term1 或 不包含 term2,因为不包含term2对应的posting lists数据量太大,无法直接从索引中获取。
可以将布尔查询用SQL表达出来,通过多次索引扫描和帖子列表的排序合并来实现。但这不是高效方式。
更复杂的布尔逻辑也可以通过设置更复杂的SQL来表达,它们的查询计划依然是多次索引扫描后排序合并得到结果。
文本检索的关键是通过各种统计、语言和图算法来对查询结果进行“魔法排序”,使最相关的文档排在前面。
为支持短语查询,倒排索引表增加一个「位置」字段,记录每个词在文档中的位置偏移。
短语如「happy days」,分别查询单词happy和days,并验证days位于happy之后1个位置即可认为匹配。
也可以用「附近」概念,比如位置差在K个范围内认为匹配。
查询结果不再只返回文档ID,需要返回内容。将文档ID改为整数编码,用文件表记录文件名等路径信息。
文件表用整数ID对应索引项,查询结果 JOIN 文件表,按需逐步获取各页内容。
整数ID能有效压缩,文件表JOIN会依次lazy loading获取内容,实现分页输出文档内容。
这樣改进后可以支持更丰富的查询需求,如短语、位置等匹配,同时提供内容级别的检索结果。
文本搜索的重点是查询,更新相对较少。通常以批处理方式定期整批更新索引。
可以在原索引和新文档构建的新索引之间合并,构建融合更新后的总索引。
LSM树能很好支持这类增量式更新需求。也可以通过交替索引实现不下线更新。
使用两个索引,一个作为查询用,一个作为后台建立;切换时删除旧索引,实现实时查询。
为支持查询,索引可以优化为插入低效但查询高效;通过整批更新来替换索引实现。
分布式扩展时,可以将索引片段分布到各节点,每个节点负责小部分,更新时较低影响。
Workload视角,文本搜索专注单查询,关系数据库一般 workload;不同数据库针对不同工作负载优化。
文本搜索对 posting 列表交集运算实现比简单连接更快,使用类似内存多重连接的算法。
重要的是对结果进行排名,这对构建好的搜索引擎至关重要。
文档聚类可以使结果更多样化,如一个关键词对应不同主题文档时。
压缩可以提高 I/O 性能,如压缩 posting 列表使其更小。
需要处理同义词、误拼写、缩写等语言问题。
如果构建网络搜索引擎,需要实现爬虫与索引加载器。
需要应对搜索引擎优化(SEO)即网络广告问题。
可以根据用户地域或历史查询个性化结果。
常用术语:文本库(corpus)、词条(term)、索引、反向文件(inverted file)、posting 列表。
内部使用关系表模型与 B+ 树,通过并集、交集运算实现查询。
评估 primera 页结果质量,而非完整输出,是性能目标。
文档可以用向量空间模型表示,每个文档是一个包含词频计数的高维向量。
查询也可以表示为向量。找出与查询向量距离最近的文档,即最相关文档。
长文档向量长度大,短文档向量长度小,直观距离长文档相似度高。
采用余弦相似度解决这个问题。每个向量坐标点除以向量长度后再计算内积。
归一化后,每个向量到原点的距离为1,仅与其向量方向相关。相似文档向量方向相近。
计算两个向量的内积可表示其角度余弦值,即余弦相似度。它顺序等价于Euclidean距离。
余弦相似度使长短文档在同一空间下可比较,实现更好的排序和检索效果。
TF-IDF是选取词频和逆文档频率作为词权重的评分模式。
词频(TF)表示词在文档中出现的频率。逆文档频率(IDF)表示词在全部文档中的稀有程度。
IDF的计算方法是对数形式的全部文档数除以包含该词的文档数量。可以将常出现的停用词 IDF设为0。
在向量空间模型中,每个文档向量中的每个元素都替换为该词的TF-IDF权重。
计算查询向量的TF-IDF与匹配文档向量的内积,即为相关度评分。这是信息检索的标准模型。
索引中需要增加包含每个词及其对应文档数量的词信息表,以计算IDF。同时增加每个词文档对的TF-IDF值。
对查询也进行同样的TF-IDF计算,与文档向量相匹配获取文档列表。为提升效率,只考虑词集交集不为空的文档。
输出排序需要针对所有记录进行,会造成延时。一般会对候选集进行筛选,只对筛选出的记录排序,快速返回前几页结果。
信息检索系统为每个查询返回top K个结果。我们需要衡量结果优劣。
结果可以分为四类:真正例(返回结果与查询相关)、假正例(返回但不相关)、真负例(没有返回也应该没有返回)、假负例(没有返回但应该返回)。
准确率表示在所有返回结果中,真正例的比例。它反映系统返回有用信息的能力。
召回率表示在所有应该返回的结果中,真正例的比例。它反映系统找到所有相关信息的能力。
precision=真正例/(真正例+假正例)
recall= 真正例/(真正例+假负例)
我们希望同时得到高准确率和高召回率,但两者难兼得。需要权衡二者。
准确率和召回率是评估信息检索系统质量的重要指标。它们考察了系统是否正确识别和返回了所有相关结果。
信息检索领域有几本很好的教科书,比如《信息检索:理论与实践》、《现代信息检索》、《管理吉字节》。
《信息检索:理论与实践》是该领域最新的教科书,其讲义在线公开。《现代信息检索》和《管理吉字节》也是经典教材。
此视频讲义内容部分参考了《信息检索:理论与实践》课程讲义。课程授课多次,资料丰富。
如果要深入学习信息检索知识,可以查阅这些教科书,或者查询《信息检索:理论与实践》完整在线讲义。这有助于进一步研究信息检索和网页搜索技术。
大规模数据集需要在多台计算节点上并行处理查询。
可将倒排索引按文档ID或词条分区到各节点。
按文档ID分区时,每个节点运行独立的子搜索引擎。
按词条分区时需要计算分布式连接,融合各节点词条对应的文档ID列表。
齐普夫定律指出,少量词条的频率很高,大多数词条频率较低。
按词条分区,热词对应的节点负载很重,效率低下。难保证节点负载平衡。
按文档ID分区,每个查询广播到所有节点,但不匹配节点工作轻。整体负载更均衡稳定。
考虑到齐普夫定律影响,按文档ID分区倒排索引是较好的分布式并行查询处理方案。
n-grams指提取文本中的n个连续词组,如词对或三词组,将其作为搜索索引内容。
q-grams指以字母三元组或更大的配对作为搜索索引的内容。
对查询”The Who”使用n-grams可以识别这组词的高度,并给予更高排名。
使用q-grams可以识别拼写错误,将错误词转化为正确词,提高搜索质量。
查询扩展技术可以自动或人工添加与查询相关的词,扩大检索范围。
文档扩展可以使用链路文本或分类标签来添加文档没有的词,提升匹配程度。
可以根据词出现位置(标题、字体等)来提升其tf-idf权重,影响排名。
这些技术都可以帮助更好捕捉用户意图,提高检索效果和用户体验。
微软和Google在20世纪90年代后期提出,网页链接可以用于搜索排序。
重要网页链接到其他网页,那么被链接网页也很重要。这个递归定义需要迭代计算。
PageRank算法将每个网页初始化权重为1,然后反复传播和分配权重。
权重传播计算图中节点的第一个特征向量,直到收敛。重要节点和相关节点会累计更高权重。
早期Google搜索仅使用PageRank已经能很好排序结果。
PageRank提出Google搜索但并不是优质排序唯一因素。标题、正文、锚文本利用也很重要。
搜索引擎需要综合利用许多因素如PageRank、位置特征等,通过不断优化获得最佳效果。
网页词汇表比英语词典更大,包含所有数字、代码、程序名等。
错别字也需要被索引,因为用户可能搜索错别字。
网页包含多种语言。
用户可能利用关键词重复生成网页来刷评分。
用户也可能利用链链接创建投机页面升高PageRank。
词频obi分布意味着常用词查询和缓存很有效。
用户搜索词短小,帮助提升效率和召回率精度。
用户对搜索结果不一致不太敏感,利于系统维护。
少量信息丢失用户可能重新搜索。
搜索引擎实现大规模服务的关键在于弹性和用户体验。
网页爬虫用于构建网页索引,需要递归遍历网页链接结构。
产生多个并发的URL请求,避免等待阻塞。
使用多台机器并行爬取,规模化爬取全网。
不应对同一主机连续请求,需要间歇请求其他主机。
网页内容变化快,需要设计重新访问策略。
需要处理动态HTML、镜像站点等特殊URL。
使用事件驱动实现单线程模型,管理进度边界集合。
不能简单广度优先遍历,需要智能选择下一个URL。
网页爬虫的目标是尽快获取重要页面,同时保持网络友好性。
根据页面PR值优先级别页面,前期Breadth-first和随机访问策略都能快速得到高PR页面。
行业标准实现需要充分理解用户查询行为特征与页面重要度计算方法。
分布式实现需要对边界url集进行分区,考虑DNS缓存以均衡负载。
可参考学术文献和Wiki补充知识,关键技术源于学术研究后经过企业优化。
索引构建需要对抓取文集进行平行排序与分类,MapReduce源于Google在此场景中的优化经验。
事务的ACID属性中,恢复管理器主要负责原子性和耐久性,还可以回滚违反一致性的事务。
事务可能由于用户明确中止、一致性检查失败、死锁或系统故障导致回滚。
恢复的目标是使已提交事务永久化,未提交事务视为未运行。
系统崩溃前若有事务已提交(如t1、t3),恢复后它们应视为永久;未提交事务(如t4、t5)应回滚。
应用程序应在异常时回滚事务,避免数据库处于不可理解状态;一致性检查失败也将回滚事务。
死锁检测通过回滚一个事务来解决循环依赖。
SQL语言支持事务操作,包括begin开启事务、commit提交、rollback回滚或者abort撤销事务。
SQL还支持保存点save point,可以部分回滚事务操作,如回滚到指定保存点将撤销该点之后的操作。
一致性约束违反如删除外键引用的数据将导致事务回滚。
数据库系统最常见的故障原因是人为操作错误,如关断错误设备、输入错误命令等。
其次是软件和系统配置错误,如资源耗尽或文件权限不足。软件bug和安全漏洞导致的故障较少。
硬件故障如存储介质故障少见,多层冗余设计可以隐藏和容错。服务器故障也很少由于物理原因。
恢复管理主要保证事务的原子性和持久性,能通过回滚或提交来实现技术目标。
简单粗暴的恢复方案是事务期间锁定缓存页面,提交时将所有涉及页面批量写回数据库。
这种方案无法实现可扩展性,因为一个大事务可能锁定全部缓存容量,也无法高效利用替换策略。
批量写回数据库 disk 也无法保证原子性,数据库崩溃可能只写部分页面。
更好的方案需要考虑可扩展性,允许页面替换,并支持部分恢复能力。同时,应记录操作日志保证原子性和一致性。
简单方案多少暴露出恢复需要考虑的主要问题: scalability、concurrency control、crash recovery等环节。后续需要更深入解决这些问题。
缓冲管理与恢复策略相关。NO STEAL策略可以简化逻辑但性能较低,限制替换策略。
FORCE策略能提供持久性但IO负荷大,写回每个页面都需要随机IO。
优选策略是STEAL和NO FORCE。页面可以在未提交时被替换,但必须记录足够日志支持回滚或重做。
NO FORCE策略难保证持久性。需要在便利位置记录日志,以支持事务失败后重做动作。
STEAL策略下,未刷新页面可能被替换。需要记录旧页内容支持回滚未提交更新。
不同策略对应不同日志需求。STEAL NO FORCE同时需要UNDO和REDO日志,性能最高但复杂度也最大。
日志将是恢复的基础,它记录了事务过程,使得系统崩溃后能重新执行或回滚事务操作。
日志记录每个事务更新,支持回滚和重做。日志顺序写入专用日志设备,提升效率。
日志记录包含事务ID、页面ID、旧值、新值等信息。
日志是有序的日志记录列表。每个记录有单调增长的LSN编号。
长期日志在内存中写为尾部日志缓冲,定期写入日志设备。
每个页面记录最新LSN号。LSN用于追踪页面最近的更新日志。
写前日志协议包含两个部分:1日志记录必须写入日志设备前更新页面;2事务日志记录必须写入日志设备前返回提交。
这保证了原子性和持久性。页面只能在其LSN号小于或等于刷新LSN后写入 You are sending and receiving too many words in a short period of time.
事务处理会产生读写操作,生成相应的日志记录。
日志记录写入内存日志队列,同时维护事务表和脏页表。
更新页时同步设置页LSN指针和脏页表REC_LSN。
后台定期将日志队列刷新到磁盘,更新刷新LSN指针。
页面回收依照日志规则:页LSN≤刷新LSN。
提交事务时,写入提交日志记录,所有日志记录随后同步刷新到磁盘。
刷新完成后返回提交,并写入结束日志记录。
保证事务只有在所有日志记录刷新完毕才返回提交。 You are sending and receiving too many words in a short period of time.
在数据库崩溃后,Aries协议进行恢复有三个阶段:
分析阶段:从上次检查点记录向前扫描日志,重新构建检查点时的事务表和脏页表,并识别检查点后提交和未提交的事务。
重做阶段:从脏页表中LSN最小的页面开始,按LSN顺序重放日志以还原数据库。包括重做未提交事务和终止的事务。
撤销阶段:从日志尾向前,撤销崩溃时尚未完成的事务对数据库的修改。
分析阶段具体包括:
从检查点记录中恢复事务表和脏页表
从开始检查点记录向后扫描日志
遇到结束记录删除事务,见更新记录但页面未在脏页表中添加到脏页表
其他记录添加事务到事务表并记录LSN
遇到提交记录更新事务状态
扫描结束,撰写未完成事务的结束日志记录
留在事务表中的是崩溃时活动中的事务
分析结束可以识别出检查点后提交的事务,以及需要在撤销阶段撤消影响的未完成事务。
重做阶段从分析阶段脏页表中最小的req LSN日志记录开始向前扫描日志。
对每个更新日志记录或撤消日志记录,如果其页面在脏页表中:
如果页面不在脏页表中,说明已经刷写到数据库
如果页面在脏页表中,但req LSN大于当前日志记录,说明当前更新已反映在数据库
或者访问数据库页面时,页面LSN大于等于日志记录LSN,说明当前更新已反映
上述三种情况会跳过重做
否则,执行日志记录指示的更新操作:
更新页面至buffer pool
设置页面LSN为当前日志记录LSN
无需强制flush至数据库
重做的目的是完整重放历史,还原崩溃前数据库状态,包括已提交和未提交事务的所有更新操作。
通过重复性地重放日志,避免了复杂的逻辑,使得恢复机制更加通用和清晰。 You are sending and receiving too many words in a short period of time.
系统在分析阶段崩溃:
系统在重做阶段崩溃:
如何限制重做工作量:
系统在回滚阶段崩溃:
如何限制回滚工作量:
分析、重做和回滚阶段都能很好抵御崩溃,因为它们按日志顺序顺序执行操作。
恢复管理器负责确保事务的原子性、持久性和一致性。
右边记录(WAL)技术实现了日志写前策略,使buffer pool可以灵活管理,同时也保证了正确性。
日志序列号(LSN)连接了日志记录、数据库页和不同事务中的日志记录,就像是数据库时间线。
检查点记录只记录了内存数据结构Dirty页表和事务表的状态,可以限制恢复时需要扫描的日志范围。
恢复包括分析、重放和回滚三个阶段:
在回滚期间仍然会追加日志,记录补偿操作。
重放阶段会重复所有操作,包括已回滚事务,这可以简化恢复逻辑,尤其是在恢复期间崩溃的情况。
分布式数据库是一种分享无存储的并行系统,节点可能分布在不同地理位置,网络传输速度较慢。
分布式计算相比集中计算更复杂,主要特点包括:并行计算、无共享内存或磁盘、不可靠网络、时钟不同步、部分节点可能发生故障。
分布式数据库在分布式计算历史上扮演重要角色,是管理状态和事务的早期模型。
目前很多复杂的分布式系统都是数据库,包括云数据库如Google Spanner、AWS Aurora,以及NoSQL数据库如DynamoDB、Cassandra等。
该课程重点介绍分布式事务数据库的并发控制和容错机制。你已了解分布式查询处理。
劳莱斯·兰波得2013年图灵奖就是因为对分布式计算的贡献,他指出单个未知节点故障也可能导致系统瘫痪。 You are sending and receiving too many words in a short period of time.
分布式系统中本地节点各自维护自己的等待图,可能无法检测全局事务等待环。
可以定期将每个节点的等待图发送给指定的死锁探测主节点。
主节点汇集所有节点等待图的边,形成全局等待图。
如果全局等待图中存在环路,说明存在事务等待环,产生死锁。
此时主节点以典型方式中断环中的一个事务,消除死锁。
该方法可以周期性地有效检测跨节点的死锁,解决分布式系统中的死锁问题。 You are sending and receiving too many words in a short period of time.
分布式事务必须实现全局一致性提交或回滚。
两阶段提交(2PC)协议通过投票实现全局一致决定。
第一阶段,协调器向参与者发送准备消息,参与者响应是否同意提交。必须达成一致。
第二阶段,如果一致同意,协调器向参与者发送提交消息,参与者回复确认消息。
协调器接收到所有确认后,事务完成。
2PC通过大量消息传递实现全局一致决定,保证分布式事务原子性。
需要考虑消息及节点失败情况,实现日志记录以提供容错能力。 You are sending and receiving too many words in a short period of time.
协调器恢复时,如果事务记录未知,应指示作废。如果记录提交,告知参与者已完成。
参与者恢复时,无日志记录采用预设作废策略。日志有预备内容请求协调器状态。
仅有提交日志,参与者重发确认信息。有预备和提交,根据协调器回复决定。仅有作废日志不需作动作。
协调器恢复,日志有提交但无结束记录,重发提交信息给参与者,重整结束。
协调器恢复见日志作废记录,不采取任何动作,参与者也按预设作废协议执行本地回滚。
恢复过程中,协调器与参与者协作,保证事务一致性和幂等性。
二阶段提交和二阶段锁定协同工作时,需要保证节点间消息有序发送和接收。
参与者收到提交请求时,已收到该事务所有消息,可以安全地本地提交。收到作废也可以本地作废。
单节点故障会导致其他节点无法知道事务结果,使部分数据不可用。
系统通过心跳检测节点,协调器可以重启失效节点。但协调器失效时系统将处于暂停状态。
Paxos协议提供了容错的复制协调器,实现了PaxosCommit来解决协调器失效问题,使分布式事务具有高可用性。
两阶段提交的优点是简单,缺点是单点故障。后续工作解决了这一问题,但理解原理需要深入研究。 You are sending and receiving too many words in a short period of time.