一种散列表的操作管理方法、系统及电子设备

1.本发明属于计算机存储领域，更具体地，涉及一种散列表的操作管理方法、系统及电子设备。
背景技术：
：：2.动态随机访问内存(dynamicrandomaccessmemory，dram)在过去几十年里作为内存被广泛使用于计算机存储体系架构中。但是，dram面临高的动态刷新功耗问题以及密度扩展瓶颈，渐渐使得dram无法满足计算机系统对内存的需求。近年来，随着新型非易失内存(non-volatilememory，nvm)或持久性内存(persistentmemory，pm)技术的出现，如3dxpoint、相变内存(phasechangememory，pcm)、阻变式随机访问内存(resistiverandomaccessmemory，rram)、因特尔傲腾数据中心持久内存模块(inteloptanedcpersistentmemorymodule，dcpmm)等具有dram的访问性能又有磁盘的非易失性，使得pm为新的内存架构提供了更多的可能性。相比dram而言，pm具有更低的静态功耗、更大的容量以及非易失特性，使得pm受到学术界和工业界广泛关注。然而，pm具有有限的耐久性，需要保障其寿命以便防止快速磨损。此外，pm的非易失特性，即掉电数据不丢失，需要保障系统故障时的数据一致性。直接加载在内存总线上的pm使得应用程序能够直接通过高速的内存指令如load和store访问数据，避免了传统的且低效的io操作从辅存磁盘中读取数据。当前以应用直连方式(applicationdirectmode)将dcpmm挂载到内存总线上，最大化利用dcpmm来提升应用读写访问性能。3.近年来，基于pm的散列表得到了广泛的研究，如p-clht，level_hashing，cceh以及clevel。缓存行友好的散列表能够大大提高缓存命中率，能最大化散列表的读性能。然而散列表在基于锁的单线程扩容的情况下，引发了诸多问题，如消耗大量的计算开销、耗时长并且不能够有效的利用多核资源。由于加解锁开销以及单线程扩容的方式大大降低了扩容并行性并且同时阻塞了其他读写线程的并发，使得散列表整体性能大大降低。针对插入删除操作而言，基于桶锁粒度的机制虽然比基于全表锁粒度而言并行性得到了较大的提升，但是依然还有进一步提升的空间。而且由于真实的器件dcpmm读延迟是dram的2到3倍，写延迟和dram相当，这需要研究人员考虑如何降低dcpmm读延迟高带来的整体性能下降的影响。技术实现要素：4.针对现有技术的缺陷，本发明的目的在于提供一种散列表的操作管理方法、系统及电子设备，旨在解决现有散列表整体性能低的问题。5.为实现上述目的，第一方面，本发明提供了一种散列表的操作管理方法，包括以下步骤：6.确定非易失内存的散列表；7.判断散列表容量是否达到预设阈值，若达到预设阈值，则采用基于上下文感知的多线程协同扩容方式对散列表进行扩容，得到新的散列表，并释放原始散列表的空间；所述多线程协同扩容为多个线程协同迁移原散列表中的主桶链，将其迁移到分配的新散列表空间内；其中，所述新散列表的容量大于原散列表的容量，在扩容过程中阻塞扩容所需线程之外的插入线程和删除线程，并在扩容过程中允许读线程并发执行；在所述多个线程协同扩容过程中，若某个线程完成迁移，则将其迁移的所有主桶链对应的数据持久化到非易失内存中。8.在一个可选的示例中，所述采用基于上下文感知的多线程协同扩容方式对散列表进行扩容，得到新的散列表，具体为：9.确定待迁移散列表的主桶数和协同扩容的线程数；10.将所述主桶数除以线程数，并对相除之后的结果向上取整得到每个线程需要迁移的主桶数；11.按照待迁移散列表内主桶的排列顺序和每个线程需要迁移的主桶数为每个线程分配对应的主桶，使其进行迁移；其中，一个主桶只能被一个线程迁移；12.为每个线程设置标志位数组，以指示该线程下各个主桶是否完成迁移；13.当某个线程的标志位数组指示该线程下的所有主桶均完成迁移时，则将对应主桶的数据持久化到非易失内存中。14.在一个可选的示例中，该方法还包括如下步骤：将新数据无锁插入到散列表中。15.在一个可选的示例中，该方法还包括如下步骤：在散列表中进行查找时，采用无锁方式查找。16.在一个可选的示例中，该方法还包括如下步骤：若需要对某个主桶链内的数据进行删除，判断主桶链所在的散列表是否在进行扩容，若在进行扩容，则阻塞等待直到扩容完成，之后对所述主桶链内的数据进行无锁删除，若散列表未进行扩容，则直接对所述主桶链内的数据进行无锁删除。17.在一个可选的示例中，所述无锁插入、无锁方式查找及无锁删除指的是采用原子指令的方式进行插入、查找或者删除。18.在一个可选的示例中，该方法还包括如下步骤：19.对散列表扩容的过程中，当有主桶链未成功迁移时，阻塞所述多个线程中未成功迁移主桶链对应线程之外的线程，基于上下文感知对未迁移成功的主桶链进行恢复。20.第二方面，本发明提供一种电子设备，包括：至少一个存储器，用于存储程序；至少一个处理器，用于执行存储器存储的程序，当存储器存储的程序被执行时，处理器用于执行第一方面或第一方面的任一种可选示例所描述的方法。21.第三方面，本发明提供一种计算机可读存储介质，计算机可读存储介质存储有计算机程序，当计算机程序在处理器上运行时，使得处理器执行第一方面或第一方面的任一种可选示例所描述的方法。22.第四方面，本发明提供一种计算机程序产品，当计算机程序产品在处理器上运行时，使得处理器执行第一方面或第一方面的任一种可选示例所描述的方法。23.总体而言，通过本发明所构思的以上技术方案与现有技术相比，具有以下有益效果：24.本发明提供了一种散列表的操作管理方法、系统及电子设备，当哈希表达到容量阈值需要扩容时，先生成大于原哈希表容量n倍的新哈希表，期间通过多线程协同重散列来并行迁移原哈希表键值条目到新哈希表中，这样可以大大缩减迁移完成时间。通过原子指令等无锁方式可以避免高额的锁开销，这在多读少写场景可以有很好的多线程可扩展性提升。相对高昂的dcpmm读延迟，可以通过指纹方式而非扫描全键来加快键值条目匹配，可以较好缓解pm较高读延迟的影响，提升读性能。附图说明25.图1是本发明实施例提供的散列表操作管理方法流程图；26.图2是本发明实施例提供的散列表无锁插入和多线程扩容流程图；27.图3是本发明实施例提供的基于上下文感知的多线程协同重散列流程图；28.图4是本发明实施例提供的散列表无锁查找流程图；29.图5是本发明实施例提供的散列表无锁删除流程图。具体实施方式30.为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅用以解释本发明，并不用于限定本发明。31.在本发明实施例中，“示例性的”或者“例如”等词用于表示作例子、例证或说明。本发明实施例中被描述为“示例性的”或者“例如”的任何实施例或设计方案不应被解释为比其它实施例或设计方案更优选或更具优势。确切而言，使用“示例性的”或者“例如”等词旨在以具体方式呈现相关概念。32.在本发明实施例的描述中，除非另有说明，“多个”的含义是指两个或者两个以上。33.首先，对本发明实施例中涉及的技术术语进行介绍。34.散列表，又叫哈希表(hashtable)，是能够通过给定的关键字的值直接访问到具体对应的值的一个数据结构。也就是说，把关键字映射到一个表中的位置来直接访问记录，以加快访问速度。通常，我们把这个关键字称为key，把对应的记录称为value，所以也可以说是通过key访问一个映射表来得到value的地址。而这个映射表，通过散列函数或者哈希函数来快速定位记录，存放记录的数组叫作散列表。35.接下来，对本发明实施例中提供的技术方案进行介绍。36.针对现有技术的缺陷和改进需求，本发明提的目的在于提升持久缓存行散列的并行扩容效率，加快插入和删除的并行性能同时减少dcpmm高的读延迟影响。37.图1是本发明实施例提供的散列表操作管理方法流程图；如图1所示，包括以下步骤：38.s101，确定非易失内存的散列表；39.s102，判断散列表容量是否达到预设阈值，若达到预设阈值，则采用基于上下文感知的多线程协同扩容方式对散列表进行扩容，得到新的散列表，并释放原始散列表的空间；所述多线程协同扩容为多个线程协同迁移原散列表中的主桶链，将其迁移到分配的新散列表空间内；其中，所述新散列表的容量大于原散列表的容量，在扩容过程中阻塞扩容所需线程之外的插入线程和删除线程，并在扩容过程中允许读线程并发执行；在所述多个线程协同扩容过程中，若某个线程完成迁移，则将其迁移的所有主桶链对应的数据持久化到非易失内存中。40.如图2所示，本发明实施例提供散列表无锁插入和多线程扩容流程包括以下步骤：41.(i1)采用比较和交换(compare-and-swap，cas)等原子指令无锁插入新数据到基于dcpmm的持久缓存行友好散列表，判断散列表是否达到缓存行扩容阈值；如果是，进行并发扩容操作(i2)步骤；否则进行(i3)。42.(i2)散列表成倍扩容，采用基于锁的多线程协同扩容生成新的散列表ht，同时保留用于扩容的散列表ht-multiply，设置扩容标志is_resizing为真。阻塞其他插入和删除操作的线程并允许读线程的并发执行操作，直至扩容完成。转到(i4)。43.(i3)采用通过pmdk提供的有序持久化函数persist将数据持久化到dcpmm中，保证了数据一致性。转入(i5)。44.(i4)无锁插入新数据到散列表ht。45.(i5)完成插入操作。46.其中散列表ht指的是当前最新有效的表；多倍散列表ht_multiply指的是用于执行扩容操作的散列表。pmdk提供的persist函数封装了缓存行刷新指令(cachelineflush，clflush)和内存栅栏指令(memoryfence，mfence)，能够有效地确保持久到dcpmm中的数据一致性。标志is_resizing表示当前散列表是否正在扩容，值为true表示正在扩容，值为false则表示未扩容。47.在一个示例中，参见图3，基于上下文感知的多线程协同重散列过程如下所示：48.(1)假设用于协同重散列的线程数为nr(编号从0到nr-1)，当前需要迁移的散列表ht的主桶数为nb，其编号由0到nb-1，那么每个协同重散列线程需要迁移s个主桶链，即s＝(nb％nr＝＝0)，(nb/nr)：(nb/nr+1)，即向上取整。49.(2)设置一个nr个标志位数组bitmap[nr]，初始均为0；bitmap[i]＝0表示对应线程编号为i的重散列线程未完成对应主桶号范围的迁移工作；bitmap[i]＝1表示对应线程编号为i的重散列线程已经完成对应主桶号范围的迁移工作。[0050](3)查看bitmap数组所有成员是否全部为1，如果是，表示需要迁移的主桶链全部迁移完成，转入(6)；如果没有，继续迁移，直到完成。[0051](4)nr个重散列线程并行进行重散列，假如线程编号为整数i(i为0到nr-2的整数)，那么每个重散列线程负责重散列的主桶号范围为[i*s,(i+1)*s-1]，编号为nr-1的重散列线程，负责的主桶号范围为[(nr-1)*s,nb-1]。[0052](5)nr个重散列线程并行迁移对应的没有交叉的主桶号范围，将对应桶号的键值对重新散列到原散列表ht的两倍大小的新散列表ht_multiply中，迁移完成的编号为i的重散列线程，将bitmap[i]设置为1，并持久化到非易失内存中。[0053](6)采用原子事务的方式生成两倍大小于ht_multiply的新的且空的临时表table_tmp，并且释放回收ht的空间，然后原子地修改元数据ht＝ht_multiply，ht_multiply＝&table_tmp，并将ht，ht_multiply持久化到非易失内存中。[0054](7)多线程协同重散列完成。[0055]在一个示例中，参见图4，无锁查找search采用指纹方式降低dcpmm高读延迟影响，其步骤具体如下：[0056](s1)从当前有效ht中查找特定的键值对(key-value，kv)项，根据key计算出2字节指纹fingerprint，以及对应的桶号bucket_number；[0057](s2)从相应的桶中查找对应的kv项，首先比较两个key的fingerprint，如果相等，进行(s3)，否则进行(s4)；[0058](s3)比较全key，判断是否相等，如果相等，进入(s5)，否则继续执行(s4)步；[0059](s4)判断是否搜索完毕，如果是，进入(s6)，否则继续执行(s2)；[0060](s5)查找成功，返回查找到的值；[0061](s6)查找失败，返回空值。[0062]在一个具体的示例中，参见图5，无锁删除delete的步骤具体如下：[0063](d1)判断当前散列表是否在扩容，即is_resizing＝＝true，如果相等就阻塞等待直到扩容完成，否则进入(d2)；[0064](d2)从当前有效ht中查找特定的kv项，根据key计算出2字节指纹fingerprint，以及对应的桶号bucket_number；[0065](d3)从相应的桶中查找对应的kv项，首先比较两个key的fingerprint，如果相等，进行(d4)，否则进行(d5)；[0066](d4)比较全key，判断是否相等，如果相等，进入(d6)，否则进入(d3)；[0067](d5)取下一个kv项进行比较；[0068](d6)采用原子交换指令cas设置该条目为空；[0069](d7)需要再次判断散列表是否在扩容is_resizing＝＝true，如果是，从头开始执行(d1)，否则，执行(d8)；[0070](d8)删除操作成功，返回删除成功的结果。[0071]在一个示例中，数据恢复recovery的步骤具体如下：[0072](1)恢复时如果is_resizing为真，扫描ht，将所有未成功迁移的有效条目迁移到ht_multiply；[0073](2)阻塞其他所有的多线程操作，采用基于上下文感知的多线程协同重散列模块进行恢复，直到恢复成功。[0074]基于上述实施例中的方法，本发明实施例提供了一种电子设备。该设备可以包括：至少一个用于存储程序的存储器和至少一个用于执行存储器存储的程序的处理器。其中，当存储器存储的程序被执行时，处理器用于执行上述实施例中所描述的方法。[0075]基于上述实施例中的方法，本发明实施例提供了一种计算机可读存储介质，计算机可读存储介质存储有计算机程序，当计算机程序在处理器上运行时，使得处理器执行上述实施例中的方法。[0076]基于上述实施例中的方法，本发明实施例提供了一种计算机程序产品，当计算机程序产品在处理器上运行时，使得处理器执行上述实施例中的方法。[0077]可以理解的是，本发明的实施例中的处理器可以是中央处理单元(centralprocessingunit，cpu)，还可以是其他通用处理器、数字信号处理器(digitalsignalprocessor，dsp)、专用集成电路(applicationspecificintegratedcircuit，asic)、现场可编程门阵列(fieldprogrammablegatearray，fpga)或者其他可编程逻辑器件、晶体管逻辑器件，硬件部件或者其任意组合。通用处理器可以是微处理器，也可以是任何常规的处理器。[0078]本发明的实施例中的方法步骤可以通过硬件的方式来实现，也可以由处理器执行软件指令的方式来实现。软件指令可以由相应的软件模块组成，软件模块可以被存放于随机存取存储器(randomaccessmemory，ram)、闪存、只读存储器(read-onlymemory，rom)、可编程只读存储器(programmablerom，prom)、可擦除可编程只读存储器(erasableprom，eprom)、电可擦除可编程只读存储器(electricallyeprom，eeprom)、寄存器、硬盘、移动硬盘、cd-rom或者本领域熟知的任何其它形式的存储介质中。一种示例性的存储介质耦合至处理器，从而使处理器能够从该存储介质读取信息，且可向该存储介质写入信息。当然，存储介质也可以是处理器的组成部分。处理器和存储介质可以位于asic中。[0079]在上述实施例中，可以全部或部分地通过软件、硬件、固件或者其任意组合来实现。当使用软件实现时，可以全部或部分地以计算机程序产品的形式实现。所述计算机程序产品包括一个或多个计算机指令。在计算机上加载和执行所述计算机程序指令时，全部或部分地产生按照本发明实施例所述的流程或功能。所述计算机可以是通用计算机、专用计算机、计算机网络、或者其他可编程装置。所述计算机指令可以存储在计算机可读存储介质中，或者通过所述计算机可读存储介质进行传输。所述计算机指令可以从一个网站站点、计算机、服务器或数据中心通过有线(例如同轴电缆、光纤、数字用户线(dsl))或无线(例如红外、无线、微波等)方式向另一个网站站点、计算机、服务器或数据中心进行传输。所述计算机可读存储介质可以是计算机能够存取的任何可用介质或者是包含一个或多个可用介质集成的服务器、数据中心等数据存储设备。所述可用介质可以是磁性介质，(例如，软盘、硬盘、磁带)、光介质(例如，dvd)、或者半导体介质(例如固态硬盘(solidstatedisk，ssd))等。[0080]可以理解的是，在本发明的实施例中涉及的各种数字编号仅为描述方便进行的区分，并不用来限制本发明的实施例的范围。[0081]本领域的技术人员容易理解，以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。当前第1页12当前第1页12
技术特征：
1.一种散列表的操作管理方法，其特征在于，包括以下步骤：确定非易失内存的散列表；判断散列表容量是否达到预设阈值，若达到预设阈值，则采用基于上下文感知的多线程协同扩容方式对散列表进行扩容，得到新的散列表，并释放原始散列表的空间；所述多线程协同扩容为多个线程协同迁移原散列表中的主桶链，将其迁移到分配的新散列表空间内；其中，所述新散列表的容量大于原散列表的容量，在扩容过程中阻塞扩容所需线程之外的插入线程和删除线程，并在扩容过程中允许读线程并发执行；在所述多个线程协同扩容过程中，若某个线程完成迁移，则将其迁移的所有主桶链对应的数据持久化到非易失内存中。2.根据权利要求1所述的方法，其特征在于，所述采用基于上下文感知的多线程协同扩容方式对散列表进行扩容，得到新的散列表，具体为：确定待迁移散列表的主桶数和协同扩容的线程数；将所述主桶数除以线程数，并对相除之后的结果向上取整得到每个线程需要迁移的主桶数；按照待迁移散列表内主桶的排列顺序和每个线程需要迁移的主桶数为每个线程分配对应的主桶，使其进行迁移；其中，一个主桶只能被一个线程迁移；为每个线程设置标志位数组，以指示该线程下各个主桶是否完成迁移；当某个线程的标志位数组指示该线程下的所有主桶均完成迁移时，则将对应主桶的数据持久化到非易失内存中。3.根据权利要求1所述的方法，其特征在于，还包括如下步骤：将新数据无锁插入到散列表中。4.根据权利要求1所述的方法，其特征在于，还包括如下步骤：在散列表中进行查找时，采用无锁方式查找。5.根据权利要求1所述的方法，其特征在于，还包括如下步骤：若需要对某个主桶链内的数据进行删除，判断主桶链所在的散列表是否在进行扩容，若在进行扩容，则阻塞等待直到扩容完成，之后对所述主桶链内的数据进行无锁删除，若散列表未进行扩容，则直接对所述主桶链内的数据进行无锁删除。6.根据权利要求3至5任一项所述的方法，其特征在于，所述无锁插入、无锁方式查找及无锁删除指的是采用原子指令的方式进行插入、查找或者删除。7.根据权利要求1所述的方法，其特征在于，还包括如下步骤：对散列表扩容的过程中，当有主桶链未成功迁移时，阻塞所述多个线程中未成功迁移主桶链对应线程之外的线程，基于上下文感知对未迁移成功的主桶链进行恢复。8.一种电子设备，其特征在于，包括：至少一个存储器，用于存储程序；至少一个处理器，用于执行所述存储器存储的程序，当所述存储器存储的程序被执行时，所述处理器用于执行如权利要求1-7任一所述的方法。9.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质存储有计算机程序，当所述计算机程序在处理器上运行时，使得所述处理器执行如权利要求1-7任一所述的方法。
10.一种计算机程序产品，其特征在于，当所述计算机程序产品在处理器上运行时，使得所述处理器执行如权利要求1-7任一所述的方法。

技术总结
本发明提供一种散列表的操作管理方法、系统及电子设备，包括：确定非易失内存的散列表；判断散列表容量是否达到预设阈值，若达到预设阈值，则采用基于上下文感知的多线程协同扩容方式对散列表进行扩容，得到新的散列表，并释放原始散列表的空间；多线程为多个线程协同迁移原散列表中的主桶链，将其迁移到分配的新散列表空间内；新散列表的容量大于原散列表的容量，在扩容过程中阻塞扩容所需线程之外的插入线程和删除线程，并在扩容过程中允许读线程并发执行；在多个线程协同扩容过程中，若某个线程完成迁移，则将其迁移的所有主桶链数据持久化到非易失内存中。本发明降低了散列表的读延迟，且提高了散列表的并行性能，提升了散列表的整体性能。的整体性能。的整体性能。


技术研发人员：冯丹 肖仁智 胡燏翀
受保护的技术使用者：华中科技大学
技术研发日：2023.05.26
技术公布日：2023/9/14