Б Бёрнс - Распределенные системы. Паттерны проектирования

Теперь вместо того, чтобы искать совпадения во всех доку-ментах, совпадение отдельного слова можно найти простым ассоциа тивным поиском. Правда, за счет этого теряется одна важная возможность. Помните, что мы ищем все документы, в которых есть слова «кот» и «собака». Поскольку индекс со-

держит только единичные слова, а не наборы слов, все равно придется искать документы, включающие оба слова. К счастью, их множество представляет собой пересечение множеств доку-ментов, содержащих отдельные слова.

Такой подход позволяет использовать поиск по документам в качестве примера реализации паттерна Scatter/Gather. Когда корневой узел получает поисковый запрос, он выделяет в нем термы и распределяет его выполнение на две машины (одной — слово «кот», а второй — «собака»). Каждая из машин возвраща-ет список документов, соответствующих ее поисковому терму, а корневой узел возвращает список документов, содержащих оба терма.

126Часть II. Паттерны проектирования обслуживающих систем Схематически процесс показан на рис. 7.2: терминальный узел, искавший слово «кот», возвращает множество {doc1, doc2, doc4} , а узел, искавший слово «собака», возвращает множество {doc1, doc3, doc4} . Корневой узел затем ищет пересечение этих множеств и возвращает пользователю множество {doc1, doc4} .

Рис. 7.2. Пример поисковой системы Scatter/Gather с шардированиемпо термам поискового запроса

Scatter/Gather с шардированием терминальных узлов

Хотя при применении реплицированного варианта паттерна Scatter/Gather сокращается время обработки пользовательских запросов, он не позволит масштабировать сервис сверх объема данных, который можно хранить в памяти или на диске одной Глава 7. Паттерн Scatter/Gather 127

машины. Как и в случае с ранее рассмотренным примером ре-плицированного сервиса, нетрудно построить реплицированную Scatter/Gather-систему. Но по достижении определенного объ-ема данных становится необходимым вводить шардирование, чтобы иметь возможность обрабатывать больше данных, чем может уместиться на одной машине.

Ранее, когда шардирование вводилось для масштабирования реплицированных систем, оно осуществлялось на уровне от-дельных запросов. Для определения того, на какой узел напра-вить запрос, использовался некоторый его фрагмент. Этот узел

впоследствии полностью обрабатывал запрос и выдавал ответ пользователю. В случае шардирования Scatter/Gather, напро-тив, запрос отправляется всем терминальным узлам (шардам) в системе. Каждый терминальный узел обрабатывает запрос, используя данные, содержащиеся в своем шарде. Частичный ответ возвращается корневому узлу — он объединяет все ча-стичные ответы в один полный ответ, который и возвращается пользователю.

В качестве конкретного примера такой архитектуры рассмотрим реализацию поиска в большом массиве документов (например, среди всех патентов в мире). Такой массив данных слишком велик для одной машины, поэтому данные шардируются среди нескольких экземпляров сервиса. Первые 100 тысяч патентов, к примеру, могут находиться на первой машине, вторые 100 ты-сяч — на второй и т. д. Заметьте, подобная схема шардирования плоха тем, что по мере регистрации новых патентов придется добавлять в систему новые шарды. На практике следует исполь-зовать остаток от деления номера патента на общее количество шардов. Когда пользователь делает поисковый запрос по всем патентам с определенным словом (к примеру, «ракеты»), запрос отправляется всем экземплярам сервиса, каждый из которых затем выполняет поиск совпадений в своем шарде массива 128Часть II. Паттерны проектирования обслуживающих систем патентов. В ответ на шардированный запрос все найденные совпадения возвращаются корневому узлу сервиса. Корневой узел затем объединяет все ответы в один общий ответ, который содержит все патенты, включающие определенное слово. Схема работы такого поисковика изображена на рис. 7.3.

Рис. 7.3. Выполнение запроса с конъюнкцией

в поисковой системе типа Scatter/Gather

Практикум. Шардированный поиск в документах

В предыдущем примере подзапросы отдельных термов распре-делялись по всему кластеру. Это работает только в том случае, когда все документы реплицированы на все машины в Scatter/ Gather-дереве. Если в каждом отдельном терминальном узле дерева не хватает места для хранения всех документов, прихо-дится прибегать к шардированию, чтобы разные подмножества документов хранились в разных узлах.

Глава 7. Паттерн Scatter/Gather 129

Это значит, что, когда пользователь запрашивает все документы, содержащие слова «кот» и «собака», его запрос отправляется всем терминальным узлам Scatter/Gather-дерева. Каждый тер-минальный узел возвращает набор известных ему документов, содержащих слова «кот» и «собака». Ранее корневой узел от-вечал за пересечение наборов документов, возвращенных для каждого поискового терма. В случае шардированного сервиса корневой узел отвечает за вычисление теоретико-множествен-ного объединения наборов документов, возвращенных шарда-ми, которое и является конечным результатом, отправляемым пользователю.

Еще раз посмотрите на рис. 7.3. Первый терминальный узел обслуживает документы 1–10 и возвращает {doc1, doc5} . Второй терминальный узел обслуживает документы 11–20 и возвращает {doc15} . Третий терминальный узел обслуживает документы 21–30 и возвращает {doc22, doc28} . Корневой узел объединяет ответы и возвращает множество {doc1, doc5, doc15, doc22, doc28} .

Выбор подходящего количества терминальных узлов

Может показаться, что в рамках паттерна Scatter/Gather всегда имеет смысл реплицировать вычисления на как можно большее количество узлов. Распараллеливая вычисления, вы сокраща-ете время обработки конкретного запроса. Увеличение степени распараллеливания несет с собой дополнительные расходы, поэтому для достижения максимальной производительности в распределенной системе чрезвычайно важно правильно вы-брать количество терминальных узлов.

Чтобы понять, почему так происходит, следует рассмотреть две вещи. Во-первых, обработка каждого конкретного запроса

130Часть II. Паттерны проектирования обслуживающих систем подразумевает определенные накладные расходы. Требует-ся время на анализ запроса, на его пересылку по сети и т. д. В общем случае накладные расходы на обработку запроса опе-рационной системой постоянны и сравнительно невелики по отношению ко времени обработки запроса в пользовательском режиме. Соответственно, при оценке производительности реализации паттерна Scatter/Gather ими, как правило, можно пренебречь.