У нас есть некоторый диапазон чисел от 0 до N, надо написать две функции int alloc() и free(int). Первая выбирает один из свободных идентификаторов из диапазона [0, N), а вторая соответственно — «возвращает» его для повторного использования(полагаем, что число N достаточно мало, что бы идентификаторы могли закончится если их не возвращать, но больше чем число выделенных в каждый конкретный момент времени идентификаторов). При этом на «нижнем уровне» у нас есть только DHT. Нету блокировок, и, кроме того, от алгоритмов требуется отказоустойчивость — если какой-то из узлов кластера «сложится» во время выполнения алгоритма поведение системы должно быть предсказуемо. Если задача интересна, а также интересно узнать почему отказоустойчивый сервис с такой сигнатурой невозможно корректно использовать, и как надо исправить сигнатуру что бы это стало возможно — добро пожаловать под кат.

API

На самом деле, начнем с того что уточним API нашего «аллокатора». Как было отмечено выше, текущий API некорректен — его невозможно использовать в распределенной системе, потому что вызывающий код не всегда сможет понять в каком именно состоянии находится тот или иной элемент пула.

Простой пример.
1) Предположим я вызываю функцию allocate(), она завершается успешно, но вызвавший код перестает работать в момент передачи ответа от allocate(). Проблема — идентификатор выделился, но я про него ничего не знаю. У меня физически нет возможности написать какую-то процедуру recovery и удалить его. С другой стороны, код, отвечающий за выделение ресурса уже отработал, с его точки зрения идентификатор выделен. И он сам не сможет его удалить, потому что должен дождаться вызова free. Которого не будет.
2) Необходима идемпотентность функции free(). Очевидно, что вызывающий код должен написан так, что бы в любом случае вызвать free(). Очевидно, получив ответ от allocate мы занесем его в персистентную память(в RDBMS, key-value storage, или просто напечатаем на принтере и бумажку загрузим в сканер). И затем, в определенный момент времени, когда какой-то узел решит удалить ресурс, он вызовет free(). Однако, если в момент работы free узел выключится, наша «вызывающая сторона» очевидно попытается вызвать его еще раз(как именно это будет реализовано — не важно. Важно что это реализуемо). Вот тут нас ожидает неприятный сюрприз. Дело в том, что free мог все-таки освободить ресурс. И даже более того, какой-нибудь сторонний alloc() мог снова его выделить. Тогда мы еще раз освободим ресурс, но на этот раз это уже будет чужой ресурс.

Вообще говоря есть несколько способов решения этих проблем с API.

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

То есть сигнатура методов меняется на int alloc(T t) и free(int id, T t). Не важно какого типа T, важно, чтобы на нем существовало некое отношение эквивалентности, и что по нему мы сможем решить две описанный выше проблемы. Во-первых метод free можно сделать идемпотентным. Во-вторых, мы можем ввести относительно простую процедуру для удаления «фантомных» идентификаторов, которые были выделены, но инфу по которым мы не получили(см. проблему 1). Подробнее на этом останавливаться не будем, что бы не раздувать статью.

Заметим, что практически использовать измененный таким образом сервис можно почти всегда, т.к. в большинстве случаев мы выделяем «идентификаторы» под что-то, и всегда можем использовать это «что-то» в качестве тега.

Теперь еще немножко, осталось понять как именно ведут себя alloc и free в случае «частичного» выполнения, что бы, в свою очередь, понять, как нам писать вызывающий код, и возможно ли его написать.

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

• Вызывающий код должен сначала записать куда-то идентификатор, по которому вызывает alloc, и уже потом его вызвать. Благодаря этому, вызывающий код сможет реализовать процедуру recovery, где поступит в обратном порядке — переберет все выделенные пары (id, t), и вызовет free для всех пар, про которые нет упоминания в его хранилище.
Аналогично, мы не можем узнать и про метод free — вызвался он, или нет.
Отсюда рождаются еще два правила
• Идентификатор переданный free должен считаться в системе «свободным»(то есть уже не использоваться) ПЕРЕД вызовом метода free
• И, тем не менее, метод free должен вызываться(допустимо — несколько раз) до тех пор, пока хотя бы один его вызов не завершится успешно.

Ну что же, перейдем к реализации.

Реализация

Напоминаю, что на входе у нас DHT. Для людей, пишущих на джаве будем считать что у нас есть ConcurrentMap(его интерфейс, между прочим совершенно тривиальный, будет понятен разработчикам, использующих другие языки). При этом ConcurrentMap разных хостов «смотрит» на одно и то же содержимое.

Сами по себе операции в DHT атомарны(это вполне себе поддерживается целым рядом имплементаций DHT).

Однако, между вызовами в DHT атомарности нет, и эту часть нам надо учесть и поддержать в своей реализации.

Итак, реализация

