Microservices and "down for maintenance" deployments are not generally practiced together. You would deploy microservices in the context of cluster orchestration and fault-tolerant load balancing.
Service gamma needs to serve 300 requests per second. Your load testing and capacity planning exercise tells you this means it needs, at minimum, 5 instances. Consequently, you instruct your cluster scheduler to run 7, so you can tolerate 2 failures.
Service delta depends on gamma.
You want to upgrade gamma. You instruct the build system to create a build of gamma-2.0 while keeping gamma-1.0 around.
You then instruct the cluster scheduler to upgrade gamma to gamma-2.0. One at a time, it stops an instance of gamma-1.0 and spins up gamma-2.0 in its place. It might hard-stop the old process, letting requests to it be retried behind the scenes (statistically, they should hit an alive instance before too many retries). Or it might remove the targeted instance from the load balancer, give it some time to "drain" what it's already working on (possibly including sending it a signal through the OS), kill it, spin up a gamma-2.0 process, health-check the new gamma-2.0 process, and the finally add the address of the new gamma-2.0 process to the load balancer. Repeat until all gamma-1.0 processes are dead and replaced with gamma-2.0.
For very large deployments you might act on more than one instance at a time. The important thing is that during a deploy, there are always enough alive instances of the service being deployed to meet the service level objective for dealing with incoming traffic in a timely and correct manner. You'd want to plan for "shit happens" failures to coincide with a deployment, which is why I said tolerate 2 failures and not 1. The instance being upgraded at a given moment is "failed" and some other failure could happen at the same time.
During this process, you would watch your dashboards, alerts, and error log aggregation of gamma for any irregularities. If you see an unacceptable increase in latency or error rate correlated with the rollout percentage of gamma-2.0, then you (or an automated system) might instruct the cluster scheduler to rollback. The cluster scheduler might also decide to rollback if some percentage of gamma-2.0 instances fail a health check (i.e. can't respond to "hey are you alive" or just exit immediately).
A rollback runs the same process, replacing gamma-2.0 instances with gamma-1.0 instances.
The result is that, from delta's perspective, gamma is always alive. If someone deploys a bad change to gamma, than some percentage of delta's requests are problematic, but only for a little while.
This has some interesting consequences. For example, you don't get to make breaking API changes in one shot: you're going to have mutually incompatible versions running side-by-side. You might add a new endpoint in gamma, start using it in delta, and then finally remove the old endpoint in gamma with 3 separate deploys. You can avoid this by (correctly) using an RPC framework with support for backwards-compatible changes (Thrift, gRPC, etc). So, for example, you add an optional field to the end of a response from gamma-2.0. delta-1.0's Thrift decoder won't know what it's about, and just silently drop it and function as before. delta-2.0 will interpret and use it correctly. If gamma is ever rolled back to 1.0, delta-2.0 is still required to function correctly in the absence of the field, because it's marked optional.
You can also do blue-green deployments. Let's say you're running gamma-1.0 on the blue side. You build up 7 gamma-2.0 instances on the green side, and validate that they're functioning properly. Then you instruct the load balancer to shift traffic over to the green side. Once the blue side is dark (no traffic) you're free to reuse it for the next deployment. Downside is, you need a smarter load balancing layer, and 2x the hardware capacity.
Real-world cluster schedulers with this kind of functionality include Mesos with Aurora, Mesos with Marathon, and Kubernetes.
Services can still go down. For example, if the new gamma deploy is bad but no one figures out to rollback, delta's requests may all fail. Say delta retries each failed requests 3 times. Delta's upstream consumer lambda may interpret these errors from delta as cause to retry 3 times. Soon you've got 9x the usual traffic to gamma. Even if you fix the problem and deploy a correct gamma-3.0, gamma-3.0 probably can't stay alive under 9x the load it was designed for. This is why we use the circuit breaker pattern.
