본문으로 건너뛰기

Infinity Sharding Paradigm

Understanding Split Merge in TON Blockchain​

TON(Telegram Open Network) 블록체인은 블록체인의 확장성과 효율성을 위한 혁신적인 개념을 도입합니다. 그 중 하나가 블록체인 아키텍처의 핵심인 Split Merge 기능입니다. 이 짧은 글에서는 무한 샤딩 패러다임(ISP) 내에서의 역할에 중점을 두고 TON 블록체인의 Split Merge의 핵심 측면을 살펴봅니다.

무한 샤딩 패러다임(ISP)과 그 적용​

ISP는 TON 블록체인 설계의 기초가 되며, 각 계정을 별도의 "계정체인"의 일부로 취급합니다. 이러한 계정체인들은 효율성을 위해 샤드체인 블록으로 집계됩니다. 샤드체인의 상태는 모든 계정체인의 상태로 구성됩니다. 따라서 샤드체인 블록은 본질적으로 할당된 계정들의 가상 블록의 모음입니다.

  • ShardState: Hashmap(n, AccountState)로 근사됨, 여기서 n은 account_id의 비트 길이입니다.
  • ShardBlock: Hashmap(n, AccountBlock)으로 근사됨.

각 샤드체인, 더 정확히는 각 샤드체인 블록은 workchain_id와 account_id의 이진 접두사 s의 조합으로 식별됩니다.

분할 또는 병합을 결정하는 알고리즘​

검증자들은 다음과 같은 방식으로 샤드를 분할하거나 병합할지 결정합니다:

  1. 각 블록에 대해 블록 크기, 가스 소비량, lt 델타가 계산됩니다.
  2. 이러한 값들을 사용하여 블록이 과부하 또는 부족부하 상태인지 판단할 수 있습니다.
  3. 각 샤드는 부족부하와 과부하 이력을 유지합니다. 최근 블록들이 충분히 부족부하 또는 과부하 상태였다면, want_merge 또는 want_split 플래그가 설정됩니다.
  4. 검증자들은 이러한 플래그를 사용하여 샤드를 병합하거나 분할합니다.

1. 현재 블록 상태 평가​

각 블록은 다음과 같은 매개변수를 가집니다. 이들은 과부하와 부족부하를 판단하는 데 사용됩니다.

  1. 블록 크기 추정 - 실제 블록 크기가 아닌, 병합 중에 계산된 추정치입니다.
  2. 가스 소비량 - 모든 트랜잭션에서 소비된 총 가스량(ticktock 및 mint/recover 특수 트랜잭션 제외).
  3. Lt 델타 - 블록의 시작 lt와 종료 lt의 차이.

2. 블록 제한과 분류​

블록 제한은 구성 매개변수 22와 23에서 로드됩니다. 세 가지 매개변수 각각은 부족부하, 소프트, 하드의 세 가지 제한을 가집니다:

  1. 블록 크기: 128/256/512 KiB.
  2. 가스 소비량: 베이스체인에서 2M/10M/20M, 마스터체인에서 200K/1M/2.5M.
  3. Lt 델타: 1000/5000/10000. 또한 (soft + hard) / 2와 같은 중간 제한도 있습니다.

크기, 가스, lt 델타의 세 매개변수를 다음과 같이 분류합니다:

  • 0 - 부족부하 제한에 도달하지 않음.
  • 1 - 부족부하 제한을 초과함.
  • 2 - 소프트 제한을 초과함.
  • 3 - 중간 제한을 초과함.
  • 4 - 하드 제한을 초과함.

블록 분류는 크기 분류, 가스 분류, lt 델타 분류 중 최대값입니다. 예를 들어: 크기 분류가 2, 가스 분류가 3, lt 델타 분류가 1이면, 최종 블록 분류는 3입니다.

  • 블록 분류가 0(부족부하)일 때, 블록은 형제와 병합하려는 경향이 있습니다.
  • 블록 분류가 2(소프트 제한 도달)일 때, 병합기는 내부 메시지 처리를 중지합니다. 블록은 분할하려는 경향이 있습니다.
  • 블록 분류가 3(중간 제한 도달)일 때, 병합기는 외부 메시지 처리를 중지합니다.

