Patent attributes
A method for communicating messages between a service and a virtual machine instance may include receiving a message from a service. The message includes a target instance identification of at least one virtual machine instance (VMI) to receive the message. A notification of the message and the target instance identification is stored in a message queue for each of a plurality of host servers associated with a plurality of VMIs. The message is stored in a message store without storing at least a portion of the message in the message queue. A request for undelivered messages is received from a VMI associated with a customer account. In response to the request, it is determined that a local cache contains an indication that the message is undelivered, where the local cache is within at least one of the plurality of host server computers associated with the VMI sending the request.