State machine replication is at the heart of almost every strongly consistent distributed system. Despite this, it is widely believed that state machine replication protocols like MultiPaxos are too slow, too complicated, and too hard to implement in practice. In this thesis, we take a step towards debunking these myths. We do so with a novel technique called compartmentalization that involves decoupling a protocol into its simplest components and then scaling each component independently. We compartmentalize MultiPaxos and increase its throughput by over 10x. We then apply compartmentalization to a family of complex state machine protocols called generalized multi-leader protocols. Through our compartmentalization, we bring clarity to a family of protocols that were previously extremely difficult to understand. Finally, we use compartmentalization to design a new reconfiguration protocol based on Vertical Paxos that state machine replication protocols can use to replace failed machines with new machines without any downtime.