ShareJS или как сделать свой Google Wave c OT и NodeJS

  • Tutorial


После двух лет работы над OT (техника разрешения конфликтов при совместном доступе к данным) для Google Wave, Джозефу(Joseph Gentle) пришла в голову идея, что для тех, кто захочет сделать аналогичный продукт, потребуется ни чуть не меньше времени. Чтобы как-то помочь этим людям и поделиться знаниями была написана библиотека ShareJS, представляющая собой реализацию OT на основе NodeJS. Также есть C-реализация.




Что такое OT?



OT — это Operational Transformation или Операционные Преобразования.
У нас есть данные и есть операции над этими данными. Операции приходят к нам по очереди. Вся суть в том, что перед тем, как выполнить себя над данными, операция сама изменяется согласно всем предыдущим операциям над текущими данными.

Наглядный пример из Википедии:




В начальный момент времени оба пользователя имеют строку 'abc', для которой одновременно создают две операции:
O1 = Insert[0, «x»] (вставить символ «x» в позиции «0»)
O2 = Delete[2, «c»] (удалить символ «c» в позиции «2»)

В зависимости от очередности выполнения данных операций, результат будет разный.
Если O2, O1, то 'abc' -> 'ab' -> 'xab'
Если O1, O2, то 'abc' -> 'xabc' -> 'xac'

Как бы нам в обоих случаях получить одинаковый результат 'xab'? Преобразовывать операции, учитывая предыдущие изменения? Как бы это выглядело при OT?

