МОДЕЛЬ СИНХРОНИЗАЦИИ РАВНОПРАВНЫХ УЧАСТНИКОВ Российский патент 2011 года по МПК G06F17/40 

Уровень техники

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

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

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

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

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

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

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

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

Краткое описание чертежей

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

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

Фиг.3 является схематическим изображением системы синхронизации одной реализации с обработчиками для образования интерфейса с устройствами участников.

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

Фиг.5 является схематическим изображением приложения синхронизации одной реализации.

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

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

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

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

Фиг.10-11 иллюстрируют типичную запись на устройстве частичного участника перед модификацией и после модификации устройством частичного участника.

Фиг.12 иллюстрирует типичную запись на устройстве частичного участника перед модификацией.

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

Фиг.14 иллюстрирует типичную запись на фиг.12, которая обновляется устройством полного участника после определения того, что частичный участник модифицировал данные, как описано в отслеживающей изменение записи на фиг.13.

Фиг.15 является примером записи знаний, хранимой на устройстве частичного участника или устройстве полного участника для одной реализации.

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

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

Фиг.18 иллюстрирует пример сообщества синхронизации для одной реализации.

Фиг.19 показывает участника и повременную иллюстрацию одной реализации, показывающей изменение, добавляемое к этому участнику, и знания участника, обновляемые для включения этого изменения.

Фиг.20 иллюстрирует одну реализацию повременного сценария репликации между двумя участниками.

Фиг.21 иллюстрирует одну реализацию повременного сценария детектирования (обнаружения) конфликта.

Фиг.22 иллюстрирует пример назначения идентификаторов изменения к изменениям в участнике в одной реализации.

Фиг.23 иллюстрирует одну реализацию повременного сценария репликации с использованием векторов знаний.

Фиг.24А иллюстрирует одну реализацию обновления знаний в участнике, следующего за репликацией, с использованием списка исключений.

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

Фиг.24С иллюстрирует одну реализацию обновления знаний в участнике, следующего за репликацией, где исключения существуют в обновленных знаниях.

Фиг.25 иллюстрирует топологию «подключайся и говори» одной реализации для реализации репликации, включающей в себя репликацию замещения.

Фиг.26А иллюстрирует примеры сценариев разрешения конфликтов в одной реализации.

Фиг.26В иллюстрирует другие сценарии разрешения конфликтов в одной реализации.

Подробное описание

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

Эта система может быть описана в общем контексте как один или несколько способов, которые улучшают синхронизацию данных между различными устройствами, имеющими различные возможности, но эта система также служит и для других целей в дополнение к этим. В одной реализации, один или несколько способов, описанные здесь, могут быть реализованы как особенности программы синхронизации, такой как MICROSOFT^® ACTIVESYNC^®, или любого другого типа программы или службы, которая участвует в процессе синхронизации между устройствами. В другой реализации, один или несколько способов, описанных здесь, реализованы как особенности с другими приложениями, которые имеют дело с синхронизацией данных по устройствам и/или службам. Термин «мобильное устройство», который используется здесь, означает включение сотовых телефонов, карманных компьютеров, портативных устройств воспроизведения мультимедийных данных, телефонов голос-через-IP и многочисленных других типов мобильных устройств различных уровней возможностей.

Фиг.1 является схематическим изображением модели синхронизации равноправных участников одной реализации, показывающим графическое представление полного участника 10, частичного участника 20 и простого участника 30. Термин «участник» также называется здесь «репликой» (точной копией). Участник и реплика относятся к устройствам и/или службам, которые участвуют в сообществе синхронизации. Полный участник 10 имеет хранилище 12 данных знаний и способность понимать знания 14. Он также имеет хранилище 16 данных синхронизации для хранения действительных данных, которые были синхронизированы, например, такие как контактная информация или другая информация, синхронизируемая между устройствами. Некоторые не ограничивающие примеры полных участников включают в себя персональные компьютеры, некоторые PDA, некоторые телефоны, некоторые другие мобильные устройства и/или другие устройства, способные хранить и понимать знания.

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

Подобно полному участнику 10, частичный участник 20 также содержит хранилище 22 данных знаний. В отличие от полного участника 10, однако, частичный участник 20 не имеет способности (или ограниченной способности) понимать знания 24. Частичный участник включает в себя хранилище 26 данных синхронизации для хранения синхронизируемых данных. Частичный участник включает в себя хранилище 25 данных версии для хранения информации, относящейся к изменениям, которые он производит с хранилищем 26 данных синхронизации. Не ограничивающие примеры частичных участников могут включать в себя некоторые карманные компьютеры, телефоны, некоторые другие мобильные устройства и/или другие типы устройств, способных управлять простой программой, которая отслеживает изменения, сделанные с хранилищем 26 данных синхронизации.

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

Обращаясь теперь к фиг.2, показано табличное представление 50 модели равноправных участников. Простой участник 52, частичный участник 54 и полный участник 56 имеют одну или несколько характеристик. Некоторые из этих характеристик были описаны в обсуждении фиг.1. Простой участник 52, например, не способен хранить знания 58. Простой участник способен к синхронизации 60 с единственным полным участником через обработчик. Частичный участник 54 хранит, но не понимает знания 62. Частичный участник 54 способен участвовать в двусторонней синхронизации 64 со многими «хозяевами». Альтернативно или дополнительно, частичный участник 54 способен к синхронизации 66 через обработчик на полном участнике. Таким образом, частичный участник 54 способен участвовать в управляемом сценарии равноправных узлов через одно или несколько устройств полных участников. Таким образом, частичные участники могут синхронизироваться друг с другом через использование полного участника. Полный участник 56 понимает и хранит знания 68, может участвовать в двусторонней синхронизации 70 со многими «хозяевами» и может выполнять синхронизации 72 равноправных узлов.

Фиг.3 является схематическим изображением системы 80 синхронизации одной реализации с обработчиками для образования интерфейса с одним или несколькими устройствами участников. Приложение 82 синхронизации включает в себя машину 84 оркестровки синхронизации, которая отвечает за завершение цикла синхронизации среди участников и перенос обновленных изменений между другими подключенными участниками. Различные обработчики 86, 88 и 90 используются для того, чтобы дать возможность другим участникам в сообществе синхронизации связываться с машиной 84 синхронизации. Машина 84 синхронизации связывается с обработчиками 86, 88 и 90 через интерфейсы 91, 92 и 97 обработчиков, соответственно. Обработчики 86, 88 и 90 затем связываются с хранилищами 93 и 95 знаний, локальным хранилищем 94 данных синхронизации и удаленным хранилищем 96 данных синхронизации для доступа к данным, если они применяются. В одной реализации, одно или несколько хранилищ данных, показанных на фиг.1, такие как удаленное хранилище 96 данных синхронизации, расположены на одном или нескольких отдельных компьютерах или устройствах.

Как показано на фиг.4, типичная компьютерная система для использования для реализации одной или нескольких частей этой системы включает в себя вычислительное устройство, такое как персональное вычислительное устройство 100. В его основной конфигурации, вычислительное устройство 100 обычно включает в себя один процессор 102 и память 104. В зависимости от точной конфигурации и типа вычислительного устройства, память 104 может быть энергозависимой (такая как RAM), энергонезависимой (такая как ROM, флэш-память и т.д.) или некоторой комбинацией этих двух. Эта наиболее основная конфигурация показана на фиг.4 пунктирной линией 106.

