大厂架构：每天数百亿用户行为数据，美团怎么实现秒级转化分析？( 二 ) _美团

另一方面，还是能够从问题的分析中得到一些“好消息”, 这些也是在设计和优化中可以利用的点。

计算需求非常单一。这个需求最终需要的就是去重计数的结果，这意味着不需要一个大而全的数据引擎，在设计上有很大的优化空间。
并发需求不高。漏斗分析这类需求一般由运营或者产品同学手动提交，查询结果用于辅助决策，因此并发度不会很高，这样可以在一次查询时充分调动整个集群的资源。
数据不可变。所谓日志即事实，用户行为的日志一旦收集进来，除非bug等原因一般不会再更新，基于此可以考虑一些索引类的手段来加速查询。
实际业务特点。最后是对实际业务观察得出的结论，整个漏斗收敛非常快，比如首页是几千万甚至上亿的结果，到了最下层节点可能只有几千，因此可以考虑一些快速过滤的方法来降低查询计算和数据IO的压力。

如果用一句话总结这个问题的核心本质，那就是“多维分析和序列匹配基础上的去重计数” 。具体来说，最终结果就是每层节点符合条件的UUID有多少个，也就是去重后的计数值。这里UUID要符合两个条件，一是符合维度的筛选，二是事件序列能匹配漏斗的定义。去重计数是相对好解的问题，那么问题的重点就是如果快速有效的做维度筛选和序列匹配。
算法设计
下图是部分行为日志的数据，前面已经提到，直接在这样的数据上做维度筛选和序列匹配都是很困难的，因此考虑如何对数据做预处理，以提高执行效率。

文章插图

【大厂架构：每天数百亿用户行为数据，美团怎么实现秒级转化分析？】很自然的想法是基于UUID做聚合，根据时间排序，这也是前面提到的UDAF的思路，如下图所示。这里的问题是没有过滤的手段，每个UUID都需要遍历，成本很高。

文章插图

再进一步，为了更快更方便的做过滤，考虑把维度和属性抽出来构成Key，把对应的UUID和时间戳组织起来构成value 。如果有搜索引擎经验的话，很容易看出来这非常像倒排的思路。

文章插图

这个数据结构还是存在问题。比如说要拿到某个Key对应的UUID列表时，需要遍历所有的value才可以。再比如做时间序列的匹配，这里的时间戳信息被打散了，实际处理起来更困难。因此还可以在此基础上再优化。
可以看到优化后的Key内容保持不变，value被拆成了UUID集合和时间戳序列集合这两部分，这样的好处有两点：一是可以做快速的UUID筛选，通过Key对应的UUID集合运算就可以达成；二是在做时间序列匹配时，对于匹配算法和IO效率都是很友好的，因为时间戳是统一连续存放的，在处理时很方便。

文章插图

基于上述的思路，最终的索引格式如下图所示。这里每个色块对应了一个索引的block，其中包括三部分内容，一是属性名和取值；二是对应的UUID集合，数据通过bitmap格式存储，在快速筛选时效率很高；三是每个UUID对应的时间戳序列，用于序列匹配，在存储时使用差值或变长编码等一些编码压缩手段提高存储效率。

文章插图

在实际应用中，通常会同时指定多个属性或维度条件，通过AND或OR的条件组织起来。这在处理时也很简单，通过语法分析可以把查询条件转为一颗表达树，树上的叶子节点对应的是单个索引数据，非叶子节点就是AND或OR类型的索引，通过并集或交集的思路做集合筛选和序列匹配即可。
上面解决的是维度筛选的问题，另一个序列匹配的问题相对简单很多。基于上述的数据格式，读取UUID对应的每个事件的时间戳序列，检查是否能按照顺序匹配即可。需要注意的是，由于存在最大时间窗口的限制，匹配算法中需要考虑回溯的情况，下图展示了一个具体的例子。在第一次匹配过程中，由于第一层节点的起始时间戳为100，并且时间窗口为10，所以第二层节点的时间戳101符合要求，但第三层节点的时间戳112超过了最大截止时间戳110，因此只能匹配两层节点，但通过回溯之后，第二次可以完整的匹配三层节点。