（计算机科学与技术专业论文）基于lvs算法控制的在线实时实验评判系统的设计与实现.pdf

独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究成果。尽 我所知，除了文中特i i i i i 以标注和致谢中所罗列的内容以外，论文中不包含其他人已经 发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示了谢意。 申请学位论文与瓷料若有不实之处，本人承担一切相关责任。 本人签名： 垒盔匠- ：日期：尘! ! ： ：鲨 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保留并向国家有 关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借阅；学校可以公布学 位论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编学位论 文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论文注释： 本学位论文不属 本人签名： 导师签名： 权书。 日期：型z ! ! 鲨二 醐：社 基于l v s 算法控制的在线实时 实验评判系统的设计与实现 摘要 软件实验对于计算机专业教学而言是一个重要的实践环节，不但检查 了学生对算法理论的掌握程度，而且还可以考核学生在规定时间内编写代 码的能力。但目前从实验题目的发布、实验过程监管到学生提交源代码文 档，再到对源代码文档的评判都是由人工完成。计算机软件实验教学的质 量控制、管理与实验编码质量的评价都存在着问题。 本文在分析了目前计算机软件编码实验手段的缺陷的基础上，结合网 络负载平衡技术和包捕获技术的研究，提出了一种基于l v s 算法控制的在 线实时实验评判系统的解决方案。 本文对i p 负载平衡技术，例如n a t 负载平衡、i p 隧道负载平衡、直接 路由负载平衡等一些最前沿的技术进行了重点分析比较。针对l i n u x 平台， 阐述了在操作系统内核中系统所实现的八种连接调度算法。并在系统实现 中使用加权最小连接调度算法实现调度。 本文同时介绍了常用包捕获技术，重点介绍t w i n d o w s 平台下包捕获 开发工具w i n p c a p 的结构和原理。并在系统中采用w i n p c a p 对网络包进行捕 获以实现抄袭监控。 关键词：网络负载平衡包捕获网络地址转换l v s t h ed e s i g na n dr e a l i z a t i o no fo n l i n er e a l - t i m ee x p e r i m e n t j u d g e m e n ts y s t e mc o n t r o l l e db yl v sa l g o r i t h m s a b s t r a c t s o f t w a r ee x p e r i m e n ti sai m p o r t a n ts t e pt oe d u c a t i o no fc o m p u t e rs c i e n c e i tc a nn o t o n l yc h e c ki fs t u d e n t sh a v em a s t e ra l g o r i t h m s t h e o r y , b u ta l s oc a l le x a m i n et h ea b i l i t yo f c o d ew r i t i n gi nr e g u l a t et i m e a tp r e s e n t ，t h es u b j e c tp u b l i s h , e x p e r i m e n tw a t c h i n ga n dt h e j u d g m e n t so fs o u r c ec o d ea l ld e p e n do nm a n u a lw o r k s ot h e r ea r es o m eb u g si nq u a l i t y c o n t r o lo f e x p e r i m e n ta n da p p r a i s eo f s o u r c ec o d e t h ep a p e ra n a l y s e sd i s f i g u r e m e n to f c o d ew r i t i n ge x p e r i m e n t i ta d v a n c e sas o l u t i o no f ak i n d o fo n l i n er e a l t i m ee x p e r i m e n tj u d g es y s t e mc o n t r o l l e db yl v s ( l i n u xv i r t u a ls e r v e r ) a l g o r i t h m s 。t h es y s t e mu s e sn e tl o a db a l a n c et e c h n i q u ea n dp a c k e tc a p t u r et e c h n i q u e t h ep a p e rc o m p a r e sa d v a n c e dt e c h n i q u eo fi p b a s e dl o a db a l a n c e i n c l u d i n gn a tl o a d b a l a n c e ，i pt u n n e ll o a db a l a n c ea n dd i r e c tr o u t i n gl o a db a l a n c e a g a i n s tl i n u xs y s t e m ，i t e x p l a i n se i g h ts c h e d u l i n ga l g o r i t h m si no p e r a t i n gs y s t e mk e r n e l t h es y s t e mu s g sw e i g h t e d l e a s t c o n n e c t i o ns c h e d u l i n gt or e a l i z el o a db a l a n c ei ne x p e r i m e n t ， a tt h es a m et i m e ，t h ep a p e ri n t r o d u c ec o m m o nt e c h n i q u eo fp a c k e tc a p t u r e i tf o c u so n t h es t r u c t u r ea n dp r i n c i p l eo fp a c k e tc a p t u r ed e v e l o p m e n tt o o lw i n p c a p t h es y s t e mr e a l i z e p l a g i a r i s mm o n i t o r i n gb yu s i n gw i n p c a p k e yw o r d s ：n e tl o a db a l a n c e ，p a c k e tc a p t u r e ，n e ta d d r e s st r a n s l a t i o n ，l i n u xv i r t u a ls e d # 翻 4 第一章研究课题介绍 1 1 研究背景 1 1 1 背景介绍 软件实验是计算机专业教学的一个重要实践环节，软件实验不但可以检查学 生对算法理论的掌握程度，而且还可以考核学生在规定时间内编写代码的能力和 效率。但目前从实验题目的发布、实验过程监管到学生提交源代码文档，再到对 源代码文档的评判都是由人工完成。计算机软件实验教学的质量控制、管理与实 验编码质量的评价都存在着问题。其表现是： 人工劳动强度大、效率低下； 很难用白盒测试法对源代码进行结构与性能评判； 因所发布的实验题目数量和发布的方式的限制，很难杜绝学生的抄袭行为； 由于全部依赖人工评判，成绩也会受到不同个体主观标准理解不同的影响， 很难保证实验教学质量和对学生实验结果评价的公平与公正性； 基于此种背景，设计并实现一个在线软件实验辅助支持系统以帮助教师实现 对软件实验教学的全面质量控制与管理是势在必行的。这样的系统不但能够自动 完成以往由手工完成的步骤，而且还提供了实验成绩的分析、统计等辅助功能， 同时还可以提高实验评判的效率和公平与公正性，还将教师从繁琐的工作中解放 出来，更多的精力用来关注教学内容与结构的改进。 1 1 2 类似课题研究情况 a c m i c p c ( a c mi n t e r n a t i o n a lc o l l e g i a t ep r o g r a m m i n gc o n t e s t ) ，即a c m 国 际大学生程序设计竞赛，是由a c m 协会提供给大学生的一个展示和提高解题与 编程能力的机会。 对于每道题目，参赛队必须写出解决该题的程序源代码，提交给在线评测系 统，由在线评测系统编译得到可执行程序，并使用预先设定好的测试用例进行自 动化测试。测试数据通常极为严格。如果对于所有的测试用例该程序都能在规定 的时问内得到f 确的结果，才能够获得通过。本系统的设计正是受到此项赛事的 裁判系统的启迪，而展开研究的。 6 但与计算机软件实验背景不同，a c m 竞赛是将所有参赛选手集中在一起， 竞赛题目是人工结合机器系统在线联合评判题目的。而实验是面对分散的学生， 实验题目完全由人工离线评判的。本系统的设计的应用环境允许学生借助互联网 络进行实验。a c m 竞赛在比赛现场只设有一台裁判服务器，这决定了其在线可同 时承载的负荷不能太大。而计算机软件实验将面对大量学生同时在线，其负荷量 远大于a c m 竞赛：竞赛现场的封闭网络环境和现场裁判的严密监督，选手没有 条件通过网络作弊。而真实实验环境下，学生很可能通过网络相互抄袭。 1 2 研究目的及意义 本论文课题期望设计并实现一个用于软件实验的在线实时评判系统，以帮助 教师实现对软件实验教学的质量控制与管理。本系统可以自动实现实验题目的临 时发布、接收实验结果的提交、完成以往由手工完成的所有评判步骤、实现对可 能存在的抄袭行为的实时监管、提供实验成绩的统计与分析。 本论文课题的研究成果不但改变了计算机软件实验的方式，还对网络负载平 衡和网络监控技术在软件教学实验中的应用做出了大胆尝试。 本论文课题采用了网络负载平衡算法控制功能，不但实现了应用多台服务器 实现集群模式，而且对于教学资源的优化利用也提出了全新的解决方案。对于有 繁重处理任务的实验教学应用不必再为高性能服务器增加投入，利用已有的多台 服务器即可解决，降低了教学成本，最大限度挖掘出了现有教学资源的潜力。 本论文课题采用了网络监控技术，实现了对于实验中利用网络抄袭行为进行 监视，在很大程度上抑制了不良学风的扩散，降低了人工评判抄袭的工作量。 同时，实时实验系统与在线考试系统有很多相似之处。它的技术路线完全可 以为考试系统所借鉴，也为教学自动化提出了一种全新的思路。 1 3 本文工作与论文的组织 本文从计算机软件编码实验的现状和特点入手，提出了在线实时实验评判系 统的设计和实现。该系统已在教学中成功使用。本文在此系统的基础上，提出了 更加完善的整体设计和具体实现方法。其中主要介绍了负载均衡模块和网络监视 模块的设计和实现。 第一章介绍了计算机软件编码实验的现状和特点，提出了本系统研究的目的 和意义。 第二章详细阐述了本系统主要功能，并介绍了系统的总体体系结构。 第三章详细介绍了本系统中负载平衡，网络监控子系统的相关研究。 第四章详细介绍了本系统中负载平衡，网络监控子系统的具体实现方式。 第五章总结了全文的研究工作，指出进一步需要研究的问题。 1 4 本章小结 本章主要论述了本课题的背景，简单介绍了论文的主要研究的内容和本文的 结构。 第二章系统总体结构 2 1 系统功能与设计目标 改系统针对传统计算机代码实验手段中存在的测试过程繁琐，抄袭现象难以发 现，成绩评判受人主观影响等缺陷，使用了i p 负载平衡系统l v s ( 1 i n u xv i r t u a l s e r v e r ) 和w i n p c a p 实现了多层分布式c s ，b s 共存的实时软件编码实验辅助系统。 该系统从教师提供的多道题目中随机组成实验题目供学生自由选择，学生选定题 目后丌始计时。在学生提交答案时系统会自动计算学生所用时问，并调用相应的编译 器进行编译，若编译通过，则会取出该题目预设的测试数据进行测试，测试结果自动 与预存结果比对。以上环节若全部顺利通过，则根据评分规则给出成绩，若有错误， 则提示学生，并且根据评分规则扣除一定分数。 教师也可以预先设定好题目及相应的测试数据和预期结果。评判学生成绩时会参 考多方面的因素，包括所用时间，是否编译错误，测试是否通过等，将之前的一些依 靠人工难以采集的因素考虑为评判成绩的参考，有效提高了实验成绩的公正度和精确 度。 本系统工作流程如图2 - 1 所示： 9 图2 - 1 系统工作流程图 ( 1 ) 管理员从题库中选择题目，或由系统随机选择： ( 2 ) 发布实验，即参加实验者( 学生) 可以看到实验内容； ( 3 ) 学生选择要做的题目，保存试卷； ( 4 ) 学生提交实验源代码文件； o ( 5 ) 自动保存文件并编译： ( 6 ) 通过编译，采用测试用例自动进行测试：否则给出错误提示并扣分； ( 7 ) 顺利通过测试，显示得分或排名；否则给出错误提示并扣分； 2 1 1 系统基本功能简介 本系统基本功能分为管理员( 课程教师) 和学生两部分，其结构如图2 2 所示： 移 瓤 、 镰t 影 多兰蘩留 图2 - 2 功能结构图 下面分为两部分介绍系统功能。 2 1 1 1 管理员端功能 管理员端通过b s 界面提供给实验管理者完备的实验题目发布，实验题目管理， 学生成绩评判等功能。 1 ) 题目管理 功能描述：对题目提供两种管理方式：题库随机生成和手动输入题目。题库可以 由文件导入，这样做主要是之前的题目都是以文件形式存在，为了方便将题目导入数 据库。所存储的实验题目属性如图2 - 3 所示： 图2 - 3 题目属性图 实验题目的分类，主要构成为课程和按章节或按知识结构设定编码。 实验题目的难度系数，如可以定义为a 、b 、c 三级。a 级表示难题，b 级表示 一般题，c 级表示简单题。 测试用例，即实验题目的边界测试输入数据集合和对应的输出数据集合，即容 易使本程序出现异常情况的边界输入数值集合。边界测试数据不作为实验文档的一部 分提供给学生，只作为本系统或教师人工评判学生提交的程序时测试数据使用。可能 一些实验文档内含有典型测试输入数据( 但不能测试出题目的l 临界状况) 和对应的典 型的输出数掘集合，供学生作题调试使用。 实验题目的最大允许c p u 运行时间( 以c p u 时间为单位) 和最长编码时间，以便 对于运行超过规定时限的实验做出强制终止执行的处理。c p u 运行时间不是绝对的， 根据接受提交的服务器负载情况，作适当调整。如果多人集中提交，造成服务器处理 效率下降，此时的最大c p u 时间应该乘上一个适当系数( 大于1 ) 予以放宽。实验题目 的最长编码时日j 是用来限制是否还要接受提交的判决门槛时间。 实验题目的最大内存开销是评价使用算法是否恰当的重要依据。倘若系统检测 到的个提交的程序在运行时使用了超过本限制值的内存容量，则应当终止其执行， 1 2 并给出相应的错误报告。 实验分值规定与难度系数成正比例关系，即难度系数越高的题目折扣系数越小 或不折扣。可以定义a 级题目的折扣系数为l o o 、b 级题目的折扣系数为8 0 9 6 、c 级 题目的折扣系数为6 0 9 6 等。 实验题本身具备一套标准的源代码程序( 可附加典型输入测试数据和对应的输 出结果数据集合) 、输入边界测试数据集合与对应的输出数据集合和测试用例( 如编 译参数) ，以作为系统自动评判学生提交程序的分值以及检查抄袭等功能的计算、比 对模版。 题库可设置筛选规则，系统自动解析筛选规则，根据规则在题库中随机生成试卷， 从而有效控制抄袭，保证实验的公平性。 无论是生成题库还是手动输入，对题目的测试用例的格式有严格的要求，必须按 照规范输入。 本功能可以随时被教师或管理人员所使用，并可以对题目进行插入、修改、删除 和查询处理。 2 ) 题目发布 功能描述：实验发布是指教师在实验发生前可以通过本系统设定一次实验要素， 包括指定实验题目或实验题目类型范围，实验起点时间、实验时长和允许登陆系统时 间区问等数据。在实验开始i j i 学生可以通过本系统获知未来要发生的实验基本要素 数据( 如实验内容、时间、地点等) 。仅当实验发布后，学生在设定的允许登陆系统 时j 日j 区问内j 可以登录系统进行实验。 管理员可以指定某一个或几个实验对外开放。关闭不进行的实验，使其除管理员 外对其他用户不可见，保证了题目不会外泄。 3 ) 实验成绩评判 功能描述：实验结束后，教师可以班级为单位批改学生的答卷。可以查看每道题 目的提交代码，可以单题批改，整卷批改或整班批改。 4 ) 进程控制 功能描述：系统在学生提交代码后，立即启动测试进程进行编译，测试，并采集 其使用的处理器时问和占用存储器容量，记录下作为评分的依据。监视并终止未能正 常结束( 超时或出现异常) 的进程。 5 ) 负载平衡： 功能描述：根据各服务器的负载情况，将用户提交的代码调度到不同的服务器完 成实时测试。 6 ) 系统配置 功能描述：提供对实验进行和成绩批判的参数进行配置。 2 1 1 2 客户端功能 客户端包含了网络数据包捕获分析的组件，所以采用c l i e n t s e r v e r 的架构。 1 ) 题目浏览： 功能描述：使用者在登陆后，系统通过教学平台通信组件获取到登陆者的班级， 课程等信息，并根据具体的学期，获得开放的实验。 2 ) 试卷生成： 功能描述：使用者选定实验后，系统会根据预先的筛选条件自动随机生成试卷， 使用者必须对试卷进行确认，否则，下次进入实验还会随机生成试卷，导致提交出错。 3 ) 答案提交： 功能描述：使用者完成试卷后，要逐题提交代码。系统会实时自动编译，测试， 评分。 4 ) 抄袭检测： 功能描述：在实验期间对客户机的网络进行监视和数据包分析。捕获并分析分析 客户机与同网段内的其他客户机的数据包，检查其中是否有代码以判定是否有抄袭行 为。同时提供按协议捕获数据包的功能。 5 ) 成绩察看： 功能描述：按照登陆者班级，课程的分类列出每次实验的成绩，可以看到每道题 目的成绩。 2 2 组成体系结构 组成体系结构图如图2 - 4 所示 图2 4 组成体系结构图 整个系统利用多台服务器构成一个w e b 集群，共分为三层。第一层是负载调度器 ( d i r e c t o r ) 它一边连接公网，对外提供一个虚拟地址供用户访问，一边与多台服 务器组成的局域网相连，在本系统中由一台运行1 i n u x 操作系统，安装l v s 的服务器 担当调度器，这样使整个系统有较高的吞吐率；第二层是w e b 服务器池，在每个节点 上都部署这相同的服务，根据目前的实际情况使用两台w e b 服务器，可以根据需要动 念添加服务器数量。第三层是共享存储，可以是数据库，也可以是网络文件系统或分 布式文件系统动态数据保存在数据库中，数据库服务运行在独立的服务器上，为所 有w e b 服务器共享。无论同一w e b 服务器上多个动态页面访问同一数据，还是不同w e b 服务器上多个动态页面访问同一数据，数据库服务器有锁机制使得这些访问有序地进 行，从而保证数掘的一致性：静态的数据和文件可以存储在网络文件系统或者分布式 文件系统中。至于选择哪一种，看系统的规模和需求而定。通过共享的网络文件系统 或者分句式文件系统，管理员可以看到统一的文档存储空间，维护和更新文件比较方 便，对共享存储中文件的修改对所有的服务器都有效。本系统一方面根据实际使用环 境，一方面出于成本考虑，将第二层和第三层都部署在了w e b 服务器上，即数据库， 文件系统，w e b 服务都运行在w e b 服务器上，这在单台, e b 服务器性能足够强的情况 下可以节省至少一台服务器，简化了部署工作。 其中： 负载调度器：采用r e d h a tl i n u x 操作系统，内核版本为2 6 。其上运行l v s ( l i n u xv i r t u a ls e r v e r ) 完成i p 层负载均衡调度。如前所述，l v s 提供了三种实现 i p 层负载均衡调度的方式v s n a t 技术( v i r t u a ls e r v e rv i an e t w o r ka d d r e s s t r a n s l a t i o n ) ，v s t u n ( v i r t u a ls e r v e rv i ai pt u n n e l i n g ) ，v s d r ( v i r t u a ls e r v e r v i ad i r e c tr o u t i n g ) ，本系统使用了v s n a t 的方式。负载调度服务器需要将请求的 目标地址和端口改写后转发给服务器，再将服务器的反馈的目标地址和端口改写发给 客户端。 w e bs e r v e r ：采用w i n d o w s 2 0 0 3 一s e r v e r 操作系统，使用i i s 6 0 发布服务， 所有业务逻辑采用w e bs e r v i c e 。这样做的目的是一方面在设计中能够很好的将业务 逻辑分离出来，使软件整体结构清晰，易于维护；另一方面可以方便服务部署，发布。 最重要的一点是w e bs e r v i c e 依靠基于h t t p 协议的s o a p ( s i m p l eo b j e c ta c c e s s p r o t o c o l 简单对象访问协议) 消息传递，而l v s 很好的支持基于h t t p 协议请求的调 度，这种协议上的互通性使服务器与负载调度器有机结合成一个整体。w e b 服务器负 责全部业务逻辑的处理，包括作业的转存，编译，测试以及相应数据库的操作。 这种体系结构可以保证系统具有如下特性： 访问透明性：虽然负载调度器和多台服务器组成一个w e b 服务集群，但从用户的 角度看来，只是一个服务地址，用户不必关心是哪台服务器处理了请求。 冗余性：通过使用l v s 一方面解决了单服务器性能不足的问题，另一方面也为系 统提供了冗余备份。当台服务器出现故障，调度器会自动终止对故障服务器的调度。 体系结构独立性：在w e b 服务器集群中，任一台w e b 服务器出现故障都不会对整 个集群产生影响，负载调度器会自动将请求调度到正常的w e b 服务器。 可扩展性：l v s 允许w e b 服务器集群动态的添加或移除服务器，对请求的处理不 会产生任何影响。 可审计性：所有的操作均有日志记录，方便日后的分析处理。 1 6 2 3 软件体系架构 本系统软件体系架构如图2 - 5 所示 图2 - 5 软件体系结构图 1 7 其中： 管理员端：负责实验内容，题目的设置，测试用例的测试，保存：评分标准设 置，实验发布等管理功能。 ( 1 ) 权限控制组件：控制不同登录用户的权限，保证系统安全。 实现方式：通过权限访问控制列表，实现单用户对应单一功能的权限控制。 ( 2 ) 实验管理组件：实验原始数据的采集。包括实验内容，题目，范例代码， 测试用例。每一份测试用例都要经过范例代码的测试，通过后才能保存。 实现方式：根据题目的必需属性制定了一系列的规则，包括题目文件命名 规则，测试用例文件格式规范，分数评判规则；系统会按照这些规范解析文件 名和文件内容，将题目自动导入数据库。并要求每道题目提供一份范例源代码， 导入每一个测试用例时，都要经过与学生提交代码相同的评判流程，以保证范 例代码正确性，之后才能导入系统中。 ( 3 ) 实验发布组件：管理员可以指定某一个或几个实验对外开放。关闭不进行 的实验，使其除管理员外对其他用户不可见，保证了题目不会外泄。 实现方式：由管理员操作改变实验状态为开放或关闭，学生获取实验时只 能获取到状态为开放的实验。 客户端：负责获取制定实验题目，提交实验代码，成绩察看，同时对实验期间 的网络流量进行监控，记录抄袭嫌疑。 耄 ( 1 ) 权限控制组件：控制不同登录用户的权限，保证系统安全。 实现方式：通过权限访问控制列表，实现单用户对应单一功能的权限控制。 ( 2 ) 实验组件：获取指定的或随机的实验题目；实验代码文件的提交以及成绩 ( 排名) 查看。 实现方式：使用教学平台通信组件从已有的教学平台获取完备的教学数据， 本系统再处理这些数据，使使用者获取正确的实验信息。之后从系统获取随机 试卷，使用者确认后会将该试卷记入使用者名下。 ( 3 ) 网络监控组件：监控并分析网络流量，记录有抄袭嫌疑的用户名和i p 。具 体功能包括： 捕获客户机网络通信包： 分析数据包，判断是否包含代码： 捕获指定协议的数据包： 捕获指定网段内通信的数据包； 实现方式：利用w i n p c a p ，使用c # 对其进行封装，使得w i n p c a p 的功能融 合进本系统。 业务处理中心：负责实验相关数据的维护，实验代码的测试，成绩评判。 ( 1 ) 题目管理组件：使用者选定实验后，系统会根据预先的筛选条件自动随机 生成试卷，使用者必须对试卷进行确认，否则，下次进入实验还会随机生成试 卷，导致提交出错。 实现方式：系统解析查询字符串自动生成s q l 语句，在数据库端实现随机 试卷的生成，使用者确认后会将该试卷记入使用者名下。 ( 2 ) 代码处理组件：对实验代码保存，编译，测试。具体功能包括： 自动编译代码： 自动测试代码； 自动代码过滤，过滤代码中的暂停代码，避免自动测试进程长时间驻 留内存； 实现方式：通过调用外部编译器重新编译源代码生成可执行文件，再运行 生成的可执行文件并自动注入测试用例，进行测试。根据程序的运行结果按 照评分规则记录成绩。 ( 3 ) 进程控制组件：控制服务器端的测试进程，防止其长期驻留内存，造成系 统崩溃；同时采集测试进程使用的处理器时间和占用存储器容量，记录下作为 评分的依据。 实现方式：对每个测试进程进行监控，设定运行上限时间，超出上限即强 制结束进程；动念采集占用存储器容量，记录峰值；测试结束时记录处理器 时问。 ( 4 ) 成绩管理组件：根据测试结果，评分规则为参加实验者打分。 实现方式：通过教学平台通信组件获取登陆者教学信息，本系统处理后获 得相应实验的成绩。 ( 5 ) 负载调度中心：负责将客户端发出的请求在w e b 集群中均衡调度。具体功 能包括： 9 允许动态向群集中添加服务器： 根据服务器实时负载调度用户请求； 自动监测服务器是否可用； 实现方式：使用l v s 调度器，采用专门的i p 负载平衡算法实现请求调度。 数据中心： ( 1 ) 文件库：保存范例代码和已提交实验代码文件。 ( 2 ) 数据库：保存实验相关数据的数据库，本系统采用s q ls q e v e r 2 0 0 5 实现。 通讯接口：负责各子系统间的消息传递通信，全部采用基于x m l 消息的w e b s e r v i c e 实现。 教学平台通讯接口：负责与现有教学平台的通信，使得本系统可以利用教学平 台的数据，也使教学平台具备了基础数据提供者的功能，方便了其他教学系统得融合 采用w e bs e r v i c e 实现。 2 4 本章小结 本章主要介绍了实时实验系统的总体结构设计，详细说明了系统的功能和设计目 标。系统结合先进的i p 负载平衡技术，采用多层分布式体系结构，将系统划分为管 理员端，客户端，业务处理中心，和数据中心；并借助特别设计的接口与教学平台融 合。 第三章项目相关技术研究 负载平衡和网络监控是本系统中所涉及的两个核心技术，也是影响本系统成败的 关键。本章就此展丌研究，论述在设计过程中所采用的具体技术、方法和思路。 3 1 网络负载平衡技术研究 3 1 i 选择负载平衡技术的背景 3 1 1 1 使用群集的背景 在本系统中，对于学生每次提交的源代码文件都要进行实时测试。而负载最大的 环节也f 是对软件编码的评判，其处理流程如图3 一l 所示： 软件编码评判 嗷 e = 习一磊 ； 曩 匕= 一y ： 7 9 一 粤 篓 囱一 o 。 j = l ： d o j = ( j + 1 ) m o dn i f ( w ( s ) 0 ) 1 = j ： r e t u r ns i ：) w h i l e ( j f = i ) ： r e t u r nn u l l ： 轮叫调度算法假设所有服务器处理性能均相同，不管服务器的当前连接数和 响应速度。该算法相对简单，不适用于服务器组中处理性能不一的情况，而且当 请求服务时间变化比较大时，轮叫调度算法容易导致服务器问的负载不平衡。 虽然r o u n d r o b i nd n s 方法也是以轮叫调度的方式将一个域名解析到多个 i p 地址，但轮叫d n s 方法的调度粒度是基于每个域名服务器的，域名服务器对域 名解析的缓存会妨碍轮叫解析域名生效，这会导致服务器间负载的严重不平衡。 这里，网络负载平衡l b s 的轮叫调度算法的粒度是基于每个连接的，同一用户的 不同连接都会被调度到不同的服务器上，所以这种细粒度的轮叫调度要比d n s 的 轮叫调度优越很多。 4 1 2 2 加权轮叫调度 加权轮叫调度( w e i g h t e dr o u n d r o b i ns c h e d u l i n g ) 算法可以解决服务器间性 能不一的情况，它用相应的权值表示服务器的处理性能，服务器的缺省权值为1 ， 假设服务器a 的权值为l ，b 的权值为2 ，则表示服务器b 的处理性能是a 的两倍。 加权轮叫调度算法是按权值的高低和轮叫方式分配请求到各服务器。权值高的服 务器先收到的连接，权值高的服务器比权值低的服务器处理更多的连接，相同权 值的服务器处理相同数目的连接数。 加权轮叫调度算法流程如下： 假设有一组服务器s = s o ，s 1 ，s n ，一个指示变量i 表示上一次选择的 服务器，w ( s ) 表示服务器s i 的权值。变量i 被初始化为n 一1 ，其中n o 。 假设有一组服务器s = s o ，s l ，s n j ，w ( s i ) 表示服务器s i 的权值，一个 指示变量i 表示上一次选择的服务器，变量e w 表示当前的权值，髓x ( s ) 表示集 合s 中所有服务器的最大权值，g c d ( s ) 表示集合s 中所有服务器权值的最大公约 数，变量i 和e w 最初都被初始化为零。当所有服务器的权值为零，即w ( s i ) = o ， 则所有的新连接都会被丢掉。 w h i l e ( t r u e ) i f ( i = o ) c i f c w g c d ( s ) ： i f ( c w = c w ) r e t u r ns i ： 加权轮叫调度算法还是比较简单和高效。当请求的服务时间变化很大，单独 的加权轮叫调度算法依然会导致服务器间的负载不平衡。 4 1 2 3 最小连接调度 最小连接调度( l e a s t c o n n e c t i o ns c h e d u l i n g ) 算法是把新的连接请求分配 到当前连接数最小的服务器。最小连接调度是一种动态调度算法，它通过服务器 当前所活跃的连接数来估计服务器的负载情况。调度器需要记录各个服务器己建 立连接的数目，当一个请求被调度到某台服务器，其连接数加i ：当连接中止或超 时，其连接数减一。 当各个服务器有相同的处理性能时，最小连接调度能把负载变化大的请求分 布平滑到各个服务器上，所有处理时间比较长的请求不可能被发送到同一台服务 器上。但是，当各个服务器的处理能力不同时，该算法并不理想，因为t c p 连接 处理请求后会进入t i m e w a i t 状态，t c p 的t i m e w a i t 一般为2 分钟，此时连接 还占用服务器的资源，所以会出现这样情形，性能高的服务器己处理所收到的连 接，连接处于t i m e w a i t 状态，而性能低的服务器己经忙于处理所收到的连接， 还不断地收到新的连接请求。 4 1 2 4 加权最小连接调度 加权最小连接调度( w e i g h t e dl e a s t - c o n n e c t i o ns c h e d u l i n g ) 算法是最小连 接调度的超集，各个服务器用相应的权值表示其处理性能。服务器的缺省权值为1 ， 可以动态地设置服务器的权值。加权最小连接调度在调度新连接时尽可能使服务 器的已建立连接数和其权值成比例。加权最小连接调度的算法如下： s = 【s o s l ，s n ) ，w ( s i ) 表示服务器s i 的权值，一个指示变量i 表示上 一次选择的服务器，变量e w 表示当前的权值，m a x ( s ) 表示集合s 中所有服务器 的最大权值，g c d ( s ) 表示集合s 中所有服务器权值的最大公约数， 假设有一组服务器s = s = s o ，s l ，s n ，每台服务器的权值为w i ( i = o ，1 ，n 1 ) ，己建立的连接数目为c i ( i = o ，1 ，n - 1 ) ，服务器当前连接数的 总和为s = e c i ( i = o ，1 ，n 一1 ) ，当前的新连接请求会被发送服务器j ，服务器j 满足以下条件： ( c j s ) w j = m i n ( c j s ) w i ( i = o ，1 ，n 一1 ) 因为s 在这一轮查找中是个常数，所以判断条件可以优化为 c j w j = m i n c i w i ) ( i = o ，1 ，n 1 ) 因为除法所需的c p u 周期比乘法多。在l i n u x 内核中为提高处理速度不允许 浮点除法，服务器的权值都大于零。所以判断条件c j w j c i w i ，可以进一步优化 为c j * w i c i * w j 。 同时保证服务器的权值为零时，服务器不被调度。算法的流程如下： f o r ( i = o ：j o ) b r e a k ：) f o r ( i = j + l ：i n ：j + + ) ( i f ( c j * w i c i * w j ) j 2i ：f i f ( j t ) m = w g c ( s e r v e r s e t d e s t i p ) ： r e m o v emf r o ms e r v e r s e t d e s t i p ：) 】s e r v e r s e t d e s t i p 1 a s t u s e = n o w ； i f ( s e r v e r s e t d e s t i p c h a n g e d ) s e r v e r s e t d e s t i p 1 a s t m o d = n o w ； r e t i j r nn ： 5 5 此外，对关联变量s e r v e r s e t d e s t i p 也要进行周期性的垃圾回收 ( g a r b a g e c o l l e c t i o n ) ，将过期的目标i p 地址到服务器关联项进行回收。过期的 关联项是指那些当前时间( 实现时采用系统时钟节拍数) 减去最近使用时间 ( 1 a s t u s e ) 超过设定过期时间的关联项。系统缺省的设定过期时间为2 4 小时。 4 1 2 7 目标地址散列调度算法分析 目标地址散列调度( d e s t i n a t i o nh a s h i n gs c h e d u l i n g ) 算法也是针对目标i p 地址的负载均衡，但它是一种静态映射算法，通过一个散列( h a s h ) 函数将一个目 标i p 地址映射到一台服务器。目标地址散列调度算法先根据请求的目标1 p 地址， 作为散列键( h a s h k e y ) ，从静态分配的散列表找出对应的服务器，若该服务器是可 用的且未超载，将请求发送到该服务器，否则返回空。该算法的流程如下： 目标地址散列调度算法流程： 假设有一组服务器s = ( s o ，s l ，s n 一1 ，) ，w ( s i ) 表示服务器s i 的权值，c ( s i ) 表示服务器s i 的当前连接数。s e r v e r n o d e 是一个有2 5 6 个桶( b u c k e t ) 的h a s h 表，一般来说服务器的数目会远小于2 5 6 ，当然表的大小也是可以调整的。算法的 初始化是将所有服务器顺序、循环地放置到s e r v e r h o d e 表中。若服务器的连接数 目大于2 倍的权值，则表示服务器己超载。 n = s e r v e r n o d e h a s h k e y ( d e s ti p ) i f ( ( ni sd e a d ) o r ( w ( n ) = 0 ) o r ( c ( n ) 2 * w ( n ) ) ) r e t u r nn u l l ： r e t u r nn ： 在实现时，采用素数乘法h a s h 函数，通过乘以素数使得散列键值尽可能地达 到较均匀的分布。所采用的素数乘法h a s h 函数如下： 素数乘法h a s h 函数： s t a t i ci n l i n eu n s i g n e dh a s h k e y ( u n s i g n e di n td e s t i p ) r e t u r n ( d e s t i p * 26 5 4 4 3 5 7 6 1 u l ) & h a s h t a b m a s k ； 其中，2 6 5 4 4 3 5 7 6 1 0 l 是2 到2 3 2 ( 4 2 9 4 9 6 7 2 9 6 ) 间接近于黄金分割的素数， ( s q r t ( 5 ) 一1 ) 2 = 0 6 1 8 0 3 3 9 8 9 2 6 5 4 4 3 5 7 6 l 4 2 9 4 9 6 7 2 9 6 = o 6 1 8 0 3 3 9 8 7 4 1 2 8 源地址散列调度算法分析 源地址散列调度( s o u r c eh a s h i n gs c h e d u l i n g ) 算法正好与目标地址散列调度 算法相反，它根据请求的源1 p 地址，作为散列键( h a s hk e y ) 从静态分配的散列表 找出对应的服务器，若该服务器是可用的且未超载，将请求发送到该服务器，否 则返回空。它采用的散列函数与目标地址散列调度算法的相同。它的算法流程与 目标地址散列调度算法的基本相似，只是将请求的目标i p 地址换成请求的源i p 地址。 在实际应用中，源地址散列调度和目标地址散列调度可以结合