Replication objectives; primary-backup

Major objectives of replication

1. Enhancing performance: replicas near clients and sharing the request load reduce response time and server load (caching, mirroring).
2. Increasing availability: the service remains available when some servers fail or are unreachable.
3. Fault tolerance: correct service despite crash (or Byzantine) failures; data survive failures.
4. Scalability: more users and more data can be supported by adding replicas.
5. Transparency: replicas appear to the user as a single logical copy of an object (replication transparency), and keep consistency between copies.

Primary-backup (passive) replication model

There is one primary replica manager (RM) and one or more backup (slave) RMs. Front ends communicate only with the primary.

 Client -> Front End -> Primary RM --updates--> Backup RM 1
                          |                 \-> Backup RM 2
        <------ reply ----+     (acks from backups)

Sequence of events:

1. Request: the front end sends the request, with a unique id, to the primary.
2. Coordination: the primary checks the id to avoid executing it twice, and orders requests (so it gives a total order).
3. Execution: the primary executes the request and stores the response.
4. Agreement: if it is an update, the primary sends the new state and the response to all backups, which acknowledge.
5. Response: the primary replies to the front end after the acknowledgements.

On primary failure: backups detect it (heartbeat/timeout), elect or promote one backup as the new primary (e.g. bully election), the front end is redirected, and the new primary continues from the last state. A request in progress is re-sent by the front end, and the id prevents double execution.

Properties: tolerates f crash failures with f+1 replicas, cannot tolerate Byzantine faults, gives linearizability if the primary is correct, and has a short failover delay. Examples: replicated databases, Sun NIS (Yellow Pages), ISIS.