[toc]
笔记来源：
实战：单机如何实现管理百万主机的心跳服务
基于LRU实现百万级别的心跳监控服务#
1. Q: 百万级别节点，如何快速找到离线的节点？（非数据库存储模式）#
全部遍历找超时，O(n)， 百万级别节点消耗非常大， 遍历时可能会因为涉及更新的同步问题， 导致此时无法插入。
如果用单线程，这个过程慢的话会造成阻塞。
实现方式1： LRU+链表+哈希表
① 所有心跳放进一个LRU队列中，保证最新的心跳包在队尾，最老的心跳包在队头。
② 如果某节点有新的心跳包进来， 利用哈希表找到这个节点的链点位置，删除掉，再将新包插入到队尾。
③ 每次心跳检查时， 只要查询队头， 不断将超时的心跳包出队，直到队头的心跳包不超时即可。
实现方式2： 时间轮，时间轮的做法见最后
2. Q: 如何保证心跳服务的可靠性？#
上面提到的心跳检查都在内存中， 心跳检查节点如果只有1个的话不可靠，而且量级也会很大。
但又不能落盘，这会导致数据库的并发查询压力很大，且数据库自身的可靠性又会成了问题。
解决方式：
分布式处理。
心跳入口网关 根据节点的ip或者节点id做哈希， 确保相同节点的心跳包发往同一个节点。
如果网关发现某个节点挂了，利用哈希一致算法更新发送的节点即可。
3. Q: 如何提升单个心跳服务节点的心跳接收性能？#
收到心跳后， 涉及心跳的解包，LRU+哈希更新，需要提升处理性能。
① 多线程处理， 同样利用上面的方法做哈希，分配到特定的心跳处理线程，不同线程之间处理的节点信息不会互相干扰。
注意点： 缓存队列放到各自的工作线程中。 即push而非pull的方式，尽可能避免N之间的竞争，即只做1+1的竞争。
队列锁采用自旋锁，避免工作线程频繁出现上下文切换（即保证工作线程一直在跑，这个用于高并发场景，高并发场景不能让他停下来的）
② 心跳包资源池减少内存释放频率
如果只有10w个节点，那么每次收到心跳请求时，不要反复new新的心跳对象，而是从心跳资源池里取出构造好的对象，把最新时间set进去后再扔给分发线程。
4. 心跳包选用TCP还是UDP？#
满足以下条件的话选择UDP:
- 心跳包报文长度内容信息量很少，基本小于MTU， 不需要利用TCP自带的分包机制。
- 超时判断时间允许偶然一次的不可靠丢包（即偶尔丢一次并不影响）
这种情况用UDP在网内发到心跳服务即可。
不需要TCP那样的高消耗。
另一个方式：时间轮#
时间轮本质：
- 弄一个数组（看起来是一个环，实际上是数组）
- 数组中中每个节点又存了一个双向链表，用于存放实际的任务（用链表是为了方便插入）
- 任务具体放数组中的哪个位置？ 根据 超期时间取余决定他的实际存放位置。
- 如果数组的节点中有任务，会把本身的超期时间带着一起扔进一个 队列中
- 队列每次取队头数据， 如果时间没到队头节点指定的延迟时间，就阻塞，直到时间到达，取出里面的任务逐个执行。
- 如果任务的定时时间超过整个环的时间？ 则新增一个时间轮，时间比这个更长，因此队列里可能会多插入一个节点，节点中会标识我是小时间轮还是大时间轮的。
其他的延时队列怎么做的?
延时队列实现的几种姿势
Q: java的DelayQueue类原理知道吗？#
A:
- 有一个优先队列， 放入的任务会根据是否快要超期进行排序， 马上就要超期的会放在队头。
- 当使用take方法取数据时，看一下队头任务，如果时间到了就返回。
- 如果时间还没到
- 首先看一下是否已经有线程在等待这个任务了，如果是的话，使用锁的condition机制做await等待。
- 如果没有线程正在等待，就计算还差多少时间， 然后用 LockSupport.parkNanos()让这个调用take方法的线程等待特定时间。
- 注意等待期间，会释放锁，因此这期间可以正常offer和take。
- 当时间到了后，这个线程肯定能取走数据了。 取完后，顺便看一下队列里还有没有数据，如果有， 调用condition.signal()，通知那堆正在等待的线程， 你们可以试着竞争一下取数据了。
- 另外每当有新的任务offer时，如果发现最新入队的数据就是马上要超期的数据， 也会立刻通知等待的各位马上苏醒竞争（因为之前等待的线程认为自己还要睡一会才会有数据）
Q: 时间轮和 java的delayQueue）有什么区别？#
A:
java的delayQueue本质上是用堆（优先队列）实现的。
接收任务后， 直接把任务放进优先队列中， 按照超期时间确定堆位置。 每次poll时如果发现堆顶没到时间就阻塞，直到时间到了再poll。
取出来检查后，再加上时间扔回队列。
坏处： 插入和删除的复杂度是O(logn)。
而时间轮并不会把任务扔进 queue中，而是把时间轮的槽扔进queue中。 因此整个延迟队列实际上时针对槽的，不需要堆，按先入先出取数据和插槽即可，O(1)的复杂度。 而后面扔进来的任务，都是往槽里的双向链表塞进去而已。