这是尤金·朱列涅夫（Eugene Zhulenev）的客座博客，讲述他在集体学习工程机械和观众建模方面的经验。在Collective，我们不仅致力于机器学习和预测建模等很酷的事情，而且还致力于那些单调乏味的报道。然而，在我们的规模，即使是简单的报告应用程序也可能成为一个具有挑战性的工程问题。这篇文章是基于我在纽约斯卡拉会议上的一篇演讲。这里有幻灯片。github上提供了示例应用程序：https://github.com/collectivemedia/spark-hyperloglog印象日志我们正在构建基于印象日志的报告应用程序。这并不完全是我们从合作伙伴那里获取数据的方式，而是通过广告、网站、Cookie预先聚合的。即使在这种预先聚合的格式中，HDFS上每天也要花费数百GB。广告|网站| Cookie |印象|点击|段------------- |-------------- | --------------- | ----------- | ------ | -------------------------------宝马X5福布斯网站|13e835610ff0d95 | 10 | 1 |[a.m，b.rk，c.rh，d.sn，…]梅赛德斯2015 |福布斯网站|13e8360c8e1233d | 5 | 0 |[a.f，b.rk，c.hs，d.mr，…]诺基亚gizmodo.com网站|13e3c97d526839c | 8 | 0 |[上午、下午、下午、下午、下午、下午，…]苹果音乐reddit.com网站|1357A253F00AC | 3 | 1 |[a.m，b.rk，d.sn，e.gh，…]诺基亚美国有线电视新闻网|13b23555294aced | 2 | 1 |[a.f，b.tk，c.rh，d.sn，…]苹果音乐脸谱网|13e8333d16d723d | 9 | 1 |[上午、下午、下午、下午、下午，…]每个cookie id都分配了4-6个字母的代码段，表示cookie的一些信息，这些信息是我们从Blukai等第三方数据提供商那里获得的。-上午：男-a.f:女性-b.tk:年收入7.5万-10万美元-b.rk:年收入10万-15万美元-c.hs：高中-c.rh:大学-d.sn：单件-先生：已婚例如，如果一个cookie被分配了a.m段，这意味着我们认为（实际上数据提供者认为）这个cookie属于男性。年收入水平和其他人口统计信息也是如此。我们没有确切的信息，一块饼干到底属于谁，也不知道他们的实际年收入水平是多少。这些片段基本上是概率的，但是我们可以从这些数据中获得非常有趣的见解。我们能用这些数据做什么利用这个印象日志，我们可以回答一些有趣的问题我们可以计算出一个特定群体在某个活动的受众中的流行率，例如，在固特异轮胎公司的活动中，男性在优化的受众中扮演什么角色？看过宝马X5广告的人的男女比例是多少福布斯网站看过苹果音乐广告的人的收入分配诺基亚点击分布在不同的教育水平使用这些基本问题，我们可以创建一个"受众概况"，描述在优化的活动或合作伙伴网站中流行的受众类型。蓝条表示这个特定的部分倾向于浏览广告/访问网站的次数多于平均水平，而红色条则意味着更少。比如固特异轮胎，我们希望看到更多的男性观众而不是女性观众。用SQL解决问题SQL看起来是解决这个问题的一个简单选择，但是正如我已经提到的，我们每天都有数百GB的数据，我们需要在几秒钟内根据1年的历史数据获取数据。蜂巢/黑斑羚根本无法解决这个问题。从impressions中选择count（distinct cookie_id）where site='福布斯网站’和ad=‘宝马X5’段包含"a.m"不幸的是，用户可以定义的过滤器组合几乎是无限的，所以预先生成所有可能的报告是不可行的。用户可以使用任意广告、网站、活动、订单筛选组合，并可能希望知道受众与任何细分市场的交集。基于超日志的受众基数逼近我们提出了一个不同的解决方案；我们没有为每个查询提供精确的结果，而是提供了非常高精度的近似数字。通常，错误率在2%左右，这对于这个特定的应用来说是非常好的。我们不需要知道观众中男女曲奇的确切数量。要想知道什么样的观众占主导地位，大概的数字就足够了。我们使用HyperLogLog，这是一种计算不同元素数量（基数）的算法。它使用有限空间，具有可配置的精度。它能够估计大于10^9的基数，典型的准确率为2%，使用1.5kB的内存。性状超对数{def add（cookieId:String）：单位//| A|def cardinality（）：长//| A∪B|def merge（其他：HyperLogLog）：超日志//| A∩B |=| A |+| B |–A∪B |，def intersect（其他：HyperLogLog）：长}下面是一个由HyperLogLog提供的粗略API。您可以添加一个新的cookieId，获得已经添加到其中的唯一cookie的基数估计，将其与另一个超日志合并，最后得到一个交集。需要注意的是，在intersect操作之后，HyperLogLog对象将丢失，并且只有近似的交集基数。因此，通常超对数交集是计算的最后一步。我建议您观看Avi Bryant的精彩演讲，他不仅讨论了HyperLogLog，还讨论了许多其他可用于大数据分析的近似数据结构：代数-analytics。从cookies到HyperLogLog我们把原版原稿分成两张表。对于广告印象表，我们删除细分信息，并按广告和网站汇总cookies、印象和点击量。HyperLogLog可以在聚合函数中使用，类似于如何使用sum操作。Zero是一个空的超日志，而plus操作是merge（顺便说一句，这正是Monoid所需要的属性）广告|网站| Cookies HLL |印象|点击------------- | ------------- | ------------------ | ----------- | ------宝马X5福布斯网站| 超级日志@23sdg4|5468 | 35宝马X5美国有线电视新闻网| HyperLogLog@84jdg4|8943 | 29对于segments表，我们删除广告和站点信息，并按段聚合数据。段| Cookies HLL |印象|点击------------- | ------------------ | ----------- | ------男性|超日志@85sdg4|235468 | 33510万至15万美元超级日志@35jdg4|569473 | 194宝马运动中大学和高中教育的百分比如果您可以想象我们可以将这些表加载到Seq中，那么受众交集就变成了一个非常简单的任务，可以通过几行函数scala操作来解决。案例类受众（ad:String，site:String，hll:HyperLogLog，imp:Long，clk:Long）case类段（name:String，hll:HyperLogLog，imp:Long，clk:Long）val adImpressions:序列[观众]=…val段印象：Seq[Segment]=…val bmwCookies:HyperLogLog=A压缩.filter（.ad="宝马X5"）.map（\.hll）.reduce（\merge\val educatedCookies:HyperLogLog=分段印象.filter（\ Seq中的段（"College"，"High School"））.map（\.hll）.reduce（\merge\val p=（bmwCookies与教育cookies相交）/bmwCookies.count()带有HyperLogLog的Apache Spark数据帧显然，我们不能在一台机器上将所有数据加载到scala Seq中，因为它非常庞大。即使删除了cookie级别的数据并将其转换为HyperLogLog对象，一天的数据量仍约为1-2GB。所以我们不得不使用一些分布式的数据处理框架来解决这个问题，我们选择了Spark。什么是Spark数据帧灵感来自R数据帧和Python/Pandas数据帧按命名列组织的行的分布式集合在Spark