基于无锁结构的大容量数据高性能检索系统研究

发布时间：2019-02-11 09:41

【摘要】：处理器的发展趋势由高频转向多核,普通的桌面PC有望在2017年末2018年初达到24核心(或者16核32线程),主流服务器的CPU核心数也都达到12核以上。基于锁同步机制的大容量数据检索系统在各方面无法发挥多核CPU的优势,开发过程中经常容易引入非常严重的缺陷,增加了引起死锁和数据竞争等严重问题的风险。同时随着核数的增加性能出现严重下降,不具备可扩展性。近年来软件开发者开始对无锁(Lock Free)数据结构进行不断研究,使用CAS的细粒度同步原语的无锁数据结构能够摆脱死锁和数据竞争问题,更重要的是它对于多核是可扩展的。业界也有诸多基于无锁的数据结构库。将这类结构应用到检索系统中,将会对检索的性能产生显著提升。本文以对现有电商商品检索系统的改进为背景,以无锁数据结构相关技术为切入点,对大容量数据高性能检索系统的实现进行了研究。具体工作可以概括为以下几点:本文首先对高性能检索系统的现状和发展趋势进行了深入分析。研究了当前检索系统在数据结构使用上的现状和局限性,分析了各类数据结构在多核计算机系统场景下所面临的问题和挑战,阐述了研究无锁数据结构对检索系统带来的作用和意义。其次,研究了大容量数据高性能检索系统的总体技术。概括性的介绍了检索系统的各组成部分及其功能,以及使用到的主要的数据结构。重点分析了 RPC消息队列、正排检索和倒排检索。然后,对RPC消息队列、正排检索和倒排检索进行无锁化结构重新设计,确定了各数据结构方案,并进行了设计和性能测试。利用无锁CAS技术提出了新的无锁队列、受限的无等待跳跃列表和受限的无等待散列表结构,并与现有常用的有锁的各类方法进行了对比,并进行了工程实践,并最终将这些新的数据结构应用到大容量数据检索系统中去。最后在单机的工作条件下,对新旧两种检索系统在相同的条件下进行检索正确率和召回率测试,在保证检索系统的检索正确率以及召回率的前提下验证了新的检索系统的检索性能改善。
[Abstract]:The development trend of processors is from high frequency to multi-core. The average desktop PC is expected to reach 24 cores (or 16 cores and 32 threads) by the end of 2017 or early 2018, and the number of CPU cores of mainstream servers will reach more than 12 cores. The large capacity data retrieval system based on lock synchronization mechanism can not play the advantage of multi-core CPU in all aspects. It is often easy to introduce very serious defects in the development process, which increases the risk of serious problems such as deadlock and data competition. At the same time, with the increase of the number of kernels, the performance is seriously decreased, and it is not extensible. In recent years, software developers have begun to study the unlocked (Lock Free) data structure. Using the fine-grained synchronization primitive of CAS, the unlocked data structure can get rid of deadlock and data competition, and more importantly, it is extensible for multi-core. There are also many lock-free-based data structure libraries in the industry. Applying this kind of structure to retrieval system will greatly improve the performance of retrieval. In this paper, based on the improvement of the existing e-commerce commodity retrieval system and the related technology of unlocked data structure, the realization of the large capacity and high performance retrieval system is studied. The specific work can be summarized as follows: firstly, the present situation and development trend of high performance retrieval system are deeply analyzed in this paper. In this paper, the present situation and limitation of data structure in retrieval system are studied, and the problems and challenges of data structure in multi-core computer system are analyzed. The function and significance of studying unlocked data structure on retrieval system are expounded. Secondly, the overall technology of large-capacity high-performance data retrieval system is studied. The components and functions of the retrieval system and the main data structures used are introduced in this paper. The RPC message queue, forward retrieval and inverted retrieval are analyzed in detail. Then, the unlocked structure of RPC message queue, forward row retrieval and inverted retrieval are redesigned, each data structure scheme is determined, and the design and performance test are carried out. This paper presents a new unlocked queue, a constrained waiting hopping list and a restricted waiting free hash table structure by using the lock free CAS technology, and compares it with other commonly used lock methods, and carries out the engineering practice. Finally, these new data structures are applied to mass data retrieval system. Finally, under the working conditions of a single machine, the retrieval accuracy and recall rate of the new and old retrieval systems are tested under the same conditions. The performance improvement of the new retrieval system is verified under the premise of guaranteeing the retrieval accuracy and recall rate of the new retrieval system.
【学位授予单位】：东南大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP391.3

【相似文献】