Uploaded image for project: '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
    • 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
    • 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-9
          70 kB
          Tomasz Nykiel
        2. hashStructures.patch-8
          70 kB
          Tomasz Nykiel
        3. hashStructures.patch-7
          69 kB
          Tomasz Nykiel
        4. hashStructures.patch-6
          69 kB
          Tomasz Nykiel
        5. hashStructures.patch-5
          69 kB
          Tomasz Nykiel
        6. hashStructures.patch-4
          69 kB
          Tomasz Nykiel
        7. hashStructures.patch-3
          69 kB
          Tomasz Nykiel
        8. hashStructures.patch-2
          69 kB
          Tomasz Nykiel
        9. hashStructures.patch
          69 kB
          Tomasz Nykiel



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


              • Created: