（计算机系统结构专业论文）高性能高可用键值存储系统的设计与实现.pdf

u1 i j 3 鑫l 爪0 ， i k f 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 ” 签名： 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：丝幽导师签名： e t 期萨州年兮月冲日 k i k ，： 毛 嘣 摘要 摘要 2 l 世纪初期，互联网进入了一个全新的发展高峰期。数据量以指数增长，提 高对海量数据的管理、访问能力的需求变得越来越迫切。海量的数据和巨大的用 户数量对存储资源和计算资源的可扩展性提出了巨大的挑战。传统的关系型数据 库系统并不能提供这些应用所需要的高可扩展性。一种新型的、存储非关系型数 据的、具有高可扩展性的键值存储系统应运而生。本文首先介绍了研究背景。其 次，分析了分布式文件系统、p 2 p 系统与键值存储系统相关的关键技术。最后， 设计了一个高可靠、高扩展性、高可用的键值存储系统k v - s t o r e 。k v - s t o r e 具有 的基本特征或创新点： 第一基于改进的一致性哈希算法的数据分散算法，该算法成功地解决了基本 的一致性哈希算法和d y n a m o 使用的数据分配算法存在的热点问题、数据分散和 集群拓扑的紧耦合问题、存储节点的异构性问题。 第二基于p g 划分的负载均衡算法。使用哈希算法进行数据分散的一个根本 缺点是这种映射关系是不可改变的。映射关系不能改变直接导致了数据的位置不 能根据系统的负载进行动态的改变，所以一旦系统出现热点或负载失衡将束手无 策。k v - s t o r e 使用了哈希算法进行数据分散，同时也创造性的实现了动态的负载 均衡算法。 第三基于c h u b b y 的消息传输和集群管理。c h o r d ，b t 等p 2 p 系统通过复杂 的路由和查询协议进行消息的传输，k v - s t o r e 使用c h u b b y 的改进版进行集群管 理和消息的快速传输。 第四k v - s t o r e 使得元数据和数据彻底解耦合。与传统的文件存储系统不同， k v - s t o r e 使用哈希规则来联系数据和其对应的元数据。系统进行数据迁移，查找 时不需要进行资源的检索，而是自己计算得出。在k v - s t o r e 中只存在很少量的元 数据信息。 最后k v - s t o r e 是用e d a n g 程序语言进行实现的。e r l a n g 是一个函数式编程语 言，该语言的特性是易于分布式编程，程序设计简单，实现相同功能的代码量大 约是c + + 语言代码量的四分之一。 关键字g 键值存储，一致性哈希，数据分散，负载均衡 丫i 越 l ； 也 s c a l a b i l i t yt h e s ea p p l i c a t i o n sn e e d t h e nan e w ：n o n - r e l a t i o n a l ，h i g h l ys c a l a b l e k e y v a l u es t o r a g es y s t e mw a sb o r n f i r s t l y ，t h et h e s i s i n t r o d u c e st h er e s e a r c h b a c k g r o u n d s e c o n d l y , t h et h e s i sa n a l y z e st h ek e yt e c h n o l o g i e so f d i s t r i b u t e df i l e s y s t e ma n dp 2 ps y s t e mb e i n gr e l a t e dt ot h ek e y v a l u es y s t e m f i n a l l y , t h et h e s i s d e s i g n e dah i g h l yr e l i a b l e ，h i g h l ys c a l a b l e ，h i g h l ya v a i l a b l es t o r a g es y s t e m - - k v - s t o r e 啊1 eb a s i cc h a r a c t e r i s t i c so ri n n o v a t i v ep o i n t so fk v - s t o r ea l ea sf o l l o w s ： f i r s t l y , t h ed a t ad i s p e r s i o na l g o r i t h m , w h i c hs o l v e dt h eh o ti s s u e s ，h e t e r o g e n e o u s ， t i g h t l yc o u p l i n gb e t w e e nd a t ad i s p e r s i o na n dt h ec l u s t e rt o p o l o g yt h a te x i s t si n d y n a m oa n df u n d a m e n t a l c o n s i s t e n t h a s h i n ga l g o r i t h m i sb a s e do ni m p r o v e d c o n s i s t e n th a s h i n g s e c o n d l y , 1 1 1 ek v - s t o r en o to n l yu s e st h eh a s ha l g o r i t h mf o rd a t ad i s t r i b u t i o n ，b u t a l s oa c h i e v e dl o a db a l a n c i n gb a s e do nt h ep a r t i t i o no fp gw h i c hd i dn o te x i s ti n t r a d i t i o n a ls y s t e m sb a s e do nh a s ha l g o r i t h mf o rd a t ad i s t r i b u t i o n t h i r d l y , t h em e s s a g et r a n s m i s s i o ns y s t e mo fk v - s t o r ei sb a s e do nt h ec h u b b y , w h i c hi sd i f f e r e n tf r o mt r a d i t i o n a lp 2 ps y s t e m st h a tu s eg o s s i p ，c h o r d ，e t c f o u r t h l y , k v - s t o r em a x i m i z e st h es e p a r a t i o no ff i l em e t a d a t am a n a g e m e n tf r o m t h es t o r a g eo fd a t ao b j e c to rp g s o n l yaf e wm e t a - d a t ae x i s t si nt h es y s t e m f i n a l l y , k v - s t o r ei s a c h i e v e db ye r l a n gp r o g r a m m i n gl a n g u a g e e r l a n gi sa f u n c t i o n a lp r o g r a m m i n gl a n g u a g e ，w h i c hm a k e sd i s t r i b u t e dp r o g r a m m i n ge a s i e ra n d s i m p l e r 耶1 ea m o u n to fc o d eo fc l a n ga c h i e v i n gt h es a m ef u n c t i o ni saq u a r t e ro fc - h - c o d e k e yw o r d ：k e y v a l u es t o r a g e ，c o n s i s t e n th a s h i n g ，d a t ad i s p e r s i o n , l o a db a l a n c i n g h o f 糊 丫f 融 l 第一章引言 l 1 1 研究背景1 1 2 数据管理技术面临的新挑战“3 1 3 本文的工作和创新山4 1 4 本文的内容和组织。5 第二章相关技术和系统 2 1 2 1 1 2 1 2 2 2 2 2 1 2 2 2 2 3 2 3 1 2 3 2 分布式文件系统6 谷歌文件系统( g f s ) 。7 c e p h 文件系统9 p 2 p 系统】【l p 2 p 网络分类1 l p 2 p 技术总结16 键值存储系统16 键值存储系统的特点1 6 键值存储系统的分类1 7 本章小结2 0 系统设计。二 k v - s t o r ej 1 9 e j 21 系统假设和需求：2 2 设计原则：2 3 系统接口2 4 系统架构2 4 组件功能2 5 关键技术：2 6 读写流程：2 6 数据划分o 2 7 基本的一致性哈希算法。2 7 ： i i i 章 他 记 驰矧 她”拊 目录 异构性的一致性哈希算法2 9 k v - s t o r e 的数据划分算法。3 0 数据划分算法小结3 3 数据存储和冗余3 4 典型冗余策略3 4 k v - s t o r e 系统的冗余算法3 5 集群管理3 9 k v - s t o r e 的通信模型4 0 集群管理器的主要功能4 l 节点失效和节点添加4 3 数据一致性4 4 读写模型4 4 冲突处理；尚- 。j 。：j 4 6 异常处理4 8 i f 6 i 时失效4 8 永久失效。4 9 基于p g 划分的负载均衡算法4 9 本章小结51 系统实现 4 1 存储节点组件的实现5 2 4 2 集群管理器的实现5 3 4 3试验结果与结论分析5 4 4 3 1 读写时延5 4 4 3 2 负载均衡仿真j 5 5 4 3 3p g 分布仿真5 6 4 4 本章小结5 7 第五章结论和展望 致谢 参考文献 攻硕期间取得的研究成果 i v 6 3 i 。 f 湖 v 2 3 4 1 2 l 2 3 l 2 l 2 讹粥川5 jii抛石姗撇姗7川抛名姗量|9加醇 3 3 3 3 3 3 乳 k 第一章引言 第一章引言 1 1 研究背景 2 l 世纪初期，伴随着w e b 2 0 的兴起，互联网进入了一个全新的高速发展期。 互联网的不断发展使得基于非关系型数据的应用不断涌现。与此同时，用户的参 与和交互程度空前提高。w e b 2 0 时代是以用户为主的时代，然而海量的用户和数 据内容使得单个计算机节点远远不能满足应用程序所需要的存储空间和计算资 源。传统的o s 服务模型在应对海量数据的存储与查询以及用户对资源的可扩展 需求的快速变化时，局限已经越来越明显。p 2 p ( p e e rt op e e r ) ，分布式计算 ( d i s t r i b u t e dc o m p u t i n g ) ，并行计算( p a r a l l e lc o m p u t i n g ) ，网格计算( 西dc o m p u t i n g ) 等概念相继出现。这些新技术的都在一定程度上满足了用户增加、数据爆炸对计 算、存储资源的巨大需求。但问题并未得到根本解决，i n t e m e t 中的数据仍然是呈 几何指数增长，用户的规模不断扩大，应用也越来越多样化和多元化。据中国互 联网信息中心第2 3 次中国互联网络发展状况统计报告显示，截至2 0 0 9 年底，中 国网民规模达到3 8 4 亿人，较2 0 0 8 年增长2 8 9 ，在总人口中的比重从2 2 6 提 升到2 8 9 ，互联网普及率在稳步上升【l 】。 图1 1 中国网民规模与增长 虽然我国网民的数量和互联网的普及率都在持续的提高，但是和发达国家相 比还有很大的差距，中国的互联网普及率还较低。图1 2 显示了我国和发达国家 互联网普及率的差距。截至2 0 0 9 年1 2 月，美国、日本和韩国互联网普及率分别 达到7 4 1 、7 5 5 和7 7 3 ，我国的互联网普及率仅仅为2 8 9 ，还有很大的增 ： l f 4 电子科技大学硕士学位论文 长空间。与此同时，全球的i n t e r n e t 用户增长潜力巨大【1 1 。 图1 之2 0 0 9 1 2 部分国家的互联网普及率 噜1 用户数量和数据量的增加使得问题接踵而来。首先，对存储资源和计算资源 的需求越来越强烈。其次，互联网中的各种应用都需要计算和储存资源的可扩展 性，分别维护各个应用程序的存储、计算资源的成本不断上升。在对存储和计算 资源的可扩展需求和成熟的技术条件的推动下，一种新的计算模式云计算出 现了。 虽然目前没有一个对云计算的准确和统一的定义，但总的来讲，云计算使用 户不再关心系统的扩展性和繁重的维护任务，而是专注于应用程序本身，这大大 的加快了应用程序的开发速度和降低了成本。 如同文件系统和数据库系统在计算机系统中的重要性一样，数据存储与数据 管理技术也是云计算的核心。存储和计算既是独立的又是相互依赖的，在计算模 式发生了巨大的变化后，必然会产生与之对应的数据存储技术、数据管理技术。 云计算是一种新型的超级计算方式，以数据为中心，是一种数据密集型的超级计 算【2 】，这将促使现有的存储技术和数据管理技术向海量、高访问量、高性能以及 低成本方向发展。 目前，分布式数据存储技术和数据管理技术发展迅速。g o o g l e ，i b m ，a m a z o n 等公司都开发了适合自身业务需求的系统并且发表了相关论文，这对本文的研究 具有重大的参考价值。随着信息爆炸和人们对数据管理技术要求的日渐提高，数 据存储和数据管理技术将会有巨大发展。 基于如上分析，具有可扩展性的云计算模式是未来的发展方向。作为其关键 技术的存储技术和数据管理技术是云计算的核心之一。新的数据管理技术和数据 2 ( a 第一章引言 存储技术都必须具有很强的可扩展性，可管理性。 1 2 数据管理技术面临的新挑战 2 0 世纪6 0 年代，数据的增长使得人工管理数据越来越复杂，这时迫切需要 一个有效的数据管理系统。尽管当时人们都开始用计算机对数据进行管理，但是 那时的管理机制还不够自动化，并且非常繁杂，不能满足人们对数据有效管理和 共享的需求。基于传统文件系统的简单数据管理模式走到了尽头，新的数据管理 系统如雨后春笋一般大量涌现。1 9 7 0 年6 月，关系数据模型首次被提出【3 】。由于 关系数据模型简单、实用，很好的满足了人们对数据管理的需求，所以很快便在 数据管理市场占据了重要地位。传统的关系型数据库系统将复杂而繁琐的数据管 理细节封装在关系模型中，简化了数据管理和不同层次的数据共享，是数据管理 技术上的一个重大进步。目前，关系数据库系统正广泛的应用于互联网，政府机 关，学校，军队，企业等场所。 现在，传统关系数据库的地位正受到多方面的挑战。首先，随着互联网的快 速发展，越来越多的基于非结构化数据内容的应用日趋广泛，这些应用对传统关 系数据库的一些特性并不关心。其次，海量数据的产生对关系数据库系统的存储 和快速访问能力构成了巨大压力。在这些环境下，关系数据库遇到了前所未有的 压力，并且缺少满足这些需求的关键功能和能力： 第一缺乏对海量数据的高并发读写能力。传统的关系数据库具有简单，共享 方便，易于管理这些优点，但是由于其基于的单节点结构和其系统特性，系统的 并发读写性能远远不能达到一些海量数据处理系统所需要的要求。一般的关系数 据库系统对于上万次的并发读还可以承受，但对于上万次的并发写是不可想象的， 这主要是受限于计算机节点的硬盘吞吐量。特别是在w e b 2 0 时代，内容都是用户 产生的，用户的页面具有个性化和动态性，使得缓存技术不能充分利用，这进一 步增加了关系数据库的负载压力。 第二缺乏对海量数据的高效率存储和访问的能力。今天，腾讯，盛大等联网 公司的系统中包含了数以亿计的账号信息，如果这些信息存储在关系数据库的一 张表中，那么在这张巨大无比的表中进行数据读写的效率是极其低下的。现在， 随着互联网的发展，这样的应用系统会越来越多，对海量数据的高效读写需求会 持续增加。 第三缺乏高可扩展性。互联网应用对存储和计算资源的可扩展需求增长十分 3 电子科技大学硕士学位论文 强烈。这种基于互联网的应用程序对可扩展性的需求有两个主要特点：需求的变 化十分迅速并且十分庞大，例如一个网站最开始的并发访问量可能只有1 0 0 0 0 ， 但由于突发需求或业务的迅速发展，并发访问量可能会成倍的增长。由于单个计 算机节点的限制，传统关系数据库系统的可扩展性局限于单个节点上的逻辑扩展， 并不能在计算能力、存储资源上进行扩展，而这是互联网应用程序的核心需求。 第四缺乏对海量数据访问的灵活性。关系数据库在方便数据管理的同时，也 固定了数据存储，查询的模式，这使得用户不能进行一些灵活的可，定制的查询 方案。 第五缺乏对非结构化数据处理能力。传统的关系数据库存储的数据类型主要 是数字、字符等，对视频，声音等数据类型只能进行简单的二进制格式存储，缺 乏对这些数据的处理能力。 第六缺乏有效的容灾与备份机制。传统的关系型数据库的备份方案具有复 杂，时间长，难度大等特点，特别是在海量数据环境下，这些问题更加难以忍受。 另外，海量数据的安全性问题也是一个重要需求。 与此同时，关系数据库的很多主要特性却不能在海里数据环境中、非结构化 数据的存储和处理上发挥令人满意的作用，例如： 第一数据库的事务一致性。现在很多基于互联网的应用对一致性的要求越来 越低，这使得传统的关系数据库中的事物一致性并不能发挥有效的作用，反而成 了限制系统性能的瓶颈。 第二数据库的实时读写功能。关系数据库严格遵守了读写实时性，这使写入 的修立刻就能看见。但在当前的一些典型互联网应用中，该特性并不需要。 第三基于关系表的复杂s q l 查询。在基于海量数据的互联网应用中，数据 的查询基本是基于主键的查询；传统的s q l 复杂查询没有了用武之地。 随着非结构化数据的应用越来越广泛，针对海量非结构化数据的数据管理技 术现在是一个新的研究领域。非关系型的数据管理技术摒弃了传统关系数据库系 统中的一些关键特性，如严格的事务一致性，读写实时性等，这使得非关系数据 管理技术充分利用了分布式，并行计算的优点，专注于非结构化数据存储、系统 可扩展新、可靠性等。 1 3 本文的工作和创新 本文总结了数据管理技术的发展历程、现状、和未来趋势，并在此基础上， ：4 l - 巫 k 第一章引言 深入全面的研究当前相关技术和系统，设计了一个具有高可用、高扩展性的键值 存储系统。本文的主要创新和工作如下o 第一设计一个具有高可用性、可扩展性的键值存储系统架构。该架构适用于 封闭的集群系统中。 第二设计了一种新型的基于一致性哈希( c o n s i s t e n th a s h i n g ) t 4 1 的数据分散算 法。该算法是本文的主要创新点。 第三设计了一种基于p g ( p l a c e m e n tg r o u p ) 划分的系统动态负载均衡算法。 这是本文的第二个重要创新。 第三引入c r u s h t 5 】函数，使得数据存储和元数据信息彻底解耦。这是本文 的一个特点。 第四使用了m e r k l et r e e ，最终一致性，副本冗余等技术解决分布式系统的 关键问题。 第五实现一个基于e r l a n go t p 平台的一个简易原型系统。 1 4 本文的内容和组织 本文共分为五章，各章的工作内容如下： 第一章为引言。首先介绍了数据存储技术的发展过程，现状和将来的趋势。 接下来介绍了本文主要工作和内容组织。 第二章为相关技术和系统介绍。首先介绍了分布式文件系统，p 2 p 系统的路 由、查询技术，以及当前典型的相关的键值存储系统。 第三章为k v - s t o r e 系统的详细设计。本章详细介绍了系统框架，集群管理， 副本冗余，数据一致性，数据划分算法，负载均衡等解决方案。重点介绍了本文 的创新点和特色：改进的一致性哈希算法，负载均衡算法，集群管理结构，数据 分散映射算法等。 第四章为k v - s t o r e 实现时的一些细节。包括存储节点组件、集群管理器组件 的实现细节，以及实验结果分析等。 第五章为结论和展望。本章对本文的工作做了一个总结，并对今后系统的发 展方向做了展望。 5 电子科技大学硕士学位论文 第二章相关技术和系统 2 1 分布式文件系统 如同文件系统一样，键值存储系统也涉及到数据存储，数据查找定位，以及 数据的读写等关键技术。所以传统文件系统特别是分布式文件系统的体系结构、 发展历史对键值存储系统的设计都有一定的参考价值。本节将介绍文件系统的发 展历程，分布式文件系统的典型技术等。在这些技术中，分片技术、文件分散技 术、负载均衡技术、可靠性技术等对本文的研究都有很大的启发作用，特别是基 于哈希函数的文件分散技术被使用于本课题设计的系统中。 最初的文件系统只存在于单个计算机节点上，其主要目的是管理本地的存储 设备如磁盘、磁带等，同时为用户提供访问接口。这种文件系统被称为本地磁盘 文件系统。本地文件系统局限于单个节点的数据管理，并且在各个计算机节点之 间没有统一的访问接口。 随着互联网的迅速发展，对各个计算机节点间的数据传输与共享需求越来越 强烈。最先出现的n f s ( n e tf i l es y s t e m ) 将一台服务器上的磁盘提供给远程用户访 问，：用户可以像操作本地硬盘一样操作另外一台服务器上的文件，而不用知道文 件存储在哪台服务器上。n f s 是一种简单的网络文件系统，在很长的时间内被广 泛的使用。 随着互联网对海量数据存储要求的提高，基于单个计算机节点的存储模式的 局限越来越明显。联网上的数据量越来越大，单个文件的大小也在快速增加。一 些文件在普通的计算机节点上根本无法存储，即使一些能存储在单个节点上的大 文件，系统吞吐量也极其低下。基于分片的文件存储系统将一个大文件分割成很 多小文件进行单独存储，这种技术使得一个文件各个部分的数据可以分散在多个 计算机节点上。分片技术使得多用户可以并行的访问文件的各个部分，系统吞吐 量得到提高，避免了性能瓶颈。 对于如何将文件的各个分片数据映射到存储节点，实现数据分片的均衡分布 和系统的负载均衡时，主要存在两种技术：( 1 ) 基于文件映射表的分散存储。该 方式为每个文件保存一个元数据表，元数据表的内容即为文件各个分片到存储节 点的映射关系。( 2 ) 基于哈希函数的随机分散方法，该方式不需要保存元数据表， 6 妒 】 k 第二章相关技术和系统 只要知道文件的相关信息即可计算出文件数据的所在位置，该技术完全避免了定 位表的存在。据统计，元数据操作占据了文件系统一半的工作负载【6 】，特别是元 数据存储在一个中心节点上时，基于定位表的寻找方式很容易成为系统性能的瓶 颈。使用哈希函数映射的方式使得文件分片在概率上均匀分散开了，但由于这种 映射关系是不可改变的，这使得系统在运行过程中可能出现热点问题。 拥有多个存储节点的分布式文件系统中，存储节点出现故障的概率大大增加， 一旦计算机节点失效就会导致一些数据不可用甚至导致系统不可用。为了保证系 统的可靠性，分布式文件系统使用了副本冗余技术，即将数据或分片冗余存储在 多个节点上。一旦节点失效后，文件的各个部分和系统仍然可用。 在当前具有较大影响和比较流行的文件系统是g f s ( g o o g l ef i l es y s t e m ) i s ， c e p h 1 0 1 ，o c e a ns t o r e 7 ，h a d o o p 9 1 等。本文将对当前最流行的文件系统g f s 和 最具特色的文件系统c e p h 进行简要介绍，深入分析其数据分散技术，数据定位 技术，可靠性技术，负载均衡技术等，这些技术对本文研究的键值存储系统具有 重要价值。 2 1 1 谷歌文件系统( g f s ) g f s 是著名搜索服务提供商谷歌公司开发的一个满足自身应用需要的分布 式文件系统。谷歌公司的背景决定了g f s 是一个适合大规模数据处理以及相关应 用的文件系统。g f s 仍然关注可伸缩性、性能、可用性以及可靠性等，但是g f s 的应用场景和设计目标也与传统文件系统有很多不同的地方： 第一专用的大型服务器是非常昂贵的，对于谷歌公司的海量数据和庞大用户 数来说，这是难以承受的成本。g f s 在设计时就考虑在廉价的常规硬件上架构集 群。所以在这种廉价硬件组成的集群中，节点失效是正常现象或平常的事情。 第二谷歌公司的数据业务还有一个特点，那就是其产生的数据文件是巨大 的。这些文件大小通常以g 字节计。 第三谷歌的数据应用对文件的读写模式与传统文件系统不同。谷歌公司的应 用( 如搜索) 对文件数据的修改主要是在文件尾部添加数据，而不是传统的对文 件原数据的修改。 图2 1 给出了g f s 的系统框架，一个g f s 集群包含一个主服务器( m a s t e r ) 和多个块服务器( c h u n ks e r v e r ) ，系统可同时被多个客户端访问。一个文件被分 割成固定大小的块( c h u n k ) 。在每个块都由一个全球惟一的、不变的6 4 位块旬柄 7 电子科技大学硕士学位论文 对它进行标识。块服务器( c h u n ks e r v e r ) 把块作为一个普通的文件保存在本地硬 盘上，并根据指定的块旬柄和字节范围来读写块数据。为了保证数据的可靠性和 可用性，每个块都会冗余存储到多个块服务器( c h u n ks e r v e r ) 上，缺省保存三个 备份。 图2 - 1 谷歌文件系统架构 主服务器( m a s t e r ) 管理文件系统所有的元数据，包括名字空间、访问控制 信息和文件到块的映射信息，以及块到计算机存储节点的映射关系( 定位表) 。 g f s 客户端代码实现了g f s 文件系统的a p i ，帮助应用程序与主服务器和块 服务器通信，对数据进行读写。 客户端跟主服务器( m a s t e r ) 交互进行元数据操作，但是所有的数据读写操 作的通信都是直接和块服务器( c h u n ks e r v e r ) 进行的。客户端提供的访问接口类 似于p o s 接口。 如同a f s t l l l 样，g f s 提供了一个与文件数据具体位置无关的名字空间，这 使得系统可以根据需要对数据进行迁移。由于r a i d 1 2 】比较复杂和磁盘存储介质 的价格比较低，g f s 只使用了副本冗余的方式保证数据可靠性和可用性。与 m i n n e s o t a sg f s 1 3 1 ，g p f s 1 4 1 不同，g f s 并没有采用去中心化的架构，这样做的动 机主要是考虑到系统的简单和可扩展性。 尽管随机读写性能较差，中心化的架构容易存在性能上的瓶颈，g f s 仍然是 当前分布式文件系统的主流。由于g f s 不是开源系统但具有广泛的应用前景，很 多开源组织或公司都按照g f s 的论文进行了相关系统的设计，比较著名的有 h a d o o p ，h y p e r t a b l e 1 5 】等。 在本文的研究中，g f s 的体系结构，文件分片寻址，可扩展性，可靠性，负 载均衡等的设计思路都是值得本文参考的重要材料。 8 ， 目 i h 第二章相关技术和系统 2 1 2c e p h 文件系统 c e p h l l o 】是一个关注可扩展性、可靠性和高性能的分布式文件系统。在c e p h 中，可扩展性被认为是多维的，包括存储容量，系统吞吐量，性能等。c e p h 是 一个完全分布式的文件系统，他不存在中心节点。c e p h 不仅将数据分散在各个 节点上，而且元数据也被分散到多个节点上。这样对数据的读写，元数据的操作 负载都分散到了系统中的各个节点上。 c e p h 避免了中心节点带来的单点失效问题，同时也提出了一种新型的数据 分散算法c r u s h 。c r u s h 算法具有可扩展性强、灵活等优点，可以配置成各种 规模的集群。由于使用了哈希方法进行数据的分散，所以c e p h 没有定位表，只 有少量的元数据信息。c e p h 也实现了良好的数据备份机制，系统的可靠性较高。 该系统的三大基本特征如下： 第一彻底解耦数据和元数据。c e p h 最大化的分割元数据和文件数据的关 系。c e p h 彻底的根除了定位表，取而代之的是将文件分为可通过规则获得名字 的对象，通过伪随机函数c r u s h 将对象分散到存储设备上。这样用户不用再查 阅定位表，而是直接计算数据的位置。该设计简化了系统设计，避免了元数据管 理的瓶颈。系统中文件到o s d 的映射关系如图2 - 2 。 ( i n o i q n o ) _ 0 i d ，m a s k , - p g i d ( o s d l ，o s d 2 ) 图2 - 2 文件到o s d 的映射流程 第二动态元数据管理。据统计分布式文件系统的元数据操作占据了大约一半 的工作负载嘲。有效的元数据管理是提高系统性能的关键。c e p h 使用了一种新 的基于动态子树划分( d y n 砌cs u b t r e ep a r t i t i o n i n g ) t l q 的集群架构。该方案可自适 应的管理元数据，避免热点问题。 9 电子科技大学硕士学位论文 第三基于可靠的对象存储设备( o s d ) 的存储方案。o s d 负责对文件数据 内容的分块存储，寻址访问等。使得系统上层设计简单。o s d 与传统的基于块的 存储设备有所不同，二者之间的对比如图2 3 所示。由图可见，对象存储设备屏 蔽了一些繁琐的底层操作，简化了接口。 t o d a y sb l o c ko b j e c ts t o r e d e v i c e o p e r a t i o n s m a db l o c k w t r i t eb l o c k s e c u r i t y w e a k f u h d i s k a i i o c a t i o n e x t e m a l 0 p e r a t i o n s r e a do b j e c to f f s e t w n t eo b j e c to f f s e t c r e a t eo b j e c t d e l e t eo b j e c t s e u g e ta t t r i b u t e s e c u r i t y s t r o n g p e r o b m a i l o c a t i o n l o c a l 图2 3 对象存储设备与传统存储设备异同 c e p h 系统包含了三个系统组件：( 1 ) 提供p o s i x 接口的客户端程序，负责 处理上层用户的命令和与系统进行元数据操作和数据下载。( 2 ) 对象存储设备集 群( o s d s ，o b j e c ts t o r a g ec l u s t e r ) 集群，负责存储数据和副本冗余。( 3 ) 元数 据管理集群( m s ，m c t a d a t as t o r a g e ) ，负责对数据的元数据进行管理。图2 - 4 给 出了c e p h 的系统架构。 ： c l i e n t s m e t a d a 一t a c 1 u 一s t e r 图2 - 4 c e p h 架构图 其中元数据管理集群( m s ，m e t a d a t as t o r a g e ) 负责管理系统元数据，包括文 件名、文件属性、目录层次等。元数据可以根据m s 的负载状况在m s 之间进行 迁移。动态子树划分算法保证了系统中元数据负载分布的动态适应性。 o s d 负责对数据对象的读写和数据的迁移等功能。由于数据是根据c r u s h 算法进行数据分散，o s d 实现了智能数据备份，o s d 进行副本恢复等操作不需要 与元数据进行交换操作，而是只需要获取集群状态的变化即可，即o s d 可以根据 1 0 ， t 、 第二章相关技术和系统 c r u s h 函数自己计算出对象的存储序列，直接与相应的存储设备进行数据传输 任务。 需要指出的是，c e p h 并没有实现文件数据的动态负载均衡功能，这是c e p h 的一个小小的遗憾。 总而言之，c e p h t 5 】是一个很有特色的文件系统，其主要贡献在于解耦了数据 和元数据的管理，根除了定位表。其次c e p h 使用哈希的方式实现了数据分散、 划分的方式也具有很大的参考价值。 2 2p 2 p 系统 p 2 p ( p e e r - t o - p e e r ) 网是一种具有较高扩展性的对等网络体系结构。对等概念 是指网络中的计算机节点在逻辑上具有等同的地位，而实际的物理结构，如技术 能力、配置状况等可能有差异。与传统的客户朋艮务器( c s ) 模型相比，p 2 p 网络弱 化了服务器的概念，在p 2 p 网络中的每一个节点既可以作为客户进行请求操作也 可以作为服务器提供各种功能。p 2 p 网络的这种特性使得系统中的计算处理任务 十分分散、避免了中心节点的存在，同时系统的处理能力大大提高。 本文研究的键值存储系统也借鉴了p 2 p 网络的对等思想，系统中的存储节点 之间就是完全对等的。由于p 2 p 网络使用范围的特殊性和其本身的一些特殊性， 键值存储系统无法完全照搬其设计。p 2 p 系统主要涉及资源放置、资源定位、资 源获取三项关键技术。本文将对p 2 p 的这些技术进行介绍和分析，最终本文将根 据这些经验设计自己的资源放置、资源定位、资源获取方案。 2 2 1p 2 p 网络分类 p 2 p 网络主要分为三种类型：集中式p 2 p 网络，全分布式非结构化p 2 p 网络， 全分布式结构化p 2 p 网络以及分布式拓扑结构网络。 2 2 1 1 集中式p 2 p 网络 该模型主要包含两个角色，主服务器和用户节点。用户节点上线后都向主节 点联系并将自己存储的数据内容的目录信息发送给主节点，这样主节点就知道了 网络中所有的资源信息。当用户要查询或下载某个文件时，其向主节点联系并发 送请求，主节点直接进行本地查找就可以确定该文件对应的用户节点并将该用户 的网络地址返回给查询用户，然后两个用户之间就开始数据传输。集中式p 2 p 网 电子科技大学硕士学位论文 络结构的最大优点是简单，易于维护，资源查找成功率较高。由于该模型中存在 中心节点，所以该模型与传统的c s 模型具有相同的缺点，即单点故障和系统的 可靠性不高。集中式p 2 p 网络拓扑结构的代表应用是用于共享音乐文件的 n a p s t e r 【1 7 1 系统( 见图2 5 ) 。 篙亳 捌 囊 圈蘑捌 图2 - 5 n a p s t e r 的系统拓扑结构 n a p s t e r 的工作原理如图2 5 所示。当用户a 需要查询文件f 时，该用户首先 连接到n a p s t e r 的主服务器上进行文件查询，主服务器查询到音乐文件f 的位置 信息后返回存有文件f 的用户的地址等信息，最后用户a 直接连接到到文件f 的 所有者进行文件传输。 在n a p s t e r 系统中，资源的查询和数据的传输的分离减少了中心服务器的负 载和带宽压力，减少了文件的传输时间。但n a p s t e r 并没有实现复杂的p 2 p 下载 功能，如从多用户进行分片的并行下载等。集中式p 2 p 网络拓扑结构存在以下问 题t 第一由于中心节点在系统中的重要作用，中心节点一旦崩溃，整个系统将不 可用。因此，集中式p 2 p 网络的可靠性较低。 第二由于单个计算机节点计算能力和存储资源的限制，当网络规模增大到一 定程度后，中心服务器将不能应对庞大的负载压力。所以集中式p 2 p 网络的可扩 展性较差。 第三在集中式p 2 p 网络中，中心服务器一般存储了目录索引，版权纠纷问 题是最大的挑战。 综合上述，集中式p 2 p 网络比较适合架构在小规模网络环境中，而不适用于 1 2 ， v t 阐 删 止 、 第二章相关技术和系统 大规模的网络环境。 2 2 1 2 全分布式非结构化p 2 p 网络 与集中式p 2 p 网络不同，全分布式非结构化p 2 p 网络完全根除了中心节点。 由于没有了中心节点存储资源信息和完成查询功能，这类系统采用了泛洪搜索算 法。由于泛洪搜索算法采用广播的方式向系统中的每一个节点广播自己的信息和 请求，所以该算法的性能较低、扩展性很差。 全分布式非结构化p 2 p 网络的典型代表是类c m u t e l l a 1 嗣系统。图2 - 6 演示了 c m u t e l l a 协议的查找过程。 某用户节点要查找a 文件，则该用户向与其直接相连的所有用户节点发送查 询请求，各个收到该请求的用户节点在本地查找a ，如果找到后则将信息返回给 发起查询的用户节点，否则向该节点的邻居节点继续进行泛洪查询，直到查找到 该文件为止。 另外，各个用户节点通过在局域网广播来发现邻居节点。为了避免查询过程 永久的进行下去，一般通过对每个查询设定一个”凡( t i m e t ol i v e ) 来控制递归查 询的深度。 图2 - 6g n u t e l l a 原理图 由于g n u t e l l a 使用了泛洪搜索算法，这导致其不适合应用在用户节点多、网 络规模大的环境中。 2 2 1 3 全分布式结构化拓扑网络 全分布式结构化拓扑网络也根除了中心节点，但这种网络模型将系统中的节 点组织成了一个有结构的应用层网络。其中的一种典型的技术就是分布式散列表 1 3 电子科技大学硕士学位论文 ( d i s t r i b u t e dh a s ht a b l e ，简写成d h t ) 1 9 】。使