По вашему запросу ничего не найдено :(
Убедитесь, что запрос написан правильно, или посмотрите другие
наши статьи:
В предыдущих лекциях обсуждалось правило кратчайшего пути и два алгоритма (или, возможно, системы) для поиска путей без петель через сеть. Существует широкий спектр таких систем—их слишком много, чтобы охватить их в отведенное время для изучения, - но для сетевых администраторв важно быть знакомыми хотя бы с некоторыми из этих систем. В этих лекциях сначала рассматривается алгоритм поиска кратчайшего пути Дейкстры, вектор пути и два различных алгоритма непересекающихся путей: Suurballe и Maximally Redundant Trees (MRTs). Наконец, в этих лекциях будет рассмотрена еще одна проблема, которую должны решить управляющие плоскости: обеспечение двусторонней связи через сеть.
Алгоритм Дейкстры Shortest Path First.
Алгоритм Дейкстры Shortest Path First (SPF), возможно, является наиболее широко известной и понятной системой для обнаружения Loop-Free путей в сети. Он используется двумя широко распространенными протоколами маршрутизации и во многих других повседневных системах, таких как программное обеспечение, предназначенное для поиска кратчайшего пути через дорожную сеть или для обнаружения соединений и паттернов соединений в социальных сетях.
Алгоритм Дейкстры в псевдокоде использует две структуры данных. Первый - это предварительный список или TENT; этот список содержит набор узлов, рассматриваемых для включения в дерево кратчайшего пути (Shortest Path Tree). Второй - PATH; этот список содержит набор узлов (а следовательно, и каналы), которые находятся в дереве кратчайшего пути.
01 move "me" to the TENT
02 while TENT is not empty {
03 sort TENT
04 selected == first node on TENT
05 if selected is in PATH {
06 *do nothing*
07 }
08 else {
09 add selected to PATH
10 for each node connected to selected in TOPO
11 v = find node in TENT
12 if (!v)
13 move node to TENT
14 else if node.cost < v.cost
15 replace v with node on TENT
16 else
17 remove node from TOPO
18 }
19 }
Как всегда, алгоритм менее сложен, чем кажется на первый взгляд; ключом является сортировка двух списков и порядок, в котором узлы обрабатываются вне списка TENT. Вот несколько примечаний к псевдокоду перед рассмотрением примера:
Процесс начинается с копии базы данных топологии, называемой здесь TOPO; это будет яснее в примере, но это просто структура, содержащая исходные узлы, целевые узлы и стоимость связи между ними.
TENT - это список узлов, которые можно условно считать кратчайшим путем к любому конкретному узлу.
PATH - это дерево кратчайшего пути (SPT), структура, содержащая loop-free путь к каждому узлу и следующий переход от «меня» к этому узлу.
Первым важным моментом в этом алгоритме является сохранение только узлов, уже каким-то образом связанных с узлом в списке PATH в TENT; это означает, что кратчайший путь в TENT - это следующий кратчайший путь в сети.
Второй важный момент в этом алгоритме - это сравнение между любыми существующими узлами TENT, которые подключаются к одному и тому же узлу; это, в сочетании с сортировкой TENT и отделением TENT от PATH, выполняет правило кратчайшего пути.
Имея в виду эти моменты, рисунки с 1 по 9 используются для иллюстрации работы алгоритма SPF Дейкстры.
На каждой из следующих иллюстраций вместе с сопроводительным описанием показан один шаг алгоритма SPF в этой сети, начиная с рисунка 2.
В точке, показанной на рисунке 2, A был перемещен из TOPO в TENT, а затем в PATH. Стоимость исходного узла всегда равна 0; эта линия включена для начала расчета SPF. Это представляет строки с 01 по 09 в псевдокоде, показанном ранее. На рисунке 3 показан второй этап расчета SPF.
На рисунке 3 каждый узел, подключенный к A, был перемещен из TOPO в TENT; это строки с 10 по 17 в псевдокоде, показанном ранее. Когда этот шаг начался, в TENT была только A, поэтому в TENT нет существующих узлов, которые могли бы вызвать какие-либо сравнения метрик. Теперь TENT отсортирован, и выполнение продолжается со строки 03 в псевдокоде. Рисунок 4 демонстрирует это.
На рисунке 4 один из двух путей с кратчайшей стоимостью - к B и F, каждый со стоимостью 1 - был выбран и перемещен в PATH (строки 05–09 в псевдокоде, показанном ранее). Когда B перемещается из TENT в PATH, любые узлы с началом B в TOPO перемещаются в TENT (строки 10-17 в псевдокоде). Обратите внимание, что C еще не был в TENT, прежде чем он был задействован посредством перехода B к PATH, поэтому сравнение показателей не выполняется. Стоимость для C - это сумма стоимости его предшественника в PATH (который равен B со стоимостью 1) и связи между двумя узлами; следовательно, C добавляется к TENT со стоимостью 2. TENT сортируется (строка 3 псевдокода), поэтому процесс готов к повторному запуску. На рисунке 5 показан следующий шаг в этом процессе.
На рисунке 5 был выбран кратчайший путь к TENT, и F переместился от TENT к PATH. Между F и E существует связь (показанная на предыдущих иллюстрациях как [E, F]), но путь через F к E имеет ту же стоимость, что и путь [A, E], поэтому эта линия не добавляется в TENT. Скорее он остается неактивным, поскольку не рассматривается для включения в SPT, и удаляется из TOPO. На рисунке 6 показан следующий шаг в процессе, который переместит один из путей метрики 2 в PATH.
Примечание. Большинство реальных реализаций поддерживают перенос нескольких путей с одинаковой стоимостью из TENT в PATH, поэтому они могут пересылать трафик по всем каналам с одинаковой метрикой. Это называется многолучевым распространением с равной стоимостью или ECMP. Для этого есть несколько различных способов, но они в этих лекциях не рассматриваются.
На рисунке 6 путь к C через B со стоимостью 2 был перемещен в PATH, а путь к D через [A, B, C, D] перемещен в TENT. Однако при перемещении этого пути к TENT строка 11 в псевдокоде находит существующий путь к D в TENT, путь [A, D], со стоимостью 5. Метрика нового пути, 3, ниже чем метрика существующего пути, 5, поэтому путь [A, D] удаляется из TENT, когда добавляется путь [A, B, C, D] (строка 15 в псевдокоде). На рисунке 7 показан следующий шаг, на котором линия оставшейся стоимости 2 перемещается из TENT в PATH.
На рисунке 7 путь к E стоимостью 2 был перемещен из TENT в PATH. G был перемещен в TENT стоимостью 4 (сумма [A, E] и [E, G]). Другой сосед E, F, исследуется, но он уже находится в PATH, поэтому не рассматривается для включения в TENT. На рисунке 8 показан следующий шаг, который перемещает D в PATH.
На рисунке 8 D общей стоимостью 3 перемещен из TENT в PATH. Это учитывает соседа D, G, последнюю запись в TOPO, для TENT. Однако уже существует путь к G с общей стоимостью 4 через [A, E, G], поэтому строка 14 в псевдокоде завершается ошибкой, и путь [D, G] удаляется из TOPO. Это последний SPT.
Основная трудность в понимании алгоритма Дейкстры заключается в том, что правило кратчайшего пути не выполняется в одном месте (или на одном маршрутизаторе), как это происходит с Bellman-Ford или Diffusing Update Algorithm (DUAL). Кратчайший путь (по-видимому) проверяется только при перемещении узлов из TOPO в TENT - но на самом деле сортировка самого TENT выполняет другую часть правила кратчайшего пути, и проверка по PATH для существующих узлов составляет еще один шаг в процесс, делающий процесс трехступенчатым:
Если путь к узлу длиннее, чем любой из TENT, то путь к TENT является более коротким путем по всей сети.
Путь, который поднялся к вершине TENT через сортировку, является самым коротким к этому узлу в сети.
Если путь перемещается к PATH от вершины TENT, это кратчайший путь к этому узлу в сети, и любые другие записи в TOPO к этому узлу следует отбросить.
При наличии базового алгоритма полезно рассмотреть некоторые оптимизации и расчет Loop-Free Alternates (LFAs) и remote Loop-Free Alternates (rLFAs).
Частичный и инкрементный SPF
Нет особой причины, по которой весь SPT должен перестраиваться каждый раз, когда происходит изменение топологии сети или информации о доступности. Рассмотрим рисунок 9 для объяснения.
Предположим, G теряет связь с 2001: db8: 3e8: 100 :: / 64. Устройству A не требуется пересчитывать свой путь к любому из узлов сети. Доступный пункт назначения - это просто лист дерева, даже если это набор хостов, подключенных к одному проводу (например, Ethernet). Нет причин пересчитывать весь SPT, когда один лист (или любой набор листьев) отключается от сети. В этом случае только лист (IP-адрес Интернет-протокола или доступный пункт назначения) должен быть удален из сети (или, скорее, пункт назначения может быть удален из базы данных без каких-либо изменений в сети). Это частичный пересчет SPT.
Предположим, что канал [C, E] не работает. Что делает А в этом случае? Опять же, топология C, B и D не изменилась, поэтому у A нет причин пересчитывать все дерево. В этом случае A может удалить все дерево за пределами E. Чтобы вычислить только измененную часть графа, выполните следующие действия:
Удалите отказавший узел и все узлы, которые нужно достичь через точку E.
Пересчитайте дерево только от предшественника C (в данном случае A), чтобы определить, есть ли альтернативные пути для достижения узлов, ранее доступных через E до того, как канал [C, E] не доступен.
Это называется инкрементным SPF.
Расчет LFA и rLFA.
Bellman-Ford не вычисляет ни соседей ниже по потоку, ни LFA, и, похоже, не располагает необходимой для этого информацией. DUAL по умолчанию вычисляет нисходящих соседей и использует их во время конвергенции. А как насчет протоколов на основе Дейкстры (и, соответственно, аналогичных алгоритмов SPF)? На рисунке 10 показан простой механизм, который эти протоколы могут использовать для поиска LFA и соседних узлов ниже по потоку.
Определение нисходящего соседа - это такое, при котором стоимость достижения соседом пункта назначения меньше, чем локальная стоимость достижения пункта назначения. С точки зрения А:
A знает местную стоимость проезда к месту назначения на основе SPT, созданного с помощью SPF Дейкстры.
A знает стоимость B и C, чтобы добраться до места назначения, вычитая стоимость каналов [A, B] и [A, C] из рассчитанной на местном уровне стоимости.
Следовательно, A может сравнивать локальную стоимость со стоимостью от каждого соседа, чтобы определить, находится ли какой-либо сосед в нисходящем направлении по отношению к любому конкретному месту назначения. Определение LFA:
Если затраты соседа для «меня» плюс затраты соседа на достижение пункта назначения ниже, чем местные затраты, соседом является LFA.
Вернее, учитывая:
NC - это стоимость соседа до пункта назначения.
BC - это стоимость соседа для меня.
LC - местная стоимость до места назначения.
Если NC + BC меньше LC, то соседом является LFA. В этом случае A знает стоимость каналов [B, A] и [C, A] с точки зрения соседа (она будет содержаться в таблице топологии, хотя не используется при вычислении SPT с использованием алгоритма Дейкстры). Таким образом, LFA и нисходящие соседи требуют очень небольшой дополнительной работы для расчета, но как насчет удаленных LFA? Модель P/Q Space обеспечивает простейший способ для алгоритмов на основе Дейкстры вычисления соседних узлов и LFA. Рисунок 11 используется для иллюстрации изнутри P/Q Space.
Определение пространства P - это набор узлов, доступных с одного конца защищенного соединения, а определение пространства Q - это набор узлов, достижимых без пересечения защищенного канала. Это должно предложить довольно простой способ вычисления этих двух пространств с помощью Дейкстры:
Рассчитайте SPT с точки зрения устройства, подключенного к одному концу линии связи; удалить линию связи без пересчета SPT. Остальные узлы доступны с этого конца линии.
На рисунке 11 E может:
Вычислите пространство Q, удалив линию [E, D] из копии локального SPT и всех узлов, для достижения которых E использует D.
Вычислите пространство P, вычислив SPT с точки зрения D (используя D в качестве корня дерева), удалив линию [D, E], а затем все узлы, для достижения которых D использует E.
Найдите ближайший узел, достижимый как из E, так и из D, с удаленной линией [E, D].
SPF Дейкстры - это универсальный, широко используемый алгоритм для вычисления Shortest Path Trees через сеть.
gRPC — это мощная платформа для работы с удаленными вызовами процедур (Remote Procedure Calls). RPC позволят писать код так, как будто он будет выполняться на локальном компьютере, даже если он может выполняться на другом компьютере.
Что такое RPC?
RPC — это форма взаимодействия клиент-сервер, в которой используется вызов функции, а не обычный вызов HTTP. Идея в том, что мы можем вызвать и выполнить функцию где-то на удаленной системе, как если бы это была локальная функция.
Он использует IDL (Interface Definition Language - язык описания интерфейса) как форму контракта на вызываемые функции и тип данных.
RPC — это протокол "запрос-ответ", т.е. он следует модели "клиент-сервер":
Клиент делает запрос на выполнение процедуры на удаленном сервере. Как и при синхронном локальном вызове, клиент приостанавливается до тех пор, пока не будут возвращены результаты процедуры. Параметры процедуры передаются по сети на сторону сервера. Процедура выполняется на сервере и, наконец, результаты передаются обратно клиенту.
gRPC воспроизводит этот архитектурный стиль взаимодействия клиент-сервер через вызовы функций.
Таким образом, gRPC технически не является новой концепцией. Скорее, он был заимствован из этой старой техники и улучшен, что сделало ее очень популярной.
Что такое gRPC?
В 2015 году Google открыл исходный код своего проекта, который в конечном итоге получил название gRPC.
Но что на самом деле означает буква «g» в gRPC? Многие люди могут предположить, что это для Google, потому что Google это сделал, но это не так. Google меняет значение «g» для каждой версии до такой степени, что они даже сделали README, чтобы перечислить все значения.
С момента появления gRPC он приобрел довольно большую популярность, и многие компании используют его.
Есть много причин, по которым gRPC так популярен: простая абстракция, он поддерживается во многих языках и он очень эффективный.
И помимо всех вышеперечисленных причин, gRPC популярен потому, что очень популярны микросервисы и имеется большое количество взаимодействий между ними. Именно здесь gRPC помогает больше всего, предоставляя поддержку и возможности для решения типичных проблем, возникающих в таких ситуациях.
А поскольку разные сервисы могут быть написаны на разных языках, gRPC поставляется с несколькими библиотеками для их поддержки.
Архитектура gRPC
Мы сказали что производительность gRPC очень высока, но что делает ее такой хорошей? Что делает gRPC намного лучше, чем RPC, если их дизайн очень похож? Вот несколько ключевых отличий, которые делают gRPC столь эффективным.
HTTP/2
HTTP был с нами очень долго. Сейчас почти все серверные службы используют этот протокол.
HTTP/1.1 долгое время оставался актуальным, затем в 2015 году, появился HTTP/2, который фактически заменил HTTP/1.1 как самый популярный транспортный протокол в Интернете.
Если вы помните, что 2015 год был также годом выхода gRPC, и это было вовсе не совпадение. HTTP/2 также был создан Google для использования gRPC в его архитектуре.
HTTP/2 — одна из важных причин, почему gRPC может работать так хорошо. И в следующем разделе вы поймете, почему.
Мультиплексирование запроса/ответа
В традиционном протоколе HTTP невозможно отправить несколько запросов или получить несколько ответов вместе в одном соединении. Для каждого из них необходимо создать новое соединение.
Такой вид мультиплексирования запроса/ответа стал возможен в HTTP/2 благодаря введению нового уровня HTTP/2, называемого binary framing.
Этот двоичный уровень инкапсулирует и кодирует данные. На этом уровне HTTP-запрос/ответ разбивается на кадры (они же фреймы).
Фрейм заголовков (HEADERS frame) содержит типичную информацию заголовков HTTP, а фрейм данных (DATA frame) содержит полезные данные. Используя этот механизм, можно получить данные из нескольких запросов в одном соединении.
Это позволяет получать полезные данные из нескольких запросов с одним и тем же заголовком, тем самым идентифицируя их как один запрос.
Сжатие заголовка
Вы могли столкнуться со многими случаями, когда заголовки HTTP даже больше, чем полезная нагрузка. И HTTP/2 имеет очень интересную стратегию под названием HPack для решения этой проблемы.
Во-первых, все в HTTP/2 кодируется перед отправкой, включая заголовки. Это помогает повысить производительность, но это не самое важное в сжатии заголовков.
HTTP/2 сопоставляет заголовок как на стороне клиента, так и на стороне сервера. Из этого HTTP/2 может узнать, содержит ли заголовок одно и то же значение, и отправляет значение заголовка только в том случае, если оно отличается от предыдущего заголовка.
Как видно на картинке выше, запрос № 2 отправит только новый путь, так как другие значения точно такие же как и были. И да, это значительно сокращает размер полезной нагрузки и, в свою очередь, еще больше повышает производительность HTTP/2.
Что такое Protocol Buffer (Protobuf)?
Protobuf — это наиболее часто используемый IDL для gRPC. Здесь вы храните свои данные и функциональные контракты в виде так называемого прото-файла. По сути это протокол сериализации данных, такой как JSON или XML.
Выглядит это так:
message Person {
required string name = 1;
required int32 id = 2;
optional string email = 3;
}
Так мы определили сообщение Person с полями name, id и email
Поскольку это форма контракта то и клиент, и сервер должны иметь один и тот же прото-файл. Файл proto действует как промежуточный контракт для клиента, чтобы вызвать любые доступные функции с сервера.
Protobuf также имеет собственные механизмы, в отличие от обычного REST API, который просто отправляет строки JSON в виде байтов. Эти механизмы позволяют значительно уменьшить полезную нагрузку и повысить производительность.
Что еще может предложить gRPC?
Метаданные
Вместо обычного заголовка HTTP-запроса в gRPC есть то, что называется метаданными (Metadata). Метаданные — это тип данных «ключ-значение», которые можно установить как на стороне клиента, так и на стороне сервера.
Заголовок может быть назначен со стороны клиента, в то время как серверы могут назначать заголовок и трейлеры, если они оба представлены в виде метаданных.
Потоковая передача
Потоковая передача (Streaming) — это одна из основных концепций gRPC, когда в одном запросе может выполняться несколько действий. Это стало возможным благодаря упомянутой ранее возможности мультиплексирования HTTP/2.
Существует несколько видов потоковой передачи:
Server Streaming RPC: когда клиент отправляет один запрос, а сервер может отправить несколько ответов. Например, когда клиент отправляет запрос на домашнюю страницу со списком из нескольких элементов, сервер может отправлять ответы по отдельности, позволяя клиенту использовать отложенную загрузку.
Client Streaming RPC: когда клиент отправляет несколько запросов, а сервер отправляет обратно только один ответ. Например, zip/chunk, загруженный клиентом.
Bidirectional Streaming RPC: клиент и сервер одновременно отправляют сообщения друг другу, не дожидаясь ответа.
Перехватчики
gRPC поддерживает использование перехватчиков для своего запроса/ответа. Они перехватывают сообщения и позволяют вам изменять их.
Это звучит знакомо? Если вы работали с HTTP-процессами в REST API, перехватчики очень похожи на middleware (оно же промежуточное ПО).
Библиотеки gRPC обычно поддерживают перехватчики и обеспечивают простую реализацию. Перехватчики обычно используются для:
Изменения запроса/ответа перед передачей. Это можно использовать для предоставления обязательной информации перед отправкой на клиент/сервер.
Позволяет вам манипулировать каждым вызовом функции, например, добавлять дополнительные логи для отслеживания времени отклика.
Балансировки нагрузки
Если вы еще не знакомы с балансировкой нагрузки, это механизм, который позволяет распределять клиентские запросы по нескольким серверам.
Но балансировка нагрузки обычно делается на уровне прокси (например, nginx). Так причем это здесь?
Дело в том, что gRPC поддерживает метод балансировки нагрузки клиентом. Он уже реализован в библиотеке Golang и может быть легко использован.
Хотя это может показаться какой-то магией, это не так. Там есть что-то типа преобразователя DNS для получения списка IP-адресов и алгоритм балансировки нагрузки под капотом.
Отмена вызова
Клиенты gRPC могут отменить вызов gRPC, когда им больше не нужен ответ. Однако откат на стороне сервера невозможен.
Эта функция особенно полезна для потоковой передачи на стороне сервера, когда может поступать несколько запросов к серверу. Библиотека gRPC оснащена шаблоном метода наблюдателя, чтобы узнать, отменен ли запрос, и позволить ей отменить несколько соответствующих запросов одновременно.
Хранилище сервера - важнейшая часть с точки зрения отказоустойчивости. При не надлежащей настройке дисков, данные могут быть утеряны. Полбеды, если вы храните там только игрули, сериальчики и фотографии из поездки в Туапсе в 2005 году, а что если это корпоративные данные?
Поэтому, нужно быть уверенными, что если что - то случится с дисками, то данные не пропадут. Для этого используют технологию RAID (Redundant Array of Independent Disks) (не путать с RAID: Shadow Legends), или так называемый избыточный массив независимых дисков.
В RAID одни и те же данные копируются сразу на множество дисков, так что, в случае, если один диск выйдет из строя, потери данных не будет - копия есть на другом носителе.
Поговорим про четыре распространенных типа RAID массивов: RAID 0, RAID 1, RAID 5 и RAID 10.
Видео: RAID 0, 1, 5 и 10 | Что это?
RAID 0
Честно говоря, RAID 0 нифига не отказоустойчивый. Мы даже против того , чтобы RAID 0 имел название RAID. Скорее AID (Redundant Array of Independent Disks) 0.
В нем цельные данные дробятся на блоки и частями записываются на 2 (два) или более диска. Тем самым, 2 физически отдельных диска, на самом деле, объединяются в один.
И, например, если один из двух физических дисков случайно попадет под каток - вы потеряете все данные. Единственный случай, когда RAID 0 имеет смысл использовать, это если вы храните не критичные к потери данные к которым нужен доступ на высокой скорости. Да - да, RAID 0 имеет низкую отказоуйстойчивость, но высокую производительность.
RAID 1
А вот это парень уже вполне отказоустойчив. RAID 1 кстати еще называют зеркальным, по вполне простой причине - данные синхронно записываются на 2 и более диска сразу:
Тем самым, если один из дисков попадет в воду и выйдет из строя, данные не будут потеряны.
Важный пункт - если вы собираете в RAID 1 массив 2 (два) диска, то в результате вы будете иметь только половину от их общей памяти.
RAID 5
В пятом рэйде вам понадобятся 3 и более дисков. Он, кстати, один из наиболее распространенных рэйдов. Он работает быстро и может хранить много данных (в отличие от первого рэйда, например).
В RAID 5 данные не копируются между всеми дисками, а как в RAID 0 последовательно записываются частями на каждый из дисков, но с одним дополнением - к данным так же равномерно записывается контрольная сумма, которая называется parity, которая нужна для восстановления данных в случае, если один из дисков отвалится.
Важный недостаток RAID 5 в том, что это контрольная сумма занимает немало места. Например, если у вас 4 диска суммарным объемом в 4 терабайта, то использовать под хранение данных вы сможете только 3 терабайта - что около 75%. Остальное займет как раз контрольная сумма.
RAID 10
Подходим к финалу - десятый рейд. Но не спешите, не такой уж он и десятый. Цифру 10 он имеет потому, что с точки зрения технологии, сочетает в себе функциональность RAID 1 и RAID 0.
Создатели технологии уверены, что 1 + 0 = 10. Не будем их расстраивать, и разберемся в технологии.
Для десятого рейда вам понадобится минимум 4 диска или больше, но всегда их количество должно быть четным.
Говоря простым языком, 4 диска делятся на 2 группы, по 2 диска, и каждая из групп объединяется в отказоустойчивый RAID 1. Тем самым, мы имеем 2 зеркальных RAID 1 массива, которые в свою очередь, объединяются в RAID 0 массив - ну вы помните, где данные частями записываются на каждый из дисков. Только вместо дисков у нас по первому рэйду.
Тем самым, 10ый рэйд имеет все скоростные преимущества RAID 0 и преимущество надежности RAID 1, но стоит как чугунный мост, так как опять же, под реальное хранение данных вы сможете использовать только 50% от общего объема всех дисков.