Перейти к основному содержимому

Парадигма бесконечного шардинга

warning

Эта страница переведена сообществом на русский язык, но нуждается в улучшениях. Если вы хотите принять участие в переводе свяжитесь с @alexgton.

Понимание разделенного слияния в блокчейне TON​

Блокчейн TON (The Open Network) представляет инновационные концепции масштабируемости и эффективности блокчейна. Одной из таких концепций является функциональность разделения и объединения, которая является неотъемлемой частью его архитектуры блокчейна. В этой короткой статье рассматриваются ключевые аспекты разделения и объединения в блокчейне TON с упором на его роль в парадигме бесконечного шардинга (Infinite Sharding Paradigm - ISP).

Парадигма бесконечного шардинга (ISP) и ее применение​

ISP лежит в основе дизайна блокчейна TON, рассматривая каждый аккаунт как часть своего отдельного "аккаунтчейна". Затем эти аккаунтчейны объединяются в блоки шардчейна для эффективности. Состояние шардчейна включает в себя состояния всех его аккаунтчейнов. Таким образом, блок шардчейна по сути представляет собой набор виртуальных блоков аккаунтов, назначенных ему.

  • ShardState: приближенно как Hashmap(n, AccountState), где n — это длина бит account_id.
  • ShardBlock: приближенно как Hashmap(n, AccountBlock).

Каждый шардчейн или, точнее, каждый блок шардчейна идентифицируется комбинацией workchain_id и двоичного префикса s из account_id.

Алгоритм принятия решения о разделении или слиянии​

Валидаторы решают, разделять или сливать шарды, следующим образом:

  1. Для каждого блока вычисляются размер блока, расход газа и изменение lt.
  2. Используя эти значения, блоки можно считать перегруженными или недогруженными.
  3. Каждый шард хранит историю недогрузки и перегрузки. Если достаточное количество недавних блоков были недогружены или перегружены, устанавливается флаг want_merge или want_split.
  4. Валидаторы объединяют или разделяют шарды, используя эти флаги.

1. Оценка текущего состояния блока​

Каждый блок имеет следующие параметры. Они используются для определения перегрузки и недогрузки.

  1. Оценка размера блока - не фактический размер блока, а оценка, рассчитанная во время сопоставления.
  2. Потребление газа - общее количество газа, потребленного во всех транзакциях (за исключением специальных транзакций ticktock и mint/recover).
  3. Lt delta - разница между началом и концом lt блока.

2. Ограничения блоков и классификация​

Ограничения блоков загружаются из параметров конфигурации 22 и 23. Каждый из трех параметров имеет три ограничения: недогрузка, мягкое и жесткое:

  1. Размер блока: 128/256/512 KiB.
  2. Потребление газа: 2M/10M/20M в бейсчейне, 200K/1M/2.5M в мастерчейне.
  3. Lt delta: 1000/5000/10000. Также есть средний предел, который равен (soft + hard) / 2.

Мы классифицируем три параметра (размер, газ и lt delta) по категориям:

  • 0 - не достигнут предел допустимой нагрузки.
  • 1 - превышен предел допустимой нагрузки.
  • 2 - превышен мягкий предел.
  • 3 - превышен средний предел.
  • 4 - превышен жесткий предел.

