利用TrieTree实现功能灰度的新思路

引言

灰度测试作为一种重要的测试手段，可以有效地提高软件的质量和可靠性。在工作中，我们经常开发新功能上线后，为了验证功能，常常会进行灰度测试。一般来说按照会个人灰度、工号末尾、工号取模等灰度策略。今天介绍一种使用TrieTree实现功能灰度的新思路，顺便掌握TrieTree这种数据结构以及适用场景。

什么是TrieTree？

trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。

                                                                                                  --Wikipedia

TrieTree，中文名为字典树（文中后面统一使用字典树替代TrieTree）。顾名思义，就是一个像字典一样的树。像下图就是一颗字典树。

观察上面树结构，可以发现，“这棵”字典树用边来代表字母，而从根结点到树上某一结点的路径就代表了一个字符串。举个例子，1 -> 4 -> 9 -> 14 表示的就是字符串 caa。

字典树的结构非常好懂，我们只需要标记插入进 trie 的是哪些字符串，每次插入完成时在这个字符串所代表的节点处打上标记（end）即可。此外常规字典树有以下三个特性

TrieTree与功能灰度的关系

上一节我们认识了下了什么是字典树，现在回到正题，字典树与功能灰度有什么样的关系？正如前文中提到我们在实现功能灰度的时候会有一系列的灰度策略，灰度策略的某些场景我们可以借用字典树的特征来实现。

下面三个场景可以考虑下使用常规手段如何实现灰度

• 要求对某BU/团队进行功能灰度
• 要求对某BU进行灰度后，BU下的某些团队/某个人不进行灰度
• 如果功能有N种表现形式，分别对BUa灰度N1，BUb灰度N2，以此类推

下面的两段话属于内心独白

老实说如果对于场景一与场景二，我常规做法可能会设置类似于“黑白”名单，在“黑”名单中的用户或者团队进行灰度，同时判断是否在“白”名单中。只有满足黑名单但不满足白名单的情况下才会进行灰度。

对于场景三来说，可能更符合AB-Test场景可能跟AB-Tes不一样的地方是灰度是定向用户，AB-Test更偏向的随机一点。对于这种场景代码中可能会写多种判断。估计实现起来很麻烦，而且后期还需要进行大量测试来保证正确性。

三种场景实现起来一个比一个困难。逻辑也一个比一个复杂。不过我们借用字典树一些特性后可简化大量逻辑判断，接下来我将使用字典树来一步一步实现这三种场景。

场景一：要求对某BU/团队进行功能灰度

  有话常说：程序 = 数据结构 + 算法

我们先把定义好数据结构。下面代码是字典树常用模版，修改isEnd字段为isGray

public class TrieNode {
    private boolean isGray; // 是否灰度
    private Map children; // 子节点
}

要求对某BU/团队进行灰度我们需要知道该用户属于那个BU/团队。好的一点是有接口可以查询到，查询的数据形如xxxx/yyyy/zzzz/... 格式，我们可以借用查询出来的格式，假设需要灰度BU aaaa/bbbb/cccc 与BU aaaa/bbbb/dddd。

我们结合字典树特性分析下需求。我们需要提供可两个方法。一是插入，二是寻找。插入将所给的BU depthPath融入到字典树这个数据结构中，寻找是给定一个BU deptPath判断在字典树中是否存在。

对于插入方法：

• 我们可以将查询出的deptPath用/恰好分割出的每一个字段可当做字典树的一条边。
• 最后一个字段，我们将isGray设置为true。

对于寻找方法：

•  需要注意的是个人的部门信息是多级的，比如说我个人的部门全称为：XX集团-控股公司-XX部门-A基础运维-XX平台。对应的deptPath查询出为 00001/00002/00003/00004/00005(都是胡写的) 。所以灰度粒度在XX集团与XX平台之间(00001 - 00001/00002/00003/00004/00005 )我都应该是命中灰度。

  • 回到代码实现部分，为了达到这一效果我们在遍历deptPath时发现如果children属性不包含当前字段的话，那么需要判断当前TrieNode的isGray是否为true

