Несколько недель назад я смотрел выступление Мартина Клеппманна о его подходе к редактированию в реальном времени с помощью структур CRDT (Conflict-Free Replicated Data Type, бесконфликтные реплицированные типы данных, которые можно реплицировать на много узлов и обновлять параллельно без координации между узлами — прим. пер.) и меня охватило глубокое отчаяние. Может, вся моя работа в течение последнего десятилетия устарела на фоне подхода Мартина. Он действительно хорош.
Давайте вернёмся немного назад.
Примерно в 2010 году я работал над Google Wave. Это была попытка создать совместно редактируемые пространства на замену электронной почты, Google Docs, веб-форумов, мгновенных сообщений и сотен других небольших приложений. У Google Wave было свойство, которое нигде не реализовали, и оно мне очень нравилось: это среда или носитель общего назначения (такой, как бумага). В отличие от многих других инструментов, он не навязывает вам свой собственный рабочий процесс. Вы можете использовать его для чего угодно: планирование праздников, редактирование вики, игра D&D с друзьями, планирование встречи и т. д.
Внутренне совместное редактирование Wave было построено поверх Operational Transform (OT). Мы использовали алгоритм, основанный на статье в журнале Jupiter от 1995 года. Он хранит хронологический список для каждого документа и каждого изменения. «Тип H в позиции 0». или «Тип a i в позиции 1» и т. д. Большую часть времени пользователи редактируют последнюю версию документа, а журнал операций — это просто список всех изменений. Но если пользователи редактируют совместно, то мы получаем параллельные правки. Когда это происходит, первая правка, поступающая на сервер, записывается как обычно. Если вторая правка устарела, мы используем журнал операций в качестве ссылки, чтобы выяснить, что на самом деле имел в виду пользователь (обычно это просто означает обновление позиций символов). Затем просто добавляем новую (отредактированную) операцию. Это как git-rebase в реальном времени.
Когда Wave закрыли, я реализовал модель OT в проекте ShareJS. Это было тогда, когда Node ещё считали новым и странным. Думаю, ShareJS работал ещё до запуска npm. Потребовалось всего около 1000 строк кода, чтобы запустить простой совместный редактор, и когда я впервые продемонстрировал его, то мы совместно редактировали документ в браузере из нативного приложения.
По своей сути OT представляет собой цикл for() с некоторыми хелперами для обновления сдвига символов. На практике это работает отлично, просто и понятно. Реализация быстрая (10-100 тыс. операций в секунду в неоптимизированном javascript. 1-20 млн операций в секунду в оптимизированном C). Единственная нагрузка на хранилище — это журнал операций, и вы можете сократить его, если захотите (хотя в таком случае потеряются очень старые правки). Нужен централизованный сервер для глобальных операций, но в большинстве систем и так есть централизованный сервер/БД, не так ли?
Главная проблема OT — зависимость от централизованного сервера. Вы когда-нибудь задумывались, почему после публикации в социальных сетях Google Docs показывает странное сообщение «Этот документ перегружен, поэтому редактирование отключено» (This document is overloaded so editing is disabled)? Думаю, причина в том, что когда вы открываете Google Docs, то выбирается один сервер, через который проходят все изменения. Когда приходит толпа из социальных сетей, Google приходится использовать кучу трюков, чтобы этот сервер не был перегружен.
Они могут использовать некоторые обходные пути. Кроме сегментирования по документу (как в Google Docs), вы можете редактировать его с помощью цикла retry для транзакций базы данных. Это переводит проблему сериализации на вашу БД (Firepad и ShareDB работают именно так).
Хотя это не идеально. Мы хотели, чтобы Wave заменил электронную почту, которая является федеративной по своей сути. В тред писем может быть включено несколько компаний, и всё это просто работает. И в отличие от Facebook Messenger, письма отправляются только тем компаниям, которые включены в CC. Если я отправлю письмо коллеге, оно не выйдет за пределы здания. Чтобы Wave заменил электронную почту, нам была нужна такая же функциональность. Но как это запустить поверх OT? Мы вроде как заставили OT работать, но он был сложным и глючным. В итоге мы получили схему, в которой каждая «волна» организует дерево серверов, а операции передаются вверх и вниз по дереву. Но это никогда не по настоящему не работало. Я выступал на саммите Wave Protocol Summit всего 10 лет назад и объяснял, как это работает. В тот день я буквально шаг за шагом выполнял нужные действия, но сделанная вживую версия не сработала. Я до сих пор понятия не имею, почему. Каковы бы ни были ошибки, вряд ли их исправили в открытом исходном коде. Всё это слишком сложно.
Вы же помните, что алгоритм Wave был изобретён в 1995 году. Это довольно давно. Кажется, в 1995 году у меня дома даже не было интернета. С тех пор исследователи занимались улучшением OT. В самых перспективных работах использовались CRDT (бесконфликтные реплицированные типы данных). CRDT подходят к проблеме несколько иначе, позволяя редактирование в реальном времени без центрального источника правды. В своём выступлении Мартин объясняет их работу лучше меня, так что я опущу детали.
Много лет люди спрашивали, что я о них думаю, и я всегда отвечал примерно так:
Они классные, и я рад что продолжается их разработка, но:
Я сделал все эти критические замечания и отверг CRDT. Но при этом я перестал следить за последними научными статьями. И — сюрприз! CRDT потихоньку исправились. Выступление Мартина (которое стоит посмотреть) затрагивает основные моменты:
Насчёт скорости я был не полностью уверен, поэтому сделал простую реализацию CRDT на Rust с помощью B-дерева, используя идеи из automerge, и замерил время. У неё не хватает функций (удаление символов, конфликты). Но она обрабатывает 6 миллионов правок в секунду (на каждой итерации делается 2000 правок в пустом документе путём чередования пары пользователей, и это занимает 330 мкс. Так получается 6,06 миллиона правок в секунду). Таким образом, разница в скорости между CRDT и OT стала меньше, чем разница в скорости между Rust и Javascript.
Все эти улучшения довольно давно значатся, что «скоро появятся» в ветке automerge. Но automerge — не единственный приличный CRDT. Y.js работает хорошо и абсолютно превосходит текущую реализацию automerge в бенчмарках Y.js. В нём отсутствуют некоторые нужные функции, но обычно легче исправить реализацию, чем изобрести новый алгоритм.
Я очень люблю представлять будущее. Что обязательно будет через сто лет? Очевидно, у нас будет редактирование в реальном времени. Но я не уверен, что будут использоваться OT и вся моя работа. Из-за этого мне очень грустно.
В наши дни повсеместно используются JSON и REST. Скажем, через 15 лет совместное редактирование в реальном времени будет повсюду. Какой эквивалент JSON для редактирования в реальном времени, чтобы любой желающий мог просто заглянуть в свой проект? В светлом будущем нам понадобятся высококачественные реализации CRDT, потому что OT просто не будет работать для некоторых приложений. С помощью OT вы не сможете сделать аналог Git в реальном времени или простой Google Wave. Но с хорошей реализацией CRDT зачем нам OT? Весь функционал OT можно реализовать в CRDT (включая операции обрезки, кстати). Но обратное неверно. Возможно, умные люди не согласятся со мной, но если бы у нас был хороший, быстрый CRDT на всех языках, с интеграцией в интернете, то вряд ли нам вообще понадобился OT.
Одним из преимуществ OT является то, что он хорошо вписывается в централизованное программное обеспечение, то есть в большинство современных программ. Но распределённые алгоритмы тоже отлично работают в централизованном ПО (например, посмотрите на Github). И я думаю, что действительно высококачественный CRDT в wasm будет быстрее, чем реализация OT в JS. И даже если вы думаете только о централизованных системах, то подумайте о том, что из-за ограничений OT у Google возникают проблемы масштабирования в Google Docs.
Поэтому мне кажется, что пришло время сделать маленький и быстрый CRDT. Научные работы в целом готовы. Теперь нужно больше великолепных реализаций алгоритма.
Я всё больше ухожу из мира программ с центральным сервером. Подумайте, софт взаимодействует с вашими данными на ваших компьютерах. Ваше программное обеспечение должно отражать эти отношения. Я хочу, чтобы мой ноутбук и мой телефон обменивались файлами по WiFi. Не загружая все данные на серверы в другой стране. Особенно если эти серверы финансируются рекламодателями, которые платят за моё внимание.
С философской точки зрения, если я изменяю документ Google Docs, мой компьютер запрашивает у Google разрешение на редактирование файла (если серверы Google скажут «Нет», я потеряю свои изменения). Для сравнения, если я делаю
Так что я думаю, что пора попрощаться с Operational Transform. Мы отлично провели время. Код Operational Transform был одним из самых сложных и забавных кодов, которые я когда-либо писал. OT — ты умный и очаровательный, но CRDT делает то, на что ты не способен. И я нужен для развития CRDT. Думаю, хорошие реализации могут сделать что-то действительно особенное.
Я оплакиваю ВСЮ работу, которую проделал с ОТ за эти годы. Но ОТ уже не вписывается в моё представление будущего. Типы данных CRDT позволят сделать новую реализацию Wave, только проще и лучше. И они позволят написать софт, который рассматривает пользователей как граждан, а не крепостных. И это имеет значение.
Сейчас самое время создавать.
Давайте вернёмся немного назад.
Примерно в 2010 году я работал над Google Wave. Это была попытка создать совместно редактируемые пространства на замену электронной почты, Google Docs, веб-форумов, мгновенных сообщений и сотен других небольших приложений. У Google Wave было свойство, которое нигде не реализовали, и оно мне очень нравилось: это среда или носитель общего назначения (такой, как бумага). В отличие от многих других инструментов, он не навязывает вам свой собственный рабочий процесс. Вы можете использовать его для чего угодно: планирование праздников, редактирование вики, игра D&D с друзьями, планирование встречи и т. д.
Внутренне совместное редактирование Wave было построено поверх Operational Transform (OT). Мы использовали алгоритм, основанный на статье в журнале Jupiter от 1995 года. Он хранит хронологический список для каждого документа и каждого изменения. «Тип H в позиции 0». или «Тип a i в позиции 1» и т. д. Большую часть времени пользователи редактируют последнюю версию документа, а журнал операций — это просто список всех изменений. Но если пользователи редактируют совместно, то мы получаем параллельные правки. Когда это происходит, первая правка, поступающая на сервер, записывается как обычно. Если вторая правка устарела, мы используем журнал операций в качестве ссылки, чтобы выяснить, что на самом деле имел в виду пользователь (обычно это просто означает обновление позиций символов). Затем просто добавляем новую (отредактированную) операцию. Это как git-rebase в реальном времени.
Когда Wave закрыли, я реализовал модель OT в проекте ShareJS. Это было тогда, когда Node ещё считали новым и странным. Думаю, ShareJS работал ещё до запуска npm. Потребовалось всего около 1000 строк кода, чтобы запустить простой совместный редактор, и когда я впервые продемонстрировал его, то мы совместно редактировали документ в браузере из нативного приложения.
По своей сути OT представляет собой цикл for() с некоторыми хелперами для обновления сдвига символов. На практике это работает отлично, просто и понятно. Реализация быстрая (10-100 тыс. операций в секунду в неоптимизированном javascript. 1-20 млн операций в секунду в оптимизированном C). Единственная нагрузка на хранилище — это журнал операций, и вы можете сократить его, если захотите (хотя в таком случае потеряются очень старые правки). Нужен централизованный сервер для глобальных операций, но в большинстве систем и так есть централизованный сервер/БД, не так ли?
Централизованные серверы
Главная проблема OT — зависимость от централизованного сервера. Вы когда-нибудь задумывались, почему после публикации в социальных сетях Google Docs показывает странное сообщение «Этот документ перегружен, поэтому редактирование отключено» (This document is overloaded so editing is disabled)? Думаю, причина в том, что когда вы открываете Google Docs, то выбирается один сервер, через который проходят все изменения. Когда приходит толпа из социальных сетей, Google приходится использовать кучу трюков, чтобы этот сервер не был перегружен.
Они могут использовать некоторые обходные пути. Кроме сегментирования по документу (как в Google Docs), вы можете редактировать его с помощью цикла retry для транзакций базы данных. Это переводит проблему сериализации на вашу БД (Firepad и ShareDB работают именно так).
Хотя это не идеально. Мы хотели, чтобы Wave заменил электронную почту, которая является федеративной по своей сути. В тред писем может быть включено несколько компаний, и всё это просто работает. И в отличие от Facebook Messenger, письма отправляются только тем компаниям, которые включены в CC. Если я отправлю письмо коллеге, оно не выйдет за пределы здания. Чтобы Wave заменил электронную почту, нам была нужна такая же функциональность. Но как это запустить поверх OT? Мы вроде как заставили OT работать, но он был сложным и глючным. В итоге мы получили схему, в которой каждая «волна» организует дерево серверов, а операции передаются вверх и вниз по дереву. Но это никогда не по настоящему не работало. Я выступал на саммите Wave Protocol Summit всего 10 лет назад и объяснял, как это работает. В тот день я буквально шаг за шагом выполнял нужные действия, но сделанная вживую версия не сработала. Я до сих пор понятия не имею, почему. Каковы бы ни были ошибки, вряд ли их исправили в открытом исходном коде. Всё это слишком сложно.
Подъём CRDT
Вы же помните, что алгоритм Wave был изобретён в 1995 году. Это довольно давно. Кажется, в 1995 году у меня дома даже не было интернета. С тех пор исследователи занимались улучшением OT. В самых перспективных работах использовались CRDT (бесконфликтные реплицированные типы данных). CRDT подходят к проблеме несколько иначе, позволяя редактирование в реальном времени без центрального источника правды. В своём выступлении Мартин объясняет их работу лучше меня, так что я опущу детали.
Много лет люди спрашивали, что я о них думаю, и я всегда отвечал примерно так:
Они классные, и я рад что продолжается их разработка, но:
- Они медленные. В смысле, очень медленные. Например, Delta-CRDT почти 6 часов обрабатывает сессию редактирования в реальном времени одного пользователя, который набрал научную статью объёмом 100 КБ (вот бенчмарки — смотрите B4).
- Из-за принципа работы CRDT документы растут безгранично. Чтобы представить на диске этот документ размером 100 КБ, основной automerge занимает 83 МБ. Можно ли удалить эти данные? Скорее всего, нет. И эти данные не могут просто лежать на диске. Их нужно загрузить в память для обработки изменений (в этом случае automerge займёт до 1,1 ГБ памяти).
- У CRDT нет функций, которые давно есть у OT. Например, никто ещё не сделал CRDT, который поддерживает /object move/ (перемещение из одной части дерева JSON в другую). Это нужно для таких приложений, как Workflowy. OT прекрасно с этим справляется.
- CRDT сложные и о них трудно рассуждать.
- В любом случае у вас, вероятно, есть централизованный сервер или база данных.
Я сделал все эти критические замечания и отверг CRDT. Но при этом я перестал следить за последними научными статьями. И — сюрприз! CRDT потихоньку исправились. Выступление Мартина (которое стоит посмотреть) затрагивает основные моменты:
- Скорость: с современными CRDT (Automerge/RGA или y.js/YATA) операции выполняются поиском log(n) (подробнее ниже).
- Размер: столбчатая кодировка Мартина хранит текстовый документ с оверхедом всего 1,5-2x относительно контента. Мартин говорит об этом на 54-й минуте своего выступления. Код для этого ещё не включён в Automerge, но идеи реализованы в Yjs. Он может хранить тот же документ 100 КБ всего в 160 КБ на диске и 3 МБ в памяти. Гораздо лучше.
- Функции: есть, по крайней мере, теоретический способ добавить все функции с помощью «перемотки и воспроизведения», хотя никто ещё не реализовал этот вариант.
- Сложность: думаю, что нормальный CRDT будет больше, чем эквивалентная реализация OT, но не намного. Мартину удалось сделать крошечную, медленную реализацию automerge всего в 100 строках кода.
Насчёт скорости я был не полностью уверен, поэтому сделал простую реализацию CRDT на Rust с помощью B-дерева, используя идеи из automerge, и замерил время. У неё не хватает функций (удаление символов, конфликты). Но она обрабатывает 6 миллионов правок в секунду (на каждой итерации делается 2000 правок в пустом документе путём чередования пары пользователей, и это занимает 330 мкс. Так получается 6,06 миллиона правок в секунду). Таким образом, разница в скорости между CRDT и OT стала меньше, чем разница в скорости между Rust и Javascript.
Все эти улучшения довольно давно значатся, что «скоро появятся» в ветке automerge. Но automerge — не единственный приличный CRDT. Y.js работает хорошо и абсолютно превосходит текущую реализацию automerge в бенчмарках Y.js. В нём отсутствуют некоторые нужные функции, но обычно легче исправить реализацию, чем изобрести новый алгоритм.
Создавая будущее
Я очень люблю представлять будущее. Что обязательно будет через сто лет? Очевидно, у нас будет редактирование в реальном времени. Но я не уверен, что будут использоваться OT и вся моя работа. Из-за этого мне очень грустно.
В наши дни повсеместно используются JSON и REST. Скажем, через 15 лет совместное редактирование в реальном времени будет повсюду. Какой эквивалент JSON для редактирования в реальном времени, чтобы любой желающий мог просто заглянуть в свой проект? В светлом будущем нам понадобятся высококачественные реализации CRDT, потому что OT просто не будет работать для некоторых приложений. С помощью OT вы не сможете сделать аналог Git в реальном времени или простой Google Wave. Но с хорошей реализацией CRDT зачем нам OT? Весь функционал OT можно реализовать в CRDT (включая операции обрезки, кстати). Но обратное неверно. Возможно, умные люди не согласятся со мной, но если бы у нас был хороший, быстрый CRDT на всех языках, с интеграцией в интернете, то вряд ли нам вообще понадобился OT.
Одним из преимуществ OT является то, что он хорошо вписывается в централизованное программное обеспечение, то есть в большинство современных программ. Но распределённые алгоритмы тоже отлично работают в централизованном ПО (например, посмотрите на Github). И я думаю, что действительно высококачественный CRDT в wasm будет быстрее, чем реализация OT в JS. И даже если вы думаете только о централизованных системах, то подумайте о том, что из-за ограничений OT у Google возникают проблемы масштабирования в Google Docs.
Поэтому мне кажется, что пришло время сделать маленький и быстрый CRDT. Научные работы в целом готовы. Теперь нужно больше великолепных реализаций алгоритма.
Что дальше
Я всё больше ухожу из мира программ с центральным сервером. Подумайте, софт взаимодействует с вашими данными на ваших компьютерах. Ваше программное обеспечение должно отражать эти отношения. Я хочу, чтобы мой ноутбук и мой телефон обменивались файлами по WiFi. Не загружая все данные на серверы в другой стране. Особенно если эти серверы финансируются рекламодателями, которые платят за моё внимание.
С философской точки зрения, если я изменяю документ Google Docs, мой компьютер запрашивает у Google разрешение на редактирование файла (если серверы Google скажут «Нет», я потеряю свои изменения). Для сравнения, если я делаю
git push на github, я только уведомляю github об изменении моего кода. Моё хранилище принадлежит мне. Я владею всеми битами и всем железом, которое их хранит. Я хочу, чтобы так работало всё моё программное обеспечение. Благодаря таким людям, как Мартин, мы теперь знаем, как сделать хорошие CRDT. Но нужно написать ещё много кода, прежде чем софт с локальным хранилищем станет стандартом.Так что я думаю, что пора попрощаться с Operational Transform. Мы отлично провели время. Код Operational Transform был одним из самых сложных и забавных кодов, которые я когда-либо писал. OT — ты умный и очаровательный, но CRDT делает то, на что ты не способен. И я нужен для развития CRDT. Думаю, хорошие реализации могут сделать что-то действительно особенное.
Я оплакиваю ВСЮ работу, которую проделал с ОТ за эти годы. Но ОТ уже не вписывается в моё представление будущего. Типы данных CRDT позволят сделать новую реализацию Wave, только проще и лучше. И они позволят написать софт, который рассматривает пользователей как граждан, а не крепостных. И это имеет значение.
Сейчас самое время создавать.