Map/Reduce вместо JOIN

[ermouth]

Полгода назад morfizm написал хороший пост про то, как работают технологии map/reduce для распараллеливания обработки больших объёмов данных.

Мне есть что к той истории добавить – все системы, что я построил за последний год, используют map/reduce для сортированной/группированной выборки данных из NoSQL БД. В силу целого ряда вкусностей мы используем CouchDB и примеры будут ближе к ней, но в остальных NoSQL БД принцип примерно такой же.

С помощью применения map/reduce практически любая сложная выборка по набору JSON-документов (деревья, не таблица) успешно приводится к простой выборке (цепочке выборок) диапазона ключей. В общем, для этого достаточно только map, про reduce я в следующий раз напишу.

Работает это так.

Пусть у нас есть БД с постами и комментами, то-есть с набором документов примерно такой структуры:

{type:"post", _id:"", author:"", title:"", stamp:0, content""}
{type:"comment", parentId:"", _id:"", author:"", title:"", stamp:0, content""}

Например, мы хотим выбирать сразу посты и комменты к ним за диапазон дат. Для такой выборки достаточно одной map-функции.

function Feed (doc) {
  if (doc.type==="post") {
    emit ([doc.id, 0], doc    );
    emit ( doc.stamp , doc._id);
    //       _↑_        __↑__
    //       key        value
  }
  if (doc.type==="comment") emit ([doc.parentId, 1], doc)
}

Наша map-функция, в зависимости от типа документа, эмитит пары ключ-значение. Для поста мы эмитим сразу две пары, а для коммента – одну.

Заметим, что разные комменты к одному конкретному посту эмитят себя по одинаковому ключу. Также заметим, что ключ может быть не только string, но и array.

Если пройтись этой функцией по нашей БД, мы на выходе получим набор пар ключ-значение со следующими свойствами:

1. Выбор из этого набора диапазона ключей startStamp … endStamp даст на выходе айдишники постов в этом диапазоне дат.


2. Выбор потом ключей вида
   [postId1, 0], [postId1, 1], [postId2, 0], [postId2, 1], [postId3, 0], [postId3, 1]…
   отдаст нам сразу и посты, и все комменты к ним.

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

Важный момент. Наша map-функция устроена так, что её результаты можно кэшировать и обновлять кэш не фуллсканом, а по частям, только когда обновился конкретный документ. Вычисление map-функций над набором доков прекрасно параллелится.

CouchDB именно так и делает. Над каждой базой можно создать набор именованных индексов, в которых хранятся результаты вычисления различных предопределённых map-функций. Выбирать из БД можно как по ID документов, так и по ключам результатов работы этих функций.

Индексы хранятся как B-tree, соответственно с рождения заточены под выбор диапазонов.

Чуток усложнив ключи с таймстампом – скажем, до [doc.author, doc.stamp], мы сможем выбирать посты конкретного автора. Диапазоны выборки ключей для первого запроса будут выглядеть тогда примерно так:  ["ermouth", 1420000000000] … ["ermouth", 1420014425025].

К такой схеме выборки после SQL пришлось некоторое время привыкать – но когда к ней приспособишься, оказывается, что она куда богаче SQL по возможностям одного только map.

На этой прекрасной ноте заканчиваю 2014 год.

Всем счастья, радости и приятных ништячков в 2015! Ушёл готовить оливье.