Синхронизация истории в мессенджерах

https://www.ejabberd.im/mod_archive

это не то

https://xmpp.org/extensions/xep-0313.html

считаются хэши от половинок истории

Теперь подумай, что будет, если у одногй стороны 10000 сообщений, а у другой 10002

плохо будет :)

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

нужно что-то типа мерджа в гите )

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

Зачем?

А другие подробности о намечающемся мессенджере будут?

Смысл? Не взлетит же.

man git-fetch

Может просто помнить время последней синхронизации с конкретным клиентом и обмениваться всеми сообщениями позднее этого времени?

Сначала подумал - для Tox, что ли? Потом увидел имя автора и понял, что для мессенжера авторского разлива :)

man three way merge. Так работают синхронизаторы почтовых архивов (offlineimap, mbsync), так работает syncthing на директориях, так работает и слияние кода в VCS.

А, чёрт, нет общего предка, three way merge не подходит.

Ну, можно сделать аналог прогона rsync без флага --delete в обоих направлениях. Везде добавить всё отсутствующее. Вроде просто реализуемо.

не пали контору :)

по ходу да, придётся в алгоритм rsync-а вникать

Для каждой записи хранишь метаданные в виде (реплика_ид, запись_ид). А так же максимальное значение запись_ид для всех известных реплик.

Реплика_ид задаёт уникальный идентификатор конкретного устройства.

Запись_ид - локальный счетчик который инкрементится когда приходит новое сообщение в текущую реплику.

Когда нужно провести синхронизацию для каждой реплики выбираешь все записи где запись_ид > максимальной известной записи для выбранной реплики.

А так же максимальное значение запись_ид для всех известных реплик.

а вот про это поподробнее, максимальное значение тоже как-то синхронизировать надо

при этом каждая сторона ведёт свою историю локально, запись_ид с нуля на каждом инстансе начинается. Или нет?

Запись_ид в каждой реплике свой, начинается например с 1 для удобства. В процессе синхронизации реплика может получить записи с других реплик. Но у них будет другое значение реплика_ид, таким образом пара (реплика_ид, запись_ид) задаёт глобальный уникальный идентификатор записи.

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

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

Ты ничего не понял из моего объяснения :-)

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

Вот тебе псевдокод для синхронизации в одну сторону. В обратную аналогично.

var thisReplica = ..  // реплика, куда льем записи
var otherReplica = .. // реплика, откуда льем записи

// Перебираем последние известные сообщения 
for (var (replicaId, recordId) in otherRelica.getKnownReplicas())
{
    // получаем последнее известное сообщение
    var thisRecordId = thisReplica.getLastKnownId(replicaId);

    // проверяем что есть неизвестные сообщения
    if (thisRecordId < recordId)
    {
        // получаем все сообщения с recordId > thisRecordId
        var records = otherReplica.getRecordsSince(replicaId, thisRecordId);
        
        // сохраняем новые сообщения
        thisReplica.addRecords(records);

        // обновляем информацию о последнем известном сообщении
        thisReplica.setLastKnownId(replicaId, recordId);
    }
}

а отдавать реплика будет записи только со своим replicaId или чужие тоже?

Все которые ей известны

А хранить данные во временной таблице вида

• ID чата
• ID сообщения
• ID клиента (кому должно упасть)
• Status

Не вариант?

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

это ты сейчас про доставку сообщений, а не про синхронизацию

Тебе между своими клиентами?

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

Любой каприз за ваши деньги