Кроме того, устройство 100 может также иметь дополнительные особенности/функциональность. Например, устройство 100 может также включать в себя дополнительное запоминающее устройство (съемное и/или несъемное), включающее в себя, но не ограниченное этим, магнитные или оптические диски или ленту. Такое дополнительное запоминающее устройство показано на фиг.4 посредством съемного запоминающего устройства 108 и несъемного запоминающего устройства 110. Компьютерные носители данных включают в себя энергозависимые и энергонезависимые, съемные и несъемные носители, реализуемые в любом способе или технологии для хранения информации, такой как считываемые компьютером инструкции, структуры данных, программные модули или другие данные. Память 104, съемное запоминающее устройство 108 и несъемное запоминающее устройство 110 являются примерами компьютерных носителей данных. Компьютерные носители данных включают в себя, но не ограничены этим, RAM, ROM, EEPROM, флэш-память или другие технологии памяти, CD-ROM, цифровые универсальные диски (DVD) или другие оптические запоминающие устройства, магнитные кассеты, магнитную ленту, запоминающее устройство на магнитных дисках или другие устройства магнитной памяти или любые другие носители, которые могут использоваться для хранения желаемой информации и которые могут быть доступны для устройства 100. Любые такие носители данных могут быть частью устройства 100.

Вычислительное устройство 100 включает в себя одно или несколько соединений 114 связи, которые дают вычислительному устройству 100 возможность связываться с другими устройствами 115, такими как полные участники, частичные участники и/или простые участники. Вычислительное устройство 100 может также связываться с другими компьютерами и/или приложениями 113. Устройство 100 может также иметь устройство (устройства) 112 ввода, такое как клавиатура, мышь, перо, устройство ввода голосом, сенсорное устройство ввода и т.д. Устройство (устройства) 111 вывода, такие как дисплей, громкоговорители, принтер и т.д. могут быть также включены. Эти устройства хорошо известны в данной области техники и не нуждаются в дальнейшем обсуждении здесь.

В одной реализации, вычислительное устройство 100 служит как устройство полного участника для реализации одного или нескольких способов, обсуждаемых здесь. В таких реализациях, вычислительное устройство 100 содержит приложение 122 синхронизации с машиной 124 оркестровки синхронизации, а также хранилище 125 данных знаний и хранилище 126 данных синхронизации. В одной реализации, хранилище 125 данных знаний и/или хранилище 126 данных синхронизации включены как часть компьютерных носителей данных, описываемых здесь, таких как память 104, съемное запоминающее устройство 108, несъемное запоминающее устройство 110 и/или другие компьютерные носители данных. В одной реализации, приложение 122 синхронизации является тем же самым, что и приложение 82 синхронизации, показанное на фиг.3.

Обращаясь к фиг.5 с продолженной ссылкой на фиг.4, показано приложение 200 синхронизации одной реализации. В одной реализации, приложение 200 синхронизации является одной из прикладных программ, которые находятся на вычислительном устройстве 100. Альтернативно или дополнительно, одна или несколько частей приложения 200 синхронизации может быть частью системной памяти 104, на других компьютерах и/или приложениях 113, или других таких вариациях, которые пришли бы на ум специалисту в компьютерном программном обеспечении.

Приложение 200 синхронизации включает в себя программную логику (логические схемы) 204, которая отвечает за выполнение некоторых или всех способов, описанных здесь. Программная логика 204 включает в себя логику для регистрации обработчиков для каждого устройства и/или службы для участия в процессе 206 синхронизации; логику для детектирования типа подключенного устройства и/или службы 208 (простой, частичный или полный участник); логику для принятия знаний от частичного участника, осуществляющего модификации в случае исключений, и переносящего знания обратно к частичному участнику 210; логику для детектирования изменений на простых участниках и сохранения конфликтов в его собственном локальном хранилище 212 данных; логику для работы с другим полным участником (участниками) для синхронизации измененных наборов данных с использованием знаний 214; логику для выполнения оркестровки для завершения цикла синхронизации и передачи обновленных изменений между другими подключенными устройствами и/или службами 216; и другую логику для управления приложением 220.

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

Фиг.6 является блок-схемой последовательности операций процесса высокого уровня для приложения 200 синхронизации. В одной форме, процесс на фиг.6 по меньшей мере частично реализован в логике работы вычислительного устройства 100, других компьютеров/приложений 113 и/или устройств 115 другого участника. Эта процедура начинается в точке 240 начала с подключения устройства или службы участника к полному участнику (такому как вычислительное устройство 100 или некоторые мобильные устройства) машиной синхронизации (стадия 242). Это устройство или служба регистрирует обработчик или иным образом связывается с машиной синхронизации на полном участнике (стадия 244). Машина синхронизации детектирует тип этого устройства или службы (стадия 246) и выполняет соответствующую логику синхронизации на основе типа участника: простой (точка 248 принятия решения), частичный (точка 250 принятия решения) или полный (точка 252 принятия решения). Например, если устройство или служба является простым участником, который имеет хранилище данных синхронизации, но не имеет знаний (точка 248 принятия решения), то машина синхронизации детектирует изменения на простом участнике и сохраняет любые конфликты в своем собственном локальном хранилище данных на полном участнике (стадия 254).

Если устройство или служба является частичным участником, который имеет хранилище данных синхронизации и хранимые-но-не-понятые знания (точка 250 принятия решения), то это устройство или служба предоставляет свое хранилище знаний машине синхронизации на полном участнике (стадия 258). Этот полный участник осуществляет модификации этих знаний, например, в случае исключений (стадия 260), и полный участник переносит измененные знания обратно к частичному участнику (стадия 262). Знания, переносимые на устройстве или службе частичного участника, позволяют ему надежно синхронизироваться со многими «хозяевами» даже когда происходят исключения (стадия 264). Если устройство или служба является полным участником, который имеет хранилище данных синхронизации, а также хранит и понимает знания (точка 252 принятия решения), то оба участника знают, как оптимально синхронизировать измененные наборы данных с использованием знаний (стадия 266). Одна или несколько реализаций для синхронизации данных между полными участниками подробно описаны в обсуждении фиг.18-26.

После определения типа участника, который имеет устройство или службу, и обработки изменений и конфликтов, соответственно, машина синхронизации следует оркестровке для завершения цикла синхронизации и передачи обновленных изменений между другими подключенными устройствами и/или службами участников (стадия 256). Этот процесс заканчивается в конечной точке 268.

Фиг.7 является блок-схемой последовательности операций процесса, иллюстрирующей стадии, включенные в обновление и синхронизацию данных с использованием устройства частичного участника. В одной форме, процесс на фиг.7 является по меньшей мере частично реализованным в логике работы вычислительного устройства 100, других компьютеров/приложений 113 и/или устройств 115 других участников. Эта процедура начинается в точке 280 начала с обеспечения устройства или службы частичного участника хранилищем данных для хранения данных, извлекаемых во время процесса синхронизации, и хранилищем данных версии для хранения информации, относящейся к изменениям, осуществляемым над этими данными (например, в векторной, строковой и/или другой форме для отслеживания изменений, которые увидел полный участник (участники)/«хозяин» («хозяева»)) (стадия 282). Некоторые не ограничивающие примеры частичных участников включают в себя некоторые Web-службы, некоторые флэшки, некоторые мобильные устройства, такие как некоторые PDA и/или некоторые телефоны, и/или другие устройства или службы, которые могут хранить знания, но не понимают их.

