[Архитектура] Отслеживание обновлений дерева
От: Real 3L0 Россия http://prikhodko.blogspot.com
Дата: 05.09.19 06:54
Оценка:
Приветствую.
Дано:
Есть дерево: ствол, на котором множество веток. Но ствол нам не интересен.
Каждая ветка состоит из связанных объектов, которые могут изменятся как сами, так и своё положение в ветке.
Пользователь может иметь или не иметь право доступа к ветке. Право доступа определяется сразу ко всей ветке.
Надо:
Требуется выслать пользователю (для его локальной базы) все обновления, произошедшие с его последнего подключения к дереву.

Грубо говоря, это все представлено в следующих таблицах:
* Объекты: PK, какое-то значение объекта
* Дерево: PK, FK дерева, FK объекта
* Право доступа: PK, FK пользователя, FK дерева

Структура одинакова как на сервере, так и локально у пользователя.

Изменения отслеживать понятно как:
* для изменений объектов добавляем поле timestamp в таблице Объекты, подключившийся пользователь определяет в своей локальной базе максимальное значение timestamp, и получает с сервера все объекты, что новее.
* для изменений положения объектов в дереве также добавляем поле timestamp, но в таблицу Дерево, изменения получаем аналогично.

Проблема у меня со следующей ситуацией: у пользователя появились прав доступа на новую для него ветку, у которой есть timestamp'ы старее, чем уже существуют в локальной базе пользователя. Тогда вышеописанные алгоритмы отслеживания изменений не работают.
Все придуманные мной алгоритмы мне не нравятся.
А как это реализуют опытные товарищи?
Вселенная бесконечна как вширь, так и вглубь.
Re: [Архитектура] Отслеживание обновлений дерева
От: BlackEric http://black-eric.lj.ru
Дата: 05.09.19 14:07
Оценка:
Здравствуйте, Real 3L0, Вы писали:

R3>Проблема у меня со следующей ситуацией: у пользователя появились прав доступа на новую для него ветку, у которой есть timestamp'ы старее, чем уже существуют в локальной базе пользователя. Тогда вышеописанные алгоритмы отслеживания изменений не работают.

R3>Все придуманные мной алгоритмы мне не нравятся.
R3>А как это реализуют опытные товарищи?

Вам же нужно всю ветку новую выкачивать при появлении прав? Как вариант можете храниьт у клиента минимальный timestamp тоже. И проверять не стал ли ему доступен меньше минимального.
https://github.com/BlackEric001
Re[2]: [Архитектура] Отслеживание обновлений дерева
От: Real 3L0 Россия http://prikhodko.blogspot.com
Дата: 05.09.19 14:20
Оценка:
Здравствуйте, BlackEric, Вы писали:

BE>Вам же нужно всю ветку новую выкачивать при появлении прав?


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

BE> Как вариант можете храниьт у клиента минимальный timestamp тоже. И проверять не стал ли ему доступен меньше минимального.


Не понял. Для всех объектов в локальной базе можно получить минимальный timestamp и он будет меньше, чем timestamp ветки, которая внезапно стала доступной.
Вселенная бесконечна как вширь, так и вглубь.
Отредактировано 05.09.2019 14:21 Real 3L0 . Предыдущая версия .
Re: [Архитектура] Отслеживание обновлений дерева
От: VladCore  
Дата: 05.09.19 14:36
Оценка:
Здравствуйте, Real 3L0, Вы писали:

R3>Приветствую.

R3>Дано:
R3>Есть дерево: ствол, на котором множество веток. Но ствол нам не интересен.
R3>Каждая ветка состоит из связанных объектов, которые могут изменятся как сами, так и своё положение в ветке.
R3>Пользователь может иметь или не иметь право доступа к ветке. Право доступа определяется сразу ко всей ветке.
R3>Надо:
R3>Требуется выслать пользователю (для его локальной базы) все обновления, произошедшие с его последнего подключения к дереву.

На другой базе храниш последний таймстамп (инкрементальный счетчик, не дату)
В любой момент просищ все изменения у которых таймстамп больше заданного.
Так работает log shipping в базах данных
Все параллелится, "пользователей" может быть сколько угодно и каждый "синхронизируется" когда ЕМУ нужно.

