You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@flink.apache.org by tillrohrmann <gi...@git.apache.org> on 2017/11/27 17:54:57 UTC

[GitHub] flink pull request #5091: [FLINK-7956] [flip6] Add support for queued schedu...

GitHub user tillrohrmann opened a pull request:

    https://github.com/apache/flink/pull/5091

    [FLINK-7956] [flip6] Add support for queued scheduling with slot sharing to SlotPool

    ## What is the purpose of the change
    
    This commit adds support for queued scheduling with slot sharing to the
    SlotPool. The idea of slot sharing is that multiple tasks can run in the
    same slot. Moreover, queued scheduling means that a slot request must not
    be completed right away but at a later point in time. This allows to
    start new TaskExecutors in case that there are no more slots left.
    
    The main component responsible for the management of shared slots is the
    SlotSharingManager. The SlotSharingManager maintains internally a tree-like
    structure which stores the SlotContext future of the underlying
    AllocatedSlot. Whenever this future is completed potentially pending
    LogicalSlot instantiations are executed and sent to the slot requester.
    
    A shared slot is represented by a MultiTaskSlot which can harbour multiple
    TaskSlots. A TaskSlot can either be a MultiTaskSlot or a SingleTaskSlot.
    
    In order to represent co-location constraints, we first obtain a root
    MultiTaskSlot and then allocate a nested MultiTaskSlot in which the
    co-located tasks are allocated. The corresponding SlotRequestID is assigned
    to the CoLocationConstraint in order to make the TaskSlot retrievable for
    other tasks assigned to the same CoLocationConstraint.
    
    This PR also moves the `SlotPool` components to `o.a.f.runtime.jobmaster.slotpool`.
    
    This PR is based on #5090 
    
    ## Brief change log
    
    - Add `SlotSharingManager` to manage shared slots
    - Rework `SlotPool` to use `SlotSharingManager`
    - Add `SlotPool#allocateMultiTaskSlot` to allocate a shared slot
    - Add `SlotPool#allocateCoLocatedMultiTaskSlot` to allocate a co-located slot
    - Move `SlotPool` components to `o.a.f.runtime.jobmaster.slotpool`
    
    ## Verifying this change
    
    - Port `SchedulerSlotSharingTest`, `SchedulerIsolatedTasksTest` and
    `ScheduleWithCoLocationHintTest` to run with `SlotPool`
    - Add `SlotSharingManagerTest`, `SlotPoolSlotSharingTest` and
    `SlotPoolCoLocationTest` 
    
    ## Does this pull request potentially affect one of the following parts:
    
      - Dependencies (does it add or upgrade a dependency): (no)
      - The public API, i.e., is any changed class annotated with `@Public(Evolving)`: (no)
      - The serializers: (no)
      - The runtime per-record code paths (performance sensitive): (no)
      - Anything that affects deployment or recovery: JobManager (and its components), Checkpointing, Yarn/Mesos, ZooKeeper: (yes)
      - The S3 file system connector: (no)
    
    ## Documentation
    
      - Does this pull request introduce a new feature? (no)
      - If yes, how is the feature documented? (not applicable)
    
    CC: @GJL 

You can merge this pull request into a Git repository by running:

    $ git pull https://github.com/tillrohrmann/flink slotPoolSlots

Alternatively you can review and apply these changes as the patch at:

    https://github.com/apache/flink/pull/5091.patch

To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:

    This closes #5091
    
----
commit d30dde83548dbeff4249f3b57b67cdb6247af510
Author: Till Rohrmann <tr...@apache.org>
Date:   2017-11-14T22:50:52Z

    [FLINK-8078] Introduce LogicalSlot interface
    
    The LogicalSlot interface decouples the task deployment from the actual
    slot implementation which at the moment is Slot, SimpleSlot and SharedSlot.
    This is a helpful step to introduce a different slot implementation for
    Flip-6.

commit e5da9566a6fc8a36ac8b06bae911c0dff5554e5d
Author: Till Rohrmann <tr...@apache.org>
Date:   2017-11-15T13:20:27Z

    [FLINK-8085] Thin out LogicalSlot interface
    
    Remove isCanceled, isReleased method and decouple logical slot from Execution by
    introducing a Payload interface which is set for a LogicalSlot. The Payload interface
    is implemented by the Execution and allows to fail an implementation and obtaining
    a termination future.
    
    Introduce proper Execution#releaseFuture which is completed once the Execution's
    assigned resource has been released.

commit 84d86bebe2f9f8395430e7c71dd2393ba117b44f
Author: Till Rohrmann <tr...@apache.org>
Date:   2017-11-24T17:03:49Z

    [FLINK-8087] Decouple Slot from AllocatedSlot
    
    This commit introduces the SlotContext which is an abstraction for the SimpleSlot
    to obtain the relevant slot information to do the communication with the
    TaskManager without relying on the AllocatedSlot which is now only used by the
    SlotPool.

commit 80a3cc848a0c724a2bc09b1b967cc9e6ccec5942
Author: Till Rohrmann <tr...@apache.org>
Date:   2017-11-24T17:06:10Z

    [FLINK-8088] Associate logical slots with the slot request id
    
    Before logical slots like the SimpleSlot and SharedSlot where associated to the
    actually allocated slot via the AllocationID. This, however, was sub-optimal because
    allocated slots can be re-used to fulfill also other slot requests (logical slots).
    Therefore, we should bind the logical slots to the right id with the right lifecycle
    which is the slot request id.

commit 3e4550c0607744b20893dc90c587b63e68e4de1e
Author: Till Rohrmann <tr...@apache.org>
Date:   2017-11-13T14:42:07Z

    [FLINK-8089] Also check for other pending slot requests in offerSlot
    
    Not only check for a slot request with the right allocation id but also check
    whether we can fulfill other pending slot requests with an unclaimed offered
    slot before adding it to the list of available slots.

commit b04dda46aaf298d921929910574662970d9c5093
Author: Till Rohrmann <tr...@apache.org>
Date:   2017-11-24T22:29:53Z

    [hotfix] Speed up RecoveryITCase

commit e512558917f9bb5005024630b8a015cd624164b4
Author: Till Rohrmann <tr...@apache.org>
Date:   2017-11-24T17:08:38Z

    [FLINK-7956] [flip6] Add support for queued scheduling with slot sharing to SlotPool
    
    This commit adds support for queued scheduling with slot sharing to the
    SlotPool. The idea of slot sharing is that multiple tasks can run in the
    same slot. Moreover, queued scheduling means that a slot request must not
    be completed right away but at a later point in time. This allows to
    start new TaskExecutors in case that there are no more slots left.
    
    The main component responsible for the management of shared slots is the
    SlotSharingManager. The SlotSharingManager maintains internally a tree-like
    structure which stores the SlotContext future of the underlying
    AllocatedSlot. Whenever this future is completed potentially pending
    LogicalSlot instantiations are executed and sent to the slot requester.
    
    A shared slot is represented by a MultiTaskSlot which can harbour multiple
    TaskSlots. A TaskSlot can either be a MultiTaskSlot or a SingleTaskSlot.
    
    In order to represent co-location constraints, we first obtain a root
    MultiTaskSlot and then allocate a nested MultiTaskSlot in which the
    co-located tasks are allocated. The corresponding SlotRequestID is assigned
    to the CoLocationConstraint in order to make the TaskSlot retrievable for
    other tasks assigned to the same CoLocationConstraint.
    
    Port SchedulerSlotSharingTest, SchedulerIsolatedTasksTest and
    ScheduleWithCoLocationHintTest to run with SlotPool.
    
    Restructure SlotPool components.
    
    Add SlotSharingManagerTest, SlotPoolSlotSharingTest and
    SlotPoolCoLocationTest.

commit 6489c6769a40b70f49b827784c810f954c413361
Author: Till Rohrmann <tr...@apache.org>
Date:   2017-11-27T08:29:54Z

    [hotfix] [tests] Speed up queryable state IT tests by removing sleep

----


---

[GitHub] flink pull request #5091: [FLINK-7956] [flip6] Add support for queued schedu...

Posted by tillrohrmann <gi...@git.apache.org>.
Github user tillrohrmann commented on a diff in the pull request:

    https://github.com/apache/flink/pull/5091#discussion_r156891235
  
    --- Diff: flink-runtime/src/main/java/org/apache/flink/runtime/jobmaster/slotpool/SlotPool.java ---
    @@ -266,104 +279,367 @@ public void disconnectResourceManager() {
     	// ------------------------------------------------------------------------
     
     	@Override
    -	public CompletableFuture<SimpleSlot> allocateSlot(
    -			SlotRequestID requestId,
    -			ScheduledUnit task,
    -			ResourceProfile resources,
    -			Iterable<TaskManagerLocation> locationPreferences,
    +	public CompletableFuture<LogicalSlot> allocateSlot(
    +			SlotRequestId slotRequestId,
    +			ScheduledUnit scheduledUnit,
    +			ResourceProfile resourceProfile,
    +			Collection<TaskManagerLocation> locationPreferences,
    +			boolean allowQueuedScheduling,
     			Time timeout) {
     
    -		return internalAllocateSlot(requestId, task, resources, locationPreferences);
    +		return internalAllocateSlot(
    +			slotRequestId,
    +			scheduledUnit,
    +			resourceProfile,
    +			locationPreferences,
    +			allowQueuedScheduling);
     	}
     
    -	@Override
    -	public void returnAllocatedSlot(Slot slot) {
    -		internalReturnAllocatedSlot(slot);
    +	private CompletableFuture<LogicalSlot> internalAllocateSlot(
    +			SlotRequestId slotRequestId,
    +			ScheduledUnit task,
    +			ResourceProfile resourceProfile,
    +			Collection<TaskManagerLocation> locationPreferences,
    +			boolean allowQueuedScheduling) {
    +
    +		final SlotSharingGroupId slotSharingGroupId = task.getSlotSharingGroupId();
    +
    +		if (slotSharingGroupId != null) {
    +			// allocate slot with slot sharing
    +			final SlotSharingManager multiTaskSlotManager = slotSharingManagers.computeIfAbsent(
    +				slotSharingGroupId,
    +				id -> new SlotSharingManager(
    +					id,
    +					this,
    +					providerAndOwner));
    +
    +			final SlotSharingManager.MultiTaskSlotLocality multiTaskSlotFuture;
    +
    +			try {
    +				if (task.getCoLocationConstraint() != null) {
    +					multiTaskSlotFuture = allocateCoLocatedMultiTaskSlot(
    +						task.getCoLocationConstraint(),
    +						multiTaskSlotManager,
    +						resourceProfile,
    +						locationPreferences,
    +						allowQueuedScheduling);
    +				} else {
    +					multiTaskSlotFuture = allocateMultiTaskSlot(
    +						task.getJobVertexId(), multiTaskSlotManager,
    +						resourceProfile,
    +						locationPreferences,
    +						allowQueuedScheduling);
    +				}
    +			} catch (NoResourceAvailableException noResourceException) {
    +				return FutureUtils.completedExceptionally(noResourceException);
    +			}
    +
    +			// sanity check
    +			Preconditions.checkState(!multiTaskSlotFuture.getMultiTaskSlot().contains(task.getJobVertexId()));
    +
    +			final SlotSharingManager.SingleTaskSlot leave = multiTaskSlotFuture.getMultiTaskSlot().allocateSingleTaskSlot(
    --- End diff --
    
    jup, we wouldn't want the single task slot to leave after all.


---

[GitHub] flink pull request #5091: [FLINK-7956] [flip6] Add support for queued schedu...

Posted by GJL <gi...@git.apache.org>.
Github user GJL commented on a diff in the pull request:

    https://github.com/apache/flink/pull/5091#discussion_r155605251
  
    --- Diff: flink-runtime/src/main/java/org/apache/flink/runtime/jobmaster/LogicalSlot.java ---
    @@ -0,0 +1,165 @@
    +/*
    + * Licensed to the Apache Software Foundation (ASF) under one
    + * or more contributor license agreements.  See the NOTICE file
    + * distributed with this work for additional information
    + * regarding copyright ownership.  The ASF licenses this file
    + * to you under the Apache License, Version 2.0 (the
    + * "License"); you may not use this file except in compliance
    + * with the License.  You may obtain a copy of the License at
    + *
    + *     http://www.apache.org/licenses/LICENSE-2.0
    + *
    + * Unless required by applicable law or agreed to in writing, software
    + * distributed under the License is distributed on an "AS IS" BASIS,
    + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    + * See the License for the specific language governing permissions and
    + * limitations under the License.
    + */
    +
    +package org.apache.flink.runtime.jobmaster;
    +
    +import org.apache.flink.runtime.clusterframework.types.AllocationID;
    +import org.apache.flink.runtime.instance.SlotSharingGroupId;
    +import org.apache.flink.runtime.jobmanager.scheduler.Locality;
    +import org.apache.flink.runtime.jobmanager.slots.TaskManagerGateway;
    +import org.apache.flink.runtime.taskmanager.TaskManagerLocation;
    +
    +import javax.annotation.Nullable;
    +
    +import java.util.concurrent.CompletableFuture;
    +
    +/**
    + * A logical slot represents a resource on a TaskManager into
    + * which a single task can be deployed.
    + */
    +public interface LogicalSlot {
    +
    +	 Payload TERMINATED_PAYLOAD = new Payload() {
    +
    +		private final CompletableFuture<?> COMPLETED_TERMINATION_FUTURE = CompletableFuture.completedFuture(null);
    --- End diff --
    
    nit: `COMPLETED_TERMINATION_FUTURE` should be camel cased because is not actually a constant (not static).


---

[GitHub] flink pull request #5091: [FLINK-7956] [flip6] Add support for queued schedu...

Posted by tillrohrmann <gi...@git.apache.org>.
Github user tillrohrmann commented on a diff in the pull request:

    https://github.com/apache/flink/pull/5091#discussion_r156902262
  
    --- Diff: flink-runtime/src/test/java/org/apache/flink/runtime/jobmaster/slotpool/SlotSharingManagerTest.java ---
    @@ -0,0 +1,502 @@
    +/*
    + * Licensed to the Apache Software Foundation (ASF) under one
    + * or more contributor license agreements.  See the NOTICE file
    + * distributed with this work for additional information
    + * regarding copyright ownership.  The ASF licenses this file
    + * to you under the Apache License, Version 2.0 (the
    + * "License"); you may not use this file except in compliance
    + * with the License.  You may obtain a copy of the License at
    + *
    + *     http://www.apache.org/licenses/LICENSE-2.0
    + *
    + * Unless required by applicable law or agreed to in writing, software
    + * distributed under the License is distributed on an "AS IS" BASIS,
    + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    + * See the License for the specific language governing permissions and
    + * limitations under the License.
    + */
    +
    +package org.apache.flink.runtime.jobmaster.slotpool;
    +
    +import org.apache.flink.runtime.clusterframework.types.AllocationID;
    +import org.apache.flink.runtime.executiongraph.utils.SimpleAckingTaskManagerGateway;
    +import org.apache.flink.runtime.instance.SimpleSlotContext;
    +import org.apache.flink.runtime.instance.SlotSharingGroupId;
    +import org.apache.flink.runtime.jobmanager.scheduler.Locality;
    +import org.apache.flink.runtime.jobmanager.slots.DummySlotOwner;
    +import org.apache.flink.runtime.jobmaster.LogicalSlot;
    +import org.apache.flink.runtime.jobmaster.SlotContext;
    +import org.apache.flink.runtime.jobmaster.SlotRequestId;
    +import org.apache.flink.runtime.taskmanager.LocalTaskManagerLocation;
    +import org.apache.flink.util.AbstractID;
    +import org.apache.flink.util.FlinkException;
    +import org.apache.flink.util.TestLogger;
    +
    +import org.junit.Test;
    +
    +import java.util.Collections;
    +import java.util.Objects;
    +import java.util.concurrent.CompletableFuture;
    +import java.util.concurrent.ExecutionException;
    +
    +import static org.junit.Assert.assertEquals;
    +import static org.junit.Assert.assertFalse;
    +import static org.junit.Assert.assertNotNull;
    +import static org.junit.Assert.assertNull;
    +import static org.junit.Assert.assertTrue;
    +
    +/**
    + * Test cases for the {@link SlotSharingManager}.
    + */
    +public class SlotSharingManagerTest extends TestLogger {
    +
    +	private static final SlotSharingGroupId slotSharingGroupId = new SlotSharingGroupId();
    --- End diff --
    
    True.


---

[GitHub] flink pull request #5091: [FLINK-7956] [flip6] Add support for queued schedu...

Posted by GJL <gi...@git.apache.org>.
Github user GJL commented on a diff in the pull request:

    https://github.com/apache/flink/pull/5091#discussion_r155549755
  
    --- Diff: flink-runtime/src/main/java/org/apache/flink/runtime/jobmaster/LogicalSlot.java ---
    @@ -32,6 +34,20 @@
      */
     public interface LogicalSlot {
     
    +	 Payload TERMINATED_PAYLOAD = new Payload() {
    +
    +		private final CompletableFuture<?> COMPLETED_TERMINATION_FUTURE = CompletableFuture.completedFuture(null);
    --- End diff --
    
    nit: `COMPLETED_TERMINATION_FUTURE` should be camel cased because is not actually a constant (not static).


---

[GitHub] flink pull request #5091: [FLINK-7956] [flip6] Add support for queued schedu...

Posted by GJL <gi...@git.apache.org>.
Github user GJL commented on a diff in the pull request:

    https://github.com/apache/flink/pull/5091#discussion_r155507607
  
    --- Diff: flink-runtime/src/main/java/org/apache/flink/runtime/jobmaster/slotpool/SlotSharingManager.java ---
    @@ -0,0 +1,722 @@
    +/*
    + * Licensed to the Apache Software Foundation (ASF) under one
    + * or more contributor license agreements.  See the NOTICE file
    + * distributed with this work for additional information
    + * regarding copyright ownership.  The ASF licenses this file
    + * to you under the Apache License, Version 2.0 (the
    + * "License"); you may not use this file except in compliance
    + * with the License.  You may obtain a copy of the License at
    + *
    + *     http://www.apache.org/licenses/LICENSE-2.0
    + *
    + * Unless required by applicable law or agreed to in writing, software
    + * distributed under the License is distributed on an "AS IS" BASIS,
    + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    + * See the License for the specific language governing permissions and
    + * limitations under the License.
    + */
    +
    +package org.apache.flink.runtime.jobmaster.slotpool;
    +
    +import org.apache.flink.annotation.VisibleForTesting;
    +import org.apache.flink.runtime.jobmaster.LogicalSlot;
    +import org.apache.flink.runtime.jobmaster.SlotContext;
    +import org.apache.flink.runtime.jobmaster.SlotOwner;
    +import org.apache.flink.runtime.jobmaster.SlotRequestId;
    +import org.apache.flink.runtime.instance.SlotSharingGroupId;
    --- End diff --
    
    nit: wrong import order (not sorted lexicographically)
    ```
    import org.apache.flink.runtime.instance.SlotSharingGroupId;
    import org.apache.flink.runtime.jobmanager.scheduler.Locality;
    ```
    items should appear before `LogicalSlot`


---

[GitHub] flink pull request #5091: [FLINK-7956] [flip6] Add support for queued schedu...

Posted by tillrohrmann <gi...@git.apache.org>.
Github user tillrohrmann commented on a diff in the pull request:

    https://github.com/apache/flink/pull/5091#discussion_r156905291
  
    --- Diff: flink-runtime/src/main/java/org/apache/flink/runtime/jobmaster/slotpool/SlotPool.java ---
    @@ -266,104 +279,367 @@ public void disconnectResourceManager() {
     	// ------------------------------------------------------------------------
     
     	@Override
    -	public CompletableFuture<SimpleSlot> allocateSlot(
    -			SlotRequestID requestId,
    -			ScheduledUnit task,
    -			ResourceProfile resources,
    -			Iterable<TaskManagerLocation> locationPreferences,
    +	public CompletableFuture<LogicalSlot> allocateSlot(
    +			SlotRequestId slotRequestId,
    +			ScheduledUnit scheduledUnit,
    +			ResourceProfile resourceProfile,
    +			Collection<TaskManagerLocation> locationPreferences,
    +			boolean allowQueuedScheduling,
     			Time timeout) {
     
    -		return internalAllocateSlot(requestId, task, resources, locationPreferences);
    +		return internalAllocateSlot(
    +			slotRequestId,
    +			scheduledUnit,
    +			resourceProfile,
    +			locationPreferences,
    +			allowQueuedScheduling);
     	}
     
    -	@Override
    -	public void returnAllocatedSlot(Slot slot) {
    -		internalReturnAllocatedSlot(slot);
    +	private CompletableFuture<LogicalSlot> internalAllocateSlot(
    +			SlotRequestId slotRequestId,
    +			ScheduledUnit task,
    +			ResourceProfile resourceProfile,
    +			Collection<TaskManagerLocation> locationPreferences,
    +			boolean allowQueuedScheduling) {
    +
    +		final SlotSharingGroupId slotSharingGroupId = task.getSlotSharingGroupId();
    +
    +		if (slotSharingGroupId != null) {
    +			// allocate slot with slot sharing
    +			final SlotSharingManager multiTaskSlotManager = slotSharingManagers.computeIfAbsent(
    +				slotSharingGroupId,
    +				id -> new SlotSharingManager(
    +					id,
    +					this,
    +					providerAndOwner));
    +
    +			final SlotSharingManager.MultiTaskSlotLocality multiTaskSlotFuture;
    +
    +			try {
    +				if (task.getCoLocationConstraint() != null) {
    +					multiTaskSlotFuture = allocateCoLocatedMultiTaskSlot(
    +						task.getCoLocationConstraint(),
    +						multiTaskSlotManager,
    +						resourceProfile,
    +						locationPreferences,
    +						allowQueuedScheduling);
    +				} else {
    +					multiTaskSlotFuture = allocateMultiTaskSlot(
    +						task.getJobVertexId(), multiTaskSlotManager,
    +						resourceProfile,
    +						locationPreferences,
    +						allowQueuedScheduling);
    +				}
    +			} catch (NoResourceAvailableException noResourceException) {
    +				return FutureUtils.completedExceptionally(noResourceException);
    +			}
    +
    +			// sanity check
    +			Preconditions.checkState(!multiTaskSlotFuture.getMultiTaskSlot().contains(task.getJobVertexId()));
    +
    +			final SlotSharingManager.SingleTaskSlot leave = multiTaskSlotFuture.getMultiTaskSlot().allocateSingleTaskSlot(
    +				slotRequestId,
    +				task.getJobVertexId(),
    +				multiTaskSlotFuture.getLocality());
    +
    +			return leave.getLogicalSlotFuture();
    +		} else {
    +			// request an allocated slot to assign a single logical slot to
    +			CompletableFuture<SlotAndLocality> slotAndLocalityFuture = requestAllocatedSlot(
    +				slotRequestId,
    +				resourceProfile,
    +				locationPreferences,
    +				allowQueuedScheduling);
    +
    +			return slotAndLocalityFuture.thenApply(
    +				(SlotAndLocality slotAndLocality) -> {
    +					final AllocatedSlot allocatedSlot = slotAndLocality.getSlot();
    +
    +					final SingleLogicalSlot singleTaskSlot = new SingleLogicalSlot(
    +						slotRequestId,
    +						allocatedSlot,
    +						null,
    +						slotAndLocality.getLocality(),
    +						providerAndOwner);
    +
    +					if (allocatedSlot.tryAssignPayload(singleTaskSlot)) {
    +						return singleTaskSlot;
    +					} else {
    +						final FlinkException flinkException = new FlinkException("Could not assign payload to allocated slot " + allocatedSlot.getAllocationId() + '.');
    +						releaseSlot(slotRequestId, null, flinkException);
    +						throw new CompletionException(flinkException);
    +					}
    +				});
    +		}
     	}
     
    -	@Override
    -	public CompletableFuture<Acknowledge> cancelSlotAllocation(SlotRequestID requestId) {
    -		final PendingRequest pendingRequest = removePendingRequest(requestId);
    +	/**
    +	 * Allocates a co-located {@link SlotSharingManager.MultiTaskSlot} for the given {@link CoLocationConstraint}.
    +	 *
    +	 * <p>If allowQueuedScheduling is true, then the returned {@link SlotSharingManager.MultiTaskSlot} can be
    +	 * uncompleted.
    +	 *
    +	 * @param coLocationConstraint for which to allocate a {@link SlotSharingManager.MultiTaskSlot}
    +	 * @param multiTaskSlotManager responsible for the slot sharing group for which to allocate the slot
    +	 * @param resourceProfile specifying the requirements for the requested slot
    +	 * @param locationPreferences containing preferred TaskExecutors on which to allocate the slot
    +	 * @param allowQueuedScheduling true if queued scheduling (the returned task slot must not be completed yet) is allowed, otherwise false
    +	 * @return A {@link SlotSharingManager.MultiTaskSlotLocality} which contains the allocated{@link SlotSharingManager.MultiTaskSlot}
    +	 * 		and its locality wrt the given location preferences
    +	 * @throws NoResourceAvailableException if no task slot could be allocated
    +	 */
    +	private SlotSharingManager.MultiTaskSlotLocality allocateCoLocatedMultiTaskSlot(
    +			CoLocationConstraint coLocationConstraint,
    +			SlotSharingManager multiTaskSlotManager,
    +			ResourceProfile resourceProfile,
    +			Collection<TaskManagerLocation> locationPreferences,
    +			boolean allowQueuedScheduling) throws NoResourceAvailableException {
    +		final SlotRequestId coLocationSlotRequestId = coLocationConstraint.getSlotRequestId();
    +
    +		if (coLocationSlotRequestId != null) {
    +			// we have a slot assigned --> try to retrieve it
    +			final SlotSharingManager.TaskSlot taskSlot = multiTaskSlotManager.getTaskSlot(coLocationSlotRequestId);
    +
    +			if (taskSlot != null) {
    +				Preconditions.checkState(taskSlot instanceof SlotSharingManager.MultiTaskSlot);
    +				return SlotSharingManager.MultiTaskSlotLocality.of(((SlotSharingManager.MultiTaskSlot) taskSlot), Locality.LOCAL);
    +			} else {
    +				// the slot may have been cancelled in the mean time
    +				coLocationConstraint.setSlotRequestId(null);
    +			}
    +		}
     
    -		if (pendingRequest != null) {
    -			failPendingRequest(pendingRequest, new CancellationException("Allocation with request id" + requestId + " cancelled."));
    +		final Collection<TaskManagerLocation> actualLocationPreferences;
    +
    +		if (coLocationConstraint.isAssigned()) {
    +			actualLocationPreferences = Collections.singleton(coLocationConstraint.getLocation());
     		} else {
    -			final Slot slot = allocatedSlots.get(requestId);
    +			actualLocationPreferences = locationPreferences;
    +		}
    +
    +		// get a new multi task slot
    +		final SlotSharingManager.MultiTaskSlotLocality multiTaskSlotLocality = allocateMultiTaskSlot(
    +			coLocationConstraint.getGroupId(), multiTaskSlotManager,
    +			resourceProfile,
    +			actualLocationPreferences,
    +			allowQueuedScheduling);
    +
    +		// check whether we fulfill the co-location constraint
    +		if (coLocationConstraint.isAssigned() && multiTaskSlotLocality.getLocality() != Locality.LOCAL) {
    +			multiTaskSlotLocality.getMultiTaskSlot().release(
    +				new FlinkException("Multi task slot is not local and, thus, does not fulfill the co-location constraint."));
     
    -			if (slot != null) {
    -				LOG.info("Returning allocated slot {} because the corresponding allocation request {} was cancelled.", slot, requestId);
    -				if (slot.markCancelled()) {
    -					internalReturnAllocatedSlot(slot);
    +			throw new NoResourceAvailableException("Could not allocate a local multi task slot for the " +
    +				"co location constraint " + coLocationConstraint + '.');
    +		}
    +
    +		final SlotRequestId slotRequestId = new SlotRequestId();
    +		final SlotSharingManager.MultiTaskSlot coLocationSlot = multiTaskSlotLocality.getMultiTaskSlot().allocateMultiTaskSlot(
    +			slotRequestId,
    +			coLocationConstraint.getGroupId());
    +
    +		// mark the requested slot as co-located slot for other co-located tasks
    +		coLocationConstraint.setSlotRequestId(slotRequestId);
    +
    +		// lock the co-location constraint once we have obtained the allocated slot
    +		coLocationSlot.getSlotContextFuture().whenComplete(
    +			(SlotContext slotContext, Throwable throwable) -> {
    +				if (throwable == null) {
    +					// check whether we are still assigned to the co-location constraint
    +					if (Objects.equals(coLocationConstraint.getSlotRequestId(), slotRequestId)) {
    +						coLocationConstraint.lockLocation(slotContext.getTaskManagerLocation());
    +					}
     				}
    +			});
    +
    +		return SlotSharingManager.MultiTaskSlotLocality.of(coLocationSlot, multiTaskSlotLocality.getLocality());
    +	}
    +
    +	/**
    +	 * Allocates a {@link SlotSharingManager.MultiTaskSlot} for the given groupId which is in the
    +	 * slot sharing group for which the given {@link SlotSharingManager} is responsible.
    +	 *
    +	 * <p>If allowQueuedScheduling is true, then the method can return an uncompleted {@link SlotSharingManager.MultiTaskSlot}.
    +	 *
    +	 * @param groupId for which to allocate a new {@link SlotSharingManager.MultiTaskSlot}
    +	 * @param slotSharingManager responsible for the slot sharing group for which to allocate the slot
    +	 * @param resourceProfile specifying the requirements for the requested slot
    +	 * @param locationPreferences containing preferred TaskExecutors on which to allocate the slot
    +	 * @param allowQueuedScheduling true if queued scheduling (the returned task slot must not be completed yet) is allowed, otherwise false
    +	 * @return A {@link SlotSharingManager.MultiTaskSlotLocality} which contains the allocated {@link SlotSharingManager.MultiTaskSlot}
    +	 * 		and its locality wrt the given location preferences
    +	 * @throws NoResourceAvailableException if no task slot could be allocated
    +	 */
    +	private SlotSharingManager.MultiTaskSlotLocality allocateMultiTaskSlot(
    +			AbstractID groupId,
    +			SlotSharingManager slotSharingManager,
    +			ResourceProfile resourceProfile,
    +			Collection<TaskManagerLocation> locationPreferences,
    +			boolean allowQueuedScheduling) throws NoResourceAvailableException {
    +
    +		// check first whether we have a resolved root slot which we can use
    +		SlotSharingManager.MultiTaskSlotLocality multiTaskSlotLocality = slotSharingManager.getResolvedRootSlot(
    +			groupId,
    +			locationPreferences);
    +
    +		if (multiTaskSlotLocality != null && multiTaskSlotLocality.getLocality() == Locality.LOCAL) {
    +			return multiTaskSlotLocality;
    +		}
    +
    +		final SlotRequestId allocatedSlotRequestId = new SlotRequestId();
    +		final SlotRequestId multiTaskSlotRequestId = new SlotRequestId();
    +
    +		// check whether we have an allocated slot available which we can use to create a new multi task slot in
    +		final SlotAndLocality slotAndLocality = pollAndAllocateSlot(allocatedSlotRequestId, resourceProfile, locationPreferences);
    +
    +		if (slotAndLocality != null && (slotAndLocality.getLocality() == Locality.LOCAL || multiTaskSlotLocality == null)) {
    +
    +			final AllocatedSlot allocatedSlot = slotAndLocality.getSlot();
    +			final SlotSharingManager.MultiTaskSlot multiTaskSlot = slotSharingManager.createRootSlot(
    +				multiTaskSlotRequestId,
    +				CompletableFuture.completedFuture(slotAndLocality.getSlot()),
    +				allocatedSlotRequestId);
    +
    +			if (allocatedSlot.tryAssignPayload(multiTaskSlot)) {
    +				return SlotSharingManager.MultiTaskSlotLocality.of(multiTaskSlot, slotAndLocality.getLocality());
     			} else {
    -				LOG.debug("There was no slot allocation with {} to be cancelled.", requestId);
    +				multiTaskSlot.release(new FlinkException("Could not assign payload to allocated slot " +
    +					allocatedSlot.getAllocationId() + '.'));
     			}
     		}
     
    -		return CompletableFuture.completedFuture(Acknowledge.get());
    -	}
    +		if (multiTaskSlotLocality != null) {
    +			// prefer slot sharing group slots over unused slots
    +			if (slotAndLocality != null) {
    +				releaseSlot(
    +					allocatedSlotRequestId,
    +					null,
    +					new FlinkException("Locality constraint is not better fulfilled by allocated slot."));
    +			}
    +			return multiTaskSlotLocality;
    --- End diff --
    
    Yes because it could not find a slot which is `LOCAL`. The alternative would be to ask the ResourceManager but it will only give you a slot with an `UNKNOWN` locality because it is uncompleted.


---

[GitHub] flink pull request #5091: [FLINK-7956] [flip6] Add support for queued schedu...

Posted by tillrohrmann <gi...@git.apache.org>.
Github user tillrohrmann commented on a diff in the pull request:

    https://github.com/apache/flink/pull/5091#discussion_r156902071
  
    --- Diff: flink-runtime/src/main/java/org/apache/flink/runtime/jobmaster/slotpool/SlotSharingManager.java ---
    @@ -0,0 +1,722 @@
    +/*
    + * Licensed to the Apache Software Foundation (ASF) under one
    + * or more contributor license agreements.  See the NOTICE file
    + * distributed with this work for additional information
    + * regarding copyright ownership.  The ASF licenses this file
    + * to you under the Apache License, Version 2.0 (the
    + * "License"); you may not use this file except in compliance
    + * with the License.  You may obtain a copy of the License at
    + *
    + *     http://www.apache.org/licenses/LICENSE-2.0
    + *
    + * Unless required by applicable law or agreed to in writing, software
    + * distributed under the License is distributed on an "AS IS" BASIS,
    + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    + * See the License for the specific language governing permissions and
    + * limitations under the License.
    + */
    +
    +package org.apache.flink.runtime.jobmaster.slotpool;
    +
    +import org.apache.flink.annotation.VisibleForTesting;
    +import org.apache.flink.runtime.jobmaster.LogicalSlot;
    +import org.apache.flink.runtime.jobmaster.SlotContext;
    +import org.apache.flink.runtime.jobmaster.SlotOwner;
    +import org.apache.flink.runtime.jobmaster.SlotRequestId;
    +import org.apache.flink.runtime.instance.SlotSharingGroupId;
    +import org.apache.flink.runtime.jobmanager.scheduler.Locality;
    +import org.apache.flink.runtime.taskmanager.TaskManagerLocation;
    +import org.apache.flink.util.AbstractID;
    +import org.apache.flink.util.FlinkException;
    +import org.apache.flink.util.Preconditions;
    +
    +import javax.annotation.Nullable;
    +
    +import java.util.AbstractCollection;
    +import java.util.Collection;
    +import java.util.Collections;
    +import java.util.HashMap;
    +import java.util.HashSet;
    +import java.util.Iterator;
    +import java.util.Map;
    +import java.util.Objects;
    +import java.util.Set;
    +import java.util.concurrent.CompletableFuture;
    +
    +/**
    + * Manager which is responsible for slot sharing. Slot sharing allows to run different
    + * tasks in the same slot and to realize co-location constraints.
    + *
    + * <p>The SlotSharingManager allows to create a hierarchy of {@link TaskSlot} such that
    + * every {@link TaskSlot} is uniquely identified by a {@link SlotRequestId} identifying
    + * the request for the TaskSlot and a {@link AbstractID} identifying the task or the
    + * co-location constraint running in this slot.
    + *
    + * <p>The {@link TaskSlot} hierarchy is implemented by {@link MultiTaskSlot} and
    + * {@link SingleTaskSlot}. The former class represents inner nodes which can contain
    + * a number of other {@link TaskSlot} and the latter class represents the leave nodes.
    --- End diff --
    
    good catch.


---

[GitHub] flink pull request #5091: [FLINK-7956] [flip6] Add support for queued schedu...

Posted by tillrohrmann <gi...@git.apache.org>.
Github user tillrohrmann commented on a diff in the pull request:

    https://github.com/apache/flink/pull/5091#discussion_r156892479
  
    --- Diff: flink-runtime/src/main/java/org/apache/flink/runtime/jobmaster/LogicalSlot.java ---
    @@ -0,0 +1,165 @@
    +/*
    + * Licensed to the Apache Software Foundation (ASF) under one
    + * or more contributor license agreements.  See the NOTICE file
    + * distributed with this work for additional information
    + * regarding copyright ownership.  The ASF licenses this file
    + * to you under the Apache License, Version 2.0 (the
    + * "License"); you may not use this file except in compliance
    + * with the License.  You may obtain a copy of the License at
    + *
    + *     http://www.apache.org/licenses/LICENSE-2.0
    + *
    + * Unless required by applicable law or agreed to in writing, software
    + * distributed under the License is distributed on an "AS IS" BASIS,
    + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    + * See the License for the specific language governing permissions and
    + * limitations under the License.
    + */
    +
    +package org.apache.flink.runtime.jobmaster;
    +
    +import org.apache.flink.runtime.clusterframework.types.AllocationID;
    +import org.apache.flink.runtime.instance.SlotSharingGroupId;
    +import org.apache.flink.runtime.jobmanager.scheduler.Locality;
    +import org.apache.flink.runtime.jobmanager.slots.TaskManagerGateway;
    +import org.apache.flink.runtime.taskmanager.TaskManagerLocation;
    +
    +import javax.annotation.Nullable;
    +
    +import java.util.concurrent.CompletableFuture;
    +
    +/**
    + * A logical slot represents a resource on a TaskManager into
    + * which a single task can be deployed.
    + */
    +public interface LogicalSlot {
    +
    +	 Payload TERMINATED_PAYLOAD = new Payload() {
    +
    +		private final CompletableFuture<?> COMPLETED_TERMINATION_FUTURE = CompletableFuture.completedFuture(null);
    --- End diff --
    
    Good point. Will fix it.


---

[GitHub] flink pull request #5091: [FLINK-7956] [flip6] Add support for queued schedu...

Posted by tillrohrmann <gi...@git.apache.org>.
Github user tillrohrmann commented on a diff in the pull request:

    https://github.com/apache/flink/pull/5091#discussion_r156890924
  
    --- Diff: flink-runtime/src/main/java/org/apache/flink/runtime/jobmaster/slotpool/SlotSharingManager.java ---
    @@ -0,0 +1,722 @@
    +/*
    + * Licensed to the Apache Software Foundation (ASF) under one
    + * or more contributor license agreements.  See the NOTICE file
    + * distributed with this work for additional information
    + * regarding copyright ownership.  The ASF licenses this file
    + * to you under the Apache License, Version 2.0 (the
    + * "License"); you may not use this file except in compliance
    + * with the License.  You may obtain a copy of the License at
    + *
    + *     http://www.apache.org/licenses/LICENSE-2.0
    + *
    + * Unless required by applicable law or agreed to in writing, software
    + * distributed under the License is distributed on an "AS IS" BASIS,
    + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    + * See the License for the specific language governing permissions and
    + * limitations under the License.
    + */
    +
    +package org.apache.flink.runtime.jobmaster.slotpool;
    +
    +import org.apache.flink.annotation.VisibleForTesting;
    +import org.apache.flink.runtime.jobmaster.LogicalSlot;
    +import org.apache.flink.runtime.jobmaster.SlotContext;
    +import org.apache.flink.runtime.jobmaster.SlotOwner;
    +import org.apache.flink.runtime.jobmaster.SlotRequestId;
    +import org.apache.flink.runtime.instance.SlotSharingGroupId;
    +import org.apache.flink.runtime.jobmanager.scheduler.Locality;
    +import org.apache.flink.runtime.taskmanager.TaskManagerLocation;
    +import org.apache.flink.util.AbstractID;
    +import org.apache.flink.util.FlinkException;
    +import org.apache.flink.util.Preconditions;
    +
    +import javax.annotation.Nullable;
    +
    +import java.util.AbstractCollection;
    +import java.util.Collection;
    +import java.util.Collections;
    +import java.util.HashMap;
    +import java.util.HashSet;
    +import java.util.Iterator;
    +import java.util.Map;
    +import java.util.Objects;
    +import java.util.Set;
    +import java.util.concurrent.CompletableFuture;
    +
    +/**
    + * Manager which is responsible for slot sharing. Slot sharing allows to run different
    + * tasks in the same slot and to realize co-location constraints.
    + *
    + * <p>The SlotSharingManager allows to create a hierarchy of {@link TaskSlot} such that
    + * every {@link TaskSlot} is uniquely identified by a {@link SlotRequestId} identifying
    + * the request for the TaskSlot and a {@link AbstractID} identifying the task or the
    + * co-location constraint running in this slot.
    + *
    + * <p>The {@link TaskSlot} hierarchy is implemented by {@link MultiTaskSlot} and
    + * {@link SingleTaskSlot}. The former class represents inner nodes which can contain
    + * a number of other {@link TaskSlot} and the latter class represents the leave nodes.
    + * The hierarchy starts with a root {@link MultiTaskSlot} which is a future
    + * {@link SlotContext} assigned. The {@link SlotContext} represents the allocated slot
    + * on the TaskExecutor in which all slots of this hierarchy run. A {@link MultiTaskSlot}
    + * can be assigned multiple {@link SingleTaskSlot} or {@link MultiTaskSlot} if and only if
    + * the task slot does not yet contain another child with the same {@link AbstractID} identifying
    + * the actual task or the co-location constraint.
    + *
    + * <p>Normal slot sharing is represented by a root {@link MultiTaskSlot} which contains a set
    + * of {@link SingleTaskSlot} on the second layer. Each {@link SingleTaskSlot} represents a different
    + * task.
    + *
    + * <p>Co-location constraints are modeled by adding a {@link MultiTaskSlot} to the root node. The co-location
    + * constraint is uniquely identified by a {@link AbstractID} such that we cannot add a second co-located
    + * {@link MultiTaskSlot} to the same root node. Now all co-located tasks will be added to co-located
    + * multi task slot.
    + */
    +public class SlotSharingManager {
    +
    +	private final SlotSharingGroupId slotSharingGroupId;
    +
    +	// needed to release allocated slots after a complete multi task slot hierarchy has been released
    +	private final AllocatedSlotActions allocatedSlotActions;
    +
    +	// owner of the slots to which to return them when they are released from the outside
    +	private final SlotOwner slotOwner;
    +
    +	private final Map<SlotRequestId, TaskSlot> allTaskSlots;
    +
    +	// Root nodes which have not been completed because the allocated slot is still pending
    +	private final Map<SlotRequestId, MultiTaskSlot> unresolvedRootSlots;
    +
    +	// Root nodes which have been completed (the underlying allocated slot has been assigned)
    +	private final Map<TaskManagerLocation, Set<MultiTaskSlot>> resolvedRootSlots;
    +
    +	// Internal class to iterate over all resolved root slots
    +	private ResolvedRootSlotValues resolvedMultiTaskSlotValues;
    +
    +	public SlotSharingManager(
    +			SlotSharingGroupId slotSharingGroupId,
    +			AllocatedSlotActions allocatedSlotActions,
    +			SlotOwner slotOwner) {
    +		this.slotSharingGroupId = Preconditions.checkNotNull(slotSharingGroupId);
    +		this.allocatedSlotActions = Preconditions.checkNotNull(allocatedSlotActions);
    +		this.slotOwner = Preconditions.checkNotNull(slotOwner);
    +
    +		allTaskSlots = new HashMap<>(16);
    +		unresolvedRootSlots = new HashMap<>(16);
    +		resolvedRootSlots = new HashMap<>(16);
    +
    +		resolvedMultiTaskSlotValues = null;
    +	}
    +
    +	public boolean isEmpty() {
    +		return allTaskSlots.isEmpty();
    +	}
    +
    +	public boolean contains(SlotRequestId slotRequestId) {
    +		return allTaskSlots.containsKey(slotRequestId);
    +	}
    +
    +	@Nullable
    +	public TaskSlot getTaskSlot(SlotRequestId slotRequestId) {
    +		return allTaskSlots.get(slotRequestId);
    +	}
    +
    +	/**
    +	 * Creates a new root slot with the given {@link SlotRequestId}, {@link SlotContext} future and
    +	 * the {@link SlotRequestId} of the allocated slot.
    +	 *
    +	 * @param slotRequestId of the root slot
    +	 * @param slotContextFuture with which we create the root slot
    +	 * @param allocatedSlotRequestId slot request id of the underlying allocated slot which can be used
    +	 *                               to cancel the pending slot request or release the allocated slot
    +	 * @return New root slot
    +	 */
    +	public MultiTaskSlot createRootSlot(
    +			SlotRequestId slotRequestId,
    +			CompletableFuture<SlotContext> slotContextFuture,
    +			SlotRequestId allocatedSlotRequestId) {
    +		final MultiTaskSlot rootMultiTaskSlot = new MultiTaskSlot(
    +			slotRequestId,
    +			slotContextFuture,
    +			allocatedSlotRequestId);
    +
    +		allTaskSlots.put(slotRequestId, rootMultiTaskSlot);
    +		unresolvedRootSlots.put(slotRequestId, rootMultiTaskSlot);
    +
    +		// add the root node to the set of resolved root nodes once the SlotContext future has been completed
    +		// and we know the slot's TaskManagerLocation
    +		slotContextFuture.whenComplete(
    +			(SlotContext slotContext, Throwable throwable) -> {
    +				if (slotContext != null) {
    +					final MultiTaskSlot resolvedRootNode = unresolvedRootSlots.remove(slotRequestId);
    +
    +					if (resolvedRootNode != null) {
    +						final Set<MultiTaskSlot> innerCollection = resolvedRootSlots.computeIfAbsent(
    +							slotContext.getTaskManagerLocation(),
    +							taskManagerLocation -> new HashSet<>(4));
    +
    +						innerCollection.add(resolvedRootNode);
    +					}
    +				} else {
    +					rootMultiTaskSlot.release(throwable);
    +				}
    +			});
    +
    +		return rootMultiTaskSlot;
    +	}
    +
    +	/**
    +	 * Gets a resolved root slot which does not yet contain the given groupId. First the given set of
    +	 * preferred locations is checked.
    +	 *
    +	 * @param groupId which the returned slot must not contain
    +	 * @param locationPreferences specifying which locations are preferred
    +	 * @return the resolved root slot and its locality wrt to the specified location preferences
    +	 * 		or null if there was no root slot which did not contain the given groupId
    +	 */
    +	@Nullable
    +	public MultiTaskSlotLocality getResolvedRootSlot(AbstractID groupId, Collection<TaskManagerLocation> locationPreferences) {
    +		Preconditions.checkNotNull(locationPreferences);
    +
    +		if (locationPreferences.isEmpty()) {
    +			return getResolvedRootSlotWithoutLocationPreferences(groupId);
    +		} else {
    +			return getResolvedRootSlotWithLocationPreferences(groupId, locationPreferences);
    +		}
    +	}
    +
    +	/**
    +	 * Gets a resolved root slot which does not yet contain the given groupId. The method will try to
    +	 * find a slot of a TaskManager contained in the collection of preferred locations. If there is no such slot
    +	 * with free capacities available, then the method will look for slots of TaskManager which run on the same
    +	 * machine as the TaskManager in the collection of preferred locations. If there is no such slot, then any slot
    +	 * with free capacities is returned. If there is no such slot, then null is returned.
    +	 *
    +	 * @param groupId which the returned slot must not contain
    +	 * @param locationPreferences specifying which locations are preferred
    +	 * @return the resolved root slot and its locality wrt to the specified location preferences
    +	 * 		or null if there was not root slot which did not contain the given groupId
    +	 */
    +	@Nullable
    +	private MultiTaskSlotLocality getResolvedRootSlotWithLocationPreferences(AbstractID groupId, Collection<TaskManagerLocation> locationPreferences) {
    +		Preconditions.checkNotNull(groupId);
    +		Preconditions.checkNotNull(locationPreferences);
    +		final Set<String> hostnameSet = new HashSet<>();
    +
    +		for (TaskManagerLocation locationPreference : locationPreferences) {
    +			final Set<MultiTaskSlot> multiTaskSlots = resolvedRootSlots.get(locationPreference);
    +
    +			if (multiTaskSlots != null) {
    +				for (MultiTaskSlot multiTaskSlot : multiTaskSlots) {
    +					if (!multiTaskSlot.contains(groupId)) {
    +						return MultiTaskSlotLocality.of(multiTaskSlot, Locality.LOCAL);
    +					}
    +				}
    +
    +				hostnameSet.add(locationPreference.getHostname());
    +			}
    +		}
    +
    +		MultiTaskSlot nonLocalMultiTaskSlot = null;
    +
    +		for (Map.Entry<TaskManagerLocation, Set<MultiTaskSlot>> taskManagerLocationSetEntry : resolvedRootSlots.entrySet()) {
    +			if (hostnameSet.contains(taskManagerLocationSetEntry.getKey().getHostname())) {
    +				for (MultiTaskSlot multiTaskSlot : taskManagerLocationSetEntry.getValue()) {
    +					if (!multiTaskSlot.contains(groupId)) {
    +						return MultiTaskSlotLocality.of(multiTaskSlot, Locality.HOST_LOCAL);
    +					}
    +				}
    +			} else if (nonLocalMultiTaskSlot == null) {
    +				for (MultiTaskSlot multiTaskSlot : taskManagerLocationSetEntry.getValue()) {
    +					if (!multiTaskSlot.contains(groupId)) {
    +						nonLocalMultiTaskSlot = multiTaskSlot;
    +					}
    +				}
    +			}
    +		}
    +
    +		if (nonLocalMultiTaskSlot != null) {
    +			return MultiTaskSlotLocality.of(nonLocalMultiTaskSlot, Locality.NON_LOCAL);
    +		} else {
    +			return null;
    +		}
    +	}
    +
    +	/**
    +	 * Gets a resolved slot which does not yet contain the given groupId without any location
    +	 * preferences.
    +	 *
    +	 * @param groupId which the returned slot must not contain
    +	 * @return the resolved slot or null if there was no root slot with free capacities
    +	 */
    +	@Nullable
    +	private MultiTaskSlotLocality getResolvedRootSlotWithoutLocationPreferences(AbstractID groupId) {
    +		Preconditions.checkNotNull(groupId);
    +
    +		for (Set<MultiTaskSlot> multiTaskSlots : resolvedRootSlots.values()) {
    +			for (MultiTaskSlot multiTaskSlot : multiTaskSlots) {
    +				if (!multiTaskSlot.contains(groupId)) {
    +					return MultiTaskSlotLocality.of(multiTaskSlot, Locality.UNCONSTRAINED);
    +				}
    +			}
    +		}
    +
    +		return null;
    +	}
    +
    +	/**
    +	 * Gets an unresolved slot which does not yet contain the given groupId. An unresolved
    +	 * slot is a slot whose underlying allocated slot has not been allocated yet.
    +	 *
    +	 * @param groupId which the returned slot must not contain
    +	 * @return the unresolved slot or null if there was no root slot with free capacities
    +	 */
    +	@Nullable
    +	public MultiTaskSlot getUnresolvedRootSlot(AbstractID groupId) {
    +		for (MultiTaskSlot multiTaskSlot : unresolvedRootSlots.values()) {
    +			if (!multiTaskSlot.contains(groupId)) {
    +				return multiTaskSlot;
    +			}
    +		}
    +
    +		return null;
    +	}
    +
    +	// ------------------------------------------------------------------------
    +	// Inner classes: TaskSlot hierarchy and helper classes
    +	// ------------------------------------------------------------------------
    +
    +	/**
    +	 * Helper class which contains a {@link MultiTaskSlot} and its {@link Locality}.
    +	 */
    +	public static final class MultiTaskSlotLocality {
    +		private final MultiTaskSlot multiTaskSlot;
    +
    +		private final Locality locality;
    +
    +		public MultiTaskSlotLocality(MultiTaskSlot multiTaskSlot, Locality locality) {
    +			this.multiTaskSlot = Preconditions.checkNotNull(multiTaskSlot);
    +			this.locality = Preconditions.checkNotNull(locality);
    +		}
    +
    +		public MultiTaskSlot getMultiTaskSlot() {
    +			return multiTaskSlot;
    +		}
    +
    +		public Locality getLocality() {
    +			return locality;
    +		}
    +
    +		public static MultiTaskSlotLocality of(MultiTaskSlot multiTaskSlot, Locality locality) {
    +			return new MultiTaskSlotLocality(multiTaskSlot, locality);
    +		}
    +	}
    +
    +	/**
    +	 * Base class for all task slots.
    +	 */
    +	public abstract static class TaskSlot {
    +		// every TaskSlot has an associated slot request id
    +		private final SlotRequestId slotRequestId;
    +
    +		// all task slots except for the root slots have a group id assigned
    +		@Nullable
    +		private final AbstractID groupId;
    +
    +		protected TaskSlot(SlotRequestId slotRequestId, @Nullable AbstractID groupId) {
    +			this.slotRequestId = Preconditions.checkNotNull(slotRequestId);
    +			this.groupId = groupId;
    +		}
    +
    +		public SlotRequestId getSlotRequestId() {
    +			return slotRequestId;
    +		}
    +
    +		@Nullable
    +		public AbstractID getGroupId() {
    +			return groupId;
    +		}
    +
    +		/**
    +		 * Check whether the task slot contains the given groupId.
    +		 *
    +		 * @param groupId which to check whether it is contained
    +		 * @return true if the task slot contains the given groupId, otherwise false
    +		 */
    +		public boolean contains(AbstractID groupId) {
    +			return Objects.equals(this.groupId, groupId);
    +		}
    +
    +		/**
    +		 * Release the task slot.
    +		 *
    +		 * @param cause for the release
    +		 * @return true if the slot could be released, otherwise false
    +		 */
    +		public abstract boolean release(Throwable cause);
    +	}
    +
    +	/**
    +	 * {@link TaskSlot} implementation which can have multiple other task slots assigned as children.
    +	 */
    +	public final class MultiTaskSlot extends TaskSlot implements AllocatedSlot.Payload {
    +
    +		private final Map<AbstractID, TaskSlot> children;
    +
    +		// the root node has its parent set to null
    +		@Nullable
    +		private final MultiTaskSlot parent;
    +
    +		// underlying allocated slot
    +		private final CompletableFuture<SlotContext> slotContextFuture;
    +
    +		// slot request id of the allocated slot
    +		@Nullable
    +		private final SlotRequestId allocatedSlotRequestId;
    +
    +		// true if we are currently releasing our children
    +		private boolean releasingChildren;
    +
    +		private MultiTaskSlot(
    +				SlotRequestId slotRequestId,
    +				AbstractID groupId,
    +				MultiTaskSlot parent) {
    +			this(
    +				slotRequestId,
    +				groupId,
    +				Preconditions.checkNotNull(parent),
    +				parent.getSlotContextFuture(),
    +				null);
    +		}
    +
    +		private MultiTaskSlot(
    +				SlotRequestId slotRequestId,
    +				CompletableFuture<SlotContext> slotContextFuture,
    +				SlotRequestId allocatedSlotRequestId) {
    +			this(
    +				slotRequestId,
    +				null,
    +				null,
    +				slotContextFuture,
    +				allocatedSlotRequestId);
    +		}
    +
    +		private MultiTaskSlot(
    +				SlotRequestId slotRequestId,
    +				@Nullable AbstractID groupId,
    +				MultiTaskSlot parent,
    +				CompletableFuture<SlotContext> slotContextFuture,
    +				SlotRequestId allocatedSlotRequestId) {
    +			super(slotRequestId, groupId);
    +
    +			this.parent = parent;
    +			this.slotContextFuture = Preconditions.checkNotNull(slotContextFuture);
    +			this.allocatedSlotRequestId = allocatedSlotRequestId;
    +
    +			this.children = new HashMap<>(16);
    +			this.releasingChildren = false;
    +
    +			slotContextFuture.whenComplete(
    +				(SlotContext ignored, Throwable throwable) -> {
    +					if (throwable != null) {
    +						release(throwable);
    +					}
    +				});
    +		}
    +
    +		public CompletableFuture<SlotContext> getSlotContextFuture() {
    +			return slotContextFuture;
    +		}
    +
    +		/**
    +		 * Allocates a {@link MultiTaskSlot} and registers it under the given groupId at
    +		 * this {@link MultiTaskSlot}.
    +		 *
    +		 * @param slotRequestId of the new multi task slot
    +		 * @param groupId under which the new multi task slot is registered
    +		 * @return the newly allocated {@link MultiTaskSlot}
    +		 */
    +		MultiTaskSlot allocateMultiTaskSlot(SlotRequestId slotRequestId, AbstractID groupId) {
    +			Preconditions.checkState(!super.contains(groupId));
    +
    +			final MultiTaskSlot inner = new MultiTaskSlot(
    +				slotRequestId,
    +				groupId,
    +				this);
    +
    +			children.put(groupId, inner);
    +
    +			// register the newly allocated slot also at the SlotSharingManager
    +			allTaskSlots.put(slotRequestId, inner);
    +
    +			return inner;
    +		}
    +
    +		/**
    +		 * Allocates a {@link SingleTaskSlot} and registeres it under the given groupId at
    +		 * this {@link MultiTaskSlot}.
    +		 *
    +		 * @param slotRequestId of the new single task slot
    +		 * @param groupId under which the new single task slot is registered
    +		 * @param locality of the allocation
    +		 * @return the newly allocated {@link SingleTaskSlot}
    +		 */
    +		SingleTaskSlot allocateSingleTaskSlot(
    +				SlotRequestId slotRequestId,
    +				AbstractID groupId,
    +				Locality locality) {
    +			Preconditions.checkState(!super.contains(groupId));
    +
    +			final SingleTaskSlot leave = new SingleTaskSlot(
    +				slotRequestId,
    +				groupId,
    +				this,
    +				locality);
    +
    +			children.put(groupId, leave);
    +
    +			// register the newly allocated slot also at the SlotSharingManager
    +			allTaskSlots.put(slotRequestId, leave);
    +
    +			return leave;
    +		}
    +
    +		/**
    +		 * Checks whether this slot or any of its children contains the given groupId.
    +		 *
    +		 * @param groupId which to check whether it is contained
    +		 * @return true if this or any of its children contains the given groupId, otherwise false
    +		 */
    +		@Override
    +		public boolean contains(AbstractID groupId) {
    +			if (super.contains(groupId)) {
    +				return true;
    +			} else {
    +				for (TaskSlot taskSlot : children.values()) {
    +					if (taskSlot.contains(groupId)) {
    +						return true;
    +					}
    +				}
    +
    +				return false;
    +			}
    +		}
    +
    +		@Override
    +		public boolean release(Throwable cause) {
    +			releasingChildren = true;
    +
    +			// first release all children and remove them if they could be released immediately
    +			children.values().removeIf(node -> {
    +				boolean release = node.release(cause);
    +
    +				if (release) {
    +					allTaskSlots.remove(node.slotRequestId);
    +				}
    +
    +				return release;
    +			});
    +
    +			releasingChildren = false;
    +
    +			if (children.isEmpty()) {
    +				if (parent != null) {
    +					// we remove ourselves from our parent if we no longer have children
    +					parent.releaseChild(getGroupId());
    +				} else {
    +					// we are the root node --> remove the root node from the list of task slots
    +					allTaskSlots.remove(getSlotRequestId());
    +
    +					if (!slotContextFuture.isDone() || slotContextFuture.isCompletedExceptionally()) {
    +						// the root node should still be unresolved
    +						unresolvedRootSlots.remove(getSlotRequestId());
    +					} else {
    +						// the root node should be resolved --> we can access the slot context
    +						final SlotContext slotContext = slotContextFuture.getNow(null);
    +
    +						if (slotContext != null) {
    +							final Set<MultiTaskSlot> multiTaskSlots = resolvedRootSlots.get(slotContext.getTaskManagerLocation());
    +
    +							if (multiTaskSlots != null) {
    +								multiTaskSlots.remove(this);
    +
    +								if (multiTaskSlots.isEmpty()) {
    +									resolvedRootSlots.remove(slotContext.getTaskManagerLocation());
    +								}
    +							}
    +						}
    +					}
    +
    +					// release the underlying allocated slot
    +					allocatedSlotActions.releaseSlot(allocatedSlotRequestId, null, cause);
    +				}
    +
    +				return true;
    +			} else {
    +				return false;
    +			}
    +		}
    +
    +		/**
    +		 * Releases the child with the given childGroupId.
    +		 *
    +		 * @param childGroupId identifying the child to release
    +		 */
    +		private void releaseChild(AbstractID childGroupId) {
    +			if (!releasingChildren) {
    +				TaskSlot child = children.remove(childGroupId);
    +
    +				if (child != null) {
    +					allTaskSlots.remove(child.getSlotRequestId());
    +				}
    +
    +				if (children.isEmpty()) {
    +					release(new FlinkException("Release multi task slot because all children have been released."));
    +				}
    +			}
    +		}
    +	}
    +
    +	/**
    +	 * {@link TaskSlot} implementation which harbours a {@link LogicalSlot}. The {@link SingleTaskSlot}
    +	 * cannot have any children assigned.
    +	 */
    +	public final class SingleTaskSlot extends TaskSlot {
    +		private final MultiTaskSlot parent;
    +
    +		// future containing a LogicalSlot which is completed once the underlying SlotContext future is completed
    +		private final CompletableFuture<LogicalSlot> logicalSlotFuture;
    +
    +		private SingleTaskSlot(
    +				SlotRequestId slotRequestId,
    +				AbstractID groupId,
    +				MultiTaskSlot parent,
    +				Locality locality) {
    +			super(slotRequestId, groupId);
    +
    +			this.parent = Preconditions.checkNotNull(parent);
    +
    +			Preconditions.checkNotNull(locality);
    +			logicalSlotFuture = parent.getSlotContextFuture()
    +				.thenApply(
    +					(SlotContext slotContext) ->
    +						new SingleLogicalSlot(
    +							slotRequestId,
    +							slotContext,
    +							slotSharingGroupId,
    +							locality,
    +							slotOwner));
    +		}
    +
    +		public CompletableFuture<LogicalSlot> getLogicalSlotFuture() {
    +			return logicalSlotFuture;
    +		}
    +
    +		@Override
    +		public boolean release(Throwable cause) {
    +			logicalSlotFuture.completeExceptionally(cause);
    +
    +			boolean pendingLogicalSlotRelease = false;
    +
    +			if (logicalSlotFuture.isDone() && !logicalSlotFuture.isCompletedExceptionally()) {
    +				// we have a single task slot which we first have to release
    +				final LogicalSlot logicalSlot = logicalSlotFuture.getNow(null);
    +
    +				if (logicalSlot != null && logicalSlot.isAlive()) {
    +					pendingLogicalSlotRelease = logicalSlot.releaseSlot(cause).isDone();
    +				}
    +			}
    +
    +			if (!pendingLogicalSlotRelease) {
    +				parent.releaseChild(getGroupId());
    +			}
    +
    +			return !pendingLogicalSlotRelease;
    +		}
    +	}
    +
    +	// ------------------------------------------------------------------------
    +	// Methods and classes for testing
    +	// ------------------------------------------------------------------------
    +
    +	/**
    +	 * Returns a collection of all resolved root slots.
    +	 *
    +	 * @return Collection of all resolved root slots
    +	 */
    +	@VisibleForTesting
    +	public Collection<MultiTaskSlot> getResolvedRootSlots() {
    +		ResolvedRootSlotValues vs = resolvedMultiTaskSlotValues;
    --- End diff --
    
    Yes this is better. Will change it.


---

[GitHub] flink pull request #5091: [FLINK-7956] [flip6] Add support for queued schedu...

Posted by GJL <gi...@git.apache.org>.
Github user GJL commented on a diff in the pull request:

    https://github.com/apache/flink/pull/5091#discussion_r155754738
  
    --- Diff: flink-runtime/src/main/java/org/apache/flink/runtime/jobmaster/slotpool/SlotPool.java ---
    @@ -266,104 +279,367 @@ public void disconnectResourceManager() {
     	// ------------------------------------------------------------------------
     
     	@Override
    -	public CompletableFuture<SimpleSlot> allocateSlot(
    -			SlotRequestID requestId,
    -			ScheduledUnit task,
    -			ResourceProfile resources,
    -			Iterable<TaskManagerLocation> locationPreferences,
    +	public CompletableFuture<LogicalSlot> allocateSlot(
    +			SlotRequestId slotRequestId,
    +			ScheduledUnit scheduledUnit,
    +			ResourceProfile resourceProfile,
    +			Collection<TaskManagerLocation> locationPreferences,
    +			boolean allowQueuedScheduling,
     			Time timeout) {
     
    -		return internalAllocateSlot(requestId, task, resources, locationPreferences);
    +		return internalAllocateSlot(
    +			slotRequestId,
    +			scheduledUnit,
    +			resourceProfile,
    +			locationPreferences,
    +			allowQueuedScheduling);
     	}
     
    -	@Override
    -	public void returnAllocatedSlot(Slot slot) {
    -		internalReturnAllocatedSlot(slot);
    +	private CompletableFuture<LogicalSlot> internalAllocateSlot(
    +			SlotRequestId slotRequestId,
    +			ScheduledUnit task,
    +			ResourceProfile resourceProfile,
    +			Collection<TaskManagerLocation> locationPreferences,
    +			boolean allowQueuedScheduling) {
    +
    +		final SlotSharingGroupId slotSharingGroupId = task.getSlotSharingGroupId();
    +
    +		if (slotSharingGroupId != null) {
    +			// allocate slot with slot sharing
    +			final SlotSharingManager multiTaskSlotManager = slotSharingManagers.computeIfAbsent(
    +				slotSharingGroupId,
    +				id -> new SlotSharingManager(
    +					id,
    +					this,
    +					providerAndOwner));
    +
    +			final SlotSharingManager.MultiTaskSlotLocality multiTaskSlotFuture;
    +
    +			try {
    +				if (task.getCoLocationConstraint() != null) {
    +					multiTaskSlotFuture = allocateCoLocatedMultiTaskSlot(
    +						task.getCoLocationConstraint(),
    +						multiTaskSlotManager,
    +						resourceProfile,
    +						locationPreferences,
    +						allowQueuedScheduling);
    +				} else {
    +					multiTaskSlotFuture = allocateMultiTaskSlot(
    +						task.getJobVertexId(), multiTaskSlotManager,
    +						resourceProfile,
    +						locationPreferences,
    +						allowQueuedScheduling);
    +				}
    +			} catch (NoResourceAvailableException noResourceException) {
    +				return FutureUtils.completedExceptionally(noResourceException);
    +			}
    +
    +			// sanity check
    +			Preconditions.checkState(!multiTaskSlotFuture.getMultiTaskSlot().contains(task.getJobVertexId()));
    +
    +			final SlotSharingManager.SingleTaskSlot leave = multiTaskSlotFuture.getMultiTaskSlot().allocateSingleTaskSlot(
    +				slotRequestId,
    +				task.getJobVertexId(),
    +				multiTaskSlotFuture.getLocality());
    +
    +			return leave.getLogicalSlotFuture();
    +		} else {
    +			// request an allocated slot to assign a single logical slot to
    +			CompletableFuture<SlotAndLocality> slotAndLocalityFuture = requestAllocatedSlot(
    +				slotRequestId,
    +				resourceProfile,
    +				locationPreferences,
    +				allowQueuedScheduling);
    +
    +			return slotAndLocalityFuture.thenApply(
    +				(SlotAndLocality slotAndLocality) -> {
    +					final AllocatedSlot allocatedSlot = slotAndLocality.getSlot();
    +
    +					final SingleLogicalSlot singleTaskSlot = new SingleLogicalSlot(
    +						slotRequestId,
    +						allocatedSlot,
    +						null,
    +						slotAndLocality.getLocality(),
    +						providerAndOwner);
    +
    +					if (allocatedSlot.tryAssignPayload(singleTaskSlot)) {
    +						return singleTaskSlot;
    +					} else {
    +						final FlinkException flinkException = new FlinkException("Could not assign payload to allocated slot " + allocatedSlot.getAllocationId() + '.');
    +						releaseSlot(slotRequestId, null, flinkException);
    +						throw new CompletionException(flinkException);
    +					}
    +				});
    +		}
     	}
     
    -	@Override
    -	public CompletableFuture<Acknowledge> cancelSlotAllocation(SlotRequestID requestId) {
    -		final PendingRequest pendingRequest = removePendingRequest(requestId);
    +	/**
    +	 * Allocates a co-located {@link SlotSharingManager.MultiTaskSlot} for the given {@link CoLocationConstraint}.
    +	 *
    +	 * <p>If allowQueuedScheduling is true, then the returned {@link SlotSharingManager.MultiTaskSlot} can be
    +	 * uncompleted.
    +	 *
    +	 * @param coLocationConstraint for which to allocate a {@link SlotSharingManager.MultiTaskSlot}
    +	 * @param multiTaskSlotManager responsible for the slot sharing group for which to allocate the slot
    +	 * @param resourceProfile specifying the requirements for the requested slot
    +	 * @param locationPreferences containing preferred TaskExecutors on which to allocate the slot
    +	 * @param allowQueuedScheduling true if queued scheduling (the returned task slot must not be completed yet) is allowed, otherwise false
    +	 * @return A {@link SlotSharingManager.MultiTaskSlotLocality} which contains the allocated{@link SlotSharingManager.MultiTaskSlot}
    +	 * 		and its locality wrt the given location preferences
    +	 * @throws NoResourceAvailableException if no task slot could be allocated
    +	 */
    +	private SlotSharingManager.MultiTaskSlotLocality allocateCoLocatedMultiTaskSlot(
    +			CoLocationConstraint coLocationConstraint,
    +			SlotSharingManager multiTaskSlotManager,
    +			ResourceProfile resourceProfile,
    +			Collection<TaskManagerLocation> locationPreferences,
    +			boolean allowQueuedScheduling) throws NoResourceAvailableException {
    +		final SlotRequestId coLocationSlotRequestId = coLocationConstraint.getSlotRequestId();
    +
    +		if (coLocationSlotRequestId != null) {
    +			// we have a slot assigned --> try to retrieve it
    +			final SlotSharingManager.TaskSlot taskSlot = multiTaskSlotManager.getTaskSlot(coLocationSlotRequestId);
    +
    +			if (taskSlot != null) {
    +				Preconditions.checkState(taskSlot instanceof SlotSharingManager.MultiTaskSlot);
    +				return SlotSharingManager.MultiTaskSlotLocality.of(((SlotSharingManager.MultiTaskSlot) taskSlot), Locality.LOCAL);
    +			} else {
    +				// the slot may have been cancelled in the mean time
    +				coLocationConstraint.setSlotRequestId(null);
    +			}
    +		}
     
    -		if (pendingRequest != null) {
    -			failPendingRequest(pendingRequest, new CancellationException("Allocation with request id" + requestId + " cancelled."));
    +		final Collection<TaskManagerLocation> actualLocationPreferences;
    +
    +		if (coLocationConstraint.isAssigned()) {
    +			actualLocationPreferences = Collections.singleton(coLocationConstraint.getLocation());
     		} else {
    -			final Slot slot = allocatedSlots.get(requestId);
    +			actualLocationPreferences = locationPreferences;
    +		}
    +
    +		// get a new multi task slot
    +		final SlotSharingManager.MultiTaskSlotLocality multiTaskSlotLocality = allocateMultiTaskSlot(
    +			coLocationConstraint.getGroupId(), multiTaskSlotManager,
    +			resourceProfile,
    +			actualLocationPreferences,
    +			allowQueuedScheduling);
    +
    +		// check whether we fulfill the co-location constraint
    +		if (coLocationConstraint.isAssigned() && multiTaskSlotLocality.getLocality() != Locality.LOCAL) {
    +			multiTaskSlotLocality.getMultiTaskSlot().release(
    +				new FlinkException("Multi task slot is not local and, thus, does not fulfill the co-location constraint."));
     
    -			if (slot != null) {
    -				LOG.info("Returning allocated slot {} because the corresponding allocation request {} was cancelled.", slot, requestId);
    -				if (slot.markCancelled()) {
    -					internalReturnAllocatedSlot(slot);
    +			throw new NoResourceAvailableException("Could not allocate a local multi task slot for the " +
    +				"co location constraint " + coLocationConstraint + '.');
    +		}
    +
    +		final SlotRequestId slotRequestId = new SlotRequestId();
    +		final SlotSharingManager.MultiTaskSlot coLocationSlot = multiTaskSlotLocality.getMultiTaskSlot().allocateMultiTaskSlot(
    +			slotRequestId,
    +			coLocationConstraint.getGroupId());
    +
    +		// mark the requested slot as co-located slot for other co-located tasks
    +		coLocationConstraint.setSlotRequestId(slotRequestId);
    +
    +		// lock the co-location constraint once we have obtained the allocated slot
    +		coLocationSlot.getSlotContextFuture().whenComplete(
    +			(SlotContext slotContext, Throwable throwable) -> {
    +				if (throwable == null) {
    +					// check whether we are still assigned to the co-location constraint
    +					if (Objects.equals(coLocationConstraint.getSlotRequestId(), slotRequestId)) {
    +						coLocationConstraint.lockLocation(slotContext.getTaskManagerLocation());
    +					}
     				}
    +			});
    +
    +		return SlotSharingManager.MultiTaskSlotLocality.of(coLocationSlot, multiTaskSlotLocality.getLocality());
    +	}
    +
    +	/**
    +	 * Allocates a {@link SlotSharingManager.MultiTaskSlot} for the given groupId which is in the
    +	 * slot sharing group for which the given {@link SlotSharingManager} is responsible.
    +	 *
    +	 * <p>If allowQueuedScheduling is true, then the method can return an uncompleted {@link SlotSharingManager.MultiTaskSlot}.
    +	 *
    +	 * @param groupId for which to allocate a new {@link SlotSharingManager.MultiTaskSlot}
    +	 * @param slotSharingManager responsible for the slot sharing group for which to allocate the slot
    +	 * @param resourceProfile specifying the requirements for the requested slot
    +	 * @param locationPreferences containing preferred TaskExecutors on which to allocate the slot
    +	 * @param allowQueuedScheduling true if queued scheduling (the returned task slot must not be completed yet) is allowed, otherwise false
    +	 * @return A {@link SlotSharingManager.MultiTaskSlotLocality} which contains the allocated {@link SlotSharingManager.MultiTaskSlot}
    +	 * 		and its locality wrt the given location preferences
    +	 * @throws NoResourceAvailableException if no task slot could be allocated
    +	 */
    +	private SlotSharingManager.MultiTaskSlotLocality allocateMultiTaskSlot(
    +			AbstractID groupId,
    +			SlotSharingManager slotSharingManager,
    +			ResourceProfile resourceProfile,
    +			Collection<TaskManagerLocation> locationPreferences,
    +			boolean allowQueuedScheduling) throws NoResourceAvailableException {
    +
    +		// check first whether we have a resolved root slot which we can use
    +		SlotSharingManager.MultiTaskSlotLocality multiTaskSlotLocality = slotSharingManager.getResolvedRootSlot(
    +			groupId,
    +			locationPreferences);
    +
    +		if (multiTaskSlotLocality != null && multiTaskSlotLocality.getLocality() == Locality.LOCAL) {
    +			return multiTaskSlotLocality;
    +		}
    +
    +		final SlotRequestId allocatedSlotRequestId = new SlotRequestId();
    +		final SlotRequestId multiTaskSlotRequestId = new SlotRequestId();
    +
    +		// check whether we have an allocated slot available which we can use to create a new multi task slot in
    +		final SlotAndLocality slotAndLocality = pollAndAllocateSlot(allocatedSlotRequestId, resourceProfile, locationPreferences);
    +
    +		if (slotAndLocality != null && (slotAndLocality.getLocality() == Locality.LOCAL || multiTaskSlotLocality == null)) {
    +
    +			final AllocatedSlot allocatedSlot = slotAndLocality.getSlot();
    +			final SlotSharingManager.MultiTaskSlot multiTaskSlot = slotSharingManager.createRootSlot(
    +				multiTaskSlotRequestId,
    +				CompletableFuture.completedFuture(slotAndLocality.getSlot()),
    +				allocatedSlotRequestId);
    +
    +			if (allocatedSlot.tryAssignPayload(multiTaskSlot)) {
    +				return SlotSharingManager.MultiTaskSlotLocality.of(multiTaskSlot, slotAndLocality.getLocality());
     			} else {
    -				LOG.debug("There was no slot allocation with {} to be cancelled.", requestId);
    +				multiTaskSlot.release(new FlinkException("Could not assign payload to allocated slot " +
    +					allocatedSlot.getAllocationId() + '.'));
     			}
     		}
     
    -		return CompletableFuture.completedFuture(Acknowledge.get());
    -	}
    +		if (multiTaskSlotLocality != null) {
    +			// prefer slot sharing group slots over unused slots
    +			if (slotAndLocality != null) {
    +				releaseSlot(
    +					allocatedSlotRequestId,
    +					null,
    +					new FlinkException("Locality constraint is not better fulfilled by allocated slot."));
    +			}
    +			return multiTaskSlotLocality;
    +		}
     
    -	CompletableFuture<SimpleSlot> internalAllocateSlot(
    -			SlotRequestID requestId,
    -			ScheduledUnit task,
    -			ResourceProfile resources,
    -			Iterable<TaskManagerLocation> locationPreferences) {
    +		if (allowQueuedScheduling) {
    +			// there is no slot immediately available --> check first for uncompleted slots at the slot sharing group
    +			SlotSharingManager.MultiTaskSlot multiTaskSlotFuture = slotSharingManager.getUnresolvedRootSlot(groupId);
    +
    +			if (multiTaskSlotFuture == null) {
    +				// it seems as if we have to request a new slot from the resource manager, this is always the last resort!!!
    +				final CompletableFuture<AllocatedSlot> futureSlot = requestNewAllocatedSlot(allocatedSlotRequestId, resourceProfile);
    +
    +				multiTaskSlotFuture = slotSharingManager.createRootSlot(
    +					multiTaskSlotRequestId,
    +					futureSlot.thenApply(Function.identity()),
    --- End diff --
    
    nit: If you change the signature to
    ```
    public MultiTaskSlot createRootSlot(
    			SlotRequestId slotRequestId,
    			CompletableFuture<? extends SlotContext> slotContextFuture,
    			SlotRequestId allocatedSlotRequestId) 
    ```
    you won't need this trick to satisfy the compiler (PECS rule). Unfortunately more changes in the code would be needed, e.g., in `MultiTaskSlot`.


---

[GitHub] flink pull request #5091: [FLINK-7956] [flip6] Add support for queued schedu...

Posted by GJL <gi...@git.apache.org>.
Github user GJL commented on a diff in the pull request:

    https://github.com/apache/flink/pull/5091#discussion_r155520946
  
    --- Diff: flink-runtime/src/main/java/org/apache/flink/runtime/jobmaster/slotpool/SlotSharingManager.java ---
    @@ -0,0 +1,722 @@
    +/*
    + * Licensed to the Apache Software Foundation (ASF) under one
    + * or more contributor license agreements.  See the NOTICE file
    + * distributed with this work for additional information
    + * regarding copyright ownership.  The ASF licenses this file
    + * to you under the Apache License, Version 2.0 (the
    + * "License"); you may not use this file except in compliance
    + * with the License.  You may obtain a copy of the License at
    + *
    + *     http://www.apache.org/licenses/LICENSE-2.0
    + *
    + * Unless required by applicable law or agreed to in writing, software
    + * distributed under the License is distributed on an "AS IS" BASIS,
    + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    + * See the License for the specific language governing permissions and
    + * limitations under the License.
    + */
    +
    +package org.apache.flink.runtime.jobmaster.slotpool;
    +
    +import org.apache.flink.annotation.VisibleForTesting;
    +import org.apache.flink.runtime.jobmaster.LogicalSlot;
    +import org.apache.flink.runtime.jobmaster.SlotContext;
    +import org.apache.flink.runtime.jobmaster.SlotOwner;
    +import org.apache.flink.runtime.jobmaster.SlotRequestId;
    +import org.apache.flink.runtime.instance.SlotSharingGroupId;
    +import org.apache.flink.runtime.jobmanager.scheduler.Locality;
    +import org.apache.flink.runtime.taskmanager.TaskManagerLocation;
    +import org.apache.flink.util.AbstractID;
    +import org.apache.flink.util.FlinkException;
    +import org.apache.flink.util.Preconditions;
    +
    +import javax.annotation.Nullable;
    +
    +import java.util.AbstractCollection;
    +import java.util.Collection;
    +import java.util.Collections;
    +import java.util.HashMap;
    +import java.util.HashSet;
    +import java.util.Iterator;
    +import java.util.Map;
    +import java.util.Objects;
    +import java.util.Set;
    +import java.util.concurrent.CompletableFuture;
    +
    +/**
    + * Manager which is responsible for slot sharing. Slot sharing allows to run different
    + * tasks in the same slot and to realize co-location constraints.
    + *
    + * <p>The SlotSharingManager allows to create a hierarchy of {@link TaskSlot} such that
    + * every {@link TaskSlot} is uniquely identified by a {@link SlotRequestId} identifying
    + * the request for the TaskSlot and a {@link AbstractID} identifying the task or the
    + * co-location constraint running in this slot.
    + *
    + * <p>The {@link TaskSlot} hierarchy is implemented by {@link MultiTaskSlot} and
    + * {@link SingleTaskSlot}. The former class represents inner nodes which can contain
    + * a number of other {@link TaskSlot} and the latter class represents the leave nodes.
    + * The hierarchy starts with a root {@link MultiTaskSlot} which is a future
    + * {@link SlotContext} assigned. The {@link SlotContext} represents the allocated slot
    + * on the TaskExecutor in which all slots of this hierarchy run. A {@link MultiTaskSlot}
    + * can be assigned multiple {@link SingleTaskSlot} or {@link MultiTaskSlot} if and only if
    + * the task slot does not yet contain another child with the same {@link AbstractID} identifying
    + * the actual task or the co-location constraint.
    + *
    + * <p>Normal slot sharing is represented by a root {@link MultiTaskSlot} which contains a set
    + * of {@link SingleTaskSlot} on the second layer. Each {@link SingleTaskSlot} represents a different
    + * task.
    + *
    + * <p>Co-location constraints are modeled by adding a {@link MultiTaskSlot} to the root node. The co-location
    + * constraint is uniquely identified by a {@link AbstractID} such that we cannot add a second co-located
    + * {@link MultiTaskSlot} to the same root node. Now all co-located tasks will be added to co-located
    + * multi task slot.
    + */
    +public class SlotSharingManager {
    +
    +	private final SlotSharingGroupId slotSharingGroupId;
    +
    +	// needed to release allocated slots after a complete multi task slot hierarchy has been released
    --- End diff --
    
    nit: All fields are commented with non-javadoc comments. Normally comments on fields are also done in Javadoc style, e.g., `SlotPool`. Javadoc comments on fields are displayed by IntelliJ (`Ctrl + J`).


---

[GitHub] flink pull request #5091: [FLINK-7956] [flip6] Add support for queued schedu...

Posted by GJL <gi...@git.apache.org>.
Github user GJL commented on a diff in the pull request:

    https://github.com/apache/flink/pull/5091#discussion_r155503866
  
    --- Diff: flink-runtime/src/test/java/org/apache/flink/runtime/jobmanager/scheduler/SchedulerTest.java ---
    @@ -0,0 +1,97 @@
    +/*
    + * Licensed to the Apache Software Foundation (ASF) under one
    + * or more contributor license agreements.  See the NOTICE file
    + * distributed with this work for additional information
    + * regarding copyright ownership.  The ASF licenses this file
    + * to you under the Apache License, Version 2.0 (the
    + * "License"); you may not use this file except in compliance
    + * with the License.  You may obtain a copy of the License at
    + *
    + *     http://www.apache.org/licenses/LICENSE-2.0
    + *
    + * Unless required by applicable law or agreed to in writing, software
    + * distributed under the License is distributed on an "AS IS" BASIS,
    + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    + * See the License for the specific language governing permissions and
    + * limitations under the License.
    + */
    +
    +package org.apache.flink.runtime.jobmanager.scheduler;
    +
    +import org.apache.flink.runtime.instance.Instance;
    +import org.apache.flink.runtime.testingUtils.TestingUtils;
    +import org.apache.flink.util.TestLogger;
    +
    +import org.junit.Test;
    +
    +import static org.apache.flink.runtime.jobmanager.scheduler.SchedulerTestUtils.getRandomInstance;
    +import static org.junit.Assert.assertEquals;
    +import static org.junit.Assert.assertFalse;
    +import static org.junit.Assert.fail;
    +
    +public class SchedulerTest extends TestLogger {
    +
    +	@Test
    +	public void testAddAndRemoveInstance() {
    +		try {
    +			Scheduler scheduler = new Scheduler(TestingUtils.defaultExecutionContext());
    +
    +			Instance i1 = getRandomInstance(2);
    +			Instance i2 = getRandomInstance(2);
    +			Instance i3 = getRandomInstance(2);
    +
    +			assertEquals(0, scheduler.getNumberOfAvailableInstances());
    +			assertEquals(0, scheduler.getNumberOfAvailableSlots());
    +			scheduler.newInstanceAvailable(i1);
    +			assertEquals(1, scheduler.getNumberOfAvailableInstances());
    +			assertEquals(2, scheduler.getNumberOfAvailableSlots());
    +			scheduler.newInstanceAvailable(i2);
    +			assertEquals(2, scheduler.getNumberOfAvailableInstances());
    +			assertEquals(4, scheduler.getNumberOfAvailableSlots());
    +			scheduler.newInstanceAvailable(i3);
    +			assertEquals(3, scheduler.getNumberOfAvailableInstances());
    +			assertEquals(6, scheduler.getNumberOfAvailableSlots());
    +
    +			// cannot add available instance again
    +			try {
    +				scheduler.newInstanceAvailable(i2);
    +				fail("Scheduler accepted instance twice");
    +			}
    +			catch (IllegalArgumentException e) {
    +				// bueno!
    +			}
    +
    +			// some instances die
    +			assertEquals(3, scheduler.getNumberOfAvailableInstances());
    +			assertEquals(6, scheduler.getNumberOfAvailableSlots());
    +			scheduler.instanceDied(i2);
    +			assertEquals(2, scheduler.getNumberOfAvailableInstances());
    +			assertEquals(4, scheduler.getNumberOfAvailableSlots());
    +
    +			// try to add a dead instance
    +			try {
    +				scheduler.newInstanceAvailable(i2);
    +				fail("Scheduler accepted dead instance");
    +			}
    +			catch (IllegalArgumentException e) {
    +				// stimmt
    --- End diff --
    
    😃 


---

[GitHub] flink pull request #5091: [FLINK-7956] [flip6] Add support for queued schedu...

Posted by tillrohrmann <gi...@git.apache.org>.
Github user tillrohrmann commented on a diff in the pull request:

    https://github.com/apache/flink/pull/5091#discussion_r156902613
  
    --- Diff: flink-runtime/src/test/java/org/apache/flink/runtime/jobmaster/slotpool/SlotSharingManagerTest.java ---
    @@ -0,0 +1,502 @@
    +/*
    + * Licensed to the Apache Software Foundation (ASF) under one
    + * or more contributor license agreements.  See the NOTICE file
    + * distributed with this work for additional information
    + * regarding copyright ownership.  The ASF licenses this file
    + * to you under the Apache License, Version 2.0 (the
    + * "License"); you may not use this file except in compliance
    + * with the License.  You may obtain a copy of the License at
    + *
    + *     http://www.apache.org/licenses/LICENSE-2.0
    + *
    + * Unless required by applicable law or agreed to in writing, software
    + * distributed under the License is distributed on an "AS IS" BASIS,
    + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    + * See the License for the specific language governing permissions and
    + * limitations under the License.
    + */
    +
    +package org.apache.flink.runtime.jobmaster.slotpool;
    +
    +import org.apache.flink.runtime.clusterframework.types.AllocationID;
    +import org.apache.flink.runtime.executiongraph.utils.SimpleAckingTaskManagerGateway;
    +import org.apache.flink.runtime.instance.SimpleSlotContext;
    +import org.apache.flink.runtime.instance.SlotSharingGroupId;
    +import org.apache.flink.runtime.jobmanager.scheduler.Locality;
    +import org.apache.flink.runtime.jobmanager.slots.DummySlotOwner;
    +import org.apache.flink.runtime.jobmaster.LogicalSlot;
    +import org.apache.flink.runtime.jobmaster.SlotContext;
    +import org.apache.flink.runtime.jobmaster.SlotRequestId;
    +import org.apache.flink.runtime.taskmanager.LocalTaskManagerLocation;
    +import org.apache.flink.util.AbstractID;
    +import org.apache.flink.util.FlinkException;
    +import org.apache.flink.util.TestLogger;
    +
    +import org.junit.Test;
    +
    +import java.util.Collections;
    +import java.util.Objects;
    +import java.util.concurrent.CompletableFuture;
    +import java.util.concurrent.ExecutionException;
    +
    +import static org.junit.Assert.assertEquals;
    +import static org.junit.Assert.assertFalse;
    +import static org.junit.Assert.assertNotNull;
    +import static org.junit.Assert.assertNull;
    +import static org.junit.Assert.assertTrue;
    +
    +/**
    + * Test cases for the {@link SlotSharingManager}.
    + */
    +public class SlotSharingManagerTest extends TestLogger {
    +
    +	private static final SlotSharingGroupId slotSharingGroupId = new SlotSharingGroupId();
    +
    +	private static final DummySlotOwner slotOwner = new DummySlotOwner();
    +
    +	private static final TestingAllocatedSlotActions allocatedSlotActions = new TestingAllocatedSlotActions();
    +
    +	@Test
    +	public void testRootSlotCreation() {
    +		final SlotSharingManager slotSharingManager = new SlotSharingManager(
    +			slotSharingGroupId,
    +			allocatedSlotActions,
    +			slotOwner);
    +
    +		SlotRequestId slotRequestId = new SlotRequestId();
    +		SlotRequestId allocatedSlotRequestId = new SlotRequestId();
    +
    +		final SlotSharingManager.MultiTaskSlot multiTaskSlot = slotSharingManager.createRootSlot(
    +			slotRequestId,
    +			new CompletableFuture<>(),
    +			allocatedSlotRequestId);
    +
    +		assertEquals(slotRequestId, multiTaskSlot.getSlotRequestId());
    +		assertNotNull(slotSharingManager.getTaskSlot(slotRequestId));
    +	}
    +
    +	@Test
    +	public void testRootSlotRelease() throws ExecutionException, InterruptedException {
    +		final CompletableFuture<SlotRequestId> slotReleasedFuture = new CompletableFuture<>();
    +		final TestingAllocatedSlotActions testingAllocatedSlotActions = new TestingAllocatedSlotActions();
    --- End diff --
    
    Indeed. Will change it.


---

[GitHub] flink pull request #5091: [FLINK-7956] [flip6] Add support for queued schedu...

Posted by ifndef-SleePy <gi...@git.apache.org>.
Github user ifndef-SleePy commented on a diff in the pull request:

    https://github.com/apache/flink/pull/5091#discussion_r154871284
  
    --- Diff: flink-runtime/src/main/java/org/apache/flink/runtime/jobmanager/scheduler/ScheduledUnit.java ---
    @@ -19,68 +19,104 @@
     package org.apache.flink.runtime.jobmanager.scheduler;
     
     import org.apache.flink.runtime.executiongraph.Execution;
    +import org.apache.flink.runtime.instance.SlotSharingGroupId;
     import org.apache.flink.runtime.jobgraph.JobVertexID;
     import org.apache.flink.util.Preconditions;
     
    +import javax.annotation.Nullable;
    +
     public class ScheduledUnit {
    -	
    +
    +	@Nullable
     	private final Execution vertexExecution;
    -	
    -	private final SlotSharingGroup sharingGroup;
    -	
    -	private final CoLocationConstraint locationConstraint;
    +
    +	private final JobVertexID jobVertexId;
    +
    +	@Nullable
    +	private final SlotSharingGroupId slotSharingGroupId;
    +
    +	@Nullable
    +	private final CoLocationConstraint coLocationConstraint;
     	
     	// --------------------------------------------------------------------------------------------
     	
     	public ScheduledUnit(Execution task) {
    -		Preconditions.checkNotNull(task);
    -		
    -		this.vertexExecution = task;
    -		this.sharingGroup = null;
    -		this.locationConstraint = null;
    +		this(
    +			Preconditions.checkNotNull(task),
    +			task.getVertex().getJobvertexId(),
    +			null,
    +			null);
     	}
     	
    -	public ScheduledUnit(Execution task, SlotSharingGroup sharingUnit) {
    -		Preconditions.checkNotNull(task);
    -		
    -		this.vertexExecution = task;
    -		this.sharingGroup = sharingUnit;
    -		this.locationConstraint = null;
    +	public ScheduledUnit(Execution task, SlotSharingGroupId slotSharingGroupId) {
    +		this(
    +			Preconditions.checkNotNull(task),
    +			task.getVertex().getJobvertexId(),
    +			slotSharingGroupId,
    +			null);
     	}
     	
    -	public ScheduledUnit(Execution task, SlotSharingGroup sharingUnit, CoLocationConstraint locationConstraint) {
    -		Preconditions.checkNotNull(task);
    -		Preconditions.checkNotNull(sharingUnit);
    -		Preconditions.checkNotNull(locationConstraint);
    -		
    +	public ScheduledUnit(
    +			Execution task,
    +			SlotSharingGroupId slotSharingGroupId,
    +			CoLocationConstraint coLocationConstraint) {
    +		this(
    +			Preconditions.checkNotNull(task),
    +			task.getVertex().getJobvertexId(),
    +			slotSharingGroupId,
    +			coLocationConstraint);
    +	}
    +
    +	public ScheduledUnit(
    +			JobVertexID jobVertexId,
    +			SlotSharingGroupId slotSharingGroupId,
    +			CoLocationConstraint coLocationConstraint) {
    +		this(
    +			null,
    +			jobVertexId,
    +			slotSharingGroupId,
    +			coLocationConstraint);
    +	}
    +
    +	public ScheduledUnit(
    +		Execution task,
    +		JobVertexID jobVertexId,
    --- End diff --
    
    We can get JobVertexID from Execution. Do we need this in Constructor?


---

[GitHub] flink pull request #5091: [FLINK-7956] [flip6] Add support for queued schedu...

Posted by ifndef-SleePy <gi...@git.apache.org>.
Github user ifndef-SleePy commented on a diff in the pull request:

    https://github.com/apache/flink/pull/5091#discussion_r156621784
  
    --- Diff: flink-runtime/src/main/java/org/apache/flink/runtime/jobmaster/slotpool/SlotPool.java ---
    @@ -266,104 +279,367 @@ public void disconnectResourceManager() {
     	// ------------------------------------------------------------------------
     
     	@Override
    -	public CompletableFuture<SimpleSlot> allocateSlot(
    -			SlotRequestID requestId,
    -			ScheduledUnit task,
    -			ResourceProfile resources,
    -			Iterable<TaskManagerLocation> locationPreferences,
    +	public CompletableFuture<LogicalSlot> allocateSlot(
    +			SlotRequestId slotRequestId,
    +			ScheduledUnit scheduledUnit,
    +			ResourceProfile resourceProfile,
    +			Collection<TaskManagerLocation> locationPreferences,
    +			boolean allowQueuedScheduling,
     			Time timeout) {
     
    -		return internalAllocateSlot(requestId, task, resources, locationPreferences);
    +		return internalAllocateSlot(
    +			slotRequestId,
    +			scheduledUnit,
    +			resourceProfile,
    +			locationPreferences,
    +			allowQueuedScheduling);
     	}
     
    -	@Override
    -	public void returnAllocatedSlot(Slot slot) {
    -		internalReturnAllocatedSlot(slot);
    +	private CompletableFuture<LogicalSlot> internalAllocateSlot(
    +			SlotRequestId slotRequestId,
    +			ScheduledUnit task,
    +			ResourceProfile resourceProfile,
    +			Collection<TaskManagerLocation> locationPreferences,
    +			boolean allowQueuedScheduling) {
    +
    +		final SlotSharingGroupId slotSharingGroupId = task.getSlotSharingGroupId();
    +
    +		if (slotSharingGroupId != null) {
    +			// allocate slot with slot sharing
    +			final SlotSharingManager multiTaskSlotManager = slotSharingManagers.computeIfAbsent(
    +				slotSharingGroupId,
    +				id -> new SlotSharingManager(
    +					id,
    +					this,
    +					providerAndOwner));
    +
    +			final SlotSharingManager.MultiTaskSlotLocality multiTaskSlotFuture;
    +
    +			try {
    +				if (task.getCoLocationConstraint() != null) {
    +					multiTaskSlotFuture = allocateCoLocatedMultiTaskSlot(
    +						task.getCoLocationConstraint(),
    +						multiTaskSlotManager,
    +						resourceProfile,
    +						locationPreferences,
    +						allowQueuedScheduling);
    +				} else {
    +					multiTaskSlotFuture = allocateMultiTaskSlot(
    +						task.getJobVertexId(), multiTaskSlotManager,
    +						resourceProfile,
    +						locationPreferences,
    +						allowQueuedScheduling);
    +				}
    +			} catch (NoResourceAvailableException noResourceException) {
    +				return FutureUtils.completedExceptionally(noResourceException);
    +			}
    +
    +			// sanity check
    +			Preconditions.checkState(!multiTaskSlotFuture.getMultiTaskSlot().contains(task.getJobVertexId()));
    +
    +			final SlotSharingManager.SingleTaskSlot leave = multiTaskSlotFuture.getMultiTaskSlot().allocateSingleTaskSlot(
    +				slotRequestId,
    +				task.getJobVertexId(),
    +				multiTaskSlotFuture.getLocality());
    +
    +			return leave.getLogicalSlotFuture();
    +		} else {
    +			// request an allocated slot to assign a single logical slot to
    +			CompletableFuture<SlotAndLocality> slotAndLocalityFuture = requestAllocatedSlot(
    +				slotRequestId,
    +				resourceProfile,
    +				locationPreferences,
    +				allowQueuedScheduling);
    +
    +			return slotAndLocalityFuture.thenApply(
    +				(SlotAndLocality slotAndLocality) -> {
    +					final AllocatedSlot allocatedSlot = slotAndLocality.getSlot();
    +
    +					final SingleLogicalSlot singleTaskSlot = new SingleLogicalSlot(
    +						slotRequestId,
    +						allocatedSlot,
    +						null,
    +						slotAndLocality.getLocality(),
    +						providerAndOwner);
    +
    +					if (allocatedSlot.tryAssignPayload(singleTaskSlot)) {
    +						return singleTaskSlot;
    +					} else {
    +						final FlinkException flinkException = new FlinkException("Could not assign payload to allocated slot " + allocatedSlot.getAllocationId() + '.');
    +						releaseSlot(slotRequestId, null, flinkException);
    +						throw new CompletionException(flinkException);
    +					}
    +				});
    +		}
     	}
     
    -	@Override
    -	public CompletableFuture<Acknowledge> cancelSlotAllocation(SlotRequestID requestId) {
    -		final PendingRequest pendingRequest = removePendingRequest(requestId);
    +	/**
    +	 * Allocates a co-located {@link SlotSharingManager.MultiTaskSlot} for the given {@link CoLocationConstraint}.
    +	 *
    +	 * <p>If allowQueuedScheduling is true, then the returned {@link SlotSharingManager.MultiTaskSlot} can be
    +	 * uncompleted.
    +	 *
    +	 * @param coLocationConstraint for which to allocate a {@link SlotSharingManager.MultiTaskSlot}
    +	 * @param multiTaskSlotManager responsible for the slot sharing group for which to allocate the slot
    +	 * @param resourceProfile specifying the requirements for the requested slot
    +	 * @param locationPreferences containing preferred TaskExecutors on which to allocate the slot
    +	 * @param allowQueuedScheduling true if queued scheduling (the returned task slot must not be completed yet) is allowed, otherwise false
    +	 * @return A {@link SlotSharingManager.MultiTaskSlotLocality} which contains the allocated{@link SlotSharingManager.MultiTaskSlot}
    +	 * 		and its locality wrt the given location preferences
    +	 * @throws NoResourceAvailableException if no task slot could be allocated
    +	 */
    +	private SlotSharingManager.MultiTaskSlotLocality allocateCoLocatedMultiTaskSlot(
    +			CoLocationConstraint coLocationConstraint,
    +			SlotSharingManager multiTaskSlotManager,
    +			ResourceProfile resourceProfile,
    +			Collection<TaskManagerLocation> locationPreferences,
    +			boolean allowQueuedScheduling) throws NoResourceAvailableException {
    +		final SlotRequestId coLocationSlotRequestId = coLocationConstraint.getSlotRequestId();
    +
    +		if (coLocationSlotRequestId != null) {
    +			// we have a slot assigned --> try to retrieve it
    +			final SlotSharingManager.TaskSlot taskSlot = multiTaskSlotManager.getTaskSlot(coLocationSlotRequestId);
    +
    +			if (taskSlot != null) {
    +				Preconditions.checkState(taskSlot instanceof SlotSharingManager.MultiTaskSlot);
    +				return SlotSharingManager.MultiTaskSlotLocality.of(((SlotSharingManager.MultiTaskSlot) taskSlot), Locality.LOCAL);
    +			} else {
    +				// the slot may have been cancelled in the mean time
    +				coLocationConstraint.setSlotRequestId(null);
    +			}
    +		}
     
    -		if (pendingRequest != null) {
    -			failPendingRequest(pendingRequest, new CancellationException("Allocation with request id" + requestId + " cancelled."));
    +		final Collection<TaskManagerLocation> actualLocationPreferences;
    +
    +		if (coLocationConstraint.isAssigned()) {
    +			actualLocationPreferences = Collections.singleton(coLocationConstraint.getLocation());
     		} else {
    -			final Slot slot = allocatedSlots.get(requestId);
    +			actualLocationPreferences = locationPreferences;
    +		}
    +
    +		// get a new multi task slot
    +		final SlotSharingManager.MultiTaskSlotLocality multiTaskSlotLocality = allocateMultiTaskSlot(
    +			coLocationConstraint.getGroupId(), multiTaskSlotManager,
    +			resourceProfile,
    +			actualLocationPreferences,
    +			allowQueuedScheduling);
    +
    +		// check whether we fulfill the co-location constraint
    +		if (coLocationConstraint.isAssigned() && multiTaskSlotLocality.getLocality() != Locality.LOCAL) {
    +			multiTaskSlotLocality.getMultiTaskSlot().release(
    +				new FlinkException("Multi task slot is not local and, thus, does not fulfill the co-location constraint."));
     
    -			if (slot != null) {
    -				LOG.info("Returning allocated slot {} because the corresponding allocation request {} was cancelled.", slot, requestId);
    -				if (slot.markCancelled()) {
    -					internalReturnAllocatedSlot(slot);
    +			throw new NoResourceAvailableException("Could not allocate a local multi task slot for the " +
    +				"co location constraint " + coLocationConstraint + '.');
    +		}
    +
    +		final SlotRequestId slotRequestId = new SlotRequestId();
    +		final SlotSharingManager.MultiTaskSlot coLocationSlot = multiTaskSlotLocality.getMultiTaskSlot().allocateMultiTaskSlot(
    +			slotRequestId,
    +			coLocationConstraint.getGroupId());
    +
    +		// mark the requested slot as co-located slot for other co-located tasks
    +		coLocationConstraint.setSlotRequestId(slotRequestId);
    +
    +		// lock the co-location constraint once we have obtained the allocated slot
    +		coLocationSlot.getSlotContextFuture().whenComplete(
    +			(SlotContext slotContext, Throwable throwable) -> {
    +				if (throwable == null) {
    +					// check whether we are still assigned to the co-location constraint
    +					if (Objects.equals(coLocationConstraint.getSlotRequestId(), slotRequestId)) {
    +						coLocationConstraint.lockLocation(slotContext.getTaskManagerLocation());
    +					}
     				}
    +			});
    +
    +		return SlotSharingManager.MultiTaskSlotLocality.of(coLocationSlot, multiTaskSlotLocality.getLocality());
    +	}
    +
    +	/**
    +	 * Allocates a {@link SlotSharingManager.MultiTaskSlot} for the given groupId which is in the
    +	 * slot sharing group for which the given {@link SlotSharingManager} is responsible.
    +	 *
    +	 * <p>If allowQueuedScheduling is true, then the method can return an uncompleted {@link SlotSharingManager.MultiTaskSlot}.
    +	 *
    +	 * @param groupId for which to allocate a new {@link SlotSharingManager.MultiTaskSlot}
    +	 * @param slotSharingManager responsible for the slot sharing group for which to allocate the slot
    +	 * @param resourceProfile specifying the requirements for the requested slot
    +	 * @param locationPreferences containing preferred TaskExecutors on which to allocate the slot
    +	 * @param allowQueuedScheduling true if queued scheduling (the returned task slot must not be completed yet) is allowed, otherwise false
    +	 * @return A {@link SlotSharingManager.MultiTaskSlotLocality} which contains the allocated {@link SlotSharingManager.MultiTaskSlot}
    +	 * 		and its locality wrt the given location preferences
    +	 * @throws NoResourceAvailableException if no task slot could be allocated
    +	 */
    +	private SlotSharingManager.MultiTaskSlotLocality allocateMultiTaskSlot(
    +			AbstractID groupId,
    +			SlotSharingManager slotSharingManager,
    +			ResourceProfile resourceProfile,
    +			Collection<TaskManagerLocation> locationPreferences,
    +			boolean allowQueuedScheduling) throws NoResourceAvailableException {
    +
    +		// check first whether we have a resolved root slot which we can use
    +		SlotSharingManager.MultiTaskSlotLocality multiTaskSlotLocality = slotSharingManager.getResolvedRootSlot(
    +			groupId,
    +			locationPreferences);
    +
    +		if (multiTaskSlotLocality != null && multiTaskSlotLocality.getLocality() == Locality.LOCAL) {
    +			return multiTaskSlotLocality;
    +		}
    +
    +		final SlotRequestId allocatedSlotRequestId = new SlotRequestId();
    +		final SlotRequestId multiTaskSlotRequestId = new SlotRequestId();
    +
    +		// check whether we have an allocated slot available which we can use to create a new multi task slot in
    +		final SlotAndLocality slotAndLocality = pollAndAllocateSlot(allocatedSlotRequestId, resourceProfile, locationPreferences);
    +
    +		if (slotAndLocality != null && (slotAndLocality.getLocality() == Locality.LOCAL || multiTaskSlotLocality == null)) {
    +
    +			final AllocatedSlot allocatedSlot = slotAndLocality.getSlot();
    +			final SlotSharingManager.MultiTaskSlot multiTaskSlot = slotSharingManager.createRootSlot(
    +				multiTaskSlotRequestId,
    +				CompletableFuture.completedFuture(slotAndLocality.getSlot()),
    +				allocatedSlotRequestId);
    +
    +			if (allocatedSlot.tryAssignPayload(multiTaskSlot)) {
    +				return SlotSharingManager.MultiTaskSlotLocality.of(multiTaskSlot, slotAndLocality.getLocality());
     			} else {
    -				LOG.debug("There was no slot allocation with {} to be cancelled.", requestId);
    +				multiTaskSlot.release(new FlinkException("Could not assign payload to allocated slot " +
    +					allocatedSlot.getAllocationId() + '.'));
     			}
     		}
     
    -		return CompletableFuture.completedFuture(Acknowledge.get());
    -	}
    +		if (multiTaskSlotLocality != null) {
    +			// prefer slot sharing group slots over unused slots
    +			if (slotAndLocality != null) {
    +				releaseSlot(
    +					allocatedSlotRequestId,
    +					null,
    +					new FlinkException("Locality constraint is not better fulfilled by allocated slot."));
    +			}
    +			return multiTaskSlotLocality;
    --- End diff --
    
    If multiTaskSlotLocality != null and multiTaskSlotLocality.getLocality() != LOCAL and slotAndLocality == null
    It will return multiTaskSlotLocality without LOCAL locality. Is this expectable?


---

[GitHub] flink pull request #5091: [FLINK-7956] [flip6] Add support for queued schedu...

Posted by tillrohrmann <gi...@git.apache.org>.
Github user tillrohrmann commented on a diff in the pull request:

    https://github.com/apache/flink/pull/5091#discussion_r156903740
  
    --- Diff: flink-runtime/src/main/java/org/apache/flink/runtime/jobmanager/scheduler/ScheduledUnit.java ---
    @@ -19,68 +19,104 @@
     package org.apache.flink.runtime.jobmanager.scheduler;
     
     import org.apache.flink.runtime.executiongraph.Execution;
    +import org.apache.flink.runtime.instance.SlotSharingGroupId;
     import org.apache.flink.runtime.jobgraph.JobVertexID;
     import org.apache.flink.util.Preconditions;
     
    +import javax.annotation.Nullable;
    +
     public class ScheduledUnit {
    -	
    +
    +	@Nullable
     	private final Execution vertexExecution;
    -	
    -	private final SlotSharingGroup sharingGroup;
    -	
    -	private final CoLocationConstraint locationConstraint;
    +
    +	private final JobVertexID jobVertexId;
    +
    +	@Nullable
    +	private final SlotSharingGroupId slotSharingGroupId;
    +
    +	@Nullable
    +	private final CoLocationConstraint coLocationConstraint;
     	
     	// --------------------------------------------------------------------------------------------
     	
     	public ScheduledUnit(Execution task) {
    -		Preconditions.checkNotNull(task);
    -		
    -		this.vertexExecution = task;
    -		this.sharingGroup = null;
    -		this.locationConstraint = null;
    +		this(
    +			Preconditions.checkNotNull(task),
    +			task.getVertex().getJobvertexId(),
    +			null,
    +			null);
     	}
     	
    -	public ScheduledUnit(Execution task, SlotSharingGroup sharingUnit) {
    -		Preconditions.checkNotNull(task);
    -		
    -		this.vertexExecution = task;
    -		this.sharingGroup = sharingUnit;
    -		this.locationConstraint = null;
    +	public ScheduledUnit(Execution task, SlotSharingGroupId slotSharingGroupId) {
    +		this(
    +			Preconditions.checkNotNull(task),
    +			task.getVertex().getJobvertexId(),
    +			slotSharingGroupId,
    +			null);
     	}
     	
    -	public ScheduledUnit(Execution task, SlotSharingGroup sharingUnit, CoLocationConstraint locationConstraint) {
    -		Preconditions.checkNotNull(task);
    -		Preconditions.checkNotNull(sharingUnit);
    -		Preconditions.checkNotNull(locationConstraint);
    -		
    +	public ScheduledUnit(
    +			Execution task,
    +			SlotSharingGroupId slotSharingGroupId,
    +			CoLocationConstraint coLocationConstraint) {
    +		this(
    +			Preconditions.checkNotNull(task),
    +			task.getVertex().getJobvertexId(),
    +			slotSharingGroupId,
    +			coLocationConstraint);
    +	}
    +
    +	public ScheduledUnit(
    +			JobVertexID jobVertexId,
    +			SlotSharingGroupId slotSharingGroupId,
    +			CoLocationConstraint coLocationConstraint) {
    +		this(
    +			null,
    +			jobVertexId,
    +			slotSharingGroupId,
    +			coLocationConstraint);
    +	}
    +
    +	public ScheduledUnit(
    +		Execution task,
    +		JobVertexID jobVertexId,
    --- End diff --
    
    Yes because `task` can be null. Will add the missing `@Nullable` annotation.


---

[GitHub] flink pull request #5091: [FLINK-7956] [flip6] Add support for queued schedu...

Posted by asfgit <gi...@git.apache.org>.
Github user asfgit closed the pull request at:

    https://github.com/apache/flink/pull/5091


---

[GitHub] flink pull request #5091: [FLINK-7956] [flip6] Add support for queued schedu...

Posted by GJL <gi...@git.apache.org>.
Github user GJL commented on a diff in the pull request:

    https://github.com/apache/flink/pull/5091#discussion_r155770364
  
    --- Diff: flink-runtime/src/test/java/org/apache/flink/runtime/jobmaster/slotpool/SlotSharingManagerTest.java ---
    @@ -0,0 +1,502 @@
    +/*
    + * Licensed to the Apache Software Foundation (ASF) under one
    + * or more contributor license agreements.  See the NOTICE file
    + * distributed with this work for additional information
    + * regarding copyright ownership.  The ASF licenses this file
    + * to you under the Apache License, Version 2.0 (the
    + * "License"); you may not use this file except in compliance
    + * with the License.  You may obtain a copy of the License at
    + *
    + *     http://www.apache.org/licenses/LICENSE-2.0
    + *
    + * Unless required by applicable law or agreed to in writing, software
    + * distributed under the License is distributed on an "AS IS" BASIS,
    + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    + * See the License for the specific language governing permissions and
    + * limitations under the License.
    + */
    +
    +package org.apache.flink.runtime.jobmaster.slotpool;
    +
    +import org.apache.flink.runtime.clusterframework.types.AllocationID;
    +import org.apache.flink.runtime.executiongraph.utils.SimpleAckingTaskManagerGateway;
    +import org.apache.flink.runtime.instance.SimpleSlotContext;
    +import org.apache.flink.runtime.instance.SlotSharingGroupId;
    +import org.apache.flink.runtime.jobmanager.scheduler.Locality;
    +import org.apache.flink.runtime.jobmanager.slots.DummySlotOwner;
    +import org.apache.flink.runtime.jobmaster.LogicalSlot;
    +import org.apache.flink.runtime.jobmaster.SlotContext;
    +import org.apache.flink.runtime.jobmaster.SlotRequestId;
    +import org.apache.flink.runtime.taskmanager.LocalTaskManagerLocation;
    +import org.apache.flink.util.AbstractID;
    +import org.apache.flink.util.FlinkException;
    +import org.apache.flink.util.TestLogger;
    +
    +import org.junit.Test;
    +
    +import java.util.Collections;
    +import java.util.Objects;
    +import java.util.concurrent.CompletableFuture;
    +import java.util.concurrent.ExecutionException;
    +
    +import static org.junit.Assert.assertEquals;
    +import static org.junit.Assert.assertFalse;
    +import static org.junit.Assert.assertNotNull;
    +import static org.junit.Assert.assertNull;
    +import static org.junit.Assert.assertTrue;
    +
    +/**
    + * Test cases for the {@link SlotSharingManager}.
    + */
    +public class SlotSharingManagerTest extends TestLogger {
    +
    +	private static final SlotSharingGroupId slotSharingGroupId = new SlotSharingGroupId();
    +
    +	private static final DummySlotOwner slotOwner = new DummySlotOwner();
    +
    +	private static final TestingAllocatedSlotActions allocatedSlotActions = new TestingAllocatedSlotActions();
    --- End diff --
    
    This instance is mutable... should not be `static`


---

[GitHub] flink pull request #5091: [FLINK-7956] [flip6] Add support for queued schedu...

Posted by tillrohrmann <gi...@git.apache.org>.
Github user tillrohrmann commented on a diff in the pull request:

    https://github.com/apache/flink/pull/5091#discussion_r156892139
  
    --- Diff: flink-runtime/src/main/java/org/apache/flink/runtime/jobmaster/slotpool/SlotPool.java ---
    @@ -266,104 +279,367 @@ public void disconnectResourceManager() {
     	// ------------------------------------------------------------------------
     
     	@Override
    -	public CompletableFuture<SimpleSlot> allocateSlot(
    -			SlotRequestID requestId,
    -			ScheduledUnit task,
    -			ResourceProfile resources,
    -			Iterable<TaskManagerLocation> locationPreferences,
    +	public CompletableFuture<LogicalSlot> allocateSlot(
    +			SlotRequestId slotRequestId,
    +			ScheduledUnit scheduledUnit,
    +			ResourceProfile resourceProfile,
    +			Collection<TaskManagerLocation> locationPreferences,
    +			boolean allowQueuedScheduling,
     			Time timeout) {
     
    -		return internalAllocateSlot(requestId, task, resources, locationPreferences);
    +		return internalAllocateSlot(
    +			slotRequestId,
    +			scheduledUnit,
    +			resourceProfile,
    +			locationPreferences,
    +			allowQueuedScheduling);
     	}
     
    -	@Override
    -	public void returnAllocatedSlot(Slot slot) {
    -		internalReturnAllocatedSlot(slot);
    +	private CompletableFuture<LogicalSlot> internalAllocateSlot(
    +			SlotRequestId slotRequestId,
    +			ScheduledUnit task,
    +			ResourceProfile resourceProfile,
    +			Collection<TaskManagerLocation> locationPreferences,
    +			boolean allowQueuedScheduling) {
    +
    +		final SlotSharingGroupId slotSharingGroupId = task.getSlotSharingGroupId();
    +
    +		if (slotSharingGroupId != null) {
    +			// allocate slot with slot sharing
    +			final SlotSharingManager multiTaskSlotManager = slotSharingManagers.computeIfAbsent(
    +				slotSharingGroupId,
    +				id -> new SlotSharingManager(
    +					id,
    +					this,
    +					providerAndOwner));
    +
    +			final SlotSharingManager.MultiTaskSlotLocality multiTaskSlotFuture;
    --- End diff --
    
    True, will rename it.


---

[GitHub] flink pull request #5091: [FLINK-7956] [flip6] Add support for queued schedu...

Posted by tillrohrmann <gi...@git.apache.org>.
Github user tillrohrmann commented on a diff in the pull request:

    https://github.com/apache/flink/pull/5091#discussion_r156887983
  
    --- Diff: flink-runtime/src/main/java/org/apache/flink/runtime/jobmaster/slotpool/SlotSharingManager.java ---
    @@ -0,0 +1,722 @@
    +/*
    + * Licensed to the Apache Software Foundation (ASF) under one
    + * or more contributor license agreements.  See the NOTICE file
    + * distributed with this work for additional information
    + * regarding copyright ownership.  The ASF licenses this file
    + * to you under the Apache License, Version 2.0 (the
    + * "License"); you may not use this file except in compliance
    + * with the License.  You may obtain a copy of the License at
    + *
    + *     http://www.apache.org/licenses/LICENSE-2.0
    + *
    + * Unless required by applicable law or agreed to in writing, software
    + * distributed under the License is distributed on an "AS IS" BASIS,
    + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    + * See the License for the specific language governing permissions and
    + * limitations under the License.
    + */
    +
    +package org.apache.flink.runtime.jobmaster.slotpool;
    +
    +import org.apache.flink.annotation.VisibleForTesting;
    +import org.apache.flink.runtime.jobmaster.LogicalSlot;
    +import org.apache.flink.runtime.jobmaster.SlotContext;
    +import org.apache.flink.runtime.jobmaster.SlotOwner;
    +import org.apache.flink.runtime.jobmaster.SlotRequestId;
    +import org.apache.flink.runtime.instance.SlotSharingGroupId;
    --- End diff --
    
    Will correct it.


---

[GitHub] flink pull request #5091: [FLINK-7956] [flip6] Add support for queued schedu...

Posted by GJL <gi...@git.apache.org>.
Github user GJL commented on a diff in the pull request:

    https://github.com/apache/flink/pull/5091#discussion_r155507294
  
    --- Diff: flink-runtime/src/main/java/org/apache/flink/runtime/jobmaster/slotpool/SlotSharingManager.java ---
    @@ -0,0 +1,722 @@
    +/*
    + * Licensed to the Apache Software Foundation (ASF) under one
    + * or more contributor license agreements.  See the NOTICE file
    + * distributed with this work for additional information
    + * regarding copyright ownership.  The ASF licenses this file
    + * to you under the Apache License, Version 2.0 (the
    + * "License"); you may not use this file except in compliance
    + * with the License.  You may obtain a copy of the License at
    + *
    + *     http://www.apache.org/licenses/LICENSE-2.0
    + *
    + * Unless required by applicable law or agreed to in writing, software
    + * distributed under the License is distributed on an "AS IS" BASIS,
    + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    + * See the License for the specific language governing permissions and
    + * limitations under the License.
    + */
    +
    +package org.apache.flink.runtime.jobmaster.slotpool;
    +
    +import org.apache.flink.annotation.VisibleForTesting;
    +import org.apache.flink.runtime.jobmaster.LogicalSlot;
    +import org.apache.flink.runtime.jobmaster.SlotContext;
    +import org.apache.flink.runtime.jobmaster.SlotOwner;
    +import org.apache.flink.runtime.jobmaster.SlotRequestId;
    +import org.apache.flink.runtime.instance.SlotSharingGroupId;
    +import org.apache.flink.runtime.jobmanager.scheduler.Locality;
    +import org.apache.flink.runtime.taskmanager.TaskManagerLocation;
    +import org.apache.flink.util.AbstractID;
    +import org.apache.flink.util.FlinkException;
    +import org.apache.flink.util.Preconditions;
    +
    +import javax.annotation.Nullable;
    +
    +import java.util.AbstractCollection;
    +import java.util.Collection;
    +import java.util.Collections;
    +import java.util.HashMap;
    +import java.util.HashSet;
    +import java.util.Iterator;
    +import java.util.Map;
    +import java.util.Objects;
    +import java.util.Set;
    +import java.util.concurrent.CompletableFuture;
    +
    +/**
    + * Manager which is responsible for slot sharing. Slot sharing allows to run different
    + * tasks in the same slot and to realize co-location constraints.
    + *
    + * <p>The SlotSharingManager allows to create a hierarchy of {@link TaskSlot} such that
    + * every {@link TaskSlot} is uniquely identified by a {@link SlotRequestId} identifying
    + * the request for the TaskSlot and a {@link AbstractID} identifying the task or the
    + * co-location constraint running in this slot.
    + *
    + * <p>The {@link TaskSlot} hierarchy is implemented by {@link MultiTaskSlot} and
    + * {@link SingleTaskSlot}. The former class represents inner nodes which can contain
    + * a number of other {@link TaskSlot} and the latter class represents the leave nodes.
    + * The hierarchy starts with a root {@link MultiTaskSlot} which is a future
    + * {@link SlotContext} assigned. The {@link SlotContext} represents the allocated slot
    + * on the TaskExecutor in which all slots of this hierarchy run. A {@link MultiTaskSlot}
    + * can be assigned multiple {@link SingleTaskSlot} or {@link MultiTaskSlot} if and only if
    + * the task slot does not yet contain another child with the same {@link AbstractID} identifying
    + * the actual task or the co-location constraint.
    + *
    + * <p>Normal slot sharing is represented by a root {@link MultiTaskSlot} which contains a set
    + * of {@link SingleTaskSlot} on the second layer. Each {@link SingleTaskSlot} represents a different
    + * task.
    + *
    + * <p>Co-location constraints are modeled by adding a {@link MultiTaskSlot} to the root node. The co-location
    + * constraint is uniquely identified by a {@link AbstractID} such that we cannot add a second co-located
    + * {@link MultiTaskSlot} to the same root node. Now all co-located tasks will be added to co-located
    + * multi task slot.
    + */
    +public class SlotSharingManager {
    +
    +	private final SlotSharingGroupId slotSharingGroupId;
    +
    +	// needed to release allocated slots after a complete multi task slot hierarchy has been released
    +	private final AllocatedSlotActions allocatedSlotActions;
    +
    +	// owner of the slots to which to return them when they are released from the outside
    +	private final SlotOwner slotOwner;
    +
    +	private final Map<SlotRequestId, TaskSlot> allTaskSlots;
    +
    +	// Root nodes which have not been completed because the allocated slot is still pending
    +	private final Map<SlotRequestId, MultiTaskSlot> unresolvedRootSlots;
    +
    +	// Root nodes which have been completed (the underlying allocated slot has been assigned)
    +	private final Map<TaskManagerLocation, Set<MultiTaskSlot>> resolvedRootSlots;
    +
    +	// Internal class to iterate over all resolved root slots
    +	private ResolvedRootSlotValues resolvedMultiTaskSlotValues;
    +
    +	public SlotSharingManager(
    +			SlotSharingGroupId slotSharingGroupId,
    +			AllocatedSlotActions allocatedSlotActions,
    +			SlotOwner slotOwner) {
    +		this.slotSharingGroupId = Preconditions.checkNotNull(slotSharingGroupId);
    +		this.allocatedSlotActions = Preconditions.checkNotNull(allocatedSlotActions);
    +		this.slotOwner = Preconditions.checkNotNull(slotOwner);
    +
    +		allTaskSlots = new HashMap<>(16);
    +		unresolvedRootSlots = new HashMap<>(16);
    +		resolvedRootSlots = new HashMap<>(16);
    +
    +		resolvedMultiTaskSlotValues = null;
    +	}
    +
    +	public boolean isEmpty() {
    +		return allTaskSlots.isEmpty();
    +	}
    +
    +	public boolean contains(SlotRequestId slotRequestId) {
    +		return allTaskSlots.containsKey(slotRequestId);
    +	}
    +
    +	@Nullable
    +	public TaskSlot getTaskSlot(SlotRequestId slotRequestId) {
    +		return allTaskSlots.get(slotRequestId);
    +	}
    +
    +	/**
    +	 * Creates a new root slot with the given {@link SlotRequestId}, {@link SlotContext} future and
    +	 * the {@link SlotRequestId} of the allocated slot.
    +	 *
    +	 * @param slotRequestId of the root slot
    +	 * @param slotContextFuture with which we create the root slot
    +	 * @param allocatedSlotRequestId slot request id of the underlying allocated slot which can be used
    +	 *                               to cancel the pending slot request or release the allocated slot
    +	 * @return New root slot
    +	 */
    +	public MultiTaskSlot createRootSlot(
    +			SlotRequestId slotRequestId,
    +			CompletableFuture<SlotContext> slotContextFuture,
    +			SlotRequestId allocatedSlotRequestId) {
    +		final MultiTaskSlot rootMultiTaskSlot = new MultiTaskSlot(
    +			slotRequestId,
    +			slotContextFuture,
    +			allocatedSlotRequestId);
    +
    +		allTaskSlots.put(slotRequestId, rootMultiTaskSlot);
    +		unresolvedRootSlots.put(slotRequestId, rootMultiTaskSlot);
    +
    +		// add the root node to the set of resolved root nodes once the SlotContext future has been completed
    +		// and we know the slot's TaskManagerLocation
    +		slotContextFuture.whenComplete(
    +			(SlotContext slotContext, Throwable throwable) -> {
    +				if (slotContext != null) {
    +					final MultiTaskSlot resolvedRootNode = unresolvedRootSlots.remove(slotRequestId);
    +
    +					if (resolvedRootNode != null) {
    +						final Set<MultiTaskSlot> innerCollection = resolvedRootSlots.computeIfAbsent(
    +							slotContext.getTaskManagerLocation(),
    +							taskManagerLocation -> new HashSet<>(4));
    +
    +						innerCollection.add(resolvedRootNode);
    +					}
    +				} else {
    +					rootMultiTaskSlot.release(throwable);
    +				}
    +			});
    +
    +		return rootMultiTaskSlot;
    +	}
    +
    +	/**
    +	 * Gets a resolved root slot which does not yet contain the given groupId. First the given set of
    +	 * preferred locations is checked.
    +	 *
    +	 * @param groupId which the returned slot must not contain
    +	 * @param locationPreferences specifying which locations are preferred
    +	 * @return the resolved root slot and its locality wrt to the specified location preferences
    +	 * 		or null if there was no root slot which did not contain the given groupId
    +	 */
    +	@Nullable
    +	public MultiTaskSlotLocality getResolvedRootSlot(AbstractID groupId, Collection<TaskManagerLocation> locationPreferences) {
    +		Preconditions.checkNotNull(locationPreferences);
    +
    +		if (locationPreferences.isEmpty()) {
    +			return getResolvedRootSlotWithoutLocationPreferences(groupId);
    +		} else {
    +			return getResolvedRootSlotWithLocationPreferences(groupId, locationPreferences);
    +		}
    +	}
    +
    +	/**
    +	 * Gets a resolved root slot which does not yet contain the given groupId. The method will try to
    +	 * find a slot of a TaskManager contained in the collection of preferred locations. If there is no such slot
    +	 * with free capacities available, then the method will look for slots of TaskManager which run on the same
    +	 * machine as the TaskManager in the collection of preferred locations. If there is no such slot, then any slot
    +	 * with free capacities is returned. If there is no such slot, then null is returned.
    +	 *
    +	 * @param groupId which the returned slot must not contain
    +	 * @param locationPreferences specifying which locations are preferred
    +	 * @return the resolved root slot and its locality wrt to the specified location preferences
    +	 * 		or null if there was not root slot which did not contain the given groupId
    +	 */
    +	@Nullable
    +	private MultiTaskSlotLocality getResolvedRootSlotWithLocationPreferences(AbstractID groupId, Collection<TaskManagerLocation> locationPreferences) {
    +		Preconditions.checkNotNull(groupId);
    +		Preconditions.checkNotNull(locationPreferences);
    +		final Set<String> hostnameSet = new HashSet<>();
    +
    +		for (TaskManagerLocation locationPreference : locationPreferences) {
    +			final Set<MultiTaskSlot> multiTaskSlots = resolvedRootSlots.get(locationPreference);
    +
    +			if (multiTaskSlots != null) {
    +				for (MultiTaskSlot multiTaskSlot : multiTaskSlots) {
    +					if (!multiTaskSlot.contains(groupId)) {
    +						return MultiTaskSlotLocality.of(multiTaskSlot, Locality.LOCAL);
    +					}
    +				}
    +
    +				hostnameSet.add(locationPreference.getHostname());
    +			}
    +		}
    +
    +		MultiTaskSlot nonLocalMultiTaskSlot = null;
    +
    +		for (Map.Entry<TaskManagerLocation, Set<MultiTaskSlot>> taskManagerLocationSetEntry : resolvedRootSlots.entrySet()) {
    +			if (hostnameSet.contains(taskManagerLocationSetEntry.getKey().getHostname())) {
    +				for (MultiTaskSlot multiTaskSlot : taskManagerLocationSetEntry.getValue()) {
    +					if (!multiTaskSlot.contains(groupId)) {
    +						return MultiTaskSlotLocality.of(multiTaskSlot, Locality.HOST_LOCAL);
    +					}
    +				}
    +			} else if (nonLocalMultiTaskSlot == null) {
    +				for (MultiTaskSlot multiTaskSlot : taskManagerLocationSetEntry.getValue()) {
    +					if (!multiTaskSlot.contains(groupId)) {
    +						nonLocalMultiTaskSlot = multiTaskSlot;
    +					}
    +				}
    +			}
    +		}
    +
    +		if (nonLocalMultiTaskSlot != null) {
    +			return MultiTaskSlotLocality.of(nonLocalMultiTaskSlot, Locality.NON_LOCAL);
    +		} else {
    +			return null;
    +		}
    +	}
    +
    +	/**
    +	 * Gets a resolved slot which does not yet contain the given groupId without any location
    +	 * preferences.
    +	 *
    +	 * @param groupId which the returned slot must not contain
    +	 * @return the resolved slot or null if there was no root slot with free capacities
    +	 */
    +	@Nullable
    +	private MultiTaskSlotLocality getResolvedRootSlotWithoutLocationPreferences(AbstractID groupId) {
    +		Preconditions.checkNotNull(groupId);
    +
    +		for (Set<MultiTaskSlot> multiTaskSlots : resolvedRootSlots.values()) {
    +			for (MultiTaskSlot multiTaskSlot : multiTaskSlots) {
    +				if (!multiTaskSlot.contains(groupId)) {
    +					return MultiTaskSlotLocality.of(multiTaskSlot, Locality.UNCONSTRAINED);
    +				}
    +			}
    +		}
    +
    +		return null;
    +	}
    +
    +	/**
    +	 * Gets an unresolved slot which does not yet contain the given groupId. An unresolved
    +	 * slot is a slot whose underlying allocated slot has not been allocated yet.
    +	 *
    +	 * @param groupId which the returned slot must not contain
    +	 * @return the unresolved slot or null if there was no root slot with free capacities
    +	 */
    +	@Nullable
    +	public MultiTaskSlot getUnresolvedRootSlot(AbstractID groupId) {
    +		for (MultiTaskSlot multiTaskSlot : unresolvedRootSlots.values()) {
    +			if (!multiTaskSlot.contains(groupId)) {
    +				return multiTaskSlot;
    +			}
    +		}
    +
    +		return null;
    +	}
    +
    +	// ------------------------------------------------------------------------
    +	// Inner classes: TaskSlot hierarchy and helper classes
    +	// ------------------------------------------------------------------------
    +
    +	/**
    +	 * Helper class which contains a {@link MultiTaskSlot} and its {@link Locality}.
    +	 */
    +	public static final class MultiTaskSlotLocality {
    +		private final MultiTaskSlot multiTaskSlot;
    +
    +		private final Locality locality;
    +
    +		public MultiTaskSlotLocality(MultiTaskSlot multiTaskSlot, Locality locality) {
    +			this.multiTaskSlot = Preconditions.checkNotNull(multiTaskSlot);
    +			this.locality = Preconditions.checkNotNull(locality);
    +		}
    +
    +		public MultiTaskSlot getMultiTaskSlot() {
    +			return multiTaskSlot;
    +		}
    +
    +		public Locality getLocality() {
    +			return locality;
    +		}
    +
    +		public static MultiTaskSlotLocality of(MultiTaskSlot multiTaskSlot, Locality locality) {
    +			return new MultiTaskSlotLocality(multiTaskSlot, locality);
    +		}
    +	}
    +
    +	/**
    +	 * Base class for all task slots.
    +	 */
    +	public abstract static class TaskSlot {
    +		// every TaskSlot has an associated slot request id
    +		private final SlotRequestId slotRequestId;
    +
    +		// all task slots except for the root slots have a group id assigned
    +		@Nullable
    +		private final AbstractID groupId;
    +
    +		protected TaskSlot(SlotRequestId slotRequestId, @Nullable AbstractID groupId) {
    +			this.slotRequestId = Preconditions.checkNotNull(slotRequestId);
    +			this.groupId = groupId;
    +		}
    +
    +		public SlotRequestId getSlotRequestId() {
    +			return slotRequestId;
    +		}
    +
    +		@Nullable
    +		public AbstractID getGroupId() {
    +			return groupId;
    +		}
    +
    +		/**
    +		 * Check whether the task slot contains the given groupId.
    +		 *
    +		 * @param groupId which to check whether it is contained
    +		 * @return true if the task slot contains the given groupId, otherwise false
    +		 */
    +		public boolean contains(AbstractID groupId) {
    +			return Objects.equals(this.groupId, groupId);
    +		}
    +
    +		/**
    +		 * Release the task slot.
    +		 *
    +		 * @param cause for the release
    +		 * @return true if the slot could be released, otherwise false
    +		 */
    +		public abstract boolean release(Throwable cause);
    +	}
    +
    +	/**
    +	 * {@link TaskSlot} implementation which can have multiple other task slots assigned as children.
    +	 */
    +	public final class MultiTaskSlot extends TaskSlot implements AllocatedSlot.Payload {
    +
    +		private final Map<AbstractID, TaskSlot> children;
    +
    +		// the root node has its parent set to null
    +		@Nullable
    +		private final MultiTaskSlot parent;
    +
    +		// underlying allocated slot
    +		private final CompletableFuture<SlotContext> slotContextFuture;
    +
    +		// slot request id of the allocated slot
    +		@Nullable
    +		private final SlotRequestId allocatedSlotRequestId;
    +
    +		// true if we are currently releasing our children
    +		private boolean releasingChildren;
    +
    +		private MultiTaskSlot(
    +				SlotRequestId slotRequestId,
    +				AbstractID groupId,
    +				MultiTaskSlot parent) {
    +			this(
    +				slotRequestId,
    +				groupId,
    +				Preconditions.checkNotNull(parent),
    +				parent.getSlotContextFuture(),
    +				null);
    +		}
    +
    +		private MultiTaskSlot(
    +				SlotRequestId slotRequestId,
    +				CompletableFuture<SlotContext> slotContextFuture,
    +				SlotRequestId allocatedSlotRequestId) {
    +			this(
    +				slotRequestId,
    +				null,
    +				null,
    +				slotContextFuture,
    +				allocatedSlotRequestId);
    +		}
    +
    +		private MultiTaskSlot(
    +				SlotRequestId slotRequestId,
    +				@Nullable AbstractID groupId,
    +				MultiTaskSlot parent,
    +				CompletableFuture<SlotContext> slotContextFuture,
    +				SlotRequestId allocatedSlotRequestId) {
    +			super(slotRequestId, groupId);
    +
    +			this.parent = parent;
    +			this.slotContextFuture = Preconditions.checkNotNull(slotContextFuture);
    +			this.allocatedSlotRequestId = allocatedSlotRequestId;
    +
    +			this.children = new HashMap<>(16);
    +			this.releasingChildren = false;
    +
    +			slotContextFuture.whenComplete(
    +				(SlotContext ignored, Throwable throwable) -> {
    +					if (throwable != null) {
    +						release(throwable);
    +					}
    +				});
    +		}
    +
    +		public CompletableFuture<SlotContext> getSlotContextFuture() {
    +			return slotContextFuture;
    +		}
    +
    +		/**
    +		 * Allocates a {@link MultiTaskSlot} and registers it under the given groupId at
    +		 * this {@link MultiTaskSlot}.
    +		 *
    +		 * @param slotRequestId of the new multi task slot
    +		 * @param groupId under which the new multi task slot is registered
    +		 * @return the newly allocated {@link MultiTaskSlot}
    +		 */
    +		MultiTaskSlot allocateMultiTaskSlot(SlotRequestId slotRequestId, AbstractID groupId) {
    +			Preconditions.checkState(!super.contains(groupId));
    +
    +			final MultiTaskSlot inner = new MultiTaskSlot(
    +				slotRequestId,
    +				groupId,
    +				this);
    +
    +			children.put(groupId, inner);
    +
    +			// register the newly allocated slot also at the SlotSharingManager
    +			allTaskSlots.put(slotRequestId, inner);
    +
    +			return inner;
    +		}
    +
    +		/**
    +		 * Allocates a {@link SingleTaskSlot} and registeres it under the given groupId at
    +		 * this {@link MultiTaskSlot}.
    +		 *
    +		 * @param slotRequestId of the new single task slot
    +		 * @param groupId under which the new single task slot is registered
    +		 * @param locality of the allocation
    +		 * @return the newly allocated {@link SingleTaskSlot}
    +		 */
    +		SingleTaskSlot allocateSingleTaskSlot(
    +				SlotRequestId slotRequestId,
    +				AbstractID groupId,
    +				Locality locality) {
    +			Preconditions.checkState(!super.contains(groupId));
    +
    +			final SingleTaskSlot leave = new SingleTaskSlot(
    +				slotRequestId,
    +				groupId,
    +				this,
    +				locality);
    +
    +			children.put(groupId, leave);
    +
    +			// register the newly allocated slot also at the SlotSharingManager
    +			allTaskSlots.put(slotRequestId, leave);
    +
    +			return leave;
    +		}
    +
    +		/**
    +		 * Checks whether this slot or any of its children contains the given groupId.
    +		 *
    +		 * @param groupId which to check whether it is contained
    +		 * @return true if this or any of its children contains the given groupId, otherwise false
    +		 */
    +		@Override
    +		public boolean contains(AbstractID groupId) {
    +			if (super.contains(groupId)) {
    +				return true;
    +			} else {
    +				for (TaskSlot taskSlot : children.values()) {
    +					if (taskSlot.contains(groupId)) {
    +						return true;
    +					}
    +				}
    +
    +				return false;
    +			}
    +		}
    +
    +		@Override
    +		public boolean release(Throwable cause) {
    +			releasingChildren = true;
    +
    +			// first release all children and remove them if they could be released immediately
    +			children.values().removeIf(node -> {
    +				boolean release = node.release(cause);
    +
    +				if (release) {
    +					allTaskSlots.remove(node.slotRequestId);
    +				}
    +
    +				return release;
    +			});
    +
    +			releasingChildren = false;
    +
    +			if (children.isEmpty()) {
    +				if (parent != null) {
    +					// we remove ourselves from our parent if we no longer have children
    +					parent.releaseChild(getGroupId());
    +				} else {
    +					// we are the root node --> remove the root node from the list of task slots
    +					allTaskSlots.remove(getSlotRequestId());
    +
    +					if (!slotContextFuture.isDone() || slotContextFuture.isCompletedExceptionally()) {
    +						// the root node should still be unresolved
    +						unresolvedRootSlots.remove(getSlotRequestId());
    +					} else {
    +						// the root node should be resolved --> we can access the slot context
    +						final SlotContext slotContext = slotContextFuture.getNow(null);
    +
    +						if (slotContext != null) {
    +							final Set<MultiTaskSlot> multiTaskSlots = resolvedRootSlots.get(slotContext.getTaskManagerLocation());
    +
    +							if (multiTaskSlots != null) {
    +								multiTaskSlots.remove(this);
    +
    +								if (multiTaskSlots.isEmpty()) {
    +									resolvedRootSlots.remove(slotContext.getTaskManagerLocation());
    +								}
    +							}
    +						}
    +					}
    +
    +					// release the underlying allocated slot
    +					allocatedSlotActions.releaseSlot(allocatedSlotRequestId, null, cause);
    +				}
    +
    +				return true;
    +			} else {
    +				return false;
    +			}
    +		}
    +
    +		/**
    +		 * Releases the child with the given childGroupId.
    +		 *
    +		 * @param childGroupId identifying the child to release
    +		 */
    +		private void releaseChild(AbstractID childGroupId) {
    +			if (!releasingChildren) {
    +				TaskSlot child = children.remove(childGroupId);
    +
    +				if (child != null) {
    +					allTaskSlots.remove(child.getSlotRequestId());
    +				}
    +
    +				if (children.isEmpty()) {
    +					release(new FlinkException("Release multi task slot because all children have been released."));
    +				}
    +			}
    +		}
    +	}
    +
    +	/**
    +	 * {@link TaskSlot} implementation which harbours a {@link LogicalSlot}. The {@link SingleTaskSlot}
    +	 * cannot have any children assigned.
    +	 */
    +	public final class SingleTaskSlot extends TaskSlot {
    +		private final MultiTaskSlot parent;
    +
    +		// future containing a LogicalSlot which is completed once the underlying SlotContext future is completed
    +		private final CompletableFuture<LogicalSlot> logicalSlotFuture;
    +
    +		private SingleTaskSlot(
    +				SlotRequestId slotRequestId,
    +				AbstractID groupId,
    +				MultiTaskSlot parent,
    +				Locality locality) {
    +			super(slotRequestId, groupId);
    +
    +			this.parent = Preconditions.checkNotNull(parent);
    +
    +			Preconditions.checkNotNull(locality);
    +			logicalSlotFuture = parent.getSlotContextFuture()
    +				.thenApply(
    +					(SlotContext slotContext) ->
    +						new SingleLogicalSlot(
    +							slotRequestId,
    +							slotContext,
    +							slotSharingGroupId,
    +							locality,
    +							slotOwner));
    +		}
    +
    +		public CompletableFuture<LogicalSlot> getLogicalSlotFuture() {
    +			return logicalSlotFuture;
    +		}
    +
    +		@Override
    +		public boolean release(Throwable cause) {
    +			logicalSlotFuture.completeExceptionally(cause);
    +
    +			boolean pendingLogicalSlotRelease = false;
    +
    +			if (logicalSlotFuture.isDone() && !logicalSlotFuture.isCompletedExceptionally()) {
    +				// we have a single task slot which we first have to release
    +				final LogicalSlot logicalSlot = logicalSlotFuture.getNow(null);
    +
    +				if (logicalSlot != null && logicalSlot.isAlive()) {
    +					pendingLogicalSlotRelease = logicalSlot.releaseSlot(cause).isDone();
    +				}
    +			}
    +
    +			if (!pendingLogicalSlotRelease) {
    +				parent.releaseChild(getGroupId());
    +			}
    +
    +			return !pendingLogicalSlotRelease;
    +		}
    +	}
    +
    +	// ------------------------------------------------------------------------
    +	// Methods and classes for testing
    +	// ------------------------------------------------------------------------
    +
    +	/**
    +	 * Returns a collection of all resolved root slots.
    +	 *
    +	 * @return Collection of all resolved root slots
    +	 */
    +	@VisibleForTesting
    +	public Collection<MultiTaskSlot> getResolvedRootSlots() {
    +		ResolvedRootSlotValues vs = resolvedMultiTaskSlotValues;
    +
    +		if (vs == null ){
    +			vs = new ResolvedRootSlotValues();
    +			resolvedMultiTaskSlotValues = vs;
    +		}
    +
    +		return vs;
    +	}
    +
    +	@VisibleForTesting
    +	Collection<MultiTaskSlot> getUnresolvedRootSlots() {
    +		return unresolvedRootSlots.values();
    +	}
    +
    +	/**
    +	 * Collection of all resolved {@link MultiTaskSlot} root slots.
    +	 */
    +	private final class ResolvedRootSlotValues extends AbstractCollection<MultiTaskSlot> {
    +
    +		@Override
    +		public Iterator<MultiTaskSlot> iterator() {
    +			return new ResolvedRootSlotIterator(resolvedRootSlots.values().iterator());
    +		}
    +
    +		@Override
    +		public int size() {
    +			int numberResolvedMultiTaskSlots = 0;
    +
    +			for (Set<MultiTaskSlot> multiTaskSlots : resolvedRootSlots.values()) {
    +				numberResolvedMultiTaskSlots += multiTaskSlots.size();
    +			}
    +
    +			return numberResolvedMultiTaskSlots;
    +		}
    +	}
    +
    +	/**
    +	 * Iterator over all resolved {@link MultiTaskSlot} root slots.
    +	 */
    +	private static final class ResolvedRootSlotIterator implements Iterator<MultiTaskSlot> {
    +		private final Iterator<Set<MultiTaskSlot>> baseIterator;
    +		private Iterator<MultiTaskSlot> currentIterator;
    +
    +		private ResolvedRootSlotIterator(Iterator<Set<MultiTaskSlot>> baseIterator) {
    +			this.baseIterator = Preconditions.checkNotNull(baseIterator);
    +
    +			if (baseIterator.hasNext()) {
    +				currentIterator = baseIterator.next().iterator();
    +			} else {
    +				currentIterator = Collections.emptyIterator();
    +			}
    +		}
    +
    +		@Override
    +		public boolean hasNext() {
    +			progressToNextElement();
    +
    +			return currentIterator.hasNext();
    +		}
    +
    +		@Override
    +		public MultiTaskSlot next() {
    +			progressToNextElement();
    +
    +			return currentIterator.next();
    +		}
    +
    +		private void progressToNextElement() {
    +			while(baseIterator.hasNext() && ! currentIterator.hasNext()) {
    --- End diff --
    
    nit: missing space between `while` and `(`.  Space after `!`.


---

[GitHub] flink pull request #5091: [FLINK-7956] [flip6] Add support for queued schedu...

Posted by GJL <gi...@git.apache.org>.
Github user GJL commented on a diff in the pull request:

    https://github.com/apache/flink/pull/5091#discussion_r155590317
  
    --- Diff: flink-runtime/src/main/java/org/apache/flink/runtime/jobmaster/slotpool/SlotPool.java ---
    @@ -266,104 +279,367 @@ public void disconnectResourceManager() {
     	// ------------------------------------------------------------------------
     
     	@Override
    -	public CompletableFuture<SimpleSlot> allocateSlot(
    -			SlotRequestID requestId,
    -			ScheduledUnit task,
    -			ResourceProfile resources,
    -			Iterable<TaskManagerLocation> locationPreferences,
    +	public CompletableFuture<LogicalSlot> allocateSlot(
    +			SlotRequestId slotRequestId,
    +			ScheduledUnit scheduledUnit,
    +			ResourceProfile resourceProfile,
    +			Collection<TaskManagerLocation> locationPreferences,
    +			boolean allowQueuedScheduling,
     			Time timeout) {
     
    -		return internalAllocateSlot(requestId, task, resources, locationPreferences);
    +		return internalAllocateSlot(
    +			slotRequestId,
    +			scheduledUnit,
    +			resourceProfile,
    +			locationPreferences,
    +			allowQueuedScheduling);
     	}
     
    -	@Override
    -	public void returnAllocatedSlot(Slot slot) {
    -		internalReturnAllocatedSlot(slot);
    +	private CompletableFuture<LogicalSlot> internalAllocateSlot(
    +			SlotRequestId slotRequestId,
    +			ScheduledUnit task,
    +			ResourceProfile resourceProfile,
    +			Collection<TaskManagerLocation> locationPreferences,
    +			boolean allowQueuedScheduling) {
    +
    +		final SlotSharingGroupId slotSharingGroupId = task.getSlotSharingGroupId();
    +
    +		if (slotSharingGroupId != null) {
    +			// allocate slot with slot sharing
    +			final SlotSharingManager multiTaskSlotManager = slotSharingManagers.computeIfAbsent(
    +				slotSharingGroupId,
    +				id -> new SlotSharingManager(
    +					id,
    +					this,
    +					providerAndOwner));
    +
    +			final SlotSharingManager.MultiTaskSlotLocality multiTaskSlotFuture;
    +
    +			try {
    +				if (task.getCoLocationConstraint() != null) {
    +					multiTaskSlotFuture = allocateCoLocatedMultiTaskSlot(
    +						task.getCoLocationConstraint(),
    +						multiTaskSlotManager,
    +						resourceProfile,
    +						locationPreferences,
    +						allowQueuedScheduling);
    +				} else {
    +					multiTaskSlotFuture = allocateMultiTaskSlot(
    +						task.getJobVertexId(), multiTaskSlotManager,
    +						resourceProfile,
    +						locationPreferences,
    +						allowQueuedScheduling);
    +				}
    +			} catch (NoResourceAvailableException noResourceException) {
    +				return FutureUtils.completedExceptionally(noResourceException);
    +			}
    +
    +			// sanity check
    +			Preconditions.checkState(!multiTaskSlotFuture.getMultiTaskSlot().contains(task.getJobVertexId()));
    +
    +			final SlotSharingManager.SingleTaskSlot leave = multiTaskSlotFuture.getMultiTaskSlot().allocateSingleTaskSlot(
    --- End diff --
    
    nit: variable name should be *leaf* 
    
    https://www.dict.cc/?s=leaf


---

[GitHub] flink issue #5091: [FLINK-7956] [flip6] Add support for queued scheduling wi...

Posted by tillrohrmann <gi...@git.apache.org>.
Github user tillrohrmann commented on the issue:

    https://github.com/apache/flink/pull/5091
  
    Thanks for the review @GJL and @ifndef-SleePy. Travis passed locally. Merging this PR.


---

[GitHub] flink pull request #5091: [FLINK-7956] [flip6] Add support for queued schedu...

Posted by GJL <gi...@git.apache.org>.
Github user GJL commented on a diff in the pull request:

    https://github.com/apache/flink/pull/5091#discussion_r155519870
  
    --- Diff: flink-runtime/src/main/java/org/apache/flink/runtime/jobmaster/slotpool/SlotSharingManager.java ---
    @@ -0,0 +1,722 @@
    +/*
    + * Licensed to the Apache Software Foundation (ASF) under one
    + * or more contributor license agreements.  See the NOTICE file
    + * distributed with this work for additional information
    + * regarding copyright ownership.  The ASF licenses this file
    + * to you under the Apache License, Version 2.0 (the
    + * "License"); you may not use this file except in compliance
    + * with the License.  You may obtain a copy of the License at
    + *
    + *     http://www.apache.org/licenses/LICENSE-2.0
    + *
    + * Unless required by applicable law or agreed to in writing, software
    + * distributed under the License is distributed on an "AS IS" BASIS,
    + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    + * See the License for the specific language governing permissions and
    + * limitations under the License.
    + */
    +
    +package org.apache.flink.runtime.jobmaster.slotpool;
    +
    +import org.apache.flink.annotation.VisibleForTesting;
    +import org.apache.flink.runtime.jobmaster.LogicalSlot;
    +import org.apache.flink.runtime.jobmaster.SlotContext;
    +import org.apache.flink.runtime.jobmaster.SlotOwner;
    +import org.apache.flink.runtime.jobmaster.SlotRequestId;
    +import org.apache.flink.runtime.instance.SlotSharingGroupId;
    +import org.apache.flink.runtime.jobmanager.scheduler.Locality;
    +import org.apache.flink.runtime.taskmanager.TaskManagerLocation;
    +import org.apache.flink.util.AbstractID;
    +import org.apache.flink.util.FlinkException;
    +import org.apache.flink.util.Preconditions;
    +
    +import javax.annotation.Nullable;
    +
    +import java.util.AbstractCollection;
    +import java.util.Collection;
    +import java.util.Collections;
    +import java.util.HashMap;
    +import java.util.HashSet;
    +import java.util.Iterator;
    +import java.util.Map;
    +import java.util.Objects;
    +import java.util.Set;
    +import java.util.concurrent.CompletableFuture;
    +
    +/**
    + * Manager which is responsible for slot sharing. Slot sharing allows to run different
    + * tasks in the same slot and to realize co-location constraints.
    + *
    + * <p>The SlotSharingManager allows to create a hierarchy of {@link TaskSlot} such that
    + * every {@link TaskSlot} is uniquely identified by a {@link SlotRequestId} identifying
    + * the request for the TaskSlot and a {@link AbstractID} identifying the task or the
    + * co-location constraint running in this slot.
    + *
    + * <p>The {@link TaskSlot} hierarchy is implemented by {@link MultiTaskSlot} and
    + * {@link SingleTaskSlot}. The former class represents inner nodes which can contain
    + * a number of other {@link TaskSlot} and the latter class represents the leave nodes.
    + * The hierarchy starts with a root {@link MultiTaskSlot} which is a future
    + * {@link SlotContext} assigned. The {@link SlotContext} represents the allocated slot
    + * on the TaskExecutor in which all slots of this hierarchy run. A {@link MultiTaskSlot}
    + * can be assigned multiple {@link SingleTaskSlot} or {@link MultiTaskSlot} if and only if
    + * the task slot does not yet contain another child with the same {@link AbstractID} identifying
    + * the actual task or the co-location constraint.
    + *
    + * <p>Normal slot sharing is represented by a root {@link MultiTaskSlot} which contains a set
    + * of {@link SingleTaskSlot} on the second layer. Each {@link SingleTaskSlot} represents a different
    + * task.
    + *
    + * <p>Co-location constraints are modeled by adding a {@link MultiTaskSlot} to the root node. The co-location
    + * constraint is uniquely identified by a {@link AbstractID} such that we cannot add a second co-located
    + * {@link MultiTaskSlot} to the same root node. Now all co-located tasks will be added to co-located
    + * multi task slot.
    + */
    +public class SlotSharingManager {
    +
    +	private final SlotSharingGroupId slotSharingGroupId;
    +
    +	// needed to release allocated slots after a complete multi task slot hierarchy has been released
    +	private final AllocatedSlotActions allocatedSlotActions;
    +
    +	// owner of the slots to which to return them when they are released from the outside
    +	private final SlotOwner slotOwner;
    +
    +	private final Map<SlotRequestId, TaskSlot> allTaskSlots;
    +
    +	// Root nodes which have not been completed because the allocated slot is still pending
    +	private final Map<SlotRequestId, MultiTaskSlot> unresolvedRootSlots;
    +
    +	// Root nodes which have been completed (the underlying allocated slot has been assigned)
    +	private final Map<TaskManagerLocation, Set<MultiTaskSlot>> resolvedRootSlots;
    +
    +	// Internal class to iterate over all resolved root slots
    +	private ResolvedRootSlotValues resolvedMultiTaskSlotValues;
    +
    +	public SlotSharingManager(
    +			SlotSharingGroupId slotSharingGroupId,
    +			AllocatedSlotActions allocatedSlotActions,
    +			SlotOwner slotOwner) {
    +		this.slotSharingGroupId = Preconditions.checkNotNull(slotSharingGroupId);
    +		this.allocatedSlotActions = Preconditions.checkNotNull(allocatedSlotActions);
    +		this.slotOwner = Preconditions.checkNotNull(slotOwner);
    +
    +		allTaskSlots = new HashMap<>(16);
    +		unresolvedRootSlots = new HashMap<>(16);
    +		resolvedRootSlots = new HashMap<>(16);
    +
    +		resolvedMultiTaskSlotValues = null;
    +	}
    +
    +	public boolean isEmpty() {
    +		return allTaskSlots.isEmpty();
    +	}
    +
    +	public boolean contains(SlotRequestId slotRequestId) {
    +		return allTaskSlots.containsKey(slotRequestId);
    +	}
    +
    +	@Nullable
    +	public TaskSlot getTaskSlot(SlotRequestId slotRequestId) {
    +		return allTaskSlots.get(slotRequestId);
    +	}
    +
    +	/**
    +	 * Creates a new root slot with the given {@link SlotRequestId}, {@link SlotContext} future and
    +	 * the {@link SlotRequestId} of the allocated slot.
    +	 *
    +	 * @param slotRequestId of the root slot
    +	 * @param slotContextFuture with which we create the root slot
    +	 * @param allocatedSlotRequestId slot request id of the underlying allocated slot which can be used
    +	 *                               to cancel the pending slot request or release the allocated slot
    +	 * @return New root slot
    +	 */
    +	public MultiTaskSlot createRootSlot(
    +			SlotRequestId slotRequestId,
    +			CompletableFuture<SlotContext> slotContextFuture,
    +			SlotRequestId allocatedSlotRequestId) {
    +		final MultiTaskSlot rootMultiTaskSlot = new MultiTaskSlot(
    +			slotRequestId,
    +			slotContextFuture,
    +			allocatedSlotRequestId);
    +
    +		allTaskSlots.put(slotRequestId, rootMultiTaskSlot);
    +		unresolvedRootSlots.put(slotRequestId, rootMultiTaskSlot);
    +
    +		// add the root node to the set of resolved root nodes once the SlotContext future has been completed
    +		// and we know the slot's TaskManagerLocation
    +		slotContextFuture.whenComplete(
    +			(SlotContext slotContext, Throwable throwable) -> {
    +				if (slotContext != null) {
    +					final MultiTaskSlot resolvedRootNode = unresolvedRootSlots.remove(slotRequestId);
    +
    +					if (resolvedRootNode != null) {
    +						final Set<MultiTaskSlot> innerCollection = resolvedRootSlots.computeIfAbsent(
    +							slotContext.getTaskManagerLocation(),
    +							taskManagerLocation -> new HashSet<>(4));
    +
    +						innerCollection.add(resolvedRootNode);
    +					}
    +				} else {
    +					rootMultiTaskSlot.release(throwable);
    +				}
    +			});
    +
    +		return rootMultiTaskSlot;
    +	}
    +
    +	/**
    +	 * Gets a resolved root slot which does not yet contain the given groupId. First the given set of
    +	 * preferred locations is checked.
    +	 *
    +	 * @param groupId which the returned slot must not contain
    +	 * @param locationPreferences specifying which locations are preferred
    +	 * @return the resolved root slot and its locality wrt to the specified location preferences
    +	 * 		or null if there was no root slot which did not contain the given groupId
    +	 */
    +	@Nullable
    +	public MultiTaskSlotLocality getResolvedRootSlot(AbstractID groupId, Collection<TaskManagerLocation> locationPreferences) {
    +		Preconditions.checkNotNull(locationPreferences);
    +
    +		if (locationPreferences.isEmpty()) {
    +			return getResolvedRootSlotWithoutLocationPreferences(groupId);
    +		} else {
    +			return getResolvedRootSlotWithLocationPreferences(groupId, locationPreferences);
    +		}
    +	}
    +
    +	/**
    +	 * Gets a resolved root slot which does not yet contain the given groupId. The method will try to
    +	 * find a slot of a TaskManager contained in the collection of preferred locations. If there is no such slot
    +	 * with free capacities available, then the method will look for slots of TaskManager which run on the same
    +	 * machine as the TaskManager in the collection of preferred locations. If there is no such slot, then any slot
    +	 * with free capacities is returned. If there is no such slot, then null is returned.
    +	 *
    +	 * @param groupId which the returned slot must not contain
    +	 * @param locationPreferences specifying which locations are preferred
    +	 * @return the resolved root slot and its locality wrt to the specified location preferences
    +	 * 		or null if there was not root slot which did not contain the given groupId
    +	 */
    +	@Nullable
    +	private MultiTaskSlotLocality getResolvedRootSlotWithLocationPreferences(AbstractID groupId, Collection<TaskManagerLocation> locationPreferences) {
    +		Preconditions.checkNotNull(groupId);
    +		Preconditions.checkNotNull(locationPreferences);
    +		final Set<String> hostnameSet = new HashSet<>();
    +
    +		for (TaskManagerLocation locationPreference : locationPreferences) {
    +			final Set<MultiTaskSlot> multiTaskSlots = resolvedRootSlots.get(locationPreference);
    +
    +			if (multiTaskSlots != null) {
    +				for (MultiTaskSlot multiTaskSlot : multiTaskSlots) {
    +					if (!multiTaskSlot.contains(groupId)) {
    +						return MultiTaskSlotLocality.of(multiTaskSlot, Locality.LOCAL);
    +					}
    +				}
    +
    +				hostnameSet.add(locationPreference.getHostname());
    +			}
    +		}
    +
    +		MultiTaskSlot nonLocalMultiTaskSlot = null;
    +
    +		for (Map.Entry<TaskManagerLocation, Set<MultiTaskSlot>> taskManagerLocationSetEntry : resolvedRootSlots.entrySet()) {
    +			if (hostnameSet.contains(taskManagerLocationSetEntry.getKey().getHostname())) {
    +				for (MultiTaskSlot multiTaskSlot : taskManagerLocationSetEntry.getValue()) {
    +					if (!multiTaskSlot.contains(groupId)) {
    +						return MultiTaskSlotLocality.of(multiTaskSlot, Locality.HOST_LOCAL);
    +					}
    +				}
    +			} else if (nonLocalMultiTaskSlot == null) {
    +				for (MultiTaskSlot multiTaskSlot : taskManagerLocationSetEntry.getValue()) {
    +					if (!multiTaskSlot.contains(groupId)) {
    +						nonLocalMultiTaskSlot = multiTaskSlot;
    +					}
    +				}
    +			}
    +		}
    +
    +		if (nonLocalMultiTaskSlot != null) {
    +			return MultiTaskSlotLocality.of(nonLocalMultiTaskSlot, Locality.NON_LOCAL);
    +		} else {
    +			return null;
    +		}
    +	}
    +
    +	/**
    +	 * Gets a resolved slot which does not yet contain the given groupId without any location
    +	 * preferences.
    +	 *
    +	 * @param groupId which the returned slot must not contain
    +	 * @return the resolved slot or null if there was no root slot with free capacities
    +	 */
    +	@Nullable
    +	private MultiTaskSlotLocality getResolvedRootSlotWithoutLocationPreferences(AbstractID groupId) {
    +		Preconditions.checkNotNull(groupId);
    +
    +		for (Set<MultiTaskSlot> multiTaskSlots : resolvedRootSlots.values()) {
    +			for (MultiTaskSlot multiTaskSlot : multiTaskSlots) {
    +				if (!multiTaskSlot.contains(groupId)) {
    +					return MultiTaskSlotLocality.of(multiTaskSlot, Locality.UNCONSTRAINED);
    +				}
    +			}
    +		}
    +
    +		return null;
    +	}
    +
    +	/**
    +	 * Gets an unresolved slot which does not yet contain the given groupId. An unresolved
    +	 * slot is a slot whose underlying allocated slot has not been allocated yet.
    +	 *
    +	 * @param groupId which the returned slot must not contain
    +	 * @return the unresolved slot or null if there was no root slot with free capacities
    +	 */
    +	@Nullable
    +	public MultiTaskSlot getUnresolvedRootSlot(AbstractID groupId) {
    +		for (MultiTaskSlot multiTaskSlot : unresolvedRootSlots.values()) {
    +			if (!multiTaskSlot.contains(groupId)) {
    +				return multiTaskSlot;
    +			}
    +		}
    +
    +		return null;
    +	}
    +
    +	// ------------------------------------------------------------------------
    +	// Inner classes: TaskSlot hierarchy and helper classes
    +	// ------------------------------------------------------------------------
    +
    +	/**
    +	 * Helper class which contains a {@link MultiTaskSlot} and its {@link Locality}.
    +	 */
    +	public static final class MultiTaskSlotLocality {
    +		private final MultiTaskSlot multiTaskSlot;
    +
    +		private final Locality locality;
    +
    +		public MultiTaskSlotLocality(MultiTaskSlot multiTaskSlot, Locality locality) {
    +			this.multiTaskSlot = Preconditions.checkNotNull(multiTaskSlot);
    +			this.locality = Preconditions.checkNotNull(locality);
    +		}
    +
    +		public MultiTaskSlot getMultiTaskSlot() {
    +			return multiTaskSlot;
    +		}
    +
    +		public Locality getLocality() {
    +			return locality;
    +		}
    +
    +		public static MultiTaskSlotLocality of(MultiTaskSlot multiTaskSlot, Locality locality) {
    +			return new MultiTaskSlotLocality(multiTaskSlot, locality);
    +		}
    +	}
    +
    +	/**
    +	 * Base class for all task slots.
    +	 */
    +	public abstract static class TaskSlot {
    +		// every TaskSlot has an associated slot request id
    +		private final SlotRequestId slotRequestId;
    +
    +		// all task slots except for the root slots have a group id assigned
    +		@Nullable
    +		private final AbstractID groupId;
    +
    +		protected TaskSlot(SlotRequestId slotRequestId, @Nullable AbstractID groupId) {
    +			this.slotRequestId = Preconditions.checkNotNull(slotRequestId);
    +			this.groupId = groupId;
    +		}
    +
    +		public SlotRequestId getSlotRequestId() {
    +			return slotRequestId;
    +		}
    +
    +		@Nullable
    +		public AbstractID getGroupId() {
    +			return groupId;
    +		}
    +
    +		/**
    +		 * Check whether the task slot contains the given groupId.
    +		 *
    +		 * @param groupId which to check whether it is contained
    +		 * @return true if the task slot contains the given groupId, otherwise false
    +		 */
    +		public boolean contains(AbstractID groupId) {
    +			return Objects.equals(this.groupId, groupId);
    +		}
    +
    +		/**
    +		 * Release the task slot.
    +		 *
    +		 * @param cause for the release
    +		 * @return true if the slot could be released, otherwise false
    +		 */
    +		public abstract boolean release(Throwable cause);
    +	}
    +
    +	/**
    +	 * {@link TaskSlot} implementation which can have multiple other task slots assigned as children.
    +	 */
    +	public final class MultiTaskSlot extends TaskSlot implements AllocatedSlot.Payload {
    +
    +		private final Map<AbstractID, TaskSlot> children;
    +
    +		// the root node has its parent set to null
    +		@Nullable
    +		private final MultiTaskSlot parent;
    +
    +		// underlying allocated slot
    +		private final CompletableFuture<SlotContext> slotContextFuture;
    +
    +		// slot request id of the allocated slot
    +		@Nullable
    +		private final SlotRequestId allocatedSlotRequestId;
    +
    +		// true if we are currently releasing our children
    +		private boolean releasingChildren;
    +
    +		private MultiTaskSlot(
    +				SlotRequestId slotRequestId,
    +				AbstractID groupId,
    +				MultiTaskSlot parent) {
    +			this(
    +				slotRequestId,
    +				groupId,
    +				Preconditions.checkNotNull(parent),
    +				parent.getSlotContextFuture(),
    +				null);
    +		}
    +
    +		private MultiTaskSlot(
    +				SlotRequestId slotRequestId,
    +				CompletableFuture<SlotContext> slotContextFuture,
    +				SlotRequestId allocatedSlotRequestId) {
    +			this(
    +				slotRequestId,
    +				null,
    +				null,
    +				slotContextFuture,
    +				allocatedSlotRequestId);
    +		}
    +
    +		private MultiTaskSlot(
    +				SlotRequestId slotRequestId,
    +				@Nullable AbstractID groupId,
    +				MultiTaskSlot parent,
    +				CompletableFuture<SlotContext> slotContextFuture,
    +				SlotRequestId allocatedSlotRequestId) {
    +			super(slotRequestId, groupId);
    +
    +			this.parent = parent;
    +			this.slotContextFuture = Preconditions.checkNotNull(slotContextFuture);
    +			this.allocatedSlotRequestId = allocatedSlotRequestId;
    +
    +			this.children = new HashMap<>(16);
    +			this.releasingChildren = false;
    +
    +			slotContextFuture.whenComplete(
    +				(SlotContext ignored, Throwable throwable) -> {
    +					if (throwable != null) {
    +						release(throwable);
    +					}
    +				});
    +		}
    +
    +		public CompletableFuture<SlotContext> getSlotContextFuture() {
    +			return slotContextFuture;
    +		}
    +
    +		/**
    +		 * Allocates a {@link MultiTaskSlot} and registers it under the given groupId at
    +		 * this {@link MultiTaskSlot}.
    +		 *
    +		 * @param slotRequestId of the new multi task slot
    +		 * @param groupId under which the new multi task slot is registered
    +		 * @return the newly allocated {@link MultiTaskSlot}
    +		 */
    +		MultiTaskSlot allocateMultiTaskSlot(SlotRequestId slotRequestId, AbstractID groupId) {
    +			Preconditions.checkState(!super.contains(groupId));
    +
    +			final MultiTaskSlot inner = new MultiTaskSlot(
    +				slotRequestId,
    +				groupId,
    +				this);
    +
    +			children.put(groupId, inner);
    +
    +			// register the newly allocated slot also at the SlotSharingManager
    +			allTaskSlots.put(slotRequestId, inner);
    +
    +			return inner;
    +		}
    +
    +		/**
    +		 * Allocates a {@link SingleTaskSlot} and registeres it under the given groupId at
    +		 * this {@link MultiTaskSlot}.
    +		 *
    +		 * @param slotRequestId of the new single task slot
    +		 * @param groupId under which the new single task slot is registered
    +		 * @param locality of the allocation
    +		 * @return the newly allocated {@link SingleTaskSlot}
    +		 */
    +		SingleTaskSlot allocateSingleTaskSlot(
    +				SlotRequestId slotRequestId,
    +				AbstractID groupId,
    +				Locality locality) {
    +			Preconditions.checkState(!super.contains(groupId));
    +
    +			final SingleTaskSlot leave = new SingleTaskSlot(
    +				slotRequestId,
    +				groupId,
    +				this,
    +				locality);
    +
    +			children.put(groupId, leave);
    +
    +			// register the newly allocated slot also at the SlotSharingManager
    +			allTaskSlots.put(slotRequestId, leave);
    +
    +			return leave;
    +		}
    +
    +		/**
    +		 * Checks whether this slot or any of its children contains the given groupId.
    +		 *
    +		 * @param groupId which to check whether it is contained
    +		 * @return true if this or any of its children contains the given groupId, otherwise false
    +		 */
    +		@Override
    +		public boolean contains(AbstractID groupId) {
    +			if (super.contains(groupId)) {
    +				return true;
    +			} else {
    +				for (TaskSlot taskSlot : children.values()) {
    +					if (taskSlot.contains(groupId)) {
    +						return true;
    +					}
    +				}
    +
    +				return false;
    +			}
    +		}
    +
    +		@Override
    +		public boolean release(Throwable cause) {
    +			releasingChildren = true;
    +
    +			// first release all children and remove them if they could be released immediately
    +			children.values().removeIf(node -> {
    +				boolean release = node.release(cause);
    +
    +				if (release) {
    +					allTaskSlots.remove(node.slotRequestId);
    +				}
    +
    +				return release;
    +			});
    +
    +			releasingChildren = false;
    +
    +			if (children.isEmpty()) {
    +				if (parent != null) {
    +					// we remove ourselves from our parent if we no longer have children
    +					parent.releaseChild(getGroupId());
    +				} else {
    +					// we are the root node --> remove the root node from the list of task slots
    +					allTaskSlots.remove(getSlotRequestId());
    +
    +					if (!slotContextFuture.isDone() || slotContextFuture.isCompletedExceptionally()) {
    +						// the root node should still be unresolved
    +						unresolvedRootSlots.remove(getSlotRequestId());
    +					} else {
    +						// the root node should be resolved --> we can access the slot context
    +						final SlotContext slotContext = slotContextFuture.getNow(null);
    +
    +						if (slotContext != null) {
    +							final Set<MultiTaskSlot> multiTaskSlots = resolvedRootSlots.get(slotContext.getTaskManagerLocation());
    +
    +							if (multiTaskSlots != null) {
    +								multiTaskSlots.remove(this);
    +
    +								if (multiTaskSlots.isEmpty()) {
    +									resolvedRootSlots.remove(slotContext.getTaskManagerLocation());
    +								}
    +							}
    +						}
    +					}
    +
    +					// release the underlying allocated slot
    +					allocatedSlotActions.releaseSlot(allocatedSlotRequestId, null, cause);
    +				}
    +
    +				return true;
    +			} else {
    +				return false;
    +			}
    +		}
    +
    +		/**
    +		 * Releases the child with the given childGroupId.
    +		 *
    +		 * @param childGroupId identifying the child to release
    +		 */
    +		private void releaseChild(AbstractID childGroupId) {
    +			if (!releasingChildren) {
    +				TaskSlot child = children.remove(childGroupId);
    +
    +				if (child != null) {
    +					allTaskSlots.remove(child.getSlotRequestId());
    +				}
    +
    +				if (children.isEmpty()) {
    +					release(new FlinkException("Release multi task slot because all children have been released."));
    +				}
    +			}
    +		}
    +	}
    +
    +	/**
    +	 * {@link TaskSlot} implementation which harbours a {@link LogicalSlot}. The {@link SingleTaskSlot}
    +	 * cannot have any children assigned.
    +	 */
    +	public final class SingleTaskSlot extends TaskSlot {
    +		private final MultiTaskSlot parent;
    +
    +		// future containing a LogicalSlot which is completed once the underlying SlotContext future is completed
    +		private final CompletableFuture<LogicalSlot> logicalSlotFuture;
    +
    +		private SingleTaskSlot(
    +				SlotRequestId slotRequestId,
    +				AbstractID groupId,
    +				MultiTaskSlot parent,
    +				Locality locality) {
    +			super(slotRequestId, groupId);
    +
    +			this.parent = Preconditions.checkNotNull(parent);
    +
    +			Preconditions.checkNotNull(locality);
    +			logicalSlotFuture = parent.getSlotContextFuture()
    +				.thenApply(
    +					(SlotContext slotContext) ->
    +						new SingleLogicalSlot(
    +							slotRequestId,
    +							slotContext,
    +							slotSharingGroupId,
    +							locality,
    +							slotOwner));
    +		}
    +
    +		public CompletableFuture<LogicalSlot> getLogicalSlotFuture() {
    +			return logicalSlotFuture;
    +		}
    +
    +		@Override
    +		public boolean release(Throwable cause) {
    +			logicalSlotFuture.completeExceptionally(cause);
    +
    +			boolean pendingLogicalSlotRelease = false;
    +
    +			if (logicalSlotFuture.isDone() && !logicalSlotFuture.isCompletedExceptionally()) {
    +				// we have a single task slot which we first have to release
    +				final LogicalSlot logicalSlot = logicalSlotFuture.getNow(null);
    +
    +				if (logicalSlot != null && logicalSlot.isAlive()) {
    +					pendingLogicalSlotRelease = logicalSlot.releaseSlot(cause).isDone();
    +				}
    +			}
    +
    +			if (!pendingLogicalSlotRelease) {
    +				parent.releaseChild(getGroupId());
    +			}
    +
    +			return !pendingLogicalSlotRelease;
    +		}
    +	}
    +
    +	// ------------------------------------------------------------------------
    +	// Methods and classes for testing
    +	// ------------------------------------------------------------------------
    +
    +	/**
    +	 * Returns a collection of all resolved root slots.
    +	 *
    +	 * @return Collection of all resolved root slots
    +	 */
    +	@VisibleForTesting
    +	public Collection<MultiTaskSlot> getResolvedRootSlots() {
    +		ResolvedRootSlotValues vs = resolvedMultiTaskSlotValues;
    --- End diff --
    
    Since this is only for testing, do we really need to cache the instance in `resolvedMultiTaskSlotValues`? It is not obvious that `resolvedMultiTaskSlotValues` is only used for testing. How about just
    ```
    	public Collection<MultiTaskSlot> getResolvedRootSlots() {
    		return new ResolvedRootSlotValues();
    	}
    ```


---

[GitHub] flink pull request #5091: [FLINK-7956] [flip6] Add support for queued schedu...

Posted by GJL <gi...@git.apache.org>.
Github user GJL commented on a diff in the pull request:

    https://github.com/apache/flink/pull/5091#discussion_r155503994
  
    --- Diff: flink-runtime/src/test/java/org/apache/flink/runtime/jobmanager/scheduler/SchedulerTest.java ---
    @@ -0,0 +1,97 @@
    +/*
    + * Licensed to the Apache Software Foundation (ASF) under one
    + * or more contributor license agreements.  See the NOTICE file
    + * distributed with this work for additional information
    + * regarding copyright ownership.  The ASF licenses this file
    + * to you under the Apache License, Version 2.0 (the
    + * "License"); you may not use this file except in compliance
    + * with the License.  You may obtain a copy of the License at
    + *
    + *     http://www.apache.org/licenses/LICENSE-2.0
    + *
    + * Unless required by applicable law or agreed to in writing, software
    + * distributed under the License is distributed on an "AS IS" BASIS,
    + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    + * See the License for the specific language governing permissions and
    + * limitations under the License.
    + */
    +
    +package org.apache.flink.runtime.jobmanager.scheduler;
    +
    +import org.apache.flink.runtime.instance.Instance;
    +import org.apache.flink.runtime.testingUtils.TestingUtils;
    +import org.apache.flink.util.TestLogger;
    +
    +import org.junit.Test;
    +
    +import static org.apache.flink.runtime.jobmanager.scheduler.SchedulerTestUtils.getRandomInstance;
    +import static org.junit.Assert.assertEquals;
    +import static org.junit.Assert.assertFalse;
    +import static org.junit.Assert.fail;
    +
    +public class SchedulerTest extends TestLogger {
    +
    +	@Test
    +	public void testAddAndRemoveInstance() {
    +		try {
    +			Scheduler scheduler = new Scheduler(TestingUtils.defaultExecutionContext());
    +
    +			Instance i1 = getRandomInstance(2);
    +			Instance i2 = getRandomInstance(2);
    +			Instance i3 = getRandomInstance(2);
    +
    +			assertEquals(0, scheduler.getNumberOfAvailableInstances());
    +			assertEquals(0, scheduler.getNumberOfAvailableSlots());
    +			scheduler.newInstanceAvailable(i1);
    +			assertEquals(1, scheduler.getNumberOfAvailableInstances());
    +			assertEquals(2, scheduler.getNumberOfAvailableSlots());
    +			scheduler.newInstanceAvailable(i2);
    +			assertEquals(2, scheduler.getNumberOfAvailableInstances());
    +			assertEquals(4, scheduler.getNumberOfAvailableSlots());
    +			scheduler.newInstanceAvailable(i3);
    +			assertEquals(3, scheduler.getNumberOfAvailableInstances());
    +			assertEquals(6, scheduler.getNumberOfAvailableSlots());
    +
    +			// cannot add available instance again
    +			try {
    +				scheduler.newInstanceAvailable(i2);
    +				fail("Scheduler accepted instance twice");
    +			}
    +			catch (IllegalArgumentException e) {
    +				// bueno!
    +			}
    +
    +			// some instances die
    +			assertEquals(3, scheduler.getNumberOfAvailableInstances());
    +			assertEquals(6, scheduler.getNumberOfAvailableSlots());
    +			scheduler.instanceDied(i2);
    +			assertEquals(2, scheduler.getNumberOfAvailableInstances());
    +			assertEquals(4, scheduler.getNumberOfAvailableSlots());
    +
    +			// try to add a dead instance
    +			try {
    +				scheduler.newInstanceAvailable(i2);
    +				fail("Scheduler accepted dead instance");
    +			}
    +			catch (IllegalArgumentException e) {
    +				// stimmt
    +
    +			}
    +
    +			scheduler.instanceDied(i1);
    +			assertEquals(1, scheduler.getNumberOfAvailableInstances());
    +			assertEquals(2, scheduler.getNumberOfAvailableSlots());
    +			scheduler.instanceDied(i3);
    +			assertEquals(0, scheduler.getNumberOfAvailableInstances());
    +			assertEquals(0, scheduler.getNumberOfAvailableSlots());
    +
    +			assertFalse(i1.isAlive());
    +			assertFalse(i2.isAlive());
    +			assertFalse(i3.isAlive());
    +		}
    +		catch (Exception e) {
    --- End diff --
    
    Better propagate the exception but I guess this file was copy pasted.


---

[GitHub] flink pull request #5091: [FLINK-7956] [flip6] Add support for queued schedu...

Posted by GJL <gi...@git.apache.org>.
Github user GJL commented on a diff in the pull request:

    https://github.com/apache/flink/pull/5091#discussion_r155528224
  
    --- Diff: flink-runtime/src/main/java/org/apache/flink/runtime/jobmaster/slotpool/SlotSharingManager.java ---
    @@ -0,0 +1,722 @@
    +/*
    + * Licensed to the Apache Software Foundation (ASF) under one
    + * or more contributor license agreements.  See the NOTICE file
    + * distributed with this work for additional information
    + * regarding copyright ownership.  The ASF licenses this file
    + * to you under the Apache License, Version 2.0 (the
    + * "License"); you may not use this file except in compliance
    + * with the License.  You may obtain a copy of the License at
    + *
    + *     http://www.apache.org/licenses/LICENSE-2.0
    + *
    + * Unless required by applicable law or agreed to in writing, software
    + * distributed under the License is distributed on an "AS IS" BASIS,
    + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    + * See the License for the specific language governing permissions and
    + * limitations under the License.
    + */
    +
    +package org.apache.flink.runtime.jobmaster.slotpool;
    +
    +import org.apache.flink.annotation.VisibleForTesting;
    +import org.apache.flink.runtime.jobmaster.LogicalSlot;
    +import org.apache.flink.runtime.jobmaster.SlotContext;
    +import org.apache.flink.runtime.jobmaster.SlotOwner;
    +import org.apache.flink.runtime.jobmaster.SlotRequestId;
    +import org.apache.flink.runtime.instance.SlotSharingGroupId;
    +import org.apache.flink.runtime.jobmanager.scheduler.Locality;
    +import org.apache.flink.runtime.taskmanager.TaskManagerLocation;
    +import org.apache.flink.util.AbstractID;
    +import org.apache.flink.util.FlinkException;
    +import org.apache.flink.util.Preconditions;
    +
    +import javax.annotation.Nullable;
    +
    +import java.util.AbstractCollection;
    +import java.util.Collection;
    +import java.util.Collections;
    +import java.util.HashMap;
    +import java.util.HashSet;
    +import java.util.Iterator;
    +import java.util.Map;
    +import java.util.Objects;
    +import java.util.Set;
    +import java.util.concurrent.CompletableFuture;
    +
    +/**
    + * Manager which is responsible for slot sharing. Slot sharing allows to run different
    + * tasks in the same slot and to realize co-location constraints.
    + *
    + * <p>The SlotSharingManager allows to create a hierarchy of {@link TaskSlot} such that
    + * every {@link TaskSlot} is uniquely identified by a {@link SlotRequestId} identifying
    + * the request for the TaskSlot and a {@link AbstractID} identifying the task or the
    + * co-location constraint running in this slot.
    + *
    + * <p>The {@link TaskSlot} hierarchy is implemented by {@link MultiTaskSlot} and
    + * {@link SingleTaskSlot}. The former class represents inner nodes which can contain
    + * a number of other {@link TaskSlot} and the latter class represents the leave nodes.
    + * The hierarchy starts with a root {@link MultiTaskSlot} which is a future
    + * {@link SlotContext} assigned. The {@link SlotContext} represents the allocated slot
    + * on the TaskExecutor in which all slots of this hierarchy run. A {@link MultiTaskSlot}
    + * can be assigned multiple {@link SingleTaskSlot} or {@link MultiTaskSlot} if and only if
    + * the task slot does not yet contain another child with the same {@link AbstractID} identifying
    + * the actual task or the co-location constraint.
    + *
    + * <p>Normal slot sharing is represented by a root {@link MultiTaskSlot} which contains a set
    + * of {@link SingleTaskSlot} on the second layer. Each {@link SingleTaskSlot} represents a different
    + * task.
    + *
    + * <p>Co-location constraints are modeled by adding a {@link MultiTaskSlot} to the root node. The co-location
    + * constraint is uniquely identified by a {@link AbstractID} such that we cannot add a second co-located
    + * {@link MultiTaskSlot} to the same root node. Now all co-located tasks will be added to co-located
    + * multi task slot.
    + */
    +public class SlotSharingManager {
    +
    +	private final SlotSharingGroupId slotSharingGroupId;
    +
    +	// needed to release allocated slots after a complete multi task slot hierarchy has been released
    +	private final AllocatedSlotActions allocatedSlotActions;
    +
    +	// owner of the slots to which to return them when they are released from the outside
    +	private final SlotOwner slotOwner;
    +
    +	private final Map<SlotRequestId, TaskSlot> allTaskSlots;
    +
    +	// Root nodes which have not been completed because the allocated slot is still pending
    +	private final Map<SlotRequestId, MultiTaskSlot> unresolvedRootSlots;
    +
    +	// Root nodes which have been completed (the underlying allocated slot has been assigned)
    +	private final Map<TaskManagerLocation, Set<MultiTaskSlot>> resolvedRootSlots;
    +
    +	// Internal class to iterate over all resolved root slots
    +	private ResolvedRootSlotValues resolvedMultiTaskSlotValues;
    +
    +	public SlotSharingManager(
    +			SlotSharingGroupId slotSharingGroupId,
    +			AllocatedSlotActions allocatedSlotActions,
    +			SlotOwner slotOwner) {
    +		this.slotSharingGroupId = Preconditions.checkNotNull(slotSharingGroupId);
    +		this.allocatedSlotActions = Preconditions.checkNotNull(allocatedSlotActions);
    +		this.slotOwner = Preconditions.checkNotNull(slotOwner);
    +
    +		allTaskSlots = new HashMap<>(16);
    +		unresolvedRootSlots = new HashMap<>(16);
    +		resolvedRootSlots = new HashMap<>(16);
    +
    +		resolvedMultiTaskSlotValues = null;
    +	}
    +
    +	public boolean isEmpty() {
    +		return allTaskSlots.isEmpty();
    +	}
    +
    +	public boolean contains(SlotRequestId slotRequestId) {
    +		return allTaskSlots.containsKey(slotRequestId);
    +	}
    +
    +	@Nullable
    +	public TaskSlot getTaskSlot(SlotRequestId slotRequestId) {
    +		return allTaskSlots.get(slotRequestId);
    +	}
    +
    +	/**
    +	 * Creates a new root slot with the given {@link SlotRequestId}, {@link SlotContext} future and
    +	 * the {@link SlotRequestId} of the allocated slot.
    +	 *
    +	 * @param slotRequestId of the root slot
    +	 * @param slotContextFuture with which we create the root slot
    +	 * @param allocatedSlotRequestId slot request id of the underlying allocated slot which can be used
    +	 *                               to cancel the pending slot request or release the allocated slot
    +	 * @return New root slot
    +	 */
    +	public MultiTaskSlot createRootSlot(
    +			SlotRequestId slotRequestId,
    +			CompletableFuture<SlotContext> slotContextFuture,
    +			SlotRequestId allocatedSlotRequestId) {
    +		final MultiTaskSlot rootMultiTaskSlot = new MultiTaskSlot(
    +			slotRequestId,
    +			slotContextFuture,
    +			allocatedSlotRequestId);
    +
    +		allTaskSlots.put(slotRequestId, rootMultiTaskSlot);
    +		unresolvedRootSlots.put(slotRequestId, rootMultiTaskSlot);
    +
    +		// add the root node to the set of resolved root nodes once the SlotContext future has been completed
    +		// and we know the slot's TaskManagerLocation
    +		slotContextFuture.whenComplete(
    +			(SlotContext slotContext, Throwable throwable) -> {
    +				if (slotContext != null) {
    +					final MultiTaskSlot resolvedRootNode = unresolvedRootSlots.remove(slotRequestId);
    +
    +					if (resolvedRootNode != null) {
    +						final Set<MultiTaskSlot> innerCollection = resolvedRootSlots.computeIfAbsent(
    --- End diff --
    
    In theory the signature of this method allows concurrent modifications on `resolvedRootSlots`. Maybe a comment why this cannot happen would be nice; perhaps with`@GuardedBy`.


---

[GitHub] flink pull request #5091: [FLINK-7956] [flip6] Add support for queued schedu...

Posted by tillrohrmann <gi...@git.apache.org>.
Github user tillrohrmann commented on a diff in the pull request:

    https://github.com/apache/flink/pull/5091#discussion_r156888058
  
    --- Diff: flink-runtime/src/main/java/org/apache/flink/runtime/jobmaster/slotpool/SlotSharingManager.java ---
    @@ -0,0 +1,722 @@
    +/*
    + * Licensed to the Apache Software Foundation (ASF) under one
    + * or more contributor license agreements.  See the NOTICE file
    + * distributed with this work for additional information
    + * regarding copyright ownership.  The ASF licenses this file
    + * to you under the Apache License, Version 2.0 (the
    + * "License"); you may not use this file except in compliance
    + * with the License.  You may obtain a copy of the License at
    + *
    + *     http://www.apache.org/licenses/LICENSE-2.0
    + *
    + * Unless required by applicable law or agreed to in writing, software
    + * distributed under the License is distributed on an "AS IS" BASIS,
    + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    + * See the License for the specific language governing permissions and
    + * limitations under the License.
    + */
    +
    +package org.apache.flink.runtime.jobmaster.slotpool;
    +
    +import org.apache.flink.annotation.VisibleForTesting;
    +import org.apache.flink.runtime.jobmaster.LogicalSlot;
    +import org.apache.flink.runtime.jobmaster.SlotContext;
    +import org.apache.flink.runtime.jobmaster.SlotOwner;
    +import org.apache.flink.runtime.jobmaster.SlotRequestId;
    +import org.apache.flink.runtime.instance.SlotSharingGroupId;
    +import org.apache.flink.runtime.jobmanager.scheduler.Locality;
    +import org.apache.flink.runtime.taskmanager.TaskManagerLocation;
    +import org.apache.flink.util.AbstractID;
    +import org.apache.flink.util.FlinkException;
    +import org.apache.flink.util.Preconditions;
    +
    +import javax.annotation.Nullable;
    +
    +import java.util.AbstractCollection;
    +import java.util.Collection;
    +import java.util.Collections;
    +import java.util.HashMap;
    +import java.util.HashSet;
    +import java.util.Iterator;
    +import java.util.Map;
    +import java.util.Objects;
    +import java.util.Set;
    +import java.util.concurrent.CompletableFuture;
    +
    +/**
    + * Manager which is responsible for slot sharing. Slot sharing allows to run different
    + * tasks in the same slot and to realize co-location constraints.
    + *
    + * <p>The SlotSharingManager allows to create a hierarchy of {@link TaskSlot} such that
    + * every {@link TaskSlot} is uniquely identified by a {@link SlotRequestId} identifying
    + * the request for the TaskSlot and a {@link AbstractID} identifying the task or the
    + * co-location constraint running in this slot.
    + *
    + * <p>The {@link TaskSlot} hierarchy is implemented by {@link MultiTaskSlot} and
    + * {@link SingleTaskSlot}. The former class represents inner nodes which can contain
    + * a number of other {@link TaskSlot} and the latter class represents the leave nodes.
    + * The hierarchy starts with a root {@link MultiTaskSlot} which is a future
    + * {@link SlotContext} assigned. The {@link SlotContext} represents the allocated slot
    + * on the TaskExecutor in which all slots of this hierarchy run. A {@link MultiTaskSlot}
    + * can be assigned multiple {@link SingleTaskSlot} or {@link MultiTaskSlot} if and only if
    + * the task slot does not yet contain another child with the same {@link AbstractID} identifying
    + * the actual task or the co-location constraint.
    + *
    + * <p>Normal slot sharing is represented by a root {@link MultiTaskSlot} which contains a set
    + * of {@link SingleTaskSlot} on the second layer. Each {@link SingleTaskSlot} represents a different
    + * task.
    + *
    + * <p>Co-location constraints are modeled by adding a {@link MultiTaskSlot} to the root node. The co-location
    + * constraint is uniquely identified by a {@link AbstractID} such that we cannot add a second co-located
    + * {@link MultiTaskSlot} to the same root node. Now all co-located tasks will be added to co-located
    + * multi task slot.
    + */
    +public class SlotSharingManager {
    +
    +	private final SlotSharingGroupId slotSharingGroupId;
    +
    +	// needed to release allocated slots after a complete multi task slot hierarchy has been released
    --- End diff --
    
    good point. Will change it.


---

[GitHub] flink pull request #5091: [FLINK-7956] [flip6] Add support for queued schedu...

Posted by tillrohrmann <gi...@git.apache.org>.
Github user tillrohrmann commented on a diff in the pull request:

    https://github.com/apache/flink/pull/5091#discussion_r156902096
  
    --- Diff: flink-runtime/src/main/java/org/apache/flink/runtime/jobmaster/slotpool/SlotSharingManager.java ---
    @@ -0,0 +1,722 @@
    +/*
    + * Licensed to the Apache Software Foundation (ASF) under one
    + * or more contributor license agreements.  See the NOTICE file
    + * distributed with this work for additional information
    + * regarding copyright ownership.  The ASF licenses this file
    + * to you under the Apache License, Version 2.0 (the
    + * "License"); you may not use this file except in compliance
    + * with the License.  You may obtain a copy of the License at
    + *
    + *     http://www.apache.org/licenses/LICENSE-2.0
    + *
    + * Unless required by applicable law or agreed to in writing, software
    + * distributed under the License is distributed on an "AS IS" BASIS,
    + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    + * See the License for the specific language governing permissions and
    + * limitations under the License.
    + */
    +
    +package org.apache.flink.runtime.jobmaster.slotpool;
    +
    +import org.apache.flink.annotation.VisibleForTesting;
    +import org.apache.flink.runtime.jobmaster.LogicalSlot;
    +import org.apache.flink.runtime.jobmaster.SlotContext;
    +import org.apache.flink.runtime.jobmaster.SlotOwner;
    +import org.apache.flink.runtime.jobmaster.SlotRequestId;
    +import org.apache.flink.runtime.instance.SlotSharingGroupId;
    +import org.apache.flink.runtime.jobmanager.scheduler.Locality;
    +import org.apache.flink.runtime.taskmanager.TaskManagerLocation;
    +import org.apache.flink.util.AbstractID;
    +import org.apache.flink.util.FlinkException;
    +import org.apache.flink.util.Preconditions;
    +
    +import javax.annotation.Nullable;
    +
    +import java.util.AbstractCollection;
    +import java.util.Collection;
    +import java.util.Collections;
    +import java.util.HashMap;
    +import java.util.HashSet;
    +import java.util.Iterator;
    +import java.util.Map;
    +import java.util.Objects;
    +import java.util.Set;
    +import java.util.concurrent.CompletableFuture;
    +
    +/**
    + * Manager which is responsible for slot sharing. Slot sharing allows to run different
    + * tasks in the same slot and to realize co-location constraints.
    + *
    + * <p>The SlotSharingManager allows to create a hierarchy of {@link TaskSlot} such that
    + * every {@link TaskSlot} is uniquely identified by a {@link SlotRequestId} identifying
    + * the request for the TaskSlot and a {@link AbstractID} identifying the task or the
    + * co-location constraint running in this slot.
    + *
    + * <p>The {@link TaskSlot} hierarchy is implemented by {@link MultiTaskSlot} and
    + * {@link SingleTaskSlot}. The former class represents inner nodes which can contain
    + * a number of other {@link TaskSlot} and the latter class represents the leave nodes.
    + * The hierarchy starts with a root {@link MultiTaskSlot} which is a future
    + * {@link SlotContext} assigned. The {@link SlotContext} represents the allocated slot
    + * on the TaskExecutor in which all slots of this hierarchy run. A {@link MultiTaskSlot}
    + * can be assigned multiple {@link SingleTaskSlot} or {@link MultiTaskSlot} if and only if
    + * the task slot does not yet contain another child with the same {@link AbstractID} identifying
    + * the actual task or the co-location constraint.
    + *
    + * <p>Normal slot sharing is represented by a root {@link MultiTaskSlot} which contains a set
    + * of {@link SingleTaskSlot} on the second layer. Each {@link SingleTaskSlot} represents a different
    + * task.
    + *
    + * <p>Co-location constraints are modeled by adding a {@link MultiTaskSlot} to the root node. The co-location
    + * constraint is uniquely identified by a {@link AbstractID} such that we cannot add a second co-located
    + * {@link MultiTaskSlot} to the same root node. Now all co-located tasks will be added to co-located
    + * multi task slot.
    + */
    +public class SlotSharingManager {
    +
    +	private final SlotSharingGroupId slotSharingGroupId;
    +
    +	// needed to release allocated slots after a complete multi task slot hierarchy has been released
    +	private final AllocatedSlotActions allocatedSlotActions;
    +
    +	// owner of the slots to which to return them when they are released from the outside
    +	private final SlotOwner slotOwner;
    +
    +	private final Map<SlotRequestId, TaskSlot> allTaskSlots;
    +
    +	// Root nodes which have not been completed because the allocated slot is still pending
    +	private final Map<SlotRequestId, MultiTaskSlot> unresolvedRootSlots;
    +
    +	// Root nodes which have been completed (the underlying allocated slot has been assigned)
    +	private final Map<TaskManagerLocation, Set<MultiTaskSlot>> resolvedRootSlots;
    +
    +	// Internal class to iterate over all resolved root slots
    +	private ResolvedRootSlotValues resolvedMultiTaskSlotValues;
    +
    +	public SlotSharingManager(
    +			SlotSharingGroupId slotSharingGroupId,
    +			AllocatedSlotActions allocatedSlotActions,
    +			SlotOwner slotOwner) {
    +		this.slotSharingGroupId = Preconditions.checkNotNull(slotSharingGroupId);
    +		this.allocatedSlotActions = Preconditions.checkNotNull(allocatedSlotActions);
    +		this.slotOwner = Preconditions.checkNotNull(slotOwner);
    +
    +		allTaskSlots = new HashMap<>(16);
    +		unresolvedRootSlots = new HashMap<>(16);
    +		resolvedRootSlots = new HashMap<>(16);
    +
    +		resolvedMultiTaskSlotValues = null;
    +	}
    +
    +	public boolean isEmpty() {
    +		return allTaskSlots.isEmpty();
    +	}
    +
    +	public boolean contains(SlotRequestId slotRequestId) {
    +		return allTaskSlots.containsKey(slotRequestId);
    +	}
    +
    +	@Nullable
    +	public TaskSlot getTaskSlot(SlotRequestId slotRequestId) {
    +		return allTaskSlots.get(slotRequestId);
    +	}
    +
    +	/**
    +	 * Creates a new root slot with the given {@link SlotRequestId}, {@link SlotContext} future and
    +	 * the {@link SlotRequestId} of the allocated slot.
    +	 *
    +	 * @param slotRequestId of the root slot
    +	 * @param slotContextFuture with which we create the root slot
    +	 * @param allocatedSlotRequestId slot request id of the underlying allocated slot which can be used
    +	 *                               to cancel the pending slot request or release the allocated slot
    +	 * @return New root slot
    +	 */
    +	public MultiTaskSlot createRootSlot(
    +			SlotRequestId slotRequestId,
    +			CompletableFuture<SlotContext> slotContextFuture,
    +			SlotRequestId allocatedSlotRequestId) {
    +		final MultiTaskSlot rootMultiTaskSlot = new MultiTaskSlot(
    +			slotRequestId,
    +			slotContextFuture,
    +			allocatedSlotRequestId);
    +
    +		allTaskSlots.put(slotRequestId, rootMultiTaskSlot);
    +		unresolvedRootSlots.put(slotRequestId, rootMultiTaskSlot);
    +
    +		// add the root node to the set of resolved root nodes once the SlotContext future has been completed
    +		// and we know the slot's TaskManagerLocation
    +		slotContextFuture.whenComplete(
    +			(SlotContext slotContext, Throwable throwable) -> {
    +				if (slotContext != null) {
    +					final MultiTaskSlot resolvedRootNode = unresolvedRootSlots.remove(slotRequestId);
    +
    +					if (resolvedRootNode != null) {
    +						final Set<MultiTaskSlot> innerCollection = resolvedRootSlots.computeIfAbsent(
    +							slotContext.getTaskManagerLocation(),
    +							taskManagerLocation -> new HashSet<>(4));
    +
    +						innerCollection.add(resolvedRootNode);
    +					}
    +				} else {
    +					rootMultiTaskSlot.release(throwable);
    +				}
    +			});
    +
    +		return rootMultiTaskSlot;
    +	}
    +
    +	/**
    +	 * Gets a resolved root slot which does not yet contain the given groupId. First the given set of
    +	 * preferred locations is checked.
    +	 *
    +	 * @param groupId which the returned slot must not contain
    +	 * @param locationPreferences specifying which locations are preferred
    +	 * @return the resolved root slot and its locality wrt to the specified location preferences
    +	 * 		or null if there was no root slot which did not contain the given groupId
    +	 */
    +	@Nullable
    +	public MultiTaskSlotLocality getResolvedRootSlot(AbstractID groupId, Collection<TaskManagerLocation> locationPreferences) {
    +		Preconditions.checkNotNull(locationPreferences);
    +
    +		if (locationPreferences.isEmpty()) {
    +			return getResolvedRootSlotWithoutLocationPreferences(groupId);
    +		} else {
    +			return getResolvedRootSlotWithLocationPreferences(groupId, locationPreferences);
    +		}
    +	}
    +
    +	/**
    +	 * Gets a resolved root slot which does not yet contain the given groupId. The method will try to
    +	 * find a slot of a TaskManager contained in the collection of preferred locations. If there is no such slot
    +	 * with free capacities available, then the method will look for slots of TaskManager which run on the same
    +	 * machine as the TaskManager in the collection of preferred locations. If there is no such slot, then any slot
    +	 * with free capacities is returned. If there is no such slot, then null is returned.
    +	 *
    +	 * @param groupId which the returned slot must not contain
    +	 * @param locationPreferences specifying which locations are preferred
    +	 * @return the resolved root slot and its locality wrt to the specified location preferences
    +	 * 		or null if there was not root slot which did not contain the given groupId
    +	 */
    +	@Nullable
    +	private MultiTaskSlotLocality getResolvedRootSlotWithLocationPreferences(AbstractID groupId, Collection<TaskManagerLocation> locationPreferences) {
    +		Preconditions.checkNotNull(groupId);
    +		Preconditions.checkNotNull(locationPreferences);
    +		final Set<String> hostnameSet = new HashSet<>();
    +
    +		for (TaskManagerLocation locationPreference : locationPreferences) {
    +			final Set<MultiTaskSlot> multiTaskSlots = resolvedRootSlots.get(locationPreference);
    +
    +			if (multiTaskSlots != null) {
    +				for (MultiTaskSlot multiTaskSlot : multiTaskSlots) {
    +					if (!multiTaskSlot.contains(groupId)) {
    +						return MultiTaskSlotLocality.of(multiTaskSlot, Locality.LOCAL);
    +					}
    +				}
    +
    +				hostnameSet.add(locationPreference.getHostname());
    +			}
    +		}
    +
    +		MultiTaskSlot nonLocalMultiTaskSlot = null;
    +
    +		for (Map.Entry<TaskManagerLocation, Set<MultiTaskSlot>> taskManagerLocationSetEntry : resolvedRootSlots.entrySet()) {
    +			if (hostnameSet.contains(taskManagerLocationSetEntry.getKey().getHostname())) {
    +				for (MultiTaskSlot multiTaskSlot : taskManagerLocationSetEntry.getValue()) {
    +					if (!multiTaskSlot.contains(groupId)) {
    +						return MultiTaskSlotLocality.of(multiTaskSlot, Locality.HOST_LOCAL);
    +					}
    +				}
    +			} else if (nonLocalMultiTaskSlot == null) {
    +				for (MultiTaskSlot multiTaskSlot : taskManagerLocationSetEntry.getValue()) {
    +					if (!multiTaskSlot.contains(groupId)) {
    +						nonLocalMultiTaskSlot = multiTaskSlot;
    +					}
    +				}
    +			}
    +		}
    +
    +		if (nonLocalMultiTaskSlot != null) {
    +			return MultiTaskSlotLocality.of(nonLocalMultiTaskSlot, Locality.NON_LOCAL);
    +		} else {
    +			return null;
    +		}
    +	}
    +
    +	/**
    +	 * Gets a resolved slot which does not yet contain the given groupId without any location
    +	 * preferences.
    +	 *
    +	 * @param groupId which the returned slot must not contain
    +	 * @return the resolved slot or null if there was no root slot with free capacities
    +	 */
    +	@Nullable
    +	private MultiTaskSlotLocality getResolvedRootSlotWithoutLocationPreferences(AbstractID groupId) {
    +		Preconditions.checkNotNull(groupId);
    +
    +		for (Set<MultiTaskSlot> multiTaskSlots : resolvedRootSlots.values()) {
    +			for (MultiTaskSlot multiTaskSlot : multiTaskSlots) {
    +				if (!multiTaskSlot.contains(groupId)) {
    +					return MultiTaskSlotLocality.of(multiTaskSlot, Locality.UNCONSTRAINED);
    +				}
    +			}
    +		}
    +
    +		return null;
    +	}
    +
    +	/**
    +	 * Gets an unresolved slot which does not yet contain the given groupId. An unresolved
    +	 * slot is a slot whose underlying allocated slot has not been allocated yet.
    +	 *
    +	 * @param groupId which the returned slot must not contain
    +	 * @return the unresolved slot or null if there was no root slot with free capacities
    +	 */
    +	@Nullable
    +	public MultiTaskSlot getUnresolvedRootSlot(AbstractID groupId) {
    +		for (MultiTaskSlot multiTaskSlot : unresolvedRootSlots.values()) {
    +			if (!multiTaskSlot.contains(groupId)) {
    +				return multiTaskSlot;
    +			}
    +		}
    +
    +		return null;
    +	}
    +
    +	// ------------------------------------------------------------------------
    +	// Inner classes: TaskSlot hierarchy and helper classes
    +	// ------------------------------------------------------------------------
    +
    +	/**
    +	 * Helper class which contains a {@link MultiTaskSlot} and its {@link Locality}.
    +	 */
    +	public static final class MultiTaskSlotLocality {
    +		private final MultiTaskSlot multiTaskSlot;
    +
    +		private final Locality locality;
    +
    +		public MultiTaskSlotLocality(MultiTaskSlot multiTaskSlot, Locality locality) {
    +			this.multiTaskSlot = Preconditions.checkNotNull(multiTaskSlot);
    +			this.locality = Preconditions.checkNotNull(locality);
    +		}
    +
    +		public MultiTaskSlot getMultiTaskSlot() {
    +			return multiTaskSlot;
    +		}
    +
    +		public Locality getLocality() {
    +			return locality;
    +		}
    +
    +		public static MultiTaskSlotLocality of(MultiTaskSlot multiTaskSlot, Locality locality) {
    +			return new MultiTaskSlotLocality(multiTaskSlot, locality);
    +		}
    +	}
    +
    +	/**
    +	 * Base class for all task slots.
    +	 */
    +	public abstract static class TaskSlot {
    +		// every TaskSlot has an associated slot request id
    +		private final SlotRequestId slotRequestId;
    +
    +		// all task slots except for the root slots have a group id assigned
    +		@Nullable
    +		private final AbstractID groupId;
    +
    +		protected TaskSlot(SlotRequestId slotRequestId, @Nullable AbstractID groupId) {
    +			this.slotRequestId = Preconditions.checkNotNull(slotRequestId);
    +			this.groupId = groupId;
    +		}
    +
    +		public SlotRequestId getSlotRequestId() {
    +			return slotRequestId;
    +		}
    +
    +		@Nullable
    +		public AbstractID getGroupId() {
    +			return groupId;
    +		}
    +
    +		/**
    +		 * Check whether the task slot contains the given groupId.
    +		 *
    +		 * @param groupId which to check whether it is contained
    +		 * @return true if the task slot contains the given groupId, otherwise false
    +		 */
    +		public boolean contains(AbstractID groupId) {
    +			return Objects.equals(this.groupId, groupId);
    +		}
    +
    +		/**
    +		 * Release the task slot.
    +		 *
    +		 * @param cause for the release
    +		 * @return true if the slot could be released, otherwise false
    +		 */
    +		public abstract boolean release(Throwable cause);
    +	}
    +
    +	/**
    +	 * {@link TaskSlot} implementation which can have multiple other task slots assigned as children.
    +	 */
    +	public final class MultiTaskSlot extends TaskSlot implements AllocatedSlot.Payload {
    +
    +		private final Map<AbstractID, TaskSlot> children;
    +
    +		// the root node has its parent set to null
    +		@Nullable
    +		private final MultiTaskSlot parent;
    +
    +		// underlying allocated slot
    +		private final CompletableFuture<SlotContext> slotContextFuture;
    +
    +		// slot request id of the allocated slot
    +		@Nullable
    +		private final SlotRequestId allocatedSlotRequestId;
    +
    +		// true if we are currently releasing our children
    +		private boolean releasingChildren;
    +
    +		private MultiTaskSlot(
    +				SlotRequestId slotRequestId,
    +				AbstractID groupId,
    +				MultiTaskSlot parent) {
    +			this(
    +				slotRequestId,
    +				groupId,
    +				Preconditions.checkNotNull(parent),
    +				parent.getSlotContextFuture(),
    +				null);
    +		}
    +
    +		private MultiTaskSlot(
    +				SlotRequestId slotRequestId,
    +				CompletableFuture<SlotContext> slotContextFuture,
    +				SlotRequestId allocatedSlotRequestId) {
    +			this(
    +				slotRequestId,
    +				null,
    +				null,
    +				slotContextFuture,
    +				allocatedSlotRequestId);
    +		}
    +
    +		private MultiTaskSlot(
    +				SlotRequestId slotRequestId,
    +				@Nullable AbstractID groupId,
    +				MultiTaskSlot parent,
    +				CompletableFuture<SlotContext> slotContextFuture,
    +				SlotRequestId allocatedSlotRequestId) {
    +			super(slotRequestId, groupId);
    +
    +			this.parent = parent;
    +			this.slotContextFuture = Preconditions.checkNotNull(slotContextFuture);
    +			this.allocatedSlotRequestId = allocatedSlotRequestId;
    +
    +			this.children = new HashMap<>(16);
    +			this.releasingChildren = false;
    +
    +			slotContextFuture.whenComplete(
    +				(SlotContext ignored, Throwable throwable) -> {
    +					if (throwable != null) {
    +						release(throwable);
    +					}
    +				});
    +		}
    +
    +		public CompletableFuture<SlotContext> getSlotContextFuture() {
    +			return slotContextFuture;
    +		}
    +
    +		/**
    +		 * Allocates a {@link MultiTaskSlot} and registers it under the given groupId at
    +		 * this {@link MultiTaskSlot}.
    +		 *
    +		 * @param slotRequestId of the new multi task slot
    +		 * @param groupId under which the new multi task slot is registered
    +		 * @return the newly allocated {@link MultiTaskSlot}
    +		 */
    +		MultiTaskSlot allocateMultiTaskSlot(SlotRequestId slotRequestId, AbstractID groupId) {
    +			Preconditions.checkState(!super.contains(groupId));
    +
    +			final MultiTaskSlot inner = new MultiTaskSlot(
    +				slotRequestId,
    +				groupId,
    +				this);
    +
    +			children.put(groupId, inner);
    +
    +			// register the newly allocated slot also at the SlotSharingManager
    +			allTaskSlots.put(slotRequestId, inner);
    +
    +			return inner;
    +		}
    +
    +		/**
    +		 * Allocates a {@link SingleTaskSlot} and registeres it under the given groupId at
    +		 * this {@link MultiTaskSlot}.
    +		 *
    +		 * @param slotRequestId of the new single task slot
    +		 * @param groupId under which the new single task slot is registered
    +		 * @param locality of the allocation
    +		 * @return the newly allocated {@link SingleTaskSlot}
    +		 */
    +		SingleTaskSlot allocateSingleTaskSlot(
    +				SlotRequestId slotRequestId,
    +				AbstractID groupId,
    +				Locality locality) {
    +			Preconditions.checkState(!super.contains(groupId));
    +
    +			final SingleTaskSlot leave = new SingleTaskSlot(
    --- End diff --
    
    will change.


---

[GitHub] flink pull request #5091: [FLINK-7956] [flip6] Add support for queued schedu...

Posted by GJL <gi...@git.apache.org>.
Github user GJL commented on a diff in the pull request:

    https://github.com/apache/flink/pull/5091#discussion_r155604499
  
    --- Diff: flink-runtime/src/main/java/org/apache/flink/runtime/jobmaster/slotpool/SlotPool.java ---
    @@ -266,104 +279,367 @@ public void disconnectResourceManager() {
     	// ------------------------------------------------------------------------
     
     	@Override
    -	public CompletableFuture<SimpleSlot> allocateSlot(
    -			SlotRequestID requestId,
    -			ScheduledUnit task,
    -			ResourceProfile resources,
    -			Iterable<TaskManagerLocation> locationPreferences,
    +	public CompletableFuture<LogicalSlot> allocateSlot(
    +			SlotRequestId slotRequestId,
    +			ScheduledUnit scheduledUnit,
    +			ResourceProfile resourceProfile,
    +			Collection<TaskManagerLocation> locationPreferences,
    +			boolean allowQueuedScheduling,
     			Time timeout) {
     
    -		return internalAllocateSlot(requestId, task, resources, locationPreferences);
    +		return internalAllocateSlot(
    +			slotRequestId,
    +			scheduledUnit,
    +			resourceProfile,
    +			locationPreferences,
    +			allowQueuedScheduling);
     	}
     
    -	@Override
    -	public void returnAllocatedSlot(Slot slot) {
    -		internalReturnAllocatedSlot(slot);
    +	private CompletableFuture<LogicalSlot> internalAllocateSlot(
    +			SlotRequestId slotRequestId,
    +			ScheduledUnit task,
    +			ResourceProfile resourceProfile,
    +			Collection<TaskManagerLocation> locationPreferences,
    +			boolean allowQueuedScheduling) {
    +
    +		final SlotSharingGroupId slotSharingGroupId = task.getSlotSharingGroupId();
    +
    +		if (slotSharingGroupId != null) {
    +			// allocate slot with slot sharing
    +			final SlotSharingManager multiTaskSlotManager = slotSharingManagers.computeIfAbsent(
    +				slotSharingGroupId,
    +				id -> new SlotSharingManager(
    +					id,
    +					this,
    +					providerAndOwner));
    +
    +			final SlotSharingManager.MultiTaskSlotLocality multiTaskSlotFuture;
    --- End diff --
    
    The variable name is confusing. `multiTaskSlotFuture` is not of type `Future`.


---

[GitHub] flink pull request #5091: [FLINK-7956] [flip6] Add support for queued schedu...

Posted by tillrohrmann <gi...@git.apache.org>.
Github user tillrohrmann commented on a diff in the pull request:

    https://github.com/apache/flink/pull/5091#discussion_r156896571
  
    --- Diff: flink-runtime/src/main/java/org/apache/flink/runtime/jobmaster/slotpool/SlotPool.java ---
    @@ -266,104 +279,367 @@ public void disconnectResourceManager() {
     	// ------------------------------------------------------------------------
     
     	@Override
    -	public CompletableFuture<SimpleSlot> allocateSlot(
    -			SlotRequestID requestId,
    -			ScheduledUnit task,
    -			ResourceProfile resources,
    -			Iterable<TaskManagerLocation> locationPreferences,
    +	public CompletableFuture<LogicalSlot> allocateSlot(
    +			SlotRequestId slotRequestId,
    +			ScheduledUnit scheduledUnit,
    +			ResourceProfile resourceProfile,
    +			Collection<TaskManagerLocation> locationPreferences,
    +			boolean allowQueuedScheduling,
     			Time timeout) {
     
    -		return internalAllocateSlot(requestId, task, resources, locationPreferences);
    +		return internalAllocateSlot(
    +			slotRequestId,
    +			scheduledUnit,
    +			resourceProfile,
    +			locationPreferences,
    +			allowQueuedScheduling);
     	}
     
    -	@Override
    -	public void returnAllocatedSlot(Slot slot) {
    -		internalReturnAllocatedSlot(slot);
    +	private CompletableFuture<LogicalSlot> internalAllocateSlot(
    +			SlotRequestId slotRequestId,
    +			ScheduledUnit task,
    +			ResourceProfile resourceProfile,
    +			Collection<TaskManagerLocation> locationPreferences,
    +			boolean allowQueuedScheduling) {
    +
    +		final SlotSharingGroupId slotSharingGroupId = task.getSlotSharingGroupId();
    +
    +		if (slotSharingGroupId != null) {
    +			// allocate slot with slot sharing
    +			final SlotSharingManager multiTaskSlotManager = slotSharingManagers.computeIfAbsent(
    +				slotSharingGroupId,
    +				id -> new SlotSharingManager(
    +					id,
    +					this,
    +					providerAndOwner));
    +
    +			final SlotSharingManager.MultiTaskSlotLocality multiTaskSlotFuture;
    +
    +			try {
    +				if (task.getCoLocationConstraint() != null) {
    +					multiTaskSlotFuture = allocateCoLocatedMultiTaskSlot(
    +						task.getCoLocationConstraint(),
    +						multiTaskSlotManager,
    +						resourceProfile,
    +						locationPreferences,
    +						allowQueuedScheduling);
    +				} else {
    +					multiTaskSlotFuture = allocateMultiTaskSlot(
    +						task.getJobVertexId(), multiTaskSlotManager,
    +						resourceProfile,
    +						locationPreferences,
    +						allowQueuedScheduling);
    +				}
    +			} catch (NoResourceAvailableException noResourceException) {
    +				return FutureUtils.completedExceptionally(noResourceException);
    +			}
    +
    +			// sanity check
    +			Preconditions.checkState(!multiTaskSlotFuture.getMultiTaskSlot().contains(task.getJobVertexId()));
    +
    +			final SlotSharingManager.SingleTaskSlot leave = multiTaskSlotFuture.getMultiTaskSlot().allocateSingleTaskSlot(
    +				slotRequestId,
    +				task.getJobVertexId(),
    +				multiTaskSlotFuture.getLocality());
    +
    +			return leave.getLogicalSlotFuture();
    +		} else {
    +			// request an allocated slot to assign a single logical slot to
    +			CompletableFuture<SlotAndLocality> slotAndLocalityFuture = requestAllocatedSlot(
    +				slotRequestId,
    +				resourceProfile,
    +				locationPreferences,
    +				allowQueuedScheduling);
    +
    +			return slotAndLocalityFuture.thenApply(
    +				(SlotAndLocality slotAndLocality) -> {
    +					final AllocatedSlot allocatedSlot = slotAndLocality.getSlot();
    +
    +					final SingleLogicalSlot singleTaskSlot = new SingleLogicalSlot(
    +						slotRequestId,
    +						allocatedSlot,
    +						null,
    +						slotAndLocality.getLocality(),
    +						providerAndOwner);
    +
    +					if (allocatedSlot.tryAssignPayload(singleTaskSlot)) {
    +						return singleTaskSlot;
    +					} else {
    +						final FlinkException flinkException = new FlinkException("Could not assign payload to allocated slot " + allocatedSlot.getAllocationId() + '.');
    +						releaseSlot(slotRequestId, null, flinkException);
    +						throw new CompletionException(flinkException);
    +					}
    +				});
    +		}
     	}
     
    -	@Override
    -	public CompletableFuture<Acknowledge> cancelSlotAllocation(SlotRequestID requestId) {
    -		final PendingRequest pendingRequest = removePendingRequest(requestId);
    +	/**
    +	 * Allocates a co-located {@link SlotSharingManager.MultiTaskSlot} for the given {@link CoLocationConstraint}.
    +	 *
    +	 * <p>If allowQueuedScheduling is true, then the returned {@link SlotSharingManager.MultiTaskSlot} can be
    +	 * uncompleted.
    +	 *
    +	 * @param coLocationConstraint for which to allocate a {@link SlotSharingManager.MultiTaskSlot}
    +	 * @param multiTaskSlotManager responsible for the slot sharing group for which to allocate the slot
    +	 * @param resourceProfile specifying the requirements for the requested slot
    +	 * @param locationPreferences containing preferred TaskExecutors on which to allocate the slot
    +	 * @param allowQueuedScheduling true if queued scheduling (the returned task slot must not be completed yet) is allowed, otherwise false
    +	 * @return A {@link SlotSharingManager.MultiTaskSlotLocality} which contains the allocated{@link SlotSharingManager.MultiTaskSlot}
    +	 * 		and its locality wrt the given location preferences
    +	 * @throws NoResourceAvailableException if no task slot could be allocated
    +	 */
    +	private SlotSharingManager.MultiTaskSlotLocality allocateCoLocatedMultiTaskSlot(
    +			CoLocationConstraint coLocationConstraint,
    +			SlotSharingManager multiTaskSlotManager,
    +			ResourceProfile resourceProfile,
    +			Collection<TaskManagerLocation> locationPreferences,
    +			boolean allowQueuedScheduling) throws NoResourceAvailableException {
    +		final SlotRequestId coLocationSlotRequestId = coLocationConstraint.getSlotRequestId();
    +
    +		if (coLocationSlotRequestId != null) {
    +			// we have a slot assigned --> try to retrieve it
    +			final SlotSharingManager.TaskSlot taskSlot = multiTaskSlotManager.getTaskSlot(coLocationSlotRequestId);
    +
    +			if (taskSlot != null) {
    +				Preconditions.checkState(taskSlot instanceof SlotSharingManager.MultiTaskSlot);
    +				return SlotSharingManager.MultiTaskSlotLocality.of(((SlotSharingManager.MultiTaskSlot) taskSlot), Locality.LOCAL);
    +			} else {
    +				// the slot may have been cancelled in the mean time
    +				coLocationConstraint.setSlotRequestId(null);
    +			}
    +		}
     
    -		if (pendingRequest != null) {
    -			failPendingRequest(pendingRequest, new CancellationException("Allocation with request id" + requestId + " cancelled."));
    +		final Collection<TaskManagerLocation> actualLocationPreferences;
    +
    +		if (coLocationConstraint.isAssigned()) {
    +			actualLocationPreferences = Collections.singleton(coLocationConstraint.getLocation());
     		} else {
    -			final Slot slot = allocatedSlots.get(requestId);
    +			actualLocationPreferences = locationPreferences;
    +		}
    +
    +		// get a new multi task slot
    +		final SlotSharingManager.MultiTaskSlotLocality multiTaskSlotLocality = allocateMultiTaskSlot(
    +			coLocationConstraint.getGroupId(), multiTaskSlotManager,
    +			resourceProfile,
    +			actualLocationPreferences,
    +			allowQueuedScheduling);
    +
    +		// check whether we fulfill the co-location constraint
    +		if (coLocationConstraint.isAssigned() && multiTaskSlotLocality.getLocality() != Locality.LOCAL) {
    +			multiTaskSlotLocality.getMultiTaskSlot().release(
    +				new FlinkException("Multi task slot is not local and, thus, does not fulfill the co-location constraint."));
     
    -			if (slot != null) {
    -				LOG.info("Returning allocated slot {} because the corresponding allocation request {} was cancelled.", slot, requestId);
    -				if (slot.markCancelled()) {
    -					internalReturnAllocatedSlot(slot);
    +			throw new NoResourceAvailableException("Could not allocate a local multi task slot for the " +
    +				"co location constraint " + coLocationConstraint + '.');
    +		}
    +
    +		final SlotRequestId slotRequestId = new SlotRequestId();
    +		final SlotSharingManager.MultiTaskSlot coLocationSlot = multiTaskSlotLocality.getMultiTaskSlot().allocateMultiTaskSlot(
    +			slotRequestId,
    +			coLocationConstraint.getGroupId());
    +
    +		// mark the requested slot as co-located slot for other co-located tasks
    +		coLocationConstraint.setSlotRequestId(slotRequestId);
    +
    +		// lock the co-location constraint once we have obtained the allocated slot
    +		coLocationSlot.getSlotContextFuture().whenComplete(
    +			(SlotContext slotContext, Throwable throwable) -> {
    +				if (throwable == null) {
    --- End diff --
    
    I will log the throwable here.


---

[GitHub] flink pull request #5091: [FLINK-7956] [flip6] Add support for queued schedu...

Posted by tillrohrmann <gi...@git.apache.org>.
Github user tillrohrmann commented on a diff in the pull request:

    https://github.com/apache/flink/pull/5091#discussion_r156887632
  
    --- Diff: flink-runtime/src/test/java/org/apache/flink/runtime/jobmanager/scheduler/SchedulerTest.java ---
    @@ -0,0 +1,97 @@
    +/*
    + * Licensed to the Apache Software Foundation (ASF) under one
    + * or more contributor license agreements.  See the NOTICE file
    + * distributed with this work for additional information
    + * regarding copyright ownership.  The ASF licenses this file
    + * to you under the Apache License, Version 2.0 (the
    + * "License"); you may not use this file except in compliance
    + * with the License.  You may obtain a copy of the License at
    + *
    + *     http://www.apache.org/licenses/LICENSE-2.0
    + *
    + * Unless required by applicable law or agreed to in writing, software
    + * distributed under the License is distributed on an "AS IS" BASIS,
    + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    + * See the License for the specific language governing permissions and
    + * limitations under the License.
    + */
    +
    +package org.apache.flink.runtime.jobmanager.scheduler;
    +
    +import org.apache.flink.runtime.instance.Instance;
    +import org.apache.flink.runtime.testingUtils.TestingUtils;
    +import org.apache.flink.util.TestLogger;
    +
    +import org.junit.Test;
    +
    +import static org.apache.flink.runtime.jobmanager.scheduler.SchedulerTestUtils.getRandomInstance;
    +import static org.junit.Assert.assertEquals;
    +import static org.junit.Assert.assertFalse;
    +import static org.junit.Assert.fail;
    +
    +public class SchedulerTest extends TestLogger {
    +
    +	@Test
    +	public void testAddAndRemoveInstance() {
    +		try {
    +			Scheduler scheduler = new Scheduler(TestingUtils.defaultExecutionContext());
    +
    +			Instance i1 = getRandomInstance(2);
    +			Instance i2 = getRandomInstance(2);
    +			Instance i3 = getRandomInstance(2);
    +
    +			assertEquals(0, scheduler.getNumberOfAvailableInstances());
    +			assertEquals(0, scheduler.getNumberOfAvailableSlots());
    +			scheduler.newInstanceAvailable(i1);
    +			assertEquals(1, scheduler.getNumberOfAvailableInstances());
    +			assertEquals(2, scheduler.getNumberOfAvailableSlots());
    +			scheduler.newInstanceAvailable(i2);
    +			assertEquals(2, scheduler.getNumberOfAvailableInstances());
    +			assertEquals(4, scheduler.getNumberOfAvailableSlots());
    +			scheduler.newInstanceAvailable(i3);
    +			assertEquals(3, scheduler.getNumberOfAvailableInstances());
    +			assertEquals(6, scheduler.getNumberOfAvailableSlots());
    +
    +			// cannot add available instance again
    +			try {
    +				scheduler.newInstanceAvailable(i2);
    +				fail("Scheduler accepted instance twice");
    +			}
    +			catch (IllegalArgumentException e) {
    +				// bueno!
    +			}
    +
    +			// some instances die
    +			assertEquals(3, scheduler.getNumberOfAvailableInstances());
    +			assertEquals(6, scheduler.getNumberOfAvailableSlots());
    +			scheduler.instanceDied(i2);
    +			assertEquals(2, scheduler.getNumberOfAvailableInstances());
    +			assertEquals(4, scheduler.getNumberOfAvailableSlots());
    +
    +			// try to add a dead instance
    +			try {
    +				scheduler.newInstanceAvailable(i2);
    +				fail("Scheduler accepted dead instance");
    +			}
    +			catch (IllegalArgumentException e) {
    +				// stimmt
    +
    +			}
    +
    +			scheduler.instanceDied(i1);
    +			assertEquals(1, scheduler.getNumberOfAvailableInstances());
    +			assertEquals(2, scheduler.getNumberOfAvailableSlots());
    +			scheduler.instanceDied(i3);
    +			assertEquals(0, scheduler.getNumberOfAvailableInstances());
    +			assertEquals(0, scheduler.getNumberOfAvailableSlots());
    +
    +			assertFalse(i1.isAlive());
    +			assertFalse(i2.isAlive());
    +			assertFalse(i3.isAlive());
    +		}
    +		catch (Exception e) {
    --- End diff --
    
    jup, but I'll remove it.


---

[GitHub] flink pull request #5091: [FLINK-7956] [flip6] Add support for queued schedu...

Posted by tillrohrmann <gi...@git.apache.org>.
Github user tillrohrmann commented on a diff in the pull request:

    https://github.com/apache/flink/pull/5091#discussion_r156948978
  
    --- Diff: flink-runtime/src/main/java/org/apache/flink/runtime/jobmaster/slotpool/SlotSharingManager.java ---
    @@ -0,0 +1,722 @@
    +/*
    + * Licensed to the Apache Software Foundation (ASF) under one
    + * or more contributor license agreements.  See the NOTICE file
    + * distributed with this work for additional information
    + * regarding copyright ownership.  The ASF licenses this file
    + * to you under the Apache License, Version 2.0 (the
    + * "License"); you may not use this file except in compliance
    + * with the License.  You may obtain a copy of the License at
    + *
    + *     http://www.apache.org/licenses/LICENSE-2.0
    + *
    + * Unless required by applicable law or agreed to in writing, software
    + * distributed under the License is distributed on an "AS IS" BASIS,
    + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    + * See the License for the specific language governing permissions and
    + * limitations under the License.
    + */
    +
    +package org.apache.flink.runtime.jobmaster.slotpool;
    +
    +import org.apache.flink.annotation.VisibleForTesting;
    +import org.apache.flink.runtime.jobmaster.LogicalSlot;
    +import org.apache.flink.runtime.jobmaster.SlotContext;
    +import org.apache.flink.runtime.jobmaster.SlotOwner;
    +import org.apache.flink.runtime.jobmaster.SlotRequestId;
    +import org.apache.flink.runtime.instance.SlotSharingGroupId;
    +import org.apache.flink.runtime.jobmanager.scheduler.Locality;
    +import org.apache.flink.runtime.taskmanager.TaskManagerLocation;
    +import org.apache.flink.util.AbstractID;
    +import org.apache.flink.util.FlinkException;
    +import org.apache.flink.util.Preconditions;
    +
    +import javax.annotation.Nullable;
    +
    +import java.util.AbstractCollection;
    +import java.util.Collection;
    +import java.util.Collections;
    +import java.util.HashMap;
    +import java.util.HashSet;
    +import java.util.Iterator;
    +import java.util.Map;
    +import java.util.Objects;
    +import java.util.Set;
    +import java.util.concurrent.CompletableFuture;
    +
    +/**
    + * Manager which is responsible for slot sharing. Slot sharing allows to run different
    + * tasks in the same slot and to realize co-location constraints.
    + *
    + * <p>The SlotSharingManager allows to create a hierarchy of {@link TaskSlot} such that
    + * every {@link TaskSlot} is uniquely identified by a {@link SlotRequestId} identifying
    + * the request for the TaskSlot and a {@link AbstractID} identifying the task or the
    + * co-location constraint running in this slot.
    + *
    + * <p>The {@link TaskSlot} hierarchy is implemented by {@link MultiTaskSlot} and
    + * {@link SingleTaskSlot}. The former class represents inner nodes which can contain
    + * a number of other {@link TaskSlot} and the latter class represents the leave nodes.
    + * The hierarchy starts with a root {@link MultiTaskSlot} which is a future
    + * {@link SlotContext} assigned. The {@link SlotContext} represents the allocated slot
    + * on the TaskExecutor in which all slots of this hierarchy run. A {@link MultiTaskSlot}
    + * can be assigned multiple {@link SingleTaskSlot} or {@link MultiTaskSlot} if and only if
    + * the task slot does not yet contain another child with the same {@link AbstractID} identifying
    + * the actual task or the co-location constraint.
    + *
    + * <p>Normal slot sharing is represented by a root {@link MultiTaskSlot} which contains a set
    + * of {@link SingleTaskSlot} on the second layer. Each {@link SingleTaskSlot} represents a different
    + * task.
    + *
    + * <p>Co-location constraints are modeled by adding a {@link MultiTaskSlot} to the root node. The co-location
    + * constraint is uniquely identified by a {@link AbstractID} such that we cannot add a second co-located
    + * {@link MultiTaskSlot} to the same root node. Now all co-located tasks will be added to co-located
    + * multi task slot.
    + */
    +public class SlotSharingManager {
    +
    +	private final SlotSharingGroupId slotSharingGroupId;
    +
    +	// needed to release allocated slots after a complete multi task slot hierarchy has been released
    +	private final AllocatedSlotActions allocatedSlotActions;
    +
    +	// owner of the slots to which to return them when they are released from the outside
    +	private final SlotOwner slotOwner;
    +
    +	private final Map<SlotRequestId, TaskSlot> allTaskSlots;
    +
    +	// Root nodes which have not been completed because the allocated slot is still pending
    +	private final Map<SlotRequestId, MultiTaskSlot> unresolvedRootSlots;
    +
    +	// Root nodes which have been completed (the underlying allocated slot has been assigned)
    +	private final Map<TaskManagerLocation, Set<MultiTaskSlot>> resolvedRootSlots;
    +
    +	// Internal class to iterate over all resolved root slots
    +	private ResolvedRootSlotValues resolvedMultiTaskSlotValues;
    +
    +	public SlotSharingManager(
    +			SlotSharingGroupId slotSharingGroupId,
    +			AllocatedSlotActions allocatedSlotActions,
    +			SlotOwner slotOwner) {
    +		this.slotSharingGroupId = Preconditions.checkNotNull(slotSharingGroupId);
    +		this.allocatedSlotActions = Preconditions.checkNotNull(allocatedSlotActions);
    +		this.slotOwner = Preconditions.checkNotNull(slotOwner);
    +
    +		allTaskSlots = new HashMap<>(16);
    +		unresolvedRootSlots = new HashMap<>(16);
    +		resolvedRootSlots = new HashMap<>(16);
    +
    +		resolvedMultiTaskSlotValues = null;
    +	}
    +
    +	public boolean isEmpty() {
    +		return allTaskSlots.isEmpty();
    +	}
    +
    +	public boolean contains(SlotRequestId slotRequestId) {
    +		return allTaskSlots.containsKey(slotRequestId);
    +	}
    +
    +	@Nullable
    +	public TaskSlot getTaskSlot(SlotRequestId slotRequestId) {
    +		return allTaskSlots.get(slotRequestId);
    +	}
    +
    +	/**
    +	 * Creates a new root slot with the given {@link SlotRequestId}, {@link SlotContext} future and
    +	 * the {@link SlotRequestId} of the allocated slot.
    +	 *
    +	 * @param slotRequestId of the root slot
    +	 * @param slotContextFuture with which we create the root slot
    +	 * @param allocatedSlotRequestId slot request id of the underlying allocated slot which can be used
    +	 *                               to cancel the pending slot request or release the allocated slot
    +	 * @return New root slot
    +	 */
    +	public MultiTaskSlot createRootSlot(
    +			SlotRequestId slotRequestId,
    +			CompletableFuture<SlotContext> slotContextFuture,
    +			SlotRequestId allocatedSlotRequestId) {
    +		final MultiTaskSlot rootMultiTaskSlot = new MultiTaskSlot(
    +			slotRequestId,
    +			slotContextFuture,
    +			allocatedSlotRequestId);
    +
    +		allTaskSlots.put(slotRequestId, rootMultiTaskSlot);
    +		unresolvedRootSlots.put(slotRequestId, rootMultiTaskSlot);
    +
    +		// add the root node to the set of resolved root nodes once the SlotContext future has been completed
    +		// and we know the slot's TaskManagerLocation
    +		slotContextFuture.whenComplete(
    +			(SlotContext slotContext, Throwable throwable) -> {
    +				if (slotContext != null) {
    +					final MultiTaskSlot resolvedRootNode = unresolvedRootSlots.remove(slotRequestId);
    +
    +					if (resolvedRootNode != null) {
    +						final Set<MultiTaskSlot> innerCollection = resolvedRootSlots.computeIfAbsent(
    --- End diff --
    
    True. I'll add the necessary synchronization because it's not guaranteed that the future completion won't change in the future.


---

[GitHub] flink pull request #5091: [FLINK-7956] [flip6] Add support for queued schedu...

Posted by tillrohrmann <gi...@git.apache.org>.
Github user tillrohrmann commented on a diff in the pull request:

    https://github.com/apache/flink/pull/5091#discussion_r156902956
  
    --- Diff: flink-runtime/src/test/java/org/apache/flink/runtime/jobmaster/slotpool/SlotSharingManagerTest.java ---
    @@ -0,0 +1,502 @@
    +/*
    + * Licensed to the Apache Software Foundation (ASF) under one
    + * or more contributor license agreements.  See the NOTICE file
    + * distributed with this work for additional information
    + * regarding copyright ownership.  The ASF licenses this file
    + * to you under the Apache License, Version 2.0 (the
    + * "License"); you may not use this file except in compliance
    + * with the License.  You may obtain a copy of the License at
    + *
    + *     http://www.apache.org/licenses/LICENSE-2.0
    + *
    + * Unless required by applicable law or agreed to in writing, software
    + * distributed under the License is distributed on an "AS IS" BASIS,
    + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    + * See the License for the specific language governing permissions and
    + * limitations under the License.
    + */
    +
    +package org.apache.flink.runtime.jobmaster.slotpool;
    +
    +import org.apache.flink.runtime.clusterframework.types.AllocationID;
    +import org.apache.flink.runtime.executiongraph.utils.SimpleAckingTaskManagerGateway;
    +import org.apache.flink.runtime.instance.SimpleSlotContext;
    +import org.apache.flink.runtime.instance.SlotSharingGroupId;
    +import org.apache.flink.runtime.jobmanager.scheduler.Locality;
    +import org.apache.flink.runtime.jobmanager.slots.DummySlotOwner;
    +import org.apache.flink.runtime.jobmaster.LogicalSlot;
    +import org.apache.flink.runtime.jobmaster.SlotContext;
    +import org.apache.flink.runtime.jobmaster.SlotRequestId;
    +import org.apache.flink.runtime.taskmanager.LocalTaskManagerLocation;
    +import org.apache.flink.util.AbstractID;
    +import org.apache.flink.util.FlinkException;
    +import org.apache.flink.util.TestLogger;
    +
    +import org.junit.Test;
    +
    +import java.util.Collections;
    +import java.util.Objects;
    +import java.util.concurrent.CompletableFuture;
    +import java.util.concurrent.ExecutionException;
    +
    +import static org.junit.Assert.assertEquals;
    +import static org.junit.Assert.assertFalse;
    +import static org.junit.Assert.assertNotNull;
    +import static org.junit.Assert.assertNull;
    +import static org.junit.Assert.assertTrue;
    +
    +/**
    + * Test cases for the {@link SlotSharingManager}.
    + */
    +public class SlotSharingManagerTest extends TestLogger {
    +
    +	private static final SlotSharingGroupId slotSharingGroupId = new SlotSharingGroupId();
    +
    +	private static final DummySlotOwner slotOwner = new DummySlotOwner();
    +
    +	private static final TestingAllocatedSlotActions allocatedSlotActions = new TestingAllocatedSlotActions();
    --- End diff --
    
    Will make it non static.


---

[GitHub] flink pull request #5091: [FLINK-7956] [flip6] Add support for queued schedu...

Posted by GJL <gi...@git.apache.org>.
Github user GJL commented on a diff in the pull request:

    https://github.com/apache/flink/pull/5091#discussion_r155770104
  
    --- Diff: flink-runtime/src/test/java/org/apache/flink/runtime/jobmaster/slotpool/SlotSharingManagerTest.java ---
    @@ -0,0 +1,502 @@
    +/*
    + * Licensed to the Apache Software Foundation (ASF) under one
    + * or more contributor license agreements.  See the NOTICE file
    + * distributed with this work for additional information
    + * regarding copyright ownership.  The ASF licenses this file
    + * to you under the Apache License, Version 2.0 (the
    + * "License"); you may not use this file except in compliance
    + * with the License.  You may obtain a copy of the License at
    + *
    + *     http://www.apache.org/licenses/LICENSE-2.0
    + *
    + * Unless required by applicable law or agreed to in writing, software
    + * distributed under the License is distributed on an "AS IS" BASIS,
    + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    + * See the License for the specific language governing permissions and
    + * limitations under the License.
    + */
    +
    +package org.apache.flink.runtime.jobmaster.slotpool;
    +
    +import org.apache.flink.runtime.clusterframework.types.AllocationID;
    +import org.apache.flink.runtime.executiongraph.utils.SimpleAckingTaskManagerGateway;
    +import org.apache.flink.runtime.instance.SimpleSlotContext;
    +import org.apache.flink.runtime.instance.SlotSharingGroupId;
    +import org.apache.flink.runtime.jobmanager.scheduler.Locality;
    +import org.apache.flink.runtime.jobmanager.slots.DummySlotOwner;
    +import org.apache.flink.runtime.jobmaster.LogicalSlot;
    +import org.apache.flink.runtime.jobmaster.SlotContext;
    +import org.apache.flink.runtime.jobmaster.SlotRequestId;
    +import org.apache.flink.runtime.taskmanager.LocalTaskManagerLocation;
    +import org.apache.flink.util.AbstractID;
    +import org.apache.flink.util.FlinkException;
    +import org.apache.flink.util.TestLogger;
    +
    +import org.junit.Test;
    +
    +import java.util.Collections;
    +import java.util.Objects;
    +import java.util.concurrent.CompletableFuture;
    +import java.util.concurrent.ExecutionException;
    +
    +import static org.junit.Assert.assertEquals;
    +import static org.junit.Assert.assertFalse;
    +import static org.junit.Assert.assertNotNull;
    +import static org.junit.Assert.assertNull;
    +import static org.junit.Assert.assertTrue;
    +
    +/**
    + * Test cases for the {@link SlotSharingManager}.
    + */
    +public class SlotSharingManagerTest extends TestLogger {
    +
    +	private static final SlotSharingGroupId slotSharingGroupId = new SlotSharingGroupId();
    --- End diff --
    
    Should be `SLOT_SHARING_GROUP_ID` since it is a constant.


---

[GitHub] flink pull request #5091: [FLINK-7956] [flip6] Add support for queued schedu...

Posted by GJL <gi...@git.apache.org>.
Github user GJL commented on a diff in the pull request:

    https://github.com/apache/flink/pull/5091#discussion_r155751694
  
    --- Diff: flink-runtime/src/main/java/org/apache/flink/runtime/jobmaster/slotpool/SlotPool.java ---
    @@ -266,104 +279,367 @@ public void disconnectResourceManager() {
     	// ------------------------------------------------------------------------
     
     	@Override
    -	public CompletableFuture<SimpleSlot> allocateSlot(
    -			SlotRequestID requestId,
    -			ScheduledUnit task,
    -			ResourceProfile resources,
    -			Iterable<TaskManagerLocation> locationPreferences,
    +	public CompletableFuture<LogicalSlot> allocateSlot(
    +			SlotRequestId slotRequestId,
    +			ScheduledUnit scheduledUnit,
    +			ResourceProfile resourceProfile,
    +			Collection<TaskManagerLocation> locationPreferences,
    +			boolean allowQueuedScheduling,
     			Time timeout) {
     
    -		return internalAllocateSlot(requestId, task, resources, locationPreferences);
    +		return internalAllocateSlot(
    +			slotRequestId,
    +			scheduledUnit,
    +			resourceProfile,
    +			locationPreferences,
    +			allowQueuedScheduling);
     	}
     
    -	@Override
    -	public void returnAllocatedSlot(Slot slot) {
    -		internalReturnAllocatedSlot(slot);
    +	private CompletableFuture<LogicalSlot> internalAllocateSlot(
    +			SlotRequestId slotRequestId,
    +			ScheduledUnit task,
    +			ResourceProfile resourceProfile,
    +			Collection<TaskManagerLocation> locationPreferences,
    +			boolean allowQueuedScheduling) {
    +
    +		final SlotSharingGroupId slotSharingGroupId = task.getSlotSharingGroupId();
    +
    +		if (slotSharingGroupId != null) {
    +			// allocate slot with slot sharing
    +			final SlotSharingManager multiTaskSlotManager = slotSharingManagers.computeIfAbsent(
    +				slotSharingGroupId,
    +				id -> new SlotSharingManager(
    +					id,
    +					this,
    +					providerAndOwner));
    +
    +			final SlotSharingManager.MultiTaskSlotLocality multiTaskSlotFuture;
    +
    +			try {
    +				if (task.getCoLocationConstraint() != null) {
    +					multiTaskSlotFuture = allocateCoLocatedMultiTaskSlot(
    +						task.getCoLocationConstraint(),
    +						multiTaskSlotManager,
    +						resourceProfile,
    +						locationPreferences,
    +						allowQueuedScheduling);
    +				} else {
    +					multiTaskSlotFuture = allocateMultiTaskSlot(
    +						task.getJobVertexId(), multiTaskSlotManager,
    +						resourceProfile,
    +						locationPreferences,
    +						allowQueuedScheduling);
    +				}
    +			} catch (NoResourceAvailableException noResourceException) {
    +				return FutureUtils.completedExceptionally(noResourceException);
    +			}
    +
    +			// sanity check
    +			Preconditions.checkState(!multiTaskSlotFuture.getMultiTaskSlot().contains(task.getJobVertexId()));
    +
    +			final SlotSharingManager.SingleTaskSlot leave = multiTaskSlotFuture.getMultiTaskSlot().allocateSingleTaskSlot(
    +				slotRequestId,
    +				task.getJobVertexId(),
    +				multiTaskSlotFuture.getLocality());
    +
    +			return leave.getLogicalSlotFuture();
    +		} else {
    +			// request an allocated slot to assign a single logical slot to
    +			CompletableFuture<SlotAndLocality> slotAndLocalityFuture = requestAllocatedSlot(
    +				slotRequestId,
    +				resourceProfile,
    +				locationPreferences,
    +				allowQueuedScheduling);
    +
    +			return slotAndLocalityFuture.thenApply(
    +				(SlotAndLocality slotAndLocality) -> {
    +					final AllocatedSlot allocatedSlot = slotAndLocality.getSlot();
    +
    +					final SingleLogicalSlot singleTaskSlot = new SingleLogicalSlot(
    +						slotRequestId,
    +						allocatedSlot,
    +						null,
    +						slotAndLocality.getLocality(),
    +						providerAndOwner);
    +
    +					if (allocatedSlot.tryAssignPayload(singleTaskSlot)) {
    +						return singleTaskSlot;
    +					} else {
    +						final FlinkException flinkException = new FlinkException("Could not assign payload to allocated slot " + allocatedSlot.getAllocationId() + '.');
    +						releaseSlot(slotRequestId, null, flinkException);
    +						throw new CompletionException(flinkException);
    +					}
    +				});
    +		}
     	}
     
    -	@Override
    -	public CompletableFuture<Acknowledge> cancelSlotAllocation(SlotRequestID requestId) {
    -		final PendingRequest pendingRequest = removePendingRequest(requestId);
    +	/**
    +	 * Allocates a co-located {@link SlotSharingManager.MultiTaskSlot} for the given {@link CoLocationConstraint}.
    +	 *
    +	 * <p>If allowQueuedScheduling is true, then the returned {@link SlotSharingManager.MultiTaskSlot} can be
    +	 * uncompleted.
    +	 *
    +	 * @param coLocationConstraint for which to allocate a {@link SlotSharingManager.MultiTaskSlot}
    +	 * @param multiTaskSlotManager responsible for the slot sharing group for which to allocate the slot
    +	 * @param resourceProfile specifying the requirements for the requested slot
    +	 * @param locationPreferences containing preferred TaskExecutors on which to allocate the slot
    +	 * @param allowQueuedScheduling true if queued scheduling (the returned task slot must not be completed yet) is allowed, otherwise false
    +	 * @return A {@link SlotSharingManager.MultiTaskSlotLocality} which contains the allocated{@link SlotSharingManager.MultiTaskSlot}
    +	 * 		and its locality wrt the given location preferences
    +	 * @throws NoResourceAvailableException if no task slot could be allocated
    +	 */
    +	private SlotSharingManager.MultiTaskSlotLocality allocateCoLocatedMultiTaskSlot(
    +			CoLocationConstraint coLocationConstraint,
    +			SlotSharingManager multiTaskSlotManager,
    +			ResourceProfile resourceProfile,
    +			Collection<TaskManagerLocation> locationPreferences,
    +			boolean allowQueuedScheduling) throws NoResourceAvailableException {
    +		final SlotRequestId coLocationSlotRequestId = coLocationConstraint.getSlotRequestId();
    +
    +		if (coLocationSlotRequestId != null) {
    +			// we have a slot assigned --> try to retrieve it
    +			final SlotSharingManager.TaskSlot taskSlot = multiTaskSlotManager.getTaskSlot(coLocationSlotRequestId);
    +
    +			if (taskSlot != null) {
    +				Preconditions.checkState(taskSlot instanceof SlotSharingManager.MultiTaskSlot);
    +				return SlotSharingManager.MultiTaskSlotLocality.of(((SlotSharingManager.MultiTaskSlot) taskSlot), Locality.LOCAL);
    +			} else {
    +				// the slot may have been cancelled in the mean time
    +				coLocationConstraint.setSlotRequestId(null);
    +			}
    +		}
     
    -		if (pendingRequest != null) {
    -			failPendingRequest(pendingRequest, new CancellationException("Allocation with request id" + requestId + " cancelled."));
    +		final Collection<TaskManagerLocation> actualLocationPreferences;
    +
    +		if (coLocationConstraint.isAssigned()) {
    +			actualLocationPreferences = Collections.singleton(coLocationConstraint.getLocation());
     		} else {
    -			final Slot slot = allocatedSlots.get(requestId);
    +			actualLocationPreferences = locationPreferences;
    +		}
    +
    +		// get a new multi task slot
    +		final SlotSharingManager.MultiTaskSlotLocality multiTaskSlotLocality = allocateMultiTaskSlot(
    +			coLocationConstraint.getGroupId(), multiTaskSlotManager,
    +			resourceProfile,
    +			actualLocationPreferences,
    +			allowQueuedScheduling);
    +
    +		// check whether we fulfill the co-location constraint
    +		if (coLocationConstraint.isAssigned() && multiTaskSlotLocality.getLocality() != Locality.LOCAL) {
    +			multiTaskSlotLocality.getMultiTaskSlot().release(
    +				new FlinkException("Multi task slot is not local and, thus, does not fulfill the co-location constraint."));
     
    -			if (slot != null) {
    -				LOG.info("Returning allocated slot {} because the corresponding allocation request {} was cancelled.", slot, requestId);
    -				if (slot.markCancelled()) {
    -					internalReturnAllocatedSlot(slot);
    +			throw new NoResourceAvailableException("Could not allocate a local multi task slot for the " +
    +				"co location constraint " + coLocationConstraint + '.');
    +		}
    +
    +		final SlotRequestId slotRequestId = new SlotRequestId();
    +		final SlotSharingManager.MultiTaskSlot coLocationSlot = multiTaskSlotLocality.getMultiTaskSlot().allocateMultiTaskSlot(
    +			slotRequestId,
    +			coLocationConstraint.getGroupId());
    +
    +		// mark the requested slot as co-located slot for other co-located tasks
    +		coLocationConstraint.setSlotRequestId(slotRequestId);
    +
    +		// lock the co-location constraint once we have obtained the allocated slot
    +		coLocationSlot.getSlotContextFuture().whenComplete(
    +			(SlotContext slotContext, Throwable throwable) -> {
    +				if (throwable == null) {
    --- End diff --
    
    Is it acceptable to swallow the `Throwable` here? 


---

[GitHub] flink pull request #5091: [FLINK-7956] [flip6] Add support for queued schedu...

Posted by GJL <gi...@git.apache.org>.
Github user GJL commented on a diff in the pull request:

    https://github.com/apache/flink/pull/5091#discussion_r155758219
  
    --- Diff: flink-runtime/src/main/java/org/apache/flink/runtime/jobmaster/slotpool/SlotSharingManager.java ---
    @@ -0,0 +1,722 @@
    +/*
    + * Licensed to the Apache Software Foundation (ASF) under one
    + * or more contributor license agreements.  See the NOTICE file
    + * distributed with this work for additional information
    + * regarding copyright ownership.  The ASF licenses this file
    + * to you under the Apache License, Version 2.0 (the
    + * "License"); you may not use this file except in compliance
    + * with the License.  You may obtain a copy of the License at
    + *
    + *     http://www.apache.org/licenses/LICENSE-2.0
    + *
    + * Unless required by applicable law or agreed to in writing, software
    + * distributed under the License is distributed on an "AS IS" BASIS,
    + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    + * See the License for the specific language governing permissions and
    + * limitations under the License.
    + */
    +
    +package org.apache.flink.runtime.jobmaster.slotpool;
    +
    +import org.apache.flink.annotation.VisibleForTesting;
    +import org.apache.flink.runtime.jobmaster.LogicalSlot;
    +import org.apache.flink.runtime.jobmaster.SlotContext;
    +import org.apache.flink.runtime.jobmaster.SlotOwner;
    +import org.apache.flink.runtime.jobmaster.SlotRequestId;
    +import org.apache.flink.runtime.instance.SlotSharingGroupId;
    +import org.apache.flink.runtime.jobmanager.scheduler.Locality;
    +import org.apache.flink.runtime.taskmanager.TaskManagerLocation;
    +import org.apache.flink.util.AbstractID;
    +import org.apache.flink.util.FlinkException;
    +import org.apache.flink.util.Preconditions;
    +
    +import javax.annotation.Nullable;
    +
    +import java.util.AbstractCollection;
    +import java.util.Collection;
    +import java.util.Collections;
    +import java.util.HashMap;
    +import java.util.HashSet;
    +import java.util.Iterator;
    +import java.util.Map;
    +import java.util.Objects;
    +import java.util.Set;
    +import java.util.concurrent.CompletableFuture;
    +
    +/**
    + * Manager which is responsible for slot sharing. Slot sharing allows to run different
    + * tasks in the same slot and to realize co-location constraints.
    + *
    + * <p>The SlotSharingManager allows to create a hierarchy of {@link TaskSlot} such that
    + * every {@link TaskSlot} is uniquely identified by a {@link SlotRequestId} identifying
    + * the request for the TaskSlot and a {@link AbstractID} identifying the task or the
    + * co-location constraint running in this slot.
    + *
    + * <p>The {@link TaskSlot} hierarchy is implemented by {@link MultiTaskSlot} and
    + * {@link SingleTaskSlot}. The former class represents inner nodes which can contain
    + * a number of other {@link TaskSlot} and the latter class represents the leave nodes.
    --- End diff --
    
    nit: *leaf nodes*


---

[GitHub] flink pull request #5091: [FLINK-7956] [flip6] Add support for queued schedu...

Posted by GJL <gi...@git.apache.org>.
Github user GJL commented on a diff in the pull request:

    https://github.com/apache/flink/pull/5091#discussion_r155768880
  
    --- Diff: flink-runtime/src/main/java/org/apache/flink/runtime/jobmaster/slotpool/SlotSharingManager.java ---
    @@ -0,0 +1,722 @@
    +/*
    + * Licensed to the Apache Software Foundation (ASF) under one
    + * or more contributor license agreements.  See the NOTICE file
    + * distributed with this work for additional information
    + * regarding copyright ownership.  The ASF licenses this file
    + * to you under the Apache License, Version 2.0 (the
    + * "License"); you may not use this file except in compliance
    + * with the License.  You may obtain a copy of the License at
    + *
    + *     http://www.apache.org/licenses/LICENSE-2.0
    + *
    + * Unless required by applicable law or agreed to in writing, software
    + * distributed under the License is distributed on an "AS IS" BASIS,
    + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    + * See the License for the specific language governing permissions and
    + * limitations under the License.
    + */
    +
    +package org.apache.flink.runtime.jobmaster.slotpool;
    +
    +import org.apache.flink.annotation.VisibleForTesting;
    +import org.apache.flink.runtime.jobmaster.LogicalSlot;
    +import org.apache.flink.runtime.jobmaster.SlotContext;
    +import org.apache.flink.runtime.jobmaster.SlotOwner;
    +import org.apache.flink.runtime.jobmaster.SlotRequestId;
    +import org.apache.flink.runtime.instance.SlotSharingGroupId;
    +import org.apache.flink.runtime.jobmanager.scheduler.Locality;
    +import org.apache.flink.runtime.taskmanager.TaskManagerLocation;
    +import org.apache.flink.util.AbstractID;
    +import org.apache.flink.util.FlinkException;
    +import org.apache.flink.util.Preconditions;
    +
    +import javax.annotation.Nullable;
    +
    +import java.util.AbstractCollection;
    +import java.util.Collection;
    +import java.util.Collections;
    +import java.util.HashMap;
    +import java.util.HashSet;
    +import java.util.Iterator;
    +import java.util.Map;
    +import java.util.Objects;
    +import java.util.Set;
    +import java.util.concurrent.CompletableFuture;
    +
    +/**
    + * Manager which is responsible for slot sharing. Slot sharing allows to run different
    + * tasks in the same slot and to realize co-location constraints.
    + *
    + * <p>The SlotSharingManager allows to create a hierarchy of {@link TaskSlot} such that
    + * every {@link TaskSlot} is uniquely identified by a {@link SlotRequestId} identifying
    + * the request for the TaskSlot and a {@link AbstractID} identifying the task or the
    + * co-location constraint running in this slot.
    + *
    + * <p>The {@link TaskSlot} hierarchy is implemented by {@link MultiTaskSlot} and
    + * {@link SingleTaskSlot}. The former class represents inner nodes which can contain
    + * a number of other {@link TaskSlot} and the latter class represents the leave nodes.
    + * The hierarchy starts with a root {@link MultiTaskSlot} which is a future
    + * {@link SlotContext} assigned. The {@link SlotContext} represents the allocated slot
    + * on the TaskExecutor in which all slots of this hierarchy run. A {@link MultiTaskSlot}
    + * can be assigned multiple {@link SingleTaskSlot} or {@link MultiTaskSlot} if and only if
    + * the task slot does not yet contain another child with the same {@link AbstractID} identifying
    + * the actual task or the co-location constraint.
    + *
    + * <p>Normal slot sharing is represented by a root {@link MultiTaskSlot} which contains a set
    + * of {@link SingleTaskSlot} on the second layer. Each {@link SingleTaskSlot} represents a different
    + * task.
    + *
    + * <p>Co-location constraints are modeled by adding a {@link MultiTaskSlot} to the root node. The co-location
    + * constraint is uniquely identified by a {@link AbstractID} such that we cannot add a second co-located
    + * {@link MultiTaskSlot} to the same root node. Now all co-located tasks will be added to co-located
    + * multi task slot.
    + */
    +public class SlotSharingManager {
    +
    +	private final SlotSharingGroupId slotSharingGroupId;
    +
    +	// needed to release allocated slots after a complete multi task slot hierarchy has been released
    +	private final AllocatedSlotActions allocatedSlotActions;
    +
    +	// owner of the slots to which to return them when they are released from the outside
    +	private final SlotOwner slotOwner;
    +
    +	private final Map<SlotRequestId, TaskSlot> allTaskSlots;
    +
    +	// Root nodes which have not been completed because the allocated slot is still pending
    +	private final Map<SlotRequestId, MultiTaskSlot> unresolvedRootSlots;
    +
    +	// Root nodes which have been completed (the underlying allocated slot has been assigned)
    +	private final Map<TaskManagerLocation, Set<MultiTaskSlot>> resolvedRootSlots;
    +
    +	// Internal class to iterate over all resolved root slots
    +	private ResolvedRootSlotValues resolvedMultiTaskSlotValues;
    +
    +	public SlotSharingManager(
    +			SlotSharingGroupId slotSharingGroupId,
    +			AllocatedSlotActions allocatedSlotActions,
    +			SlotOwner slotOwner) {
    +		this.slotSharingGroupId = Preconditions.checkNotNull(slotSharingGroupId);
    +		this.allocatedSlotActions = Preconditions.checkNotNull(allocatedSlotActions);
    +		this.slotOwner = Preconditions.checkNotNull(slotOwner);
    +
    +		allTaskSlots = new HashMap<>(16);
    +		unresolvedRootSlots = new HashMap<>(16);
    +		resolvedRootSlots = new HashMap<>(16);
    +
    +		resolvedMultiTaskSlotValues = null;
    +	}
    +
    +	public boolean isEmpty() {
    +		return allTaskSlots.isEmpty();
    +	}
    +
    +	public boolean contains(SlotRequestId slotRequestId) {
    +		return allTaskSlots.containsKey(slotRequestId);
    +	}
    +
    +	@Nullable
    +	public TaskSlot getTaskSlot(SlotRequestId slotRequestId) {
    +		return allTaskSlots.get(slotRequestId);
    +	}
    +
    +	/**
    +	 * Creates a new root slot with the given {@link SlotRequestId}, {@link SlotContext} future and
    +	 * the {@link SlotRequestId} of the allocated slot.
    +	 *
    +	 * @param slotRequestId of the root slot
    +	 * @param slotContextFuture with which we create the root slot
    +	 * @param allocatedSlotRequestId slot request id of the underlying allocated slot which can be used
    +	 *                               to cancel the pending slot request or release the allocated slot
    +	 * @return New root slot
    +	 */
    +	public MultiTaskSlot createRootSlot(
    +			SlotRequestId slotRequestId,
    +			CompletableFuture<SlotContext> slotContextFuture,
    +			SlotRequestId allocatedSlotRequestId) {
    +		final MultiTaskSlot rootMultiTaskSlot = new MultiTaskSlot(
    +			slotRequestId,
    +			slotContextFuture,
    +			allocatedSlotRequestId);
    +
    +		allTaskSlots.put(slotRequestId, rootMultiTaskSlot);
    +		unresolvedRootSlots.put(slotRequestId, rootMultiTaskSlot);
    +
    +		// add the root node to the set of resolved root nodes once the SlotContext future has been completed
    +		// and we know the slot's TaskManagerLocation
    +		slotContextFuture.whenComplete(
    +			(SlotContext slotContext, Throwable throwable) -> {
    +				if (slotContext != null) {
    +					final MultiTaskSlot resolvedRootNode = unresolvedRootSlots.remove(slotRequestId);
    +
    +					if (resolvedRootNode != null) {
    +						final Set<MultiTaskSlot> innerCollection = resolvedRootSlots.computeIfAbsent(
    +							slotContext.getTaskManagerLocation(),
    +							taskManagerLocation -> new HashSet<>(4));
    +
    +						innerCollection.add(resolvedRootNode);
    +					}
    +				} else {
    +					rootMultiTaskSlot.release(throwable);
    +				}
    +			});
    +
    +		return rootMultiTaskSlot;
    +	}
    +
    +	/**
    +	 * Gets a resolved root slot which does not yet contain the given groupId. First the given set of
    +	 * preferred locations is checked.
    +	 *
    +	 * @param groupId which the returned slot must not contain
    +	 * @param locationPreferences specifying which locations are preferred
    +	 * @return the resolved root slot and its locality wrt to the specified location preferences
    +	 * 		or null if there was no root slot which did not contain the given groupId
    +	 */
    +	@Nullable
    +	public MultiTaskSlotLocality getResolvedRootSlot(AbstractID groupId, Collection<TaskManagerLocation> locationPreferences) {
    +		Preconditions.checkNotNull(locationPreferences);
    +
    +		if (locationPreferences.isEmpty()) {
    +			return getResolvedRootSlotWithoutLocationPreferences(groupId);
    +		} else {
    +			return getResolvedRootSlotWithLocationPreferences(groupId, locationPreferences);
    +		}
    +	}
    +
    +	/**
    +	 * Gets a resolved root slot which does not yet contain the given groupId. The method will try to
    +	 * find a slot of a TaskManager contained in the collection of preferred locations. If there is no such slot
    +	 * with free capacities available, then the method will look for slots of TaskManager which run on the same
    +	 * machine as the TaskManager in the collection of preferred locations. If there is no such slot, then any slot
    +	 * with free capacities is returned. If there is no such slot, then null is returned.
    +	 *
    +	 * @param groupId which the returned slot must not contain
    +	 * @param locationPreferences specifying which locations are preferred
    +	 * @return the resolved root slot and its locality wrt to the specified location preferences
    +	 * 		or null if there was not root slot which did not contain the given groupId
    +	 */
    +	@Nullable
    +	private MultiTaskSlotLocality getResolvedRootSlotWithLocationPreferences(AbstractID groupId, Collection<TaskManagerLocation> locationPreferences) {
    +		Preconditions.checkNotNull(groupId);
    +		Preconditions.checkNotNull(locationPreferences);
    +		final Set<String> hostnameSet = new HashSet<>();
    +
    +		for (TaskManagerLocation locationPreference : locationPreferences) {
    +			final Set<MultiTaskSlot> multiTaskSlots = resolvedRootSlots.get(locationPreference);
    +
    +			if (multiTaskSlots != null) {
    +				for (MultiTaskSlot multiTaskSlot : multiTaskSlots) {
    +					if (!multiTaskSlot.contains(groupId)) {
    +						return MultiTaskSlotLocality.of(multiTaskSlot, Locality.LOCAL);
    +					}
    +				}
    +
    +				hostnameSet.add(locationPreference.getHostname());
    +			}
    +		}
    +
    +		MultiTaskSlot nonLocalMultiTaskSlot = null;
    +
    +		for (Map.Entry<TaskManagerLocation, Set<MultiTaskSlot>> taskManagerLocationSetEntry : resolvedRootSlots.entrySet()) {
    +			if (hostnameSet.contains(taskManagerLocationSetEntry.getKey().getHostname())) {
    +				for (MultiTaskSlot multiTaskSlot : taskManagerLocationSetEntry.getValue()) {
    +					if (!multiTaskSlot.contains(groupId)) {
    +						return MultiTaskSlotLocality.of(multiTaskSlot, Locality.HOST_LOCAL);
    +					}
    +				}
    +			} else if (nonLocalMultiTaskSlot == null) {
    +				for (MultiTaskSlot multiTaskSlot : taskManagerLocationSetEntry.getValue()) {
    +					if (!multiTaskSlot.contains(groupId)) {
    +						nonLocalMultiTaskSlot = multiTaskSlot;
    +					}
    +				}
    +			}
    +		}
    +
    +		if (nonLocalMultiTaskSlot != null) {
    +			return MultiTaskSlotLocality.of(nonLocalMultiTaskSlot, Locality.NON_LOCAL);
    +		} else {
    +			return null;
    +		}
    +	}
    +
    +	/**
    +	 * Gets a resolved slot which does not yet contain the given groupId without any location
    +	 * preferences.
    +	 *
    +	 * @param groupId which the returned slot must not contain
    +	 * @return the resolved slot or null if there was no root slot with free capacities
    +	 */
    +	@Nullable
    +	private MultiTaskSlotLocality getResolvedRootSlotWithoutLocationPreferences(AbstractID groupId) {
    +		Preconditions.checkNotNull(groupId);
    +
    +		for (Set<MultiTaskSlot> multiTaskSlots : resolvedRootSlots.values()) {
    +			for (MultiTaskSlot multiTaskSlot : multiTaskSlots) {
    +				if (!multiTaskSlot.contains(groupId)) {
    +					return MultiTaskSlotLocality.of(multiTaskSlot, Locality.UNCONSTRAINED);
    +				}
    +			}
    +		}
    +
    +		return null;
    +	}
    +
    +	/**
    +	 * Gets an unresolved slot which does not yet contain the given groupId. An unresolved
    +	 * slot is a slot whose underlying allocated slot has not been allocated yet.
    +	 *
    +	 * @param groupId which the returned slot must not contain
    +	 * @return the unresolved slot or null if there was no root slot with free capacities
    +	 */
    +	@Nullable
    +	public MultiTaskSlot getUnresolvedRootSlot(AbstractID groupId) {
    +		for (MultiTaskSlot multiTaskSlot : unresolvedRootSlots.values()) {
    +			if (!multiTaskSlot.contains(groupId)) {
    +				return multiTaskSlot;
    +			}
    +		}
    +
    +		return null;
    +	}
    +
    +	// ------------------------------------------------------------------------
    +	// Inner classes: TaskSlot hierarchy and helper classes
    +	// ------------------------------------------------------------------------
    +
    +	/**
    +	 * Helper class which contains a {@link MultiTaskSlot} and its {@link Locality}.
    +	 */
    +	public static final class MultiTaskSlotLocality {
    +		private final MultiTaskSlot multiTaskSlot;
    +
    +		private final Locality locality;
    +
    +		public MultiTaskSlotLocality(MultiTaskSlot multiTaskSlot, Locality locality) {
    +			this.multiTaskSlot = Preconditions.checkNotNull(multiTaskSlot);
    +			this.locality = Preconditions.checkNotNull(locality);
    +		}
    +
    +		public MultiTaskSlot getMultiTaskSlot() {
    +			return multiTaskSlot;
    +		}
    +
    +		public Locality getLocality() {
    +			return locality;
    +		}
    +
    +		public static MultiTaskSlotLocality of(MultiTaskSlot multiTaskSlot, Locality locality) {
    +			return new MultiTaskSlotLocality(multiTaskSlot, locality);
    +		}
    +	}
    +
    +	/**
    +	 * Base class for all task slots.
    +	 */
    +	public abstract static class TaskSlot {
    +		// every TaskSlot has an associated slot request id
    +		private final SlotRequestId slotRequestId;
    +
    +		// all task slots except for the root slots have a group id assigned
    +		@Nullable
    +		private final AbstractID groupId;
    +
    +		protected TaskSlot(SlotRequestId slotRequestId, @Nullable AbstractID groupId) {
    +			this.slotRequestId = Preconditions.checkNotNull(slotRequestId);
    +			this.groupId = groupId;
    +		}
    +
    +		public SlotRequestId getSlotRequestId() {
    +			return slotRequestId;
    +		}
    +
    +		@Nullable
    +		public AbstractID getGroupId() {
    +			return groupId;
    +		}
    +
    +		/**
    +		 * Check whether the task slot contains the given groupId.
    +		 *
    +		 * @param groupId which to check whether it is contained
    +		 * @return true if the task slot contains the given groupId, otherwise false
    +		 */
    +		public boolean contains(AbstractID groupId) {
    +			return Objects.equals(this.groupId, groupId);
    +		}
    +
    +		/**
    +		 * Release the task slot.
    +		 *
    +		 * @param cause for the release
    +		 * @return true if the slot could be released, otherwise false
    +		 */
    +		public abstract boolean release(Throwable cause);
    +	}
    +
    +	/**
    +	 * {@link TaskSlot} implementation which can have multiple other task slots assigned as children.
    +	 */
    +	public final class MultiTaskSlot extends TaskSlot implements AllocatedSlot.Payload {
    +
    +		private final Map<AbstractID, TaskSlot> children;
    +
    +		// the root node has its parent set to null
    +		@Nullable
    +		private final MultiTaskSlot parent;
    +
    +		// underlying allocated slot
    +		private final CompletableFuture<SlotContext> slotContextFuture;
    +
    +		// slot request id of the allocated slot
    +		@Nullable
    +		private final SlotRequestId allocatedSlotRequestId;
    +
    +		// true if we are currently releasing our children
    +		private boolean releasingChildren;
    +
    +		private MultiTaskSlot(
    +				SlotRequestId slotRequestId,
    +				AbstractID groupId,
    +				MultiTaskSlot parent) {
    +			this(
    +				slotRequestId,
    +				groupId,
    +				Preconditions.checkNotNull(parent),
    +				parent.getSlotContextFuture(),
    +				null);
    +		}
    +
    +		private MultiTaskSlot(
    +				SlotRequestId slotRequestId,
    +				CompletableFuture<SlotContext> slotContextFuture,
    +				SlotRequestId allocatedSlotRequestId) {
    +			this(
    +				slotRequestId,
    +				null,
    +				null,
    +				slotContextFuture,
    +				allocatedSlotRequestId);
    +		}
    +
    +		private MultiTaskSlot(
    +				SlotRequestId slotRequestId,
    +				@Nullable AbstractID groupId,
    +				MultiTaskSlot parent,
    +				CompletableFuture<SlotContext> slotContextFuture,
    +				SlotRequestId allocatedSlotRequestId) {
    +			super(slotRequestId, groupId);
    +
    +			this.parent = parent;
    +			this.slotContextFuture = Preconditions.checkNotNull(slotContextFuture);
    +			this.allocatedSlotRequestId = allocatedSlotRequestId;
    +
    +			this.children = new HashMap<>(16);
    +			this.releasingChildren = false;
    +
    +			slotContextFuture.whenComplete(
    +				(SlotContext ignored, Throwable throwable) -> {
    +					if (throwable != null) {
    +						release(throwable);
    +					}
    +				});
    +		}
    +
    +		public CompletableFuture<SlotContext> getSlotContextFuture() {
    +			return slotContextFuture;
    +		}
    +
    +		/**
    +		 * Allocates a {@link MultiTaskSlot} and registers it under the given groupId at
    +		 * this {@link MultiTaskSlot}.
    +		 *
    +		 * @param slotRequestId of the new multi task slot
    +		 * @param groupId under which the new multi task slot is registered
    +		 * @return the newly allocated {@link MultiTaskSlot}
    +		 */
    +		MultiTaskSlot allocateMultiTaskSlot(SlotRequestId slotRequestId, AbstractID groupId) {
    +			Preconditions.checkState(!super.contains(groupId));
    +
    +			final MultiTaskSlot inner = new MultiTaskSlot(
    +				slotRequestId,
    +				groupId,
    +				this);
    +
    +			children.put(groupId, inner);
    +
    +			// register the newly allocated slot also at the SlotSharingManager
    +			allTaskSlots.put(slotRequestId, inner);
    +
    +			return inner;
    +		}
    +
    +		/**
    +		 * Allocates a {@link SingleTaskSlot} and registeres it under the given groupId at
    +		 * this {@link MultiTaskSlot}.
    +		 *
    +		 * @param slotRequestId of the new single task slot
    +		 * @param groupId under which the new single task slot is registered
    +		 * @param locality of the allocation
    +		 * @return the newly allocated {@link SingleTaskSlot}
    +		 */
    +		SingleTaskSlot allocateSingleTaskSlot(
    +				SlotRequestId slotRequestId,
    +				AbstractID groupId,
    +				Locality locality) {
    +			Preconditions.checkState(!super.contains(groupId));
    +
    +			final SingleTaskSlot leave = new SingleTaskSlot(
    --- End diff --
    
    nit: *leaf*


---

[GitHub] flink pull request #5091: [FLINK-7956] [flip6] Add support for queued schedu...

Posted by tillrohrmann <gi...@git.apache.org>.
Github user tillrohrmann commented on a diff in the pull request:

    https://github.com/apache/flink/pull/5091#discussion_r156886562
  
    --- Diff: flink-runtime/src/test/java/org/apache/flink/runtime/jobmaster/slotpool/TestingAllocatedSlotActions.java ---
    @@ -0,0 +1,53 @@
    +/*
    + * Licensed to the Apache Software Foundation (ASF) under one
    + * or more contributor license agreements.  See the NOTICE file
    + * distributed with this work for additional information
    + * regarding copyright ownership.  The ASF licenses this file
    + * to you under the Apache License, Version 2.0 (the
    + * "License"); you may not use this file except in compliance
    + * with the License.  You may obtain a copy of the License at
    + *
    + *     http://www.apache.org/licenses/LICENSE-2.0
    + *
    + * Unless required by applicable law or agreed to in writing, software
    + * distributed under the License is distributed on an "AS IS" BASIS,
    + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    + * See the License for the specific language governing permissions and
    + * limitations under the License.
    + */
    +
    +package org.apache.flink.runtime.jobmaster.slotpool;
    +
    +import org.apache.flink.api.java.tuple.Tuple3;
    +import org.apache.flink.runtime.instance.SlotSharingGroupId;
    +import org.apache.flink.runtime.jobmaster.SlotRequestId;
    +import org.apache.flink.runtime.messages.Acknowledge;
    +import org.apache.flink.util.Preconditions;
    +
    +import javax.annotation.Nullable;
    +
    +import java.util.concurrent.CompletableFuture;
    +import java.util.function.Consumer;
    +
    +/**
    + * Simple {@link AllocatedSlotActions} implementations for testing purposes.
    + */
    +public class TestingAllocatedSlotActions implements AllocatedSlotActions {
    +
    +	private volatile Consumer<Tuple3<SlotRequestId, SlotSharingGroupId, Throwable>> releaseSlotConsumer;
    +
    +	public void setReleaseSlotConsumer(Consumer<Tuple3<SlotRequestId, SlotSharingGroupId, Throwable>> releaseSlotConsumer) {
    +		this.releaseSlotConsumer = Preconditions.checkNotNull(releaseSlotConsumer);
    +	}
    +
    +	@Override
    +	public CompletableFuture<Acknowledge> releaseSlot(SlotRequestId slotRequestId, @Nullable SlotSharingGroupId slotSharingGroupId, @Nullable Throwable cause) {
    +		Consumer<Tuple3<SlotRequestId, SlotSharingGroupId, Throwable>> currentReleaseSlotConsumer = this.releaseSlotConsumer;
    +
    +		if (currentReleaseSlotConsumer != null) {
    +			currentReleaseSlotConsumer.accept(Tuple3.of(slotRequestId, slotSharingGroupId, cause	));
    --- End diff --
    
    Will fix it.


---

[GitHub] flink pull request #5091: [FLINK-7956] [flip6] Add support for queued schedu...

Posted by GJL <gi...@git.apache.org>.
Github user GJL commented on a diff in the pull request:

    https://github.com/apache/flink/pull/5091#discussion_r155502971
  
    --- Diff: flink-runtime/src/test/java/org/apache/flink/runtime/jobmaster/slotpool/TestingAllocatedSlotActions.java ---
    @@ -0,0 +1,53 @@
    +/*
    + * Licensed to the Apache Software Foundation (ASF) under one
    + * or more contributor license agreements.  See the NOTICE file
    + * distributed with this work for additional information
    + * regarding copyright ownership.  The ASF licenses this file
    + * to you under the Apache License, Version 2.0 (the
    + * "License"); you may not use this file except in compliance
    + * with the License.  You may obtain a copy of the License at
    + *
    + *     http://www.apache.org/licenses/LICENSE-2.0
    + *
    + * Unless required by applicable law or agreed to in writing, software
    + * distributed under the License is distributed on an "AS IS" BASIS,
    + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    + * See the License for the specific language governing permissions and
    + * limitations under the License.
    + */
    +
    +package org.apache.flink.runtime.jobmaster.slotpool;
    +
    +import org.apache.flink.api.java.tuple.Tuple3;
    +import org.apache.flink.runtime.instance.SlotSharingGroupId;
    +import org.apache.flink.runtime.jobmaster.SlotRequestId;
    +import org.apache.flink.runtime.messages.Acknowledge;
    +import org.apache.flink.util.Preconditions;
    +
    +import javax.annotation.Nullable;
    +
    +import java.util.concurrent.CompletableFuture;
    +import java.util.function.Consumer;
    +
    +/**
    + * Simple {@link AllocatedSlotActions} implementations for testing purposes.
    + */
    +public class TestingAllocatedSlotActions implements AllocatedSlotActions {
    +
    +	private volatile Consumer<Tuple3<SlotRequestId, SlotSharingGroupId, Throwable>> releaseSlotConsumer;
    +
    +	public void setReleaseSlotConsumer(Consumer<Tuple3<SlotRequestId, SlotSharingGroupId, Throwable>> releaseSlotConsumer) {
    +		this.releaseSlotConsumer = Preconditions.checkNotNull(releaseSlotConsumer);
    +	}
    +
    +	@Override
    +	public CompletableFuture<Acknowledge> releaseSlot(SlotRequestId slotRequestId, @Nullable SlotSharingGroupId slotSharingGroupId, @Nullable Throwable cause) {
    +		Consumer<Tuple3<SlotRequestId, SlotSharingGroupId, Throwable>> currentReleaseSlotConsumer = this.releaseSlotConsumer;
    +
    +		if (currentReleaseSlotConsumer != null) {
    +			currentReleaseSlotConsumer.accept(Tuple3.of(slotRequestId, slotSharingGroupId, cause	));
    --- End diff --
    
    nit: whitespace after `cause`
    ```
    ... cause	));
    ```


---

[GitHub] flink pull request #5091: [FLINK-7956] [flip6] Add support for queued schedu...

Posted by tillrohrmann <gi...@git.apache.org>.
Github user tillrohrmann commented on a diff in the pull request:

    https://github.com/apache/flink/pull/5091#discussion_r156887866
  
    --- Diff: flink-runtime/src/main/java/org/apache/flink/runtime/jobmaster/slotpool/SlotSharingManager.java ---
    @@ -0,0 +1,722 @@
    +/*
    + * Licensed to the Apache Software Foundation (ASF) under one
    + * or more contributor license agreements.  See the NOTICE file
    + * distributed with this work for additional information
    + * regarding copyright ownership.  The ASF licenses this file
    + * to you under the Apache License, Version 2.0 (the
    + * "License"); you may not use this file except in compliance
    + * with the License.  You may obtain a copy of the License at
    + *
    + *     http://www.apache.org/licenses/LICENSE-2.0
    + *
    + * Unless required by applicable law or agreed to in writing, software
    + * distributed under the License is distributed on an "AS IS" BASIS,
    + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    + * See the License for the specific language governing permissions and
    + * limitations under the License.
    + */
    +
    +package org.apache.flink.runtime.jobmaster.slotpool;
    +
    +import org.apache.flink.annotation.VisibleForTesting;
    +import org.apache.flink.runtime.jobmaster.LogicalSlot;
    +import org.apache.flink.runtime.jobmaster.SlotContext;
    +import org.apache.flink.runtime.jobmaster.SlotOwner;
    +import org.apache.flink.runtime.jobmaster.SlotRequestId;
    +import org.apache.flink.runtime.instance.SlotSharingGroupId;
    +import org.apache.flink.runtime.jobmanager.scheduler.Locality;
    +import org.apache.flink.runtime.taskmanager.TaskManagerLocation;
    +import org.apache.flink.util.AbstractID;
    +import org.apache.flink.util.FlinkException;
    +import org.apache.flink.util.Preconditions;
    +
    +import javax.annotation.Nullable;
    +
    +import java.util.AbstractCollection;
    +import java.util.Collection;
    +import java.util.Collections;
    +import java.util.HashMap;
    +import java.util.HashSet;
    +import java.util.Iterator;
    +import java.util.Map;
    +import java.util.Objects;
    +import java.util.Set;
    +import java.util.concurrent.CompletableFuture;
    +
    +/**
    + * Manager which is responsible for slot sharing. Slot sharing allows to run different
    + * tasks in the same slot and to realize co-location constraints.
    + *
    + * <p>The SlotSharingManager allows to create a hierarchy of {@link TaskSlot} such that
    + * every {@link TaskSlot} is uniquely identified by a {@link SlotRequestId} identifying
    + * the request for the TaskSlot and a {@link AbstractID} identifying the task or the
    + * co-location constraint running in this slot.
    + *
    + * <p>The {@link TaskSlot} hierarchy is implemented by {@link MultiTaskSlot} and
    + * {@link SingleTaskSlot}. The former class represents inner nodes which can contain
    + * a number of other {@link TaskSlot} and the latter class represents the leave nodes.
    + * The hierarchy starts with a root {@link MultiTaskSlot} which is a future
    + * {@link SlotContext} assigned. The {@link SlotContext} represents the allocated slot
    + * on the TaskExecutor in which all slots of this hierarchy run. A {@link MultiTaskSlot}
    + * can be assigned multiple {@link SingleTaskSlot} or {@link MultiTaskSlot} if and only if
    + * the task slot does not yet contain another child with the same {@link AbstractID} identifying
    + * the actual task or the co-location constraint.
    + *
    + * <p>Normal slot sharing is represented by a root {@link MultiTaskSlot} which contains a set
    + * of {@link SingleTaskSlot} on the second layer. Each {@link SingleTaskSlot} represents a different
    + * task.
    + *
    + * <p>Co-location constraints are modeled by adding a {@link MultiTaskSlot} to the root node. The co-location
    + * constraint is uniquely identified by a {@link AbstractID} such that we cannot add a second co-located
    + * {@link MultiTaskSlot} to the same root node. Now all co-located tasks will be added to co-located
    + * multi task slot.
    + */
    +public class SlotSharingManager {
    +
    +	private final SlotSharingGroupId slotSharingGroupId;
    +
    +	// needed to release allocated slots after a complete multi task slot hierarchy has been released
    +	private final AllocatedSlotActions allocatedSlotActions;
    +
    +	// owner of the slots to which to return them when they are released from the outside
    +	private final SlotOwner slotOwner;
    +
    +	private final Map<SlotRequestId, TaskSlot> allTaskSlots;
    +
    +	// Root nodes which have not been completed because the allocated slot is still pending
    +	private final Map<SlotRequestId, MultiTaskSlot> unresolvedRootSlots;
    +
    +	// Root nodes which have been completed (the underlying allocated slot has been assigned)
    +	private final Map<TaskManagerLocation, Set<MultiTaskSlot>> resolvedRootSlots;
    +
    +	// Internal class to iterate over all resolved root slots
    +	private ResolvedRootSlotValues resolvedMultiTaskSlotValues;
    +
    +	public SlotSharingManager(
    +			SlotSharingGroupId slotSharingGroupId,
    +			AllocatedSlotActions allocatedSlotActions,
    +			SlotOwner slotOwner) {
    +		this.slotSharingGroupId = Preconditions.checkNotNull(slotSharingGroupId);
    +		this.allocatedSlotActions = Preconditions.checkNotNull(allocatedSlotActions);
    +		this.slotOwner = Preconditions.checkNotNull(slotOwner);
    +
    +		allTaskSlots = new HashMap<>(16);
    +		unresolvedRootSlots = new HashMap<>(16);
    +		resolvedRootSlots = new HashMap<>(16);
    +
    +		resolvedMultiTaskSlotValues = null;
    +	}
    +
    +	public boolean isEmpty() {
    +		return allTaskSlots.isEmpty();
    +	}
    +
    +	public boolean contains(SlotRequestId slotRequestId) {
    +		return allTaskSlots.containsKey(slotRequestId);
    +	}
    +
    +	@Nullable
    +	public TaskSlot getTaskSlot(SlotRequestId slotRequestId) {
    +		return allTaskSlots.get(slotRequestId);
    +	}
    +
    +	/**
    +	 * Creates a new root slot with the given {@link SlotRequestId}, {@link SlotContext} future and
    +	 * the {@link SlotRequestId} of the allocated slot.
    +	 *
    +	 * @param slotRequestId of the root slot
    +	 * @param slotContextFuture with which we create the root slot
    +	 * @param allocatedSlotRequestId slot request id of the underlying allocated slot which can be used
    +	 *                               to cancel the pending slot request or release the allocated slot
    +	 * @return New root slot
    +	 */
    +	public MultiTaskSlot createRootSlot(
    +			SlotRequestId slotRequestId,
    +			CompletableFuture<SlotContext> slotContextFuture,
    +			SlotRequestId allocatedSlotRequestId) {
    +		final MultiTaskSlot rootMultiTaskSlot = new MultiTaskSlot(
    +			slotRequestId,
    +			slotContextFuture,
    +			allocatedSlotRequestId);
    +
    +		allTaskSlots.put(slotRequestId, rootMultiTaskSlot);
    +		unresolvedRootSlots.put(slotRequestId, rootMultiTaskSlot);
    +
    +		// add the root node to the set of resolved root nodes once the SlotContext future has been completed
    +		// and we know the slot's TaskManagerLocation
    +		slotContextFuture.whenComplete(
    +			(SlotContext slotContext, Throwable throwable) -> {
    +				if (slotContext != null) {
    +					final MultiTaskSlot resolvedRootNode = unresolvedRootSlots.remove(slotRequestId);
    +
    +					if (resolvedRootNode != null) {
    +						final Set<MultiTaskSlot> innerCollection = resolvedRootSlots.computeIfAbsent(
    +							slotContext.getTaskManagerLocation(),
    +							taskManagerLocation -> new HashSet<>(4));
    +
    +						innerCollection.add(resolvedRootNode);
    +					}
    +				} else {
    +					rootMultiTaskSlot.release(throwable);
    +				}
    +			});
    +
    +		return rootMultiTaskSlot;
    +	}
    +
    +	/**
    +	 * Gets a resolved root slot which does not yet contain the given groupId. First the given set of
    +	 * preferred locations is checked.
    +	 *
    +	 * @param groupId which the returned slot must not contain
    +	 * @param locationPreferences specifying which locations are preferred
    +	 * @return the resolved root slot and its locality wrt to the specified location preferences
    +	 * 		or null if there was no root slot which did not contain the given groupId
    +	 */
    +	@Nullable
    +	public MultiTaskSlotLocality getResolvedRootSlot(AbstractID groupId, Collection<TaskManagerLocation> locationPreferences) {
    +		Preconditions.checkNotNull(locationPreferences);
    +
    +		if (locationPreferences.isEmpty()) {
    +			return getResolvedRootSlotWithoutLocationPreferences(groupId);
    +		} else {
    +			return getResolvedRootSlotWithLocationPreferences(groupId, locationPreferences);
    +		}
    +	}
    +
    +	/**
    +	 * Gets a resolved root slot which does not yet contain the given groupId. The method will try to
    +	 * find a slot of a TaskManager contained in the collection of preferred locations. If there is no such slot
    +	 * with free capacities available, then the method will look for slots of TaskManager which run on the same
    +	 * machine as the TaskManager in the collection of preferred locations. If there is no such slot, then any slot
    +	 * with free capacities is returned. If there is no such slot, then null is returned.
    +	 *
    +	 * @param groupId which the returned slot must not contain
    +	 * @param locationPreferences specifying which locations are preferred
    +	 * @return the resolved root slot and its locality wrt to the specified location preferences
    +	 * 		or null if there was not root slot which did not contain the given groupId
    +	 */
    +	@Nullable
    +	private MultiTaskSlotLocality getResolvedRootSlotWithLocationPreferences(AbstractID groupId, Collection<TaskManagerLocation> locationPreferences) {
    +		Preconditions.checkNotNull(groupId);
    +		Preconditions.checkNotNull(locationPreferences);
    +		final Set<String> hostnameSet = new HashSet<>();
    +
    +		for (TaskManagerLocation locationPreference : locationPreferences) {
    +			final Set<MultiTaskSlot> multiTaskSlots = resolvedRootSlots.get(locationPreference);
    +
    +			if (multiTaskSlots != null) {
    +				for (MultiTaskSlot multiTaskSlot : multiTaskSlots) {
    +					if (!multiTaskSlot.contains(groupId)) {
    +						return MultiTaskSlotLocality.of(multiTaskSlot, Locality.LOCAL);
    +					}
    +				}
    +
    +				hostnameSet.add(locationPreference.getHostname());
    +			}
    +		}
    +
    +		MultiTaskSlot nonLocalMultiTaskSlot = null;
    +
    +		for (Map.Entry<TaskManagerLocation, Set<MultiTaskSlot>> taskManagerLocationSetEntry : resolvedRootSlots.entrySet()) {
    +			if (hostnameSet.contains(taskManagerLocationSetEntry.getKey().getHostname())) {
    +				for (MultiTaskSlot multiTaskSlot : taskManagerLocationSetEntry.getValue()) {
    +					if (!multiTaskSlot.contains(groupId)) {
    +						return MultiTaskSlotLocality.of(multiTaskSlot, Locality.HOST_LOCAL);
    +					}
    +				}
    +			} else if (nonLocalMultiTaskSlot == null) {
    +				for (MultiTaskSlot multiTaskSlot : taskManagerLocationSetEntry.getValue()) {
    +					if (!multiTaskSlot.contains(groupId)) {
    +						nonLocalMultiTaskSlot = multiTaskSlot;
    +					}
    +				}
    +			}
    +		}
    +
    +		if (nonLocalMultiTaskSlot != null) {
    +			return MultiTaskSlotLocality.of(nonLocalMultiTaskSlot, Locality.NON_LOCAL);
    +		} else {
    +			return null;
    +		}
    +	}
    +
    +	/**
    +	 * Gets a resolved slot which does not yet contain the given groupId without any location
    +	 * preferences.
    +	 *
    +	 * @param groupId which the returned slot must not contain
    +	 * @return the resolved slot or null if there was no root slot with free capacities
    +	 */
    +	@Nullable
    +	private MultiTaskSlotLocality getResolvedRootSlotWithoutLocationPreferences(AbstractID groupId) {
    +		Preconditions.checkNotNull(groupId);
    +
    +		for (Set<MultiTaskSlot> multiTaskSlots : resolvedRootSlots.values()) {
    +			for (MultiTaskSlot multiTaskSlot : multiTaskSlots) {
    +				if (!multiTaskSlot.contains(groupId)) {
    +					return MultiTaskSlotLocality.of(multiTaskSlot, Locality.UNCONSTRAINED);
    +				}
    +			}
    +		}
    +
    +		return null;
    +	}
    +
    +	/**
    +	 * Gets an unresolved slot which does not yet contain the given groupId. An unresolved
    +	 * slot is a slot whose underlying allocated slot has not been allocated yet.
    +	 *
    +	 * @param groupId which the returned slot must not contain
    +	 * @return the unresolved slot or null if there was no root slot with free capacities
    +	 */
    +	@Nullable
    +	public MultiTaskSlot getUnresolvedRootSlot(AbstractID groupId) {
    +		for (MultiTaskSlot multiTaskSlot : unresolvedRootSlots.values()) {
    +			if (!multiTaskSlot.contains(groupId)) {
    +				return multiTaskSlot;
    +			}
    +		}
    +
    +		return null;
    +	}
    +
    +	// ------------------------------------------------------------------------
    +	// Inner classes: TaskSlot hierarchy and helper classes
    +	// ------------------------------------------------------------------------
    +
    +	/**
    +	 * Helper class which contains a {@link MultiTaskSlot} and its {@link Locality}.
    +	 */
    +	public static final class MultiTaskSlotLocality {
    +		private final MultiTaskSlot multiTaskSlot;
    +
    +		private final Locality locality;
    +
    +		public MultiTaskSlotLocality(MultiTaskSlot multiTaskSlot, Locality locality) {
    +			this.multiTaskSlot = Preconditions.checkNotNull(multiTaskSlot);
    +			this.locality = Preconditions.checkNotNull(locality);
    +		}
    +
    +		public MultiTaskSlot getMultiTaskSlot() {
    +			return multiTaskSlot;
    +		}
    +
    +		public Locality getLocality() {
    +			return locality;
    +		}
    +
    +		public static MultiTaskSlotLocality of(MultiTaskSlot multiTaskSlot, Locality locality) {
    +			return new MultiTaskSlotLocality(multiTaskSlot, locality);
    +		}
    +	}
    +
    +	/**
    +	 * Base class for all task slots.
    +	 */
    +	public abstract static class TaskSlot {
    +		// every TaskSlot has an associated slot request id
    +		private final SlotRequestId slotRequestId;
    +
    +		// all task slots except for the root slots have a group id assigned
    +		@Nullable
    +		private final AbstractID groupId;
    +
    +		protected TaskSlot(SlotRequestId slotRequestId, @Nullable AbstractID groupId) {
    +			this.slotRequestId = Preconditions.checkNotNull(slotRequestId);
    +			this.groupId = groupId;
    +		}
    +
    +		public SlotRequestId getSlotRequestId() {
    +			return slotRequestId;
    +		}
    +
    +		@Nullable
    +		public AbstractID getGroupId() {
    +			return groupId;
    +		}
    +
    +		/**
    +		 * Check whether the task slot contains the given groupId.
    +		 *
    +		 * @param groupId which to check whether it is contained
    +		 * @return true if the task slot contains the given groupId, otherwise false
    +		 */
    +		public boolean contains(AbstractID groupId) {
    +			return Objects.equals(this.groupId, groupId);
    +		}
    +
    +		/**
    +		 * Release the task slot.
    +		 *
    +		 * @param cause for the release
    +		 * @return true if the slot could be released, otherwise false
    +		 */
    +		public abstract boolean release(Throwable cause);
    +	}
    +
    +	/**
    +	 * {@link TaskSlot} implementation which can have multiple other task slots assigned as children.
    +	 */
    +	public final class MultiTaskSlot extends TaskSlot implements AllocatedSlot.Payload {
    +
    +		private final Map<AbstractID, TaskSlot> children;
    +
    +		// the root node has its parent set to null
    +		@Nullable
    +		private final MultiTaskSlot parent;
    +
    +		// underlying allocated slot
    +		private final CompletableFuture<SlotContext> slotContextFuture;
    +
    +		// slot request id of the allocated slot
    +		@Nullable
    +		private final SlotRequestId allocatedSlotRequestId;
    +
    +		// true if we are currently releasing our children
    +		private boolean releasingChildren;
    +
    +		private MultiTaskSlot(
    +				SlotRequestId slotRequestId,
    +				AbstractID groupId,
    +				MultiTaskSlot parent) {
    +			this(
    +				slotRequestId,
    +				groupId,
    +				Preconditions.checkNotNull(parent),
    +				parent.getSlotContextFuture(),
    +				null);
    +		}
    +
    +		private MultiTaskSlot(
    +				SlotRequestId slotRequestId,
    +				CompletableFuture<SlotContext> slotContextFuture,
    +				SlotRequestId allocatedSlotRequestId) {
    +			this(
    +				slotRequestId,
    +				null,
    +				null,
    +				slotContextFuture,
    +				allocatedSlotRequestId);
    +		}
    +
    +		private MultiTaskSlot(
    +				SlotRequestId slotRequestId,
    +				@Nullable AbstractID groupId,
    +				MultiTaskSlot parent,
    +				CompletableFuture<SlotContext> slotContextFuture,
    +				SlotRequestId allocatedSlotRequestId) {
    +			super(slotRequestId, groupId);
    +
    +			this.parent = parent;
    +			this.slotContextFuture = Preconditions.checkNotNull(slotContextFuture);
    +			this.allocatedSlotRequestId = allocatedSlotRequestId;
    +
    +			this.children = new HashMap<>(16);
    +			this.releasingChildren = false;
    +
    +			slotContextFuture.whenComplete(
    +				(SlotContext ignored, Throwable throwable) -> {
    +					if (throwable != null) {
    +						release(throwable);
    +					}
    +				});
    +		}
    +
    +		public CompletableFuture<SlotContext> getSlotContextFuture() {
    +			return slotContextFuture;
    +		}
    +
    +		/**
    +		 * Allocates a {@link MultiTaskSlot} and registers it under the given groupId at
    +		 * this {@link MultiTaskSlot}.
    +		 *
    +		 * @param slotRequestId of the new multi task slot
    +		 * @param groupId under which the new multi task slot is registered
    +		 * @return the newly allocated {@link MultiTaskSlot}
    +		 */
    +		MultiTaskSlot allocateMultiTaskSlot(SlotRequestId slotRequestId, AbstractID groupId) {
    +			Preconditions.checkState(!super.contains(groupId));
    +
    +			final MultiTaskSlot inner = new MultiTaskSlot(
    +				slotRequestId,
    +				groupId,
    +				this);
    +
    +			children.put(groupId, inner);
    +
    +			// register the newly allocated slot also at the SlotSharingManager
    +			allTaskSlots.put(slotRequestId, inner);
    +
    +			return inner;
    +		}
    +
    +		/**
    +		 * Allocates a {@link SingleTaskSlot} and registeres it under the given groupId at
    +		 * this {@link MultiTaskSlot}.
    +		 *
    +		 * @param slotRequestId of the new single task slot
    +		 * @param groupId under which the new single task slot is registered
    +		 * @param locality of the allocation
    +		 * @return the newly allocated {@link SingleTaskSlot}
    +		 */
    +		SingleTaskSlot allocateSingleTaskSlot(
    +				SlotRequestId slotRequestId,
    +				AbstractID groupId,
    +				Locality locality) {
    +			Preconditions.checkState(!super.contains(groupId));
    +
    +			final SingleTaskSlot leave = new SingleTaskSlot(
    +				slotRequestId,
    +				groupId,
    +				this,
    +				locality);
    +
    +			children.put(groupId, leave);
    +
    +			// register the newly allocated slot also at the SlotSharingManager
    +			allTaskSlots.put(slotRequestId, leave);
    +
    +			return leave;
    +		}
    +
    +		/**
    +		 * Checks whether this slot or any of its children contains the given groupId.
    +		 *
    +		 * @param groupId which to check whether it is contained
    +		 * @return true if this or any of its children contains the given groupId, otherwise false
    +		 */
    +		@Override
    +		public boolean contains(AbstractID groupId) {
    +			if (super.contains(groupId)) {
    +				return true;
    +			} else {
    +				for (TaskSlot taskSlot : children.values()) {
    +					if (taskSlot.contains(groupId)) {
    +						return true;
    +					}
    +				}
    +
    +				return false;
    +			}
    +		}
    +
    +		@Override
    +		public boolean release(Throwable cause) {
    +			releasingChildren = true;
    +
    +			// first release all children and remove them if they could be released immediately
    +			children.values().removeIf(node -> {
    +				boolean release = node.release(cause);
    +
    +				if (release) {
    +					allTaskSlots.remove(node.slotRequestId);
    +				}
    +
    +				return release;
    +			});
    +
    +			releasingChildren = false;
    +
    +			if (children.isEmpty()) {
    +				if (parent != null) {
    +					// we remove ourselves from our parent if we no longer have children
    +					parent.releaseChild(getGroupId());
    +				} else {
    +					// we are the root node --> remove the root node from the list of task slots
    +					allTaskSlots.remove(getSlotRequestId());
    +
    +					if (!slotContextFuture.isDone() || slotContextFuture.isCompletedExceptionally()) {
    +						// the root node should still be unresolved
    +						unresolvedRootSlots.remove(getSlotRequestId());
    +					} else {
    +						// the root node should be resolved --> we can access the slot context
    +						final SlotContext slotContext = slotContextFuture.getNow(null);
    +
    +						if (slotContext != null) {
    +							final Set<MultiTaskSlot> multiTaskSlots = resolvedRootSlots.get(slotContext.getTaskManagerLocation());
    +
    +							if (multiTaskSlots != null) {
    +								multiTaskSlots.remove(this);
    +
    +								if (multiTaskSlots.isEmpty()) {
    +									resolvedRootSlots.remove(slotContext.getTaskManagerLocation());
    +								}
    +							}
    +						}
    +					}
    +
    +					// release the underlying allocated slot
    +					allocatedSlotActions.releaseSlot(allocatedSlotRequestId, null, cause);
    +				}
    +
    +				return true;
    +			} else {
    +				return false;
    +			}
    +		}
    +
    +		/**
    +		 * Releases the child with the given childGroupId.
    +		 *
    +		 * @param childGroupId identifying the child to release
    +		 */
    +		private void releaseChild(AbstractID childGroupId) {
    +			if (!releasingChildren) {
    +				TaskSlot child = children.remove(childGroupId);
    +
    +				if (child != null) {
    +					allTaskSlots.remove(child.getSlotRequestId());
    +				}
    +
    +				if (children.isEmpty()) {
    +					release(new FlinkException("Release multi task slot because all children have been released."));
    +				}
    +			}
    +		}
    +	}
    +
    +	/**
    +	 * {@link TaskSlot} implementation which harbours a {@link LogicalSlot}. The {@link SingleTaskSlot}
    +	 * cannot have any children assigned.
    +	 */
    +	public final class SingleTaskSlot extends TaskSlot {
    +		private final MultiTaskSlot parent;
    +
    +		// future containing a LogicalSlot which is completed once the underlying SlotContext future is completed
    +		private final CompletableFuture<LogicalSlot> logicalSlotFuture;
    +
    +		private SingleTaskSlot(
    +				SlotRequestId slotRequestId,
    +				AbstractID groupId,
    +				MultiTaskSlot parent,
    +				Locality locality) {
    +			super(slotRequestId, groupId);
    +
    +			this.parent = Preconditions.checkNotNull(parent);
    +
    +			Preconditions.checkNotNull(locality);
    +			logicalSlotFuture = parent.getSlotContextFuture()
    +				.thenApply(
    +					(SlotContext slotContext) ->
    +						new SingleLogicalSlot(
    +							slotRequestId,
    +							slotContext,
    +							slotSharingGroupId,
    +							locality,
    +							slotOwner));
    +		}
    +
    +		public CompletableFuture<LogicalSlot> getLogicalSlotFuture() {
    +			return logicalSlotFuture;
    +		}
    +
    +		@Override
    +		public boolean release(Throwable cause) {
    +			logicalSlotFuture.completeExceptionally(cause);
    +
    +			boolean pendingLogicalSlotRelease = false;
    +
    +			if (logicalSlotFuture.isDone() && !logicalSlotFuture.isCompletedExceptionally()) {
    +				// we have a single task slot which we first have to release
    +				final LogicalSlot logicalSlot = logicalSlotFuture.getNow(null);
    +
    +				if (logicalSlot != null && logicalSlot.isAlive()) {
    +					pendingLogicalSlotRelease = logicalSlot.releaseSlot(cause).isDone();
    +				}
    +			}
    +
    +			if (!pendingLogicalSlotRelease) {
    +				parent.releaseChild(getGroupId());
    +			}
    +
    +			return !pendingLogicalSlotRelease;
    +		}
    +	}
    +
    +	// ------------------------------------------------------------------------
    +	// Methods and classes for testing
    +	// ------------------------------------------------------------------------
    +
    +	/**
    +	 * Returns a collection of all resolved root slots.
    +	 *
    +	 * @return Collection of all resolved root slots
    +	 */
    +	@VisibleForTesting
    +	public Collection<MultiTaskSlot> getResolvedRootSlots() {
    +		ResolvedRootSlotValues vs = resolvedMultiTaskSlotValues;
    +
    +		if (vs == null ){
    +			vs = new ResolvedRootSlotValues();
    +			resolvedMultiTaskSlotValues = vs;
    +		}
    +
    +		return vs;
    +	}
    +
    +	@VisibleForTesting
    +	Collection<MultiTaskSlot> getUnresolvedRootSlots() {
    +		return unresolvedRootSlots.values();
    +	}
    +
    +	/**
    +	 * Collection of all resolved {@link MultiTaskSlot} root slots.
    +	 */
    +	private final class ResolvedRootSlotValues extends AbstractCollection<MultiTaskSlot> {
    +
    +		@Override
    +		public Iterator<MultiTaskSlot> iterator() {
    +			return new ResolvedRootSlotIterator(resolvedRootSlots.values().iterator());
    +		}
    +
    +		@Override
    +		public int size() {
    +			int numberResolvedMultiTaskSlots = 0;
    +
    +			for (Set<MultiTaskSlot> multiTaskSlots : resolvedRootSlots.values()) {
    +				numberResolvedMultiTaskSlots += multiTaskSlots.size();
    +			}
    +
    +			return numberResolvedMultiTaskSlots;
    +		}
    +	}
    +
    +	/**
    +	 * Iterator over all resolved {@link MultiTaskSlot} root slots.
    +	 */
    +	private static final class ResolvedRootSlotIterator implements Iterator<MultiTaskSlot> {
    +		private final Iterator<Set<MultiTaskSlot>> baseIterator;
    +		private Iterator<MultiTaskSlot> currentIterator;
    +
    +		private ResolvedRootSlotIterator(Iterator<Set<MultiTaskSlot>> baseIterator) {
    +			this.baseIterator = Preconditions.checkNotNull(baseIterator);
    +
    +			if (baseIterator.hasNext()) {
    +				currentIterator = baseIterator.next().iterator();
    +			} else {
    +				currentIterator = Collections.emptyIterator();
    +			}
    +		}
    +
    +		@Override
    +		public boolean hasNext() {
    +			progressToNextElement();
    +
    +			return currentIterator.hasNext();
    +		}
    +
    +		@Override
    +		public MultiTaskSlot next() {
    +			progressToNextElement();
    +
    +			return currentIterator.next();
    +		}
    +
    +		private void progressToNextElement() {
    +			while(baseIterator.hasNext() && ! currentIterator.hasNext()) {
    --- End diff --
    
    Good catch. Will correct it.


---

[GitHub] flink pull request #5091: [FLINK-7956] [flip6] Add support for queued schedu...

Posted by tillrohrmann <gi...@git.apache.org>.
Github user tillrohrmann commented on a diff in the pull request:

    https://github.com/apache/flink/pull/5091#discussion_r156901374
  
    --- Diff: flink-runtime/src/main/java/org/apache/flink/runtime/jobmaster/slotpool/SlotPool.java ---
    @@ -266,104 +279,367 @@ public void disconnectResourceManager() {
     	// ------------------------------------------------------------------------
     
     	@Override
    -	public CompletableFuture<SimpleSlot> allocateSlot(
    -			SlotRequestID requestId,
    -			ScheduledUnit task,
    -			ResourceProfile resources,
    -			Iterable<TaskManagerLocation> locationPreferences,
    +	public CompletableFuture<LogicalSlot> allocateSlot(
    +			SlotRequestId slotRequestId,
    +			ScheduledUnit scheduledUnit,
    +			ResourceProfile resourceProfile,
    +			Collection<TaskManagerLocation> locationPreferences,
    +			boolean allowQueuedScheduling,
     			Time timeout) {
     
    -		return internalAllocateSlot(requestId, task, resources, locationPreferences);
    +		return internalAllocateSlot(
    +			slotRequestId,
    +			scheduledUnit,
    +			resourceProfile,
    +			locationPreferences,
    +			allowQueuedScheduling);
     	}
     
    -	@Override
    -	public void returnAllocatedSlot(Slot slot) {
    -		internalReturnAllocatedSlot(slot);
    +	private CompletableFuture<LogicalSlot> internalAllocateSlot(
    +			SlotRequestId slotRequestId,
    +			ScheduledUnit task,
    +			ResourceProfile resourceProfile,
    +			Collection<TaskManagerLocation> locationPreferences,
    +			boolean allowQueuedScheduling) {
    +
    +		final SlotSharingGroupId slotSharingGroupId = task.getSlotSharingGroupId();
    +
    +		if (slotSharingGroupId != null) {
    +			// allocate slot with slot sharing
    +			final SlotSharingManager multiTaskSlotManager = slotSharingManagers.computeIfAbsent(
    +				slotSharingGroupId,
    +				id -> new SlotSharingManager(
    +					id,
    +					this,
    +					providerAndOwner));
    +
    +			final SlotSharingManager.MultiTaskSlotLocality multiTaskSlotFuture;
    +
    +			try {
    +				if (task.getCoLocationConstraint() != null) {
    +					multiTaskSlotFuture = allocateCoLocatedMultiTaskSlot(
    +						task.getCoLocationConstraint(),
    +						multiTaskSlotManager,
    +						resourceProfile,
    +						locationPreferences,
    +						allowQueuedScheduling);
    +				} else {
    +					multiTaskSlotFuture = allocateMultiTaskSlot(
    +						task.getJobVertexId(), multiTaskSlotManager,
    +						resourceProfile,
    +						locationPreferences,
    +						allowQueuedScheduling);
    +				}
    +			} catch (NoResourceAvailableException noResourceException) {
    +				return FutureUtils.completedExceptionally(noResourceException);
    +			}
    +
    +			// sanity check
    +			Preconditions.checkState(!multiTaskSlotFuture.getMultiTaskSlot().contains(task.getJobVertexId()));
    +
    +			final SlotSharingManager.SingleTaskSlot leave = multiTaskSlotFuture.getMultiTaskSlot().allocateSingleTaskSlot(
    +				slotRequestId,
    +				task.getJobVertexId(),
    +				multiTaskSlotFuture.getLocality());
    +
    +			return leave.getLogicalSlotFuture();
    +		} else {
    +			// request an allocated slot to assign a single logical slot to
    +			CompletableFuture<SlotAndLocality> slotAndLocalityFuture = requestAllocatedSlot(
    +				slotRequestId,
    +				resourceProfile,
    +				locationPreferences,
    +				allowQueuedScheduling);
    +
    +			return slotAndLocalityFuture.thenApply(
    +				(SlotAndLocality slotAndLocality) -> {
    +					final AllocatedSlot allocatedSlot = slotAndLocality.getSlot();
    +
    +					final SingleLogicalSlot singleTaskSlot = new SingleLogicalSlot(
    +						slotRequestId,
    +						allocatedSlot,
    +						null,
    +						slotAndLocality.getLocality(),
    +						providerAndOwner);
    +
    +					if (allocatedSlot.tryAssignPayload(singleTaskSlot)) {
    +						return singleTaskSlot;
    +					} else {
    +						final FlinkException flinkException = new FlinkException("Could not assign payload to allocated slot " + allocatedSlot.getAllocationId() + '.');
    +						releaseSlot(slotRequestId, null, flinkException);
    +						throw new CompletionException(flinkException);
    +					}
    +				});
    +		}
     	}
     
    -	@Override
    -	public CompletableFuture<Acknowledge> cancelSlotAllocation(SlotRequestID requestId) {
    -		final PendingRequest pendingRequest = removePendingRequest(requestId);
    +	/**
    +	 * Allocates a co-located {@link SlotSharingManager.MultiTaskSlot} for the given {@link CoLocationConstraint}.
    +	 *
    +	 * <p>If allowQueuedScheduling is true, then the returned {@link SlotSharingManager.MultiTaskSlot} can be
    +	 * uncompleted.
    +	 *
    +	 * @param coLocationConstraint for which to allocate a {@link SlotSharingManager.MultiTaskSlot}
    +	 * @param multiTaskSlotManager responsible for the slot sharing group for which to allocate the slot
    +	 * @param resourceProfile specifying the requirements for the requested slot
    +	 * @param locationPreferences containing preferred TaskExecutors on which to allocate the slot
    +	 * @param allowQueuedScheduling true if queued scheduling (the returned task slot must not be completed yet) is allowed, otherwise false
    +	 * @return A {@link SlotSharingManager.MultiTaskSlotLocality} which contains the allocated{@link SlotSharingManager.MultiTaskSlot}
    +	 * 		and its locality wrt the given location preferences
    +	 * @throws NoResourceAvailableException if no task slot could be allocated
    +	 */
    +	private SlotSharingManager.MultiTaskSlotLocality allocateCoLocatedMultiTaskSlot(
    +			CoLocationConstraint coLocationConstraint,
    +			SlotSharingManager multiTaskSlotManager,
    +			ResourceProfile resourceProfile,
    +			Collection<TaskManagerLocation> locationPreferences,
    +			boolean allowQueuedScheduling) throws NoResourceAvailableException {
    +		final SlotRequestId coLocationSlotRequestId = coLocationConstraint.getSlotRequestId();
    +
    +		if (coLocationSlotRequestId != null) {
    +			// we have a slot assigned --> try to retrieve it
    +			final SlotSharingManager.TaskSlot taskSlot = multiTaskSlotManager.getTaskSlot(coLocationSlotRequestId);
    +
    +			if (taskSlot != null) {
    +				Preconditions.checkState(taskSlot instanceof SlotSharingManager.MultiTaskSlot);
    +				return SlotSharingManager.MultiTaskSlotLocality.of(((SlotSharingManager.MultiTaskSlot) taskSlot), Locality.LOCAL);
    +			} else {
    +				// the slot may have been cancelled in the mean time
    +				coLocationConstraint.setSlotRequestId(null);
    +			}
    +		}
     
    -		if (pendingRequest != null) {
    -			failPendingRequest(pendingRequest, new CancellationException("Allocation with request id" + requestId + " cancelled."));
    +		final Collection<TaskManagerLocation> actualLocationPreferences;
    +
    +		if (coLocationConstraint.isAssigned()) {
    +			actualLocationPreferences = Collections.singleton(coLocationConstraint.getLocation());
     		} else {
    -			final Slot slot = allocatedSlots.get(requestId);
    +			actualLocationPreferences = locationPreferences;
    +		}
    +
    +		// get a new multi task slot
    +		final SlotSharingManager.MultiTaskSlotLocality multiTaskSlotLocality = allocateMultiTaskSlot(
    +			coLocationConstraint.getGroupId(), multiTaskSlotManager,
    +			resourceProfile,
    +			actualLocationPreferences,
    +			allowQueuedScheduling);
    +
    +		// check whether we fulfill the co-location constraint
    +		if (coLocationConstraint.isAssigned() && multiTaskSlotLocality.getLocality() != Locality.LOCAL) {
    +			multiTaskSlotLocality.getMultiTaskSlot().release(
    +				new FlinkException("Multi task slot is not local and, thus, does not fulfill the co-location constraint."));
     
    -			if (slot != null) {
    -				LOG.info("Returning allocated slot {} because the corresponding allocation request {} was cancelled.", slot, requestId);
    -				if (slot.markCancelled()) {
    -					internalReturnAllocatedSlot(slot);
    +			throw new NoResourceAvailableException("Could not allocate a local multi task slot for the " +
    +				"co location constraint " + coLocationConstraint + '.');
    +		}
    +
    +		final SlotRequestId slotRequestId = new SlotRequestId();
    +		final SlotSharingManager.MultiTaskSlot coLocationSlot = multiTaskSlotLocality.getMultiTaskSlot().allocateMultiTaskSlot(
    +			slotRequestId,
    +			coLocationConstraint.getGroupId());
    +
    +		// mark the requested slot as co-located slot for other co-located tasks
    +		coLocationConstraint.setSlotRequestId(slotRequestId);
    +
    +		// lock the co-location constraint once we have obtained the allocated slot
    +		coLocationSlot.getSlotContextFuture().whenComplete(
    +			(SlotContext slotContext, Throwable throwable) -> {
    +				if (throwable == null) {
    +					// check whether we are still assigned to the co-location constraint
    +					if (Objects.equals(coLocationConstraint.getSlotRequestId(), slotRequestId)) {
    +						coLocationConstraint.lockLocation(slotContext.getTaskManagerLocation());
    +					}
     				}
    +			});
    +
    +		return SlotSharingManager.MultiTaskSlotLocality.of(coLocationSlot, multiTaskSlotLocality.getLocality());
    +	}
    +
    +	/**
    +	 * Allocates a {@link SlotSharingManager.MultiTaskSlot} for the given groupId which is in the
    +	 * slot sharing group for which the given {@link SlotSharingManager} is responsible.
    +	 *
    +	 * <p>If allowQueuedScheduling is true, then the method can return an uncompleted {@link SlotSharingManager.MultiTaskSlot}.
    +	 *
    +	 * @param groupId for which to allocate a new {@link SlotSharingManager.MultiTaskSlot}
    +	 * @param slotSharingManager responsible for the slot sharing group for which to allocate the slot
    +	 * @param resourceProfile specifying the requirements for the requested slot
    +	 * @param locationPreferences containing preferred TaskExecutors on which to allocate the slot
    +	 * @param allowQueuedScheduling true if queued scheduling (the returned task slot must not be completed yet) is allowed, otherwise false
    +	 * @return A {@link SlotSharingManager.MultiTaskSlotLocality} which contains the allocated {@link SlotSharingManager.MultiTaskSlot}
    +	 * 		and its locality wrt the given location preferences
    +	 * @throws NoResourceAvailableException if no task slot could be allocated
    +	 */
    +	private SlotSharingManager.MultiTaskSlotLocality allocateMultiTaskSlot(
    +			AbstractID groupId,
    +			SlotSharingManager slotSharingManager,
    +			ResourceProfile resourceProfile,
    +			Collection<TaskManagerLocation> locationPreferences,
    +			boolean allowQueuedScheduling) throws NoResourceAvailableException {
    +
    +		// check first whether we have a resolved root slot which we can use
    +		SlotSharingManager.MultiTaskSlotLocality multiTaskSlotLocality = slotSharingManager.getResolvedRootSlot(
    +			groupId,
    +			locationPreferences);
    +
    +		if (multiTaskSlotLocality != null && multiTaskSlotLocality.getLocality() == Locality.LOCAL) {
    +			return multiTaskSlotLocality;
    +		}
    +
    +		final SlotRequestId allocatedSlotRequestId = new SlotRequestId();
    +		final SlotRequestId multiTaskSlotRequestId = new SlotRequestId();
    +
    +		// check whether we have an allocated slot available which we can use to create a new multi task slot in
    +		final SlotAndLocality slotAndLocality = pollAndAllocateSlot(allocatedSlotRequestId, resourceProfile, locationPreferences);
    +
    +		if (slotAndLocality != null && (slotAndLocality.getLocality() == Locality.LOCAL || multiTaskSlotLocality == null)) {
    +
    +			final AllocatedSlot allocatedSlot = slotAndLocality.getSlot();
    +			final SlotSharingManager.MultiTaskSlot multiTaskSlot = slotSharingManager.createRootSlot(
    +				multiTaskSlotRequestId,
    +				CompletableFuture.completedFuture(slotAndLocality.getSlot()),
    +				allocatedSlotRequestId);
    +
    +			if (allocatedSlot.tryAssignPayload(multiTaskSlot)) {
    +				return SlotSharingManager.MultiTaskSlotLocality.of(multiTaskSlot, slotAndLocality.getLocality());
     			} else {
    -				LOG.debug("There was no slot allocation with {} to be cancelled.", requestId);
    +				multiTaskSlot.release(new FlinkException("Could not assign payload to allocated slot " +
    +					allocatedSlot.getAllocationId() + '.'));
     			}
     		}
     
    -		return CompletableFuture.completedFuture(Acknowledge.get());
    -	}
    +		if (multiTaskSlotLocality != null) {
    +			// prefer slot sharing group slots over unused slots
    +			if (slotAndLocality != null) {
    +				releaseSlot(
    +					allocatedSlotRequestId,
    +					null,
    +					new FlinkException("Locality constraint is not better fulfilled by allocated slot."));
    +			}
    +			return multiTaskSlotLocality;
    +		}
     
    -	CompletableFuture<SimpleSlot> internalAllocateSlot(
    -			SlotRequestID requestId,
    -			ScheduledUnit task,
    -			ResourceProfile resources,
    -			Iterable<TaskManagerLocation> locationPreferences) {
    +		if (allowQueuedScheduling) {
    +			// there is no slot immediately available --> check first for uncompleted slots at the slot sharing group
    +			SlotSharingManager.MultiTaskSlot multiTaskSlotFuture = slotSharingManager.getUnresolvedRootSlot(groupId);
    +
    +			if (multiTaskSlotFuture == null) {
    +				// it seems as if we have to request a new slot from the resource manager, this is always the last resort!!!
    +				final CompletableFuture<AllocatedSlot> futureSlot = requestNewAllocatedSlot(allocatedSlotRequestId, resourceProfile);
    +
    +				multiTaskSlotFuture = slotSharingManager.createRootSlot(
    +					multiTaskSlotRequestId,
    +					futureSlot.thenApply(Function.identity()),
    --- End diff --
    
    Good point. Will change it.


---