Как в базе поставщиков найти лучшие по цене предложения, чтобы показать их пользователю
Управление поиском цен на отели в сервисе бронирования — это как ремонт работающего двигателя. Работа с запросами происходит в реальном времени, и простого варианта «отель N на майские» недостаточно, чтобы получить то, что нужно. Скрейпинг, массовые запросы, настройка баланса просмотров и бронирований при работе с самописными базами поставщиков и их ограниченными серверными мощностями — задача почти невыполнимая. Почти…
Привет, Хабр! Меня зовут Иван Чернов. Я 12 лет в IT, 6 из них работаю в «Островок!». Успел побывать и бэкендером, и СТО. Затем снова вернулся в бэкенд. А сейчас мутирую в системного архитектора. В свободное время веду подкасты: «Два Ивана (название обсуждается)» про IT и «Вечерний даунтайм» про настолки.
В этой статье расскажу, как справиться с нагрузкой и поддерживать бесперебойную работу системы. Рассмотрим масштабирование Redis, использование Aerospike, фильтр Блума и решим задачку со звёздочкой. Поговорим о маленьком кусочке схемы, который непосредственно работает с поставщиками в поиске. Это самая нагруженная часть, где возникают наибольшие проблемы с highload. Но именно она нужна, чтобы пользователи получили лучшие цены.
350 технических сотрудников «Островка!» обеспечивают работу высоконагруженной системы из 2,5 миллионов отелей. У нас больше 30 тысяч бронирований в день и 210 тысяч поисковых запросов на сайте в секунду.
Где взять столько отелей
Единой базы отелей во всём мире — не существует! Во-первых: их очень много. Во-вторых: люди пока не могут договориться об этом. Есть крупные сети типа Marriott, Wyndham или Holiday Inn, но они скорее исключение. Да и филиалы их часто ведут собственные базы в Excel, без привязки к остальным отелям сети.
Мы можем создать свою площадку и предложить отельерам зарегистрироваться, чтобы номера бронировали онлайн. Так работает «Островок!» и другие сервисы бронирования, например, Booking.
Вы можете вбить в поисковике запрос: «Booking, system design, interview», и увидеть примерно такую картинку:
В этой схеме много всего. Разобьём её на логические блоки, чтобы стало понятнее:
Система для менеджмента отеля: регистрация, заполнение информации — описание, адрес, фотографии.
Через Kafka переход в Elasticsearch на конкретный поисковый кластер, например, московский.
3. Теперь остаётся только забронировать отель и списать деньги. Кажется, что всё работает хорошо. Но на самом деле нет.
До появления Booking в конце 90-х отельеры сами вели инвентарную базу и менеджерили отели. Часто сами писали софт. Поэтому многие отели не появляются на Booking автоматически и вообще не пытаются туда попасть. За них это приходится делать другим компаниям. Они приходят к отельерам и предлагают сделать интеграцию: выкачивать данные, передать их дальше и получить свою комиссию за посредничество. А если вдруг в онлайн приходит больше бронирований, то запрашивают скидки. Так в схеме появляются поставщики. А как только поставщиков для одних и тех же отелей становится несколько, возникает необходимость в консолидаторах.
Идея в том, чтобы взять всех поставщиков, найти лучшие по цене предложения и именно их предложить пользователю. Как раз этим и занимается «Островок!».
На первый взгляд принципиальная архитектура такого решения напоминает предыдущую.
Точно также, как на прошлой схеме у нас есть блок управления отелями, поисковый кластер и сервис для бронирования. Отличие в том, что появляется новый кубик — это поставщики, которые отдают данные.
Мы хотим выстроить Anti-Corruption Layer, чтобы наша внутренняя бизнес-логика и работа поставщика не пересекались. Для этого зеркалим сервисы по кубикам:
Эти данные меняются довольно редко, поэтому их можно скачивать раз в неделю. Но есть две сложности:
Поставщик может отдать zip-архив с XML на 4 ТБ, и разбирай его сам как знаешь.
Нужно как-то разобраться с тем, что находится в zip-архивах от разных поставщиков. Отель Космос и Космос-отель — это может быть один и тот же отель. Наша задача — понять это и сделать все полученные данные единообразными.
Организовываем поиск. Он делается по запросу вроде: «Дай мне цены на майские праздники на отель Космос». В ответ на запрос выводится информация о том, какие цены доступны.
Бронирование. Этот этап ещё более сложный, потому что в случае бронирования на Booking нужно следить за консистентностью между внутренними сервисами. В нашем случае мы должны учитывать, что обращаемся за данными вовне.
Ловушка хороших цен
Проблема цен в том, что это игра с закрытой информацией. Вы можете отправить запрос «отель Космос на майские» и получить ответ. Но, конечно, это не будет zip-архив со всеми ценами и календарем. Можно попробовать скрейпить: взять все отели, все 365 дней в году и направлять запросы. Но это не так просто, как кажется.
В договор включено конкретное соотношение между просмотрами и бронированиями, и вы должны его выдерживать. Если этого не делать, цены либо будут выше, либо вас отключат. Поэтому задача так не решается.
Из-за этого в нашей сфере существует самая плохая корреляция во всей индустрии. Она заключается в том, что чем лучшие цены от партнера вы видите, тем, как правило, он более технологически не развит. Яркий пример — отели all-inclusive в Турции. Они рады продаваться через туроператоров просто по запросу номера телефона и не хотят никуда подключаться. У них в офисе стоит сервер, который выдерживает 10 запросов в минуту, и больше ничего с этим сделать нельзя. А подключить надо, ведь пользователям это нужно.
Если резюмировать, то у проблемы такой сетап: большое количество подключений, большое количество отелей, большое количество поисков, и для всего этого нужна схема.
На первый взгляд проблема типовая, и очевидным кажется решение с кэшем: когда вся архитектура сводится к тому, чтобы при поисковом запросе пользователя мы обращались к кэшу, а если это не сработает, то к поставщику.
Когда мы слышим слово «кэш», то обычно думаем о Redis. Потому что это простое, понятное, быстрое in memory решение, в которое можно вместить всё, что угодно. В Redis есть множество разных нестандартных структур. Очевидно, что при всех плюсах хочется сразу запустить Redis в прод. Но, сделав это, увидим, что всё горит. Кэш, поставщики и наш внутренний сервис запросов не выдерживают. В результате приходится постоянно решать возникающие проблемы. Расскажу, как это сделать.
Формируем ключ
Начнём с кэша. Так как это key–value база данных, давайте разберемся, как вообще формируется ключ.
Понятно, что в ключ входят отель и даты, но ещё туда входят:
Количество гостей + специфика их размещения. Два гостя в двух номерах — это не то же самое, что двое в одном номере. Как минимум будет разница в количестве уборок и обслуживании. Отдельный нюанс — дети, которые могут спать с родителями в отдельной платной или бесплатной кроватке. Цены на все эти варианты различаются.
Календарь, в котором поиск на 7 дней ≠ 7 поискам на один день. Кажется, что можно просто выгрузить цены по одному дню и сложить, но так не работает. С номерами , как с ценами на лимонад — двухлитровая бутылка дешевле, чем две по литру. Также и здесь: выгоднее искать отель на семь дней. И сами отельеры стимулируют людей заезжать не на один день. У них даже существует регламент: минимум три дня. А чем дольше, тем лучше, потому что в этом случае они несут меньше операционных расходов на уборку, оснащение номера необходимыми расходниками. Да и легче избежать длительных простоев номеров, когда заезды длинные. Профит!
Поиск в глубину. Искать на майские в апреле ≠ искать на майские в феврале. Доступность и цены будут кардинально отличаться. Не так, как в такси, когда при высоком спросе поездка дороже. Но в отельном сегменте тоже свои нюансы. Если вы посмотрели все цены на полгода вперед, то, скорее всего, в ближайшую неделю они меняться не будут. Но при поиске день в день нужно постоянно следить за обновлениями.
Всё это приводит к определенному соотношению между тем, сколько мы читаем и сколько пишем.
Вывод из этого простой: много ключей в один большой вертикальный Redis не вместить. А значит, систему нужно делать распределённой.
Масштабируем Redis
Есть несколько вариантов масштабирования, разберем их подробнее.
В мануале Redis написано, что есть дефолтная схема master ←→ replica. Вы можете установить Redis, сделать к нему N реплик, и всё будет хорошо. Казалось бы, с десяти реплик можно читать в десять раз больше. Но проблема в том, что схема масштабирует только чтение. Реплики замедляют запись, а хочется, чтобы везде были консистентные данные. Но так не получится.
Шардирование по поставщикам. Попробуем решить проблему с бизнесовой точки зрения — выдадим каждому поставщику по Redis или даже по микросервису.
И вот у нас подключено 250 поставщиков, и если каждому поставить по одному Redis и по две реплики, получится 750 контейнеров, подов и виртуалок. Как такое количество оркестрировать — отдельный вопрос.
Но и это не всё, есть ещё одна сложность. Redis требует установить дополнительный софт: Sentinel, twemproxy, etc, если нужна high availability. То есть нужно много софта, ресурсов и инженеров, которые должны обслуживать кластер.
Нашу компанию не устраивал Total Cost of Ownership этого решения. Слишком много подвижных частей, которые могут упасть.
Требования
Чтобы найти альтернативное решение, определили требования, и получился такой список:
Много ключей.
Толстые данные, когда спрашиваешь «отель Космос на майские» и получаешь цену, количество номеров каждого типа: стандартов, люксов, номеров с кроватями разной конфигурации.
Частое обновление ключей (WPS ~ RPS).
Отказоустойчивость.
Низкий Total Cost of Ownership — потому что хотим дёшево.
Выбор DB
Мы сузили область проблем, а значит следующим этапом могли сузить область решений. Для этого просмотрели топ-10 на сайте DB-Engines:
Redis — на первом месте. С ним всё понятно.
DynamoDB от Amazon и CosmosDB от Microsoft — идут следующими. Для меня они в одной категории, хоть и по-разному устроены. Ведь их основной смысл в том, чтобы вы платили больше денег за большую производительность. А это, увы, не соответствует критерию «дёшево».
Memcached — только in-memory, а ведь надо выстраивать pipeline.
etcd и Aerospike — выглядят интереснее. Когда мы искали решение, etcd не было. Мне кажется, что он на седьмом месте просто потому, что используется в K8s.
Aerospike — на него мы обратили внимание и пошли читать официальные отчеты.
Создатели Aerospike обещают:
Они утверждают, что в сравнении с Redis потребуется в 10 раз меньше серверов для обслуживания того же потока. У них 300 тысяч TPS. И если Redis нужно 120 серверов, то Aerospike хватит всего 12, причём аналогичной конфигурации — профит!
Как устроен Aerospike?
Чтобы разобраться, как такое возможно, рассмотрим устройство Aerospike подробнее.
Связан со всеми нодами
Клиентский слой Aerospike устанавливает connect с одной из нод кластера. Но дальше получает информацию о всём кластере и поддерживает connect уже со всеми нодами. Это нужно чтобы при выбивании ноды автоматически происходил connect с другой и приложение работало беспрерывно.
Health-чеки, встроенные в Aerospike, есть как внутри кластера, так и внутри клиента. То есть Aerospike сам держит эту информацию. А при отсутствии сетевой доступности к клиенту роутится другим путём и записывает в кеш с информацию о доступности отеля. Но, по сути, может записывать всё, что угодно.
Раскидывает данные по нодам
Внутри Aerospike — 4096 партиций. Мы берём хэш от ключа и начинаем их раскидывать. При этом партиции мапятся на разные сервера. Например, партиция 1 — это мастер, который попадает на ноду 1. Но она может выступать и репликой для других данных. То есть данные раскидываются по всему кластеру, где выступают то мастером, и в них можно писать, то репликой, и их можно только читать. Это помогает в случае проблем с конкретной нодой.
Автоматически перераспределяет ноды
Например, выставили replication factor 3, и при наличии одного мастера и трёх реплик выпадает эта нода. При этом сам по себе кластер больше, и какие-то ноды просто не использовались. Когда всё падает, нода встаёт недостающей репликой, и начинается миграция данных, которые до этого были успешно скопированы. Мы говорим, что реплика — up, и начинаем с неё читать.
Модель хранения
В Aerospike можно хранить значения и в памяти, и на диске. А когда данных много и они толстые — модель гибридная. То есть ключ хранится в памяти, а запись идёт непосредственно на диск. При этом Aerospike рекомендуют либо отдавать /dev/sda, и тогда мы сами знаем, как и что будет там лежать. Либо использовать файловую систему с Direct Access.
В итоге оказалось, что весь наш поиск держат всего 8 серверов по 48 ядер и 128 гигов оперативки. Туда суммарно прилетает около 30 тысяч TPS — учитывая и запись, и чтение. Всё это хранят 400 миллионов ключей (с учётом replication factor) на каждой из точек.
Это решение казалось нам более годным, чем гипотетические 750 от Redis. Поэтому мы изменили схему:
Мы использовали Aerospike в качестве кэша и нас всё устраивало. Но в один день всё изменилось…
Бум!
Aerospike тоже взорвался! Пошли разбираться, смотреть графики и оказалось, что:
Кластер перестал принимать новые записи.
CPU / IOPS / % на диске — в норме.
Память ушла в потолок.
Нужно было внимательно изучить данные и понять почему ключ Primary Index перестал помещаться в оперативке. Но у нас много ключей, и нужно было понять, какие именно там лежат и откуда они берутся.
У нас два вида ключей:
Доступные отели, где есть цена, комнаты, тарифы с завтраком, без завтрака и так далее.
Недоступные отели — очень странный ключ, показывающий, в какие даты отель недоступен. То есть когда при запросе к поставщику: «Дай мне отель Космос на майские», вам ответят, что его нет. Это единственная информация, которую мы получили от поставщика. Поэтому вы не узнаете, какие там были номера и по каким ценам.
Когда мы изучили графики, то увидели, что в целом поставщики со сплитом 50 на 50 отвечают, что половина отелей доступна, а половина нет.
Мы посмотрели оперативную память Primary Index и обнаружили, что половина ключей — пустые. Они содержат лишь информацию о том, что отель недоступен и не используется. Так мы столкнулись с ограничением Aerospike — использованием 64 байт в оперативке, чтобы отметить, что в базе есть этот ключ. И ожидаемо упёрлись в лимит.
Новое решение — фильтр Блума
Нам нужно было придумать, как хранить ключи по-другому. Мы хотели, чтобы новая структура умела проверять вхождение элемента, делала это быстро и была эффективна по памяти. Потому что просто так в Aerospike мы её положить не можем.
У нас было несколько вариантов:
Хэш-таблица. В Computer Science нам сказали бы, что нужна хэш-таблица, но Aerospike и был такой хэш-таблицей.
Не подходит.
Set. Можно было выделить один ключ, который будет множеством. Так мы обеспечим быструю проверку. Но это не так хорошо с точки зрения памяти, как кажется. Ведь ключи тоже большие и формируются из большого количества параметров.
Тоже не подходит.
Фильтр Блума. Это вероятностная структура, которая состоит из битовой маски и набора хэшей. Когда мы хотим записать элемент, он прогоняется через набор хэшей. В результате мы обновляем в битовой маске соответствующие позиции. Потом, когда хотим проверить, проходимся тем же алгоритмом. Если видим, что во всех позициях единички, то считаем, что этот ключ там есть.
Но может произойти коллизия. Когда какой-то другой ключ на тех же хэшах в эту же позицию даст единички. При коллизии мы получим ответ «ОК». Подтверждение, что ключ, которого на самом деле нет, там есть.
Хорошо, что математики рассчитали, как контролировать эту вероятность:
(1-e-kn/m)k
Здесь k, n и m зависят от того, насколько большая битовая маска, сколько вставок предполагается и какой набор хэшей будет. Если мы хотим 0,01% ошибок, можно вычислить эти параметры исходя из того, сколько вставок ожидали.
Формируем ключ
После того как разобрались с коллизиями, сформируем сам ключ. В него входит отель, количество гостей, поставщиков и даты, которые каждый день меняются. Например, мы записали, что отель недоступен с 24 по 26 июня. Но недоступность может растянуться на большее количество дней.
Вот так отельеры ведут учёт доступности.
Это так называемая шахматка, где по строкам прописаны номер и тариф, а по столбцам — даты. А ещё есть небольшой pop-up с двумя видами ограничений:
За какое время можно найти тариф — например, забронировать номер возможно минимум за неделю до заезда.
Минимальное/максимальное время проживания. Например, определённая цена доступна, только если ты заехал минимум на 5 дней.
Получается, наш ключ из дат должен хранить количество дней до заезда и количество дней проживания, потому что эта информация не будет обновляться между строками дат. Значит, мы можем хранить её у себя дольше.
Где и как хранить
С формированием разобрались, осталось выбрать где хранить ключ.
Наверное, можно в оперативке, ведь это просто битовая маска. Преимущества:
Есть готовые библиотеки для большинства языков. У нас эти сервисы написаны на Go.
Работает быстро и компактно.
В Go любят делать бенчмарки по локациям, чтобы всё работало быстро да гладко. Но получаем минус. Мы не шарим знания между нодами. У нас есть кластер на 40 точек. Каждый хранит информацию о недоступных отелях у себя, и это не очень хорошо.
Redis даёт:
Latency на сеть.
У Redis встроенная структура, которая заводится как фильтр Блума. Она сама раскидает, что и какого объема хранить. С помощью фильтра мы шарим знания о недоступных отелях, и наша схема улучшается.
Теперь у нас два кэша, чтобы всё работало в два раза быстрее. Redis используется только для недоступных отелей, а Aerospike — для доступных номеров и тарифов, потому что это толстые данные.
Для этого мы строили эффективный кэш, но осталась проблема с запросами.
Запросов всё ещё много
Поставщики сказали, что у нас всё ещё много запросов. И мы начали думать, почему так происходит.
У нас есть один экземпляр из кластера, второй экземпляр из кластера. Один человек искал на майские отель №1, второй искал на майские отель №2. К поставщику отправили два запроса.
Шардирование поставщиков
Представим, что вместо парадигмы того, что делаем по микросервису на поставщика, мы используем библиотечный подход. У нас есть ноды, умеющие обрабатывать любые запросы, которые мы распределяем равномерно:
Каждый раз при поступлении запроса мы вычисляем, в какую ноду его отправить, и отправляем.
Это выглядит так, как будто мы не решили проблему из предыдущих пунктов.
Но если выкинуть из алгоритма отель, то можно понять, что на первую ноду у нас попадут: один и тот же поставщик, одни и те же даты и два разных отеля, которые можно объединить.
Я говорю про консистентное хеширование. Но и здесь скрывается минус — у нас есть нода, которая вообще ничего не обрабатывает, а мы хотим, чтобы всё происходило более-менее равномерно.
Rendezvous hashing
Используем алгоритм Rendezvous hashing. Он улучшает консистентное хеширование:
У нас есть набор клиентов и набор серверов. Мы начинаем вычислять хэш не только от ключа, но и передаем сервер как параметр. Выбираем самый большой вес и отсылаем запросы туда.
Такая схема лучше:
Можно менять веса серверов. В зависимости от того, на какой сервер пришёл запрос, мы можем проставить ему вес. Это позволяет распределять поставщиков. У нас единый кластер, который с точки зрения operations менеджерится как один. С точки зрения разработки он тоже менеджерится как один. В нашей конфигурации поискового кластера находится десяток серверов. Если мы будем отправлять запросы в режиме round robin (каждый запрос на новый сервер по списку), то наш алгоритм объединения не будет оптимальным. Поэтому надо реализовать кастомный алгоритм балансировки запросов с клиентской стороны. Для этого используем алгоритм рандеву. Так запросы для одного и того же поставщика и дат будут приходить только на подмножество всех используемых серверов с автоматическим фоллбеком в случае недоступности.
Автоматическое перенаправление. Мы получаем фичу по автоматическому перенаправлению. А из-за того, что вычисляем хэши, если у нас выпадает какой-то сервер, то мы просто выбираем следующий, и всё снова хорошо.
Платим скоростью работы — O (N) / O (logN). Вычисляя хэш от каждого сервера, получаем сложность O (N). У нас есть возможность улучшить его до O (logN). Но если серверов меньше 50 и алгоритм выбора сервера — с консистентным хешированием, то скорость останется примерно на том же уровне.
Но запросов всё еще много
Пока мы только перенаправили два запроса к поставщику на два запроса к одному серверу. Поэтому добавляем буфер и начинаем отправлять поставщику один запрос. Поставщик доволен, потому что батч запроса всегда работает лучше, чем единичный.
Кажется, всё хорошо.
Мы уменьшили запросы, но сами поставщики тоже горят. И рано или поздно придётся автоматизировать ситуацию, когда надо отключать поставщиков.
Отключение поставщиков
Есть график проблем, ошибок. И есть решение — поставить circuit breaker, чтобы отключал поставщиков. Тогда вроде бы всё будет хорошо…
Но что, если этот график выглядит так только в Grafana, а на самом деле так:
На полном графике красные точки вообще не видно, но алерты срабатывают и говорят, что всё плохо.
Если пересчитать в процентах, получится три девятки, а значит алертить это не нужно.
Но проценты наших 250 поставщиков выглядят как месиво, где непонятно, что хорошо, а что плохо. Поэтому нам пришлось придумать автоматический способ отслеживания.
Как следить
Пришлось вспоминать статистику. Я пробовал вбивать в Google «скользящее среднее, мониторинг», но выпадали только инвестиционные каналы. А хотелось увидеть, как это применяется в мониторинге.
Возьмём, к примеру, срез за 15 минут, усредним данные и нарисуем гладкую линию, на которой выброса нет.
Дальше будем считать в каждой конкретной точке, что несколько отклонений — это плохо. А в этот же график добавим медианы от прошлых значений, чтобы видеть высокоуровневые тренды, когда поставщик деградирует.
Чтобы всё работало автоматизировано, используем стек TICK (Telegraf, InfluxDB, Chronograf, Kapacitor).
В InfluxDB будут храниться метрики, в Chronograf писаться запросы для отключения, а Kapacitor будет их экзекьютить и дальше что-то с ними делать. Останется понять, за чем следить.
За чем хотим следить
В SRЕ book есть так называемые золотые сигналы — это процент ошибок, availability, latency и так далее.
Например, процент ошибок вышел за критичное значение, и мы отключили этого поставщика. Но на графике видно, что мы экспоненциально его включаем обратно. То есть мы посылаем какое-то количество запросов. Если всё ещё плохо, то отключаем обратно, и от 5 минут до 2 часов число запросов растёт.
Но с точки зрения бизнес-логики есть гораздо более интересные кейсы.
Например, поставщики могут не упасть (504, в NGINX Gateway Timeout и все остальное), а включить режим, что все отели недоступны. А у нас кэш зафиксирует, что всё плохо.
Поэтому лучше сразу превентивно указать, что если поставщик отдаёт 100% недоступность — значит, всё у себя отключил и ничего не ищет. Нам такие запросы не нужны.
А ещё может быть, что поставщик отдаёт доступность, но потом пользователь приходит, пытается забронировать, но отель не бронируется, потому что на самом деле этого номера нет, он уже забронирован. И с этим тоже надо что-то делать.
Эту проблему довольно сложно решить, неважно, делите ли вы систему с помощью функционального подхода (фронт, бек, база) или кросс-функционального (контент, поиск, бронирования). Системы должны друг на друга влиять.
Но с этим всё равно надо что-то делать. Поэтому мы автоматизируем отключение поставщиков и постим себе в Slack с помощью бота Kapacitor. Он пишет, что видит, что success rate одного из поставщиков упал ниже 65%, и его, наверное, надо отключить на 2 часа.
«Разработчики шутят, что бот называется Kapacitor, потому что это Тор с конденсатором в руке.
Таким образом, как будто бы мы решили все проблемы.
Выводы
Гораздо чаще стратегический прорыв происходит в результате измененного представления данных или таблиц. Здесь заключена сердцевина программы. Покажите мне блок-схемы, не показывая таблиц, и я останусь в заблуждении. Покажите мне ваши таблицы, и блок-схемы, скорее всего, не понадобятся: они будут очевидны.
© Брукс «Мифический человеко-месяц»
Напомню:
Мы спроектировали кэш;
Сделали буфер для того, чтобы батчить наши запросы;
Поставили circuit breaker.
Стратегические изменения достигаются за счет того, что вы изменили представление о данных. Вообще то, как вы у себя складываете данные, много говорит о том, над чем вы работаете и будет ли это эффективно. Мы эту проблему решали на каждом шаге. Выбирали решение, исходя из того, какие данные нам отдают, выбирали, как нам фильтровать их правильно с эффективной структурой. Решали, как распределять запросы в нашем кластере, а не просто делать Round Robin. Поэтому думайте о том, какие у вас бизнес-данные и как их можно распределить.
