Путешествие во времени с графическими базами данных

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

Хотя ArangoDB может не иметь встроенной поддержки управления историей изменений графических данных, в этой статье мы покажем, как эффективно управлять ею для некоторых общих классов графов. Лучше всего то, что для этого не потребуются какие-либо новаторские идеи. Мы просто позаимствуем несколько инструментов и приемов из литературы по постоянным структурам данных и адаптируем их для обеспечения хорошей производительности в ArangoDB. Мы надеемся, что это поможет открыть новые способы использования всеми любимого хранилища данных, работающего на авокадо, и запустить некоторые полезные приложения. (Не знакомы с графовой базой данных? Пройди бесплатный курс)

Новичок в мультимоделировании и графиках? Ознакомьтесь с нашим бесплатным Курсом по графам ArangoDB.

Во-первых, немного мотивации

Прежде чем мы углубимся в это, вы можете спросить себя: «Зачем мне вообще сохранять историю изменений для графических данных?» Это справедливый вопрос.

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

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

Предупреждаем об ограничениях

Прежде всего, если вы знакомы с персистентными структурами данных, мы в первую очередь будем обсуждать механизмы частичной персистентности, а не более сложные полные или слитные настойчивость. Это означает, что мы будем говорить о приложениях, в которых вы можете читать любую версию данных, но можете обновлять только текущую версию. В какой-то степени вы можете внести изменения в старую версию данных, но для этого потребуется стереть существующее будущее с этой точки. (Подумайте об этом так: вы можете нажать «отменить» несколько раз и отредактировать эту версию, но как только вы внесете изменение, вы больше не сможете нажать «повторить».)

Во-вторых, не все эти методы будут работать для произвольных графических данных. В некоторых случаях мы будем ограничиваться ориентированными ациклическими графами (далее DAG). Проще говоря, все ребра имеют направление, и если существует путь от вершины u к вершине v, следующий за ребрами только в их прямом направлении, то не может быть прямого пути от v, который огибает обратно к u. Для получения дополнительной информации о группах обеспечения доступности баз данных см. Статья Википедии по этому вопросу с более точным определением и интересным обсуждением некоторых свойств и способов использования групп доступности баз данных. Это нормально, если ваше приложение содержит некоторые дополнительные данные, не относящиеся к DAG, в графе, но только до тех пор, пока нас интересует только сохранение данных ревизии для части DAG. В этом случае, вероятно, будет полезно хранить любые ребра, которые могут создавать циклы, в отдельных коллекциях ребер, для которых мы явно не храним историю изменений.

В-третьих, в некоторых случаях мы ограничимся приложениями, в которых мы можем разложить DAG на логически сгруппированные компоненты, которые сами по себе являются индуцированными деревьями. Игнорируя эти математические термины, это означает, что для каждой группы вершин, которую имеет смысл объединить как компонент в приложении, каждая вершина имеет не более одного входящего ребра из другой вершины в группе. Другой разговорный способ выразить это так: ни одна вершина не имеет нескольких родителей в своей собственной группе. На рисунке ниже мы изображаем DAG с тремя компонентами, T1, T2 и T3, каждый из которых является индуцированным деревом.

Рисунок 1 — Компоненты индуцированного дерева

Наконец, всякий раз, когда вы видите ∞ (символ бесконечности), это просто заполнитель для некоторого произвольно большого числа, обычно самого большого целого числа, которое может быть сохранено в любом представлении, которое мы используем. Например, внутри атрибута документа ArangoDB это число будет 253–1. Ввод этого везде сделал бы презентацию немного загроможденной и утомительной, поэтому я предпочитаю использовать ∞.

Теперь, со всем этим, давайте погрузимся!

Простой и мощный примитив для путешествий во времени.

На мгновение отвлечемся от того, как были сгенерированы данные на приведенной ниже диаграмме, и просто рассмотрим структуру и то, как мы можем ее пройти.

Рисунок 2 — Разбивка DAG по времени

