一个简单的算法，分布式系统的性能瞬间被提升10倍以上

作者：编程橙橙橙 2019-10-08 14:22:43

大数据

分布式

算法 这篇文章，给大家聊聊分布式文件系统HDFS在大量客户端并发写数据时，如何进行性能优化?先引入一个小的背景，假如多个客户端同时要并发的写Hadoop HDFS上的一个文件，这个事儿能成吗?

一、概要

这篇文章，给大家聊聊分布式文件系统HDFS在大量客户端并发写数据时，如何进行性能优化?

二、背景引入

先引入一个小的背景，假如多个客户端同时要并发的写Hadoop HDFS上的一个文件，这个事儿能成吗?

明显不可以接受啊，因为HDFS上的文件是不允许并发写的，比如并发的追加一些数据什么。

所以HDFS里有一个机制，叫做文件契约机制。

也就是说，同一时间只能有一个客户端获取NameNode上面一个文件的契约，然后才可以写入数据。

此时如果其他客户端尝试获取文件契约的时候，就获取不到，只能干等着。

通过这个机制，可以保证同一时间只有一个客户端在写一个文件。

在获取到了文件契约之后，在写文件的过程期间，那个客户端需要开启一个线程，不停的发送请求给NameNode进行文件续约，告诉NameNode：

• NameNode大哥，我还在写文件啊，你给我一直保留那个契约好吗?

而NameNode内部有一个专门的后台线程，负责监控各个契约的续约时间。

如果某个契约很长时间没续约了，此时就自动过期掉这个契约，让别的客户端来写。

说了这么多，老规矩，给大家来一张图，直观的感受一下整个过程。 

三、问题凸现

好，那么现在问题来了，假如我们有一个大规模部署的Hadoop集群，同时存在的客户端可能多达成千上万个。

此时NameNode内部维护的那个文件契约列表会非常非常的大，而监控契约的后台线程又需要频繁的每隔一段时间就检查一下所有的契约是否过期。

比如，每隔几秒钟就遍历大量的契约，那么势必造成性能不佳，所以说这种契约监控机制明显是不适合大规模部署的hadoop集群的。

四、优化方案

那么如何对文件契约监控算法进行优化的呢?

咱们来一步一步的看一下他的实现逻辑。首先，我们一起来看看下面这张手绘图： 

其实奥秘十分的简单，每次一个客户端发送续约请求之后，就设置这个契约的最近一次续约时间。

然后，基于一个TreeSet数据结构来根据最近一次续约时间对契约进行排序，每次都把续约时间最老的契约排在最前头，这个排序后的契约数据结构十分的重要。

TreeSet是一种可排序的数据结构，他底层基于TreeMap来实现。

TreeMap底层则基于红黑树来实现，可以保证元素没有重复，同时还能按照我们自己定义的排序规则在你每次插入一个元素的时候来进行自定义的排序。

所以这里我们的排序规则：就是按照契约的最近一次续约时间来排序。

其实这个优化就是如此的简单，就是维护这么一个排序数据结构而已。

我们现在来看一下Hadoop中的契约监控的源码实现： 

每次检查契约是否过期的时候，你不要遍历成千上万的契约，那样遍历效率当然会很低下。

我们完全可以就从TreeSet中获取续约时间最老的那个契约，假如说连最近一次续约时间最老的那个契约都还没过期，那么就不用继续检查了啊!这说明续约时间更近的那些契约绝对不会过期!

举个例子：续约时间最老的那个契约，最近一次续约的时间是10分钟以前，但是我们判断契约过期的限制是超过15分钟不续约就过期那个契约。

这个时候，连10分钟以前续约的契约都没有过期，那么那些8分钟以前，5分钟以前续约的契约，肯定也不会过期啊! 

这个机制的优化对性能的提升是相当有帮助的，因为正常来说，过期的契约肯定还是占少数，所以压根儿不用每次都遍历所有的契约来检查是否过期。

我们只需要检查续约时间最旧的那几个契约就可以了，如果一个契约过期了，那么就删掉那个契约，然后再检查第二旧的契约好了。以此类推。

通过这个TreeSet排序 + 优先检查最旧契约的机制，有效的将大规模集群下的契约监控机制的性能提升至少10倍以上，这种思想是非常值得我们学习和借鉴的。

给大家稍微引申一下，在Spring Cloud微服务架构中，Eureka作为注册中心其实也有续约检查的机制，跟Hadoop是类似的。

但是在Eureka中就没有实现类似的续约优化机制，而是暴力的每一轮都遍历所有的服务实例的续约时间。

如果你面对的是一个大规模部署的微服务系统呢，情况就不妙了!

部署了几十万台机器的大规模系统，有几十万个服务实例的续约信息驻留在Eureka的内存中，难道每隔几秒钟都要遍历几十万个服务实例的续约信息吗?

最后给大家提一句，优秀的开源项目，蕴含着很多优秀的设计思想。多看各种优秀开源项目的源码，是短时间内快速、大幅度提升一个人的技术功底和技术水平的方式，大家不妨尝试一下。