A patching operation on an availability group cluster having a plurality of nodes is disclosed. The patching operation is performed in a plurality of iterations, each including determining a current state of each of the plurality of nodes, selecting a next node based on the current state, and patching the next node. A secondary replica node is selected as the next node before the a primary replica node. Each secondary replica node is patched in accordance with a first priority, upon patching each of the secondary replica node, a failover target node for patching the primary replica node is selected, the failover target node is selected based on a second priority, and according to the second priority, a healthy synchronous secondary replica node of the plurality of nodes is selected as the failover target node before an unhealthy synchronous secondary replica node of the plurality of nodes.