闪存数据库系统中一种高效的自适应存储模式

使用闪存作为存储介质成为提高数据库系统性能的一条新途径,为了解决闪存数据库系统存储管理技术中基于日志的更新策略存在查询效率低、日志区空间分配不合理、索引更新代价高等问题,提出了基于Bloom Filter的最新版本预测算法,引入记录定位器结构,提出日志概要结构和基于闪存更新查询代价评估模型的自适应机制。实验证明,该方法能够自适应地划分合理的日志区空间,有效提高查询性能,减少各种非聚集索引的更新代价。     

LD_B~+树:闪存系统上一种DBMS索引结构

以往的研究大多针对文件系统,而DBMS存在更多细粒度的更新.本文综合考虑闪存自身的特点、设备种类繁多及不同闪存设备读写特性差别大等,提出了一种基于闪存的DBMS索引结构:LD_B+树.LD_B+树根据工作负载的读写特性动态地调节索引模式使之能够适应于不同种类的闪存设备.LD_B+树采用日志结构组织结点,通过结点转换表和日志缓冲区维护索引结构.模拟实验结果表明,不同闪存设备及工作负载下,LD_B+索引结构比B+树和日志型B+树(BFTL)具有6%-63%的性能提高.     

一种自适应的闪存存储管理方法

针对数据库的数据访问特点和已有的闪存存储管理方法的不足,提出一种新的自适应的闪存存储管理方法AFS.AFS方法将逻辑页区分为日志和非日志两种模式,并采用不同的更新方法;同时能够根据负载的变化自适应地调整逻辑页的模式.实验结果表明,AFS方法能够在提高闪存数据更新性能的同时较好地兼顾数据读取性能.     

一种应用于闪存数据库的高效B+树索引机制

为解决现有闪存数据库索引机制无法同时具备高索引更新性能和高检索性能的问题,提出一种应用于闪存数据库的高效B+树索引机制。该机制采用日志方式更新索引,利用日志缓存区保证日志快速写入闪存。针对日志方式检索效率低的缺陷,设计节点日志映射表,通过哈希映射直接索引节点更新记录,避免全局搜索节点日志。将更新日志整合为B+树逻辑节点,使索引检索转化为B+树深度搜索,在此基础上设计节点缓存区,提高节点检索效率。实验结果表明,该机制相比日志型索引机制BFTL,更新效率提高了51%、检索效率提高了2.3倍,相比基于Nand闪存转换层的B+树索引机制,在保证与其相当的高检索效率的同时,更新效率提高了2.4倍。     

ALERT:基于Radix Tree的工作负载自适应学习型索引

学习型索引通过学习数据分布可以准确地预测数据存取的位置,在保持高效稳定的查询下,显著降低索引的内存占用.现有的学习型索引主要针对只读查询进行优化,而对插入和更新支持不足.针对上述挑战,设计了一种基于Radix Tree的工作负载自适应学习型索引ALERT.ALERT使用Radix Tree来管理不定长的分段,段内采用具有最大误差界的线性插值模型进行预测.同时,ALERT使用一种高效的插入缓冲来降低数据插入更新的代价.针对点查询和范围查询提出两种自适应重组优化方法,通过对工作负载进行感知,动态地调整插入缓冲的组织结构.经实验验证,ALERT与业界流行的学习型索引相比,构建时间平均降低了81%,内存占用平均降低了75%,在保持了优秀读性能的同时,使插入延迟平均降低了50%;此外,ALERT使用自适应重组优化能有效感知查询工作负载特征,与不使用自适应重组优化相比,查询延迟平均降低了15%.     

闪存环境下B+树索引重访

闪存容量的增大使在其上构建大型系统成为可能,如何构建闪存数据库也成为数据库的热点研究领域之一。索引结构是数据库中必不可少的结构之一,而B+树是最广泛使用的索引结构。这里对存储在闪存芯片模拟器及固态硬盘上的B+树性能进行了测试及分析。首先介绍了闪存的IO特点,并测试了固态硬盘的基本IO特性。接着,对B+树的插入和查询效率进行了详细地测试。测试发现节点大小,缓存大小,以及数据值的分布方式都会对B+树的性能带来很大影响。例如由于闪存的读取速度不对称,闪存的更新和查询操作最优块大小相差较大。这些测试结果为更好地在闪存上使用B+树索引,并进一步设计出更适合闪存的索引提供了指导。     

