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