经过分析推理，我们完成insert跟find方法如下：

  public void insert(String str) {
        TrieNode_1 t = this;
        for (String s : str.split("/")) {
            Map children = t.getChildren();
            if (!children.containsKey(s)) {
                children.put(s,new TrieNode_1());
            }
            t = children.get(s);
        }
        t.setGray(true);
    }

    public boolean find(String str) {
        TrieNode_1 t = this;
        for (String s : str.split("/")) {
            Map children = t.getChildren();
            if (!children.containsKey(s)) {
                //判断当前节点是否为isGray
               return t.isGray();
            }
            t = children.get(s);
        }
        return t.isGray();
    }

代码逻辑相对比较绕，我用几个动图解释下insert与find函数逻辑。

• insert逻辑：

• find 逻辑：

当能查询到时 

当不能查询到时：

注意：当不能查询到时，代码和动图不一样的是，动图里面直接返回的是false，而代码会先判断最后节点（在图中也就是bbbb）的isGray是否为true

最后编写对应的测试，测试通过，我们仅使用不到100行完成场景一的实现

 @Test
    public void test_gray_bu_with_trieTree() {
        TrieNode node = TrieNode.init();
        for (String buGray : getBUGrayList()) {
            node.insert(buGray);
        }

        assertTrue(node.find("aaaa/bbbb/cccc"));
        assertTrue(node.find("aaaa/bbbb/dddd"));
        assertTrue(node.find("aaaa/bbbb/dddd/eeee/tttt"));
        assertTrue(node.find("aaaa/bbbb/cccc/eeee/oooo"));
        assertFalse(node.find("aaaa/bbbb/eeee"));
    }



    private List getBUGrayList() {
        return List.of("aaaa/bbbb/cccc", "aaaa/bbbb/dddd");
    }

场景二：要求对某BU进行灰度后，BU下的某些团队/某个人不进行灰度

如果分别考虑个人跟BU两种情况的话，代码中难免会有些判断。不如我们将两种场景归一化。我们可以将个人看做是BU的特殊情况。还是按照我举例子我的deptPath00001/00002/00003/00004/00005我的工号为123456。两者结合为00001/00002/00003/00004/00005/#123456同时使用特殊符号#标识工号信息防止恰好某个人工号与BU deptPath相同问题。经过这样归一化处理后，代码处理难度大大降低。归一化处理后生成的字典树大概长这样：

接着考虑对某些团队/某个人不进行灰度改如何实现。场景一最后是通过find方法判断是否命中灰度。所以只要想办法让find方法返回为false即可。修改insert方法增加入参isGray。find方法则完全不需要变动。修改如下。

  public void insert(String str, boolean isGray) {
        TrieNode_2 t = this;
        for (String s : str.split("/")) {
            Map children = t.getChildren();
            if (!children.containsKey(s)) {
                children.put(s,new TrieNode_2());
            }
            t = children.get(s);
        }
        t.setGray(isGray);
    }

场景二与场景一不同的是 将灰度判断逻辑交给“用户”判断，用户可配置所有节点是否开启灰度。修改代码后编写相应的测试用例。

     @Test
    public void test_gray_bu_not_gray_bu_with_trieTree() {
        TrieNode node = TrieNode.init();
        for (String buGray : getBUGrayList()) {
            node.insert(buGray, true);
        }
        for (String notGray : getBuNotGrayList()) {
            node.insert(notGray, false);
        }

        assertTrue(node.find("aaaa/bbbb/cccc"));
        assertTrue(node.find("aaaa/bbbb/cccc/qqqq"));
        assertTrue(node.find("aaaa/bbbb/dddd"));
        assertTrue(node.find("aaaa/bbbb/dddd/sssss"));

        assertFalse(node.find("aaaa/bbbb/cccc/eeee/ttttt"));
        assertFalse(node.find("aaaa/bbbb/dddd/#12345"));
        assertFalse(node.find("aaaa/bbbb"));
    }

    private List  getBuNotGrayList() {
        return List.of("aaaa/bbbb/cccc/eeee", "aaaa/bbbb/dddd/#12345");
    }


    private List getBUGrayList() {
        return List.of("aaaa/bbbb/cccc", "aaaa/bbbb/dddd");
    }

场景三：如果功能有N种表现形式，分别对BUa灰度N1，BUb灰度N2，以此类推

