Load balancing includes receiving, from a client, a connection request to establish a connection with a server; determining load balancing state information based at least in part on the connection request; synchronizing the determined load balancing state information across a plurality of service engines, including to invoke an atomic read-miss-create (RMC) function on a distributed data store service; and distributing the connection to a selected server among a plurality of servers according to a result of the RMC function.