Делаем быстрый поиск по турам на основе ClickHouse

В этой статье мы рассмотрим способы создания поиска по базе туров (тур из себя представляет набор из отеля и перелета) и рассмотрим две опции — ClickHouse и MySQL (два движка — InnoDB и MyISAM).

В чем сложность поиска по турам

Туроператоры (TezTour, TUI, Natalie Tours, etc) продают свои путевки неочевидным, на первый взгляд, способом:

• резервируется определенное количество номеров в отелях на некоторый набор дат
• выкупается несколько самолетов
• выпускается новый пакет туров, в котором содержатся комбинации всех возможных типов номеров, длительностей пребывания, городов и дат вылета

После этого по таким комбинациям (количество которых может исчисляться сотнями миллионов и даже миллиардами) осуществляется поиск. Пример формы поиска можно увидеть у TezTour — пользователь может выбрать только один город вылета, тип размещения и страну, а остальные параметры пользователь может выбирать произвольные.

Несмотря на то, что общее количество туров (комбинаций) исчисляется сотнями миллионов, на каждый фиксированный набор параметров (город вылета, тип размещения, страна) приходятся, в худшем случае, десятки миллионов вариантов. Но даже по такому количеству туров не так просто осуществлять поиск, потому что нужно найти записи, которые удовлетворяют свободным критериям, которые задают пользователи, и сортировка может быть более-менее произвольной (как правило, сортировка делается по цене, но это не единственный возможный критерий). В этой статье мы рассмотрим упрощенную архитектуру реалтайм-поиска по турам на основе MySQL и ClickHouse, без учета стопов (сленговый термин, который означает, что по каким-то вариантам закончились номера или места в самолете, и такие туры нужно исключить из выдачи). Мы научимся делать поиск быстрым и уметь показывать результаты с сортировкой по любым полям.

Откуда брать данные

Изначально я хотел взять настоящую базу какого-нибудь туроператора и загружать её в качестве тестовых данных для нашей системы — так можно было бы проверять адекватность нашего поиска путем сравнения нашей выдачи и выдачи поиска на сайте туроператора. Но, к сожалению, легко найти базу туров в открытом доступе мне не удалось, поэтому вместо этого придется ограничиться набором псевдослучайных данных, которые будут имитировать реальные туры.

Набор полей

Так как при поиске город, страна и тип размещения фиксированы, мы можем создать таблицы, в именах которых будет содержаться ID соответствующих параметров, например tours_12_55_1001, где 12, 55 и 1001 — это ID города, страны и типа размещения соответственно. Это позволяет нам резко сократить количество записей, которые нам нужно просматривать и заодно сэкономить место за счёт того, что мы не будем хранить повторяющиеся значения в таблицах.

Тем не менее, даже для одной такой таблицы могут быть десятки миллионов вариантов, и для тестовой выборки мы будем генерировать ровно 10 миллионов записей со следующей структурой:

• tour_id — uint64 — уникальный ID предложения
• package_id — uint64 — ID соответствующего пакета туров (пакеты добавляются и отзываются целиком)
• date_start — uint8 — дата прилета — число дней с определенного момента
• stars — uint8 — количество звезд у отеля + специальные значения, например для апартаментов
• pansion — uint8 — тип питания (Bed & Breakfast, All Inclusive, etc)
• nights — uint8 — продолжительность пребывания (количество ночей)
• region_id — uint16 — ID региона отеля
• hotel_id — uint32 — ID отеля
• airport_id — uint8 — ID аэропорта прилета
• price — uint16 — цена предложения, в долларах

Для разных стран и разных туроператоров список может отличаться (например, может также присутствовать аэропорт вылета, или цена указана в другой валюте, и тогда она не поместится в uint16, и т.д.), но мы остановимся на этом варианте, как самом базовом.

Код для генерации пишется за 10 минут любым программистом, я приведу пример на go:

package main

import (
	"encoding/csv"
	"flag"
	"math/rand"
	"os"
	"strconv"
)

var n = flag.Int("n", 10000000, "How many entries to generate")

