Forerunner: 이더리움 트랜잭션 수행 속도 8배 향상시키기
Chen, Yang, et al. “Forerunner: Constraint-based Speculative Transaction Execution for Ethereum.” Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles CD-ROM. 2021.
오늘은 Forerunner라는 최신 연구를 소개하려 한다. 본 연구는 컴퓨터분야 최상위 학회인 SOSP에 등재되고 마이크로소프트에서 연구한 내용이라는 점에서 본인의 이목을 끌었는데, 그 타이틀에 걸맞게 흥미로운 내용을 담고 있었다.
한마디로 Forerunner는 이더리움의 트랜잭션 수행 속도를 크게 향상시킨 연구이다. 저자들이 실제 이더리움 네트워크에 연결하여 1300만 개의 트랜잭션에 대해 평가한 결과 Forerunner는 전체 트랜잭션의 95.71%에 대해 8.39배의 속도 향상을 이룩했고, 나머지 트랜잭션들의 수행까지 포함하면 최종적으로 6.06배의 속도 향상을 달성할 수 있었다.
이더리움 트랜잭션의 수행 속도를 향상시키면 좋은 점이 무엇인가? 직관적으로 생각해보면, 채굴자의 입장에서 트랜잭션 수행 실행을 줄여 채굴(PoW 퍼즐 풀기)에 더 많은 자원을 할애할 수 있다는 강점이 있다. 그러나 원래부터 트랜잭션 수행 시간은 전체 블록 생성 프로세스 중 작은 부분만을 차지하기 때문에 그다지 큰 이득은 아니다.
그보다도 이번 라운드에서 블록을 생성하는 채굴자와 나머지 검증자들 모두에게, 즉 이더리움 네트워크의 모든 참여자를 대상으로 트랜잭션 수행에 할애되는 총 시간을 줄였다는 점에서 큰 이득이 있다. 이를 통해 큰 폭의 TPS 향상을 기대할 수 있는 것이다. 쉽게 말하자면:
- Forerunner의 방법을 적용하면 모든 참여 노드의 전반적인 성능 향상이 있으므로,
- 이더리움의 한 블록이 감당할 수 있는 연산량 한도를 높일 수 있고,
- 그래서 한 블록에 담기는 트랜잭션 수가 크게 증가하면,
- 초당 트랜잭션 처리량(TPS)이 크게 높아진다. 블록 생성 간극 등 이더리움 프로토콜의 핵심 수치의 수정 없이도!
이는 채굴자의 트랜잭션 수행 성능 향상만을 꾀했던 기존 연구들과는 차별화되는 점으로, Forerunner를 더 의미있게 만들어주는 요소라 할 수 있겠다.
Forerunner는 어떻게 8배 이상의 트랜잭션 수행 속도를 확보할 수 있었는가? 간단히 말하자면 트랜잭션을 투기적으로 실행하기 때문이다.
컴퓨터공학을 공부한 독자라면 ‘투기적 실행’이라는 키워드가 익숙할텐데, 실제로 이는 여러 곳에서 성능 향상을 위해 두루 사용되는 기법이다. 가령 CPU에서 추후에 실행될 명령어를 미리 실행하고 그 값이 맞는 경우 그대로 적용하지만, 틀릴 경우 결과를 파기하고 재실행하는 ‘투기적 실행’ 등이 있다.
병렬 실행 및 유휴 자원을 이용해 미래의 작업을 미리 수행하고 그 결과를 이용한다는 점은 분명 매력적이지만, 만일 예측이 틀릴 경우 결과를 파기하고 재계산하는 비용이 크게 요구된다는 문제가 있다. 오히려 직렬적으로 수행하는 것 보다 느려질 수도 있다. 따라서 투기적 실행에서는 어떻게 정확도를 높일 수 있을까에 대한 고민을 많이 한다. 그래야 예측에 실패하는 폴백(fallback) 상황을 최대한 줄여 효율을 이끌어 낼 수 있는 것이다.
다시 블록체인으로 돌아오자. 이더리움에서는 트랜잭션이 직렬적으로, 즉 한번에 하나씩 수행되므로 투기적 실행의 수혜를 받을 수 있다. 첫 번째 트랜잭션을 수행하면서 동시에 두 번째, 세 번째 트랜잭션도 같이 수행해버리는 것이다. 첫 번째 트랜잭션이 이더리움의 상태(state)를 어떻게 변경시킬지 모르는 상태에서 뒤이은 트랜잭션들을 미리 실행해두는 것이므로 이는 투기적 실행에 해당한다.
그럼 이더리움에서 투기 실행을 위한 예측의 정확도를 어떻게 높일 것인지에 대해 생각하면 될 것 같은데, 이게 그렇게 쉬운 일이 아니다. 이더리움에서 예측해야 할 미래의 가능성이 너무나도 많기 때문이다.
DiCE 패러다임과 ‘수 많은 미래’의 저주
잘 알다시피 이더리움은 신뢰할 수 있는 월드(world) 컴퓨터를 표명하며 등장해, 분산 컴퓨팅의 새로운 패러다임을 불러일으켰다. 저자들은 이를 DiCE 패러다임이라 칭하고 있다.
DiCE 패러다임
DiCE는 Dissemination-Consensus-Execution의 약자로, 말 그대로 배포-합의-실행의 절차를 따라 트랜잭션이 처리된다는 의미이다.
- 배포(Dissemination) 단계에서는 임의의 이더리움 참여자가 트랜잭션을 제시하고, 이를 다른 모든 참여자들에게 전파(broadcast)한다. 각 노드들은 전파받은 트랜잭션을 저마다의(local) 트랜잭션 풀(pool)에 보관한다.
- 합의(Consensus) 단계에서는 누구나 채굴자처럼 행동할 수 있고, 저마다의 트랜잭션 풀을 통해 트랜잭션을 검증하고 순서를 결정한다. 이를 블록에 담은 후, PoW의 수행까지 마쳐 최종적으로 새 블록을 형성한다.
- 이렇게 만들어진 새 블록은 네트워크에 전파되고, 다른 모든 노드들은 이를 검증해 실행하게 된다. 이를 실행(Execution) 단계라 한다. 이러한 배포-합의-실행의 절차를 거쳐 일련의 트랜잭션이 수행되면 비로소 다음 블록을 생성할 준비가 된 것이다. 다시 배포 단계로 돌아가서 단계를 반복한다.
이렇듯 트랜잭션을 수행하기까지 배포와 합의의 단계를 거쳐야만 하기에, 실제로 트랜잭션을 ‘수행’하는 것에는 제한된 시간만이 허락된다. 이 한정된 시간 안에 수행되는 트랜잭션의 수가 바로 전체 시스템의 처리량이 된다. 따라서 트랜잭션 수행 시간을 가속화하면 이더리움 시스템의 성능이 향상되는 것이다.
투기적 실행의 기회
배포 단계를 좀 더 살펴보자. 이더리움에서 트랜잭션들은 비동기적이고 연속적으로 노드들에게 전파된다. 노드들은 각 트랜잭션을 배포 단계에서 이미 인지하고 저장하고 있지만, 실제 수행은 합의를 지나 실행 단계에까지 도달해야지만 진행되게 된다.
오늘날 이더리움에서 트랜잭션의 인지와 수행 사이의 시간 간극은 수 초에서 수 분까지 달한다. 이더리움에서 발행되는 트랜잭션 수가 원체 많기 때문에 트랜잭션 풀에 담긴다고 해서 바로바로 블록에 포함되는 것이 아니고, 여러 합의-수행 단계를 거치고 나서야 비로소 포함되는 경향이 있기 때문이다.
이러한 시간 간극이 바로 투기적 실행의 기회를 만들어낸다. 실행 단계에 도달하기 전에 미리 트랜잭션을 수행해 둔 다음, 그 결과만을 불러와 적용할 수 있다면? 제한된 수행 단계 안에서 많은 수의 트랜잭션을 처리할 수 있을 것이며, 위에서 언급했다시피, 결국 이더리움 시스템의 성능이 향상되는 것이다.
수 많은 미래의 저주
그러나 DiCE 모델의 탈중앙적이고 비결정론적인 속성 때문에, 각 트랜잭션은 수 많은 ‘가능한 미래’를 내포하고 있다. 일단 이번 블록 라운드에서 누가 채굴자가 될 지 아무도 모르며, 해당 채굴자가 생성한 블록에 어느 트랜잭션들이 담기고 심지어 그 트랜잭션들간의 순서도 어찌될지 아무도 모르기 때문이다. 이 뿐만이 아니다. 타임스탬프 등 각 노드의 로컬 상태까지도 영향을 끼친다.
이 모든 것들은 각 트랜잭션이 수 많은 미래를 형성하게 만든다. 이 중에 맞는 미래가 무엇일지 알 방법이 없다. 일반적인 방법으로는 예측의 정확도를 높이기가 애초에 불가능하다. 각 노드들은 합의 단계가 끝나 실제 블록을 전파받아서야 문맥(context)을 알 수 있다. 이는 바로 위에서 살펴본 투기적 실행의 기회와 상충된다.
제약 기반 투기적 실행
DiCE 모델에서 완벽한 예측을 통한 트랜잭션 가속이 불가능하다면, 다른 방법을 찾아야 한다. 저자들은 투기적 실행을 위한 제약 기반 방법이라는 새로운 방법을 제안한다.
제약 기반 방법은 두 단계로 구성된다.
- 투기 단계에서 트랜잭션은 하나 혹은 많은 미래의 문맥을 실행하고, 제약과 fast-path 프로그램을 형성한다.
- 실제 실행 단계에서 문맥이 결정되면, 즉 블록이 생성되어 전파되었으면, 어떠한 제약이 충족되었는지를 살펴본 다음 fast-path 프로그램을 수행한다. 만일 해당사항이 없으면 원래의 트랜잭션을 수행한다.
Fast-path 프로그램은 원래 트랜잭션 수행보다 훨씬 빠른 속도로 수행되는 최적화된 작업이며, 제약은 어느 fast-path 프로그램이 수행될지를 결정짓는 조건에 해당한다. 쉽게 말하자면 각 트랜잭션이 만들어낼 수 있는 가능한 미래들에 대해 최대한 많은 최적화를 해두고, 실제 문맥이 결정되면 그 중 하나를 통해 트랜잭션을 빠르게 수행해버리는 것이다.
이제 문제는 다음의 항목들로 대치된다.
- 어떻게 제약과 fast-path들을 빠르게 형성할 것인지
- 어떻게 실제 문맥에 대응될만한 제약을 형성할 것인지
- 어떻게 fast-path 프로그램의 효율성을 높일지
사실 이러한 제약 기반 투기적 실행은 전통적인 투기적 실행을 일반화한 것으로 간주할 수 있다. 후자는 하나의 제약이 항상 만족될 것으로 기대하고, fast-path 프로그램을 대신해 미리 계산된 결과를 저장한다.
Forerunner
Forerunner는 실제 이더리움에 적용 가능한 수준의 효율성을 갖춘 제약 기반 투기적 실행을 제공한다. 이를 위해 CD-Equiv 제약과 fast-path라는 개념을 도입하고, 최적화된 효율을 위해 변경된 이더리움 가상 머신, 메모이제이션, 그리고 새로운 자료 구조를 사용한다.
CD-Equiv 제약과 fast-path
Forerunner에서는 제약이 실제 문맥에 잘 대응되도록 하기 위해 Forerunner에서는 트랜잭션 수행에서의 제어 흐름(control flow)와 데이터 의존성(data dependencies)을 이용한다. 자명하게도 같은 제어 흐름과 데이터 의존성을 가진 상황이라면 트랜잭션은 동일한 일렬의 명령어들을 수행한다. 저자들은 이를 CD-Equiv 제약 상황이라 칭한다. 그리고 그 일렬의 명령어들을 최적화 한 것이 fast-path 프로그램이다.
이러한 구조가 제공하는 강점들은 다음과 같다.
- 여러 CD-Equiv를 고려하는 덕분에 Forerunner는 투기의 많은 가능성들을 다룰 수 있고, 완벽히 문맥을 예측해야하는 전통적 투기 실행의 제약으로부터 자유로워진다.
- 투기적 실행에서 접근하는 (데이터베이스에서의) 데이터 위치는 실제 문맥에서의 데이터 위치와 동일하다. 투기적 실행을 통해 데이터를 미리 캐시에 담아두게 되고, 실제 실행에서는 이를 참조하기 때문에 I/O 시간이 감소한다.
S-EVM
명령어들을 쉽게 분석하고 최적화하고, (아래에서 설명할 메모이제이션을 위해) 변경하고, 그리고 가속화된 프로그램을 수행하기 위해 Forerunner에서는 S-EVM으로 명명한 새로운 이더리움 가상 머신 구조를 사용한다.
본래의 EVM은 스택(stack) 기반 머신이지만, S-EVM은 레지스터 기반의 EVM이다. S-EVM은 가속화된 프로그램 수행을 위해 EVM 명령어의 일부를 지원한다. 대수연산, 비교, 비트와이즈(bitwise) 연산, SHA3, 블록 정보, 스토리지, 로깅(logging) 등이 이에 해당한다.
S-EVM은 레지스터 기반의 가상 머신이기 때문에 EVM 명령들은 레지스터에 해당하는 글로벌 배열만을 읽고 쓸 수 있으면 된다. 스택을 읽거나 힙(heap) 메모리에 접근하는 등 스택 기반 EVM의 복잡한 구조가 필요하지 않다. 덕분에 명령어의 분석과 최적화가 쉬워진다. 가령 정해진 결과를 내놓는 명령어를 재귀적으로 제거하는 constant folding, 반복된 연산에 해당하는 명령어를 제거하는 common subexpression elimination 등의 최적화가 가능하다. 또한 fast-path에서 접근하지 않는 명령어들을 제거하는 dead code elimination도 진행한다.
메모이제이션
메모이제이션(Memoization)은 동일한 계산을 반복할 때, 이전에 계산한 값을 메모리에 저장해 두었다가 이용함으로써 중복 수행을 피해 프로그램 실행 속도를 빠르게 하는 기술이다.
Forerunner는 제약 검사 로직과 fast-path 프로그램을 형성하는 것에 메모이제이션을 이용해 효율성을 높였다. 연산의 특정 부분에서 그 결과가 결정론적으로 계산된다면, 여러 가능한 문맥들의 투기 각자에 걸쳐 이미 연산된 결과를 이용하는 것이다. 만일 전체 문맥이 예측 가능하다면 제약 조건에서부터 수행 결과까지의 예측이 통째로 가능하고, 이는 전통적 투기 예측의 효율성과 거의 동등한 효과를 보인다. (약간의 추가적 오버헤드가 있기 때문에 ‘거의’ 동등하다고 표현)
효율적 자료 구조
또한 Forerunner는 여러 제약 검사 로직을 통합하는 자료 구조를 개발해 이용했다. 제약 기반 투기적 실행에서는 여러 제약 조건들이 각자의 fast-path를 가지고 저마다 다른 문맥에서부터 등장한다. 잘 생각해보면 어느 제약이 만족되어 해당하는 fast-path를 실행했을 때, 다른 문맥에 있는 제약은 검사할 필요가 없다. 이를 효과적으로 걸러내어 오버헤드(overhead)를 피할 수 있도록 하는 자료 구조를 설계해 이용했다.
구현 및 평가
저자들은 Go-Ethereum v1.9.9를 수정해 Forerunner를 구현했다. 해당 구현체는 오픈소스로 공개되어 있다: https://github.com/microsoft/Forerunner
흥미롭게도 저자들은 2021년 3월 12일부터 22일까지의 라이브(live) 이더리움 네트워크를 그대로 Forerunner의 실험 환경으로 삼았다. Forerunner가 이더리움 워크로드에 대해 제대로 동작하는가를 볼 수 있을 뿐만 아니라, 실제 트랜잭션의 발생 및 도달 타이밍을 그대로 이용했다는 점에서 고무적이다. 이외에도 2020년 1월 1일부터 2021년 3월 22일까지의 상황을 리플레이(replay)하여 더 많은 데이터에 대한 실험을 진행했다.
라이브 데이터에 대한 실험 결과, 트랜잭션들의 속도 향상은 위 그래프의 분포를 보였다. 평균 8.39배의 속도 향상을 기록했으며 경우에 따라 50배 이상 수행 속도가 빨라지기도 했다. 물론 1배 이하의, 즉 일반적인 이더리움보다 느린 속도를 보인 경우도 존재했는데, 이는 투기적 실행에 실패한 경우 처음부터 다시 트랜잭션을 수행하는 오버헤드가 존재하기 때문이다. 그러나 그 개수가 그다지 많지 않음 역시 알 수 있다.
이 때의 투기 실행의 정확도는 95.71%로, 다시 말해 전체 트랜잭션 중 95.71% 만큼의 트랜잭션들이 채굴되어 블록에 담기기 전에 이미 가공되었음을(fast-path를 형성했음을) 의미한다. 결국 수행 단계에서 상당수의 트랜잭션들은 빠른 수행이 가능해진다.
이외에도 저자들은 정확도 검증, 제약 만족률, 전체 향상된 결과에서 Forerunner의 각 항목이 기여한 정도, 그리고 결과의 안정성 등을 실험하여 평가하였는데, 상세한 내용은 원 논문을 참고하길 바란다.
결론
Forerunner는 제약 기반의 접근 방법으로 투기적 실행을 DiCE 패러다임을 적용한 시스템에서도 가능하게 만들었다. 각 제약들은 제어 흐름과 데이터 의존성에 따른 미리 실행된/최적화된 트랜잭션 수행을 이용할 수 있게 한다. 이는 극단적으로 높은 수준의 트랜잭션 수행 속도 향상을 가능케 했다. 또한, 메모이제이션 등의 기법으로부터 투기적 실행의 효율성을 높였다.
이더리움 실제 데이터에 기반한 실험에서, 결과적으로 투기적 실행에 성공한 트랜잭션들은 8.39배 이상의 성능 향상을 달성했다. 해당하지 못한 트랜잭션들까지 포함하면 최종적으로 6.06배 성능이 향상되었다. 이는 블록 가스 한도를 높이는 등의 프로토콜 최적화를 가능하게 하며, 이더리움의 근본적인 처리량 향상을 가능하게 한다.
- CURG(Crypto United Research Group)는 2018년 5월 대학(원), 기업, 스타트업 등 다양한 분야의 열정적인 블록체인-er들이 모인 연합 연구 그룹입니다. CURG는 2018년 5월 출범된 이후, ‘Trendy, Thoughtful, and Transdisciplinary’ 한 자세로 한 주도 빠짐없이 블록체인 연구를 지속해오고 있습니다.
- 디사이퍼(DECIPHER)는 “건강한 블록체인 생태계 조성에 기여한다” 라는 미션 아래 블록체인에 대해 연구하고 이를 실용적으로 응용하는 서울대 블록체인 연구 학회입니다. 2018년 3월에 처음 조직 되어 현재까지 블록체인 기술을 다방면에서 연구하고 산업계에 응용하고 있는 100명 이상의 회원들을 배출해왔습니다. 다양한 팀별 연구활동과 프로젝트, 컨퍼런스 개최, 서울대학교 블록체인 강의 개설, 유수 기업들과의 산학협력과 파트너십 체결을 해오며 국내 최고의 블록체인 학회로 자리 잡았습니다.
커그와 디사이퍼는 향후 적극적인 협력을 통해 블록체인 필드에서의 강력한 시너지를 구축하고자 합니다.
