Эта статья выбрана из серии статей «Практика инфраструктуры Byte Beat».

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

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

1. Графоподобные структурированные данные широко распространены

Большую часть бизнес-данных всех продуктов ByteDance можно разделить на следующие три типа:

Информация о пользователе, пользователь и его отношения (подписки, друзья и т. д.);
контент (видео, статьи, реклама и т. д.);
Связь пользователя и контента (лайки, комментарии, ретвиты, клики по рекламе и т. д.).

Эти три типа данных связаны вместе, чтобы сформировать структурированные данные Graph.

Чтобы соответствовать онлайн-сценариям добавления, удаления, модификации и поиска социального графа, ByteDance разработала распределенную систему хранения графов — ByteGraph. Для приведенных выше данных структуры графа ByteGraph поддерживает модель данных направленного графа атрибутов, поддерживает язык запросов Gremlin и поддерживает гибкие и богатые интерфейсы записи и запросов.Пропускная способность чтения и записи может быть увеличена до десятков миллионов запросов в секунду с задержкой. миллисекунд. В настоящее время ByteGraph поддерживает почти все линейки продуктов ByteDance, такие как Toutiao, Douyin, TikTok, Xigua, Volcano и т. д. по всему миру. В этой статье будет сделано подробное введение с точки зрения применимых сценариев, внутренней архитектуры и анализа ключевых проблем.

ByteGraph в основном используется в онлайн-сценариях OLTP, а в автономных сценариях постепенно появляются требования к анализу и вычислениям данных графа. В начале 2019 года на саммите Gartner Data and Analytics Summit графы были включены в десятку основных тенденций в области данных и аналитики в 2019 году, и ожидается, что глобальное приложение для анализа графов будет быстро расти со скоростью 100 % в год и достигнет 8 миллиардов долларов в год. 2020. Поэтому наша команда также начала поддержку и практику в сценариях офлайн-вычислений на графах.

Далее будет представлена часть работы ByteDance в этой области из базы данных графов и расчета графов.

2. Внедрение графовой базы данных собственной разработки (ByteGraph)

С точки зрения модели данных внутренние данные графовой базы данных представляют собой ориентированный граф атрибутов, а его базовыми элементами являются вершина (Vertex), ребро (Edge) в графе и атрибуты, присоединенные к нему; как инструмент, интерфейс, предоставляемый графическими данными, полностью внешний, построен вокруг этих элементов.

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

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

Базы данных графов появились в 1990-х годах, и до недавнего времени они быстро развивались в соответствии с общей тенденцией взрыва данных, и расцвели сотни цветов; но большинство более зрелых баз данных в настоящее время сталкиваются с меньшими наборами данных и сценариями с низкой пропускной способностью доступа в традиционных сценариях. Отрасли, такие как Neo4j с открытым исходным кодом, представляют собой автономную архитектуру, поэтому в сценарии Интернета система обычно настраивается на основе существующей инфраструктуры: например, Facebook инкапсулирует систему Social Graph TAO на основе системы MySQL, который несет почти всю логику данных Facebook; сервис Social Graph построен на платформе; Weibo строит отношения между фанатами и подписчиками на основе Redis.

Сценарий онлайн-хранилища ByteDance Graph также имеет свои особенности, которые можно резюмировать следующим образом:

Массовое хранение данных: масштаб данных десятков миллиардов точек и триллионов ребер, а график соответствует степенному распределению, например, небольшое количество больших вееров V достигает десятков миллионов;
Огромная пропускная способность: самый большой кластер QPS достигает десятков миллионов;
Низкая задержка: требуется, чтобы задержка доступа pct99 была ограничена миллисекундами;
Больше читайте и меньше пишите: трафик чтения почти в сто раз больше, чем трафик записи;
Более легкие запросы, менее тяжелые запросы: 90% запросов — это запросы в пределах второй степени на графике;
Эволюция архитектуры аварийного восстановления: она должна поддерживать различные схемы развертывания аварийного восстановления, такие как аварийное восстановление «активный-резервный» и удаленное многоактивное восстановление между городскими сетями, глобальными сетями и межконтинентальными сетями со скачкообразной перестройкой байтов.

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

