Как синхронизируется Lists

Несколько дней назад я рассказывал про Lists , свой список дел для macOS, Android и веба. Там синхронизации досталось несколько абзацев. Эта статья целиком про неё: какую задачу она решает, почему устроена именно так и что в ней пришлось переделать за первые десять дней.

Задача

Требования к синхронизации у меня были такие:

• своего сервера у проекта нет, и учётных записей тоже;
• приложение полностью работает без сети, правка пишется на устройство сразу;
• устройств несколько, и правят они без связи друг с другом;
• ни одна правка не теряется, а файлов вида «конфликтная копия» не бывает.

Из первого пункта следует, что данные лежат там, где они уже есть у человека. Из третьего и четвёртого — что два устройства обязательно изменят одну задачу одновременно, и приложение должно само решить, что получится, не спрашивая пользователя.

Почему WebDAV

Хранилище, которое есть почти у всех, кто держит что-то своё: каталог WebDAV. Его отдают Nextcloud, Synology, SFTPGo, Fastmail, его легко поднять самому. Но WebDAV — «тупое» хранилище. Оно умеет читать, писать, перечислять и удалять файлы, и больше ничего: ни транзакций, ни надёжных блокировок, ни уведомлений об изменениях.

Отсюда главное решение. Если хранилище ничего не умеет, вся логика должна жить на устройствах, а от хранилища нужны только эти четыре операции. Тогда подходит и обычная папка, которую синхронизирует другая программа: Syncthing или iCloud Drive.

Как сливаются правки

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

Поэтому в Lists каждое поле каждой задачи хранится отдельно и несёт метку времени. Метка — гибридные логические часы: миллисекунды, счётчик и идентификатор устройства в одной строке. Для каждого поля побеждает значение с большей меткой. Правки разных полей сохраняются обе, а при правке одного поля побеждает поздняя. Удаление тоже поле, deleted, а не стирание строки, поэтому заметка, дописанная к задаче, которую в это время удалили на другом устройстве, вернётся вместе с задачей из корзины.

Такая схема называется CRDT: итог не зависит от того, в каком порядке дошли изменения. Два устройства с одинаковым набором изменений показывают одно и то же. Тест прогоняет три устройства через случайные правки и синхронизации и сверяет итог¹.

Готовые библиотеки я рассматривал и отказался. У Automerge нет операции перемещения, а задачи перемещаются постоянно. cr-sqlite не выпускал релизов с января 2024 года. Loro хранит собственный двоичный документ рядом с SQLite, а не вместо него. Для записей со скалярными полями регистры по полям проще, и их целиком покрывают тесты².

Журнал изменений

Вторая проблема — где хранить изменения так, чтобы два устройства не писали в один файл. Без блокировок одновременная запись одного файла кончается тем, что одна запись затирает другую.

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

lists/v1/
  vault.json                       {"format":2,"vault":"<uuid>"}
  log/<устройство>-<номер>.jsonl
  log/<устройство>-<номер>.snap    отметка о снимке
  snap/<устройство>-<номер>.jsonl  снимок, сжат gzip
  blobs/<два знака>/<sha256>
  push/<устройство>.json

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

Обрывы сети учтены двумя правилами. Первая строка файла — заголовок с числом изменений. Если строк меньше или какая-то не читается, файл считается недописанным, и устройство не продвигается за него, а перечитывает в следующий раз. Свой файл устройство фиксирует локально до первой попытки выгрузки, поэтому повтор после сбоя отправляет те же байты под тем же номером.

Синхронизация, которой нечего читать и нечего отправлять, стоит одного запроса — списка log/. Раз в минуту, пока приложение открыто, это важно.

Почему отдельно журнал и снимок

Журнал только растёт. Устройство, подключённое к хранилищу через полгода, должно было бы прочитать все файлы всех устройств с первого. Хранить только полное состояние тоже нельзя: тогда каждая правка переписывает один большой файл, и снова встаёт вопрос, кто его пишет.

Поэтому изменения и полное состояние лежат отдельно. Время от времени устройство записывает снимок: всё состояние по такой-то номер своего журнала и таблицу «устройство → номер последнего учтённого файла». После этого оно кладёт в log/ пустую отметку .snap и удаляет свои покрытые файлы журнала и прежний снимок.

Снимок нужен не всем. Устройство, которое в курсе, читает следующий файл журнала и снимков не скачивает. Снимок читает только тот, кто отстал или подключился впервые: следующего файла уже нет, а отметка говорит, что есть снимок новее. Слияние снимка подчиняется тому же правилу «большая метка побеждает», поэтому читать его безопасно в любой момент.

Отметка в log/ появилась не сразу. Без неё о снимке можно было узнать только отдельным запросом списка snap/, и холостая синхронизация стоила двух запросов. С отметкой список snap/ запрашивается при первой синхронизации после запуска и тогда, когда отметки не объясняют пропуск.

Почему ещё и CalDAV

