WWW.DISSERS.RU

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

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

Pages:     || 2 |
Электронный журнал «ИССЛЕДОВАНО В РОССИИ» 355 http://zhurnal.ape.relarn.ru/articles/2001/035.pdf МОДЕЛЬ РАСПРЕДЕЛЕННОГО ХРАНЕНИЯ ДАННЫХ С РЕГУЛИРУЕМОЙ ИЗБЫТОЧНОСТЬТЮ.

Тормасов А.Г., М.А. Хасин (hma@prbank.ru), Ю.И. Пахомов Московский физико-технический институт (Государственный Университет) В статье рассматривается модель распределенного представления данных, основанная на применении (N, k) – пороговой схемы. Файл хранится в виде (N, k)-пороговой схемы, имеющую геометрическую интерпретацию. Файл представляется в виде последовательности k-мерных векторов над полем GF(2n), а каждая из частей схемы является последовательностью проекций этих векторов на некоторый выбранный для данной части k-мерный вектор над GF. Избыточность данных регулируется путем создания новых частей или удаления существующих. Приведены различные реализации модели.

Исследуется эффективность их использования для обеспечения доступности (availability) в системах управления Internet -ресурсами.

1. Введение На фоне бурного развития Internet-технологий, все более актуальной становится задача построения системы, которая бы обеспечивала возможность хранения огромных объемов информации и в то же время гарантировала стабильное время доступа к информационному ресурсу, а также включала в себя механизмы обеспечения безотказного доступа к информации.

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

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

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

• Аппаратные: Shared-Memory Multiprocessing, кластеры, RAID-массивы[1], Shared-Nothing Multiprocessing, Server Net Architecture [8]. В этих технологиях Электронный журнал «ИССЛЕДОВАНО В РОССИИ» 356 http://zhurnal.ape.relarn.ru/articles/2001/035.pdf надежность системы обеспечивается путем добавления избыточных компонент в аппаратную платформу.

• Операционные: MS.Net, NonStop UX System Architecture [8]. Здесь надежность обеспечивается путем усложнения алгоритмов работы системных вызовов операционных систем.

• Прикладные: MS Cluster[11], Error Detection/Correction Codes[5],[6], метод “зеркала” (mirrors), Server Load Balancing [9] и др. В этих технологиях задача решается путем разработки специальных протоколов и механизмов взаимодействия прикладных программ с OS.

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

Рассмотрим, например технологию RAID, которая первоначально была создана для увеличения скорости чтения/записи на магнитные носители путем их распараллеливания.

Основная идея заключается в том, что входной поток информации делится на блоки, которые, в свою очередь, записываются на диски. При считывании происходит обратный процесс - блоки собираются с накопителей и преобразовываются в единый поток. В зависимости от способа распределения блоков различают несколько уровней RAID, с нулевого по пятый. (Наиболее распространены 0,1 и 5 уровни).

RAID0 - алгоритм, при котором каждая порция информации входного потока делится на N фиксированных блоков (N - число дисков в матрице), а затем каждый блок записывается на свой диск. Его назначение - сделать максимально быструю дисковую систему, скорость которой в идеале в N раз превышает быстродействие одного диска (поскольку обычно скорость работы контроллера диска много выше чем самого диска).

RAID1 - или зеркалирование (mirroring) требует четного числа дисков и осуществляет попарное дублирование информации. Этот алгоритм уже обеспечивает отказоустойчивость, т.е. гарантию сохранности данных и теоретическое увеличение скорости в N/2 раз, но стоимость дискового пространства увеличивается вдвое.

RAID5 - этот алгоритм представляет собой что-то среднее между нулевым и первым.

Порция информации из входного потока разделяется на N-1 блоков, а N-й блок вычисляется из N-1 первых и является контрольным. В случае потери одного из N блоков, информация однозначно восстанавливается из N-1 других. Контрольный блок каждый раз от цикла к циклу записываются на новый диск. Теоретическая скорость записи/чтения увеличивается в N/N-1 раз.

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

Аналогичная проблема восстановления данных возникает при решении задачи обеспечения надежности передачи информации по каналам связи. Для этих целей используются алгоритмы исправления ошибок (Error Correction Codes, ECC) и обнаружения ошибок (Error Detection Codes, EDC).[5],[6]. Оба они заключаются в Электронный журнал «ИССЛЕДОВАНО В РОССИИ» 357 http://zhurnal.ape.relarn.ru/articles/2001/035.pdf избыточности передачи информации путем внесения дополнительных битов в передаваемый блок данных. Первый формирует дополнительные биты так, чтобы, анализируя полученный блок, можно было бы указать, где возникли искажения и исправить их. Это, так называемые, коды с исправлением ошибок. Второй алгоритм вносит избыточность лишь для того, чтобы, анализируя полученные данные, можно было сказать, есть в переданном блоке ошибки или нет. Это, так называемые, коды с обнаружением ошибок. Выбор того или иного обычно зависит от требований к процессу передачи.

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

