Failure recovery for cloud-based services

A tangible non-transitory computer readable storage media, including program instructions loaded into memory that, when executed on processors, cause the processors to implement a computer-implemented method of recovery from failure of a service instance, in a service chain of services that perform at least services A and B, using service instance AA and service instances BA and BB to perform the services A and B, respectively, the computer-implemented method performing actions including:

• the service instance BA identifying the service instance BB as having a secondary role for packets carrying a stream affinity code which is specified in a service map distributed to service instances, and synchronizing service instance BA state information with the service instance BB after processing a first packet;
• after failure of the service instance BA, the service instance AA receiving an updated service map, and preparing to forward to the service instance BA a second packet, wherein the second packet includes a same stream affinity code as the first packet forwarded before the failure;
• determining from the updated service map that the service instance BB is available and servicing the same stream affinity code as the service instance BA;
• and
• forwarding the second packet to the service instance BB instead of the service instance BA.