![](https://webcf.waybackmachine.org/web/20220520013621/https://habrastorage.org/webt/vf/t0/sb/vft0sbwgcmwdvmwyqq4hl-vkfmi.jpeg)
Меня зовут Александр Горякин, и я работаю в отделе разработки систем для внешних заказчиков Tarantool. Очень часто мы сталкиваемся с весьма нетривиальными задачами, например с хранением графов. Расскажу об этом на примере создания системы по борьбе с мошенническими действиями для одного из заказчиков, очень крупного банка.
Постановка задачи
У банка много клиентов, которые каждый день, неделю, месяц и год выполняют транзакции: переводят средства с одного счёта на другой, будь то оплата услуг или товаров в магазине, переводят деньги родственникам, знакомым и рабочим.
Каждого клиента банка мы можем считать вершиной графа. Любая транзакция, которую выполнил пользователь — это ребро графа. Запись выглядит так:
{счёт1, счёт2, сумма, год, квартал}
, где:счёт 1
— это исходный счёт, с которого мы переводим средства;счёт 2
— целевой счёт;сумма
— переведённые деньги;год
иквартал
— для идентификации записи.
Сначала заказчик предоставил нам список всех транзакций за год, однако по условиям задачи нужно было хранить данные за пять лет. Это колоссальный объём данных, записей в подобном графе примерно 5 млрд. — это 10 млн. вершин, которые занимают 2 ТБ. Удержать столько в оперативной памяти очень сложно, и искать в таком массиве данных тоже довольно тяжело. А ведь наша цель — поиск клиентов, выполняющих мошеннические операции. Поэтому нам нужно было создать систему, которая может хранить рёбра графа и выполнять запросы по индексу и по графовому поиску.
Клиент хотел выполнять запросы трёх видов — связи:
- первого порядка (1->2);
- второго порядка (1->2->3);
- третьего порядка(1->2->3->4).
Виды запросов
Связи первого порядка — это сами транзакции: перевели кому-то деньги. Их мы можем искать по индексу: нам известен исходный и целевой счёт, а также время (год и квартал), когда была проведена операция. Сумма нас не интересует.
Связи второго порядка — это когда в транзакции участвует один посредник. Например, вы хотите перевести деньги работнику, но его контактов у вас нет, и вы переводите деньги кому-то, у кого есть эти контакты — родственнику или знакомому, — а тот пересылает деньги нужному человеку. Для таких связей применяется простейший графовый поиск.
Поиск связей третьего порядка — самый сложный алгоритм, потому что он представляет собой поиск в графе с путём длиной в три перехода. Когда могут проводиться такие операции? Например, мошенники хотят вывести деньги с чьего-то счёта на свой через промежуточные счета. Но при этом им нужно использовать как можно меньше промежуточных счетов, так как за каждый перевод берётся комиссия, особенно если сумма большая.
![](https://webcf.waybackmachine.org/web/20220520013621/https://habrastorage.org/webt/nm/cr/sp/nmcrspa5uznlgxkxrlotmot8nho.png)
Выбор инструмента для реализации
Основной сложностью были требования заказчика. Мы должны были уложиться в ограничения:
- Полная холодная загрузка данных — не более 7 часов.
- При поиске связей первого и второго порядка система должна выдерживать нагрузку до 3 тыс. транзакций в секунду. Под транзакциями подразумеваются не внутренние операции, которые выполняются в системе, а бизнес-транзакции по переводу средств.
- В случае графового поиска мы должны были уложиться в SLA 10 тыс. запросов в секунду.
Исходя из поставленной задачи и требований возникает вопрос: а есть ли готовые решения и почему бы ими не воспользоваться? Такие действительно есть — это графовые базы данных Arango DB, Titan и Neo4J. Есть и различные системы обработки графов, например, Pregel, в том числе реализованный на Lua. Кроме специализированных решений можно использовать для хранения графов реляционные файловые базы данных.
Однако у всех этих решений есть свои недостатки. Например, мы не могли использовать в нашем проекте графовые базы данных, так как необходимо было импортозамещение, к тому же у Arango DB, Titan и Neo4J нет русскоязычной поддержки. Некоторые базы данных могут хранить только вершины, а нам нужны были ещё и рёбра. Не все хранят метаинформацию, которая необходима для поиска по индексу. Кроме того, у каждой графовой базы собственный язык запросов: у Arango DB — SQL, у Neo4J — Cypher, у Titan — Gremlin. Каждый язык запросов накладывает свои ограничения на реализацию алгоритмов графового поиска. Скажем, у Titan нет своего хранилища, вместо него он использует Cassandra или Hadoop (является файловой базой данных).
Мы не стали использовать Pregel, потому что он не умеет выполнять запросы по индексам. И если бы мы использовали Lua-реализацию, которая специфична для Tarantool, то она упёрлась бы в ограничение виртуальной машины Lua, то есть работала бы очень медленно. Реляционные файловые базы тоже работали бы очень медленно, потому что в них данных хранятся на диске. К тому же запросы на графовый поиск очень сложные. Вот пример SQL-запроса на поиск связи второго порядка:
SELECT DISTINCT Entity.id
FROM Entity AS X
JOIN R1 AS R1_X ON Entity.id = R1_X.source JOIN Entity AS A ON A.id = R1_X.target JOIN R1 AS R1_A ON A.id = R1_A.source JOIN R2 AS R2_A ON A.id = R2_A.source
JOIN R3 AS R3_A ON A.id = R3_A.source JOIN Entity AS A1 ON R1_A.target = A1.id JOIN Entity AS A2 ON R2_A.target = A2.id JOIN Entity AS A3 ON R3_A.target = A3.id
JOIN R2 AS R2_X ON Entity.id = R2_X.source JOIN Entity AS B ON B.id = R2_X.target JOIN R2 AS R2_B ON B.id = R2_B.source JOIN R3 AS R3_B ON B.id = R3_B.source
JOIN R4 AS R4_B ON B.id = R4_B.source JOIN Entity AS B2 ON R2_B.target = B2.id JOIN Entity AS B3 ON R3_B.target = B3.id JOIN Entity AS B4 ON R4_B.target = B4.id
JOIN R3 AS R3_X ON Entity.id = R3_X.source JOIN Entity AS C ON C.id = R3_X.target JOIN R3 AS R3_C ON C.id = R3_C.source JOIN R4 AS R4_C ON C.id = R4_C.source
JOIN R5 AS R5_C ON C.id = R5_C.source JOIN Entity AS C3 ON R3_C.target = C3.id JOIN Entity AS C4 ON R4_C.target = C4.id JOIN Entity AS C5 ON R5_C.target = C5.id
WHERE
Entity.attr1 = val1 AND Entity.attr2 = val2 AND Entity.attr3 = val3 AND A.attr1 = val4 AND A.attr2 = val5 AND A.attr3 = val6 AND
A1.attr1 = valA AND A2.attr2 = valB AND A3.attr3 = valC AND B.attr1 = val7 AND B.attr2 = val8 AND B.attr3 = val9 AND
B2.attr1 = valA AND B3.attr2 = valB AND B4.attr3 = valC AND C.attr1 = val10 AND C.attr2 = val11 AND C.attr3 = val12 AND
C3.attr1 = valA AND C4.attr2 = valB AND C5.attr3 = valC
Здесь 24 join’а и 21 условие фильтрации. Этот запрос сложно написать и сложно читать, он просто огромный. Изначально у заказчика все данные хранились в Hadoop, запросы на поиск выполнялись через Hive, и на переброску по сети уходило очень много времени и ресурсов. Tarantool этих недостатков лишён.
В результате для хранения графов мы выбрали Tarantool. Одно из его главных преимуществ: мы умеем с ним работать, знаем, как посчитать необходимое количество экземпляров, как правильно их конфигурировать. Кроме того, в Tarantool очень хорошо работает поиск по первичному и вторичному индексу. Если важна производительность, то можно реализовать модули сколь угодно сложных алгоритмов графового поиска на компилируемом языке, например, на С — Tarantool написан на нём с использованием виртуальной машины Lua.
Загрузка и хранение данных
Переданный нам заказчиком один большой граф мы смогли разделить на много мелких, чтобы оптимально шардировать данные и распараллелить обработку. Мы смогли это сделать благодаря тому, что Tarantool позволяет шардировать под конкретные нагрузки. И в результате удалось использовать более эффективную репликацию.
![](https://webcf.waybackmachine.org/web/20220520013621/https://habrastorage.org/webt/ey/gf/rk/eygfrkghw87pdujf7zbyy8mah20.png)
Данные нам передали в формате ORC, а Tarantool из коробки не умеет с ним работать. Поэтому мы написали на Go импортёр на основе существующей библиотеки. Выбирали только необходимые нам поля:
счёт 1
, счёт 2
, год
, квартал
и сумму
, а затем импортировали. И поскольку нам передали информацию за год, а заказчик хотел за пять лет, пришлось данные размножить. Весь получившийся объём мы загрузили не за 7 часов, как это происходит у заказчика с Hadoop, а за час.Данные мы храним не в одном экземпляре Tarantool, а в кластере, созданном с помощью фреймворка Tarantool Cartridge. У Tarantool есть несколько видов экземпляров: роутеры, маршрутизаторы и хранилища. Роутеры маршрутизируют запросы к хранилищам. Хранилища — это наборы реплик (replica set), в каждом из которых есть один мастер и несколько реплик.
Изучив данные, мы увидели, что у них есть общие поля —
год
и квартал
. Нам показалось логичным шардировать именно по ним. В нашем случае каждый шард — это квартал определённого года. Для поиска связей первого порядка мы сделали первичный индекс по полям счёт 1
, счёт 2
, год
и квартал
, так как этот индекс удовлетворяет всем нашим требованиям к поиску. А для реализации графового поиска мы сделали вторичный индекс по полям счёт 2
, год
и квартал
.Как я уже говорил, мы повысили гибкость репликации: больше запросов и больше реплик. Изучив данные, мы поняли, что больше обращений будет к более свежим данным (за прошедший год), потому что эти транзакции актуальнее и важнее для нас. Поэтому для их хранения мы увеличили количество реплик в наборах. Таким образом мы повысили скорость обработки и отказоустойчивость системы. Даже если упадёт мастер, запросы пойдут на реплику и мы всё равно сможем прочитать данные.
Алгоритмы поиска
В одном кластере Tarantool у нас хранится 10 млн. узлов и 5 млрд. записей. Сначала мы сформировали распределение по степеням вершин по всему набору данных. Степени вершин — это количество транзакций, выполненных с текущего счёта, то есть исходящие связи. Оказалось, что у нас есть вершины, из которых выходит от 100 тыс. до миллиона связей, и если мы будем перебирать наивным поиском в ширину, то это займёт очень много времени. Потому мы отказались от этого алгоритма.
![](https://webcf.waybackmachine.org/web/20220520013621/https://habrastorage.org/webt/og/49/w5/og49w5mh_q7wuhi6x99blaaxene.png)
Стали искать другой способ и пришли к такому решению:
![](https://webcf.waybackmachine.org/web/20220520013621/https://habrastorage.org/webt/ei/xk/uc/eixkuc5zcv8tfbzxkwsefvprty0.png)
У нас есть первичные и вторичные индексы. С помощью первичного индекса мы ищем все вершины — транзакции, — которые выполнялись с исходного счёта на какой-нибудь другой счёт, связанный с какими-то вершинами — назовём это множество Вершины 1. Пусть его мощность будет N. Также у нас есть вторичный индекс, который позволяет найти все вершины, из которых транзакции приходили на целевой счёт — назовем это множество Вершины 2. Пусть его мощность будет К.
Два шага пути нами сделано, осталось найти только связку между этими двумя множествами. Перебираем N*K пар из Вершины 1 и Вершины 2, так мы ищем связи между этими двумя множествами, тем самым сильно уменьшая количество вершин, которые нам нужно перебрать, и увеличивая скорость работы алгоритма.
Поиск связей второго порядка работает примерно так же, но немного проще: с помощью первичного индекса ищем все вершины, которые связаны с исходным счётом, а с помощью вторичного — все вершины, которые связаны с целевым счётом, и потом ищем пересечение этих двух множеств. То есть все вершины, которые есть в множествах Вершины 1 и Вершины 2 являются посредниками в транзакции.
Алгоритмы графового поиска мы реализовали тремя разными способами на Lua, SQL и С. Оставалось только выбрать самый эффективный из них.
Сравнение производительности
Для сравнения мы выбрали самый простой запрос — поиск связей первого порядка.
![](https://webcf.waybackmachine.org/web/20220520013621/https://habrastorage.org/webt/um/5n/r-/um5nr-k5bsgmyeu-valabzl4ylu.png)
Хуже всех себя показал Lua, а у SQL в Tarantool есть одна особенность: он работает только в рамках одного экземпляра и не умеет выполнять кластерные запросы. Так что мы выбрали решение на С. Но и у него обнаружился один недостаток: сложность реализации. Наш алгоритм графового поиска получился очень громоздкий и сложный в написании. Тогда мы стали искать, каким компилируемым языком можно заменить С, чтобы сохранить производительность, но написать меньше кода. Выбрали Rust, на нём хранимые процедуры получились меньше где-то в пять раз. Скомпилировали модули и подключили их в Tarantool так же, как и модули на С. Производительность получилась почти такой же.
Результаты
Мы не просто учли требования заказчика, нам удалось их превзойти: данные загружаются в семь раз быстрее, при поиске связей первого и второго порядка обрабатывается уже на 30% больше транзакций в секунду, а в запросах графового поиска — на 80% больше. Даже если случайно заставить Tarantool обработать распределение с 1 миллионом связей, он с этим справится и не упадёт.
Хранить графы в Tarantool возможно, но делать это можно только в том случае, если вы изучили данные и знаете, как их можно шардировать, чтобы распараллелить обработку, Tarantool в этом отношении гибкий инструмент. Если для вас критична производительность или вам нужно реализовать какой-то сложный алгоритм, можете воспользоваться компилируемыми языками, например, С или Rust, для написания более эффективного кода. Причём Rust позволяет сделать это проще и с сохранением производительности.
Скачать Tarantool можно на официальном сайте, а получить помощь — в Telegram-чате.