Merge branch 'feat/2.x-failures' into '2.x'

Implement basic hardware-level failures

See merge request opendc/opendc-simulator!35

6 files changed, 269 insertions, 15 deletions

diff --git a/opendc/opendc-core/src/main/kotlin/com/atlarge/opendc/core/failure/CorrelatedFaultInjector.kt b/opendc/opendc-core/src/main/kotlin/com/atlarge/opendc/core/failure/CorrelatedFaultInjector.kt
new file mode 100644
index 00000000..da4dee12
--- /dev/null
+++ b/opendc/opendc-core/src/main/kotlin/com/atlarge/opendc/core/failure/CorrelatedFaultInjector.kt
@@ -0,0 +1,110 @@
+/*
+ * 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.core.failure
+
+import com.atlarge.odcsim.Domain
+import com.atlarge.odcsim.simulationContext
+import kotlinx.coroutines.Job
+import kotlinx.coroutines.delay
+import kotlinx.coroutines.ensureActive
+import kotlinx.coroutines.launch
+import kotlin.math.exp
+import kotlin.random.Random
+import kotlin.random.asJavaRandom
+
+/**
+ * A [FaultInjector] that injects fault in the system which are correlated to each other. Failures do not occur in
+ * isolation, but will trigger other faults.
+ */
+public class CorrelatedFaultInjector(
+    private val domain: Domain,
+    private val iatScale: Double,
+    private val iatShape: Double,
+    private val sizeScale: Double,
+    private val sizeShape: Double,
+    random: Random = Random
+) : FaultInjector {
+    /**
+     * The active failure domains that have been registered.
+     */
+    private val active = mutableSetOf<FailureDomain>()
+
+    /**
+     * The [Job] that awaits the nearest fault in the system.
+     */
+    private var job: Job? = null
+
+    /**
+     * The [Random] instance to use.
+     */
+    private val random: java.util.Random = random.asJavaRandom()
+
+    /**
+     * Enqueue the specified [FailureDomain] to fail some time in the future.
+     */
+    override fun enqueue(domain: FailureDomain) {
+        active += domain
+
+        // Clean up the domain if it finishes
+        domain.scope.coroutineContext[Job]!!.invokeOnCompletion {
+            this@CorrelatedFaultInjector.domain.launch {
+                active -= domain
+
+                if (active.isEmpty()) {
+                    job?.cancel()
+                    job = null
+                }
+            }
+        }
+
+        if (job != null) {
+            return
+        }
+
+        job = this.domain.launch {
+            while (true) {
+                ensureActive()
+
+                // Make sure to convert delay from hours to milliseconds
+                val d = lognvariate(iatScale, iatShape) * 3600 * 1e6
+
+                // Handle long overflow
+                if (simulationContext.clock.millis() + d <= 0) {
+                    return@launch
+                }
+
+                delay(d.toLong())
+
+                val n = lognvariate(sizeScale, sizeShape).toInt()
+                for (failureDomain in active.shuffled(random).take(n)) {
+                    failureDomain.fail()
+                }
+            }
+        }
+    }
+
+    // XXX We should extract this in some common package later on.
+    private fun lognvariate(scale: Double, shape: Double) = exp(scale + shape * random.nextGaussian())
+}
diff --git a/opendc/opendc-core/src/main/kotlin/com/atlarge/opendc/core/failure/FailureDomain.kt b/opendc/opendc-core/src/main/kotlin/com/atlarge/opendc/core/failure/FailureDomain.kt
new file mode 100644
index 00000000..91ca9b83
--- /dev/null
+++ b/opendc/opendc-core/src/main/kotlin/com/atlarge/opendc/core/failure/FailureDomain.kt
@@ -0,0 +1,42 @@
+/*
+ * 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.core.failure
+
+import kotlinx.coroutines.CoroutineScope
+
+/**
+ * A logical or physical component in a computing environment which may fail.
+ */
+public interface FailureDomain {
+    /**
+     * The lifecycle of the failure domain to which a [FaultInjector] will attach.
+     */
+    public val scope: CoroutineScope
+
+    /**
+     * Fail the domain externally.
+     */
+    public suspend fun fail()
+}
diff --git a/opendc/opendc-core/src/main/kotlin/com/atlarge/opendc/core/failure/FaultInjector.kt b/opendc/opendc-core/src/main/kotlin/com/atlarge/opendc/core/failure/FaultInjector.kt
new file mode 100644
index 00000000..ac7a08de
--- /dev/null
+++ b/opendc/opendc-core/src/main/kotlin/com/atlarge/opendc/core/failure/FaultInjector.kt
@@ -0,0 +1,35 @@
+/*
+ * 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.core.failure
+
+/**
+ * An interface for stochastically injecting faults into a running system.
+ */
+public interface FaultInjector {
+    /**
+     * Enqueue the specified [FailureDomain] into the queue as candidate for failure injection in the future.
+     */
+    public fun enqueue(domain: FailureDomain)
+}
diff --git a/opendc/opendc-core/src/main/kotlin/com/atlarge/opendc/core/failure/UncorrelatedFaultInjector.kt b/opendc/opendc-core/src/main/kotlin/com/atlarge/opendc/core/failure/UncorrelatedFaultInjector.kt
new file mode 100644
index 00000000..3883eb11
--- /dev/null
+++ b/opendc/opendc-core/src/main/kotlin/com/atlarge/opendc/core/failure/UncorrelatedFaultInjector.kt
@@ -0,0 +1,58 @@
+/*
+ * 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.core.failure
+
+import com.atlarge.odcsim.simulationContext
+import kotlinx.coroutines.delay
+import kotlinx.coroutines.launch
+import kotlin.math.ln1p
+import kotlin.math.pow
+import kotlin.random.Random
+
+/**
+ * A [FaultInjector] that injects uncorrelated faults into the system, meaning that failures of the subsystems are
+ * independent.
+ */
+public class UncorrelatedFaultInjector(private val alpha: Double, private val beta: Double, private val random: Random = Random) : FaultInjector {
+    /**
+     * Enqueue the specified [FailureDomain] to fail some time in the future.
+     */
+    override fun enqueue(domain: FailureDomain) {
+        domain.scope.launch {
+            val d = random.weibull(alpha, beta) * 1e3 // Make sure to convert delay to milliseconds
+
+            // Handle long overflow
+            if (simulationContext.clock.millis() + d <= 0) {
+                return@launch
+            }
+
+            delay(d.toLong())
+            domain.fail()
+        }
+    }
+
+    // XXX We should extract this in some common package later on.
+    private fun Random.weibull(alpha: Double, beta: Double) = (beta * (-ln1p(-nextDouble())).pow(1.0 / alpha))
+}
diff --git a/opendc/opendc-core/src/main/kotlin/com/atlarge/opendc/core/services/ServiceRegistry.kt b/opendc/opendc-core/src/main/kotlin/com/atlarge/opendc/core/services/ServiceRegistry.kt
index d9a85231..75aa778f 100644
--- a/opendc/opendc-core/src/main/kotlin/com/atlarge/opendc/core/services/ServiceRegistry.kt
+++ b/opendc/opendc-core/src/main/kotlin/com/atlarge/opendc/core/services/ServiceRegistry.kt
@@ -25,10 +25,15 @@
 package com.atlarge.opendc.core.services
 
 /**
- * A service registry for a datacenter zone.
+ * An immutable service registry interface.
  */
 public interface ServiceRegistry {
     /**
+     * The keys in this registry.
+     */
+    public val keys: Collection<ServiceKey<*>>
+
+    /**
      * Determine if this map contains the service with the specified [ServiceKey].
      *
      * @param key The key of the service to check for.
@@ -41,12 +46,18 @@ public interface ServiceRegistry {
      *
      * @param key The key of the service to obtain.
      * @return The references to the service.
-     * @throws IllegalArgumentException if the key does not exists in the map.
+     * @throws IllegalArgumentException if the key does not exist in the map.
      */
     public operator fun <T : Any> get(key: ServiceKey<T>): T
 
     /**
-     * Register the specified [ServiceKey] in this registry.
+     * Return the result of associating the specified [service] with the given [key] in this registry.
      */
-    public operator fun <T : Any> set(key: ServiceKey<T>, service: T)
+    public fun <T : Any> put(key: ServiceKey<T>, service: T): ServiceRegistry
 }
