Flink实战: 窗口TopN分析与实现

TopN 的需求场景不管是在离线计算还是实时计算都是比较常见的，例如电商中计算热门销售商品、广告计算中点击数前N的广告、搜索中计算搜索次数前N的搜索词。topN又分为全局topN、分组topN, 比喻说热门销售商品可以直接按照各个商品的销售总额排序，也可以先按照地域分组然后对各个地域下各个商品的销售总额排序。本篇以热门销售商品为例，实时统计每10min内各个地域维度下销售额top10的商品。

这个需求可以分解为以下几个步骤：

• 提取数据中订单时间为事件时间

• 按照区域+商品为维度，统计每个10min中的销售额

• 按照区域为维度，统计该区域的top10 销售额的商品

时间提取

数据源类型是Kafka, 数据为订单数据包含：订单id、订单时间、商品id、区域id、订单金额（包含用户Id在这里省略）

case class Order(orderId: String, orderTime: Long, gdsId: String, amount: Double, areaId: String)

我们这里统计的每10min内的数据，希望按照真实的订单时间统计，那么使用事件时间EventTime,考虑到可能存在数据乱序问题，允许最大延时为30s

val orderStream=ds.assignTimestampsAndWatermarks(new BoundedOutOfOrdernessTimestampExtractor[Order](Time.seconds(30)) {
      override def extractTimestamp(element: Order): Long = element.orderTime
    })

统计销售额

统计每10min中的销售额，例如[9:00,9:10]、[9:10,9:20] 等等，对应Flink中事件时间滚动滚动窗口

val amountStream=dataStream.keyBy(x => {
      x.areaId + "_" + x.gdsId
    }).timeWindow(Time.minutes(10))
      .reduce(new ReduceFunction[Order] {
        override def reduce(value1: Order, value2: Order): Order = {
          Order(value1.orderId, value1.orderTime, value1.gdsId, value1.amount + value2.amount, value1.areaId)
        }
      })

首先以区域areaId与商品gdsId进行keyBy操作分组，使得相同的key流入到同一个task的window 里面计算，窗口函数包含WindowFunction、ReduceFunction、AggregateFunction，由于使用的是聚合操作，无需保留中间结果数据所以直接使用ReduceFunction边读取数据边聚合，减少内存使用。在ReduceFunction中直接对两个order数据销售额相加得到一个新的订单数据

区域维度的top10 销售额的商品

到目前为止已经拿到了每个10min内各个区域下的各个商品的销售额amountStream，现在需要对其按照区域为维度分组，计算top10销售额的商品，需要考虑两个问题：

• 如何获取到10min窗口的所有数据

• 如何排序

先看第一个如何获取到10min窗口的数据，也就是amountStream的每个窗口的输出，这个其实在Flink 官网上也给出了说明，那么就是直接在后面接一个相同大小的窗口即可，那么后面的窗口即获取到了前一个窗口的所有数据，代码如下：

amountStream.keyBy(_.areaId)
      .timeWindow(Time.minutes(10))
      .apply(...)

其实笔者最开始对这里也是不解，为什么后面接一个相同的窗口就能够获取到前一个窗口的输出呢？直到看了一下这里的源码来慢慢理解，事件时间窗口的触发是依靠watermark来推动的，

//AbstractStreamOperator中
public void processWatermark(Watermark mark) throws Exception {
        if (timeServiceManager != null) {
            timeServiceManager.advanceWatermark(mark);
        }
        output.emitWatermark(mark);
    }

这里在前面的时间系统系列也有分析到，advanceWatermark会触发满足要求的窗口，并且将窗口的结果输出，之后在才输出watermark, 在这里有一个很重要的关系watermark是在窗口数据输出之后输出，那么下一个窗口是如何判断上一个窗口的输出应该划分在同一个窗口呢，当然是按照时间，但是窗口输出数据时间是什么呢？

//WindowOperator
private void emitWindowContents(W window, ACC contents) throws Exception {
        timestampedCollector.setAbsoluteTimestamp(window.maxTimestamp());
        processContext.window = window;
        userFunction.process(triggerContext.key, window, processContext, contents, timestampedCollector);
    }

可以看到TimestampedCollector类型的collector,设置的时间正是窗口的endTime, 也就是窗口输出数据的数据时间就是窗口的endTime, 那么同一个窗口的输出数据具有相同的数据时间endTime, 这些数据正好可以在下游窗口被分配到同一个窗口中。在上一个窗口触发之后输出watermark正好可以触发下游窗口的窗口操作。

到现在我们可以获取到每一个地域下的所有商品销售额信息，接下来就是完成排序操作，很容易想到的就是Sorted的数据结构TreeSet或者是优先级队列PriorityQueue , TreeSet 实现原理是红黑树，优先队列实现原理就是最大/最小堆，这两个都可以满足需求，但是需要选择哪一个呢？红黑树的时间复杂度是logN，而堆的构造复杂度是N, 读取复杂度是1， 但是我们这里需要不断的做数据插入那么就涉及不断的构造过程，相对而言选择红黑树比较好(其实flink sql内部做topN也是选择红黑树类型的TreeMap)。

最后一点，是否需要保存所有的数据排序？很显然是不需要的，将TreeSet设置成为升序排序，那么第一个节点数据就是最小值，当TreeSet里面的数据到达N, 就获取第一个节点数据(最小值)与当前需要插入的数据进行比较，如果比其大，则直接舍弃，如果比其小，那么就将TreeSet中第一个节点数据删除，插入新的数据，最终得到的TreeSet 数据就是我们需要的topN。看下apply中代码实现：

new WindowFunction[Order, Order, String, TimeWindow] {
        override def apply(key: String, window: TimeWindow, input: Iterable[Order], out: Collector[Order]): Unit = {
          println("==area===" + key)
          val topMap = new util.TreeSet[Order](new Comparator[Order] {
            override def compare(o1: Order, o2: Order): Int = (o1.amount-o2.amount).toInt
          })
          input.foreach(x => {
            if (topMap.size() >= N) {
              val min=topMap.first()
              if(x.amount>min.amount) {
                  topMap.pollFirst() //舍弃
                  topMap.add(x)
                }
            }else{
              topMap.add(x)
            }
          })
          //这里直接做打印
          topMap.foreach(x=>{
            println(x)
          })
        }
      }

最后直接执行main函数，为了方便做了一个简单的测试只获取1min以内top3,kafka输入数据：

orderId02,1573483405000,gdsId01,500,beijing
orderId03,1573483408000,gdsId02,200,beijing
orderId03,1573483408000,gdsId03,300,beijing
orderId03,1573483408000,gdsId04,400,beijing
orderId07,1573483600000,gdsId01,600,beijing //触发

最终得到的结果：

==area===beijing
Order(orderId03,1573483408000,gdsId03,300.0,beijing)
Order(orderId03,1573483408000,gdsId04,400.0,beijing)
Order(orderId02,1573483405000,gdsId01,500.0,beijing)

总结

到此为止实现了窗口topN功能，我认为比较重要的点就是如何获取窗口的聚合数据并排序，获取窗口的聚合结果就是在后面再接一个相同的窗口，数据排序类似使用最小堆机制。