Как мы разработали функцию совместного написания писем в email-клиенте Spark
Меня зовут Дмитрий Поволоцкий, я являюсь iOS/Mac разработчиком в Readdle на проекте Spark. В этой статье я расскажу о нашем пути к реализации одной из самых интересных в технологическом плане фич Spark — «Shared Drafts».
В чем проблема
Взаимодействие между людьми — неотъемлемая составляющая командной работы. Мы постоянно обмениваемся документами, обсуждаем и делегируем задачи. За последние
Представим, что СЕО компании пишет важное письмо инвесторам и хочет добавить туда цифры из последнего финотчета. Руководитель запрашивает эти данные у финансового отдела. Но СЕО должен отправлять письмо от своего имени, поэтому ему приходится самому редактировать текст и добавлять туда финансовую информацию (хотя эту работу можно и делегировать). А что если бы он мог просто поделиться черновиком письма с коллегами из финансового отдела, и они добавили все нужные цифры? Идеально! Но можно ли сделать это с помощью популярных email-клиентов? К сожалению, здесь нет простого способа.
Мы в Readdle решили разработать новый способ взаимодействия между пользователями в нашем email-клиенте под названием Spark. Мы хотели дать людям такой же простой и интуитивный инструмент для совместной работы над черновиками писем, как Google Docs.
Как реализовать это с технической точки зрения? Как позволить нескольким людям одновременно редактировать текст, форматировать его, вставлять туда изображения и при необходимости отменять предыдущие действия? На эти вопросы нам еще предстояло ответить.
Если вы считаете, что это не так уж и сложно, давайте посмотрим на самый простой пример и возможные проблемы.
Алиса и Боб хотят отредактировать документ. Для простоты, рассмотрим случай, когда единственное возможное действие — вставить символ C на позицию N. Все просто! Нам нужно лишь передавать такие команды от одного пользователя другому.
Видите проблему? Она здесь есть. Допустим, изначально оба пользователя видят текст «123456789». Они одновременно замечают, что в последовательности не хватает нуля. Алиса решает добавить его в начале текста, а Боб — в конце. Теперь Алиса видит «0123456789», а Боб — «1234567890», свою версию текста. Так как мы говорим о взаимодействии в реальном времени, то результаты должны синхронизироваться, чтобы пользователи видели все изменения. Алиса отправляет Бобу команду: «Insert ’0′ in position 0», Боб говорит Алисе: «Insert ’0′ in position 9». Каждый клиент получает команду от противоположной стороны и пытается изменить текст. Что происходит? Боб вставляет «0» на позицию 0 и получает «01234567890». Но Алиса ставит «0» на девятое место и получает комбинацию «01234567809» — не совсем то, что мы ожидали увидеть. Это и есть базовый конфликт, который нам нужно решить.
Проблема работы над текстом в реальном времени не нова, и существует несколько известных алгоритмов, позволяющих решить ее. Самые популярные из них — OT (Operational Transformation) и CRDT (Conflict-free Replicated Data Type). С них мы и начали наш путь.
OT (Operational Transformation)
Мы решили начать с OT как с самого известного и хорошо изученного алгоритма. OT — довольно старый алгоритм, опубликованный в 1989 году. Google успешно использовала OT и расширяла его функциональность сначала в Google Wave, а позже в Google Docs.
Основная идея проста: пользователи отправляют изменения в виде операций, и каждая входящая операция трансформируется на основе уже существующих. Давайте посмотрим, как ОТ работает в указанном выше примере с Алисой.
У Алисы есть операция «Insert ’0′ in position 0» = INS(’0′, 0), и она получает еще одну операцию «Insert ’0′ in position 9» = INS(’0′, 9).
Следуя алгоритму ОТ, нам нужно трансформировать входящие операции учитывая исходящие операции с момента последней синхронизации. Другими словами, нам нужно изменить параметры операции так, чтобы измененная входящая операция, примененная на результат действия исходящей операции дала тот же результат, как исходная неизмененная операция. Это значит, что нам нужны правила для пар операций каждого типа — то есть N2 правил. Например, в нашем случае есть две операции вставки одного типа (Insert). Нам нужно правило для преобразования одной операции вставки (А) на основе другой (В).
Мы можем использовать следующее правило: если позиция в операции В меньше, чем в А, увеличим позицию операции А на длину текста в В. Проверим, как это работает в нашем случае. Входящая операция для Алисы — INS(’0′, 9), исходящая — INS(’0′, 0). Нам нужно изменить INS(’0′, 9) беря во внимание INS(’0′, 0). Позиция 9 больше, чем 0, поэтому мы увеличим ее на 1 (длина текста, который мы вставляем). Операция INS(’0′, 9) трансформируется в INS(’0′, 9+1) = INS(’0′, 10), и, применив ее на текст «0123456789», мы получим «01234567890».
Посмотрим на ситуацию Боба. Ему нужно трансформировать INS(’0′, 0) с учетом его собственной операции INS(’0′, 9). Но 0 меньше 9, поэтому никакие изменения не требуются и операция INS(’0′, 0) остается без изменений. Применив ее, он получит тот же текст, что и у Алисы: «01234567890». Работает!
Это было просто. Но когда вы будете масштабировать этот подход, то можете заметить одну проблему. Если Алиса уже отправила одну или несколько операций, как мы узнаем получил и применил ли ее Боб, когда отправлял свои операции? Нужно ли трансформировать входящие операции от Боба, или они порождены уже с учетом операций Алисы?
Чтобы решить эту проблему, каждый клиент должен знать текущее состояние других клиентов. Такое решение довольно дорого, если у вас несколько клиентов. Чтобы избежать этих трат, мы можем уменьшить количество связей и использовать сервер, который координирует всех клиентов. В таком случае, они синхронизируются только с сервером, и им нужно знать лишь о его состоянии. Недостаток этого подхода состоит в том, что серверу придется действовать как клиенту, принимая операции от других клиентов. Это значит, что нам нужно дублировать на сервере всю логику клиента. А это усложнит будущие обновления, тестирование и отладку.
К тому же, мы пока обсуждали только один тип операций, но реальная жизнь намного сложнее (вспомните о форматировании, изображениях и т. д.). Нам нужно продумать и реализовать трансформации для всех возможных пар операций. Все усложняется еще сильнее, если нужно добавить функциональность undo/redo.
Учитывая все это, мы решили на время отложить OT и рассмотреть другую возможность — CRDT.
CRDT (Conflict-free Replicated Data Type)
Общая идея CRDT довольно проста: это структура, которая «может реплицироваться на нескольких компьютерах в сети, где реплики могут обновляться независимо и одновременно, не координируясь друг с другом, и где возможные несоответствия можно разрешить математически» (Википедия).
Если говорить простым языком, CRDT — это структура, позволяющая применять операции в любом порядке, в условиях возможных задержек и дублирований в коммуникации. Звучит как магия. Чтобы разобраться, как это работает, рассмотрим самую простую структуру CRDT — grow only counter (увеличивающийся счетчик).
Grow only counter
Что может быть проще счетчика? Единственная доступная операция — «увеличить на 1», единственный результат — значение на счетчике.
Но всё не так просто, если вы хотите использовать этот счетчик на нескольких распределенных нодах с децентрализованной синхронизацией.
Структуры CRDT изначально призваны работать в условиях нестабильного соединения, когда пакеты могут теряться или дублироваться. Однако нам не нужен такой уровень стабильности, так как мы используем сетевые протоколы с гарантированной доставкой. Но давайте представим наихудший сценарий. Как передавать изменения счетчика? Мы не можем отправить обновленное значение, так оно уже могло устареть после изменения другим пользователем. Мы не можем просто отправлять операции инкремента, так как сообщения могут дублироваться. CRDT решает эту проблему просто и элегантно, предоставляя каждой ноде собственный счетчик.
Ноды передают свои значения, и каждая из них хранит значения других нод. Значения всех нод суммируются, чтобы получить окончательный результат. Каждая нода может в любое время изменить значение и передать его другим, что позволяет избежать конфликтов. Дублирование событий — не проблема. Мы передаем только значения, а не операции, потому повторная передача не изменит состояния. Задержка — тоже не проблема. Мы получим значение позже. Даже изменение порядка пакетов в процессе передачи не является проблемой, так как мы знаем, что значение может только расти и можем игнорировать пакеты со значением ниже текущего. Изящное решение для любой сети.
Мы рассмотрели, как алгоритмы CRDT решают проблемы взаимодействия между пользователями. Но нам нужен не простой счетчик, а решение для совместной работы над текстом. К счастью, существуют алгоритмы CRDT и для этой задачи. Первый алгоритм, который мы попробовали, называется Logoot.
Logoot
Основная идея состоит в том, чтобы присвоить каждому символу в тексте ID, который строго возрастает в рамках всего текста, и использовать этот ID для адресации в тексте. Такой подход позволит синхронизировать текст на всех устройствах независимо от того, как пользователи редактируют его.
Давайте рассмотрим пример: два пользователя пытаются написать слово «HELLO».
- Алиса хочет вставить первый символ «H». Чтобы совершить эту операцию, нам нужно сгенерировать ID для этого символа. Для начала, ограничим наш выбор и добавим виртуальные символы S (для Start) и E (для End). Пусть у S будет id=0, а у E=1000. Генерация новых ID — сама по себе интересная тема. Но для простоты мы выберем для нового символа первый из возможных ID — 1. Теперь у нас есть операция INS(‘H’, 1).
- Боб получает операцию вставить символ «H» с id=1. Мы ищем в текущем тексте символ с максимальным ID менее 1 (учитывая, что в тексте используются возрастающие ID, мы можем использовать бинарный поиск, чтобы выполнить задачу быстрее). Очевидно, таким символом окажется виртуальный символ S, после которого мы вставим «H». Успех! На всех нодах появился символ «H».
- Теперь Алиса хочет вставить «L» после «H». На этот раз, мы выбираем ID в диапазоне между 1 («H») и 1000. Мы опять используем простой генератор ID и выбираем следующее доступное значение — это 2. Наконец повторяем предыдущий шаг на всех нодах. И снова успех! Теперь у нас есть «HL» на всех нодах.
- Но подождите, кажется, Алиса забыла вставить «E» между «H» и «L». Для вставки такого символа нам понадобится ID в диапазоне 1<id<2. Хм, интересно. Но кто сказал, что ID может быть только целым числом? Мы можем использовать массив чисел. Выберем 1 на первом уровне и перейдем на второй уровень, который сейчас пуст. Здесь мы снова можем использовать диапазон от 0 до 1000 и выбрать любое значение между ними. Например, выберем 1 и получим ID 1.1. Мы сохранили строгую последовательность ID, и другие ноды смогут выполнить эту операцию у себя. Отлично, все почти готово!
- Но помните, что над текстом работает несколько человек. Боб тоже заметил ошибку в слове и в тоже время пытается исправить ее. Боб оказался голландцем, поэтому он вставляет «А» вместо «Е» (как вы вероятно знаете, «hello» по-голландски будет «hallo»).
- Согласно текущему алгоритму, Боб и Алиса не знают друг о друге, поэтому оба символа получают одинаковый ID, что ломает принцип строгого возрастания последовательности.
Похоже на проблему. К счастью, ее легко исправить.
Сначала присвоим ID каждому пользователю (мы называем его site ID). Для наглядности, возьмем ID «А» и «В», хотя в реальной жизни удобнее использовать последовательность целых чисел. Теперь добавим эти site к ID каждого символа. Символ с ID 1, который создал пользователь «А», становится 1:А. Теперь дублирование символов невозможно, а при сравнении ID мы также будем использовать site ID. Проблема решена, и мы добились строгого порядка даже в случае коллизии.
Этот простой алгоритм позволяет нам добавить любое количество символов в любом порядке и показать всем пользователям одинаковый результат.
Операция удаления тоже довольно проста: достаточно указать ID символа, который будет удален. Имея возможность вставлять и удалять символы, мы можем редактировать текст любым образом.
Можно заметить важный момент: данная система не будет работать, если события будут получены в неверном порядке (например, вставка после соответствующего удаления). Эту проблему можно решить несколькими способами. Но, к счастью, мы работаем с централизованным сервером и гарантированно получаем все события в правильном порядке, потому для нас этой проблемы не существует.
Полученный алгоритм показался достаточно хорошим для нашей задачи, и мы решили попробовать создать прототип. После нескольких дней реализации мы получили первый Proof of Concept для механизма взаимодействия между пользователями.
Все работало как по маслу... но оставалась одна маленькая, но важная проблема. Представим, что два пользователя работают офлайн, а затем начинают синхронизировать созданные документы. У первого пользователя есть такие события: H — 1:A, E- 2:A, L — 3:A, L — 4:A, O — 5:A, а у второго — B — 1:B, Y- 2:B, E — 3:B. Что получится в результате?
HBEYLELO — не совсем то, что мы ожидали увидеть. Кропотливая работа двух людей уничтожена нашим алгоритмом!
Такой продукт определенно нельзя было выпускать, поэтому мы стали искать новый алгоритм.
RGA (Replicated Growing Array)
Это был сложный период: мы думали, что сделали неправильный выбор и лучше вернуться к ОТ алгоритмам. Но к счастью, мы нашли другой CRDT алгоритм под названием RGA (Replicated Growing Array). Он во многом похож на Logoot, но лишен проблем со слиянием двух офлайн-версий документа. Этот алгоритм казался простым и быстрым решением наших проблем, и мы снова вернулись к реализации.
Давайте посмотрим на этот алгоритм. У каждого символа по-прежнему есть ID, но теперь мы генерируем его таким образом: new id = (max_id +1, site_id). Операция вставки теперь адресует позицию с помощью ID символа, находящегося слева от места, куда мы вставим новый символ. Таким образом, операция содержит ID символа слева, ID нового символа, который мы будем вставлять; и сам символ.
В случае коллизии (когда две операции пытаются вставить символы на одну и ту же позицию) мы используем следующее правило: проверяем символы справа от места вставки нового символа и пропускаем все символы с ID больше, чем ID нового символа. Таким образом мы сможем сохранить строгий порядок.
Как насчет удаления текста? Это первый недостаток RGA. Все операции учитывают ID символов, потому мы не можем просто удалить один из них — он может использоваться в событиях других клиентов. Чтобы решить эту проблему, мы пометим удаленный символ как недействительный, уберем его из текста, но оставим во внутреннем представлении. Кажется, теперь у нас есть все части головоломки: мы можем вставлять и удалять символы, а значит и редактировать текст!
Довольно быстро мы перевели нашу реализацию с Logoot на RGA и начали придирчиво тестировать наше решение. К счастью, в этот раз результат оказался довольно хорош. Мы не обнаружили серьезных неисправностей, кроме проблем с производительностью, которые были оперативно решены с помощью некоторых оптимизаций.
Получив более-менее стабильную версию алгоритма, мы приступили к внедрению его в Spark.
Результаты
Мы успешно внедрили RGA для совместной работы над текстом и сейчас используем этот алгоритм для функции совместного редактирования черновиков в Spark. Рассмотрим плюсы и минусы алгоритма:
Плюсы:
- Простой алгоритм, что облегчает тестирование, отладку, добавление новых функций и жизнь в целом ;)
- Вся логика слияния нескольких версий документа содержится на стороне клиента, благодаря чему наш сервер остается простым. Следовательно, при дальнейших обновлениях нам не нужно проводить изменения на обеих сторонах.
Минусы:
- Необходимо хранить всю историю событий. Нет простого способа сохранить промежуточное состояние документа.
- При каждом открытии текста необходима обработка полной истории, чтобы восстановить последнюю версию. В результате, открытие черновика может занимать значительное время.
- ID не имеют строго порядка, а распределены по тексту случайным образом, поэтому нам приходится пользоваться медленным линейным поиском, чтобы найти индекс символа по ID.
Безусловно, мы не остановились на этом. Наша команда добавила возможность вставлять в письма изображения, форматировать текст и отменять или повторять предыдущие действия пользователя (undo/redo). Мы также реализовали в Spark возможность отображения позиции курсора/выделения всех участников редактирования. И, конечно же, у нас есть планы по расширению функционала черновиков и много других идей, ожидающих реализации.
