Эффективный алгоритм и протокол для удаленного дифференциального сжатия

Эффективный алгоритм и протокол для удаленного дифференциального сжатия

Иллюстрации

Показать все

Реферат

Область техники, к которой относится изобретение

Настоящее изобретение, в общем, относится к обновлению объектов данных через сети с ограниченной пропускной способностью. Более конкретно, настоящее изобретение относится к системе и способу для дифференциальной передачи данных объекта с использованием методики удаленного дифференциального сжатия (RDC). Для дополнительной минимизации нагрузки пропускной способности при передаче больших объектов может использоваться рекурсивное применение методики RDC.

Предшествующий уровень техники

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

Распространенным способом передачи через сеть с ограниченной пропускной способностью больших объемов данных стали способы сжатия данных. Сжатие данных может быть охарактеризовано, в основном, как сжатие без потерь или с потерями. Сжатие без потерь включает в себя такое преобразование набора данных, чтобы при применении преобразования восстановления (сжатых данных) могло быть восстановлено точное воспроизведение набора данных. Сжатие без потерь наиболее часто используется для уплотнения данных, когда требуется точная копия.

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

Сущность изобретения

Вкратце, настоящее изобретение относится к способу и системе для обновления объектов через сети с ограниченной пропускной способностью. Осуществляется обновление объектов между двумя или большим количеством вычислительных устройств с использованием способов удаленного дифференциального сжатия (RDC) так, чтобы были минимизированы необходимые передачи данных. Согласно одному аспекту, эффективные передачи больших объектов достигаются при рекурсивном применении алгоритма RDC к его собственным метаданным; в этом случае для уменьшения объема метаданных, передаваемых через сеть алгоритмом RDC, используется один рекурсивный этап или несколько рекурсивных этапов. Объекты и/или списки сигнатур и длин порций могут быть разделены на порции посредством размещения границ в динамически определяемых местоположениях. Математическая функция оценивает значения хеш-функции, ассоциированные в пределах окна горизонта относительно возможной границы порции. Описанные способ и система удобны в ряде приложений с сетевой структурой, таких как одноранговые репликаторы, клиенты и серверы электронной почты, системы кэширования стороны клиента, универсальные утилиты копирования, репликаторы базы данных, порталы, услуги обновления программного обеспечения, синхронизация файлов/данных и другие.

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

ПЕРЕЧЕНЬ ФИГУР ЧЕРТЕЖЕЙ

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

Фиг.1 - диаграмма, иллюстрирующая рабочую среду.

Фиг.2 - диаграмма, иллюстрирующая возможный вариант вычислительного устройства.

Фиг.3A и 3B - диаграммы, иллюстрирующие возможную процедуру RDC.

Фиг.4A и 4B - диаграммы, иллюстрирующие последовательности операций взаимодействия между локальным устройством и удаленным устройством в продолжение возможной процедуры RDC.

Фиг.5A и 5B - диаграммы, иллюстрирующие последовательности операций рекурсивного удаленного дифференциального сжатия списков сигнатуры и длины порции при возможном обмене информацией в продолжение процедуры RDC.

Фиг.6 - диаграмма, графически иллюстрирующая возможный вариант рекурсивного сжатия в возможной последовательности RDC.

Фиг.7 - диаграмма, иллюстрирующая взаимодействие между клиентским и серверным приложениями с использованием возможной процедуры RDC.

Фиг.8 - диаграмма, иллюстрирующая последовательность операций для возможной процедуры разделения на порции.

Фиг.9 - диаграмма возможного набора инструкций для возможной процедуры разделения на порции.

Фиг.10 и 11 - диаграммы другого возможного набора инструкций для другой возможной процедуры разделения на порции, сконфигурированного по меньшей мере согласно одному аспекту настоящего изобретения.

ПОДРОБНОЕ ОПИСАНИЕ ПРЕДПОЧТИТЕЛЬНОГО ВАРИАНТА ОСУЩЕСТВЛЕНИЯ

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

