Systems and methods for implementing stateful services using cloud-based resources are described. A server computing system determines existence of a first volume based on a launch of a first instance by an auto-scaling group (ASG). The first volume is to have a resource tag having a value similar to a value of a resource tag of the ASG. The first volume was previously attached to a second instance terminated by the ASG. Based on a successful determination of the existence of the first volume, the server computing system attaches the first volume to the first instance. Based on a failed determination of the existence of the first volume, the server computing system generates a second volume, attaches the second volume to the first instance, and set a resource tag of the second volume to a value similar to the value of the resource tag of the ASG.