Поэтому в августе 2018 года мы начали долгий путь к базе данных графов с первой строки кода, начав с решения основной проблемы социальных отношений Douyin, и постепенно перешли к поддержке модели данных направленного графа атрибутов и поддержки написания , Универсальная система графовых баз данных, включающая атомарность и часть языка запросов графов Gremlin, которая реализована во всех продуктовых системах компании, мы называем ее ByteGraph. Ниже мы поделимся с вами нашей работой с моделью данных, архитектурой системы и другими частями.

2.2 Модель данных и API ByteGraph

модель данных

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

Например, как упоминалось выше, если вы хотите сохранить отношения пользователей в ByteGraph, первый шаг — абстрагировать пользователей как точки, а второй шаг — абстрагировать «отношения следования» и «отношения друзей» как ребра. Далее мы представим типы данных следующего ребра с уровня кода.

Точка (Вершина)

Точки являются основными элементами баз данных графов и обычно отражают статическую информацию. В ByteGraph точки содержат следующие поля:

- 点的id(uint64_t): 比如用户id作为一个点
- 点的type(uint32_t): 比如appID作为点的type
- 点的属性（KV 对）：比如 'name': string，'age': int, 'gender': male，等自定义属性
- [id, type]唯一定义一个点

Край

Ребро состоит из двух точек и типа ребра между точками. Ребро может описывать взаимосвязь между точками. Например, пользователь А следует за пользователем Б, что может быть описано следующими полями:

- 两个点（Vertex）: 比如用户A和用户B
- 边的类型(string): 比如“关注”
- 边的时间戳(uint64_t)：这个t值是业务自定义含义的，比如可以用于记录关注发生的时间戳
- 边属性（KV对）：比如'ts_us': int64 描述关系创建时间的属性，以及其他用户自定义属性

направление края

В модели данных ByteGraph ребра являются направленными, и в настоящее время поддерживаются 3 направления ребер:

- 正向边：如 A 关注 B(A -> B)
- 反向边：如 B 被 A 关注(B <- A)
- 双向边：如 A 与 B 是好友(A <-> B)

Сценарий с использованием примера псевдокода

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

Сценарий 1. Запишите следующее отношение A следует за B

// 创建用户A和B，可以使用 .property('name', 'Alice') 语句添加用户属性
g.addV().property("type", A.type).property("id", A.id)
g.addV().property("type", B.type).property("id", B.id)
// 创建关注关系 A -> B，其中addE("关注")中指定了边的类型信息，from和to分别指定起点和终点，
g.addE("关注").from(A.id, A.type).to(B.id, B.type).property("ts_us", now)

Сценарий 2. Запросите всех пользователей, на которых подписаны A и C.

Пользователь A заходит на страницу сведений о пользователе C и хочет увидеть промежуточные узлы второго уровня между A и C, например, A->B, B->C и B является промежуточным узлом.

// where()表示对于上一个step的每个执行结果，执行子查询过滤条件，只保留关注了C的用户。
g.V().has("type", A.type).has("id", A.id).out("关注").where(out("关注").has("type", C.type).has("id", C.id).count().is(gte(1)))

Сценарий 3. Запросить друзей друзей А (отношения второй степени)

// both("好友")相当于in("好友")和out("好友")的合集，
g.V().has("type", A.type).has("id", A.id).both("好友").both("好友").toSet()

2.3 Архитектура системы

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

На следующем рисунке показана внутренняя архитектура ByteGraph, где bg — это сокращение от ByteGraph.

Точно так же, как MySQL обычно можно разделить на два уровня: уровень SQL и уровень механизма, ByteGraph делится сверху вниз на уровень запросов (bgdb), уровень механизма хранения/транзакций (bgkv) и уровень дискового хранилища.Каждый уровень состоит из несколько уровней.Он состоит из экземпляра процесса. Среди них уровень bgdb и уровень bgkv развертываются смешанным образом, а уровень дискового хранилища развертывается независимо Мы подробно представляем ключевую структуру каждого уровня.

