DCST:主存空间高效的缓存敏感型T-树索引研究

已有主存索引通过指针消除和预取机制提升索引结构的缓存感知能力,减少缓存失效次数,但是并没有有效地利用现代计算机的CPU性能和内存空间。为了进一步提升索引结构对内存空间以及CPU性能的利用率,提出了DCST-树索引结构。该索引结构采用数据压缩的方式,对结点中的关键字进行压缩,提高索引结构对内存空间和缓存空间的利用率,减少内存访问次数,提高缓存命中率。同时,对结点进行分区,增加结点容量,提高结点扇出度,降低树的高度。实验结果表明,所提方案比现有主存索引机制具有更加高效的空间利用率和缓存感知能力,同时具有更加优秀的查询处理能力。     

多线程环境的高效内存分配技术

介绍了一种新的多线程内存分配技术（NIXMalloc）的设计和实现,提出了两种高效的分配策略及其自适应调优方法,有效地提高多线程应用程序的内存管理性能;其中Local分配策略对超级块对象Span进行了线程私有化,基于超级块对象为单位的垃圾回收和内存布局调整使多线程性能更优越;Global分配策略采用了自适应调优方法,在动态检测应用程序内存使用情况的基础上进行内存预取和线程缓存限值的动态调整;实验证明NIXMalloc可改善内存管理性能,提高吞吐量,同时降低内存使用量;在多线程应用系统中能获得较好的时空效率。     

面向社交网络密集图数据存储的缓存置换算法

为了缓解社交网络热点话题生成的密集图数据导致存储的频繁读取和缓存空间浪费等问题，针对话题产生与消亡的演化更新规律，提出了基于话题热度演化加速度的缓存置换算法(cache replacement algorithm based on topic heat evolution acceleration, THEA-CR)。该算法首先对社交网络数据进行话题簇的实体划分，识别锚定目标。其次，计算话题热度演化加速度，对热点数据的优先级进行研判；最后设计双队列缓存置换策略，针对话题关注度和访问频率进行缓存空间的置换和更新。在新浪微博数据集中与经典的缓存置换算法进行大量对比实验，验证了所提算法具有较好的可行性与有效性。结果表明提出的THEA-CR算法能够在社交网络密集图数据的不同图查询操作中平均提升约31.4%的缓存命中率，并且缩短了约27.1%的查询响应时间。     

优化内存问答

问:优化系统内存有哪些途径? 所谓优化内存是指对系统内存作一定的调整,使用户应用程序能够最高效地使用系统内存资源。优化内存使用的关键是释放常规内存空间,访问640KB以外的内存空间。基本途径有4条。     

一种基于页面级流缓存结构的流检测和预取算法

为了提高网络内存的访存性能,基于一种页面级流缓存和预取结构提出了可变步长的带状流检测算法VSS(variable stride stream)和基于时钟步长的流预取优化算法来优化网络访存性能.带状流检测算法解决了固定步长流检测下循环访问中虚拟页地址的跳跃问题,消除了断流,可以有效提高流检测的覆盖率.基于时钟步长的流预取优化动态调整预取长度,可以解决有些预取不能及时取回的问题,进一步提高预取性能.通过和顺序预取算法的比较可以看出,VSS算法可以实现高准确率、低通信开销的预取.通过模拟分析了这种流缓存和预取机制在网络访存系统中的应用,验证了以少量性能下降换取灵活的远程内存扩展方法的可行性.     

内存数据库在TPC-H负载下的处理器性能

