Comments 37
Шаг 1. Оптимизировать выражения.
Например, у вас куча условий по акциям, и, где-то в конце списка условий стоит наличие какого-то товара в корзине.
Если начать проверку условий с проверки этого товара, то остальные условия можно не проверять.
Это экономит время на бесполезной работе.
Шаг 2. Масштабирование / слияние выражений:
Предположим, у вас большая часть акций связана с наличием определенного товара.
Создаем таблицу товар->акции.
Пробиваем все товары из корзины по таблице в первую очередь.
Отправляем на дальнейшую обработку только акции из правой части таблицы.
Таким образом, мы за одну операцию проверили сразу все условия на "наличие товара" во всех акциях.
Шаг 3. Пишем свой оптимизатор
Автоматизация процесса на шаге 2.
Пишем свой собственный автоматический оптимизатор выражений / на основе статистики запросов.
Шаг 4. Компиляция в машинный код.
Например, средствами LLVM.
....
Имеем свой собственный оптимизирующий JIT компилятор DSL.
Это всё конечно замечательно, но мне кажется 99.9% перфоманса тратится на этапе микросервисы, бд, отправка джсонов...
И как вообще изменили DSL если требованием было не менять то что видит пользователь? Что он видит в итоге? И почему это не обычное выражение, а совершенно неудобное нечто в джсоне?
a == 5
типа сложнее распарсить чем
$eq {
type: int
value: 5
,
'a'
}
?
Не стоит смотреть на практическую сторону вопроса! Адепты оптимизации оптимизируют ради оптимизации, и, ни для чего больше!
На практике, с точки зрения экономической целесообразности про этот микросервис можно забыть до тех пор, пока нагрузка на него не вырастет раз в 10-100.
Если вы имели ввиду процесс настройки акций и под пользователем подразумевался пользователь админ-панели, то для этого используется адаптер. Клиенты для которых считаются скидки ничего не знают о DSL. Вот фрагмент из статьи по этому поводу:
Было принято решение спроектировать его с нуля, при этом написав адаптер, чтобы условия в БД продолжали храниться в старом формате и в админ-панели не пришлось ничего дорабатывать.
Насчет JSON, тут дело вкуса, можно конечно оптимизировать формат для более быстрого парсинга, но это того не стоит (на мой взгляд), парсинг DSL происходит только на моменте вставки или обновления акции (а это происходит относительно нечасто, и в данный момент с этим нет проблем). JSON естественный для JS формат, к тому же, у нас не чистый JS, а TypeScript и хотелось бы иметь типизацию. "Голую" строку же, почти невозможно типизировать средствами TS.
Вопрос в том почему просто не отправлять в префиксной форме записанное выражение
= + 5 a b
во-первых это понятно, во вторых упрощает парсинг, в третьих меньше строка, формировать запрос тоже вероятно легче, передавать в джсоне или нет - уже ваше дело
Так как скорость парсинга вряд ли станет узким местом (в нашем случае), то я это расцениваю просто как формат передачи данных и я выбрал тот формат который был мне ближе и удобнее (не исключено, что старая реализация оставила неизгладимый след в моей голове). Но вариант с префиксной нотацией хорош
Полностью согласен. Типичный пример подхода "я знаю плюсы, поэтому оптимизировать будем переписав на плюсах" )) Не поверю никогда, что затык был в вычислениях, при условии доступности локально данных. Даже если так, надо смотреть в каком там виде акции хранятся. 99% там были тормоза из-за БД и возможно, из-за сети. Плюс еще и монга медленная... (Не знаю как она на in memory, по мне так это экзотика какая-то. Но у меня она проигрывает как на выборке, так и на вставке обычному пострес. Без крайней необходимости её фичей я бы не стал использовать)
На месте автора, я бы монгу выкинул, а дальше думал бы в сторону "выбрать всё акции при старте приложения, и дальше просто обновлять их именно поллингом, т к это наиболее просто и они, как и сказал сам автор, не задействуются моментально. Это бы убрало 90% проблем. Дальше можно, как тут предлагают, посмотреть что там накрутили с движком правил. Что-то мне подсказывает, что надо банально взять уже имеющийся готовый движок правил (кстати, вот он то может быть на любом языке, т к этот код будет поддерживать другая организация, и соответственно проблем будет в разы меньше)
Никакого раста, и уж тем более упаси вселенная, плюсов для этой задачи внедрять бы не стал. Я на 99% уверен, что движок V8 не сильно проиграет плюсам на обработке данных, которая полна условных переходов и кэш проца не будет эффективно работать в обоих вариантах: в V8 т к это jit, а в плюсах из-за самой задачи. Уверен, можно было ускорить пусть не в 500, но в 200-300 раз, чего было бы достаточно, и без возни с ещё одним, да ещё и низкоуровневым языком. Перфекционизм автора понимаю, но одобрить не могу. Если я был бы в качестве тим-лида или архитектора, идею переписать на плюсах зарубил бы.
Моё впечатление: Современная ИТ-индустрии, упрощая одни вещи, позволяет слишком переусложнить на ровном месте другие. Тут ещё надо сказать спасибо и "мудрецам", которые на js придумали делать серверные приложения.... Что-то из разряда: "А давайте на пыхе напишем 3Д-шутер" )) Не, как-бы можно наверное, но зачем? )
+1, этому подходу лет дцать, что только люди не выдумают, лишь бы Lisp не использовать.
Вся эта история с булевыми выражениями очень похожа на NP-полную задачу B-SAT, но как минимум можно попробовать применить Bloom-фильтр.
Тут вам DNF в помощь. SAT для выражений в DNF решается за линейное время. Плюс, DNF упрощает реализацию оптимизатора.
При локальном замере производительности, использование Docker-контейнера замедляет приложение примерно в 4-5 раз.
Вы уже ускорили сервис с 500 мс до нуля. В 4-5 раз больше, чем ноль - это ноль. Так что все оптимизации бессмысленны.
Вы пишете: Все наши сервисы запускаются в виде Docker-контейнеров, скидочный сервис не стал исключением. Дополнительный слой виртуализации имеет свою цену. При локальном замере производительности, использование Docker-контейнера замедляет приложение примерно в 4-5 раз.
А с чем связано это?
Быть может нужна более тонкая настройка докер контейнеров по cpu / ram?
Замеры производились локально, ограничений по CPU/RAM у него не было, это первое, что я проверил. С чем это в действительности связано - не знаю. Если найду время, то попробую предоставить больше деталей.
А можете поделиться, на какой системе тестировали? Вполне представляю себе такие просадки на macos с docker desktop для i/o
Не поверите, но все так. Это какие то известные проблемы с версией docker desktop под macOS?
Деталей я не знаю, я не настоящий сварщик.
Я docker desktop воспринимаю как настроенную до уровня магии linux виртуалку и красивый gui к ней. Нужно учитывать, что запросы пойдут через сетевой стек macos, потом гипервизора, linux-а и ещё и сеть докера. Даже есть сеть паравиртуализована, это всё равно не бесплатно и получается много слоёв. Аналогичные проблемы есть и с volume mount-ами.
Для тестов и разработки подойдёт, а для замеров производительности такой сетап не выглядит репрезентативным.
Я сначала не понял откуда у вас взялась виртуализация, вместо контейнеризации, но наличие macos всё объяснило. Так-то у докера практически нулевой оверхед
machdep.cpu.brand_string: Intel(R) Core(TM) i9-9880H CPU @ 2.30GHz
Версию ядра на момент замеров не могу точно сказать (это было достаточно давно), скорее всего 10.12.
Сейчас понимаю, что возможно не стоило добавлять этот пункт в статью (как минимум мне следовало указать спецификацию машины на которой выполнялись замеры). Но снижение производительности (RPS) было стабильным, в 4-5 раз, эта стабильность меня и смутила, возможно дело было как раз таки в моем специфичном (на то время) сетапе.
Чуть не забыл ответить! Нет, почему же, пункт хороший. Я думал речь о линуксовом хосте. Apple наверняка какие-то патчи добавляла от процессорных уязвимостей и, смело предположу, что в ядре Linux над ними потратили за последние года больше времени ради оптимизации. То есть патчи сами чуть медленнее. Значит Docker запускается в виртуальной машине, тогда накладные расходы еще выше. Учитывая упор на I/O, то тут сходятся все звезды, чтобы оно было как можно медленнее -- из-за постоянного context switching из гостевой системы в хост ради I/O и обратно.
Вот вам январь 2018 г., сервера Fortnite под сотню игроков, высокая нагрузка по I/O сети. +120% по процу.
И, честно говоря, путеводителя по уязвимым / патченным на уровне железа поколений процов у меня нет. Одно ясно, Intel долго микроархитектуру не менял, а ради маркетинга названия сменял. И на каком уровне они таки патчили уязвимости на обновленных Skylake (6000) / Kaby Lake (7000) и иже с ними -- вообще не понятно.
Наконец-то статья не про Blazing Fast Rust ?
Словил пару флешбеков при прочтении ? Приятно видеть, что сервис живёт и развивается. Молодцы!
Если бы всё остальное тоже бы на C++ писали, или чём-то схожим по скорости (Rust, Go), то глядишь не понадобилось бы распиливать код на 150 микросервисов, что к тому же могло бы сильно сохранить накладные расходы на коммуникацию.
Очень бегло глянул на код и пара вопросов: почему много где используются 1) "голые" поинтеры, и 2) выражения типа а.в->с или а->в->с->d?
Это определяется внешними API или это такой дизайн автора? Если это авторский стиль такой, то некошерно.
Ну и главное. Очень зря автор ускорил эту штуку сразу в 500 раз. Надо было сейчас в 5, через квартал ещё в 5, потом еще в 5.. и потом еще в 4 - работы на целый год! Да и нечего начальство баловать. ;)
Если речь про иерархию узлов и
Visitor
, то голые указатели используются по дизайну, но их можно заменить наstd::shared_ptr
+std::enable_shared_from_this
расплатившись производительностью (точных чисел не назову, но замеры делал в свое время).Это упрощенный пример кода, чтобы не раздувать его лишними вспомогательными функциями которые не имеют отношения к сути, в реальном коде таких выражений
a->b->c
как правило нет.
А почему нельзя просчитать все варианты акций сразу же после внесения изменений о них в бд?
Потому что конечный результат зависит от состояния корзины, а это состояние неизвестно до запроса. Всевозможных состояний корзины огромное множество. Акции могут применяться совместно. Более того, результат применения одной акции может изменить дальнейший ход действий (решая одну подзадачу мы влияем на результаты еще не решенных), динамическое программирование тут не поможет (если намек был на него).
"Всевозможных состояний корзины огромное множество."
Теоретически да, но практически как? Может случиться что на практике состояние корзины можно определить заранее. И тогда, к примеру для 99% или 88% или 77% таких случаев просчитать все варианты акций, а для остальной экзотики уже считать иначе.
То есть создать типа "кеширование просчета акций" в зависимости от состояния корзины, и использовать эти данные из кеша и только при их отсутствии "считать по новой. "
В одной лишь позиции, находящейся в корзине более 15 параметров, на каждый из которых можно настроить условие. Да, какие-то корзины с течением времени будут повторяться, но при достаточно большом кол-ве sku такой кэш вряд-ли будет эффективен. Процент попадания в него будет ничтожен. 99% RAM будет израсходовано впустую (если ее вообще хватит).
Даже если представить, что у нас всего 1000 sku, максимальное кол-во каждого товара в корзине равно единице и всегда выбирается 5 позиций, то уже имеется C из 1000 по 5 = 8'250'291'250'200
вариантов выбора 5 позиций. Понятное дело что статистически большая часть из этих вариантов выбора никогда не случится, но даже этот простой пример дает понять размах всего множества состояний, поэтому как такое можно закэшировать я не понимаю.
Я зацепился взглядом за строку "В глаза сразу бросилось отсутствие кеширования."
Кеши бывают разные. Не всегда имеет смысл держать в кеши всё. Иногда достаточно держать "наиболее запрашивает данные", выполняя для запроса остальных обычные запросы.
"1 Периодические запросы в БД с целью отдать акции, время изменения которых (updatedAt) больше, ранее сохраненной временной метки
2. Слушать события изменения коллекции используя change streams"
Можно добавить и 3 - использовать снова кеш. При обычном запросе акций на инстансе скидочного сервиса на текущий день для какой либо корзины (запрос пришёл на расчёт скидок по акциям для товаров в корзине) идёт запрос к хосту(базе) акций через кеш, если в кеше нет акций на текущий день, то запрос дальше идёт к хосту (базе) акций и кеш заполняется акциями на текущий день а также из кеша удаляются акции за прошлый день (дни) .
Таким образом данные акций из кеша синхронизируются с удалённой базой акций.
Это простая реализация синхронизации. Если этот процесс занимает слишком много времени (неприемлемо для покупателя (покупателей), который оказался первым в этот день), то только в этом случае можно использовать, например, механизм запуска в отдельном потоке по времени, раз в сутки, функции на инстансе скидочного сервиса, которая заполняла бы кеш актуальными данными и убирала бы старые данные из этого кеша акций.
Введение такого кеширования позволяет отказаться от "узкого места" коррдинатора, про который вы упоминаете: "координатором более сложен в реализации. Не стоит забывать, что являясь единственным источником истины, он так же является единой точкой отказа."
Выше вы предлагали кэшировать посчитанные скидки для каждой корзины. Я описал, почему такой кэш при текущей вариативности будет не эффективен.
Теперь вы говорите про кеширование акций, они и так кешируются, в уже "разобранном" виде. Знать заранее какие акции потребуются невозможно, для этого надо посчитать их для конкретной корзины.
Акции меняются не часто, но чаще чем раз в сутки/час и желательно реагировать на изменения как можно быстрее. Если я вас правильно понял, то вы предлагаете вариант с "ленивой" первой инициализацией и последующими синхронизациями по истечению TTL, как в самом обычном кэше. В моем случае TTL будет небольшим, тянуть каждую минуту все акции по сети, выполнять парсинг и последующее полное обновление кэша не хотелось бы. Частичное обновление, с таким подходом, возможно только если ходить в БД на каждый N-ый запрос и смотреть акции которые изменились (чтобы не тянуть все). Вариант рабочий, но не без недостатков, кому то он может подойти больше в силу своей простоты.
Одним из главных недостатков в подходе который вы предлагаете, это то, что если во время синхронизации отдельных инстансов сервиса, произойдет изменение каких либо акций, то инстансы будут находиться в неконсистентном состоянии вплоть до следующей удачной синхронизации. В совокупности с большим TTL это не очень хорошо. В итоге результат расчета скидок будет зависеть от того, на какой инстанс "упадет" запрос.
"Выше вы предлагали кэшировать посчитанные скидки для каждой корзины. Я описал, почему такой кэш при текущей вариативности будет не эффективен."
Ок. Это мы выяснили. Там похоже нет места для кеша.
"Теперь вы говорите про кеширование акций, они и так кешируются, в уже "разобранном" виде. Знать заранее какие акции потребуются невозможно, для этого надо посчитать их для конкретной корзины. Акции меняются не часто, но чаще чем раз в сутки/час."
В статье вы писали что "К тому же большая часть акций создается заранее, со сроком начала действия указанным в будущем, к этому моменту состояние в рамках этих акций почти наверняка будет консистентным."
Я подумал что акция обычно создаётся заранее и применяется в некий период,с такого дня по такой то день. То есть время акций (старт и окончание) измеряется с точностью до дня). Можно конечно описать акцию и в вечернее, к примеру время, но тогда у нас у акции будет два времени: время использования акции (например 8 марта) и время действия акции (весь день или с 18:00 до 21:00) . - нас, в этом случае для заполнения нашего гипотетического кеша на инстансе сервиса, заботит только "время использования акции".
Например, акции на 8 марта создаются, по-видимуму, по крайней мере не позже 7 марта, ведь их надо ещё прорекламировать (реально наверное за неделю до 8 марта). И они начинают действовать с 8 марта.
Я думал так. И тогда зачем обращаться к хосту с акциями чаще чем раз в день? - поэтому и предложил такой алгоритм заполнения кеша акций.
В случае "форс-мажора" (когда 8 марта в 10 часов утра, вдруг выяснилось что с акциями что-то кто-то "нахомутал" и надо их изменить (подправить), то в этом случае можно просто перезапустить инстансы скидочного сервиса, тогда кеш станет чистым и снова наполнится данными из базы (хоста) акций при старте или при первом обращении к базе акций.
Механизм кеша действительно простой и часто эффективный.
(Мне пришлось, например, продумывать сервис,который на сайте публиковал некие "данные на текущий день", данные брал из базы, - там сложность была в том, что сервис был для всех жителей Земли, но у каждого юзера время отличалось от времени на сервере. В кеши пришлось хранить данные на два дня. И в зависимости от времени на клиенте, выдавать нужные данные на "текущий для клиента день". Но это специфика работы с сервером, который обслуживает не одну временную зону на клиенте.)
P.S. "Одним из главных недостатков в подходе который вы предлагаете, это то, что если во время синхронизации отдельных инстансов сервиса, произойдет изменение каких либо акций, то инстансы будут находиться в неконсистентном состоянии вплоть до следующей удачной синхронизации."
Этого замечания я не понял. Как это может произойти? - например, 8 марта инстанс сервера обнаруживает что в кеше нет акций на 8 марта и делает запрос на хост (базу) акций для заполнения кеша акциями на 8 марта. База акций вполне позволяет вернуть на этот запрос от инстанса все акции на 8 марта, независимо от того что кто-то во время этого запроса что-то правит в ней. - другое дело что если кто-то правит (вводит) 8 марта акции на 8 марта, то конечно они могут не попасть в ответ на запрос с инстанса сервиса 8 марта. Но изменять акции на какой-то день в тот же день - это недопустимо наверное. Ибо акции должны начать применяться с 00:00 часов наступившего конкретного дня. (00:00 тут не абсолютно, можно настроить кеш на начало открытие магазинов, но в общем случае есть же и магазины online и им точно нужны акции по крайней мере с 00:00 часов для корректной работы их).
P.P.S. для того чтобы я получал на почту сообщение что вы мне ответили тут, то отвечайте именно на моё сообщение, а не на ваше же (как вы выше ответили (добавили как бы) ненароком), иначе мне сообщение о вашем ответе таком не приходит на почту.
В моем случае акции могут быть изменены в любую секунду. Заводятся акции как правило заранее, но изменяться могут когда угодно. Инстансов сервиса несколько, они ничего не знают друг о друге. Задержки в сети могут быть неопределенных размеров. Если инстанс A стянул обновления, затем кто-то отключает акцию (по каким либо причинам), и сразу после, инстанс B стягивает обновления, то инстансы будут находиться в неконсистентном состоянии (и пробудут в нем, вплоть до следующей удачной синхронизации).
Рассылка общей последовательности тоже не идеальна (и в целом страдает от схожих проблем, именно поэтому я упомянул вариант с координатором), но в данном случае имеется один источник истины и на деле худшее что может случиться это разрыв соединения с БД у слушателя, с последующим переподключением, без какого либо ручного вмешательства. На практике же такое случается крайне редко.
В том случае когда время создания/обновления акций можно согласовать с временем синхронизации (ввести мораторий на определенные часы), ваш вариант вполне себе применим.
"В моем случае акции могут быть изменены в любую секунду. Заводятся акции как правило заранее, но изменяться могут когда угодно."
Вот этого я не ожидал.
Не ожидал что реклама "8 марта в наших магазинах скидка 50% на парфюмерию" может быть 8 же марта и отменена. Или отменена с полдня. Или 50% изменено на 30%. - интересно, как на это реагируют покупатели? - "у вас сегодня акция была, я пришёл, а её нет (или вместо 50% скидка почему-то 30%")? Ему в ответ - "мы имеем полное право отменить акцию или изменить процент скидки. Там мелким шрифтом и написано в условиях акции".
Но и в этом случае можно дать сигнал на сервера с инстансами, чтобы они очистили кеш. Тогда автоматически новые условия по акциям скачаются из базы акций.
Вообще спор что использовать: всегда get (тянуть), кеш и get(тянуть) или pull (получать) при запросе данных- это всегда вопрос подумать, конечно.
(Кеши бывают такие разные, что иногда удивляешься, - например недавно узнал про патерн - по запросу даём сразу из кеша а потом обновляем кеш, если там данные "протухли" или их не было вообще. Данный патерн используется в броузере, когда клиенту сразу показывают страницу с данными которые могли быть уже в кеше,а потом обновляют кеш, если данные там "протухли", и потом асинхронно заменяют данные на странице. Визуально это проявляется как будто приложение мгновенно стартовало. Применимо на показе ленты новостей (или сообщений), к примеру. Но это конечно не тот случай что у вас.)
С 500 мс до нуля, или история о том, как я написал Node.js C++ addon и ускорил скидочный сервис в 500 раз