Слой запросов (bgdb)

Уровень bgdb такой же, как уровень SQL MySQL, и его основная работа заключается в анализе и обработке запросов на чтение и запись; среди них так называемая «обработка» может быть разделена на следующие три шага:

Проанализируйте оператор запроса Gremlin, отправленный клиентом, для создания плана выполнения;
И в соответствии с определенными правилами маршрутизации (такими как согласованное хеширование) найти узел хранения (bgkv), где находятся целевые данные, и отправить запросы на чтение и запись в плане выполнения на несколько bgkv;
Суммируйте и отфильтруйте результаты чтения и записи bgkv, чтобы получить окончательный результат и вернуть его клиенту.

Слой bgdb не имеет состояния, может масштабироваться по горизонтали и разработан на языке Go.

Уровень хранилища/механизма транзакций (bgkv)

Уровень bgkv состоит из нескольких экземпляров процесса, каждый из которых управляет подмножеством (сегментом/разделом) всех данных кластера.

Реализация и функции уровня bgkv в чем-то похожи на базу данных в памяти, обеспечивая высокопроизводительные функции чтения и записи данных.Его характеристики:

Различные интерфейсы: предусмотрены только интерфейсы чтения и записи «точка-в-край»;
Поддержка оператора pushdown: перемещая вычисление (оператор) в хранилище (bgkv), производительность чтения может быть эффективно улучшена;
1. Например: например, большой V набирал подписчиков в прошлом году, а bgkv поддерживает запрос последних 100 подписчиков, поэтому нет необходимости считывать все миллионы подписчиков.
Кэш-хранилище органично объединено: как кеш-уровень хранилища KV, оно обеспечивает функцию управления кешем и поддерживает сложные функции, такие как загрузка кеша, подкачка, кэширование, а также синхронизация дисков и асинхронная синхронизация.

Как видно из приведенного выше описания, производительность и эффективность использования памяти для bgkv очень критичны, поэтому он написан на C++.

Уровень дискового хранилища (кластер KV)

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

Как хранить графики в базе данных KV

Предыдущий раздел только что представил взаимосвязь между тремя уровнями внутри ByteGraph.Внимательные читатели, возможно, обнаружили, что снаружи ByteGraph является графическим интерфейсом, а нижний уровень зависит от хранилища KV, поэтому возникает вопрос: как хранить данные графа. миллионов болельщиков в А как насчет системы КВ?

В бизнес-сценариях ByteDance есть много сценариев с чрезвычайно высоким доступом и «плотностью данных», таких как большой V Douyin, популярные статьи и т. д., количество поклонников или лайков превысит 10 миллионов; магазин KV, есть надежда, что размер (количество байтов) KV-пары бизнес-стороны контролируется на уровне КБ, и желательно равномерен по размеру: при слишком большом значении путь ввода/вывода будет заполнен моментально, что не может быть гарантировано. Стабильность в сети; для особенно малых значений эффективность хранения относительно низка. Фактически, проблема неравномерного размера данных преследует многие бизнес-группы, и в сети часто происходят несчастные случаи.

Для Douyin big V с десятками миллионов вееров это эквивалентно исходящей степени десятков миллионов ребер в определенной точке графа.Он должен не только храниться, но и удовлетворять онлайн добавление, удаление и изменение на уровне миллисекунд Затем ByteGraph Как решить эту проблему?

Идея на самом деле очень проста, если подвести итог, то это использование гибкого метода агрегации ребер, чтобы сделать размер значения в хранилище KV однородным, что можно описать следующими четырьмя пунктами:

Вершина (Vertex) и все связанные с ней ребра образуют группу данных (Group); разные начальные и конечные точки принадлежат разным группам и хранятся в разных парах KV; например, фанаты пользователя A и пользователя B. Вентиляторы делятся на разные KV место хранения;
Для некоторой точки и ее исходящих ребер, когда число исходящих степеней относительно невелико (уровень KB), сериализовать все ее исходящие степени, то есть все конечные точки, в пару KV, которую мы называем методом хранения первого уровня ( описано позже);
Когда исходящая степень точки постепенно увеличивается, например, обычный пользователь постепенно вырастает в Douyin V, мы используем распределенное B-Tree для организации этих миллионов вееров, которые мы называем вторичным хранилищем;
Возможно одновременное и безопасное переключение между первичным и вторичным хранилищем в режиме онлайн;