Как вы могли заметить, каждое ребро в нашем графе G помечено диапазоном целых чисел в форме (a, b). Мы используем его для обозначения времени создания каждого ребра и времени его истечения. В нашем обычном формате JSON это можно смоделировать как {created: a, expired: b}. Это все данные, необходимые для включения квантования времени. Учитывая момент времени t, из которого мы хотим запросить наш граф G, мы можем легко отфильтровать, чтобы включить только ребра, которые были действительны в момент времени t. Используя параметр привязки @queryTime со значением t в приведенном ниже запросе, мы должны получить все допустимые пути.

ДЛЯ вершины, ребра, пути

IN 1..10 ИСХОДЯЩИЕ ‘вершины/A’ ГРАФИК ‘G’

ФИЛЬТР path.edges[*].created ВСЕ ‹= @queryTime AND path.edges[*].expired ВСЕ › @queryTime

Обратный путь

Предположим, мы выполняем этот запрос в момент времени 0. Мы должны получить доступ к [A, B, C, D, E]. В момент времени 3 мы должны быть в состоянии достичь [A, C, D, E, F, G, H].

Что кодируют вышеуказанные временные метки с точки зрения ревизий графа? По сути, мы создали граф в момент времени 0 с вершинами [A, B, C, D, E] и ребрами [(A, B), (A, C), (B , D), (C, D), (C, E)] каждый с диапазоном отметок времени (0, ∞). Затем в момент времени 1 срок действия ребра (A, B) истек, изменив диапазон отметок времени на (0, 1), и вставили F с ребром (A, F) и метки времени (1, ∞). Затем в момент времени 2 мы вставили G и H, а также ребра [(A, G), (G, D ), (G, E), (E, H)]) с отметками времени (2, ∞). В момент времени 3 мы добавили ребро (D, H) с отметками времени (3, ∞). В момент времени 4 мы воссоздали ребро (A, B) с отметками времени (4, ∞). В момент 7 срок действия ребра (D, H) истек, изменив временные метки на (3, 7), и, наконец, в момент времени 8 срок действия ребра (E, H) истек, изменив временные метки на (2, 8).

Изучая последовательность операций, вы можете заметить, что изначально мы используем заполнитель ∞ для метки времени expired, которая в конечном итоге перезаписывается для «удаления» объекта. Кроме того, мы никогда не меняем данные после их записи. Если мы хотим изменить атрибуты ребра, мы можем истечь срок действия оригинала и создать новую копию с желаемыми изменениями и соответствующими метками времени. Такое поведение, часто называемое копированием при записи, представляет собой мощную технику, которую мы более подробно рассмотрим в следующих разделах.

Подводя итог, мы использовали простые диапазоны временных меток, чтобы обеспечить разрезку времени в запросах, что создает удивительно убедительное впечатление о путешествии во времени. Мы можем запросить наши данные, как они есть сейчас. Мы можем запросить его, как если бы это было вчера в 12:01. Мы можем запросить его точно в то время, когда было сделано конкретное изменение.

Разве это не здорово?

Давайте отследим некоторые простые изменения

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

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

С этого момента мы будем предполагать, что не только ребра, но и вершины будут содержать метки времени в форме {created: a, expired: b}. В предыдущем разделе мы видели, что добавить ребро или вершину в нашу постоянную структуру очень просто, создав новое ребро или вершину соответственно в ArangoDB и установив для его атрибута
created текущее время, а expired — большое значение заполнителя. Точно так же его просто «удалить» в момент времени t, изменив expired со значения-заполнителя на t. Но что, если мы хотим изменить атрибуты ребра или вершины?

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

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

Рисунок 3 — Толстые края

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

Рисунок 4 — Толстые вершины

Обратите внимание, что для того, чтобы несколько версий одного и того же ребра или вершины были связаны друг с другом, вам придется включить некоторый атрибут постоянного идентификатора, например. id. Когда вы создаете копию объекта, просто оставьте этот атрибут прежним и позвольте ArangoDB автоматически сгенерировать новые значения _key и _rev. Для быстрого доступа вам нужно создать индекс по полю вашего постоянного идентификатора.

