同构分布式数据库：所有站点都使用共同的数据库管理系统软件，它们彼此了解，合作处理用户的需求。本地的站点放弃了作为其自治权一部分的更改模式或者数据库管理系统软件的权利。异构分布式数据库：不同的站点具有不同的模式和不同的数据库管理系统软件。站点之间并不了解，在事务处理过程中，它们仅仅为合作提供有限的功能。模式的差别经常是查询处理中的主要问题，软件的差别成为访问多站点事务处理的障碍。我们主要讨论同构分布式数据库。分布式数据存储在分布式数据库存储一个关系的方法：复制：系统维护关系的几个完全相同的副本，各个副本存储在不同的站点。分片：系统把关系分为几个片，各片存储在不同的站点上。分片和复制的组合：一个关系划分为多个片，每个片有几个副本。数据复制如果关系r被复制，则在两个或两个以上的站点存在关系r的副本。最极端情况下采用全复制，这是每个站点都存有副本，优缺点：可用性：当包含关系r的站点之一发生故障时，关系r可以在另一个站点找到。增加的并行度：几个站点可以并行地处理涉及关系r的查询增加的更新开销:系统必须保证关系r的所有副本是一致的，否则可能产生错误的计算。因此，只要r更新，更新就必须传播到包含其副本的所有站点。数据分片对一个关系分片有两种模式：水平分片：将r的每个元组分到一个或多个片来对关系进行划分，水平划分通常用于把元组保留在它们最常用的站点上以减少数据的传输。垂直分片：对关系r的模式R进行划分透明性分布式数据库系统的用户不需要知道数据的物理位置，或者如何访问某个特定本地站点的数据。该特点称为数据透明性，可以有以下形式：分片透明性复制透明性位置透明性数据项必须有为唯一的名字，在分布式数据库中，我们必须保证两个站点没有对不同数据项使用相同的名字。解决方法：将所有名字都在中央名字服务器注册。但这样名字服务器可能成为性能的瓶颈，并且如果名字服务器崩溃，分布式系统的站点不可能允许下去。要求每个站点都将其站点标识符作为前缀加到该站点所产生的所有名字上。为了实现位置透明性，用户可以用简单的名字来引用数据项，而简单名字被本地系统翻译为完整的名字，这样，用户不需要了解数据项的真实物理位置。分布式事务局部事务：仅访问和更新一个局部数据库数据的事务；可以用集中式数据库系统的方法来保证ACID特征。全局事务：访问和更新多个数据库中数据的事务；保证ACID更加复杂。系统结构每个站点都有自己的局部事务管理器，保证在该站点执行的事务的ACID特性。各个事务管理器协调执行全局事务。其中每个站点包括两个子系统：事务管理器：管理那些访问存储在一个局部站点中数据的事务的执行。这样的事务既可以是局部事务，也可以是全局事务。维护一个用于恢复的日志参与适当的并发控制机制，协调在该站点执行的事务的并发执行事务协调器：协调该站点上发起的各个不同事务（全局或局部事务）。启动事务的执行将事务分裂为一些子事务，并将这些子事务分派到恰当的站点去执行协调事务的终止，其结果可以是事务在所有站点上都提交或事务在所有站点上都中止系统故障模式基本故障类型包括：站点故障消息丢失通信链路故障网络分割分布式系统总是可能发生消息的丢失或损坏，系统采用TCP/IP协议来处理这样的错误。如果两个站点A和B不直接相连，消息必须通过一系列的通信链路从一个站点到两一个。如果有一条链路故障，则通过该链路传送的消息必须重新路由。在某些情况下，故障可能导致某些站点之间没有连接。如果一个系统分成了两个彼此无任何连接的称为分区的子系统，我们说该系统被分割。提交协议两阶段提交协议（2PC）是最简单且使用最广泛的提交协议之一。两阶段提交考虑一个从站点Si发起的事务T，并设Si的事务协调器是Ci。提交协议当T完成执行时（即执行T的所有站点都通知Ci已完成了T的执行），Ci启动2PC协议。阶段一：Ci将记录加到日志中，并强制日志写入稳定存储器中。接着它将一条prepare T消息发送到执行T的所有站点上。当收到这样一条消息时，其他所有站点上事务管理器确定是否愿意提交T中属于它的那部分。如果不，事务管理器将加到日志中，并通过向Ci发送一条abort T消息进行响应。如果是，事务管理器把就加到日志中，并将日志强制写入稳定存储器中，然后事务管理器通过向Ci发送一条ready T消息作为回答。阶段二：当Ci收到所有站点对prepare T消息的回答时，或者当prepare T消息发送后一个预定的时间间隔过去，Ci就可以确定是否将事务T提交还是中止。如果Ci收到所有ready T消息，事务T提交，否则中止。根据结论不同，将记录或记录加到日志中，并将日志强制写入稳定存储器中。此后，协调器向所有参与站点发送消息commit T或消息abort T 。当其他所有站点收到后，将此消息记录日志。在向协调器发送ready T消息之前，执行T的站点可以在任何时候无条件中止。一旦ready T消息发出，则站点上的事务称为就绪状态。由于事务的提交需要全体一致，只要有一个站点回答abort T，事务T的命运就决定了。由于作为协调器的站点Si是执行T的站点之一，协调器可以单方面将T中止。故障处理参与站点的故障。如果协调器Ci检测到某个站点发生了故障，将采取如下：如果该站点在用ready T消息回答Ci之前发生故障，则协调器假定该站点用abort T回答。如果是之后，则协调器忽略该故障。如果参与站点Sk从故障中恢复，必须检查日志，看看故障发生时正在执行的事务的状态。日志中包含记录，站点执行redo(T)日志中包含记录，站点执行undo(T)日志中包含记录，站点必须询问Ci以确定T的最终结果。结果Ci仍在工作，它就发现Sk关于T是提交还是中止的信息。如果T已提交，Sk执行redo(T)；否则，Sk执行undo(T)。如果Ci停止工作，Sk必须试图从别的站点发现T的最终结果。通过向系统中所有站点发送querystatus T 消息来进行。站点收到这样一条消息，必须查阅其日志来看T是否在该站点执行过，如果是，还要看一看T是否提交。然后再把查询结果告诉Sk。如果每个站点都没有恰当的信息，那么Sk既不能提交也不能中止T，关于T的决定需要推迟到Sk能得到所需信息为止。因此，Sk会定期向其他站点发送querystatus 消息。日志中没有包含关于T的控制记录(abort,commit,ready)。因此，Sk在响应来自Ci的prepare T消息前发生了故障。根据上面算法，Ci必然中止T，因此Sk必须执行undo(T)。协调器的故障。如果协调器在为事务T执行提交协议的过程中发生故障，那么，必须由参与的站点来决定事务T的最终结果。如果某个活跃站点的日志中包含记录，则T必须被提交。如果某个活跃站点的日志中包含记录，则T必须被中止。如果某个活跃站点的日志中不包含记录，则发生故障的协调器不可能已经将T提交。但是可能协调器已经决定中止T而不是提交。如果上述情况不成立，则所有活跃站点都有，但此外没有别的控制记录。由于协调器已经发生故障，不等到协调器恢复，就不可能站点是否已经做出决定，或者做了决定是什么。因此，活跃站点必须等待Ci恢复。这是，别的事务可能被迫等待T，数据项在发生故障的站点不能获得，在活跃的站点也不能获得，称为阻塞问题。网络分割协调器和它所有参与者在同一分区。故障对提交协议没有影响。协调器与它所有参与者在不同分区。从其中一个分区的站点的角度看，就好象其他分区中的站点发生了故障一样。不在协调器所位于的分区的站点只需要执行处理协调器故障的协议。协调器以及与协调器在同一分区的站点遵循平常的提交协议，而认为其他分区的站点发生了故障。2PC的主要缺陷在于协调器可能导致阻塞。恢复与并发控制当故障站点重启后，恢复过程必须对疑问事务进行特殊对待：疑问事务时发现有S and 2*Qw>S  . 为了执行读操作，必须封锁足够的副本，使它们总权重大于Qr。为了执行写操作，使总权重大于Qw。降低读和写的代价能子啊站点故障下工作时间戳产生时间戳的两种方法：集中在一个站点分发时间戳，可以用逻辑计数器或自己的本地时钟分布在每个站点，每个站点用逻辑计数器或本地时钟产生一个唯一的局部时间戳。通过将唯一的局部时间戳和唯一的站点标识符连接起来，可以得到唯一的全局时间戳。弱一致性复制在主从复制下，数据库允许在主站点更新，并自动将更新传播到其他站的副本。事务可以读其他站点上的副本，但是不允许对它们更新。这种复制的重要特性是事务在远程站点上不能得到锁，为了保证运行在副本站点上看到一致的数据库视图，副本应该反映主站点上数据的事务一致性快照。副本应该反映按串行化顺序排列的先于某个事务的事务所做的更新，而不应反映按串行化顺序排在该事务之后的事务所做的更新。数据库可能配置成在主站点发生更新之后，马上将更新传播到其他站点，或者只是周期性地传播。主从复制对于分发消息特别有。在多主副本更新的情况下，更新允许在数据项的任何副本进行，并且自动传播到所有副本。这种模式是用于管理分布式数据库副本的基本模式。事务更新本地的副本，系统透明地更新其他副本。更新副本的方法是以两阶段提交来实现立即更新或使用有偏协议作为并发控制技术。许多数据库提供一种“延迟传播”将更新传播到其他站点。以延迟传播为基础的模式运行事务处理（包括更新）即使在站点断开网络时仍能进行，因此提高了可用性。在使用延迟传播时，以下两种方法通常使用：在副本上的更新转化为在主站点上的更新，然后延迟传播到所有副本。更新在任何副本上执行，并传播到所有其他站点。死锁处理如果允许死锁发生并依赖于死锁检测，则分布式系统中的主要问题就是决定如何维护等待图。处理这个问题的技术要求每个站点维护一个局部等待图。在集中死锁检测的方法中，系统在一个单独站点构造和维护一个全局等待图。 可用性高可用性：数据库在任何时候能工作健壮性：必须在多种不同类型故障发生时仍能工作。能检测故障，重构系统以继续计算，以及在处理器或链路修复后能进行恢复。链路故障征兆：通过某链路的一个消息进行多次重传，却得不到确认。在站点间使用多条链路网络分割征兆：网络试图为此消息寻找另一条路径，却无法找到。区分网络链路故障和站点故障时不可能的，任何重构模式必须涉及成能够在网络分割情况下正确运行：两个甚至更多中央服务器在不同的分区中选出不止一个分区更新某个被复制的数据项基于多数的方法每一个数据对象都存储它的一个版本号来检测它最后一次写入的时间。每当一个事务写一个对象的时候要以如下方式更新版本号：如果数据对象a复制到n个不同的站点，那么一个锁请求消息必须发送到存储a的n个站点的一半以上。事务直到获得a的大多数副本的锁后才对a操作读操作检查所有已经加锁的副本，读取具有最高版本号的值。写操作和读操作一样，也要读所有的副本来找到最高版本号。新的版本号比最高的版本号多1.在事务处理期间的故障也可以容忍。读一个、写锁有可用的方法将单位权授予所有站点来实施有偏协议：设读的法定人数为1，设置写的法定人数为n（所以站点）。在这种情况下，不需要使用版本号。但是，主要容纳数据项的一个站点发生故障，对该数据项的写操作就不能进行。为了使发生意外故障工作能够进行，我们使用读一个、写所有可用的协议。这样，事务管理器就不等待故障站点恢复而继续工作。在可能发生网络分割的情况下，使用读一个、写所有可用的模式会导致不一致性。站点重建将修复的站点或链路重建到系统必须小心。故障站点恢复后，必须发起一个过程来更新其系统表，使之能反映该站点停止工作后发生的变化。一个简单的方法是故障站点重新连入后，暂时让整个系统停止，但是，在大多数应用中不可行。使用一些技术可以在对任意数据项授予读或写锁前，站点必须确保它已经更新称为最新的数据项。如果一个故障链路恢复，两个或更多分区就能重新连接起来。由于网络分割限制了部分站点或所有站点可允许的操作，应该将链路的恢复迅速通知所有站点。与远程备份比较使用远程备份系统时，操作在单一站点上执行，只有数据和日志记录复制到其他站点。特别地，远程备份系统有助于避免两阶段提交及其导致的开销。同时，事务只需和主站点联系，避免了在多个站点运行事务代码的开销。另一方面，通过具有多个可用副本并使用多数协议，复制可以提供更高的可用性。协调器的选择备份协调器是一个可以在完成其他任务同时，还在本地维护足够信息，使它可以在分布式系统带来最小限度干扰的情况下担负起协调器角色的站点。所有直接发给协调器的消息都会被协调器及其备份收到。协调器和它的备份区别在于，备份不会采取任何影响其他站点的动作，这些动作由真实的协调器进行。备份方法优点在于它能立即将处理继续下去的能力。避免了分布式系统从协调器故障恢复所需的大量延迟。其缺点在于协调器任务的重复执行带来的开销。在缺少指定的的备份协调器或者为了处理多种故障时候，可以由那些活跃站点动态地选出新的协调器。选举算法可以使站点以分散的方式选出一个站点作为新的协调器。算法要求系统中每个活跃站点对应一个唯一的标识号。用于选举的威逼算法：设站点Si的标识号为i。同时假设所选出的协调器总具有最大标识号的站点。当协调器故障时，算法必须选出具有最大标识号的活跃站点。该算法将高号码发送到系统的每个站点。另外，该必须提供一种能使从故障中恢复的站点辨认出当前协调器的机制。假设站点Si发出的请求在预定时间T内没有得到协调器的回答，这时假设协调器发生故障，Si视图选举自己作为新协调器的站点。站点Si给每个据偶更大标识符的站点发一条选举信息。接着Si等待一个时间间隔T，等这些站点的任何一个回复，如果在时间站点T内没有收到，就假设具有大于i的号码的所有站点都发生故障，于是选举自己，并给具有小于i的标识号的所有站点发消息通知新协调器的站点。如果Si收到回答，就开始一个时间间隔T’来接收通知自己一个具有更大标识号的站点已被选中的消息。如果Si在T’时间内没有收到消息，就假设具有更大标识号的站点发生了故障，站点Si重新开始算法的执行。当故障站点恢复后，马上开始执行相同算法。如果没有具有更大标识号的活跃站点，恢复后的站点就强迫具有较小数字的所有站点让自己成为协调器站点。如果出现网络分割，威逼算法在各分区选举出一个分离协调器。 分布式查询处理代价：磁盘访问量数据在网络上的传输代价通过在几个站点并行地处理查询的一部分，可能得到的性能收益。查询转换考虑一个查询“找出关系r上所有元组”，关系r可能被分片，复制，也可能既被分片也被复制。如果关系r被复制，我们就需要对副本进行选择。如果所有副本都没有分片，我们就选择使用传输代价最小的副本。但是如果被分片了，需要进行连接算法或并算法来重构关系r。简单的连接处理假设三个关系连接，三个关系既没复制又没分片，且关系r存储在站点S1上，关系s存储在站点S2上，关系k存储在站点S3上。设S1表示提出查询的站点，系统需要在站点S1产生结果。三个策略：将三个关系的副本都送到站点S1。然后本地连接将关系r的一个副本送到站点S2，在S2上计算temp1=r ⋈ s 。将temp1从S2送到S3，在S3计算temp2=temp1 ⋈ k。最后将结果temp2送到S1设计与上一个策略类似的策略，只是交换S1，S2，S3的角色。没有一个策略是最好的。半连接策略我们假设希望计算表达式r1 ⋈ r2，其中r1和r2分布存储在站点S1和S2上。令r1和r2的模式分别为R1和R2。假设希望在站点S1上得到结果。如果r2中有许多元组不能和r1中的任何元组相连接，那么把r2送到S1会使我们必须传输对结果无贡献的元组。一个可能的策略：在S1上计算temp