Leach： an automatic learning cache for inline primary deduplication system

Deduplication technology has been increasingly used to reduce storage costs. Though it has been successfully applied to backup and archival systems, existing techniques can hardly be deployed in primary storage systems due to the associated latency cost of detecting duplicated data, where every unit has to be checked against a substantially large fin- gerprint index before it is written. In this paper we introduce Leach, for inline primary storage, a self-learning in-memory fingerprints cache to reduce the writing cost in deduplica- tion system. Leach is motivated by the characteristics of real- world I/O workloads： highly data skew exist in the access patterns of duplicated data. Leach adopts a splay tree to or- ganize the on-disk fingerprint index, automatically learns the access patterns and maintains hot working sets in cache mem- ory, with a goal to service a majority of duplicated data de- tection. Leveraging the working set property, Leach provides optimization to reduce the cost of splay operations on the fin- gerprint index and cache updates. In comprehensive experi- ments on several real-world datasets, Leach outperforms con- ventional LRU （least recently used） cache policy by reducing the number of cache misses, and significantly improves write performance without great impact to cache hits.     

旅行商问题中巡回路径的数据结构

旅行商问题中巡回路径的数据结构对局部启发式算法的效率起着非常关键的作用。巡回路径的数据结构必须能够查询一条回路中每个城市的相对顺序,并且能够将一条回路中的部分城市逆序。分析了数组表示法、伸展树表示法和两级树表示法表示巡回路径时各种基本操作的实现过程及时间复杂度。数组表示法能够在常数时间内确定一条回路中每个城市的相对顺序,但是最坏情况下完成逆序操作需要Ω（n）时间,不适用于大规模的旅行商问题。伸展树表示法执行查询和更新操作的平摊时间复杂度是O（logn）,适用于极大规模的旅行商问题。而两级树表示法在最坏情况下每一个更新操作的时间复杂度是O（n^0.5）,适用于大规模的旅行商问题。     

基于缓存技术的XML代数查询优化

针对XML代数查询优化,采用缓存技术将经常被查询到的模式树保存在缓存中,根据匹配规则判断查询模式树是否与缓存中的模式树匹配,对匹配的部分直接从缓存中获取部分查询结果,以提高查询效率。分析查询与缓存的模式匹配规则,并通过实验证明该规则的可行性和有效性。     

基于XQuery语义缓存的异构数据集成系统的查询处理

提出了一种在Mediator-Wrapper结构中嵌入基于XQuery语义缓存的异构数据集成系统的查询处理方案,主要包括查询包含关系判定、查询分解和重写.同时提出利用树型同态算法解决XQuery查询语义包含关系的判断问题和Web环境下的缓存替换策略,旨在提高信息集成系统的查询性能.     

Splaysort: Fast,Versatile, Practical

Adaptivity in sorting algorithms is sometimes gained at the expense of practicality. We give experimental results showing that Splaysort — sorting by repeated insertion into a Splay tree — is a surprisingly efficient method for in-memory sorting. Splaysort appears to be adaptive with respect to all accepted measures of presortedness, and it outperforms Quicksort for sequences with modest amounts of existing order. Although Splaysort has a linear space overhead, there are many applications for which this is reasonable. In these situations Splaysort is an attractive alternative to traditional comparison-based sorting algorithms such as Heapsort, Mergesort, and Quicksort.     

Case Studies on Cache Performance and Optimization of Programs with Unit Strides

Cache performance in modern computers is important for program efficiency. A cache is thrashing if a significant amount of time is spent moving data between the memory and the cache. This paper presents two cache thrashing examples, one in scientific computing and one in image processing, both of which involve several one-dimensional arrays that are accessed sequentially, i.e., with unit strides. Accessing arrays in unit strides was considered very efficient on cache-based computer systems. However, the existence of cache thrashing is demonstrated by significant increases in computing speed in the equivalent programs tuned for cache locality. This shows that accessing several arrays sequentially may cause cache thrashing. Thus, to improve cache performance, it is important that the compiler or the programmer takes all arrays inside a loop into consideration. © 1997 by John Wiley & Sons, Ltd.     

一种纯分布式P2P协作缓存PWCache

针对目前纯分布式点对点(P2P)协作缓存没有结合用户访问Web特性的问题,提出一种纯分布式协作缓存——PWCache。在PWCache中,其下层路由机制使用SA-Chord,上层缓存定位机制使用基于URL划分的缓存定位机制,既能克服节点之间的差异性带来的性能问题,又能利用用户访问Web的特性。实验结果表明,相对于其他基于P2P的协作缓存机制,PWCache具有更好的查询性能。     

Parallel Multithreaded Satisfiability Solver: Design and Implementation

We describe the design and implementation of a highly optimized, multithreaded algorithm for the propositional satisfiability problem. The algorithm is based on the Davis-Putnam-Logemann-Loveland sequential algorithm, but includes many of the optimization techniques introduced in recent years. We provide experimental results for the execution of the parallel algorithm on a variety of multiprocessor machines with shared memory architecture. In particular, the detrimental effect of parallel execution on the performance of processor cache is studied.     

基于实时应用的组播路由算法研究

摘要实时多媒体应用要求组播接收者在一定的时延限制之内收到组播信息,这就对组播路由提出了新的要求。该文提出了一种基于实时应用的组播路由算法,该算法以较低的通信代价建立满足时延界限的接近最优的组播树。最后简要讨论了组播接收者的动态改变时如何重建组播树的问题。     

Hierarchical Binary Set Partitioning in Cache Memories