Частичный участник не знает, как понять знания, а просто хранит их (стадия 284). Частичный участник принимает запрос (требование) от пользователя изменить некоторые или все данные в хранилище данных синхронизации (стадия 286). Частичный участник изменяет эти данные в хранилище данных, как потребовал пользователь (стадия 288). Частичный участник отвечает за отслеживание того, какие изменения данных он осуществил, и, таким образом, сохраняет информацию, относящуюся к изменениям, которые он осуществил на основании запроса пользователя (стадия 290). В одной реализации, когда частичный участник синхронизируется с некоторым полным участником, синхронизация имеет место от полного к частичному и от частичного к полному (стадия 292). В одной реализации, это две отдельных односторонних синхронизации. В других реализациях, также возможны и другие порядки и/или сценарии синхронизации, такие как единственная односторонняя синхронизация. Во время синхронизации, любые изменения, которые осуществляются частичным участником, извлекаются полным участником (стадия 294). Полный участник обновляет хранилище данных и знания на частичном участнике после разрешения каких-либо конфликтов (стадия 296). Этот процесс заканчивается в конечной точке 298.

Фиг.8 является блок-схемой последовательности операций процесса для одной реализации, иллюстрирующей стадии, включенные в отслеживание частичным участником изменений данных посредством обновления записи с новым тактовым отсчетом или другим идентификатором. В одной форме, процесс на фиг.8 по меньшей мере частично реализуется в логике работы вычислительного устройства 100, других компьютеров/приложений 113 и/или устройств 115 других участников. Процедура начинается в начальной точке 300 с частичного участника, отвечающего за отслеживание изменений, которые он осуществляет с данными (стадия 302). Частичный участник обновляет запись хранилища данных версии для указания того, что произошло некоторое изменение (стадия 304). В качестве некоторых не ограничивающих примеров, хранилище данных версии может быть обновлено новым тактовым отсчетом, версией или другим идентификатором, который идентифицирует (распознает), что запись изменилась, и/или который идентифицирует последнее устройство или службу, которая осуществила это изменение. Полный участник считывает измененный тактовый отсчет или другой идентификатор для того, чтобы узнать, что конкретная запись была изменена частичным участником (стадия 306). Этот процесс заканчивается в конечной точке 308.

Фиг.9 является блок-схемой последовательности операций процесса, иллюстрирующей стадии, включенные в одну реализацию, где частичный участник отслеживает изменения, которые он осуществил с данными, посредством отдельного сохранения идентификатора записи и даты/времени для этого изменения. В одной форме, процесс на фиг.9 по меньшей мере частично реализуется в логике работы вычислительного устройства 100, других компьютеров/приложений 113 и/или устройств 115 других участников. Процедура начинается в начальной точке 310 с частичного участника, отвечающего за отслеживание того, какие изменения он осуществляет с данными (стадия 312). Частичный участник отслеживает уникальный идентификатор, который идентифицирует запись точной копии (реплики) и метку даты/времени, указывающую дату/время, когда эта запись была изменена (стадия 314). Полный участник считывает этот уникальный идентификатор и метку даты/времени для того, чтобы узнать, что эта конкретная запись изменилась (стадия 316). Полный участник обновляет тактовый отсчет или другой идентификатор, который идентифицирует последнее устройство или службу для изменения этой записи, которое в этом случае является частичным участником (стадия 318). Этот процесс заканчивается в конечной точке 320.

Фиг.10-11 иллюстрируют типичную запись на устройстве частичного участника перед модификацией и после модификации устройством частичного участника согласно стадиям, описанным на фиг.8. В одной реализации, запись 330 фиг.10 включает в себя поле 332 идентификатора реплики, поле 334 тактового отсчета последнего участника, который изменил запись, и поле 334 локального тактового отсчета, когда запись пришла от полного участника 336. Соответствующие значения 338, 340 и 342 в полях 332, 334 и 336, соответственно, могут храниться в строке, векторе и/или любом другом типе представления, подходящем для хранения на устройствах или службах, имеющих ограниченную емкость хранилища и/или ресурсы. Как описано ранее, многочисленные другие вариации могут также использоваться для указания того, что конкретная запись на частичном участнике была изменена.

Обращаясь к фиг.11, запись 343 показывает данные после того, как они были исправлены частичным участником и на нем. Поле 332 идентификатора реплики осталось значением «Х1» (350), так как это уникальный идентификатор для этой записи. Поле 334 тактового отсчета последнего компьютера, который изменил запись, было модифицировано со значения «G66» (340 на фиг. 10) на значение «G67» (352). «G» представляет участника, который осуществил изменение, а «67» является следующим более высоким числом, доступным в последовательности тактового счетчика. Локальный тактовый отсчет, когда он пришел от поля 336 полного участника, остается тем же самым значением «34» (354).

Фиг.12 иллюстрирует типичную запись на устройстве частичного участника перед модификацией согласно стадиям, описанным на фиг.9. Подобно примеру на фиг.10 и 11, запись 360 включает в себя значение 368 для поля 362 идентификатора реплики, значение 370 для поля 364 тактового отсчета последнего участника, который изменил запись, и значение 372 для поля 366 локального тактового отсчета, когда он пришел от полного участника. В этой реализации, частичный участник обновляет отдельную запись отслеживания изменения вместо записи с тактовым отсчетом. Запись 360 показывает запись с тактовым отсчетом перед модификацией лежащих ниже данных частичным участником. Запись 375 на фиг.13 иллюстрирует типичную запись отслеживания изменений на устройстве частичного участника, которое будет отслеживать изменения, осуществляемые с записью фиг.12, согласно стадиям, описанным на фиг.9. Поле 374 идентификатора реплики и поле 376 даты/времени, когда запись изменилась, хранятся на частичном участнике. В этом примере, значение «Х1» 378 хранится для идентификатора 374 реплики, а «01-26-06-12:32PM» 380 хранится для поля 376 даты/времени. Когда частичный участник следующим подключается к полному участнику, полный участник извлекает и интерпретирует запись 375 для определения того, что частичный участник осуществил изменения лежащих ниже данных в хранилище данных синхронизации. Обращаясь к фиг.14, полный участник затем обновляет поле 390 тактового отсчета записи 381 последнего участника, который изменил запись, которой в этом случае является «G67» для представления частичного участника и следующего более высокого числа тактового отсчета. Поле 366 локального тактового отсчета исправляется на обновленное значение 392, если соответствует. Значение 388 для поля 362 идентификатора реплики остается тем же самым.

Фиг.15 является примером записи знаний, хранимой на устройстве частичного участника или устройстве полного участника для одной реализации. В показанном примере, запись 396 знаний представлена как вектор строк, описанный здесь, со значениями 398, 400, 402 и 404, указывающими идентификатор участника и порядковый номер для последних изменений, которые были увидены для этого конкретного устройства. Например, значение «G100» (398) означает, что этот участник увидел все изменения для устройства G через запись 100. Эти векторы знаний описаны более подробно в обсуждении фиг.18-26.

Обращаясь к фиг.16, показана блок-схема последовательности операций процесса, иллюстрирующая стадии, включенные в обновление и синхронизацию данных с использованием устройства простого участника. В одной форме, процесс на фиг.16 по меньшей мере частично реализуется в логике работы вычислительного устройства 100, других компьютеров/приложений 113 и/или устройств 115 других участников. Процедура начинается в начальной точке 420 с предоставления устройства или службы простого участника, который имеет хранилище данных для хранения синхронизируемых данных, но не имеет знаний (стадия 424). Некоторые не ограничивающие примеры простых устройств включают в себя некоторые флэшки, некоторые карты/платы памяти, некоторые PDA, некоторые сотовые телефоны и/или другие устройства или службы, которые не могут хранить и понимать знания. Простой участник не может хранить и понимать знания (стадия 426) из-за ограничений устройства или службы или настроек пользователя. Простой участник принимает запрос (требование) от пользователя изменить некоторые или все данные в хранилище данных синхронизации (стадия 428).

