Распространение блока турбины

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

Во время своего слота узел-лидер распределяет кусочки между узлами-валидаторами в первой окрестности (уровень 0). Каждый валидатор делится своими данными в своем окружении, но также повторно передает фрагменты на один узел в некоторых соседствах на следующем уровне (уровень 1). Каждый из узлов уровня 1 делится своими данными со своими одноранговыми узлами по соседству и повторно передает их узлам следующего уровня и т. д., пока все узлы в кластере не получат все фрагменты.

Назначение соседства — взвешенный выбор

Чтобы разветвление плоскости данных работало, весь кластер должен согласовать, как кластер делится на окрестности. Для этого все признанные узлы валидатора (одноранговые узлы TVU) сортируются по доле и сохраняются в списке. Затем этот список индексируется различными способами для определения границ соседства и повторной передачи одноранговых узлов. Например, лидер просто выберет первые узлы, составляющие уровень 0. Они автоматически станут держателями самых высоких ставок, что позволит лидеру первым вернуться к лидеру с наибольшим количеством голосов. Узлы уровня 0 и нижнего уровня используют одну и ту же логику для поиска своих соседей и одноранговых узлов следующего уровня.

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

Слой и структура окружения

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

Как упоминалось выше, каждый узел на уровне должен транслировать свои фрагменты только своим соседям и ровно 1 узлу в некоторых окрестностях следующего уровня, а не каждому узлу TVU в кластере. Хороший способ представить это так: уровень 0 начинается с 1 соседства с узлами разветвления, слой 1 добавляет соседства разветвления, каждое из которых имеет узлы разветвления, а слой 2 будет иметь «разветвление * количество узлов в слое 1» и так далее.

Таким образом, каждый узел должен взаимодействовать не более чем с 2 * DATA_PLANE_FANOUT - 1 узлами.

На следующей диаграмме показано, как Лидер отправляет фрагменты с разветвлением 2 в Окрестность 0 на уровне 0 и как узлы в Окрестности 0 обмениваются своими данными друг с другом.

На следующей диаграмме показано, как Окрестности 0 разветвляются на Окрестности 1 и 2.

Наконец, на следующей диаграмме показан двухуровневый кластер с разветвлением, равным 2.

Значения конфигурации

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

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

Расчет требуемой скорости FEC

Turbine полагается на повторную передачу пакетов между валидаторами. Из-за повторной передачи, любая потеря пакетов в сети усугубляется, и увеличивается вероятность того, что пакет не достигнет адресата на каждом прыжке. Скорость FEC должна учитывать всю сеть. потеря пакетов и глубина распространения.

Уничтоженная группа — это набор данных и пакетов кодирования, которые можно использовать. реконструировать друг друга. У каждой группы клоков есть шанс провала, на основе вероятности того, что количество пакетов курс ФЭК. Если валидатору не удается восстановить группу уничтожения, тогда блок не может быть реконструирован, и валидатору приходится полагаться на ремонте починить блоки.

Вероятность отказа группы уничтожения может быть вычислена с помощью биномиальное распределение. Если скорость FEC равна «16:4», то размер группы равно 20, и по крайней мере 4 фрагмента должны выйти из строя, чтобы группа вышла из строя. Что равно сумме вероятностей отказа 4 или более трасс. из 20.

Вероятность успеха блока в турбине:

• Вероятность сбоя пакета: P = 1 - (1 - network_packet_loss_rate)^2
• Скорость FEC: K:M
• Количество испытаний: N = K + M
• Частота отказов группы Shred: S = СУММА i=0 -> M для бинома (prob_failure = P, пробы = N, неудачи = i)
• Клочков на блок: G
• Вероятность успеха блока: B = (1 - S) ^ (G / N)
• Биномиальное распределение для ровно i результатов с вероятностью P в N испытаниях определяется как (N выбирают i) * P^i * (1 - P)^(N-i)

Например:

• Скорость потери сетевых пакетов составляет 15%.
• Сеть 50k tps генерирует 6400 фрагментов в секунду.
• Скорость FEC увеличивает общее количество фрагментов на блок на коэффициент FEC.

Со скоростью FEC: 16:4

• G = 8000
• P = 1 - 0,85 * 0,85 = 1 - 0,7225 = 0,2775
• S = СУММА i=0 -> 4 для бинома (prob_failure = 0,2775, испытаний = 20, отказов = i) = 0,689414
• В = (1 - 0,689) ^ (8000/20) = 10^-203

Со скоростью FEC 16:16

• G = 12800
• S = СУММА i=0 -> 32 для бинома (prob_failure = 0,2775, испытаний = 64, отказов = i) = 0,002132
• В = (1 - 0,002132) ^ (12800/32) = 0,42583

Со скоростью FEC 32:32

• G = 12800
• S = СУММА i=0 -> 32 для бинома (prob_failure = 0,2775, испытаний = 64, отказов = i) = 0,000048
• В = (1 - 0,000048) ^ (12800/64) = 0,99045

Окрестности

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