+
+/**
+ * Construct an empty [ServiceRegistry].
+ */
+@Suppress("FunctionName")
+public fun ServiceRegistry(): ServiceRegistry = ServiceRegistryImpl(emptyMap())
diff --git a/opendc/opendc-core/src/main/kotlin/com/atlarge/opendc/core/services/ServiceRegistryImpl.kt b/opendc/opendc-core/src/main/kotlin/com/atlarge/opendc/core/services/ServiceRegistryImpl.kt
index 91147839..0686ebaf 100644
--- a/opendc/opendc-core/src/main/kotlin/com/atlarge/opendc/core/services/ServiceRegistryImpl.kt
+++ b/opendc/opendc-core/src/main/kotlin/com/atlarge/opendc/core/services/ServiceRegistryImpl.kt
@@ -27,20 +27,18 @@ package com.atlarge.opendc.core.services
 /**
  * Default implementation of the [ServiceRegistry] interface.
  */
-public class ServiceRegistryImpl : ServiceRegistry {
-    /**
-     * The map containing the registered services.
-     */
-    private val services: MutableMap<ServiceKey<*>, Any> = mutableMapOf()
+internal class ServiceRegistryImpl(private val map: Map<ServiceKey<*>, Any>) : ServiceRegistry {
+    override val keys: Collection<ServiceKey<*>>
+        get() = map.keys
 
-    override fun <T : Any> set(key: ServiceKey<T>, service: T) {
-        services[key] = service
-    }
-
-    override fun contains(key: ServiceKey<*>): Boolean = key in services
+    override fun contains(key: ServiceKey<*>): Boolean = key in map
 
     override fun <T : Any> get(key: ServiceKey<T>): T {
         @Suppress("UNCHECKED_CAST")
-        return services[key] as T
+        return map[key] as T
     }
+
+    override fun <T : Any> put(key: ServiceKey<T>, service: T): ServiceRegistry = ServiceRegistryImpl(map.plus(key to service))
+
+    override fun toString(): String = map.toString()
 }