Насколько плохо все это копирование?

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

То же самое относится и к толстым вершинам. Копия вершины фактически свободна, хотя в долгосрочной перспективе она требует дополнительного места. С вершинами нужно быть осторожным: копирование вершины также требует копирования всех живых ребер. Это означает, что мы больше не ограничены постоянным числом операций над графом! Как насчет «суперузлов» с тысячами ребер? О-о!

Что теперь?

Логические абстракции и прокси-вершины в помощь

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

Каждая реальная вершина ArangoDB внутри логической группы будет иметь один и тот же постоянный идентификатор. У нас будет одна специальная вершина in-proxy и одна специальная вершина out-proxy. Все входящие ребра, предназначенные для логической вершины, будут направляться во внутренний прокси. Все исходящие ребра, исходящие из логической вершины, будут исходить из исходящего прокси. Внутри каждая версия данных вершинного документа будет храниться в реальной вершине, как и раньше, но у нас больше не будет множества ребер, соединяющих каждое из них с другими частями графа. Вместо этого каждая вершина данных будет иметь одно входящее ребро, соединяющее ее с входным прокси, и одно исходящее ребро, соединяющее ее с исходящим прокси. Эти два ребра будут помечены временными метками, идентичными меткам на вершине данных, которую они соединяют с прокси. На рисунке ниже показана преобразованная версия диаграммы из предыдущего примера.

Рисунок 5 — Преобразование логического прокси

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

Рисунок 6 — Логическая модификация вершины

Простая история: свершилось!

Объединив методы жирных вершин и ребер вместе с логической абстракцией вершин и прокси-вершинным трюком, мы теперь имеем простое отслеживание истории изменений для графов с постоянными затратами времени и пространства для каждой модификации. Миссия выполнена!

«Но подождите, — говорите вы, — а вы что-нибудь говорили о DAG и индуцированных деревьях?» Вы правы, я сделал. Методы, которые мы обсуждали до сих пор, работают (по крайней мере, для большинства) общих графов. Но ключевое слово в заголовке этого раздела — «простой». Эти методы позволяют нам выполнять типичную операцию «сохранения», внося изменения «на месте». Что, если вместо этого мы хотим сделать что-то вроде «сохранить как», внеся изменения в новую копию или ветку?

Очевидным подходом было бы просто создать копию всей структуры графа и перемаркировать ее каким-либо подходящим образом, чтобы отличить от оригинала. Надеюсь, это звучит как плохая идея — это много копирования!

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

Обработка изменений ветвления

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

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

Рисунок 7 — Базовое копирование пути

Предположим, у нас есть исходное дерево слева, и мы создали новую ветвь. Вместо того, чтобы копировать все дерево, мы просто будем использовать копирование пути, когда это необходимо. Если мы хотим внести изменение в вершину E после ответвления, мы создадим новую копию E2, а также новые копии любых предков. В этом случае мы должны создать новые копии C и A, помеченные соответственно C2 и A2. Мы создаем идентичные копии этих узлов, включая временные метки, поскольку они остаются логически неизменными. Что касается ребер, мы копируем любые внутренние ребра пути, ведущие к немодифицированным вершинам, чтобы они указывали на новые копии. Мы копируем любые ребра, выходящие из пути, так, чтобы они указывали на исходные вершины. Наконец, для измененной вершины E мы создаем копию ребра от его родительского пути к исходной вершине и истечение срока ее действия. Затем мы создаем новое ребро для копии E2, созданной в настоящее время. Обратите внимание, что мы также копируем любые ребра в потомки без изменений.

