系统设计题面试八股文背诵版

文章目录：

• 面试时回答系统设计题的思路

• 系统的一些性能指标

• 经典系统设计题与思路

  • 分布式ID生成器

  • 短网址系统

  • 定时任务调度器

  • 最近一个小时内访问频率最高的10个IP

  • key-Value存储引擎

  • Manifest文件

  • Log文件

  • 数据流采样

  • 基数估计

  • 频率估计

  • Top k频繁项

  • 范围查询

  • 成员查询

面试时回答系统设计题的思路

这部分内容主要参考了Github的一个国外的开源项目

常见的系统设计题有设计一个秒杀系统、红包雨、URL短网址等，完成一个系统设计题大概需要分为四步。

需要注意的是，在面试过程中是比较紧张的，但遇到这种系统设计题，一定先不要急着回答，一定要先需要设计系统的一些使用场景。

1. 第一步：像面试官不断提问，搞清楚系统的使用场景

   • 系统的功能是什么
   • 系统的目标群体是什么
   • 系统的用户量有多大
   • 希望每秒钟处理多少请求？
   • 希望处理多少数据？
   • 希望的读写比率？

2. 第二步：创造一个高层级的设计

   • 画出主要的组件和连接

     例如设计一个网络爬虫，这个是个完整的架构图，在这一步只需要画出一个抽象的架构图即可，不需要这么具体。
   • 

   • 1. 设计核心组件

        对每一个核心组件进行具体地分析。例如，面试官让你设计一个url短网址，你需要考虑这些问题

        • 数据库查找
        • MD5和 Base62
        • Hash 碰撞
        • SQL 还是 NoSQL
        • 数据库模型
        • 生成并储存一个完整 url 的 hash
        • 将一个 hashed url 翻译成完整的 url
        • API 和面向对象设计

     2. 对系统进行优化

        找到系统的瓶颈所在，对其进行优化，例如可以考虑水平扩展、数据库分片等等。

     系统的一些性能指标

     1. 响应时间

        响应时间指从发出请求开始到收到最后响应数据所需的时间，响应时间是系统最重要的性能指标其直观地反映了系统的“快慢”。

     2. 并发数

        并发数指系统能够同时处理请求的数目，这个数字反映了系统的负载特性。

     3. 吞吐量

        吞吐量指单位时间内系统处理的请求数量，体现系统的整体处理能力。

        QPS（Query Per Second）：服务器每秒可以执行的查询次数

        TPS（Transaction Per Second）：服务器每秒处理的事务数

        并发数=QPS*平均响应时间

     4. 经常听到的一些系统活跃度的名词

        • PV（Page View）

          页面点击量或者浏览量，用户每次对网站中的每个页面访问均被记录一个PV，多次访问则会累计。

        • UV（Unique visitor）

          独立访客，统计一天内访问网站的用户数，一个用户多次访问网站算一个用户

        • IP（Internet Protocol）

          指一天内访问某站点的IP总数，以用户的IP地址作为统计的指标，相同IP多次访问某站点算一次

          IP和UV的区别：

          在同一个IP地址下，两个不同的账号访问同一个站点，UV算两次，IP算一次

        • DAU（Daily Active User）：日活跃用户数量。

        • MAU(monthly active users)：月活跃用户人数。

     5. 常用软件的QPS

        通过了解这些软件的QPS可以更清楚地找出系统的瓶颈所在。

        • Nginx：一般Nginx的QPS是比较大的，单机的可达到30万
        • MySQL：对于读操作可达几百k，对于写操作更低，大概只有100k
        • Redis：大概在几万左右，像set命令甚至可达10万
        • Tomcat：单机 Tomcat 的QPS 在 2万左右。
        • Memcached：大概在几十万左右

     经典系统设计题与思路

     这里列举了一些比较经典的系统设计题，并给出了解题思路，该部分内容来源于Gitbook

     分布式ID生成器

     如何设计一个分布式ID生成器(Distributed ID Generator)，并保证ID按时间粗略有序？

     应用场景(Scenario)

     现实中很多业务都有生成唯一ID的需求，例如：

     • 用户ID
     • 微博ID
     • 聊天消息ID
     • 帖子ID
     • 订单ID

     需求(Needs)

     这个ID往往会作为数据库主键，所以需要保证全局唯一。数据库会在这个字段上建立聚集索引(Clustered Index，参考 MySQL InnoDB)，即该字段会影响各条数据再物理存储上的顺序。

     ID还要尽可能短，节省内存，让数据库索引效率更高。基本上64位整数能够满足绝大多数的场景，但是如果能做到比64位更短那就更好了。需要根据具体业务进行分析，预估出ID的最大值，这个最大值通常比64位整数的上限小很多，于是我们可以用更少的bit表示这个ID。

     查询的时候，往往有分页或者排序的需求，所以需要给每条数据添加一个时间字段，并在其上建立普通索引(Secondary Index)。但是普通索引的访问效率比聚集索引慢，如果能够让ID按照时间粗略有序，则可以省去这个时间字段。为什么不是按照时间精确有序呢？因为按照时间精确有序是做不到的，除非用一个单机算法，在分布式场景下做到精确有序性能一般很差。

     这就引出了ID生成的三大核心需求：

     • 全局唯一(unique)
     • 按照时间粗略有序(sortable by time)
     • 尽可能短

     下面介绍一些常用的生成ID的方法。

     UUID

     用过MongoDB的人会知道，MongoDB会自动给每一条数据赋予一个唯一的ObjectId,保证不会重复，这是怎么做到的呢？实际上它用的是一种UUID算法，生成的ObjectId占12个字节，由以下几个部分组成，

     • 4个字节表示的Unix timestamp,
     • 3个字节表示的机器的ID
     • 2个字节表示的进程ID
     • 3个字节表示的计数器

     UUID是一类算法的统称，具体有不同的实现。UUID的优点是每台机器可以独立产生ID，理论上保证不会重复，所以天然是分布式的，缺点是生成的ID太长，不仅占用内存，而且索引查询效率低。

     多台MySQL服务器

     既然MySQL可以产生自增ID，那么用多台MySQL服务器，能否组成一个高性能的分布式发号器呢？显然可以。

     假设用8台MySQL服务器协同工作，第一台MySQL初始值是1，每次自增8，第二台MySQL初始值是2，每次自增8，依次类推。前面用一个 round-robin load balancer 挡着，每来一个请求，由 round-robin balancer 随机地将请求发给8台MySQL中的任意一个，然后返回一个ID。

     Flickr就是这么做的，仅仅使用了两台MySQL服务器。可见这个方法虽然简单无脑，但是性能足够好。不过要注意，在MySQL中，不需要把所有ID都存下来，每台机器只需要存一个MAX_ID就可以了。这需要用到MySQL的一个REPLACE INTO特性。

     这个方法跟单台数据库比，缺点是ID是不是严格递增的，只是粗略递增的。不过这个问题不大，我们的目标是粗略有序，不需要严格递增。

     Twitter Snowflake

     比如 Twitter 有个成熟的开源项目，就是专门生成ID的，Twitter Snowflake 。Snowflake的核心算法如下：

     

     最高位不用，永远为0，其余三组bit占位均可浮动，看具体的业务需求而定。默认情况下41bit的时间戳可以支持该算法使用到2082年，10bit的工作机器id可以支持1023台机器，序列号支持1毫秒产生4095个自增序列id。

     Instagram用了类似的方案，41位表示时间戳，13位表示shard Id(一个shard Id对应一台PostgreSQL机器),最低10位表示自增ID，怎么样，跟Snowflake的设计非常类似吧。这个方案用一个PostgreSQL集群代替了Twitter Snowflake 集群，优点是利用了现成的PostgreSQL，容易懂，维护方便。

     有的面试官会问，如何让ID可以粗略的按照时间排序？上面的这种格式的ID，含有时间戳，且在高位，恰好满足要求。如果面试官又问，如何保证ID严格有序呢？在分布式这个场景下，是做不到的，要想高性能，只能做到粗略有序，无法保证严格有序。

     短网址系统

     如何设计一个短网址服务(TinyURL)？

     使用场景(Scenario)

     微博和Twitter都有140字数的限制，如果分享一个长网址，很容易就超出限制，发布出去。短网址服务可以把一个长网址变成短网址，方便在社交网络上传播。

     需求(Needs)

     很显然，要尽可能的短。长度设计为多少才合适呢？

     短网址的长度

     当前互联网上的网页总数大概是 45亿，45亿超过了 2^{32}=4294967296232=4294967296，但远远小于64位整数的上限值，那么用一个64位整数足够了。

     微博的短网址服务用的是长度为7的字符串，这个字符串可以看做是62进制的数，那么最大能表示{62}^7=352161****208627=3521614606208个网址，远远大于45亿。所以长度为7就足够了。

     一个64位整数如何转化为字符串呢？，假设我们只是用大小写字母加数字，那么可以看做是62进制数，log_{62} {(2^{64}-1)}=10.7log62(264−1)=10.7，即字符串最长11就足够了。

     实际生产中，还可以再短一点，比如新浪微博采用的长度就是7，因为 62^7=352161****208627=3521614606208，这个量级远远超过互联网上的URL总数了，绝对够用了。

     现代的web服务器（例如Apache, Nginx）大部分都区分URL里的大小写了，所以用大小写字母来区分不同的URL是没问题的。

     因此，正确答案：长度不超过7的字符串，由大小写字母加数字共62个字母组成

     一对一还是一对多映射？

     一个长网址，对应一个短网址，还是可以对应多个短网址？这也是个重大选择问题

     一般而言，一个长网址，在不同的地点，不同的用户等情况下，生成的短网址应该不一样，这样，在后端数据库中，可以更好的进行数据分析。如果一个长网址与一个短网址一一对应，那么在数据库中，仅有一行数据，无法区分不同的来源，就无法做数据分析了。

     以这个7位长度的短网址作为唯一ID，这个ID下可以挂各种信息，比如生成该网址的用户名，所在网站，HTTP头部的 User Agent等信息，收集了这些信息，才有可能在后面做大数据分析，挖掘数据的价值。短网址服务商的一大盈利来源就是这些数据。

     正确答案：一对多

     如何计算短网址

     现在我们设定了短网址是一个长度为7的字符串，如何计算得到这个短网址呢？

     最容易想到的办法是哈希，先hash得到一个64位整数，将它转化为62进制整，截取低7位即可。但是哈希算***有冲突，如何处理冲突呢，又是一个麻烦。这个方法只是转移了矛盾，没有解决矛盾，抛弃。

     **正确答案：**分布式ID生成器

     如何存储

     如果存储短网址和长网址的对应关系？以短网址为 primary key, 长网址为value, 可以用传统的关系数据库存起来，例如MySQL, PostgreSQL，也可以用任意一个分布式KV数据库，例如Redis, LevelDB。

     如果你手痒想要手工设计这个存储，那就是另一个话题了，你需要完整地造一个KV存储引擎轮子。当前流行的KV存储引擎有LevelDB和RockDB，去读它们的源码吧

     301还是302重定向

     这也是一个有意思的问题。这个问题主要是考察你对301和302的理解，以及浏览器缓存机制的理解。

     301是永久重定向，302是临时重定向。短地址一经生成就不会变化，所以用301是符合http语义的。但是如果用了301， Google，百度等搜索引擎，搜索的时候会直接展示真实地址，那我们就无法统计到短地址被点击的次数了，也无法收集用户的Cookie, User Agent 等信息，这些信息可以用来做很多有意思的大数据分析，也是短网址服务商的主要盈利来源。

     所以，正确答案是302重定向。

     可以抓包看看新浪微博的短网址是怎么做的，使用 Chrome 浏览器，是我事先发微博自动生成的短网址。来抓包看看返回的结果是啥

     
     

   • 可见新浪微博用的就是302临时重定向。

     预防攻击

     如果一些别有用心的黑客，短时间内向TinyURL服务器发送大量的请求，会迅速耗光ID，怎么办呢？

     首先，限制IP的单日请求总数，超过阈值则直接拒绝服务。

     光限制IP的请求数还不够，因为黑客一般手里有上百万台肉鸡的，IP地址大大的有，所以光限制IP作用不大。

     可以用一台Redis作为缓存服务器，存储的不是 ID->长网址，而是 长网址->ID，仅存储一天以内的数据，用LRU机制进行淘汰。这样，如果黑客大量发同一个长网址过来，直接从缓存服务器里返回短网址即可，他就无法耗光我们的ID了。

     定时任务调度器

     请实现一个定时任务调度器，有很多任务，每个任务都有一个时间戳，任务会在该时间点开始执行。

     定时执行任务是一个很常见的需求，例如Uber打车48小时后自动好评，淘宝购物15天后默认好评，等等。

     方案1: PriorityBlockingQueue + Polling

     我们很快可以想到第一个办法：

     • 用一个java.util.concurrent.PriorityBlockingQueue来作为优先队列。因为我们需要一个优先队列，又需要线程安全，用PriorityBlockingQueue再合适不过了。你也可以手工实现一个自己的PriorityBlockingQueue，用java.util.PriorityQueue + ReentrantLock，用一把锁把这个队列保护起来，就是线程安全的啦
     • 对于生产者，可以用一个while(true)，造一些随机任务塞进去
     • 对于消费者，起一个线程，在 while(true)里每隔几秒检查一下队列，如果有任务，则取出来执行。

     这个方案的确可行，总结起来就是轮询(polling)。轮询通常有个很大的缺点，就是时间间隔不好设置，间隔太长，任务无法及时处理，间隔太短，会很耗CPU。

     方案2: PriorityBlockingQueue + 时间差

     可以把方案1改进一下，while(true)里的逻辑变成：

     • 偷看一下堆顶的元素，但并不取出来，如果该任务过期了，则取出来
     • 如果没过期，则计算一下时间差，然后 sleep()该时间差

     不再是 sleep() 一个固定间隔了，消除了轮询的缺点。

     稍等！这个方案其实有个致命的缺陷，导致它比 PiorityBlockingQueue + Polling 更加不可用，这个缺点是什么呢？。。。假设当前堆顶的任务在100秒后执行，消费者线程peek()偷看到了后，开始sleep 100秒，这时候一个新的任务插了进来，该任务在10秒后应该执行，但是由于消费者线程要睡眠100秒，这个新任务无法及时处理

     方案3: DelayQueue

     方案2虽然已经不错了，但是还可以优化一下，Java里有一个DelayQueue，完全符合题目的要求。DelayQueue 设计得非常巧妙，可以看做是一个特化版的PriorityBlockingQueue，它把计算时间差并让消费者等待该时间差的功能集成进了队列，消费者不需要关心时间差的事情了，直接在while(true)里不断take()就行了。

     DelayQueue的实现原理见下面的代码。

     import java.util.PriorityQueue; import java.util.concurrent.Delayed; import java.util.concurrent.locks.Condition; import java.util.concurrent.locks.ReentrantLock; import static java.util.concurrent.TimeUnit.NANOSECONDS; public class DelayQueue<E extends Delayed> {
         private final transient ReentrantLock lock = new ReentrantLock();
         private final PriorityQueue<E> q = new PriorityQueue<E>();
         private final Condition available = lock.newCondition();
         private Thread leader = null;
     
         public DelayQueue() {}
     
         /**
          * Inserts the specified element into this delay queue.
          *
          * @param e the element to add
          * @return {@code true}
          * @throws NullPointerException if the specified element is null
          */     public boolean put(E e) {
             final ReentrantLock lock = this.lock;
             lock.lock();
             try {
                 q.offer(e);
                 if (q.peek() == e) {
                     leader = null;
                     available.signal();
                 }
                 return true;
             } finally {
                 lock.unlock();
             }
         }
     
         /**
          * Retrieves and removes the head of this queue, waiting if necessary
          * until an element with an expired delay is available on this queue.
          *
          * @return the head of this queue
          * @throws InterruptedException {@inheritDoc}
          */     public E take() throws InterruptedException {
             final ReentrantLock lock = this.lock;
             lock.lockInterruptibly();
             try {
                 for (;;) {
                     E first = q.peek();
                     if (first == null)
                         available.await();
                     else {
                         long delay = first.getDelay(NANOSECONDS);
                         if (delay <= 0)
                             return q.poll();
                         first = null; // don't retain ref while waiting                     if (leader != null)
                             available.await();
                         else {
                             Thread thisThread = Thread.currentThread();
                             leader = thisThread;
                             try {
                                 available.awaitNanos(delay);
                             } finally {
                                 if (leader == thisThread)
                                     leader = null;
                             }
                         }
                     }
                 }
             } finally {
                 if (leader == null && q.peek() != null)
                     available.signal();
                 lock.unlock();
             }
         }
     }

     这个代码中有几个要点要注意一下。

     1. put()方法

     if (q.peek() == e) {
         leader = null;
         available.signal();
     }

     如果第一个元素等于刚刚插入进去的元素，说明刚才队列是空的。现在队列里有了一个任务，那么就应该唤醒所有在等待的消费者线程，避免了方案2的缺点。将leader重置为null，这些消费者之间互相竞争，自然有一个会被选为leader。

     2. 线程leader的作用

     leader这个成员有啥作用？DelayQueue的设计其实是一个Leader/Follower模式，leader就是指向Leader线程的。该模式可以减少不必要的等待时间，当一个线程是Leader时，它只需要一个时间差；其他Follower线程则无限等待。比如头节点任务还有5秒就要开始了，那么Leader线程会sleep 5秒，不需要傻傻地等待固定时间间隔。

     想象一下有个多个消费者线程用take方法去取任务,内部先加锁,然后每个线程都去peek头节点。如果leader不为空说明已经有线程在取了，让当前消费者无限等待。

     if (leader != null)
        available.await();

     如果为空说明没有其他消费者去取任务,设置leader为当前消费者，并让改消费者等待指定的时间，

     else {
         Thread thisThread = Thread.currentThread();
         leader = thisThread;
         try {
              available.awaitNanos(delay);
         } finally {
              if (leader == thisThread)
                  leader = null;
         }
     }

     下次循环会走如下分支，取到任务结束，

     if (delay <= 0)
         return q.poll();

     3. take()方法中为什么释放first

     first = null; // don't retain ref while waiting

     我们可以看到 Doug Lea 后面写的注释，那么这行代码有什么用呢？

     如果删除这行代码，会发生什么呢？假设现在有3个消费者线程，

     • 线程A进来获取first,然后进入 else 的 else ,设置了leader为当前线程A，并让A等待一段时间
     • 线程B进来获取first, 进入else的阻塞操作,然后无限期等待，这时线程B是持有first引用的
     • 线程A等待指定时间后被唤醒，获取对象成功，出队，这个对象理应被GC回收，但是它还被线程B持有着，GC链可达，所以不能回收这个first
     • 只要线程B无限期的睡眠，那么这个本该被回收的对象就不能被GC销毁掉，那么就会造成内存泄露

     Task对象

     import java.util.concurrent.Delayed; import java.util.concurrent.TimeUnit; public class Task implements Delayed {
         private String name;
         private long startTime;  // milliseconds     public Task(String name, long delay) {
             this.name = name;
             this.startTime = System.currentTimeMillis() + delay;
         }
     
         @Override     public long getDelay(TimeUnit unit) {
             long diff = startTime - System.currentTimeMillis();
             return unit.convert(diff, TimeUnit.MILLISECONDS);
         }
     
         @Override     public int compareTo(Delayed o) {
             return (int)(this.startTime - ((Task) o).startTime);
         }
     
         @Override     public String toString() {
             return "task " + name + " at " + startTime;
         }
     }

     JDK中有一个接口java.util.concurrent.Delayed，可以用于表示具有过期时间的元素，刚好可以拿来表示任务这个概念。

     生产者

     import java.util.Random; import java.util.UUID; public class TaskProducer implements Runnable {
         private final Random random = new Random();
         private DelayQueue<Task> q;
     
         public TaskProducer(DelayQueue<Task> q) {
             this.q = q;
         }
     
         @Override     public void run() {
             while (true) {
                 try {
                     int delay = random.nextInt(10000);
                     Task task = new Task(UUID.randomUUID().toString(), delay);
                     System.out.println("Put " + task);
                     q.put(task);
                     Thread.sleep(3000);
                 } catch (InterruptedException e) {
                     e.printStackTrace();
                 }
             }
         }
     }

     生产者很简单，就是一个死循环，不断地产生一些是时间随机的任务。

     消费者

     public class TaskConsumer implements Runnable {
         private DelayQueue<Task> q;
     
         public TaskConsumer(DelayQueue<Task> q) {
             this.q = q;
         }
     
         @Override     public void run() {
             while (true) {
                 try {
                     Task task = q.take();
                     System.out.println("Take " + task);
                 } catch (InterruptedException e) {
                     e.printStackTrace();
                 }
             }
         }
     }

     当 DelayQueue 里没有任务时，TaskConsumer会无限等待，直到被唤醒，因此它不会消耗CPU。

     定时任务调度器

     public class TaskScheduler {
         public static void main(String[] args) {
             DelayQueue<Task> queue = new DelayQueue<>();
             new Thread(new TaskProducer(queue), "Producer Thread").start();
             new Thread(new TaskConsumer(queue), "Consumer Thread").start();
         }
     }

     DelayQueue这个方案，每个消费者线程只需要等待所需要的时间差，因此响应速度更快。它内部用了一个优先队列，所以插入和删除的时间复杂度都是logn。

     JDK里还有一个ScheduledThreadPoolExecutor，原理跟DelayQueue类似，封装的更完善，平时工作中可以用它，不过面试中，还是拿DelayQueue来讲吧，它封装得比较薄，容易讲清楚原理。

     方案4: 时间轮(HashedWheelTimer)

     时间轮(HashedWheelTimer)其实很简单，就是一个循环队列，如下图所示，

     

     上图是一个长度为8的循环队列，假设该时间轮精度为秒，即每秒走一格，像手表那样，走完一圈就是8秒。每个格子指向一个任务集合，时间轮无限循环，每转到一个格子，就扫描该格子下面的所有任务，把时间到期的任务取出来执行。

     举个例子，假设指针当前正指向格子0，来了一个任务需要4秒后执行，那么这个任务就会放在格子4下面，如果来了一个任务需要20秒后执行怎么？由于这个循环队列转一圈只需要8秒，这个任务需要多转2圈，所以这个任务的位置虽然依旧在格子4(20%8+0=4)下面，不过需要多转2圈后才执行。因此每个任务需要有一个字段记录需圈数，每转一圈就减1，减到0则立刻取出来执行。

     怎么实现时间轮呢？Netty中已经有了一个时间轮的实现, HashedWheelTimer.java，可以参考它的源代码。

     时间轮的优点是性能高，插入和删除的时间复杂度都是O(1)。Linux 内核中的定时器采用的就是这个方案。

     Follow up: 如何设计一个分布式的定时任务调度器呢？ 答: Redis ZSet, RabbitMQ等

     最近一个小时内访问频率最高的10个IP

     实时输出最近一个小时内访问频率最高的10个IP，要求：

     • 实时输出
     • 从当前时间向前数的1个小时
     • QPS可能会达到10W/s

     这道题乍一看很像Top K 频繁项，是不是需要 Lossy Count 或 Count-Min Sketch 之类的算法呢？

     其实杀鸡焉用牛刀，这道题用不着上述算法，请听我仔细分析。

     1. QPS是 10万/秒，即一秒内最高有 10万个请求，那么一个小时内就有，向上取整，大概是个请求，也不是很大。我们在内存中建立3600个HashMap<Int,Int>，放在一个数组里，每秒对应一个HashMap，IP地址为key, 出现次数作为value。这样，一个小时内最多有个pair，每个pair占8字节，总内存大概是节，即4GB，单机完全可以存下。
     2. 同时还要新建一个固定大小为10的小根堆，用于存放当前出现次数最大的10个IP。堆顶是10个IP里频率最小的IP。
     3. 每次来一个请求，就把该秒对应的HashMap里对应的IP计数器增1，并查询该IP是否已经在堆中存在，
        • 如果不存在，则把该IP在3600个HashMap的计数器加起来，与堆顶IP的出现次数进行比较，如果大于堆顶元素，则替换掉堆顶元素，如果小于，则什么也不做
        • 如果已经存在，则把堆中该IP的计数器也增1，并调整堆
     4. 需要有一个后台常驻线程，每过一秒，把最旧的那个HashMap销毁，并为当前这一秒新建一个HashMap，这样维持一个一小时的窗口。
     5. 每次查询top 10的IP地址时，把堆里10个IP地址返回来即可。

     以上就是该方案的全部内容。

     有的人问，可不可以用"IP + 时间"作为key, 把所有pair放在单个HashMap里？如果把所有数据放在一个HashMap里，有两个巨大的缺点，

     • 第4步里，怎么淘汰掉一个小时前的pair呢？这时候后台线程只能每隔一秒，全量扫描这个HashMap里的所有pair,把过期数据删除，这是线性时间复杂度，很慢。
     • 这时候HashMap里的key存放的是"IP + 时间"组合成的字符串，占用内存远远大于一个int。而前面的方案，不用存真正的时间，只需要开一个3600长度的数组来表示一个小时时间窗口。