opendaylight/md-sal/cds-access-client/src/main/java/org/opendaylight/controller/cluster/access/client/ProgressTracker.java

   1 /*
   2  * Copyright (c) 2016 Cisco Systems, Inc. and others.  All rights reserved.
   3  *
   4  * This program and the accompanying materials are made available under the
   5  * terms of the Eclipse Public License v1.0 which accompanies this distribution,
   6  * and is available at http://www.eclipse.org/legal/epl-v10.html
   7  */
   8
   9 package org.opendaylight.controller.cluster.access.client;
  10
  11 import com.google.common.base.Preconditions;
  12 import javax.annotation.concurrent.NotThreadSafe;
  13 import org.slf4j.Logger;
  14 import org.slf4j.LoggerFactory;
  15
  16 /**
  17  * Base class for tracking throughput and computing delays when processing stream of tasks.
  18  *
  19  * <p>The idea is to improve throughput in a typical request-response scenario.
  20  * A "frontend" is sending requests towards "backend", backend is sending responses back to fronted.
  21  * Both frontend and backend may be realized by multiple Java threads,
  22  * so there may be multiple requests not yet responded to.
  23  * In terms of taks processing, frontend is "opening" tasks and backend is "closing" them.
  24  * Latency of the backend may fluctuate wildly. To avoid backend running out of open tasks,
  25  * there should be a queue of requests frontend can add to.
  26  * In order to avoid excessive memore consumption, there should be a back-pressure mechanism
  27  * which blocks the frontend threads for appropriate durations.
  28  * Frontend can tolerate moderately delayed responses, but it only tolerates small block times.
  29  *
  30  * <p>An ideal back-pressure algorithm would keep the queue reasonably full,
  31  * while fairly delaying frontend threads. In other words, backend idle time should be low,
  32  * as well as frontend block time dispersion
  33  * (as opposed to block time average, which is dictated by overall performance).
  34  *
  35  * <p>In order for an algorithm to compute reasonable wait times,
  36  * various inputs can be useful, mostly related to timing of various stages of task processing.
  37  * Methods of this class assume "enqueue and wait" usage.
  38  * The delay computation is pessimistic, it expects each participating thread to enqueue another task
  39  * as soon as its delay time allows.
  40  *
  41  * <p>This class is not thread safe, the callers are responsible for guarding against conflicting access.
  42  * Time is measured in ticks (nanos), methods never look at current time, relying on {@code now} argument instead.
  43  * Input data used for tracking is tightly coupled with TransitQueue#recordCompletion arguments.
  44  *
  45  * @author Vratko Polak
  46  */
  47 // TODO: Would bulk methods be less taxing than a loop of single task calls?
  48 @NotThreadSafe
  49 abstract class ProgressTracker {
  50     private static final Logger LOG = LoggerFactory.getLogger(ProgressTracker.class);
  51
  52     /**
  53      * When no tasks has been closed yet, this will be used to estimate throughput.
  54      */
  55     private final long defaultTicksPerTask;
  56
  57     /**
  58      * Number of tasks closed so far.
  59      */
  60     private long tasksClosed = 0;
  61
  62     /**
  63      * Number of tasks so far, both open and closed.
  64      */
  65     private long tasksEncountered = 0;
  66
  67     /**
  68      * The most recent tick number when the number of open tasks has become non-positive.
  69      */
  70     private long lastIdle = Long.MIN_VALUE;
  71
  72     /**
  73      * The most recent tick number when a task has been closed.
  74      */
  75     private long lastClosed = Long.MIN_VALUE;
  76
  77     /**
  78      * Tick number when the farthest known wait time is over.
  79      */
  80     private long nearestAllowed = Long.MIN_VALUE;
  81
  82     /**
  83      * Number of ticks elapsed before lastIdle while there was at least one open task.
  84      */
  85     private long elapsedBeforeIdle = 0L;
  86
  87     // Constructors
  88
  89     /**
  90      * Construct an idle tracker with specified ticks per task value to use as default.
  91      *
  92      * @param ticksPerTask value to use as default
  93      */
  94     ProgressTracker(final long ticksPerTask) {
  95         Preconditions.checkArgument(ticksPerTask >= 0);
  96         defaultTicksPerTask = ticksPerTask;
  97     }
  98
  99     /**
 100      * Construct a copy of an existing tracker, all future tracking is fully independent.
 101      *
 102      * @param tracker the instance to copy state from
 103      */
 104     ProgressTracker(final ProgressTracker tracker) {
 105         this.defaultTicksPerTask = tracker.defaultTicksPerTask;
 106         this.tasksClosed = tracker.tasksClosed;
 107         this.tasksEncountered = tracker.tasksEncountered;
 108         this.lastClosed = tracker.lastClosed;
 109         this.lastIdle = tracker.lastIdle;
 110         this.nearestAllowed = tracker.nearestAllowed;
 111         this.elapsedBeforeIdle = tracker.elapsedBeforeIdle;
 112     }
 113
 114     // Public shared access (read-only) accessor-like methods
 115
 116     /**
 117      * Get the value of default ticks per task this instance was created to use.
 118      *
 119      * @return default ticks per task value
 120      */
 121     public final long defaultTicksPerTask() {
 122         return defaultTicksPerTask;
 123     }
 124
 125     /**
 126      * Get number of tasks closed so far.
 127      *
 128      * @return number of tasks known to be finished already; the value never decreases
 129      */
 130     public final long tasksClosed() {
 131         return tasksClosed;
 132     }
 133
 134     /**
 135      * Get umber of tasks so far, both open and closed.
 136      *
 137      * @return number of tasks encountered so far, open or finished; the value never decreases
 138      */
 139     public final long tasksEncountered() {
 140         return tasksEncountered;
 141     }
 142
 143     /**
 144      * Get number of tasks currently open.
 145      *
 146      * @return number of tasks started but not finished yet
 147      */
 148     public final long tasksOpen() {
 149         // TODO: Should we check the return value is non-negative?
 150         return tasksEncountered - tasksClosed;
 151     }
 152
 153     /**
 154      * When idle, there are no open tasks so no progress is made.
 155      *
 156      * @return {@code true} if every encountered task is already closed, {@code false} otherwise
 157      */
 158     public boolean isIdle() {
 159         return tasksClosed >= tasksEncountered;
 160     }
 161
 162     /**
 163      * Number of ticks elapsed (before now) since the last closed task while there was at least one open task.
 164      *
 165      * @param now tick number corresponding to caller's present
 166      * @return number of ticks backend is neither idle nor responding
 167      */
 168     public long ticksStalling(final long now) {
 169         return isIdle() ? 0 : Math.max(now, lastClosed) - lastClosed;
 170     }
 171
 172     /**
 173      * Number of ticks elapsed (before now) while there was at least one open task.
 174      *
 175      * @param now tick number corresponding to caller's present
 176      * @return number of ticks there was at least one task open
 177      */
 178     public long ticksWorked(final long now) {
 179         return isIdle() ? elapsedBeforeIdle : Math.max(now, lastIdle) - lastIdle + elapsedBeforeIdle;
 180     }
 181
 182     /**
 183      * One task is roughly estimated to take this long to close.
 184      *
 185      * @param now tick number corresponding to caller's present
 186      * @return total ticks worked divided by closed tasks, or the default value if no closed tasks
 187      */
 188     public double ticksWorkedPerClosedTask(final long now) {
 189         if (tasksClosed < 1) {
 190             return defaultTicksPerTask;
 191         }
 192         return (double) ticksWorked(now) / tasksClosed;
 193     }
 194
 195     /**
 196      * Give an estimate of openTask() return value.
 197      *
 198      * <p>When the returned delay is positive, the caller thread should wait that time before opening additional task.
 199      *
 200      * <p>This method in general takes into account previously assigned delays to avoid overlaps.
 201      *
 202      * @param now tick number corresponding to caller's present
 203      * @return delay (in ticks) after which another openTask() is fair to be called by the same thread again
 204      */
 205     public long estimateDelay(final long now) {
 206         return estimateAllowed(now) - now;
 207     }
 208
 209     /**
 210      * Give an estimate of a tick number when there will be no accumulated delays.
 211      *
 212      * <p>The delays accumulated include one more open task.
 213      * Basically, the return value corresponds to openTask() return value,
 214      * but this gives an absolute time, instead of delay relative to now.
 215      *
 216      * @param now tick number corresponding to caller's present
 217      * @return estimated tick number when all threads with opened tasks are done waiting
 218      */
 219     public long estimateAllowed(final long now) {
 220         return Math.max(now, nearestAllowed) + estimateIsolatedDelay(now);
 221     }
 222
 223     // State-altering public methods.
 224
 225     /**
 226      * Track a task is being closed.
 227      *
 228      * @param now tick number corresponding to caller's present
 229      * @param enqueuedTicks see TransitQueue#recordCompletion
 230      * @param transmitTicks see TransitQueue#recordCompletion
 231      * @param execNanos see TransitQueue#recordCompletion
 232      */
 233     public void closeTask(final long now, final long enqueuedTicks, final long transmitTicks, final long execNanos) {
 234         if (isIdle()) {
 235             LOG.info("Attempted to close a task while no tasks are open");
 236         } else {
 237             protectedCloseTask(now, enqueuedTicks, transmitTicks, execNanos);
 238         }
 239     }
 240
 241     /**
 242      * Track a task that is being opened.
 243      *
 244      * @param now tick number corresponding to caller's present
 245      * @return number of ticks (nanos) the caller thread should wait before opening another task
 246      */
 247     public long openTask(final long now) {
 248         protectedOpenTask(now);
 249         return reserveDelay(now);
 250     }
 251
 252     // Internal state-altering methods. Protected instead of private,
 253     // allowing subclasses to weaken ad-hoc invariants of current implementation.
 254
 255     /**
 256      * Compute the next delay and update nearestAllowed value accordingly.
 257      *
 258      * @param now tick number corresponding to caller's present
 259      * @return number of ticks (nanos) the caller thread should wait before opening another task
 260      */
 261     protected long reserveDelay(final long now) {
 262         nearestAllowed = estimateAllowed(now);
 263         return nearestAllowed - now;
 264     }
 265
 266     /**
 267      * Track a task is being closed.
 268      *
 269      * <p>This method does not verify there was any task open.
 270      * This call can empty the collection of open tasks, that special case should be handled.
 271      *
 272      * @param now tick number corresponding to caller's present
 273      * @param enqueuedTicks see TransitQueue#recordCompletion
 274      * @param transmitTicks see TransitQueue#recordCompletion
 275      * @param execNanos see TransitQueue#recordCompletion
 276      */
 277     protected void protectedCloseTask(final long now, final long enqueuedTicks, final long transmitTicks,
 278                 final long execNanos) {
 279         tasksClosed++;
 280         lastClosed = now;
 281         if (isIdle()) {
 282             elapsedBeforeIdle += now - lastIdle;
 283         }
 284     }
 285
 286     /**
 287      * Track a task is being opened.
 288      *
 289      * <p>This method does not aggregate delays, allowing the caller to sidestep the throttling.
 290      * This call can make the collection of open tasks non-empty, that special case should be handled.
 291      *
 292      * @param now tick number corresponding to caller's present
 293      */
 294     protected void protectedOpenTask(final long now) {
 295         if (isIdle()) {
 296             lastIdle = Math.max(now, lastIdle);
 297         }
 298         tasksEncountered++;
 299     }
 300
 301     /**
 302      * Give an estimate of a fair delay, assuming delays caused by other opened tasks are ignored.
 303      *
 304      * @param now tick number corresponding to caller's present
 305      * @return delay (in ticks) after which another openTask() would be fair to be called by the same thread again
 306      */
 307     abstract long estimateIsolatedDelay(final long now);
 308 }