一种多核环境下哈希表并发访问性能优化方法

摘要

本发明公开了一种多核环境下哈希表并发访问性能优化方法，包括：针对哈希表高并发访问的并发连接处理，采用半同步半异步的网络连接处理机制；针对哈希表高并发访问的并发数据处理，将哈希表按CPU核心数划分成多个独立的子哈希表，每个工作线程和一个独立的子哈希表一一对应，每个工作线程只负责处理自己对应的子哈希表的数据；主线程根据每个数据的Key采用一致性哈希策略选择相应的工作线程处理；每个子哈希表维护一个LRU队列，当内存空间不足时，剔除冷数据，插入新的元素。本发明方法提高了并发连接处理能力和哈希表的并发访问能力，同时消除了解决多线程访问共享哈希表时的同步开销和cache一致性开销的问题。

说明书

技术领域

本发明属于多核软件性能优化的领域，更具体地，涉及一种多核环境 下哈希表并发访问性能优化方法。

背景技术

哈希表是一种常用的数据结构，它通过把关键码值映射到表中一个位 置来访问记录，以加快查找的速度。由于其高效的查找效率，在存储系统、 搜索引擎等实际应用中有着广泛的使用，例如数据库中的哈希索引，缓存 系统中的哈希表结构等。单核处理器通过提高主频来提升处理器的性能， 然而随之带来的功耗和散热问题却成为处理器速度进一步提高的瓶颈。随 后处理器厂商开始横向扩展CPU，在一个处理器上集成多个计算核心，即多 核架构。从单核到多核,改变的不仅仅是处理器核心的数量，还有处理器 体系结构、I/O，甚至是计算机的整体架构，这需要人们调整数据处理算法 设计的理念，即如果想获得较好的性能，必须设计多核敏感的数据结构和 算法。多核处理器的兴起和广泛使用给传统软件开发带来了新的挑战，如 何利用多核提供的并行化优势来提升软件的性能成为亟待解决的问题。于 是，多核环境下哈希表的高效并发访问就成为一个重要的研究课题。

发明内容

针对现有技术的以上缺陷或改进需求，本发明提供了一种多核环境下 哈希表并发访问性能优化方法。其目的在于解决现有方法中存在的高并发 连接处理、锁竞争、cache一致性开销和系统可扩展性的技术问题。

本发明提供了一种多核环境下哈希表并发访问性能优化方法，包括：

针对哈希表高并发访问的并发连接处理，采用半同步半异步的网络连 接处理机制，在系统中设置主线程和工作线程，主线程利用异步非阻塞机 制接受新的连接，并将已接受的连接分发到工作线程，由工作线程负责具 体的逻辑处理；

针对哈希表高并发访问的并发数据处理，将哈希表按CPU核心数划分 成多个独立的子哈希表，每个工作线程和一个独立的子哈希表一一对应， 每个工作线程只负责处理自己对应的子哈希表的数据；

主线程根据每个数据的Key采用一致性哈希策略选择相应的工作线程 处理；

每个子哈希表维护一个LRU队列，当内存空间不足时，剔除冷数据， 插入新的元素。

进一步地，所述针对哈希表高并发访问的并发连接处理，具体优化方式 为：

主线程负责接受连接请求，将该新连接push到工作线程的连接队列中； 主线程和工作线程之间通过管道进行通讯,主线程将新的连接push到工作线 程之后，主线程向该工作线程的管道中写一个字符，每个工作线程也有自 己的poll set，其中会包含自己的管道fd；

工作线程通过多路复用I/O来监控管道的情况，一旦可读，说明有新的 连接到来，此时从连接队列中取出新连接，将其fd加入到自身的poll set 中；

对该连接的业务逻辑处理也全都在该工作线程中进行，包括读数据， 处理，以及发送回应。

进一步地，所述主线程根据每个数据的Key采用一致性哈希策略选择相 应的工作线程处理，具体优化方式为：

给每个工作线程分配一个线程号，线程号从0到N，N为工作线程数目， 通过预设的Hash函数计算出每个工作线程号的哈希值，并将其映射到0～2 的32次方的圆环上；

当主线程接受一个连接请求时，通过相同的Hash函数计算出该请求数 据的key对应的哈希值，将其也映射到圆环中，然后从映射到的位置开始 顺时针查找，将连接请求分配给找到的第一个工作线程处理。

进一步地，所述主线程根据每个数据的Key采用一致性哈希策略选择 相应的工作线程处理，具体处理为：执行SET或GET操作。

总体而言，通过本发明所构思的以上技术方案与现有技术相比，能够 取得下列有益效果：

(1)针对哈希表高并发访问的并发连接处理，采用半同步半异步的网 络连接处理机制，将可能阻塞的操作放在工作线程中，这样不会影响到主 线程对网络连接的处理，主线程采用异步非阻塞机制可以提高网络IO效率， 支持大量并发连接。