Теперь у нас есть исходное, немодифицированное дерево с корнем A, которое все еще можно прочитать в исходной ветви, а также новая версия дерева в новой ветви с корнем A2. Ключевым моментом здесь является то, что, поскольку все ребра в дереве идут от родителя к дочернему, и нет ребер, которые возвращаются вверх, мы можем реализовать модификацию, только изменив предков в дереве. Другими словами, обходчик, расположенный в D, не может видеть C или C2, и поэтому ему не нужно заботиться об изменениях. Это позволяет нам избежать копирования каких-либо вершин, кроме набора прямых предков вершин, которые мы хотим изменить.

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

ДЛЯ вершины

IN 1..∞ INBOUND ‘vertices/C’ GRAPH ‘G’

OPTIONS {bfs: true, uniqueVertices: global}

ВОЗВРАТ вершины

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

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

Обратите внимание, что это не ограничивает приложение от «редактирования через границы компонентов». Если компоненты A и B имеют общую зависимость от компонента C, и мы хотим внести изменения в C, которые обновят B, но не A, мы можем: сначала создать новую ветку для C, содержащую желаемые изменения. Затем создайте ссылку на новую версию из B (либо в новой ветке B, либо в существующей ветке с помощью обновления на месте в зависимости от политики приложения).

Курс Graph проведет вас от нулевых знаний об ArangoDB до продвинутых методов запросов к графам в AQL — языке запросов ArangoDB.
Пройти курс

Все вместе сейчас…

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

Рисунок 8 — Все вместе: оригинал

На диаграмме выше у нас есть три компонента T1 (состоит из [A, B, C, D, E]), T2 (состоит из [X, Y]) и T3 (состоит из [Q, R, S]). Первоначально каждый начинается с одной исходной ветви, обозначенной b1. Чтобы обратиться к корню ветви j компонента i, мы поддерживаем простой документ с тегом версии (Ti, bj) вне основной структуры графа. .

Рисунок 9 — Все вместе: после разветвления T1

Первое изменение, которое мы вносим, — это создание новой ветви (T1, b2) и изменение узла E. Нам нужно только скопировать путь к корневому узлу A, поэтому мы делаем копии E2, C2 и A2. . Новым корнем дерева в (T1, b2) является A2. Обратите внимание, что когда мы копируем логическую вершину для модификации, мы копируем всю внутреннюю историю изменений вершины. (Можно было бы сделать некоторые оптимизации, чтобы уменьшить это копирование, однако это усложняет обход, поэтому мы не будем углубляться в это в этой статье.)

Рисунок 10 — Все вместе: после разветвления T3

Следующее изменение, которое мы вносим, заключается в обновлении S, но только в отношении представления B T3. Для этого создадим новую ветку (T3, b2). Мы скопируем путь из S в его корневой компонент, Q, добавив новые узлы S2 и Q2. Теперь, поскольку T1 уже разветвлен, мы, вероятно, не хотим выполнять обновление до B на месте. Вместо этого мы создадим копию B1
, а также копию A с именем A1 и обновим нашу корневую метку на точку (T1, b1), чтобы указать на A1. Обратите внимание, что A и B больше не используются ни в одной ветви, и теперь срок их действия истек вместе с их инцидентными ребрами.

Рисунок 11 — Все вместе: после обновления Т2

Наконец, мы обновляем Y в T2, чтобы использовать новую ветвь (T3, b2) для его зависимости T3. Поскольку T2 не является разветвленным, мы можем безопасно внести эту модификацию на месте, используя наши ранее установленные методы.

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

В заключении…

Эта статья уже стала довольно длинной. Давайте закончим с этим, хорошо?

Созрел для пошива и настройки

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

Идеально подходит для Foxx

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

Поговори с нами

Мы в команде ArangoDB любим слышать о новых и интересных вещах, которые люди делают с нашей базой данных, поэтому расскажите нам, используете ли вы историю изменений для чего-то интересного! Если у вас возникли проблемы с пониманием того, как это работает, загляните в наш сообщество. И, конечно же, если вам нужна более глубокая помощь в моделировании данных, не стесняйтесь спрашивать о наших консультационных услугах.

Кредит, где кредит должен

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