Неограниченный недетерминизм

Неограниченный недетерминизм — свойство параллелизма, благодаря которому величина задержки в обслуживании запроса может стать неограниченной, но при этом сохраняется гарантия что запрос в конечном итоге все же будет обслужен. То же: unbounded nondeterminism, unbounded indeterminacy.

Красивым и стройным решением парадоксов параллельных вычислений стала модель акторов, предложенная Карлом Хьюиттом: у параллельных вычислений не должно быть общего состояния, обслуживание запроса может затянуться на сколько угодно, общение между процессами (акторами) происходит с помощью “почтовых ящиков” (сообщений, туда приходящих).

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

Такой пример. Допустим, у нас есть онлайн-сервис, в нём у пользователя открыт “кошелёк”. На нём сумма — предположим, 100 руб. Пользователь кладёт на счёт 1000 руб. и тут же, не дождавшись обратной связи, совершает покупку на 500 руб. Пользователь этими действиями запускает на нашем сервере параллельные процессы. Может быть так, что сначала на счёт будет положено 1000 руб., а потом уже снимется 500 руб. А может быть и так, что сначала будет попытка снять 500 руб., а потом уже будут положены 1000 руб. Поскольку у нас в системе не может быть отрицательного счёта, покупка не состоится. Такие случаи надо хорошо продумывать.

Другой пример, с визуализацией. Я написал программу, которая генерирует картинку (svg-файл). В этом ей помогают четыре актора, которые она же и заспаунила. Первый актор всегда предлагает нарисовать отрезок на север, другой — на запад, третий — на юг, четвёртый — на восток. Все отрезки — одинаковой длины (16 точек).

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

Сгенерированный svg 1 Сгенерированный svg 2

Сгенерированный svg 3 Сгенерированный svg 4

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

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