Page 429 - 《软件学报》2025年第7期

3350 软件学报 2025 年第 36 卷第 7 期

阶段查询之间迁移两次哈希桶中某个其他指纹, 将会产生需要重试两阶段查询的误判. 但是, 由于使用迁移计数器
不会将需要重试的场景判断为无需重试. 因此, 当查询操作返回元素不存在时, 说明元素对应的指纹在两阶段查询
流程中并未找到, 并且两阶段查询过程中的计数器变化也不足以引发重试. 在这种情况下, 最后一次读哈希桶的指
令可作为可线性化点.
但是, 在部分特殊情况下, 线性化点会发生变化. 在算法 1 第 10 行的读哈希桶操作完成后指纹被插入到此哈
希桶的情况下, 若将最后一次读哈希桶的操作视为线性化点, 则预期能够查询到元素对应的指纹, 而实际无法查询
到, 因此可线性化点应调整为第 10 行. 同理, 在算法 1 第 11 行的读哈希桶操作完成后指纹被插入到此哈希桶的场
景下, 可线性化点应调整为第 11 行. 在第 10 行和第 11 行的读哈希桶操作之间, 指纹被从第 11 行对应的哈希桶中
移除, 再被插入到第 10 行对应的哈希桶的场景下, 第 10 行和第 11 行都不能作为线性化点, 因为这样预期能够查
询元素对应的指纹, 而实际上无法查询. 但是从指纹删除到指纹再次插入的时间段中, 指纹在过滤器中并不存在,
此时间段在从第 10 行到第 11 行的执行时间范围内, 因此可将此时间段中任一时间点作为可线性化点.
性质 2. 插入操作是可线性化的.
插入时最终将在两个候选哈希桶中找到空槽, 故通过 CAS 操作将指纹写入到过滤器的指令为可线性化点.
性质 3. 删除操作是可线性化的.
如果删除操作找到了待删除的指纹, 则通过 CAS 操作将指纹删除的指令为可线性化点. 若删除操作未找到指
纹, 则线性化点的分析与查询操作返回元素不是集合成员的情况相同, 此处暂不赘述.
性质 4. 无锁并发布谷鸟过滤器是可线性化的.
由于无锁并发布谷鸟过滤器的各项操作均为可线性化的, 所以无锁并发布谷鸟过滤器是可线性化的.

3.5 进展性分析
性质 5. 执行一次指纹原子迁移操作的算法 4 将在有限步骤后完成, 否则其他操作将在有限步骤后完成.
当算法 4 不发生重试时, 算法 4 将在有限步骤后完成. 若算法 4 发生重试, 则说明源哈希桶内的元素发生了变
化, 这说明其他线程执行的指纹插入、迁移或删除操作取得了进展.
性质 6. 若算法 3 执行完毕后没有迁移源哈希桶指纹, 则算法 3 执行的过程中一定有其他线程取得了进展.
若算法 3 因为目标哈希桶中没有空指纹槽而无法完成迁移, 则说明其他线程通过执行插入或迁移操作占用了
目标哈希桶中原有的空指纹槽, 即其他线程取得了进展. 若算法 3 发现目标哈希桶中有空指纹槽, 但是通过 K-CAS
操作原子更新源哈希桶和目标哈希桶时失败, 则说明从读取目标哈希桶到原子更新过滤器期间, 有其他线程通过
执行插入、删除、迁移等操作修改了源哈希桶或目标哈希桶, 即其他线程取得了进展.
性质 7. 查询操作将在有限步骤后完成, 否则其他操作将在有限步骤后完成.
查询操作只有当两个候选哈希桶的迁移计数器满足条件时才会发起重试. 如第 3.1 节所述, 查询操作的重试
说明此时有其他迁移操作正在取得进展.
性质 8. 插入操作将在有限步骤后完成, 否则其他操作将在有限步骤后完成.
插入操作只有在 CAS 操作修改哈希桶失败后 (算法 2 第 9、14 行) 或指纹迁移成功完成后 (算法 2 第 17 行)
发生重试. 对于第 1 种情况, 之所以 CAS 操作修改哈希桶失败, 是因为有其他的插入、删除或迁移操作对哈希桶
进行了修改, 即其他操作取得了进展. 对于第 2 种情况, 指纹迁移成功完成后一定会在一个候选桶中会产生空指纹
槽, 此时插入操作会重试并在此空指纹槽中插入指纹, 即插入操作取得了进展.
性质 9. 删除操作将在有限步骤后完成, 否则其他操作将在有限步骤后完成.
删除操作只有在 CAS 操作修改哈希桶失败后 (算法 5 第 8、12、19 或 23 行) 或迁移计数器满足两阶段查询
重试条件后将发起重试 (算法 5 第 27 行). 对于第 1 种情况, CAS 修改哈希桶失败说明有其他的插入、删除或迁移
操作能够取得进展. 而第 2 种重试情况与查询操作的重试情况相同, 此处暂不赘述.
性质 10. 无锁并发布谷鸟过滤器为无锁过滤器.
本文所提过滤器的各项操作将在有限步骤后完成, 否则其他操作将在有限步骤后完成. 这符合无锁的进展性