论文标题：Wildcard Topic Management using Bloom Filter in Distributed MQTT Brokers
中文标题：分布式MQTT代理中使用布隆过滤器管理通配符主题
作者信息：
- Ryohei Banno，Hitotsubashi University, Graduate School of Social Data Science, Tokyo, Japan
- Yoshito Watanabe，Solid Surface Inc., Tokyo, Japan 电子邮件：banno@computer.org, yoshito.watanabe@solidsurface.co.jp
论文出处：该论文的具体出处在文档中未提及，但根据文档内容推测，可能是在某个与物联网(IoT)系统或消息队列遥测传输(MQTT)协议相关的学术会议上发表。
摘要(Abstract)： MQTT是物联网系统中广泛使用的一种协议，它遵循发布-订阅消息模型，允许MQTT客户端通过指定主题来通信。在大规模系统中，为了提高通信吞吐量和降低延迟，需要在多个代理之间分配负载。当使用多个代理时，共享订阅主题是一种常见的策略，以防止发布消息泛滥。鉴于主题的潜在巨大数量，一些现有方法使用布隆过滤器来存储和管理它们，以节省空间。然而，这些方法在管理通配符时存在困难，即许多查询布隆过滤器可能会发生在搜索一个主题上。本文介绍了一种使用布隆过滤器高效处理通配符主题的方法。该方法通过向布隆过滤器添加订阅主题的前缀来管理它们。通过布隆过滤器搜索发布的主题时，处理方式类似于使用Trie结构，同时考虑通配符模式。实验结果表明，我们的方法在许多情况下比现有方法减少了对布隆过滤器的查询次数。
引言(Introduction)： MQTT是物联网系统中的主要协议之一，它通过MQTT代理允许客户端之间进行通信。由于MQTT代理是消息的集中点，大规模系统需要通过多个代理来分配负载。分布式代理增加了可能的客户连接数，并提高了物联网设备之间的通信吞吐量。在多个代理之间共享订阅主题是避免发布消息泛滥的典型方法。由于主题集可能很大，使用布隆过滤器是一种常见的方法。布隆过滤器允许高效地检查主题的存在，显著减少了共享和管理主题的通信流量和内存使用。然而，处理通配符存在困难。在MQTT协议中，订阅主题可能包含通配符。由于布隆过滤器使用哈希函数并假设精确匹配，通配符主题会导致主题管理效率低下，即需要大量查询布隆过滤器。这种效率低下可能会影响代理的性能，例如吞吐量和延迟。本文提出了一种使用布隆过滤器高效管理通配符主题的新方法。该方法通过向布隆过滤器添加订阅主题的前缀来管理它们。通过布隆过滤器搜索发布的主题时，处理方式类似于Trie结构，并考虑通配符模式。本文的其余部分组织如下：第二节描述了我们对分布式MQTT代理的假设；第三节介绍了MQTT代理订阅管理的相关工作；第四节解释了提出的方法，第五节展示了实验评估。最后，我们在第六节得出结论。
分布式MQTT代理(Distributed MQTT Brokers)： 对于大规模系统，通过多个代理进行负载分配是提高吞吐量和延迟的关键。在后续讨论中，我们假设有多个代理，每个客户端都连接到其中之一。客户端可以像连接到单个代理一样发布和订阅。为此，每个代理根据需要将PUBLISH消息转发到其他代理。一种简单的方法是像MQTT-ST一样转发所有PUBLISH消息。正如一些研究所建议的，共享订阅主题并减少代理之间的流量是提高性能的有效方法。本文关注于共享和管理主题的数据结构。以下是关于共享订阅主题的假设：
- 代理响应接收SUBSCRIBE消息或检测到新代理，与其他代理共享其客户端的订阅主题。
- 当代理接收到PUBLISH消息时，它会检查其他代理中是否有相应的订阅，并确定后续行动，例如将消息转发给代理。
由于主题集可能很大，使用布隆过滤器是一种典型方法。也就是说，代理将主题添加到布隆过滤器并与其他代理共享。然后每个接收PUBLISH消息的代理通过布隆过滤器检查主题的存在。由于布隆过滤器中的误报，每个代理可能需要丢弃从其他代理转发的不必要消息。我们可以通过适当确定布隆过滤器的大小来抑制误报率。我们省略了处理UNSUBSCRIBE消息的细节，但可以通过使用布隆过滤器的一些变体，如计数布隆过滤器来实现。后续部分将解释MQTT主题和布隆过滤器的详细信息。
MQTT主题(MQTT Topics)： 在MQTT协议中，主题是由称为主题级别的项组成的斜杠分隔的字符串，如“building3/room2/temperature”。主题的最大长度为65,535字节。客户端可以使用两种通配符订阅主题。一种是单级通配符“+”，匹配任何单个主题级别；另一种是多级通配符“#”，匹配任何数量的主题级别。多级通配符只出现在主题的末尾。表I中显示了示例。在某些应用中，主题的数量可能是巨大的。例如，我们可以考虑使用Spatial-ID这样的通用空间识别方案中的位置信息。Spatial-ID类似于Slippy地图瓦片名称，但扩展到三维，即空间被划分为体素，在层次结构中，每个体素被分配一个ID。考虑使用这样的体素ID作为主题级别，可能会有大量的主题，每个主题有数十个级别。
布隆过滤器(Bloom Filter)： 布隆过滤器是一种概率性数据结构，可以确认元素是否存在。它是一个长度为b的位数组，最初所有位都设置为0。添加元素包括以下步骤：通过k个哈希函数计算哈希值，获取对应于哈希值的位数组中的k个位置，并将这些位设置为1。搜索元素时，我们计算k个哈希值，获取k个位置，并检查位。如果所有相应的位都是1，则元素以高概率存在。否则，它不存在。注意，我们可以通过按位逻辑或运算轻松合并多个布隆过滤器。搜索结果可能是误报。误报率pfp计算为pfp = (1 − e−(kne/b))k，其中ne是元素的数量。最小化pfp的最优k值为k = (b/ne) ln 2。假设最优k值，b和pfp之间的关系表示为b = −((ln pfp)/(ln 2)2)ne。
相关工作(Related Work)： 由于布隆过滤器在空间和时间效率方面具有优越性，它通常用于主题管理。Dominguez等人利用计数布隆过滤器进行基于主题的发布-订阅消息的订阅管理，并使用MQTT进行了实验。除了MQTT，RabbitMQ这样的面向消息的中间件，其“流过滤”功能内部使用布隆过滤器进行订阅管理。内容中心网络和命名数据网络领域的一些研究也采取了类似的方法，使用布隆过滤器进行消息路由。它们在添加布隆过滤器的前缀方面与我们提出的方法相似。然而，这些都没有考虑高效处理通配符。Naaman和Chen等人介绍了在多个MQTT代理之间共享订阅主题的布隆过滤器。他们的方法考虑了通配符。除了共享订阅主题的布隆过滤器外，每个代理还与其他代理共享一组通配符主题模式。通配符主题模式是一组级别，其中出现两种通配符。例如，如果代理有订阅主题“a/+/c”，“x/+/z”，“a/+/+”和“+/+/#”，则要共享的模式集合类似于[{1;-1}, {1,2;-1}, {0,1;2}]。模式{0,1;2}意味着有一个或多个订阅主题，其中单级通配符出现在级别0和1，多级通配符出现在级别2。在模式中，-1表示没有相应的通配符。注意，我们假设最低级别是0。当代理接收到PUBLISH消息时，它使用布隆过滤器检查主题及其通过模式获得的变体是否存在。例如，如果发布的主题是“x/y/z”，并且共享的模式与上述示例相同，那么使用布隆过滤器搜索以下变体：“x/y/z”，“x/+/z”，“x/+/+”和“+/+/#”。这种方法假设通配符模式的数量很小。多样化的订阅主题可能会导致对布隆过滤器的大量查询。
提出的方法(Proposed Method)： 我们提出了一种使用布隆过滤器高效处理通配符主题的方法。该方法通过向布隆过滤器添加订阅主题的前缀来管理它们。它允许以类似搜索主题树的方式检查主题的存在。如第二节所述，我们假设代理通过其订阅制作布隆过滤器，并与其他代理共享。当代理接收到PUBLISH消息时，它通过其他代理共享的布隆过滤器搜索发布的主题，以确定后续行动，例如将消息转发给代理。以下部分描述了如何用布隆过滤器管理主题。
添加主题到布隆过滤器(Adding topics to Bloom filter)： 要使用布隆过滤器管理主题，我们使用它的前缀。这里，前缀是从开始到特定级别的连续主题级别。例如，考虑主题“foo/bar/baz”，有三个前缀：“foo”，“foo/bar”和“foo/bar/baz”。在添加到布隆过滤器
之前，向最后一个主题级别添加终止符号。以下简称$表示终止符号。然后，我们将每个前缀添加到布隆过滤器中。图2显示了一个示例。订阅主题“a/+/c/d”涉及向布隆过滤器添加以下前缀：“a”，“a/+”，“a/+/c”和“a/+/c/d$”。布隆过滤器的大小应适当确定以抑制误报。我们可以根据允许的误报率pfp和假设的最大元素数量ne通过第二节中描述的方程计算适当的位数组b的长度。我们还可以确定最优的哈希函数数量k。例如，假设pfp = 0.001和ne = 100,000，b大约变为1,437,759位，其中k约为10。
搜索主题(Searching for a topic)： 通过布隆过滤器搜索发布的主题tp的处理方式类似于考虑通配符模式的Trie。设d表示tp的主题级别数，l0, l1, ...ld−1表示主题级别。我们首先搜索以下前缀，其级别数为一：“#$”，“+”和l0”。这些是可能匹配tp的订阅主题的前缀。如果它们都不存在于布隆过滤器中，我们可以得出没有匹配的订阅。相反，如果它们中的任何一个存在于布隆过滤器中，搜索将继续到下一个级别的前缀。在下一步中，要搜索的前缀是通过在上一步在布隆过滤器中找到的前缀后面连接“#$”，“+”和l1获得的。随后，这样的过程重复，直到级别数达到d。注意，当级别数等于d时，我们在以“+”或ld−1结尾的前缀后面添加“$”，然后进行搜索。在此过程中，如果任何以“$”结尾的前缀存在于布隆过滤器中，搜索在该点终止，我们可以得出存在匹配的订阅的高概率结论。否则，搜索结果为没有匹配的订阅。图3显示了搜索过程的示例，我们假设使用图2中的布隆过滤器。绿色框对应于添加到布隆过滤器的前缀。在这种情况下，前缀“a”，“a/+”和“a/+/c”存在于布隆过滤器中，最后，“a/+/c/d$”也存在。因此，结果是存在匹配的订阅。在上述搜索过程中，我们遵循以下政策：
- 使用深度优先搜索。
- 在每个级别首先检查以“#$”结尾的前缀。这些使我们能够在搜索中途终止，如果存在匹配的订阅。伪代码显示在算法1中。函数SEARCH返回true，如果主题以高概率存在于主题中，返回false，如果它肯定不存在。PARSE TOPIC将主题分割为主题级别并返回它们。CONCAT连接给定的字符串。SEARCH HELPER是一个递归调用的函数，用于深度优先搜索，具有以下参数：prefix是上一步中在布隆过滤器中存在的前缀。level是当前打算搜索的前缀的级别数。levelList是发布主题的主题级别的列表。从第8行到第14行，准备在级别检查的前缀。从第15行到第23行，通过增加级别递归处理搜索。CHECK BF是检查给定元素是否存在于布隆过滤器中的函数。
讨论(Discussion)： 由于提出的方法可以在每个级别不存在所有可能的前缀时终止搜索，因此与现有方法相比，预期对布隆过滤器的查询次数较少，现有方法全面搜索通配符模式。表II显示了渐近分析。“BF”是将订阅主题添加到布隆过滤器并搜索所有可能的通配符模式的简单方法。“BF with patterns”是第III节中描述的现有方法。在这里，我们称这种方法为BFP。我们使用以下符号：
- nt：布隆过滤器管理的订阅主题数量。
- nlv：主题的平均级别数。
- np：通配符模式的数量。
- nw：模式中使用的通配符的平均数量。
关于内存空间，提出的方法需要更大的布隆过滤器，因为它添加的是前缀而不是主题。适当的布隆过滤器大小与元素数量成比例，因此变为O(ntnlv)。它比其他方法大，但并不认为有显著影响，因为与实际存储主题相比，布隆过滤器相当小。平均搜索时间强烈依赖于通配符的使用，因此我们通过第V节中的模拟评估它。至于最坏情况，所有方法都有指数阶。然而，最坏情况被认为在提出的方法中很少发生，即在搜索中途不终止就搜索布隆过滤器中嵌入的前缀树的每个分支的概率很低。相反，现有方法相对容易面临最坏情况；如果没有匹配的订阅主题，必须搜索所有可能的模式。我们还在第V节中阐明了这种趋势。
评估(Evaluation)： 为了阐明提出方法的特点，我们使用Java实现进行了模拟实验。评估标准是确认发布主题是否有相应的订阅主题所需的布隆过滤器查询次数。比较目标是第IV-C节中描述的BF和BFP。模拟参数如表III所示。对于每个参数，我们通过改变其值并固定其他参数的默认值来进行模拟。nt是由布隆过滤器管理的订阅主题数量。构成主题的主题级别是随机字符串，长度为10或通配符。nlv是每个主题的主题级别数。在实验中，所有主题都有相同数量的级别，以便于分析。pwc是nt主题中存在通配符主题的概率。假设pwc = 0.5，预计nt/2的主题将包含通配符。注意，每个通配符主题的生成如下。首先，随机生成一个没有通配符的主题。其次，基于它，生成所有可能的通配符主题。然后，从它们中以相等的概率选择一个。lwc是通配符的最小级别。例如，如果lwc = 0，所有主题级别都可以是通配符。我们进行了以下三种模式的订阅主题实验：
- 允许包含仅通配符主题，例如“#”和“+/#”。
- 排除仅通配符主题。
- 排除仅通配符主题和匹配发布主题的主题。
仅通配符主题匹配许多发布主题。特别是，“#”匹配所有主题，可能会导致大量流量。因此，假设大规模系统，客户端可能会避免使用这样的仅通配符主题。此外，由于发布-订阅消息模型的松散耦合特性，PUBLISH消息不一定有匹配的订阅。我们使用上述三种模式来阐明这些不同情况下的差异。发布主题的生成具有nlv主题级别。每个主题级别是长度为10的随机字符串。图4至6显示了结果。请注意，BFP在这些图中表示为“BF w/ patterns”。我们对每种模式进行了10次模拟，并计算了所需的布隆过滤器查询的平均次数。总体而言，提出的方法实现了相对较少的查询次数。特别是，当主题级别数量增加时，提出的方法明显优于现有方法。对于nlv = 10的图6(b)，提出的方法平均需要29.7次查询，不到BFP的两个百分点。在图4(a)、4(b)和4(c)的大多数情况下，平均查询次数为1。这是因为存在以高概率匹配大多数发布主题的订阅主题，如“#”。在每种方法中，这样的主题首先被搜索，以便尽快终止搜索。在图4(c)中，pwc = 0导致相对较多查询次数，因为没有通配符主题可以在搜索中途终止。BFP只需要一次查询，因为没有通配符模式。在图4(d)中，lwc ≥ 1的情况下，主题“#”被排除，因此每种方法的查询次数都超过一个。对于BFP，lwc越大，平均查询次数越小，因为通配符模式减少。
在图5(a)、5(c)和5(d)中，BF在每种情况下大致显示相同的查询次数。BF搜索所有可能的通配符模式，这些模式是从发布主题考虑的。nt、pwc和lwc不影响模式的数量，而nlv显著影响BF的结果，如图5(b)所示。BFP主要受订阅主题中通配符模式的数量影响。增加nlv会增加模式，而增加lwc会减少模式。
图6显示了发布主题未订阅的情况。在这种情况下，BF和BFP需要大量查询，因为它们需要全面搜索相当多的模式。相反，提出的方法实现了较少的查询次数，因为它可以在搜索中途终止，如果某个级别的前缀在布隆过滤器中不存在。图5(b)和6(b)中显示了显著的结果。在这些情况下，提出的方法比现有方法需要的查询次数显著减少。考虑到每个PUBLISH消息都发生布隆过滤器的搜索，这种差异可能影响代理性能。我们在下一节中确认这一点。
对代理性能的影响(Influence on broker performance)： 本节解释了一个实验，以确认布隆过滤器查询次数对代理性能的影响。评估标准是平均出站吞吐量和平均延迟。前者是代理每秒向订阅者发送的消息数量，后者是从发布者到订阅者所需的平均时间。我们使用HiveMQ CE 2024.52作为代理，MQTTLoader v0.8.63作为客户端。我们修改了代理实现，以便在接收PUBLISH消息和将其转发给订阅者之间进行简化的布隆过滤器搜索过程。对于
布隆过滤器实现，我们使用guava 33.1.0-jre4，它内部使用128位MurmurHash3哈希函数。添加到布隆过滤器的预期元素数量设置为10,000，期望的误报率设置为0.001。在测量吞吐量和延迟之前，向布隆过滤器添加了10,000个元素。每个元素是一个长度为100的随机字符串。当代理接收到PUBLISH消息时，会发生处理指定数量的布隆过滤器查询。MQTTLoader的参数设置如下：
- MQTT协议版本：v5.0
- 发布者和订阅者的数量：各1
- 启动和关闭时间：各5秒
- 执行时间：70秒
- 有效载荷大小：1,024字节
- 发布间隔：10微秒
我们使用了三台主机机器作为发布者、订阅者和代理。它们的规格是Intel Core i9-12900 CPU、64 GB RAM、1 GbE网络和Ubuntu 22.04操作系统。图7显示了结果。增加查询次数会带来较小的吞吐量和较高的延迟。考虑到图4至6中显示的结果，提出的方法预计在性能上优于现有方法，这些方法在某些情况下平均查询次数超过100或1,000。
结论(Conclusion)： 在本文中，我们提出了一种使用布隆过滤器管理包括通配符在内的订阅主题的方法。提出的方法向布隆过滤器添加订阅主题的前缀，并实现类似Trie的搜索。实验结果表明，提出的方法在许多情况下比现有方法减少了对布隆过滤器的查询次数。特别是，当主题级别为10且没有匹配的订阅时，所需的查询次数不到现有方法的两个百分点。提出的方法可以显著提高分布式MQTT代理的性能。在未来的工作中，我们计划通过在一些代理产品中实现提出的方法来进行额外的实验，以阐明性能改进的有效性。我们还将考虑代理之间交换布隆过滤器的策略。
