WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 | 2 || 4 | 5 |

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

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

В отличие от реляционных СУБД, BigTable не поддерживает язык SQL. Доступ к BigTable из приложений обеспечивается с помощью клиентской библиотеки, реализующей довольно простой интерфейс прикладного программирования (API).

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

BigTable-кластер состоит из главного сервера (master) и множества таблетсерверов (tablet server), которые могут динамически добавляться или удаляться из кластера. В обязанности главного сервера входит распределение таблетов по таблетсерверам, отслеживание состояния таблет-серверов, балансировка нагрузки между среверами и удаление неиспользуемых файлов. Кроме того, главный сервер управляет созданием и изменением таблиц и семейств столбцов. Каждый таблет-сервер предоставляет доступ к выделенному набору таблетов. Сервер обрабатывает запросы на чтение и запись в обслуживаемые таблеты, а также разбивает таблеты, размер которых стал слишком большим. Как и в предыдущих описанных системах, данные передаются между клиентом и таблет-сервером напрямую, минуя главный сервер. В отличие от GFS, клиенты не используют главный сервер для определения местоположения таблетов. Поэтому главный сервер обычно загружен слабо.

Для хранения информации о местоположении таблетов используется трехуровневая иерархическая структура. Первый уровень состоит из файла, содержащего адрес корневого таблета (root tablet). Данный файл размещается на высоконадежном сервисе Chubby, описанном в разделе 3.1. Отметим, что в Chubby также хранятся схемы таблиц, права доступа и другие служебные данные BigTable. В корневом таблете хранятся местоположения всех таблетов в системной таблице METADATA. В свою очередь, в таблетах METADATA хранятся адреса всех таблетов из пользовательских таблиц. Клиенты BigTable кэшируют информацию о местоположении таблетов, а также считывают сразу информацию о нескольких таблетах, что позволяет снизить число обращений к таблице METADATA.

В любой момент времени каждый таблет обслуживается одним таблет-сервером.

Главный сервер отслеживает статус таблет-серверов и текущее расположение таблетов.

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

Сами таблеты хранятся в виде файлов в распределенной файловой системе GFS (см. раздел 1.1), что обеспечивает надежное хранение данных. Список GFS-файлов с данными таблета хранится в таблице METADATA. Для хранения данных BigTable используется специальный формат SSTable, позволяющий реализовать эффективный поиск значений по их ключам, а также итерации по значениям, связанным с заданным диапазоном ключей. SSTable состоит из несколько блоков и индекса блоков, хранимого в конце файла. Для быстрого поиска блоков таблет-сервер загружает индекс в оперативную память.

При обслуживании запросов на запись, таблет-сервер заносит все изменения таблетов в log-файл, также хранимый в GFS. При этом последние изменения сохраняются в оперативной памяти в отсортированном буфере, называемом memtable.

Операции чтения обслуживаются путем объединения содержимого SSTable-файлов таблета и memcache. При превышении порогового размера, содержимое memtable конвертируется в формат SSTable и сохраняется в GFS. Эта процедура называется малым сжатием (minor compaction). Большое количество файлов SSTable снижает производительность и увеличивает объем хранимых данных. Поэтому периодически проводится процедура сжатия слиянием (merging compaction), когда из нескольких SSTable-файлов и содержимого memtable формируется один SSTable-файл. Случай, когда в сжатии слиянием участвуют все SSTable-файлы таблета, называется большим сжатием (mahjor compaction). После большого сжатия в SSTable не остается удаленных записей. Во время загрузки таблета, таблет-сервер считывает из GFS в оперативную память индексы SSTable и log-файл с последними изменениями. Далее сервер восстанавливает содержимое буфера memcache путем применения всех изменений со времени последнего малого сжатия.

Для обнаружения и отслеживания статуса таблет-серверов в BigTable используется сервис Chubby (см. раздел 3.1). Главный сервер и таблет-сервера поддерживают периодически продлеваемые Chubby-сессии. Каждый таблет-сервер при запуске создает в выделенной директории Chubby новый файл и получает блокировку на него. Главный сервер определяет появление новых таблет-серверов по созданию новых файлов в данной директории. Когда таблет-сервер теряет блокировку на созданный им файл, он прекращает обслуживание клиентов и пытается заново получить блокировку. В случае если файл больше не существует, таблет-сервер прекращает свою работу. Главный сервер периодически запрашивает у таблет-сервера статус его блокировки. Если сервер теряет блокировку или становится недоступным, то главный сервер пытается получить блокировку на файл сервера. Если главный сервер получает блокировку, то он удаляет файл сервера, тем самым, гарантируя, что сервер больше не будет обслуживать клиентов. После чего главный сервер переносит таблеты, обслуживавшиеся сервером, в список неназначенных таблетов. В случае потери Chubby-сессии, главный сервер прекращает свою работу, поскольку надежное функционирование системы без доступа к Chubby невозможно.