Основной формат хранения

В первичном формате хранения есть только одна пара KV, кодировка ключа и значения:

-  key: 某个起点 id + 起点 type + 边 type
-  value: 此起点的所有出边（Edge）及其边上属性聚合作为 value，但不包括终点的属性

Вторичное хранилище (степень выхода точки больше порогового значения)

Если большой V сильно увеличивает вентиляторы, значение вентиляторов будет становиться все больше и больше, и идея решения этой проблемы также очень проста: разделить на несколько пар KV.

Но как его демонтировать? Метод ByteGraph состоит в том, чтобы разделить все исходящие степени и конечные точки на несколько пар KV, и все пары KV образуют логически распределенное дерево B. Ключ в KV указывает на, а не указатель памяти; B-дерево распределено, что означает, что узлы на всех уровнях, составляющих дерево, распределены по нескольким экземплярам кластера, а не по отдельным отношениям индекса. Конкретная взаимосвязь показана на следующем рисунке:

Среди них все B-дерево состоит из нескольких наборов пар KV, которые можно разделить на три типа данных в зависимости от отношения:

Корневой узел: Корневой узел, по сути, является ключом в системе KV, и его метод кодирования такой же, как у ключа в основном хранилище.
Метаданные:
- Метаданные — это, по сути, значение в KV, и они образуют пару KV с корневым узлом;
- Meta хранит несколько ключей PartKey, каждый из которых является ключом в паре KV, а соответствующие ему данные значения представляют собой данные Part, описанные ниже;
Данные детали
- Для вторичного формата хранения существует несколько частей, и каждая часть хранит атрибуты и идентификаторы назначения исходящих ребер части.
- Каждая часть является значением пары KV, и соответствующий ключ хранится в мета.

Из приведенного выше описания видно, что для точки и ее краевых данных со многими исходящими степенями (такими как большая V и ее вееры) в ByteGraph они хранятся как несколько KV, и перед лицом необходимости добавления , удаление, проверка и изменение — все это нужно выполнить бинарным поиском в B-дереве. По сравнению с одной парой KV для одного ребра или одной парой KV для всех ребер, организация B-Tree может эффективно выполнять некоторые динамические корректировки между усилением чтения и усилением записи.

Однако в реальном бизнес-сценарии вентиляторы будут динамически меняться: только что родившийся большой V быстро добавит поклонников, а какой-то большой V продолжит терять поклонников, поэтому метод хранения будет переключаться между первичным хранилищем и вторичным хранилищем, а B-Tree будет продолжать разделяться или объединяться, это приведет к сложным проблемам, таким как распределенные параллельные добавления, удаления, проверки, а также разделения и слияния.Если у вас есть возможность, вы можете поделиться этим интересным дизайном отдельно.

Отношения между ByteGraph и хранилищем KV аналогичны отношениям между файловой системой и блочным устройством.Блочное устройство отвечает за объединение ресурсов хранения и предоставление низкоуровневых интерфейсов чтения и записи.Файловая система организует метаданные и данные в различные деревья на блочное устройство Структура индекса и инкапсулирует богатый интерфейс POSIX для внешнего использования.

2.4 Углубленное обсуждение некоторых вопросов

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

Решения для чтения и записи данных Hotspot

Данные горячих точек широко распространены в онлайн-бизнесе ByteDance: видео горячих точек, статьи горячих точек, большие пользователи V, реклама горячих точек и т. Д. Данные горячих точек могут мгновенно появляться при большом количестве операций чтения и записи. В практике онлайн-бизнеса ByteGraph разработал полный набор копинг-решений.

горячее чтение

