Опубликовано здесь - http://docs.google.com/View?id=dgwv2xfq_12hkpwshcg

Операционные Трансформации в Google Wave

оригинал: Google Wave Operational Transformation

авторы: Дэвид Ванг (David Wang), Алекс Ма (Alex Mah)
перевод: HabraTranslation, Creative Commons BY

Waves (Волны) представляют собой серверные XML документы, позволяющие быстро и гладко вносить конкурентные правки.
Чтобы обеспечить такую живость, в качестве теоретической базы управления конкуренцией Wave использует Операционные Трансформации (ОТ).

Обзор

Совместное редактирование документа подразумевает возможность одновременного редактирования одного общего документа несколькими редакторами. Живое и конкурентное — обозначает возможность видеть изменения, которые вносят другие, буква за буквой.

Сейчас на рынке уже есть несколько продуктов, которые предлагают совместное редактирование документов. Некоторые из них предлагают конкурентное редактирование в реальном времени, такие как EtherPad и SubEthaEdit, но не позволяют редактировать текст с оформлением. Другие предлагают такую возможность, например GoogleDocs, но не обеспечивают живого гладкого конкурентного редактирования, так как не обходятся без проблем при совмещении правок.

Волна позиционируется как решение, которое предлагает одновременно и живое гладкое конкурентное редактирование, и поддержку документов с форматированным текстом.

В итоге Волны можно использовать для очень увлекательных бесед, где вы можете символ за символом видеть, что набирают собеседники, как-будто вы беседуете в кафе. Это очень похоже на обмен мгновенными сообщениями, только тут вы ещё и можете видеть, что набирает собеседник, в живую. Волны также позволяют прочувствовать и новый уровень продуктивности совместного редактирования документов, где не придётся волноваться о том, как бы не наступить кому-то на пятки, и при этом по-прежнему иметь всю базовую функциональность текстового процессора: жирность, курсив, маркированные списки и заголовки.

Волны — это нечто большее, чем просто документы с форматированным текстом. По сути, базовая технология Wave обеспечивает возможность внесения живых конкурентных правок в XML документы, которые могут быть использованы для представления любого структурированного контента, включая служебные данные, совместно используемые клиентскими и серверными системами.

Для достижения этой цели Волны используют систему управления конкуренцией, основанную на Операционных Трансформациях.

Введение

Операционные Трансформации (ОТ) — это теоретическая основа для управления конкуренцией, которое исследовалась в контексте группового редактирования на протяжении более чем 10 лет. Этот документ не описывает базовую теорию ОТ и предполагает, что читатель понимает ОТ. Для теоретической подготовки читателю предлагается ознакомиться с документами в разделе ссылок.

Вкратце, ОТ в Волне делают общий документ доступным на всех сайтах, и позволяют любому пользователю редактировать любую часть документа в любое время. Операции локального редактирования производятся без задержек и блокировок. Удаленные операции (в отличие от локальных) перед выполнением трансформируются. Свобода от блокировок при ОТ делает локальное время реакции нечувствительным к сетевым задержкам. Эти свойства ОТ играют большую роль в формировании Оптимистичного Пользовательского Интерфейса. Оптимистичность пользовательского интерфейса заключается в том, что действия пользователя выполняются и отображаются для пользователя мгновенно, без ожидания принятия сервером.

Отправной точкой для создания Волны была статья "High-latency, low-bandwidth windowing in the Jupiter collaboration system". Как и описанная в документе система Jupiter, Волны реализует клиентскую и серверную часть системы ОТ. Читателю весьма рекомендуется ознакомиться с этим документом.

В системе Волны существует несколько важных объектов. Волна — набор Всплесков. Всплеск — это набор документов. Документ состоит из XML документа и некоторых аннотаций. Всплеск — это то место, где происходят конкурентные изменения. Всплеск — это объект, к которому применяются Операционные Трансформации.

Этот документ подробно опишет те расширения, которые Волна внесла в общую теорию ОТ, и как именно Волновые операции поддерживают документы с форматированным текстом. А ещё важнее то, что этот документ описывает — как мы спроектировали волновые операции так, чтобы трансформировать огромное количество операций эффективно, и как они делают эффективным просмотр любой части истории вейвлета.

