Uploaded image for project: 'Hadoop Common'
  1. Hadoop Common
  2. HADOOP-5638

More improvement on block placement performance

    XMLWordPrintableJSON

Details

    • Improvement
    • Status: Closed
    • Major
    • Resolution: Fixed
    • None
    • 0.21.0
    • None
    • None
    • Reviewed

    Description

      Block placement algorithm currently has an excluded node list, which contains all datanodes that have been visited. This list is implemented as an array list, whose cost of inserting is O(1) but the cost of query "contains" is O( n ), where n is the number of datanodes. This makes the cost of block placement to be O(n*n) when a cluster is full.

      I propose to change the data structure of the excluded node list as a HashMap. So in average, the cost of insertion is O(1) and the cost of query is O(1). This makes the block placement algorithm to be O( n ) in average.

      Attachments

        1. excludedList.patch
          10 kB
          Hairong Kuang
        2. excludedList1.patch
          12 kB
          Hairong Kuang
        3. excludedList2.patch
          13 kB
          Hairong Kuang
        4. excludedList3.patch
          12 kB
          Hairong Kuang
        5. excludedList4.patch
          15 kB
          Hairong Kuang

        Issue Links

          is related to

          Improvement - An improvement or enhancement to an existing feature or task. HADOOP-5603 Improve block placement performance

          • Major - Major loss of function.
          • Closed

          Activity

            People

              hairong Hairong Kuang
              hairong Hairong Kuang
              Votes:
              0 Vote for this issue
              Watchers:
              2 Start watching this issue

              Dates

                Created:
                Updated:
                Resolved: