SMaRtTrie: Reducing Checkpoint’s Impact in SMR Systems with a CTrie Data Structure

• Erick Pintor PUCRS
• Fernando Luís Dotti PUCRS

DOI: https://doi.org/10.5753/sbrc.2021.16751

Resumo

State Machine Replication (SMR) is a well-established approach for the development of fault tolerant systems through replication. Durable SMR systems rely on command logging and checkpoints for fast recovery upon failures. However, checkpoints are known to impact service's throughput as traditional SMR architectures stop serving requests in order to ensure checkpoint consistency. In this paper, we present SMaRtTrie: a simple in-memory key-value storage built on a concurrent trie data structure that supports the creation of consistent checkpoints in parallel with command execution. Experimental evaluation shows that SMaRtTrie can reach the same throughput as other commonly used solution while sustaining 78% throughput during checkpoints.

Referências

Bessani, A., Santos, M., Felix, J., Neves, N., and Correia, M. (2013). On the efficiency of durable state machine replication. In 2013 fUSENIXg Annual Technical Conference (fUSENIXgfATCg 13), pages 169–180.

Bessani, A., Sousa, J., and Alchieri, E. E. (2014). State machine replication for the masses with bft-smart. In 2014 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, pages 355–362. IEEE.

Cooper, B. F., Silberstein, A., Tam, E., Ramakrishnan, R., and Sears, R. (2010). Benchmarking cloud serving systems with ycsb. In Proceedings of the 1st ACM symposium on Cloud computing, pages 143–154.

Défago, X., Schiper, A., and Urb´an, P. (2004). Total order broadcast and multicast algorithms: Taxonomy and survey. ACM Computing Surveys, 36(4):372–421.

Fischer, M. J., Lynch, N. A., and Paterson, M. S. (1985). Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2):374–382.

Freeman, A. (2015). The object pool pattern. In Pro Design Patterns in Swift, pages 137–156. Springer.

Harris, T. L., Fraser, K., and Pratt, I. A. (2002). A practical multi-word compare-and-swap operation. In International Symposium on Distributed Computing, pages 265–279. Springer.

Herlihy, M. and Wing, J. M. (1990). Linearizability: A correctness condition for concurrent objects. ACM Transactions on Programing Languages and Systems, 12(3):463– 492.

Lamport, L. (1978). Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7):558–565.

Lamport, L. et al. (2001). Paxos made simple. ACM Sigact News, 32(4):18–25.

Mendizabal, O. M., Dotti, F. L., and Pedone, F. (2017). High performance recovery for parallel state machine replication. In 2017 IEEE 37th International Conference on Distributed Computing Systems (ICDCS), pages 34–44.

Okasaki, C. (1999). Purely functional data structures. Cambridge University Press.

Ongaro, D. and Ousterhout, J. (2014). In search of an understandable consensus algorithm. In 2014 fUSENIXg Annual Technical Conference (fUSENIXgfATCg 14), pages 305–319.

Prokopec, A., Bronson, N. G., Bagwell, P., and Odersky, M. (2012). Concurrent tries with efficient non-blocking snapshots. In Proceedings of the 17th ACM SIGPLAN symposium on Principles and Practice of Parallel Programming, pages 151–160.

Schneider, F. B. (1990). Implementing fault-tolerant services using the state machine approach: A tutorial. ACM Computing Surveys (CSUR), 22(4):299–319.

Stärk, R. F., Schmid, J., and Börger, E. (2012). Java and the Java virtual machine: definition, verification, validation. Springer Science & Business Media.

Zheng, W., Tu, S., Kohler, E., and Liskov, B. (2014). Fast databases with fast durability and recovery through multicore parallelism. In 11th fUSENIXg Symposium on Operating Systems Design and Implementation (fOSDIg 14), pages 465–477.