Мне кажется очень интересным то, что делается в компании Google в области управления структурированными данными. Хотя все исследовательские работы имеют выраженную практическую направленность, по сути, в них делаются попытки решения очень важных фундаментальных проблем. Небольшая статья, пересказ которой предлагается вашему вниманию, написана не слишком хорошо, похоже, что некоторые разделы писались просто наспех. Боюсь, что в моем пересказе эти дефекты оригинала полностью устранить не удалось. Тем не менее, материал заслуживает внимания, поскольку позволяет хотя бы вчерне понять, что же реально делают исследователи компании Google в настоящее время.

Сергей Кузнецов

1. Введение

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

В ранние годы Google управление структурированными данными требовалось, главным образом, для хранения и обработки данных, связанных с рекламой. Однако, по мере того, как компания переходит к поддержке размещаемых приложений (hosted application), и над потоками запросов и индексами производится все более сложный анализ, управление структурированными данными становится ключевой инфраструктурой во всех частях компании.

В статье описывается лишь часть проектов, выполняемых в настоящем время. Кроме того, помимо авторов статьи, в проектах, относящихся к управлению структурированными данными, участвуют и другие исследователи, в частности, Роберто Баярдо (Roberto Bayardo), Омар Бенжелоун (Omar Benjelloun), Вингеш Ганапати (Vignesh Ganapathy), Йосси Матиас (Yossi Matias), Роб Пайк (Rob Pike) и Рамакришнан Срикант (Ramakrishnan Srikant).

В разд. 2 и 3 описываются проекты, целью которых является обеспечение возможности поиска в коллекциях структурированных данных, уже существующих в Web. В разд. 2 описываются работы, направленные на обеспечение индексации контента, доступного только через Web-формы, а в разд. 3 – начальное состояние исследований, ориентированных на поддержку поиска в HTML-таблицах. В разд. 4 обсуждаются исследования, посвященные анализу больших коллекций данных и социальных графов. В разд. 5 и 6 описывается текущее состояние дел в области BigTable, основной инфраструктуре Google для хранения структурированных данных.

2. Поиск в «Глубокой Паутине» (Deep Web)

Джаянт Мадхаван и Элон Хэлеви

«Глубокой Паутиной» называется контент, доступный только через HTML-формы. Чтобы получить Web-страницу из Deep Web, пользователь должен заполнить поля некоторой формы допустимыми входными значениями. Поскольку поисковые агенты для обнаружения Web-страниц полагаются, прежде всего, на гиперссылки, они не могут достичь страниц Глубокой Паутины, и, следовательно, эти страницы остаются не проиндексированными поисковыми машинами. Глубокая Паутина является существенной брешью в зоне действия поисковых машин, и многие люди считают, что в Deep Web содержится намного больше данных, чем во Всемирной Паутине, доступной для поиска в настоящее время. В Глубокую Паутину входит много высококачественных сайтов, в частности, системы поиска магазинов (store locator) и правительственные сайты. Поэтому исследователи хотели бы расширить зону действия поисковой машины Google, включив в нее Web-страницы из Deep Web.

Имеются два взаимодополняющих подхода к обеспечению доступа к контенту Глубокой Паутины. Первый подход, опирающийся, по сути, на интеграцию данных, состоит в создании вертикальных поисковых машин для конкретных прикладных областей (например, автомашины, книги, недвижимость). При применении этого подхода можно было бы создать для данной предметной области некоторую форму-посредника (mediator form) и производить семантические отображения между отдельными источниками данных и этой формой-посредником. В масштабе Web этот подход страдает несколькими недостатками. Во-первых, требуются большие расходы на построение и поддержку форм-посредников, а также на осуществление отображений. Во-вторых, исключительно сложной проблемой является определение по запросу на основе ключевых слов релевантной предметной области и форм внутри этой области. Наконец, даже если не говорить о наличии многих разных языков, во Всемирной Паутине содержатся данные обо всем на свете, границы предметных областей четко не определены, и создание схемы-посредника для всего на свете будет громадной проблемой.