R3>Грубо говоря, это все представлено в следующих таблицах:

R3>* Объекты: PK, какое-то значение объекта
R3>* Дерево: PK, FK дерева, FK объекта
R3>* Право доступа: PK, FK пользователя, FK дерева

R3>Структура одинакова как на сервере, так и локально у пользователя.


R3>Изменения отслеживать понятно как:

R3>* для изменений объектов добавляем поле timestamp в таблице Объекты, подключившийся пользователь определяет в своей локальной базе максимальное значение timestamp, и получает с сервера все объекты, что новее.
R3>* для изменений положения объектов в дереве также добавляем поле timestamp, но в таблицу Дерево, изменения получаем аналогично.

R3>Проблема у меня со следующей ситуацией: у пользователя появились прав доступа на новую для него ветку, у которой есть timestamp'ы старее, чем уже существуют в локальной базе пользователя. Тогда вышеописанные алгоритмы отслеживания изменений не работают.

R3>Все придуманные мной алгоритмы мне не нравятся.
R3>А как это реализуют опытные товарищи?

Как рабоает Log Shipping чем не подходит?
В трех таблицах храниш колонку timestamp. Для каждой из трех таблиц хранищ одну таблицу с ID удаленных строчек, если конечно логика там удаляет строчки в БД.

Это универсальное решение. Просто не думая заводи колонку timestamp и таблицу удаленных айдишников для всех таблиц которые надо "шарить" в другие "копии" базы.

И я так делал.

Можно даже отключать констрейнты при применении изменений и insert & update & delete выполнять одним merge стейтментом, если на MS SQL. Все очень быстро работает. Тогда порядок синхронизации таблиц вообще не важен. Но это так из опыта. Отвлекся я.
Отредактировано 05.09.2019 14:43 VladCore . Предыдущая версия . Еще …
Отредактировано 05.09.2019 14:38 VladCore . Предыдущая версия .
Re: [Архитектура] Отслеживание обновлений дерева
От: vsb Казахстан  
Дата: 05.09.19 14:42
Оценка:
Обновить таймстэмп у ветки.
Re[2]: [Архитектура] Отслеживание обновлений дерева
От: Real 3L0 Россия http://prikhodko.blogspot.com
Дата: 05.09.19 15:25
Оценка:
Здравствуйте, vsb, Вы писали:

vsb>Обновить таймстэмп у ветки.


Не понял, ну обновлю я это значение и что? При выборке максимального таймстамп из локальной базы, он будет больше, чем у объектов из ветки с обновлённым таймстампом.
Вселенная бесконечна как вширь, так и вглубь.
Re[2]: [Архитектура] Отслеживание обновлений дерева
От: Real 3L0 Россия http://prikhodko.blogspot.com
Дата: 05.09.19 15:36
Оценка:
Здравствуйте, VladCore, Вы писали:

VC>На другой базе храниш последний таймстамп (инкрементальный счетчик, не дату)


Ага, так и делаю.

VC>В любой момент просищ все изменения у которых таймстамп больше заданного.


Я так и написал.

VC>Как рабоает Log Shipping чем не подходит?


Поверхносто почитал.
У меня разные БД: MS и SQLite.
Мне не нужна полная синхронизация, а только тех вещей, который относятся к пользователю.

VC>В трех таблицах храниш колонку timestamp. Для каждой из трех таблиц хранищ одну таблицу с ID удаленных строчек, если конечно логика там удаляет строчки в БД.

VC>Это универсальное решение. Просто не думая заводи колонку timestamp и таблицу удаленных айдишников для всех таблиц которые надо "шарить" в другие "копии" базы.

Например, клиенту добавили права. У него обновился timestamp в таблице Право доступа. Как мне это поможет вычитать нужные записи из двух других таблиц?
Вселенная бесконечна как вширь, так и вглубь.
Отредактировано 05.09.2019 15:41 Real 3L0 . Предыдущая версия .
Re[3]: [Архитектура] Отслеживание обновлений дерева
От: vsb Казахстан  
Дата: 05.09.19 17:33
Оценка:
Здравствуйте, Real 3L0, Вы писали:

R3>Не понял, ну обновлю я это значение и что? При выборке максимального таймстамп из локальной базы, он будет больше, чем у объектов из ветки с обновлённым таймстампом.


Почему? Ты в 15:20 синхронизировался. В 15:30 тебе дали доступ на ветку и обновили у этой ветки таймстэмп. В 15:40 ты полез обновляться, спрашиваешь, что нового произошло с 15:20, тебе ветку выслали.

Обновить это я в смысле присвоить текущее время в центральной базе.
Отредактировано 05.09.2019 17:34 vsb . Предыдущая версия . Еще …
Отредактировано 05.09.2019 17:34 vsb . Предыдущая версия .
Re[4]: [Архитектура] Отслеживание обновлений дерева
От: Real 3L0 Россия http://prikhodko.blogspot.com
Дата: 05.09.19 18:58
Оценка:
Здравствуйте, vsb, Вы писали:

vsb>Почему? Ты в 15:20 синхронизировался. В 15:30 тебе дали доступ на ветку и обновили у этой ветки таймстэмп. В 15:40 ты полез обновляться, спрашиваешь, что нового произошло с 15:20, тебе ветку выслали.


Что значит "обновили у этой ветки таймстэмп"? Завести ещё один таймстэмп, но для всей ветки? У меня сейчас таймстэмп для каждого элемента ветки: для объекта и местоположения.
Ок, допустим.
Создам таймстэмп для всей ветки и обновлять его буду только при изменении доступа. В 15:40 я полез обновляться, мне дали таймстэмп этой ветки. Я получил и полез обновлять именно эту ветку. Обновил. Так получилось, что таймстэмп одного объекта в этой ветке самый новый: 16:00. Я получаю из локальной базы максимальный таймстэмп всех объектов — 16:00. А пока я выкачивал ветку, доступ к которой мне дали, кто-то обновил объект в другой ветке, доступ к которой я имел: 15:50. Я лезу обновляться, нет ли чего новее 16:00 и теряю объект 15:50.

Ок, допустим второй вариант.
Создам таймстэмп для всей ветки и обновлять его буду не только при изменении доступа, но и любого объекта. Да, это будет работать. (Я этот вариант делал. Он мне чем-то сейчас не нравится.) Но если ветка будет часто меняемой, то постоянно будем обновлять таймстэмп для всей ветки. Не будет ли тут дедлоков?
Вселенная бесконечна как вширь, так и вглубь.
Re: [Архитектура] Отслеживание обновлений дерева
От: Sinclair Россия https://github.com/evilguest/
Дата: 06.09.19 06:14
Оценка:
Здравствуйте, Real 3L0, Вы писали:
R3>А как это реализуют опытные товарищи?
Ну, простейшая реализация — это в момент выдачи прав на ветку вычислить минимальный таймстамп объекта в ней (самый старый из вновь доступных объектов), и метку синхронизации клиента сдвинуть назад на этот момент.
Тогда при следующей синхронизации он выкачает всю ветку, плюс повторно выкачает все объекты, которые у него уже есть.

Более сложная реализация будет построена на вычислении "эффективного таймстампа" для каждого объекта.
Не очень понял, какая именно будет структура таблиц и где там деревья.
Для более простого случая с "группами" имеем следующее:
create table Groups (
  id int identity primary key,
  name varchar(max)
)
create table Objects(
  id int identity primary key,
  last_change timestamp not null,
  payload varchar(max),
  group_id int not null foreign key references Groups(id)
)

create table Users (
  id int identity primary key,
  name varchar(max)
)

create table AccessRights
(
  id int identity primary key,
  user_id int not null foreign key references Users(Id),
  group_id int not null foreign key references Groups(Id),
  last_change timestamp not null
)


теперь запрос "новых" объектов для пользователя выглядит так:
select * from Objects where last_change > @last_seen_timestamp
  and group_id in (select group_id from AccessRights where user_id = @user_id)

