В предыдущей статье, была рассмотрена модель данных, необходимая для хранения информации об абитуриентах. Теперь пришло время показать, как используя реляционные БД можно обрабатывать модифицирующие запросы от миллиарда абитуриентов. А что бы расставить все точки над i, предлагаемая архитектура должна обрабатывать миллион модифицирующих запросов в секунду. Используя реляционные БД, гарантировать, что все возможные комбинации обрабатываются за сутки для миллиарда абитуриентов, каждому из которых предоставляется 20 вариантов (что предоставляет каждому абитуриенту 60 запросов к сервису)! С ростом числа абитуриентов требования по железу должны расти линейно.

О проблемах

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

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

Кажется, что решить проблему невозможно. Однако следует признать, что отказ от реляционных БД принесет куда как больше проблем, а значит нужно искать решение дальше.

Количественные оценки

Согласно модели данных, абитуриент может зарегистрироваться на поступление, подать документы на поступление (сделать выбор куда желает поступать), а так же вернуть документы (отказаться от поступления на специальность). Если представить каждому абитуриенту возможность поступать на 20 специальностей и 20 раз отправлять/возвращать документы на поступление, то итоговое количество запросов, которое сможет отправить миллиард абитуриентов, будет равно 20 + 20*2 = 60 миллиардов запросов, которые нужно обработать за сутки. Так как в БД на каждого пользователя приходится 1 + N строк, где N количество поступлений на специальность, то необходимо посчитать, сколько места займут 21 миллиард строк. PostgreSQL предоставляет возможность рассчитать размер существующей строки в БД. Для этого выполним два запроса:

SELECT (user_id,selection_session_id,spec_id), pg_column_size(apasc.enrollee_select.*) FROM apasc.enrollee_select;
SELECT (user_id,selection_session_id), pg_column_size(apasc.enrollee.*) FROM apasc.enrollee;

Первый запрос выдаст 80 байт, и второй 48 байт. Разумеется в эти величины не включен размер индексов, но его можно выразить как процент от общего объема. Итого получаем, что размер хранимых данных равен 119 гб. С учетом индексов и необходимости свободного места на диске, для корректного функционирования системы, можно принять, что диска в 500 гб будет более чем достаточно, что бы хранить информацию о выборе поступления миллиарда абитуриентов.

Как же получить миллион модифицирующих запросов в секунду?

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

Как уже сказано выше, в решаемой задаче есть две проблемы. Для того, что бы корректно принять решение пользователя - все его записи должны лежать в одной БД, однако что бы получить полноценный список поступающих на специальность нужно так же держать все эти записи в одном месте. Получается, что разделить БД не выйдет? На самом деле нет. Так как под огромным числом потенциальных модификаций выполнять операции чтения не является реалистичным, то необходимо разделить запись и чтение на два слоя. А именно, пользователи пишут в свои БД, читают уже из других, где контекстным объектом выступает специальность. Данные в последние будут попадать пакетно через шину данных (очередь сообщений). Это позволит сократить число писателей в БД и обеспечить адекватную скорость для чтения.

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

На рисунке 2 изображена структура сервисов модуля записи. Принцип работы этого модуля состоит в том, что бы максимально быстро принять данные от пользователя, не тратя время на другие операции. Учитывая, что запрос на поступление на специальность или отправку документов может выполнится только тогда, когда пользователь может участвовать в приеме (его идентификатор зарегистрирован в специальной таблице БД, состоящей из разрешенных идентификаторов), то авторизация может быть возложена на уровень БД, в случае невозможности выполнить запрос приложение может сообщить корректную ошибку. Это должно позволить выполнять запрос за максимум ~400 мкс от приема на СЗ и заканчивая записью ответа в сеть.

Абитуриенты между модулями записи могут быть разделены различными способами. Так как не существует балансировщика, способного выдержать миллион запросов в секунду, то каждый модуль записи и чтения имеет свой адрес и суб-домен, что бы можно было сразу обращаться в соответствующий модулю балансировщик. Что бы выбрать какой именно модуль использовать, можно брать первые k бит идентификатора абитуриента и считать это число как селектор модуля записи, а первые l бит идентификатора специальности как селектор модуля чтения.

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

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

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

