На данный момент практически все криптовалюты, созданные на блокчейне сталкиваются с проблемой масштабируемости. В централизованном мире такие международные платежные системы, как Visa и MasterCard позволили миллиардам людей осуществлять практически моментальные платежи, и, пока блокчейн-разработчики не смогут решить вопрос масштабируемости — мы так и будем пользоваться Visa и ждать по 30-60 минут биткоин-платеж.
Если с безопасностью криптовалют все более-менее нормально, то с масштабируемости действительно беда. Многие энтузиасты слышали о таком протоколе Lightning network, который позволяет совершать молниеносные биткоин-платежи и при этом не разоряться на комиссиях. Эта технология решает ключевую проблему — время добычи блока, от чего собственно зависит скорость работы всей сети.
Предыстория DAG
Интеграция блокчейн-решений в различные рынки является главным событием в 2017 году. Демократы и критики бумажных денег начали ликовать, мол все — блокчейн и криптовалюты набирает обороты и уже скоро весь вся финансовая система будет децентрализована. Банковские учреждения и правительственные чиновники потеряют контроль над данными и средствами людей, а тем более управлять ими.
Не успев оправится от бума биткоина, как на рынок заходит Эфир со своими умными контрактами и dApps. Практически каждый мог запустить свое ICO и свой токен. А блокчейн-игра «CryptoKitties» не только затмила умы многих, но создала серьезные проблемы с транзакциями. Игра практически заблокировала сеть Ethereum, заполнила мемпул, а пользователи ждали ETH-платежи по 24 часа.
Вернемся немного назад. Во второй половине 2017 года стали появляться криптовалюты, работающие на технологии DAG, призванная решить все существующие проблемы масштабируемости и высоких комиссий. Вот почему сейчас новые блокчейн-проекты стараются перейти с блокчейна на DAG.
Некоторые разработчики заявили, что DAG — это так называемый блокчейн 3.0, который станет фундаментом для многих существующих проектов. Что же, хватит болтовни — давайте разберемся: Что из себя представляет DAG и какие существуют преимущества и недостатки этой технологии.
Что такое DAG?
DAG (Directed Acyclic Graph) — это тип распределенного реестра, отличающийся от привычного нам блокчейна структурой записей и асинхронностью. Это совсем не тип блокчейна и не модель достижения консенсуса, поскольку в DAG нет блоков.
Если блокчейн — это база данных, которая содержит информацию о всех транзакциях в формате блоков, то DAG — это своего рода механизм, в котором каждая новая транзакция ссылается на несколько предыдущих. В результате формируется «дерево» неподтвержденных и неизменных транзакций.
Преимущества технологии DAG
Криптовалюты на основе DAG
NANO (ранее известная как RaiBlocks) не так популярна, как IOTA, но стоит учитывать, что это первая криптовалюта в классическом виде технологии DAG. Также NANO одна из немногих криптовалют, что действительно позволяет осуществлять транзакций в режиме реального времени и без каких-либо комиссий.
Далее идет Byteball, который помимо своей масштабируемости может похвастаться экосистемой умных контрактов, с помощью которой предприятия могут хранить информацию, задолженности и различные права собственности. К примеру, с помощью Byteball вы сможете заключить смарт-контракт на покупку недвижимости с оплатой в монетах. Если по каким-то причинам ваша сделка расторгается, то ваши монеты автоматически отправляются обратно на ваш кошелек.
Fantom — очень крутая криптовалюта на основе DAG, способная обрабатывать около 300 тысяч транзакций в секунду с практически нулевой комиссией.
IOTA, NANO, Byteball и Fantom сейчас торгуются на крупнейших криптобиржах, имеют сплоченную команду разработчиков и с расчетом на долгосрочную перспективу являются достаточно успешными DAG-проектами.
А как насчет недостатков DAG? Вы удивитесь, но у DAG их попросту нет. Но это пока. Технология весь еще не обкатана и находится на стадии становления. Как только монеты на базе DAG начнут использовать миллионы людей — можно будет делать какие-то выводы. Пока что DAG — это всего ли хайп, который имеет все шансы вырасти в нечто большее.
Направленный ациклический граф (DAG)
Понравилась статья? Поделись:
Направленный ациклический граф (Directed acyclic graph, DAG) – это график, которые направлен и связывает остальные рёбра без циклов. Это значит, что невозможно преодолеть весь направленный граф, начав с одного ребра. Рёбра направленного графа идут только одним путём.
Направленный ациклический граф являет собой топологическую сортировку, где каждый нод находится в определённом порядке. Конструкция DAG состоит из вершин, соединяемых рёбрами. Основной алгоритм DAG называется топологическим распределением, это означает, что каждое ребро направлено от более раннего ребра к более позднему.
Содержание
Что такое Направленный Ациклический Граф? [ править ]
Поговорим о направленных ациклических графиках более подробно. Сейчас направленные ациклические графы – DAG очень популярны в криптосообществе. Прежде всего тем, что IOTA и другие проекты их используют. Вот как это работает.
Легко объяснить Directed Acyclic Graph поэтапно. На самом деле, всё так, как и у блокчейна. Когда вы разделяете это слово на «блок» и «чейн» (цепь), становится гораздо понятнее. Сделаем это и с DAG. Это график – да. Он ацикличен – то есть, ноды не связаны циклами. Следуя графику от нода к ноду, вы ни разу не перейдёте к одной и той же ноде дважды. Он также направленный – рёбра на направленном графике идут только в одну сторону.
Итак, Directed acyclic graph – это график, где рёбра идут в одном направлении, и он не имеет циклов – вы никогда не придёте к началу или к той же самой ноде.
Алгоритм направленного графа называется топологическим распределением. Каждое ребро всегда направлено от более раннего ребра к более позднему. DAG часто называют конкурентом блокчейна или даже следующим поколением блокчейна.
Блокчейн vs. Directed Acyclic Graph (DAG) [ править ]
На самом деле, блокчейн и DAG больше родственники, но в то же время и конкуренты. Дело в том, что оба эти понятия являются распределёнными реестрами. Блокчейн является линейным распределённым журналом, а направленные ациклические графики – без цепи блоков. В мире криптовалюты, блокчейн и распределённый реестр становятся синонимами, но это не совсем правильно – DAG – это реестры без блокчейна.
Преимущества DAG [ править ]
DAG имеют очевидные преимущества над блокчейном:
Недостатки Направленных Ациклических Графов [ править ]
Конечно, Directed Acyclic Graph – это не панацея для блокчейна и криптовалюты и имеет свои ограничения. Прежде всего, несмотря на миллион возможных транзакций, у DAG всё же есть лимиты. Кто знает, может быть, в будущем мы будем говорить о проблеме масштабируемости DAG. Ещё одно сомнение в том, что нет информации о защите от взлома системы в её алгоритме или конструкции.
Криптовалюты с DAG [ править ]
IOTA [ править ]
Сотрудничество IOTA и DAG привело к Tangle. Конструкция графика IOTA даже шире – согласно White Paper, он выглядит как направленный ациклический график в 3D. Каждой транзакции в Tangle нужно подтвердить любые две предыдущие транзакции, которые выбираются сетью случайно. Также, алгоритм данной криптовалюты, соединённый с DAG, сделал возможным создавать даже офлайн-части сети. При подключении к интернету эти блоки становятся частью общего «блокчейна». Также есть одно преимущество IOTA, не связанное с DAG – противодействие квантовых компьютеров из-за разных способов криптографии.
В конце мая IOTA Foundation представили кошелёк Trinity Mobile Wallet.
Byteball [ править ]
Криптовалютный проект Byteball пользуется преимуществами DAG, чтобы построить экосистему смарт-контрактов для быстрых платежей и хранения финансовых данный: валюты, права собственности, задолженности, акции и другое. Это не блокчейн-проект, основанный на конструкции DAG, уже работающий и имеющий хороший и удобный для пользователей кошелёк. Byteball хорош, когда речь заходит об одноранговых смарт-контрактов. Пользователи Byteball могут использовать безрисковые условные смарт-платежи: всё, что вам нужно – это установить условие, когда получатель получает деньги. Если это условие не выполнено, ваши деньги автоматически буду отправлены обратно вам – очень простой алгоритм, основанный на DAG. Например, Byteball позволяет купить или продать одноранговую страховку на своей платформе, используя смарт-контракты.
Учитывая потребности KYC/AML в сегодняшнем финансовом мире, хорошо, что Byteball даёт клиентам возможность присоединить свой адрес Byteball к их физическим лицам через сервис Jumio. Однако, в Byteball есть место и анонимности. Проект имеет две валюты – Bytes (GBYTE) и Blackbytes. Bytes – это широко используемая валюта на платформе Byteball, и все транзакции являются публичными. Blackbytes обеспечивают пользователям полную конфиденциальность, если это необходимо. Blackbytes – это наличная, неотслеживаемая валюта, чьи транзакции не видны в общественной базе данных. И последняя интересная вещь – Bytes доступны абсолютно бесплатно. Вам только нужно иметь биткоины (BTC) и привязать ваш биткоин-адрес к адресу Bytes!
Dagcoin (Дагкоин) [ править ]
Если вы уже провели собственное исследование о криптовалюте, использующей DAG, вы должны были найти что-нибудь о Dagcoin. Согласно фактам и информации из разных источников в интернете, (например, здесь, здесь и здесь), он выглядит как обман. Их страница на GitHub закрыта с предупреждением: «Dagcoin – это мошенническая финансовая пирамида, продвигаемая известными мошенниками» в заглавии. Вы также можете поискать дополнительную информацию о Dagcoin в сети самостоятельно.
Согласно информации выше, Dagcoin имеет несколько очевидных признаков мошеннического проекта. Но информации о расследованиях против него или о закрытии этого проекта нет.
Топологическая сортировка
Перевод статьи подготовлен в преддверии старта курса «Алгоритмы для разработчиков».
Топологическая сортировка для ориентированного ациклического графа (Directed Acyclic Graphs, далее DAG) — это линейное упорядочение вершин, для которого выполняется следующее условие — для каждого направленного ребра uv вершина u предшествует вершине v в упорядочении. Если граф не является DAG, то топологическая сортировка для него невозможна.
Например, топологическая сортировка приведенного ниже графа — «5 4 2 3 1 0». Для графа может существовать несколько топологических сортировок. Например, другая топологическая сортировка для этого же графа — «4 5 2 3 1 0». Первая вершина в топологической сортировке — это всегда вершина без входящих ребер.
Топологическая сортировка vs обход в глубину:
При обходе в глубину (Depth First Traversal, далее DFS) мы выводим вершину и затем рекурсивно вызываем DFS для смежных вершин. При топологической сортировке нам нужно вывести вершину перед ее смежными вершинами. Например, в данном графе вершина «5» должна быть выведена перед вершиной «0», и, в отличие от DFS, вершина «4» также должна быть выведена перед вершиной «0». Этим топологическая сортировка отличается от DFS. Например, DFS графа выше — «5 2 3 1 0 4», но это не топологическая сортировка.
Рекомендация: перед тем, как переходить к реализации алгоритма, попробуйте сначала разобраться с задачей на practice.
Алгоритм поиска топологической сортировки.
Для начала, рекомендуем ознакомиться с этой реализацией DFS. Мы можем модифицировать DFS так, чтобы в результате была получена топологическая сортировку графа. В DFS мы начинаем с подходящей вершины, которую сначала выводим, а затем рекурсивно вызываем DFS для ее смежных вершин. В топологической сортировке мы используем временный стек. Вершина не выводится сразу — сначала вызывается топологическая сортировка для всех смежных вершин, затем вершина помещается в стек. Только после обхода всех вершин содержимое стека выводится. Обратите внимание, что вершина помещается в стек только тогда, когда все смежные вершины (и их смежные вершины и т. д.) уже находятся в стеке.
Изображение ниже является иллюстрацией вышеупомянутого подхода:
Текст на изображении:
Лист смежности (G)
0 →
1→
2 → 3
3 → 1
4 → 0, 1
5 → 2, 0
Стек пустой
Шаг 1:
Топологическая сортировка (0), visited[0] = true
Список пуст. Больше нет рекурсивных вызовов.
Стек 0
Шаг 2:
Топологическая сортировка (1), visited[1] = true
Список пуст. Больше нет рекурсивных вызовов.
Стек 0 1
Шаг 3:
Топологическая сортировка (2),, visited[2] = true
Топологическая сортировка (3),, visited[3] = true
Вершина 1 уже посещена. Больше нет рекурсивных вызовов
Стек 0 1 3 2
Шаг 4:
Топологическая сортировка (4),, visited[4] = true
Вершины 0 и 1 уже посещены. Больше нет рекурсивных вызовов
Стек 0 1 3 2 4
Шаг 5:
Топологическая сортировка (5), visited[5] = true
Вершины 2 и 0 уже посещены. Больше нет рекурсивных вызовов
Стек 0 1 3 2 4 5
Шаг 6:
Вывод всех элементов стека сверху вниз
Ниже приведены реализации топологической сортировки. Пожалуйста, ознакомьтесь с реализацией DFT для несвязного графа и обратите внимание на различия между вторым кодом, приведенным там, и кодом, приведенным ниже.
Python
Сложность по времени: приведенный выше алгоритм это DFS с дополнительным стеком. Таким образом, сложность времени такая же, как и у DFS, которая равна O(V+E).
Примечание: также можно использовать вектор вместо стека. Если используется вектор, чтобы получить топологическую сортировку, необходимо выводить элементы в обратном порядке.
Топологическая сортировка в основном используется для составления графика работ из заданных зависимостей между ними. В компьютерных науках применяется для планирования команд, упорядочения ячеек для вычисления формулы при повторном вычислении значений формул в электронных таблицах, логического синтеза, определения порядка задач компиляции для выполнения в make-файлах, сериализации данных и разрешения символьных зависимостей в компоновщиках [2].
Статьи по теме
Ссылки
Пожалуйста, оставьте комментарий, если обнаружите ошибку, или если захотите поделиться дополнительной информацией по обсуждаемой теме.
Продвинутые структуры данных. Часть первая: Направленный ациклический граф
Всем привет! Уже на следующей неделе стартуют занятия в новой группе курса «Алгоритмы для разработчиков». В связи с этим, делимся с вами переводом совсем небольшого, но довольно интересного материала.
Я хотел начать эту серию статей со структуры данных, с которой все мы как разработчики, хорошо знакомы, но вполне возможно, что даже не представляем как она устроена.
«Направленный ациклический граф? Никогда об этом не слышал. Не думай, что все обо мне знаешь!», вы можете сказать, но именно этот граф делает возможным контроль версий. Да, Git представляет из себя ациклический граф. В этой статье я поделюсь с вами знаниями о направленных ациклических графах (Directed Acyclic Graphs, DAG), а затем покажу, как написать свой собственный.
Что такое DAG?
Так что это вообще значит? DAG – это однонаправленный граф, где ни один элемент не может считаться дочерним. Многие из нас знакомы со связными списками, деревьями и графами. DAG очень похож на первое и второе в реализации третьего.
Выглядит похоже на дерево, но не совсем
В самом минимальном виде у DAG есть 4 составляющих:
А теперь попишем код. Сначала создадим конструктор с двумя свойствами и назовем его DAG.
Создадим метод для добавления узлов. Видите, что я здесь сделал?
Как это работает? Объект vertex – это место, где происходит вся магия. Мы добавляем узел, объект с поступающими узлами и массив со всеми их именами, переменную типа Boolean, сигнализирующую о том, указывает ли узел на что-то или нет, и его значение. К этому мы перейдем попозже.
Пора отдать должное
Пока я изучал материалы для написания этой статьи, я прочел несколько замечательных сообщений от удивительно умных людей, и в итоге большая часть информации была получена от них. Часть теоретической информации я получил, изучив этот хорошо структурированный пост о DAG и контроле версий. Код, представленный здесь, вдохновлен исходниками emberjs и их авторами. А еще я многое почерпнул из других статей и сообщений о DAG в блогах множества великих людей.
Airflow Workshop: сложные DAG’и без костылей
Привет, Хабр! Меня зовут Дина, и я занимаюсь разработкой игрового хранилища данных для решения задач аналитики в Mail.Ru Group. Наша команда для разработки batch-процессов обработки данных использует Apache Airflow (далее Airflow), об этом yuryemeliyanov писал в недавней статье. Airflow — это opensource-библиотека для разработки ETL/ELT-процессов. Отдельные задачи объединяются в периодически выполняемые цепочки задач — даги (DAG — Directed Acyclic Graph).
Как правило, 80 % проекта на Airflow — это стандартные DAG’и. В моей статье речь пойдёт об оставшихся 20 %, которые требуют сложных ветвлений, коммуникации между задачами — словом, о DAG’ах, нуждающихся в нетривиальных алгоритмах.
Управление потоком
Условие перехода
Представьте, что перед нами стоит задача ежедневно забирать данные с нескольких шардов. Мы параллельно записываем их в стейджинговую область, а потом строим на них целевую таблицу в хранилище. Если в процессе работы по какой-то причине произошла ошибка — например, часть шардов оказалась недоступна, — DAG будет выглядеть так:
Для того чтобы перейти к выполнению следующей задачи, нужно обработать ошибки в предшествующих. За это отвечает один из параметров оператора — trigger_rule. Его значение по умолчанию — all_success — говорит о том, что задача запустится тогда и только тогда, когда успешно завершены все предыдущие.
Также trigger_rule может принимать следующие значения:
Ветвление
Для реализации логики if-then-else можно использовать оператор ветвления BranchPythonOperator. Вызываемая функция должна реализовывать алгоритм выбора задачи, который запустится следующим. Можно ничего не возвращать, тогда все последующие задачи будут помечены как не нуждающиеся в исполнении.
В нашем примере выяснилось, что недоступность шардов связана с периодическим отключением игровых серверов, соответственно, при их отключении никаких данных за нужный нам период мы не теряем. Правда, и витрины нужно строить с учётом количества включённых серверов.
Вот как выглядит этот же DAG со связкой из двух задач с параметром trigger_rule, принимающим значения one_success (хотя бы одна из предыдущих задач успешна) и all_done (все предыдущие задачи завершились), и оператором ветвления select_next_task вместо единого PythonOperator’а.
Макросы Airflow
Операторы Airflow также поддерживают рендеринг передаваемых параметров с помощью Jinja. Это мощный шаблонизатор, подробно о нём можно почитать в документации, я же расскажу только о тех его аспектах, которые мы применяем в работе с Airflow.
Вот как мы применяем Jinja в Airflow:
Приведу несколько примеров рендеринга параметров в интерфейсе Airflow. В первом мы удаляем записи старше количества дней, передаваемого параметром cut_days. Так выглядит sql c использованием шаблонов jinja в Airflow:
В обработанном sql вместо выражения уже подставляется конкретная дата:
Второй пример посложнее. В нём используется преобразование даты в unixtime для упрощения фильтрации данных на источнике. Конструкция «<:.0f>» используется, чтобы избавиться от вывода знаков после запятой:
Jinja заменяет выражения между двойными фигурными скобками на unixtime, соответствующий дате исполнения DAG’а и следующей за ней дате:
Ну и в последнем примере мы используем функцию truncshift, переданную в виде параметра:
Вместо этого выражения шаблонизатор подставляет результат работы функции:
Коммуникация между задачами
В одном из наших источников интересная система хранения логов. Каждые пять дней источник создаёт новую таблицу такого вида: squads_02122017. В её названии присутствует дата, поэтому возник вопрос, как именно её высчитывать. Какое-то время мы использовали таблицы с названиями из всех пяти дней. Четыре запроса падали, но trigger_rule=’one_success’ спасал нас (как раз тот случай, когда выполнение всех пяти задач необязательно).
Спустя какое-то время мы стали использовать вместо trigger_rule встроенную в Airflow технологию для обмена сообщениями между задачами в одном DAG’е — XCom (сокращение от cross-communication). XCom’ы определяются парой ключ-значение и названием задачи, из которой его отправили.
XCom создаётся в PythonOperator’е на основании возвращаемого им значения. Можно создать XCom вручную с помощью функции xcom_push. После выполнения задачи значение сохраняется в контексте, и любая последующая задача может принять XCom функцией xcom_pull в другом PythonOperator’е или из шаблона jinja внутри любой предобработанной строки.
Вот как выглядит получение названия таблицы сейчас:
Ещё один пример использования технологии XCom — рассылка email-уведомлений с текстом, отправленным из PythonOperator’а:
А вот получение текста письма внутри оператора EmailOperator:
Заключение
Я рассказала о способах ветвления, коммуникации между задачами и шаблонах подстановки. С помощью встроенных механизмов Airflow можно решать самые разные задачи, не отходя от общей концепции реализации DAG’ов. На этом интересные нюансы Airflow не заканчиваются. У нас с коллегами есть идеи для следующих статей на эту тему. Если вас заинтересовал этот инструмент, пишите, о чём именно вам хотелось бы прочитать в следующий раз.
