고성능 트랜잭션 처리를 위한 확장 가능한 상태 기계 복제
Scalable State Machine Replication for High-Performance Transaction Processing※ 이 논문은 인천대학교 2023년도 자체연구비 지원에 의하여 연구되었음
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
상태 기계 복제(SMR: State Machine Replication)는 결함 감내를 제공할 수 있는 기술로 잘 알려져 있다. 클라이언트의 요청이 같은 순서로 정렬되어 복제들에서 실행되도록 하고, 결정적 알고리즘의 실행 결과로 모든 정상 복제는 각 요청을 실행하고 나면 같은 상태에 이르게 된다. 그런데 SMR에는 확장성이 없다. 즉, 복제의 수가 늘어나더라도 처리량은 늘어나지 않는다. 이 논문에서는 전체 시스템의 성능을 제고할 수 있는 확장 가능한 SMR 프로토콜을 제안한다. 지리적으로 분산되어 있는 클라이언트와 복제들의 데이터 액세스 특성을 고려해서 전체 시스템을 여러 개의 파티션으로 분할한다. 각 파티션마다 클라이언트 요청의 순서를 결정하는 리더를 둔다. 액세스해야 하는 데이터가 상충하지 않는다면 두 개 이상의 트랜잭션이 동시에 처리되게 하는 것이다. 과반의 동의를 얻은 리더의 강력한 강제 쓰기를 근간으로 하는 Raft 알고리즘을 확장하여 구현한 테스트베드 상에서의 실험을 통하여 효용성을 입증하였다. 기존의 접근 방식과 비교하여 데이터의 지역성에 따라 트랜잭션 처리 응답 시간을 줄일 수 있음을 확인할 수 있었다.
Abstract
State Machine Replication (SMR) is a well-known technique designed to provide fault tolerance. Client requests are coordinated to be executed in the same order at all replicas, and after the execution of deterministic algorithm every normal replica arrives at the same state. However, SRM is not scalable. That is, the throughput does not increase with the number of replicas. This paper is to propose a SMR protocol which can increase the overall system performance. Considering the properties of the clients and replicas geographically distributed, the system is divided into multiple partitions. A leader is allocated to each partition to determine the sequence of client requests. The protocol is designed to allow more than two transactions executed simultaneously unless there is collision of data to be accessed. The effectiveness of the protocol was demonstrated through experiments on a testbed implemented by expanding the Raft algorithm which is based on majority voting and strong write according to a powerful leader. Experiments have shown that transaction response delays can be reduced with the locality of data compared to the existing approach.
참고문헌 (14)
- L. Lamport, "Time, clocks, and the ordering of events in a distributed system", Communications of the ACM, 21(7), pp.558~565 (1978)
- C. E. Bezerra, "Scalable State-Machine Replication", 44th Annual IEEE, 2014, ~
- J. C. Yim, "Blockchain and Consensus Algorithm", ETRI Electronics and Telecommunications Trends, 33(1), pp.45~56 (2018)
- G-T Nguyen, "A survey about consensus algorithms used in blockchain", Journal Inf Process Syst, 14(1), pp.101~128 (2018)
- Diego Ongaro, "In Search of and Understandable Consensus Algorithm(Extended Version)", Proc. of the USENIX Annual Tech. Conf (2014)
- "release master" (2021)[URL]
- L. Lamport, "Paxos made simple", ACM SIGACT News, 32(4), pp.18~25 (2001)
- M. Pease, "Reaching agreement in the presence of faults", Journal of the ACM (JACM), 27(2), pp.228~234 (1980)
- Marius Poke, "Algorithms for High-Performance State-Machine Replication", Doctor, pp.2019
- P. Coelho, "GoePaxos+ : Practical Geographical State Machine Replication", 40th International Symposium on Reliable Distributed Systems (SRDS) (2021)
- F. Ryabinin, "SwiftPaxox : Fast Geo-Replicated State Machine", 21st USENIX Symposium on Networked Systems Design and Implementation (2024)
- Andrew S. Tanenbaum, "Distributed Systems : Principles and Paradigms" (2016), Pearson International Edition
- "Reducing Recovery Time of Raft Replicated Servers for Hyperledger Fabric", Journal of Korean Institute of Next Generation Computing, pp.38~51 (2023)
- "An Improvement of Hyperledger Fabric Raft Algorithm toward Enhancing Availability", Journal of Korean Institute of Next Generation Computing, pp.84~97 (2022)