scalalang2

Merklized LSM — 이더리움 스토리지 성능 최적화 이야기

개인적으로 이더리움을 표현할 때 블록체인 대신 새로운 용어를 만들어서 불러야 한다고 생각한다. 블록체인이라는 용어는 지나치게 데이터베이스의 성격을 강조하는 용어이기 때문에 많은 연구자들과 사용자들이 블록체인을 데이터 저장소 용도로만 생각하는 경우가 많다. 그래서 분산 컴퓨팅과 분산 데이터베이스 그 중간 어디를 표현할 수 있는 새로운 용어가 필요하다.

이더리움은 분산 데이터베이스와 분산 컴퓨팅 그 중간 어딘가에 위치하는 복잡한 시스템이다. 이런 이유로 분산 데이터베이스의 성격이 강한 비트코인에서는 적용할 수 있는 성능 해결방법들이 이더리움에는 적용하기 힘든 경우가 많다. 또한, 이더리움이 가지는 성능 문제 또한 비트코인이 겪는 성능 문제와는 성격이 많이 다르다. 이번 포스팅 에서는 이더리움의 성능 문제 중 스토리지와 가상머신에 대한 이야기를 다루어보려고 한다. 그리고 문제의 원인을 진단하고 어떻게 해결할 수 있는지 아이디어를 제시한 논문*을 소개하고자 한다.

구성

이더리움의 성능 문제, 그 고통의 역사

이더리움은 예로부터 스토리지 성능 문제로 인해 고통받아 왔다. 2016년 9월 22일, 이더리움은 서비스 거부 공격(DoS)에 노출되어 네트워크가 급격히 느려지는 일이 발생했다. 이더리움 공식 블로그를 통해 네트워크가 공격당하고 있으니 노드의 수수료 정책을 업데이트 할 것을 긴급히 알리는 글이 올라왔다[1]. 무엇이 문제였을까?

이더리움의 스마트 컨트랙트는 보통 Solidity언어로 작성한다. Solidity언어를 컴파일하면 OPCODE의 집합으로 컴파일된다. 자바 언어를 컴파일 하면 기계어로 번역되지 않고 바이트 코드 집합으로 컴파일 되는 원리와 비슷한다. 이렇게 컴파일된 OPCODE는 스택-기반 가상머신인 EVM에서 처리한다.

그런데 이 가상머신이 처리하는 OPCODE중 EXTCODESIZE의 수수료가 연산시간에 비해 지나치게 저렴하게 가격이 매겨져 있던 것이다. 결국 공격자는 의도적으로 해당 코드가 많이 포함되는 스마트 컨트랙트를 전파해서 저비용으로 네트워크를 마비시킬 수 있었다.

결국, 이 사건으로 인해 이더리움은 EIP-150 하드포크를 단행해서 트랜잭션 수수료를 대대적으로 인상하는 작업을 거치게 된다[2]. 문제의 주 원인이었던 EXTCODESIZE의 수수료를 기존 20 GAS에서 700 GAS까지 인상하게 된다. 아래 표는 해당 하드포크에서 인상된 수수료를 보여준다.

표1. EIP-150 에서 변경된 수수료 정책 (단위: GAS)

이더리움이 경험한 이런 성능문제는 이번으로 끝나지 않는다. 2019년 12월 이더리움의 이스탄불 하드포크에서도 마찬가지로 성능문제로 인해 수수료 인상을 단행했다. 이스탄불 업데이트에서 포함된 EIP-1884는 EIP-150업데이트를 사례로 들면서 이 문제를 정확히 진단했다. 아래표는 EIP-1884에서 인상된 수수료 정책을 보여준다[3].

표2. EIP-1884 에서 변경된 수수료 정책 (단위: GAS)

위 표를 보면 EIP-150에서 한번 인상된 BALANCE, SLOAD가 다시 한 번 수수료가 인상된 것을 알 수 있다. SLOAD같은 경우에는 초기 설정인 50 GAS보다 16배 인상되었다. 이 업데이트가 불과 몇개월 전에 발생한 것을 보면 이더리움의 고질적인 성능 문제가 존재하고 있다는 것을 알 수 있다.

