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

More improvement on block placement performance

Log workAgile BoardRank to TopRank to BottomAttach filesAttach ScreenshotBulk Copy AttachmentsBulk Move AttachmentsVotersWatch issueWatchersCreate sub-taskConvert to sub-taskMoveLinkCloneLabelsUpdate Comment AuthorReplace String in CommentUpdate Comment VisibilityDelete Comments
    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
          This comment will be Viewable by All Users Viewable by All Users
          Cancel

          People

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

            Dates

              Created:
              Updated:
              Resolved:

              Slack

                Issue deployment