Сцены горячего чтения можно увидеть повсюду, как, например, собственно онлайн-сцена: горячее видео часто обновляется, проверяется количество лайков и т. д. В этом сценарии это означает, что доступ имеет сильную локальность данных, и частота попаданий в кеш будет очень высокой, поэтому мы разработали и внедрили многоуровневый механизм Query Cache и механизм пересылки горячих запросов, кеширование результатов запросов в bgdb уровень запросов. Производительность bgdb при чтении попаданий в кэш с одним узлом составляет более 20 Вт QPS, а несколько bgdb могут одновременно обрабатывать запросы на чтение из одной и той же точки доступа, поэтому общей «эластичности» системы для работы с точками доступа вполне достаточно.

горячая запись

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

Высокий конфликт блокировки строки: в настоящее время ByteGraph представляет собой модель транзакции с одной строкой только с блокировками структуры памяти Параллелизм этой блокировки составляет десятки миллионов в секунду, что в основном не является узким местом записи;
Дисковые IOPS заполнены:
- Понятие IOPS (количество операций ввода-вывода в секунду): существует верхний предел количества запросов на запись в секунду на диск.Значения IOPS у разных моделей твердотельных накопителей разные, но есть верхний предел. трафик записи превышает этот порог, запрос будет поставлен в очередь, весь путь данных будет заблокирован, задержка увеличится в геометрической прогрессии, и сервис станет недоступен.
- Решение Group Commit: Group Commit — это зрелое техническое решение для базы данных.Проще говоря, несколько запросов на запись объединяются в памяти bgkv для формирования пакета для записи в хранилище KV, тогда скорость записи, отраженная извне, равна BatchSize * IOPS. .

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

индекс графика

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

По умолчанию ByteGraph сортирует и сохраняет в соответствии с меткой времени (ts) на границе, поэтому эффективность запросов очень высока для следующих запросов:

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

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

2.5 Будущие исследования

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

От хранилища графов к базе данных графов: для системы баз данных ключевым вопросом является поддержка транзакций ACID. В настоящее время ByteGraph решает только атомарность и согласованность и вообще не затрагивает самую сложную изоляцию. Это очень важно. Китайская академия информационных и коммуникационных технологий выпустила технический документ о функциях внутренних графовых баз данных.Основываясь на этом стандарте, если мы хотим создать хорошо функционирующую систему «базы данных», мы все еще сталкиваемся с морем звезд;
Стандартный язык запросов к графам: в настоящее время индустрия языков запросов к базам данных графов еще не сформировала стандарт (GQL будет выпущен в 2020 г.) ByteGraph выбирает языковую систему Gremlin Apache, AWS и Alibaba Cloud, но в настоящее время поддерживает только подмножество. Больше поддержки синтаксиса и более глубокой оптимизации запросов не проводилось;
Эволюция архитектуры облачного хранилища: ByteGraph по-прежнему строится поверх хранилища KV, монополизируя все ресурсы физических машин; с точки зрения гибкого развертывания ресурсов, размещения операций и обслуживания и т. д., есть ли возможность изучить эволюцию другой архитектуры, от запроса к транзакции к дисковому хранилищу?Есть место для глубокой оптимизации вертикальной интеграции, которая также остается без ответа;
Теперь ByteGraph содержит большой объем онлайн-данных в сценарии OLTP, и эти данные также будут применяться для сложного анализа и сценариев графических вычислений, таких как рекомендации и контроль рисков. Это также обширное голубое океанское поле.

3. Введение и практика системы графовых вычислений

3.1 История технологии графовых вычислений

Введение в графические вычисления

Графовые базы данных сосредоточены на сценариях OLTP с транзакциями в качестве ядра, подчеркивая как добавления, удаления, так и изменения, а запрос часто включает в себя лишь небольшой объем данных в графе; хотя вычисление графа отличается от него, это решение крупномасштабная обработка данных графа. Для сценария OLAP анализ и расчет выполняются на всем графе. На следующем рисунке (цитата из основного доклада VLDB 2019 «Обработка графа: панорамный вид и некоторые открытые проблемы») показаны некоторые различия полей между графовыми вычислениями и графовыми базами данных.

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

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

пакетная система