Простой участник изменяет данные в хранилище данных синхронизации по требованию пользователя (стадия 430). Один не ограничивающий пример того, как пользователь может изменять хранилище данных синхронизации, включает в себя модификацию этих данных в броузере файлов от другого устройства, такого как персональный компьютер, например, вставку флэшки в персональный компьютер и последующее изменение содержимого флэшки. Простой участник не отвечает за отслеживание того, какие изменения данных он осуществил, так как предполагается, что он ничего не знает (стадия 432). Когда простой участник синхронизируется с полным участником, синхронизация происходит от полного участника к простому, а затем от простого к полному (стадия 434). Во время синхронизации, любые изменения, осуществленные простым участником с хранилищем данных синхронизации, извлекаются полным участником (стадия 436). Полный участник обновляет хранилище данных синхронизации на простом участнике после разрешения каких-либо конфликтов (стадия 438). Этот процесс заканчивается в конечной точке 440.

Фиг.17 является схематическим изображением типичного сообщества синхронизации для одной реализации, имеющей множественные устройства и обработчики. Фиг.17 показывает полного участника 500, называемого персональным компьютером 1, или «PC1» (506); простого участника, называемого устройством 1 (514); частичного участника 502, называемого «Служба 1»; и второго полного участника 504, называемого персональным компьютером 2, или «PC2». Для иллюстрации, предположим, что устройством 1 (514) является флэшка или другая плата памяти, службой 1 является музыкальная служба, расположенная на Web-сервере, а PC1 и PC2 - персональные компьютеры, подобные вычислительному устройству 100. Полный участник 500 имеет обработчики 508, 510 и 512, а полный участник 504 имеет обработчики 516, 518 и 520. Эти обработчики отвечают за сопряжение с различными участниками, которые являются частью сообщества синхронизации. Когда устройство 1 (514) подключается к PC1 (506), выполняется процесс синхронизации, описанный на фиг.6. Определяется тип участника, который в этом случае является простым, а затем происходит синхронизация между устройством 1 (514) и PC1 (506) полного участника 500. После завершения синхронизации между этими двумя участниками (500 и 514), оркестровка вызовет обновление других участников (502 и 504), если они подключены, и/или когда в следующий раз они подключатся к PC1 (506) или Устройству 1 (514).

Обращаясь к фиг.18-26, описана одна или несколько реализаций для синхронизации данных между полными участниками (например, двумя персональными компьютерами, такими как устройство 100). Один или несколько примеров, обсуждаемых на фиг.18-26, могли бы также применяться по меньшей мере в некоторой части к сценарию частичного участника или другим сценариям, описанным в предыдущих чертежах. Альтернативно или дополнительно, один или несколько способов, обсуждаемых на фиг.18-26, могут быть реализованы на таком устройстве, как вычислительное устройство 100 на фиг.4. Термин «реплика», используемый в следующем обсуждении, также означает «участник».

Реплики/участники в сообществе синхронизации дублируют посредством обеспечения их собственных знаний репликой (точной копией), которую они дублируют. Для уменьшения величины данных, представляющих знания, которые должны посылаться между дублированием реплик, эти знания могут быть выражены как вектор знаний, как описано ранее. Таким образом, знания, которые посылаются между репликами, необязательно включают в себя каждый идентификатор изменения, а могут быть в форме вектора, который представляет собой некоторое количество идентификаторов изменений. Например, если реплика знает обо всех изменениях, осуществленных репликой А, от первого изменения до десятого изменения, и все изменения, сделанные репликой, помеченной В, от первого изменения до пятого изменения, то реплика могла бы послать вектор А10В5 знаний, указывающий, что реплика знает обо всех изменениях, соответствующих идентификаторам А1-А10 изменений, и всех изменениях, соответствующих идентификаторам В1-В5 изменений. Хотя эти знания могут быть выражены как вектор знаний, другие реализации изобретения рассматривают также и другие выражения знаний. Например, некоторые реализации изобретения выражают знания с использованием любого выражения знаний, в котором кто-либо может (1) добавить изменение к выражению знаний, (2) проверить, включено ли это изменение в выражение знаний, и (3) объединить два выражения знаний вместе.

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

На фиг.18, реплика А 1102 может быть электронным образом связана с репликой В 1104 через линию 1106 связи. Реплика А 1102 может быть подключена через линию 1108 связи к реплике С 1110. Реплика С 1110 может быть подключена к реплике В 1104 через линию 1112 связи. Реплика С 1110 может быть дополнительно подключена к реплике D 1114 через линию 1116 связи. В этом сообществе 1100 синхронизации, хотя не все реплики непосредственно подключены через линии связи, изменения в любой из реплик может быть дублировано в любую из других реплик в пределах сообщества 1100 синхронизации.

Например, для реплики А 1102, подлежащей дублированию с репликой D 1114, реплики А 1102 и С 1110 могут быть дублированы через линию 1108 связи. Таким образом, реплика С 1110 включает в себя изменения, сделанные на реплике А 1102. Реплики С и D затем дублируются через линию 1116 связи, и как таковая реплика D 1114 включает в себя изменения от реплики А 1102. Таким образом, реплика А 1102 может дублироваться с репликой D 1114 без какого-либо сорта прямой линии связи. Фактически, реплики А 1102 и D 1114 могут даже не знать о существовании друг друга в пределах сообщества 1100 синхронизации. Иллюстрированные линии связи могут быть проводными и/или беспроводными линиями связи.

Со ссылкой на фиг.19, одна реализация изобретения иллюстрирует, как управляют изменениями в реплике. Фиг.19 показывает повременную последовательность реплики А 1200. Реплика А 1200 включает в себя знания 1202, в данном случае помеченные К_А, и изменения 1204, в данном случае помеченные Δ_А. Каждое изменение в изменениях 1204 является текущим содержанием данных некоторого элемента. Изменением может быть новый элемент, добавленный к реплике, даже хотя ни один элемент не был изменен per se (на стандартную редакцию), удаление элемента и т.п. Каждое из изменений 1204 связано с некоторой версией, которой в одной реализации изобретения является идентификатор изменения. Заметно, что одним выгодным аспектом изобретения является то, что нет необходимости поддерживать журнал (регистрации) изменений, включающий в себя информацию о предыдущих изменениях. Точнее, каждая реплика включает в себя знания и базу данных изменений (т.е. текущих элементов), где каждое изменение имеет соответствующую версию. В момент времени (1), реплика А 1200 находится в неизменном состоянии. В момент времени (2), пользователь вводит изменение, помеченное Х, в реплику А 1200. Фиг.19 показывает изменение Х, добавляемое как компонент изменений 1204. Знания 1202 обновляются для включения идентификатора изменения, ChangeID(X), который связан с изменением Х и идентифицирует добавление изменения Х к изменениям 1204. Эта реализация иллюстрирует один способ, в котором изменения к реплике связаны с конкретными идентификаторами изменений. Знания 1202 могут быть вектором знаний и представляют собой изменения, о которых знает реплика А 1200. В одной реализации данного изобретения, версии или идентификаторы изменений поддерживаются для элементов или объектов в базе данных, и эти версии могут использоваться для идентификации того, что необходимо дублировать. Альтернативно, может также поддерживаться журнал (регистрации) изменений.

