无规则采集器列表算法(广告运营中的后根跳跃和存储规则的计算问题研究)

　　无规则采集器列表算法(广告运营中的后根跳跃和存储规则的计算问题研究)

　　1、名称说明

　　回根跳跃遍历是指在树结构的回根遍历过程中，跳过那些对计算结果不再有贡献的节点，使遍历速度达到最快的一种遍历方法。它可用于涉及规则匹配的系统。

　　2、研发背景

　　旧的广告运营设计存在一些问题：

　　需要设计一套新的算法​​，使广告运营位置能够支持任意规则的可配置性（匹配性能更好）。

　　3、结构和特点

　　树状结构，使用嵌套集模型存储mysql，根节点存储规则的对象（如操作广告空间，以下简称对象），子节点存储规则。相同规则类型的规则在同一个直分支上，从而限制了树结构，使得根节点外的子节点最多有一个子节点，类似这样：

　　每个节点使用左值节点（lft）、右值节点（rgt）和深度节点（depth）来表示树结构。这种改进后的结构具有以下特点：

　　以上左右值的计算请参考Nested set模型。遍历的时候会根据这些特征跳转。4、数据承载

　　对象及其规则按照树形结构存储在同一张表中。建议表结构设计如下：

　　CREATE TABLE `demo` (

`id` int(11) unsigned NOT NULL AUTO_INCREMENT,

`gid` int(10) unsigned NOT NULL,//用于表示不同的运营广告位，同一个运营广告位，gid相同

`pid` int(10) unsigned NOT NULL,//辅助阅读字段，不参与计算

`topic` varchar(255) NOT NULL DEFAULT '',//规则名OR对象名

`value` blob NOT NULL,//规则的值OR对象的值

`op` varchar(255) NOT NULL DEFAULT '',//规则运算符

`lft` int(10) unsigned NOT NULL,

`rgt` int(10) unsigned NOT NULL,

`depth` int(10) unsigned NOT NULL,

`add_time` int(10) unsigned NOT NULL,

PRIMARY KEY (`id`)

);

　　除了上一节的结构属性外，还有三个关键属性：节点（topic）、节点（value）、节点（op），用于存储业务数据，比如运营广告位，以及存储内容经营广告位及以下限制规则。

　　设计了十种类型的计算：

　　in的数量超过总数的一半，建议使用nin）

　　各种规则和操作组合支持的不同配置的最大数量为（可配置任何规则）：

　　其中，m为规则类型的个数，如城市规则、版本号规则、用户年龄规则等（规则名称不限，规则名称是存储什么规则），10为十操作类型。

　　5、匹配过程

　　其次是遍历的顺序，阅读完可操作的广告空间规则数据列表后：

　　注意op为in或nin时，存储的值只是redis指针，不是规则的真值。这里也可以用mysql来存储指针所指向的真实值。选择redis的主要原因是为了使用redis设置过期时间与活动截止时间一致，实现过期数据的自动清理。

　　拉到列表后，最多遍历一次即可计算出所有满足规则的对象。在遍历过程中，如果某个规则不匹配，就会发生跳转，即直接忽略对象其他规则的匹配过程，所以速度非常快。

　　同一个规则可以有多个规则，它们之间的关系是OR，不同规则之间的关系是and。匹配时，同一规则的多条规则（这里称为同组规则）会跳过同一组的其他规则，匹配不同组规则的其他规则，只要匹配一条，直到该组的所有规则都匹配成功匹配，对象有效；如果任何一组规则不匹配，则跳过所有剩余的组规则并且对象无效。

　　由于同一个广告位只能展示一个对象，在遍历匹配的过程中，如果同一个广告位匹配多个对象，后面匹配的会覆盖前面的（列表按加入时间升序排列），所以最终，只有一个对象生效。

　　最坏情况匹配复杂度：log(n)6、 冲突解决

　　下图A表示可以看到广告A的用户集合，B表示可以看到广告B的用户集合

　　当集合A收录在集合B中时，在同一时间段内，如果您仍然希望用户看到广告A和广告B，这是需要解决的冲突。

　　如上图，在左图中，集合B完全覆盖了集合A，导致集合A中的用户看不到广告A而是看到广告B。此时B的广告应该配置在A的广告之前，所以设置A的用户可以正常看到它。对于广告A，除了集合A之外，来自集合B的用户都可以看到B广告，冲突解决。

　　当 A 和 B 不收录在关系中，而只有一个交集时，配置的顺序对结果有一定的影响，但不存在冲突，发布者沟通协调决定谁先到。

　　两个以上广告的冲突解决等。

　　发挥你的想象力，没有什么不值得的，只有你没想到。

　　参考

　　嵌套集模型