Настоящее изобретение описано в контексте локальных и удаленных вычислительных устройств (или, для краткости, "устройств"), имеющих один или большее количество общеассоциированных объектов, которые на них хранятся. Термины "локальный" и "удаленный" относятся к одному варианту способа. Однако в различных вариантах одно и то же устройство может играть роль и "локального", и "удаленного". Способы удаленного дифференциального сжатия (RDC) используются для эффективного обновления общеассоциированных объектов через сеть связи с ограниченной пропускной способностью. Когда устройству, имеющему новую копию объекта, требуется обновить устройство, имеющее более старую копию этого объекта или подобного объекта, применяется способ RDC для передачи через сеть связи только отличий между объектами. Описанный возможный способ RDC использует (1) рекурсивный подход для передачи метаданных RDC для уменьшения объема метаданных, передаваемых для больших объектов, и (2) способ разделения на порции на основе локального максимума для увеличения точности, соответствующей дифференцированию объектов, чтобы минимизировать нагрузку пропускной способности. Некоторые возможные приложения, которые выигрывают от описанных способов RDC, включают в себя: одноранговые службы репликации, протоколы передачи файлов, такие как SMB (блок серверных сообщений), виртуальные серверы, передающие большие изображения, серверы электронной почты, синхронизацию сотового телефона и PDA (персонального цифрового информационного устройства), репликацию сервера базы данных и т.д.

Рабочая среда

Фиг.1 - диаграмма, иллюстрирующая возможную рабочую среду для настоящего изобретения. Как изображено на чертеже, устройства сконфигурированы для связи через сеть. Указанными устройствами могут быть универсальное вычислительное устройство, специализированное вычислительное устройство или любые другие соответствующие устройства, которые подсоединены к сети. Сеть 102 может соответствовать любой топологии связности, включая, но не в ограничительном смысле, прямое кабельное соединение (например, параллельный порт, последовательный порт, универсальную последовательную шину (USB), IEEE 1394 и т.д.), беспроводное соединение (например, инфракрасный (IR) порт, порт Bluetooth и т.д.), проводную сеть, беспроводную сеть, локальную сеть, глобальную сеть, ультра-глобальную сеть, интернет, интранет и эксранет.

При возможном взаимодействии между устройством A (100) и устройством B (101) на этих двух устройствах локально хранятся разные версии объекта: объект O_A на 100 и объект O_B на 101. В некоторый момент времени устройство A (100) принимает решение обновить копию объекта O_A копией (объекта O_B), которая хранится на устройстве B (101), и передает в устройство B (101) запрос на инициирование способа RDC. В альтернативном варианте осуществления способ RDC может быть инициирован устройством B (101).

Устройство A (100) и устройство B (101) обрабатывают объект, который хранится на них локально, и разделяют ассоциированные данные на изменяемое количество порций способом, зависящим от данных, (например, порции 1-n для объекта O_B и порций 1-k для объекта O_A соответственно). Обоими устройствами локально вычисляется набор сигнатур, например, значений сильных хэш-функций (SHA), для порций. Оба устройства компилируют отдельные списки сигнатур. В продолжение следующего этапа способа RDC устройство B (101) передает в устройство A (100) через сеть 102 связи вычисленный им список сигнатур и длин порций 1-n. Устройство A (100) оценивает этот список сигнатур, сравнивая каждую принятую сигнатуру со сформированным им списком сигнатур 1-k. Несоответствия в списках сигнатур указывают одно или большее количество отличий в объектах, которые требуют корректировки. Устройство A (100) передает в устройство B (101) запрос на передачу порций, которые были идентифицированы несоответствиями в списках сигнатур. Потом устройство B (101) сжимает и передает запрошенные порции, которые затем, после выполнения приема и восстановления сжатых данных, повторно собираются устройством A (100). Устройство A (100) повторно собирает принятые порции совместно с собственными соответствующими порциями для получения локальной копии объекта O_B.

Возможное вычислительное устройство