Фиг.20 иллюстрирует использование знаний для перечисления изменений во время репликации. Фиг.20 показывает две реплики, а именно, реплику А 1302 и реплику В 1304. Реплика А 1302 включает в себя набор изменений 1306, в этом примере помеченный Δ_А. Реплика А 1302 дополнительно включает в себя знания 1308, в этом примере помеченные К_А. Знания 1308 включают в себя список идентификаторов изменений, таких как описаны выше. Подобным же образом, реплика В 1304 включает в себя набор изменений 1310, каждое из которых связано с некоторой версией, которая является идентификатором изменения. Для начала репликации, в момент времени (1) реплика А 1302 посылает запрос синхронизации к реплике В 1304, которая включает в себя знания 1308. Реплика В 1304, посредством сравнения знаний 1308 с версиями, связанными с каждым из изменений в наборе изменений 1310, может принимать решения, касающиеся того, какие изменения 1310 реплики В реплика А 1302 уже имеет в своих изменениях 1306, и какие изменения известны реплике А. Альтернативно, реплика В 1304 сравнивает знания 1308 с версией каждого элемента. Таким образом, реплика В 1304 посылает реплике А 1302 в момент времени (2) только ту часть изменений 1310 реплики В, которые связаны с версиями, которые не включены в знания 1308 реплики А 1302, как показано изменениями 1314. Например, если вектором знаний реплики А был А3В12, и реплика В имеет текущие изменения, связанные с версиями, которыми являются идентификаторы В13 и В14 изменений, то изменения, посланные к реплике А, включали бы в себя изменения, связанные с идентификаторами В13 и В14 изменений. В одной реализации, посылается только В14, если В13 и В14 были сделаны с одним и тем же элементом.

Кроме того, реплика В 1304 также посылает знания 1312 реплики В к реплике А 1302. Поскольку реплика В 1304 послала все изменения 1310, доступные в реплике В 1304 уже не в реплике А 1302, к реплике А 1302, реплика А 1302 теперь имеет все изменения 1306, которые первоначально были в реплике А 1302, поскольку этим изменениям 1310 не предшествовали изменения, посланные репликой В 1304, в дополнение к изменениям 1310, которые первоначально были в реплике В 1304. Реплика А 1302 далее имеет информацию обо всех изменениях, которые были известны реплике В 1304. Следовательно, реплика А 1302 может обновить свои знания 1308 для того, чтобы отразить добавление изменений 1310. Это делается просто добавлением знаний 1308 реплики А к знаниям 1312 реплики В и определением этого значения как знания 1308 реплики А, как показано в момент времени (3) на фиг.20.

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

В дополнение к перечислению изменений, знания реплики могут также использоваться в детектировании конфликтов. Со ссылкой на фиг.21, одна реализация данного изобретения показывает, как может быть выполнено детектирование конфликтов. Фиг.21 показывает две реплики, соединенные электронной линией связи (беспроводной и/или проводной) для связи и репликации. Реплика А 1402 включает в себя знания 1408 и набор изменений 1406. Как и с примером на фиг.20, знания 1408 включают в себя коллекцию идентификаторов изменений, связанных с изменениями 1406 и связанных с предыдущими изменениями. Реплика А 1402 дополнительно включает в себя, для целей этого примера, изменение некоторого элемента, сделанное в реплике А 1402. Это изменение помечено Х, и Х является компонентом изменений 1406. Подобным же образом, реплика В 1404 включает в себя знания 1412, коллекцию элементов 1410, каждый с его текущей версией (идентификатором изменения). Иллюстративно, в момент времени (1) реплика А 1402 посылает изменение Х к реплике В 1404.

Связанными с изменением Х и посылаемыми с ним являются две другие величины, а именно, идентификатор изменения, связанный с изменением Х, помеченный ChangeID(X), и «сделанная-со-знанием» величина, помеченная К_А(Х). «Сделанной-со-знанием» величиной являются знания, которые существовали в реплике А 1402 в момент времени, когда изменение Х было сделано с репликой А 1402. Альтернативно, в некоторых реализациях изобретения «сделанными-со-знанием» могут быть знания, которые существовали в некоторой реплике, когда послано изменение. Текущие знания 1408 реплики А могут также посылаться к реплике В 1404. Как показано в момент времени (2), реплика В 1404 сравнивает элемент, измененный изменением Х, с элементом, измененным изменением Y, для определения того, может ли А-изменение (Х) конфликтовать с В-состоянием.

Если изменения относятся к различным версиям одного и того же элемента, то необходим дальнейший анализ. Реплика В 1404 затем проверяет, чтобы увидеть, было ли изменение Х известно реплике В 1404, когда изменение Y было сделано в реплике В 1404. Изменение Y имеет идентификатор изменения, ChangeID(Y), и «сделанную со знанием» величину, К_В(Y), связанную с ним. Если ChangeID(X) является компонентом изменения Y «сделанной со знанием», К_В(Y), то конфликта нет. Другими словами, изменение Y было сделано в реплике В 1404 со знанием изменения Х, сделанного в реплике А 1402. По существу, изменение Y теперь представляет собой наиболее современные и действительные данные для реплик А и В. Хотя это и не показано в примере, иллюстрированном на фиг.21, в последующее время, изменение Y вероятно будет послано к реплике А 1402, и элемент, связанный с изменениями Х и Y, обновится в изменение Y на реплике А 1402 способом, описанным на фиг.20.

Если изменения Х и Y предназначены для одного и того же элемента, и ChangeID(X) не появляется в К_В(Y), то, как показано в момент времени (4), осуществляется проверка того, было ли известно изменение Y реплике А 1402, когда было сделано изменение Х. Это обычно делается посредством проверки того, включено ли перечисление изменений для изменения Y, показанного как ChangeID(Y), в знания 1408 реплики А в момент времени, когда было сделано изменение Х, К_А(Х). Если ChangeID(Y) является компонентом К_А(Х), то изменение Х было «сделано со знанием» изменения Y, и конфликта нет. Изменение Х является наиболее современным и действительным изменением для этого конкретного элемента. По существу, реплика В 1404 вероятно будет обновлена изменением Х способом, описанным на фиг.20.

Если изменения Х и Y предназначены для одного и того же элемента, ChangeID(Y) не появляется в К_А(Х), и ChangeID(X) не появляется в К_В(Y), то существует конфликт истинности. Другими словами, изменение Х и изменение Y были сделаны независимыми друг от друга. В этом случае, конфликт будет сообщен, и различные правила разрешения конфликтов могут быть применены для определения, какое изменение, Х или Y, является наиболее современным и действительным изменением. Такие правила могут включать в себя проверку меток времени для определения того, какое изменение было сделано наиболее недавно, постоянное разрешение конфликтов в пользу определенного типа реплик (таких как реплики, хранимые на серверах) и/или любое другое подходящее разрешение конфликтов. Альтернативно, в одной форме разрешения конфликтов, элемент с конфликтующими изменениями может быть обновлен таким образом, что конфликтующие изменения объединяются для образования нового изменения.

Со ссылкой на фиг.22, показана одна типичная реализация идентификаторов изменений и отслеживание знаний. Фиг.22 показывает реплику 1502. Реплика 1502 включает в себя коллекцию изменений 1506 и знания 1508. Коллекция изменений 1506 включает в себя несколько индивидуальных изменений 1510 в этом примере, показанных как Х, Y и Z. В примере, показанном на фиг.22, данное состояние знаний реплики обозначено вектором 1512 знаний, которым в этом случае является А4. Вектор 1512 знаний представляет собой все знания 1508 реплики А.

Также на фиг.22 представлено некоторое количество идентификаторов 1514 изменений. В примере фиг.22, реплика А 1502 включает в себя три измененных элемента 1516, I_X, I_Y и I_Z, соответствующих изменениям 1510. С использованием идентификаторов изменений, можно понять, что элемент I_X, с идентификатором изменения А1, был сделан в реплике А 1502 в первое время. Изменение I_Y, с идентификатором изменения А2, было сделано в реплике А 1502 в момент времени, последующий по отношению к элементу I_X. И элемент I_Z, с идентификатором А4 изменения, был сделан в реплике А 1502 во время, последующее к тому, когда был сделан элемент I_Y. А3, хотя и не показанный непосредственно на фиг.22, может соответствовать предыдущему изменению, например, в одном примере, изменению, которое предшествует изменению элемента I_Z, помеченному А4.

