Uploaded image for project: 'Hadoop YARN'
  1. Hadoop YARN
  2. YARN-6592 [Umbrella] Rich placement constraints in YARN
  3. YARN-7783

Add validation step to ensure constraints are not violated due to order in which a request is processed

    XMLWordPrintableJSON

    Details

    • Type: Sub-task
    • Status: Resolved
    • Priority: Blocker
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 3.1.0
    • Component/s: None
    • Labels:
      None
    • Target Version/s:

      Description

      When the algorithm has placed a container on a node, allocation tags are added to the node if the constraint is satisfied, But depending on the order in which the algorithm sees the request, it is possible that a constraint that happen to be valid during placement of an earlier-seen request, might not be valid after all subsequent requests have been placed.

      For eg:
      Assume nodes n1, n2, n3, n4 and n5
      Consider the 2 constraints:

      1. foo -> anti-affinity with foo
      2. bar -> anti-affinity with foo

      And 2 requests

      1. req1: NumAllocations = 4, allocTags = [foo]
      2. req2: NumAllocations = 1, allocTags = [bar]

      If req1 is seen first, the algorithm can place the 4 containers in n1, n2, n3 and n4. And when it gets to req2, it will see that 4 nodes have the foo tag and will place it on n5. But if req2 is seen first, then bar tag will be placed on any node, since no node will at that point have foo, and then when it gets to req1, since foo has no anti-affinity with bar, the algorithm can end up placing foo on a node with bar violating the second constraint.

      To prevent the above, we need a validation step: after the placements for a batch of requests are made, then for each req, we remove its tags from the node and try to see of constraints are still satisfied if the tag were to be added back on the node.

      When applied to the example above, after the algorithm has run through req2 and then req1, we remove the bar tag from the node and try to add it back on the node. This time, constraint satisfaction will fail, since there is now a foo tag on the node and bar cannot be added. The algorithm will then retry placing req2 on another node.

        Attachments

        1. YARN-7783-YARN-6592.001.patch
          23 kB
          Arun Suresh
        2. YARN-7783-YARN-6592.002.patch
          39 kB
          Arun Suresh
        3. YARN-7783-YARN-6592.003.patch
          9 kB
          Arun Suresh
        4. YARN-7783-YARN-6592.004.patch
          11 kB
          Arun Suresh

          Activity

            People

            • Assignee:
              asuresh Arun Suresh
              Reporter:
              asuresh Arun Suresh
            • Votes:
              0 Vote for this issue
              Watchers:
              7 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved: