Разделение и объединение шардчейнов


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

Конфигурация шарда

Напомним, что в любой момент времени каждый воркчейн w разбивается на один или несколько шардчейнов (w, s) (см. 2.1.8). Эти шардчейны могут быть представлены листьями двоичного дерева, корнем (w, 0) и каждым не-листовым узлом (w, s), имеющим дочерние элементы (w, s.0) и (w, s.1). Таким образом, каждая учетная запись в воркчейне w назначается ровно одному шарду, и все, кто знают текущую конфигурацию шардчейна, могут определить сегмент (w, s), содержащий учетную запись account_id: это единственный сегмент с двоичной строкой s, являющейся префиксом account_id.

Конфигурация шарда — то есть это двоичное дерево шарда или совокупность всех активных (w, s) для данного w (соответствующего листьям двоичного дерева шарда) — является частью состояния мастерчейна и доступна всем, кто отслеживает мастерчейн.

Самая последняя конфигурация и состояние шарда

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

Объявление и внесение изменений в конфигурацию шарда

Конфигурацию шарда можно изменить двумя способами: шард (w, s) можно разделить на два шарда (w, s.0) и (w, s.1), либо два «родственных» шарда (w, s .0) и (w, s.1) можно объединить в один шард (w, s).

Эти операции разделения/слияния объявляются несколькими блоками заранее, сначала в «заголовках» соответствующих блоков шардчейна, а затем в блоке мастерчейна, который относится к этим блокам шардчейна. Такое заблаговременное объявление позволяет всем заинтересованным сторонам подготовиться к запланированному изменению (например, создать оверлейную многоадресную сеть для распределения новых блоков вновь созданных шардчейнов).

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

Группы задач валидаторов для новых шардчейнов

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

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

Если некоторые валидаторы будут временно или навсегда забанены из-за подписания невалидных блоков, то они автоматически исключаются из всех групп задач.

Обратите внимание, что любой активный шард (w, s) будет либо наследником некоторого однозначно определенного исходного шарда (w, s’), то есть, s’ является префиксом s, либо он будет корнем поддерева исходных шардов (w, s’), где s будет префиксом каждого s’. В первом случае просто берется и удваивается группа задач исходного шарда (w, s’), в результате чего получается группа задач нового шарда (w, s). Во втором случае группа задач нового шарда (w, s) будет объединением групп задач всех исходных шардов (w, s ‘), которые являются наследниками (w, s) в дереве шардов.

Таким образом, для каждого активного шарда (w, s) назначается четко определенное подмножество валидаторов (группа задач). При разделении оба результирующих шарда наследуют всю группу задач от исходного шарда. При объединении двух шардчейнов соответствующие группы задач также объединяются.

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

Ограничение операций разделения/объединения в период ответственности исходных групп задач
В конечном итоге будет учтена новая конфигурация шарда, и для каждого шарда будут автоматически назначены новые выделенные подмножества (группы задач) валидаторов. Прежде чем это произойдет, необходимо наложить определенный лимит на операции разделения/слияния; в противном случае исходная группа задач может закончить проверку 2k шардчейнов для большого k одновременно, если исходный шард быстро разделится на 2k новых шардчейнов.

Это достигается путем наложения ограничений на то, насколько активная конфигурация шарда может быть удалена от исходной конфигурации шарда (той, которая используется для выбора групп задач валидаторов, отвечающих за проверку блоков в настоящее время). Например, может быть задано требование, чтобы расстояние в дереве шардов от активного шарда (w, s) до исходного шарда (w, s’) не превышало 3, если s’ является предшественником s (т. е. S’ является префиксом двоичной строки s), и не должно превышать 2, если s’ является преемником s (т. е. s является префиксом s’). В противном случае операция разделения или слияния не будет разрешена.

Грубо говоря, в данном случае вводится ограничение на количество процессов разделения (например, три) или объединения (например, два) шарда в течение периода ответственности данного набора валидаторов. Кроме того, после создания шарда в результате слияния или разделения его нельзя перенастроить в течение некоторого периода времени (некоторого количества блоков).

Определение необходимости операций разделения

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

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

Выполнение операций разделения

После добавления флага «выполнить разделение» в блок B шардчейна (w, s) в этом шардчейне не может быть последующего блока B’. Вместо этого будут созданы блоки B’0 и B’1 шардчейнов (w, s.0) и (w, s.1), соответственно, причем оба они будут ссылаться на блок B как на предыдущий блок (и у обоих шардчейнов в заголовке будет флаг с указанием, что шард только что был разделен). Следующий блок мастерчейна будет содержать хэши блоков B’0 и B’1 новых шардчейнов; в блоке не может содержаться хэш нового блока шардчейна B’ (w, s), потому что событие «выполнить разделение» уже было зафиксировано в предыдущем блоке мастерчейна.

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

Определение необходимости операций слияния

Необходимость операций слияния шардчейнов также определяется некоторыми формальными условиями (например, если в 64 последовательных блоках сумма размеров двух блоков родственных шардчейнов не превышает 60% от максимального размера блока). Формальные условия также должны учитывать общий объем газа, израсходованный этими блоками, и сравнивать его с текущим лимитом газа на блок, в противном случае блоки могут оказаться небольшими из-за наличия некоторых транзакций, требующих большого объема вычислений, которые препятствуют включению большего количества транзакций.

Эти условия отслеживаются группами задач валидаторов обоих родственных шардов (w, s.0) и (w, s.1). Обратите внимание, что родственные шардчейны обязательно являются соседями с точки зрения маршрутизации в гиперкубе, поэтому валидаторы из группы задач любого шарда в любом случае будут в какой-то степени контролировать родственный шард.

Если эти условия выполнены, одна из подгрупп валидаторов может предложить другой объединиться, отправив специальное сообщение. Затем они объединяются во временную «объединенную группу задач» с объединенным членством, способную запускать согласованные алгоритмы BFT и при необходимости распространять обновления блоков и блоков-кандидатов.

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

Выполнение операций слияния

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