Для крупномасштабной обработки данных мы напрямую думаем об использовании систем пакетной обработки, таких как MapReduce / Spark.В первые дни ByteDance многие предприятия использовали MapReduce / Spark для реализации графических алгоритмов. Благодаря широкому использованию систем пакетной обработки бизнес-студенты могут быстро реализовывать и запускать собственную алгоритмическую логику.

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

графовая вычислительная система

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

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

распределенная архитектура

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

вычислительная модель

В зависимости от объекта расчета модель расчета графических данных можно разделить наУзлоцентрическая вычислительная модель,Реберно-центрированная вычислительная модель,Модель вычисления центра подграфаЖдать.

Большинство систем графовых вычислений используют модель вычислений, ориентированную на узлы (здесь узел относится к точке на графе), которая исходит от Google Pregel.Основная идея заключается в том, что в процессе пользовательского программирования узел и его смежные ребра в граф используются в качестве входных данных.Преимущество этого заключается в простоте программирования. Типичные вычислительные модели, ориентированные на узлы, включают Pregel API, предложенный Pregel, GAS API, предложенный PowerGraph, и некоторые другие API.

Прегель новаторски предложил идею «думать как вершина». Пользователям нужно только написать логику обработки одного узла, и ее можно распространить на весь граф для итерационных операций. Описанный Прегелем PageRank показан в следующем фигура:

def pagerank(vertex_id, msgs):
    // 计算收到消息的值之和
    msg_sum = sum(msgs)
    // 更新当前PR值
    pr = 0.15 + 0.85 * msg_sum
    // 用新计算的PR值发送消息
    for nr in out_neighbor(vertex_id):
        msg = pr / out_degree(vertex_id)
        send_msg(nr, msg)
    // 检查是否收敛
    if converged(pr):
        vote_halt(vertex_id)

GAS API заключается в том, что PowerGraph делит логику обработки узла на три этапа Gather, Apply и Scatter, чтобы решить проблему степенных графов (небольшое количество узлов имеют очень высокую степень). При условии, что расчет удовлетворяет коммутативному закону и ассоциативному закону, с использованием модели GAS стоимость связи снижается с |E| до |V|, а PageRank, описанный GAS, показан на следующем рисунке:

def gather(msg_a, msg_b):
    // 汇聚消息
    return msg_a + msg_b

def apply(vertex_id, msg_sum):
    // 更新PR值
    pr = 0.15 + 0.85 * msg_sum
    // 判断是否收敛
    if converged(pr):
        vote_halt(vertex_id)

def scatter(vertex_id, nr):
    // 发送消息
    return pr / out_degree(vertex_id)

раздел графа

Для сверхбольших графов, которые не могут быть обработаны одной машиной, данные графа необходимо разделить на несколько подграфов и использовать методы распределенных вычислений, поэтому будет задействована проблема деления графа, то есть как разрезать весь граф на подграфы и назначать их на разные машины, выполняющие распределенные вычисления. Общие методы деления графаОбрезка кромкииМетод точечной резки (Vertex-Cut), его принципиальная схема выглядит следующим образом:

Метод обрезки ребер, как следует из названия, будет отрезан от середины ребра, узлы с обеих сторон будут распределены по разным разделам графа, и каждый узел появится в глобальном масштабе только один раз, но метод обрезки ребер может привести к тому, что ребро появится глобально дважды. Как показано на левом рисунке выше, между узлом A и узлом B есть ребро. Метод разрезания ребра будет резать между A и B. A принадлежит к разделу графа 1, а B принадлежит к разделу графа 2.

Правило точечного отсечения заключается в том, чтобы разрезать узел, и разные ребра на узле будут распределены по разным разделам графа, и каждое ребро появится только один раз в глобальном масштабе, но метод точечного отсечения приведет к тому, что узел появится несколько раз глобально. Как показано на правом рисунке выше, узел A разделен на 3 части, где ребро AB принадлежит разделу 2, а ребро AD принадлежит разделу графа 3.

Разделение графа также будет включать стратегии сегментации графа, например, метод pointcut будет иметь различные стратегии: случайное хэширование по ребрам, Edge1D, Edge2D и так далее. Некоторые стратегии могут выполняться параллельно глобально, и скорость высокая, но эффективность связи во время балансировки нагрузки и вычислений не идеальна; некоторые должны выполняться последовательно, но балансировка нагрузки и эффективность связи будут лучше. основываться на различных бизнес-сценариях на выбор.

