Well, you break your services out onto stateless and stateful machines. After that, you make sure that each of your stateful services is resilient to individual

Well, you break your services out onto stateless and stateful machines. After that, you make sure that each of your stateful services is resilient to individual node failure. I prefer to believe that if you can't roll your entire infrastructure over to new nodes monthly then you're unprepared for the eventual outage of a stateful service. Most databases have replication but you need to make sure that the characteristics of how the database handles a node failure are well understood. Worst case you use EBS, put your state on it, snapshot it regularly, and ship those snapshots to another region because when EBS fails it fails hard. Also, logs make every machine stateful. Use something like logstash to centralize that state.