Using hierarchical indexing for access control to shared resources in microservices

Full Text

Введение

С развитием разработки высоконагруженных систем произошла трансформация архитектуры серверной части. С приходом облачных вычислений и таких технологий, как Kubernetes [1, 2] и Docker [3], популярность микросервисов возросла. В настоящее время существует значительное число готовых фреймворков для построения микросервисов как от крупных компаний, так и open source решения. При проектировании микросервисов применяется ряд хорошо зарекомендовавших себя решений. В частности, широко используется удаленный вызов процедур. Данный подход появился сравнительно давно и претерпел ряд эволюционных изменений. Также широко известны решения, основанные на Corba [4], OLE/COM [5], однако данные решения не получили широкого распространения в проектировании микросервисов. Эти решения во многом зависят от операционной системы, в частности, ole/com решения возможно использовать только в windows-системах. К другим недостаткам данных технологий можно отнести сложность проектирования решений, использующих данные технологии. В микросервисах, основанных на удаленных вызовах процедур широко применяется gRPC [6] (решение, предложенное Google), использующее в качестве IDC определения сообщения Protobuf и Thrift [7] (решение, предложенное Meta).

Первое решение несколько более производительно, однако второе решение обладает более богатым функционалом. К недостаткам микросервисов, основанных на удаленных вызовах процедур, можно отнести синхронный вид взаимодействия между микросервисами. В корпоративном мире также получили достаточно большое распространение микросервисы, основанные на Restfull-технологии. Типичным примером такого подхода является решение, предлагаемое библиотекой Spring Boot [8], широко известной Java библиотеки Spring.

Данное решение в качестве метода кодирования сообщений использует Json-формат, и вызовы микросервисов происходят через Web-сервисы. К недостаткам такого подхода можно отнести большую latency и малую скорость обработки сообщений, а также зависимость от языка программирования (в данном случае Java). Другим подходом в программировании микросервисов является подход с асинхронными вызовами. Здесь есть две основные модели: архитектура без брокера сообщений и с ним. При проектировании микросервисной архитектуры с брокером сообщений (рис. 1) используются серверные решения на базе ActiveMQ, RabitMQ, Kafka и многие другие. Основная идея в данных системах строится на применении Publisher/Subscriber [12] шаблона проектирования.

 

Рис. 1. Mикросервисная архитектура с брокером сообщений

Fig. 1. Microservice architeckture with message brocker

 

Микросервис, который производит данные, публикует их в очередь на сервере. Микросервис, который обрабатывает данные, подписывается на них. При этом можно организовать чтение данных несколькими сервисами, а также выбрать точку, с которой начать обработку данных. Очень часто узким местом в такой архитектуре является брокер сообщений. К его производительности предъявляются большие требования. Системы, не использующие брокер сообщений (рис. 2), гораздо более гибкие.

 

Рис. 2. Mикросервисная архитектура без брокера сообщений

Fig. 2. Microservice architeckture without message brocker

 

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

При реализации асинхронного микросервиса часто применяются такие методы построения многопоточных приложений, как порождение отдельного потока исполнения (fork and join) [9] или использование очереди сообщений. Применение отдельных потоков исполнения вызывает проблемы при большом потоке сообщений, т.к. создание потока исполнения требует большого количества машинного времени. При реализации очереди сообщения попадают в очередь и поочередно выбираются потоками исполнения. Потоки исполнения при этом не создаются для каждого сообщения, а берутся из пула потоков. К настоящему времени создано достаточно большое количество примитивов для выполнения данного подхода.

Например, в библиотеках языка C# можно найти такую структуру, как BlockingCollection. Эта структура реализует концепцию producer/consumer [10, 11]. Нити, производящие данные в цикле, могут добавлять их в эту коллекцию. Нити, обрабатывающие данные в цикле, забирают их из коллекции. Эти операции выполнены потоко-безопасным образом. При отсутствии данных в коллекции нить-обработчик данных блокируется до того момента, как они не появятся в коллекции.

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

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

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

Теоретический подход

Рассмотрим поток различных сообщений, приходящих в микросервис. Данные сообщения относятся к одной доменной области, однако при этом должны быть обработаны различным образом. Возможна ситуация, когда порядок обработки сообщений может влиять на результат. Рассмотрим последовательность сообщений, представленных на рис. 3. В данной последовательности мы предположили, что сообщения x₁, x₂, x₅ влияют на состояние некоторого разделяемого ресурса X₁, x₃ на X₂, а x₄ на X₃ и X₂, причем X₁ является родительским ресурсом для X₂ и X₃. Сообщения y₁ на Y₁, y₂, y₃ на Y₂, а y₄ на Y₃, причем состояние Y₁ является родительским для Y₂ и Y₃. Сообщение xy изменяет состояния X₁ и Y₁.

 

