`

СПЕЦИАЛЬНЫЕ
ПАРТНЕРЫ
ПРОЕКТА

Архив номеров

Как изменилось финансирование ИТ-направления в вашей организации?

Best CIO

Определение наиболее профессиональных ИТ-управленцев, лидеров и экспертов в своих отраслях

Человек года

Кто внес наибольший вклад в развитие украинского ИТ-рынка.

Продукт года

Награды «Продукт года» еженедельника «Компьютерное обозрение» за наиболее выдающиеся ИТ-товары

 

Файлы поколения пир(с)инга

0 
 

Файловая система (ФС) – одна из самых не обласканных вниманием подсистем практически любой современной ОС. Максимальные размеры файла, каталога и всей системы в целом, быстродействие при выполнении типовых операций, способность (или неспособность) «откатываться» к последнему целостному состоянию – вот, пожалуй, и все, что принято говорить о ФС.

С массовым распространением ОС Windows 2000/XP и стабильным ростом популярности UNIX-совместимых систем все меньше и меньше становится пользователей, имеющих за плечами опыт наблюдения медитативных картинок дефрагментации диска. А жаль. В том смысле, что долго скачущие разноцветные квадратики дают не только достаточное для обдумывания интересных вещей время, но и пищу для весьма небесполезных размышлений. Вот хотя бы на такую тему: легкость, с которой программа-дефрагментатор «тасует» секторы жесткого диска, говорит о чем-то важном, и более того, фундаментальном для ФС. Это фундаментальное очевидно, но не очень хорошо заметно (как и все очевидное вообще). Речь идет о независимости адреса блока данных (сектора) и собственно данных в адресуемом блоке – именно благодаря этой независимости не слишком быстрая процедура дефрагментации хоть когда-нибудь, да завершается. Но и это не все, о чем можно додуматься, наблюдая за работой дефрагментатора. Есть еще одна крайне важная характеристика традиционных файловых систем – во всех из них безукоризненно строго соблюдается уникальность адреса блока данных в пределах одного устройства. Если, например, при записи нового блока случается так, что его адрес неуникален – то можно говорить о том, что или данные в нем неновы на самом деле, а являются «обновлением» уже существующих, или случилась катастрофа, и содержимое какого-то другого блока будет безвозвратно утеряно.

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

Пиринговые сети как изменение стиля

Вы можете ненавидеть эти два слова из компьютерного новояза – «блогинг» и «пиринг», но деться вам от них некуда. Это уже сегодняшний и, по оценкам большинства специалистов (преимущественно социологов), завтрашний день Интернета. И сколь бы странным ни казалось на первый взгляд – это то самое изменение стиля использования компьютеров, которое способно породить изменения даже в таких ортодоксальных программных подсистемах, как ФС. Еще «удивительнее» тот факт, что в своих основах более организационные, чем технические, блогинг и пиринг порождают изменения именно благодаря глубинным социальным причинам. Возможно, это первый прецедент такого рода. До сих пор в ФС операционных систем что-то существенно изменялось только из технико-экономических соображений, к которым можно прежде всего отнести постоянный рост емкости и быстродействия накопителей и снижение стоимости хранения блока данных. О социальных аспектах упоминалось разве что в рекламе, да и то в традиционном контексте «теперь еще больше и еще дешевле». Но как только множество этого «большого и дешевого» стало объединяться в нечто единое целое, компьютерные идеалисты «вдруг» с удивлением выяснили, что главным фактором, определяющим работоспособность целого, является вовсе не стоимость хранения килобайта данных, а человек (как это всегда бывает в человекомашинных системах).

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

Итак, давайте представим себе распределенную систему хранения и обмена файлами, организованную по принципу равноправного информационного обмена (на сленге «точка-точка»), иначе – пиринговую сеть. Чего ожидают потенциальные пользователи от такой сети? Естественно, того, что попавшие в нее данные будут гарантированно в ней доступны. При предоставлении любых услуг желание потребителя – закон. А потребитель файловой системы (пусть и распределенной) хочет пока неясного (любой пользователь всегда хочет, в принципе, того же самого), но очевидного – надежного хранения данных. Вот оно-то и является тем самым фундаментальным свойством, для пояснения которого мы продолжим наши рассуждения попыткой нахождения ответа на вопрос: чем пользователь готов пожертвовать за, так сказать, исполнение мечты?

Как показывает историческая практика – жертвенность свойственна очень немногим, и ни создать идеального человека, ни просто переделать его пока никому не удавалось. На деле это означает, что потребитель чаще всего теряет интерес к участию в пиринговой сети сразу после получения от нее желаемого. А ведь именно он и является одним из ее узлов, по идее, хранящим часть ее информационного ресурса. Но ведь желания любого потребителя – закон, а это означает, что и после того, как удовлетворенный клиент А покинул сеть, новый страждущий пользователь В все равно должен получить от нее вожделенное. Вот эта способность файловой системы и называется надежным хранением и обеспечивается, по небольшому рассуждению, различными механизмами реализации, для принципиальной работоспособности которых требуется соблюдение одного правила: скорость создания новых копий блоков данных должна существенно превышать скорость их утраты. В распределенных сетях скорость создания копий блоков данных, хранимых на разных узлах, фактически определяется пропускной способностью сети. И следует заметить, что вследствие этого ограничения возникает весьма серьезная проблема, правда, неплохо изученная. Так, на девятом симпозиуме по горячим проблемам операционных систем (есть и такой Workshop on Hot Topics in Operating Systems) исследователи Блейк и Родригес предоставили результаты анализа сети Gnutella. При наблюдаемой интенсивности выхода узлов из строя (по любым причинам) и хранении каждым узлом более 3 GB данных для обеспечения надежности хранения в Gnutella ее узлы должны соединяться с сетью чем-то, что в несколько раз превышает возможности традиционных недорогих высокоскоростных кабельных модемов. Естественно, существуют сугубо социальные приемы снижения частоты выхода узлов из строя (или из сети – что одно и то же в данном контексте), но и они не отменяют потребности в механизмах, позволяющих технически увеличить надежность хранения данных без астрономического увеличения затрат на сетевые соединения.

Хэш-функции как отпечатки пальцев

Независимость адресов блоков данных от их содержания, которую демонстрируют скачущие в программе-дефрагментаторе квадратики секторов диска, – это замечательно. Пока речь идет об одном диске с таким адресным пространством секторов, гарантирующим уникальность каждого сектора. Или о нескольких дисках, соединенных высокоскоростными каналами обмена с несколькими контроллерами (или с одним, но многоканальным). Короче говоря, пока речь идет о локальном компьютере. А как быть в распределенной файловой системе? Очевидное, «лобовое» решение – уточнять уникальный в пределах одного компьютера адрес блока собственно адресом компьютера – далеко не такое удачное, как кажется на первый взгляд (хотя бы потому, что оно смешивает абстракции совершенно разных уровней – ничего хорошего обычно из таких коктейлей не получается). Создатели сетевой файловой системы Venti, ориентированной на архивацию данных, решили отказаться сразу от двух фундаментальных принципов ФС – в Venti содержимое блока данных по сути является его же адресом, а адресное пространство всех возможных блоков не гарантирует уникальности их адресов.

В Venti вместо отдельной сущности – «адрес блока данных» – используется рассчитываемое на основании содержимого блока значение «отпечаток пальцев» (fingerprint). Надо сказать, что название на удивление удачно – особенно для Venti, системы, надстроенной над собственной ФС ОС Plan 9, где выбор названий, мягко говоря, специфичен (о Plan 9 мы некогда рассказывали). Так же, как отпечаток пальца позволяет идентифицировать его владельца, fingerprint Venti позволяет опознать блок данных. И так же, как отпечаток пальца, fingerprint в общем случае недостаточен для идеально точного опознания.

Для расчета значения fingerprint в Venti используется механизм хэширования, ставящий (с помощью вычислительной процедуры) в соответствие наборам данных некоторые, характеризующие их, числа. Разработчики Venti в качестве хэширующего механизма выбрали хорошо известный... криптографический алгоритм SHA1. Он описывает стандартизованную хэш-функцию, разработанную Национальным институтом стандартов США (NIST – National Institute оf Standards and Technology). Особенность SHA1 заключается в том, что для блоков данных длиной менее 160 битов SHA1 гарантированно выдает уникальные 160-битовые ключи (именно благодаря этому свойству SHA1 и применяется в криптографии). Но в файловых системах блоки данных размером в 20 байт практически не применяются, и в Venti хэш-функция SHA1 рассчитывается для более традиционного 8-килобайтового блока. Естественно, в таком случае об уникальности ее значений для всех возможных блоков (количество которых описывается астрономической цифрой 265535) и речи идти не может. Впрочем, для файловой системы, состоящей из 214 8-килобайтовых блоков, вероятность того, что хэш-функция SHA1 даст для различных блоков одно и то же значение (такую ситуацию принято называть коллизией), не превышает 10–20. А ведь речь идет о далеко не маленькой файловой системе – все-таки экзабайтовые (примерно миллиард гигабайтов) массивы данных и по сей день не так уж часто встречаются. На основе вышеупомянутого соображения создатели Venti решили вообще отказаться от всяких механизмов защиты от коллизий – по их мнению, если в экзабайтовом хранилище данных с интенсивностью записи 1 блок в миллионную долю секунды может произойти один сбой примерно за 32 млн лет, на это можно просто не обращать внимания.

Что же дает Venti отказ от двух фундаментальных принципов ФС? Давайте попробуем рассуждать – раз адрес блока данных в этой системе является свойством собственно данных в блоке, то любое изменение их приведет, естественно, к изменению адреса. Соответственно, запись этого обновленного блока в ФС Venti не приведет к уничтожению содержимого его старого варианта – адрес-то автоматически изменился. В традиционных ФС такое поведение фундаментально невозможно – так как адрес блока независим от данных, модифицированный блок перепишет содержимое по прежнему, неизменному, адресу. А к чему приведут в Venti повторные записи неизмененного блока данных? Так как в этой ФС, по сути, уникально (с поправкой, сделанной выше) содержимое блока данных, то, очевидно, ни к чему: если блок с таким адресом уже существует в ФС, то нет никакой нужды его записывать повторно. Традиционной файловой системе абсолютно безразлично – изменилось ли содержание блока данных с таким-то адресом или нет – в любом случае операция записи будет произведена. Если эти описательные модели поместить в условия распределенной сети, окажется, что Venti и более эффективно расходует трафик, исключая повторные записи уже имеющихся в ней блоков данных, и не допускает их дублирования, и создает основу для так называемого «версионного» ведения архивов. Дублирование данных – это болезнь любых файловых систем, не только распределенных (иначе на рынке не существовал бы отдельный востребованный класс утилит для поиска дубликатов файлов). Venti гарантирует невозможность дублирования, потому что в ней нельзя дважды записать блок данных с одним и тем же содержанием. Принцип версионного хранения фактически описан выше – когда вы, например, загрузили файл с документом для редактирования и изменили в нем два каких-то блока данных, при сохранении файла Venti автоматически запишет эти новые блоки, сохранив версии старых – адреса новых блоков ведь изменились. Соответственно, Venti именно благодаря низкоуровневому механизму адресации позволяет хранить всю историю набора данных – все его версии.

Производительность Venti как системы в целом больше является предметом ее критики, чем вопросом, заслуживающим восторженного обсуждения. Связано это, скорее всего не с фундаментальными для системы проектными решениями. Так, потенциально высокое быстродействие механизма генерации адресов в Venti по сути ничем особо не сдерживается. Эту процедуру трудно назвать ресурсоемкой – если даже на универсальных процессорах догигагерцевого диапазона тактовых частот она позволяла находить результат для 8-килобайтового блока за пару сотен микросекунд, то благодаря возможностям современных сверхпроизводительных цифровых сигнальных процессоров и аппаратных вычислителей на программируемой логике ее можно сделать фактически «прозрачной». Таким образом, в «неторопливости» Venti виноваты нюансы конкретной ее реализации (и хотя нюансы нас не интересуют, в их краткий перечень входят переменный, а не фиксированный размер блока данных, не отличающаяся выдающимися характеристиками низкоуровневая ФС ОС Plan 9 и т. д.). К минусам системы отнесем и неизящно решенные вопросы обеспечения безопасности данных, и много чего еще, что свойственно всем пилотным, исследовательским разработкам. Но все же главным недостатком является то, что теория вероятности ни в коем случае не может гарантировать, что теоретически невероятный сбой в Venti непременно произойдет на лично вам совершенно неинтересном временном отрезке 32-миллионного периода – об этом никогда не следует забывать. Последнее соображение не теряет силы даже при учете того, что в NIST созданы модификации алгоритма SHA1, порождающие 256-битовые и даже 512-битовые значения. А раз разработчики оставили вопросы коллизий вне внимания, узнать о том, что в Venti при записи произошел сбой и содержимое какого-то блока данных осталось навсегда утраченным, можно только по последствиям использования этого блока в дальнейшем. А тут уж любые варианты возможны – все зависит от богатства воображения. И, вероятно, нас еще когда-нибудь попугают «проблемами неожиданной ошибки 31 миллион 107-тысячного года» – ведь Venti вместе с ОС Plan 9 стали собственностью Google, и кто знает, чем могут заколоситься бурно растущие пиринговые сети на обильных почвах опыта талантливых команд разработчиков лабораторий знаменитой Bell Labs и стоимости акций Goggle.

Фильтры Блума и «отпечатки пальцев»

В 1970 г. для слова «мегабайт ОЗУ» и «много денег» были синонимами – ведь именно тогда появилась первая серийно выпускаемая интегральная схема динамического ОЗУ емкостью 1 Kb и ценой $21. Для построения ОЗУ в 1 MB таких микросхем надо было ровно 8192 – а это целых 172 тыс. долл., да еще и тех самых, полновесных долларов начала семидесятых. Но компьютеры уже выпускались вовсю, и потребность в программах росла с каждым днем. В том числе и в программах... проверки правописания, для эффективной работы которых надо было много памяти.

Изящное решение проблемы предложил в своей статье в журнале Communications of the ACM сотрудник компании с непритязательным названием Computer Usage Company Бартон Блум (Burton Bloom). Суть идеи Блума проста и объясняется на примере той же программы проверки правописания. Обычно она функционирует так: в проверяемом тексте выделяется слово, для него рассчитывается значение хэш-функции, играющее роль индекса большой таблицы. Затем проводится проверка. Ячейка таблицы с адресом, равным индексу, может содержать само проверяемое слово, другое слово и пустую строку. Первый случай соответствует правильному написанию, третий – неправильному, а вот второй является коллизией – следствием особенности механизма хэширования. При использовании хороших хэш-функций вероятность возникновения коллизий может равняться нескольким процентам.

В 1970 г. Блум решил, что это весьма неплохой для целого ряда задач показатель, и предложил вообще убрать из таблицы что-либо, кроме признака «есть-нет». То есть вместо слова хранить в каждом элементе таблицы всего один бит. Фактически эта таблица и получила название «фильтра Блума», и ее суть и главное предназначение – поддержка эффективной реализации алгоритма проверки принадлежности элемента к множеству с определенной степенью вероятности. Многочисленные модернизации и вариации фильтра Блума позволили добиться исключительно высоких показателей эффективности использования памяти с произвольным доступом. Так, если в решаемой задаче некритична одна коллизия на сто проверок, для формирования таблицы (фильтра) Блума понадобится всего 10∙N (где N – число всех элементов множества) битов ОЗУ независимо от размера проверяемого элемента.

В последнее время к фильтрам Блума возвращается интерес, связанный с социальными трансформациями WWW. В частности, они прекрасно сочетаются с идеями «отпечатков пальцев» Venti и позволяют эффективно решать задачи координации поиска данных в основанных на этой ФС сетях. Теперь фильтры Блума экономят полосу пропускания, которая дешевеет значительно медленнее ОЗУ.

0 
 

Напечатать Отправить другу

Читайте также

 
 
IDC
Реклама

  •  Home  •  Рынок  •  ИТ-директор  •  CloudComputing  •  Hard  •  Soft  •  Сети  •  Безопасность  •  Наука  •  IoT