func main() {
	wr := csv.NewWriter(os.Stdout)
	defer wr.Flush()

	wr.Write([]string{
		"tour_id",
		"package_id",
		"date_start",
		"stars",
		"pansion",
		"nights",
		"region_id",
		"hotel_id",
		"airport_id",
		"price",
	})

	for i := 0; i < *n; i++ {
		wr.Write([]string{
			strconv.FormatInt(int64(i), 10),
			strconv.FormatInt(rand.Int63(), 10),
			strconv.FormatInt(rand.Int63n(90), 10),
			strconv.FormatInt(rand.Int63n(10), 10),
			strconv.FormatInt(rand.Int63n(10), 10),
			strconv.FormatInt(rand.Int63n(30), 10),
			strconv.FormatInt(rand.Int63n(1000), 10),
			strconv.FormatInt(rand.Int63n(1000000), 10),
			strconv.FormatInt(rand.Int63n(10), 10),
			strconv.FormatInt(rand.Int63n(10000), 10),
		})
	}
}

Полученный csv-файл занимает порядка 500 Мб и содержит 10 млн записей, в которых tour_id монотонно возрастает, а остальные поля имеют случайные значения в более-менее приближенных к реальности диапазонах.

Критерии поиска

Нам нужно уметь искать по любым наборам значений для каждого из полей и с любой сортировкой, но, как правило, диапазоны дат вылета и продолжительность имеют не очень большой разброс — люди редко ищут туры с диапазоном дат вылета, например, с 1 марта по 1 мая. Мы можем считать, что поиск с широким диапазоном дат вылета тоже должен работать, но оптимизировать время ответа и потребление ресурсов нужно для случая, когда этот диапазон существенно ограничен, например, составляет в среднем не более 10 дней. Это знание нам пригодится при выборе индексов.

Реализация на MySQL

Я выбрал MySQL потому, что хорошо знаком с этой базой данных, а также потому, что она относительно неплохо подходит для этой задачи.

Попробуем использовать 3 немного разных подхода: простой InnoDB, InnoDB + primary key(date_start, id) и MyISAM. Структура таблицы будет одинаковой для всех 3 подходов и отличия будут только в движке и в том, какие индексы мы накладываем:

CREATE TABLE `tours` (
  `tour_id` bigint(20) NOT NULL,
  `package_id` bigint(20) NOT NULL,
  `date_start` tinyint(4) NOT NULL,
  `stars` tinyint(4) NOT NULL,
  `pansion` tinyint(4) NOT NULL,
  `nights` tinyint(4) NOT NULL,
  `region_id` smallint(6) NOT NULL,
  `hotel_id` int(11) NOT NULL,
  `airport_id` tinyint(4) NOT NULL,
  `price` smallint(6) NOT NULL
)

InnoDB

Сначала попробуем использовать стандартный движок InnoDB со стандартными индексами — PRIMARY KEY (`tour_id`), KEY `date_start` (`date_start`). Ключ на date_start нам должен ускорить выборки по диапазону дат вылета, а PRIMARY KEY tour_id сделан с расчетом на то, что tour_id монотонно возрастает, что нам должно дать оптимальную скорость вставки.

Вставим наши данные в дефолтную инсталляцию MySQL 5.7.17 (innodb_buffer_pool_size=128 Мб, остальные настройки см. под спойлером):

LOAD DATA LOCAL INFILE 'tours.csv' INTO TABLE tours FIELDS TERMINATED BY ','

Во время заливки убедимся, что узким местом является именно MySQL-сервер, а не клиент (CPU usage клиента не должен быть 100%) и посмотрим на время исполнения запроса:

Query OK, 10000000 rows affected, 11 warnings (1 min 35.09 sec)
Records: 10000001  Deleted: 0  Skipped: 1  Warnings: 11

Кажется, что 1,5 минуты для вставки 10 миллионов записей — это ок для InnoDB. Ворнинги относятся к первой строчке в CSV-файле, поскольку там написаны имена столбцов.

Получившийся размер таблицы — 490 Мб данных и 162 Мб индексов. В процессе выполнения запроса MySQL записал на диск 3,5 Гб и загрузка CPU была в районе 100% (утилизировано 1 ядро из 4 на тестовом ноутбуке).

