背景
随着 IPv6的推进，我们发现线上需要使用 IPv6 定位的流量已经达到了 8000 QPS。此前我们并未对 IPv6 定位做任何缓存或者其它优化，这部分流量会直接请求定位服务，随着流量进一步提升可能触发调用量报警以及流控。另外由于此前已经对 IPv4 进行了缓存，如果 IPv6 不做相应的优化，因为多了一次 RPC 请求，服务的响应时间会随着 IPv6 流量占比提升而变长。
调研
通过和定位服务负责人沟通，我们获取到如下有用信息：
- IPv6 定位数据是从外部采购，数据量大概是几十万条
- 和 IPv4 类似，前缀相同的地址定位到相同的地域，但是不像 IPv4 使用固定的前3段，具体多少位不确定，由另外一个参数决定
- 数据每天更新一次，每次变更量不大，几百条左右
- 除了提供定位服务之外，还会将定位数据在 HDFS 上存储一份
定位数据示例如下：
代码语言：javascript复制2001:250:200::/48 中国 北京市 北京
2001:250:201::/48 中国 北京市 北京
2001:250:202::/48 中国 北京市 北京
2001:250:203::/48 中国 北京市 北京
2001:250:204::/48 中国 北京市 北京
使用第一行来进行一个说明，如果地址的前 48 位和 2001:250:200:: 的前 48 位一致，则定位到北京。另外需要注意的是虽然示例数据中都是根据前 48 位来进行定位，但是这个值可能是不同的。
方案
从定位数据的格式以及定位逻辑来看，比较适合的数据结构是前缀树，这样可以很好的实现根据前 xx 位进行定位。IPv6 共有 128位，即 128 个 0 和 1，由于值要么是 0 要么是 1，所以构建出来的是一颗二叉树，数据结构相关的代码如下：
代码语言：javascript复制private Node root = new Node();
public class Node {
private Node[] children = new Node[2];
private Integer localId = null;
public Integer getLocalId() {
return localId;
}
public void setLocalId(Integer localId) {
this.localId = localId;
}
public Node getChild(int pos) {
return children[pos];
}
public void setChild(int pos, Node child) {
children[pos] = child;
}
}
比如数据 2001:250:200::/48 只需要使用到前 48 位即可，并且在第 48 位上标记地域信息，构建前缀树的代码如下：
public void put(Inet6Address inet6Address, Integer mask, Integer localId) {
if (inet6Address == null || localId == null || localId <= 0 || mask == null || mask <= 0 || mask > 128) {
return;
}
Address address = new Address(inet6Address);
Node node = root;
for (int i = 0; i < mask; i ) {
int pos = address.valueAt(i);
Node child = node.getChild(pos);
if (child == null) {
child = new Node();
node.setChild(pos, child);
}
node = child;
}
node.setLocalId(localId);
}
public static class Address {
private static int[] temp = new int[]{0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x1};
private byte[] bytes;
public Address(Inet6Address address) {
this.bytes = address.getAddress();
}
public byte valueAt(int pos) {
if (pos < 0 || pos >= 128) {
throw new IllegalArgumentException("pos 的取值范围是 [0, 128)");
}
int num = pos / 8;
int p = pos % 8;
return (byte) ((bytes[num] & temp[p]) >>> (7 - p));
}
}
其中 Address 类是对 JDK 内置类 Inet6Address 的一个封装，提供了便捷的取指定位的方法 valueAt。
通过上述代码使用定位数据的每一行调用 put 方法即可完成前缀树的构建，下边看下构建好的前缀树如何进行查找：
代码语言：javascript复制public Integer get(Inet6Address inet6Address) {
if (inet6Address == null) {
return null;
}
Address address = new Address(inet6Address);
Node node = root;
for (int i = 0; i < 128; i ) {
int pos = address.valueAt(i);
Node child = node.getChild(pos);
if (child == null) {
return null;
}
Integer localId = child.getLocalId();
if (localId != null) {
return localId;
}
node = child;
}
return null;
}
通过上述代码已经可以实现对前缀树进行构建以及查找，需要注意这颗前缀树是不能进行修改的，只能新增和查找。
服务启动的时候需要进行前缀树的初始化，此时会请求 HDFS 拉取定位数据，由于网络请求不总是靠谱的，增加了三次重试，另外在镜像中放置一份数据（更新频率更低）来进行降级，避免服务启动失败。
对于数据更新，使用了一个定时任务每天 8 点更新，因为定位数据每天变更的量很小，这个更新是允许失败的，更新的时候会根据新的定位数据构建一颗前缀树，如果更新成功则替换之前的前缀树，更新结果会记录一条日志，后续只需要关注下相关日志即可，不再做一个很复杂的方案来保证更新成功。
通过上述方案即可处理好 IPv6 的定位，同时由于不使用 RPC 调用，也会给性能和响应时间带来一定的提升。
- END -
