Embodiments presented herein disclose a VPN service which includes a cluster of VPN appliances that requires only an eventually consistent database to share VPN session data among cluster nodes. Doing so provides a VPN service that can scale both horizontally (i.e., the VPN service can support large numbers of VPN appliances) as well as geographically (i.e., nodes of the cluster do not need to be physically proximate to one another in order to satisfy latency requirements). Thus, the VPN service can provide regional endpoints to VPN clients that do not share common points of failure or administrative burdens.