[algorithm][heap]基于小顶堆和hash map的虚拟机管理方法

前言： 集群中，存在大量的虚拟机。如何对大量的虚拟机进行高效的管理，也逐渐成为问题。 分析： 1，上报和拉取 逻辑层上，如果想获得虚拟机的信息，无非有两种方式获得到数据： a，虚拟机所在的物理机进行推送。一种情况下，虚拟机状态发生了变化，例如crash了，需要立刻通知逻辑层处理；还有一种情况就是周期性上报。 b，逻辑层上主动拉取。 对于正常的周期性上报监控数据的虚拟机，可以认为它是正常运行的。对于长时间没有上报数据的虚拟机，要么上宿主机出现了故障，要么就是虚拟机出现了故障。 如何发现哪些虚拟机有异常，对于时间的计算，就成为了一个基础问题。 2，小顶堆

如图，每个节点的数据结构是一个timestamp和uuid组成（占用内存很小），是一个基于timestamp排序的小顶堆。也就是说，堆顶的timestamp最小，也就是离当前时间最远的节点。如果有虚拟机的数据超时没有上报，那么会先出现在堆顶。例如超时时间是90s，堆顶的时间只有50s，那么可以判断出来，其他的虚拟机的上报时间都在50s之内（包括50s）。 用一个线程或者协程，周期性的扫描堆顶，就足够找到超时没有上报的虚拟机了。对于超时的虚拟机，可以主动拉取信息，拉取失败意味着可能需要HA处理，拉取成功则可以更新当前节点的timestamp，再调整堆。 heap完成了timestamp到uuid的关系映射，通过timestamp找到uuid，计算量可以做到最小化。 3，hash map 如果上报了虚拟机的信息，同样需要更新对应的节点和调整小顶堆，需要使用uuid找到对应的节点。需要有uuid到堆的节点的映射。 所以，可以使用hash map来保存。例如声明类似结构UUIDHashMap[uuid]*heapItem，其中uuid是string类型，是虚拟机的uuid；heapItem是上文中堆节点的指针。 由此完成了从uuid到timestamp的关系映射，通过uuid可以找到节点更新堆。时间复杂度是O（1）。 4，mutex 上文中，有两条路径可以修改到堆中的节点。其一是协程周期性扫描堆顶，其二是从hash map中找到节点操作。所以需要在关键位置加锁保护临界资源。