Введение в представления

Что такое представление?

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

{
    "_id":"biking",
    "_rev":"AE19EBC7654",

    "title":"Biking",
    "body":"My biggest hobby is mountainbiking. The other day...",
    "date":"2009/01/30 18:04:11"
}

{
    "_id":"bought-a-cat",
    "_rev":"4A3BBEE711",

    "title":"Bought a Cat",
    "body":"I went to the pet store earlier and brought home a little kitty...",
    "date":"2009/02/17 21:13:39"
}

{
    "_id":"hello-world",
    "_rev":"43FBA4E7AB",

    "title":"Hello World",
    "body":"Well hello and welcome to my new blog...",
    "date":"2009/01/15 15:52:20"
}

Для примера достаточно трёх документов. Обратите внимание: документы отсортированы по «_id» — именно так они хранятся в базе данных. Теперь определим представление. Пока не будем ничего объяснять и просто покажем код:

function(doc) {
    if(doc.date && doc.title) {
        emit(doc.date, doc.title);
    }
}

Это функция map, написанная на JavaScript. Если вы не знакомы с JavaScript, но использовали C или любой другой язык, похожий на C, например Java, PHP или C#, этот код должен быть вам знаком. Это простое определение функции.

Вы передаёте CouchDB функции представления в виде строк, хранящихся в поле views документа дизайна. Чтобы создать это представление, можно выполнить следующую команду:

curl -X PUT http://admin:password@127.0.0.1:5984/db/_design/my_ddoc
     -d '{"views":{"my_filter":{"map":
         "function(doc) { if(doc.date && doc.title) { emit(doc.date, doc.title); }}"}}}'

Вы не запускаете функцию JavaScript самостоятельно. Вместо этого, когда вы выполняете запрос к представлению, CouchDB берёт исходный код и запускает его за вас для каждого документа в базе данных, для которой определено представление. Чтобы получить результат представления, выполните запрос к представлению следующей командой:

curl -X GET http://admin:password@127.0.0.1:5984/db/_design/my_ddoc/_view/my_filter

Все функции map имеют один параметр — doc. Это отдельный документ в базе данных. Наша функция map проверяет, есть ли у документа атрибуты date и title — к счастью, они есть во всех наших документах, — а затем вызывает встроенную функцию emit(), передавая эти два атрибута в качестве аргументов.

Функция emit() всегда принимает два аргумента: первый — key, а второй — value. Функция emit(key, value) создаёт запись в нашем результате представления. Ещё один момент: функцию emit() можно вызывать несколько раз в функции map, чтобы создать несколько записей в результатах представления из одного документа, но пока мы этого не делаем.

CouchDB помещает всё, что вы передаёте функции emit(), в список (см. таблицу 1 «Результаты представления» ниже). Каждая строка в этом списке содержит ключ и значение. И что ещё важнее, список отсортирован по ключу (в нашем случае — по doc.date). Важнейшая особенность результата представления заключается в том, что он отсортирован по ключу. Мы будем снова и снова возвращаться к этому свойству, чтобы выполнять интересные действия. Продолжение следует.

Таблица 1. Результаты представления:

Когда вы выполняете запрос к представлению, CouchDB берёт исходный код и запускает его за вас для каждого документа в базе данных. Если документов много, это занимает немало времени, и вы можете задаться вопросом, не является ли такой подход ужасно неэффективным. Да, был бы, но CouchDB спроектирована так, чтобы избегать лишних затрат: она проходит по всем документам только один раз — при первом запросе к представлению. Если документ изменяется, функция map запускается только один раз, чтобы пересчитать ключи и значения для этого документа.

Результат представления хранится в B-дереве, как и структура, отвечающая за хранение документов. B-деревья представлений хранятся в отдельных файлах, поэтому при высокопроизводительном использовании CouchDB можно разместить представления на отдельном диске. B-дерево обеспечивает очень быстрый поиск строк по ключу, а также эффективную потоковую обработку строк в диапазоне ключей. В нашем примере одно представление может ответить на любые вопросы, связанные со временем: «Покажите все записи блога за прошлую неделю», «за прошлый месяц» или «за этот год». Очень удобно.

При запросе к представлению мы получаем список всех документов, отсортированных по дате. Каждая строка также содержит заголовок записи, поэтому мы можем создать ссылки на записи. Таблица 1 — всего лишь графическое представление результата представления. Фактический результат закодирован в формате JSON и содержит немного больше метаданных:

{
    "total_rows": 3,
    "offset": 0,
    "rows": [
        {
            "key": "2009/01/15 15:52:20",
            "id": "hello-world",
            "value": "Hello World"
        },

        {
            "key": "2009/01/30 18:04:11",
            "id": "biking",
            "value": "Biking"
        },

        {
            "key": "2009/02/17 21:13:39",
            "id": "bought-a-cat",
            "value": "Bought a Cat"
        }

    ]
}

