Feature Request: Leader Election

This issue has been migrated from [#13126](https://github.com/matrix-org/synapse/issues/13126).

---

When running synapse in Kubernetes, then it's typically run as a StatefulSet with 1 replica in order to make sure that there's always at most one instance of synapse running. When the Kubernetes node where this instance runs goes unreachable, then a new synapse instance can only be created after either (1) the node is back up again and confirms that the old synapse instance doesn't run anymore or (2) an admin manually confirms that the old synapse instance doesn't run anymore (e.g. by confirming that the unreachable node is down and not just network-partitioned).

**Description:**

It would be nice, if synapse could be run as a Deployment with multiple replicas that perform leader election.

Note that this feature request is not about load balancing but merely about high availability. In a setup with worker processes, this feature request only applies to the main process.

There should always be only one leader that actually performs work. When the leader goes unreachable, the remaining replicas should elect a new leader after x time. The leader continuously confirms that he's still the leader, and if the last confirmation was y time ago, where y < x, then the leader stops doing work.

**Possible solution:**

The leader election itself could be done with a sidecar container per synapse replica. There exist container images for this job. This is described [here](https://kubernetes.io/blog/2016/01/simple-leader-election-with-kubernetes/#leader-election-with-sidecars). synapse itself would then just need to continuously query the sidecar over HTTP via localhost, getting back the name of the current master, and compare that name with the own hostname.