Сервисы модуля чтения представлены на рисунке 3. СП (сервис пересылки), слушает канал передачи данных и пакетно обновляет состояние БД. Каждый пакет - это набор событий, которые нужно применить к модели. Особенность этих событий в том, что дубликаты событий можно игнорировать на уровне БД. Перечислим все возможные события:

1. Подача документов - содержит дату подачи документов на поступление на специальность;

2. Оценка абитуриента - информация о ранжировании абитуриента на специальность;

3. Согласние на поступление - содержит дату согласия на поступления на специальность;

4. Отказ от поступления - дата отказа, запись абитуриента удаляется (через флаг удаления).

Очевидно, что если для записи уже задано поле оценки, то обновление строки можно оградить условием, что бы поле было равно NULL.

Каждая запись в модуле чтения должна агрегировать в себе 1,2 и 3 события, что бы абитуриент мог поступать. Ранжирование осуществляется на основе следующих колонок: оценка абитуриента (максимальные значения выше), согласие на поступление (чем раньше, тем выше), дата подачи документов (чем раньше, тем выше). При таком подходе все абитуриенты будут корректно отсортированы без дискриминации по фамилии или еще какому-то признаку. Все абитуриенты обрабатываются обезличено. Так же это будет мотивировать абитуриентов не тянуть до последнего с подачей согласия на поступление. В случае отказа, второй раз на ту же специальность в том же вузе попать не удастся.

Такой подход позволяет намного эффективнее производить обновления и не влиять так негативно на производительность БД, так как множественные конкурентные модификации потребуют большого числа транзакций, а значит и ресурсов системы. СЧ (сервис чтения), предоставляет доступ к списку абитуриентов, поступающих на специальность, выдавая список в нужном формате (все, только подтвержденные). В виду того, что на каждый модуль чтения приходится определенное количество специальностей, то при должной планировке можно обойтись без кеширования и выдавать данные почти на живую. Разница будет заключаться только в том, что сообщения об изменениях могут приходить с некоторым опозданием, особенно в случае высокой нагрузки. Но это решаемо, если пропускная способность канала будет рассчитана на это, что однако потребует серьезной инфрастуктуры, даже упаковка в 128 изменений все равно будет давать в результате десятки миллионов сообщений общей нагрузки в процессе эксплуатации.

Миллиард абитуриентов, как уже было сказано выше, дает 20 миллиардов комбинаций поступления. Так как количество вузов обычно коррелирует с количеством абитуриентов, то возьмем соотношение абитуриентов к вузам в РФ. Приблизительно 1 миллион абитуриентов приходится на тысячу вузов. Так как количество специальностей сильно варьируется от вуза к вузу, то примем, что каждый вуз предлагает 20 специальностей. Тогда в нашей модели вузов должен быть миллион, а специальностей 20 миллионов. В этом случае в среднем на специальность будет поступать 1000 человек (20 млрд разделить на 20 млн). Если разделить специальности между модулями чтения, то даже, если какая специальность будет пользоваться аномальной популярностью, проблему все равно можно будет решить горизонтальным масштабированием, так как железо используется для каждого модуля минимальное, и всегда можно удвоить или утроить производительность модуля не вкладывая каких-то серьезных средств (добавить к машине с 2 ядрами и 4 гигами ОЗУ еще столько же не будет стоить вообще ничего для управляющей компании).

Подводя итоги, для модуля записи контекстным объектом является абитуриент. Для модуля чтения вуз-специальность. Обновление списка поступающих происходит через общую шину данных, обеспечивающую гарантированную доставку сообщения хотя бы 1 раз.

Нагрузка на шину данных и время обработки

На запись система принимает миллион запросов в секунду. Сервис пересылки работает как револьвер, переключаясь между каналами и отправляет данные в виде пакета по 128 изменений, либо меньше, если есть что отправлять и прошло больше определенного периода времени с последней отправки. В идеале модули записи отправляют данные не сразу все в один канал, а случайно, что бы избежать избыточной мгновенной нагрузки на канал. При таким подходе в шину данных в общем (от всех модулей записи) должно уходить не более 7 812 сообщений в секунду в максимально возможной нагрузке. Если принять, что максимальная длина сообщения равна 16 кб, то максимальная нагрузка на шину будет составлять 122 мб/с.

