사전 고지: 본 글은 단순 정보 제공을 위해 작성되었고 투자, 법률, 자문 등 어떤 부분에 대해서도 책임을 지지 않습니다. 특정 자산에 대한 투자를 추천하는 것이 아님을 밝히며, 본문의 내용만을 바탕으로 투자에 대한 의사결정을 내리지 마십시오.

Review: Steve Kim, Ethan Lee

본 글은 A41에서 기획하는 앱토스 시리즈의 5편으로, a41이 처음 앱토스에 대해서 다루었을 땐, 앱토스의 백서가 나오지 않았던 상태였기 때문에 a41이 그때 다루지 못했던 내용들과 추가적으로 더 심도 있게 다뤄야 하는 부분들을 중심으로 시리즈를 이어나가고자 한다. 그럼에도 불구하고 글들이 서로 연관되어있기 때문에 처음부터 차례대로 읽어보시는 것을 강력하게 추천드린다.

1편: Introducing Aptos — 모놀리틱 블록체인의 새로운 패러다임

2편: AptosBFT — 확장성과 보안의 합의 할고리즘

3편: Move — 안정적인 구조 속에서 빠르게 실행하라.

4편: 추가적인 확장성을 위한 기술들

5편: Block STM - 어떻게 앱토스는 트랜잭션을 병렬처리 하는가

6편: Narwhal - 앱토스의 멤풀 프로토콜

7편: 앱토스의 토크노믹스와 거버넌스, 그리고 생태계 소개

세 줄 요약

1. Block-STM은 BoHM과 STM에 기반하고 여기에 협업 스케줄러가 추가된 컨트랙트 병렬 처리 엔진이다.

2. Block-STM은 순차적으로 트랜잭션을 실행하는 것과 결과를 같게 만들면서 트랜잭션 처리량을 늘리는 기술이다.

3. Block-STM을 활용하면 앱토스는 최대 16만 TPS를 발생시킬 수 있다.

더 많은 트랜잭션 처리량을 위한 인간의 열망과 노력은 계속된다. 앱토스는 추가적인 개발이 없더라도 다른 블록체인들과 비교해 장점이 명확한 블록체인이다. 앱토스는 현 기술로도 최대 1만 TPS를 기록할 수 있고, 솔리디티보다 안전한 Move라는 프로그래밍 언어를 통해 블록체인의 안전성을 확보하였다. 초당 1만 건의 트랜잭션을 처리한다는 것은 엄청나게 큰 숫자다. 세계적인 결제 기업 VISA는 평균적으로 초당 4,000건의 거래를 처리하고, 피크 때는 24,000건의 거래를 처리한다. 이론적으로 앱토스는 VISA의 결제 처리 속도를 보여줄 수 있는 것이다.

하지만 블록체인의 트랜잭션은 단순 결제에서 멈추지 않는다. 결제 뿐만 아니라 메시지, 사진 전송, 데이터 조회 등 다양한 온라인상의 활동들이 블록체인 트랜잭션을 통해 처리된다면 1만 TPS는 전 세계 고객들의 니즈를 만족시키는 데 있어 말도 안되는 수준으로 부족할 것이다. 그렇기에 각각의 블록체인은 자신만의 방식으로 트랜잭션 처리량을 늘리기 위해 노력하고 있다. 이더리움은 롤업으로, 수이는 DAG 방식으로 자신만의 특색있는 방식을 통해 문제를 해결하려 한다. 그렇다면 앱토스가 내놓는 답은 무엇일까? 앱토스가 제시한 답은 바로 트랜잭션 병렬 처리를 통해 처리량을 높이는 Block-STM이라는 기술이다. 이번 글에서는 이 Block-STM에 대해 다뤄보도록 하자.

1. Block-STM이란?

블록체인의 처리량을 늘리기 위해선 어떻게 해야 할까? 합의 알고리즘을 수정해 보다 빠른 합의에 이르게 하여 처리량을 늘릴 수도 있겠지만, 합의 알고리즘은 그대로 두고 트랜잭션 실행을 보다 빠르게 하여 트랜잭션을 더 많이 처리할 수도 있을 것이다.

(블록체인의 합의, 실행, 저장 중 실행 부분을 개선하고자 하는 Block-STM | 출처 : Protocol Labs Youtube)