Очевидно что у нас в DHT будет какая-то карта вида id->t (ну или наоборот). Проблема в том, как добраться до первого свободного id, не перебирая все занятые узлы?

Предлагается такое решение. Давайте построим бинарное дерево интервалов, такое, что
• Корень дерева — интервал [0, N)
• Под не-листовым узлом X [a, b) находится ровно два узла [a, c) и [c, b), где c выбирается так, что бы длины этих интервалов были равны
• А интервалы вида [id, id+1) — являются листами дерева.
Очевидно что у такого дерева N листов, к каждому из которых от корня можно добраться за ln(N) переходов.

Давайте теперь в каждый не-листовой узел дерева положим число зарезервированных идентификаторов на интервале, который представляет этот узел. А в листовые узлы дерева будем помещать тег, если соответствующий идентификаторов занят, и null — если свободен.
Теперь осталось сохранить это дерево в DHT. Кроме того, важно обновлять в его узлах информацию в правильном порядке, ведь, напоминаю, наш алгоритм должен корректно работать, даже если он прервется на произвольном шаге.

Положим у нас есть структура Interval с двумя полями — from и to, задающая полуоткрытый интервал(включает from, но не включает to). Очевидно, что такая структура кодирует узел дерева. Также следует отметить относительно тривиальный момент — в дереве нет повторяющихся узлов, и, более того, для определения позиции интервала в таком дереве ничего, кроме этого интервала не нужно. Иными словами, нам нет нужды связывать элементы дерева «указателями». Мы всегда можем построить алгоритм, который по узлу X сможет определить, какие узлы находятся «под» ним, и какой узел находится «над» ним.
Это достаточно важное свойство, упрощающее нам жизнь.

Положим в этой структуре есть нужные конструкторы, очевидные equals и hashcode, а также есть еще три полезных метода: left(), right() — для определения дочерних узлов и up() — для определения родительского. С конструкторами и хеш-кодами я думаю все справятся. С left() и right() тоже. С функцией up() придется несколько сложнее, но и ее написать возможно(к ней мы вернемся в конце статьи, что бы не размывать текст лишними подробностями).

Теперь, имея «волшебную» структуру Interval, которая умеет кодировать наше дерево интервалов, дело осталось за малым.
В allocate нам надо выбрать какой-нибудь непустой лист и записать в него тег, а потом подняться «вверх» от выбранного листа и обновить их значения. При этом важно помнить о двух вещах
• Тег добавляется в list атомарной операцией putIfAbsent
• Значения в не-листовых узлах обновляется через цикл с read-modify-atomicUpdate. А именно — мы читаем значение из обновляемого узла, читаем значение в дочерних узлах, записываем в обновляемый узел сумму дочерних через atomic replace. Если atomic replace не сработал, повторяем операцию.
• Если даже мы прочитали из DHT, что в под-дереве узла есть свободные листья, это еще не значит что они там действительно есть.
Поэтому наш allocate будет написан в виде цикла «до успеха» из failfast процедуры поиска и обновления пустого листа. Заметим, что первая модификация дерева, которую мы делаем — обновление листа, а уже потом — обновление родительских узлов. Это необходимо, т.к. allocate может завершится в любой момент.

Free работает примерно также — он «освобождает» идентификатор(т.е. удаляет узел из DHT), если тег в нем совпадает с запрошенным, и обновляет узлы вверх по дереву. При этом обновление узлов совпадает с тем, как оно идет в allocate. Единственное, что важно отметить — free выполняет обновление дерева даже если листовой узел не содержит значения(т.е. если free уже вызывали). Это необходимо, т.к. предыдущий free мог выполнится частично, освободив лист, но не обновив вышестоящие узлы. Собственно, именно для этого нам нужно требование в API о том, что free можно вызывать несколько раз, и что его необходимо вызывать повторно, если есть сомнения в том, что в прошлый раз его вызов завершился успешно.

Функция up

Собственно, обещанная функция up(). Тут стоит отметить, что написание left(), right() и up() значительно упрощается, если мы условимся, что интервал верхнего уровня имеет длину 2^n. Тогда и любой другой интервал в дереве будет иметь длину 2^n, кроме того, интервалы на одному «уровне» дерева будут иметь одинаковую длину. Вообще говоря, все три сабжевые функции можно написать для интервала верхнего уровня произвольного вида(но тогда помимо «текущего» интервала нужно будет всегда знать интервал верхнего уровня). Но это неудобно, а обобщение до 2^n ничему не вредит.

Таким образом, при длине интервалов 2^n, left() и right() пишутся тривиально, а для up() нужно лишь определить, является ли текущий интервал «правым» или «левым» для своего родительского интервала. Это определяется по простому правилу — у «левых» интервалов начальное значение делится без остатка на удвоенную длину интервала. Соответственно, зная про интервал, был ли он получен из функции left() или right() несложно применить обратное действие и получить интервал верхнего уровня.

Failsafe resource allocator over DHT