最近的访问次数

class VideoService{
  String readFromDb(String key){

  }
  String get(String key){
    //如果key为热门key，则将key/value缓存下来
  }
}

如果一个 key 在最近 N 分钟内被 get 次数大于 M，则称该帖子为热 key，把热 key 缓存到内存中。请使用 Java 实现 get 方法。

思路就是每次 get 产生一个事件，把事件放到队列 Q 中（按照时间放）。同时维护一个map string=>int，表示每个 key 的访问次数。对 Q 中的过期数据进行清理的时候，对 map 进行相应的修改操作。
如果 QPS 太大，会导致 Q 中的事件变得非常多。解决思路是时间离散化，将 key+时间戳作为唯一键统计次数。Q 中每个元素 Node 如下：

class Node{
  long timeStamp;
  Map<String,Integer> vis;
}

每次产生的事件，都往队列 Q 中的最后一个元素内写入。同时维护一个map string=>int。

以上为内存中的实现。
现在我们要实现一个访问次数的服务，如何实现一个这样的微服务。

service CounterService{
  boolean emitCounter(String key);
  long query(String key,long t);//查询最近k秒内的访问次数
}

使用 Redis 实现，这样才能够适合多机运行。使用 prefix+timestamp 的形式作为 key，类型为哈希。每一秒产生一个这样的 key，过期时间设置为 t+Ns。

这样做的坏处就是存在大 key，例如 key 有 10 万个，就导致 redis 存在大 key。解决方式是直接把 key+timestamp 作为 key。这样就可以避免一个 key 对应的数据量太大。

面试