3. 과부하 또는 부족부하 결정​

블록을 분류한 후, 병합기는 과부하와 부족부하 조건을 확인합니다. 아웃바운드 메시지 큐의 크기와 디스패치 큐 처리 상태도 고려됩니다.

  • 블록 클래스가 ≥ 2(소프트)이고 메시지 큐 크기가 ≤ SPLIT_MAX_QUEUE_SIZE = 100000이면 블록은 과부하 상태입니다.
  • 디스패치 큐에서 처리된 총 메시지의 제한에 도달했고 메시지 큐 크기가 ≤ SPLIT_MAX_QUEUE_SIZE = 100000이면 블록은 과부하 상태입니다.
  • 블록 클래스가 0(부족부하)이고 메시지 큐 크기가 ≤ MERGE_MAX_QUEUE_SIZE = 2047이면 블록은 부족부하 상태입니다.
  • 메시지 큐 크기가 ≥ FORCE_SPLIT_QUEUE_SIZE = 4096이고 ≤ SPLIT_MAX_QUEUE_SIZE = 100000이면 블록은 과부하 상태입니다.

4. 분할 또는 병합 결정​

각 블록은 부족부하와 과부하 이력을 유지합니다 - 이는 최근 64개 블록의 부족부하/과부하 상태를 나타내는 64비트 마스크입니다. 이는 분할 또는 병합을 결정하는 데 사용됩니다.

부족부하와 과부하 이력은 다음과 같이 계산되는 가중치를 가집니다: one_bits(mask & 0xffff) * 3 + one_bits(mask & 0xffff0000) * 2 + one_bits(mask & 0xffff00000000) - (3 + 2 + 1) * 16 * 2 / 3 (여기서 one_bits는 마스크의 1-비트 수이며, 하위 비트는 가장 최근의 블록에 해당합니다).

부족부하 또는 과부하 이력의 가중치가 음수가 아닐 때, want_merge 또는 want_split 플래그가 설정됩니다.

5. 최종 결정​

검증자들은 want_split과 want_merge 플래그 및 워크체인 구성 매개변수를 사용하여 샤드를 분할하거나 병합할지 결정합니다.

  • 샤드의 깊이가 < min_split이면 분할됩니다.
  • 샤드의 깊이가 > max_split이면 병합됩니다.
  • 깊이가 min_split인 샤드는 병합할 수 없고, 깊이가 max_split인 샤드는 분할할 수 없습니다.
  • 블록에 want_split 플래그가 있으면 샤드가 분할됩니다.
  • 블록과 그 형제에 want_merge 플래그가 있으면 샤드가 병합됩니다.

샤드는 결정이 이루어진 후 split_merge_delay = 100초 후에 분할 및 병합됩니다.

메시지와 인스턴트 하이퍼큐브 라우팅(Instant Hypercube Routing)​

무한 샤딩 패러다임에서 각 계정(또는 스마트 계약)은 별도의 샤드체인에 있는 것처럼 취급됩니다. 계정 간의 상호작용은 계정이 액터로서 작동하는 액터 모델의 일부인 메시지 전송을 통해서만 이루어집니다. 샤드체인 간의 효율적인 메시징 시스템은 TON 블록체인의 운영에 매우 중요합니다. TON의 특징은 인스턴트 하이퍼큐브 라우팅으로, 이는 샤드체인 간의 빠른 메시지 전달과 처리를 가능하게 하여, 하나의 샤드체인 블록에서 생성된 메시지가 시스템의 수와 관계없이 대상 샤드체인의 다음 블록에서 처리되도록 보장합니다.

샤딩 예시​

제공된 그래픽 도식에서:

  • 워크체인의 샤드는 시간별로 구분되어 점선으로 표시됩니다.
  • 블록 222, 223, 224는 seqno=102인 마스터체인 블록과 관련이 있습니다. 여기서 222는 하나의 샤드에 있고, 223과 224는 다른 샤드에 있습니다.
  • 분할 또는 병합 이벤트가 발생하면, 영향을 받는 샤드는 다음 마스터체인 블록까지 일시 중지됩니다.

