Reasons for replication; fault tolerant services

Reasons for replicating a service

1. Performance enhancement: replicas share load and can be placed near users, so response time falls (web caching, mirror sites, CDN). Scalability in numbers and geography.
2. Increased availability: if a server fails or is unreachable, another replica provides the service. With n replicas each failing with probability p, availability is 1 − pⁿ.
3. Fault tolerance: the system keeps correct service despite crashes, and, using voting among replicas, even arbitrary (Byzantine) faults. Data survive disk or machine failure.
4. Disconnected operation: mobile users work on local copies when the network is down.
5. Reduced network traffic because requests are answered locally.

Fault-tolerant services

A fault-tolerant service continues to give correct answers even if some of its servers fail. It is made by replicating the service on several replica managers (RMs) so that failures are masked. Main models:

1. Passive (primary-backup): front ends talk to one primary RM, which executes requests and sends updates to the backups. If the primary fails, a backup is promoted. Tolerates crash faults, with less work than active.

2. Active replication: requests are multicast in total order to all RMs, which all execute them; replies are compared or the first one used. Hides failures immediately and can tolerate Byzantine faults.

3. Gossip / lazy replication: any replica can be contacted; updates are propagated in the background. Highly available, with weaker consistency.

Correctness criteria: linearizability (operations appear in real-time order of one copy) or sequential consistency. A fault-tolerant service requires also failure detection, request ids to avoid duplicate execution, state transfer to repaired replicas, and enough replicas: f+1 for f crashes, 2f+1 for f Byzantine failures with voting (3f+1 if the replicas must also agree).