Существует различие между идентификатором А4 изменения и вектором 1512 знаний реплики А, который также помечен А4. В этом примере, вектор А4 знаний означает, что знания 1508 реплики А включают в себя изменения, соответствующие идентификаторам изменений, помеченным А4, А3, А2 и А1. Другими словами, вектор знаний включает в себя изменение, представленное идентификатором 1518 изменения, который равен вектору знаний, а также все изменения с одним и тем же идентификатором реплики, которые были сделаны ранее идентификатора 1518 изменения, представленного в векторе знаний. С другой стороны, в данном примере, идентификатор 1518 изменения, помеченный А4, представляет собой только изменение Z, сделанное с элементом I_Z.

Со ссылкой на фиг.23, показан пример дублирования двух реплик в топологии, содержащей некоторое количество реплик. Реплика А 1602 содержит набор изменений 1604, знания 1606 и вектор 1608 знаний, который является сокращенным представлением знаний 1606. Иллюстративно, вектор 1608 знаний реплики А 1602, А5В3С1D10, показывает, что знания 1606 реплики А включают в себя изменения, сделанные вплоть до пятого изменения в реплике А 1602, знания вплоть до третьего изменения в реплике В 1610, знания вплоть до первого изменения в реплике С и знания вплоть до десятого изменения в реплике D. Реплика В 1610, в примере на фиг.23, включает в себя набор изменений 1612, знания 1614 и вектор 1616 знаний, который является сокращенным представлением знаний 1614 реплики В. Вектор 1616 знаний реплики В, А3В3С5D8, показывает, что реплика В имеет знания, включающие в себя знания вплоть до третьего изменения, сделанного репликой А 1602, знания вплоть до третьего изменения, сделанного репликой В 1610, знания вплоть до пятого изменения, сделанного репликой С, и знания вплоть до восьмого изменения, сделанного репликой D. Векторы знаний, изложенные выше, включают в себя непрерывное представление перечислений изменений, сделанных репликой от первого изменения до некоторого последующего изменения. Как будет объяснено более подробно позже, вектор знаний может также включать в себя точку начала, которая является некоторым другим перечислением изменений, чем первое перечисление изменений, сделанный репликой.

Повременная иллюстрация репликации реплики А 1602 с репликой В 1610 показана на фиг.23. В момент времени (1), реплика А 1602 посылает запрос 1618 синхронизации вместе со знаниями 1606 реплики А, которые могут быть представлены вектором 1608 знаний реплики А, к реплике В 1610. Реплика В 1610 в момент времени (2) проверяет знания 1606 реплики А путем сравнения их с идентификаторами изменений, связанными с изменениями в реплике В. Реплика В 1610 обнаруживает, что реплика А не знает об изменениях, сделанных репликой С, которые помечены идентификаторами С2, С3, С4 и С5 изменений. Таким образом, реплика В посылает изменения 1612 реплики В, соответствующие этим идентификаторам изменений, пока изменения, помеченные этими идентификаторами изменений, являются текущими изменениями, применимыми к элементам в реплике В 1610. Если идентификатор изменения соответствует предыдущему устаревшему изменению, то изменение, соответствующее этому идентификатору, не посылается. Например, если элемент, который имел версию С3, был обновлен и назначен новой версией, то изменение, связанное с С3, больше не существует в реплике В 1610 и не посылается к реплике А. В последующем или одновременно, как показано, в момент времени (3) реплика В 1610 посылает к реплике А 1602 знания 1614 реплики В, которые могут быть представлены как вектор 1616 знаний.

В момент времени (4) реплика А 1602 проверяет знания 1614 путем сравнения их с идентификаторами изменения, соответствующими изменениям в реплике А 1602. Реплика А 1602 обнаруживает, что реплика В не имеет ни изменений, представленных идентификаторами А4, А5, D9 и D10 изменений, ни знаний об этих изменениях. Таким образом, реплика А 1602 посылает любые текущие изменения, существующие в изменениях 1604 реплики А, соответствующих этим идентификаторам изменений (за исключением того случая, когда идентификатор изменения представляет устаревшее изменение, так что изменение не посылается). Реплика А 1602 может впоследствии послать сообщение к реплике В 1610, указывающее, что все изменения были посланы, таким образом, что реплика А 1602 и реплика В 1610 могут теперь обновить их векторы 1608 и 1616 знаний, соответственно, для включения недавно дублированных изменений. Как показано на фиг.23 в момент времени (5), вектор знаний реплики А, А5В3С5D10, равен вектору знаний реплики В, который включает в себя все изменения, сделанные репликой А, вплоть до перечисления пятого изменения, все изменения, сделанные репликой В, вплоть до перечисления третьего изменения, все изменения, сделанные репликой С, вплоть до перечисления пятого изменения, и все изменения, сделанные репликой D, вплоть до перечисления десятого изменения.

Со ссылкой на фиг.24А и 24В, показаны два способа обновления векторов знаний, следующего за полной репликацией, как та, что представлена на фиг.23. Конкретно, фиг.24А иллюстрирует способ обновления векторов знаний с использованием списка 1702 исключений, хранимого на реплике. Для создания списка 1702 исключений, когда изменения посылаются между репликами, изменения посылаются с идентификатором изменения, связанным с этим изменением. Когда изменение добавляется к реплике, идентификатор изменения добавляется как исключение к списку 1702 исключений. Исследуем теперь знания для реплики А на фиг.24А; эти знания включают в себя вектор 1608 знаний и список 1702 исключений, который включает в себя исключения С2, С3, С4 и С5. Исследование списка 1702 исключений в сочетании с вектором 1608 обнаруживает, что включая идентификаторы изменений из списка 1702 исключений, знания реплики А включают в себя все изменения вплоть до пятого изменения, сделанного репликой С. Таким образом, исключения могут быть удалены из знаний реплики А 1602 и вектора знаний, обновленного для включения элемента С5, как показано в обновленном векторе 1704 знаний. Подобный анализ может быть выполнен на знаниях 1614 реплики В 1610. Первоначальный вектор 1616 знаний, скомбинированный с исключениями А4, А5, D9 и D10 в списке 1703 исключений, дает возможность обновить вектор 1616 знаний в обновленный вектор 1706 знаний.

Заметно, что если была выполнена частичная репликация, например, если изменения, соответствующие идентификаторам А4 и D9 изменений, не были посланы в репликацию, такую как репликация, представленная на фиг.23, то знания 1614 реплики В 1610 нуждались бы в поддержании исключений А5 и D10 до последующей репликации с другой репликой, которая переносит изменения, представленные идентификаторами А4 и D9 изменений, к реплике В 1610.

Фиг.24В иллюстрирует другой способ обновления векторов 1608 и 1616 знаний для отражения репликации, показанной на фиг.23. В этом примере, векторы знаний обновляются с использованием поэлементного максимума для каждого из элементов в первоначальных векторах 1608 и 1616 знаний для формирования обновленного вектора 1708 знаний. Первый элемент каждого из векторов 1608 и 1616 соответствует набору идентификаторов изменений, помечающих изменения, сделанные в реплике А. Поскольку А5 является элементом поэлементного максимума двух векторов 1608 и 1616 знаний, обновленный вектор 1708 знаний включает в себя элемент А5. Подобным же образом, каждый из элементов В3, С5 и D10 вектора представляет собой элемент поэлементного максимума, соответствующий изменениям на конкретных репликах, которым соответствует каждый из элементов. Исследование каждого из обновленных векторов 1704, 1706 и 1708 знаний обнаруживает, что любым из способов получен тот же самый обновленный вектор знаний. Способ поэлементной максимизации обновления вектора знаний обычно используется, когда была выполнена полная репликация, тогда как способ списка исключений обновления вектора знаний может быть полезным, когда не определено, что произошла полная репликация (пользователь может отменить репликацию, устройство может сломаться и т.д.). А именно, способ списка исключений может нуждаться в использовании таким образом, что исключения могут продолжать содержать часть знаний конкретной реплики, когда полные знания реплики не могут быть представлены в простой векторной форме.

