哈工大数据库课件-第七讲数据库系统体系结构.ppt

教学目的 本章在一个更高的层次上认识数据库系统，首先简要介绍一下数据库的存储结构，然后从传统的集中式系统开始，依次讨论客户-服务器系统、并行数据库系统和分布式数据库系统，使学生了解如何根据不同的计算环境搭建与之相适应的数据库系统。 主要内容 数据存储，数据库系统体系结构概述，集中式数据库系统，数据库系统，并行数据库系统，分布式数据库系统 教学方法 课堂讲授为主 重点 集中式数据库系统、数据库系统、并行数据库系统、分布式数据库系统的概念及特点，分布式查询处理 难点 分布式查询处理,第七章 数据库系统体系结构,第七章 数据库系统体系结构,内容出处： 1.Abraham Silberschatz数据库系统概念第十一章1-3节，第十八章，第十九章2，7节,物理存储介质,特性 数据存取速度 每单位数据的成本 可靠性 电源故障或系统崩溃时的数据丢失 介质故障 介质分类 易失介质（volatile storage） 电源关时数据丢失 非易失介质（non-volatile storage） 电源关时数据持久保留，包括二级和三级存储,物理存储介质,高速缓冲存储器（Cache） 最快最昂贵的存储介质，一般由操作系统来管理 主存储器（Main memory） 用于存放可被处理的数据的存储介质 快速访问，但一般不能存放整个数据库 如果发生电源故障或系统崩溃，主存储器中的数据会丢失 快闪存储器（Flash memory） EEPROM：电可擦可编程只读存储器 电源故障时数据会保存 读速度：0.1s; 写速度：10s,物理存储介质,磁盘存储器（Magnetic-disk storage） 用于长期联机数据存储 一般存放整个数据库 数据必须从磁盘移入主存才能访问 直接存取（direct-access） 按任意顺序存取数据 如果发生电源故障或系统崩溃，数据不会丢失 光盘存储（Optical storage） CD-ROM：只读，提供预先记录的数据 WORM：一次写，多次读，用于数据归档,物理存储介质,磁带存储（Tape storage） 用于数据的备份和归档 顺序访问（sequential-access） 速度慢 容量大 价格低,存储层次,基本存储,辅助存储,三级存储,易失性存储,非易失 性存储,存储层次,基本存储（primary storage） 快速但易失 cache, main memory 辅助存储（secondary storage） 非易失，相对快速 联机存储（on-line storage） flash memory, magnetic disks 三级存储（tertiary storage） 非易失，速度慢相对快速 脱机存储（off-line storage） magnetic tape, optical storage,磁盘结构,磁盘性能估计,访问时间 从发出请求到数据开始传输之间的时间 寻道时间（Seek time） 磁盘臂定位时间，即磁盘臂移动到正确的磁道所需时间 与移动距离成正比，平均寻道时间是最坏时间的1/3 旋转等待时间（Rotational latency ） 寻道结束后，等待被存取的扇区出现在读写头下面的时间 平均旋转等待时间是磁盘旋转一周时间的1/2 数据传输率 从磁盘获得数据或向磁盘存储数据的速率 平均故障时间（MTTF） 预期系统无故障连续运行的时间 是指基于全新磁盘发生故障的可能性,RAID,廉价磁盘冗余阵列（RAID） Redundant Arrays of Inexpensive Disks 是一种利用大量廉价磁盘进行磁盘组织的技术 价格上，大量廉价的磁盘比少量昂贵的大磁盘合算得多 性能上，使用大量磁盘可以提高数据的并行存取 可靠性上，冗余数据可以存放在多个磁盘上，因此一个磁盘的故障不会导致数据丢失 过去RAID是大而昂贵的磁盘的替代方法；今天，使用RAID是因为它的高可靠性和高数据传输率；因此 “I” 代表independent，而非inexpensive,RAID,通过冗余提高可靠性 N个磁盘组成的集合中某个磁盘发生故障的概率比特定的单个磁盘发生故障的概率高很多 假定单个磁盘的MTTF是100,000小时 (约为11年)，则由100个磁盘组成的阵列的MTTF是1000小时(约为41天) 冗余（Redundancy） 存储额外的信息，以便当磁盘故障时能从中重建 镜像(Mirroring or shadowing) 一个逻辑磁盘由两个物理磁盘组成，写操作在每个磁盘上执行 如果其中一个发生故障，数据可以从另一个磁盘读出 只有第一个磁盘的故障尚未恢复，第二个磁盘也发生故障，这时才会发生数据丢失 假定一个磁盘的MTTF是100,000小时，修复时间是10小时，则镜像磁盘系统的MTTF是100,0002/（2*10）=500*106小时，约为57000年,RAID,通过并行提高性能 负载平衡多个小的存取操作（即页面存取），以提高这种存取操作的吞吐量 并行执行大的存取操作，以减少大的存取操作的响应时间 通过在多个磁盘上对数据进行拆分来提高传输率 比特级拆分（Bit-level striping） 将每个字节按比特分开，存储到多个磁盘上 例如，对于一个由8个磁盘组成的阵列，将每个字节的第i个比特位写到第i个磁盘上；它的存取速度是单个磁盘的8倍 对于由4个磁盘组成的阵列，将每个字节的第i个比特位和第i+4个比特位写到第i个磁盘上 块级拆分（Block-level striping） 对于由n个磁盘构成的阵列，文件的第i块 存放在第(i mod n) + 1个磁盘上,RAID,RAID级别 镜像提供高可靠性，拆分提供高数据传输率，通过利用与奇偶校验相结合的磁盘拆分思想，可以实现以较低成本提供冗余的方案 不同的RAID级别，具有不同的代价、性能和可靠性,C,P,代表数据的第二个拷贝,表示纠错位,RAID,RAID 0 块级拆分且没有任何冗余（如镜像或奇偶校验位）的磁盘阵列 用于高性能访问并且数据丢失不十分重要的应用场合,RAID,RAID 1 带块级拆分的磁盘镜像 完全容错，成本高 一般用于类似于数据库系统中日志文件存储的应用场合,RAID,RAID 2 按比特级拆分，具有内存风格的纠错码 纠错码（ECC：Error-Correcting-Codes） 内存中每个字节都有一个奇偶校验位与之相连，它记录这个字节中为1的比特位的总数是偶数（=0）还是奇数（=1），如果字节中有一位被破坏，则字节的ECC与存储的ECC就不会相匹配；通过ECC可以检测到所有的1位错误；通过更多的附加位，当数据遭到破坏时，还可以重建数据,RAID,RAID 3 磁盘控制器能够检测一个扇区是否被正确的读出 如果一个扇区被破坏，我们先能准确地知道是哪个扇区坏了，然后对扇区的每一位，通过计算其他磁盘上对应扇区的对应位的奇偶值来推断该位是1还是0。如果其余位的奇偶值等于存储的奇偶值，则丢失的位是0，反之为1 RAID 3效果与RAID 2一样，但只有一个磁盘的额外开销 使用N道数据拆分的RAID 3对一个字节的读写散布在多个磁盘中，因此读写一个块的传输率是使用N道数据拆分的RAID 1的N倍 每个磁盘参与每个I/O请求，每秒RAID 3支持的I/O数较少,RAID,RAID 4 块级拆分，在一个独立的磁盘上为其他N个磁盘上对应的块保留一个奇偶校验块 读取一个块只访问一个磁盘 每个存取操作的传输率低，但可以并行地执行多个读操作，从而产生较高的总的I/O率 读取大量数据的操作有很高的传输率，因为所有磁盘可以并行地读,RAID,RAID 5 将数据和奇偶校验位都分布到所有的N+1个磁盘上；对每个块，一个磁盘存储奇偶校验位，其余磁盘存储数据 例如由5个磁盘组成的阵列，第n块的奇偶校验位存储在第(n mod 5)+1上，其余4个磁盘的第n块存储了对应这个块的实际数据 奇偶校验块不能和这个块对应的数据存储在同一个磁盘上 所有磁盘都参与对读请求的服务，而RAID 4中奇偶校验磁盘不参与读操作 RAID 5包容了RAID 4，同时在相同成本下，提供了更好的读写性能,RAID 5：块交叉的分布奇偶校验,P,P,P,P,P,RAID,RAID 6 类似于RAID 5，存储了额外的冗余信息 不采用奇偶校验位的方法，使用类似Reed-Solomon码的编码 对每4位数据存储2位冗余信息 可以容忍两个磁盘发生故障,RAID 6：P+Q冗余,P,P,P,P,P,P,高性能 可靠性差,完全容错 成本高,高数据传输率 大数据量,高的总I/O率 适合随机读 大数据量,高可靠性,用于数据安全性不是很重要的高性能应用,相对于RAID5，RAID3很少使用,适于日志文件的存储,相对于RAID1，具有较低的存储开销，但写操作开销高，因此适于经常进行读而很少写的应用,适于数据安全十分重要的应用,数据库系统体系结构,数据库系统体系结构,数据库系统体系结构概述 集中式数据库系统 数据库系统 并行数据库系统 分布式数据库系统,数据库系统体系结构概述,数据库系统的体系结构与计算机系统的体系结构密切相关 集中式体系结构 集中式数据库系统 计算机的联网 客户/服务器数据库系统 并行处理能力 并行数据库系统 分布计算能力 分布式数据库系统,集中式体系结构,集中式系统,集中式系统 运行在一台机器上，数据集中存储在一台计算机中，并且不与其他计算机系统交互的数据库系统 单用户系统 个人使用的桌面系统 单CPU，1至2个硬盘，OS可以只支持单用户 数据库系统不支持并发控制 ，故障恢复能力没有或非常有限，用户接口类似QBE 多用户系统 服务大量用户，用户通过终端与之相连 多个磁盘，多个主存储器，多个CPU，多用户OS 具有并发控制、故障恢复等能力,客户-服务器系统,PC的速度更快，能力更强，价格更低 连接到集中式系统的终端被PC代替； 以前由集中式系统执行的诸如用户界面功能由PC来处理； 集中式系统变成服务器系统的作用，来响应客户系统产生的请求,客户-服务器系统,集中式或分布式- 单服务器与多服务器系统 单服务器系统: 多个客户共享一个服务器 多服务器系统: 一个客户可以对多个服务器进行访问。,客户-服务器系统,数据库功能的划分 后端（Back-end） 存取结构、查询计算和优化、并发控制、故障恢复 前端（Front-end） 表格生成工具、报表书写工具、图形用户界面工具 前端和后端的接口通过SQL或应用程序接口,客户-服务器系统,客户/服务器优点 有利于充分利用网络中的计算资源 减少网络上的传输量 高性能/价格比 可扩展性 友好的用户接口 易维护,客户-服务器系统,服务器系统的分类 事务服务器 又称查询服务器或SQL服务器 广泛用于关系数据库系统 客户向服务器发送请求，事务在服务器端执行，结果返回给客户端 可以以SQL表达请求，也可以通过应用程序接口，使用远程过程调用(RPC)机制来表达请求 Open Database Connectivity (ODBC) 使用ODBC接口的任何客户程序都可以与提供ODBC接口的任何服务器连接,客户-服务器系统,数据服务器 用于局域网中 客户与服务器之间具有高速连接 客户机与服务器的处理能力相当，并且其执行的任务主要以计算为主 数据传送到客户机器，在客户机上进行所有处理，然后再把数据传回到服务器 多用于面向对象数据库系统,并行系统,并行数据库系统 由通过高速互连网络连接在一起的多个CPU、存储器和磁盘组成 查询大数据量 处理大数量的事务 粗粒度并行机由几个能力强大的处理器组成 细粒度并行机由数千个小处理器组成,并行系统的需求和目的,数据库应用需求 查询非常大的数据库（1012字节以上） 处理很大数量的事务（每秒数千个事务） 引入并行的目的 保证即使在数据库的规模和事务的数量都大大增长时，数据库系统仍能以可接受的速度运行。,并行系统的需求和目的,关系数据库的固有并行性 数据操作间的流水线并行性age20(s) dept 数据操作间的独立并行性age20(s) dno,dean (dept) 单数据操作内的并行性age20(s),并行系统的需求和目的,数据库系统性能的度量 吞吐量(throughput)：在给定的时间区间里所能完成的任务的数量。 响应时间(response time)：对于单个任务从提交到完成所需的时间。 对于处理大量小事务的系统，通过并行地处理许多事务可以提高吞吐量。 对于处理大事务的系统，通过并行地执行每个事务中的子任务可以缩短响应时间，同时提高吞吐量。,并行系统,加速比（Speedup） 通过增加并行度来在更短的时间内运行一个给定的任务 目标：使处理任务所需的时间与所分配的处理器和磁盘的数量成反比例。 扩展比（Scaleup） 通过增加并行度来处理更大的任务 目标：使能够处理的任务的规模与所分配的处理器和磁盘的数量成正比例。,并行系统：加速比, 线性的加速比：当较大的系统的资源是较小的系统的资源的N倍，获得的加速比也是N时，称并行系统实现了线性的加速比。 亚线性的加速比：当较大的系统的资源是较小的系统的资源的N倍，而获得的加速比小于N，则称系统实现了亚线性的加速比。,并行系统：扩展比, 线性的扩展比：如果TL = TS ，则称并行系统ML对于任务Q实现了线性的扩展比。 亚线性的扩展比：如果TL TS ，则称系统实现了亚线性的扩展比。,并行系统：负影响因素,启动代价 进程初始化的启动时间，影响加速比 干扰 竞争共享资源，影响加速比和扩展比 偏斜 任务的分配是有偏的 最慢的并行步骤起决定作用 木桶效应,互连网络结构,总线（Bus） 所有系统成分通过单一的通信总线来发送和接收数据 适于少量处理器的情况，不适于并行度增大的情况 网格（Mesh） 将各种成分都安排成网格中结点，每个结点与网格中它的所有邻接结点相连接 相互间没有直接连接的结点间的通信可以通过一系列相互间有直接连接的结点来传送 有较好的扩展性 超立方体（Hypercube） 系统各成分按二进制编码，如果某两个成分的二进制编号相差1位，那么它们之间连接起来 每个成分将与log(n)个其他成分相连接，并且最多经过log(n)个链可以到达其他成分,互连网络结构,并行数据库体系结构,并行数据库体系结构,共享内存 所有处理器和磁盘通过总线或互连网络访问一个公共主存储器 处理器间的通信效率高，共享内存中数据可以被任何处理器访问 一个处理器通过写共享内存的方式来向其他处理器发送消息 规模有限制，总线会成为瓶颈，一般不能超过64个处理器 缺点 规模不能超过32个或64个处理器，因为总线或互连网络是由所有的处理器共享的，它会变成瓶颈。,并行数据库体系结构,共享磁盘 所有处理器可以通过互联网络直接访问所有的磁盘，每个处理器有自己的主存储器 以较为经济的方式提供一定的容错性 处理器间的通信通过网络来完成 存储器总线不再成为瓶颈，但与磁盘子系统的连接成为瓶颈,并行数据库体系结构,无共享 机器的每个结点包括一个处理器，一个存储器，一个或多个磁盘 一个结点上的处理器通过高速网络与另一个结点上的处理器通信 通信代价和非本地磁盘的访问高 层次的 最上层是无共享体系结构 低层是共享内存体系结构 中间是共享磁盘体系结构,并行数据库体系结构,无共享的结构是支持并行数据库系统的最好并行结构（Stonebraker 1986年提出，得到普遍接受。） 理由 共享资源最少，从而由资源竞争带来的系统干扰最小。 具有高可扩充性，处理器个数可扩展到数千甚至上万个而不增加处理器间的干扰。 在数据库查询处理过程中需要在通讯网络上进行的数据通讯量较小。 在复杂数据库查询处理和联机事务处理中可获得接近线性的加速。,分布式数据库系统,分布式数据库系统,基本定义,背景 数据库系统+计算机网络,基本定义,基本特性 分布性 数据存储在不同场地上 与集中式数据库不同 逻辑整体性 数据逻辑上是相互联系的一个整体 与分散在计算机网络不同站点上的一组没有相互联系的本地数据库区别开来,基本定义,定义 描述定义 D-DBS是一个数据集合，这些数据在逻辑上属于同一个系统，但在物理上分布在计算机网络的不同结点上 精确定义 D-DBS是一个数据集合，这些数据，分布在计算机网络的不同计算机上，网络中每个结点具有独立处理的能力，可以执行局部应用，同时每个结点也能通过网络通讯支持全局应用 分布式数据库强调场地自治性（局部应用）以及自治场地之间的协作性（全局应用） “在自治的结点之间协同工作”,D-DBS的特点,数据独立性 D-DBS除了集中式DBS的物理独立性及逻辑独立性之外，还有数据分布的独立性，也称分布透明性，即用户不必关心数据物理位置的分布 集中与自治相结合的控制结构 集中式DBS中，控制是集中的，统一由DBA维护 D-DBS中，控制是分层的： 全局DBA：管理整个数据库 本地DBA：管理本地数据库,D-DBS的特点,适当增加数据冗余 集中式DBS中，尽可能减少数据冗余以避免不一致性及节省存储空间 D-DBS中，适当增加冗余，在不同场地存储同一数据的多个副本 提高系统可靠性、可用性：一场地发生故障，可存取另一场地同一副本 提高系统性能：存取距离最近的数据副本，减少通讯代价 全局的一致性、可串行性、可恢复性 涉及多个结点,D-DBS的优点,经济上和组织上的理由 数据库的使用单位组织上、地理上是分布的 既有数据库互连 历史继承；数据资源共享 系统规模逐步扩展 增加结点，不影响现有系统运行 减少通讯开销 提高应用的本地化 提高系统的可靠性与可用性 多副本机制,D-DBS的体系结构,D-DBS的体系结构,G-外模式 全局应用的用户视图。 G-概念模式 定义D-DBS中数据的整体逻辑结构，数据如同没有分布一样。 分片模式 每一个关系可以分为若干互不相交的部分，每一部分称为一个片段。 分布模式 定义片段的存放地点,分布式数据存储,数据在分布式数据库的存储途径 复制 系统维护关系的几个完全相同的副本，这些副本存储在不同的结点上 分片 关系被划分为几个片段，各个片段存储在不同的结点上 复制+分片 关系被划分为几个片段，系统为每个片段维护几个副本,分布式数据存储,数据复制 优点 可用性 增加并行度 缺点 一致性维护 结论 有利于只读事务，增加更新事务开销,分布式数据存储,数据分片 优点 将关系分片，有利于按用户需求组织数据的分布。 如产品（内销产品，出口产品）。 分片方式 水平分片 垂直分片 导出分片 混合分片,分布式数据存储,水平分片 将关系r按行分为若干子集r1，r2，rn，每个子集ri称为一个水平片段 一个水平片段可以看成是关系上的一个选择 ri =P（i）（r） 如C_S=DNO=D08（S） 关系的重构可以通过并运算来实现 r= r1 r2rn,分布式数据存储,垂直分片 将关系r按列分为若干属性子集r1，r2，rn，每个子集ri称为一个垂直片段 一个垂直片段可以看成是关系上的一个投影 ri =Ri（r） 其中Ri是r的一个属性子集 如P_S = PNO，SAL（P） 关系的重构可以通过连接运算来实现。 r= r1 r2 rn 所有分片都包括每个元组的唯一标识码tuple_id,分布式数据存储,导出分片 导出水平分片，分片的条件不是关系本身属性条件，而是其它关系的属性条件 如SC（S#，C#，G）按学生系别分片 混合分片 关系按某种方式分片后，得到的片段再按另一种方式继续分片 如SC（S#，C#，G）按学生系别分片，再对每个片段按成绩（及格，不及格）分片,分布式数据存储,分布（网络）透明性 分片透明性 用户或应用程序只对全局关系进行操作而不必考虑关系的分片。如果分片模式改变了，通过调整全局模式与分片模式之间的映象关系来保持全局模式不变 位置透明性 用户或应用程序不必了解片段的存储位置 局部数据模型透明性 用户或应用程序不必了解局部场地上使用的是哪种数据模型,分布式数据存储,示例：设有全局关系S，它被划分为两个片段S-A（本科生），S-B（研究生），S-B有两个副本,分布式数据存储,写一个查询，输入学号，输出学生姓名 系统具有分片透明性 scanf (“%s”,S_NO); EXEC SQL select SN into ：S_NAME from S where SNO= :S_NO; printf(“%d, %s”,S_NO,S_NAME);,分布式数据存储,系统具有位置透明性，但不具有分片透明性 scanf (“%s”,S_NO); EXEC SQL select SN into ：S_NAME from S_A where SNO= :S_NO; if(!FOUND) EXEC SQL select SN into ：S_NAME from S_B where SNO= :S_NO; printf(“%d, %s”, S_NO, S_NAME);,分布式数据存储,系统具有局部模型透明性，但不具有位置透明性 scanf (“%s”,S_NO); EXEC SQL select SN into ：S_NAME from S_A at Site_1 where SNO= :S_NO; if(!FOUND) EXEC SQL select SN into ：S_NAME from S_B at Site_2(或Site_3) where SNO= :S_NO; printf(“%d, %s”, S_NO, S_NAME);,分布式数据存储,数据项的命名 每个数据项（关系、副本、片段）必须有唯一的名字，在分布式数据库系统中必须保证在不同的结点上不会用同一个名字来代表不同的数据项 途径1：名字服务器 所有名字都在名字服务器中注册，每个名字对应一个数据项 缺陷：名字服务器成为名字解析的瓶颈；依赖性大 途径2：将结点标识作为前缀加到该结点数据项的名字前面(site1.Tom, site2.Jerry) 保证唯一性，不须中央控制；不能保证网络透明性,分布式数据存储,途径3：别名 用户使用简单的别名引用数据，别名被系统翻译成完整的名字 别名到真实名字的映射形成一张别名表被存储在系统的每一个结点上。当用户引用别名时，系统通过查找别名表找到实际的数据项 对照路由表,分布式查询处理,假定每条元组100bit大小 求供应红色零件的、北京的供应商号码 select S.S# from S, P, SP where S.CITY = 北京 and S.S# = SP.S# and SP.P# = P.P# and P.COLOR = 红色,分布式查询处理,把关系P从B站传送到A站，在A站进行查询 传送时间T=1+105 100 /104=103s,S, SP,P,传P,传送时间T=总传输延迟+总数据量/传输速度,分布式查询处理,把关系S，SP从A站传送到B站，在B站进行查询 传送时间T=2+(104+106)100/104104s,S, SP,P,传S,SP,分布式查询处理,在A站连接S与SP，选出城市为北京的元组（假定有105个），然后对其中每个元组的P#，询问B站，看其是否为红色 传送时间T=2 105s,S, SP,P,问,答,分布式查询处理,在B站选出红色零件（假定有10个），然后对每个元组询问A站，看北京的供应商是否供应此零件 传送时间T=2 10=20s,S, SP,P,问,答,分布式查询处理,在A站选出北京的供应商（105个），传送到B站，在B站完成查询 传送时间T=1+ 105100/104=103s,S, SP,P,传(S) SP,分布式查询处理,在B站选出红色零件（10个），把结果传送到A站，在A站完成查询 传送时间T=1+ 10100/104=1.1s,S, SP,P,传(P),分布式查询处理,场地1： EMP(ENO, ENAME, ADDRESS, SEX, DNO) ENO(9), ENAME(10), ADDRESS(20), DNO(4),有10000条记录，每条记录100字节，共