Первая версия архитектурного документа отклоняла CalDAV целиком. Проверка в тот же день показала, что это слишком категорично. CalDAV нужен в двух случаях: у человека есть только он, или задачи хочется видеть ещё и в Tasks.org, DAVx5 и других клиентах.

В CalDAV список становится календарём, а задача — объектом VTODO. Стандартные поля идут в стандартные свойства: название, заметка, даты, приоритет, теги, повтор. Всё остальное и метки всех полей лежат в собственном свойстве X-LISTS-STATE. Правила слияния те же, меняется только место хранения. Если стандартное свойство расходится с тем, что записано в состоянии, значит, задачу правил чужой клиент, и его правка принимается как новое значение поля.

У CalDAV своя цена. Объект заменяется целиком, поэтому запись идёт с If-Match, а при отказе объект перечитывается, сливается и записывается снова. Вложения лежат внутри объекта в base64, поэтому предел — 5 МБ на файл и 20 МБ на задачу. Сервер, который вырезает неизвестные свойства (судя по коду, так делает Cyrus), оставит от задачи только стандартные поля³. Поэтому CalDAV — второй способ, а основной — журнал поверх WebDAV.

Вложения отдельно от задач

Вложение может весить мегабайты, а поле задачи — десятки байт. Если синхронизировать их вместе, задача с телефона ждёт, пока докачается PDF.

Поэтому синхронизация идёт в два прохода. Первый передаёт только поля и заканчивается, не трогая blobs/; после него приложение уже показывает пришедшее. Второй выгружает и скачивает содержимое вложений. Файл лежит под именем своего SHA-256, и содержимое, хеш которого не совпал с именем, на устройстве не сохраняется. Сбой на одном файле не останавливает остальные и не считается сбоем синхронизации.

Здесь же нашлась первая ошибка с настоящим сервером. На SFTPGo за Caddy выгрузка файла в ещё не созданную папку blobs/c2/ падала тридцать раз подряд. Код уже умел создавать папку после ответа 404 или 409, но сервер на Go при теле больше 256 КБ отвечает отказом, не дочитав запрос, и закрывает соединение. Клиент видел обрыв, а не ответ, и до создания папки не доходил. Теперь при обрыве устройство спрашивает, есть ли папка, создаёт недостающие и повторяет запись один раз⁴.

Толчки через ntfy

Остаётся проблема, которую журнал не решает: хранилище не умеет сообщать, что в нём что-то изменилось. Устройство узнаёт о чужой правке, только когда само заглянет в log/. Пока приложение открыто, это раз в минуту. Закрытое приложение на Android синхронизируется в фоне раз в 15 минут, и то если система не отложит. Задача, добавленная на компьютере, могла появиться на телефоне через четверть часа.

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

Устройство, выгрузившее изменения, отправляет остальным толчок: POST с телом sync. Данных толчок не несёт, задачи по-прежнему идут через хранилище. Сервер ntfy видит моменты правок, но не их содержимое. Получив толчок, устройство запускает обычную синхронизацию. Она ничего не выгружает, поэтому ответного толчка нет.

Адреса устройства публикуют в том же хранилище, в push/<устройство>.json, и отдельной настройки для обмена адресами не нужно. Mac и веб-сервер держат подписку на тему ntfy сами. На Android подписку держит приложение-распространитель UnifiedPush, например тот же ntfy, и адрес выдаёт он. Получив толчок, Lists ставит синхронизацию срочной задачей системы, поэтому она идёт и при закрытом приложении. На эмуляторе задача, добавленная на другом устройстве, дошла до телефона с убитым процессом приложения примерно за три секунды⁵.

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

Что переделали в толчках

Первая версия отправляла толчки внутри прохода синхронизации, по одному адресу за раз, с ожиданием до пяти секунд на каждый. Один недоступный адрес задерживал синхронизацию на пять секунд. Теперь запросы уходят одновременно и уже после прохода: проход их не ждёт.

Вторая доработка — общая тема. Сначала каждое устройство выбирало себе случайную тему из 32 знаков, и отправитель слал по запросу на каждое. Я разбирал вариант с одной темой на всех, и разбор советовал оставить как есть: выигрыш — несколько запросов, а Android всё равно остаётся при адресе распространителя. Сделали всё же общую тему, но без нового механизма. Устройства с одним сервером ntfy видят адреса друг друга в push/, берут наименьший и переходят на него. Один запрос будит все такие устройства, а своё сообщение отправитель узнаёт по заголовку X-Title и пропускает. Пока устройства не сошлись на одной теме, толчки идут по прежним адресам, и ни один не теряется.

Третья — свой сервер ntfy с закрытым доступом. Lists передаёт ему токен в заголовке Authorization, но только на сервер из настроек самого устройства. Адреса в хранилище может записать кто угодно с доступом к нему, и токен не должен уходить по ним. Отказ сервера во входе показывается в настройках, остальные сбои толчка — нет.

Снимок по весу, а не по числу файлов

