With the new NAT Gateway this looks like something of the past, but recently I had to configure a NAT instance in our deployment. This Cloudformation configuration creates an autoscaling group with 1 instance allows recovery. The following diagram shows the resources created by the stack.