getaddrinfo 中最长前缀匹配实现导致的DNS 负载均衡失效
DNS 负载均衡方案的失效
通过 DNS 实现负载均衡是一种常见的方案。这种方案通常会返回多个 A 记录，客户端会按照 DNS 响应中的顺序依次尝试去连接服务器，直到成功为止。这个方案对于客户端是有要求的，即客户端必须严格按照 DNS 响应中的地址顺序来访问服务器。在一段不算短的时间以前，大概是 Linux 还未成熟的时候，很多应用还是使用 gethostbyname 来进行 DNS 解析。gethostbyname 接口会严格返回 DNS 响应中的地址顺序，因此应用使用一个循环来进行连接尝试时，就达到了负载均衡的目的。但是，在 getaddrinfo 接口被实现，并且被推荐用来替代 gethostbyname 之后，这个情况就变了。原因是 getaddrinfo 会实现 RFC 3484 (Default Address Selection for Internet Protocol version 6 (IPv6)) 中的地址选择功能，其中的目标地址选择功能直接导致了 DNS 负载均衡方案的失效。简单的说，目标地址选择功能会修改返回给应用程序的 DNS 地址记录的顺序，导致应用程序是按照目标地址选择功能决定的顺序，而不是 DNS 服务器决定的顺序来访问服务器。会导致地址返回顺序被修改的场景很多，本文会描述一种我觉得最常见的失效场景。
失效场景：与 IP 地址的选择有关
失效的场景设置如下图所示：
整个业务的流程是这样的：
- 某个业务有一个客户端，以及三台服务器。采用 DNS 负载均衡方案，让客户端按照一定的比例将请求转发到三个服务器上。
- 客户端需要通过内部的 DNS 服务器来解析域名，获得可以访问的服务器地址。在实现上，从
getaddrinfo返回的第一个地址开始尝试。
DNS 服务器返回的其中一个 DNS 响应如下：
test.dom. 3600 IN A 192.168.192.128
test.dom. 3600 IN A 192.168.192.127
test.dom. 3600 IN A 192.168.192.129
因为我们采用了负载均衡的策略，所以返回的 DNS 响应，每次都会重新排列所有的地址，保证每个地址出现在第一条的概率基本一样。所以，实际上有 6 中排列组合方式。
客户端也有一个同网段的地址：192.168.192.121。所有这些地址，都属于 192.168.192.0/24 这个子网。如本章的标题所示，这些地址的选择是非常重要的，就是地址的值导致了 DNS 负载均衡的失效。
在这个场景中，我们发现我们的客户端程序每次都是去连接 192.168.192.127 这个地址，从来不使用其他两个地址，不管这个 192.168.192.127 的地址是出现在响应中的哪个位置。
问题定位与分析
我们首先排除了 DNS 服务器的问题，以及客户端实现的问题。所以，问题出现在 DNS 请求成功后，到将地址列表返回给客户端程序之前。为了简化问题定位，我们发现 ping 程序也遇到了同样的问题，即 ping 这个域名，都只会使用 192.168.192.127 这个地址。
使用 strace 命令来分析问题
我们先使用 strace ping -c 1 test.dom 命令来看看程序到底做了什么。下面是其中的相关内容（为了好看，我删掉了不相关的内容。另外，如果你想看到更多的参数信息，可以使用 strace 的 -s 参数）：
# 先连接 DNS 服务器，发出 DNS 请求，并且收到响应。
socket(AF_INET, SOCK_DGRAM|SOCK_CLOEXEC|SOCK_NONBLOCK, IPPROTO_IP) = 4
connect(4, {sa_family=AF_INET, sin_port=htons(53), sin_addr=inet_addr("192.168.192.132")}, 16) = 0
sendto(4, "\272\273\1\0\0\1\0\0\0\0\0\0\4test\3dom\0\0\1\0\1", 26, MSG_NOSIGNAL, NULL, 0) = 26
recvfrom(4, "\272\273\205\0\0\1\0\3\0\1\0\0\4test\3dom\0\0\1\0\1\4test\3"..., 1024, 0, {sa_family=AF_INET, sin_port=htons(53), sin_addr=inet_addr("192.168.192.132")}, [16]) = 121
close(4) = 0
# 尝试打开这个文件，见下文。
open("/etc/gai.conf", O_RDONLY|O_CLOEXEC) = -1 ENOENT (No such file or directory)
# 通过 NETLINK 获取一些接口信息 (getifaddrs)
socket(AF_NETLINK, SOCK_RAW, NETLINK_ROUTE) = 4
bind(4, {sa_family=AF_NETLINK, pid=0, groups=00000000}, 12) = 0
getsockname(4, {sa_family=AF_NETLINK, pid=217030, groups=00000000}, [12]) = 0
sendto(4, "\24\0\0\0\26\0\1\3\312W`a\0\0\0\0\0\0\0\0", 20, 0, {sa_family=AF_NETLINK, pid=0, groups=00000000}, 12) = 20
recvmsg(4, {msg_name(12)={sa_family=AF_NETLINK, pid=0, groups=00000000}, msg_iov(1)=[{"L...
recvmsg(4, {msg_name(12)={sa_family=AF_NETLINK, pid=0, groups=00000000}, msg_iov(1)=[{"H
recvmsg(4, {msg_name(12)={sa_family=AF_NETLINK, pid=0, groups=00000000}, msg_iov(1)=[{"...
# 尝试连接 DNS 返回的每个地址，判断是否可用。这里用的是 UDP，所以主要是判断路由是否可达。
socket(AF_INET, SOCK_DGRAM|SOCK_CLOEXEC, IPPROTO_IP) = 4
connect(4, {sa_family=AF_INET, sin_port=htons(0), sin_addr=inet_addr("192.168.192.128")}, 16) = 0
getsockname(4, {sa_family=AF_INET, sin_port=htons(58008), sin_addr=inet_addr("192.168.192.121")}, [16]) = 0
connect(4, {sa_family=AF_UNSPEC, sa_data="\0\0\0\0\0\0\0\0\0\0\0\0\0\0"}, 16) = 0
connect(4, {sa_family=AF_INET, sin_port=htons(0), sin_addr=inet_addr("192.168.192.127")}, 16) = 0
getsockname(4, {sa_family=AF_INET, sin_port=htons(44743), sin_addr=inet_addr("192.168.192.121")}, [16]) = 0
connect(4, {sa_family=AF_UNSPEC, sa_data="\0\0\0\0\0\0\0\0\0\0\0\0\0\0"}, 16) = 0
connect(4, {sa_family=AF_INET, sin_port=htons(0), sin_addr=inet_addr("192.168.192.129")}, 16) = 0
getsockname(4, {sa_family=AF_INET, sin_port=htons(35095), sin_addr=inet_addr("192.168.192.121")}, [16]) = 0
# 开始连接 192.168.192.127。注意到，从上面到这里，没有任何系统调用，所以这里是一段完全由代码和内存数据决定的逻辑。
socket(AF_INET, SOCK_DGRAM, IPPROTO_IP) = 4
connect(4, {sa_family=AF_INET, sin_port=htons(1025), sin_addr=inet_addr("192.168.192.127")}, 16) = 0
getsockname(4, {sa_family=AF_INET, sin_port=htons(34211), sin_addr=inet_addr("192.168.192.121")}, [16]) = 0
setsockopt(3, SOL_RAW, ICMP_FILTER, ~(1<<ICMP_ECHOREPLY|1<<ICMP_DEST_UNREACH|1<<ICMP_SOURCE_QUENCH|1<<ICMP_REDIRECT|1<<ICMP_TIME_EXCEEDED|1<<ICMP_PARAMETERPROB), 4) = 0
setsockopt(3, SOL_IP, IP_RECVERR, [1], 4) = 0
setsockopt(3, SOL_SOCKET, SO_SNDBUF, [324], 4) = 0
setsockopt(3, SOL_SOCKET, SO_RCVBUF, [65536], 4) = 0
getsockopt(3, SOL_SOCKET, SO_RCVBUF, [131072], [4]) = 0
PING test.dom (192.168.192.127) 56(84) bytes of data.
在上面的代码中，我注释了关键的部分。最后，我们可以发现，导致问题的代码是在尝试 connect 之后，以及应用开始使用 IP 地址之前的部分，也就是说，getaddrinfo 导致的问题。但是，为什么 getaddrinfo 这个函数会有这个问题？理论上来说，一个广泛使用的库函数，应该是很稳定的。此时，我注意到了上面的 /etc/gai.conf 这个文件。
getaddrinfo 与 RFC 3484
通过阅读 man gai.conf，我了解到 getaddrinfo 根据 RFC 3484 实现了目的地址排序，再通过阅读 RFC 的相关内容，我了解到，这个排序会涉及到 10 条规则 (RFC 3484, Chapter 6 Destination Address Selection)。通过反复研究这 10 条规则，以及进行一些测试，我判断比较可能是规则 9 导致的问题：
Rule 9: Use longest matching prefix. When DA and DB belong to the same address family (both are IPv6 or both are IPv4): If CommonPrefixLen(DA, Source(DA)) > CommonPrefixLen(DB, Source(DB)), then prefer DA. Similarly, if CommonPrefixLen(DA, Source(DA)) < CommonPrefixLen(DB, Source(DB)), then prefer DB.
那么，RFC 3484 是做什么的呢？这个其实在引入 IPv6 之后，对于网络中一个节点，如何选择源地址与目的地址做出了规定。getaddrinfo 因为涉及到网络地址的选择，所以实现了这个标准。你可能有疑问，为什么一个 IPv6 的标准会影响到 IPv4 的网络，这个主要是因为网络总是要过度的，所以在指定标准的过程中就都进行了考虑。这个标准对于 IPv4 源地址的选择没有做规定，这个取决于操作系统的实现，主要还是路由来决定选择哪个源地址。但是规定了目标地址的选择，比如遵守上面提到的 10 条规则。
为什么我会判断是 Rule 9 导致的问题，主要是结合一下几个方面：
- 客户端和服务器的地址在同一个网段，不会收到路由决策的干扰，且全部处于可用状态。
- 操作系统不存在 /etc/gai.conf 文件，所以不会有 label 和优先级的问题。
- 因为地址都是 IPv4 的私有网段，所以 scope 也都是规定好的，也就没有任何差异。
阅读 glibc 代码并且进行 gdb
当然，上面只是推测，还需要证据。接下来，我们要结合代码来找证据，当然，因为时间有限，不太可能仔细研究代码，所以我一般结合代码和调试信息来定位问题。
glibc 的代码： https://sourceware.org/git/glibc.git。
我们是 CentOS 7.6 的系统，可以在系统上安装 debuginfo 来进行调试：
# 会自动安装 glibc 的 debuginfo。
# debuginfo-install iputils-20160308-10.el7.x86_64
然后使用 gdb 来辅助代码阅读：
# gdb --args ping -c 1 test.dom
(gdb) b getaddrinfo
Breakpoint 1 at 0x2210
(gdb) run
Starting program: /usr/bin/ping -c 1 test.gfs
Breakpoint 1, __GI_getaddrinfo (name=name@entry=0x7fffffffe666 "test.gfs", service=service@entry=0x0, hints=hints@entry=0x7fffffffe270, pai=pai@entry=0x7fffffffe248)
at ../sysdeps/posix/getaddrinfo.c:2208
2208 {
Missing separate debuginfos, use: debuginfo-install libattr-2.4.46-13.el7.x86_64 zlib-1.2.7-18.el7.x86_64
(gdb) b rfc3484_sort
Breakpoint 2 at 0x7ffff6d3df70: file ../sysdeps/posix/getaddrinfo.c, line 1440.
(gdb) c
这个时候，我们就进入到了 glibc 这个库中的 rfc3484_sort 这个函数，函数名字取得很好，最终的问题也是由这里导致的。接下来是逐行分析这个函数的逻辑，过程就不细说了，我们来看结论。
rfc3484_sort Longest Matching Prefix 实现
这个函数的注释很清晰，标明了哪个部分是对应到标准的哪个 rule。通过 gdb 的逐步调试，我们发现，果然是 Rule 9 导致的问题。我们只关心 IPv4 的部分，见下面的代码（代码原始缩进就没对齐）：
// 这个函数是用在快排中的 cmp 函数，用来比较两个地址的优先级。
// 函数里的 a1 和 a2 两个变量，会在快排过程中，对应到 DNS 返回的两个地址，比如 192.168.192.127 和 192.168.192.128。
// 函数运行到这里时，源地址已经选择完毕了，就是根据路由选出来的网卡地址，在这个场景中，就是 192.168.192.121。
/* Rule 9: Use longest matching prefix. */
if (a1->got_source_addr
&& a1->dest_addr->ai_family == a2->dest_addr->ai_family)
{
int bit1 = 0;
int bit2 = 0;
if (a1->dest_addr->ai_family == PF_INET)
{
assert (a1->source_addr.sin6_family == PF_INET);
assert (a2->source_addr.sin6_family == PF_INET);
/* Outside of subnets, as defined by the network masks,
common address prefixes for IPv4 addresses make no sense.
So, define a non-zero value only if source and
destination address are on the same subnet. */
struct sockaddr_in *in1_dst
= (struct sockaddr_in *) a1->dest_addr->ai_addr;
in_addr_t in1_dst_addr = ntohl (in1_dst->sin_addr.s_addr);
struct sockaddr_in *in1_src
= (struct sockaddr_in *) &a1->source_addr;
in_addr_t in1_src_addr = ntohl (in1_src->sin_addr.s_addr);
in_addr_t netmask1 = 0xffffffffu << (32 - a1->prefixlen);
// in1_src_addr 就是选择到的源地址，在这个场景里，就是 192.168.192.121
// netmask1 和 24 位掩码对应： 0xffffff00
// in1_dst_addr 就是参与比较的某个 DNS 响应中的地址。
if ((in1_src_addr & netmask1) == (in1_dst_addr & netmask1))
// 因为我们的客户端和服务端在同一个子网，所以这个条件会成立。
// fls 函数，从左到右找到第一个 1 的位置，最左边是位置 0，最右边是位置 31.
// 将源地址和目标地址进行 XOR，然后找到第一个 1 的位置。
bit1 = fls (in1_dst_addr ^ in1_src_addr);
struct sockaddr_in *in2_dst
= (struct sockaddr_in *) a2->dest_addr->ai_addr;
in_addr_t in2_dst_addr = ntohl (in2_dst->sin_addr.s_addr);
struct sockaddr_in *in2_src
= (struct sockaddr_in *) &a2->source_addr;
in_addr_t in2_src_addr = ntohl (in2_src->sin_addr.s_addr);
in_addr_t netmask2 = 0xffffffffu << (32 - a2->prefixlen);
if ((in2_src_addr & netmask2) == (in2_dst_addr & netmask2))
bit2 = fls (in2_dst_addr ^ in2_src_addr);
}
else if (a1->dest_addr->ai_family == PF_INET6)
{
...
}
// 第一个 1 的位置越靠右边，值越小。注意，如果值相等，就不改变位置。
if (bit1 > bit2)
return -1;
if (bit1 < bit2)
return 1;
}
以我们的场景来说：
192.168.192.127 和 192.168.192.128 进行比较：
HEX(192.168.192.121) = 0xc0a8c079HEX(192.168.192.127) = 0xc0a8c07fHEX(192.168.192.128) = 0xc0a8c080netmask1 = netmask2 = 0xffffff00
bit1 = fls(in1_dst_addr ^ in1_src_addr) = fls(0xc0a8c07f ^ 0xc0a8c079) = 29
bit2 = fls(in2_dst_addr ^ in2_src_addr) = fls(0xc0a8c079 ^ 0xc0a8c080) = 24
因为 bit1 > bit2，所以 192.168.192.127 排在 192.168.192.128 前面。同样，你可以算出 192.168.192.129 的 fls(...) 值为 24，所以它也排在 192.168.192.127 后面。于是，只要服务端返回是这三个地址，192.168.192.127 永远排在第一个。
构造 DNS 轮询不失效的地址
把上面的 192.168.192.127 换成 192.168.192.130，此时，你就会发现，128, 129, 130 这三个地址算出来的 fls(...) 值都是 24，所以 getaddrinfo 不会改变 DNS 响应返回的地址的顺序，DNS 轮询“神奇“的生效了。
再看另外一个例子：
- 客户端是 10.253.1.14
- 三个服务器是 10.253.1.43, 10.253.1.44, 10.253.1.45
- DNS 服务器是 10.253.1.46
使用这些地址，你会算出来三个服务器地址的 fls(...) 都为 26，所以 DNS 轮询又“神奇”的生效了。
Ref
- https://en.wikipedia.org/wiki/Getaddrinfo
- https://access.redhat.com/solutions/22132
- RedHat 官方对于这个问题的解决方案，其实结论是除非关掉 IPv6，否则无解。所以，无解。
- https://daniel.haxx.se/blog/2012/01/03/getaddrinfo-with-round-robin-dns-and-happy-eyeballs/
- https://jameshfisher.com/2018/02/03/what-does-getaddrinfo-do/
- 通过 strace 来介绍了
getaddrinfo做了什么。
- 通过 strace 来介绍了
- https://www.ietf.org/rfc/rfc3484.txt
- https://lists.debian.org/debian-glibc/2007/09/msg00347.html
- 狂喷 RFC 3484 Rule 9
Update
- 2021-10-09:
s/192.168.192.197/192.168.192.127/g
本作品采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可。