В этой небольшой статье я хочу поделиться опытом реализации классической для большинства Интернет-магазинов системы фильтров товаров по критериям применительно к туристическому порталу, где появилась задача поиска и фильтрации по базе в десятки тысяч отелей, каждый из которых описывается рядом параметров и наличием нескольких десятков предоставляемых сервисов из сотен возможных.
Постановка задачи
Есть база отелей на несколько десятков тысяч объектов. Каждый отель описывается:
- Рядом параметров с небольшим количеством возможных вариантов для каждого. Например, звёздность отеля: от 1 до 5. Или же типы питания в отеле: их так же не много. И так далее. Сложность тут составляет лишь то, что для некоторых параметров для каждого отеля может быть лишь одно значение, а для некоторых любой набор из возможных. Но при условии небольшого количества возможных вариантов, это пока что не проблема.
- Цена. Упрощая задачу, за базовую цену взята минимальная цена за дабл в сутки с заездом завтра. И эта цена может колебаться от 0 (ох, если бы...) и до тысяч. В фильтрации присутствует несколько диапазонов цен на выбор. Соответственно, необходимо искать отели, цена которых попадает в заданный промежуток.
- Региональная принадлежность. Ситуация такая же, как и в п.1 за исключением того, что количество возможных вариантов для критерия “страна” исчисляется двумя сотнями, а для “города” — уже тысячами. Задача облегчается тем, что каждый отель имеет единственное значение для параметров страны и города.
- И, наконец, самое интересное: список сервисов, предоставляемых отелем. Начиная решать эту задачу, список сервисов был более 700 элементов. С помощью ручного “выкидывания всего ненужного” и группировок, количество сервисов сократилось до 300, что тоже не мало. Чем это грозит — далее.
Теперь, собственно, задача: сделать фильтрацию по произвольному набору любых комбинаций возможных значений параметров, описывающих отель и при показе списка фильтров отображать количество отелей напротив каждого из фильтров. Каждая комбинация фильтров должна иметь понятный URL и отражать воспроизводимую выборку отелей.
Поиск отелей по критериям при количестве объектов в десятки тысяч и условии относительной статичности информации более-менее безболезненно реализуется с помощью ручного анализа/оптимизации каждого запроса и построения индексов либо по двум десяткам таблиц в случае нормализованной БД, либо по одной широкой таблице в случае выбора пути решения задачи через денормализацию.
Но вот небольшая “красивость” в виде подсчёта количества отелей, попадающих в выборку по каждому из возможных значений параметров поиска при количестве этих значений приближающимся к 1000, первоначально вызвала небольшой ступор.
Немного комбинаторики
Подобная задача для прайс-агрегатора в далёком прошлом была решена в лоб и с большим количеством ограничений: в базе данных хранилась огромная таблица с предрасчитанными комбинациями фильтров и количествами товаров по каждой комбинации. Таблица полностью перерасчитывалась каждую ночь и занимала эта операция довольно продолжительное время.
В нашем случае мы хотим сделать нечто более универсальное и без каких либо ограничений, например, на количество одновременно заданных фильтров. Почему это условие так важно? Ответим на этот вопрос, вооружившись Excel и базовыми знаниями комбинаторики.
Для этой цели в Excel есть замечательная функция “ЧИСЛКОМБ”, которая возвращает количество комбинаций для заданного количества элементов при заданном количестве выбранных элементов. Для наглядности берём 10 элементов и считаем количество возможных комбинаций при выбранных 1, 2, 3 и так далее элементах. Получаем таблицу:
| 1 | 10 |
| 2 | 45 |
| 3 | 120 |
| 4 | 210 |
| 5 | 252 |
| 6 | 210 |
| 7 | 120 |
| 8 | 45 |
| 9 | 10 |
| 10 | 1 |
В сумме: 1023 варианта. Таким образом, для 10 возможных фильтров мы должны создать таблицу с 1023 вариантами комбинаций фильтров, для каждого из которых мы должны просчитать количество отелей, попадающие под каждую из комбинаций фильтров. Всё бы хорошо, но при росте количества фильтров, количество вариантов возрастает до цифры, которая лично меня повергла в шок.
При количестве сервисов равным 200 (а реально их гораздо больше) и любым возможным количеством выбранных сервисов, мы получаем количество комбинаций 10 в 63 степени. Другими словами, нам необходимо сделать таблицу, в которой мы будем держать миллиард миллиардов миллиардов записей с предрасчитанным количеством отелей, которую ещё к тому же надо каждый день актуализировать.
Вывод: держать нечто подобное в базе данных, даже используя битовые массивы и актуализировать информацию просто нереально. Никак. Надо искать другой путь.
Используем MongoDB
Когда под туристический портал выбиралась база данных для хранения 1+ миллиарда цен на отели, MongoDB была опробирована в первых рядах, т.к. мной на тот момент только что был окончен курс по вышеозначенной базе и всё представлялось в радужных тонах: шардирование, репликация, документо-ориентированная БД, высокая производительность… Но всё мгновенно разбилось о реалии: давно висящий у 10gen тикет на блокировки на уровне коллекции (ещё тикет и ещё тикет) и крайне медленная конкурентная вставка документов при большом количестве составных индексов сделали своё чёрное дело: после множества экспериментов база была с громкими матюками отправлена в утиль. Казалось бы, навсегда. Но как часто бывает в жизни: для каждой задачи — свой инструмент. И MongoDb дождалась своего часа.
Почему MongoDB?
Для поставленной задачи именно Монга с её schema-less и document-oriented подошла как нельзя лучше: каждый отель мы представляем как документ с произвольным набором атрибутов и (что важно!) с возможностью хранить массивы значений для каждого из атрибутов. Это значит, что мы можем хранить списки сервисов и других параметров, которые могут принимать несколько значений одновременно, в массивах внутри документа, проиндексировать их и делать произвольные поиски по коллекции документов. Конечно же, кроме MongoDB рассматривались варианты других NoSQL баз данных, но именно Монга покорила своей простотой и возможностью хранить и производить индексрованный поиск по коллекциям внутри документов.
Привожу обрезанную (привет, NDA) структуру документа, описывающего отель:
"_id" : ObjectId(),
"hotel_id" : int,
"country_id" : int,
"city_id" : int,
"category_id" : int,
"services" : [int, int, int...]
По крону эта коллекция обновляется на основании информации из главной базы данных с помощью Монговского upsert.
И из этой коллекции нет никаких проблем получить список отелей с произвольным набором фильтров. Например:
- {country_id: 1, services: {$all: [10, 20]}} — все отели из страны 1, у которых есть сервис 10 и 20 одновременно.
- {category_id: 5, services: {$in: [20, 30]}} — все отели категории 5, у которых есть сервис 10 или 20.
Точно такие же фильтры формируются не только для сервисов, но и для всех остальных параметров, описывающих отель. Таким образом, мы избегаем необходимости писать десятиэтажные запросы на SQL к основной базе данных. При этом, производительность остаётся на очень высоком уровне, т.к. с относительно статичным коллекциями на тысячи или десятки тысяч документов при наличии разумных составных индексов и достаточного количества оперативной памяти, MongoDB справляется замечательно.
Отлично! А при чём тут MapReduce?
Итак, после разбора параметров GET-запроса с фильтрами мы можем сделать запрос в MongoDb на получение списка отелей. Тут подходит очередь формирования списка фильтров и получения количества отелей, которые попадают под каждый из фильтров. Инструмент очевиден из названия статьи: MongoDB&MapReduce.
Я не буду долго расписывать теорию MapReduce. Напомню лишь, что данный подход к обработке данных состоит из двух этапов: мэппингу и свёртке. Причём, каждый этап может происходить параллельно на нескольких ядрах/процессорах/серверах/кластерах и работать над единым массивом данных. По мере подготовки данных операцией мэппинга, через shared-memory (в нашем случае с Монгой) эти данные попадают в свёртку, где проходят окончательную обработку и превращение в искомый массив.
Понимая эту теорию, на практике всё получается на удивление просто. Привожу исходный код методов map и reduce:
var map = function() {
emit({"category": this.category_id}, 1);
if (this.services)
this.services.forEach(function(value) {
emit({"service": value}, 1);
});
if (this.types)
this.types.forEach(function(value) {
emit({"type": value}, 1);
});
// ….................................
// And a large number of other filters
};
var reduce = function(key, values) {
return Array.sum(values);
};
Как это работает?
Очень просто!
В функцию мэппинга попадает каждый из отелей, хранящиеся в базе MongoDb и для каждого из сервисов/типов питания/расположения отеля (и так далее по списку) вызывается функция emit(), которая складывается в ассоциативный массив в памяти циферку “1” для каждого из сервисов.
Функция свёртки до предела простая: суммирование цифр количества для каждого из элементов ассоциативного массива, полученного на этапе мэппинга.
Вот и всё!
На выходе мы получаем массив из всех сервисов с просчитанными количествами отелей для каждого из сервиса. Учитывая, что эта вся операция отлично параллелится, то скорость формирования этого массива получается доли секунды. Ну и не забываем о кешировании, естественно. В нашем случае кеширование может использоваться во всю ширь, т.к. информация относительно статична, выборка занимает немного места и её можно спокойно складывать в memcached по ключу из хеша Whirlpool на базе исходного GET-запроса.
Основная хитрость состоит в том, что функцию MapReduce можно применять для части коллекции отелей. Т.е. мы можем тот же запрос, что был сформирован для получения списка отелей, использовать при вызове функции MapReduce и производить все действия зачастую на очень небольшом итоговом количестве отелей. Как побочный эффект этого подхода, мы в массиве с сервисами получаем только те сервисы, который есть у отелей в искомой выборке и получаем возможность очень просто на фронте сайта отобразить только те сервисы, которые имеются у отелей в текущей выборке, исключая варианты-пустышки, что в конечном итоге положительно сказывается на юзабилити.
Можно ли оптимизировать?
Да, можно. Дело в том, что при обработке большого количества отелей (скажем, 100 тысяч) и при условии, что каждый отель имеет наборы из суммарно 100 значений параметров, то будет произведено 10 миллионов вызовов функции emit(), что может сказаться на производительности даже не смотря на распараллеливание. И решение нашлось:
var map = function() {
var obj = {
"categories": {},
"services": {}
// Other params
};
if (this.category_id > 0)
obj.categories[this.category_id] = 1;
var attrs = ["services", "types"];
for (var i = 0; i < 2; i++) {
var attrKey = attrs[i];
var attrsArray = this[attrKey];
for (var key in attrsArray) {
obj[attrKey][attrsArray[key]] = 1;
}
}
emit("attrs", obj);
};
var reduce = function(key, values) {
var obj = {
"categories": {},
"services": {}
// Other params
};
var attrs = ["categories", "services"];
for (var j = 0; j<2; j++) {
attrObjArray = [];
for (var i = 0; i < values.length; i++) {
attrValuesArray = values[i][attrs[j]];
for (var attrKey in attrValuesArray) {
var val = parseInt(attrValuesArray[attrKey]);
if (!attrObjArray[attrKey]) {
attrObjArray[attrKey] = val;
} else {
attrObjArray[attrKey] += val;
}
}
}
finalAttrObj = {};
for (i = 0; i < attrObjArray.length; i++) {
var val = attrObjArray[i];
if (val) {
finalAttrObj[i] = val;
}
}
obj[attrs[j]] = finalAttrObj;
}
return obj;
};
В оптимизированном решении вместо нескольких emit на каждой операции маппинга производится упаковка параметров отеля в объект, который передаётся в emit, где производится распаковка, подсчёт и свёртка. Визуально решение получилось значительно тяжелее, но количество свёрток уменьшается до числа отелей. Естественно, за счёт более тяжёлых операций упаковки и распаковки объектов. Как следствие, эффективно это решение будет работать только на очень больших выборках отелей и гарантированно проигрывает на выборках до 10 тысяч отелей. Исходя из реалий нашего проекта было принято решение не нагромождать код лишними проверками и вызовами разных типов MapReduce для каждого случая и оставить этот метод “про запас”.
Что дальше?
Конечно же, в данной статье изложены только базовые принципы получения выборки отелей и построения системы фильтрации, изначально сильно упрощённой через предположение, что цена на отель так же хранится в MongoDB. На самом деле всё несколько сложнее и настоящая магия начинается, когда пользователь указывает фильтр по цене и появляется необходимость найти все отели, попадающие под фильтры сервисов и с ценой на заданное количество людей/ночей/даты из заданного промежутка. Особенно учитывая, что цены на отели берутся с помощью запроса к REST-сервису. Эту магию работы с многосотмилионными БД и как при этом добиться респонза максимум в 100мс на холодном кеше и самых тяжёлых запросах я так же планирую потихоньку раскрывать в следующих статьях.
Итого
С помощью MongoDB и MapReduce получилось создать очень лёгкое по используемым ресурсам, крайне простое в понимании и отлично масштабируемое решение.
Буду рад вопросам!
Спасибо за внимание!
This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at fivefilters.org/content-only/faq.php#publishers. Five Filters recommends: 'You Say What You Like, Because They Like What You Say' - http://www.medialens.org/index.php/alerts/alert-archive/alerts-2013/731-you-say-what-you-like-because-they-like-what-you-say.html
Комментариев нет:
Отправить комментарий