大家好，我是三斤_5233
都说“面试造火箭，工作拧螺丝”，今日咱们就来看一下为啥要理解底层原理。
工作原因
今日遇到一个需求，需求完结机器的负载均衡。机器地址和客户端的对应保存在map中。大致如下
map[IP1:client1 IP2:client2 IP3:client3]
在完结负载均衡的随机战略时，开端时依照如下思路完结的：由于map的遍历次序是随机的，从哪个kv对开端遍历也便是随机的喽。所以，对map进行遍历，只取第一个作为要使用的机器。模拟代码如下：
func testMapRand() {
services := map[string]string{}
services["IP1"] = "client1"
services["IP2"] = "client2"
services["IP3"] = "client3"
// 计数用的
count := map[string]int{}
for i := 0; i < 2000; i++ {
for k, _ := range services {
count[k]++
break
}
}
fmt.Println(count)
}
一共进行了2000次机器挑选，按理说，三台机器被挑选的次数应该是均衡的。成果如下，这个成果不是偶尔，我尝试了屡次。排在第一位的更简单被挑选出来。即，map的遍历随机并非在已有的key中完全随机。
map[IP1:1490 IP2:255 IP3:255]
追因溯源
map的结构
为了弄清这是怎样回事，首要咱们得弄懂goalng的map结构。要点看蓝色的代码。B是用来符号槽位数量的，假如B为5，那么槽位的数量为2^5，可以装下的元素便是loadFactor2^B。其间loadFactor是装载因子，值为6.5。当超过loadFactor2^B时槽位会扩容。
// A header for a Go map.
type hmap struct {
count int // key的数量
flags uint8 // 标志当时map的状况，如：正在扩容，等量扩容，完结扩容...
B uint8 // 假如B为5，那么槽位的数量为2^5，可以装下的元素便是loadFactor*2^B
noverflow uint16 // 溢出桶，的数量，估计数，大致罢了
hash0 uint32 // hash seed
buckets unsafe.Pointer // 指向桶数组的指针，正在使用的。桶数组便是bmap，看下边
oldbuckets unsafe.Pointer // 扩容时，指向本来的桶数组
nevacuate uintptr
extra *mapextra
}
buckets指向的bmap，下边这个是源码中的bmap结构
type bmap struct {
tophash [bucketCnt]uint8
}
但这只是表面(src/runtime/hashmap.go)的结构，编译期间会给它加料，动态地创立一个新的结构
type bmap struct {
topbits [8]uint8
keys [8]keytype
values [8]valuetype
pad uintptr
overflow uintptr
}
bmap便是真实用来装kv对的结构，也便是咱们说的槽位，每个槽位对应一个桶。每个桶中最多装8个kv对，这些元素之所以会落入到同一个桶中是由于key经过hash取模后落入到了相同的哈希槽中。取模的值便是[]bmap槽的容量。当一个桶装不下后，会在该桶后链接出一个溢出桶，溢出桶可形成一个链表。
接下来咱们拉近视点，看一下bmap是怎样存这8个kv对的。
前8位(非二进制的位，这里指方位)，也便是TOP Hash实际上是状况位，别离符号其对应的kv对状况，共有六种
emptyRest = 0 // 当时cell是空的，它下边也都是空的cell了，而且没有溢出桶
emptyOne = 1 // 当时cell是空的
evacuatedX = 2 // 当时cell的内容现已搬迁到了X区域
evacuatedY = 3 // 当时cell的内容现已搬迁到了Y区域
evacuatedEmpty = 4 // 当时cell是空的，而且当时桶现已搬迁完毕了
minTopHash = 5 // 正常填充当时cell的最小值
然后接下来的两个8位别离存key和val。至于为什么不选用k-v、k-v….、k-v的存储方式，官方给出的解释是方便内存对齐，不必每一个k-v后都进行内存对齐。
padding是用来最后进行内存对齐的。overflow是溢出桶的指针。
元素存入bmap时，会对key进行hash，然后低B位决议对应到哪个槽位。然后遍历决议将元素放入桶的哪个cell。
当装入了三个元素时，map的结构是怎样的？B的值会是多少？会有多少个槽位？搞一下
func main() {
m := map[string]string{}
m["IP1"] = "client1"
m["IP2"] = "client2"
m["IP3"] = "client3"
B := *(*uint8)(unsafe.Pointer(uintptr(unsafe.Pointer(*(**int)(unsafe.Pointer(&m)))) + 9))
fmt.Println(B)
}
// 输出
B: 0
也便是说，map装三个元素时他的结构是下边这个姿态滴
map存储元素进程
履行汇编指令，经过其输出可以看到，在存储”IP1″这对键值时，调用了runtime.mapassign_faststr()函数
go build -gcflags=-S main.go
...
0x0076 00118 (.\main.go:25) LEAQ go:string."IP1"(SB), CX
0x007d 00125 (.\main.go:25) MOVL $3, DI
0x0082 00130 (.\main.go:25) CALL runtime.mapassign_faststr(SB)
...
事实上，mapassign 有一个系列的函数，根据 key 类型的不同，编译器会将其优化为相应的“快速函数”。
而咱们只需求了解mapassign这一个函数即可。咱们挑要点的说
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
// ...
// 对key取hash
hash := t.Hasher(key, uintptr(h.hash0))
// ...
again:
// 取低B位，决议落入哪个槽位
bucket := hash & bucketMask(h.B)
// ...
top := tophash(hash)
// ...
bucketloop:
for {
// 对一个桶的八个方位进行遍历，有空位就放
for i := uintptr(0); i < bucketCnt; i++ {
if b.tophash[i] != top {
if isEmpty(b.tophash[i]) && inserti == nil {
inserti = &b.tophash[i]
insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))
elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
}
// ...
}
// ...
}
// ...
}
// ...
return elem
}
除去一些逻辑断定，主体的存储进程便是向上边代码保存的那样。首要会对key进行hash，然后取低B位决议落入哪个槽位。咱们的例子是B等于0，只有一个槽位，因而会落入到第0个槽位中。接下来便是对每个桶的八个方位进行遍历，有空方位就会放入元素。
为什么说一个桶有八个方位？
对于这个问题，简单贴个源码
// Maximum number of key/elem pairs a bucket can hold.
// 每个桶能装键值对的最大数量
bucketCntBits = 3
bucketCnt = 1 << bucketCntBits
由于，咱们的map没有经过复杂的操作，其每个cell的状况都是*emptyRest* 。 因而三个kv对会依次放入前三个cell。验证一下(验证的办法本文就不讲了，今后可能会弥补回来)
func main() {
services := make(map[string]string, 0)
services["IP1"] = "client1"
showKeysAndValues(services)
services["IP2"] = "client2"
showKeysAndValues(services)
services["IP3"] = "client3"
showKeysAndValues(services)
}
func showKeysAndValues(m map[string]string) {
topHash := *(**[8]uint8)(unsafe.Pointer(uintptr(unsafe.Pointer(*(**int)(unsafe.Pointer(&m)))) + 16))
keys := (*[8]string)(unsafe.Pointer(uintptr(unsafe.Pointer(topHash)) + 8))
valus := (*[8]string)(unsafe.Pointer(uintptr(unsafe.Pointer(topHash)) + 136))
fmt.Println("keys: ", keys, " values: ", valus)
}
keys: &[IP1 ] values: &[client1 ]
keys: &[IP1 IP2 ] values: &[client1 client2 ]
keys: &[IP1 IP2 IP3 ] values: &[client1 client2 client3 ]
map的遍历
对如下map遍历的代码进行履行汇编指令，能看到其遍历是调用了runtime.mapiterinit()
func main() {
services := make(map[string]string, 0)
services["IP1"] = "client1"
services["IP2"] = "client2"
services["IP3"] = "client3"
for k, v := range services {
fmt.Println(k, v)
}
}
0x0187 00391 (.\main.go:11) CALL runtime.mapiterinit(SB)
这是本文的要点，到底map遍历的随机是怎样随机的。
先说hiter，map的遍历是经过hiter结构体进行遍历的，hiter中包含当时遍历的bucket和cell。
type hiter struct {
key unsafe.Pointer
elem unsafe.Pointer
t *maptype
h *hmap
buckets unsafe.Pointer
bptr *bmap
overflow *[]*bmap
oldoverflow *[]*bmap
startBucket uintptr // 起始遍历的桶，可以理解为从哪个槽位开端
offset uint8 // 偏移，指的是在一个桶中的偏移量。即从哪个cell开端
wrapped bool
B uint8
i uint8
bucket uintptr
checkBucket uintptr
}
mapiterinit的效果便是初始化一个hiter，遍历的起始方位便是在该办法中确认的。
func mapiterinit(t *maptype, h *hmap, it *hiter) {
// ...
// decide where to start
var r uintptr
// 生成一个随机数
if h.B > 31-bucketCntBits {
r = uintptr(fastrand64())
} else {
r = uintptr(fastrand())
}
// 取该随机数的低B位，可确认是从哪个槽位开端
it.startBucket = r & bucketMask(h.B)
// 取随机数的高8位
it.offset = uint8(r >> h.B & (bucketCnt - 1))
// iterator state
it.bucket = it.startBucket
// ...
// 上边初始换完结，调用mapinternext()开端遍历
mapiternext(it)
}
inter的初始化首要生成了一个随机数，然后取低B位，决议从哪个槽位开端。接着取高8位，决议从哪个cell开端。这里咱们就能发现，能作为初始桶的都是非溢出桶，也便是说溢出桶永远都不会作为初始桶。这在一定程度上也决议了map的随机不是很随机的呀。
初始化完结后，调用mapinternext()会对一切的桶依次遍历，最终会回到初始cell的方位，完毕遍历。
func mapiternext(it *hiter) {
// ...
next:
if b == nil {
// 假如回到了开端的cell，完毕遍历
if bucket == it.startBucket && it.wrapped {
// end of iteration
it.key = nil
it.elem = nil
return
}
// ...
}
for ; i < bucketCnt; i++ {
offi := (i + it.offset) & (bucketCnt - 1)
// 假如遍历到空的cell，不做处理，遍历下一个cell
if isEmpty(b.tophash[offi]) || b.tophash[offi] == evacuatedEmpty {
continue
}
// ...
}
// 到下一个桶
goto next
}
然后咱们接着看，咱们现在只有一个桶，无所谓以谁作为初始桶的问题。经过map存储元素进程的剖析，可以知道存储三个元素时的map结构是下边这个姿态滴。
由于map的遍历是要循环回初始cell的，而且没有的元素的cell也会遍历，只是没有值罢了。那岂不是以[3][4][5][6][7][0]作为初始方位的，第一个遍历的元素就都是IP1。那以IP1作为初始方位的概率便是其他两个的6倍。验证一下
func main() {
for i := 0; i < 10; i++ {
testMapRand()
}
}
func testMapRand() {
services := map[string]string{}
services["IP1"] = "client1"
services["IP2"] = "client2"
services["IP3"] = "client3"
// 计数用的
count := map[string]int{}
for i := 0; i < 2000; i++ {
for k, _ := range services {
count[k]++
break
}
}
fmt.Println(count)
}
map[IP1:1534 IP2:243 IP3:223]
map[IP1:1494 IP2:255 IP3:251]
map[IP1:1489 IP2:269 IP3:242]
map[IP1:1499 IP2:247 IP3:254]
map[IP1:1499 IP2:256 IP3:245]
map[IP1:1488 IP2:256 IP3:256]
map[IP1:1492 IP2:242 IP3:266]
map[IP1:1482 IP2:252 IP3:266]
map[IP1:1452 IP2:270 IP3:278]
map[IP1:1504 IP2:240 IP3:256]
还真差不多是6倍的关系。
定论
-
map在一个桶中存储元素时从头遍历8个cell，有可用的就存。
-
map的遍历的随机挑选初始桶时，只在非溢出桶中选，即槽位对应的第一个桶。可是挑选cell时，是8个cell随机的。
-
不可用map遍历的随机性，作为随机挑选map中元素的办法。
在map中随机选取元素的可行办法
将map中的key保存到一个slice中，然后生成随机下表值。再到map中取val。
func main() {
for i := 0; i < 10; i++ {
rand.Seed(time.Now().UnixMicro())
testMapRand()
}
}
func testMapRand() {
services := map[string]string{}
services["IP1"] = "client1"
services["IP2"] = "client2"
services["IP3"] = "client3"
// 取出来key
keys := make([]string, 0)
for k, _ := range services {
keys = append(keys, k)
}
// 计数用的
count := map[string]int{}
for i := 0; i < 2000; i++ {
pick := rand.Intn(len(keys))
count[keys[pick]]++
}
fmt.Println(count)
}
map[IP1:625 IP2:699 IP3:676]
map[IP1:647 IP2:647 IP3:706]
map[IP1:642 IP2:686 IP3:672]
map[IP1:682 IP2:683 IP3:635]
map[IP1:678 IP2:661 IP3:661]
map[IP1:686 IP2:610 IP3:704]
map[IP1:646 IP2:671 IP3:683]
