云搜索正确性的快速验证系统

摘要

随着计算机硬件和网络带宽的发展，云计算在个人的日常使用中以及商业用途中扮演起了越来越重要的角色。得益于云存储容量大、高可靠、易访问的特点，越来越多的个人和企业选择把他们的文档存储到云上。在对云文档的操作中，搜索是一项常用并且有用的功能，怎么保证云搜索结果的正确性也变得越来越重要。针对这个问题已经有不少的相关研究工作，但是一个高效的高扩展性的系统到现在也没有推广开来。
　　在研究了一些现有的验证方案之后，设计并实现了一个云搜索验证系统，能够快速高效地验证云搜索的正确性。首先，设计了一套基于 RSA Accumulator的验证机制，并以这个验证机制为基础设计实现了一个云搜索验证系统。该系统采用了模块化的设计方法，每个模块都是一个单独的进程，模块之间可以独立部署，使得整个系统有很高的扩展性和易维护性。其次，为了解决当搜索的文档集合比较大时，正确性证明生成速度慢的问题，设计了一种树状结构证明，通过将大的集合拆分成多个小的集合并按照树状组织起来，以此减少计算量，提高计算并行程度，加快了证明的生成速度。还提出了一个将树状结构证明用于生成完整性证明的思路，可以用于提高完整性证明的生成速度。同时，为了方便树状结构证明中多个同类任务的并行计算，实现了一套轻量级的并行计算框架，该框架可以方便地进行任务分派，并可以配置使用机器的数量。最后，考虑到有些计算是效率优先而不用完全保证正确性，提出了一种基于采样的验证方式，使得用户可以根据需求在计算效率和正确性保证程度之间做出权衡。
　　使用两个真实数据集进行实验评估，实验结果表明通过使用树状结构，该系统在计算正确性证明上有着平均2.5倍的速度提升。在整个搜索和证明生成的速度上，该系统相比于原来的计算方法有着平均为2倍的提升，尤其是对于那些本来处理比较慢的情况，比如原来要10秒左右的查询，该系统可以达到4倍左右的速度提升。在处理数据的规模上，在实验环境下，该系统已经能够对100GB级别的数据集进行计算，这是原有的计算方法无法处理的。

目录

封面

中文摘要

英文摘要

目录

第一章 绪论

1.1 研究背景和意义

1.2 国内外研究现状

1.3 研究内容

1.4 论文结构

1.5 本章小结

第二章 相关工作

2.1 RSA Accumulator

2.2 集合交集的证明

2.3 一种基于加密哈希的查询验证方式

2.4 本章小结

第三章 应用场景

3.1 云档案管理系统

3.2 本章小结

第四章 设计

4.1 基于RSA Accumulator的验证机制

4.2 基于采样的验证

4.3 本章小结

第五章 实现

5.1 系统的整体架构

5.2 树状结构证明

5.3 本章小结

第六章 实验评估

6.1 数据集

6.2 测试环境

6.3 正确性证明的性能比较

6.4 总体性能测试

6.5 验证时间的比较

6.6 基于采样的验证机制的性能和正确性保证

6.7 大数据集的性能测试

6.8 本章小结

第七章 全文总结

7.1 课题贡献

7.2 工作展望

参考文献

致谢

攻读学位期间发表的学术论文目录

声明