Расширение Волной теории Операционных Трансформаций

Клиенты ждут подтверждения от сервера, прежде чем посылать новые операции

Резюмируя: по базовой теории ОТ, клиент может последовательно посылать операции на сервер так быстро, как сможет. Сервер может делать тоже самое. Это означает, что клиент и сервер могут проходить через пространство состояний к конвергентным результатам различными маршрутами Операционных Трансформаций, зависящими от того, когда именно они получат операции других участников. См. диаграмму ниже.

Когда у вас множество клиентов подключены к серверу, у каждой пары клиент-сервер есть свое пространство состояний. Одно из следствий такого подхода в том, что серверу необходимо заботиться о пространстве состояний для каждого подключенного клиента, что может потребовать много памяти. Также это усложняет серверный алгоритм, требуя от него преобразования клиентских операций между пространствами состояний.

Иметь простой и эффективный сервер очень важно для того, чтобы сделать Волну надежной и масштабируемой. С этой целью Волновые ОТ отходят от базовой теории ОТ в том, что требуют от клиентов ожидать подтверждение от сервера, прежде чем посылать следующие операции. То, что сервер подтвердил операции клиента, означает, что сервер уже преобразовал операции клиента, применил их к серверной копии Вейвлета и разослал преобразованную операцию остальным подсоединенным клиентам. Во время ожидания подтверждения клиент кэширует локальные операции и отсылает их позже все вместе.

В дополнение к подтверждениям, клиент может вычислить возможный маршрут ОТ в пространстве состояний сервера. Мы называем это вычисленный серверный маршрут. Таким образом клиент может отправлять операции на сервер, которые уже находятся на маршруте ОТ сервера.

Это даёт важный плюс — серверу необходимо отслеживать единственное пространство состояний, являющееся историей операций, которые он применил. Когда сервер получает операцию клиента, ему остаётся только преобразовать её относительно истории операций, применить преобразованную операцию и затем разослать её остальным.

Одним из недостатков такого изменения получается то, что клиент будет видеть пакеты операций, произведённые другим клиентом в течение интервала времени, в среднем соответствующего одному полному циклу обмена с другими клиентами. Однако мы надеемся на то, что полученные от этого изменения преимущества окажутся стоящими этого.

Восстановление

Сверх ОТ, Волна так же имеет возможность восстанавливаться после коммуникационного сбоя или отказа сервера. Это особенно важно в среде крупных масштабируемых систем.

Контрольные Суммы

ОТ требует, что бы все клиенты и сервер были способны преобразовывать и выполнять операции одинаково. В качестве дополнительной гарантии, что результирующие XML документы будут идентичными, ОТ Волны также передаёт контрольные суммы документов XML вместе с операциями и подтверждениями. Это позволяет клиентам быстро обнаруживать ошибки и восстанавливаться после них, заменяя поврежденное содержимое свежими копиями с сервера.

Волновые Операции

Волновые операции бывают операциями над документом (для изменения XML документов), и операциями не над документом. Операции не для документов предназначены для задач типа добавления или удаления участника во Всплеске. Мы сосредоточимся здесь на операциях над документом, как наиболее важных в Волне.

Нелишне отметить, что XML документ в Волне может рассматриваться как одна операция над документом, которая может быть применена к пустому документу.

В этом разделе будет также описано, каким образом волновые операции остаются весьма эффективными даже при большом количестве преобразований.

Поддержка XML документов

Волна использует потоковый интерфейс для операций над документами. Это аналогично XMLStreamWriter или SAX-обработчику. Операция над документом состоит из упорядоченной последовательности изменений документа. Эти изменения применяются последовательно, по мере последовательного прохода по документу.

Организация операций над документом в таком стиле упрощает написание функции преобразования и функции комбинирования, рассматриваемых далее.

В Волне каждый 16-битный символ Юникода (используется в javascript, JSON, и строках в Java), начинающий или завершающий тэг XML документа называется элементом. Интервалы между элементами называются позициями. Позиция 0 располагается перед первым элементом. Операция над документом может содержать изменения, связанные с позициями. Например: изменение "Skip" определяет сколько позиций пропустить вперед в XML документе перед применением следующего изменения.