앱토스에서 사용하는 AptosBFT에선 리더가 트랜잭션들을 모아 제안(Proposal)을 만들고, 이렇게 만들어진 제안을 다른 밸리데이터들에게 전파한다. 그리고 제안을 전파받은 밸리데이터는 제안을 검증하고 문제가 없다는 것이 판단되면 이 제안에 대한 투표(vote)를 진행하고 결과를 다음 라운드의 리더에게 전송한다. 이 과정에서 밸리데이터들은 제안에 포함된 트랜잭션을 직접 실행하여 제안에 문제가 없는지 파악한다. 만약 이 때 밸리데이터들이 트랜잭션을 한번에 여러 개씩 실행할 수 있게 된다면 어떨까? 밸리데이터는 보다 많은 트랜잭션을 감당할 수 있게 되어 같은 시간에 더 많은 트랜잭션을 처리할 수 있게 될 것이다.

Block-STM은 여러 트랜잭션을 순차적으로 실행하는 기존의 처리 방식과 달리, 트랜잭션을 여러 쓰레드에서 병렬로 처리하여 처리량을 늘린다. 원래 순차적 처리 시에는 1개의 트랜잭션만 처리할 수 있었다면, 3쓰레드에서 병렬로 트랜잭션을 처리하게 되면 같은 시간에 3개의 트랜잭션을 처리할 수 있게 되어 처리량이 늘어난다.

물론 모든 트랜잭션을 병렬로 처리할 수는 없는데, 각각의 트랜잭션이 서로 영향을 미쳐 순차적으로 실행되어야만 하는 트랜잭션들이 있기 때문이다. 기본적으로 A가 B에게 1APT를 보내는 것과 C가 D에게 2APT를 보내는 것은 아무런 연관성이 없기 때문에 동시에 실행해도 문제가 되지 않는다. 하지만 옥션이나 아비트라지 거래와 같은 트랜잭션은 누가 먼저 실행했는가가 중요하고, 많은 사람들이 호출하는 트랜잭션같은 경우도 내부 로직에 따라 충돌하는 경우가 있다. 이러한 충돌 가능성이 있는 트랜잭션은 순차적으로 실행시키면서, 병렬로 처리할 수 있는 트랜잭션은 최대한 병렬로 처리해 처리량을 늘리는 기술이 바로 Block-STM이다.

2. Block-STM 이전의 연구들

비트코인은 갑자기 세상에 등장하지 않았다. 비트코인 이전에도 디지털 화폐에 관한 수많은 시도들이 있었다. 비트코인은 웨이 다이(Wei Dai)의 비머니(B-Money), 닉 재보(Nicholas Szabo)의 비트골드, 할 피니(Hal Finney)의 e머니(e-money) 등의 영향을 받았을 가능성이 크다. Block-STM도 이와 유사하게 다양한 연구들의 영향을 받아 탄생하게 되었기 때문에 아래에서 다룰 기술들은 전혀 가볍게 넘어갈 부분이 아니다. Block-STM 이전에 처리량을 늘리고자 했던 연구들에 대해 살펴보자.

2-1 STM(Software Transactional Memory)

Block-STM이 STM으로 끝나는 것만 봐도 알 수 있듯이, Block-STM의 작동 방식의 가장 기초가 되는 부분은 바로 이 STM이라고 할 수 있다. 1997년 발표된 STM은 특정 작업이 시스템의 메모리에 접근하는 것을 체크하여 작업 간의 충돌을 감지하는 기술이다. 이 과정에서 중요한 용어는 OCC(Optimistic Concurrency Control, 낙관적 동시성 제어)인데, 이 OCC가 결합된 STM은 실행 과정에서 작업의 메모리 접근을 체크하고 실행 이후엔 작업의 유효성 검증(Validation)을 실행하여 이 때 트랜잭션간 충돌이 발생하는 경우 트랜잭션을 중단하고 다시 실행한다. 낙관적이라는 단어를 사용하는 이유는 일단 모든 작업이 유효하다고 낙관적으로 가정하고 실행을 시킨 후, 검증 과정에서 잘못되면 재실행하는 방식 때문이다. 이렇게 처리한 최종 결과는 모든 작업을 순차적으로 실행한 것과 같아야 한다. 이러한 트랜잭션 처리 방식은 Block-STM에서 그대로 활용하고 있다.

