PPPT: 푸시풀 위상 전환을 통한 가십서브 오버헤드에 맞서기

작성자: @cskiraly

참고: PPPT의 초기 버전과 여기에서 논의되는 알고리즘은 2024년 5월 FullDAS 게시물 에 소개되었습니다. 측정값이 포함된 버전도 2025년 1월에 발표 및 슬라이드 형태로 배포 되었습니다.
최근 여러 연구 그룹이 유사한 주제에 대한 연구를 시작하며 다양한 토론 포럼에서 아이디어를 공유하고 있습니다. 그중 훌륭한 연구 중 하나가 "GossipSub v2.0"이라는 이름으로 최근 발표되었습니다. ProbeLab 팀 또한 관련 표준화 활동에 참여하고 있습니다. 본 게시물에서는 이러한 접근 방식을 직접 비교하지는 않지만, 추후 논의를 위해 남겨두겠습니다(예: 아래 댓글).

이전 게시물에서는 일괄 게시를 소개하면서 DAS 분산에서 상당한 지연 시간 개선을 보여주고 게시자의 대역폭 병목 현상을 해결하는 방법을 보여주었습니다.

소스에서 일괄 게시를 구현하더라도 GossipSub은 중복으로 인해 P2P 재배포 과정에서 큰 대역폭 오버헤드를 발생시킵니다. 이 글에서는 이 문제를 해결하고 오버헤드를 줄이거나 완전히 제거하는 방법을 제시합니다.

물론 공짜 점심은 없습니다. 여기서 소개하는 기술에는 여러 가지 타협이 따르는데, 이에 대해서도 자세히 설명하겠습니다.

가십서브 오버헤드

GossipSub은 "적당한 증폭 계수와 우수한 확장성을 갖춘 범용 pubsub 프로토콜" 로 소개되었습니다. 대역폭 효율성은 기존 FloodSub보다 훨씬 뛰어나지만, 여전히 상당한 대역폭 오버헤드가 발생하여 일부 이더리움 사용 사례에 대한 우려를 불러일으킵니다.

GossipSub은 우리가 푸시(push)와 풀(pull)이라고 부르는 두 가지 주요 기술을 기반으로 합니다.

1. 주어진 주제에 대해 GossipSub은 약 D D 정도의 무작위 메시를 구성하고 이 메시를 따라 적극적으로 메시지를 푸시합니다 .

2. 또한 더 큰 이웃 그래프를 따라 "HAVE" 메타데이터를 배포합니다(이것은 소위 IHAVE 메시지를 사용하는 GossipSub의 가십 부분입니다). 그리고 이 정보를 기반으로 PULL을 실행하여 누락된 메시지를 복구합니다.

GossipSub의 기본 버전 에서는 PUSH가 빠른 전송에 사용되는 반면, PULL은 손실 복구에만 사용됩니다 . 피어로부터 메시지를 수신한 노드는 D-1 D − 1 개의 모든 메시 피어(수신한 피어에게 다시 전송하지 않으므로 D-1 D − 1 )에게 전송하기 위해 대기열에 넣습니다. 이는 첫 번째 수신 시 동작입니다. 다른 수신은 중복으로 간주되어 쉽게 필터링됩니다. 여기서 우리가 답하고자 하는 질문은 다음과 같습니다.

중복된 항목이 몇 개나 있나요 ? 성능을 저하시키지 않고(또는 약간 저하시키지 않고) 이 개수를 줄이기 위해 무엇을 할 수 있나요?

중복 수 대 사본 수

때로는 사본이 중복보다 더 쉽게 추론될 수 있습니다. 노드가 메시지 사본 C 개 를 수신하면, 첫 번째 사본만 유용하고, 그중 C - 1 개 는 중복입니다.

보낸 사본 수

간단히 말해서, 토픽에 구독된 N개의 노드 각각은 "첫 번째 수신"을 한 후 D-1개의 D - 1개의 사본을 전송합니다. 따라서 시스템 전체로 전송되는 사본은 N * (D-1) N ∗ ( D - 1 ) 개입니다. 이 중 N-1 개의 N - 1 개만 유용하며, 나머지는 중복되어야 합니다.

받은 사본 수

