支持高效更新的移动对象索引研究

基于TPR-树(Time parameterized R-tree,TPR-树)提出的LUTPR-树采用基于主存的更新方法,更新对象的删除操作在内存中完成,故避免了TPR-树中对象更新所导致的耗时的查找操作。同时,LUTPR-树能有效利用主存资源。实验结果表明,与TPR-树相比,LUTPR-树以牺牲很小部分查询性能为代价,大大提高了更新效率,更加适用于更新密集型应用。

Using multi-threads to hide deduplication I/O latency with low synchronization overhead

Data deduplication, as a compression method, has been widely used in most backup systems to improve bandwidth and space efficiency. As data exploded to be backed up, two main challenges in data deduplication are the CPU-intensive chunking and hashing works and the I/0 intensive disk-index access latency. However, CPU-intensive works have been vastly parallelized and speeded up by multi-core and many-core processors; the I/0 latency is likely becoming the bottleneck in data deduplication. To alleviate the challenge of I/0 latency in multi-core systems, multi-threaded deduplication （Multi-Dedup） architecture was proposed. The main idea of Multi-Dedup was using parallel deduplication threads to hide the I/0 latency. A prefix based concurrent index was designed to maintain the internal consistency of the deduplication index with low synchronization overhead. On the other hand, a collisionless cache array was also designed to preserve locality and similarity within the parallel threads. In various real-world datasets experiments, Multi-Dedup achieves 3-5 times performance improvements incorporating with locality-based ChunkStash and local-similarity based SiLo methods. In addition, Multi-Dedup has dramatically decreased the synchronization overhead and achieves 1.5-2 times performance improvements comparing to traditional lock-based synchronization methods.

频繁更新环境下的移动对象索引研究

基于TPR*-树提出一种能有效减少更新开销的索引结构EUTPR*-树(Efficient Update TPR*-tree)。EUT-PR*-树采用基于主存的更新方法,更新时对象的删除操作在内存中完成,避免了TPR*-树中对象更新所导致的耗时的查找过期数据项的操作。同时,EUTPR*-树能有效利用主存资源。实验结果表明,与TPR*-树相比,EUTPR*-树以稍稍牺牲一部分查询性能为代价,大大提高了更新效率,更加适用于更新密集型应用。