b*******d
发帖数: 750 | 1 给出了incoming entry的distribution的曲线，qps是几千这样子。这个system有三个
api：
1）getTopTenMillionInPast24Hour()
2) isInTopTenMilionInPast24Hour()
3) notifyWhenJoinOrRemovedFromTopTenMillionInPast24Hour()
自己来architect系统，定义service能提供数据的精度。
我当时给的是个多台机器的架构。我觉得是旧data每秒钟都在产生（任何当前时间进行
的api call，准确来说，1小时零1秒前的数据都是旧的，对算
top10millioninPast24Hour没有意义），但几乎没有任何系统在一秒钟内可以purge掉
这么多的旧数据，所以就要定义一个精度。比如，semantics是“我能保证给结果是精
确的，但是有个最多20分钟的delay”，或者“我不能保证结果是100%精确的，但是我
能最新的query能够实时的反应在结果中，并且返回的结果和真值有90%的重合”。
其实就是说consistency，availability，partition/sharding， 只能选两样。
------------------
我当时的做法：
若干worker，把request 通过hash shard到不同的worker上去，每个worker上记录：
K1: t1, t2, t3, ...., tm
K2: t1', t2', t3', ..., tn'
把各个K对应的时间序列aggregate成hourly slot，或更小的slot（15分钟，或者10分
钟），里面放个counter。
变成：
k1: s1, s2, s3, ...,s24, s25 (old) ...
k2: s1', s2', s3', ..., s24', s25 (old) ...
每个worker接受新的request，找到对应的hourly slot，counter加1.
每个worker上有个一直在run 的job，算每个K的last hour只用把最近24个slot的
counter叠加，然后把结果送给server。server上保持个10million大小的min-Heap.看
是否加入这个值。这里的trick：用个hashmap来快速access heap里的node；把top放到
各个worker上直到它被更新，用来降低和server间的message数量。
另外，新的request来的时候，添加完counter后，也算个sum of recent 24 hours (若
干个旧slot里的值+最新的slot的值)，看是否放入heap中。
这些值几乎都可以放在memory中，可以assume 那个local job 5分钟能全部扫面一次（
因为每个local就算放了几十million的k，每个k的sum也只是24个slot相加，或者旧值
减去23个slot在加上最新的slot，总之非常trivia）。那个server上的heap的更新也足
够快，几乎每秒钟都在被check，必要时更新。
90%只是估计。测试可以通过load testing（在旧log data上）来完成调制参数：比如
有了一个礼拜的log后，任一时刻你都知道真实的top10Million，然后模拟真实的qps在
QA环境下跑一边这些log entry,调用比如1000次api call，看返回的top10Million（就
是那个Heap里的所有值）和真值有多大差别。
可以调的参数包括：worker的个数（shard的数量）；每个local 的copy of min-heap
top更新的速度（需要和server talk），slot的大小（一个小时，半个小时，还是15分
钟）。调节参数使这些api call经常性的达到90+%准确，就可以release这个系统了。
我不是design高手，尽我所能而已。。 | g*****e
发帖数: 282 | 2 我很好奇用什么数据结构来存储和更新当前的有效entry。很久之前做过类似的，fb的
题。返回过去n小时内（n<48）内访问最多的ip。只需要描述，不coding。
我给出的解法是同时维护一个queue（按时间顺序存储当前所有有效entry），max
priority queue（快速求top n）和一个hash function（把queue里的值map到priority
queue的node）。因为ip addr其实就是int32，开个hashtable内存勉强吃得消。如果
是url之类的entry似乎更expensive（转成短url？）。欢迎探讨。
【在 b*******d 的大作中提到】
: 给出了incoming entry的distribution的曲线，qps是几千这样子。这个system有三个
: api：
: 1）getTopTenMillionInPast24Hour()
: 2) isInTopTenMilionInPast24Hour()
: 3) notifyWhenJoinOrRemovedFromTopTenMillionInPast24Hour()
: 自己来architect系统，定义service能提供数据的精度。
: 我当时给的是个多台机器的架构。我觉得是旧data每秒钟都在产生（任何当前时间进行
: 的api call，准确来说，1小时零1秒前的数据都是旧的，对算
: top10millioninPast24Hour没有意义），但几乎没有任何系统在一秒钟内可以purge掉
: 这么多的旧数据，所以就要定义一个精度。比如，semantics是“我能保证给结果是精
|
|
