На чем написан яндекс такси
Как мы обучали приложение Яндекс.Такси предсказывать пункт назначения
Представьте: вы открываете приложение, чтобы в очередной раз заказать такси в часто посещаемое вами место, и, конечно, в 2017 году вы ожидаете, что все, что нужно сделать – сказать приложению «Вызывай», и такси за вами тут же выедет. А куда вы хотели ехать, через сколько минут и на какой машине — все это приложение узнает благодаря истории заказов и машинному обучению. В общем-то все, как в шутках про идеальный интерфейс с единственной кнопкой «сделать хорошо», лучше которого только экран с надписью «все уже хорошо». Звучит здорово, но как же приблизить эту реальность?
На днях мы выпустили новое приложение Яндекс.Такси для iOS. В обновленном интерфейсе один из акцентов сделан на выборе конечной точки маршрута («точки Б»). Но новая версия – это не просто новый UI. К запуску обновления мы существенно переработали технологию прогнозирования пункта назначения, заменив старые эвристики на обученный на исторических данных классификатор.
Как вы понимаете, кнопки «сделать хорошо» в машинном обучении тоже нет, поэтому простая на первый взгляд задача вылилась в довольно захватывающий кейс, в результате которого, мы надеемся, у нас получилось немного облегчить жизнь пользователей. Сейчас мы продолжаем внимательно следить за работой нового алгоритма и еще будем его менять, чтобы качество прогноза было стабильнее. На полную мощность запустимся в ближайшие несколько недель, но под катом уже готовы рассказать о том, что же происходит внутри.
Задача
При выборе пункта назначения, в поле «куда» у нас есть возможность предложить пользователю буквально 2-3 варианта на главном экране и еще несколько – если он перейдет в меню выбора точки Б:
Если наш прогноз верный, пользователю не требуется вбивать адрес, и вообще есть повод порадоваться, что приложение в состоянии хоть немного запомнить его предпочтения. Именно для этих подсказок разрабатывалась модель, которая на основе истории поездок пользователя пытается предугадать, куда именно он сейчас скорее всего отправится.
До построения модели на основе машинного обучения была реализована такая стратегия: берутся все точки из истории, «одинаковые» точки (с одинаковым адресом или находящиеся близко) сливаются, за разные параметры получившимся локациям начисляются различные баллы (если пользователь ездил в эту точку, ездил из этой точки, ездил в эту точку в какое-то временное окно и так далее). Затем выбираются локации с наибольшим числом баллов и рекомендуются пользователю. Как я уже говорил, исторически эта стратегия неплохо работала, но точность прогнозирования можно было повысить. А главное — мы знали как. 
«Старые» эвристики и обученный классификатор могут давать разные прогнозы: на этом рисунке размер круга показывает, насколько высоко данная точка находится в списке рекомендаций в конкретный день и конкретное время. Обратите внимание, что обученный алгоритм в данном примере предложил несколько дополнительных локаций (зеленые круги).
Наша задача состояла в том, чтобы поверх «старой» стратегии использовать переранжирование наиболее вероятных «точек Б» с помощью машинного обучения. Общий подход такой: сначала начисляем баллы, как и раньше, затем берём топ n по этим баллам (где n заведомо больше, чем нужно в итоге порекомендовать), а далее переранжируем его и пользователю в итоге показываем только три наиболее вероятные точки Б. Точное число кандидатов в списке, конечно, определяется в ходе оптимизации, чтобы и качество кандидатов и качество переранжирования были как можно выше. В нашем случае оптимальное число кандидатов оказалось равным 20.
Об оценке качества и результатах
Во-первых, качество нужно разделить на две части: качество кандидатов и качество ранжирования. Качество кандидатов — это то, насколько отобранные кандидаты в принципе возможно правильно переранжировать. А качество ранжирования — это насколько мы правильно предсказываем точку назначения при условии того, что она вообще есть среди кандидатов.
Начнём с первой метрики, то есть качества кандидатов. Стоит отметить, что только примерно в 72 процентах заказов выбранная точка Б (или очень близкая к ней географически) присутствовала ранее в истории. Это означает, что максимальное качество кандидатов ограничено этим числом, так как мы пока не можем рекомендовать точки, куда человек еще ни разу не ездил. Мы подобрали эвристики с назначением баллов так, что при отборе топ-20 кандидатов по этим баллам правильный ответ в них содержался в 71% случаев. При максимуме в 72% это весьма неплохой результат. Это качество кандидатов нас полностью устраивало, поэтому эту часть модели мы дальше не трогали, хотя, в принципе, могли бы. Например, вместо эвристик можно было обучить отдельную модель. Но так как механизм поиска кандидатов, основанный на эвристиках, уже был технически реализован, мы смогли сэкономить на разработке, лишь подобрав нужные коэффициенты.
Снова вернемся к качеству переранжирования. Так как на главном экране заказа поездки показывать мы можем одну, две, ну максимум три точки, то нас интересует доля случаев, когда правильный ответ оказался в топ-1, топ-2 и топ-3 списка ранжирования соответственно. В машинном обучении долю правильных ответов в топ k списка ранжирования (от всех правильных ответов) называют recall@k. В нашем случае нас интересуют recall@1, recall@2 и recall@3. При этом «правильный ответ» в нашей задаче только один (с точностью до близко расположенных точек), а значит, эта метрика как раз будет показывать долю случаев, когда настоящая «точка Б» попадает в топ 1, топ 2 и топ 3 нашего алгоритма.
В качестве базового алгоритма ранжирования мы взяли сортировку по количеству баллов и получили следующие результаты (в процентах): recall@1 = 63,7; recall@2 = 78,5 и recall@3 = 84,6. Заметим, что проценты здесь – это доля от тех случаев, где правильный ответ в кандидатах вообще присутствовал. В какой-то момент возник логичный вопрос: возможно, простая сортировка по популярности уже даёт хорошее качество, а все идеи сортировки по баллам и использование машинного обучения излишни? Но нет, такой алгоритм показал самое плохое качество: recall@1 = 41,2; recall@2 = 64,6; recall@3 = 74,7.
Запомним исходные результаты и перейдем к обсуждению модели машинного обучения.
Доля случаев, когда фактический пункт назначения попадал в число первых k рекомендаций
Какая модель строилась
Для начала опишем механизм нахождения кандидатов. Как мы уже говорили, на основании статистики поездок пользователя разным местам начисляются баллы. Точка получает баллы, если в нее или из нее совершаются поездки; причем существенно больше баллов получают те точки, в которые пользователь ездил из места, где сейчас находится, а ещё больше баллов, если это происходило примерно в это же время. Далее логика понятная.
Теперь перейдём к модели для переранжирования. Так как мы хотим максимизировать recall@k, в первом приближении мы хотим прогнозировать вероятность поездки пользователя в определенное место и ранжировать места по вероятности. «В первом приближении» потому, что эти рассуждения верны только при очень точной оценке вероятностей, а когда в них появляются погрешности, recall@k может лучше оптимизироваться и другим решением. Простая аналогия: в машинном обучении, если мы точно знаем все распределения вероятностей, самый лучший классификатор — байесовский, но поскольку на практике распределения восстанавливаются по данным приближенно, часто другие классификаторы работают лучше.
Задача классификации ставилась следующим образом: объектами были пары (история предыдущих поездок пользователя; кандидат в рекомендации), где положительные примеры (класс 1) — пары, в которых пользователь все-таки поехал в эту точку Б, отрицательные примеры (класс 0) — пары, в которых пользователь в итоге поехал в другое место.
Таким образом, если побыть прожженным формалистом, модель оценивала не вероятность того, что человек поедет в конкретную точку, а сдвинутую вероятность того, что заданная пара «история-кандидат» является релевантной. Тем не менее, сортировка по этой величине столь же осмыслена, что и сортировка по вероятности поездки в точку. Можно показать, что при избытке данных это будут эквивалентные сортировки.
Классификатор мы обучали на минимизацию log loss, а в качестве модели использовали активно применяемый в Яндексе Матрикснет (градиентный бустинг над решающими деревьями). И если с Матрикснетом всё понятно, то почему всё-таки оптимизировался log loss?
Ну, во-первых, оптимизация этой метрики приводит к правильным оценкам вероятности. Причина, по которой так происходит, своими корнями уходит в математическую статистику, в метод максимального правдоподобия. Пусть вероятность единичного класса у i-го объекта равна 
, а истинный класс равен 
. Тогда, если считать исходы независимыми, правдоподобие выборки (грубо говоря, вероятность получить именно такой исход, который был получен) равно следующему произведению:
В идеале нам хотелось бы иметь такие , чтобы получить максимум этого выражения (ведь мы хотим, чтобы полученные нами результаты были максимально правдоподобны, правда?). Но если прологарифмировать это выражение (так как логарифм — монотонная функция, то можно его максимизировать вместо исходного выражения), то мы получим 
. А это уже известный нам log loss, если заменить на их предсказания и умножить все выражение на минус-единицу.
Во-вторых, мы, конечно, доверяем теории, но на всякий случай попробовали оптимизировать разные функции потерь, и log loss показал самый большой recall@k, так что все в итоге сошлось.
О методе поговорили, о функции ошибки – тоже, осталась одна важная деталь: признаки, по которым мы обучали наш классификатор. Для описания каждой пары «история-кандидат» мы использовали более сотни разных признаков. Вот несколько для примера:
И, наконец, о результатах: после переранжирования с помощью построенной нами модели мы получили следующие данные (опять же в процентах): recall@1 = 72,1 (+8,4); recall@2 = 82,6 (+4,1); recall@3 = 88 (+3,4). Совсем неплохо, но в будущем возможны улучшения за счет включения в признаки дополнительной информации.
Можно посмотреть на примере, как новый алгоритм прогнозирования будет выглядеть для пользователя:
Дальнейшие планы
Разумеется, впереди много экспериментов по улучшению модели. Будет и добавление новых данных для построения рекомендаций, в том числе интересов пользователя, а также предполагаемых «дома» и «работы» из Яндекс Крипты и связанных с ними признаков, и эксперимент по сравнению различных методов классификации в этой задаче. Например, у Яндекса уже есть не только используемый сугубо внутри команды Матрикснет, но и набирающий популярность и в Яндексе, и за его пределами CatBoost. При этом, конечно же, нам интересно сравнивать не только собственные разработки, но и другие реализации популярных алгоритмов.
Кроме того, как уже было сказано в начале поста – было бы здорово, если бы приложение само понимало, когда, куда и на какой машине нам нужно поехать. Сейчас сложно сказать, насколько по историческим данным возможно точно угадывать параметры заказа и настройки приложения, подходящие пользователю, но мы работаем в этом направлении, будем делать наше приложение все более «умным» и способным подстраиваться под вас.
Зачем С++ в Такси? Доклад Яндекса
Бэкенд первой версии Яндекс.Такси, которая вышла в 2011 году, был написан на Python. Мы довольно долго не меняли основной язык, но постепенно пришли к идее о необходимости С++ в стеке технологий. Перед вами доклад о том, что мы переписали в первую очередь и почему, а также о трюках С++, которые помогают нам справляться с ростом.
— Добрый день. Меня зовут Александр Голубев, и сегодня я вам расскажу, зачем C++ появился в Такси. Обсудим, как он развивался и какие проблемы мы встречали.
Сначала, чтобы быть не совсем noname-персоной, я немного расскажу о себе. Я руковожу Сектором разработки инфраструктуры в Технологической платформе, которая входит в Бизнес-группу электронной коммерции и перемещения Яндекса. В эту бизнес-группу входит Такси, Еда, Лавка, Драйв, Доставка, Маркет и ряд других направлений. В этой технологической платформе я отвечаю за сервисы коммуникаций, поиск исполнитлей на заказ и инфраструктуру партнерского продукта.
Общий стаж моей работы в IT-сфере — 18 лет. За это время я успел поработать с корпоративными мессенджерами, с VoIP-телефонией, с DPI на магистральных каналах, в облачном хранилище размером в десятки петабайт. Делал антивирусные SDK и, собственно, работал в агрегаторе Такси.
В сегодняшнем докладе я дам ответ на следующие вопросы: когда и зачем появился C++ в Яндекс.Такси, как эволюционировало его использование и какие «велосипеды» помогают нам в решении задач. Особого хардкора не будет, но, надеюсь, будет интересно.
Прежде чем приступить к основной части доклада, давайте взглянем, что есть у других агрегаторов такси, какие языки они используют. Данные взяты из открытых источников, и здесь можно наблюдают эволюцию разработки. Большинство агрегаторов начинали с простых технологий, которые позволяли двигаться быстро. Это мог быть Python, Ruby, PHP. Затем, когда они дорастали до этапа развития, на котором привычные технологии перестали отвечать потребностям, возникали более производительные языки, например Go, C++ или Java.
Яндекс.Такси не был исключением, он начался в 2011 году с языка Python.
Начало. 2011 год
Почему? Потому что у команды, которая этим занималась, была экспертиза в Python. На этом языке писали достаточно много людей, их легко было нанять. Python позволяет быстро прототипировать и достаточно быстро разрабатывать. Производительность на этом этапе не критична, на нее обычно не обращают внимания при выборе языка, на котором стартует какой-либо новый сервис.
Немаловажное свойство — широкий выбор библиотек. Такси в своем развитии использует и внешние библиотеки — например, для построения деревьев для задач поиска, и внутрияндексовые — например, коннекторы к базам, которые есть только внутри Яндекса. Это немаловажный пункт при выборе.
Был Python, был Twisted как фреймворк, активно использовалась многопоточность и асинхронность. В то время водителей на линии работало до 10 тысяч одновременно. Было подключено более 200 партнеров-таксопарков, это позволяло выполнять более 200 тысяч заказов в неделю.
Если вам интересно, вы можете посмотреть доклад 2014 года Дмитрия Курилова, рассказывающий о том, как это работало, какие проблемы решались и как работали с асинхронностью и многопоточностью в Python:
Следующие слайды взяты как раз из того самого доклада. Здесь представлена архитектура Такси. Есть пользователи, есть монолит Такси, есть роутер, который занимается маршрутизацией, есть партнеры, которые предоставляют информацию о доступных водителях, и есть Трекер. Трекер решает конкретную задачу: осуществляет геопоиск подходящих водителей на заказ. В нашем дальнейшем рассказе он наиболее интересен.
Примерно так он работал: брал позиции водителей от всех партнеров, строил по ним дерево для геопоиска, упаковывал его и раздавал другим потокам, чтобы они могли осуществлять по нему поиск.
Здесь начали всплывать типичные проблемы второго Python. В первую очередь — GIL, который не позволял из одного процесса работать с данными эффективно. Упаковка и построение дерева — достаточно CPU-емкая операция. Соответственно, input и output там нет и асинхронность в рамках Python не очень эффективна. К тому же Python — не очень производительный язык, он не предназначен для того, чтобы молотить цифры, а построение деревьев и поиск по ним — это как раз по большей части обход деревьев и математика.
Когда мы строим дерево геопоиска, нам важны не только позиции исполнителей, но и их статус, какой профиль, какие классы он может перевозить, согласен ли он на перевозку животных. Возможно, он заблокирован какими-либо системами. Эти данные должны быть достаточно горячими, должны быть близки. Здесь возникает потребность в кэшировании. Но Python не очень подходит и для кэширования данных в памяти, потому что из-за GIL и других ограничений он работает в несколько процессов, которые не имеют общей памяти. Эти проблемы становятся узким местом языка.
Отдельно отмечу, что в сфере такси задержки очень важны. Почему? Потому что Такси работает с реальным миром. Автомобили двигаются, и при средней скорости в городе 60 км/ч за минуту автомобиль проезжает километр, а за секунду — 17 метров. И каждая секунда задержки принятия данных в обработку, в дерево поиска, приводит к ошибкам позиционирования, а они — к тому, что водитель может проехать нужный поворот, что ведёт к снижению эффективности, к скачкам времени ожидания, к снижению качества Такси как сервиса.
Чтобы решить эти проблемы, требовалось выбрать другой стек технологий для решения задач, позволяющих работать эффективно и с кэшированием, быстрее обрабатывать потоки данных.
И выбрали C++. Почему? Причины те же самые. Экспертиза: C++ — один из основных языков разработки в Яндексе, а на рынке много кадров и их легко нанимать. Скоростью разработки и прототипирования пришлось пожертвовать, зато у нас появилась нужная нам производительность и также широкий выбор библиотек.
Какие были альтернативы? В то время — напомню, это 2015 год — разработчиков на Go было достаточно мало на рынке, да и внутри Яндекса было недостаточно опыта, чтобы эффективно решать задачи при помощи Go. У Java есть Garbage Collector, который может вносить свои коррективы. А Rust? О нем и сейчас больше говорят, чем реально используют.
Первый сервис на C++ в Такси. 2015 год
Первый сервис на C++ появился в Такси в 2015 году. Это был Tracker. Он наследовал не только зону ответственности, но и имя своего прародителя. Разрабатывали его на 14-м стандарте, очень активно использовали clang-format, который стал нашим стандартом. Я его выписал отдельно, потому что эта технология позволяет нам решить две проблемы.
Во-первых, код становится единообразным, легко читается. Во-вторых, убираются все холивары и споры о пробелах на ревью. Форматирование стандартизировано, рекомендую тем, кто не использует. У нас есть ряд хуков, которые не позволяют неотформатированный код запушить в репозиторий. Это приводит к тому, что код у нас везде выглядит единообразно.
В качестве фреймворка выбрали FastCGI-Daemon, это тоже OpenSource-разработка Яндекса. Вы можете ознакомиться с ней на GitHub. У него есть ряд своих минусов, как например он имеет пул потоков и синхронно обрабатывает запросы. В том числе благодаря этому, у нас в дальнейшем появился Userver, так как мы в поисках решения поняли, что лучше делать фреймворк самостоятельно и с другим подходом. Для сборки использовали CMake, у нас было дерево для построения геоиндексов, множество кэшей, и на всем этом у нас крутились данные о более чем 200 тысячах водителей на линии единовременно.
Но сервис не стоял на месте, развивался. Изначально в нем был только индекс свободных водителей. Но для аналитики, для лучшего понимания того, что происходит вокруг, и чтобы качественнее сделать мониторинги, добавился отдельный индекс занятых водителей. Для удобства работы с ним и для расчета более разнообразного числа метрик — в том числе и для определения повышенного спроса — в индекс занятых попадают свободные водители. А в индекс свободных въезжают «цепочки» с занятыми водителями — теми, которые сейчас выполняют заказ, но он у них близится к концу, и можно выдать следующий. Дополнительно появился индекс с очередями в аэропорту. Добавился аналитический режим, который позволял видеть вообще всех участников системы, вне зависимости от того, насколько они активны, заблокированы они или нет. И появился дорожный граф. Он позволяет сильно поднять эффективность поиска за счет того, что мы при поиске учитываем дорожную обстановку. Обычный геопоиск ищет какое-то количество ближайших водителей, которые дальше отдельно маршрутизируются. В отдельных сценариях он находит не совсем идеальных для этого заказа водителей.
Поиск на графе учитывает дорожную обстановку и находит тех исполнителей, которые действительно находятся вблизи. Здесь выбор языка сыграл нам в плюс, так как у Яндекса есть свои карты. Мы просто взяли библиотеку дорожного графа Яндекса, построили на нем свою систему и встроили ее в сервис. Это позволило нам более эффективно искать водителей.
И все это развитие делалось разными командами, в рамках разных целей и задач. И, соответственно, у сервисе не было какого-то одного человека, который видит, как сервис должен развиваться, знает, куда он должен двигаться. Код потихонечку начинал превращаться в спагетти. Большие функции на несколько экранов, где последовательно шли разные проверки. Это все легко было сломать, потому что не всегда можно было понять, куда можно безопасно встроиться и на что это повлияет.
Кроме того, трудно исследовать проблемы, понимать, что и где надо улучшить. Все это приводило к высокому порогу вхождения. Если человек приходил с новой функциональностью, то он достаточно много времени тратил на исследования и на понимание, как все работает. Было трудно поменять что-либо. Например, добавление графа привело к «шрапнельным» правкам, так как данные пришлось пробрасывать от самого начала запроса до самых его глубин. Это привело нас к мысли, что мы в развитии этого сервиса зашли в тупик и надо его переосмыслить.
Второй подход к задаче. 2019 год
В 2019 году мы начали движение к микросервисности. У нас уже появилась ранняя версия Userver, который должен был прийти на замену FastCGI-Daemon. К слову, с самим FastCGI-Daemon у нас не было проблем. Дело в том, что у него пул потоков практически не болел в этом сервисе за счет того, что мы в основном упирались в CPU. У нас почти отсутствовал ввод-вывод в обработке запросов.
У FastCGI-Daemon кончался пул потоков в сервисах, где большую часть операций составляет ввод-вывод, обращение к другим сервисам, хождение в базу, при любых увеличениях задержки сети, или если смежный сервис начинал подтупливать. FastCGI-Daemon просто начинал отбрасывать новые соединения. У нас такой проблемы не было, но мы двигались со всеми вместе и решили перейти на Userver.
Мы выписали все, что хотим получить от новой платформы. Это было отображением проблем, которые у нас были. Мы хотели переиспользовать этот сервис в других сценариях. К нам уже присоединилась Еда, где были схожие задачи — поиск курьера на доставку заказа. Нужно было гибко расширять, конфигурировать.
Сервис должен быть отказоустойчивым. Нужно предусмотреть ручную и автоматическую деградацию функциональности, чтобы в случае резких всплесков заказов или проблем смежников мы могли бы ухудшить качество поиска, но продолжать работать и выполнять заказы. Функциональность должна добавляться легко и просто. Должны быть прочерчены четкие зоны ответственности, мы должны пережить активный рост, уметь масштабироваться.
К слову, большинство из этих требований решаются при помощи такой замечательной вещи, как объектно-ориентированное программирование. Здесь C++ тоже сыграл нам на пользу.
Что у нас было? 17-й стандарт. Мы по-прежнему с любовью использовали clang-format и продолжаем его использовать. В качестве фреймворка стал использоваться Userver. Появилась кодогенерация, причем много. Мы кодогенерируем и методы, и конфиги, и эксперименты, и нашу внутреннюю логику. Эта кодогенерация в основном строится на формате YAML. У нас сразу было KD-дерево для геопоиска, дорожный граф как основной инструмент, достаточно много кэшей. И сотни тысяч водителей на линии.
Чтобы построить эту схему, мы решили сделать такой конвейер. У нас есть индекс — отдельная сущность. Есть процессор, который пропускает тех водителей, которых нам предлагает геоиндекс, через цепочку фильтрующих логик. Информацию о водителях, которые прошли успешно всю цепочку, мы складируем в хранилище.
Я покажу интерфейсы, которые у нас получились. Они очень тривиальны, их очень легко реализовать. За счет этого расширение логик выполняется очень просто. У нас есть фильтр, который реализовывает фильтрующую логику. У него один виртуальный метод, который принимает исполнителя, его контекст и просто отвечает, подходит ли он под представленные требования.
Есть геоиндекс, принимающий параметры поиска и ссылку на процессор, который будет обрабатывать найденных исполнителей.
Есть интерфейс хранилища, который принимает исполнителей, прошедших все проверки, и может ответить, хватит ли искать или нужно еще.
И сам процессор, который получает в конструкторе некоторую цепочку фильтров, прогоняет через нее исполнителей и отправляет результаты в хранилище.
Сейчас это работает в трех дата-центрах на 74 хостах. У нас почти две тысячи ядер. Сотни тысяч водителей онлайн. Обрабатываем мы 20 тысяч запросов в секунду. Цифра кажется не очень большой. Один сервис, делающий простые операции, может обрабатывать столько же на одном хосте, даже на одном ядре.
У нас же в основном все операции сложные — геопоиск, обход графа, проверки водителей с сотнями фильтров на разные условия. Это получение класса водителя, проверки блокировок, не устал ли он, есть ли у него лицензия, удовлетворяет ли он требованиям в запросе, что у него с балансом, может ли он принимать данный способ оплаты. Таких проверяющих логик у нас более ста.
Этими ста логиками мы каждую секунду для этих двадцати тысяч запросов пропускаем 30 миллионов исполнителей. У нас шесть разных индексов: деревья, граф, несколько очередей для разных задач. Теперь у нас есть и отдельные индексы поиска для пеших курьеров, которые не привязаны к автомобильным дорогам.
Более 60 кэшей хранят полную информацию об исполнителях так, чтобы мы могли быстро и оперативно отвечать, не ходя за данными в какие-либо сервисы. Потому что если мы 30 миллионов раз в секунду будем ходить и спрашивать какую-либо базу: а дай мне метаданные по данному водителю, то, кажется, ни одна база не выдержит.
В этом проекте участвовали 40 с лишним разработчиков, при этом он сохранил свою простоту и надежность. Каждая фильтрующая логика — это просто отдельная папочка, в которой хранятся ее модели, сама реализация и необходимые для данной логики кэши, если они требуются.
Дальше я хотел бы немножко показать «велосипеды», которые мы используем, чтобы иметь возможность достичь этих цифр.
Конкурентный словарь индексов
В системе миллионы водителей. Не все из них активны, но большинство из этих водителей имеют пересекающиеся данные, не уникальные. Это может быть класс или модель автомобиля. Соответственно, хранить эти миллионы записей в виде строк не рационально.
Возникла задача: хорошо бы уметь быстро и эффективно преобразовывать строки из ограниченного списка. Например, ясно, что классов будет меньше 200 или что моделей, которые активно участвуют, несколько тысяч, не больше. Можно просто преобразовать эти строковые описания в некое число, положить его в профиль. Это упростит сравнение, уменьшит потребление памяти и в целом повысит эффективность.
Можно для этого использовать class enum, с него большинство таких ситуаций и начиналось. Из enum можно получить строку, из строки — распарсить enum. Но здесь возникает проблема: с развитием этот enum начинает разрастаться. При добавлении туда данных все исходники, которые его используют, должны пересобраться, а проект у нас и так собирается не моментально.
Получается единое место, куда все пишут. Это приводит и к конфликтам на пул-реквестах, оттуда забывают удалять какую-либо информацию. Там бывают ошибки, опечатки, сделали копипаст и забыли поправить. В итоге из enum получается не та строка, или из строки получается не тот enum. Можно было бы взять два unordered_map, использовать их для прямого/обратного индекса. Но нам нужно уметь с этим работать конкурентно, и это требует mutex, а mutex приводит к блокировкам, все это снижает эффективность. Можно, конечно, побить эти индексы на некие ведра, разделить их на множества так, чтобы минимизировать количество блокировок в системе. Но можно сделать все то же самое, но более эффективным способом.
Итак, у нас появился конкурентный словарь индексов. Он параметризуется максимальным количеством ключей, которые могут быть количеством ведер. Здесь мы отдельно принимаем тип mutex, потому что этот класс не всегда работает в контексте корутины, и иногда мы хотим использовать не mutex Userver, а mutex стандартной библиотеки. Есть типы ключа, хэша. Чтобы не хранить дважды один и тот же ключ в прямом/обратном индексе, мы в прямом индексе из строки храним не саму строку, а ссылку на нее.
Определяем структуру ведра, которое содержит индекс для данного подмножества и mutex. Причем здесь мы знаем, каким будет максимальное число элементов и на сколько частей мы побили. Поэтому можем рассчитать, примерно сколько в данном индексе будет элементов, и заранее предалоцировать место для них, чтобы не делать это в процессе работы.
Есть всего лишь четыре поля. Мы знаем сколько будет частей, и можем сразу объявить их в виде массива. Знаем сколько у нас будет ключей, которые также объявляем их в виде массива. И два счетчика: счетчик следующего элемента для получения его идентификатора и счетчик для учета, сколько ключей мы уже сохранили. Почему их два, будет видно дальше.
Есть примитивы, которые позволяют получить нужное нам подмножество. Мы легко высчитываем индекс. Если мы решили не делить на подмножества, то всегда можем просто возвращать готовый индекс, нулевой.
Если же у нас несколько частей, то считаем хэш от ключа, остатком от деления получаем нужный индекс. И две реализации получения bucket: константный и не константный.
Как выглядит добавление, получение индекса для нового ключа? Здесь все делится на три части. Сначала мы проверяем, есть ли такой ключ. Если да, возвращаем готовый индекс. Потом мы блокируем данные в bucket уже на запись, перепроверяем, не успели ли мы в него записать значение. Если записали — возвращаем готовый индекс. Если нет — получаем новый индекс через счетчик. По этой позиции кладем сам ключ в хранилище ключей.
Делаем это абсолютно безопасно, потому что массив уже предалоцирован. Никто по этому индексу не может писать одновременно. И так как мы этот ключ еще не зарегистрировали как сохраненный, то и читать из него никто не будет. Ссылку на строку в этом хранилище мы используем как ключ в прямом индексе, который позволяет нам получить из строки идентификатор.
Снимаем данную блокировку и последним фрагментом гарантируем, что мы последовательно будем увеличивать счетчик сохраненных ключей. Почему? Потому что у нас может быть несколько bucket. Мы можем писать в них параллельно. И может так случиться, что первая запись получила ключ один, вторая получила ключ два и освободилась раньше. Мы не можем сказать, что мы сохранили второй ключ, потому что тогда может произойти обращение к первому индексу, а ключ просто может быть еще не сохранен физически.
И мы просто гарантируем в цикле, что будем увеличивать по порядку счетчик сохраненных ключей. Сначала запишем один и только после этого два. Чтобы облегчить эту операцию в рамках асинхронного фреймворка, мы вызываем Yield, который позволяет не крутить этот цикл вхлостую, а заняться чем-нибудь более полезным.
Получение индекса и ключа по индексу тривиальны — ряд проверок и обращение в хранилище. Все элементарно.
Динамическое перечисление с эффективным списком
Но иногда нам недостаточно получить некий индекс из строки. Мы хотим работать со списком строк. Например, это могут быть классы автомобиля — Эконом, Комфорт, Комфорт+, Бизнес. Могут быть экзамены — водители сдают экзамены на работу в Детском тарифе или в VIP-классе. Хотелось бы уметь работать и с этими списками быстро и эффективно. Можно было бы преобразовать строки в индексы, положить их в вектор. Но в нем неудобно искать. Надо писать код, который будет бежать по нему и проверять значение.
Причем если вдруг окажется, что вектор достаточно большой, этот поиск будет иметь линейную сложность. unordered_set помогает эту задачу решить, но здесь возникают другие вопросы: а если мы хотим слить два set или проверить вхождение одного в другого? Подобное также приводит к линейной сложности этих алгоритмов.
Но в стандартной библиотеке есть bitset. У нас уже есть ограничение по количеству элементов. Мы гарантируем в нашем конкурентном словаре индекса, что все элементы будут идти по порядку, что не будет пропусков. Здесь можно посмотреть в сторону bitset. Естественно, сырой bitset использовать не очень удобно. Давайте попробуем его улучшить. Для начала сделаем простой класс, который преобразует строку в наш идентификатор и назад. Он параметризуется типом нашего индекса. Это сделано для того, чтобы использовать strong definition. То есть мы делаем class enum и потом с ними работаем.
Указываем количество элементов, этими данными параметризуем конкурентный словарь индексов и позволяем из него преобразовывать строку в индекс, а индекс в строку. Все это делается тривиально, с минимальными проверками. Останавливаться здесь не будем.
Далее мы можем на основании этого класса построить наш список. Он принимает Mapper, берет из него количество элементов, типы и определяет сам bitset подходящей размерности.
Работать с bitset очень легко. Мы говорим — по такому-то ключу выстави true или false. Если нужно преобразование строки, оно также добавляется элементарно.
Все проверки упрощаются, в bitset есть готовые методы, мы можем их использовать. Можем проверить, что в одном списке есть хотя бы одно вхождение, тривиально через логический оператор И.
И мы не только можем использовать готовые, то есть сравнивать, есть ли пересечение, но и делать свои кастомные операции, которые ведут себя, возможно, неожиданно и странно.
Например, у нас есть оператор «минус», он просто убирает из одного списка все элементы, которые есть в другом. То есть в какой-то степени накладывает реверсивную маску.
Сюда же можно добавить итераторы, чтобы иметь возможность итерироваться и перебирать все заведенные типы. Все это сильно упрощает нам работу.
При этом мы еще и эффективно начинаем, с точки зрения потребления ресурсов, работать с такими задачами. Можно определить тип strong definition, объявить Mapper, список на нем и успешно решать нужные нам задачи.
Контекст фильтров
Как уже я говорил, у нас есть фильтрующие логики, у них — некий контекст. Фильтры могут добавить туда информацию, а потом другие фильтры могут ее использовать. Например, какой-то из фильтров может получить профиль водителя, запомнить его. Другие фильтры уже не будут ходить в кэши, доставать оттуда данные. Они просто возьмут эти данные из контекста. Для упрощения этой операции нам нужно было что-то придумать, сделать хранилище для обмена информацией между фильтрами.
Самый простой вариант — сделать структуру, в которой объявить все нужные поля нужного нам типа, но здесь возникает все та же проблема. Фильтров у нас более 100. Постоянно добавляются новые, отмирают старые. В эту структуру будут писать все. При любой модификации будет пересобираться бо́льшая часть проекта. Туда будут что-то добавлять, но, может быть, забывать удалять. Получится такая структура-помойка на несколько экранов. У нас такое уже было в нескольких местах, это ужасно. С этим очень неприятно работать, особенно пытаться понять, а вот это поле — оно вообще где-то используется или его просто забыли удалить?
Можно было сделать unordered_map, который по некому ключу хранит std::any. Можно по этому ключу достать данные, преобразовать их в нужные типы и работать с ними. И мы так, на самом деле, в начале и сделали. Но так как у нас 100 фильтров, 30 миллионов исполнителей, которых мы рассматриваем в секунду, то нам хорошо бы обращаться к этой map эффективно. Почему бы не использовать enum class, который позволит по некому числовому представлению получать нужные нам данные? А если в enum ключи лежат по порядку, то, может быть, нам нужен не unordered_map, а хватит и вектора? Мы просто по позиции достанем оттуда нужные нам данные. Но здесь возникает та же проблема: нужен этот большой enum class, где все будут добавлять записи, забывать удалять, и изменения в котором будут приводить к тому, что все будет пересобираться.
Но у нас уже есть конкурентный словарь индексов, почему бы не использовать его? Мы это сделали. С unordered_map от string простые фильтрующие логики, которые берут информацию из контекста, проверяют, например, наличие экзамена и решают, пропускать данные водителя или нет, работали за единицы микросекунд — одну, две, иногда три. Когда мы переделали это на решение с конкурентным словарем индексов, они же стали работать менее чем за одну микросекунду. То есть ускорение было буквально в разы. Бо́льшая часть их работы состояла в том, что они считали хэш по ключу, искали нужную нам ячейку, проверяли, совпадает ли там строка, получали данные и решали коллизии. Когда мы эту работу у них забрали, они стали легковесными.
Здесь опять надо начать с класса, который нам позволит эффективно преобразовывать строку в индекс. Простая обертка.
И сам контекст, который предоставляет тривиальные функции для получения данных и для записи в них. Сам вектор с std::any.
Вот немного кода. Наверное, на нем не стоит останавливаться, он достаточно тривиален. Мы пробуем получить данные из вектора, сохранить с проверками.
Но здесь есть неудобство: нам нужно помнить индекс, знать тип данных, которые мы достаем. Типов много, они разные, могут меняться. Это все надо синхронизировать.
Чтобы упростить работу, мы сделали отдельный класс, который хранит контекст, позволяет работать с данными в контексте. Он параметризуется типом хранимых данных, хранит индекс, по которому эти данные находятся, предоставляет простой интерфейс получения данных нужного нам типа из контекста. Здесь тип уже зашит в API и не требует вспоминать о нем и вручную преобразовывать.
Применение становится тривиальным. Мы делаем статическое константное поле, инициируем его, и у нас есть два готовых метода для получения и сохранения данных. Такие примитивы позволяют нам быстро и эффективно искать исполнителей, чтобы предоставлять вам сервис Такси.
На этом мой доклад окончен. Я рассказал вам краткую историю технологий в Такси, о том, как они развивались, какие проблемы мы встречали. Поделился «велосипедами», которые позволяют нам решать их быстро и эффективно. Спасибо.