和下線主要有關的代碼集中在blockmanager,以及UnderReplicatedBlocks

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被取到，所以還是要有序的。

實際上，這么做是合理的，先進入隊列可以優先被取到。但對于我們這種場景，并不要求取出的順序性和放入順序一致。如果能打亂順序，再取出就能使一次迭代取出的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

private final List> priorityQueues
= new ArrayList>();public static final String NAMENODE_BLOCKMANAGEMENT_QUEUES_SHUFFLE =    "dfs.namenode.blockmanagement.queues.shuffle";private Map priorityToReplIdx = new HashMap(LEVEL);new HdfsConfiguration(); boolean useShuffle = conf.getBoolean(NAMENODE_BLOCKMANAGEMENT_QUEUES_SHUFFLE, false); for (int i = 0; i < LEVEL; i++) {    if (useShuffle) {
     priorityQueues.add(new ShuffleAddSet());
} else {
     priorityQueues.add(new LightWeightLinkedSet());
}
   priorityToReplIdx.put(i, 0);
}
}

我們發現使用ShuffleAddSet時候，開始下線8臺dn時會卡住，主要是卡在DecommissionManager$Monitor，每次要檢查此dn上全部的blocks是否 underReplicated,這樣blocks很多拿寫鎖的時間會很長。

也會檢查ShuffleAddSet.contains(blocks),由于有兩個隊列，所以contain開銷會比之前大。

2019-04-12,12:09:35,876 INFO org.apache.hadoop.hdfs.server.namenode.FSNamesystem: Long read lock is held at 1555042175235. And released after 641 milliseconds.Call stack is:
java.lang.Thread.getStackTrace(Thread.java:1479)
org.apache.hadoop.util.StringUtils.getStackTrace(StringUtils.java:914)
org.apache.hadoop.hdfs.server.namenode.FSNamesystemLock.checkAndLogLongReadLockDuration(FSNamesystemLock.java:104)
org.apache.hadoop.hdfs.server.namenode.FSNamesystem.writeUnlock(FSNamesystem.java:1492)
org.apache.hadoop.hdfs.server.blockmanagement.BlockManager.isReplicationInProgress(BlockManager.java:3322)
org.apache.hadoop.hdfs.server.blockmanagement.DatanodeManager.checkDecommissionState(DatanodeManager.java:751)
org.apache.hadoop.hdfs.server.blockmanagement.DecommissionManager$Monitor.check(DecommissionManager.java:93)
org.apache.hadoop.hdfs.server.blockmanagement.DecommissionManager$Monitor.run(DecommissionManager.java:70)
java.lang.Thread.run(Thread.java:662)

通過修改isReplicationInProgress方法，類似處理blockreport,每隔一定數量放一次鎖的方式，緩解寫鎖時間太長導致其他rpc請求沒有響應。

++processed;// Release lock per 5w blocks processed and has too many underReplicatedBlocks.if (processed == numReportBlocksPerIteration &&
   namesystem.hasWriteLock() && underReplicatedBlocks > numReportBlocksPerIteration) {
 namesystem.writeUnlock();
processed = 0;
namesystem.writeLock();
}

對于單副本較多的集群，可采用如下方式下線：

dfs.namenode.blockmanagement.queues.shuffle= truedfs.namenode.replication.max-streams= 12 默認是2，限制一個datanode復制數量
dfs.namenode.replication.max-streams-hard-limit=12 默認是4dfs.namenode.replication.work.multiplier.per.iteration= 4 默認2 / namenode一次調度的數量=該值×datanodes數量

開啟shuffle and add,并調整單個dn最大復制數為物理磁盤數量，對于小集群可以調大work.multiplier一次處理4倍LiveDatanode數量block.使下線速度最大化。

注意的問題：

每次操作下線2臺節點（refreshNodes），隔10分鐘再下2臺，一直到8臺。同時下線的dn最好不要超過8臺。不然DecommissionManager的開銷會很大，影響NN正常服務。