大发一分彩 首页 > 学霸

每天数百亿用户行为数据,美团点评怎么实现秒级转化分析?

2019-10-07 06:23 Hadoop技术博文

很自然的想法是基于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,因此只能匹配两层节点,但通过回溯之后,第二次可以完整的匹配三层节点。

通过上述的讨论和设计,完整的算法如下图所示。其中的核心要点是先通过UUID集合做快速的过滤,再对过滤后的UUID分别做时间戳的匹配,同时上一层节点输出也作为下一层节点的输入,由此达到快速过滤的目的。

工程实现和优化

有了明确的算法思路,接下来再看看工程如何落地。

首先明确的是需要一个分布式的服务,主要包括接口服务、计算框架和文件系统三部分。其中接口服务用于接收查询请求,分析请求并生成实际的查询逻辑;计算框架用于分布式的执行查询逻辑;文件系统存储实际的索引数据,用于响应具体的查询。

这里简单谈一下架构选型的方法论,主要有四点:简单、成熟、可控、可调。

1.简单。不管是架构设计,还是逻辑复杂度和运维成本,都希望尽可能简单。这样的系统可以快速落地,也比较容易掌控。

2.成熟。评估一个系统是否成熟有很多方面,比如社区是否活跃,项目是否有明确的发展规划并能持续落地推进?再比如业界有没有足够多的成功案例,实际应用效果如何?一个成熟的系统在落地时的问题相对较少,出现问题也能参考其它案例比较容易的解决,从而很大程度上降低了整体系统的风险。