Lock vs. Lease

10 August 2010 theory distributed concurrency

Представьте себе типичную задачу, есть поток событий и этот поток событий надо разделить между несколькими пользователями системы. Типичный пример: модерация. Скажем, есть три модератора, которые просматривают добавляемый пользователями контент (допустим рекламные кампании). Мы хотим “распилить” поток событий между модераторами, чтобы они не делали одну и ту же работу дважды.

В самом простом случае, мы можем использовать mq в любом его проявлении. Пользователи просто берут сообщение из головы и обрабатывают его. Эта схема хорошо работает, но к сожалению не всегда применима. Например, если пользователи имеют возможность указывать критерии событий которые хотят обрабатывать. Последнее требование очень часто в том или ином виде всплывает в подобных задачах, потому что люди (точно так же, как и процессоры) плохо переносят context switch. Например, если я настроился на модерацию авто тематики, то я фигурально выражаясь загрузил в кеш ключевые слова относящиеся к этой тематике и буду очень расстроен если мне подсунут объект с тематикой относящийся к сотовым телефонам.

Окей, мы не можем использовать mq, что тогда? Далее приходит на ум следующее — хранить события в реляционной таблице (чтобы иметь возможность фильтрации) и брать shared lock на каждое из событий/объектов при их обработке. В данном случае lock’и позволяют исключить дублирующую обработку события. Ничего криминального в использовании локов для решения этой задач нет, но если вы начнете имплементировать подобное решение, то вы очень быстро прийдете к тому что lock’и обладают семантикой отличной от той которая необходима вам. И вот почему…

Lock timeout

Если мы говорим про web-приложение, то необходимо понимать что факт закрепления события за конкретным пользователем должен иметь timeout. HTTP — это stateless протокол. После того как вы закрепили событие за пользователем, он может просто закрыть браузер и пойти по своим делам. Если мы хотим чтобы любое событие было рано или поздно обработано, мы обязаны аннулировать устаревшие локи.

Но традиционный механизм lock’ов не имеет timeout’ов, и это решение вполне обосновано, так как обычно lock’и или используются внутри одного адресного пространства (а следственно проблемы исчезновения lock owner’а нет) или используются в distributed окружении, но имеют механизм autorelease’а (при разрыве соединения текущего владельца блокировки и координатора автоматически происходит release).

Это означает в традиционных use case’ах использовании lock’ов между текущим владельцем лока и координатором всегда есть канал связи, чего нет в нашем случае.

Immediate Locking

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

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

Lease

Проблема в том, что люди видя эту семантическую разницу пытаются расширить интерфейс локов для того чтобы покрыть им данный use case использования. Это опасно, так как в механизм добавляется элемент autorelease’а, который легко может нарушить целостность данных. Представьте, что если при традиционном использовании локов (скажем, параллельном изменении коллекции элементов) autorelease произойдет до того момента когда владелец лока успеет выполнить операцию?

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

Помните DHCP? Это протокол автоматической конфигурации сетевого стека компьютера. Сегодня его можно найти буквально в любом домашнем маршрутизаторе. DHCP позволяет компьютеру автоматически получать IP-адрес и автоматически конфигурировать сетевой стек в зависимости от топологии сети в которой находится компьютер.

Обратите внимание, когда компьютер получает IP-адрес по DHCP, он не посылает запрос “дайте мне IP 192.168.1.15”. Он посылает запрос: “дайте мне любой свободный адрес”. В ответ он получает lease. Lease — это аренда адреса. Аренда имеет timeout, по истечении которого, если lease не был продлен, то аренда аннулируется и IP-адрес возвращается в список доступных. Вполне подходит под нашу задачу, верно?

В случае DHCP, клиенту по большому счету все равно с каким IP-адресом работать. В нашей задаче клиенту все равно какие именно события обрабатывать. Главное чтобы они удовлетворяли формальным требованиям о которых мы говорили раньше.

Модель аренды гораздо ближе к природе задачи. Во-первых, timeout’ы, которые нам просто необходимы, лежат в природе механизма аренды. Во-вторых, аренда не подразумевает владения объектом. Фактически в этот же момент с этим же объектом может происходить какая-то другая операция (например, индексация), которая скорее всего имеет возможность выполнятся параллельно, а значит данные находящиеся в объекте не являются предметом защиты от конкурентного доступа. Это сигнализирует о том что локи в данном случае не уместны. В этой задаче lock’и могут служить только инструментом обеспечения целостности списка арендованных объектов, но не более того.

P.S. интересно услышать к какими способами решения схожих задач приходилось сталкиваться вам?