一种针对闪存的高效缓冲区置换算法

随着闪存容量的不断增长和闪存应用的日益广泛,针对闪存的缓冲区管理已成为一个迫切需要解决的问题.针对闪存的写代价显著高于读代价的特性,提出一种针对闪存的页面置换算法LEAC.LEAC根据页面的读写负载和闪存的读写代价差异对换出页面引起的预期闪存访问开销进行评估,优先换出预期访问开销最低的页.实验表明,LEAC可以显著降低闪存访问开销.     

一种针对块内日志存储模型的缓冲区管理方法

闪存的擦后写特性,使其对小粒度随机更新为主的数据库应用,存在较大的更新时延.基于块内日志的存储管理模型提出了一种使用日志的方法,有效地解决了该问题.但是由于没有考虑数据访问的冷热特性,使得热擦除块合并操作非常频繁,同时它们采用的强制日志刷新策略导致闪存日志区存在严重的碎片问题.针对上述问题,本文提出一种基于数据冷热检测的双链表缓冲区算法DLPA,它根据数据的访问特性动态地分配日志页大小,可以有效减少擦除块合并操作,同时在日志刷新至闪存时,结合两种日志打包策略,有效地改善了日志区碎片问题.实验显示,该算法在增加少量存储开销的前提下,显著地优于现有算法.     

基于更新日志的移动对象索引方法

在TPR-tree上增加一个基于内存的更新日志,实现一种支持频繁更新的移动对象索引ULTPR-tree,采用分组更新方法对移动对象记录进行批量删除,从而减少ULTPR-tree索引结构的删除维护代价。理论分析和实验结果表明,ULTPR-tree的动态更新性能优于TPR-tree和HTPR-tree。     

HF-Tree:一种闪存数据库的高更新性能索引结构

随着电子技术的发展,闪存作为一种新型的电子存储设备具有高速的访问速度和无机械延迟的特性.但是由于闪存高昂的写操作代价,传统的基于磁盘的索引结构如果直接应用在闪存上会导致极差的更新性能.提出一种新颖的索引结构HF-Tree,通过组提交、更新合并以及多级延迟的方式来提高更新性能.HF-Tree能够有效地克服闪存和现有基于磁盘索引之间的不匹配性的问题.通过和经典的BFTL及IPL索引的性能比较,实验结果充分显示了HF-Tree优越的更新和查询性能.此外HF-Tree能够有效地减少擦除次数,从而延长闪存的使用寿命.     

纠错码拜占庭容错Quorum中错误检测机制

摘要在大规模存储系统中，拜占庭存储节点的容错显得越来越重要。传统拜占庭Quorum通过复制可以容忍拜占庭失效，但是它们有两个主要缺点：低的存储空间利用率和静态quorum参数。我们提出纠错码拜占庭容错Quorum（Erasure-code Byzantine Fault-tolerance Quorum, E-BFQ），E-BFQ采用纠错码作为冗余策略，可以提供高可靠性，同时比复制占用更少存储空间。通过客户端读／写操作和管理器诊断操作，E-BFQ可以检测拜占庭节点，动态调整系统规模和故障闽值。结果显示本文方法可以达到动态调整的目的。     

An effective pre-store/pre-load method exploiting intra-request idle time of NAND flash-based storage devices

NAND flash-based storage devices (NFSDs) are widely employed owing to their superior characteristics when compared to hard disk drives. However, NAND flash memory (NFM) still exhibits drawbacks, such as a limited lifetime and an erase-before-write requirement. Along with effective software management, the implementation of a cache buffer is one of the most common solutions to overcome these limitations. However, the read/write performance becomes saturated primarily because the eviction overhead caused by limited DRAM capacity significantly impacts overall NFSD performance. This paper therefore proposes a method that hides the eviction overhead and overcomes the saturation of the read/write performance. The proposed method exploits the new intra-request idle time (IRIT) in NFSD and employs a new data management scheme. In addition, the new pre-store eviction scheme stores dirty page data in the cache to NFMs in advance. This reduces the eviction overhead by maintaining a sufficient number of clean pages in the cache. Further, the new pre-load insertion scheme improves the read performance by frequently loading data that needs to be read into the cache in advance. Unlike previous methods with large migration overhead, our scheme does not cause any eviction/insertion overhead because it actually exploits the IRIT to its advantage. We verified the effectiveness of our method, by integrating it into two cache management strategies which were then compared. Our proposed method reduced read latency by 43% in read-intensive traces, reduced write latency by 40% in write-intensive traces, and reduced read/write latency by 21% and 20%, respectively, on average compared to NFSD with a conventional write cache buffer.     