Волновые операции над документом также поддерживают аннотации. Аннотация — это некоторые метаданные, связанные с диапазоном элементов, заданным начальной и конечной позициями. Это чрезвычайно полезно для описания форматирования текста или предложений при синтаксической проверке, так как совсем не требует усложнения базового формата XML документа.

Волновые операции над документом состоят из следующих компонентов изменений:

пропуск (skip)
вставка символов (insert characters)
вставка начала элемента XML (insert element start)
вставка конца элемента XML (insert element end)
вставка начала анти-элемента XML (insert anti-element start)
вставка конца анти-элемента XML (insert anti-element end)
удаление символов (delete characters)
удаление начала элемента XML (delete element start)
удаление конца элемента XML (delete element end)
удаление начала анти-элемента XML (delete anti-element start)
удаление конца анти-элемента XML (delete anti-element end)
установка атрибутов XML (set attributes)
изменение атрибутов XML (update attributes)
открытие аннотации (commence annotation)
завершение аннотации (conclude annotation)

Вот более полный пример операции над документом:

skip 3
insert element start with tag "p" and no attributes
insert characters "Превед Медвед!"
insert element end
skip 5
delete characters 4

Из него можно увидеть, как именно XML документ может быть целиком представлен одной операцей.

Функция Преобразования

Представление операций над документом с использованием интерфейса потока (stream) имеет тот плюс, что делает простой их последовательную обработку.

Преобразователь операций работает, беря два потока изменений из операций на входе, одновременно их обрабатывая, и выдавая в потоки двух операций на выходе. Такая потоковая обработка гарантирует, что преобразование пары даже очень больших операций будет всё равно эффективным.

Комбинирование и Преобразование большого числа операций

Операции над документом спроектированы таким образом, что они могут быть скомбинированы вместе, и такая комбинация двух любых операций, которые могут быть скомбинированы вместе, само по себе является одной операцией.

Кроме того, алгоритм комбинирования работает с операциями как с линейными потоками, обеспечивая свою эффективность.

Операция комбинирования спроектирована так, чтобы удовлетворять следующим требованям.

Во-первых, комбинация B⋅A имеет такое свойство, что (B⋅A)(d)=B(A(d)) для всех документов, к которым может быть применена A. Это требование вытекает из определения комбинации.

Второе требование такое, что при таких A,B,X,A',B',X' и X'', что
transform(A,X) = (A',X') и transform(B,X') = (B',X'')
должно быть верным, что
transform(B⋅A,X) = (B'⋅A',X'')
и при таких A,B,X,A',B',X' и X'', что
transform(X,A) = (X',A') и transform(X',B) = (X'',B')
должно быть верным, что
transform(X,B⋅A) = (X'',B'⋅A')

В традиционных реализациях операционного трансформирования, если сервер и клиент рассинхронизируются и накопят с обеих сторон большое количество конкурирующих неподтвержденных операций, преобразование может оказаться дорогостоящим.

Если n — это число операций клиента, не подтвержденных сервером, а m — число операций сервера, не подтвержденных клиентом, то для разрешения проблем конкуренции в традиционных реализациях потребуется n*m преобразований.

Преобразование множества клиентских операций на множестве серверных операций может быть эффективно, если эффективны и комбинирование, и преобразование возникших в результате этого комбинирования операций.

Мы можем сделать комбинирование достаточно эффективным, чтобы сократить время выполнения преобразования до O(n log n + m log m), где n — общее количество операций клиента, а m — общее количество операций сервера.

Ссылки

"Operational transformation". в Википедии, свободной энциклопедии, 28 мая, 2009.

David A. Nichols, Pavel Curtis, Michael Dixon, and John Lamping:
High-latency, low-bandwidth windowing in the Jupiter collaboration system, UIST '95:
Протоколы 8-го ежегодного симпозиума ACM по Пользовательскому интерфейсу и программным технологиям, стр.111-120. ACM, 1995.