基于格雷码的结构化对等计算系统及其数据管理

论文摘要

对等计算（Peer-to-Peer,简称P2P）是一个自组织的分布式网络系统。脱胎于文件共享,当前P2P系统的研究热点已经逐步过渡到:系统资源共享、分布式数据管理等。这类研究给现代网络应用注入了新的活力,因为P2P系统打破了现有网络结构,进而提供了一个自组织、高分散、可扩展、节点对等的分布式网络。同时,这种分布式网络结构也给网络应用带来了很多新的挑战,例如,如何提供有效的复杂数据查询、如何获取当前网络中数据的分布信息等等。尽管对等计算系统在文件共享、简单数据管理方面已经取得了不少研究成果,但是许多问题（如复杂数据管理等）依旧亟待解决。本文的研究重点是在现有成熟的P2P覆盖网络（Chord）基础上,对其改进、优化,并提出了一个新的P2P系统——GChord系统。结合了Chord系统的路由特性和格雷码（GrayCode）数据索引编码的优点,GChord（Gray Code based Chord System）系统由此具备了支持复杂数据管理能力。现有GChord系统支持的复杂数据管理主要包括:当前网络中数据密度分布函数的准确估计、一维（多维）精确匹配查找、一维（多维）范围查找、偏好查找、多属性查找等。以后我们将对GChord系统不断研究、充实,使之成为一个完备的P2P系统。下面给出本文的主要贡献:●实现了GChord系统中节点管理和数据管理的无缝结合。GChord系统脱胎于Chord系统,但是青出于蓝而胜于蓝。GChord系统将原Chord系统中相互独立的节点管理和数据管理紧密地结合起来,进而获得了很多Chord系统不具备的特性。对于节点管理,GChord系统和Chord系统具有相同的组织、维护方式。对于数据管理,GChord系统结合了基于格雷码（任意相邻的两个格雷码相差一位）混洗编码（shuffle-based）的数据索引键值生成技术,实现了节点管理和数据管理的无缝结合。GChord系统的指表（fingertable,即路由表）不仅实现了节点路由的O（logn）复杂度,同时也实现了数据值域路由的O（logn）复杂度,其中n为系统中节点数目。突破了Chord系统只支持精确匹配查找的限制,GChord系统能够支持包括范围查找在内的许多复杂数据管理。●对GChord系统中分布无关数据密度分布函数估计提供了支持,即让网络中的每个节点都能精确估计当前网络中数据的密度分布。P2P系统的许多应用均受益于密度分布估计,例如:负载平衡分析、复杂数据查询和数据挖掘等等。分布无关数据密度函数估计算法的主要特性是,不论底层数据按照何种模型分布抑或是根本不存在任何分布模型,该算法均能以近似的估计精度准确估计当前网络中的数据密度分布函数。分布无关密度估计算法首先将底层数据的任意分布转换成一中间分布——累计概率分布函数。由于累计概率分布函数的输出在[0,1]之间均匀分布,因此接着对累计概率分布函数的输出随机采样,可以准确估计当前网络中数据的密度分布。本文在GChord系统环境下,提出了三种计算累计概率分布函数的有效算法和两种对累计概率分布函数的输出随机采样的算法。累计概率分布函数计算算法让网络中每个节点只维护累计概率分布函数中相互不重叠的一个片段,而所有这些片断综合起来又构成了完整的累计概率分布函数,由此降低了各个节点的维护代价。我们从理论上证明了累计概率分布函数的计算误差和分布无关数据密度估计的估计误差,同时给出了详尽的算法。充分的实验也证明了该算法在估计数据分布方面的有效性和高效性。●对GChord系统中偏好查找提供了支持。所谓偏好查找是指查询请求中包含有用户对各个属性项不同偏好程度并返回top-k条数据元组的查询。对于各个属性项具有不同偏好程度的查询请求,其查询结果可能大相径庭。现有数据索引技术均无法对偏好查找提供很好的支持。本文提出了一种在GChord系统上支持偏好查找的新颖方法。通过估计当前网络中的数据分布,并计算包含有top-k查询数据元组的区域范围,将偏好查找转换为范围查找并执行有效查找。通过对数据空间多维柱状图信息进行离散余弦变换可有效维护当前网络中数据的分布,从而实现数据密度分布的准确估计。本文也提出了对偏好矩阵（由查询请求给定）作奇异值分解,有效计算对应查找范围的算法。在实现偏好查找到范围查找的有效转换之后,通过多播区域（mutli-cast zone）的形式获取相关节点上的top-k条数据元组。本文给出了数据分布估计算法和范围计算的算法及其理论分析。详尽的实验证明了该方法在处理偏好查找方面的有效性和高效性。●对GChord系统中多属性范围查找提供了支持。所谓多属性查找是指查询请求中仅包含有用户关心属性项的谓词（即查询中包含的属性项可以是数据元组属性项集合的子集）。因此,该类查询请求中包含的谓词可以针对任意数目的属性项,也可以针对任意属性项之间的组合。现有P2P系统都无法高效的处理该类查询。由于GChord系统实现了节点管理和数据管理之间的无缝结合,进而实现了相邻数据之间的快速路由,由此提供了对多属性查询的良好支持。本文提出了使用卡诺图（Karnaugh map）有效计算包含有查询结果节点的算法,并且以多播树（multi-cast tree）的方式获取这些节点上数据元组的算法及其理论分析。详尽的试验证明了该方法在处理多属性查询的有效性和高效性。综上所述,本文详细介绍了GChord系统,及其支持的复杂数据管理操作。GChord系统实现了节点管理和数据管理的无缝结合,并对当前网络中分布无关数据密度的精确估计、偏好查找、多属性范围查找、一维精确匹配查找（源于对Chord系统的继承）、多维精确匹配查找和一维（多维）范围查找（源于对多属性范围查找的支持）提供了支持。这些功能满足了当前P2P系统发展的需要,促进了P2P系统的发展。以后我们将不断充实和完善GChord系统,使之成为一个成熟、完备的P2P系统。