Фиг.2 - блочная диаграмма возможного вычислительного устройства, сконфигурированного в соответствии с настоящим изобретением. В базовой конфигурации вычислительное устройство 200 обычно содержит по меньшей мере один процессор (202) и системную память (204). В зависимости от точной конфигурации и вида вычислительного устройства, системная память 204 может быть энергозависимой (например, оперативным запоминающим устройством (RAM, ОЗУ)), энергонезависимой (например, постоянным запоминающим устройством (ROM, ПЗУ), флэш-памятью и т.д.) или некоторой их комбинацией. Системная память 204 обычно содержит операционную систему (205), один или большее количество программных модулей (206), и может содержать данные (207) программ. Указанная базовая конфигурация изображена на фиг.2 компонентами внутри пунктирной линии 208.

Вычислительное устройство 200 может также иметь дополнительные признаки или функциональные возможности. Например, вычислительное устройство 200 также может содержать дополнительные запоминающие устройства для хранения данных (съемные и/или несъемные), такие, например, как магнитные диски, оптические диски или ленту. Такое дополнительное запоминающее устройство иллюстрируется на фиг.2 съемным запоминающим устройством (ЗУ) 209 и несъемным запоминающим устройством 210. Компьютерные носители данных могут включать в себя энергозависимые и энергонезависимые, съемные и несъемные носители, реализованные любым способом или технологией для хранения информации, такой как машиночитаемые инструкции, структуры данных, программные модули или другие данные. Системная память 204, съемное запоминающее устройство 209 и несъемное запоминающее устройство 210, - все являются примерами компьютерных носителей данных. Компьютерные носители данных включают в себя, но не в ограничительном смысле ОЗУ, ПЗУ, электрически стираемое программируемое ПЗУ (EEPROM), флэш-память или память другой технологии, CD-ROM, цифровые универсальные диски (DVD) или другие оптические запоминающие устройства, магнитные кассеты, магнитную ленту, накопитель на магнитных дисках или другие магнитные запоминающие устройства, или любой другой носитель информации, который может использоваться для хранения требуемой информации и к которому может осуществить доступ вычислительное устройство 200. Любой такой компьютерный носитель данных может быть частью устройства 200. Вычислительное устройство 200 также может иметь устройство(а) 212 ввода данных, такое как клавиатура, мышь, перо, устройство ввода речи, сенсорное устройство ввода данных и т.д. Также может быть включено устройство(а) вывода 214 данных, такое как дисплей, динамики, принтер и т.д. Все указанные устройства известны в технике и их описание здесь не требуется.

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

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

Удаленное дифференциальное сжатие (RDC)

Фиг.3A и 3B - диаграммы, иллюстрирующие возможную процедуру RDC согласно по меньшей мере одному аспекту настоящего изобретения. Количество порций, в частности, может варьироваться для каждого варианта, в зависимости от фактических объектов O_A и O_B.

Согласно фиг.3A, между двумя вычислительными устройствами (устройством A и устройством B) выполняется согласование основного протокола RDC. Протокол RDC неявно предполагает, что устройства A и B имеют два различных варианта (или версии) одного объекта или ресурса, которые идентифицированы вариантами (или версиями) объекта O_A и O_B, соответственно. Для примера, иллюстрируемого этим чертежом, устройство A имеет старую версию ресурса O_A, в то время как устройство B имеет версию O_B с небольшим (или инкрементальным) отличием в содержимом (или данных), ассоциированном с ресурсом.

Ниже описан протокол для передачи обновленного объекта O_B из устройства B в устройство A. Подобный протокол может использоваться для передачи объекта из устройства A в устройство B, и эта передача может быть инициирована по требованию любого из устройств A и B без существенного изменения протокола, описанного ниже.

1. Устройство A передает в устройство B запрос на передачу Объекта O_B с использованием протокола RDC. В альтернативном варианте осуществления устройство B инициирует передачу; в этом случае протокол опускает этап 1 и начинается с этапа 2, приведенного ниже.

2. Устройство A разбивает Объект O_A на порции 1-k и вычисляет сигнатуру Sig_Ai и длину (или размер в байтах) Len_Ai для каждой порции 1 … k Объекта O_A. Разбиение на порции будет подробно описано ниже. Устройство A сохраняет список сигнатур и длин порций ((Sig_A1, Len_A1) … (Sig_Ak, Len_Ak)).

3. Устройство B разбивает Объект O_B на порции 1-n и вычисляет сигнатуру Sig_Bi и длину Len_Bi для каждой порции 1 … n Объекта O_B. Алгоритм разбиения, используемый на этапе 3, должен соответствовать алгоритму разбиения на этапе 2, приведенному выше.