При применении второго подхода, иногда называемого подходом выявления скрытого контента (surfacing approach), производится предварительное вычисление наиболее уместных вариантов заполнения форм для всех интересных HTML-форм. После этого результирующие URL могут быть проиндексированы подобно любым другим страницам HTML. Важно то, что этот подход позволяет использовать существующую инфраструктуру поисковых машин и, следовательно, допускает органичное включение страниц Глубокой Паутины в результаты поиска в Web. По этим причинам исследователи Google предпочитают опираться на подход выявления скрытого контента. Целью авторов является привлечение нового трафика к сайтам Deep Web, которые до сих пор посещались только в тех случаях, когда люди знали о соответствующих формах, или сами формы появлялись в результатах поиска. Поэтому не слишком существенно получить от этих сайтов ответы на все возможные заполненные формы, достаточно получить столько результатов, чтобы их хватило для увеличения трафика. Кроме того, предварительно вычисленные варианты форм способствуют дальнейшему раскрытию соответствующего сайта: после индексирования начального набора страниц система просмотра страниц Web-сайтов будет автоматически использовать информацию о внутренней структуре сайта для обнаружения других страниц, представляющих интерес.

В Google разрабатывается система обнаружения скрытого контента, которая уже помогла расширить область действия поискового индекса Web-страницами, полученными на основе более миллиона HTML-форм. Имеется возможность выполнения более тысячи запросов в секунду от поисковой страницы Google.com к контенту Глубокой Паутины.

При разработке своего решения авторам пришлось преодолеть несколько проблем. Во-первых, в большом количестве форм имеются поля для ввода текста, и требуется предоставить допустимые вводные данные. Поэтому система должна подобрать для заполнения формы такие варианты наборов значений, которые позволят обнаружить наиболее полезные результирующие страницы. Для решения этой проблемы используется комбинация двух подходов. Для поисковых полей, в которых, главным образом, допускается ввод ключевых слов, возможные ключевые слова подбираются на основе анализа содержимого уже проиндексированных страниц данного Web-сайта. Для типизированных текстовых полей, в которых допускается ввод только правильно определенного набора значений, разработчики стремятся сопоставить тип текстового поля с библиотекой типов, наиболее распространенных в различных прикладных областях, например, с почтовыми индексами США.

Во-вторых, в HTML-формах обычно имеется несколько полей для ввода данных, и поэтому простая стратегия перебора полного Декартова произведения всех возможных вариантов ввода данных в каждое поле может привести к генерации очень большого числа URL. Потребность в обходе слишком большого количества URL приведет к перерасходу ресурсов обходчика Web поисковой машины, а также создаст чрезмерную нагрузку для Web-серверов, поддерживающих HTML-формы. Интересно, что при больших размерах Декартова произведения подача многих заполненных форм приводит к пустому результату, бесполезному с точки зрения индексирования. Например, в поисковой форме сайта cars.com имеется пять полей ввода данных, и при использовании подхода с Декартовым произведением появится более 200 миллионов URL, хотя в продаже на cars.com имеется всего 650000 автомашин. Авторы разработали алгоритм, который разумным образом обходит пространство поиска всех возможных вариантов заполнения формы для определения подмножества вариантов, которые, вероятно, окажутся полезными для индекса поисковой машины. В среднем для каждой формы генерируется несколько сотен вариантов заполнения. Кроме того, авторы полагают, что число генерируемых вариантов заполнения формы должно быть пропорционально размеру базы данных, на которую опирается соответствующий сайт, а не числу полей ввода и потенциально возможных вариантов их заполнения.

