Pull to refresh

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

Reading time 12 min
Views 22K
В этой статье мы рассмотрим способы создания поиска по базе туров (тур из себя представляет набор из отеля и перелета) и рассмотрим две опции — 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 Мб, остальные настройки см. под спойлером):

Дефолтные настройки innodb
innodb_adaptive_flushing ON
innodb_adaptive_flushing_lwm 10
innodb_adaptive_hash_index ON
innodb_adaptive_hash_index_parts 8
innodb_adaptive_max_sleep_delay 150000
innodb_api_bk_commit_interval 5
innodb_api_disable_rowlock OFF
innodb_api_enable_binlog OFF
innodb_api_enable_mdl OFF
innodb_api_trx_level 0
innodb_autoextend_increment 64
innodb_autoinc_lock_mode 1
innodb_buffer_pool_chunk_size 134217728
innodb_buffer_pool_dump_at_shutdown ON
innodb_buffer_pool_dump_now OFF
innodb_buffer_pool_dump_pct 25
innodb_buffer_pool_filename ib_buffer_pool
innodb_buffer_pool_instances 1
innodb_buffer_pool_load_abort OFF
innodb_buffer_pool_load_at_startup ON
innodb_buffer_pool_load_now OFF
innodb_buffer_pool_size 134217728
innodb_change_buffer_max_size 25
innodb_change_buffering all
innodb_checksum_algorithm crc32
innodb_checksums ON
innodb_cmp_per_index_enabled OFF
innodb_commit_concurrency 0
innodb_compression_failure_threshold_pct 5
innodb_compression_level 6
innodb_compression_pad_pct_max 50
innodb_concurrency_tickets 5000
innodb_data_file_path ibdata1:12M:autoextend
innodb_data_home_dir
innodb_deadlock_detect ON
innodb_default_row_format dynamic
innodb_disable_sort_file_cache OFF
innodb_doublewrite ON
innodb_fast_shutdown 1
innodb_file_format Barracuda
innodb_file_format_check ON
innodb_file_format_max Barracuda
innodb_file_per_table ON
innodb_fill_factor 100
innodb_flush_log_at_timeout 1
innodb_flush_log_at_trx_commit 1
innodb_flush_method
innodb_flush_neighbors 1
innodb_flush_sync ON
innodb_flushing_avg_loops 30
innodb_force_load_corrupted OFF
innodb_force_recovery 0
innodb_ft_aux_table
innodb_ft_cache_size 8000000
innodb_ft_enable_diag_print OFF
innodb_ft_enable_stopword ON
innodb_ft_max_token_size 84
innodb_ft_min_token_size 3
innodb_ft_num_word_optimize 2000
innodb_ft_result_cache_limit 2000000000
innodb_ft_server_stopword_table
innodb_ft_sort_pll_degree 2
innodb_ft_total_cache_size 640000000
innodb_ft_user_stopword_table
innodb_io_capacity 200
innodb_io_capacity_max 2000
innodb_large_prefix ON
innodb_lock_wait_timeout 50
innodb_locks_unsafe_for_binlog OFF
innodb_log_buffer_size 16777216
innodb_log_checksums ON
innodb_log_compressed_pages ON
innodb_log_file_size 50331648
innodb_log_files_in_group 2
innodb_log_group_home_dir ./
innodb_log_write_ahead_size 8192
innodb_lru_scan_depth 1024
innodb_max_dirty_pages_pct 75.000000
innodb_max_dirty_pages_pct_lwm 0.000000
innodb_max_purge_lag 0
innodb_max_purge_lag_delay 0
innodb_max_undo_log_size 1073741824
innodb_monitor_disable
innodb_monitor_enable
innodb_monitor_reset
innodb_monitor_reset_all
innodb_old_blocks_pct 37
innodb_old_blocks_time 1000
innodb_online_alter_log_max_size 134217728
innodb_open_files 2000
innodb_optimize_fulltext_only OFF
innodb_page_cleaners 1
innodb_page_size 16384
innodb_print_all_deadlocks OFF
innodb_purge_batch_size 300
innodb_purge_rseg_truncate_frequency 128
innodb_purge_threads 4
innodb_random_read_ahead OFF
innodb_read_ahead_threshold 56
innodb_read_io_threads 4
innodb_read_only OFF
innodb_replication_delay 0
innodb_rollback_on_timeout OFF
innodb_rollback_segments 128
innodb_sort_buffer_size 1048576
innodb_spin_wait_delay 6
innodb_stats_auto_recalc ON
innodb_stats_include_delete_marked OFF
innodb_stats_method nulls_equal
innodb_stats_on_metadata OFF
innodb_stats_persistent ON
innodb_stats_persistent_sample_pages 20
innodb_stats_sample_pages 8
innodb_stats_transient_sample_pages 8
innodb_status_output OFF
innodb_status_output_locks OFF
innodb_strict_mode ON
innodb_support_xa ON
innodb_sync_array_size 1
innodb_sync_spin_loops 30
innodb_table_locks ON
innodb_temp_data_file_path ibtmp1:12M:autoextend
innodb_thread_concurrency 0
innodb_thread_sleep_delay 10000
innodb_tmpdir
innodb_undo_directory ./
innodb_undo_log_truncate OFF
innodb_undo_logs 128
innodb_undo_tablespaces 0
innodb_use_native_aio OFF
innodb_version 5.7.17
innodb_write_io_threads 4

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 Мб (по всей видимости, весь объем был отсортирован в памяти и записан одним куском).

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

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


Давайте соберем все показатели вставки в одну таблицу:
Метод Время Размер таблицы Записано на диск
InnoDB 95 секунд 652 Мб 3,5 Гб
InnoDB+PK 73 секунды 538 Мб 3,0 Гб
MyISAM 40 секунд 491 Мб 350 Мб?
ClickHouse 4 секунды 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.

Итак, результаты:
Метод 1, мс 2, мс 3, мс 4, мс 5, мс
InnoDB 4300 3800 3800 3800 3700
InnoDB+PK 4600 600 4000 4000 540
MyISAM 1300 1600 (1000) 800 700 1500 (670)
ClickHouse 120 (40) 40 (14) 150 (54) 180 (80) 14 (8)

И то же самое с холодным кешом (на ноутбучном SSD):
Метод 1, мс 2, мс 3, мс 4, мс 5, мс
InnoDB 5500 5000 4800 4700 4700
InnoDB+PK 12700 1960 12100 12000 1720
MyISAM 14800 (1060) 800 920 799 14900 (767)
ClickHouse 570 (188) 177 (90) 591 (224) 608 (254) 122 (55)

Анализ


Можно видеть, что, без тюнинга, в 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, чтобы результаты были лучше и опубликуете свои бенчмарки, то пишите обязательно в комментариях, это будет полезным дополнением к статье, поскольку мои цифры лишь примерны, и правильные настройки могут изменить результаты в несколько раз для некоторых видов запросов.

Ссылки


  1. ClickHouse
  2. Генератор данных для туров
  3. Собранные бинарники ClickHouse под macOS
Tags:
Hubs:
+31
Comments 19
Comments Comments 19

Articles