Всем привет! Меня зовут Иван Привалов, я разработчик в команде BI Авито Финтеха и в этой статье расскажу, как мы сделали FIFO-сопоставление между N начислений и M списаний для бонусов. Заодно покажу подвох, без которого SQL быстро превращался в тыкву.
Статья будет полезна аналитикам и data-инженерам уровней мидл+, которые работают с финансовыми данными в Trino, Presto и Spark SQL.
В этой статье
Что такое бонусы и зачем им FIFO
Бонусы в Авито — виртуальные средства, которыми пользователи оплачивают услуги площадки: размещение и выделение объявлений, продвижение, доставку. Бонусы выпускаются по разным поводам: за активный тариф, в рамках маркетинговой акции, как компенсация за неудобства, по программам CPA. У каждого начисления есть срок жизни, и если за это время пользователь не успел воспользоваться бонусами, остаток сгорает.
С точки зрения хранилища у нас есть два независимых потока событий:
— лента начислений, по которой видно кому, когда и сколько начислили, а так же до какой даты эти бонусы живут;
— лента списаний и сгораний, когда пользователь использовал бонусы в качестве оплаты за услугу или у них кончился срок жизни.
В обычном бухгалтерском смысле начисления и траты — это два числа. Но этих данных недостаточно, поскольку нам нужно знать, что случилось с каждым бонусом, чтобы отразить это в налоговой и МСФО-отчётности, показать на аудите и корректно выгрузить в управленческие системы в конце концов. Бонус, выпущенный из тарифа, и из маркетинговой акции ложатся в строки P&L по-разному: первый закрывает выручку, второй идёт на расходы маркетинга. Чтобы их различить, нужно построить поимённое сопоставление между лентами начислений и списаний.
Это классический FIFO: первыми списываются самые ранние начисления, что создаёт большие проблемы для SQL, если надо обработать миллионы строк.
Почему на один платёж приходятся N строк начисления и M трат
Сырые события в DWH прилетают полуструктурированно, в формате JSON. И уже на этапе разбора одно начисление разворачивается в N строк с весами по подкатегориям объявлений и типам выручки:
accrual_id microcat revenue_type amount ACC-1 детская одежда tariff 600 ACC-1 бытовая техника vas 400
Это намеренная декомпозиция, чтобы бухгалтерии понимала, в каких долях и за что именно начислены бонусы. Сумма строк равна полной сумме начисления, но каждая доля несёт свою бухгалтерскую этикетку из микрокатегории и типа выручки, которую нельзя терять.
Следствие №1: уникальный id в исходниках присваивается паре из id начисления и микрокатегории. Это бакет для FIFO.
Списания, наоборот, атомарны. Одна трата равна одной строке с собственным набором атрибутов: дата, услуга, вертикаль, микрокатегория и тип выручки. Никакого внутреннего разворота у списаний нет.
Следствие №2: на стороне списаний M возникает по другой причине. За время жизни одного начисления пользователь тратит бонусы по частям: на разные услуги, в разные дни, по разным подкатегориям объявлений. Поэтому на одном платеже встречается M отдельных трат, иногда десятки. К ним добавляется событие сгорания остатка, если бонус не успел израсходоваться.
Сложность задачи в том, что слои асимметричны. Сторона начисления разнесена по подкатегориям для бухгалтерии, а списания по времени и услугам для поведенческой детализации. FIFO нужно делать по графу N×M аллокаций на каждом платеже.
Постановка задачи
На входе для каждого платежа мы имеем:
— N бакетов начислений с собственной суммой и атрибутами.
— M событий списаний и сгораний с ключом из даты, услуги, вертикали, микрокатегории и типа выручки. У каждого также своя сумма и атрибуты.
На выходе для каждой пары из бакета начисления и события списания рассчитывается точная сумма аллокации. Получаем строки вида: трата 150 ₽ на платное размещение потратила 80 ₽ из начисления ACC-1 (детская одежда, тариф) и 70 ₽ из начисления ACC-2 (бытовая техника, продвижение).
Правило аллокации, FIFO: списания съедают бакеты в порядке поступления, целыми и без округлений.
Как мы переформулировали FIFO
В открытых источниках тему FIFO в SQL обычно разбирают на простой модели «1 начисление ↔ 2–3 списания». Реальные финансовые данные устроены сложнее, и наивные подходы здесь не подойдут.
📌 Trino не поддерживает процедурный SQL, рекурсия в его CTE ограничена и плохо параллелится. На N×M-графе на каждом из миллионов платежей задача не помещается в память.
📌 Простой JOIN по сумме или дате не моделирует «поедание» бонусов в порядке поступления, а даёт двойной счёт: одно списание матчится сразу с несколькими начислениями без правильного распределения долей. Получается, списание учтётся полностью столько раз, сколько существует строк для начислений.
📌 Текущая логика агрегации схлопывает строки до уровня id начисления, из-за чего теряется бухгалтерская детализация, ради которой источник развернул одно начисление в N строк. После такой агрегации восстановить детализацию невозможно.
📌 GROUP BY с MAX/SUM не учитывает гранулярность витрины и молча задваивает или утраивает суммы. Это вообще главная ошибка при потреблении подобных витрин, в разделе про гранулярность я к ней вернусь.
Мы решили переформулировать FIFO через геометрию и сделали это в три шага.
Шаг 1. На стороне начислений взяли бакеты с ключом (id начисления, микрокатегория). На стороне списаний берём атомарные траты плюс события сгораний.
Шаг 2. В рамках одного платежа вычисляем накопительную сумму по каждой ленте:
SUM(amount) OVER ( PARTITION BY payin_ext ORDER BY ... ROWS UNBOUNDED PRECEDING )
После этого каждый бакет начисления превращается в отрезок [acc_cum_start, acc_cum_end] на оси «накопленная сумма платежа». Каждая трата превращается в отрезок [w_cum_start, w_cum_end] на той же оси.
Шаг 3. FIFO эквивалентен пересечению отрезков. Если бакет начисления и трата накладываются на одну и ту же часть оси сумм, значит, эта трата частично или целиком съела этот бакет. Сумма аллокации равна длине пересечения.
FIFO как пересечение интервалов: бакеты начисления сверху, события трат снизу, на одной оси накопленной суммы платежа. Длина пересечения равна сумме аллокации
Этот трюк широко известен в задачах interval scheduling и timeline merging, но в финансовых задачах FIFO он почему-то редко используется явно. А именно здесь от него больше всего пользы: один и тот же SQL обслуживает вырожденные платежи из 1 бакета и 1 траты, а также сложные из десятков бакетов и десятков трат, без if/else.
Полный SQL-запрос в упрощённом виде, без технических полей витрины:
-- Шаг 0: подготовка стороны начислений, собираем бакеты WITH accrual_buckets AS ( SELECT payin_ext, accrual_id, accrual_microcat, SUM(accrual_amount) AS bucket_amount FROM raw_accruals GROUP BY payin_ext, accrual_id, accrual_microcat ), -- Накопительная сумма на стороне начислений accruals_cum AS ( SELECT a.*, SUM(bucket_amount) OVER ( PARTITION BY payin_ext ORDER BY accrual_id, accrual_microcat ROWS UNBOUNDED PRECEDING ) AS acc_cum_end, SUM(bucket_amount) OVER ( PARTITION BY payin_ext ORDER BY accrual_id, accrual_microcat ROWS UNBOUNDED PRECEDING ) - bucket_amount AS acc_cum_start FROM accrual_buckets a ), -- Шаг 0b: подготовка стороны списаний через UNION ALL трат и сгораний consumption AS ( SELECT payin_ext, writeoff_date, writeoff_purchase, ..., writeoff_amount, FALSE AS is_burn FROM writeoffs UNION ALL SELECT payin_ext, burn_date AS writeoff_date, 'burn' AS writeoff_purchase, ..., burn_amount AS writeoff_amount, TRUE AS is_burn FROM burns ), -- Накопительная сумма на стороне списаний consumption_cum AS ( SELECT c.*, SUM(writeoff_amount) OVER ( PARTITION BY payin_ext ORDER BY writeoff_date, writeoff_purchase, ... ROWS UNBOUNDED PRECEDING ) AS w_cum_end, SUM(writeoff_amount) OVER ( PARTITION BY payin_ext ORDER BY writeoff_date, writeoff_purchase, ... ROWS UNBOUNDED PRECEDING ) - writeoff_amount AS w_cum_start FROM consumption c ) -- Сердце алгоритма: interval overlap join + длина пересечения SELECT a.payin_ext, a.accrual_id, a.accrual_microcat, c.writeoff_date, c.writeoff_purchase, ..., GREATEST(0, LEAST(a.acc_cum_end, c.w_cum_end) - GREATEST(a.acc_cum_start, c.w_cum_start) ) AS allocated_amount FROM accruals_cum a JOIN consumption_cum c ON c.payin_ext = a.payin_ext AND c.w_cum_start < a.acc_cum_end AND c.w_cum_end > a.acc_cum_start;
Несмотря на формальный вид «N×M», декартов взрыв не случается: условие w_cum_start < acc_cum_end AND w_cum_end > acc_cum_start чрезвычайно селективно на отсортированных интервалах. Каждая трата пересекается обычно с одним или двумя бакетами начисления, и движок это учитывает.
Мы обошлись без процедурного кода и курсора, поскольку сложность алгоритма линейная по числу пар (на практике O(N log N) с учётом сортировок window-функций).
Где ещё можно использовать подход
Cumulative sum + interval overlap join — это общая идея, не привязанная к бонусам. Например, я уже видел несколько подобных задач:
— Распределение оплат по нескольким счетам: те же интервалы, тот же overlap join.
— LIFO-партии: те же интервалы, обратный порядок ORDER BY в накопительной сумме.
— Налоговые партии (FIFO inventory) в учёте товаров: буквально из учебников бухучёта, но впервые сформулированные как чистый SQL и сразу с поддержкой внутренней разбивки партии.
— Страховые требования с разбивкой по видам ущерба, взаиморасчёты между сервисами с разнесением по статьям, развёрстка авансовых платежей по позициям договора.
Любая задача формата «M входящих событий закрыли N исходящих с разделением на доли», в которой сама сущность тоже разбита на подкатегории, это кандидат на такой паттерн.
Где ломается наивный SUM в гранулярной витрине
Витрина-результат имеет составной ключ:
payin_ext × accrual_microcat × writeoff_microcat × flow_type
Расшифровка: id платежа, микрокатегория со стороны начисления, микрокатегория со стороны траты, тип потока (writeoff, burn, accrual). Каждая строка — одна пара из бакета начисления и траты с аллокацией. Всё аккуратно и разнесено по бухгалтерским разрезам.
И здесь начинается подвох. Каждый бакет начисления повторяется в нескольких строках одного платежа по числу трат, которые его съели. Поле accrual_amount (сумма бакета) в этих строках одинаковое. Любой потребитель, пишущий SUM(accrual_amount) GROUP BY payin_ext, получит сумму, кратную числу строк. Цифры в отчёте растут в разы, при этом никакой ошибки в SQL формально нет, отчего баг очень тяжело заметить.
Поэтому витрина защищается от наивного потребителя: в каждой строке есть предсчитанные tot_accrual_by_payin, tot_writeoff_by_payin, tot_burn_by_payin. Это настоящие суммы платежа, одинаковые во всех строках. Правильный паттерн потребителя — это any_value:
SELECT payin_ext, any_value(tot_accrual_by_payin) AS accrued, any_value(tot_writeoff_by_payin) AS spent, any_value(tot_burn_by_payin) AS burned FROM bonus_flows_fifo_subcat WHERE constant = 1 GROUP BY payin_ext;
Если потребителю нужна разбивка по выручке или подкатегориям, он использует amount_flow. Это сумма конкретной аллокации, которая привязана к паре бакет ↔ траты и не удваивается.
Главное правило проектирования FIFO-витрин: правильные суммы должно быть невозможно посчитать неправильно. Предсчитанные tot_*_by_payin + any_value проще и безопаснее, чем DISTINCT-фильтрация или сложные оконные функции на стороне потребителя.
Как защищаем витрину от балансового расхождения из-за лагов
Бонус закрыт, когда он целиком исчерпан: accrued = spent + burned. Казалось бы, это можно проверять по дате expire: срок истёк, бонус закрыт, но практика показала, что так делать нельзя.
У любой витрины есть лаг, когда срок жизни закончился, но событие сгорания ещё не доехало в DWH. Такой бонус по дате формально закрыт, но баланс не сошёлся и если строить отчёт по expire_date < today, мы будем считать живые бонусы закрытыми и получим расхождения.
Мы решили эту задачу с помощью балансового фильтра одной строкой:
WHERE abs(accrued - spent - burned) < 0.01
Этот фильтр одновременно:
— отсекает живые бонусы (для них spent + burned < accrued);
— защищает от лагов: если для запоздавших burn-событий баланс не сошёлся, они тоже отсеются.
В наших данных это даёт около 98% сходимости на бонусах, закрытых по сроку, и 100% на досрочно потраченных. Потерянные 2% это те самые, у которых сгорание ещё не доехало. Они автоматически вернутся в выборку, как только догрузится источник.
Граничные случаи и шрамы
📌 Смена источника на середине истории. В день, когда мы переезжали со старой модели на новую, исходные таблицы расщепились, и появился риск потерять или задвоить данные. Проблему решили оператором UNION ALL с фильтрами по дате: cut date разделяет периоды, после неё используется только новая модель.
📌 Поле «мигрированный флаг». Часть записей перенеслась из старой модели в новую. Их отсекаем фильтром, чтобы не задвоить с pre-cut периодом.
📌 Семантика поля hold_operation. До cut date это числовые id, а после — текстовые лейблы. Переписывать витрину ради унификации не стали, поэтому появилась публичная особенность модели — потребители разрешают её через справочник.
Что мы из этого вынесли
👉 У нас была задача учитывать бонусы строго в соответствии с историей начислений — раньше пришло → раньше ушло. Проблема в том, что на N начислений приходится M строк списаний, поэтому наивные способы подсчёта не сработали.
👉 Мы разобрались с задачей при помощи бакетирования. За единицу начисления взяли бакет из id начисления и микрокатегории, а траты оставили атомарными по одной строке.
👉 По дороге встретились с проблемой неверных подсчётов. Наивный SUM многократно умножал траты, поскольку бакет начислений списывался с каждой строки трат.
👉 Вторая проблема — алгоритм неверно подсчитывал пограничные бонусы, срок которых формально истёк, но данные до витрины ещё не добрались. Задачу решили с помощью балансового уравнения: WHERE abs(accrued - spent - burned) < 0.01. Также решили и другие проблемы: отсеяли живые бонусы и защитились от лагов.
👉 Итоговый паттерн — cumulative sum + interval overlap join — позволяет решать FIFO на миллионах строк без курсоров и процедурного кода.
Теперь мы правильно подсчитываем каждый бонус.
Аналитики Авито пишут много статей, а ещё ведут недушный Телеграм-канал «Коммуналка аналитиков» Подписывайтесь!