支持高并发访问的新型NVM存储系统

I/O系统软件栈是影响NVM存储系统性能的重要因素。针对NVM存储系统的读写速度不均衡、写寿命有限等问题，设计了同异步融合的访问请求管理策略；在使用异步策略管理数据量较大的写操作的同时，仍然使用同步策略管理读请求和少量数据的写请求。针对多核处理器环境下不同计算核心访问存储系统时地址转换开销大的问题，设计了面向多核处理器地址转换缓存策略，减少地址转换的时间开销。最后实现了支持高并发访问NVM存储系统（CNVMS）的原型，并使用通用测试工具进行了随机读写、顺序读写、混合读写和实际应用负载的测试。实验结果表明，与PMBD相比，所提策略能提高1%~22%的读写速度和9%~15%的IOPS，验证了CNVMS策略能有效提高NVM存储系统的I/O性能和访问请求处理速度。     

Read/write-optimized tree indexing for solid-state drives

Flash-memory-based solid-state drives (SSDs) are used widely for secondary storage. To be effective for SSDs, traditional indices have to be redesigned to cope with the special properties of flash memory, such as asymmetric read/write latencies (fast reads and slow writes) and out-of-place updates. Previous flash-optimized indices focus mainly on reducing random writes to SSDs, which is typically accomplished at the expense of a substantial number of extra reads. However, modern SSDs show a narrowing gap between read and write speeds, and read operations on SSDs increasingly affect the overall performance of indices on SSDs. As a consequence, how to optimize SSD-aware indices by reducing both write and read costs is a pertinent and open challenge. We propose a new tree index for SSDs that is able to reduce both writes and extra reads. In particular, we use an update buffer and overflow pages to reduce random writes, and we further exploit Bloom filters to reduce the extra reads to the overflow nodes in the tree. With this mechanism, we construct a read/write-optimized index that is capable of offering better overall performance than previous flash-aware indices. In addition, we present an analysis of the proposed index and show that the read and write costs of the operations on the index can be balanced by only tuning the false-positive rate of the Bloom filters. Our experimental results suggest that our proposal is efficient and represents an improvement over existing methods.     

A novel dynamic network data replication scheme based on historical access record and proactive deletion

Data replication is becoming a popular technology in many fields such as cloud storage, Data grids and P2P systems. By replicating files to other servers/nodes, we can reduce network traffic and file access time and increase data availability to react natural and man-made disasters. However, it does not mean that more replicas can always have a better system performance. Replicas indeed decrease read access time and provide better fault-tolerance, but if we consider write access, maintaining a large number of replications will result in a huge update overhead. Hence, a trade-off between read access time and write updating cost is needed. File popularity is an important factor in making decisions about data replication. To avoid data access fluctuations, historical file popularity can be used for selecting really popular files. In this research, a dynamic data replication strategy is proposed based on two ideas. The first one employs historical access records which are useful for picking up a file to replicate. The second one is a proactive deletion method, which is applied to control the replica number to reach an optimal balance between the read access time and the write update overhead. A unified cost model is used as a means to measure and compare the performance of our data replication algorithm and other existing algorithms. The results indicate that our new algorithm performs much better than those algorithms.     

一种嵌入式微处理器中的在线调试模块设计

文章提出了一种嵌入式微处理器的在线调试模块。这个模块可以用较少的硬件开支实现一些强大的调试功能:响应硬件和软件触发,提供开始/停止调试模试;单步调试操作;程序执行的跟踪;代码内存、外部数据存储器、SFR、内部数据存储器的读和写。文章首先介绍了嵌入式微处理器可调试模块设计的原理,其次介绍了在线调试的结构设计,最后给出结论和分析。     