Фактический результат отформатирован не так красиво и не содержит лишних пробелов или символов новой строки, но в таком виде его удобнее читать и понимать и вам, и нам. Откуда в строках результата взялся элемент «id»? Раньше его не было. Мы просто опустили его, чтобы не запутывать вас. CouchDB автоматически добавляет в результат представления идентификатор документа, создавшего запись. Мы также используем его при создании ссылок на страницы записей блога.

Эффективный поиск

Перейдём ко второму сценарию использования представлений: «построение эффективных индексов для поиска документов по любому содержащемуся в них значению или структуре». Мы уже объяснили, как работает эффективная индексация, но пропустили несколько деталей. Сейчас самое время завершить обсуждение, рассмотрев немного более сложные функции map.

Сначала вернёмся к B-деревьям! Мы объяснили, что B-дерево, лежащее в основе отсортированного по ключу результата представления, создаётся только один раз — при первом запросе к представлению, а все последующие запросы просто читают B-дерево, не запуская функцию map заново для всех документов. Но что происходит, когда вы изменяете документ, добавляете новый или удаляете существующий? Всё просто: CouchDB достаточно умна, чтобы найти в результате представления строки, созданные определённым документом. Она помечает их как недействительные, поэтому они больше не отображаются в результатах представления. Если документ удалён, всё в порядке — итоговое B-дерево отражает состояние базы данных. Если документ обновлён, новый документ передаётся функции map, а полученные новые строки вставляются в B-дерево в нужные места. Новые документы обрабатываются таким же образом. B-дерево — очень эффективная структура данных для наших задач, и проектирование баз данных CouchDB с учётом возможности сбоев распространяется также на индексы представлений.

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

/blog/_design/docs/_view/by_date?startkey="2010/01/01 00:00:00"&endkey="2010/02/00 00:00:00"

{
    "date": "2009/01/31 00:00:00"
}

{
    "date": [2009, 1, 31, 0, 0, 0]
}

/blog/_design/docs/_view/by_date?startkey=[2010, 1, 1, 0, 0, 0]&endkey=[2010, 2, 1, 0, 0, 0]

{
    ...
    tags: ["cool", "freak", "plankton"],
    ...
}

{
    ...
    tags: [],
    ...
}

function(doc) {
    if(doc.tags.length > 0) {
        for(var idx in doc.tags) {
            emit(doc.tags[idx], null);
        }
    }
}

Представление для получения комментариев к записям

Здесь мы используем ключ-массив, чтобы поддержать параметр запроса свёртки group_level. Представления CouchDB хранятся в структуре файлов B-дерева. Благодаря устройству B-деревьев мы можем кэшировать промежуточные результаты свёртки в нелистовых узлах дерева, поэтому запросы на свёртку можно вычислять для произвольных диапазонов ключей за логарифмическое время. См. рисунок 1 «Функция map для комментариев».

В приложении блога мы используем запросы свёртки group_level для подсчёта комментариев как для каждой записи, так и в целом. Это достигается запросом к одному и тому же индексу представления разными способами. Используем массивы в качестве ключей и предположим, что у каждого ключа значение 1:

["a","b","c"]
["a","b","e"]
["a","c","m"]
["b","a","c"]
["b","a","g"]

представление reduce:

function(keys, values, rereduce) {
    return sum(values)
}

или:

_sum

это встроенная функция reduce в CouchDB (другие функции — _count и _stats). Здесь _sum возвращает общее количество строк между начальным и конечным ключами. Таким образом, при использовании startkey=["a","b"]&endkey=["b"] (включающего первые три ключа из приведённых выше) результат будет равен 3. Это позволяет подсчитывать строки. Чтобы подсчитывать строки, не учитывая их значения, можно включить параметр rereduce:

function(keys, values, rereduce) {
    if (rereduce) {
        return sum(values);
    } else {
        return values.length;
    }
}

Это представление reduce, используемое демонстрационным приложением для подсчёта комментариев. Функция map выводит сами комментарии, что полезнее, чем снова и снова получать только 1. Стоит потратить некоторое время на эксперименты с функциями map и reduce. Fauxton для этого подходит, но не предоставляет доступа ко всем параметрам запроса. Написание собственного тестового кода для представлений на предпочитаемом вами языке — отличный способ изучить особенности и возможности инкрементальной системы MapReduce в CouchDB.

В любом случае запрос group_level фактически запускает последовательность запросов свёртки по диапазонам: по одному для каждой группы, появляющейся на выбранном уровне. Повторно выведем приведённый ранее список ключей, сгруппировав его на уровне 1:

["a"]   3
["b"]   2