2-2 Miner-Replay

Miner-Replay에 Miner가 포함된 이유는 이 연구가 PoW(작업증명, 채굴 방식)가 주류일 때 이에 영감을 받았기 때문이다. Miner-Replay는 채굴자(혹은 리더)가 사전 계산을 통해 종속성을 미리 인지하고 각각의 트랜잭션을 DAG 형태로 밸리데이터들에게 제공하는 방식이다. 이렇게 트랜잭션을 처리하게 되면 대부분의 트랜잭션은 밸리데이터끼리 병렬로, 종속성이 있는 트랜잭션은 한 밸리데이터가 처리한 후 다른 밸리데이터가 처리하는 방식으로 매우 빠르게 트랜잭션을 처리할 수 있다. 또한 여기서 각각의 참여자들이 종속성 그래프를 기록하고 공유하면 일부 참여자는 사전 계산에 필요한 시간을 줄일 수 있다는 장점도 있다.

(Miner-Replay 진행 과정 | 출처 : Axelar Tech Talks)

장점만 있는 것처럼 보이는 Miner-Replay지만, Block-STM이 이 방식을 사용하지 않는 이유가 있다. Miner-Replay는 채굴자가 느린 경우 지연 시간 문제가 발생하고, 채굴자가 비잔틴 공격자인 경우 채굴자가 보내는 종속성 데이터가 맞는지 알 길이 없어 신뢰 문제가 발생할 수 있다. 또한 채굴자는 종속성 데이터를 밸리데이터들에게 전파하기 전에 반드시 이 종속성을 알아내기 위해 사전 실행을 거쳐야 하는데, 여기에서 시간이 많이 소모된다. 트랜잭션을 병렬로 처리하기 위해선 더 나은 접근법이 필요했다.

2-3 BoHM

위에서 살펴본 Miner-Replay와 달리, BoHM을 이용하면 종속성 그래프 없이도 작업을 병렬로 처리할 수 있다. BoHM은 정적 분석이나 사전 실행, 또는 사용자가 제공한 데이터를 통해 쓰기 위치를 미리 예상하여 트랜잭션 실행 전에 트랜잭션들의 실행 순서를 지정해 그 순서대로 트랜잭션이 처리되도록 하는 방식을 말한다. 또한 아래에서 좀 더 자세히 살펴보겠지만, BoHM은 다중 버전 자료구조(Multi-Version Data-Structure)를 이용하여 종속성이 해결될 때에만 트랜잭션을 실행하여 충돌을 피한다.

Block-STM은 BoHM의 방식을 차용했으나 BoHM만을 사용하지는 않는다. BoHM 독자적으로 블록체인에서 사용되기 어려운 가장 큰 이유는 컨트랙트 실행 전에 쓰기 집합(결과값)을 명확히 알고 있어야 한다는 점이다. 많은 사람들이 이용하는 스마트 컨트랙트를 실행할 경우 여러 트랜잭션이 서로 연관되어 있을 가능성이 높은데, 조금이라도 잘못 실행 순서를 예상했다면 이미 예상했던 데이터 위치에 잘못된 결과를 썼기 때문에 문제가 발생한다. 또한 보조 인덱스(Secondary Index)같은 경우는 명확하기 쓰기 집합을 추정하기 어렵기 때문에 BoHM을 독자적으로 블록체인에서 사용하기 더욱 어렵게 만든다.

3. Block-STM의 등장

위에서 살펴본 BoHM과 STM을 기반으로 하여 Block-STM이 등장한다. BoHM과 마찬가지로 Block-STM은 다중 버전 자료구조(Multi-Version Data-Structure)를 사용하며, 정해진 순서에 따라 트랜잭션을 실행한다. 그리고 Block-STM은 여기에 OCC가 결합된 STM을 추가한다. 원래 BoHM에서는 사전 실행 등을 통해 쓰기 위치를 미리 예상하여 트랜잭션을 실행하였지만, Block-STM에서는 낙관적으로 트랜잭션을 실행시킨 후 검증 과정에서 문제가 발생하는 경우 트랜잭션을 중단하고 다시 실행하는 방식을 취한다. 이러한 방식은 사전 실행에 비해 두 가지 장점이 있는데, 하나는 Block-STM은 충돌이 거의 없는 경우엔 대부분의 트랜잭션이 한 번만 실행되어 리소스 소모를 줄일 수 있다는 것, 그리고 두 번째는 충돌이 빈번하게 발생한다고 해도 Block-STM에서 여러 쓰레드가 트랜잭션을 처리하는 과정에서 결과로 나오는 쓰기 집합이 사전 실행을 통해 예상값으로 나온 쓰기 집합보다 더욱 정확하다는 것이다.

