1. distribute new package to all servers;
2. run an additional application service on all servers and run some quick tests on each of them to verify proper working;
3. add new application servers to load balancers;
4. upgrade data model to new version (we use postgresql, and this happends in a single db transaction, and remember that our new version x is compatbible with both the current and the previous data model);
5. remove old application services from load balancers;
6. upgrade successful.
If anything goes wrong, we can roll back each of these steps. Note that this whole process, perhaps needless to say, is fully automated.
By running multiple versions inside the load balancer at the same time, and having the requirement that version x + 1 is always compatible with version x, this procedure allows us to seamlessly upgrade to a new version without any downtime.