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

陪她去流浪 桃子 阅读次数：22363

在 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

相关文章