노드가 수신하는 사본의 평균 개수도 D-1 D - 1 로 동일 합니다. 모든 노드가 보내고 받는 메시지 수를 더하면 같은 개수가 나오기 때문입니다. 그러나 D-1 D - 1은 단지 평균일 뿐입니다. 수신된 사본의 개수는 노드마다 크게 다를 수 있습니다. 실제로는 1 1 에서 D D 사이입니다(실제로는 노드의 차수가 D D 와 약간 다를 수 있으므로 수신된 사본의 개수도 비트(Bit) 더 많을 수 있습니다).

중복이 거의 없는 행운의 노드는 어디인가요?

직관은 간단합니다. 메시지가 소스에서 먼저 전송되면 D D 노드가 이를 받습니다. 이들은 1번째 홉 에서 이를 받는 노드입니다. 메시의 무작위 구성으로 인해 이들이 메시 이웃일 확률은 다소 낮습니다. 1번째 홉 노드 중 두 개가 같은 노드로 전송할 확률도 낮습니다. 따라서 모든 이웃(소스로 다시 전송하는 경우 제외)에 전송할 때 2번째 홉 노드는 모두 첫 번째 사본을 받고 다시 전송하지 않습니다. 따라서 1번째 홉 노드는 중복을 거의 받지 않습니다. 1 번째 홉 노드보다 2번째 홉 노드가 더 많고, 이 중 일부(하지만 소수)는 서로 연결되고, 일부 이웃(3번째 홉)도 공통적일 것입니다. 이더리움 클래식(ETC).

확산 과정의 끝, 즉 여러 홉을 거친 후에 는 상황이 매우 다릅니다. 예를 들어 5홉 후에 메시지를 처음 수신한 노드는 여전히 D-1 개의 다른 노드 (D - 1) 에게 메시지를 전송하지만, 이러한 이웃 노드가 이미 메시지를 수신한 노드일 확률, 즉 메시지가 중복될 확률이 상당히 높습니다.

홉 카운트 대 수신된 중복

홉 카운터는 표준 GossipSub 메시지 구조에 포함되지 않지만, nim-libp2p 코드를 수정하여 홉 카운터를 포함시켰습니다. 이를 통해 홉 카운트당 수신된 중복 메시지의 분포에 대한 정보를 쉽게 수집할 수 있습니다. 더 정확히 말하면, 첫 번째 수신된 사본의 홉 카운터를 사용하는데, 이는 소스와의 그래프 거리와 같습니다. 노드는 나중에 다른 사본을 수신하는데, 대개 더 큰 홉 카운트를 가질 것입니다( 링크(Chainlink) 지연 시간의 차이로 인해 더 작은 홉 카운트를 가질 수도 있습니다). 여기서는 단순화를 위해 최단 경로가 아닌 첫 번째 수신의 홉 카운터를 사용합니다.

이 홉 카운터는 실험에서 측정 목적으로만 사용되었으며, 야외에서 사용하기 위한 것이 아닙니다(개인정보 보호 문제는 나중에 다루겠습니다).

아래 그림은 소스에서 노드까지의 거리에 따른 함수로 수신된 메시지 사본 수의 분포를 보여줍니다( firsthops : 처음 발견된 홉 카운터 값).

rxcount_push 990×766 58.7KB

보시다시피, 노드가 메시지를 늦게(첫 번째 홉 수가 많을수록) 수신할수록 첫 번째 수신 후 중복되는 노드가 더 많아집니다. 여기에 노드 수가 첫 번째 홉 수에 따라 거의 기하급수적으로 증가한다는 사실을 더하면, 중복을 제거하려면 확산의 후반 단계에서 제거해야 한다는 것이 분명해집니다. 아래에서는 이를 달성하기 위한 몇 가지 방법을 비교하지만, 그 전에 중복이 발생하지 않는 극단적인 경우를 살펴보겠습니다.

풀 모드

중복을 제거하는 가장 간단한 방법은 PULL 모드만 사용하는 것입니다. 메시지를 수신하면 노드는 D-1 D − 1 IHAVE 메시지를 피어에게 전송합니다. 이는 프로토콜을 약간 변형한 것이지만, 매우 간단합니다 . 풀 모드에서는 각 홉(hop)에 더 많은 시간이 소요됩니다. IHAVE(A->B), IWANT(B->A), 그리고 메시지 자체(A->B)가 단순 PUSH 모드보다 3배의 지연 시간을 추가하기 때문입니다. IHAVE와 IWANT 모드는 트래픽 바이트를 추가로 발생시키지만, 메시지 크기에 따라 무시할 수 있을 정도로 작을 수 있습니다.

다음 그림은 Pull의 경우 중복과 첫 번째 홉 수의 관계를 보여줍니다. 다소 지루하네요.

중복_풀 1028×762 24.7KB

지연 기반 억제

PUSH에서 PULL로 전환하는 것 외에도 오버헤드를 줄일 수 있는 또 다른 방법이 있습니다. 바로 전송을 피하는 것입니다.

중복 메시지의 상당 부분은 실제로 동일한 A-B 링크(Chainlink) 양방향으로 통과하는 메시지에서 발생합니다. 전달 전에 약간의 ( \delta δ ) 지연을 추가하면 중복 메시지가 일부 수신될 수 있으며, 그러면 해당 링크(Chainlink) 에서 D- 1 개 미만 의 복사본을 전송하여 다시 전송하는 것을 피할 수 있습니다. IDONTWANT는 이 차원에서 작동하며, 메시지 검증 전에도 전달 전에 작은 "경고"를 보냅니다.

이 시간 동안 중복 메시지를 수신하면 해당 링크로 다시 전송하지 않습니다. 따라서 일부 노드는 D- 1 개 보다 적은 양의 메시지를 전송합니다. 모든 구현에서 GossipSub 메시지 검증 지연으로 인해 일부 대기 시간이 발생한다는 점에 유의하세요. Nim 구현에서는 이미 이 지연 시간을 사용하여 메시지 전송을 억제하지만, 다른 구현에서는 이를 사용하지 않습니다.

지연 시간-대역폭 균형 이해

위의 모든 소개를 통해 이제 순수한 PUSH와 순수한 PULL의 두 극단 사이의 상충 공간을 매핑하고 결정 논리에 지연을 추가할 수 있는 지점에 도달했습니다.

우리는 4가지 서로 다른 전략을 소개하는데, 각 전략에는 상충관계를 "조정"할 수 있는 매개변수가 있습니다.

• 대기( \delta δ ) : 가장 쉬운 방법은 수신 후 복사본을 전송하기 전에 \delta δ 시간 동안 기다리는 것입니다. 이 시간 동안 중복된 복사본을 수신하면 해당 링크로 다시 전송하지 않습니다. 따라서 노드는 D-1개 (D - 1 개)보다 적은 복사본을 전송할 수 있습니다. 모든 구현에서 gossipsub 메시지 검증 지연으로 인해 일부 대기가 발생한다는 점에 유의하세요. Nim 구현은 이미 이 지연을 사용하여 메시지 전송을 억제하지만, 다른 구현에서는 이를 사용하지 않습니다. (suppressNone)

• 대기 후 풀(Wait-and-Pull, \delta δ ) : 이 전략에서는 다시 \delta δ 시간 동안 대기하지만, 중복된 데이터가 수신되면 전송을 중단하는 데 그치지 않고 PULL 모드로 전환하여 나머지 모든 링크에 IHAVE를 전송합니다. (SuppressIfSeen)

• 푸시-풀( d d ) : 이 전략에서는 D D 개의 이웃이 있지만, 그중 일부에만 푸시(PUSH)를 전송하고 나머지에는 PULL 모드를 사용합니다. d d 매개변수를 사용하여 상충 관계를 설정하여, 무작위로 선택된 d d 개의 피어에 푸시를 전송하는 동시에 나머지 피어에는 IWANT를 전송합니다. (suppressAbove)

• 푸시-풀 위상 전이( d d ) 또는 PPPT: 마지막 변형에서는 홉 카운터에 의존합니다. 노드가 홉 카운터 값이 h h 인 메시지를 처음 수신하면, max(0, dh) 개의 푸시 ( PUSH ) 메시지 를 보내고 나머지 노드 에는 PULL 메시지를 보냅니다. (suppressOnHops)

이 중 마지막 것만 홉 카운터를 사용하며, 나머지는 메시지 형식을 수정하지 않고 구현할 수 있습니다(코드에서 통계 수집을 위해 홉 카운터를 사용합니다). 홉 카운트 노출은 논란의 여지가 있는 주제이므로, 나중에 더 자세히 살펴보겠습니다.

시뮬레이션 시나리오

성능 지표를 도출하기 위해 Shadow와 nim-libp2p 기반 시뮬레이터를 사용합니다. 다음 매개변수를 사용하여 시뮬레이션을 실행합니다.

