BucketMap:golang快速并发 HashMap 开源实现

23-01-09 banq

一个非常快速、线程安全、简单的 hashmap 实现。

在高度竞争的情况下,它比sync.Map和带mutexes的map快4-10倍以上;所需的堆空间是sync.Map的25%-50%,如果在堆中分配,所需的堆空间是默认map的66%-90%(默认map可以是堆分配);使sync.Map的堆分配量减少33%-50%。

它被设计成一个通用的并发映射,没有明显的缺点,针对高度竞争的用例进行了优化,其中大量读取/插入/删除是并行发生的。
特征:
  1. 正确的。
  2. 良好的兼容性:使用 uint 代替 uint32/uint64 更好地支持 32 位系统。
  3. 完全非阻塞,没有忙等待读取。
  4. 使用原子和锁的组合进行快速插入/删除操作。当失败的原子操作导致过多的额外工作时,使用锁来简化事情。
  5. 便宜的(速度和内存)扩展/收缩操作。
  6. 内存高效且快速。
  7. 简单,易于理解(imo),并且易于根据您自己的需要进行更改。
  8. 高度可定制。您可以指定哈希值的范围,如果它们自己分布良好以实现最佳性能。内存/速度权衡非常明显。
  9. 保证顺序可见性。如果操作 A 在 B 完成后的任何时间开始,则 B 对 A 可见。如果 A 在 B 完成之前开始,则 B 对 A 不可见。没有中间状态。
  10. 易于使用:使用与 sync.Map 相同的接收者签名和行为。
  11. 支持原始键类型以及任意结构作为键类型。允许键和值的零值。

缺点:
  1. 使用链表,因此可能未针对缓存进行优化。
  2. 对错误的散列值没有弹性(因为没有内部散列函数)。为了解决这个问题,我提供了一个使用 stl 中的 hash/maphash 的通用内存哈希器。我听说 xxHash 是一个不错的选择。
  3. 由于过于可定制,无法适应不良参数。
  4. 由于链表导致的频繁分配/释放内存,可能会给 GC 带来一些压力。

有关详细信息和基准,请参阅https://github.com/GM-twostay/Go-Utils/blob/master/Maps/ChainMap/README.md