A configuration manager of a storage service receives a set of service requirements, comprising one or more of: a performance requirement for one or more types of storage operations, or an access interface type requirement Based on the service requirements, a candidate storage configuration that includes one or more data store instances and a first log-based transaction manager is generated. Subsequent to an approval of the first storage configuration by a client, the establishment of the data store instances and the log-based transaction manager is initiated.