После двух лет работы над 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 многое зависит от типа данных. Ведь операции (а также операции на операциями 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)
Автор: vmakhaev