А список объектов, к которым он получил доступ со времени последней синхронизации — вот так:
select * from Objects where group_id in (select group_id from AccessRights where user_id = @user_id and last_change > @last_seen_timestamp)

Объединяем оба списка:
select Objects.* from Objects inner join AccessRights on Objects.group_id = AccessRights.group_id and user_id = @user_id
where object.last_change > @last_seen_timestamp or AccessRights.last_change > @last_seen_timestamp


В реальной жизни надо будет пристально поработать с планами запросов; но перед этим неплохо бы продумать вопросы синхронизации удаления объектов и отбора прав. Ну, и скорректировать в соответствии с реальной структурой данных — дерево там, всё такое.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[2]: [Архитектура] Отслеживание обновлений дерева
От: Real 3L0 Россия http://prikhodko.blogspot.com
Дата: 06.09.19 07:11
Оценка:
Здравствуйте, Sinclair, Вы писали:

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


Ок. Это получается, что клиенту надо отдельно хранить таймстамп, а не вычислять его.

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


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

S>Более сложная реализация будет построена на вычислении "эффективного таймстампа" для каждого объекта.

S>Не очень понял, какая именно будет структура таблиц и где там деревья.
S>Для более простого случая с "группами" имеем следующее:
S>
S>create table Groups (
S>  id int identity primary key,
S>  name varchar(max)
S>)
S>create table Objects(
S>  id int identity primary key,
S>  last_change timestamp not null,
S>  payload varchar(max),
S>  group_id int not null foreign key references Groups(id)
S>)

S>create table Users (
S>  id int identity primary key,
S>  name varchar(max)
S>)

S>create table AccessRights
S>(
S>  id int identity primary key,
S>  user_id int not null foreign key references Users(Id),
S>  group_id int not null foreign key references Groups(Id),
S>  last_change timestamp not null
S>)
S>


S>теперь запрос "новых" объектов для пользователя выглядит так:

S>
S>select * from Objects where last_change > @last_seen_timestamp
S>  and group_id in (select group_id from AccessRights where user_id = @user_id)
S>


+1.
Только тут ещё сортировка нужна, но это мелочи.

S>А список объектов, к которым он получил доступ со времени последней синхронизации — вот так:

S>
S>select * from Objects where group_id in (select group_id from AccessRights where user_id = @user_id and last_change > @last_seen_timestamp)
S>


В этом запросе @last_seen_timestamp = @last_seen_timestamp из предыдущего запроса?
Хотя не важно.
Тут проблема в том, что не всегда можно выкачать все объекты за один запрос. Нужно вводить дополнительные @last_seen_timestamp для каждой ветки, к которой получили доступ.

S>... неплохо бы продумать вопросы синхронизации удаления объектов и отбора прав. Ну, и скорректировать в соответствии с реальной структурой данных — дерево там, всё такое.


Это я реализовал через галочку IsDeleted. Тогда удаление объекта — это просто особое изменение объекта и вся логика ложится на те же рельсы синхронизации. Удалили объект, поставили признак, обновили timestamp, клиенту отправили "заголовочную" строку объекта с установленным признаком, но без бизнес-данных, клиент у себя поставил галочку и удалил бизнес-данные.
Вселенная бесконечна как вширь, так и вглубь.
Отредактировано 06.09.2019 7:12 Real 3L0 . Предыдущая версия .
Re[3]: [Архитектура] Отслеживание обновлений дерева
От: Sinclair Россия https://github.com/evilguest/
Дата: 06.09.19 08:01
Оценка: 4 (1)
Здравствуйте, Real 3L0, Вы писали:

R3>Это я реализовал через галочку IsDeleted. Тогда удаление объекта — это просто особое изменение объекта и вся логика ложится на те же рельсы синхронизации. Удалили объект, поставили признак, обновили timestamp, клиенту отправили "заголовочную" строку объекта с установленным признаком, но без бизнес-данных, клиент у себя поставил галочку и удалил бизнес-данные.