В-третьих, решения должны масштабироваться и не зависеть от прикладной области. В Web имеются миллионы потенциально полезных форм. Для любой заданной формы можно было бы привлечь эксперта, который вручную определил бы наилучшие варианты ее заполнения, но такое решение не было бы масштабируемым. Целью авторов являлось нахождение полностью автоматического решения, которое можно было бы применить к любой Web-форме на любом языке и в любой прикладной области. В настоящее время разработанная система может работать более чем с миллионом форм, представленных на более чем 50 языках и относящихся к сотням прикладных областей.

Индексировались только информационные сайты с формами. Принимались меры предосторожности во избежание любых форм, для которых требуется какая-либо персональная информация, и/или которые могут обладать какими-либо побочными эффектами. Например, не анализировались формы, в которых используется метод POST, требуется ввод паролей или содержатся такие ключевые слова, как username, login и т.д.

Хотя при использовании метода выявления скрытого контента генерируется значительный трафик к сайтам Глубокой Паутины, остается большое число форм, автоматический анализ которых представляет серьезную проблему. Например, во многих формах активизируются события JavaScript при наличии тегов onselect и onsubmit, что позволяет выполнять произвольный код JavaScript. Такие ситуации являются камнем преткновения для автоматического анализа.

Кроме того, во многих формах имеются взаимосвязанные входные данные, и для доступа к таким сайтам требуется корректно (и автоматически) определить базовые зависимости между этими данными. Эффективное решение этих и других проблем в масштабе миллионов сайтов является частью продолжающейся работы авторов по обеспечению большей доступности Глубокой Паутины для пользователей поисковых машин. В заключение авторы отмечают, что еще одним механизмом, позволяющим контент-провайдерам предоставить поисковым машинам списки URL и XML-файлы и, тем самым, раскрыть содержимое Глубокой Паутины, являются карты сайтов. Сегодня во всех основных поисковых машинах поддерживается протокол карт сайтов, описанный на сайте www.sitemaps.org. Контент, обеспечиваемый картами сайтов, дополняет контент, автоматически обнаруживаемый с помощью методов, описанных в этом разделе статьи.

3. Поиск в HTML-таблицах

Майкл Кафаррела и Элон Хэлеви

Всемирная Паутина состоит из гигантского числа неструктурированных гипертекстовых документов, но также содержит и структурную часть в форме HTML-таблиц. В некоторых из этих таблиц содержатся данные, представленные в реляционном стиле. Строки таких таблиц похожи на кортежи, и таблицы обладают схемой, которая явно не определяется, но часто является очевидной для наблюдателя. На самом деле, эти HTML-таблицы являются наиболее крупным собранием реляционных баз данных (в Web имеется более 100 миллионов баз данных, обладающих двумя миллионами различных схем). Проект WebTables направлен на то, чтобы обеспечить возможность извлечения из HTML-таблиц высококачественных отношений, разрешить запрашивать из них данные и строить на основе этих уникальных наборов данных новые приложения баз данных.

Первая задача WebTables состоит в получении высококачественных отношений при обходе Web. Процедура получения отношений состоит из двух шагов. На первом шаге WebTables отфильтровывает HTML-таблицы, не содержащие реляционных данных (например, таблицы, используемые для компоновки страниц). На втором шаге для таблиц, прошедших через реляционный фильтр, WebTables формирует метаданные схемы, такие как типы и имена столбцов. У разработчиков HTML нет возможности надежным образом указать, является ли таблица реляционной, или формально определить реляционные метаданные. Система WebTables должна полагаться на совокупность неявных подсказок. Например, в таблицах, используемых для компоновки страниц, часто содержатся очень длинные и насыщенные текстом ячейки, а таблицы с реляционными данными обычно содержат более короткие ячейки, не слишком различающиеся по длине. Аналогично, одним из признаков того, что разработчик таблицы вставил в нее «строку-заголовок», является то, что первая строка состоит только из строк символов, а у остальных строк столбцы имеют другие типы.