Со ссылкой на фиг.24С, пример обновления знаний показан для реплики, которая имеет информацию от неполной репликации. Фиг.24С включает в себя первоначальный вектор 1710 знаний, первоначальный список 1712 исключений, обновленный вектор 1714 знаний и обновленный список 1716 исключений. Относительно показанной реплики, после частичной репликации, реплика имеет все идентификаторы изменений, помеченные А1-А5, представленные элементом А5 вектора, и все идентификаторы изменений, помеченные А7-А10, представленные списком исключений, включающим в себя А7, А8, А9 и А10. Как показано на фиг.24С, в обновленной версии знаний, обновленный список 1716 исключений может быть сокращен для указания включения всех элементов от А7 до А10 как, например, посредством выражения (А7:А10), показанного на фиг.24С. Это выражение является просто вектором, подобным тем, которые обсуждались здесь ранее, за исключением того, что начальной точкой вектора является некоторая другая точка, чем первое перечисление изменений для реплики А. Таким образом, представление знаний реплики по отношению к А представлено векторным элементом А5 и вектором (А7:А10) исключения.

В случае знаний реплики относительно реплики В, вектор 1710 знаний может быть обновлен для включения непрерывных идентификаторов изменений, следующих за идентификаторами изменений, включенных в векторный элемент для реплики В. Векторный элемент В1 включает в себя только идентификатор В1 изменения. Поскольку идентификаторы В2, В3 и В4 изменений существуют в списке 1712 исключений, и они непрерывны с идентификатором В1 изменения, включенным в вектор 1710 знаний, векторный элемент для реплики В может быть обновлен в В4 в обновленном векторе 1714 знаний, который представляет включение элементов В1-В4. Поскольку идентификатор В5 изменения отсутствует в списке исключений, исключение В6 должно оставаться в списке 1716 исключений в обновленных знаниях.

Подобный анализ может быть выполнен относительно знаний реплики на фиг.24С, относительно изменений, сделанных репликой С. Первоначальный вектор 1710 знаний включает в себя С5. Первоначальный список исключений включает в себя С6, С7 и С8. Поскольку первоначальный элемент С5 вектора знаний включает в себя идентификаторы С1-С5 изменений, и С5 является непрерывным с идентификаторами изменений в первоначальном списке 1712 исключений, обновленный элемент вектора знаний для реплики С может быть обновлен в С8.

Одно возражение, которое может возникнуть в отношении размера векторов знаний, особенно, когда число реплик в сообществе синхронизации велико. В топологии, где вектор знаний включает в себя идентификатор изменения или другой векторный элемент для каждой реплики в пределах сообщества синхронизации, вектор знаний возрастает с каждой репликой, которая добавляется к сообществу синхронизации. Одной оптимизацией является распознавание того, что в некоторых сообществах синхронизации не каждая реплика нуждается в представлении в векторе знаний. Одной иллюстрацией такого случая является сообщество синхронизации, показанное на фиг.25, которое представляет собой серверную топологию «подключайся и говори». Фиг.25 показывает сервер 1802, подключенный к некоторому количеству клиентов, включающих в себя реплику А 1804, реплику В 1806, реплику С 1808 и реплику D 1810. В этом примере, все пути 1812-1818 репликации между клиентами проходят через сервер 1802, и таким образом, сервер 1802 может назначить идентификатор изменения, который включает в себя сервер 1802 как идентификатор реплики. Все изменения, сделанные в пределах индивидуальных клиентов 1804-1810, остаются в пределах соответствующего клиента, в котором было сделано это изменение, без назначения идентификатора изменения, до выполнения репликации. Таким образом, в этом примере, вектор знаний включает в себя единственный элемент, который содержит идентификатор реплики и идентификатор изменения сервера 1802. Иллюстративно, если изменение сделано в реплике А 1804 и дублировано сервером 1802 в первое время, то сервер 1802 назначает перечисление S1 изменения для этого изменения. В последующее время, изменение, сделанное в реплике В 1806, дублируется сервером 1802. Это изменение назначается перечислением изменений сервером S2. Заметно, что хотя в этом примере, сервер 1802 назначает все перечисления изменений, могут существовать и другие реализации, когда сервер 1802 назначает некоторые перечисления изменений, и другие реплики назначают другие перечисления изменений.

Реализации изобретения также применимы для оптимизации вектора знаний в других топологиях. Например, на фиг.18, реплика D 1114 только дублирует с репликой С 1110. Таким образом, изменения, сделанные посредством С и D, могут быть перечислены с использованием перечислений изменений, которые имеют единственный идентификатор реплики. В одном примере, если идентификатор реплики С выбран в качестве части перечисления изменений для всех изменений посредством либо реплики С1110, либо реплики D 1114, первое изменение в реплике С было бы помечено перечислением С1 изменений. Последующее изменение в реплике D 1114 помечено С2 и т.д. Когда одна реплика создает идентификатор изменения для изменений, сделанных на другой реплике, реплику, создающую этот идентификатор изменения, можно назвать суррогатным автором.

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

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

Если все реплики в пределах сообщества синхронизации или топологии разрешают конфликты одним и тем же образом, то обычно не требуется других правил или систем разрешения, так как все реплики в пределах системы будут перемещаться к дублированному разрешению любых конфликтов. Хотя реплики в пределах сообщества синхронизации могут быть не рассчитаны конкретно для разрешения конфликтов в точности одним и тем же способом, реплики в пределах сообщества синхронизации могут тем не менее разрешать конфликты в точности одним и тем же способом. Пример этого показан на фиг.26А. Фиг.26А показывает реплику D 1902. Реплика D 1902 принимает идентификатор изменения, соответствующий изменению в элементе I_x, где идентификатором изменения является А4. В последующем реплика D 1902 принимает идентификатор изменения для того же элемента I_x, где идентификатором изменения является В5. Реплика D 1902 имеет правила разрешения конфликтов для выбора того, какое из изменений для элемента I_x является предпочтительным изменением. В этом случае реплика D выбирает изменение для элемента I_x, помеченное идентификатором А4 изменения. Для указания того, что конфликт был разрешен репликой D 1902, и как этот конфликт был разрешен, новый идентификатор изменения назначается элементу I_x, который включает в себя как результаты разрешения конфликта, так и новый идентификатор изменения, назначенный конкретной репликой, которая выполнила это разрешение конфликта. Новый идентификатор изменения включает в себя следующее последовательное перечисление изменений для реплики, которая выполнила разрешение конфликта. В этом случае, новый идентификатор изменения помечается А4 (D7) для указания того, что изменение, помеченное А4, было выбрано в разрешении конфликта, и что этот конфликт был разрешен репликой D 1902. Как показано на фиг.26А, подобный процесс происходит, когда конфликт в изменениях детектируется репликой С 1904. Реплика С 1904 разрешает конфликт тем же способом, что и реплика D 1902. Таким образом, новый идентификатор изменения, помеченный А4 (С3), назначается изменению элемента I_x. В этом случае, конфликт между изменениями для элемента I_x, помеченный идентификаторами А4 и В5 изменений, будет в результате разрешен одним и тем же способом во всех репликах в пределах топологии.

