count distinctはどうやって実現されますか？

4610 ワード
Storm
count実現:
count（1|*）は比較的簡単に実現できます。計算機を設置すれば、記録ごとに1を順次加算して、必要なメモリ空間はInt/Longが占有する空間です。
pikeのcountコード:
https://github.com/PPTV/Pike/blob/master/pike/src/main/java/com/pplive/pike/function/builtin/Count.java 
//CountState   long  ，       
public CountState combine(CountState left, CountState right) {
    if (left == null) 
        return right;
    if (right == null)
        return left;
    return new CountState(left.count() + right.count());
}
count distinctの実現：
distinctは重いパラメータをHashSetで保存し、最終的に出力結果をHashSetのsizeでいいです。map分布式のカウントを採用すれば、HashSetに統合してからsizeを求めます。
pikeの中でHashSetを使ってdistinct countコードを求めます。https://github.com/PPTV/Pike/blob/master/pike/src/main/java/com/pplive/pike/function/builtin/DistinctFilter.java 
//      ，
public boolean addIfNew(Object obj) {
    if(obj == null)
        return false;
    boolean result = this._values.add(obj);
    return result;
}

//    
public long size() {
    return this._values.size();
}

//   ，   
public static DistinctFilter merge(ISizeAwareIterable distinctFilters) {
    if (distinctFilters.size() == 1) {
        return distinctFilters.iterator().next();
    }
    HashSet values = new HashSet();
    for(DistinctFilter f : distinctFilters) {
        values.addAll(f._values);
    }
    return new DistinctFilter(values);
}
このような方法の欠点は明らかで、データ量が大きいと、OOMが現れやすいということです。
しかし、多くの応用シーンは正確な重さが必要ではありません。例えば、ページのUVを求めて、私達が注目しているのはトップページのような重点ページのUVです。このようなページの一般的なアクセス量が多く、uvの数量レベルと変化傾向にもっと関心を持っています。このような一般的な統計需要に対して，スマートな数学者たちは確率統計の知識に基づいて基数統計アルゴリズムを発明した。
基数概念と推定アルゴリズムは、以下のリンクされた一連の文章で紹介されています。ここでは、プロジェクトの観点からいくつかのアルゴリズムの実装を検討します。
http://blog.csdn.net/yunlong34574/article/details/48494663
Pikeでは、3つのバージョンのdistinc countを実現し、それぞれlineam-lib、loglogicativecount、およびhyperloglogcountアルゴリズムに対応し、名前からアルゴリズムの空間的複雑さが分かるようになりました。プロジェクトではPike直接copyはstream-libの実現に加え、implemens Serializableインターフェースを加えて、分散式distinct countを実現しました。
Liner Count
Liner Countは最も簡単な基数推定アルゴリズムであり、空間複雑度に定数レベルの低下があり、アルゴリズムステップはこの文章を参照することができる。
http://blog.codinglabs.org/articles/algorithms-for-cardinality-estimation-part-ii.html
Pikeでの実現:https://github.com/PPTV/Pike/blob/master/pike/src/main/java/com/pplive/pike/function/builtin/LinearCountState.java
ラインストーンアルゴリズムは一部のコードも分かりやすく実現しています。Pikeはラインストーンアルゴリズムを使って2つのバージョンのUDAFを実現しました。
  • LinearCount（maxCadinality、expression）はMax Cadinalityをすでに知っていて、誤差は1%の
    • より低いです。
  • LinearCountEx（bit MapBytes、expression）は、Hash Valueを格納するbyte[]の長さを指定し、長いほど誤差が小さい
    • LogLogAdaptive Count
    LogLogAdaptive CountはLog LogLogCount空き樽率によって、Liner Countを使うか、LogLogLogLogCountを使うか、LogLogCount空間複雑度O（log 2（log 2（Nmax）））を決定し、スペースオーバーヘッドを大幅に低減しました。
    http://blog.codinglabs.org/articles/algorithms-for-cardinality-estimation-part-iii.html
    PikeにおけるLog LogAdaptive Countの実現：
    https://github.com/PPTV/Pike/blob/master/pike/src/main/java/com/pplive/pike/function/builtin/LoglogAdaptiveCountState.java
    コードも比較的分かりやすく、LogLogAdaptive Countカウンタを構築し、hash valueでbucket indexを計算するビット数kを指定します。
  • LogloglogAdaptive Count(k，expression)LogLogApptiveCountバケットの個数を指定します。1<です。
    HyperLog LogCount
    HyperLog LogもLogLogCountアルゴリズムに基づいています。相対LogLogAdaptive Count、hyperlogcountは2つの方法で誤差を修正します。
  • は、調和平均を用いて幾何平均を置換し、バケツ中の偏差の大きい値をフィルタリングする
    • 。
  • は、段階別補正アルゴリズム
    • を使用する。
    現在基数推定を行っている工程実践では基本的にHyperLogLogアルゴリズムを使用しています。HyperLogアルゴリズムについては以下の文章で紹介しています。
    http://rainybowe.com/blog/2017/07/13/不思議なHyperLogアルゴリズム/index.
    PikeにおけるHyperLogアルゴリズムの実現：
    https://github.com/PPTV/Pike/blob/master/pike/src/main/java/com/pplive/pike/function/builtin/HyperLoglogCountState.java
    この実装は、同じcopyはstream-libからなりますが、コードは比較的難しいです。主にRegister Setを記憶桶情報データ構造として使用します。Register SetにはInt配列が含まれています。スペースを節約するために、一つのIntの32 bitがまた6つのbucketに分割されました。各bucketは5 bitを使います。bucketに格納されているのは、hash valueでbucket indexを計算するビットを除いた後に最初の1が現れる位置です。
    stream-libの実現に比べて、Kylinの古いバージョンの実現の中で各bucketは1 byteを占有して、記憶範囲はもっと広くて、空間の利用率はそんなに高効率ではないかもしれませんが、コードははっきりしていて、読みやすくなりました。
    Kylin HyperLogソース：
    https://github.com/apache/kylin/blob/master/core-metadata/src/main/java/org/apache/kylin/measure/hllc/HLLCounterOld.java
    現在、新しいバージョンKylinもHyperLogメモリ空間を最適化しました。
    PikeでHyperLog Logを使用するUDAFパラメータの意味はLoglogAdaptiveと全く同じです。
  • HyperLogCount（k，expression）は、HyperLogCountバケットの個数を指定します。
    締め括りをつける
    3つのアルゴリズムは順次漸進し、計算はますます精密になり、HyperLogLogは基本的に基数推定の標準アルゴリズムとなり、pikeのmove/accumulate関数と結合して、少量のメモリを使って、各種のリアルタイムシーンの基数推定需要を実現することができます。
    • pythonは貪食蛇を実現します。
    つの走馬灯のいくつかの設計の構想