Если принять n равным 64, то на каждый модуль записи будет приходиться 15 625 запросов в секунду от абитуриентов. Если запросы будут равномерно приходится на все специальности, тогда получится 122 сообщения в секунду. При m равным 32, на каждый канал будет приходится 4 сообщения в секунду с каждого модуля записи каждому модулю чтения. Так как запись осуществляется последовательно (хотя можно сделать несколько инстансов сервиса пересылки, что бы один работал с одними каналами, другие с другими), то в реальности количество отправленных сообщений будет ниже. Если время обязательной отправки сообщения будет больше, чем 1 секунда, то очевидно, что количество отправленных сообщений будет стремительно падать. Так как каждый абитуриент может отправить всего 60 модифицирующих запросов, то общее число равно 60 000 000 000. На каждый модуль записи приходится 937 500 000 запросов. При поддержании обработки в 15625 запросов в секунду, весь объем работ будет выполнен за 60 000 секунд (~16,5 часов).

Для уже принятого m равного 32, получается, что в секунду может приходить 244 сообщения с изменениями (количество затронутых изменениями строк не превышает 31 250). Учитывая, что речь идет про пиковые нагрузки, можно считать, что в один поток PostgreSQL вполне в состоянии агрегировать такое количество изменений в БД и обеспечить максимальную производительность чтения, несмотря на частый пересчет индексов.

Из принятых выше 20 000 000 специальностей на каждый модуль чтения приходится 625 000, что дает нам 625 000 000 пар абитуриент-специальность на каждый модуль чтения. Если учесть, что максимум на каждую пару может быть 4 изменения (3 от самого абитуриента и 1 от сервиса оценки), то общее возможное число изменений равно 2 500 000 000 или 19 531 250 сообщений. При скорости обработки равной 244 сообщений в секунду весь объем будет выполнен за 80 046 секунд (~22 часа).

Особенности архитектуры по масштабированию

Модули записи масштабируются по количеству абитуриентов, а модули чтения по количеству специальностей, легко заметить, что управляя этими числами можно масштабировать систему в произвольных количествах, при этом сохраняя нагрузку на канал в пределах тех же 244 сообщений в секунду на модуль чтения. При правильно спроектированной шине данных, разницы в работе системы для 1 млрд и 1 трлн абитуриентов не будет никакой, кроме увеличения общей нагрузки в 1000 раз, при этом цена обработки 1 абитуриента останется константной. Так же важно заметить, что чем больше модулей чтения, тем дольше модулю записи потребуется времени, что бы собрать пакет из 128 сообщений. Каждый модуль записи создает только 122 сообщения в секунду, очевидно, что для 32000 модулей чтения накопление 128 изменений займет минуты, это можно частично решить, уменьшив размер пакета, но все равно обновление списка абитуриента будет занимать десятки секунд, либо заполонять шину данных сообщениями с 1-2 изменениями.

По мере роста числа модулей записи наступает проблема, что шине данных придется иметь дело с таким огромным числом клиентов, что она не сможет справится, поэтому если предполагается в системе абитуриентов больше, чем 10¹², то использовать предлагаемую архитектуру уже окажется затруднительным и придется выжимать все возможное из железа и софта, свыше 10¹⁵ уже гарантированно невозможно из-за общей шины данных, не способной обрабатывать такое число сообщений у сотен тысяч модулей (напомню, что через шину будет проходить уже в 1 000 000 раз больше данных, т.е. 116 пб/с - петабайт в секунду!). У каждого решения есть свои ограничения, и описываемая система не является исключением. Читателю предлагается самостоятельно найти способ обойти это ограничение.

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