Для прав доступа придётся делать примерно так же.
Для того, чтобы корректно сделать частичное выкачивание, надо делать двойную сортировку — по времени изменения и по ID объекта.
И маркер репликации — это пара (timestamp, id).
Получаем
select top (@batch_size) * from (select Objects.id, Objects.payload, Objects.deleteFlag, AccessRights.has_access, max(Objects.last_change, AccessRights.last_change) as last_change from Objects inner join AccessRights on Objects.group_id = AccessRights.group_id and user_id = @user_id) Replication 
where last_change > @last_seen_change or (last_change = @last_seen_change and id > @last_seen_id)
order by last_change, id

Строки с AccessRights.has_accss = False надо обрабатывать так же, как с Objects.deleteFlag = True.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[3]: [Архитектура] Отслеживание обновлений дерева
От: VladCore  
Дата: 06.09.19 10:30
Оценка:
Здравствуйте, Real 3L0, Вы писали:

R3>Здравствуйте, VladCore, Вы писали:


VC>>На другой базе храниш последний таймстамп (инкрементальный счетчик, не дату)


R3>Ага, так и делаю.


VC>>В любой момент просищ все изменения у которых таймстамп больше заданного.


R3>Я так и написал.


VC>>Как рабоает Log Shipping чем не подходит?


R3>Поверхносто почитал.

R3>У меня разные БД: MS и SQLite.

Я про принцип — все insert/update/delete ты применяеш в том же порядке что и на "мастер" базе. В результате у тебя в слейве точно такая же база и данные в ней даже во время применения всегда соответствует своим констрейнтам.

R3>Мне не нужна полная синхронизация, а только тех вещей, который относятся к пользователю.


VC>>В трех таблицах храниш колонку timestamp. Для каждой из трех таблиц хранищ одну таблицу с ID удаленных строчек, если конечно логика там удаляет строчки в БД.

VC>>Это универсальное решение. Просто не думая заводи колонку timestamp и таблицу удаленных айдишников для всех таблиц которые надо "шарить" в другие "копии" базы.

R3>Например, клиенту добавили права. У него обновился timestamp в таблице Право доступа. Как мне это поможет вычитать нужные записи из двух других таблиц?


не в таблице в а в каждой конкретной строчке.
Чтоб было понятней вот псевдокод:

changes = RetrieveChanges(prevTimestamp)
foreach(LogicalTransaction lt in changes)
{
  var table = lt.TableName;
  switch(lt.Kind)
  {
     case Update/Insert:
       .... lt содержит все колонки строки table
     case Delete:
       .... lt содержит только ID строки table
  }
  prevTimestamp = lt.Timestamp;
}


Вот это и есть простейшая поверхностная иллюстрация принципа log shipment c поллингом на "слейве".
Re[4]: [Архитектура] Отслеживание обновлений дерева
От: Real 3L0 Россия http://prikhodko.blogspot.com
Дата: 06.09.19 11:42
Оценка:
Здравствуйте, Sinclair, Вы писали:

S>
S>select top (@batch_size) * from (select Objects.id, Objects.payload, Objects.deleteFlag, AccessRights.has_access, max(Objects.last_change, AccessRights.last_change) as last_change from Objects inner join AccessRights on Objects.group_id = AccessRights.group_id and user_id = @user_id) Replication 
S>where last_change > @last_seen_change or (last_change = @last_seen_change and id > @last_seen_id)
S>order by last_change, id
S>


Описание Replication не нашёл.

У меня ID — гуиды, поэтому точно так же не получится. Но если я правильно понял мысль, мне надо будет использовать два last_seen_change: который у прав, и который у объектов.
1. Запрос: получить обновления по last_seen_change объектов.
2. Ответ: обновление объектов, обновление прав.
3. Но если в ответе идёт обновление прав, то следующими в ответе пойдут объекты из ветки, права к которой обновили
3. Запрос: если в ответе было обновление прав, то запрашиваем обновления по last_seen_change обновлённых прав и максимальному last_seen_change полученных объектов из ветки, права к которой обновили.

