🎗️Golang map

type
status
date
slug
summary
tags
category
icon
password
Blocked by
Blocking
AI summary

go的map

底层数据结构

  • go使用拉链法实现了hashMap
  • slot中有多个bucket
  • 每个bucket中存放，hash后 得mod相同的k&v
  • 每一个bucket中存放hash key的高8bit
  • 桶超出8个数据后，机会将数据存储在溢出桶中
 
notion image
 

扩容过程

为什么需要扩容
  • map的溢出桶太多会严重影响查询和插入的性能
什么时候需要扩容
  • 装载系数超过6.5（平均每个槽6.5个key）
  • 使用太多的 溢出桶（溢出桶数量大于普通桶）
 
扩容策略
  • 等量扩容：数据不多，但溢出桶中数据过多（整理）
  • 翻倍扩容：数据太多，装载系数大，进行容量翻倍
 
渐进式驱逐
  • 创建新的newBuckets
  • oldBuckets指向之前的buckets
  • 采用渐进式驱逐，每次操作一个旧桶时，将旧桶驱逐到新桶
  • 读取时不进行驱逐，只判断读取新桶还是旧桶
  • 旧桶数据驱逐完成后，回收oldBuckets
 

为什么map不支持并发读写

Go 中 map 的扩容是一个渐进的过程，在我们访问 map 的时候，会对 map 底层实际存储数据的桶进行迁移。
如果支持并发读写，就有可能会导致底层定位到的桶是扩容前的，但是实际上数据已经迁移到了新的桶中，这样就会导致访问到的并不是我们想要的数据

sync.Map

  • 读多写少的场景
 

分片锁

  • 适合写多读少读场景
如果我们有了解过 MongoDB，就会知道，MongoDB 中也有分片的概念，当数据量过大时， 单个 MongoDB 实例可能无法存储所有的数据，或者单个实例无法处理过多的读写请求， 这时候就需要将数据分片存储到多个 MongoDB 实例中，也就是按照一定的规则将数据存储到不同的机器上， 然后读写数据的请求也会依据一定规则被路由到对应的机器上。
 
我们需要做的是：通过 key 来计算其 hash 值，然后根据 hash 值来决定将 key 存储到哪个 map 中， 同时，我们每一个 map 都需要加上互斥锁，这样就可以保证每一个 map 的并发安全了。
将并发压力分散到多个子map中，将少锁在单个map上的竞争
 
 
Prev
MongoDB 总结
Next
epoll
Loading...
Article List