IPv6定位优化

背景

随着 IPv6的推进，我们发现线上需要使用 IPv6 定位的流量已经达到了 8000 QPS。此前我们并未对 IPv6 定位做任何缓存或者其它优化，这部分流量会直接请求定位服务，随着流量进一步提升可能触发调用量报警以及流控。另外由于此前已经对 IPv4 进行了缓存，如果 IPv6 不做相应的优化，因为多了一次 RPC 请求，服务的响应时间会随着 IPv6 流量占比提升而变长。

调研

通过和定位服务负责人沟通，我们获取到如下有用信息：

IPv6 定位数据是从外部采购，数据量大概是几十万条
和 IPv4 类似，前缀相同的地址定位到相同的地域，但是不像 IPv4 使用固定的前3段，具体多少位不确定，由另外一个参数决定
数据每天更新一次，每次变更量不大，几百条左右
除了提供定位服务之外，还会将定位数据在 HDFS 上存储一份

定位数据示例如下：

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，所以构建出来的是一颗二叉树，数据结构相关的代码如下：

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 方法即可完成前缀树的构建，下边看下构建好的前缀树如何进行查找：

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 -