一种面向闪存键值存储的矩阵索引布鲁姆过滤器

A Matrix-Indexed Bloom Filter for Flash-Based Key-Value Store

索引结构是提高闪存键值存储插入和查询性能的关键技术之一.在分析目前相关索引结构特点的基础上提出了一种面向闪存键值存储的矩阵索引布鲁姆过滤器(matrix-indexed Bloom filter,MIBF),由m×s的位矩阵表示的多个布鲁姆过滤器组(multiple Bloom filter group,MBFG)和一个附加布鲁姆过滤器(additional Bloom filter,ABF)组成,其核心思想是键值对的闪存页地址被拆分为多组位串,每组位串采用MBFG中的一组布鲁姆过滤器(Bloom filter,BF)来表示,同时将键值对的Key与闪存页地址组合值存入ABF中.根据Key查询Value时,MBFG中的每组BF产生多位,组合生成键值对的闪存页地址,并通过ABF滤掉部分伪闪存页地址达到较精确地址定位,从而降低闪存访问次数,提高系统性能.与已有类似方法相比,MIBF的查询地址定位精度提高,内存和闪存访问次数降低明显,插入和查询性能显著提升.

Flash-based key-value store, an important type of NoSQL database, has been widely used to store and query data. Indexing structure is an effective organization of data in the store system, which is one of the key technologies to improve the performance of system insertion and query. On the analysis of the characteristics and shortcomings of current and relevant indexing structure, matrix-indexed Bloom filter （MIBF） for flash-based key-value store is proposed. MIBF is composed of multiple Bloom filter group （MBFG） represented by m×s bits matrix and additional Bloom filter （ABF）. The core idea of MIBF is that flash page address of key-value pair is split into multiple bit groups, and MBFG is also divided into multiple groups correspondingly, and each group bits are represented by one group Bloom filter （BF） in MBFG, while the combined value of key and flash page address is inserted into ABF. When an element is queried according to the key, each BF group in MBFG generates a plurality of bit values and combines to generate the flash page address for the key-value pairs. In order to reduce pseudo flash page address generated by the MBFG due to false positive probability, pseudo flash page addresses are filtered out through the ABF, thereby achieving more accurate address location, reducing the number of flash access, and improving the system performance. Compared with previous work, the address location accuracy of MIBF query is improved and the access number of RAM and flash is decreased significantly, which greatly improves the performance of solid state disk （SSD） insertion and query.