共计 3033 个字符，预计需要花费 8 分钟才能阅读完成。
文|李旭东（花名：向旭 )
蚂蚁团体技术专家
蚂蚁中间件研发，专一于 SOFARegistry 及其周边基础设施的开发与优化
本文 2098 字 浏览 8 分钟
|前言|
MOSN 应用了 Subset 算法作为其标签匹配路由负载平衡的形式。本文次要介绍 Subset 的原理，包含了在超大规模集群下 MOSN 的 Subset 所遇到的一些性能瓶颈与采纳的优化算法。
首先， 为什么要优化 Subset 呢？
总体而言，性能瓶颈往往会因为集群规模的增大逐步裸露进去。在蚂蚁的超大规模的集群上，注册核心推送地址列表会对利用造成肯定的开销。
在我所参加过的某一次大规模压测中，外围利用的机器数目十分宏大，当进行公布或者运维的时候，它的地址列表会被推送给所有调用它的利用。
而 MOSN 会接管这份地址列表从新构建本人的路由。当地址列表十分宏大的时候，MOSN 更新 cluster 的性能瓶颈逐步地裸露进去，呈现了较高的 CPU 毛刺，内存在短时间内呈现了上涨，gc 频率也大幅度减少。
通过下方的火焰图，咱们能够看到这次压测期间对某利用的 MOSN 的 pprof：
– Alloc：
– CPU：
从 pprof 能够看到，无论是 CPU 还是 alloc 的开销，构建 SubsetLoadBalancer 都显著占了大头，所以优化这部分的构建是亟待去做的一件事。
最终通过摸索优化， 咱们能够缩小 SubsetLoadBalancer 构建过程中 95% 的 CPU 开销和 75% 的 alloc 开销。
上面让咱们一起回顾下本次优化的过程与思路。
PART. 1–Subset 基本原理介绍
在一个集群里，通常机器会有不同的标签，那么如何将一个申请路由到指定标签的一组机器呢？
MOSN 的做法是把一个服务下的机器依照机标签组合进行事后分组，造成多个子集。在申请的时候，依据申请中的 metadata 信息能够疾速查问到这个申请对应应该匹配到的子集。
如下图所示，能够看到以后有 4 个节点：
标签匹配规定会依据 zone、mosn_aig、mosn_version 这 3 个字段进行匹配路由，依据这 3 个 key 的排序进行组合失去以下匹配门路：
绝对应的匹配树如下：
假如须要拜访 {zone: zone1, mosn_aig: aig1}，那么通过排序后查找程序为 mosn_aig:aig1 -> zone:zone1，查找到 [h1, h2]。
以上就是 Subset 的基本原理介绍。
PART. 2–MOSN 对 Subset 的构建
首先须要输出的参数有两个：
– 带标签的机器列表 hosts，比方 [h1, h2, h3, h4]；
– 用于匹配的 subSetKeys, 如下图：
接着咱们先带上思路，而后浏览源码来看一下 MOSN 的 SubsetLoadBalancer 是如何构建这棵树的。
外围思路如下：
– 遍历每一个 host 的 labels 和 subSetKeys 递归去创立一棵树；
– 对于树的每一个节点，都会遍历一次 hosts 列表，过滤出匹配这个节点的 kvs 的 subHosts，每个节点创立一个子 load balancer。
咱们来看源码图：
整体的构建复杂度是 O (MNK) (M: Subset 树节点个数，N: Hosts 个数, K: 匹配的 Keys）
PART. 3– 构建性能瓶颈剖析
通过对生产的 profile 剖析，咱们发现 SubsetLoadBalancer 的 createSubsets 在 CPU 和 alloc 的火焰图中的占比都较高。所以上面咱们开始编写 benchmark，来优化这一部分的性能。
咱们的输出参数为：
– subSetKeys：
– 8000 个 hosts （每个 hosts 都有 4 个 label, 每个 label 对应 3 种 value）：
接着，咱们来看 CPU 和 alloc_space 的占用状况。
– CPU：
– alloc_space：
从下面两张火焰图中，咱们能够看出 HostMatches 和 setFinalHost 占用了较多的 CPU_time 和 alloc_space。咱们首先来看下 HostMatches：
它的作用是判断一个 host 是不是齐全匹配给定的键值对，且判断这个 host 是否匹配这个匹配树节点。
它的开销次要在于执行次数过多：treeNodes * len(hosts)，所以在集群变大时，这边的运行开销会大幅度回升。
而后咱们再来看一下 setFinalHost：
他的次要逻辑是按 IP 进行去重，同时会附带 copy。如果咱们在 SubsetLoadBalancer 的顶层进行去重，那么它的任意 Subset 都不须要再次去重。因而，这边能够把它改成不去重。
PART. 4– 倒排索引优化构建
在 HostMatches 的这么屡次匹配中，实际上有很多的反复操作，比方对 host label 中某个 kv 判断 equals，在构建过程中反复的次数相当之多。
所以优化的思路能够基于防止这部分反复的开销，从事后构建倒排索引登程。具体步骤开展如下：
1. 输出两项参数:
– subSetKeys：
– hosts：
2. 遍历一次 hosts，针对每个 kv 咱们用 bitmap 构建倒排索引：
3. 依据 subSetKeys 和倒排索引中的 kvs，构建出匹配树，因为索引中是去重的与 hosts 数目无关，这个操作开销占比很低；
4. 对于树的每个节点，利用倒排索引中的 bitmap 做交加疾速失去匹配全副 kv 的 hosts 的索引 bitmap；
5. 应用 bitmap 中存储的 index 从 hosts 中取出对应 subHosts 构建子 load balancer，同时留神此处不须要应用 setFinalHosts 进行去重。
基于上述思路过程开发新的 Subset preIndex 构建算法，能够在 MOSN 的对应 Pull Request 页面查看详情：
https://github.com/mosn/mosn/pull/2010
再分享下增加 benchmark 进行测试的地址：
https://github.com/mosn/mosn/blob/b0da8a69137cea3a60cdc6dfc0784d29c4c2e25a/pkg/upstream/cluster/subset_loadbalancer_test.go#L891
能够看到绝对之前的构建形式，构建速度快了 20 倍，alloc_space 减小了 75%。同时，alloc 次数呈现了大量的回升，这是因为须要额定的构建一次倒排索引所致。
上面察看一下 gc：
咱们能够发现，相较于之前的构建形式，运行期间的内存更小了，而且 CPU 回收的内存也变少了，同时 gc 并行扫描的时长小幅上涨，STW 工夫变的更短。
最初，测试一下在不同 hosts 数目下的优化水平，能够看到在 hosts 数目较多时 （>100)，新的构建算法都会大幅的优于旧的构建算法。
PART. 5– 总结
咱们看到在大规模生产环境中，一些以前不会留神到的性能瓶颈往往会裸露进去，但通过压测，咱们能提前发现并优化这些问题。
目前，该构建算法曾经合并到 MOSN master，作为 MOSN 默认的 SubsetLoadBalancer 构建形式。
在这次优化过程中，咱们用到了一些常见的优化伎俩，如：倒排索引、bitmap。不难看出，这些优化伎俩尽管根底常见，但也获得了现实的优化成果，心愿能对大家有所帮忙。
理解更多
MOSN Star 一下✨：
https://github.com/mosn/mosn
本周举荐浏览
MOSN 文档使用指南
MOSN 1.0 公布，开启新架构演进
MOSN Contributor 采访|开源能够是做力不从心的事
【2022 开源之夏】SOFAStack 和 MOSN 社区我的项目当选后果
