opendaylight/md-sal/cds-access-client/src/main/java/org/opendaylight/controller/cluster/access/client/AveragingProgressTracker.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 java.util.concurrent.TimeUnit;
  12 import javax.annotation.concurrent.NotThreadSafe;
  13
  14 /**
  15  * A ProgressTracker subclass which uses {@code ticksWorkedPerClosedTask} to compute delays.
  16  *
  17  * <p>This class has {@code tasksOpenLimit} used as a (weak) limit,
  18  * as number of open tasks approaches that value, delays computed are increasing.
  19  *
  20  * <p>In order to keep delays from raising to unreasonably high values,
  21  * a maximal delay (per task) value is never exceeded.
  22  *
  23  * <p>On the other hand, there is no delay when number of open tasks is half the limit or less,
  24  * in order to prevent backend from running out of tasks while there may be waiting frontend threads.
  25  *
  26  * @author Vratko Polak
  27  */
  28 @NotThreadSafe
  29 final class AveragingProgressTracker extends ProgressTracker {
  30     private static final long DEFAULT_TICKS_PER_TASK = TimeUnit.MILLISECONDS.toNanos(500);
  31
  32     /**
  33      * The implementation will avoid having more that this number of tasks open.
  34      */
  35     private final long tasksOpenLimit;
  36
  37     /**
  38      * We do not delay tasks until their count hits this threshold.
  39      */
  40     private final long noDelayThreshold;
  41
  42     /**
  43      * Create an idle tracker with limit and specified ticks per task value to use as default.
  44      *
  45      * @param limit of open tasks to avoid exceeding
  46      * @param ticksPerTask value to use as default
  47      */
  48     private AveragingProgressTracker(final int limit, final long ticksPerTask) {
  49         super(ticksPerTask);
  50         tasksOpenLimit = limit;
  51         noDelayThreshold = limit / 2;
  52     }
  53
  54     /**
  55      * Create a default idle tracker with given limit.
  56      *
  57      * @param limit of open tasks to avoid exceeding
  58      */
  59     AveragingProgressTracker(final int limit) {
  60         this(limit, DEFAULT_TICKS_PER_TASK);
  61     }
  62
  63     /**
  64      * Create a copy of an existing tracker, all future tracking is fully independent.
  65      *
  66      * @param tracker the instance to copy state from
  67      */
  68     AveragingProgressTracker(final AveragingProgressTracker tracker) {
  69         super(tracker);
  70         this.tasksOpenLimit = tracker.tasksOpenLimit;
  71         this.noDelayThreshold = tracker.noDelayThreshold;
  72     }
  73
  74     // Public shared access (read-only) accessor-like methods
  75
  76     /**
  77      * Give an estimate of a fair delay, assuming delays caused by other opened tasks are ignored.
  78      *
  79      * <p>This implementation returns zero delay if number of open tasks is half of limit or less.
  80      * Else the delay is computed, aiming to keep number of open tasks at 3/4 of limit,
  81      * assuming backend throughput remains constant.
  82      *
  83      * <p>As the number of open tasks approaches the limit,
  84      * the computed delay increases, but it never exceeds defaultTicksPerTask.
  85      * That means the actual number of open tasks can exceed the limit.
  86      *
  87      * @param now tick number corresponding to caller's present
  88      * @return delay (in ticks) after which another openTask() would be fair to be called by the same thread again
  89      */
  90     @Override
  91     public long estimateIsolatedDelay(final long now) {
  92         final long open = tasksOpen();
  93         if (open <= noDelayThreshold) {
  94             return 0L;
  95         }
  96         if (open >= tasksOpenLimit) {
  97             return defaultTicksPerTask();
  98         }
  99
 100         /*
 101          * Calculate the task capacity relative to the limit on open tasks. In real terms this value can be
 102          * in the open interval (0.0, 0.5).
 103          */
 104         final double relativeRemainingCapacity = 1.0 - (((double) open) / tasksOpenLimit);
 105
 106         /*
 107          * Calculate delay coefficient. It increases in inverse proportion to relative remaining capacity, approaching
 108          * infinity as remaining capacity approaches 0.0.
 109          */
 110         final double delayCoefficient = (0.5 - relativeRemainingCapacity) / relativeRemainingCapacity;
 111         final long delay = (long) (ticksWorkedPerClosedTask(now) * delayCoefficient);
 112
 113         /*
 114          * Cap the result to defaultTicksPerTask, since the calculated delay may overstep it.
 115          */
 116         return Math.min(delay, defaultTicksPerTask());
 117     }
 118 }