Фиг.26В иллюстрирует пример, когда конфликты разрешаются различными способами различными репликами в пределах топологии. На фиг.26В, в момент времени (1) реплика D 1902 разрешает конфликт одним способом и назначает новый идентификатор изменения для элементов, который иллюстрируют разрешение конфликта, В5, и реплику, которая выполнила это изменение, (D7). В момент времени (2) реплика С 1904 разрешает тот же самый конфликт другим способом, показанным новым идентификатором изменения, назначенным репликой С 1904, А4 (С3). В момент времени (3), реплика D 1902 принимает разрешение репликой С конфликта. Реплика D 1902 в этой точке распознает, что этот конкретный конфликт был разрешен двумя различными способами. Некоторые реализации данного изобретения, следовательно, определяют, что определенное (детерминированное) разрешение должно быть сделано между конфликтующими изменениями для элемента I_x. Конкретное детерминированное разрешение, показанное на фиг.26В, вызывает изменение с наиболее низким значением идентификатора реплики, подлежащим выбору в качестве детерминированного результата. Таким образом, поскольку А является более низким значением идентификатора реплики, чем реплика В, детерминированным разрешением конфликта выбирается изменение, помеченное идентификатором А4 изменения. Реплика D 1902, таким образом, изменяет идентификатор изменения, связанный с изменением для элемента I, на А4 (D7). Отметим, что для того, чтобы избежать циклов репликации или других конфликтных проблем, перечисление изменений (т.е. D7), связанное с репликой, выполняющей изменение, является тем же самым в детерминированном результате 1906, что и в первоначальном разрешении конфликта 1908.

Хотя объект изобретения был описан языком, специфическим для структурных особенностей и/или методологических действий, следует понимать, что объект изобретения, заявленный в прилагаемой формуле изобретения, необязательно ограничен конкретными особенностями или действиями, описанными выше. Точнее, специфические особенности и действия, описанные выше, раскрыты как примерные формы реализации формулы изобретения. Желательно, чтобы все эквиваленты, изменения и модификации, которые приходят на ум в пределах сущности этих реализаций, описанных здесь и/или посредством следующей формулы изобретения, были защищены.

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

Изобретение относится к средствам синхронизации данных между различными типами устройств и/или служб, а также различными правами участников при обмене данными. Технический результат заключается в обеспечении адаптирования процесса обмена информацией в зависимости от прав доступа участников. Машина синхронизации определяет, является ли устройство или служба полным, частичным или простым участником. Устройство или служба является простым участником, если оно имеет хранилище данных для синхронизированных данных и не имеет хранилища знаний. Устройство или служба является частичным участником, если оно имеет хранилище данных для синхронизированных данных и хранилище знаний, но не понимает этих знаний. Устройство или служба является типом полного участника, если оно имеет хранилище данных для синхронизированных данных и хранилище знаний и понимает эти знания. Машина синхронизации выполняет операцию синхронизации с устройством или службой с использованием набора логики, который подходит для этого типа устройства или службы. 5 н. и 15 з.п. ф-лы, 26 ил.

1. Способ для синхронизации данных, содержащий этапы, на которых:
обеспечивают частичного участника, причем этот частичный участник имеет хранилище данных и хранилище знаний, причем хранилище данных выполнено с возможностью хранения набора данных, извлеченных в процессе синхронизации первым полным участником, причем хранилище знаний действует для хранения набора знаний о данных в хранилище данных, причем набор знаний представляет собой изменения для данных, о которых осведомлен первый полный участник (282), причем частичный участник не понимает набор знаний (284), и причем частичный участник отвечает за отслеживание того, какие изменения частичный участник производит с множеством данных в хранилище данных (290);
принимают запрос от пользователя частичного участника для изменения конкретной записи в наборе данных в хранилище данных (286); и
обновляют конкретную запись в хранилище данных после принятия запроса от пользователя (288), причем обновление включает в себя хранение информации, идентифицирующей источник изменения как частичного участника (290).

2. Способ по п.1, в котором частичный участник выполнен с возможностью синхронизации со вторым полным участником (66).

3. Способ по п.1, в котором частичный участник синхронизируется с первым полным участником через обработчик на первом полном участнике (66).

4. Способ по п.1, в котором первым полным участником является персональный компьютер (242).

5. Способ по п.1, в котором первым полным участником является мобильное устройство (242).

6. Способ по п.1, в котором частичным участником является мобильное устройство (282).

7. Способ по п.1, в котором частичным участником является Web-служба (282).

8. Способ по п.1, в котором информация, идентифицирующая источник изменения, является версией (304).

9. Способ по п.8, в котором первая часть версии включает в себя идентификатор, который уникально идентифицирует частичного участника, и в котором вторая часть версии включает в себя число, которое указывает версию записи (304).

10. Способ по п.1, в котором информацией, идентифицирующей источник изменения, является уникальный идентификатор для записи и идентификатор даты и времени для указания того, когда эта запись изменилась (314).

11. Способ по п.1, дополнительно содержащий этап, на котором:
принимают обновленный набор знаний от первого полного участника после того, как первый полный участник обновит набор знаний после процесса синхронизации (296).

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

13. Машиночитаемый носитель, имеющий инструкции, исполняемые компьютером, для того, чтобы вызвать выполнение компьютером этапов, на которых:
принимают запрос от участника для выполнения операции синхронизации с использованием машины синхронизации (244);
определяют тип для участника, причем этот тип выбирается из группы, состоящей из типа полного участника, типа частичного участника и типа простого участника (246);
причем определено, что участник является типом простого участника, если он имеет хранилище данных простого участника и не имеет знаний (248);
причем определено, что участник является типом частичного участника, если он имеет хранилище данных частичного участника и хранимые, но не понимаемые знания (250);
причем определено, что участник является типом полного участника, если он имеет хранилище данных полного участника и хранимые и понимаемые знания (252); и
причем машина синхронизации выполняет операцию синхронизации с участником с использованием набора логики, который является подходящим для типа участника (256).

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

15. Машиночитаемый носитель по п.13, если определено, что тип для участника является типом частичного участника, то машина синхронизации принимает хранимые-но-не-понимаемые знания от участника (258) и обновляет хранимые-но-не-понимаемые знания на участнике, если происходят исключения (260).

16. Машиночитаемый носитель по п.15, в котором машина синхронизации обновляет хранимые-но-не-понимаемые знания на участнике посредством модификации локальной копии и последующей передачи этой локальной копии к участнику (262).

17. Машиночитаемый носитель по п.13, в котором, если определено, что тип для участника является типом частичного участника, то участник выполняется с возможностью участия в операции двусторонней синхронизации со многими ведущими устройствами из-за хранимых-но-не-понимаемых знаний на участнике (264).

18. Машиночитаемый носитель по п.13, в котором машина синхронизации принимает запрос от участника для регистрации обработчика для операции синхронизации (244).

19. Способ для синхронизации данных, содержащий этапы, на которых:
обеспечивают простого участника, причем простой участник имеет хранилище данных и не имеет хранилища знаний, причем хранилище данных выполняется с возможностью хранения набора данных, обеспеченных в процессе синхронизации с полным участником, и причем простой участник не отвечает за отслеживание того, какие изменения простой участник производит для набора данных в хранилище данных (424);
принимают запрос от пользователя простого участника для изменения конкретной записи в наборе данных в хранилище данных (428); и обновляют конкретную запись в хранилище данных по принятии запроса от пользователя (430).

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