Вторая проблема проекта WebTables состоит в разработке средства запросов, обеспечивающего простой доступ более чем к сотне миллионов уникальных баз данных, обладающих более двумя миллионами уникальных схем. Авторы создают «поисковую машину для структурированных данных», при использовании которой пользователи вводят текстовый поисковый запрос, и поисковая машина возвращает не список URL, а список баз данных, упорядоченный в порядке уменьшения релевантности. После того как пользователь выбрал релевантную базу данных, он может применить более традиционные средства структурированных запросов (такие как выборка, проекция и т.д.). Кроме того, поисковая машина может автоматически применить некоторые структурированные операции, не дожидаясь действий пользователя. Например, WebTables может проанализировать содержимое таблицы и попытаться сгенерировать ее некоторое наглядное представление, соответствующее данной предметной области и являющееся «интересным». Это представление отображается в результате запроса вслед за ссылкой на данную таблицу.

Наконец, в проекте WebTables совокупность восстановленных баз данных используется для построения ряда новых приложений. Пока разрабатываются два таких приложения. Первое из них – это автоматическое восполнение схемы (schema autocomplete). Пользователь вводит один или несколько желательных атрибутов данных (например, «name»), а приложение автоматически предлагает вариант оставшейся части схемы (например, «address», «city», «zip», «phone» и т.д.). Второе предложение – нахождение синонимов (synonym finding). Это средство автоматически определяет, какие имена атрибутов таблиц являются синонимами (например, «song» и «title», «telephone» и «tel-#»). Затем эти данные могут использоваться для улучшения сопоставления схем. Оба эти инструмента основываются на статистике использования имен атрибутов, вычисляемой на совокупности восстановленных баз данных.

В настоящее время WebTables находится в работоспособном состоянии, но авторы считают, что имеется много вопросов, заслуживающих дальнейших исследований. Можно улучшить эффективность существующих шагов (например, точность восстановления отношений и качество ранжирования баз данных), расширить набор допустимых входных данных (обрабатывая не только простые HTML-таблицы, но также и HTML-списки и электронные таблицы Excel) и построить новые приложения (например, приложение, обеспечивающее варианты возможных данных, «вертикальный» аналог приложения автоматического восполнения схемы). Имеется также ряд вопросов, связанных с представлением Web, ориентированным на данные. Например, исследуется возможность автоматического нахождения соединений между структурированными данными, восстановленными из разных Web-страниц. Например, для нахождения информации о том, где находятся мировые лидеры, можно было бы соединить таблицу стран и их столиц с таблицей стран и их премьер-министров.

Проекты WebTables и Deep-Web Crawl являются частями более обширного исследования в областях пространств данных [6] и интеграции неполных и неточных данных в качестве основы построения систем пространств данных. Некоторые ранние работы в этих областях описаны в [4, 5, 8].

4. Продукты для крупномасштабного интеллектуального анализа данных и поддержки сообществ

Эдвард Чанг

В этом разделе описываются работы по созданию масштабируемых алгоритмов интеллектуального анализа Web-данных и социальных графов. Этими проектами руководит Эдвард Чанг, возглавляющий Google Research в Китае. На основе масштабируемой инфраструктуры интеллектуального анализа данных инженерная группа разрабатывает и внедряет два продукта поддержки социальных сетей. Работа этой группы привела к радикальному сокращению объема спама в результатах алгоритма PageRank в Китае (от 5% в 2006 г. до 1% в настоящее время).

Исследовательская работа фокусировалась на параллелизации шести критически важных алгоритмов машинного обучения: методов опорных векторов (Support Vector Machines, SVMs), декомпозиции сингулярных векторов (Singular Vector Decomposition, SVD), спектральной кластеризации (Spectral Clustering), поиска ассоциаций (Association Mining), вероятностного латентно-семантического анализа (Probabilistic Latent Semantic Analysis, (PLSA) и латентного размещения Дирихле (Latent Dirichlet Allocation, LDA). Целью распараллеливания этих алгоритмов являлось использование массивного распределенного хранилища данных и вычислительных сервисов Google. В частности, эта группа выполнила распараллеливание алгоритма SVMs [1] и сделала полученную программу публично доступной вместе с исходным текстом по лицензии Apache.

Алгоритм SVMs широко используется при решении задач классификации из-за своей строгой теоретической обоснованности и успешного практического применения. К сожалению, этому алгоритму свойственны проблемы масштабируемости по отношению к использованию памяти и времени вычислений. Для преодоления этих проблем разработан параллельный вариант алгоритма SVMs (PSVM). PSVM позволяет сократить требуемый объем памяти за счет выполнения приближенной построчной факторизации матриц и загрузки на каждую из параллельно работающих машин только существенных данных. Время вычислений сокращается за счет разумного переупорядочивания последовательностей вычислений и выполнения их на параллельных машинах. Кроме того, PSVM поддерживает отказоустойчивые вычисления для обеспечения возможности восстановления после отказов компьютеров-узлов.

Что касается вычислительной сложности, то пусть n обозначает число учебных образцов, p – размерность сжатой матрицы после факторизации (p значительно меньше n) и m – число машин. Если сравнивать PSVM с методом внутренних точек (Interior Point Method, IPM), то он позволяет сократить требования к памяти от O(n↑2) до O(np/m) и требует времени вычислений O(np↑2/m). Например, задача, решавшаяся на одной машине семь дней, на основе PSVM решается на 200 машинах за два часа. В настоящее время PSVM используется внутри Google для опознания распространяющих спам и предосудительных Web-сайтов. Поскольку реализация PSVM была сделана общедоступной, широко распространено скачивание кода.

Кроме PSVM, внутри Google доступны для использования параллельные версии алгоритмов SVD, PLSA и LDA. Эти алгоритмы полезны для решения задач классификации и совместного фильтрования (collaborative filtering). Что касается классификации, то PLSA применяется для обеспечения тегов для пользовательских запросов, коротких сообщений и пользовательских постов. В связи с совместным фильтрованием PLSA и LDA используются для поддержки различных средств рекомендаций, например, советов от друзей и экспертов, рекомендаций от форумов и подбора рекламы. Совместно эти два алгоритма применяются в двух продуктах, которые описываются ниже.

Первый продукт – это Knowledge Search, который сначала был запущен в России, потом в Китае [12], а теперь запускается в нескольких других странах. Knowledge Search позволяет пользователям публиковать вопросы, а затем подбирает экспертов для своевременного ответа на вопросы. Отличительными чертами этого продукта по сравнению с конкурирующими продуктами являются обеспечение оперативной классификации вопросов, рекомендации родственных вопросов и подбор экспертов с учетом темы вопроса. Все эти возможности поддерживаются вышеупомянутой инфраструктурой машинного обучения.

Второй продукт – это Laiba, средство поддержки социальных сетей, изначально разработанное на основе Orkut. Группа сначала локализовала его, а затем быстро расширила его возможности, относящиеся, в частности, к совместному использованию фотографий и сервисам пользовательских взаимодействий. В Китае система Laiba была запущена в 2007 г. [10]. Как и Knowledge Search, этот продукт основывается на использовании крупномасштабных алгоритмов интеллектуального анализа данных для поддержки рекомендаций от друзей, сообщества или рекомендаций, основанных на контенте.

В настоящее время группа занимается дальнейшим расширением возможностей Laiba для поддержки платформы Google Open-Social [11], которая позволит подключать Laiba и другие средства организации социальных сетей к приложениям сторонних разработчиков.

5. Bigtable

Эндрю Файкс и Вильсон Се

Система Bigtable [2] разрабатывается для хранения в Google структурированных и полуструктурированных данных. (В тех случаях, когда приемлемым является интерфейс файловой системы, используется Google File System [7].) На системном уровне можно считать, что Bigtable – это распределенная, не реляционная база данных. На алгоритмическом уровне можно представлять Bigtable как распределенное многоуровневое отображение. Наконец, на реализационном уровне можно относиться к Bigtable как к некоторому варианту распределенного B-дерева. В Google Bigtable используется для хранения данных во многих разных проектах, например, в проектах индексации Web, Google Earth и Orkut.

Bigtable активно разрабатывается с конца 2003 г., и первое производственное внедрение системы было произведено в середине 2005 г. В последние несколько лет объем использования Bigtable постоянно возрастает. К январю 2008 г. в Google имелось более 600 кластеров Bigtable, и в наиболее крупном кластере содержалось более 2000 машин. В самых крупных ячейках храниться более 700 терабайт данных, и в наиболее загруженных ячейка выполняется до 100 тысяч операций в секунду.

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

• Отказоустойчивость. Программное обеспечение Bigtable выполняется на большом количестве машин, достаточно большом, чтобы можно было почти гарантировать присутствие дефектной аппаратуры (одной из наиболее распространенных проблем является неисправная основная память). Исследуются более совершенные способы решения этих проблем, не слишком сильно вредящие производительности.

• Совместное использование машин пользователями. Хотя в интерфейсе Bigtable имеются средства поддержки нескольких пользователей, в реализации пока еще не обеспечивается достаточная изоляция пользователей. Продолжается работа по развитию возможностей Bigtable управления ресурсами и изоляции пользователей.

• Репликация между центрами данных. В настоящее время пользователи Bigtable могут установить режим отложенной (lazy) репликации своих таблиц (которые могут размещаться в разных центрах данных). Эта система репликации гарантирует уровень согласованности, достаточный для многих пользователей. Однако для некоторых клиентов (в частности, тех, которые создают продукты для конечных пользователей) требуются более строгие гарантии согласованности и доступности данных. Для предоставления таких гарантий разрабатываются дополнительные средства как поверх Bigtable, так и внутри системы.

• Присоединение вычислений к данным. Для поддержки длительных вычислений, в которых требуется доступ к данным в Bigtable, разрабатывается API, позволяющий пользователям выполнять код на тех же машинах, в которых хранятся данные. Хотя в инфраструктуре Map-Reduce [3] обеспечивается некоторая поддержка выполнения вычислений поблизости от данных, в ней не предоставляются какие-либо строгие гарантии.

• Более выразительные запросы. В Bigtable не поддерживается SQL. В настоящее время для формулировки запросов используется разработанный в Google язык Sawzall [9], позволяющий задавать условия фильтрации данных на стороне сервера. По разным причинам это средство использовать неудобно, и для описания даже простых фильтров требуется изрядный объем работы. В настоящее время реализуется небольшой язык, в котором будет поддерживаться большинство разновидностей фильтров, требуемых пользователям.

• Прямая поддержка индексирования. Многие пользователи хотят хранить в Bigtable индексированные данные. В настоящее время им приходится самим управлять индексами. Ведется работа по встраиванию поддержки индексов непосредственно в Bigtable.

Большинство этих возможностей добавляется прямо в систему Bigtable, но некоторые из них создаются на уровне клиентов поверх Bigtable. Например, в проекте Megastore создаются более общие средства поддержки транзакций, согласованной репликации и DAO (Data Access Objects). Хотя Bigtable не является базой данных, большая часть добавляемых возможностей хорошо знакома сообществу баз данных, что не удивительно, если учитывать полезность этих возможностей. Интересно то, что проектирование и реализация Bigtable заняли всего 1-2 года, и это привело к созданию высокопроизводительной, сильно распределенной системы хранения данных.

6. Minitable: взятие образцов из Bigtable

Альберто Лернер и С. Мутукришнан

Как описывалось выше, Bigtable является высокопроизводительной, распределенной системой хранения строчных данных, которая является хорошо масштабируемой, но не поддерживает обработку реляционных запросов или сложное индексирование. Поэтому при некоторых видах доступа возникает потребность в объемных параллельных просмотрах данных. Хотя в инфраструктуре Google такие просмотры поддерживаются достаточно хорошо, имеются случаи, в которых желательно работать с образцом (sample) данных из Bigtable. В этом разделе обсуждаются проблемы и перспективы построения такого средства взятия образцов.

Каждой строке данных (row) в Bigtable соответствует уникальная символьная строка (string), называемая именем строки данных (rowname), и данные каждой такой строки распределяются по ряду семейств столбцов (column family). Семейство столбцов может состоять из переменного числа реальных столбцов. Поскольку Bigtable является разреженной структурой данных, для заданного запроса любая строка данных может существовать или не существовать в зависимости от того, какие запрашиваются столбцы. Данные поддерживаются в лексикографическом порядке, но столбцы могут сохраняться как вместе, так и по отдельности. Из-за наличия такой семантики и схемы хранения невозможно пропустить N строк без их реального чтения. Даже число строк в Bigtable в любой момент времени можно определить только в вероятностном смысле. С другой стороны, поскольку в Bigtable не поддерживаются реляционные запросы, не требуется принимать во внимание, какие методы сэмлинга пригодны для различных реляционных операций (например, соединений), или каким образом следует учитывать ошибки взятия образцов при возрастании сложности структуры запросов.

Однородное случайное взятие образцов (Uniform Random Sampling). В применяемой схеме сэмплинга извлекается образец строк Bigtable и представляется в виде Bigtable. Полученная структура называется Minitable. Это делается для того, чтобы код, написанный для работы с Bigtable, можно было без изменений выполнять над образцом.

Сэмплинг основывается на схеме хэширования. Подбирается удобная хэш-функция, отображающая пространство имен строк данных в очень большое пространство ключей (например, функция ax+b mod p, где p не меньше 2128). Строки, которым соответствуют первые fp ключей, где f – относительный размер образца (доля), включаются в образец. Более формально, выбирается хэш-функция h : R −> 0..p, и если h(r) ∈ [0, fp−1], то r добавляется к образцу. Легко видеть, что ожидаемый размер образца составляет f × 100% от числа строк в Bigtable независимо от реального числа строк, и вероятность того, что данная строка r попадет в образец, равняется, как и требовалось, f. Этот метод взятия образцов, основанный на хэшировании, обеспечивает поддержку образца при каждой мутации Bigtable (вставке, модификации или удалении строк данных).

Только система может направлять уместные мутации из Bigtable в Minitable. Во всех остальных отношениях Minitable ведет себя, как любая другая Bigtable: ее можно подвергать резервному копированию и даже реплицировать. В настоящее время механизм Minitable внедряется для поддержки репозитория документов, генерируемого системой обхода Web. Поддержка нескольких Minitable с разными коэффициентами взятия образцов позволяют системе быстрее и чаще вычислять агрегаты.

Пристрастное взятие образцов (Biased Sampling). Однородный случайный сэмплинг является очень полезным, но в некоторых случаях требуются методы пристрастного сэмплинга. В настоящее время ведется работа над одним из таких расширений, называемым сэмплингом по маске (Mask Sampling). В этой схеме решение о включении строки данных в образец по-прежнему основывается на имени этой строки, но теперь пользователь может определить для этих имен маску m. Эта маска, которая может быть регулярным выражением, с которым сопоставляются части имени строки данных, используется для группирования строк. Две строки принадлежат одной и той же группе, если применение к ним маски приводит к получению одной и той же строки. При использовании сэмпинга по маске гарантируется, что если некоторая группа выбирается в образец, то эта группа будет в нем в достаточной мере представлена независимо от своих относительных размеров.

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

Более точно, данная процедура должна возвращать, возможно, не однородный образец, содержащий ‹k.m›, т.е. проекции имен строк k на маску m. Имеются, по крайней мере, две детали, делающие данную проблему интересной. Во-первых, множество разных ‹k.m› может быть большим, и из него потребуется брать образец. Если вернуться к предыдущему примеру, то для всех доменов может просто не хватить желаемого размера образца. Во-вторых, хотя имена строк данных являются уникальными, их проекции на маску часто свойством уникальности не обладают. Для каждого значения ‹k.m› имеется множество строк из Bigtable, и нужно решить, какие из них сохранять в Minitable. Если опять обратиться к примеру с таблицей Web-страниц, может потребоваться выбирать образец внутри заданного домена. Рассмотрим множество S(n) строк данных, для которых ‹k.m› = n. Тогда в идеале хотелось бы сохранять все строки r из S(n), если значение |S(n)| невелико, делать умеренную выборку при больших значениях |S(n)|, и сокращать относительный размер образца из S(n) при совсем больших значениях |S(n)|.

Для пристрастного взятия образцов можно обобщить процедуру взятия образцов с использованием хэш-функции. Как и раньше, в процедуре используется хэш-функция h1 : ‹k.m› −> [0 .. p], и в образце сохраняются те ‹k.m›, для которых h1(‹k.m›) ∈ [0, fp−1]. Затем для каждой группы S(n), для которой n было сохранено в первом образце, к полным именам строк применяется хэш-функция h2 (зависящая от n). Здесь предполагается, что имеется побочная таблица T : ‹k.m&rsaquo = n −> gn, которая на практике часто подготавливаются автономным образом или легко поддерживается в отложенном режиме. (Ее можно получить неявно, если имеется однородная Minitable.) Авторы называются эту таблицу gtable, поскольку она содержит некоторую строку для каждой группы, задаваемой маской.

На практике эта схема сэмплинга может обеспечить пристрастную Minitable с репрезентативным образцом доменов на основе Bigtable с Web-страницами. Для каждого из этих доменов будет иметься достаточно много строк, чтобы позволить, например, приближенно вычислять агрегаты, даже если для выбранных доменов сильно разнится число строк в базовой Bigtable.

Литература

[1] E. Y. Chang, K.Zhu et al. Parallelizing Support Vector Machines on Distributed Computers. Proceedings of NIPS 2007. Downloadable open source at http://code.google.com/p/psvm/.
[2] Chang, F., et al. Bigtable: A Distributed Storage System for Structured Data. In Proc. of the 7th OSDI (Dec. 2006), pp. 205–218
[3] Dean, J., and Ghemawat, S. MapReduce: Simplified data processing on large clusters. In Proc. of the 6thOSDI (Dec. 2004), pp. 137–150
[4] Dong X. and Halevy A. Indexing Dataspaces. In Proc. of the International Conference on Management of Data (SIGMOD), pp. 43-54, 2007
[5] Dong X., Halevy A., and Yu C. Data Integration with Uncertainty. International Conference on Very Large Databases (VLDB), pp. 687-698, 2007
[6] Franklin M., Halevy A., and Maier D. From databases to dataspaces: a new abstraction for information management. SIGMOD Record, 34(4): 27-33, 2005. Есть перевод на русский язык: Майкл Франклин, Элон Хэлеви, Дэвид Майер. От баз данных к пространствам данных: новая абстракция управления информацией
[7] Ghemawat, S., Gobioff, H., and Leung, S.-T. The Google file system. In Proc. of the 19th ACM SOSP (Dec. 2003), pp. 29–43
[8] Madhavan J., Cohen S., Dong X., Halevy A., Jeffery S., Ko D., and Yu C. Web-Scale Data Integration: You can only afford to Pay as You Go. Proceedings of CIDR, pp. 342-350, 2007
[9] Pike, R., Dorward, S., Griesemer, R., and Quinlan, S. Interpreting the data: Parallel analysis with Sawzall. Scientific Programming Journal 13, 4 (2005), 227–298
[10] http://liaba.tianya.cn.
[11] Google Open Social
[12] http://otvety.google.ru/otvety/. http://wenda.tianya.cn