Ailamaki等人1999年研究了数据库管理系统(database management system,简称DBMS)在处理器上的时间开销分解.此后,相关研究集中在分析DBMS在处理器上的瓶颈.但这些研究工作均是在磁盘数据库DRDBs(disk resident databases)上开展的,而且都是分析DBMS上的TPC-C类负载.然而,随着硬件技术的进步,现代计算机的多级缓存结构(memory hierarchy)在逐渐地"上移".例如,容量越来越大的芯片内缓存(on-chip caches)和芯片外缓存(off-chip caches),容量越来越大的RAM,Flash Memory等等.为此,处理器负载分析的研究工作也应随之"上移".研究内存数据MMDBs(mainmemory resident databases)在计算密集型负载下的处理器行为特性.由于磁盘数据库的主要性能瓶颈是磁盘I/O,因而可以用索引、压缩等技术进行优化;然而,内存数据库的性能瓶颈却在于处理器和内存之间的数据交换.针对这一问题,首先分析了磁盘数据库和内存数据库在TPC-H负载下处理器性能瓶颈的差异,并给出了一些优化建议,提出了通过预取的优化方法.其次,通过实验比较了不同存储体系结构(行存储与列存储)对处理器利用率的差异,并探索了下一代内存数据库体系结构方面的解决方案.此外,还研究了索引结构对处理器多级缓存的影响,并给出了索引的优化建议.最后,提出一个微测试集用于评估内存数据库在DSS(decision support system)负载下处理器的性能及行为特性.研究结果会对运行于下一代处理器上的内存数据库体系结构设计和性能优化提供一定的实验依据.     

一种智能终端数据共享中的预取缓存技术

针对智能终端数据共享中的网络延迟问题,本文提出一种两阶段,主动预取与被动预取相结合的数据预取缓存方法,减少网络延迟,提高用户体验。该方法利用网络空闲时间预取数据,减少用户等待时间;通过两阶段预取策略减少网络带宽消耗;通过主被动配合的预取算法来预取数据,提高预取准确率和预取效率;通过一种权重更新函数来更新客户端的缓存,减少对智能终端存储空间的消耗。实验表明使用此方法能减少用户等待时间58.2%,预取命中率为92%,带来的带宽损耗小于5%。     

一种智能的预取算法

网络延迟问题是用户QoS的主要问题之一,它依赖诸多因素如网络带宽、传输延迟、排队延迟和客户机及服务器的处理速度。目前主要采用缓存和预取技术来减少网络延迟,但缓存技术所提高的缓存代理服务器的命中率是有限的。该文系统地阐述了目前预取算法的基本思想并把它们分成四类:基于流行度、基于交互、基于访问概率和基于数据挖掘的预取算法。在对它们进行分析比较的基础上,提出了一种智能的预取方案。该方案使用模糊匹配来计算用户对页面的访问概率,同时要控制预取的量和预取的时刻,以避免对网络的性能产生负面影响。     

基于深度优先序列模式挖掘的预取模型

序列模式挖掘能够发现隐含在Web日志中的用户的访问规律,可以被用来在Web预取模型中预测即将访问的Web对象。目前大多数序列模式挖掘是基于Apriori的宽度优先算法。提出了基于位图深度优先挖掘算法,采用基于字典树数据结构的深度优先策略,同时采用位图保存和计算各序列的支持度,能够较迅速地挖掘出频繁序列。将该序列模式挖掘算法应用于Web预取模型中,在预取缓存一体化的条件下实验表明具有较好的性能。     

IP交换机中嵌入式内存数据库HSQL的索引优化

该文分析总结了当前在内存数据库中提高树索引的缓存敏感性的主要技术,设计并实现了一个具有缓存敏感性的AVL树,即CC-AVL树。CC-AVL树合理利用缓存行的大小,并构造父子节点在内存中连续存储的结构,从而使一个缓存行中包含正要访问的节点和其左孩子节点,同时使用CPU支持的数据预取技术获得右孩子节点。从而使CC-AVL树比AVL树具有更高的缓存敏感性。CC-AVL树被用于一个运行在IP交换机中的嵌入式内存数据库HSQL中。     

基于时空局部性的层次化查询结果缓存机制

