Автор Цяо Цзин, Яо Чи
1. Управление потоком в OneFlow
Команда OneFlow ранее опубликовала статью «Только эта статья позволит вам освоить системный дизайн платформы OneFlow».Механизм противодавлениярешить проблему управления потоком. Принципиальная схема двух трубопроводов приведена в тексте:
Рисунок: Хронология, когда обучение является узким местом
Рисунок: Временная шкала, когда загрузка данных является узким местом
Как показано на двух рисунках выше, хотя время DataLoading очень короткое, он не будет загружать данные без ограничений, а будет ждать, когда будут заполнены два его регистра.
- Когда обучение является узким местом, а данные пакета 3 обучаются, DataLoading заранее подготавливает данные пакетов 7 и 8, а затем ожидает.
- Когда предварительная обработка является узким местом, DataLoading всегда обрабатывает два пакета данных перед предварительной обработкой.
Эти два рисунка просто иллюстрируют, что вДецентрализованный дизайн с асинхронным исполнениемв системе OneFlow, черезМеханизм противодавления, система автоматически позаботится о юните с самой низкой скоростью обработки, чтобы каждый исполнительный юнит (мы называем его Актером) мог соответствующим образом настроить рабочий ритм.
Если вы хорошенько об этом подумаете, то обнаружите, что механизм противодавления здесь похож на хорошо известное скользящее окно TCP.
В самом деле,Механизм противодавления, также известный как управление потоком на основе кредита, является классическим решением проблемы управления потоком в сетевой связи.Его предшественник возник из скользящего окна TCP.
Эта идея особенно проста и эффективна.Позже мы увидим, что эта идея, основанная на том же принципе, применима к любой схеме управления потоком и используется при проектировании многих аппаратных и программных систем.
Однако вы можете и не подозревать, что за этой простой идеей стоит сложный жизненный опыт. Это даже вызвало ожесточенные академические дебаты и проиграло в дебатах. Несмотря на то, что она проиграла, идея управления потоком на основе кредитов была усовершенствована в ходе дебатов, и позже она засияла во многих областях.
Сегодня мы поговорим о принципе, стоящем за ним, и истории его взлетов и падений.
2. Что такое управление потоком
Управление сетевым потоком (Network Flow Control) — это базовая функция в сети, ее цель — предотвратить пропуск кадров сетью в случае перегрузки.
На приведенной выше диаграмме предположим, что между парой сетевых узлов связи:
- Скорость, с которой отправитель создает данные, составляет 2 МБ/с, скорость, с которой получатель потребляет данные, составляет 1 МБ/с, а скорость, с которой данные передаются по сети, составляет 2 МБ/с.
- Каждый из двух узлов имеет буфер данных (буфер отправки/получения) размером 5 МБ.
Можно сделать вывод, что, поскольку отправитель производит данные быстрее, чем получатель потребляет данные, буфер приема будет заполнен через 5 секунд, и в это время возникнут две ситуации:
- Если буфер приема ограничен, то вновь поступившие данные могут быть только отброшены.
- Если буфер приема не ограничен, буфер приема будет продолжать расширяться, что в конечном итоге приведет к исчерпанию памяти на стороне получателя.
Подводя краткий итог, так называемое управление потоком предназначено для решения сквозной задачи.Скорости отправителя и получателя не совпадаютПроблема. Или, если быть более точным, решить проблему «быстрого отправителя и медленного получателя».
Итак, каковы решения для управления потоком? Так называемая схема управления потоком предназначена для обеспечения набора мер согласования скорости для адаптации к более низкой скорости чтения Получателя путем сдерживания более высокой скорости отправки Отправителя.
Тогда возникает вопрос, как ограничить скорость отправки Sender? Есть два распространенных решения.
Идея 1: Простое и грубое ограничение скорости
Отправитель отправляет данные с заданной скоростью. Например, внедрите ограничитель скорости на стороне отправителя, чтобы уменьшить скорость отправки отправителя до 1 МБ/с, чтобы скорость отправки отправителя и скорость обработки получателя совпадали.
Идея 2: Авторизация на отправку
Отправитель не может отправить напрямую, если он не получилприемлемый трафикинструкции. Эта схема квантования защищает приемник от переполнения памяти.
Обратите внимание, что здесьприемлемый трафик, часто называемый авторизацией (кредитом), что это такое? И какое это имеет отношение к тому, что мы называем управлением потоком на основе кредитов?
Сначала продай. Далее мы опишем жизненный опыт управления потоками на основе кредитов в хронологическом порядке. На самом деле, эти два направления мысли как раз и являются двумя сторонами конфликта в дебатах, которые мы собираемся увидеть. Ответ на вопрос также раскроется в рассказе.
2. История управления потоком на основе кредитов
Скользящее окно TCP
В 1974 году разработчик протокола TCP/IP Винтон Дж. Серф, известный как один из отцов Интернета, опубликовал в этой статье основополагающий документ протокола TCP/IP «Протокол для пакетной сетевой связи». , Предложена схема управления потоком на основе скользящего окна.
В декабре того же года концепция раздвижных окон была официально добавлена в RFC675 (*
Woohoo.Bazooka.at/doc/RFC/RFC…середина. Со временем в протокол TCP/IP было внесено множество улучшений, постепенно исправлены различные ошибки и несоответствия, но идея скользящих окон осталась. Позже эта идея была развита, и были разработаны «окна» в различных сценариях управления сетевым потоком, которые затем были преобразованы в управление потоком на основе кредита.
Далее давайте взглянем на рабочий процесс скользящего окна TCP.
Анимация выше демонстрирует рабочий процесс скользящего окна TCP:
- Предполагается, что при инициализации размер окна отправки равен 3 (которое будет динамически корректироваться в соответствии с ситуацией отправки), а размер окна приема равен 5 (фиксировано). А скорость, с которой отправитель отправляет пакеты данных, в три раза превышает скорость, с которой получатель потребляет данные.
- Отправитель отправляет 1
Пакет 3, Получатель получает 1Пакет 3 помещается в буфер. - Получатель потребляет пакет номер 1.
- Получатель отвечает отправителю с Ack=4, что означает, что отправитель может затем отправить из 4-го пакета, а размер окна равен 3 (общий размер равен 5, но есть 2 пакета данных, которые могут быть использованы в будущем ); получатель получает сообщение После сообщения переместите скользящее окно на 4 и отправьте размер окна на 3.
- Отправитель отправляет 4
Пакет 6, получатель получает 4Пакет 6 и помещается в буфер. - Получатель потребляет пакет номер 2.
- Получатель отвечает отправителю с Ack=7, что означает, что отправитель может затем отправить 7-й пакет, а размер окна равен 1; после получения сообщения получатель перемещает скользящее окно на 8,При этом размер окна доводится до 1, то есть скорость передачи уменьшается до 1/3 от исходной.
- Отправитель отправляет 7-й пакет, а Получатель получает 7-й пакет. В настоящее времяБуфер приемника заполнен.
- Если предположить, что существует проблема с потреблением данных получателем, данные не потреблялись, а окно приема в это время заполнено, тогда получатель ответит ACK=8, а размер окна равен 0. После того, как получатель получит сообщение, он изменит размер окна отправки на 0, то естьостановить отправку.
- Предполагая, что приемник восстанавливает данные о потреблении, описанный выше процесс, аналогичный 3~5, будет повторяться.
Предложение концепции управления потоком на основе кредита
В 1981 году в «Методах, инструментах и наблюдениях за управлением потоком в сетях передачи данных с коммутацией пакетов» Пузен и Луи обобщили некоторые схемы управления потоком в сети, существовавшие в то время, и предложили концепцию управления потоком на основе кредита. определяется как:
credit (or *token) *: which gives permission for message flow.
Он также указал, что схема управления потоком, основанная на оконном механизме, является примером управления потоком на основе кредита, который называетсяSelf-Correcting Credit Scheme.
Рисунок: «Методы, инструменты и наблюдения за управлением потоком в сетях передачи данных с коммутацией пакетов»
Ожесточенные дебаты по поводу управления потоком на основе кредитов
Эти дебаты начались в начале 1990-х годов, когда в некогда многообещающей сети банкоматов полным ходом шла разработка и формулирование стандартов.
Сеть ATM (асинхронный режим передачи) представляет собой общий режим передачи, ориентированный на соединение, предназначенный для нескольких услуг. Он обладает такими преимуществами, как хорошая производительность в режиме реального времени, высокая гибкость и отличное качество обслуживания. Поэтому дискуссия о выборе сопутствующих технологий в сети банкоматов также идет очень интенсивно.
В 1993 году китайский профессор Х. Т. Кунг (Конг Сянчжун) представил на Форум банкоматов предложение по управлению потоком на основе кредита в сети банкоматов.
В этом предложении приводится конкретный алгоритм реализации управления потоком на основе кредита в сети банкоматов, а также проводится подробный анализ удобства использования. Как только схема была предложена, она была серьезно воспринята промышленностью.
Однако к концу 1994 года ATM Forum проголосовал за другую схему, называемую управлением потоком на основе скорости, и отклонил схему управления потоком на основе кредита.
Помните две схемы управления потоком, о которых мы упоминали в предисловии? Фактически, управление потоком на основе скорости соответствует вышеупомянутомуПростое и грубое ограничение скорости, Управление потоком на основе кредита соответствует вышеупомянутомуРазрешено отправлять.
Вот краткое введение в управление потоком на основе скорости.
Идея управления потоком на основе скорости заключается в том, что отправитель заранее оценивает требования к скорости в соответствии с требуемыми ресурсами и отправляет данные с заранее определенной скоростью.
Типичным применением этой схемы является периферийное устройство ввода-вывода, которое работает с фиксированной скоростью. Например, такое устройство, как символьный терминал, вообще говоря, когда оно действует как получатель, не может активно управлять скоростью, с которой отправитель отправляет данные. Таким образом, чтобы он работал правильно, единственный способ — заставить отправителя передавать ему данные в своем ритме. Другим типичным применением отправителя, отправляющего данные с фиксированной скоростью, является конвейерная технология в конструкции ЦП.Фиксированная глобальная тактовая частота в конвейере определяет, что каждый компонент работает с одинаковой скоростью.
Возвращаясь к нашей предыдущей истории, что произошло за более чем один год между 93-м и 94-м?
Из итоговой статьи 1996 года «Контроль перегрузки и управление трафиком в сетях банкоматов: последние достижения и обзор» мы можем получить представление об интенсивности дебатов между двумя схемами в то время.
Споры, длящиеся уже больше года, можно назвать весьма «религиозными», поскольку сторонники каждого метода преследуют совершенно разные цели и не желают идти на компромисс. Для достижения своих целей они готовы идти на компромиссы, которые другие не могут принять.
Одна сторона на основе кредита гласила: «Кредит там, где причитается кредит», а другая сторона на основе скорости говорила: «Преимущества управления потоком на основе скорости для службы ABR».
Сторонняя атака на основе скорости: «Ограничения управления потоком на основе кредита». Сторона на основе кредита отвечает: «Реалии управления потоком для службы ABR».
Очевидно, Credit-based Flow Control очень недовольна выбором ATM Forum. Они твердо убеждены, что Credit-based Flow Control — лучшее решение. В ближайшие несколько лет ученые продолжат исследования в этой области.
Например, сам профессор Конг опубликовал три статьи подряд, внося ряд соответствующих улучшений в алгоритм, изначально предложенный схемой управления потоком на основе кредитов, таких как поддержка динамического кредита.
Кроме того, он также организовал команду в Гарварде для совместной разработки коммутатора банкоматов на основе управления потоком на основе кредитов с BNR и провел дополнительные эксперименты, чтобы доказать эффективность алгоритма, см. здесь:
Уууу, даже если quota/read/5769/from…
Профессор Конг упомянул причины своих усилий в «Управлении потоком на основе кредита для сетей банкоматов»:
Мы надеемся, таким образом, ускорить эволюцию управления потоками ATM и свести к минимуму риск стандартизации неадекватных решений.В этой статье избегаются политические и краткосрочные прагматические вопросы, такие как пути миграции и функциональная совместимость, отмечая, что механизмы управления потоками, принятые в настоящее время, могут использоваться после того, как такие проблемы забыты.
Интуитивное понимание управления потоком на основе кредитов
Далее давайте рассмотрим основные принципы управления потоком на основе кредитов с аналогичной и эвристической точки зрения, и мы обнаружим, что эта идея очень тонкая и краткая, в соответствии с эстетикой дизайна «Меньше значит больше».
В сети, используемой для передачи данных, мы часто видим какие-то буферы (Buffer). Например, буфер отправки и буфер приема, которые мы видели в предисловии.
Что делают эти буфера?
В аналогии с нашей жизнью мы строим ряд плотин вдоль реки, как показано на изображении ниже.
рисунок:Уууу, даже если quota/read/5769/from…
Каковы преимущества плотины? Мы можем мыслить открыто:
Основным преимуществом является то, что она имеет функцию «буферизации»: наличие плотины обеспечивает удобство использования воды жителями, находящимися вблизи плотины.Если плотины нет, когда потребление воды резко возрастает за короткий промежуток времени, он может только ждать, пока «дальняя вода сразится с ближним огнем».
Во-вторых, плотина имеет эффект контроля наводнений «обратной связи». Всякий раз, когда плотина ниже по течению заполняется, ее плотина выше по течению получает уведомление о закрытии. Затем, когда происходит наводнение, каждая плотина выше по течению может помочь уменьшить наводнение в местах скопления вниз по течению, и пропускная способность каждой плотины используется эффективно.
В сети, которая передает данные, цель проектирования буфера в начале в основном состоит в том, чтобы справиться с колебаниями производительности устройств по разным причинам, что приводит к проблеме нескоординированной эффективности между устройствами. Это похоже на плотины в нашей жизни, которые регулируют колебания потребления воды.
Итак, можем ли мы имитировать принцип контроля затопления плотины и обеспечить механизм обратной связи для буфера в сети, чтобы динамически регулировать поток данных?
Конечно, это идея Credit-based Flow Control.
В случае контроля затопления плотины всякий раз, когда плотина заполняется, ее верхняя плотина уведомляется о закрытии. Другими словами, то, что нижележащая плотина возвращает плотине выше по течению, является ее емкостью для хранения воды.
Точно так же в управлении потоком на основе кредита получатель (нисходящий узел) может возвращать информацию о занятости своего собственного буфера отправителю (восходящий узел), тем самым регулируя объем данных, отправляемых отправителем. Здесь мы называем информацию, требующую обратной связи, кредитом, как показано на рисунке ниже.
рисунок:Уууу, даже если quota/read/5769/from…
Выбор содержания кредита и способа обработки после того, как Отправитель получит кредит, может быть определен в соответствии с конкретным сценарием. Например, в предложении профессора Конга по управлению потоком на основе кредита в сети банкоматов в 1993 году были даны три метода выбора значений кредита, и разные методы использовались для работы с разными сценариями.
Мы не будем здесь расширяться, просто уточним, что значение Credit отражает заполнение буфера отправителя, и отправитель определяет, сколько данных отправить, на основе полученного значения Credit.
Можно ясно видеть, что в управлении потоком на основе кредита скорость отправки или потокКонтролируется приемником, Отправитель всегда вынужден подстраиваться для синхронизации с Получателем.
Поэтому управление потоком на основе кредита часто называютМеханизм противодавленияУправление потоком отражает основную идею о том, что восходящий поток управляется нисходящим потоком.
Подводя итог, преимущества управления потоком на основе кредитов:
- Теоретически буфер приемника никогда не переполнится.
- Управление потоком является динамическим и может поддерживать работу Receiver все время (Keep Receiver Very Busy).
В практических приложениях управление потоком на основе кредита также имеет некоторые специфические проблемы, которые необходимо учитывать, такие как:
- Что, если я потеряю кредит?
- Передача Кредита требует определенных затрат. Допустимо ли это для конкретной системы?
Еще в 1994 году, когда ATM Forum проголосовал за схему управления потоком, ATM Forum объявил:
Управление потоком на основе кредитов считается не масштабируемым для большого количества кредитов, учитывая, что некоторые крупные коммутаторы будут поддерживать миллионы виртуальных каналов (управление потоком на основе кредитов основано на наборе кредитов на каждый виртуальный канал, виртуальный канал относится к виртуальному каналу). сети ATM, на физическом канале может быть несколько виртуальных путей), что приведет к огромной сложности при реализации коммутаторов. ——《Контроль заторов и управление трафиком в сетях банкоматов: последние достижения и обзор》
Управление потоком на основе кредитов расцветает в других областях
С развитием технологий мы можем наблюдать такую тенденцию появления новых технологий во все большем количестве областей.Режим передачи данных развивается в направлении «многосвязность и раздача».. Поэтому многие проблемы абстрагируются от сетевых проблем, а управление потоком также стало важной частью этих технических решений.
Идея Credit-based Flow Control лаконична и ясна, и эта идея применима к любой схеме управления потоком. На самом деле различные программно-аппаратные комплексы имеют схожие механизмы, но с разными названиями.
Например, от новой шинной технологии PCI Express и Intel QPI в аппаратном обеспечении до нового сетевого протокола RDMA, а затем до системы потоковых вычислений Flink можно увидеть управление потоком на основе кредита.
Далее давайте посмотрим, как в этих сценариях работает управление потоком на основе кредитов.
PCIe
PCIe — это аббревиатура от PCI-Express (Peripheral Component Interconnect Express), который является стандартом высокоскоростной последовательной компьютерной шины расширения.Он был предложен Intel в 2001 году и теперь заменил старые PCI, PCI-X и AGP, став самый популярный автобус стандарт.
Соединение для передачи данных в PCIe называетсяLane, фактический канал данных может быть объединен несколькими дорожками для обеспечения более высокой пропускной способности, что немного похоже на концепцию виртуальных каналов в сетях ATM. Для управления потоком в этом сценарии многоканальной связи необходимо тщательно решать проблему отбрасывания пакетов и повторной передачи из-за недостаточного буфера на принимающей стороне, здесь как нельзя кстати приходит Credit-based Flow Control.
Чтобы узнать, сколько буферов доступно на принимающей стороне, принимающая сторона должна сообщить о доступных буферах в любое время через DLLP (пакет уровня канала передачи данных).DLLP здесь является конкретной реализацией кредита в PCIe.
Intel QPI
Технология Intel QuickPath Interconnect (QPI), переводится как Quick Path Interconnect, используется для достижения прямого соединения между чипами, заменяя традиционную FSB (Front Side Bus). В традиционной FSB (Front Side Bus) вся передача данных осуществляется через одну шину, которая называется подходом с одной общей шиной, как показано на рисунке ниже.
рисунок:woohoo.Intel.com/content/woohoo…
Одним из основных преимуществ QPI является то, что он поддерживает несколько подключений к системной шине, как показано на рисунке ниже. Системная шина будет разделена на несколько соединений, и частота больше не будет единой фиксированной. Скорость каждого соединения системной шины также может варьироваться в зависимости от требований к пропускной способности данных различных подсистем системы. Этот переход от одной шины к нескольким шинам является основным направлением развития процессоров для повышения производительности передачи данных в последние годы.
Это похоже на небольшую топологию сети, и, что интересно, ее протокол передачи данных также разработан каккомпьютерная сетьмногослойная модель.
Среди них пакет данных, передаваемый канальным уровнем (Link Layer), называется Flit, что означает блок управления потоком. Каждый Flit содержит поток управления потоком, функция которого состоит в том, чтобы возвращать буферное пространство от Rx (получателя) к Tx (передатчику). Вот пример использования схемы на основе кредита для реализации управления потоком, чтобы предотвратить переполнение буфера получателя.
RDMA
RDMA (удаленный прямой доступ к памяти), то есть удаленный прямой доступ к данным, создается для устранения задержки обработки данных на стороне сервера при передаче по сети.Он очень подходит для использования в крупномасштабных параллельных компьютерных кластерах.В последние годы он стал популярен в центрах обработки данных.
В настоящее время существует примерно три типа сетей RDMA, а именно Infiniband, RoCE (RoCE и Roce v2) и iWARP. Среди них Infiniband — сеть, специально разработанная для RDMA, которая обеспечивает надежную передачу на аппаратном уровне, а RoCE и iWARP — технологии RDMA на основе Ethernet.
После тщательного анализа будет обнаружено, что все схемы управления потоком этих трех типов сетей RDMA основаны на Credit-b.
Идея ased Flow Control.
InfiniBand
В разделе «Управление потоком на канальном уровне на основе кредита InfiniBand» упоминается, что управление потоком на основе кредита реализовано на канальном уровне в InfiniBand. Пакет управления потоком на канальном уровне является конкретной реализацией Credit в InfiniBand.
RoCE
В RoCE используется алгоритм управления потоком PFC (управление потоком на основе приоритетов). В статье «Пересмотр сетевой поддержки RDMA» описан алгоритм PFC, заключающийся в том, что когда очередь превышает определенный настроенный порог, коммутатор отправляет кадр паузы вышестоящему объекту.
Нисходящий поток контролирует восходящий, что является идеей управления потоком на основе кредитов.
iWARP
Управление потоком выполняется напрямую через TCP, а TCP — это идея управления потоком на основе кредитов.
Flink
В эпоху больших данных Интернета требования к данным в реальном времени становятся все выше и выше, и все больше и больше распределенных вычислительных машин начинают использовать потоковую абстракцию. Apache Flink был создан для потоковых вычислений и используется для выполнения вычислений с отслеживанием состояния потоков данных.Он известен как вычислительный движок четвертого поколения после Hadoop, Pig/Hive и Spark/Storm в эпоху больших данных.
В статье «Как Apache Flink™ справляется с обратным давлением», которая знакомит с Flink, в заголовке появляется слово Противодавление, которое должно означать «Управление потоком на основе кредита».
В частности, на схематической диаграмме, нарисованной в статье, черные полосы Task1 и Task2 на рисунке представляют буфер. Конечно, в статье говорилось: «Если нет доступного буфера, он прервет чтение данных из TCP-соединения», что, очевидно, является идеей управления потоком на основе кредитов.
3. Оглянитесь назад на дизайн управления потоком OneFlow
Во-первых, просмотрите конструктивные особенности OneFlow.
OneFlow автоматически скомпилирует граф логических вычислений пользователя в граф физических вычислений в распределенной системе, и граф физических вычислений будет выполняться средой выполнения OneFlow. Единицей выполнения графа физических вычислений является Актер, и входные данные проходят через каждую исполнительную единицу Актера, как поток воды, для завершения операции.
Вычислительные графы, состоящие из Актеров в OneFlow, имеют две уникальные особенности по сравнению с вычислительными графами, состоящими из OP в других платформах:
- Центрального узла планирования нет.
- Каждый актор выполняется асинхронно.
То есть каждый Актер обнаруживает, что у вышестоящего есть данные для чтения, а у нижестоящего есть место для записи, тогда он может работать, не зная состояния других Актеров.
Преимущества этих двух уникальных конструкций:
- Децентрализованный дизайн, который легко решает проблему узкого места производительности в одной точке метода централизованного планирования в сценарии сверхкрупномасштабного распределенного обучения.
- Дизайн для асинхронного выполнения, сделать конвейер параллельным возможно, и теоретически аппаратные ресурсы можно использовать на полную катушку.
Увидев это, можно остановиться и подумать, как сделать управление потоком для такой потоковой распределенной системы?
После прочтения вышеприведенной истории, строительство плотины (Регст) и использование обратного давления для управления потоком будет первым выбором в вашем сердце?
P.S.: Улучшите вопрос
При идее использования обратного регулирования расхода возникает следующий вопрос, как выбрать мощность плотины (величину Регста) при конкретном строительстве?
Например, в примере в начале статьи мы установили Regst=2, это лучший выбор?
Добро пожаловать, чтобы поделиться своими мыслями в области комментариев,Для достоверных ответов, мы будем раздавать сувениры OneFlow. Если вы хотите узнать о новинке OneFlow, нажмите «читать оригинал«Перейдите к коду OneFlow, чтобы найти ответ, вы также можете продолжать обращать внимание, возможно, в будущем мы организуем еще один выпуск статей с интерпретациями.
Заглавное изображение от Геральта, Pixabay