Жук, нумерология, хеш или ничо? Оптимизация работы с путями
Привет, Хабр! Меня зовут Евгений Кузьмин, я Java‑разработчик в CDEK. Надеюсь, все знают, что это за компания и чем занимается. Давайте представим, что вам нужно отправить посылку с гостинцами родственнику в Москву из Новосибирска. Вы приходите в ближайший пункт приёма посылок и оформляете услугу доставки. Что же происходит дальше? Казалось бы, всё очевидно: посылка сразу летит или едет из Новосибирска в Москву. Но всё не так просто… Думаю, все согласятся, что не рационально гнать отдельную фуру с одной коробочкой для каждого заказа. Наша задача выстроить логистику таким образом, чтобы по пути загрузить и выгрузить как можно больше посылок и поехать дальше. В этой статье я поделюсь с своим опытом оптимизации задачи по редактированию и поддержке в актуальном состоянии огромного количества данных типа «куда направить товар». Классическая задача программирования на практике логистики. При этом мы не будем выходить за рамки стандартного стека Java Springboot и Postgres. Статья будет интересна разработчикам (от джуна до сеньора), которым будет интересно погрузиться в трудовые будни разработчика в сфере транспортной логистики.
Оглавление
О системе
Прежде чем перейти непосредственно к оптимизации, необходимо погрузиться в нюансы системы.
Строим пути из всех пунктов во все
Чтобы клиент смог отправить посылку в любой пункт системы, мы строим пути из всех пунктов во все.
Соответственно, для 3 пунктов имеем 6 направлений: A→B, A→C, B→A, B→C, C→A, C→B, для 10 — 90, для 10 000 — 99 990 000. Кол‑во направлений = N * N — N, где N — количество пунктов. Лучше всего представить данные в виде матрицы.
Матрица для тарифа ЭКСПРЕСС (доставка быстрее, чем ЭКОНОМ). До Новосибирска летим прямиком! Да чтоб побыстрее!
Оперативно реагируем на изменения
Например, из‑за снегопада закрылась трасса M-11, и нужно выстроить логистику по другим путям. Или открывается новый крупный склад, который будет сортировочным центром для всего Кавказа. Соответственно, необходимо как можно быстрее изменить тысячи направлений.
Держим данные в согласованном виде
Если меняем путь до основного пункта, например, до Москвы, то нужно перестроить пути и до Подмосковья.
«СЛОЖНА»
Если поменяли логистику до Москвы из Новосибирска, то до Звенигорода, Обнинска и Зеленограда — тоже. А если затронут Зеленоград, то и до Алабушево нужно поменять. Грубо говоря, один пункт может «наследоваться» от другого.
Как соблюсти все три условия? (волнительная музыка на заднем фоне тададам)
Как было раньше
До определённого момента прекрасно работал лёгкий и понятный способ: задачи на изменение вставали в очередь и только один поток обрабатывал их, чтобы параллельные потоки друг другу чего не попортили и дедлоки лукавые не насоздавали.
«Blurred» дедлок
К тому же любое изменение вызывало перерасчёт всего столбца матрицы, чтобы зависимые направления были полностью перестроены.
Но в какой‑то момент любое изменение данных стало 8 часов ждать своей очереди. Нехорошо!
Что предприняли
Сначала мы с командой привели архитектуру к строгой луковке и DDD. Здесь особо останавливаться не буду. Скажу только, что управлять более 50 use‑case стало возможным. Грубо говоря, сделали рефакторинг. Если вдруг будет кому интересно — пишите, вынесу в отдельную статью.
Потом я приступил к оптимизации. Сначала сделал так, чтобы каждый сценарий работал только со своей двумерной матрицей или в разрезе своего тарифа. Например, для изменения 5 000 направлений с тарифом «Эконом» и 5 000 с тарифом «Экспресс» начали создаваться 2 операции. Итого на бумажке ускоряем расчёт в N раз, где N — количество тарифов. Образно можно представить, что на картинке ниже все советчики взяли лопаты и принялись тоже копать =)
Далее подумал: «А зачем пересчитывать весь столбец матрицы на каждый чих? Будем изменять только нужные объекты!» И тут мне встретилась проблема декартового произведения.
Собственно, проблема
Проблема состоит в том, что изменения в основном идут по тройке ПУНКТ ОТКУДА + ПУНКТ КУДА + ТАРИФ. Клиент не знает UUID объектов. И если в какой‑то момент редактируется 10 тысяч направлений, то при стандартном запросе к БД через оператор IN для ПУНКТА ОТКУДА и ПУНКТА КУДА where node_from in ( вернётся уже около 10 млн строк (количество node_from * количество node_to)! Карл, а нам нужно было всего 10 тысяч. Память в JVM не резиновая…
И тут я понял ещё одну хитрость предыдущего решения: всегда был только один ПУНКТ ОТКУДА или ПУНКТ КУДА в одной операции. И из БД доставались только нужные направления.
Пути решения
Но пути назад уже не было! Благо у нас в команде есть JOOQ (это я про технологию, если что) и из коробки можно писать множественный выбор where (node_from,node_to,tariff) = ( Но с нагрузкой на тесте что‑то пошло не так.
Далее попробовал сжать три поля (ПУНКТ ОТКУДА, ПУНКТ КУДА, ТАРИФ) в одно, по которому будет быстрый поиск. Выбор пал на хеш‑функцию. По тройке формируем неизменяемые хешы и в БД ищем по ним нужные строки. Да‑да, знаю, такое себе — в БД хранить хеш‑функцию, которая может меняться между версиями Java. Но допустим, мы люди консервативные и новомодные хеш‑функции использовать не будем. Останемся навсегда (ох уж это «всегда») на хеш‑функции 17/37.
Итого: запрос по 10 тысяч направлений конвертируется в 10 тысяч чисел, и с ними уже идём в БД. Но тут проницательный читатель заметит, что у хеш‑функции бывают коллизии из‑за ограниченности разрядности числового типа. И снова не беда! Отфильтруем полученную выборку из БД. Разок пробежаться по входящему списку не жалко =)
Хоть предыдущий вариант и был интересным, времени на задачу катастрофически не хватало, поэтому выбрал быстрый способ: делим редактируемые направления на батчи, чтобы произведение количества ПУНКТОВ ОТКУДА на количество ПУНКТОВ КУДА не было больше 1000. Это чисто эмпирическое число: несколько раз пробовал другие, но это показалось мне самым красивым, да и нумерология не против (дичькакаято). В итоге каждый батч достаёт терпимое количество лишних данных, которые благополучно фильтруются на стороне Java.
Практика — критерий истины
А теперь проверим, что я вам тут написал. Вспомним проблему: как по большому количеству троек ПУНКТ ОТКУДА + ПУНКТ КУДА + ТАРИФ эффективно доставать данные из БД. Появились четыре метода решения:
С помощью JOOQ, где много блоков where. Назовём его «Жук».
Конвертируем тройку в хеш‑функцию и ищем в БД. Дадим ему название «Хеш».
Батчи с магическим числом 1000. Позывной — «Нумерология» («Нум»). Зачем бороться с декартовым произведением, когда можно дружить.
Ничего не бить на батчи. Достаём по обычному where всё декартово произведение — позывной «Ничо».
Вспомним биологию за 7 класс и посмотрим на табличку запусков:
Метод | Количество входных параметров | Время | Лишние данные |
Жук | 10 000 | 15 с | - |
Жук | 100 000 | 1 м 31 с | - |
Жук | 1 000 000 | 10 м 3 с | - |
Нум | 10 000 | 1 м 3 с | 312 903 |
Нум | 100 000 | 10 м 31 с | 17 129 108 |
Хеш | 10 000 | 6 с | 59 |
Хеш | 100 000 | 18 с | 574 |
Хеш | 1 000 000 | 1 м 26 с | 5 242 |
Ничо | 10 000 | 4 м 41 с | 7 684 134 |
Количество входных параметров — это сколько троек (ПУНКТ ОТКУДА, ПУНКТ КУДА и ТАРИФ) нужно найти в БД;
Время — сколько отрабатывала операция по поиску;
Лишние данные — сколько лишних строк приложение достаёт из БД. То есть во входных параметрах нет такого запрашиваемого направления.
В итоге «Ничо» занимает последнюю строчку нашего ТОПа. Уже на 10 000 входных записей я устал ждать. Боюсь представить, что будет на 100 000. Да и лишних данных извлёк аж в 768 раз больше, чем было во входном списке. Жёстко!
На третьем месте — «Нумерология». Тут я немного расстроился, ведь этот метод лично реализовал и внедрил, а он оказался далеко не самым лучшим: и лишних данных много тащит, и работает не так быстро. Что ж, уповаю на то, что никто до этой части статьи не дочитает. Или же, как модно сейчас говорить, «это моя зона роста» (добавим +10 к софт скиллам).
«Жук» вырывается на вторую позицию. Не знаю, что у меня в тесте пошло не так с этим решением, но результаты показывают, что это быстрое и практичное решение. Почти не требует доработки. В 10 раз быстрее «Нумерологии».
Как и ожидалось, «Хеш» занял первое место. Лишних данных извлекалось немного, и это говорит, что доля коллизий невелика. И время на порядок быстрее, чем у «Жука».
З.Ы. Помню, что Postgres кеширует страницы, поэтому на каждый прогон выбирались случайные входные данные из 25 млн тестовых направлений. Память и потребляемые ресурсы процессора на каждом запуске одинаковые: 1024 Мb и 1 CPU соответственно.
Резюме
Хотя решение с разбивкой на батчи и не самое оптимальное, и проблема с доставанием лишних данных не ушла, но зато память не заканчивается, когда на батчи вообще не бьём. В итоге после всех действий ожидание задачи в очереди снизилось с почти 8 часов до 7 минут. Результат неплохой! Но нужно помнить, что при развитии системы в будущем снова придётся сюда возвращаться и уже серьёзно решать проблему извлечения лишних данных. Кто знает, может и решение с хранением хеш-кода в БД подойдёт. А может, нужно будет уйти в сторону нереляционной базы данных. Пишите, пожалуйста, что вы думаете о задаче такого рода и как вам статья?