4. Устройство B передает в устройство A список вычисленных сигнатур порций и длин порций ((Sig_B1, Len_B1) … (Sig_Bn, Len_Bn)), ассоциированных с Объектом O_B. Информация длин порций может быть использована впоследствии устройством A для запроса определенного набора порций посредством их идентификации их начальным смещением и их длиной. Из-за последовательного характера списка можно вычислить начальное смещение в байтах каждой порции Bi посредством суммирования длин всех предшествующих порций в списке.

В другом варианте осуществления список сигнатур порций и длин порций, до передачи в устройство A, компактно кодируется и дополнительно сжимается с использованием алгоритма сжатия без потерь.

5. После приема упомянутых данных устройство A сравнивает принятый список сигнатур с сигнатурами Sig_A1 … Sig_Ak, вычисленными для Объекта O_A на этапе 2, которые ассоциированы со старой версией содержимого.

6. Устройство A передает в устройство B запрос на все порции, сигнатуры которых, принятые из устройства B на этапе 4, не соответствуют ни одной из сигнатур, вычисленных устройством A на этапе 2. Для каждой запрошенной порции Bi запрос содержит начальное смещение порции, вычисленное устройством A на этапе 4, и длину порции.

7. Устройство B передает в устройство A содержимое, ассоциированное со всеми запрошенными порциями. До передачи в устройство A содержимое, передаваемое устройством B, может быть дополнительно сжато с использованием алгоритма сжатия без потерь.

8. Устройство A воссоздает локальную копию Объекта O_B с использованием порций, принятых из устройства B на этапе 7, а также собственных порций Объекта O_A, соответствующих сигнатурам, переданным устройством B на этапе 4. Порядок, в котором локальные и удаленные порции повторно компонуются в устройстве A, определен списком сигнатур порций, принятых устройством A на этапе 4.

Этапы 2 и 3 разбиения могут выполняться способом, зависящим от данных, который использует функцию снятия опознавательного признака, которая вычисляется в каждой позиции байта в ассоциированном объекте (O_A и O_B соответственно). Для заданной позиции функция снятия опознавательного признака вычисляется с использованием малого окна данных, окружающего эту позицию в объекте; значение функции снятия опознавательного признака зависит от всех байтов объекта, включенных в упомянутое окно. Функцией снятия опознавательного признака может быть любая подходящая функция, такая, например, как хэш-функция или полином Рабина (Rabin).

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

Список сигнатур и длин порций, передаваемый на этапе 4, обеспечивает основу для воссоздания объекта с использованием исходных порций и идентифицированных обновленных или новых порций. Порции, запрашиваемые на этапе 6, идентифицированы их смещениями и длинами. Объект воссоздается на устройстве A с использованием локальных и удаленных порций, сигнатуры которых соответствуют сигнатурам, принятым устройством A на этапе 4, в том же порядке.

После завершения устройством A этапа воссоздания, Объект O_A может быть удален и заменен копией Объекта O_B, которая была воссоздана в устройстве A. В других вариантах осуществления устройство может сохранить Объект O_A для возможного "повторного использования" порций в продолжение будущих передач RDC.

Для больших объектов, для варианта основного протокола RDC, иллюстрируемого фиг.3A, характерен существенный фиксированный объем дополнительной служебной информации на этапе 4, даже если Объект O_A и Объект O_B очень близки или идентичны. При заданном среднем размере порции, равном C, объем информации, передаваемой через сеть связи на этапе 4, пропорционален размеру Объекта O_B, в частности, он пропорционален размеру Объекта O_B, деленному на C, что составляет количество порций Объекта B, и соответственно пар (сигнатура порции, длина порции), передаваемых на этапе 4.