Среди существующих технологий, обеспечивающих отказоустойчивость Internetресурсов, следует отметить технологию SLB (Server Load Balancing), задача которой обеспечить масштабируемость серверов, предоставляющих различные Internet-сервисы (Web,DNS,FTP). Суть его заключается в том, что несколько тесно связанных серверов объединяются в один виртуальный сервер и клиентские запросы распределяются между ними. Такой подход предполагает, что клиенты всегда обращаются к IP-адресу виртуального сервера, а функция SLB выбирает реальный сервер для обслуживания запроса клиента.

Такая технология, однако, имеет ряд недостатков. Во-первых, она предполагает зеркалирование данных каждого сервера, включенного в группу. Во-вторых, технология обеспечивает масштабируемость только по скорости обработки запросов и не обеспечивает масштабируемость по скорости передачи данных пользователю. Если каналы связи из-за загруженности сети не позволяют передавать объем данных, ёёнеобходимый для удовлетворения всех клиентских запросов, то даже если виртуальный сервер найдет все необходимые данные он не сможет в необходимое время передать их клиенту.

Кроме вышеописанной технологии SLB, в существующих системах часто применяется технология “зеркала”. Создаются несколько идентичных серверов, дублирующих друг друга. Для доступа к информации, пользователю достаточно подсоединится к “ближайшему” c зрения доступности серверу. Недостатками данной технологии является необходимость многократного дублирования хранилищ данных, что требует существенных ресурсов для построения больших систем, и потребность пользователю самостоятельно определять “ближайший” к себе сервер.

В данной статье рассматривается метод распределенного хранения данных, который может быть использован для обеспечения доступности информационной системы в условиях неравномерной загруженности сети и неравномерного распределения в ней информации. Метод основан, на представлении файла в виде (N, k) - пороговой схемы, которая позволяет представить файл в виде n частей (n N), таким образом, что пользователю достаточно иметь доступ к любым k них, чтобы собрать весь файл целиком.

(N, k) – пороговые схемы были разработаны независимо Эди Шамиром [12] и Бобом Блэкли [13]. Задачей этих схем являлось обеспечение безопасного хранения секретной информации. Никакие k-1 из существующих частей не представляют абсолютно никакой информации (в смысле теории информации Шеннона) относительно исходных данных.

Рассматриваемая ниже (N, k) – пороговая схема отличается от алгебраической схемы Шамира и геометрической схемы Блэкли. Ее задача обеспечить минимальное увеличение размера частей, необходимых для сборки файла по сравнению с размерам исходного файла. Кроме этого число N должно быть достаточно велико, чтобы обеспечивать доступность ресурса при интенсивном его использовании.

Электронный журнал «ИССЛЕДОВАНО В РОССИИ» 358 http://zhurnal.ape.relarn.ru/articles/2001/035.pdf 2. Модель распределенного представления данных.

2.1 Для чего хранить файл в виде (N, k)-пороговой схемы.

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

Размер каждой части ~ 1/k от размера хранящегося файла. Количество частей файла - n, содержащихся в системе может меняться в зависимости от ее конфигурации, от количества компьютеров в ней, интенсивности работы с данным файлом и т.д. Причем, при изменении (увеличении) числа n уже существующие части никак не изменяются, то есть новые части строятся таким образом, чтобы по-прежнему выполнялось условие избыточности.

Число k является фиксированным для каждого конкретного файла и зависит от его размера. При использовании протокола TCP/IP [10], который де факто является основным в существующих сетях, скороcть передачи данных максимальна, когда их размер соответствует размеру пакета протокола (message transfer unit), что составляет ~1Kb.

Таким образом, размер каждой части должен быть ~ 1Kb. То есть для файла размера S число k определяется по формуле k=S/Sp, где Sp – размер пакета протокола TCP/IP.

Средний размер Internet ресурсов ~5-7 Kb. В следующих разделах будет показано, что сложность алгоритма сборки файла пропорциональна k и размеру файла, поэтому при исследовании производительности мы будем считать k=5.

Для того, чтобы получить файл, пользователю необходимо получить любые k частей из существующих в данный момент в системе, из которых он сможет восстановить исходный файл. Размер каждой части будет 1/k от размера исходного файла, поэтому общий объем полученной информации будет равен объему файла, тем самым общая нагрузка на сеть не будет увеличена.

РИС. Электронный журнал «ИССЛЕДОВАНО В РОССИИ» 359 http://zhurnal.ape.relarn.ru/articles/2001/035.pdf На рисунке показано удовлетворение пользовательского запроса на чтение файла при k=3. Для удовлетворения запроса пользователь будет получать k “ближайших” с точки зрения загрузки в данный момент сети и пропускной способности каналов связи, что обеспечивает минимальное время удовлетворения запросов. Запросы на поиск кусков в системе служат для мониторинга интенсивности использования данного файла. Для этого каждый из серверов хранит историю запросов прошедших через него.

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

2.2 Описание (N, k) – пороговой схемы.

Рассмотрим конечное поле P = GF(N) (поле Галуа, состоящее из N элементов).

Конечные поля существуют для количества элементов равного степени простого числа.

Pages:     || 2 |



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

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