Design Hit Counter

URL: https://leetcode.com/problems/design-hit-counter/description/

这是一道典型的从最基本的算法入手，到设计一个复杂的系统的综合题。

最容易想到的解法

前提：不考虑并发，不考虑数据量。单机作战。

利用一个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 问题。

如果数据量很大，lock 的 performance 会成为整个系统的 bottleneck，怎么办？

多个系统共同协作。

可以设置一个Master Node，好几个Worker Node。由Master Node来分配不同的请求。这里，Master Node分配的时候要尽可能地均匀分配，不然某些 Worker 工作量太大会影响整个系统的性能。均匀分配的方法有很多，比如对请求进行 hash，再根据 hash 值进行分配。

当要 getHits 的时候，每个 Worker Node 独立进行 count，然后返回给 Master Node，并由 Master Node 进行统计并返回。

Reference

http://blog.gainlo.co/index.php/2016/09/12/dropbox-interview-design-hit-counter/