Вроде должно работать.
Всё равно не нравится, что два поля, но получается, без второго не обойтись.
Вселенная бесконечна как вширь, так и вглубь.
Re: [Архитектура] Отслеживание обновлений дерева
От: rm822 Россия  
Дата: 06.09.19 17:12
Оценка:
R3>А как это реализуют опытные товарищи?
Если ms-sql то юзать change tracking и snapshot isolation. https://docs.microsoft.com/en-us/sql/relational-databases/track-changes/about-change-tracking-sql-server
Re[5]: [Архитектура] Отслеживание обновлений дерева
От: Sinclair Россия https://github.com/evilguest/
Дата: 06.09.19 17:13
Оценка:
Здравствуйте, Real 3L0, Вы писали:

R3>Здравствуйте, Sinclair, Вы писали:


S>>
S>>select top (@batch_size) * from (select Objects.id, Objects.payload, Objects.deleteFlag, AccessRights.has_access, max(Objects.last_change, AccessRights.last_change) as last_change from Objects inner join AccessRights on Objects.group_id = AccessRights.group_id and user_id = @user_id) Replication 
S>>where last_change > @last_seen_change or (last_change = @last_seen_change and id > @last_seen_id)
S>>order by last_change, id
S>>


R3>Описание Replication не нашёл.

Оно является частью запроса.
(select Objects.id, Objects.payload, Objects.deleteFlag, AccessRights.has_access, max(Objects.last_change, AccessRights.last_change) as last_change from Objects inner join AccessRights on Objects.group_id = AccessRights.group_id and user_id = @user_id)

R3>У меня ID — гуиды, поэтому точно так же не получится.
Получится. Тип GUID подразумевает отношение полного порядка, поэтому всё сработает корректно.

R3> Но если я правильно понял мысль, мне надо будет использовать два last_seen_change: который у прав, и который у объектов.

Нет. Каждый клиент должен хранить пару (timestamp, id), которая получилась у последней строки из последнего батча, который он успешно сохранил.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[2]: [Архитектура] Отслеживание обновлений дерева
От: std.denis Россия  
Дата: 06.09.19 19:17
Оценка: +1
vsb>Обновить таймстэмп у ветки.
и заставить всех 100500 клиентов скачивать эту ветку?
Re[3]: [Архитектура] Отслеживание обновлений дерева
От: vsb Казахстан  
Дата: 06.09.19 20:50
Оценка:
Здравствуйте, std.denis, Вы писали:

vsb>>Обновить таймстэмп у ветки.

SD>и заставить всех 100500 клиентов скачивать эту ветку?

Да. Если это будет проблемой, начать решать уже эту проблему. Самый простой способ — разделить скачивание на два этапа — на первом этапе запрашиваются ID и контрольные суммы, на втором этапе клиент сравнивает контрольные суммы с локальными и запрашивает данные по нужным ID. Но это уже потом, если это действительно станет проблемой. Скорей всего не станет, никто каждые 5 секунд не будет менять права на ветки.
Re[4]: [Архитектура] Отслеживание обновлений дерева
От: std.denis Россия  
Дата: 08.09.19 09:06
Оценка: +1
vsb>Да. Если это будет проблемой, начать решать уже эту проблему.
ну такое себе, сделать проблему чтобы её героически решать)

vsb>Скорей всего не станет, никто каждые 5 секунд не будет менять права на ветки.

часто такое "да скорее всего никто" превращается в геморрой в дальнейшем 😅

По мне так лучше предусмотреть отдельный метод для скачивания иерархии, к которой юзеру предоставили доступ, как уже выше предложил BlackEric
Re[5]: [Архитектура] Отслеживание обновлений дерева
От: rm822 Россия  
Дата: 08.09.19 17:31
Оценка: 42 (2)
в реальности, надо понимать что timestamp — это НЕ корректная метка последнего обновления.
как на таймстемпах пропустить апдейт
пример: 3 транзакции, по горизонтали время
writer1: begin tran -------- insert (timestamp = 2) ---------------------------------------------------- commit
writer2: ----begin tran -------- insert (timestamp = 3) --- commit
reader1: ----------------------------------------------------begin tran -- read timestamp=3 ---- commit

ридер читает timestamp =3, т.к. он уже закомичен, и соотв никогда не увидит данные с timestamp=2
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.