В качестве нового достижения алгоритмических исследований в области распределенных систем за последние годыCRDTБазовая библиотека открывает фантастические возможности для интерфейсных приложений:Имея только уровень модели с API, который почти так же прост, как магистраль, ваше приложение может естественным образом получить поддержку одновременных обновлений в сценариях совместной работы с несколькими людьми.. Что за черная магия стоит за этим? В этой статье мы надеемся показать максимальную производительность интерфейсной библиотеки CRDT.YjsНапример, показать всем интуитивноhow CRDT works.
(На рисунке показано сравнение производительности между Yjs и другими общедоступными библиотеками CRDT, Yjs соответствует синей линии внизу)
Эта статья начнется с инженерной реализации Yjs и расскажет, как типичная библиотека CRDT промышленного уровня реализует следующие возможности:
- моделирование структур данных
- разрешать конфликты параллелизма
- Возврат истории
- Синхронизировать состояние сети
В качестве популярного введения эта статья не будет содержать большого количества неясного исходного кода и не потребует много абстрактных математических знаний. Для чтения требуется только понимание основ компьютера с точки зрения структур данных.
Прежде чем представить внутренние концепции Yjs, как мы можем интуитивно понять, как используется библиотека CRDT? Yjs предоставляет пользователямYText,YArrayа такжеYMapи другие часто используемые типы данных (так называемыеShared Types, здесь они вместе называются YModel), который можно использовать непосредственно в качестве слоя модели приложения:
import * as Y from 'yjs'
// 应用中的全部协作状态均可在单个 YDoc 容器中承载
// 将该实例传入 WebSocket 等协议的 provider 后即可支持网络同步
const doc = new Y.Doc()
// 在 YDoc 上可以创建不同类型的顶层 YModel 实例
// 这里创建了一个顶层名为 root 的 YMap
const yRoot = doc.getMap('root')
// 也可以用 class 构造器来实例化独立的 YMap 等 YModel
// 可直接用 get set delete 等常见 API 对 YModel 增删改查
const yPoint = new Y.Map()
yPoint.set('x', 0)
yPoint.set('y', 0)
// YMap 的值也可以是 YMap，从而构造出嵌套的数据类型
yRoot.set('point', yPoint)
// YMap 中还可以存入 YText 等其他 YModel，形成复合的数据类型
const yName = new Y.Text()
yName.insert(0, 'Wilson Edwards')
yRoot.set('name', yName)
Этот API может показаться пресным на первый взгляд, но его настоящая сила заключается вConflict-free, то есть для верхнего слоя,Потенциальные конфликты состояний во время одновременных обновлений были автоматически разрешены Yjs.:
// 可以用 2 份独立的 YDoc 实例来模拟 2 个客户端
const doc1 = new Y.Doc()
const doc2 = new Y.Doc()
const yText1 = doc1.getText()
const yText2 = doc2.getText()
// 在某份 YDoc 更新时，应用二进制的 update 数据到另一份 YDoc 上
doc1.on('update', (update) => Y.applyUpdate(doc2, update))
doc2.on('update', (update) => Y.applyUpdate(doc1, update))
// 制造两次存在潜在冲突的更新
yText1.insert(0, 'Edwards')
yText2.insert(0, 'Wilson')
// CRDT 算法可保证两份客户端中的状态始终一致
yText1.toJSON() // WilsonEdwards
yText2.toJSON() // WilsonEdwards
Благодаря этим примерам API-интерфейса Yjs Surface мы уже должны понимать мощь CRDT. Вот действительно интересный вопрос:Как Yjs достигает этой возможности внутри компании??
моделирование структур данных
Когда дело доходит до «основополагающих принципов», многие ученики могут сразу начать представлять себе некий тонкий алгоритм разрешения конфликтов. Но прежде чем представить этот алгоритм, нам лучше ознакомиться с базовой структурой данных, которую Yjs использует для моделирования CRDT в инженерии:Двусвязный список.
В Yjs, будь то YText, YArray или YMap, данные в этих экземплярах YModel хранятся в двусвязном списке. Грубо говоря,Каждый элемент (или каждый элемент) в этом связанном списке уникальным образом записывает данные, измененные пользовательской операцией., в какой-то степени он похож на блокчейн. Можно предположить, что операции с YModel в приведенном выше примере в конечном итоге будут преобразованы в структурные преобразования, такие как добавление, вставка, разделение, слияние и т. д. в этом связанном списке. каждый в спискеitemОн будет сериализован, закодирован и распространен, и на основе гарантии алгоритма CRDT,Поскольку каждый клиент в конечном итоге получает все элементы, он может восстановить точное состояние документа независимо от порядка, в котором клиенты получили элементы..
Структура CRDT, реализованная на основе вышеуказанных средств, является одним из жанров CRDT, который можно назватьoperation-based CRDT, список CRDT или последовательность CRDT.
Очевидно, что в сценарии, когда несколько человек сотрудничают в режиме реального времени, время получения элемента не может быть гарантировано, каждый элемент должен иметь некоторую идентификацию, чтобы система однозначно определяла его положение на логической оси времени. Yjs присвоит каждому элементу уникальный идентификатор, его структураID(clientID, clock),Следующим образом:
// Yjs 中的 ID 源码，这样的朴素实现有利于引擎的 hidden class 优化
class ID {
constructor (client: number, clock: number) {
// 客户端的唯一 ID
this.client = client
// 逻辑时间戳
this.clock = clock
}
}
Здесь clientID и часы являются целыми числами, первое используется для уникальной идентификации клиента, соответствующего YDoc, а последнее принадлежитLamport timestampЛогическая временная метка , которую можно рассматривать как счетчик, увеличивающийся с нуля. Правила его обновления очень просты:
- Когда происходит локальное событие,
localClock += 1. - При получении удаленного события
localClock = max(remoteClock, localClock) + 1.
Этот, казалось бы, простой механизм на самом деле позволяет нам получать математически хорошо охарактеризованные структуры полного порядка. Это означает, что до тех пор, пока размер clientID сравнивается друг с другом, можно сравнивать отношения логической последовательности между любыми двумя элементами, что очень важно для обеспечения правильности алгоритма CRDT. Однако соответствующая математическая теория не находится в центре внимания этой статьи и не будет здесь подробно излагаться.
Понять, как работает этот список CRDT, можно на примере редактирования текста. В наивном случае без какой-либо оптимизацииЭта структура требует, чтобы мы моделировали каждую операцию вставки символа как элемент, то есть каждый символ несет логический идентификатор временной метки.:
В приведенном выше примереY A T A !Эти символы каждый соответствует элементу (или вставленной символ). Они проходятleftа такжеrightПоля объединяются вместе. вставка новых символовT, Yjs найдет соответствующую позицию вставки в связанном списке в соответствии с идентификатором элемента и вставит элемент, соответствующий новому символу, в связанный список. Кроме того, текст, постоянно добавляемый одним и тем же пользователем, также будет объединен вlengthОчень длинный отдельный элемент, чтобы избежать проблем с производительностью при большом количестве фрагментированных объектов.
Обратите внимание, что не все элементы будут сохраняться в связанном списке при частом добавлении и удалении документов. Однако, поскольку разрешение конфликтов CRDT должно опираться на метаданные исторических элементов,Мы не можем напрямую удалить элемент в истории, в лучшем случае мы можем удалить только содержимое YModel, соответствующее элементу.(Специально разработан для этого YjsGCобъект для замены устаревшей модели YModel пустой структурой, эквивалентной механизму надгробной плиты). Это поднимает следующий вопрос:Какую структуру данных следует использовать для хранения всех элементов документа??
Поскольку любой элемент можно отсортировать по идентификатору, одним из вариантов является сохранение всех элементов в сбалансированном двоичном дереве с использованием структуры данных, такой как B-дерево, с хорошей логарифмической сложностью времени вставки и удаления. Но на практике Yjs выбрал более простое и прямое решение,То есть назначьте плоский массив элементов каждому клиенту., соответствующая структура называетсяStructStore:
// 实践中可以用 doc.store.clients.get(doc.clientID) 查看
doc.store.clients: {
114514: [Item, Item, Item], // ...
1919810: [Item, Item, Item] // ...
}
В приведенной выше структуре каждый массив элементов сортируется по значению поля часов. Таким образом, требуется только один бинарный поиск, чтобы быстро найти элемент, соответствующий идентификатору. При получении удаленного элемента Yjs не только вставляет элемент в связанный список, но и вставляет его в соответствующую позицию в StructStore.
Следовательно, мы можем думать, что есть два способа индексации данных в Yjs:
- В соответствии с порядком структуры документа (т.document order) для моделирования двусвязного списка.
- В соответствии с логикой синхронизации (т.е.insertion order) смоделированный StructStore.
Понимание этой ментальной модели поможет нам отладить внутреннее состояние Yjs. Например, следующий код сгенерирует 3 элемента:
const yPoint = new Y.Map()
yRoot.set('a', yPoint) // item 1
yPoint.set('x', 0) // item 2
yPoint.set('y', 0) // item 3
Обратите внимание, что элемент эквивалентен переносуleft / right / IDКонтейнеры, такие как поля CRDT, где конкретные данные YModel (или AbstractType) будут храниться вitem.contentполе, помимоparentа такжеparentSubПоля используются для выражения отношения родитель-потомок вложенных структур, таких как YMap. Его общая структура выглядит следующим образом:
из-заitem.contentОн также может содержать любые данные AbstractType, такие как YMap, которые, естественно, поддерживают вложенность данных. На основе этой структуры цепочки YMap соответствует серии записей в это время, в которой каждый ключ использует последние данные на логической оси времени в качестве текущего состояния, а элементы, соответствующие другим более ранним состояниям в этом ключе, будут отмечены для удаления.
Чтобы оптимизировать локальную скорость вставки, Yjs также разработал дополнительный механизм кэширования. Если новый символ случайно вставляется в любом месте документа, то в список может быть вставлен символ, соответствующий новому элементу теоретически требуемой O(N) временной сложности. Но на самом деле большая часть вставки будет следовать за позицией курсора при окончательном редактировании пользователем. Поэтому Yjs по умолчанию кэширует 10 самых последних позиций вставки для быстрого сопоставления, в этой реализации это относится к списку пропуска (авторы считают, что кеширование было вдохновлено таблицей переходов) или маркером быстрого поиска.
Познакомившись с базовой структурой данных, мы можем лучше понять механизм разрешения конфликтов, разработанный Yjs.
разрешать конфликты параллелизма
Как библиотека CRDT разрешает конфликты? На самом деле, в приведенных выше противоречащих друг другу случаях, независимо от того, как устроены и объединены два абзаца Уилсона и Эдвардса, все они могут рассматриваться как улун. В настоящее время то, что является «правильным», уже не так важно.Достаточно гарантировать, что все узлы, которые получают сообщение, могут сознательно получить одно и то же состояние.- Это так называемая концепция конвергенции (согласованности конечного состояния).
Элементы в YJS образуют двусторонний связанный список. Но для того, чтобы правильно разрешать конфликты, его реализация включает не толькоleftа такжеrightполе, и эти два поля:
-
originПоле хранит левый узел элемента, когда он был вставлен. -
rightOriginПоле хранит правый узел элемента, когда он был вставлен.
Каждый элемент должен выполнять своюintegrateметод, основной алгоритм разрешения конфликтов использует здесь эти поля, и всего около 20 строк:
while (o !== null && o !== this.right) {
itemsBeforeOrigin.add(o)
conflictingItems.add(o)
if (compareIDs(this.origin, o.origin)) {
if (o.id.client < this.id.client) {
left = o
conflictingItems.clear()
} else if (compareIDs(this.rightOrigin, o.rightOrigin)) {
break
}
} else if (o.origin !== null && itemsBeforeOrigin.has(getItem(transaction.doc.store, o.origin))) {
if (!conflictingItems.has(getItem(transaction.doc.store, o.origin))) {
left = o
conflictingItems.clear()
}
} else {
break
}
o = o.right
}
Согласно статье об алгоритме YATA, используемом Yjs, основная идея приведенного выше кода состоит в том, чтобы обеспечить левое и правое соединения нового потенциально вставляемого элемента (то есть красная линия на рисунке ниже).не пересекают:
Однако почему корректность алгоритма гарантируется, пока пересечение не происходит? Это требует математического доказательства, в статье об алгоритме YATA есть более конкретные детали, которые выходят за рамки этой статьи.
Интересно, что конфликты на самом деле редко встречаются в практических приложениях. Поэтому, хотя приведенный выше код относится к ядру алгоритма библиотеки CRDT, он редко выполняется, а также может рассматриваться как гарантийный механизм, гарантирующий, что данные не будут повреждены из-за одновременных обновлений.
Возврат истории
Из приведенного выше введения мы можем обнаружить, что на самом деле все структуры элементов в документе могут храниться непрерывно, что, очевидно, имеет большое значение для исторических записей. По этой причине Yjs также поставляется сUndoManagerпредоставить готовые возможности управления историей. В моем предыдущем ответе ЧжихуТакже представлены рекомендации по проектированию модуля истории в совместном сценарии.. Однако ментальная модель, упомянутая в этом ответе, в основном полезна для вывода эффектов некоторых операций с продуктом на высоком уровне, а не для реализации инженерных деталей. Чтобы добиться максимальной производительности, в реализации Yjs было проведено больше оптимизаций. Вот краткое изложение.
Прежде чем обсуждать, как реализован UndoManager, нам нужно понять, как Yjs обрабатывает операции удаления. В Yjs каждый элемент можно пометить на удаление (путемitem.deletedгеттер для проверки), но больше в item не записывается информация об операции удаления:
- В элементе нет записи о том, когда он был удален или каким пользователем.
- Операции удаления также не регистрируются в StructStore.
- Локальные часы не увеличиваются после удаления.
Итак, где находится информация для смоделированных операций удаления? Yjs представляетDeleteSetКонцепция , которая может записывать все удаленные элементы за определенный период времени (или в определенной транзакции) на логической временной шкале, и эти данные также будут распространяться независимо от элемента. другими словами,Операция удаления в Yjs спроектирована так, чтобы быть независимой от структуры двусвязного списка.. В предыдущем введении к двусвязному списку элементов мы обсуждали CRDT на основе операций. Но при работе с операциями удаления дизайн Yjs эквивалентен более простомуstate-based CRDT.
Так называемый CRDT на основе состояния будет отправлять полное локальное состояние каждому клиенту и выполнять комбинированные вычисления независимо для каждого клиента. Для легкого состояния, такого как счетчики, такие CRDT, как правило, имеют более высокую полезность. Можно утверждать, что моделирование операций удаления в Yjs соответствует этой концепции.
В приведенном выше описании мы упомянулиtransactionКонцепция, это абстракция YJS для построения систем событий. Каждая корреспонденция обновления включает в себя два данных:
- Элемент, вставленный на этот раз, обновляется.
- На этот раз обновляется DeleteSet удаленного элемента.
Двоичные добавочные данные обновления, фактически распространяемые по сети, представляют собой сериализованную и закодированную транзакцию. Можно считать, что транзакция будет использоваться как для кодирования обновлений, так и для отмены соответствующей гранулярности повторных операций. Основываясь на приведенной выше структуре данных, можно обнаружить, что транзакцию можно отменить, выполнив две вещи:
- Помечает элемент, вставленный этой транзакцией, для удаления.
- Отмечает элементы, удаленные этим обновлением, для восстановления.
Поскольку этот процесс не требует добавления новых элементов, таким образом, непрерывные операции отмены-повтора теоретически эквивалентны просто непрерывному распространению облегченного набора DeleteSet. Из-за очень легкой структуры DeleteSet (например, в документе, который записывает процесс редактирования реальной пользовательской бумаги LaTeX)B4В эталонном наборе данных после 182 000 вставок и 77 000 удалений генерируется только 4,5 КБ DeleteSet), этот дизайн ближе к «абстракции с нулевыми накладными расходами», поскольку отмена-повтор не создает никаких неизвестных новых данных.
Однако я лично считаю, что, хотя эта конструкция может обеспечить более экстремальный эффект оптимизации, она также усложняет обслуживание. Например, проблема, которую было трудно исправить в UndoManager, заключалась в том, что «повторное выполнение может быть повторено и возвращено в исходное состояние в течение 3 последовательных отмен, а поля могут быть потеряны, если более 4 раз». Корень этой проблемы в том, что реализация в то время имела проблемы с логикой восстановления элемента и, возможно, не могла непрерывно перемещаться вправо, чтобы найти правильное положение элемента, который должен быть восстановлен. Хотя отдельные лица представили исправления для этой проблемыPR, но в процессе его расследования также есть много взлетов и падений. Если есть студенты, которые хотят реализовать свою собственную экспериментальную библиотеку CRDT, оптимизация на основе DeleteSet не должна быть возможностью, которую необходимо реализовать в первом прототипе.
Синхронизировать состояние сети
Хотя сама библиотека CRDT не имеет ничего общего с конкретным сетевым протоколом, в качестве полного набора прогрессивных решений Yjs также разработал поддерживающий сетевой протокол. Основные моменты этого раздела, связанные с внутренней реализацией Yjs, включают следующее:
- Весь документ Yjs может быть закодирован как данные обновления в форме Uint8Array, и Yjs также может десериализовать структуру объекта YDoc из двоичных данных. Транзакция для каждого обновления документа также вычисляет добавочные обновления для синхронизации, которые содержат item и DeleteSet, как описано ранее.
- Yjs находит логическую временную шкалу с помощью концепции вектора состояния.Эта структура данных на самом деле представляет собой набор записей, которые записывают всех клиентов в определенное время.
(client, clock)кортеж.
При синхронизации состояния документа Yjs делится на две фазы:
- Фаза 1: клиент может отправить свой собственный локальный вектор состояния, чтобы получить недостающие данные обновления документа от удаленного клиента.
- Этап 2: Удаленный клиент может использовать свои локальные часы для расчета объекта элемента, требуемого клиентом, и дополнительный код для создания минимальных данных обновления, содержащих все несинхронизированные состояния.
Теоретически мы можем поддерживать больше сетевых протоколов, кроме WebSocket для Yjs, и Yjs уже поддерживает его.DatЭто новый протокол для распределенной сети. Но контента, связанного с сетевым протоколом, нет в основном репозитории Yjs, вы можете обратиться кy-protocolsпроект.
Суммировать
На данный момент мы представили основные внутренние функции Yjs:
- Базовая структура данных на основе двусвязного списка и StructStore
- Параллельный механизм разрешения конфликтов на основе алгоритма YATA
- Отменить повтор на основе механизма DeleteSet и Transaction
- Механизм синхронизации на основе двухэтапного деления
Ограниченные личными возможностями, существует множество технических деталей, которые невозможно рассмотреть по отдельности в этой статье. Наконец, некоторые ценные ссылки перечислены:
- YATAВ этой статье представлен дизайн алгоритма Yjs с доказательством правильности.
- Yjs InternalsКлючевые внутренности Yjs задокументированы, многие из них полезны для этой статьи.
- Are CRDTs suitable for shared editingНесколько ключевых оптимизаций, которые он реализовал, были представлены автором Yjs Кевином Янсом.
- 5000x fater CRDTs: An Adventure in OptimizationЭто запись в блоге, написанная Сефом Джентлом, автором библиотеки OT ShareDB, в которой подробно анализируется процесс улучшения инженерной производительности CRDT.
- How Yjs works from the inside outЭто было длинное видео-интервью с Кевином, которое Сеф предложил узнать об Yjs, и оно было весьма поучительным.
- личныйD2Поделился и представил практику доступа к проектам Yjs.
Из-за отличной децентрализованной природы CRDT, стоящей за Yjs, у него может быть возможность стать некоторой формой внешней инфраструктуры в эпоху Web 3.0. Из этого случая мы можем почувствовать, что практическое применение результатов академических исследований не достигается в одночасье, а также зависит от большого количества конкретных инженерных деталей, обработки и целевой оптимизации, которые все еще не могут избежать базовых компьютерных знаний, таких как основные структуры данных и алгоритмы. . И по сравнению с классической OT, популярность CRDT в последние годы также может быть связана с потенциальной сменой парадигмы, что означает новые возможности для фронтенд-разработчиков. Я надеюсь, что эта статья может быть полезна заинтересованным студентам.