论文目录

• 中文摘要
• 英文摘要
• 图目录
• 表目录
• 第一章 绪论
• 1.1 对等计算概述
• 1.1.1 P2P系统的起源:从ARPANET到P2P
• 1.1.2 P2P系统的发展:从无结构化P2P到结构化P2P
• 1.1.3 P2P系统的数据管理:从简单到复杂
• 1.1.4 P2P系统的抽象层次结构:从网络层到应用层
• 1.2 本文的研究目标、内容和面临的挑战
• 1.2.1 研究目标与内容
• 1.2.2 面临的挑战
• 1.3 本文的主要工作和论文组织
• 第二章 对等计算数据管理的研究进展
• 2.1 数据估计
• 2.2 数据查找
• 2.2.1 精确匹配查找
• 2.2.2 范围查找
• 2.2.3 聚合查找
• 2.3 本章小结
• 第三章 GChord覆盖网络
• 3.1 DHT式P2P覆盖网络简介
• 3.2 Chord覆盖网络简介
• 3.2.1 指表维护
• 3.2.2 数据索引及查找
• 3.3 GChord覆盖网络
• 3.3.1 数据索引
• 3.3.2 覆盖网络的性质
• 3.4 本章小结
• 第四章 分布无关数据密度估计
• 4.1 相关工作
• 4.2 预备知识
• 4.2.1 基本概率定义
• 4.2.2 覆盖网络
• 4.2.3 索引方法
• 4.3 分布无关估计
• 4.4 累计频率分布函数的计算
• 4.4.1 基本方法
• 4.4.2 快速方法
• 4.4.3 同步方法
• 4.4.4 更新
• 4.5 采样和估计
• 4.5.1 全局累计分布函数采样
• 4.5.2 部分累计分布函数采样
• 4.5.3 数据密度估计
• 4.6 扩展
• 4.6.1 离散值域数据
• 4.6.2 多维数据
• 4.7 实验分析
• 4.7.1 GChord系统的动态性测试
• 4.7.2 改进方法的测试
• 4.7.3 比较实验
• 4.8 本章小结
• 第五章 偏好查找
• 5.1 相关工作
• 5.2 预备知识
• 5.2.1 问题定义
• 5.2.2 覆盖网络
• 5.2.3 离散余弦变换
• 5.3 多维数据密度估计
• 5.3.1 离散余弦变换的理论计算
• 5.3.2 GChord系统下离散余弦变换计算
• 5.3.3 理论分析
• 5.4 偏好查找转换与执行
• 5.4.1 范围计算
• 5.4.2 范围路由
• 5.5 实验分析
• 5.5.1 GChord系统的动态性测试
• 5.5.2 比较实验
• 5.6 本章小结
• 第六章 多属性查找
• 6.1 问题定义
• 6.2 基本多属性查找处理
• 6.2.1 查找处理框架
• 6.2.2 构造多播树
• 6.2.3 基于多播树的查找处理
• 6.3 索引与查找优化
• 6.3.1 网络索引缓存
• 6.3.2 多播树聚类
• 6.4 实验结果
• 6.5 本章小结
• 第七章 结论与展望
• 7.1 本文工作的总结
• 7.2 展望
• 参考文献
• 攻读博士期间发表或完成的论文
• 致谢