OCC와 사전 순서 결정이 합쳐질 때의 주요 문제는 검증 과정이 순서대로 발생해야 한다는 것이다. 특정 트랜잭션의 검증이 실패할 경우 그 이후의 트랜잭션은 이전의 트랜잭션의 검증이 성공적으로 이뤄진 후에만 커밋될 수 있다. Block-STM은 사전 순서보다 낮은 트랜잭션에 대한 실행 및 검증, 우선순위와 관련된 작업을 낙관적으로 보내는 협업 스케줄러(Collaborative Scheduler)를 통해 이 문제를 처리한다. 협업 스케줄러에 관한 내용은 아래에서 다시 다루도록 하겠다.

Block-STM의 입력값은 트랜잭션 블록이다. 여기서 블록이란 블록체인의 블록이 아니라 단순히 트랜잭션이 모여 있는 집합이라고 생각하면 된다. 이 트랜잭션 블록에는 n개의 트랜잭션이 포함되어 있는데, n개의 트랜잭션은 실행 전에 순서가 정해진다(tx1 < tx2 < … < txn). 각각의 트랜잭션은 중단될 수 있기에 여러 번 실행될 수 있으며, 각각의 트랜잭션의 i번째 실행을 ‘트랜잭션의 i번째 생애(incarnation i)’라고 부른다. 그리고 시스템에서 트랜잭션 재실행이 필요하다고 결정하면, 트랜잭션의 실행이 중단(abort)되었다고 말한다. 트랜잭션이 중단된 경우 이 트랜잭션의 i번째 생애는 i+1번째 생애로 증가한 채로 재실행된다.

4. 블록체인의 특성이 Block-STM의 성능에 기여하는 부분

재미있게도 블록체인의 몇몇 특성은 Block-STM의 병렬처리 성능에 기여한다. 블록체인의 어떠한 특성이 Block-STM을 보다 효율적으로 만들까?

4-1 업데이트 단위 = 블록

블록체인에서 데이터의 상태는 블록별로 업데이트된다. 이 특징으로 인해 Block-STM은 트랜잭션을 커밋하는 과정에서 발생하는 동기화와 관련된 복잡성을 피할 수 있다. 블록별로 커밋이 완료되기 때문에 확정된 블록에 담긴 트랜잭션을 다시 검증해야 할지에 대해 고민할 이유가 없다. 또한 블록체인에서는 블록 사이에서 자연스럽게 가비지 컬렉션이 이뤄지기 때문에 가비지 컬렉션과 관련된 메커니즘이 필요하지 않다.

4-2 가상머신(VM)을 통한 안전성 확보

