Несколько недель назад я посмотрел презентацию Мартина Клеппмана про его подход к редактированию в реальном времени через CRDT и ощутил жгучее отчаяние. Его подход хорош настолько, что превосходит всю мою работу за последнее десятилетие, и места в будущем ей уже не видать.
Но начнем сначала.
В 2010 году я работал в Google Wave, где мы пробовали создать совместные редактируемые пространства для замены электронной почты, Google Docks, форумов, мгновенных сообщений и многих других однозадачных приложений. Среди моих инструментов мне особенно нравится среда общего назначения, нигде более как в Wave не сформулированный в то время функционал. В отличие от большинства других инструментов, среда общего назначения не навязывает собственный рабочий процесс, благодаря чему через нее можно планировать праздники, создавать вики-проекты, играть с друзьями в настольные игры, назначать рабочие собрания и много чего еще.
Изнутри совместное редактирование Wave работает поверх операционного преобразования (Operational Transform, OT), и в то время им пользовались уже не один день: наш алгоритм основывался на докладе Jupiter 1995 года. Для каждого документа алгоритм хранит отдельный хронологический список изменений, «Набрать H в позиции 0», «набрать i в позиции 1» и так далее. В большинстве случаев пользователи меняют последнюю версию документа, и лог выглядит как последовательность изменений, однако при совместном редактировании мы сталкиваемся с одновременными правками.
В таком случае первая попавшая на сервер правка записывается как обычно, а следующая, если она оказывается устаревшей, сравнивается с логом событий для определения изначальных целей пользователя. (Чаще всего все сводится к обновлению позиций символов.) Затем алгоритм, с видом якобы «именно такого результата и хотел пользователь», добавляет новую операцию, будто git-rebase в реальном времени.
С закрытием Google Wave я перенес OT модель в ShareJS. В то время node ощущался новым и странным, и если я правильно помню, ShareJS я запустил еще до релиза npm. Простой совместный редактор затребовал всего лишь тысячу строк кода, и на демонстрации демо-версии я совместно отредактировал документ в браузере и в приложении.
По своей сути, OT это приукрашенный цикл for() с несколькими функциями помощи для обновления смещения символов. На практике OT прост, легко понятен, быстро вводится в работу и работает отлично. (10-100 тысяч операций в секунду в неоптимизированном javascript, 1-20 миллионов в оптимизированном C). Лог событий может тратить памяти больше обычного, однако при желании его можно урезать, правда объединить особо давние правки не получится. Для глобального назначения операций потребуется централизованный сервер, однако у большинства систем уже есть такой сервер или база данных, не правда ли?
Значимая проблема OT это зависимость от централизованного сервера. Задумывались ли вы когда-нибудь, почему при разрешении доступа к документу Google Docs через социальные сети вы сталкивались со странным сообщением вида «Этот документ перегружен и его редактирование отключено»? Причина (на мой взгляд) в следующем: когда вы открываете документ, для обработки всех его правок выбирается один конкретный сервер, и когда на документ набрасывается толпа пользователей, системе приходится очень постараться чтобы не перегрузить сервер.
Обойти эту проблему можно несколькими способами: помимо подокументного шардинга (как в Google Docks) можно вносить правки через цикл retry в обход транзакций базы данных, благодаря чему проблема сериализации взваливается на плечи все той же базы данных (в такой манере работают Firepad и ShareDB).
Тем не менее, OT не идеален. Мы хотели заменить электронную почту на Wave, но почта поддерживает объединения, одна цепочка писем может растягиваться на множество компаний, и все это как-то успешно работает. К тому же, в отличие от сообщений в Facebook, электронную почту можно разослать упомянутым в графе «копия» компаниям. Если мы хотим чтобы Wave заменил почту, ему также потребуется функционал передачи сообщений без выхода во внешнюю сеть, например, когда я отсылаю письмо своему коллеге за соседним столом. Но как можно реализовать все это поверх OT? У нас кое-как получилось настроить такой процесс, но он оказался слишком сложным и полным ошибок: мы создали схему, в которой каждый wave протокол настраивал дерево wave серверов для передачи операций в обе стороны, но она так до конца и не заработала. Чуть менее десяти лет назад на Wave Protocol Summit я дал презентацию по вопросу создания и настройки подобной сети, но, несмотря на всю мою подготовку и все предварительные проверки, строгое следование каждому шагу на самой презентации провалилась, и сеть так и не заработала. Я до сих пор не знаю, почему это произошло, но что бы это ни были за ошибки, в общедоступной версии их вряд ли когда-либо исправляли, слишком уж все это было сложно.
Как я уже упомянул, основной алгоритм Wave был создан довольно давно, в 1995 году, и я даже не припомню, чтобы у меня в то время дома был интернет. С тех пор исследователи неустанно трудились над улучшением работы OT, и в самом многообещающем направлении они пользуются CRTD (Conflict-Free Replicated data types). Такой подход несколько отличается от обычного и позволяет редактировать файлы в реальном времени без необходимости центрального сервера. В презентации Мартина их работа описана лучше, чем я бы смог о них рассказать, поэтому я опущу детали.
Люди не первый год спрашивают мое мнение по поводу CRTD, и всегда мой ответ звучит в следующем ключе:
Со всей своей критикой я игнорировал CRDT, но тем самым игнорировал соответствующую литературу, и к своему удивлению пропустил тихое и незаметное улучшение CRDT. В своей презентации (она более чем стоит вашего внимания) Мартин адресует основные моменты:
Аргументация за скорость меня не убедила, поэтому для проверки идеи я самостоятельно реализовал и протестировал CRDT на Rust через B-дерево с использованием идей из automerge. В ней недоставало функционала (удаление символов, конфликты), однако она оказалась в состоянии обрабатывать 6 миллионов правок в секунду. (Каждая итерация проводила 2000 правок в пустой документ двумя чередующимися пользователями, что в целом занимало по 330 микросекунд, или 6.06 миллиона правок в секунду.) Таким образом, CRDTs действительно улучшились и разница в скорости между ними и OT теперь даже меньше чем между Rust и Javascript.
Все эти правки уже долгое время лежат в разделе «в скором будущем» в ветке производительности automerge, но в конце концов automerge не единственный CRDT. Y.js показывает себя достойно и в своих тестах с легкостью обходит текущую версию automerge. Ему недостает интересующего меня функционала, но в целом конечно проще поправить существующую реализацию, чем создавать новый алгоритм.
Меня очень беспокоит достижение прогресса. Что было бы странным не иметь в ходу через сотню лет? Очевидно, у нас будет редактирование в реальном времени, но я уже не уверен в его реализации через OT и всю проделанною мною в этом отношении работу, что не может меня не печалить.
В наши дни JSON и REST используются повсеместно. Допустим, через 15 лет так же повсеместно будет использоваться совместное редактирование в реальном времени. Каков будет аналог у JSON в плане совместного редактирования для легкого переноса в свой проект? В этом славном будущем нам потребуется высококачественная реализация CRDT, поскольку для некоторых приложений OT попросту не будет работать, создать через него версию GIt в реальном времени или простую вариацию Google Wave уже не получится. Но если у нас уже есть хорошая реализация CRDT, нужна ли нам еще и реализация OT? Я считаю, что нет, ведь перенести весь функционал из OT в CRDT не составит труда (включая, между прочим, операции урезания), тогда как обратное неверно. Умные люди со мной не согласны, но, по моему мнению, при наличии у нас хорошего, быстрого CRDT для каждого языка, нужда в OT отпадет полностью.
Одно из преимуществ OT заключается в удобной реализации в централизованных системах – как и большинство современных приложений – но так же хорошо в них реализуются и распределенные алгоритмы. (Взгляните на Github например.) На мой взгляд, высококачественный CRDT на wasm окажется быстрее, чем реализация OT на JS. А если вас беспокоят только централизованные системы, помните: ограничения OT привели Google к проблемам скалирования в Google Docs.
Так что, как мне кажется, сейчас самое время переходить на небольшой и быстрый CRDT. Академическая работа по большей части уже проделана, дело осталось за успешными реализациями.
Меня все меньше и меньше волнует мир централизованных приложений. Приложения взаимодействуют с моими данными, на моих устройствах, и пора бы уже этим приложениям реагировать на такие связи соответствующим образом. Я хочу, чтобы мой ноутбук и мой телефон могли передавать друг другу данные по wifi, а не через загрузку моих данных на серверы в другой стране. Особенно если эти серверы финансируются соревнующимися за мое внимание рекламными гигантами.
С философской точки зрения, когда я редактирую документ в Google Doсks, мой компьютер спрашивает у Google разрешение на редактирование файла (поскольку если по какой-то причине сервер говорит «нет», я теряю все мои правки). Для сравнения, при
В общем, пришло время прощаться с операционным преобразованием. Мы прекрасно провели это время вместе, из всего мной написанного код операционного преобразования был одним из самых непростых и интересных. Ты умен и удивителен, OT, но CRDT может то, что ты не сможешь никогда. И я нужен CRDT. Я думаю, за несколько хороших реализаций мы сможем достичь чего-то по-настоящему особенного.
Я оплакиваю весь мой вложенный за эти годы в OT труд, но OT более не вписывается в мое видение будущего. CRDT позволит нам проще и быстрее пересоздать Wave и создавать приложения с отношением к пользователям как к цифровым гражданам, а не цифровым крестьянам. И это важно.
Настало время создавать.
Но начнем сначала.
В 2010 году я работал в Google Wave, где мы пробовали создать совместные редактируемые пространства для замены электронной почты, Google Docks, форумов, мгновенных сообщений и многих других однозадачных приложений. Среди моих инструментов мне особенно нравится среда общего назначения, нигде более как в Wave не сформулированный в то время функционал. В отличие от большинства других инструментов, среда общего назначения не навязывает собственный рабочий процесс, благодаря чему через нее можно планировать праздники, создавать вики-проекты, играть с друзьями в настольные игры, назначать рабочие собрания и много чего еще.
Изнутри совместное редактирование Wave работает поверх операционного преобразования (Operational Transform, OT), и в то время им пользовались уже не один день: наш алгоритм основывался на докладе Jupiter 1995 года. Для каждого документа алгоритм хранит отдельный хронологический список изменений, «Набрать H в позиции 0», «набрать i в позиции 1» и так далее. В большинстве случаев пользователи меняют последнюю версию документа, и лог выглядит как последовательность изменений, однако при совместном редактировании мы сталкиваемся с одновременными правками.
В таком случае первая попавшая на сервер правка записывается как обычно, а следующая, если она оказывается устаревшей, сравнивается с логом событий для определения изначальных целей пользователя. (Чаще всего все сводится к обновлению позиций символов.) Затем алгоритм, с видом якобы «именно такого результата и хотел пользователь», добавляет новую операцию, будто git-rebase в реальном времени.
С закрытием Google Wave я перенес OT модель в ShareJS. В то время node ощущался новым и странным, и если я правильно помню, ShareJS я запустил еще до релиза npm. Простой совместный редактор затребовал всего лишь тысячу строк кода, и на демонстрации демо-версии я совместно отредактировал документ в браузере и в приложении.
По своей сути, OT это приукрашенный цикл for() с несколькими функциями помощи для обновления смещения символов. На практике OT прост, легко понятен, быстро вводится в работу и работает отлично. (10-100 тысяч операций в секунду в неоптимизированном javascript, 1-20 миллионов в оптимизированном C). Лог событий может тратить памяти больше обычного, однако при желании его можно урезать, правда объединить особо давние правки не получится. Для глобального назначения операций потребуется централизованный сервер, однако у большинства систем уже есть такой сервер или база данных, не правда ли?
Централизованные серверы
Значимая проблема OT это зависимость от централизованного сервера. Задумывались ли вы когда-нибудь, почему при разрешении доступа к документу Google Docs через социальные сети вы сталкивались со странным сообщением вида «Этот документ перегружен и его редактирование отключено»? Причина (на мой взгляд) в следующем: когда вы открываете документ, для обработки всех его правок выбирается один конкретный сервер, и когда на документ набрасывается толпа пользователей, системе приходится очень постараться чтобы не перегрузить сервер.
Обойти эту проблему можно несколькими способами: помимо подокументного шардинга (как в Google Docks) можно вносить правки через цикл retry в обход транзакций базы данных, благодаря чему проблема сериализации взваливается на плечи все той же базы данных (в такой манере работают Firepad и ShareDB).
Тем не менее, OT не идеален. Мы хотели заменить электронную почту на Wave, но почта поддерживает объединения, одна цепочка писем может растягиваться на множество компаний, и все это как-то успешно работает. К тому же, в отличие от сообщений в Facebook, электронную почту можно разослать упомянутым в графе «копия» компаниям. Если мы хотим чтобы Wave заменил почту, ему также потребуется функционал передачи сообщений без выхода во внешнюю сеть, например, когда я отсылаю письмо своему коллеге за соседним столом. Но как можно реализовать все это поверх OT? У нас кое-как получилось настроить такой процесс, но он оказался слишком сложным и полным ошибок: мы создали схему, в которой каждый wave протокол настраивал дерево wave серверов для передачи операций в обе стороны, но она так до конца и не заработала. Чуть менее десяти лет назад на Wave Protocol Summit я дал презентацию по вопросу создания и настройки подобной сети, но, несмотря на всю мою подготовку и все предварительные проверки, строгое следование каждому шагу на самой презентации провалилась, и сеть так и не заработала. Я до сих пор не знаю, почему это произошло, но что бы это ни были за ошибки, в общедоступной версии их вряд ли когда-либо исправляли, слишком уж все это было сложно.
Взлет CRTD
Как я уже упомянул, основной алгоритм Wave был создан довольно давно, в 1995 году, и я даже не припомню, чтобы у меня в то время дома был интернет. С тех пор исследователи неустанно трудились над улучшением работы OT, и в самом многообещающем направлении они пользуются CRTD (Conflict-Free Replicated data types). Такой подход несколько отличается от обычного и позволяет редактировать файлы в реальном времени без необходимости центрального сервера. В презентации Мартина их работа описана лучше, чем я бы смог о них рассказать, поэтому я опущу детали.
Люди не первый год спрашивают мое мнение по поводу CRTD, и всегда мой ответ звучит в следующем ключе:
Они аккуратны и я рад, что люди над ними работают, однако:
- Они медленные. Очень медленные. Например, на обработку сессии по редактированию академической статьи в 100 килобайт в реальном времени одним пользователем Delta-CRTD тратит почти шесть часов. (Тесты: внимание на B4.)
- Из-за особенностей работы CRTD объем документов растет бесконтрольно, например, для отображения документа в 100 килобайт automerge master занимает 83 мегабайта памяти. Эти данные просто лежат на диске, удалить их, похоже, нельзя, и для редактирования их необходимо загружать в память. (Потенциально automerge может вырасти до 1.1 гигабайта памяти.)
- Годами присутствующий в OT функционал отсутствует в CRDT, например никто еще не сделал CRDT с поддержкой /object move/ (перенос чего либо из одной части JSON дерева в другую). Такие процедуры требуются для приложений типа Workflowy, и OT с ними отлично справляется.
- CRDT сложны сами по себе и рассуждать о них непросто.
- У вас, по всей видимости, уже есть централизованный сервер/база данных.
Со всей своей критикой я игнорировал CRDT, но тем самым игнорировал соответствующую литературу, и к своему удивлению пропустил тихое и незаметное улучшение CRDT. В своей презентации (она более чем стоит вашего внимания) Мартин адресует основные моменты:
- Скорость: С использованием современных CRDT (Automerge / RGA или Y.js / YATA) применение операций становится доступным через логарифмический [log(n)] запрос. (Подробнее об этом ниже.)
- Размер: Столбчатое кодирование Мартина в состоянии хранить текстовый документ всего лишь в полутора-двукратном превышении размера по сравнению с исходным содержимым, о чем сам Мартин говорит в презентации на 54-ой минуте. В automerge соответствующий код еще не ввели, однако эти идеи уже есть вY.js, благодаря чему Y.js хранит наш 100 килобайтный документ как 160 килобайт на диске или 3 мегабайта в памяти. Прогресс налицо.
- Функционал: Есть как минимум теоретические возможности по реализации функционала через перемотку и проигрывание, однако этим еще никто не занялся.
- Сложность: Я полагаю, средний CRDT ненамного превысит аналогичную реализацию через OT. Мартин сумел создать крохотную, медленную версию automerge всего на сотню строк.
Аргументация за скорость меня не убедила, поэтому для проверки идеи я самостоятельно реализовал и протестировал CRDT на Rust через B-дерево с использованием идей из automerge. В ней недоставало функционала (удаление символов, конфликты), однако она оказалась в состоянии обрабатывать 6 миллионов правок в секунду. (Каждая итерация проводила 2000 правок в пустой документ двумя чередующимися пользователями, что в целом занимало по 330 микросекунд, или 6.06 миллиона правок в секунду.) Таким образом, CRDTs действительно улучшились и разница в скорости между ними и OT теперь даже меньше чем между Rust и Javascript.
Все эти правки уже долгое время лежат в разделе «в скором будущем» в ветке производительности automerge, но в конце концов automerge не единственный CRDT. Y.js показывает себя достойно и в своих тестах с легкостью обходит текущую версию automerge. Ему недостает интересующего меня функционала, но в целом конечно проще поправить существующую реализацию, чем создавать новый алгоритм.
Изобретая будущее
Меня очень беспокоит достижение прогресса. Что было бы странным не иметь в ходу через сотню лет? Очевидно, у нас будет редактирование в реальном времени, но я уже не уверен в его реализации через OT и всю проделанною мною в этом отношении работу, что не может меня не печалить.
В наши дни JSON и REST используются повсеместно. Допустим, через 15 лет так же повсеместно будет использоваться совместное редактирование в реальном времени. Каков будет аналог у JSON в плане совместного редактирования для легкого переноса в свой проект? В этом славном будущем нам потребуется высококачественная реализация CRDT, поскольку для некоторых приложений OT попросту не будет работать, создать через него версию GIt в реальном времени или простую вариацию Google Wave уже не получится. Но если у нас уже есть хорошая реализация CRDT, нужна ли нам еще и реализация OT? Я считаю, что нет, ведь перенести весь функционал из OT в CRDT не составит труда (включая, между прочим, операции урезания), тогда как обратное неверно. Умные люди со мной не согласны, но, по моему мнению, при наличии у нас хорошего, быстрого CRDT для каждого языка, нужда в OT отпадет полностью.
Одно из преимуществ OT заключается в удобной реализации в централизованных системах – как и большинство современных приложений – но так же хорошо в них реализуются и распределенные алгоритмы. (Взгляните на Github например.) На мой взгляд, высококачественный CRDT на wasm окажется быстрее, чем реализация OT на JS. А если вас беспокоят только централизованные системы, помните: ограничения OT привели Google к проблемам скалирования в Google Docs.
Так что, как мне кажется, сейчас самое время переходить на небольшой и быстрый CRDT. Академическая работа по большей части уже проделана, дело осталось за успешными реализациями.
Что дальше
Меня все меньше и меньше волнует мир централизованных приложений. Приложения взаимодействуют с моими данными, на моих устройствах, и пора бы уже этим приложениям реагировать на такие связи соответствующим образом. Я хочу, чтобы мой ноутбук и мой телефон могли передавать друг другу данные по wifi, а не через загрузку моих данных на серверы в другой стране. Особенно если эти серверы финансируются соревнующимися за мое внимание рекламными гигантами.
С философской точки зрения, когда я редактирую документ в Google Doсks, мой компьютер спрашивает у Google разрешение на редактирование файла (поскольку если по какой-то причине сервер говорит «нет», я теряю все мои правки). Для сравнения, при
git push в github я всего лишь оповещаю github о правках в моем коде. Мой репозиторий все еще принадлежит мне, как и каждый бит данных и железо на котором они находятся, и именно так должны работать мои приложения. Благодаря таким людям как Мартин мы теперь знаем, как сделать хорошие CRDT. Однако до принятия local-first приложений за основу придется написать еще не одну строчку кода.В общем, пришло время прощаться с операционным преобразованием. Мы прекрасно провели это время вместе, из всего мной написанного код операционного преобразования был одним из самых непростых и интересных. Ты умен и удивителен, OT, но CRDT может то, что ты не сможешь никогда. И я нужен CRDT. Я думаю, за несколько хороших реализаций мы сможем достичь чего-то по-настоящему особенного.
Я оплакиваю весь мой вложенный за эти годы в OT труд, но OT более не вписывается в мое видение будущего. CRDT позволит нам проще и быстрее пересоздать Wave и создавать приложения с отношением к пользователям как к цифровым гражданам, а не цифровым крестьянам. И это важно.
Настало время создавать.