Используемая Google система управления кластером производит мониторинг и автоматический перезапуск главного сервера. При запуске главный сервер производит следующие действия. Сервер получает блокировку на файл в Chubby, выделенный для главного сервера BigTable. Таким образом, гарантируется, что в системе только один главный сервер. Далее сервер сканирует директорию с файлами таблет-серверов в Chubby и связывается с каждым из серверов, чтобы определить список обслуживаемых ими таблетов. Затем главный сервер сканирует таблицу METADATA для получения списка таблетов. В случае если обнаружен таблет, не обслуживаемый ни одним таблетсервером, он заносится в список неназначенных таблетов.

Набор хранимых в системе таблетов может изменяться в результате операций создания и удаления таблиц, слияния двух таблетов или разбиения таблета на части.

Главный сервер управляет всеми перечисленными операциями, за исключением последней. Разбиение таблета инициируется таблет-сервером и фиксируется путем записи информации в таблицу METADATA, после чего таблет-сервер уведомляет об изменениях главный сервер.

В реализации BigTable используется ряд дополнительных механизмов, нацеленных на достижение высокой производительности, надежности и доступности системы.

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

BigTable поддерживает сжатие хранимых данных, параметры которого также определяются на уровне группы локализации. Указанный пользователем формат сжатия применяется к каждому блоку SSTable. Поскольку хранимые в группе данные обычно относятся к одному типу, и ключ строки может быть выбран таким образом, чтобы похожие данные находились рядом, то на практике часто достигается высокая степень сжатия данных.

Для повышения производительности операций чтения в таблет-серверах применяется двухуровневая схема кэширования: на верхнем уровне кэшируются значения из ячеек таблицы, а на нижнем – блоки SSTable.

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

Применение Bloom-фильтров позволяет определять, есть ли искомые данные в SSTable, не обращаясь к диску.

В заключение перечислим основные отличительные особенности BigTable в сравнении с реляционными СУБД:

Ориентация на хранение больших объемов слабоструктурированных, разреженных данных;

Высокая производительность, масштабируемость и устойчивость;

Модель хранения, ориентированная на столбцы, аналогичная column-oriented базам данных (C-Store, Vertica, Sybase IQ, SenSage, KDB+, MonetDB/X100);

Нет поддержки реляционной модели, типов данных у столбцов, языка SQL, транзакций и т.д.

1.4. HBase Система HBase [7] входит в состав свободно распространяемой платформы распределенных вычислений Hadoop (см. раздел 2.2). HBase является общедоступным аналогом описанной выше системы BigTable, работающим поверх распределенной файловой системы HDFS. Приведенное ниже описание HBase соответствует текущей на момент написания статьи версии HBase 0.1.2.

Поскольку модель данных, архитектура и реализация HBase очень близка к BigTable, остановимся только на характерных особенностях и отличиях HBase от BigTable.

HBase использует несколько иную терминологию, чем BigTable. Так, аналог таблетов называется регионом (region), а обслуживающие регионы серверы называются регион-сервером (RegionServer). Внутри регионов данные разбиты на вертикальные семейства столбцов. Каждое семейство внутри региона хранится в отдельной структуре данных, называемой Store и аналогичной SSTable в BigTable. Содержимое Store хранится в нескольких файлах в HDFS, называемых StoreFile. Регион-сервер кэширует последние изменения в оперативной памяти (MemCache) и периодически сохраняет их в новые Store-файлы. Аналогично процедурам сжатия в BigTable, регион-сервер периодически объединяет Store-файлы. В отличие от BigTable, HBase не поддерживает определение прав доступа для семейств столбцов.





