Як ми розробили функцію спільного написання листів email-клієнта Spark

Мене звати Дмитро Поволоцький, я iOS/Mac розробником в Readdle на проект Spark . У цій статті я розповім про нашому шляху до реалізації одного з найцікавіших в технологічному плані фіч Spark — «Shared Drafts».

В чому проблема

Взаємодія між людьми — невід'ємна складова командної роботи. Ми постійно обмінюємося документами, обговорюємо і делегуємо завдання. За останні 5-10 років інструменти для командної роботи значно еволюціонували. Ми переписуємося в корпоративних месенджерах (Slack, Skype), разом редагуємо документи (Google Docs, Pages, Dropbox), працюємо над кодом (пулл-риквесты на GitHub, Crucible) і т. д. Але командна робота з email чомусь не користується популярністю, хоча ця ідея і лежить на поверхні.

Уявімо, що СЕО компанії пише важливий лист інвесторам і хоче додати туди цифри з останнього фінзвіту. Керівник запитує ці дані фінансового відділу. Але СЕО повинен відправляти лист від свого імені, тому йому доводиться самому редагувати текст і додавати туди фінансову інформацію (хоча цю роботу можна і делегувати). А що якби він міг просто поділитися чернеткою листи з колегами з фінансового відділу, і вони додали всі потрібні цифри? Ідеально! Але можна зробити це за допомогою популярних 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 можливість відображення курсора/виділення всіх учасників редагування. І, звичайно ж, у нас є плани з розширення функціоналу чернеток і багато інших ідей, що очікують реалізації.

Опубліковано: 08/08/19 @ 10:00
Розділ Різне

SEO Блог