This sounds crazy, but it's essential if you can't guarantee that you can atomically deploy a new service version AND any other services that call it.
Creating backwards compatible releases means sticking to some rules, things like:
- you can add fields but you can never delete them
- you can add new methods but you can't remove old ones
Having really detailed logging helps a lot. If you want to deprecate a method you can remove it from calling clients first and then use the logs to confirm it isn't being called any more before removing it from the service.
It's a lot if work, and teaching a large engineering team how to be productive in this kind of environment is decidedly non trivial.