Классификация блоков - максимальная ("Классификация по размеру", "Классификация по газу", "Классификация по lt delta\`). Например: если классификация по размеру равна 2, классификация по газу равна 3, классификация по lt delta равна 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 секунд после принятия решения.

Сообщения и мгновенная маршрутизация гиперкуба (мгновенная маршрутизация гиперкуба)​

В парадигме бесконечного шардинга каждый аккаунт (или смарт-контракт) рассматривается так, как если бы он сам находился в отдельном шардчейне. Взаимодействие между аккаунтами происходит исключительно посредством отправки сообщений, что является частью модели субъекта, где аккаунты выступают в качестве субъектов. Эффективная система обмена сообщениями между шардчейнами имеет решающее значение для работы блокчейна TON. Особенностью TON является мгновенная маршрутизация гиперкуба, которая обеспечивает быструю доставку и обработку сообщений между шардчейнами, гарантируя, что сообщения, созданные в блоке одного шардчейна, обрабатываются в следующем блоке целевого шардчейна, независимо от их количества в системе.

Пример шардинга​

На представленной графической схеме:

  • Шарды воркчейна разделены по времени и обозначены пунктирной линией.
  • Блоки 222, 223 и 224 относятся к блоку мастерчейна с seqno=102. Здесь 222 находится в одном шарде, а 223 и 224 — в другом.
  • Если происходит событие разделения или слияния, затронутые шарды приостанавливаются до следующего блока мастерчейна.

Подводя итог, можно сказать, что разделение и слияние в блокчейне TON — это сложный, но эффективный механизм, который повышает масштабируемость и взаимодействие в сети блокчейнов. Он иллюстрирует подход TON к решению общих проблем блокчейнов, подчеркивая эффективность и глобальную согласованность.

Подробности шардинга​

Разделенные и неразделенные части шардчейна​

Блок и состояние шардчейна делятся на две части:

  1. Разделенная часть: соблюдает форму провайдера (ISP), содержащую специфические данные аккаунтов.
  2. Неразделенная часть: включает данные, относящиеся к взаимодействию блока с другими блоками и внешним миром.

Взаимодействие с другими блоками​

Неразделенные части имеют решающее значение для обеспечения глобальной согласованности, сведенной к внутренним и внешним локальным условиям согласованности. Они важны для:

  • Пересылки сообщений между шардчейнами.
  • Транзакций с участием нескольких шардчейнов.
  • Гарантий доставки и проверки начального состояния блока по сравнению с его предшественником.

Входящие и исходящие сообщения​

Ключевые компоненты неразделенной части блока шардчейна включают:

  • InMsgDescr: Описания всех сообщений, импортированных в блок (т. е. либо обработанных транзакцией, включенной в блок, либо перенаправленных в выходную очередь, в случае транзитного сообщения, перемещающегося по пути, продиктованному маршрутизацией гиперкуба).
  • OutMsgDescr: Описания всех сообщений, экспортированных или сгенерированных блоком (т. е. либо сообщения, сгенерированные транзакцией, включенной в блок, либо транзитные сообщения с пунктом назначения, не принадлежащим текущему шардчейну, перенаправленные из InMsgDescr).

Заголовок блока и подписи валидатора​

Заголовок блока, еще один неразделенный компонент, содержит важную информацию, такую ​​как workchain_id, двоичный префикс account_ids, порядковый номер блока (определяемый как наименьшее неотрицательное целое число, большее порядковых номеров его предшественников), логическое время и генерацию unixtime. Он также содержит хэш непосредственного предшественника блока (или двух его непосредственных предшественников в случае предшествующего события слияния шардчейна), хэши его начального и конечного состояний (т. е. состояния шардчейна непосредственно перед и сразу после обработки текущего блока) и хэш самого последнего блока мастерчейна, известного на момент генерации блока шардчейна. Подписи валидатора добавляются к неподписанному блоку, образуя подписанный блок.

Исходящая очередь сообщений​

OutMsgQueue в состоянии щардчейна является критической неразделенной частью. Она содержит недоставленные сообщения, включенные в OutMsgDescr, либо последним блоком шардчейна, ведущим к этому состоянию, либо одним из его предшественников. Изначально каждое исходящее сообщение включается в OutMsgQueue и хранится там, пока они не будут обработаны или доставлены по назначению.

Механика разделения и слияния шардов​

В контексте динамического шардинга конфигурации шардов могут меняться из-за событий разделения и слияния. Эти события синхронизируются с блоком мастерчейна. Например, если происходит разделение или слияние, затронутые шарды ждут следующего блока мастерчейна, прежде чем продолжить.

См. также​