From 548804adc2b675042e59b9e2f6bfba7b0428024c Mon Sep 17 00:00:00 2001 From: Fabian Mastenbroek Date: Tue, 31 Mar 2020 22:24:13 +0200 Subject: feat: Add reversed policies and random allocation policy --- .../virt/service/SimpleVirtProvisioningService.kt | 22 ++++------ .../virt/service/VirtProvisioningServiceEvent.kt | 43 ------------------- .../virt/service/allocation/AllocationPolicy.kt | 18 +++++--- .../AvailableCoreMemoryAllocationPolicy.kt | 16 ++++---- .../allocation/AvailableMemoryAllocationPolicy.kt | 13 +++--- .../allocation/ComparableAllocationPolicyLogic.kt | 48 ++++++++++++++++++++++ .../NumberOfActiveServersAllocationPolicy.kt | 13 +++--- .../allocation/ProvisionedCoresAllocationPolicy.kt | 15 ++++--- .../service/allocation/RandomAllocationPolicy.kt | 47 +++++++++++++++++++++ .../opendc/experiments/sc20/TestExperiment.kt | 11 +++-- 10 files changed, 157 insertions(+), 89 deletions(-) delete mode 100644 opendc/opendc-compute/src/main/kotlin/com/atlarge/opendc/compute/virt/service/VirtProvisioningServiceEvent.kt create mode 100644 opendc/opendc-compute/src/main/kotlin/com/atlarge/opendc/compute/virt/service/allocation/ComparableAllocationPolicyLogic.kt create mode 100644 opendc/opendc-compute/src/main/kotlin/com/atlarge/opendc/compute/virt/service/allocation/RandomAllocationPolicy.kt diff --git a/opendc/opendc-compute/src/main/kotlin/com/atlarge/opendc/compute/virt/service/SimpleVirtProvisioningService.kt b/opendc/opendc-compute/src/main/kotlin/com/atlarge/opendc/compute/virt/service/SimpleVirtProvisioningService.kt index 07693200..c7347783 100644 --- a/opendc/opendc-compute/src/main/kotlin/com/atlarge/opendc/compute/virt/service/SimpleVirtProvisioningService.kt +++ b/opendc/opendc-compute/src/main/kotlin/com/atlarge/opendc/compute/virt/service/SimpleVirtProvisioningService.kt @@ -2,6 +2,7 @@ package com.atlarge.opendc.compute.virt.service import com.atlarge.odcsim.SimulationContext import com.atlarge.odcsim.flow.EventFlow +import com.atlarge.odcsim.simulationContext import com.atlarge.opendc.compute.core.Flavor import com.atlarge.opendc.compute.core.Server import com.atlarge.opendc.compute.core.ServerEvent @@ -57,14 +58,9 @@ class SimpleVirtProvisioningService( override val hypervisorEvents: Flow = EventFlow() /** - * The internal event flow to emit to. + * The allocation logic to use. */ - private val internalEventFlow = EventFlow() - - /** - * The allocation comparator to use. - */ - private val allocationComparator = allocationPolicy(CoroutineScope(coroutineContext), internalEventFlow) + private val allocationLogic = allocationPolicy() init { launch { @@ -119,19 +115,21 @@ class SimpleVirtProvisioningService( } private suspend fun schedule() { + val log = simulationContext.log val imagesToBeScheduled = incomingImages.toSet() for (imageInstance in imagesToBeScheduled) { - val selectedHv = availableHypervisors.minWith(allocationComparator.thenBy { it.server.uid }) ?: break + val requiredMemory = (imageInstance.image as VmImage).requiredMemory + val selectedHv = allocationLogic.select(availableHypervisors, imageInstance) ?: break try { - println("Spawning ${imageInstance.image}") + log.info("Spawning ${imageInstance.image} on ${selectedHv.server}") incomingImages -= imageInstance // Speculatively update the hypervisor view information to prevent other images in the queue from // deciding on stale values. selectedHv.numberOfActiveServers++ selectedHv.provisionedCores += imageInstance.flavor.cpuCount - selectedHv.availableMemory -= (imageInstance.image as VmImage).requiredMemory // XXX Temporary hack + selectedHv.availableMemory -= requiredMemory // XXX Temporary hack val server = selectedHv.driver.spawn( imageInstance.name, @@ -146,7 +144,7 @@ class SimpleVirtProvisioningService( selectedHv.numberOfActiveServers-- selectedHv.provisionedCores -= imageInstance.flavor.cpuCount - selectedHv.availableMemory += (imageInstance.image as VmImage).requiredMemory + selectedHv.availableMemory += requiredMemory } } } @@ -162,13 +160,11 @@ class SimpleVirtProvisioningService( 0 ) hypervisors[server] = hv - internalEventFlow.emit(VirtProvisioningServiceEvent.HypervisorAdded(hv.uid)) } ServerState.SHUTOFF, ServerState.ERROR -> { val hv = hypervisors[server] ?: return hv.provisionedCores -= server.flavor.cpuCount availableHypervisors -= hv - internalEventFlow.emit(VirtProvisioningServiceEvent.HypervisorRemoved(hv.uid)) requestCycle() } else -> throw IllegalStateException() diff --git a/opendc/opendc-compute/src/main/kotlin/com/atlarge/opendc/compute/virt/service/VirtProvisioningServiceEvent.kt b/opendc/opendc-compute/src/main/kotlin/com/atlarge/opendc/compute/virt/service/VirtProvisioningServiceEvent.kt deleted file mode 100644 index bab43b90..00000000 --- a/opendc/opendc-compute/src/main/kotlin/com/atlarge/opendc/compute/virt/service/VirtProvisioningServiceEvent.kt +++ /dev/null @@ -1,43 +0,0 @@ -/* - * MIT License - * - * Copyright (c) 2020 atlarge-research - * - * Permission is hereby granted, free of charge, to any person obtaining a copy - * of this software and associated documentation files (the "Software"), to deal - * in the Software without restriction, including without limitation the rights - * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell - * copies of the Software, and to permit persons to whom the Software is - * furnished to do so, subject to the following conditions: - * - * The above copyright notice and this permission notice shall be included in all - * copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR - * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE - * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER - * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, - * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - */ - -package com.atlarge.opendc.compute.virt.service - -import java.util.UUID - -/** - * An internal event emitted by the [VirtProvisioningService] for the allocation policies to keep track of the - * available hypervisors. - */ -public sealed class VirtProvisioningServiceEvent { - /** - * This event is emitted when a hypervisor is added to the pool of schedulable hypervisors. - */ - public data class HypervisorAdded(val uid: UUID) : VirtProvisioningServiceEvent() - - /** - * This event is emitted when a hypervisor is removed from the pool of schedulable hypervisors. - */ - public data class HypervisorRemoved(val uid: UUID) : VirtProvisioningServiceEvent() -} diff --git a/opendc/opendc-compute/src/main/kotlin/com/atlarge/opendc/compute/virt/service/allocation/AllocationPolicy.kt b/opendc/opendc-compute/src/main/kotlin/com/atlarge/opendc/compute/virt/service/allocation/AllocationPolicy.kt index b1ec53b3..b7c9388d 100644 --- a/opendc/opendc-compute/src/main/kotlin/com/atlarge/opendc/compute/virt/service/allocation/AllocationPolicy.kt +++ b/opendc/opendc-compute/src/main/kotlin/com/atlarge/opendc/compute/virt/service/allocation/AllocationPolicy.kt @@ -2,16 +2,24 @@ package com.atlarge.opendc.compute.virt.service.allocation import com.atlarge.opendc.compute.metal.Node import com.atlarge.opendc.compute.virt.service.HypervisorView -import com.atlarge.opendc.compute.virt.service.VirtProvisioningServiceEvent -import kotlinx.coroutines.CoroutineScope -import kotlinx.coroutines.flow.Flow +import com.atlarge.opendc.compute.virt.service.SimpleVirtProvisioningService /** * A policy for selecting the [Node] an image should be deployed to, */ -interface AllocationPolicy { +public interface AllocationPolicy { + /** + * The logic of the allocation policy. + */ + public interface Logic { + /** + * Select the node on which the server should be scheduled. + */ + public fun select(hypervisors: Set, image: SimpleVirtProvisioningService.ImageView): HypervisorView? + } + /** * Builds the logic of the policy. */ - operator fun invoke(scope: CoroutineScope, events: Flow): Comparator + operator fun invoke(): Logic } diff --git a/opendc/opendc-compute/src/main/kotlin/com/atlarge/opendc/compute/virt/service/allocation/AvailableCoreMemoryAllocationPolicy.kt b/opendc/opendc-compute/src/main/kotlin/com/atlarge/opendc/compute/virt/service/allocation/AvailableCoreMemoryAllocationPolicy.kt index 6232d087..79b622d2 100644 --- a/opendc/opendc-compute/src/main/kotlin/com/atlarge/opendc/compute/virt/service/allocation/AvailableCoreMemoryAllocationPolicy.kt +++ b/opendc/opendc-compute/src/main/kotlin/com/atlarge/opendc/compute/virt/service/allocation/AvailableCoreMemoryAllocationPolicy.kt @@ -25,14 +25,16 @@ package com.atlarge.opendc.compute.virt.service.allocation import com.atlarge.opendc.compute.virt.service.HypervisorView -import com.atlarge.opendc.compute.virt.service.VirtProvisioningServiceEvent -import kotlinx.coroutines.CoroutineScope -import kotlinx.coroutines.flow.Flow /** - * An [AllocationPolicy] that selects the machine with the highest amount of memory per core. + * An [AllocationPolicy] that selects the machine with the highest/lowest amount of memory per core. + * + * @param reversed An option to reverse the order of the machines (lower amount of memory scores better). */ -public class AvailableCoreMemoryAllocationPolicy : AllocationPolicy { - override fun invoke(scope: CoroutineScope, events: Flow): Comparator = - compareBy { -it.availableMemory / it.server.flavor.cpuCount } +public class AvailableCoreMemoryAllocationPolicy(val reversed: Boolean = false) : AllocationPolicy { + override fun invoke(): AllocationPolicy.Logic = object : ComparableAllocationPolicyLogic { + override val comparator: Comparator = + compareBy { -it.availableMemory / it.server.flavor.cpuCount } + .run { if (reversed) reversed() else this } + } } diff --git a/opendc/opendc-compute/src/main/kotlin/com/atlarge/opendc/compute/virt/service/allocation/AvailableMemoryAllocationPolicy.kt b/opendc/opendc-compute/src/main/kotlin/com/atlarge/opendc/compute/virt/service/allocation/AvailableMemoryAllocationPolicy.kt index 06c82209..c081244f 100644 --- a/opendc/opendc-compute/src/main/kotlin/com/atlarge/opendc/compute/virt/service/allocation/AvailableMemoryAllocationPolicy.kt +++ b/opendc/opendc-compute/src/main/kotlin/com/atlarge/opendc/compute/virt/service/allocation/AvailableMemoryAllocationPolicy.kt @@ -1,14 +1,15 @@ package com.atlarge.opendc.compute.virt.service.allocation import com.atlarge.opendc.compute.virt.service.HypervisorView -import com.atlarge.opendc.compute.virt.service.VirtProvisioningServiceEvent -import kotlinx.coroutines.CoroutineScope -import kotlinx.coroutines.flow.Flow /** * Allocation policy that selects the node with the most available memory. + * + * @param reversed A flag to reverse the order (least amount of memory scores the best). */ -public class AvailableMemoryAllocationPolicy : AllocationPolicy { - override fun invoke(scope: CoroutineScope, events: Flow): Comparator = - compareBy { -it.availableMemory } +public class AvailableMemoryAllocationPolicy(val reversed: Boolean = false) : AllocationPolicy { + override fun invoke(): AllocationPolicy.Logic = object : ComparableAllocationPolicyLogic { + override val comparator: Comparator = compareBy { -it.availableMemory } + .run { if (reversed) reversed() else this } + } } diff --git a/opendc/opendc-compute/src/main/kotlin/com/atlarge/opendc/compute/virt/service/allocation/ComparableAllocationPolicyLogic.kt b/opendc/opendc-compute/src/main/kotlin/com/atlarge/opendc/compute/virt/service/allocation/ComparableAllocationPolicyLogic.kt new file mode 100644 index 00000000..5e41bcef --- /dev/null +++ b/opendc/opendc-compute/src/main/kotlin/com/atlarge/opendc/compute/virt/service/allocation/ComparableAllocationPolicyLogic.kt @@ -0,0 +1,48 @@ +/* + * MIT License + * + * Copyright (c) 2020 atlarge-research + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +package com.atlarge.opendc.compute.virt.service.allocation + +import com.atlarge.opendc.compute.core.image.VmImage +import com.atlarge.opendc.compute.virt.service.HypervisorView +import com.atlarge.opendc.compute.virt.service.SimpleVirtProvisioningService + +/** + * The logic for an [AllocationPolicy] that uses a [Comparator] to select the appropriate node. + */ +interface ComparableAllocationPolicyLogic : AllocationPolicy.Logic { + /** + * The comparator to use. + */ + public val comparator: Comparator + + override fun select( + hypervisors: Set, + image: SimpleVirtProvisioningService.ImageView + ): HypervisorView? { + return hypervisors.asSequence() + .filter { it.availableMemory >= (image.image as VmImage).requiredMemory } + .minWith(comparator.thenBy { it.server.uid }) + } +} diff --git a/opendc/opendc-compute/src/main/kotlin/com/atlarge/opendc/compute/virt/service/allocation/NumberOfActiveServersAllocationPolicy.kt b/opendc/opendc-compute/src/main/kotlin/com/atlarge/opendc/compute/virt/service/allocation/NumberOfActiveServersAllocationPolicy.kt index b95d4260..7e3e5864 100644 --- a/opendc/opendc-compute/src/main/kotlin/com/atlarge/opendc/compute/virt/service/allocation/NumberOfActiveServersAllocationPolicy.kt +++ b/opendc/opendc-compute/src/main/kotlin/com/atlarge/opendc/compute/virt/service/allocation/NumberOfActiveServersAllocationPolicy.kt @@ -1,14 +1,15 @@ package com.atlarge.opendc.compute.virt.service.allocation import com.atlarge.opendc.compute.virt.service.HypervisorView -import com.atlarge.opendc.compute.virt.service.VirtProvisioningServiceEvent -import kotlinx.coroutines.CoroutineScope -import kotlinx.coroutines.flow.Flow /** * Allocation policy that selects the node with the least amount of active servers. + * + * @param reversed A flag to reverse the order, such that the node with the most active servers is selected. */ -public class NumberOfActiveServersAllocationPolicy : AllocationPolicy { - override fun invoke(scope: CoroutineScope, events: Flow): Comparator = - compareBy { it.numberOfActiveServers } +public class NumberOfActiveServersAllocationPolicy(val reversed: Boolean = false) : AllocationPolicy { + override fun invoke(): AllocationPolicy.Logic = object : ComparableAllocationPolicyLogic { + override val comparator: Comparator = compareBy { it.numberOfActiveServers } + .run { if (reversed) reversed() else this } + } } diff --git a/opendc/opendc-compute/src/main/kotlin/com/atlarge/opendc/compute/virt/service/allocation/ProvisionedCoresAllocationPolicy.kt b/opendc/opendc-compute/src/main/kotlin/com/atlarge/opendc/compute/virt/service/allocation/ProvisionedCoresAllocationPolicy.kt index 816d85bf..e1a995a0 100644 --- a/opendc/opendc-compute/src/main/kotlin/com/atlarge/opendc/compute/virt/service/allocation/ProvisionedCoresAllocationPolicy.kt +++ b/opendc/opendc-compute/src/main/kotlin/com/atlarge/opendc/compute/virt/service/allocation/ProvisionedCoresAllocationPolicy.kt @@ -25,15 +25,18 @@ package com.atlarge.opendc.compute.virt.service.allocation import com.atlarge.opendc.compute.virt.service.HypervisorView -import com.atlarge.opendc.compute.virt.service.VirtProvisioningServiceEvent -import kotlinx.coroutines.CoroutineScope -import kotlinx.coroutines.flow.Flow /** * An [AllocationPolicy] that takes into account the number of vCPUs that have been provisioned on this machine * relative to its core count. + * + * @param reversed A flag to reverse the order of the policy, such that the machine with the most provisioned cores + * is selected. */ -class ProvisionedCoresAllocationPolicy : AllocationPolicy { - override fun invoke(scope: CoroutineScope, events: Flow): Comparator = - compareBy { it.provisionedCores / it.server.flavor.cpuCount } +class ProvisionedCoresAllocationPolicy(val reversed: Boolean = false) : AllocationPolicy { + override fun invoke(): AllocationPolicy.Logic = object : ComparableAllocationPolicyLogic { + override val comparator: Comparator = + compareBy { it.provisionedCores / it.server.flavor.cpuCount } + .run { if (reversed) reversed() else this } + } } diff --git a/opendc/opendc-compute/src/main/kotlin/com/atlarge/opendc/compute/virt/service/allocation/RandomAllocationPolicy.kt b/opendc/opendc-compute/src/main/kotlin/com/atlarge/opendc/compute/virt/service/allocation/RandomAllocationPolicy.kt new file mode 100644 index 00000000..142846ac --- /dev/null +++ b/opendc/opendc-compute/src/main/kotlin/com/atlarge/opendc/compute/virt/service/allocation/RandomAllocationPolicy.kt @@ -0,0 +1,47 @@ +/* + * MIT License + * + * Copyright (c) 2020 atlarge-research + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +package com.atlarge.opendc.compute.virt.service.allocation + +import com.atlarge.opendc.compute.core.image.VmImage +import com.atlarge.opendc.compute.virt.service.HypervisorView +import com.atlarge.opendc.compute.virt.service.SimpleVirtProvisioningService +import kotlin.random.Random + +/** + * An [AllocationPolicy] that select a random node on which the server fits. + */ +public class RandomAllocationPolicy(val random: Random = Random(0)) : AllocationPolicy { + @OptIn(ExperimentalStdlibApi::class) + override fun invoke(): AllocationPolicy.Logic = object : AllocationPolicy.Logic { + override fun select( + hypervisors: Set, + image: SimpleVirtProvisioningService.ImageView + ): HypervisorView? { + return hypervisors.asIterable() + .filter { it.availableMemory >= (image.image as VmImage).requiredMemory } + .randomOrNull(random) + } + } +} diff --git a/opendc/opendc-experiments-sc20/src/main/kotlin/com/atlarge/opendc/experiments/sc20/TestExperiment.kt b/opendc/opendc-experiments-sc20/src/main/kotlin/com/atlarge/opendc/experiments/sc20/TestExperiment.kt index 0c5bf461..cc403e6e 100644 --- a/opendc/opendc-experiments-sc20/src/main/kotlin/com/atlarge/opendc/experiments/sc20/TestExperiment.kt +++ b/opendc/opendc-experiments-sc20/src/main/kotlin/com/atlarge/opendc/experiments/sc20/TestExperiment.kt @@ -40,6 +40,7 @@ import com.atlarge.opendc.compute.virt.service.allocation.AvailableCoreMemoryAll import com.atlarge.opendc.compute.virt.service.allocation.AvailableMemoryAllocationPolicy import com.atlarge.opendc.compute.virt.service.allocation.NumberOfActiveServersAllocationPolicy import com.atlarge.opendc.compute.virt.service.allocation.ProvisionedCoresAllocationPolicy +import com.atlarge.opendc.compute.virt.service.allocation.RandomAllocationPolicy import com.atlarge.opendc.core.failure.CorrelatedFaultInjector import com.atlarge.opendc.core.failure.FailureDomain import com.atlarge.opendc.core.failure.FaultInjector @@ -76,7 +77,7 @@ class ExperimentParameters(parser: ArgParser) { } .default { emptyList() } val failures by parser.flagging("-x", "--failures", help = "enable (correlated) machine failures") - val allocationPolicy by parser.storing("name of VM allocation policy to use").default("mem") + val allocationPolicy by parser.storing("name of VM allocation policy to use").default("core-mem") fun getSelectedVmList(): List { return if (selectedVms.isEmpty()) { @@ -122,9 +123,14 @@ fun main(args: Array) { val allocationPolicies = mapOf( "mem" to AvailableMemoryAllocationPolicy(), + "mem-inv" to AvailableMemoryAllocationPolicy(true), "core-mem" to AvailableCoreMemoryAllocationPolicy(), + "core-mem-inv" to AvailableCoreMemoryAllocationPolicy(true), "active-servers" to NumberOfActiveServersAllocationPolicy(), - "provisioned-cores" to ProvisionedCoresAllocationPolicy() + "active-servers-inv" to NumberOfActiveServersAllocationPolicy(true), + "provisioned-cores" to ProvisionedCoresAllocationPolicy(), + "provisioned-cores-inv" to ProvisionedCoresAllocationPolicy(true), + "random" to RandomAllocationPolicy() ) if (allocationPolicy !in allocationPolicies) { @@ -191,7 +197,6 @@ fun main(args: Array) { event.numberOfDeployedImages, event.hostServer ) - else -> println(event) } } .launchIn(this) -- cgit v1.2.3