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.
