Design Hit Counter
Last updated
Last updated
URL:
这是一道典型的从最基本的算法入手，到设计一个复杂的系统的综合题。
前提：不考虑并发，不考虑数据量。单机作战。
利用一个Queue，每次 hit 的时候往 Queue 里加当前时间戳，每次 getHits 的时候从 Queue 的头部开始扫，将所有超过当前window size的元素出队，最后Queue的size即为答案。
然而，这里有一个问题。
如果 hit 被调用很多次，而 getHits 的调用次数很少，那么Queue的size必然会很大，这将是对space的一种浪费。Can we improve space usage?
我们需要一个滚动数组，即以 window size 为长度的一个int[] time。该数组用来记录时间戳，同时我们需要记录每一个时间戳的 hit number，所以再建一个 array int[] hit。
当 hit 的时候，将 timestamp 对 window size 取余，存入 int[] time 中，并且更新对应的 hit number。当 getHits 的时候，扫一遍int[] time ，计算 window size 以内的即可。
这里，可以引入 Concurrency 问题。
利用 Lock。
这里，可以引入 Distributed System 问题。
多个系统共同协作。
可以设置一个Master Node，好几个Worker Node。由Master Node来分配不同的请求。这里，Master Node分配的时候要尽可能地均匀分配，不然某些 Worker 工作量太大会影响整个系统的性能。均匀分配的方法有很多，比如对请求进行 hash，再根据 hash 值进行分配。
当要 getHits 的时候，每个 Worker Node 独立进行 count，然后返回给 Master Node，并由 Master Node 进行统计并返回。