Go 语言中迭代 map 时的无序性与随机性
在 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 |
|
节点 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 |
|
所以,它是使用快速随机算法随机选了一个桶作为起始桶,并且又快速随机地选择了桶内的任意一个偏移的元素作为起始元素。
在迭代的时候,如果桶内 offset + i
处的元素是空的话,就会 continue
跳到下一个元素:
1 2 3 4 5 6 |
|
注:哈哈,正如注释所说,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 |
|
概率分布:
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
可以看出分布是很均匀的,多次测试的分布均类似。
对于我的场景来说,这种随机性已经足够使用。