Записки программиста

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

Суть проблемы

Допустим, вы храните в памяти состояние неких объектов. Для определенности, пусть это будут пользователи в системе и количество денег в различной валюте на счетах этих пользователей. В систему приходят какие-то события, например, транзакции, изменяющие состояние счетов. Если вы пишите на Erlang, будет вполне естественным завести ETS, в которой ключом будет выступать имя пользователя, а значением — состояние счета этого пользователя.

Пока вы обрабатываете транзакции в один поток, все хорошо. Берем состояние счета из ETS, обновляем, кладем обратно в ETS. Но нагрузка на систему растет, и обрабатывать транзакции в один поток уже не получается. Поэтому вы заводите пул процессов, а транзакции между ними планируете распределять случайным образом, round robin’ом или же в зависимости от текущих длин очередей сообщений. Но тут возникает состояние гонки. Если два процесса одновременно получат транзакции, затрагивающие одного и того же пользователя, вы запишите фигню.

Поэтому правильно делать шардинг не round robin’ом или еще как, а по crc32 от ID юзера. Итого получаем N gen_server’ов, каждый из которых работает со своим подмножеством ключей в ETS. А может быть, каждый gen_server даже имеет собственную ETS. Как правило, такая схема отлично работает и проблем не возникает.

Но иногда проблемы все-таки возникают. Во-первых, скорее всего, нагрузка на вашу систему меняется со временем. В среднем вы обрабатываете 1000 транзакций в секунду, но в пики — 10 000 транзакций. В результате большую часть времени все работает хорошо, а в пики скапливаются очереди и приложение падает. Можно, конечно, тупо запустить 10 000 процессов, но это не так-то дешево, даже в Erlang’е, к тому же, большую часть времени эти процессы будут простаивать.

Во-вторых, что, если нужно перевести деньги с одного счета на другой? Если повезет, то вы просто напишите уродливый код типа «если за оба счета отвечает один процесс, просто обновить их, иначе сделать gen_server:call другому процессу». Но скорее всего вы напишите просто «сходить в другой gen_server», в результате чего в тестовом окружении ваше приложение будет работать нормально, а в боевом — грохнется из-за рекурсивного gen_server:call. Ведь при 1000 gen_server’ов ошибка проявляется только в 0.1% случаев, а то и реже, если необходимость переводить деньги со счета на счет зависит от каких-то флагов (реферальная программа, например). Стоит ли говорить, что ситуация становится намного сложнее, если нужно атомарно обновить три и более счетов?

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

Решение

А давайте заведем специальный процесс и назовем его менеджером локов. Если требуется сделать что-то со счетами x, y и z, идем в менеджер локов, сказав lock([x,y,z]). По завершении работы, соответственно, требуется сказать unlock([x,y,z]). Обратите внимание, что все блокируемые ключи передаются сразу, чтобы сделать дэдлок было труднее. Чтобы не забыть сделать unlock после lock, заведем специальную функцию-обертку, в результате чего работа со счетами будет выглядеть примерно так:

Помним, что передаваемая в качестве аргумента функция может бросить исключение, поэтому ее нужно обернуть в try … after. Кроме того, следует принять во внимание, что блок after не будет выполнен, например, если процесс, обновляющий счета, будет прибит с помощью exit(Pid, kill), поэтому менеджер локов должен мониторить процессы, захватывающие локи.

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

Реализацию всего этого хозяйства вы найдете в этом репозитории на GitHub. Как им пользоваться я вкратце описал в README.md. Также можете заглянуть в модульные тесты или в саму реализацию, она довольно простая.

Кое-какие замечания касательно реализации

Честно говоря, я довольно долго не работал с Mnesia. Возможно, она куда лучше решает эту задачу по сравнению с самопальным велосипедом. Но последние впечатления от Mnesia были не очень приятными, все работало медленно и копились очереди. Кроме того, как будет показано ниже, в задаче много переменных, подогнать значения которых в случае с Mnesia, видимо, будет непросто.

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

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

У меня используется только один gen_server, в который можно упереться. Для решения этой проблемы можно завести пул. Можно даже завести пул побольше, отвечающих за локи вообще ко всем ресурсам, а не только одну ETS. Но у такого решения есть свои проблемы. Если нужно залочить ключи, за которые отвечают разные процессы, нужно лочить их в правильном порядке. При этом мы можем залочить x на одном gen_server, затем пойти во второй gen_server, чтобы залочить ключ y, выяснить, что он уже кем-то используется, в результате чего придется разлочить x. Но какой-то другой процесс в это время может пытаться залочить x и не преуспеть.

В теории менеджер локов может разрешать двойное взятие одного и того же лока одним процессом. Однако в моей реализации это запрещено. Во-первых, так проще. Во-вторых, если вы написали что-то вроде:

… то это почти наверняка не то, что вы на самом деле имели в виду. На самом деле во вложенной функции вы хотите получить доступ к X2, а не тому значению, что находится в ETS. Но вложенные локи непересекающихся множеств ключей при этом, разумеется, разрешены.

Касательно оптимизаций. Для хранения локов я использовал sets и dict. Не удивлюсь, если окажется, что ETS будет работать быстрее. С другой стороны, если вы работаете с большими ключами, из-за накладных расходов на копирование данных это может оказаться и не так. Также я делаю demonitor в функции unlock, хотя, возможно, было бы эффективнее делать demonitor по расписанию, проверяя, какие из процессов давно не ходили за локами или уже завершились. С другой стороны, такая «сборка мусора» может оказаться довольно тяжелой операцией, из-за которой у менеджера локов быстро скопятся очереди. В общем, на самом деле тут ничего не понятно, все замеры нужно проводить на реальных данных и под реальной нагрузкой.

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

Метки: Erlang, Функциональное программирование.