Hi,
最近正在研究 Top K 的問題,在研究中找到了 Blink SQL 可以透過維護一個儲存 K 的最大紀錄的
”堆”來優化底下這類 SQL,不過我認為這只能針對 `score` 只會增加不減少的情況。
> SELECT user_id, score
> FROM (
> SELECT *,
> ROW_NUMBER() OVER (ORDER BY score DESC) AS row_num
> FROM user_scores)
> WHERE row_num <= 3
>
>
我的問題是當如果這樣的計算是應用在流數據上,且 `score` 可能隨時間增加或是
Hi Tony!
其实 Flink 对 Top-N 问题并没有很 fancy 的实现... Flink 把 Top-N 问题分成三种情况:
1. 数据只添加,不更新不删除(就像 batch mode)
这种情况的实现是 AppendOnlyTopNFunction,就像你说的一样使用一个 Map
来维护。不能直接使用堆来维护的原因是:因为要告知下游每一条记录的精确排名。
2. 数据可能有添加和更新
这种情况的实现是 UpdatableTopNFunction,但是这个类开头的注释表明了它只能用于以下特殊情况:
* 数据更新后排名只能变小不能变大;
* 数据的 sort
Hi Caizhi,
謝謝你的回答。你的第三點想法給了我蠻大的啟發,我本來設想的情況是能否避免把全部使用者
資料都存放在 state 來解決這個問題,但聽起來這部分是避免不了的。如果我沒有理解錯,你的
作法比較像是將全部使用者的排名資訊都存放在 state,在使用了 rocksdb state backend 的狀況
下,這些資料都不需要在記憶體中實體化,所以不會受限記憶體的擴展性,只有那些需要被放入
Top-N 的資料會被讀取出來存放在一個 in-memory 的堆中做為加速運算的優化。
在我們目前的應用場景中,精確排名不是必要的資訊,可能還有一些不是硬性的需求來鬆綁這個
問題的限制,
Hi Tony!
這些資料都不需要在記憶體中實體化,所以不會受限記憶體的擴展性,只有那些需要被放入 Top-N 的資料會被讀取出來存放在一個 in-memory
> 的堆中做為加速運算的優化。
前两种情况下,由于不需要从老数据中捞记录回 Top-N,state 里其实也只要放 Top-N 的数据。Top-N
的数据先在内存里维护,checkpoint 的时候同步到 state。
第三种情况下,你的说法是社区引入 SortedMapState 后可以实现的情况,现在由于暂时没有引入 SortedMapState,每次读
state 还是会把所有数据都读出来(具体来说有两个 state,
Hi Caizhi,
非常感謝你提供的資訊和講解,這對我幫助非常大。我會試著把這些知識應用到我們的案例中。
Best Regards,
Tony Wei
Caizhi Weng 於 2019年7月12日 週五 下午12:31寫道:
> Hi Tony!
>
> 這些資料都不需要在記憶體中實體化,所以不會受限記憶體的擴展性,只有那些需要被放入 Top-N 的資料會被讀取出來存放在一個 in-memory
> > 的堆中做為加速運算的優化。
>
>
> 前两种情况下,由于不需要从老数据中捞记录回 Top-N,state 里其实也只要放 Top-N 的数据。Top-N
> 的数据先在内存