今天簡(jiǎn)單跟大家聊下指數(shù)退避算法（Exponential Backoff ），關(guān)于指數(shù)避退算法的話題開(kāi)始前首先向大家拋出幾個(gè)問(wèn)題：指數(shù)退避算法是什么呢路媚？為什么要用指數(shù)退避算法呢？指數(shù)退避算法的應(yīng)用場(chǎng)景有哪些呢缠黍？代碼如何實(shí)現(xiàn)呢集嵌？帶著這些疑問(wèn)諸君且向下看讥电。
指數(shù)退避算法到底是什么呢女仰？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"猜年。通俗點(diǎn)說(shuō)， 退避算法就是網(wǎng)絡(luò)上的節(jié)點(diǎn)在發(fā)送數(shù)據(jù)沖突后疾忍，等待一定時(shí)間后再發(fā)乔外，等待時(shí)間是隨指數(shù)增長(zhǎng)，從而避免頻繁的觸發(fā)沖突一罩。在計(jì)算機(jī)網(wǎng)絡(luò)中杨幼，二進(jìn)制指數(shù)退避算法或截?cái)嘀笖?shù)退避算法常常作為避免網(wǎng)絡(luò)堵塞的一部分用于同一數(shù)據(jù)塊的重發(fā)策略。發(fā)生n次沖突后聂渊，等待時(shí)間在0~2^n-1個(gè)間隙時(shí)間（slot times） 之間選擇隨機(jī)選擇差购。比如，發(fā)生第一次沖突后汉嗽，每個(gè)發(fā)送方將會(huì)等待0或1個(gè)間隙時(shí)間（slot times）歹撒；第二次沖突后，每個(gè)發(fā)送方的等待時(shí)間將會(huì)在0到3個(gè)間隙時(shí)間（slot times） 之間任意選擇诊胞；第三次沖突后，每個(gè)發(fā)送方的等待時(shí)間將會(huì)在0到7個(gè)間隙時(shí)間（slot times） 之間任意選擇锹杈，以此類推撵孤，隨著沖突次數(shù)的增加，發(fā)送方的等待時(shí)間將會(huì)有成倍增加的可能性竭望。而從“截?cái)啵?truncated）”的字面意思我們不妨可以猜出邪码，到一定次數(shù)，指數(shù)運(yùn)算會(huì)停止咬清，也就是說(shuō)等待時(shí)間不會(huì)再無(wú)限的增加下去闭专。比如奴潘，設(shè)置上限n=10，則最長(zhǎng)等待時(shí)間為1023個(gè)間隙時(shí)間影钉。因?yàn)樵诘却龝r(shí)間內(nèi)某些場(chǎng)景同樣有沖突發(fā)生的可能性画髓，所以一般流程會(huì)在16次重試后終止。具體的退避算法如下：
確定基本退避時(shí)間平委，它就是爭(zhēng)用期（總線上的單程端到端傳播時(shí)延記為 x奈虾，以太網(wǎng)的端到端往返時(shí)間2x）。以太網(wǎng)把爭(zhēng)用期定為51.2us廉赔。對(duì)于10Mb/s以太網(wǎng)肉微，在爭(zhēng)用期內(nèi)可發(fā)送512bit，即64字節(jié)蜡塌。也可以說(shuō)爭(zhēng)用期是512比特時(shí)間碉纳。1比特時(shí)間就是發(fā)送1比特所需要的時(shí)間。所以這種時(shí)間單位與數(shù)據(jù)率密切相關(guān)馏艾。
從離散的整數(shù)集合[0,1,…,]中隨機(jī)取出一個(gè)數(shù)劳曹，記為r。重傳應(yīng)推后的時(shí)間就是r倍的爭(zhēng)用期攒至。上面的參數(shù)k按下面的公式計(jì)算： k=Min[重傳次數(shù)厚者，10] 可見(jiàn)當(dāng)重傳次數(shù)不超過(guò)10時(shí)，參數(shù)k等于重傳次數(shù);但當(dāng)重傳次數(shù)超過(guò)10時(shí)迫吐，k就不在增大而一直等于10库菲。
當(dāng)重傳達(dá)16次仍不能成功時(shí)(這表明同時(shí)打算發(fā)送的數(shù)據(jù)站太多，以致連續(xù)發(fā)生沖突)志膀，則丟棄該熙宇，并向高層報(bào)告。例如溉浙，在第1次重傳時(shí)烫止，k=1，隨機(jī)數(shù)r從整數(shù){0,1}中選一個(gè)數(shù)戳稽。因此重傳推遲的時(shí)間是0或爭(zhēng)用期馆蠕，在這兩個(gè)時(shí)間中隨機(jī)選擇一個(gè)。若再發(fā)生碰撞惊奇，則重傳時(shí)互躬，k=2，隨機(jī)數(shù)r就從整數(shù){0,1,2,3}中選一個(gè)數(shù)颂郎。因此重傳推遲的時(shí)間是在0,2x ,4x和6x 這4個(gè)時(shí)間中隨機(jī)抽取一個(gè)吼渡。同樣，若在發(fā)生碰撞乓序，則重傳時(shí)k=3寺酪，隨機(jī)數(shù)r就從整數(shù){0,1,2,3,4,5,6,7}中選一個(gè)數(shù)坎背。以此類推。若連續(xù)多次發(fā)生沖突寄雀，就表明可能有較多的站參與爭(zhēng)用信道得滤。但使用退避算法可使重傳需要推遲的平均時(shí)間隨重傳次數(shù)而增大（這也稱為動(dòng)態(tài)退避），因而減小發(fā)生碰撞的概率咙俩，有利于整個(gè)系統(tǒng)的穩(wěn)定耿戚。
相信讀到這里，大家對(duì)第二個(gè)問(wèn)題的答案也呼之欲出了吧阿趁， 大多數(shù)指數(shù)退避算法會(huì)利用抖動(dòng)（隨機(jī)延遲）來(lái)防止連續(xù)的沖突膜蛔。 但是，如果使用并發(fā)客戶端脖阵，抖動(dòng)可幫助您更快地成功執(zhí)行請(qǐng)求皂股。
至于指數(shù)避退算法的場(chǎng)景有哪些呢？指數(shù)退避算法在計(jì)算機(jī)網(wǎng)絡(luò)中應(yīng)用很廣泛命黔，這里簡(jiǎn)單說(shuō)兩個(gè)場(chǎng)景呜呐，第一個(gè)場(chǎng)景，接入三方支付服務(wù)悍募，在三方支付提供的接入接口規(guī)范中蘑辑，服務(wù)方交易結(jié)束結(jié)果通知和商戶主動(dòng)查詢交易結(jié)果都用到重發(fā)機(jī)制，這就是所謂的退避算法坠宴，這地方其實(shí)也引出了另一個(gè)知識(shí)點(diǎn)——接口的冪等性（ 使用相同參數(shù)對(duì)同一資源重復(fù)調(diào)用某個(gè)接口的結(jié)果與調(diào)用一次的結(jié)果相同）洋魂，這里不再過(guò)多贅述。第二個(gè)場(chǎng)景喜鼓，在app應(yīng)用中副砍，很多場(chǎng)景會(huì)遇到輪詢一類的問(wèn)題，一般的輪詢對(duì)于app性能和電量的消耗都是個(gè)巨大的災(zāi)難庄岖。那如何解決這種問(wèn)題呢豁翎？app在上一次更新操作之后還未被使用的情況下，使用指數(shù)退避算法來(lái)減少更新頻率隅忿，從而節(jié)省資源和減少電的消耗心剥。
最后一個(gè)問(wèn)題，這里簡(jiǎn)單的用偽代碼和java代碼的方式給大家演示一下增量延遲輪詢的實(shí)現(xiàn)方法背桐。
偽代碼
Dosome asynchronous operation.
retries=0
DO
waitfor(2^retries*100)milliseconds
status=Getthe result of the asynchronous operation.
IF status=SUCCESS
retry=false
ELSE IF status=NOT_READY
retry=true
ELSE IF status=THROTTLED
retry=true
ELSE
Someother error occurred,so stop calling the API.
retry=false
ENDIF
retries=retries+1
WHILE(retry AND (retries<MAX_RETRIES))
java代碼
public enum Results {
SUCCESS,
NOT_READY,
THROTTLED,
SERVER_ERROR
}
public static void doOperationAndWaitForResult() {
try {
long token = asyncOperation();
int retries = 0;
boolean retry = false;
do {
long waitTime = Math.min(getWaitTimeExp(retries), MAX_WAIT_INTERVAL);
System.out.print(waitTime + "\n");
Thread.sleep(waitTime);
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 {
retry = false;
}
} while (retry && (retries++ < MAX_RETRIES));
}
catch (Exception ex) {
}
}
public static long getWaitTimeExp(int retryCount) {
long waitTime = ((long) Math.pow(2, retryCount) * 100L);
return waitTime;
}
ok刘陶，就談到這啦，源于自己認(rèn)知的局限性牢撼，也許談的一些地方會(huì)有錯(cuò)誤之處，歡迎大牛指正疑苫。
拓展閱讀：
https://en.wikipedia.org/wiki/Exponential_backoff
https://www.awsarchitectureblog.com/2015/03/backoff.html
打開(kāi)手機(jī)看微信熏版，加微信公眾平臺(tái)“Martin說(shuō)”纷责，每天收獲更多Martin的閑扯。
