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

n n教学目的教学目的教学目的教学目的n n本本本本章章章章在在在在一一一一个个个个更更更更高高高高的的的的层层层层次次次次上上上上认认认认识识识识数数数数据据据据库库库库系系系系统统统统，首首首首先先先先简简简简要要要要介介介介绍绍绍绍一一一一下下下下数数数数据据据据库库库库的的的的存存存存储储储储结结结结构构构构，然然然然后后后后从从从从传传传传统统统统的的的的集集集集中中中中式式式式系系系系统统统统开开开开始始始始，依依依依次次次次讨讨讨讨论论论论客客客客户户户户-服服服服务务务务器器器器系系系系统统统统、并并并并行行行行数数数数据据据据库库库库系系系系统统统统和和和和分分分分布布布布式式式式数数数数据据据据库库库库系系系系统统统统，使使使使学学学学生生生生了了了了解解解解如如如如何何何何根根根根据不同的计算环境搭建与之相适应的数据库系统。据不同的计算环境搭建与之相适应的数据库系统。据不同的计算环境搭建与之相适应的数据库系统。据不同的计算环境搭建与之相适应的数据库系统。n n主要内容主要内容主要内容主要内容n n数数数数据据据据存存存存储储储储，数数数数据据据据库库库库系系系系统统统统体体体体系系系系结结结结构构构构概概概概述述述述，集集集集中中中中式式式式数数数数据据据据库库库库系系系系统统统统，数据库系统，并行数据库系统，分布式数据库系统数据库系统，并行数据库系统，分布式数据库系统数据库系统，并行数据库系统，分布式数据库系统数据库系统，并行数据库系统，分布式数据库系统n n教学方法教学方法教学方法教学方法n n课堂讲授为主课堂讲授为主课堂讲授为主课堂讲授为主n n重点重点重点重点n n集集集集中中中中式式式式数数数数据据据据库库库库系系系系统统统统、数数数数据据据据库库库库系系系系统统统统、并并并并行行行行数数数数据据据据库库库库系系系系统统统统、分分分分布布布布式式式式数据库系统的概念及特点，分布式查询处理数据库系统的概念及特点，分布式查询处理数据库系统的概念及特点，分布式查询处理数据库系统的概念及特点，分布式查询处理n n难点难点难点难点n n分布式查询处理分布式查询处理分布式查询处理分布式查询处理第七章第七章 数据库系统体系结构数据库系统体系结构第七章第七章 数据库系统体系结构数据库系统体系结构内容出处：内容出处：1.Abraham Silberschatz1.Abraham Silberschatz数据库系统概念数据库系统概念第十一第十一章章1-31-3节，第十八章，第十九章节，第十八章，第十九章2 2，7 7节节物理存储介质物理存储介质n n特性n n数据存取速度数据存取速度n n每单位数据的成本每单位数据的成本n n可靠性可靠性n n电源故障或系统崩溃时的数据丢失电源故障或系统崩溃时的数据丢失n n介质故障介质故障n n介质分类n n易失介质（易失介质（volatile storagevolatile storage）n n电源关时数据丢失电源关时数据丢失n n非易失介质（非易失介质（non-volatile storagenon-volatile storage）n n电源关时数据持久保留，包括二级和三级存储电源关时数据持久保留，包括二级和三级存储物理存储介质物理存储介质n n高速缓冲存储器（Cache）n n最快最昂贵的存储介质，一般由操作系统来管理最快最昂贵的存储介质，一般由操作系统来管理n n主存储器（Main memory）n n用于存放可被处理的数据的存储介质用于存放可被处理的数据的存储介质n n快速访问，但一般不能存放整个数据库快速访问，但一般不能存放整个数据库n n如如果果发发生生电电源源故故障障或或系系统统崩崩溃溃，主主存存储储器器中中的的数数据会丢失据会丢失n n快闪存储器（Flash memory）n nEEPROMEEPROM：电可擦可编程只读存储器电可擦可编程只读存储器n n电源故障时数据会保存电源故障时数据会保存n n读速度：读速度：0.10.1s;s;写速度：写速度：1010s s物理存储介质物理存储介质n n磁盘存储器（Magnetic-disk storage）n n用于长期联机数据存储用于长期联机数据存储n n一般存放整个数据库一般存放整个数据库n n数据必须从磁盘移入主存才能访问数据必须从磁盘移入主存才能访问n n直接存取直接存取（direct-accessdirect-accessdirect-accessdirect-access）n n按任意顺序存取数据按任意顺序存取数据n n如果发生电源故障或系统崩溃，数据不会丢失如果发生电源故障或系统崩溃，数据不会丢失n n光盘存储（Optical storage）n nCD-ROMCD-ROM：只读，提供预先记录的数据只读，提供预先记录的数据n nWORMWORM：一次写，多次读，用于数据归档一次写，多次读，用于数据归档物理存储介质物理存储介质n n磁带存储（Tape storage）n n用于数据的备份和归档用于数据的备份和归档n n顺序访问（顺序访问（sequential-accesssequential-access）n n速度慢速度慢n n容量大容量大n n价格低价格低存储层次存储层次基本存储基本存储辅助存储辅助存储三级存储三级存储易失性存储易失性存储非易失非易失性存储性存储存储层次存储层次n n基本存储（primary storage）n n快速但易失快速但易失n ncache,main memorycache,main memoryn n辅助存储（secondary storage）n n非易失，相对快速非易失，相对快速 n n联机存储（联机存储（on-line storageon-line storage）n nflash memory,magnetic disksflash memory,magnetic disksn n三级存储（tertiary storage）n n非易失，速度慢相对快速非易失，速度慢相对快速n n脱机存储（脱机存储（off-line storageoff-line storage）n nmagnetic tape,optical storagemagnetic tape,optical storage磁盘结构磁盘结构磁盘性能估计磁盘性能估计n n访问时间访问时间n n从发出请求到数据开始传输之间的时间从发出请求到数据开始传输之间的时间n n寻道时间寻道时间（Seek timeSeek time）n n磁盘臂定位时间，即磁盘臂移动到正确的磁道所需时间磁盘臂定位时间，即磁盘臂移动到正确的磁道所需时间n n与移动距离成正比，平均寻道时间是最坏时间的与移动距离成正比，平均寻道时间是最坏时间的1/31/3n n旋转等待时间旋转等待时间（Rotational latency Rotational latency）n n寻道结束后，等待被存取的扇区出现在读写头下面的时间寻道结束后，等待被存取的扇区出现在读写头下面的时间n n平均旋转等待时间是磁盘旋转一周时间的平均旋转等待时间是磁盘旋转一周时间的1/21/2n n数据传输率数据传输率n n从磁盘获得数据或向磁盘存储数据的速率从磁盘获得数据或向磁盘存储数据的速率n n平均故障时间（平均故障时间（MTTFMTTF）n n预期系统无故障连续运行的时间预期系统无故障连续运行的时间n n是指基于全新磁盘发生故障的可能性是指基于全新磁盘发生故障的可能性RAIDRAIDn n廉价磁盘冗余阵列（RAID）n nRedundant Arrays of Inexpensive DisksRedundant Arrays of Inexpensive Disksn n是一种利用大量廉价磁盘进行磁盘组织的技术是一种利用大量廉价磁盘进行磁盘组织的技术n n价价格格上上，大大量量廉廉价价的的磁磁盘盘比比少少量量昂昂贵贵的的大大磁磁盘盘合合算得多算得多n n性能性能上，使用大量磁盘可以提高数据的并行存取上，使用大量磁盘可以提高数据的并行存取n n可可靠靠性性上上，冗冗余余数数据据可可以以存存放放在在多多个个磁磁盘盘上上，因因此一个磁盘的故障不会导致数据丢失此一个磁盘的故障不会导致数据丢失n n过过去去RAIDRAID是是大大而而昂昂贵贵的的磁磁盘盘的的替替代代方方法法；今今天天，使使用用RAIDRAID是是因因为为它它的的高高可可靠靠性性和和高高数数据据传传输输率率；因此因此“I”“I”代表代表independentindependent，而非而非inexpensiveinexpensiveRAIDRAIDn n通过冗余提高可靠性通过冗余提高可靠性n nNN个个磁磁盘盘组组成成的的集集合合中中某某个个磁磁盘盘发发生生故故障障的的概概率率比比特特定定的的单个磁盘发生故障的概率高很多单个磁盘发生故障的概率高很多 n n假假定定单单个个磁磁盘盘的的MTTFMTTF是是100,000100,000小小时时 (约约为为1111年年)，则则由由100100个磁盘组成的阵列的个磁盘组成的阵列的MTTFMTTF是是10001000小时小时(约为约为4141天天)n n冗余（冗余（RedundancyRedundancy）n n存储额外的信息，以便当磁盘故障时能从中重建存储额外的信息，以便当磁盘故障时能从中重建n n镜像镜像(Mirroring or shadowing)(Mirroring or shadowing)n n一个逻辑磁盘由两个物理磁盘组成，写操作在每个磁盘上执行一个逻辑磁盘由两个物理磁盘组成，写操作在每个磁盘上执行n n如果其中一个发生故障，数据可以从另一个磁盘读出如果其中一个发生故障，数据可以从另一个磁盘读出n n只只有有第第一一个个磁磁盘盘的的故故障障尚尚未未恢恢复复，第第二二个个磁磁盘盘也也发发生生故故障障，这这时时才才会发生数据丢失会发生数据丢失n n假假定定一一个个磁磁盘盘的的MTTFMTTF是是100,000100,000小小时时，修修复复时时间间是是1010小小时时，则则镜镜像像磁磁盘盘系系统统的的MTTFMTTF是是100,000100,0002 2/（2*102*10）=500*10=500*106 6小小时时，约约为为5700057000年年RAIDRAIDn n通过并行提高性能通过并行提高性能n n负负载载平平衡衡多多个个小小的的存存取取操操作作（即即页页面面存存取取），以以提提高高这这种种存取操作的吞吐量存取操作的吞吐量n n并行执行大的存取操作，以减少大的存取操作的响应时间并行执行大的存取操作，以减少大的存取操作的响应时间n n通过在多个磁盘上对数据进行拆分来提高传输率通过在多个磁盘上对数据进行拆分来提高传输率n n比特级拆分（比特级拆分（Bit-level stripingBit-level striping）n n将每个字节按比特分开，存储到多个磁盘上将每个字节按比特分开，存储到多个磁盘上n n例例如如，对对于于一一个个由由8 8个个磁磁盘盘组组成成的的阵阵列列，将将每每个个字字节节的的第第i i个个比比特特位位写到第写到第i i个磁盘上；它的存取速度是单个磁盘的个磁盘上；它的存取速度是单个磁盘的8 8倍倍n n对对于于由由4 4个个磁磁盘盘组组成成的的阵阵列列，将将每每个个字字节节的的第第i i个个比比特特位位和和第第i+4i+4个个比特位写到第比特位写到第i i个磁盘上个磁盘上n n块级拆分（块级拆分（Block-level stripingBlock-level striping）n n对对于于由由n n个个磁磁盘盘构构成成的的阵阵列列，文文件件的的第第i i块块 存存放放在在第第(i(i mod mod n)n)+1 1个个磁盘上磁盘上RAIDRAIDn nRAID级别n n镜镜像像提提供供高高可可靠靠性性，拆拆分分提提供供高高数数据据传传输输率率，通通过过利利用用与与奇奇偶偶校校验验相相结结合合的的磁磁盘盘拆拆分分思思想想，可可以以实现以较低成本提供冗余的方案实现以较低成本提供冗余的方案n n不不同同的的RAIDRAID级级别别，具具有有不不同同的的代代价价、性性能能和和可可靠靠性性CP代表数据的第二个拷贝表示纠错位RAIDRAIDn nRAID 0n n块块级级拆拆分分且且没没有有任任何何冗冗余余（如如镜镜像像或或奇奇偶偶校校验验位位）的磁盘阵列的磁盘阵列n n用用于于高高性性能能访访问问并并且且数数据据丢丢失失不不十十分分重重要要的的应应用用场合场合RAID 0：无冗余拆分RAIDRAIDn nRAID 1n n带块级拆分的磁盘镜像带块级拆分的磁盘镜像n n完全容错，成本高完全容错，成本高n n一一般般用用于于类类似似于于数数据据库库系系统统中中日日志志文文件件存存储储的的应应用场合用场合RAID 1：镜像的磁盘CCCCRAIDRAIDn nRAID 2n n按比特级拆分，具有内存风格的纠错码按比特级拆分，具有内存风格的纠错码n n纠错码（纠错码（ECCECC：Error-Correcting-CodesError-Correcting-Codes）n n内内存存中中每每个个字字节节都都有有一一个个奇奇偶偶校校验验位位与与之之相相连连，它它记记录录这这个个字字节节中中为为1 1的的比比特特位位的的总总数数是是偶偶数数（=0=0）还还是是奇奇数数（=1=1），如如果果字字节节中中有有一一位位被被破破坏坏，则则字字节节的的ECCECC与与存存储储的的ECCECC就就不不会会相相匹匹配配；通通过过ECCECC可可以以检检测测到到所所有有的的1 1位位错错误误；通通过过更更多多的的附附加加位位，当当数数据据遭遭到到破破坏坏时时，还还可可以以重建数据重建数据RAID 2：内存风格纠错码PPPRAIDRAIDn nRAID 3RAID 3n n磁盘控制器能够检测一个扇区是否被正确的读出磁盘控制器能够检测一个扇区是否被正确的读出n n如如果果一一个个扇扇区区被被破破坏坏，我我们们先先能能准准确确地地知知道道是是哪哪个个扇扇区区坏坏了了，然然后后对对扇扇区区的的每每一一位位，通通过过计计算算其其他他磁磁盘盘上上对对应应扇扇区区的的对对应应位位的的奇奇偶偶值值来来推推断断该该位位是是1 1还还是是0 0。如如果果其其余余位位的的奇奇偶值等于存储的奇偶值，则丢失的位是偶值等于存储的奇偶值，则丢失的位是0 0，反之为，反之为1 1n nRAID 3RAID 3效果与效果与RAID 2RAID 2一样，但只有一个磁盘的额外开销一样，但只有一个磁盘的额外开销n n使使用用NN道道数数据据拆拆分分的的RAID RAID 3 3对对一一个个字字节节的的读读写写散散布布在在多多个个磁磁盘盘中中，因因此此读读写写一一个个块块的的传传输输率率是是使使用用NN道道数数据据拆拆分分的的RAID 1RAID 1的的NN倍倍n n每个磁盘参与每个每个磁盘参与每个I/OI/O请求，每秒请求，每秒RAID 3RAID 3支持的支持的I/OI/O数较少数较少RAID 3：位交叉奇偶校验PRAIDRAIDn nRAID 4n n块块级级拆拆分分，在在一一个个独独立立的的磁磁盘盘上上为为其其他他NN个个磁磁盘盘上上对应的块保留一个奇偶校验块对应的块保留一个奇偶校验块n n读取一个块只访问一个磁盘读取一个块只访问一个磁盘n n每每个个存存取取操操作作的的传传输输率率低低，但但可可以以并并行行地地执执行行多多个读操作，从而产生较高的总的个读操作，从而产生较高的总的I/OI/O率率n n读读取取大大量量数数据据的的操操作作有有很很高高的的传传输输率率，因因为为所所有有磁盘可以并行地读磁盘可以并行地读RAID 4：块交叉奇偶校验PRAIDRAIDn nRAID 5RAID 5n n将将数数据据和和奇奇偶偶校校验验位位都都分分布布到到所所有有的的N+1N+1个个磁磁盘盘上上；对对每每个块，一个磁盘存储奇偶校验位，其余磁盘存储数据个块，一个磁盘存储奇偶校验位，其余磁盘存储数据n n例例如如由由5 5个个磁磁盘盘组组成成的的阵阵列列，第第n n块块的的奇奇偶偶校校验验位位存存储储在在第第(n n mod mod 5)+15)+1上上，其其余余4 4个个磁磁盘盘的的第第n n块块存存储储了了对对应应这这个个块块的实际数据的实际数据n n奇偶校验块不能和这个块对应的数据存储在同一个磁盘上奇偶校验块不能和这个块对应的数据存储在同一个磁盘上n n所所有有磁磁盘盘都都参参与与对对读读请请求求的的服服务务，而而RAID RAID 4 4中中奇奇偶偶校校验验磁磁盘不参与读操作盘不参与读操作n nRAID RAID 5 5包包容容了了RAID RAID 4 4，同同时时在在相相同同成成本本下下，提提供供了了更更好好的的读写性能读写性能RAID 5：块交叉的分布奇偶校验PPPPPRAIDRAIDn nRAID 6RAID 6n n类似于类似于RAID 5RAID 5，存储了额外的冗余信息存储了额外的冗余信息n n不不采采用用奇奇偶偶校校验验位位的的方方法法，使使用用类类似似Reed-SolomonReed-Solomon码码的的编编码码n n对每对每4 4位数据存储位数据存储2 2位冗余信息位冗余信息n n可以容忍两个磁盘发生故障可以容忍两个磁盘发生故障RAID 6：P+Q冗余PPPPPP高性能可靠性差完全容错成本高高数据传输率大数据量高的总I/O率适合随机读大数据量高可靠性用于数据安全性不是很重要的高性能应用相对于RAID5，RAID3很少使用适于日志文件的存储相对于RAID1，具有较低的存储开销，但写操作开销高，因此适于经常进行读而很少写的应用适于数据安全十分重要的应用数据库系统体系结构数据库系统体系结构数据库系统体系结构数据库系统体系结构n n数据库系统体系结构概述n n集中式数据库系统n n数据库系统n n并行数据库系统n n分布式数据库系统数据库系统体系结构概述数据库系统体系结构概述n n数据库系统的体系结构与计算机系统的体系结构密切相关n n集中式体系结构集中式体系结构 集中式数据库系统集中式数据库系统n n计算机的联网计算机的联网 客户客户/服务器数据库系统服务器数据库系统n n并行处理能力并行处理能力 并行数据库系统并行数据库系统n n分布计算能力分布计算能力 分布式数据库系统分布式数据库系统集中式体系结构集中式体系结构集中式系统集中式系统n n集中式系统n n运运行行在在一一台台机机器器上上，数数据据集集中中存存储储在在一一台台计计算算机机中，中，并且不与其他计算机系统交互的数据库系统并且不与其他计算机系统交互的数据库系统n n单用户系统n n个人使用的桌面系统个人使用的桌面系统n n单单CPUCPU，1 1至至2 2个硬盘，个硬盘，OSOS可以只支持单用户可以只支持单用户n n数数据据库库系系统统不不支支持持并并发发控控制制 ，故故障障恢恢复复能能力力没没有有或非常有限，用户接口类似或非常有限，用户接口类似QBEQBEn n多用户系统n n服务大量用户，用户通过终端与之相连服务大量用户，用户通过终端与之相连n n多个磁盘，多个主存储器，多个多个磁盘，多个主存储器，多个CPUCPU，多用户多用户OSOSn n具有并发控制、故障恢复等能力具有并发控制、故障恢复等能力客户客户-服务器系统服务器系统n nPCPC的速度更快，能力更强，价格更低的速度更快，能力更强，价格更低n n连接到集中式系统的终端被连接到集中式系统的终端被PCPC代替；代替；n n以前由集中式系统执行的诸如用户界面功能由以前由集中式系统执行的诸如用户界面功能由PCPC来处理；来处理；n n集集中中式式系系统统变变成成服服务务器器系系统统的的作作用用，来来响响应应客客户户系系统统产产生生的请求的请求客户客户-服务器系统服务器系统n n集中式或分布式-单服务器与多服务器系统n n单服务器系统单服务器系统:多个客户共享一个服务器多个客户共享一个服务器n n多多服服务务器器系系统统:一一个个客客户户可可以以对对多多个个服服务务器器进进行行访访问。问。客户客户-服务器系统服务器系统n n数据库功能的划分数据库功能的划分n n后端（后端（Back-endBack-end）n n存取结构、查询计算和优化、并发控制、故障恢复存取结构、查询计算和优化、并发控制、故障恢复n n前端（前端（Front-endFront-end）n n表格生成工具、报表书写工具、图形用户界面工具表格生成工具、报表书写工具、图形用户界面工具n n前端和后端的接口通过前端和后端的接口通过SQLSQL或应用程序接口或应用程序接口客户客户-服务器系统服务器系统n客户/服务器优点n有利于充分利用网络中的计算资源n减少网络上的传输量n高性能/价格比n可扩展性n友好的用户接口n易维护客户客户-服务器系统服务器系统n n服务器系统的分类n n事务服务器事务服务器n n又称查询服务器或又称查询服务器或SQLSQL服务器服务器n n广泛用于关系数据库系统广泛用于关系数据库系统n n客客户户向向服服务务器器发发送送请请求求，事事务务在在服服务务器器端端执执行行，结果返回给客户端结果返回给客户端n n可可以以以以SQLSQL表表达达请请求求，也也可可以以通通过过应应用用程程序序接接口，使用远程过程调用口，使用远程过程调用(RPC)(RPC)机制来表达请求机制来表达请求n nOpen Database Connectivity(ODBC)Open Database Connectivity(ODBC)n n使使用用ODBCODBC接接口口的的任任何何客客户户程程序序都都可可以以与与提提供供ODBCODBC接口的任何服务器连接接口的任何服务器连接客户客户-服务器系统服务器系统n n数据服务器数据服务器n n用于局域网中用于局域网中n n客户与服务器之间具有高速连接客户与服务器之间具有高速连接n n客客户户机机与与服服务务器器的的处处理理能能力力相相当当，并并且且其其执执行行的任务主要以计算为主的任务主要以计算为主n n数数据据传传送送到到客客户户机机器器，在在客客户户机机上上进进行行所所有有处处理，然后再把数据传回到服务器理，然后再把数据传回到服务器n n多用于面向对象数据库系统多用于面向对象数据库系统并行系统并行系统n n并行数据库系统n n由由通通过过高高速速互互连连网网络络连连接接在在一一起起的的多多个个CPUCPU、存存储器和磁盘组成储器和磁盘组成n n查询大数据量查询大数据量n n处理大数量的事务处理大数量的事务n n粗粒度并行机由几个能力强大的处理器组成粗粒度并行机由几个能力强大的处理器组成n n细粒度并行机由数千个小处理器组成细粒度并行机由数千个小处理器组成并行系统的需求和目的并行系统的需求和目的n n数据库应用需求n n查询非常大的数据库（查询非常大的数据库（10121012字节以上）字节以上）n n处理很大数量的事务（每秒数千个事务）处理很大数量的事务（每秒数千个事务）n n引入并行的目的n n保保证证即即使使在在数数据据库库的的规规模模和和事事务务的的数数量量都都大大大大增增长时，数据库系统仍能以可接受的速度运行。长时，数据库系统仍能以可接受的速度运行。并行系统的需求和目的并行系统的需求和目的n n关系数据库的固有并行性n n数据操作间的流水线并行性数据操作间的流水线并行性age20age20(s)deptn n数据操作间的独立并行性数据操作间的独立并行性age20age20(s)dno,dean dno,dean(dept)n n单数据操作内的并行性单数据操作内的并行性age20age20(s)并行系统的需求和目的并行系统的需求和目的n n数据库系统性能的度量n n吞吞吐吐量量(throughput)(throughput)：在在给给定定的的时时间间区区间间里里所所能能完完成的任务的数量。成的任务的数量。n n响响应应时时间间(response(response time)time)：对对于于单单个个任任务务从从提提交交到到完成所需的时间。完成所需的时间。n n对对于于处处理理大大量量小小事事务务的的系系统统，通通过过并并行行地地处处理理许许多多事务可以提高吞吐量。事务可以提高吞吐量。n n对对于于处处理理大大事事务务的的系系统统，通通过过并并行行地地执执行行每每个个事事务务中的子任务可以缩短响应时间，同时提高吞吐量。中的子任务可以缩短响应时间，同时提高吞吐量。并行系统并行系统n n加速比（加速比（SpeedupSpeedup）n n通过增加并行度来在更短的时间内运行一个给定的任务通过增加并行度来在更短的时间内运行一个给定的任务n n目目标标：使使处处理理任任务务所所需需的的时时间间与与所所分分配配的的处处理理器器和和磁磁盘盘的的数量成反比例。数量成反比例。n n扩展比扩展比（ScaleupScaleup）n n通过增加并行度来处理更大的任务通过增加并行度来处理更大的任务n n目目标标：使使能能够够处处理理的的任任务务的的规规模模与与所所分分配配的的处处理理器器和和磁磁盘盘的数量成正比例。的数量成正比例。加速比加速比 =小系统运行时间小系统运行时间大系统运行时间大系统运行时间扩展比扩展比 =小系统处理小问题运行时间小系统处理小问题运行时间大系统处理大问题运行时间大系统处理大问题运行时间并行系统并行系统：加速比加速比 线性的加速比：当较大的系统的资源是较小的系统的资源的N倍，获得的加速比也是N时，称并行系统实现了线性的加速比。亚线性的加速比：当较大的系统的资源是较小的系统的资源的N倍，而获得的加速比小于N，则称系统实现了亚线性的加速比。并行系统并行系统：扩展比扩展比 线性的扩展比：如果TL=TS，则称并行系统ML对于任务Q实现了线性的扩展比。亚线性的扩展比：如果TL TS，则称系统实现了亚线性的扩展比。并行系统并行系统：负影响因素：负影响因素n n启动代价n n进程初始化的启动时间，影响加速比进程初始化的启动时间，影响加速比n n干扰n n竞争共享资源，影响加速比和扩展比竞争共享资源，影响加速比和扩展比n n偏斜n n任务的分配是有偏的任务的分配是有偏的n n最慢的并行步骤起决定作用最慢的并行步骤起决定作用n n木桶效应木桶效应互连网络结构互连网络结构n n总线（总线（BusBus）n n所有系统成分通过单一的通信总线来发送和接收数据所有系统成分通过单一的通信总线来发送和接收数据n n适于少量处理器的情况，不适于并行度增大的情况适于少量处理器的情况，不适于并行度增大的情况n n网格（网格（MeshMesh）n n将将各各种种成成分分都都安安排排成成网网格格中中结结点点，每每个个结结点点与与网网格格中中它它的的所有邻接结点相连接所有邻接结点相连接 n n相相互互间间没没有有直直接接连连接接的的结结点点间间的的通通信信可可以以通通过过一一系系列列相相互互间有直接连接的结点来传送间有直接连接的结点来传送n n有较好的扩展性有较好的扩展性n n超立方体（超立方体（HypercubeHypercube）n n系系统统各各成成分分按按二二进进制制编编码码，如如果果某某两两个个成成分分的的二二进进制制编编号号相差相差1 1位，那么它们之间连接起来位，那么它们之间连接起来n n每每个个成成分分将将与与log(n)log(n)个个其其他他成成分分相相连连接接，并并且且最最多多经经过过log(n)log(n)个链可以到达其他成分个链可以到达其他成分互连网络结构互连网络结构并行数据库体系结构并行数据库体系结构并行数据库体系结构并行数据库体系结构n n共享内存n n所所有有处处理理器器和和磁磁盘盘通通过过总总线线或或互互连连网网络络访访问问一一个个公公共主存储器共主存储器n n处处理理器器间间的的通通信信效效率率高高，共共享享内内存存中中数数据据可可以以被被任任何处理器访问何处理器访问n n一一个个处处理理器器通通过过写写共共享享内内存存的的方方式式来来向向其其他他处处理理器器发送消息发送消息n n规规模模有有限限制制，总总线线会会成成为为瓶瓶颈颈，一一般般不不能能超超过过6464个个处理器处理器n n缺点缺点n n规规模模不不能能超超过过3232个个或或6464个个处处理理器器，因因为为总总线线或或互互连连网网络络是由所有的处理器共享的，它会变成瓶颈。是由所有的处理器共享的，它会变成瓶颈。并行数据库体系结构并行数据库体系结构n n共享磁盘n n所所有有处处理理器器可可以以通通过过互互联联网网络络直直接接访访问问所所有有的的磁磁盘，每个处理器有自己的主存储器盘，每个处理器有自己的主存储器n n以较为经济的方式提供一定的容错性以较为经济的方式提供一定的容错性n n处理器间的通信通过网络来完成处理器间的通信通过网络来完成n n存存储储器器总总线线不不再再成成为为瓶瓶颈颈，但但与与磁磁盘盘子子系系统统的的连连接成为瓶颈接成为瓶颈并行数据库体系结构并行数据库体系结构n n无共享n n机机器器的的每每个个结结点点包包括括一一个个处处理理器器，一一个个存存储储器器，一个或多个磁盘一个或多个磁盘n n一一个个结结点点上上的的处处理理器器通通过过高高速速网网络络与与另另一一个个结结点点上的处理器通信上的处理器通信n n通信代价和非本地磁盘的访问高通信代价和非本地磁盘的访问高n n层次的n n最上层是无共享体系结构最上层是无共享体系结构n n低层是共享内存体系结构低层是共享内存体系结构n n中间是共享磁盘体系结构中间是共享磁盘体系结构并行数据库体系结构并行数据库体系结构n n无无共共享享的的结结构构是是支支持持并并行行数数据据库库系系统统的的最最好好并并行行结结构构（Stonebraker 1986Stonebraker 1986年提出，得到普遍接受。）年提出，得到普遍接受。）n n理由理由n n共享资源最少，从而由资源竞争带来的系统干扰最小。共享资源最少，从而由资源竞争带来的系统干扰最小。n n具具有有高高可可扩扩充充性性，处处理理器器个个数数可可扩扩展展到到数数千千甚甚至至上上万万个个而而不增加处理器间的干扰。不增加处理器间的干扰。n n在在数数据据库库查查询询处处理理过过程程中中需需要要在在通通讯讯网网络络上上进进行行的的数数据据通通讯量较小。讯量较小。n n在在复复杂杂数数据据库库查查询询处处理理和和联联机机事事务务处处理理中中可可获获得得接接近近线线性性的加速。的加速。分布式数据库系统分布式数据库系统分布式数据库系统分布式数据库系统基本定义基本定义n n背景数据库系统数据库系统+计算机网络计算机网络DB1DB1DB1DB1DB1DB1计算机1计算机1计算机1通讯网络北京重庆上海银行系统基本定义基本定义n n基本特性n n分布性分布性数据存储在不同场地上数据存储在不同场地上与集中式数据库不同与集中式数据库不同n n逻辑整体性逻辑整体性数据逻辑上是相互联系的一个整体数据逻辑上是相互联系的一个整体与与分分散散在在计计算算机机网网络络不不同同站站点点上上的的一一组组没没有有相相互互联系的本地数据库区别开来联系的本地数据库区别开来基本定义基本定义n n定义定义n n描述定义描述定义D-DBSD-DBS是是一一个个数数据据集集合合，这这些些数数据据在在逻逻辑辑上上属属于于同同一一个个系系统，但在物理上分布在计算机网络的不同结点上统，但在物理上分布在计算机网络的不同结点上n n精确定义精确定义D-DBSD-DBS是是一一个个数数据据集集合合，这这些些数数据据，分分布布在在计计算算机机网网络络的的不不同同计计算算机机上上，网网络络中中每每个个结结点点具具有有独独立立处处理理的的能能力力，可可以以执执行行局局部部应应用用，同同时时每每个个结结点点也也能能通通过过网网络络通通讯讯支支持持全全局应用局应用分分布布式式数数据据库库强强调调场场地地自自治治性性（局局部部应应用用）以以及及自自治治场场地地之间的协作性（全局应用）之间的协作性（全局应用）“在自治的结点之间协同工作在自治的结点之间协同工作”D-DBSD-DBS的特点的特点n n数据独立性D-DBSD-DBS除除了了集集中中式式DBSDBS的的物物理理独独立立性性及及逻逻辑辑独独立立性性之之外外，还还有有数数据据分分布布的的独独立立性性，也也称称分分布布透透明明性性，即用户不必关心数据物理位置的分布即用户不必关心数据物理位置的分布n n集中与自治相结合的控制结构n n集中式集中式DBSDBS中，控制是集中的，统一由中，控制是集中的，统一由DBADBA维护维护n nD-DBSD-DBS中，控制是分层的：中，控制是分层的：全局全局DBADBA：管理整个数据库管理整个数据库本地本地DBADBA：管理本地数据库管理本地数据库D-DBSD-DBS的特点的特点n n适当增加数据冗余n n集集中中式式DBSDBS中中，尽尽可可能能减减少少数数据据冗冗余余以以避避免免不不一一致致性及节省存储空间性及节省存储空间n nD-DBSD-DBS中中，适适当当增增加加冗冗余余，在在不不同同场场地地存存储储同同一一数数据的多个副本据的多个副本提提提提高高高高系系系系统统统统可可可可靠靠靠靠性性性性、可可可可用用用用性性性性：一一场场地地发发生生故故障障，可可存取另一场地同一副本存取另一场地同一副本提提提提高高高高系系系系统统统统性性性性能能能能：存存取取距距离离最最近近的的数数据据副副本本，减减少少通讯代价通讯代价n n全局的一致性、可串行性、可恢复性涉及多个结点涉及多个结点D-DBSD-DBS的优点的优点n n经济上和组织上的理由数据库的使用单位组织上、地理上是分布的数据库的使用单位组织上、地理上是分布的n n既有数据库互连历史继承；数据资源共享历史继承；数据资源共享n n系统规模逐步扩展增加结点，不影响现有系统运行增加结点，不影响现有系统运行n n减少通讯开销提高应用的本地化提高应用的本地化n n提高系统的可靠性与可用性多副本机制多副本机制D-DBSD-DBS的体系结构的体系结构G-G-外模式外模式G-G-外模式外模式G-G-概念模式概念模式分片模式分片模式分布模式分布模式L-L-概念模式概念模式L-L-概念模式概念模式L-L-内模式内模式L-L-内模式内模式L-DBL-DBL-DBL-DBG-DBMSG-DBMSG-DBMSG-DBMSD-DBSD-DBS的体系结构的体系结构n nG-外模式全局应用的用户视图。全局应用的用户视图。n nG-概念模式定定义义D-DBSD-DBS中中数数据据的的整整体体逻逻辑辑结结构构，数数据据如如同同没没有有分布一样。分布一样。n n分片模式每每一一个个关关系系可可以以分分为为若若干干互互不不相相交交的的部部分分，每每一一部分称为一个片段。部分称为一个片段。n n分布模式定义片段的存放地点定义片段的存放地点分布式数据存储分布式数据存储n n数据在分布式数据库的存储途径n n复制复制系系统统维维护护关关系系的的几几个个完完全全相相同同的的副副本本，这这些些副副本本存储在不同的结点上存储在不同的结点上n n分片分片关关系系被被划划分分为为几几个个片片段段，各各个个片片段段存存储储在在不不同同的的结点上结点上n n复制复制+分片分片关关系系被被划划分分为为几几个个片片段段，系系统统为为每每个个片片段段维维护护几几个副本个副本分布式数据存储分布式数据存储n n数据复制n n优点优点n n可用性可用性n n增加并行度增加并行度n n缺点缺点n n一致性维护一致性维护n n结论结论n n有利于只读事务，增加更新事务开销有利于只读事务，增加更新事务开销分布式数据存储分布式数据存储n n数据分片n n优点优点将关系分片，有利于按用户需求组织数据的分布。将关系分片，有利于按用户需求组织数据的分布。如产品如产品（内销产品，出口产品）（内销产品，出口产品）。n n分片方式分片方式n n水平分片水平分片n n垂直分片垂直分片n n导出分片导出分片n n混合分片混合分片分布式数据存储分布式数