앱토스에서 트랜잭션은 Move라는 안전성에 초점을 맞춘 스마트 컨트랙트 언어로 만들어지며 실행을 [캡슐화](https://www.codestates.com/blog/content/객체-지향-프로그래밍-특징#:~:text=캡슐화란 클래스 안에 서로,모아 관리하는 것입니다.)하고 안전한 동작을 보장하는 VM(가상머신)에서 실행된다.

(VM은 스마트 컨트랙트 버그로부터 블록체인을 보호한다 | 출처 : Axelar Tech Talks)

위와 같은 상황을 예시로 들어보도록 하자. 먼저, x=2가 실행되고, 그 다음 y=2가 실행되고, 마지막으로 z = 1/(x-y)라는 식을 실행시킨다. 그런데, x=2, y=2면 x-y = 0이고, 위 코드는 결국 0으로 나누는 식이 되기 때문에 에러를 발생시킨다. 원래라면 이러한 상황에서는 프로그램에 문제가 발생하고 멈추게 되지만 블록체인에서는 VM에서 0으로 나눴다는 것을 감지하고 에러를 반환한 후 재실행한다. 즉, VM이 스마트 컨트랙트의 행위로부터 블록체인을 보호하고 있는 것이다. 블록체인의 이러한 특성으로 인해 Block-STM은 낙관적으로 실행, 검증과정을 진행할 수 있다. 실행이나 검증 과정에서 에러가 발생하더라도 블록체인에 문제 없이 트랜잭션을 재실행할 수 있다.

4-3 사전 설정 순서

블록체인은 트랜잭션들의 순서가 정해져 있기 때문에 Block-STM을 통한 병렬처리 이후 실제 블록체인 트랜잭션의 결과와 비교를 하기가 용이하다.

(순서가 정해지지 않은 경우 결과가 달라질 가능성이 있다 | 출처 : Axelar Tech Talks)

위의 예시처럼 순서가 정해져 있지 않을 경우, X,Y중 무엇이 먼저 실행되는가에 따라 결과값이 달라질 수 있고, 이 경우 여러 노드들의 동기화에 대한 이슈가 발생할 수 있다. 하지만 블록체인은 순서가 있어 이에 대한 이슈를 고민하지 않아도 된다.

5. Block-STM의 다양한 특징

5-1 다중 버전 자료구조(multi-version data-structure)

Block-STM은 다중 버전 자료구조를 지원한다. 이는 각각의 메모리 공간에 트랜잭션이 쓴 최신 값을 개별적으로 저장하는 구조를 의미한다. 데이터를 효율적으로 읽고 쓰기 위해 다중 버전 자료구조에서는 트랜잭션이 메모리의 특정 위치를 읽을 때, 정해진 순서에서 트랜잭션 앞에 존재하는 트랜잭션들 중 가장 높은 트랜잭션의 값을 읽는다. 예를 들어, 아래 예시에서 tx5는 tx3의 값인 val3을 읽는다.(Tx4가 없기 때문에 앞에 존재하는 트랜잭션 중 가장 높은 트랜잭션은 tx3이다) 만약 더 낮은 순서의 트랜잭션이 없다면 블록 실행 전 상태를 기반으로 스토리지에서 값을 가져온다.

(다중 버전 자료구조 읽기/쓰기 예시 | 출처 : Axelar Tech Talks)

5-2 종속성 추정

Block-STM은 BoHM과 달리 종속성을 미리 계산하지 않는다. 대신 Block-STM은 추정 마커(ESTIMATE Marker)를 사용한다. 검증이 실패하여 트랜잭션 생애가 중단되면 실행 과정에서 다중 버전 자료구조에 작성했던 쓰기값이 추정 마커로 대체된다. 아래 예시와 같이, txn 3의 검증이 실패할 경우 다중 버전 자료구조의 txn 3 위치의 값이 val3에서 ESTIMATE로 변경된다.

(검증 실패 후 값이 추정 마커로 대체되는 과정 | 출처 : Axelar Tech Talks)

이 추정 마커는 txn 3이 재실행되는 다음 생애에서 같은 메모리 장소에 값을 쓸 것이라는 의미를 나타낸다. 이렇게 추정 마커가 붙은 상태에서 다른 트랜잭션이 이 추정 마커를 읽게 되면, 그 트랜잭션은 중단된다. 중단되는 이유는 이 트랜잭션이 추정 마커가 있는 위치에 데이터를 쓸 가능성이 있는데, 그렇게 된다면 트랜잭션의 결과값이 달라질 수 있기 때문이다. 즉, Block-STM은 추정 마커를 통해 혹시나 있을지 모를 종속성에 따른 검증 실패를 사전 차단하는 방식으로 병렬처리를 최적화한다. 이 추정 마커는 트랜잭션이 재실행되면 사라지게 된다.

5-3 협업 스케줄러(Collaborative Scheduler)

Block-STM은 실행과 검증 작업을 관리하는 협업 스케줄러를 도입하였다. 트랜잭션을 순서대로 커밋시키기 위해, 협업 스케줄러는 인덱스가 낮은 트랜잭션부터 순서대로 실행과 검증을 지시한다. 협업 스케줄러는 실행 작업 집합과 검증 작업 집합을 체크하고, 작업의 우선순위를 지정한다. 트랜잭션의 중단과 재실행 또한 협업 스케줄러에서 관리한다. 위에서 설명한 추정 마커를 읽은 트랜잭션에 대한 중단 과정 또한 협업 스케줄러가 관할한다.

이 과정에서 협업 스케줄러는 실행과 검증 과정을 낙관적으로 스케줄링한다. 낙관적으로 스케줄링한다는 것은 모든 트랜잭션이 문제없다는 것을 가정하고 모든 쓰레드에서 최대한 작업을 진행한다는 것이다. 예를 들어, 트랜잭션 1,2,3,4를 검증해야 한다고 할 때 모든 트랜잭션이 문제가 없다고 가정하고 트랜잭션 1,2,3,4를 병렬처리한다고 하자. 여기서 트랜잭션 3이 검증에 실패했다고 하더라도 그만큼 실패를 빠르게 확인할 수 있기 때문에 더욱 많은 처리가 가능하다(트랜잭션 4를 다시 검증해야 하는 것을 감안하더라도 빠르다).

6. Block-STM의 트랜잭션 실행, 검증, 중단

즉, Block-STM은 BoHM에서 차용한 실행 과정에 STM에서 차용한 검증 과정을 더하고, 여기에 Block-STM이 추가한 개념인 협업 스케줄러가 작업을 관리하는 형태이다. 이번에는 실행 과정과 검증 과정이 어떻게 진행되는지에 대해 보다 자세하게 알아보도록 하자.

6-1 실행 작업(Execution Task)

(트랜잭션 실행 과정 | 출처 : Axelar Tech Talks)

Block-STM의 실행 과정은 협업 스케줄러(Collaborative Scheduler), 실행자(Executor), 가상머신(VM), 다중 버전 자료구조(Multi-version data-structure)를 통해 진행된다.

실행자가 협업 스케줄러에게 작업을 달라고 요청하고, 문제가 없을 경우 협업 스케줄러는 작업(트랜잭션)을 실행자에게 할당한다.
그 후 실행자는 가상머신을 통해 협업 스케줄러로부터 할당된 트랜잭션을 실행하는 것을 요청한다.
가상머신은 다중 버전 자료구조로부터 초깃값을 읽는다.
가상머신은 읽은 초깃값을 바탕으로 트랜잭션을 실행하여 이에 대한 결과(쓰기)와 초깃값(읽기)를 묶어 실행자에게 반환한다.
실행자는 이렇게 받은 세트 중 쓰기 부분을 다중 버전 자료구조에 작성한다.

6-2 검증 작업(Validation Task)

(트랜잭션 검증 과정 | 출처 : Axelar Tech Talks)

검증 과정은 실행자가 다중 버전 자료구조에 작성된 값을 검증하며 시작된다. 실행자는 가상머신을 통해 결과인 쓰기값 외에도 기존에 변하기 전의 값이었던 읽기값도 함께 받았다. 실제로 결과에 반영되는 것은 쓰기값밖에 없지만 읽기값을 가져오는 이유는 실행 과정에서 발생한 읽기가 변하지 않았는지 재차 읽고 받은 읽기값과 비교하기 위해서이다. 이렇게 값을 비교했을 때 문제가 없을 경우 다중 버전 자료구조에 저장된 값은 스토리지로 보내지고 실행자는 협업 스케줄러에게 할당된 작업이 완료되었다는 것을 알리면서 검증 작업이 종료된다.

6-3 작업 중단(Abort)

트랜잭션이 중단되는 케이스는 크게 두 가지로 나뉘는데, 하나는 실행 과정에서 종속성을 만나게 되는 것이고, 하나는 검증 과정에서 검증이 실패할 경우다. 이렇게 트랜잭션이 중단되면 트랜잭션 생애 i가 i+1로 증가하고 다시 실행 준비 과정으로 돌아가게 된다.

(트랜잭션의 중단 과정 | 출처 : Block-STM 백서)

7. Block-STM을 이용한 트랜잭션 처리 과정 예시

위에서 살펴본 Block-STM에 관련된 내용들을 종합하여, 이제 실제로 Block-STM을 이용해 트랜잭션이 병렬처리되는 과정을 예시를 통해 알아보도록 하자.

(Block-STM을 이용한 트랜잭션 병렬처리과정 예시 | 출처 : Block-STM 백서)

이번 예시에서는 트랜잭션 1~9번까지 총 9개의 트랜잭션이 실행되고, 3개의 쓰레드가 작업을 진행한다. 이 예시에서는 4번 트랜잭션이 2번 트랜잭션에 종속성이 있다. 위의 E는 실행 과정을 진행해야 하는 트랜잭션들이 모여 있는 집합이고, V는 검증 과정을 진행해야 하는 트랜잭션들이 모여 있는 집합이다. 만약 V와 E가 모두 비었고, 작업 중인 쓰레드도 없을 경우 모든 작업이 완료되어 트랜잭션 처리 과정이 종료된다. 그리고 V와 E 안에 있는 가장 작은 트랜잭션 번호부터 작업이 진행된다. 초기에 모든 트랜잭션은 순서가 정해진 상태로 E안에 있다. 이제 각각의 단계에서 어떠한 과정이 진행되는지 살펴보도록 하자.

1단계 : V에 속한 트랜잭션이 없기 때문에 검증 작업이 없다. 따라서 쓰레드는 E에 속한 트랜잭션 중 빠른 순서 순으로 tx1, tx2, tx3을 병렬로 실행한다.
2단계 : tx1, tx2, tx3은 실행이 완료되어 V에 들어가 있다. V에 속한 트랜잭션이 tx1, tx2, tx3 3개가 있기 때문에 쓰레드는 tx1, tx2, tx3을 병렬로 검증한다. 이 때 tx1과 tx3의 검증은 성공했지만 tx2가 tx1에 종속성이 있어 검증이 실패하였다. 이 경우 tx2는 중단되고 tx2의 다중 버전 자료구조 위치에는 추정 마커(ESTIMATE Marker)가 붙는다. 그리고 tx2는 다시 E로 돌아가고 tx3은 V로 돌아간다.
3단계 : 3개의 쓰레드 중 하나의 쓰레드에서 tx3이 검증되고, 남은 두 개의 쓰레드에선 트랜잭션 tx2와 tx4의 생애가 시작된다. 하지만 여기서 tx2에 종속성이 있는 tx4는 tx2의 추정 마커를 읽고 실행이 중단된다. 따라서 이 쓰레드는 E안에 있는 다음 트랜잭션인 tx5를 실행시킨다. tx2와 tx5의 실행이 끝난 후 두 트랜잭션이 V에 추가된다. 이 예시에서 tx2의 새로운 생애는 이전 생애에서 사용했던 위치에 쓰기를 시도하기 때문에 tx3이 쓴 메모리 위치에 tx2가 먼저 와서 tx3의 결과값이 변할 가능성이 없어 tx3은 다른 검증 없이 커밋될 수 있다.
4단계 : tx2와 tx5는 검증되고 남은 쓰레드 1자리에서 tx4가 실행된다. tx4는 새로운 메모리 위치에 쓰기를 시도하였고, 이 새로운 메모리 위치가 tx5의 메모리 위치라면 tx5의 결과값이 변할 수 있기 때문에 tx5는 재검증을 위해 다시 V에 추가된다.
5단계 : tx4와 tx5는 검증되고 tx6이 실행된다.

예시를 보면 알 수 있듯이 Block-STM은 실행 과정에서 여러 개의 쓰레드를 사용하면서, 그리고 그 과정에서 종속성이 있는 트랜잭션들은 순차적 처리를 하면서 처리 속도를 높인다.

8. Block-STM의 압도적인 성능

8-1 기존의 병렬처리 기술들과의 비교

그렇다면 Block-STM의 성능은 얼마나 뛰어날까? 순차적 처리 방식과 기존에 존재했던 병렬처리 기술(BoHM, LiTM)과 비교해보자. 비교에 앞서 LiTM(Lightweight Deterministic Software Transactional Memory Ststem)은 여기서 다루지 않은 다른 종류의 STM 시스템을 말하고, acc는 트랜잭션을 보내는 어카운트의 수를 의미한다.

(쓰레드 개수당 처리량 비교 | 출처 : Axelar Tech Talks)

Block-STM은 32쓰레드일 때 블록 사이즈가 1k인 경우 순차적 처리의 약 7배, 블록 사이즈가 10k인 경우 순차적 처리의 약 17배의 처리량을 보였다. 흥미로운 사실은 Block-STM이 BoHM과 유사한 처리량을 보인다는 것이다. BoHM는 제대로 된 쓰기 집합을 예상하지 못할 경우 실행이 불가능하다. 이 때문에 BoHM은 항상 정확하게 쓰기 집합을 예상하는 것으로 가정하고 테스트를 진행하였다. 이러한 상황에서도 Block-STM은 BoHM과 유사한 처리량을 보이는 것이다.

8-2 계정 수에 따른 TPS 비교

Block-STM의 경우 트랜잭션이 종속성을 많이 가지고 있으면 있을수록 그만큼 트랜잭션이 느리게 실행된다는 단점이 있다. 때문에 이 특성을 보다 명확히 수치로 측정하기 위해 트랜잭션을 일으키는 계정 수를 다양하게 하여(2, 100, 10000) 트랜잭션을 실행시킨 후 값을 확인해보자.

계정 수가 100개가 넘어가게 되면 순차적 처리와 비교해 훨씬 높은 TPS를 보인다는 것을 확인할 수 있다. 그리고 계정 수가 2개일 경우, 대부분의 트랜잭션이 종속성을 가지고 있을 것이지만 의외로 순차적 실행과 비교해 TPS가 그렇게 낮게 떨어지지 않았다.(둘 다 1만 TPS 수준 기록)

32쓰레드일 때 100개의 계정이 트랜잭션을 일으킬 경우 8만 TPS가, 1만 개의 계정이 트랜잭션을 보낼 경우 무려 16만 TPS가 나오는 것을 확인할 수 있다. 앱토스에서 주장하는 16만 TPS가 여기에서 등장한다. 최대 16배 수준의 성능 향상을 이끌어낼 수 있는 것이다.

물론 실제로는 모든 계정들이 완벽하게 랜덤하게 다른 계정으로 트랜잭션을 일으키지도 않을 것이고, 특정 어플리케이션에 트랜잭션이 몰려 종속성이 높아질 수 있다. 이 경우 위 실험과 같은 수의 계정과 쓰레드더라도 TPS는 더 낮아질 수 있다. 그럼에도 모든 사람들이 앱토스 위에서 하나의 어플리케이션만 사용하지는 않을 것이고, 어플리케이션 위에 하나의 컨트랙트만 있는 것이 아니라 여러 컨트랙트가 존재하여 종속성이 분산될 것이기 때문에 Block-STM은 상당히 유의미한 기술이 될 것으로 전망한다.

9. 마치며 - 16만 TPS를 위한 여정

수이는 Narwhal&Bullshark로, 이더리움은 롤업으로 각자의 방식대로 TPS를 증가시키기 위한 시도를 하고 있다. 하지만 수이의 DAG 방식은 기술적인 의문이 아직 해결되지 못한 상태이고, 이더리움의 롤업 또한 엄청난 TPS를 기록하기에는 무리가 있다. 물론 Block-STM도 다양한 트랜잭션들이 서로 의존성이 있는 경우 원래 속도와 비슷하거나 더 느릴 수도 있다. 하지만 모든 거래가 서로 의존적이지 않을 가능성이 높고 합의 알고리즘 단에서 트랜잭션 처리량을 늘리는 것이 아니라 실행 단계에서 처리량을 늘리는 것이 아니기 때문에 합의 알고리즘이 잘못되어 발생하는 신뢰 문제를 일으키지 않는다. 그래서 앱토스의 TPS를 늘리기 위한 시도는 충분히 가치가 있다.

앱토스가 최고 16만 TPS를 달성할 수 있다면 현재 블록체인 위에서 구동하기 어려운 서비스들이 블록체인 위에 올라올 수 있을 것이다. 대작 게임의 모든 아이템과 데이터를 블록체인 위에 올리거나 SNS 데이터 또한 블록체인 위에 자세히 올릴 수 있을 것이다. 블록체인 위에 게임 아이템과 데이터가 올라가게 되면 투명하게 게임과 관련된 정보를 알 수 있게 되고, 블록체인을 통해 아이템 거래가 되어 수많은 서드파티 게임 서비스들이 생기고 데이터 분석 서비스들또한 생겨 게임의 질과 재미를 높여줄 수 있을 것이다. 블록체인 위에 올라갈 수 있는 서비스가 다양해질수록, 블록체인의 장점을 살릴 수 있는 가능성 또한 높아진다. 앱토스가 실제로 16만 TPS를 달성할 수 있을지, 그리고 블록체인의 대중화를 이끌어낼 수 있을지 기대해보도록 하자.

All for Scalability

[앱토스 시리즈] #5: Block STM - 어떻게 앱토스는 트랜잭션을 병렬처리 하는가