Посоветуйте алгоритм репликации

← →
Суслик © (2005-06-10 15:45) [0]

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

Посоветуйте что-нибудь.

← →
TUser © (2005-06-10 15:48) [1]

Рекурсией?

procedure Assign (Source);
begin
{копируем детей}

for each child do
Child.Assign (Source.CorrespondingChild)
end;

← →
kaif © (2005-06-10 15:51) [2]

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

← →
Суслик © (2005-06-10 15:52) [3]

Но это же просто копирование!
Нужно именно репликации.

Например:

на компе 1 и 2 одинаковые структуры

<ParentObject> <ChildObject1> <ChildObject2>

Потом на компе 1 меняется ChildObject1, а на компе 2 - ChildObject2.
Я допускаю, что все поля (не подиченные объекты) каждого объекта пеплицируются полностью.

В итогде после репликации на каждом из компов должна быть структура

<ParentObject> <ModifiedChildObject1> <ModifiedChildObject2>

← →
DiamondShark © (2005-06-10 15:53) [4]

> Требования к быстродействию минимальные.

Тогда самый тупой -- копирование.

← →
Суслик © (2005-06-10 15:53) [5]

> [2] kaif © (10.06.05 15:51)

Ссылок межжду ветками НЕТ!.

Т.е. только отношение вледения - простое дерево. При этом каждая ветка дерева может независимо меняться.

← →
jack128 © (2005-06-10 15:53) [6]

Суслик © (10.06.05 15:45)
Требования к быстродействию минимальные.
function SyncNodes(Node1, Node2: ТNode); begin if not Node1.IsEqual(Node2) then Node1.Assign(Node2); i := Node1.ChildCount; while i < Node2.ChildCount do begin Node1.AddChild; inc(i); end; while Node1.ChildCount > Node2.ChildCount do Node1.DeleteChild(Node1.ChildCount - 1); for i := 0 to Node1.ChildCount - 1 do SyncNodes(Node1.Children[i], Node2.Children[i]); end;

← →
Суслик © (2005-06-10 15:55) [7]

> [4] DiamondShark © (10.06.05 15:53)

А что копировать?
Нужне скорее merge...
Но нужно отлеживать, чему делать merge. При этом, конечно, по сети гонять всю структуру не хочется, а только то, что нужно для репликации.

У меня есть ощущения, что должны быть стандартные алгоритмы на это. Я порылся в литературе (Кнут, Алгоритмы, Бакнел) - вроде ничего нет. Может в сети что?

← →
BiN © (2005-06-10 15:58) [8]

а если на разных компах меняется один и тот же узел дерева, что будешь делать?
Ты определись, какая машина имеет приоритет.

← →
kaif © (2005-06-10 15:58) [9]

Все равно не понимаю. Если никаких ссылок нет, то тогда - просто копирование. DROP TABLE, CREATE TABLE, FILL TABLE :-)
Кстати, я по секрету где-то читал, что любая система репликаций рано или поздно доходит до такого заср..го состояния, что приходится делать именно то, что я сказал - тупое копирование.

← →
BiN © (2005-06-10 16:03) [10]

kaif © (10.06.05 15:58) [9]
Кстати, я по секрету где-то читал, что любая система репликаций рано или поздно доходит до такого заср..го состояния...

Прямо так и было написано?
-)

← →
Суслик © (2005-06-10 16:08) [11]

> [6] jack128 © (10.06.05 15:53)

это же копирование, а мне нужно слияние параллельно изменяемых данных.

Поставлю вопрос более корректно на основе примера, того, что мне нужно.

Итак:

1. Есть деловая компьютерная игра - пошаговая стратегия. Сразу скажу (дабы не вызвать упреков в неэффективности) - данных мало. Максимум - 1000 объектов ~ 2 мб.

2. Есть собственно ручно написанный многопоточный сервер на основе TCP/IP. Сервер сам по себе умеет все (коннект, дисконект и все такое), кроме того, для чего он создавался - обслуживание игрового процесса.

3. По ряду причин НЕ была выбрана "чистая" архитектура "клиент-сервер", т.е. когда ТОЛЬКО сервер хранит данные, а клиенты спрашивают нужную порцию. Была выбрана архитектура - клиент и сервер хранят полную информацию, которая переодически реплицируется. Такое решение было принято по той причине, что помимо сетевой игры, нужна еще и дискетная (да, у нас бывают бедные ВУЗы). А там не набегаешься на каждый запрос с дискетой.

