AshBlade
@AshBlade
Просто хочу быть счастливым

Как обрабатывать переполнение счетчиков и индексов?

В разных алгоритмах используются различные счетчики. Например, счетчик транзакции в БД, Терм в Raft, счетчик событий в векторных часах и т.д.
Но что случится, когда нижележащая структура данных (int, short, long) переполнится? Например, всю неделю безостановочно слали запросы и какой-то счетчик достиг своего максимального значения.

Вопросы:
- Как подобные ситуации обрабатывать правильно?
- Есть ли примеры этого в реальных приложениях?
  • Вопрос задан
  • 183 просмотра
Решения вопроса 1
wataru
@wataru
Разработчик на С++, экс-олимпиадник.
Обычно берут тип данных с запасом так, чтобы переполнения не было.
Если же переполнение действительно может произойти, то есть несколько подходов:
- игнорировать переполнение. Иногда это подходящий вариант. Например какая-нибудь CRC сумма для проверки целостности.

- определять переполнение и как-то его бросать исключение или завершать программу. Все операции идут с проверками.

- Clamped типы. Максимальное значение типа считается бесконечностью. Прибавление к нему не меняет это значение. Переполнение выдаст это максимальное. Все операции с переменной, естественно, тоже сопровождаются проверками. Тут есть возможность потом какие-то выводы о значении счетчика потом даже делать. Вы будете видеть, что там больше или равно INT_MAX, но насколько больше - знать не будете.

- Wraparound. Часто вам не важно абсолютное значение счетчика. Нужно лишь знать, какое из двух значений больше. При этом вы знаете, что сравниваемые значения не могут быть слишком большими. Тогда очень маленькое значение будет считаться больше очень большого. Два примерно одинаковых будут сравниваться как обычные числа. Так можно делать, например, с sequence number пакетов. Если вы получите пакет с номером 0x02 после покета с номером OxFFF1, Можно с спокойно считать, что это номер после переполнения. Ну не будет сеть задерживать перетасовывать 65 тысяч пакетов.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
mayton2019
@mayton2019
Bigdata Engineer
В классических языках программирования происходит обнуление переменных int, long.
Тоесть ошибки не будет но счетчик пойдет снова с нуля. Чтоб детектировать - надо
делать проверку условия на максимум.

На уровне языка Ассемблер и процессора существует флаг переполнения (OF) который взводится в
состояние true если в результате сложения или инкремента последняя операция детектировала
переполнение. Тоесть обработать это технически возможность существует. И далее - условный переход
на обработку.

В реальных приложениях такого лучше не допускать. Лучше не жадничать и вводить long счетчики.
Их хватит на тысячи лет как-бы вы там интенсивно не делали инкременты. В базах данных типа Oracle
NUMBER тип хранит 38 десятичных знаков числа. Надолго хватает. И я не слыхал чтоб у кого-то в обычном
режиме бизнес-транзакций эти счетчики переполнялись.

У Постгреса была проблема с 32 битными счетчиками XID. Не знаю как они ее порешали. Кажется
как-то они сбрасывают их для всей таблицы. Толи в вакууме толи еще как-то я не помню. Пускай
постгресщики скажут точнее.

Чтобы уйти от мелких счетчиков попробуйте использовать SnowflakeId (64bit) или GUID(128bit). Их надолго
хватает и никто не жаловался. Git использует 160-bit идентификаторы коммитов в графе коммитов
и тоже пока никто не жаловался.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы