论文部分内容阅读
[摘 要] 在多服务器系统中,数据分配和负载平衡是互相影响和互相联系的,但在很多情况下因为没有考虑到数据和负载的相互作用,网络的性能不是特别理想。因此,允许独立提交是解决阻塞问题的关键,在实际的Client/Server系统开发中,并不是所有的复制服务器上的数据都要自始至终维护一个一致的复制数据视图和进行即刻的更新传播,本文对之进行了行之有效的方法探讨。
[关键词] 服务器 网络传输 负载均衡
采用多复制服务器系统是提高系统可用性最有希望的手段,但是,复制数据更新过程的阻塞问题是整个系统性能的一个瓶颈。复制数据更新的首要困难是控制多副本的一致性,通常采用的方法包括投票(Voting)和令牌(Token)传递方法,但是,这些方法的复杂性给实现带来困难,更新传播的另一个问题是保证事务的原子性,两阶段提交协议(2PC)是使用最多的保证事务原子性的提交协议,但是它由事务协调程序(Coordinator)决定各个参与者是否可以提交,这样就降低了系统的可用性,并增加了事务提交的延迟时间。网络环境的不健壮性使得所有参与结点同时提交的可能性减少,不可避免地造成能够正常提交的结点等待因失效不能提交的结点,而形成事务提交的阻塞。
一、多复制服务器的数据更新
我们假定在网络上有多个等同的复制服务器结点(简称结点),它们或者处于连接状态,或者处于非连接状态。但是在连接状态下通信是可靠的,网络各个结点之间能够保持消息的顺序,保证消息的内容正确到达,并且提供超时检测。系统出现故障的情况有两种,或者是各个结点之间处于非连接状态而不能通信,或者某个结点可能会因失效而不能正常工作,在每个结点有一个本地的逻辑时钟,在整个系统内对各个结点操作的定序可以利用Lamport邮戳机制解决。操作对象可以唯一标识,并且数据操作是一元的,它只影响到本地数据,每个事务中的数据操作不会跨越多个数据对象,在每个结点都有一个操作日志,其格式是(事务标识,邮戳,事务协调服务器编号,数据对象标识,操作标识,操作参数),其中邮戳是指记录在日志里某事务中操作的时间。在每一个结点建立一个用于数据协调目的的协调日志,其格式是(数据对象标识,结点标识),以便在数据协调时参考。
1、更新算法
算法1.更新发起点X对数据对象D开始更新
UpdateCoordinator(D)
{//更新发起点X对数据对象D开始更新
if(数据对象D的最后一次事务是失败的)
退出函数,或者先触发数据协调过程再调用此函数;
写Begin-Trans到操作日志;
发送Begin-Trans到各个复制结点,并且把此事务的超时时间发送给各结点;
while(事务写操作进行中)
{
执行写操作Wi(D)并记录操作完成时间Ti;
记录写操作Wi(D)到操作日志;
等待各个结点的确认;
if(等待超时)
对于所有未收到确认消息的结点Y,插入(D,Y)到协调日志;
}
算法2.各个复制结点Y对数据对象D的更新
UpdateParticipator(D)
{//各个复制结点Y对数据对象D的更新
if(数据对象D的最后一次事务是失败的)
退出函数,或者先触发数据协调过程再调用此函数;
写Begin-Trans到操作日志;
while(还有本事务写操作)
{
以原子方式提交更新事务并写Commit Trans到操作日志;
向发起结点X发送确认消息;
}
else
{
对此事务执行本地回滚,清除此事务的操作日志;
标志此结点其数据对象D的最后一次事务是失败的;
}
}
2、更新算法分析
算法1和算法2保证了网络和结点失效时数据更新的原子性。由于网络连接失效对于更新发起点来说等价于一个或者多个结点失效,因此,我们只分析结点失效的情况。对于更新发起结点,在失效情况下事务无论如何都会顺利完成。下面着重只分析参与者结点失效的情况。(1)如果参与者在提交前失效,则在失效恢复时,该事务的操作被撤销,同时更新发起点在等待确认消息时超时,然后假定该参与者失效并在协调日志中记录;(2)如果参与者提交后失效,则在失效恢复时,虽然更新发起点假定该参与者失效并在协调日志中记录,但在本地的操作日志中已经提交了事务,所以该事务的操作不会被重新执行。总之在各种失效下,参与者都不会被阻塞,也不必执行远程恢复,而是由更新发起点记录未正常确认的结点信息通过以后的协调操作来达到数据一致。
二、多复制服务器的负载协调
我们先分析结点数据不一致的几种失效类型。由算法1与2易知,如果一个结点对数据对象D的事务失败,就不能再继续执行以后关于此数据对象的任何事务,除非是通过协调过程消除这种标志。这种情况是一个结点数据良好,另一结点完全失效,我们叫事务失效。考虑当系统中两个数据一致的服务器在某一时刻起,相互不能通信,但他们都还有与之保持连接的客户群,各客户群根据实际的情况分别对自己可以操作的服务器执行了数据更新,并且在两服务器上产生了数据不一致。这种情况在通过路由器连接的两个子网中比较常见,如果路由器失效而子网运行良好就会产生上面情况,它有别于事务失效,我们把这种失效形式叫孤立失效。
针对以上两种不同的失效形式,必须提供不同的协调方法来达到各结点数据副本的一致性。如果系统中存在孤立失效形式的结点,那么系统中就没有数据一致性的结点,这是因为数据一致性结点反映的是所有在线客户操作的情况,而孤立失效结点的存在孤立起一部分客户。如果系统中只有事务失效形式的结点,那系统中要么存在数据一致性结点,要么全是事务失效形式的结点。考虑一般性,假设系统中既有孤立失效结点,又有事务失效结点,易知这两种类型的结点是不相交的,因为结点一旦事务失败,在协调之前是不会执行任何事务的。事务失效结点要达到数据一致性,必须参考数据一致性结点,如果系统中有孤立失效结点,则应该从这些结点中选择最接近一致性的孤立失效结点作为一致性结点,使各孤立失效结点与所选结点达成一致性,然后再协调事务失效结点;如果系统中只有事务失效结点(也没有一致性结点),此时应仿照孤立失效结点的做法选其中一个最接近一致性的事务失效结点作为数据一致性结点,使其它事务失效结点达到一致。总结以上情况,得出协调的一般思想:首先使孤立结点达到数据一致性,然后使事务失效结点达到数据一致性。
1、协调算法
设结点X中有协调记录(D,Y),是协调的发起点。
算法3.协调发起点X的协调算法
HarmonizeCoordinator()
{//协调发起点X的协调算法
按先从孤立失效结点、数据一致性结点再到事务失效结点的顺序选择协调发起点X;
协调结点和参与结点都需调用协调函数来达到数据副本的一致性,孤立失效协调函数要求发起点是最接近一致性的结点,因为其它孤立失效结点是以此为复制目标的。
2、算法分析
协调算法主要有针对孤立失效协调和事务失效协调两种算法。这两种协调算法有相同的算法框架,即在协调发起点的选择、协调日志分析、协调信息的发送和协调日志的删除上是相同的。根据上面讨论的协调的一般思想,协调发起点的选择原则是:先选择最接近数据一致性的孤立结点作为更新发起点(如果存在孤立结点);其次选择最接近数据一致性的事务失效结点作为更新发起点(如果没有数据一致性结点,否则当然是选数据一致性结点)。
对于孤立失效协调算法,根据协调发起点的选择原则选择协调发起点X,从X结点的协调日志中读取(D,Y),向协调参与结点Y发送关于数据对象D的一致性数组,然后等待结点Y返回本身的一致性数组,结点根据接收到的一致性数组得到它们最近公共执行的操作邮戳T,对于发起点,仅从自己的操作日志中取出大于T的本地操作,向协调参与结点发送;对于协调参与结点,则等待发起点的操作差,协调参与点取消本地所有大于T的操作,然后按顺序执行从发起点发送过来的操作差,最后更新操作日志和一致性数组。对于事务失效协调算法,根据协调发起点的选择原则选择协调发起点X,从X结点的协调日志中读取(D,Y),向协调参与结点Y发送关于数据对象D的一致性数组,然后等待结点Y返回本身的一致性数组,结点根据接收到的一致性数组得到在本地结点执行而在对方结点没有执行的操作集发送给对方,并等待对方的操作集DiffD,从DiffD中得到最小的邮戳Tmin,根据Tmin从本地操作日志中得到大于Tmin的需要取消的操作集合UD,接着按时间撤消UD中的操作,再合并UD与DiffD并对它们进行顺序执行,最后更新操作日志和一致性数组。
三、结束语
当考虑多复制服务器系统时,由于各服务器完成相同的功能,这里我们假设各服务器具有完全相同的数据(绝大部分情况如此),则在系统中数据的分配可以不用考虑,只需要考虑负载的平衡,由前面简单的分析,随机选择服务器就可以达到比较好的负载平衡,这是因为根据概率论,服务器被选择的概率和服务器的负载成反比。最优的负载分配算法是选择最低负载的服务器,在多复制服务器系统中,只要根据各服务器的平均响应时间选择服务器,平均响应时间短的服务器吞吐量大,应先考虑执行请求。服务器分配请求的算法是先分配空闲的服务器同时兼顾平均响应时间的原则。
参 考 文 献
1.Ji Hua,Xie Li.A Distributed Computing Model Based on Multiserver.ACM Opera-ting Systems Review,1996,30(4):3-11
2.徐庆生.分布式应用系统设计方法.楚雄师专学报.2001,(03):12-15
3.梁筱丽,杨建中.构建Intranet的多层分布式应用.计算机系统应用,2000,(02):18-21■
[关键词] 服务器 网络传输 负载均衡
采用多复制服务器系统是提高系统可用性最有希望的手段,但是,复制数据更新过程的阻塞问题是整个系统性能的一个瓶颈。复制数据更新的首要困难是控制多副本的一致性,通常采用的方法包括投票(Voting)和令牌(Token)传递方法,但是,这些方法的复杂性给实现带来困难,更新传播的另一个问题是保证事务的原子性,两阶段提交协议(2PC)是使用最多的保证事务原子性的提交协议,但是它由事务协调程序(Coordinator)决定各个参与者是否可以提交,这样就降低了系统的可用性,并增加了事务提交的延迟时间。网络环境的不健壮性使得所有参与结点同时提交的可能性减少,不可避免地造成能够正常提交的结点等待因失效不能提交的结点,而形成事务提交的阻塞。
一、多复制服务器的数据更新
我们假定在网络上有多个等同的复制服务器结点(简称结点),它们或者处于连接状态,或者处于非连接状态。但是在连接状态下通信是可靠的,网络各个结点之间能够保持消息的顺序,保证消息的内容正确到达,并且提供超时检测。系统出现故障的情况有两种,或者是各个结点之间处于非连接状态而不能通信,或者某个结点可能会因失效而不能正常工作,在每个结点有一个本地的逻辑时钟,在整个系统内对各个结点操作的定序可以利用Lamport邮戳机制解决。操作对象可以唯一标识,并且数据操作是一元的,它只影响到本地数据,每个事务中的数据操作不会跨越多个数据对象,在每个结点都有一个操作日志,其格式是(事务标识,邮戳,事务协调服务器编号,数据对象标识,操作标识,操作参数),其中邮戳是指记录在日志里某事务中操作的时间。在每一个结点建立一个用于数据协调目的的协调日志,其格式是(数据对象标识,结点标识),以便在数据协调时参考。
1、更新算法
算法1.更新发起点X对数据对象D开始更新
UpdateCoordinator(D)
{//更新发起点X对数据对象D开始更新
if(数据对象D的最后一次事务是失败的)
退出函数,或者先触发数据协调过程再调用此函数;
写Begin-Trans到操作日志;
发送Begin-Trans到各个复制结点,并且把此事务的超时时间发送给各结点;
while(事务写操作进行中)
{
执行写操作Wi(D)并记录操作完成时间Ti;
记录写操作Wi(D)到操作日志;
等待各个结点的确认;
if(等待超时)
对于所有未收到确认消息的结点Y,插入(D,Y)到协调日志;
}
算法2.各个复制结点Y对数据对象D的更新
UpdateParticipator(D)
{//各个复制结点Y对数据对象D的更新
if(数据对象D的最后一次事务是失败的)
退出函数,或者先触发数据协调过程再调用此函数;
写Begin-Trans到操作日志;
while(还有本事务写操作)
{
以原子方式提交更新事务并写Commit Trans到操作日志;
向发起结点X发送确认消息;
}
else
{
对此事务执行本地回滚,清除此事务的操作日志;
标志此结点其数据对象D的最后一次事务是失败的;
}
}
2、更新算法分析
算法1和算法2保证了网络和结点失效时数据更新的原子性。由于网络连接失效对于更新发起点来说等价于一个或者多个结点失效,因此,我们只分析结点失效的情况。对于更新发起结点,在失效情况下事务无论如何都会顺利完成。下面着重只分析参与者结点失效的情况。(1)如果参与者在提交前失效,则在失效恢复时,该事务的操作被撤销,同时更新发起点在等待确认消息时超时,然后假定该参与者失效并在协调日志中记录;(2)如果参与者提交后失效,则在失效恢复时,虽然更新发起点假定该参与者失效并在协调日志中记录,但在本地的操作日志中已经提交了事务,所以该事务的操作不会被重新执行。总之在各种失效下,参与者都不会被阻塞,也不必执行远程恢复,而是由更新发起点记录未正常确认的结点信息通过以后的协调操作来达到数据一致。
二、多复制服务器的负载协调
我们先分析结点数据不一致的几种失效类型。由算法1与2易知,如果一个结点对数据对象D的事务失败,就不能再继续执行以后关于此数据对象的任何事务,除非是通过协调过程消除这种标志。这种情况是一个结点数据良好,另一结点完全失效,我们叫事务失效。考虑当系统中两个数据一致的服务器在某一时刻起,相互不能通信,但他们都还有与之保持连接的客户群,各客户群根据实际的情况分别对自己可以操作的服务器执行了数据更新,并且在两服务器上产生了数据不一致。这种情况在通过路由器连接的两个子网中比较常见,如果路由器失效而子网运行良好就会产生上面情况,它有别于事务失效,我们把这种失效形式叫孤立失效。
针对以上两种不同的失效形式,必须提供不同的协调方法来达到各结点数据副本的一致性。如果系统中存在孤立失效形式的结点,那么系统中就没有数据一致性的结点,这是因为数据一致性结点反映的是所有在线客户操作的情况,而孤立失效结点的存在孤立起一部分客户。如果系统中只有事务失效形式的结点,那系统中要么存在数据一致性结点,要么全是事务失效形式的结点。考虑一般性,假设系统中既有孤立失效结点,又有事务失效结点,易知这两种类型的结点是不相交的,因为结点一旦事务失败,在协调之前是不会执行任何事务的。事务失效结点要达到数据一致性,必须参考数据一致性结点,如果系统中有孤立失效结点,则应该从这些结点中选择最接近一致性的孤立失效结点作为一致性结点,使各孤立失效结点与所选结点达成一致性,然后再协调事务失效结点;如果系统中只有事务失效结点(也没有一致性结点),此时应仿照孤立失效结点的做法选其中一个最接近一致性的事务失效结点作为数据一致性结点,使其它事务失效结点达到一致。总结以上情况,得出协调的一般思想:首先使孤立结点达到数据一致性,然后使事务失效结点达到数据一致性。
1、协调算法
设结点X中有协调记录(D,Y),是协调的发起点。
算法3.协调发起点X的协调算法
HarmonizeCoordinator()
{//协调发起点X的协调算法
按先从孤立失效结点、数据一致性结点再到事务失效结点的顺序选择协调发起点X;
协调结点和参与结点都需调用协调函数来达到数据副本的一致性,孤立失效协调函数要求发起点是最接近一致性的结点,因为其它孤立失效结点是以此为复制目标的。
2、算法分析
协调算法主要有针对孤立失效协调和事务失效协调两种算法。这两种协调算法有相同的算法框架,即在协调发起点的选择、协调日志分析、协调信息的发送和协调日志的删除上是相同的。根据上面讨论的协调的一般思想,协调发起点的选择原则是:先选择最接近数据一致性的孤立结点作为更新发起点(如果存在孤立结点);其次选择最接近数据一致性的事务失效结点作为更新发起点(如果没有数据一致性结点,否则当然是选数据一致性结点)。
对于孤立失效协调算法,根据协调发起点的选择原则选择协调发起点X,从X结点的协调日志中读取(D,Y),向协调参与结点Y发送关于数据对象D的一致性数组,然后等待结点Y返回本身的一致性数组,结点根据接收到的一致性数组得到它们最近公共执行的操作邮戳T,对于发起点,仅从自己的操作日志中取出大于T的本地操作,向协调参与结点发送;对于协调参与结点,则等待发起点的操作差,协调参与点取消本地所有大于T的操作,然后按顺序执行从发起点发送过来的操作差,最后更新操作日志和一致性数组。对于事务失效协调算法,根据协调发起点的选择原则选择协调发起点X,从X结点的协调日志中读取(D,Y),向协调参与结点Y发送关于数据对象D的一致性数组,然后等待结点Y返回本身的一致性数组,结点根据接收到的一致性数组得到在本地结点执行而在对方结点没有执行的操作集发送给对方,并等待对方的操作集DiffD,从DiffD中得到最小的邮戳Tmin,根据Tmin从本地操作日志中得到大于Tmin的需要取消的操作集合UD,接着按时间撤消UD中的操作,再合并UD与DiffD并对它们进行顺序执行,最后更新操作日志和一致性数组。
三、结束语
当考虑多复制服务器系统时,由于各服务器完成相同的功能,这里我们假设各服务器具有完全相同的数据(绝大部分情况如此),则在系统中数据的分配可以不用考虑,只需要考虑负载的平衡,由前面简单的分析,随机选择服务器就可以达到比较好的负载平衡,这是因为根据概率论,服务器被选择的概率和服务器的负载成反比。最优的负载分配算法是选择最低负载的服务器,在多复制服务器系统中,只要根据各服务器的平均响应时间选择服务器,平均响应时间短的服务器吞吐量大,应先考虑执行请求。服务器分配请求的算法是先分配空闲的服务器同时兼顾平均响应时间的原则。
参 考 文 献
1.Ji Hua,Xie Li.A Distributed Computing Model Based on Multiserver.ACM Opera-ting Systems Review,1996,30(4):3-11
2.徐庆生.分布式应用系统设计方法.楚雄师专学报.2001,(03):12-15
3.梁筱丽,杨建中.构建Intranet的多层分布式应用.计算机系统应用,2000,(02):18-21■