А теперь на уровне group_level=2:

["a","b"]   2
["a","c"]   1
["b","a"]   2

Использование параметра group=true заставляет его работать так, как если бы это был параметр group_level=999. Поэтому в нашем примере для каждого ключа будет возвращено число 1, поскольку точно повторяющихся ключей нет.

Reduce/Rereduce

Мы кратко говорили о параметре rereduce функции reduce. В этом разделе объясним, для чего он нужен. К этому моменту вы уже должны знать, что для повышения эффективности результат представления хранится в индексной структуре B-дерева. Наличие и использование параметра rereduce тесно связаны с принципом работы индекса B-дерева.

Рассмотрим результат map:

"afrikaans", 1
"afrikaans", 1
"chinese", 1
"chinese", 1
"chinese", 1
"chinese", 1
"french", 1
"italian", 1
"italian", 1
"spanish", 1
"vietnamese", 1
"vietnamese", 1

Пример 1. Пример результата представления (mmm, food)

Чтобы узнать, сколько блюд приходится на каждое место происхождения, можно повторно использовать простую функцию reduce, показанную ранее:

function(keys, values, rereduce) {
    return sum(values);
}

На рисунке 2 «Индекс B-дерева» показана упрощённая схема индекса B-дерева. Строки ключей сокращены.

Результат представления — это то, что выпускники факультетов информатики называют обходом дерева «в прямом порядке». Мы рассматриваем каждый элемент каждого узла, начиная слева. Если видим подузел, в который можно перейти, переходим к нему и начинаем читать его элементы. Когда мы обошли всё дерево, работа завершена.

Как видно, CouchDB хранит и ключи, и значения в каждом листовом узле. В нашем случае значение всегда равно 1, но в другом случае вы можете подсчитывать другие результаты, и тогда значения во всех строках будут разными. Важно то, что CouchDB передаёт все элементы узла функции reduce (устанавливая параметр rereduce в false) и сохраняет результат в родительском узле вместе со ссылкой на подузел. В нашем примере у каждой ссылки есть значение 3, представляющее результат reduce для узла, на который она указывает.

Теперь посмотрим, что произойдёт при выполнении запроса. Мы хотим узнать, сколько у нас записей со значением «chinese». Параметр запроса прост: ?key="chinese". См. рисунок 3 «Результат reduce для индекса B-дерева».

CouchDB обнаруживает, что все значения в подузле содержат ключ «chinese». Она заключает, что для вычисления итогового результата достаточно взять три значения, связанные с этим узлом. Затем она находит расположенный слева узел и видит, что в нём находятся ключи вне запрошенного диапазона (key= задаёт диапазон, начало и конец которого совпадают). CouchDB заключает, что нужно передать значение элемента «chinese» и значение другого узла функции reduce, установив параметр rereduce в true.

Во время выполнения запроса функция reduce фактически вычисляет 3 + 1 и возвращает нужный результат. В следующем примере показан псевдокод последнего вызова функции reduce с фактическими значениями:

function(null, [3, 1], true) {
    return sum([3, 1]);
}

Мы говорили, что функция reduce должна действительно сворачивать значения. Если взглянуть на B-дерево, станет очевидно, что происходит, когда значения не сворачиваются. Рассмотрим следующий результат map и функцию reduce. На этот раз мы хотим получить список всех уникальных меток в представлении:

"abc", "afrikaans"
"cef", "afrikaans"
"fhi", "chinese"
"hkl", "chinese"
"ino", "chinese"
"lqr", "chinese"
"mtu", "french"
"owx", "italian"
"qza", "italian"
"tdx", "spanish"
"xfg", "vietnamese"
"zul", "vietnamese"

Ключ нас здесь не интересует — нужно лишь вывести все имеющиеся метки. Наша функция reduce удаляет дубликаты:

function(keys, values, rereduce) {
    var unique_labels = {};
    values.forEach(function(label) {
        if(!unique_labels[label]) {
            unique_labels[label] = true;
        }
    });

    return unique_labels;
}

Это показано на рисунке 4 «Переполненный индекс reduce».

Надеемся, теперь идея понятна. Из-за принципа хранения данных в B-дереве, если функция reduce фактически не сворачивает данные, CouchDB будет копировать огромные объёмы данных, которые растут линейно или даже быстрее по мере увеличения числа строк в представлении.

CouchDB сможет вычислить итоговый результат, но только для представлений с небольшим количеством строк. При большем количестве строк построение представления будет чрезвычайно медленным. Чтобы избежать этого, начиная с версии 0.10.0 CouchDB выдаёт ошибку, если функция reduce не сворачивает входные значения.

Один или несколько документов дизайна

Часто задают вопрос: когда следует разделять представления по разным документам дизайна, а когда лучше хранить их вместе?

