Moquette源码分析（二）v0.12订阅树

Moquette 0.12（以下简称M12）的订阅树实现在moquette-0.12/broker/src/main/java/io/moquette/broker/subscriptions，包括：

订阅树版本	M10	M12
订阅树增删改查	SubscriptionDirectory	CTrieSubscriptionDirectory
订阅树	-	CTrie
片段	Token	Token
主题	Topic	Topic
订阅信息	Subscription	Subscription
普通节点	TreeNode	CNode
封装节点	-	INode
墓碑节点	-	TNode

查看源码的时候应该从CTrie开始阅读。

M12定义

为了修复M10的问题，M12提升了很大的数据结构复杂度。细分了三种节点：

• 普通节点：去掉了M10的订阅数量属性，订阅数量通过单独的一次遍历来计算获得
• 封装节点：封装了一个可以原子替换的结构，在被父节点引用不变的情况下，替换掉节点内容
• 墓碑节点：当没有客户端再订阅的时候，用来临时标记需要被移除的节点，然后通过一个独立的CAS替换方法来清理这个墓碑节点。

如下图所示是一棵典型的M12订阅树：

匹配订阅信息过程

M12匹配算法和M10类似，递归遍历整棵树，不再赘述。 （请搜索博客中M10的文章）

增加订阅

M10中，增加订阅的时候从根节点开始浅拷贝，然后从第一个没有创建的节点开始创建新节点，最后用CAS替换根节点；
M12中，封装了INode，可以让父节点到子节点的指针引用不变，替换子节点的CNode内容，因此去掉了从根节点开始的浅拷贝，直接遍历然后创建节点，算法如下：

算法4-1 M12增加节点 
FUNCTION Action insert（Topic topic, INode inode, Subscription newSubscription）
    // 弹出第一个token
    token = topic.headToken
    // 如果有子节点匹配，递归遍历
    IF ANY inode.child.token match token
        RETURN insert(topic.remainingTopic, inode.child.inode, newSubscription)
    // 如果没有节点，开始创建节点
    ELSE
        // 如果遍历完成，说明路径存在，直接加入订阅信息
        IF topic == EMPTY
            insertSubscription(inode, newSubscription)
        ELSE
            // 递归创建新节点，并且把订阅信息加入叶子节点
            newSubINode = recursiveCreateINodeAndAddSubscription(topic, newSubscription)
            // 浅拷贝当前节点，加入新子节点
            newINode = inode.mainNode.copy().addChild(newSubINode)
            // 比较并替换当前节点为新节点
            inode.cas(inode.mainNode, newINode)
END

例如，现在客户端F增加一个新订阅”abc/+/123/new1/new2/new3”，订阅质量为0，我们看看是如何插入的：

1. 递归遍历到N5
   
2. 递归创建新节点，并赋值订阅信息
   
3. 浅拷贝当前节点
   
4. 比较并替换（N2永远指向N5，只是新N5替换了旧N5）
   

取消订阅

取消订阅后仍然有订阅，则只需要更新subscriptions即可，这里也不再叙述。主要描述取消订阅后没有订阅信息的情况。假设A取消订阅“abc/+/123”：

1. 遍历到N5，当发现N5没有其他订阅者后，为N5建立一个墓碑节点：
   
2. 建立完成后清理掉这个墓碑节点，浅拷贝一个N2，将N5从children中去掉，并通过CAS将旧N2替换为新N2：
   

总结

可以看到，M12提升了数据结构复杂度，但降低了逻辑复杂度，并且去掉了重复统计订阅数量的耗时操作，增加了清理工作。

很容易看出还是有一些问题：

• 仍然没有区分非通配符订阅和通配符订阅，无论哪种都要遍历一次树
• “墓碑节点”的设计只能清除最后一个叶子节点，中间节点为空的时候并没有递归清除（比如N2节点已经空了，但没有清除），因为是单向引用，无法向上追溯父节点

Moquette现在一直停留在0.12.1版本（2019年3月3日），作者说要优先进行MQTT 5.0的兼容，所以订阅树这块近期都不会再有太多更新了。