Например, согласно фиг.6, большой образ (например, виртуальный образ жесткого диска, используемый монитором виртуальных машин, таким, например, как Microsoft Virtual Server (Виртуальный сервер), может привести к Объекту (O_B) размером 9,1 Гбайт. Для среднего размера C порции, равного 3 Кбайт, объект 9 Гбайт может привести к 3 миллионам порций, сформированных для Объекта O_B, с 42 Мбайт ассоциированной информации сигнатур и длин порций, которую требуется передать через сеть на этапе 4. Так как 42 Мбайт информации сигнатур требуется передать через сеть связи, даже когда отличия между Объектом O_A и Объектом O_B (и, соответственно, объем данных, который требуется передать на этапе 7) очень малы, расходы на фиксированную дополнительную служебную информацию протокола чрезмерно высоки.

Такие расходы на фиксированную дополнительную служебную информацию могут быть существенно снижены с использованием рекурсивного применения протокола RDC вместо передачи информации сигнатур на этапе 4. Согласно фиг.3B, ниже описаны дополнительные этапы 4.2-4.8, заменяющие этап 4 основного алгоритма RDC. Этапы 4.2-4.8 соответствуют рекурсивному применению этапов 2-8 из основного протокола RDC, описанного выше. Рекурсивное применение может быть дополнительно использовано для этапа 4.4, представленного ниже, и так далее, до требуемой глубины рекурсии.

4.2. Устройство A выполняет рекурсивное разделение своего списка сигнатур и длин порций ((Sig_A1, Len_A1) … (Sig_Ak, Len_Ak)) на рекурсивные порции сигнатур, получая другой список рекурсивных сигнатур и рекурсивных длин порций ((RSig_A1, RLen_A1) … (RSig_As, RLen_As)), где s << k.

4.3. Устройство B рекурсивно набирает список сигнатур и длин порций ((Sig_B1, Len_B1) … (Sig_Bn, Len_Bn)) для создания списка рекурсивных сигнатур и рекурсивных длин порций ((RSig_B1, RLen_B1) … (RSig_Br, RLen_Br)), где r << n.

4.4. Устройство B передает упорядоченный список рекурсивных сигнатур и рекурсивных длин порций ((RSig_B1, RLen_B1) … (RSig_Br, RLen_Br)) в устройство A. Список рекурсивных сигнатур порций и рекурсивных длин порций, до передачи в устройство A, компактно кодируется и может быть сжат дополнительно с использованием алгоритма сжатия без потерь.

4.5. Устройство A сравнивает рекурсивные сигнатуры, принятые из устройства B, с собственным списком рекурсивных сигнатур, вычисленным на этапе 4.2.

4.6. Устройство A передает в устройство B запрос на каждую отдельную рекурсивную порцию сигнатуры (с рекурсивной сигнатурой RSig_Bk), для которой устройство A не имеет соответствующей рекурсивной сигнатуры в своем

наборе (Rsig_A1 … RSig_As).

4.7. Устройство B передает в устройство A запрошенные рекурсивные порции сигнатур. Запрошенные рекурсивные порции сигнатур, до передачи в устройство A, могут быть дополнительно сжаты с использованием алгоритма сжатия без потерь.

4.8. Устройство A воссоздает список сигнатур и информации порций ((Sig_B1, Len_B1) … (Sig_Bn, Len_Bn)) с использованием локальных соответствующих рекурсивных порций сигнатур и рекурсивных порций, принятых из устройства B на этапе 4.7.

После завершения этапа 4.8, представленного выше, выполнение продолжается на этапе 5 основного протокола RDC, описанного выше, который иллюстрируется фиг.3A.

В результате операций рекурсивного разделения на порции количество рекурсивных сигнатур, ассоциированных с объектами, уменьшается с коэффициентом, равным среднему размеру порции C, приводя к существенно меньшему количеству рекурсивных сигнатур (r << n для объекта O_B и s << k для объекта O_A соответственно). В одном варианте осуществления для разделения сигнатур на порции могут использоваться те же параметры разделения на порции, что для разделения на порции исходных объектов O_A и O_B. В альтернативном варианте осуществления для рекурсивных этапов могут использоваться другие параметры разделения на порции.

Для очень больших объектов рекурсивные этапы, упомянутые выше, могут быть применены k раз, где k ≥1. Для среднего размера порции C рекурсивное разделение на порции может уменьшить объем трафика сигнатур через сеть (этапы с 4.2 по 4.8) с коэффициентом, приблизительно соответствующим C^k. Так как C является относительно большим, то глубина рекурсии, превышающая единицу, может потребоваться только для очень больших объектов.

В одном варианте осуществления количество рекурсивных этапов может определяться динамически при рассмотрении параметров, которые включают в себя один или большее количество из следующих параметров: ожидаемый средний размер порции, размер объектов O_A и/или O_B, формат данных объектов O_A и/или O_B, задержки и характеристики пропускной способности сетевого соединения устройства A и устройства B.

Используемая на этапе 2 функция снятия опознавательного признака соответствует функции снятия опознавательного признака, используемой на этапе 3. Аналогично, функция снятия опознавательного признака, используемая на этапе 4.2, соответствует функции снятия опознавательного признака, используемой на этапе 4.3. Функция снятия опознавательного признака из этапов 2-3 может, в необязательном порядке, соответствовать функции снятия опознавательного признака из этапов 4.2-4.3.

Как описано ранее, каждая функция снятия опознавательного признака использует малое окно данных, которое окружает позицию в объекте, при этом значение, ассоциированное с функцией снятия опознавательного признака, зависит от всех байтов объекта, которые включены в пределы упомянутого окна данных. Размер окна данных может корректироваться динамически на основе одного или большего количества критериев. Кроме того, процедура разделения на порции использует значение функции снятия опознавательного признака и один или большее количество дополнительных параметров разделения на порции для определения границ порций на этапах 2-3 и 4.2-4.3, представленных выше.

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

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

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

Возможная последовательность операций

Фиг.4A и 4B - диаграммы, иллюстрирующие последовательности операций для взаимодействия между локальным устройством (например, устройством A) и удаленным устройством (например, устройством B) в продолжение возможной процедуры RDC, которая сконфигурирована в соответствии по меньшей мере с одним аспектом настоящего изобретения. Левая сторона фиг.4A иллюстрирует этапы 400-413, которые выполняются на локальном устройстве A, в то время как правая сторона фиг.4A иллюстрирует этапы 450-456, которые выполняются на удаленном устройстве B.

Согласно фиг.4A, взаимодействие начинается запросом устройством A передачи объекта O_B согласно RDC на этапе 400 и приемом этого запроса устройством B на этапе 450. После этого локальное устройство A и удаленное устройство B независимо вычисляют опознавательные признаки на этапах 401 и 451, разделяют свои объекты на порции на этапах 402 и 452 и вычисляют сигнатуры (например, SHA) для каждой порции на этапах 403 и 453 соответственно.

На этапе 454 устройство B передает список сигнатур и длин порций, вычисленный на этапах 452 и 453, в устройство A, которое принимает эту информацию на этапе 404.

На этапе 405 локальное устройство A инициализирует список запрошенных порций пустым списком (Empty) и инициализирует смещение (OFFSET) слежения для удаленных порций нулем (0). На этапе 406 выбирается для рассмотрения следующая пара (сигнатура, длина порции) (Sig_Bi, Len_Bi) из списка, принятого на этапе 404. На этапе 407 устройство A проверяет, соответствует ли сигнатура Sig_Bi, выбранная на этапе 406, какой-либо из сигнатур, вычисленных им в продолжение этапа 403. Если соответствует, то выполнение продолжается на этапе 409. Если не соответствует, то на этапе 408 в список запроса добавляются смещение слежения удаленной порции и длина в байтах Len_Bi. На этапе 409 смещение слежения увеличивается на длину текущей порции Len_Bi.

На этапе 410 локальное устройство A тестирует, все ли пары (сигнатура, длина порции), принятые на этапе 404, обработаны. Если нет, то выполнение продолжается на этапе 406. Иначе, на этапе 411 список запроса на порцию кодируется соответствующим образом в компактном режиме, сжимается и передается в удаленное устройство B.

Удаленное устройство B принимает сжатый список порций на этапе 455, восстанавливает его, затем сжимает и передает обратно данные порций на этапе 456.

На этапе 412 локальное устройство принимает и восстанавливает запрошенные данные порций. На этапе 413 локальные устройства, используя локальную копию объекта O_A и принятые данные порций, повторно собирают локальную копию O_B.

Фиг.4B подробно иллюстрирует пример этапа 413 по фиг.4A. Обработка продолжается на этапе 414, где локальное устройство A инициализирует воссозданный объект в пустой объект (Empty).

На этапе 415 выбирается для рассмотрения следующая пара (сигнатура, длина порции) (Sig_Bi, Len_Bi) из списка, принятого на этапе 404. На этапе 416 устройство A проверяет, соответствует ли сигнатура Sig_Bi, выбранная на этапе 417, какой-либо из сигнатур, вычисленных им в продолжение этапа 403.

Если соответствует, то выполнение продолжается на этапе 417, где к воссозданному объекту присоединяется соответствующая локальная порция. Если не соответствует, то на этапе 418 к воссозданному объекту присоединяется принятая и восстановленная удаленная порция.

На этапе 419 локальное устройство A тестирует, все ли пары (сигнатура, длина порции), принятые на этапе 404, обработаны. Если нет, то выполнение продолжается на этапе 415. Иначе, воссозданный объект используется на этапе 420 для замены старой копии объекта O_A на устройстве A.

Возможная последовательность операций для рекурсивной передачи сигнатур.

Фиг.5A и 5B - диаграммы, иллюстрирующие последовательности операций для рекурсивной передачи списка сигнатур и длин порций в возможной процедуре RDC, которая сконфигурирована согласно по меньшей мере одному аспекту настоящего изобретения. Описанная ниже процедура может быть применена в отношении и локального, и удаленного устройства, которые осуществляют попытку обновить общеассоциированные объекты.

Левая сторона фиг.5A иллюстрирует этапы 501-513, которые выполняются на локальном устройстве A, в то время как правая сторона фиг.5A иллюстрирует этапы 551-556, которые выполняются на удаленном устройстве B. Этапы 501-513 заменяют этап 404 по фиг.4A, в то время как этапы 551-556 заменяют этап 454 по фиг.4A.

На этапах 501 и 551 локальное устройство A и удаленное устройство B независимо вычисляют рекурсивные опознавательные признаки своих списков сигнатур и длин порций ((Sig_A1, Len_A1), … (Sig_Ak, Len_Ak)) и ((Sig_B1, Len_B1), … (Sig_Bn, Len_Bn)), соответственно, которые были вычислены на этапах 402/403 и 452/453, соответственно. На этапах 502 и 552 устройства разделяют свои соответствующие списки сигнатур и длин порций на рекурсивные порции, и на этапах 503 и 553 вычисляют рекурсивные сигнатуры (например, SHA) для каждой рекурсивной порции, соответственно.

На этапе 554 устройство B передает рекурсивный список сигнатур и длин порций, вычисленный на этапах 552 и 553, в устройство A, которое принимает эту информацию на этапе 504.

На этапе 505 локальное устройство инициализирует список запрошенных рекурсивных порций пустым списком и инициализирует смещение слежения удаленной рекурсивной порции для удаленных рекурсивных порций в 0. На этапе 506 выбирается для рассмотрения следующая пара (рекурсивная сигнатура, рекурсивная длина порции) (RSig_Bi, RLen_Bi) из списка, принятого на этапе 504. На этапе 507 устройство A проверяет, согласуется ли рекурсивная сигнатура RSig_Bi, выбранная на этапе 506, с какой-либо из рекурсивных сигнатур, вычисленных им в продолжение этапа 503. Если согласуется, то выполнение продолжается на этапе 509. Если не согласуется, то на этапе 508 смещение слежения удаленной рекурсивной порции и длина в байтах RLen_Bi добавляются в список запроса. На этапе 509 смещение слежения удаленной рекурсивной порции увеличивается на длину текущей рекурсивной порции RLen_Bi.

На этапе 510 локальное устройство A тестирует, все ли пары (рекурсивная сигнатура, рекурсивная длина порции), принятые на этапе 504, обработаны. Если нет, то выполнение продолжается на этапе 506. Иначе, список запроса на рекурсивную порцию компактно кодируется, сжимается и передается в удаленное устройство B на этапе 511.

Удаленное устройство B принимает сжатый список рекурсивных порций на этапе 555, восстанавливает список