Каждому создаваемому представлению соответствует одно B-дерево. Все представления в одном документе дизайна хранятся в одном наборе индексных файлов на диске (по одному файлу на каждый сегмент базы данных; начиная с версии 2.0 по умолчанию — по 8 файлов на узел).

Самый практичный фактор при разделении представлений по разным документам — частота их изменения. Часто изменяемые представления, находящиеся в одном документе дизайна с другими представлениями, при записи документа дизайна делают недействительными индексы этих представлений, заставляя перестраивать их с нуля. Очевидно, в рабочей среде этого следует избегать!

Однако если в одном документе дизайна есть несколько представлений с одинаковой функцией map, CouchDB оптимизирует их и вычислит эту функцию map только один раз. Это позволяет создать два представления с разными функциями reduce (например, одно с _sum и другое с _stats), но построить только одну копию индекса map. Это также экономит место на диске и время, необходимое для записи нескольких копий.

Ещё одно преимущество хранения нескольких представлений в одном документе дизайна заключается в том, что файлы индекса могут содержать единый индекс обратных ссылок от docid к строкам. CouchDB нужны эти «обратные ссылки», чтобы делать строки представления недействительными при удалении документа (иначе при каждом удалении пришлось бы перестраивать всё представление!).

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

Итак, использовать один или несколько документов дизайна? Выбор за вами.

Что мы узнали

• Если вы не используете поле key в функции map, скорее всего, вы делаете что-то не так.

• Если вы пытаетесь получить список уникальных значений с помощью функций reduce, скорее всего, вы делаете что-то не так.

• Если функция reduce не сворачивает значения до одного скалярного значения или небольшого объекта либо массива фиксированного размера с заданным числом небольших скалярных значений, скорее всего, вы делаете что-то не так.

Итоги

Функции map не имеют побочных эффектов: они принимают документ в качестве аргумента и выдают пары ключ/значение. CouchDB хранит выданные строки, строя отсортированный индекс B-дерева, поэтому поиск строк по ключу и потоковая обработка диапазона строк выполняются с небольшими затратами памяти и вычислительных ресурсов, а при записи не требуется перемещение головки диска. Создание представления занимает O(N), где N — общее число строк в представлении. Однако запросы к представлению выполняются очень быстро, поскольку B-дерево остаётся неглубоким, даже когда содержит очень много ключей.

Функции reduce обрабатывают отсортированные строки, выданные функциями map представления. Функциональность reduce в CouchDB использует одно из фундаментальных свойств индексов B-дерева: для каждого листового узла (отсортированной строки) существует цепочка внутренних узлов, ведущая к корню. Каждый листовой узел B-дерева содержит несколько строк (обычно несколько десятков, в зависимости от размера строки), а каждый внутренний узел может ссылаться на несколько листовых узлов или других внутренних узлов.

Функция reduce запускается для каждого узла дерева, чтобы вычислить итоговое значение свёртки. В результате получается функция reduce, которую можно обновлять инкрементально при изменениях функции map, пересчитывая значения свёртки для минимального числа узлов. Первоначальная свёртка вычисляется один раз для каждого узла дерева (внутреннего и листового).

При запуске для листовых узлов, содержащих фактические строки map, третий параметр функции reduce — rereduce — имеет значение false. В этом случае аргументами являются ключи и значения, выданные функцией map. Функция возвращает одно значение свёртки, которое сохраняется во внутреннем узле, общем для рабочего набора листовых узлов, и используется в качестве кэша при последующих вычислениях reduce.

При запуске функции reduce для внутренних узлов флаг rereduce имеет значение true. Это позволяет функции учитывать, что она получит собственный предыдущий результат. Если rereduce имеет значение true, функция получает промежуточные значения свёртки, сохранённые в кэше после предыдущих вычислений. Если глубина дерева превышает два уровня, этап rereduce повторяется: обрабатываются фрагменты результата предыдущего уровня, пока в корневом узле не будет вычислено итоговое значение свёртки.

Распространённая ошибка начинающих пользователей CouchDB — попытка построить сложные агрегированные значения с помощью функции reduce. Полная свёртка должна возвращать скалярное значение, например 5, а не, скажем, JSON-объект с набором уникальных ключей и количеством каждого из них. Проблема такого подхода в том, что итоговое значение получится очень большим. Даже для большого набора число уникальных ключей может быть почти таким же, как общее число ключей. Объединить несколько скалярных вычислений в одной функции reduce вполне допустимо; например, можно вычислить сумму, среднее значение и стандартное отклонение набора чисел в одной функции.

Если вас интересуют возможности инкрементальной свёртки в CouchDB, ознакомьтесь со статьёй Google о Sawzall, в которой приведены примеры более необычных свёрток, реализуемых в системе с похожими ограничениями.