（计算机科学与技术专业论文）采用chord协议实现分布式内存数据库系统的研究.pdf

北京邮电大学硕士学位论文采用c h o r d 协议实现分布式内存数据库系统的研究 采用c h o r d 协议实现分布式内存数据库系统的研究 摘要 随着通信技术的飞速发展，信息的海量存储与实时处理，对设备 的性能要求越来越高了。但是，无论多大的磁盘空间，从最初的几k ， 到几十g ，几百t ，始终还是不能满足所有的需求。然而，互联网的 发展却成为一个成功的例子，网上每时每刻都有大量的信息、数据在 传输，但是却不会发生由于数据量太大而导致整个互联网崩溃的情 况。究其原由，数据的分布存储，在充分利用存储资源的同时，又能 够动态的共享数据。另外很多企业都具有一定规模的局域网资源。针 对以上特点，本文提出一种分布式数据管理的体系结构分布式内 存数据库系统( d i s t r i b u t e dm e m o r yd a t a b a s es y s t e m ，以下简称 d m d s ) ，利用网络技术来解决这个问题。 d m d s 体系策略是结合分布式技术和内存数据库技术的优点，它 的功能主要是提供给用户能够透明的使用局域网上的内存资源。由于 该资源的存取速度要远远超过普通数据库软件的磁盘操作速度，因 此，该方案不但能够共享局域网的内存资源，还可以实现高效的数据 存储管理。基于c h o r d 协议的p 2 p 系统动态管理系统节点，抛弃传统 的b s 或c s 模式，保证了系统的灵活性和容错性，同时还提高了系 统的运行效率和负载均衡性。随着计算机网络技术的成熟发展和大容 量廉价内存的出现，d m d s 的应用前景将越来越广阔。 关键词分布式、内存数据库、c h o r d 、p 2 p 、包 i i i 。 北京邮电大学硕士学位论文 采用c h o r d 协议实现分布式内存数据库系统的研究 r e s e a r c h0 fd i s t r i b u t e dm e m o r yd a t a b a s e s y s t e mb y c h o r dp r o t o c o l a b s t r a c t w i t ht h ef a s td e v e l o p m e n to fc o m m u n i c a t i o nt e c h n o l o g y ，m u c h i n f o r m a t i o n s t o r a g e d a n dr e a l t i m e p r o c e s s e d ，t h ep e r f o r m a n c e r e q u i r e m e n tf o re q u i p m e n t si s m o r ea n dm o r eh i g h b u tt h eb i gd i s k s p a c ec a n n o tm e e ta l ln e e d st h r o u g h o u tr e g a r d l e s so fs e v e r a lk d o z e n sg o rs o m eh u n d r e d st h o w e v e r ，t h ed e v e l o p m e n to fi n t e m e tb e c o m e sa s u c c e s s f u le x a m p l ea c t u a l l y ，t h e r ei sm a s s i v ei n f o r m a t i o no nt h en e t ，i ti s t r a n s m i t t e de v e r yt i m e ，b u ti tc a n tc a u s et h ee n t i r ei n t e r n e tc o l l a p s e da sa r e s u l to ft h em u c hd a t a b e c a u s eo ft h ed i s t r i b u t e ds t o c k e dd a t aw ec a n m a k ef u l lu s eo fm e m o r yr e s o u r c e sa n ds h a r et h e m m o r e o v e rm a n y e n t e r p r i s e sa l l h a v et h el o c a la r e an e t w o r kr e s o u r c e s a b o v ea 1 1 t h i s p a p e rm a k eak i n d o fa r c h i t e c t u r e 。_ _ d i s t r i b u t e dm e m o r yd a t a b a s e s y s t e m ( h e r e a f t e rr e f e r st oa sd m d s ) t os o l v et h i sp r o b l e mb yu s i n gt h e n e t w o r kt e c h n o l o g y t h es t r a t e g yo fd m d si st ou n i t et h em e r i to fd i s t r i b u t i o n a l t e c h n i c a la n dt h e m e m o r yd a t a b a s e i tp r o v i d e s t h eu s e rw i t ht h e t r a n s p a r e n tu s eo fl o c a la r e an e t w o r km e m o r yr e s o u r c e s b e c a u s et h i s r e s o u r c e sa c c e s ss p e e ds u r p a s s e st h eo r d i n a r yd a t a b a s ed i s ko p e r a t i n g s p e e d ，t h e r e f o r e ，t h i sp l a nn o to n l yc a ns h a r et h el o c a la r e an e t w o r k m e m o r yr e s o u r c e s ，b u ta l s om a yr e a l i z et h eh i g h l ye f f e c t i v ed a t as t o r a g e m a n a g e m e n t t h ep 2 ps y s t e mc a nd y n a m i c a l l ym a n a g ei t sn o d e sb a s e d o nc h o r da g r e e m e n t ，t h et r a d i t i o n a lb so rc sp a t t e r ni sa l s oa b a n d o n e d ， w h i c hc a ng u a r a n t e e f l e x i b i l i t y a n dt o l e r a n c eo fs y s t e m ，m e a n w h i l e e n h a n c et h es y s t e mo p e r a t i n ge f f i c i e n c ya n dp r o p o r t i o n w i t ht h em a t u r e d e v e l o p m e n to fn e t w o r kt e c h n o l o g ya n da p p e a r a n c eo ft h el o w p r i c e d m e m o r yo fh i g hc a p a c i t y ，t h ea p p l i c a t i o np r o s p e c to fd m d s w i l lb em o r e i v 北京邮电大学硕士学位论文 采用c h o r d 协议实现分布式内存数据库系统的研究 a n dm o r ev a s t e r k e yw o r d sd i s t r i b u t e ds y s t e m ，m a i nm e m o r yd a t a b a s e ，c h o r d ， p 2 p ，p a c k a g e v 北京邮电大学硕士学位论文 采用c h o r d 协议实现分布式内存数据库系统的研究 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：耋矍盘日期：! 翌：三兰f 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名：筮磊 日期：兰丝芝：主，墨j 导师签名 寺啦卜 日期 签北京邮电大学硕：仁学位论文采用c h o r d 协议实现分布式内存数据库系统的研究 1 1 背景 1 1 1 项目背景 第一章绪论 伴随着计算机通信技术的高速发展，以及地理上分散的公司、组织对数据更 为广泛的应用要求，传统意义上的单计算机有限的磁盘空间已经无法满足所有的 需求。然而互联网的成功发展却给我们带来一个很好的例子，由此，产生了分布 式系统( d i s t r i b u t e ds y s t e m ) ，并且它已经在电子商务、自动化技术和工作流控 制系统等领域发挥着重大的作用。 另一方面，传统的数据库技术将数据存放在磁盘中，这样数据的读写不可避 免受到磁盘读写的影响，随着廉价大容量内存的出现，内存数据库( m a i nm e m o r y d a t a b a s e ) 正变得可行。简单而言，内存数据库就是以内存作为存储介质的数据 库，并仅在系统设备需要时才将数据写入磁盘。这样，势必大大加快数据的处理 速度，同时满足了高性能，保证“硬实时”这样的性能要求。文献研究表明，目前 在高速局域网络中对网络主机内存c a c h e 的存取速度已经高于直接存取本机硬盘 速度，是后者的2 蛰 1 0 倍1 1 。 c h o r d 协议是2 0 0 1 年由美国麻省理工学院提出的，目前仍在研究当中，该技 术为我们搭建p 2 p 网络创造了一个方便、快捷的环境，使分布式搜索变得更加容 易。相信不久的将来，它必能得到更广泛的应用。 2 0 世纪8 0 年代末，s u n 公司提出“网络就是计算机”的名言，今天这句话已经 得到充分的证实。分布式计算机系统具有很多优点，如：坚定性强、扩充容易、 可靠性好、维护方便和效率高等。所以我们想要利用分布式技术和内存数据库技 术各自的优点，同时使用c h o r d 网络做底层，提出一种新的解决方案，即：基于 c h o r d 协议的分布式内存数据库系统策略。 1 1 2 目前国内外该课题的研究状况 目前，国内外有大量关于分布式系统、内存数据库矛h c h o r d 协议的成功研究 北京邮电大学硕士学位论文采用c h o r d 协议实现分布式内存数据库系统的研究 经验，极具指导意义。 从8 0 年代中期开始至今，分布式技术已经得到了飞速的发展，目前分布式结 构使用的核心大致上可以分别两种不同的工业标准【引，第一种是m i c r o s o f l 锘l j 定的 c o m d c o m 以及c o m + ，第二种则是由7 0 0 多个厂商共同提倡的c o r b a ( c o m m o no b j e c tr e q u e s tb r o k e ra r c h i t e c t u r e ) 。由于分布式结构的广为流行，所以 现在也有愈来愈多的分布式技术是根据这两种分布式核心技术再加以演进而产 生的，例如e j b ( e n t e r p r i s ej a v ab e a n ) 等。 内存数据库( m m d b )的研究始于1 9 8 0 年，最初的目标就是要解决在电 信、金融领域的关键应用系统中，大规模内存数据的有效管理问题，有影响的研 究项目有1 3 j ：i b m 公司的s t a r b u r s t 可扩展d b m s 研究项目；a t & tb e l l 实验室 进行的d a l i 项目等。至u 1 9 9 0 年代中后期，由于软硬件技术的进步，配置8 g b 甚 至更多内存、运行6 4 位操作系统的计算机已很普通，将几百m b 甚至几十g b 的 数据库全部装入内存在技术上的限制已不存在，m m d b 技术逐渐成熟并走向商 用市场。! z i l u c e n t 公司开发的通用内存数据库系统d a t a b l i t z 就在5 e s s 交换机 和实时计费应用s u n r i s e 等系统中被广泛使用。t i m e s t e n 公司的m m d b 产品 t i m e s t e n 也在h p 的智能网平台、c i s c o 的v o i p 呼叫代理，以及a l c a t e l 、e r i c s s o n 等的电信系统中使用，极大地改善了电信系统的服务性能。 c h o r d 协议主要由麻省理工学院进行研究，已经产生相对成熟的协议，目前 它的研究方向主要在于解决c h o r d 节点的分割问题、安全问题等，同时c h o r d 在因 特网上大规模应用还存在不小问题，这些都需要进一步去解决。 1 2 研究动机 根据分析和调研结果，d m d s 系统目前是基于中小型企业的实际需求来设 计实现的。大部分中小企业在应用上都存在如下特点：业务不太多，对于数据量 的需求不是很大，这样就可以将数据存储到局域网的内存中，来提高访问速度； 应用相对简单，但是对数据的实时更新速度要求较高，符合内存数据库的实时性 高的要求；用户访问量很大，要求系统的回应时间加快； 从另一方面看，我们可以发现在现有技术水平的前提下，计算机系统本身 存在着相当程度的不稳定性，如经常可能发生电源和网络的中断。这种不稳定性 在中小型企业的计算机系统中体现得更为明显，所以要求我们提供可靠安全，但 性能和实时性高的系统来满足这样的需求。 所以我们的设计开发就以上述中小企业的需求为基础来设计d m d s 系统。 北京邮l 乜大学硕士学位论文 采用c h o r d 协议实现分布式内存数据库系统的研究 利用c h o r d 协议思路上的优势，以及p 2 p 网络带来的分布特性而提出分布式内 存数据库系统( d i s t r i b u t e dm e m o r yd a t a b a s es y s t e m ，以下简称d m d s ) 的策略。 d m d s 的目标是提供给用户能够透明的使用局域网上的内存资源，在使用内存 资源的同时，用户可以享受高可靠性的内存保护功能。d m d s 策略是将数据放 到局域网的机器的内存中，来代替放到传统的磁盘阵列存储介质中，直接利用内 存读入读出数据，同时对这种内存中的数据做一个保护备份机制，保证数据的安 全。系统的处理速度依赖于网络的带宽和内存处理数据的速度，对于现在的局域 网中的机器系统，网络的带宽和内存的效率都已经不是问题。 分布式内存数据库系统具有如下优点： ( 1 ) 内存直接快速存取，优于普通的数据库软件磁盘存取。 ( 2 ) 现有设备计算资源的利用率低是不可忽视的，通过该设计能够实现c p u 和闲散内存的高效利用。 ( 3 ) 分布式的设计，尽管组织机构分散，但保证了数据间的相互联系。 ( 4 ) 整个系统实现均衡负载，负载在各节点间分担，可避免临界瓶颈。 ( 5 ) 容错性和可靠性高，数据分布在不同节点，且存有多个备份，即使个 别节点发生故障，不致引起整个系统的瘫痪。 ( 6 ) 动态性和可扩充性好，当需要增加新的节点时，可在对当前正在运行 的系统影响最小的情况下进行。 1 3 论文工作 整个论文的目标是使用c h o r d 协议设计并实现一个简单的分布式内存数据库 系统模型，本人在项目中主要负责以下工作： 与项目组其他成员共同完成了分布式内存数据库系统分析、设计、方案确定、 功能定义和任务划分等工作。 负责底层c h o r d 协议的实现：包括c h o r d 节点的加入、离开、查找、更新等操 作，关键字的备份操作。提出服务实体和消息模式分别完成c h o r d 节点的功能操 作和通信操作，同时对c h o r d 协议尝试进行了修改。 负责c h o r d 部分的测试和该部分与内存数据库的接口设计工作。 与项目其他成员一起完成上层应用实例一分布式内存数据库。 北京邮电大学硕士学位论文 采用c h o r d 协议实现分布式内存数据库系统的研究 整个项目使用j a v a 技术( j d k l 4 ) 开发完成。 1 4 论文结构 本文的论文结构大致如下： 第二章主要总结介绍分布式内存数据库系统设计和存在的问题，主要从分布 式数据库、内存数据库以及c h o r d 协议三方面展开。重点论述c h o r d 协议如何解决 现有平台存在的缺点。 第三章提出了分布式内存数据库底层管理系统的描述模型，并具体介绍了模 型的系统分析与设计过程，并论述了该模型的体系结构。这一章重点提出基于 c h o r d 的管理机制，同时解决了上层应用对底层的需求问题。 第四章介绍了作者所参与的c h o r d 协议的具体实现环节，侧重论述作者负责 的c h o r d 节点的加入、离开、查找、更新的实现，以及基于消息的通信模式。 第五章介绍了对分布式内存数据库系统的试验验证。主要介绍c h o r d 网络和 包数据访问的验证过程。 第六章分析总结了现阶段的工作情况，分析了现阶段工作还存在的一些问 题，并提出了解决这些不足的可行性建议，最后在现有的基础上对系统应用和发 展的前景进行了展望。 4 北京邮电大学硕二l 学位论文采用c h o r d 协议实现分布式内在塑塑壁墨堑塑研究 第二章技术背景 本章先介绍目前分布式内存数据库系统的特点以及存在的问题，然后引出我 们重点讲述的c h o r d 协议，阐明作者使用该协议的原因。同时对课题研究涉及到 的热点技术，如分布式数据库技术，内存数据库技术也做了简要的说明。 2 1 分布式内存数据库 2 1 1 分布式内存数据库的概念 我们提出的分布式内存数据库可以简单定义为在一个分布式网络的节点上 进行内存数据管理的系统。在设计上主要吸取了分布式数据库和内存数据库的思 想，在这里我们先简单介绍一下两者的概念，然后再提及一下当前已有数据库的 特点。 分布式数据库是由一组数据组成的1 4 】，这组数据分布在计算机网络的不同计 算机上，网络中的每个节点具有独立处理的能力( 称为场地自治) ，可以执行局 部应用。同时，每个节点也能通过网络通信子系统执行全局应用。 内存数据库( m m d b ) 1 5 】，它将整个数据库或大部分热点数据存放在主存中， 消除了i o 瓶颈，省去了大部分磁盘i o 操作，也就是相当于创建了一个r a m 磁盘。在传统的面向磁盘数据库d r d b 中，数据库主备份位于磁盘，在m m d b 中则位于主存。对不同的存储介质，d b m s 采取的策略也各不相同。数据驻留内 存，可以大部分或全部在内存中存取数据，缩短系统的响应时间，内存数据库是 支持实时事务的最佳技术。 我们设计的系统主要是针对北京邮电大学计算机应用实验室宋平、田星同学 的毕业论文：分布式内存数掘库1 6 】做的改进，该平台提出了一个分布式内 存数据库系统的实现策略，主要概念有：包、节点、队长( 队员) 、智能客户端： “包”是内存数据的存储、定位、保护的基本单位。用户数据存储在不同的包中， 由包通过“包管理实体”来负责数据的组织、存储以及定位，数据操作以包为单 位进行。“节点”是该平台网络的组成单位，可以简单认为是参与系统的各个计 算机；“队长( 队员) ”是对节点的一些职能划分，它们主要是反映系统内所有 北京邮电大学硕= b 学位论文采用c h o r d 协议实现分布式内存数据库系统的研究 包管理实体的运行状况和检测网络故障，并通过队长的集中控制机制来对不良的 节点或出现网络故障的节点进行处理。“智能客户端”是用户对其平台的访问接 口，提供了透明访问功能( 关于具体内容请参考该论文，在此不再详述) 。 2 1 2 目前存在的问题 分布式内存数据库1 6 】实现了数据的分布式内存管理功能，但是又存在 一些问题，主要表现在以下三个方面： ( 1 ) 系统负载过重 分布式内存数据库1 6 】提出的是一种集中和分治的策略，存在有中心服务 器记录各个实体节点的情况，客户端从中心服务器的包地址状态表进行实体管理 和搜索，同时如果各个实体节点的数据包发生变化，需要同步中心服务器的包地 址状态表，所以其系统仍然具有中心化的特点，是一种非纯粹的p 2 p 结构。这样 容易因为访问量的增大而造成中心服务器的负担过重。同时所有对系统的访问都 要通过智能客户端来进行，这样也增加了它的负荷。 为了保证系统的可靠性，在该论文当中，提出了队长机制，利用网络中指定 好的“队长 ，“副队长”和“队员”定期发出的互测请求，来发现网络节点 的故障情况，这样会增加各个节点特别是“队长”的负担。 另外，对于该论文提出的智能客户端，需要有w e b 服务器的支持，这也额外 增加了系统的开销。 ( 2 ) 扩展性差 在分布式内存数据库【6 】的系统中，新节点的加入是通过写配置文件的形 式的，需要预先在配置文件中保存节点地址和节点数据情况。该文件由手动完成 也容易出错。这些都使系统在扩展时相对比较麻烦。 ( 3 ) 可靠性不足 由以上叙述知道，在该论文中提出了队长机制( 队长，副队长和队员) ，它 们之间互相监督，来保证网络的可靠性。但是这种做法存在着缺陷，如果队长和 副队长的节点同时死掉，整个机制就无法继续使用。完全依赖于某些节点的做法 降低了系统的可靠性。 总的来说，分布式内存数据库提出的系统策略中存在着以上三个问题， 为了解决这些问题，我们引入了c h o r d 协议。 6 北京邮电大学硕士学位论文 采用c h o r d 协议实现分布式内帝塑塑壁墨堕箜研究 2 2c h o r d 协议 由于分布式内存数据库系统是在参与系统的机器节点中，动态分配内存的， 因此系统具有良好的动态适应性。整个数据库系统可以自由增删成员节点，而不 会损失数据内容。当某节点由于故障或退出系统时，系统会立即启动该节点数据 内容的备包，并按照故障处理方案作相关处理。这样，系统就会一直保持工作状 态而不损失数据了。因此，要维护整个系统的正常运行，需要合理的设计管理角 色，控制系统资源。 那么，如何选择一种合适的管理机制，既可以随时添加新的节点到系统中， 又能够及时处理运行中退出系统的节点? 显然，需要一种灵活可靠的算法，在此， 我们使用了p 2 p 系统中应用广泛的c h o r d 协议。 2 2 1c h o r d 协议的概念 c h o r d 其实是一种分布式搜索协议【7 】，它提供的核心功能就是：给定一个值， 来映射到一个节点。而这个功能，则是通过一致性哈希函数( c o n s i s t e n th a s h ) 来具体实现的。使用它有很多好处，它可以在p 2 p 的环境下很自然地做到负载平 衡，而负载平衡正是传统网络长久以来无法解决的重大难题。在实现因特网p 2 p 系统时，可以通过一个统一的哈希函数将各机器的i p 地址哈希成为一个i d 号，在 保证i d 号不会重复且连续的情况下i d 号可以排序以形成环状结构，然后就很容易 能被c h o r d 进行各种操作。此外我们应用所需要的数据( 或文件等) 也同样使用 该函数进行哈希，然后根据结果将它存放在其后继节点上。这样，在进行数据查 找时仅需要查找该数据对应的后继节点就可以了。当c h o r d 环中的节点加入或者 离开时，c h o r d 环需要做自适应调整，对应节点中的数据也要进行转移等。关于 这段叙述中关键词的说明请参考附录。 举例说明，在8 节点环状结构的情况下( 节点为o 一7 ) ，节点0 并不需要保存 所有其他节点的路由信息。在他的路由表中，只需要保存k 0 9 2 ( n ) = 3 个路由入e l ( 此例中n = 3 ) 。这三个路由入口分别为0 + 2 “0 = 1 ，0 + 2 “1 = 2 ，0 + 2 “2 = 4 。所有的 节点也只需要依此类推，保存三个节点的路由信息。在节点0 寻找节点7 时，他先 发现自己路由表各项中小于7 并最接近7 的是4 ，然后就将查找7 的任务转交给节点 4 。4 的路由表项包括了5 ，6 和o 。在这三项中小于7 并最接近7 的是6 ，于是任务被 再次转移。在6 的寻找中成功发现了节点7 的存在，于是这一消息被一级级地向上 返回到节点0 ，就这样实现了任意两个节点的互动。如图2 1 所示 北京邮电大学硕= b 学位论文 采用c h o r d 协议实现分布式内存数据库系统的研究 2 2 2 与其它协议的比较 图2 - 1c h o r d 分布图 本节我们将比较一下c h o r d 协议与其它类似协议的不同，从对比中去总结 c h o r d 的优势。 d n s 8 j 提供了主机名对i p 地址的映射，而c h o r d 可以提供同样的服务。域名 可以被换作值，i p 地址可以被换作数据，这样就完成了值 数据( k e y v a l u e ) 的 映射。c h o r d 不需要请求任何的特殊服务器，而d n s 则依赖于根服务器。d n s 名 称这一结构反映了管理的范围，而c h o r d 去p 没有任何命名结构。d n s 是专门用来 寻找被命名的主机以及服务，而c h o r d 也能用来寻找不固定在特定机器上的数据 目标。我们提供的系统是完全分布式的，所以不能有专门的服务器，不能采用 d n s 协议。 f r e e n e t l 8 】又叫自由网，是一种分布式信息存储和搜索系统，像c h o r d 一样，是 一个非集中式的，系统化的而且能够在主机加入或者离开时自动适应的p 2 p 系 统。f r e e n e t 不把文档分配给专门的服务器，取而代之的是，它的搜索是用一种查 找c a c h e 昌l j 本的形式。这就允许f r e e n e t 提供一定程度的匿名。但是这个使得它不 能确保提取已经存在的文档或者可能会导致提取代价很大。c h o r d 不能提供匿名， 但是它的搜索操作可以在一个预期的时间内进行，而且能够成功或者是确定的失 败。由于我们的系统要求做到准确的数据访问，所以f r e e n e t 不适合使用。 p l a x t o n i 8 】很好的发展了分布式的数据位置协议，它提供了比c h o r d 更加强的 保证：像c h o r d 一样它保证了一个查询将产生对数级数量的段以及可以很好的平 8 北京邮电大学硕二卜学位论文采用c h o r d 协议謇现分布式内存数据库系统的研究 衡值的分布，但是p l a x t o n 协议还可以保证，根据网络拓扑的假设，查询距离从来 不会超过存储值的节点在网络中的距离。但是p l a x t o n 在构造时需要知道全局信息， 这会导致结点的加入和离开操作相当复杂。另外，每个对象的根结点实际上成了 一个单一失效点，如果该结点失效，则该结点保存的对象将有可能无法被访问到。 这些缺点和我们设计系统的初衷不负荷。 p a s t r y 9 】协议和c h o r d 协议类似，对网络中的每个节点都有一个唯一的节点号 ( n o d e i d ) ，当给定一条消息和一个关键字时，p a s t r y 节点将会把这条消息路由到 在当前所有的p a s t r y 节点中n o d e i d 矛l 关键字最接近的那个节点。路由过程的复杂 度是o ( 1 9 n ) ，这里n 是节点的总数。p a s t r y 考虑了网络的位置信息，它的目标是 使消息传递的距离最短。但是，p a s t r y 是一个基于前缀的路由协议，其查找服务 也没有c h o r d 简单，c h o r d 的优势在于它很简单而且能够很好的处理并发的节点加 入或者失败，而且我们的系统是在局域网内的，不用过多考虑网络位置的问题， 所以上述协议的优点对我们来说不明显。 c a n 9 j 用的是d 维c a r t e s i a n 坐标空间( 有时的d 是固定) 来实现一个分布式 h a s h 表，用来把值映射到数据上去。每一个节点维持着o ( d ) 个状态，每次搜索代 价是o ( d n “l d ) 因此，相对于c h o r d ，一个c a n 节点维持的状态不依赖于网络的 大d , n 。但是搜索代价增长的速度要快于l o g n 。如果d = l o g n ，c a n 搜索次数以 及存储需要都和c h o r d 一样。然而，c a n 不是专门为了随着n ( l o g n ) 变化d 才 变化而设计的，所以这种一样只是碰到了合适的n 才会发生，对应于固定的d 来 说。c a n 需要一个另外的维护协议来间隔性的把i d 空间重新映射到节点上去。 c h o r d 还有一个优势就是它的准确性是强壮的，尽管存在一些不正确的路由信息。 c a n 的操作虽然更为简单，但是其相邻节点之间需要周期性交换更新消息，系 统维护负载大。我们的系统读写数据频繁，所以对负载要求比较严格，从这个方 面来考虑c a n 也不适合。 2 2 3 系统使用c h o r d 协议的原因 由2 2 2 节我们知道，相比其它协议，c h o r d 协议更加适合我们的系统策略。 为此特地引入它，总结起来主要有以下几个原因，首先是为了解决在分布式内 存数据库【6 】中存在的三个问题。 ( 1 ) 系统负载问题 c h o r d 协议为我们构建了一个对等网络，网络上的各个节点的地位是平等的， 也就是传统意义上的p 2 p 系统。但是由c h o r d 组成的p 2 p 幂i 某些p 2 p 系统不同，比 9 北京邮电大学硕士学位论文 采用c h o r d 协议实现分布式内存数据库系统的研究 如美国著名的n a p s t e r 系统和宋平等人的分布式内存数据库【酬，它们依然使用 了中央索引服务器，保留着以往c s 的模型的特点，属于集中目录式结构。而c h o r d 却带来了一个完全没有中央控制和分层组织的系统，属于纯粹的p 2 p 系统。其中 没有哪一个节点比其他的节点更重要，而且对网络的访问不需要任何w e b j 艮务器 的支持。 另外，c h o r d 协议使用一致性哈希函数，与以往对等系统中的每个节点都可 以知道系统中所存在的其他大部分节点不同，每个在c h o r d 中的节点仅仅需要 知道其他少数节点的路由消息。一个n 个节点的系统在稳定状态的时候，每个节 点仅仅保持o ( l 0 9 2 ( n ) ) 个其他节点的信息，查询操作仅仅也需要发送 o ( l 0 9 2 ( n ) ) 条消息到其他节点【7 】。这就提供了一定程度上的负载平衡。对于我们 提出的分布式内存数据库来说，由于数据读写频繁，对硬件设备性能要求较高， 而c h o r d 的这个特性，可以为我们降低这个要求。 ( 2 ) 扩展性问题 每个节点并不需要维护整个网络的信息，同时又取消了泛洪算法。有效地减 少了节点信息的发送数量，从而增强了p 2 p 网络的扩展性。新节点的加入是系统 动态调控完成的，而且不需要进行任何参数的调整，这个特性也使我们的系统管 理变得更加容易，同时也丢掉了以往平台配置文件所带来的问题。 ( 3 ) 可靠性问题 c h o r d 自动调整它其中的路由表来反映新节点的加入或者节点的失败退出， 确保只要下层网络不发生错误，管理某个数据的节点总是能够被找到的。即使系 统的状态在不停的变化，这种有效性也是能够保证的。这样就抛弃了原有系统的 “队长”机制，或者可以简单认为c h o r d 的每个节点都可以起到“队长”作用， 这一点也大大提高了我们系统的可靠性。 另p l - c h o r d 协议还具有其它的优点，比如灵活的命名方式【1 0 1 ，c h o r d 没有对 数据设置任何的限制，在应用程序给数据设置自己所需要的名字时具有很大的灵 活性，同时我们也可以很方便地进行系统扩展。 由以上分析得知，c h o r d 协议为我们提出的系统带来了很多优势，而且它还 具有实现简单等特点，虽然目前由于拓扑维护和修复算法还不成熟，它只对于规 模较小的系统较为有效，但这点和我们设计应用目标的初衷也是相吻合的，我们 提出的分布式内存管理策略正是面向小型局域网，基于以上种种分析，我们决定 使用c h o r d 协议而不是其它的p 2 p 协议来进行底层管理，同时也很容易利用c h o r d 的各个节点作为实体来管理系统使用的数据。 1 0 北京邮电大学硕士学位论文 采用c h o r d 协议实现分布式内存数据库系统的研究 第三章系统设计 这一章介绍分布式内存数据库( d m d s ) 底层管理系统的设计方案。d m d s 的功能主要是提供给用户能够透明的使用局域网上的内存资源，在使用内存资源 的同时，用户还很容易做到系统的扩充。作为d m d s 的底层管理系统，在设计上 充分考虑了它的需求，并结合分布式内存结构与共享存储结构的优点，具有可扩 充性、通用性、方便性。本章的主要内容是系统结构的设计、针对应用需求的解 决方案、使用流程的设计等。 3 1 需要解决的问题 由2 1 1 节分析得知，分布式内存数据库是由一组数据组成的，这组数据分布 在计算机网络的不同计算机的内存上。每个网络节点是独立的数据库系统，它有 自己的数据库，运行自己的d b m s ( 数据管理) ，执行局部应用，具有高度的自 治性，同时又相互协作组成一个整体。这种整体性的含义是：对于用户来说，一 个分布式数据库系统逻辑上看如同一个集中式数据库系统一样，用户可以在任何 一个场地执行全局应用。 作者参与的是整个数据库的底层管理系统，主要是使用c h o r d 协议来构造一 个分布式管理网络，该网络具有完全p 2 p ( p e e rt op e e r ，点对点) 特性，并且满 足了上层应用对底层的功能需求，主要是有关底层网络节点的操作接口( 具体设 计请参考3 2 2 节) 。另外，上层应用对底层管理系统提出了严格的性能要求，总 的来说主要有三点：( 1 ) 负载均衡( 2 ) 可扩展性好( 3 ) 可靠性高。这三点要 求是传统意义上分布式数据库系统所必须具有的特点，同时也解决了以往平台存 在的问题。 3 2 解决方案 针对以上应用要求，我们设计了系统的实现策略，下面将首先阐述系统的设 计思想，然后重点介绍如何使用c h o r d 协议来解决问题。 北京邮电大学硕士学位论文 采用c h o r d 协议实现分布式内存数据库系统的研究 3 2 1 系统结构设计 整个底层系统设计的目标是实现c h o r d 协议并提供应用接口，为了达到这一 点，我们对底层系统按照功能进行了层次划分，各个层次相对独立。系统层次结 构如图3 1 所示： 应用接口层：提供上层应用 所调用的接口，使用下层服 务层提供的功能。 1 l 服务层：完成数据映射、消 息解析、查询服务等功能 一 1 r c h o r d 层：实现c h o r d 协议： 节点的加入、离开、搜索等 1r 网络层：底层使用t c p i p ( s o c k e t ，流) 图3 - 1 系统层次图 各个层次实现的功能如下：( 1 ) 应用接口层，主要是提供给上层应用接口； ( 2 ) 服务层，完成系统的各种功能，比如查询服务、节点加入服务等。另外， 在该层上很容易针对不同应用开发出新的服务功能，使系统具有良好的扩展性； ( 3 ) c h o r d 层，用来构建底层的c h o r d 网络；( 4 ) 网络层，完成系统的通信功能。 关于各层的详细设计请参考3 2 3 节 对整个系统进行层次划分主要是由于以下原因：( 1 ) 在实现中用到的协议 和算法都封装起来，可以随时替换，以实现系统的高灵活性和易维护性的特点。 ( 2 ) 对应用接口层、服务层功能的增减不会影响底层网络的构建，同样底层的 改变也不会触及上层服务，这样可以使整个系统不仅满足论文设计的应用要求， 也很容易在它上面做其它的开发应用，具有良好的可扩展性。 1 2 北京邮电大学硕二l ：学位论文 采用c h o r d 协议实现分布式内存数据库系统的研究 值得说明的是，我们提出的分布式内存数据库系统是整个小组合作开发完成 的，作者负载的是底层的管理和实现部分，所以与上层应用就存在一个接口，这 个接口就是作者提出的应用接口层，这样其它小组成员在使用本系统时，可以忽 略底层的实现部分，而只关心这个接口。 基于以上思路，系统的体系结构图如下图3 2 i 。一一一。一。一一一一一一。一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一i 二二二二二二二二二二二二二二二二二二二二彳 li ：，一一w | 、 l 局域网系统 l ： ，一i 一一一i、l _ j 图3 2 系统结构图 其中整个系统的重点在于c h o r d 层和服务层上面，c h o r d 层按照我们优化过的 c h o r d 协议来实现，它的通信功能是由网络层封装好的t c p i p 模块提供( 该模块 使用s o c k e t 实现，使用服务层提出的消息概念) ，而服务层则是提出各种服务实 体，对消息进行解析然后进行相应处理。 3 2 2 应用接口设计 使用简单是许多系统的设计目标，具有这一点可以使系统应用的更加广泛。 在此，我们设计了应用接口层。设计该层的目的就是解决与上层应用交互的问题， 使整个底层的管理对于上层来说是透明的。 具体设计要求如下：能够为上层应用提供接口a p i ，系统使用者只需要直接 1 3 园团 北京邮电大学硕士学位论文采用c h o r d 协议实现分布式内存数据库系统的研究 调用就完成节点的加入、离开、查询、更新操作。该接口屏蔽了系统的细节问题， 可以直接和系统的服务层交互，间接通过c h o r d 层找到需要的数据节点。下表是 接口的详细说明。 编方法 方法参数 号 1 节点添加j o i n 节点的添加动作j o i n ( j o i n ，ie1d s u ci ds u c f i n g e r ) 参数：节点在完成加入操作后，提供如下参数值， i o i ni d 保存当前节点的标识符；s u ci d 、s u ci p 分别保存返回其后继节点的标识符及地址； f i n g e r 保存路由表信息 返回：0 表示操作成功，1 表示操作失败 2 节点离开l e a v e 节点的离开动作l e a v e ( ) 参数：无 返回：o 表示操作成功，1 表示操作失败 3数据查找 数据查找s u c c e s s o r ( s t r i n gr e q u e s t，ids t r i n g s u c c e s s o r r e p l y _ i d ，s t r i n gr e p l y _ i p ) 参数：r e q u e s t 表示用于查找的数据名称，操id 作完成后提供如下参数，r e p l y保存数据所在id 节点标识，r e p l y 保存该节点地址id 返回：o 表示操作成功，1 表示操作失败 备注：此方法也可以用于节点后继的查找 4节点 更新节点更新s t a b i l i z a t i o n( f i n g e rf i n g e rt a b l e n o d e u p d a t e f i n g e r n o d e 】s u c c e s s o r l i s t ) 参数：操作完成后提供如下参数，f i n g e rt a b l e 保 存更新后的路由表信息，s u c c e s s o rl i s t 保存更新 后的后继列表信息 返回：0 表示操作成功，1 表示操作失败 5 哈希函数h a s h 哈希函数h a s h ( s t r i n gs o u r c e ，s t r i n gi d ) 参数：s o u r c e 是需要进行h a s h 操作的原属性值， l d 保存了哈希后的结果 返回：0 表示操作成功，一1 表示操作失败 表3 - 1 与上层接口说明 其中关于各个方法的详细设计我们将在下面几节详细介绍，在此不再重复。 3 2 3 解决系统负载问题 负载问题是许多管理系统所必须重点考虑的问题之一。为了提高系统的效 率，在我们提出的分布式内存管理策略中，引入了c h o r d 协议，该协议为我们搭 1 4 北京邮电大学硕士学位论文采用c h o r d 协议实现分布式内存数据库系统的研究 建了一个具有完全p 2 p 特性的网络平台，这样可以将系统的负载平均分配到各 个节点上。为此主要有三个方法： 3 2 3 1 一致性哈希函数 我们使用c