НАДЕЖНОЕ ЭФФЕКТИВНОЕ ХРАНЕНИЕ В ОДНОРАНГОВЫХ УЗЛАХ
RELIABLE, EFFICIENT PEER-TO-PEER STORAGE

В приложении для одноранговых узлов (P2P) одноранговые узлы вносят с собой сетевую пропускную способность и/или ресурсы хранения на жестких дисках, когда они присоединяются к службе P2P. С ростом требований к P2P-системе емкость системы также растет. Это находится в остром контрасте с системой клиент-сервер, где емкость сервера фиксирована и оплачивается поставщиком системы клиент-сервер. В результате система P2P является более экономичной для работы, чем система клиент-сервер, и является лучшей, так как является масштабируемой.
В P2P систему одноранговый узел привносит не только пропускную способность, но также и пространство памяти (хранения), чтобы обслуживать другие одноранговые узлы. Общее пространство хранения, внесенное одноранговыми узлами, формирует облако распределенного хранения. Данные могут быть сохранены в него и могут быть извлечены из этого облака. P2P память может использоваться для ряда приложений. Одним является распределенное резервное копирование. Одноранговый узел может выполнять резервное копирование своих собственных данных в P2P-облако. Когда одноранговый узел дает сбой, данные могут быть восстановлены из этого облака. Другим P2P приложением является доступ к распределенным данным. Так как клиент может извлекать данные одновременно из множества одноранговых узлов, хранящих данные, извлечение в P2P может иметь более высокую производительность по сравнению с извлечением данных из единственного источника. Другим приложением является просмотр кинофильма по требованию. Сервер мультимедийной информации может "питать" P2P облако файлами кинофильмов с использованием приоритетов. Когда клиент просматривает кинофильм, он может передавать в виде потока кинофильм как из P2P облака, так и из сервера, таким образом уменьшая нагрузку сервера, уменьшая трафик на сетевой магистрали и улучшая качество передаваемого в виде потока кинофильма.
-6
-2
Хотя одноранговые узлы в P2P-сети могут действовать подобно серверам, они отличаются от коммерческих серверов Web/баз данных по одному важному аспекту: надежности. Поскольку одноранговым узлом обычно является обычный компьютер, который поддерживает P2P приложение своим зарезервированным местом на жестком диске и незанятой полосой частот, он является гораздо менее надежным, чем типичный сервер. Пользователь может выбрать выключение компьютера однорангового узла или P2P приложение время от времени. Обязательная необходимость, например, выгрузка/загрузка большого файла, может отбирать у однорангового узла необходимую полосу частот для P2P-действия. Компьютер однорангового узла может быть переведен в автономный режим (off-line) из-за необходимости модернизировать или обновить программное обеспечение/аппаратное обеспечение или из-за вирусной атаки. Компьютерное аппаратное обеспечение и сетевая линия связи однорангового узла также неотъемлемо являются намного более ненадежными, чем типичный серверный компьютер и его коммерческие сетевые линии связи, которые предназначены для обеспечения надежности. В то время как коммерческие кластеры сервер/сервер предназначены для надежности "шесть девяток" (с интенсивностью отказов 10, при такой интенсивности каждый год разрешается приблизительно 30 секунд простоя), хороший одноранговый узел потребителя может иметь надежность только "две девятки" (интенсивность отказов 10 или приблизительно 15 минут времени простоя каждый день), и не является редкостью для одноранговых узлов иметь только 50% (половину времени) или даже надежность 10% (снижение на 90% времени).
Большинство приложений P2P, например резервное копирование и извлечение данных P2P, хочет поддерживать такой же уровень надежности для P2P хранения, что и для сервера (надежность "шесть девяток"). Вопрос состоит в том, как сформировать надежное эффективное P2P-хранилище, используя минимальные полосы частот и ресурсы хранения одноранговых узлов.
Сущность изобретения
Представлены система и способ хранения с адаптивным кодированием для эффективного и надежного сохранения данных в сети одноранговых узлов (P2P). Упомянутые система и способ хранения с адаптивным кодированием регулируют количество фрагментов для отказоустойчивого кодирования с исправлением ошибок (ERC), причем число фрагментов ERC основано на размере файла, сохраненного и распределенного.
Ряд вариантов осуществления системы хранения с адаптивным кодированием использует процедуры для повышения эффективности и надежности P2P сети. Например, в одном варианте осуществления малые динамические данные направляют более надежным одноранговым узлам или даже серверу, если доступна поддержка компонентов сервера. Также в другом варианте осуществления для сбалансированной P2P сети одноранговым узлам, которые являются ненадежными и распределяющими меньшие файлы, разрешено распределение меньшего количества данных.
Следует заметить, что хотя вышеописанные ограничения в существующем одноранговом запоминающем устройстве и системах распределения, описанные в разделе уровня техники, могут быть разрешены конкретной реализацией системы хранения с адаптивным кодированием согласно настоящему изобретению, эти система и процесс никоим образом не ограничены реализациями, которые только решают какой-либо или все отмеченные недостатки. Вместо этого, существующая система и процесс имеют намного более широкое применение, как очевидно из нижеследующего описания.
Также следует заметить, что этот раздел сущности изобретения обеспечивается, чтобы представить выбор концепций в упрощенной форме, которые описаны ниже в подробном описании. Этот раздел сущности изобретения не предназначен для идентификации ключевых признаков или существенных признаков заявленного изобретения, и при этом не предназначен для использования в качестве помощи при определении объема заявленного предмета изобретения.
Краткое описание чертежей
Конкретные признаки, аспекты и преимущества системы хранения с адаптивным кодированием станут лучше поняты со ссылками на нижеследующее описание, прилагаемую формулу изобретения и сопроводительные чертежи, на которых:
Фиг. 1 является общей диаграммой системы, изображающей вычислительное устройство общего назначения, образующего примерную систему, реализующую систему и способ хранения с адаптивным кодированием, как описано в настоящем описании.
Фиг. 2 иллюстрирует примерную одноранговую (P2P) сеть, которая может использоваться с системой и способом хранения с адаптивным кодированием, как описано здесь.
-6
Фиг. 3 является графиком, иллюстрирующим количество хранящих информацию одноранговых узлов для достижения требуемой надежности 10.
Фиг. 4 является графиком, иллюстрирующим надежность однорангового узла и требуемый коэффициент дублирования.
-6
Фиг. 5 является графиком, иллюстрирующим количество хранящих информацию одноранговых узлов, необходимых для достижения требуемой надежности 10, с использованием отказоустойчивого кодирования с исправлением ошибок.
Фиг. 6 является графиком, иллюстрирующим количество ERC фрагментов и связанный подходящий размер файла для хранения информации в P2P сети.
Фиг. 7 обеспечивает график, изображающий использование полосы частот между одноранговыми узлами в P2P конфигурации с адаптивным ERC и фиксированным ERC (при одноранговом узле с надежностью=50%).
Фиг. 8 обеспечивает график, изображающий использование полосы частот между одноранговыми узлами в P2P конфигурации с адаптивным ERC и фиксированным ERC (при одноранговом узле с надежностью=99%).
Фиг.9 изображает один вариант осуществления способа сохранения с адаптивным кодированием.
Фиг. 10 изображает примерную схему последовательности операций, показывающую, как методика хранения с адаптивным кодированием используется в P2P сети.
Фиг. 11 изображает вариант осуществления системы и процесса хранения с адаптивным кодированием, который осуществляет процедуру для оптимизации эффективности хранения P2P сети.
Фиг. 12 изображает другой вариант осуществления системы и способа хранения с адаптивным кодированием, который реализует процедуры для оптимизации эффективности хранения P2P системы.
Фиг. 13 изображает вариант осуществления системы и способа хранения с адаптивным кодированием, который использует резервную копию P2P с серверной поддержкой.
Подробное описание
В нижеследующем описании предпочтительных вариантов осуществления настоящей системы хранения с адаптивным кодированием ссылка делается на сопроводительные чертежи, которые формируют его часть, и на которых показываются посредством иллюстрации конкретные варианты осуществления, в которых система хранения с адаптивным кодированием может быть реализована. Понимается, что другие варианты осуществления могут использоваться, и структурные изменения могут быть сделаны без отхода от сущности настоящей системы хранения с адаптивным кодированием.
1.0 Примерная среда
Фиг. 1 иллюстрирует пример подходящей среды 100 вычислительной системы, в которой может быть осуществлено изобретение. Среда 100 вычислительной системы является только одним примером подходящей вычислительной среды и не предназначена, чтобы предложить какое-либо ограничение относительно объема использования или функциональных возможностей изобретения. Вычислительная среда 100 не должна интерпретироваться как имеющая какую-либо зависимость или требования, относящиеся к какому-либо или комбинации компонентов, проиллюстрированных в примерной среде 100.
Изобретение работает с множеством других вычислительных системных сред или конфигураций общего назначения или специализированных. Примеры известных вычислительных систем, сред и/или конфигураций, которые могут быть подходящими для использования с изобретением, включают в себя, но не ограничиваются ими, персональные компьютеры, серверные компьютеры, карманный, портативный или мобильный компьютер или устройства связи, такие как сотовые телефоны и персональные цифровые ассистенты (ПЦА, PDA), мультипроцессорные системы, основанные на микропроцессорах системы, телевизионные приставки, программируемую бытовую электронику, сетевые персональные компьютеры, мини-компьютеры, универсальные компьютеры, распределенные вычислительные среды, которые включают в себя любую из вышеупомянутых систем или устройств, и т.п.
Изобретение может быть описано в общем контексте выполняемых компьютером команд, таких как программные модули, выполняемые компьютером в комбинации с аппаратными модулями, включающими в себя компоненты набора микрофонов 198. В общем случае программные модули включают в себя подпрограммы, программы, объекты, компоненты, структуры данных и т.д., которые выполняют конкретные задачи или реализуют конкретные абстрактные типы данных. Изобретение также может быть осуществлено в распределенных вычислительных средах, где задачи выполняются удаленными устройствами обработки, которые связаны через систему коммуникаций. В распределенной вычислительной среде программные модули могут быть расположены как в локальных, так и удаленных компьютерных носителях памяти, включая запоминающие устройства памяти. Со ссылками на фиг. 1 примерная система для осуществления изобретения включает в себя вычислительное устройство общего назначения в форме компьютера 110.
Компоненты компьютера 110 могут включать в себя, но не ограничиваться ими, процессор 120, системную память 130 и системную шину 121, которая подсоединяет различные элементы системы, включая системную память, к процессору 120. Системная шина 121 может быть любой из нескольких типов шинных структур, включающих в себя шину памяти или контроллер памяти, периферийную шину и локальную шину, используя любую из ряда архитектур шины. В качестве примера, а не ограничения, такие архитектуры включают в себя шину архитектуры промышленного стандарта (ISA), шину микро-канальной архитектуры, (MCA), расширенную шину ISA (EISA), локальную шину Ассоциации Стандартов Видео Электроники (VESA) и шину связи периферийных компонентов (PCI), также известную как шина Mezzanine.
Компьютер 110 типично включает в себя ряд считываемых компьютером носителей. Считываемыми компьютером носителями могут быть любые доступные носители, к которым может обращаться компьютер 110, и включают в себя как энергозависимые, так и энергонезависимые носители, сменные и несменные носители. В качестве примера, а не ограничения, считываемые компьютером носители могут охватывать компьютерные носители хранения и коммуникационные носители. Компьютерные носители хранения включают в себя энергозависимые и энергонезависимые сменные и несменные носители, осуществленные любым способом или технологией для хранения информации, например, считываемых компьютером команд, структур данных, программных модулей или других данных.
Компьютерные носители хранения включают в себя, но не ограничиваются ими, ОЗУ, ПЗУ, ППЗУ, ЭППЗУ, ЭСППЗУ, флэш-память или память другой технологии; CD ROM, цифровые универсальные диски (DVD), или другую оптическую память на дисках; магнитные кассеты, магнитную ленту, запоминающее устройство на магнитных дисках или другие магнитные запоминающие устройства; или любую другую среду, которая может использоваться, чтобы хранить требуемую информацию и к которой можно обращаться компьютером 110. Коммуникационные носители типично реализуют считываемые компьютером команды, структуры данных, программные модули или другие данные в модулируемом сигнале данных, таком как несущая или другой транспортный механизм, и включают в себя любую среду доставки информации. Термин "модулированный сигнал данных" означает сигнал, который имеет одну или более из его характеристик, установленную или измененную таким образом, чтобы кодировать информацию в сигнале. В качестве примера, а не ограничения, коммуникационные носители включают в себя проводную среду, например проводную сеть или непосредственное проводное соединение, и беспроводные носители, такие как акустические, РЧ, инфракрасные, и другие беспроводные среды (носители). Комбинации любых из вышеупомянутых также должны быть включены в понятие считываемых компьютером носителей.
Системная память 130 включает в себя компьютерные носители памяти в форме энергозависимой и/или энергонезависимой памяти, такие как запоминающее устройство только для чтения (ПЗУ) 131 и оперативное запоминающее устройство (ОЗУ) 132. Базовая система ввода-вывода 133 (BIOS), содержащая основные подпрограммы, которые помогают передавать информацию между элементами в компьютере 110, например, в течение запуска, обычно сохраняется в ПЗУ 131. ОЗУ 132 обычно содержит данные и/или программные модули, которые являются немедленно доступными для и/или в настоящее время обрабатываемыми процессором 120. В качестве примера, а не ограничения, Фиг. 1 иллюстрирует операционную систему 134, прикладные программы 135, другие программные модули 136 и программные данные 137.
Компьютер 110 может также включать в себя другие сменные/несменные, энергозависимые/энергонезависимые компьютерные носители памяти. В качестве примера только, Фиг. 1 иллюстрирует накопитель 141 на жестких дисках, который считывает с или записывает на несменные энергонезависимые магнитные носители, накопитель 151 на магнитном диске, который считывает с или записывает на сменный энергонезависимый магнитный диск 152, и накопитель 155 на оптических дисках, который считывает с или записывает на сменный энергонезависимый оптический диск 156 типа CD ROM или другие оптические носители. Другие сменные/несменные, энергозависимые/энергонезависимые компьютерные носители памяти, которые могут использоваться в примерной среде, включают в себя, но не ограничиваются ими, кассеты магнитной ленты, платы флэш-памяти, цифровые универсальные диски, цифровую видеоленту, твердотельное ОЗУ, твердотельное ПЗУ и т.п. Накопитель 141 на жестких дисках обычно соединяется с системной шиной 121 через интерфейс несменных ЗУ, например, интерфейс 140, а накопитель 151 на магнитном диске и накопитель 155 на оптических дисках обычно соединяются с системной шиной 121 интерфейсом сменных ЗУ, типа интерфейса 150.
Диски и их связанные компьютерные носители хранения, описанные выше и проиллюстрированные на Фиг. 1, обеспечивают хранение считываемых компьютером команд, структур данных, программных модулей и других данных для компьютера 110. На фиг. 1, например, накопитель 141 на жестких дисках проиллюстрирован как хранящий операционную систему 144, прикладные программы 145, другие программные модули 146 и программные данные 147. Следует заметить, что эти компоненты могут или быть теми же самыми, или отличными от операционной системы 134, прикладных программ 135, других программных модулей 136 и программных данных 137. Операционная система 144, прикладные программы 145, другие программные модули 146 и программные данные 147 имеют различные ссылочные позиции, чтобы проиллюстрировать, что как минимум они являются различными копиями. Пользователь может вводить команды и информацию в компьютер 110 через устройства ввода, например, клавиатуру 162, и устройства 161 управления позицией, обычно называемые как мышь, шаровой указатель или сенсорный экран.
Другие устройства ввода (не показаны) могут включать в себя джойстик, игровую клавиатуру, спутниковую антенну, сканер, радиоприемник и телевизионный приемник или приемник вещаемого видео, или подобные. Эти и другие устройства ввода часто соединяются с процессором 120 через проводной или беспроводный пользовательский интерфейс 160, который подсоединен к системной шине 121, но могут быть соединены посредством другого обычного интерфейса и шинными структурами, такими как, например, параллельный порт, игровой порт, универсальная последовательная шина (USB), интерфейс IEEE 1394, беспроводный интерфейс Bluetooth (TM), беспроводный интерфейс IEEE 802.11 и т.д. Кроме того, компьютер 110 может также включать в себя устройство ввода речи или звука, например, микрофон или набор микрофонов 198, а также громкоговоритель 197 или другое устройство вывода звука, подсоединенное через аудио интерфейс 199, снова включая в себя обычные проводные или беспроводные интерфейсы, такие как, например, параллельный порт, последовательный порт, USB, IEEE 1394, Bluetooth (TM) и т.д.
Монитор 191 или другой тип устройства отображения также связан с системной шиной 121 через интерфейс, такой как видеоинтерфейс 190. В дополнение к монитору компьютеры могут также включать в себя другие периферийные устройства вывода, например, принтер 196, который может быть связан через интерфейс 195 периферийных устройств вывода.
Компьютер 110 может работать в сетевой среде, используя логические соединения с одним или более удаленными компьютерами, таким как удаленный компьютер 180. Удаленным компьютером 180 может быть персональный компьютер, сервер, маршрутизатор, сеть ПК, устройство однорангового узла, или другой обычный сетевой узел, и обычно включает в себя многие или все элементы, описанные выше относительно компьютера 110, хотя только запоминающее устройство памяти 181 было проиллюстрировано на фиг. 1. Логические соединения, изображенные на фиг. 1, включают в себя локальную сеть (LAN) 171 и глобальную сеть (WAN) 173, но могут также включать в себя другие сети. Такие сетевые среды являются обычными в офисах, корпоративных сетях, интранет и Интернет.
При использовании в сетевой среде LAN компьютер 110 связан с LAN 171 через сетевой интерфейс или адаптер 170. При использовании в глобальной сети WAN компьютер 110 обычно включает в себя модем 172 или другие средства для установления связи по WAN 173, типа Интернет. Модем 172, который может быть внутренним или внешним, может быть связан с системной шиной 121 через пользовательский интерфейс 160 ввода или другой соответствующий механизм. В сетевой среде программные модули, изображенные относительно компьютера 110 или его частей, могут быть сохранены в удаленном запоминающем устройстве памяти. В качестве примера, а не ограничения, Фиг. 1 иллюстрирует удаленные прикладные программы 185 как постоянно находящиеся на ЗУ 181. Следует заметить, что показанные сетевые соединения являются примерными и могут использоваться другие средства установления линии связи между компьютерами.
В общем случае система хранения с адаптивным кодированием работает в P2P сети, такой как сеть, проиллюстрированная на Фиг. 2. Для конкретного сеанса передачи данных в виде потока, "сервер" 200 определен как узел в P2P сети, который выдает данные или передаваемую в виде потока информацию; "клиент" (или приемник) 210 определен как узел, который в настоящее время запрашивает данные; и "обслуживающий одноранговый узел" 220 определен как узел, который обслуживает клиента полной или частичной копией данных.
Вообще, сервер 200, клиент 210 и обслуживающие одноранговые узлы 220 - все являются узлами конечного пользователя, связанными с сетью, такой как Интернет. Поскольку сервер 200 всегда способен к обслуживанию данных, серверный узел также действует как обслуживающий одноранговый узел 220. Серверный узел 200 может также выполнять административные функции, которые не могут быть выполнены обслуживающими одноранговыми узлами 220, например, поддержание списка доступных обслуживающих одноранговых узлов, выполнение функций управления цифровыми правами (DRM) и так далее. Кроме того, как и с обычными P2P схемами, система хранения с адаптивным кодированием, описанная здесь, извлекает выгоду из повышенной эффективности по мере того, как разворачивается все больше одноранговых узлов 220. В частности, когда количество одноранговых узлов 220 увеличивается, нагрузка на сервер 200 данных уменьшается, таким образом становясь менее дорогой в работе, в то время как каждый клиентский узел 210 будет способен принять намного лучшее качество данных в течение конкретного сеанса связи передачи данных.
Кроме того, должно быть ясно, что роль конкретных узлов может изменяться. Например, конкретный узел может действовать как клиент 210 в одной конкретной передаче данных, в то же время действуя как обслуживающий одноранговый узел 220 в другом сеансе связи. Кроме того, конкретные узлы могут одновременно действовать и как клиентские узлы 210 и серверы 200 или обслуживающие одноранговые узлы 220, чтобы одновременно посылать один или более файлов данных или частей этих файлов, в то же время принимая другие данные от одного или более других обслуживающих одноранговых узлов.
В течение передачи данных клиент 200 сначала определяет местонахождение ряда одноранговых узлов 220, которые хранят некоторые или все требуемые данные, и затем принимает данные от множества одноранговых узлов (которые могут включать в себя сервер 200). Следовательно, каждый обслуживающий одноранговый узел 220 действует так, чтобы помочь серверу 200, сокращая общую нагрузку, посредством обслуживания части запроса по загрузке для клиента 210. В результате клиент 210, особенно в случае, когда имеется множество клиентов, может часто принимать намного лучшее качество данных, так как имеется значительно большая пропускная способность обслуживания, доступная, когда имеются много обслуживающих одноранговых узлов 220, чтобы помочь серверу 200.
После описания выше примерной рабочей среды, оставшиеся части этого раздела описания будут посвящены описанию программных модулей, воплощающих систему и процесс хранения с адаптивным кодированием.
2.0 Надежное эффективное одноранговое хранение
Система хранения с адаптивным кодированием обеспечивает адаптивную отказоустойчивую схему кодирования с исправлением ошибок (ERC), которая адаптивно решает, использовать ли ERC кодирование, и использует оптимальное количество фрагментов, которые нужно использовать для ERC кодирования для заданного размера файла для оптимальной надежности и эффективности. Количество фрагментов, используемых для ERC кодирования файла, будет называться "количество ERC фрагментов" для целей настоящего описания. Нижеследующие параграфы предоставляют описание эффективности и надежности однорангового (P2P) (запоминающего устройства) хранения и использования ERC в P2P сетях, а также описание количества используемых ERC фрагментов. Ниже описаны различные варианты осуществления системы и процесса (способа) хранения с адаптивным кодированием.
2.1 Надежность при P2P хранении: избыточность данных
adhoc
p
0
Решение  (для данного конкретного случая) привнести надежность в систему с ненадежными частями состоит в том, чтобы использовать избыточность. Если каждый отдельный одноранговый узел в сети имеет надежность p, чтобы достичь требуемой надежности , можно просто продублировать информацию в n одноранговых узлов:
p
0
n=log(1-)/log(1-p),(1)
где n - количество одноранговых узлов, хранящих информацию. Во время извлечения клиент может входить в контакт с хранящими информацию одноранговыми узлами "один за другим". Пока один из хранящих информацию одноранговых узлов находится в оперативном режиме (on-line), информация может быть надежно извлечена.
Хотя и достигает надежности, простая стратегия дублирования не эффективна. Фиг. 3 показывает в виде графика количество хранящих информацию одноранговых узлов, необходимых, чтобы достичь надежности "шесть девяток". При надежности однорангового узла 50 % требуется копировать и сохранять информацию в 20 одноранговых узлах. Это ведет к более чем 20-кратному размеру полосы частот и объема памяти для распределения и хранения информации. Очевидно, эффективность была пожертвована в обмен на надежность информации.
2.2 Отказоустойчивое кодирование с исправлением ошибок в P2P
i
16
16
Чтобы повысить эффективность при поддержании одной и той же надежности, ERC может быть полезным инструментом. ERC разбивает первоначальный файл на k первоначальных фрагментов {x}, i=0;…, k-1, каждый из которых является вектором по полю Галуа GF(q), где q - порядок поля. Скажем, при кодировании файла, который имеет длину 64 Кбайт, при использовании q=2 и k=16 каждый фрагмент будет размером 4 Кбайт и будет состоять из 2K слов, причем каждое слово является элементом GF(2). ERC затем формирует кодированные фрагменты из первоначальных фрагментов. ERC кодированный фрагмент формируется посредством операции:
,
j
j
где c является кодированным фрагментом, G является k-мерным порождающим вектором, и уравнение (2) является матричным перемножением, все на GF(q). Во время декодирования одноранговый узел собирает m кодированных фрагментов, где m - количество, равное или немного большее k, и пытается декодировать k первоначальных фрагментов. Это эквивалентно решению уравнения:
=(3)
Если эта матрица, сформированная порождающими векторами, имеет полный ранг k, первоначальные сообщения могут быть восстановлены.
Имеются много доступных ERC. Особенно интересным является код Рида-Соломона (RS). RS код использует структурные порождающие векторы и является разделимым на максимальное расстояние (MDS). В результате любые k различных кодированных фрагментов будут способны декодировать первоначальные фрагменты. Другое преимущество RS кода состоит в том, что кодированный фрагмент может быть легко идентифицирован и управляться индексом j порождающего вектора, таким образом облегчая обнаружение дублированных RS кодов. В нижеследующем описании ERC, принимается, что используется код RS. Однако система хранения с адаптивным кодированием может быть осуществлена с любым количеством обычных ERC.
2.3 ERC: Количество фрагментов
1
Используя ERC в P2P (одноранговой системе) хранении, файл данных распределяется к большему количеству одноранговых узлов, но каждый одноранговый узел должен только хранить один кодированный фрагмент, который имеет размер 1/k первоначального файла, приводя к общему сокращению полосы частот и объему памяти, требуемым для достижения того же уровня надежности, и таким образом повышая эффективность. Пусть n есть количество одноранговых узлов, которым кодированные фрагменты должны быть распределены, чтобы достичь некоторого требуемого уровня надежности. Так как RS код является кодом MDS, k одноранговых узлов, хранящие k различных кодированных фрагментов, будут достаточны для восстановления первоначального файла. Вероятность, что имеется точно m доступных одноранговых узлов, может быть рассчитана через биноминальное распределение:
p(m,n
)=
p
(1-p)
1
m
(4)
1
0
p
p
k
Можно таким образом вычислить n из ,  и  как:
1
n=(5)
Коэффициент дублирования r определяется как:
1
r=n/k(6)
Коэффициент дублирования r является хорошим индикатором эффективности, поскольку r копий файлов должны быть распределены и сохранены в P2P (одноранговом) "облаке".
На фиг. 4 показан требуемый коэффициент дублирования, чтобы достичь надежности "шесть девяток" для различного количества k ERC фрагментов. Заметим, что использование ERC сильно уменьшает требуемый коэффициент дублирования. Сравнивая не-ERC (k=1) и ERC количество фрагментов k=256, требуемый коэффициент дублирования уменьшается от r=132 до r=13,1 для надежности однорангового узла 10%, от r=20 до r=2,5 для надежности однорангового узла 50% и от r=3 до r=1,05 для надежности однорангового узла 99%. ERC может улучшать эффективность без того, чтобы жертвовать надежностью.
Также заметим, что большее количество ERC фрагментов дополнительно уменьшает коэффициент дублирования. При надежности однорангового узла 50% изменение от k=8 до 16, 32, 64, 128 и 256 ведет к сокращению коэффициента дублирования от r=5,75 до 4,375, 3,53, 3,02, 2,68 и 2,48. Соответствующее повышение эффективности - 24%, 19%, 15%, 11% и 8%, соответственно. Это, кажется, предлагает, что нужно использовать большее количество ERC фрагментов для большей эффективности.
1
Однако большее количество ERC фрагментов подразумевает, что необходимо больше одноранговых узлов, чтобы хранить и извлекать кодированные фрагменты. На фиг. 5 показано количество одноранговых узлов, которые необходимы для хранения кодированных фрагментов, чтобы достичь надежности "шесть девяток", в виде графика. Снова при надежности однорангового узла 50%, изменение от k=8 до 16, 32, 64, 128 и 256 увеличивает количество хранящих информацию одноранговых узлов от n=46 до 70, 113, 193, 343 и 630. Каждое удвоение k приводит к 52%, 61%, 71%, 78%, 84% увеличению одноранговых узлов, необходимых для хранения информации. Удвоение k также требует по меньшей мере двойного количества одноранговых узлов, с которыми нужно войти в контакт в течение извлечения информации.
служебные_расходы
В большинстве практических P2P сетей, установление соединения между одноранговыми узлами требует нетривиального количества накладных (служебных) расходов. Одна часть служебных расходов может быть приписана извлечению надлежащей идентификационной информации однорангового узла и обнаружению надлежащего тракта маршрутизации (например, посредством распределенной хеш-таблицы (DHT)). Другая часть служебных расходов вызвана необходимостью вызвать некоторые алгоритмы преобразования сетевого адреса (NAT), например, STUN (простой обход UDP посредством NAT), если один или оба одноранговых узлов "находятся" позади NAT. В предположении, что среднее число служебных расходов для установления соединения между двумя одноранговыми узлами равно (установлено равным 16 Кб в этом примере), можно вычислить полную сетевую пропускную способность, необходимую для сохранения файла размера s, равную:
1
служебные_расходы
Пропускная_способность_хранения=s*r+n*(7)
С учетом уравнения (7) очевидно, что большее количество ERC фрагментов не всегда ведет к лучшей эффективности. Вместо этого для маленького файла малое количество ERC фрагментов или даже не-ERC должно использоваться. Вычисляют полную пропускную способность, требуемую в уравнении (7) для различных размеров файла и ERC количества фрагментов, и составляют график кривых, показанных на фиг. 6. Граница между различным ERC количеством фрагментов является диапазоном оптимального размера файла, подходящим для конкретного ERC количества фрагментов. Например, нижняя кривая на Фиг. 6 иллюстрирует границу размера файла, ниже которой должно использоваться не-ERC и выше которой должно использоваться ERC с количеством фрагментов k=2. Интересное наблюдение состоит в том, что граница размера файла является относительно нечувствительной для доступности однорангового узла, что очень упрощает выбор оптимального параметра ERC-фрагмента. Вообще, для файла меньшего, чем приблизительно 10 Кб, ERC не должно использоваться. Для ERC с количеством фрагментов k=2, 4, 8, 16, 32, 128 и 256 наиболее подходящий диапазон размера файла составляет приблизительно 10-33 Кб, 33-100 Кб, 100-310 Кб, 310-950 Кб, 950 Кб-2,9 Мб, 2,9 Мб-8,9 Мб, 8,9-26 Мб, >26 Мб, соответственно.
2.4 Схема адаптивного ERC
Система и способ хранения с адаптивным кодированием адаптивно выбирают соответствующее количество ERC фрагментов для эффективного сохранения контента в P2P сети надежным образом. Используя кривую границы файла, установленную на фиг. 6, один вариант осуществления системы адаптивно выбирает - использовать не-ERC и ERC с количеством фрагментов k=2, 4, 8, 16, 32, 64, 128, 256 для различных размеров файла. Адаптивный ERC подход сравнивается с фиксированным параметром ERC, и эта разность в использовании сетевой полосы частот показывается на фиг. 7 и Фиг. 8, где надежность однорангового узла равна 50% и 99%, соответственно. По сравнению с использованием фиксированного ERC количества фрагментов k=1 (не-ERC), 8, 32 и 256, адаптивный способ ERC может улучшить эффективность в среднем на 61%, 26%, 25% и 50% для надежности однорангового узла, равной 50%, и на 50%, 18%, 29% и 57% для надежности однорангового узла, равной 99%. Повышение эффективности является существенным.
В наиболее общем смысле один вариант осуществления процесса сохранения с адаптивным кодированием показывается на фиг. 9. Как показано на этапе 902 процесса, система хранения с адаптивным кодированием вычисляет границы оптимального размера файла для различного количества фрагментов. Подают (вводят) файл с заданным размером файла, подлежащий кодированию (этап 904 процесса). Выполняется проверка относительно того, соответствует ли размер входного файла кодированию без исправления ошибок (k=1), как показано на этапе 906 процесса. Если размер входного файла не соответствует ERC, файл кодируют без использования ERC (этап 908 процесса). Если размер файла соответствует диапазону размеров файла ERC, файл кодируют, используя кодирование ERC и количество фрагментов, соответствующих размеру файла входного файла, которое является оптимальным количеством фрагментов для файла этого размера (этап 910 процесса).
Главное применение процесса адаптивного ERC, описанного здесь, заключается в P2P (одноранговом) резервном копировании или восстановлении. Одноранговый узел может выполнять резервное копирование файлов на другие одноранговые узлы в сети и затем восстанавливать эти файлы, извлекая их из одноранговых узлов в сети в случае, если они потеряны (например, в случае, если они потеряны при аварийном отказе компьютера). В общем случае Фиг. 10 иллюстрирует примерную операционную блок-схему последовательности операций, показывающую, как методика хранения с адаптивным кодированием может использоваться в P2P системе. Следует заметить, что любые прямоугольники и взаимосвязи между прямоугольниками, которые представлены ломаными или пунктирными линиями на фиг. 10, представляют альтернативные варианты осуществления системы хранения с адаптивным кодированием, описанной ниже, и что любой или все эти альтернативные варианты осуществления, которые описаны ниже, могут использоваться в комбинации с другими альтернативными вариантами осуществления, которые описаны в данном документе.
В частности, как проиллюстрировано на фиг. 10, до операции по передаче данных, например, когда требуется выполнять резервное копирование данных в одноранговые узлы в сети, сервер 200 или одноранговый узел 220 кодирует 1000 данные, которые должны быть переданы другим одноранговым узлам для хранения. Система хранения с адаптивным кодированием способна работать с любым из ряда обычных кодеков, такими, как, например, MPEG 1/2/4, WMA, WMV и т.д. Кроме того, в течение процесса 1000 кодирования сервер 200 или одноранговый узел 220 также формирует как заголовок данных, так и сопутствующий файл, содержащий структуру данных.
Как описано выше, в одном варианте осуществления, как только данные закодированы 1000, закодированные пакеты данных разбиваются 1005 на ряд модулей данных фиксированного размера. Далее, как и с закодированными данными, заголовок данных и структура данных также разбиваются 1005 на ряд модулей данных того же самого фиксированного размера, который используется для разбиения кодированных пакетов данных. Разбиение 1005 этой информации на модули данных фиксированной длины позволяют одноранговым узлам предварительно распределить блоки памяти до операций по передаче данных, таким образом избегая в вычислительном отношении дорогих операций по распределению памяти в течение процесса передачи данных. Далее, использование меньших модулей (блоков) данных позволяет использовать более тонкое управление клиентом или одноранговым узлом, сохраняющим данные, по точной величине полосы частот, расходуемой каждым одноранговым узлом, чтобы удовлетворить клиентские запросы модулей данных во время операций передачи данных.
В дополнение к разбиению 1005 закодированные данные, заголовок данных и структура данных на меньшие модули данных, если используется отказоустойчивое кодирование с исправлением ошибок, используется дополнительный уровень кодирования, чтобы обеспечить увеличенную избыточность в обычной P2P среде, где обслуживающие одноранговые узлы являются неотъемлемо ненадежными. В частности, как описано выше, в одном варианте осуществления, если определено, что гибкое кодирование с исправлением ошибок является подходящим для файла данных, модули данных дополнительно разделяют на ряд блоков данных и используется процесс 1010 отказоустойчивого кодирования с исправлением ошибок, чтобы кодировать файл.
Использование такого кодирования 1010 гарантирует, что один или более одноранговых узлов будут иметь блоки данных, необходимые для восстановления конкретных модулей данных, в то же время упрощая требования в отношении клиента, чтобы идентифицировать, какой из одноранговых узлов содержит необходимые данные. Дополнительно, в одном варианте осуществления ключи отказоустойчивого кодирования с исправлением ошибок, используемые каждым обслуживающим одноранговым узлом 220, автоматически назначают для каждого однорангового узла сервером 200. Однако, в другом варианте осуществления каждый обслуживающий одноранговый узел 220 просто выбирает ключи отказоустойчивого кодирования с исправлением ошибок случайным образом. Эти ключи затем извлекаются клиентом 210, когда каждый одноранговый узел 220 первоначально выполняет контакт с клиентом.
Как только файл данных был первоначально закодирован 1000, разбит на модули данных 1005, и возможно дополнительно закодирован с исправлением ошибок 1010, получившиеся модули данных или блоки данных затем распределяются 1015 различным одноранговым узлам 220. Это распределение 1015 может быть преднамеренным в том смысле, что блоки или пакеты кодированных данных просто подаются полностью или частично ряду одноранговых узлов, где они затем кэшируется или сохраняются для будущей передачи данных при вызове клиентом, который желает извлечь данные.
Как только данные были распределены 1015 к обслуживающим одноранговым узлам 220, клиент 210 затем готов начать выдавать запросы данных этим одноранговым узлам в случае, когда клиент желает извлечь эти данные из запоминающего устройства. Далее, как отмечено выше, сервер 200 может также действовать как одноранговый узел 220 с целью передачи данных клиенту 210.
В этот момент клиент 210 начинает сеанс передачи данных посредством первого извлечения списка доступных обслуживающих одноранговых узлов 220. Этот список извлекают непосредственно из сервера 200, из одного из одноранговых узлов 220 или используя обычный способ с распределенной хеш-таблицей (DHT) для идентификации потенциальных обслуживающих одноранговых узлов. Как только клиент 1010 извлек список одноранговых узлов, клиент затем соединяется с каждым обслуживающим одноранговым узлом 220 и извлекает 1025 список доступных файлов из каждого однорангового узла. Как только клиент 210 извлек список доступных файлов каждого однорангового узла 220, клиент затем извлекает 1035 заголовок данных и структуру данных для данных, которые должны быть переданы, из одного или более одноранговых узлов посредством запрашивания модулей данных, соответствующих этой информации, из одного или более одноранговых узлов через сетевое соединение между клиентом и такими одноранговыми узлами.
Заголовок данных в общем случае содержит глобальную информацию, описывающую данные, например, количество каналов в данных, свойства и характеристики (частота дискретизации аудио, частота кадров/разрешение видео) каждого канала, используемые кодеки, владельца прав автора/авторских прав носителей, и так далее. Следовательно, извлечение заголовка данных в начале сеанса передачи данных позволяет клиенту 220 устанавливать или инициализировать 1040 необходимые инструментальные средства, чтобы декодировать 1065 впоследствии принимаемые пакеты до приема этих пакетов в течение сеанса передачи данных.
Далее, после извлечения 1035 структуры данных конкретных данных клиент анализирует эту структуру данных и вычисляет идентификаторы 1045 модулей данных из модулей данных переданных данных, которые должны быть запрошены во время процесса передачи данных. Клиент 210 затем запрашивает эти модули данных 1050 один за другим от одного или более одноранговых узлов 220.
Наконец, как только все модули данных, составляющие конкретный пакет данных, были извлечены в соответствии с запросом 1050 клиентом 210, эти пакеты данных повторно собираются 1055 в первоначальный пакет данных. Повторно собранные пакеты данных затем декодируются 1060 и могут быть восстановлены 1065 на клиенте 210.
3.0 Одноранговое хранение: политики и стратегии структуры
В дополнение к настройке ERC количества фрагментов на основании размера файла, который должен быть сохранен в P2P сети, эффективность может также быть повышена. Различные варианты осуществления системы хранения с адаптивным кодированием, описанной здесь, предназначены для повышения эффективности хранения, используя некоторые стратегии, которые описаны ниже. Эти стратегии могут использоваться вместе с системой хранения с адаптивным кодированием или использоваться в любой P2P сети.
3.1 Стоимость P2P хранения
В этом разделе хранение файла в P2P сети сравнивается с хранением файла непосредственно в сервере с надежностью "шесть девяток". Заметим, что P2P решение уменьшает полосу частот и стоимость сервера, но требует, чтобы одноранговый узел использовал большую полосу частот, чтобы распределить файл в запоминающее устройство P2P. Полное использование сетевой полосы частот увеличивается в P2P решении. Увеличение в ширине полосы для загрузки для клиента может рассматриваться как стоимость P2P системы хранения. Эта стоимость для различных значений надежности однорангового узла и размеров файла сведена в таблицу.
Стоимость увеличенного использования полосы частот в P2P
Размер файла
Надежность
10 Кб
100 Кб
1 Мб
10 Мб
100 Мб
10%
332,9
79,1
29,5
16,5
12,5
50%
51,0
12,11
4,34
2,23
1,56
99%
9,4
1,87
0,65
0,22
0,09
Заметим, что стоимость использования P2P хранения мала, если надежность однорангового узла высока и размер файла большой. Например, хранение 100 Мб файла в одноранговых узлах с надежностью 99% включает стоимость только 9%. Однако, когда надежность однорангового узла низка и размер файла мал, стоимость может быть существенной.
3-2 Политики P2P хранения
Из таблицы можно вывести следующую политику использования "облака" P2P запоминающих устройств.
a. Нужно использовать ненадежные одноранговые узлы для сохранения больших файлов и использовать надежные одноранговые узлы для сохранения маленьких файлов. Стоимость для P2P системы должен быть меньшей, если распределять большие файлы ненадежным одноранговым узлам и назначать меньшие файлы надежным одноранговым узлам.
b. Нужно использовать ненадежные одноранговые узлы для сохранения статических файлов и использовать надежные одноранговые узлы для сохранения динамических файлов. Вызывают те файлы, которые не изменяются как статические, и вызывают те файлы, которые постоянно изменяются как динамические. Множество маленьких статических файлов могут быть связаны в большой статический файл и сохранены в облаке P2P запоминающих устройств. Та же самая стратегия не эффективна для динамических файлов, поскольку изменение единственного файла требует, чтобы полный объединенный файл был обновлен.
Вывод этой политики состоит в том, что если использовать P2P сеть для хранения состояния приложения, информации состояния однорангового узла и так далее, нужно передавать информацию наиболее надежным одноранговым узлам сети. Если имеется ограничение, что файл, который содержит состояние приложения, должен быть помещен только в высоконадежные одноранговые узлы (в сущности, высоконадежные одноранговые узлы формируют подсеть, которые составляют ядра расширенной P2P сети), можно значительно уменьшить этот коэффициент дублирования и стоимость обновления файла состояния и повысить эффективность.
c. Ненадежным одноранговым узлам должно быть разрешено распределение меньше, и надежным одноранговым узлам должно быть разрешено распределять больше.
d. Меньшим файлам должна быть назначена более высокая стоимость распределения, а большим файлам должна быть назначена более низкая стоимость распределения.
Политики c) и d) предназначены для резервного P2P копирования и приложений поиска (извлечения), где одноранговый узел может распределять контент в P2P облако хранения, и хранить контент для других одноранговых узлов. Сбалансированная P2P сеть хранения должна позволять каждому одноранговому узлу балансировать его вклад и выгоду. В предыдущих работах было указано, что полоса частот является первичным ресурсом в приложении P2P хранения. Пусть вкладом однорангового узла является количество кодированных фрагментов, которые он принимает и хранит для других одноранговых узлов. Пусть выгода однорангового узла есть объем контента, который он распределяет в P2P облако. Учитывая, что низкая надежность ведет к более избыточному хранению данных, нужно налагать штраф на ненадежные одноранговые узлы так, чтобы им было разрешено распределять меньше, и вознаграждать надежные одноранговые узлы так, чтобы им было разрешено распределять больше. Такая политика может иметь положительную выгоду в P2P экономии, поскольку она может поощрять пользователя сохранять P2P приложение интерактивно, таким образом повышая общую надежность P2P сети и уменьшая требуемый коэффициент дублирования.
Можно также налагать штраф на распределение маленького файла посредством назначения ему высокой стоимости распределения, требуя, чтобы одноранговый узел пропорционально давал больший вклад; и вознаграждать распределение большого файла посредством назначения ему низкой стоимости распределения, позволяя одноранговому узлу пропорционально вносить меньший вклад. В качестве вывода, P2P приложения резервного копирования должны быть разработаны так, чтобы минимизировать частоту резервного копирования. Вместо немедленного обновления файла сразу после его изменения, можно рассматривать связывание множества изменений в большой файл и обновлять его только однажды, скажем каждую полночь, в P2P облако запоминающих устройств.
Один вариант осуществления системы и способа хранения с адаптивным кодированием, которые разработаны согласно вышеупомянутым политикам, показан на фиг. 11. Как показано на этапе 1102 процесса, определяется надежность каждого однорангового узла в распределенной или P2P сети. Вводят файл, который должен быть распределен или сохранен (этап 1104 процесса). Оценивают размер файла (этап 1106 процесса), и стоимость распределения назначают файлу на основании ожидаемой полосы частот сохранения в уравнении (7) (этап 1108 процесса). Если файл является большим файлом, может быть назначена более высокая стоимость распределения. Если файл маленький, файлу может быть назначен более низкая стоимость распределения. На основании размера файла система хранения с адаптивным кодированием выберет одноранговые узлы с надлежащей надежностью, чтобы сохранить файл (этап 1110 процесса). То есть используются одноранговые узлы, чья надежность ниже заданного порога, чтобы хранить и распределять большой файл, и используются одноранговые узлы, чья надежность выше заданного порога, чтобы сохранить и распределить маленький файл.
Другой вариант осуществления системы и способа хранения с адаптивным кодированием, которые разработаны согласно вышеупомянутым политикам, показан на фиг. 12. Как показано на этапе 1202 процесса, определяется надежность каждого однорангового узла в распределенной или P2P сети. Вводится файл, который должен быть распределен или сохранен (этап 1204 процесса). Этот файл сравнивают с тем же самым файлом, который был предварительно сохранен, чтобы определить, является ли файл статическим или динамическим (этап 1206 процесса). Первый раз, когда файл сохраняют, принимается, что файл является динамическим. Если частые наблюдаются изменения к файлу, этот файл остается обозначенным как динамический. Если наблюдается, что файл не изменяется в течение длительного периода времени, файл обозначают как статический. Динамические файлы сохраняют в высоконадежных одноранговых узлах (этап 1210 процесса). (Таким образом, сначала файлы должны быть сохранены в серверах или высоконадежных одноранговых узлах.) Как только наблюдается, что файлы не изменяются и они станут статическими, эти статические файлы будут перераспределены и сохранены в одноранговых узлах более низкой надежности.
Следует заметить, что варианты осуществления, показанные на фиг. 11 и 12, могут использоваться поодиночке или в комбинации, чтобы повысить общую эффективность и надежность распределенной или одноранговой сети.
3.3 P2P хранение с поддержкой компонента сервера
Если компонент сервера используется в дополнении P2P сети, можно использовать P2P хранение для больших и статических файлов, и использовать этот сервер для маленьких, динамических файлов. Так как имеются большие файлы, которые потребляют большинство ресурса сервера, P2P хранение хорошо дополняет сервер.
Как показано на фиг. 13, один вариант осуществления системы и процесса хранения с адаптивным кодированием использует резервное копирование P2P с серверной поддержкой. Как показано на фиг. 13, динамические файлы в сети копируются в сервер (этап 1302 процесса). Клиент и/или сервер могут затем автоматически обнаруживать те динамические файлы, которые не изменяются больше и превращаются в статические файлы (этап 1304, 1306 процесса). Эти обнаруженные статические файлы затем могут быть связаны вместе в большой файл, как показано на этапе 1308 процесса, и распределены с ERC в P2P облако хранения (этап 1310 процесса). Это эффективно увеличивает размер файла, сохраненного в P2P облаке. В объединении с ERC большого количества фрагментов это может повысить эффективность.
Вариант осуществления, показанный на фиг. 13, может использоваться поодиночке или в комбинации с вариантами осуществления, показанными на фиг. 11 и 12, чтобы повысить общую эффективность и надежность распределенной или одноранговой сети. Следует также заметить, что этот вариант осуществления может использоваться как с гибким кодированием с исправлением ошибок и без него.
Следует заметить, что любой или все вышеупомянутые альтернативные варианты осуществления могут использоваться в любой комбинации, требуемой для формирования дополнительных гибридных вариантов осуществления. Хотя предмет изобретения был описан на языке, специфическом для структурных особенностей и/или методологических действий, должно быть понятно, что предмет, определенный в прилагаемой формуле изобретения, не обязательно ограничен конкретными признаками или действиями, описанными выше. Вместо этого, конкретные признаки и действия, описанные выше, раскрыты как формы примера осуществления формулы изобретения.