[01363147]基于哈希表的三维空间数据自适应缓存管理方法及系统

由于三维空间数据具有结构复杂、类型繁多、数据量庞大、空间分布不均衡、个体对象的差异性以及多细节层次表达的特性,针对三维实时可视化应用的高效数据调度需求,如何高效、一体化的组织、管理、调度不均匀分布的地上地下、室外室内的三维空间数据成为亟需突破的难点。与此同时,地理、地质特征相关信息的一体化存储与访问是GIS软件平台研发的关键技术。 缓存（Cache）是计算机领域非常通用的概念。它介于应用程序和永久性数据存储源（如硬盘上的文件或者数据库）之间,其作用是降低应用程序直接读写永久性数据存储源的频率,从而提高应用的运行性能。缓存中的数据是数据存储源中数据的拷贝,应用程序在运行时直接读写缓存中的数据,只在某些特定时刻按照缓存中的数据来同步更新数据存储源。在应用程序中缓存数据有以下好处： 1)降低需要做的磁盘访问次数,减少硬盘读写数据的耗时; 2)减少交互的数据读取量,缓存数据能有效减少在应用程序进程和机器硬件间的数据传输量; 3)降低系统中的数据处理量,减少数据修改处理次数。 依据缓存技术的应用领域不同,主要有存储器缓存技术、磁盘缓存技术、Web服务器的缓存技术以及数据缓存技术等;根据缓存的应用位置不同可以分为：客户端数据缓存系统、集中式数据缓存系统、分布式数据缓存系统以及虚拟数据缓存系统等。 内存驻留缓存,包含在内存中临时存储数据的所有实现方法,通常使用在应用程序频繁使用同样的数据和应用程序需要经常获取数据这两类情况中。通过将数据保留在内存中,可以有效降低昂贵的磁盘访问操作,也可以通过将数据保留在使用者进程中来最大程度的减少跨进程的数据传输。 磁盘驻留缓存,包含所有使用磁盘作为存储介质的缓存技术,如文件和数据库。基于磁盘的缓存有效的应用在处理大数据量;应用服务提供的数据可能并不是总能使用（比如离线的情况）;缓存的数据必须能在进程回收和机器重启的情况下保持有效等应用中。 从三维空间数据库中动态调度数据时,需要频繁地进行数据库的访问操作。目前,绝大多数的数据库管理系统都是基于磁盘管理的体系架构,如Oracle、SQL Server、DB2等,频繁的磁盘读写操作往往成为影响空间数据动态调度性能的主要瓶颈,如果将经常被访问的数据保存在内存中,则可以大大降低或消除数据库读取数据的开销。因此,缓存技术成为提高数据访问效率的有效方法。对于对响应速度与数据存取性能要求极高的三维空间数据库来说,采用缓存技术可以大幅度提高海量三维空间数据并发访问能力以及动态调度的性能。 缓存技术作为缓解处理器的速度和磁盘I/O性能之间的差距的主要技术,一直是工业界和学术界的研究热点。随着网络存储、数据服务器架构、云存储等新技术的出现,数据存储的层次越来越复杂,对缓存技术又提出了新的要求。缓存替换算法作为缓存技术的核心技术之一受到广泛的关注,而频率和时间综合考虑的缓存替换方法、多级缓存的替换技术则是研究的热点。通过缓存处理过的数据,可以有效降低数据处理的负担,同时可减少数据交互的代价。 替换策略以最小化损耗（如失误率、字节失误率、平均延时和总体损耗）为标准。传统的缓存替换算法主要利用对数据块的访问频率或者最近的访问时间为标准判断数据块在本次替换操作中应该被替换掉。 传统的缓存替换算法主要有LRU、MRU、LFU三类代表。单级缓存替换算法研究中基于频率和时间平衡策略的算法有很多,比如UFU、ARC、MQ/2Q等。这些替换算法的判断标准都比较单一,且基本上只对一类访问模式有比较好的效果,对其他的访问模式其效果明显不好。当前单级缓存算法的研究更加侧重于对各种应用访问模式的自适应能力。因为基于特殊应用策略的缓存替换算法,比如DBMIN、Application-Controlled File Caching等一般属于为专有系统特殊的应用场景而定制的,其通用性很有限。 多级缓存算法又可以划分成两类：Hierarchy-aware Caching 和Aggressively-collaborative Caching。Hierarchy-aware Caching存储服务器知道在它的前端存在大量的客户端缓存,但不需要对自己I/O接口和存储客户端软件有任何改变。主要通过猜测的手段对缓存的冗余等情况进行判断,可以通过数据块的地址、文件语义等信息进行猜测。Aggressively-collaborative Caching修改I/O接口和存储客户端软件。又可以分为基于线索的方式hitbased,比如TQ,DEMOTE等,客户端控制的方式client-controlle。基于recency/frequency平衡策略仍然是研究的热点。 为了提高三维空间数据从三维空间数据库中动态调度的效率,满足三维实时可视化的快速数据请求,高效的缓存机制成为有效的解决方法之一。由于硬件条件的不断提高,内存数据量在不断增大,缓存内查询效率成为影响数据调度速度的因素之一。一般的线性表、树,记录在结构中的相对位置是随机的,即和记录的关键字之间不存在确定的关系,在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较”的基础上,查找的效率与比较次数密切相关。理想的情况是能直接找到需要的记录,因此必须在记录的存储位置和它的关键字之间建立一种确定的对应关系,使每个关键字和结构中一个唯一的存储位置相对应。哈希表正是按照这个思想建立的,不需要进行比较便可直接取得所查记录,大大缩短了查找消耗的时间。本发明的目的是提供一种基于哈希表的三维空间数据自适应缓存管理方法及系统,针对三维空间数据实时可视化应用的高效调度需求,解决高效、一体化的组织、管理、调度不均匀分布的地上地下、室外室内的三维空间数据,并在服务器/客户端、硬盘/内存/显存等多个层次建立高效的数据缓存和应用缓存,用于提高三维空间数据的调度能力以及并发访问能力,同时针对文件系统、关系型数据库管理系统及其集群并行管理系统等三种不同的应用模式的需要,实现缓存的自适应设置。本发明缓存替换算法综合考量数据组织耗时、访问频率和时间,可依据查询特性设定权值计算中访问次数和最近一次访问的时间的权重,通过运行统计调整替换算法到最佳命中效果;缓存统一管理各缓存池,结合系统资源使用情况,把数据库与查询运行的实际执行信息加入考虑,调整缓存状态及各缓存池的深度和粒度;按对象类型分缓存池存储,按数据类型遍历缩短了数据查找时间;缩短了空间对象读取时几何数据与属性数据组织时间;满足文件系统、关系型数据库管理系统及其集群并行管理系统等三种不同的应用模式的需要,实现缓存的自适应设置。本发明的技术内容自2007年起,已成为QuantyView（原名：GeoView）三维地质信息系统平台的有机组成部分,已经应用于“数字矿山”、“数字油田”、“数字勘查”、“数字地灾”、“数字地调”、“数字水利”、“数字城市”、“数字国土”等多个软件系统中,产生了良好的经济效益和社会效益。