hadoop集群在管理大量文件契约过期时用到的算法

缘起

javaweb实习过一段时间. 最大的感触就是

这个领域它喵的不需要啥高深算法~

用的最多的算法就是for遍历, 最难也就是写个最简单最简单他喵的连剪枝都不需要的递归. 别跟我扯什么链表、数组、哈希表、红黑树，那他喵的都是别人写好让你们这些API调用工程师调用的，和你们没毛关系.

但是真是没什么tricky的东西吗? 那倒不是, 至少今天我听说到了Hadoop集群管理文件契约过期问题用的就是比较tricky的主意.

分析

背景是这样的. Hadoop是java写就的比较复杂的平台性的框架. 它管理着很多资源——例如文件句柄. Hadoop不允许并发写文件. 所以某个Hadoop客户端要写Hadoop集群管理的文件的话, 就必须获取该文件的某种锁. 这里叫文件契约. 获取到某份文件的文件契约的客户端就能操作该文件, 否则就只能干等着.而且因为客户端对文件的操作会比较耗时, 所以客户端在操作该文件的时候，会另外安排一个后台线程不断的发送续约该文件契约的请求到Hadoop平台，告诉Hadoop平台: “嘿~ 大哥, 我还在写哈, 这份文件我还在操作, 文件契约给我留着哈, 别让给别的客户端.” 那么Hadoop平台怎么知道一个客户端不再操作某份文件了呢? 一种情况是客户端操作完毕主动发送请求告知Hadoop平台说我写完了, 你可以将此文件契约转让给别的客户端了. 另一种情况可能因为某种网络缘故,客户端迟迟没有发送主动结束契约的请求. 但是 Hadoop总不能一直帮他保持这份文件契约不让其他客户端来操作这份文件呀~ 那岂不是出岔子了? 所以Hadoop针对过期的文件契约就主动回收掉了.

上述过程其实和网络中的DHCP协议非常相似. 也就是说, 本文讲述的内容其实并不仅仅是针对Hadoop. 对于任何互斥型资源池对资源的回收管理都是适用的. 例如eureka的服务发现实例. zk对于服务的监控、最普遍的缓存过期策略等等等等.

我们继续用Hadoop为例来说事情. 如果一个Hadoop集群管理了上万文件契约的话, 一个无可避免的情况就是必须要启动一个后台线程每秒钟扫描这上万个契约来看看这些契约有没有过期? 这是一件非常耗时的工作!!!

那怎么办呢? 实际中，过期的文件契约占比其实是非常少的. 我们只需要将所有文件契约按照过期时间倒叙排序, 即即将过期的排在前面. 换言之, 过期时间最早的文件契约排在最前面. Hadoop只需要维护一个这样的数据结构（未必是线性表, 可以是树）即可. 以链表为例, 头部就是最早马上要过期的. 如果头部都没过期的话, 则后面就不需要考察了. 因为实际上过期的文件契约并不多. 而每次客户端发送请求过来，就要维护这个链表（选择链表就是为了防止插入节点的话, 大量移动元素导致效率低下）