[논문 리뷰] Block-STM : Scaling Blockchain Execution by Turning Ordering Curse to a Performance Blessing

• Authors : Rati Gelashvili, Alexander Spiegelman, Zhuolun Xiang, George Danezis, Zekun Li , Dahlia Malkhi
• ACM CCS 2022

 

[Purpose]

• Diem blockchain 에서의 연구
• 합의 단계에서 leader validator 가 블럭(proposed block)을 하나 만들어냈다고 가정하고, 그 블록을 입력을 받는 상황.
• 블럭 내의 트랜잭션들을 검증하기 위해서는 모든 트랜잭션을 순차적으로 실행시켜야하는데, 이를 병렬로 실행시켜 최적화하는 방법에 대한 논문.
• 트랜잭션 간 의존성을 on-the-fly 방식으로 해결하는 것이 장점.

 

[Key ideas]

https://developers.diem.com/docs/transactions/basics-life-of-txn/

• 입력 받은 블럭의 트랜잭션 순서를 그대로 유지(preset order)하면서, 병렬적으로 수행하고자 함. (in memory execution)
• OCC(in-memory multi-version shared data structure) 와 preset order 를 이용하는 것이 핵심 아이디어.
• 이 때 트랜잭션간 존재하는 의존성을 해결하는 것이 주요한 challenge 라고 볼 수 있음. -> collaborated scheduler 를 통해 해결함. (의존성이 발생하는 것을 detect 하고, 줄줄이 의존성이 있는 트랜잭션들을 estimate 후 pending 시키고, 다음 수행할 트랜잭션들을 선택하는 등의 작업을 수행함.)
• BOHM이라는 deterministic databases 에 관한 연구에서 모티브를 가져온 것을 보임. BOHM 은 트랜잭션의 의존 관계를 DAG으로 미리 계산한 후에, 그것을 바탕으로 병렬처리함. 하지만 이 논문에서는 pre-computing 없이, 실행 도중 의존관계를 관리할 수 있는 방법(runtime write-estimation)을 제안하였고, 그 결과가 deterministic 함.(perset order 를 순차 실행시킨것과 동일)
• 한 블록 내의 트랜잭션을 모두 처리하고 나면, 메모리에 있는 multi-version shared data 를 storage 에 커밋하는 방식.

 

[Implementation Features]

• 두 개의 concurrent priority waiting queue (execution, validation) 을 만들어서, utilization 이 떨어지지 않도록 함.
• 어디까지 execution (validation) 했는지를 알려주는 일종의 포인터 execution_idx (validation_idx) 를 사용함.
• read set validation에 실패하면 해당 트랜잭션의 write set 이 접근한 메모리를 모두 ESTIMATE 라고 마킹한다. 이 마커를 읽는 트랜잭션들은 앞서 실패한 트랜잭션에 의존성이 있는 것으로 판단하고, dependency 배열에 추가하고 즉시 abort 시킨다.
•  

 

[Implementation Results]

• Diem과 Aptos에서 각각 110k tps, 170k tps로, 순차처리 방식에 비해 17~20 배 정도 빠른 성능 향상 (32 threads 기준)
• contended workload 에서는 각각 50k, 80k tps 를 보임.
• BOHM 모델에 dependency graph 을 완벽하게 제공한 상태에서 실험한 결과와 비슷한 성능.

 

[Review]

• Preset and deterministic order 가 주어진 채로 STM 을 이용할 때, 앞선 의존성이 해결되고 완전히 commit 될때까지  뒤의 스레드들은 stall 되어야만 한다. 이를 ordering curse 라고 한다. 근데 블록체인 상에서는 블록 단위로 commit 하면 되기 때문에, 개별 트랜잭션이 완전히 commit 되는 것을 기다릴 필요없이 optimistic 하게 블록 단위로 해결한 것이다. 오히려 이 점을 performance blessing 이라고 표현한 것이다.
• 인메모리 방식이라는 점에서 속도는 빠를 수 있으나, 불안정함이 단점이 될 수 있을 듯 하다. 중간에 머신이 종료되면 처음부터 다시 validation 을 진행해야한다. BFT의 특성상 3f+1 개 중 2f+1 개만 살아있으면 되니까.. 괜찮으려나? 
• 메모리 사용량을 언급해주었으면 좋았을 거 같다. (근데 이건 smart contract의 종류와, workload에  따라 달라질 거 같긴한데..) 블럭 크기가 클 때, 메모리가 부족하면 프로세스가 죽을 수 있기 때문이다.