Сам процесс разделения данных может быть как деление поровну, так и выделение самостоятельного модуля, который уже дальше делится не будет. Если учесть, что общий объем данных примерно равен 120 гб, то на 64 модуля записи придется 1,8 гб, копирование половины этого объема займет пару секунд - намного дольше происходит аллоцирование железа под новый модуль и изменение конфигурации доменной зоны. Такой подход хорош тем, что в случае неслучайных идентификаторов абитуриентов (например часть идентификатора, используемая для определения модуля, задается его регионом), можно часть регионов объединить на одном физическом модуле, а под наиболее густонаселенные создавать сразу отдельные. Имея на руках демографическую статистику можно прогнозировать нагрузку и предварительно аллоцировать нужные объемы железа.

Стоимость

Из-за ухода из РФ AWS, придется использовать цены всяких ноунейм облачных провайдеров, поэтому воспользуемся калькулятором от НеХерня.Cloud.

Для модуля записи нужна БД с 4 ядрами и минимум 8 гб ОЗУ. НеХерня предлагает s2.small за 11 117 рублей в месяц. Для сервисов модуля записи нужно:

• Сервис записи - 2 ядра, 2 гб ОЗУ, потребуется 3 инстанса для гарантированной работы системы;

• Сервис оценки - так как не известно, каким образом они будут вычисляться (и в статье об этом ничего не говорится), то выделим 4 машины по 0.5 ядра и 0.5 гб ОЗУ;

• Сервис пересылки - желательно иметь по 1 машине на не более 4 канала. Так как m равно 32, то сервисов пересылки будет 8, каждый 0.5 ядра и 0.5 гб ОЗУ.

В сумме получается 2*3 + 4 * 0.5 + 8 * 0.5 = 12 ядер и 12 гб озу. Kubernetes кластер для таких размеров стоит 18 014. Стоимость одного модуля записи в месяц обойдется в 29 131 рублей.

Для модуля чтения потребуется БД с 8 ядрами и не менее 16 гб озу, подходит s2.medium, обойдется в 21 975 рублей в месяц. Для сервисов чтения нужны следующие ресурсы:

• Сервис чтения - до 4 инстансов по 2 ядра и 2 гб ОЗУ;

• Сервис пересылки до 8 инстансов по 0.5 ядер и 0.5 гб ОЗУ.

В сумме выходит 4 * 2 + 8 * 0.5 = 12 ядер и 12 гб озу. Такое железо стоит 18 014 рублей в месяц. В итоге один модуль чтения обойдется в 39989 рублей в месяц.

Для шины данных необходимо не менее 8 партиций, каждая из которых должна иметь не менее 12 ядер и 36 гб ОЗУ с 512 гб SSD диском. Стоимость такой машины равна 22 442 рублей в месяц, так как их необходимо 8, то шина данных на kafka обойдется в 179 536 рублей в месяц.

Итого, общая стоимость системы вычисляется по следующей формуле:

64 * СМЗ + 32 * СМЧ + СШД = 64 * 29131 + 32 * 39989 + 179536 = 1864384 + 1279648 + 179536 = 3 323 568 рублей в месяц.

Если поделить эту сумму на число абитуриентов (1 млрд), то получается стоимость обслуживания одного абитуриента равной 0.003323568 рублей в месяц или 0,33 копейки в месяц. Довольно дорого, но необходимо учитывать, что можно значительно (по меньшей мере в 100 раз) уменьшить это число, если ограничить варианты поступления до 5, а так же увеличить время гарантированной обработки всех комбинаций до недели или уменьшить число обрабатываемых запросов с 1 000 000, до скажем 100 000.

Так же следует учитывать, что для работы приемной комиссии такие затраты нужны сезонно и выделяться могут по необходимости, после окончания приема голосов абитуриентов, все модули записи могут выводиться из эксплуатации, ввиду их ненужности. Учитывая все перечисленные факты, стоимость обработки одного абитуриента, равной 0,33 копейки в месяц, можно считать адекватной, тем более что речь идет о 1 млрд DAU. Сама система в состоянии принять куда как больше абитуриентов, если они будут пользоваться системой не все в один день.

Заключение

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

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

P.S.

Для работодателей

https://hh.ru/resume/b33504daff020c31070039ed1f77794a774336