HDFS解析 | HDFS Decommission问题分析

//

分析数据结构

//

和下线主要有关的代码集中在blockmanager,以及UnderReplicatedBlocks

/**
 * Store set of Blocks that need to be replicated 1 or more times.
 * We also store pending replication-orders.
 */public final UnderReplicatedBlocks neededReplications = new UnderReplicatedBlocks();

所有需要做replicate的block都会放在blockmanager.neededReplications中。

UnderReplicatedBlocks是一个复合结构，保存者5个(LEVEL=5)带有优先级的队列：

private final List> priorityQueues

对于只有一个副本的block，或者replica都在decommision节点上，它在优先级最高的队列中，raid副本下线就是这种情况。

对于每一个优先级的队列，实现是LightWeightLinkedSet，它是一个有序的hashset,元素收尾相连。

UnderReplicatedBlocks的实现是保证每个队列的元素都会被取到，同时，每个队列中的元素按顺序依次被取出，不会让某些block永远没机会被取出。

具体做法是为每一个队列保存一个偏移：

private finalList> priorityQueues

如果取到最后一个队列(LEVEL-1)末尾了，就重置所有队列的偏移=0，从头再取。

这5个队列都是先进先被选，队尾进，而且优先级Level=0的更容易被取到。具体取的算法是在UnderReplicatedBlocks.chooseUnderReplicatedBlocks()中。

在进行decommission操作的时候，可能整个dn的块都是要加入neededReplication队列(raid集群如此，如果有3副本，那一个block有3个source.单副本的source dn只有一个)。这时候，加入某一个优先级队列(LightWeightLinkedSet)的blocks是有序的，而且连续上w个blocks属于同一个dn，甚至连续在同一个磁盘上。由于从队列是从头到尾顺序取，所以会有问题，尤其是对单副本的情况。

因此，我们想要随机从优先级队列中取出block.但又要保证每个block被取到，所以还是要有序的。

//

数据结构改造-ShuffleAddSet

//

实际上，这么做是合理的，先进入队列可以优先被取到。但对于我们这种场景，并不要求取出的顺序性和放入顺序一致。如果能打乱顺序，再取出就能使一次迭代取出的blocks尽可能在不同dn或者不同磁盘上。

LightWeightLinkedSet： UnderReplicatedBlocks默认采用的优先级队列的实现。本身是一个hashset继承LightWeightHashSet，同时元素双向连接，带有Head tail

LightWeightHashSet： 轻量级hashSet

ShuffleAddSet： Look like LightWeightLinkedSet

我们实现了一种ShuffleAddSet继承LightWeightHashSet，尽可能表现和LightWeightLinkedSet一致，这样对外UnderReplicatedBlocks不需要做过多修改。

ShuffleAddSet中有两个队列，而对外表现为一个优先级队列。

第一个队列， 同时也是Set和LightWeightLinkedSet是一样的，双向有序，外部调用方法取元素也是从这个Set取。

第二个队列， 缓存队列cachedAddList，一开始用ArrayList、LinkedList,由于性能问题不使用了。现在也是用LightWeightHashSet，HashSet具有天然无序性质。

每当有新的元素加入，首先会放入cachedAddList中，随后当第一个队列数据空或者取到末尾，立即将cachedAddList数据shuffle,并拷贝到第一个队列中，然后清空自己，继续接收新元素。由于HashSet本身无序，因此少一步shuffle操作，直接从cachedAddList拷贝至第一个队列即可。

需要注意的是取数据(调用迭代器取)和add操作必须是同步的，因为取的时候第一个队列到达末尾或着空，会触发shuffle and add操作，清空cachedlist。

综上，第一个队列只有为空或者取到末尾的时候，会从第二个队里加入数据，如果都为空说明整个优先级队列空。每从cachedlist加入一批，这一批就是随机顺序，虽然第一个队列不是整个队列都随机打乱，总体上，第一个队列还是是乱序的。

这样做的问题：

(1)外部调用这个优先级队列的add操作，先进入队列的不一定是先被调度，后加入cachedList的元素，也可能排在第一个队列的前面先调度。

(2)极端情况，如果每次加入1个，然后再取1个元素，少量的元素，或者取出数量和频率远大于add数量，(比如cachedlist加入一个元素，第一个队列立刻到达末尾了)实际上没有达到随机效果。

好在我们的场景不要求FIFO,而且每次Decommision初始加入UnderReplicatedBlocks的block数量很大，ReplicationMonitor每次取/处理的数量blockToProcess，相对而言(下线8台节点，UnderReplicatedBlocks会达到180w)较小。发生shuffle and add不是很频繁，也不是性能瓶颈。观测到最长时间是200ms。

同时，我们将这个功能ShuffleAddSet作为一种可配置项目，UnderReplicatedBlocks可以在初始化时候选择用ShuffleAddSet或者LightWeightLinkedSet

dfs.namenode.blockmanagement.queues.shuffle