An index selection method without repeated optimizer estimations

The index selection problem (ISP) concerns the selection of an appropriate index set to minimize the total cost for a given workload containing read and update queries. Since the ISP has been proven to be an NP-hard problem, most studies focus on heuristic algorithms to obtain approximate solutions. However, even approximate algorithms still consume a large amount of computing time and disk space because these systems must record all query statements and frequently request from the database optimizers the cost estimation of each query in each considered index. This study proposes a novel algorithm without repeated optimizer estimations. When a query is delivered to a database system, the optimizer evaluates the costs of various query plans and chooses an access path for the query. The information from the evaluation stage is aggregated and recorded with limited space. The proposed algorithm can recommend indexes according to the readily available information without querying the optimizer again. The proposed algorithm was tested in a PostgreSQL database system using TPC-H data. Experimental results show the effectiveness of the proposed approach.     

Multiversion concurrency control for the generalized search tree

Many read‐intensive systems where fast access to data is more important than the rate at which data can change make use of multidimensional index structures, like the generalized search tree (GiST). Although in these systems the indexed data are rarely updated and read access is highly concurrent, the existing concurrency control mechanisms for multidimensional index structures are based on locking techniques, which cause significant overhead. In this article we present the multiversion‐GiST (MVGiST), an in‐memory mechanism that extends the GiST with multiversion concurrency control. The MVGiST enables lock‐free read access and ensures a consistent view of the index structure throughout a reader's series of queries, by creating lightweight, read‐only versions of the GiST that share unchanging nodes among themselves. An example of a system with high read to write ratio, where providing wait‐free queries is of utmost importance, is a large‐scale directory that indexes web services according to their input and output parameters. A performance evaluation shows that for low update rates, the MVGiST significantly improves scalability w.r.t. the number of concurrent read accesses when compared with a traditional, locking‐based concurrency control mechanism. We propose a technique to control memory consumption and confirm through our evaluation that the MVGiST efficiently manages memory. Copyright © 2009 John Wiley & Sons, Ltd.     

基于倒排表与B+树的联合索引技术

为提高XML文档的查询效率,提出一种基于倒排表与B+树的联合索引技术。DTD结构索引和内容索引采用倒排表作为索引单位,XML文档索引使用B+树作为索引基本组织。在DTD结构索引的结点编码中设置标识信息,便于确定需要查询的文档。通过建立DTD结构索引、XML文档索引和内容索引,实现混合型XML文档的查询。理论分析与实验结果表明,该技术具有较小的空间开销和较高的查询效率。     

Write-Optimized B+ Tree Index Technology for Persistent Memory

Due to its low latency,byte-addressable,non-volatile,and high density,persistent memory (PM) is expected to be used to design a high-performance storage system.However,PM also has disadvantages such as limited endurance,thereby proposing challenges to traditional index technologies such as B+ tree.B+ tree is originally designed for dynamic random access memory (DRAM)-based or disk-based systems and has a large write amplification problem.The high write amplification is detrimental to a PM-based system.This paper proposes WO-tree,a write-optimized B+ tree for PM.WO-tree adopts an unordered write mechanism for the leaf nodes,and the unordered write mechanism can reduce a large number of write operations caused by maintaining the entry order in the leaf nodes.When the leaf node is split,WO-tree performs the cache line flushing operation after all write operations are completed,which can reduce frequent data flushing operations.WO-tree adopts a partial logging mechanism and it only writes the log for the leaf node.The inner node recognizes the data inconsistency by the read operation and the data can be recovered using the leaf node information,thereby significantly reducing the logging overhead.Furthermore,WO-tree adopts a lock-free search for inner nodes,which reduces the locking overhead for concurrency operation.We evaluate WO-tree using the Yahoo!Cloud Serving Benchmark(YCSB) workloads.Compared with traditional B+ tree,wB-tree,and Fast-Fair,the number of cache line flushes caused by WO-tree insertion operations is reduced by 84.7％,22.2％,and 30.8％,respectively,and the execution time is reduced by 84.3％,27.3％,and 44.7％,respectively.