Рис. 3. Последовательность сообщений

Fig. 3. Sequence of messages

 

Предполагаемый порядок обработки сообщений представлен на рис. 4. Здесь сообщения, влияющие на некоторый разделяемый ресурс, выполняются в порядке доставки в микросервис, однако порядок обработки сообщений x и y не гарантируется. В приведенном примере сообщение x₁ заблокировало выполнение сообщений x₂, x₃, потому как состояние X₁ является родительским для X₂ и X₃. В последовательности сообщений есть сообщения xy, которые могут влиять также на состояния ресурсов X₁ и Y₁. В этом случае обработка сообщений x_i и y_i должна быть приостановлена при достижении сообщения xy и продолжена только после того, как это сообщение будет обработано.

 

Рис. 4. Обработка сообщений

Fig. 4. Messages processing

 

Данный алгоритм достаточно трудно реализовать, основываясь на традиционных примитивах синхронизации [13, 14] (мьютексы, семафоры и т.д.), т.к. в общем случае мы не знаем количество разделяемых ресурсов, а также время обработки каждого сообщения может быть различным вследствие того, что для выполнения действий нам, возможно, понадобятся дополнительные данные и мы вынуждены будем сделать вызов в другой микросервис для их получения. Обработка этих сообщений в одном потоке исполнения также не выглядит перспективной, потому как вызов в другой микросервис достаточно часто занимает много машинного времени и исполнение всех остальных сообщений будет приостановлено.

Рассмотрим алгоритм, представленный на рис. 5.

 

Рис. 5. Алгоритм обработки сообщений

Fig. 5. Algorithm of message processing

 

Сообщения при доставке в микросервис попадают во входную очередь сообщений, и таким образом достигается асинхронность работы данного микросервиса. По запросу обрабатывающего потока мы берем первое сообщение в очереди на обработку. Для выбранного сообщения генерируется необходимое количество блокирующих ключей на основании типа сообщения и содержания сообщения. Данные ключи представляют собой структуры, описывающие иерархию разделяемых ресурсов и позволяющие быстро определять, является ли один из ключей потомком или предком другого. Примеры генерации таких ключей можно найти в следующих источниках^{1, 2, 3} [15].

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

Анализ метода

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

 

Рис. 6. Субоптимальный порядок обработки сообщений

Fig. 6. Suboptimal message processing

 

Добавление записи в очередь и чтение первой записи выполняется за время O(1). Каждое сообщение генерирует небольшое количество ключей (на практике не больше 4–5), вследствие этого список блокированных ключей можно реализовать при помощи списка, и поиск, удаление блокированного ключа будет иметь сложность O(n), где n – количество ключей, генерируемое для каждого сообщения, а добавление ключа – O(1).

Список ключей, напротив, может быть достаточно обширен при большом параллелизме системы, и его можно реализовать при помощи упорядоченного множества (ordered set). В этом случае операции добавления, поиска и удаления записи выполняются за O(log m), где m – количество ключей обрабатываемых сообщений.

Рассмотрим возможность взаимной блокировки сообщений с несколькими ключами. Как мы видим, алгоритм имеет 2 атомарные секции, однако они имеют доступ к одному и тому же разделяемому ресурсу – списку ключей. Следовательно, это реализуемо при помощи одного объекта синхронизации (например, mutex). При этом происходит единовременная проверка возможности заблокировать доступ к некоторым ресурсам, и, следовательно, невозможна ситуация, когда 2 сообщения потребуют доступ к одним и тем же ресурсам и будут одновременно блокировать доступ в зеркальном порядке. Следовательно, взаимная блокировка невозможна.

Заключение

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

К недостаткам также можно отнести то, что блокировка ресурса происходит перед началом обработки сообщения, а снятие блокировки – после. Применение данного алгоритма положительно сказывается на увеличении отказоустойчивости микросервисов.

 

¹Tropashko V. Trees in SQL: Nested Sets and Materialized Path. [Электронный ресурс]. 2002. URL: www.dbazine.com/tropashko4.shtml.

²Tropashko V. Nested Intervals with Farey Fractions. [Электронный ресурс]. 2004. URL: arXiv preprint cs.DB/0401014.

³ PostgreSQL index – ltree [Электронный ресурс]. URL: http://www.sai.msu.su.

About the authors

Vladimir S. Kirillov

North Caucasus Federal University

Author for correspondence.
Email: vkirillov74@gmail.com
ORCID iD: 0009-0007-3996-1844

Candidate of Physical and Mathematical Sciences

Russian Federation, 355017, Stavropol, Pushkin street, 1

References

Supplementary files