技术摘要：
提供了一种操作数据的方法和装置以及管理持久化跳表的方法和装置。操作数据的方法包括：读取具有特定格式的第一指针sp，其中，所述特定格式至少包括地址部分和脏位；根据第一指针sp的脏位确定是否对第一指针sp执行flush操作；以及通过比较并交换CAS操作将第一指针sp修  全部
背景技术：
现有的并发无锁跳表都是基于比较并交换(Compare  and  Swap,CAS)操作实现的， 但是PMEM不同于DRAM的地方在于持久化特性，即在断电时数据不会丢失。在现有计算机软 硬件架构下，程序对内存的读写都会经过C P U中的缓存 (基本单元叫做缓存行 (Cacheline))，所以对于PMEM中的数据的写操作(包括CAS)，并不能保证此被写入的新数据 会被立刻写入PMEM。只有当新数据所在的Cacheline被写回PMEM中(即进行缓存行刷新 (Cacheline  flush)，以下简称FLUSH)时，数据才被真正写入PMEM。FLUSH的顺序与数据被修 改的顺序无关，由CPU自行决定，程序可以通过额外执行一次指令(CLFLUSH/CLWB)达到目 的，但是这些指令无法与传统CAS组合成原子操作。因此在某些情况下，使用传统CAS在断电 恢复后会造成数据不一致的问题。例如，如图1中所示，X由线程1控制，初始值为1，Y需要始 终保持其值等于X 1，由线程2控制。由于CAS FLUSH不是原子操作，因此线程1和2可能会按 照图1的顺序执行，因此，如果在线程1的flush(X)前系统断电，则恢复后由于X的新值未被 真正写入PMEM，因此会导致X的值仍为修改前的1，而Y的新值4已经写入PMEM，导致Y≠X 1， 进而造成数据不一致的问题。所以现有的CAS无法运用到基于PMEM的持久化数据结构中。 虽然，现有技术可利用读前刷新(flush-on-read)机制从正确性上解决以上问题， 即在CAS前对所读数据进行一次FLUSH，但是在现今系统中，缺乏判断所读数据是否需要 FLUSH的方法。此外，在无锁跳表的实现中大量使用了CAS，如果每个CAS前都进行FLUSH，则 会产生大量的不必要的FLUSH，而FLUSH本身是一个非常耗时的操作。此外，现有技术还可利 用Cachelineflush指令(CLFLUSH/CLWB)来解决以上问题，但是这些指令本身只有在flush 的数据量≤64字节(64B)才是原子操作，这意味着如果在对于数据量>64B的数据执行flush 操作的过程中发生断电，则在系统重启恢复后，涉及的数据量>64B的数据可能会出现只有 部分数据被更新而导致的数据不一致的问题。
技术实现要素：
本申请的示例性实施例在于提供一种操作数据的方法和装置以及管理持久化跳 表的方法和装置，以至少解决现有技术存在的上述问题。 根据本申请的示例性实施例，提供一种操作数据的方法，所述方法可包括：读取具 有特定格式的第一指针sp，其中，所述特定格式至少包括地址部分和脏位；根据第一指针sp 的脏位确定是否对第一指针sp执行flush操作；通过比较并交换CAS操作将第一指针sp修改 为指向新地址。 可选地，根据第一指针sp的脏位确定是否对第一指针sp执行flush操作的步骤可 4 CN 111597076 A 说　明　书 2/12 页 包括：确定第一指针sp的脏位是否为第一值；如果第一指针sp的脏位为第一值，则将第一指 针sp的脏位设置为第二值并对第一指针sp执行flush操作，如果第一指针sp的脏位为第二 值，则不对第一指针sp执行flush操作。 可选地，所述特定格式中的脏位可以是指针的最低的3个位中的至少一位。 可选地，通过比较并交换CAS操作将第一指针sp修改为指向所述新地址的步骤可 包括：创建具有所述特定格式的第二指针sp_old和第三指针sp_new；将第二指针sp_old指 向第一指针sp的地址部分，并将第二指针sp_old的脏位设置为第二值；将第三指针sp_new 指向所述新地址，并将第三指针sp_new的脏位设置为第一值；对第一指针sp、第二指针sp_ old和第三指针sp_new执行CAS操作。 根据本申请的示例性实施例，提供一种操作数据的装置，所述装置可包括：读取模 块，被配置为读取具有特定格式的第一指针sp，其中，所述特定格式至少包括地址部分和脏 位；以及处理模块，被配置为：根据第一指针sp的脏位确定是否对第一指针sp执行flush操 作；并且通过比较并交换CAS操作将第一指针sp修改为指向新地址。 可选地，处理器可被配置为通过以下操作来确定是否对第一指针sp执行flush操 作：确定第一指针sp的脏位是否为第一值；如果第一指针sp的脏位为第一值，则将第一指针 sp的脏位设置为第二值并对第一指针sp执行flush操作，如果第一指针sp的脏位为第二值， 则不对第一指针sp执行flush操作。 可选地，所述特定格式中的脏位可以是指针的最低的3个位中的至少一位。 可选地，处理模块可被配置为通过以下操作来将第一指针sp修改为指向所述新地 址：创建具有所述特定格式的第二指针sp_old和第三指针sp_new；将第二指针sp_old指向 第一指针sp的地址部分，并将第二指针sp_old的脏位设置为第二值；将第三指针sp_new指 向所述新地址，并将第三指针sp_new的脏位设置为第一值；对第一指针sp、第二指针sp_old 和第三指针sp_new执行CAS操作。 根据本申请的示例性实施例，提供一种管理持久化跳表的方法，所述方法可包括： 根据具有第一格式的指针和具有第二格式的指针来生成一个持久化跳表；并且将所述持久 化跳表中的所有具有第一格式的指针以及所有节点的键值对和高度存储在持久化存储装 置中，其中，第一格式至少包括地址部分和脏位，第二格式仅包括地址部分，所述脏位用于 确定是否对具有第一格式的指针执行flush操作，其中，所述持久化跳表中的底层链表中的 每个节点的next指针具有第一格式，并且所述持久化跳表中的除了所述底层链表之外的上 层链表中的每个节点的next指针具有第二格式。 可选地，第一格式中的脏位可以是指针的最低的3个位中的至少一位。 可选地，当修改所述底层链表中的任意一个节点时，可进行以下操作：读取所述任 意一个节点的next指针sp；确定所述任意一个节点的next指针sp的脏位是否为第一值；如 果所述任意一个节点的next指针sp的脏位为第一值，则将所述任意一个节点的next指针sp 的脏位设置为第二值并对所述任意一个节点的next指针sp执行flush操作，如果所述任意 一个节点的next指针sp的脏位为第二值，则不对所述任意一个节点的next指针sp执行 flush操作；通过比较并交换CAS操作将所述任意一个节点的next指针sp修改为指向新地 址。 可选地，通过比较并交换CAS操作将第一指针sp修改为指向所述新地址的步骤可 5 CN 111597076 A 说　明　书 3/12 页 包括：创建具有第一格式的指针sp_old和指针sp_new；将指针sp_old指向所述任意一个节 点的next指针sp的地址部分，并将指针sp_old的脏位设置为第二值；将指针sp_new指向所 述新地址，并将指针sp_new的脏位设置为第一值；对所述任意一个节点的next指针sp、指针 sp_old和指针sp_new执行CAS操作。 可选地，当修改所述持久化跳表中的除了所述底层链表之外的上层链表中的任意 一个节点时，可进行以下操作：读取所述任意一个节点的next指针sp；创建具有第二格式的 指针sp_old和指针sp_new；将指针sp_old指向所述任意一个节点的next指针sp；将指针sp_ new指向新地址；对所述任意一个节点的next指针sp、指针sp_old和指针sp_new执行CAS操 作。 可选地，当使用所述方法的装置上电时，可通过在所述持久化存储装置中存储的 所述底层链表的基础上重建所述持久化跳表中的具有第二格式的next指针来恢复所述持 久化跳表。 可选地，恢复所述持久化跳表的步骤可包括：获得所述底层链表的头节点，并将所 述头节点赋值给当前节点；从所述头节点开始进行以下操作：如果所述底层链表中的当前 节点的next指针未指向尾节点，则根据所述底层链表中的当前节点的高度，将每一个上层 链表前一个节点的相应层链表的next指针修改为指向当前节点，如果所述底层链表中的当 前节点的next指针指向所述尾节点，则将每一个上层链表的最后一个节点的next指针修改 为指向所述尾节点。 可选地，根据本申请的示例性实施例，提供一种管理持久化跳表的装置，所述装置 可包括：处理单元，被配置为根据具有第一格式的指针和具有第二格式的指针来生成一个 持久化跳表；并且存储单元，被配置为将所述持久化跳表中的所有具有第一格式的指针以 及所有节点的键值对和高度存储在持久化存储装置中，其中，第一格式至少包括地址部分 和脏位，第二格式仅包括地址部分，所述脏位用于确定是否对具有第一格式的指针执行 flush操作，其中，所述持久化跳表中的底层链表中的每个节点的next指针具有第一格式， 并且所述持久化跳表中的除了所述底层链表之外的上层链表中的每个节点的next指针具 有第二格式。 可选地，第一格式中的脏位可以是指针的最低的3个位中的至少一位。 可选地，当修改所述底层链表中的任意一个节点时，处理单元可被配置为：读取所 述任意一个节点的next指针sp；确定所述任意一个节点的next指针sp的脏位是否为第一 值；如果所述任意一个节点的next指针sp的脏位为第一值，则将所述任意一个节点的next 指针sp的脏位设置为第二值并对所述任意一个节点的next指针sp执行flush操作，如果所 述任意一个节点的next指针sp的脏位为第二值，则不对所述任意一个节点的next指针sp执 行flush操作；通过比较并交换CAS操作将所述任意一个节点的next指针sp修改为指向新地 址。 可选地，处理单元可被配置为通过以下操作将第一指针sp修改为指向所述新地 址：创建具有第一格式的指针sp_old和指针sp_new；将指针sp_old指向所述任意一个节点 的next指针sp的地址部分，并将指针sp_old的脏位设置为第二值；将指针sp_new指向所述 新地址，并将指针sp_new的脏位设置为第一值；对所述任意一个节点的next指针sp、指针 sp_old和指针sp_new执行CAS操作。 6 CN 111597076 A 说　明　书 4/12 页 可选地，当修改所述持久化跳表中的除了所述底层链表之外的上层链表中的任意 一个节点时，处理单元可被配置为进行以下操作：读取所述任意一个节点的next指针sp；创 建具有第二格式的指针sp_old和指针sp_new；将指针sp_old指向所述任意一个节点的next 指针sp；将指针sp_new指向新地址；对所述任意一个节点的next指针sp、指针sp_old和指针 sp_new执行CAS操作。 可选地，当所述装置上电时，处理器可被配置为通过由存储单元在所述持久化存 储装置中存储的所述底层链表的基础上重建所述持久化跳表中的具有第二格式的next指 针来恢复所述持久化跳表。 可选地，处理单元可被配置为通过以下操作恢复所述持久化跳表的步骤包括：获 得所述底层链表的头节点，并将所述头节点赋值给当前节点；从所述头节点开始进行以下 操作：如果所述底层链表中的当前节点的next指针未指向尾节点，则根据所述底层链表中 的当前节点的高度，将每一个上层链表前一个节点的相应层链表的next指针修改为指向当 前节点，如果所述底层链表中的当前节点的next指针指向所述尾节点，则将每一个上层链 表的最后一个节点的next指针修改为指向所述尾节点。 根据本申请的另一示例性实施例，提供了一种存储指令的计算机可读存储介质， 其中，当所述指令被至少一个计算装置运行时，促使所述至少一个计算装置执行如上所述 的操作数据的方法或如上所述的管理持久化跳表的方法。 根据本申请的另一示例性实施，提供了一种包括至少一个计算装置和存储指令的 至少一个存储装置的系统，其中，所述指令在被所述至少一个计算装置运行时，促使所述至 少一个计算装置执行如上所述的操作数据的方法或如上所述的管理持久化跳表的方法。 根据本申请的示例性实施例的操作数据的方法和装置利用新的智能指针避免了 不必要的flush，实现了高效的基于PMEM的CAS，同时能够解决CAS在PMEM中导致的数据不一 致的问题。此外，根据本申请的示例性实施例的管理持久化跳表的方法和装置利用上述智 能指针取代传统内存地址指针，实现了持久化并发无锁跳表。 将在接下来的描述中部分阐述本发明总体构思另外的方面和/或优点，还有一部 分通过描述将是清楚的，或者可以经过本发明总体构思的实施而得知。 附图说明 从下面结合附图对本申请实施例的详细描述中，本申请的这些和/或其他方面和 优点将变得更加清楚并更容易理解，其中： 图1是示出现有技术中的基于DRAM的CAS操作的示例的示图； 图2是示出现有技术中的普通指针和根据本申请示例性实施例的智能指针的示 图； 图3是示出根据本申请示例性实施例的操作数据的方法的总流程图； 图4是示出根据本申请示例性实施例的操作数据的方法的详细流程图； 图5是示出根据本申请示例性实施例的操作数据的装置的框图； 图6是示出根据本申请示例性实施例的管理持久化跳表的方法的流程图； 图7是示出基于DRAM的传统跳表和根据本申请示例性实施例的基于PEME的持久化 跳表的示例的示图； 7 CN 111597076 A 说　明　书 5/12 页 图8是示出根据本申请示例性实施例的修改基于PMEM的持久化跳表的底层链表的 过程的流程图； 图9是示出根据本申请示例性实施例的恢复基于PMEM的持久化跳表的过程的流程 图； 图10是示出根据本申请示例性实施例的恢复基于PMEM的持久化跳表的过程的伪 代码的示图； 图11是示出根据本申请示例性实施例的管理持久化跳表的装置的框图。