• 주제에 1000개의 노드가 구독됨

• 1KB의 작은 메시지 크기

• 노드 대역폭을 대칭 20Mbps로 제한합니다.

• p2p 지연 시간 : 이전 그래프에서는 푸시(Push)와 풀(Pull)의 효과를 단순화하기 위해 노드 간 지연 시간을 50ms로 동일하게 설정했습니다. 그러나 이러한 균일성은 부작용을 야기하므로, 다음 그래프에서는 실제 인터넷( RIPE Atlas 데이터베이스 )에서 측정한 지연 시간을 사용하여 각 노드를 지구상의 임의의 위치에 매핑했습니다. 평균 지연 시간은 62ms이지만, 이보다 훨씬 빠른 링크도 많습니다.

다음 그림은 중복과 수신 지연 간의 상충 공간을 보여줍니다. 각 점은 두 가지 측정 기준에 따라 주어진 매개변수를 사용한 주어진 전략의 성능을 나타냅니다.

• x축은 달성된 평균 전달 지연 시간을 나타냅니다(예를 들어 95백분위수 지연 시간에 대해서도 비슷한 그래프를 그릴 수 있습니다). 값이 작을수록 더 좋으며, 왼쪽은 순수 PUSH, 오른쪽은 순수 PULL을 사용합니다.

• y축은 평균 사본 수를 나타냅니다. 값이 작을수록 좋으며, 순수 PULL은 아래쪽(1개 사본 수신)에, 순수 Pull은 위쪽(평균적으로 약 D- 1 개 사본 수신)에 위치합니다.

각 전략의 매개변수를 변경하면 중복과 지연 시간 간의 균형을 이루는 상충 곡선을 그릴 수 있습니다. 예를 들어, 녹색 곡선의 가장 왼쪽 점은 대기 시간이 없음( \delta=0 δ = 0 )을 나타내는 반면, 가장 오른쪽 점은 중복은 감소하지만 대기 시간이 길어지면 지연 시간이 증가함을 나타냅니다 ( \delta=70~ms δ = 70 ). 메시지를 전달하기 전에 m s를 입력하세요.

마찬가지로, 다른 곡선의 경우, 가장 왼쪽 지점은 전략이 발동되지 않도록 매개변수를 설정한 지점입니다. 이는 Wait-and-Pull의 경우 a ( \delta=0 δ = 0 )이고, Push-Pull 및 Push-Pull 위상 전이의 경우 d d 의 큰 값( D D 보다 큼)을 의미합니다.

중복 억제 전략 757×500 30.3KB

대기( \delta δ )는 가장 효과가 낮아서 지연 시간을 늘리는 반면 중복 횟수는 약간만 줄입니다.

Wait-and-Pull( \delta δ )은 훨씬 더 나은 결과를 달성합니다. 실제로 짧은 시간 내에 중복 데이터를 수집하는 것은 명시적인 홉 카운터 없이도 확산 과정의 후반부에 있음을 추정하는 데 사용될 수 있습니다.

푸시풀( d d )은 추정기나 홉 카운트가 필요하지 않은 고정 전략이더라도 인상적인 이득을 제공합니다.

마지막으로, PPPT는 이전의 모든 전략보다 더 나은 성능을 달성하여 지연 시간을 약간만 늘려도 거의 모든 중복 항목을 제거할 수 있고, 지연 시간을 두 배로 늘리면 모든 중복 항목을 제거할 수 있습니다.

논의

위에 제시된 전략들은 가능한 다양한 전략의 예시일 뿐입니다. 이러한 전략들의 조합과 변형은 쉽게 도출될 수 있습니다. 특히 인터넷이라는 이질적인 환경에서 최적의 결과를 제공하는 일반적인 이론은 알려져 있지 않습니다.

저희의 연구는 아직 예비적인 단계이고 평가할 수 있는 부분이 훨씬 더 많습니다(노드 수의 차이, 메시지 크기, 대역폭 제한 차이 이더리움 클래식(ETC)). 하지만 이미 몇 가지 측면을 강조할 수 있습니다.

홉 카운터의 이점은 분명하다

홉 카운터를 추가하면 지연 시간을 낮추면서 중복을 줄이는 데 상당한 이점을 얻을 수 있다는 것은 분명합니다. 시스템 내 중복의 위치를 ​​자세히 분석한 결과, 이는 놀라운 일이 아니며, 홉 카운터가 실제로 푸시(Push)에서 풀(Pull)로 전환하는 좋은 계기가 될 수 있음을 보여줍니다.

