Алгоритм синхронизации порядка записей

Question

Это клиент-серверная прикладная система.

Приложение клиентской части может выходить в автономный режим и иногда синхронизироваться с сервером. (как GMail в автономном режиме)

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

Алгоритм добавления, редактирования и удаления записей тривиален. Сервер может создавать уникальный идентификатор для каждой новой записи, и клиенты используют этот идентификатор для обновления и удаления.

Новое требование - порядок записей.

Есть два клиентских приложения - x, y. И они хранят записи - A, B, C и D. Эти массивы записей представлены как D-C-B-A, поэтому свойство порядка A равно 4, B равно 3, C равно 2 и D равно 1.

• x: D-C-B-A: A (4), B (3), C (2), D (1)
• y: D-C-B-A: A (4), B (3), C (2), D (1)

Клиент y создает новую запись E между D и C

• x: D-C-B-A: A (4), B (3), C (2), D (1)
• y: D-E-C-B-A: A (5), B (4), C (3), D (1), E (2)

После синхронизации клиента с сервером.

• x: D-E-C-B-A: A (5), B (4), C (3), D (1), E (2)
• y: D-E-C-B-A: A (5), B (4), C (3), D (1), E (2)

Как мне синхронизировать эти данные заказа?

---

* Дополнительный тест *

Cient x удаляет D и C, но клиент y создает новую запись E между D и C.

• x: B-A: A (2), B (1)
• y: D-E-C-B-A: A (5), B (4), C (3), D (1), E (2)

После синхронизации.

• x: C-B-A: A (5), B (4), C (3), D (1), E (2)
• y: C-B-A: A (5), B (4), C (3), D (1), E (2)

---

Answer 1

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

Если вы этого не сделаете, у вас будут большие проблемы с согласованностью (согласованностью) хранимых данных. Например, вы сохранили D-C-B-A, а клиенты x и y синхронизированы.

• клиент x удаляет C и A -> D - B
• клиент z синхронизируется, он получает D - B и добавляет F между D и B -> D - F - B
• между тем клиент y добавляет E между C и B -> D - C - E - B - A

Теперь, если все клиенты будут синхронизироваться, вы не можете сказать, где F будет помещен в последовательность данных: D - F - E - B или D - E - F - B.

Answer 2

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

Answer 3

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