модель исполнения

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

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

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

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

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

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

коммуникационная модель

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

3.2 Выбор технологии

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

Pregel & Giraph

Google предложил Pregel решить проблему неэффективной работы графовых алгоритмов на MapReduce, но он не был с открытым исходным кодом. Facebook разработал систему с открытым исходным кодом Giraph в соответствии с идеями Прегеля, но у Giraph есть две проблемы: во-первых, сообщество Giraph не очень активно; во-вторых, графы в реальной жизни — это графы, которые подчиняются степенному закону распределения, то есть есть ребра с небольшим количеством точек. Число очень велико, и эти точки могут легко замедлить всю вычислительную задачу в режиме расчета Прегеля.

GraphX

GraphX — это система графовых вычислений, построенная на Spark, которая объединяет многие идеи PowerGraph и оптимизирует избыточный Shuffle в процессе запуска графовых алгоритмов в Spark. По сравнению с нативным Spark GraphX имеет большое преимущество в производительности, но GraphX очень требователен к памяти, а эффективность Shuffle не очень высока, что приводит к относительно большому времени работы.

Gemini

Gemini – документ о системе графических вычислений, опубликованный в OSDI в 2016 году. Он сочетает в себе преимущества различных систем графовых вычислений и имеет реализацию с открытым исходным кодом. Как один из самых быстрых движков графовых вычислений, он получил широкое признание в отрасли.

Как указано в статье «Масштабируемость! Но какой ЦЕНОЙ?», для масштабируемости большинство систем графовых вычислений игнорируют производительность одной машины, а огромные накладные расходы на связь, вызванные распределением, приводят к вычислительной производительности в многомашинной среде. иногда даже хуже Автономная среда. В ответ на эти проблемы Gemini разработала целевую оптимизацию, которая вкратце описана следующим образом:

Формат хранения графов оптимизирует накладные расходы памяти: использует CSC и CSR для хранения графов и дополнительно индексирует CSC/CSR для сокращения использования памяти;
Иерархическое секционирование на основе фрагментов. Сокращение коммуникационных издержек за счет сегментации графа с учетом региона в нескольких измерениях Node, Numa и Socket;
Адаптивный расчет Push/Pull: используется двухрежимная стратегия связи, которая может динамически переключаться в плотный или разреженный режим в соответствии с текущим количеством активных узлов.

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

3.3 Практика на основе открытого исходного кода

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

Исследование большего масштаба данных

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

Кодировка идентификатора точки

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

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

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

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

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

Реализация пользовательского алгоритма

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

Поскольку API, предоставляемый текущей системой графовых вычислений, не очень хорошо инкапсулирован, пользователи, которые пишут алгоритмы, будут напрямую воспринимать лежащие в их основе внутренние механизмы, такие как различные режимы связи, методы представления графов и т. д., что, безусловно, удобно для алгоритмов графовых вычислений. Настройка, но также приводит к определенным затратам для студентов бизнес-школ; кроме того, из-за высокопроизводительных вычислений, использующих сверхбольшие объемы данных, некоторые детали (такие как вызов виртуальной функции на горячем пути, синхронизация потоков) могут иметь решающее влияние на производительность. , требует от студентов, изучающих бизнес, определенного понимания компьютерной архитектуры. Основываясь на двух вышеупомянутых причинах, текущий алгоритм разработан студентами, изучающими графовые вычислительные машины, и пользователями графовых вычислений, но в долгосрочной перспективе мы будем инкапсулировать общие вычислительные операторы и предоставлять привязку Python или внедрять DSL для снижения затрат на бизнес-обучение.

3.4 Перспективы будущего

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