4. Структура данных имеет вид (приведу схематично в виде XML, хотя это просто объекты в памяти)

<game> <firm number = "1"> <month number = "1" ... и еще куча атрибутов> ... кое какие подиченные объекты </month> <month number = "2" ... и еще куча атрибутов> ... кое какие подиченные объекты </month> </firm> <firm number = "2"> тоже самое, что и для фирмы 1 </firm> и так далее - фирм может быть до 10 </game>

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

Что я хочу
Я хочу написать обобщенный алгоритм репликации объектной структуры.

← →
Суслик © (2005-06-10 16:12) [12]

> [8] BiN © (10.06.05 15:58)

> а если на разных компах меняется один и тот же узел дерева,
> что будешь делать?
> Ты определись, какая машина имеет приоритет.

Буду сваливаться с ошибкой!
Такого по логике программы быть не должно.

Конечно, валиться я не буду - на стадии отладки буду просто в лог данные писать - мол было нарушении логики - и перезаписывать новые данные.

← →
Суслик © (2005-06-10 16:18) [13]

← →
DiamondShark © (2005-06-10 16:19) [14]

Так как конфликты запрещены, то получатся именно копирование.
Клиент отправляет на сервер свою часть, а получает с сервера объединённую.

← →
BiN © (2005-06-10 16:37) [15]

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

← →
Суслик © (2005-06-10 16:41) [16]

> [14] DiamondShark © (10.06.05 16:19)

Я согласен, что копирование. Но копирование объектов, но не списков объектов.
Например,
1) на сервере и на клиенте есть одинаковая структура данных (список объектов с одним атрибутом, в качестве идентификатора в примере выбран guid)

<obj id = "guid 1" property="a">
<obj id = "guid 2" property="a">
<obj id = "guid 3" property="a">

2) на сервере происходят изменения, в результате которых образуется такая структура данных:

<obj id = "guid 1" property="a"> <obj id = "guid 2" property="b"> <- здесь поменялся атрибут <obj id = "guid 3" property="a"> <obj id = "guid 4" property="a"> <- новый объект
3) на клиенте происходят изменения, в результате которых образуется такая структура данных:

<obj id = "guid 1" property="c"> <- здесь поменялся атрибут <obj id = "guid 2" property="a"> <obj id = "guid 3" property="a"> <obj id = "guid 5" property="a"> <- новый объект
4) в итоге после репликации на сервере и на клиенте должна быть такая структура:

<obj id = "guid 1" property="c"> <- здесь поменялся атрибут на клиенте <obj id = "guid 2" property="b"> <- здесь поменялся атрибут на сервере <obj id = "guid 3" property="a"> <obj id = "guid 4" property="a"> <- новый объект, созданный на сервере <obj id = "guid 5" property="a"> <- новый объект, созданный на клиенте
5) Замечу, что вопросы удаления я не рассматриваю т.к. удаления объектов НЕТ.

6) Т.е. стоит задача - отлеживать измененные объекты и их отправлять адресату, который может расположить их в своей структуре данных.

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

← →
Суслик © (2005-06-10 16:46) [17]

> [15] BiN © (10.06.05 16:37)

1 тогда по сети нужно будет гонять эти идентификаторы для каждого объекта.
2 Хотелось бы так:
а) Клиент посылает серверу запрос на репликацию Сс сервера НА клиента. При этом клиент сообщает серверу - я мол последний раз обновлялся тогда-то и тогда-то (можно время передавать, можно счетчик, что лучше)
б) Сервер в ответ данные, которые я СОГЛАСНО ОБЩЕМУ алгоритму располагаю в своей модели. При этом есно изменяя счетчик.

По большому счету, я почти изложил алгоритм. Если ничего не найду почитать, то так и буду делать. Но хотелось бы что-то найти. Вот по сжатию данных полно литературы, по бинарным деревьям тоже полно. А почему по репликации нет? Возможно, что тут нет такой общей теории, чтобы излагать в книгах. Я в этом не силен :(

← →
Jeer © (2005-06-10 16:50) [18]

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

← →
DiamondShark © (2005-06-10 16:51) [19]

> Суслик © (10.06.05 16:41) [16]

Тогда наводящий вопрос: а ситуация вроде

2) на сервере происходят изменения, в результате которых образуется такая структура данных:

