（计算机应用技术专业论文）基于划分的分布式环境：设计模式与动态划分.pdf

浙江大学硕士学位论文摘要 摘要 基于划分的分布式模型是一种利用了数据局部性以增强系统性能和可靠性 的分布式架构。利用这种架构开发出来的系统已经在实践中证明了它所具有的对 于一般分布式架构的优势。在本文之前，关于这个架构下的工作主要集中在如何 将一个单机系统通过逆向工程的方法设计成为基于划分的分布式系统，以及在这 样的模型下，如何通过在网络结点之前移动作为独立运算服务的划分，从而充分 利用资源以提高整体的性能表现n 卫1 的方法。这篇硕士论文则关注与回答下面两个 问题：1 ) 如何能够更好的运用前人已有的研究结果最大效率的开展这种模型的 软件系统的设计和实践活动；2 ) 在这样的模型之下还存在着什么样的问题。对 于第一个问题，这篇文章运用了设计模式的方法，总结出了6 个设计基于划分的 分布式系统的模式，并配以案例分析以分享设计经验。由于这个总结的过程暴露 出了这个模型下存在的问题，即缺乏自动化，过分依赖于设计者和管理员的经验。 于是，在重新审视这个架构之后，这篇论文以队列模型来分析这个架构，从而提 出了自动化的方法。这篇论文发现，引入运行时的动态划分可以提供解决问题的 途径；在旧有的全局负载均衡的基础上，设计了在全局和局部两个层次上的负载 均衡，又加入了在局部的对于资源利用的监视和反馈机制。模拟实验证明这个方 法达到了非常好的效果。此外，这篇硕士论文还回顾了这种的分布式模型出现的 背景，详细的阐述了并行体系架构、并行数据库和负载均衡方面的研究历史和进 展。 关键词：分布式系统，划分，动态划分，负载均衡，设计模式 浙江大学硕士学位论文 a b s t r a c t a b s t r a c t p a r t i t i o n 。b a s e dd i s t r i b u t e dm o d e li sad i s t r i b u t e ds y s t e mm o d e lw h i c h l e v e r a g e sd a t al o c a l i t yt oi m p r o v et h ep e r f o r m a n c e t h er e a la p p l i c a t i o n d e v e l o p e db ye m p l o yt h i sm o d e la p p e a r st oh a v ea d v a n t a g e so v e rt h eg e n e r a l d i s t r i b u t e ds y s t e mm o d e l s t h i sm a s t e rt h e s i sp r o v i d e sar e t r o s p e c to n t h eb a c k g r o u n do ft h ee m e r g e n c eo ft h i sm o d e l ，i e t h ee v o l v e m e n to ft h e s y s t e ma r c h i t e c t u r e ，p a r a l l e ld a t a b a s ea n dt h el o a db a l a n c i n gt e c h n i q u e ， a n dt h e nd e s c r i b e st h em o d e li nd e t a i1 b e c a u s et h e r ea r es o m ec o m m o n p r o b l e m se n c o u n t e r e di nt h ep h a s eo fd e s i g n i n ga na p p l i c a t i o nu s i n gt h i s m o d e l ，t h i sp a p e rc o n c l u d e st h e s ep r o b l e m si n t od e s i g np a t t e r n s f i n a l l y ， ad y n a m i c p a r t i t i o n i n gm e t h o da i m i n ga ti m p r o v i n gt h ep e r f o r m a n c ei s p r o p o s e dt os o l v et h en o n a u t o m a t i cp r o b l e m si nt h ed e s i g np a t t e r n s k e y w o r d s ：d i s t r i b u t e ds y s t e m ，p a r t i t i o n ，d y n a m i cp a r t i t i o n i n g ，l o a db a l a n c e ，d e s i g n p a t t e r n s 浙江大学硕士学位论文图目录 图目录 图2 1 共享内存的多处理结构4 图2 2 共享硬盘的多处理器结构5 图2 3 不共享的结构5 图2 4 现代的i n t e m e t 服务架构9 图3 1 非对称的和对称的分布式架构1 5 图3 2 基于划分的分布式模型架构1 6 图3 3d 。对服务器结点间d a 值标准差和服务中断时间的影响2 1 图3 4s r t 对服务器结点间d a 值标准差和服务中断时间的影响2 1 图4 1 划分粒度。2 4 图4 2 线程池以及队列和后端队列的架构2 9 图4 3 划分恢复的过程3 3 图4 4g 系统架构3 7 图4 5 基于历史纪录的针对6 、5 、4 、3 个计算结点，2 0 个划分的分配比较 ：；9 图4 6e n do fd a y 操作的消息传送和执行过程4 1 图5 1 粒度过大的示例4 4 图5 2 粒度过小的示例。4 5 图5 3 基于划分的分布式环境的架构4 7 图5 4 资源一队列模型4 9 图5 5 队列模型5 0 图5 6 队列变化的示例51 图5 7 不同方法下运行时划分和资源热度的标准差变化。5 9 i i i 浙江大学硕士学位论文表目录 表目录 表3 1 三种并行模型的订单进入和匹配速度实验。1 7 表6 1 模拟系统假设参数5 6 表6 24 0 0 个周期的请求序列不同结点数的服务时间对比5 6 表6 38 0 0 个周期的请求序列使用不同方法的服务时间对比5 7 i v 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得逝鎏盘堂或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文作者签名： 饮多叉 签字日期：渺年6 月占日 学位论文版权使用授权书 本学位论文作者完全了解 逝姿盘堂一有权保留并向国家有关部门或机 构送交本论文的复印件和磁盘，允许论文被查阅和借阅。本人授权逝江苤堂 可以将学位论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 签字同期：2 矿，扩年月( ) 同签字n 期：2 口心年6 月6 同 浙江大学硕士学位论文第1 章绪论 第1 章绪论 1 1 引言 在上个世纪的后三十年中，为了一些企业应用开发了很多大型系统。这些系 统大多部署在一台主机( m a i n f r a m e ) 上。然而随着系统复杂性的提高和用户需 求的增加，这样的系统对于扩展性的要求也逐渐提高。在单一的主机上要想获得 性能太高只有采取垂直升级的办法，例如使用更高级的c p u ，加入更多的内存， 替换更大的磁盘存储系统和增加网络接入的带宽。 在 1 ，2 中，作者提出了被称为基于划分的分布式系统的架构，并证明了它 是行之有效的针对大型数据集中系统的解决方法。它主要的特点有二：一，是利 用了数据划分方法得到数据的局部性，从而将负载分散到网络中的多个结点上； 二，利用划分移动的方法，实现负载均衡。作者还阐释了这种系统架构的作为高 可靠性架构的可行性。 针对这种系统架构和使用它设计并实现应用程序，我们开展了调查和总结。 在这个过程中我们发现，使用这种架构开发程序对于设计人员的经验要求比较 高。比如，如果开发程序的需求来自于针对旧的单一主机系统的在过程 ( r e e n g i n e e r i n g ) 项目，往往需要在旧的应用程序中有大量实践经验的开发人 员才能完成。然而这样的人力资源是非常宝贵的。所以我们力图将利用基于划分 的分布式架构来设计开发应用的过程中会碰到的问题总结出来，以作为将来的开 发人员的参考或者规范。为此，我们一方面在过去的文献资料中寻找别人的研究 成果和开发经验，另一方面从实际案例的分析中总结实践经验。同时我们发现， 对于软件开发人员，设计模式是一种很好的总结经验的形式。于是我们将我们所 发现的总结为划分设计、划分分配、不可划分组件的分配、任务队列和线程池、 划分间的同步和划分恢复这六个模式，每一个模式都从问题提出开始，进而分析 因素，最后给出解决方案和需要注意的细节。最后还以案例分析的形式，将这些 浙江大学硕士学位论文第l 章绪论 模式用一个实际案例展现出来。 然而我们还是发现这些设计模式中的人工干预程度过高，而自动化程度缺 乏。这种缺乏，集中体现在划分设计和划分分配模式中，并且在负载均衡算法中 得到体现( 在第五章中，我将给出2 个例子说明) 。所以我们重新审视了基于划 分架构的模型，并且提出了利用动态划分来解决这些问题的方法。我们主要的思 路是，系统性能的提高来自两点：尽量的分散负载，以及在每一个结点上尽量的 提高对于资源的利用率。这首先需要一个能够同时衡量全局和局部的模型，此时 我们总结的模式中的一个即队列模型给了我们启发。于是我用队列来衡量划分、 资源等局部和全局的系统组成单元。然后，我给出了在全局和局部实现二个层次 的负载均衡的方法：全局的层次上，利用划分移动实现全局的负载均衡，这是重 量级的操作；在一个计算结点上是利用动态划分，即划分的增加、合并实现局部 的负载均衡，这是轻量级的操作。并且我还加入了在局部进行的不断通过监视前 后端队列从而调节划分的并行率以提高对于局部资源的利用率的方法。通过将三 者结合在一起，我们用一个模拟实验证明这个方法的结果，即在一个通过三者结 合方法的调节资源利用的集群和一个单使用全局负载均衡的集群，前者的性能大 大好于后者，从而证明了我们的观点，并且解决了自动化的问题，即可以随意的 设定初始划分的粒度和分配，系统会根据运行时的状况自动适应到最佳的配置方 案上去。 这篇文章的贡献在于： 一，总结了设计一个基于划分的分布式系统的设计步骤、关键问题和通用解 决方法； 二，进一步提出了自动化的系统解决方法，减少了人工干预因素，降低了系 统设计的难度。 1 1 1 文章组成 在第二章中将回顾基于划分的分布式架构出现的背景，主要就并行数据库和 负载均衡技术的发展做一个小结。第三章介绍什么是基于划分的分布式架构，并 2 浙江大学硕士学位论文第l 章绪论 介绍 i ，2 中提出的一个负载均衡算法。在第四章中，6 种设计基于划分的分布式 应用的模式会被提出来。第五章提出针对性能提升的动态划分的新方法。 浙江大学硕士学位论文第2 章背景和相关工作 第2 章背景和相关工作 2 1 数据划分方法 数据划分方法是高性能并行数据库体系架构下针对数据放置( d a t a p l a c e m e n t ) 问题的一种解决方法。下面将首先介绍并行数据库的发展，然后描 述数据划分方法的研究状况。 2 1 1 并行数据库 数据库管理( d b m s ) 技术的在过去3 0 年中不断成熟；同时，分布式计算和 并行计算技术也在不断发展。这两者的融合，使得分布式和并行体系架构上的并 行数据库成为高性能计算领域主流的数据管理工具。 并行计算技术在自身的发展中涌现出多种并行体系架构，包括：共享内存的 多处理器结构( s h a r e d m e m o r y ) 、共享硬盘的多处理器结构( s h a r e d - d i s k ) 、不 共享结构( s h a r e d n o t h i n g ) 3 ( 如下图2 1 - 2 3 所示) 。 图2 1 共享内存的多处理结构 4 浙江大学硕士学位论文 第2 章背景和相关工作 图2 2 共享硬盘的多处理器结构 图2 3 不共享的结构 共享内存的多处理器结构通过高速互联网络把所有处理器连接到全局共享 内存上，i b m 3 7 0 和v a x 是这种结构的代表。共享硬盘的多处理器结构给每个处 理器都配有独立的私有内存，通过高速互联网络，处理器可以直接访问共享的硬 盘存储，i b ms y s p l e x 和v a x c l u s t e r 是这种结构的代表。前面两张结构的共同问 题是扩展性( s c a l a b i l i t y ) ，当需要建造更多处理器的并行计算机时，用来传递 数据的高速网络成为了瓶颈。不共享的结构给每个处理器配备独立的私有内存和 一个或多个硬盘，处理器之间通过高速互联网络联系。各个处理器之间通过消息 传递解决进行协作，这种结构可以扩展到数干和上万个处理器。这种结构和用高 s 浙江大学硕士学位论文第2 章背景和相关工作 速网络连接的计算机集群，已经差别很小了。 并行数据库是数据库技术和并行计算体系结合的产物。它利用这种体系结构 中多处理器的特点，建造出在单一主机上难以实现的高性能和高可用性的数据库 服务器。这种用软件技术的方案，和1 9 7 0 年戴的数据库机( d a t a b a s em a c h i n e ) 的想法是一致的，都是用并行的方法来解决i o 瓶颈的问题；然而，数据库机的 硬件解决方案由于较低的性价比而失败了。并行数据库在设计时考虑了三种形式 的并行：查询间的并行( i n t e r - q u e r yp a r a l l e l i s m ) 允许同步发生的事务，从 而使得多个查询并行执行；查询内的并行( i n t r a q u e r yp a r a l l e l i s m ) 允许一 个查询之内多个操作并行执行；操作内的并行( i n t r a o p e r a t i o np a r a l l e l i s m ) 允许一个操作之内多个子操作并行执行。而前两种并行都可以通过数据划分 ( d a t ap a r t i t i o n i n g ) 的办法来实现。 并行数据库的研究包括下面几个方面的问题： 体系结构虽然大多数并行数据库研究都假设一个典型的体系结构，比如共 享内存的多处理器结构或者不共享的结构；但是混合( h y b r i d ) 的体系结构常常 要展现出更好的结果，例如自行设计的磁盘存储系统或者网络。 数据放置数据放置是并行数据库设计的重要问题。理想的数据放置是同步 并行操作中的相互干扰通过数据放置完全避免，即每个操作都单独的执行在独立 的数据集上。而独立操作的数据集是可以通过数据横向划分( h o r i z o n t a l p a r t i t i o n i n g ，也被称作d e c l u s t e r i n g ) 的方法来实现。数据划分还能有助于实 现查询间的并行，因为多个查询可以同时执行在不同的划分( p a r t i t i o n ) 之上。 除了划分，数据还可以被复制，即同一份数据被放置在多个划分中间。这样做的 好处，一是数据的可靠性( a v a i l a b 订i t y ) 得到提高，二是针对只读查询( 常常 在决策支持系统和电子商务系统的查询操作中占据大部分) 可以大量的同步执 行；但是坏处是数据更新的一致性成为一个问题。 并行查询处理这是指自动的将一个用中央执行模型的形式描述的查询操 作，转换成可并行的执行计划( e x e c u t i o np l a n ) 。这就要求这个执行计划，既 是正确的，即产生和中央执行模型同样的执行结果，又是优化的，即最大程度的 6 浙江大学硕士学位论文第2 章背景和相关工作 利用计算资源，挺高性能。数据划分是并行查询处理的基础。 2 1 2 数据划分 并行数据库中的数据放置问题是一个重要的问题。数据放置的方法直接影响 整体的数据库的性能，一个不好的数据放置会造成运行时的访问量不均衡，从而 使得整个数据库的性能受制于瓶颈，使得事务处理的开销增大。一个静态的数据 放置策略可以分成三个阶段：划分( p a r t i t i o n i n g ) ，放置( p l a c e m e n t ) ，和重 新分布( r e d i s t r i b u t i o n ) 。这三个阶段并非是完全相互独立的，比如对于放置 的策略常常限制了划分和重新分布的策略的选择。 数据划分，是指将整个数据集分成多个子数据集，这些子集之间可以是相交 的，也可以是不想交的。对于关系数据库( r e l a t i o n a ld a t a b a s e ) 而言，数据 划分可以是横向的( h o r i z o n t a l ，也被称作d e c l u s t e r i n g ) 也可以是纵向的 ( v e r t i c a l ) 。横向划分是指将一个关系的数据，以元组( t u p l e ) 为基本单位分 成多个子集。这是比较直观的方法，也是比较流行的数据划分方法。纵向的划分 是将一个关系的数据映射到一些属性( a t t r i b u t e ) 子集上，每个划分都是都跟 原来的关系具有同样的元组个数，但是只有相对较少的属性。如果数据在各属性 上的访问有区别的话，使用纵向划分的方法，可以有选择的将一些划分放到内存 层次等级( m e m o r yh i e r a r c h y ) 的较高层次上，也可以放到具有较强计算能力的 处理器结点上。 横向划分的基本方法有循环( r o u n d r o b i n ) ，区间( r a g e ) 和哈希( h a s h ) 。 横向划分需要面对的一个问题是运行一段时间以后的负载不均衡( 1 0 a d i m b a l a n c e ) 。负载不均衡可能是由于数据增减而造成的数据不对称( d a t as k e w ) ， 也有可能是访问频率不同造成的访问不均衡。当负载不均衡出现以后，就需要重 现分布数据，进行数据迁移( d a t am i g r a t i o n ) 。但是移动大量数据是有成本的， 可能需要暂停数据库服务，即使在后台运行也有可能因为竞争计算资源使得系统 性能下降；有时候数据迁移带来的好处还及不上它本身的开销。所以数据重新分 布的算法应该是谨慎的，即不可以常常执行，但却能有效( 这是一对矛盾) ，并 7 浙江大学硕士学位论文第2 章背景和相关工作 且每次都要移动最少的数据。数据重新分布和负载均衡方法( 将在下一节中展开) 常常是相联系的。 数据放置的方法主要包括根据数据量的分配策略、根据访问频率的分配策略 和根据网络传输的分配策略。关于数据放置的范围，可以通过完全划分( f u l l d e c l u s t e r i n g ) ，放置到所有处理器之上。但是这样对一些数据量小的关系或表 是不适用的，对于有很多处理器的系统也是不适用的。所以也有不定划分 ( v a r i a b l ed e c l u s t e r i n g ) 的方法，根据数据量和查询频率的情况，决定将哪 些关系的数据放置到哪些结点之上。 2 2 负载均衡 负载均衡是在一个网络中把计算任务分配给多个计算机、网络连接、处理器 或者其他资源，已获得优化的资源利用( r e s o u r c eu t i l i z a t i o n ) 、吞吐 ( t h r o u g h p u t ) 或者响应时间( r e s p o n s et i m e ) 的技术。 2 2 1 网络服务中的负载均衡技术 负载均衡的一个最重要的应用是来源于提供i n t e r n e t 服务的多台服务器主 机。在这样的一个网络中，负载均衡器( 1 0 a db a l a n c e r ) 将请求发送到多台服 务器中的一台或几台上，有它们继续提供服务，从而实现由于用户增加和访问量 增大带来的对于系统负荷的扩展性( s c a l a b i l i t y ) 要求。 一个现代的i n t e r n e t 服务架构如下图2 4 所示。 浙江大学硕士学位论文第2 章背景和相关工作 l , w m l yd 轴一b 埘dw 曲野硝哪 ，。一一，蔓譬皤蝗蔓轧 a u t t r l 妇l “to | ! i ；r 垤r f o rw w w 鞠t m r 薯 图2 4 现代的i n t e r a c t 服务架构 在现代的i n t e r n e t 服务器中，使用负载均衡技术已经很普遍： d n s 循环最简单的负载均衡的办法是把固定的客户( c l i e n t ) 分配到固定的 服务器上面去。如果在d n s 服务器中对一个域名( h o s t n a m e ) 配有多个记录，循 环( d n sr o u n d r o b i n ) 地将这些记录中的i p 地址指向的服务器分配给新的用户， 就可以实现分散请求的目标。这种在d n s 服务器中实现负载均衡的方法适用于对 于服务的环境依赖性不强的网络服务应用，例如搜索引擎服务，来自客户的请求 不依赖于发送到某个特定的机器上去执行，这在解析域名是就可以实现。d n s r o u n d r o b i n 是一种粗粒度的负载均衡方法。更细粒度的方法不是给每个服务器 都分配独立的i p 地址而是在本地的分布式网络系统的入口处有一个网络交换机 ( w e bs w i t c h ) ，它具有对外的唯一的i p 地址；内部的工作机制对于客户是透明 的。 第4 层负载均衡工作在o s i 模型第4 层上的网络交换机在客户请求建立t c p 连接的时候决定目标服务器，执行内容不可知的路由( c o n t e n t b l i n dr o u t i n g ) 。 由于工作在第4 层上，来自客户的数据包没有到达应用层，从而使得这种方法的 效率很高，但是分发策略就无法考虑客户请求的内容。 浙江大学硕士学位论文第2 章背景和相关工作 第7 层负载均衡网络交换机和客户建立完整的t c p 连接之后，检查h t t p 请 求的内容，由此决定目标服务器。这种方法相对于前一种，被称作内容可知的路 由( c o n t e n t - a w a r er o u t i n g ) 。它相比较内容不可知的路由，效率是比较低下的， 但是可以支持更加高级的分发策略的实现。由于这些高级的分发策略，我们可以 实现更高的磁盘c a c h e 的命中率，对于数据内容的划分，使用特别的服务器结点， 将安全连接会话( s s ls e s s i o n ) 中的后续请求发送到同一台服务器结点。但是 另一方面，由于支持这些高级的分发策略，带来了大量的开销，使得的同时可以 响应服务请求的连接数大为减少。 分发策略也是一个重要的问题。因为分发策略不仅影响到客户请求响应的效 率，也影响到多台服务器网络的扩展性问题。通常来说，分发策略是实现在网络 交换机中，有时由于分发策略本身的需要，这台网络交换机本身用一台或者多台 服务器实现。这个实现分发策略的部件被称为调度器( s c h e d u l e r ) 或者分发器 ( d i s p a t c h e r ) 。如前所述，工作在第4 层和第7 层上的差别，将分发策略分成 内容不可知的分发策略和内容可知的分发策略。 内容不可知的分发策略( c o n t e n t b li n dd is p a t c h i n gp o li c i e s ) 这个类 别又可以分为如下几个子类别： 客户状态可知的策略( c l i e n ts t a t ea w a r ep o l i c y ) 因为第4 层的限 制，分发器只能知道客户的i p 地址和端口，但是这样也可以将来自同一 个i p 地址的请求发送到同一台服务器上去。 服务器状态可知的策略( s e r v e rs t a t ea w a r ep o l i c y ) 当决定目标服 务器时，如果分发器获取了服务器的负载信息，那么久可以做出更好的 决定。网络系统中可能成为瓶颈的资源很多，如何选择一个好的负载信 息指数( 1 0 a di n d e x ) 是需要考虑的问题。一旦选定了这个指数之后， 就可以采用不同的实际的分发策略。最小负载( 1 e a s tl o a d ) 是一类分 发策略，例如最小连接( 1 e a s tc o n n e c t i o n s ) 和最小响应时间( 1 e a s t r e s p o n s et i m e ) 等。动态加权循环( d y n a m i cw e i g h t e dr o u n d r o b i n ) 是一种静态加权循环的变形，它在运行时给每个服务器按照收集到的负 1 0 浙江大学硕士学位论文第2 章背景和相关工作 载状态设置权重，然后再在这个基础上循环分发请求。 客户和服务器状态可知的策略( c l i e n ta n ds e r v e rs t a t ea w a r ep o l i c y ) 这类方法是前述两种方法的结合。在将请求分发的同时考虑客户来源的 好处，是可以实现用户粘性( c l i e n ta f f i n i t y ) 。这主要是考虑到用户 请求相应中的部分内容，可能是跨请求共享的，例如动态内容中的静态 模板和s s l 密码键。这些内容会被缓存在同一台服务器的c a c h e 中，在 来自同一客户的下一次请求时再被利用。另外，f t p 协议，则规定一个 会话的请求都被包括在一对建立连接和停止连接的控制请求中，也是必 须连接到同一台服务器上面去。 内容可知的分发策略( c o n t e n t a w a r ed i s p a t c h i n gp o l i c y ) 由于第7 层 上的一些特性使得这种内容可知的分法策略可以考虑更多的因素。例如s s l 密码 键和c o o k i e 都可以用来帮助提高用户粘性。 客户状态可知的策略( c l i e n ts t a t ea w a r ep o l i c y )由于在第7 层上 得到了用于请求的u r l ，利用u r l 可以将所有的网页文件做一个划分， 分布到不同的服务器上面，当对应的请求到达时就把该请求发送到特定 的服务器上面去。这可以用一个哈希表来实现。但是这种方法只适用于 静态内容页面。虽然这种方法在存储内容上通过划分实现了负载分散， 但是如果存在极端的访问频率差异就会产生访问瓶颈从而抵消这种负载 分散的好处。另一种方法，c 1 i e n t - a w a r ep o l i c y ( c a p ) 1 针对提供多 重网络服务的分布式服务器系统，考虑到不同的网络服务消耗资源类型 不同，将来自客户的请求按照它们对于网络接口、c p u 、磁盘等资源的潜 在影响通过u r l 进行分类，在运行时通过一个循环链表记录为每一种网 络分配的服务器。c a p 的目标是在所有服务器上共享多种负载类型从而 保证没有一个服务器成为一个负载过度的瓶颈。 客户和服务器状态可知的策略( c l i e n ta n ds e r v e rs t a t ea w a r ep o l i c y ) 利用在应用层获得的辅助信息，分发器也可以将客户和服务器状态很好 的结合。利用客户状态信息是为了更好的换窜粘性( c a c h ea f f i n i t y ) ， 浙江大学硕士学位论文第2 章背景和相关工作 利用服务器状态信息是为了更好的负载分散( 1 0 a ds h a r i n g ) 。 l o c a l i t y - a w a r er e q u e s td i s t r i b u t i o n ( l a r d ) 哺3 是一种同时考虑了局 部性( 1 0 c a l i t y ) 和负载均衡的内容可知的请求分发策略。l a r d 的基本 原则是把对于同一个网页目标( w e bo b j e c t ) 的访问尽量的发送到同一 个服务器上面去，只要这要还没有引起负载不均衡超过一个预设的上限。 由于这样的原则，网页目标会很有可能从同一台的服务器上的缓存中再 被发现，而不需要从通过磁盘读写获取。直到这样的操作已经使得此台 服务器的载荷超过了预设的上限，发生这种情况是就把请求发送到较低 负载的服务器上去。l a r d 还提出了允许复制的方法，即可以使用一组服 务器来服务对于一个网页目标的请求，在这组服务器之中使用最小负载 的负载均衡。l a r d 的缺点是适用于静态内容服务。 i n t e r n e t 服务中的负载均衡技术被大量的研究，这其中涌现的方法被其他架 构或者其他应用的研究者借鉴。但是这些研究多专注于静态内容提供服务。我们 知道，在i n t e r n e t 服务中很大一类是动态内容提供服务，这些服务常常是利用 数据库作为其后端数据管理工具。在这样的架构中，仅有前端的网页服务负载均 衡还是不够的，就需要数据库中的负载均衡功能。 2 2 2 数据库中的负载均衡技术 在2 1 中提到的并行数据库本来是在并行体系结构上诞生的一种高性能数据 管理工具。但是并行体系结构的问题是价格较高，而且部署后由于用户访问量增 加而产生的扩展性需求难以得到满足。同时由于在i n t e r n e t 服务中逐渐流行起 来的计算机网络集群，以及由于在此之上关于网页内容服务的负载均衡的研究， 人们逐渐的意识到这种体系结构的重要性。在这种体系结构上开发出的分布式数 据管理工具常常是实现一个满足数据管理需要的中间件，而在各个服务器结点上 可以安装独立的操作系统、独立的或者经过改进以配合中间件工作的本地数据管 理工具。由于动态内容提供服务自己的特点，例如c p u 利用率高，每次操作内存 需求量大，以及数据一致性保持的功能性要求，在这个领域诞生出新的问题。并 1 2 浙江大学硕士学位论文第2 章背景和相关工作 且，研究者把并行数据库中的方法和集群中的网页内容服务的负载均衡作为出发 点，针对这些新特点展开了分布式数据库以及其中的负载均衡问题的研究。 如前2 1 中所述，数据放置的方法主要就是划分( p a r t i t i o n i n g ) 和复制 ( r e p l i c a t i n g ) 两种，当然两者也可以结合起来，例如将一些划分复制到多个 服务器结点上。每一个被复制的部分被称作一个复制( r e p l i c a ) 。由于在一个分 布式的环境中，所以对于动态数据的一致性( c o n s i s t e n c y ) 有特殊的要求。 卜c o p y s e r i a l i z a b i l i t y 作为一种一致性模型，是说所有互相冲突( c o n f l i c t ) 的事务( t r a n s a c t i o n s ) 在所有的复制上面执行的顺序都是一致的。 为了满足上述的这种一致性要求，数据更新过程中涉及到复制的问题。 同步复制( s y n c h r o n o u sr e p l i c a t i o n ) 所有事务的执行都按照顺序执 行。分发器等到一个查询在所有的复制上都更新之后才将查询结果返回 给查询前端。 满足一致性的异步复制( a s y n c h r o n o u sr e p l i c a t i o nw i t hc o n s i s t e n c y ) 分发器在检查了查询的类型和设计的表了之后，对于表的锁被发送到每 个复制上去。分发器给所有的事务一个单调增长的序列号，这就在所有 的事务中规定了一个全序( t o t a lo r d e r ) 。这也跟着锁和事务被发送到 复制上面去。在复制上，每个服务器自己按照这个序列顺序，执行事务。 只要一个复制的事务执行结束，将结果返回给分发器，分发器即可将结 果返回给查询前端。这种方法的一种优化是，只在一个主复制( p r i m a r y r e p l i c a ) 上真的执行事务的操作，而在其他复制上面只是将这个事务对 数据表的更新差异用写集( w r i t es e t ) 发送到其他复制上面。 冲突可知的调度( c o n f l i c t - a w a r es c h e d u l i n g ) 考虑了事务之间的读 写冲突，冲突可知的调度可以解决读写查询之间的冲突和写查询之间的 冲突。对于读与写查询之间的冲突，可以采用懒惰的一处读多处写的复 制( 1 a z yr e a d o n e ，w r i t e - a l l r e p li c a t i o n ) 方法口1 。然而针对只读 查询，会被发送到没有冲突的复制上，即使它还没有完成之前已经发出 的读写事务；因为不冲突，所以这样的复制对于该只读查询来说已经是 浙江大学硕士学位论文第2 章背景和相关工作 更新了的。这样就可以更大范围上的实现负载分散。而且考虑到在某些 系统中只读查询和读写查询的比重不同，这样的优化是有实际意义的。 另外一方面，考虑写查询之间存在的冲突，过多的冲突的查询如果在不 同的复制上执行，如果不像前述方法那样规定一个全序，就会在在各个 复制上产生不一致，在c o m m i t 的阶段，有些写查询就可能会被推出 ( a b o r t ) 。为了解决这个问题就需要把更多的相冲突的事务分发到相同 的复制上面；然后为了实现更多的并行和负载分散，就要求更多的事务 分发到不同的复制上：这是一对矛盾。m a x i m i z i n gp a r a l l e l i s mf i r s t a n dm i n i m i z i n gc o n f l i c tf i r s t ( m p fa n dm c f ) 嘲是针对这一对矛盾， 使用了一个混杂的方法在两者之间寻求一种平衡。 前述的l a r d 是一种针对静态内容特别有效的能提高缓存粘性的负载均衡方 法。但是对于动态内容提供服务和数据库后端，l a r d 存在局限性。为了提高在对 于内存的使用效率，t a s h k e n t + 阻3 中使用了内存可知的负载均衡( m e m o r y - a w a r e l o a db a l a n c i n g ，m a l b ) 方法。m a l b 方法将数据库事务按照类别进行区分，对于 每个类别估计它的内存工作集大小( w o r k i n gs e ts i z e ) 。然后在运行时根据内 存工作集的大小将服务器结点分配给不同的数据库事务类别，以保证分配到同一 个服务器结点上的工作集大小之和能够容纳到内存中。 以上是在数据管理的方面数据库中的负载均衡技术一些成果。为了支持这种 数据库，人们在系统和体系架构方面也展开了研究。例如，s p r i n t n 是利用每个 结点上的内存数据库( i n - m e m o r yd a t a b a s e ) 构建了一个高性能的数据库，并且 提供了将性能与可靠性( a v a i l a b i l i t y ) 和持久性( d u r a b i i i t y ) 区分开来的想 法。 2 3 本章小结 在本章中回顾了数据划分方法出现的背景，即并行体系结构的发展和并行数 据库的出现，以及负载均衡技术从i n t e r n e t 服务向数据库中发展的历程。 1 4 浙江大学硕士学位论文第3 章基于划分的分布式架构 第3 章基于划分的分布式架构 3 1 介绍 分布式架构的系统相对于单独主机上的系统的主要优势是性能价格比以及 更好的可扩展性。在以前要想获得好的计算性能的唯一办法是是垂直扩展 ( v e r t i c a ls c a l a b i l i t y ) ，即更换更快的c p u ，增加内存和磁盘资源，以及升级 软件等；但是很容易达到性能极限，而且主机的价格一直以来对于小型企业是无 法承受的。然后分布式架构的系统的出现，使得横向扩展( h o r i z o n t a l ) 成为可 能，在部署之后如果遇到性能问题可以通过在网络中加入计算机结点而获得持续 增长。但是分布式架构的系统对软件系统提出了同步性( c o n c u r r e n c y ) 、统一性 ( c o h e r e n c e ) 、负载分散( 1 0 a ds h a r i n g ) 、容错( f a u l tt o l e r a n c e ) 的新要求。 分布式架构的一种分类方法是按照功能单元( 组件) 在网络中所处的位置来 区分。在基于划分的分布式架构之前主要有两种类别的架构n 2 1 ：非对称式的分布 式架构和对称式的分布式架构( 如图3 1 ) 。 巍e q 愀 p 爷确l 融a p h y s i c a ln o d , b 0 够甲 t - l m i d d l e w a r e i 图3 1 非对称的和对称的分布式架构 非对称( u n s y m m e t r i c a l ) 的分布式架构在这种架构中不同的功能单元被放 置到不同的结点上。每一个请求被按照处理逻辑的顺序，经过所有的功能单元。 对称式( s y m m e t r i c a l ) 的分布式架构这是一种并行结构，同样的功能单元 浙江大学硕士学位论文第3 章基于划分的分布式架构 被放置到所有的结点上。每一个结点都独立地可以处理任何请求。在前端有一个 分发器，可以按照一定的负载均衡策略分发请求。 非对称式架构的问题是，所有的请求都要经过所有的计算结点。如果某个功 能单元的计算量非常大，就会给它所处的计算结点产生很大的压力，从而使得这 里出现系统瓶颈。对称式架构的问题主要是局部性( 1 0 c a l i t y ) 原则难以保证。 如果相关的请求被发送到不同的计算结点上，要通过通讯来实现一些相关操作就 会比较困难而且也会产生较大的性能开销。 r e q u e s td i s p a t c h e r r e q u e s t st o 哆钟獭t oh e q u e s t s b i b 2 b 3 ，b 4 t ob 5 b 6 帮 澎碜 t d a t a b a s e ：p a r t i t i o no 岂侧婴曲k 图3 2 基于划分的分布式模型架构 如上图3 2 所示，基于划分的分布式模型n 2 提供了以上两者无法提供的优 势，可以实现更好的性能表现和横向扩展性。如前第二章中所述，数据划分本来 是并行数据库和分布式数据库中的一种数据放置的方法，后来也被用到静态网页 内容存储上面去。基于划分的分布式模型是利用了在数据库中做划分的特点，在 应用层中也做出相应的划分，并且按照负载均衡的原则部署到各个计算结点上。 在图3 2 中，b 是一个数据集中( d a t ai n t e n s i v e ) 的功能单元。根据在后端数 据库中所作的数据划分，b 也作出了相应的划分，成为b 1 - b 6 ，被放置在3 台计 算机点上。每一个划分都具有完全的等同于b 的处理逻辑，但是每一个划分负责 的请求仅仅是和与之对应的数据划分相关的。位于前段的分发器将请求发送到相 1 6 浙江大学硕士学位论文第3 章基于划分的分布式架构 应的划分所在结点上面去。而对于非数据集中的功能单元，如图3 2 中的a 和c ， 可以复制到各个结点上。 基于划分的分布式架构主要有3 点好处。第一，相关的请求可以被发送同一 个划分上，这样的好处是可以更好的利用局部性。例如在一个股票交易系统中对 于同一支股票的订单当然最好能在同一个划分中处理，可以在内存寻找可以成功 的买入和卖出订单进行撮合交易逻辑处理。第二，可以在平衡整个系统中的工作 负载时，既考虑到请求的因素也考虑到系统资源的平衡。第三，划分使得可靠性 ( a v a i l a b i l i t y ) 更加容易实现。当一个结点停止工作以后，可以将原来工作在 这个结点上的划分分散到其他正常工作的结点上去。 如下表3 1 所示，在一个股票交易系统中，基于划分的分布式架构的系统超 过了非对称式的( u n s y m m e t r i c a ld i s t r i b u t e ds y s t e m ，u d s ) 和对称式架构 ( s y m m e t r i c a ld i s t r i b u t e ds y s t e m ，s d s ) 的系统。订单进入( o r d e re n t e r i n g ) 测量了来测客户端的订单请求进入到系统的速度。匹配( m a t c h i n g ) 测量了在买 入订单和卖出订单之间的撮合的速度。 表3 1 三种并行模型的