【算法】6、指数退避算法

今天简单跟大家聊下指数退避算法（Exponential Backoff ），关于指数避退算法的话题开始前首先向大家抛出几个问题：指数退避算法是什么呢？为什么要用指数退避算法呢？指数退避算法的应用场景有哪些呢？代码如何实现呢？带着这些疑问诸君且向下看。

指数退避算法到底是什么呢？wiki上有这么一段解释："Exponential backoff is an algorithm that uses feedback to multiplicatively decrease the rate of some process, in order to gradually find an acceptable rate"。通俗点说，退避算法就是网络上的节点在发送数据冲突后，等待一定时间后再发，等待时间是随指数增长，从而避免频繁的触发冲突。在计算机网络中，二进制指数退避算法或截断指数退避算法常常作为避免网络堵塞的一部分用于同一数据块的重发策略。发生n次冲突后，等待时间在0~2^n-1个间隙时间（slot times）之间选择随机选择。比如，发生第一次冲突后，每个发送方将会等待0或1个间隙时间（slot times）；第二次冲突后，每个发送方的等待时间将会在0到3个间隙时间（slot times）之间任意选择；第三次冲突后，每个发送方的等待时间将会在0到7个间隙时间（slot times）之间任意选择，以此类推，随着冲突次数的增加，发送方的等待时间将会有成倍增加的可能性。而从“截断（ truncated）”的字面意思我们不妨可以猜出，到一定次数，指数运算会停止，也就是说等待时间不会再无限的增加下去。比如，设置上限n=10，则最长等待时间为1023个间隙时间。因为在等待时间内某些场景同样有冲突发生的可能性，所以一般流程会在16次重试后终止。具体的退避算法如下：

确定基本退避时间，它就是争用期（总线上的单程端到端传播时延记为 x，以太网的端到端往返时间2x）。以太网把争用期定为51.2us。对于10Mb/s以太网，在争用期内可发送512bit，即64字节。也可以说争用期是512比特时间。1比特时间就是发送1比特所需要的时间。所以这种时间单位与数据率密切相关。
从离散的整数集合[0,1,…,]中随机取出一个数，记为r。重传应推后的时间就是r倍的争用期。上面的参数k按下面的公式计算： k=Min[重传次数，10] 可见当重传次数不超过10时，参数k等于重传次数;但当重传次数超过10时，k就不在增大而一直等于10。
当重传达16次仍不能成功时(这表明同时打算发送的数据站太多，以致连续发生冲突)，则丢弃该，并向高层报告。例如，在第1次重传时，k=1，随机数r从整数{0,1}中选一个数。因此重传推迟的时间是0或争用期，在这两个时间中随机选择一个。若再发生碰撞，则重传时，k=2，随机数r就从整数{0,1,2,3}中选一个数。因此重传推迟的时间是在0,2x ,4x和6x 这4个时间中随机抽取一个。同样，若在发生碰撞，则重传时k=3，随机数r就从整数{0,1,2,3,4,5,6,7}中选一个数。以此类推。若连续多次发生冲突，就表明可能有较多的站参与争用信道。但使用退避算法可使重传需要推迟的平均时间随重传次数而增大（这也称为动态退避），因而减小发生碰撞的概率，有利于整个系统的稳定。

相信读到这里，大家对第二个问题的答案也呼之欲出了吧，大多数指数退避算法会利用抖动（随机延迟）来防止连续的冲突。但是，如果使用并发客户端，抖动可帮助您更快地成功执行请求。

至于指数避退算法的场景有哪些呢？指数退避算法在计算机网络中应用很广泛，这里简单说两个场景，第一个场景，接入三方支付服务，在三方支付提供的接入接口规范中，服务方交易结束结果通知和商户主动查询交易结果都用到重发机制，这就是所谓的退避算法，这地方其实也引出了另一个知识点——接口的幂等性（使用相同参数对同一资源重复调用某个接口的结果与调用一次的结果相同），这里不再过多赘述。第二个场景，在app应用中，很多场景会遇到轮询一类的问题，一般的轮询对于app性能和电量的消耗都是个巨大的灾难。那如何解决这种问题呢？app在上一次更新操作之后还未被使用的情况下，使用指数退避算法来减少更新频率，从而节省资源和减少电的消耗。

最后一个问题，这里简单的用伪代码和java代码的方式给大家演示一下增量延迟轮询的实现方法。

伪代码

Do some asynchronous operation.·
retries = 0
DO
    wait for (2^retries * 100) milliseconds
    status = Get the result of the asynchronous operation.
    IF status = SUCCESS
        retry = false
    ELSE IF status = NOT_READY
        retry = true
    ELSE IF status = THROTTLED
        retry = true
    ELSE
        Some other error occurred, so stop calling the API.
        retry = false
    END IF
    retries = retries + 1
WHILE (retry AND (retries < MAX_RETRIES))

java代码

public enum Results {
    SUCCESS, 
    NOT_READY, 
    THROTTLED, 
    SERVER_ERROR
}

/*
 * Performs an asynchronous operation, then polls for the result of the
 * operation using an incremental delay.
 */
public static void doOperationAndWaitForResult() {
    try {
        // Do some asynchronous operation.
        long token = asyncOperation();
        int retries = 0;
        boolean retry = false;
        do {
            long waitTime = Math.min(getWaitTimeExp(retries), MAX_WAIT_INTERVAL);
            System.out.print(waitTime + "
");
            // Wait for the result.
            Thread.sleep(waitTime);
            // Get the result of the asynchronous operation.
            Results result = getAsyncOperationResult(token);
            if (Results.SUCCESS == result) {
                retry = false;
            } else if (Results.NOT_READY == result) {
                retry = true;
            } else if (Results.THROTTLED == result) {
                retry = true;
            } else if (Results.SERVER_ERROR == result) {
                retry = true;
            }
            else {
                // Some other error occurred, so stop calling the API.
                retry = false;
            }
        } while (retry && (retries++ < MAX_RETRIES));
    }
    catch (Exception ex) {
    }
}

/*
 * Returns the next wait interval, in milliseconds, using an exponential
 * backoff algorithm.
 */
public static long getWaitTimeExp(int retryCount) {
    long waitTime = ((long) Math.pow(2, retryCount) * 100L);
    return waitTime;
}

ok，就谈到这啦，源于自己认知的局限性，也许谈的一些地方会有错误之处，欢迎大牛指正。