1. A computer system for determining and recovering from a notification service failure, the computing system comprising: one or more processors; and one or more computer readable hardware storage devices, wherein the one or more computer readable hardware storage devices comprise computer executable instructions that are executable by at least one of the one or more processors to cause the computer system to perform the following: provide a client with read access to a first queue of one or more queues of a notification service, the first queue having a first queue identifier and being created at a time during which the notification service has a first notification service identifier, the notification service identifier and the first queue identifier being provided to the client, the first queue being maintained in a soft memory; receive a client request at the notification service, the client request including at least the notification service identifier; compare the notification service identifier received from the client request to a current notification service identifier maintained by the notification service; upon determining the notification service identifier received from the client request fails to match the current notification service identifier, determine a failure of the notification service has occurred and that the first queue is lost from the soft memory; and create a new queue with a new queue identifier.