Поначалу снимок писался, когда у устройства набиралось больше 64 своих файлов журнала. Порог считал файлы, а не байты. На моих данных (202 задачи, 1876 полей) снимок весит 246 КБ JSON, а обычный файл журнала — несколько сотен байт. Мелкие правки платили полной выгрузкой каждые 64 прохода. А крупное изменение, например импорт, ждало 65-го файла, прежде чем отставшие устройства получали компактное состояние.

Теперь снимок пишется, когда файлы журнала после последнего снимка весят больше самого снимка, или когда своих файлов в log/ стало больше 256. Пока снимка нет, за его размер берётся 16 КБ. На снимки уходит не больше байт, чем на сами изменения, а отставшее устройство читает не больше снимка и хвоста журнала того же размера. Так же Redis решает, когда переписать журнал AOF. Решение принимает только пишущее устройство, поэтому формат хранилища от этой правки не изменился.

Заодно снимок стал сжиматься gzip: 246 КБ превращаются в 32,5 КБ. Я замерил и двоичную запись, с идентификаторами и метками в байтах. Со сжатием она дала 29,3 КБ, на 10 % меньше, но файлы перестают читаться без инструментов, и от неё я отказался. Файлы журнала не сжимаются: в них сотни байт, и выигрыш меньше накладных расходов на запрос⁶.

Проблема смены формата

Сжатие снимка оказалось первой правкой, которая сломала совместимость.

До неё формат хранилища менять не приходилось, хотя данные менялись не раз. Появился исход «не буду делать», общие настройки, отмена завершения повтора. Каждый раз это было новое поле, а устройство старой версии неизвестные поля хранит и передаёт дальше, только не применяет. Задачу «не буду делать» старая версия показывает просто выполненной, но ничего не портит. Номер формата оставался прежним.

Со сжатием так не выйдет. Старая версия не прочитает gzip вообще, а молча пропущенный снимок хуже ошибки: устройство будет ждать файл журнала, которого уже нет. Поэтому в vault.json формат поднялся до 2, а переход устроен так:

• Устройство новой версии при первой синхронизации с хранилищем формата 1 переписывает vault.json с форматом 2 и прежним идентификатором хранилища. Два устройства, сделавшие это одновременно, пишут одни и те же байты, так что гонка здесь безвредна.
• Всё, что оно пишет дальше, — формат 2. Старые файлы остаются читаемыми и уходят сами, когда их устройства в следующий раз сожмут журнал. Специально ничего не переписывается.
• Устройство старой версии останавливает синхронизацию с понятной ошибкой: «хранилище использует формат 2, эта версия понимает формат 1; обновите приложение». Оно узнаёт это из vault.json при запуске или раньше, когда встретит нечитаемый файл. Работа на устройстве продолжается, а правки уйдут после обновления.
• Имя снимка нарочно не поменялось. Под новым именем старая версия снимка просто не увидела бы и ждала бы пропавший файл журнала без всякой ошибки.

Обратного пути нет: старой версии файлы формата 2 не прочитать. Поэтому с выпуском 0.5.0 все устройства нужно обновить примерно в одно время: Mac, телефон и веб-сервер. Пока пользователей мало, я считаю это приемлемой ценой. CalDAV эта смена не затронула: у него нет ни vault.json, ни снимков.

Удаление ненужных вложений

В том же выпуске закрылась ещё одна дыра: содержимое вложений не удалялось никогда. Файл, убранный из задачи, и файлы задач, удалённых навсегда, лежали и на устройстве, и в хранилище. На моём Mac из 6,1 МБ в blobs/ не были нужны ни одной задаче 4,5 МБ.

Удалять общее содержимое сложнее, чем кажется. Имя файла — хеш, поэтому одно содержимое могут держать вложения разных устройств. Устройство без связи могло снова прикрепить тот же файл и считать его уже выгруженным. Поэтому удаление идёт в два хода. Устройство, увидевшее содержимое ненужным, удаляет файл из blobs/ и только потом пишет в журнал поле blob/<хеш>/gone. Устройство, которому файл ещё нужен, получив это поле, забывает, что он был в хранилище, и выгружает его заново. Порядок важен: запись до удаления позволила бы второму устройству проверить хранилище раньше удаления и не узнать о нём.

Задача в корзине своё содержимое держит: её восстанавливают вместе с вложениями. Удаление делается только в конце прохода, который прочитал всё хранилище: посреди прохода устройство ещё не знает всех ссылок на файл.

Как это работает на деле

Синхронизацией я пользуюсь каждый день: мои устройства обмениваются задачами через свой сервер WebDAV. Ядро синхронизации, кроме того, покрыто тестами против папки, тестового сервера WebDAV и тестового сервера CalDAV, а CalDAV отдельно прошёл проверку на Radicale 3.8.2.

Тесты нашли не всё. Ошибку с SFTPGo обнаружила именно ежедневная работа: журнал настоящего сервера показал то, чего тестовый сервер не воспроизводил. Поэтому, если у вас Lists синхронизируется через свой сервер и что-то идёт не так, напишите в задачах репозитория и, если можно, приложите журнал сервера.