哈希

哈希是一种key value的存储结构

当哈希表的key越来越多的时候,则避免不了要rehashing来保证新的key能插进来或者来达到更高的性能

然后rehash会导致让当前哈希表的操作停顿,知道rehashing完成为止

借鉴redis分布式的架构,可以使用二级哈希来维护一个hash结构

二级hash高效数据结构

第一级hash

使用一个动态的一致性hash表来维护,他有若干个slot,每个slot是一个hash node

第二级hash

使用unordered_map

分裂

当二级map的key达到一定阈值,则分裂次map,在一致性hash表中,分裂出下一个node,来分担此node的数据

预期效果

性能:

  • 在每次获取key时,需要进行二次hash。这可以通过位运算来解决hash带来的性能问题
  • 使用分裂来代替整体的rehash,可以大大减少停顿时间,使系统的更加稳定
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。
禁止转载,如需转载请通过简信或评论联系作者。

推荐阅读更多精彩内容