m******0
发帖数: 222 | 1 如题，这个题怎么答，请教各位。题目的背景是，数据量非常大（twitter级别），要
求准确度能反映最近10分钟之内的变化。 |
H**********5
发帖数: 2012 | 2 东邪黄药师助教
发表于 9/18/2017, 10:34:50 PM · 3个赞
求实时 Top K 的做法有很多，但是具体说起来很长，你可以搜一下这样一些算法：
Space Saving, Efficient Count, Lossy Counting, Sticky Sampling, Hash Count.
(如果搜不到对应的论文，就加 Top K Frequent Items / Elements 之类的关键字)
这里我不展开说这些算法是怎么做的，你自己去搜。或者上 Big Data 的班（http://www.jiuzhang.com/course/4/）。我这里主要说一下 Filter 的这个部分怎么设计和整个架构是什么，因为即使你有一个 Realtime Top K 的 Service，你依旧需要设计一下 Filter。
整个架构
整个架构里，可以分为下面几个 Service:
Topic Service
Feature Service
Realtime Top K Service
用户发了一个 Post 之后，Post 要被丢到 Top Service 和 Feature Service 里，做
如下的一些事情：
提取出有哪些 Topic
提取出有哪些 Feature（男，女，年龄层）
然后把 Topic 丢给每一个 Feature 的 Realtime Top K Set 里，也就是把
feature> 这样的pair丢给 Realtime Top K Service 进行处理。这个 service 为不同
的 feature 维护不同的 Top K Topic Set。这样你想知道哪个 Feature 的 Top K 的
时候，就能查到哪个。
你附近的 Top K Topic
这个就区别与上面的 Feature Topic 了。此时我们需要定义一下，这个“附近”到底
有多近。我认为可以以 City 为单位的近。因为 太小了没多少用户发帖就没多少有意
义的 Topic。因为 City 不多，完全可以每个 City 当做一个 Feature。因此答案就很
明显了，根据经纬度找到属于哪个 City，或者模糊一点的话，都不需要知道是哪个
City，直接用 GeoHash 的前 3 位为 Feature 就好了（3位大概 +- 78 KM 范围内)。 |
r*****s
发帖数: 1815 | 3 扯蛋的太多，其实你搭个storms小集群就好了
基本模拟mapreduce的结构，但是实时算。
三层节点，均可水平扩展
非常简单
非常简单 |
R*********4
发帖数: 293 | |
K***s
发帖数: 621 | |
m******0
发帖数: 222 | 6 good point！
如果题目的要求是，没有fancy的工具可以用，只有简单的key-value store（比如
Redis）和50台普通PC机器（彼此联网）呢？
【在 r*****s 的大作中提到】
: 扯蛋的太多，其实你搭个storms小集群就好了
: 基本模拟mapreduce的结构，但是实时算。
: 三层节点，均可水平扩展
: 非常简单
: 非常简单
|
s**x
发帖数: 7506 | 7
1) hash the key randomly so all the 50 machines, each machine gets 1/50 of
the total traffic.
2) each PC has a priority queue with size of 500, update the counter for
each key using the k-v store. update the priority queue
3) the aggregator sends request to all the 50 PCs, merge sort 500*50 data to
generate the final 500 answer.
( mention sampling to get extra credit. LOL)
【在 m******0 的大作中提到】
: good point！
: 如果题目的要求是，没有fancy的工具可以用，只有简单的key-value store（比如
: Redis）和50台普通PC机器（彼此联网）呢？
|
g****y
发帖数: 2810 | 8 还是map reduce啊
：1) hash the key randomly so all the 50 machines, each machine gets 1/50 of
：the total traffic.
：2) each PC has a priority queue with size of 500, update the counter for
：each key using the k-v store. update the priority queue
：3) the aggregator sends request to all the 50 PCs, merge sort 500*50 data
to generate the final 500 answer.
：( mention sampling to get extra credit. LOL)
【在 s**x 的大作中提到】
:
: 1) hash the key randomly so all the 50 machines, each machine gets 1/50 of
: the total traffic.
: 2) each PC has a priority queue with size of 500, update the counter for
: each key using the k-v store. update the priority queue
: 3) the aggregator sends request to all the 50 PCs, merge sort 500*50 data to
: generate the final 500 answer.
: ( mention sampling to get extra credit. LOL)
|
r*****s
发帖数: 1815 | 9 用redis算的话过程稍微复杂一点，但是还是可以算的，提个想法吧。
首先我觉得24小时的这个尺度，都可以做离线算法了，每次mr算个一小时，将就一下就
行了。
我们来讨论一个15分钟的好了。。。
那么再首先一下，粒度不可能是无限的，我们每分钟总结一次。
起15个ordered set，每次来一个新sample点的时候（全部数据都进来未必能撑住，
redis也就handle
10,000数量级的QPS），就往这15个set里同时写进一条。这15个set，后面14个是未来
14分钟我们要用的，前面一个是当前这一分钟我们用的。
查询的时候，从当前set里面取前500。
每过一分钟，就干掉当前set，启用下一个set，并且添加一个空的set，作为15分钟后
要用的set。
这里cost是搞了点，但是我基本保证这玩意可以用。
如果扩展到24小时的话基本上我们要搭persistent层，做lambda架构了。
: good point！
: 如果题目的要求是，没有fancy的工具可以用，只有简单的key-value store（比如
: Redis）和50台普通PC机器（彼此联网）呢？
【在 m******0 的大作中提到】
: good point！
: 如果题目的要求是，没有fancy的工具可以用，只有简单的key-value store（比如
: Redis）和50台普通PC机器（彼此联网）呢？
|