요약하면, TON 블록체인의 Split Merge는 블록체인 네트워크의 확장성과 상호작용을 향상시키는 복잡하지만 효율적인 메커니즘입니다. 이는 효율성과 전역 일관성을 강조하면서 일반적인 블록체인 과제를 해결하는 TON의 접근 방식을 보여줍니다.

샤딩 상세 정보​

샤드체인의 분할 및 비분할 부분​

샤드체인 블록과 상태는 두 부분으로 나뉩니다:

  1. 분할 부분: ISP 형식을 준수하며, 계정별 데이터를 포함합니다.
  2. 비분할 부분: 블록과 다른 블록 및 외부 세계와의 상호작용과 관련된 데이터를 포함합니다.

다른 블록과의 상호작용​

비분할 부분은 내부 및 외부 로컬 일관성 조건으로 축소되는 전역 일관성을 보장하는 데 중요합니다. 다음과 같은 경우에 중요합니다:

  • 샤드체인 간의 메시지 전달.
  • 여러 샤드체인이 관련된 트랜잭션.
  • 전달 보장 및 블록의 초기 상태를 이전 블록과 대조하여 검증.

인바운드 및 아웃바운드 메시지​

샤드체인 블록의 비분할 부분의 주요 구성요소는 다음과 같습니다:

  • InMsgDescr: 블록으로 가져온 모든 메시지의 설명(즉, 블록에 포함된 트랜잭션에 의해 처리되거나, Hypercube Routing이 지시한 경로를 따라 이동하는 일시적인 메시지의 경우 출력 큐로 전달됨).
  • OutMsgDescr: 블록에서 내보내거나 생성한 모든 메시지의 설명(즉, 블록에 포함된 트랜잭션에 의해 생성된 메시지이거나, 현재 샤드체인에 속하지 않는 대상을 가진 InMsgDescr에서 전달된 일시적인 메시지).

블록 헤더와 검증자 서명​

블록 헤더는 또 다른 비분할(non-split) 구성 요소로, 중요한 정보를 포함합니다. 예를 들어 workchain_id, account_ids의 바이너리 접두사, 블록 시퀀스 번호(이전 블록들의 시퀀스 번호보다 큰 최소의 음수가 아닌 정수로 정의됨), 논리적 시간, 그리고 생성 시의 유닉스 시간 등이 있습니다. 또한, 바로 직전 블록(또는 샤드체인 병합 이벤트가 있는 경우 두 개의 직전 블록) 해시, 초기 및 최종 상태(현재 블록 처리 직전과 직후의 샤드체인 상태) 해시, 그리고 샤드체인 블록 생성 시점에 알려진 최신 마스터체인 블록 해시를 포함합니다.
검증자 서명은 서명되지 않은 블록에 추가되어 서명된 블록을 형성합니다.

아웃바운드 메시지 큐​

샤드체인 상태의 OutMsgQueue는 중요한 비분할(non-split) 구성 요소입니다. 이 큐는 OutMsgDescr에 포함된 전달되지 않은 메시지들을 담고 있습니다. 이러한 메시지들은 해당 상태로 이어진 마지막 샤드체인 블록 또는 그 이전 블록 중 하나에 의해 생성됩니다.
처음에는 모든 출력 메시지가 OutMsgQueue에 포함되어 저장되며, 대상지로 처리되거나 전달될 때까지 대기합니다.

샤드 분할 및 병합 메커니즘​

동적 샤딩의 맥락에서 샤드 구성은 분할(split) 및 병합(merge) 이벤트로 인해 변경될 수 있습니다. 이러한 이벤트는 마스터체인 블록과 동기화됩니다. 예를 들어, 분할 또는 병합이 발생하면 관련 샤드는 다음 마스터체인 블록을 기다린 후 진행됩니다.

참고 자료​