이더스캔에서 제공한 데이터에 따르면 이더리움을 Full-Node로 실행해서 기존 네트워크와 동기화 할 때 필요한 용량이 작성일 기준 3.9TB(테라 바이트)이다. 오늘 소개 할 논문에서의 내용을 잠깐 빌려오자면, 이더리움은 데이터가 많을 수록 성능저하를 겪고 있다. 아래 그림은 Full-Node 동기화 할 때 각 블록을 실행하는데 걸린 시간을 시간별로 보여주는 그래프이다. 그림을 보면 시간에 따른 성능저하가 눈에 띄게 보인다[3].

그림1. Full-Node 동기화 할 때 총 소요된 블록 실행 시간을 시간 순서로 보여주는 그래프이다.

위 그래프는 Full-Node를 0번 블록부터 570만번 블록까지 동기화 할 때 시간별로 블록을 실행시키는데 걸리는 시간을 말한다. 그래프의 맨 왼쪽이 동기화를 시작한 시간이고 오른쪽이 동기화를 완료한 시간이다. 여기서 말하는 블록 실행 시간이란 채굴을 뜻하는게 아니다. 순수하게 블록에 담긴 모든 트랜잭션을 실행시켜서 상태를 재구성하는데 까지 걸리는 시간이다. 그래프를 보면 최신 블록으로 갈수록 블록을 실행하는데 많은 시간이 필요한 것을 알 수 있다.

머클 패트리샤 트리의 성능 저하 원인

패트리샤 트리 (Patricia Trie)

머클 패트리샤 트리(MPT:Merkle Patricia Trie)는 이더리움이 상태를 저장할 때 이용하는 자료구조이다.

MPT는 패트리샤 트리와 머클트리를 결합해서 사용하는 구조를 가진다. 이더리움은 그 특성에 맞게 조금씩 수정해서 사용하고 있다. 먼저 패트리샤 트리부터 설명한 뒤 전체적인 그림을 맞춰 보자. 아래 트리 구조는 home, happen, hash, haste 이 네가지 단어를 패트리샤 트리로 구성된 결과를 나타낸다.

그림2. Patricia Trie 트리 구조 (Radix Trie라고도 부른다.)

위 트리에서 빨간색 라인을 따라가다 보면 hash라는 결과를 얻을 수 있다. 이 자료구조는 검색 엔진에서 첫 키워드를 입력하면 나타나는 자동 검색어 완성 기능을 구현할 때 주로 사용하고 있다. 이더리움에서는 이 자료구조를 가장 하위에 있는 리프 노드에 값을 저장하는 형태로 재구성했다. 아래 그림은 리프 노드에 계좌 잔액을 저장한 모습을 보여준다.

그림3. Patricia Trie 리프 노드에 값을 저장한 그림

위 트리에서 Alice의 잔액을 조회하려면 총 4개의 노드를 방문해서 0.27 ETH의 값을 얻는다. 위 트리 구조가 나타내는 내용은 아래와 같다.

우리는 이 트리구조를 이용해서 키-밸류(Key-Value)구조를 구현할 수 있다. 트리에 키를 입력하면 순회해서 리프 노드에 있는 밸류를 리턴하는 방식이다. 실제 이더리움에서는 키로 입력되는 값은 이더리움 계정 주소를 keccak 256 hash로 해시한 값이 된다. 이 값은 32 bytes의 길이를 가지기 때문에 이론적으로 Worst-case인 경우 순회해야 하는 경로의 개수가 64개나 된다. 값을 하나 얻기 위해서 64번이나 트리를 방문하게 되면 Disk I/O가 증가하기 때문에 그대로 사용할 수 없다. 그래서 이더리움의 설계자들은 위 패트리샤 트리에다가 Extension Node, Branch Node, Leaf Node 세 가지 타입의 노드를 추가해서 성능을 높이는 방식을 고안했다[4].

그림4. Modified Merkle Patricia Trie를 간략하게 표현한 그림이다.

위 자료구조에서 Extension Node를 통해 경로를 압축하긴 했지만 여전히 Worst-case인 경우 순회해야 하는 노드의 개수는 64개이다. 하지만 이런 상황이 나타나기 위해서는 독립적인 이더리움 계정 주소가 엄청나게 많이 필요하기 때문에 실제로 발생할 확률은 적다. 그렇기 때문에 어느 정도 합리적인 최적화는 이루었다고 말할 수 있다.

머클 트리(Merkle Tree)

머클 트리는 어떠한 값이 전체 트리 구조 안에 포함되어 있는지 검증할 때 사용한다. 이 것을 Membership Proof라고 부른다. 이더리움은 위에서 정의한 패트리샤 트리와 머클트리를 합친 Merkle Patricia Trie를 사용하고 있다. 이 자료구조 또한 머클트리와 동일하게 최상단 노드에 존재하는 Hash Root로 리프 노드의 값의 존재를 증명할 때 이용한다.

이더리움에서는 머클 패트리샤 트리의 각각의 노드의 키가 되는 Hash값을 키로, 각 노드의 값을 밸류로 해서 내부 데이터베이스인 Level DB에저장한다. Level-DB는 키-밸류 데이터베이스로서 키와 값을 1:1로 매칭해서 저장한다.

머클 패트리샤 트리의 성능 이슈

이더리움의 채굴자는 한 블록을 검증하거나 실행할 때 상태 트리를 조회 하고 트리의 내용을 변경하는 작업을 많이 수행한다. 머클 패트리샤 트리의 각 노드의 해시값은 키-밸류 데이터베이스인 Level DB에 저장되는데 이 때 값을 하나 조회하기만 해도 평균 7번의 디스크 I/O가 발생한다.

게다가, 머클 패트리샤 트리는 구조적인 특징으로 인해 Random I/O가 발생할 수 밖에 없다. 디스크는 무작위 위치를 특정해서 데이터를 읽는 것보다 순차적으로 읽는 것이 훨씬 빠르다. 이는 배열의 원소에 접근하는 속도가 링크드 리스트의 원소에 접근하는 속도보다 훨씬 빠른것과 유사하다. 이 성능을 개선한 SSD같은 경우에는 상황이 좀 괜찮지만 HDD의 Random I/O 처리 능력은 현저히 낮다. 아래 표는 LevelDB의 Read/Write 성능을 보여준다[5].

표3. Level DB의 Read/Write 성능 비교

위 데이터에 따르면 random/sequential write는 그렇게 큰 차이는 보이지 않는다. 하지만 random/sequential read는 현저하게 성능 차이가 눈에 보인다. 이 번 포스팅에서 소개 할 mLSM 논문에서는 이 문제를 I/O amplification problem이라고 정의한다. 해당 논문에서는 이더리움에서 random read I/O가 얼마나 자주 발생하는지 측정해서 아래 결과를 도출했다[6]. 현재 생성된 970만개의 블록 중 첫 160만개의 블록을 동기화 하는 동안만 측정했기 때문에 현재 상황과는 많이 다를 수 있다.

표4. 첫 160만개 블록을 동기화 하는 동안 발생한 요청(Metrics)와 수행된 I/O개수

이 논문에서는 이더리움의 성능저하 원인을 많은 LevelDB 조회로 진단했다. 위에서 말한 것 처럼 Disk I/O는 random access에 취약한데, 이더리움의 자료구조 디자인 특성상 random access를 할 수 밖에 없다. 다만 위 [표4]는 이더리움의 커뮤니티가 폭발적으로 성장하기 전에 수행된 실험이기 때문에 현재 이더리움 상황을 정확히 대변하는 수치는 아니다. 만약 위 실험 방법론을 현재 그대로 적용하면 더 심각한 결과를 얻을 것이라고 생각한다. 논문의 발표일은 2018년 6월이다.

최근 CURG에서도 실험을 위해 이더리움 트랜잭션을 수집하고 있었다. 현재 이더리움에서 830만번 블록부터 960만번 블록까지 저장된 트랜잭션의 총 개수가 1억 5000만개 정도이다. 위 논문에서 진행된 실험이 520만개의 트랜잭션만을 가지고 진행된 걸 감안하면 현재 상황에서 실험을 다시 할 필요가 있다고 생각한다.

본 포스팅에서 소개하는 “mLSM : Making Authenticated Storage Faster in Ethereum” 논문은 텍사스 대학교 오스틴의 석사 과정 대학원생이 USENIX HotStorage 19’ 에 제출한 논문이다. 6 페이지의 짧은 논문이기 때문에 실험 내용이 많이 부족해 보일 수 있다. 다만, 그가 진단했던 문제점과 진행한 연구방식은 다른 연구자가 참고하기에 부족하지 않다고 생각한다.

EVM 대체 무엇이 문제인가

위에서 진행된 실험이 오래전에 진행된 실험이기 때문에 정확한 판단을 하기에 적절하지 않을 수 있다. 그래서 2019년에 멜버른 대학교의 Renlord Yang이 실험한 내용을 소개하려고 한다. 이 논문에서는 제네시스 블록부터 470만개의 블록을 동기화 하면서 EVM의 OPCODE별로 수행시간을 측정했다[7].

`표5. EVM의 OPCODE별 수행시간 편차

이 논문에서는 고성능 컴퓨터와 일반 가정용 컴퓨터 두 대에 이더리움을 설치해보고 수행시간을 구했다. [표5]는 그 중 가정용 컴퓨터(Machine B)에서 실행한 결과를 가져온 것이다. Machine B는 Intel i7–4770@3.40GHz의 쿼드 코어와 16GB 메모리, SATA3 SSD가 장착된 모델이다.

위 표에서 BALANCE OPCODE의 평균 Time-to-Gas는 12,883이다. 여기서 단위는 나노세컨드 이다. BALANCE의 평균 총 실행 시간을 구하려면 수수료 * μ 를 하면 된다. 이 경우엔 BALANCE의 수수료가 700이고 μ가 12,883 이기 때문에 총 수행시간은 9,018,100 나노 세컨드 (9.018 밀리 세컨드)가 된다.

내가 만약 150명의 사용자의 계정 잔액을 조회하는 스마트 컨트랙트를 작성해서 실행한다면 채굴자가 이 트랜잭션을 실행하는데 1.35초가 걸린다는 의미이다. 이더리움이 현재 한 블록당 평균 100~150개의 트랜잭션을 처리하고 있는데 내가 이런 트랜잭션을 100개 작성했다면 이 트랜잭션을 모두 실행하는데에만 135초가 걸린다는 의미이다. 이더리움은 이런 상황을 방지하기 위해 그동안 지속적으로 수수료를 높여왔다. 어쩌면, 이더리움은 시스템 설계 문제로 인해 발생된 비효율을 사용자에게 비용으로 청구하고 있었는지도 모른다.

머클 패트리샤 트리의 캐시 무효화 문제

위에서 성능 저하의 주 원인이 많은 LevelDB 접근이라고 설명했다. 사실 이 문제를 가장 간단히 해결하는 방법은 머클 패트리샤 트리의 모든 노드들을 캐시에 올려두는 것이다. 하지만, 불행하게도 우리는 3TB가 넘는 메모리를 가지고 있지 않다. 그렇다면 자주 접근하는 데이터, 즉 유난히 많이 거래하는 계정의 정보만 캐시에 올려둔다면 성능 문제를 어느 정도 해결할 수 있지 않을까? mLSM 논문의 저자는 그것도 해결방법이 될 수 없다고 말한다.

그림5. Machine B에서 측정한 캐시 히트율

위 그림은 멜버른 대학의 Renlord Yang이 Machine B에서 관찰한 캐시 히트율이다. LevelDB의 자체 캐싱 기능을 사용하지 않고 이더리움이 최적화한 캐시 매커니즘을 따랐다. 그림 왼쪽에 가장 밝은 부분을 보면 1밀리 세컨드의 수행시간을 요구하는 OPCODE가 10⁶ 개나 발견 되었음에도 캐시 히트율은 0에 가깝다. 이 실험을 진행한 Renlord Yang은 이더리움의 캐시 매커니즘의 효과가 미미하다고 평가했다.

캐시 매커니즘이 적절히 동작하지 않는 이유는 mLSM의 논문의 저자 Pandian Raju가 잘 설명해주고 있다. 그가 진단한 이유는 이더리움의 머클 트리의 특징과 연결되어 있다. 머클 패트리샤 트리의 각 노드를 캐시에 올릴 때 필요한 정보는 키와 밸류 뿐만 아니라 Membership Proof에 필요한 Proof 정보까지 캐시에 올려두어야 한다. 하지만 머클 트리는 리프 노드의 값이 바뀌면 그에 해당하는 모든 부모 노드의 해시값이 바뀌기 때문에 캐시에 올려둔 데이터 전체가 Invalidation이 발생한다. 이 문제를 쉽게 보여주기 위해 머클 패트리샤 트리를 간단하게 그려보았다.

그림6. 머클 패트리샤 트리의 내용이 캐시 메모리에 어떻게 저장되는지 보여준다.

[그림 6]을 보면 0xa2023a의 데이터를 캐시에 어떻게 저장하는지 보여준다. 리프 노드의 데이터를 캐시에 올리기 위해서는 전체 키 값(주소)과 밸류, 그리고 Membership Proof과정에 필요한 모든 값을 Proof필드에 저장하면 된다. 이제 이 키를 캐시에 올림으로써 O(1) 복잡도로 값을 조회할 수 있다. 만약 이 키값이 캐시에 저장되어 있지 않는다면 총 2번에 걸쳐서 트리 탐색을 해야 한다. 실제 이더리움에서는 트리의 깊이가 깊기 때문에 여러번에 걸쳐서 탐색해야 한다. 이제 캐시 매커니즘을 이용함으로서 값을 빠르게 조회 할 수 있게 된다.

하지만, 머클 트리 특성상 하나의 데이터가 변경되면 모든 부모 노드의 해시값이 변경 되기 되기 때문에 이미 캐시에 올려져 있는 데이터와 불일치가 발생한다. 즉, 캐시에 올려져 있는 모든 데이터 즉시 Invalidation 된다. 아래 그림은 이 문제를 보여준다.

그림7. 리프 노드의 값이 변경되면서 캐시 전체가 Invalidation되는 모습을 그린 그림

[그림 7]에서는 0xa2023a 계정이 0xa2022f 계정으로 10 ETH를 전송한 다음, 변경된 상태 트리 모습을 보여준다. hashC와 hashD노드의 값이 바뀌면서 상위 노드에 있던 hashA의 값이 바뀌고 그로 인해 RootHash의 값이 바뀌었다. 위 그림에서 주황색 대각선 패턴이 그려져 있는 노드가 단일 송금으로 인해 값이 변경된 것을 보여준다. 결과적으로 RootHash의 값이 변경되었기 때문에 캐시에 저장된 Proof값 전체가 사용할 수 없게 되었다. 위와 같은 문제로 이더리움의 캐시 레이어는 위 그림 대로 구현되어 있지는 않다. 이더리움의 캐시 레이어는 최근 128 블록의 state trie정보만 메모리에 올려둔다. 이는 이더리움에서 분기가 발생하면 빠르게 롤백 해야 하기 때문이다. 즉 트리 구조를 메모리에 올려둔 것 뿐이라서 트리 탐색은 그대로 메모리에서 진행한다.

논문의 저자는 이 문제를 해결하기 위해 Log Structured Merge Tree(LSM)의 도입을 제안한다. 이 LSM의 목적은 하나의 글로벌 상태 트리에서 데이터를 조회할 때 탐색하는 트리와 데이터를 수정할 때 쓰는 트리를 분리하는 것이다. 이것이 만약 보안성을 해치지 않고 트리를 분리할 수 있다면 데이터를 수정하는 행위가 Lookup Tree의 내용을 변경하지 않으므로 캐시가 Invalidation되는 주기를 늦출 수 있다.

Merklized LSM의 접근 방법

Log Structured Merge Tree(이하 LSM)은 LevelDB를 비롯한 RocksDB, Apache Cassandra, HBase등의 데이터베이스에 흔히 쓰이고 있는 자료구조이다. LSM의 기본적인 아이디어는 데이터를 쓸 때는 메모리에 쓰고 있다가 메모리에 작성된 데이터의 크기가 어느 정도 임계치에 도달하면 디스크에 Merge(Flush)함으로써 쓰기 성능(Write Performance)을 높이는 것이다.

LSM은 Level 0k까지 여러 개의 계층 구조로 되어있다. Level 0은 메모리 영역으로 데이터를 작성하면 Level 0에 최초로 기록이 된다. 그리고 Level 1k층에서는 주기적으로 k → k+1 층으로 데이터를 병합한다. LevelDB의 핵심 스토리지 아키텍처가 이 LSM 구조를 기반으로 하고 있다. LevelDB는 주기적으로 compaction 작업을 거치는데 이게 바로 LSM의 병합 과정이다. 아래 그림은 LSM이 어떻게 동작하는지 보여준다.

그림8. Log-Structured Merge Tree(LSM)의 동작 방법

위 그림에서 △모양은 하나의 이진 탐색 트리를 나타낸다. LSM의 동작 방법을 천천히 설명하자면 모든 데이터 쓰기 요청은 Level 0의 메모리 영역에 저장된다. 그리고 데이터가일정 주기 커지면 Level 0에 존재했던 트리와 Level 1에 존재하던 트리가 병합이 발생한다. 그리고 다시 데이터가 Level 0에 쓰이기 시작한다. 이런 과정이 반복되면서 Level 1의 트리도 크기가 커지면 (2) Compaction 발생해서 Level 1의 트리와 Level 2의 트리가 병합된다. LSM이 Compaction 작업을 한 번에 처리하지 않고 이렇게 나눈 이유는 병합 과정이 트리를 단순히 이어 붙이는 것이 아니라 재구성 하는 작업 이기 때문에 이 부담되는 과정을 작은 단위로 나눈 것이다.

mLSM의 에서는 LSM 구조를 그대로 사용해서 State Trie를 여러개의 서브 트리로 분리한 다음 분리된 서브트리로 머클 트리를 구성하는 방법으로 캐시 무효화 문제의 해결 방법을 제안했다. 이렇게 하면 모든 트랜잭션 요청으로 인한 상태 변경은 Level 0의 트리에서만 발생하므로 Level 1+ 에 있는 트리는 내용이 변경되지 않는다. 따라서, Level 1+에 있는 트리 중 자주 접근하는 내용은 캐시 메모리에 저장해서 캐시 미스를 줄이고 나중에 Compaction 과정이 발생할 때만 병합된 State Trie만 다시 캐시 메모리에 작성하면 된다.

그림 9. mLSM의 여러 개의 서브 트리와 글로벌 상태 루트 해시 구성

위 [그림 9]와 같이 각 서브 트리의 Root Hash만 모아서 Global State Root를 구성한다. 이 때 Global State Root는 새로운 블록이 생성 될 때마다 변경되기 때문에 캐시에 저장하지 않는다. 캐시에 저장되는 부분은 Level 0~k 사이에 존재하는 트리 중 자주 접근되는 데이터만 캐시에 저장하는 방법으로 캐시 미스를 상당히 개선할 수 있고 데이터가 변경 된다 하더라도 캐시 무효화가 발생하지 않는다.

결론

mLSM의 논문 저자는 위 자료구조를 직접 구현해서 실험하지는 않았다. 또한 mLSM의 치명적인 단점이 하나 존재하는데, 캐시 미스가 발생하면 Level 1~k 에 존재하는 모든 서브 트리를 탐색하면서 데이터를 찾아야 한다는 것이다. 이더리움의 머클 패트리샤 트리는 최악의 경우에도 64번의 탐색으로 데이터를 찾을 수 있는 반면, 이 경우에는 기약 없는 여정이 시작된다.

이번 이 논문을 읽으면서 mLSM에서 제안한 새로운 자료구조가 나이브 하게 설계 된 것 처럼 보였고 논문의 설명이 많이 부족했다. 또한 직접 실험을 하지는 않았기 때문에 검증된 모델이라고도 보기 어렵다. 하지만, 블록체인의 스토리지 성능 부분을 연구하고 싶은 사람들에게 해당 논문이 분석한 문제점과 연구 방법론은 살펴 볼 가치가 있다고 생각한다.

Reference

[1] The Ethereum network is currently undergoing a DoS attack

[2] EIP-150, Vitalik Buterin, 2016–09–24

[3] EIP-1884, Martin Holst Swende, 2019–03–28

[4] Ethanos Lightweight Bootstrapping for ethereum

[5] Google Github, LevelDB

[6] mLSM : Making Authenticated Storage Faster in Ethereum

[7] Empirically Analyzing Ethereum’s Gas Mechanism