有没有好的算法来检测停止向服务器发送心跳的客户端？

Question

假设数百万个客户端在固定的时间间隔内向一台服务器发送心跳，则服务器判断该客户端停止发送心跳的时间超过该时间间隔失败。如果服务器只维护一个映射，并不断迭代每个客户端以检查客户端是否超时，这将产生O(n)复杂性，这对数百万客户端来说是可怕的。有没有像堆或二叉树一样的O(log(n))复杂度的算法来解决这样的问题？谢谢。

Answer 1

如果保留双向链表和hashmap，则可以使用hashmap查找与发送心跳的客户端相对应的列表条目。收到心跳后，解除列表条目的链接，并将其放在链接列表的末尾。

链表开头的条目是一个候选的“已死”客户端。链表可以被遍历到第一个活动的客户端。

一些注意事项：

1. Add a client:创建一个列表条目，将其添加到哈希图和链表的末尾。O(1)
2. 删除客户端:通过在哈希表中查找来查找客户端列表条目。解除客户端的链接。从哈希图中删除。O(1).
3. 处理心跳:通过在哈希图中查找来查找客户端列表条目。解除客户端列表条目的链接。将列表条目添加到链接列表的末尾。O(1)
4. 查找死客户端:查看链表的第一个条目。O(1)

Answer 2

方法1

为您提供O(log N)性能的最简单方法是使用优先级队列(堆)。在这个队列中，您为每个客户端保留一对<last-heartbeet-time, client-id>，其中last-heartbeet-time是您最后一次从该客户端接收心跳的协调世界时时间，并确保具有较小(较早) last-heartbeet-time的元素位于队列顶部。

每次客户端发送心跳时，您都会更改相应对中的值，从而将客户端移动到队列中较晚的位置。当您想要删除非活动客户端时，您只需从队列中提取数据，直到到达last-heartbeet-time超过阈值的客户端。

更新是每个心菜的O(log N) (有关详细信息，请参阅“索引优先级队列”下的here或here )，删除是每个已删除的客户端的O(log N)。请注意，这种方法不需要遍历所有客户端来查找那些应该删除的客户端。它只迭代那些实际被删除的对象。因此，如果您有N客户端、总共的M心跳请求和总共的K删除，那么这种方法将在O(M log N + K log N)时间内处理它们。

UPD：如果您的客户端具有不同的生存时间，即来自不同客户端的心菜具有不同的过期时间，则此解决方案也可以处理这种情况。您只需要存储expiration-time-of-last-heartbeet，而不是last-heartbeet-time。

UPD2：请看Ronald的答案，了解类似的想法，但不是使用堆并在每次迭代中实现O(1) -对于所有客户端都有相同的生存时间的情况，它比上面的更好(你不需要堆，因为每次你更新一些值，它都会移动到队列的末尾)。

方法2

另一种方法可以如下所示。为您收到的所有心菜保持一个普通队列(FIFO)，以及一个单独的数组，对于每个客户端，您可以在其中存储该客户端的多少个心菜已经在队列中。

每次新的心菜到达时，您都会将其推入队列，并为该客户端增加心菜的数量。

每次要删除非活动客户端时，都会开始从队列中弹出数据。您将按到达的顺序弹出心菜，从最旧的开始。每次弹出心菜时，都会减少数组中的相应值，并检查该值是否已变为零。如果If已变为零，则此客户端处于非活动状态。你会一直唱下去，直到你到了足够年轻的时候。

这看起来可能很慢，但请注意，每个心菜只弹出一次，因此pops的总数不会大于接收的心菜总数，因此此解决方案的总复杂性仅为O(M)！您无法拥有更快的解决方案，因为您需要处理所有传入的心菜，这已经是O(M)了，所以如果您的应用程序可以处理传入的心菜流量，那么它也应该能够处理此解决方案。

下面是此解决方案的伪代码

def receive_heartbeet(hb)
    q.push(hb)
    nActive[hb.client]++

def find_inactive
    while q.front().time < currentTime - threshold
        hb = q.pop()
        nActive[hb.client]--
        if nActive[hb.client] == 0
            mark hb.client as inactive

Answer 3

我建议的方法与@Petr建议的第一种方法略有不同。

您需要一个HashMap<client, FIFO<heartbeatDate>> clientHeartbeats和一个按heartbeatDate升序排序的Heap<heartbeatDate, client> heartbeats (第一个元素是最早的心跳)。

当客户端发送心跳时，将其插入到heartBeats (时间复杂度= O(log(n)))和clientHeartbeats (时间复杂度= O(1))中。

当heartbeats中的第一个心跳超出给定的时间间隔时，只需将其从堆中删除(时间复杂度= O(log(n)))，并从clientHeartbeats[removed heartbeat's client]中删除心跳(时间复杂度= O(1))。如果列表为空，则该特定客户端在指示的时间间隔内未发送心跳。

如果有什么不清楚的地方，请告诉我。