Классика баз данных - статьи
Сэмплинг основывается на схеме хэширования.
Сэмплинг основывается на схеме хэширования. Подбирается удобная хэш-функция, отображающая пространство имен строк данных в очень большое пространство ключей (например, функция 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. Эта маска, которая может быть регулярным выражением, с которым сопоставляются части имени строки данных, используется для группирования строк. Две строки принадлежат одной и той же группе, если применение к ним маски приводит к получению одной и той же строки.