(2)将哈希表按CPU核心数划分成独立的子哈希表，对每个子哈希表 的操作不会涉及到其它核心，这样就避免了cache一致性开销，同时也能 提高cache的命中率。

(3)利用一致性哈希策略选择工作线程，将已接受的连接分发给该线 程。与简单的哈希策略相比，一致性哈希数据分布策略可以避免单点失效 造成整个系统不可用，同时使得动态调整线程数目成为可能，一致性哈希 也使得数据的分布更加的均匀，即提高了系统的可扩展性、可用性和负载 均衡能力。

(4)子哈希表维护一个LRU队列，当内存空间不足时，LRU策略剔 除冷数据，插入新的元素，提高热点数据的访问效率，热点数据在内存和 磁盘之间的交换次数。

附图说明

图1为本发明系统整体架构示意图；

图2为多核环境下哈希表的划分示意图；

图3为子哈希表的结构示意图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图 及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体 实施例仅仅用以解释本发明，并不用于限定本发明。此外，下面所描述的 本发明各个实施方式中所涉及到的技术特征只要彼此之间未构成冲突就可 以相互组合。

系统的整体架构如图1所示，本发明一种多核环境下哈希表并发访问性 能优化方法，包括以下技术特点：

(1)针对哈希表高并发访问的并发连接处理，采用半同步半异步的网 络连接处理机制。在系统中设置主线程和工作线程，主线程利用异步非阻 塞机制接受新的连接，并将已接受的连接分发到工作线程，由工作线程负 责具体的逻辑处理。

主线程负责接受连接请求，将该新连接push到工作线程的连接队列中。 主线程和工作线程之间通过管道进行通讯,因此主线程将新的连接push到工 作线程之后，主线程要向该工作线程的管道中写一个字符，而每个工作线 程也都有自己的poll set，其中会包含自己的管道fd。

工作线程也会通过多路复用I/O来监控管道的情况，一旦可读，说明有 新的连接到来，此时从连接队列中取出新连接，将其fd加入到自身的poll set 中。

最后对该连接的业务逻辑处理也全都在该工作线程中进行(读数据，处 理，发送回应等)。

本技术的优势在于将可能阻塞的操作放在工作线程中，这样不会影响到 主线程对网络连接的处理，主线程采用异步非阻塞机制可以提高网络IO效 率，支持大量并发连接。

(2)针对哈希表高并发访问的并发数据处理，将哈希表按CPU核心数 划分成多个独立的子哈希表。每个工作线程和一个独立的子哈希表一一对 应，每个工作线程只负责处理自己对应的子哈希表的数据。

例如图2所示，CPU有四个核心，则将哈希表划分成四个独立的子哈希 表，每个子哈希表由专门的工作线程负责其所有操作，同时利用CPU亲和 力将工作线程固定在相应的核心上，工作线程访问相应的子哈希表不用加 锁。

本技术的优势在于工作线程之间不存在锁竞争，对每个子哈希表的操作 不会涉及到其它核心，这样就避免了cache一致性开销，同时也能提高cache 的命中率。

(3)主线程根据每个数据的Key采用一致性哈希策略选择相应的工作 线程处理(执行SET或GET操作)。

首先给每个工作线程分配一个线程号(从0到N，N为工作线程数目)， 通过特定的Hash函数计算出每个工作线程号的哈希值，并将其映射到0～2 的32次方的圆环上。

当主线程接受一个连接请求时，通过相同的Hash函数计算出该请求数 据的key对应的哈希值，将其也映射到圆环中。然后从映射到的位置开始 顺时针查找，将连接请求分配给找到的第一个工作线程处理。

本技术的优势在于与简单的哈希策略相比，一致性哈希数据分布策略可 以避免单点失效造成整个系统不可用，同时使得动态调整线程数目成为可 能，一致性哈希也使得数据的分布更加的均匀，即提高了系统的可扩展性、 可用性和负载均衡能力。

(4)每个子哈希表维护一个LRU队列，当内存空间不足时，剔除冷数 据，插入新的元素。

由于内存大小是有限的，当哈希表大小超过内存容量时，需要将一部分 数据替换出去来存放新的数据。替换算法采用LRU(最近最少使用)，如图 3所示用双向链表来实现LRU，双向链表的表尾元素即最近最少使用的元 素，当内存空间不足时即可将其替换出去。

本技术的优势在于当内存空间不足时，LRU策略剔除冷数据，插入新 的元素，提高热点数据的访问效率，热点数据在内存和磁盘之间的交换次 数。

本领域的技术人员容易理解，以上所述仅为本发明的较佳实施例而已， 并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等 同替换和改进等，均应包含在本发明的保护范围之内。