Перед тем, как делать поисковые запросы, давайте посмотрим на другие возможные варианты вставки данных.

InnoDB + PRIMARY KEY(date_start, tour_id)

Поскольку мы заранее знаем, что большинство запросов будут затрагивать только относительно небольшой диапазон дат вылета, можно кластеризовать данные по дате вылета вместо tour_id — в этом случае чтение по диапазону date_start будет давать меньше случайного чтения с диска (или из buffer_pool), а значит поиск по такой таблице должен быть быстрее.

Давайте посмотрим, как обстоят дела со вставкой:

Query OK, 10000001 rows affected, 10 warnings (1 min 13.34 sec)
Records: 10000001  Deleted: 0  Skipped: 0  Warnings: 10

Вопреки ожиданиям, вставка в такую таблицу прошла даже немного быстрее, чем в «обычную» структуру. Вероятно, это связано с тем, что у нас нет «лишнего» индекса по date_start, и он включен в PRIMARY KEY. На диск было записано немного меньше, чем в прошлый раз — всего 3 Гб.

Размер таблицы — 538 Мб данных и 0 Мб индекса (вторичных индексов нет, а PRIMARY KEY записывается является частью данных в InnoDB)

MyISAM

В былые годы MyISAM был движком по умолчанию в MySQL и славился своей скоростью вставки и выполнения FULL SCAN. Чем не идеальный кандидат для нашей задачи? Структура таблицы остается такой же, как в случае с первым вариантом InnoDB.

Query OK, 10000000 rows affected, 11 warnings (40.39 sec)
Records: 10000001  Deleted: 0  Skipped: 1  Warnings: 11

Результат, безусловно, получше, хотя и не на порядок. Тюнингом настроек можно добиться лучших результатов как в случае MyISAM, так и в случае InnoDB, но это тема для отдельной большой статьи. На диск было записано 350 Мб, а размер таблицы — 286 Мб данных + 205 Мб индекса. Почему, согласно приборам, на диск было записано меньше, чем размер таблицы в MyISAM, я понять не смог. Читатель может попробовать воспроизвести эксперимент на своем инстансе MySQL и сравнить цифры.

ClickHouse

Ну и последним вариантом будет база данных от яндекса под названием ClickHouse. Это колоночная база данных с автоматическим распараллеливанием запросов и кучей других ништяков. Существуют бинарные сборки под Linux и даже Docker-контейнеры и заявлена поддержка macOS. Бинарных сборок под macOS я найти не смог, поэтому собрал и выложил: yadi.sk/d/RffdbxaM3GL7Ac (сборка требует gcc-6, нескольких десятков гигабайт места и примерно 2 часов на моем ноутбуке). Тесты я буду гонять на macOS.

Сначала создадим таблицу:

CREATE TABLE tours
(
    tour_id UInt64, 
    package_id UInt64, 
    date_start UInt8, 
    stars UInt8, 
    pansion UInt8, 
    nights UInt8, 
    region_id UInt16, 
    hotel_id UInt32, 
    airport_id UInt8, 
    price UInt16, 
    date Date MATERIALIZED toDate(date_start)
) ENGINE = MergeTree(date, date_start, 8192)

При создании таблицы типа MergeTree (рекомендуется по умолчанию) требуется указать столбец с датой (по нему осуществляется шардирование). Здесь я немного поленился и сделал просто MATERIALIZED столбец date со значением toDate(date_start). В реальных данных намного проще будет просто сделать столбец date_start с типом Date — в clickhouse дата много места не занимает благодаря компрессии столбцов.

ClickHouse, вставка данных

Теперь вставим данные:

$ cat tours.csv | pv | clickhouse --client --query 'INSERT INTO tours FORMAT CSVWithNames'
524MiB 0:00:04 [ 123MiB/s]

Если у вас ещё не уставлена утилита pv — рекомендую поставить, она позволяеть печатать прогресс исполнения операций и показывает, сколько байт прошло через пайп.

Можно видеть, что вставка csv-файла произошла за 4 секунды со скоростью вставки порядка 100 Мб/сек (как и заявлено авторами). При вставке сервер потратил 7 секунд процессорного времени.

