DART: distributed adaptive radix tree for efficient affix-based keyword search on HPC systems
DART: distributed adaptive radix tree for efficient affix-based keyword search on HPC systems
复制标题
DOI：
10.1145/3243176.3243207
复制
发表时间：
2018-11
期刊：
影响因子：
--
通讯作者：
Wei Zhang;Houjun Tang;S. Byna;Yong Chen
中科院分区：
文献类型：
--
作者：
Wei Zhang;Houjun Tang;S. Byna;Yong Chen
基于词缀的搜索是存储系统的基本功能。它允许用户找到所需的数据集，其中数据集的属性与词缀匹配。虽然构建倒排索引以促进高效的基于词缀的关键字搜索是独立数据库和桌面文件系统的常见实践，但是由于系统内的存储设备的大量数据和分布式性质，构建本地索引或采用独立数据存储中使用的索引技术对于高性能计算（HPC）系统是不够的。在本文中，我们提出了分布式自适应基数树（DART），以解决分布式词缀为基础的关键字搜索HPC系统的挑战。这种基于trie树的方法在实现高效的基于词缀的搜索和减轻不平衡的关键字分布和对关键字的过度请求方面是可扩展的。我们在不同规模下的评估表明，与最流行的分布式索引技术-分布式哈希表（DHT）的“全字符串哈希”用例相比，DART在前缀搜索和后缀搜索的情况下实现了高达55倍的吞吐量，同时在精确和中缀搜索的情况下实现了相当的吞吐量。此外，与DHT的“初始散列”用例相比，DART在分布式节点上保持了平衡的关键字分布，并消除了针对流行关键字的过多查询工作量。
Affix-based search is a fundamental functionality for storage systems. It allows users to find desired datasets, where attributes of a dataset match an affix. While building inverted index to facilitate efficient affix-based keyword search is a common practice for standalone databases and for desktop file systems, building local indexes or adopting indexing techniques used in a standalone data store is insufficient for high-performance computing (HPC) systems due to the massive amount of data and distributed nature of the storage devices within a system. In this paper, we propose Distributed Adaptive Radix Tree (DART), to address the challenge of distributed affix-based keyword search on HPC systems. This trie-based approach is scalable in achieving efficient affix-based search and alleviating imbalanced keyword distribution and excessive requests on keywords at scale. Our evaluation at different scales shows that, comparing with the "full string hashing" use case of the most popular distributed indexing technique - Distributed Hash Table (DHT), DART achieves up to 55× better throughput with prefix search and with suffix search, while achieving comparable throughput with exact and infix searches. Also, comparing to the "initial hashing" use case of DHT, DART maintains a balanced keyword distribution on distributed nodes and alleviates excessive query workload against popular keywords.