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

Question

[Сергей Соловьев]

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

Вопросы:
- Как подобные ситуации обрабатывать правильно?
- Есть ли примеры этого в реальных приложениях?

Answer 1

[Wataru]

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

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

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

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

Comments

[Mercury13]

Не «не могут быть слишком большими», а «не могут быть слишком далеко».

Answer 2

[mayton2019]

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

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

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

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

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

Comments

[Василий Банников]

Тоесть ошибки не будет но счетчик пойдет снова с нуля. Чтоб детектировать - надо
делать проверку условия на максимум.

1. В некоторых языках. Например в C++ переполнение может быть UB
2. В некоторых языках есть способ явно проверить, что нет переполения. Ключевое слово checked в C# или всякие wrapping_add checked_add, saturating_add в Rust

[mayton2019]

Да. Про арифметику с насыщением я читал. Но не использовал нигде. Как по мне - это должно быть
глобальной опцией. Либо в скоупе компиллятора либо в классе либо в функции. Потому что практически делать сложение через saturating_add не очень удобно. Здесь я беру аналогию обработки исключений.
Никто не хочет проверять файловую операцую на каждый чих. Просто хотят try { } catch IOEx {} и таким
образом минимизировать лишние действия.

В кейсе который обсуждает автор - нужна реакция на переполнение а не молчаливое поглощение ошибки.