Случайны выбор дневника Раскрыть/свернуть полный список возможностей


Найдено 24328 сообщений
Cообщения с меткой

поиск - Самое интересное в блогах

Следующие 30  »
rss_rss_hh_new

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

Суббота, 25 Марта 2017 г. 16:49 (ссылка)

В этой статье мы рассмотрим способы создания поиска по базе туров (тур из себя представляет набор из отеля и перелета) и рассмотрим две опции — 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, чтобы результаты были лучше и опубликуете свои бенчмарки, то пишите обязательно в комментариях, это будет полезным дополнением к статье, поскольку мои цифры лишь примерны, и правильные настройки могут изменить результаты в несколько раз для некоторых видов запросов.
Original source: habrahabr.ru.

https://habrahabr.ru/post/324846/?utm_source=habrahabr&utm_medium=rss&utm_campaign=best

Метки:   Комментарии (0)КомментироватьВ цитатник или сообщество
rss_rss_hh_new

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

Суббота, 25 Марта 2017 г. 16:49 (ссылка)

В этой статье мы рассмотрим способы создания поиска по базе туров (тур из себя представляет набор из отеля и перелета) и рассмотрим две опции — 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, чтобы результаты были лучше и опубликуете свои бенчмарки, то пишите обязательно в комментариях, это будет полезным дополнением к статье, поскольку мои цифры лишь примерны, и правильные настройки могут изменить результаты в несколько раз для некоторых видов запросов.
Original source: habrahabr.ru (comments, light).

https://habrahabr.ru/post/324846/

Метки:   Комментарии (0)КомментироватьВ цитатник или сообщество
Ollsvar

Подсказка для сыщиков

Суббота, 25 Марта 2017 г. 17:09 (ссылка)

Это цитата сообщения Дом_советов Оригинальное сообщение

Как узнать максимум информации о человеке в интернете

Мало ли какие бывают ситуации, когда необходимо узнать максимум информации о человеке, не прибегая при этом к прямому допросу. Конечно, полную автобиографию вы в интернете не найдёте, но всё, что человек показывал и рассказывал о себе миру, так или иначе сохраняется в сети. Уверен, что многие приемы станут для вас откровением. Например, знаете, как узнать номер квартиры человека по его домашнему телефону? Узнайте, как эту информацию добыть.
002-06 (550x327, 59Kb)

15 конкретных способов >>>

Метки:   Комментарии (0)КомментироватьВ цитатник или сообщество
kiev2376393

NASA продемонстрировало робота для поиска внеземной жизни (видео)

Пятница, 24 Марта 2017 г. 16:29 (ссылка)

NASA продемонстрировало робота для поиска внеземной жизни (видео) [ Редактировать ] 16 марта 2017 13:54 по материалам: Подробности автор: Наталия Клюева 182 Фото: Twitter SarahMicrobio NASA продемонстрировало робота для поиска внеземной

Читать далее...
Метки:   Комментарии (0)КомментироватьВ цитатник или сообщество
lj_tema

Чезафильм

Среда, 22 Марта 2017 г. 19:01 (ссылка)

В этом посте все желающие ищут музыку, фильмы, книги и пр.

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

Например: чезафильм, типа старый польский, где у мальчика рука вырастает на 50 метров по мере необходимости?

И т. д.

Ищем и находим.

http://tema.livejournal.com/2461465.html

Метки:   Комментарии (0)КомментироватьВ цитатник или сообщество
lenov_ru

Guardians of Fantasy v 1.0.0 Мод (Massive Damage/Crit) » Клуб пользователей планшетов на ANDROID / Lenovo IdeaTab A2109 8GB / Samsung Galaxy Tab 2 7.0 / Asus Transformer TF700T / NVIDIA Tegra 3

Среда, 22 Марта 2017 г. 07:44 (ссылка)
lenov.ru/games/28481-guardi...-crit.html


Guardians of Fantasy - японское MMORPG с характерным стилем очень красивой HD графики. Геймеров ждёт превосходно продуманная вселенная полная магии и захватывающих сражений. Здесь каждый найдёт себе

Комментарии (0)КомментироватьВ цитатник или сообщество

Следующие 30  »

<поиск - Самое интересное в блогах

Страницы: [1] 2 3 ..
.. 10

LiveInternet.Ru Ссылки: на главную|почта|знакомства|одноклассники|фото|открытки|тесты|чат
О проекте: помощь|контакты|разместить рекламу|версия для pda