고정 전략 성능은 전혀 나쁘지 않습니다.

비트(Bit) 더 놀라운 점은(적어도 저에게는) 고정 전략도 괜찮은 성능을 보인다는 점인데, 홉 카운트 정보가 없어서 성능 곡선이 확실히 떨어지는 듯합니다.

홉 카운트 및 개인 정보 보호

홉 카운트가 게시자 개인 정보 보호를 침해하고 있다는 점도 분명해야 합니다. 애초에 그런 문제가 있었다면 말입니다. libp2p와 GossipSub은 게시자 개인 정보 보호가 문제가 되지 않는 용도로도 사용될 수 있다고 생각합니다. 이더리움 사용 사례에서도 발신자의 익명성을 해제하는 것이 이미 쉬운 경우가 많으며, 이러한 경우 홉 카운트가 이를 크게 어렵게 만듭니다.

홉 카운트는 속일 수 있습니다

홉 카운트의 또 다른 단점은 거짓말하기 쉽다는 것입니다. 또한, 홉 카운트는 피어 스코어링에 포함되어서는 안 됩니다. 부정행위를 위한 추가적인 인센티브를 제공하기 때문입니다. 그럼에도 불구하고, 노드가 홉 카운트에 대해 거짓말을 하면 확산 트리에서 자신의 서브트리 속도만 늦추거나 높일 뿐, 전체적인 효과는 없기 때문에 이는 근본적인 문제는 아니라고 생각합니다.

GossipSub 사용 사례는 다릅니다

중복 완화 전략을 상쇄 공간으로 제시한 데에는 이유가 있습니다. 이더리움에서도 GossipSub은 다양한 사용 사례를 가지고 있기 때문입니다(이더리움 외부에서의 사용은 말할 것도 없습니다). 사용 사례(또는 주제, 메시지 크기)에 따라 서로 다른 전략과 매개변수가 선택될 수 있습니다.

RTT 기반 최적화 동네에 관하여

첫 번째 홉에서 중복이 없다는 우리의 추론은 무작위 이웃(neighborhood)을 가정한다는 점도 언급할 가치가 있습니다. 측정된 RTT(Return to Time)를 기반으로 이웃을 최적화한다는 아이디어가 (문헌이나 토론에서) 종종 등장합니다. 하지만 안타깝게도 이러한 최적화는 오버레이 그래프 구조를 변경하여 첫 번째 홉에서 훨씬 더 많은 중복을 발생시키고, 결과적으로 직경이 커지는 부작용을 초래합니다. RTT 기반 최적화는 신중하게 설계할 수 있지만, 이러한 부작용을 인지하는 것이 중요합니다.

교통량이 많아

그림에서는 메시지 사본을 기준으로 계산했지만, IHAVE 메시지의 오버헤드는 계산하지 않았습니다. 이러한 단순화가 타당한지 여부는 메시지 크기, 메시지 ID 및 IHAVE 메시지 인코딩과의 관계에 따라 달라집니다. 이 부분에서는 몇 가지 최적화 방안이 가능하다는 점에 유의해야 합니다.

• 링크(Chainlink) 에 메시지 빈도가 높으면 개별 IHAVE 메시지를 약간의 추가 지연 시간을 감수하고 단일 메시지로 집계 할 수 있습니다.

• 이 IHAVE 집계는 제어된 추가 대기 시간을 통해 여러 주제에 걸쳐 수행될 수도 있습니다.

• 메시지가 구조화된 메시지 ID 공간 에서 ID를 받을 수 있는 일부 사용 사례에서는 이러한 집계된 IHAVE 메시지를 압축할 수도 있습니다. DAS의 경우, 비트맵 기반 IHAVE 메시지를 제안했지만, 비트맵 기반 압축은 더 일반적인 도구로 사용될 수도 있습니다.

재생산 방법

홉 카운트와 모든 전략은 nim-libp2p의 일부로 구현되었으며, 곧 후속 조치로 분기로 게시될 예정입니다.

이러한 시뮬레이션을 수용하기 위해 저희 시뮬레이션 프레임워크에도 몇 가지 임시 변경 사항이 적용되었으며, 이는 후속 조치로 게시될 예정입니다.