基于快照和克隆的索引技术设计与实现.pdf

《基于快照和克隆的索引技术设计与实现.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号密级公开编号碛士蚵究嗲依铪式题目：棊于快照和完隆的索引技术设计与实现学院（所、中心）软件学院专业名称软件工程研究生姓名傅央学号导师姓名周维职称副教授年月论文独创性声明及使用授权本论文是作者在导师指导下取得的研宄成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研宄成果，不存在剽窃或抄袭行为。与作者一同工作的同志对本研宄所做的任何贡献均已在论文中作了明确的说明并表示了谢意。现就论文的使用对云南大学授权如下：学校有权保留本论文（含电子版），也可以采用影印、缩印或其他复制手段保存论文；学校有权公布论文

2、的全部或部分内容，可以将论文用于查阅或借阅服务；学校有权向有关机构送交学位论文用于学术规范审查、社会监督或评奖；学校有权将学位论文的全部或部分内容录入有关数据库用于检索服务。内部或保密的论文在解密后应遵循此规定）研究生签名：导师签名：曰期：鄉用摘要随着目前存储系统中数据量的不断增加，数据的索引也变得越来越庞大。庞大的索引导致当数据发生回溯时重建索引的开销无法忽视。同时对于海量数据建立逻辑上独立的索引也成为目前云存储系统中一个不可或缺的需求。由于树结构在索引上独特的优势，己经被成功的应用于许多磁盘文件索引中，传统基于单点服务器的树

3、索引在大数据时代存在诸多问题，故需要对分布式环境下树架构以及高效的快照与克隆操作进行深入研究。针对以上问题，本文主要工作包括设计了一种基于树的双层索引结构，克服了由于单节点索引负载承受引发的局限性问题，使得系统具有可扩展性；设计并实现了一种仅备份修改节点并共用相同节点的树快照与克隆方式，其中快照的实现保证了能够存储多个时间点的索引镜像，方便索引进行回溯操作；而克隆则可以提供多个相互独立可修改的索引镜像，使得可以有多个相互独立的索引存在与一个存储系统中，由于共用了相同节点，在空间利用率上比起传统的完整备份方式有较大优势。提出了一种

4、基于快照克隆技术的高并发双层索引。采取原子操作和惰性平衡相结合的方式使得索引具有较高的并发效率。通过最后的实验数据表明，本文提出的快照与克隆方法具有较高的效率。关键词：数据索引；树型结构；快照；克隆AbstractWiththeconstantlyincreasingofdatastoragesystems,thedataindexhasalsobecomelargerandlarger.Duetohugedataindex,nowwecan'tignorethecostofrebuildingindexwhenpursuing

5、datatraceback.Atthesametimebuildinglogicindependentindexonbigdatabecomesailindispensableneedincurrentcloudstoragesystem.B-treehasbeenutilizedinmanydiscdocumentindexesbecauseofitsuniqueadvantage.TraditionalB-treeindexbasedonsinglepointserverhastoomanyproblemsinbigdata

6、ages，，目录第一章引言研究背景选题目的和意义本文主要工作第二章相关技术树在索引结构中的应用快照与克隆中深度拷贝介绍第三章基于树的快照与克隆基于树分部式双层索引结构设计树叶节点链式结构对快照与克隆的影响树的节点定义快照技术设计与实现克隆技术设计与实现第四章高并发双层索引结构设计原子操作介绍利用原子操作实现无锁堆栈基于快照克隆技术高并发双层索引设计第五章实验对比第六章总结第七章参考文献第八章致谢图目录图标准树图同步备份与异步备份示意图快照实现思路图双层索引结构示意图图快照思路图叶子节点层指针对快照的影响图插入数据时快照建立流程图

7、阶树举例图树插入数据导致层高改变时快照建立图删除数据时树情况图删除数据时快照建立过程图克隆镜像创建过程图当发生修改时克隆镜像处理流程图当发生层高改变时克隆处理流程图双层索引结构无锁并发解决方案图两千万级别数据下快照插入删除与完全拷贝耗时图—千万级别数据下快照插入删除与完全拷贝耗时比较图—百万级别数据下快照插入删除与完全拷贝耗时比较图插入删除条数据耗时图插入删除条数据耗时第一章引言第一章引言」研究背景随着信息技术的快速发展，海量信息对数据的存储和索引都提出了更高的要求。在这个信息高速增长的时代，在单台服务器上存储和索引数据已经无法

8、满足数据量高速增长的需求，分布式云存储系统应运而生。目前主流的云存储系统包括亚马逊的，的以及的微软的等，这些平台都是由成千上万的计算机构连接而成，在这样大规模的数据面前，如何快速准确的索引数据并为用户提供服务是一个关键的问题，同时，如何保证这样大规模索引的稳定性