Go 语言中迭代 map 时的无序性与随机性

陪她去流浪 桃子 2020年08月30日 编辑 阅读次数:4681

在 Go 语言里面,对 map 的每次迭代都不是按某个固定的顺序进行的。规范的说明:

The iteration order over maps is not specified and is not guaranteed to be the same from one iteration to the next.

对 map 的迭代顺序是未指定的,并且不保证前后两次的迭代顺序相同。

领导跟我强调 is not guaranteed 不等于 guaranteed not,即不保证一样保证不一样。 提示我可能使用了未定义行为。不过我觉得规范里面这样说也没啥问题,毕竟:当元素个数只有一个的时候,顺序没法保证不一样吧?哈哈,我抬杠了。

最近的项目中,我简单地直接运用了这个特性:我在并发访问 Elasticsearch 的 Data Nodes 的时候,采用了基于 map 的迭代无序性随机选取一个 Data Node 来进行请求,结果发现部分节点 CPU 占用很高,请求似乎很不均匀。 所以简单地写了段代码验证一下 map 中的元素在迭代时各自出现的概率。

不过,在此之前,需要了解一下 Go 语言中的 map: Go 语言的 map 采用的是哈希表(Hash Table)实现,而不是红黑树,哈希表目前是初始时有 8 个桶,按 2 倍速扩容。 这有助于理解我代码中设置的元素的个数。

代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package main

import "fmt"

func main() {
	nodes := map[string]struct{}{
		`localhost:9200`: {},
		`localhost:9201`: {},
		`localhost:9202`: {},
	}

	count := map[string]int{}

	for i := 0; i < 10000; i++ {
		for endpoint := range nodes {
			count[endpoint]++
			// 假设节点正常,直接退出循环
			break
		}
	}

	fmt.Println(count)
}

节点 nodes 数量分别为 3、5、8 时,结果如下:

localhost:9200: 7482
localhost:9201: 1246
localhost:9202: 1272

localhost:9200: 4989
localhost:9201: 1243
localhost:9202: 1300
localhost:9203: 1207
localhost:9204: 1261

localhost:9200: 1267
localhost:9201: 1246
localhost:9202: 1194
localhost:9203: 1232
localhost:9204: 1291
localhost:9205: 1231
localhost:9206: 1318
localhost:9207: 1221

可以勉强得出一个结论:各元素出现的概率是跟元素总个数有关的。当个数不为 8 的整数倍时,命中的概率落在第 1 个元素上。

所以,使用 map 的无序迭代作为随机算法是不合适的

然后我好奇这个随机迭代是如何做到的,跑去看了一下源代码

1
2
3
4
5
6
7
// decide where to start
r := uintptr(fastrand())
if h.B > 31-bucketCntBits {
	r += uintptr(fastrand()) << 31
}
it.startBucket = r & bucketMask(h.B)
it.offset = uint8(r >> h.B & (bucketCnt - 1))

所以,它是使用快速随机算法随机选了一个桶作为起始桶,并且又快速随机地选择了桶内的任意一个偏移的元素作为起始元素

在迭代的时候,如果桶内 offset + i 处的元素是空的话,就会 continue 跳到下一个元素

1
2
3
4
5
6
offi := (i + it.offset) & (bucketCnt - 1)
if isEmpty(b.tophash[offi]) || b.tophash[offi] == evacuatedEmpty {
	// TODO: emptyRest is hard to use here, as we start iterating
	// in the middle of a bucket. It's feasible, just tricky.
	continue
}

注:哈哈,正如注释所说,continue 在这里的用法并不高效。为空的时候何不直接取第 1 个元素即可?反正最终结果一样。没看太仔细源代码,不过多讨论。

因为桶内的元素是用数组这样的顺序表结构来存储的,所以,不足 8 个的那些概率,都被统计到其中某一个元素头上去了。这也解释了上面概率测试代码的结论。

我后来怎么做了?一个同事建议直接每次都随机,限制总次数为节点数即可。 但是这样会有一个问题:每次都简单地随机取是没法保证每次都取到不同的元素的,这样的取法是有放回地取。 然后又有同事建议用洗牌算法之后再迭代。这样能保证不重复,且是随机的。 但是,集群的节点大多数时候应该是正常的,所以保证第一次足够随机即可。 洗牌算法会把整个数组洗一遍,实属没必要。况且节点元素可能有几百的规模,可能影响性能(接近千万的QPS)。

所以,我直接按照上述 map 内随机的方式,先随机选择一个元素,如果不可用,再顺序尝试下一个元素。只要保证第 1 次的随机够好(我比较相信 Go 标准库能保证这一点),那么就能保证每个元素出现的概率大概一致。 这样的算法:既保证了随机性,也保证了无放回地取完每个元素

测试代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
package main

import (
	"math/rand"
	"os"

	"gopkg.in/yaml.v2"
)

func main() {
	nodes := []string{
		`localhost:9200`,
		`localhost:9201`,
		`localhost:9202`,
		`localhost:9203`,
		`localhost:9204`,
		`localhost:9205`,
		`localhost:9206`,
		`localhost:9207`,
	}

	count := map[string]int{}

	nn := len(nodes)

	for n := 0; n < 10000; n++ {
		for i, first := 0, rand.Intn(nn); i < nn; i++ {
			endpoint := nodes[(first+i)%nn]
			count[endpoint]++
			break
		}
	}

	yaml.NewEncoder(os.Stdout).Encode(count)
}

概率分布:

localhost:9200: 3344
localhost:9201: 3311
localhost:9202: 3345

localhost:9200: 2032
localhost:9201: 2073
localhost:9202: 1998
localhost:9203: 1950
localhost:9204: 1947

localhost:9200: 1242
localhost:9201: 1211
localhost:9202: 1266
localhost:9203: 1215
localhost:9204: 1261
localhost:9205: 1285
localhost:9206: 1253
localhost:9207: 1267

可以看出分布是很均匀的,多次测试的分布均类似。

对于我的场景来说,这种随机性已经足够使用。

标签:Go