查询结果缓存可以对查询结果的文档标识符集合或者实际的返回页面进行缓存,以提高用户查询的响应速度,相应的缓存形式可以分别称之为标识符缓存或页面缓存。对于固定大小的内存,标识符缓存可以获得更高的命中率,而页面缓存可以达到更高的响应速度。该文根据用户查询访问的时间局部性和空间局部性,提出了一种新颖的基于时空局部性的层次化结果缓存机制。首先,该机制将固定大小的结果缓存划分为两层:页面缓存和标识符缓存。对于用户提交的查询,该机制会首先使用第一层的页面缓存进行应答,如果未能命中,则继续尝试使用第二层的标识符缓存。实验显示这种层次化的缓存机制较传统的仅依赖于单一缓存形式的机制,在平均查询响应时间上,取得了可观的性能提升:例如,相对单纯的页面缓存,平均达到9%,最好情况下达到11%。其次,该机制在标识符缓存的基础上,设计了一种启发式的预取策略,对用户查询检索的空间局部性进行挖掘。实验显示,这种预取策略的融合,能进一步促进检索系统性能的有效提升,从而最终建立起一套时空完备的、有效的结果缓存机制。     

Towards Intelligent Semantic Caching for Web Sources

An intelligent semantic caching scheme suitable for web sources is presented. Since web sources typically have weaker querying capabilities than conventional databases, existing semantic caching schemes cannot be directly applied. Our proposal takes care of the difference between the query capabilities of an end user system and web sources. In addition, an analysis on the match types between a user's input query and cached queries is presented. Based on this analysis, we present an algorithm that finds the best matched query under different circumstances. Furthermore, a method to use semantic knowledge, acquired from the data, to avoid unnecessary access to web sources by transforming the cache miss to the cache hit is presented. To verify the effectiveness of the proposed semantic caching scheme, we first show how to generate synthetic queries exhibiting different levels of semantic localities. Then, using the test sets, we show that the proposed query matching technique is an efficient and effective way for semantic caching in web databases.     

基于用户特性的搜索引擎查询结果缓存与预取

针对搜索引擎查询结果缓存与预取问题,与传统的基于查询特性相关的方法不同,提出了一种基于用户特性的缓存与预取方法,用于提高搜索引擎系统性能,尤其针对部分用户效果更显著。通过对国内某著名商业搜索引擎用户的查询贡献分析得出,用户对搜索引擎的贡献具有长尾分布特性,结合该特性设计查询结果预测模型来进行预取和分区缓存。在该搜索引擎两个月的大规模真实用户查询日志上的实验结果表明,与传统的基于查询特性的典型方法相比,该方法可以获得3.03%~4.17%的命中率提升,对于查询贡献最大的0.25%的用户群体,可以获得20.52%~28.2%的命中率提升。     

一种自适应的数据预取与缓冲算法

在海量数据中进行的直接查找往往耗时巨大,在实际应用中很难满足实时性的需求,因此采用数据预取和缓冲技术实现对查找操作的优化成为实际系统中的重要环节。自适应的数据预取和缓冲算法是通过使用人工智能中的技术来分析用户的查询习惯,从而实现动态的预取策略并对预取的数据进行缓冲,以达到提高查询速度的目的。文章根据不同的数据查询需求提出了两类智能算法以适应不同的应用场合。在实验中分别针对单个用户的历史查询应用和多用户的并发查询应用分别进行了分析,证明了这两类智能算法分别对不同的应用场合拥有较好的性能。     

一种基于查询特性的查询结果缓存与预取方法

针对搜索引擎查询结果缓存与预取问题,该文提出了一种基于查询特性的搜索引擎查询结果缓存与预取方法,该方法包括用来指导预取的查询结果页码预测模型和缓存与预取算法框架,用于提高搜索引擎系统性能。通过对国内某著名中文商业搜索引擎的某段时间的用户查询日志分析得出,用户对不同查询返回的查询结果所浏览的页数具有显著的非均衡性,结合该特性设计查询结果页码预测模型来进行预取和分区缓存。在该搜索引擎两个月的大规模真实用户查询日志上的实验结果表明,与传统的方法相比,该方法可以获得3.5%~8.45%的缓存命中率提升。     

