文章目录

一、M12简介

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中,增加订阅的时候从根节点开始浅拷贝,然后从第一个没有创建的节点开始创建新节点,最后用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的兼容,所以订阅树这块近期都不会再有太多更新了。


转载请注明出处http://www.bewindoweb.com/270.html | 三颗豆子
分享许可方式知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议
重大发现:转载注明原文网址的同学刚买了彩票就中奖,刚写完代码就跑通,刚转身就遇到了真爱。
你可能还会喜欢
具体问题具体杠