我们前两个场景使用boolean来判断是都命中灰度，而对于场景三来说，boolean字段就不适用了，场景三需要的不是true或者false，而是具体的灰度场景。所以对于场景三，我们可以使用枚举来定义不同的灰度场景，这个场景我们假设有四种不同的灰度场景。

public enum GrayEnum {
    // 不灰度
    NO_GRAY,
    // 场景A
    GRAY_A,
    // 场景B
    GRAY_B,
    // 场景C
    GRAY_C;
}

同时只需要小小的修改场景二中的insert与find方法，将原来的isGray布尔值改成GrayEnum枚举即可。需要注意的一点在TrieNode的构造方法里需要将grayEnum赋值为GrayEnum.NO_GRAY，防止空指针异常。

  private TrieNode_3() {
      this.grayEnum = GrayEnum.NO_GRAY;
      this.children = new HashMap();
  }

  public void insert(String str, GrayEnum grayEnum) {
        TrieNode_3 t = this;
        for (String s : str.split("/")) {
            Map children = t.getChildren();
            if (!children.containsKey(s)) {
                children.put(s, new TrieNode_3());
            }
            t = children.get(s);
        }
        t.setGrayEnum(grayEnum);
    }

  public GrayEnum find(String str) {
        TrieNode_3 t = this;
        for (String s : str.split("/")) {
            Map children = t.getChildren();
            if (!children.containsKey(s)) {
                //获取最后一个的节点的grayEnum
                return t.getGrayEnum();
            }
            t = children.get(s);
        }
        return t.getGrayEnum();
    }

编写对应的测试，测试通过，需求完成。

    @Test
    public void test_gray_when_policy_with_trieTree_3() {
        TrieNode_3 node = TrieNode_3.init();
        for (Pair buGray : getBUGrayList()) {
            node.insert(buGray.getL(), buGray.getR());
        }
        for (String notGray : getBuNotGrayList()) {
            node.insert(notGray, GrayEnum.NO_GRAY);
        }

        assertEquals(GrayEnum.GRAY_A, node.find("aaaa/bbbb/cccc"));
        assertEquals(GrayEnum.GRAY_A, node.find("aaaa/bbbb/cccc/qqqq"));
        assertEquals(GrayEnum.GRAY_B, node.find("aaaa/bbbb/dddd"));
        assertEquals(GrayEnum.GRAY_B, node.find("aaaa/bbbb/dddd/sssss"));
        assertEquals(GrayEnum.GRAY_C, node.find("aaaa/bbbb/eeee/#1234"));

        assertEquals(GrayEnum.NO_GRAY, node.find("aaaa/bbbb/cccc/eeee/ttttt"));
        assertEquals(GrayEnum.NO_GRAY, node.find("aaaa/bbbb/dddd/#12345"));
        assertEquals(GrayEnum.NO_GRAY, node.find("aaaa/bbbb"));
    }

    private List getBuNotGrayList() {
        return List.of("aaaa/bbbb/cccc/eeee", "aaaa/bbbb/dddd/#12345");
    }


    private List getBUGrayList() {
        return List.of(
                Pair.of("aaaa/bbbb/cccc", GrayEnum.GRAY_A),
                Pair.of("aaaa/bbbb/dddd", GrayEnum.GRAY_B),
                Pair.of("aaaa/bbbb/eeee/#1234", GrayEnum.GRAY_C)
        );
    }

后记

为什么我会使用字典树来做功能灰度呢？一方面我在现实中真的碰到了对应的需求，同时灰度能力也是慢慢从场景一升级到场景三。另一方面应该跟刷题有关系吧，刷题一些常见的数据结构模板与应用范围碰到类似题型都形成潜意识了吧。不过好在字典树非常适用于文中的三个场景。也算是在工作中“爽”上了一次。

最后总结下字典树的应用范围：字典树非常适合用于前缀匹配。简单来讲就是给你个前缀 ---- 需要找到相同的前缀的所有条目/数目。除了文中所讲的场景外，国内的区县划分、购物网站里面的物品分类等都有很明显的前缀特征（中国/浙江省/杭州市... 、服饰内衣/男装/背心...）。没有前缀特征的没有办法使用(这句话是废话)。

文中数据结构展示地址： www.cs.usfca.edu/~galles/vis…  （原网址输入字符串会拆成字符当做节点，我下载源代码魔改过）