Главный сервер HBase (Master) управляет назначением регионов серверам и отслеживает их состояние. В отличие от BigTable, HBase не использует подобный Chubby высоконадежный сервис для координации серверов. В случае, если регионсервер теряет связь с главным сервером, то он автоматически завершает работу и перезапускается. При этом главный сервер перераспределяет обслуживавшиеся данным сервером регионы между другими регион-серверами. В отличие от этого, таблет-сервер BigTable может продолжать обслуживать клиентов после потери соединения с главным сервером. При перезапуске главного сервера, регион-сервера подключаются к нему и передают список обслуживаемых ими регионов.

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

Как остальные компоненты, входящие в состав платформы Hadoop, HBase реализована на языке Java. Система имеет несколько интерфейсов для клиентских приложений: Java API, REST-интерфейс и доступ по протоколу Thrift. Пользователи могут взаимодействовать с системой через командную оболочку HBase Shell, которая поддерживает SQL-подобный язык HQL. HBase также предоставляет Web-интерфейс, позволяющий пользователям просматривать информацию о системе и хранимых таблицах.

2. Модели программирования и технологии распределенной обработки данных В главе рассматриваются модели программирования и технологии, ориентированные на обработку больших массивов данных на распределенных кластерных системах. Центральное место в главе занимает описание модели программирования MapReduce, разработанной в компании Google, и ее открытой реализации Apache Hadoop. В качестве другого подхода к описанию и реализации процессов обработки данных рассматривается технология Microsoft Dryad.

2.1. Модель программирования MapReduce MapReduce [2] – модель программирования и платформа для пакетной обработки больших объемов данных, разработанная и используемая внутри компании Google для широкого круга приложений. Модель MapeReduce отличается простотой и удобством использования, скрывая от пользователя детали организации вычислений в ненадежной распределенной среде. Пользователю достаточно описать процедуру обработки данных в виде двух функций – map и reduce, после чего система автоматически распределяет вычисления по кластеру из большого количества машин, обрабатывает отказы машин, балансирует нагрузку и координирует взаимодействия между машинами для эффективного использования сетевых и дисковых ресурсов.

Впервые описание MapReduce было опубликовано в работе [8]. За последние четыре года внутри Google было разработано более 10 тысяч программ для MapReduce. В среднем, каждый день на кластерах Google выполняется около тысячи MapReduceзаданий, обрабатывающих вместе более 20 петабайтов данных [2]. Используемая в Google реализация MapReduce является закрытой технологией, однако существует общедоступная реализация Apache Hadoop (см. раздел 2.2).

В рамках MapReduce вычисления принимают на вход и производят на выходе данные, состоящие из множества пар “ключ-значение”. Обозначим входные данные как list(k1,v1), а выходные – как list(k2,v2). Пользователь описывает вычисления в виде двух функций - map и reduce, близких по смыслу одноименным функциям языка Lisp.

Функция map(k1,v1)list(k2,v2) применяется к каждой паре входных данных и возвращает набор промежуточных пар. Далее реализация MapReduce группирует промежуточные значения v2, связанные с одним ключом k2, и передает эти значения функции reduce. Функция reduce(k2,list(v2))list(v2) преобразует промежуточные значения в окончательный набор значений для данного ключа. Как правило, это одно агрегированное значение, например, сумма.

В качестве примера рассмотрим задачу подсчета числа вхождения каждого слова в большую коллекцию документов. Входные данные можно представить в виде пар <имя документа, содержимое>. Тогда функция map для каждого слова, найденного в содержимом документа, должна возвратить пару <слово, 1>, а функция reduce должна просуммировать все значения для каждого слова, возвратив пары <слово, число вхождений>. Ниже приведен пример реализации данных функций на псевдокоде:

map(String key, String value):

// key: имя документа // value: содержимое документа for each word w in value:

EmitIntermediate(w, “1”);

reduce(String key, Iterator values):

// key: слово // values: список отметок о вхождении слова int result = 0;

for each v in values:

result += ParseInt(v);

Emit(AsString(result));

Обратим внимание на использование итератора в приведенном коде функции reduce. Обусловлено это тем, что обрабатываемые функцией наборы данных могут быть слишком большими для размещения в памяти.

Помимо описания функций map и reduce, в спецификацию MapReduce-задания входят пути к входным и выходным файлам, размещаемым в GFS, а также дополнительные конфигурационные параметры. Пользователь формирует объект со спецификацией задания при помощи интерфейса прикладного программирования на языке C++, предоставляемого библиотекой MapReduce. Запуск задания производится с помощью вызова специальной функции MapReduce, которой передается спецификация задания.

Pages:     | 1 | 2 || 4 | 5 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.