От вычислений с полной памятью до вычислений с гибридным хранилищем: для поддержки больших объемов данных и обеспечения более дешевых вычислительных возможностей мы изучим новое оборудование для хранения, включая память или внешние устройства хранения, такие как AEP/NVMe, для расширения системных возможностей. ;
Расчет динамического графика: Текущая система поддерживает только расчет статического графика, то есть расчет полного объема данных полного графика. График в реальном бизнесе меняется каждую минуту, поэтому в существующих системах для каждого расчета необходимо предоставлять полный график. Вычисления с динамическим графом могут лучше обрабатывать добавочные данные, и нет необходимости выполнять повторные вычисления с уже обработанными данными, поэтому мы рассмотрим вычисления с динамическим графом в некоторых сценариях;
Гетерогенные вычисления. Система графовых вычислений требует больших вычислительных ресурсов и в некоторых сценариях предъявляет чрезвычайно высокие требования к производительности вычислений. Поэтому мы попробуем гетерогенные вычисления, в том числе с использованием GPU/FPGA и другого оборудования для ускорения вычислений, чтобы добиться отличной вычислительной производительности;
Язык графических вычислений: бизнес, напрямую контактирующий с базовым вычислительным движком, имеет много недостатков, например, бизнес-логика сильно связана с вычислительным движком, что делает невозможным более гибкую оптимизацию производительности различных алгоритмов. Описывая алгоритм на языке графовых вычислений, а затем компилируя его для генерации исполняемого кода вычислительной машины, бизнес-логику можно отделить от вычислительной машины, а различные алгоритмы можно лучше автоматически настроить для достижения максимальной производительности.

4. Резюме

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

5. Ссылки

Бронсон, Натан и др. «{TAO}: распределенное хранилище данных Facebook для социального графа». Представлено в рамках Ежегодной технической конференции {USENIX} 2013 г. ({USENIX}{ATC} 13). 2013 г.
Malewicz, Grzegorz, et al. "Pregel: a system for large-scale graph processing." Proceedings of the 2010 ACM SIGMOD International Conference on Management of data. 2010.
Low, Yucheng, et al. "Distributed graphlab: A framework for machine learning in the cloud." arXiv preprint arXiv:1204.6078 (2012).
Gonzalez, Joseph E., et al. "Powergraph: Distributed graph-parallel computation on natural graphs." Presented as part of the 10th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 12). 2012.
Gonzalez, Joseph E., et al. "Graphx: Graph processing in a distributed dataflow framework." 11th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 14). 2014.
Zhu, Xiaowei, et al. "Gemini: A computation-centric distributed graph processing system." 12th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 16). 2016.
Kyrola, Aapo, Guy Blelloch, and Carlos Guestrin. "Graphchi: Large-scale graph computation on just a {PC}." Presented as part of the 10th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 12). 2012.
Roy, Amitabha, Ivo Mihailovic, and Willy Zwaenepoel. "X-stream: Edge-centric graph processing using streaming partitions." Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles. 2013.
Shun, Julian, and Guy E. Blelloch. "Ligra: a lightweight graph processing framework for shared memory." Proceedings of the 18th ACM SIGPLAN symposium on Principles and practice of parallel programming. 2013.
McSherry, Frank, Michael Isard, and Derek G. Murray. "Scalability! But at what {COST}?." 15th Workshop on Hot Topics in Operating Systems (HotOS {XV}). 2015.
Aditya Auradkar, Chavdar Botev, Shirshanka Das. "Data Infrastructure at LinkedIn "2012 IEEE 28th International Conference on Data Engineering

поделиться больше

Практика ByteDance HDFS уровня EB

Основная практика ByteDance по оптимизации Spark SQL

Команда инфраструктуры ByteDance

Команда инфраструктуры ByteDance — важная команда, которая поддерживает бесперебойную работу множества пользовательских продуктов ByteDance, включая Douyin, Today's Toutiao, Xigua Video и Volcano Small Video, Стабильная разработка обеспечивает гарантии и импульс.

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

В культурном плане команда активно использует открытый исходный код и инновационные аппаратные и программные архитектуры. Мы давно набираем студентов по направлению инфраструктура, подробнее см.job.bytedance.com, заинтересованные могут обращаться по электронной почте arch-graph@bytedance.com .

Добро пожаловать в техническую команду ByteDance