In this paper, a new cache placement scheme is proposed to achieve higher hit ratios with respect to the two conventional schemes namely set-associative and direct mapping. Similar to set-associative, in this scheme, cache space is divided into sets of different sizes. Hence, the length of tag fields associated to each set is also variable and depends on the partition it is in. The proposed mapping function has been simulated with some standard trace files and statistics are gathered and analyzed for different cache configurations. The results reveal that the proposed scheme exhibits a higher hit ratio compared to the two well-known mapping schemes, namely set-associative and direct mapping, using LRU replacement policy.     

大规模C++工程单元测试性能优化研究

为了解决自动化单元测试工具在测试大规模C++工程时经常发生内存溢出故障且耗时较长这一问题,在测试流程中引入了缓存优化技术,并提出了一种面向不同测试方式的缓存优化方法;当用户直接对整个工程进行测试时,系统将采用缓存预取的方式,通过设计的缓存预取模型,在缓存出现读缺失之前为其提供数据块;当用户对单个文件进行测试时,系统将采用改进的GDSF替换算法进行缓存替换;实验表明,该方法能够有效地避免此类单元测试工具发生内存溢出故障并减少了测试的时间,使其支持的被测工程规模由5 000行左右增加至十几万行,大大提升了系统的性能。     

一种高性能高可靠的混合客户端缓存系统

现代数据中心普遍使用网络存储系统提供共享存储服务.存储服务端通常使用独立冗余磁盘阵列(RAID)技术保障数据可靠性,如可以容单/双盘错的RAID5/6.相比于传统磁盘,固态盘具有更低的访问时延和更高的价格,因此将固态盘作为存储客户端缓存成为一种流行的方案.写回法可以充分发挥固态盘的优势加速存储读写性能,然而一旦固态盘发生故障,写回法无法保证数据的一致性和持久性.写直达法简化了一致性模型,但是无法减小写时延.设计并实现一种新的混合客户端缓存(hybrid host cache, HHC),HHC通过使用廉价的日志磁盘镜像存放固态盘上的脏数据来提高可靠性,并且利用写屏障语义保证数据的可靠性和一致性.分析表明,HHC的平均无故障时间远远高于后端存储系统.最后实现了一个原型系统并使用Filebench进行性能评估,结果表明在不同负载下,HHC性能与传统的写回法接近,远远超过写直达法.     

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

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

面向移动Web应用的浏览器缓存性能度量与优化

随着移动互联网的飞速发展,用户越来越多地通过移动设备访问Web应用.浏览器为Web应用提供基本的计算、渲染等运行时支撑,其缓存机制可以支持Web应用直接从本地而不是通过网络来获取可复用资源,不仅能够减少整体的执行时间从而提升应用加载速度,还能够减少网络流量使用和电池电量消耗,从而保证移动Web用户体验.近年来,围绕面向移动Web应用的浏览器缓存优化得到了国内外学术界和工业界的广泛关注.然而,现有研究工作大多都是从网络层面关注浏览器缓存的整体性能,未充分考虑移动互联网用户访问行为的差异性和动态性,以及Web应用自身持续演化对浏览器实际缓存性能的影响.针对这一问题,首先设计了一种新型主动式缓存度量实验,通过仿真用户的访问行为来分析移动Web应用实际资源使用情况,揭示了浏览器缓存的理论性能上限和实际性能之间的巨大差距,并发现了造成这一差距的3个主要原因:重复请求别名资源、启发式过期时间和保守的过期时间配置.基于此发现,从应用层和平台层分别提出了两种浏览器缓存性能优化方案,并实现了原型系统.实验结果表明,采用两种方法分别平均可减少8%～51%和4%～58%的网络流量,且系统开销较小.     

面向虚拟机环境的Cache动态划分算法设计与实现

为改善虚拟化系统的cache隔离性,提高系统的整体性能,面向虚拟化环境设计并实现了一种cache动态划分算法。该算法采用页面着色的思想,通过为虚拟机分配私有颜色页面来实现cache的划分,同时能够根据虚拟机的cache需求为其动态调整cache容量。在Xen虚拟环境中实现了该算法。实验结果表明,该算法可以在较低开销的情况下,显著提高多虚拟机上并发程序的全局性能。     

Java Servlet模式的WebGIS性能优化研究*

探讨了使用Java Servlet模式实现WebGIS的优势与方法,采用GeoServer与OpenLayers结合的方式设计并实现了一种Java Servlet模式的WebGIS系统.由于服务器端性能的优劣直接影响到客户端用户的使用和体验效果,因此对WebGIS服务器端性能问题进行了深入研究,提出了JVM(Java虚...     

SQLite 的SQL 语句高速缓存技术

随着嵌入式应用领域的发展,系统功能的日趋复杂,嵌入式设备中使用嵌入式数据库越来越成为一种趋势。SQLite因其性能和功能上的优势被广泛的使用于嵌入式应用中。但是嵌入式设备CPU处理能力相对较低,存储器容量有限,制约了SQLite的性能。针对上述问题,根据高速缓存原理,简化SQL语句执行过程中的词法分析、语法分析过程,以减少运行过程中的时间消耗。实验表明,本方法可有效提高SQL语句执行效率,在保持可用性与可靠性的前提下,提升SQLite的整体性能。     

支持内存数据库索引缓存优化的CST树的设计与实现

针对目前内存数据库中索引缓存失配的问题,在分析了现有内存数据库索引结构基础上,提出了一种缓存敏感T树（CST树）的索引数据结构,详细数据结构描述和操作算法也已给出。通过CST树的缓存次数分析和进行查询、插入等操作性能测试,结果表明CST树能有效减少缓存敏感次数,并且在数据量较小时,CST树的插入、删除速度比T树略慢,而查询速度比T树要快。在数据量较大时,CST树的插入、删除、查询效率都比T树要高。