В чем выгода использования экспоненциального отката?

Question

Когда код ожидает некоторого условия, при котором время задержки не является детерминированным, похоже, что многие люди предпочитают использовать экспоненциальный откат, то есть ждать N секунд, проверить, удовлетворяет ли условие; если нет, подождите 2N секунды, проверьте состояние и т. д. В чем преимущество этой проверки по сравнению с постоянным / линейно увеличивающимся интервалом времени?

Answer 1

Экспоненциальный откат полезен в тех случаях, когда одновременные попытки что-то сделать будут мешать друг другу, так что ни одна из них не будет успешной. В таких случаях, если устройства случайным образом предпринимают попытку выполнить операцию в слишком маленьком окне, это приведет к тому, что большинство попыток завершится неудачно, и их придется повторить. Только когда окно станет достаточно большим, попытки будут иметь значительную вероятность успеха.

Если заранее знать, что 16 устройств будут хотеть общаться, можно было бы выбрать размер окна, который будет оптимальным для этого уровня загрузки. Однако на практике количество конкурирующих устройств обычно неизвестно. Преимущество экспоненциального отката, при котором размер окна удваивается при каждой повторной попытке, заключается в том, что независимо от количества конкурирующих объектов:

1. Размер окна, при котором большинство операций завершается успешно, обычно будет в пределах двух крат от наименьшего размера окна, при котором большинство операций будет успешным,

2. Большинство операций, которые терпят неудачу при таком размере окна, будут успешными при следующей попытке (так как большинство более ранних операций будут успешными, из-за этого менее половины из них будут бороться за окно, которое в два раза больше), и

3. Общее время, необходимое для всех попыток, в конечном итоге будет примерно вдвое больше, чем для последней.

Если вместо удвоения каждый раз окно просто увеличивалось на постоянную величину, то время, затрачиваемое на повторение операции до тех пор, пока окно не достигло полезного размера, было бы пропорционально квадрату любого требуемого размера окна. Хотя окончательный размер окна может быть меньше, чем при экспоненциальном откате, общая стоимость всех попыток будет намного выше.

Answer 2

Это поведение управления перегрузкой TCP. Если сеть сильно перегружена, трафик фактически не проходит. Если каждый узел ожидает постоянного времени перед проверкой, трафик только для проверки продолжит засорять сеть, и перегрузка никогда не разрешится. Аналогично, для линейного увеличения времени между проверками может пройти много времени, прежде чем затор разрешится.

Answer 3

Предполагая, что вы имеете в виду тестирование условия перед выполнением действия:

• Экспоненциальный откат выгоден, когда стоимость тестирования условия сопоставима со стоимостью выполнения действия (например, при перегрузке сети).
• если стоимость тестирования условия намного меньше (или незначительна), то линейное или постоянное ожидание может работать лучше, если время, необходимое для изменения условия, также незначительно.

Например, если ваше условие представляет собой сложный (медленный) запрос к базе данных, а действие представляет собой обновление той же базы данных, то каждая проверка условия будет отрицательно влиять на производительность базы данных, и в какой-то момент без экспоненциального отката, Проверка состояния несколькими участниками может быть достаточной для использования всех ресурсов базы данных.

Но если условие представляет собой просто облегченную проверку памяти (например, критический раздел), а действие по-прежнему является обновлением базы данных (в лучшем случае в десятки тысячных раз медленнее, чем проверка), и если условие переворачивается незначительно время в самом начале действия (путем входа в критическую секцию), тогда постоянный или линейный откат будет в порядке. На самом деле в этом конкретном сценарии экспоненциальный откат будет вредным, так как он приведет к задержкам в ситуациях с низкой нагрузкой и с большей вероятностью приведет к тайм-аутам в ситуациях с высокой нагрузкой (даже когда пропускная способность обработки достаточна).

Подводя итог, можно сказать, что экспоненциальный откат - это молот: он отлично работает для гвоздей, а не для винтов:)