分布式数据库

分布式数据库第一节基本概念一，集中式数据库系统和分布式数据库系统1．集中式数据库系统，是指数据库中的数据集中存储在一台计算机上，数据的处理也集中在一台计算机上完成。2.分散式数据库系统，采用了数据分散存储的办法，将数据库分成多个建立在多台计算机上，此时各个数据库的管理和应用程序是分开的并独立的，这种系统称为分散式系统。3.分布式数据库系统，是指数据库数据存放在计算机网络上的不同场地的计算机中，每一个计算机都有自治处理能力，并完成局部应用；而每一场地也参与（至少一种）全局应用程序的执行，全局应用程序可以通过网络通信访问系统中的多个场地的数据，这样的系统，称为分布式数据库系统。4.分布式数据库管理系统DDBMS，是分布式数据库系统的核心，它是分布式数据库系统中的一组软件，负责分布式数据库的建立、查询、更新、复制、管理的软件。5.局部自治性，是指有独立处理能力并能完成局部应用。区分一个系统是分散式还是分布式系统，就是判断系统是否支持全局。二，分布式数据库体统的透明性分布式数据库系统具有位置透明性和复制透明性，使用户看到的系统如同一个集中式数据库系统。位置透明性：是指用户或应用程序员应当了解分片情况，但不必了解片段的存储场地。位置透明性位于分片视图与分配视图之间。数据复制：是指数据在每个场地的重复存储。复制透明性：即用户或程序员不必关心数据库在网络中各个节点的数据复制情况，更新操作引起的波动由系统来处理。三，分布式数据库的特点数据的分布性。分布式数据库中的数据分布在网络中的各个节点。统一性。包括数据在逻辑上的统一性和数据在管理上的统一性。逻辑上的统一性指的是分散在计算机网络各个节点上的数据库构成一个在逻辑上单一的数据库，呈现给用户的如同一个统一的集中式数据库。管理上的统一性指的是分布式数据库是由分布式数据管理系统统一管理和维护。透明性。用户在使用数据库时，与使用集中式数据库一样，无需知道其所关心的数据存放的位置，存储了几次。用户需要关心的仅仅是整个数据库的逻辑结构理想的分布式数据库所具有的规则和目标局部节点自治性。与集中式DBS相比，分布式DBS中数据库的存储是分布性的，即数据不是存储在一个场地。与分散式DBS相比，分布式DBS中的数据库具有与集中式DBS相比，分布式DBS中数据库的存储是分布性的，即数据不是存储在一个场地。与分散式DBS相比，分布式DBS中的数据库具有“逻辑整体性”，即从表面看，分布式数据库的数据分散在各个场地，但这些数据在逻辑上却是一个整体，如同一个集中式数据库。能继续操作。具有位置独立性（位置透明性）。分片独立性（分片透明性）。数据复制独立性（复制透明性）支持分布查询处理。支持分布事务管理。具有硬件独立性。具有操作系统独立性。具有网络独立性具有DBMS独立性。三，分布式数据库系统的分类1.按照DDBMS软件的同构度来分，分为同构和异构分布式数据库。同构分布式数据库（homogeneousdistributeddatabase）中，所有的站点都使用同样的数据库管理系统软件，彼此了解，合作处理用户需求。异构分布式数据库（heterogeneousdistributeddatabase）中，不同的站点有不同的模式和不同的数据库管理系统软件。如果细分可以分三类：如果细分可以分三类：同构同质型DDBS：不同的站点采用同一类型的数据模型，相同的DBMS.同构异质型DDBS：不同的站点采用同一类型的数据模型，不同的DBMS.异构性DDBS：不同的站点的数据库模型是不同的，DBMS也不同。2.按照局部自治度来分，分为：无局部自治和局部自治局部自治分布式数据库：当局部事务允许对服务器软件进行直接存取，则系统称为有一定的局部自治。无局部自治分布式数据库：当对DDBMS的存取必须通过客户软件，则系统称为无局部自治；四，分布式数据库系统的模式结构全局外模式：它们是全局应用的用户视图，是全局概念模式的子集。全局概念模式：定义分布式数据库中数据的整体逻辑结构。分片模式：每一个全局关系可以划分为若干个不相交的部分，每一个部分称为一个片断。分片模式就是定义片段及全局关系到片断的映像。（1：M）分布模式：每一个片断物理上可以分配到网络不同的节点上，分布模式定义片断的存放节点。局部概念模式：被分配到某个场地上的逻辑片断的集合。局部内模式：局部内模式是DDB中关于物理数据库的描述。这种6层模式结构具有显著的特征：数据分片和数据分布概念的分离，形成了“数据分布独立性”概念。数据冗余的显式控制。数据在各个场地的分配情况在分配模式中一目了然，便于系统管理。局部DBMS的独立性。这个特征也称为：“局部映射透明性”。分布式数据库的优点：具有灵活的体系结构。适应分布式管理和控制机构。经济性能优越。系统可靠性高。局部应用的响应速度快。可扩展性好，易于集成现有系统。分布式数据库的缺点系统开销大，主要在通信部分。复杂的存取结构，集中式系统的存取数据技术，在分布式不再适用。数据的安全性和保密性较难处理。第二节分布式数据库系统的体系结构分布式数据库数据存储可以从两个角度考察：分片和分配。一，分布式数据库数据分配：数据分配就是数据在计算机网络各个场地上的分配策略，也称为数据分布。1.数据分配的策略集中式：所有数据均安排在同一场地。分割式：数据在每个场地重复存储。全复制：数据在每个场地重复存储。混合型：数据库分成若干个可相交的子集，每一个子集安置在一个或多个场地上，但每一个场地未必保存全部数据。四个评估因素：存储代价、可靠性、检索代价、更新代价。存储代价和可靠性是一对矛盾的因素。检索代价和更新代价，是一对矛盾的因素。二，数据分片数据分片是指数据存放单位不是全部关系，而是关系的一个片断，也就是关系的一部分。分布式数据库中的数据可以被复制在网络场地的各个物理数据库中，数据分片是通过关系代数的基本运算实现的。1.数据分片包括三种：水平分片：按一定的条件把全局关系的所有元组划分为若干个不相交的子集，每个子集为关系的一个片断。垂直分片：把一个全局关系的属性集分成若干个子集，并在这个子集上作投影运算，每个投影为一个垂直分片。混合分片：将水平分片和垂直分片方式综合起来使用，则为混合分片。2.数据分片应遵循的原则完备性条件：必须把全局关系的所有数据映射到各个片断中，决不允许发生属于全局关系的某一个数据不属于任何一个片断。重构条件：划分所采用的方法必须确保能够由各个片断重建全局关系。（指垂直分割）不相交条件：要求一个全局关系被划分后，得到的各个数据片断互不重叠。（指水平划分）。三，分布式数据库系统的体系结构全局外模式：它们是全局应用的用户视图，是全局概念模式的子集。全局概念模式：它们定义了分布式数据库中所有数据的逻辑结构。分片模式：定义了片断以及全局关系与片断之间的映像。这种映像是一对多的，即每个片断来自一个全局关系，而一个全局关系可分为多个片断。分配模式：片断是全局关系的逻辑部分，一个片断在物理上可以分配到网络上的不同场地上，分配模式根据分配策略的选择定义片断的存储场地。四，分布的透明性分布透明性，也称为分布的独立性，是指用户不必关心数据的逻辑分片，不必关心数据存放的物理位置等细节，也不必关心各个场地上数据库的数据模型。分片的透明性：用户无需知道关系是如何分片的。位置的透明性：用户不必知道数据存放的物理位置。局部数据库模型的透明性：这个透明性位于分配视图与局部概念视图之间，指用户或应用程序要了解分片及各个片断存储的场地，但不必了解局部场地使用了何种数据模型。（复制透明性：用户不必关系复制了什么数据对象，也不必关系副本的存放位置）分布式数据存储（复制和分片）对于一个要存储到数据库中的关系R，在分布式DBS中有两种方法：（1）复制：系统维护这个关系的几个副本，各个副本存储在不同的场地。（2）分片：把关系划分为几个片断，每个片断存储在不同的站点上。分片和复制可以组合，一个关系可以分成几个片，每个片有几个副本。数据复制如果关系r被复制，则在两个以上关系中存在副本，极端情况下是每个场地都有一个副本，称为全复制（fullreplication）数据复制的优点可用性。当包含关系r的站点之一发生故障，系统仍可以运行。增加的并行性。由于有多个副本，增加了查询操作的并行性。增加了更新的开销。复制的缺点复制可以提高read操作的性能，但对数据更新的开销增大，一致性维护复杂。如何保证两个站点没有对不同的数据项实用相同的名字？使用中央名字服务器（nameserver）注册，确保名字不重复使用在名字的前面加上站点的标识符以示却别。但破坏了位置的透明性。五，分布式数据库管理系统distributeddatabasemanagementsystem分布式数据库管理系统的结构：LDBMS。局部场地上的数据库管理系统，其功能是建立和管理局部数据库，提供场地自治、执行局部应用及全局查询的子查询。GDBMS。全局数据库管理系统，其功能是提供分布透明性，协调全局事务的执行，协调各局部DBMS以完成全局应用，保证数据库的全局一致性，执行并发控制，实现更新同步，提供全局恢复功能。全局数据字典。存放全局概念模式、分片模式、分布模式的定义及各模式之间的映像的定义。存放用户存取权限、数据库安全性，完整性约束条件。通信管理（CM）。在分布数据库各场地之间传送消息和数据，完成通信功能。对全局控制有几种方式：全局控制集中的DBMS：全局控制成分GDBMS集中在一个场地上。全局控制分散的DBMS：全局控制成分GDBMS分散在各个场地上。全局控制部分分散的DBMS：控制成分GDBMS分散在某些场地上。第三节分布式事务处理复习：事务的ACID特性原子性atomicity：事务是数据库的逻辑工作单位，事物的操作要么都做，要么都不做。一致性consistency：事务执行的结果必须是使数据库从一个一致性状态转换为另一个一致性状态。隔离性isolation：数据库中一个事务的执行同其他事务的执行是隔离的，互不干扰。持续性durability：事务一旦提交，则对数据库中数据的改变就是永久的，以后的操作或故障不会对事务的操作产生影响。局部事务localtransaction：仅访问和更新一个局部数据库的事务。全局事务globaltransaction：访问和更新多个局部数据库中数据的事务。一，分布式事务的系统结构组成：事务管理器和事务协调器（1）事务管理器，transactionmanager，管理那些访问存储在一个局部站点中数据的事务的执行（即可以是局部事务，也可以是全局事务）。维护一个用户恢复的日志。参与适当的并发控制，以协调在该站点执行的事务的并发执行。（2）事务协调器transactioncoordinator，协调该站点上发起的各个不同事务的执行（即有全局事务，也有局部事务）。（集中式DBS不需要事务协调器）启动事务的执行。将事务分裂为一些子事务，并将这些子事务分派到恰当站点上执行。协调事务的终止，其结果是事务在所有站点上都提交或都终止。复习集中式数据库事务的故障：复习集中式数据库事务的故障：1.事务内部故障（包括可预期的和不可预期的）2.系统故障（软故障）3.介质故障（硬故障）二，分布式数据库事务的系统故障模式分布式系统的故障包括集中式的故障类型（事务内部故障、系统故障、介质故障、其他故障）外，分布式系统另外还有一些基本故障类型：站点故障、消息丢失、通信链路故障、网络分割。故障恢复的难度，从小到大依次为：一是节点故障；二是节点故障和消息丢失，但无分区故障；三是节点故障、消息丢失、分区故障。三，两段提交协议为了保证事务的原子性，就必须做到事务T要么在所有站点上都提交，要么都终止。为了保证这一原子特性，T的事务协调器必须执行一个提交协议。两端提交协议two-phasecommitprotocol，2PC是最简单和使用最广泛的提交协议。设定从一个站点Si发起一个事务T，并设Si的事务协调器是Ci阶段1。Ci将记录<prepareT>写入日志中，并存入稳定存储器中。发送一条prepareT到所有站点。各站点接收到此消息，先加入到日志中去。当站点事务管理器确定如果不愿意提交属于该站点的事务，事务管理器把记录<noT>写入日志，并向Ci发送一条abortT的消息。当站点事务管理器愿意提交属于该站点的事务，则事务管理器把记录<readyT>写入日志，并向Ci发送一条readyT的消息。阶段2。当Ci发送prepareT消息一段预定时间间隔或者收到所有站点的回复时，Ci就可以确定该事务是提交还是终止。如果Ci收到所有站点的readyT消息，则将记录<commitT>写入日志，并向所有参与站点发送<commitT>消息。如果Ci收到有一个站点的abortT消息，则将记录<abortT>写入日志，并向所有参与站点发送<abortT>消息。由于事务的提交要求全体站点一致，只要有一个站点回答abortT消息，则事务T就被终止。只有全体站点响应readyT则事务被提交。并把记录写入日志文件。当所有站点收到commitT消息后，将<commitT>写入日志文件，并提交该事务。两阶段提交的故障处理1.参与站点的故障failureofaparticipatingsite如果协调器Ci监测到某个站点发生故障，如果该站点在用readyT消息回答Ci之前发生故障，则协调器认为该站点是用abortT消息回答的，则事务终止。如果该站点是在发送readyT之后发生故障的，则协调器按照通常方式提交协议的剩余部分，忽略该站点的故障。此时，该站点故障恢复后，检查日子文件，根据日志文件作以下操作：日志文件包含<commitT>记录。执行redo(T)。日志文件包含<abortT>记录。执行undo(T)。日志文件包含<readyT>记录。询问Ci确定T的最终结果，执行相应的redo(T)或者undo(T)操作。2.协调器故障failureofthecoordinator如果协调器在为事务T执行提交协议的过程发生故障，则必须根据参与站点的日志决定T的最终结果。如果某个活跃站点日志中包括<commitT>记录，则T必须被提交。如果某个活跃站点日志中包括<abortT>记录，则T必须被终止。如果某个活跃站点日志中不包含<readyT>记录，则T被终止。如果上述情况都不成立，则所有活跃站点都包含<readyT>记录，还有别的站点包含<commitT>或<abortT>记录，因此必须等待Ci故障恢复，这段时间，其他事务必须被迫等待，因此发生阻塞。3.网络分割networkpartition协调器同他的参与者处于一个分区，这种情况故障对提交协议没有影响。协调器和他的参与者处在不同分区，不在协调器分区的站点执行处理协调器故障的协议；在协调器分区的执行一般提交协议。因此，2PC的主要缺陷在于发生协调器故障时可能导致阻塞，这种情况必须等到Ci恢复才能做出是提交还是终止T的决定。恢复与并发控制为了处理分布式提交协议（2PC或3PC），恢复过程必须对疑问十五进行特殊对待：疑问事务是发现有<readyT>日志记录，但未发现<commitT>或<abortT>的日志记录的事务。如果协调器发生故障，而任何站点都没有关于未完事务的状态（提交/终止），在使用2PC时就存在着恢复被阻塞的可能。为了克服这个问题，恢复算法通常提供对在日志中记载封锁信息的支持（假设这里用于并发控制），此时所写的日志记录不再是<readyT>，而是<readyT,L>，其中L是写入日志记录时事务T所有的写锁的列表。当恢复时，对所有的写锁需要从新获取。当所有疑问事务的锁从新获取完成后，即使疑问事务的提交-终止状态确定之前，该站点的事务处理就可以开始了。疑问事务的提交和回滚与新事务的执行是并发的。这样，站点的恢复就会加快，并且不会产生阻塞。三，三阶段提交3PC三阶段提交是两阶段提交的扩展，在某种前提条件下可以避免阻塞问题，只有在大于k个站点发生故障时才发生阻塞。如果网络分割会产生多于k个站点，仍然会发生阻塞。3PC协议由于开销太大，没有被广泛使用。四，并发控制并发控制是为了保证事务的原子性，是保证多个事务的高效、正确的执行，是分布式事务管理的基本任务之一。在数据库系统中，事务是以发出读操作和写操作原语的方式来存取数据的，事务的并发控制就是保证事务的并发操作正确执行。在实际应用中，可以采用锁的方法和时间戳方法来实现事务的可串行化调度。1.锁模型基本思想原则：事务对任何数据的操作必须先申请该数据项的锁，只有申请到锁以后，即加锁成功以后，才可以对数据项进行操作。操作完成以后，要释放已申请的锁。通过锁的共享与排斥的特性，实现事务的可串行化。对于基本锁，不区分共享锁和排他锁，有可能降低事务的并发程度。读锁，共享锁：是对数据项进行读操作时加的锁，可共享操作。写锁，排他锁：是对数据项进行写操作时加的锁，不可共享操作。读锁写锁读锁共享排他写锁排他排他两段锁协议：任何事务对数据项的操作先加锁，加锁的方法是事务中全部加锁操作在第一个解锁操作之前完成。因此，加锁和解锁分布在事务的两个阶段，故称为两段锁协议，即2PL协议。在集中式数据库中,2PL可以保证事务可串行化调度。在分布式数据库系统中，也遵循两段锁协议，实现分布式事务的并发处理。因此，全局事务遵循2PL协议时，各子事务也遵循2PL协议。2.时间戳模型对每一个事务在激活是分配一个时间戳，唯一标识该事务和事务激活的顺序。事务对数据项的操作时，先把自己的时间错赋予该数据项。当事务间发生冲突时，时间戳小的先执行，时间戳大的后执行。当一个事务的时间戳小于另一个已经执行的事务时，该事务被终止，并重新启动，且赋予一个新的时间戳。时间戳分为读时间戳和写时间戳。在锁的方式中，当两个以上的事务互相锁住对方所需的资源时，系统就发生了死锁。因此需要有死锁检测和消除机制及死锁防治机制，进行死锁后处理和预防。而时间戳协议中，事务要么继续执行，要么终止，重新获得时间戳，因此不会发生死锁。但重新启动频繁。时间戳的算法有两种：基本时间戳方法和保守时间戳方法。第四节分布式查询分布式查询有两个新特点：网络通信速率较低，因此考虑查询处理时各节点之间通信造成的明显时间延迟。由于各节点有独立的计算机，有了在各台计算机上进行并行处理各个子查询部分，以及在各节点之间进行并行传送数据的可能性。分布式数据库系统中的查询处理过程：由全局数据库管理系统在查询产生节点时对查询进行词法和语法分析，生成查询树。对全局查询树进行变化，查询分解，把查询分解成若干个子查询，确定处理子查询的运算次序和节点。对子查询进行优化和执行。子查询结果的汇总和处理。一，全局查询树的变换为了提高查询执行效率，可对全局查询树进行下述变换。用片断替换查询树中的全局关系。水平分割用“并”操作，垂直分割用“联结”操作。尽可能把选择、投影等一元操作推向查询树的叶端。减少查询中间结果，降低网络数据传输。合并公共子表达式。减少查询次数。消除空的关系和冗余度。使用逻辑化简规则消除空关系和冗余度。移去无用的垂直叶片，减少联结操作和网络传输。二，副本的选择和多副本的更新策略。为了提高访问的局部性和系统的可用性，关系和片断常常设置多个复本，分布于不同的节点，这样，查询处理时就存在复本选择的问题：尽可能提高访问的局部性，减少远距离访问。尽可能减少通信开销，尤其要减少大量数据传输。适当考虑节点负荷的平衡。虽然多复本可以提高访问的局部性和系统的坚固性，但是更新时，必须保证多复本的一致性：在事务提交前更新全部复本。（只要有一个复本未更新，则事务就失败）立即更新有效节点的复本，失效节点复本留待修复后更新。主复本法。指定一个复本为主复本，其他为副本。更新时只更新主复本，所有副本根据主复本广播的内容进行更新。主复本和副本之间可能出现不一致。为此可以让每个副本附加一个版本号，如果主复本的版本号同副本的版本号相同，则可以读副本，否则，读主复本或待更新后再度副本。快照法。是指数据在某一时刻的状态，他不随数据库中的数据更新而即时更新。如统计报表中的“截止×月×日止”。三，查询树的分解查询树的分解一般采用后序遍历法。全局优化的核心问题是执行分布式联结的策略。四，分布式查询通常采用半联结的查询优化策略有时候作联结操作时，并不需要将整个关系（或片断）都传送到对方，只要传送联结时与对方匹配的元组就够了。半联结可以减少节点间的数据传输量和运算量。在广域网中，通信开销是主要矛盾，通常采用半联结方式的查询优化策略。五，查询优化应考虑的问题优化的代价函数对系统的影响：响应时间。系统的吞吐量。总的局部资源利用率（CPU利用率、FO操作等）网络通信量。网络中各节点负载的均衡分布。在集中式数据库系统中，已经建立的优化算法通常是以耗费的CPU时间和FO操作来衡量代价函数的。分布式数据库系统则比较复杂，全局优化执行方案受下面因素的影响：多种复本的选择。多种执行次序。对于多元联结个并操作，利用结合律和交换律组成多种次序。多个执行地点。多种联结方法。分布式数据库的查询优化按实现方法可以分为：静态优化法和动态优化法。静态优化法：在事务执行前进行优化。动态优化法：在事务执行过程中进行优化，优化质量高于静态优化法。第五节网络环境下的数据库系统的设计实施任务：定义全局数据库的概念模式。设计物理数据库，将概念模式映射到存储区域并确定适当的存取方法。设计分片。确定将全局关系进行水平、垂直、或混合划分，以便分配。设计片段的分配。确定片断分配到各个场地的分配情况和复制的片断。一，数据的分布设计1．数据划分原则和分片方法按DDB外部特征来划分。如按照部门来划分。按DDB的内部特征来划分。对DDB的组成性质划分后仍应保持其原有的性质。划分后个逻辑关系必须遵守下列原则：完整性原则。不允许某些数据属于全局但不属于任何一个片断。可重构原则。对于水平划分的可利用‘并操作’重构，对于垂直划分的，可利用联结操作重构。不相交原则。不允许一个全局关系的某些数据即属于该全局关系的某一个片断，同时又属于该关系的另一个片断（适用于水平划分）。（3）分片方法：水平分片、垂直分片和混合分片。水平分片：按一定的条件将关系按行（水平方向）划分为不相交的若干子集，每个子集就是一个片断。垂直分片：将关系按照列（垂直方向）分为若干子集，每个子集就是一个片断。混合分片。采用水平分片和垂直分片相结合的方法进行划分。2.数据分配的策略和一般准则DDB中全局关系经逻辑划分后，其分配通常由4种类型。集中型。数据虽经划分，但所有逻辑片断仍然存放在一个场地上。分割型。数据划分后，所有逻辑片断各自分配到一个场地所有场地上分配的知识全局关系的一个子关系。全复制型。数据被划分后，所有逻辑片断在每个场地上均重复设置。混合型。数据被划分后的逻辑片断根据需要分配。共享的片断重复设置，高度私用的片断只设置在所需的片断。对各种划分方法的评估。4个评估因素:存储代价、可靠性、更新代价、检索代价。集中型：存储代价：无；可靠性：差；更新代价：无；检索代价：高。分割型：存储代价：无增加；可靠性好；更新代价：无；检索代价：低。全复制型：存储代价高；检索代