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

Причина создания и планы

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

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

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

Я решил это проверить.

В данной статье будет описана задача и выбранные технологии.

Во второй части будет описана база данных для хранения правил и результатов.

В третьей части будет создано решение на базе Apache Spark и его функций по работе с графами.

Бонусом получится сравнить скорость выборки результирующих данных из Postgres с помощью рекурсивных запросов и запросов к Apache Spark с помощью GraphFrame.

Общее описание задачи

Предположим, получена задача создать приложение по распределению затрат в организации по отделам. При этом отделы могут часть своих затрат переводить на затраты других отделов.

Более жизненное описание. Есть торговая фирма, где есть отделы:

• Продаж.

• Закупок.

• IT.

В процессе работы отдела продаж он просит отдел закупок сделать закупки товаров, а отдел IT предоставить дополнительные ресурсы.

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

Самое интересное здесь, когда отдел закупок отдает часть своих затрат отделу IT, а отдел IT в свою очередь отдает часть своих затрат отделу закупок, и такое может повториться несколько раз.

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

Графическое описание

Предположим есть 2 отдела с такими правилами распределения своих затрат:

Текстовое описание правил:

1. Затраты меньше 100 рублей, не распределять.

2. Отдел 1 всегда должен оставить у себя 25% пришедших затрат. Эти затраты дальше не должны распределяться.

3. Отдел 1 может отдать 25% своих затрат отделу 2.

4. Отдел 1 может отдать 50% своих затрат отделу 3.

5. Отдел 3 не имеет правил распределения затрат: то есть все затраты пришедшие в этот отдел в нем и остаются.

Для отдела 2 правила аналогичны.

Пример распределения затрат

Предположим, отделу 1 выставили по результатам месяца сумму в 1000 единиц затрат.

Теперь он должен распределить свои затраты.

Согласно правилам из предыдущего раздела, получилась следующая иерархия распределения:

Что тут интересно, отдел 1 отдал часть своих затрат отделу 2, однако отдел 2, в свою очередь отдал часть тих затрат обратно отделу 1, который еще раз вернул их отделу 1. И третий уровень последний, так как суммы стали меньше 100 единиц.

Итоговая сумма для распределения затрат отделом 1 получилась следующая:

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

Подразумеваемые ограничения

Описана очень облегченная задача, далекая от реального мира. Данная активность задумана как проверка работоспособности технологий, а не для написания готового решения.

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

Выбранные технологии

Хранение данных

Для хранения правил распределения затрат и результатов распределения будет использоваться PostgreSQL с простой реляционной структурой таблиц.

Это позволит сравнить производительность поиска результатов расчета с помощью SQL-запросов (через рекурсивные запросы) и с помощью запросов к Apache Spark.

Расчеты

Распределение расходов будет выполняться с помощью Apache Spark.

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

Встроенная поддержка работы с графами в Apache Spark, к сожалению, работает на прошлой версии API для работы с данными (RDD вместо DataFrame), что побудило использовать плагин GraphFrame. Радует, что проект GraphFrame известный и живой проект.

Итог

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

Тем, кому интересно, предлагаю следить за дальнейшей активностью.