高级检索

    HyperTree:高并发B+树索引加速器

    HyperTree: High Concurrent B+tree Index Accelerator

    • 摘要: B+树是关系型数据库中用来加速查询的常用索引结构,通过构建平衡树维护关键属性的顺序. 索引提升了数据库查询性能,但其严格的有序关系增加了数据库表的维护开销. 特别是在大数据场景下,数据量激增使得索引查询和维序性能进一步下降. 如何平衡B+树的查询和维序性能,以及在大数据场景下提升索引查询和维序的效率,对提升索引系统性能具有重要意义. 由此设计了一种专用的B+树索引加速系统,对存储和计算进行协同优化,均衡提升索引查询和维序性能. 利用内存突发读写高带宽的特性设计规则的树和节点存储格式以提升内存带宽利用效率,设计高效的同构计算架构和多数据通道以提升索引操作并行度. 同时设计解耦合的子树结构缓解索引维护时的树读写冲突. 实验结果表明,相比于CPU,B+树索引加速系统能够提升系统查询性能超过6.84倍,提升索引维序性能提升超过29.14倍.

       

      Abstract: B+tree is the most commonly used index structure to improve query performance in relational databases. It maintains the order of key attributes in the database by building a balanced tree. The index improves database query performance but introduces index maintenance overheads, which include index updating, index deletion and index insertion, because of the high sequential order of the B+tree. Additionally, the performance of the B+tree will be further damaged by the huge amount of data under the circumstance of big data. Therefore, it is significant to balance index performance between the requirement of query and maintenance in B+tree systems while improving the index operation efficiency. To tackle these problems in big data applications, a domain-specific B+tree accelerator, called HyperTree, is proposed to boost the performance of B+tree operations including both index query and index maintenance. HyperTree co-optimizes both memory bandwidth and computation efficiency to fully utilize resources on the domain-specific accelerator. Specifically, to improve memory bandwidth utilization, the structures of the node and the B+tree are designed based on the characteristic of high bandwidth utilization in memory burst read/write; to improve computation parallelism and concurrency, multiple homogeneous computing engines and multiple data channels are configured to fully utilize hardware resources and reduce control overheads. In addition, to eliminate the block of index maintenance operations, a sub-tree system is proposed to uncouple the nodes in B+tree. The results of experiments show that compared with CPU, the FPGA-based B+tree accelerator achieves 6.84 times boosts in the throughput of query transactions and 29.14 times boosts in the throughput of index insertion.

       

    /

    返回文章
    返回