Hadoop HDFS
  1. Hadoop HDFS
  2. HDFS-2362 More Improvements on NameNode Scalability
  3. HDFS-2476

More CPU efficient data structure for under-replicated/over-replicated/invalidate blocks


    • Type: Sub-task Sub-task
    • Status: Closed
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: 0.23.0
    • Fix Version/s: 2.0.0-alpha, 0.23.7
    • Component/s: namenode
    • Labels:
    • Target Version/s:
    • Hadoop Flags:


      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.

      1. hashStructures.patch
        69 kB
        Tomasz Nykiel
      2. hashStructures.patch-2
        69 kB
        Tomasz Nykiel
      3. hashStructures.patch-3
        69 kB
        Tomasz Nykiel
      4. hashStructures.patch-4
        69 kB
        Tomasz Nykiel
      5. hashStructures.patch-5
        69 kB
        Tomasz Nykiel
      6. hashStructures.patch-6
        69 kB
        Tomasz Nykiel
      7. hashStructures.patch-7
        69 kB
        Tomasz Nykiel
      8. hashStructures.patch-8
        70 kB
        Tomasz Nykiel
      9. hashStructures.patch-9
        70 kB
        Tomasz Nykiel


        No work has yet been logged on this issue.


          • Assignee:
            Tomasz Nykiel
            Tomasz Nykiel
          • Votes:
            0 Vote for this issue
            9 Start watching this issue


            • Created: