TY - GEN
T1 - When Paxos meets erasure code
T2 - 23rd ACM Symposium on High-Performance Parallel and Distributed Computing, HPDC 2014
AU - Mu, Shuai
AU - Chen, Kang
AU - Wu, Yongwei
AU - Zheng, Weimin
PY - 2014
Y1 - 2014
N2 - Paxos-based state machine replication is a key technique to build highly reliable and available distributed services, such as lock servers, databases and other data storage systems. Paxos can tolerate any minority number of node crashes in an asynchronous network environment. Traditionally, Paxos is used to perform a full copy replication across all participants. However, full copy is expensive both in term of network and storage cost, especially in wide area with commodity hard drives. In this paper, we discussed the non-triviality and feasibility of combining erasure code into Paxos protocol, and presented an improved protocol named RS-Paxos (Reed Solomon Paxos). To the best of our knowledge, we are the first to propose such a combination. Compared to Paxos, RS-Paxos requires a limitation on the number of possible failures. If the number of tolerated failures decreases by 1, RS-Paxos can save over 50% of network transmission and disk I/O. To demonstrate the benefits of our protocol, we designed and built a key-value store based on RS-Paxos, and evaluated it on EC2 with various settings. Experiment results show that RS-Paxos achieves at most 2.5x improvement on write throughput and as much as 30% reduction on latency, in common configurations.
AB - Paxos-based state machine replication is a key technique to build highly reliable and available distributed services, such as lock servers, databases and other data storage systems. Paxos can tolerate any minority number of node crashes in an asynchronous network environment. Traditionally, Paxos is used to perform a full copy replication across all participants. However, full copy is expensive both in term of network and storage cost, especially in wide area with commodity hard drives. In this paper, we discussed the non-triviality and feasibility of combining erasure code into Paxos protocol, and presented an improved protocol named RS-Paxos (Reed Solomon Paxos). To the best of our knowledge, we are the first to propose such a combination. Compared to Paxos, RS-Paxos requires a limitation on the number of possible failures. If the number of tolerated failures decreases by 1, RS-Paxos can save over 50% of network transmission and disk I/O. To demonstrate the benefits of our protocol, we designed and built a key-value store based on RS-Paxos, and evaluated it on EC2 with various settings. Experiment results show that RS-Paxos achieves at most 2.5x improvement on write throughput and as much as 30% reduction on latency, in common configurations.
KW - Asynchronous message passing model
KW - Consensus
KW - Erasure code
KW - Paxos
KW - State machine replication
UR - https://www.scopus.com/pages/publications/84904438453
U2 - 10.1145/2600212.2600218
DO - 10.1145/2600212.2600218
M3 - Conference contribution
AN - SCOPUS:84904438453
SN - 9781450327480
T3 - HPDC 2014 - Proceedings of the 23rd International Symposium on High-Performance Parallel and Distributed Computing
SP - 61
EP - 72
BT - HPDC 2014 - Proceedings of the 23rd International Symposium on High-Performance Parallel and Distributed Computing
PB - Association for Computing Machinery
Y2 - 23 June 2014 through 27 June 2014
ER -