O2: 'abc' -> 'ab'
OT: O1 Insert[0, «x»] -> O1` Insert[0, «x»]
O1`: 'ab' -> 'xab'
В данном случае операции O1 и O1` идиентичны (Insert[0, «x»]) ибо предыдущая операция O2 была над символами в позиции больше, чем позиция для O1. Таким образом O2 не оказывает влияния на O1 и не изменяет ее.

O1: 'abc' -> 'xabc'
OT: O2 Delete[2, «c»] -> O2` Delete[3, «c»]
O2`: 'xabc' -> 'xab'
В данном случае OT учло, что до O2 уже была операция O1, которая вставила один символ перед позицией для O2 и по этому O2 следует удалять символ не с позиции 2, а с позиции 3. Вот и вся магия.

Подробнее про OT: wiki, FAQ

Типы данных



В OT многое зависит от типа данных. Ведь операции (а также операции на операциями o_O) разные для разных типов данных. Например, все операции со строкой в конечном итоге можно свести всего лишь к 3-м:
— Переместить каретку на позицию n
— Вставить строку n в текущую позицию
— Удалить n символов, начиная с текущей позиции
Или даже к двум:
— Вставить строку в позицию n
— Удалить m символов, начиная с позиции n

Нас прежде всего интересует тип данных json и там всё несколько сложнее, так как json может состоять из объектов, массивов, строк, чисел. Это всё разные типы данных. Мы уже видели, как это работает для строк. Для массивов похожая ситуация. Так же OT может разобраться с инкрементом числа. Сложнее с объектами: если два пользователя одновременно перезаписывают поле json-объекта, то невозможно учесть изменения от обоих пользователей для общего типа данных json. Одна из двух операций потеряется. Если это критично, вы можете создавать собственные типы данных, специфичные для вашего приложения.

Типы данных для ShareJS вынесены отдельным проектом OTTypes. В данный момент есть несколько реализаций для строки и json. В планах — rich-text тип данных.

Арихтектура



ShareJS состоит из серверной и клиентской частей. Часть кода (например, преобразование операций) изоморфна, то есть выполняется и на сервере и на клиенте. В роли хранилища операций используется LiveDB, состоящия из Mongo (данные) и Redis (кэш операций). Модель данных — документоориентированная — коллекции и документы. Каждый документ имеет тип данных и версию, которая инкрементируется при каждом изменении документа. Операции атомарны на уровне документа.
Клиент выполняет несколько синхронных операций. Они группируются (setTimeout(sendToServer, 0);), сжимаются (объединяются последовательные одинаковые, удаляются те, которые нейтрализуют действие друг друга) и отправляются всем скопом на сервер.
Если версия данных операции, соответсвует актуальной версии данных в бд, то операция применяется, если нет, то сервер пытается найти историю промежуточных операций сначала в Redis, затем в Mongo (по умолчанию также хранилище всех операций). Операция преобразуется, согласно промежуточным операциям и применяется к данным. Само выполнение операций происходит последовательно (транзакция) в Redis (Lua script), где еще раз проверяется актуальность версии данных, если версия уже не актуальна, то круг повторяется заново.
С помощью Redis PubSub ловятся события изменения данных и промежуточные операции рассылаются всем подписанным клиентам, где соответсвенно применяются.
Такая модель позволяет иметь с одной стороны консистентные данные, с другой высокую скорость и масштабируемость.

LiveDB можно реализовать и в другом виде. Главное чтобы хранилище поддерживало транзакции и события (PubSub). Например, Foundation DB отлично подойдёт для этого.
В текущей реализации связь с Mongo обеспечивается по средствам адаптера, который можно переписать для любой другой базы данных.
По умолчанию вся история операций хранится в той же Mongo бд, что и данные. Можно ее вообще не хранить или хранить в другой бд.

Применение



ShareJS отлично подходит для создания real-time приложений совместного доступа к данным, таких как Google Wave, Google Docs и т.п.
Существует обертка над ShareJS — RacerJS. Это по сути красивый интерфейс для работы с данными. Возможно использование RacerJS с клиентскими фреймворками (AngularJS, Backbone и т.п.).
Для тех, кто хочет всё и сразу существует DerbyJS. Это full-stack изоморфный фреймворк, использующий RacerJS, как модель для работы с данными.

Вопросы по ShareJS, RacerJS, DerbyJS можно задавать в Stackoverflow Chat (Нужна репутация на Stackoverflow > 20)

Материалы по DerbyJS
Поделиться публикацией

Комментарии 16

    0
    Про ОТ есть еще русское вики.
      0
      Кстати как у ShareJS с RitchEdit? Или из коробки он работает только с plaintext?
        0
        Ходят слухи, что где-то в дебрях Share.js google groups было много споров по поводу можно ли реализовать Rich Text Editor на json типе данных. Вроде как решили, что нужен специальный тип данных для этого. Пока еще никто не запилил.
          +1
          Что-то я не вижу проблемы в формировании JSON документа для Rich редактора. Ну то есть, вот мы же можем все это отобразить в виде DOM, а значит ни что не мешает нам это представить в виде JSON.
            0
            Пожалуйста, не вводите людей в заблуждение.
            Там давно сделана интеграция с AceEditor и какими-то другими редакторами и JSON тип данных тоже сделан. github.com/share/ottypes/tree/master/lib вот все типы данных которые Джозеф успел реализовать. rich text в 0.6 из коробки работает.
            Вот примеры github.com/share/ShareJS/tree/master/prototype/public
              0
              Ткните пальцем, плиз, где там Rich Text, там вроде везде textarea, а это plaintext? (В AceEditor, кстати, по сути plain text, разукрашиваемый регэкспами)
                –1
                Мне кажется, что AceEditor вполне себе RichText.
                  0
                  Вы же пишете в нем только код (без всякой разметки). АйсЭдитор сам разукрашивает ваш код — вы не можете сделать сами что-то жирным, что-то наклонным, применить к абзацу стили.

                  Суля по всему, это вы вводите народ в заблуждение :)
                    0
                    Про эйсэдитор согласен.
                    JSON-тип для реализации Rich Text необязателен кмк, это более прямой путь для реализации мапа «rich текст -> HTML», но не единственный. Я могу использовать привычный язык разметки HTML для того, чтобы оформлять plain текст. Например, можно взять какой-нибудь wysiwig редактор, которых много, которые на выходе дают HTML и этого вообщем-то достаточно для работы с rich text.
                      0
                      > Например, можно взять какой-нибудь wysiwig редактор, которых много, которые на выходе дают HTML и этого вообщем-то достаточно для работы с rich text.

                      Это только при первом приближении так кажется. Дьявол в мелочах. Как-то нужно будет обрабатывать коллизии, если, например, два пользователя пометили пересекающийся текст несовместимыми тегами и т.д.
                        0
                        Я таки раскопал обсуждения rich text editor в Share.js google groups: тут и тут.
                          0
                          Ага, прочитал. Что-то там пока подзаглохло.
                          0
                          Задачу можно свести к задаче без коллизий, например ограничить множество тегов только совместимыми. Но в целом я понимаю, что это путь ограничений и не тру вей.
                            0
                            кстати несовместимости надо будет решать и в JSON типе, они там автоматически сами не разрешатся. То есть в любом случае вам придется решать как вы относитесь к пересекающимся диапазонам текста.
                              0
                              Полностью согласен.
                0
                ShareJS работает не только с plaintext, у него есть JSON API. То есть в теории ты можешь сформировать json документ, который будет олицетворять твой Rich элемент.

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

              Самое читаемое