Корректность

Проблема

Представьте, что вы разрабатываете систему бронирования билетов для концертного зала. Пользователи могут просматривать свободные места и бронировать их. Все довольно просто. Но что произойдет, если два пользователя попытаются забронировать одно и то же место одновременно?

Алиса хочет место B8. Боб тоже хочет место B8. Вот что должно произойти:

Алиса получает место, а Боб получает ошибку. Но вот что может случиться в конкурентной среде:

Оба пользователя проверили доступность места до того, как кто-либо из них завершил бронирование. Оба увидели, что место свободно. Оба продолжили процесс бронирования. Запись пользователя Боб перезаписала запись Алисы, и теперь Алиса думает, что у нее есть билет, но когда она придет, то обнаружит на своем месте Боба.

Это проблема корректности. Несколько потоков сделали общее состояние некорректным. Проверка "свободно ли место?" и само действие "забронировать его" произошли как два отдельных шага. Другой поток вклинился между ними и сделал исходное предположение недействительным. Алиса проверила место, ответ был утвердительным, но к тому моменту, когда она выполнила действие на основе этого ответа, он уже перестал быть верным.

Тот же самый паттерн встречается повсюду на интервью по ООП проектированию. Ограничители запросов проверяют, не превышен ли лимит, прежде чем разрешить запрос. Пулы соединений проверяют, свободно ли соединение, прежде чем выдать его. Кэши проверяют, есть ли место, прежде чем добавить элемент. Каждый раз, когда результат проверки может измениться до действия, перед вами проблема корректности.

В этой статье мы рассмотрим четыре решения проблем корректности, от самого простого к самому сложному:

• Широкая блокировка (Coarse-grained locking) защищает все связанное состояние одной блокировкой.
• Точечная блокировка (Fine-grained locking) разрешает конкурентный доступ к независимым ресурсам, защищая при этом связанные.
• Атомарные переменные (Atomic variables) работают для одиночных переменных, но не подходят для инвариантов, состоящих из нескольких значений.
• Изоляция потоков (Thread confinement) полностью исключает конкурентность для связанных данных.

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

• Check-then-act - например, бронирование места, если оно свободно.
• Read-modify-write - например, увеличение счетчика.

Решения

Любую проблему корректности можно решить одним из четырех подходов. Мы рассмотрим их в порядке того, как часто они встречаются на собеседованиях.