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
  13 /**
  14  * A ProgressTracker subclass which uses {@code ticksWorkedPerClosedTask} to compute delays.
  15  *
  16  * <p>This class has {@code tasksOpenLimit} used as a (weak) limit,
  17  * as number of open tasks approaches that value, delays computed are increasing.
  18  *
  19  * <p>In order to keep {@code estimateIsolatedDelay} values from raising unreasonably high,
  20  * {@code defaultTicksPerTask} acts as a maximal value. {@code openTask} may return
  21  * higher value if there are tasks above the limit.
  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  * <p>
  27  * This class is NOT thread-safe.
  28  *
  29  * @author Vratko Polak
  30  */
  31 final class AveragingProgressTracker extends ProgressTracker {
  32     private static final long DEFAULT_TICKS_PER_TASK = TimeUnit.MILLISECONDS.toNanos(500);
  33
  34     /**
  35      * The implementation will avoid having more that this number of tasks open.
  36      */
  37     private final long tasksOpenLimit;
  38
  39     /**
  40      * We do not delay tasks until their count hits this threshold.
  41      */
  42     private final long noDelayThreshold;
  43
  44     /**
  45      * Create an idle tracker with limit and specified ticks per task value to use as default.
  46      *
  47      * @param limit of open tasks to avoid exceeding
  48      * @param ticksPerTask value to use as default
  49      */
  50     private AveragingProgressTracker(final long limit, final long ticksPerTask) {
  51         super(ticksPerTask);
  52         tasksOpenLimit = limit;
  53         noDelayThreshold = limit / 2;
  54     }
  55
  56     /**
  57      * Create a default idle tracker with given limit.
  58      *
  59      * @param limit of open tasks to avoid exceeding
  60      */
  61     AveragingProgressTracker(final long limit) {
  62         this(limit, DEFAULT_TICKS_PER_TASK);
  63     }
  64
  65     /**
  66      * Construct a new tracker suitable for a new task queue related to a "reconnect".
  67      *
  68      * <p>The limit is set independently of the old tracker.
  69      *
  70      * @param oldTracker the tracker used for the previously used backend
  71      * @param limit of open tasks to avoid exceeding
  72      * @param now tick number corresponding to caller's present
  73      */
  74     AveragingProgressTracker(final ProgressTracker oldTracker, final long limit, final long now) {
  75         super(oldTracker, now);
  76         tasksOpenLimit = limit;
  77         noDelayThreshold = limit / 2;
  78     }
  79
  80     /**
  81      * Construct a new tracker suitable for a new task queue related to a "reconnect".
  82      *
  83      * <p>The limit is copied from the old tracker.
  84      *
  85      * @param oldTracker the tracker used for the previously used backend
  86      * @param now tick number corresponding to caller's present
  87      */
  88     AveragingProgressTracker(final AveragingProgressTracker oldTracker, final long now) {
  89         this(oldTracker, oldTracker.tasksOpenLimit, now);
  90     }
  91
  92     // Protected read-only methods
  93
  94     /**
  95      * Give an estimate of a fair delay, assuming delays caused by other opened tasks are ignored.
  96      *
  97      * <p>This implementation returns zero delay if number of open tasks is half of limit or less.
  98      * Else the delay is computed, aiming to keep number of open tasks at 3/4 of limit,
  99      * assuming backend throughput remains constant.
 100      *
 101      * <p>As the number of open tasks approaches the limit,
 102      * the computed delay increases, but it never exceeds defaultTicksPerTask.
 103      * That means the actual number of open tasks can exceed the limit.
 104      *
 105      * @param now tick number corresponding to caller's present
 106      * @return delay (in ticks) after which another openTask() would be fair to be called by the same thread again
 107      */
 108     @Override
 109     protected long estimateIsolatedDelay(final long now) {
 110         final long open = tasksOpen();
 111         if (open <= noDelayThreshold) {
 112             return 0L;
 113         }
 114         if (open >= tasksOpenLimit) {
 115             return defaultTicksPerTask();
 116         }
 117
 118         /*
 119          * Calculate the task capacity relative to the limit on open tasks. In real terms this value can be
 120          * in the open interval (0.0, 0.5).
 121          */
 122         final double relativeRemainingCapacity = 1.0 - (double) open / tasksOpenLimit;
 123
 124         /*
 125          * Calculate delay coefficient. It increases in inverse proportion to relative remaining capacity, approaching
 126          * infinity as remaining capacity approaches 0.0.
 127          */
 128         final double delayCoefficient = (0.5 - relativeRemainingCapacity) / relativeRemainingCapacity;
 129         final long delay = (long) (ticksWorkedPerClosedTask(now) * delayCoefficient);
 130
 131         /*
 132          * Cap the result to defaultTicksPerTask, since the calculated delay may overstep it.
 133          */
 134         return Math.min(delay, defaultTicksPerTask());
 135     }
 136 }