<obj id = "guid 2" property="b"> <- здесь поменялся атрибут

3) на клиенте происходят изменения, в результате которых образуется такая структура данных:

<obj id = "guid 2" property="b"> <- здесь поменялся атрибут

Возможны?

← →
DiamondShark © (2005-06-10 16:54) [20]

> Jeer © (10.06.05 16:50) [18]

Вот о том же подумал.

Если конфликтов нет, то это ничем не отличается от обыччного синхронного клиент-серверного взаимодействия.

← →
Суслик © (2005-06-10 16:59) [21]

> [19] DiamondShark © (10.06.05 16:51)

> Возможны?

нет.
Т.е. один объект не может быть изменен там и там.
НО! В одном списке объектов могут быть объекты измененные и там и там, т.е. один объект изменен там, а другой тут, и нужно их слить а там и тут.:)

← →
DiamondShark © (2005-06-10 17:07) [22]

> Суслик © (10.06.05 16:59) [21]

Посылаем на сервер изменённый у себя объект.
Получаем с сервера набор всех объектов.
Перезаписываем у себя весь набор.

Это если объём пересылаемых данных не волнует.

> НО! В одном списке объектов могут быть объекты измененные
> и там и там, т.е. один объект изменен там, а другой тут,
> и нужно их слить а там и тут.:)

Ты прямо про Cached updates рассказываешь. Или про модель briefcase

А почему бы не воспользоваться стандартным подходом - абстрагируйся от того, что это дерево. Пусть это таблица. В ней строки могут добавляться, удаляться, изменяться. Храни лог-таблицу всех изменений и отсылай ее на сервер или другому клиенту. Пусть там эти вставки, удаления и изменения обрабатываются так же, как они исторически происходили.
Если же тебе нужно именно копирование (внахлест), то нуджно подумать об удалении. Как "удалять внахлест"? Надо помнить, что нечто было удалено и "применять это удаления там". То есть мы приходим к стандартной логике репликаций - применять то, что сделал "здесь", "там". Но это всегда источник глюков :) Один создает, другой - удаляет. Этот опять создает. Конфликт, однако...

Расскажу, как я делаю репликацию. Это, правда, для СУБД.
Есть таблица изменений.
В ней поля
код таблицы/код строки (первичный ключ)/тип изменения/отсылка(да нет)/принятие(неизв принято отброшено)/причина непринятия/датавремя/автор изменения/история ихменений
в таблице "таблиц" поля
код/наименование в базе/описание/первичный ключ

Сколько ни будет изменений на конкретном узле брать мы будем только на момент отправки

Данные выбираем и запихаем в xml, которое парсим при получении. Если изменение insert/update, то данные пихаем в InsertUpdate процедуру, если delete то в delete запрос. Так как есть автор изменений, то можно делать черные списки.
Вот так, вкратце.

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

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

> Ты прямо про Cached updates рассказываешь. Или про модель
> briefcase

Даже проще. В Cached updates, всё-таки, возможны конфликты.

> [23] Игорь Шевченко © (10.06.05 17:15)
> Ты прямо про Cached updates рассказываешь. Или про модель
> briefcase

Намек понял (или не понял:)), но у меня молуля briefcase нет :)
Вообще, если это общая теория, то дай, пожалуйста, более конкретную ссылку :)

> [22] DiamondShark © (10.06.05 17:07)

Нет, всех объектов не пойдет. Вернее пойдет, но это на крайний случай. Хотелось бы получать именно мин. репликационную информацию.

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

Т.е. требования к быстродействию внутри одного компьютера минимальны, по сети же хотелось бы передавать как можно меньше, т.к. есть перспектива доработки продукта до Internet

> [24] kaif © (10.06.05 17:18)

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

> Вообще, если это общая теория, то дай, пожалуйста, более
> конкретную ссылку

На rsdn статья была. Чуть не Гоблина (Михаила Голованова). Поищи по ключевому слову.

thaks, уже нашел

thanks, уже нашел

Посоветуйте алгоритм репликации Найти похожие ветки