Размер данных составляет 378 Мб, и на диск было записано тоже 378 Мб (по всей видимости, весь объем был отсортирован в памяти и записан одним куском).

К сожалению, поскольку наши тестовые данные случайны, у нас не получилось извлечь значимую пользу от компрессии столбцов. Реальные данные должны сжиматься лучше, поэтому итоговый размер должен быть ещё меньше.

Времена вставки данных, сравнение

Давайте соберем все показатели вставки в одну таблицу:

Выборка

Мы будем делать несколько выборок, которые соответствуют более-менее правдивым видам запросов, которые приходят в поиск по турам:

-- 1. «Горящие туры»
SELECT * FROM tours ORDER BY price ASC LIMIT 20;

-- 2. «Горящие туры» в интервале 10 дней (1/9 всех записей)
SELECT * FROM tours WHERE date_start BETWEEN 40 AND 50 ORDER BY price ASC LIMIT 20;

-- 3. 5 ночей с ценой от 500 до 600 долларов
SELECT * FROM tours WHERE nights = 5 AND price BETWEEN 500 AND 600 ORDER BY price ASC LIMIT 20;

-- 4. цена от 500 до 600 долларов, максимальная продолжительность и число звезд
SELECT * FROM tours WHERE price BETWEEN 500 AND 600 ORDER BY nights DESC, stars DESC LIMIT 20;

-- 5. конкретный отель в определенные даты
SELECT * FROM tours WHERE date_start BETWEEN 10 AND 20 AND hotel_id = 767036 ORDER BY price LIMIT 20;

Для MyISAM в скобках указаны времена запросов, если указать IGNORE INDEX(date_start).
Для ClickHouse в скобках указаны времена запросов, если выбирать не *, а только tour_id и price.

Итак, результаты:

И то же самое с холодным кешом (на ноутбучном SSD):

Анализ

Можно видеть, что, без тюнинга, в MySQL лучше всего подходит MyISAM, причём индекс по date_start нам делает только хуже, особенно в случае холодного кеша (это объясняется тем, что в MyISAM случайный доступ к строкам сделан не слишком эффективно — всегда читается по одной строке системным вызовом read(), что в случае с холодным кешом имеет катастрофические последствия даже на SSD). Некоторые запросы лучше исполняются быстрее на схеме InnoDB+PK, но только на прогретом кеше. В случае холодного старта MyISAM намного предпочитетельней, причём без индекса по date_start (можно вместо этого расшардить таблицу ещё и по диапазонам дат и пускать запросы параллельно).

Поскольку ClickHouse является колоночной базой, запрос вида SELECT * для него является не очень удобным — это можно видеть по времени исполнения запросов. Если есть возможность, нужно выбирать только те колонки, которые нужны (мета-информация для tour_id в любом случае должна дублироваться ещё где-то в надежном хранилище, и можно оттуда её доставать вместо выборки напрямую из ClickHouse). Также, ClickHouse автоматически распараллеливает исполнение запросов на все доступные ядра, а также сканирует только нужные колонки, поэтому работает очень быстро при прогретом кеше. В случае холодного старта особенно заметно, почему предпочительней выбирать не все колонки, а только нужные.

Однако, даже при холодном старте, ClickHouse лидирует по времени исполнения запросов во всех случаях без исключения.

Заключение

В этой статье мы с вами построили упрощенную модель для поиска по турам, без учета стопов, на основе MySQL (3 различных подхода) и ClickHouse, и во всех случаях база данных от Яндекса показывала значительное преимущество в скорости, иногда на 2-3 порядка.

Надеюсь, эта статья поможет ускорить и удешевить поиск тем, кто делает поиск по турам, а также даст базовое понимание того, для каких задач годится ClickHouse. Спасибо за то, что прочитали до конца, буду рад услышать комментарии.

P.S. Если вы можете затюнить MySQL и ClickHouse, чтобы результаты были лучше и опубликуете свои бенчмарки, то пишите обязательно в комментариях, это будет полезным дополнением к статье, поскольку мои цифры лишь примерны, и правильные настройки могут изменить результаты в несколько раз для некоторых видов запросов.

Автор: youROCK

Источник