基于网络性能的智能Web加速技术——缓存与预取

Web业务在网络业务中占有很大比重,在无法扩大网络带宽时,需要采取一定技术合理利用带宽,改善网络性能。研究了基于RTT（round trip time)等网络性能指标的Web智能加速技术,在对Web代理服务器上的业务进行分析和对网络RTT进行测量分析的基础上,提出了智能预取控制技术及新的缓存（cache）替换方法。对新算法的仿真研究表明,该方法提高了缓存的命中率。研究表明预取技术在不明显增加网络负荷的前提下,提高了业务的响应速度,有效地改进了Web访问性能。     

一种基于预取感知接纳策略的查询结果缓存方法

针对搜索引擎查询结果缓存问题,提出了一种基于预取感知接纳策略的查询结果缓存方法,用于提高搜索引擎检索系统性能.查询结果预取导致查询结果页码的缓存缺失率具有显著差异性,结合该特性设计预取感知接纳策略,该策略包含查询评估模型以及模型特征选择方法.在该策略基础上,设计了一种查询结果缓存方法.在该搜索引擎两个月的大规模真实用户查询日志上的实验结果表明,与传统的典型方法相比,该方法可以获得6.38%～11.99%的缓存命中率提升.     

Value complete,column complete,predicate complete

Caching is a proven remedy to enhance scalability and availability of software systems as well as to reduce latency of user requests. In contrast to Web caching where single Web objects are accessed and kept ready somewhere in caches in the user-to-server path, database caching uses full-fledged database management systems as caches, close to application servers at the edge of the Web, to adaptively maintain sets of records from a remote database and to evaluate queries on them. We analyze a new class of approaches to database caching where the extensions of query predicates that are to be evaluated are constructed by constraints in the cache. Starting from the key concept of value completeness, we explore the application of cache constraints and their implications on query evaluation correctness and on controllable cache loading called cache safeness. Furthermore, we identify simple rules for the design of cache groups and their optimization before discussing the use of single cache groups and cache group federations. Finally, we argue that predicate completeness can be used to develop new variants of constraint-based database caching.     

Web search engine: Characteristics of user behaviors and their implication

In this paper, first studied are the distribution characteristics of user behaviors based on log data from a massive web search engine. Analysis shows that stochastic distribution of user queries accords with the characteristics of power-law function and exhibits strong similarity, and the user' s queries and clicked URLs present dramatic locality, which implies that query cache and 'hot click' cache can be employed to improve system performance. Then three typical cache replacement policies are compared, including LRU, FIFO, and LFU with attenuation. In addition, the distribution character-istics of web information are also analyzed, which demonstrates that the link popularity and replica pop-ularity of a URL have positive influence on its importance. Finally, variance between the link popularity and user popularity, and variance between replica popularity and user popularity are analyzed, which give us some important insight that helps us improve the ranking algorithms in a search engine.     

Semantic caching of Web queries

Abstract. In meta-searchers accessing distributed Web-based information repositories, performance is a major issue. Efficient query processing requires an appropriate caching mechanism. Unfortunately, standard page-based as well as tuple-based caching mechanisms designed for conventional databases are not efficient on the Web, where keyword-based querying is often the only way to retrieve data. In this work, we study the problem of semantic caching of Web queries and develop a caching mechanism for conjunctive Web queries based on signature files. Our algorithms cope with both relations of semantic containment and intersection between a query and the corresponding cache items. We also develop the cache replacement strategy to treat situations when cached items differ in size and contribution when providing partial query answers. We report results of experiments and show how the caching mechanism is realized in the Knowledge Broker system. Received June 15, 1999 / Accepted December 24, 1999