[HDFS-2476] More CPU efficient data structure for under-replicated/over-replicated/invalidate blocks

• Type: Sub-task
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Affects Version/s: 0.23.0
• Fix Version/s: 2.0.0-alpha, 0.23.7
• Component/s: namenode
• Target Version/s: 0.23.3
• Hadoop Flags: Reviewed
• Assignee: Tomasz Nykiel
• Reporter: Tomasz Nykiel
• Created: 20/Oct/11 02:40
• Updated: 28/Sep/15 20:58
• Resolved: 15/Nov/11 01:14

Description

This patch introduces two hash data structures for storing under-replicated, over-replicated and invalidated blocks.

1. LightWeightHashSet
2. LightWeightLinkedSet

Currently in all these cases we are using java.util.TreeSet which adds unnecessary overhead.

The main bottlenecks addressed by this patch are:
-cluster instability times, when these queues (especially under-replicated) tend to grow quite drastically,
-initial cluster startup, when the queues are initialized, after leaving safemode,
-block reports,
-explicit acks for block addition and deletion

1. The introduced structures are CPU-optimized.
2. They shrink and expand according to current capacity.
3. Add/contains/delete ops are performed in O(1) time (unlike current log n for TreeSet).
4. The sets are equipped with fast access methods for polling a number of elements (get+remove), which are used for handling the queues.